- Forward


Integrated Services
An Introduction


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Motivation
Back Forward
  • Properties of IP:
    • "Cross traffic" is unpredictable and impacts traffic on other paths
    • IP provides best effort service (i.e., no service guarantees)
  • Possible Improvements:
    • Service guarantees (e.g., for real-time applications)
    • Service classes
Overview
Back Forward
  • Service Classes:
    • Guaranteed service class
    • Controlled-load service class (i.e., can tolerate some delay/loss)
  • Protocols and Algorithms:
    • Resource management
    • State management
Overview (cont.)
Back Forward
  • Approach:
    • Based on sessions and/or flows
    • Each flow has a stable path
    • Routers along the path are responsible for providing QoS
  • QoS Methods:
    • RSVP - for reservations
    • Traffic Shaping - controls turbulent flow
    • Admission Control - admits/rejects flow
    • Scheduling - of packets
Traffic Shaping
Back Forward
  • Goal:
    • Control the arrivals of packets to avoid/reduce turbulence
  • Leaky-Bucket Traffic Shaping:
    • Some incoming packets are discarded (i.e., leak)
    • Other packets are "regularized" (i.e., transmitted smoothly)
Admission Control
Back Forward
  • Goal:
    • Accept or reject packets
  • Approach:
    • Flow is admitted only if currently available resources can service the flow without affecting the QoS of previously admitted flows
Packet Scheduling
Back Forward
  • Goal:
    • Manage packets that are in queues in order to provide the required QoS
  • Components:
    • Packet classifier
    • Queues
First-In, First Out (FIFO) Scheduling
Back Forward
  • Defined:
    • Packets are served in the order they arrive
  • Issues:
    • Source has an incentive to transmit at a high rate (since the queue "favors" the most greedy flow)
    • It is hard to control the delay of packets through a network of FIFO queues
Priority Queue Scheduling
Back Forward
  • Defined:
    • Packets are placed in a priority-specific FIFO queue
    • The nonempty queue with the highest priority is served first
  • Issues:
    • Queues with low priorities can be starved of bandwidth
  • Types:
    • Preemptive - lower priority queues are preempted when packets arrive at a higher priority queue
    • Non-Preemptive
Earliest Deadline First Scheduling
Back Forward
  • Defined:
    • Serve the packet with the earliest deadline first
  • Process:
    • Compute the departure deadline for incoming packets
    • "Sort" packets based on deadline (using a heap)
Fair Scheduling
Back Forward
  • Idea:
    • Allocate resources in a fair manner
  • A Difficulty:
    • What does "fair" mean?
Some Concepts from Microeconomics
Back Forward
  • Efficient Policies:
    • Social welfare is increased (a.k.a., the Kaldor-Hicks/utilitarian criterion)
  • Equitable Policies:
    • Nobody is made worse off (a.k.a., the Pareto/egalitarian criterion)
  • Fair/Superfair Policies:
    • People would rather have what they have than what others have (a.k.a., the Baumol/envy criterion)
A Networking Example
Back Forward
  • The Situation:
    • Source A and B route through R to C
    • A wants 10Mb/s
    • B wants 100Mb/s
    • R has a capacity of 1.1MB/s
  • What is Fair?
    • A and B get equal shares (i.e., 0.55Mb/s each)
    • Shares are based on the 1:10 ratio of wants (i.e., A gets 0.1Mb/s and B gets 1Mb/s)
Max-Min Fairness
Back Forward
  • The Setting:
    • \(N\) sources share a link of rate \(C\)
    • \(W(f)\) denotes the "wanted" rate of \(f\)
    • \(R(f)\) denotes the "received"/allocated rate for \(f\)
  • The Algorithm:
    • while \(N \gt 0\)
      • Pick the source, \(f\) with smallest \(W\)
      • If \(W(f) \lt C/N\) set \(R(f) = W(f)\)
      • else set \(R(f) = C/N\)
      • Set \(N = N - 1\)
      • Set \(C = C - R(f)\)
An Example of Max-Min Fairness
Back Forward
  • The Situation:
    • \(N = 3\)
    • \(W(1) = 0.1\)
    • \(W(2) = 0.5\)
    • \(W(3) = 5.0\)
    • \(C = 1.0\)
  • Max-Min Fairness:
    • \(R(1) = 0.10\)
    • \(R(2) = 0.90 / 2 = 0.45\)
    • \(R(3) = 0.45 / 1 = 0.45\)
Bit-by-Bit Fair Queueing
Back Forward
  • Setup:
    • Packets belonging to a flow are placed in a FIFO queue for that flow
  • Servicing the Queues:
    • Queues are served one bit at a time in a round-robin
Weighted Bit-by-Bit Fair Queueing
Back Forward
  • Setup:
    • Packets belonging to flow \(f\) are placed in a FIFO queue for that flow
  • Servicing the Queues:
    • Queues are served \(w_f\) bits at a time in a round-robin
  • Also Known As:
    • Generalized Processor Sharing (GPS)
Packetized Weighted Fair Queueing
Back Forward
  • Setup:
    • Packets belonging to flow \(f\) are placed in a FIFO queue for that flow
  • Servicing the Queues:
    • Determine what time a packet would complete if we served flows bit-by-bit
    • Serve packets in order ot increasing finishing time
  • Also Known As:
    • Packetized Generalized Processor Sharing (PGPS)
Some Observations
Back Forward
  • Many routers support weighted fair queueing
  • Weighted fair queueing can be used to provide different rates to different flows
Summary of the Complete Process
Back Forward
  • Source asks for a guaranteed QoS
  • Source negotiates an arrivale rate with each router
  • Routers perform admission control to ensure they have sufficient resources
  • Each router along the path reserves resources using RSVP
  • Source starts sending packets at agreed rate
  • Router determines the flow for each packet and puts it in the appropriate queue
  • Router uses weighted fair queueing to serve packets
There's Always More to Learn
Back -