performance over end-to-end rate control and stochastic available capacity.
Motivated by TCP over end-to-end ABR, we study the performance of adaptive window congestion control, when it operates over an explicit feedback rate-control mechanism, in a situation in which the bandwidth available to the elastic traffic is stochastically time varying. It is assumed that the sender and receiver of the adaptive window protocol are colocated with the rate-control endpoints. The objective of the study is to understand if the interaction of the rate-control loop and the window-control loop is beneficial for end-to-end throughput, and how the parameters of the problem (propagation delay, bottleneck buffers, and rate of variation of the available bottleneck bandwidth) affect the performance.The available bottleneck bandwidth is modeled as a two-state Markov chain. We develop an analysis that explicitly models the bottleneck buffers, the delayed explicit rate feedback, and TCP's adaptive window mechanism. The analysis, however, applies only when the variations in the available bandwidth occur over periods larger than the round-trip delay. For fast variations of the bottleneck bandwidth, we provide results from a simulation on a TCP testbed that uses Linux TCP code, and a simulation/emulation of the network model inside the Linux kernel.We find that, over end-to-end ABR, the performance of TCP improves significantly if the network bottleneck bandwidth variations are slow as compared to the round-trip propagation delay. Further, we find that TCP over ABR is relatively insensitive to bottleneck buffer size. These results are for a short-term average link capacity feedback at the ABR level (INSTCAP). We use the testbed to study EFFCAP feedback, which is motivated by the notion of the effective capacity of the bottleneck link. We find that EFFCAP feedback is adaptive to the rate of bandwidth variations at the bottleneck link, and thus yields good performance (as compared to INSTCAP) over a wide range of the rate of bottleneck bandwidth variation. Finally, we study if TCP over ABR, with EFFCAP feedback, provides throughput fairness even if the connections have different round-trip propagation delays.
Introduction
bottleneck link
xmitter
recvr
ABR
recvr
end-to-end ABR
source
ABR

Figure

1: The network under study has a large round trip delay and a single congested
link in the path of the connection. The ABR connection originates at the host and ends
at the destination node. We call this scenario "end-to-end" ABR.
The Available Bit Rate (ABR) service in Asynchronous Transfer Mode (ATM)
networks is primarily meant for transporting best-effort data traffic. Connections that
use the ABR service (so called ABR sessions) share the network bandwidth left over after
serving CBR and VBR traffic. This available bandwidth varies with the requirements of
the ongoing CBR/VBR sessions, hence the switches carrying ABR sessions implement
a rate-based feedback control for congestion avoidance. This control causes the ABR
sources to reduce or increase their cell transmission rates depending on the availability
of bandwidth in the network. As the ABR service does not guarantee end-to-end reliable
transport of data to the applications above it, an additional protocol is needed between
the application and the ATM layer to ensure reliable communication. In most deploy-
IP
host
IP
host
ATM
wide area network
router/switch router/switch
IP
IP
ABR
IP
IP
ABR

Figure

2: TCP/IP over edge-to-edge ATM/ABR, with the TCP connection split into one
edge-to-edge TCP over ABR connection, and two end-to-edge TCP over IP connections.
The edge switch/router regulates the flow of TCP acknowledgements back to the TCP
senders.
ments of ATM networks, the Internet's Transport Control Protocol (TCP) is used to
ensure end-to-end reliability for data applications.
TCP, however, has its own adaptive window based congestion control mechanism
that serves to slow down sources during network congestion. Hence, it is very important
to know whether the adaptive window control at the TCP level, and the rate-based
control at the ABR level interact beneficially from the point of view of application level
throughput. In this paper, we consider the situation in which the ATM network extends
upto the TCP endpoints; i.e., end-to-end ABR (as opposed to edge-to-edge ABR), see

Figure

1. Our results also apply to TCP over edge-to-edge ABR if the end-to-end TCP
connection comprises a tandem of an edge-to-edge TCP connection, and two edge-to-end
connections, with TCP spoofing being done at the edge-devices (see Figure 2).
Consider the hypothetical situation in which the control loop has zero delay. In
such a case, the ABR source of a session (i.e., the ATM network interface card (NIC)
at the source node) will follow the variations in the bandwidth of the bottleneck link
without delay. As a result, no loss will take place in the network. The TCP window will
grow, and once the TCP window size exceeds the window required to fill the round trip
pipe, the packets will be buffered in the source buffer. Hence, we can see that congestion
is effectively pushed to the network edge. As the source buffer would be much larger than
the maximum window size, the TCP window will remain fixed at the maximum window
size and congestion control will become a purely rate based one. If ABR service was not
used, however, TCP would increase its window, overshoot the required window size, and
then due to packet loss, would again reduce the window size. Hence, it is clear that, for
zero delay in the control loop, end-to-end ABR will definitely improve the throughput of
TCP.
When variations in the bottleneck bandwidth do occur, however, and there is
delay in the ABR control loop, it is not clear whether there will be any improvement.
In this paper, we study TCP over end-to-end ABR, and consider a TCP connection in a
network with large round-trip delay; the connection has a single bottleneck link with time
varying capacity. Current trends seem to indicate that at least in the near future, ATM
will remain only a WAN transport technology. Hence ATM services will only extend
to the network edge, whereas TCP will continue to be used as the end-to-end protocol,
with interLAN IP packets being transported over ATM virtual circuits. When designing
a wide-area intranet based on such IP over ATM technology one can effectively control
congestion in the backbone by transporting TCP/IP traffic over ABR virtual circuits. A
connection between hosts on two LANs would be split into a TCP over ABR wide-area
edge-to-edge connection, and two end-to-edge connections over each of the LANs;
see

Figure

2. The edge devices would then control the TCP end-points on their respective
LANs by regulating the flow of acknowledgements (ACKs) back to the senders. In this
framework, our results would apply to the edge-to-edge TCP over ABR connection.
Many simulation studies have been carried out to study the interaction between
the TCP and ATM/ABR control loops. In [7], the authors study the effect of running
large unidirectional file transfer applications on TCP over ABR. An important result
from their study is that cell loss ratio (CLR) is not a good indicator of TCP perfor-
mance. They also show that when maximum throughput is achieved, the TCP sources
are rate limited by ABR rather than window limited by TCP. Reference [8] reports a
study of the buffering requirements for zero cell loss for TCP over ABR. It is shown that
the buffer capacity required at the switch is proportional to the maximum round trip
time of all the VCs through the link, and is independent of the number of sources (or
VCs). The proportionality factor depends on the switch algorithm. In further work, in
[9], the authors introduce various patterns of VBR background traffic. The VBR background
traffic introduces variations in the ABR capacity and the TCP traffic introduces
variations in the ABR demand.
In [3], the authors study the effect of ATM/ABR control on the throughput and
fairness of running large unidirectional file transfer applications on TCP-Tahoe and TCP-Reno
(see [15]) with a single bottleneck link with a static service rate. The authors in
[12] study the performance of TCP over ATM with multiple connections, but with a
static bottleneck link. The paper reports a simulation study of the relative performances
of the ATM ABR and UBR service categories in transporting TCP/IP flows through an
edge-to-edge ATM (i.e., the host nodes are not ATM endpoints) network. Their summary
conclusion is that there does not seem to be strong evidence that for TCP/IP workloads
the greater complexity of ABR pays off in better TCP throughputs. Their results are,
however, for edge-to-edge ABR; they do not comment on end-to-end (i.e., the hosts have
an ATM NIC) ATM which is what we study in this paper.
All the studies above are primarily simulation studies, and analytical work on
TCP over ABR does not seem to exist in the literature. In this paper, we make the
following contributions:
(i) We develop an analytical model for a TCP connection over explicit rate ABR
when there is a single bottleneck link with time varying available capacity. In the
analytical model we assume that the explicit rate feedback is based on the short
term average available capacity; we think of this as instantaneous capacity feedback,
and we call the approach INSTCAP feedback.
(ii) We use a test-bed to validate the analytical results. This test-bed implements
a hybrid simulation comprising actual Linux TCP code, and a network emula-
tion/simulation implemented in the IP loopback code in the Linux kernel.
(iii) We then develop an explicit rate feedback that is based on a longer term history
of the bottleneck rate process. The computation is motivated from (though it
is not the same as) the well known concept of effective capacity (derived from
large deviations analysis of the bottleneck queue process). We call this EFFCAP
feedback. EFFCAP is more effective in preventing loss at the bottleneck buffers.
Since the resulting model is hard to analyse, the results for EFFCAP feedback are
all obtained from the hybrid simulator mentioned above. Our results show that
different types of bottleneck bandwidth feedbacks are needed for slowly varying
bottleneck bandwidth, rapidly varying bottleneck bandwidth and the intermediate
regime. EFFCAP feedback adapts itself to the rate of bandwidth variation. We then
develop guidelines for choosing two parameters that arise in the on-line calculations
of EFFCAP.
(iv) Finally, we study the performance of two TCP connections that pass through the
same bottleneck link, but have different round trip propagation delays. Our objective
here is to determine whether TCP over ABR is fairer than TCP alone, and
under what circumstances. In this study we only use EFFCAP feedback.
The paper is organized as follows. In Section 2, we describe the network model
under study. In Section 3 we develop the analysis of TCP over ABR with INSTCAP
Segmentation
Buffer
Rate Feedback
HOST COMPUTER
ABR
adaptive rate
server bottleneck link

