Equivalent multiple path traffic distribution in communications networks

• US 20040235480A1
• Filed: 05/02/2003
• Published: 11/25/2004
• Est. Priority Date: 05/02/2003
• Status: Active Grant

• Current Assignee: RPX Corporation
• Original Assignee: Alcatel SA (Nokia Corporation)
• Inventors: Rezaaifar, Ehsan, Bassin, Yuri
• Granted Patent: US 7,346,706 B2
• Time in Patent Office: Days
• US Class Current: 455/445
• 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/24 Multipath

Abstract

A method and associated device for selecting one of a number of equivalent paths in forwarding a network message from a node of a communication network. A source and destination address is provided for the network message. The addresses are formed of individual bit values, and these values have a relative mapping between them. The relative mapping is decorrelated to obtain a decorrelated address pair. A randomized selection function is applied to the decorrelated address pair to produce an index which is derived from the relative sequence of bit values of the decorrelated address paid. The index is then used to select one of the equivalent paths. The associated device provides an address reader, a decorrelation module and a randomized selection module for performing the method previously described.

Claims

1. A method of selecting one of a plurality of equivalent paths for forwarding a network message from a network node of a communications network, the method comprising the steps of:

providing a source address and a destination address for the network message, the source address and the destination address being respectively comprised of individual bit values, the individual bit values having a relative mapping as between the source address and the destination address;

decorrelating the relative mapping of individual bit values as between the source address and the destination address to obtain decorrelated address pair,

applying a randomized selection function to the decorrelated address pair, wherein the randomized selection function thereby produces an index which is derived from a relative sequence of bit values pertaining to the decorrelated address pair; and

selecting said one of the plurality of equivalent paths by means of the index.

2. The method according to claim 1, wherein the said step of decorrelating the relative mapping of individual bit values as between the source address and the destination address comprises modification of a relative sequence of said bit values as between the source address and the destination address.

3. The method according to claim 2, wherein the said step of decorrelating the relative mapping of individual bit values as between the source address and the destination results in preservation of a summed value of each of the individual bit values of the source address and of a summed value of each of the individual bit values of the destination address following said decorrelating.

4. The method according to claim 3, wherein randomized selection function is a hashing function.

5. The method according to claim 2, wherein the said step of decorrelating the relative mapping of individual bit values as between the source address and the destination address is accomplished by scrambling of said individual bit values of at least one of said source address and said destination address.

6. The method according to claim 2, wherein the said step of decorrelating the relative mapping of individual bit values as between the source address and the destination address is accomplished by shuffling of said individual bit values of at least one of said source address and said destination address.

7. The method according to claim 4, wherein the said step of decorrelating the relative mapping of individual bit values as between the source address and the destination address is accomplished by bit rotation of said individual bit values of at least one of said source address and said destination address.

8. The method according to claim 7, wherein the said step of decorrelating the relative mapping of individual bit values as between the source address and the destination address is accomplished by bit rotation of said individual bit values of each of said source address and said destination address.

9. The method according to claim 8, wherein bit rotation of said individual bit values of the source address is performed in a direction of rotation that is opposite to a direction of bit rotation of said individual bit values of the destination address.

10. The method according to claim 9, wherein the bit rotation is performed respectively for a predetermined number of bits in respect of the source address and the destination address, the predetermined number of bits being defined by a bit rotation parameter associated respectively with each of the source address and the destination address.

11. The method according to claim 10, wherein each bit rotation parameter is derived by means of a random number generator.

12. The method according to claim 11, wherein the random number generator employs a timestamp as a mathematical seed therefor.

13. The method according to claim 12, wherein the timestamp is obtained upon initialization of the network node.

14. The method according to claim 13, wherein each bit rotation parameter is re-derived dynamically subsequent to initialization of the network node.

15. The method according to claim 14, wherein each bit rotation parameter is re-derived dynamically based upon a new timestamp from that obtained upon initialization of the network node.

