Maximizing profit in overloaded networks

We consider the problem of scheduling data in overloaded networks. We wish to maximize the total profit of data that is served. We first consider a single server that has to schedule data over time-varying channels. This model is motivated by scheduling in wireless networks. Our objective is to maximize $sum_i log R_i (t)$ where $R_i(t)$ is the total amount of data scheduled to user $i$ by time $t$. In contrast to most previous work we assume that the channel conditions are defined by an adversary rather than a stationary, stochastic process. We give lower bounds on how competitive an online algorithm can be and show that the bounds are nearly matched by a simple randomized algorithm. We also consider a situation in which packets with associated profits are injected into a network of servers. We wish to schedule the packets in the network and maximize the profit of data that reaches its destination. We show that if the servers are allowed to exchange control packets that inform each other of the congestion in the network then we can approximate the optimum profit arbitrarily closely. We also show that without these control packets this is not possible. Our results are motivated by recent work on primal-dual algorithms for flow control in networks. The key difference between our approach and this previous work is that we take into account the scheduling dynamics in the network.