Title of Invention	A METHOD FOR DYNAMICALLY ALLOCATING LINK BANDWIDTH ON RESILIENT PACKET RING
Abstract	The invention discloses a method for distributing dynamic link bandwidth for Resilient Packet Ring. This method adopts a new fair distribution mode, which measures a group of variables in an advertisement interval, calculates local fair rate by using the group of variables, and dertermines advertising rate by local fair rate. Each node at Resilient Packet Ring transmits data packet based on the advertising rate, ensuring a fair distribution on the bandwidth of Resilient Packet Ring; this method, compared with the existing method, introduces a concept of integral for the idle rate, thus obtaining a 100% of bandwidth utilization rate, and avoiding the present concept of “congested state” in existing fair distribution mode used currently.

Title of Invention

A METHOD FOR DYNAMICALLY ALLOCATING LINK BANDWIDTH ON RESILIENT PACKET RING

Abstract

The invention discloses a method for distributing dynamic link bandwidth for Resilient Packet Ring. This method adopts a new fair distribution mode, which measures a group of variables in an advertisement interval, calculates local fair rate by using the group of variables, and dertermines advertising rate by local fair rate. Each node at Resilient Packet Ring transmits data packet based on the advertising rate, ensuring a fair distribution on the bandwidth of Resilient Packet Ring; this method, compared with the existing method, introduces a concept of integral for the idle rate, thus obtaining a 100% of bandwidth utilization rate, and avoiding the present concept of “congested state” in existing fair distribution mode used currently.

