Ad hoc communication
Download
Report
Transcript Ad hoc communication
Communication Research Labs Sweden AB
Course element content for Ad hoc
•Lecture 1 (Ad hoc concept and networking overview)
•Ad hoc concept
•Ad hoc basic functionality
•Ad hoc possible usage areas
•Background of ad hoc
•Networking: OSI, Protocols, routing, TCP/IP
•Project description (briefly)
•Lecture 2 (Networking and routing in depth)
•TCP/IP in depth
•Routing protocols: purpose, conceptual function and review
•Standardization work: IETF, IEEE current protocols
•Additional ad hoc routing features
•Lecture 3 (Advanced concepts)
•ARP, MAC layer
•Quality of Siervice (QoS): SNR, Bandwidth constraints, Neighbor solicitation errors
•IPv6 (briefly)
•Security issues for ad hoc networks (briefly)
Ad hoc communication: Concept, OSI and TCP/IP
Communication Research Labs Sweden AB
Routing algorithms in general
(Not ad hoc specific!)
Purpose:
•
•
Means of discovering paths in a (data) network along which information can be sent.
Allows routing in large/complex networks without the need of manual configuration.
Example of applications:
•
•
Public Switched Telephone Network (PSTN)
The Internet
Example of wired routing algorithms:
•
•
•
Open Shortest Path First (OSPF)
Routing Information Protocol (RIP)
Border Gateway Protocol (BGP)
Communication Research Labs Sweden AB
The 7-Layer OSI Reference Model
7 - Application Layer
6 - Presentation Layer
Network
Operating
System
(NOS)
802.3
Ethernet
•
•
•
•
•
802.4
Token Bus
802.5
Token Ring
802.11
Wireless LAN
5 - Session Layer
4 - Transport Layer
TCP
3 - Network Layer
IP
2 - Data Link Layer
802.2Logical Link Control (LLC)
Medium Access Control (MAC)
1 - Physical Layer
Divides the functions of protocols into a series of layers.
Often referred to as a protocol stack.
Each layer performs services for the next higher layer and makes requests of the
next lower layer.
Is an ISO standard.
Often simplified to a 5-layer model.
Communication Research Labs Sweden AB
Simplified OSI Reference Model
(Examples of each layer)
HyperText
Application
Transfer
Layer
Protocol
Transmission
Transport
ControlLayer
Protocol (TCP)
Internet
Network
Protocol
Layer(IP)
Data
Ethernet
Link(MAC)
Layer
Physical
Layer
802.11x
Communication Research Labs Sweden AB
The Data Link Layer – Layer 2
•
•
•
•
Provides a reliable data transfer over a physical link.
May detect and possibly correct errors occurred at the physical layer.
All IEEE 802 compatible devices has a unique Media Access Control (MAC)
address.
The MAC addresses are used for identification on point-to-point (link)
communication.
Communication Research Labs Sweden AB
The Network Layer – Layer 3
•
•
•
•
•
Responsible for end-to-end packet delivery.
Determines the route from source to destination.
Most famous Network Layer Protocol is the Internet Protocol, IPv4.
Provides logical addressing, such as the IP addresses.
IP provides an unreliable packet service (best effort). Reliability is typically
performed at higher level protocols like TCP.
Communication Research Labs Sweden AB
Layer 7 example: HTTP
Objective: We want to transmit a HyperText Transfer Protocol
HTTP/1.1 200 OK
Date: Tue, 1 November 2005 12:38:34 GMT
Server: Apache/1.3.27 (Linux)
Last-Modified: Wed, 08 Jan 2003 23:11:55 GMT
Accept-Ranges: bytes
Content-Length: 188
Content-Type: text/html; charset=UTF-8
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html>
<head>
<title>
Communication Research Labs Sweden AB
</title>
</head>
<body>
...
</body>
</html>
HTTP object
(HTTP/1.1 200 OK\n Date:Tue, 1 November 2005 12:38:34 GMT\nServer: Apache/1.3.27 ...)
Communication Research Labs Sweden AB
Layer 4 example: TCP
TCP PAYLOAD
(i.e. the HTTP object)
HTTP/1.1 200 OK\nDate: Tue, 1 November 2005 12:38:34 GMT\nServer: Apache/1.3.27 (Linux)\nLast-Modified: Wed, 08 Jan 2003
23:11:55 GMT\nAccept-Ranges: 148 bytes\nContent-Length: 188\nContent-Type: text/html; charset=UTF-8\n<!DOCTYPE html PUBLIC "//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1transitional.dtd">\n<html>\n<head>\n<title>\nCommunication Research Labs Sweden
AB</title>\n</head>\n<body>\n...\n</body>\n</html>\n
Payload is to large.
TCP PAYLOAD Fragmentation needed!
TCP
HEADER
HTTP/1.1 200 OK\nDate: Tue, 1 November 2005 12:38:34 GMT\nServer:
Apache/1.3.27 (Linux)\nLast-Modified: Wed, 08 Jan 2003 23:11:55
GMT\nAccept-Ranges: 148 bytes\nContent-Length: 188\nContent-Type:
text/html; charset=UTF-8\n<!DOCTYPE html PUBLIC "//W3C//DTD XHTML 1.0 Transitional//EN"
TCP
HEADER
"http://www.w3.org/TR/xhtml1/DTD/xhtml1transitional.dtd">\n<html>\n<head>\n<title>\nCommunication
Research Labs Sweden
AB</title>\n</head>\n<body>\n...\n</body>\n</html>\n
(Fragment 1)
TCP PAYLOAD
(Fragment 2)
Communication Research Labs Sweden AB
Layer 2 & 3 example: IP & MAC
TCP
HEADER
TCP PAYLOAD
(Fragment 1)
IP
HEADER
TCP
HEADER
MAC
HEADER
IP
HEADER
TCP PAYLOAD
(Fragment 1)
TCP
HEADER
TCP PAYLOAD
(Fragment 1)
Communication Research Labs Sweden AB
Layer 1 example: PHY
MAC
HEADER
IP
HEADER
• Line coding (0010
TCP
HEADER
TCP PAYLOAD
(Fragment 1)
)
0010 1100 0101 …
• Channel coding (01010
01010 11100 01101 …)
• Modulation
Communication Research Labs Sweden AB
IPv4 Header overview
0 bit
32
Version IHL Type of Service
Total Length
64
Identification
0 DM
FF
Fragment offset
Time To Live
0 bit
Version
IHL
Type of Service
Identification
IP header
Total Length
DM
M
00 D
Time To Live
Protocol
FF
F
F
Fragment
offset
Fragment
offset
Header Checksum
Source Address
Destination Address
Transport Layer Data….
Communication Research Labs Sweden AB
32
64
96
128 bit
160
…..
Standardization work
The Internet Engineering Task Force (IETF)
• Charged with developing and promoting Internet standards,
in particular, those of the TCP/IP protocol suite
• Organized into a large number of Working Groups (WGs),
each dealing with a specific topic, and intended to complete
work on that topic and then shut down.
• IETF MANET WG is dedicated to MANET research in
deployment of open standards for ad hoc routing protocols.
Communication Research Labs Sweden AB
Standardization work
IETF – MANET Workgroup
Internet-Drafts:
• The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks (DSR)
• Dynamic MANET On-demand (DYMO) Routing
• Simplified Multicast Forwarding for MANET
• The Optimized Link-State Routing Protocol version 2
Request For Comments:
• Mobile Ad Hoc Networking (MANET): Routing Protocol Performance Issues and
Evaluation Considerations (RFC2501)
• Ad Hoc On Demand Distance Vector (AODV) Routing (RFC 3561)
• Optimized Link-State Routing Protocol (RFC 3626)
• Topology Dissemination Based on Reversed-Path Forwarding (TBRPF) (RFC 3684)
Communication Research Labs Sweden AB
Ad hoc routing protocols
•
AODV
•
DSR
•
OLSR
•
TBRPF
Ad hoc On demand Distance Vector Protocol
(IETF RFC #3561)
Dynamic Source Routing Protocol
(IETF DRAFT #09)
Optimized Link State Routing Protocol
(IETF RFC #3626)
Topology Dissemination Based on
Reverse-Path Forwarding
(IETF RFC #3684)
Will used in one of the projects.
Communication Research Labs Sweden AB
Routing / mobility management
(Repetition from the first lecture)
Proactive Routing
Reactive Routing
• Continuously updates the
network topology
• Requested routes are
immediately available
• Network resources are wasted
• Route discovery on demand
• Might cause some initial delay
• Consumes less network
resources
• Silent network
Communication Research Labs Sweden AB
Ad hoc communication with WLAN
802.11 MAC Layer Service Set
Infrastructure Mode
Extended Service Set
(ESS)
Ad hoc Mode
Independent Basic Service Set
(IBSS)
Communication Research Labs Sweden AB
Limitations with WLAN
B
A
B
A
C
C
Uni-directional link
•
•
•
•
Bi-directional link
The Data Link Layer (MAC Layer) in IEEE 802.11 requires bi-directional
links for point-to-point communication.
Broadcasted messages is done at a lower bit rate and thereby travel further.
Broadcasted transmissions are not guaranteed to be bi-directional, unlike
unicasted transmissions.
Small packets are often used to discover routes. However, small packets
are less prone to bit errors than large packets.
Communication Research Labs Sweden AB
Ad hoc On-demand Distance Vector
(AODV)
• Reactive routing protocol.
• The User Datagram Protocol (UDP), Layer 4, is used for locating
and maintaining routes.
• Uses Expanding Ring Search to locate destinations.
• Simple, yet effective routing algorithm.
Communication Research Labs Sweden AB
AODV Route Establishment
RREQ
RREP
•
•
•
•
•
RREQ
RREP
RREQ
RREP
RREQ
RREP
Expanding Ring Search (ERS) limits data packets from traversing through
the entire network.
Route Requests are broadcasted!
All routing messages MUST contain node specific sequence numbers which
are incremented for every transmission.
Each node MUST record and maintain sequence numbers for all known
destinations.
A received message with lower sequence number than recorded is to be
discarded to ensure loop freedom at all times.
Communication Research Labs Sweden AB
AODV Connectivity
• Each forwarding node MUST ensure connectivity to its active next
hops.
• Most implementations of AODV uses hello messages to offer
connectivity.
A hello message is a broadcasted message with hop limit of one.
This also allows nodes to always keep track of its neighbors.
• Broken links has to be reported by sending a Route Error message
to adjacent nodes.
Connectivity lost. Sending
Route Error!
RERR
Communication Research Labs Sweden AB
AODV Characteristics
Advantages:
• Low processing.
• Low network utilization.
• Low memory overhead.
Disadvantages:
• Initial latency while requesting new routes. (Reactive routing)
• Sensitive to unstable links (for instance when used in WLAN).
• Does not support multi-path, load balancing or weighting of routes.
Communication Research Labs Sweden AB
Optimized Link-State Routing
(OLSR)
•
•
•
•
Proactive routing protocol.
Table driven (i.e. nodes exchange topology information).
Quality aware algorithm.
Uses the User Datagram Protocol (UDP) for topology propagation.
Communication Research Labs Sweden AB
OLSR Multipoint relays (MPR) – 1 of 3
• Each node selects a set of its neighbor nodes as Multipoint Relays
(MPR) by two rules: any 2-hop neighbor must be covered by at least
one MPR and the number of MPRs be as low as possible.
• Only MPRs advertises (floods) their current links.
1
2
4
A
B
3
5
6
• MPRs was first introduced in HiperLAN, a ETSI standard similar to
WLAN.
Communication Research Labs Sweden AB
OLSR Multipoint relays (MPR) – 2 of 3
Left image:
• Normal flooding.
Right image:
• MPRs are the only nodes that may forward (flood) messages.
Communication Research Labs Sweden AB
OLSR Multipoint relays (MPR) – 3 of 3
Communication Research Labs Sweden AB
OLSR Route Establishment
• Every node periodically broadcasts hello messages in order to
exchange neighborhood information. (IP address, route weight,
distance, sequence number etc.)
• MPRs propagates the topology information in the network.
• Hello messages allows nodes to calculate the shortest/best route to
other nodes.
• The information is only updated when:
1. The neighborhood has changed.
2. A route has expired.
3. A better route is detected.
Communication Research Labs Sweden AB
OLSR Characteristics
Advantages:
• Minimal latency.
• Supports multi-path.
• Supports route weighting. (i.e. the cost of using a certain route)
Disadvantages:
• High routing control overhead traffic.
• High demands on memory, computational capacity and power.
• Complex (implementation)!
Communication Research Labs Sweden AB
Dynamic Source Routing
(DSR)
• Reactive routing protocol.
• Modifies every IP packet with an additional header, DSR Header.
Example:
IP
DSR
TCP
HEADER HEADER HEADER
TCP PAYLOAD
Communication Research Labs Sweden AB
DSR Route Discovery
• A Route Request is preformed as in AODV but with one great
difference: Each node adds its own IP address in the request.
• The Route Discovery mechanism in DSR allows intermediate nodes
to eavesdrop on routes.
• The destination of a Route Request reverses the the route in the
received request. Thereby, the return-path is found.
X
A
”A”
Id=2
X
X
B
”A,B”
Id=2
X
C
”A,B,C”
X
D
Id=2
X
Communication Research Labs Sweden AB
X
DSR Route Maintenance
• Every node is responsible for confirming that the next hop in the
DSR Header receives the packet.
• Packets are retransmitted up to a maximum number of times. If the
retransmission fails, a Route Error message is sent to the initiator of
the packet.
Communication Research Labs Sweden AB
DSR Characteristics
Advantages:
• Forwarding nodes do not need to know the path (memory efficient).
• Does not transmit any routing data (overhead) when there is no data
traffic.
• Simple, yet very effective!
• Natively supports uni-directional links, however, the MAC protocols
in IEEE 802.11 does not.
Disadvantages:
• Source routing information (the DSR Header) increases per hop.
(e.g. IP packet size increases per hop)
• Initial latency while requesting new routes. (Reactive routing)
Communication Research Labs Sweden AB
Zone Routing Protocol
(ZRP)
•
•
Hybrid routing protocol.
Consists of 3 routing algorithms
1. Intrazone Routing Protocol (IARP) (Proactive)
2. Interzone Routing Protocol (IERP) (Reactive)
3. Bordercast Resolution Protocol (BRP) (Reactive)
Communication Research Labs Sweden AB
ZRP Characteristics
Advantages:
• No initial delay within a cluster.
• Takes advantage of pro-active route discovery within a nodes local
neighborhood.
Disadvantages:
• Small initial delay in cluster-cluster communication.
• Complex (implementation)!
Communication Research Labs Sweden AB
Different routing approaches
•
•
•
•
•
UDP based routing packets. (Most common)
TCP based routing packets.
Self-defined IP Header. (e.g. DSR)
Usage of the ARP - Address Resolution Protocol. (Next lecture)
IPv6 Routing Header. (Next Lecture)
Communication Research Labs Sweden AB
Additional advanced features
•
Promiscuous mode
•
•
•
•
Setting the network interface into promiscuous mode.
Listen to all data packets within reach.
A node can catch and examine all routing specific packets, even if the target
address of the packets is neither broadcast nor its own IP.
Network can save a lot of overhead packets by using such information:
•
•
•
Passive acknowledgement of a transmitted packet by overhearing the next node forward the
same packet.
route shortening. When a node is overhearing a packet with a source route where this node is
used later in the route, but not the next hop, it can send back a gratuitous route reply to the
original sender of the packet, telling it there is a shorter route to the destination.
Gratuitous Route errors
A node that is receiving a route error can, in addition to update its route cache, also
resend the route error to its neighbors with the next route request. By caching recent
route errors, the node can also assure that an incoming route reply does not deliver
an old previously broken link.
Communication Research Labs Sweden AB
Ad hoc communication
References
•
Standardization
•
•
•
IETF MANET WG: http://www.ietf.org/html.charters/manet-charter.html
Mobile Ad hoc Networking (MANET): Routing Protocol Performance Issues
and Evaluation Considerations (RFC 2501)
How 802.x Wireless Works:
http://www.microsoft.com/technet/prodtechnol/windowsserver2003/library/Te
chRef/370b019f-711f-4d5a-8b1e-4289db0bcafd.mspx
Communication Research Labs Sweden AB