Method and system for implementing a fair, high-performance protocol for resilient packet ring networks

• US 20030163593A1
• Filed: 02/25/2003
• Published: 08/28/2003
• Est. Priority Date: 02/25/2002
• Status: Abandoned Application

• Current Assignee: Rice University
• Original Assignee: William March Rice University
• Inventors: Knightly, Edward
• Application Number:
  US10/374,232
• Publication Number:
  US 20030163593A1
• Time in Patent Office: Days
• US Class Current: 709/251
• CPC Class Codes: H04L 12/42 Loop networks
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/762 triggered by the network
• CPC Class Codes: H04L 47/822 Collecting or measuring resource availability data
• CPC Class Codes: H04Q 11/0066 Provisions for optical burst or packet networks
• CPC Class Codes: H04Q 2011/0081 Fault tolerance; Redundancy; Recovery; Reconfigurability
• CPC Class Codes: H04Q 2011/0092 Ring

Abstract

A system and method for dynamic bandwidth allocation is provided. The method provides one or more nodes to compute a simple lower bound of temporally and spatially aggregated virtual time using per-ingress counters of packet (byte) arrivals. Thus, when information is propagated along the ring, each node can remotely approximate the ideal fair rate for its own traffic at each downstream link. In this way, flows on the ring rapidly converge to their ring-wide fair rates while maximizing spatial reuse.

Claims

1. A method for allocating bandwidth in a multi-node packet ring network, comprising the steps of:

at each node of the packet ring network, calculating a proxy to obtain a fair rate, the proxy calculated on the basis of per-ingress measurements of traffic on the packet ring network;

distributing to upstream nodes of the packet ring network, the calculated proxy for the node; and

wherein each upstream node modulates the rate of its traffic according to the bandwidth demands of the downstream nodes of the packet ring network.

2. The method of claim 1, wherein each upstream node modulates the rate of its traffic according to the rate controller associated with each egress node.

3. The method of claim 1, wherein each upstream node modulates the rate of its traffic according to a single rate controller associated with each egress node.

4. The method of claim 1, further comprising the step of adjusting the rate of traffic at a node in response to update information concerning the bandwidth demands of the downstream nodes of the packet ring network.

5. The method of claim 1, wherein the multi-node packet ring network is a Gigabit Ethernet ring.

6. The method of claim 1, wherein the multi-node packet ring network is a 10 Gigabit Ethernet ring.

7. The method of claim 1, wherein the multi-node packet ring network is an Ethernet ring.

8. The method of claim 1, wherein the multi-node packet ring network is an IEEE 802.17 Resilient Packet Ring.

9. A method for determining the rate of traffic flow at a node of a multi-node packet ring network, comprising the steps of:

at each node, determining an aggregated traffic flow associated with the node by calculating a traffic flow rate on the basis of per-ingress measurements of traffic on the packet ring;

communicating the calculated traffic flow to at least one upstream node of the packet ring network; and

adjusting the traffic flow rate at each node on the basis of the downstream traffic demands of the packet ring network.

10. The method of claim 9, wherein the step of adjusting the traffic flow rate comprises the step of adjusting the traffic flow rate in response to an indication that downstream nodes of the packet ring network include at least one data stream originating in the downstream nodes of the packet ring network.

11. The method of claim 9, further comprising the step of periodically adjusting the traffic flow rates for at least one node according to updated information concerning the calculated traffic flow rates for said at least one node.

12. A multi-node packet ring network,

wherein each node of the network calculates a traffic flow rate on the basis of the data stream originating at the node;

and

wherein each node of the network manages its traffic flow rate as a function of the traffic flow rates of downstream nodes in the packet ring network.

13. A method for establish ring ingress aggregated fairness in a multi-node packet ring network, comprising the steps of:

calculating, for at least one node of the packet ring network, a proxy, the proxy calculated on the basis of per-ingress measurements of traffic on the packet ring;

distributing to at least one upstream node of the packet ring network, the calculated proxy for the node; and

