Int. J. Communications, Network and System Sciences, 2009, 7, 675-686
doi:10.4236/ijcns.2009.27078 Published Online September 2009 (http://www.SciRP.org/journal/ijcns/).
675
TCP-R with EPDN: Handling out of Order Packets
in Error Prone Satellite Networks
Arjuna SATHIASEELAN
Electronics Research Group, University of Aberdeen, Aberdeen, United Kingdom
Received May 28, 200 9; revised July 8, 2009; accepted September 10, 20 09
ABSTRACT
Studies have shown that packet reordering is common, especially in satellite networks where there are link
level retransmissions and multipath routing. Moreover, traditional satellite networks exhibit high corruption
rates causing packet losses. Reordering and corruption of packets decrease the TCP performance of a net-
work, mainly because it leads to overestimation of the congestion in the network. We consider satellite net-
works and analyze the performance of such networks when reordering and corruption of packets occurs. We
propose a solution that could significantly improve the performance of the network when reordering and
corruption of packets occur in a satellite network. We report results of our simulation experiments, which
support this claim.
Keywords: TCP, Packet, Reorder, Throughput, Drops, Congestion, Multipath, Satellite
1. Introduction
Transmission Control Protocol (TCP) is the commonly
used transport protocol in the Internet. The TCP protocol
provides a reliable, connection oriented, in-order deliv-
ery of data between any two hosts in the Internet [1]. To
ensure the data is delivered from the sender to receiver
correctly and in-order, the TCP sender uses sequence
numbers to each octet of data that is transmitted and the
TCP receiver acknowledgements (ACKs) the receipt of
these transmitted bytes that are received correctly and
in-order. Since ACKs are cumulative, the receipt of
out-of-order packets generates duplicate ACKs that are
sent to the TCP sender. TCP assumes congestion in the
network to be the cause of loss of packets. Thus when a
TCP sender receives three successive duplicate ACKs, it
assumes a packet has been lost and that this loss is an
indication of network cong estion and reduces its sending
rate [2].
Networking using satellites began by using individual
satellites in Geostationary Earth Orbit (GEO), where the
signals were amplified and then up-linked to the GEO
satellite. The satellite then frequency-shifts the signal
and broadcasts it down to a large ground area. These
GEO satellites acted as simple transparent ‘bent-pipe’
repeaters [3]. A Lower Earth Orbit (LEO) network such
as Iridium [4] has several satellites connected together to
form a network. When there is congestion in a particular
path, the satellite routes the packets through a different
path. This introduces reordering of packets [5]. Satellite
networks such as GEO and LEO have high round trip
times (RTTs), typically in the order of several hundred
milliseconds. In order to keep the pipe full, link-layer
retransmission protocols send subsequent packets while
awaiting an ACK or negative acknowledgement (NAK)
for a previously sent packet. Here, a link-layer retrans-
mission is reordered by the number of packets that were
sent between the orig inal transmission of that packet an d
the return of the ACK or NAK [6].
In satellite networks, the packet loss is mainly due to
corruption. These corrupted packets could be dropped
either in the routers (in case of LEO network) or in the
receiver when the header checksum fails. If the link layer
at the receiver detects any errors and if there is enough
redundancy transmitted in the code, then the errors can
be corrected using the Forward Error Correction (FEC)
algorithms without requesting for a retransmission.
Therefore, the link layer could pass the error free packet
to the top layers. If the link layer detects an error but
cannot correct it (i.e. the cyclic redundancy check (CRC)
fails, the link layer drops the corrupted packet and the
link layer at the receiver requests the link layer at the
sender to retransmit the packet. These link level retrans-
missions only make a limited attempt to recover the lost
packet. If the link layer cannot recover the lost packet, it
will be left to the higher layers to recover the packet.

A. SATHIASEELAN 676
Thus when packets are lost due to corruption, link layer
protocols that do not attempt in-order delivery across the
link cause packets to reach the TCP receiver in out-of-
order. This leads to the generation of duplicate ACKs by
the TCP receiver, which causes the sender to invoke fast
retransmission and recovery [7].
There have been many proposals for extending TCP to
improve the performance when the losses are mainly due
to corruption. Some of the proposed mechanisms are the
Explicit Loss Notification (ELN) mechanism [8], Ex-
plicit Transport Error Notification (ETEN) [9], Indi-
rect-TCP (I-TCP) [10], TCP PEACH [11] etc. These
proposals improve the performance of TCP when packets
get lost due to corruption in the network but do not con-
sider the effects caused due to reordering of packets.
Several methods to detect the needless retransmission
due to the reordering of packets have also been proposed:
The DSACK (Duplicate Selective Acknowledgement)
option in TCP, allows the TCP receiver to report to the
sender when duplicate segments arrive at the receiver’s
end. Using this information, the sender can determine
whether a retransmission was spurious [12]. If the re-
transmission was spurious, then the slow start threshold
(ssthresh) is set to the previous congestion window
(cwnd). Their proposal does not specify any mechanisms
to proactively detect reordering of packets. We term this
mechanism as DSACK-R (DSACK with Recovery).
In [13], the authors propose mechanisms to detect and
recover from false retransmits using the DSACK infor-
mation. They propose several algorithms for proactively
avoiding false retransmits by adaptively varying the du-
plicate threshold (dupthresh) value. The DSACK-FA
algorithm (DSACK-R + fixed FA ratio), the dupthresh
value is chosen to avoid a percentage of false fast re-
transmits, by setting the dupthresh value equal to the
percentile value in the reordering length cumulative dis-
tribution. The percentage of reordering the algorithm
avoids is known as FA ratio algorithm. In the DSACK-
FAES algorithm (DSACK-FA + Enhanced RTT sam-
pling), the DSACK-FA algorithm is combined with a
RTT sampling algorithm which samples the RTT of re-
transmitted packets caused by packet delays. The
DSACK-TA algorithm (DSACK-FA + Timeout Avoid-
ance) uses cost functions that heuristically increase or
decrease the FA ratio such that the throughput is maxi-
mized for a connection experiencing reordering. The FA
ratio will increase when false retransmits occur and the
FA ratio will decrease when there are significant time-
outs. In the DSACK-TAES algorithm (DSACK-TA +
Enhanced RTT sampling), the DSACK-TA algorithm is
combined with a RTT sampling algorithm which samples
the RTT of retransmitted packets caused by packet de-
lays. According to [19], the DSACK-TA algorithm per-
formed the best when compared with the other algo-
rithms for various delay distributions. DSACK-TAES
performed better than DSACK-TA for large packet de-
lays that exceeded the one second minimum RTO. For
other delay distributions, both DSACK-TA and DSACK-
TAES perform similarly.
In [14], we proposed a novel method to enable the
TCP senders to distinguish whether a packet has been
dropped or reordered in the network by using the gate-
ways to inform the ‘receiver’ about the dropped packets.
This mechanism was called the Explicit Packet Drop
Notification version 2.0 (EPDNv2). The receiver then
uses this information to inform the sender about which
packets have been reordered by setting a drop-negative
bit. If the packets had been dropped in the network, the
TCP sender retransmits the lost packets after waiting for
three duplicate ACKs. If the packets are assumed to be
reordered in the network, the TCP sender waits for ‘3+k’
duplicate ACKs (k,1) before retransmitting the packets.
We termed this new version of TCP as Reorder Notify-
ing TCP (RN-TCP). Although using EPDNv2 requires
modifications to all routers along the path, when com-
bined with RN-TCP it gave good performance improve-
ments. The computational and storage costs, and other
implementation issues were analyzed in detail in [14].
The proposals mentioned to alleviate the TCP per-
formance in the presence of packet reordering do not
consider error prone networks. It would be interesting to
find out the performance of these protocols when reor-
dering happens in a network that is error prone. If a
packet had been actually dropped due to corruption,
having an increased value of dupthresh may require a
timeout to detect the packet loss. Thus increasing the
dupthresh value to more than three when a packet has
been assumed not to be dropped may have serious im-
plications in the performance, if the packet had actually
been dropped due to corruption. The EPDNv2 mecha-
nism proposed by us in [14], informs the sender/receiver
about dropped packets. This could be dropped due to
congestion in the network or due to corruption in the
network. RN-TCP retransmits the lost packet and re-
duces the transmission rate even if the packets had been
dropped due to corruption. If a packet had actually been
lost due to corruption, the performance of TCP can be
improved, if the TCP sender does not reduce the cwnd
upon a retransmission of the lost packet. Moreover, when
networks exhibit high RTT, unnecessary reduction of the
cwnd requires large number of RTTs to retrieve back to
the previous cwnd. This reduces the throughput per-
formance. Thus, it was imperative for us to propose a
new TCP protocol, that can improve the throughput per-
formance when packets experience reordering and cor-
ruption.
In this paper, we propose extending the SACK proto-
col to enable TCP senders to recognize whether a re-
ceived duplicate ACK means that a packet has been
dropped or corrupted/reordered. The extended protocol
also requires a modification to EPDNv2. We call the
modified mechanism as Explicit Packet Drop Notifica-

A. SATHIASEELAN 677
tion Version 3.0 (EPDNv3) mechanism to infer which
packets have been dropped due to congestion. The TCP
sender uses this information to take an appropriate action.
We term this new TCP protocols as Robust TCP
(TCP-R).
The remainder of this paper is organized as follows.
Section 2 presen ts the details of our prop osed solution. In
Section 3 discusses the simulation environment. Section
4 discusses the simulation results. We conclude the paper
with a summary o f our work and a short discussion of the
further research in Section 5.
2. Implementation Details
2.1. EPDNv3
We propose a mechanism similar to EPDNv2 (proposed
by us in [14]), by maintain ing information about packets
dropped due to congestion in the gateways and not by
header checksum error which occurs mainly due to cor-
ruption1. Corrupted packets dropped by the MAC layer
are not maintained. Each gateway maintains information
about dropped packets in the gateways. This is by having
a hashtable that maintains for each flow the maximum
sequence number and minimum sequence number of the
packets that get dropped due to congestion in the gate-
way. When the next data packet of flow i passes through
that gateway, the gateway inserts the maximum sequence
number and the minimum sequence number of the
dropped packets in the data packet and the entry is de-
leted from the data structure. We term this mechanism of
explicitly informing the receiver about the dropped in-
formation as Explicit Packet Drop Notification Version
3.0 (EPDNv3.0)2.
2.2. TCP-R: Robust TCP
We propose extending the TCP SACK protocol to enable
TCP senders to recognize whether a received duplicate
ACK means that a packet has been dropped or cor-
rupted/reordered in the network. The extended protocol
uses the EPDNv3.0 mechan ism mentioned abov e to infer
which packets have been dropped. The TCP-R receiver
maintains two lists: the reorder/corruption list and the
drop list. The TCP-R receiver uses the algorithm men-
tioned in [14] to determine which packets have been
dropped due to congestion and which have been reor-
dered or corrupted, and puts those sequence numbers into
the corresponding lists3. Informing the sender is done by
setting the drop-negative bit in corresponding duplicate
ACKs if the packet has been assumed to be reordered or
corrupted4. If the packets are assumed to be reordered or
corrupted in the network, the TCP-R sender retransmits
the packet after receiving three duplicate ACKs with the
drop-negative bit set and enters our modified fast recov-
ery mechanism where the procedure of reducing the
ssthresh and the cwnd are bypassed i.e. we do not reduce
the ssthresh and the cwnd. In order to prevent TCP-R
from falsely misjudging drops due to congestion and not
reducing the sending rate, we ensure the modified fast
recovery mechanism is executed only in the absence of
ECN messages. If the packets had been dropped in the
network, the TCP-R sender retransmits the lost packet
after waiting for three duplicate ACKs (fast retransmit)
and reduces the cwnd by half (fast recovery)5.
In an environment where out-of-order packets can
happen due to corruption and reordering, the throughput
performance can be improved if we do not reduce the
cwnd upon the occurrence of a reordering or a corrup tion
event. Even though TCP-R unnecessarily retransmits a
reordered packet, it reduces the instances of timeouts by
not delaying the retransmission of corrupted packets.
Moreover it does not reduce the cwnd unnecessarily, thus
improving the thro ughput of the sender.
2.2.1. Sender Sid e: Impl ementation Details
When an ACK is received the TCP sender does the fol-
lowing,
 If none of the three duplicate ACKs received have
their drop-negative bit set, then the sender assumes
that the packet has been dropped. So the sender re-
transmits the lost packet after receiving three dupli-
cate ACKs and enters fast recovery.
 If all the three duplicate ACKs received have their
drop-negative bit set and the ECE bit is set to zero
(i.e no ECN information has been received off
lately), then the sender assumes that the packet has
been reordered or corrupted in the network and re-
transmits the packet immediately. The procedure of
reducing th e ssthresh and the cwnd in the fast recov-
ery procedure are bypassed. In order to avoid multi-
ple retransmits, we ensure that a packet assumed to
be reordered or corrupted would be retransmitted
only once in a RTT.
1EPDNv2 maintains information about drops caused by both corrupted
and congested packets. The implementation details are similar to
EPDNv2.
2The implementation details are similar to EPDNv2. The implementa-
tion issues and costs have bee n th o roughly analyzed in [14].
3TCP-R uses the reorder list specified in [14] to store out-of-order
p
acket sequence numbers caused by losses due to corruption and reor-
dering. We denote the list as reor-der/corr uption list.
4The drop-negative bit is set to 1.
5The drop-negative bit is set to 0.
3. Simulation Environment
Figure 1 presents the topology used for our simulations.
The simulated net w or k has a source and destinat i on no de

A. SATHIASEELAN 678
Figure 1. TCP-R: Simulated network.
connected to two intermediate routers. The nodes are
connected to the routers via 10 Mbps Ethernet having a
delay of 1 ms. The routers are connected to each other
via long delay link with a fixed link capacity (set to 1.5
Mbps) and variable delay. Our simulations use 1500 byte
packets. We used the RED queuing strategy with a queue
size set to the bandwidth delay product. All routers were
ECN enabled. Reordering and packet drops are intro-
duced at the bottleneck link (R1,R2). The experiments
were conducted using a single long lived FTP flow trav-
ersing the network topology, except otherwise noted. The
maximum window size of the TCP flow was also set to
the bandwidth delay product. The TCP flow lasts 1000
seconds.
Our simulations consider the case of both LEO and
GEO satellite links. The lack of flexibility of the current
ns-2 simulator to delay a fraction of packets and to test
for various average packet delays for satellite links
caused us to model the satellite links by representing a
wired link with the same capacity and delay as a GEO or
a LEO satellite link, similar to [15]. The GEO satellite
link has roughly a delay of 300 ms (one way). The LEO
satellite link has a one way delay that varies [40,400] ms
depending on whether the LEO n etwork has one satellite
hop or multiple hops and how far each of these satellite
hops are placed [15]. In GEO networks, we consider the
reordering to be caused only due to link level retransmis-
sions and in LEO networks we consider the case of link
level retransmissions and multipath routing. Reordering
is caused when a delayed packet with a higher sequence
number is scheduled to traverse the link later than an
un-delayed packet with a lower sequence number. To
simulate packet reordering, we delay a percentage of
packets traversing the link by delay distributions. Our
experiments can be classified into the following scenar-
ios.
1) Scenario 1: The link layer at the receiver could de-
tect and correct some of the corrupted packets using link
level retransmissions. Those packets that cannot be re-
covered at the link layer will not arrive at the TCP, caus-
ing out-of-order packets. In addition to this, some cor-
rupted packets may have been dropped by the satellite
nodes (incase of LEO networks). Due to retransmission
at the link layer, some of the packets could have been
reordered. Thus the TCP receiver will receive out-of-
order packets caused by both reordering and corruption.
In order to simulate packet loss due to corruption, the
experiments were performed for a BER of 106.
2) Scenario 2: The link layer at the receiver could de-
tect and correct all corrupted packets using link level
retransmissions, but these link level retransmissions
could cause reordering. In this scenario, we assume all
packets are correctly retrieved in the link layer after re-
transmissions. In addition to this, we also assume that the
intermediate satellite nodes do not drop any corrupted
packets. In order to simulate no loss of packets, we set
the BER to zero. Thus the TCP receiver will receive
out-of-order packets caused by reordering only.
3) Scenario 3: Reordering of packets caused due to
multipath routing (in LEO networks) and some packets
getting dropped due to corruption. Thus the TCP receiver
will receive out-of-order packets caused by reordering
and corruption. In order to simulate packet loss due to
corruption, the experiments were performed for a BER of
106.
4) Scenario 4: Reordering of packets caused due to
multipath routing (in LEO networks) and no packets get-
ting dropped due to corruption. In order to simulate no
loss of packets, we set the BER to zero. Thus the TCP
receiver will receive out-of-order packets caused by re-
ordering.
We compare TCP-R with RN-TCP(EPDNv2) i.e.
when RN-TCP operates with EPDNv2, RN-TCP (EPDN-
v3) i.e. when RN-TCP operates with EPDNv3, DSACK-
TA, DSACK-R and SACK.
4. Results
4.1. Reordering due to Link Level
Retransmissions
In this section, we consider the case when packets get
reordered due to link level retransmissions in GEO and
LEO networks. The propagation delay was set to 300 ms.
To introduce severe packet delays in the order of multi-
ple of RTTs, we used a mean packet delay of yP s (P is
the propagation delay) and standard deviation of y/3 P
s, such that the delay introduced varied from 0 to 2yP s.
The packet delay rate was fixed at 4%. We varied the
value of y from 1.0 to 6.0.
4.1.1. Thro ughput: La rge Reordering Delays (Scenario 1)
In this section, we compare the throughput performance
of TCP-R, RN-TCP(EPDNv2), RN-TCP(EPDNv3), DS-
ACK-TA, DSACK-R and SACK when the packets ex-
perience reordering and losses due to corruption. In order
to simulate packet losses due to corruption, we set the
BER to 106. Figure 2 presents the results of the simula-
tions. As we increase y, the RTT of the packet that gets
delayed exceeds the one second minimum RTO causing
large number of timeouts. TCP-R outperforms RN-TCP
(EPDNv2), RN-TCP(EPDNv3), DSACK-TA, DSACK-
R and SACK for all tested mean packet delays from 0.3 s
to 1.8 s. For example, when the average packet delay is
0.9 s, TCP-R gives a three fold throughput improvement

