In most prior work on survivable network design, lower level connection requirements are assumed to have already been "groomed" into a required set of lightpath demands. In this work, we show how grooming decisions can be directly integrated into an overall p-cycle network design for more efficiency. We use this new ability to understand how the number of grooming sites affects overall network efficiency and how grooming decisions can interact with the p-cycle protection strategy. In test case results a set of STM-1 demands are groomed into a set of STM-16 transport connections in a way that is jointly optimal considering both working path capacities and p-cycles formed to protect those paths. The study also compares different criteria for selecting grooming sites.

Shared protection promises the benefits of lower network capacity utilization without sacrificing the availability level of dedicated protection. Shared protection is often evaluated in terms of its spare capacity efficiency, but seldom in terms of real-world CAPEX (capital expenditure) costs. In this paper, we investigate the design of several shared protection architectures under a standardized cost model for the WDM layer, developed recently within the European NOBEL project. This paper presents a comparative study of the implementations and costs of these architectures under this model. Findings show a counterintuitive relationship between network capacity utilization and design cost when the network is lightly loaded.

As a research challenge we have sought to create and solve p-cycle network design problems involving 200 or more nodes. At such problems sizes, the space of all simple cycle structures on the network graph cannot even be known in practice, let alone put into a conventional ILP problem instance. The approach being taken is a combination of GA methods with ILP; GA is guided by a subsidiary ILP surrogate problem to preselect a set of collectively high merit candidate cycles to populate a size-reduced final fully detailed ILP. Feasible solutions of high quality have been obtained for an initial 200- node test case. Comparison of the result by other workers is invited.

Since the advent of p-cycles it has been understood that, in addition to their span-protecting properties, p-cycles have the same inherent protection as a BLSR ring to "on-cycle" demands that transit a failed node. It has remained less clear how to protect straddling demand flows from node failure as well. Other work has sought to achieve full node protection with extensions of the p-cycle concept such as node-encircling p-cycles, path-segment or "flow"-protecting p-cycles, and failure independent path-protecting p-cycles. Here we report a rather simple and useful finding about the problem-that high levels of node failure protection can be achieved with an ordinary set of p- cycles which designed in a way that every demand that transits a node in a straddling manner is also intercepted at points upstream and downstream on its route by some other p-cycle. We first characterize the inherent properties of ordinary minimum- capacity p-cycle network designs when inspected for use from this new standpoint. We then alter the basic network design model to maximize node restorability and even achieve 100% protection against both single node and span failures, with little additional capacity. The practical importance is that the simplicity of basics-cycles is retained, and only one set ofp-cycles is required, while efficiently achieving node failure protection either for priority paths or for all demands in a network.

We study an idea for efficient integrated protection of an IP over WDM network using the spare capacity of span-protecting p-cycles to provide protection against both optical link failures and router node failures in the IP/MPLS layer. Previously, networks using span-protecting p-cycles were designed from the point of view of a single-layer physical transport network. Also separately, it has been known how to plan capacity allocations to IP-layer logical links to support controlled levels of bandwidth oversubscription on transiting traffic flows through a failed router or ATM node. To address both failure types, however, it is unattractive to simply combine the two investments in added protection capacity. Accordingly, we have studied ways to plan a 100% span-restorable set of physical-layer p-cycles so that very high levels of transiting traffic flow can also be restored upon MPLS router node failure, with controlled worst-case oversubscription of LSP capacity allocations. In test cases it was found that the spare capacity provided by span-protecting p-cycles can provide a high level of node protection depending on the strategy used for exploring the p-cycle capacity. We think this leads to novel and efficient strategies for multi-service and multi-layer survivable traffic engineering and bandwidth management

We consider path-based survivable service provisioning in transparent optical networks with the constraints of wavelength continuity and a limited number of add/drop ports at each OXC node in the presence of limited tunability of transmitters. We develop simple but valid analytical models to estimate the effects of number of add/drop ports and transmitter tunability on survivable service provisioning performance. We propose effective algorithms for the assignments of wavelength resources and add/drop ports for each survivable connection service and conduct simulations to evaluate the impacts of number of add/drop ports and transmitter tunability on path- based survivable service provisioning and further to examine the validity of the analytical models. It is found that a certain system add/drop ratio is required at each node so as to eliminate the blocking due to the lack of free add/drop ports. A network with a higher density requires a larger relative number of add/drop ports (i.e., add/drop ratio) for a given overall blocking objective. A network with a higher density benefits more in blocking from transmitter tunability. Finally, the analytical models are verified to be able to qualitatively predict the trends and effects of all the related constraints on the performance of survivable service provisioning.

