Solving routing and wavelength assignment problem with maximum edge-disjoint paths

Chia-Chun Hsu; Hsun-Jung Cho; Shu-Cherng Fang

doi:10.3934/jimo.2016062

Article Contents

2017, Volume 13, Issue 2: 1065-1084. Doi: 10.3934/jimo.2016062

This issue Previous Article A multi-objective integrated model for closed-loop supply chain configuration and supplier selection considering uncertain demand and different performance levels Next Article Two-echelon supply chain model with manufacturing quality improvement and setup cost reduction

Solving routing and wavelength assignment problem with maximum edge-disjoint paths

1.
Department of Transportation and Logistics Management, National Chiao Tung University, Hsinchu 300, Taiwan
2.
Department of Industrial and Systems Engineering, North Carolina State University, Raleigh, NC 27606, USA

* Corresponding author
* Corresponding author

Received: October 2014

Revised: August 2016

Published: August 2017

Abstract / Introduction Full Text(HTML) Figure(13) / Table(5) Related Papers Cited by

Abstract

The routing and wavelength assignment (RWA) problem in wave-length-division multiplexing optical networks is critically important for increasing the efficiency of wavelength-routed all-optical networks. Given the physical network structure and a set of connection requests, the problem aims to establishing routes for the requests and assigning a wavelength to each of them, subject to the wavelength continuous and wavelength clash constraints. The objective is to minimize he number of required wavelengths to satisfy all requests. The RWA problem was proven to be NP-hard and has been investigated for decades. In this paper, an algorithm based on the maximum edge-disjoint paths is proposed to tackle the RWA problem. Its performance is verified by experiments on some realistic network topologies. Compared with the state-of-the-art bin-packing based methods and the particle swarm optimization algorithm, the proposed method can find the best solution among all testing instances in reasonable computing time.

Keywords:

Edge-disjoint paths,
MEDP,
routing and wavelength assignment problem,
RWA.

Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.

Citation:

Full Text(HTML)

Figure 1. Pseudocode of FD(FFD) Algorithm

Download: Full-size image PowerPoint slide

Figure 2. Pseudocode of FD(FFD) Algorithm

Download: Full-size image PowerPoint slide

Figure 3. Pseudocode of PSO Algorithm

Download: Full-size image PowerPoint slide

Figure 4. Pseudocode of a basic MEDP-RWA algorithm

Download: Full-size image PowerPoint slide

Figure 5. Pseudocode of GMR algorithm

Download: Full-size image PowerPoint slide

Figure 6. Number of times that the best value is achieved by different methods

Download: Full-size image PowerPoint slide

Figure 7. Frequency graphs of testing results on zib54

Download: Full-size image PowerPoint slide

Figure 8. Frequency graphs of testing results on ta2

Download: Full-size image PowerPoint slide

Figure 9. Frequency graphs of testing results on Germany50

Download: Full-size image PowerPoint slide

Figure 10. Relative difference of computational time on Norway

Download: Full-size image PowerPoint slide

Figure 11. Relative difference of computational time on giul

Download: Full-size image PowerPoint slide

Figure 12. Relative difference of computational time on graph Germany

Download: Full-size image PowerPoint slide

Figure 13. Relative difference of computational time on graph ta2

Download: Full-size image PowerPoint slide

Table 1. Main quantitative characteristics of testing networks

Graph	$\left \| V \right \|$	$\left \| E \right \|$	Min.	Avg.	Max.	Diameter
CHNNET	15	27	3	3.6	5	5
NSF	16	25	2	3.1	4	4
New York	16	49	2	6.1	11	3
APPANET	20	32	3	3.2	4	6
EON	20	39	2	3.9	7	5
France	25	45	2	3.6	10	5
Norway	27	51	2	3.8	6	7
cost266	37	57	2	3.1	5	8
janos-us-ca	39	67	2	3.1	5	10
giul	39	86	3	4.4	8	6
piro40	40	89	4	4.5	5	7
USAnet	46	75	2	3.3	5	11
Germany50	50	88	2	3.5	5	9
zib54	54	80	1	3.0	10	8
ta2	65	108	1	3.3	10	8
(Min., Avg. and Max. denote the minimum, average and maximum degree, respectively)