Figure

3: The segmentation buffer of the system under study is in the host NIC card
and extends into the host's main memory. The rate feedback from the bottleneck link is
delayed by one round trip delay.
feedback, and of TCP alone. In Section 4, we develop the EFFCAP algorithm; TCP
over ABR with EFFCAP feedback is only amenable to simulation. In Section 5, we
present analysis results for INSTCAP feedback, and simulation results for INSTCAP
and EFFCAP. The performance of INSTCAP and EFFCAP feedbacks are compared. In
Section 6, we study the choice of two parameters that arise in EFFCAP feedback. In
Section 7 we provide simulation results for two TCP connections over ABR with EFFCAP
feedback. Finally, in Section 8, we summarise the observations from our work.
2 The Network Model
Consider a system consisting of a TCP connection between a source and destination node
connected by a network with a large propagation delay as shown in Figure 1. The TCP
congestion control does not implement fast-retransmit, and hence must time out for loss
recovery. We assume that only one link (called the bottleneck link) causes significant
queueing delays in this connection, the delays due to the other links being fixed (i.e.,
only fixed propagation delays are introduced due to the other links). A more detailed
model of this is shown in Figure 3. The TCP packets are converted into ATM cells and
are forwarded to the ABR segmentation buffer. This buffer is in the network interface
card (NIC) and extends into the main memory of the computer. Hence, we can look upon
this as an infinite buffer. The segmentation buffer server (also called the ABR source)
gets rate feedback from the network. The ABR source service rate adapts to this rate
feedback.
The bottleneck link buffer represents either an ABR output buffer in an ATM
switch (in case of TCP over ABR), or a router buffer (in case of TCP alone). The
network carries other traffic (CBR/VBR) which causes the bottleneck link capacity (as
seen by the connection of interest) to vary with time. The bottleneck link buffer is finite
which can result in packet loss due to buffer overflow when rate mismatch between the
source rate and the link service rate occurs. In our model, we will assume that a portion
of the link capacity is reserved for best-effort traffic, and hence is always available to the
TCP connection. In the ATM/ABR case such a reservation would be made by using the
Minimum Cell Rate (MCR) feature of ABR, and would be implemented by an appropriate
link scheduling mechanism. Thus when guaranteed service traffic is backlogged at this
link, then the TCP connection gets only the bandwidth reserved for best-effort traffic,
otherwise it gets the full bandwidth. Hence a two state model suffices for the available
link rate.
In the first part of our study, we assume that the ABR feedback is an instantaneous
rate feedback scheme; i.e., the bottleneck link periodically feeds back its short term
to the ABR source. This feedback reaches after one round trip
propagation delay. The ABR source adapts to this value and transmits the cells at this
rate.
3 TCP/ABR with Instantaneous Capacity Feedback
At time t, the cells in the ATM segmentation buffer at the source are transmitted at a time
dependent rate S \Gamma1
which depends on the ABR rate feedback (i.e., S t is the service time
of a packet at time t). The bottleneck has a finite buffer B max and has time dependent
service rate R \Gamma1
t packets=sec which is a function of an independent Markov chain. In our
analysis, we assume that there is a 2 state Markov chain modulating the channel. In each
state, the bottleneck link capacity is deterministic. If the buffer is full when a cell arrives
to it, the cell is dropped. In addition, we assume that all cells corresponding to that TCP
packet are dropped. This assumption allows us to work with full TCP packets only; it
is akin to the Partial Packet Discard proposed in [13]. If the packet is not lost, it gets
serviced at rate R \Gamma1
(assumed constant over the service time of the packet), and reaches
the destination after some deterministic delay. The destination ATM layer reassembles
the packet and delivers it to the TCP receiver. The TCP receiver responds with an ACK
TCP/ABR Transmitter Bottleneck Link Propagation Delay

Figure

4: Queueing model of TCP over end-to-end ABR
(acknowledgement) which, after some delay (propagation processing delay) reaches the
source. The TCP source responds by increasing the window size.
The TCP window evolution can be modeled in several ways (see [11], [10]). In
this study, we model the TCP window adjustments in the congestion avoidance phase
(for the original TCP algorithm as proposed in [4] by Van Jacobson) probabilistically
as follows: every time a non-duplicate ACK (an acknowledgement that requests for a
packet that has not been acknowledged earlier) arrives at the source, the window size W t
increases by one with probability 1
On the other hand, if a packet is lost at the bottleneck link buffer, the ACK
packets for any subsequently received packets continue to carry the sequence number of
the lost packet. Eventually, the source window becomes empty, timeout begins and at the
expiry of the timeout, the threshold window W th
t is set to half the maximum congestion
window achieved after the loss, and the next slow start begins.
3.1 Queueing Network Model

Figure

4 is a closed queueing network representation of the TCP over ABR session. We
model the TCP connection during the data transfer phase; hence the data packets are
assumed to be of fixed length. The buffer of the segmentation queue at the source host
is assumed to be infinite in size. There are as many packets in this buffer as the number
of untransmitted packets in the window. The service time at this buffer models the time
taken to transmit an entire TCP packet worth of ATM cells. Owing to the feedback
rate control, the service rate follows the rate of the bottleneck link. We assume that
the rate does not change during the transmission of the cells from a single TCP packet.
The service time (or equivalently, the service rate) follows the bottleneck link service rate
with a delay of \Delta units of time, \Delta being the round trip (fixed) propagation delay.
The bottleneck link is modeled as a finite buffer queue with deterministic packet
service time with the service time (or rate) Markov modulated by an independent Markov
chain on two states 0 and 1; the service rate is higher in state 0. The round trip propagation
delay \Delta is modeled by an infinite server queue with service time \Delta. Notice that
various propagation delays in the network (the source-bottleneck link delay, bottleneck
link-destination delay and the destination-source return path delay) have been lumped
into a single delay element (See Figure 4). This can be justified from the fact that even
if the source adapts itself to the change in link capacity earlier than one round trip time,
the effect of that change will be seen only after a round trip time at the bottleneck link.
With "packets" being read as "full TCP packets", let
A t be the number of packets in the segmentation buffer at the host at time t
t be the number of packets in the bottleneck link buffer at time t
D t be the number of packets in the propagation queue at time t
R t be the service time of a packet at the bottleneck link; R t 2 fr g. We take
. Thus, all times are normalized to the bottleneck link
packet service time at the higher service rate.
S t be the service time of a packet at the source link. S t follows R t with delay \Delta, the
round trip propagation delay, i.e., S g. Since the instantaneous
rate of the bottleneck link is fed back, we call this the instantaneous rate
feedback scheme. (Note that, in practice, the instantaneous rate is really the average
rate over a small window; that is how instantaneous rate feedback is modelled
in our simulations to be discussed later; we will call this feedback INSTCAP.)
3.2 Analysis of the Queueing Model
Consider the vector process
Slow start phase
no loss Window reaches w & ceases to grow
Coarse timeout occurs
log wLoss epoch
round trip propagation delay
Figure

