View File

download report

Transcript View File

Mobile and Ad hoc Networks
Background of Ad hoc
Wireless Networks
Wireless Communication
Technology and Research
Ad hoc Routing and
Mobile IP and Mobility
Wireless Sensor and Mesh
Networks
Student Presentations
Transport Layer for Adhoc Networks
http://web.uettaxila.edu.pk/CMS/SP2012/teAWNms/
Outline
 Overview of TCP
 The problems of TCP over MANETs
 Overview of best transport protocols
 In depth
 Specific problems of TCP over MANETs
 Details of major TCP variants
 Discussion - other efforts
 Conclusion
8-2
TCP in Wired Network and MANET
Data stream in Wired Network
ACKs stream
Data stream in a MANET
TCP
Source 1
2
3
4
TCP
N Sink
ACKs stream
8-3
Network Architecture at a Crossroads
 Wireline-centric network design is “obsolete”
 New network environments have emerged
 Ad hoc, sensors, consumer-owned, delay-tolerant
 New networking technologies have emerged
 UWB, Cooperative approaches, MIMO, Directed antennas
 The R&D community recognizes the need for
change
8-4
Revisiting the Current Transport Architecture
 The vision:
 Wireless as an integral part of the network
 Multiple wireless hops: not just the last mile
(Cellular)
 Pockets of wireless ad hoc connectivity
 A new protocol stack is required
 Is TCP/IP capable of delivering?
8-5
Problem Statement
 Why does TCP perform poorly in MANETs?
 Developed for Wireline networks
 Assumes all losses congestion related
 Many TCP variants have been proposed
 How good are they?
 Are they sufficient?
 Are there any other alternatives?
 Are non-tcp protocols the solution?
8-6
Our Goal
 Identify the problems of TCP in MANETs.
 Evaluate various major TCP variants.
 12 TCP variants, 7 improvement techniques
 Observations:
 Most TCP variants are NOT sufficient.
 A new transport layer protocol may be/is
needed.
8-7
TCP Basics
 Byte Stream Delivery
 Connection-Oriented: Two communicating TCP entities
(the sender and the receiver) must first agree upon the
willingness to communicate
 Full-Duplex: TCP almost always operates in full-duplex
mode,
 TCP exhibit asymmetric behavior only during connection start and
close sequences (i.e., data transfer in the forward direction but not
in the reverse, or vice versa)
8-8
Reliable TCP Guarantees
 A number of mechanisms help provide the guarantees:
 Checksums: To detect errors with either the TCP header or data
 Duplicate data detection: Discard duplicate copies of data that has
already been received
 Retransmissions:
 For lost and damaged data
 Due to lack of positive acknowledgements
 Timeout period calls for a retransmission
 Sequencing: To deliver the byte stream data to an application in order
 Timers: Various static and dynamic timers used for deciding when to
retransmit
 Window: For flow control in the form of a data transmission
window size
8-9
Overview of TCP Concepts
Congestion
detected
32
30
2
28
26
24
n
io
st c e
e
ng an
Co oid
av
22
3
20
18
16
threshold
14
10
1
8
sta
rt
12
6
4
Fast retransmit/
fast recovery
n
io
st c e
e
ng an
Co oid
av
threshold
Slo
w

34
sta
rt

http://en.wikipedia.org/wiki/TCP_congesti
on_avoidance_algorithm
Slo
w

Conventional TCP: Tahoe, Reno, New-Reno
Sending rate is controlled by
 Congestion window (cwnd): limits the # of
packets in flight
 Slow-start threshold (ssthresh): when CA
start
Loss detection
 3 duplicate ACKs (faster, more efficient)
 Retransmission timer expires (slower, less
efficient)
Overview of congestion control mechanisms
 Slow-start phase: cwnd start from 1 and
increase exponentially
 Congestion avoidance (CA): increase
linearly
 Fast retransmit and fast recovery: Trigger
by 3 duplicate ACKs
Congestion windows size