Full Text	FORM 2 THE PATENTS ACT, 1970 (39 of 1970) & The Patents Rules, 2003 PROVISIONAL / COMPLETE SPECIFICATION (See section 10 and rule 13) 1. TITLE OF THE INVENTION : "METHOD FOR DYNAMICALLY ALLOCATING LINK BANDWIDTH ON RESILIENT PACKET RING " 2. APPLICANT (S) (a) NAME (b) NATIONALITY (c) ADDRESS ZTE CORPORATION CHINESE ZTE Plaza, Keji Road South, Hi-Tech Industrial Park, Nanshan District, Shenzhen City, Guangdong Province 518057, P.R. China. 3. PREAMBLE TO THE DESCRIPTION PROVISIONAL The following specification describes the invention COMPLETE The following specification particularly describes the invention and the manner in which it is to be performed. 4. DESCRIPTION (Description shall start from next page) 5. CLAIMS (not applicable for provisional specification. Claims should start with the preamble "I/we claim" on separate page) 6. DATE AND SIGNATURE (to be given at the end of last page of specification) 7. ABSTRACT OF THE INVENTION (to be given along with complete specification on separate page) Note:- * Repeat boxes in case of more than one entry. To be signed by the applicant(s) or by authorized registered patent agent. Name of the applicant should be given in full, family name in the beginning. Complete address of the applicant should be given stating the postal index no./code, state and country Strike out the column which is/are not applicable. Method for Dynamically Allocating Link Bandwidth on Resilient Packet Ring Field of the Invention This invention relates to data communication technology used in Wide Area Network (WAN) or Local Area Network (LAN), more particularly, to a method for dynamically allocating link bandwidth on Resilient Packet Ring (RPR). Background of the Invention RPR is a metropolitan area network (MAN) with a brand-new ring structure, which supports the data traffic for three service levels, and has the advantages of high bandwidth utilization, high reliability and so on. One of the key techniques for implementing RPR is to allocate the link bandwidth to the nodes competing for resources on the ring. The present invention discloses a method for dynamically allocating link bandwidth on resilient packet ring. Compared with the solution proposed by the current PRP working group (IEEE 802.17 working group), this method is simpler and has higher bandwidth utilization. The mission of IEEE 802.17 working group is to establish a technical standard for RPR. The RPR technology is used in the data communication in WAN or LAN, and compared with the existing data communication technology used in WAN or LAN, it has two obvious advantages: 1. higher bandwidth utilization. 2. fast protection mechanism. The protection kicks in within 50ms, which is on the same level as fault detection. Each node on the RPR ring can insert some fairness eligible packet on to the ring. Once a data packet is added on to the ring, it will be passed on by the downstream nodes. During this process, the upstream node may transmit too much traffic, leaving the downstream nodes "starved". So a mechanism is needed to ensure each node on the ring has the same opportunity to transmit user's data packets. In the mechanism proposed by IEEE 802.17 working group, each node will transmit a special packet, named fairness packet, which is used to pass a proposed advertising rate to the upstream node. In order to ensure that every node on the ring has some chance to send its packets, each node will make sure that the amount of Fairness Eligible -2.- packets added to the ring not exceeding an allowed rate, which is the smaller one of the received advertising rate and the local fair rate. The key point to guarantee the network performance lies on how to determine the advertising rate based on the advertising rate received from the downstream node and the local fair rate. The mechanism proposed by IEEE 802.17 working will be described briefly. At present, there are two fairness modes proposed by IEEE 802.17 working group, one is named aggressive mode, the other is named conservative mode. Here only un-weighted version is discussed for the existing fairness algorithm proposed by IEEE 802.17. It is noted that the method for dynamically allocating link bandwidth on resilient packet ring proposed in the present patent application is a weighted fairness algorithm. The existing fairness algorithm is described as following: add rate (add_rate): this is the byte count, in an advertisement interval, for local packets added onto the ring by the node for the FE eligible packets; local fair rate (local_fair_rate): the low pass filtered add rate, different modes employ different algorithms to obtain local_fair_rate; received advertising rate (received_advertising_rate): the advertising rate carried in type A fairness packet, which is advertised by the downstream node. advertisement interval: On every advertisement interval, a type A fairness packet will be send to the upstream stations, with advertising-rate inside the type A fairness message. advertising rate: the rate is determined as follows: o If (the local node is congested and local_fair_rate 3 o If (the local node is congested and local_fair_rate >= received_advertising_rate ) congested, the advertising-rate will be the received advertising rate from downstream (received_advertising_rate). o If (the local node is not congested), the advertising_rate will be the ones received from downstream, or null if receiving null rate, which indicates the maximum link rate. The main difference, along with some minor ones, between the aggressive mode and the conservative mode lies on how to define the local_fair_rate. In the aggressive mode, the local_fair_rate is the low pass filtered version of the add-rate. In the conservative mode, the local_fair_rate is the low pass filtered version of the add_rate, which is similar to that of aggressive mode, and o plus a fraction of the filtered version of the add-rate if the link utilization is less than 85% (below low_threshold) o minus a fraction of the filtered version of the add_rate if the link utilization is more than 95% (above high_threshold) Compared to the fairness algorithm in the aggressive mode, the fairness algorithm in the conservative mode offers better performance under varying conditions, at the cost of maximum 95% bandwidth utilization, which is inferior under certain situations. The main issue with the aggressive mode is, when the congestion point is not a greedy source, as illustrated in Figure 1, the bandwidth can not be properly allocated among all the sources and result in inefficient resource usage, as illustrated in simulation in Figure 2. Summary of the Invention In summary, the main issue with the fairness algorithm in aggressive mode is the stability of the bandwidth allocation when non-greedy source is mixed with greedy source, which leads to bandwidth wastage. The main issue with the fairness algorithm in conservative mode is maximum 95%o bandwidth utilization, which leads to inferior performance when all the sources are greedy sources. The objective of the present invention is to provide a method for dynamically allocating link bandwidth on resilient packet ring, which can ensure the fairness of the bandwidth allocate. It should be simpler, and 4 should yield higher bandwidth utilization than the existing fairness algorithm in 802.17 standard drafts. The method for dynamically allocating link bandwidth on resilient packet ring keeps the basic structure and message type as defined by the IEEE 802.17 working group for conformance purposes. The concept of advertisement interval is used. Within one advertisement interval, the following steps are implemented: a. measure the values for variables 1. add_rate: This is the byte count for local packets added onto the ring by the node for the fairness eligible packets. 2. total_add_rate: This is the total byte count for local packets added onto the ring by the node. 3. fw_rate: This is the byte count for transit packets on the ring for the fairness eligible packets. 4. total_fw_rate: This is the total byte count for transit packets on the ring. b. The objective of the method for dynamically allocating link bandwidth on resilient packet ring is to ensure that the link is fully utilized, while the bandwidth is properly allocated among all the competing stations. In order to achieve this, the local_fair_rate is always calculated according to the following steps: bl. calculate an idle rate (idle_rate) with the equation: idle_rate=link_rate-total_add_rate-total_fw_rate, where link_rate is the byte count for one advertisement interval at full link rate; b2. if idle_rate acc_idle=(a; -1) * acc_idle/a otherwise, acc_idle=acc_idle+idle_rate/ β acc_idle=min(acc_idle,unreserved_rate) 5 where acc_idle is basically the integral of the idle rate, and its value is no more than the unreserved rate (unreserved_rate); b3. Calculate the local fair rate (local_fair_rate) with the formula: local_fair_rate=((5-l)local_fair_rate/d+add_rate(^weight)+acc_idle/^ where Weight is the station weight for weighted fairness algorithm. c. determining an advertising rate (advertising_rate), which comprises the following steps: c l. if the value of the received advertising rate is less than the value of the local fair rate (i.e. received_advertising_rate c 2. if(fw_rate c3. if ( add_rate>minimum packet size) or there are packets in the low priority queue to be transmitted, the advertising rate (advertising_rate) is set to the local fair rate (local_fair_rate); c4. otherwise, the advertising rate (advertising_rate) is set to the received advertising rate (received_advertising_rate). d. each node on the RPR ring transmits data packets with a rate no more than the advertising rate determined in the third step to ensure that the nodes fairly share the bandwidth ring. Compared with the existing fairness algorithm in 802.17 standard draft, the method for dynamically allocating link bandwidth on resilient packet ring in this invention introduces integral for the idle rate, so as to obtain 100% of bandwidth utilization. (In most of the cases in practice, only one link can achieve this (100%) due to the advertisement rules for the local_fair_rate.) The new algorithm also avoids the concept of "congestion state" in existing fairness algorithms. The new algorithm in this invention has the following advantages: Philosophical advantage: 6 1. Existing fairness algorithm attempts to achieve fair bandwidth distribution among all the competing stations only when some nodes are in the "congestion state". 2. The method for dynamically allocating link bandwidth on resilient packet ring attempts to ensure 100% link utilization on every segment. For a single choke point fairness algorithm, in most cases, only one link can achieve such link utilization, which is also one of the purposes the fairness algorithm. Algorithmic advantage: 1. congestion state: In the existing approach, every station will advertise "null" indicating the maximum bandwidth if there is no congestion point on the ring. The station will advertise non-null value only if it is in the congestion state or receiving advertisement with non-null value. In the new approach, there is no concept of "congestion state" and every station will advertise according to the algorithm above, which significantly reduces the algorithm complexity. 2. measurement of the idle rate: The purpose of such measurement is to ensure 100% usage of the link bandwidth. An integrated (similar to the / function of the PID [Proportional, Integral, and Derivative] controller in the control theory) version of the idle rate contributes to the local_fair rate. The existing approach will measure many other information which will not be required in the new approach. 3. advertising rate: The determination of advertising_rate is different. In the new approach, the RPR station will advertise its local_fair_rate if the station sends out any packet or if there is any packet waiting to be sent out, conditioning on the local_fair_rate is smaller than the received_advertising_rate. (rule c3 above).. 4. local fair rate (local_fair_rate): The calculation mechanism to obtain the local_fair_rate is completely different between the existing fairness algorithm and the present invention. Brief Description of the Drawings Fig.l shows the fairness scenario of none-greedy and greedy sources 7 sharing link bandwidth.( detailed as choking high/low bandwidth pairs example in Annex 1.3.7 in IEEE802.17 draft 2.4). Fig.2 is the simulation result of the example in Fig.l using existing fairness algorithm aggressive mode. Fig.3 is the simulation result of the example in Fig.l using existing fairness algorithm conservative mode. Fig.4 shows fairness scenario with four sources requesting FE packet transmission (see the parking lot example detailed by Annex 1.3.1 in IEEE802.17 draft 2.4); Fig. 5 is the simulation result of the fairness scenario in Fig.4 under the existing fairness algorithm aggressive mode; Fig. 6 is the simulation result of the fairness scenario in Fig.4 under the existing fairness algorithm conservative mode; Fig.7 is the simulation result of the fairness scenario in Fig.4 using the method in this invention. Fig.8 is the simulation result of the fairness scenario in Fig.l using the method in this invention; Fig.9 is the flow chart for determining local_fair_rate in the method of the present invention; Fig. 10 is the flow chart for determining the advertising_rate in the method of the present invention. Detailed Description of the Invention The detailed implementation of the technical solution will be described together with the figures. This invention discloses a method for dynamically allocating link bandwidth on resilient packet ring. The method comprises the following steps in one advertisement interval: a. measure the values for variables 1. add_rate: This is the byte count for local packets added onto the ring by the node for the fairness eligible packets. 2. total_add_rate: This is the total byte count for local packets added onto the ring by the node. 3. fw_rate: This is the byte count for transit packets on the ring for the fairness eligible packets. 4. total_fw_rate: This is the total byte count for transit packets on the ring. b. The objective of the present invention is to ensure that the link is fully used, while the bandwidth is properly allocated among all the competing stations. In order to achieve this, the local_fair rate is always calculated according to the following steps (see Fig. 9 ): bl. calculate an idle rate (idle_rate) with the equation: idle_rate=link_rate-total_add_rate-total_fw_rate, where link_rate is the byte count for one advertisment interval at full link rate; b2. if idle_rate acc_idle=(a -1) * acc_idle/a otherwise, acc_idle=acc_idle+idle_rate//? acc_idle=min(acc_idle,unreserved_rate) where acc_idle is basically the integral of the idle rate, and its value is no more than the unreserved rate (unreserved_rate); b3. calculate the local fair rate (local_fair_rate) with the formula: local_fair_rate=(5-l)local_fair_rate/ c. determining an advertising rate (advertising_rate), which comprises the following steps (see Fig. 10): c l. if the value of the received advertising rate is less than the value of the local fair rate (i.e. received_advertising_rate 9 advertising rate (received _advertising_rate); c 2. if (fw_rate c3. if ( add_rate>minimum packet size) or there are packets in the low priority queue to be transmitted, the advertising rate (advertising_rate) is set to the local fair rate (local_fair_rate); c4. otherwise, the advertising rate (advertising_rate) is set to the received advertising rate (received_advertising_rate). d. each node on the RPR ring transmits data packets with a rate no more than the advertising rate determined in the third step to ensure that the nodes fairly share the bandwidth ring. Simulation studies have been performed on this invention. The simulation studies cover all the 8 cases suggested by IEEE 802.17 working group for fairness algorithm evaluation and the inter-operation test between the existing fairness algorithm and this invention. Selected result will be presented here, with the rest of them available on request. Fairness scenario (1) - high-low bandwidth: The high-low bandwidth setup is shown in Fig. 1. The ideal bandwidth allocation for node S5 is 12.5M (more than 5% due to the particular simulation parameters), and that for node SI is 137.5M. The simulation result of the aggressive mode is shown in Fig. 2. The bandwidth allocated to node SI oscillates between 46M and 130M under the aggressive mode. That is the main reason for introducing the conservative mode of the existing fairness algorithm. The main issue with the conservative mode is maximum 95% bandwidth utilization, which leads to inferior performance when all the sources are greedy sources. Fig.3 shows the simulation result of the conservative mode. Fig.8 shows the simulation result of the method for dynamically allocating link bandwidth on resilient packet ring. The simulation results show that the present invetion yields high 10 bandwidth utilization, as shown in Fig. 8. The present invention achieves almost 100% bandwidth utilization. Comparing with the aggressive mode shown in Fig. 2, it can avoid bandwidth wastage. Fairness scenario (2) - parking lot: Fig.4 shows the station arrangement and the traffic requirement. Fig. 5 is the simulation result of the fairness scenario in Fig.4 under the existing fairness algorithm aggressive mode. Fig. 6 is the simulation result of the fairness scenario in Fig.4 under the existing fairness algorithm conservative mode. Fig.7 is the simulation result of the fairness scenario in Fig.4 using the method in this invention. The fundamental requirement for bandwidth allocation is the fairness. It can be seen from these simulation results that the new algorithm can ensure the fair bandwidth allocation. So can all the existing fairness algorithms. The new algorithm achieves the same bandwidth utilization as aggressive mode does. The bandwidth utilization of the conservative mode is only about 90%. 11 1. A method for dynamically allocating link bandwidth on Resilient Packet Ring, which is based on fairness bandwidth calculation per advertisement interval, characterized in that, the method comprises the following steps in one advertisement interval: a. measuring a group of variables; b. calculating a local fair rate using the measured variables; c. determining the advertising rate based on the local fair rate and the advertising rate provided by a downstream node; d. each node on a resilient packet ring determines the advertising rate by Step c, and transmits data packets with the advertising rate. 2. The method for dynamically allocating link bandwidth on Resilient Packet Ring according to claim 1, characterized in that, the group of variables in Step a are: al. add_rate: This is the byte count for local packets added onto the ring by the node for the fairness eligible packets, a2. total_add_rate: This is the total byte count for local packets added onto the ring by the node, a3. fw_rate: This is the byte count for transit packets on the ring for the fairness eligible packets, a4. total_fw_rate: This is the total byte count for transit packets on the ring. 3. The method for dynamically allocating link bandwidth on Resilient Packet Ring according to claim 1, characterized in that, Step b comprises the following further steps: bl. calculate an idle rate with the equation: idle_rate=link_rate-total_add_rate-total_fw_rate, where link_rate is the byte count in one advertisement interval at full link 12 rate; b2. if idle_rate is less than idle_rate_threshold, where the idle_rate_threshold could be set to 0.01 or even lower: acc_idle=(a -1) acc_idle/a otherwise, acc_idle=acc_idle+idle_rate//? acc_idle=min(acc_idle,unreserved_rate) where acc_idle is basically the integral of the idle rate, and its value is no more than the unreserved rate; b3. calculate the local fair rate with the formula: local_fair_rate=(^-l)*local_fair_rate/ 4. The method for dynamically allocating link bandwidth on Resilient Packet Ring according to claim 1, characterized in that, Step c comprises the following further steps: c l. if the received advertising rate is less than the local fair rate, the advertising_rate is set to the value of the received advertising rate; c 2. if fw_rate is less than local_fair_rate, the advertising_rate is set to the local_fair_rate; c3. if add_rate is more than minimum packet size or there are packets in the low priority queue to be transmitted, the advertising_rate is set to the local_fair_rate; c4. otherwise, the advertising_rate is set to the received advertising rate. 5. The method for dynamically allocating link bandwidth on Resilient Packet Ring according to claim 1, characterized in that, Step d means that: each node on the resilient packet ring determines the advertising rate by 13 Step c, and transmits data packets with the advertising rate, ensures the fair bandwidth allocation to the nodes on the resilient packet ring. 6, A method for dynamically allocating link bandwidth on Resilient Packet Ring substantially as herein described with reference to the accompanying drawings. Dated this 27th day of July, 2005, -14- Abstract The invention discloses a method for dynamically allocating link bandwidth on resilient packet ring. This algorithm comprises the steps of measuring a group of variables in one advertisement interval, calculating the local fair rate using the measured variables, determining an advertising rate based on the local fair rate, and transmitting the data packets with the advertising rate. Compared with existing fairness algorithms, the new algorithm introduces integration for the idle rate to achieve 100% of bandwidth utilization. It also avoids using the concept of "congestion state" which is essential in the existing fairness algorithm. 15

