一种新的WDM网状网中的动态子通路保护算法

论文研究了业务量疏导WDM网状网中的生存性问题,提出一种新的基于优先级的自适用子通路保护算法(PASPP)。该算法在为子通路寻找保护通路时,高优先级业务可以通过抢占低优先级的业务保护通路来提高其连通率,而同时对低优先级业务也能提供部分保护。仿真结果表明,该算法有较好的性能。     

A global approach for designing reliable WDM networks and grooming the traffic

In this paper, we address the global problem of designing reliable wavelength division multiplexing (WDM) networks including the traffic grooming. This global problem consists in finding the number of optical fibers between each pair of optical nodes, finding the configuration of each node with respect to transponders, finding the virtual topology (i.e., the set of lightpaths), routing the lightpaths, grooming the traffic (i.e, grouping the connections and routing them over the lightpaths) and, finally, assigning wavelengths to the lightpaths. Instead of partitioning the problem into subproblems and solving them successively, we propose a mathematical programming model that addresses it as a whole. Numerical results are presented and analyzed.     

A novel recursive shared segment protection algorithm in survivable WDM networks

This paper investigates the problem of dynamic survivable routing for shared segment protection in mesh Wavelength-Division-Multiplexing (WDM) optical networks. We propose a heuristic algorithm, named Recursive Shared Segment Protection (RSSP), to introduce a more flexible way to partition the working path into segments and compute the corresponding backup segments. In RSSP, the working segments cannot be determined before the backup segments are found, we adopt a recursive process to compute the backup segments one by one and then choose an optimized way to partition the working path. The calculations of every neighbor working segment and its backup segment are connected with each other. We constrain the hop count for each backup segment to insure the short failure recovery time and control the bandwidth resource utilization. Compared with the Share Path Protection (SPP), RSSP can achieve much shorter failure recovery time with a little sacrifice in bandwidth resource utilization and RSSP can also perform better compromise between the failure recovery time and the bandwidth resource utilization than the Equal-Length Segment Protection (ELSP) algorithm. We evaluate the effectiveness of RSSP and the results are found to be promising.     

基于重构SPT的单链路故障路由保护方法

为了减少故障对网络运行带来的影响,提出了一种基于重构SPT的单链路故障路由保护算法SLFRPRSPT。该算法在最短路径树SPT的基础上实现,通过制定一系列定义和规则,对SPT进行重构,搜索节点关系发生改变的节点,为每个节点计算最佳备份下一跳节点,从而达到提高路由可用性的目的。经过实验验证,其在网络拓扑中故障保护率可以达到1,并且具有较低的路径拉伸度,可以有效避免单链路故障带来的影响。该方案支持增量部署和逐跳转发,便于实现。     

Multilayer Protection with Availability Guarantees in Optical WDM Networks

Survivability is a key concern in modern network design. This paper investigates the problem of survivable dynamic connection provisioning in general telecom backbone networks, that are mesh structured. We assume differentiated services where connections may have different availability requirements, so they may be provisioned differently with protection (if needed) based on their availability requirements and current network state. The problem of effectively provisioning differentiated-service requests, that has been widely investigated for connections routed at the physical layer, assumes peculiar features if we consider sub-wavelength requests at the logical layer that have to be protected (or more generically, whose availability target has to be guaranteed), but also have to be groomed for an efficient use of network resources. An integrated multilayer approach is necessary that considers requirements and grooming of connections at the logical layer as well as their routing and availability at the physical layer. Joint availability-guaranteed routing and traffic grooming may lead to a negative interaction, since the objective of the first problem (guaranteeing a given level of availability to the connections) clashes with the objective of the other problem (minimizing resource consumption). For a multilayer WDM mesh network, we propose new multilayer routing strategies that perform effective availability-guaranteed grooming of sub-wavelength connections. These strategies jointly considers connection availability satisfaction and resource optimization and are developed under two different practical hypotheses: guaranteed target, i.e., a connection is routed only if its availability target is satisfied, and best-effort target, a connection is always routed and, when the availability target cannot be guaranteed, the path with the best possible availability is provisioned. Numerical results are reported and discussed for the two approaches mentioned above. In both cases, the results show high effectiveness of our provisioning strategy.     

多信道无线网状网带宽有效的路由机制设计

针对基于IEEE 802.11标准的多信道无线网状网中采用接纳控制方案,设计出一种分布式的低干扰且带宽保证的最短路径路由协议;该协议通过分布式免干扰的链路调度机制,并根据带宽要求为链路分配相应时槽数,以实现带宽保证的链路流。NS-2模拟实验结果显示,该协议能为通信链路提供有效的带宽保证,对于有带宽保证要求的业务,可实现较高的通信连接成功概率,具有良好的性能。     

