Dead reckoning routing of packet data within a network of nodes having generally regular topology
AssigneeBritish Telecommunications public limited company
InventorsDavid Cotter, Martin C Tatham
Life of this patent
Estimating the term…
Abstract
A packet is routed by “dead reckoning” on a network having a generally regular topology. The packet is received at a node where a local routing decision is made. The packet is output in a direction selected according to the routing decision. The packet carries in addition to a destination address a directional flag indicating explicitly the preferred direction of onward travel and the routing decision is made using this flag. Several flags may be used, corresponding to different dimensions of the network.
Claims36
A method of routing a packet carried on a network having a generally regular topology comprising:
- (a) receiving a packet at a node;
- (b) reading a destination address and a directional flag, both of which are carried with the packet, the directional flag indicating explicitly a preferred direction of onward travel for the packet without indicating the magnitude of travel needed to reach the destination;
- (c) terminating the travel of said packet when the node address equals the destination address;
- (d) otherwise making a local routing decision according to the value of the directional flag;
- and
- (e) outputting the packet from the node in a direction selected in accordance with the routing decision.
A node for routing packets carried on a generally regular network, the node comprising:
- a) an input for receiving a packet;
- b) a routing decision unit for making a local routing decision using information carried by the packet, the routing decision unit including means for terminating the travel of said packet when the node address equals the destination address and responsive to a directional flag carried by the packet indicating explicitly a preferred direction of onward travel without indicating the magnitude of travel needed to reach the destination;
- c) a plurality of outputs for directing the packet onto the network in different respective directions;
- and
- d) means for directing a packet to different respective ones of the plurality of outputs depending on an output of the routing decision unit.
A method of routing packet data on a network of nodes when onward routing decisions between intermediate nodes are locally made at each node, said method comprising:
- including with a packet of both a node destination address and directional flag data which does not fully determine a routing path for the packet but which does indicate at least one preferred direction of onward travel for the packet without indicating the magnitude of travel needed to reach the destination;
- and
- making a local onward routing decision at each intermediate node according to the directional flag data or terminating the travel of said packet when the node address equals the destination address.
A node for making local onward routing decisions for packets of data to be carried through network of similar nodes, said node comprising:
- a routing decision unit connected to make onward routing decisions responsive to a directional flag data carried by each incoming packet which identifies a preferred direction of onward travel without firstly identifying an entire routing path for the packet without indicating the magnitude of travel needed to reach the destination;
- a plurality of outputs connected to onwardly directing a packet within the network in different respective directions;
- and
- a switch connected to direct a packet to different respective ones of the outputs depending on an output of the routing decision unit or terminating the travel of said packet when the node address equals the destination address.
Dependencies are inferred from the claim text.