Logical topology design for IP rerouting: ASONs versus static OTNs

IP-based backbone networks are gradually moving to a network model consisting of high-speed routers that are flexibly interconnected by a mesh of light paths set up by an optical transport network that consists of wavelength division multiplexing (WDM) links and optical cross-connects. In such a model, the generalized MPLS protocol suite could provide the IP centric control plane component that will be used to deliver rapid and dynamic circuit provisioning of end-to-end optical light paths between the routers. This is called an automatic switched optical (transport) network (ASON). An ASON enables reconfiguration of the logical IP topology by setting up and tearing down light paths. This allows to up- or downgrade link capacities during a router failure to the capacities needed by the new routing of the affected traffic. Such survivability against (single) IP router failures is cost-effective, as capacity to the IP layer can be provided flexibly when necessary. We present and investigate a logical topology optimization problem that minimizes the total amount or cost of the needed resources (interfaces, wavelengths, WDM line-systems, amplifiers, etc.) in both the IP and the optical layer. A novel optimization aspect in this problem is the possibility, as a result of the ASON, to reuse the physical resources (like interface cards and WDM line-systems) over the different network states (the failure-free and all the router failure scenarios). We devised a simple optimization strategy to investigate the cost of the ASON approach and compare it with other schemes that survive single router failures.     

On the Maximum Protection Problem in IP-over-WDM Networks Using IP LSP Protection

In dynamic IP-over-WDM networks efficient fault-management techniques become more difficult since as demands change with time the optimal logical topology varies as well. Changes in the virtual topology should be done with care because working IP LSPs routed on top of a virtual topology should not be interrupted. Reconfiguration of the virtual topology may also affect precomputed backup IP LSPs to be activated in case of failure meaning that backup IP LSPs would need to be recomputed after any change in the virtual topology. A good sense solution can be the dimensioning of the virtual topology for a worst case traffic scenario, having as goal the minimization of the network cost, for example, and then route dynamic IP LSPs on this virtual topology. The virtual topology would remain unchanged as long as possible, that is, until changes in the virtual topology are considered to bring considerable benefits. Since data services over IP are essentially of a best-effort nature, protection could be provided, using IP LSP protection, only when bandwidth is available in the virtual topology. The computation of backup IP LSPs does not interfere with working IP LSPs meaning that no service interruption will exist. Such a strategy, considered in this paper, allows resources to be used efficiently, since free bandwidth is used for backup purposes, while the normal delivery of traffic is guaranteed in peak traffic situations although having no protection guarantees. Our main objective is to quantify the spare capacity, which can be used for restoration (backup) purposes, over a virtual topology designed and optimized to carry a traffic scenario with no survivability and QoS requirements. We analyse the maximum protection (MP) problem in such IP-over-WDM network environment. Protection is provided to IP LSP requests whenever possible through bandwidth reservation in a backup IP LSP on the virtual topology. Besides the mathematical formalization of the MP problem, an upper bound and heuristic algorithms are proposed and evaluated. The traffic considered includes IP LSPs of different granularities and is the worst case traffic scenario for which the network should be dimensioned.     

IP/ MPLS over WDM网中考虑QoS的VPN业务设计

本文研究了在IP／MPLS over WDM网络中支持不同QoS要求的VPN业务的逻辑拓扑设计问题。对于给定的网络物理拓扑和业务需求矩阵，本文提出，基于不同时延要求的VPN业务逻辑拓扑设计可以运用两种方法加以解决。一为基于迭代的线性规划方法，适合于规模较小的网络。另一个为启发式算法，可运用于网络规模较大的环境。对比仿真结果表明，启发式算法不但较好地解决了不同QoS要求的VPN业务的选路和波长分配问题，还较好地降低了链路的最大负载。     

Resource efficient network design and traffic grooming strategy with guaranteed survivability

