WiMoN

Hop-by-Hop_TCP

Outline

MANET and Sensor Network

TCP

TCP

Flow control & Congestion control

Design Objectives of TCP

RFC Documents

Lost Packet Retransmission

Local Retransmission

Split TCP

Hop-by-Hop TCP

Related Work

ATCP

TCP Muzha

Adaptive CWL (Congestion Window Limit)

The Transport Layer Revisited

Our Approach

Hop-by-Hop TCP

Design Objectives

Design Issues

End-to-End TCP

One-Hop TCP

One-Hop TCP

End-to-End ACK

One-Hop Flow of Receiving Local ACK

One-Hop Flow of Receiving Data Packet

State Transition of One-Hop TCP

One-Hop TCP機制

One-Hop TCP Pseudo code

Overhead Reduction

802.11 MAC Layer 4-Way Handshake

Performance Evaluation

Design of Experiments

Experiment 1: Topology and Parameters

Change of Congestion Window Size

Delay Time at Different Number of Hops

Throughput at different number of hops

Effect of Piggybacking

Evaluation of Retransmission Rate

Summary of Experiment 1

Experiment 2 Fairness Test

Topology and Parameter for Fairness Test

Jain's Fairness Index

Fairness Test 2A

Fairness Test 2B (MANET)

Fairness Test 2B

Summary of Fairness Test

Conclusion

Future

Untitled Document

Outline

♦ Introduction

♦ Related Work

♦ Our Approach

♦ Performance Evaluation

♦ Conclusion

Untitled Document

MANET and Sensor Network

MANET	Sensor Network (A Special MANET)
A group of mobile computing devices that are equipped with WLAN capability.	WSN is a wireless network consisting of spatially distributed autonomous devices using sensors to cooperatively monitor physical or environmental conditions at different locations.

Nodes can transmit packets to each other to construct an Intranet without the assistance of any base station (Access Point). Nodes help each other to forward packets from hop to hop such that two nodes that can't hear each other can transmit data to each other.	Each node is typically equipped with a radio transceiver, a small microcontroller and a battery. Size and cost constraints on sensor nodes result in corresponding constraints on resources such as energy, memory, computational speed and communication bandwidth.

Untitled Document

TCP

How to guarantee data delivery? TCP !! Inefficient !

Untitled Document

TCP

The most popular reliable transport protocol
Located at both ends of a connection
Reliable, in-order
Connection-oriented
With flow controlled

Untitled Document

Flow control & Congestion control

♦ Trial-and-error based flow control for controlling congestion

♦ Sliding window mechanism

adjust window size = adjust data rate

⊕ Slow Start Problem

♦ A mechanism to resolve congestion problem

Untitled Document

Design Objectives of TCP

♦ Guarantee packets delivery

♦ To maximize bandwidth utilization while minimizing network congestion

⊕ However,

MANET/Sensor Network prefers shorter delivery time to high throughput

Untitled Document

RFC Documents

RFC number	Topic
793	Transmission Control Protocol
1323	TCP Extensions for High Performance
2018	TCP Selective Acknowledgement Options
2581	TCP Congestion Control
2914	Congestion Control Principles
3168	The Addition of Explicit Congestion Notification (ECN) to IP
3390	Increasing TCP's Initial Window
3782	The NewReno Modification to TCP's Fast Recovery Algorithm

Untitled Document

Lost Packet Retransmission

♦ Retransmission from sender packets may get lost again and again under high error Take too many retransmission to reach destination -- induce long delay time

Untitled Document

Local Retransmission

MANET/Sensor Network applications prefer fast packet delivery

♦ Hop-by-Hop TCP is to speed up packet delivery

Each intermediate node retransmits lost packets to assure packet delivery
Faster than retransmission from sender

Retransmit from Sender	Retransmit from Local

Untitled Document

Split TCP

Untitled Document

Hop-by-Hop TCP

♦ Intermediate nodes (routers) do not participate in TCP execution.
Conventional TCP is executed on both ends of a connection.

On MANET, each node is a computer, which can participate in the Hop-by-Hop TCP execution.

Untitled Document

Related Work

♦ Utilize info. provided by IP layer to distinguish the packet loss caused by congestion from others

ATCP (Ad Hoc TCP)

TCP Muzha

♦ Utilize intermediate node to assist congestion control

Transport layer revisited

TCP Muzha

Untitled Document

ATCP

♦ 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

Untitled Document

TCP Muzha

♦ Utilize intermediate node to assist congestion control