We develop design theory and related operating concepts to support multiple differentiated levels of survivability assurances for individual demands in a transport network that uses p-cycles as the basic protection method. Notably this includes an ultra-high availability (dual span failure protected) service class that is based on principles that are unique to p-cycles for dual failure protection without dynamic reconfiguration of p-cycles. Results show that p-cycle based networks operating this way could offer dual failure protection to as much as 30% of all demands in the test cases with essentially the same redundancy as the single-failure protected design. These ideas and methods can enhance the cost-competitiveness of transport network operators and enable a range of service offerings to best suit actual customer requirements on transport survivability.

p-cycles offer an approach to protection of optical transport networks which is as fast as a ring-based network but with mesh-like capacity efficiency. One misconception about p-cycle designs seems to be that they involve long protection paths, even though it is trivial to limit the circumference of cycles admitted to the design problem. In addition, through straddling span considerations the average protection path on a p-cycle is actually shorter than in a corresponding ring. Nonetheless there are some open questions regarding path and cycle circumference limit effects with p-cycles. One question is whether p-cycle networks exhibit a "threshold hop-limit" effect corresponding to that well-known aspect of span-restorable mesh networks. (Beyond the threshold hop-limit there are negligible savings in capacity.) To study this question we extend the existing p-cycle network design theory to include the capability of direct restriction of protection path lengths, rather than indirect restriction through circumference limits. A second, quite practical question is to ask how well simple limitation of cycle circumferences serves as a surrogate for a more involved design method of directly asserting a hop (or distance) limit on the maximum length of protection paths. The answers to the questions and the methods developed to address them both enhance our ability to design p-cycle networks in which optically transparent length may affect transmission quality, or where the length of protection paths may affect cost if regeneration is required en route of a protection path. The main findings are that p-cycles do exhibit threshold hop-limiting effects (at about two or three hops above those in corresponding mesh networks) and that cycle limiting is a simple and effective surrogate for direct limitation on path lengths in p-cycle design problems.

We suggest methods for achieving high dual-failure restorability in p-cycle networks that are optimally designed only to withstand all single failures, or have minimized amounts of additional capacity for dual failure considerations. In one set of circumstances we consider static p-cycles (that cannot be rearranged once established) and propose strategies to enhance the dual-failure restorability based on concepts of failure spreading and limiting the maximum number of protection relationships of any p-cycle. We then consider the case of reconfigurable p-cycles, in which the spare capacity can be reconfigured dynamically, creating a new set of p-cycles that are optimized to withstand possible second failures. Results show significant improvements of the dual-failure restorability obtained by limiting the number of protection relationships in static design. For 100% dual-failure restorability, p-cycle reconfiguration reusing most of the existing p-cycles and adding some new ones appears to be the most promising approach.

GMPLS provides standardized protocols through which nodes can request and establish (or release) lightpaths on demand between themselves and peer nodes. The primary intent is to support automated provisioning for dynamic demand environments. However, an apparently tempting assumption is that GMPLS also provides a mechanism for physical layer network restoration, wherein all effected node pairs "simply redial their connections" - simultaneously. We argue from basic considerations, and illustrate with experimental results, that this is an oversimplified view. It assumes that the problem of replacing a failed path is the same when the path fails in isolation and when numerous paths fail together from a cable cut. Without some form of preplanning, or overall coordination of the multiple simultaneous reprovisioning attempts in the latter case, no guarantees are possible about the overall extent or pattern of recovery level. Capacity over-provisioning can mitigate the risk, but may involve almost as much overprovisioning as would suffice for simple 1+1 signal duplication in the first place, which defeats one of the main aims (efficiency) of a mesh-oriented scheme.

