Todd Lamle

How to Evaluate Exotic Wireless Routing Protocols? : 

How to Evaluate Exotic Wireless Routing Protocols? 1 Dimitrios Koutsonikolas1, Y. Charlie Hu1, Konstantina Papagiannaki2 1Purdue University , 2Intel Research, Pittsburgh

Evolution of Wireless Routing Protocols : 

Evolution of Wireless Routing Protocols From the Ad Hoc Era to the Mesh Era New design goals High throughput vs. connectivity New “exotic” optimization techniques Cross – layer design 2 1994 1996 1997 1998 2000 2003 2004 2005 2006 2007 DSDV DSR AODV TORA Performance comparisons ETX ETT ExOR ROMER SOAR COPE MORE MC2 noCoCo Ad Hoc Networking Era Mesh Networking Era

In This Talk… : 

In This Talk… Review the evolution of wireless protocol design Reveal challenges to evaluation methodology of new routing protocols Discuss current practices Weaknesses Suggest guidelines for fair and meaningful evaluation 3

Ad Hoc Networking Era : 

Ad Hoc Networking Era Primary challenge Deal with route breaks due to host mobility Layering principle Routing protocol discovers route 802.11 unicast transmits packets to next hop ACK/RETX, exponential backoff Evaluation PDR, control overhead, tradeoffs Low constant offered load 4

Mesh Networking Era : 

Mesh Networking Era Static routers Mobility not a concern Commercial applications Compete with other internet technologies New research focus High Throughput 5

Towards High Throughput : 

Towards High Throughput Link-quality routing metrics Examples: ETX, ETT Still follow layering principle “Exotic” optimization techniques Examples: Opportunistic Routing, Network Coding Abandon layering principle 6

Opportunistic Routing : 

Opportunistic Routing First demonstrated in ExOR [SIGCOMM ‘05] Packet broadcast at each hop, all neighbors can receive it Neighbor closest to destination rebroadcasts Coordination required S B D C S D A A B C 50% 50% 50% 0% 0% 0%

Intra-Flow Network Coding : 

Intra-Flow Network Coding First demonstrated in MORE [SIGCOMM ‘07] Routers randomly mix packets Benefits Remove need for coordination FEC-style reliability, no ACK/RETX S D A B p1, p2 p1, p2 p1, p2 S D A B p1, p2 γ*p1+ δ*p2 α*p1+ β*p2 Who forwards? Both forward Coordination Required! No Coordination!

Inter-Flow Network Coding : 

Inter-Flow Network Coding First demonstrated in COPE [SIGCOMM ‘06] Routers mix packets from different flows Increase network capacity! Implied evaluation methodology Subject network to congestion Use network coding to eliminate congestion 9 Alice Router Bob 1:p1 2:p2 4:p2 3:p1 Traditional Routing: 4 TX Alice Router Bob 1:p1 2:p2 3:p1+p2 Network Coding: 3 TX 3:p1+p2

Implications of 802.11 Broadcast : 

Implications of 802.11 Broadcast 802.11 broadcast has no ACK/RETX, no exponential backoff No reliability Nodes can send faster than in unicast Exotic techniques do not work well with TCP Batching Consequence Reliability and rate control are brought to routing layer from lower or upper layers 10

Evolution of Protocol Stack : 

Evolution of Protocol Stack 11 Physical Layer Physical Layer MAC Layer MAC Layer Network Layer Network Sublayer 1 Transport Layer Network Sublayer 2 Network Sublayer 3 Application Layer Application Layer Medium Access Hop-by-hop Reliability Packet Forwarding End-to-end Rate Control End-to-end Reliability Medium Access Hop-by-hop Reliability Hop-by-hop Rate Control Network Coding Packet Forwarding End-to-end Reliability End-to-end Rate Control Traditional Network Stack New Network Stack

Implications on Protocol Evaluation : 

Implications on Protocol Evaluation Evaluation becomes a much subtler task Possible conflicts between new and old mechanisms Inter-flow network coding vs. rate control Current state Diverse set of evaluation methodologies Lack of clear guidelines 12

Evaluation of Unreliable Protocols : 

Evaluation of Unreliable Protocols 13

Practice 1: Making Both Protocols Reliable : 

Practice 1: Making Both Protocols Reliable Evaluation of ExOR, comparison with Srcr ExOR guarantees delivery of 90% of the file Srcr offers no guarantee Methodology Download a 1MB file Send 1.1MB with ExOR to compensate for loss Carry the whole file hop-by-hop with Srcr to avoid collisions 14 Problem Removes spatial reuse from traditional routing

