Markov decision algorithms for dynamic routing [telephone networks]

The nature of the traffic-routing problem is described, and early studies of state-dependent routing are noted. A state-dependent scheme seeks to route each call so as to minimize the risk of blocking future calls, and thus responds to the current state of the network on the basis of certain assumptions about future traffic demands. State-dependent routing is considered as a Markov decision process. How the relative costs can be determined for the case of direct routing is shown     

光网络中实现流量工程的负载均衡动态路由算法

提出了一种在光网络中实现流量工程的负载均衡动态路由算法(LBDRO).该算法通过新定义的链路关键度函数和链路当前可用带宽确定链路动态成本,并依据该动态成本运用最短路径优先算法为到达的LSP请求建立动态成本优化路径.该算法的计算复杂度低,仿真实验表明,与MHA、WSP、MIRA算法相比,在光传输网络中,该算法在降低LSP建立请求服务拒绝率、均衡网络负载以及链路失效后重路由等方面有很好的性能.     

Post‐Disaster least loaded lightpath routing in elastic optical networks

Disaster events directly affect the physical topology of core networks and may lead to simultaneous failure of multiple lightpaths leading to massive service outages for network operators. To recover from such a failure scenario, the existing routing algorithms running on network nodes (routers or switches) typically attempt to reestablish the connections over new routes with shortest distances and hop count approach. However, this approach may result in congestion on some links, while other links may have the unutilized capacity. Hence, intelligent lightpath computing techniques are required to efficiently route network traffic over the new routes by considering traffic load of each link in addition to distance and hop count to minimize network congestion. In this paper, we have proposed a capacity‐constrained maximally spatial disjoint lightpath algorithm to tackle the provisioning and restoration of disrupted lightpaths in a postdisaster scenario in the context of elastic optical networking. This algorithm computes an alternate least loaded lightpath for disrupted primary lightpath using capacity‐constrained shortest lightpath. Alternate lightpath selection is based on a criteria parameter for a lightpath to be least loaded and constrained by either the length or the spatial distance between primary and alternate lightpaths. The spatial distance between lightpaths enables to reestablish the disrupted connection request away from disaster proximity. The performance of the proposed algorithm is evaluated through simulation for several parameters like blocking probability, network utilization, connection success rates, and minimum spatial distance.     

Proactive defragmentation in elastic optical networks under dynamic load conditions

The main weakness of elastic optical networks (EON), under dynamic traffic conditions, stems from spectrum fragmentation. A lot of research efforts have been dedicated during recent years to spectrum defragmentation. In this work, a thorough study about proactive defragmentation is carried out. Effects of the different defragmentation parameters on the EON performance are analyzed, and appropriate values of the defragmentation period, which guarantee suitable network performance while keeping the network control complexity at reasonable values, are obtained by means of extensive simulations. Benefit obtained by applying different defragmentation strategies, in terms of increase in the supported load at a given bandwidth blocking probability, is also reported. Different traffic conditions and network topologies are simulated to assess the validity of the obtained results.     

Parallel routing algorithms in Benes-Clos networks

A new parallel algorithm for route assignments in Benes-Clos (1962, 1953) networks is studied. Most known sequential route assignment algorithms, such as the looping algorithm, are designed for circuit switching systems where the switching configuration can be rearranged at relatively low speed. In packet switching systems, switch fabrics must be able to provide internally conflict-free paths simultaneously, and accommodate packets requesting connections in real time as they arrive at the inputs. In this paper, we develop a parallel routing algorithm for Benes networks by solving a set of Boolean equations which are derived from the connection requests and the symmetric structure of the networks. Our approach can handle partial permutations easily. The time complexity of our algorithm is O(log/sup 2/ N), where N is the network size. We also extend the algorithm and show that it can be applied to the Clos networks if the number of central modules is M=2/sup m/, where m is a positive integer. The time complexity is O(log N/spl times/log M) in this case.     

Eco-sustainable routing in optical networks

It is quite easy to foresee that in the next years, the future generation ultra-high speed network infrastructures and equipments will be no longer constrained only by their pure transport capacity, but also by their energy consumption costs and environmental effects. In particular, large network infrastructures are now widely recognized to play a fundamental role in the emission of greenhouse gases in the atmosphere, significantly affecting the environmental sustainability of new evolutions in network architectures as well as technological developments in communication devices. In this paper, a novel eco-sustainable routing and wavelength assignment algorithm, based on shortest path routing with an adaptive link weighting function relying on an extension of the OSPF-TE protocol to convey carbon footprint information, has been proposed to decrease the network ecological impact while balancing the traffic load and maintaining acceptable connection-blocking rate. The trade-off between load balancing and carbon footprint is also analyzed to evaluate the effectiveness of the proposed strategy within the context of a real world network.     

