System and method for asymmetrical bandwidth management

• US 20020114334A1
• Filed: 02/21/2001
• Published: 08/22/2002
• Est. Priority Date: 02/21/2001
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Yang, Xuechen
• Granted Patent: US 7,382,727 B2
• Time in Patent Office: Days
• US Class Current: 370/395.1
• CPC Class Codes: H04L 12/2801 Broadband local area networks
• CPC Class Codes: H04L 12/2856 Access arrangements, e.g. Internet access asynchronous transfer mode networks H04L12/5601; broadband local area networks H04L12/2801; optical access or distribution networks H04Q11/0067; access to open networks H04L12/5691; digital subscriber line end-user equipment and bit-level processing of data on a PSTN-based network H04M11/00; home network gateways H04L12/2834; wireless access networks H04W
• CPC Class Codes: H04L 12/2874 Processing of data for distribution to the subscribers
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/2433 Allocation of priorities to traffic types
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]

Abstract

System and method for allocating and managing a shared Internet access channel on an Internet access device. The system and method prioritize data flow in a multi-user, limited bandwidth networking environment by differentiating data types for disparate processing thereof by which a plurality of aggregation classes are hierarchically ordered to include at least one favored class (bandwidth guaranteed) and at least one disfavored class (best effort). Network sessions are aggregated into these classes according to an aggregation policy and bandwidth is asymmetrically allocated to the sessions according to a plurality of algorithms operating in conjunction with the hierarchy.

Claims

1. A method for controlling data flow in a multi-user, limited bandwidth networking environment by differentiating data types for disparate processing thereof, said method comprising steps of:

establishing a plurality of aggregation classes that are hierarchically ordered to include at least one favored class and at least one disfavored class;

aggregating one or more network sessions into at least one of said plurality of aggregation classes according to a pre-defined aggregation policy;

asymmetrically allocating bandwidth to said network sessions according to said hierarchically ordering whereby said allocation occurs in accordance with a first algorithm for said favored class and a second algorithm for said disfavored class, said first algorithm controlling a first arrival rate for a first data packet by controlling a first serving rate for said first data packet in accordance with a first serving/arrival ratio, said second algorithm controlling a second arrival rate for a second data packet by controlling a second serving rate for said second data packet in accordance with a second serving/arrival ratio, said favored class including said first data packet and said disfavored class including said second data packet.

2. The method of claim 1 wherein said first algorithm is implemented using a rate-control schedule algorithm.

3. The method of claim 2 wherein said rate-control algorithm is a Token Bucket algorithm.

4. The method of claim 3 wherein said first serving rate correlates to a token bucket in the Token Bucket Algorithm.

5. The method of claim 3 wherein said Token Bucket algorithm utilizes an amount of tokens that corresponds to a packet size of said first data packet.

6. The method of claim 3 wherein a timer callback generates tokens at a constant token generation rate for said plurality of aggregation classes.

7. The method of claim 1 wherein said bandwidth initially correlates to a WAN link bandwidth.

8. The method of claim 1 wherein said first serving/arrival ratio is pre-determined.

9. The method of claim 8 wherein said first serving/arrival ratio is 0.75.

10. The method of claim 8 wherein said first serving/arrival ratio is 1.0 whereby said first arrival rate corresponds to said first serving rate.

11. The method of claim 1 wherein said second algorithm is implemented using a token bucket to calculate said second serving rate.

12. The method of claim 1 wherein said favored class includes a plurality of favored classes within said favored class.

13. The method of claim 12 wherein said plurality of favored classes includes a bandwidth-guaranteed average rate favored class and a bandwidth-guaranteed minimum rate favored class within said plurality of favored classes.

14. The method of claim 1 wherein said disfavored class includes a plurality of disfavored classes within said disfavored class.

15. The method of claim 14 wherein said second algorithm is implemented using a weighted round-robin scheduler algorithm to allocate bandwidth among said plurality of disfavored classes.

16. The method of claim 14 wherein said second algorithm is implemented using a round-robin scheduler algorithm to allocate bandwidth equally among said plurality of disfavored classes.

