Quality of Service (QoS) in the Internet: Architectures and Mechanisms

Posted on Sep 3, 2024 in Computers

Lecture 5: Internet Evolution Part II: Better-than-Best-Effort

QoS, IntServ, DiffServ, RSVP, RTP

Why Better-than-Best-Effort (QoS-enabled) Internet?

• To support a wider range of applications (Real-time, Multimedia, etc.)
• To develop sustainable economic models and new private networking services
• Current flat-priced models and best-effort services are insufficient for businesses

Quality of Service: What is it?

What is QoS? It refers to the level of performance a network provides to an application, ensuring its proper functioning. “Better performance” can be described by parameters or measured by metrics.

Generic Parameters:

• Bandwidth
• Delay
• Delay-jitter
• Packet loss rate (or loss probability)

Transport/Application-specific Parameters:

• Timeout
• Percentage of “important” packets lost

What is QoS (contd)? These parameters can be measured at various granularities: “micro” flow, aggregate flow, and population. QoS is considered “better” if:

1. More parameters can be specified
2. QoS can be specified at a fine-granularity.

QoS Spectrum:

In a FIFO service discipline, the performance assigned to one flow is convoluted with the arrivals of packets from all other flows! We can’t achieve QoS with a “free-for-all.” We need new scheduling disciplines that provide “isolation” of performance from the arrival rates of background traffic.

Fundamental Problems

Conservation Law (Kleinrock): Σ_r(i)W_q(i) = K

Irrespective of the chosen scheduling discipline:

• Average backlog (delay) is constant
• Average bandwidth is constant
• Zero-sum game => need to “set-aside” resources for premium services

QoS Big Picture: Control/Data Planes

QoS Components: QoS => set aside resources for premium services

1. Specification of premium services: (service/service level agreement design)
2. How much resources to set aside? (admission control/provisioning)
3. How to ensure network resource utilization, do load balancing, flexibly manage traffic aggregates and paths? (QoS routing, traffic engineering)
4. How to actually set aside these resources in a distributed manner? (signaling, provisioning, policy)
5. How to deliver the service when the traffic actually comes in (claim/police resources)? (traffic shaping, classification, scheduling)
6. How to monitor quality, account, and price these services? (network mgmt, accounting, billing, pricing)

How to Upgrade the Internet for QoS?

Approach: decouple end-system evolution from network evolution

• End-to-end protocols: RTP, H.323, etc., to spur the growth of adaptive multimedia applications. Assume best-effort or better-than-best-effort clouds.
• Network protocols: IntServ, DiffServ, RSVP, MPLS, COPS … To support better-than-best-effort capabilities at the network (IP) level.

QoS SPECIFICATION, TRAFFIC, SERVICE CHARACTERIZATION, BASIC MECHANISMS

Service Specification

• Loss: probability that a flow’s packet is lost
• Delay: time it takes a packet’s flow to get from source to destination
• Delay jitter: maximum difference between the delays experienced by two packets of the flow
• Bandwidth: maximum rate at which the source can send traffic

QoS Spectrum:

• Hard Real Time: Guaranteed Services
  • Service contract: Network to client: guarantee a deterministic upper bound on delay for each packet in a session. Client to network: the session does not send more than it specifies.
  • Algorithm support: Admission control based on worst-case analysis. Per-flow classification/scheduling at routers.
• Soft Real Time: Controlled Load Service
  • Service contract: Network to client: similar performance as an unloaded best-effort network. Client to network: the session does not send more than it specifies.
  • Algorithm Support: Admission control based on the measurement of aggregates. Scheduling for aggregate possible.

Traffic and Service Characterization

To quantify a service, one has to know:

1. Flow’s traffic arrival
2. Service provided by the router, i.e., resources reserved at each router

Examples:

• Traffic characterization: token bucket
• Service provided by the router: fix rate and fix buffer space

Characterized by a service model (service curve framework)

Token Bucket

Characterized by three parameters (b, r, R)

• b – token depth
• r – average arrival rate
• R – maximum arrival rate (e.g., R link capacity)

A bit is transmitted only when there is an available token. When a bit is transmitted, exactly one token is consumed.

Characterizing a Source by Token Bucket

• Arrival curve – maximum amount of bits transmitted by time t
• Use token bucket to bound the arrival curve

Example Arrival Curve

• Maximum amount of bits transmitted by time t
• Use token bucket to bound the arrival curve

Per-hop Reservation

Given b, r, R, and per-hop delay d, allocate bandwidth r_a and buffer space B_a such that to guarantee d

What is a Service Model?

The QoS measures (delay, throughput, loss, cost) depend on offered traffic and possibly other external processes. A service model attempts to characterize the relationship between offered traffic, delivered traffic, and possibly other external processes.

