Summary and Critique by Ed Spitznagel:

SUMMARY

The authors present an algorithm to solve a deterministic form of a routing problem in delay tolerant networking with the following constraints: contact possibilities are known in advance, and both capacity and transit times for the links are piecewise constant. The algorithm first performs a discretization step, which determines the size for the time step intevals; then it creates a linear program to find the optimal solution to the problem, which is a dynamic version of the multicommodity flow problem. Two equivalent linear programming formulations are given; the second one is smaller and runs faster in the general-purpose linear solver CPLEX.

CRITIQUE

The paper is well-written and the algorithm does, in fact, find the optimal solution to the specified problem. The algorithm, however, is perhaps more of theoretical interest than practical, for the following reasons:

• No indication of the computational complexity or time to find a solution is given. However it appears that even a simple example with a handful of links and a dozen time steps can create thousands of variables in the linear program; things can get even worse as the discretization step may result in time steps several orders of magnitude smaller than the total window for scheduling. Even for the restricted set of problem instances where the running time is not prohibitively large, it may be faster to simply hand the problem instance to Anshul.
• It requires global knowledge of the entire network, knowledge of when links will be available, and of traffic demands. These requirements may make the algorithm infeasible for many applications.
• Some lesser issues: Delay is in no way a function of traffic load (which can still make sense if propagation delay >> queueing delay), fairness is not addressed, fault-tolerance is not addressed, and efficient multicast support is not considered.