Routing Connections With Differentiated Reliability Requirements in WDM Mesh Networks
Routing Connections With Differentiated Reliability Requirements in WDM Mesh Networks
复制标题
WDM网状网络中具有差异化可靠性要求的路由连接
DOI：
10.1109/tnet.2008.925087
复制
发表时间：
2009-02
期刊：
影响因子：
--
通讯作者：
中科院分区：
文献类型：
--
作者：
在现代高速网络设计中，可靠性已成为一个重要的设计目标。虽然传统方法在单链路故障的情况下提供100%的保护，或者根本不提供保护，但实际网络中的连接可能有多种可靠性要求。文献中引入了差异化可靠性（DiR）的概念，以在提供备用资源的保护方案中提供多种可靠性要求。本文研究了波分复用（WDM）网状网络中不允许备份共享时的差分可靠性路由连接问题。我们的目标是以最小的网络成本（例如，网络资源）路由连接，同时满足其所需的可靠性。我们假设连接一次一个地动态到达，并且必须在不知道未来到达的先验知识的情况下做出接受或拒绝连接的决定。由于共享不能用于实现效率，所以目标是通过改进路径选择来实现效率。本文首先给出了该问题的整数线性规划（ILP）公式。通过求解ILP公式，我们可以得到每个动态到达点相对于当前网络状态的最优解。然而，求解ILP公式对于大型网络来说是非常耗时的。因此，我们提出了两种近似算法。第一种方法称为基于最短路径对的辅助图（SPPA），它可以在O((n2（n + 1) + 2mn)(log log(2n) + 1/epsiv)）时间内得到一个epsiv逼近解，其代价不超过1 + epsiv乘以最优解，其中n和m分别是网络中的节点数和链路数。为了降低第一种算法的计算复杂度，提出了基于辅助图的两步法（ATSA），该算法可以在O（mn(log log n + 1/epsiv)）时间内获得最优解的代价最多为最优解的2 + epsiv倍的近最优解。在两种典型的载波网格网络上进行的大量仿真结果表明了这两种算法的有效性。
Reliability has been well recognized as an important design objective in the design of modern high-speed networks. While traditional approaches offer either 100% protection in the presence of single link failure or no protection at all, connections in real networks may have multiple reliability requirements. The concept of differentiated reliability (DiR) has been introduced in the literature to provide multiple reliability requirements in protection schemes that provision spare resources. In this paper, we consider the problem of routing connections with differentiated reliability in wavelength-division multiplexing (WDM) mesh networks when backup sharing is not allowed. Our objective is to route connections with minimum network cost (e.g., network resources) while meeting their required reliability. We assume connections arrive dynamically one-at-a-time and a decision as to accept or reject a connection has to be made without a priori knowledge of future arrivals. Since sharing cannot be used for achieving efficiency, the goal is to achieve efficiency by improved path selection. In this paper, we first present an integer linear programming (ILP) formulation for the problem. By solving the ILP formulation, we can obtain an optimal solution with respect to the current network state for each dynamic arrival. To solve the ILP formulation, however, is time consuming for large networks. We thus propose two approximation algorithms for the problem. The first one, called Shortest-Path-Pair-based Auxiliary graph (SPPA), can obtain an epsiv-approximation solution whose cost is at most 1 + epsiv times the optimum in O((n2(n + 1) + 2mn)(log log(2n) + 1/epsiv)) time, where n and m are the number of nodes and links in a network, respectively. To reduce the computational complexity of the first algorithm, the second algorithm, called Auxiliary graph-based Two-Step Approach (ATSA), is proposed and can obtain a near optimal solution with cost at most 2 + epsiv times that of the optimal solution in O(mn(log log n + 1/epsiv)) time. Results from extensive simulations conducted on two typical carrier mesh networks show the efficiency of the two algorithms.
登录
查看更多内容
DOI：
10.1007/3-540-44554-4_20
发表时间：
2001-12
期刊：
--
影响因子：
--
作者：
A. Fumagalli;M. Tacca
通讯作者：
A. Fumagalli;M. Tacca
DOI：
10.1109/49.725189
发表时间：
1998-09
期刊：
IEEE J. Sel. Areas Commun.
影响因子：
--
作者：
Y. Miyao;H. Saito
通讯作者：
Y. Miyao;H. Saito
DOI：
10.1016/s0020-0190(02)00205-3
发表时间：
2002-09
期刊：
Inf. Process. Lett.
影响因子：
--
作者：
Funda Ergün;R. Sinha;Lisa Zhang
通讯作者：
Funda Ergün;R. Sinha;Lisa Zhang
DOI：
10.1109/infcom.1999.751461
发表时间：
1999-03
期刊：
IEEE INFOCOM '99. Conference on Computer Communications. Proceedings. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies. The Future is Now (Cat. No.99CH36320)
影响因子：
--
作者：
S. Ramamurthy;B. Mukherjee
通讯作者：
S. Ramamurthy;B. Mukherjee
DOI：
10.1109/icc.2003.1203942
发表时间：
2003-05
期刊：
IEEE International Conference on Communications, 2003. ICC '03.
影响因子：
--
作者：
Kai Wu;L. Valcarenghi;A. Fumagalli
通讯作者：
Kai Wu;L. Valcarenghi;A. Fumagalli