Packet routing
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
13 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. - View Dependent Claims (3, 4, 5, 6)
-
-
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. - View Dependent Claims (8)
-
-
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. - View Dependent Claims (11)
-
-
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. - View Dependent Claims (13)
-
Specification