The list of MISTRAL seminars:

Abstracts of presentations:

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