Notes
Slide Show
Outline
1
Quality-of-Service:
Methods and Software
  • Vincenzo Liberatore
  • Case Western Reserve University
2
Pervasive Computing
3
Real-Time Issues
  • Quality-of-Service (QoS)
    • Ensure low delay, jitter, loss rates, and high bandwidth
    • Implement below, at, or above IP
  • Real-Time Protocol (RTP)
    • Transport protocol
    • Support real-time communication
4
Quality-of-Service
  • Problem
    • Best-effort networks
    • Congestion
  • Metrics
  • Implementation
    • Application-middleware
    • IP
    • Data link
5
Quality-of-Service (QoS)
  • Best-effort model
    • Prevalent in the Internet
    • No end-to-end circuit
    • Packets can be delayed
    • Delay is often unpredictable
    • No bandwidth reservation
  • QoS
    • Ameliorate best-effort model
    • E.g., packet priorities
  • Impact on control
    • Delays
      • E.g., forces small feedback gains
    • Packet drop-outs
      • Infinite delays
    • Jitter
      • Delay variability
      • Often more troublesome than average delays
    • Bandwidth
      • Scalability

6
QoS and Congestion
  • Objectives
    • QoS protects from cross-traffic
    • QoS does not protect from failures, interferences
    • But in some cases, it does
  • Possible strategies
    • Priorities
    • Reservation
    • Weighted Fair Queuing
7
Congestion: Example
  • Scenario
    • One controller
      • Discrete LQR
      • Assumes 50ms sampling rate
      • Assumes no delays
    • n inverted pendulum
    • Bottleneck: T1 line
    • RTT: 3ms
    • Plot response over time
  • Congestion
    • When more plants are added
    • Scalability
8
Congestion and Performance
9
Overprovisioning
  • Over-provisioning
    • Large bandwidth implies short queues
    • 1Gbps Ethernet vs. 1Mbps CAN
    • Useful for probabilistic QoS
  • Risk
    • Congestion caused by even one cross-traffic flow
    • TCP tends to take over
    • Example: ping a machine in same building with and without one FTP flow as cross-traffic
    • Explains poor plant performance with one flow
10
Congestion and TCP
  • One TCP flow can congest a link
    • 1 plant, 1 TCP flow
    • Scalar linear plant
  • Sporadic TCP [R03]
    • Congest link sporadically
    • Average utilization rate low
    • Difficult convergence
11
Overprovisioning
  • Access networks
    • Any flow can saturate the network
    • Exacerbated by TCP
      • Attempt to use all the bandwidth
  • Core network
    • Good news
      • Statistical multiplexing
      • Relatively low rate flows
    • Bad news
      • Not ready yet for VoIP [MTK02]
      • Only 50Mbps over-provisioning on half of the paths [ASS03]
12
Congestion – Recap
  • Scalability
    • Multiple plants eventually congest bandwidth
  • Aggressive behaviors
    • TCP expands to fill available bandwidth
    • Aggressive flows
  • Over-provisioning
    • Does not deal with above
13
Quality-of-Service
  • Problem
    • Best-effort networks
    • Congestion
  • Metrics
  • Implementation
    • Application-middleware
    • IP
    • Data link
14
QoS Assurances
  • So, what do we want from QoS?
  • Worst-case
    • Reasoning
      • Reason about system timing
      • Priorities make it easy
    • Is it cross-traffic?
    • Is it failures (e.g., network partition)?
    • Failures as first class citizens
  • Average-case
    • Non-sense
    • Exacerbated by TCP
  • Tail
    • E.g., 99-percentile
    • Must be paired with middleware, fault-tolerance
15
Quality-of-Service
  • Problem
    • Best-effort networks
    • Congestion
  • Metrics
  • Implementation
    • Application-middleware
    • IP
    • Data link
