NDLI: Constructions of Optical 2-to-1 FIFO Multiplexers With a Limited Number of Recirculations

Content Provider	IEEE Xplore Digital Library
Author	Jay Cheng
Copyright Year	1963
Abstract	Recently, there has been a lot of attention in the literature on a less well-known aspect of queueing theory, the theory of the constructions of queues. Such an interest originates mainly from optical packet switching due to the lack of optical buffers. These constructions of optical queues are based on optical switches and fiber delay lines (SDL). Theoretical studies in the SDL constructions have been recently reported for the constructions of various types of optical queues, including output-buffered switches, first-in-first-out (FIFO) multiplexers, FIFO queues, last-in-first-out (LIFO) queues, priority queues, linear compressors, nonovertaking delay lines, and flexible delay lines. In this paper, we consider the constructions of optical 2-to-1 FIFO multiplexers with a limited number of recirculations through the fibers, which is a very important practical feasibility issue on the constructions of optical queues that has not been theoretically addressed before. Specifically, we consider the constructions of optical 2-to-1 FIFO multiplexers with buffer size at least 2ⁿ-1 by using a feedback system consisting of an (M+2)times(M+2) optical crossbar switch and M fiber delay lines under a simple packet routing policy and under the limitation that each packet can be recirculated through the M fibers at most k times. In one of our previous works, we have shown that this can be done by using n fibers with delays 1, 2, 2²,..., 2^n-1 if there is no limitation on the number of recirculations through the fibers. The main idea in our constructions in this paper is to use extra fibers (other than the n fibers with delays 1, 2, 2²,..., 2^n-1) with appropriately chosen delays to emulate the effective delays of the concatenations of some of the n fibers with delays 1, 2, 2²,..., 2^n-1 so that the number of recirculations is reduced by so doing. It turns out that the number of fibers needed and their delays are determined based on a dynamic programming formulation obtained through a divide-and-conquer approach. We obtain a closed-form expression for the number of fibers needed in our constructions, and show that there are (_r ^k) possible choices for the delays of the required fibers, where r is the remainder of n divided by k. Furthermore, we give the optimal choice of the fiber delays that achieves the maximum buffer size among the (_r ^k) possible choices. Finally, we show that when n=k or nges2k, such an optimal choice also requires the minimum total fiber length among the (_r ^k) possible choices.
Sponsorship	IEEE Information Theory Society
Starting Page	4040
Ending Page	4052
Page Count	13
File Size	356897
File Format	PDF
ISSN	00189448
Volume Number	54
Issue Number	9
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2008-09-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	Multiplexing Optical buffering Optical packet switching Optical feedback Queueing analysis Delay lines Delay effects Optical switches Optical fiber theory Compressors switched delay lines Dynamical programming first-in–first-out (FIFO) multiplexers majorization theory optical buffers optical queues optical switches Schur convex function
Content Type	Text
Resource Type	Article
Subject	Library and Information Sciences Information Systems Computer Science Applications

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

Recursive Constructions of Parallel FIFO and LIFO Queues With Switched Delay Lines

Constructions of Fault-Tolerant Optical 2-to-1 FIFO Multiplexers

Constructions of optical FIFO queues

Handling Priorities in Optical Buffers

A Necessary and Sufficient Condition for the Construction of 2-to-1 Optical FIFO Multiplexers by a Single Crossbar Switch and Fiber Delay Lines

Recursive construction of FIFO optical multiplexers with switched delay lines

Average Number of Recirculations in SDL Constructions of Optical Priority Queues

Constructions of Optical Priority Queues With Multiple Inputs and Multiple Outputs

Constructing $N$ -to-$N$ Shared Optical Queues With Switches and Fiber Delay Lines

Constructions of Optical 2-to-1 FIFO Multiplexers With a Limited Number of Recirculations

Similar Documents

Recursive Constructions of Parallel FIFO and LIFO Queues With Switched Delay Lines

Constructions of Fault-Tolerant Optical 2-to-1 FIFO Multiplexers

Constructions of optical FIFO queues

Handling Priorities in Optical Buffers

A Necessary and Sufficient Condition for the Construction of 2-to-1 Optical FIFO Multiplexers by a Single Crossbar Switch and Fiber Delay Lines

Recursive construction of FIFO optical multiplexers with switched delay lines

Average Number of Recirculations in SDL Constructions of Optical Priority Queues

Constructions of Optical Priority Queues With Multiple Inputs and Multiple Outputs

Constructing $N$ -to-$N$ Shared Optical Queues With Switches and Fiber Delay Lines

Constructions of Optical 2-to-1 FIFO Multiplexers With a Limited Number of Recirculations