Network Flow Analysis And Scheduling In Time-varying Netwoks

In order to meet the requirements for the continuous growth of both user devices and services,information networks are evolving towards dynamic,differentiated,diversified,and heterogeneously integrated,while time-varying characteristics are significantly critical in these networks.For example,due to the change of topologies,time-varying characteristics exhibit in networks such as in the medium/low orbit satellite networks,the deepspace exploration networks,the social networks,the Internet of Vehicles,and the Internet of Things.Meanwhile,the change of network-carried services leads to the dynamic changes of the available resources regarding to the nodes and links in the terrestrial Internet and the data center networks.Currently,both the mobile Internet and the space-ground integrated information network,which are two typical information networks,are varying over time.However,the methods for modeling,analyzing,and designing time-varying networks are still incomplete.Since it is difficult to characterize time-varying multi-dimensional resources accurately,time-varying networks are regarded as segmented static networks with existing networking technologies,whose approaches ignore the connectivity of the network resources in different segmented sub-networks and that connectivity as well as the time characteristics of multi-dimensional network resources.As a result,resource utilization is inefficient and transmission quality of service(Qo S)is very challenging to be guaranteed in such time-varying networks.Therefore,it becomes a crucial issue in time-varying networks to accurately characterize the time variability and correlation of the multi-dimensional resources,to efficiently design the methods for network performance analysis,and to establish scheduling strategies with respect to multi-dimensional resources.In this thesis,we focus on the network flow analysis and scheduling methods over the time-varying networks.By extending time-varying theory,a low-complexity and highlyaccuracy time-varying graph model is constructed,and time-varying multi-dimensional resources as well as their mutual restrictions are characterized accurately,both of which can address the resources characterization for time-varying networks.In addition,time-varying graph-based network maximum flow algorithms and Qo S guaranteed routing algorithm are proposed in order to solve the problem in terms of network performance analysis and to improve the ability to guarantee services requirements combining with time-varying multidimensional networks resources.The main contributions of this thesis are list as follows:1.In terms of the difficulties to establish a network model with mutual restrictions of time-varying multi-dimensional resources and to achieve a network maximum flow solution,we propose a time-varying network graph model with low-storage complexity,i.e.,storage time aggregated graph(STAG),and a STAG-based single-source single-sink maximum flow algorithm.Firstly,to reduce the complexity and to increase the characterization accuracy of the existing time-varying graphs,STAG is constructed by aggregating both node and link resources over multiple time slots.Moreover,the storage transfer series of each node is designed in STAG to effectively characterize the restricted relations among adjacent time-related links.Besides,the concepts such as time-varying path,path feasible flow and residual network are redefined in STAG.Secondly,a STAG-based maximum flow algorithm is proposed to solve the problem with respect to the single-source single-sink maximum flow of the time-varying network.Due to the obvious time characteristics of link connectivity,the order of path selection affects the computation results of the network maximum flow.Thus,we design the computation rules of the storage transfer series,which allows to constantly seek and modify the time-variant paths and finally achieves the maximum flow of the time-varying network.Theoretical analysis demonstrates both the low-storage complexity of STAG and efficiency of STAG-based maximum flow algorithm.2.In terms of the difficulties to obtain a solution to two-source two-sink maximum flow caused by the dynamic resources and coupling relationship of multi-flows in time-varying networks,a STAG-based two-source two-sink maximum flow algorithm is proposed.Firstly,STAG is utilized to model the spatiotemporal resources of the multi-source multi-sink timevarying networks.Then,a time-varying two-commodity flow decoupling theory is proposed to simplify the coupling two-commodity flow problem as two single-flow ones,through analyzing the coupling relationship of the two-commodity flow at nodes and links,and constructing both the dual flows(addition flow and subtraction flow)and the time-dependent flow constraints.After that,one STAG-based dynamic combined flow algorithm is proposed to obtain the two-commodity maximum flow by combining maximum flow of the addition flow with subtraction flow.The simulation results show that the proposed algorithm can effectively solve the two-source two-sink maximum flow problem,and the utilization of link resources can be improved by jointly using the storage and transmission resources of the time-varying networks.3.In terms of the difficulties to match resources and missions requirements and to deal with the inefficiency of utilization for multi-dimensional resources in time-varying network,a STAG-based routing algorithm to support Qo S requirements is proposed to realize on-demand missions scheduling and the efficient utilization of multi-dimensional resources.Firstly,a STAG-based on-demand mission model is constructed to jointly depict both multidimensional dynamic network resources and the requirements of mission transmission,addressing the transmission for multiple observation missions in the typical satellite networks.Specifically,in order to depict the mission Qo S requirements(such as mission size,transmission start time and end time,and etc.)and the time-varying network resources,we add the mission source and the support sink as well as the corresponding mission input links and support output links into STAG.As such,the multi-missions Qo S support problem is reduced into the STAG-based maximum flow problem.Then,one STAG-based Qo S support multi-paths routing algorithm is proposed.Through jointly utilizing the time-varying shortest path search strategy,the node's cache limitation and the computation rule of storage transfer series,the multiple feasible paths are obtained for each mission.Besides,considering the maximum transmission delay of each mission,the optimal multi-path transmission scheme is found to maximize the completed mission number,and to ensure the transmission requirements of the multi-missions with the fully utilization of the network resources.Simulation results show that the proposed algorithm can effectively improve the mission completion rate and resource utilization rate.