4
2
0
0
1
2
3
4
5
6
8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
Slow-start
Congestion
Time
avoidance
7
8-10
TCP Basics
34
Congestion
detected
32
30
2
28
24
n
tio e
s
e
c
ng an
Co oid
av
22
3
20
18
16
threshold
14
6
Fast retransmit/
fast recovery
n
tio e
s
e
c
ng dan
o
i
C
o
av
sta
rt
1
8
4
threshold
Slo
w
10
sta
rt
12
Slo
w
Congestion windows size
26
4
2
0
0
1
2
3
4
5
6
7
8
9 10 11 12 13 14 15 16 17 18 19 20 21 22
Time
Slow-start
Congestion
avoidance
8-11
Congestion Control
 Slow Start (SS): A mechanism to control the transmission rate)
 When TCP connection starts (Initial Value): CWND =1,
 congestion window increases by one segment for each
acknowledgement returned
 Congestion Avoidance (CA): Used to reduce the transmission rate
 When Slow Start drops one or more packets due to congestion
 Fast Retransmit: Sender receiving triple duplicate ACKs
 Immediate transmission of missing packet without waiting for the
Retransmission Timeout to expire
 Fast Recovery: In SS or CA when sender receiving triple duplicate
ACKs  Sender only enters Congestion Avoidance mode
8-12
What is Different in MANETs?
Mobility
1.

Route stability and availability
High bit error rate
2.

Packets can be lost due to “noise”
Unpredictability/Variability
3.

Difficult to estimate time-out, RTT, bandwidth
Contention: packets compete for airtime
4.

Intra-flow and inter-flow contentions
Long connections have poor performance
5.

More than 4 hops thruput drops dramatically
8-13
Overview of Best Protocols
 TCP-Westwood [Casetti et. al.]
 Estimate bandwidth to alleviate the effect of wireless errors.
 TCP-Jersey [Xu et. al.]
 Estimate bandwidth to alleviate the effect of wireless errors.
 Congestion warning assists the determination of packet loss due to wireless
error from congestion.
 ATP [Sundaresan et. al.]
 Rate based transmission, periodic rate feedback, no timeout concept, reliability
provided by SACK.
 Split-TCP [Kopparty et. al.]
 Separating congestion control from reliability.
 Dropped packets are recovered from the most recent proxy instead of the
source.
8-14
Why Does TCP Fail in MANETs?
Specific problems are identified:
1.
2.
3.
4.
TCP misinterprets route failures as congestion
TCP misinterprets wireless errors as congestion
Intra-flow and inter-flow contention reduce
throughput and fairness
Delay spike causes TCP to invoke unnecessary
retransmissions

5.
RTO too small  unnecessary retransmissions.
Inefficiency due to the loss of retransmitted packet

When retransmitted packet is lost timer expires 
performance drops
RTO: default maximum retransmission timeout value
8-15
TCP in MANET
 TCP misinterprets route failures as congestion
 Effects: Reduce sending rate
 Buffered packets (Data and ACKs) at intermediate
nodes are dropped.
 Sender encounters timeout.
 Under prolonged disconnection, a series of
timeouts may be encountered.
8-16
TCP in MANET
 TCP misinterprets wireless errors as congestion
 Effects: Incorrect execution of congestion
control  Performance drops.
 Wireless channel is error-prone compared to
wireline
 Fading, interference, noise
8-17
TCP in MANET
 Intra-flow and inter-flow contention
 Effects: Increased delay, unpredictability, and unfairness.
 Inter-flow contention: contention of nearby flows.
 Intra-flow contention: between packets of the same flow (e.g. forward
data and reverse ACKs).
 Wireline: only packet on same link “compete”
 Wireless: all close by devices compete for the channel
Two nearby flows
Data stream
ACKs stream
8-18
Impact of Partition on Throughput
A
S
B
C
P
X
Y
Z
D
Link Failure
Data transfer continues
in spite of failure
No communication between the partitions
8-19
Effects of Partitions on TCP
Node 5 moves away from node 3 (short-term partition)
8-20
Reestablishing Path
5
2
8
1
7
3
9
6
4
The routing protocol reestablishes the path through node 6
8-21
Long Term Partition
Node 5 moves away from node 3 (long-term partition)
8-22
Long Term Network Partition
No communication between the partitions
8-23
TCP Throughput
 Larger the number of nodes a TCP connection needs to span, lower is
the end-to-end throughput, as there will be more medium contention
taking place in several regions of the network
 TCP throughput is inversely proportional to the number of