A. SATHIASEELAN 679
Figure 2. GEO link: Propagation delay of 300 ms, BER of
10.
over the other protocols. When the average packet delay
is 1.8 s (3 x RTT), TCP-R gives more than a two fold
throughput improvement over the other protocols.
When packets get dropped in the gateways due to
header checksum error caused by corruption, EPDNv2
informs the sender about the dropped information.
RN-TCP(EPDNv2) on receipt of this information, re-
transmits the corrupted packet immediately and reduces
the cwnd after receiving three duplicate ACKs. Thus
RN-TCP(EPDNv2) encounters more fast retransmissions
than RN-TCP(EPDNv3) but lesser incidence of timeouts
compared to RN-TCP(EPDNv3) and DSACK-TA. On
the other hand, EPDNv3 informs the sender only about
packets dropped due to congestion. Thus RN-TCP
(EPDNv3) would assume the packet to be reordered and
delays the fast retransmission procedure. This could
cause the timer to expire leading to timeouts. Unlike RN-
TCP and DSACK-TA, TCP-R on detecting the packet
has not been dropped due to congestion in the network,
retransmits the packet after receiving three duplicate
ACKs without reducing the cwnd. This reduces the inci-
dence of timeouts and unnecessary reduction of the cwnd
due to fast retransmissions, leading to an improved
throughput performance.
4.1.2. Throughput: Large Reordering Delays
(Scenario 2).
Figure 3 presents the results of the simulations when
packets just experience reordering and no loss of packets
due to corruption. RN-TCP(EPDNv2) and RN-TCP
(EPDNv3) perform similarly as both EPDN versions
store only packets that get dropped due to congestion as
there are no drops due to corruption. Initially, TCP-R
performs slightly less compared to RN-TCP and
DSACK-TA for average packet delays of 0.3 s and 0.45
s. From further investigation, as TCP-R sends more
packets compared to RN-TCP and DSACK-TA (TCP-R
does not prevent retransmission of corrupted or reordered
packets), the ECN enabled routers mark the packets of
the TCP-R flow by setting the CE bit. This causes
TCP-R to reduce the cwnd more often. When th e av er age
packet delay is more than 0.6 s, TCP-R performs better
than the other protocols. For example, when the average
packet delay is set to 0.9 s, TCP-R gives a 4% through-
put improvement over RN-TCP, 9% improvement over
DSACK-TA, four times more than DSACK-R and six
times more than SACK. Similarly when the average
packet delay is set to 1.8 s, TCP-R gives a two fold
throughput performance over RN-TCP, 80% improve-
ment over DSACK-TA, three times more than DSACK-
R and SACK. Moreover DSACK-TA undergoes large
number of cwnd reductions due to fast retransmissions
and has a higher timeout ratio compared to RN-TCP and
TCP-R. TCP-R has almost zero fast retransmit and
timeout ratios.
4.2. Reordering Due to Multipath Routing
In this section, we consider the case when packets get
reordered due to multipath routing in LEO network s. The
propagation delay was set to 400 ms. Multipath routing
produces modal delays i.e. when successive packets are
sent on paths with different RTTs, these packets would
be reordered proportionally to the RTT difference of the
pa th. 50% of the data packets were delayed. We performed

