18 - Multi-Commodity Flow Routing

Summary

Introduction

In this chapter, we consider a canonical network flow problem, popularly known as multicommodity routing, where the network is represented as a directed graph. Each flow request identifies a source–destination pair and a flow demand, i.e., the amount of flow going from the source to the destination (possibly over multiple paths of the graph) should be at least as much as the demand. Each edge of the graph is equipped with a latency function, and the cost of an edge is equal to the latency function evaluated at the total flow passing through it. Requests arrive sequentially or in an online manner, and have to be routed irrevocably using only the causal information, and the goal is to minimize the sum of the cost of all edges after all request arrivals.

Unlike many other problems considered in this book, the offline optimal solution is easy to find by solving a convex program. On the online front, however, an optimal online algorithm is not known. We consider both the splittable and the unsplittable cases (where only one path can be used to route the demand for each source–destination pair). For both cases, we consider affine latency functions and present the best-known guarantees on the competitive ratio that are achieved by a locally optimal algorithm that solves a convex program on each request arrival given the past routing decisions.

It is worthwhile noting that the unsplittable problem considered in this chapter is similar to the network load balancing problem studied in Section 12.4, where the objective was to minimize the maximum load exerted on any one edge of the network. Compared to that objective, in this chapter, we consider minimizing the sum of the ‘loads’ exerted on all edges of the network via summing the latency functions of each edge evaluated at their flow allocation. This new cost function has a fundamentally different competitive ratio guarantee compared to the network load balancing problem. In particular, we showed in Chapter 12 that the best competitive ratio for the network load balancing problem scales as Θ(log(n)), where n is the number of vertices in the network graph. In contrast, we will show that for affine latency functions, a simple algorithm is constant competitive.