Declarative Policy-based Adaptive MANET Routing Changbin Liu*, Ricardo Correa*, Xiaozhou Li* Prithwish Basu, Boon Thau Loo*, Yun Mao *University of Pennsylvania BBN Technologies AT&T Labs - Research 1
Motivation Variety of MANET routing protocols Reactive (DSR, AODV) Proactive (LS, OLSR, HSLS) Epidemic Hybrid (ZRP, SHARP) However, a one-size-fits-all MANET protocol DOES NOT exist: Variability in network connectivity, wireless channels, mobility Wide range of traffic patterns 2
Approach Policy-based adaptive protocols Composed from any number of known protocols Generic set of policies for selecting and switching amongst different routing protocols due to network/traffic conditions Declarative networking A general platform and framework for specifying and implementing network protocols 3
Declarative Networking [Loo et. al., SIGCOMM 05] Use a database query language to specify network protocols Specifying what to do instead of how Distributed query engine executes specifications to implement network protocols Similar to Click modular router Efficient performance compared to imperative implementations 4
Why Declarative for MANETs? Compact and high level representation of protocols Orders of magnitude reduction in code size Chord DHT in 47 rules MANET routing protocols in a few rules Easy customization for policy-based adaptive MANETs 5
Example(1): Link State Broadcast specifier Built-in periodic trigger ls1lsu(@*,s,n,c,n) :-periodic(@s,t), link(@s,n,c). ls2lsu(@*,s,n,c,z) :-lsu(@z,s,n,c,w). Input: link (@src, next, cost) Output: lsu (@loc, src, next, cost, from) 6
Example(2): Hazy Sighted Link State hs1 lsu(@*,s,n,c,n,ttl) :- periodic(@s,t), link(@s,n,c), TTL=f_pow(2,K), T=TTL*Tp, K=range[1,5]. hs2 lsu(@*,s,n,c,z,ttl) :- lsu(@z,s,n,c,w), TTL > 0. Input: link (@src, next, cost) Output: lsu (@loc, src, next, cost, from) Scoped flooding Link updates to farther nodes sent less frequently TTL field to limit the forwarding range of LSU 7
Declarative MANET protocols Reactive DSR (Dynamic Source Routing) (10 rules) Proactive LS (Link State) (8 rules) HSLS (Hazy Sighted Link State routing) (14 rules) OLSR (Optimized Link State Routing) (27 rules) Epidemic Summary Vector based (16 rules) 8
Validation of Declarative MANETs Declarative MANET protocols executed by the P2 declarative networking system Local cluster consisting of 15 nodes interconnected by high-speed Ethernet emulating up to 40 MANET nodes Emulate network dynamics by adding/deleting links during rule execution Fig 1. Per-node communication overhead (KB/s) for LS, HSLS, OLSR Declarative MANETs show expected scalability trends 9
Measurements on ORBIT Wireless Testbed ORBIT wireless testbed at Rutgers University 1 GhZ VIA Nehemiah, 64 KB cache, 512 MB RAM Atheros AR5212 chipset 802.11 a/b/g ad hoc mode 33 nodes in a 7m x 5m grid 23 nodes 10
Policy-based Adaptive MANETs In declarative networking framework Hybrid protocol composed from any number of known protocols Generic set of policies for selecting and switching among different routing protocols due to network/traffic conditions Policies also specified in declarative language Examples Hybrid link state Hybrid proactive-epidemic 11
Example(1): Hybrid Link State LS: quick convergence, may perform better in stable network HSLS: incurs low bandwidth overhead, scales better Switch between LS and HSLS Low mobility: LS High mobility: HSLS Mobility measurement: link average availability (AA), i.e. percentage of time when link is up #define THRES 0.5 s1 linkavail(@m,avg<aa>) :- lsu(@m,s,n,aa,z,k). s2 usehsls(@m) :- linkavail(@m,aa), AA<THRES. // unstable s3 usels(@m) :- linkavail(@m,aa), AA>=THRES. // stable 12
Evaluation of Hybrid Link State 33 wireless nodes on 7m x 5m grid on ORBIT testbed that communicate over 802.11a Linux iptables to filter packets from non-neighbors Emulate 2-dimensional random waypoint model Random jitter and desynchronized broadcasting to alleviate packet collision Alternate at 60 seconds interval of: Moderate stage: nodes move at 0.06 m/s Fast stage: nodes move at 0.15m/s 13
Link dynamics Evaluation of Hybrid Link State Average link AA Protocol switching Bandwidth overhead Route stretch Hybrid Link State protocol achieves the best of both LS and HSLS 14
Example(2): Hybrid Proactive-Epidemic LS: good performance for well connected network Epidemic: for DTN, reliable message delivery in the sacrifice of high bandwidth Switch between LS and Epidemic Well connected network: LS Disrupted network: Epidemic Network connectivity measurement: path length Refer to our paper for more details about evaluation Declarative framework makes it easier to express policies for runtime adaptation of routing protocols 15
Summary MANET protocols in declarative framework Reactive, Proactive, Epidemic Compact specification Exhibit expected behaviors Policy-based adaptive MANETs Easy to build using existing declarative MANET protocols Protocol switching due to policies and network/traffic conditions Experiment results demonstrate that hybrid protocol can achieve the best of different protocols 16
Ongoing work Enhance declarative policy-based framework for adaptive protocols Adapt in a unified manner amongst proactive, reactive and epidemic Integrate with a channel selection policy engine Formally verifiable networking Verification of network protocols[hotnets 09] RapidNet A development toolkit that unifies rapid prototyping, simulation and experimentation [SIGCOMM 09 Demo] Integrates a declarative networking engine with the ns-3network simulator and emulator Successful evaluation on the ORBIT testbed [WinTECH 09] 17
RapidNet open source code release: http://netdb.cis.upenn.edu/rapidnet/ Thank you! 18
Backup 19
Network Datalog (NDlog) Example R1: reachable(@s,d) link(@s,d) R2: reachable(@s,d) link(@s,z), reachable(@z,d) For link(@a,b) all nodes there S,D, is a link from node a to node b If there is a link from S to D, then S can reach D. reachable(@a,b) node a can reach node b Input: link(@source, destination) Output: reachable(@source, destination) 20
Network Datalog (NDlog) Example R1: reachable(@s,d) link(@s,d) R2: reachable(@s,d) link(@s,z), reachable(@z,d) For all nodes S,D and Z, If there is a link from S to Z, AND Z can reach D, then S can reach D. Input: link(@source, destination) Output: reachable(@source, destination) 21
Epidemic (Summary vector based) e1 ebitvecreq(@y,x,v):- summaryvec(@x,v), edetectnewlink(@x,y). e2 ebitvecreply(@x,y,v):- ebitvecreq(@y,x,v1), summaryvec(@y,v2), V=f_vec_AND(V1,f_vec_NOT(V2)). e3 enewmsg(@y,i,s,d):- ebitvecreply(@x,y,v), msgs(@x,i,s,d), f_vec_in(v,i)==true. e4 msgs(@y,i,s,d):- enewmsg(@y,i,s,d). 22
Evaluation of Hybrid Proactive Epidemic Emulate 35 wireless nodes on 7m x 5m grid on local cluster Application level filtering to accept packets only from neighbors Emulate 2-dimensional random waypoint model Vary neighbor distance to construct connected/disconnected network Alternate at 60 seconds interval: Low connectivity with high mobility: nodes move at 0.03 m/s High connectivity with low mobility: nodes move at 0.001m/s 23
Evaluation of Hybrid Proactive Epidemic Performance Metrics: Per-node communication bandwidth overhead Packet delivery ratio: messages are forwarded from random sources to random destination Hybrid Proactive Epidemic achieves the best of both LS and Epidemic 24