Multicast protection scheme in survivable WDM optical networks

The protection design is a key issue in survivable wavelength division multiplexing (WDM) optical networks. Most researches focused on protecting unicast traffic against the failure of a single network component such as a link or a node. In this paper, we investigate the protection scheme for multicast traffic in meshed WDM optical networks under dual-link failure consideration, and propose a novel protection algorithm called shared segment protection with reprovisioning (SSPR). Through dynamically adjusting link-cost according to the current network state, SSPR establishes a primary light-tree and corresponding link-disjoint backup segments for each multicast connection request. A backup segment can efficiently share wavelength capacity of its working tree or the common resource of other backup segments. Capacity reprovisioning establishes new segments for the vulnerable connections after a link failure and tolerates following link failures. The simulation results show that SSPR not only can make good use of wavelength resources and protect multicast sessions against any single-link failure, but also can greatly improve the traffic restorability in the event of dual-link breakdown.     

基于单节点故障的IP Over WDM网络生存性映射算法

在IP Over WDM网络中, WDM层的一条物理链路往往对应多条IP层逻辑链路,无论采用何种机制,都不允许WDM层的故障导致上层逻辑拓扑变的不连通,因此,解决IP Over WDM的生存性映射问题便显得尤为重要。本文在现有IP Over WDM静态拓扑映射算法的基础上提出一种基于单节点故障的映射算法,目的是在WDM层出现单节点故障后, IP层逻辑拓扑不被分割为多个不连通的部分,以保证IP拓扑的连通性。     

A new shared-risk link groups (SRLG)-disjoint path provisioning with shared protection in WDM optical networks

This paper addresses the protection problem in WDM optical networks and presents a New Shared-risk link groups (SRLG)-Disjoint Path Provisioning (NSDPP) approach with shared protection to tolerate the single-risk failure. Comparing to previous Shared-risk link groups (SRLG)-Disjoint Path Provisioning (SDPP) approach, NSDPP is able to obtain better performance, because in NSDPP some primary path and backup paths of other primary paths can share the common resources if the corresponding rules can be satisfied. Simulation results are shown to be promising.     

An efficient joint channel assignment and QoS routing protocol for IEEE 802.11 multi-radio multi-channel wireless mesh networks

With the emerging of video, voice over IP (VoIP) and other real-time multimedia services, more and more people pay attention to quality of service (QoS) issues in terms of the bandwidth, delay and jitter, etc. As one effective way of broadband wireless access, it has become imperative for wireless mesh networks (WMNs) to provide QoS guarantee. Existing works mostly modify QoS architecture dedicated for ad hoc or sensor networks, and focus on single radio and single channel case. Meanwhile, they study the QoS routing or MAC protocol from view of isolated layer. In this paper, we propose a novel cross-layer QoS-aware routing protocol on OLSR (CLQ-OLSR) to support real-time multimedia communication by efficiently exploiting multi-radio and multi-channel method. By constructing multi-layer virtual logical mapping over physical topology, we implement two sets of routing mechanisms, physical modified OLSR protocol (M-OLSR) and logical routing, to accommodate network traffic. The proposed CLQ-OLSR is based on a distributed bandwidth estimation scheme, implemented at each node for estimating the available bandwidth on each associated channel. By piggybacking the bandwidth information in HELLO and topology control (TC) messages, each node disseminates information of topology and available bandwidth to other nodes in the whole network in an efficient way. From topology and bandwidth information, the optimized path can be identified. Finally, we conduct extensive simulation to verify the performance of CLQ-OLSR in different scenarios on QualNet platform. The results demonstrate that our proposed CLQ-OLSR outperforms single radio OLSR, multi-radio OLSR and OLSR with differentiated services (DiffServ) in terms of network aggregate throughput, end-to-end packet delivery ratio, delay and delay jitter with reasonable message overheads and hardware costs. In particular, the network aggregate throughput for CLQ-OLSR can almost be improved by 300% compared with the single radio case.     

A new heuristic protection algorithm based on survivable integrated auxiliary graph in waveband switching optical networks

In this paper, we study the survivability in waveband switching optical networks and propose a new heuristic algorithm called Protection based on Survivable Integrated Auxiliary Graph (PSIAG) to tolerate the single-link failure. The survivable integrated auxiliary graph (SIAG) is compared of the single virtual topology layer and multiple waveband-plane layers, and it can well solve the problem of routing and waveband assignment. In PSIAG, we can feasible use the waveband sub-path grouping scheme based on SIAG to save the switching ports in MG-OXCs. For each demand, PSIAG first computes the single-hop or multi-hop route-pair including a primary path and a link-disjoint backup path on virtual topology layer. If the route-pair cannot be found on virtual topology layer, PSIAG then computes the hybrid multi-hop route-pair on jointing the virtual topology layer and waveband-plane layers. Simulation results show that PSIAG can obtain better performance than previous algorithm.     

