Microsoft PowerPoint - snutalk

Size: px

Start display at page:

Download "Microsoft PowerPoint - snutalk"

세경 오
5 years ago
Views:

1 무선메쉬네트워크상에서 의라우팅프로토콜 2006 년 11 월 22 일이상환 국민대학교컴퓨터학부 /143

2 참고문헌 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 b mesh network. In Proc. ACM Sigcomm, August Kamal Jain Jitendra Padhye Venkat Padmanabhan Lili Qiu. The impact of interference on multi-hop wireless network performance. In Proc. ACM Mobicom, September 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 Richard Draves, Jitendra Padhye, and Brian Zill. Comparison of routing metrics for static multihop wireless networks. In Proc. ACM Sigcomm, August Richard Draves Jitendra Padhye Brian Zill. Routing in Multi-Radio, Multi-Hop Wireless Mesh Networks. In Proc. ACM Mobicom, September 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 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 /143

3 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 /143

4 Examples Node / Router Wireless Link Internet Internet /143

5 Static vs Mobile Motivating scenario Static Community wireless networks Mobile Battlefield networks Key challenge Improving network capacity Handling mobility, node failures, limited power /143

6 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 /143

7 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 /143

8 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 /143

9 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 /143

10 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) /143

11 Timing Diagram for DCF /143

12 Efficiency Of DCF Consider a data packet of size 1500 bytes Link Capacity of 2Mbps Effective data throughput T c = 1500 *2.0 Mbps ~ = 1.80 Mbps With inter-frame timing, T c ~= 1.7 Mbps /143

13 Multi-Hop Performance 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) /143

14 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 = Mbps /143

15 Chain Throughput /143

16 Cause of Packet Loss /143

17 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 /143

18 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 management frames No carrier sense /143

19 Lossy radio links are common Broadcast packet delivery probability % 30-70% 1-30% 1 kilometer /143

20 Delivery probabilities are uniformly distributed Broadcast Packet Delivery Probability > two-thirds of links deliver less than 90% Node Pair /143

21 Causes for intermediate delivery rates Marginal signal-to-noise ratios Interference: Long bursts, Short burst Multi-path interference /143

22 Multi-path interference B A Reflection is a delayed and attenuated copy of the signal /143

23 A channel emulator to investigate multi-path effects Sender Receiver delay attenuation /143

24 A reflection can cause intermediate packet loss Delivery probability Delay of second ray (nanoseconds or feet) /143

25 Roofnet links are long Cumulative fraction of links Link distance (feet or nanoseconds) It s reasonable to expect delays >500 ns /143

26 Link Quality Metric /143

27 Indoor wireless network 29 PCs with b radios (fixed transmit power) in ad hoc mode 2 nd floor 3 rd floor 4 th floor 5 th floor 6 th floor /143

28 What throughput is possible? Routing protocol Best Best for each pair is highest measured throughput of 10 promising static routes /143

29 Challenge: more hops, less throughput Links in route share radio spectrum Extra hops reduce throughput Throughput = 1 Throughput = 1/2 Throughput = 1/ /143

30 Challenge: many links are lossy One-hop broadcast delivery ratios Good Bad Smooth link distribution complicates link classification /143

31 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 /143

32 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 /143

33 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% % 33% /143

34 Calculating link ETX Assuming 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 ) /143

35 Route ETX Route ETX = Sum of link ETXs Route ETX Throughput 100% 50% 50% 33% 20% /143

36 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 /143

37 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 /143

38 Median Throughput Median Throughput (Kbps) HOP ETX RTT PktPair ETX performs best. RTT performs worst /143

39 Link Quality Metric for Multi-Radio & Multi-Hop Wireless Network /143

40 Multi-Hop Networks with Single Radio With a single radio, a node can not transmit and receive simultaneously /143

41 Multi-Hop Networks with Multiple Radios With two radios tuned to non-interfering channels, a node can transmit and receive simultaneously /143

42 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 /143

43 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 /143

44 ETT: Illustration 11 Mbps 5% loss 18 Mbps 50% 10% loss 1000 Byte Packet ETT : 0.77 ms ETT : ms /143

45 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 /143

46 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) /143

47 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 /143

48 Median Throughput Throughput (Kbps) 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 /143

49 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 /143

50 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 /143

51 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 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 /143

52 A New MAC Protocol for Long Distance Mesh Networks /143

53 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 /143

54 Basic Idea Nodes alternate between sending and receiving phases Dummy data for synchronization /143

55 Topology formation results: set /143

56 ExOR:Opportunistic Multi- Hop Routing For Wireless Networks Sanjit Biswas and Robert Morris MIT CSAIL /143

57 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/ = 5tx 4 ExOR: 1/ (1-(1-0.25) ) + 1 = 2.5tx /143

58 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? /143

59 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 /143

60 25 Highest Throughput Pairs ACK might get dropped even for single hop /143

61 25 Lowest Throughput Pairs Asymmetric long links affect ACK handling /143

62 Transmission Range ExOR requires less packet transmissions to travel far /143

63 IEEE s Wireless Mesh Networks 의 표준화과정 /143

64 802.11s Unapproved IEEE standard for ESS Mesh Networking An extension to the IEEE 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 s Ended in June 2005 with 15 proposals received. In the July 2005 meeting, 6 proposals remained Single proposal on March /143

65 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 /143

66 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 /143

67 802.11s 참고문헌 ml id= No= /143

68 슬라이드참고자료 m2004.ppt m2004.ppt ppt /143

Microsoft PowerPoint ppt

Microsoft PowerPoint ppt Wireless LAN 최양희서울대학교컴퓨터공학부 Radio-Based Wireless LANs Most widely used method Adv: penetrating walls and other obstacles with little attenuation. Disadv: security, interference, etc. 3 approaches: ISM