Faculté informatique et communications IC, Section des systèmes de communication, Institut de systèmes de communication ISC (Laboratoire pour les communications informatiques et leurs applications 2 LCA2)

Bits of Internet traffic control

Vojnovic, Milan ; Le Boudec, Jean Yves (Dir.)

Thèse sciences techniques Ecole polytechnique fédérale de Lausanne EPFL : 2003 ; no 2827.

Ajouter à la liste personnelle
    Summary
    In this work, we consider four problems in the context of Internet traffic control. The first problem is to understand when and why a sender that implements an equation-based rate control would be TCP-friendly, or not—a sender is said to be TCP-friendly if, under the same operating conditions, its long-term average send rate does not exceed that of a TCP sender. It is an established axiom that some senders in the Internet would need to be TCP-friendly. An equation-based rate control sender plugs-in some on-line estimates of the loss-event rate and an expected round-trip time in a TCP throughput formula, and then at some points in time sets its send rate to such computed values. Conventional wisdom held that if a sender adjusts its send rate as just described, then it would be TCP-friendly. We show exact analysis that tells us when we should expect an equation-based rate control to be TCP-friendly, and in some cases excessively so. We show experimental evidence and identify the causes that, in a realistic scenario, make an equation-based rate control grossly non-TCP-friendly. Our second problem is to understand the throughput achieved by another family of send rate controls—we termed these "increase-decrease controls," with additive-increase/multiplicative-decrease as a special case. One issue that we consider is the allocation of long-term average send rates among senders that adjust their send rates by an additive-increase/multiplicative-decrease control, in a network of links with arbitrary fixed routes, and arbitrary round-trip times. We show what the resulting send rate allocation is. This result advances the state-of-the-art in understanding the fairness of the rate allocation in presence of arbitrary round-trip times. We also consider the design of an increase-decrease control to achieve a given target loss-throughput function. We show that if we design some increase-decrease controls under a commonly used reference loss process—a sequence of constant inter-loss event times—then we know that these controls would overshoot their target loss-throughput function, for some more general loss processes. A reason to study the design problem is to construct an increase-decrease control that would be friendly to some other control, TCP, for instance. The third problem that we consider is how to obtain probabilistic bounds on performance for nodes that conform to the per-hop-behavior of Expedited Forwarding, a service of differentiated services Internet. Under the assumption that the arrival process to a node consists of flows that are individually regulated (as it is commonplace with Expedited Forwarding) and the flows are stochastically independent, we obtained probabilistic bounds on backlog, delay, and loss. We apply our single-node performance bounds to a network of nodes. Having good probabilistic bounds on the performance of nodes that conform to the per-hop-behavior of Expedited Forwarding, would enable a dimensioning of those networks more effectively, than by using some deterministic worst-case performance bounds. Our last problem is on the latency of an input-queued switch that implements a decomposition-based scheduler. With decomposition-based schedulers, we are given a rate demand matrix to be offered by a switch in the long-term between the switch input/output port pairs. A given rate demand matrix is, by some standard techniques, decomposed into a set of permutation matrices that define the connectivity of the input/output port pairs. The problem is how to construct a schedule of the permutation matrices such that the schedule offers a small latency for each input/output port pair of the switch. We obtain bounds on the latency for some schedulers that are in many situations smaller than a best-known bound. It is important to be able to design switches with bounds on their latencies in order to provide guarantees on delay-jitter.
    Résumé
    Le présent travail traite de quatre problèmes relatifs au contrôle de trafic sur Internet. Le premier problème est de comprendre quand et pourquoi une source utilisant un contrôle de flux régi par équation est-elle "TCP-friendly" (une source est dite TCP-friendly si dans les mêmes conditions, son débit à long terme ne dépasse pas celui d'une source utilisant TCP). Il est par ailleurs établi que pour éviter la congestion, certaines sources doivent être TCP-friendly. Le contrôle de flux régi par équation fonctionne de la manière suivante: la source estime le taux de perte de paquets ainsi que leur temps de parcours. Elle calcule à l'aide des ces paramètres le débit qu'une source TCP aurait dans ces conditions, et ajuste son propre débit selon le résultat. Ce travail propose une analyse exacte de ce mécanisme et prédit quand la source sera effectivement TCP-friendly. Des preuves expérimentales montrent que dans des cas réalistes, ce type de sources peut grossièrement différer d'une source TCP. Le deuxième problème concerne une autre famille de contrôles de flux, dite "increase-decrease", dont un cas particulier est l'incrément additif/décrément multiplicatif. Il s'agit ici de calculer le débit moyen à long terme de plusieurs sources concurrentes utilisant ce dernier type de mécanisme, dans un réseau arbitraire où les chemins sont fixés et les temps de parcours connus. Nous montrons quelle répartition des ressources en résulte. Ce résultat est un progrès certain dans la compréhension de la répartition équitable de ressources dans un réseau où les délais sont arbitraires. Un autre problème consiste à concevoir un mécanisme "increase-decrease" qui réalise une certaine fonction débit/taux de perte. Il est montré dans ce travail que si la conception est faite en utilisant un processus de pertes usuel (une séquence d'intervalles constantes entre les pertes), le mécanisme sort de son objectif pour un processus de perte plus général. La motivation pour étudier le problème de conception est de créer un mécanisme "increase-decrease" qui soit TCP-friendly. Le troisième problème consiste à obtenir des bornes probabilistes à la performance de noeuds qui se conforment au comportement spécifié dans "Expedited Forwarding", un service différencié d'Internet. Sous l'hypothèse que le processus d'arrivée à un noeud est formé de flots régulés individuellement — c'est un lieu commun dans Expedited Forwarding — et que les flux sont stochastiquement indépendants, des bornes à la taille et à la durée de la file d'attente à un noeud, ainsi qu'au taux de perte, sont calculées. Ces bornes permettent un dimensionnement plus efficace que des bornes déterministes calculées pour le pire des cas. Le quatrième et dernier problème est de calculer le temps de réponse d'un commutateur (switch) avec attente en entrée et utilisant un planificateur à décomposition (decomposition-based scheduler). Partant d'une certaine matrice de demande (contenant le débit à atteindre entre chaque paire de ports), le planificateur décompose cette matrice en un ensemble de matrices de permutations qui décrivent les connections entre les ports. La difficulté est de construire une suite de permutations telle que le temps de réponse soit faible pour chaque paire entrée-sortie. De nouvelles bornes sur ce temps de réponse sont proposées, qui sont, dans bien des cas, meilleures que les bornes connues. Il est utile de concevoir des commutateurs à temps de réaction borné pour obtenir des garanties sur les délais et la gigue.