breaking the data transfer bottleneck：打破了数据传输的瓶颈

1 : 50,BREAKING THE DATA TRANSFER BOTTLENECK,Yunhong GUNational Center for Data MiningUniversity of Illinois at ChicagoOctober 10, 2005Updated on August 8, 2009,,UDT: A High Performance Data Transport Protocol,2 : 50,Outline,INTRODUCTION,PROTOCOL DESIGN & IMPLEMENTATION,CONGESTION CONTROL,PERFORMANCE EVALUATION,COMPOSABLE UDT,CONCLUSIONS,3 : 50, INTRODUCTION,PROTOCOL DESIGN & IMPLEMENTATION,CONGESTION CONTROL,PERFORMANCE EVALUATION,COMPOSABLE UDT,CONCLUSIONS,4 : 50,Motivations,The widespread use of high-speed networks (1Gb/s, 10Gb/s, etc.) has enabled many new distributed data intensive applicationsInexpensive fibers and advanced optical networking technologies (e.g., DWDM - Dense Wavelength Division Multiplexing)10Gb/s is common in high speed network testbeds, 40 Gb/s is emergingLarge volumetric datasetsSatellite weather dataAstronomy observationNetwork monitoringThe Internet transport protocol (TCP) does NOT scale well as network bandwidth-delay product (BDP) increasesNew transport protocol is needed!,5 : 50,Data Transport Protocol,FunctionalitiesStreaming, messagingReliabilityTimelinessUnicast vs. multicastCongestion controlEfficiencyFairnessConvergenceDistributedness,Physical Layer,Applications,Data link Layer,Network Layer,Transport Layer,6 : 50,TCP,Reliable, data streaming, unicastCongestion controlIncrease congestion window size (cwnd) one full sized packet per RTTHalve the cwnd per loss event,Poor efficiency in high bandwidth-delay product networksBias on flows with larger RTT,7 : 50,TCP,Throughput (Mb/s),Throughput (Mb/s),Packet Loss,Round Trip Time (ms),8 : 50,Related Work,TCP variantsHighSpeed, Scalable, BiC, FAST, H-TCP, L-TCPParallel TCPPSockets, GridFTPRate-based reliable UDPRBUDP, Tsunami, FOBS, FRTP (based on SABUL), Hurricane (based on UDT)XCPSABUL,9 : 50,Problems of Existing Work,Hard to deployTCP variants and XCPNeed modifications in OS kernel and/or routersCannot be used in shared networksMost reliable UDP-based protocolsPoor fairnessIntra-protocol fairnessRTT fairnessManual parameter tuning,10 : 50,A New Protocol,Throughput (Mb/s),Throughput (Mb/s),Packet Loss,Round Trip Time (ms),11 : 50,UDT (UDP-based Data Transfer Protocol),Application level, UDP-basedSimilar functionalities to TCPConnection-oriented reliable duplex unicast data streamingNew protocol design and implementationNew congestion control algorithmConfigurable congestion control framework,12 : 50,Objective & Non-objective,ObjectiveFor distributed data intensive applications in high speed networksA small number of flows share the abundant bandwidthEfficient, fair, and friendlyConfigurableEasily deployable and usableNon-objectiveReplace TCP on the Internet,13 : 50,UDT Project,Open source ()Design and implement the UDT protocolDesign the UDT congestion control algorithmEvaluate experimentally the performance of UDTDesign and implement a configurable protocol framework based on UDT (Composable UDT),14 : 50, PROTOCOL DESIGN & IMPLEMENTATION,INTRODUCTION,CONGESTION CONTROL,PERFORMANCE EVALUATION,COMPOSABLE UDT,CONCLUSIONS,15 : 50,UDT Overview,Two orthogonal elementsThe UDT protocolThe UDT congestion control algorithmProtocol design & implementationFunctionalityEfficiencyCongestion control algorithmEfficiency, fairness, friendliness, and stability,16 : 50,UDT Overview,17 : 50,Functionality,ReliabilityPacket-based sequencingAcknowledgment and loss report from receiverACK sub-sequencingRetransmission (based on loss report and timeout)Streaming and MessagingBuffer/memory managementConnection maintenanceHandshake, keep-alive message, teardown messageDuplexEach UDT instance contains both a sender and a receiver,18 : 50,Protocol Architecture,UDP Channel,Sender,19 : 50,Software Architecture,CC,20 : 50,Efficiency Consideration,Less packetsTimer-based acknowledgingLess CPU timeReduce per packet processing timeReduce memory copyReduce loss list processing timeLight ACK vs. regular ACKParallel processingThreading architectureLess burst in processingEvenly distribute the processing time,21 : 50,Application Programming Interface (API),Socket APINew APIsendfile/recvfile: efficient file transfersendmsg/recvmsg: messaging with partial reliabilityselectEx: a more efficient version of “select”Rendezvous ConnectFirewall traversing,22 : 50, CONGESTION CONTROL,INTRODUCTION,PROTOCOL DESIGN & IMPLEMENTATION,PERFORMANCE EVALUATION,COMPOSABLE UDT,CONCLUSIONS,23 : 50,Overview,Congestion control vs. flow controlCongestion control: effectively utilize the network bandwidthFlow control: prevent the receiver from being overwhelmed by incoming packetsWindow-based vs. rate-basedWindow-based: tune the maximum number of on-flight packets (TCP)Rate-based: tune the inter-packet sending time (UDT)AIMD: additive increases multiplicative decreasesFeedbackPacket loss (Most TCP variants, UDT)Delay (Vegas, FAST),24 : 50,AIMD with Decreasing Increases,AIMDx = x + (x), for every constant interval (e.g., RTT)x = (1 - ) x, when there is a packet loss eventwhere x is the packet sending rate.TCP(x) 1, and the increase interval is RTT. = 0.5AIMD with Decreasing Increase(x) is non-increasing, and limx-+ (x) = 0.,25 : 50,AIMD with Decreasing Increases,26 : 50,Increase(x) = f( B - x ) * c where B is the link capacity (Bandwidth), c is a constant parameterConstant rate control interval (SYN), irrelevant to RTTSYN = 0.01 secondsDecreaseRandomized decrease factor = 1 (8/9)n,UDT Control Algorithm,27 : 50,The Increase Formula: an Example,Bandwidth (B) = 10 Gbps, Packet size = 1500 bytes,28 : 50,Dealing with Packet Loss,Loss synchronizationRandomization method,Non-congestion lossDo not decrease sending rate for the first packet loss,Packet reordering,29 : 50,Bandwidth Estimation,Packet Pair,FiltersCross trafficInterrupt CoalescenceRobust to estimation errorsRandomized interval to send packet pair,P2,P1,Packet Size / Space Bottleneck Bandwidth,30 : 50, PERFORMANCE EVALUATION,INTRODUCTION,PROTOCOL DESIGN & IMPLEMENTATION,CONGESTION CONTROL,COMPOSABLE UDT,CONCLUSIONS,31 : 50,Performance Characteristics,EfficiencyHigher bandwidth utilization, less CPU usageIntra-protocol fairnessMax-min fairnessJains fairness indexTCP friendlinessBulk TCP flow vs Bulk UDT flowShort-lived TCP flow (slow start phase) vs Bulk UDT flowStability (oscillations)Stability index (standard deviation),32 : 50,Evaluation Strategies,Simulations vs. experimentsNS2 network simulator, NCDM teraflow testbedSetupNetwork topology, bandwidth, distance, queuing, Link error rate, etc.Concurrency (number of parallel flows)Comparison (against TCP)Real world applicationsSDSS data transfer, high performance mining of streaming data, etc.Independent evaluationSLAC, JGN2, UvA, Unipmn (Italy), etc.,33 : 50,Efficiency, Fairness, & Stability,34 : 50,Efficiency, Fairness, & Stability,35 : 50,TCP Friendliness,500 1MB TCP flows vs. 0 10 bulk UDT flows1Gb/s between Chicago and Amsterdam,36 : 50, COMPOSABLE UDT,INTRODUCTION,PROTOCOL DESIGN & IMPLEMENTATION,CONGESTION CONTROL,PERFORMANCE EVALUATION,CONCLUSIONS,37 : 50,Composable UDT - Objectives,Easy implementation and deployment of new control algorithmsEasy evaluation of new control algorithmsApplication awareness support and dynamic configuration,38 : 50,Composable UDT - Methodologies,Packet sending controlWindow-based, rate-based, and hybridControl event handlingonACK, onLoss, onTimeout, onPktSent, onPktRecved, etc.Protocol parameters accessRTT, loss rate, RTO, etc.Packet extensionUser-defined control packets,39 : 50,Composable UDT - Evaluation,SimplicityCan it be easily used?ExpressivenessCan it be used to implement most control protocols?SimilarityCan Composable UDT based implementations reproduce the performance of their native implementations?OverheadWill the overhead added by Composable UDT be too large?,40 : 50,Simplicity & Expressiveness,Eight event handlers, four protocol control functions, and one performance monitoring function.Support a large variety of protocolsReliable UDT blastTCP and its variants (both loss and delay based)Group transport protocols,41 : 50,Simplicity & Expressiveness,CCCBase Congestion Control Class,42 : 50,Similarity and Overhead,SimilarityHow Composable UDT based implementations can simulate their native implementationsCTCP vs. Linux TCP,CPU usageSender: CTCP uses about 100% more times of CPU as Linux TCPReceiver: CTCP uses about 20% more CPU than Linux TCP,43 : 50, CONCLUSIONS,INTRODUCTION,PROTOCOL DESIGN & IMPLEMENTATION,CONGESTION CONTROL,PERFORMANCE EVALUATION,COMPOSABLE UDT,44 : 50,Contributions,A high performance data transport protocol and associated implementationThe UDT protocolOpen source UDT library ()User includes research institutes and industriesAn efficient and fair congestion control algorithmDAIMD & the UDT control algorithmPacket loss handling techniquesUsing bandwidth estimation technique in congestion controlA configurable transport protocol frameworkComposable UDT,45 : 50,Selected Publications,Papers on the UDT ProtocolUDT: UDP-based Data Transfer for High-Speed Wide Area Networks, Yunhong Gu and Robert L. Grossman, Computer Networks (Elsevier). Volume 51, Issue 7. May 2007. Supporting Configurable Congestion Control in Data Transport Services, Yunhong Gu and Robert L. Grossman, SC 2005, Nov 12 - 18, Seattle, WA.Experiences in Design and Implementation of a High Performance Transport Protocol, Yunhong Gu, Xinwei Hong, and Robert L. Grossman, SC 2004, Nov 6 - 12, Pittsburgh, PA.An Analysis of AIMD Algorithms with Decreasing Increases, Yunhong Gu, Xinwei Hong and Robert L. Grossman, First Workshop on Networks for Grid Applications (Gridnets 2004), Oct. 29, San Jose, CA.Internet DraftUDT: A Transport Protocol for Data Intensive Applications, Yunhong Gu and Robert L. Grossman, draft-gg-udt-02.txt.,46 : 50,Commercia