Method and apparatus for providing reserved rates to multiple flows on a network interface

• US 6,801,500 B1
• Filed: 05/18/2000
• Issued: 10/05/2004
• Est. Priority Date: 05/18/2000
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Chandran, Kartik
• Primary Examiner(s): QURESHI, AFSAR M
• Application Number:
  US09/574,638
• Time in Patent Office: 1,601 Days
• Field of Search: 370/230.1, 370/235-240, 370/232, 370/233, 370/234, 370/389, 370/235.1, 370/236.1, 370/450, 370/395.21
• US Class Current: 370/230.1
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/5637 Leaky Buckets
• CPC Class Codes: H04L 2012/5681 Buffer or queue management
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/215 using token-bucket

Abstract

The disclosed system provides management of multiple flows at a network device interface such as a router interface to assure maximum usage of the bandwidth available on the physical line while guaranteeing minimum reserved rates for individual flows. It accomplishes this by monitoring usage of a peak rate and a reserved rate for each data flow handled by the interface.

Claims

1. A method for controlling data traffic flow through a network device interface supporting multiple data flows, the method comprising:

determining how much bandwidth is being used at the interface;

for a first data flow through the interface, determining how much bandwidth allotted to the first data flow is being used in comparison to a peak rate and a reserved rate associated with the first data flow; and

depending on how much bandwidth is being used at the interface and on how much bandwidth of the first data flow is being used in comparison to its peak and reserved rates, determining whether to transmit data for the first data flow.

2. The method of claim 1, wherein determining how much bandwidth of the interface is being used comprises determining the bandwidth consumed by each of the multiple data flows.

3. The method of claim 1, wherein determining how much bandwidth of the interface is being used comprises monitoring tokens representing available bits of data, which tokens are replenished with passing time and consumed by data flowing through the interface.

4. The method of claim 1, wherein determining how much bandwidth allotted to the first flow is being used in comparison to the peak rate comprises monitoring tokens representing available bits of data, which tokens are replenished at the peak rate with passing time and consumed by data used for the first flow.

5. The method of claim 1, wherein determining how much bandwidth allotted to the first flow is being used in comparison to the reserved rate comprises monitoring tokens representing available bits of data, which tokens are replenished at the reserved rate with passing time and consumed by data used for the first flow.

6. The method of claim 1, wherein the first data flow is allowed to transmit a packet provided said first data flow has not exceeded its reserved rate.

7. The method of claim 1, wherein a packet for the first data flow is dropped or delayed in a buffer if said first data flow has exceeded its reserved rate and either the first data flow has exceeded its peak rate or the interface has no available bandwidth.

8. The method of claim 1, wherein if it is determined that data for the first flow should not be transmitted, providing the data for the first flow to traffic-shaping logic.

9. The method of claim 8, wherein the traffic-shaping logic determines a traffic-shaping delay.

10. The method of claim 9, wherein the traffic-shaping delay is calculated by subtracting a number of tokens in a token bucket for the first data flow from the size of an incoming packet and dividing this difference by the reserved rate.

11. The method of claim 9, further comprising dropping said incoming packet if the traffic-shaping delay exceeds a maximum shaping delay.

12. The method of claim 9, further comprising placing said packet in a queue for a period of time greater than or equal to its traffic-shaping delay.

13. The method of claim 1, wherein said network device interface is a router interface.

14. An apparatus for controlling data traffic for multiple data flows connected to a network device interface, the apparatus comprising:

one or more processors;

memory coupled to at least one of said one or more processors;

a reserved rate meter for each said flow, said reserved rate meter configured to track the use of reserved bandwidth associated with said data flow;

a peak rate meter for each said data flow, said peak rate meter configured to track the use of peak bandwidth associated with said data flow; and

an interface meter configured to track the use of bandwidth of said network device interface;

wherein at least one said processor is configured or designed to adjust said meters based on the amount of data transmitted and refresh said meters based on the reserved and peak rates for each flow and the bandwidth for the network device interface.

15. The apparatus of claim 14 wherein a flow is allowed to transmit a packet provided said reserved rate meter indicates that said flow has not exceeded its reserved rate and either the peak rate meter indicates that the flow has not exceeded its peak rate or said interface meter shows available network device bandwidth.

16. The apparatus of claim 15 wherein said packet is dropped or delayed in a buffer if the reserved rate meter indicates the reserved rate has been exceeded and either the interface meter shows no remaining network device bandwidth or the peak rate meter shows the peak rate has been exceeded.

17. The apparatus of claim 16 wherein a traffic-shaping delay is calculated by subtracting the remaining reserved rate bandwidth from the packet size and dividing this number by the reserved rate for the associated flow.

18. The apparatus of claim 16 wherein a traffic-shaping delay is calculated by subtracting the remaining peak rate bandwidth from the packet size and dividing this number by the reserved rate for the associated flow.

19. The apparatus of claim 16 wherein said network device interface is a router interface.

20. An apparatus for controlling data traffic for multiple data flows at a network interface, the apparatus comprising:

one or more processors;

memory coupled to at least one of said one or more processors;

a reserved rate meter for each said flow, said meter configured to track the use of reserved bandwidth associated with said data flow;

a peak rate meter for each said data flow, said meter configured to track the use of peak bandwidth associated with said data flow; and

an interface meter configured to track the use of bandwidth of said network device interface;