A. SATHIASEELAN 680
Figure 3. GEO link: Propagation delay of 300 ms.
experiments by gradually increasing the average packet
delay from 0.0 s to 0.8 s (2 x RTT). When the average
packet delay is 0.0 s, the packets are routed through the
same path without the packets are routed through the
same path without any reordering events.
4.2.1. Throughput: Multipath Routing (Scenario 3).
In this section, we compare the throughput performance
of the simulated network using SACK, DSACK-R,
DSACK-TA, RN-TCP and TCP-R when packets experi-
ence losses due to corruption and reordering. The ex-
periments were performed for a BER of 106.
Figure 4 presents the results of the simulations when
the propagation delay was set to 400 ms. For all tested
average packet delays, TCP-R outperforms the other
protocols. For example, when the average packet delay is
0.4 s, TCP-R performs four times more than RN-TCP
(EPDNv2), five times more than DSACK-TA and RN-
Figure 4. LEO link: Multipath performance, propagation
delay of 400 ms, BER of 106.

A. SATHIASEELAN 681
TCP(EPDNv3), six times more than DSACK-R and al-
most seven times more than SACK. Similarly, when the
average packet delay is 0.8 s, TCP-R performs four times
more than RN-TCP(EPDNv2), RN-TCP(EPDNv3),
DSACK-TA, six times more than DSACK-R and almost
seven times more than SACK. RN-TCP(EPDNv2) en-
counters fewer timeouts compared to RN-TCP(EPDNv3)
and DSACK-TA. TCP-R maintains a low incidence of
timeouts and maintains a zero fast retransmit ratio com-
pared to the other protocols, thus giving a better through-
put performance.
4.2.2. Throughput: Multipath Routing (Scenario 4).
In this section, we compare the throughput performance
of the simulated network using SACK, DSACK-R,
DSACK-TA, RN-TCP and TCP-R when packets experi-
ence reordering due to multipath routing and no drops
due to corruption.
Figure 5 presents the results of the simulations when
packets experience reordering. TCP-R performs almost
similar to RN-TCP for all tested average packet delays.
TCP-R gives a better throughput performance when
compared to DSACK-TA for majority of the average
packet delays. For example when the average packet
delay is 0.2 s, TCP-R gives a 5% throughput improve-
ment over DSACK-TA and when the average packet
delay is 0.8 s, TCP-R gives a 10% improvement in
throughput pe rformance when co mpared to DSACK-TA.
TCP-R outperforms DSACK-R and SACK for all tested
average packet delays. None of the protocols exhibit any
timeouts. TCP-R and RN-TCP maintain a zero fast re-
transmit ratio. DSACK-TA’s fast retransmit ratio hovers
around zero. DSACK-R and SACK have a higher fast
retransmit ratio.
4.3. Varying Delay with Constant Bandwidth
In order to analyze the performance of the protocols over
the range of propagation delays exhibited by LEO net-
works, we compare the throughput performance of the
protocols when the propagation delay varied from
[40,400] ms. The bandwidth was fixed at 1.5 Mbps. 7%
of packets were delayed using uniform distribution [0;
4P ] where P is the propagation delay. The BER was set
to 107.
As shown in the Figure 6, it is evid en t that TCP-R ou t-
performs SACK, DSACK-R RN-TCP and DSACK-TA
irrespective of the propagation delay. For large propaga-
tion delays, TCP-R gives an improved throughput per-
formance. For example when the propagation delay was
set to 80 ms, TCP-R gives a 10% throughput improve-
ment over RN-TCP, 20% improvement over DSACK-
TA, 71% more than DSACK-R and a two fold through-
put performance over SACK. When the propagation de-
lay was set to 200 ms, TCP-R gives a 50% improvement
Figure 5. LEO link: Multipath performance, propagation
delay of 400 ms.
Figure 6. Throughput versus propagation delay.
over RN-TCP, 66% improvement over DSACK-TA,
three fold improvement over DSACK-R and four times
more than SACK.
4.4. Varying Bit Error Rates
In this section, we compare the throughput performance

