Self-healing ATM networks based on virtual path concept

This paper proposes self-healing network techniques suitable for ATM networks in order to realize a high-reliablity B-ISDN. First, the characteristics of the virtual paths (VP) and their influence on failure restoration are discussed. A high-speed restoration technique which exploits the benefits of the VP is then proposed and described. The technique simplifies the message transmission processes and reduces the number of generated messages by using preassigned backup virtual paths. Next, the scheme used to design the backup VP routes and spare resource distribution for each link is proposed in order to create a network that applies the proposed restoration scheme. Next, self-reconstruction techniques of backup virtual paths are proposed for the realization of a reversionless restoration cycle. Finally, the feasibility of the distributed control operation is discussed     

Self-healing virtual path architecture in ATM networks

ATM network techniques have been actively researched and developed with the goal of realizing B-ISDN. ATM networks can transport signals of various services efficiently and economically, and offer the benefit of enhanced flexibility if the virtual path (VP) concept is adopted. Therefore, the ATM network will provide the infrastructure for B-ISDN. One of the most important themes in B-ISDN is the increased level of network reliability required to to match the high volume of data transmission that will be incurred by the information society and the “mission critical” nature of such data. The authors summarize self-healing network (SHN) schemes they have developed, and discuss problems that must be solved to realize SHN     

Virtual path routing for survivable ATM networks

The advent of high-capacity optical fiber has increased the impact of a network failure in high-speed networks since a large volume of data can be lost even in a short outage. Self-healing algorithms have previosly been proposed to achieve fast restoration from a failure, but their success greatly depends on how traffic is distributed and how spare capacity is dimensioned over the network when a failure happens. Thus, in order to offer better network survivability, it is crucial that a network manager realizes a restorable traffic assignment in response to changing traffic demand and facility network configuration. The authors address the problem of virtual path routing for survivable asynchronous transfer mode (ATM) networks. An algorithm is developed to find a virtual path configuration and bandwidth assignment that minimizes the expected amount of lost flow upon restoration from a network failure. The concept of two-step restoration is introduced to achieve fast restoration as well as optimal reconfiguration. The problem can be formulated as a nonlinear, nonsmooth multicommodity flow problem with linear constraints. A modified flow deviation method is developed to obtain a near-optimal solution, where premature convergence to a nonsmooth point could be avoided by adjusting an optimization parameter. The result of the performance evaluation indicates that the proposed routing scheme can detect the links that are vulnerable to a failure under the current traffic demand pattern and adjust a flow so as to improve the network survivability level     

Competitive routing of virtual circuits in ATM networks

Classical routing and admission control strategies achieve provably good performance by relying on an assumption that the virtual circuits arrival pattern can be described by some a priori known probabilistic model. A new on-line routing framework, based on the notion of competitive analysis, was proposed. This framework is geared toward design of strategies that have provably good performance even in the case where there are no statistical assumptions on the arrival pattern and parameters of the virtual circuits. The on-line strategies motivated by this framework are quite different from the min-hop and reservation-based strategies. This paper surveys the on-line routing framework, the proposed routing and admission control strategies, and discusses some of the implementation issues     

MSB虚通路自愈在ATM网络中的应用

针对已有的 ATM自愈方式 ,提出了基于多段备份虚通路概念的自愈方法。利用 P/ T方法着重对恢复概率进行了公式推导 ,最后仿真计算结果表明 ,该方法要比已有的方法可靠性高。     

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.     

A simple bandwidth management strategy based on measurements ofinstantaneous virtual path utilization in ATM networks

A new connection admission control method based on actual virtual path traffic measurements is proposed to achieve high bandwidth efficiency for various types of traffic. The proposed method is based on the measurement of instantaneous virtual path utilization, which is defined as the total cell rate of the active virtual channels normalized by the virtual path capacity. A low-pass filter is used to determine the instantaneous virtual path utilization from crude measurements. A smoothing coefficient formula is derived as a function of the peak rate of the virtual channel. The residual bandwidth is derived from the maximum instantaneous utilization observed during a monitoring period. Simulation shows that the proposed method achieves statistical multiplexing gains of up to 80% of the limit possible with optimum control for similar traffic sources. It can be implemented with very simple hardware. The admission decision is simple: the requested bandwidth is compared with the residual bandwidth. This method is therefore well suited for practical asynchronous transfer mode switching systems     

