Recursive first fit: a highly parallel optimal solution to spectrum allocation

George N. Rouskas; Chaitanya Bandikatla

doi:10.1364/JOCN.445492

Journal of Optical Communications and Networking
Vol. 14,
Issue 4,
pp. 165-176
(2022)
•https://doi.org/10.1364/JOCN.445492

Recursive first fit: a highly parallel optimal solution to spectrum allocation

George N. Rouskas and Chaitanya Bandikatla

Get PDF
Email
Share
Get Citation
Copy Citation Text
George N. Rouskas and Chaitanya Bandikatla, "Recursive first fit: a highly parallel optimal solution to spectrum allocation," J. Opt. Commun. Netw. 14, 165-176 (2022)

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

Related Topics
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: October 8, 2021
- Revised Manuscript: December 30, 2021
- Manuscript Accepted: December 31, 2021
- Published: February 8, 2022

Accepted Manuscript
Download Accepted Manuscript
Access to this article is made available via and is subject to Optica Publishing Group Terms of Use.

Abstract

We revisit the classical spectrum allocation (SA) problem, a fundamental subproblem in optical network design, and make three contributions. First, we show how some SA problem instances may be decomposed into smaller instances that may be solved independently without loss of optimality. Second, we prove an optimality property of the well-known first-fit (FF) heuristic. Finally, we leverage this property to develop a recursive and parallel algorithm that applies the FF heuristic to find an optimal solution efficiently. This recursive FF algorithm is highly scalable because of two unique properties: (1) it completely sidesteps the symmetry inherent in SA and hence drastically reduces the solution space compared to typical integer linear programming formulations, and (2) the solution space can be naturally decomposed in non-overlapping subtrees that may be explored in parallel almost independently of each other, resulting in faster than linear speedup.

Full Article | PDF Article

More Like This

Symmetry-free algorithm for spectrum allocation: parallel implementations and evaluation

George N. Rouskas, Shubham Gupta, and Priya Sharma
J. Opt. Commun. Netw. 15(10) E40-E50 (2023)

Towards Elastic and Fine-Granular Bandwidth Allocation in Spectrum-Sliced Optical Networks

Yang Wang, Xiaojun Cao, Qian Hu, and Yi Pan
J. Opt. Commun. Netw. 4(11) 906-917 (2012)

Spectrum Assignment in Optical Networks: A Multiprocessor Scheduling Perspective

Sahar Talebi, Evripidis Bampis, Giorgio Lucarelli, Iyad Katib, and George N. Rouskas
J. Opt. Commun. Netw. 6(8) 754-763 (2014)

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 (6)

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 (2)

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

		FF	RFF
	Traffic	% from LB	% from LB	# Instances $<$ FF	# Instances = LB	Avg. Diff. (Slots)
NSFNET	Skewed high	9.28%	5.46%	53	20	3.78
	Skewed low	11.73%	6.55%	52	26	2.65
	Uniform	10.12%	6.01%	47	23	3.08
GEANT2	Skewed high	2.66%	1.22%	79	14	8.44
	Skewed low	6.58%	3.54%	77	30	7.76
	Uniform	2.88%	1.37%	71	33	6.47

# Threads	Solution $<$ FF	Metric	1 h	2 h	3 h	4 h	5 h
4	54, thread #4, at 4 s	# leaves visited	34,296	66,272	93,306	131,155	163,585
		# branches trimmed	216,663	418,252	588,868	827,575	1,032,258
8	54, thread #7 at 4.3 s	# leaves visited	69,273	134,123	188,173	263,795	328,588
		# branches trimmed	434,245	838,736	1,176,169	1,648,114	2,052,756
12	54, thread #4 at 4.6 s	# leaves visited	127,182	246,496	345,935	485,053	604,269
		# branches trimmed	628,374	1,214,951	1,703,769	2,388,076	2,974,743
16	54, thread #15 at 4.2 s	# leaves visited	209,913	406843	570967	800663	997538
		# branches trimmed	929,582	1,798,143	2,521,971	3,535,185	4,403,676
20	56, 54, thread #1, #18 at	# leaves visited	275,740	5,59,773	843,719	1,127,720	1,411,716
	4, 4.1 s, respectively	# branches trimmed	1,136,325	2,302,512	3,468,185	4,634,389	5,800,467
