Adaptation de capacité dans le réseau dédié de service pour la maximisation du bénéfice

Tran, Côn (2011). Adaptation de capacité dans le réseau dédié de service pour la maximisation du bénéfice. Thèse de doctorat électronique, Montréal, École de technologie supérieure.

Prévisualisation	PDF Télécharger (1MB) | Prévisualisation
Prévisualisation	PDF Télécharger (769kB) | Prévisualisation

Résumé

Les réseaux dédiés de service (Service Overlay Network – SON) sont formés en plaçant des noeuds dédiés dans l’Internet et en les reliant par des liens dédiés établis avec de la bande passante, incluant garantie de Qualité de Service (QoS), achetée d’une multitude de Systèmes Autonomes Internet (AS). La bande passante est obtenue par accords de niveau de service (Service Level Agreement – SLA) avec les fournisseurs de service Internet qui sont propriétaires des AS. Par sa couverture sur la multitude de AS, le SON peut alors fournir la QoS de bout en bout aux connexions de services en temps réel qu’il admet.

La quantité de largeur de bande achetée a un effet à la fois sur le trafic admis et sur le coût du réseau, affectant ainsi le bénéfice de l’opérateur du réseau. Cela donne à ce dernier la possibilité d’optimiser son bénéfice en adaptant ses ressources de réseau aux conditions changeantes de la demande de trafic et des coûts de SLA. Deux éléments sont requis pour réaliser l’optimisation : une méthode efficace d’estimation en temps réel de la demande de trafic, et une approche d’adaptation de capacité optimale qui sera alimentée par l’estimation de la demande. Dans cette thèse, nous proposons des nouvelles approches pour répondre à ces besoins identifiés.

Notre approche d’adaptation de capacité maximise le bénéfice du réseau en changeant lorsque requis les termes des SLA, afin d’adapter l’attribution de la largeur de bande des liens dédiés à de fréquentes estimations de demande de trafic. Pendant que s’effectue l’adaptation de capacité, le degré de service du réseau, spécifié par des contraintes de blocage de connexions, doit être maintenu. En s’appuyant sur un modèle économique, l’adaptation des ressources de lien est intégrée à la politique de contrôle d’admission de connexions (CAC) et de routage en vigueur dans le réseau. Dans notre approche, nous proposons d’appliquer une politique de CAC et routage, fondée sur la théorie de décision de Markov, qui maximise la récompense du réseau, bien que d’autres politiques de routage soient aussi applicables. L’intégration mène à un algorithme itératif et distribué d’adaptation de capacité de lien, où la sensibilité du bénéfice du réseau aux dimensions de lien est calculée à partir de la moyenne du shadow price de lien, qui lui-même constitue un paramètre du routage.

Des approches d’estimation en temps réel de tendance de demande de trafic, fondée sur des mesures et convenant bien à l’adaptation de capacité du SON, sont ensuite proposées. Dans la première approche, le paramètre du modèle de lissage exponentiel (Exponential Smoothing – ES) est adapté à la tendance de trafic. La tendance dans ce cas est estimée en utilisant les fonctions d’autocorrélation et de distribution cumulée de mesures de taux d’arrivées de connexion. La deuxième approche applique un filtre de Kalman dont le modèle est construit à partir de données historiques de trafic. Dans ce dernier cas, la disponibilité de la distribution de l’erreur d’estimation dans l’algorithme du filtre permet d’élaborer une méthode qui améliore le contrôle du degré de service durant l’adaptation de capacité.

L’analyse ainsi que la simulation des modèles proposés ont été effectuées pour évaluer la performance des approches. La maximisation du bénéfice du réseau par l’approche d’adaptation de capacité est confirmée avec une étude analytique d’exemples de petits réseaux. Ensuite, la simulation d’exemples réalistes de réseau démontre les meilleurs bénéfices et/ou degré de service obtenus par notre approche d’adaptation de capacité, quand on la compare à l’attribution fixe de capacités de liens.