wherein at least one of said processors is configured or designed to determine whether to transmit data for said data flow depending on the interface meter level, the reserved rate meter level, and the peak rate meter level.

21. A method for controlling data traffic flow through a network device interface comprising:

providing an interface token bucket associated with said network device interface;

providing peak and reserved token buckets for each flow connected to said network device interface;

refreshing the interface, reserved, and peak token buckets based on the network device bandwidth and the peak and reserved rates for said flows; and

subtracting the number of tokens equivalent to the size of a packet from the interface, peak, and reserved token buckets associated with a packet enqueued to output when the associated reserved token bucket is not empty or both the interface and associated peak token buckets are not empty.

22. An apparatus for supporting multiple data flows and controlling at least a first data traffic flow, the apparatus comprising:

a network device interface; and

one or more processors designed or configured to determine how much bandwidth of the interface is being used, and how much bandwidth allotted to the first data flow is being used in comparison to a peak rate and a reserved rate, and depending on how much bandwidth of the interface is being used and on how much bandwidth of the first data flow is being used in comparison to its peak and reserved rates, determining whether to transmit data for the first flow.

23. The apparatus of claim 22, wherein said network device interface is a router interface.

24. The apparatus of claim 22, wherein the one or more processors determine how much bandwidth of the interface is being used by determining the bandwidth consumed by each of the multiple data flows.

25. The apparatus of claim 22, wherein the one or more processors allow the interface to transmit a packet for the first data flow provided said first data flow has not exceeded its reserved rate.

26. The apparatus of claim 22, wherein the one or more processors drop or delay transmission of a packet for first data flow if the first data flow has exceeded its reserved rate and either the first data flow has exceeded its peak rate or the interface has no available bandwidth.

27. The apparatus of claim 22, wherein if the one or more processors determine that data for the first flow should not be transmitted, providing the data for the first flow to traffic-shaping logic executed on the one or more processors.

28. The apparatus of claim 27, wherein the traffic-shaping logic determines a traffic-shaping delay.

29. A computer program product comprising a machine readable medium on which is provided program instructions for controlling data traffic flow through a network device interface supporting multiple data flows, the instructions encoding a method comprising:

determining how much bandwidth of the interface is being used;

for a first data flow through the interface, determining how much bandwidth allotted to the first flow is being used in comparison to a peak rate and a reserved rate for the first data flow; and

depending on how much bandwidth of the interface is being used and on how much bandwidth of the first data flow is being used in comparison to its peak and reserved rates, determining whether to transmit data for the first flow.

30. The computer program product of claim 29, wherein instructions for determining how much bandwidth of the interface is being used comprise instructions for determining the bandwidth consumed by each of the multiple data flows.

31. The computer program product of claim 29, wherein instructions for determining how much bandwidth of the interface is being used include instructions for monitoring tokens representing available bits of data, which tokens are replenished with passing time and consumed by data flowing through the interface.

32. The computer program product of claim 29, wherein instructions for determining how much bandwidth allotted to the first flow is being used in comparison to the peak rate include instructions for monitoring tokens representing available bits of data, which tokens are replenished at the peak rate with passing time and consumed by data used for the first flow.

33. The computer program product of claim 29, wherein instructions for determining how much bandwidth allotted to the first flow is being used in comparison to the reserved rate includes instructions for monitoring tokens representing available bits of data, which tokens are replenished at the reserved rate with passing time and consumed by data used for the first flow.

34. The computer program product of claim 29, wherein the first data flow is allowed to transmit a packet provided said first data flow has not exceeded its reserved rate.

35. The computer program product of claim 29, wherein a packet for the first data flow is dropped or delayed in a buffer if said first data flow has exceeded its reserved rate and either the first data flow has exceeded its peak rate or the interface has no available bandwidth.

36. The computer program product of claim 29, wherein if it is determined that data for the first flow should not be transmitted, providing the data for the first flow to traffic-shaping logic.

37. The computer program product of claim 36, wherein the traffic-shaping logic determines a traffic-shaping delay.

38. An apparatus for controlling data traffic for multiple data flows connected to a network device interface, the apparatus comprising:

means for processing information about said multiple flows;

means for storing at least one of said data traffic and said information, wherein the means for storing is coupled to the means for processing;

means for metering a reserved rate for each said flow, said means for metering the reserved rate configured to track the use of reserved bandwidth associated with said data flow;

means for metering a peak rate for each said data flow, said means for metering the peak rate configured to track the use of peak bandwidth associated with said data flow; and

for tracking the use of bandwidth of said network device interface;

wherein means for processing (i) adjusts the means for metering the reserved rate, the means for metering the peak rate, and the interface metering means based on the amount of data transmitted, (ii) refreshes said means for metering the reserved rate based on the reserved rate for each flow, (iii) refreshes the means for metering the peak rate based on the peak rate for each flow, and (iv) refreshes the interface metering means based on the bandwidth for the network device interface.

39. An apparatus for supporting multiple data flows, the apparatus comprising:

means for determining the amount of bandwidth being used at an interface;

means for determining the amount of bandwidth being used for a first data flow at the interface;

means for comparing the amount of bandwidth being used for the first data flow with a peak rate and a reserved rate associated with the first data flow; and

means for deternining whether to transmit data for the first data flow depending on the amount of bandwidth being used at the interface and the amount of bandwidth being used for the first data flow in comparison to the peak rate and the reserve rate.