Some of the TCP papers I read during my M.Phil study, with short notes.

2004

Call Admission Control Schemes and Performance Analysis in Wireless Mobile Network

by Yuguang Fang and Yi Zhang
Read: Dec 31, 2004

This paper is about wireless mobile network (i.e. cellular). In such network, users are mobile and each cell has its own capacity.

The paper is about admission control to enter a cell. This paper assumes that, a cell may move between cells during the holding time and a drop on on-going calls is more sensitive than new calls being blocked. Hence on-going calls should have higher priority to use the channels.

The analysis of this paper uses “multidimensional Markov chain”. According to the authors, this technique is used extensively by S. S. Rappaport.

Simulation Studies on Performance of Balanced Fairness

by Vesa Timonen, Dept of Engineering Physics and Mathematics, Helsinki University of Technology, 2003
Master Thesis
Read: Nov 25, 2004

This is an excellent text for an introduction of fairness criteria. The thesis aimed at showing how balanced fairness is a suitable objective in maximizing network bandwidth allocation. In chpaters 2-4 of the thesis, however, describes what is fairness.

The thesis describes in enough details of different fairness criterias and their characteristics and pitfalls, namely, the max-min fairness, proportional fairness, utility-based fairness, and the balanced fairness.

The balanced fairness is different from other fairness because it is insensitive. Which means it do not rely on the detail properties of each flows but the average quantities. The thesis describe those “classical” fairness as “no time scale is considered”. But I cannot see how balanced fairness says about time scale of flows.

Applying Traffic Theory to Internet Design

by Jim Roberts, INOC 2003
A set of powerpoint slides
Read: Nov 24, 2004

This slide describes about the traffic control on internet. In P.6, Roberts describes the IP traffic as “a stationary stopchastic process of sessions, flows and packets” where “congestion is experienced at flow level”.

It also mentioned about the measurement-bassed admission control (MBAC) is a necessary to moderate traffic. It is measurement-based because this can avoid a priori description of how the do admission control. This can also equalize the blocking probabilities for all streaming flows.

In doing the MBAC, it has the lower limit \(R_s\) which is the upper bound of the peak rate of streaming applications, and an upper limit to ensure high utilization.

I don’t understand fully about this. Need review later.

Congestion Control

by Andreas Pitsillides, University of Cyprus, Sep 2000
A set of powerpoint slides
Read: Nov 24, 2004.

This set of slides describes about the difficulties of designing TCP congestion control. It says that the current scene of congestion control divided into two strategies: model based and equation based. But due to the non-linearity of models, the strategies lack of strong theoretical foundation in stabilizing networks. The author of the slides gives two examples on what it means about “strong theoretical foundation in stabilizing”, which are “control systems theory” on controlling complex systems, and “pricing theory” on stabilizing human centered systems.

The slides mentioned the work of Petros Ioannou and L. Rossides of designing a non-linear adaptive robust controller called IDCC (integrated dynamic congestion controller), which can draw some analytical performance bound from it. The rest of the slides are concentrated on IDCC.

To do: Study about IDCC.

by Dah Ming Chiu
Read: Nov 22, 2004

This is a piece of easy-to-read text on the fairness issues in bandwidth sharing on the internet.

Sec 1 describes the works of F. Kelly, M. Mathis and J. Padhye that the TCP bandwidth is approx:

\[x = c/(T \sqrt{q})\]

where \(c\) is some proportionality constant, \(T\) is the RTT and \(q\) is the fraction of packets dropped. But in terms of fairness, we usually use the max-min fairness or proportional fairness.

Sec 2 describes that, F. Kelly’s proportional fairness is the solution to the optimization problem of total social benefit with logarithmic utility function. And having the property that if \(x\) is the fairness (optimal) solution vector:

\[\sum_i \frac{y_i-x_i}{x_i}\le 0\]

for all non-optimial vector \(y\).

