Raj JainThe Ohio State University197-1085: A Switch97-1085: A SwitchAlgorithm for ABRAlgorithm for ABRMultipointMultipoint-to-Point-to-PointConnectionsConnectionsSonia Fahmy, Raj Jain, Rohit Goyal,and Bobby VandaloreDepartment of CIS, The Ohio State UniversityContact: [email protected]://www.cis.ohio-state.edu/~jain/Raj JainThe Ohio State University2OverviewOverviewq Multipoint-to-point VCsq VC Mergingq Rate Allocation Algorithmq Merging Point Algorithmq Design Issuesq Simulation ResultsRaj JainThe Ohio State University3RootLeaf 1Leaf 2Merge PointMultipointMultipoint-to-Point -to-Point VCsVCsq More than one concurrent senderq Traffic at root= Σ traffic originating from leavesq Source-based fairness:N-to-one connection = N one-to-one connections⇒ max-min fairness among sourcesRaj JainThe Ohio State University4RootLeaf 1Leaf 2Merge Point100100100100VC MergingVC Mergingq Buffer cells at merging point tillEOM bit = 1q Cells of senders in the same multipoint-to-point VCcannot be distinguishedq Question: Can we achieve source-based fairness?Raj JainThe Ohio State University5ERICA+ERICA+q Time is slotted into averaging intervalsq ABR capacity = [link capacity− (VBR + CBR load)] × f(queue length)q Estimate input rate = Σ CCRjq overload = input rate/ABR capacityq ERj_efficiency = CCRj/overloadq ER_fairshare = ABR capacity/# of active sourcesq IF overload ≤ 1+ δ THEN ERj = max (ERj_efficiency, ER_fairshare, maxERprevious) ELSE ERj = max(ERj_efficiency, ER_fairshare)q maxERcurrent = max(maxERcurrent, ERj)q ER in BRMj = min(ER in BRMj, ERj)Raj JainThe Ohio State University6Changes to ERICA+Changes to ERICA+q Remove fair share term (# active sources)q Use CCRjmax instead of CCRjMaximum is calculated in successive intervalsq To minimize oscillations, use exponential averagingoptions for:m Input ratem ABR capacitym maxERpreviousRaj JainThe Ohio State University7Rate AllocationRate AllocationAlgorithmAlgorithm1. FRM cell is received for VC j:CCRj = CCR from FRMOR:IF FirstFRMj THENCCRj = CCR from FRMFirstFRMj = FALSEELSECCRj = max (CCR from FRM, CCRj)Raj JainThe Ohio State University8Algorithm (Cont.)Algorithm (Cont.)2. BRM cell to be sent out for VC j:IF overload > 1+δ THENER = CCRj/overloadELSEER = max (CCRj/overload, maxERprevious)ER = min (capacity, ER)maxERcurrent = max (ER, maxERcurrent)ER in BRM = min (ER, ER in BRM)[note: δ = 0.1 in our simulations]Raj JainThe Ohio State University9Algorithm (Cont.)Algorithm (Cont.)3. End of averaging interval:input rate = exponential averagecapacity = exponential average scaled by queue functionoverload = input rate/capacity∀j: FirstFRMj = TRUEmaxERprevious = maxERcurrentOR: maxERprevious = (1-α) × maxERcurrent + α ×maxERpreviousmaxERcurrent = 0[note: α = 0.1 in our simulations]Raj JainThe Ohio State University10= FRM= data = BRMRootLeaf 1Leaf 2Merge PointMerging Point AlgorithmMerging Point Algorithmq Maintain a bit at the merging point foreach flow being mergedBit = 1⇒ FRM received from this flow after BRM sent to itq BRMs are duplicated and sent to flows whose bits areset, then bits are resetRaj JainThe Ohio State University11Design IssuesDesign Issuesq Per-source accounting is avoidedq Using CCR from BRM cells can causeunfairness because CCR in BRM may belong to a sourcewith a higher bottleneck rate than all upstream sourcesq CCR from FRM cells is adequate because ofmaxERprevious term and properties of merging pointq BRM to FRM ratio at sender and inside the network isclose to 1q Destinations (not merging points) turn around BRMs forscalability, insensitivity to levels of tree and to avoidnoiseRaj JainThe Ohio State University12Simulation ParametersSimulation Parametersq Unidirectional trafficq RIF = 1/32, 1q Rule 6 disabledq Queue control: a = 1.15, b = 1, drain limit = 50%,target queuing delay = 1.5 sq Measurement interval = 5 ms, 200 µsq One cell long packets (Avoids VC merging issues)q Max CCR and averaging maxERprevious usedq Link lengths in kms: {LINK1, LINK2, LINK3} ={50, 500, 5000}, {5000, 500, 50}Raj JainThe Ohio State University13S1Sw1Sw4dS1dSASw3S3SASw2S2LINK1LINK2LINK3All links are 150 MbpsDownstream BottleneckDownstream Bottleneckq Goal:{S1,S2,S3,SA}←{37.5,37.5,37.5,37.5}q ICRs:{S1,S2,S3,SA}←{25,25,25,25},{100,100,100,100},{65,10,65,10}q Result: All sources are allocated 37.5 Mbps, smallqueues, LINK3 100% utilized, cells received atdSA:dS1 ≈ 175k:520k ≈ 1:3Raj JainThe Ohio State University14S1Sw1Sw4dS1dSASw3S4SASw2S3LINK1LINK2LINK3All links are 150 Mbps, except LINK1 which is 50 MbpsS2Upstream BottleneckUpstream Bottleneckq Goal:{S1,S2,S3,S4,SA}←{16.7,16.7,58.3,58.3,16.7}q ICRs:{S1,S2,S3,S4,SA}←{20,20,30,80,10}q Results are similar with different link lengths,RIF = 1/32, 1, interval length = 5 ms, 200 µs (no RMsfor S1,S2 ,SA for 4 intervals; for S3,S4 for 1 interval)Raj JainThe Ohio State University15WAN 4-leaf with upstream bottleneck: ACRs0204060801001201401601800200 400 600 800 1000 1200 1400 1600 1800 2000ACRsTime in milliseconds ACR for S1 ACR for S2 ACR for S3 ACR for S4 ACR for SA Simulation ResultsSimulation Resultsq Upstream Bottleneck, LINK3 = 5000 km, RIF = 1, interval = 5 msRaj JainThe Ohio State University16Queue LengthsQueue LengthsWAN 4-leaf with upstream bottleneck0200400600800100012000 200 400 600 800 100012001400160018002000Queue LengthsTime in milliseconds Queue Length for Switch 1 Queue Length for Switch 2 Queue Length for Switch 3Raj JainThe Ohio State University17Link UtilizationLink UtilizationRaj JainThe Ohio State University1801000002000003000004000005000006000007000008000000 200 400 600 800 1000 1200 1400 1600 1800 2000Cells ReceivedTime in millisecondsWAN 4-leaf with upstream bottleneck Cells Received at dS1 Cells Received at dSA dSA:dS1 ≈ 80k:700k≈ 16.67:133.09Cells ReceivedCells ReceivedRaj JainThe Ohio State University19Lessons LearntLessons Learntq Avoid determining the effective numberof active sourcesq Avoid estimation of rates of sources, ordetermining if a source is bottlenecked at this linkq Use only aggregate measurementsq Do not use CCR values from BRM cellsq CCR from FRM cells can be usedq Using the maximum CCR in an interval, andexponentially averaging the maximum ER in theprevious interval can improve performanceq Do not turn around RM cells at merging pointRaj JainThe Ohio State University20SummarySummaryq Multipoint-to-point ABR congestion controlalgorithms need to avoid problems that can arise in anaïve extension of point-to-point