Mô tả:
262001
Mobile & Wireless Networking
Lecture 10:
Ad Hoc Networks & Mobile Transport Layer
[Schiller, Section 8.3 & Section 9]
[Reader, Part 8]
Geert Heijenk
Mobile and Wireless Networking
2009 / 2010
Outline of Lecture 10
Ad hoc networks
Concept
Routing
Problem
DSDV (Destination Sequenced Distance Vector)
Ad-hoc On-demand Distance Vector (AODV)
DSR (Dynamic Source Routing)
Further alternatives
Mobile transport layer
Motivation
Approaches for improvement
Indirect TCP
Snooping TCP
Mobile TCP
Selective retransmission
Comparison
Recommended TCP improvements for 2.5G/3G wireless
2
Mobile and Wireless Networking
2009 / 2010
Ad hoc network concept
Networks of wireless terminals that do not necessarily rely on
existing infrastructure
Although interworking with infrastructure is possible
Direct communication between terminals when needed
Multi-hop communication
Extended concept of mobility: network mobility (moving routers)
3
Mobile and Wireless Networking
2009 / 2010
Mobile ad hoc networks
Standard Mobile IP needs an infrastructure
Home Agent/Foreign Agent in the fixed network
DNS, routing etc. are not designed for mobility
Sometimes there is no infrastructure!
remote areas, ad-hoc meetings, disaster areas
cost can also be an argument against an infrastructure!
Main topic: routing
no default router available
every node should be able to forward
A
B
C
4
Mobile and Wireless Networking
2009 / 2010
Routing examples
Routing is a major topic
in principle, every node should be able to forward
dynamic topology
asymmetric links
redundant links: too many links when terminals are close
N1
N1
N2
N3
N4
time = t1
N3
N2
N4
N5
good link
weak link
N5
time = t2
5
Mobile and Wireless Networking
2009 / 2010
Traditional routing algorithms
Distance Vector
periodic exchange of messages with all physical neighbors that contain
information about who can be reached at what distance
(monodirectional)
selection of the shortest path if several paths available
Link State
periodic notification of all routers about the current state of all physical
links (bidirectional)
router get a complete picture of the network
6
Mobile and Wireless Networking
2009 / 2010
Problems of traditional routing algorithms
Dynamic of the topology
Limited performance of mobile systems
frequent changes of connections, connection quality, participants
periodic updates of routing tables need energy without contributing
to the transmission of user data, sleep modes difficult to realize
limited bandwidth of the system is reduced even more due to the
exchange of routing information
links can be asymmetric, i.e., they can have a direction dependent
transmission quality
Problem
protocols have been designed for fixed networks with infrequent
changes and typically assume symmetric links
7
Mobile and Wireless Networking
2009 / 2010
Ad hoc routing algorithms
Pro-active
Example:
Destination Sequenced Distance Vector (DSDV)
Re-active
Example:
Ad-hoc On-demand Distance Vector (AODV)
Dynamic Source Routing (DSR)
8
Mobile and Wireless Networking
2009 / 2010
DSDV (Destination Sequenced Distance Vector)
Expansion of distance vector routing
Sequence numbers for all routing updates
assures in-order execution of all updates
avoids loops and inconsistencies
Decrease of update frequency
store time between first and best announcement of a path
inhibit update if it seems to be unstable (based on the stored time
values)
See [Schiller] for details
9
Mobile and Wireless Networking
2009 / 2010
Ad-hoc On-demand Distance Vector (AODV)
•
Specified in IETF: RFC 3561
•
Forms the basis for DYMO
(Dynamic On-demand MANET routing protocol)
which is a planned IETF reactive routing protocol.
•
Uses destination sequence numbers to avoid loops, and ensure
proper updating of routes
Storage of routes in Route Table
Uses only symmetric links
•
•
10
Mobile and Wireless Networking
2009 / 2010
Route Discovery
•
Source broadcasts Route Request (RREQ):
•
A node can reply to the RREQ if
•
•
•
•
It is the destination
It has a “fresh enough” route
to the destination
Otherwise it rebroadcasts the RREQ
Nodes keep track of
and discard redundant broadcasts
Source: Perkins & Royer
11
Mobile and Wireless Networking
2009 / 2010
Reverse Path Setup
•
•
•
Nodes update their Route Table with
source node information before
forwarding RREQ
Reverse path entry used to forward
Route Reply (RREP) back to source
if one is received
Expiration time is long enough for
a RREP to be received and forwarded
12
Mobile and Wireless Networking
2009 / 2010
Forward Path Setup
•
Destination, or intermediate node with current route to
destination, unicasts Route Reply (RREP) back to source:
•
•
•
Nodes along path record forward route
in Route Table, use reverse route
to forward RREP
Source can begin sending data
when it receives first RREP
If it later receives a RREP
with better metric,
it updates its route entry
13
Mobile and Wireless Networking
2009 / 2010
Route Table
•
Fields:
•
•
•
•
•
•
•
•
Destination IP Address
Destination Sequence Number
HopCount
Next Hop IP Address
Active Neighbors
Expiration time
Each time a route entry is used to transmit data, the expiration
time is updated to current time + active_route_timeout
Route entries may be updated if a route with greater sequence
number or smaller hopcount is discovered
14
Mobile and Wireless Networking
2009 / 2010
Path Maintenance
•
•
•
Movement of nodes not along active path
does not trigger protocol action
If source node moves, it can reinitiate route discovery
When destination or intermediate node moves,
node upstream of break sends unsolicited RREP
to all active upstream neighbors
•
•
•
•
•
∞ metric, incremented Seq#
Used to flush stale routes
RREP is propagated to their active neighbors,
and so on back to source
Source can reinitiate route discovery if route is still needed
RREQs for reinitiated route discovery contain destination
sequence number of one greater than last known number
15
Mobile and Wireless Networking
2009 / 2010
Path Maintenance (example)
•
•
•
•
Node 3 moves to new location 3’
Node 2 notices loss of link, sends link failure to Node 1
Node1 forwards link failure to Source
Source reinitiates route discovery,
finds new route through Node 4
16
Mobile and Wireless Networking
2009 / 2010
Local Connectivity Management
•
•
•
•
Node must periodically hear from active neighbors to know they
are still within range
Eavesdrop on neighbor transmissions
If no other transmissions within hello_interval, broadcast
Hello packet
Failure to hear from a neighbor for
(1+ allowed_hello_loss) * hello_interval
indicates loss of link
17
Mobile and Wireless Networking
2009 / 2010
Optimizations
•
Expanding Ring Search
•
•
RREP generated by intermediate node
•
•
•
by limiting TTL at first attempt,
and increasing it at successive attempts.
only if Seq# for route to destination ≥ Dest_Seq# of RREQ
Maintaining Local Connectivity by means of layer 2 info.
Local Repair
•
node upstream of link failure tries to find
a new route to destination by sending a RREQ
(with reduced TTL, and incremented Dest_Seq#)
18
Mobile and Wireless Networking
2009 / 2010
DSR (Dynamic Source Routing)
•
Similar to AODV
•
Big difference:
DSR uses Source Routing
• AODV relies on storing routing table entries in intermediate nodes
RREQ and RREP carry addresses of all intermediate nodes
•
See [Schiller] for details
19
Mobile and Wireless Networking
2009 / 2010
Alternative metrics
Not only the number of hops is important
Also:
interference with other stations
total energy consumption (against number of hops)
balanced energy consumption
energy availability per node
price (accounting based on forwarding effort)
20
Mobile and Wireless Networking
2009 / 2010
- Xem thêm -