Virtual source-based minimum interference path multicast routing in optical virtual private networks

Virtual Private Network (VPN) services over the Internet are gaining increased acceptance due to the economic benefits and flexibility. However, with difficulties of providing sufficient transmission capacity for value-added and mission-critical services, the Optical VPN (OVPN) deploying Dense Wavelength-Division Multiplexing (DWDM) technology has been seen as a favorable approach for realizing the future VPN services. In an OVPN, the Routing and Wavelength Assignment problem plays a key role for capacity utilization and therefore the Multicast Routing and Wavelength Assignment problem has been the dominant issue in a DWDM-based OVPN. In this paper, using Virtual Source (VS) nodes that have splitting and wavelength conversion capabilities, we propose a new Multicast Routing and Wavelength Assignment method for multicast sessions. The algorithm combines the VS-based tree generation approach with Multi-Wavelength Minimum Interference Path Routing (MW-MIPR) that chooses a path that does not interfere too much with potential future multicast session requests.     

ATM网上基于蚂蚁算法的VC路由选择方法

针对ＡＴＭ网中的ＶＰ／ＶＣ路由选择问题,本文提出了一种新颖的基于蚂蚁算法的ＶＣ路由选择方法。实验表明,该方法可以根据网络当前的业务情况,以及用户提出的时延要求,有效地实现ＶＣ路由选择。     

Performance analysis for the dynamic virtual path bandwidth control method in ATM networks

Broadband ISDN (integrated services digital network) should provide various kinds of communication services for multimedia traffic, including voice, computer data, still picture and motion video, and an ATM (asynchronous transfer mode) technology is expected to satisfy those demands. In ATM networks, a VP (virtual path) concept is introduced for simplifying the network resource management. However, if the bandwidth of each VP is fixed, it cannot absorb traffic load fluctuation. In this case, it is likely to happen that one VP has no remaining bandwidth while other VPs on the same physical link have free capacities. Another extremity is that a VP is not introduced, and that all VCs along the same physical link share the whole bandwidth of the link. This can achieve an efficient use of the link, but it apparently requires complicated call set-up procedures. In this paper, we propose a new dynamic VP bandwidth control method, in which the bandwidth allocated to each VP is dynamically changed according to traffic fluctuation. More specifically, in the case that multiple VPs are multiplexed on the same link between two nodes, when the utilization of some VP is increased, that VP requests an additional bandwidth. When the traffic load becomes low and the utilization of a VP is decreased, a part of the assigned bandwidth is released. We consider two methods for this purpose; one is the basic method in which the bandwidth increase request is issued after the VP bandwidth is exhausted. The other is the look-ahead method where the bandwidth increase is requested in advance before the bandwidth starvation. An approximate analysis for the above methods is provided, and the validation of its accuracy is assessed by comparing with simulation results. Through numerical examples, we show that our methods can provide performance improvement in terms of call loss probabilities of each VP.     

A framework for inter-domain routing in virtual coordinate based mobile networks

Routing is considered to be one the most challenging problems in mobile ad hoc networks. It has been shown that the use of virtual coordinates or identifiers for efficient routing and data management has several advantages compared to classical topology control techniques based on pre-defined addresses or geographical coordinates. However, these advantages only hold for single domain networks with limited mobility. In a previous paper, we discussed the challenges arising from using virtual coordinates for routing (to a particular destination ID or to indexed data or resources) in mobile networks in multi-domain network scenarios. We developed a solution by managing data with a distributed hash table scheme. Based on our virtual cord protocol, we then implemented inter-domain routing using appropriate indirections. That approach, however, was still limited in finding efficient routes over multiple transit networks. In this paper, we extend that work by defining a framework for optimized inter-domain routing. In particular, we investigate the use of ant colony optimization for optimizing routes between multiple network domains. We show how distributed routing tables can be created and maintained and we outline a heuristic for finding candidate routes. Simulation experiments confirm the efficiency of the selected routes both on a intra and on a inter-domain level.     

