Adaptive inverse multiplexing method and system

• US 6,625,161 B1
• Filed: 12/14/1999
• Issued: 09/23/2003
• Est. Priority Date: 12/14/1999
• Status: Expired due to Fees

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Su, Ching-Fong, Chen, Yao-Min, Taniguchi, Tomohiko
• Primary Examiner(s): VANDERPUYE, KENNETH N
• Application Number:
  US09/461,165
• Time in Patent Office: 1,379 Days
• Field of Search: 370/412, 370/415, 370/428, 370/395.1, 370/389, 370/536, 370/542
• US Class Current: 370/415
• CPC Class Codes: H04L 69/14 Multichannel or multilink protocols
• CPC Class Codes: Y02D 30/50 in wire-line communication networks, e.g. low power modes or reduced link rate

Abstract

A method and system of combining a plurality of parallel communication channels to emulate a single high-bandwidth communication channel. A continuous stream of packets are grouped as traffic aggregates and assigned to queues associated with the plurality of parallel communication channels. The assignment and reassignment of traffic aggregates to the queues is performed dynamically based on measuring the queue load ratios associated with the lengths of the queues for each of the parallel communication channels. Grouping of existing and future packets as traffic aggregates is based on common attributes shared by the packets such as common source and destination IP addresses.

Claims

1. A method of aggregating a plurality of parallel communication channels transmitting packets and each parallel communication channel coupled with an associated queue, the method comprising:

assigning packets to each queue associated with each of a plurality of parallel communication channels;

computing average queue load ratios for each of the plurality of parallel communication channels; and

re-assigning packets which are assigned to a first one of the plurality of parallel communication channels with a maximum average queue load ratio to a second one of the plurality of parallel communication channels with a lowest average queue load ratio.

2. The method of claim 1 wherein assigning packets comprises:

determining a plurality of traffic aggregates; and

assigning each of the plurality of traffic aggregates to each of the plurality of parallel communication channels based on a predetermined map.

3. The method of claim 2 wherein the predetermined map is determined from a look-up table presenting each the plurality of traffic aggregates to each of the plurality of parallel communication channels.

4. The method of claim 3 wherein each of the pluarlity of traffic aggregates is a set of packets having in common at least one pre-determined attribute.

5. The method of claim 4 wherein the at least one pre-determined attribute is a common key determined based on the destination of a packet.

6. The method of claim 5 wherein the common key is a hash value, the hash value being a unique number calculated using a hash function that depends on a destination Internet protocol address of a packet.

7. The method of claim 1 wherein assigning packets comprises:

determining a plurality of traffic aggregates; and

assigning each of the plurality of traffic aggregates to each of the plurality of parallel communication channels randomly.

8. The method of claim 7 wherein each of the plurality of traffic aggregates is a set of packets having in common at least one pre-determined attribute.

9. The method of claim 8 wherein the at least one pre-determined attribute is a common key determined based on a destination of a packet.

10. The method of claim 9 wherein the common key is a hash value, the hash value being a unique number calculated using a hash function that depends on a destination Internet protocol address of a packet.

11. The method of claim 1 wherein computing the average queue load ratio for each of the plurality of communication channels comprises:

measuring an average queue length for each of the parallel communication channels, a queue length being the total bytes contained in packets assigned to a queue;

determining capacity of each of the plurality of the parallel communication channels; and

dividing each of the average queue lengths measured by each of the capacities determined for each of the plurality of parallel communication channels.

12. The method of claim 11 wherein measuring the average queue length of each of the parallel communication channels comprises:

measuring the size of a departing packet, the departing packet being a packet leaving a queue;

determining the length of the queue when the departing packet leaves the queue; and

determining the capacity of one of the plurality of parallel communication channels associated with the queue.

13. The method of claim 12 wherein measuring the average queue length of each of the parallel communication channels further comprises:

summing the product of the size of the departing packet measured by the length of the queue determined when the departing packet leaves the queue for all packets that leave the queue during a pre-determined measurement time interval; and

dividing the summation of the products by the capacity determined of one of the plurality of parallel communication channels associated with the queue and the pre-determined measurement time interval.

14. The method of claim 12 wherein the pre-determined time interval is about a half of a second to one and one half second.

15. The method of claim 1 further comprising continuing to re-assign packets per a pre-determined time interval.

16. The method of claim 12 wherein the pre-determined time interval is one second.

17. An adaptive network system comprising:

a first network;

a plurality of parallel communication channels coupled to the first network;

a second network; and

