NDLI: Greedy dynamic hot-potato routing on arrays

Content Provider	IEEE Xplore Digital Library
Author	Caragiannis, I. Kaklamanis, C. Vergados, I.
Copyright Year	2000
Description	Author affiliation: Dept. of Comput. Eng. & Inf., Patras Univ., Greece (Caragiannis, I.)
Abstract	We consider the problem of routing packets in two-dimensional torus-connected processor arrays. Motivated by theoretical work on dynamic routing, we address the dynamic case where packets are continuously injected into the network. We describe three greedy hot-potato routing algorithms and present simulation experiments on tori of several sizes using four well-known greedy (also known as work-conserving) protocols (namely FIFO, LIFO, FTG, and NTG) for the implementation of injection buffers. Our results demonstrate that there exists a greedy hot-potato routing algorithm that is stable for all greedy injection queueing protocols for injection rates very close to 100% of the network capacity. Furthermore, according to the algorithms we studied, we can claim that the one-pass property is not appropriate for the dynamic case, since the system cannot achieve stability at high injection rates.
Starting Page	178
Ending Page	185
File Size	791468
Page Count	8
File Format	PDF
ISBN	0769509363
ISSN	10874089
DOI	10.1109/ISPAN.2000.900283
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2000-12-09
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Buffer storage Informatics Routing protocols Stability Heuristic algorithms Vents
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

Potential Function Analysis of Greedy Hot-Potato Routing (1997)

Potential Function Analysis of Greedy Hot-Potato Routing (Extended Abstract) (1994)

A lower bound for nearly minimal adaptive and hot potato algorithms.

Lower bounds for one-to-one packet routing on trees using hot-potato algorithms (2000).

Randomized greedy hot-potato routing

On buffer-economical store-and-forward deadlock prevention

Routing with Bounded Buffers and Hot-Potato Routing in Vertex-Symmetric Networks (1995)

Hot-potato routing on processor arrays

Pseudo-stabilizing causal ordering

Greedy dynamic hot-potato routing on arrays

Similar Documents

Potential Function Analysis of Greedy Hot-Potato Routing (1997)

Potential Function Analysis of Greedy Hot-Potato Routing (Extended Abstract) (1994)

A lower bound for nearly minimal adaptive and hot potato algorithms.

Lower bounds for one-to-one packet routing on trees using hot-potato algorithms (2000).

Randomized greedy hot-potato routing

On buffer-economical store-and-forward deadlock prevention

Routing with Bounded Buffers and Hot-Potato Routing in Vertex-Symmetric Networks (1995)

Hot-potato routing on processor arrays

Pseudo-stabilizing causal ordering

Greedy dynamic hot-potato routing on arrays