Hashing-based network load balancing

• US 6,888,797 B1
• Filed: 03/25/2000
• Issued: 05/03/2005
• Est. Priority Date: 05/05/1999
• Status: Expired due to Term

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Cao, Zhirou, Wang, Zheng
• Primary Examiner(s): Ton, Dang
• Assistant Examiner(s): Mehra, Inder Pal
• Application Number:
  US09/536,338
• Time in Patent Office: 1,865 Days
• Field of Search: 370/235, 370/253, 370/352, 370/389, 370/392, 370/401, 370/218, 370/349, 370/395.32, 370/237, 370/238, 370/390, 370/402, 370/232, 455/453, 709/105, 713/153, 713/162
• US Class Current: 370/235
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering

Abstract

A hashing-based router and method for network load balancing includes calculating a hash value from header data of incoming data packets and routing incoming packets based on the calculated hash values to permissible output links in desired loading proportions.

Claims

1. A method of traffic splitting of incoming data for network load balancing comprising the steps of:

calculating the value from entirety of header data located within the incoming data by use of a hash function x=K_{modulo M}, where x is said value, M is a preselected modulus value, and K is related to said header data;

determining, in accord with a predetermined algorithm, an output link based on the value and on network load directions; and

coupling the incoming data to the outgoing link.

2. The method of claim 1 wherein the value is determined from a hash function.

3. The method of claim 1 where said header data comprises information from said destination field and data from at least on of the following:

protocol ID, destination port, source address, and source port.

4. The method of claim 1 where said header data comprises data from a protocol ID, a source address, a destination address, a source port, or a destination port.

5. The method of claim 3 where K is obtained by combining selected fields in said header data with an Exclusive OR function.

6. The method of claim 5 where said selected fields are a protocol ID, a source address, a destination address, a source port, and a destination port.

7. The method of claim 5 where said selected fields are a destination field and at least one of the following fields:

protocol ID, destination port, source address, and source port.

8. The method of claim 5 where said selected fields are at least one section of a destination field and data from at least one of the following fields:

on or more sections of a protocol ID, one or more sections of a destination port, one or more sections of a source address, one or more sections of a source port, and other sections of said destination field.

9. The method of claim 5 where said selected fields are one or more segments, but less entirety, of a source address and one or more segments, but less entirety, of a destination address.

10. The method of claim 1 where said step of determining an output link is effected through a look-up table.

11. The method of claim 1 where said step of determining an output link is effected through comparing said value to thresholds.

12. The method of claim 1 where said network loading directions are specified.

13. The method of claim 1 where said network loading directions are supplied pursuant to network load conditions.

14. A router including input links for receiving incoming packets, a routing element for directing incoming packets to outgoing links, and a controller, the improvement comprising:

a many-to-few mapping element for obtaining a value from data contained in headers of incoming packets, applying said value to said controller, and

said controller modified to be responsive to said value and to desired loading of said outgoing links, and to route incoming packets that may be routed to any of a plurality of output links in accordance with said value and said desired loading of said output links.

15. The router of claim 14 wherein said data comprises destination address of incoming packets combined with at least a portion of one or more from the following:

protocol ID, source port, destination address, and destination port.

16. The router of claim 15 where said many-to-few mapping elements computes a hash value from said data.

17. The router of claim 16 where said controller is modified to include a modulo that routes packets based on results of an evaluation of relationship of said value and output links, which evaluation embodies desired network loading.

18. The router of claim 16 where said controller is modified to include a modulo that routes packets based on results of an evaluation of relationship of said value to thresholds.

19. The router of claim 16 where said thresholds are set by desired network loading.