17. The method of claim 1 wherein controlling said first serving rate comprises queuing said first data packet for a period of time to inactivate said first data packet within a one of said network sessions, thereby reducing throughput of said network session.

18. The method of claim 1 further comprising a step of:

discarding said first packet at a calculated interval to force said first data packet to be retransmitted within said network session, thereby reducing transmission window size of a one of said network sessions.

19. The method of claim 1 wherein said first algorithm and said second algorithm employ threads for managing said network session.

20. A computer-readable storage medium containing computer executable code for instructing a computer to operate as follows:

establish a plurality of aggregation classes that are hierarchically ordered to include at least one favored class and at least one disfavored class;

aggregate one or more network session into at least one of said plurality of aggregation classes according to a pre-defined aggregation policy;

asymmetrically allocate bandwidth to said network sessions according to said hierarchically ordering whereby said allocation occurs in accordance with a first algorithm for said favored class and a second algorithm for said disfavored class, said first algorithm controlling a first arrival rate for a first data packet by controlling a first serving rate for said first data packet in accordance with a first serving/arrival ratio, said second algorithm controlling a second arrival rate for a second data packet by controlling a second serving rate for said second data packet in accordance with a second serving/arrival ratio, said favored class including said first data packet and said disfavored class including said second data packet.

21. The computer-readable storage medium of claim 20 wherein said executable code instructs said computer to implement said first algorithm using a rate-control schedule algorithm.

22. The computer-readable storage medium of claim 21 wherein said executable code instructs said computer to implement said rate-control schedule algorithm using a Token Bucket algorithm.

23. The computer-readable storage medium of claim 22 wherein said executable code instructs said computer to correlate said first serving rate to a token bucket in the Token Bucket algorithm.

24. The computer-readable storage medium of claim 22 wherein said executable code instructs said computer to utilize an amount of tokens that corresponds to a packet size of said first data packet.

25. The computer-readable storage medium of claim 22 wherein said executable code instructs said computer to generate tokens at a constant token generation rate for said plurality of aggregation classes using a timer callback.

26. The computer-readable storage medium of claim 20 wherein said executable code instructs said compute to correlate initial bandwidth with a WAN link bandwidth.

27. The computer-readable storage medium of claim 20 wherein said executable code instructs said computer to predetermine said first serving/arrival ratio.

28. The computer-readable storage medium of claim 27 wherein said executable code instructs said computer to set said first serving/arrival ratio to 0.75.

29. The computer-readable storage medium of claim 27 wherein said executable code instructs said computer to set said first serving/arrival ratio to 1.0 whereby said first arrival rate corresponds to said first serving rate.

30. The computer-readable storage medium of claim 20 wherein said executable code instructs said computer to implement said second algorithm using a token bucket to calculate said second serving rate.

31. The computer-readable storage medium of claim 20 wherein said executable code instructs said computer to include a plurality of favored classes within said favored class.

32. The computer-readable storage medium of claim 31 wherein said executable code instructs said computer to include a bandwidth-guaranteed average rate favored class and a bandwidth-guaranteed minimum rate favored class within said plurality of favored classes.

33. The computer-readable storage medium of claim 20 wherein said executable code instructs said computer to include a plurality of disfavored classes within said disfavored class.

34. The computer-readable storage medium of claim 33 wherein said executable code instructs said computer to implement said second algorithm using a weighted round-robin scheduler algorithm to allocate bandwidth among said plurality of disfavored classes.

35. The computer-readable storage medium of claim 33 wherein said executable code instructs said computer to implement said second algorithm using a round-robin scheduler algorithm to allocate bandwidth equally among said plurality of disfavored classes.

36. The computer-readable storage medium of claim 20 wherein said executable code instructs said computer to queue said first data packet for a period of time to inactivate said first data packet within said network session, thereby reducing throughput of a one of said network sessions.

37. The computer-readable storage medium of claim 20 wherein said executable code instructs said computer to discard said first packet at a calculated interval to force said first data packet to be retransmitted within a one of said network sessions, thereby reducing transmission window size of said network session.

38. The computer-readable storage medium of claim 20 wherein said executable code instructs said computer to employ threads for managing said network session