A new algorithm for virtual path network design in ATM networks

Virtual paths (VPs) in an ATM network form a logical network, called VP network (VPN), over the underlying physical network. VPN allows flexible management of network resources and hence its design is an important issue in designing an ATM network. In this paper, we consider the VPN design problem which is formulated as an optimization problem with the objective of minimizing the switching and transmission cost, and control and management cost. We present here, a two-phase heuristic solution for designing a good VPN for a given traffic demand. The first phase is a routing phase in which a route is found between every node pair in the network. In the second phase, paths are selected as VPs using the set of routes generated in the routing phase. A path is selected as a VP so as to minimize the following parameters: (i) the total number of VPs configured; (ii) the number of VPs carried by a link (load); and (iii) the VP hopcount, the number of VPs that are concatenated to form a virtual channel (VC). We study the performance of the proposed algorithm through extensive simulation on various networks. The results show that the VPN generated by the proposed algorithm is good in minimizing the number of VPs configured, the load on a link, and the VP hopcount. The comparison of the results obtained by the proposed algorithm and that of Ahn et al. [Virtual path layout design in ATM networks, in: Proceedings of IEEE INFCOM’94, Toronto, Ontario, Canada, 1994, pp. 192–200] shows that our algorithm performs better.     

Joint coverage and link utilization for fast IP local protection

To mitigate the impact of failures, many IP Fast Local Recovery (IPFLR) schemes have been proposed to reroute traffic in the events of failures. However, the existing IPFLR schemes either aimed to find the alternate backup routes to protect failures, or focused on balancing the traffic load routed on the backup routes. Furthermore, in Internet, flows are often managed by shortest path routing, and therefore purely determining the backup routing paths is not sufficient in protecting the error-prone networks. In this paper, we propose a Simulated Annealing based Load balancing and Protection (SALP) scheme to determine link weights for balancing link utilization in the non-failure state and simultaneously construct backup routing tables for protecting any single link failure in IP networks. In our proposed scheme, the two most significant issues, (1) load balancing and (2) coverage, are jointly considered to recover the network operation from single link failures. In the proposed scheme, upon a failure, only the nodes adjacent to a failure are activated to divert affected traffic to backup paths without disturbing regular traffic. Numerical results delineate that the proposed scheme achieves high coverage rate and load balancing at the expense of slightly increasing the entries of backup routing table.     

Multicasting VP design methodology using simulated annealing in an ATM network

Multicast routing over semi-permanent VP (virtual path)s in an ATM (asynchronous transfer mode)-based B-ISDN (broadband integrated services digital network) determines a set of VPs connecting from a source node to destination nodes. The problem of finding the optimal constrained multicasting tree over the semi-permanent VPs in an ATM network is known to be NP (nondeterministic polynomial time)-complete. We develop an optimization methodology for searching a constrained multicast routing tree with minimum cost, using simulated annealing technique. We define the problem-dependent components such as state space and cost function, and refine the implementation-dependent factors including initial temperature and cooling schedule. The simulation results show that our optimization methodology demonstrates good behavior in terms of performance on a variety of graphs modeling the sample ATM networks.     

Reconfiguration for service and self-healing in ATM networks based on virtual paths

This paper presents a reconfiguration scheme resulting in capacity efficiency and fast restoration by utilizing the inherent benefits of Virtual Paths in ATM networks. The unified optimization of bandwidth reconfiguration is addressed so that switched ATM networks can support both service and survivability from a common pool of network spare capacity at a given time. The spare capacity is composed of idle bandwidth and freed up bandwidth from the switch pairs which have a surplus bandwidth. Fast restoration can be achieved by using the pre-optimized network spare bandwidth and preplanned backup Virtual Paths based on the link and node disjoint path routing scheme. The overall operation of the proposed self-healing strategy can be consolidated into distributed fault management functions at ATM layer based on Virtual Paths. The scheme enables a logical Virtual Paths ring protection switching in ATM networks.     

Improved WWW multimedia transmission performance in HTTP/TCP overATM networks