A linear‐based trunk reservation routing algorithm for ATM networks

In this paper a practical routing algorithm is proposed that increases the network throughput irrespective of the network traffic load. Its effectiveness is based on an efficient cost function which achieves a successful trade‐off between the use of the minimum‐hop routes and the application of the load‐balancing concept. Moreover, it employs the known Trunk Reservation notion according to a probability that increases linearly with the traffic load. This results in an effective compromise of the performance of the algorithm between light and heavy traffic loads. Finally, its simplicity and its suitability for a real‐time application render it as an efficient routing algorithm for ATM networks. Copyright © 1999 John Wiley & Sons, Ltd.     

Resource management with virtual paths in ATM networks

A virtual path connection (VPC) is a labelled path which can be used to transport a bundle of virtual channel connections (VCCs) and to manage the resources used by these connections. The virtual network is organized as a collection of VPCs which form a VPC, or logical, overlay network. If the VPCs are permanent or semi-permanent and have reserved capacity, establishing new VCCs requires simple connection admission decisions at the VPC terminators of existing VPCs. This would enable faster connection establishment since transit nodes are not involved in the connection setup. The virtual path concept also allows the possibility of segregating traffic types according to quality of service requirements. However, the extent to which VPC provisioning is able to improve network efficiency is dependent on the resource management decisions that determine the VPC topology and capacity allocations. The article surveys resource management using virtual paths in an ATM network. Of interest are techniques which modify the VPC topology and capacity assignments in order to adapt to changing traffic conditions and possible network failures. The resource management activities employed to facilitate such adaptation can be categorized by the timescale on which they operate. On the shortest timescale are strategies for dynamically making minor changes to the VPC topology or capacity assignments. On a somewhat longer timescale are strategies for making more widespread modifications to the VPC overlay network. This would be appropriate for traffic changes based on time of day and for recovering from network failures. Finally, on an even longer timescale, strategies may be employed to design a general VPC overlay network, to be used at startup or after major network upgrades. Solutions to VPC resource management for each of these timescales are discussed     

The layout of virtual paths in ATM networks

We study the problem of designing a layout of virtual paths (VPs) on a given ATM network. We first define a mathematical model that captures the characteristics of virtual paths. In this model, we define the general VP layout problem, and a more restricted case; while the general case layout should cater connections between any pair of nodes in the network, the restricted case layout should only cater connections between a specific node to the other nodes. For the latter case, we present an algorithm that finds a layout by decomposing the network into subnetworks and operating on each subnetwork, recursively; we prove an upper bound on the optimality of the resulting layout and a matching lower bound for the problem, that are tight under certain realistic assumptions. Finally, we show how the solution for the restricted case is used as a building block in various solutions to more general cases (trees, meshes, K-separable networks, and general topology networks) and prove a lower bound for some of our results. The results exhibit a tradeoff between the efficiency of the call setup and both the utilization of the VP routing tables and the overhead during recovery from link disconnections     

QUARTS-II: a routing simulator for ATM networks

This article presents a discrete-event simulator, called QUARTS-II, that can be used for the design and analysis of routing protocols for ATM networks. This simulator shares many high-level features of the ATM Forum's P-NNI routing protocol; topology-state advertisement, on-demand source routing, call admission control and generic call admission control, hierarchical routing, and crank-back and rerouting. Simulations can be carried out at both the call and cell levels. Although this simulation tool has been designed primarily to simulate routing protocols, it can easily be extended to simulate other elements of an AIM traffic control architecture     

Distributed routing protocols for ATM extended Banyan networks

