Scholarlink

<p>One of the most promising solutions to deal with huge data traffic demands in large communication networks is given by flexible optical networking, in particular the <i>flexible grid</i> (flexgrid) technology specified in the ITU-T standard G.694.1. In this specification, the frequency spectrum of an optical fiber link is divided into narrow frequency <i>slots</i>. Any sequence of consecutive slots can be used as a simple channel, and such a channel can be switched in the network nodes to create a <i>lightpath</i>. In this kind of networks, the problem of establishing lightpaths for a set of end-to-end demands that compete for spectrum resources is called the <i>routing and spectrum allocation problem</i> (RSA). Due to its relevance, this NP-hard problem has been intensively studied in the last decade. In this work we present an integer-programming-based heuristic for RSA. We propose several measures of the instance density, and we explore the performance of the proposed heuristic procedure as a function of these measures. Our computational experience shows that the proposed heuristic is effective for tackling RSA, in particular for detecting probably infeasible instances. We report the impact of the addition of this heuristic to an existing branch-and-cut procedure, showing that this addition enhances the ability of this procedure to solve realistic instances with optimality. Finally, we propose an instance benchmark in order to allow the comparison among different methods for RSA, a feature that was lacking in the RSA literature up to this point.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

A matheuristic for the routing and spectrum allocation problem

  • 期刊论文

  • 发表日期：

    2025年5月28日

查看全文
  • Marcelo Bianchetti,
  • Javier Marenco

摘要

One of the most promising solutions to deal with huge data traffic demands in large communication networks is given by flexible optical networking, in particular the flexible grid (flexgrid) technology specified in the ITU-T standard G.694.1. In this specification, the frequency spectrum of an optical fiber link is divided into narrow frequency slots. Any sequence of consecutive slots can be used as a simple channel, and such a channel can be switched in the network nodes to create a lightpath. In this kind of networks, the problem of establishing lightpaths for a set of end-to-end demands that compete for spectrum resources is called the routing and spectrum allocation problem (RSA). Due to its relevance, this NP-hard problem has been intensively studied in the last decade. In this work we present an integer-programming-based heuristic for RSA. We propose several measures of the instance density, and we explore the performance of the proposed heuristic procedure as a function of these measures. Our computational experience shows that the proposed heuristic is effective for tackling RSA, in particular for detecting probably infeasible instances. We report the impact of the addition of this heuristic to an existing branch-and-cut procedure, showing that this addition enhances the ability of this procedure to solve realistic instances with optimality. Finally, we propose an instance benchmark in order to allow the comparison among different methods for RSA, a feature that was lacking in the RSA literature up to this point.