DORA: Efficient Routing for MPLS Traffic Engineering

This paper introduces DORA, a dynamic online routing algorithm for construction of bandwidth guaranteed paths in MPLS-enabled networks. The main objective of DORA is to place paths with reserved bandwidth evenly across the network in order to allow more future paths to be accepted into the network and to balance the traffic load. During path computation, the key operation in DORA is to avoid routing over links that (1) have high potential to be part of any other path, and (2) have low residual bandwidth available. Our simulation results based on unsuccessful path-setup ratio and successful path-reroutes upon link failure, show that DORA offers better performance than some sophisticated algorithms, while at the same time being less computationally expensive.     

一种综合IP层和WDM层资源的光网络动态路由优化模型及其性能研究

在分层图模型的基础上,本文提出一种以最小化全网光路总代价为优化目标的IP over WDM光网络动态路由优化模型,设计了一种针对该模型的在线综合路由算法——MCTLP（Minimizing the Cost of Total Lightpaths）,MCTLP通过综合考虑IP逻辑层带宽资源分配和WDM光物理层波长链路资源的占用以优化网络资源。与两种有代表性的IP over WDM光网络路由算法的性能仿真时比表明：MCTLP能够在IP逻辑层和WDM光物理层都使用较少的链路以承载IP业务流,接纳更多的IP业务连接请求,有效地降低网络阻塞率．     

Graph transformation approaches for diverse routing in shared risk resource group (SRRG) failures

Failure resilience is a desired feature of the Internet. Most traditional restoration architectures assume single failure assumption, which is not adequate in present day WDM optical networks.Multiple link failure models, in the form of shared risk link groups (SRLG’s) and shared risk node groups (SRNG’s) are becoming critical in survivable optical network design. We classify both of these form of failures under a common scenario of shared risk resource groups (SRRG) failures. We develop graph transformation techniques for tolerating multiple failures arising out of shared resource group (SRRG) failures.Diverse routing in such multi-failure scenario essentially necessitates finding out two paths between a source and a destination that are SRRG disjoint. The generalized diverse routing problem has been proved to be NP-Complete. The proposed transformation techniques however provides a polynomial time solution for certain restrictive failure sets. We study how restorability can be achieved for dependent or shared risk link failures and multiple node failures and prove the validity of our approach for different network scenarios. Our proposed technique is capable of improving the diverse route computation by around 20–30% as compared to approaches proposed in the literature.     

Ant-based survivable routing in dynamic WDM networks with shared backup paths

In this paper, we consider the problem of survivable routing in dynamic WDM networks with single link failure model. Our work mainly concerns in how to dynamically determine a protection cycle (i.e., two link-disjoint paths between a node pair) to establish a dependable lightpath with backup paths sharing. This problem is identified as NP-complete, thus a heuristic for finding near optimal solution with reasonable computation time is usually preferred. Inspired from the principle of ant colony optimization, we propose in this paper an ant-based mobile agents algorithm for this problem with improved blocking performance. To enable the new ant-based algorithm, we propose to use on each network node both a routing table that contains a set of feasible protection cycles between source destination nodes and also a pheromone table for mobile agents. By keeping a suitable number of mobile agents in a network to continually and proactively update the routing tables based on the current network congestion state, the routing solution of a connection request can be obtained with a reasonable computation time. Extensive simulation results upon the ns-2 network simulator and two typical network topologies show that our new algorithm can achieve a significantly lower blocking probability than the promising algorithm for dynamic lightpath protection proposed in [11] with a comparable computation complexity.     

Survivable power efficiency oriented integrated grooming in green networks

The wide interests in the power savings of IP over wavelength-division-multiplexing (WDM) optical networks have recently risen in both academic and industrial communities. In an effort to tackle this problem, the hybrid grooming (traffic grooming along with an optical bypass) approach has been presented to reduce the power consumed by the entire network infrastructure, including the transmission ports of routers and optical-electrical-optical (OEO) conversions. However, the related works pay little or no attention to the power consumed to ensure the resiliency of the overall network. Meanwhile, the power consumed by components used for establishing lightpaths is not simultaneously taken into account. One survivable network with the higher power efficiency thereby save more power with hybrid grooming, require the lower power consumption of establishing lightpaths and exhibit the shorter recovery time. For the first time, this paper proposes the evaluating models of both survivable power ratio and protection switching time. We subsequently compare two green and survivable grooming heuristics, known as Single-hop Survivable Grooming with considering Power Efficiency (SSGPE) and Multi-hop Survivable Grooming with considering Power Efficiency (MSGPE). Simulation results demonstrate that, MSGPE obtains the higher power efficiency and resiliency although it has the slightly higher time complexity in comparison to SSGPE. Furthermore, it is effective to exploiting waveband merging in our MSGPE to form integrated grooming for further port savings.     

