Optimal resource allocation of virtualized router: a multi-objective approach

随着云和大型虚拟数据中心的出现，在网络上的虚拟化域之间提供新的流量隔离服务的需求非常巨大。遗憾的是，目前可用的隔离主要基于管理平面和控制平面，并未嵌入数据平面。这是一项新的 隔离级别需要重新考虑资源分配策略并重新设计网络节点(交换机和路由器)。目标资源包括网络处理器、专用处理器和多核处理器等报文处理，TCAM、SRAM等内存，以及以太网等接口等。 传统的资源分配策略试图最大化全局效用，以保证分组的性能和服务质量。本研究项目的目的是在这些节点上推送可分割性，并保证切片之间的公平性。最大化问题被扩展了新的约束，需要扩展与资源分配相关的策略、框架和算法。提出的研究旨在利用博弈论、控制论、随机优化和网络微积分等多种方法的创新组合来解决这一问题。将利用博弈论来开发一种公平分布的切片之间的资源分配算法。为了实现公平分配，我们将开发一个基于合作和非合作博弈论的框架。对于合作方式，将使用纳什讨价还价解来解决集中问题。然后，我们将提出一种分布式算法来实现最优和公平的资源分配，并为其收敛提供条件。 另一方面，随机网络效用最大化(NUM)被用来对大量的资源分配问题进行建模，并且能够很好地适应分片路由器环境。效用函数将取决于速率、等待时间、抖动、能量、失真等，并且可以跨片耦合。该方法有助于理解和降低调度算法的通信复杂度。 我们将开发一个用于分析分布式计算模型的框架。该框架将使用基于Min-plus代数的网络演算理论来建立资源和任务/流量之间的最优映射。这种方法将被用来详细描述每个片的积压和延迟的流量估计方法。 与资源分配相关的另一个非常重要的问题来自路由器的分布式结构，该结构构建在管理多个组件(线路卡、交换结构、专用接口……)的多个控制器上。分布式解需要稳定性，这将通过应用控制论原理来获得。 总之，本项目提出了一种多目标方法，利用博弈论、随机最优化、网络演算和控制理论来推导框架，允许网络节点的可切割性，以便提供最优和公平的资源分配

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 new level 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