Scheduling of Virtual Connections in Fast Networks
Proceedings of the 4th Parallel Systems and Algorithms Workshop (PASA'96)
In communication networks based on ATM it is necessary to allocate
sufficient resources whenever a new connection is established. In
particular, a certain amount of bandwidth must be reserved along a path
between sender and receiver. Several virtual
connections can share a physical link
if the sum of their bandwidths does not exceed the link capacity.
Given a network and a set of connection requests, one is interested
to find a schedule for these calls that minimizes the completion time.
For the restricted setting with unit call durations and unit bandwidth
requirements, it is shown that the call scheduling problem is NP-complete in
tree networks of arbitrary degree and in ring networks. A polynomial-time
optimal algorithm for bidirectional calls in binary trees and a
1.1-approximation algorithm for bidirectional calls in arbitrary trees
are given. In addition, NP-completeness is shown for calls with
arbitrary duration or arbitrary bandwidth requirements
in a wide class of networks.
