We consider protection switching in an IP over optical network. There is IP Fast Reroute Loop-free Alternates (IP FRR LFA) at the IP layer, and protection switching at the optical layer. Our network model assumes a completely connected IP network over an optical ring network that is required to protect a predetermined fraction of network bandwidth. This model leads to analytical formulas on network protection costs which we show are accurate. We also show that network cost is at or near zero when the network is required to protect at most 33% of traffic. A cost comparison to networks using MPLS Fast Reroute (MPLS FRR) further indicates that LFA is a feasible protection mechanism.

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.

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 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.

This paper proposes optical wavelength division multiplexed (WDM) networks with limited wavelength conversion that can efficiently support lightpaths (connections) between nodes. Each lightpath follows a route in a network and must be assigned a channel on each link along the route. The load /spl lambda//sub max/ of a set of lightpaths is the maximum over all links of the number of lightpaths that use the link. At least /spl lambda//sub max/ wavelengths will be needed to assign channels to the lightpaths. If the network has full wavelength conversion capabilities, then /spl lambda//sub max/ wavelengths are sufficient to perform the channel assignment. Ring networks with fixed wavelength conversion capability within the nodes are proposed that can support all lightpath sets with load /spl lambda//sub max/ at most W-1, where W is the number of wavelengths in each link. Ring networks with a small additional amount of wavelength conversion capability within the nodes are also proposed that allow the support of any set of lightpaths with load /spl lambda//sub max/ at most W. A star network is also proposed with fixed wavelength conversion capability at its hub node that can support all lightpath sets with load /spl lambda//sub max/ at most W. These results are extended to tree networks and networks with arbitrary topologies. This provides evidence that significant improvements in traffic-carrying capacity can be obtained in WDM networks by providing very limited wavelength conversion capability within the network.

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.

This paper proposes optical wavelength division multiplexed (WDM) networks with limited wavelength conversion that can efficiently support lightpaths (connections) between nodes. Each lightpath follows a route in the network and must be assigned a channel along each link in its route. The load /spl lambda//sub max/ of a set of lightpath requests is the maximum over all links of the number of lightpaths that use the link. At least /spl lambda//sub max/ wavelengths will be needed to assign channels to the lightpaths. If the network has full wavelength conversion capabilities then /spl lambda//sub max/ wavelengths are sufficient to perform the channel assignment. We propose ring networks with a fixed wavelength conversion capability within the nodes that can support all lightpath request sets with load /spl lambda//sub max/ at most W-1, where W is the number of wavelengths in each link. We also propose ring networks with selective pairwise wavelength conversion capability within the nodes that can support all lightpath request sets with load /spl lambda//sub max/ at most W. We also propose a star network with fixed wavelength conversion capability at its hub node that can support all lightpath request sets with load /spl lambda//sub max/ at most W. We extend this result to tree networks and networks with arbitrary topologies. These results show that significant improvements in traffic-carrying capacity can be obtained in WDM network by providing a very limited wavelength conversion capability within the network.

This paper presents a fair network access scheme called MultiSAT which can be seen as a generalization of two access schemes proposed by Ofek and Yung (see IEEE/ACM Trans. Networking, vol.3, no.4, p.169-80, 1995) and Ngai and Seitz (1989). An upper bound on the delay before a node can inject a packet into the network is given which is valid when packet routes have no cyclic dependencies, backpressure flow control is used, and the processing and propagation delays are negligible. Upper bounds on packet injection delay are also given for ring networks employing shortest path routing for the case of negligible processing and propagation delays, and for the case of the MetaRing network when link propagation delays are significant.

A routing scheme is presented for a class of mesh topologies, which include tori and variations of tori. The variations model torus networks that have undergone topological perturbations. Such perturbations are due to addition and deletion of nodes, which may occur because of network failure and incremental network growth. Since the routing scheme is operable over a class of topologies, where addition or deletion of a node keeps a topology within the class, it is robust to incremental changes in network topology. In addition, it requires only minimal space and processing at the network nodes, which makes it suitable for high-speed implementation. Its efficiency, in terms of path length taken by packets, is demonstrated through both computer simulation and mathematical analysis. The analysis uses a random topology model to show that for “typical” topologies the scheme routes packets along near-optimum paths. © 1996 John Wiley & Sons, Inc.

The MetaNet is a proposed high speed LAN/MAN architecture with simple protocols and operates on arbitrary network topologies. Since it operates on arbitrary topologies, it has the potential for better aggregate throughput than networks such as FDDI and DQDB that are ring and bus networks, respectively. This paper presents mathematical and numerical evidence that better throughput is possible for MetaNet on the well known grid and hypercube topologies. Simulation results are also presented to illustrate the importance of the choice of the embedded ring on MetaNet performance.>

