The Role of PCE in the Evolution of Transport Protocols : The Role of PCE in the Evolution of Transport Protocols Pfldnet 2005, Lyon, France
M. Y. 'Medy' Sanadidi
http://www.cs.ucla.edu/~medy
http://www.cs.ucla.edu/NRL/hpi/tcpw/
Recent Issues in Transport Protocols: Recent Issues in Transport Protocols Large Pipes Utilization
Steady state
Start-up
Impact of Wireless Links:
Last-hop wireless
Multihop contention networks
Fairness for asymmetric flows
Protocols Co-Existence
New Paradigms:
Voice/Video
Store-and-forward at Transport layer (e.g. PEPs, P2P/Overlays)
Example: Satellite/802.11 Networks: Example: Satellite/802.11 Networks
Outline : Outline Path Characteristics Estimation (PCE)
Prospects for Higher Efficiency
Future of Friendly Co-Existence
Addressing the New Paradigms
Summary
Path Characteristics Estimation (PCE): Path Characteristics Estimation (PCE) Characteristics of Interest:
Links capacity
Path ‘dynamic range’, i.e. buffering capacity
Cross traffic level, path-persistence, responsiveness
Random loss
Multihop wireless connectivity, contention, route diversity
Participating Nodes:
Sources only
Sources and Destinations
Forwarding nodes (routers, base stations, multihop wireless nodes)
Sharing a Link: Sharing a Link Flow2 Flow1 2 flows, red one is non-responsive fair share ? bandwidth residual bandwidth bottleneck interface queue backlog Buffer space Propagation Time
A Hierarchy of Characteristics: A Hierarchy of Characteristics Achieved rate
Delay/Dynamic Range
Packet loss Intensity
Path persistence
Elasticity Links capacities
Propagation times
Buffer space
Errors Cross Traffic Load Architecture Flow Behavior +
Path Capacity Estimation: Path Capacity Estimation Path Capacity: capacity of narrow link
Pathrate: rely on packet pair dispersion measurements followed by statistical processing of results
CapProbe: use dispersion measurements; perform on line filtering of results based on end-to-end delay
TcpProbe: an adaptation of CapProbe into TCP with minimal sender side only changes
CapProbe and TcpProbe: CapProbe and TcpProbe
Prospects for Higher Efficiency: Prospects for Higher Efficiency Steady State:
Congestion avoidance (FAST): stable at high throughput, co-existence ??, and random loss impact ??
Scaling up congestion recovery (HSTCP, STCP): higher throughput, but fairness and stability ??
Scaling up congestion recovery (BIC): improves on the above in fairness
Forwarder Based (XCP): superb, when we are done with implementation issues
PCE reliance (TCP Westwood, TCP Peach): Peach requires forwarder priority support, TCPW requires good estimation at high speeds
Using PCE: Using PCE Tahoe/Reno/NewReno estimate:
Packet loss via Dup Acks
RTT average and variance
Maintain a pipe size (or bandwidth-delay product) estimate: ssthresh
Vegas/FAST:
Achieved Rate and its relation to the Expected Rate, or equivalently RTT and RTTmin, or Queuing delay
HSTCP/STCP/BIC:
Use current window size (Expected Rate) in addition to all items above in Reno
Using PCE (2): Using PCE (2) TCPW estimates
Packet loss and type of loss
Narrow link capacity, or Path capacity
Achieved Rate
'Dynamic Range' resulting from buffering space:
(RTTmax-RTTmin)
XCP measures at forwarders the actual:
Links capacities
Load intensity
RTT (obtained from sources)
Large Pipes Measurements Results: Large Pipes Measurements Results
Acceptable Long Term Efficiency: Acceptable Long Term Efficiency
Some Difference in Completion Times: Some Difference in Completion Times
Co-Existence at Gbps Speed: Co-Existence at Gbps Speed
Random Loss Impact: Random Loss Impact
Effect of Random Loss: Effect of Random Loss
TCPW: Mining ACK Streams for PCE: TCPW: Mining ACK Streams for PCE Rely on PCE ( e.g. capacity, achieved rate, dynamic range) to determine an Eligible Rate Estimate (ERE)
ERE is used to size the congestion window after a packet loss Receiver Sender Internet Bottleneck packets ACKs measure
TCPW BE (2001): TCPW BE (2001) BE Sampling:
With Saverio Mascolo (P. Bari) and Claudio Casetti (P. Torino)
~ Packet pair
a noisy estimate of achieved rate/capacity
Provides throughput boost under random loss, overestimates under congestion
Efficient but not friendly
Slide21: TCPW RE (2002)
RE Sampling:
~ Packet train
Fair estimate under congestion, underestimates under random loss
Used in TCPW RE and inTCP Westwood+ (S. Mascolo)
Friendly
Adaptive Estimation in TCPW: Adaptive Estimation in TCPW
TCPW CRB: ERE BE if random loss, else ERE RE
TCPW ABSE: ERE RE andlt;X andlt; BE by continuously adapting the bandwidth sample width to congestion level
TCPW Astart: use ERE to help short lived flows
TCPW BBE: ERE u * C + (1-u) * RE,
where u is a congestion measure taking into account path dynamic range
Slide23: TCPW CRB (2002) Combined 'Rate' and 'Bandwidth'
Binary adaptive
Congestion measure: Expected Rate/Achieved Rate
Clarified Efficiency/Friendliness tradeoff Congestion measure Packet Loss Detected ssthresh, cwnd = BE x RTTmin over a threshold under a threshold Ssthresh, cwnd = RE x RTTmin
Slide24: TCPW ABSE (2002) Under Congestion Under No Congestion Adaptive Bandwidth Share Estimation
Adapt the sample interval Tk according to congestion level
Congestion measure, similar to Vegas
Tk ranges from one ‘interACK’ interval to current RTT
Better Efficiency/Friendliness profile than CRB
Helping Short Lived Connections: Helping Short Lived Connections Approaches:
Cached ssthresh
Larger initial window
PCE based: Hoe’s; TCPW Astart
Negotiation: Quick-Start
No problems here for XCP!
TCPW Astart (2003): TCPW Astart (2003) Take advantage of ERE :
Adaptively and repeatedly reset ssthresh ERE until sender window reaches estimated pipe size, or encounters packet loss Includes multiple mini ‘exponential increase’, and mini ‘linear increase’ phases
cwnd grows slower as it approaches BDP
Connection converges faster to its pipe size with less buffer overflow, since it adapts to pipe size and transient loading
Astart: First 20 Seconds Throughput: Astart: First 20 Seconds Throughput RTT =100ms, Buffer =BDP RTT =100ms, Bottleneck =40 Mbps Bottleneck capacity = 40 Mbps, Buffer =BDP
Good scaling with capacity and propagation time
Robust to buffer size variation
TCPW BBE (Work in Progress): TCPW BBE (Work in Progress) With H. Shimonishi (NEC, Tokyo)
'Buffer' and 'Bandwidth' Estimation
Estimates Capacity using TcpProbe (much more accurate than BE!!)
Higher efficiency at higher random loss rates (e.g. 5-10%)
Estimates Dynamic Range (related to buffer size)
Improves TCPW control as a function of congestion
The result is higher efficiency and robust friendliness even at small buffers!
TCPW BBE Algorithms (ICC 2005): TCPW BBE Algorithms (ICC 2005) Dynamic Range estimate
Dmax = RTTcong loss - RTTmin
Current Delay Distance
D = RTT – RTTmin Eligible Rate estimate
ERE = u * C + (1-u) * RE
Note: u=0 if D and Dmax are small
Opportunistic Friendliness of TCPW-BBE: Opportunistic Friendliness of TCPW-BBE If Reno under-perform: use all the opportunity provided without hurting co-existing Reno flows TCP-Reno
Sender Receiver 10M-1Gbps TCPW-BBE
Sender 0.001% loss Receiver RTT 40msec If Reno performs: achieve similar to Reno
The Future of Friendly Co-Existence: The Future of Friendly Co-Existence Defining Friendliness:
TCP Friendliness:
Achieve throughput equal to that of TCP Reno under some conditions (RTT, packet loss rate)
Problematic if Reno under-perform; e.g. under random losses
Opportunistic Friendliness:
If Reno performs, achieve similar to Reno
If Reno under-perform: use all the opportunity provided without hurting co-existing Reno flows
Evaluating a New Proposed Protocol:The Efficiency/Friendliness Profile: Evaluating a New Proposed Protocol: The Efficiency/Friendliness Profile Each point in the graph is obtained as follows:
N legacy flows =andgt;
legacy throughput tR1
total utilization U1
N/2 legacy, N/2 proposed flows =andgt;
legacy throughput tR2
Total utilization U2
Efficiency Improvement
E = U2 / U1
Friendliness
F = tR2 / tR1
E/F Profiles of TCPW BE, CRB and ABSE: E/F Profiles of TCPW BE, CRB and ABSE
E/F Profile of Vegas: E/F Profile of Vegas 1 1.1 1.2 1.3 1.4 1.5 0.4 0.6 0.8 1 1.2 1.4 Utilization Ratio G (Efficiency) Throughput Ratio L (Friendliness) N=2 N=4 N=8 N=16 N=24 Vegas vs. NewReno (RED) Vegas uses fixed targeted queue length =andgt; varying friendliness depending on number of connections!
Addressing New Paradigms: Addressing New Paradigms Audio/Video Streaming:
Increasing portion of the total traffic with distinct requirements
Multihop Wireless:
Difficult fundamental issues
Store-and-forward at the Transport Layer:
Revisit early problems and new opportunities
Continuous Media Transport: Continuous Media Transport Requirements:
Minimum bandwidth
Upper bound on delay
Lower reliability requirements than in FTP
Adaptive streaming objectives:
Delivered quality
Congestion control
Support for adaptive coding
Addressing Continuous Media Issues : Addressing Continuous Media Issues Issues with the standard protocols:
UDP: no congestion or error control
TCP: AIMD behavior undesirable due to fluctuation in rate, and consequently delay, and intolerance to random loss
DCCP provides an excellent framework, recommends TFRC as one possible protocol, but allows for alternatives
TFRC is equation based, rate-equivalent to Reno, with smoother delivery suitable for streaming
SCTP enables multiple streams with different congestion control mechanisms, among other features
Streaming Over Wireless: Streaming Over Wireless Under random loss, Reno and its rate-equivalent TFRC, will both under-perform
Approaches, some with loss discrimination, have been proposed:
TFRC Wireless:
Combination of loss discrimination schemes,
Multi-TFRC
Multiple TFRC connections until link is congested
VTP
Rate estimation and loss discrimination
Performance Comparison: Performance Comparison Efficiency in presence of errors 5% error rate, single connection Rate adaptation 5% error rate, single connection with on/off CBR cross traffic
TCP over Multihop Wireless: TCP over Multihop Wireless Packet losses due to:
Contention due to hidden terminals
Varying channel quality
Route collapse
Buffer overflow ??
Solution approaches:
Neighborhood RED
Delayed ACK extension
Sizing the TCP window for contention reduction
Store & Forward at the Transport Layer: Store andamp; Forward at the Transport Layer Overlays/P2P tunneling through TCP connections
PEPs breaking ETE path into concatenated TCP connections, e.g. satellites
New(?) Requirements:
Buffer management and priority schemes for better ETE application protocol performance
TCP Receiver advertised window role
Related item: Prioritized TCP for QOS at the Transport layer (TCP-LP, TCPW-LP)
Summary: Summary Excellent progress by many approaches for scaling efficiency with pipe size
Focus on PCE techniques is promising, e.g. TCPW provides:
Scalable efficiency
Robustness to random loss
Tunable opportunistic friendliness
Streaming, multihop wireless, and forwarding at the Transport layer to receive attention and make good progress
Steady State Characteristics (TCPW RE): Steady State Characteristics (TCPW RE) For small loss rate, TCPW has much larger window
than NewReno. More scalable!
Fairness (TCPW RE): Fairness (TCPW RE) For small loss rate, TCPW is more fair than NewReno