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