Per-hop and end-to-end capacity estimationOutlineNetwork BandwidthBandwidth & layeringCapacityExampleHop and path capacityEstimation MethodologiesCapacity estimationPer Hop Capacity Estimation1. VPS methodologyExampleEffect of layer2 switchesEffect of layer2 switches (cond.)Does this error propagate?Other sources of error for VPS2. Delay variation methodsExampleEnd-to-End Capacity EstimationPacket pair dispersionEffects of probe sizeCross-traffic effectsExample of statistical analysisCharacteristics of packet pair estimatesEffect of cross-traffic size variationEffect of probe size variationPacket train dispersionPacket train dispersionEnd-to-end capacity estimation toolPer-hop and end-to-end capacity estimationFall 2003CS 8803: Network Measurement SeminarRavi S. PrasadOutline! Introduction! Definitions! Capacity estimation methodologies" Hop capacity! Variable packet size (VPS)" Effect of layer 2 switches! Delay variation methods" Path capacity! Packet pair dispersion" Effect of cross-traffic! Packet train dispersionNetwork Bandwidth! Bandwidth: Metric for data transfer rate! Important for many applications" File transfer" Multimedia streaming" Overlay network routing" Service level agreement (SLA) and its verificationBandwidth & layering! Link layer transmits at fixed data rate! All higher layers add overhead (header and/or trailer)! Different layers observe different data rate! For IP network" Bandwidth = IP layer data rateExamplePerceived data rate1000BApp1000/x1020BTransport1020/x1040BNetwork1040/xTransmission takes x sec1060BLink 1060/xCapacity! Maximum IP layer data rate! Packet size dependence due to Layer2 encapsulation+=23323LLLLLHLLCC!HL2= Layer 2 header!LL3= Layer 3 (IP) data size! Capacity = data rate for MTU packetsExample! Ethernet overhead 38B! PPP overhead 8B(default)Hop and path capacity! Hop capacity " Maximum possible bandwidth! Path capacity" Minimum of hop capacities" Narrow link: hop with minimum capacity()hopiHipathCC,...,1min==Estimation MethodologiesCapacity estimation! Per-hop capacity" Variable Packet Size (VPS)! Pathchar, clink, pchar, tailgater" Delay Variations! Packet quartet methods! End-to-end capacity" Packet Pair Dispersion! Pathrate, Sprobe, Bprobe" Packet Train DispersionPer Hop Capacity Estimation1. VPS methodology! Obtain RTT up to Ithhop for different size (L) packets (using ICMP response or tailgating)! Components of RTT" Propagation delay (constant)" Queuing delay" Serialization delay (L/C) ! Assume:" Minimum RTT (TI) for a packet size didn’t see queuing.∑==+=IiiIIICLLT11)(ββαExample1221111βββ−==CCEffect of layer2 switches! Increase serialization delayEffect of layer2 switches (cond.)! Increase serialization delay! Capacity underestimation! Can’t be detected with TTL expiration222111LLCC+=β),min(112221LLCCC =<βDoes this error propagate?! If no layer2 switches in Ithhop" Path up to (I-1)th hop may have switches! Estimated capacity for Ithhop" Localized error131−+=ILIICββ311LIIIC=−−ββOther sources of error for VPS! Non-zero queuing delays! Limited clock resolution! Error propagation/amplification! ICMP generation latencies2. Delay variation methods! Pasztor and Veitch (IWQoS `02)! Use difference of one-way delay of consecutive probes! Instead of VPS like regression! More than one useful probe per size! Delay variation after h hops∑∑=−=−−+−=hjjijihjjijihiqqCLCL1111)(δ•qij Queuing delay for ithpacket at jthhopExampleEnd-to-End Capacity EstimationPacket pair dispersion! Relate dispersion of two back-to-back packets to path capacity! Empty link! Empty path∆=∆iinoutCL,maxCLCLiHiR==∆= ,...,1maxEffects of probe size! Small probes" Incorrect estimate! Higher layer-2 header" Small dispersion value! Require high resolution clock! Large probes" Higher probability of cross-traffic interferenceCross-traffic effects! Before the narrow link" Can increase dispersion! After the narrow link" Can increase or decrease dispersion! Large error possible in any estimate! Correct estimation requires statistical analysisExample of statistical analysis! Dispersion with highest frequency gives capacity" Fails when probe size and cross-traffic size constant" Internet traffic is mostly 40, 512,1500B packets " Have different size packet pairsxxxCharacteristics of packet pair estimates ! Multi-modal estimates! Local modes" Peaks in pdf of bandwidth estimates" Formed by repetitive measurement" Potential candidates for capacity! Three zones of local modes" Capacity mode(CM)! Captures path capacity" Post Narrow Capacity Mode (PNCM) ! Captures capacity after narrow link" Sub-Capacity Dispersion Range(SCDR)! Increased dispersion due to cross-trafficEffect of cross-traffic size variationEffect of probe size variationPacket train dispersion! Extension of packet pair! Send N packets back-to-back! Dispersion rate D(N)NNLND∆−=)1()(! In absence of cross-traffic " D(N) = C (Capacity)Packet train dispersion! cprobe assumes" D(N)=Available bandwidth (A)! Dovrolis et. al. (Infocom 2001)" D(N)≠A" D(N)=Average Dispersion Rate (ADR)! If N is large enough" ADR = f(hop capacities, hop utilizations)" C ≥ ADR ≥ AExamplecccccRCADECRCELNDECLNXRXCLN−=≠+=∆−=−+=∆∆=−=∆101212101)(1)()1()()1()1(C1C0RcCross-trafficPacket train∆2∆1Xc•For large N, ∆1is large•Variation in Xcis small•D(N) = E(D)End-to-end capacity estimation tool! Pathrate " 1000 packet pair estimation with different size probe (600B-1500B)! Obtain multi-modal estimate distribution" 500 packet train estimation with maximum size probes! Obtain ADR" Use ADR as lower bound on possible capacity modes! Capacity mode: strongest local mode higher than ADRThank