inside the island, however, the packet labels are no longer on receiving packet p an accurate estimate of its rate, We cannot. rerun our es e ro classify(p) timation algorithm, because it involves per-flow state, For p Label estimate -rate(ri, P); / use Eq()*/ tunately, as note inl Section 2. 1 the oulguinIg rale: is Inertly he minimum bet ween the incoming rate and the fair rate prob=max(0, 1-a/p label) if rand(0, 1) a, Therefore, we rewrite thethe packet label L as r =estimate_ar (p, 1) Lnet= min( Lold, a), By doing so, the outgoing Row rates will be properly repre- rr =estimatec(p, 0 sented by the packet labels if(prob>0) 2.3 Weighted CSFQ p label a;/* relabel p* The CSFQ algorithm can be extended to support Flows with different weights, Let w; denote the weight of flow i. Re estinate_a(p, dropped) turning to our fluid model, the meaning of these weight estimate rate( A, p);/* est. arrival rate(use Eq. (5))+/ that we say a fair allocation is one in which all bottle- FALSE cked flows have the same value for i. Then, if A(t)>C. estimate- rate(F, p);/* est. accepted traffic rate * the normalized fair rate a(t)is the unique value such that 2i, wr min(a, Ui )=C. The expression for the drop- if(congested== FALSE) congested= TRUE ping probabilities in the weighted case is max(0, 1-a w) start_time=crt_time Tle unly other major change is that the label is now r:/ else instead simply ri. Finally, without going into details we if(crt timc> start-time +Kc) note that the weighted packet-by-packet version is virtual a=a×C/F; identical to the corresponding version of the plain CSF( t tame= crtt algorithm It is inportant wo nule that with weighted CSFQ we can else/*A<C+ only approximate islands in which each flow has the same if(congested = TRUE weight at all routers in an island. That is, our algorithm congested= FALSE cannot accommodate situations where the relative weight: tart_time = crt_time. of flows differ from router to router within an island. How tmpa=0;/+ use to compute nca a+/ ever, even with this limitation, weighted CSFQ may prove else if(crt_time start-time +Kc) a valuable mechanism in implementing differential services, such as the one proposed in [24] tmp-ax =max(tmp_a, p label) a= trrp_a: 2.4 Performance bounds start time crt time: We now present the main theoretical result of the paper tmp_o =0 For generality, this result is given for weighted CSFQ. The return ar proof is given in [22] Our algorithm is built, around several estimation proce- dures, and thus is inherently inexact, One natural concern Figure 2: The pseudocode of CSFQ is whether a How can purposely exploit"these inaccuracies o get. more than its fair share of bandwidth. We answer this question in full generality, but we can analyze a time the buffer overflows, a is decreased by a small fixed per- simplified situation where the normalized fair share rate or entage(taken to be 1% in our simulations). Moreover, is held fixed and there is no buffering, so the drop probabil- avoid overcorrection, we make by e updates a does not decrease by more than 25% that. when a packet arrives a fraction of that packet equal to In addition, since there is little reason to consider a link the fows forwarding probability is transmitted. Note that congested if the buffer is almost empty, we apply the fol during any time interval [t1, t2)a How with weight w is enti- lowing rule. If the link becomes uncongested by the test tled to receive at most wa(t2-t1)service time; we call al Figure 2, then we assume that it remains ingested amount above this the excess service. We can bound this ng as the buffer occupancy is less than some predefined ess service, and the bounds are independent of both the threshold. In this paper we use a threshold that is half of arrival process and the length of the time interval during he total buffer capacity which the flow is active. The bound does depend crucially on the maximal rate R at which a flows packets can arrive 2.2.3 Label Rewriting at a router(limited, for example, by the speed of the flows access link); the smaller this rate R the tighter the bound Our rate estimation al in Section 2.2.1 label packets with their flows rate as they ent land Theorem 1 Consider a link with a constant normalized fa Our packet dropping algorithm described in tc a, and a fow with weight w. Then, the ercess service allows us to limit Rows to their fair share of the bandwidth. received by a flow with weight w, that sends at a rate no After a flow experiences significant losses at a congested link larger than R is bounded above b 121on receiving packet, p if (edge router) 2 =classify(p); p,label = estimate-rate(r,,p); /* ~dse Ep. (3) */ prob =max(O, 1 - a/p.label); if @rob >unifrand(O, 1)) 0 =estimate-cY (p, 1); drop(p); else 0 =estimate-rw (p, 0); tmqueue(p); if (prob > 0) p.label = cy; /+ relabel p */ estimate-u (p, dropped) estimate-rate(X,p); /* est. arrival rate (use Eq. (5)) */ if (dropped == Fz4-LSE) estimate-rate(F,p); /* est. accepted trafic rate */ if(A^>C) if (congested == FALSE) congested = TRUE; start-time = crt-time; else if (crt-time > start-time + Ii,) 6 = 2 x c/F; start-ti’me = crt-time; else /* 2 < C */ if (congested == TRUE) congested = FALSE; start-time = crt-time; tmp-cy = 0; /* use to compute new cy */ else if (crt-time < start-time + KC) tmp-cu =max(tmp-cu,l,.label); else Cu = tmp-ff ; start-time = crt-time; tmp-rw = 0; return G;; Figure 2: The pseudocode of CSFQ. time the bufl’er overflows, ;u^ is decreased by a small fixed per￾centage (taken to be 1% in our simulations). Moreover, to avoid overcorrection, we make sure that during consecutive updates su^ does not decrease by more than 25%. In addition, since there is little reason to consider a link congested if the buffer is almost empty, we apply the fol￾lowing rule. If the link becomes uncongested by the test in Figure 2, then we assume that it remains uncongested as long as the buffer occupancy is less than some predefined threshold. In this paper we use a threshold t,hat is half of the I,otal bufl’er capacity. 2.2.3 Label Rewriting Our rate estimation algorithm in Section 2.2.1 allows us to label packets with their flow’s rate as they enter the island. Our packet dropping algorithm described in Section 2.2.2 allows us to limit flows to their fair share of the bandwidth. After a flow experiences significant losses at a congested link inside the island, however, the packet labels are no 1o11gr1 an accurate estimate of its rate. We cannot rcr,m our es￾timation algorithm, because it involves per-flow state. IJor.- tunately, as note in Section 2.1 the outgoing rat,<! is merely the minimum between the incoming rate and the fair ra(,e N. Therefore, we rewrite the the packet, label I, as L new - min(Ldd, a), (7) By doing so, the outgoing flow rates will be properly reprc￾sented by the packet labels. 2.3 Weighted CSFQ 7’1~ CSFQ algorithm can be ext,ended to support, Hews with diH’erent weights. Let w, denote the weight of flow I. Re￾turning to our Huitl model, the meaning of t,hese weights is that we say a fair allocat,ion is one in which all bottle￾necked Hows have the same value for 2. l’hen, if A(t) > C, the normalized fair rate a(t) is the unique value such that CL w, min (0, 2) = C. The expression for the drop￾ping probabilities in the weighted case is max (0, I - (Y?). The only other major change is that the label is now rlj$L, instead simply rz. Finally, without going into details we note that the weighted packet-by-packet version is virtually identical to the corresponding version of the plain CSFQ algorithm. It is import,ant to note that with weighted CSFQ we can only approximate islands in which each How has t,he same weight at all routers in an island. That is, our algorithm cannot accommodate situations where the relative weights of Hows differ from router to router within an island. How￾ever, even with this limitation, weighted CSFQ may prove a valuable mechanism in implementing differential services, such as the one proposed in [24] 2.4 Performance Bounds We now present the main theoretical result of the paper. For generality, this result is given for weighted CSFQ. The proof is given in [22]. Our algorithm is built around several estimat,ion proce￾dures, and thus is inherently inexact. One natural concern is whether a flow can purposely “exploit” these inaccuracies to get more than its fair share of bandwidth. We cannot answer this question in full generality, but we can analyze a simplified situation where the normalized fair share rate N is held fixed and there is no buffering, so the drop probabil￾ities are precisely given by Eq. (2). In addition, we assume that when a packet arrives a fraction of that, packet equal to the flow’s forwarding probability is transmitted. Note that during any time interval [tl, t2) a flow with weight w is enti￾tled to receive at most, zua(tz - tl) service time; we call any amount above this the excess service. We can bound this excess service, and the bounds are independent of both the arrival process and the length of the time interval during which the How is active. The bound does depend crucially on the maximal rat,e R at which a Hows packets can arrive at, a router (limited, for example, by the speed of the flow’s access link); the smaller this rate R the tighter the bound. Theorem 1 Consider a link with a constant normalizedfair rute CY, and a flow with weight u). Then, the e.rcess seruzce received by a flow ,witla weight w, that sends at a ratr, no lurger than R is bounded above by 121