Intermediate nodes provides status inf. to sender

Sender can adjust data rate before congestion

♦ Identify bottleneck and estimate its residual bandwidth for a better data rate adjustment.

♦ Reduce the occurrence of congestion

♦ Can distinguish the packet loss caused by congestion from random loss

Untitled Document

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

Untitled Document

The Transport Layer Revisited

Heimlicher, Simon Baumann, Rainer May, Martin Plattner, Bernhard, “ The Transport Layer Revisited,” Communication Systems Software and Middleware, 2007. COMSWARE 2007.

♦ The framework is implemented on two sublayers

The hop-by-hop layer runs on every node and provides per-link flow control and congestion control

On this layer, data is managed in units of fragments(8 packets)

The end-to-end layer operates at the end points of the connection, provides a reliable-byte-stream interface to the application-layer, just like TCP

Data is managed as segments, which are data units comprising a few fragments(4 fragments)

♦ The end-to-end congestion control mechanism has a job similar to the congestion control algorithm of TCP: it limits the number of un-acknowledged segments on a per-connection basis.

♦ If no acknowledgement is received for a segment for a certain period, the source needs to retransmit the segment.

♦ If a packet is lost on any intermediate link, the node at the receiving side will not acknowledge the corresponding fragment and the last hop will retransmit the fragment.

Untitled Document

Our Approach

⊕ Hop-by-Hop TCP

♦ Let each intermediate note assure packet delivery by buffering and local retransmission.

Untitled Document

Hop-by-Hop TCP

♦ 2 Components

End-to-End TCP	running on sender and receiver
One-hop TCP	running on each intermediate nodes

Untitled Document

Design Objectives

♦ Reduce packet delivery latency

♦ Reduce number of retransmission

♦ improve throughput

♦ maintain performance when coexist with other TCP versions

Untitled Document

Design Issues

♦ Data rate control: avoid network congestion and best utilize bandwidth

♦ Fairness maintenance

♦ Handling of local and end-to-end packet loss

♦ Handling of local and end-to-end ACK loss

♦ Buffer management

Untitled Document

End-to-End TCP

♦ Running at both ends of a connection to assure successful delivery of packets

♦ Reuse TCP Reno, but

Set an upper bound for CWND (congestion window size)

increase End-to-End RTO to avoid unnecessary Slow Start due to slowness of MANET

Untitled Document

One-Hop TCP

♦ Used between two adjacent nodes to assure local packet delivery

♦ Functionality:

Buffer packet

Local retransmission for lost packets

Untitled Document

One-Hop TCP

⊕ Data Rate

♦ CWND=1 (one packet per ACK)

No need for sliding window

⊕ Retransmission

♦ If One-Hop RTO expired w/o ACK, do the retransmission

♦ Upto Retransmission Threshold avoid useless retransmissions

Route Failure -> need to change route

Network Congestion -> need to reduce CWND (slow start)

Untitled Document

End-to-End ACK

End-to-End ACK：	Same as ACK for conventional TCP
Mechanism to improve survival rate	Use One-Hop TCP in the reverse direction for ACK

Untitled Document

One-Hop Flow of Receiving Local ACK

Untitled Document

One-Hop Flow of Receiving Data Packet

Untitled Document

State Transition of One-Hop TCP

Untitled Document

One-Hop TCP機制

Event	Status	Actions taken in the receiving node	Next state
Receive a packet when flag no_packet_outgoing is false	Ready	Buffer the new packet; if there is any packet to be sent in another direction, piggyback it, if not, return LACK	Ready
Receive a packet and no packet is outgoing	Ready	Buffer the new packet; if there is any packet to be sent in another direction, piggyback it, if not, return LACK, send the packet, and start timer	Wait
Local Timeout and retry count < 6	Wait	Retransmit the Timeout packet; restart timer	Wait
Local Timeout and retry count > 5	Wait	Purge the packet that retransmits over five times from buffer; stop timer	Done
Receive a LACK from downstream node	Wait	Purge the packet from buffer; stop timer	Done
Other Packet in Buffer	Done	Send the next packet from buffer; start timer	Wait
Buffer empty	Done	Set flag no_packet_outgoing to true; wait the next packet	Ready

Untitled Document

One-Hop TCP Pseudo code