16
Protocol Stack
  • Dealing with complex systems
  • Explicit structure allows identification, relationship of complex system’s pieces
    • Layered reference model for discussion
  • Modularization eases maintenance, updating of system
    • Change of implementation of layer’s service transparent to rest of system
    • E.g., change in gate procedure doesn’t affect rest of system
17
QoS
18
Middleware
  • Between application and transport
    • Libraries to provide advanced functionality
    • Hide communication
  • Applications
    • Resource Discovery
    • Remote Procedure Calls
    • Security
    • Interoperability (e.g., since Real-Time Corba)
    • Scheduling, resource management, performance analysis
    • Multicast
  • Software development
    • Simpler, faster
    • State-of-the-art functionality
  • Middleware over IP
    • Wealth of libraries for IP
    • Critical advantage of the Internet Protocol
19
Middleware and QoS
  • End-point middleware
    • Assume best-effort, unreliable network with no explicit QoS provision
    • End-points compensate for vagaries
  • Previous work (example)
    • Voice-over-IP
    • Replay buffer
  • Address both congestion and transient failures
    • E.g., routing transients
20
Sampling and Control [ACC03]
  • Metrics
    • Stability and tracking
  • Delay characterization
    • Heavy tail: Pr[delay>x]~x-a
    • View delay spikes as transient failures
  • Contingency control
    • Used if no regular control received
    • Recover from delay spikes
21
Evaluation
  • Methodology
    • Collect Round-Trip Times Case ↔ NASA (and other locations)
    • Note: NASA is far from Case (in Internet distance)
    • Simulate scalar plant with fast dynamics
    • Use deadbeat control  but compensate for nominal RTT
  • Observations
    • Base case diverges
    • Contingency converges
22
QoS
23
QoS: from IP to data link
  • QoS at data link
    • E.g., priorities, token passing, VPN
    • E.g., Ethernet
  • QoS at IP
    • Protocol
      • IPv4: 4 basic Types-of-Service (ToS)
      • IPv6: many flow ids, Classes-of-Service (CoS)
  • QoS: from data link to IP
    • Code-point mapping
    • IP addresses
24
QoS in Multi-hop Networks
  • Queuing
    • Packets are forwarded from one network to another
    • Packets are queued at routers (store-and-forward)
    • Protect from cross-traffic cause congestion
  • Per-Hop Behaviors (PHB)
    • Behavior of individual router
      • E.g., Forward before all other queued packets
    • Maps into data link QoS
    • Depends on Class-of-Service
  • Class of service
    • Assigned by source or shapers
    • Imply PHB
25
QoS at IP
  • Best effort IP
    • IP is de facto a convergence layer
      • Must deal with heterogeneous networks
    • Architectural principle
  • Difficult to deploy QoS at IP
    • Hard to provide end-to-end QoS
26
QoS
27
QoS: LAN and WAN
  • Data link
    • Network layers
      • Data link QoS independent of IP, transport, middleware
      • Middleware and transport motivate IP
    • Multiple possible solutions
      • E.g., Ethernet switches with 802.1p, 802.1q
  • Administrative
    • Can do anything (e.g., RVSP) within any single administrative domain
    • Need much cooperation with multiple administrative domains
28
Ethernet
  • IEEE 802.1p
    • Priority
      • Three bits, recommended values
        • 0-3=normal
        • 4-7=high
    • Multicast control
      • Multicast packets forwarded after unicast packets with same priority
  • IEEE 802.1q
    • Objective: create Virtual LANs (VLAN)
    • Cross-traffic, multicast control
    • Locally administered
29
QoS: Summary
  • Traffic isolation
    • Cross-traffic can degrade performance
    • Worst-case and probabilistic assurance
  • Application and Middleware
    • Adaptive
  • Network
    • Queueing, scheduling, forwarding
  • Data link
    • Priorities and beyond