Transmission control protocol/Internet protocol (TCP/IP) is the de facto standard of the networking world. It dynamically adjusts routing of packets to accommodate failures in channels and allows construction of very large networks with little central management. But IP packets are based on the datagram model and are not really suited to real-time traffic. In order to overcome the drawbacks, a new network technology, ATM, is proposed. ATM provides quality of service (QOS) guarantees for various classes of applications and in-order delivery of packets via connection oriented virtual circuits. Unfortunately, when ATM is to be internetworked with the existing network infrastructure, some special signaling, addressing and routing protocols are needed. IP over ATM is one of the methods proposed by IETF. It allows existing TCP/IP applications to run on ATM end-stations and ATM networks to interconnect with legacy LAN/WAN technologies. But the performance of TCP/IP over ATM leaves something to be desired. Partial packet discard (PPD) and early packet discard (EPD) are two schemes to improve its performance. This paper proposes a “selective packet retransmission” scheme for improving HTTP/TCP performance when transmitting through ATM networks. In selective packet retransmission, we take advantage of the property of humans' perception tolerance for errors to determine whether to retransmit a corrupted TCP segment or not. For lossable data, such as images, when an error occurs because of cell losses, it will not be retransmitted. The simulations show that, for the same buffer size and traffic load, selective packet retransmission performs better than PPD, EPD, and plain TCP over ATM     

Implementation of self-healing function in ATM networks

This paper proposes an implementation scheme for the self-healing function in ATM (Asynchronous Transfer Mode) networks and assesses its performance in a developed experimental system. First, our proposed ATM self-healing scheme is described. This scheme realizes more rapid restoration of failed Virtual Paths than other self-healing algorithms, supports the node failure case, and minimizes the spare resources required. Next, an implementation scheme is proposed. We propose that the self-healing function can be implemented as a software process, and that OAM (Operation, Administration, and Maintenance) cells be utilized for fast message transmission. Next, results of a prototype system that we implemented on an ATM cross-connect system are discussed. The fundamental characteristics of restoration performance are measured using the experimental system. Based on these results, restoration characteristics of real world scale networks are estimated by computer simulations. The simulation results indicate that any-one link failure is completely restored within 2 seconds.     

An adaptive multipath routing scheme for connectionless traffic in an ATM network

This paper addresses the problem of routing connectionless traffic through an ATM network. A solution is proposed based on a per-packet adaptive multipath routing scheme which is added to the routing algorithm implemented at the Inter-Working Units. A scheme is presented that distributes packets among multiple Virtual Paths (VPs) according to the utilization of the links on these VPs. The utilization of the VPs is determined by a periodic feedback mechanism. Simulation studies show the effectiveness of the proposed adaptive multipath routing scheme.The work by J. Sole-Pareta was supported in part by a CIRIT (Generalitat de Catalunya) grant (expedient number EE92/2-338), and in part by the National Science Foundation under Grant No. INT-94033646. The work by I. Akyildiz was supported in part by the National Science Foundation under Grant No. INT-94033646.     

Comparison of recovery schemes to maximize restorable throughput in multicast networks

Multicast networks have many applications especially in real-time content delivery systems. For high-quality services, users do not expect to witness any interruption; thus, network link failure has to be handled gracefully. In unicast networks there are many approaches for dealing with link failures using backup paths. Recently, Cohen and Nakibly categorized these methods, provided linear programming formulations for optimizing network throughput under the assumption that the paths are splitable, and compared them experimentally. In this work, we take their approach and apply to the multicast failure recovery problem. We propose backup bandwidth allocation algorithms based on linear programs to maximize the throughput, and perform an experimental study on the performance of recovery schemes. We study many recovery schemes in multicast networks and propose a new recovery scheme that performs better than all other recovery scheme except the one that recomputed the whole multicast tree from scratch for each link failure.     

Congestion control based dynamic routing in ATM networks

In this paper we describe briefly a dynamic multi-path algorithm that has been considered for connection oriented asynchronous transfer mode (ATM) networks. Our scheme takes advantage of a cell multiplexing capability that has particular advantage in networks supporting variable bit rate (VBR) traffic. The fundamental objective of the scheme is to propose a congestion control based scheme that bridges the gap between routing and congestion control as the network becomes congested. The proposed routing scheme works as a shortest path first algorithm under light traffic conditions. However, as the shortest path becomes congested under unbalanced heavy traffic, the source uses multiple paths when and if available to distribute the calls and reduce cell loss. This mechanism will provide good Quality of Service for clients within the given constraints. We compare the performance of the proposed scheme with other competitive schemes. The throughput and cell loss performance are compared via simulations. These have been carried out concentrating on a five node network, each with varying traffic patterns, with the intention of gaining insight into the strengths and weaknesses of the various schemes.     

Models for network design,servicing and monitoring of ATM networks based on the virtual path concept

