SAHNS07

SAHNS07

Motivation

TCP Protocol

Congestion Control in TCP Protocol

AIMD Windows Size Adjustment

TCP Problems on Ad-Hoc Networks

TCP Problems on MANET

Frequent Slow Start

How to Improve?

Problem of Loss-Based TCP

Objectives

Related Work

Related Work

TCP-F (TCP-Feedback)

TCP-ELFN

ATCP (Ad Hoc TCP)

Adaptive CWL (Congestion Window Limit)

Our Approach

Design Philosophy

Design Issues

TCP Muzha

TCP Muzha

Modification of slow-start

Estimation and Sharing of Available Bandwidth

Data Rate Adjustment Index

Minimum Data Rate Adjustment Index

Handling of Random loss

TCP Muzha - Two Phases

Congestion Control in TCP Muzha

Performance Evaluation

Performance Evaluation - Experiment Setup

Performance Evaluation - CWND

Performance Evaluation - CWND

Performance Evaluation - Throughput

Performance Evaluation - Retransmission

Fairness Test

Fairness comparison - Throughput

Fairness comparison - Jain's Index

Fairness Test 2

Test - Chain Topology

Test - Cross Topology

Conclusion

Motivation

⊕ TCP over MANET is poor

⊕ In MANET, nodes perform routing

⊕ We use routers to help TCP

TCP Protocol

a transport layer protocol
guarantee data delivery
data flow driven by acknowledge packets
built-in with a congestion control mechanism
perform well without any support from the network elements at IP layer

Congestion Control in TCP Protocol

Utilize resource as much as it can
Avoid congestive collapse
Dissolve congestion

⊕ Delay-Based Congestion Control

♦ Use RTT to control data rate (CWND Size)

⊕ Loss-Based Congestion Control

♦ Congestion Signal - Packet Loss

AIMD Windows Size Adjustment

trial-and-error based flow control
slower in increasing phases, faster in decreasing phases

♦ Slow Start

♦ Congestion Avoidance

♦ Fast Retransmits and Fast Recovery

TCP Problems on Ad-Hoc Networks

⊕ Wireless network is Unreliable

Many packets may be lost due to noisy channels, but not network congestion, However, congestion control is triggered anyway

♦ Mobile Wireless network is even more unreliable

⊕ Ad-Hoc Network is Slow and Easy to congested

Contention based Media Access Protocol
Broadcast nature of Radio Signals - Blocking Effect
Forwarding and Routing performed in every node

TCP Problems on MANET

⊕ Packet losses in MANET can be classified into

Congestion loss
Random loss or Transmission error
Link failure or route change (in most case)

♦ Congestion Control takes no difference

cause frequent triggering of slow-start (time-out or 3 duplicate ACK)

Frequent Slow Start

Connections spend most of time in Slow Start phase due to frequent timeout -- up to 40% of connection time

It takes several RTTs for slow-start to reach the max. available bandwidth

End of slow-start phase tends to generate too much packets

Frequent network overloaded!!

How to Improve?

⊕ Distinguish random loss from congestion loss

⊕ Avoid unnecessary congestion window overshoot

Use Router to Help

♦ Router can indicate its own condition and offer CWND adjustment advice

Problem of Loss-Based TCP

♦ Unaware of Network Status

♦ Use Trial-and-error style congestion control

Resuling in poor CWND control -- overshoot and slow start

Objectives

♦ Design a new TCP congestion control mechanism that is aware of network condition over MANET

♦ The protocol can dynamically respond with different situations according to the explicit information from routers

Related Work

Related Work

Related Work

⊕ Router-assisted congestion control

♦ TCP-F (TCP-Feedback)

♦ TCP-ELFN (Explicit Link Failure Notification)

♦ ATCP (Ad Hoc TCP)

All of them use users to feedback link failure or random loss

⊕ Other Proposals

♦ Adaptive CWL (Congestion Window Limit)

TCP-F (TCP-Feedback)

♦ Sender is able to distinguish route failure and network congestion

♦ Network components detect the route failure and notify sender by RFN packet (Route Failure Notification)

♦ Sender then freezes all the variable (RTO and cwnd) until it receives the RRN packet (Route Recovery Notification)

TCP-ELFN

♦ (Explicit Link Failure Notification)

This scheme is based on DSR (Dynamic Source Routing)

♦ ELFN message is similar to “host unreachable” ICMP message. It contains:

