Slide 115 -
|
Wireless Mesh Networks Victor Bahl http://research.microsoft.com/~bahl Lecture 1
MSR India Summer School on Networking June 15, 2007 These lecture notes are for educating. Feel free to incorporate these slides in your presentations but please cite the source on each borrowed slide and as a courtesy to the author please inform him of such use. Do not post a copy of these slides, or slides derived from these on a web site without the author’s written permission. The contents of this deck may change without notice . Notice Foreword Mobile ad hoc networking and mesh networking is a thriving area of research. The number of solutions & results are simply too large to cover in a short lecture.
This is not a lecture on (1) wireless communications (2) MAC protocols, (3) PHY Layer techniques and (3) multi-hop routing protocols.
This is quick talk about what I know about building mesh networks. Exhaustive & deep treatment of all existing results is not provided.
These notes are an attempt to describe the main problems & the general idea behind some of the promising solutions. At the end of this lecture you should have a reasonably good understanding of the state-of-art in mesh networking. . Topics not covered in this lecture Due to lack of time I was not cover several important research results that you should also be aware of.
Some of these are:
Modulation and PHY techniques like OFDM, Analog Network Coding etc.
Adaptive antenna technologies like MIMO, beam forming, etc.
TCP enhancements (for mesh networking)
Routing protocols (there are hundreds……)
Multicast routing and group communications
Topology control and power management
Standards including IEEE 802.11s,…
Security and Management
Directional MACs etc
. Roadmap Mesh Networking & Applications
Basics of Radio Frequency Communications (already covered by Dr. Ramjee)
Multi-hop Wireless Networking
Historical background
Challenges: Mesh networking with 802.11
Handling the Challenges
Capacity Enhancement & Calculation
MMAC, SSCH, BFS-CA, HMCP, MUP, Network Coding, conflict graphs, ….
Routing Protocols & Link Quality Metrics
RFC 2501, RFC 3626, RFC 3684, RFC 3561, RFC 4728, ETX, LQSR, EXoR, HWMP, ETT, WCETT
Security & Network Management
Mesh Deployments – Discoveries & Innovations
MSR’s Mesh, MIT’s RoofNet, IIT’s DGP, Rice’s TFA, UMASS’s DieselNet, UCSB’s Mesh,
Madcity’s Mesh, JHU’s SMesh
Mesh Networking Standards
IEEE 802.11s (IETF standards covered previously)
References . Will not
cover,
tutorial notes available on request Mesh Networking & Applications Wireless Mesh Networking Definition
A wireless mesh network is a peer-to-peer multi-hop wireless network in which participant nodes connect with redundant interconnections and cooperate with one another to route packets.
Unlike Mobile Ad hoc NETworks (MANETs) where routings node are mobile, in mesh networks routing nodes are stationary.
Mesh nodes may form the network's backbone. Other non-routing mobile nodes ("clients") may connect to the mesh nodes and use the backbone to communicate with one another over large distances and with nodes on the Internet
. Characteristics of a Mesh Network Classic Hub & Spoke Network Mesh Network Can grow “organically”
Does not require infrastructure support
Is fault tolerant
Requires distributed management
Offers higher capacity (via spatial diversity & power management), but
Too many nodes shared bandwidth may suffer due to interference
Too few nodes route maintenance is difficult disconnections possible
Identity and security management is a challenge . The Mesh Networking World Internet Communication Corporate Data Games Shopping Media Web Content Broadband Neighbourhood Mesh Node Mesh Node Mesh Node Mesh Node Home Mesh Mesh Node Traditional Last Mile Territory Mesh Node . Scenario 1: Broadband Internet Access Cost of middle and last miles make physical wired infrastructure not an option in rural areas and many countries
Equipment capital cost
The scale of touching / maintaining so many endpoints
The physics of running cable large distances over unfriendly terrain
Political, social and territorial implications
Wireless mitigates these issues but introduces others
Range
Bandwidth
Spectrum availability
Cost & maintenance issues of new hardware / standards
Mesh networking makes wireless workable
Range & bandwidth addressed by shorter links
Cost & maintenance addressed by building on commodity standards Internet Backbone Middle Mile Last Mile . Scenario 2: A Community Mesh Network Organic – Participants own the equipment and the network . Community Mesh Network Applications Shared broadband Internet access
Neighborhood watch (e.g. video surveillance)
Shared media content (e.g. neighborhood DVR)
Medical & emergency response
Neighborhood eBay (garage sales, swaps)
Billboards (babysitter/service recommendations, lost cat, newsletter)
Bits produced locally, gets used locally
Social interaction
Distributed backup
Internet use increased social contact, public participation and size of social network. (social capital - access to people, information and resources)
Prof. Keith N. Hampton (author of “Netville Neighborhood Study”)
URL: http://www.asanet.org/media/neville.html
. Scenario 3: Home Mesh Extend Access Point (AP) coverage
Better spectrum (re)use greater capacity
Automatic discovery, plug-and-play networked home devices:
AV equipment (Cameras, TV, DVD, DVR, satellite/cable)
Phones (Cellular and POTS)
Traditionally disassociated smart devices (PDAs, AutoPC)
Home infrastructure items (Light switches, HVAC controls)
. Scenario 4: Blanket City-wide Wireless Coverage Philadelphia picks Earthlink for City Wireless, TechNew World, October 5, 2005
San Francisco Keeps Pushing City Wide WiFi, CNET News.com, August 17, 2005
“San Francisco Mayor Gavin Newsom wants to make Wi-Fi coverage in the city as ubiquitous as the fog that blankets its neighborhoods.”
Wi-Fi Hits the Hinterlands, BusinessWeek Online, July 5, 2004
“Who needs DSL or cable? New “mesh” technology is turning entire small towns into broadband hot spots”, Rio Rancho N.M., population 60,000, 500 routers covering 103 miles2
NYC wireless network will be unprecedented, Computerworld, June 18, 2004
“New York City plans to build a public safety wireless network of unprecedented scale and scope, with a capacity to provide tens of thousands of mobile users”
Rural Areas need Internet too! Newsweek, June 7, 2004 Issue
“EZ Wireless built the country's largest regional wireless broadband network, a 600-square-mile Wi-Fi blanket, and activated it this February”, Hermiston, Oregon, population 13,200, 35 routers with 75 antennas covering 600 miles2
Mesh Casts Its Net, Unstrung, January 23, 2004
“Providing 57 miles2 of wireless coverage for public safety personnel in Garland Texas”
PCCW takes Wireless Broadband to London, The Register, September 2, 2005
“Prices for the service in UK start from £10 / month for 256 Kbps to £18 /month for 1 Mbps”
Anacapa and Firetide Bring Free Wireless Internet to La Semaine Italienne in Paris, France ,
Business Wire, 24 May, 2005
Bell Canada and Nortel Networks launch Project Chapleau,
designed to evaluate broadband in rural Canada, Optical Networks Daily, 18 July 2005
. Scenario 5: All-Wireless Office No wires
No switches
No APs Older buildings
For small offices (~100 PCs)
Rapid deployment
Low cost
Short-term offices
Not a replacement for wire . Scenario 6: Spontaneous “Mesh” Definition
A temporary ad-hoc multihop wireless network for exchanging voice, video or data, for collaboration in a locally distributed environment, when no permanent infrastructure or central control is present. Usually between portable wireless devices.
1. Peer Calling & Party Lines
P2P calling within local groups – conferences, events, school campus,…
3. Real Time Advisory
Drivers need traffic information and advisories generated in real time 2. Public Safety
Fire and rescue teams need ad-hoc communication at incident sites . Grass Roots Mesh Deployments Academia
The Roofnet Project (MIT, USA) - http://pdos.csail.mit.edu/roofnet/doku.php
802.11 mesh network for broadband IA in cities
The CITRIS TIER Project (UC Berkeley, USA) - http://tier.cs.berkeley.edu/
Technology and Infrastructure for emerging regions
The Digital Gangetic Plains Project (IIT Kanpur, India) - http://www.iitk.ac.in/mladgp
802.11-based low-cost Networking for rural India
The TFA Project (Rice University, USA) - http://taps.rice.edu/index.html
Technology for All Project
….
Community Mesh Networks
Community Network Movement - http://www.scn.org/commnet/
Seattle Wireless - http://www.seattlewireless.net/
Champaign-Urbana Community Wireless Network - http://www.cuwireless.net/
Kingsbridge Link, U.K. - http://www.kingsbridgelink.co.uk/
…. . Industry Breakdown SkyPilot, QualNet (Flarion),
Motorola (Canopy) IRoamAD, Vivato,
Arraycomm, Malibu Networks,
BeamReach Networks, NextNet
Wireless, Navini Networks, etc. Meshnetworks Inc.,Radiant Networks,
Invisible Networks, FHP, Green Packet Inc.,
LocustWorld, etc. Infrastructure Based Infrastructure-less Architecture effects design decisions on
Capacity management, fairness, addressing & routing, mobility management, energy management, service levels, integration with the Internet, etc. . Industry Deployment Scenarios http://www.unstrung.com/insider/ March 2005, Source: Unstrung Insider . What about WiMAX? IEEE 802.16d for developing/rural use (.16e targets mobile scenarios)
Still needs market momentum around hardware optimisation: size, power, efficiency and most important—cost
WiMAX as a last-mile solution?
In low-density areas, WiMAX requires high-power towers or lots of towers: (=> cost goes up)
In NLOS environments, range impacts bandwidth through reduced modulation
WiMAX CPE expensive in next 3-5 years (~ $150-250)
WiMAX feeding a mesh can be a good solution
Mesh extends WiMAX tower reach
Mesh simplifies the financials by greatly reducing equipment cost
Mesh is robust and deal with network vagaries . 16 QAM 16 QAM 16 QAM 8PSK 16 QAM QPSK FSK WiMAX + Mesh WiFi Meshes can add value to WiMAX in several ways:
Reduce CPE costs
Extend range of WiMAX tower without compromising speed
Replace high-price WiMAX towers with cheaper mesh nodes WiMAX Only 16 QAM WiMAX with Mesh A A . Multi-Hop Wireless Networking Historical Perspective Packet Radio Network (PRNET), 1972-1982
Band: 1718.4-1840 MHz; Power: 5 W; Range: 10 km; Speed:100-400 Kbps, Addressing: Flat; Routing: Distance Vector; Scale: 50+
Survivable Adaptive Networks (SURAN), 1983-1992
Band: 1718.4-1840 MHz; Power: 5 W; Range: 10 Km; Speed: 100-400 kbps, Addressing: Hierarchical; Routing: Distance Vector; Scale: 1000+ (Low cost packet radio)
Global Mobile Information Systems (GLOMO), 1995-2000
e.g. NTDR, Band: 225-450 MHz; Power: 20 W; Range: 11-20 Km; Speed: 300 kbps, Addressing: Flat; Routing: Link-state / 2-level clusters; Scale: 400+
IETF Mobile Ad Hoc Networks (MANET) Working Group, 1997 –
RFC 2501 (Eval), RFC 3561 (AODV), RFC 3626 (OLSR), RFC 3684 (TBRPF), Drafts – DSR, DYMO, Multicast, OLSRv2
MSR Mesh Networking Project (2002 – 2005)
IEEE 802.11s Working Group, 2004 - PRNET Van . Challenge: Mesh Networking with IEEE 802.11 2 3 4 5 7 8 9 1 11 10 RTS RTS CTS CTS 6 The MAC Problem – Packets in Flight Example 2 packets in flight! Only 4 out of 11 nodes are active…. Backoff window doubles RTS RTS RTS . RTS CTS Throughput: Internet Gateway Example RTS RTS Backoff window doubles Backoff window doubles Internet . The Scheduling Problem Conflict graph If future traffic is not known, which one do you schedule first? D Choice 1 Choice 2 yes D yes . The Fairness Problem Information Asymmetry
A & C do not have the same information
C knows about flow 1 (knows how to contend)
A does not know about flow 2
Flow 2 always succeeds, Flow 1 suffers
When RTS/CTS is used
A’s packets are not acknowledged by B
A times out & doubles it’s contention window
When RTS/CTS is not used
A’s packet collide at B, but Flow 2 is succesful
A times out & double it’s contention window
Downstream links suffer 1 2 . Gambiroza-MoiCom-2004 Jinyang-MobiCom-2001 The Fairness Problem (2) Location closest to gateway gets the more packets
Nodes farthest from the gateway get very little bandwidth and can get starved
Possible solution: Rate control on each node with fairness in mind
Need topology & traffic information to calculate fair amount
Global vs. distributed solution
ITAP . Camp-DC-2005 The Fairness Problem (3) MAC attempts to provide fairness at packet level not flow level
Capture phenomena
Winner of competing flows has a higher chance of winning contention again
Different levels of interference at different links (different neighborhood)
Highly interfered flows can be drowned Active area of research
- MACAW, WFQ, DFS, Balanced MAC, EBF-MAC, PFCR, …. . Qiu-MSRTR-2003 Nandagopal-MobiCom-2000 The Path Length Problem Experimental Setup
23 node testbed
One IEEE 802.11a radio per node (NetGear card)
Randomly selected 100 sender-receiver pairs (out of 23x22 = 506)
3-minute TCP transfer, only one connection at a time
If a connection takes multiple paths over lifetime,
lengths are byte-averaged
Total 506 points. Impact of path length on throughput . Expected multi-hop b/w based on single-hop b/w Actual Roofnet b/w is often much lower The Collision Problem Robert Morris’s Rooftnet MSR Mesh Summit 2004 Presentation Multi-hop collisions cut b/w by about 2x The Node Density Problem A new 100Kbps CBR connection starts every 10 seconds,
between a new pair of nodes. All nodes hear each other. Round trip delay versus node density . The Power Control Problem A & B do not detect RTS/CTS exchange between C & D
B does not detect data transmission from D to C
B’s transmission to A results in packet collision at C A B C D . Tight power control reduces interference and increases throughput The Power Control Problem (2) Tight power control reduces interference & increases overall throughput
But it also disconnects the network. So what’s the “right” power control algorithm? A B C D A B C D . The Capacity of Mesh Nodes Optimal Case
Nodes are optimally located, destinations are optimally located
Traffic patterns are fixed
Optimally spatio-temporal scheduling, routes, ranges for each transmission
As each node obtains bits/sec Average Case
Randomly located nodes and destinations
Traffic pattern are random
Each node chooses same range
Each node obtains bits/sec . What is the maximum achievable capacity of a mesh network with N nodes? Gupta-IEEEIT-2000 The Capacity Calculation Problem Gupta and Kumar 2000
Theorem for stationary ad hoc nodes in the worst case traffic scenario
Determines asymptotic, pessimistic bounds on performance
Every node in the mesh is active (either transmitting or receiving)
Does not answer:
What is the capacity of a mesh which is using multiple channels, directional antennas, tight power control? . What is the Real Capacity of a Chain? With Ideal MAC, Chain Utilization = 1/3 1 2 3 4 5 6 Source Destination With interferences, Chain Utilization = 1/4 ….but this is achievable only with optimum scheduling and optimum offered load!,
…with random scheduling and random load, utilization ~ 1/7 ! …but the radio’s interferance range is > radios communication range . Jinyang-MobiCom-2001 Routing Problem: Which to Choose? Unicast Ad Hoc Multi-hop Routing Protocols ABR (Associativity-Based Routing Protocol)
AODV (Ad Hoc On Demand Distance Vector)
ARA (Ant-based Routing Algorithm)
BSR (Backup Source Routing)
CBRP (Cluster Based Routing Protocol)
CEDAR (Core Extraction Distributed Ad hoc Routing)
CHAMP (CacHing And MultiPath routing Protocol)
CSGR (Cluster Gateway Switch Routing)
DART (Dynamic Address Routing)
DBF (Distributed Bellman-Ford)
DDR (Distributed Dynamic Routing)
DNVR (Dynamic Nix-Vector Routing)
DSDV (Dynamic Destination-Seq. Dist. Vector)
DSR (Dynamic Source Routing)
DSRFLOW (Flow State in the DSR)
DYMO (Dynamic Manet On-Demand)
FORP (Flow Oriented Routing Protocol)
FSR (Fisheye State Routing)
GB (Gafni-Bertsekas)
GLS(Grid) (Geographic Location Service)
GPSAL (GPS Ant-Like)
GSR (Global State Routing)
Guesswork
HARP (Hybrid Ad hoc Routing Protocol)
HSLS (Hazy Sighted Link State)
HSR (Hierarchical State Routing)
HSR (Host Specific Routing)
IARP (Intrazone Routing Protocol)
IERP (Interzone Routing Protocol)
LANMAR (LANdMARk Routing Protocol)
LAR (Location-Aided Routing)
LBR (Link life Based Routing)
LCA (Linked Cluster Architecture)
LMR (Lightweight Mobile Routing)
LQSR (Link Quality Source Routing)
LUNAR (Lightweight Underlay Network Ad hoc Routing)
MMRP (Mobile Mesh Routing Protocol)
MOR (Multipoint On-demand Routing)
MPRDV (Multi Point Relay Distance Vector)
OLSR (Optimized Link State Routing)
OORP (OrderOne Routing Protocol)
DREAM (Distance Routing Effect Algorithm for Mobility)
PLBR (Preferred Link Based Routing)
RDMAR (Relative-Distance Micro-discover Ad hoc Routing)
Scar (DSR and ETX based)
SSR (Signal Stability Routing)
STAR (Source Tree Adaptive Routing)
TBRPF (Topology dissemination Based on Reverse-Path Forwarding)
TORA (Temporally-Ordered Routing Algorithm)
WRP (Wireless Routing Protocol)
ZHLS (Zone-Based Hierarchical Link State)
ZRP (Zone Routing Protocol)
…. . The Path Selection Problem Several link quality metrics to select from
Hop count
Round trip time
Packet pair
Expected data transmission count incl. retransmission
Weighted cumulative expected transmission time
Signal strength stability
Energy related
Link error rate
Air Time
…
Which to select? We still don’t have a interference-aware metric! We still don’t know how to measure interference….. . Baseline comparison of Metrics Single Radio Mesh Experimental Setup
23 node testbed
One IEEE 802.11a radio per node (NetGear card)
Randomly selected 100 sender-receiver pairs (out of 23x22 = 506)
3-minute TCP transfer, only one connection at a time
ETX performs the best Median path length:
HOP: 2, ETX: 3.01, RTT: 3.43, PktPair: 3.46 . Draves-MobiCom-2004 Experimental Setup
23 node testbed
Randomly selected 100 sender-receiver pairs (out of 23x22 = 506)
3-minute TCP transfer
Two scenarios:
Baseline (Single radio):
802.11a NetGear cards
Two radios
802.11a NetGear cards
802.11g Proxim cards WCETT utilizes 2nd radio better
than ETX or shortest path Baseline Comparison of Metrics Two Radio Mesh Median path length:
HOP: 2, ETX: 2.4, WCETT: 3 . Draves-SIGCOMM-2004 But with different traffic pattern…. Trace Capture
1 workstations connected via Ethernet
Traces captured during 1-month period
Trace Replayed
Testbed of 22 mesh computers in office environment
2 IEEE 802.11a/b/g cards per computer . Erickson-MobiSys-2006 The Multicast Problem A multicast group is defined with a unique group identifier.
Nodes may leave or join the group anytime
In wired networks physical network topology is static
In ad hoc multi-hop wireless networks physical topology can change often
Need to Integrate with unicast routing protocols
Many proposals [Tree-based, Mesh-based, Location-based] which one to use?
. - ABAM (On-Demand Associatively-Based Multicast) - FGMP (Forwarding Group Multicast Protocol)
- ADMIR (Adaptive Demand-Driven Multicast Routing) - LAM (Lightweight Adaptive Multicast)
- AMRIS (Ad hoc Multicast Routing utilizing Increased id-numberS) - MAODV (Multicast AODV)
- DCMP (Dynamic Core Based Multicast Routing) - MCEDAR (Multicast CEDAR)
- AMRoute (Adhoc Multicast Routing) - MZR (Multicast Zone Routing)
- CAMO (Core-Assisted Mesh Protocol) - ODMRP (On-Deman Multicast Routing Protocol)
- CBM (Content Based Multicast) - SPBM (Scalable Position-Based Multicast)
- DDM (Differential Destination Multicast) - SRMP (Source Routing-based Multicast Protocol)
- DSR-MB (Simple Protocol for Multicast and Broadcast using DSR) - …
- … The Interference Detection Problem When two systems operate on overlapping frequencies, there exists a potential for harmful interference between them
Performance degradation on both systems
Conflict graph is determined by the “Interference Graph”
To determine the Interference Graph, require
Knowledge of packet transmission from nodes that are not “visible”
Knowledge of physical location of nodes within the network
Knowledge of whether or not multiple transmissions increase ot decrease interference?
Interference Graph can change
as rapidly as the environment
when a node leaves or join the network
. The Transport Layer Problem Majority of the Internet traffic is TCP
Packet losses & delays in wireless can occur due to
Environmental fluctuations resulting link failures
Stochastic link performance due to rapidly changing error rates
CSMA/CA assumes loss is due to congestion and back-off’s
TCP assumes packet losses are due to congestion
Times out when no ACK is received
Invokes slow start, when instead the best response would be to retransmit lost packets quickly
RTT calculation can change as rapidly as the environment (link) changes
Can we solve this problem without changing the end-to-end semantics? . The Security Problem Two type of attackers:
External malicious node (no crypto keys)
Compromised node (attacker captures legitimate node and reads out all cryptographic information)
Attacks
Selfish behavior, do not forward other node’s packets
Denial of Service (DoS)
Jamming
Resource consumption attack
Routing disruption (e.g. Wormhole attack)
Inject malicious routing information
Ongoing Research
Possible solutions: SEAD, Ariadne, SRP, CONFIDANT, … . Hu-MobiCom-2002 Bucheggar-MobiHoc-2002 Packets get dropped! Doesn’t care The Spectrum Etiquette Problem Local behavior affects Global Performance! . Consequently we….. Must Increase Range and Capacity
Single radio meshes built on 802.11 technologies are not good enough. We must extend the range of radios; we must understand the achievable capacity in an ideal wireless mesh and we must build technology to approach this capacity?
Must Improve Routing Performance
Routing protocols based on shortest-hop are sub-optimal. We must build a routing protocol that adapts quickly to topology changes, incorporates wireless interference and link quality.
Must Provide Security and Fairness
Is it possible to ensure fairness and privacy for end-users and security for the network? We must ensure that no mesh nodes starves and that the mesh guards itself against malicious users.
Must Provide Self Management
An “organic network” should be both self-organizing and self managing? To what extent can we remove the human out of the loop?
.
Must Develop a Resilient Framework for Applications
In a environmentally hostile environment, we must provide a framework for applications to work robustly. . Handling the Challenges . Strategies for increasing Capacity Strategy 1: Use all available channels
Avoid spectrum waste
Strategy 2: Improve modulation, reception, and coding
Today ~ 2.5 bits/Hz (.11g), Soon ~ 4.5 bits / Hz (.11n)
Network coding
Strategy 3: Improve spatial reuse by reducing interference
Fine grain transmit power control
(Steerable) directional antennas and directional MACs
Strategy 4: Navigate around harmful interference
Interference aware least cost routing . Will not
cover Strategy 1: Multi-Channel Communications Goal
Assign n non-interfering channels to n pair of nodes such that n packet transmissions can occur simultaneously.
. Knobs Single Radio – Multiple Channels (SR-MC) Distributed: Use a modified RTS/CTS sequence to negotiate channels
Problem
How does the sender know which channel the receiver is listening on?
Solutions
Receive on all channels simultaneously
Simplest solution but too costly - will not consider here
Use a dedicated rendezvous channel
Use a synchronized hopping protocol
Provide multiple rendezvous opportunities
Centralized: Compute channel assignments using global knowledge
Scope of Coverage
We will cover schemes that work on commodity radios only
. Packets-in-Flight Example Revisited Negotiating Channel with RTS / CTS . 2 3 4 5 7 8 9 1 11 10 RTS (C1,C3,C7) RTS (C3,C5,C7,C11)
CTS (C11) CTS (C1, C7) 6 C2 C2 C1 C11 C1 10 nodes are active, 5 packets in flight, 150% improvement! Note: Hidden Terminal – Multi-Channel Case Let C1 be the rendezvous channel
γ can hear traffic on C1 only, doesn’t hear the CTS from β consequently doesn’t know anything about traffic on C6 (δ is too far to hear anything from β) . α β γ δ Possible solution: Use multiple radios So-MobiHoc-2004
Firmware Packets for C6 TCP/IP, Network Stack Packets for C11 Application Layer User-level Kernel-level Buffer packets, switch between channels Packets for C1 802.11 hardware Implementation Option for SR-MC 802.11 Device Driver
Switching logic Channel switching speed:
Today - 5 milliseconds
Possible - 80 microseconds Chandra-INFOCOM-2004 Multi-Channel Medium Access Control (MMAC) .
Divide time into beacon intervals
Divide a beacon interval into two phase
Negotiation Phase: All nodes switch to a pre-defined common channel and negotiate the channel to use
Transfer Phase: Once a channel is selected, the source & receiver switch to this channel and data transfer occurs during this phase Idea: Periodically rendezvous on a fixed channel to decide the next channel Issues
Requires tight clock synchronization
Packets to multiple destinations can incur high delays
Congestion on the common channel
Common channel goes bad, everything goes bad
Not able to handle broadcasts So-MobiHoc-2004 Slotted Seeded Channel Hopping (SSCH) Divide time into slots
At each slot hop to a different channel
Nodes hop across channels to distribute traffic
Senders and receivers probabilistically meet & exchange schedules
Senders loosely synchronize hopping schedule to receivers
Characteristics
Distributed: every node makes independent choices
Optimistic: exploits common case that nodes know each others’ channel hopping schedules
Traffic-driven: nodes repeatedly overlap when they have packets to exchange . Bahl-MobiCom-2004 Divide time into slots: switch channels at beginning of a slot 3 channels
E.g. for 802.11b
Ch 1 maps to 0
Ch 6 maps to 1
Ch 11 maps to 2 1 0 2 1 0 2 1 0 0 1 2 0 1 2 0 1 New Channel = (Old Channel + seed) mod (Number of Channels)
seed is from 1 to (Number of Channels - 1) Seed = 2 Seed = 1 (1 + 2) mod 3 = 0 (0 + 1) mod 3 = 1 A B Enables bandwidth utilization across all channels
Does not need control channel rendezvous . SSCH Rendezvous Each node broadcasts (channel, seed) once every slot
If B has to send packets to A, it adjusts its (channel, seed) Stale (channel, seed) info simply results in delayed syncing 3 channels 1 0 2 1 0 2 1 0 2 0 2 1 0 2 1 0 Seed Seed A B 2 2 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 1 1 B wants to start a flow with A . SSCH Syncing Seeds Using all Available Channels with SSCH Only one of 3 pairs is active @ any given time In current IEEE 802.11 meshes . SSCH Performance Significant capacity improvement when traffic load is on multiple separate flows 100 nodes, IEEE 802.11a, 13 channels, every flow is multihop Avg. per node Throughput Total System Throughput SSCH SSCH IEEE 802.11a IEEE 802.11a . How many Channels can we really use?
IEEE 802.11{b,g} partitions the allocated 83.5 MHz spectrum into 11 channels
Only channels 1, 6 and 11 are mutually non-overlapping
But…using only the orthogonal channels may waste spectrum . Banerjee-SIGMETRICS-2006 How many Channels can we really use?
Can we use more channels by using partially-overlapped channels?
Caution: may increase interference and cause more harm than good
Need an appropriate model to capture interference-effects and make correct choices
Overlapped Channels do work! Link A, Channel 1 Link B, Channel Y Distance
(X-axis) ChSep = 0 ChSep = 1 ChSep = 2 ChSep = 5 Minimum distance between links for different choices of channel separation
For every channel separation there is a minimal distance
Model-based algorithmic approach for channel assignment in wireless mesh networks . Notes on Single Radio – Multiple Channels Single radio solutions can be applied to multi-radios nodes since in most cases the number of channels is greater than the number of radios in the node.
Compared to multi-radio solutions, single radio solutions are power efficient – but power is not the primary concern in most mesh networks
Single radio solutions are less costly than multi-radio solutions but radios are fairly inexpensive
Switching speeds and mute-deaf-time is a problem in single radio solutions but switching speeds are being reduced dramatically
When distance between nodes is large, need not restrict operation to non-overlapping channels only …so now lets look at multi-radio solutions . Single Node Multiple Radio - Interference Study Question:
Do two radios operating on non-overlapping channel interfere?
Experimental setup: A B C D TCP TCP 6” separation between B & C radios HOP 1 HOP 2 . 802.11a/g Interference Results
Same channel or channel separation of 4 causes 46% - 49% reduction in overall throughput 802.11a link causes a 22%
reduction in overall throughput,
and a 63% reduction in
throughput on the 802.11g link.
Surprise: 802.11g does not affect 802.11a Implications
Interference even when radios are placed 6” apart is significant
Significant RF hardware shielding work is needed . Single Node Multiple Radios Let’s assume we can build “mesh-boxes” with enough separation / shielding between radios that performance does not suffer.
Then interesting problem to consider
(1) How should we assign channels to each interface?
Don’t want to cause network partitions
(2) Which interface should we send the packet on?
State-of-art metrics (hop count, ETX, SRTT, packet-pair) are not suitable for multiple radio / node. As they do not leverage channel, range, data rate diversity.
. Multiple Radios - Multiple Channels Options to consider
Static Assignment
One channel / radio for all time
Suboptimal use of spectrum
Some routes may be suboptimal
Dynamic Assignment (all SR-MC strategies apply)
Channels assigned to match traffic patterns and/or to reduce interference
Interference patterns can change,
network may get disconnected
Hybrid Assignment
One channel to one radio for all time, for all other radios, channels are assigned dynamically to match traffic patterns and/or reduce interference . 11 1 1 11 11 1 1 11 11 Static Assignment (1) B C D E F 2 radios / node All nodes use common set of channels Suboptimal use of spectrum Draves-MobiCom-2004 . A 11 1 64 60 60 52 52 60 56 52 Static Assignment (2) A B C D E F 2 radios / node, 4 channels Different nodes use different channels Some routes may be suboptimal (e.g. B->F) Raniwala-Infocom-2005 . Dynamic Assignment B C D E F Coordination may be needed before each transmission N radios / node; M channels; N < M
Interfaces can switch channels as needed A . MMAC
SSCH
BFS-CA See section on single radio – multiple channels Breadth First Search – Channel Assignment (BFS-CA) Goals:
External interference can severely degrade mesh performance
Measure & avoid external interference
Internal interference between mesh links should be avoided
Assign orthogonal channels to any two interfering mesh links
Nodes periodically estimate surrounding interference levels
A radio per-node monitors 802.11 data and control traffic
Channels ranked from least interfered to most interfered
Ranking sent to centralized channel assignment server
Distributed channel sensing and channel assignment
can break network connectivity
A radio per-router is tuned to a common channel to
ensure connected mesh
Ramachandran-Infocom-2006 . Dynamic Assignment BFS-CA Interference-Aware Channel Assignment Multi-radio conflict graph models interference between mesh links
Breadth first search algorithm selects channels for mesh radios
Significant performance improvement over static channel assignment in the presence of varying interference levels
Issues
Interference patterns can change rapidly
Dependence on existance of traffic patterns to determine interferance
Incorrect channel assignment possible
. Hybrid Multichannel Control Protocol (HMCP) Each node has two interfaces (1 fixed, 1 switch-able)
Connectivity is maintained + all channels used
Every node picks a channel as it’s fixed channel
Different nodes use different fixed channels
Sender tunes it’s “switchable” interface to receiver’s fixed channel to send packets
Once a “connection” is made, there may not be a reason to switch channels again for that particular flow.
. Hybrid Assignment Kyasanur-WCM-2006 HMCP Channel Selection Challenge: Nodes in a neighborhood should use different fixed channels
Fixed Channel Selection
On startup pick a random fixed channel
Periodically send a “hello” pkt. containing fixed channel & 1-hop neighbors info. on all channels (using the switchable interface)
Maintain a NeighborTable containing fixed channels being used by neighbors
Select the channel with fewest nodes as a candidate
Use 2-hop neighbor information
Change fixed channel to candidate channel probabilistically to avoid oscillations
Issues
High overhead for broadcast packets
. Which Interface should we send the packet on? A Simple Approach: For every transmission select the interface with the “best” channel & transmit on it
Multi-Radio Unification Protocol (MUP)
Pros:
- Locally optimizes use of available spectrum
- Does not require changes to routing protocols or application-level software
- Interoperates with legacy hardware
- Does not require global topology information
Cons:
For one-hop ad hoc – works great. For meshes need metrics that combine link selection metrics into a path selection metric (will see) . Adya-BroadNets-2004 Goal
Allow nodes with multiple radios to locally optimize use of available spectrum and hence increase capacity
Operation
Set the network interface cards on different
frequency channels
Periodically monitor channel / Link
quality on each interface
Select the interface with the “best” channel
and transmit packets Illustration of Channel Switching Ch. 0 Ch. 1 . Adya-BroadNets-2004 Does not require global topology information
MultiRadio Unification Protocol (MUP) 0 1 MUP in a Neighborhood 252 houses in a Seattle neighborhood
(Green Lake Area) Mesh formation among 35
randomly selected houses Routes via RFC 3561 (AODV) ITAP Web surfer 40-50% reduction in delay
compared to a one-radio network . Why MUP is not enough? MUP is a link metric not a path metric. Routing protocols that use MUP do not
Leverage channel diversity
A two hop path with hops on different channels is better than a path with both hops are on the same channel.
Leverage range and data rate diversity
A path with two 6 Mbps hops is better than a path with a single 1 Mbps hop. MUP will take the 1Mbps path.
…..but a path with four 6 Mbps hops is worse than a path with a single 2 Mbps hop. MUP and metrics like ETX may take the four-hop path, depending on delay & loss rate.
Note: Striping protocols are not enough
Packet-level striping results is packet reordering, and hence poor TCP throughput
Flow-level striping requires a routing algorithm!
MUP may work, but only if radios have identical range.
Bottom Line: Need a routing protocol / metric that takes bandwidth, loss rate, and channel diversity into account. . …about routing in mesh networks The Routing Problem Why not simply use traditional routing protocols (RIP/OSPF/etc)?
Network topologies are dynamic due to router mobility & environmental fluctuations
Dynamic topology may prevent routing protocol convergence
Many links are redundant (routing updates can be large)
Periodic updates may waste bandwidth & batteries
Computed routes may not work due to unidirectional links
Wireless makes routing protocols easy to attack
Link quality, spectrum utilization and interferences are uniquely important for path selection . Desirable Qualitative Properties Distributed operation
Loop-freedom
Demand-based operation
Proactive operation
Attack resistant & Secure
“Sleep” period operation (friendly to power management)
Unidirectional link support / asymmetric link support
Implementation
Layer 3 - traditional “network layer” / IP layer
Interoperable internetworking capability and consistency over a heterogeneous networking infrastructure.
Layer 2.5
Agnostic of IPv4 or IPv6 issues and can incorporate link quality measures more easily
Capable of handling multiple wireless & wired networking technologies . Corson-RFC2501-1999 Routing and Addressing Many choices, which is the best one?
Flat addressing - Each node runs the routing protocol; node’s address is independent of its location (e.g. PRNET, TORA, DSR, AODV,..)
Clustering – Only cluster heads run routing protocol; addressing is flat and independent of node’s location (NTDR, CEDAR,..)
Hierarchical – Only cluster heads run routing protocol, a node’s form subnets, each node acquire’s address of its subnet (SURAN).
Many protocols to consider
See next
Multiple path routing
Many choices: MSDR, AOMDV, AODV-BR, APR, SMR, ROAM, …. . Bucketizing Routing Protocols Proactive (periodic)
Each node maintains route to each other network node (Global state)
Routes are determined independent of traffic
All topology changes propagated to all nodes
Periodic routing advertisements (neighbor discovery is beacon based)
Generally longer route convergence time
Examples: Distance vector and link state (DSDV, OLSR, TBRPF)
Reactive (on-demand)
Actions driven by data packet requiring delivery
Source builds route only when needed by “flooding” (Route Discovery)
Maintain only active routes (Route Maintenance)
Pro: Typically less overhead, better scaling properties
Cons: Route acquisition latency
Examples: DSR, AODV
Conventional Wisdom
Proactive protocols perform best in networks with low to moderate mobility, few nodes and many data sessions
E.g. OLSR (RFC 3626), TBRPF (RFC 3684)
Reactive protocols perform best in resource-limited, dynamic networks where nodes are mobile. Tradeoff routing overhead for start-up delay
E.g. AODV (RFC 3561), DSR (IETF Draft) Popular Taxonomy . Mapping Protocols to Taxonomy . Common Metrics for Comparing Routing Protocols Route Acquisition Time
Time required to establish route(s)
Routing Overhead
Total number of routing packets transmitted (for discovery & maintenance) for a fixed amount of transfer over multiple hops with random node mobility.
Path Optimality / End-to-End Throughput
TCP & UDP data throughput and delay
Previously path optimality was measured in terms of the difference between the number of hops a packet took to reach it’s destination and the length of the shortest path that physically existed through the network when the packet originated. However, the hop count metric has been overshadowed by other link metrics when it came to end-to-end throughput
Packet Delivery Ratio
Ratio between the number of packets originated by the application layer and the number of packets received by the sink at the final destination . Broch-MobiCom-1998 Context for Comparing Metrics Network size
Measured in terms of the number of nodes
Network connectivity
Measured in terms of avg. node degree (i.e. the avg. number of neighbors)
Topological rate of change
Speed with which a network's topology changes
Link capacity
Effective link speed in bps, after accounting for losses due to multiple access, coding, framing, etc.
Fraction of unidirectional links
Transmission ranges of radios may be different
Traffic patterns
Long-lived versus bursty non-uniform
Mobility
Described in terms of dwell time, movement direction, speed etc.
Fraction and frequency of sleeping nodes . Corson-RFC2501-1999 Link / Path Selection Metrics Min. hop count results in lower-quality links Incorporate metric into routing protocols Path Selection Metrics Link Metric: Assign a weight to each link
Prefer high bandwidth, low-loss links
RTT, Packet Pair, ETX
Metrics such as shortest path, RTT, Packet Pair, ETX etc. do not leverage channel, range, data rate diversity
Path Metric: Combine metrics of links on path
Prefer short, channel-diverse paths
WCETT
. Expected Transmission Count (ETX) Link Selection Metric for Single Radio Meshes Each node periodically broadcasts a probe
The probe carries information about probes received from neighbors
Each node can calculate loss rate on forward (Pf) and reverse (Pr) link to each neighbor
Selects the path with least total ETX
Advantages
Explicitly takes loss rate into account
Implicitly takes interference between successive hops into account
Low overhead
Disadvantages
PHY-layer loss rate of broadcast probe packets is not the same as PHY-layer loss rate of data packets
Broadcast probe packets are smaller
Broadcast packets are sent at lower data rate
Does not take data rate or link load into account
. Couto-MobiCom-2003 Given:
Loss rate p
Bandwidth B
Mean packet size S
Min backoff window CWmin
Takes bandwidth and loss rate of the link into account
Expected Transmission Time (ETT) Link Selection Metric for Single Radio Meshes Weighted Cumulated ETT (Combine link ETTs) Link Selection Metric for Multi-Radio Meshes Given a n hop path, where each hop can be on any one of k channels, and two tuning parameters, a and b: Select the path with min WCETT Sum of ETTs of all links on the path
- Favors short paths Sum of ETTs of all links on the path that are on the same channel Path throughput is dominated by the max
of the sum of ETTs of path links on the
same channel Draves-MobiCom-2004 Takes bandwidth, loss rate and channel diversity into account Path Length and Throughput Which metric is best? (“Wireless Office Study”) Experimental Setup
23 node testbed
Randomly selected 100 sender-receiver pairs (out of 23x22 = 506)
3-minute TCP transfer (transmit as many bytes as possible in 2 minutes, followed by 1 minute of silence)
For 1 or 2 hop the choice of
metric doesn’t matter Eriksson-MobiSys-2006 . Comparison of Metrics Wireless Office Scenario 23 node indoor testbed. Two radios (both 802.11a) per node.
11 active clients, 4 servers. Heavy Office Traffic
1 hour, 308 sessions, 587.5 MB total Light Office Traffic
1 hour, 415 sessions, 19.72 MB total Relatively light traffic means performance is okay for all metrics.
WCETT does better under heavy load (worst case delay) . Eriksson-MobiSys-2006 Summarizing Many routing protocols to choose from
Protocols that take link quality into account show most promise
A link quality metric that incorporates interference is still needed
Adaptive protocols that change behavior in different environments might be best
. Additional Areas of Research Active Areas of Research Analytical tools for calculating mesh capacity
Flow-level and packet-level fairness
Network management & automatic diagnosis of faults
Network coding for capacity improvement
Routing with directional antennas / routing for network coding
Supporting VoIP & video traffic over meshes
Inexpensive software steerable directional antennas
Smart medium access control
Meshing with cognitive radios
Multi-spectral meshes
Delay tolerant meshing
Usage scenarios . Q/A Thanks! For prior work & updates, check out: http://research.microsoft.com/nrg/ Complete tutorial notes available on my web site:
http://research.microsoft.com/~bahl References Papers are categorized under subject area. Duplication is possible because some papers include more than one problem/solution pair. This is not a exhaustive list. List is not exhausted (was prepared at least 2 years ago) References - Testbeds
UMASS’s DieselNet
[Zhao-MASS-2006] Wenrui Zhao, Yang Chen, Mostafa Ammar, Mark Corner, Brian N. Levine, and Ellen Zegura. Capacity Enhancement using Throwboxes in DTNs, IEEE Intl Conf on Mobile Ad hoc and Sensor Systems (MASS), Oct 2006.
[Partan-WUWNet-2006] Jim Partan, Jim Kurose, Brian N. Levine, A Survey of Practical Issues in Underwater Networks. ACM Intl Wkshp on Underwater Networks (WUWNet), September 2006
[Jun-ACHANTS-2006] Hyewon Jun, Mostafa Ammar, Mark Corner, Ellen Zegura. Hierarchical Power Management in Disruption Tolerant Networks with Traffic-Aware Optimization, ACM CHANTS. September, 2006.
[Burgess-INFOCOM-2006] John Burgess, Brian Gallagher, David Jensen, and Brian N. Levine. MaxProp: Routing for Vehicle-Based Disruption-Tolerant Networks, IEEE INFOCOM, April 2006.
[Burns-ICRA-2006] Brendan Burns, Oliver Brock, and Brian N. Levine. Autonomous Enhancement of Disruption Tolerant Networks, IEEE Intl Conf on Robotics and Automation (ICRA), May 2006.
[Burns-INFCOMM-2005] Brendan Burns, Oliver Brock, and B.N. Levine. MV routing and capacity building in disruption tolerant networks., IEEE INFOCOM, March 2005.
[Hanna-ICNP-2003] Kat Hanna, Brian N. Levine, and R. Manmatha. Mobile Distributed Information Retrieval For Highly Partitioned Networks, IEEE ICNP, November 2003.
. References - Testbeds IITK’s Digital Gangetic Plains
[Chebrolu-MobiCom-2006] Kameswari Chebrolu, Bhaskaran Raman, and Sayandeep Sen, Long-Distance 802.11b Links: Performance Measurements and Experience, 12th Annual International Conference on Mobile Computing and Networking (MOBICOM), Sep 2006, Los Angeles, USA.
[Raman-MobiCom-2005] Bhaskaran Raman and Kameswari Chebrolu, Design and Evaluation of a new MAC Protocol for Long-Distance 802.11 Mesh Networks, 11th Annual International Conference on Mobile Computing and Networking (MOBICOM), Aug/Sep 2005, Cologne, Germany.
[Bhagwat-HotNets-2003] Pravin Bhagwat, Bhaskaran Raman, and Dheeraj Sanghi, Turning 802.11 Inside-Out, Second Workshop on Hot Topics in Networks (HotNets-II), 20-21 Nov 2003, Cambridge, MA, USA.
MIT’s RoofNet
[Briket-MobiCom-2005] John Bicket, Daniel Aguayo, Sanjit Biswas, and Robert Morris, Architecture and Evaluation of an Unplanned 802.11b Mesh Network, ACM MobiCom 2005.
[Biswas-SIGCOMM-2005] Sanjit Biswas and Robert Morris, Opportunistic Routing in Multi-Hop Wireless Networks, ACM SIGCOMM 2005
[Aguayo-SIGCOMM-2004] Daniel Aguayo, John Bicket, Sanjit Biswas, Glenn Judd, Robert Morris, Link-level Measurements from an 802.11b Mesh Network, SIGCOMM 2004, Aug 2004
[Couto-MobiCom-2003] Douglas S. J. De Couto, Daniel Aguayo, John Bicket, Robert Morris, A High-Throughput Path Metric for Multi-Hop Wireless Routing, ACM Mobicom 2003 . References - Testbeds MSR’s Mesh Network
[Qiu-CCR-2006] Lili Qiu, Paramvir Bahl, Ananth Rao, Lidong Zou, “Troubleshooting Wireless Meshes”, ACM Computer Communications Review 2006
[Eriksson-MobiSys-2006] Jacob Eriksson, Sharad Agarwal, Paramvir. Bahl, Jitendra Padhye, Feasibility Study of Mesh Networks for All-Wireless Offices, ACM/USENIX MobiSys, Uppsala, Sweden, June 2006
[Kyasanpur-Broadnets-2005] Pradeep Kyasanur, Jitendra Padhye, Paramvir Bahl, On the Efficacy of Separating Control and Data into Different Frequency Bands, IEEE BroadNets 2005 , Boston, Massachusetts, USA (October 2005)
[Padhye-IMC-2005] Jitendra Padhye, Sharad Agarwal, Venkata Padmanabhan, lili Qiu, A. Rao, Brian Zill, “Estimation of Link Interference in Static Multi-hop Wireless Networks”, ACM Internet Measurement Conference 2005, October 2005
[Kuga-NRSM-2004] Y Kuga, J. Cha, J. A. Ritcey, James Kajiya, Mechanically Steerable Antennas Using Dielectric Phase Shifters, IEEE AP-S International Symposium and USNC/URSI National Radio Science Meeting, June 2004
[Qiu-ICNP-2004] Lili Qiu, Ranveer Chandra, Kamal Jain, M. Mahdian, Optimizing the Placement of Integration Points in Multi-hop Wireless Networks, IEEE ICNP 2004.
[Draves-MobiCom-2004] Richard Draves, Jitendra Padhye, Brian Zill, Routing in Multi-radio, Multi-hop Wireless Mesh Networks, ACM MobiCom, Philadelphia, PA, September 2004.
[Bahl-MobiCom-2004] Paramvir Bahl, Ranveer Chandra, John Dunagan, SSCH: Slotted Seeded Channel Hopping for Capacity Improvement in IEEE 802.11 Ad-Hoc Wireless Networks, ACM MobiCom, Philadelphia, PA, September 2004.
[Draves-SIGCOMM-2004] Richard Draves, Jitendra Padhye, Brian Zill, Comparison of Routing Metrics for Static Multi-Hop Wireless Networks, ACM SIGCOMM, Portland, OR, August 2004.
. References - Testbeds MSR’s Mesh Network
[Qiu-MSRTR-2003] Lili Qiu, Paramvir Bahl, A. Rao, Lidong Zhou, Fault Detection, Isolation, and Diagnosis in Multi-hop Wireless Networks, Microsoft Research Technical Report, TR-2004-11
[Jain-MobiCom-2003] K. Jain, J. Padhye, V. Padmanabhan, and L. Qiu, Impact of Interference on Multi-hop Wireless Network Performance, ACM MobiCom, San Diego, CA, September 2003
Rice’s TFA
[Camp-MobiSys-2006] Joseph Camp, J. Robinson, C. Steger, Edward Knightly, "Measurement Driven Deployment of a Two-Tier Urban Mesh Access Network," in Proceedings of ACM MobiSys 2006, Uppsala, Sweden, June 2006.
[Camp-DC-2005] Joseph Camp, Edward Knightly, W. Reed, "Developing and Deploying Multihop Wireless Networks for Low-Income Communities," in Proceedings of Digital Communities 2005, Napoli, Italy, June 2005.
JHU’s SMESH
[Amir-MobiSys-2006] Yair Amir, Claudiu Danilov, Michael Hilsdale, Raluca Musaloiu-Elefteri, Nilo Rivera, “Fast Handoff for Seamless Wireless Mesh Networks”, ACM/USENIX MobiSys 2006, June 2006 . Purdue’s Mesh
[Das-JSAC-2006] Saumitra M. Das, Himabindu Pucha, Dimitrios Koutsonikolas, Y. Charlie Hu, Dimitrios Peroulis, “DMesh: Incorporating Practical Directional Antennas in Multi-Channel Wireless Mesh Networks”, IEEE Journal on Selected Areas in Communications (JSAC 06) special issue on Multi-Hop Wireless Mesh Networks, 2006.
[Das-mobicom_wintech-2006] Saumitra M. Das, Dimitrios Koutsonikolas, Y. Charlie Hu, Dimitrios Peroulis, “Characterizing Multi-Way Interference In Wireless Mesh Networks”, ACM MobiCom International Workshop on Wireless Network Testbeds, Experimental evaluation and Characterization (MobiCom WiNTECH 06), Los Angeles, CA, September 29, 2006. References - Testbeds . References - Fairness [Nandagopal-MobiCom-2000] Thyagarajan Nandagopal, Tae-Eun Kim, Xia Gao, Vadhuvar Bharghavan, “Achieving MAC Layer Fairness in Wireless Packet Networks,” ACM MobiCom 2000, August 2000
[Luo-MobiCom-2000] Haiyun Luo, Songwu Lu, Vadhuvar Bharghavan, “A New Model for Packet Scheduling in Multihop Wireless Networks”, ACM MobiCom 2000, August 2000 References – Capacity / Channelization [MSBA-SIGMETRICS-2006] Arunesh Mishra, Vivek Shrivastava, Suman Banerjee, William Arbaugh, Partially-overlapped Channels not Considered Harmful, ACM SIGMETRICS, June 2006.
[Ramachandran-Infocom-2006] K. Ramachandran, E. Belding, K. Almeroth, M. Buddhikot, “Interference-Aware Channel Assignment in Multi-Radio Wireless Mesh Networks”, IEEE Infocom, Barcelona, Spain, April 2006
[Kyasanur-WCM-2006] Pradeep Kyasanur, Jungmin So, Chandrakanth Chereddi, and Nitin H. Vaidya, "Multi-Channel Mesh Networks: Challenges and Protocols", IEEE Wireless Communications, April 2006
[Kyasanur-BroadNets-2005] Pradeep Kyasanur, Jitendra Padhye, and Paramvir Bahl, "On the Efficacy of Separating Control and Data into Different Frequency Bands", in IEEE Broadnets, Boston, MA, October 2005
[Raniwala-Infocom-2005] Ashish Raniwala and Tzi-cker Chiueh, “Architecture and Algorithms for an IEEE 802.11-based Multi-Channel Wireless Mesh Network”, IEEE INFOCOM, 2005
Alicherry-MobiCom-2005] Mansoor Alicherry, Randeep Bhatia, Li Li, “Joint Channel Assignment and Routing for Throughput Optimization in Multi-radio Wireless Mesh Networks”, ACM MobiCom 2005, September 2005
[Kodialam-MobiCom-2005] Muralidharan Kodialam, Thyaga Nandagopal, “Characterizing the Capacity Region in Multi-Radio, Multi-Channel Wireless Mesh Networks”, ACM MobiCom 2005, September 2005
. References – Capacity / Channelization [Kyasanur-MobiCom-2005] Pradeep Kyasanur, Nitin Vaidya, Capacity of Multi-Channel Wireless Networks: Impact of Number of Channels and Interfaces”, ACM MobiCom 2005, September 2005
[Adya-BroadNets-2004] Atul Adya, Paramvir Bahl, Jitendra Padhye, Alec Wolman, and Lidong Zhou, “A Multi-Radio Unification Protocol for IEEE 802.11 Wireless Networks”, IEEE BroadNets 2004.
[Bahl-MobiCom-2004] Paramvir Bahl, Ranveer Chandra, John Dunagan, “SSCH: Slotted Seeded Channel Hopping for Capacity Improvement in IEEE 802.11 Ad-Hoc Wireless Networks”, ACM MobiCom, Philadelphia, PA, September 2004
[So-MobiHoc-2004], Jungmin So, Nitin Vaidya, “Multi-Channel MAC for Ad Hoc Networks: Handling Multi-Channel Hidden Terminals Using A Single Transceiver”, ACM MobiHoc 2004, Tokyo, Japan, May 2004
[Jain-MobiCom-2003] Kamal Jain, Jitendra Padhye, Venkata Padmanabhan, and Lili Qiu, “Impact of Interference on Multi-hop Wireless Network Performance”, ACM MobiCom, San Diego, CA, September 2003
[Jinyang-MobiCom-2001] Jinyang Li, Charles Blake, Douglas S. J. De Couto, Hu Imm Lee, and Robert Morris, Capacity of Ad Hoc Wireless Networks, ACM MobiCom '01), Rome, Italy, July 2001
[Gupta-IEEEIT-2000] Piyush Gupta, P. R. Kumar, “Capacity of Wireless Networks”, IEEE Transactions on Information Theory, March 2000.
[Wu-ISPAN-2000] S.L. Wu, C.Y. Lin, Y.C. Tseng, J.P. Sheu, “A New Multi-Channel MAC Protocol with On-Demand Channel Assignment for Mobile Ad Hoc Networks”, International Symposium on Parallel Architectures, Algorithms and Networks (I-SPAN), 2000
. References - Routing IETF Standards
[Corson-RFC2501-1999] Scott Corson, Joseph Macket, “Mobile Ad hoc Networking (MANET): Routing Protocol Performance Issues and Evaluation Considerations”, IETF RFC 2501, January 1999
[Perkins-RFC3561-2003] Charlie Perkins, Elizabeth Beilding-Royer, Samir Das, “Ad Hoc On Demand Distance Vector (AODV) Routing”, IETF RFC 3561, July 2003
[Clausen-RFC3626-2003] T. Clausen, P. Jacquet, “Optimized Link State Routing Protocol (OLSR)”, IETF RFC 3626, October 2003
[Ogier-RFC3684-2004] R. Ogier, Fred Templin, Mark Lewis, “Topology Dissemination Based on Reverse-Path Forwarding (TBRPF)”, IETF RFC 3684, February 2004
[Johnson-RFC4728-2007] D. Johnson, Y. Hu, D. Maltz, “The Dynamic Source Routing Protocol (DSR) for Mobile Ad Hoc Networks for IPv4”, IETF RFC 4728, February 2007
Papers & Drafts
[Biswas-SIGCOMM-2005] Sanjit Biswas and Robert Morris, Opportunistic Routing in Multi-Hop Wireless Networks, ACM SIGCOMM 2005
[Draves-SIGCOMM-2004] Richard Draves, Jitendra Padhye, Brian Zill, Comparison of Routing Metrics for Static Multi-Hop Wireless Networks, ACM SIGCOMM, Portland, OR, August 2004.
[Johnson-Draft-2004] David B. Johnson, David A. Maltz, Yih-Chun Hu, “The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks (DSR)”, IETF Draft, July 2004
[Ni-MobiCom-1999] S. Ni, Y. Tseng, Y. Chen, J. Chen, “The Broadcast Storm Problem in a Mobile Ad Hoc Network,” ACM MobiCom ’99, Seattle, Washington, August 1999 . References - Routing Papers & Drafts
[Alicherry-MobiCom-2005] Mansoor Alicherry, Randeep Bhatia, Li Li, “Joint Channel Assignment and Routing for Throughput Optimization in Multi-radio Wireless Mesh Networks”, ACM MobiCom 2005, September 2005
[Couto-HotNets-2002] Douglas De Couto, Daniel Aguayo, Benjamin Chambers, Robert Morris, “Performance of Multihop Wireless Networks: Shortest Path is Not Enough”, First Workshop on Hot Topics in Networks (HotNets-I), October 2002
[Broch-MobiCom-1998] Josh Broch, David A. Maltz, David B. Johnson, Yih-Chun Hu, and Jorjeta Jetcheva. “A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocol”,. ACM MobiCom'98, Oct. 1998.
[Perkins-CCR-1994] Charlie Perkins and Pravin Bhagwat, “Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers,”, Computer Communications Review 24(4), Oct. 1994
. References – Security & Management [Qiu-CCR-2006] Lili Qiu, Paramvir Bahl, Ananth Rao, Lidong Zou, “Troubleshooting Wireless Meshes”, ACM Computer Communications Review 2006
[Badonnei-JNM-2005] Remi Badonnel, Radu State, Olivier Festor “Management of Mobile Ad Hoc Networks: Information Model and Probe-based Architecture”, International Journal of Network Management, Vol. 15, Issue 5, September 2005
[Kyasanur-TMC-2005] Pradeep Kyasanur, Nitin Vaidya, “Selfish MAC Layer Misbehavior in Wireless Networks”, IEEE Transactions on Mobile Computing, Vol. 4, Issue 4, September 2005
[Hu-Infocom-2003] Yih-Chun Hu, Adrian Perrig, David B. Johnson, “Packet Leashes: A Defense Against Wormhole Attacks in Wireless Ad Hoc Networks,”, IEEE INFOCOM 2003
[Qiu-MSRTR-2003] Lili Qiu, Paramvir Bahl, A. Rao, Lidong Zhou, Fault Detection, Isolation, and Diagnosis in Multi-hop Wireless Networks, Microsoft Research Technical Report, TR-2004-11
[Shen-Milcom-2002] C.-C. Shen, C. Jaikaeo, C. Srisathapornphat, Z. Huang, “The GUERILLA Management Architecture for Ad Hoc networks”, IEEE MILCOM 2002, Oct. 2002
[Hu-MobiCom-2002] Yih-Chun Hu, Adrian Perrig, David B. Johnson, “Ariadne: A Aecure On-Demand Routing Protocol for Ad Hoc Networks”, ACM MobiCom 2002, Atlanta, GA
[Bucheggar-MobiHoc-2002] S. Buchegger, J. Y. Le Boudec, “Performance Analysis of the CONFIDANT Protocol”, ACM MobiHoc 2002
[Marti-MobiCom-2000] Sergio Marti, T. J. Giuli, Kevin Lai, Mary Baker, “Mitigating Routing Misbehavior in Mobile Ad Hoc Networks”, ACM MobiCom 2000, Boston, MA
[Zhang-MobiCom-2000] Yongguang Zhang , Wenke Lww, “Intrusion Detection in Wireless Ad Hoc Networks”, ACM MobiCom 2000, Boston, MA
[Chen-JSAC-1999] Wenli Chen, Nitin Jain, Suresh Singh, “ANMP: Ad Hoc Network Management Protocol”, IEEE Journal on Selected Areas in Communications, Volume 17 Number 8, August 1999 . References - General Network Management
[Badonnel-JTS-2005] Remi Badonnel, Radu State, Olivier Festor, “Self-Organized Monitoring of Ad Hoc Networks”, Journal of Telecommunications Systems, Vol. 30, No. 1-3, 2005
General
[Andel-Computer-2006] Todd R. Andel, Alec Yasinsac, “On the Credibility of MANET Simulations”, IEEE Computer Magazine, pp. 48-54, 2006
[IEEE-Mesh-2006] Joint SEE-Mesh/Wi-Mesh Proposal to 802.11 TGs Overview”, IEEE 802.11-06/0329r2, March 6, 2006
[Karn-CNC-1997] Phil Karn, “MACA – A New Channel Access Method for Packet Radio”, in Proceedings of AARL/CRRL Amateur Radio 9th Computer Networking Conference, Sept. 1997
[Powers-Proc-1995] R. A. Powers. “Batteries for Low Power Electronics”, Proceedings of the IEEE,, April 1995
[Tobagi-Comm-1975] F. A. Tobag, L. Klienrock, “Packet Switching in Radio Channels: Part II – The hidden Terminal Problem in a Carrier Sense Multiple-Access Modes and Busy-Tone Solution”, IEEE Transaction Communications, Vol. COM-23, no. 12, 1975
.
|