Using an example, in page 3, n one-hop flow and one n-hop flow will have the max-min fairness of all equally share \(1/2\) of each hop’s capacity. But in proportional fairness, the bandwidth allocation is inversely proportional to the length of the flow, i.e. those one-hop flows each shares \(n/(n+1)\) and the \(n\)-hop flow shares \(1/(n+1)\). However, as said in page 5, if the network has a single bottleneck, the prop fairness is same as max-min fairness. An example is have one one-hop flow and one n-hop flow only in the whole system.

Sec 3 onward are describing the fairness issue in multicast flows. The conclusion of that is: multicast flow to n receivers is not a single flow (hence should not be counted as one utility value as other unicast flows), and it is also not n times of a single unicast flow because there are “perceived cost-savings from sharing a ride”. Hence the true utility function for that is something in between and yet to be found.

In the implementation of the utility maximization, (1) we should not assume the sender know about the number of receiver in the congestion control algorithm implemented. However, (2) it is possible to elect a representative receiver and do congestion control with them and repeat this for all receivers. (3) The congestion control in multicast can allow some relaxed emulation of TCP.

Rate Control for Communication Networks: Shadow Prices, Proportioanl Fairness and Stability

by F. P. Kelly, A. K. Maulloo, D. K. H. Tan
Read: Nov 19, 2004

This paper describes how does the proportional fairness means (non-weighted/weighted):

\[\begin{align*} \sum_{r\in R} \frac{x_r^\star - x_r}{x_r} & \le 0 \\ \sum_{r\in R} w_r \frac{x_r^\star - x_r}{x_r} & \le 0 \end{align*}\]

However, some system control theory in this paper cause me to stop reading and continue later.

Optimization Problems in Congestion Control

by R. Karp, E. Koutsoupias, C. Papadimitriou, S. Shenker
Read: Nov 18, 2004

This paper describes how to think about congestion control. The authors think congestion control as an searching algorithm such that a flow is aimed to search for the available bandwidth and use it up.

In sec.2, it shows the roadmap of the whole paper: divide the problem into static case and dynamic case. Static case means the bandwidth threshold is a fixed value but dynamic case means the bandwidth is something varying.

Sec 2.1 describes the cost function: it is the opportunity cost \(u-x\) if you sending at \(x\le u\); but overshoting penalty \(\alpha(x-u)\) or \(u\) if you sending at \(x\ge u\) — depends on whether you are using the fast-retransmit TCP or timeout-based TCP, i.e. whether you can detect about the congestion in a short time.

Sec 2.2 says that the threshold \(u\) can change, but assume that \(u_{t+1}\) is somehow in the neighborhood of \(u_t\). The paper suggested that we should study the gain function, which defined as u-cost, rather than the cost function in dynamic case.

Sec 3 evaluates the cost of searching for \(u\) in static case. It gives out different algorithms for the search and the cost is defined to be the sum of the cost incurred (using the cost function in sec 2.1) until you successfully found u and stick to it. In this section, the paper finds the worst case cost as well as the expected cost.

Sec 4 studies the dynamic case. Which is not finished.

by J. W. Roberts and L. Massoulie
Read: Nov 17 2004

This paper describes solely elastic traffic.

In sec.2 of the paper, it reviews the different objective of bandwidth sharing, namely, the maximum throughput, max-min fairness, and proportional fairness. In section 3, it describes the cases that the arrival and data volume of the flows are both random. In detail, they assume the arrival of flows are poisson, and the size distribution are pareto. From that, they found the ordinary processor sharing model gives the result that long flows will utilize all the capacity left by the transfer of shorter documents, i.e. the long flows are taking advantage from short flows.

In sec 3.4, the paper describe the case if the network is employing “shortest remaining processing time” (SPRT) preemptive resume scheduling algorithm. Which improves the response time of short documents, especially if the document size is in pareto distribution.

Sec 5 of the paper studies the case that admission control is imposed on the elastic flows. By admission control, it means to limit the number of flows using a link to a certain maximum number. In that case, it has little use if \(\rho<1\) because the number of flows using the link is usually quite small. But in the case that \(\rho\ge 1\), the number of user using the link tends to infty and the use of admission control can solve that case that everybody stay in the system with tiny amount of throughput, by making some users having zero and keep the number of users in a low number.

The author describe this admission control on elastic traffic as a special case of “intelligent routing” because we divert some flows to a link of zero capacity if the original link is saturated.