Sender and receiver address

Ports

Packet sequence number

♦ Sender disables its retransmission timer and enter “standby mode” after receiving ELFN

♦ Then sender keeps probing the network by sending a small packet to restored the route (nature of DSR)

ATCP (Ad Hoc TCP)

♦ A layer called ATCP is inserted between the TCP and IP layers of the source node

♦ ATCP listens to the network state by

ECN (Explicit Congestion Notification) message

Congestion!!

ICMP “Destination Unreachable” message

Network Partitioning!!

♦ Sender can be put into 3 states:

Persist State – by ICMP message

Congestion Control State – by ECN message

Retransmit State – by packet loss without ECN flag

Note - After receiving three duplicate ACKs, sender does not invoke congestion control and puts TCP in Persist State and quickly retransmit the loss packet from buffer ( Multipath routing or channel loss)

♦ Recomputation of congestion window size after route re-establishment

Adaptive CWL (Congestion Window Limit)

♦ If the congestion window size is greater than an upper bound, the TCP performance will degrade.

♦ Find the BDP (Bandwidth Delay Product) of a path in MANET

♦ They use this upper bound of BDP to dynamically adjust TCP’s max. window size

Our Approach

Our Approach

Design Philosophy

⊕ Design Objectives

Allowing sender to reach appropriate sending rate quickly
Fully utilize the available bandwidth alone the path
Dissolve congestion
Provide fairness with other TCP variants

⊕ Design Philosophy

Distinguish the loss between congestion loss and random loss
Reducing the chance of congestion
Identify the bottleneck and share its residual bandwidth

Design Issues

♦ Estimation and sharing of the residual bandwidth in a router (node)

♦ Determine the bottleneck w.r.t a TCP path

♦ Fairness

♦ Recovery of random lost packets

TCP Muzha

TCP Muzha

TCP Muzha

Sender function	Modification of Slow Start
Router function	Estimation of residual bandwidth Determine CWND adjustment advice (compute DRAI value) Determine minimum DRAI value Handling random loss
Receiver function	Return ACK with DRAI back to Sender

Modification of slow-start

⊕ Avoid trial-and-error style CWND control

♦ Sender adjusts its sending rate according to the router feedback

♦ More accurate CWND adjustment can reduce overshooting problem

⊕ Slow start is only activated when ACK is blocked

Estimation and Sharing of Available Bandwidth

♦ Assume each router can determine its own load (and residual bandwidth) based on QoS statistics

