Bobby Vandalore, Sonia Fahmy, Raj Jain, Rohit Goyal, Mukul Goyal
The Ohio State University
Department of Computer and Information Science
2015 Neil Avenue Mall, Columbus, OH 432101277
{vandalor, fahmy, jain, goyal, mukul}@cse.wustl.edu
In this paper we give a general definition of weighted fairness and discuss how a pricing policy can be mapped to general weighted (GW) fairness. The GW fairness can be achieved by calculating the ExcessFairshare(weighted fairshare of the left over bandwidth) for each VC. We show how a switch algorithm can be modified to support the GW fairness by using the ExcessFairshareterm. We use ERICA+ as an example switch algorithm and show how it can be modified to achieve the general fairness. Simulations results are presented to demonstrate that, the modified switch algorithm achieves GW fairness. An analytical proof for convergence of the modified ERICA+ algorithm is given in the appendix. ^{1 }
The specification of the ABR feedback control algorithm (switch algorithm) is not yet standardized. The earliest algorithms used binary feedback techniques [ 22]. Distributed algorithms [ 10] that emulated a centralized algorithm were proposed in [ 5, 17]. Improved, simpler distributed algorithms which achieved maxmin fairness were proposed in [ 13, 4, 9, 15, 18, 11]. Recently, [ 20, 2] discussed a generalized definition of maxmin fairness and its distributed implementation. [ 19] discussed a weightbased maxmin fairness policy and its implementation in ABR service. [ 7, 21] discussed the fairness in the presence of MCR guarantees.
In this paper we generalize the definition of the fairness, by allocating the excess bandwidth proportional to weights associated with each source. We show how a switch schemes can support nonzero MCRs and achieve the GW fairness. As an example, we show how the ERICA+ switch scheme can be modified to support GW fairness.
The modified scheme is tested using simulations with various network configurations. The simulations test the performance of the modified algorithm, with different weights, using simple configuration, transient source configuration, link bottleneck configuration, and source bottlenecked configuration. These simulations show that the scheme realizes various fairness definitions in ATM TM 4.0 specification, that are special cases of the generalized fairness. We present an analytical proof of convergence for the modified algorithm in the appendix.
The general weighted fair allocation is defined as follows:
It is reasonable to assume that f() is a nondecreasing function of W. That is, those sending more bits do not pay less. The function f() should also be a nonincreasing function of time Tor equivalently a nondecreasing function of rate R. For economy of scale, it is important that the cost per bit does not increase as the number of bits goes up. That is, C/Wis a nondecreasing function of W. Mathematically, we have three requirements: a) b) c) .
One simple function that satisfies all these requirements is: C= c+ wW+ rR. Here, cis the fixed cost per connection; wis the cost per bit; and ris the cost per Mbps. In general, c, w, and rcan take any nonnegative value.
In the presence of MCR, the above discussion can be generalized to: C=f(W,R,M) where, Mis the MCR. All arguments given above for Rapply to Malso except that the customers requesting larger Mpossibly pay more. One possible function is: C= c+ wW+ rR+ mM, where, mis dollars per Mbps of MCR. In effect, the customer pays r+mdollars per Mbps up to Mand then pays only rdollars per Mbps for all the extra bandwidth he/she gets over and above M.
Consider two users with MCRs M _{1 }and M _{2 }. Suppose their allocated rates are R _{1 }and R _{2 }and, thus, they transmit W _{1 }and W _{2 }bits, respectively. Their costs are: C _{1 }= c+ wW _{1 }+ rR _{1 }+ mM _{1 }and C _{2 }= c+ wW _{2 }+ rR _{2 }+ mM _{2 }
Cost per bit (C/W) should be a decreasing function of bits W. Thus, if :
Since R _{i }= W _{i }/T, we have:
Where a(=c/m) is the ratio of the fixed cost and cost per unit of MCR. Note that the allocated rates should either be proportional to a+MCR or be a nondecreasing function of MCR. This is the weight policy we have chosen to use in our simulations.
The following additional notation is necessary:
Definition 1 General Weighted Fair Allocation Problem
The GW fair problem is to find the rate vector equal to the GW fair allocation, i.e., . Where is calculated for each link las defined in the section 2.
Note the 5tuple represents an instant of the bandwidth sharing problem. When all weights are equal the allocation is equivalent to the general maxmin fair allocation as defined in [ 20, 2]. A simple centralized algorithm for solving the above problem would be to first, find the correct allocation vector for the bottleneck links. Then, solve the same problem of smaller size after deleting bottleneck links. A similar kind of centralized, recursive algorithm is discussed in [ 20]. Centralized algorithm implies that all information is known at each switch, which is not feasible, hence a distributed algorithm is necessary.
In the case of GW fairness, the
ExcessFairshareterm is given by:
The activity level inherently captures the notion of marking, i.e., when a source is bottlenecked elsewhere, then activity level times the fairshare (based on available left over capacity) is the actual fairshare of the bottleneck source. The computation of activity level can be done locally and is an O(1) operation, compared to O(n)computations required in consistent marking [ 1].
We expect that the links use their ExcessFairshare, but this might not be case. By multiplying the weights by the activity level, and using these as the weights in calculating the ExcessFairsharewe can make sure that the rates converge to the GW fairness allocation. Therefore, the ExcessFairshareshare term is defined as:
A switch algorithm can use the above ExcessFairshareterm to achieve general fairness. In the next section we show how the ERICA+ switching algorithm is modified to achieve GW fairness.
The ERICA+ algorithm uses the term FairSharewhich is the bottleneck link capacity divided by the active number of VCs. It also uses a MaxAllocPreviousterm, which is the maximum allocation in the previous ``Averaging Interval''. This term is used to achieve maxmin fairness. We modify the algorithm by replacing the FairShareterm by ExcessFairshare(i) and adding the . The keys steps in ERICA+ which are modified to achieve the GW fairness are shown below:
Algorithm A
At the end of Averaging Interval:
The Fractionterm is dependent on the queue length [ 3]. Its value is one for small queue lengths and drops sharply as queue length increases. When the Fractionis less than one, is used to drain the queues. ERICA+ uses an hyperbolic function for calculating value of the Fraction.
When a BRM is received:
The VCShareis used to achieve an unit overload. When the network reaches steady state the VCShareterm converges to ExcessFairshare(i), achieving generalized fairness criterion. The complexity of the computations done at the switching interval is O(number of VCs). The update operation when the BRM cell arrives is an O(1) operation. Proof of convergence of algorithm A, is given in the appendix.
Configuration  Link  Averaging  Target 
Name  Distance  interval  Delay 
Three Sources  1000 Km  5 ms  1.5 ms 
Source Bottleneck  1000 Km  5 ms  1.5 ms 
GFC2  1000 Km  15 ms  1.5 ms 
Expected  
Case  Src  mcr  a  wt  fair  Actual 
#  #  func.  share  share  
1  1  0  1  49.92  49.92  
2  0  1  49.92  49.92  
3  0  1  49.92  49.92  
2  1  10  1  29.92  29.92  
2  30  1  49.92  49.92  
3  50  1  69.92  69.92  
3  1  10  5  15  18.53  16.64 
2  30  5  35  49.92  49.92  
3  50  5  55  81.30  81.30 
The allocations of these cases are given in Table 2. The following can be observed from the Table 2
The Figure 2shows the ACRs of the three sources for the above three cases. From the figure one can observe that the sources achieve the GW fairness. Steady state queues were of constant length.
The ACR values of the sources for these three simulations are shown in figure 5. It can be seen both from the Table 3and the graphs that the switch algorithm does converge to the general fairness allocation even in the presence of transient sources. We observed that the algorithm had a good response time from the utilization graph (not shown here due to lack of space).
Cases 1, 2 and 3 of section 8.1were simulated using the three sources bottleneck configuration. The total simulation time was 800 ms. In these simulations the source S1 is bottlenecked at 10 Mbps for first 400 ms, i.e., it always transmits data at rate of at most 10 Mbps, irrespective of its ACR (and ICR).

