Because of its decentralized nature and the lack of the required cooperations among the Internet autonomous systems, the current Internet is unable to provide end-to-end QoS guarantees to the application layer. The Service Overlay Network (SON) is a proposed solution to this end-to-end QoS provisioning problem. With its special overlay structure,the Service Overlay Network is able to provide reliable end-to-end QoS support on top of the Internet infrastructure. By considering the SON as a network with virtual connections and bandwidth allocations, we derive a series of new results for the SON. First, by referring to the reliability theory, we obtain a general form for the end-to-end blocking function. With the general blocking function, we investigate the two optimization approaches for designing a SON, namely the Maximum Profit (MP) approach that maximizes the prot and the Minimum Cost (MC) approach that minimizes the investment. Our study reveals that though the two approaches have been shown to be equivalent in many other settings, they are different in the SON environment. Our result indicates that the MP approach is a more appropriate approach for designing a SON, and the result is independent of the routing algorithm employed. Second, we develop a novel event dependent routing scheme that is efficient enough to be incorporated into the optimal capacity allocation problem. This allows the SON design problem to be formulated and solved as a MP optimization problem. Then we improve the optimization methodology by decomposing the main SON design problem into a number of sub-problems and we solve the main design problem by solving the sub-problems which involve finding the link shadow prices of the network links. It is exactly because we are using the maximum profit approach, the idea of link shadow price could be incorporatedto solve the design problem. A fast macro-state convolution scheme based on the link shadow price is developed to provide a traffic differentiation module to the optimization formulation. This additional module allows the optimization framework consider traffic connections based on the (monetary) contributions they offer to the network. Like many other telecommunications services, SON is believed to exhibit positive net-work externalities - once the network reaches a "critical mass", it will continue to grow in a self-reinforcing manner. The optimal pricing of the SON services is therefore another crucial piece of information for the SON to achieve success. We study a set of Lagrange i imultipliers and show that the SON service charges are closely related to the set of multipliers. When the service levels are not hard requirements, by using the multipliers as the service charges, the resulting network will be on the Pareto frontier of a multi-criteria optimization problem that maximizes both the operator utility and the user utility. This piece of work provides information from the problem formulation, to the actual design process, to the simplication and enhancement of the design process, and finally to the set of optimal prices which the operator could charge. It essentially provides comprehensive information for deploying the SON network. / En raison de son caractere decentralise et le manque de cooperations necessaires entre les l'Internet des systemes autonomes, l'Internet actuel est incapable de fournir de bout en bout QoS garantit a la couche application. L'Overlay Service Network (SON) est une solution proposee a ce QoS de bout-en-bout probleme. Grace a sa structure speciale de recouvrement, l'Overlay Service Network est en mesure de fournir des informations ables de bout en bout la qualite de service support au-dessus de l'infrastructure Internet. En considerant la SON en reseau avec des connexions virtuelles et la bande passante allocations, nous obtenons une serie de nouveaux resultats pour le SON. Tout d'abord, en se referant a la theorie de la abilite, nous obtenons une forme generale pour la fin-en-bout fonction de blocage. Avec l'general fonction de blocage, nous examinons les deux approches d'optimisation pour la conception une SON, soit le maximum Profit (MP) approche qui maximise le profit et le Cout minimum (MC) approche qui minimise l'investissement. Notre etude revele que si les deux approches se sont revelees etre l'equivalent dans de nombreux autres parametres, ils sont differents dans l'environnement SON. Nos resultats montrent que l'approche MP est une approche plus appropriee pour la conception d'un SON, et le resultat est independant de l'algorithme de routage utilise. Deuxiemement, nous developpons un nouvel evenement depend regime de routage qui est assez efficace pour etre incorpores dans le probleme d'allocation de la capacite optimale. Cela permet au probleme de conception Fils pour etre formule et resolu comme un probleme d'optimisation MP. Ensuite, nous avons d'ameliorer la methodologie d'optimisation en decomposant le probleme de conception principale fils dans un certain nombre de sous problemes et nous resolvons le probleme de conception principale en resolvant les problemes sous-qui impliquent la constatation du prix fictifs lien des liens du reseau. C'est justement parce que nous utilisons la recherche du profit maximum, l'idee de prix fictif lien pourrait etre constituee pour resoudre le probleme de conception. Un schema de convolution rapide macro-etat base sur le prix fictif lien est developpe pour fournir une differenciation du trafic module d'optimisation de la formulation. Ce module additionnel permet l'optimisation examiner le cadre des connexions de trafic sur la base des contributions (monetaires), ils offrent au reseau. Comme beaucoup d'autres services de telecommunications, SON est estime a exposer nette positive externalites de travail - une fois que le reseau atteint une "masse critique", il va continuer a croitre dans un auto-renforcement maniere. La tarification optimale des services de SON est donc un autre element crucial de l'information pour le SON pour reussir. Nous etudions une serie de multiplicateurs Lagrange et montrent que les frais de service SON sont etroitement liees a l'ensemble des multiplicateurs. Lorsque les niveaux de service ne sont pas des exigences dur, en utilisant les multiplicateurs que les frais de service, le reseau qui en resulte sera sur la frontiere de Pareto d'un probleme d'optimisation multi-criteres qui maximise la fois l'utilite operateur et l'utilite de l'utilisateur. Ce travail fournit des informations a partir de la formulation du probleme, a l'actuel la conception de processus, de la simplification et l'amelioration du processus de conception, et enfin a l'ensemble des prix optimal o l'operateur peut charger. Il fournit essentiellement des informations completes pour le deploiement du reseau SON. Ce travail fournit des informations a partir de la formulation du probleme, a l'actuel la conception de processus, de la simplification et l'amelioration du processus de conception, et enfn a l'ensemble des prix optimal o l'operateur peut charger. Il fournit essentiellement des informations completes pour le deploiement du reseau SON.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.103599 |
| Date | January 2011 |
| Creators | Lam, Ngok |
| Contributors | Lorne Mason (Supervisor1), Zbigniew Dziong (Supervisor2) |
| Publisher | McGill University |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Format | application/pdf |
| Coverage | Doctor of Philosophy (Department of Electrical and Computer Engineering) |
| Rights | All items in eScholarship@McGill are protected by copyright with all rights reserved unless otherwise indicated. |
| Relation | Electronically-submitted theses. |
Page generated in 0.0071 seconds