MANET中一种新QoS路由技术的研究

移动AdHoc网络（MANET）支持QoS保证的能力,受限于无线介质的带宽和节点的移动特性。由于节点的移动,网络拓朴频繁发生变化,一旦节点移动,当前的路由就很容易失效,从而造成通讯中断,这种情况就是链路失效。QoS路由是MANET获得端到端QoS保证的第1步。然而,拓朴变化造成的链路失效状况的存在,使得路由的可靠性对于QoS路由而言非常重要。为使链路失效造成的影响最小,找到生存时间长并且可靠性高的路由就显得尤为重要。提出了一种在MANET中支持Oos路由,并能较好解决链路失效状况的方案。该方案定义了一种新机制,在执行时类似表驱路由协议,通过利用主路径上被共享的邻居节点信息,为主路径上各个独立的子路径预备了可替换的路径。     

Dynamic service-level-agreement aware shared-path protection in WDM mesh networks

The notion of service level agreements (SLA) has been proposed to capture qualitatively and quantitatively defined performance contracts between service providers and their customers. How to provision satisfiable connections for customers according to their SLA parameters to avoid penalty as well as minimizing cost is one of the main concerns for a service provider. Connection reliability and restoration time are two important SLA parameters for a customer, and should be carefully considered in survivable wavelength-division-multiplexing (WDM) networks. A sound scheme should guarantee customers’ reliability and reduce restoration time while benefiting a service provider in resource efficiency. Under the SLA constraints and the assumption of single link failure, we first investigate a partial link-disjoint protection (PLDP) and analyze its availability and average restoration time. We then propose a dynamic constraint shared path protection (DCSP) algorithm in WDM mesh networks. Based on the basic ideas of the K-shortest path algorithm and PLDP, DCSP can provide differentiated services for customers according to their SLA parameters while being favorable for reducing average restoration time and optimizing resource utilization. Simulation results show that DCSP can efficiently guarantee the specific SLA requirements of customers with a slight increase in the blocking probability while still achieving spare resource sharing and restoration time optimizations.     

Redundant multicast routing in multilayer networks with shared risk resource groups: Complexity,models and algorithms

This paper presents a redundant multicast routing problem in multilayer networks that arises from large-scale distribution of realtime multicast data (e.g., Internet TV, videocasting, online games, stock quotes). Since these multicast services commonly operate in multilayer networks, the communications paths need to be robust against a single router or link failure as well as multiple such failures due to shared risk link groups (SRLGs). The main challenge of this multicast is to ensure the service availability and reliability using a path protection scheme, which is to find a redundant path that is SRLG-disjoint (diverse) from each working path. The objective of this problem is, therefore, to find two redundant multicast trees, each from one of the two redundant sources to every destination, at a minimum total communication cost whereas two paths from the two sources to every destination are guaranteed to be SRLG-diverse (i.e., links in the same risk group are disjoint). In this paper, we present two new mathematical programming models, edge-based and path-based, for the redundant multicast routing problem with SRLG-diverse constraints. Because the number of paths in path-based model grows exponentially with the network size, it is impossible to enumerate all possible paths in real life networks. We develop three approaches (probabilistic, non-dominated and nearly non-dominated) to generate potentially good paths that may be included in the path-based model. This study is motivated by emerging applications of internet-protocol TV service, and we evaluate the proposed approaches using real life network topologies. Our empirical results suggest that both models perform very well, and the nearly non-dominated path approach outperforms all other path generation approaches.     

基于双维序路由策略的低能耗NoC网络分配

在片上网络(NoC)的网络分配与任务映射相配合的路径分配中,单维序路由策略会限制可行解空间。为此,提出一种基于双维序路由策略的网络分配方法。在路径分配步骤中采用双维序路由法,设计以带宽、延时和无死锁为约束条件、以降低动态及静态能耗为优化目标的遗传算法。实验结果表明,该方法可以扩大任务映射的可行解空间,求解最小所需带宽比单维序法平均减少6.3%,且在各种带宽场合时均能求得更低能耗解。