무선메쉬네트워크상에서 의라우팅프로토콜 2006 년 11 월 22 일이상환 sanghwan@kookmin.ac.kr 국민대학교컴퓨터학부 2006-11-21 1/143
참고문헌 MACAW: A Medium Access Protocol for Wireless LANs, by V. Bharghavan et al., ACM SIGCOMM '94 Jinyang Li, charles Blake, Douglas S. J. De Couto, Hu Imm Lee, Robert Morris, Capacity of Ad Hoc Wireless Networks. In Mobicom 2001, Rome, Italy D. Aguayo, J. Bicket, S. Biswas, G. Judd, and R. Morris. Link-level measurements from an 802.11b mesh network. In Proc. ACM Sigcomm, August 2004. Kamal Jain Jitendra Padhye Venkat Padmanabhan Lili Qiu. The impact of interference on multi-hop wireless network performance. In Proc. ACM Mobicom, September 2003. Douglas De Couto, Daniel Aguayo, John Bicket, and Robert Morris. A high throughput path metric for multi-hop wireless routing. In Proc. ACM Mobicom, September 2003. Richard Draves, Jitendra Padhye, and Brian Zill. Comparison of routing metrics for static multihop wireless networks. In Proc. ACM Sigcomm, August 2004. Richard Draves Jitendra Padhye Brian Zill. Routing in Multi-Radio, Multi-Hop Wireless Mesh Networks. In Proc. ACM Mobicom, September 2004. Srihari Nelakuditi, Sanghwan Lee, Yinzhe Yu, Junling Wang, Zifei Zhong, Guor-Huar Lu, and Zhi-Li Zhang, "Blacklist-Aided Forwarding in Static Multihop Wireless Networks," In the Proceedings of IEEE SECON'05, Santa Clara, CA, Sep 2005 Bhaskaran Raman et al, "Design and Evaluation of a new MAC Protocol for Long-Distance 802.11 Mesh Networks", in Proc. ACM Mobicom 2005 Sanjit Biswas and Robert Morris. ExOR: Opportunistic Multi-Hop Routing for Wireless Networks. In Proc. ACM Sigcomm, August 2005. http://grouper.ieee.org/groups/802/11/reports/tgs_update.htm 2006-11-21 2/143
What is Wireless Mesh Network? Nodes are static Static Wireless Network Wireless channel for node to node transmission External interference, channel fading, inclement weather Quality of a link varies frequently over time Static wireless mesh networks are expected to proliferate Broadband access to residential areas Ease of deployment and maintenance 2006-11-21 3/143
Examples Node / Router Wireless Link Internet Internet 2006-11-21 4/143
Static vs Mobile Motivating scenario Static Community wireless networks Mobile Battlefield networks Key challenge Improving network capacity Handling mobility, node failures, limited power. 2006-11-21 5/143
MAC In Wireless Environment MAC : Multiple Access Control How to resolve the access to the common transmission media? Ex : CSMA / CD Senses the carrier, detect transmission, defer the transmission Problems in Wireless Environment Collision occurs at the receiver Hidden terminal problem C attempts to transmit when A is transmitting C cannot detect transmission => collision at B A B C 2006-11-21 6/143
MAC In Wireless Environment Exposed terminal problem B is sending to A and C is ready to transmit to other station Detect transmission => defer transmission, but can transmit A B C 2006-11-21 7/143
MACA MACA : Multiple Access with Collision Avoidance Two types of short, fixed-size signaling packets RTS (Request-to-Send), CTS (Clear-to-Send) Sender sends RTS, Receiver replies CTS, then Sender sends the data immediately after it receives CTS Overhearing RTS : defer transmission for some time Overhearing CTS : defer transmission for the length of data transmission Solves hidden terminal Timeout : when the sender cannot receive CTS Assume collision occurs Use Binary exponential backoff (BEB) algorithm 2006-11-21 8/143
MACAW ACK packet For link layer recovery RTS-CTS-DATA-ACK When no ACK reply, sender retransmits DATA When the receiver receives second RTS after ACK loss, sends ACK instead of CTS 2006-11-21 9/143
802.11 Distributed Coordination Function Overview of DCF NAV : Network Allocation vector : tracks the time for which the channel is reserved Sender transmits RTS (40 bytes) If destination node s NAV = 0, destination responds with a CTS message (39 bytes) Both RTS and CTS packets specify the time for which the channel is being reserved. All other nodes that can listen to RTS or CTS, update their NAV to NAV new = max ( NAV_Curr, time in RTS/CTS) Each data packet is acknowledged (ACK : 39 bytes) 2006-11-21 10/143
Timing Diagram for DCF 2006-11-21 11/143
Efficiency Of DCF Consider a data packet of size 1500 bytes Link Capacity of 2Mbps Effective data throughput T c = 1500 *2.0 Mbps 1500+ 40+ 39+ 39+ 47 ~ = 1.80 Mbps With inter-frame timing, T c ~= 1.7 Mbps 2006-11-21 12/143
Multi-Hop Performance 1 2 3 4 5 6 Throughput over # of hops 1 hop = 1 2 hop = 1/2 3 hop = 1/3 MAC Interference among a chain of nodes. The Solid-line circle denotes transmission range (200m approx) and the dotted line circle denotes the interference range (550m approx) 2006-11-21 13/143
Capacity Of A Chain of Nodes Since a node interferes with up to 4 other nodes, only ¼ links in the chain can be operational at any time instant Hence, effective end-end throughput is given by 0.25*1.7 = 0.425 Mbps 2006-11-21 14/143
Chain Throughput 2006-11-21 15/143
Cause of Packet Loss 2006-11-21 16/143
Cause of Packet Loss Roofnet is a multi-hop, wireless mesh net Packet loss makes protocol design hard Phenomena in this paper are well-known Does not propose any solution Analyzing the causes of packet loss, and fi nd important factors for protocol designs 2006-11-21 17/143
Methodology: Link-level measurem ents of packet loss Goal: all-pairs loss rates Each node broadcasts for 90 seconds All other nodes listen Raw link-level measurements: No ACKs, retransmissions, RTS/CTS No other Roofnet traffic No 802.11 management frames No carrier sense 2006-11-21 18/143
Lossy radio links are common Broadcast packet delivery probability 70-100% 30-70% 1-30% 1 kilometer 2006-11-21 19/143
Delivery probabilities are uniformly distributed Broadcast Packet Delivery Probability > two-thirds of links deliver less than 90% Node Pair 2006-11-21 20/143
Causes for intermediate delivery rates Marginal signal-to-noise ratios Interference: Long bursts, Short burst Multi-path interference 2006-11-21 21/143
Multi-path interference B A Reflection is a delayed and attenuated copy of the signal 2006-11-21 22/143
A channel emulator to investigate multi-path effects Sender Receiver delay attenuation 2006-11-21 23/143
A reflection can cause intermediate packet loss Delivery probability Delay of second ray (nanoseconds or feet) 2006-11-21 24/143
Roofnet links are long Cumulative fraction of links Link distance (feet or nanoseconds) It s reasonable to expect delays >500 ns 2006-11-21 25/143
Link Quality Metric 2006-11-21 26/143
Indoor wireless network 29 PCs with 802.11b radios (fixed transmit power) in ad hoc mode 2 nd floor 3 rd floor 4 th floor 5 th floor 6 th floor 2006-11-21 27/143
What throughput is possible? Routing protocol Best Best for each pair is highest measured throughput of 10 promising static routes. 2006-11-21 28/143
Challenge: more hops, less throughput Links in route share radio spectrum Extra hops reduce throughput Throughput = 1 Throughput = 1/2 Throughput = 1/3 2006-11-21 29/143
Challenge: many links are lossy One-hop broadcast delivery ratios Good Bad Smooth link distribution complicates link classification. 2006-11-21 30/143
Challenge: many links are asymmetric Broadcast delivery ratios in both link directions. Very asymmetric link. Many links are good in one direction, but lossy in the other. 2006-11-21 31/143
One straw-man route metric Maximize bottleneck throughput B Delivery ratio = 100% 50% A C 51% 51% Bottleneck throughput: D A-B-C = 50% A-D-C = 51% Actual throughput: A-B-C : ABBABBABB = 3 tx A-D-C : AADDAADD = 4 tx 2006-11-21 32/143
New metric: ETX Minimize total transmissions per packet (ETX, Expected Transmission Count ) Delivery Ratio 100% Link throughput 1/ Link ETX Link ETX 1 Throughput 100% 50% 33% 2 3 50% 33% 2006-11-21 33/143
Calculating link ETX Assuming 802.11 link-layer acknowledgments (ACKs) and retransmissions: P(TX success) = P(Data success) P(ACK success) Link ETX = 1 / P(TX success) = 1 / [ P(Data success) P(ACK success) ] Estimating link ETX: P(Data success) measured fwd delivery ratio r fwd P(ACK success) measured rev delivery ratio r rev Link ETX 1 / (r fwd r rev ) 2006-11-21 34/143
Route ETX Route ETX = Sum of link ETXs Route ETX 1 2 2 3 5 Throughput 100% 50% 50% 33% 20% 2006-11-21 35/143
ETX Properties ETX predicts throughput for short routes (1, 2, and 3 hops) ETX quantifies loss ETX quantifies asymmetry ETX quantifies throughput reduction of longer routes 2006-11-21 36/143
Comparison of Link Quality Metrics Per-hop Round Trip Time (RTT) Per-hop Packet-Pair (PktPair) Expected transmissions (ETX) Minimum-hop routing (HOP) Binary link quality 2006-11-21 37/143
Median Throughput 1600 1400 Median Throughput (Kbps) 1200 1000 800 600 400 200 0 HOP ETX RTT PktPair ETX performs best. RTT performs worst. 2006-11-21 38/143
Link Quality Metric for Multi-Radio & Multi-Hop Wireless Network 2006-11-21 39/143
Multi-Hop Networks with Single Radio With a single radio, a node can not transmit and receive simultaneously. 2006-11-21 40/143
Multi-Hop Networks with Multiple Radios With two radios tuned to non-interfering channels, a node can transmit and receive simultaneously. 2006-11-21 41/143
Existing Routing Metrics are Inadequate 2 Mbps 18 Mbps 18 Mbps 11 Mbps 11 Mbps Shortest path: 2 Mbps Path with fastest links: 9 Mbps Best path: 11 Mbps 2006-11-21 42/143
Link Metric: Expected Transmission Time (ETT) Link loss rate = p Expected number of transmissions 1 ETX = 1- p Packet size = S, Link bandwidth = B Each transmission lasts for S/B S ETT = * ETX B Lower ETT implies better link 2006-11-21 43/143
ETT: Illustration 11 Mbps 5% loss 18 Mbps 50% 10% loss 1000 Byte Packet ETT : 0.77 ms ETT : 0.89 0.40ms 2006-11-21 44/143
Combining Link Metric into Path Metric Proposal 1 Add ETTs of all links on the path Use the sum as path metric SETT = Sum of ETTs of links on path (Lower SETT implies better path) Pro: Favors short paths Con: Does not favor channel diversity 2006-11-21 45/143
Combining Link Metric into Path Metric : Proposal 2 Group links on a path according to channel Links on same channel interfere Add ETTs of links in each group Find the group with largest sum. This is the bottleneck group Too many links, or links with high ETT ( poor quality links) Use this largest sum as the path metric Lower value implies better path Bottleneck Group ETT (BG-ETT) 2006-11-21 46/143
Path Metric: Putting it all together SETT favors short paths BG-ETT favors channel diverse paths Weighted Cumulative ETT (WCETT) WCETT = (1-β) * SETT + β * BG-ETT β is a tunable parameter Higher value: More preference to channel diversity Lower value: More preference to shorter paths 2006-11-21 47/143
Median Throughput Throughput (Kbps) 3500 3000 2500 2000 1500 1000 500 0 Single Radio Two Radios WCETT (β = 0.5) ETX HOP WCETT makes Performance ETX can judicious not take of use HOP full of worsens advantage 2 nd radio: with 86% of 2 nd gain radio! over baseline 2006-11-21 48/143
Blacklist-Aided Forwarding in Static Multihop Wireless Networks Srihari Nelakuditi, Sanghwan Lee, Yinzhe Yu, Junling Wang, Zifei Zhong, Guor-Huar Lu, and Zhi-Li Zhang, In the Proceedings of IEEE SECON'05, Santa Clara, CA, Sep 2005 2006-11-21 49/143
Blacklist Aided Forwarding A link state protocol with base topology When there s no link failure, works as if link state routing When packet loss, carries blacklist in the packet header Blacklist initialized to empty at the packet s source Stays empty if forward progress w.r.t. base topology A link X Y is added to the packet s blacklist if Packet arrives at X and the nexthop is Y and Link X Y is currently degraded A packet s blacklist is reset to empty if Cost from next hop to destination is the smallest so far Blacklist grows if necessary and reset when possible Minimal set of degraded links to ensure loop-freedom 2006-11-21 50/143
Illustration: BAF 3, {B-E} B 3 E 2, {} 2 3 A 1 C 3 F 1 H 3, {B-E, A-C} A packet from B to E 2 4 3 D, {} gets caught in a loop under Shortest Path Forwarding traverses B-A-D-C-E under BAF BAF can forward packets between all pairs of nodes without informing G,F,H about A-C or B-E and A,B,C,D,E about G-H 2 G 2 2006-11-21 51/143
A New MAC Protocol for Long Distance 802.11 Mesh Networks 2006-11-21 52/143
The Assumed Mesh Network 3 relevant characteristics: Multiple radios per node Use of high-gain directional antenna Long-distance point-to-point links (several kms) Use single channel 2006-11-21 53/143
Basic Idea Nodes alternate between sending and receiving phases Dummy data for synchronization 2006-11-21 54/143
Topology formation results: set 1 2006-11-21 55/143
ExOR:Opportunistic Multi- Hop Routing For Wireless Networks Sanjit Biswas and Robert Morris MIT CSAIL http://pdos.csail.mit.edu/roofnet 2006-11-21 56/143
Why ExOR promises high throughput? 25% S 100% S 25% 25% S S 100% 100% D 25% S 100% Reception at different node is independent, no interference Traditional Routing: 1/ 0.25 + 1 = 5tx 4 ExOR: 1/ (1-(1-0.25) ) + 1 = 2.5tx 2006-11-21 57/143
Agreement using Gossip and Batch S Batch N8 1st round 2nd round 3rd round N3 N1 F N4 F F N2 N7 N6 F N5 F D A complete schedule, undelivered packet are retried in subsequent one A subset within a transmission batch is called Fragment (F) After each batch destination sends packet just containing batch map Okay, where is the agreement? 2006-11-21 58/143
Forwarding Timer and Transmission Tracker S Batch N8 1st round 2nd round 3rd round N3 N1 F N4 F F N2 N7 N6 F N5 F D Header contains information to predict source transmission rate Transmission schedule allows high priority node to send first Uses EWMA to set Forwarding Timer 2006-11-21 59/143
25 Highest Throughput Pairs ACK might get dropped even for single hop. 2006-11-21 60/143
25 Lowest Throughput Pairs Asymmetric long links affect ACK handling 2006-11-21 61/143
Transmission Range ExOR requires less packet transmissions to travel far. 2006-11-21 62/143
IEEE 802.11s Wireless Mesh Networks 의 표준화과정 2006-11-21 63/143
802.11s Unapproved IEEE 802.11 standard for ESS Mesh Networking An extension to the IEEE 802.11 MAC Solve the interoperability problem among vendors Radio-aware metrics over self-configuring multi-hop topologies IEEE Task Group TGs, Chaired by Donald Eastlake CFP for 802.11s Ended in June 2005 with 15 proposals received. In the July 2005 meeting, 6 proposals remained Single proposal on March 2006 2006-11-21 64/143
802.11s : Wi-Mesh Proposal Wi-Mesh Alliance (WiMA), Accton, ComNets, InterDigital, NextHop, Nortel, Philips, Extreme Networks, MITRE, Naval Research Laboratory, Swisscom Innovations and Thomson, Application area Consumer and small business Metropolitan Military 2006-11-21 65/143
802.11s : SEEMesh Proposal SEEMesh Alliance Firetide Networks, Intel, Nokia, Motorola, NTT DoCoMo, and Texas Instruments. Mesh Portal Intel and Firetide Offer interoperability to mesh networks Allow older, and newer, wireless standard technology to be recognized and incorporated into the network 2006-11-21 66/143
802.11s 참고문헌 http://grouper.ieee.org/groups/802/11/reports/tgs_update.htm http://wi-mesh.org/ http://standards.ieee.org/announcements/pr_80211sproposal.ht ml http://www.extremetech.com/article2/0,1697,1951233,00.asp http://www.eweek.com/article2/0,1895,1776125,00.asp http://dailywireless.org/modules.php?name=news&file=article&s id=3743 http://www.networkworld.com/news/tech/2006/041706-80211s-wireless.html http://www.inews.org/snews/11/articleshow.php?domain=koit& No=20923 2006-11-21 67/143
슬라이드참고자료 http://pdos.csail.mit.edu/roofnet/sigcomm-talk.ppt http://www-faculty.cs.uiuc.edu/~jhou/cs598jh/mitroofnet_sigcomm.ppt http://www.cse.buffalo.edu/~qiao/cse620/fall04/capacity.ppt http://research.microsoft.com/netres/kit/publications/presentations/mobico m2004.ppt http://www-faculty.cs.uiuc.edu/~jhou/cs598jh/routing4.ppt http://research.microsoft.com/netres/kit/publications/presentations/sigcom m2004.ppt http://www.cs.cmu.edu/~srini/15-849e/s06/lectures/12-metrics.ppt http://pdos.csail.mit.edu/grid/mobicom03-mark-ii.ppt http://www.cs.utexas.edu/~lili/classes/f05/slides/etx.ppt http://www.cs.ucsb.edu/~avijit/exor.ppt http://netweb.usc.edu/cs558/slides/gaurav.ppt http://www.cs.utexas.edu/~lili/classes/f05/slides/2p.ppt http://lion.cs.uiuc.edu/group_seminar_slides/mesh-2p-chunyu-2005-07- 23.ppt 2006-11-21 68/143