 |
|
|||
| Authors: | Thomas Erlebach, Klaus Jansen |
| Group: | Theory of Communication Networks |
| Type: | Inproceedings |
| Title: | Scheduling of Virtual Connections in Fast Networks |
| Year: | 1997 |
| Pub-Key: | EJ97 |
| Book Titel: | 4th Parallel Systems and Algorithms Workshop (PASA 96) |
| Pages: | 13-32 |
| Keywords: | call scheduling |
| Publisher: | World Scientific Publishing |
| Abstract: | 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. |
| Location: | Research Center Jülich |
| Resources: | [BibTeX] |
