Distributed Storage of Routing Information in a Link State Protocol Controlled Network

Abstract

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. The DHT may be implemented to store MAC addresses, IP addresses, MPLS labels, or other information.

What is claimed is: 
     
         1 - 22 . (canceled) 
     
     
         23 . 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, each node having a respective node identifier, the method comprising:
 at a first node having a packet for transmission on the network, the packet having a destination address:
 performing a hash on the address to determine a route identifier; 
 determining nodes to query for route information using the determined route identifier and a membership table, the membership table containing a list of nodes implementing the distributed hash table; and 
 transmitting a route information request to a second node, the second node being one of the determined nodes; 
   at the second node:
 receiving the route information request from the first node; 
 determining route information associated with the destination address based on the route information request; and 
 sending a route information response to the first node, the route information response indicating the determined route information; and 
   at the first node:
 receiving the route information response; 
 determining a route associated with the destination address based on the route information response; and 
 forwarding the packet having the destination address according to the determined route. 
   
     
     
         24 . The method of  claim 23 , wherein determining the nodes to query for route information using the determined route identifier and the membership table comprises comparing the determined route identifier to node identifiers in the membership table to determine a set of nodes having node identifiers deemed closest to the route identifier. 
     
     
         25 . The method of  claim 24 , wherein comparing the determined route identifier to node identifiers comprises comparing the route identifier to the node identifiers using an XOR-distance process. 
     
     
         26 . The method of  claim 23 , wherein the first node stores in the membership table node identifiers of other nodes in the packet network which together store the DHT. 
     
     
         27 . The method of  claim 23 , comprising:
 at the first node:
 detecting a change in topology of the packet network; 
 determining routes affected by the change in topology; and 
 for each of the routes affected by the change in topology: 
 performing a hash on an address to determine nodes in the DHT to query for a route; and 
 transmitting a route information request to another node, the other node being one of the determined nodes; and 
   at the other node:
 receiving the route information request from the first node; 
 determining route information associated with the destination address based on the route information request; and 
 sending a route information response to the first node, the route information response indicating the determined route information; and 
   at the first node:
 receiving the route information response; 
 determining a route update based on the route information response; and 
 storing the route update in a local forwarding table. 
   
     
     
         28 . The method of  claim 27 , 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.   
     
     
         29 . The method of  claim 23 , wherein the destination address is a media access control (MAC) address. 
     
     
         30 . The method of  claim 23 , wherein the destination address is a customer media access control (C-MAC) address and the DHT associates C-MAC addresses with provider MAC (P-MAC) addresses. 
     
     
         31 . The method of  claim 23 , wherein the destination address is an internet protocol (IP) address. 
     
     
         32 . The method of  claim 23 , wherein the destination address is a network application services platform (NSAP) address. 
     
     
         33 . The method of  claim 23 , wherein the destination address is a multi-protocol label switching (MPLS) label. 
     
     
         34 . The method of  claim 24 , wherein the node identifiers are calculated by performing a hash on an address associated with each respective node. 
     
     
         35 . The method of  claim 26 , wherein the node identifiers are addresses associated with each respective node. 
     
     
         36 . The method of  claim 34 , wherein the address associated with each respective node is an Ethernet MAC address. 
     
     
         37 . The method of  claim 35 , wherein the address associated with each respective node is an Ethernet MAC address. 
     
     
         38 . The method of  claim 34 , wherein the address associated with each respective node is an IP address. 
     
     
         39 . The method of  claim 35 , wherein the address associated with each respective node is an IP address. 
     
     
         40 . The method of  claim 23 , wherein:
 the first node transmits the route information request to a plurality of the determined nodes; and   the first node determines a route associated with the destination address based on a route information response received from one of the plurality of determined nodes; and   the first node forwards the packet having the destination address according to the determined route.