NDLI: An Euler path based technique for deadlock-free multicasting

Content Provider	IEEE Xplore Digital Library
Author	Agrawal, N. Ravikumar, C.P.
Copyright Year	1997
Description	Author affiliation: Dept. of Electr. Eng., Indian Inst. of Technol., New Delhi, India (Agrawal, N.)
Abstract	The existing algorithms for deadlock-free multicasting in interconnection networks assume the Hamiltonian property in the networks topology. However, these networks fail to be Hamiltonian in the presence of faults. This paper investigates the use of Euler circuits in deadlock-free multicasting. Not only are Euler circuits known to exist in all connected networks, a fast polynomial-time algorithm exists to find an number circuit in a network. We present a multicasting algorithm which works for both regular and irregular topologies. Our algorithm is applicable to store-and-forward as well as wormhole-routed networks. We show that at most two virtual channel are required per physical channel for any connected network. We also prove that no virtual channels are required to achieve deadlock-free multicasting on a large class of networks. Unlike other existing algorithms for deadlock-free multicasting in faulty networks, our algorithm requires a small amount of information to be stored at each node. The potential of our technique is further illustrated with the help of various examples. A performance analysis on wormhole-routed networks shows that our routing algorithm out-performs existing multicasting procedures.
Starting Page	378
Ending Page	384
File Size	681618
Page Count	7
File Format	PDF
ISBN	081868108X
ISSN	01903918
DOI	10.1109/ICPP.1997.622669
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1997-08-11
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	System recovery Multicast algorithms Routing Network topology Circuit faults Casting Multiprocessor interconnection networks Polynomials Circuit topology Algorithm design and analysis
Content Type	Text
Resource Type	Article

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

An Euler Path Based Technique for Deadlock-free Multicasting

Adaptive routing in hexagonal torus interconnection networks

Deadlock-free adaptive routing algorithms for multicomputers: evaluation of a new algorithm

A Condition of Deadlock-Free Routing in Mesh Network

A topology-independent generic methodology for deadlock-free wormhole routing

A trail-based deadlock-free routing scheme in wormhole-routed networks

Deadlock avoidance and adaptive routing in interconnection networks

A new theory of deadlock-free adaptive multicast routing in wormhole networks

Deadlock-Free Routing Algorithms for 6D Mesh/iBT Interconnection Networks

An Euler path based technique for deadlock-free multicasting

Similar Documents

An Euler Path Based Technique for Deadlock-free Multicasting

Adaptive routing in hexagonal torus interconnection networks

Deadlock-free adaptive routing algorithms for multicomputers: evaluation of a new algorithm

A Condition of Deadlock-Free Routing in Mesh Network

A topology-independent generic methodology for deadlock-free wormhole routing

A trail-based deadlock-free routing scheme in wormhole-routed networks

Deadlock avoidance and adaptive routing in interconnection networks

A new theory of deadlock-free adaptive multicast routing in wormhole networks

Deadlock-Free Routing Algorithms for 6D Mesh/iBT Interconnection Networks

An Euler path based technique for deadlock-free multicasting