Resource management for virtualized networks

Quttoum, Ahmad (2011). Resource management for virtualized networks. Thèse de doctorat électronique, Montréal, École de technologie supérieure.

Prévisualisation

PDF Télécharger (7MB) | Prévisualisation

Résumé

Network Virtualization has emerged as a promising approach that can be employed to efficiently enhance the resource management technologies. In this work, the goal is to study how to automate the bandwidth resource management, while deploying a virtual partitioning scheme for the network bandwidth resources. Works that addressed the resource management in Virtual Networks are many, however, each has some limitations. Resource overwhelming, poor bandwidth utilization, low profits, exaggeration, and collusion are types of such sort of limitations. Indeed, the lack of adequate bandwidth allocation schemes encourages resource overwhelming, where one customer may overwhelm the resources that supposed to serve others. Static resource partitioning can resist overwhelming but at the same time it may result in poor bandwidth utilization, which means less profit rates for the Internet Service Providers (ISPs). However, deploying the technology of autonomic management can enhance the resource utilization, and maximize the customers’ satisfaction rates. It also provides the customers with a kind of privilege that should be somehow controlled as customers, always eager to maximize their payoffs, can use such a privilege to cheat. Hence, cheating actions like exaggeration and collusion can be expected. Solving the aforementioned limitations is addressed in this work.

In the first part, the work deals with overcoming the problems of low profits, poor utilization, and high blocking ratios of the traditional First Ask First Allocate (FAFA) algorithm. The proposed solution is based on an Autonomic Resource Management Mechanism (ARMM). This solution deploys a smarter allocation algorithm based on the auction mechanism. At this level, to reduce the tendency of exaggeration, the Vickrey-Clarke-Groves (VCG) is proposed to provide a threat model that penalizes the exaggerating customers, based on the inconvenience they cause to others in the system. To resist the collusion, the state-dependent shadow price is calculated, based on the Markov decision theory, to represent a selling price threshold for the bandwidth units at a given state.

Part two of the work solves an expanded version of the bandwidth allocation problem, but through a different methodology. In this part, the bandwidth allocation problem is expanded to a bandwidth partitioning problem. Such expansion allows dividing the link’s bandwidth resources based on the provided Quality of Service (QoS) classes, which provides better bandwidth utilization. In order to find the optimal management metrics, the problem is solved through Linear Programming (LP). A dynamic bandwidth partitioning scheme is also proposed to overcome the problems related to the static partitioning schemes, such as the poor bandwidth utilization, which can result in having under-utilized partitions. This dynamic partitioning model is deployed in a periodic manner. Periodic partitioning provides a new way to reduce the reasoning of exaggeration, when compared to the threat model, and eliminates the need of the further computational overhead.

The third part of this work proposes a decentralized management scheme to solve aforementioned problems in the context of networks that are managed by Virtual Network Operators (VNOs). Such decentralization allows deploying a higher level of autonomic management, through which, the management responsibilities are distributed over the network nodes, each responsible for managing its outgoing links. Compared to the centralized schemes, such distribution provides higher reliability and easier bandwidth dimensioning. Moreover, it creates a form of two-sided competition framework that allows a double-auction environment among the network players, both customers and node controllers. Such competing environment provides a new way to reduce the exaggeration beside the periodic and threat models mentioned before. More important, it can deliver better utilization rates, lower blocking, and consequently higher profits.

Finally, numerical experiments and empirical results are presented to support the proposed solutions, and to provide a comparison with other works from the literature.

Résumé traduit

La virtualisation des ressources a émergé comme une approche prometteuse qui peut être employée pour améliorer l’efficacité des technologies de gestion des ressources dans un réseau. Ainsi, dans ce travail, l’objectif est d’étudier comment automatiser la gestion de la bande passante dans un réseau, tout en utilisant un schéma de partitionnement virtuel des ressources. Dans la littérature plusieurs travaux de recherche ont abordé la gestion des ressources dans le contexte des réseaux virtuels privés, mais chacun a ses limites. Un partage non équitable des ressources, une faible utilisation de la bande passante disponible, faibles profits, l’exagération, et la collusion sont tous des exemples de ces limitations. En effet, l’absence des systèmes capables de garantir un partage équitable de la bande passante entre les utilisateurs, encourage l’exagération en besoin des ressources. C’est-à-dire, un client peut monopoliser les ressources qui sont censées servir les autres utilisateurs. Un partitionnement statique des ressources peut limiter le problème d’exagération, toutefois il peut en résulter une mauvaise utilisation de la bande passante, ce qui signifie des profits moindres pour les fournisseurs de services réseau virtuel. Cependant, le déploiement d’une technologie de gestion de bande passante autonome peut améliorer l’utilisation des ressources, et maximiser le taux de satisfaction des clients. Une telle technologie peut fournit également aux clients une sorte de privilège qui peut être utiliser pour tricher. Ainsi, des actions de tricherie comme la collusion et l’exagération peuvent être adopter par certains clients. Résoudre des telles problèmes est aussi abordé dans ce travail.