Option 1 : Direct publish actual available bandwidth	Option 2 : Publish (available bandwidth)/ (# of TCP flows)	Option 3 : Our approach - feedback DRAI
May seduce greedy TCP senders and cause bandwidth fluctuation	Router has to be TCP-aware	Routers compute a quantized index according to available bandwidth as a guideline for sender to adjust sending rate

Data Rate Adjustment Index

Advice	DRAI	Change of CWND
Aggressive Acceleration	5	CWND = CWND *2
Moderate Acceleration	4	CWND = CWND+1
Stabilizing	3	CWND = CWND
Moderate Deceleration	2	CWND = CWND -1
Aggressive Deceleration	1	CWND =CWND *1/2

Pros	Cons
Reduce Consistency Problem caused by different bandwidth computation Simplicity and Ease of implementation More delicate than ECN, which is a bi-level DRAI	Number of levels determined by simulation

Minimum Data Rate Adjustment Index

♦ Each router estimates available bandwidth itself and convert this into DRAI

♦ Then each router compares and marks every passed packet with DRAI

If the value is greater, then DRAI stays untouched
Otherwise, replaces it with new DRAI
The smallest value of DRAI will reach the receiver -- Minimum data Rate Adjustment Index (MRAI)

Handling of Random loss

⊕ Effect of random loss

Timeout or 3 Duplicated ACK	Reduction of congestion window size

⊕ Our approach

♦ Router detects random loss and feedback

3 duplicate ACK with deceleration marking (congestion)
3 duplicate ACK with acceleration marking or no marking (random loss)

TCP Muzha - Two Phases

♦ We simplify three phases of TCP NewReno into two phases
⊕ Congestion Avoidance (CA)
⊕ Fast Retransmit and Fast Recovery (FF)

⊕ Slow start is only activated when ACK is blocked

Congestion Control in TCP Muzha

Event	Status	Sender Behavior	Note
Receive the ACK of the pervious packet	Congestion Avoidance (CA)	Dynamically adjust CWND according to the returning MRAI	Adjust CWND in every RTT
Receiving marked 3 duplicate ACKs	Congestion Avoidance (CA)	(1)CWND = CWND * (1/2) (2) Enter FF phase	Fast respond and half the CWND
Receiving 3 duplicate ACKs	Congestion Avoidance (CA)	(1) Enter FF phase without change of CWND	Retransmit the lost packets
Timeout	Congestion Avoidance (CA)	(1)CWND = 1 (2)Re-enter CA phase	Re-enter the CA phase

Performance Evaluation

Performance Evaluation

Performance Evaluation - Experiment Setup

NS-2 Network Simulator	Chain topology (4~32 hops)

Link Layer	IEEE 802.11 MAC
Bandwidth	2MB/s
Transmission Radius	250m
Routing	AODV
Evaluation Metrics	CWND change, Throughput Retransmission, Fairness

Performance Evaluation - CWND

Performance Evaluation - CWND

Performance Evaluation - Throughput

Performance Evaluation - Retransmission

Fairness Test

♦ Cross Topology

♦ TCP Vegas vs. TCP NewReno

♦ TCP Muzha vs. TCP NewReno

♦ Jain's Fairness Index

N: Number of Flow

Xi: throughput of the i-th flow

Fairness test 1 Avg. Throughput
Fairness test 2 Throughput Dynamics

Num. of Hops 4, 6, and 8
Bandwidth 2Mbps
Simulation time 50 sec.

Fairness comparison - Throughput

Fairness comparison - Jain's Index

Fairness Test 2

♦ 3 flows of same TCP, each starts at different times

Test - Chain Topology

♦ 4 Hops

	TCP NewReno	TCP Vegas	TCP Muzha
Avg. Throughput (Kbps)	175	214	186
Avg. Retransmission	14	6	10
Fairness (with NewReno)		0.925	0.99

♦ 6 Hops

	TCP NewReno	TCP Vegas	TCP Muzha
Avg. Throughput (Kbps)	54	89	65
Avg. Retransmission	16	6	10
Fairness (with NewReno)		0.74	0.99

♦ 8 Hops

	TCP NewReno	TCP Vegas	TCP Muzha
Avg. Throughput (Kbps)	34	35	37
Avg. Retransmission	25	9	18
Fairness (with NewReno)		0.89	0.99

Test - Cross Topology

♦ Cross Topology - 4 Hops

Vegas+NewReno

Muzha+NewReno

	Throughput (Kbps)	Delay (ms)
Flow1 (Vegas)	35.7	72.4
Flow2 (NewReno)	118.0	100.4
Aggregate	153.7
Fairness	0.72

	Throughput (Kbps)	Delay (ms)
Flow1 (Muzha)	106.0	63.9
Flow2 (NewReno)	102.0	65.3
Aggregate	208
Fainess	0.99

♦ Cross Topology - 6 Hops

Vegas+NewReno

Muzha+NewReno

	Throughput (Kbps)	Delay (ms)
Flow1 (Vegas)	23.2	264.0
Flow2 (NewReno)	89.9	101.6
Aggregate	113.1
Fairness	0.74

	Throughput (Kbps)	Delay (ms)
Flow1 (Muzha)	65.3	119.5
Flow2 (NewReno)	53.6	112.4
Aggregate	118.9
Fairness	0.99

♦ Cross Topology - 8 Hops

Vegas+NewReno

Muzha+NewReno

	Throughput (Kbps)	Delay (ms)
Flow1 (Vegas)	20.2	91.9
Flow2 (NewReno)	41.7	168.0
Aggregate	61.9
Fairness	0.89

	Throughput (Kbps)	Delay (ms)
Flow1 (Muzha)	43.7	97.2
Flow2 (NewReno)	36.8	112.4
Aggregate	80.5
Fairness	0.99

Conclusion

♦ We proposed a new TCP scheme over MANET by router-assisted approach in order to improve the performance of TCP.

♦ By assistance of router, our scheme has about 5%~10% throughput improvement and less retransmission in MANET, as compared with TCP NewReno and TCP SACK via

its dynamic data rate adjustment mechanism and

the ability to deal with random loss

⊕ TCP over MANET is poor

⊕ In MANET, nodes perform routing

⊕ We use routers to help TCP

⊕ Delay-Based Congestion Control

♦ Use RTT to control data rate (CWND Size)

⊕ Loss-Based Congestion Control

♦ Congestion Signal - Packet Loss

♦ Slow Start

♦ Congestion Avoidance

♦ Fast Retransmits and Fast Recovery

⊕ Wireless network is Unreliable

Many packets may be lost due to noisy channels, but not network congestion, However, congestion control is triggered anyway

♦ Mobile Wireless network is even more unreliable

⊕ Ad-Hoc Network is Slow and Easy to congested

⊕ Packet losses in MANET can be classified into

♦ Congestion Control takes no difference

cause frequent triggering of slow-start (time-out or 3 duplicate ACK)

Connections spend most of time in Slow Start phase due to frequent timeout -- up to 40% of connection time

It takes several RTTs for slow-start to reach the max. available bandwidth

End of slow-start phase tends to generate too much packets

Frequent network overloaded!!

⊕ Distinguish random loss from congestion loss

⊕ Avoid unnecessary congestion window overshoot

♦ Router can indicate its own condition and offer CWND adjustment advice

♦ Unaware of Network Status

♦ Use Trial-and-error style congestion control

Resuling in poor CWND control -- overshoot and slow start

♦ Design a new TCP congestion control mechanism that is aware of network condition over MANET

♦ The protocol can dynamically respond with different situations according to the explicit information from routers

⊕ Router-assisted congestion control

♦ TCP-F (TCP-Feedback)

♦ TCP-ELFN (Explicit Link Failure Notification)

♦ ATCP (Ad Hoc TCP)

All of them use users to feedback link failure or random loss

⊕ Other Proposals

♦ Adaptive CWL (Congestion Window Limit)

♦ Sender is able to distinguish route failure and network congestion

♦ Network components detect the route failure and notify sender by RFN packet (Route Failure Notification)

♦ Sender then freezes all the variable (RTO and cwnd) until it receives the RRN packet (Route Recovery Notification)

♦ (Explicit Link Failure Notification)

This scheme is based on DSR (Dynamic Source Routing)

♦ ELFN message is similar to “host unreachable” ICMP message. It contains:

Sender and receiver address

Ports

Packet sequence number

♦ Sender disables its retransmission timer and enter “standby mode” after receiving ELFN

♦ Then sender keeps probing the network by sending a small packet to restored the route (nature of DSR)

♦ A layer called ATCP is inserted between the TCP and IP layers of the source node

♦ ATCP listens to the network state by

ECN (Explicit Congestion Notification) message

Congestion!!

ICMP “Destination Unreachable” message

Network Partitioning!!

♦ Sender can be put into 3 states:

Persist State – by ICMP message

Congestion Control State – by ECN message

Retransmit State – by packet loss without ECN flag

Note - After receiving three duplicate ACKs, sender does not invoke congestion control and puts TCP in Persist State and quickly retransmit the loss packet from buffer ( Multipath routing or channel loss)

♦ Recomputation of congestion window size after route re-establishment

♦ If the congestion window size is greater than an upper bound, the TCP performance will degrade.

♦ Find the BDP (Bandwidth Delay Product) of a path in MANET

♦ They use this upper bound of BDP to dynamically adjust TCP’s max. window size

⊕ Design Objectives

⊕ Design Philosophy

♦ Estimation and sharing of the residual bandwidth in a router (node)

♦ Determine the bottleneck w.r.t a TCP path

♦ Fairness

♦ Recovery of random lost packets

⊕ Avoid trial-and-error style CWND control

♦ Sender adjusts its sending rate according to the router feedback

♦ More accurate CWND adjustment can reduce overshooting problem

⊕ Slow start is only activated when ACK is blocked

♦ Assume each router can determine its own load (and residual bandwidth) based on QoS statistics

♦ Each router estimates available bandwidth itself and convert this into DRAI

♦ Then each router compares and marks every passed packet with DRAI

⊕ Effect of random loss

⊕ Our approach

♦ Router detects random loss and feedback

♦ We simplify three phases of TCP NewReno into two phases

⊕ Congestion Avoidance (CA)

♦ By assistance of router, our scheme has about 5%~10% throughput improvement and less retransmission in MANET, as compared with TCP NewReno and TCP SACK via

its dynamic data rate adjustment mechanism and

the ability to deal with random loss