Packet Routing and PRAM Emulation on Star Graphs and Leveled Networks
| Autor: | Sanguthevar Rajasekaran, Michael A. Palis |
|---|---|
| Rok vydání: | 1994 |
| Předmět: |
Routing protocol
Dynamic Source Routing Computer Networks and Communications Equal-cost multi-path routing Computer science Routing table A* search algorithm Topology Theoretical Computer Science law.invention Routing Information Protocol Artificial Intelligence law Computer Science::Networking and Internet Architecture Destination-Sequenced Distance Vector routing Triangular routing Static routing Interconnection Path vector protocol Deterministic routing Distance-vector routing protocol Link-state routing protocol Hardware and Architecture Multipath routing Hypercube Algorithm Software |
| Zdroj: | Journal of Parallel and Distributed Computing. 20:145-157 |
| ISSN: | 0743-7315 |
| DOI: | 10.1006/jpdc.1994.1015 |
| Popis: | We consider the problem of permutation routing on a star graph, an interconnection network which has better properties than the hypercube. In particular, its degree and diameter are sublogarithmic in the network size. We present optimal randomized routing algorithms that run in O(D) steps (where D is the network diameter) for the worst-case input with high probability. We also show that for the n-way shuffle network with N = nn nodes, there exists a randomized routing algorithm which runs in O(n) time with high probability. Another contribution of this paper is a universal randomized routing algorithm that could do optimal routing for a large class of networks (called leveled networks) which includes the star graph. The associative analysis is also network-independent. In addition, we present a deterministic routing algorithm, for the star graph, which is near optimal. All the algorithms we give are oblivious. As an application of our routing algorithms, we also show how to emulate a PRAM optimally on this class of networks. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|