1. Introduction

For real-time communications, such as teleconferencing, videoconferencing or real-time online multicast routing applications, connection establishment time can be crucial. Especially for online multicast sessions where new members join and some members leave the session, immediate establishment of new admissible paths may be as important as constructing low cost delay-constrained paths. The proposed heuristic PAS (partial-path combination approach for constrained path selection) can easily be employed in such time-critical path selection tasks. PAS is a heuristic proposed to find best effort least-cost delay-constrained paths between nodes or trees with the same order of complexity as Dijkstra's algorithm.

In order to formulate the problem of finding delay-constrained least-cost paths, the network is modeled as a directed, connected graph G = (V, E), where V is the set of nodes and E is the set of directed links. Each link, e, is characterized by a cost, C( e), and a delay, D( e) and n is the number of...