Flow I Core Router Packet Labeling F(a()=∑min(r(),a(t) (4) Note that F() is a continuous, nondecreasing, concave, and Flaw i packe labeling piecewise-linear function of a. If the link is congested(A(:)> C) we choose a(t)to be the unique solution to F(r)= If the link is not congested (A(t)<C)we take a(t) to be the largest rate among the flows that traverse the link,i,e Estimator c(l)=naxK<i<n(ri(c)). Fron Ey (4)note that if we knew the arrival rates ri(t) we could then compute a(t)directly To avoid having to keep such per-flow state, we seek instead to implicitly compute a(t) by using only aggregate mea ments of F and a Figure I: The architecture of the output port of an edge We use the following heuristic algorithm with thre router, and a core router, respectively. gregate state variables: a, the estimate for the fair share rate;A, the estimated aggregate arrival rate; F, the esti We still employ a drop-on-input. scheme, except that now mated rate of the accepted traffic. The last two variables we drop packets rather than bits. Because the ti- are updated upon the arrival of each packet. For A we use lalion(described below) incorporates the packet size, the exponential averaging with a parameter e-T/Ka where Tis the inter-arrival time between the current and the previous depends only, as above, on the rate r: (t)and fair share rate packet we are left with two remaining challenges: estimating Anew=(1 (5 the rates ri(t)and the fair share a(t). We address these two the rewriting of the labels. Pseudocode reflecting this algo- an analogous formula to update Ae the updating. We use where Aold is the value of a befo rithm is described in Figure 2. We should note, however The updating rule for a depends on whether the link is hat the main point of our paper is the overall architecture congested or not. 'lo hilter out the estimation inaccuracies and that the detailed algorithm presented below represents due to exponential smoothi only an init ial prot. ntype While it serves adequately as a A link is assumed to be congested, if A>C at all times dui proof-of-concept of our architecture, we fully expect that the ing an interval of length Kc. Conversely, a link is assumed details of this design will continue to evolve to be uncongested, if A< C at all times during an interval 2.2.1 Computation of Flow Arrival Rate interval in which the link is either congested or uncongested Recall that in our architecture, the rates ri(t) are estimated according to these definitions. If the link is congested then at the edge routers and then these rates are inserted int a is updated based on the equation F (ar)=C. We approxi- reaging to estimate the rate of a fow. Let tk and 4k be has slope F/aold. This yields the arrival time and length of the k packet of flow i. The estimated rate of Hlow i, ri, is updated every time a new aold )/ (3) If the link is not congested, aneto is set to the largest rate of any active fow(i. e, the largest label seen)during the last Ks time units. The value of anew is then used to com where tk=tt-tk-I and k is a constant. We discuss pute dropping probabilities, according to Eq(2). For com the rationale for using the form e-Ti/k for the exponential weight in Section 2.7. In the longer version of this paper We now describe two minor amendments to this algo- 22] we show that, under a wide range of conditions, this rith related to how the buffers are managed. The goal of estimation algorithm converges estimating the fair share a is to match the accepted rate to the link bandwidth. Due to estimation inaccuracies, load 2.2.2 Link Fair Rate Estimation fluctuations between ars updates, and the probabilistic na In this section, we present an estimation algorithm for a(t). exceed the link capacity. While ideally the router's buffers tion 2. 1 where the arrival rates are known exactly, and as- can accor lack of sume the system performs the tIc ping alg rithm according to Eq(2). Then, the rate with which the ffer space. Since drop-tail behavior will defeat the purp n. a rrent estl- ase of adaptive flows sucll as TCP mate of the fair share rate, which we denote by a(t). Letting to limit its effect. To do so, we use a simple heuristic: every F(a(t))denote this acceptance rate, we haveE:dge Router I Estimator Figure 1: The architecture of the output port of an edge rout,er, and a core router, respectively. We still employ a drop-on-input scheme, except that now we drop packets rather than bits. Because the rate esti￾mation (described below) incorporates the packet size, the dropping probability is independent of the packet size and depends only, as above, on the rate r;(t) and fair share rate u(t). We are left with two remaining challenges: estimating the rates r,(t) and t,he fair share o(t). We address these two issues in turn in the next two subsections, and then discuss the rewriting of the labels. Pseudocode reflecting this algo￾rithm is described in Figure 2. We should note, however, that, the main point, of our paper is the overall architecture and that the detailed algorithm presented below represents only an init,ial prototype. While it serves adequately as a proof-of-concept of our architecture, we fully expect that the details of this design will continue to evolve. 2.2.1 Computation of Flow Arrival Rate Recall that in our architecture, the rates rt(t) are estimated at t,he edge routers and then these rates are inserted into the packet labels. At each edge router, we use exponential averaging to estimate the rate of a flow. Let tf and 1: be the arrival time and length of the lath packet of flow i. The estimated rate of flow i, T,, is updated every time a new packet is received: where T,k = tt - tr-’ and K is a constant. We discuss the rationale for using the form e-Tak/Ji for the exponential weight in Section 2.7. In the longer version of this paper [22] we show that, under a wide range of conditions, this estimation algorithm converges. 2.2.2 Link Fair Rate Estimation In this section, we present an estimation algorithm for o(t). To give intuition, consider again the fluid model in Sec￾tion 2. t where the arrival rates are known exactly, and as￾sumr the system performs the probabilistic dropping algo￾rithm according to Eq. (2). Then, the rate with which the algorithm accepts packets is a function of the current esti￾mate of the fair share rate, which we denote by 6(t). Letting .“‘(&(t)) denote this acceptance rate, we have F(qt)) = 2 min (rl(t), G(t)) r=, Note that F(.) is a continuous, nondecreasing, concave, and piecewise-linear function of cr. If the link is congested (A(t) > C) we choose G(t) to be the unique solution to F(s) = C. If the link is not congested (A(t) < C) we take G(t) to be the largest rate among the flows that traverse the link, i.e., G(t) = maxi<,<,(r,(t)). From Eq (4) note that if we knew -- the arrival rates rl(t) we could then compute o(t) directly. To avoid having to keep such per-flow state, we seek instead to implicitly compute G(t) by using only aggregate measure￾ments of F and A. We use the following heuristic algorithm with three ag￾gregate state variables: G, the estimate for the fair share rate; A, the estimated aggregate arrival rate; F, the esti￾mated rate of the accepted traffic. The last two variables are updated upon the arrival of each packet. For A we use exponential averaging with a parameter e -T/Xi, where T is the inter-arrival time between the current and the previous packet : where Aold is the value of A before the updating. We use an analogous formula to update F. The updating rule for ;i depends on whether the link is congested or not. To filter out the estimation inaccuracies due to exponential smoothing we use a window of size K,. A link is assumed to be congested, if A^ 2 C at all times dur￾ing an interval of length EC,. Conversely, a link is assumed to be uncongested, if A^ < C at all times during an interval of length I(,. The value% is updated only at the end of an interval in which the link is either congested or uncongested according to these definitions. If the link is congested then G is updated based on the equation F(G) = C. We approxi￾mate F(‘) by a linear function that intersects the origin and has slope p/Gold. This yields h c CYnezLi = QoldT F (6) If the link is not congested, (r,,, is set to the largest rate of any active flow (i.e., the largest label seen) during the last Ii’, time units. The value of ;u^,,,,, is then used to com￾pute dropping probabilities, according to Eq. (2). For com￾pleteness, we give the pseudocode of the CSFQ algorithm in Figure 2. We now describe two minor amendments to this algo￾rithm related to how the buffers are managed. The goal of estimating the fair share G is to match the accepted rate to the link bandwidth. Due to estimation inaccuracies, load fluctuations between G’s updates, and the probabilistic na￾ture of our algorithm, the accepted rate may occasionally exceed the link capacity. While ideally the router’s buffers can accommodate the extra packets, occasionally the router may be forced to drop the incoming packet, due to lack of buffer space. Since drop-tail behavior will defeat the purpose of our algorithm, and may exhibit undesirable properties in the case of adaptive flows such as TCP [9], it, is important to limit, its effect. To do so, we use a simple heuristic: every 120