L’étude de l’estimation de demande de trafic montre que la performance de l’adaptation de capacité est améliorée par l’usage de nos méthodes proposées. Les méthodes adaptatives procurent des bénéfices plus élevés que celles à paramètre fixe. L’estimation par lissage exponentiel adaptée par autocorrélation donne la meilleure performance combinée réponsestabilité, quand on la compare aux autres lissages exponentiels. Enfin, les approches fondées sur filtre de Kalman améliorent l’adaptation de capacité, démontrant des réductions significatives de l’augmentation du blocage du réseau quand la demande de trafic augmente.

Titre traduit

Service overlay network capacity adaptation for profit maximization

Résumé traduit

Service Overlay Networks (SON) are formed by placing overlay nodes over the Internet and interconnecting them with overlay links established by leasing bandwidth with Quality of Service (QoS) guarantees from a multitude of Internet Autonomous Systems (AS). Bandwidth is leased through service level agreements (SLA) with Internet Service Providers owning the AS. By covering a multitude of AS, the SON can provide end-to-end QoS to real time service connections serviced by its network.

The amount of leased bandwidth influences both the admitted traffic and network cost, affecting the network profit. This gives the network operator the opportunity to optimize the profit by adapting the network resources to changing traffic and SLA cost conditions. To realize this optimization, two elements are required: an efficient real time estimation of traffic demand, and an optimal capacity adaptation that will be fed by the demand estimation. In this thesis, we propose novel approaches that address the mentioned elements.

The approach for capacity adaptation maximizes network profit by modifying the SLA terms as needed to adapt overlay links bandwidth allocation to frequently updated traffic demand estimates. While performing capacity adaptation, the network Grade of Service, specified by connection blocking constraints, must also be maintained.

Using an economic model, the link resources adaptation is integrated with the connection admission control (CAC) and routing policy in effect in the network. In our proposal, we apply a reward maximizing CAC and routing policy that is derived from the Markov Decision Process theory, although the approach can be applied to other routing policies. This integration leads to a distributed iterative algorithm for link bandwidth adaptation, where network profit sensitivity to link dimensions is calculated from the average link shadow price, itself being a routing parameter.

Approaches for measurement-based online traffic trend estimation that fit the SON capacity adaptation are next proposed. In the first approach, the smoothing parameter of the exponential smoothing (ES) model is adapted to the traffic trend. Here, the trend is estimated using measured connection arrival rate autocorrelation or cumulative distribution functions. The second approach applies a Kalman filter whose model is built from historical traffic data. In this case, availability of the estimation error distribution provided by the filter algorithm allows for better control of the network Grade of Service during capacity adaptation.

Analytical models as well as simulation of measurement based implementations of the proposed models are used to evaluate the performance of the proposed approach. Profit maximization by the capacity adaptation approach is confirmed by analysis of small network examples. Simulations on realistic network examples demonstrates higher network profit and/or better Grade of Service obtained by our adaptation proposal, when compared to fixed link capacities.

Study of traffic demand estimation methods shows that capacity adaptation performance is further improved with the use of our proposed methods. Adaptive estimation, as compared to fixed parameter estimation, provided higher profits. The proposed autocorrelation based ES estimation gives the best combined response and stability performances when compared to known ES methods. The proposed Kalman filter based approach improves capacity adaptation performance by significantly limiting network blocking increase when traffic demand increases.

Type de document:	Mémoire ou thèse (Thèse de doctorat électronique)
Renseignements supplémentaires:	"Thèse présentée à l'École de technologie supérieure comme exigence partielle à l'obtention du doctorat en génie" Bibliogr. : f. [104]-111.
Mots-clés libres:	Points d'interconnexion Internet. Qualité de service. Circulation Estimation. Processus de Markov. Kalman, Filtre de. Adaptation, AS, Bande, Bénéfice, CAC, Capacité, Dédié, Gestion, Maximisation, Passant, Réseau, Ressource, Service, SLA, SON, Trafic, Décision
Directeur de mémoire/thèse:	Directeur de mémoire/thèse Dziong, Zbigniew
Programme:	Doctorat en génie > Génie
Date de dépôt:	02 nov. 2011 20:33
Dernière modification:	02 mars 2017 01:17
URI:	https://espace.etsmtl.ca/id/eprint/928

Gestion Actions (Identification requise)

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