Université de Liège Réseau des Bibliothèques

BICTEL/e - ULg
Serveur institutionnel des thèses de doctorat



Nouvelles thèses
dans BICTEL/e - ULg
  • Ait Kaki, Asma - Recherche de nouvelles potentialités de bactéries du genre Bacillus pour l’agriculture et l’agroalimentaire
  • Dubois, Charline - Quels agritourismes pour les campagnes périurbaines ? Les cas de la Wallonie et du Grand-Duché de Luxembourg
  • Nibirantiza, Aboubacar - Sur les quantifications équivariantes en supergéométrie de contact
Présentation Recherche thèse Dépôt thèse Accès
gestionnaires
 
Page de résumé pour ULgetd-05292012-152102

Auteur : Cantin, François
E-mail de l'auteur : Francois.Cantin@ulg.ac.be
URN : ULgetd-05292012-152102
Langue : Français/French
Titre : Improving Overlay Routing scalability using an Internet Coordinate System
Intitulé du diplôme : Doctorat en sciences de l'ingénieur
Département : FSA - Département d'électricité, électronique et informatique
Jury :
Nom : Titre :
Bonaventure, Olivier Membre du jury/Committee Member
Dabbous, Walid Membre du jury/Committee Member
Donnet, Benoît Membre du jury/Committee Member
Fu , Xiaoming Membre du jury/Committee Member
Leduc, Guy Membre du jury/Committee Member
Mathy, Laurent Membre du jury/Committee Member
Boigelot, Bernard Président du jury/Committee Chair
Mots-clés :
  • routage / routing
  • système de coordonnées Internet / Internet coordinate system
  • réseaux informatiques / computer networks
  • réseau overlay / overlay network
Date de soutenance : 2012-07-02
Type d'accès : Public/Internet
Résumé :

Aujourd’hui de nombreuses applications communiquant en temps réel sont déployées

dans l’Internet : téléphonie IP, jeux vidéos en ligne, etc. Pour de telles applications, les

performances d’un chemin entre deux noeuds sont un point critique. En particulier, la

plupart de ces applications exigent que les délais entre les noeuds soient les plus petits

possible. Le problème est que le choix des routes dans l’Internet n’est généralement

pas basé sur les performances et il est bien connu que, pour de nombreux chemins dans

l’Internet, il existe un chemin alternatif proposant un délai plus court. Dans cette thèse,

notre objectif principal est de trouver ces chemins alternatifs.

Pour résoudre ce problème, une première solution est de remplacer les routes actuellement

utilisées dans l’Internet par des routes offrant de meilleures performances. Toutefois,

remplacer la philosophie de routage utilisée dans l’Internet semble très difficile,

voire impossible en pratique. Une autre solution consiste à laisser les routes actuelles

telles qu’elles sont et de réaliser du routage indirect. Considérons un chemin AB entre

deux noeuds A et B. Si un chemin ACB propose un délai plus court que AB, alors C est

un raccourci de routage pour AB. Dans ce cas, au lieu d’envoyer ses données directement

à B, A peut les envoyer à C et C peut les relayer vers B. Procéder de la sorte s’appelle

faire du routage overlay, car le routage est géré au sein d’un réseau overlay construit sur

l’Internet. Le principal problème du routage overlay est son coût : mesurer les caractéristiques

des chemins, échanger les résultats de ces mesures entre les noeuds et calculer les

meilleures routes, cela requiert énormément de ressources, et une telle approche peut difficilement

être envisagée à grande échelle. La contribution principale de cette thèse est la

proposition d’un mécanisme de routage overlay économe en ressources. Nous proposons

des critères basés sur les informations fournies par un système de coordonnées (ICS) afin

d’obtenir, avec un coût minimal, un ensemble de raccourcis de routage potentiels pour

n’importe quel chemin donné dans un réseau. Dans des réseaux constitués de centaines,

voire de milliers de noeuds, notre meilleur critère est en mesure de réduire le nombre de

raccourcis potentiels pour n’importe quel chemin donné à environ un ou deux pour cent

du nombre total de noeuds.

Cette thèse présente également des résultats plus généraux concernant les raccourcis

de routage et les ICS. Pour un ICS, un raccourci de routage est une violation du principe

d’inégalité triangulaire (TIV) et c’est un problème majeur. En effet, les TIV n’étant pas

modélisables dans un espace métrique, ils génèrent des erreurs d’estimation. Une étude