| Show Table

DownLoad: CSV

Table 2. Results of GMR and bin-packing based methods (time unit: sec)

	GA_MEDP_RWA (GMR)				FF		FFD		BF		BFD
instance	max	avg	min	avg time	# wl	$t_{FF}$	# wl	$t_{FFD}$	# wl	$t_{BF}$	# wl	$t_{BFD}$
CHNNET_02	4	4.0	4	2.07	4	0.24	4	0.14	4	0.11	5	0.14
CHNNET_04	5	4.4	4	3.02	5	0.18	4	0.15	5	0.23	4	0.26
CHNNET_06	11	11.0	11	10.66	11	0.70	11	0.62	11	0.81	11	0.96
CHNNET_08	14	14.0	14	13.50	15	1.02	14	1.17	14	1.21	14	1.51
CHNNET_1	16	15.0	15	16.31	15	1.48	15	1.42	16	1.75	15	2.20
NSF_02	5	5.0	5	2.41	6	0.34	5	0.17	6	0.19	6	0.18
NSF_04	8	7.3	7	5.80	9	0.37	9	0.35	8	0.52	8	0.50
NSF_06	9	8.8	8	7.97	10	0.46	10	0.49	9	0.59	9	0.64
NSF_08	14	13.2	13	15.11	17	1.06	15	1.10	14	1.50	14	1.47
NSF_1	17	16.6	16	22.89	19	1.70	17	1.45	17	1.96	17	2.08
NewYork_02	2	2.0	2	1.37	2	0.14	2	0.08	2	0.07	2	0.08
NewYork_04	3	3.0	3	2.65	3	0.23	3	0.20	3	0.23	3	0.23
NewYork_06	5	4.1	4	3.93	4	0.33	4	0.34	4	0.34	4	0.33
NewYork_08	7	6.0	6	6.75	7	0.64	6	0.58	7	0.62	6	0.81
NewYork_1	8	8.0	8	7.03	8	0.73	8	0.80	8	1.02	8	2.30
ARPANET_02	10	9.1	9	10.58	9	0.55	9	0.53	9	0.64	9	0.86
ARPANET_04	13	12.1	12	16.96	12	1.05	12	1.29	12	1.31	12	1.76
ARPANET_06	21	21.0	21	25.98	21	2.70	21	2.68	21	3.39	21	4.58
ARPANET_08	29	29.0	29	32.31	30	5.46	29	6.14	30	7.82	29	10.94
ARPANET_1	33	33.0	33	62.85	34	6.85	33	7.77	34	10.19	33	12.68
EON_02	4	3.1	3	3.19	3	0.22	4	0.17	4	0.34	4	0.36
EON_04	9	8.3	8	14.74	10	1.10	9	1.14	8	1.53	8	1.54
EON_06	11	11.0	11	17.52	13	1.21	11	1.18	11	1.94	11	1.90
EON_08	14	13.7	13	26.63	16	2.20	13	2.99	13	3.61	13	3.72
EON_1	19	18.1	18	38.17	22	3.64	18	3.58	18	5.77	18	5.73
France_02	8	8.0	8	8.87	8	1.30	8	1.27	8	1.57	8	1.72
France _04	13	12.8	12	16.05	14	4.29	13	4.90	13	5.14	13	6.03
France _06	22	22.0	22	39.07	22	8.73	22	10.55	22	11.69	22	15.27
France _08	27	26.3	26	47.09	28	13.25	27	14.00	27	18.53	26	24.20
France _1	34	34.0	34	60.09	34	22.54	34	23.99	34	29.93	34	35.84

| Show Table

DownLoad: CSV