A. SATHIASEELAN 682
of the protocols for various BERs. The bandwidth was
fixed at 1.5 Mbps. The propagation delay was fixed at
300 ms. 5% of packets were delayed using normal dis-
tribution with a mean packet delay of 0.6 s and a stan-
dard deviation of 0.2 s such that the packets were de-
layed between 0 and 1.2 s. We tested the protocols for
various BERs from a relatively low BER of 1013 to a
relatively high BER of 105.
From the Figure 7, it is evident that TCP-R gives a
better throughput performance compared to the other
protocols for different BERs from 1013 to 106. When the
BER is 105, all protocols give a similar throughput per-
formance. For BERs from 1013 to 108, TCP-R, DSACK-
TA, RN-TCP(EPDNv2) and DSACK-R have almost a
zero timeout ratio, whereas SACK encounters more
timeout event and thus has a large timeout ratio. For
BERs of 107 and 106, TCP-R still maintains a zero time-
out ratio whereas the other protocols start encountering
more timeout events and have a larger timeout ratio
compared to TCP-R. When the BER is large as 105, all
protocols undergo lots of timeout events and thus have a
large timeout ratio. Even though RN-TCP (EPDNv2) has
a large fast retransmit ratio compared to DSACK-TA,
DSACK-TA experiences more timeout events compared
to the RN-TCP(EPDNv2). Thus RN-TCP(EPDNv2)
performs better compared to DSACK-TA. TCP-R has a
zero fast retransmit ratio and thus gives an overall im-
provement in throughput compared to the other proto-
cols.
4.5. Throughput: Packet Drops due to
Congestion.
In this section, we compare the throughput performance
of the protocols when the link experiences both packet
delays and packet drops due to congestion in the network.
We also compared the performance of SACK and TCP-R
with packet drops only. The propagation delay was set to
300 ms. 4% of the packets were delayed with a mean
packet delay of 0.6 s and a standard distribution of 0.2 s
such that the packets were delayed between 0 s to 1.2 s.
The packet drop rate varied from 0% to 1%. We assumed
that there were no loss of packets due to corruption and
thus we set the BER to zero.
Figure 8, reveals that the throughput of all the proto-
cols reduce considerably when packets get dropped.
When packet drops occur, the throughput of any TCP
variant would reduce drastically even when there is no
reordering in the network. This is eviden t from the graph,
where the performance of SACK with no delay reduces
drastically with increasing packet drops. Moreover, our
TCP-R with no delay performs similar to SACK with no
delay. Thus, it is clear that given there are no reordering
events, TCP-R performs similar to SACK. When packets
get dropped, TCP-R performs almost similar to DSACK-
Figure 7. Performance for various BERs.
TA. RN-TCP is able to achieve a b etter throughput when
compared to TCP-R and DSACK-TA. But when the
packet drop rate is increased from 0.4%, the performance
of TCP-R, RN-TCP and DSACK-TA are similar. It is to
be noted that all protocols experience similar throughput
performance when large number of packets get dropped
in the network due to congestion in the network.