Full Text

FORM 2
THE PATENTS ACT, 1970
(39 of 1970)
&
The Patents Rules, 2003
PROVISIONAL / COMPLETE SPECIFICATION
(See section 10 and rule 13)
1. TITLE OF THE INVENTION :
"METHOD FOR DYNAMICALLY ALLOCATING LINK BANDWIDTH ON RESILIENT PACKET RING "

2. APPLICANT (S)
(a) NAME
(b) NATIONALITY
(c) ADDRESS

ZTE CORPORATION
CHINESE
ZTE Plaza, Keji Road South, Hi-Tech Industrial Park, Nanshan District, Shenzhen City, Guangdong Province 518057, P.R. China.

3. PREAMBLE TO THE DESCRIPTION

PROVISIONAL
The following specification describes the invention

COMPLETE
The following specification particularly describes the invention and the manner in which it is to be performed.

4. DESCRIPTION (Description shall start from next page)
5. CLAIMS (not applicable for provisional specification. Claims should start with the preamble "I/we claim" on separate page)
6. DATE AND SIGNATURE (to be given at the end of last page of specification)
7. ABSTRACT OF THE INVENTION (to be given along with complete specification on separate page)
Note:-
* Repeat boxes in case of more than one entry.
*To be signed by the applicant(s) or by authorized registered patent agent.
*Name of the applicant should be given in full, family name in the beginning.
*Complete address of the applicant should be given stating the postal index no./code, state and country
* Strike out the column which is/are not applicable.