des TIV présents dans l’Internet et de leur impact sur l’ICS appelé Vivaldi nous a permis

d’aboutir à deux résultats. Premièrement, nous proposons des critères qui permettent

d’établir s’il existe un raccourci de routage pour un chemin donné. Deuxièmement, nous

proposons d’adopter une structure hiérarchique pour les ICS afin de réduire l’impact des

TIV sur ceux-ci. Finalement, dans cette thèse, nous étudierons l’efficacité de deux solutions

proposées dans la littérature afin d’éliminer la problématique des TIV pour les

ICS. La première consiste à appliquer des transformations non linéaires aux délais avant

d’essayer de les plonger dans un espace métrique. La seconde consiste à considérer le

problème de l’obtention des estimations comme un problème de complétion de matrice

afin d’éviter les désagréments liés au plongement dans un espace métrique./Nowadays lots of real time applications are used over the Internet: voice over IP, online

video games, etc. For these applications the performance of the path between two communicating

nodes is critical. Particularly, most of these applications require small delays

between communicating nodes. For these applications, the problem is that the choice of

the routes in the Internet is generally not very much guided by performance concerns. It

is well known that for lots of node pairs the default Internet path is suboptimal and there

exists an alternative path providing a smaller delay between these nodes. In this thesis,

we mainly address the problem of finding these alternative paths.

Replacing Internet’s routing philosophy in order to obtain default paths providing the

best performance possible should be a good theoretical solution. However, replacing

Internet’s routing philosophy by a brand new one is very difficult or even impossible in

practice. Another solution is to leave the default routes as they are and to perform indirect

routing. Consider a path AB between two nodes A and B. If a path ACB has a smaller

delay than AB, then, instead of sending data directly to B, A can send them to C and

C can relay them to B. This is called overlay routing because we manage the routing

in an overlay network built on top of the Internet (i.e. at the application level). Overlay

routing is a promising way to improve the quality of service in the Internet but its main

drawback is its poor scalability: measuring the characteristics of the paths, exchanging

the measurement results between the nodes and computing the best routes in the full

mesh overlay network generally implies a high consumption of resources. In this thesis,

our main contribution is the design of a lightweight one-hop overlay routing mechanism

improving the latencies: we define criteria that rely on the information provided by an

Internet Coordinate System (ICS) in order to provide a small set of potential one-hop

shortcuts for any given path in the network with small costs. Our best criterion does not

guarantee to find the best shortcut for any given path in a network but, even in networks

with hundreds or thousands of nodes, it will restrict the search for potential shortcuts to

about one or two percent of the total number of nodes.

Even if the estimation-based approach of overlay routing is our main contribution,

this thesis also presents general results about routing shortcuts and Internet Coordinate

Systems. For an ICS, a routing shortcut is a Triangle Inequality Violation (TIV) and it is

often a big problem. Indeed, a TIV will cause estimation errors since, in this particular

case, nodes cannot be embedded into any metric space. In this thesis, we study TIVs

existing in the Internet and their impact on the Vivaldi ICS. This analysis leads to two

contributions. Firstly, we propose criteria to establish, with a high probability of success,

if there exists a shortcut or not for a given path AB. Secondly, we propose a Two-Tier

architecture for ICSes that mitigates the effect of TIVs on the estimations. Finally, this

thesis also discusses the efficiency of two solutions proposed in the literature in order

to obtain an ICS that can deal with TIVs. The first one consists in applying non-linear

transformations to delays before trying to embed them in a metric space. The second one

consists in modelling the estimation problem as a matrix completion problem in order to

completely avoid the embedding in a metric space.

Autre version :
Fichiers :
Nom du fichier Taille Temps de chargement évalué (HH:MI:SS)
Modem 56K ADSL
[Public/Internet] Master-bk.pdf 6.01 Mb 00:14:18 00:00:32

Bien que le maximum ait été fait pour que les droits des ayants-droits soient respectés, si un de ceux-ci constatait qu'une oeuvre sur laquelle il a des droits a été utilisée dans BICTEL/e ULg sans son autorisation explicite, il est invité à prendre contact le plus rapidement possible avec la Direction du Réseau des Bibliothèques.


Parcourir BICTEL/e par Auteur|Département | Rechercher dans BICTEL/e


© Réseau des Bibliothèques de l'ULg, Grande traverse, 12 B37 4000 LIEGE