A. SATHIASEELAN 683
Figure 8. Throughput ver sus packet drop rate.
4.6. Performance: ECN Enabled Multiple FTP
Flows.
In this section, we conducted a simulation on the same
topology as in Figure 1, but used RED queues instead of
drop-tail queues. The gateways were ECN enabled with
a queue size set to 300 packets. The link delay was set to
300 ms. To introduce severe packet delays, we used a
mean of yP s (P is the propagation delay) and standard
deviation of y/3 P s, such that the delay introduced varied
from 0 to 2yP s. The packet delay rate was fixed at 4%.
We varied the value of y from 1.0 to 8.0. The BER was
set to 10¡6. The total number of flows traversing the net-
work was increased to fifty flows, in which the sender
was configured to send ten SACK flows, ten DSACK-R
flows, ten DSACK-TA flows, ten RN-TCP flows and ten
TCP-R flows. All the flows were enabled with ECN.
However, when the number of flows id increased, con-
gestion will be caused in the bottleneck queue causing
large number of packet drops. The graphs in Figure 9
present the results of the average throughput of SACK,
DSACK-R, DSACK-TA, RN-TCP and TCP-R flows. It
can be seen from the graph, that for all average packet
delays from 0.3 s to 2.4 s, TCP-R outperforms the other
protocols. For example, when the average packet delay is
0.3 s, TCP-R gives a 16% improvement over RN-TCP,
29% improvement over DSACK-TA, 36% improvement
over DSACK-R and a 62% improvement ver SACK.
Similarly when the average packet delay is 2.4 s, TCP-R
gives a 26% improvement over RN-TCP, 29% im-
provement over DSACK-TA, 45% improvement over
DSACK-R and a 77% improvement over SACK.
4.7. Conservative RTO Estimation
DSACK-TA and RN-TCP avoids sampling RTTs for all
packets that have been retransmitted by timeouts or fast
retransmit, in accordance with Karn’s algorithm [9],
since the sender cannot infer whether an ACK matches
an original transmission or the retransmission of a data
packet. In the case of paths that predominantly delays
packets it is the delayed packets that are most likely to
provoke retransmissio ns. Thus they are not included hile
estimating the RTO value. This produces RTO estimates
that are too short leading to false timeouts. This is evi-
dent from the poor throughput performance achieved by
RN-TCP and DSACK-TA for large average packet de-
lays in the previous sections. Thus it is imperative to
implement a conservative RTO sampling algorithm that
considers both transmission and retransmission of data
packets. DSACK-TAES is a combination of DSACK-TA
and a conservative RTO sampling algorithm and [19]
proves that for large packet delays, DSACK-TAES per-
forms much better compared to DSACK-TA. In order to
verify the performance of DSACK-TAES with our pro-
posed protocols, we also ensure that our RN-TCP algo-
rithm is also enhanced with this new RTO sampling al-
gorithm.
When packets are falsely retransmitted either by fast
retransmit or by a timeout, two ACKs return, the second
of which is a DSACK. When the sender receives both
these ACKs, it can calculate the RTTs experienced by
the packets by pairing the first ACK with the first trans-
mission, and the second ACK with the second transmis-
sion. It can then calculate the time elapsed for each and
take the mean of these two values as a single RTT sam-
ple for the RTO estimator. The scoreboard data structure
used by SACK can hold this time information associated
with the packet’s transmission and retransmission. Incase
no DSACK arrives at the sender, then either the original
or retransmitted packet was lost due to packet drops, and
we do not sample that packets RTT. This complies with
the Karns Algorithm for retransmissions caused by
packet drops, but includes additional RTT samples for
retransmissions caused by packet delays. We term this
RTT sampling extension to RN-TCP as RN-TCP-ES
Figure 9. Average throughput ver sus ave r age packet de lay.

A. SATHIASEELAN 684
(Reorder Notifying TCP with Enhanced RTT Sampling).
4.7.1. Throughput: Large Reordering Delays (Sce-
nario 1)
In this section, we analyze the throughput performance
of TCP-R over RN-TCP, RN-TCP-ES, DSACK-TA and
DSACK-TAES when packets experience both reordering
due to link level retransmissions and packet losses due to
corruption. In order to drop packets based on corruption,
the BER was set to 106. Figure 10 presents the results of
the simulations when the propagation delay was set to
300 ms. To introduce severe packet delays, we used a
mean packet delay of yP s (P is the propagation delay)
and standard deviation of y/3 P s, such that the delay
introduced varied from 0 to 2yP s. The packet delay rate
was fixed at 7%. We varied the value of y from 1.0 to 7.0.
As we increase y, the RTT of the packet that gets delayed
exceeds the one second minimum RTO causing large
number of ti m eouts.
For all tes ted av e r ag e p acket delays fro m 0 .3 s to 0. 9 s,
the performance of RN-TCP-ES and DSACK-TAES is
almost similar to RN-TCP and DSACK-TA respectively.
When the average packet delay exceeds the one second
minimum RTO, the performance of RN-TCP and
DSACK-TA begin to decrease whereas RN-TCP-ES and
DSACK-TAES maintain a steady throughput. For all
tested average packet delays, TCP-R outperforms the
other protocols. For example, when the average packet
delay is 0.9 s, TCP-R gives a three fold throughput im-
provement over the other protocols. Similarly, when the
average packet delay is 1.8 s, TCP-R gives a 62%
throughput improvement over RN-TCP-ES, 81% through-
put improvement over RN-TCP, 77% throughput im-
provement over DSACK-TAES and almost a 86% im-
provement over DSACK-TA. TCP-R maintains a low
timeout ratio and a zero fast retransmit ratio compared to
the other protocols. Even though RN-TCP-ES has a
higher fast retransmit ratio compared to DSACK-TAES,
RN-TCP-ES has a lower timeout ratio compared to
DSACK-TAES leading to a better throughput improve-
ment.
4.7.2. Throughput: Large Reordering Delays (Sce-
nario 2)
In this section, we analyze the throughput performance
of TCP-R over RN-TCP, RN-TCP-ES, DSACK-TA and
DSACK-TAES when packets experience reordering due
to link level retransmissions and no packets get dropped
due to corruption. The packet delay rate was fixed at 7%.
We varied the value of y from 1.0 to 7.0.
It can be seen from the Figure 11, that when the aver-
age packet delay is less than 1.0 s, the throughput per-
formance of RN-TCP-ES and DSACK-TAES is similar
to RN-TCP and DSACK-TA. When the average packet
delay is more than 1.0 s, the throughput of RN-TCP and
Figure 10. Propagation delay of 300 ms, BER of 106.
DSACK-TA drop rapidly whereas the throughput of
RN-TCP-ES and DSACK-TAES is steady. It is evident
from the timeout ratio graph, that both RN-TCP and
DSACK-TA have a large timeout ratio unlike RN-
TCP-ES and DSACK-TAES which have timeout ratio
that hovers around zero. TCP-R performs much better
compared to the other protocols. For example, when the
average packet delay is 0.9 s, TCP-R gives a 12%
throughput performance over RN-TCP and RN-TCP-ES.

