Deadline-Constrained Multi-Commodity Flow Routing and Scheduling Optimization with Consideration of Edge Lengths and Capacities

As satellite communications emerge, meeting the deadline requirement of data flow concentrates more on the trade-off between the route lengths and capacities, since the propagation delay becomes more outstanding in satellite networks.To deal with the transmission optimization problems of multi-commodity flow with deadlines in the networks considering edge lengths and capacities, like satellite-basd networks, wepropose a new traffic model of flow conservation with the delay of edge lengths and then construct the deadline-constrained multi-commodity flow routing and scheduling optimization based on the proposed traffic model.Besides, for priority scheduling of multi-commodity flow, admission control is studied to schedule the commodities according to the priority level based on the proposed deadline-constrained flow optimization model.The time-slicing approach and the decomposition methods are applied to the approximate solution of the proposed models, where the flow optimizations and the admission control are respectively discretized to linear programmings and mixed 0-1 linear programmings, whose forms are suitable for the Benders or (and) Dantzig-Wolfe decompositions.Numerical examples on a benchmark network and Iridium satellite network illustrate the effect of the proposed routing/scheduling methods, compared to the methods without considering the edge delays