Availability in connection-oriented service in networks has traditionally been all-or-nothing, i.e., when a failure occurs, a connection either is unprotected or fully protected. The differences in availability and cost between these two extremes can be quite high. A general framework for service availability will be presented that fills the gap. It is shown how network resources and cost are related to service parameters of the framework for networks that are bandwidth-efficient. In addition, a simple revenue model is presented and characterized, revealing when nontraditional service agreements may be attractive.

New protection schemes for video on demand (VOD) in a DWDM ring network are proposed that employ information per customer. Unlike prior schemes that rely on fixed priorities, the proposed scheme varies the priority to ensure the system best meets customer expected downtime, thereby ensuring revenues are maximized. The information used to determine current priorities includesfailure and revenue statistics. Failure statistics is the number of VOD service interruptions a customer experiences, and revenue statistics is the rate that revenues are generated by a customer. To evaluate the schemes a simple model of traffic and customer behavior is used. They are evaluated over two network resource provisioning scenarios. There are cases when the lost revenue can be reduced from about 20% to zero by using failure and revenue statistics.

Consider a website containing a collection of webpages with data such as in Yahoo or the Open Directory project. Each page is associated with a weight representing the frequency with which that page is accessed by users. In the tree hierarchy representation, accessing each page requires the user to travel along the path leading to it from the root. By enhancing the index tree with additional edges (hotlinks) one may reduce the access cost of the system. In other words, the hotlinks reduce the expected number of steps needed to reach a leaf page from the tree root, assuming that the user knows which hotlinks to take. The hotlink enhancement problem involves finding a set of hotlinks minimizing this cost. This article proposes the first exact algorithm for the hotlink enhancement problem. This algorithm runs in polynomial time for trees with logarithmic depth. Experiments conducted with real data show that significant improvement in the expected number of accesses per search can be achieved in websites using this algorithm. These experiments also suggest that the simple and much faster heuristic proposed previously by Czyzowicz et al. [2003] creates hotlinks that are nearly optimal in the time savings they provide to the user. The version of the hotlink enhancement problem in which the weight distribution on the leaves is unknown is discussed as well. We present a polynomial-time algorithm that is optimal for any tree for any depth.

A protection scheme is proposed that can be applied to video distribution networks. Instead of fully protecting affected High Definition TV connections it provides reduced bandwidth that suffices for Standard Definition TV. Two versions of this scheme are studied: when working and protection bandwidth are separate, and when working bandwidth may be "victimized" (interrupted). An analysis is given to determine when such a scheme is economical.

We introduce a probabilistic framework, based on service risk mitigation and disruption management, for the problem of capacity protection in optical networks. This contrasts the established deterministic approach of designing the protection network to guarantee no service disruption for up to M failures. We present the novel problem formulation and establish a framework for optimal network design in this extended abstract, while leaving the detailed optimization results and algorithms for the full paper (N. Bambos et al., 2003).

This paper looks at several aspects of optical layer protection techniques from an implementation perspective. We discuss the factors that affect the complexity of optical protection schemes, such as supporting mesh instead of ring protection, handling low-priority traffic, and dealing with multiple types of failures. The paper also looks at how the client layer interacts with the optical layer with respect to protection, in terms of how client connections are mapped into the optical layer, and how protection schemes in both layers can work together in efficient ways. Finally, we describe several interesting optical protection implementations, focusing on the ones that are different from conventional SONET-like implementations.

The failure of a single optical link or node in a wavelength division multiplexing (WDM) network may cause the simultaneous failure of several optical channels. In some cases, this simultaneity may make it impossible for the higher level (SONET or IP) to restore service. This occurs when the higher level is not aware of the internal details of network design at the WDM level. We call this phenomenon "failure propagation." We analyze three types of failure propagation, called "bottleneck," "connectivity," and "multiple groups." Then we present a solution based on the definition of appropriate requirements at network design and a WDM channel placement algorithm, protection interoperability for WDM (PIW). Our method does not require the higher level to be aware of WDM internals, but still avoids the three types of failure propagation mentioned above. We finally show the result on various network examples.

We provide network designs for optical add-drop wavelength-division-multiplexed (OADM) rings that minimize overall network cost, rather than just the number of wavelengths needed. The network cost includes the cost of the transceivers required at the nodes as well as the number of wavelengths. The transceiver cost includes the cost of terminating equipment as well as higher-layer electronic processing equipment, which in practice can dominate over the cost of the number of wavelengths in the network. The networks support dynamic (i.e., time-varying) traffic streams that are at lower rates (e.g., OC-3, 155 Mb/s) than the lightpath capacities (e.g., OC-48, 2.5 Gb/s). A simple OADM ring is the point-to-point ring, where traffic is transported on WDM links optically, but switched through nodes electronically. Although the network is efficient in using link bandwidth, it has high electronic and opto-electronic processing costs. Two OADM ring networks are given that have similar performance but are less expensive. Two other OADM ring networks are considered that are nonblocking, where one has a wide-sense nonblocking property and the other has a rearrangeably nonblocking property. All the networks are compared using the cost criteria of number of wavelengths and number of transceivers.

