Grant: Discovery Grants Program - Individual
Université du Québec à Montréal
$17,000.00
Optimal resource allocation of virtualized router: a multi-objective approach
FY 2014-15
Summary
With the venue of the cloud and the large virtualized data centers, there is a huge need to provide new traffic isolation services between virtualized domains on the network. Unfortunately, the isolation available today is mainly based on the management plane and control plane and is not embedded with the data plane. This newlevel of isolation will require to revisit the resource allocation strategies and redesign the network nodes (switches and routers). The targeted resources include the packet processing such as network processors, dedicated processors and multicore processors, memories such as TCAM, SRAM, etc., and interfaces such as Ethernet, etc.Traditionally, the resource allocation strategies tried to maximize the global utility to guarantee performance and quality of service on packets. The aim of this research project is to push the sliceability on those node and ensure fairness between slices. The maximization problem is extended with new constraints that require the extension of the strategies, frameworks and algorithms related to resource allocation. The proposed research aims at solving this problem using an innovative combination of multiple approaches: Game Theory, Control Theory, Stochastic Optimization and Network Calculus. The Game Theory will be used to develop a fair distributed algorithm for resource allocation between slices. To achieve a fair allocation, we will develop a framework based on cooperative and non-cooperative game theory. For the cooperative approach, the Nash bargaining solution will be used to solve the centralized problem. We will then propose a distributed algorithm for implementing the optimal and fair resource allocation and provide conditions for its convergence.On the other hand, the Stochastic Network Utility Maximization (NUM) is used to model a significantly large array of resource allocation problems and is well-adapted to the slicing router context. The utility function will depend on rate, latency, jitter, energy, distortion, etc and may be coupled across slices. The approach will help to understand and reduce the communication complexity of the scheduling algorithms.We will develop a framework for the analysis of the distributed computational model. This framework will use the Network Calculus theory which is based on Min-plus algebra to develop the optimal mapping between resource and tasks/flow traffic. This approach will be used to elaborate traffic estimation methods of the backlog and the latency for each slice.Another very important issue related to the resource allocation comes from the distributed structure of the router which is built on multiple controllers managing multiple components (Linecard, Switch fabrics, dedicated interface....). The distributed solution requires stability which will be obtained by applying control theory principles.In conclusion, this project proposes a multi-objective approach drawing from the Game Theory, the Stochastic Optimization, the Network Calculus and the Control Theory to derive frameworks that will allow sliceability of the network node in order to provide an optimal and fair resource allocatio
Program
Discovery Grants Program - Individual
Recipient
Location
Quebec, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
46384-2012
Name nom
Cherkaoui, Omar
Department département
Informatique
Organization id
57
Institution établissement
Université du Québec à Montréal
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2014
Competition year année de concours
2012
Award amount
17000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
803
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Computer communications
Area of application fr
Téléinformatique
Research subject code
2718
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Communication and information theory
Research subject fr
Théorie des télécommunications et de l'information
Partie
3
Nb partie
5
Application title
Optimal resource allocation of virtualized router: a multi-objective approach
Keyword
NSERC
Application summary
With the venue of the cloud and the large virtualized data centers, there is a huge need to provide new traffic isolation services between virtualized domains on the network. Unfortunately, the isolation available today is mainly based on the management plane and control plane and is not embedded with the data plane. This newlevel of isolation will require to revisit the resource allocation strategies and redesign the network nodes (switches and routers). The targeted resources include the packet processing such as network processors, dedicated processors and multicore processors, memories such as TCAM, SRAM, etc., and interfaces such as Ethernet, etc.Traditionally, the resource allocation strategies tried to maximize the global utility to guarantee performance and quality of service on packets. The aim of this research project is to push the sliceability on those node and ensure fairness between slices. The maximization problem is extended with new constraints that require the extension of the strategies, frameworks and algorithms related to resource allocation. The proposed research aims at solving this problem using an innovative combination of multiple approaches: Game Theory, Control Theory, Stochastic Optimization and Network Calculus. The Game Theory will be used to develop a fair distributed algorithm for resource allocation between slices. To achieve a fair allocation, we will develop a framework based on cooperative and non-cooperative game theory. For the cooperative approach, the Nash bargaining solution will be used to solve the centralized problem. We will then propose a distributed algorithm for implementing the optimal and fair resource allocation and provide conditions for its convergence.On the other hand, the Stochastic Network Utility Maximization (NUM) is used to model a significantly large array of resource allocation problems and is well-adapted to the slicing router context. The utility function will depend on rate, latency, jitter, energy, distortion, etc and may be coupled across slices. The approach will help to understand and reduce the communication complexity of the scheduling algorithms.We will develop a framework for the analysis of the distributed computational model. This framework will use the Network Calculus theory which is based on Min-plus algebra to develop the optimal mapping between resource and tasks/flow traffic. This approach will be used to elaborate traffic estimation methods of the backlog and the latency for each slice.Another very important issue related to the resource allocation comes from the distributed structure of the router which is built on multiple controllers managing multiple components (Linecard, Switch fabrics, dedicated interface....). The distributed solution requires stability which will be obtained by applying control theory principles.In conclusion, this project proposes a multi-objective approach drawing from the Game Theory, the Stochastic Optimization, the Network Calculus and the Control Theory to derive frameworks that will allow sliceability of the network node in order to provide an optimal and fair resource allocatio