A. SATHIASEELAN 685
Figure 11. Propagation delay of 300 ms.
Moreover TCP-R gives a staggering 65% improvement
over RR-TCP(both DSACK-TA and DSA- CK-TAES).
When the average packet delay is 1.65 s, TCP-R gives a
7% throughput improvement over RN-TCP-ES, 8%
throughput improvement over RN-TCP, 58% throughput
improvement over DSACK-TAES and almost a two fold
improvement over DSACK-TA. TCP-R has a zero fast
retransmit ratio and almost a zero timeout ratio.
5. Conclusions and Future Work
In this paper, we proposed a solution that allows the TCP
sender to distinguish whether a packet has been lost or
reordered in the satellite network and perform actions
accordingly. This was done by maintaining information
about dropped packets (only due to congestion in the
network) in the gateway and using this information to
notify the sender, whether the packet has been dropped
or reordered/corrupted in the network. We termed this
mechanism as Explicit Packet Drop Notification
(EPDNv3). We also proposed an extension to SACK
protocol called Robust TCP (TCP-R). If the TCP-R
sender assumes the packets to be reordered or corrupted
in the network, it immediately retransmits the packet
after receiving three duplicate ACKs and enters our
modified fast recovery mechanism where the procedure
of reducing the ssthresh and the cwnd are bypassed i.e.
we do not reduce the ssthresh and the cwnd. We com-
pared TCP-R with other protocols namely SACK,
DSACK-R, RR-TCP and RN-TCP and showed TCP-R
gave performance improvement over these protocols. We
believe the gateway could be modified to send the
dropped information in an ICMP message to the sender.
This requires further study and testing. Further simula-
tions and testing needs to be carried out to find the effi-
ciency of the protocol when there is an incremental de-
ployment i.e. when there are some routers in a network
which have not bee n upgraded to use our mechani sm.
6. References
[1] J. Postel, “Transmission control protocol,” RFC 793,
1981.
[2] V. Jacobson, “Symposium proceedings on communica-
tions architectures and protocols,” California, pp. 314–
329, 1988.
[3] G. Maral, “VSAT networks,” J. Wiley and Sons, 1995.
[4] R. J. Leopold, “Low-earth orbit global cellular commu-
nications network,” Proceedings of ICC’91, pp. 1108–
1111, 1991.
[5] L. Wood, G. Pavlou, and B. G. Evans, “Effects on TCP
of routing strategies in satellite constellations,” IEEE
Communications Magazine, special issue on Satel-
lite-Based Internet Technology and Services, Vol. 39, No.
3, pp. 172–181, 2001.
[6] C. Ward, H. Choi, and T. Hain, “A data link control pro-
tocol for LEO satellite networks providing a reliable
datagram service,” IEEE/ACM Transactions on Net-
working, Vol. 3, No. 1, 91103, Feb. 1995.
[7] H. Balakrishnan, V. N. Padmanabhan, S. Seshan, and R.
H. Katz, “A comparison of mechanisms for improving
TCP performance over wireless links,” IEEE/ACM
Transactions on Networking (TON) Archive, Vol. 5 , No.
6, pp. 756–769, December 1997.

