چكيده به لاتين
Network resource management and the ability to provide diverse services based on the user requirements and network constraints are two important factors for the Telco operators to be successful. The notion of service chaining has been introduced by the network research community as a technique for agile configuration of complex services through a chain of more basic service components. Service chaining involves many aspects such as: the placement of network functions, service management, as well as security. Recent advancements in the technologies such as Software Defined Networking (SDN) and Network Function Virtualization (NFV) enable service chaining to facilitate dynamic control, traffic management through service functions, orchestration of service functions, and efficient deployment. Service chaining is an NP-hard problem and has been addressed via centralized and decentralized approaches the literature. A centralized solution requires perfect knowledge w.r.t. the network state and system parameters and does not scale in large problems. Recently decentralized solutions based on game theory have come into spotlight. However existing game-theoric solutions need to have accurate or statistical information about the values of the problem parameters. For example, the delays of links between nodes should be specified before starting the execution. This makes the solution dependent on operational environment and bound to a specific model, i.e. if the environment changes, the current solution is no longer valid. As in many scenarios, the network statistics may not be known beforehand. We need to come up with a solution that only relies on the feedback from real interactions with the system to compute the optimal service chain configuration.
In this thesis, we consider decentralized service chaining problem where no information about the link latencies is assumed to be available a priori. The novelty of our approach is in proposing a potential game with a noisy cost function to formulate the problem. In this game, the so-called network service brokers (NSBs) are the players, and they are equipped with convergent multi-agent learning procedures to gradually shape their service chaining strategy by sample-based learning and experience. We experiment with several scenarios and compare our solution with a previous distributed scheme. As evidenced by the results, we achieve an improvement on total cost, while requiring less statistical information of the problem. More specifically, the minimum, maximum, and average of total cost reduction are equal to 19.55%, 22.99% and 21.26%, respectively. However, as expected, the previous work with known information converges faster than our solution (which relies on learning and sampling). Also, given that the proposed solution has to explore the quality of all possible chains to complete the learning process, as the number of functions, players, and servers increase, it has lower scalability than the approach with known information.
