2. 7 Miscellaneous Details Tak(1+in=)+Imax (8) Having presented the basic CS algorithm, we now return We have used exponential averaging to estimate the ar- where ra= aw, and lmar represents the marimum length of al rate in Eq.(3). However, instead of using a consta exponential weight we used e-T/k where T is the inter packet arrival time and K is a constant. Our motivation By bounding the excess service, we have shown that in was that e-T/k more closely refects a Auid averaging pro his idealized setting the asymptotic throughput cannot. ex- cess which is independent of the packetizing structure. More system over short time scales; they are limited to their fair specifically, it can be shown that if a constant weight. ls sed the estimated rate will be sensitive to the packet length dis- share over long time scales tribution and there are pathological cases where the esti- 2.5 Implementation Complexity this would allow flows to exploit the estimation process and At core routers, both the time and space conplexity of our btain more than their fair share. In contrast by using a algorithm are constant with respect to the number of com- parameter of e-T/, the estimated rate will asymptotical peting flows and thus we think CSFQ could be implemented converge to the real rate, and this allows us to bound the excess service that can be achieved (as in Theorem 1. We g needs to maintain per flow state. upoassify the packet l on each arrival of each used a similar averaging process in Eq.(5)to estimate the Hlow,(2)update the fair share rate estimation for the cor- The choice of K in the above expression e-T/k presents responding out going link, (3)update the flow rate estima us with several tradeoffs. First, while a smaller K increases tion,and (4)label the packet. All these operations with the system responsiveness to rapid rate fluctuations, a larger the exception of packet classification can be efficiently im K better filters the noise and avoids potential system insta plemented today. ility. Second, k should be large enough guch t hat the esti- Ffficient and general-purpose packet classification algo- mated rate, calculated at the edge of the net work, remains rithins are still under active research, We expect to lever reasonabl r a packet traverses multiple links results. We also note that packet classification his is because the delay- jitter changes the packets'inter is needed for a number of other purpose arrival pattern, which may result in an increased discrep- ontext of Multiprotocol Label Switching ancy between thc estimated ratc (rcccivcd in the packets ing purposes; therefore, the classi labels) and the real rate. To counteract this effect, as a rule fication required for CSFQ may not be an extra cost. In ad of thumb, I should be one order of magnitude larger that dition, if the edge routers are typically not on the high-speed he delay-jitter experienced by a flow over a time interval of backbone links then there is no problem as classification at he same size, K. Third, K should be no larger than the average duration of a flow. Based on this constraints,an appropriate value for K would be between 100 and 500 ms A second issue relates to the requirement of CSFQ for a 2. 6 Architectural Considerations label to be carried in each packet. One possibility is to use he Type Of Service byte in the IP header. For example, by This was intentional, as the CSFQ approach can be applied using a floating point representation with four bits for man tutcs a flow is arbitrary as long as all packets in the io between 1 Kbps and 65 Mbps with an accuracy of 6. 25% follow the same path within the core. In this paper, for co Another possibility is to define an IP option in the case of venience, a flow is implicitly defined as a source-destination IPv4, or a hop-by-hop extension header in the case of IPv6 pair, but one could easily assign fair rates to many other granularities such as source-destination-ports. Moreover 3 Simulation as the rates are re-estimated when entering a new island the unit of How"can vary from island to island as long In this section we evaluate our algorithm by simulation. To Similarly, we have not been precise about the size of these provide some context, we compare CSFQ's performance to CSQ islands. In one extreme, we could take each router four additional algorithms. Two of these, FIFO and RED, as an island and estimate rates at every router; this would represent baseline cases where routers do not attempt to allow us to avoid the use of complicated per-How achcdulin chieve fair bandwidth allocations. The other two alg and dropping algorithms, but would require per-flow classi thms, FRED and DRR, represent different approach fication. Another possibility is that ISP's could extend their island of CSFQ routers to the very edge of their net work having their edge routers at the points where customer's FIFo(First In First Out).Packets are served in a packets enter the ISP's nctwork. Building on the prey first-in first-out order, and the buffers are scenario, multiple ISP's could combine their islands so that using a simple drop-tail strategy; i. e, incoming pack at ISP-ISP boundaries. The key obstacle here is one of trust RED(Random Early Detection in a first-in first-out order, but manage- an drop-tail2.7 Miscellaneous Details Having presented the basic CSFQ algorithm, we now return to discuss a few aspects in more detail. We have used exponential averaging to estimate the ar￾rival rate in Eq. (3). However, instead of using a constant exponential weight we used e-‘/Ii where T is the inter￾packet arrival time and li is a constant. Our motivation was that e-Tt1’ more closely reflects a fluid averaging pro￾cess which is independent of the packetizing structure. More specifically, it can be shown that if a constant weight is used, the estimated rate will be sensitive to the packet length dis￾tribution and there are pathological cases where the esti￾mated rate differs from the real arrival rate by a factor; this would allow flows to exploit the estimation process and obtain more than their fair share. In contrast, by using a parameter of e-‘/Ii, the estimated rate will asymptotically converge to the real rate, and this allows us to bound the excess service that can be achieved (as in Theorem 1). We used a similar averaging process in Eq. (5) to estimate the total arrival rate A. The choice of li in the above expression e-‘r”i presents us with several tradeoffs. First, while a smaller Ei increases the system responsiveness to rapid rate fluctuations, a larger I( better filters the noise and avoids potential system insta￾bility. Second, I< should be large enough such that the esti￾mated rate, calculated at the edge of the network, remains reasonably accurate after a packet traverses multiple links. This is because the delay-jitter changes the packets’ inter￾arrival pattern, which may result in an increased discrep￾ancy between the estimated rate (received in the packets’ labels) and the real rate. To counteract this effect, as a rule of thumb, I< should be one order of magnitude larger that the delay-jitter experienced by a flow over a time interval of the same size, K. Third, I( should be no larger than the average duration of a flow. Based on this constraints, an appropriate value for li would be between 100 and 500 ms. A second issue relates to the requirement of CSFQ for a label to be carried in each packet. One possibility is to use the Type Of Service byte in the IP header. For example, by using a floating point representation with four bits for man￾tissa and four bits for exponent we can represents any rate between 1 Kbps and 65 Mbps with an accuracy of 6.25%. Another possibility is to define an IP option in the case of lPv4, or a hop-by-hop extension header in the case of IPv6. whew r a = ,IUJ, and l,,, represents the maximum length of a packet. By bounding the excess service, we have shown that. in this idealized setting the asymptotic throughput cannot ex￾ceed the fair share rate. Thus, flows can only exploit the system over short time scales; they are limited to their fair share over long time scales 2.5 Implementation Complexity At core routers, both the time and space complexity of our algorithm are constant with respect to the number of com￾pet,iiig flows. and thus we think CSFQ could be implemented in very high speed core rout,ers. At each edge router CSFQ needs to maintain per flow state. Upon each arrival of each packet, the edge router needs to (1) classify the packet to a flow, (2) update the fair share rate estimation for the cor￾responding outgoing link, (3) update the flow rate estima￾t,ion, and (4) label the packet. All these operations with the exception of packet classification can be efficiently im￾plemented today. E:fficient and general-purpose packet, classification algo￾rithins are still under act,ive research. We expect to lever￾age lhese results. W e a 1 so note that packet classification at irigress nodes is needed for a number of other purposes, such as in the context of Multiprotocol Label Switching (MPLS) [4] or for accounting purposes; therefore, the classi￾fication required for CSFQ may not be an extra cost. In ad￾dition, if the edge routers are typically not on the high-speed backbone links then there is no problem as classification at rnoderate speeds is quite practical. 2.6 Architectural Considerations We have used the term flow wit,hout defining what we mean. This was int,entional, as the CSFQ approach can be applied to varying degrees of flow granularity; that is, what consti￾tutes a flow is arbitrary as long as all packets in the flow follow the same path within the core. In this paper, for con￾venience, a flow is implicitly defined as a source-destination pair, but one could easily assign fair rates to many other granularities such as source-destination-ports. Moreover, the unit of Vlow” can vary from island to island as long as the rates are re-estimated when entering a new island. Similarly, we have not been precise about the size of these CSF’Q islands. In one extreme, we could take each router as an island and estimate rates at every router; this would allow us to avoid the use of complicated per-flow scheduling and dropping algorithms, but would require per-flow classi￾fication. Another possibility is that ISP’s could extend their island of CSFQ routers to the very edge of their network, having their edge routers at the points where customer’s packets enter the ISP’s network. Building on the previous scenario, multiple ISP’s could combine their islands so that classification and estimation did not have to be performed at ISP-ISI’ boundaries. The key obstacle here is one of trust between ISl’s. 3 Simulations In this section we evaluate our algorithm by simulation. To provide some context, we compare CSFQ’s performance to four additional algorithms. Two of these, FIFO and RED. represent baseline cases where routers do not attempt to achieve fair bandwidth allocations. The other two algo￾rithms, FRED and DRR, represent different approaches to achieving fairness. l FIFO (First In First Out) - Packets are served in a first-in first-out order, and the buffers are managed using a simple drop-tail strategy; i.e., incoming pack￾ets are dropped when the buffer is full. l RED (Random Early Detection) - Packets are served in a first-in first-out order, but the buffer manage￾ment is significantly more sophisticated than drop-tail. RED [9] starts to probabilistically drop packets long 122