Distributed routing table architecture and design

• US 20080253306A1
• Filed: 04/13/2007
• Published: 10/16/2008
• Est. Priority Date: 04/13/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Lieuallen, Brian R., Senkeresty, Scott A., Dewey, Jeremy L., Ransom, Kevin Charles, Singhal, Sandeep Kishan, De, Pritam, Manion, Todd R.
• Granted Patent: US 7,895,345 B2
• Time in Patent Office: Days
• US Class Current: 370/255
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/60 Router architectures

Abstract

A Distributed Routing Table (DRT) mesh can comprise two or more nodes, each of which maintains its own routing table that represents some or all of the overall routing knowledge of the DRT mesh. Each node can be comprised of modular components that can perform various defined functions such that the features and abilities of the node can be customized by an application based on which modular components are instantiated. A routing table management module can maintain individual routing tables at each node, and can ensure that only entries that are close to the node, in a network topology sense, are maintained in the routing table. In addition, a security module can verify received messages based on an agreed-upon root certificate.

Claims

1. One or more computer-readable media comprising computer-executable instructions for creating a node instance, the node instance representing an endpoint of a distributed routing table mesh, the computer-executable instructions directed to steps comprising:

selecting a transport module in accordance with a network transport used for the distributed routing table mesh;

instantiating the transport module;

selecting a bootstrap module in accordance with a predefined mechanism for initiating communication with other nodes of the distributed routing table mesh;

instantiating the bootstrap module;

selecting a security module in accordance with one or more security mechanisms associated with the distributed routing table mesh;

instantiating the security module; and

instantiating a node module for utilizing the transport module, the bootstrap module and the security module to participate in the distributed routing table mesh.

2. The computer-readable media of claim 1, wherein the node module comprises computer-executable instructions for instantiating a routing table management module for managing entries in a routing table associated with the node instance.

3. The computer-readable media of claim 2, wherein the routing table management module filters entries of the routing table associated with the node instance to retain those entries that are closer, according to a network topology, to the node instance than those entries that were not retained.

4. The computer-readable media of claim 1, wherein the one or more security mechanisms associated with the distributed routing table mesh comprise a certificate-based security mechanisms based on at least one root certificate.

5. The computer-readable media of claim 4, wherein the security module comprises computer-executable instructions for verifying a message received from another node instance in the distributed routing table mesh by referencing a certificate associated with the other node instance to ensure that the certificate is chained to the at least one root certificate.

6. The computer-readable media of claim 1, wherein the bootstrap module communicates with other node instances using a peer name resolution protocol specific to the bootstrap module.

7. The computer-readable media of claim 1 comprising further computer-executable instructions for creating a second node instance, the computer-executable instructions performing steps comprising:

instantiating a second node module for utilizing a second transport module, a second bootstrap module and a second security module to participate in the distributed routing table mesh.

8. The computer-readable media of claim 1, wherein the node module comprises computer-executable instructions for:

requesting the bootstrap module to enumerate other nodes of the distributed routing table mesh, requesting the security module to verify the enumerated other nodes provided by the bootstrap module, and requesting a routing table management module to add the verified, enumerated other nodes to a routing table associated with the node instance.

9. The computer-readable media of claim 1, wherein the node module comprises computer-executable instructions for:

requesting a key from the security module to be associated with the node instance, identifying another node associated with another key, the other key being closest in value to the key, and sending a flood message, comprising the key, to the other node.

10. One or more computer-readable media comprising computer-executable instructions for maintaining a routing table associated with a node instance, the node instance representing an endpoint of a distributed routing table mesh, the computer-executable instructions directed to steps comprising:

determining a first distance according to a network topology between a first node associated with a first key and the node instance;

determining a second distance according to the network topology between a second node associated with a second key and the node instance;

maintaining the routing table associated with the node instance to include an entry associated with the first node, the entry comprising the first key and a first routing from the node instance to the first node, if the first distance is less than the second distance; and

maintaining the routing table associated with the node instance to include an entry associated with the second node, the entry comprising the second key and a second routing from the node instance to the second node, if the second distance is less than the first distance.

11. The computer-readable media of claim 10, wherein the determining the first distance comprises determining a first round trip time of a first message between the node instance and the first node, and wherein the determining the second distance comprises determining a second round trip time of a second message between the node instance and the second node.

12. The computer-readable media of claim 10, wherein the maintaining the routing table associated with the node instance comprises maintaining the routing table to include the entry associated with the first node if the first distance and the second distance are equivalent and the first node is associated with a first network address more similar to a node instance network address than a second network address associated with the second node;

and maintaining the routing table to include the entry associated with the second node if the first distance and the second distance are equivalent and the second network address is more similar to the node instance network address than the first network address.

13. The computer-readable media of claim 10, wherein the routing table associated with the node instance already comprised the entry associated with the first node and the entry associated with the second node prior to the determining of the first distance and prior to the determining of the second distance, the maintaining the routing table associated with the node instance further comprising:

removing the entry associated with the second node if the first distance is less than the second distance, and removing the entry associated with the first node if the second distance is less than the first distance.

14. The computer-readable media of claim 10 comprising further computer-executable instructions for receiving a request to add the first node to the routing table associated with the node instance, wherein the routing table associated with the node instance comprises the entry associated with the first node only if the first distance is less than the second distance.

15. The computer-readable media of claim 14, wherein the maintaining the routing table associated with the node instance to include the entry associated with the first node further comprises removing the entry associated with the second node if the first distance is less than the second distance.

16. One or more computer-readable media comprising computer-executable instructions for verifying messages, the computer-executable instructions directed to steps comprising:

receiving a request to verify a message received by a node instance in a distributed routing table mesh from another node in the distributed routing table mesh, wherein the distributed routing table mesh is associated with at least one root certificate;

receiving a certificate associated with the message, the certificate comprising a public key;

verifying that the public key decodes the message; and

verifying that the certificate is either the at least one root certificate, or that the certificate derives from the at least one root certificate.

17. The computer-readable media of claim 16, wherein the computer-executable instructions comprise a security module independently instantiated as part of the node instance.

18. The computer-readable media of claim 16 comprising further computer-executable instructions for receiving a request to generate a key with which to identify the node instance, and generating the key based on security credentials provided by an application associated with the node instance.

19. The computer-readable media of claim 16 comprising further computer-executable instructions for requesting, from the other node, further information in response to receiving the request to verify the message, wherein the receiving the certificate is in response to the request for further information.

20. The computer-readable media of claim 16, wherein the message comprises routing information associated with the other node.