On Performance Bounds for the Integration of Elastic and Adaptive Streaming Flows

by Thomas Bonald and Alexandre Proutiere
Read: Nov 12 2004

This paper describe how to use bounds to do analysis of mix-flow throughput.

In sec.2 of the paper, it describes the performance metrics and notations, and using the “processor sharing” model to represent the case of bandwidth sharing between elastic and streaming flows.

In that section, it concludes that in the case of mixed traffic, we cannot get the sensitive bounds or close form solutions for the scenario. However, we can have the insensitive bounds, which is described in detail in the appendix A of the paper. Furthermore, it also shown that, the upper and lower bound of the probability of having \(x_e\) elastic and \(x_s\) streaming flows can be easily obtained in a product form.

The rest of the paper are describing explicitly the probability calculation as well as extending the network model of single link into a queueing network.

MAMSolver: A matrix analytic methods tool

by Alma Riska and Evgenia Smirni

This paper describes how to use the software, mamsolver, to solve queueing problems.

2005

Modeling Markovian Queues and Similar Processes

by Winfried Grassmann
Read: Mar 21.

This gives a survey on the history and achievements on solving markovian queues. The bibliography of this paper can serve as an starting point on different skills for solving queue-related Markov chains.

Transient Analysis of M/M/1/N Queue – An Alternative Approach

by A. M. K. Tarabia (Egypt), 2000
Read: Mar 20.

The paper use vigorious math (but comprehensible) to show the result of Takacs on M/M/1/N queue. The author assumed Chapman-Kolmogorov equation:

\[P'(t) = P(t)P'(0)\]

on a M/M/1/N Continous-time Markov Chain and applying Laplace transform to it and get the result. I am not good at this subject, especially have the following questions:

What is Takacs’ work on transient behavior of M/M/1/N queue?
What is the “transient behavior” about?
What is the reason for applying Laplace transform? (more examples of use desired)

QOS PDQ

by Gunnar Karlsson, Henrik Lundqvist, Ignacio Mas Ivars
Read: Jan 27.

This is a report from KTH, Sweden. PDQ means pretty damn quick.

This documents talks about the QoS issue. In the introduction, they gives the reason why QoS don’t work: “Some installed routers support scheduling for service differentiation, but enabling the scheduling might result in dramatically decreased forwarding performance”. Hence they claim that the right way is to do QoS or service differentiation at the transport level.

The differentiation is looking at two classes: elastic traffic and stream traffic. They were considering the PBAC, probe-based admission control.

Their proposal are as follows: for elastic traffic, impose FEC on established flows (flows in congestion avoidance) to protect them with higher resilience to packet loss. And for those in slow start phase, the flows will back off in case they experience packet loss. The result is to delay new flows until clearing up the old one.

For stream traffic, they said “it is more acceptable to postpone a conversation that cannot reliably be carried out than to allow it to start with high uncertainty about the chances of completing it”. They propose to use PBAC, which the receiver of stream measures the loss ratio and estimates the loss probability to some specified confidence level, then compare the probability with the threshold to determine whether to continue. The established streams also have FEC builtin to protect against packet loss.

In the paper, they claim the stream traffic do probing by sending at the peak rate of the session and that should be at most 1%. They also said, their experiment with modified protocol stack shows successfully that the FEC can priorities established elastic flows. Their result also shows the inband probing traffic will congest the network for a very high rate of set-up attempts.

An Analysis of the Skype Peer-to-Peer Internet Telephony Protocol

