I want to study this pdf file in a 30 minutes. I know almost nothing about its concept and I want you to:
1. create an index from all the contents it provides 2. Give me a comprehensive, but casual description about what it contains in a way that I understand the main points of this pdf file, (If it could make a sense you may gimme an example in which contains a scenario related to the main point of this pdf)

Routing in Wireless
D2D Networks3
D2D Networks
• Nodes are computing and communication
devices, e.g laptops, PDAs, mobile phones, even
sensors
• Nodes organize and maintain the network by
themselves
• A node is both a host and a router
• IP is used at the network layer
• First and foremost issue: routing4
Problems with Routing
1. Self-organizing networks
– Need for distributed algorithms
2. Topology changes dynamically
– Mobile nodes (joining in or leaving)
– Unannounced loss of network connectivity due to the
time-varying channel nature
3. Link failure / repair
– Network partitions
– Loop formation during temporary node failures5
Problems with Routing
4. Asymmetric links: links may be unidirectional
5. Limited bandwidth
– Protocols using flooding create high traffic and
control overhead
6. Different performance criteria
– Number of hops (delay)
– Available Bandwidth
– Route stability despite mobility
– Energy consumption6
Remarks/Assumptions
1. Find/maintain a route provided it exists
– Another problem is to ensure that a route
exists, e.g., through power control
– Assume that nodes are willing to cooperate7
• Topology based routing
– Proactive approach, e.g., DSDV, OLSR
– Reactive approach, e.g., DSR, AODV
– Hybrid approach, e.g., Cluster, ZRP
Routing Protocols for D2D
• Position based routing
– Location Services: e.g., DREAM, Quorum-based,
GLS, Home zone etc.
– Forwarding Strategy: e.g., Greedy, GPSR, RDF,
Hierarchical8
The Proactive Approach
• Attempts to maintain consistent, up-to-date routing
information from each node to every other node in
the network
– Respond to changes by propagating updates
throughout the network
– Good for connection-less traffic where you may
send traffic to any node at any time
• Based on distance vector or link-state mechanisms9
The Reactive Approach
• Routes are only created when desired by the source
node
• Two-stage procedure
– Route discovery protocol: route discovery ends
either when a route is discovered or all possible
communication paths have been examined
– Once a route is established, it’s maintained by
some sort of route maintenance protocol10
Trade-off
• Reactive more suitable for a mobile environment
with limited bandwidth
• Proactive preferred when time constraints are
important
Proactive
Approach
Reactive
Approach
Latency Low High
Overhead High Low11
Proactive Protocols
DV for fixed networks, DSDV for
wireless networks13
Distance Vector Routing (1)
• Let’s consider that cost coincides with distance, i.e., number of
hops (it could be expressed also in terms of bandwidth, latency,…)
• Each node has a routing table where distance to all reachable
destinations is recorded
1) Each table entry contains:
a) Destination node ID (i.e., IP address)
b) Next hop
c) Distance (number of hops) to the destination
2) Each node keeps track and informs its neighbors of its
distance to every destination (main idea at the basis of
distance vector-based protocols)
• A router updates its distance to a destination based on its
neighbors distance to the destination14
Distance Vector Routing (2)
The picture can't be displayed.
1. Initially, each node sets the cost of the link to itself to 0 and
to any other node to infinity
2. A node broadcasts its routing information (list of
destinations and distance)
3. Upon receiving information from neighbors, a node
computes the minimum cost-path toward destination and
makes changes to its routing table if needed
4. Either periodically or every time a node updates its table, it
broadcasts routing information to its neighbors (then the
procedure repeats from step 2)
• The algorithm converges by iteration16
More Details on Step 3
• At node i and time step n+1, the minimum cost path
between nodes i and j is computed as
where:
is the path cost from i to j at time step n
is the cost of the link between i and its
neighbor k
is the set of i’s neighbours
The picture can't be displayed.
Dn(i, j)
d(i,k)17
Distance Vector Routing for
Address “Z”
A
2 1
3
4
5
17
2
35
5
41
Link cost
Link number
Z
k18
Distance Vector Routing for
Address “Z”
A
1
2
3
4
5
97
62
118
29
81
17
2
35
5
41
Cost from
neighbour to
destination Z
Z19
Distance Vector Routing for
Address “Z”
A
1
2
3
4
5
98
99
97
123 70
Cost for A
to get to Z
via this link
Minimum
cost route
17
2
35
5
41
97
62
118 29
81
Z20
Distance Vector Routing for
Address “Z”
A
70
70
70
70
70
Cost from
A to Z
1
2
3
4
5
17
2
35
5
41
Z22
Count-to-Infinity: An Example
A B
A B
2 1
2 3
A B
4 5
A B
6 7
D Node D becomes unreachable
Cost of the link A-B and B-D equal to 1 => cost of the
path between A and D equal to 2
Route cost to D
1 2
It occurs only if A sends its update before B23
DSDV (1): Destination Sequenced
Distance Vector Routing
• Proposed by Perkins [’94], based on Bellman-Ford
routing mechanism
• Each node maintains a routing table that records all
possible destinations
• Each table entry contains
1. Destination node ID (i.e., IP address)
2. Next hop
3. Number of hops to the destination
4. A sequence number (SN), used to distinguish “old”
vs. “new” routes and avoid loops24
DSDV (2)
• Upon reception of a route update:
– If the node doesn’t have such information, it adds an entry
to its table
– Otherwise, it checks the SN and updates the table only in
case of fresher information, i.e., the route with most
recent SN is used
– If two routes have the same SN, the route with the smaller
metric (== shorter route) is used
• When a link fails, an ¥ metric is used and the route SN is
increased26
Count-to-Infinity: An Example
A B
A B
2 1
2 3
A B
4 5
A B
6 7
D Node D becomes unreachable
Cost of the link A-B and B-D equal to 1 => cost of the
path between A and D equal to 2
Route cost to D
1 2
SN of the route notified by A is older than the one of the
route declared invalid by B -> A’s info is not considered. B
sends an update to A, and A too declares the route to D
(through B) as invalid
¥ ¥
¥
¥
New
SN27
Detecting Link Failure
• Detection:
– If data is flowing over a link, failure of link layer
to deliver a packet can be used to assume link
failure
– If a node does not hear for a long time (how
long?) from its neighbor30
Proactive Protocol
OLSR31
OLSR
Optimized Link State Routing [Jacquet’00]
• OLSR is based on the link state routing approach
• Traditional approach in Link State Routing:
– Every node generates control packets to advertise
its links status (i.e., its one-hop neighbors and the
links cost)
– Such information is propagated over the whole
network (flooding)32
OLSR
Optimized Link State Routing [Jacquet’00]
• However, in OLSR:
– Sources build routes proactively by using only MultiPoint
Relay nodes (MPRs)
– Only MPRs need to generate and forward link state
updates
• OLSR thus leads to efficient flooding of control
messages in the network: superfluous broadcast
packet retransmission as well as the size of the link
state packets are reduced33
MPRs and Their Selection
• Every node in the network selects its own MPR(s)
• A node selects its MPRs among its 1-hop neighbors so that
it can reach all nodes that are within 2-hop away, through
symmetric links
• Nodes exchange 1-hop neighbor lists to know their 2-hop
neighbors and link type, and choose the MPRs
• No. of MPRs per node should be minimized34
MPRs: Example (1)
• Hp: all links are bi-directional
A
B F
C
D
E H
G
K
J
E
Nodes C and E are multipoint relays of node A35
MPRs: Example (2)
• C selects A as MPR, while E selects A and H
• Node E is a multipoint relay also for node H
– If the link H-J were unidirectional, then K would also be selected as MPR
by H
– Indeed, OLSR never uses unidirectional links
A
B F
C
D
E H
G
K
J36
MPRs: Example (3)37
Controlled Flooding of Link State Updates
24 retransmissions
to deliver a message
up to 3 hops
11 retransmissions to
deliver a message up to
3 hops38
Controlled Flooding of Link State Updates
• OLSR is particularly suited for dense networks
• In sparse networks, every neighbor becomes a
multipoint relay, then OLSR reduces to pure
link state protocol39
How It Works: Hellos
• The generic node X broadcasts Hello messages
every Hello interval to its 1-hop neighbors:
– Hello message contains list of known 1-hop
neighbors and
– the link status (symmetric, asymmetric, or
MPR) of its 1-hop neighbors40
How It Works: Neighbor Table
• Node X builds a Neighbor Table that includes all its 1-hop
neighbors and, for each of them, all 2-hop neighbors that can be
reached through it. The link types are also recorded.
– X selects its MPR nodes among its 1-hop neighbors such that
it can reach all nodes that are within 2-hops away through
symmetric links
– Once X has selected a neighbor, say Y, as MPR, X tags its link
with Y as MPR and, through the next Hello, X will notify Y
about it
– Y maintains the list of nodes that selected Y as an MPR41
How It Works: Topology Control
• MPR nodes generate and broadcast Topology Control (TC)
messages every TC interval to advertize link states, specifically
– A TC message contains list of 1-hop neighbors who have
selected this node as an MPR
– Only MPR nodes can forward TC messages (but note that
all network nodes connected through symmetric links will
receive them) -> more efficient flooding
– Nodes receiving TC messages use them to build their
Topology Table (and for routing table calculation
afterwards)42
Some Remarks
• Control messages do not require a reliable
transmission since they are periodically sent
• Each control message includes a sequence number
so that old messages with outdated information
can be detected and discarded43
How It Works: Topology Table
• Each node maintains a topology table where the
information obtained from the received TC messages is
recorded
• Each entry includes:
– Address of a potential destination (i.e., the MPR
selector in the received TC)
– Address of the last hop to that destination (i.e., the
MPR that generated that TC)
– MPR selectors set sequence number44
How It Works: Routing Table
• Each node maintains a Routing Table where routes to any
potential destination are recorded
• The Routing Table is built based on the Topology Table and the
Neighbor Table
• Each entry includes:
1) Address of the potential destination
2) Address of the next hop to reach that destination
3) Estimated distance to the destination
• Note that the Routing Table is re-calculated at every change
in either the Topology Table or the Neighbor Table45
Building the Routing Table (1)
Initialization:
• Set h to 1;
• Use the Neighbor Table: take the 1-hop
neighbors (whose link status is not unidirectional) as destinations (i.e., h =1 ) and
create the corresponding entry in the Routing
Table;
• set their distance to h = 1.46
Building the Routing Table
Iterative procedure:
1) For each entry in the Topology Table:
(i) if its destination does not correspond to any destination in the
Routing Table and
(ii) if its last hop (i.e., MPR) is the destination of an entry in the
Routing Table with distance equal to h, then add a new route
entry in the routing table where:
– dest = dest of the entry in the Topology Table;
– next-hop = next-hop of the route entry whose dest is the lasthop in the Topology Table;
– Set distance = h+1;
2) Set h = h+1 and go to step 1 (till all entries in the Topology Table
have been processed)47
Some Observations (1)
• Routes are all composed of MPRs only (except source and
destination): MPRs form a network backbone that is in charge
of routing all traffic
• Asymmetric links are never used
• MPR nodes selection impact:
– How much more traffic must MPR nodes handle? Higher
load leads to higher energy consumption
• Node mobility impact
– Consequences? Particularly for MPR nodes48
Some Observations (2)
• Hello interval impact on overhead vs. protocol reactivity:
– Recall: Hellos are sent by all nodes to their 1-hop
neighbors (but they are not rebroadcast)
• TC interval impact on overhead vs. protocol reactivity:
– Recall: TC messages are sent only by MPR nodes to
advertize link state but they reach all network nodes49
Reactive Protocols
DSR
AODV50
DSR
Dynamic Source Routing [Johnson’96]
• Entirely “on demand”: No periodic messages or
advertisements at any layer
• Dynamic: it maintains a “soft state,” i.e., all state is discovered
when needed and can be easily re-discovered if needed after
a failure without impacting the protocol functioning
• Source Routing: the source specifies in the header of each
data packet the entire route, not only the next hop (no need
for routing tables)51
Assumptions
• The network is fairly small (up to 200 nodes, i.e.,
network diameter of 10-15 nodes)
• Each node maintains a cache containing all source
routes of which it is aware
– Routes in the cache are continuously updated as
they are learned
– Several routes can be cached to the same
destination
• Either bi- or uni-directional links are present52
DSR: Two Phases
The protocol consists of two phases:
• Route discovery:
– Started by S when S needs to send data to D and
doesn’t have any route to D in cache
• Route Maintenance:
– While using a route to D, S can detect if the route is
not longer valid and, in case, send an error message
– Upon route failure, S may use another route (if it
knows it) or start a new route discovery54
L
H
J
D
C
G
S
N
K
B
A
Route Discovery
RREQ
Initiator ID
Initiator seq#
Dest ID
Partial route
TTL
Initiator seq#
Dest ID
Time to go
RREQ Table
If no reply by the “time to go”, S sends a new RREQ till a
max no. of attempts have been made
Unique ID
QoS cost55
L
H
J
D
C
G
S
N
K
B
A
Route Discovery
RREQ
recently
seen?
Discard
RREQ
yes
no
myAddr in
partial
route? yes
no
store RREQ ID
in list
decrease TTL and
rebroadcast packet
myAddr=
target?
no
S
S
S,C
S,L
S,C
S,C
S,L
S,L
known
route?
append myAddr to
partial route
no56
L
H
J
D
C
G
S
N
K
B
A
Route discovery succeeded !
Route Discovery
S,L,J
S,C,G
S,C,H59
L
H
J
D
C
G
S
N
K
B
A
RREP
Route Reply
S,L,J,D
S,C,G,K
S,C,G,K
S,L,J,D
S,L,J,D
S,L,J,D
Place route record and
cost into RREP
(cost depends on target
QoS metric)
RREP sent by reversing the route
followed by RREQ. If unidirectional,
use any cached route to S. If none,
send an RREQ and piggyback RREP
myAddr=
target?
yes60
L
H
J
D
C
G
S
N
K
B
A
DATA
Data Delivery
Write route in
packet header and
send packet to
next hop
S,L,J,D
S,L,J,D
S,L,J,D
S,L,J,D61
L
H
J
D
C
G
S
N
K
B
A
RREP
Route Caching
S,L,J,D
S,L,J,D
S,L,J,D
Place cached route and
cost into RREP
(cost depends on target
QoS metric)
RREP sent by reversing the route
followed by RREQ. If unidirectional,
use any cached route to S. If none,
send an RREQ and piggyback RREP
known
route?
yes62
Route Caching
• S caches the route to D contained in the RREP
– For each D, more than one route can be cached,
thus S can perform traffic routing over several
possible routes
• Advantages of route caching
– Speeds up routing
– Reduces propagation of route requests63
Route Maintenance
• Along a source route, each node transmitting a packet
is responsible for correct transmission confirmation
• An ACK is needed for confirmation
– MAC or link-layer ACKs can be used
– Overhearing next node forwarding the packet
(passive ACK: A hears B sending to C)
– Use of DSR-ACKs: the node transmitting the packet can
require an ACK (which may follow a different route back)65
Route Maintenance
S
B C
G
D
H
F
Mark link to next
hop as broken
Received
ACK?
yes
Max
#ACKreq
exceeded?
Remove from cache
all routes including
that link
Send an RERR to every source
that sent a packet to be routed
over that link
no Route Cache (S)
D: S,B,C,F,D
D: S,B,C,G,H,D
C: S,B,C
RERR
RERR66
Route Maintenance
• Nodes overhearing RERR remove from their
cache all routes including the broken link
• S uses another route from its cache, if it has any;
otherwise it starts a new route discovery
• The transport layer (e.g., TCP) should take care
of data retransmissions67
Optimizations
• Promiscuous mode: listening to arbitrary routes in use (A hears
B sending to C)
– Replace with shorter routes / Store new routes
– But promiscuous mode takes energy
• Packet salvaging
– Upon link failure
– If intermediate node has another route to D, it replaces the
original source
– However, no double salvage is allowed !!! (flag in the packet
header indicates if the packet has been saved already once)68
Packet Salvaging: An Example (1)
• Initial route: S (source) – B – C – F – D (destination)
• However, S and C have an alternative route to D in their cache
(S-B-Z-F-D and C-I-G-H-D, respectively)
• At a certain time, F moves out of the network
S
B C
G
F D
H
L
I
M
I
L
Z69
Packet Salvaging: An Example (2)
• Assume that unfortunately S (and B) do not receive RERR,
from either C or Z, then S keeps sending its packets toward C
• C can salvage the packets by replacing the original route (SB-C-F-D) in the packet with the new route (C-I-G-H-D)
S
B C
G
D
H
L
I
M
I
L
Z70
Packet Salvaging: An Example (3)
• Now, assume the G-H link fails, then IF G could save the
packet again, a loop could have been formed. Indeed
(i) G does not know that the packet was originated by S (it
only sees C as originator),
(ii) S could reply with the route S-B-Z-F-D
S
B C
G
F D
H
L
I
M
I
REQ
REQ
REQ
REQ
REQ
REP
REP
REP
REP
REP
L
Z
REQ REQ72
Enrirely reactive
“Soft state” and support of unidirectional links
Source routing
No need for routing decisions by intermediate nodes
Nodes can learn new routes from relayed packets
Guarantee that routes are loop-free
Caching
Reduced route discovery overhead
One route discovery may yield many routes to D, due to
intermediate nodes replying from local caches
DSR: Advantages73
RREQ flooding may be huge
Possible collisions between RREQs propagated by
neighboring nodes
Contention between RREPs come back due to use of local
caches (RREP Storm problem)
Packet delays/jitters due to on-demand routing
Headers may become too long with respect to data
payloads -> suitable for small networks
Cached routes may become invalid; stale caches can
adversely affect performance
DSR: Disadvantages74
AODV
Ad-Hoc On Demand Distance Vector [Perkins’99]
• Builds routes on demand
• Attempts to improve DSR by using (small) routing
tables at the nodes so that packets do not have to
include routes
• Avoids loop formation by using sequence numbers
• Similar procedures of route discovery and route
maintenance as in DSR75
Assumptions
Each node maintains:
• A broadcast ID to be used for RREQs
– Broadcast ID is incremented for each RREQ
– Combination of the node IP address & broadcast ID uniquely
identifies an RREQ
• A (small) routing table with an entry for each “useful”
destination node
• Consider only symmetric links76
Routing Table
A routing table entry includes:
1. Destination IP address
2. Next hop
3. Hop count
4. Active route timeout (lifetime)
5. Routing flag indicating whether the path is active or not
6. Sequence number assigned to the path by the destination
(Destination Sequence Number, DSN)78
L
H
J
D
C
G
S
N
K
B
A
Route Discovery
RREQ
Initiator ID
Dest. Sequ. #
Dest ID
Broadcast ID
• Two routes will be found: one from S to D, the other from D to S
• A new RREQ by node S for a given destination, is assigned a higher
DSN (for the inverse route with S as a destination)
TTL
QoS cost79
L
H
J
D
C
G
S
N
K
B
A
Route Discovery
known route
with higher
DSN?
Send
RREP
yes
no no
sets up a reverse
path pointing to the
source
TTL-- then
re-broadcast
RREQ
RREQ
already
seen?
no
Discard
RREQ
yes
store RREQ
myAddr=
target?80
L
H
J
D
C
G
S
N
K
B
A
Route discovery succeeded !
Route Discovery82
L
H
J
C
G
D
S
N
K
B
A
RREP
Route Reply
Place route record & cost
into RREP (cost depends
on target QoS metric)
DSN is increased
RREP sent on
reverse path
myAddr=
target?
yes
Nodes on the route set a forward path to D
as they receive the RREP83
Remarks
• D replies to the first arrived RREQ thus AODV
favors the least congested route (that is not
always the shortest one)
• As OLSR, it only supports symmetric links!
– RREP forwarded along the same route followed by the
RREQ84
L
H
J
D
C
G
S
N
K
B
A
Route Discovery
known route
with higher
DSN?
Send
RREP
yes
no no
sets up a reverse
path pointing to the
source
TTL-- then
re-broadcast
RREQ
RREQ
already
seen?
no
Discard
RREQ
yes
store RREQ
myAddr=
target?85
L
H
J
D
C
G
S
N
K
B
A
DATA
Data Delivery
Send data packet to next hop
using routing table entry
(no route in packet header)86
Timeouts
• A routing table entry maintaining a reverse
path is purged after a timeout interval long
enough to let the RREP come back to the
source
• A routing table entry is purged if the route has
not been used for an active_route_timeout
interval87
Route Maintenance
• HELLO messages are periodically exchanged
between neighboring nodes to maintain local
connectivity
– Absence of Hello messages is used as an indication of link
failure
– Hello messages can also contain the ID of the neighbors
from which a node has heard
• A node can also use MAC acknowledgements or
packet retransmissions done by a neighbor to check
on the next hop reachability90
Link Failure
S
B C
F
D
G
E
Route Table (C)
D: E DSN: 5
Active ...
C sends RERR to
upstream
neighbors
yes
C detects link
failure
C increases DSN and
includes it in the
RERR
Route Table (S)
D: B DSN: 5
Active ...
Route DSN: 591
Link Failure
S
B C
F
D
G
Route Table (C)
D: E DSN: 5
Active ...
RERR
RERR
C sends RERR to
upstream
neighbors
yes
C detects link
failure
C increases DSN and
includes it in the
RERR
6
Inactive ...
Route Table (S)
D: B DSN: 5
Active ...
6
Inactive ...
Route DSN: 5
Route DSN: 692
Link Failure
S
B C
F
D
G
C sends RERR to
upstream
neighbors
yes
C detects link
failure
C increases DSN and
includes it in the
RERR
Route Table (C)
D: E DSN: 6
Inactive ...
RREQ
RREQ
Route Table (S)
D: B DSN: 6
Inactive ...
RREQ
RREQ
RREQ
Route DSN: 5
Route DSN: 6
Route DSN: 7
Route DSN: 693
Link Failure
S
B C
F
D
G
C sends RERR to
upstream
neighbors
yes
C detects link
failure
C increases DSN and
includes it in the
RERR
Route Table (C)
D: E DSN: 6
Inactive ...
RREP
RREP
Route Table (S)
D: B DSN: 6
Inactive ...
RREP
RREP
RREP
Route DSN: 5
Route DSN: 6
Route DSN: 7
Route DSN: 7
Route Table (S)
D: B DSN: 7
Active ...
F 7
Active ...97
Advantages
• No need to include route in the packet header
• Nodes maintain routing tables containing entries only for
routes in use
• DSNs allow nodes to avoid invalid/broken routes
• DSNs prevent formation of loops
Disadvantages
Unused routes expire even if topology is unchanged
Multiple routes for each pair S-D are not supported
Need for symmetrical links
Advantages & Disadvantages99
QoS Routing
• Associate each link with a cost
– E.g., transmission power, transmitter’s residual energy,
traffic load, available bandwidth
• RREQs used to collect the cost (or minimum cost) of
all traversed links along a route
S
B
C
F
D
G
E
S-B TxPw
RREQ
+ B-C TxPw + C-E TxPw + E-D TxPw
+ F-G TxPw
+ G-D TxPw
+ C-F TxPw100
QoS Routing
• Destination responds with a Route Reply to a RREQ if
– it is the first RREQ with a given (“current”)
sequence number, or
– the route cost is smaller than all other routes cost
received with the current sequence number
• Possible modifications to routing protocols, such as
DSR, to make them QoS-aware101
QoS Routing
• Optimal routing decision requires constant updates
on link state information (e.g., delay, bandwidth,
loss rate, link stability) resulting in large overhead
• Dynamic nature of ad hoc networks makes
maintaining the precise link state information very
hard
• Even after resource reservation, QoS still cannot be
guaranteed due to the frequent topology changesRouting in VANETsWhich Protocol Is Suitable?
• Proactive and reactive protocols may not be suitable:
§ Proactive protocols: routing tables might often
contain stale information, due to the highlydynamic network topology
§ Reactive protocols typically imply high latency due
to the route discovery phase
• Positioning systems can be exploited to efficiently
route traffic in VANETs geographic routingGeographic Routing (1)
• Position-based schemes: nodes determine their
geographical position through GPS; using BSM/CAM
messages a node can acquire also the position of its
neighboring nodes
• It is assumed that the destination coordinates are
known (easy if it’s an RSU) and they are included in the
data packet
§ If the destination is a vehicle, then its position can
vary over time and message delivery may failGeographic Routing (2)
• Next hops are determined based on their position or
movement direction with respect to the intended
destination
§ Self-election is possible, or the current forwarder
can select the next one
• In the basic greedy geographic technique, the packet is
forwarded at each step to the neighbor whose position
is closest to destination
• Greedy forwarding, however, is susceptible to problem
of dead-endsDead-end with Geographic Routing
• Both E’s neighbors (i.e., C and D) are further
away from the destination than the sender
(E)
• Adopt the right-hand rule to solve the
problem: E-C-F-B (same as to get out of a
maze)
• A similar approach is used in sensor
networks; however in VANETs, several factors
can help:
• the spatial-constrained topology (roads)
• the delay-tolerant nature of the traffic,
along with the fact that nodes move and
can get closer to the destination
themselves
void120
References on Routing
• C.E. Perkins, P. Bhagwat, “Highly dynamic Destination
Sequenced Distance Vector routing (DSDV) for mobile
computers“, Sigcomm 1994
• Z.J. Haas, M.R. Pearlman, “The Zone Routing Protocol (ZRP) for
ad hoc networks,” <draft-ietf-manet-zone-zrp-02.txt>, 1999
• B. Karp, H. T. Kung. “GPSR: Greedy perimeter stateless routing
for wireless networks,” MobiCom 2000
• S. Basagni, I. Chlamtac, V.R. Syrotiuk, B.A. Woodward, “A
distance routing effect algorithm for mobility (DREAM),”
MobiCom 1998
• N. Guba, T. Camp, “GLS: a location service for an ad hoc
network,” Grace Hopper Celebration 2002121
References on Routing
• [Johnson96] D.B. Johnson, D.A. Maltz, "Dynamic source routing
in ad hoc wireless networks", Mobile Computing, vol. 353,
1996
• [Perkins99] C.E. Perkins, E.M. Royer, "Ad hoc on-demand
distance vector routing," 2nd IEEE Workshop on Mobile
Computing Systems and Applications, 1999
• J. Broch, D.A. Maltz, D.B. Johnson et al., “A performance
comparison of multi-hop wireless ad hoc network routing
protocols,” MobiCom 1998
• AODV Linux freeware implementations:
http://moment.cs.ucsb.edu/AODV/aodv.html#Implementation
s122
• S.R. Das, C.E. Perkins, E.M. Royer, “Performance Comparison
of two on-demand routing protocols for ad hoc networks,”
Infocom 2000
• P. Johansson, T. Larsson, N. Hedman et al., “Scenario-based
performance analysis of routing protocols for mobile ad-hoc
networks,” MobiCom 1999
• F. Bai, N. Sadagopan, A. Helmy, " IMPORTANT: A framework to
systematically analyze the Impact of Mobility on Performance
of RouTing protocols for Ad hoc NeTworks," Infocom 2003
• Two papers by A. Helmy et al. at ICC 2004
References on Routing