Packet routing

• US 7,508,766 B2
• Filed: 07/05/2001
• Issued: 03/24/2009
• Est. Priority Date: 07/06/2000
• Status: Expired due to Fees

• Current Assignee: British Telecommunications PLC (BT Group PLC)
• Original Assignee: British Telecommunications PLC (BT Group PLC)
• Inventors: Marshall, Ian W, Tateson, Jane E
• Primary Examiner(s): PHAN, MAN U
• Application Number:
  US10/312,770
• Publication Number:
  US 20030174654A1
• Time in Patent Office: 2,819 Days
• Field of Search: 370230-254, 370338-389, 370400-469, 709229-241
• US Class Current: 370/238
• 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 routing protocol scatters a stream of packets along a number of parallel paths, the packets being treated independently. The next hop for each packet is chosen probabilistically by comparing the ‘resistance’ of available options. The resistance of a given hop depends upon the time the packet would spend in an output buffer from the current node, the time the packet would spend in the input buffer of the next hop node, the transfer time between the nodes and the number of hops that the packet would take from the current node to the ultimate destination of the packet using the shortest path. This routing protocol is more efficient that shortest path first routing under simulation.

Claims

1. A method of routing a data packet at a network node, the method comprising:

(a) determining valid node outputs to which the packet may be routed;

(b) generating a routing factor for each of the valid node outputs to which the packet may be routed;

(c) randomly selecting one of said valid node outputs, the probability of selecting one of the valid node outputs is inversely proportional to the respective routing factor for that node output;

wherein the probability of selecting one of the valid node outputs is related to the respective routing factor for that node output; and

wherein the routing factor includes a component which depends upon the shortest possible number of hops in which the packet could reach its ultimate destination if it were routed via the respective node output, such that the fewer the number of hops, the more likely it is that the respective output node will be selected.

2. A method of routing a data packet at a network node, the method comprising:

(a) determining valid node outputs to which the packet may be routed;

(b) generating a routing factor for each of the valid node outputs to which the packet may be routed;

(c) randomly selecting one of said valid node outputs,

wherein the probability of selecting one of the valid node outputs is related to the respective routing factor for that node output;

wherein the routing factor includes a component which depends upon the shortest possible number of hops in which the packet could reach its ultimate destination if it were routed via the respective node output, such that the fewer the number of hops, the more likely it is that the respective output node will be selected; and

wherein the routing factor depends only upon information which is directly accessible to the network node at which the method is being performed or is directly accessible to a neighboring node, such that no information needs to be gathered from non-neighboring nodes.

3. A method of routing a data packet at a network node according to claim 2, wherein the routing factor additionally depends upon the time that the packet would be buffered in the respective output buffer.

4. A method of routing a data packet at a network node according to claim 2, wherein each respective node output is connected to a respective node input of a respective associated neighboring node, the respective node input having an associated input buffer, and wherein the routing factor additionally depends upon the time that the packet would be buffered in the respective input buffer of the connected input of the respective neighboring node of the respective node output.

5. A method of routing a data packet at a network node according to claim 2, wherein each respective node output is connected to a respective associated neighboring node, and wherein the routing factor additionally depends upon the packet transmission time to reach the respective neighboring node.

6. A program on a computer readable medium containing computer code which, when executed by a computer, performs the method of claim 2.

7. A network node which routes a data packet, said network node comprising:

(a) means for determining valid node outputs to which the packet may be routed;

(b) means for generating a routing factor for each of the valid node outputs to which the packet may be routed;

(c) means for randomly selecting one of said valid node outputs,

wherein the probability of selecting one of the valid node outputs is related to the respective routing factor for that node output;

wherein the routing factor includes a component which depends upon the shortest possible number of hops in which the packet could reach its ultimate destination if it were routed via the respective node output, such that the fewer the number of hops, the more likely it is that the respective output node will be selected; and

wherein the routing factor depends only upon information which is directly accessible to the network node or is directly accessible to a neighboring node, such that no information needs to be gathered from non-neighboring nodes.

8. A communications network comprising one or more network nodes according to claim 7.

9. A method of routing a data packet at a network node the method comprising:

(a) determining valid node outputs to which the packet may be routed;

(b) generating a routing factor for each of the valid node outputs to which the packet may be routed;

(c) randomly selecting one of said valid node outputs,

wherein the probability of selecting one of the valid node outputs is related to the respective routing factor for that node output;

wherein the routing factor includes a component which depends upon the shortest possible number of hops in which the packet could reach its ultimate destination if it were routed via the respective node output, such that the fewer the number of hops, the more likely it is that the respective output node will be selected;

wherein, each respective node output is connected to a respective node input of a respective associated neighboring node, the respective node input having an associated input buffer, and

wherein the routing factor additionally depends upon one or more of the following additional factors;

(a) the time that the packet would be buffered in a respective output buffer;

(b) the time that the packet would be buffered in the respective input buffer of the connected input of the respective neighboring node of the respective node output; and

(c) a packet transmission time to reach the respective neighboring node.

10. A method of routing a data packet at a network node, said method comprising:

(a) determining valid node outputs to which the packet may be routed;

(b) generating a routing factor for each of the valid node outputs to which the packet may be routed;

(c) randomly selecting one of said valid node outputs,

wherein the probability of selecting one of the valid node outputs is related to the respective routing factor for that node output;

wherein the routing factor includes a component which depends upon the shortest possible number of hops in which the packet could reach its ultimate destination if it were routed via the respective node output, such that the fewer the number of hops, the more likely it is that the respective output node will be selected;

wherein each respective node output is connected to a respective node input of a respective associated neighboring node, the respective node input having an associated input buffer, and wherein the routing factor additionally depends upon one or more of the following additional factors;

(a) the time that the packet would be buffered in a respective output buffer;

(b) the time that the packet would be buffered in the respective input buffer of the connected input of the respective neighboring node of the respective node output; and

(c) a packet transmission time to reach the respective neighboring node; and

wherein the extent to which the routing factor depends on said shortest possible number of hops component relative to each additional factor depends upon a weighting constant, k, and wherein different values of k are used for respectively different packets depending upon a priority level assigned to the respective different packets.

11. A program on a computer readable medium containing computer code which, when executed by a computer, performs the method of claim 10.

12. A network node which routes a data packet, said node comprising:

(a) means for determining valid node outputs to which the packet may be routed;

(b) means for generating a routing factor for each of the valid node outputs to which the packet may be routed;

(c) means for randomly selecting one of said valid node outputs,

wherein the probability of selecting one of the valid node outputs is related to the respective routing factor for that node output;

wherein the routing factor includes a component which depends upon the shortest possible number of hops in which the packet could reach its ultimate destination if it were routed via the respective node output, such that the fewer the number of hops, the more likely it is that the respective output node will be selected; and

wherein the routing factor depends only upon information which is directly accessible to the network node or is directly accessible to a neighboring node, such that no information needs to be gathered from non-neighboring nodes;

wherein each respective node output is connected to a respective node input of a respective associated neighboring node, the respective node input having an associated input buffer, and wherein the routing factor additionally depends upon one or more of the following additional factors;

(a) the time that the packet would be buffered in a respective output buffer;

(b) the time that the packet would be buffered in the respective input buffer of the connected input of the respective neighboring node of the respective node output; and

(c) a packet transmission time to reach the respective neighboring node; and

wherein the extent to which the routing factor depends on said shortest possible number of hops component relative to each additional factor depends upon a weighting constant, k, and wherein different values of k are used for respectively different packets depending upon a priority level assigned to the respective different packets.

13. A communications network comprising one or more network nodes according to claim 12.