Method and apparatus for distributed bandwidth allocation for a bi-directional ring media with spatial and local reuse

• US 6,314,110 B1
• Filed: 03/06/1998
• Issued: 11/06/2001
• Est. Priority Date: 03/06/1998
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Broberg, Robert M., Bates, Anthony J., Tsiang, David J., Chin, Hon Wah, Wilford, Bruce A.
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): PHAM, BRENDA H
• Application Number:
  US09/036,539
• Time in Patent Office: 1,341 Days
• Field of Search: 370/329, 370/341, 370/381, 370/376, 370/358, 370/377, 370/395, 370/400, 370/468, 370/222, 370/229, 370/235, 370/253, 370/258, 370/404, 370/460, 370/543
• US Class Current: 370/468
• CPC Class Codes: H04L 12/433 with asynchronous transmission, e.g. token ring, register insertion
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/13 in a LAN segment, e.g. ring or bus

Abstract

A system and method for locally determining a fair allocated bandwidth for a network node configured to send and receive packets in an upstream direction and a downstream direction is disclosed. A local allocated bandwidth is allocated for locally generated network packets sent in the downstream direction. A minimum downstream available network bandwidth is determined from information received in the upstream direction. The local allocated bandwidth is adjusted based on the minimum downstream available network bandwidth and the local allocated bandwidth is used to govern whether a class of locally generated network packets are sent in the downstream direction.

Claims

1. A method of locally determining a fair allocated bandwidth for a network node configured to send and receive packets in an upstream direction and a downstream direction comprising:

allocating a local allocated bandwidth for locally generated network packets sent in the downstream direction;

determining from information received in the upstream direction a minimum downstream available network bandwidth;

adjusting the local allocated bandwidth based on the minimum downstream available network bandwidth and periodically increasing the local allocated bandwidth toward a maximum local allocated bandwidth; and

using the local allocated bandwidth to govern whether a class of locally generated network packets are sent in the downstream direction.

2. A method of locally determining a fair allocated bandwidth for a network node as recited in claim 1 wherein periodically increasing the local allocated bandwidth toward a maximum local allocated bandwidth further includes:

periodically adding a fraction of the difference between the local allocated bandwidth and the maximum local allocated bandwidth to the local allocated bandwidth.

3. A method of locally determining a fair allocated bandwidth for a network node as recited in claim 1 wherein adjusting the locally allocated bandwidth based on the minimum downstream available network bandwidth further includes:

reducing the local allocated bandwidth when the local allocated bandwidth is greater than the minimum downstream available network bandwidth.

4. A method of locally determining a fair allocated bandwidth for a network node as recited in claim 1 wherein adjusting the locally allocated bandwidth based on the minimum downstream available network bandwidth further includes:

reducing the local allocated bandwidth to the average of the local allocated bandwidth and the minimum downstream available network bandwidth when the local allocated bandwidth is greater than the minimum downstream available network bandwidths.

5. A method of locally determining a fair allocated bandwidth for a network node as recited in claim 1 wherein adjusting the locally allocated bandwidth based on the minimum downstream available network bandwidth further includes:

increasing the local allocated bandwidth asymptotically toward a maximum local allocated bandwidth when the local allocated bandwidth is less than the minimum downstream available network bandwidth.

6. A method of locally determining a fair allocated bandwidth for a network node as recited in claim 1 wherein adjusting the locally allocated bandwidth based on the minimum downstream available network bandwidth further includes:

increasing the local allocated bandwidth asymptotically toward the minimum downstream available network bandwidth when the local allocated bandwidth is less than the minimum downstream available network bandwidth.

7. A method of locally determining a fair allocated bandwidth for a network node as recited in claim 1 wherein using the local allocated bandwidth to govern whether locally generated network packets are sent in the downstream direction further includes:

determining a local network usage in the downstream direction;

comparing the local network usage in the downstream direction to the local allocated bandwidth; and

preventing the sending of a class of locally generated network packets in the downstream direction if the local network usage in the downstream direction exceeds the local allocated bandwidth.