This paper considers grooming of low speed traffic into high speed lightpaths in a WDM based optical ring with a primary goal of reducing the cost of the entire system, which is dominated by the cost of the SONET transmission equipment connected to the optical ring. The paper attempts to enumerate the architectural options provided by SONET to arrive at a cost-effective solution, including unidirectional path-switched rings (UPSR) and bidirectional line-switched rings (BLSR), use of back-to-back connections between SONET ADMs to reduce the overall cost, and use of different ring speeds (OC-48 and OC-12). To demonstrate each of the architectures, a uniform traffic is considered and its grooming and resulting SONET architecture demonstrated. The paper deviates from earlier approaches which break the problem into two steps: traffic grooming and assignment of lightpaths to rings, in that it looks at the problem as a whole and tries to solve it in a single step. The paper also considers the characteristics of SONET UPSR and BLSR rings and how these affect the grooming. The paper derives lower and upper bounds to these problems for uniform traffic and shows how these improve on known results.

This paper proposes algorithms for allocating wavelengths to connections (lightpaths) in optical wavelength division multiplexed networks, predominantly for ring topologies. A worst-case model is considered, where no blocking of lightpaths is allowed, and there are no assumptions made on the traffic arrival and holding times. The traffic is characterized only by its load L, which is the maximum number of lightpaths that can be present on any link, assuming no blocking. A dynamic traffic model is considered where requests to set up lightpaths arrive over time and, must be accommodated without rerouting existing lightpaths, and lightpaths may be terminated over time as well. For networks without wavelength conversion, we show that at least 0.5Llog/sub 2/N wavelengths are required by any dynamic algorithm for rings of N nodes and present an algorithm that uses at most Llog/sub 2/N+L wavelengths for rings and 2(L-1)log/sub 2/N for trees. We also study the worst-case behavior of the well-known first-fit algorithm, and show that it requires at most 2.52Llog/sub 2/N+5L wavelengths (small variants of these constants are proven as well). When limited wavelength conversion is allowed, we first show how to use expanders to insure no blocking in arbitrary topologies. Then, we present conversion patterns for rings with conversion degree d=2, which require Llog/sub 2/L+4L or 2Llog/sub 2/log/sub 2/L+4L wavelengths, thereby eliminating the dependence (that exists without wavelength conversion) between the number of wavelengths and N. We also consider different traffic models where lightpath setup requests arrive over time, but once set up, lightpaths are never taken down. For this model, the number of wavelengths needed is shown to be only max{0,L-d}+L for a conversion degree of d.

Discusses wavelength assignment for lightpaths. We study WDM networks in the form of rings and higher level networks as SONET/SDH self-healing rings. This view changes the goal of wavelength assignment (WLA) vs. previous work on the subject in a number of aspects. First, a pair of SONET add/drop multiplexers (ADMs) terminates each lightpath. These ADMs also terminate adjacent lightpaths to form rings, implying that the WLA has to support this type of sharing. Second, following Gerstal et al. (1998), we argue that the first-order optimization goal should be to minimize the overall network cost which is dominated by the number of required ADMs and not the number of wavelengths. These two minimization problems are intrinsically different, and there exist cases where the two minima cannot be simultaneously achieved. We derive a simple lower bound to the number of ADMs and show that this lower bound is not always achievable. Adding wavelength converters to the system does not improve the cost but splitting a lightpath and handling each part separately may reduce the total number of ADMs. We develop two heuristics to minimize the number of ADMs: cut-first, and assign-first. Both heuristics attempt to use the smallest number of ADMs possible. Cut-first always uses the minimum number of wavelengths, but may use more ADMs than necessary. However, the number of extra ADMs is proven to be bounded by the number of supported wavelengths and typically much less. We show instances where cut-first performs better than assign-first and vice versa. Finally, we present a set of transformations that take any WLA and improve its cost.

