Point-to-point circuit routing is a generalization of online load balancing. Jobs arrive online and must be assigned immediately. Assigning a job to a machine increases the machine’s load according to a load vector. All coordinates of the load vector are the same if all machines are related. If the machines are unrelated, then the coordinates are either infinity or a value that depends only on the job (not the machine). The goal is to minimize the maximum load.

The effectiveness of an online algorithm is its competitive ratio: the ratio of the maximum relative load of the online algorithm to the maximum relative load achieved by an optimal offline algorithm as a function of n, the number of nodes in a network.

The paper gives an algorithm that achieves a constant competitive ratio when the machines are related. It also gives an algorithm that achieves an ( O log n ) competitive ratio when the machines are unrelated. The result is tight in a directed network. That is, for any online algorithms in a directed network, there exists a scenario in which a log n increase in bandwidth is necessary.

The paper contrasts these bounds with the bounds (which it proves) for a natural greedy approach. If the machines are related, the greedy approach has a competitive ratio of log n; if the machines are unrelated, it has a competitive ratio of n.

The paper solves the multicast online allocation  problem  by modifying its point-to-point algorithm to route over min-weight Steiner trees instead of min-weight paths.The same big-Oh bounds hold for multicast upon using a 2-approximation to the NP-hard problem of determining a min-weight Steiner tree.