In this paper we study the problem of on-line call control in a commun
ication network, namely, the problem of accepting or rejecting an inco
ming call (a request for a connection between two points in a network)
without having the knowledge of future calls. The problem is a part o
f the more general problem of bandwidth allocation and management. Int
uition suggests that knowledge of future call arrivals can be crucial
to the performance of the system. In this paper, however, we present p
reemptive deterministic on-line call control algorithms. We use compet
itive analysis to measure their performance--i.e., we compare our algo
rithms to their off-line, clairvoyant counterparts--and prove optimali
ty for some of them. We consider two specific networks, a line of node
s and a single edge, and investigate a variety of cases concerning the
value of the calls. The value is accrued only if the call terminates
successfully; otherwise-if the call is rejected, or prematurely termin
ated--no value is gained. The performance of the algorithm is then mea
sured by the cumulative value achieved, when given a sequence of calls
. The variety of call value criteria that we study--constant; proporti
onal to the length of the call's route; proportional to its holding ti
me--captures many of the natural cost assignments to network services.
(C) 1997 Academic Press.