New algorithms for multicast routing and wavelength assignment in multi-hop optical WDM networks

We study the problem of multicast routing and wavelength assignment (MC-RWA) in multi-hop optical WDM networks with respect to several target functions. Specially, we first study the MC-RWA problem under the target of minimize maximum hops, an efficient MC-RWA algorithm was proposed for that case. But for the objective of minimizing the total number of wavelength conversions, problem turns out to be NP-hard, we proposed a new approximation MC-RWA algorithm based on group Steiner tree. At last, combining the two objectives, a bi-factor approximation algorithm was introduced to minimize the both targets in the system simultaneously.     

弹性光网络中结合预测的多维感知RSA算法

弹性光网络(EON)中的传统路由频谱分配(RSA)算法多考虑路由跳数或频谱资源占用情况,缺乏时域与相邻链路的信息有效利用.提出一种结合预测的多维感知RSA算法,对持续时间已知业务的历史时间信息通过后向传播神经网络预测未来业务的时间信息,在路由时综合考虑时间、频谱和相邻链路资源占用程度.仿真结果表明:与传统RSA算法相比...     

一种基于能量感知的弹性光网络RSA算法

弹性光网络具有高频谱效率和灵活性等优点,是光网络发展的主要方向。路由和频谱分配是弹性光网络的核心技术之一。文章提出了一种改进的基于能量感知的弹性光网络RSA(路由和频谱分配)算法,在进行选路和频谱分配时,同时考虑了网络中的能耗和可用频谱资源情况。理论分析和仿真结果表明,与传统RSA算法相比,改进算法可以提高能量效率,降低业务阻塞率。     

Adaptive subcarrier-distribution algorithm for routing and spectrum allocation in OFDM-based elastic optical networks

In this paper, we have proposed the adaptive subcarriers-distribution routing and spectrum allocation (ASD-RSA) algorithm, which is the first elastic optical network routing and spectrum allocation algorithm based on distributed subcarriers. It allocates lightpaths to request adaptively and proved to achieve much lower bandwidth blocking probability than traditional routing and spectrum allocation algorithms based on centralized subcarriers with integer linear programming and dynamic simulation methods. Additionally, the ASD-RSA algorithm performs the best with three alternate routing paths; this character will decrease the calculating amount of both alternate routing path searching and spectrum allocation immensely in large networks.     

Distributed dynamic grooming routing and wavelength assignment in WDM optical mesh networks

The bandwidth of a wavelength channel in WDM optical networks is very high compared to the user’s requirements for various applications. Therefore, there is a scope for better utilization of channel bandwidth by traffic grooming, in which several user’s channels are multiplexed for transmission over a single channel. Several research works have been reported on traffic grooming routing and wavelength assignment (GRWA) for static and dynamic traffic pattern under centralized environment. Distributed dynamic grooming routing and wavelength assignment (DDGRWA) is a new and quite unexplored area in WDM optical mesh networks. This article introduces the concept of distributed traffic grooming in WDM mesh networks which also includes virtual topology construction, reconfiguration, routing and wavelength assignment in the distributed environment assuming incoming traffic to be dynamic in nature. We have also presented simulation results of our algorithm on dynamically generated traffic under various network topologies.     

Study on dynamic routing and spectrum assignment in bitrate flexible optical networks

The exponential growth of Internet traffic necessitates high-capacity optical networks and has also highlighted the importance of bandwidth-flexible and multi-granularity transport platforms. Improving both transport capacity and bandwidth flexibility is a significant challenge in optical networks. A bitrate flexible network architecture that is based on orthogonal frequency division multiplexing has been proposed as a promising solution for meeting this challenge. In the current study, we focus on the online routing and spectrum assignment problems in the aforementioned network architecture and introduce a general solution for dynamic bitrate flexible traffic in distributed environments. A novel spectrum representation method based on continuous spectrum segments is introduced into the networks. Segment-based routing and signaling mechanisms provide general solutions that support both the conventional slot-based networks and the ideal fully gridless networks. The routing algorithms and spectrum selection approaches are demonstrated and compared in a simulation. Performance estimation indicates that random spectrum segment assignment achieves the lowest capacity blocking rate in light traffic, whereas the adaptive routing plus minimum residual spectrum scheme obtains the lowest capacity blocking rate under heavy traffic.     

Effects of wavelength routing and selection algorithms onwavelength conversion gain in WDM optical networks