In WDM networks, path protection has emerged as a widely accepted technique for providing guaranteed survivability of network traffic. However, it requires allocating resources for backup lightpaths, which remain idle under normal fault-free conditions. In this paper, we introduce a new design strategy for survivable network design, which guarantees survivability of all ongoing connections that requires significantly fewer network resources than protection based techniques. In survivable routing, the goal is to find a Route and Wavelength Assignment (RWA) such that the logical topology remains connected for all single link failures. However, even if the logical topology remains connected after any single link fault, it may not have sufficient capacity to support all the requests for data communication, for all single fault scenarios. To address this deficiency, we have proposed two independent but related problem formulations. To handle our first formulation, we have presented an Integer Linear Program (ILP) that augments the concept of survivable routing by allowing rerouting of sub-wavelength traffic carried on each lightpath and finding an RWA that maximizes the amount of traffic that can be supported by the network in the presence of any single link failure. To handle our second formulation, we have proposed a new design approach that integrates the topology design and the RWA in such a way that the resulting logical topology is able to handle the entire set of traffic requests after any single link failure. For the second problem, we have first presented an ILP formulation for optimally designing a survivable logical topology, and then proposed a heuristic for larger networks. Experimental results demonstrate that this new approach is able to provide guaranteed bandwidth, and is much more efficient in terms of resource utilization, compared to both dedicated and shared path protection schemes.     

Design of wavelength-routed optical networks for packet switchedtraffic

We consider the problem of designing a logical optical network topology for a given physical topology (or fiber layout) and a given traffic demand matrix between the end-users. Traffic between the end-users is carried in a packet-switched form and the objective of our logical topology design is to minimize the maximum congestion on the logical connections in the logical topology. The logical connections are realized by wavelength continuous paths or lightpaths between end-users and they are routed via wavelength-selective routers. Note that a topology with lower maximum link congestion will allow its traffic demand matrix to be scaled up by a larger factor. In the logical topology each node is equipped with a limited number of optical transceivers, hence logical connections cannot be set up between every pair of nodes. In this paper we present an improved lower bound for maximum congestion on any link In the logical topology. The bound is shown to be up to 50% higher than the existing ones. An analytical model for obtaining the maximum and average logical connection loads for a given logical network and traffic demand matrix is also formulated, and it has been confirmed via simulation. Finally, two heuristic algorithms for constructing a logical topology that reduces maximum logical connection congestion are presented     

Branch-exchange sequences for reconfiguration of lightwave networks

Some of today's telecommunications networks have the ability to superimpose some form of logical connectivity, or virtual topology, on top of the underlying physical infrastructure. According to the degree of independence between the logical connectivity and the physical topology, the network can dynamically adapt its virtual topology to track changing traffic conditions, and cope with failure of network equipment. This is particularly true for lightwave networks, where a logical connection diagram is achieved by assignment of transmitting and receiving wavelengths to the network stations that tap into, and communicate over, an infrastructure of fiber glass. Use of tunable transmitters and/or receivers allow the logical connectivity to be optimized to prevailing traffic conditions. With rearrangeability having thus emerged as a powerful network attribute, this paper discusses the reconfiguration phase which is the transition between the current logical connection diagram and a target diagram. We consider here an approach where the network reaches some target connectivity graph through a sequence of intermediate connection diagrams, so that two successive diagrams differ by a single branch-exchange operation. This is an attempt at logically reconfiguring the network in a way that is minimally disruptive to the traffic. We propose and compare three polynomial-time algorithms that search for “short” sequences of branch-exchange operations, so as to minimize the overall reconfiguration time. For networks made of up to 40 stations, theoretical and simulation results show that, when a randomly selected diagram is to be changed to another randomly chosen diagram, the average number of branch-exchange operations required grows linearly with the size of the network     

Survivable lightpath routing: a new approach to the design ofWDM-based networks

Network restoration is often done at the electronic layer by rerouting traffic along a redundant path. With wavelength-division multiplexing (WDM) as the underlying physical layer, it is possible that both the primary and backup paths traverse the same physical links and would fail simultaneously in the event of a link failure. It is, therefore, critical that lightpaths are routed in such a way that a single link failure would not disconnect the network. We call such a routing survivable and develop algorithms for survivable routing of a logical topology. First, we show that the survivable routing problem is NP-complete. We then prove necessary and sufficient conditions for a routing to be survivable and use these conditions to formulate the problem as an integer linear program (ILP). Due to the excessive run-times of the ILP, we develop simple and effective relaxations for the ILP that significantly reduces the time required for finding survivable routings. We use our new formulation to route various logical topologies over a number of different physical topologies and show that this new approach offers a much greater degree of protection than alternative routing schemes such as shortest path routing and a greedy routing algorithm. Finally, we consider the special case of ring logical topologies for which we are able to find a significantly simplified formulation. We establish conditions on the physical topology for routing logical rings in a survivable manner     

A Bandwidth Guaranteed Integrated Routing Algorithm in IP over WDM Optical Networks

