Transcript September 2004

September 2004
doc.: IEEE 802.11-04/1042r0
Routing in Mesh Networks
Myung. J Lee, Chunhui Zhu
Samsung Lab @ CUNY
{lee, zhuc}@ccny.cuny.edu
Submission
Slide 1
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
Outline
• Definitions of Mesh Network
• Features of Mesh Network
• Desirable Qualitative Properties
(IETF)
• Quantitative Metrics
• Basic Classifications
• Non-MANET Routing Protocols
– Geographical and Position-based
Routing
– Directional Antenna Based
Routing
– Power, Link Quality and other
Cost-based Routing
– Multi-path Routing and Load
Balancing
– Binary Tree Routing
– Virtual Backbone Based Routing
– Sensor Network Routing
– Layer 2 Data Forwarding
– Layer 2.5 Routing
– Proactive, Reactive and Hybrid
– Single-path and Multi-path
– Flat and Hierarchical
• Basic Components of Routing
Protocols
• IETF & IRTF Activities
Submission
Slide 2
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
Mesh Network
• General definition
– Mobile Ad Hoc Networks (MANET)
• Strict definition
– Mesh routes (multiple routes) exist between each
source-destination pairs
• The application this group is considering
– Some nodes are infrastructure nodes (e.g. APs) and
others are client nodes (mobile user devices) [1]
Submission
Slide 3
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
Features of Mesh Network
•
•
•
•
•
•
•
Infrastructure-less/Peer-to-Peer
Multi-hop – nodes need to relay packets for others
Random and dynamic topologies (e.g., mobility)
Bandwidth-constrained, variable capacity links
Lossy, unstable and asymmetric wireless links
Battery-powered nodes and sleeping nodes
MAC layer dependant (e.g. hidden terminal problem of
802.11)
• Different antenna (omni-directional, directional)
• Limited physical security
• etc
 All these affect the design of a routing protocol