This work introduces a significant extension to the method p-cycles for network protection. The main advance is the generalization of the p-cycle concept to protect multi-span segments of contiguous working flow, not only spans that lie on the cycle or directly straddle the p-cycle. This effectively extends the p-cycle technique to include path protection or protection of any flow segment along a path as well as the original span protection use of p-cycles. It also gives an inherent means of transit flow protection against node loss. We develop a capacity optimization model for the new scheme and compare it to prior p-cycle designs and other types of efficient mesh-survivable networks. Results show that path-segment-protecting p-cycles have capacity efficiency near that of a path-restorable network is to suggest the use of flow p-cycles to protect transparent optical express flows through a regional network.

The paper introduces an extension to the method of p-cycles for network protection. The p-cycle concept is generalized to protect path segments of contiguous working flow, not only spans that lie on the cycle or directly straddle the p-cycle. The original span protecting use of the p-cycle technique is extend to include path protection or protection of any flow segment along a path. It also gives an inherent means of protecting working flows that transit a failed node. We use integer linear programming to study the new concept and determine its inherent capacity requirements relative to prior p-cycle designs and other types of efficient mesh-survivable networks. Results show that path-segment-protecting p-cycles ("flow p-cycles") have capacity efficiency near that of the shared backup path-protection (SBPP) scheme currently favored for optical networking. Because its protection paths are fully preconnected and because it protects path segments (not entire paths), it has the potential for both higher speed and higher availability than SBPP. We also develop capacity optimization models to support 100% restoration of transiting flows through failed nodes. Only a very small additional spare capacity is needed to achieve both 100% span and intermediate node-failure restorabilities, and a very high transiting traffic restorability can be accomplished for node failure restorability given spare capacity only for span-failure protection. An immediate practical application is to suggest the use of flow p-cycles to protect transparent optical express flows through a regional network.

The most common aim in designing a survivable network is to achieve restorability against all single span failures, with a minimal investment in spare capacity. This leaves dual-failure situations as the main factor to consider in quantifying how the availability of services benefit from the investment in restorability. We approach the question in part with a theoretical framework and in part with a series of computational routing trials. The computational part of the analysis includes all details of graph topology, capacity distribution, and the details of the restoration process, effects that were generally subject to significant approximations in prior work. The main finding is that a span-restorable mesh network can be extremely robust under dual-failure events against which they are not specifically designed. In a modular-capacity environment, an adaptive restoration process was found to restore as much as 95% of failed capacity on average over all dual-failure scenarios, even though the network was designed with minimal spare capacity to assure only single-failure restorability. The results also imply that for a priority service class, mesh networks could provide even higher availability than dedicated 1+1 APS. This is because there are almost no dual-failure scenarios for which some partial restoration level is not possible, whereas with 1+1 APS (or rings) there are an assured number of dual-failure scenarios for which the path restorability is zero. Results suggest conservatively that 20% or more of the paths in a mesh network could enjoy this ultra-high availability service by assigning fractional recovery capacity preferentially to those paths upon a dual failure scenario.

We have developed a design refinement to increase the capacity efficiency of span-restorable mesh networks on sparse facility graphs. The new approach views the network as a "meta-mesh of chain subnetworks". This makes the prospect of WDM mesh networking more economically viable than with previous mesh-based designs where the average nodal degree is low. The meta-mesh graph is a homeomorphism of the complete network in which edges are either direct spans or chains of degree-2 nodes. The main advantage is that loop-back-type spare capacity is provided only for the working demands that originate or terminate in a chain and not for the entire flow that crosses a chain. The transiting ("express") flows are entirely mesh-protected within the meta-mesh graph which is of higher average degree and hence efficiency for mesh restoration than the network as a whole. Nodal equipment savings also arise from the grooming of express lightpaths onto the logical chain-bypass span. Only the meta-mesh nodes need optical cross-connect functionality. Other sites use OADMs and/or glassthroughs. The resultant designs comprise a special class of restorable network that is intermediate between pure span restoration and path restoration. Most of the efficiency of path restoration is achieved, but with a span restoration mechanism which is more localized and potentially faster and simpler than path restoration. The concept lends itself to implementation with OADMs having a passive waveband pass-through feature to support the logical chain bypass spans for express lightpaths.

