Transcript ppt

Improving RPR Fairness
Convergence
Speaker: Chun-Hung Chen
Author: Chuan-Gang Liu, Jung-Shian Li
The 2004 IEEE Asia Pacific Conference on
Circuits and Systems
Refresh on Resilient Packet Ring
Problems in RPR Standard

Convergence Time



RPR Standard performs long convergence time
with some traffic pattern
There are some traffic pattern which may
generate forever convergence
Oscillation

While convergence, the bandwidth allocation will
display an unstable state which will show up and
down
How to Increase Convergence Time and
Prevent Oscillation

Bounded Flow and Unbounded Flow



Bounded Flow: The flow is bounded in the other
links
Unbounded Flow: The flow is unbounded
elsewhere is the other links or the source but is
limited in the local link
Without the knowledge of numbers of
unbounded flows in each link will make fair
rate tracking hard
Example of the importance of the
acknowledge of unbounded flows

There are two
flows passing
Link c, flow 2
and flow 4



Flow 2 is from A
to Station over
D
If Link c is congested, Station C will calculate a fair rate
and send the information upstream to Station B
If flow 2 is congested at Link b, the surplus bandwidth
is wasted at Link c

Flow 2 at Link b gets 1/3 of total bandwidth, but it gets ½ of
total bandwidth at Link c1/6 of total bandwidth is unused at
Link c
Detail Procedure of Calculating
Unbounded Flows

Formula (1)








R: input rate of the link
Kt: number of unbounded flows
F: local fair rate
r: total rate bounded by the other links or source
Formula (2)


Ki (n)  Ri (n) / Fi (n)
Ki(n): estimated number of unbounded flows in link i in the nth
iteration
Ri(n): measured input rate of link i in the nth iteration
Fi(n): estimated fair rate of link i in the nth iteration
Formula (3)

R  Kt  F  r
Ci: capacity of link I
Ni: number of active flows in link i
Fi (0)  Ci / Ni
There is any flow joining or leaving the link i
Fi (n  1)  min{ C, C / Ki (n)}
K i (n)  K i (n  1)  N i , if N i  0
K i (n)  [ K i (n  1)  N i ] / 2 , if ( Ps  0﹠Tt  Ttt )
K i (n)  Ri (n) / Fi (n) , otherwise
When some flows change state from bounded to unbounded




△Ni: the change of active flow number in link i
Ps: ratio of time in an iteration used by station traffic
Tt: number of iterations
Ttt: threshold of iterations with Ps=0
Comparison with DVSR
R  K t  F  r , F (n  1)  F (n) / R(n)  1 /( K t  r / F (n))
F (0)  initial_fa ir_rate
1
F ( n) 
1 r n
rn
K t ( 1 r )  F ( 0 )
If n is large enough
∵r<0 ∴rn0 => F(n)=(1-r)/Kt
F (n)  1Ktr [1  (1  Kt / N ) n ]  F (0)(1  Kt / N ) n
nPROPOSED
log( 1  Kt / N )
ratio 

nDVSR
log[ Favg  ( N  Kt )]
Simulation Results: Environment




Simulation Software: ns-2
Ttt: 3
Link Capacity: 600Mbps
Flow Demand:



(1,3) : 600Mbps starts at 0.1s, ends at 0.4s
(2,4) : 600Mbps starts at 0.2s, ends at 0.5s
(3,4) : 100Mbps starts at 0.3s, ends at 0.9s
1
2
3
4
Simulation Results

a
Discussion, Observations and Conclusions


Acknowledge of unbounded and bounded
flows is helpful to calculate true fair rate
RIAS is the goal in both mechanisms: DVSR
and Proposed mechanism in this paper


Is RIAS fairness the best fairness state among all?
To minimize the convergence time is to
minimize the times of fair rate iteration