Method for Dynamically Allocating Link Bandwidth on Resilient Packet Ring
Field of the Invention
This invention relates to data communication technology used in Wide Area Network (WAN) or Local Area Network (LAN), more particularly, to a method for dynamically allocating link bandwidth on Resilient Packet Ring (RPR).
Background of the Invention
RPR is a metropolitan area network (MAN) with a brand-new ring structure, which supports the data traffic for three service levels, and has the advantages of high bandwidth utilization, high reliability and so on. One of the key techniques for implementing RPR is to allocate the link bandwidth to the nodes competing for resources on the ring. The present invention discloses a method for dynamically allocating link bandwidth on resilient packet ring. Compared with the solution proposed by the current PRP working group (IEEE 802.17 working group), this method is simpler and has higher bandwidth utilization. The mission of IEEE 802.17 working group is to establish a technical standard for RPR. The RPR technology is used in the data communication in WAN or LAN, and compared with the existing data communication technology used in WAN or LAN, it has two obvious advantages:
1. higher bandwidth utilization.
2. fast protection mechanism. The protection kicks in within 50ms, which is on the same level as fault detection.
Each node on the RPR ring can insert some fairness eligible packet on to the ring. Once a data packet is added on to the ring, it will be passed on by the downstream nodes. During this process, the upstream node may transmit too much traffic, leaving the downstream nodes "starved". So a mechanism is needed to ensure each node on the ring has the same opportunity to transmit user's data packets.
In the mechanism proposed by IEEE 802.17 working group, each node will transmit a special packet, named fairness packet, which is used to pass a proposed advertising rate to the upstream node.
In order to ensure that every node on the ring has some chance to send its packets, each node will make sure that the amount of Fairness Eligible
-2.-

