Network functions virtualization (NFV) is a new paradigm to achieve flexible and agile network services by decoupling network functions from proprietary hardware and running them on generic hardware as virtual network functions (VNFs). In the NFV network, a network service can be modeled as a sequence of VNFs, called a service chain. Given a connection request (e.g, origin, destination, and a sequence of required functions), we have to solve both the service chaining and function placement problems to find an appropriate service path that optimizes the objective (e.g., minimization of the total path delay) while satisfying the service chain requirements. In this paper, focusing on the similarity between the service chaining problem and the shortest path tour problem (SPTP) and developing the novel network model called augmented network, we formulate capacitated SPTP-based integer linear programs (ILPs) for the service chaining and function placement. Through numerical results obtained by the existing solver, we show the proposed ILP for the service chaining can support 1.22–1.90 times as large-scale systems as the existing ILP. Furthermore, we also demonstrate that the proposed ILP for both the service chaining and function placement can shorten the total delay by 15.8% compared with that only for the service chaining. For further scalability, we propose a shortest-path-based heuristic algorithm to solve the ILPs and show the heuristic for service chaining and function placement can calculate the optimal solution with high accuracy in strongly polynomial time.
Traffic congestion in urban areas causes economic and time loss. Such traffic congestion is caused by selfish routing where users aim to minimize their own travel time. Even if a navigation system provides them with recommended routes, they may not follow the routes, due to dissatisfaction with the expected travel time. In this paper, inspired by the concept of “Nudge”, we propose “selfish yet optimal routing”, where all users rationally aim to minimize their own travel time but social optimal routing emerges from such selfish routing by adjusting their perceived traffic information appropriately. We propose a scheme to derive nudging traffic information that fills the gap between selfish routing criterion and altruistic one by internalizing the marginal cost into the perceived traffic information. Users will conduct the selfish routing under their perceived traffic information, which unconsciously results in the optimal routing. Through numerical experiments using both the artificial road network and the real one, we show that the proposed scheme achieves almost the same performance compared with the optimal routing. In addition, the proposed scheme reduces the average travel time by 19.1% compared with notification of actual traffic information, in case of the central-area road network of Nagoya city, Japan.
9 January 2024 in IEEE Transactions on Network and Service Management
To achieve sustainable networking, network service providers have expressed significant interest in employing automated network operations that integrate network functions virtualization (NFV), software-defined networking (SDN), and machine learning (ML). In the context of NFV/SDN, a certain network service is regarded as a sequence of virtual network functions (VNFs) forming a service chain. The service chaining (SC) problem aims at establishing an appropriate service path from an origin node to a destination node where the VNFs are executed at intermediate nodes in the required order under resource constraints on nodes and links. SDN enables programmable configurations on forwarding devices (i.e., switches and routers) for traffic forwarding between VNFs. In our previous work, we formulated the SC problem as an integer linear program (ILP) based on the capacitated shortest path tour problem (CSPTP), which is an extended version of SPTP with additional node and link capacity constraints. Furthermore, we developed Lagrangian heuristics to solve the problem by considering the balance between optimality and computational complexity. In this paper, we propose a deep reinforcement learning (DRL) framework coupled with the graph neural network (GNN) to realize CSPTP-based SC that adapts to changes of service demand and/or network topology. Numerical results show that the proposed framework achieves nearly optimal SC with higher learning speed compared to the conventional deep Q-Network based approach. Moreover, it performs well when confronted with variations in service demand and exhibits competitive performance compared to the ILP solutions across the majority of 243 real-world topologies.
31 December 2022 in Journal of Network and Systems Management