We provide network designs for optical wavelength division multiplexed (OWDM) rings that minimize overall network cost, rather than just the number of wavelengths needed. The network cost includes the cost of the transceivers required at the nodes as well as the number of wavelengths. The transceiver cost includes the cost of terminating equipment as well as higher-layer electronic processing equipment, and in practice, can dominate over the cost of the number of wavelengths in the network. The networks support dynamic (time varying) traffic streams that are at lower rates (e.g., OC-3, 155 Mb/s) than the lightpath capacities (e.g., OC-48, 2.5 Gb/s). A simple OWDM ring is the point-to-point ring, where traffic is transported on WDM links optically, but switched through nodes electronically. Although the network is efficient in using link bandwidth, it has high electronic and opto-electronic processing costs. Two OWDM ring networks are given that have similar performance but are less expensive. Two other OWDM ring networks are considered that are nonblocking, where one has a wide sense nonblocking property and the other has a rearrangeably nonblocking property. All the networks are compared using the cost criteria of number of wavelengths and number of transceivers.

This paper presents methods for recovering from channel failures, link failures, and node failures in wavelength-division multiplexed (WDM) point-to-point links and ring networks with limited wavelength conversion/switching capabilities at the nodes. Different recovery schemes are presented to handle each type of failure. Each scheme is evaluated based on the network hardware configuration required to support it and the performance and management overheads associated with fault recovery. Although similar recovery techniques have been used in conventional networks such as SONET, the constraints due to limited wavelength conversion require new and more complex solutions.

We present a new network design problem that is applicable for designing virtual paths (VPs) in an asynchronous transfer mode (ATM) network to efficiently support client/server applications. We present several alternatives for the solution, compare their properties, and focus on a novel "greedy" solution, which we prove to optimize certain important criteria (namely, the network overhead for a request/response and the utilization of bandwidth and routing table resources). We also present simulation results that demonstrate the performance and scalability of our solution. In addition, we propose a new efficient bandwidth allocation scheme which is tailored for client/server applications over ATM networks.

We focus on wavelength allocation schemes for all-optical WDM ring networks. For an N node network we characterize the traffic by its load L/sub max/ (the maximum number of lightpaths that share a link) and do not assume knowledge of the arrival/departure processes. We prove that shortest path routing produces a routing which has at most twice the load of the optimal solution. We show that at least 0.5 L/sub max/ log/sub 2/N+L/sub max/ wavelengths are required by any algorithm in the worst case, and develop an algorithm which requires up to 3 L/sub max/ log/sub 2/N wavelengths. For the case when the load is high and blocking is necessary we present an improved algorithm.

This paper presents methods for recovering from channel failures, link failures, and node failures in wavelength-division multiplexed (WDM) point-to-point links and ring networks, with limited wavelength conversion/switching capabilities at the nodes. Different recovery schemes are presented to handle each type of failure. Each scheme is evaluated based on the network hardware configuration required to support it, and the performance and management overheads associated with fault-recovery.

We present a new network design problem that arises when designing virtual paths in an ATM network to properly support client/server applications. We present several alternatives for the solution, discuss their pros and cons, and focus on a novel "greedy" solution, which we prove to optimize certain important criteria (namely, the network overhead for a request/response and the utilization of bandwidth and routing table resources). In addition, we propose a new, efficient bandwidth allocation scheme which is tailored for client/server applications over ATM networks. The results in this work imply the importance of ATM switches that switch both VPs and VCs.

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.

Discusses methods for adjusting the layout of virtual paths in an ATM network, to the dynamics of changes in the usage of the network by its end-users. The authors first present a centralized algorithm for finding a better layout for the current traffic pattern, and for applying the change in the network, and discuss its drawbacks. They then present a distributed algorithm that emulates the centralized algorithm with a much lower overhead, and enhanced durability to faults. They prove that both algorithms produce identical layouts, thus showing the superiority of the latter algorithm. Both algorithms base the changes in the network on a new rerouting protocol, which does not cause any losses in data, nor changes in the FIFO order of cells.

In th~paper we present a new model, within which we define a generrd routing problem (termed virtual path layout) that occurs in fast networks (ATM).In an effort to solve this general problem, we first define an intermediate problem, and prove it is NPcomplete.We then restrict some of the assumptions to yield a practical subproblem, for which we present a polynomial time greedy algorithm, that produces an optimal solution.Finally, we solve the general problem using the polynomially solvable subproblem as a building block.The results exhibit a tradeoff between the performance of a routing scheme and its resource utilization.

Abstract A new characterization of tree medians is presented: We show that a vertex m is a median of a tree T with n vertices iff there exists a partition of the vertex set into [n/2] disjoint pairs (excluding m when n is odd), such that all the paths connecting the two vertices in any of the pairs pass through m. We show that in this case the sum of the distances between these pairs of vertices is the largest possible among all such partitions, and we use this fact to discuss lower bounds on the message complexity of the distributed sorting problem. We show that, given a network of a tree topology, choosing a median and then routing all the information through it is the best possible strategy, in terms of worst‐case number of messages sent during any execution of any distributed sorting algorithm. We also discuss the implications for networks of a general topology and for the distributed ranking problem. © 1994 by John Wiley & Sons, Inc.