Distributed routing table architecture and design

Patent metadata

Field	Value
Publication number	US-9270585-B2
Application number	US-201113012789-A
Country	US
Kind code	B2
Filing date	Jan 24, 2011
Priority date	Apr 13, 2007
Publication date	Feb 23, 2016
Grant date	Feb 23, 2016

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.

First claim

We claim:

1. One or more computer-readable memory comprising computer-executable instructions for maintaining a local portion of a distributed routing table, the computer-executable instructions directed to steps comprising:
determining a first distance according to a network topology between a first node and a node instance representing an endpoint of a distributed routing table (DRT) mesh associated with the distributed routing table;
determining a second distance according to a network topology between a second node and the node instance; and
removing, from the local portion of the distributed routing table associated with the node instance, an entry associated with the second node based only on a comparing of the determined first distance to the determined second distance if the comparing reveals that the first distance is less than the second distance.

2. The computer-readable memory of claim 1 , 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.

3. The computer-readable memory of claim 1 , comprising further computer-executable instructions for removing, from the local portion of the distributed routing table associated with the node instance, the entry associated with the second 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.

4. The computer-readable memory of claim 1 , wherein the local portion of the distributed routing table associated with the node instance already comprised an entry associated with the first node and the entry associated with the second node, wherein the removing is also based on a quantity of entries in the local portion of the distributed routing table exceeding a threshold quantity of entries.

5. The computer-readable memory of claim 1 comprising further computer-executable instructions for receiving a request to add the first node to the local portion of the distributed routing table associated with the node instance, wherein the addition of the first node to the local portion of the distributed routing table is independent of entries associated with the second node.

6. A method of maintaining a local portion of a distributed routing table, the method comprising:
determining a first distance according to a network topology between a first node and a node instance representing an endpoint of a distributed routing table (DRT) mesh associated with the distributed routing table;
determining a second distance according to a network topology between a second node and the node instance; and
removing, from the local portion of the distributed routing table associated with the node instance, an entry associated with the second node based only on a comparing of the determined first distance to the determined second distance if the comparing reveals that the first distance is less than the second distance.

7. The method of claim 6 , 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.

8. The method of claim 6 , further comprising: removing, from the local portion of the distributed routing table associated with the node instance, the entry associated with the second 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.

9. The method of claim 6 , wherein the local portion of the distributed routing table associated with the node instance already comprised an entry associated with the first node and the entry associated with the second node, wherein the removing is also based on a quantity of entries in the local portion of the distributed routing table exceeding a threshold quantity of entries.

10. The method of claim 6 , further comprising: receiving a request to add the first node to the local portion of the distributed routing table associated with the node instance, wherein the addition of the first node to the local portion of the distributed routing table is independent of entries associated with the second node.

11. The method of claim 6 , further comprising:
receiving a message from the first node;
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 a root certificate of the DRT mesh, or that the certificate derives from the root certificate.

12. The method of claim 11 , wherein the received message comprises routing information associated with the first node.

13. The computer-readable memory of claim 1 , comprising further computer-executable instructions for:
receiving a message from the first node;
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 a root certificate of the DRT mesh, or that the certificate derives from the root certificate.

14. The computer-readable memory of claim 13 , wherein the received message comprises routing information associated with the first node.

15. A computing device comprising:
one or more computer-readable memory comprising a local portion of a distributed routing table; and
one or more Central Processing Units (CPUs) executing computer-executable instructions, which, when executed, cause the CPUs to perform steps comprising:
determining a first distance according to a network topology between a first node and the computing device;
determining a second distance according to the network topology between a second node and the computing device; and
removing, from the local portion of the routing table associated with the computing device, an entry associated with the second node based only on a comparing of the determined first distance to the determined second distance if the comparing reveals that the first distance is less than the second distance.

16. The computing device of claim 15 , wherein the determining the first distance comprises determining a first round trip time of a first message between the computing device and the first node, and wherein the determining the second distance comprises determining a second round trip time of a second message between the computing device and the second node.

17. The computing device of claim 15 , wherein the CPUs execute further computer-executable instructions, which, when executed, cause the CPUs to perform further steps comprising removing, from the local portion of the distributed routing table associated with the computing device, the entry associated with the second 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 computing device network address than a second network address associated with the second node.

18. The computing device of claim 15 , wherein the computing de

Assignees

• Manion Todd R
• Ransom Kevin Charles
• Dewey Jeremy L
• Senkeresty Scott A
• Lieuallen Brian R
• De Pritam
• Singhal Sandeep Kishan
• Microsoft Technology Licensing Llc

Inventors

• Manion Todd R
• Ransom Kevin Charles
• Dewey Jeremy L
• Senkeresty Scott A
• Lieuallen Brian R
• De Pritam
• Singhal Sandeep Kishan

Classifications

• H04L45/02

  Topology update or discovery · CPC title

• H04L45/60

  Router architectures · CPC title

• H04L45/54 Primary

  Organization of routing tables · CPC title