Equivalent multiple path traffic distribution in communications networks
View Patent ↗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.
1. A method of selecting a path from a plurality of equal cost multiple paths (ECMP) for a datagram egressing a network node of a communications network, said datagram having a header which provides a source and a destination address, the method comprising the steps of:
i). decorrelating individually the source address and the destination address using a node specific parameter to obtain a decorrelated address pair;
ii). applying a randomized selection function to the decorrelated address pair to obtain a path index which is specific to said node; and
iii). selecting said path by means of the path index.
2. The method according to claim 1 , wherein the randomized selection function is a hashing function.
3. The method according to claim 1 , wherein said step i) is accomplished by scrambling the individual bits of at least one of said source address and said destination address.
4. The method according to claim 1 , wherein said step i) is accomplished by shuffling the individual bits of at least one of said source address and said destination address.
5. The method according to claim 1 , wherein said step i) is accomplished by bit rotation of the individual bits of at least one of said source address and said destination address.
6. The method according to claim 5 , wherein the bit rotation of the bits of the source address is performed in a direction that is opposite to a direction of rotation of the bits of the destination address.
7. The method according to claim 6 , 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.
8. The method according to claim 7 , wherein each bit rotation parameter is derived by means of a random number generator.
9. The method according to claim 8 , wherein the random number generator employs a timestamp as a mathematical seed therefore.
10. The method according to claim 9 , wherein the timestamp is obtained upon initialization of the network node.
11. The method according to claim 10 , wherein each bit rotation parameter is re-derived dynamically subsequent to initialization of the network node.
12. The method according to claim 11 , wherein each bit rotation parameter is re-derived dynamically based upon a new timestamp from that obtained upon initialization of the network node.
13. A method as claimed in claim 1 , further comprising changing said node specific parameter at time intervals at predetermined and selectable intervals.
14. A network apparatus for selecting a path from a plurality of equal cost multiple paths (ECMP) for a datagram egressing a network node of a communications network, said datagram having a header which provides a source and a destination address, the apparatus comprising:
a decorrelation device for decorrelating the relative mapping of individual bit values as between the source address and the destination address using a node-specific parameter to obtain a decorrelated address pair; and
a randomized selection device for producing a path index which is is specific to said node.
15. The apparatus according to claim 14 , wherein the randomized selection device executes a hashing function for producing the said path index.
16. The apparatus according to claim 14 , wherein the decorrelation device unit decorrelates by scrambling of said individual bit values of at least one of said source address and said destination address.
17. The apparatus according to claim 14 , wherein the decorrelation device decorrelates by shuffling of said individual bit values of at least one of said source address and said destination address.
18. The apparatus according to claim 14 , wherein the decorrelation device decorrelates by bit rotation of said individual bit values of at least one of said source address and said destination address.
19. The network apparatus according to claim 14 , 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.
20. The apparatus according to claim 14 , wherein the decorrelation device decorrelates by bit rotation of said individual bit values of each of said source address and said destination address.
21. The apparatus according to claim 14 , wherein the bit rotation of the bits 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.
22. The apparatus according to claim 21 , 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.
23. The apparatus according to claim 22 , further comprising two parameter registers for respectively storing each bit rotation parameter.
24. The apparatus according to claim 23 , further comprising a random number generator for deriving each bit rotation parameter.
25. The apparatus according to claim 24 , wherein the random number generator employs a timestamp as a mathematical seed therefore.
26. The apparatus according to claim 25 , wherein the decorrelation units are each implemented as shift registers.
27. The apparatus according to claim 26 , further comprising a clock unit for providing the timestamp to the random number generator.
28. The apparatus according to claim 27 , wherein the timestamp is provided to the random number generator and the bit rotation parameters are derived therefrom upon initialization of the network node.
29. The apparatus according to claim 28 , wherein each bit rotation parameter is re-derived dynamically subsequent to initialization of the network node.
30. The apparatus according to claim 29 , 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.