In this paper, we have developed an integrated online algorithm for dynamic routing of bandwidth guaranteed label switched paths (LSPs) in IP-over-WDM optical networks. Traditionally, routing at an upper layer (e.g., IP layer) is independent of wavelength routing at the optical layer. Wavelength routing at the optical layer sets up a quasi-static logical topology which is then used at the IP layer for IP routing. The coarse-grain wavelength channels and the pre-determined virtual topologies with respect to some a priori assumed traffic distribution are barriers to efficient resource use and inflexible to changing traffic. We take into account the combined knowledge of resource and topology information at both IP and optical layers. With this added knowledge, an integrated routing approach may extract better network efficiencies, be more robust to changing traffic patterns at the IP layer than schemes that either use dynamic routing information at the IP layer or use a static wavelength topology only. LSP set-up requests are represented in terms of a pair of ingress and egress routers as well as its bandwidth requirement, and arrive one-by-one. There is no a priori knowledge regarding the arrivals and characteristics of future LSP set-up requests. Our proposed algorithm considers not only the importance of critical links, but also their relative importance to routing potential future LSP set-up requests by characterizing their normalized bandwidth contribution to routing future LSP requests with bandwidth requirements. Moreover, link residual bandwidth information that captures the link's capability of routing future LSPs is also incorporated into route calculation. Extensive simulation was conducted to study the performance of our proposed algorithm and to compare it with some existing ones, such as the integrated minimum hop routing algorithm and the maximum open capacity routing algorithm. Simulation results show that our proposed algorithm performs better than both routing algorithms in terms of the number of LSP set-up requests rejected and the total available bandwidth between router pairs.     

On Achieveing Bandwidth-Aware LSP//spl lambda/SP Multiplexing/Separation in Multi-layer Networks

We present a new traffic engineering (TE) model which is based on QoS rerouting and uses hybrid resilience to improve the recovery performance of multi-layer networks where an MPLS network is layered above an MPlambdaS network. We formulate the rerouting of the LSPs/lambdaSPs as a multi-constrained problem and use its polynomial reduction to find a heuristic solution that can be implemented by standardized constraint-based routing algorithms. This heuristic solution uses a cost-based routing optimization to achieve different network configurations which multiplex/separate bandwidth-aware LSPs/lambdaSPs on the network links. We formulate the resilience upon failure as a multi-objective problem consisting of finding a resilience strategy that minimizes recovery operation time and maximizes the LSP/lambdaSP restorability. A solution to this problem is proposed where a hybrid resilience framework is used to achieve restoration in the MPLS layer to complement path switching in the MPlambdaS layer. We evaluate the performance of the TE model when rerouting the tunnels carrying the traffic offered to a 23- and 31-node networks. Simulation reveals that the hybrid resilience model performs better than classical recovery mechanisms. In terms of restorability, quality of rerouting paths and rerouting stability     

Performance and testbed study of topology reconfiguration in IP over optical networks

With the widespread deployment of Internet protocol/wavelength division multiplexing (IP/WDM) networks, it becomes necessary to develop traffic engineering (TE) solutions that can effectively exploit WDM reconfigurability. More importantly, experimental work on reconfiguring lightpath topology over testbed IP/WDM networks is needed urgently to push the technology forward to operational networks. This paper presents a performance and testbed study of topology reconfiguration for IP/WDM networks. IP/WDM TE can be fulfilled in two fashions, overlay vs. integrated, which drives the network control software, e.g., routing and signaling protocols, and selects the corresponding network architecture model, e.g., overlay or peer-to-peer. We present a traffic management framework for IP over reconfigurable WDM networks. Three "one-hop traffic maximization"-oriented heuristic algorithms for lightpath topology design are introduced. A reconfiguration migration algorithm to minimize network impact is presented. To verify the performance of the topology design algorithms, we have conducted extensive simulation study. The simulation results show that the topologies designed by the reconfiguration algorithms outperform the fixed topology with throughput gain as well as average hop-distance reduction. We describe the testbed network and software architecture developed in the Defense Advanced Research Projects Agency (DARPA) Next Generation Internet (NGI) SuperNet Network Control and Management project and report the TE experiments conducted over the testbed.     

Dynamic load balancing in WDM packet networks with and without wavelength constraints

