Distributed storage of routing information in a link state protocol controlled network
View Patent ↗A distributed hash table is implemented to store routing information on a network. Node IDs exchanged in connection with implementation of a link state routing protocol are used as keys in the distributed hash table, and routes are stored at one or more nodes on the network. When a route is learned, the route is processed against the set of keys to determine which nodes should store the route. When a route is needed, the route is processed against the set of keys to determine which nodes should have the route information. The manner in which the route is processed against the set of keys is the same in both instances, so that the DHT may be used to store and retrieve route information on the network.
1. A method of forwarding packets in a packet network having route information stored in a distributed hash table (DHT) distributed across nodes of the network, the method comprising:
performing a hash on an address to determine nodes in the DHT to query for a route;
transmitting a route request to the determined nodes;
receiving at least one route response from at least one of the determined nodes;
determining a route from the at least one route response; and
forwarding packets having the address as a destination address according to the determined route;
wherein:
each node is associated with a respective node identifier;
performing a hash on the address provides a route identifier; and
nodes in the DHT to query for a route are determined by comparing the route identifier with node identifiers; and
wherein the node identifiers are stored in a membership table.
2. The method of claim 1 , wherein:
the route identifier is compared to node identifiers to determine a set of nodes having node identifiers deemed closest to the route identifier; and
the route request is transmitted to the set of nodes having node identifiers deemed closest to the route identifier.
3. The method of claim 2 , wherein the route identifier is compared to node identifiers using an XOR-distance process.
4. The method of claim 1 , further comprising:
detecting a network topology change; and
determining routes affected by the network topology change; and
for each route affected by the network topology change:
performing a hash on an address to determine nodes in the DHT to query for a route;
transmitting a route request to the determined nodes;
receiving at least one route response from at least one of the determined nodes;
determining a route update from the at least one route response; and
storing the route update in a local forwarding table.
5. The method of claim 4 , further comprising:
receiving a packet having a destination address;
determining a route from the local forwarding table based on the destination address; and
forwarding the packet according to the route determined from the local forwarding table.
6. The method of claim 1 , wherein the address is a media access control (MAC) address.
7. The method of claim 1 , wherein the address is a customer MAC (C-MAC) address, and the DHT associates C-MAC addresses with provider MAC (P-MAC) addresses.
8. The method of claim 1 , wherein the address is one of an IP address, a Network Application Services Platform (NSAP) address, and an MPLS label.
9. A routing apparatus for routing a packet in a packet network having routing information stored in a distributed hash table (DHT) distributed across nodes of the network, the apparatus comprising:
at least one processor; and
at least one non-transitory storage medium storing instructions for execution by the processor, the instructions comprising instructions executable by the processor:
to perform a hash on an address to determine nodes in the DHT to query for a route;
to transmit a route request to the determined nodes;
to receive at least one route response from at least one of the determined nodes;
to determine a route from the at least one route response; and
to forward packets having the address as a destination address according to the determined route;
wherein:
each node is associated with a respective node identifier;
performing a hash on the address provides a route identifier; and
the instructions executable to determine nodes in the DHT to query for a route comprise instructions executable to compare the route identifier with node identifiers; and
wherein the node identifiers are stored in a membership table.
10. The apparatus of claim 9 , wherein:
the instructions executable to compare the route identifier with node identifiers comprise instructions executable to compare the route identifier to node identifiers to determine a set of nodes having node identifiers deemed closest to the route identifier; and
the instructions executable to transmit the route request comprise instructions executable to transmit the route request to the set of nodes having node identifiers deemed closest to the route identifier.
11. The apparatus of claim 10 , wherein the instructions executable to compare the route identifier to node identifiers implement an XOR-distance process.
12. The apparatus of claim 9 , wherein the instructions further comprise instructions executable:
to detect a network topology change; and
to determine routes affected by the network topology change; and
for each route affected by the network topology change:
to perform a hash on an address to determine nodes in the DHT to query for a route;
to transmit a route request to the determined nodes;
to receive at least one route response from at least one of the determined nodes;
to determine a route update from the at least one route response; and
to store the route update in a local forwarding table.
13. The apparatus of claim 12 , wherein the instructions further comprise instructions executable:
to receive a packet having a destination address;
to determine a route from the local forwarding table based on the destination address; and
to forward the packet according to the route determined from the local forwarding table.
14. The apparatus of claim 9 , wherein the address is a media access control (MAC) address.
15. The apparatus of claim 9 , wherein the address is a customer MAC (C-MAC) address, and the DHT associates C-MAC addresses with provider MAC (P-MAC) addresses.
16. The apparatus of claim 9 , wherein the address is one of an IP address, a Network Application Services Platform (NSAP) address, and an MPLS label.
17. A method of forwarding packets in a packet network having route information stored in a distributed hash table (DHT) distributed across nodes of the network, the method comprising:
performing a hash on an address to determine nodes in the DHT to query for a route;
transmitting a route request to the determined nodes;
receiving at least one route response from at least one of the determined nodes;
determining a route from the at least one route response; and
forwarding packets having the address as a destination address according to the determined route;
wherein:
each node is associated with a respective node identifier;
performing a hash on the address provides a route identifier; and
nodes in the DHT to query for a route are determined by comparing the route identifier with node identifiers; and
wherein:
the route identifier is compared to node identifiers to determine a set of nodes having node identifiers deemed closest to the route identifier; and
the route request is transmitted to the set of nodes having node identifiers deemed closest to the route identifier.
18. The method of claim 17 , wherein the route identifier is compared to node identifiers using an XOR-distance process.
19. The method of claim 17 , further comprising:
detecting a network topology change; and
determining routes affected by the network topology change; and
for each route affected by the network topology change:
performing a hash on an address to determine nodes in the DHT to query for a route;
transmitting a route request to the determined nodes;
receiving at least one route response from at least one of the determined nodes;
determining a route update from the at least one route response; and
storing the route update in a local forwarding table.
20. The method of claim 19 , further comprising:
receiving a packet having a destination address;
determining a route from the local forwarding table based on the destination address; and
forwarding the packet according to the route determined from the local forwarding table.
21. The method of claim 17 , wherein the address is a media access control (MAC) address.
22. The method of claim 17 , wherein the address is a customer MAC (C-MAC) address, and the DHT associates C-MAC addresses with provider MAC (P-MAC) addresses.
23. The method of claim 17 , wherein the address is one of an IP address, a Network Application Services Platform (NSAP) address, and an MPLS label.
24. A routing apparatus for routing a packet in a packet network having routing information stored in a distributed hash table (DHT) distributed across nodes of the network, the apparatus comprising:
at least one processor; and
at least one non-transitory storage medium storing instructions for execution by the processor, the instructions comprising instructions executable by the processor:
to perform a hash on an address to determine nodes in the DHT to query for a route;
to transmit a route request to the determined nodes;
to receive at least one route response from at least one of the determined nodes;
to determine a route from the at least one route response; and
to forward packets having the address as a destination address according to the determined route;
wherein:
each node is associated with a respective node identifier;
performing a hash on the address provides a route identifier; and
the instructions executable to determine nodes in the DHT to query for a route comprise instructions executable to compare the route identifier with node identifiers; and
wherein:
the instructions executable to compare the route identifier with node identifiers comprise instructions executable to compare the route identifier to node identifiers to determine a set of nodes having node identifiers deemed closest to the route identifier; and
the instructions executable to transmit the route request comprise instructions executable to transmit the route request to the set of nodes having node identifiers deemed closest to the route identifier.
25. The apparatus of claim 24 , wherein the instructions executable to compare the route identifier to node identifiers implement an XOR-distance process.
26. The apparatus of claim 24 , wherein the instructions further comprise instructions executable:
to detect a network topology change; and
to determine routes affected by the network topology change; and
for each route affected by the network topology change:
to perform a hash on an address to determine nodes in the DHT to query for a route;
to transmit a route request to the determined nodes;
to receive at least one route response from at least one of the determined nodes;
to determine a route update from the at least one route response; and
to store the route update in a local forwarding table.
27. The apparatus of claim 26 , wherein the instructions further comprise instructions executable:
to receive a packet having a destination address;
to determine a route from the local forwarding table based on the destination address; and
to forward the packet according to the route determined from the local forwarding table.
28. The apparatus of claim 24 , wherein the address is a media access control (MAC) address.
29. The apparatus of claim 24 , wherein the address is a customer MAC (C-MAC) address, and the DHT associates C-MAC addresses with provider MAC (P-MAC) addresses.
30. The apparatus of claim 24 , wherein the address is one of an IP address, a Network Application Services Platform (NSAP) address, and an MPLS label.