16. The method according to claim 15, wherein the network message is an Internet Protocol packet.

17. The method according to claim 16, wherein the source address and the destination address are each 32 bits in length.

18. The method according to claim 17, wherein the rotation parameters are each 4 bits in length.

19. The method according to claim 18, wherein the predetermined number of bits is in a range of from 1 to 16.

20. The method according to claim 16, wherein the predetermined number of bits is in a range of from 1 to one-half of a total length of the source address.

21. The method according to claim 17, wherein the equivalent paths are equal cost multiple paths.

22. A network apparatus for selecting one of a plurality of equivalent paths for forwarding a network message from a network mode of a communications network, the apparatus comprising:

an address reader for deriving a source address and a destination address of said network message, the source address and the destination address being respectively comprised of individual bit values, the individual bit values having a relative mapping as between the source address and the destination address;

a decorrelation device for decorrelating the relative napping of individual bit values as between the source address and the destination address to obtain a decorrelated address pair; and

a randomized selection device for producing an index which is derived from a relative sequence of bit values pertaining to the decorrelated address pair and for selecting said one of the plurality of equivalent paths by means of the index.

23. The apparatus according to claim 22, wherein the decorrelating unit decorrelates the relative mapping of individual bit values as between the source address and the destination address by modification of a relative sequence of said bit values as between the source address and the destination address.

24. The apparatus according to claim 23, wherein the decorrelation device unit decorrelates the relative mapping of individual bit value as between the source address and the destination while preserving a summed value of each of the individual bit values of the source address and a summed value of each of the individual bit values of the destination address.

25. The apparatus according to claim 24, wherein the randomized selection device executes a hashing function for producing the said index.

26. The apparatus according to claim 24, wherein the decorrelation device unit decorrelates the relative mapping of individual bit values as between the source address and the destination address by scrambling of said individual bit values of at least one of said source address and said destination address.

27. The apparatus according to claim 24, wherein the decorrelation device decorrelates the relative mapping of individual bit values as between the source address and the destination address by shuffling of said individual bit values of at least one of said source address and said destination address.

28. The apparatus according to claim 24, wherein the decorrelation device decorrelates the relative mapping of individual bit values as between the source address and the destination address by bit rotation of said individual bit values of at least one of said source address and said destination address.

29. The network apparatus according to claim 24, further comprising a second decorrelation device, wherein each of the decorrelation devices operates on a respective source address and destination address to obtain the decorrelated address pair.

30. The apparatus according to claim 30, the decorrelation device decorrelates the relative mapping of individual bit values between the source address and the destination address by bit rotation of said individual bit values of each of said source address and said destination address.

31. The apparatus according to claim 30, wherein the bit rotation of said individual bit values of the source address is performed in a direction of rotation that is opposite to a direction of bit rotation of said individual bit values of the destination address.

32. The apparatus according to claim 31, wherein the bit rotation is performed respectively for a predetermined number of bits in respect of each of the source address and the destination address, the predetermined number of bits being defined by a bit rotation parameter associated respectively with each of the source address and the destination address.

33. The apparatus according to claim 32, further comprising two parameter registers for respectively storing each bit rotation parameter.

34. The apparatus according to claim 33, further comprising a random number generator for deriving each bit rotation parameter.

35. The apparatus according to claim 34, wherein the random number generator employs a timestamp as a mathematical seed therefor.

36. The apparatus according to claim 35, wherein the decorrelation units are each implemented as shift registers.

37. The apparatus according to claim 36, further comprising a clock unit for providing the timestamp to the random number generator.

38. The apparatus according to claim 37, wherein the timestamp is provided to the random number generator and the bit rotation parameters are derived therefrom upon initialization of the network node.

39. The apparatus according to claim 38, wherein each bit rotation parameter is re-derived dynamically subsequent to initialization of the network node.

40. The apparatus according to claim 39, wherein each bit rotation parameter is re-derived dynamically based upon a new timestamp from that provided to the random number generator upon initialization of the network node.