An on-line, processor sharing problem for a single server within a packet-switched network is considered. The input to a problem, at each time step, is a set of desired processing rates. These rates in general cannot be exactly achieved since they treat the incoming data as fluid, that is, they assume arbitrarily small fractions of packets can be processed at each time step. The goal of the problem is to closely approximate the given, time-varying sequence of desired rates by a sequence of processor allocations in which only whole packets are processed. The focus of this paper is bounding the additional packet delay incurred in using such an approximation. In this paper, we analyze the worst-case, packet delay in a single server, traffic scheduler that processes N incoming data flows, when total link usage is at most the server capacity. We consider how optimal delay bounds depend on the resources available to a packet-scheduling algorithm. In particular, we analyze the trade-offs between speedup and lookahead (knowledge of the fluid policy's future behavior) required to bound delay for arbitrary, time-varying fluid policies. First, we prove for scheduling algorithms using bounded lookahead and no speedup that worst-case packet delay grows linearly with the number of data flows N. Next, we prove for algorithms using no lookahead that worst-case delay grows linearly with N and decreases exponentially with speedup. Lastly, we look at algorithms using both lookahead and speedup; for fixed speedup and maximum tolerable delay, we lower bound the necessary lookahead (by a function linear in N) and upper bound sufficient lookahead (by a function linear in N).
展开▼
