Algorithmes distribués pour la négociation de contrats de qualité de service dans les réseaux multi-domaines
Institution:
Rennes 1Disciplines:
Directors:
Abstract EN:
Deploying services (e. G. Video-conference) over the Internet X-domain topology requires guaranteeing an end-to-end QoS composed of several parameters. For this, QoS contracts are committed between domains. The key factors to consider are the heterogeneity, independence of domains and privacy of contracts. Before establishing a service, a negotiation occurs: it consists in selecting a chain of pair-wise commitments that satisfies the end-to-end QoS requirements and optimizes an objective function, given that global QoS is subject to accumulation effects (e. G. Delays sum up along a path). We address different negotiation problems. They reduce to knapsack problems, which are NP-Hard. Domain independence and contract privacy constrain us to design distributed solutions based on Dynamic Programming principles. We develop also self-repairing mechanisms in case of negotiation failures and contract violations. Negotiation per request can be slow. It may be preferable to pre-negotiate QoS contract chains. Thus, we address the problem of pipe negotiation: a domain asks for a number of connections satisfying a required QoS. We propose a network flow model and a distributed version of the Busacker-Gowen algorithm. We also consider the negotiation when several routes are explored to reach the target domain and describe some mechanisms to detect cycles and termination. Finally, we study negotiation in an "open world" where domains potentially organize themselves as cartels or coalitions.
Abstract FR:
Déployer des services (ex: vidéo-conférence) sur la topologie multi-domaines ("X-domaines") d'Internet implique de garantir la Qualité de Service (QdS) de bout-en-bout agrégeant plusieurs paramètres. Ainsi, des contrats de QdS sont établis entre domaines. Les éléments clés à prendre en compte sont l'hétérogénéité, l'indépendance des domaines et la confidentialité des contrats. Avant d'établir un service, un processus de négociation de la QdS s'exécute: il s'agit de la sélection de contrats pair-à-pair formant une chaîne satisfaisant une QdS de bout-en-bout (sujette à des effets d'accumulations: les délais s'additionnent, les disponibilités se multiplient, etc. ) et optimisant une fonction objectif. Nous étudions différents problèmes de négociation. Ces problèmes se réduisent à des problèmes de "sac à dos", qui sont NP-difficiles. Nous proposons des algorithmes distribués utilisant la Programmation Dynamique et fournissons également des mécanismes d'auto-réparation en cas d'échec ou de violations de contrats. Négocier chaque requête peut s'avérer un processus lent. Il peut être préférable de pré-négocier des chaînes de contrats. Ainsi, nous considérons le problème de la négociation de tuyaux: un domaine sollicite un nombre de connexions pour une QdS requise. Nous proposons un modèle de flots et une version distribuée de l'algorithme de Busacker-Gowen pour résoudre ce problème. En outre, nous étudions la négociation avec exploration de plusieurs routes pour atteindre le domaine cible et y répondons par des mécanismes de détection de cycles et de terminaison. Enfin, nous discutons de l'application de la négociation en "milieu ouvert" où les domaines s'organisent éventuellement en cartels ou coalitions.