Transcript ppt - UCL Computer Science

EPDN: Explicit Packet Drop Notification
and its uses
By
Arjuna Sathiaseelan
Tomasz Radzik
Department of Computer Science
King’s College London
Motivation

Reordering or Corruption of packets leads to overestimation of the
congestion of the network.

Decreases the TCP performance of a network

Imperative to propose a mechanism that allows the TCP sender to
know the exact cause of the out of order data
Problem of Packet Reordering


Packet reordering is common : due to parallelism in networks.
Parallelism reduces cost of equipments and trunks.
Types of Parallelism:
 Local parallelism : Multiple paths within a device.
 Multi-path routing.
Effects of Parallelism:
 Decreases the TCP performance of the network.
Detecting packet loss

Retransmission Timer

Fast Retransmit
Implications of Reordering

Unnecessary retransmission of data segments means that some of
the bandwidth is wasted.

Unnecessary reduction of the congestion window.

TCP ensures that the receiving application receives data in order.
Burden on the TCP receiver since the receiver must buffer the outof-order data until the missing data arrive to fill the gaps.
Impact of Reordering
Related Work

[Floyd, Mahdavi, Mathis, Podolsky; 2000]: DSACK option allows the
TCP receiver to report to the sender when duplicate segments arrive at the
receiver. Using this information, the sender can determine when a retransmission
is spurious. If spurious, the cwnd can be restored to the previous value.

RR-TCP [Zhang, Karp, Floyd, Peterson; 2003]: RR-TCP:
mechanisms to detect and recover from false retransmits using the DSACK
information. They propose several algorithms for proactively avoiding false
retransmits by adaptively varying DUPTHRESH.
EPDN: Explicit Packet Drop Notification

Each gateway has a hashtable storing entries:
<i, max:PNO, min:PNO>

i is the flow id (also the key used to index the hashtable).

max:PNO is the maximum sequence number of the packet dropped in the
gateway.

min:PNO is the minimum sequence number of the packet dropped in the gateway.
Packet Drop
P2
P3
P4
P4 P1
3,2
Received Packets
Hash Table
P1 P4
Flow Id: 1
Min: P2
Max: P3
P2
Droplist: 2 3
Reorderedlist:
Packet Reorder
P1
P3
P2
P3
Received Packets
Hash Table
Flow Id:
Min:
Max:
P1 P3
Droplist:
Reorderedlist: P2
RN-TCP: Reorder Notifying TCP

Receiver uses the following information to identify whether a packet has been
dropped or reordered.
Packet Notation: P<fid,n,max,min>

P:n - Sequence number of the current received packet

P:max - Maximum dropped entry

P:min - Minimum dropped entry

Q:n - Last received packet in the receiver buffer queue
RN-TCP: Reorder Notifying TCP (contd.)

Receiver maintains two lists:
- Reorder List
- Drop List

Drop is notified by not setting ‘drop-negative’ bit in the ACK.

Reorder is notified by setting ‘drop-negative’ bit in the ACK.
Storage and Computational Costs






The IP options field has 40 bytes.
We use 4 bytes for each minimum and maximum dropped entries to be inserted
into the option field of the IP segment.
We use one bit from the reserved bits in TCP to denote the ‘drop-negative' bit.
Our monitoring process records only flows whose packets
have been dropped.
When the dropped information is inserted into the corresponding packet that
leaves the gateway successfully, the entry is deleted.
Rough estimate: 500KB SRAM would be sufficient for storing infoirmation
about dropped packets ?
Storage and Computational Costs(contd..)

For each packet, the computational cost in each gateway is constant, assuming a
constant time access/update of the hashtable.

Computational costs at the receiver are as follows:
- Insertion O(n) where n is the number of packets the
assumed to be dropped or reordered.
- Deletion and comparison costs O(m) where m is the
length of the list.

receiver has
Computational cost O(log n) and O(log m) respectively if we use balanced trees.
Simulation Details

Used Network Simulator ns-2.

Segment size : 1500 bytes.

Conducted experiments for Drop-tail.

Queue size used : 65 segments.

Used FTP traffic flows.
Throughput – Packet Delays
(Delays: Normally distributed with mean = 25ms, std.dev = 8ms)
Throughput – Multipath Routing
(Delays: Modal Distribution)
Link Utilization
(30% Packets Delayed)
Throughput: Delays and Drops
(5% Packets Delayed)
TCP-R : Robust TCP

RN-TCP: proposed for terrestrial networks.

Terrestrial networks:
- the out of order packets are caused mainly due to losses related to
reordering of packets.
- Losses due to corruption is negligible.
congestion and

Satellite links have high RTTs, typically on the order of several
hundred milliseconds.

Losses mainly due to corruption than congestion.

If a packet had been actually dropped due to corruption, having an increased value of dupthresh
requires a RTO to detect the packet loss.

Imperative to propose a mechanism that improves the performance when packets get corrupted,
reordered and dropped for networks with large RTT.
TCP-R : Robust TCP

TCP-R uses EPDN.

The TCP-R receiver informs the TCP-R sender about its assumption.

If the packets had been dropped in the network, the lost packets are retransmitted after
waiting for 3 DUPACKS (fast retransmit) and reduces the congestion window by half
(fast recovery).

If the packets are assumed to be reordered or corrupted in the network, - TCP-R sender
retransmits the packet after receiving three
DUPACKS
Enters our modified fast recovery mechanism where the
procedure of
reducing the slow start threshold (ssthresh) and the congestion window (cwnd) are
bypassed.
Simulations



Segment size : 1000 bytes
Queue size used : 100 segments.
Used FTP traffic flows.
Throughput – Packet Delays
(Delays: Normally distributed with mean = 200ms, std.dev = 80ms)
Throughput: Delays and Corruption
(5% Packets Delayed)
AND
Timeout Avoidance
Throughput – Delays and Drops
(3% Packets Delayed)
Future Work

Scalability of EPDN in wired networks – is it possible just to use EPDN in hot spots
where packets get dropped?

In case the routing changes and if the dropped information cannot
be propagated to the receiver - send the dropped information in an ICMP message to the
sender ?

Use the RED packet drop history for EPDN?

Verify the size requirements needed for EPDN?