Pseudo-Banyan Optical WDM Packet Switching System With Near-Optimal Packet Scheduling

Maria C. Yuang; Po-Lung Tien; Shih-Hsuan Lin

doi:10.1364/JOCN.1.0000B1

Journal of Optical Communications and Networking
Vol. 1,
Issue 3,
pp. B1-B14
(2009)
•https://doi.org/10.1364/JOCN.1.0000B1

Pseudo-Banyan Optical WDM Packet Switching System With Near-Optimal Packet Scheduling

Maria C. Yuang, Po-Lung Tien, and Shih-Hsuan Lin

Not Accessible

Your library or personal account may give you access

Get PDF
Email
Share
Get Citation
Copy Citation Text
Maria C. Yuang, Po-Lung Tien, and Shih-Hsuan Lin, "Pseudo-Banyan Optical WDM Packet Switching System With Near-Optimal Packet Scheduling," J. Opt. Commun. Netw. 1, B1-B14 (2009)

Export Citation
- BibTex
- Endnote (RIS)
- HTML
- Plain Text
Citation alert
Save article

Related Topics
Table of Contents Category
- Architectures and Technologies for Ultra-High Capacity Switched and Routed Optical Networks
Optics & Photonics Topics
?

The topics in this list come from the Optics and Photonics Topics applied to this article.

About this Article
History
- Original Manuscript: November 28, 2008
- Revised Manuscript: March 30, 2009
- Manuscript Accepted: May 3, 2009
- Published: July 28, 2009

Abstract

We present a novel pseudo-Banyan optical packet switching system (SBOPSS) for optical wavelength division multiplexing (WDM) networks. The system includes a group of pseudo-Banyan space switches together with single-stage downsized fiber-delay-line-based optical buffers. SBOPSS is scalable, with the result that each pseudo-Banyan space switch performs packet switching only for a cluster of wavelengths. The downsized optical buffers that are shared by output ports via the use of a small number of internal wavelengths result in efficient reduction in packet loss. Essentially, SBOPSS employs a packet scheduling algorithm, referred to as the parallel and incremental packet scheduler (PIPS). Given a set of newly arriving packets per time slot, PIPS determines a maximum number of valid paths (packets) to be scheduled with the current buffers’ state taken into account. The algorithm aims at maximizing the system throughput subject to satisfying three constraints, which are switch-contention free, buffer-contention free, and sequential delivery. Significantly, we prove that PIPS is incremental in the sense that the computed-path sets are monotonically nondecreasing over time. We then propose a hardware parallel system architecture for the implementation of PIPS. As is shown, PIPS achieves a near-optimal solution with an exceptionally low computational complexity, $O (∣ P ∣ \times \log_{2} (N M W))$ , where P is the newly-arriving-packet set, N the number of input ports, and M and W the numbers of internal and external wavelengths, respectively. From simulation results that pit the PIPS algorithm against four other algorithms, we show that PIPS outperforms these algorithms on both system throughput and computational complexity.

Full Article | PDF Article

More Like This

Optical Packet Contention Resolution Through Edge Smoothing Into Decomposed Subflows

Zheng Lu and David K. Hunter
J. Opt. Commun. Netw. 1(7) 622-635 (2009)

Development of a 640-Gbit∕s∕port Optical Packet Switch Prototype Based on Wide-Colored Optical Packet Technology

Hideaki Furukawa, Naoya Wada, Hiroaki Harai, and Tetsuya Miyazaki
J. Opt. Commun. Netw. 1(3) B30-B39 (2009)

Exact Analysis of Single-Wavelength Optical Buffers With Feedback Markov Fluid Queues

Huseyin Emre Kankaya and Nail Akar
J. Opt. Commun. Netw. 1(6) 530-542 (2009)

Previous Article Next Article

Cited By

You do not have subscription access to this journal. Cited by links are available to subscribers only. You may subscribe either as an Optica member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Login to access Optica Member Subscription

Figures (4)

You do not have subscription access to this journal. Figure files are available to subscribers only. You may subscribe either as an Optica member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Login to access Optica Member Subscription

Tables (5)

You do not have subscription access to this journal. Article tables are available to subscribers only. You may subscribe either as an Optica member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Login to access Optica Member Subscription

Equations (1)

You do not have subscription access to this journal. Equations are available to subscribers only. You may subscribe either as an Optica member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Login to access Optica Member Subscription

PBS Size	Method	Load
PBS Size	Method	0.55	0.65	0.75	0.85	0.95
$8 \times 8$ ( $N = 2$ , $W = 4$ )	Optimal (Exhaustive)	BP: 100%	BP: 99.94%	BP: 99.48%	BP: 96.78%	BP: 92.3%
	Optimal (Exhaustive)	IBP: 99.98%	IBP: 99.9%	IBP: 99.14%	IBP: 96.46%	IBP: 91.98%
	PIPS	BP: 99.84%	BP: 99.23%	BP: 97.66%	BP: 95.08%	BP: 91.05%
	PIPS	IBP: 99.83%	IBP: 99.21%	IBP: 97.71%	IBP: 94.8%	IBP: 90.74%