Dans la première partie de cette thèse, nous nous proposons de résoudre les problèmes de la mauvaise utilisation de la bande passante, des faibles profits pour les fournisseurs de services et les taux de blocage élevés rencontré dans l’approche traditionnelle "Premier arrivé premier servie " (FAFA) . La solution proposée est basée sur un mécanisme de gestion des ressources Autonome (ARMM). Cette solution déploie un algorithme intelligent d’allocation de la bande passante basé sur le mécanisme de vente aux enchères. Pour réduire la tendance de l’exagération, nous proposons d’utiliser la technique Vickrey-Clarke-Groves (VCG), qui consiste en un modèle de menace qui pénalise les clients qui exagèrent leurs besoins en bande passante. La pénalité pour chaque client qui exagère son besoin en bande passante est calculée en se basant sur les désagréments qu’il cause à autrui dans le système. Pour résister à la collusion entre clients, nous proposons de calculer un prix fictif seuil dépendant de l’état du système et en se basant sur la théorie de décision de Markov. En effet, nous calculons pour chaque état du système un seuil de prix de vente pour chaque unité de la bande passante disponible dans le réseau. Tout client offrant un prix de vente par unité de bande passante inférieure au seuil calculé est automatiquement bloqué et ne peut utiliser les ressources du réseau.

Dans la deuxième partie de cette thèse, nous nous proposons de résoudre une version élargie du problème d’allocation de la bande passant dans un réseau virtuel privé, et en utilisant une méthodologie différente. Le problème d’allocation de la bande passante est étendu à un problème de partitionnement. Une telle expansion permet de calculer la répartition optimale de la bande passante de chacun des liens du réseau entre les différentes classes de service et de fournir une meilleure utilisation des ressources du réseau. Afin de trouver les paramètres d’une gestion optimale des ressources d’un réseau virtuel privé, le problème est résolu par les techniques de la programmation linéaire (LP). Un schéma de partitionnement dynamique de bande passante est également proposé pour surmonter les problèmes liés au partitionnement statique des ressources telle que un faible taux d’utilisation de la bande passante disponible, qui peut résulter en des partitions sous-utilisées. Ce modèle de partitionnement dynamique est déployé d’une manière périodique. Un partitionnement périodique fournit une nouvelle façon de réduire le raisonnement de l’exagération, par rapport au modèle basé sur la menace de payer une pénalité relative au désagrément posé à autrui. Nous réduisons ainsi le coût lié au calcul de cette pénalité.

Dans la troisième partie de cette thèse, nous proposons un système de gestion décentralisé pour résoudre les problèmes mentionnés ci-dessus dans le contexte des réseaux virtuels privés gérés par des opérateurs des réseaux (VNOs).Cette décentralisation permet le déploiement d’un niveau supérieur de la gestion autonome des ressources du réseau, à travers lequel, les responsabilités de gestion sont répartis sur les nuds du réseau, chacun étant responsable de la gestion de ses liens sortants. Comparé aux architectures centralisées, une telle distribution permet une plus grande fiabilité et un dimensionnement de la bande passante plus facile et plus efficace. En outre, il crée un cadre de la concurrence à deux faces qui permet une double vente aux enchères parmi les acteurs du réseau, les clients et les contrôleurs des nuds du réseau. Un tel environnement de compétition offre une nouvelle façon de réduire l’exagération comparée au modèle périodique basé sur la menace de payer une pénalité. Mieux encore, ce nouveau modèle peut offrir des meilleurs taux d’utilisation, un taux de blocage moins élevé et par conséquent des profits pour le fournisseur de service plus importants.

Enfin, des simulations numériques et des résultats empiriques sont présentés pour soutenir les solutions proposées, et fournir une comparaison plus éclairée avec d’autres modèles qui ont été proposés dans la littérature.

Type de document:	Mémoire ou thèse (Thèse de doctorat électronique)
Renseignements supplémentaires:	"Manuscript-based thesis presented to École de technologie supérieure in partial fulfillment of the requirements for the degree of doctor of philosophy" Bibliogr. : f. [139]-145.
Mots-clés libres:	Réseaux d'ordinateurs. Réseaux d'ordinateurs Gestion Automatisation. Théorie des jeux. Processus de Markov. Prise de décision. Programmation linéaire. ARMM, Bande, FAFA, Fournisseur, Nud, Partitionnement, Passant, Privé, Service, VCG, Virtualisation, VNO, Virtuel, Gestion, Méchanisme, Design.
Directeur de mémoire/thèse:	Directeur de mémoire/thèse Dziong, Zbigniew
Codirecteur:	Codirecteur Hadi, Otrok
Programme:	Doctorat en génie > Génie
Date de dépôt:	10 nov. 2011 16:56
Dernière modification:	28 févr. 2017 21:29
URI:	https://espace.etsmtl.ca/id/eprint/934

Gestion Actions (Identification requise)

Dernière vérification avant le dépôt