packets added to the ring not exceeding an allowed rate, which is the smaller one of the received advertising rate and the local fair rate.
The key point to guarantee the network performance lies on how to determine the advertising rate based on the advertising rate received from the downstream node and the local fair rate. The mechanism proposed by IEEE 802.17 working will be described briefly.
At present, there are two fairness modes proposed by IEEE 802.17 working group, one is named aggressive mode, the other is named conservative mode.
Here only un-weighted version is discussed for the existing fairness algorithm proposed by IEEE 802.17. It is noted that the method for dynamically allocating link bandwidth on resilient packet ring proposed in the present patent application is a weighted fairness algorithm.
The existing fairness algorithm is described as following:
add rate (add_rate): this is the byte count, in an advertisement interval, for local packets added onto the ring by the node for the FE eligible packets;
local fair rate (local_fair_rate): the low pass filtered add rate, different modes employ different algorithms to obtain local_fair_rate;
received advertising rate (received_advertising_rate): the advertising rate carried in type A fairness packet, which is advertised by the downstream node.
advertisement interval: On every advertisement interval, a type A fairness packet will be send to the upstream stations, with advertising-rate inside the type A fairness message.
advertising rate: the rate is determined as follows:
o If (the local node is congested and local_fair_rate 3

o If (the local node is congested and local_fair_rate >= received_advertising_rate ) congested, the advertising-rate will be the received advertising rate from downstream (received_advertising_rate).
o If (the local node is not congested), the advertising_rate will be the ones received from downstream, or null if receiving null rate, which indicates the maximum link rate.
The main difference, along with some minor ones, between the aggressive mode and the conservative mode lies on how to define the local_fair_rate. In the aggressive mode, the local_fair_rate is the low pass filtered version of the add-rate. In the conservative mode, the local_fair_rate is the low pass filtered version of the add_rate, which is similar to that of aggressive mode, and
o plus a fraction of the filtered version of the add-rate if the link utilization is less than 85% (below low_threshold)
o minus a fraction of the filtered version of the add_rate if the link utilization is more than 95% (above high_threshold)
Compared to the fairness algorithm in the aggressive mode, the fairness algorithm in the conservative mode offers better performance under varying conditions, at the cost of maximum 95% bandwidth utilization, which is inferior under certain situations.
The main issue with the aggressive mode is, when the congestion point is not a greedy source, as illustrated in Figure 1, the bandwidth can not be properly allocated among all the sources and result in inefficient resource usage, as illustrated in simulation in Figure 2.
Summary of the Invention
In summary, the main issue with the fairness algorithm in aggressive mode is the stability of the bandwidth allocation when non-greedy source is mixed with greedy source, which leads to bandwidth wastage. The main issue with the fairness algorithm in conservative mode is maximum 95%o bandwidth utilization, which leads to inferior performance when all the sources are greedy sources.
The objective of the present invention is to provide a method for dynamically allocating link bandwidth on resilient packet ring, which can ensure the fairness of the bandwidth allocate. It should be simpler, and
4

should yield higher bandwidth utilization than the existing fairness algorithm in 802.17 standard drafts.
The method for dynamically allocating link bandwidth on resilient packet ring keeps the basic structure and message type as defined by the IEEE 802.17 working group for conformance purposes. The concept of advertisement interval is used. Within one advertisement interval, the following steps are implemented:
a. measure the values for variables
1. add_rate: This is the byte count for local packets added onto the ring by the node for the fairness eligible packets.
2. total_add_rate: This is the total byte count for local packets added onto the ring by the node.
3. fw_rate: This is the byte count for transit packets on the ring for the fairness eligible packets.
4. total_fw_rate: This is the total byte count for transit packets on the ring.
b. The objective of the method for dynamically allocating link bandwidth
on resilient packet ring is to ensure that the link is fully utilized, while the
bandwidth is properly allocated among all the competing stations. In order
to achieve this, the local_fair_rate is always calculated according to the
following steps:
bl. calculate an idle rate (idle_rate) with the equation:
idle_rate=link_rate-total_add_rate-total_fw_rate,
where link_rate is the byte count for one advertisement interval at full link rate;
b2. if idle_rate acc_idle=(a; -1) * acc_idle/a
otherwise,
acc_idle=acc_idle+idle_rate/ β acc_idle=min(acc_idle,unreserved_rate)
5
where acc_idle is basically the integral of the idle rate, and its value is no more than the unreserved rate (unreserved_rate);
b3. Calculate the local fair rate (local_fair_rate) with the formula:
local_fair_rate=((5-l)*local_fair_rate/d+add_rate(^*weight)+acc_idle/^ where Weight is the station weight for weighted fairness algorithm.
c. determining an advertising rate (advertising_rate), which comprises the
following steps:
c l. if the value of the received advertising rate is less than the value of the local fair rate (i.e. received_advertising_rate c 2. if(fw_rate c3. if ( add_rate>minimum packet size) or there are packets in the low priority queue to be transmitted, the advertising rate (advertising_rate) is set to the local fair rate (local_fair_rate);
c4. otherwise, the advertising rate (advertising_rate) is set to the received advertising rate (received_advertising_rate).
d. each node on the RPR ring transmits data packets with a rate no more
than the advertising rate determined in the third step to ensure that the
nodes fairly share the bandwidth ring.
Compared with the existing fairness algorithm in 802.17 standard draft, the method for dynamically allocating link bandwidth on resilient packet ring in this invention introduces integral for the idle rate, so as to obtain 100% of bandwidth utilization. (In most of the cases in practice, only one link can achieve this (100%) due to the advertisement rules for the local_fair_rate.) The new algorithm also avoids the concept of "congestion state" in existing fairness algorithms. The new algorithm in this invention has the following advantages:
Philosophical advantage:
6

1. Existing fairness algorithm attempts to achieve fair bandwidth
distribution among all the competing stations only when some nodes are in
the "congestion state".
2. The method for dynamically allocating link bandwidth on resilient
packet ring attempts to ensure 100% link utilization on every segment. For
a single choke point fairness algorithm, in most cases, only one link can
achieve such link utilization, which is also one of the purposes the fairness
algorithm.
Algorithmic advantage:
1. congestion state: In the existing approach, every station will advertise "null" indicating the maximum bandwidth if there is no congestion point on the ring. The station will advertise non-null value only if it is in the congestion state or receiving advertisement with non-null value. In the new approach, there is no concept of "congestion state" and every station will advertise according to the algorithm above, which significantly reduces the algorithm complexity.
2. measurement of the idle rate: The purpose of such measurement is to ensure 100% usage of the link bandwidth. An integrated (similar to the / function of the PID [Proportional, Integral, and Derivative] controller in the control theory) version of the idle rate contributes to the local_fair rate. The existing approach will measure many other information which will not be required in the new approach.
3. advertising rate: The determination of advertising_rate is different. In the new approach, the RPR station will advertise its local_fair_rate if the station sends out any packet or if there is any packet waiting to be sent out, conditioning on the local_fair_rate is smaller than the received_advertising_rate. (rule c3 above)..
4. local fair rate (local_fair_rate): The calculation mechanism to obtain the local_fair_rate is completely different between the existing fairness algorithm and the present invention.
Brief Description of the Drawings
Fig.l shows the fairness scenario of none-greedy and greedy sources
7

sharing link bandwidth.( detailed as choking high/low bandwidth pairs example in Annex 1.3.7 in IEEE802.17 draft 2.4).
Fig.2 is the simulation result of the example in Fig.l using existing fairness algorithm aggressive mode.
Fig.3 is the simulation result of the example in Fig.l using existing fairness algorithm conservative mode.
Fig.4 shows fairness scenario with four sources requesting FE packet transmission (see the parking lot example detailed by Annex 1.3.1 in IEEE802.17 draft 2.4);
Fig. 5 is the simulation result of the fairness scenario in Fig.4 under the existing fairness algorithm aggressive mode;
Fig. 6 is the simulation result of the fairness scenario in Fig.4 under the existing fairness algorithm conservative mode;
Fig.7 is the simulation result of the fairness scenario in Fig.4 using the method in this invention.
Fig.8 is the simulation result of the fairness scenario in Fig.l using the method in this invention;
Fig.9 is the flow chart for determining local_fair_rate in the method of the present invention;
Fig. 10 is the flow chart for determining the advertising_rate in the method of the present invention.
Detailed Description of the Invention
The detailed implementation of the technical solution will be described together with the figures. This invention discloses a method for dynamically allocating link bandwidth on resilient packet ring. The method comprises the following steps in one advertisement interval:
a. measure the values for variables
1. add_rate: This is the byte count for local packets added onto the ring by the node for the fairness eligible packets.

2. total_add_rate: This is the total byte count for local packets added onto the ring by the node.
3. fw_rate: This is the byte count for transit packets on the ring for the fairness eligible packets.
4. total_fw_rate: This is the total byte count for transit packets on the ring.
b. The objective of the present invention is to ensure that the link is fully
used, while the bandwidth is properly allocated among all the competing
stations. In order to achieve this, the local_fair rate is always calculated
according to the following steps (see Fig. 9 ):
bl. calculate an idle rate (idle_rate) with the equation:
idle_rate=link_rate-total_add_rate-total_fw_rate,
where link_rate is the byte count for one advertisment interval at full link rate;
b2. if idle_rate acc_idle=(a -1) * acc_idle/a
otherwise,
acc_idle=acc_idle+idle_rate//? acc_idle=min(acc_idle,unreserved_rate)
where acc_idle is basically the integral of the idle rate, and its value is no more than the unreserved rate (unreserved_rate);
b3. calculate the local fair rate (local_fair_rate) with the formula:
local_fair_rate=(5-l)*local_fair_rate/ c. determining an advertising rate (advertising_rate), which comprises the
following steps (see Fig. 10):
c l. if the value of the received advertising rate is less than the value of the local fair rate (i.e. received_advertising_rate 9

advertising rate (received _advertising_rate);
c 2. if (fw_rate c3. if ( add_rate>minimum packet size) or there are packets in the low priority queue to be transmitted, the advertising rate (advertising_rate) is set to the local fair rate (local_fair_rate);
c4. otherwise, the advertising rate (advertising_rate) is set to the received advertising rate (received_advertising_rate).
d. each node on the RPR ring transmits data packets with a rate no more than the advertising rate determined in the third step to ensure that the nodes fairly share the bandwidth ring.
Simulation studies have been performed on this invention. The simulation studies cover all the 8 cases suggested by IEEE 802.17 working group for fairness algorithm evaluation and the inter-operation test between the existing fairness algorithm and this invention. Selected result will be presented here, with the rest of them available on request.
Fairness scenario (1) - high-low bandwidth:
The high-low bandwidth setup is shown in Fig. 1. The ideal bandwidth allocation for node S5 is 12.5M (more than 5% due to the particular simulation parameters), and that for node SI is 137.5M. The simulation result of the aggressive mode is shown in Fig. 2. The bandwidth allocated to node SI oscillates between 46M and 130M under the aggressive mode. That is the main reason for introducing the conservative mode of the existing fairness algorithm. The main issue with the conservative mode is maximum 95% bandwidth utilization, which leads to inferior performance when all the sources are greedy sources.
Fig.3 shows the simulation result of the conservative mode.
Fig.8 shows the simulation result of the method for dynamically allocating link bandwidth on resilient packet ring.
The simulation results show that the present invetion yields high
10

bandwidth utilization, as shown in Fig. 8. The present invention achieves almost 100% bandwidth utilization. Comparing with the aggressive mode shown in Fig. 2, it can avoid bandwidth wastage.
Fairness scenario (2) - parking lot:
Fig.4 shows the station arrangement and the traffic requirement.
Fig. 5 is the simulation result of the fairness scenario in Fig.4 under the existing fairness algorithm aggressive mode.
Fig. 6 is the simulation result of the fairness scenario in Fig.4 under the existing fairness algorithm conservative mode.
Fig.7 is the simulation result of the fairness scenario in Fig.4 using the method in this invention.
The fundamental requirement for bandwidth allocation is the fairness. It can be seen from these simulation results that the new algorithm can ensure the fair bandwidth allocation. So can all the existing fairness algorithms. The new algorithm achieves the same bandwidth utilization as aggressive mode does. The bandwidth utilization of the conservative mode is only about 90%.

11

1. A method for dynamically allocating link bandwidth on Resilient
Packet Ring, which is based on fairness bandwidth calculation per
advertisement interval, characterized in that, the method comprises the
following steps in one advertisement interval:
a. measuring a group of variables;
b. calculating a local fair rate using the measured variables;
c. determining the advertising rate based on the local fair rate and the
advertising rate provided by a downstream node;
d. each node on a resilient packet ring determines the advertising rate by
Step c, and transmits data packets with the advertising rate.
2. The method for dynamically allocating link bandwidth on Resilient
Packet Ring according to claim 1, characterized in that, the group of
variables in Step a are:
al. add_rate: This is the byte count for local packets added onto the ring by the node for the fairness eligible packets,
a2. total_add_rate: This is the total byte count for local packets added onto the ring by the node,
a3. fw_rate: This is the byte count for transit packets on the ring for the fairness eligible packets,
a4. total_fw_rate: This is the total byte count for transit packets on the ring.
3. The method for dynamically allocating link bandwidth on Resilient
Packet Ring according to claim 1, characterized in that, Step b comprises
the following further steps:
bl. calculate an idle rate with the equation:
idle_rate=link_rate-total_add_rate-total_fw_rate,
where link_rate is the byte count in one advertisement interval at full link
12

rate;
b2. if idle_rate is less than idle_rate_threshold, where the idle_rate_threshold could be set to 0.01 or even lower:
acc_idle=(a -1) * acc_idle/a
otherwise,
acc_idle=acc_idle+idle_rate//? acc_idle=min(acc_idle,unreserved_rate)
where acc_idle is basically the integral of the idle rate, and its value is no more than the unreserved rate;
b3. calculate the local fair rate with the formula:
local_fair_rate=(^-l)*local_fair_rate/ 4. The method for dynamically allocating link bandwidth on Resilient
Packet Ring according to claim 1, characterized in that, Step c comprises
the following further steps:
c l. if the received advertising rate is less than the local fair rate, the advertising_rate is set to the value of the received advertising rate;
c 2. if fw_rate is less than local_fair_rate, the advertising_rate is set to the local_fair_rate;
c3. if add_rate is more than minimum packet size or there are packets in the low priority queue to be transmitted, the advertising_rate is set to the local_fair_rate;
c4. otherwise, the advertising_rate is set to the received advertising rate.
5. The method for dynamically allocating link bandwidth on Resilient
Packet Ring according to claim 1, characterized in that, Step d means
that:
each node on the resilient packet ring determines the advertising rate by
13

Step c, and transmits data packets with the advertising rate, ensures the fair bandwidth allocation to the nodes on the resilient packet ring.
6, A method for dynamically allocating link bandwidth on Resilient Packet Ring substantially as herein described with reference to the accompanying drawings.

Dated this 27th day of July, 2005,

-14-

Abstract
The invention discloses a method for dynamically allocating link bandwidth on resilient packet ring. This algorithm comprises the steps of measuring a group of variables in one advertisement interval, calculating the local fair rate using the measured variables, determining an advertising rate based on the local fair rate, and transmitting the data packets with the advertising rate. Compared with existing fairness algorithms, the new algorithm introduces integration for the idle rate to achieve 100% of bandwidth utilization. It also avoids using the concept of "congestion state" which is essential in the existing fairness algorithm.

15

A METHOD FOR DYNAMICALLY ALLOCATING LINK BANDWIDTH ON RESILIENT PACKET RING

Documents:

Inventors:

PCT Conventions: