NDLI: A graph-coloring scheme for scheduling cell transmissions and its photonic implementation

Content Provider	IEEE Xplore Digital Library
Author	Lakshman, T.V. Bagchi, A. Rastani, K.
Copyright Year	1972
Abstract	The authors present a scheme for scheduling cell-transmissions in an ATM switch capable of atomic multicasts. In an atomic multicast, partial transmissions to subsets of the requested output ports are not allowed. In any transmission slot, a cell at an input port is either successfully (without output contention) transmitted to all requested destinations or it is not transmitted at all. Scheduling is needed because many cells (due to the uncoordinated nature of their arrivals at the switch input ports) can request transmission to the same switch output port at the same time even though the switch may not have the ability to simultaneously satisfy all these requests. The problem is to devise an implementable scheme for scheduling atomic multicast requests such that all requests present at the beginning of a scheduling interval are satisfied in a minimum number of cell transmission slots. However, finding this minimum transmission schedule is equivalent to finding the minimum vertex coloring of a "contention graph" derived from the input requests. Since finding the minimum vertex coloring is an NP-hard problem, it is not feasible to find the minimum schedule. They present a scheduling scheme which uses a heuristic coloring algorithm with a known upper bound on the number of transmission slots used. This scheme can also schedule a mix of request types (unicasts, atomic and non-atomic multicasts). They describe two methods for photonic implementation of the scheduler and also methods to incorporate fairness and priorities.<>
Starting Page	2062
Ending Page	2070
Page Count	9
File Size	1096713
File Format	PDF
ISSN	00906778
Volume Number	42
Issue Number	234
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1994-02-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Optimal scheduling Switches Unicast Asynchronous transfer mode Communication switching NP-hard problem Heuristic algorithms Multicast algorithms Scheduling algorithm Upper bound
Content Type	Text
Resource Type	Article
Subject	Electrical and Electronic Engineering

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

Distributed routing for dynamic multicasting with advance resource reservation information

An efficient communication scheme for multicasting on ATM networks

A new packet scheduling algorithm for input-buffered multicast packet switches

FINE: a multicast scheduling algorithm for high-speed ATM switches

Multicast routing algorithms for 3-stage Clos ATM switching networks

Achieving IP-multicast functionality in the asynchronous transfer mode environment

A study of non blocking multicast switching networks

Multicast routing in 3-stage Clos ATM switching networks

Multicast scheduling for input-queued switches

A graph-coloring scheme for scheduling cell transmissions and its photonic implementation

Similar Documents

Distributed routing for dynamic multicasting with advance resource reservation information

An efficient communication scheme for multicasting on ATM networks

A new packet scheduling algorithm for input-buffered multicast packet switches

FINE: a multicast scheduling algorithm for high-speed ATM switches

Multicast routing algorithms for 3-stage Clos ATM switching networks

Achieving IP-multicast functionality in the asynchronous transfer mode environment

A study of non blocking multicast switching networks

Multicast routing in 3-stage Clos ATM switching networks

Multicast scheduling for input-queued switches

A graph-coloring scheme for scheduling cell transmissions and its photonic implementation