|
|
|
Introduction and History |
|
Data in Wireless Cellular Systems |
|
Data in Wireless Local Area Networks |
|
Internet Protocols |
|
Routing and Ad-Hoc Networks |
|
TCP over Wireless Link |
|
Services and Service Discovery |
|
System Support for Mobile Applications |
|
|
|
|
|
|
|
Problem:
Find the lowest cost path between any two nodes |
|
Factors: |
|
Static: topology |
|
Dynamic: load |
|
|
|
|
|
|
Each node maintains a set of triples: |
|
(Destination, Cost, NextHop) |
|
Each node sends updates to (and receives updates
from) its directly connected neightbors |
|
periodically (on the order of several seconds) |
|
whenever its table changes (called triggered
update) |
|
Each update is a list of pairs: |
|
(Destination, Cost) |
|
Update local table if receive a “better” route |
|
smaller cost |
|
came from next-hop |
|
Refresh existing routes; delete if they time out |
|
|
|
|
|
|
|
Example 1 |
|
F detects that link to G has failed |
|
F sets distance to G to infinity and sends
update to A |
|
A sets distance to G to infinity since it uses F
to reach G |
|
A receives periodic update from C with 2-hop
path to G |
|
A sets distance to G to 3 and sends update to F |
|
F decides it can reach G in 4 hops via A |
|
|
|
|
|
Example 2 |
|
Link from A to E fails |
|
A advertises distance of infinity to E |
|
B and C advertise a distance of 2 to E |
|
B decides it can reach E in 3 hops; advertises
this to A |
|
A decides it can reach E in 4 hops; advertises
this to C |
|
C decides that it can reach E in 5 hops...... |
|
Heuristics to break routing loops |
|
set infinity to 16 |
|
split horizon |
|
split horizon with poison reverse |
|
|
|
|
|
Strategy: Send to all nodes (not just neighbors)
information about directly connected links (not entire routing table). |
|
Link State Packet (LSP) |
|
id of the node that created the LSP |
|
cost of link to each directly connected neighbor |
|
sequence number (SEQNO) |
|
time-to-live (TTL) for this packet |
|
Reliable Flooding |
|
store most recent LSP from each node |
|
forward LSP to all nodes but one that sent it |
|
generate new LSP periodically; increment SEQNO |
|
start SEQNO at 0 when reboot |
|
decrement TTL of each stored LSP; discard when
TTL=0 |
|
|
|
|
|
|
|
|
Dijkstra's shortest path algorithm |
|
N denotes set of nodes in the graph |
|
l(i,j) denotes non-negative cost (weight) for
edge (i,j) |
|
s /in N denotes this node |
|
M denotes the set of nodes incorporated so far |
|
C(n) denotes cost of the path from s to node n |
|
M = {s} |
|
for each n
in N - {s} |
|
C(n) = l(s,n) |
|
while (N ° M) |
|
M = M union {w} such that C(w) |
|
is the minimum for all w in (N-M) |
|
for each n in (N-M) |
|
C(n) = MIN (C(n), C(w)+l(w,n)) |
|
|
|
|
|
|
|
|
|
Original ARPANET metric |
|
measured number of packets enqueued on each link |
|
took neither latency or bandwidth into
consideration |
|
New ARPANET metric |
|
stamp each incoming packet with its arrival time
(AT) |
|
record departure time (DT) |
|
when link-level ACK arrives, compute |
|
Delay = (DT - AT) + Transmit + Latency |
|
if timeout, reset DT to departure time for
retransmission |
|
link cost = average delay over some time period |
|
|
|
|
|
|
Problems with “New” metric |
|
under low load, static factors dominated cost;
worked OK |
|
under high load, congested links had very high
costs; packets oscillated between congested and idle links |
|
range of costs too large; preferred path of 126
lightly loaded 56Kbps links to a 1-hop 9.6Kbps path |
|
Revised ARPANET metric |
|
replaced delay measurement with link utilization |
|
compressed dynamic range |
|
highly loaded link never has a cost more than 3
times its idle cost |
|
most expensive link only 7 times the cost of the
least expensive |
|
high-speed satellite link more attractive than
low-speed terrestrial link |
|
cost is a function of link utilization only at
moderate to high loads. |
|
|
|
|
|
|
|
Idea: Impose a second hierarchy on the network
that |
|
limits what routers talk to each other. (The
first |
|
hierarchy is the address hierarchy that governs
how |
|
packets are forwarded.) |
|
Autonomous System (AS) |
|
corresponds to an administrative domain |
|
examples: University, company, backbone network |
|
assign each AS a 16-bit number |
|
Two-level route propagation hierarchy |
|
interior gateway protocol (each AS selects its
own) |
|
exterior gateway protocol (Internet-wide
standard) |
|
|
|
|
|
RIP: Route Information Protocol |
|
developed for XNS |
|
distributed with Unix |
|
distance-vector algorithm |
|
based on hop-count |
|
OSPF: Open Shortest Path First |
|
recent Internet standard |
|
uses link-state algorithm |
|
supports load balancing |
|
supports authentication |
|
|
|
|
|
Overview |
|
designed for tree-structured Internet |
|
concerned with reachability, not optimal routes |
|
Protocol messages |
|
neighbor acquisition: one router requests that
another be its peer; peers exchange reachability information |
|
neighbor reachability: one router periodically
tests to see if the other router is still reachable; exchange HELLO/ACK
messages; uses a k-out-of-n rule |
|
routing updates: peers periodically exchange
their routing tables (distance-vector) |
|
|
|
|
|
|
Assumes the Internet is an arbitrarily
interconnected |
|
set of AS's. Define local traffic as traffic
that |
|
originates at or terminates on nodes within an
AS, |
|
and transit traffic as traffic that passes
through |
|
an AS, we can classify AS's into three types: |
|
Stub AS: an AS that has only a single connection
to one other AS; such an AS will only carry local traffic. |
|
Multihomed AS: an AS that has connections to
more than one other AS, but refuses to carry transit traffic. |
|
Transit AS: an AS that has connections to more
than one other AS, and is designed to carry both transit and local traffic. |
|
|
|
|
|
Each AS has: |
|
One or more border routers |
|
One BGP speaker that advertises: |
|
local networks |
|
other reachable networks (transit AS only) |
|
gives path information |
|
|
|
|
|
Speaker for AS 2 advertises reachability to P
and Q |
|
Network 128.96, 192.4.153, 192.4.32, and
192.4.3, can be |
|
reached directly from AS 2. |
|
Speaker for backbone network then advertises |
|
Networks 128.96, 192.4.153, 192.4.32, and
192.4.3 can be |
|
reached along the path <AS 1, AS 2>. |
|
Speaker can also cancel previously advertised
paths |
|
|
|
|
|
|
idea: allow an arbitrary collection of mobiles
to create a network on demand, without support from any “base” station or
user administration: |
|
create a network of all people attending a
working group meeting to exchange e-mail or to run groupware applications |
|
digital battlefield communications |
|
disaster relief efforts |
|
one host might have special capabilities (such
as an Internet connection) and all other machines might want to route
through it |
|
solution should coexist with existing protocols,
such as mobile IP |
|
|
|
|
|
Mobile Ad-hoc Networks (manet) at IETF:
http://www.ietf.org/html.charters/manet-charter.html |
|
A "mobile ad hoc network" (MANET) is
an autonomous system of mobile routers (and associated hosts) connected by
wireless links |
|
routers are free to move randomly and organize
themselves arbitrarily; thus, the network's wireless topology may change
rapidly and unpredictably |
|
The primary focus of the working group is to
develop and evolve MANET routing specification(s) and introduce them to the
Internet Standards track. The goal is to support networks scaling up to
hundreds of routers. |
|
|
|
|
|
|
|
|
|
DSDV: Destination-Sequenced Distance Vector
protocol |
|
basic idea: destination provides freshness
indication, not intermediate nodes |
|
each mobile host is a router |
|
periodic broadcasts with sequence numbers |
|
significant new information triggers broadcast
updates |
|
link breakages (metric ¥) are significant |
|
two criteria for route selection: |
|
sequence number guarantee maximal freshness (top
priority) |
|
metric comparison for lowest cost |
|
protocol supports incremental and full updates |
|
some routes in forwarding table might not be
advertised |
|
|
|
|
|
|
claimed properties of the DSDV protocol: |
|
loop-free at all instants |
|
dynamic, multi-hop, self-starting |
|
low memory requirements |
|
quick convergence via triggered updates |
|
routes available for all destinations |
|
fast processing time |
|
reasonable network load |
|
minimal route trashing |
|
intended for operation with 100 mobile nodes,
depending on “mobility factor” |
|
|
|
|
|
|
|
|
|
|
|
DSDV good for small ad-hoc networks |
|
Brute-force approach to larger networks |
|
requires periodic advertisements and global
dissemination of connectivity information |
|
each node has to keep complete list of routes |
|
|
|
|
|
AODV intends to improve on DSDV shortcomings |
|
basic idea: create routes only “on demand” to
eliminate overhead of periodic broadcasts |
|
problem: if purely “on demand”, could lead to
long latencies before first packet gets transmitted |
|
AODV assumes symmetric links between two nodes |
|
discover new nodes in neighborhood using local hello
messages |
|
primary objectives of AODV: |
|
broadcast discovery packets only when necessary |
|
distinguish between local connectivity changes
and general topological maintenance |
|
disseminate information about local changes only
to those neighboring mobiles that are likely to need information |
|
|
|
|
Initiated whenever a source needs to talk to
another node and does not have routing information for that node |
|
every node maintains two separate counters: node
sequence number and broadcast id (incremented for each RREQ) |
|
broadcast RREQ to neighbors, containing these
fields |
|
neighbors either reply with RREP (if they have
route to destination) or pass RREQ on to their neighbors |
|
drop RREQ if received more than once |
|
if RREQ is passed on, keep some information to
temporarily establish a reverse path for RREP and potential establishment
of path |
|
|
|
|
|
|
|
eventually, RREQ will reach a node with route to
destination |
|
problem: what if route is old? |
|
solution: source includes destination sequence
number in RREQ to indicate desired “freshness” |
|
if node’s destination sequence number is less
than the one in RREQ, keep forwarding RREQ to neighbors |
|
if acceptable route information, unicast RREP
back to neighbor who sent out RREQ, which follows reverse path back to
source, setting up route along the path |
|
nodes that are not on reverse path will timeout
and delete temporary information (timeout interval chosen appropriately,
make sure that there is enough time for route to be discovered….) |
|
if node receives multiple RREP, propagate first,
and additional ones only if they indicate better path (using DSDV
criteria): |
|
greater destination sequence number (“fresher”
route) |
|
same destination sequence number with smaller
hopcount |
|
|
|
|
|
each entry has source and destination sequence
numbers, plus soft-state information: |
|
route request expiration timer: when to delete
reverse path entries |
|
route caching timeout: when the expire an
established route (assuming that is has not been active) |
|
active indicator: routes are considered active
if node originates and/or relays packet to destination within most recent active_timeout
interval |
|
update routing table if “fresher” or better
routes become available |
|
|
|
|
|
if path breaks (hello messages, link-layer
acknowledgements), upstream nodes propagate unsolicited RREP with higher
sequence number and hop count of ¥ to all active upstream nodes |
|
according to protocol, these RREPs get forwarded
to other active nodes, eventually all active correspondents will be
informed of link failure |
|
if needed, correspondents can start
establishment of new route by issuing RREQ with destination sequence number
one higher than last known sequence number |
|
problem: how to make “smart” decision as to
whether route is still needed? |
|
|
|
|
|
|
|
Suppose MH1 moves away from MH2 towards MH7 and
has active sessions with MH3 and MH6: |
|
MH2 notices that its link to MH1 is broken |
|
MH2 checks its routing table and finds that its
link to MH1 was actively in use by MH3 and MH4 |
|
MH2 unicasts an ¥-metric route update, with an incremented
destination sequence number, to MH3 and MH4. MH3 may subsequently issue a
new route request for MH4 |
|
MH4 also notes that its route to MH1 was
actively in use and forwards a ¥ -metric route update to MH6 |
|
the ¥-metric route update for MH1 may also be
included in the next periodic limited broadcast issued by MH2 |
|
MH6 may subsequently issue a new route request
for MH1 |
|
any subsequent route request for MH1 which is
satisfied by a route reply through MH2 may cause MH2 to update its route
table |
|
|
|
|
|
Nodes move randomly with geographic region |
|
speed chosen from uniform distribution between
0.4 and 0.8 meters/second |
|
once they arrive at random location, rest for
period chosen from uniform distribution between 60 and 300 seconds |
|
2 nodes can communicate directly (are neighbors)
if they are less than 10 meters apart |
|
|
|
|
|
|
Voice: longer packets, resulting in more
collisions and longer queue lengths at intermediate nodes, which in turn
delays RREQ and RREP messages and increases route acquisition latency |
|
Bandwidth efficiency slightly higher, since
number of “control” messages the same, but more data being send |
|
|
|
|
|
|
Source Routing: sender of packet determines
complete sequence of nodes along path and lists them in packet header |
|
use dynamic route discovery to determine path |
|
advantages: |
|
no periodic routing advertisement messages |
|
saves bandwidth when there is little change in
network |
|
saves battery power (no need to send/receive
messages) |
|
ad-hoc networks have many redundant links, which
cause flooding of routing messages |
|
no assumption of link symmetry |
|
possible to react to changes faster than
state-based or distance-vector based protocols |
|
|
|
|
each node in network has route cache |
|
if route to intended destination not in cache,
initiate route discovery |
|
while using a route, monitor correct operation
of this route (i.e., make sure it does not brake) |
|
various optimizations to improve performance |
|
|
|
|
|
Node broadcasts route request message to all
hosts within transmission range |
|
route requests carry route record (sequence of
hosts visited so far) and unique request id |
|
each node maintains list of “recently seen”
route request messages |
|
upon reception of route request by a node: |
|
check whether request is a duplicate and discard |
|
check whether node is in route record and
discard |
|
if node is intended target, route record is
complete, reply with route reply |
|
otherwise, append node to route record and
re-broadcast |
|
|
|
|
|
traditionally, route maintenance implied in
periodic broadcasts of state/distance vector |
|
as configuration changes, info will eventually
spread through network |
|
route maintenance: send route error packet to
sender |
|
easy if data link layer provides hop-by-hop
acknowledgement (notification of route breaking) |
|
passive acknowledgement: if node sends packet to
neighbor, it should hear neighbor transmitting packet (symmetric links!) |
|
active acknowledgement: force neighbor to ack,
use if link has been idle for a while (no data came from next-hope node) |
|
asymmetric links: last resort would be
end-to-end acks |
|
to send route error packet: node needs route to
sender, maybe be reversing route in packet header, maybe by explicit route
discovery |
|
|
|
|
|
|
Route cache |
|
organized as tree |
|
route discovery also learns about routes to
intermediate nodes |
|
intermediate nodes learn about routes by
“snooping” on route request/reply messages and/or routing data |
|
intermediate nodes may learn routes by listening
to route discovery through neighboring nodes |
|
use route cache to reply to route requests, even
if not target node |
|
multiple hosts can answer with different routes:
how to pick best route/suppress transmission of additional replies? |
|
possibility for routing loops: node that replies
with route from cache has to check for loops before replying |
|
limit hop count for route requests |
|
|
|
|
|
piggy-backing data onto route discovery to
reduce latency |
|
if node that is not target replies to route
request, special attention is needed to make sure that the data is
forwarded to final destination |
|
reflecting shorter routes |
|
usually, as nodes move closer, they will also
move out of range in existing route, so route maintenance will take care of
this |
|
alternatively, run network interfaces in
promiscuous mode, listen to who is in your neighborhood and see whether
routes in cache can be shortened |
|
|
|
|
|
handling network partitions |
|
if nodes cannot communicate, lots of failed
route request messages, with corresponding overhead |
|
limit route requests using exponential backoff
algorithm |
|
eavesdrop on route error packets (promiscuous
mode) |
|
error packets detail hop that is down |
|
other nodes can update/invalidate routes that
use this hop in their cache |
|
keep negative information (hops that are down)
in cache for a brief period to make sure new routes do not use outdated hop |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
each paper/proposal tends to come with its own
set of performance evaluations, based on some simulated environment |
|
similar to location management proposals, no
common performance evaluation framework exists |
|
one study (November 1998): implement a number of
proposals in NS and evaluate them, compare relative advantages and
disadvantages |
|
catch: study done by authors of DSR, which ends
up being found superior |
|
|
|
|
|
Movement Model: |
|
1500m x 300m space |
|
user picks random location, moves there at a
speed randomly distributed between 0 and 20 meters/sec |
|
stay at new location for pause time second,
repeat |
|
Communication Model: |
|
10, 20, or 30 CBR sources, sending 4 packets/sec |
|
packet size is fixed at 64 bytes |
|
all communication peer-to-peer, starts at times
uniformly distributed between 0 and 180 seconds |
|
transmission range of 250 meters for each radio |
|
|
|
|
|
|
|
Performance Metrics: |
|
packet delivery ratio |
|
routing overhead |
|
path optimality |
|
Not considered: |
|
latency to establish route |
|
goodput |
|
route failures (i.e., routes break and
connection times out before new route can be established) |
|
|
|
|
|
|
|
|
|
|
|
|
Conclusions of study: |
|
each protocol performs well in come cases and
has drawbacks in others |
|
DSR performs predictably |
|
delivers virtually all data packets at low
mobility rate and speed |
|
fails to converge as node mobility increases |
|
AODV performs nearly as well as DSR at all
mobility rates and speeds |
|
accomplishes its goal of eliminating source
routing overhead |
|
requires transmission of many routing overhead
packets |
|
is more expensive than DSR of high rates of node
mobility |
|
|
|
|
|
|
|
|
|
Notes