Direct routing: Algorithms and complexity
SourceLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Google Scholar check
MetadataShow full item record
Direct routing is the special case of bufferless routing where N packets, once injected into the network, must be routed along specific paths to their destinations without conflicts. We give a general treatment of three facets of direct routing: (i) Algorithms. We present a polynomial time greedy algorithm for arbitrary direct routing problems which is worst-case optimal, i.e., there exist instances for which no direct routing algorithm is better than the greedy. We apply variants of this algorithm to commonly used network topologies particular, we obtain near-optimal routing time for the tree and d-dimensional mesh, given arbitrary sources and destinationsfor the butterfly and the hypercube, the same result holds for random destinations. (ii) Complexity. By a reduction from Vertex Coloring, we show that Direct Routing is inapproximable, unless P=NP. (iii) Lower Bounds for Buffering. We show that certain direct routing problems cannot be solved efficientlyto solve these problems, any routing algorithm needs buffers. We give non-trivial lower bounds on such buffering requirements for general routing algorithms. © Springer-Verlag 2004.
Showing items related by title, author, creator and subject.
Polycarpou, Marios M.; Ioannou, P. A. (1991)
Fernández Anta, Antonio; Georgiou, Chryssis; Kowalski, D. R.; Zavou, Elli (2015)Consider a system in which tasks of different execution times arrive continuously and have to be executed by a set of machines that are prone to crashes and restarts. In this paper we model and study the impact of parallelism ...
Le, T.; Hadjicostis, Christoforos N. (2007)In this paper, we study the application of the max-product algorithm (MPA) to the generalized multiple-fault diagnosis (GMFD) problem, which consists of components (to be diagnosed) and alarms/connections that can be ...