a network switch coupled to the second network and to the plurality of communication channels, the network switch includes a plurality of queues associated with each of the plurality of parallel communication channels and the network switch is configured to measure an average queue load ratio of each of the plurality of queues and to assign and re-assign packets to each of the plurality of queues based on a maximum, minimum or both maximum and minimum average queue load ratios measured.

18. The adaptive network system of claim 17 wherein the network switch further comprises:

memory containing the plurality of queues; and

processor configured to assign and re-assign packets to each queue and to measure the average queue load ratio of each of the plurality of parallel communication channels.

19. An adaptive network device sending packets through a plurality of parallel communication channels comprising:

a plurality of network interface devices coupled to a plurality of parallel communication channels;

a memory coupled to the plurality of network interface devices, the memory stores a plurality of queues associated with each of the plurality of communication channels; and

a processor coupled to the memory, the processor configured to measure an average queue load ratio of each of the plurality of communication channels and to assign and re-assign packets to each of the plurality of queues based on a maximum, minimum or both maximum and minimum average queue load ratios measured.

20. The adaptive network device of claim 19 wherein the processor is further configured to determine capacities of each of the plurality of communication channels and is configured to assign and re-assign packets by grouping the packets into traffic aggregates and assigning the traffic aggregates to each of the plurality of communication channels based on the maximum, minimum or both maximum and minimum average queue load ratios measured.

21. The adaptive network device of claim 20 wherein each of the traffic aggregates is a set of packets having in common at least one pre-determined attribute.

22. The adaptive network device of claim 21 wherein the at least one pre-determined attribute is a common key determined based on a destination of a packet.

23. The adaptive network device of claim 22 wherein the common key is a hash value, the hash value being a unique number calculated using a hash function that depends on a destination Internet protocol address of a packet.

24. The adaptive network device of claim 23 wherein the processor is configured to measure the average queue load ratio of each of the plurality of communication channels by measuring the average queue length of each of the plurality of communication channels, such that a queue length is a total number of bytes in packets assigned to each of the plurality of queues associated with each of the plurality of communication channels, by determining the capacity of each of the plurality of communication channels of the associated queue, and by dividing the determined average queue lengths by the determined capacity of each of the plurality of communication channels.

25. The adaptive network device of claim 24 wherein the processor is further configured to continue to measure the average queue load ratio of each of the plurality of communication channels for a plurality of predetermined time intervals and the processor re-assigns packets to each queue based on the maximum, minimum or both maximum and minimum average queue load ratios measured for each of the plurality of predetermined time intervals.

26. The adaptive network device of claim 25 wherein each of the plurality of predetermined time intervals is one second in length.

27. An adaptive network device sending packets through a plurality of parallel communication channels comprising:

a plurality of network interface devices coupled to a plurality of communication channels;

a memory coupled to the plurality of network interface devices, the memory stores a plurality of queues associated with each of the plurality of communication channels; and

a processor coupled to the memory, the processor configured to measure an average queue load ratio of each of the plurality of communication channels and to assign a set of the plurality of queues to each of the plurality of communication channels based on a maximum, minimum or both maximum and minimum average queue load ratios measured.

28. The adaptive network device of claim 27 wherein the processor is further configured to assign the packets by grouping the packets into traffic aggregates and assigning the traffic aggregates to each of the plurality of communication channels based on the maximum, minimum or both maximum and minimum average queue load ratio measured of each of the plurality of communication channels.

29. The adaptive network device of claim 28 wherein each of the traffic aggregates is a set of packets having in common at least one pre-determined attribute.

30. The adaptive network device of claim 29 wherein the at least one pre-determined attribute is a common key determined based on a destination of a packet.

31. The adaptive network device of claim 30 wherein the common key is a hash value, the hash value being a unique number calculated using a hash function that depends on a destination Internet protocol address of a packet.

32. The adaptive network device of claim 31 further comprising a queue scheduler coupled to the memory and the plurality of network devices, the queue scheduler determines a service order in which a packet is extracted from the set of the plurality of queues.

33. The adaptive network device of claim 32 wherein the processor is further configured to continue to measure the average queue load ratio of each of the plurality of communication channels for a plurality of predetermined time intervals and re-assigns the set of the plurality of queues to each of the plurality of communication channels based on the maximum, minimum or both maximum and minimum average queue load ratios measured for each of the plurality of predetermined time intervals.

34. The adaptive network device of claim 33 wherein each of the plurality of predetermined time intervals is at least a half a second in length.