Arrival and Departure Process

Traffic Envelope (Arrival Curve)

Maximum amount of service that a flow can send during an interval of time t

Service Curve

Assume a flow that is idle at time s and it is backlogged during the interval (s, t). Service curve: the minimum service received by the flow during the interval (s, t)

Big Picture: Delay and Buffer Bounds

Mechanisms: Traffic Shaping/Policing

• Token bucket: limits input to specified Burst Size (b) and Average Rate (r). Traffic sent over any time T
• a.k.a Linear bounded arrival process (LBAP)
• Excess traffic may be queued, marked BLUE, or simply dropped

Mechanisms: Queuing/Scheduling

• Use a few bits in the header to indicate which queue (class) a packet goes into (also branded as CoS)
• High $$ users classified into high priority queues, which also may be less populated => lower delay and low likelihood of packet drop
• Ideas: priority, round-robin, classification, aggregation, …

Mechanisms: Buffer Mgmt/Priority Drop

Ideas: packet marking, queue thresholds, differential dropping, buffer assignments

SCHEDULING

Packet Scheduling

Decide when and what packet to send on the output link. Usually implemented at the output interface.

Focus: Scheduling Policies

• Priority Queuing: classes have different priorities; class may depend on explicit marking or other header info, e.g., IP source or destination, TCP Port numbers, etc.
• Transmit a packet from the highest priority class with a non-empty queue
• Preemptive and non-preemptive versions

Scheduling Policies (more)

• Round Robin: scan class queues serving one from each class that has a non-empty queue

Round-Robin Discussion

• Advantages: protection among flows. Misbehaving flows will not affect the performance of well-behaving flows. Misbehaving flow – a flow that does not implement any congestion control. FIFO does not have such a property.
• Disadvantages: More complex than FIFO: per flow queue/state. Biased toward large packets – a flow receives service proportional to the number of packets.

Generalized Processor Sharing (GPS)

• Assume a fluid model of traffic
• Visit each non-empty queue in turn (RR)
• Serve infinitesimal from each
• Leads to “max-min” fairness
• GPS is un-implementable! We cannot serve infinitesimals, only packets.

Generalized Processor Sharing

A work-conserving GPS is defined as:

W_i(t₁, t₂) / W(t₁, t₂) = w_i / Σ_jεB(t) w_j

where:

• w_i – weight of flow i
• W_i(t₁, t₂) – total service received by flow i during [t₁, t₂)
• W(t₁, t₂) – total service allocated to all flows during [t₁, t₂)
• B(t) – number of flows backlogged

Fair Rate Computation in GPS

• Associate a weight w_i with each flow i
• If the link is congested, compute f such that: Σ_iεB(t) w_i / f

Bit-by-bit Round Robin

• Single flow: clock ticks when a bit is transmitted. For packet i: P_i = length, A_i = arrival time, S_i = begin transmit time, F_i = finish transmit time. F_i = S_i + P_i = max (F_i-1, A_i) + P_i
• Multiple flows: clock ticks when a bit from all active flows is transmitted à round number. Can calculate F_i for each packet if the number of flows is known at all times. This can be complicated.

Packet Approximation of Fluid System

• Standard techniques of approximating fluid GPS
• Select the packet that finishes first in GPS, assuming that there are no future arrivals

Important properties of GPS

• Finishing order of packets currently in the system independent of future arrivals
• Implementation based on virtual time. Assign virtual finish time to each packet upon arrival. Packets served in increasing order of virtual times.

Fair Queuing (FQ)

Idea: serve packets in the order in which they would have finished transmission in the fluid flow system. Mapping bit-by-bit schedule onto packet transmission schedule. Transmit the packet with the lowest F_i at any given time.

Variation: Weighted Fair Queuing (WFQ)

Approximating GPS with WFQ Fluid GPS system service order. Weighted Fair Queueing selects the first packet that finishes in GPS.

FQ Example

FQ Advantages

• FQ protects well-behaved flows from ill-behaved flows. Example: 1 UDP (10 Mbps) and 31 TCPs sharing a 10 Mbps link.

System Virtual Time: V(t)

• Measure service, instead of time
• V(t) slope – rate at which every active flow receives service
• C – link capacity
• N(t) – number of active flows in the fluid system at time t

System Virtual Time

Virtual time (V_GPS)

– service that backlogged flow with weight = 1 would receive in GPS

Service Allocation in GPS

The service received by flow i during an interval [t₁, t₂), while it is backlogged, is:

W_i(t₁, t₂) = ∫_t1^t2 [w_i / Σ_jεB(t) w_j] C dt = w_i [V_GPS(t₂) – V_GPS(t₁)]

Virtual Time Implementation of Weighted Fair Queueing