Receive ( Packet ){
  if ( Data )
  {
     ReturtLACK ( ) ;
     if ( NewPacket_ == True )
{ BufferPacket ( ) ; }
     if ( isdataoutgoing_ == False )
       {
SendPacket ( ) ;
Isdataoutgoing == True;
}
  }
  if ( LACK )
  {
     PurgeBuffer ( ) ;
     if ( Buffer == NULL )
       { set isdataoutgoing == False ; }
     else
       { SendPacketInBuffer ( ) ; }
  }
}

Untitled Document

Overhead Reduction

Piggyback packets in the same direction to reduce overhead

Forward dats stream	Data Local ACK for E2E ACK
Backward dats stream	End-to-End ACK Local ACK

Untitled Document

802.11 MAC Layer 4-Way Handshake

Untitled Document

Performance Evaluation

♦ Evaluation by NS-2 Simulator

⊕ Evaluation Metrics

♦ Average Delay Time

♦ Average Throughput

♦ Retransmission

♦ Change of CWND

♦ Fairness Index

Untitled Document

Design of Experiments

⊕ Performance Test

Control Variables	hop count	error rate	buffer size

⊕ Fairness Test

♦ Fairness when multiple TCP coexist

HbH and Reno Coexist
Many HbH Coexist

Untitled Document

Experiment 1: Topology and Parameters

Parameter	Range
Packet Size	1000 bytes (MANET) 50 bytes (Sensor)
Buffer Size	50 packets (MANET) 10 packets (Sensor)
CWND Upper Bound	4
Link Bandwidth	0.5~1 Mbps (MANET) 5~10 Kbps (Sensor)
Error Rate	0.0~0.2 (MANET) 0.0-0.5 (Sensor)
Number of Nodes	5~11
MAC Protocol	802.11
Routing Algorithm	DSR

Untitled Document

Change of Congestion Window Size

( Sensor Netowrk/error rate = 0.4)
\|

( MANET/error rate = 0.0)	( MANET/error rate = 0.1)

Untitled Document

Delay Time at Different Number of Hops

SensorNet/error rate = 0.4	MANET/error rate = 0.1

MANET/error rate = 0.1	MANET/error rate = 0.2

♦ When lost rate is high, HbH TCP can reduce delay time by 20%

Untitled Document

Throughput at different number of hops

SensorNet/error rate = 0.4	MANET/error rate = 0.1

MANET/error rate = 0.1	MANET/error rate = 0.2

♦ When lost rate is high, HbH TCP can improve throughput by 25%

Untitled Document

Effect of Piggybacking

Untitled Document

Evaluation of Retransmission Rate

SensorNet/error rate = 0.4

MANET/error rate = 0.1	MANET/error rate = 0.2

Untitled Document

Summary of Experiment 1

♦ When lost rate is high, Compared with NewReno, HbH TCP can

reduce delay time by 20%

improve throughput by 25%

♦ HbH can stablize CWND when lost rate is high

Untitled Document

Experiment 2 Fairness Test

Different versions of TCP may compete for bandwidth, pessimal TCP (Vegas) may get hungry when coexist with aggressive TCP (NewReno)

Test 2A	Fairness Test for multiple versions of TCP
Test 2B	Fairness Test for multiple flows of same TCP

Untitled Document

Topology and Parameter for Fairness Test

Topology	Parameter	Range

	Packet Size	1000 bytes (MANET) 50 bytes (Sensor)
	Buffer Size	50 packets (MANET) 10 packets (Sensor)
	Link Bandwidth	0.5~1 Mbps (MANET) 5~10 Kbps (Sensor)
	Error Rate	0.1 (MANET) 0.4 (Sensor)
	Link Bandwidth	1 Mbps (MANET) 10 Kbps (Sensor)
	Number of hops	4, 6, 8
	MAC Protocol	802.11
	Routing Algorithms	DSR

Untitled Document

Jain's Fairness Index

x _i is the flow throughput of flow i
equal partitioning of bandwidth achieves index of 1
If only k of n flows receive equation bandwidth (and others get non) index is k/n

Untitled Document

Fairness Test 2A

NewReno vs. Vegas (MANET/Throughput)	NewReno vs. Hop-by-Hop TCP (MANET/Throughput)

Jain's Fairness Index (MANET)	Jain's Fairness Index (SensorNet)

Untitled Document

Fairness Test 2B (MANET)

Protocol	Throughout Dynamics	Jain's Index Dynamics
HbH TCP
TCP Vegas
TCP NewReno

Untitled Document

Fairness Test 2B

MANET	Sensor Network

Untitled Document

Summary of Fairness Test

♦ HbH TCP inherents Congestion Control of NewReno

