K.E. Avrachenkov (INRIA Sophia Antipolis)
TCP Network Calculus: The case of large delay-bandwidth product.
We present an analytical model for the calculation of network
load and drop probabilities in a TCP/IP network with general topology.
First we formulate our model as a nonlinear complementarity problem.
Then we transform the model into two equivalent formulations:
fixed point formulation and nonlinear programming formulation.
These equivalent formulations provide efficient computational
procedures for the solution of our model. Furthermore, with
the help of the fixed point formulation we are able to prove
the existence of a solution. Our model has the main advantage
of not requiring the pre-definition of bottleneck links.
The model also takes into account the receiver congestion
window limitation. Our approach can be used for TCP/IP networks
with drop tail routers as well as for TCP/IP networks with
active queue management routers. We solve the problem for
some network examples and we show how the distribution of load
varies with network parameters. The distribution of load is
sometimes counter-intuitive which cannot be detected by other
models making prior assumptions on the locations of bottlenecks.
This is a joint work with E. Altman and C. Barakat.
C. Touati (INRIA Sophia Antipolis)
La notion d'equite dans les problemes d'allocation de bande passante.
Imaginons le cas d'une ressource partagee entre plusieurs clients de
besoins differents. Le probleme auquel est confronte l'operateur du
reseau est de savoir comment distribuer cette ressource entre tous.
Une strategie consiste a attribuer la ressource au plus offrant : c'est
la maximisation du profit pour l'operateur.
A l'autre extreme, l'operateur peut choisir de donner un maximum de
ressource au plus petit client : ainsi on choisit de leser le moins
possible les petites demandes.
Le concept d'equite permet de modeliser toutes les strategies possibles
de l'industriel et peut etre utilise pour les problemes d'allocation de
bande passante dans les reseaux.
Je proposerai 2 algorithmes, l'un base sur la programmation semi-definie
positive (SDP), l'autre sur la programmation dynamique qui resolvent les
problemes d'allocation dans deux exemples, tires respectivement du cas
des reseaux terrestres et satellitaires.
U. Ayesta (INRIA Sophia Antipolis)
Modeling of short TCP transfers
In this talk we examine the behaviour of TCP/IP network with multiple
short TCP sessions. In the first instance we consider a scenario with a
single bottleneck. TCP sessions arrive according to the Poisson process.
The data that a TCP session needs to transmit is distributed exponentially
with the mean 10Kbytes. We study two cases: In the first case the load was
up to 80% and the packets on the link did not experience any significant
lossses. It turned out that it is appropriate to apply M/G/inf model in
this situation. In the second case one cannot neglect anymore losses on
the link. For this case we propose to use the fixed point approach.
R. van der Mei (KPN Research and Vrije Universiteit, Amsterdam)
Analyis of a flow-level model for TCP behaviour in case of
priority queueing
The TCP protocol is responsible for the transportation of the
vast majority of the Internet traffic. Currently, the Internet is migrating
from a best-effort type of service delivery to a network supporting Quality
of Service (QoS) differentiation.
In this talk, I will focus on the problem of dimensioning of TCP-based
networks supporting QoS differentiation. To this end, I will discuss the
use of the so-called Generalized Processing Sharing (GPS) model for the
development of simple and fast approximations for mean object download
times over the Internet. The validity of the model is validated by
comparing the results with simulations.
R. Groenevelt (INRIA Sophia Antipolis)
Peer-to-Peer network in a nutshell
One of the latest developments on the internet has been the emergence of
Peer-to-Peer (P2P) networks. The basic idea behind P2P is (computer) resource
sharing. This can mean, for example, the sharing of computational calculation
power (as in the SETI@Home project) or the sharing of storage capacity. In most
of the cases, however, one must think of file-sharing in the sense of searching
for and locating files in a big network. With the introduction and court appeal
of the controversial Napster (MP3 site), P2P has stepped into the spotlight and
serious development has commenced. Peer-to-peer has been labelled by many as
the 'hot item' of the future and the upcoming emergence of (scientific) articles
and development of special P2P soft- and hardware are prove of this. So far very
little technical literature has been written on the (mathematical) modelling of
P2P networks. We are interesting in developing mathematical models of (generic)
P2P architectures in order to gain a better understanding of these networks.
In a quest for acquiring knowledge on peer-to-peer (P2P) networks, this lecture
will be used to present P2P (modelling) in a nutshell, as well as identifying
problems and research topics. Topics to be touched are the different characteristics
of (real-life) P2P networks, the pros and cons of different P2P models, and finally,
which (characteristics of) P2P networks are interesting to look at from a (mathematical)
modelling point of view.
R. Elazouzi (INRIA Sophia Antipolis)
Side Contrained Traffic Equilibrium in Multiuser Communication Networks
We study noncooperative routing in a network of parallel links, in which
each user is faced with a multicriterion optimization problem which is
formulated as the minimization of one criterion subject to constraint on
others. We address here the basic questions of existence and uniqueness
of equilibrium.
To that end,
we first show in a simple example
of parallel links that there may be several such equilibria.
In the same example, in absence of side constraints there
would be a single equilibrium (Rosen). We then obtain some weak
uniqueness result for the parallel link topology, and show that although
the equilibrium may not be unique, the links utilization at equilibrium
is unique.
In view of the nonuniqueness of the equilibria, our second objective is
to study the normalized Nash equilibrium introduced by Rosen. The
uniqueness of this equilibrium notion has been established
in Rosen for cases in which constrained Nash equilibria
were not unique, under some strictly diagonal concavity conditions.
These conditions turn out not to hold in general in our setting of
networking games. In spite of that, we establish the uniqueness of the
normalized Nash equilibrium for the case of parallel links, and we study
its properties. We then use some properties of this equilibrium to
design an appealing pricing mechanism that would enforce a unique Nash
equilibrium.
E. Nyberg (Helsinki University of Technology)
Scheduling based approaches for differentiating short and long
TCP flows
From queuing system studies, it is known that when the coefficient of
variance of the job distribution is greater than one, it is optimal to
use some form of scheduling that services short jobs before long ones.
(Depending on the definition of fairness this policy may, however, not
be fair.) The choice of the optimal scheduling policy depends mostly on
the knowledge on the job sizes.
We propose the use of TCP sequence numbers as information on the amount
of service a flow has obtained from the network. Assuming that sequence
numbers for each flow start from zero, if a packet has a small sequence
number it belongs to a flow that has received less total service time
than a flow whose packet has a large sequence number.
By ordering packets in the packet scheduler according to sequence
number, we are able on the flow level to service flows according to the
Foreground Background scheduling policy. There each flow is given a
quantum of service, and flows are serviced in a pre-emptive fashion in
the order of total quanta received from smallest total quanta to largest
total quanta.
Besides the FB scheduling policy, we present variants of FB, where it is
not necessary to order packets strictly by sequence number, but only
according to a given threshold, e.g. sequence number less than or more
than 10 packets.
All scheduling policies are studied on the packet level through
simulations and on the flow level through analytical studies on M/G/1
queues, with varying scheduling policy.
This is a joint work with U. Ayesta, K. Avrachenkov and P. Brown.
This page is maintained by k.avrachenkov@sophia.inria.fr