NDLI: Nonpreemptive Scheduling of Optical Switches

Content Provider	IEEE Xplore Digital Library
Author	Kesselman, A. Kogan, K.
Copyright Year	1972
Abstract	Many high-speed routers today use input-queuing (IQ) architectures with a crossbar switching fabric based on optical technology. Packets in the input queues are divided into cells of unit length, and the goal is to find a schedule of minimum makespan that forwards all packets to the output ports. The problem is complicated since, in optical switches, so-called configuration delay, that is the time required to reconfigure the switching fabric, is non-negligible with respect to the cell transmission time. We aim to design a scheduler whose complexity does not depend on the number of packets in the input queues. Thus, we focus on the nonpreemptive bipartite scheduling (NPBS) problem, where each input queue is connected to each output port in at most one configuration. We demonstrate that the NPBS problem is NP-hard for any value of the configuration delay, and approximation within a ratio smaller than 7/6 is NP-hard as well. For the offline version of the NPBS problem, we show that a simple greedy algorithm achieves an approximation factor of 2 for arbitrary configuration delay. Then, we consider the online version of the NPBS problem, where the switch gathers the incoming traffic periodically and then schedules the accumulated batches. We propose a scheduling algorithm that guarantees strict delay for any admissible traffic, provided that the switch has a moderate speed-up of two. Finally, we extend our results to the nonbipartite scheduling problem.
Starting Page	1212
Ending Page	1219
Page Count	8
File Size	413786
File Format	PDF
ISSN	00906778
Volume Number	55
Issue Number	6
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2007-06-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	Optical switches Fabrics Scheduling Delay Optical packet switching Packet switching Telecommunication traffic Traffic control Internet Communication switching store and forward networks Nonpreemptive scheduling optical switches
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

A distributed scheduling architecture for scalable packet switches

Considerations of periodic traffic in packet switching

Smart trunk scheduling strategies for future integrated services packet-switched networks

Multipath interconnection: a technique for reducing congestion within fast packet switching fabrics

Control of Satellite-Packet Switched Telecommunications Networks

On the stability of local scheduling policies in networks of packet switches with input queues

Traffic scheduling in non-blocking optical packet switches with minimum delay

Performance study of an input queueing packet switch with two priority classes

Exact admission control for networks with a bounded delay service

Nonpreemptive Scheduling of Optical Switches

Similar Documents

A distributed scheduling architecture for scalable packet switches

Considerations of periodic traffic in packet switching

Smart trunk scheduling strategies for future integrated services packet-switched networks

Multipath interconnection: a technique for reducing congestion within fast packet switching fabrics

Control of Satellite-Packet Switched Telecommunications Networks

On the stability of local scheduling policies in networks of packet switches with input queues

Traffic scheduling in non-blocking optical packet switches with minimum delay

Performance study of an input queueing packet switch with two priority classes

Exact admission control for networks with a bounded delay service

Nonpreemptive Scheduling of Optical Switches