Can coexist with NewReno w/o performance degradation

♦ Fair bandwidth sharing when multiple flows of HbH coexist

Untitled Document

Conclusion

♦ Each intermediate node use local retransmission to guarantee packet delivery in each link

outperform NewReno in delay time and throughput

♦ When lost rate is high, Compared with NewReno, HbH TCP can

reduce delay time by 20%

improve throughput by 25%

♦ Maintain Good Fairness

Untitled Document

Future

♦ Introduction

♦ Related Work

♦ Our Approach

♦ Performance Evaluation

♦ Conclusion

♦ Trial-and-error based flow control for controlling congestion

♦ Sliding window mechanism

adjust window size = adjust data rate

⊕ Slow Start Problem

♦ A mechanism to resolve congestion problem

♦ Guarantee packets delivery

♦ To maximize bandwidth utilization while minimizing network congestion

⊕ However,

MANET/Sensor Network prefers shorter delivery time to high throughput

♦ Retransmission from sender

packets may get lost again and again under high error

Take too many retransmission to reach destination -- induce long delay time

MANET/Sensor Network applications prefer fast packet delivery

♦ Hop-by-Hop TCP is to speed up packet delivery Each intermediate node retransmits lost packets to assure packet delivery Faster than retransmission from sender

♦ Intermediate nodes (routers) do not participate in TCP execution. Conventional TCP is executed on both ends of a connection.

On MANET, each node is a computer, which can participate in the Hop-by-Hop TCP execution.

♦ Utilize info. provided by IP layer to distinguish the packet loss caused by congestion from others

ATCP (Ad Hoc TCP)

TCP Muzha

♦ Utilize intermediate node to assist congestion control

Transport layer revisited

TCP Muzha

♦ 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:

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

♦ Utilize intermediate node to assist congestion control

Intermediate nodes provides status inf. to sender

Sender can adjust data rate before congestion

♦ Identify bottleneck and estimate its residual bandwidth for a better data rate adjustment.

♦ Reduce the occurrence of congestion

♦ Can distinguish the packet loss caused by congestion from random loss

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

Heimlicher, Simon Baumann, Rainer May, Martin Plattner, Bernhard, “ The Transport Layer Revisited,” Communication Systems Software and Middleware, 2007. COMSWARE 2007.

♦ The framework is implemented on two sublayers

The hop-by-hop layer runs on every node and provides per-link flow control and congestion control

On this layer, data is managed in units of fragments(8 packets)

The end-to-end layer operates at the end points of the connection, provides a reliable-byte-stream interface to the application-layer, just like TCP

Data is managed as segments, which are data units comprising a few fragments(4 fragments)

♦ The end-to-end congestion control mechanism has a job similar to the congestion control algorithm of TCP: it limits the number of un-acknowledged segments on a per-connection basis.

♦ If no acknowledgement is received for a segment for a certain period, the source needs to retransmit the segment.

♦ If a packet is lost on any intermediate link, the node at the receiving side will not acknowledge the corresponding fragment and the last hop will retransmit the fragment.

⊕ Hop-by-Hop TCP

♦ Let each intermediate note assure packet delivery by buffering and local retransmission.

♦ 2 Components

♦ Reduce packet delivery latency

♦ Reduce number of retransmission

♦ improve throughput

♦ maintain performance when coexist with other TCP versions

♦ Data rate control: avoid network congestion and best utilize bandwidth

♦ Fairness maintenance

♦ Handling of local and end-to-end packet loss

♦ Handling of local and end-to-end ACK loss

♦ Buffer management

♦ Running at both ends of a connection to assure successful delivery of packets

♦ Reuse TCP Reno, but

Set an upper bound for CWND (congestion window size)

increase End-to-End RTO to avoid unnecessary Slow Start due to slowness of MANET

♦ Used between two adjacent nodes to assure local packet delivery

♦ Functionality:

Buffer packet

Local retransmission for lost packets

⊕ Data Rate

♦ CWND=1 (one packet per ACK)

No need for sliding window

⊕ Retransmission

♦ If One-Hop RTO expired w/o ACK, do the retransmission

♦ Upto Retransmission Threshold avoid useless retransmissions

♦ Hop-by-Hop TCP is to speed up packet delivery

Each intermediate node retransmits lost packets to assure packet delivery
Faster than retransmission from sender

♦ Intermediate nodes (routers) do not participate in TCP execution.
Conventional TCP is executed on both ends of a connection.