The area of broadband communication networks
gives rise to a large number of
on-line problems.
One of the most extensively studied problem in this area is the
on-line processing of calls;
two classes of problems have been considered: call control and load
balancing.
In the first case a sequence of
requests for calls is given on-line to an algorithm which can be
either accepted or rejected; the algorithm
has to select a virtual circuit between the communicating parties
of an accepted call,
obeying the network constraints, with the
goal of maximizing the total benfit of accepted calls.
In load balancing the goal of the algorithm is to find virtual
circuits for all calls that minimize the use
of network resources.
Algorithms for on-line problems are usually analysed in terms of
their competitive ratio, i.e., the worst case, over all input
sequences, of the ratio between the values of the solution found by
an optimal off-line algorithm (that knows the whole sequence in
advance) and by the on-line algorithm.
In this talk we review the main results that have been proposed in
the literature by presenting both deterministic and randomized
algorithms for various kind of network topologies and discussing
lower bounds.
CV: