On the reliability of links in a ring network

This paper analyzes the reliability of links in a computer network which is configured in a ring topology. It will be shown that the expression for reliability of elements connected in series is not adequate for computing the reliability of links in a ring network. Consequently, new expressions for computing such reliability for rings with and without back-up links are proposed. Furthermore, an optimal back-up links assignment which guarantees optimal links reliability is formulated.     

Survivable SONET networks-design methodology

A prototype software system that implements a methodology for the strategic planning of survivable interoffice networks is presented. The software system determines strategic locations and ring types for synchronous optical network ring placement. Two types of survivable network architectures are considered-1:1 diverse protection and SONET self-healing rings. The software considers three types of SONET self-healing rings-unidirectional, 2-fiber bidirectional, and 4-fiber bidirectional. Hubbing is assumed in all architectures. Inputs include nodes, links, connectivity, facility hierarchy, and multiyear point-to-point demands, together with the costs of fiber material and splicing, route mileage (installation), and multiplexors and regenerators of different rates. The outputs are a set of near-optimal rings based on cost, specifying the ring types and rates, fiber span sizes and counts, regenerator locations and speeds, the topology (set of links to be used), and the network cost. In addition, the software outputs the time in the planning period that each ring and fiber span should be installed     

An algorithm for designing rings for survivable fiber networks

The authors present an algorithm for routing fiber around a ring in a network, when the network nodes, links, connectivity, and which offices are to be used on that ring together are known. The algorithm aids automated survivable network planning. The algorithm was programmed in C, and run on a SPARC-station. Under certain conditions, the problem degenerates to the traveling salesman problem, and the ring routing algorithm degenerates to the nearest neighbor method of solving that problem     

Multiclass scheduling algorithms for the DAVID metro network

The data and voice integration over dense wavelength-division-multiplexing (DAVID) project proposes a metro network architecture based on several wavelength-division-multiplexing (WDM) rings interconnected via a bufferless optical switch called Hub. The Hub provides a programmable interconnection among rings on the basis of the outcome of a scheduling algorithm. Nodes connected to rings groom traffic from Internet protocol routers and Ethernet switches and share ring resources. In this paper, we address the problem of designing efficient centralized scheduling algorithms for supporting multiclass traffic services in the DAVID metro network. Two traffic classes are considered: a best-effort class, and a high-priority class with bandwidth guarantees. We define the multiclass scheduling problem at the Hub considering two different node architectures: a simpler one that relies on a complete separation between transmission and reception resources (i.e., WDM channels) and a more complex one in which nodes fully share transmission and reception channels using an erasure stage to drop received packets, thereby allowing wavelength reuse. We propose both optimum and heuristic solutions, and evaluate their performance by simulation, showing that heuristic solutions exhibit a behavior very close to the optimum solution.     

Evaluation of throughput and protection in optically switched metropolitan network architectures

In this study, we investigate the performance of optical packet/burst switched (OPS/OBS) architectures connected as mesh and as ring topologies for future optical metropolitan networks. Network throughput and protection to link failure under uniform traffic distribution for all nodes are investigated to evaluate the sensitivity of OPS/OBSN performance. Our data are based on analytic results and computer simulations that include a comparison between various mesh and ring topologies. We also consider detailed traffic distributions over the network links and the impact caused by failure of more or less loaded links, thus providing a method to select links that require protection, which can be very useful in network planning.     

Flooding Strategy for Target Discovery in Wireless Networks

In this paper, we address a fundamental problem concerning the best flooding strategy to minimize cost and latency for target discovery in wireless networks. Should we flood the network only once to search for the target, or should we apply a so-called “expansion ring” mechanism to reduce the cost? If the “expansion ring” mechanism is better in terms of the average cost, how many rings should there be and what should be the radius of each ring? We separate wireless networks based on network scale and explore these questions. We prove that two-ring and three-ring schemes can reduce the cost of flooding compared to a single attempt, and we provide a general formula to determine good parameters for the two-ring and three-ring hop-based flooding schemes. Through simulations, we show that choosing flooding parameters according to our techniques gives performance close to that of ideal flooding schemes. Afterwards, we extend our work from the single target discovery problem to the multi-target discovery problem. We show that a properly chosen searching radius can save much more searching cost than a simple radius selection scheme for multi-target discovery problems.     

Network Reliability Optimization via the Cross-Entropy Method

Consider a network of unreliable links, each of which comes with a certain price, and reliability. Given a fixed budget, which links should be purchased in order to maximize the system's reliability? We introduce a new approach, based on the cross-entropy method, which can deal effectively with the constraints, and noise introduced when estimating the reliabilities via simulation, in this difficult combinatorial optimization problem. Numerical results demonstrate the effectiveness of the proposed technique     

Reducing Network Cost of Many-to-Many Communication in Unidirectional WDM Rings With Network Coding

In this paper, we address the problem of traffic grooming in wavelength-division multiplexing rings with all-to-all and its generalization to many-to-many service by using network coding. We consider minimizing the number of line terminating equipment on two types of unidirectional rings, namely, single-hub and unhubbed rings, as our objective. In single-hub rings, we investigate the minimum cost provisioning of uniform all-to-all traffic in two cases: where network coding is used to linearly combine data, and where it is not used and data are transmitted without coding. We generalize the service mode to many-to-many and evaluate the cost of provisioning. In unhubbed ring, we propose a multihub approach to obtain the minimum cost provisioning in the case of all-to-all and many-to-many traffic. In each type of ring topology, two network scenarios are considered: first, the distinct communication groups in the ring are node-disjoint, and second, the different groups may have common member nodes. From our numerical results, we find that under many-to-many traffic pattern for both scenarios, network coding can reduce the network cost by 10%–20% in single-hub rings and 1%–5% in unhubbed rings in both network scenarios.      

Ring–mesh topology design in a SONET–WDM network

This article deals with a ring–mesh network design problem arising from the deployment of an optical transport network. The problem seeks to partition the set of demand pairs to a number of rings and a mesh cluster, and to determine the location of the optical cross-connect system (OXC), while minimizing the total cost of optical add-drop multiplexers (OADMs), OXCs, and fiber links. We formulate this problem as a zero-one integer programming problem. In strengthening the formulation, we develop some valid inequalities for the zero-one quadratic (knapsack) polytope and a column generation formulation that eliminates the symmetry of ring configurations. Also, we prescribe an effective tabu search procedure for finding a good quality feasible solution, which is also used as a starting column for the column generation procedure. Computational results show that the proposed solution procedure provides tight lower and upper bounds within a reasonable time bound.     

Physical topology design for survivable routing of logical rings in WDM-based networks

In a wavelength-division multiplexed (WDM)-based network, a single physical link failure may correspond to multiple logical link failures. As a result, two-connected logical topologies, such as rings routed on a WDM physical topology, may become disconnected after a single physical link failure. We consider the design of physical topologies that ensure logical rings can be embedded in a survivable manner. This is of particular interest in metropolitan area networks, where logical rings are in practice almost exclusively employed for providing protection against link failures. First, we develop necessary conditions for the physical topology to be able to embed all logical rings in a survivable manner. We then use these conditions to provide tight bounds on the number of physical links that an N-node physical topology must have in order to support all logical rings for different sizes K. We show that when K/spl ges/4 the physical topology must have at least 4N/3 links, and that when K/spl ges/6 the physical topology must have at least 3N/2 links. Subsequently, we generalize this bound for all K/spl ges/4. When K/spl ges/N-2, we show that the physical topology must have at least 2N-4 links. Finally, we design physical topologies that meet the above bounds for both K=4 and K=N-2. Specifically, our physical topology for embedding (N-2)-node rings has a dual hub structure and is able to embed all rings of size less than N-1 in a survivable manner. We also provide a simple extension to this topology that addresses rings of size K=N-1 and rings of size K=N for N odd. We observe that designing the physical topology for supporting all logical rings in a survivable manner does not use significantly more physical links than a design that only supports a small number of logical rings. Hence, our approach of designing physical topologies that can be used to embed all possible ring logical topologies does not lead to a significant overdesign of the physical topology.     

Hierarchical Ring Network Design Using Branch-and-Price

We consider the problem of designing hierarchical two layer ring networks. The top layer consists of a federal-ring which establishes connection between a number of node disjoint metro-rings in a bottom layer. The objective is to minimize the costs of links in the network, taking both the fixed link establishment costs and the link capacity costs into account.Hierarchical ring network design problems combines the following optimization problems: Clustering, hub selection, metro ring design, federal ring design and routing problems. In this paper a branch-and-price algorithm is presented for jointly solving the clustering problem, the metro ring design problem and the routing problem. Computational results are given for networks with up to 36 nodes.     

K-terminal reliability in ring networks

The authors present a new formula for computing K-terminal reliability in a communication network whose stations and links (vertices and edges) form a network graph G having a ring topology, where K-terminal reliability is the probability R_K(G) that a subset of R specific terminal stations in G can communicate. This new formula is applied to three Fiber Distributed Data Interface (FDDI) ring-network topologies, and for each topology the authors derive closed-form polynomial expressions of R_K(G) in terms of the failure probabilities of links, network ports, and station common units. The authors define the concept of the K-minimal Eulerian circuit and use combinations of these circuits to obtain K-graphs and their resulting dominations, thus extending the use of K-graphs to ring networks in which data messages, tokens, or other control frames traverse operative network links with an Eulerian tour. Distinct K-graphs having a nonzero sum of dominations are called noncanceled K-graphs and correspond exactly to terms in closed-form polynomial expressions of R_K(G). The authors show that trees have only one K-graph and that counter-rotating dual rings and rings of trees have at most 2K+1 noncanceled R-graphs. These results contribute the first closed-form polynomial R-terminal reliability expressions for the ring-of-trees topology. The results are useful in evaluating dependability, reliability, availability, or survivability of token rings and similar networks     

Lightpath arrangement in survivable rings to minimize the switchingcost

This paper studies the design of low-cost survivable wavelength-division-multiplexing (WDM) networks. To achieve survivability, lightpaths are arranged as a set of rings. Arrangement in rings is also necessary to support SONET/SDH protection schemes such as 4FBLSR above the optical layer. This is expected to be the most common architecture in regional (metro) networks. We assume that we are given a set of lightpaths in an arbitrary network topology and aim at finding a partition of the lightpaths to rings adding a minimum number of lightpaths to the original set. The cost measure that we consider (number of lightpaths) reflects the switching cost of the entire network. In the case of a SONET/SDH higher layer, the number of lightpaths is equal to the number of add-drop multiplexers (ADMs) (since two subsequent lightpaths in a ring can share an ADM at the common node). We prove some negative results on the tractability and approximability of the problem and provide an approximation algorithm with a worst case approximation ratio of 8/5. We study some special cases in which the performance of the algorithm is improved. A similar problem was introduced, motivated, and studied by Liu, Li, Wan and Frieder (see Proc. INFOCOM 2000, p.1020-1025, 2000) Gerstel, Lin and Sasaki, (see Proc. IEEE INFOCOM '98, p. 94-101, 1998)(where it was termed minimum ADM problem). However, these two works focused on a ring topology while we generalize the problem to an arbitrary network topology     

Impacts of Hierarchy in Ethernet Ring Networks on Service Resiliency

In transport networks, a multi‐ring architecture is very useful to facilitate network planning and to design and provide more resilient services for customers. Unlike traditional synchronous optical network multi‐rings, the service resiliency of Ethernet‐based multi‐rings is significantly impacted by the ring hierarchy because a link or node failure in a certain level ring triggers filtering database flush actions in all higher level rings as well as in the ring with the failure, and consequently a large amount of duplicated data frames may be flooded. In this paper, we investigate how the ring hierarchy impacts the service resiliency of multi‐ring networks. Based on extensive experiments on various single‐ and multiple‐link failures, we suggest two effective inter‐ring connection rules to minimize the transient traffic and to ensure more resilient multi‐ring networks. In addition, we consider a flush optimization technique called e‐ADV, and show that the combination of e‐ADV and multi‐ring structures satisfying our inter‐ring connection rules results in a more attractive survivability performance.     

A comparison of ring and tree embedding for real-time group multicast

In general topology networks, routing from one node to another over a tree embedded in the network is intuitively a good strategy, since it typically results in a route length of O(logn) links, n being the number of nodes in the network. Routing from one node to another over a ring embedded in the network results in route length of O(n) links. However, in group (many-to-many) multicast, the overall number of links traversed by each packet, i.e., the networks elements on which resources must possibly be reserved, is typically O(N) for both tree and ring embedding, where N is the size of the group. The paper focuses on tree versus ring embedding for real-time group multicast in which all packets should reach all the nodes in the group with a bounded end-to-end delay. Real-time properties are guaranteed by the deployment of time-driven priority in network nodes. In order to have a better understanding of the nontrivial problem of ring versus tree embedding, we consider static, dynamic and adaptive group multicast scenarios. Tree and ring embedding are compared using different metrics. The results are interesting and counterintuitive, showing that embedding a tree is not always the best strategy. In particular, dynamic and adaptive multicast on a tree require a protocol for updating state information during operation of the group. Such a protocol is not required on the ring where the circular topology and implicit token passing mechanisms are sufficient. Moreover, the bandwidth allocation on the ring for the three multicast scenarios is O(N), while on a general tree it is O(N) for the static multicast scenario and O(N/sup 2/) for the dynamic and adaptive multicast scenarios.     

一种基于ITU-T G.8032的多级保护倒换机制

ITU-T G.8032协议只定义了以太环网中一级链路故障情况下的保护方案,对于多级链路故障,缺乏具体的解决方案。文章阐述了ITU-T G.8032中单环和多环的工作原理,分析了多环中存在的问题及缺陷,在此基础上提出了一种针对多环的多级保护倒换机制。该机制利用多环中虚链路的概念,通过对虚链路故障检测以及虚链路保护进行研究,实现了对以太环网中多级链路故障的保护。测试结果表明,多级保护倒换的时间在50ms以内,满足电信级以太网的网络自愈时间要求,提高了以太网的可靠性。     

Capacity versus robustness: a tradeoff for link restoration in meshnetworks

Link recovery in high-speed four-fiber networks can be achieved using dynamic searches, covers of rings, or generalized loopback. We present a method to provide link recovery for all links in a network without using all links for backup traffic transmission. The method extends generalized loopback to operate on a subgraph of the full backup graph. The backup capacity on such links can then be used to carry unprotected traffic, i.e., traffic that is not recovered in case of a failure, while primary fibers on the links retain failure protection. Although all primary fibers remain fully robust to single-link failures, reserving links for unprotected traffic reduces a network's ability to recover from multiple failures. We explore the tradeoff between capacity and robustness to two-link failures for several typical high-speed optical fiber networks, comparing the properties of three link-restoration algorithms based on generalized loopback with the properties of covers of rings. Our results demonstrate robustness comparable or superior to that available with covers of rings while providing an additional unprotected traffic capacity of roughly 20% of the network's primary capacity     

Optimal Cost Stacked Uni-Directional Path Switched SONET/SDH Ring Design

SONET/SDH rings appear to be well-positioned to serve as the transport network for the next generation of voice and data networks. The problem of designing optimal ring networks, however, poses considerable challenges. In this paper, we have formulated the optimal cost stacked uni-directional path switched (UPSR) ring design problem. Given a set of demands between nodes which are arranged in a fiber ring topology, the problem is one of designing multiple rings stacked on the topology to carry the nodal demands. This design is to be carried out in a manner to minimize the overall equipment cost which includes three major components: a nodal add/drop multiplexer cost, an express node cost and a fixed per ring cost. We have shown that this problem is NP-hard and have proposed adapted bin-packing and LP column generation based heuristics and a cost lower bound. In numerical studies, the hybrid bin-packing and column generation heuristics were both observed to produce designs which were within 10% of the cost lower bound on average. However, the adapted bin-packing heuristic yielded a slightly worse cost performance but was found to be considerably faster than the column generation heuristic. Overall, choice of appropriate heuristic depends on the desired run-time performance.     

Ultra-wideband slotline dispersion measurements using ring resonator

The design for an ultra-wideband coplanar waveguide-fed slotline ring resonator is presented. The broadband feed system permits dispersion measurements to be made over the frequency range 2?220 GHz using a single circuit and coplanar waveguide probes connected to a vector network analyser. Measured effective dielectric constant data from a number of different rings using thin-film copper on alumina is presented, and compared with a theoretical prediction using the spectral domain approach, the agreement being better than 3.5%.     

Reliability and cost evaluation of third-generation wireless accessnetwork topologies: a case study

The "explosive growth in bursty traffic" changes the network dynamics and requires a good evaluation of various classes of service when designing an access network. From a topological standpoint, the multiservice networks in this paper are heterogeneous systems which integrate both a core and some wireless access networks into an infrastructure similar to third-generation wireless networks. Such networks require reliable and cost-effective solutions to the problem of selecting access technologies for satisfying performance and quality of service requirements related to the services and applications envisioned. This paper analyzes the reliability aspects of some access network topologies to insure a certain level of quality of service at the lowest cost for the end users. It considers a mass market equivalent to 1.6 million subscribers, the objective being to determine the cost the users are ready to pay to benefit from services and applications provided by these multiservice networks. For these purposes, the relative behavior of 3 access-network topologies are studied: the tree with parallel backup links, the ring, and the partially meshed topologies. In ring topology, simulation results show that a great connectivity in the access network is not justified in terms of reliability requirements; the partially meshed topology, even if it has redundant links which affect its cost, outperforms the tree with parallel backup links; and the ring topology is more reliable in terms of disconnected sessions than the tree topology. By considering both reliability and cost, a tree with parallel backup links appears the best topology for the access network and its cost is acceptable for the end user. This study can be extended by: (1) establishing the cost as a function of the quality of service; (2) optimizing the partially meshed topology for more reliable networks; and (3) defining a (shaping) policy to deal with a variety of traffic schemes