NDLI: Optimally adaptive, minimum-distance, circuit-switched routing in hypercubes

Content Provider	ACM Digital Library
Author	Lynch, Donald J. Shaffer, Roger B. Mahmood, Ausif
Copyright Year	1997
Abstract	In circuit-switched routing, the path between a source and its destination is established by incrementally reserving all required links before the data transmission can begin. If the routing algorithm is not carefully designed, deadlocks can occur in reserving these links. Deadlock-free algorithms based on dimension-ordered routing, such as the $\textit{E-cube},$ exist. However, $\textit{E-cube}$ does not provide any flexibility in choosing a path from a source to its destination and can thus result in long latencies under heavy or uneven traffic. Adaptive, minimum-distance routing algorithms, such as the Turn Model and the UP Preference algorithms, have previously been reported. In this article, we present a new class of adaptive, provably deadlock-free, minimum-distance routing algorithms. We prove that the algorithms developed here are optimally adaptive in the sense that any further flexibility in communication will result in deadlock. We show that the Turn Model is actually a member of our new class of algorithms that does not perform as well as other algorithms within the new class. It creates artificial hotspots in routing the traffic and allows fewer total paths. We present an analytical comparison of the flexibility and balance in routing provided by various algorithms and a comparison based on uniform and nonuniform traffic simulations. The Extended UP Preference algorithm developed in this article is shown to have improved performance with respect to existing algorithms. The methodology and the algorithms developed here can be used to develop routing for other schemes such as wormhole routing, and for other recursively defined networks such as $\textit{k}-ary$ $\textit{n}-cubes.$
Starting Page	166
Ending Page	193
Page Count	28
File Format	PDF
ISSN	07342071
e-ISSN	15577333
DOI	10.1145/253145.253261
Volume Number	15
Issue Number	2
Journal	ACM Transactions on Computer Systems (TOCS)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1997-05-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	$\textit{k}-ary$ $\textit{n}-cube$ Adaptive routing Circuit switched Hypercube Interconnection networks Parallel processing Routing algorithms
Content Type	Text
Resource Type	Article
Subject	Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Pancyclicity and Panconnectivity in Augmented k-ary n-cubes

Modeling adaptive routing in k-ary n-cube networks

Theoretical Research on Topological Properties of Generalized K-Ary n-Cube Interconnection Network

Adaptive routing protocols for hypercube interconnection networks

Fault diameter of k-ary n-cube networks

k-Pancyclicity of k-ary n-Cube Networks under the Conditional Fault Model

Extended hypercube: a hierarchical interconnection network of hypercubes

Pancyclicity and panconnectivity in augmented k-ary n-cubes.

Exchanged Crossed Cube: A Novel Interconnection Network for Parallel Computation

Optimally adaptive, minimum-distance, circuit-switched routing in hypercubes

Similar Documents

Pancyclicity and Panconnectivity in Augmented k-ary n-cubes

Modeling adaptive routing in k-ary n-cube networks

Theoretical Research on Topological Properties of Generalized K-Ary n-Cube Interconnection Network

Adaptive routing protocols for hypercube interconnection networks

Fault diameter of k-ary n-cube networks

k-Pancyclicity of k-ary n-Cube Networks under the Conditional Fault Model

Extended hypercube: a hierarchical interconnection network of hypercubes

Pancyclicity and panconnectivity in augmented k-ary n-cubes.

Exchanged Crossed Cube: A Novel Interconnection Network for Parallel Computation

Optimally adaptive, minimum-distance, circuit-switched routing in hypercubes