wherein each upstream node modulates the rate of its traffic according to the bandwidth demands of the downstream nodes of the packet ring network.

14. The method of claim 13, wherein the multi-node packet ring network is a Gigabit Ethernet ring.

15. The method of claim 13, wherein the multi-node packet ring network is an IEEE 802.17 Resilient Packet Ring.

16. A method for allocating bandwidth in a multi-node packet ring network, comprising the steps of:

constructing, by at least one of said nodes, a proxy to determine a fair rate of a aggregate flow granularity.

17. The method of claim 16, wherein said first granularity is an ingress aggregated flow granularity.

18. The method of claim 16, wherein said proxy provides a lower bound that is temporally aggregated over time for an ingress point.

19. The method of claim 18, wherein said proxy also provides a lower bound that is spatially aggregated over one or more traffic flows for said ingress point.

20. The method of claim 16, wherein said proxy emulates fair queuing.

21. The method of claim 20, wherein said proxy distributes information to at least one other of said nodes.

22. The method of claim 21, further comprising:

receiving by said node, information from one or more other nodes;

computing a fair rate for a downstream node based upon said information.

23. The method of claim 22, further comprising:

rate controlling said node'"'"'s per-destination station traffic to a ring ingress aggregated with spatial reuse (RIAS) fairness rate.

24. The method of claim 20, further comprising:

throttling traffic, by said node, when said information indicates congestion in a downstream node.

25. The method of claim 20, wherein said information is a temporally aggregated summary of conditions.

26. The method of claim 24, wherein said node measures the number of arriving bytes from one or more ingress nodes over a pre-determined time interval.

27. The method of claim 26, further comprising:

computing a fair rate for said pre-determined time interval.

28. The method of claim 27, further comprising:

generating a control message, said control message containing said fair rate for said pre-determined time interval for said node.

29. The method of claim 28, further comprising:

sending said control message to another of said nodes.

30. The method of claim 28, further comprising:

determining a rate controller value.

31. The method of claim 30, wherein said step of determining comprises:

sub-allocating a per-link fair rate to the flow with at least one egress node.

32. The method of claim 16, wherein the multi-node packet ring network is a Gigabit Ethernet ring.

33. The method of claim 16, wherein the multi-node packet ring network is an IEEE 802.17 Resilient Packet Ring.

34. The method of claim 16, wherein said node has at least one rate controller, said rate controller constructed and arranged to receive ingress traffic.

35. The method of claim 34, wherein said node has a fair bandwidth allocator operative with said rate controller, said fair bandwidth allocator constructed and arranged to send a control message.

36. The method of claim 35, wherein said node has a traffic monitor operative with said rate controller and said fair bandwidth allocator.

37. The method of claim 32, wherein said node has at least one station transmit buffers operative with said rate controllers.

38. The method of claim 34, wherein said node has at least one transmit buffer.

39. The method of claim 34, wherein said node has:

at least one station transmit buffers operative with said rate controllers;

at least one transit buffer; and

a scheduler, operative with said station transit buffers and said transmit buffer, said scheduler further operative with said traffic monitor.

40. The method of claim 16, wherein said node comprises:

at least one rate controller, said rate controller constructed and arranged to receive ingress traffic;

a fair bandwidth allocator operative with said rate controller, said fair bandwidth allocator constructed and arranged to send a control message;

a traffic monitor operative with said rate controller and said fair bandwidth allocator;

at least one station transmit buffers operative with said rate controllers;

at least one transit buffers, said transit buffers constructed and arranged to receive transit in signals;

a scheduler operative with said traffic monitor, said scheduler constructed and arranged to receive signals from said station transmit buffers and said transit buffers, said scheduler further constructed and arranged to send transit out signals.

41. The method of claim 16, wherein the multi-node packet ring network is a 10 Gigabit Ethernet ring.

42. The method of claim 16, wherein the multi-node packet ring network is an Ethernet ring.