Table 3. Results of GMR and bin-packing based methods (cont'd)

	GA_MEDP_RWA (GMR)				FF		FFD		BF		BFD
instance	max	avg	min	avg time	# wl	$t_{FF}$	# wl	$t_{FFD}$	# wl	$t_{BF}$	# wl	$t_{BFD}$
Norway_02	9	8.6	8	9.26	10	1.67	8	1.78	9	1.90	8	2.17
Norway _04	15	14.6	14	18.47	15	3.75	15	4.12	15	4.56	15	5.43
Norway _06	22	21.4	21	32.84	22	7.87	22	8.20	22	9.73	22	12.32
Norway _08	30	29.5	29	46.41	31	15.05	30	16.59	31	19.79	30	24.59
Norway _1	37	36.6	36	63.77	37	21.99	36	23.75	38	28.58	36	36.13
cost266_02	19	18.2	18	46.68	19	7.34	18	7.44	19	10.38	19	12.40
cost266_04	35	34.1	33	159.69	35	27.28	33	28.58	36	36.35	35	47.28
cost266_06	54	53.1	53	237.55	54	67.18	53	70.90	55	98.00	53	117.30
cost266_08	68	67.2	67	275.29	67	120.73	68	144.22	69	190.55	68	273.40
janos-us-ca_02	26	26.0	26	54.75	27	16.61	26	16.53	27	27.40	27	27.58
janos-us-ca_04	40	39.6	39	97.42	42	49.52	39	59.49	43	70.75	40	88.45
janos-us-ca_06	68	67.8	67	210.36	71	110.99	69	124.10	72	157.50	68	200.32
janos-us-ca_08	89	88.2	88	326.39	92	199.09	92	212.16	93	257.39	91	345.67
giul_02	11	10.3	10	26.93	10	7.40	10	8.11	10	8.89	10	11.24
giul_04	21	20.2	19	82.66	19	29.10	19	31.70	19	37.42	19	46.16
giul_06	25	24.6	24	150.73	25	48.91	25	55.96	25	59.10	24	73.12
giul_08	36	34.9	34	226.85	35	113.85	34	125.20	36	134.25	34	181.70
piro40_02	17	17	17	55.51	17	10.67	17	12.58	17	15.20	17	18.50
piro40_04	28	28	28	118.50	28	34.98	28	38.00	28	43.05	28	54.44
piro40_06	46	46	46	208.81	46	61.98	46	68.00	46	84.33	46	109.15
piro40_08	60	60	60	338.61	60	105.97	60	119.35	60	140.20	60	181.52
USAnet_02	25	24.0	23	86.13	25	35.62	26	37.95	26	45.15	25	56.09
USAnet_04	47	45.9	45	355.64	47	130.43	45	147.76	48	176.43	45	228.50
USAnet_06	67	66.1	65	422.63	68	244.00	65	287.58	68	346.66	66	432.89
USAnet_08	88	86.5	85	490.20	88	475.69	85	544.98	89	587.11	86	791.38
Germany50_02	21	20.7	20	109.28	21	35.86	21	36.10	21	46.10	22	58.58
Germany50_04	45	44.2	43	350.24	45	152.90	44	163.00	48	217.60	48	276.50
Germany50_06	61	60.5	60	584.92	63	347.70	61	410.61	63	430.89	65	544.74
Germany50_08	76	74.7	73	921.59	77	552.50	75	725.90	79	843.70	76	1098.40
zib54_02	32	31.1	30	149.44	33	52.28	31	55.01	35	77.70	33	91.67
zib54_04	67	65.7	65	406.90	67	209.80	65	220.50	73	304.64	71	379.55
zib54_06	92	90.0	88	762.56	91	442.95	89	522.85	99	696.78	98	889.98
zib54_08	122	119.2	117	1446.41	117	994.60	117	939.60	130	1229.60	127	1457.22
ta2_02	35	34.6	34	411.59	35	148.93	34	163.00	35	188.75	35	250.99
ta2_04	72	70.1	69	945.79	72	507.30	69	542.50	73	635.57	70	813.04
ta2_06	99	97.4	96	1865.20	98	1311.70	98	1484.00	100	1881.30	97	2047.40
ta2_08	131	129.7	128	2835.57	130	1935.30	129	2577.90	135	2644.43	128	3713.46

| Show Table

DownLoad: CSV

Table 4. Results of GMR and PSO (time unit: sec)

	GA_MEDP_RWA				PSO
instance	max	avg	min	avg time	max	avg	min	avg time
CHNNET_02	4	4.0	4	2.07	7	5.9	5	12.97
CHNNET_04	5	4.4	4	3.02	9	7.5	7	18.60
CHNNET_06	11	11.0	11	10.66	18	15.5	13	30.39
CHNNET_08	14	14.0	14	13.50	24	20.4	18	48.95
CHNNET_1	16	15.0	15	16.31	25	21.5	18	78.96
NSF_02	5	5.0	5	2.41	7	6.0	5	6.75
NSF_04	8	7.3	7	5.80	10	9.0	8	13.75
NSF_06	9	8.8	8	7.97	11	10.0	9	16.19
NSF_08	14	13.2	13	15.11	17	15.5	14	29.02
NSF_1	17	16.6	16	22.89	20	18.9	18	36.03
NewYork_02	2	2.0	2	1.37	3	2.9	2	7.37
NewYork _04	3	3.0	3	2.65	6	5.2	4	18.78
NewYork _06	5	4.1	4	3.93	8	6.8	6	25.51
NewYork _08	7	6.0	6	6.75	10	9.1	8	38.35
NewYork _1	8	8.0	8	7.03	12	10.7	10	50.17
ARPANET_02	10	9.1	9	10.58	13	11.3	10	21.30
ARPANET_04	13	12.1	12	16.96	19	16.3	14	62.15
ARPANET_06	21	21.0	21	25.98	28	24.9	22	93.86
ARPANET_08	29	29.0	29	32.31	40	36.5	33	133.70
ARPANET_1	33	33.0	33	62.85	46	41.2	36	172.60
EON_02	4	3.1	3	3.19	5	4.3	4	10.40
EON_04	9	8.3	8	14.74	12	10.6	10	35.34
EON_06	11	11.0	11	17.52	15	13.0	12	46.61
EON_08	14	13.7	13	26.63	20	18.2	17	48.92
EON_1	19	18.1	18	38.17	25	22.9	22	73.32
France_02	8	8.0	8	8.87	14	11.5	10	50.60
France _04	13	12.8	12	16.05	22	19.3	17	86.48
France _06	22	22.0	22	39.07	34	30.4	27	129.16
France _08	27	26.3	26	47.09	45	40.3	38	290.72
France _1	34	34.0	34	60.09	54	48.9	45	236.64

| Show Table

DownLoad: CSV

Table 5. Results of GMR and PSO (con't)

	GA_MEDP_RWA				PSO
instance	max	avg	min	avg time	max	avg	min	avg time
Norway_02	9	8.6	8	9.26	15	13.1	11	61.56
Norway _04	15	14.6	14	18.47	25	22.5	20	101.40
Norway _06	22	21.4	21	32.84	37	32.6	29	202.11
Norway _08	30	29.5	29	46.41	48	43.6	40	254.75
Norway _1	37	36.6	36	63.77	59	54.1	49	323.64
cost266_02	19	18.2	18	46.68	26	23.8	21	105.22
cost266_04	35	34.1	33	159.69	54	50.9	47	239.95
cost266_06	54	53.1	53	237.55	79	73.2	70	436.38
cost266_08	68	67.2	67	275.29	99	93.4	88	703.53
janos-us-ca_02	26	26.0	26	54.75	40	36.1	31	288.18
janos-us-ca_04	40	39.6	39	97.42	66	60.5	56	529.74
janos-us-ca_06	68	67.8	67	210.36	111	102.7	94	959.93
janos-us-ca_08	89	88.2	88	326.39	144	134.1	122	1239.46
giul_02	11	10.3	10	26.93	16	14.5	13	294.44
giul_04	21	20.2	19	82.66	32	28.8	26	451.61
giul_06	25	24.6	24	150.73	42	38.3	34	738.65
giul_08	36	34.9	34	226.85	59	53.5	49	990.63
piro40_02	17	17	17	55.51	22	20.0	19	159.88
piro40_04	28	28	28	118.50	36	33.7	32	300.88
piro40_06	46	46	46	208.81	66	58.7	52	474.73
piro40_08	60	60	60	338.61	86	79.4	73	684.40
USAnet_02	25	24.0	23	86.13	40	36.4	32	446.56
USAnet_04	47	45.9	45	355.64	76	69.5	65	983.93
USAnet_06	67	66.1	65	422.63	106	98.1	92	1418.73
USAnet_08	88	86.5	85	490.20	139	126.5	120	1715.20
Germany50_02	21	20.7	20	109.28	37	33.5	31	379.56
Germany50_04	45	44.2	43	350.24	74	69.4	66	683.95
Germany50_06	61	60.5	60	584.92	102	95.7	91	969.87
Germany50_08	76	74.7	73	921.59	126	120.5	115	1271.90
zib54_02	32	31.1	30	149.44	75	64.1	58	619.63
zib54_04	67	65.7	65	406.90	159	141.6	133	1462.19
zib54_06	92	90.0	88	762.56	208	195.2	187	2955.29
zib54_08	122	119.2	117	1446.41	289	266.3	250	4147.09
ta2_02	35	34.6	34	411.59	75	70.3	66	1453.68
ta2_04	72	70.1	69	945.79	152	141.8	133	2852.21
ta2_06	99	97.4	96	1865.20	208	198.7	181	3867.39
ta2_08	131	129.7	128	2835.57	284	271.0	258	5953.52

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	D. Banerjee and B. Mukherjee, A practical approach for routing and wavelength assignment in large wavelength-routed optical networks, IEEE Journal on Selected Areas in Communications, 14 (1996), 903-908. doi: 10.1109/49.510913.
[2]	M. J. Blesa and C. Blum, Findinge edge-disjoint paths in networks: An ant colony optimization algorithm, Journal of Mathematical Modeling and Algorithms, 6 (2007), 367-391. doi: 10.1007/s10852-007-9060-y.
[3]	I. Chlamtac, A. Ganz and G. Karmi, Lightpath communications: an approach to high bandwidth optical WAN's, IEEE Transactions on Communications, 40 (1992), 1171-1182. doi: 10.1109/26.153361.
[4]	J. S. Choi, N. Golmie, F. Lapeyrere, F. Mouveaux and D. Su, A functional classification of routing and wavelength assignment schemes in DWDM networks: Static Case, In Proceedings of the 7th International Conference on Optical Communications and Networks, (2000), 1109-1115.
[5]	H. Choo and V. V. Shakhov, Routing and wavelength assignment in optical WDM networks with maximum quantity of edge disjoint paths, Computational Science -ICCS 2004, 3038 (2004), 1138-1145. doi: 10.1007/978-3-540-24688-6_147.
[6]	T. Fischer, K. Bauer, P. Merz and K. Bauer, Solving the routing and wavelength assignment problem with a multilevel distributed memetic algorithm, Memetic Computing, 1 (2009), 101-123. doi: 10.1007/s12293-008-0006-3.
[7]	X. Guan, S. Guo, W. Gong and C. Qiao, A new method for solving routing and wavelength assignment problems in optical networks, Journal of Lightwave Technology, 25 (2007), 1895-1909. doi: 10.1109/JLT.2007.901344.
[8]	A. Hassan, Particle Swarm Optimization for Routing and Wavelength Assignment in Next Generation WDM Networks, Ph. D thesis, Queen Mary University of London, 2010.
[9]	C.-C. Hsu and H.-J. Cho, A genetic algorithm for the maximum edge-disjoint paths problem, Neurocomputing, 148 (2015), 17-22. doi: 10.1016/j.neucom.2012.10.046.
[10]	C.-C. Hsu, H.-J. Cho and S.-C. Fang, Routing and wavelength assignment in optical networks from maximum edge-disjoint paths, Genetic and Evolutionary Computing: Advances in Intelligent Systems and Computing, 238 (2014), 95-103. doi: 10.1007/978-3-319-01796-9_10.
[11]	Y. S. Kavian, A. Rashedi, A. Mahani and Z. Ghassemlooy, Routing and wavelength assignment in optical networks using artificial bee colony algorithm, European Journal of Operational Research, 124 (2013), 1243-1249. doi: 10.1016/j.ijleo.2012.03.022.
[12]	J. Kleinberg, Approximation Algorithms for Disjoint Paths Problems, Ph. D thesis, Massachusetts Institute of Technology, 1996.
[13]	P. Leesutthipornchai, C. Charnsripinyo and N. Wattanapongsakorn, Solving multi-objective routing and wavelength assignment in WDM network using hybrid evolutionary computation approach, Computer Communications, 33 (2010), 2246-2259. doi: 10.1016/j.comcom.2010.07.029.
[14]	G. Li and R. Shmha, The partition coloring problem and its application to wavelength routing and assignment, In Proceedings of the First Workshop on Optical Networks, 2000.
[15]	P. Manohar, D. Manjunath and R. K. Shevgaonkar, Routing and wavelength assignment in optical networks from edge disjoint path algorithms, IEEE Communications Letters, 6 (2002), 211-213. doi: 10.1109/4234.1001667.
[16]	A. X. Martins, C. Duhamel, P. Mahey, R. R. Saldanha and M. C. de Souza, Variable neighborhood descent with iterated local search for routing and wavelength assignment, Computers and Operations Research, 39 (2012), 2133-2141. doi: 10.1016/j.cor.2011.10.022.
[17]	T. F. Noronha, M. G. C. Resende and C. C. Ribeiro, A biased random-key genetic algorithm for routing and wavelength assignment, Journal of Global Optimization, 50 (2011), 503-518. doi: 10.1007/s10898-010-9608-7.
[18]	T. F. Noronha and C. C. Ribeiro, Routing and wavelength assignment by partition colouring, European Journal of Operational Research, 171 (2006), 797-810. doi: 10.1016/j.ejor.2004.09.007.
[19]	A. E. Ozdaglar and D. P. Bertsekas, Routing and wavelength assignment in optical networks, IEEE/ACM Transactions on Networking, 11 (2003), 259-272. doi: 10.1109/TNET.2003.810321.
[20]	R. Poli, J. Kennedy and T. Blackwell, Particle swarm optimization -An overview, Swarm intelligence, 1 (2007), 33-57.
[21]	N. Skorin-Kapov, Routing and wavelength assignment in optical networks using bin packing based algorithms, European Journal of Operational Research, 177 (2007), 1167-1179. doi: 10.1016/j.ejor.2006.01.003.
[22]	Y. Wang, T. H. Cheng and M. H. Lim, A Tabu search algorithm for static routing and wavelength assignment problem, IEEE Communications Letters, 9 (2005), 841-843. doi: 10.1109/LCOMM.2005.1506721.
[23]	W. J. Yoon, D. H. Kim, M. Y. Chung, T. J. Lee and H. Choo, Routing with maximum EDPs and wavelength assignment with path conflict graphs, In Proceedings of the 2006 international conference on Computational Science and Its Applications, 3981 (2006), 856-865. doi: 10.1007/11751588_89.
[24]	H. Zang, J. P. Jue and B. Mukherjee, A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks, Optical Networks Magazine, 1 (2000), 47-60.