Algorithms for Wireless Sensor Networks Presenters Vaibhav Mittal Sumeet Bajaj Prof Jie Gao State University of New York at Stony Brook Virtual Ring Routing Network Routing Inspired by DHTs Matthew Caesar Miguel Castro1 Edmund B Nightingale3 Greg O Shea1 Antony Rowstron1 1 Microsoft Research 2 University of California Berkeley 3 University of Michigan Cambridge UK Berkeley USA Ann Arbor USA mcastro gregos antr microsoft com mccaesar cs berkeley edu enightin 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 network OVERVIEW 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 addresses OVERVIEW 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 paths between a node and each of its virtual neighbors Virtual Ring Network Topology FC1 F01 35F A10 A01 V SET PATHS V set paths are multi hop in most cases bidirectional because membership in the vset is symmetrical i e if node x is in the vset of node y then node y is in the vset of 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 Forwarding 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 neighbors VRR 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 network NextHop rt dst endpoint closest id to dst from Endpoints rt if endpoint me return null return 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 vset and 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 Node joining contd 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 Selects 8F6 as its proxy Failure Detection Each Node Detects failures using only direct communication between physical neighbors Broadcast hello messages every Th seconds Maintains state for each neighbor Linked Pending Failed Unknown considers pset as the set of nodes in the Linked state Y state X Hello Message Linked and Active Linked but not Active Pending Failed X state Y Failure Detection Y s local state at X X s state in Hello message from Y State Diagram at node X Failure Detection Additional Rules Hello message is an indication of whether a node is active or not Whenever