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)

The provision of a low delay service within the best-effort Internet

Hurley, Paul ; Le Boudec, Jean Yves (Dir.)

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

Ajouter à la liste personnelle
    Summary
    In this work, we define a novel Internet service, called ABE (Alternative Best-Effort), which allows interactive multimedia applications to receive low queuing delay within the existing best-effort Internet. We then develop and analyse a number of innovative scheduling algorithms that can implement ABE in a router. ABE differs from other services that provide low queuing delay in that it does not rely on any reservation and requires no charging of those that avail of the low delay service. We retain the best-effort context by protecting traffic that does not require lower delay for individual packets so that the existence of ABE is transparent to them, namely their performance is at least as good as it would be in the current best-effort Internet. The primary scheduler to implement ABE we developed is called DSD (Duplicate Scheduling with Deadlines). It guarantees that traffic marked as low-delay will spend no longer in the system of each router than some operator specified value. The performance of other traffic is protected by the use of a virtual queue, a packet deadline decision based mechanism and a controller. We prove important properties of DSD and show, by the tools of queuing analysis and simulation, that it succeeds in its goal: protecting the performance of other traffic and the best possible performance for low-delay traffic subject to the constraints of not exceeding the maximum permitted delay. The final part of this work addresses the question: what is the resultant long-term distribution of rates amongst flows, with equal round-trip times in a general network, that update their rates by the additive increase/multiplicative decrease algorithm? Contrary to what was previously believed, we find that the rate allocation is not proportionally fair, but is more closely represented by an allocation we derive.
    Résumé
    Dans ce travail, nous définissons un nouveau service pour l'Internet. Il permet aux applications multimédias interactives de bénéficier d'un faible délai d'attente dans le contexte actuel "best-effort" (meilleur service possible) de l'Internet. Nous développons et analysons plusieurs algorithmes d'ordonnancement et de service des paquets, capable d'implémenter ABE dans un routeur. Contrairement aux autres services offrant un faible délai d'attente, ABE ne requiert ni réservation, ni facturation de frais supplémentaires à ses utilisateurs. Le contexte du best-effort est maintenu en protégeant, au niveau paquet, le trafic qui ne requiert pas un faible délai d'attente. La performance de cette classe de trafic est au moins aussi bonne avec ABE que dans l'Internet actuel. Ainsi, tout en procurant aux utilisateurs qui le souhaitent un faible délai d'attente, ABE est transparent aux autres utilisateurs qui souhaitent conserver le service actuel. Le principal algorithme d'ordonnancement et service réalisant ABE que nous avons développé est appelé DSD (Duplicata Scheduling with Deadlines). Il garantit que la classe de trafic marquée pour le service à bas délai ne séjournera pas dans un routeur plus longtemps qu'une valeur spécifiée par le vendeur. Les performances de l'autre classe de trafic sont préservées à un niveau au moins aussi élevé que celui qui aurait été atteint si ABE n'était pas implémenté dans ce routeur, grâce à l'utilisation d'une file virtuelle, d'un serveur basant ses décisions sur les échéances auxquelles les paquets doivent avoir quitté le routeur, et d'un régulateur. Nous établissons des propriétés importantes du DSD. En utilisant des outils de théorie des files d'attente et de simulation, nous montrons que cet algorithme remplit son objectif: la meilleure performance possible pour le trafic à faible délai est atteinte, tout en garantissant un délai maximum fixé pour cette classe de trafic et un service au moins aussi bon que si ABE n'était pas déployé pour l'autre classe de trafic. La dernière partie de ce travail répond à la question suivante: dans un réseau dont les flots mettent à jour leurs taux de transmission par un algorithme de croissance additive/décroissance multiplicative, quelle est, à long terme, la distribution des taux alloués à chacun, dans le cas où leurs temps d'aller-retour dans le réseau sont identiques ? Contrairement à l'opinion admise jusqu'à présent, nous trouvons que cette distribution n'est pas proportionnellement équitable, mais se rapproche davantage d'un nouveau type d'allocation intermédiaire entre équité proportionnelle et équité max-min.