We consider the problem of determining an optimal facilities route topology for an optical mesh-restorable network. In general, there will be a set of existing rights-of-way for cable ducts etc. and a limited number of new acquisition prospects for topology evolution. The enhancement of network connectivity is of particular interest in a mesh-based transport network, but new rights-of-way can be very expensive. The interaction between the edge costs and capacity savings in a mesh network is also different than in prior topology design problems. We describe a three-stage heuristic based on a particular hypothesis about the problem. The heuristic runs quickly and produces solutions that typically cannot be improved upon by the optimal formulation in 6 to 12 hours and are within 8% of optimal in cases where the optimum reference could be solved. The heuristic also provides a fairly tight upper bound to help in solving the complete problem.

We describe and test a tabu search (TS) meta-heuristic for the design of transport networks based on SONET or DWDM optical rings. The relatively simple TS procedure serves to discover incremental design enhancements following a baseline design by RingBuilder (or any other) synthesis package, or to raise confidence in the quality of the initial design. It offers a complimentary approach to existing methods and has the advantage of being applied for however much run-time is available. In metropolitan network test cases from 15 to 43 nodes it finds up to 20% savings in one to three hours.

This work is motivated by interest in restorable mesh architectures for WDM optical networking DWDM technology is expected to create an extremely modular capacity-planning situation and to produce potentially strong nonlinear economy-of-scale effects in capacity. How will this influence the design of cost-optimized mesh-restorable networks? Will it be essential to do true modular design optimization, or will the traditional rounding-up procedure still be adequate? Can a true modular design method exploit these effects for capital cost savings in the network design? What influence would strong modularity and economy-of-scale have on the evolution of the fiber facilities graph topology for these networks? We address these questions with three mathematical programming formulations that allow a comparative study of these issues in terms of the cost and architectural differences between networks designed with different treatments of the modularity issue. Results show that there are worthwhile savings to be had by bringing modularity aspects directly into the basic design formulation, rather than postmodularizing a continuous integer result, as done in most prior practice. The most significant research finding may be the demonstration of topology reduction (or paring down of the facilities graph) arising spontaneously in optimized designs under the combined effects of high modularity and economy-of-scale. This is the first quantitative indication and explanation of why less highly connected graph topologies may be preferred (at least from an economic standpoint) in future WDM networks, even though the spare capacity efficiency for mesh-based restoration is improved by higher connectivity.

Distributed path restoration based on optical cross-connects can provide highly capacity-efficient real-time restoration for WDM-based optical networking. However, to obtain an assured restoration level with the theoretically very low amounts of spare capacity that path restoration allows, one must solve, or closely approximate a solution to, the integer multicommodity maximum flow (MCMF) problem, MCMF is, however a hard combinatorial optimization problem due to what is called the "mutual capacity" aspects of the problem: which of many competing origin-destination pairs should be allowed paths over the finite spares on each span? Integer MCMF is further complicated by the nonunimodular nature of the problem, i.e., fractional flows are forbidden but would arise if solved by linear programming. This paper presents a heuristic principle that tests well against integer programming solutions of MCMF routing. The heuristic is first characterized in a centralized program, then adapted for use in a distributed path restoration protocol. In all test cases, the protocol obtains over 97% of the paths found in an optimal MCMF solution in the same network. Via OPNET simulation it is also predicted that the protocol will run in well under 2 seconds which means it could be used directly in real-time, or in distributed prefailure self-planning, for restoration. The significance is that network operators could aggressively optimize their spare capacity, toward theoretical minimums, while still assuring 100% restorability.

