Maximum Throughput Routing of Traffic in the Hose Model

In this paper, we investigate whether the desirable properties of two-phase routing come with any resource overhead compared to (i) direct source-destination path routing, and (ii) optimal scheme among the class of all schemes that are allowed to even make the routing dependent on the traffic matrix. In the pursuit of this endeavor, we achieve several milestones. First, we develop the first polynomial size linear programming (LP) formulation for maximum throughput routing of hose traffic along direct source-destination paths. Second, we develop the first polynomial size LP formulation for maximum throughput two-phase routing of hose traffic for a generalized version of the scheme proposed in [9]. Third, we prove that the throughput of two-phase routing is at least 1/2 that of the optimal scheme.