• a_j^k – arrival time of packet k of flow j
• S_j^k – virtual starting time of packet k of flow j
• F_j^k – virtual finishing time of packet k of flow j
• L_j^k – length of packet k of flow j

Virtual Time Implementation of Weighted Fair Queueing

• Need to keep per flow instead of per packet virtual start, finish time only
• System virtual time is used to reset a flow’s virtual start time when a flow becomes backlogged again after being idle

System Virtual Time in GPS

Virtual Start and Finish Times

Big Picture

• FQ does not eliminate congestion à it just manages the congestion
• You need both end-host congestion control and router support for congestion control
• End-host congestion control to adapt
• Router congestion control to protect/isolate
• Don’t forget buffer management: you still need to drop in case of congestion. Which packet’s would you drop in FQ? One possibility: the packet from the longest queue.

QoS ARCHITECTURES

Parekh-Gallager Theorem

• Let a connection be allocated weights at each WFQ scheduler along its path so that the least bandwidth it is allocated is g
• Let it be leaky-bucket regulated such that # bits sent in time [t₁, t₂] 2 – t₁) + s
• Let the connection pass through K schedulers, where the kth scheduler has a rate r(k)
• Let the largest packet size in the network be P

Significance

• P-G Theorem shows that WFQ scheduling can provide end-to-end delay bounds in a network of multiplexed bottlenecks.
  • WFQ provides both bandwidth and delay guarantees
  • Bound holds regardless of cross-traffic behavior (isolation)
  • Needs shapers at the entrance of the network
• Can be generalized for networks where schedulers are variants of WFQ, and the link service rate changes over time

Stateless vs. Stateful QoS Solutions

• Stateless solutions – routers maintain no fine-grained state about traffic
  • Scalable, robust
  • Weak services
• Stateful solutions – routers maintain per-flow state
  • Powerful services
  • Guaranteed services + high resource utilization
  • Fine-grained differentiation
  • Protection
  • Much less scalable and robust

Existing Solutions

Integrated Services (IntServ)

• An architecture for providing QoS guarantees in IP networks for individual application sessions
• Relies on resource reservation, and routers need to maintain state information of allocated resources (e.g., g) and respond to new Call setup requests

Signaling semantics

• Classic scheme: sender initiated
• SETUP, SETUP_ACK, SETUP_RESPONSE
• Admission control
• Tentative resource reservation and confirmation
• Simplex and duplex setup; no multicast support

RSVP: Internet Signaling

• Creates and maintains distributed reservation state
• Decoupled from routing:
  • Multicast trees set up by routing protocols, not RSVP (unlike ATM or telephony signaling)
• Receiver-initiated: scales for multicast
• Soft-state: reservation times out unless refreshed
• Latest paths discovered through “PATH” messages (forward direction) and used by RESV messages (reverse direction).

Call Admission

• Session must first declare its QoS requirement and characterize the traffic it will send through the network
• R-spec: defines the QoS being requested
• T-spec: defines the traffic characteristics
• A signaling protocol is needed to carry the R-spec and T-spec to the routers where reservation is required; RSVP is a leading candidate for such a signaling protocol

Call Admission

• Call Admission: routers will admit calls based on their R-spec and T-spec and based on the current resources allocated at the routers to other calls.

Stateful Solution: Guaranteed Services

• Achieve per-flow bandwidth and delay guarantees
  • Example: guarantee 1MBps and
• Allocate resources – perform per-flow admission control
• Install per-flow state
• Challenge: maintain per-flow state consistent
• Per-flow classification
• Per-flow buffer management

Stateful Solution Complexity

• Data path
  • Per-flow classification
  • Per-flow buffer management
  • Per-flow scheduling
• Control path
  • Install and maintain per-flow state for data and control paths

Stateless vs. Stateful

• Stateless solutions are more:
  • Scalable
  • Robust
• Stateful solutions provide more powerful and flexible services
  • Guaranteed services + high resource utilization
  • Fine-grained differentiation
  • Protection

Question

• Can we achieve the best of two worlds, i.e., provide services implemented by stateful networks while maintaining the advantages of stateless architectures?
  • Yes, in some interesting cases. DPS, CSFQ.
• Can we provide reduced state services, i.e., maintain state only for larger granular flows rather than end-to-end flows?
  • Yes: Diff-serv

Differentiated Services (DiffServ)

• Intended to address the following difficulties with Intserv and RSVP:
• Scalability: maintaining states by routers in high-speed networks is difficult due to the very large number of flows
• Flexible Service Models: Intserv has only two classes, want to provide more qualitative service classes; want to provide ‘relative’ service distinction (Platinum, Gold, Silver, …)
• Simpler signaling: (than RSVP) many applications and users may only want to specify a more qualitative notion of service

