Algorithms for Wireless Sensor NetworksPresentersVaibhav MittalSumeet BajajProf. Jie GaoState University of New York at Stony BrookVirtual Ring Routing: Network Routing Inspired by DHTs[Matthew Caesar, Miguel Castro1, Edmund B. Nightingale3, Greg O’Shea1, Antony Rowstron11 Microsoft Research 2 University of California Berkeley 3 University of Michigan Cambridge, UK Berkeley, USA Ann Arbor, USAmcastro,gregos,[email protected] [email protected]@eecs.umich.edu]Virtual Ring Routing (VRR)• new network routing protocol implemented directly on top of the link layer• Provides both traditional point-to-point network routing and DHT routing to the node responsible for a hash table key• Never floods the network and uses only location independent identifiers to route. • Nodes organized into a virtual ring ordered by their identifiers• Each node maintains a small number of routing paths to its neighbors in the ring.• VRR uses these routing tables to route packets between any pair of nodes in the networkOVERVIEW• VRR uses random unsigned integers to identify nodes, and organizes the nodes into a virtual ring in order of increasing identifier• Node identifiers are fixed, unique and location independent and can be generated in different ways.• for example, an identifier could be the 160-bit SHA-1 hash of a node’s public key to facilitate secure communication or a randomly selected 32-bit integer to provide backwards compatibility with IPv4 addressesOVERVIEW(contd...)• Each node maintains a virtual neighbor set (or vset) of cardinality r containing the node identifiers of the r/2 closest neighbors clockwise in the virtual ring and the r/2 closest neighbors counter clockwise. • Each node also maintains a physical neighbor set (or pset) with the identifiers of nodes that it can communicate • A node only adds a neighbor to the pset if the quality of the links to and from that neighbor is above a threshold.• VRR sets up and maintains routing paths called vset-pathsbetween a node and each of its virtual neighbors.F01FC135FA01A10Virtual Ring & Network Topology• V-set paths are– multi-hop in most cases.– bidirectional because membership in the vset is symmetricali.e (if node x is in the vset of node y then node y is in the vsetof x).• vset-paths can be used to route packets between any pair of nodes.• VRR routes messages sent to numerical keys to the node whose identifier is numerically closest to the key from among all the endpoints in their routing table.V-SET PATHSForwarding• Each node maintains a routing table with information about the vset-paths to its virtual neighbors and other vset-paths that are routed through the node• Each entry contains the identifiers of the two endpoints of the path, the identifier of the physical neighbor to be used as the next hop towards each endpoint, and a vset-path identifier. • The first endpoint identifier in an entry is always the identifier of the node that initiated the vset-path setup.• The first four entries are for the vset-paths from the node to its four virtual ring neighbors.• Since node 8F6 is an endpoint in these paths, the identifier of the next hop towards the node is null. • The 5th and 6th entries in the table are for two vset-paths that are routed through node 8F6. VRR maintains the invariant that the nextA and nextB fields in a node’s routing table entries are in the pset of the node.• The last four entries are one-hop paths to physical neighborsVRR Forwarding Algorithm• VRR picks the node with the identifier closest to the destination from the routing table and forwards the message towards that node. • The packet is delivered to the node with the identifier closest to the destination in the networkNextHop(rt, dst)endpoint := closest id to dst from Endpoints(rt)if (endpoint == me)return nullreturn next hop towards endpoint in rt• the next hop to reach endpoint is retrieved from the routing table and the packet is sent to that node.Node joining• When a node joins the VRR network, it initializes its pset and vsetand sets up vset-paths to its virtual neighbors. • The joining node starts by looking for physical neighbors that are already active in the network and, therefore, can be used as proxies to route messages to others• It finds a proxy by sending and listening to hello messages that VRR nodes broadcast to physical neighbors periodically, These messages are also used to initialize the pset of the joining node• After finding a proxy, the joining node sends a setup req message to its own identifier x without flooding the network, through the proxy. • This message is routed using the forwarding algorithm to the node whose identifier, y, is closest to x.Node joining(contd…)• Node y is one of the immediate virtual neighbors of the joining node in the virtual ring and it knows the identities of the other virtual neighbors of x.• Node y replies with a setup message and also adds x to its vset. • This message sets up the vset-path between node y and the joining node by updating the routing tables of the nodes it visits. • The joining node adds y to its vset when it receives the message.• The setup message also includes y’s vset.• The joining node uses the received vset to initialize its own; it sends setup req messages to the identifiers of its other virtual neighbors.• The joining node adds these neighbors to its vset when it receives setup messages from them. • This completes all routing state initialization and the node becomes active• There are two additional message types:  setup fail messages: sent in reply to setup req messages indicating refusal to setup a vset-path to the source,  Teardown messages: used to remove entries for vset-paths from the routing tables along the path.• A node replies to a setup req message from x with setup fail when it does not add x to its vset.• VRR aborts a vset-path setup by calling TearDownPath to remove all entries for the path from the routing tables of all nodes that may have been visited by the setup message.Node joining(contd…)Selects 8F6 as its proxyFailure DetectionEach Node …• Detects failures using only direct communication between physical neighbors• Broadcast hello messages every Thseconds• Maintains state for each neighbor {Linked, Pending, Failed, Unknown}• considers pset as the set of nodes in the Linked stateHello Message{Linked and Active}{Linked but