$16 \times 16$ ( $N = 4$ , $W = 4$ )	PIPS	BP: 98.67%	BP: 98.26%	BP: 96.08%	BP: 92.51%	BP: 87.13%
	PIPS	IBP: 98.54%	IBP: 98.1%	IBP: 95.79%	IBP: 92.19%	IBP: 86.79%
	JMinD	BP: 98.19%	BP: 95.93%	BP: 93.14%	BP: 92.19%	BP: 85.62%
	JMinD	IBP: 97.78%	IBP: 95.2%	IBP:93.05%	IBP: 91.73%	IBP: 85.34%
	JMaxS	BP: 97.91%	BP: 95.29%	BP: 90.86%	BP: 86.72%	BP: 81.59%
	JMaxS	IBP: 97.78%	IBP: 94.98%	IBP: 90.93%	IBP: 86.29%	IBP: 81.11%
	SMinB	BP: 90.31%	BP: 86.39%	BP: 80.62%	BP: 75.13%	BP: 70.54%
	SMinB	IBP: 90.09%	IBP: 85.8%	IBP: 80.27%	IBP: 75.48%	IBP: 70.22%
	SMinD	BP: 70.13%	BP: 68.56%	BP: 65.74%	BP: 63.95%	BP: 61.59%
	SMinD	IBP: 70.65%	IBP:68.42%	IBP: 65.73%	IBP: 64.09%	IBP: 61.61%
$32 \times 32$ ( $N = 8$ , $W = 4$ )	PIPS	BP: 96%	BP: 94.06%	BP: 91.17%	BP: 86.84%	BP: 81.96%
	PIPS	IBP: 96.1%	IBP: 94.06%	IBP: 91.05%	IBP: 86.77%	IBP: 81.8%
	JMinD	BP: 94.3%	BP: 91.73%	BP: 89.33%	BP: 85.36%	BP: 79.24%
	JMinD	IBP: 94.26%	IBP: 91.81%	IBP: 89.35%	IBP: 85.17%	IBP: 79.43%
	JMaxS	BP: 94.54%	BP: 90.16%	BP: 84.89%	BP: 79.4%	BP: 73.94%
	JMaxS	IBP: 94.57%	IBP: 90.08%	IBP: 84.56%	IBP: 79.32%	IBP: 74.12%
	SMinB	BP: 85.65%	BP: 80.14%	BP: 74.16%	BP: 68.94%	BP: 64.21%
	SMinB	IBP: 85.86%	IBP: 79.82%	IBP: 74.1%	IBP: 68.9%	IBP: 64.31%
	SMinD	BP: 65.32%	BP: 62.47%	BP: 60.39%	BP: 57.57%	BP: 54.86%
	SMinD	IBP: 65.3%	IBP: 62.57%	IBP: 59.88%	IBP: 57.39%	IBP: 54.91%

PBS Size	Buffer Size	0.55	0.65	0.75	0.85	0.95
$16 \times 16$ ( $N = 4$ , $W = 4$ )	$D = 1$ , $M = 4$ $(B = 0)$	90.5%	87.57%	84.06%	81.48%	78.8%
	$D = 4$ , $M = 4$ $(B = 12)$	98.67%	98.26%	96.08%	92.51%	87.13%
	$D = 8$ , $M = 8$ $(B = 56)$	98.67%	98.4%	97%	92.72%	87.5%
$32 \times 32$ ( $N = 8$ , $W = 4$ )	$D = 1$ , $M = 8$ $(B = 0)$	86.32%	82.1%	77.81%	74.11%	70.19%
	$D = 4$ , $M = 8$ $(B = 24)$	95.84%	93.67%	90.36%	86.31%	81.47%
	$D = 8$ , $M = 8$ $(B = 56)$	96%	94.06%	91.17%	86.84%	81.96%

Category	Architecture	No. of $2 \times 2$ Switching Elements	Splitter No.	Coupler No.
Nonblocking space switches	CrossBar [3]	${(N W)}^{2}$	0	0
	Broadcast and select [24]	$N^{2} W$	$N W$	$N W$
	Cantor [4]	$N W ∕ 2 \times (2 \log_{2} (N W) - 1) \times \log_{2} (N W)$	$N W$	$N W$
	Strictly nonblocking Clos [15]	$2 N W (2 W - 1) + (2 W - 1) N^{2}$	0	0