Virtual Path (VP) concept has gained attention in terms of effective deployment of ATM networks for wide-area environment. In this paper, we present models and algorithms for network design and management of ATM networks based on virtual path concept from a network planning perspective. Our approach is based on statistical multiplexing of traffic within a traffic class by using a virtual path for the class and deterministic multiplexing of different virtual paths, and on providing dynamic bandwidth and reconfigurability through virtual path concept depending on traffic load during the course of the day. For some realistic example networks, we observe that considering network dynamism through variation of traffic during the course of a day by doing dynamic bandwidth and virtual path reconfiguration can save between 10 to 14% in network design costs compared to a static network based on maximum busy hour traffic.     

Integrating reliability and quality of service in networks with switched virtual circuits

In this paper, we present an optimization model based on cost minimization for traffic engineering of multirate and ATM networks with switched virtual circuits (SVCs). There is an increasing interest for efficient traffic engineering methods for routing and dimensioning of large and robust multiservice networks. In the case of ATM and other types of packet multiservice networks, traffic engineering requires resource allocation and performance optimization at the cell or packet level in order to assure a satisfactory grade of service (GoS) at the call level to the users. Therefore, we are interested in networks with switched connections that are flexible enough so that planners may offer cost-effective networks with guaranteed GoS even in the event of important failures. The model integrates the notions of QoS, GoS, failures and failure propagation between the physical and the logical level as well as circuit routing.     

Comparison of two path restoration schemes in self-healing networks

The state-independent (SI) and state-dependent (SD) path restoration schemes for self-healing networks are studied in this paper. The integer programming (IP) formulations for the spare capacity allocation and restoration flow assignment are first presented. Based on the optimal IP solutions, the SI and SD restoration schemes are then compared quantitatively in terms of spare capacity requirement (SCR), restoration time, VPI (virtual path identifier) redundancy (in ATM) and nodal storage capacity requirement. The comparison is based on spare optimization, single link failure scenario and 100% restoration. The SCR is also compared under single node failure scenario. It is observed that using group VP (virtual path) restoration (for either SI or SD) can substantially reduce the restoration time with only a small increase in spare capacity cost. Further, the SI restoration seems better than the SD restoration for the cases we have studied, at least in spare optimization, as its implementation is relatively easier and the difference in SCR between SI and SD is not significant. The economies of scale in transmission facility cost is also investigated in the paper.     

An efficient critical protection scheme for intra-domain routing using link characteristics

In recent years, there are substantial demands to reduce packet loss on the Internet. Among the proposed schemes, finding backup paths in advance is considered to be an effective method to reduce the reaction time. Very commonly, a backup path is chosen to be the most disjoint path from the primary path, or on the network level, a backup path is computed for each link (e.g., IPFRR). The validity of this straightforward choice is based on two things. The first thing is all the links may have the equal likelihood to fail; the second thing is, facing the high protection requirement today, it just looks weird to have links not protected or to share links between the primary and backup paths. Nevertheless, many studies have confirmed that the individual vulnerability of the links on the Internet is far from being equal. In addition, we have observed that full protection schemes (In this paper, full protection schemes means schemes (1) in which backup path is a most disjoint path from the primary path; or (2) which compute backup path for each link.) may introduce high cost (e.g., computation).In this paper, we argue that such approaches may not be cost-efficient and therefore propose a novel critical protection scheme based on link failure characteristics. Firstly, we analyze the link failure characteristics based on real world traces of CERNET2 (China Education and Research NETwork 2). The analysis results clearly show that the failure probabilities of the links in CERNET2 backbone are heavy-tailed, i.e., a small set of links causing most of the failures. Based on this observation, we find out two key parameters which strongly impact link criticality and propose a critical protection scheme for both single link failure situation and multi-link failure situation. We carefully analyze the implementation details and overhead for backup path schemes of the Internet today; the problem is formulated as an optimization problem to guarantee the routing performance and minimize the backup cost. This cost is special as it involves computational overhead. Based on this, we propose a novel Critical Protection Algorithm which is fast itself for both the single link failure and the multi-link failure versions. A comprehensive set of evaluations with randomly generated topologies, real world topologies and the real traces from CERNET2, shows that our scheme gains significant achievement over full protection in both single link failure situation and multi-link failure situation. It costs only about 30–60% of the full protection cost when the network relative availability increment is 90% of the full protection scheme.     

无线ATM通信网的越区切换控制

