Our basic idea is motivated by recent work concerning Active Queue Management (AQM) emulation from end-hosts using delay measurements, called Probabilistic Early Response TCP (PERT) [1]. The basic idea behind PERT is very simple and involves responding to delay in a probabilistic rather than deterministic manner. By judiciously selecting the manner of the probabilistic response, Reddy et al. [1] are able to emulate, from end-hosts, the behaviour of a range of AQM’s. To facilitate such AQM emulation, each PERT flow probes the network for congestion as a normal AIMD flow, but reduces its congestion window in a probabilistic manner that depends on the estimated network delay. We refer to this mechanism as a back-off policy. The authors of PERT demonstrate that (in principle) any AQM can be emulated by selecting the back-off policy appropriately. The modified version of PERT (mPERT) [2] purports to be a delay based protocol that solves the coexistence. However, it was subsequently shown that mPERT algorithm fails to solve the coexistence problem in a satisfactory manner [3]. In particular, it is shown in this latter paper that PERT can lead to high loss rates when loss-based flows are present, and that the delay-based flows may fail to revert to delay-based operation when the loss based flows leave the network. Our main contribution here is to present a similar idea that can be used to solve the coexistence problem by carefully choosing the probabilistic back-off function, while avoiding many of the side-effects of the PERT strategy. As we shall see our strategy, referred to as Coexistent TCP (C-TCP) further in this article, avoids problems of adjusting AIMD parameters, keeps the network loss rate low when loss-based flows are present, and ensures that the delay-based flows revert to delay-based operation when loss-based flows are no longer present in the network (termed here as on/off behaviour), even though these flows do not attempt to sense the presence of such flows directly.

We select probabilistic back-off strategies of the form depicted in the figure below. As can be observed, the per-packet back-off probability function has two parts; a part that increases monotonically with the delay (Region A), and a part that decreases monotonically with delay (Region B).

This form of AQM emulation has the following properties:

  1. assuming that the maximum equilibrium loss rate (pmax ) is large enough, the network stabilises in Region A when only delay-based flows are present;
  2. when loss-based flows are present, the network is driven to Region B, and delay-based flows behave as loss-based flows due to the low per-packet back-off probability;
  3. when loss-based flows switch off, the network cannot stabilise in this region due to a backward pressure exerted by the probability function. Namely, as the flows experience back-offs, the queueing delay reduces, thereby increasing the per-packet back-off probability, thus making further back-offs more likely. This process continues until the network stabilises in Region A.
As can be seen, this type of strategy should achieve coexistence of loss- and delay-based AIMD flows, without a discernible increase in network loss rate. Furthermore, the back-pressure described in (3) should ensure on/off behaviour.

A detailed evaluation of C-TCP is presented in a series of articles [3-5].

[1] S. Bhandarkar, A. Reddy, Y. Zhang, and D. Loguinov, “Emulating AQM from end hosts,” SIGCOMM Comput. Commun. Rev., vol. 37, no. 4, pp. 349–360, October 2007.
[2] K. Kotla and A. Reddy, “Making a delay-based protocol adaptive to heterogeneous environments,” in Proc. of 16th International Workshop on Quality of Service (IWQoS 2008), June 2008, pp. 100–109.
[3] Ł. Budzisz, R. Stanojevic, A. Schlotte, R. Shorten and F. Baker On the fair coexistence of loss- and delay-based TCP,” Proc. of the 17th International Workshop on Quality of Service (IWQoS 2009) Charleston, SC, United States, July 2009.
Ł. Budzisz, R. Stanojevic, R. Shorten and F. Baker A strategy for fair coexistence of loss and delay-based congestion control algorithms,” IEEE Communications Letters, vol. 13, no. 7, p. 555-557, July 2009.
Ł. Budzisz, R. Stanojevic, A. Schlotte, R. Shorten and F. Baker Delay based congestion control for heterogeneous environments,submitted to IEEE/ACM Transactions on Networking magazine, under evaluation.

Extended material

To extend the results presented in [5, Section III.A, paragraph 3: Further features in heterogeneous scenarios] we  illustrate the convergence properties of C-TCP in the homogeneous scenario. In what follows all flows are delay-based and have the same RTT. In the analysed test, there are initially 31 delay-based flows running the proposed algorithm, and then, flows either enter (additional 20 flows at time: 200 s), or leave (30 flows at time: 400 s) the discussed scenario. Below, the following cases are presented:

  • Flow living for all the experiment (500 s):
  • One of the flows entering at time=200 s:

  • One of the flows leaving at time=400 s:

As can be seen, all the flows (one that lives for all the time the test lasts, one that enters late and one that leaves early)  adapt almost instantaneously to the predicted throughput rate following the changes in the number of flows.


  Go back to main page

version 0.1,

© Lukasz Budzisz, 17 June 2010