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