Considers a broadcast-and-select, wavelength division multiplexed (WDM), optical communication network that is packet switched and time slotted. The amount of time it takes transmitters and receivers to tune from one wavelength to another is assumed to be T slots. The authors consider all-to-all transmission schedules, which are defined to be ones that schedule a packet transmission between each input-output pair. They present upper and lower bounds for the minimum length of such schedules. In particular, if each of N inputs has a tunable transmitter and each of N outputs has a tunable receiver then the minimum length is between (N+o(N))(/spl radic/T+1) and ((N+o(N))/spl radic/T. This provides some insight into the relationship between packet delay and T. The authors also consider schedules that do not allow packet transmissions while a transmitter or receiver is tuning from one wavelength to another.>

The irregular torus, a class of topologies proposed for metropolitan area networks, is torus-like, and thus more reliable than the bus and ring topologies. There is a routing algorithm for the topologies which is space and time efficient so that it is suitable for high-speed implementations. In addition, it is robust to topology perturbations due to network growth and node/link failure. A buffer management is proposed to prevent store-and-forward deadlock for routing in the irregular torus, and the throughput of a typical irregular torus network is analyzed. Store-and-forward deadlock is avoided by a buffer management whose storage requirement and control complexity at a node are both constant with the size of a network. The throughput of a typical irregular torus network is shown to be within a constant factor of that of a square torus. Hence for a large number of nodes, it is much higher than the throughput of a bus, ring or tree.>

The go-back- infinity protocol is studied under a two-state Markov chain packet-loss model, where the delay for packet acknowledgements is random. Expressions are presented for the z transform, mean, and variance of the time tau taken to successfully transmit N packets. In addition, the authors discuss how the probability distribution of the delay for packet acknowledgements can affect E mod tau mod .>

The authors consider linear lightwave networks with a single waveband that have N inputs, each with a transmitter, and N outputs, each with a receiver, interconnected by optical links, broadcast stars, and wavelength-independent 2*2 switches. The transmitters and receivers can tune to C different wavelengths. The authors describe a rearrangeably nonblocking network that is a modification of the Benes network and uses transmitters that are fixed tuned and switches with two states. The network uses (1+o(1))N/log/sub 2/(N/C) switches, which is shown to be nearly the minimum number. It is also shown that, if C=o(log N), then a rearrangeably nonblocking network requires (1+o(1))Nlog/sub 2/N switches even if the switches have more than two states.>

A communication switching system is considered where nodes communicate through transmitters and receivers that have the same bandwidth. Communication constraints are imposed so that the number of active transmitters or receivers on designated subsets of nodes is bounded by prespecified values. The constraints are assumed to have a hierarchical structure. An algorithm is given that produces minimal length schedules of data transfers through the system if transmission preemption is allowed. A variation of the switching system when nodes communicate through transceivers is also considered, and accompanying scheduling algorithms are presented. Applications to transmission scheduling in packet radio networks are discussed.>

A study is made of the effect of correlated packet losses for some simple automatic repeat request (ARQ) protocols: go-back- infinity , and Blast. The packet losses are modeled by a two state Markov chain and it is assumed that the round trip delay is random. Expressions are derived for the z-transform and the first and second moments of the time ( tau ), taken to successfully transmit N packets for go-back- infinity and variations of the Blast protocol. For go-back- infinity , bounds are derived for E( tau ), and it is shown that for a fixed mean round trip delay, E( tau ) is minimized when the distribution of the round trip delay is such that its variance is minimized. Some of the protocols investigated show a significant improvement in performance when packet losses occur in bursts. The authors propose and analyze a variation of the Blast protocol which seems particularly suited to bursty packet loss situations.>

Simple strategies are analyzed for the layout of networks of interconnected buses. The networks considered have topologies of a square grid and a mesh of cubes of buses. These regular topologies have properties that are desirable for very large high-speed networks. The objective of the design strategies is to minimize the maximum bus length. To demonstrate the effectiveness of the algorithms, it is shown that if there are a large number of communication nodes placed randomly on the unit square then the strategies produce, with high probability, layouts that have maximum bus lengths of at most a constant factor of the minimum.>

The random, heuristic search algorithm called simulated annealing is considered for the problem of finding the maximum cardinality matching in a graph. It is shown that neither a basic form of the algorithm, nor any other algorithm in a fairly large related class of algorithms, can find maximum cardinality matchings such that the average time required grows as a polynomial in the number of nodes of the graph. In contrast, it is also shown for arbitrary graphs that a degenerate form of the basic annealing algorithm (obtained by letting “temperature” be a suitably chosen constant) produces matchings with nearly maximum cardinality in polynomial average time.

Two polynomial-time algorithms are given for scheduling conversations in a spread spectrum radio network. The constraint on conversations is that each station can converse with only one other station at a time. The first algorithm is strongly polynomial and finds a schedule of minimum length that allows each pair of neighboring stations to converse directly for a prescribed length of time. The second algorithm is designed for the situation in which messages must be relayed multiple hops. The algorithm produces, in polynomial time, a routing vector and compatible link schedule that jointly meet a prespecified end-to-end demand, so that the schedule has the smallest possible length.>

In this paper, we present iterative methods for finding optimal state-dependent routing strategies in single commodity networks. The key to our method is to show that there exists a family of optimization problems with convex cost and linear constraints that have solutions that can be converted into an optimal routing strategy by way of a flow relaxation transformation. These problems, when solved by certain iterative algorithms, lead to different convergence rates. In particular, one of the problems has quadratic cost. To solve one of these optimization problems, we use an iterative projected descent direction algorithm due to Bertsekas. We present an alternative to the Armijo-like step size rule of the algorithm, which we believe is more robust. Also included are Newton-like descent directions that take a reasonable amount of time to compute. Finally, some results of our computer experiments are summarized.