Rearrangeable space switches	Rearrangeable Clos [4]	$2 N W^{2} + W N^{2}$	0	0
Rearrangeable space switches	Benes [25]	$N W ∕ 2 \times (2 \log_{2} (N W) - 1)$	0	0
Blocking space switches	SBOPSS	$N W ∕ 2 \times \log_{2} (N W ∕ C)$	0	0

Category	Architecture	No. of $2 \times 2$ Switching Elements (Signal Impairment)	Splitter and Coupler (Output/Input Power)
Nonblocking space switches	CrossBar [3]	$2 N W$	N/A
	Broadcast and select [24]	1	$1 ∕ N^{2}$
	Cantor [4]	$2 \log_{2} (N W) - 1$	${(1 ∕ \log_{2} (N W))}^{2}$
	Strictly nonblocking Clos [15]	$4 W (2 W - 1) + 2 N^{2}$	N/A
Rearrangeable space switches	Rearrangeable Clos [4]	$4 W^{2} + 2 N^{2}$	N/A
Rearrangeable space switches	Benes [25]	$2 \log_{2} (N W) - 1$	N/A
Blocking space switches	SBOPSS	$\log_{2} (N W ∕ C)$	N/A

PBS Size	Method	Load
PBS Size	Method	0.55	0.65	0.75	0.85	0.95
$8 \times 8$ ( $N = 2$ , $W = 4$ )	Optimal (Exhaustive)	BP: 100%	BP: 99.94%	BP: 99.48%	BP: 96.78%	BP: 92.3%
	Optimal (Exhaustive)	IBP: 99.98%	IBP: 99.9%	IBP: 99.14%	IBP: 96.46%	IBP: 91.98%
	PIPS	BP: 99.84%	BP: 99.23%	BP: 97.66%	BP: 95.08%	BP: 91.05%
	PIPS	IBP: 99.83%	IBP: 99.21%	IBP: 97.71%	IBP: 94.8%	IBP: 90.74%
$16 \times 16$ ( $N = 4$ , $W = 4$ )	PIPS	BP: 98.67%	BP: 98.26%	BP: 96.08%	BP: 92.51%	BP: 87.13%
	PIPS	IBP: 98.54%	IBP: 98.1%	IBP: 95.79%	IBP: 92.19%	IBP: 86.79%
	JMinD	BP: 98.19%	BP: 95.93%	BP: 93.14%	BP: 92.19%	BP: 85.62%
	JMinD	IBP: 97.78%	IBP: 95.2%	IBP:93.05%	IBP: 91.73%	IBP: 85.34%
	JMaxS	BP: 97.91%	BP: 95.29%	BP: 90.86%	BP: 86.72%	BP: 81.59%
	JMaxS	IBP: 97.78%	IBP: 94.98%	IBP: 90.93%	IBP: 86.29%	IBP: 81.11%
	SMinB	BP: 90.31%	BP: 86.39%	BP: 80.62%	BP: 75.13%	BP: 70.54%
	SMinB	IBP: 90.09%	IBP: 85.8%	IBP: 80.27%	IBP: 75.48%	IBP: 70.22%
	SMinD	BP: 70.13%	BP: 68.56%	BP: 65.74%	BP: 63.95%	BP: 61.59%
	SMinD	IBP: 70.65%	IBP:68.42%	IBP: 65.73%	IBP: 64.09%	IBP: 61.61%
$32 \times 32$ ( $N = 8$ , $W = 4$ )	PIPS	BP: 96%	BP: 94.06%	BP: 91.17%	BP: 86.84%	BP: 81.96%
	PIPS	IBP: 96.1%	IBP: 94.06%	IBP: 91.05%	IBP: 86.77%	IBP: 81.8%
	JMinD	BP: 94.3%	BP: 91.73%	BP: 89.33%	BP: 85.36%	BP: 79.24%
	JMinD	IBP: 94.26%	IBP: 91.81%	IBP: 89.35%	IBP: 85.17%	IBP: 79.43%
	JMaxS	BP: 94.54%	BP: 90.16%	BP: 84.89%	BP: 79.4%	BP: 73.94%
	JMaxS	IBP: 94.57%	IBP: 90.08%	IBP: 84.56%	IBP: 79.32%	IBP: 74.12%
	SMinB	BP: 85.65%	BP: 80.14%	BP: 74.16%	BP: 68.94%	BP: 64.21%
	SMinB	IBP: 85.86%	IBP: 79.82%	IBP: 74.1%	IBP: 68.9%	IBP: 64.31%
	SMinD	BP: 65.32%	BP: 62.47%	BP: 60.39%	BP: 57.57%	BP: 54.86%
	SMinD	IBP: 65.3%	IBP: 62.57%	IBP: 59.88%	IBP: 57.39%	IBP: 54.91%

Abstract

Cited By

Figures (4)

Tables (5)

Equations (1)

Journal of Optical Communications and Networking