Differentiated Services Model

• Edge routers: traffic conditioning (policing, marking, dropping), SLA negotiation
  • Set values in the DS-byte in the IP header based upon negotiated service and observed traffic.
• Interior routers: traffic classification and forwarding (near stateless core!)
  • Use DS-byte as an index into the forwarding table

Diffserv Architecture

Packet format support

• Packet is marked in the Type of Service (TOS) in IPv4, and Traffic Class in IPv6: renamed as “DS”
• 6 bits used for Differentiated Service Code Point (DSCP) and determine Per-Hop Behavior (PHB) that the packet will receive
• 2 bits are currently unused

Traffic Conditioning

• It may be desirable to limit the traffic injection rate of some class; the user declares a traffic profile (e.g., rate and burst size); traffic is metered and shaped if non-conforming

Per-hop Behavior (PHB)

• PHB: name for interior router data-plane functions
  • Includes scheduling, buff. mgmt, shaping, etc.
• Logical spec: PHB does not specify mechanisms to use to ensure performance behavior
• Examples:
  • Class A gets x% of outgoing link bandwidth over time intervals of a specified length
  • Class A packets leave first before packets from class B

PHB (contd)

• PHBs under consideration:
  • Expedited Forwarding: departure rate of packets from a class equals or exceeds a specified rate (logical link with a minimum guaranteed rate)
    • Emulates leased-line behavior
  • Assured Forwarding: 4 classes, each guaranteed a minimum amount of bandwidth and buffering; each with three drop preference partitions
    • Emulates frame-relay behavior

Question

• Can we achieve the best of two worlds, i.e., provide services implemented by stateful networks while maintaining the advantages of stateless architectures?
  • Yes, in some interesting cases. DPS, CSFQ.
• Can we provide reduced state services, i.e., maintain state only for larger granular flows rather than end-to-end flows?
  • Yes: Diff-serv

Scalable Core (SCORE)

• A trusted and contiguous region of the network in which:
  • Edge nodes – perform per-flow management
  • Core nodes – do not perform per-flow management

The DPS Approach

• Define a reference stateful network that implements the desired service

The DPS Idea

• Instead of having core routers maintaining per-flow state, have packets carry per-flow state

Dynamic Packet State (DPS)

• Ingress node: compute and insert flow state in the packet’s header
• Core node:
  • Process packet based on the state it carries and the node’s state
  • Update both packet and node’s state
• Egress node: remove state from the packet’s header

Example: DPS-Guaranteed Services

• Goal: provide per-flow delay and bandwidth guarantees
• How: emulate the ideal model in which each flow traverses dedicated links of capacity r
• Per-hop packet service time = (packet length) / r

Guaranteed Services

• Define the reference network to implement service
  • Control path: per-flow admission control, reserve capacity r on each link
  • Data path: enforce the ideal model by using the Jitter Virtual Clock (Jitter-VC) scheduler
• Use DPS to eliminate per-flow state in the core
  • Control path: emulate per-flow admission control
  • Data path: emulate Jitter-VC by Core-Jitter Virtual Clock (CJVC)

E.g., Streaming & RTSP

• User interactive control is provided, e.g., the public protocol Real-Time Streaming Protocol (RTSP)
• Helper Application: displays content, which is typically requested via a Web browser; e.g., RealPlayer; typical functions:
  • Decompression
  • Jitter removal
  • Error correction: use redundant packets to be used for the reconstruction of the original stream
  • GUI for user control

Using a Streaming Server

• Web browser requests and receives a Meta File (a file describing the object)
• Browser launches the appropriate Player and passes it the Meta File
• Player contacts a streaming server, may use a choice of UDP vs. TCP to get the stream

Receiver Adaptation Options

• If UDP: Server sends at a rate appropriate for the client; to reduce jitter, Player buffers initially for 2-5 seconds, then starts to display
• If TCP: sender sends at the maximum possible rate; retransmit when an error is encountered; Player uses a much larger buffer to smooth the delivery rate of TCP

H.323

• H.323 is an ITU standard for multimedia communications over best-effort LANs.
• Part of a larger set of standards (H.32X) for videoconferencing over data networks.
• H.323 includes both stand-alone devices and embedded personal computer technology as well as point-to-point and multipoint conferences.
• H.323 addresses call control, multimedia management, and bandwidth management as well as interfaces between LANs and other networks.

H.323 Architecture

Summary

•QoS big picture, building blocks

•Integrated services: RSVP, 2 services, scheduling, admission control etc

•Diff-serv: edge-routers, core routers; DS byte marking and PHBs

•Real-time transport/middleware: RTP, H.323

•New problems: Content delivery/web caching