Packet Routing in Fixed-Connection Networks: A Survey

✍ Scribed by Miltos D Grammatikakis; D.Frank Hsu; Miro Kraetzl; Jop F Sibeyn

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 748 KB
• Volume: 54
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.1998.1483

✦ Synopsis

We survey routing problems on fixed-connection networks. We consider many aspects of the routing problem and provide known theoretical results for various communication models. We focus on (partial) permutation, k-relation routing, routing to random destinations, dynamic routing, isotonic routing, fault tolerant routing, and related sorting results. We also provide a list of unsolved problems and numerous references.

1998 Academic Press

1. Introduction

With advances in VLSI technology it has become feasible to build multicomputers consisting of hundreds or even thousands of processor nodes with local memory, which communicate with each other over a fixed interconnection network. Essential conditions for the efficient use of such machines are routines for exchanging data between the processors. In view of the many network topologies and the multitude of communication patterns, it is not surprising that a rich body of article no. PC981483 77