Optimal Path Selection for Ethernet Over SONET Under Inaccurate Link-State Information

被引:0
|
作者
Ahuja, Satyajeet [1 ]
Krunz, Marwan [1 ]
Korkmaz, Turgay
机构
[1] Univ Arizona, Dept ECE, Tucson, AZ 85721 USA
来源
2ND INTERNATIONAL CONFERENCE ON BROADBAND NETWORKS (BROADNETS 2005) | 2005年
关键词
Ethernet over SONET/SDH; virtual concatenation; differential delay; path selection;
D O I
10.1109/ICBN.2005.1589604
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
Ethernet over SONET (EoS) is a popular approach for interconnecting geographically distant Ethernet segments using a SONET transport infrastructure. It typically uses virtual concatenation (VC) for dynamic bandwidth management. The aggregate SONET bandwidth that supports a given EoS system is obtained by "concatenating" a number of virtual channels (VCs), which together form a virtually concatenated group (VCG). This aggregate bandwidth can be increased on demand by adding one or more VCs to the existing VCG. The new VC (route) must be selected such that its end-to-end delay is within a certain range that reflects the delays of all existing VCs in the VCG and the available memory buffer of the EoS system. Algorithmically, the problem of selecting such a VC becomes that of finding a path in a graph network that is bounded by an upper and lower bounds (the lower bound being a positive number). This problem, known as the two-sided constrained path (TSCP), was first formulated in [ 2] assuming exactly known link delays, and a heuristic solution known as the MLW-KSP algorithm was proposed for solving it. In this paper, we first prove that the TSCP problem is NP-complete. We then propose a new solution for it based on the "backward-forward" search approach. We show that this solution is much more efficient than the previously proposed MLW-KSP algorithm. We then consider the TSCP problem under inaccurate link information, in which the delay and available bandwidth for each link are taken as random variables. The problem is now formulated as that of finding the most probable path that satisfies the upper and lower delay constraints. We consider two cases. In the first case, we assume that the link delays are random but the link bandwidths are exact. We then consider the more general case where both the link delays and bandwidths are random. Heuristic solutions are presented for both cases. Simulations are conducted to evaluate the performance of the proposed algorithms and to demonstrate the advantages of the probabilistic path selection approach over the classic trigger-based approach.
引用
收藏
页码:94 / +
页数:10
相关论文
共 50 条
  • [1] Optimal path selection for minimizing the differential delay in Ethernet-over-SONET
    Ahuja, Satyajeet
    Krunz, Marwan
    Korkmaz, Turgay
    COMPUTER NETWORKS, 2006, 50 (13) : 2349 - 2363
  • [2] Pareto optimal path selection in the presence of inaccurate state information
    Tian, Jing
    Zheng, Yan-Xing
    Dou, Wen-Hua
    Tongxin Xuebao/Journal on Communications, 2007, 28 (03): : 68 - 77
  • [3] A randomized QoS routing algorithm on networks with inaccurate link-state information
    Wang, JX
    Wang, WP
    Chen, JN
    Chen, SQ
    2000 INTERNATIONAL CONFERENCE ON COMMUNICATION TECHNOLOGY PROCEEDINGS, VOLS. I & II, 2000, : 1617 - 1622
  • [4] Bandwidth-delay constrained path selection under inaccurate state information
    Korkmaz, T
    Krunz, M
    IEEE-ACM TRANSACTIONS ON NETWORKING, 2003, 11 (03) : 384 - 398
  • [5] Multiple path routing in networks with inaccurate link state information
    Jia, YX
    Nikolaidis, I
    Gburzynski, P
    2001 IEEE INTERNATIONAL CONFERENCE ON COMMUNICATIONS, VOLS 1-10, CONFERENCE RECORD, 2001, : 2583 - 2587
  • [6] Approximation and heuristic algorithms for delay constrained path selection under inaccurate state information
    Xiao, Y
    Thulasiraman, K
    Xue, GL
    FIRST INTERNATIONAL CONFERENCE ON QUALITY OF SERVICE IN HETEROGENEOUS WIRED/WIRELESS NETWORKS, PROCEEDINGS, 2004, : 130 - 137
  • [7] Routing path authentication in link-state routing protocols
    Hamamreh, Rushdi
    Network Security, 2012, 2012 (05) : 14 - 20
  • [8] Fuzzy Non-dominance multipath link-state routing framework for network routing management with inaccurate information
    An, Jing
    Pangalos, Paul
    Aghvami, A. H.
    2012 IEEE GLOBECOM WORKSHOPS (GC WKSHPS), 2012, : 886 - 890
  • [9] Improving QoS routing performance under inaccurate link state information
    Apostolopoulos, G
    Guérin, R
    Kamat, S
    Tripathi, SK
    TELETRAFFIC ENGINEERING IN A COMPETITIVE WORLD, 1999, 3 : 1351 - 1362
  • [10] Optimal Link-state Hop-by-hop Routing
    Michael, Nithin
    Tang, Ao
    Xu, Dahai
    2013 21ST IEEE INTERNATIONAL CONFERENCE ON NETWORK PROTOCOLS (ICNP), 2013,