What do packet dispersion techniques measure?Constantinos DovrolisParameswaran RamanathanDavid MooreUniversity of WisconsinUniversity of [email protected] [email protected] @caida.orgAbstract— The packet pair technique estimates the capacity of a path(bottleneck bandwidth) from the dispersion (spacing) experienced by twoback-to-back packets [1][2][3]. We demonstrate that the d~persion ofpacket pairs in Ioaded paths follows a multimodal d~tribution, and dis-cuss the queueing effects that cause the multiple modes. We show that thepath capacity is often not the global mode, and so it cannot be estimatedusing standard statistical procedures.The effectof the sizeof the probingpackets is atso investigated, showing that the conventional wisdom of usingmaximum sized packet pairs is not optimal. We then study the d~persionof long packet trains. Increasing the length of the packet train reduces themeasurement variance, but the estimates converge to a value, referred toas Asymptotic D~persion Rate (ADR), that is lower than the capacity. Wederive the effect of the cross traffic in the d~persion of long packet trains,showing that the ADR is not the av~llable bandwidth in the path, as wasassumed in previous work. Putting all the pieces together, we present a ca-pacity estimation methodology that has been implemented in a tool calledpathrate.Keywords—Active network measurements, baudwidth monitoring, bet.tleneck bandwidth, available bandwidth.I. INTRODUCTIONThe Internet is a commercial infrastructure in which users payfor their access to an Internet Service Provider (ISP), and fromthere to the global Internet. It is often the case that the perfor-mance level (and tariff) of these network connections is based on, their bandwidth, since more bandwidth normally means higherthroughput and better quality-of-service to an application. Insuch an environment, bandwidth monitoring becomes a crucialoperation. Users need to check whether they get the accessbandwidth that they have paid for, and whether the network‘clouds’ that they use are sufficiently provisioned. ISPS alsoneed bandwidth monitoring tools in order to plan their capacityupgrades, and to detect congested or underutilized links [4].Network operators are increasingly using tools such asMRTG[5] to monitor the utilization of their links with information ob-tained from the router management software. These techniquesare based on statistics maintained by the routers, and they arenormally very accurate. Their drawback, however, is that theycan be performed only with access to the router, and such anaccess is usually limited to the network manager. Instead, inthis paper we focus on an end-to-end bandwidth monitoring ap-proach that requires the cooperation of only the path end-points.Even though end-to-end approaches are usually not as accurateas router-based methodologies, they are often the only feasibleapproach for monitoring a path that crosses several networks.We define a network path as the sequence of links that forwardpackets from the path sender (source) to the receiver (sink)l.Two bandwidth metrics that are commonly associated with apath are the capaci~ C and the available bandwidth A. TheThis work was supported in part by the USENIX association and by theNational ScienceFoundation under Grant No. NCR-97 11092.1We assumethat the path is fixed and unique, i.e., no routing changesor mul-tipath forwarding occur during bandwidth monitoring.capacity is the maximum IP-layer throughput that the path canprovide to a flow, when there is no competing trajfic load (crosstraffic), The available bandwidth, on the other hand, is themaximum IP-layer throughput that the path can provide to ajiow, given the path’s current cross trafjic load. The link withthe minimum transmission rate determines the capacity of thepath, while the link with the minimum unused capacity limitsthe available bandwidth. To avoid the term bottleneck link, thathas been widely used for both metrics, we refer to the capacitylimiting link as the narrow link, and to the available bandwidthlimiting link as the tight link.Specifically, if H is the number of hops in a path, Ci is thetransmission rate or capacity of link i, and C’. is the transmissionrate of the source, then the path’s capacity is‘c =~=~,inH Ci(1)Additionally, if Ui is the utilization of link i (with O < ui ~ 1and UO=O), the unused capacity in link i is Ci (1 – ui), andsothe available bandwidth of the path isA =i&IH [G(l – w)](2)Note that the available bandwidth definition requires stationarytraffic and sufficiently large timescales so that the utilizationterms Ui to be practically constant. The capacity and availablebandwidth metrics are further discussed in the Appendix.The packet pair technique is a well-known procedure to mea-sure the capacity of a path. When a packet is transmitted ina link, it encounters a transmission or serialization delay dueto the physical bandwidth limitations of the link and the hard-ware constraints of the transmitting equipment. In a link of ca-pacity Ci and for a packet of size L, the transmission delay isri = L/Ci. A packet pair experiment consists of two packetssent back-to-back, i.e., with a spacing that is as short as possible,from the source to the sink. Without any cross traffic in the path,the packet pair will reach the receiver dispersed (spaced) by thetransmission delay in the narrow link T. s L/C. So, the re-ceiver can compute the capacity C from the measured dispersionA, as C = L/A. Figure 1 illustrates the packet pair technique inthe case of a three-link path, using the fluid analogy introducedin [6]. Even though simple in principle, this technique can pro-duce widely varied estimates and erroneous results. The mainreason is that the cross traffic in the path distorts the packet pairdispersion, increasing or decreasing the capacity estimates.The main objective in this paper is to develop a capacity es-timation methodology, based on end-to-end measurements, thatis robust to cross traffic effects. We show that a straightforwardapplication of the packet pair technique cannot, in general, pro-duce accurate results when the cross traffic effects are ignored.0-7803-7018-8/01/$10.00 (C) 2001 IEEE IEEE INFOCOM 2001L13CL/CA=LICeceiver@C,=3CC2=c C3=3CFig. 1. Graphical illustration of the packet pair technique. The width of eachlink correspondsto its capacity.The reason is that the distribution of bandwidth measurementsis multimodal, and some
View Full Document
Unlocking...