Submission
Slide 4
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
Desirable Qualitative Properties
• Listed by IETF [2]
– Distributed operation
– Loop-freedom
– Demand-based operation and/or Proactive
operation
– Security
– "Sleep" period operation
– Unidirectional link support
Submission
Slide 5
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
Quantitative Metrics
• IETF Metrics [2]
–
–
–
–
End-to-end data throughput and delay
Route Acquisition Time (on-demand routing)
Percentage Out-of-Order Delivery
Efficiency
• Data Bit Efficiency: Data bits transmitted/data bit delivered
• Control Overhead: Control bits transmitted/data bit delivered
• Channel Access Efficiency: Control and data packets
transmitted/data packet delivered
• Other Protocol-Specific Metrics
– Power consumption and network lifetime
– Link quality and etc.
Submission
Slide 6
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
Basic Classifications (1)
• Proactive protocols
– Maintaining route map of all nodes
– Example protocols: DSDV[11], OLSR[12], FSR[13]
• Reactive protocols
– Adapting to the traffic pattern on a demand or need basis
– Example protocols: DSR[14], AODV[15]
• Hybrid protocols
– Proactive for nearby nodes while reactive for distant nodes
– Example protocols: ZRP[16]
Submission
Slide 7
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
Basic Classifications (2)
• Single Path
– There exists only one route between a sourcedestination pair
• Multiple Path
– More than one route between a source-destination
pair are created and maintained
– Two types of Multi-path routing
• Node disjoint routes
• Link disjoint routes
Submission
Slide 8
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
Basic Classifications (3)
• Flat
– All nodes are equivalent in routing functions
• Hierarchical
– The whole network is divided into multiple
clusters
– Cluster heads have more functions than regular
nodes in routing
– Suitable for large networks whose scalability are
concerned
Submission
Slide 9
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
Basic Components of
Routing Protocols
1.
2.
3.
4.
5.
6.
7.
Neighbor discovery and maintenance
Route discovery
Route selection
Route representation
Route maintenance
Failure response and route repair
Data forwarding
Submission
Slide 10
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
1. Neighbor discovery and
maintenance
• Functions:
– The base of most mesh network routing protocols
– Link breakage detection
– Calculating relay nodes for broadcast
• Approaches:
– 1-hop neighbor information
– 2-hop Neighbor information (neighbor list in hello
message)
Submission
Slide 11
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
2. Route Discovery
• Functions:
– Finding the route(s) to the destination
• Approaches:
– Proactive
• Broadcasting cost-to-all to neighbors (DSDV[11])
• Broadcasting cost-to-neighbor to all (OLSR[12]
– A variation: Periodic update (aggregation possible) (GSR[17],
FSR[13])
• Self-routing
– Tree routing (binding address with topology)
– Geographic-based routing
Submission
Slide 12
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
2. Route Discovery (cont.)
• Approaches: (cont.)
– Reactive routing
• Full-flooding RREQ (AODV[15], Expanding Ring Search)
• Limited-Flooding RREQ (LAR[18])
• Probabilistic RREQ (ANT [29])
– Hybrid routing
• Proactive for intra-cluster, reactive for inter-cluster (ZRP[16])
• Proactive for virtual backbone, reactive for end-devices
(TTDD[19])
Submission
Slide 13
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
3. Route Selection
• Functions:
– Selecting the best route(s) to the destination
• Approaches:
– Proactive routing
• Optimization based on distance vector (Bellman-Ford algorithm)
• Optimization based on link state (Dijkstra’s algorithm to compute
the shortest route)
• Calculation based on tree topology (tree)
• Calculation based on position information (GPSR[20])
Submission
Slide 14
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
3. Route Selection (cont.)
• Approaches (cont.):
– Reactive routing
• Source behavior
– First arrival RREP vs. selecting the best from multiple arrived
RREPs
• Destination behavior
– Selective reply vs. reply to all RREQs
• Intermediate nodes behavior
– Filtering RREQs vs simple relaying
Submission
Slide 15
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
4. Route Representation
• Functions:
– Storing the selected routes
• Approaches:
– Exact Route
•
•
•
•
Routing table
Interest entry (DD[21])
Route in the packet (DSR[14])
Binary tree (tree routing)
– Route Guidance
• Cost table (GRAd[22])
• Geographical information
Submission
Slide 16
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
5. Route Maintenance
• Functions:
– Keeping the route available and fresh for desired time
• Approaches:
– Reactive
• Control packet (AODVjr[23], “connection packet”)
• Data packet
– Proactive
• Periodically Distance Vector update
– Hybrid
• Proactive for intra-cluster, reactive for inter-cluster (ZRP[16])
Submission
Slide 17
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
6. Failure Response & Route Repair
• Functions:
– Propagating the route failure information and recover the route
• Failure Response:
– Invalidate the corresponding route
– Inform the source nodes who are using the broken route via a special control
message (e.g. Route ERRor)
• Route Repair:
– Reactive
•
•
•
•
Rediscovery
Local repair
Route cache (DSR[14])
Alternative path (multipath like TORA[24])
– Proactive
• Update neighbor topology information to whole network upon failure (OLSR[12])
• Update neighbors with distance vector upon failure, then update whole network
periodically (DSDV[11])
Submission
Slide 18
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
7. Data forwarding
• Functions:
– Forwarding data packets for other nodes using the
discovered route
• Approach:
– Forward to next hop by routing table lookup or following
the tree structure
– Include routing information into data packets
– Forward to certain direction (position-based or directional
antenna based protocols)
– Forward to cluster head or virtual backbone node
(hierarchical protocols)
– Simple data broadcast + receiver filtering
Submission
Slide 19
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
Non-MANET Routing Protocols
1.
2.
3.
4.
5.
6.
7.
8.
Geographical and Position-based Routing
Directional Antenna Based Routing
Power, Link Quality and other Cost-based Routing
Multi-path Routing and Load Balancing
Binary Tree Routing
Virtual Backbone Based Routing
Sensor Network Routing
Layer 2 Data Forwarding (e.g. Spanning Tree
Protocol)
9. Layer 2.5 Routing
Submission
Slide 20
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
1. Geographical & Position-Based
Routing
• Why Position-based Routing?
– Route packets without discovery.
– Storage and bandwidth requirements increase slowly when the network
grows
– RREQs can be broadcast to certain direction instead of to the whole
network
• Enabling technologies
– Absolute Position – GPS (outdoor only)
– Relative Position – exchanging estimated distance information based on
(indoor/outdoor)
• TOA, AOA, and TDOA
• Near field ranging algorithm
• Signal strength based ranging algorithm
Submission
Slide 21
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
1. Geographical & Position-Based
Routing (cont.)
• Location Service
–
–
–
–
Some for Some
Some for All
All for Some
All for All
• Forwarding Strategies
– Restricted Directional Flooding
– Greedy Forwarding
• Next-hop selection (minimum distance to the destination)
• Recovery strategy when greedy algorithm fails
– Hierarchical Approach
• Virtual backbone/Infrastructure node
Submission
Slide 22
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
Example: Location Aided Routing [18]
•
LAR – an on-demand source routing protocol
•
Route Discovery
–
–
–
Submission
The route request packet is forwarded to the rectangle
request zone.
If a neighbor of S determines it is within the request
zone, it forwards the route request further.
If a route reply packet is not received within the
timeout, then the second route request is flooded
through the network.
Slide 23
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
Example: Location Aided Routing (cont)
The Expected Zone
– A circle area
determined by the most
recent location
information on D.
Source
Request Zone
The Request Zone
Dest
Expected Zone
– A rectangle with S on
one corner and the
circle containing D in
the other corner.
• At time t0, Dest’s recorded location is (XD,YD), and velocity of Dest is Vavg
• At current time t1, the expected zone is a circle with radius R = Vavg × (t1 – t0)
Submission
Slide 24
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
2. Directional Antenna based
Routing
• Why directional antenna?
–
–
–
–
Improve network capacity by spatial reuse
Reduce interference
Extend range or Save power
Reduce the number of flooding packets
• What to be considered?
–
–
–
–
Complexity (angle of the arrival packets and etc.)
Mobility handling / Antenna handoff
Deafness problem
Effective usage together with omni directional antenna
Submission
Slide 25
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
Example: Directional DSR
C
C
B
B
D
D
A
A
Omni-directional
Antenna
Submission
Directional Antenna
Slide 26
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
Example: Directional DSR (cont.)
DiMAC – Directional MAC
 Broadcast implemented
through sweeping
 RREQ transmitted
sequentially on all N
beams
 Beam Handoffs (due to
node mobility) handled
through scanning
C
 Send probe packets on
recently used beams
 Update neighbor cache
based on replies to
probes
A
Submission
Slide 27
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
3. Power, Link Quality and
other Cost-based Routing
• Hop count
– Less significant in MANETs, e.g. smaller hop-count does not necessarily mean
smaller delay.
• Link Quality
– Less hops → longer per-hop distance → poorer link quality
– Different link quality for forward and backward routes
– Example: SSA[25]
• Energy consumption is important
–
–
–
–
Many devices are battery powered
Especially true for wireless sensor networks
Shortened network lifetime if not well handled
Example: PARO[26]
Submission
Slide 28
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
Example: SSA [25]
• Signal Stability based Adaptive Routing
– Selects routes based on the signal strength between nodes
or a node’s location stability
• Comprises two protocols:
– Dynamic Routing Protocol (DRP)
• Maintains the signal strength of neighboring nodes by periodic
beacons among neighbors
• Signal strength is recorded as a strong or weak channel
– Static Routing Protocol (SRP)
• processes the route search
Submission
Slide 29
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
Route Discovery
• The Query packets are forwarded only if they are received over strong
channel and has never been processed before.
• No packet can be sent over weak channel
Source
Destination
A
D
H
G
C
F
B
E
Strong Channel
Submission
Weak Channel
Slide 30
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
Route Discovery (cont.)
• When there are only weak links can reach the destination
– The source times out, it changes the PREF field in the header
– Weak channels are acceptable
Source
Destination
A
D
H
G
C
F
B
E
Strong Channel
Submission
Weak Channel
Slide 31
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
4. Multi-path Routing and
Load Balancing
• Why Multi-path Routing?
–
–
–
–
• Data forwarding strategies
– One route at a time (Round
Robin)
– Multi-route at the same time
Robustness
Higher packet delivery ratio
Shorter route recovery time
Energy and load balancing
• How multi-paths are
formed?
• Considerations
– Route maintenance cost
• Extra storage of multiple
route entries
• Control traffic
– Node disjoint vs. Link
disjoint
Submission
Slide 32
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
Example: Multipath Extension to DSR
[27]
• Multipath creation
– The destination replies to a selected set of route queries.
• Primary source route is the route taken by the first query reaching the
destination.
• Route queries that carry a source route that is link-wise disjoint from the
primary source route are also replied – multiple routes created.
– The source keeps all routes received on reply packets in its route cache;
• Data Forwarding
– When the primary route breaks, the shortest remaining alternate route
is used.
– This process continues until all routes break, then a fresh route
discovery will be initiated.
Submission
Slide 33
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
Example: Multipath Extension to
DSR [27]
• Improvement
– multipath at all intermediate nodes (each node has a
link-disjoint alternate path to the destination)
Destination
Source
Primary Route
Submission
Alternate Path
Slide 34
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
5. Binary Tree Routing
• Why Binary Tree Routing?
– Good for networks with one portal to the wired
network, e.g. home networks.
– Binary tree structure binds addressing with routing
• By checking the destination address of a given packet, every
node knows how to route the packet
– Routing decision is simple, either up to parent, or down
to one of children
– Low routing control overhead
Submission
Slide 35
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
5. Binary Tree Routing (cont.)
• Considerations:
– Sub-optimal routes to peer nodes
– Tree construction overhead
– Mobility support
• Fixed binding of address to the tree structure makes it a very
difficult issue
• when a node changes its connecting point to the tree, it has to
change its address
– Tree link breakage and repair
– The scale of the network is limited by the address space
– Load and energy balance
Submission
Slide 36
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
Example: Cluster-Tree Routing [28]
1  CmLm 1
Bsize 
1  Cm
Bsize
0
Bsize  k i0 Cm 
L
CskipLi 
1
Cskip0
41
Cskip0
81
Cskip1
2
15
28
42
55
68
82
95
Cskip1
108
Cm  3,
Cm L 1
i
Lm  4
Bsize  121
Cskip0  40
Cskip1  13
Cskip2
Cskip2
Cskip2
Cskip2  4
Cluster-tree addressing and self-routing
Submission
Slide 37
Myung Lee, Chunhui Zhu, Samsung
k
September 2004
doc.: IEEE 802.11-04/1042r0
6. Virtual Backbone Based Routing
• Why Virtual Backbone Routing?
– Virtual backbone nodes usually have more resources than client nodes,
e.g. bandwidth, power, antenna gain and etc.
– Virtual backbone nodes are usually static so that they can provide stable
connections
– Virtual backbone nodes sometimes form a dominant set over which can
cover all network nodes – good for broadcast traffic
• Considerations:
– The selection and placement of the virtual backbone nodes
– Virtual backbone maintenance overhead (e.g. virtual backbone
reconfiguration when an existing backbone node fails)
Submission
Slide 38
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
Example: Dynamic Backbone
Algorithm [6][7]
• A distributed protocol implements routing underneath the IP layer
– At the IP layer, the network so-constructed behaves like an ordinary
Ethernet subnet.
– Different from MANET protocols (implemented at IP layer)
• Maintaining a dynamic backbone for a subnet by periodically probing node
connectivity
• The backbone can be reconfigured in a known, fixed length of time
(approximately 1 to 3 seconds)
• Combining the features of ad-hoc networks with the control features of
802.11 infrastructure networks
Submission
Slide 39
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
Example: Dynamic Backbone
Algorithm (cont.)
• Broadcast and multicast
– The backbone approximates a spanning tree that connects all nodes and
over which all broadcast traffic is routed.
– Standard protocols such as ARP, RARP, DHCP, and other service
discovery mechanisms can work in their normal fashion.
• Unicast
– Node connectivity information is sent over the backbone in order to
develop unicast routing tables using Dijkstra’s Shortest Path Algorithm.
– Unicast traffic is not constrained to use only backbone links, but is free
to use shortest path routing.
Submission
Slide 40
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
Source: Dennis Baker, James Hauser, “Mobile 802.11 Extended Service Sets
using the Dynamic Backbone Subnet Architecture (DBS/802.11)”, Doc# 03/236
Submission
Slide 41
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
7. Sensor Network Routing
• There could be only one sink (data collector) in the network;
others are sensor nodes;
• Sensor nodes could be very inexpensive and resource-limited;
• Routing is done by using attributes instead of Node ID’s (e.g.
temperature, light intensity and etc):
– Directed Diffusion
• Routing may be combined with collaborative signal processing
– Data Fusion to reduce communication traffic
Submission
Slide 42
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
Example: Directed Diffusion [21]
Sink
Source
interest
gradient
low rate event
Submission
reinforcement
high rate event
Slide 43
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
8. Layer 2 Data Forwarding
• Why Layer 2 Data Forwarding for 802.11s?
– Hiding the multi-hop feature to higher layers (transparent to end nodes)
– Network layer independent, e.g. IPv4, IPv6, AppleTalk and etc
– Natural broadcast support
• Good for protocols rely on broadcast, such as ARP, DHCP and
service/device discovery
– Roaming/mobility is easily supported
• Considerations:
– Broadcast even for unicast traffic when the destination is unknown
– Address list grows proportionally with the number of the nodes in the
network as with other proactive protocols
Submission
Slide 44
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
Example: Spanning Tree Protocol
• Spanning Tree
– A tree connects all nodes in a network without loops
– There is exactly one path from any one node to all other
nodes
• Spanning Tree Protocol (802.1D/1W)
– A bridging technology and a link management protocol
• Prevents undesirable loops in the network
– Forcing redundant data paths into standby
• Provides path redundancy
– Activating the standby path
Submission
Slide 45
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
Example : Spanning Tree Protocol
(cont.)
• Considerations:
– Broadcast even for unicast traffic when the
destination is unknown
– Sub-optimal routes to peer nodes
– Mobility support
• Link change leads to global tree reconstruction
Submission
Slide 46
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
Example : Spanning Tree Protocol
(cont.)
Bridge A
B
C
Spanning Tree Structure
LAN 2
LAN 1
LAN 3
LAN 4
LAN 1
D
E
F
A
LAN 2
B
LAN 3
C
LAN 4
D
E
F
LAN 5
LAN 6
LAN 7
H
J
LAN 8
LAN 9
G
LAN 5
LAN 7
Bridges that
are part of the
spanning tree
LAN 6
H
J
I
LAN 8
Submission
Bridge that is
NOT part of the
spanning tree
LAN 9
Slide 47
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
9. Layer 2.5 Routing
• Why Layer 2.5 Routing?
– Similar to Layer 2 Data forwarding
• Major Approaches
– Ad Hoc routing under IP
• Ethernet emulation
• Multihop support
• Example: DBS[6][7], LUNAR[8], MCL (LQSR)[9]
– Label switching
• QoS support
• Multi-protocol support
• Mobility control
Submission
Slide 48
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
Example 1: LUNAR [8]
• Route discovery is triggered by ARP request
– One-hop address resolution → multihop address
resolution
• New routes (L2.5 paths) are built on-demand
– Source routing or L2.5 table driven
• Routes are rediscovered every 3 seconds, route
expires after 6 seconds
– no hello, no repair
Submission
Slide 49
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
Example 2: Label Switching
MAC
Header
Label
IP
Header
TCP
Header
Data
• Route through L2.5 labels
• Keep IP address consistent
Submission
Slide 50
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
IETF Activities
• Mobile Ad-hoc Networks (MANET) working group
– http://www.ietf.org/html.charters/manet-charter.html
• RFCs:
– Mobile Ad hoc Networking (MANET): Routing Protocol Performance
Issues and Evaluation Considerations (RFC 2501)
– Ad Hoc On Demand Distance Vector (AODV) Routing (RFC 3561)
– Optimized Link State Routing Protocol (RFC 3626)
– Topology Dissemination Based on Reverse-Path Forwarding (TBRPF)
(RFC 3684)
• Draft:
– The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks
(DSR)
Submission
Slide 51
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
IRTF Activities
• IRTF RRG Ad hoc Network Systems Research Subgroup
– http://www.flarion.com/ans-research/
• Areas of interest:
–
–
–
–
Inter-layer Protocol Interaction, and its effect on...
Quality of Service Routing
Routing Scalability
Network Auto-Configuration
• Internet-Drafts:
– Interlayer Interactions and Performance in Wireless Ad Hoc Network
– Notes on Scalability of Wireless Ad hoc Networks
– Common Wireless Ad Hoc Network Usage Scenarios
Submission
Slide 52
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
Reference (1/4)
[1]
L. Yang, S. Conner, X. Guo, M. Hazra, J. Zhu, “Common Wireless Ad Hoc Network Usage Scenarios”, Internet Draft
Document: draft-irtf-yang-ans-scenarios-00.txt
[2]
S. Corson, J. Macker , “Mobile Ad hoc Networking (MANET): Routing Protocol Performance Issues and Evaluation
Considerations”, IETF rfc1501
[3]
Ivan Stojmenovic, “Position-Based Routing in Ad Hoc Networks”
[4]
Romit R. Choudhury, Nitin H. Vaidya, “Impact of Directional Antennas on Ad Hoc Routing”
[5]
Martin Mauve, Jorg Widmer, “A Survey of Position-Based Routing in Mobile Ad Hoc Networks”
[6]
Dennis J. Baker, James P. Hauser, and Dennis N. McGregor, "Design and Performance of an HF Multichannel
Intratask Force Communication Network," NRL Report 9322, Nov. 1991.
[7]
Dennis J. Baker, James P. Hauser, Dennis N. McGregor, and James T. Ramsey, "The UNT/NRL HF Intratask Force
Communication Network Experiment," NRL/MR/4440-92-6965, June 1992.
[8]
Christian Tschudin, Richard Gold, Olof Rensfelt and Oskar Wibling, “LUNAR — A Lightweight Underlay Network
Ad-hoc Routing Protocol and Implementation”, NEW2AN'04, St. Petersburg, Feb 2004.
[9]
R. Draves, J. Padhye, and B. Zill, “Routing in Multi-radio, Multi-hop Wireless Mesh Networks”, MobiCom,
Philadelphia, Sep. 2004.
[10] Hiroyo Ogawa, Yoshihiro Suzuki, “Mobility Control by L2.5 Routing”, IEEE C802.16e-03/09, Jan. 2003
Submission
Slide 53
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
Reference (2/4)
[11] C. E. PERKINS, P. BHAGWAT, “Highly Dynamic Destination-Sequenced Distance Vector (DSDV) for Mobile
Computers”, Proc. of the SIGCOMM 1994 Conference on Communications Architectures, Protocols and
Applications, Aug 1994, pp 234-244.
[12] T. Clausen, P. Jacquet “Optimized Link State Routing Protocol”, RFC 3626
[13] M. GERLA, G. PEI, X. HONG, TS. CHEN “Fisheye State Routing Protocol (FSR) for Ad Hoc Networks”, Internet
Draft, draft-ietf-manet-fsr-00.txt, work in progress, June 2001.
[14] David B. Johnson, David A. Maltz, Yih-Chun Hu, “The Dynamic Source Routing Protocol for Mobile Ad Hoc
Networks (DSR)”, <draft-ietf-manet-dsr-10.txt>
[15] C. Perkins, E. Belding-Royer, S. Das, “Ad hoc On-Demand Distance Vector (AODV) Routing”, RFC 3561
[16] Nicklas Beijar, “Zone Routing Protocol (ZRP)”
[17] T. Chen and M. Gerla, “Global State Routing: A New Routing Scheme for Ad-hoc Wireless Networks" Proc. IEEE
ICC'98, 5 pages. http://www.ics.uci.edu/atm/adhoc/paper-collection/gerla-gsr-icc98.pdf
[18] Y.-B. KO, V. N. H. “Location-Aided Routing in mobile Ad hoc networks”, In Proc. ACM/IEEE Mobicom, pages 6675, October 1998.
[19] Haiyun Luo, Fan Ye, Jerry Cheng, Songwu Lu, Lixia Zhang, “TTDD: Two-tier Data Dissemination in Large-scale
Wireless Sensor Networks”, ACM/Kluwer Mobile Networks and Applications (MONET), Special Issue on ACM
MOBICOM, 2002
Submission
Slide 54
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
Reference (3/4)
[20] BRAD KARP AND H.T.KUNG. “Greedy Perimeter Stateless Routing for Wireless Networks”. In MobiCom 2000. Harvard
University.
[21] C. Intanagonwiwat, R. Govindan, Deborah Estrin, “Directed Diffusion: A Scalable and Robust Communications Paradigm for
sensor networks”, MOBICOM 2000
[22] R. Poor, “Gradient Routing (GRAd)”
[23] I. D. Chakeres, L. Klein-Berndt, “AODVjr, AODV Simplified”
[24] Vincent D. Park and M. Scott Corson. “Temporally-Ordered Routing Algorithm (TORA) version 1: Functional Specification.”
Internet-Draft, draft-ietf-manettora -spec01. txt, August 1998
[25] Rohit Dube Cynthia D. Rais Kuang-Yeh Wang Satish K. Tripathi, “Signal Stability based Adaptive Routing (SSA) for Ad-Hoc
Mobile Networks”, 1997
[26] J. GOMEZ, A. T. CAMPBELL, M. NAGHSHINEH, C. BISDIKIAN, T.J. WATSON, “POWER-AWARE ROUTING
OPTIMIZATION PROTOCOL (PARO)”, Internet Draft, draft-gomez-paro-manet-00.txt, work in progress, June 2001.
[27] Asis Nasipuri, Samir R. Das, “On-Demand Multipath Routing for Mobile Ad Hoc Networks
(M-DSR)”
[28] Hester, L., Huang, Y., Allen, A., Andric, O., Chen, P., “neuRFon Netform: A Self-Organizing Wireless Sensor Network,"
Proceedings of the 11th IEEE ICCCN Conference, Miami, Florida, Oct. 2002.
[29] O. Hussein, T. Saadawi and M. Lee, “Ant Routing Algorithm for mobile Ad-hoc Networks”, in the proceeding of CTAC 2003
pp 141-145 April 2003
Submission
Slide 55
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
Reference (4/4)
[30] Romit Roy Choudhury Nitin H. Vaidya, “Impact of Directional Antennas on Ad Hoc Routing”
Submission
Slide 56
Myung Lee, Chunhui Zhu, Samsung
September 2004
doc.: IEEE 802.11-04/1042r0
Acknowledgement
Special thanks to Yong Liu, Xuhui Hu,
Hsin-hui Juan, and June-Seung Yoon for
providing some of the example protocols
and drawings.
Submission
Slide 57
Myung Lee, Chunhui Zhu, Samsung