Bianchini-Shen

Bianchini and Shen [7] presented a methodology for generating routing schedules for static problems, using an optimal polynomial-time algorithm. They examine `traffic compilation' once data operators are mapped onto nodes, optimizing for overall bandwidth in the system.

Their network traffic scheduler iterates through the following four steps. A saturated link is one that has been allocated 100% of the traffic it can support.

1.

An initial schedule is presented (possibly using a simple shortest path routing scheme).

2.

Traffic volumes are simultaneously and proportionally increased until one or more links are saturated.

3.

A new schedule is presented, by rerouting traffic from saturated to unsaturated links.

4.

The previous two steps are iterated until an optimal traffic schedule results.

The traffic-smoothing technique they present is a version of multi-commodity flow, much discussed in the literature [41,34,35,40]. The general form of the problem is to model a network graph as fluid pipes, where distinct communication source/destination pairs correspond to distinct commodities that must push through the pipes to reach their destination. An optimal schedule has been found when a cutset of saturated links is produced, i.e. a set of links that disconnect the graph when removed from it. A linear programming formulation can be shown for this problem, but can not be rapidly solved.

Bianchini and Shen present a direct scheduler solution to the problem that is polynomial in the number of links. They find the minimum spanning tree for the graph; then, for each node at one end of a saturated link not on the spanning tree, they check how the traffic is routed. If it is routed onto the saturated link rather than via the spanning tree, a reroute is possible to improve the overall link usage. Each phase of the algorithm takes only $O(L \log{L})$steps, resulting in a rapid solution of the routing problem.