We describe a novel restoration strategy called virtual protection cycles (p-cycles, patents pending) for extremely fast restoration in IP networks. Originally conceived for use in WDM and Sonet transport networks, we outline the adaption of the p-cycle concept to an IP environment. In an IP router-based network, p-cycles are implemented with virtual circuits techniques (such as an MPLS label switched path, or other means) to form closed logical loops that protect a number of IP links, or a node. In the event of failure, packets which would normally have been lost are encapsulated with a p-cycle IP address and reenter the routing table, which diverts them onto a protection cycle. They travel by normal forwarding or label switching along the p-cycle until they reach a node where the continuing route cost to the original destination is lower than that at the p-cycle entry node. Diverted packets are deencapsulated (dropped from the p-cycle) at that node and follow a normal (existing) route from there to their destination. Conventional routing protocols such as OSPF remain in place and operate as they do today, to develop a longer term global update to routing tables. Diversionary flows on the p-cycle inherently cease when the global routing update takes effect in response to the failed link or node. The p-cycle thus provides an immediate real-time detour, preventing packet loss, until conventional global routing reconvergence occurs. The aim of the paper is to explain the basic p-cycle concept and its adaptation to both link and node restoration in the IP transport layer, and to outline certain initial results on the problem of optimized design of p-cycle based IP networks.

Previous work on restorable networks has shown experimentally that one can support 100% restoration with an optimized set of closed cycles of spare capacity while requiring little or no increase in spare capacity relative to a span-restorable mesh network. This is important and unexpected because it implies that future restoration schemes could be as capacity efficient as a mesh network, while being as fast as ring-based networks because there is no real-time work at any nodes other than the two failure nodes. This paper complements the prior work by giving a greater theoretical basis and insight to support the prior results. We are able to show in a bounding-type of argument that the proposed protection cycles ("p-cycles") have as high a restoration efficiency as it is possible to expect for any type of preconfigured pattern, and are categorically superior to preconfigured linear segments or trees. We are also able to show that the capacity efficiency of a fully preconfigured p-cycle network has the same well-known lower bound as that of a span restorable mesh network which is cross-connected on-demand. These results provide a theoretical underpinning for the efficiency of p-cycles and confirmation of the experimental observations.

This work develops mathematical models for path availability and provisioning resources required in various strategies for realizing high availability service paths in a transport environment of bidirectional line-switched rings or shared protection optical (wavelength division multiplexing) rings. The work originated in response to user requests for SONET service paths with unavailabilities under 30 s/year. A number of schemes for redundant routing and ring interconnection are considered as options to meet such a demanding target in the most economic way. An analytical framework for comparison of various provisioning schemes allows a "cost effectiveness" assessment of four high-performance alternatives, in terms of total resource investment and the corresponding service unavailability relative to a single-fed path construction. The logical models of cost and availability can be used in a variety of SONET or optical-ring transport planning studies or perhaps in future automated provisioning tools. An important finding is that while the availability benefit of dual-ring interconnection is high in metro-ring networks, the availability of paths through long-haul ring networks may be relatively poor due to lower limits from two-failure intra-ring combinations.

Cycle-oriented preconfiguration of spare capacity is a new idea for the design and operation of mesh-restorable networks. It offers a sought-after goal: to retain the capacity-efficiency of a mesh-restorable network, while approaching the speed of line-switched self-healing rings. We show that through a strategy of pre-failure cross-connection between the spare links of a mesh network, it is possible to achieve 100% restoration with little, if any, additional spare capacity than in a mesh network. In addition, we find that this strategy requires the operation of only two cross-connections per restoration path. Although spares are connected into cycles, the method is different than self-healing rings because each preconfigured cycle contributes to the restoration of more failure scenarios than can a ring. Additionally, two restoration paths may be obtained from each pre-formed cycle, whereas a ring only yields one restoration path for each failure it addresses. We give an optimal design formulation and results for preconfiguration of spare capacity and describe a distributed self-organizing protocol through which a network can continually approximate the optimal preconfiguration state.

The total transmission capacity required by a transport network to satisfy demand and protect it from failures contributes significantly to its cost, especially in long-haul networks. Previously, the spare capacity of a network with a given set of working span sizes has been optimized to facilitate span restoration. Path restorable networks can, however, be even more efficient by defining the restoration problem from an end to end rerouting viewpoint. We provide a method for capacity optimization of path restorable networks which is applicable to both synchronous transfer mode (STM) and asynchronous transfer mode (ATM) virtual path (VP)-based restoration. Lower bounds on spare capacity requirements in span and path restorable networks are first compared, followed by an integer program formulation based on flow constraints which solves the spare and/or working capacity placement problem in either span or path restorable networks. The benefits of path and span restoration, and of jointly optimizing working path routing and spare capacity placement, are then analyzed.