Wavelength-division multiplexing (WDM) technology is emerging as the transmission and switching mechanism for future optical mesh networks. In these networks it is desired that a wavelength can be routed without electrical conversions. Two technologies are possible for this purpose: wavelength selective cross-connects (WSXC) and wavelength interchanging cross-connects (WIXC), which involve wavelength conversion. It is believed that wavelength converters may improve the blocking performance, but there is a mix of results in the literature on the amount of this performance enhancement. We use two metrics to quantify the wavelength conversion gain: the reduction in blocking probability and the increase in maximum utilization, compared to a network without converters. We study the effects of wavelength routing and selection algorithms on these measures for mesh networks. We use the overflow model to analyze the blocking probability for wavelength-selective (WS) mesh networks using the first-fit wavelength assignment algorithm. We propose a dynamic routing and wavelength selection algorithm, the least-loaded routing (LLR) algorithm, which jointly selects the least-loaded route-wavelength pair. In networks both with and without wavelength converters the LLR algorithm achieves much better blocking performance compared to the fixed shortest path routing algorithm. The LLR produces larger wavelength conversion gains; however, these large gains are not realized in sufficiently wide utilization regions and are diminished with the increased number of fibers     

Diverse routing in optical mesh networks

We study the diverse routing problem in optical mesh networks. We use a general framework based on shared risk link groups to model the problem. We prove that the diverse routing problem is indeed NP-complete, a result that has been conjectured by several researchers previously. In fact, we show that even the fiber-span-disjoint paths problem, a special case of the diverse routing problem, is also NP-complete. We then develop an integer linear programming formulation and show through numerical results that it is a very viable method to solve the diverse routing problem for most optical networks found in many applications which typically have no more than a few hundred nodes and fiber spans.     

Deflection routing in IP optical networks

This paper deals with optical packet switching in a full-IP transport network scenario. Given the technological limits of accomplishing packet buffering in the optical domain, deflection routing is here explored as an alternative technique for resolving packet contentions without buffering packets. Two different network topologies have been considered here, that is a regular six-node network with different connectivity factors and the classical NSF network. A limited amount of optical buffering is considered in the switching nodes that performs both input queuing and shared queuing of packets to be switched. The performance improvements that can be obtained by deflection routing have been evaluated considering different methods for choosing the alternative paths where to deflect packets that cannot be transmitted onto the shortest path to the addressed destination.     

Cross-layer routing in clustered optical networks

Physical layer impairment aware routing algorithms have been proposed for optical transparent networks in order to calculate the feasibility of dynamically establishing an optical path when no regeneration is used. The benefit of node clustering in optical networks, regarding routing with physical layer impairment awareness, is investigated under the CANON network architecture where regenerators are conveniently placed and routing is confined among a small subset of nodes. The CANON architecture exhibits enhanced blocking performance, high resource utilisation and adequate physical performance; hence, it can serve Quality of Service.     

Assessment of novel regenerator assignment strategies in dynamic translucent elastic optical networks

Photonic Network Communications - The problem of regenerator assignment (RA) in translucent optical networks consists in segmenting a lightpath into several transparent segments, each of...     

GSM-R应急自组网中的分簇路由算法研究

在采用分簇结构的GSM-R应急自组织网络中,簇头的选择将直接影响整个网络的性能,因此必须设计合理的分簇算法,综合考虑网络环境中的各种因素,使得形成的分簇结构具有很好的系统环境和应用需求的适应性。通过对Ad Hoc自组网中的加权分簇算法WCA（Weighted Clustering Algorithm）简单介绍,从算法的复杂度、负载均衡性和适用环境等方面对其性能进行比较和分析。本文改进一种基于组合加权思想的分簇算法,即基于簇稳定性的加权分簇算法,以下简称CSBWCA（Cluster-Stability Based Weighted Clustering Algorithm）。同时,介绍了此算法的设计思想,并仿真了加权分簇算法和基于稳定性的加权分簇算法的节点簇间转移次数R随GSM-R应急网络中参与应急通信的终端数目N和最大转移速度的变化情况以及两种分簇算法的簇头更新次数U随终端数目以及终端最大移动速度的变化情况。仿真结果表明,基于簇稳定性的加权分簇算法的性能明显优于加权分簇算法。     

Adhoc-like routing in wired networks with genetic algorithms

Routing of packets in networks requires that a path be selected either dynamically while the packets are being forwarded, or statically (in advance) as in source routing from a source node to a destination. Quality of service (QoS) driven routing has been proposed using a protocol called the “Cognitive Packet Network” (CPN) which dynamically selects paths through a store and forward packet network so as to provide best effort QoS to route peer-to-peer connections. CPN operates very much as an adhoc protocol within a wired setting, and uses smart packets to select routes based on QoS requirements. We extend the path discovery process in CPN to include a genetic algorithm which can help discover new paths that may not have been discovered by smart packets. We describe how possible routes can “evolve” from prior knowledge, and then be selected based on “fitness” with respect to QoS. We detail the design of the algorithm and of its implementation, and report on resulting QoS measurements.