Robust packet routing over a distributed network containing malicious failures

• US 5,455,865 A
• Filed: 12/20/1993
• Issued: 10/03/1995
• Est. Priority Date: 05/09/1989
• Status: Expired due to Term

• Current Assignee: Enterasys Networks Incorporated (Extreme Networks, Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Perlman, Radia J.
• Primary Examiner(s): Gregory, Bernarr E.
• Application Number:
  US08/170,686
• Time in Patent Office: 652 Days
• Field of Search: 370/60, 370/61, 370/85.1, 370/85.13, 370/85.4, 370/94.1, 370/92, 370/93, 370/94.3, 370/99, 395/200, 380/30, 380/49, 380/50, 380/, 380/23, 380/25
• US Class Current: 713/153
• CPC Class Codes: H04L 2209/60 Digital content management, e.g. content distribution
• CPC Class Codes: H04L 9/3247 involving digital signatures
• CPC Class Codes: H04L 9/40 Network security protocols
• CPC Class Codes: H04Q 3/665 Circuit arrangements therefor

Abstract

A method and system for routing information packets among nodes interconnected by links to form a network, each information packet traversing a path of links and nodes from a source node to a destination node. Information indicating the relationships of nodes and links in the network is assembled in the source node. The entire route from the source node to the destination node is computed prior to sending each information packet and the information packet is routed through the network in accordance with the computed route.

Information is assembled about the local topology of the network including the identities of the neighboring nodes which are connected via links to the local node. The local topology information of each local node is distributed to every other node in the network.

Each node is assigned a unique identifier, a unique public key and an associated private key. The source node'"'"'s assigned identifier, public key and private key are assembled in the source node along with the assigned identifier, public key and associated private key of each of a plurality of other nodes. The computed route is enclosed in a packet. The packet containing the routes is signed and transmitted to each node on the route.

Claims

1. A method for routing a packet from a source node to a destination node in a network of nodes interconnected by links, said source node and said destination node belonging respectively to different subnetworks, each subnetwork having a router, the routers of the subnectworks being organized in hierarchical levels for routing of said packet between said subnetworks, the routers of each of said hierarchical levels being interconnected, comprising

sending packets from said source node to a first router within the subnetwork to which said source node belongs based on a route completely determined at the source node,

determining, in said first router, a complete route to a destination router within one of said hierarchical levels to which said first router and said destination router belong, said route leading toward said destination node,

iterating the preceding step in a manner in which said destination router of each iteration becomes the first router of the next iteration, until the destination router is a router within a subnetwork to which said destination node belongs,

at said destination router within said subnetwork to which said destination node belongs, determining a complete route to said destination node, and

sending said packet from said router along said determined route.

2. The method of claim 1 further comprising

including in said packet sent from said router information specifying said determined route.

3. The method of claim 1 further comprising

sending a route setup packet from said router prior to sending said packet from said router, said route setup packet including information specifying said determined route.

4. The method of claim 1, 2, or 3 wherein said packet is cryptographically authenticated in each said router.

5. Apparatus for routing a packet from a source node to a destination node in a network of nodes interconnected by links, said source node and said destination node belonging respectively to different subnetworks each sub-network having a router, the routers of the subnetworks being organized in hierarchical levels for routing of said packet between said subnetworks, the routers of each of said hierarchical levels being interconnected, comprising

source node circuitry for sending said packet to a first router within the subnetwork to which said source node belongs, based on a route completely determined at the source node,

said router comprising router circuitry for

determining, in said first router, a complete route to a destination router within one of said hierarchical levels to which said first router and said destination router belong, said route leading toward said destination node,

iterating the preceding step in a manner in which said destination router of each iteration becomes the first router of the next iteration, until the destination router is a router within a subnetwork to which said destination node belongs, and

at said destination router within said subnetwork to which said destination node belongs, determining a complete route to said destination node, and

circuitry for sending said packet from said router along said determined route.

6. A method for regulating the delivery of packets from source nodes to destination nodes in a network of nodes interconnected by links, comprising

including sequence data in one or more packets, the sequence data in a packet from a source node indicating the relative age of said packet compared to other packets from the same said source node,

sending each packet from a source node to a destination node via a predetermined route,

in each node, storing information from received packets by allocating predetermined portions of memory to respective other source nodes of the network, each portion for storing information associated with an other source node, and further for storing sequence data from a packet which contained said information, and

regulating the use of each said memory portion of a node by storing received information associated with an other source node only if sequence data from a packet containing said received information is more up-to-date than the sequence in said memory portion allocated to said other source node.

7. The method of claim 6 wherein said information associated with said other source node comprises data packets being delivered from said other source node to destination nodes.

8. The method of claim 6 wherein said information associated with said other source node comprises network information concerning said other source node, said network information being used in delivering packets from said other source node to destination nodes.

9. The method of claim 8 further comprising including in each said packet, information specifying a route through said network from a source node to a destination node.

10. The method of claim 8 further comprising

including in each said packet a sequence value indicating the packet'"'"'s relative position in a time sequence of packets sent from the node which was the source of the packet,

in a node which is along the route from the source node to the destination node, storing in the memory portion allocated to said source node, network information contained in packets received from said source node, and

regulating the storage of network information in a given said memory portion in a manner that favors the storage of more current network information.

11. The method of claim 10 wherein said regulating comprises discarding stored information that is less recent than currently received information.

12. The method of claim 10 further comprising determining the currency of said information based on said sequence value.

13. The method of claim 8 wherein said network information comprises public key information which enables a node receiving a packet from a source node to verify the validity of said packet.

14. Apparatus for regulating the delivery of packets from source nodes to destination nodes in a network of nodes interconnected by links, comprising

source node circuitry for sending each packet from a source node to a destination node via a predetermined route, one or more packets including sequence data, the sequence data in a packet indicating the relative age of said packet compared to other packets from said source node,

each said node comprising circuitry for storing information from received packets by allocating predetermined portions of memory to respective other source nodes of the network, each portion for storing information associated with an other source node, and further for storing sequence data from a packet which contained said information, and

each said node further comprising circuitry for regulating the use of each said memory portion of a node by storing received information associated with an other source node only if sequency data from a packet containing said received information is more up-to-date than the sequence data in said memory portion allocated to said other source node.

15. A method for routing a packet from a source node to a destination node in a network, comprising

forming at the source node a route setup packet including (a) a sequence number indicating the relative position of the route setup packet in a time sequence of packets issued from the source node, (b) a signature which identifies the source node for use in validating the packet, and (c) route information identifying intermediate nodes lying along a route between the source node and the destination node,

sending the route setup packet to the destination node via an intermediate node,

verifying in the intermediate node the validity of the route setup packet based on the signature,

storing in the intermediate node route information from the setup packet, the stored route information identifying a previous node along the route via which packets from the source node are expected to reach the intermediate node on their way to the destination node,

subsequently sending the data packet from the source node via the route to the destination node, and

verifying the data packet at the intermediate node by confirming that it has reached the intermediate node from the expected previous node.

16. Apparatus for routing a packet from a source node to a destination node in a network, comprising

source node circuitry for forming a route setup packet including (a) a sequence number indicating the relative position of the route setup packet in a time sequence of packets issued from the source node, (b) a signature which identifies the source node for use in validating the packet, and (c) route information identifying intermediate nodes lying along a route between the source node and the destination node,

delivery circuitry for sending the route setup packet to the destination node via an intermediate node,

said intermediate node comprising

circuitry for verifying the validity of the route setup packet based on the signature,

circuitry for storing in the intermediate node route information from the setup packet, the stored route information identifying a previous node along the route via which packets from the source node are expected to reach the intermediate node on their way to the destination node, and

circuitry for verifying the data packet at the intermediate node by confirming that it has reached the intermediate node from the expected previous node.

17. A method for routing a packet from a source node to a destination node in a network comprising

sending said packet from said source node toward said destination node along a first route via intermediate nodes,

at the source node, awaiting an acknowledgment by said destination node of receipt of said packet,

eventually, if no acknowledgment is received at the source node, after a timer period determining an alternate route to said destination node which shares no intermediate nodes in common with the first route, and

sending the packet via the alternate route.

19. The method of claim 17 or 18 further comprising

prior to sending said packet from a first router along said first route, determining said first route.

20. The method of claim 19 further comprising

prior to sending said packet from said first router, sending a route setup packet from said source node to said destination node, said route setup packet specifying said first route.

21. The method of claim 19 comprising

including in said packet information describing said first route.

22. The method of claim 19 wherein said first route is cryptographically authenticated at nodes along said first route.

18. A method for routing a packet from a source node to a destination node in a network comprising

sending said packet from said source node toward said destination node along a first route via intermediate nodes,

at the source node awaiting an acknowledgment by said destination node of receipt of said packet,

eventually, if no acknowledgment is received at the source node, after a timer period broadcasting said packet throughout the network.

23. Apparatus for routing a packet from a source node to a destination node in a network, said source node comprising comprising

circuitry for sending said packet from said source node toward said destination node along a first route via intermediate nodes,

circuitry for awaiting an acknowledgment by said destination node of receipt of said packet,

circuitry for determining an alternate route to said destination node which shares no intermediate nodes in common with the first route, if no acknowledgment is eventually received at the source node after a time period, and

circuitry for sending the packet via the alternate route.

24. Apparatus for routing a packet from a source node to a destination node in a network wherein said source node comprises

circuitry for sending said packet from said source node toward said destination node along a first route via intermediate nodes,

circuitry for awaiting an acknowledgment by said destination node of receipt of said packet,

circuitry for broadcasting said packet throughout the network if no acknowledgment is eventually received at the source node after a time period.

25. A method for regulating the delivery of data packets from source nodes to destination nodes in a network of nodes interconnected by links, comprising

sending each packet from a source node to a destination node via a predetermined route including intermediate nodes, said predetermined route including at least one link leading from one of said intermediate nodes, said packets including a first set of said packets originating from a first of said source nodes and routed via said one of said intermediate nodes, and a second set of said packets originating from others of said source nodes, and

limiting the number of packets in said first set that are transmitted sequentially on said link while a packet in said second set is awaiting delivery on said link.

26. The method of claim 25 wherein said allocation is done on a round-robin basis.

27. Apparatus for regulating the delivery of data packets from source nodes to destination nodes in a network of nodes interconnected by links, comprising

circuitry for sending each packet from a source node to a destination node via a predetermined route including intermediate nodes, said predetermined route including at least one link leading from one of said intermediate nodes, said packets including a first set of said packets originating from a first of said source nodes and routed via said one of said intermediate nodes, and a second set of said packets originating from others of said source nodes, and

intermediate node circuitry for limiting the number of packets in said first set that are transmitted sequentially on said link while a packet in said second set is awaiting delivery on said link.

28. A method of regulating the delivery of packets from source nodes via intermediate nodes to destination nodes in a network of nodes interconnected by links, comprising

distributing to nodes in the network, information about the state of links interconnecting nodes in the network, said link state information being distributed to a given node in a network from more than one other trusted node, said other trusted nodes serving as sources of said link state information,

in said given node, determining a route from said given node to a destination node using link state information stored in said given node,

said route determination being made using only link state information received from a single one of the trusted nodes.

29. A method of sending information from a source node to a destination node in a network of nodes interconnected by links, comprising

assigning to each node a public key, a private key, and an identifier, said private key being used by a node which is a source of a packet, to generate a signature based on data to be sent to a destination node via a predetermined route, said public key being used by intermediate nodes along said route to verify the validity of the packet as received from said source node,

assembling, in selected trusted nodes, identifiers and corresponding public keys for nodes in said network,

including in a packet, information identifying the nodes along the route to be traveled by the packet and an identifier of one of said trusted nodes which contains information with respect to the public keys to be used by nodes along the route, the packet not containing any public keys.