We develop load balancing algorithms for WDM-based packet networks where the average traffic between nodes is dynamically changing. In WDM-based packet networks, routers are connected to each other using wavelengths (lightpaths) to form a logical network topology. The logical topology may be reconfigured by rearranging the lightpaths connecting the routers. Our algorithms reconfigure the logical topology to minimize the maximum link load. In this paper, we develop iterative reconfiguration algorithms for load balancing that track rapid changes in the traffic pattern. At each reconfiguration step, our algorithms make only a small change to the network topology hence minimizing the disruption to the network. We study the performance of our algorithms under several dynamic traffic scenarios and show that our algorithms perform near optimally. We further show that these large reconfiguration gains are achievable in systems with a limited number of wavelengths.     

网络拓扑发现新算法及其实现

 本文首先提出一种面向IP主干网的启发式网络拓扑发现算法.该算法基于启发式、贪心法的思想,具有IP地址的自动推理和查找范围的自我调整,因而具备较强的自适应性.进而提出了一个数据链路层拓扑发现算法.该算法与已有的算法相比重点解决了无生成树协议工作下数据链路层拓扑发现、主机的拓扑构造以及集线器或无IP地址的交换机等所谓的哑设备发现问题.同时阐述了一种新的数据结构类型并给出其数学定义、专有操作及该数据结构在算法中的应用.算法已经实现并应用到我们自己开发的软件中,同时在清华大学网络研究中心实验网络环境中进行了实际测试和验证,达到了很好的效果.     

Restoration of IP Networks by Using a Hybrid Interacting Mechanism Between Layer 2 & 3 in the Networks Over OA&M

The Internet generation infrastructure is growing and moving towards a consistency model of high-speed nodes interconnected by optical core networks. Therefore, the interaction between IP and optical network layers, specifically, the routing and signalling aspects, are maturing and they can lead to enhance the services and network performance. At the same time, a consensus has emerged in the industry on utilizing IP-based protocols for the optical control plane. This paper defines a new technique for IP over Optical networks (interacting between bottom layers), considering both the IP-based control plane for optical networks as well as IP-optical network interactions (together referred to as “IP over optical networks”). In this paper, a new technique is proposed that reduces recovery time by making an interoperation between the data link layer (layer 2) with the network layer (layer 3). The proposed technique enables layer 2 with layer 3 to make a hybrid mechanism that improves the recovery time in the network through two cases (1st-Detection and 2nd-Rerouting). The technique involves detecting failure in less time through layer 2 and rerouting traffic through an alternative path between source and destination by using a new algorithm in layer 3 to deliver data packets without the need to wait for the routing protocol to update the network topology and compute the routing table. In case of the network recovery, layer 2 has demonstrated its capability to detect failure extremely quickly shown through the immediate detection of the loss of signals for the link or node. The recovery mechanism, i.e., the rerouting mechanism, which leads the node, switches the data packets through an adjacent node to its destination via the life node. The latter is created by the proposed mechanism before the occurrence of the failure. The aim of this mechanism is to avoid loss of packets, improve QoS and improve recovery time as we have shown in the results shown below.     

Survivable routing in IP-over-WDM networks: An efficient and scalable local search algorithm

In IP-over-WDM networks, a logical IP network is routed on top of a physical optical fiber network. An important challenge here is to make the routing survivable. We call a routing survivable if the connectivity of the logical network is guaranteed in the case of a failure in the physical network. In this paper we describe FastSurv, a local search algorithm for survivable routing. The algorithm works in an iterative manner: after each iteration it learns more about the structure of the logical graph and in the next iteration it uses this information to improve its solution. The algorithm can take link capacity constraints into account and can be extended to deal with multiple simultaneous link failures and node failures. In a large series of tests we compare FastSurv with current state-of-the-art algorithms for this problem. We show that it can provide better solutions in much shorter time, and that it is more scalable with respect to the number of nodes, both in terms of solution quality and run time.     

Topology discovery in heterogeneous IP networks: the NetInventory system