hops
8-24
Impact of Lower Layers on TCP -MAC
 It is intended for providing an efficient shared broadcast channel
through which the involved mobile nodes can communicate

In IEEE 802.11, RTS/CTS handshake is only employed when the DATA
packet size exceeds some predefined threshold

Each of these frames carries the remaining duration of time for the
transmission completion, so that other nodes in the vicinity can hear it and
postpone their transmissions

The nodes must await an IFS interval and then contend for the medium
again

The contention is carried out by means of a binary exponential backoff
mechanism which imposes a further random interval

At every unsuccessful attempt, this random interval tends to become
higher
8-25
Impact of Lower Layers on TCP -MAC


Consider a linear topology in which each node can only communicate with its
adjacent neighbors
In addition, consider that in Figures (a) and (b) there exist a single TCP
connection running between nodes 1 and 5
8-26
Capture Conditions

In Figure (c) where there are two independent connections,(connection 2-3)
(connection 4-5)

Assuming that connection 2-3 experiences collision due to the hidden node
problem caused by the active connection 4-5 , node 2 will back off and retransmit
the lost frame

At every retransmission, the binary exponential backoff mechanism imposes an
increasingly backoff interval, and implicitly, this is actually decreasing the
possibility of success for the connection 2-3 to send a packet as connection 4-5 will
“dominate” the medium access once it has lower backoff value

In consequence, the connection 2-3 will hardly obtain access to the medium while
connection 4-5 will capture it
8-27
Network Layer Impact
 Routing strategies play a key role on TCP
performance
 There have been a lot of proposed routing
schemes and, typically, each of them have
different effects on the TCP performance
8-28
DSR
 DSR protocol operates on an on-demand basis in which a
node wishing to find a new route broadcasts a RREQ
packet
 The problem with this approach concerns the high
probability of stale routes in environments where high
mobility as well as medium constraints may be normally
present
 The problem is aggravated by the fact that other nodes can
overhear the invalid route reply and populate their buffers
with stale route information
 It can be mitigated by either manipulating TCP to tolerate
such a delay or by making the delay shorter so that the
TCP can deal with them smoothly
8-29
TORA
 TORA has been designed to be highly dynamic by establishing
routes quickly and concentrating control messages within a
small set of nodes close to the place where the topological
change has occurred
 TORA makes use of directed acyclic graphs, where every node
has a path to a given destination and established initially
 This protocol can also suffer from stale route problem similar to
the DSR protocol
 The problem occurs mainly because TORA does not prioritize
shorter paths, which can yield considerable amount of out-ofsequence packets for the TCP receiver, triggering retransmission
of packets
8-30
Path Asymmetry Impact
 In Ad hoc networks, there are several Asymmetries
 Loss Rate Asymmetry: It takes place when the backward path
is significantly more error prone than the forward path
 Bandwidth Asymmetry: Arises when forward and backward
data follow distinct paths with different speeds
 Can happen in ad hoc networks when all nodes not have the same
interface speed
 Media Access Asymmetry: Arises when TCP ACKs and Data
are contending for the same
8-31
Route Asymmetry
 Route asymmetry implies having different paths in both
directions
 Route asymmetry is associated with the possibility of
different transmission ranges for the nodes
 The inconvenience with different transmission ranges is that
it can lead to conditions in which the forward data follow a
considerably shorter path than the backward data (TCP
ACK) or vice versa --> affecting hop counts and delays
(RTT)
 Multi-hop paths are prone to have lower throughput and TCP
ACKs may face considerable disruptions
8-32
Overview of Results
 The best TCP variants:
 TCP-Westwood and TCP-Jersey seem the best.
 Both protocols estimate bandwidth more accurately.
 TCP mechanisms:
 Feedback from intermediate nodes leads to big gains.
 The best non-TCP approaches:
 Ad-hoc Transport Protocol (ATP) seems to address most issues
 Non-window based: estimates achievable rate periodically
 Split-TCP: promising new way of looking at transport layer
 Dynamically buffer packets mid-path
 Key: Separation of congestion control from reliability.
8-33
Assignment #8
 Write note on the TCP and non-TCP approaches for
Transport Layer of Ad hoc Networks highlighted in
Yellow.
Q&A
 ?