Fakultät für Informatik der Technischen Universität München Lehrstuhl für Effiziente Algorithmen Postadresse: 80290 München; Hausadresse: Arcisstr.21, 80333 München

Off-line and On-line Call-Scheduling in Stars and Trees

Thomas Erlebach and Klaus Jansen

Given a communication network and a set of call requests, the goal is to find a minimum makespan schedule for the calls such that the sum of the bandwidth requirements of simultaneously active calls using the same link does not exceed the capacity of that link. In this paper the call-scheduling problem is studied for star and tree networks. Lower and upper bounds on the worst-case performance of List-Scheduling (LS) and variants of it are obtained for call-scheduling with arbitrary bandwidth requirements and either unit call durations or arbitrary call durations. LS does not require advance knowledge of call durations and, hence, is an on-line algorithm. It has performance ratio (competitive ratio) at most 5 in star networks. A variant of LS for calls with unit durations is shown to have performance ratio at most 2+(2/3). In tree networks with n nodes, a variant of LS for calls with unit durations has performance ratio at most 6, and a variant for calls with arbitrary durations has performance ratio at most 5*log(n).