A fault recovery system that is fast and reliable is essential to today's networks, as it can be used to minimize the impact of the fault on the operation of the network and the services it provides. This paper proposes a methodology for performing automatic protection switching (APS) in optical networks with arbitrary mesh topologies in order to protect the network from fiber link failures. All fiber links interconnecting the optical switches are assumed to be bidirectional. In the scenario considered, the layout of the protection fibers and the setup of the protection switches is implemented in nonreal time, during the setup of the network. When a fiber link fails, the connections that use that link are automatically restored and their signals are routed to their original destination using the protection fibers and protection switches. The protection process proposed is fast, distributed, and autonomous. It restores the network in real time, without relying on a central manager or a centralized database. It is also independent of the topology and the connection state of the network at the time of the failure.

Dynamic routing of point-to-point connections in a waveband selective linear lightwave network is addressed. Linear lightwave networks are all optical networks in which only linear operations are performed on signals in a waveband selective manner. Special constraints arise because of the linearity in the linear lightwave network. The overall problem of finding a path satisfying all the routing constraints for point-to-point connections is shown to be very complex. Owing to the complexity, the overall routing problem is decomposed into several subproblems. In particular, given a request for a point-to-point connection a waveband is first chosen for the call. Two heuristics, MAXBAND which allocates the most used band to a call and another MINBAND (least used band) are studied. Then, the problem of routing in a given waveband is further divided into smaller subproblems of finding a path in the waveband, checking for feasibility of the path in the chosen waveband and channel allocation (within the waveband). For finding paths in a waveband, K-SP, BLOW-UP and MIN-INT algorithms are proposed. A recursive algorithm checks for feasibility of the path on the waveband. Two channel allocation schemes (within a single waveband) MIN and MAX are presented. Simulations show that using MAXBAND (waveband), MIN-INT (path on waveband) and MIN (channel within waveband) policies resulted in the best performance (least blocking).>

Dynamic routing algorithms are proposed for setting up multicast connections in a linear lightwave network (LLN). The problem of finding a physical path for the multicast connection so as to satisfy all the constraints in the LLN is shown to be NP-complete, and a heuristic approach is presented. An algorithm is presented that decomposes the LLN into edge disjoint trees with at least one spanning tree. A multicast call is allocated a physical path on one of the trees, using the smallest component tree (SCT) or the minimum interference tree (MIT) criterion. Finally, the call is allocated the least used channel from among channels that can be allocated to it. The best performance (low blocking probability) is obtained when the LLN is decomposed into many spanning trees, each of them having a small diameter. It is also found that the selection of trees for each call using the MIT criterion exhibits better performance than with the SCT criterion.>

The output queues of an M*N packet switch are studied using a Markov-modulated flow model. The switching element is a central server which sequentially routes packets from the inputs to the outputs. The focus is on systems in which the server speed is such that the bulk of the queuing takes place in the output queues. The conventional point process approach neglects the impact of switching and transmission time. An attempt is made to account for these finite system speeds by using a Markov-modulated continuous flow to approximate the arrival process to an output queue. This model captures the dependency between arrivals at different outputs and reflects the fact that packet arrivals and departures are not instantaneous. The output queue content distribution is obtained, for both infinite and finite buffer systems, from the spectral expansion of the solution of a system of differential equations. Numerical examples and comparisons with the results of an M/M/1 approximation are presented.>

Routing algorithms are proposed for setting up calls on a circuit-switched basis in linear lightwave networks (LLN), i.e., networks composed only of linear components, including controllable power combiners and dividers, and possibly linear (non-regenerative) optical amplifiers. The overall problem is decomposed into three subproblems: (1) physical path allocation, (2) checking for violations of the special optical constraints on the allocated physical path, and (3) channel assignment. Only point to point connections are considered. The physical path allocation technique uses the K-shortest path algorithm and tries to minimize the number of sources potentially interfering with each other, as a result of the incoming call. A channel assignment heuristic that tends to spread out calls evenly among the available channels works better than one that tries to maximize channel reuse.>

A general model is presented to study the performance of a family of space-domain packet switches, implementing both input and output queuing and varying degrees of speedup. Based on this model, the impact of the speedup factor on the switch performance is analyzed. In particular, the maximum switch throughput, and the average system delay for any given degree of speedup are obtained. The results demonstrate that the switch can achieve 99% throughput with a modest speedup factor of four. Packet blocking probability for systems with finite buffers can also be derived from this model, and the impact of buffer allocation on blocking probability is investigated. Given a fixed buffer budget, this analysis obtains an optimal placement of buffers among input and output ports to minimize the blocking probability. The model is also extended to cover a nonhomogeneous system, where traffic intensity at each input varies and destination distribution is not uniform. Using this model, the effect of traffic imbalance on the maximum switch throughput is studied. It is seen that input imbalance has a more adverse effect on throughput than output imbalance.>

A preliminary generic architecture is proposed for a packet voice messaging system (PVMS) which provides 'answering machine' service in a packet-switched environment. Its performance is considered in light of constraints imposed by the required quality of stored speech. A critical element in determining this quality is overflow in the PVMS packet buffer, which buffers packets of voice samples delivered to the PVMS for storage. A two-dimensional Markov chain analysis of the buffer occupancy of the PVMS is developed. Mean values and distributions of buffer occupancy are derived and validated against simulation. From these distributions, the probability of packet loss due to buffer overflow can be estimated, and the buffer can be sized to restrict overflow to an acceptably low level. In addition, the disk block size can be chosen to balance the tradeoff between the packet buffer size and wasted disk space.>

