DISTRIBUTED ALGORITHMS FOR THE CONSTRAINED ROUTING PROBLEM IN COMPUTER-NETWORKS

The quickest path problem is possibly the most important problem for d ata routing in computer networks. The quickest path problem is to find quickest paths in a computer network to transmit a given amount of da ta with minimal transmission time. The selection of quickest paths dep ends on both the characteristics of the computer network and the amoun t of data to be transmitted. In addition, if the quickest paths are re quired to go through a specified path, then the restricted problem is called the constrained quickest path problem. In this study, some new distributed routing algorithms are developed for multimedia data trans fer in an asynchronous computer network. For all pairs of nodes in a n etwork, an O(mn) messages and O(m) time distributed algorithm is first presented to find constrained quickest paths, and then an O(mn) messa ges and O(m) time distributed algorithm is present to enumerate the fi rst k quickest paths. (C) 1998 Elsevier Science B.V. All rights reserv ed.