In a self-organizing system, behavior emerges at the large scale from the collective interaction of simple rules that apply at the smaller scale. The behavior that emerges is not directly apparent from inspection of the local rules or processes operating at the lower level. Few problems in engineering have been addressed with the specific idea of designing simple rules that operate in an isolated local manner to derive a desired self-organizing side effect. Some specific telecommunication network control problems have been addressed with this approach, however, in areas where conventional approaches are suffering from the "software mountain " phenomenon. In the applications of transport network restoration and traffic adaptation, this self-organizing approach promises better speed, accuracy, autonomy, and robustness than centralized control or explicit messaging-based distributed approaches. A key advance has been the development of a set of nodal rules for game-like operations on information tags (called statelets) borne on every link of the network. These rules spontaneously organize the resources of the transport network into a maximal set of simultaneously feasible paths between named points in the network. This process is adapted for restoration, provisioning, and traffic adaptation in a manner where the network is its own data base. The computational workload is distributed over the network as a whole, and external control is relaxed to focus only on large-scale tuning of what is operationally a self-organizing autonomous transport network. This paper is an applications oriented survey of the self-organizing concept and mechanism and its application to restoration, provisioning, network audit and traffic adaptation.

There are a number of contexts in transport network design where cost savings arise from providing a dedicated transmission system between two nonadjacent nodes. This occurs when the cost to terminate demands at intermediate cross-connecting and grooming nodes exceeds the alternative of providing a dedicated, perhaps only partly filled, system. Today, dedicated end-to-end "express routes" are usually found where large demands flow between major centers or to/from hubbing sites where traffic can be aggregated to warrant an express system. Smaller demand flows are usually terminated at each flexibility point en route to permit remultiplexing with other demands, thereby keeping the fiber system fill high. We consider a new means to find economic express system opportunities among combinations of the smaller co-routed demands. The hypothesis is that certain collections of demand may warrant express treatment over some common portion of their routes. These demands need not share common end nodes or be aggregated at a hub. Rather, they are discovered among the natural pattern of demand flows as a group of demands that travel together over some sequence of spans on which an express system might be cost-effective. The search problem is to detect the maximally coherent subgroups of demands en route that yield the best economic payback. Test results were obtained in four representative transport network topology and demand matrix models. Assuming a 75% level of system fill in the nonexpress baseline case, opportunities worth up to $45 M in equipment savings, relative to conventional design, were obtained using industry-supplied cost data. The concept of distributed partial-express system design may also be applicable to WDM-based networks to assign OC-n level units of demand to various express or nonexpress wavelengths.

The paper proposes and analyzes a combined framing and error control scheme for the DS3 format in which the primary framing bits are replaced with parity check bits of a rate 0.9912 extended and shortened Hamming code. A fast syndrome computation scheme is developed for the code to facilitate faster reframe times. The proposed scheme has better overall reframing performance than conventional framing, and reduces the output BER to approximately 1360P/sub e//sup 2/. This is effective against error-rate floors or "dribble error" phenomena in fiber optical transmission. Primary applications are in advanced in-service performance monitoring and for throughput enhancement in ATM networking applications using leased DS3 carrier signals.>

In the development of technologies for span failure restoration, a question arises about the restoration rerouting characteristics to be specified. In theory, maximal rerouting capacity is obtained with a maximum flow (Max Flow) criterion. However, rerouting that realizes the k-successively shortest link disjoint paths (KSP) may be faster, easier, and, in distributed implementation, more robust than a distributed counterpart for Max Flow. The issue is, therefore, what the restoration capacity penalty is if KSP is used instead of Max Flow. To explore this tradeoff, the authors present a comparative study of the effectiveness of KSP versus Max Flow as an alternative rerouting criteria in the context of transport network span restoration. The comparison applies to both centrally controlled and distributed restoration systems. Study methods include exhaustive span failure experiments on a range of network models, and parametric and analytical investigations for insight into the factors resulting in KSP versus Max Flow differences. The main finding is that KSP restoration capacity is more than 99.9% of that from Max Flow in typical network models. The hypothesis is made that a generalized "trap" topology is responsible for all KSP-Max Flow capacity differences. The hypothesis is tested experimentally and used to develop analytical bounds which agree well with observed results. These findings and data are relevant to standards makers and equipment developers in specifying and engineering future restorable networks.>

