Một phương pháp chính xác theo cách tiếp cận từ điển cho bài toán cặp đường tối đa phân tán rủi ro/chi phí tối thiểu trong các mạng viễn thông

Top - 2022
Marta Pascoal1, José Craveirinha2, João Clímaco2
1Department of Mathematics, University of Coimbra, CMUC, 3001-501, Coimbra, Portugal
2Institute for Systems Engineering and Computers at Coimbra, Universidade de Coimbra, rua Sílvio Lima, Pólo II, 3030-290, Coimbra, Portugal

Tóm tắt

Tóm tắtBài báo này nghiên cứu bài toán cặp đường tối đa phân tán rủi ro/chi phí tối thiểu, nhắm đến việc tìm một cặp đường giữa hai nút đã cho, với đường ngắn nhất (về mặt chi phí) trong số những đường có ít rủi ro chung nhất. Bài toán này đặc biệt quan trọng trong thiết kế mạng viễn thông, liên quan đến các mô hình định tuyến đáng tin cậy, ở đó cả đường chính và đường dự phòng cần phải được tính toán để tối thiểu hóa nguy cơ thất bại của kết nối giữa các nút nguồn và đích, trong trường hợp có sự cố xảy ra dọc theo đường chính và chi phí định tuyến băng thông cũng cần được tối thiểu hóa. Một thuật toán tổ hợp chính xác được đề xuất nhằm giải quyết bài toán này, kết hợp giữa phương pháp phân hạng đường và thuật toán gán nhãn đường. Ngoài ra, một công thức lập trình toàn số (ILP) cũng được trình bày để so sánh. Sau khi lý giải lý thuyết về cơ sở thuật toán, bài viết được mô tả và thử nghiệm, cùng với quy trình ILP, đối với một tập hợp các mạng tham khảo trong ngành viễn thông, xem xét các rủi ro được tạo ra ngẫu nhiên, liên quan đến Nhóm Liên kết Rủi ro Chung (SRLG) và chi phí nhánh. Cả hai phương pháp đều có khả năng giải quyết các trường hợp bài toán trong thời gian tương đối ngắn và, nói chung, thuật toán đề xuất rõ ràng nhanh hơn so với công thức ILP, ngoại trừ đối với các mạng có kích thước lớn nhất và độ kết nối cao.

Từ khóa


Tài liệu tham khảo

Betker A, Gerlach C, Hülsermann R, Jäger M, Barry M, Bodamer S, Späth J, Gauger C, Köhn M (2003) Reference transport network scenarios. Technical report

Clímaco J, Craveirinha J (2019) MCDA/M in telecommunication networks: challenges and trends. Chapman and Hall/CRC, New York, pp 11–55

Clímaco J, Pascoal M (2012) Multicriteria path and tree problems: discussion on exact algorithms and applications. Int Trans Oper Res 19:63–98

Clímaco J, Craveirinha J, Girão-Silva R (2016) Multicriteria analysis in telecommunication network planning and design: a survey, vol 233. Springer, New York, pp 1167–1233

Gomes T, Jorge L, Melo P, Girão-Silva R, Mendes S (2013a) Calculating a maximally node and SRLG-disjoint path pair of min-sum cost in GMPLS networks. In: 9th International conference on the design of reliable communication networks (DRCN 2013), pp 314–321

Gomes T, Simões C, Fernandes L (2013b) Resilient routing in optical networks using SRLG-disjoint path pairs of min-sum cost. Telecommun Syst J 52(2):737–749

Gomes T, Jorge L, Melo P, Girão-Silva R (2016) Maximally node and SRLG-disjoint path pair of min-sum cost in GMPLS networks: a lexicographic approach. Photon Netw Commun 31(1):11–22

Hu JQ (2003) Diverse routing in optical mesh networks. IEEE Trans Commun 51(3):489–494

Katoh N, Ibaraki T, Mine H (1982) An efficient algorithm for $$K$$ shortest simple paths. Networks 12:411–427

Maesschalck SD, Colle D, Lievens I, Pickavet M, Demeester P, Mauz C, Jäger M, Inkret R, Mikac B, Derkacz J (2003) Pan-European optical transport networks: an availability-based comparison. Photon Netw Commun 5:203–225

Martins E, Pascoal M, Santos J (1999) Deviation algorithms for ranking shortest paths. Int J Found Comput Sci 10:247–263

NOBEL. Next generation optical networks for broadband European leadership. http://www.ist-nobel.org (Accessed 25 Nov 2019)

Orlowski SM, Pióro RW, Tomaszewski A (2010) SNDlib 1.0—survivable network design library. Networks 55(3):276–286

Rak J (2015) Resilient routing in communication networks. Springer, Berlin

Rostami M, Khorsandi S, Khodaparast A (2007) Cose: a SRLG-disjoint routing algorithm. In: Fourth European conference on universal multiservice networks (ECUMN’07), pp 86–92

Silva J, Gomes T, Fernandes L, Simões C, Craveirinha J (2011An heuristic for maximally SRLG-disjoint path pairs calculation. In: 2011 3rd international congress on ultra modern telecommunications and control systems and workshops (ICUMT), pp 1–8

Todimala A, Ramamurthy B (2004) IMSH: an iterative heuristic for SRLG diverse routing in WDM mesh networks. In: Proceedings 13th international conference on computer communications and networks (ICCCN 2004). IEEE, pp 199–204

Xu D, Xiong Y, Qiao C, Li G (2003) Trap avoidance and protection schemes in networks with shared risk link groups. J Lightw Technol 21(11):2683–2693

Yen J (1971) Finding the $$K$$ shortest loopless paths in a network. Manag Sci 17:712–716

Thông tin
Thông tin xuất bản

Top

Thông tin tác giả