by Salman A. Baset, Henning Schulzrinne
Read: Jan 20.
Update Feb 2: Skype released Mac OS X and Linux clients (http://www.skype.com/products/skype/linux/). Now I can try it out.

I get the link of this paper from Slashdot. It describes the authors have reverse engineered the Skype protocol and describes how in works in the protocol level.

The paper talks about how Skype search for the peer, finding the user, the login procedure and so on. Given that Skype protocol is proprietory, this can serve as some sort of open documentation if you need to re-produce one.

Something to note: Skype’s login is not necessary and do not account for the service. However, login is required to show your precence in the phone book so that other people can find you. Hence if I don’t need that, may be I can use the way edonkey or gnutella using to find the peer to talk to — given we assumes six-degree rule is correct. Moreover, seems (from protocol analysis) that Skype server is running Debian.

Debian rules.

Stability and Performance Analysis of Networks Supporting Elastic Services

by Gustavo de Veciana, Tae-Jin Lee, Takis Konstantopoulos
Read: Jan 13.

This paper introduces to me the way to derive the stability from a network with elastic flows.

The network in the paper has only one class – the elastic flows. The network has many nodes. Hence the system state is described by a vector n which describes how many elastic users at each route of the network, where each route is a subset of links of the network.

For each route, the paper constructs a function \(N_r(t)\) to describe the population at time t and the arrival/departure are in Markovian process. The paper describes (A) Max-min fair, (B) weighted max-min fair, (C) proportionally fair bandwidth allocation schemes, which describes how much bandwidth will each users in a route share with other users in the network.

In sec.3, the paper talk about the stability of a stochastic network. They construct a continuous-time markov chain about the system state vector \(n\) and define the generator matrix as \(Q\). If we have a vector function \(V(n)\) as a function of \(n\), then \(QV(n)\) is the expected drift which can serve as similar purpose as first derivative. In sec 3.A, which talks about the stability in max-min fair allocation, the authors construct the function \(V(n)\) as the max time to finish off the work load on any link in the network and use it as a Lyapunov function. They proved that \(V(n)\) is suitable to be a Lyapunov function and it is used to show the stability criteria.

Fair Internet Traffic Integration: Network flow models and analysis

by Peter Key, Laurent Massoulie, Alan Bain, Frank Kelly
Read: Jan 10.

This paper is to address for the problem of what is fair, when the internet gets mixed traffics.

Sec.2 of the paper gives the big picture of what they mean by fairness: as an optimization problem using \(\alpha\)-fairness. Precisely, it is (from paper eq.1 to eq.3):

\[\begin{align*} \textrm{maximize } & \sum_{r\in R} w_r N_r \frac{x_r^{1-\alpha}}{1-\alpha} \\ \textrm{subject to } & \sum_r A_{jr} N_r x_r\le C_j, j\in J \\ \textrm{over } & x_r\ge 0, r\in R \end{align*}\]

and over there, the solution of \(x_r\) using Lagrange multiplier technique is:

\[x_r = \left(\dfrac{w_r}{\sum_j p_j A_{jr}}\right)^{1/\alpha}\]

where \(p_j\) is the Lagrange multiplier and \(\alpha\) is the parameter for \(\alpha\)-fairness, where \(\alpha=0\) is the optimization for max throughput; \(\alpha=1\) is for proportionally fair; \(\alpha=2\) correspond to the inverse-sq. root law; and \(\alpha=\infty\); is the max-min fair. The result of optimization of the vector \(x=(x_r: r\in R)\).

Sec.3 gives a Markov model for the transition of (n,m) where n and m are respectively vectors of number of elastic/streaming users in different routes. In sec.4, the paper gives two differential equations on the number of users of individual route, base on the markov model in sec.3:

\[\begin{align*} \frac{dn_r}{dt} & = \nu_r -\mu_r n_r x_r(n+m) \\ \frac{dm_r}{dt} & = \kappa_r -\eta_r m_r \end{align*}\]

and the invariant point of the above are:

\[\begin{align*} n_r &= \nu_r/\mu_r \left(\frac{\sum_{j\in J} p_j A_{jr}}{w_r}\right)^{1/\alpha} \\ m_r &= \kappa_r/\eta_r \end{align*}\]

But by using this, the bandwidth share are no longer identical between elastic and streaming flows, and they should be different in order to optimize the fairness. Which the optimization becomes (page 9):

\[\begin{align*} \textrm{maximize } & \phi(\lambda,\gamma)=\sum_{r\in R} w_r \left( n_r^\alpha \frac{\lambda_r^{1-\alpha}}{1-\alpha}+m_r^\alpha \frac{\gamma_r^{1-\alpha}}{1-\alpha}\right)\\ \textrm{subject to } & \sum_r A_{jr} (\lambda_r+\gamma_r)\le C_j, j\in J \\ \textrm{over } & \lambda_r, \gamma_r\ge 0, r\in R \end{align*}\]

where \(\lambda_r=n_r x_r\) and \(\gamma_r\) are the total bandwidth consumed by elastic and streaming flows on route \(r\) respectively.

Sec.5.2 further modifies the model to include admission control. Their admission control model are as follows: the streaming flow will try to behave as elastic flow. If, for some time, the rate achieved is \(\lambda_r\) and is greater then its target rate \(\pi_r\), then it will proceed at target rate \(\pi_r\). Otherwise, it will proceed, still in target rate \(\pi_r\), with a probability \(\lambda_r/\pi_r\). Once the flow is admitted, no more adaptation will be done. Their model is definitely going to extract most out of the capacity. But probably overshoot. However, my claim is yet to be proved.

This paper is also doing stability analysis using Lyapunov functions. From which, they cite their technique is referenced from the paper “Impact of Fairness on Internet Performance”, by Bonald and Massoulie, “Fluid model for a nework operating under a fair bandwidth-sharing policy” by Kelly and Williams, and “Stability and Performance Analysis of Networks Supporting Elastic Services” by de Veciana, Lee and Konstantopoulos.

Modeling integration of streaming and data traffic

by F. Delcoigne, A. Proutiere and G. Regnie
Read: Jan 5, 2005

This paper try to measure the performance of elastic traffics when there is streaming flows coexist with them. The metric they measure in this paper is the response time, i.e. the holding time of elastic flows.

In this paper, the author seems to model their stuff base on the Ph.D. thesis of R. Nunez Queija, “Processor-Sharing Models for Integrated-Services Networks”. I am going to read that thesis.

The paper contains some math that I cannot understand. But I found several points interesting to note: 1. Roberts and Massoulie are the first one to use “fluid model” to look at the traffics. 2. The authors said the duration of elastic flows is of the order of a few seconds while the streaming flows is of the order of several minutes.

The core of this paper is to develop bounds on the response time of elastic flows, under the assumption of M/G/1 processor sharing queue model.

2006

Characterizing and Detecting Relayed Traffic: A Case Study using Skype

by Kyoungwon Suh, Daniel R Figueiredo, Jim Jurose, Don Towsley
Tech Report, UMass.
Read: Jan 17

The paper gives an idea on how Skype uses relay nodes. This paper has two focus, the first one is to investigate how the relayed traffic are correlated and the second one tells how to detect such traffic.

For the first part, the authors use “burst” to describe a stream of packets that is sending from one node to another. Normally, in Skype’s case, the burst correspond to a conversation and if it is relayed, the relay node should receive and send the same/similar burst in approximately the same time. The author then controlled a pair of conversation nodes and did an experiment to collect the packet informations to/from an outside relay node. The result is that,

For start time, the bursts to/from the relay node is approximately the same. The start time have no more than 5s difference and most of them is less then 3s. Even if 5% loss is imposed, the difference don’t have significant change.
For end time, the difference is also within 5s and most of them less than 3s. But if the 5% loss is imposed, because of the possibility of lossing the FIN packet, the max difference in end time can be up to 16s.

To study the correlation, the paper proposed a formula to describe the correlation (range from 0 to 1). It is found that the relayed flows have the maximum cross correlation of at least \(0.37\) and \(85%\) of the flows will have more than \(0.9\).

Similar experiment is did to control a relay node and let the Skype users relay using the controlled node. The study shows a similar result.

The second part of the paper is to identify the Skype flows from a network’s packet capture. Using the result above, one can identify the relays by checking whether the “bursts” fulfil certain criteria. They includes the start time difference (\(<11\)s), end time difference (\(<13\)s), burst size ratio (\(<1.33\)), and cross correlation (\(>0.38\)).

The techniques of thinking “flows” as a series of “bursts” in an ON-OFF mannar can be applied to other relay-using applications such as Gnutella. The key concept is to identify the application’s correlation, start time difference, and end time difference, so that the flows can be identified using the measured data.