Method and apparatus for managing communications between nodes in a bi-directional ring network
DC
First Claim
Patent Images
1. A method for managing the access of a node to a bi-directional ring network, the node having a downstream link and an output bandwidth, the method comprising the steps of:
- a. identifying the node as being part of a congested span;
b. adjusting the output bandwidth of the node as a function of the congestion in the span.
12 Assignments
Litigations
0 Petitions
Accused Products
Abstract
A fairness scheme is disclosed for managing data flow between nodes in a bi-directional ring network. A method in accordance with the invention controls the output bandwidth of nodes in a bi-directional ring network by: identifying a congested span comprising a head node having a congested downstream link, and a plurality of chain nodes contributing to the congestion in the downstream link: adjusting the output bandwidth of the head node as a function of the congestion in the downstream link; and adjusting the output bandwidth of the chain nodes as a function of the congestion in the downstream link.
32 Citations
30 Claims
-
1. A method for managing the access of a node to a bi-directional ring network, the node having a downstream link and an output bandwidth, the method comprising the steps of:
-
a. identifying the node as being part of a congested span;
b. adjusting the output bandwidth of the node as a function of the congestion in the span. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20)
a. receiving at the node a DS rate from a downstream node in a congested span of which the node is a part;
b. adjusting the output bandwidth of the node as a function of the DS rate;
c. setting an add rate for the node as a function of the DS rate.
-
-
3. A method as defined in claim 2, wherein step “
- b”
comprises the step of;b. setting an add rate for the node as a function of the DS rate.
- b”
-
4. A method as defined in claim 1, wherein the function is a fair function.
-
5. A method as defined in claim 1, wherein the function is an unfair function.
-
6. A method as defined in claim 1, comprising the steps of:
-
a. determining whether the downstream link of the node is congested;
b. if the downstream link is congested, adjusting the output bandwidth of the node as a function of the congestion in the downstream link.
-
-
7. A method as defined in claim 6, wherein step “
- b”
comprises the steps of;b. if the downstream link is congested;
i. adjusting the output bandwidth of the node as a function of the congestion in the downstream link;
ii. adjusting the output bandwidth of one or more upstream nodes contributing to congestion in the downstream link as a function of the congestion in the downstream link.
- b”
-
8. A method as defined in claim 6, wherein step “
- b”
comprises the steps of;b. if the downstream link is congested;
i. setting a target rate for the node;
ii. setting an add rate for the node as a function of the target rate;
iii. setting an advertised rate for the node as a function of the target rate;
iv. sending the advertised rate to one or more upstream nodes contributing to congestion in the downstream link;
v. measuring the downstream link utilization;
vi. setting the target rate as a function of the downstream link utilization;
vii. setting the add rate as a function of the target rate;
vii. repeating steps “
ii”
to “
vii”
.
- b”
-
9. A method as defined in claim 8, wherein steps “
- vi” and
“
vii”
comprise the steps of;vi. if the downstream link is overutilized;
(1) decreasing the target rate;
(2) setting the add rate as a function of the target rate and any DS rate;
vii. if the downstream link is underutilized;
(1) increasing the target rate;
(2) setting the add rate as a function of the target rate and the DS rate.
- vi” and
-
10. A method as defined in claim 9, wherein steps “
- vi” and
“
vii”
comprise the steps of;vi. if the downstream link is overutilized;
(1) decreasing the target rate to a next smallest value;
(2) setting the add rate as a function of the target rate and the DS rate;
vii. if the downstream link if underutilized;
(1) increasing the target rate to a next highest value;
(2) setting the add rate as a function of the target rate and the DS rate.
- vi” and
-
11. A method as defined in claim 8, wherein step “
- vii”
comprises the step of;viii. repeating steps “
ii”
to “
vii”
until the target rate is reaches a maximum threshold.
- vii”
-
12. A method as defined in claim 1, comprising the steps of:
-
a. receiving at the node a DS rate from a downstream node in a congested span of which the node is a part;
b. determining whether the downstream link of the node is congested;
c. adjusting the output bandwidth of the node as a function of the DS rate and the congestion in the downstream link.
-
-
13. A method as defined in claim 12, further comprising the step of:
d. adjusting the output bandwidth of one or more upstream nodes contributing to congestion in the downstream link as a function of the DS rate and the congestion in the downstream link.
-
14. A method as defined in claim 1, comprising the steps of:
-
a. receiving at the node a DS rate from a downstream node in a congested span of which the node is part;
b. setting an add rate for the node as a function of the DS rate;
c. determining whether the downstream link of the node is congested;
d. if the downstream link is congested;
i. setting a target rate for the node;
ii. setting an add rate for the node as a function of the target rate and the DS rate;
iii. setting an advertised rate for the node as a function of the target rate and the DS rate;
iv. sending the advertised rate to one or more upstream nodes contributing to congestion in the downstream link;
v. measuring the downstream link utilization;
vi. setting the target rate as a function of the downstream link utilization;
vii. setting the add rate as a function of the target rate and the DS rate;
viii. repeating steps “
ii”
to “
vii”
.
-
-
15. A method as defined in claim 14, wherein in step “
- c”
, congestion is defined as a function of the maximum bandwidth of the downstream link.
- c”
-
16. A method as defined in claim 14, wherein:
-
a. in step “
vi”
, overutilization of the downstream link is defined as a function of the maximum bandwidth of the downstream link;
b. in step “
vii”
, underutilization of the downstream link is defined as a function of the maximum bandwidth of the downstream link.
-
-
17. A method as defined in claim 1, wherein the step of identifying the node includes the step of identifying a head node in the congested span, which has a congested downstream link, and the step of identifying a chain node in the congested span, which contributes to the congestion in the downstream link.
-
18. A method as defined in claim 17, further comprising the step of sending a fairness message to the upstream node in the congested span to adjust the output bandwidth of the node.
-
19. A method as defined in claim 18, further comprising the step of determining, on the head node, whether the downstream link is underutilized, and the step of increasing, on the head node, a target rate when the downstream link is underutilized, the fairness being sent with the target rate to the upstream node.
-
20. A method as defined in claim 18, further comprising the step of determining, on the head node, whether the downstream link is overutilized, and the step of decreasing, on the head node, the target rate when the downstream link is overutilized, the fairness message being sent with the target rate to the upstream node.
-
21. A method for managing the access of nodes to a bi-directional ring network, the method comprising the steps of:
-
a. identifying a congested span comprising a plurality of nodes;
b. adjusting the output bandwidth of the nodes in the congested span as a function of the congestion in the span. - View Dependent Claims (22, 23)
a. identifying a congested span comprising a head node having a congested downstream link, and a plurality of chain nodes contributing to the congestion in the downstream link;
b. adjusting the output bandwidth of the head node as a function of the congestion in the downstream link;
c. adjusting the output bandwidth of the chain nodes as a function of the congestion in the downstream link.
-
-
23. A method as defined in claim 21, wherein the step of identifying a congested span includes the step of identifying a group of nodes as a congested span, the group of nodes including a head node which has a congested downstream link and a chain node which contributes to the congestion of the downstream link, and the step of adjusting the output bandwidth of the nodes includes the step of sending fairness messages to upstream nodes in the congested span to alleviate the congestion in the downlink congestion.
-
24. An apparatus for managing the access of a node to a bi-directional ring network, the node having a downstream link and an output bandwidth, the apparatus comprising:
-
a. means for identifying a congested span comprising a plurality of nodes;
b. means for adjusting the output bandwidth of the nodes in the congested span as a function of the congestion in the span.
-
-
25. Computer executable software code stored on a computer readable medium, the code for managing the access of a node to a bi-directional ring network, the node having a downstream link and an output bandwidth, the code comprising:
-
a. code to identify the node as being part of a congested span;
b. code to adjust the output bandwidth of the node as a function of the congestion in the span.
-
-
26. A programmed computer for managing the access of a node to a bi-directional ring network, the node having a downstream link and an output bandwidth, comprising:
-
a. a memory having at least one region for storing computer executable program code; and
b. a processor for executing the program code stored in the memory;
c. wherein the program code includes;
i. code to identify the node as being part of a congested span;
ii. code to adjust the output bandwidth of the node as a function of the congestion in the span.
-
-
27. A computer readable medium having computer executable software code stored thereon, the code for managing the access of a node to a bi-directional ring network, the node having a downstream link and an output bandwidth, comprising:
-
a. code to identify the node as being part of a congested span;
b. code to adjust the output bandwidth of the node as a function of the congestion in the span.
-
-
28. A computer data signal embodied in a carrier wave comprising, for managing the access of a node to a bi-directional ring network, the node having a downstream link and an output bandwidth;
-
a. identify the node as being part of a congested span;
b. code to adjust the output bandwidth of the node as a function of the congestion in the span.
-
-
29. An apparatus managing the access of a node to a bi-directional ring network, the node having a downstream link and an output bandwidth, the apparatus comprising:
-
a. an identifier to identify the node as being part of a congested span;
b. an adjuster to adjust the output bandwidth of the node as a function of the congestion in the span. - View Dependent Claims (30)
a. a forwarding filter database for receiving packets from a WAN input port and for forwarding the packets to a WAN output port through a passthrough fifo and a scheduler, or dropping the packet to a WAN egress port through a drop queue;
b. an ingress filter database for receiving packets from a WAN ingress port and for forwarding the packets to a WAN output port through an add queue, a leaky bucket and the scheduler;
c. a tandem rate estimator for calculating a tandem rate by counting packets passing through the passthrough fifo over a first time period;
d. an add rate estimator for calculating an add rate by counting packets passing through the leaky bucket over a second time period;
e. an advertise rate generator for calculating the bandwidth utilization of the WAN output port from the tandem rate and the add rate and for determining an advertise rate as a function of the bandwidth utilization and any DS rate received as a DS rate receive module.
-
Specification
-
- Resources
Litigation Campaign Assessment
Thank you for your request. You will receive a custom alert email when the Litigation Campaign Assessment is available.
×
Litigation Data
-
Current AssigneeRPX Clearinghouse LLC (RPX Corporation)
-
Original AssigneeNortel Networks Limited (Nortel Networks Corporation)
-
InventorsLee, Yang Sup, Peng, Wang-Hsin
-
Primary Examiner(s)CANGIALOSI, SALVATORE A
-
Application NumberUS09/345,453Time in Patent Office1,601 DaysField of Search370/222, 370/229-240, 370/413, 370/468US Class Current370/229CPC Class CodesH04L 12/42 Loop networksH04L 47/10 Flow control; Congestion co...H04L 47/12 Avoiding congestion; Recove...H04L 47/263 Rate modification at the so...Y02D 30/50 in wire-line communication ...
