Method for distance-vector routing using adaptive publish-subscribe mechanisms

Abstract

A distance-vector based routing protocol that integrates with adaptive publish-subscribe mechanisms by establishing routes to well-known controllers using distance-vector signaling.

What is claimed is: 
     
         1 . A method of routing, the method comprising:
 (i) establishing a computer network comprising a plurality of nodes, each node of said plurality of nodes having a unique node identifier, the plurality of nodes including an anchor controller storing a mapping having addresses of each of the plurality of nodes;   (ii) dynamically selecting a subset of said plurality of nodes to serve as controllers, said selecting based on a distributed algorithm that selects controllers such that each non-controller node is within a maximum distance from a minimum number of local controllers and wherein dynamically selecting controllers is performed in accord with predetermined Controller Addition Rules, thereby dividing said plurality of nodes into a plurality of controller nodes and a plurality of destination nodes;   (iii) maintaining routes to nearby destination nodes of each controller node, thereby forming local controllers;   (iv) maintaining routes to all controllers in each controller based on distance vectors; and   (v) using publish-subscribe mechanisms in which destination nodes inform local controllers of routes to them and sources obtain routes to local controllers of the destination nodes, wherein the sources obtaining routes includes:
 (a) sending a subscription request from a source node to the anchor controller, the subscription request including a destination node and a source node controller selected from the local controllers; 
 (b) sending the mapping to the source node controller from the anchor controller; 
 (c) forwarding the mapping to the source node; 
 (d) sending a data packet based on the mapping to a destination node controller of the destination node, the destination node being selected from the local controllers; and 
 (e) forwarding the data packet from the destination node controller to the destination node. 
   
     
     
         2 . The method of routing of  claim 1 , wherein dynamically selecting controllers is performed by nodes of said plurality of nodes deselecting themselves as controllers and wherein deselecting is performed in accord with Controller Deletion Rules. 
     
     
         3 . The method of routing of  claim 1 , wherein maintaining routes to all controllers uses sequence numbers to restrict selection of next hops towards a given controller such that only neighbors with shorter distances to the controller can be considered as successors. 
     
     
         4 . The method of routing of  claim 3 , wherein maintaining routes to all controllers include deleting controllers based on Controller Deletion Rules, and wherein controllers are deleted based on loss of connectivity to neighbors. 
     
     
         5 . The method of routing of  claim 4 , wherein controllers are deleted based on HELLOs from neighbors. 
     
     
         6 . The method of routing of  claim 5 , wherein controllers are updated based on an Update Controller rule. 
     
     
         7 . The method of routing of  claim 1 , wherein maintaining routes to each nearby destination node of each controller node in each controller is performed by:
 (i) each non-controller node d sending a publish message to each of its local controllers with a mapping (d, {I 1   d  . . . I k   d }), where I i   d  (1≤i≤k) is a local controller for non-controller node d;   (ii) each local controller I i   d  of non-controller node d and each destination node between said each local controller I i   d  and said non-controller node d receiving said publish message stores a tuple stating an address of non-controller d, a next hop to non-controller d, and {I 1   d , . . . , I k   d }; and   (iii) each non-controller node d selecting an anchor node a d  using a hash function;   (iv) each non-controller node d sends said selected anchor node a d  the mapping (d, {I 1   d , . . . I k   d }); and   (v) said selected anchor node a d  and relay nodes between d and a d  cache the mapping (d, {I 1   d , . . . , I k   d }).   
     
     
         8 . The method of routing of  claim 7 , further including determining a path from a source node s to a destination node d by performing:
 (i) having a node s identifying anchor a d  using said hash function;   (ii) said node s sending said identified anchor a d  addresses d and (s, {I 1   s , . . . , I k   s }) where I i   s  (1≤i≤k) is a local controller for node s;   (iii) anchor a d  returns a mapping (d, r) to node s by sending a response towards a local controller of node s;   (iv) said local controller of node s passes said mapping (d, r) to node s, and   (v) node s sends data packets to d by sending them towards controller r.   
     
     
         9 . The method of routing of  claim 1 , wherein each non-controller node i maintains the following:
 a controller table (CT i ) that states information about network controllers;   a neighbor controller table (NCT i ) stating information reported by each neighbor of non-controller node i regarding all controllers elected in the network;   a neighbor table (NT i ) stating information about all one-hop and two-hop neighbors of non-controller node i;   a neighbor local routing table (NLRT i ) stating routing information reported by each neighbor regarding all destinations within two hops and some destinations within r hops;   a local routing table (LRT i ) stating routing information about all destinations within two hops and some destinations within r hops;   a neighbor routing table (N RT i ) stating information reported by each neighbor regarding distant destinations; and   a routing table (RT i ) stating information about distant destinations.   
     
     
         10 . The method of routing of  claim 9 , wherein entries in RT i  and N RT i  are populated by publish-subscribe signaling and wherein using publish-subscribe mechanisms uses a network-wide consistent hash function. 
     
     
         11 . The method of routing of  claim 10 , wherein publishing is performed by:
 a node i using the network-wide consistent hash function on a set of identifiers in CT i  to obtain hash(i)=a i , where a i ∈CT i ;   node i sending a publication request towards its anchor controller a i  with a tuple {nid i  sn i   i , d i   i , LCL i   i ,};   nodes in the route from node i to controller a i  forwarding the publication request towards a i ; and   a i  caching a tuple {nid v   i  sn v   i , d v   i , s v   i , LCL v   i }.   
     
     
         11 . The method of routing of  claim 10 , wherein publishing is performed by:
 a node o using the network-wide consistent hash function on a set of identifiers in CT o  to obtain hash(i)=a j , where a j ∈CT o ;   node o sending a subscription request towards its anchor controller a j  stating an identifier of node j, its anchor controller a j , and LCL o ;   nodes in the route from node o to controller a j  forwarding a publication request towards a j ; and   a j  receiving o's request and sending a tuple {ni a j   j , sn a j   j  LCL a j   j } to a nearest controller it finds in LCL o ;   the nearest controller in LCL o  sending a tuple {ni 1 j   j , sn 1 j   j  LCL 1 j   j } to o.   
     
     
         12 . The method of routing of  claim 11 , wherein node o stores a tuple {nid o   j , sn o   j , LCL o   j } in RT jO  upon receiving a reply to its subscription; and wherein node o sends data packets towards controllers in LCL o   j  that are closest to node o for transmission to node i. 
     
     
         13 . The method of routing of  claim 7 , wherein maintaining routes to named services or content objects is performed by performing:
 (i) each non-controller node d selecting an anchor node a o  using a hash function on a name of a service or content o that it wants to publish;   (ii) each non-controller node d sends said selected anchor node a o  a mapping (o, d, {l 1   d , . . . , l k   d }); and   (iii) said selected anchor node a o  and the relay nodes between d and a o  cache the mapping (o, d, {l 1   d , . . . , l k   d }).   
     
     
         14 . The method of routing of  claim 13 , further including determining a path from a subscriber node s to a named service or content object o by performing:
 (i) a node s identifying anchor a o  using a hash function on the name of the service or content object o required by s;   (ii) said node s sending said identified anchor a o  the name o and (s, {l 1   s , . . . , l k   s }), where l i   s  (1≤i≤k) is a local controller for node s;   (iii) anchor a o  returns a mapping (o, d, {l 1   d , . . . l k   d }) to node s by sending a response towards a local controller of node s;   (iv) said local controller of node s passes said mapping (o, d, {l 1   d , . . . , l k   d }) to node s, and   (v) node s sends request for object o to d by sending them towards a local controller of d.   
     
     
         15 . The method of routing of  claim 13 , further comprising constructing a name of a service or content object to include a prefix component and a suffix component, with the prefix component being used in the hash function used to select an anchor controller for a named service or content object. 
     
     
         16 . The method of routing of  claim 1 , wherein establishing a computer network establishes an ad hoc network. 
     
     
         17 . The method of routing of  claim 16 , wherein the ad hoc network is a wireless network. 
     
     
         18 . The method of routing of  claim 14 , wherein establishing a computer network establishes an ad hoc network. 
     
     
         19 . The method of routing of  claim 18 , wherein the ad hoc network is a wireless network.