Abstract The problem of finding shortest paths arises in many contexts; testing restoration algorithms and developing design packages for large telecommunications networks are two cases where the simple task of finding sets of restoration paths can consume up to 95 per cent of the execution time of an application program. This paper presents experimental studies of several well‐known shortest‐paths algorithms adapted to the task of finding the k‐successively‐shortest link‐disjoint replacement paths for restoration in a telecommunications network with n nodes. The implementations range in complexity fromO(kn2) when based on Dijkstra's original method, through several improvements to an efficient implementation ofO(kn[v+longn]) complexity, and finally to anO(kn) implementation for the special case of edge‐sparse graphs with small integer edge weights. Here v is the maximum degree of a node in the network. Several alternatives were tested during the course of these studies, particularly with a view to minimizing the number of heap updates, These alternatives are possible because we are searching for several paths between a given pair of nodes, rather than just one path between one or more pairs of nodes. Two fairly straightforward changes yield a decrease in execution time, whereas a more complex heap management strategy consumes as much time in the added code as it releases from the main routine. Experimental results confirm the theoretical complexity of q k n log n) and demonstrate a speed‐up of nearly an order of magnitude over the simplerO(kn2) implementation in the largest networks tested. The optimized implementation is recommended for planning and operational applications of k‐shortest paths rerouting for telecommunications network restoration and restorable network design. If hop counts or small integer link weights can be used to measure distances, then the qkn) implementation is recommended, as typical telecommunications networks are edge‐sparse.

This paper presents a metric for managing dynamically reconfigurable transport networks. In such networks, one physical set of transport links can be configured into many different logical networks, in order to meet uncertain and volatile traffic demands. Connectability is a figure of merit for capturing the composite routing efficiency and capacity utilization of a transport network. Connectability is mathematically inspired by existing metrics for reliability. Reliability concepts are adapted to quantify notions of efficiency in reconfigurable networks. The authors define connectability mathematically, and set out a procedure for its' calculation in a distributed real-time setting. The centralized version of this calculation has O(n log n) time complexity. A series of simulation studies are presented to illustrate the use of connectability in characterizing strategies for transport network reconfiguration. One strategy based on the isolated calculation of connectability at each node is shown to yield lower blocking and more efficient use of transport network resources than the other strategies tested. Finally, a short study of applying connectability to restoration in a national network demonstrates that there is a continuum along which restoration can be temporarily traded off against transport network management.>

The authors report simulation results and prototype control protocols for a digital subscriber loop transmission system, which will find and operate at the highest common bidirectional transmission rate that is viable on a given loop while preserving a specified noise margin. A prototype implements the rate-adaptation and transmission protocols over a captive multigauge cable facility. Simulation results predict the accompanying symbol rate versus reach characteristics for a transceiver with the same structure as basic rate access (BRA) systems under RA-DSL control. Results show that 1.5 Mb/s could be delivered to loops of up to 2 km while subscribers out to 10 km could receive 80 kb/s. For a number of specialized or short-notice situations, RA-DSL could be the basis for a fast and flexible response vehicle. If RA-DSL cannot serve an individual combination of distance and capacity, existing methods remain. However, a statistical assessment with metro population data shows the potential for RA-DSL to satisfy 4-6 times more n*DS-0 access requests than BRA on existing copper, without carrier serving area constraints.>

The methodology used, and results obtained, in the development and verification of a protocol for real-time network restoration are described. This protocol, called selfhealing, relies on a combination of hardware and software features to achieve an advance in the speed of restoring network spans that have been cut. The hardware environment provides a paradigm for heavily parallel, asynchronous, distributed interaction. This environment is uniquely suited to interactions between digital cross-connect switches (DCS) embedded in a highly-capacity transport network. A speed determination based on an implementation of the protocol exactly as it would exist in the target DCS host machine is given.>

