Joint Optimization of VNF Deployment and Routing in Software Defined Satellite Networks

By integrating software defined network and network function virtualization, software defined satellite networks (SDSNs) can enable flexible virtual network function (VNF) deployment to process and forward end-to-end traffic flows. Since one traffic flow has to go through all its required VNFs, the VNF deployment has a significant impact on traffic routing. In this regard, with time-varying network topology and limited network resources taken into account, we aim to match VNF deployment and routing to fulfill traffic flows' requirements in the SDSN in a cost-effective manner. Specifically, we first evolve the traditional time evolving graph as a software defined time evolving graph (SDTEG) to depict the time-varying network topology and meanwhile, provide a shared platform for elastic network resource provisioning. On this basis, we then formulate a cost minimization problem as a multi-slot integer linear programming problem to make a judicious decision on VNF deployment and routing for each traffic flow. To address this challenging problem effectively, we further propose a heuristic algorithm, referred to as time-slot decoupled algorithm (TDA). Finally, the effectiveness of the TDA as well as the superiorities from the joint optimization of VNF deployment and routing are demonstrated through simulation results.