Practice 2: No Rate Control – Varying the Sending Rate : 

Practice 2: No Rate Control – Varying the Sending Rate Evaluation of COPE, comparison with Srcr COPE increases network capacity Methodology UDP traffic Vary offered load Exceed nominal capacity (6Mbps) 15 Problem PDR drops quickly as network capacity is exceeded

Practice 3: A Protocol With Rate Control Against a Protocol Without Rate Control : 

Practice 3: A Protocol With Rate Control Against a Protocol Without Rate Control Evaluation of SOAR, comparison with Shortest Path (SP) SOAR applies rate control SP has no rate control Methodology Saturate the network 16 Problem Not clear what fraction of gain comes from opportunistic routing and what from rate control

Evaluation of Reliable Protocols : 

Evaluation of Reliable Protocols 17

Practice 5: A Reliable Against an Unreliable Protocol : 

Practice 5: A Reliable Against an Unreliable Protocol Evaluation of MORE, comparison with Srcr MORE offers FEC-style e2e reliability Srcr offers no reliability Methodology UDP sent at maximum possible rate 18 Problem Srcr suffers losses due to congestion Same amount of data sent by src, different amount delivered to dst

Practice 6: Running an Unreliable Protocol Under TCP : 

Practice 6: Running an Unreliable Protocol Under TCP Evaluation of noCoCo, comparison with COPE noCoCo applies backpressure-based congestion control/reliability COPE has no congestion control, weak reliability Methodology Run COPE under TCP 19 Problem TCP performs poorly in multihop wireless networks Solution – Practice 7 Modify COPE to use noCoCo’s congestion control/reliability

Use (or No Use) of Autorate Adaptation : 

Use (or No Use) of Autorate Adaptation Traditional routing uses 802.11 unicast Exploits autorate adaptation Exotic optimization techniques rely on 802.11 broadcast Operates on single rate Methodology Evaluation of most exotic protocols disables autorate adaptation for traditional routing For “fair”comparison 20 Problem Methodology can be unfair to traditional routing

Recommendations for more consistent and meaningful evaluation : 

Recommendations for more consistent and meaningful evaluation 21

The Importance of Rate Control I Unreliable Protocols : 

The Importance of Rate Control I Unreliable Protocols Traditional routing under UDP has no rate control Packets dropped beyond capacity Throughput reduction Exotic protocols w/o rate control Increase throughput, may increase capacity Packets still dropped beyond (new) capacity Exotic protocols w/ rate control Constant throughput beyond capacity No need to increase offered load beyond capacity 22

The Importance of Rate Control II Reliable Protocols : 

The Importance of Rate Control II Reliable Protocols FEC-style reliability provides no rate control PDR remains 100%, rate control still needed Exceeding capacity may lead to Increased delays Unfairness among flows Related recommendation Evaluate with multiple flows 23

Isolating the Benefit from Exotic Technique : 

Isolating the Benefit from Exotic Technique Evaluation should quantify the gain from new exotic optimization technique Tricky part Adding an exotic technique may require old techniques to move to the routing layer Recommendation Old techniques should also be incorporated into traditional routing 24

Separating Rate Control from End-to-end Reliability : 

Separating Rate Control from End-to-end Reliability Running traditional routing under TCP + No modification to the protocol itself TCP performs poorly in multihop wireless networks TCP provides both rate control and reliability If new protocol has only one mechanism, overkill to run old protocol under TCP Recommendation Incorporate reliability/rate control mechanism of new protocol to old protocol 25

How to Incorporate Reliability To Traditional Routing : 

How to Incorporate Reliability To Traditional Routing Case 1: reliability component disjoint to exotic technique Example: ARQ component in noCoCo Method: add same component to traditional routing Case 2: reliability component merged with exotic technique Example: intra-flow NC in MORE Method: add FEC to traditional routing? 26

MAC Autorate Adaptation : 

MAC Autorate Adaptation Exotic protocols should try to incorporate autorate adaptation Not always feasible Recommendation Enable autorate adaptation for traditional routing Show exotic protocol outperforms traditional routing both with and without autorate adaptation 27

Conclusions : 

Conclusions Inconsistencies in evaluating wireless mesh routing protocols Fundamental reason No unified framework for understanding interactions among MAC Congestion Reliability Interference Network coding Real problem goes beyond how to evaluate exotic protocols 28

Thank You! : 

Thank You! 29