30
Real-Time Protocol
31
Network Layer
  • Convergence layer (IP)
  • IP (Internet Protocol)
  • IP supports multiple data links
  • Multiple transports support IP
  • Transport independent of data link
  • Mix and match
    • E.g., RTP/UDP over 802.11, Ethernet
    • E.g., TCP over Infinet
32
Transport Layer
  • Design choice
    • TCP or RTP/UDP
  • Three rules:
    • Real-time data: RTP/UDP
      • Sensor data
      • Video, sound, I/O
      • Control
    • Bulk data: TCP
      • Log download
      • Software upgrades
      • Coarse supervision
    • Middleware rules
      • E.g., RealAudio over UDP
      • E.g., HTTP over TCP
      • Usually, right choice made by middleware designer
      • However, bad choices can propagate
33
Real-Time Transport
  • RTP-RTCP
    • RTP is a data transfer protocol
    • RTCP is a companion control protocol
  • Problems above solved
  • Support for
    • Feedback on connection quality
    • Timing, synchronization
    • End-point description, aggregation
    • Frame boundaries
  • Flexibility
    • Application-level framing
    • Custom-tailored reaction to congestion, packet losses, but
    • No error detection, recovery
    • Independent of underlying transport
      • Can work over TCP
  • Small header
  • Multicast support
34
RTP Session
  • Session identified by
    • IP addresses
    • Port numbers
  • IP addresses
    • Unicast or multicast
  • RTP port number
  • RTCP port number
    • RTP port number + 1
35
RTP Packet
  • Header
    • Version (2 bits)
    • Padding (1 bit)
    • Extension (1 bit)
    • CSRC count (4 bits)
    • Marker (1 bit)
    • Payload type (7 bits)
    • Seqno (16 bits)
    • Timestamp (32 bits)
    • SSRC id (32 bits)
    • CSRC ids (32 bits each)

  • Payload
  • Padding
    • Padding
    • Pad count (8 bits)
36
RTCP
  • Control protocol
    • Works in conjunction with RTP
  • Functions
    • QoS monitoring and congestion control
      • Convey feedback on quality of data delivery and information of membership
      • Modify transmission rates
      • Diagnostic
    • Source identification
    • Session size estimation and scaling
    • Session control
      • E.g., user names  to be displayed
  • Reports
    • Participants periodically send RTCP report packets
    • Statistics, e.g.,
      • Number of packets sent
      • Number of packets lost
      • Inter-arrival jitter
37
Mixers
  • Merge several media streams of the same types into one new stream
  • Can reduce bandwidth consumption
  • Mixer appears as new source
    • Use new SSRC
    • Put original SSRCs in CSRC list.
38
Translators
  • Single media stream
  • May convert encoding
  • Protocol translation
    • E.g., ATM↔IP
    • Keep original SSRCs
39
Mixers and Translators
40
Implementation
  • RTP Libraries
    • Bell Laboratories (in C)
      • http://www.bell-labs.com/topic/swdist/
    • JRTPLIB (in C++)
      • http://lumumba.luc.ac.be/jori/jrtplib/jrtplib.html
    • liveCaster and other tools
      •  http://live.sourceforge.net/
    • RTP Tools (rtpdump, rtpmon, rtpsend,…)
      • http://www.cs.columbia.edu/IRT/software/rtptools/


41
RTPlib
42
RTPlib
  • Get session information
    • RTPMemberInfoGetStatus();
    • RTPMemberInfoGetRTPAddr();
    • RTPMemeberInfoGetPktCnt();
    • RTPMemberInfoGetUserInfo();
    • RTPSessionGetBandwidth();
    • RTPFindMember();
  • Advanced functions
    • RTPSplitCompoundRTCP();
43
Conclusions
  • Quality-of-Service
  • Real-Time Protocols
  • Web resources (next)
44
Web resources
  • Network Control Systems
    • At Case
      • http://vincenzo.liberatore.org/NetBots/
    • Community-wide repository
      • Under construction
  • Network Research Lab
    • http://vincenzo.liberatore.org/netlab/
45