Study On Routing Strategies For Software Defined Space Information Networks

In the future 6G network,one of the key features is to provide global seamless coverage.The space information network(SIN)is a flexible,global coverage network,which can achieve real-time acquisition,massive data transmission and processing.Therefore,SIN plays a critical role in future 6G networks.However,with the explosive growth of mission requirements and the emergence of new missions,the disadvantages of the space information network,such as the underutilization of resources,difficulties in upgrading on-orbit hardware,and poor service guarantee capabilities,have gradually become prominent.The space information network adopts virtualization technologies,called software-defined space information network(SD-SIN),which can break through the resource barriers of heterogeneous networks,realize the integration and sharing of multi-dimensional resources,such as communication,storage and computation,to support requested services with diverse quality of service(QoS)requirements.Adopting network function virtualization(NFV)in the SD-SIN can decouple network functions from the dedicated physical devices,thereby,network functions can be virtualized into software components,referred to as virtual network functions(VNF).In this way,adopting NFV in the SD-SIN can flexible deployment VNF,and improve the utilization of resources and network performance.In order to complete the requested service,the mission flow in SD-SIN must satisfy the service function chain(SFC)constraint,i.e.,the mission flow from the source node to the destination node should be processed by all VNFs in the predefined order.Therefore,it is necessary to design a routing strategy that satisfies the SFC constraint to guarantee the request requested service.In addition,as satellites move dynamically in the orbits,the connections between satellites are intermittent,which results in a time-varying network for SD-SIN.Moreover,the requested services in SD-SIN usually require the cooperation of multi-dimensional resources,such as communication resources,storage resources,and computation resources.However,resources in SD-SIN are heterogeneous and limited.Therefore,how to effectively allocate multi-dimensional resources,and design routing in time-varying SD-SIN to meet diverse requirements of services,meanwhile effectively improving network performance is an urgent problem to be solved.Therefore,in this paper,we investigate the routing strategy satisfying SFC constraints in time-varying SD-SIN to improve resource utilization and network performance,thereby guaranteeing diverse requirements of services.The major contributions of this paper are summarized as follows:Aiming at the scenario of a single mission and fixed VNF deployment scheme in timevarying SD-SIN,we propose a maximum flow routing strategy in SD-SIN.Specifically,we exploit the time expanded graph(TEG)to jointly model the communication,storage,and computation resource in time-varying SD-SIN.Based on the TEG,the problem of maximum flow routing strategy with SFC constraints is formulated as a Linear Programming(LP)problem.In addition,for a large-scale SD-SIN network,the complexity of solving the LP problem is very high,as the total number of variables involved is very large.In order to reduce the complexity of solving this problem,we propose a graph theory-based low-complexity maximum flow(GT-LCMF)algorithm.The complexity analysis demonstrates that the proposed GT-LCMF algorithm can effectively reduce the complexity.In addition,simulation results show that the proposed GT-LCMF algorithm can achieve near-optimal performance.simulation results also demonstrate that joint consideration of communication resources and storage resources can effectively improve network performance.Aiming at the single mission scenario in time-varying SD-SIN,we investigate the trade-off between the network maximum flow and coordination overhead,and propose a group sparse jointly VNF deployment and routing strategy(GS-VNF-R)to achieve or approach the network maximum flow,meanwhile reducing network collaboration overhead.Specifically,we propose the Multi-functional time expanded graph(MF-TEG)to jointly model communication,storage,and computation capability in time-varying SD-SIN.Based on the MF-TEG,we propose the GS-VNF-R strategy to strike the trade-off between the network maximum flow with SFC constraints and coordination overhead,which can be formulated as a convex problem.However,for a large-scale SIN,solving this convex problem by traditional convex optimizations imposes a heavy computation burden.In order to reduce the time complexity,we propose a novel optimal low-complexity block-successive upper-bound minimization method of multipliers routing based group sparse(BSUM-M-GS)algorithm.The complexity analysis proves that the proposed BSUM-M-GS algorithm can effectively reduce the complexity.Simulation results show that for some scenarios,the proposed GS-VNF-R strategy can achieve the network maximum flow,meanwhile reducing network collaboration overhead.In addition,the proposed BSUM-M-GS algorithm can converge to the global optimum with less complexity.Aiming at the QoS guarantee problem in the multi-missions scenario for time-varying SD-SIN,we investigate the joint VNFs deployment and routing with QoS constraints(VNF-RQ)strategy to maximize the number of completed missions with the guaranteed end-to-end latency under SFC constraints in time-varying SD-SIN.Specifically,we adopt the MF-TEG to jointly model communication,storage,and computation capability in time-varying SD-SIN.Based on the MF-TEG,we propose the VNF-RQ strategy to maximize the number of completed missions with the guaranteed End-toEnd(E2E)latency.Furthermore,the problem can be formulated as a mixed integer linear programming(MILP)problem and we show that checking the feasibility of this problem is strongly NP-hard in general.In order to effectively solve the problem,we propose a novel low-complexity near-optimal completed missions maximization routing problem(CMMR)algorithm.The simulation results show that the proposed CMMR algorithm can achieve near-optimal performance,and our proposed VNF-R scheme significantly improves network performance while ensuring E2E delay requirements.