The technique introduced has relatively simple encoding and decoding procedures which can be implemented at the high bit rates used in optical fiber communication systems. Because it is similar to the established technique of self-synchronizing scrambling but is also capable of guiding the scrambling process to produce a balanced encoded bit stream, the technique is called guided scrambling, (GS). The concept of GS coding is explained, and design parameters which ensure good line code characteristics are discussed. The performance of a number of guided scrambling configurations is reported in terms of maximum consecutive like-encoded bits, encoded stream disparity, decoder error extension, and power spectral density of the encoded signal. Comparison of guided scrambling with conventional line code techniques indicates a performance which approaches that of alphabetic lookup table codes with an implementation complexity similar to that of current nonalphabetic coding techniques.>

M12 Stuff-ratio, clock synthesis, and signaling capacity considerations are developed for a anew class of DS-3 format in which C-bits are released DS-2 stage synchronization and frequency manipulation to a pseudo-DS-2 frequency, Fc2, at which wholly predictable DS-3 stuffing patterns arise. It is shown that the previously proposed special case of forcing 100% DS-3 stuffing literature may adversely affect the DS-1 jitter performance of the dependent M12 stage, but that this risk can be avoided by considering the wider class of freed C-bit formats which are based on deterministic patterns of ganged DS-3 stuffing, rather than 100% stuffing. The ganged stuffing approach is based on the principles (a) that synchronized DS-2s can share the same DS-3 stuffing information regardless of Fc2 rate, and (b) that certain Fc2 rates exist at which predictable repeating patterns of DS-3 stuff decisions occur.>

The derivation of a signaling channel using the redundant justification bits in the DS-3 signal is proposed to remedy the DS-3 networks lack of overhead for support of intelligent network functions. In the DS-3 network each frame of 680 time slots contains one time slot (a stuff slot) that can be used to either transmit information from an appropriate tributary or to fill out the format. In the latter case, the redundant time slot can be used to carry auxiliary signaling information. It is proposed to use the random sequence of all these redundant time slots as the basis for the new signaling channel. It is shown that the information capacity of the resulting channel is 23 kb/s. This capacity is more than sufficient to implement the network management techniques in DS-3 networks and has the advantage of complete transparency to the existing payloads and to existing or new equipment not intended to process such signaling channels.>

The authors have designed and characterized a single-error-correcting (SEC), double-error-detecting (DED) code applicable to the STS-1 SONET format. They show that if two of the presently unallocated bytes in the path overhead field of STS-1 are assigned for error-correction coding (ECC), a (6208, 6195) shortened extended Hamming code can be implemented using as few as 660 gates plus a 1-kbyte RAM IC, achieving (O8.6*10/sup -3/ P/sub 2//sup 2/) BER reduction with 139 mu s of signal delay. The authors explain how the existing BIP-8 error-monitoring byte of the STS-1 format could be integrated with the proposed ECC so that a net allocation of only one new STS-1 overhead byte is required for both error monitoring and error correction. The implementation method is such that all path, line, and section overhead functions in SONET can be performed at intermediate sites without requiring ECC decoding. The authors consider application alternatives and describe the forward-error-correction (FEC) circuit design and trial results. System issues are covered, including network delay, effects of error extension on BER, addition of double-error detection, performance monitoring, and options for intelligent network control and management of FEC functions. Codes related to their path-level design that are applicable to a number of other strategies for applying FEC in SONET are presented.>

A technique for precise synchronization of the time-of-day clocks in networks of digital cross-connect systems (DCSs) is described. This method is intended to enhance the performance of reconfigurable transport networks and is specifically devised to exploit the fine time resolution of the carrier signals to which a DCS has direct access. The resulting scheme is a master-slave, multisite, implicitly delay compensated, nonhierarchical time-transfer method with a theoretical precision of one bit time at the carrier rate. In practice, precision is limited by transmission span delay asymmetries but residual time errors of under 1 mu s are predicted. The method is intended for n/n space-switching DCS, but other DCS properties can be accommodated. Requirements for DCS equipment design are given, including a generic circuit module for DCS hardware support of the time transfer function. The proposed method applies to DS-3 networks or synchronous optical networks and requires no change in the standards. Measurement or improved estimation of characteristic span delay asymmetries is recommended to refine the preliminary performance estimate.>