论文研究无线ATM通信网的越区切换控制问题,提出不同的业务类型应采用不同的切换控制方法,从而使多媒体业务的服务质量(QoS)在越区切换时仍然可以得到保证。文中着重讨论了由于无线ATM通信的特点所引起的路由重建、QoS的保证与协商,信元次序的保证等关键问题,并提出了相应的解决办法。     

Route Maintenance in IEEE 802.11 wireless mesh networks

In this paper, we propose a novel Route Maintenance scheme for IEEE 802.11 wireless mesh networks. Despite lack of mobility and energy constraints, reactive routing protocols such as AODV and DSR suffer from frequent route breakages in 802.11 based infrastructure wireless mesh networks. In these networks, if any intermediate node fails to successfully transmit a packet to the next hop node after a certain number of retransmissions, the link layer reports a transmission problem to the network layer. Reactive routing protocols systematically consider this as a link breakage (and therefore a route breakage). Transmission failures can be caused by a number of factors e.g. interference or noise and can be transient in nature. Frequent route breakages result in significant performance degradation. The proposed mechanism considers multiple factors to differentiate between links with transient transmission problems from those links which have permanent transmission problems and takes a coherent decision on link breakage. The proposed mechanism is implemented in AODV for single-radio single-channel mesh network and an extension is incorporated in multi-radio multi-channel scenarios. Simulation results show substantial performance improvement compared to classical AODV and local route repair schemes.     

An architecture for managing virtual circuit and virtual path services in ATM networks

ATM networks rely on the Virtual Circuit (VC) and Virtual Path (VP) concepts to provide unicast connection-oriented services with Quality of Service (QoS) guarantees. This paper presents a model for managing the configuration and performance of the VC and VP services in these networks. The model consists of a connection management architecture that provides the services and is instrumented for network management purposes, and a network management architecture that uses the OSI management model to provide access to the appropriate service monitoring and control functions. The network management architecture proposes complete managed object definitions that achieve a variety of monitoring and control objectives: service configuration, service performance at the call and cell level, and service control. The latter includes the capability to establish VPs and control their allocated networking capacity and also control parameters of the signaling system that affect the performance of the VC service. The architecture was implemented in its entirety on the Xunet ATM testbed, and several experiments were conducted to illustrate the trade-off between the throughput of the VC service and the allocation of capacity to VPs. The experiments further demonstrated that the signaling system can create throughput bottlenecks in the absence of VPs in the network, and therefore, the network operator can increase performance by controlling the VP distribution.     

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.     

Dynamic Path Management with Resilience Constraints under Multiple Link Failures in MPLS/GMPLS Networks

Most previous research on MPLS/GMPLS recovery management has focused on efficient routing or signaling methods from single failures. However, multiple simultaneous failures may occur in large-scale complex virtual paths of MPLS/GMPLS networks. In this paper, we present a dynamic MPLS/GMPLS path management strategy in which the path recovery mechanism can rapidly find an optimal backup path which satisfies the resilience constraints under multiple link failure occurrences. We derived the conditions to test the existence of resilience-guaranteed backup path, and developed a decomposition theorem and backup path construction algorithm for the fast restoration of resilience-guaranteed backup paths, for the primary path with an arbitrary configuration. Finally, simulation results are presented to evaluate the performance of the proposed approach.     

Self-healing routing: failure,modeling and analysis

Network failures occur frequently, and self-healing ability of existing routing protocols cannot guarantee fast route convergence under these failures without impacting packet forwarding. During routing convergence, network routes may be incorrect and even routing black holes and loops occur, which will result in extensive packet loss and thus influence network performance. To solve this problem, several improved routing solutions have been proposed. In this paper, we propose the concept and model of self-h...     

A new approach for designing fault-tolerant WDM networks

In recent years, path protection has emerged as a widely accepted technique for designing survivable WDM networks. This approach is attractive, since it is able to provide bandwidth guarantees in the presence of link failures. However, it requires allocating resources for backup lightpaths, which remain idle under normal fault-free conditions. In this paper, we introduce a new approach for designing fault-tolerant WDM networks, based on the concept of survivable routing. Survivable routing of a logical topology ensures that the lightpaths are routed in such a way that a single link failure does not disconnect the network. When a topology is generated using our approach, it is guaranteed to have a survivable routing. We further ensure that the logical topology is able to handle the entire traffic demand after any single link failure. We first present an ILP that optimally designs a survivable logical topology, and then propose 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.