Knowledge of the up-to-date physical topology of an IP network is crucial to a number of critical network management tasks, including reactive and proactive resource management, event correlation, and root-cause analysis. Given the dynamic nature of today's IP networks, keeping track of topology information manually is a daunting (if not impossible) task. Thus, effective algorithms for automatically discovering physical network topology are necessary. Earlier work has typically concentrated on either 1) discovering logical (i.e., layer-3) topology, which implies that the connectivity of all layer-2 elements (e.g., switches and bridges) is ignored, or 2) proprietary solutions targeting specific product families. In this paper, we present novel algorithms for discovering physical topology in heterogeneous (i.e., multi-vendor) IP networks. Our algorithms rely on standard SNMP MIB information that is widely supported by modern IP network elements and require no modifications to the operating system software running on elements or hosts. We have implemented the algorithms presented in this paper in the context of the NetInventory topology-discovery tool that has been tested on Lucent's own research network. The experimental results clearly validate our approach, demonstrating that our tool can consistently discover the accurate physical network topology with reasonably small running-time requirements even for fairly large network configurations.     

Design of logical topologies for wavelength-routed optical networks

The problem of designing a logical topology over a wavelength-routed all-optical network (AON) physical topology is studied. The physical topology consists of the nodes and fiber links in the network. On an AON physical topology, we can set up lightpaths between pairs of nodes, where a lightpath represents a direct optical connection without any intermediate electronics. The set of lightpaths along with the nodes constitutes the logical topology. For a given network physical topology and traffic pattern, our objective is to design the logical topology and the routing algorithm so as to minimize the network congestion while constraining the average delay seen by a source-destination pair and the amount of processing required at the nodes (degree of the logical topology). Ignoring the delay constraints can result in fairly convoluted logical topologies with very long delays. On the other hand, in all our examples, imposing it results in a minimal increase in congestion. While the number of wavelengths required to imbed the resulting logical topology on the physical all optical topology is also a constraint in general, we find that in many cases of interest this number can be quite small. We formulate the combined logical topology design and routing problem described above as a mixed integer linear programming problem which we then solve for a number of cases of a six-node network. This programming problem is split into two subproblems: logical topology design, and routing. We then compare the performance of several heuristic topology design algorithms against that of randomly generated topologies, as well as lower bounds     

Chord上拓扑不匹配的研究和改进

Chord系统中没有考虑到逻辑网络拓扑和物理网络拓扑不相匹配而导致的路由效率低下,由此提出了一种利用节点IP地址信息使节点得以聚类从而达到系统逻辑网络拓扑与物理网络拓扑在一定程度上的匹配,对Chord系统改进得到了TChord系统模型,通过仿真实验证明了TChord系统在路由延迟和覆盖网络路由跳数方面比Chord系统有明显的改进,从而效提高路由效率.     

Multilayer traffic engineering for multiservice environments

Multilayer traffic engineering (MLTE) serves to provide cross-layer online network optimization techniques to cope with rapid variations and short-term evolutions in traffic patterns. MLTE extends traffic engineering as it exists in IP/MPLS-based technology toward the multilayer IP/MPLS-over-optical transport network. In addition to the IP/MPLS traffic routing, MLTE exposes much larger adaptation flexibility by building on next-generation automatic switched optical transport networks. These offer fast setup and teardown of end-to-end multi-hop optical connections (lightpaths), which are offered to the IP/MPLS layer as dynamically provisioned capacity. This dynamic nature leads to an IP/MPLS logical topology that can be reconfigured on the fly, and IP/MPLS link capacity that can be up- or downgraded as client traffic demand varies. These MLTE techniques are generally used to increase perceived network performance in terms of throughput or QoS. As such, a MLTE-managed network offers a better than best-effort service. Many types of traditional and novel services are shifting toward IP/MPLS technology. Consequentially, MLTE algorithms and strategies should be conceived with the characteristics of such services in mind. We present a MLTE strategy that can be implemented in a robust and distributed way. This strategy is then taken as the starting point in a study which evaluates its suitability to such services. We show how the strategy can be adapted considering service performance metrics such as end-to-end delay, traffic loss, and routing stability, and how such service optimizations impact general MLTE objectives such as IP/MPLS logical topology mesh size reduction.

A Shared Buffer‐Constrained Topology Reconfiguration Scheme in Wavelength Routed Networks

The reconfiguration management scheme changes a logical topology in response to changing traffic patterns in the higher layer of a network or the congestion level on the logical topology. In this paper, we formulate a reconfiguration scheme with a shared buffer‐constrained cost model based on required quality‐of‐service (QoS) constraints, reconfiguration penalty cost, and buffer gain cost through traffic aggregation. The proposed scheme maximizes the derived expected reward‐cost function as well as guarantees the required flow's QoS. Simulation results show that our reconfiguration scheme significantly outperforms the conventional one, while the required physical resources are limited.