A. SATHIASEELAN 686
[8] H. Balakrishnan and R. H. Katz, “Explicit loss notifica-
tion and wireless web performance,” Proceedings of the
IEEE Globecom Internet Mini-Conference, Sydney, Aus-
tralia.
[9] R. Krishnan, P. G. Sterbenz, W. M. Eddy, C. Partridge,
and M. Allman, “Explicit transport error notification for
error-prone wireless and satellite networks,” Computer
Networks journal, Elsevier, 2004.
[10] A. Bakre and B. R. Badrinath, “I-TCP: Indirect TCP for
mobile hosts,” Proceedings of the 15th International Con-
ference on Distributed Computing Systems (ICDCS),
1995.
[11] I. F. Akyildiz, G. Morabito, and S. Palazzo, “TCP-peach:
A new congestion control scheme for satellite IP net-
works,” IEEE/ACM Transactions on Networking, Vol. 9,
No. 3, pp. 307–321, 2001.
[12] S. Floyd, J. Mahdavi, M. Mathis, and M. Podolsky, “An
extension to the selective acknowledgement (SACK) op-
tion for TCP,” RFC 2883, 2000.
[13] M. Zhang, B. Karp, S. Floyd, L. Peterson, “RR-TCP: A
reordering robust TCP with DSACK,” 11th IEEE Inter-
national Conference on Network Protocols (ICNP’03),
Georgia, 2003.
[14] A. Sathiaseelan and T. Radzik, “Reorder notifying TCP
(RN-TCP) with explicit packet drop notification
(EPDN),” International Journal of Communication Sys-
tems, Wiley, Vol. 19, No. 6, pp. 659–678, 2005.
[15] T. R. Henderson and R. H. Katz, “Transport protocols for
internet-compatible satellite networks,” IEEE Journal on
Selected Areas in Communications, Vol. 17, No. 2, pp.
345–359, February 1999.