It is well known that a multistage banyan network, which is a single-path blocking structure, becomes rearrangeable nonblocking in a circuit-switching environment if the number of its stages is increased so as to obtain a Benes network. Banyan networks, provided with a shared queue in each switching element, have often been proposed as the core of an interconnection network for an ATM packet switching environment. In this scenario, if the classical interstage backpressure protocols are used, adding stages to a banyan network can even degrade the banyan network performance, in spite of the multipath capability given by the additional stages. A class of new simple interstage protocols is here defined to operate in the added stages of the banyan network so that a sort of sharing of the queueing capability in each added stage is accomplished. Large improvements in the traffic performance of these extended banyan networks are obtained, especially in the region of offered loads providing a low packet loss probability     

Multicast routing strategies for zoned VP-based ATM networks

In ATM networks, the concept of virtual path (VP) greatly simplifies cell processing in switches. The virtual channel connection (VCC) can be more quickly and efficiently established by good strategies of resource management. The method of constructing virtual path and the strategies of managing and allocating resources greatly affect the performance of the system operation. We propose a new architecture and the corresponding methods of constructing virtual paths; various methods and strategies, such as bandwidth control, rerouting, resource management, and fault recovery, are studied (Lee and Shie 2000). This paper focuses on multicast routing and analyzes some algorithms for this model. Simulation results show the good performance in bandwidth utilization, blocking probability, and loss probability     

Traffic analysis for multiparty videoconferencing in virtual path‐based ATM networks

With effective bandwidth concept encapsulating cell‐level behaviour, asynchronous transfer mode (ATM) network design and analysis at the call‐level may be formulated in the framework of circuit‐switched loss networks. In this paper, we develop an analytical framework for a kind of multiparty videoconferencing in the VP‐based ATM network at call‐level. For this kind of conference, only the video of the current speaker is broadcast to other conferees. We first address several conference management issues in the VP‐based ATM network, including the bandwidth allocation strategies, routing rule, call admission policy and speaker change management. Next, we formulate a traffic model for the conferences. Since an exact analysis of such a multiparty conference network is mathematically intractable, an approximate analysis for such conferences in a fully connected VP network is performed. The key of our method is to make use of the reduced‐load approximation and open Jackson network model to derive the traffic loads from new conferences as well as that from the speaker change of the on‐going conferences. Our study shows that the proposed analysis can give accurate predictions of the blocking probabilities for the new conference calls as well as video freeze probabilities for the on‐going conferences. Copyright © 2000 John Wiley & Sons, Ltd.     

光网络中基于路径计算单元的路由机制研究

针对大规模多层多域光网络群故障发生时的网络受损情况,提出基于路径计算单元(PCE)架构的跨域路由算法进行快速恢复,并基于OMNet平台对多层多域路由方案进行了性能仿真分析。结果表明,基于PCE架构的路由策略在群故障发生时能够大大减少网络中的路径计算请求泛洪信息,降低路由计算收敛时间,可以提高全网剩余资源的资源利用率,为业务的快速恢复提供了路由基础。     

Integrated dynamic distributed routing and admission control in ATM networks

A node-by-node admission control and routing scheme for ATM networks is devised. The scheme is based on the subdivision of traffic into a number of classes, characterized by different performance requirements. At each network node, for all outgoing links, link capacity partitions are periodically assigned to the traffic classes, as the result of an optimization problem over a fixed time interval. Local access control rules compute the maximum number of connections of each class that a link can accept within the assigned capacity. Incoming call connection requests are forwarded in a hop-by-hop fashion. Each node traversed, first checks the presence of resources needed to accept a new connection and guarantee all quality of service (QoS) requirements. This is done by using the local access control rule. Then, it chooses the next node along the path on the basis of a distributed routing strategy. This minimizes a cost function accounting for local instantaneous information, as well as for aggregate information that is passed periodically among adjacent nodes. Two routing strategies are introduced. In the first scheme, a new call is rejected if, at a certain node along the path, there are not enough resources to guarantee QoS requirements, and no recovery mechanism is implemented. In the second scheme, an alternative path is looked for after the first failure. Simulation results are presented which show a comparison between the two proposed routing strategies. Comparison is also made between the proposed scheme and the other approaches. © 1997 John Wiley & Sons, Ltd.