CS 417: Distributed Systems 12/16/2011 © 2011 Paul Krzyzanowski 1 Distributed Systems 26. Mobile Ad Hoc Mesh Networks Paul Krzyzanowski [email protected] Mesh Networks • Mobile Ad-hoc networks, sensor networks, … • Decentralized networking • No need for routers or access points • Each node participates in routing Mesh Networks • Topology of the network has to be discovered – Nodes come and go or move around • Topology may change frequently → on-demand routing – New nodes announce themselves – Other nodes listen for announcements • Often low-range, battery-powered devices – Multiple hops are common Mesh Networking • Hop node-to-node until the destination is reached – Nodes can act as repeaters to nearby peers – Robust connectivity: find alternate routes • Dynamic routing – Table-based: maintain fresh lists of destinations/routes – Dynamic: find route on demand – Hierarchical – Geographical – Power-aware – Multicast See http://en.wikipedia.org/wiki/Ad_hoc_routing_protocol_list Dynamic Source Routing (DSR) • On-demand routing • Source routing: sender learns the complete set of hops needed to reach the destination – Every packet carries the path of hops in its header • Intermediate nodes do not need to store routing information to route packets Route discovery via flooding • Broadcast Route Request message for some destination node, D, to all connected (reachable) nodes • Receiving node: – If it saw a packet with this ID, ignore request – If node ≣ node D: send back a Route Reply message to the path in the header – Else: add node ID to the path and forward Route Request to connected nodes • Note: – Path is maintained throughout the Route Request – Loops are prevented (don’t route to a node in the path)CS 417: Distributed Systems 12/16/2011 © 2011 Paul Krzyzanowski 2 Route discovery via flooding D e c b S d f a (S,D) (S,D) Route discovery via flooding D e c b S d f a (S, a, D) b will drop the request to route S to D if it saw the same Route Request ID Route discovery via flooding D e c b S d f a (S, b, D) (S, b, D) Route discovery via flooding D e c b S d f a (S, b, c, D) d will drop the request to route S to D since it saw the same Route Request ID from b earlier (S, b, c, D) Route discovery via flooding D e c b S d f a (S, b, d, D) (S, b, d, D) At around the same time, c will drop the request to route S to D since it saw the same Route Request ID from b earlier Route discovery via flooding D e c b S d f a e routes to d. D is the destination! (S, b, c, e, D)CS 417: Distributed Systems 12/16/2011 © 2011 Paul Krzyzanowski 3 Route discovery via flooding D e c b S d f a D sends a Route Reply back to S via the path. Request: (S, b, c, e, D) Reply: (D, e, c, b, S) Source Routing • Once a route is known – Path is specified with the packet header – If delivery fails, path will need to be rediscovered • Optimizations – Every node that sees packets or Route Reply messages learns how to reach all the nodes listed in the route. – Nodes can maintain tables to minimize learning routes – More-frequently used routes may be considered to be more accurate – Maintain and optimize for Distance Vector • Distance Vector = number of hops • Replace known routes with new routes with smaller distance vector – Or test new routes with a potentially smaller distance vector Table Driven Routing • When a node learns of a newly accessible node, it adds it to its routing table – Propagates updated routing table to other nodes (those nodes forward it, etc.) – Everyone’s routing table is kept updated • No need to perform dynamic routing • No need to send source route in each packet • Downside: extra network traffic for table propagation – May be worthwhile if the environment is not dynamic Example: ZigBee • ZigBee (IEEE 802.15.4) – 192 kbps – 100-1000 ft. range • ZenSys Z-Wave Screw-in lamp module $38 Dimmer switch $38 Outdoor plug module $40 ZigBee • Wireless star or mesh network – Star: single coordinator; no routing • Self-configuring • Redundant paths • Self-healing ZigBee device types • Coordinator – Starts & controls network – Stores info about the network – Repository for security keys • Router – Extends network coverage, provides backup routes – Connects to coordinator, other routers, & end devices • End devices – Transmit or receive a message – Does not perform routing – must connect to a coordinator or router • Roles may be combined: – Light socket: router or coordinator & end device – Battery-powered light switch: end device (mostly off)CS 417: Distributed Systems 12/16/2011 © 2011 Paul Krzyzanowski 4 Joining & Routing • Joining – Device sends a request to [re] join a network to the coordinator or router – In the simplest case, it has the network key • Routing – Based on Distance Vector routing • Distance Vector = number of hops to the destination – Each router maintains a routing table with entries for each destination – Routing table entry stores a distance vector & next router • Learning routes – Originating device broadcasts a route request – Destination device sends a a route reply – Intermediate nodes build up routing tables ZigBee Security • Encryption – All network traffic is encrypted with 128-bit AES • Trust Center – Maintains network key; periodically sends key updates (new key encrypted with old key) – Runs on a designated trusted device – Decides whether to allow new devices onto its network • Keys – Master keys: initial shared secret between two devices. Used to generate Link Keys – Network keys: all devices on a network share the same key – Link keys: optional for application-level encryption between two devices ZigBee setup • Out-of-the-box device can join any network • Installer: – Uses dedicated device with ZigBee coordinator – Device joins a “commissioning network” – Installer commissions device to identify correct network & security settings • Master key & Trust Center address configured • If master key is not configured – May sent on an insecure channel during configuration – Some implementations (Certicom’s) support public-key based key exchange using ECC (Elliptic Curve Cryptography) • Less compute (power) overhead than RSA or Diffie-Hellman Network-Based Plug & Play Ad-hoc networking and auto-discovery • Device/service discovery