A study is made of the output queues of an M*N packet switch using a Markov-modulated flow model. The switching element is a central server which sequentially routes packets from the inputs to the outputs. The authors focus on systems where the server speed is such that the bulk of the queueing takes place in the output queues. For such systems, accurate sizing of the output buffers is an important design issue and requires a correct characterization of the arrival processes to the output buffers. The conventional point process approach neglects the impact of switching and transmission time. An attempt is made to account for these finite system speeds by using a Markov-modulated continuous flow to approximate the arrival process to an output queue. This model captures the dependency between arrivals at different outputs and reflects the fact that packet arrivals and departures are not instantaneous. The output queue content distribution is obtained, for both infinite and finite buffer systems, from the spectral expansion of the solution of a system of differential equations. Numerical examples and comparisons with the results of an M/M/1 approximation are presented.>

In order to reduce the time delays as well as multiplexer memory requirements in packet voice systems, a family of congestion control schemes is proposed. They are all based on the selective discarding of packets whose loss will produce the least degradation in quality of the reconstructed voice signal. A mathematical model of the system is analyzed and queue length distributions are derived. These are used to compute performance measures, including mean waiting time and fractional packet loss. Performance curves for some typical systems are presented, and it is shown that the control procedures can achieve significant improvement over uncontrolled systems, reducing the mean waiting time and total packet loss (at transmitting and receiving ends). Congestion control with a resume level is also analyzed, showing that without increasing the fractional packet loss, the mean and variance of the queue can be reduced by selecting an appropriate resume level. The performance improvements are confirmed by the results of some informal subjective testing.>

A study is made of statistical multiplexing of voice packets from a number of packetized voice sources onto a single channel. Each source alternates between talkspurt (active period) and silence, and packets are generated during active periods only. The packets are buffered (in a finite size buffer) when transmission capacity is not available. An embedded Markov chain model is adopted to analyze the system and a numerical technique is presented to compute system performance. Simulation results validate the analysis.>

Intermodulation (IM) effects were recently observed in communications satellites where the source of nonlinearity was traced back to passive and normally linear components. This phenomenon is sometimes called passive intermodulation (PIM) and can cause serious interference to the ultrasensitive receiver on board the spacecraft. One interesting and important aspect of the PIM study is to find the order and type of IM products causing interference in an arbitrary satellite receive band. It is shown that the problem can be reduced by the use of number theory to a Diophantine optimization problem. Two types of tree searches are formulated and proposed as viable approaches. Some additional bounds for the equal-spacing case and an iterative technique for the unequal-spacing case are described. Finally, we show, by means of an example, that the proposed techniques offer a practical method of solving the order and type prediction problem.

An overview is provided in this paper of the routing procedures used in a number of operating networks, as well as in two commercial network architectures. The networks include TYMNET, ARPANET, and TRANSPAC. The network architectures discussed are the IBM SNA and the DEC DNA. The routing algorithms all tend to fall in the shortest path class. In the introductory sections, routing procedures in general are discussed, with specialization to shortest path algorithms. Two shortest path algorithms, one appropriate for centralized computation, the other for distributed computation, are described. These algorithms, in somewhat modified form, provide the basis for the algorithms actually used in the networks discussed.

Various adaptive algorithms have been proposed for routing, flow and congestion control in packet-switched computer communication networks. In most of them, information on queue lengths, or equivalently, time delays, at various points in the network is required for proper adaptation. Since up-to-date information is not always available, these quantities must be estimated based on prior information. This paper presents approximations for the dynamic behavior of theM/M/1queue which is used to yield the desired estimates of queue lengths. Based on the assumption of finite (but arbitrarily large) storage, a closed form expression for the evolution in time of the queue length distribution is obtained. From this expression various approximations for estimated queue length are extracted. A simple expression for the "relaxation time" of the queue is also deduced as a function of utilization factor and service time. The approximations are applied to a simple adaptive routing example in which packets are routed along the transmission path having the shortest estimated queue, based on delayed information.

An important problem in packet-switched communication networks is the optimal assignment of routes to the message packets. An optimal routing assignment is one which chooses network paths for the packets in a way that minimizes some cost function, typically average message delay. A class of optimal routing algorithms is described which utilize a type of iterative computation known as relaxation. Computation is decentralized in the sense that each node computes its routing strategy using only information supplied from adjacent nodes. Being iterative, the algorithms are inherently adaptive. The routing computation is based conceptually on an electrical network analog for the optimization problem. We show that a simple, convergent relaxation procedure can be used to "solve" the analog network, thereby yielding the optimal routing strategy. A simple example is presented to illustrate the method. In general, the computational load compares favorably with other (centralized) methods, although further work is needed to obtain quantitive comparisons in specific cases.

In this paper the quantum nature of electromagnetic radiation is used as a basis for a mathematical model of a continuous channel. It is shown that this "photon channel" model leads to more realistic conclusions regarding information transmission. Among the results obtained are: 1) the maximum entropy for a narrow-band source under an average power limitation, 2) the frequency distribution (Bose-Einstein) for a wide-band power-limited source, 3) the transmission rate through a Poisson channel with additive Poisson noise.