Packet routing

• US 20030174654A1
• Filed: 12/30/2002
• Published: 09/18/2003
• Est. Priority Date: 07/06/2000
• Status: Active Grant

• Current Assignee: British Telecommunications PLC (BT Group PLC)
• Original Assignee: British Telecommunications PLC (BT Group PLC)
• Inventors: Tateson, Jane E., Marshall, Ian W
• Granted Patent: US 7,508,766 B2
• Time in Patent Office: Days
• 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

The present invention provides a routing protocol that 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 O 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 the steps of:

(a) determining the number of 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;

characterised in that

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 according to claim 1, wherein in step (c) the probability of selecting one of the valid node outputs is inversely proportional to the respective routing factor for that node output.

3. A method of routing a data packet at a network node according to claim 1 or claim 2, wherein the routing factor 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 any preceding claim, wherein the routing factor depends upon the time that the packet would be buffered in the respective input buffer.

5. A method of routing a data packet at a network node according to any preceding claim, wherein the routing factor depends upon the packet transmission time to reach the respective node.

6. A method of routing a data packet at a network node according to any preceding claim, 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 neighbouring node, such that no dynamic information needs to be gathered from or about non-neighbouring nodes.

7. A network node configured, in use, to operate according to the method of any of claims 1 to 6.

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

9. A data carrier containing computer code for loading into a computer for the performance of the method of any of claims 1 to 6.