Oblivious Network Design

Consider the following network design problem: given a network G = (V,E), source-sink pairs \{s_i, t_i\} arrive and desire to send a unit of flow between themselves. The cost of the routing is this: if edge e carries a total of f_e flow (from all the terminal pairs), the cost is given by \sum_e \load(f_e), where \load is some concave cost function; the goal is to minimize the total cost incurred. However, we want the routing to be oblivious: when terminal pair \{s_i, t_i\} makes its routing decisions, it does not know the current flow on the edges of the network, nor the identity of the other pairs in the system. Moreover, it does not even know the identity of the function \load, merely knowing that \load is a concave function of the total flow on the edge. How should it (obliviously) route its one unit of flow? Can we get competitive algorithms for this problem?

In this paper, we develop a framework to model oblivious network design problems (of which the above problem is a special case), and give algorithms with poly-logarithmic competitive ratio for problems in this framework (and hence for this problem). Abstractly, given a problem like the one above, the solution is a multicommodity flow producing a "load" on each edge of \edgeload_e = \load(f_1(e), f_2(e), \ldots, f_k(e)), and the total cost is given by an "aggregation function" \agg(\edgeload_{e_1}, \ldots,\edgeload_{e_m}) of the loads of all edges. Our goal is to develop oblivious algorithms that approximately minimize the total cost of the routing, knowing the aggregation function \agg, but merely knowing that \load lies in some class C, and having no other information about the current state of the network. Hence we want algorithms that are simultaneously "function-oblivious" as well as "traffic-oblivious".

The aggregation functions we consider are the \max and \sum objective functions, which correspond to the well-known measures of congestion and total cost of a network; in this paper, we prove the following:

• If the aggregation function is \sum, we give an oblivious algorithm with O(\log^2 n) competitive ratio whenever the load function \load is in the class of monotone sub-additive functions. (Recall that our algorithm is also "function-oblivious"; it works whenever each edge has a load function \load in the class.)
• For the case when the aggregation function is \max, we give an oblivious algorithm with O(\log^2 n\log\log n) competitive ratio, when the load function \load is a norm; we also show that such a competitive ratio is not possible for general sub-additive functions.