The initial ICRs were set to 50, 30, 110 Mbps. The load on the bottleneck link is near unity. If the switch algorithm uses the CCR (current cell rate) value indicated in the RM cell as the source rate the switch cannot estimate the correct value of source rate of the bottleneck source. But if the switch uses measured source rate then it can correctly estimate the bottlenecked source's rate. Table 4shows the results both when the switch uses the CCR field and when it measures the source rate. The correct fairness is achieved when the measured source rates are used.
Exp  Actual  Exp  Actual  
Src  wt.  frshr  (ntr)  frshr  (tr)  
#  #  func.  (ntr)  share  (tr)  share 
1  1  1  74.88  74.83  49.92  49.92 
2  1  NC  NC  49.92  49.92  
3  1  74.88  74.83  49.92  49.92  
2  1  1  54.88  54.88  29.92  29.83 
2  1  NC  NC  49.92  49.92  
3  1  94.88  95.81  69.92  70.93  
3  1  15  29.92  29.23  18.53  18.53 
2  35  NC  NC  49.92  49.92  
3  55  119.84  120.71  81.30  81.94 
The graphs for these simulations are given in Figure 6. Graphs in Figure 6 (a), (b) and (c) correspond to cases 1, 2 and 3 without using measured source rates. Graphs in Figure 6 (c), (d) and (e) are for the same cases using measured source rates. The switch algorithm uses queue control, to dynamically use part of available ABR capacity to drain the queues. When the queue is large the available ABR capacity is only a fraction of actual capacity. So, the algorithm takes sometime before converging to the correct fairness values. When the CCR value from the RM cells is used, the algorithm is not able to estimate the actual rate at which the source is sending data. So it does not converge in case 2 and case 3 (Figures 6 (b) and 6 (c)). In case 1 (Figure 6 (a), it converged since the bottleneck source's rate (CCR) had the correct value of 50 which is the same allocation it would get in the fair allocation.
In this configuration each link is a bottleneck link. The Figure 7 (a) shows the ACR graphs for each type of VCs. The expected share for VCs of type A, B, C, D, E, F, G, H are 10, 5, 35, 35, 35, 10, 5, and 52.5 Mbps respectively. The actual allocation for these VCs in the simulation was 9.85, 4.97, 35.56, 35.71, 35.34, 10.75, 5, and 51.95 Mbps respectively. From the Figure and actual allocations it can be seen that the VCs converge to their expected fairshare. This shows that the algorithm works in the presence of multiple link bottlenecks and varying round trip times.
Exp  Using  Using  
Case  Src  wt.  frshr  CCR  Measured 
#  #  func.  in RM cell  CCR  
1  1  1  49.92  49.85  49.92 
2  1  49.92  49.92  49.92  
3  1  49.92  49.92  49.92  
2  1  1  29.92  NC  29.62 
2  1  49.92  NC  49.60  
3  1  69.92  NC  71.03  
3  1  15  18.53  NC  18.42 
2  35  49.92  NC  49.92  
3  35  81.30  NC  81.93 
We have shown how ERICA+ switch algorithm can be modified to achieve this general fairness. The proof of convergence of algorithm A is given in the appendix. The modified algorithm has been tested under different configuration using persistent sources. The simulations results show that the modified algorithm achieves the general fairness in all configurations. In addition, the results show that the algorithm converges in the presence of both source and link bottleneck and is quick to respond in the presence of transient sources. In source bottlenecked configuration the value of the CCR (source rate) from the RM cells maybe incorrect. Hence, it is necessary to used the measured source rate in the presence of source bottlenecks.
Lemma 1 The Algorithm A converges to the GW fair allocation, for a session bottlenecked by a link.
Proof:The proof technique used here is similar to the one used in [ 13]. Let l _{b }be the link which is bottlenecked. Without loss of generality assume that first ksessions through the link l _{b }are bottlenecked (either link bottlenecked or source bottlenecked) elsewhere. Let . Let be the bottleneck rates and be the rates of nonbottlenecked (underloaded) sources. Let be total capacity of bottlenecked links. These nonbottlenecked sources are bottlenecked at the current link l _{b }. According to the GW fairness definition, fair allocation rates g _{i }is given by:
Assume that the bottlenecks elsewhere have been achieved, therefore the rates are stable. For simplicity, assume that the MCRs of these sources are zero. Proof for the bottlenecks having nonzero MCRs is a simple extension.
We show that rates allocated at this switch converges to and and load factor converges to z= 1.
Case 1:Load factor z< 1. Here the link is underloaded, hence due to the VCShare term , all the rates increase. If n= 0, i.e. all the sessions across this link are bottlenecked elsewhere, there are no nonbottlenecked sources, the GW fair allocation is trivially achieved. Assume that , now because of the VCShare term (in step for calculating ERin Algorithm A), the rates of nonbottlenecked sources increase. This continues till load factor reaches a value greater than or equal to one. Hence we have shown that if load factor is less than one, the rates increase till the load factor becomes greater than one.
Case 2:Load factor z> 1. In this case if the link is not getting its ExcessFairsharethen, its rate increases, which might further increase z. This continues till all the sessions achieve at least their ExcessFairshare. At this point the allocation rates are decreased proportional to 1/zdue to the first term. As in the previous case the zdecreases, till it reaches a value of 1 or less.
From the above two cases it can be seen that load factor oscillates around one and converges to the value of one. Assume that load factor is , then the number round trip times for it to converge to one is given by . Henceforth, in our analysis we assume that the network is near the steady state that is load factor is near one. This implies that
Let be the total allocation for MCRs of the nonbottlenecked sources. Define , then we have: . We have to show that:
Case A:n= 0, i.e., there are no bottleneck sources. From the step for calculating ERin Algorithm A, we have:
We observe that this equation behaves like a differential equation in multiple variables [ 8]. The behavior is like that of successive values of root acquired in the NewtonRalphson method for finding roots of a equation. Hence the above equation converges, and the stable values of is given by:
Since, we have assumed greedy sources and no bottlenecks in this case, the activity level is one for all sessions. Hence, , which is indeed the desired value for .
Case B: , i.e., there are some bottleneck sources. Let be the allocated rate corresponding to r _{b i }. Let w _{b i }be the weight for session s _{b i }. Let and . We know that the equation for the rate allocation behaves as a stabilizing differential equation. In the steady state all the above terms such as W, W _{b }and rates stabilize. For sources bottlenecked elsewhere the algorithm calculates a rate which is greater than r _{b i }, otherwise the bottlenecked session would be bottlenecked at the current link. For nonbottlenecked source the rate at steady state is given by:
Since the link has an overload of one at steady state we have , which implies that
Using the above value for W
_{b
}we get:
Therefore, which is the desired values for the . Hence, the sessions bottlenecked at the link l _{b }do indeed achieve the GW fairness.
Theorem 1 Starting at any arbitrary state of the network, if only greedy sources and source bottlenecked or link bottlenecked sources are present the Algorithm A converges to GW fair allocation.
Proof:The convergence of the distributed algorithm similar to the centralized algorithm. Assume that the centralized algorithm converges in Miterations. At each iteration there are set of links which are bottlenecked at the current iteration. .
Using lemma 1, we know that each link does indeed converge to the general fair allocation . The distributed algorithm converges in the above order of links until the whole network is stable and allocation is . The number of round trips taken to converge is bounded by , since each link takes round trips for convergence.