Fast Exact ILP Decompositions for Ring RWA
Fast Exact ILP Decompositions for Ring RWA
复制标题
环 RWA 的快速精确 ILP 分解
DOI：
10.1364/jocn.3.000577
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
G. Rouskas
中科院分区：
文献类型：
--
作者：
Emre Yetginer;Zeyu Liu;G. Rouskas
波分复用环现在能够在单根光纤上支持100多个波长。传统的链路和路径公式的路由和波长分配问题是低效的，由于固有的对称性，在波长分配和事实，即问题的大小增加快速的波长的数量。虽然最大独立集（MIS）的基础上制定没有这些缺点，它遭受指数增长的变量的数量随着网络规模的增加。我们开发了一个新的ILP（整数线性规划）制定的关键思想的基础上，分区的路径集，并表示MIS在原始网络中使用的独立集计算在每个这些分区。这种精确的分解权衡了变量的数量和约束的数量，因此，在网络维度方面实现了更好的可扩展性。对不同规模的环形网络的数值结果表明，这种新的ILP分解实现了几个数量级的运行时间相比，现有的配方减少。我们的主要贡献是一种新颖的和非常快速的技术，在几秒钟内使用商品CPU，最佳的解决方案，以实例的最大大小的SONET环与任何数量的波长，这样的情况下，不能处理与经典配方没有大量的投资，计算资源和时间。
Wavelength division multiplexing rings are now capable of supporting more than 100 wavelengths over a single fiber. Conventional link and path formulations for the routing and wavelength assignment problem are inefficient due to the inherent symmetry in wavelength assignment and the fact that the problem size increases fast with the number of wavelengths. Although a formulation based on maximal independent sets (MIS) does not have these drawbacks, it suffers from exponential growth in the number of variables with increasing network size. We develop a new ILP (integer linear program) formulation based on the key idea of partitioning the path set and representing the MIS in the original network using the independent sets calculated in each of these partitions. This exact decomposition trades off the number of variables with the number of constraints and, as a result, achieves a much better scalability in terms of network dimension. Numerical results on ring networks of various sizes demonstrate that this new ILP decomposition achieves a decrease of several orders of magnitude in running time compared to existing formulations. Our main contribution is a novel and extremely fast technique for obtaining, in a few seconds using commodity CPUs, optimal solutions to instances of maximum size SONET rings with any number of wavelengths; such instances cannot be tackled with classical formulations without vast investments in computational resources and time.