5: The embedded process
This process is hard to analyze directly. Instead, we study an embedded process, which
with suitable approximations, turns out to be analytically tractable.
consider the embedded process
f ~
with ~
use the obvious notation ~
In the following analysis, we will make the following assumptions :
(i) We assume that the rate modulating Markov chain is embedded at the epochs
(ii) The source adapts immediately to the explicit rate feedback that it receives. This
is true for the actual ABR source behaviour (as specified by the ATM Forum [1]) if
the rate decreases. In the actual ABR source behaviour, an increase in the explicit
rate results in an exponential growth of the source rate and not a sudden jump.
We, however, assume that even an increase in the source rate takes place with a
sudden jump.
(iii) There is no loss in the slow start phase of TCP. In [11], the authors show that
loss will occur in the slow start phase if Bmax \Delta
1even if no rate change occurs in
the slow start phase. However, for the case of TCP over ABR, as the source and
bottleneck link rates match, no loss will occur in this phase as long as rate changes
do not occur during slow-start. Hence, this assumption is valid for the case of TCP
alone only if Bmax \Delta
Observe that packets in the propagation delay queue (see Figure 4) at t k will have
departed from the queue by t k+1 . This follows as the service time is deterministic, equal
to \Delta, and t \Delta. Further, any new packet arriving to the propagation delay
queue during still be present in that queue at t k+1 . On the other hand,
if loss occurs due to buffer overflow at the bottleneck link in (t k ; t k+1 ), we proceed as
follows. Figure 5 shows a packet loss epoch in the interval This is the first
loss since the last time that TCP went through a timeout and recovery. At this loss
epoch, there are packets in the bottleneck buffer, and some ACKs "in flight" back to the
transmitter. These ACKs and packets form an unbroken sequence, and hence will all
contribute to the window increase algorithm at the transmitter (we assume that there is
no ACK loss in the reverse path). The transmitter will continue transmitting until the
window is exhausted and then will start a coarse timer. We assume that this timeout will
occur in the interval (t k+2 ; t k+3 ) (see Figure 5), and that recovery starts at the embedded
epoch t k+3 . Thus, when the first loss (after recovery) occurs in an interval then, in our
model, it takes two more intervals to start recovery.
s). Note that, since no loss has occurred (since last
recovery) until t k , therefore, the TCP window at t k is a d. Now, given ~
assuming that
(i) packet transmissions do not straddle the embedded epochs, and
(ii) packets arrive back-to-back into the segmentation buffer during any interval (t
(This leads to a conservative estimate of TCP throughput. See the discussion following
Figure 8 below.)
we can find the probability that a loss occurs during (t k ; t k+1 ), and the distribution of
the TCP window at the time that timeout starts. Suppose this window is w, then the
congestion avoidance threshold in the next recovery cycle will be m := d we. It will
take approximately dlog 2 me round trip times (each of length \Delta) to reach the congestion
avoidance threshold. Assuming that no loss occurs during the slow start phase (this
is true if B max is not too small [11]), at k me, we can determine the
distribution of ~
. With the above description in mind, define
For k  1,
loss occurs
in (T
loss occurs
in (T
the loss window is w
and
. For a particular realization of X k , we will write
(a; b; d;
loss occurs during (T k ;
and
for k  0 (7)
Recalling the evolution of fT
We now proceed to analyze the evolution of fX k ; k  0g.
The bottleneck link modulating process, as mentioned earlier, is a two state
Markov chain embedded at taking values in fr g. Let p 01 be the
transition probabilities of the Markov chain. Notice that S
also a Discrete time Markov chain (DTMC). Let Q be the transition probability matrix
for (R k
g.
As explained above, given X
is
For particular can be determined using the probabilistic
model of window evolution during the congestion avoidance phase. Consider the evolution
of A k , the segmentation buffer queue process. If no loss occurs in (T k ; T k+1 ),
s
where N k is the increment in the TCP window in the interval, and is characterized as
follows: During (T k ; T k+1 ), for each ACK arriving at the source (say, at time t), the
window size increases by one with probability 1
. However, we further assume that
the window size increases by one with probability 1
(where
the probability does not change after every arrival but, instead, we use the window at
Then, with this assumption, due to d arrivals to the source queue, the window size
increases by the random amount N k . We see that for d ACKs, the maximum increase
in window size is d. Let us define ~
N k such that ~
a+b+d ). Then ,
d)). We can similarly get recursive relations for B k+1 and
Consider an example for explaining the evolution of X k to X k+1 . Let X
(a; b; d; 2; 1), i.e., the source service rate is twice that of the bottleneck link server, and
loss can take place. Further, d  \Delta packets are in flight. These d packets arrive at the
source queue, increase the window size by N k , and hence, min(a+d+N k ; \Delta) packets are
transmitted into the bottleneck buffer (at most \Delta packets can be transmitted at rate 1
during an interval of length \Delta). If
loss will occur. For a given b and d, we can compute the range of N k for which
Equation 11 is satisfied. Suppose that loss occurs for N k  x( 0). Then,
ix
Let us define
Prfwindow achieved is w loss occurs in (T k
We can compute this quantity in a manner similar to that outlined for the computation
of p(x).
When no loss occurs, U k is given by Equation 8. When loss occurs, given X
the next cycle begins after the recovery from loss which includes the
next slow start phase. Suppose that the window was 2m when loss occured. Then, the
next congestion avoidance phase will begin when the TCP window size in the slow start
phase after loss recovery reaches m. This will take dlog 2 me cycles. At the end of this
period, the state of various queues is given by m). The channel state
at the start of the next cycle can be described by the transition probability matrix of the
modulating Markov chain. Hence,
me with probability p(x):ff(x; 2m) (14)
and
From the above discussion, it is clear that given X k , the distribution of X k+1 can
be computed without any knowledge of its past history. Hence, fX k ; k  0g is a Markov
chain. Further, given T k and X k , the distribution of T k+1 can be computed without any
knowledge of its past history. Hence, the process f(X k ; T k ); k  0g is a Markov Renewal
Process (MRP) (See [17]). It is this MRP that is our model for TCP/ABR.
3.3 Computation of Throughput
Given the Markov Renewal Process f(X we associate with the kth cycle
that accounts for the successful transmission of packets. Let (x)
denote the stationary probability distribution of the Markov chain fX k ; k  0g. Denote
by fl TCP=ABR , the throughput of TCP over ABR. Then, by the Markov renewal-reward
theorem ([17]), we have
denotes the expectation w.r.t. the stationary distribution (x).
The distribution (x) is obtained from the transition probabilities in Section 3.2.
We have
x
is the expected reward in a cycle that begins with
B(x) and D(x) the values of A, B and D in the state x. Then, in an interval (T k
where no loss occurs, we take
Thus for lossless intervals the reward is the number of acknowledgements returned to the
source; note that this actually accounts for packets successfully received by the receiver
in previous intervals.
Loss occurs only if the ABR source is sending at the high rate and the link is
transmitting at the low rate. When loss occurs in (T k \Delta), we need to account
for the reward in the interval starting from T k until T k+1 when slow-start ends. Note
that at T k the congestion window is A(x) D(x). The first component of the
reward is D(x); all the B(x) buffered packets will result in ACKs, causing the left edge
of the TCP window to advance. Since the link rate is half the source rate, loss will
occur when 2(B packets enter the link buffer from the ABR source; these
packets succeed and cause the left edge of the window to further advance. Further, we
assume that the window grows by 1 in this process; hence, following the lost packet,
at most A(x) packets can be sent. Thus we bound the reward
before timeout occurs by D(x)
loss and timeout, the ensuing slow-start phase successfully
transfers some packets (as described earlier). Hence, an upper bound on the "reward"
when loss occurs is A(x)
the summation index w being over all window sizes. Actually, this is an optimistic reward
as some of the packets will be transmitted again in the next cycle even though they have
successfully reached receiver. We could also have a conservative accounting, where we
assume that if loss occurs, all the packets transmitted in that cycle are retransmitted in
future cycles. In the numerical results, we shall compare the throughputs with these two
bounds. It follows that
x
Similarly we have
x
where U(x) is the mean cycle length when x at the beginning of the cycle. From
the analysis in Section 3.2, it follows that
Hence,
x
3.4 TCP without ATM/ABR
Without the ABR rate control, the source host would transmit at the full rate of its
link; we assume that this link is much faster than the bottleneck link and model it as
Constant Rate
Arrival Process

Figure

server queue with time varying service capacity, being fed by a constant
rate source.
infinitely fast. The system model is then very similar to the previous case, the only
difference being that we have eliminated the segmentation buffer. The assumptions we
make in this analysis, however, lead to an optimistic estimate of the throughput. The
analysis is analogous to that provided above.
4 TCP/ABR with Effective Capacity Feedback
We now develop another kind of rate feedback. To motivate this approach, consider a
finite buffer single server queue with a stationary ergodic service process (see Figure 6).
Suppose that the ABR source sent packets at a constant rate. Then, we would like to
find that rate which maximizes TCP throughput. Hence, let the input process to this
queue be a constant rate deterministic arrival process. Given the buffer size B max and a
desired Quality of Service (QoS) (say a cell loss probability  ffl), we would like to know
the maximum rate of the arrival process such that the QoS guarantee is met.
We look at a discrete time approach to this problem (see [16]); in practice, the
discrete time approach is adequate as the rate feedback is only updated at multiples of
some basic measurement interval. Consider a slotted time queueing model where we can
service C i packets in slot i and the buffer can hold B max packets. fC i g is a stationary and
ergodic process; let EC be the mean of the process and C min be the minimum number of
packets that can be served per slot. A constant number of packets (denoted by fl) arrive
in each slot. We would like to find fl max such that the desired QoS (cell loss probability
ffl) is achieved. In [16], the following asymptotic condition is considered. If X is a
random variable that represents the stationary queue length, then, with
lim
log
i.e., for large B max the loss probability is better then e \GammaffiB max . It is shown that this
All logarithms are taken to the base e
performance objective is met if
lim
log Ee \Gammaffi
For the desired QoS we need
. Let us denote the expression on the right hand
side of Equation 25 as \Gamma eff . Then, \Gamma eff can be called the effective capacity of the server.
which is what we intuitively
expect. For all other values of ffl, \Gamma eff 2 (C min ; EC).
Let us apply this effective capacity approach to our problem. Let the ABR source
(see

Figure

adapt to the effective bandwidth of the bottleneck link server. In our anal-
ysis, we have assumed a Markov modulated bottleneck link capacity, changes occurring
at most once every \Delta units of time, \Delta being the round trip propagation delay. Hence,
we have a discrete time model with fl being the number of packet arrivals to the bottle-neck
link in \Delta units of time and C i being the number of packets served in that interval.
We will compute the effective capacity of the bottleneck link server using Equation 25.
However, before we can do this, we still need to determine the desired QOS, i.e, ffl or
equivalently, ffi.
To find ffi, we conduct the following experiment. We let the ABR source transmit
at some constant rate, say ; For a given Markov modulating process, we
find that  which maximizes TCP throughput. We will assume that this is the effective
capacity of the bottleneck link. Now, using Equation 25, we can find the smallest ffi that
results in an effective capacity of this . If the value of ffi so obtained turns out to be
consistent for a wide range of Markov modulating processes, then we will use this value
of ffi as the QoS requirement for TCP over ABR.
The above discrete time queueing model for TCP over ABR can be analyzed in
a manner analogous to that in Section 3.2. We find from the analysis that for several
sets of parameters, the value of ffi which maximizes TCP throughput is consistently very
large (about 60-70). This is as expected since TCP performance is very sensitive to loss.
4.1 Algorithm for Effective Capacity Computation
In practice, we do not know a priori the statistics of the modulating process. Hence,
we need an on-line method of computing the effective bandwidth. In this section, we
develop an algorithm for computing the effective capacity of a time varying bottleneck
link carrying TCP traffic. The idea is based on Equation 25, and the observation at the
end of the previous section that ffi is very large.
Averages
time

Figure

7: Schematic of the windows used in the computation of the effective capacity
bsed rate feedback.
We take the measurement interval to be s time units; s is also the update interval
of the rate feedback. We shall approximate the expression for effective bandwidth in
Equation 25 by replacing n !1 by a large finite M .
log Ee \Gammaffi
What we now have is an effective capacity computation performed over Ms units of time.
We will assume that the process is ergodic and stationary. Hence, we approximate the
expectation by the average of N sets of samples, each set taken over Ms units of time.
Note that since the process is stationary and ergodic, the N intervals need not be disjoint
for the following argument to work. Then, denoting C ij as the ith link capacity value
in the jth block of M intervals (j 2 f1; Ng), we have
logN
e \Gammaffi
log 1
log
e \Gammaffi
As motivated above, we now take ffi to be large. This yields
log e
\Gammaffi(min
We notice that this essentially means that we average capacities over N sliding blocks,
each block representing Ms units of time, and feed back the minimum of these values (see

Figure

7).
The formula that has been obtained (Equation 31) has a particularly simple form.
The above derivation should be viewed more as a motivation for this formula. The
formula, however, has independent intuitive appeal; see below. In the derivation it was
required that M and N should be large. We can, however, study the effect of the choice
of M and N (large or small) on the performance of effective capacity feedback. This
is done in Section 6, where we also provide guidelines for selecting values of M and N
under various situations.
The formula in Equation 31 is intuitively satisfying; we will call it EFFCAP
feedback. Consider the case when the network changes are very slow. Then, all N values
of the average capacity will be the same, and each one will be equal to the capacity
of the bottleneck link. Hence, the rate that is fed back to the ABR source will be
the instantaneous free capacity of the bottleneck link; i.e., in this situation EFFCAP
is the same as INSTCAP. When the network variations are very fast, EFFCAP will
be the mean capacity of the bottleneck link which is what should be done to get the
best throughput. Hence, EFFCAP behaves like INSTCAP for slow network changes and
adapts to the mean bottleneck link capacity for fast changes. For intermediate rates of
changes, EFFCAP is (necessarily) conservative and feeds back the minimum link rate.
There is another benefit we could get by using EFFCAP. As EFFCAP assumes
a large value of ffi, this means the the cell loss probability ffl is very small. This implies
that the TCP throughput will essentially be the ABR throughput. Thus EFFCAP when
used along with the Minimum Cell Rate feature of the ABR service can guarantee a
minimum throughput to TCP connections. Some of our simulation results to be presented
demonstrate this.
5 Numerical and Simulation Results
In this section, we first compare our analytical results for the throughput of TCP, without
ABR and with ABR with INSTCAP feedback, with simulation results from a hybrid TCP
simulator involving actual TCP code, and a model for the network implemented in the
loopback driver of a Linux Pentium machine. We show that the performance of TCP
improves when ABR is used for end-to-end data transport below TCP. We then study
the performance of the EFFCAP scheme and compare it with the INSTCAP scheme.
Efficiency
Mean time per state (rtd)
"Conservative Analysis, 10 packets"
"Conservative Analysis, 12 packets"
"Optimistic Analysis, 12 packets"
"Testbed results, 10 packets"
"Testbed results, 12 packets"

Figure

8: Analysis and Simulation results: INSTCAP feedback. Throughput of TCP over
ABR: The round trip propagation delay is 40 time units. The bottleneck link buffers are
either 10 or 12 packets. Notice that, for / ? 80, the lowest two curves are test-bed
results, the uppermost two curves are the optimistic analysis, and the middle two curves
are the conservative analysis.
5.1 Instantaneous Rate Feedback Scheme
We recall from the previous section that the bottleneck link is Markov modulated. In
our analysis, we have assumed that the modulating chain has two states which we call
the high state and the low state. In the low state, with some link capacity being used by
higher priority traffic, the link capacity is some fraction of the link capacity in the high
state (where the full link rate is available). In the set of results that we present in this
section, we will assume that this fraction is 0.5. Further, we will also assume that the
mean time in each state is the same, i.e., the Markov chain is symmetric. We denote the
mean time in each state by  , and denote the mean time in each state normalized to \Delta
by /, i.e., / :=
. For example, if \Delta is 200msec, then means that the mean time
per state is 400msec. Note that our analysis only applies to / ? 1. A large value of /
means that the network changes are slow compared to the round trip propagation delay
(rtd) , whereas / !! 1 means that the network transients occur several times per round
trip time. In the Linux kernel implementation of our network simulator, the Markov
chain can make transitions at most once every 30msec. Hence we take this also to be the
measurement interval, and the explicit rate feedback interval (i.e.,
We denote one packet transmission time at the bottleneck link in the high rate
state as one time unit. Thus, in all the results presented here, the packet transmission
time in the low rate state is 2 time units.
We plot the bottleneck link efficiency vs. mean time that it spends in each state
(i.e. We define efficiency as the throughput as a fraction of the mean capacity of
the bottleneck link. We include the TCP/IP headers in the throughput, but account for
ATM headers as overhead. We use the words throughput and efficiency interchangeably.
With the modulating Markov chain spending the same time in each state, the mean
capacity of the link is 0.75.

Figure

8 shows the throughput of TCP over ABR with the INSTCAP scheme 2 .
Here, we compare an optimistic analysis, a conservative one (see Section 3.3), and the
test-bed (i.e., simulation) results for different buffer sizes. In our analysis, the processes
are embedded at multiples of one round trip propagation delay, and the feedback from
the bottleneck link is sent once every rtd. This feedback reaches the ABR source after
one round trip propagation delay. In the simulations, however, feedback is sent to the
ABR source every 30msec. This reaches the ABR source after one round trip propagation
delay.
In

Figure

8, we can see that, except for very small /, the analysis and the simulations
match to within a few percent. Both the analyses are less than the observed
throughputs by about 10-20% for small /. This can be explained if we note that in our
model, we assume that packets arrive (leave) back to back to (from) the ABR source.
When a rate change occurs at the bottleneck link, as the packets arrive back to back, and
the source sends at twice the rate of the bottleneck link (in our example); for every two
packets arriving to the bottleneck link, one gets queued. However, in reality, the packets
need not arrive back to back and hence, the queue buildup is slower. This means that
the probability that packet loss occurs at the bottleneck link buffer is actually lower than
in our analytical model. This effect becomes more and more significant as the rate of
bottleneck link variations increase. However, we observe from the simulations that this
effect is not significant for most values of /.

Figure

9 shows the throughput of TCP without ABR. We can see that the simulation
results give a throughput of upto 20% less than the analytical ones. This occurs
due to two reasons.
Even if / !1, the throughput of TCP over ABR will not go to 1 because of ATM overheads. For
every 53 bytes transmitted, there are 5 bytes of ATM headers. Hence, the asymptotic throughput is
approximately 90%.
Efficiency
Mean time per state (rtd)

Figure

9: Analysis and Simulation results; throughput of TCP without ABR : The round
propagation delay is 40 time units. The bottleneck link buffers are either 10 or 12
packets. We observe that TCP is sensitive to bottleneck link buffer size changes.
(i) We assumed in our analysis that no loss occurs in the slow-start phase. It has been
shown in [11] that if the bottleneck link buffer is less than 1of the bandwidth-delay
product (which corresponds to about 13 packets or 6500 byte buffer), loss will occur
in the slow-start phase.
(ii) We optimistically compute the throughput of TCP by using an upper bound on
the "reward" in the loss cycle.
We see from Figures 8 and 9 that ABR makes TCP throughput insensitive to
buffer size variations. However, with TCP alone, there is a significant worsening of
throughput with buffer reduction. This can be explained by the fact that once the ABR
control loop has converged, the buffer size is immaterial as no loss takes place when
source and bottleneck link rate are the same. However, without ABR, TCP loses packets
even when no transients occur.
It is useful to observe that since the times in the above curves are normalized
to the packet transmission time (in the high rate state), results for several different
ranges of parameters can be read off these curves. To give an example, if the link has
a capacity of 155Mbps during its high rate state, and TCP packets have a size of 500
bytes each, then one time unit is 25:8sec. The round trip propagation delay (\Delta) is
means that changes in link bandwidth occur
Efficiency
Mean time per state (rtd)
Alone, 8 packets"
Alone, 12 packets"

Figure

10: Simulation results for TCP with and without ABR (INSTCAP feedback) for
small values of /. The rtd is 40 time units.
on an average, once every 103.2msec. Consider another example where the link capacity
is 2Mbps during the high rate period. Let the packet size by 1000bytes. Then, the delay
here corresponding to 40 time units is 160msec. here corresponds to changes
occurring once every 16 seconds. These two examples illustrate the fact the the curves
are normalized and can be used to read off numbers for many scenarios. 3
From

Figures

8 and 9, we can see that the performance of TCP improves by
about 20% when ABR is employed for data transport, INSTCAP feedback is used, and
the changes in link rate are slow. This improvement in performance with ABR is due to
the fact that ABR pushes the congestion to the network edge. After the TCP window
grows beyond the point where the pipe gets full, i.e., W t
r , the packets start
queueing in the ABR segmentation buffer, which being on the end system, is very large.
The window size increases till the maximum window size advertised by the receiver is
reached. No loss occurs in the network as the ABR source sends at just the right rate to
the bottleneck link. Hence, we end up with the TCP window size fixed at the maximum
window size and the pipe is always full.
The assumptions in our analysis render it inapplicable for very small /. Figure 10
compares the simulation results for TCP with ABR (INSTCAP feedback) and without
ABR for various buffer sizes. These results are for / starting with going
3 Note however that \Delta is an absolute parameter in these curves, since it governs the round trip "pipe".
Thus, although / is normalized to \Delta, the curves do not yield values for fixed / and varying \Delta.
down to We note that even though the throughput improvement due to ABR
is not great for small /, the performance of TCP does not significantly worsen due to
ABR. In the next section, we will see how a better rate feedback in ABR can result in a
distinct improvement of TCP/ABR throughput even for this range of /.
We see from Figure 10 that when / becomes less than 1, the throughput of TCP
increases. This can be explained by the fact that the rate mismatch occurs for an interval
of time less than one round trip propagation delay. As a result, the buffer size required
to handle the overload becomes less. As / becomes very small, each packet is sent at a
different rate and hence, the ABR source effectively sends at the mean capacity. Then
loss very rarely occurs as the buffers can handle almost all rate mismatches and hence,
the throughput increases.
5.2 Comparison of EFFCAP and INSTCAP Performance: Simulation
Efficiency
Mean time per state (rtd)
"Effective Capacity, 8 packets"
"Effective Capacity, 10 packets"
"Effective Capacity, 12 packets"
"Instantaneous rate feedback, 8 packets"
"Instantaneous rate feedback, 10 packets"
"Instantaneous rate feedback, 12 packets"

Figure

11: Simulation results; Comparison of the EFFCAP and INSTCAP feedback
schemes for TCP over ABR for various bottleneck link buffers (8-12 packets). As before,
the rtd is 40 time units. Here, Figure 7). In this figure, we
compare their performances for relatively large /.
In

Figure

11, we use results from the test-bed to compare the relative performances
of the EFFCAP and INSTCAP feedback schemes for ABR. Recall that the EFFCAP
algorithm has two parameters, namely M , the number of samples used for each block
average, and N , the number of blocks of M samples over which the minimum is taken.
Efficiency
Mean time per state (rtd)
"Effective Capacity, 8 packets"
"Effective Capacity, 10 packets"
"Effective Capacity, 12 packets"
"Instantaneous rate feedback, 8 packets"
"Instantaneous rate feedback, 10 packets"
"Instantaneous rate feedback, 12 packets"

Figure

12: Simulation results; Comparison of the EFFCAP and INSTCAP feedback
schemes for TCP over ABR for various bottleneck link buffers (8-12 packets). As before,
the rtd is 40 time units. Here, Figure 7). In this figure, we
compare their performances for small values of /.
In this figure, the EFFCAP scheme uses i.e, we average over one round trip
propagation delay 4 worth of samples. We also maintain a window of 8 rtd worth of
averages, i.e, we maintain averages over which the bottleneck link
returns the minimum to the ABR source. The source adapts to this rate. In the case of
the INSTCAP scheme, in the simulation, the rate is fed back every 30msec.
We can see from Figure 11 that for large /, the throughput with EFFCAP is worse
than that with the INSTCAP scheme by about 3-4%. This is because of the conservative
nature of the EFFCAP algorithm (it takes the minimum of the available capacity over
several blocks of time in an interval).
However, we can see from Figure 12 that for small /, the EFFCAP algorithm
improves over the INSTCAP approach by 10-20%. This is a significant improvement and
it seems worthwhile to lose a few percent efficiency for large / to gain a large improvement
for small /.
To summarize, in Figures 13 and 14, we have plotted the throughput of TCP over
ABR using the two different feedback schemes. We have compared these results with
the throughput of TCP without ABR. We can see that the throughput of TCP improves
4 A new sample is generated every 30msec. The rtd is 200msec in this example. Hence,
6.667 which we round up to 7.
Efficiency
Mean time per state (rtd)
"Effective Capacity, 10 packets"
"Instantaneous rate feedback, 10 packets"

Figure

13: Simulation results; Comparison of throughput of TCP over ABR with effective
capacity scheme, instantaneous rate feedback scheme and TCP without ABR for a buffer
of 10 packets, the other parameters remaining the same as in other simulations.0.50.60.70.80.9
Efficiency
Mean time per state (rtd)
"Effective Capacity, 10 packets"
"Instantaneous rate feedback, 10 packets"

Figure

14: Simulation results; Comparison of throughput of TCP over ABR with effective
capacity scheme, instantaneous rate feedback scheme and TCP without ABR for a buffer
of 10 packets, the other parameters remaining the same as in other simulations.
if ABR is employed for link level data transport. These plots clearly brings out the
merits of the effective capacity scheme. We can see that for all values of /, the EFFCAP
scheme performs considerably better than TCP alone. For large /, we have a throughput
improvement of about 30% while for small /, the improvement is of the order of 10-15%.
Further, while being adaptive to /, EFFCAP succeeds in keeping the TCP throughput
better than the minimum link rate, which INSTCAP fails to do (for small /). Thus an
MCR in the ABR connection may be used to guarantee a minimum TCP throughput.
6 Choice of M and N for EFFCAP
6.1 Significance of M and N
We begin by recalling the results shown in Figures 11 and 12. From these figures, we can
identify three broad regions of performance in relation to /.
For / very large (/ ? 50), the rate mismatch occurs for a small fraction of  .
Also the rate mismatches are infrequent, implying infrequent losses, thereby increasing
the throughput. Hence, it is sufficient to track the instantaneous available capacity by
choosing small values of M and N . This is verified from Figure 11 which shows that the
INSTCAP feedback performs better in this region.
On the other hand, when  is a small fraction of \Delta (/ ! 0:2) there are frequent
rate mismatches but of very small durations as compared to \Delta. This reduces the buffer
requirement, and hence losses occur rarely. Because of the rapid variations in the capacity,
even a small M provides the mean capacity. Also all the N averages roughly equal the
mean capacity. Thus, the source essentially transmits at the mean capacity in EFFCAP
as well as INSTCAP feedback. Hence a high throughput for both feedbacks is seen from

Figure

12.
For the intermediate values of / (0:5 ! / ! 20), the throughput drops substantially
for both types of feedback. For these values of /,  is comparable to \Delta. Hence rate
mismatch is frequent, and persists relatively longer causing the buffer to build up to a
larger value. This leads to frequent losses. Because of frequent losses the throughput is
adversely affected by TCP's blind adaptation window control. In this range, we expect
to see severe throughput loss for sessions with large \Delta. Therefore, in this region, we
need to choose M and N properly; essentially, to avoid rate mismatch and hence loss,
the capacity estimate should yield the minimum capacity, implying the need for small
M and large N . A small M helps to avoid averaging over many samples, and a large N
helps to pick out the minimum.
The selection of M and N cannot be based on the value of / alone however.
\Delta is an absolute parameter in TCP window control and has a major effect on TCP
throughput, and hence on the selection of M and N . This can be seen from the results
in Section 6.2.
6.2 Simulation Results and Discussion
Simulations were carried out on the hybrid simulator that was also used in Section 5. As
before, the capacity variation process is a two state Markov chain. In the high state, the
capacity value is 100KB/sec (KB= Kilo Bytes) while in the low state it is 50KB/sec. The
mean capacity is thus 75KB/sec. In all the simulations, the measurement and feedback
30ms. Throughput is measured for data transfer of a 10MB file; the average
throughput for 4 file transfers is reported. The TCP packet size is 500 bytes and the
maximum TCP window is 32KB.
M denotes the number of measurement samples in the averaging window. The
effective capacity method uses N such overlapping windows (see Figure 7) to determine
the minimum average. Thus N corresponds to the 'memory' of the algorithm. We
introduce the following notation in the simulation results. means that each average
is calculated over measurement intervals corresponding to the round trip propagation
delay, that is, d \Delta
means that
e averages are
compared (or the memory of the algorithm is k round trip times). For example, let
200ms and
(i.e., minimum of 49 averages).
6.2.1 Study of N
In this section, we study the effect of N on the throughput by carrying out two sets of
simulations.
Case 1: Fixed \Delta; varying

Figure

15 shows the effect of N on the throughput of a TCP session with a
given \Delta, when  (or equivalently the rate of capacity variation) is varying. These results
corroborate the discussion at the beginning of Section 6.1 for fixed \Delta; for large / (/ ? 60),
a small value of N performs slightly better, whereas when / is very small (/ ! 0:3),
where the throughput increases steeply, there is negligible throughput gain by increasing
N . When 0:3 ! / ! 1, as expected, an improvement is seen for larger N . But for
only a slight improvement is seen with varying N .
Efficiency
Mean Time per State (rtd)
Efficiency
Mean Time per State (rtd)

Figure

15: Efficiency variation with / for increasing values of N .
is varied from 32ms
to 40s. The link buffer is 10 pkts or 5000KB. The advantage of choosing a larger value
of N in the intermediate range of / (0:2 clearly seen.
Case 2: Fixed  ; varying \Delta0.30.40.50.6
Efficiency
Mean Time per State (rtd)

Figure

Efficiency vs.  is fixed to
1000ms. \Delta is varied (right to left) from
50ms to 500ms. M : \Delta; link buffer=10
Efficiency
Mean Time per State (rtd)

Figure

17: Efficiency vs.  is fixed to
100ms. \Delta is varied (right to left) from
50ms to 500ms. M : \Delta, link buffer=10
pkts.

Figures

and 17 show the Efficiency variation with / for different values of N
when  is fixed and \Delta is varied. We note that, according to the notation, N is different
for different \Deltas on a N : k\Delta curve. For example, N on the N : 4\Delta curve for (i.e., the
memory of the algorithm is 4 rtds) 100ms is respectively 6 and 12.
We notice that compared to Figure 15, Figures 16 and 17 show different Efficiency
variations with /. This is because, in the former case  is varied and \Delta kept constant,
whereas in the latter case  is fixed and \Delta varied. As indicated in Section 6.1, \Delta is
an absolute parameter which affects the throughput Figure 16 corresponds to
\Delta=500ms, and Figure 17 corresponds to 50ms). The considerable throughput
difference demonstrates the dependence on the absolute value of \Delta. It can be observed
that the throughput for larger values of \Delta is lower than that for small values of \Delta. This
difference is because a TCP session with larger \Delta needs a larger window 5 to achieve the
desired throughput. A single packet loss causes the TCP window to drop. After a packet
loss, it takes a longer time for a session with larger \Delta to rebuild the window than a
session with a smaller \Delta. In the intermediate range of /, as explained in Section 6.1,
losses are frequent and high. Hence, the throughput of a session with large \Delta is severely
affected.
In

Figure

17, a substantial improvement in the throughput is seen as the memory
of the EFFCAP algorithm increases. A larger memory gives better throughput over a
wider range of \Delta as compared to lower values. The reason for these observations is
as follows. For a given \Delta, as N increases we are able to track the minimum capacity
value better. The minimum capacity is 50KB/sec, which is 66% of the mean capacity
75KB/sec. Hence, as N increases we see Efficiency increasing above 0.6.
that for small / , the average over \Delta yields the average rate, whereas for large / the
average over \Delta yields the peak or minimum rate. Thus for large /, the minimum over
just few \Deltas (4 to 6) is adequate to yield a high throughput, whereas for small / many
more averages need to be minimized over to get the minimum rate.

Figure

shows that for / ! 8, larger values of N improve the throughput
according to the argument given above. When we see that smaller N performs
better, but the improvement is negligible.
The conclusions that can be drawn from above results are as follows. The choice
of N is based on / and \Delta. For very large / (/ ? 20) N should be small (along with
M ); the limiting case being 1. For very small / (/ ! 0:2) N does not matter
much. In the intermediate range, a large N is better.
6.2.2 Study of M
In this section we study the performance of M , the averaging parameter. We have already
seen from Figure 11 that for / ? 60, a small value of M should be selected. We now
study the lower ranges of /.
5 Actually TCP window depends directly on the bandwidth delay product. In all the numerical results
however the link speed is fixed, hence the window depends simply on \Delta.
Efficiency
Window Size (measurement intervals)
RTT 50ms
RTT 100ms
Efficiency
Window Size (measurement intervals)
RTT 50ms
RTT 100ms
RTT 200ms

Figure

Efficiency variation with varying M .  is set to 1000ms, and three \Delta values-
50ms, 100ms and 200ms are considered. In the left-hand graph, N is set according to
and in the right-hand N : 12\Delta. M is varied from 1 to 10, i.e., the averaging
interval is varied from 30ms to 300ms. The link buffer is 10 pkts. / ranges from 5 (for
Efficiency
Window Size (measurement intervals)
RTT 50ms
RTT 100ms
RTT 200ms0.50.70.9
Efficiency
Window Size (measurement intervals)
RTT 50ms
RTT 100ms
RTT 200ms

Figure

19: Efficiency variation with varying M .  is set to 100ms, and three \Delta values-
50ms, 100ms and 200ms are considered. In the left-hand graph, N is set according to
and in the right-hand N : 12\Delta. M is varied from 1 to 10. The link buffer is 10
pkts. / ranges from 0.5 (for
To study the effect of M , we vary the window size for two N settings, so that the
effect of N could be differentiated. M is varied from 1 to 10 measuring intervals. The
results are shown in Figure Figure 19 100ms). The values
of \Delta are 50ms, 100ms and 200ms. Thus the range of /(=
under consideration is 0.5
to 20. We have already found that M needs to be small for / ? In the
range under consideration, however, we observe that the throughput is not very sensitive
to M .
In

Figure

18, a clear advantage of increasing N is seen for 200ms. For
ms in this figure, that is, we see a slight trend in decreasing throughput with
increasing M . This is because \Delta is small and with small M it is possible to track the
instantaneous capacity better for larger  . For larger \Delta values and 1000ms the above
mentioned trend is greatly reduced making the throughput insensitive to M . However,
a slight decrease in the throughput is seen in case of ms when M takes larger
values. The reason is as follows. As discussed in Section 6.1, larger value of M makes
the response of the algorithm sluggish. Hence to track the minimum in the intermediate
range of /, a larger N is needed. In this case N is fixed, hence the decrease for larger
M . A similar effect is seen in the Figure 19 for \Delta=50ms and 100ms.
In

Figure

19, / is in the range 0.5 to 2. For the throughput is insensitive
to the variation in M . Insensitivity is observed in the case of N : small / but for
larger /, that is, \Delta=50ms and 100ms, a 10-15% decrease in the throughput is seen. The
reason, as explained above, is the inability to track the minimum because of the smaller
value of N .
We conclude that in the intermediate range of /, the throughput is not very
sensitive to M . For small \Delta and larger / (e.g. performs
better since it is possible to track the instantaneous rate. In general, a small value of M
improves the throughput in the intermediate range. For larger values of M , N needs to
be increased to enable tracking of the minimum.
7 TCP/ABR with EFFCAP Feedback:
Multiple Sessions Sharing a Bottleneck Link
Throughput fairness is a major issue for multiple sessions sharing a bottleneck link. It
is seen that TCP alone is unfair towards sessions that have larger round trip times.
It may be expected however, that TCP sessions over ABR will get a fair share of the
available capacity. In [14], the fairness of the INSTCAP feedback was investigated and
it was shown that for slow variations of the available capacity, TCP sessions over ABR
employing the INSTCAP feedback achieve fairness. In this section we study the fairness
of TCP sessions over ABR with the EFFCAP feedback scheme
In the simulations, we use 240ms as the round-trip time for Session 1 and 360ms
for Session 2. The link buffer size is bytes. Denote by \Delta 1 and \Delta 2 , the
round-trip times for Session 1 and Session 2 respectively. Other notations are as described
earlier (subscripts denote the session number). In the following graphs / is  (mean time
per state of the Markov chain) divided by larger 360ms. Simulations are
carried out by calculating the EFFCAP by two different ways as explained below.
Case 1: Effective Capacity with
In this case, we calculate the EFFCAP for each session independently. This is done by
selecting M i proportional to \Delta i , that is (with a 30ms update interval) we select
for Session 1 and 2. We take
132 (see section 6). EFFCAP i is computed with M i and N i ; session i is fedback 1of

Figure

20 shows the simulation results. We see that for very small values of /
0:3), the sessions receive equal throughput. However, for 0:3 unfairness is
seen towards the session with larger propagation delay. This can be explained from the
discussion in Section 6.1. In this range of /, due to frequent rate mismatches and hence
losses, TCP behavior is dominant. A packet drop leads to greater throughput decrease
for a session with larger \Delta than for a session with smaller \Delta.0.250.350.450.550
Efficiency
Mean time per state (larger rtd)
session 1:240ms
session 2:360ms0.250.350.450.550
Efficiency
Mean time per state (larger rtd)
session 1:240ms
session 2:360ms

Figure

20: Efficiency variation with / (mean time per state normalized to larger
in the case of two sessions sharing a link. \Delta 1 is 240ms and \Delta 2 is 360ms. Link buffer
is 18pkts. Each session is fed back the fair share (half) of the
EFFCAP calculated.
7.2 Case 2: Effective Capacity with simulation M corresponds to the average of \Delta 1 and \Delta 2 , i.e., 300ms or 10 measurement
intervals. Correspondingly, with choosing
Efficiency
Mean time per state (larger rtd)
session 1:240ms
session 2:360ms0.250.350.450.550
Efficiency
Mean time per state (larger rtd)
session 1:240ms
session 2:360ms

Figure

21: Efficiency variation with / (mean time per state normalized to larger
in the case of two sessions sharing a link. \Delta 1 is 240ms and \Delta 2 is 360ms. Link buffer is
18pkts. averages. Each session is
fed back the fair share (half) of the EFFCAP calculated.
M and N this way, we are making rate calculation independent of individual round-trip
times.
We observe from Figure 21 that the EFFCAP calculated in this way yields somewhat
better fairness than the scheme used in Case 1. We also see that better fairness
is obtained even in the intermediate range of /. However, there is a drop in the overall
efficiency. This is because the throughput of the session with smaller \Delta is reduced.

Figures

22 and 23 show the comparison of TCP alone with TCP over ABR with
EFFCAP feedback for a longer range of /. These curves include results from Figures 20
and 21. We see that for / ? 20, EFFCAP gives fairness to the sessions whereas TCP
is grossly unfair to the session with larger \Delta. There is a slight decrease in the overall
efficiency with TCP over ABR; but note that with TCP over ABR the link actually
carries 10% more bytes (the ATM overhead) than with TCP alone! We also see from

Figure

even when / ! 20 which is not observed in the
case of INSTCAP in [14].
Conclusions
In this paper, we first developed an analytical model for a wide-area TCP connection
over end-to-end ABR with INSTCAP feedback, running over a single bottleneck link with
time-varying capacity. We have compared our analytical results for the performance of
TCP without ABR, and with ABR (INSTCAP rate feedback) with results from a hybrid
Efficiency
Mean time per state (larger rtd)
session 1: EFFCAP
session 2: EFFCAP
session 1: TCP alone
session 2: TCP alone

Figure

22: Comparison between Efficiency of sessions with TCP alone and TCP over
ABR employing EFFCAP feedback (Case 1). \Delta 1 is 240ms and \Delta 2 is 360ms. Both the
cases use a link buffer of pkts.
simulation. We have seen that the analysis and simulation results for TCP over ABR
match quite well, whereas the analysis overestimates the performance of TCP without
ABR. Our results show that the throughput improvement by running TCP over ABR
depends on the relative rate of capacity variation with respect to the round trip delay in
the connection. For slow variations of the link capacity the improvement is significant
(25% to 30%), whereas if the rate variations are comparable to the round trip delay then
the TCP throughput with ABR can be slightly worse than with TCP alone.
We have also proposed EFFCAP, an effective capacity based algorithm for rate
feedback. We have simulated TCP over ABR with EFFCAP feedback and shown that,
unlike INSTCAP feedback, EFFCAP succeeds in keeping the TCP throughput higher
than the minimum bandwidth of the bottleneck link; see Figure 12. The EFFCAP
computation involves two parameters M and N .
The throughput variation with /, of a TCP session over ABR employing EFFCAP
feedback, can be broadly divided into three regions. The selection of parameters M and
thus, depends on the range of / as well as on the round-trip propagation delay.
When / is very large (? 60) M and N need to be small. Ideally
Efficiency
Mean time per state (larger rtd)
session 1: EFFCAP
session 2: EFFCAP
session 1: TCP alone
session 2: TCP alone

Figure

23: Comparison between Efficiency of sessions with TCP alone and TCP over
ABR employing EFFCAP feedback (Case 2). \Delta 1 is 240ms and \Delta 2 is 360ms. Both the
cases use a link buffer of pkts.
INSTCAP) performs the best in this region. When / is small (! 0:3), it is sufficient for
the source to send at the mean bottleneck rate; for such /, because of rapid capacity
variations, the mean capacity can be measured by selecting a large M . However, as /
becomes very small, the choice of M and N does not matter much. When / is in the
intermediate range (0:5 ! / ! 20), the throughput decreases due to frequent losses,
hence M and N need to be selected carefully. In this region a large value of N improves
the throughput whereas the performance is insensitive towards M . In general, a small
value of M performs better for a given value of N . The throughput drop in this region
can be compensated by choosing a large buffer, thereby, reducing the losses.
In summary, as a broad guideline, for the buffer sizes that we studied, using
provides good throughput performance for TCP
over ABR over a wide range of / and \Delta values.
In the case of multiple sessions, EFFCAP feedback provides fairness over a wider
range of / then INSTCAP. EFFCAP feedback based on the average round-trip times
of the sessions is seen to provide fairness even when the capacity variations are in the
intermediate range. This is an advantage over INSTCAP which is fair only when the
rate variations are slow compared to \Delta [14].



--R

The ATM Forum Traffic Management Specification Version 4.0
"A Simulation of TCP Performance in ATM Networks"
" Impact of ATM ABR Control on the Performance of TCP-Tahoe and TCP-Reno"
"Congestion avoidance and control"
"Modified TCP Congestion Avoidance Algorithm"
" The ERICA Switch Algorithm for ABR Traffic Management in ATM Networks,"
" Performance of TCP/IP over ABR Service on ATM Networks"
" Buffer Requirements for TCP/IP over ABR"
" Performance of TCP over ABR on ATM Backbone and with Various VBR Traffic Patterns"
"Comparative performance analysis of versions of TCP in a local network with a lossy link"
"The Performance of TCP/IP for Networks with High Bandwidth Delay Products and Random Loss, "
"TCP over ATM: ABR or UBR"
"Dynamics of TCP Traffic over ATM Networks"
"TCP over End-to-End ABR: A Study of TCP Performance with End-to-End Rate Control and Stochastic Available Capacity"
Slow Start, Congestion Avoidance, Fast Retransmit, and Fast Recovery Algorithms"
"Effective Bandwidths: Call Admission, Traffic Policing and Filtering for ATM Networks"
Stochastic Modeling and the Theory of Queues Prentice Hall
--TR
The performance of TCP/IP for networks with high bandwidth-delay products and random loss
Comparative performance analysis of versions of TCP in a local network with a lossy link
Analysis of source policy and its effects on TCP in rate-controlled ATM networks
TCP over wireless with link level error control
The ERICA switch algorithm for ABR traffic management in ATM networks
Modeling TCP Reno performance
A new approach for asynchronous distributed rate control of elastic sessions in integrated packet networks

--CTR
Aditya Karnik , Anurag Kumar, Performance of TCP congestion control with explicit rate feedback, IEEE/ACM Transactions on Networking (TON), v.13 n.1, p.108-120, February 2005
Jung-Shian Li , Chuan-Gang Liu , Cheng-Yu Huang, Achieving multipoint-to-multipoint fairness with RCNWA, Journal of Systems Architecture: the EUROMICRO Journal, v.53 n.7, p.437-452, July, 2007
Ahmed E. Kamal, Discrete-time modeling of TCP Reno under background traffic interference with extension to RED-based routers, Performance Evaluation, v.58 n.2+3, p.109-142, November 2004
TCP over ABR;congestion control;TCP performance