24	54, thread #1 at 4.4 s	# leaves visited	339,936	688,602	1,037,170	1,385,642	1,734,152
		# branches trimmed	1,334,599	2,698,611	4,062,554	5,426,799	6,790,888
32	54, thread #20 at 4.3 s	# leaves visited	469,795	930,734	1,391,734	1,852,580	2,313,480
		# branches trimmed	2,000,565	3,956,799	5,913,386	7,868,762	9,824,610

# Threads	Solution $<$ FF	Metric	1 h	2 h	3 h	4 h	5 h
4	N/A	# leaves visited	29,876	60,526	91,167	121,817	152,466
		# branches trimmed	51,533	104,193	156,846	209,507	262,157
8	N/A	# leaves visited	33,007	68,333	103,657	138,984	174,322
		# branches trimmed	241,861	499,835	757,688	1,015,629	1,273,617
12	N/A	# leaves visited	32,797	68,037	103,282	138,510	173,755
		# branches trimmed	348,867	722,884	1,096,902	1,470,812	1,844,861
16	N/A	# leaves visited	27,625	58,646	89,632	120,635	151,622
		# branches trimmed	426,081	902,905	1,379,765	1,856,722	2,33,3593
20	227, thread #18 at 33 s	# leaves visited	7831	17,797	27,765	37,733	47,679
		# branches trimmed	836,549	1,780,946	2,725,429	3,669,986	4,612,521
24	227, thread #18 at 42 s	# leaves visited	7147	15,622	24,078	32,541	41,009
		# branches trimmed	927,868	1,894,965	2,862,343	3,829,659	4,797,085
32	226, thread #26 at 41 s	# leaves visited	8241	17,536	26,835	36,136	45,436
		# branches trimmed	1,298,205	2,703,580	4,108,992	5,514,505	6,919,965

		FF	RFF
	Traffic	% from LB	% from LB	# Instances $<$ FF	# Instances = LB	Avg. Diff. (Slots)
NSFNET	Skewed high	9.28%	5.46%	53	20	3.78
	Skewed low	11.73%	6.55%	52	26	2.65
	Uniform	10.12%	6.01%	47	23	3.08
GEANT2	Skewed high	2.66%	1.22%	79	14	8.44
	Skewed low	6.58%	3.54%	77	30	7.76
	Uniform	2.88%	1.37%	71	33	6.47

# Threads	Solution $<$ FF	Metric	1 h	2 h	3 h	4 h	5 h
4	54, thread #4, at 4 s	# leaves visited	34,296	66,272	93,306	131,155	163,585
		# branches trimmed	216,663	418,252	588,868	827,575	1,032,258
8	54, thread #7 at 4.3 s	# leaves visited	69,273	134,123	188,173	263,795	328,588
		# branches trimmed	434,245	838,736	1,176,169	1,648,114	2,052,756
12	54, thread #4 at 4.6 s	# leaves visited	127,182	246,496	345,935	485,053	604,269
		# branches trimmed	628,374	1,214,951	1,703,769	2,388,076	2,974,743
16	54, thread #15 at 4.2 s	# leaves visited	209,913	406843	570967	800663	997538
		# branches trimmed	929,582	1,798,143	2,521,971	3,535,185	4,403,676
20	56, 54, thread #1, #18 at	# leaves visited	275,740	5,59,773	843,719	1,127,720	1,411,716
	4, 4.1 s, respectively	# branches trimmed	1,136,325	2,302,512	3,468,185	4,634,389	5,800,467
24	54, thread #1 at 4.4 s	# leaves visited	339,936	688,602	1,037,170	1,385,642	1,734,152
		# branches trimmed	1,334,599	2,698,611	4,062,554	5,426,799	6,790,888
32	54, thread #20 at 4.3 s	# leaves visited	469,795	930,734	1,391,734	1,852,580	2,313,480
		# branches trimmed	2,000,565	3,956,799	5,913,386	7,868,762	9,824,610

Abstract

Cited By

Figures (6)

Tables (5)

Equations (2)

Journal of Optical Communications and Networking