8. A method of locally determining a fair allocated bandwidth for a network node as recited in claim 7 wherein the class of locally generated network packets includes low priority packets.

9. A method of locally determining a fair allocated bandwidth for a network node as recited in claim 7 wherein high priority packets are sent in the downstream direction even when the local network usage in the downstream direction exceeds the local allocated bandwidth.

10. A method of locally determining a fair allocated bandwidth for a network node as recited in claim 7 wherein determining a local network usage in the downstream direction further includes:

creating a locally generated traffic count by accumulating the number of bytes in locally generated network packets that are sent in the downstream direction; and

periodically reducing the locally generated traffic count.

11. A method of locally determining a fair allocated bandwidth for a network node as recited in claim 10 wherein periodically reducing the locally generated traffic count includes:

periodically subtracting a fraction of the locally generated traffic count from the locally generated traffic count.

12. A method of locally determining a fair allocated bandwidth for a network node as recited in claim 1 further including:

determining a local network usage in the downstream direction;

determining an amount of forwarded network traffic in the downstream direction;

comparing the local network usage in the downstream direction to the amount of forwarded network traffic in the downstream direction; and

preventing the sending of minimum downstream available network bandwidth information in the upstream direction if the local network usage in the downstream direction exceeds the amount of forwarded network traffic in the downstream direction.

13. A method of locally determining a fair allocated bandwidth for a network node as recited in claim 12 wherein determining a local network usage in the downstream direction further includes:

creating a locally generated traffic count by accumulating the number of bytes in locally generated network packets that are sent in the downstream direction; and

periodically reducing the locally generated traffic count.

14. A method of locally determining a fair allocated bandwidth for a network node as recited in claim 13 wherein periodically reducing the locally generated traffic count includes:

periodically subtracting a fraction of the locally generated traffic count from the locally generated traffic count.

15. A method of locally determining a fair allocated bandwidth for a network node as recited in claim 12 wherein an amount of forwarded network traffic in the downstream direction further includes:

creating downstream forwarded network traffic count by accumulating the number of bytes in downstream forwarded network packets that are sent in the downstream direction; and

periodically reducing the downstream forwarded network traffic count.

16. A method of locally determining a fair allocated bandwidth for a network node as recited in claim 15 wherein periodically reducing the downstream forwarded network traffic count includes periodically subtracting a fraction of the downstream forwarded network traffic count from the downstream forwarded network traffic count.

17. A method of locally determining a fair allocated bandwidth for a network node as recited in claim 1 further including:

sending minimum downstream available network bandwidth information in the upstream direction if the local network usage in the downstream direction is less than the amount of forwarded network traffic in the downstream direction.

18. A method of locally determining a fair allocated bandwidth for a network node as recited in claim 17 wherein the minimum downstream available network bandwidth information is determined by taking the lesser of the local network usage in the downstream direction and the minimum downstream available network bandwidth.

19. A method of locally determining a fair allocated bandwidth for a network node as recited in claim 18 wherein the minimum downstream available network bandwidth information is determined by taking the lessor of the local network usage in the downstream direction and the minimum downstream available network bandwidth plus a small constant.

20. A method of locally determining a fair allocated bandwidth for a network node as recited in claim 1 wherein the network node is a network node in a bi-directional ring network.

21. A method of locally determining a fair allocated bandwidth for a network node as recited in claim 1 wherein the network node is a network node in a linear network.

22. A statistically multiplexed network node with fairly allocated bandwidth comprising:

a network interface configured to send and receive packets in an upstream direction and a downstream direction; and

a packet controller configured to allocate a bandwidth for locally generated network packets sent in the downstream direction wherein the packet controller determines a minimum downstream available network bandwidth available in the downstream direction from information received in the upstream direction and adjusts the local allocated bandwidth based on the minimum downstream available network bandwidth, periodically increasing the local allocated bandwidth toward a maximum local allocated bandwidth and wherein the packet controller uses the local allocated bandwidth to govern whether a class of locally generated network packets are sent in the downstream direction.

25. The statistically multiplexed network node as recited in claim 22 wherein periodically increasing the local allocated bandwidth toward a maximum local allocated bandwidth further includes:

periodically adding a fraction of the difference between the local allocated bandwidth and the maximum local allocated bandwidth to the local allocated bandwidth.

26. The statistically multiplexed network node as recited in claim 22 wherein adjusting the locally allocated bandwidth based on the minimum downstream available network bandwidth further includes:

reducing the local allocated bandwidth when the local allocated bandwidth is greater than the minimum downstream available network bandwidth.

27. The statistically multiplexed network node as recited in claim 22 wherein adjusting the locally allocated bandwidth based on the minimum downstream available network bandwidth further includes:

reducing the local allocated bandwidth to the average of the local allocated bandwidth and the minimum downstream available network bandwidth when the local allocated bandwidth is greater than the minimum downstream available network bandwidth.

28. The statistically multiplexed network node as recited in claim 22 wherein adjusting the locally allocated bandwidth based on the minimum downstream available network bandwidth further includes:

increasing the local allocated bandwidth asymptotically toward a maximum local allocated bandwidth when the local allocated bandwidth is less than the minimum downstream available network bandwidth.

29. The statistically multiplexed network node as recited in claim 22 wherein adjusting the locally allocated bandwidth based on the minimum downstream available network bandwidth further includes:

increasing the local allocated bandwidth asymptotically toward the minimum downstream available network bandwidth when the local allocated bandwidth is less than the minimum downstream available network bandwidth.

30. The statistically multiplexed network node as recited in claim 22 wherein using the local allocated bandwidth to govern whether locally generated network packets are sent in the downstream direction further includes:

determining a local network usage in the downstream direction;

comparing the local network usage in the downstream direction to the local allocated bandwidth; and

preventing the sending of a class of locally generated network packets in the downstream direction if the local network usage in the downstream direction exceeds the local allocated bandwidth.

23. A method of statistically multiplexing network use by nodes in a bi-directional ring network having an upstream direction and a downstream direction comprising:

determining at each node a local allocated bandwidth for locally generated network packets sent in the downstream direction;

sending downstream available network bandwidth information from each node in the upstream direction;

adjusting the local allocated bandwidth at each node based on the minimum downstream available network bandwidth information received at each node and periodically increasing the local allocated bandwidth toward a maximum local allocated bandwidth; and

using the local allocated bandwidth at each node to govern whether a class of locally generated network packets are sent in the downstream direction.

24. A method of locally determining a fair allocated bandwidth for a network node of a unidirectional ring network wherein the network node is configured to send packets in a downstream direction and to receive packets from an upstream direction, comprising:

forwarding traffic received from the upstream direction to the downstream direction;

determining a local allocated bandwidth for locally generated network packets sent in the downstream direction based on a notification received from the upstream direction;

combining local usage with information from the notification received from the upstream direction to generate a downstream notification;

sending the downstream notification in the downstream direction;

determining local usage of the network; and

restricting local usage based on the notification received from the upstream direction.

31. A system of locally determining a fair allocated bandwidth for a network node configured to send and receive packets in an upstream direction and a downstream direction comprising:

means for allocating a local allocated bandwidth for locally generated network packets sent in the downstream direction;

means for determining from information received in the upstream direction a minimum downstream available network bandwidth;

means for adjusting the local allocated bandwidth based on the minimum downstream available network bandwidth and periodically increasing the local allocated bandwidth toward a maximum local allocated bandwidth; and

means for using the local allocated bandwidth to govern whether a class of locally generated network packets are sent in the downstream direction.

32. A computer program product for locally determining a fair allocated bandwidth for a network node configured to send and receive packets in an upstream direction and a downstream direction, the computer program product being embodied in a computer readable medium and comprising computer instructions for:

allocating a local allocated bandwidth for locally generated network packets sent in the downstream direction;

determining from information received in the upstream direction a minimum downstream available network bandwidth;

adjusting the local allocated bandwidth based on the minimum downstream available network bandwidth and periodically increasing the local allocated bandwidth toward a maximum local allocated bandwidth; and

using the local allocated bandwidth to govern whether a class of locally generated network packets are sent in the downstream direction.