We present an analytical technique of very low complexity, using the inclusion-exclusion principle of combinatorics, for the performance evaluation of all-optical, wavelength-division multiplexed networks with no wavelength conversion. The technique is a generalized reduced-load approximation scheme which is applicable to arbitrary topologies and traffic patterns. One of the main issues in computing blocking probabilities in all-optical networks is the significant link load correlation introduced by the wavelength continuity constraint. One of the models we propose takes this into account and gives good results even under conditions with high link load correlation. Through numerous experiments we show that our models can be used to obtain fast and accurate estimates of blocking probabilities in all-optical networks and scale well with the path length and capacity of the network. We also extend one of our models to take into account alternate routing, in the form of Fixed Alternate Routing and Least Loaded Routing.

We consider the problem of routing and dimensioning in a large optical network where traffic is growing over time. A model of traffic in optical network lightpaths is presented. Lightpaths arrive randomly according to a time-varying Poisson process and hold for a random time with a general distribution. We propose a wavelength division multiplexing network that requires no capacity upgrading in a given time period T while allowing the operator to accommodate all the lightpath requests. We obtain an exact solution of the routing and dimensioning problem under an asymptotic regime where both the capacities and the arrival rates are large. For moderate link capacities, we propose a method to dimension the links so that the first lightpath request rejection occurs, with high probability, after the specified time T. This involves the computation of capacity-exhaustion probability $the probability that at least one lightpath request is rejected in the time period (0, T) due to lack of bandwidth/capacity on some link. Computation of the exact capacity-exhaustion probability is possible for a few specific holding time distributions (e.g., exponential). Since this requires large computing resources, it is feasible only for small networks. We propose a method to estimate the capacity-exhaustion probabilities for a large optical network with general holding time distribution based on the results of an asymptotic analysis. We show that this method has a low computational complexity and is quite accurate in the desired range of low capacity-exhaustion probabilities.

In this paper, we consider the problem of dimensioning a large optical wavelength-division multiplexing (WDM) network assuming the traffic is growing over time. Traffic between pairs of nodes is carried through lightpaths which are high-bandwidth end-to-end circuits, occupying a wavelength on each link of the path between two nodes. We are interested in dimensioning the WDM links so that the first lightpath request rejection will occur, with high probability, after a specified period of time T. Here we introduce the concept of capacity exhaustion probability - the probability that at least one lightpath request will be rejected in the time period (0,T) due to lack of bandwidth/capacity on some link. We propose a network dimensioning method based on a traffic growth model which eventually results in a nonlinear optimization problem with cost minimization as the objective and route capacity exhaustion probabilities as the constraints. Computation of exact capacity exhaustion probabilities requires large computing resources and is thus feasible only for small networks. We consider a reduced load approximation for estimating capacity exhaustion probabilities of a wavelength routed network with arbitrary topology and traffic patterns. We show that the estimates are quite accurate and converge to the correct values under a limiting regime in the desired range of low-capacity exhaustion probabilities.

We consider the problem of routing and dimensioning in a large optical network, assuming the traffic is growing over time. In optical networks, traffic is carried through lightpaths and we model the traffic as follows: lightpaths arrive randomly according to a time-varying Poisson process and hold for a random time with a general distribution. We are interested in dimensioning the links so that the first lightpath request rejection occurs, with high probability, after a specified period of time, T, and thus the network requires no capacity upgrading in that time period. We propose a solution based on the absorption probability - the probability that at least one lightpath request is rejected in the time interval (0, T). Computation of exact absorption probability is possible for a few specific holding time distributions (e.g., exponential) and it requires large computing resources. We propose a method which has low computational complexity to approximate the absorption probability for a general holding time distribution based on an asymptotic analysis and we show that it is quite accurate in the desired range of low absorption probabilities.

We introduce a traffic growth model for optical networks with time-varying traffic arrivals assuming the nodes are capable of full wavelength conversion. We propose a network dimensioning method based on the traffic growth model and it eventually results in a nonlinear optimization problem with cost minimization as the objective and route absorption probabilities as the constraints. The absorption probabilities can be obtained from transient analysis of a Markov chain. Computation of exact absorption probabilities requires huge computing resources and is thus feasible only for small networks. We consider a reduced load approximation for estimating absorption probabilities of a wavelength routed network with arbitrary topology and traffic patterns. We show that the approximation method performs very well for optical networks with long-lived lightpaths.

We present an integer linear program based algorithm and a K shortest path based heuristic algorithm for solving the routing and wavelength assignment problem in all optical networks with limited wavelength conversion. These algorithms are executed on a random mesh National Science Foundation Network (NSFNET). Their performances are compared.

We analyze the outage and capacity performance of an interference based admission control strategy in cellular CDMA systems. Most approaches to estimate the outage probability and the system capacity of CDMA systems in the literature do not take interference based admission control into account. In this paper, we present an analytical model to evaluate the outage probability and the capacity on the reverse link of cellular CDMA systems with interference based admission control. We make two main approximations in the outage analysis-one based on the central limit theorem (CLT) and the other based on the Chernoff bound (CB). We also obtain an improved approximation to the outage probability using Edgeworth expansion. It is shown that the considered admission control policy results in increased system capacity compared to that with no admission control, by about 30% for an outage probability of 0.01.

A network dimensioning method allocates appropriate capacities to the links based on the network topology and traffic requirements. We introduce the concept of absorption probability instead of blocking probability which is a more appropriate measure to express the grade of service of an optical network, in many cases. Absorption probability can be obtained from transient analysis of a Markov chain. Computation of exact absorption probabilities requires large computing resources and is thus feasible only for small networks. We present a method to approximate the absorption probability of a wavelength-routed network with arbitrary topology and traffic patterns assuming the nodes have full wavelength conversion capability. We show that the approximation method performs well especially in the desired range of absorption probabilities and it is computationally efficient.

Channel allocation algorithms for channelized cellular systems are discussed from a new perspective, viz., fairness of allocation. The concepts of relative and absolute fairness are introduced and discussed. It is shown that under certain reasonable assumptions, there exists an absolute (max-min) fair carried traffic intensity vector (a vector describing the traffic carried in the cells of the system). We also show that this vector is unique. We describe some properties of the max-min fair carried traffic intensity vector in an asymptotic limit where the traffic and the number of channels are scaled together. For each traffic pattern, we determine a fixed channel allocation which attains this max-min fair carried traffic intensity vector independent of the value of the offered traffic, in the same asymptotic limit. Finally, we discuss a tradeoff between being max-min fair and trying to maximize revenue. We conclude by discussing some possible extensions of our work.

This paper considers the problem of routing sessions with quality of service (QoS) requirements in a network under packet generalized processor sharing (PGPS) scheduling. PGPS is a non-preemptive scheduling policy that tracks GPS. The GPS policy operates by allocating a weight /spl phi//sub n//sup m/ for a session n whose traffic uses link m. These weights determine the rate at which the traffic from session n is served at link m and the rate in turn determines the end-to end delay of packets belonging to session n. As a deterministic and easily computable end-to-end delay bound is available for locally stable sessions, we consider the locally stable regime in this paper. Two separate problems are considered in this paper. The first problem deals with the practically important inverse procedure of specifying appropriate weights for sessions at each link on their paths, that satisfy predetermined delay bounds, when the set of sessions to be routed is given. Here we show that the fixed routing case can be formulated as a linear program (LP) and the adaptive routing case can be formulated as a mixed integer linear program (MILP). The second problem examines the performance of PGPS scheduling policy when providing per-session QoS guarantees. We measure the performance in terms of weighted carried traffic. We derive an upper bound on the weighted carried traffic for any heuristic algorithm for admission control that operates within the locally stable domain. This upper bound can be obtained by computing a linear program (LP). By simulating a simple heuristic algorithm for admission control, we show that this upper bound is reasonably tight. Hence our upper bound can be used as a metric against which the performance of different algorithms can be compared.

In this paper, we find bounds and approximations for the capacity of mobile cellular communication networks based on code division multiple access (CDMA). We develop efficient analytic techniques for capacity calculations of CDMA cellular networks. Each cell is modeled as an independent M/G//spl infin/ queue and traffic capacity assessed based on the maximum Erlang traffic that leads to acceptable link quality with high probability. Subsequently, approximations and bounds for the outage probability and hence traffic capacity are obtained using asymptotic expansions and large deviations theory. Numerical examples, considering uniform and normalized truncated Gaussian user density in the system are evaluated. The propagation model we consider takes care of distance and lognormal shadowing losses.

We consider the problem of constructing logical topologies over a wavelength-routed optical network with no wavelength changers. We present a general linear formulation which considers routing traffic demands, and routing and assigning wavelengths to lightpaths, as a combined optimization problem. The formulation also takes into account the maximum number of hops a lightpath is permitted to take, multiple logical links in the logical topology, multiple physical links in the physical topology, and symmetry/asymmetry restrictions in designing logical topologies. The objective is to minimize congestion. We show by examples how equality and inequality logical degree constraints have a bearing on congestion. We prove that, under certain conditions, having equality degree constraints with multiple edges allowed in the design of logical topologies does not affect congestion. This helps in reducing the dimensionality of the search space and hence speeds up the search for an optimal solution of the linear formulation. We solve the linear formulation for small examples and show the tradeoff between congestion, number of wavelengths available and the maximum number of hops a lightpath is allowed to take. For large networks, we solve the linear formulation by relaxing the integer constraints. We develop topology design algorithms for large networks based on rounding the solutions obtained by solving the relaxed problem. Since the whole problem is linearizable, the solution obtained by relaxation of the integer constraints yields a lower bound on congestion. This is useful in comparing the efficiency of our heuristic algorithms. Following Bienstock and Gunluk (1995), we introduce a cutting plane which helps in obtaining better lower bounds on congestion and also enables us to reduce the previously obtained upper bounds on congestion.

We present a new analytical technique, based on the inclusion-exclusion principle from combinatorial mathematics, for the analysis of all-optical networks with no wavelength conversion and random wavelength assignment. We use this technique to propose two models of low complexity for analysing networks with arbitrary topologies and traffic patterns. The first model improves the current technique by Birman (1996) in that the complexity of calculation is independent of hop-length and scales only with the capacity of the link as against that of Birman's method which grows exponentially with hop-length. We then propose a new heuristic to account for wavelength correlation and show that the second model is accurate even for sparse networks. Our technique can also be extended to analyse fixed alternate and least loaded routing.

In this paper we propose a method to calculate the average blocking probability in all-optical networks using limited-range wavelength conversion. Previous works have shown that there is a remarkable improvement in blocking probability while using limited-range wavelength conversion, but these analytical models were either for a path or for a mesh-torus network. Using a graph-theoretical approach, we extend Birman's (1996) model for no wavelength conversion and derive an analytical expression to compute the blocking probabilities in networks for fixed routing. The proposed model is applicable to any network topology. We consider the case where an incoming wavelength can be converted to d adjacent outgoing wavelengths on either side of the input wavelength, in addition to the input wavelength itself, where d is the degree of conversion. When d=0 and d=((C-1)/2), where C is the capacity of a link, the proposed model reduces to the model previously given for no wavelength conversion and the model previously given for full wavelength conversion respectively. Using this model we demonstrate that the performance improvement obtained by full wavelength conversion over no wavelength conversion can almost be achieved by using limited-range wavelength conversion with the degree of conversion, d, being only 1 or 2. In the example networks we considered, for blocking probabilities up to a few percent, the carried traffic with limited conversion degree d=2 was almost equal to the carried traffic for full wavelength conversion. Comparisons to simulations show that our analytical model is accurate for a variety of networks, for various values of the conversion degree (d=1,2,3), and hop length (1-4), and over a wide range of blocking probabilities (>0.0001). The method is also accurate in estimating the blocking probabilities on individual paths (and not just the average blocking probability in the network).

We propose a method to calculate the average blocking probability in all-optical networks using limited-range wavelength conversion. Previous works have shown that there is a remarkable improvement in blocking probability while using limited-range wavelength conversion but these analytical models were either for a path or for a mesh-torus network. Using a graph-theoretical approach, we extend Birman's model (see IEEE JSAC/JLT Special I on Optical Networks, vol.14, no.5, p.852-57, 1996) for no wavelength conversion and derive an analytical expression to compute the blocking probabilities in networks with limited-range wavelength conversion for fixed routing. The proposed analytical model is a generalization of Birman's model and is applicable to any network topology. We consider the case where an incoming wavelength can be converted to d adjacent outgoing wavelengths on either side of the input wavelength, in addition to the input wavelength itself, where d is the degree of conversion. Using this model we demonstrate that the performance improvement obtained by full wavelength conversion over no wavelength conversion can almost be achieved by using limited-wavelength conversion with the degree of conversion, d, being only 1 or 2. In a few example networks we considered, for blocking probabilities up to a few percent, the carried traffic with limited-conversion degree d=2 was almost equal to the carried traffic for full wavelength conversion. The results obtained show that significant improvements in blocking performance can be obtained by providing limited-range wavelength conversion of small degree within the network.

In a tiered cellular system the cells are split into two regions: the inner tier and the outer tier. These two regions can be treated as logically separate cells. Due to the smaller radii of the inner tier cells, a frequency plan with greater reuse can be employed for the inner tier cells than for the original (untiered) system, or the outer tier cells. This results in a net increase in the call carrying capacity of the system due to tiering. In this paper, we propose a method for the determination of the frequency plan for a tiered system while maintaining the specified call quality. The call quality is assumed to be specified in the form of a minimum carrier-to-interference ratio that is to be met at each base station, under the worst-case locations of the mobiles. Under these co-channel interference constraints, the cellular system can be modeled as a hypergraph. The frequency planning method involves generating the maximal independent sets (MISs) of this hypergraph and solving a linear program whose constraints are determined by these MISs. Moreover, these frequency plans can be shown to be optimal (have the greatest call carrying capacity) asymptotically, that is, when a very large number of frequencies are available. The method is applicable to systems with either omnidirectional or sectored antennas. However the number of MISs is significantly larger in the sectored case and thus we use only a fraction of them which may make the resulting frequency plans somewhat sub-optimal. The same remark holds for systems with a large number of cells. Nevertheless, in all cases, the frequency plans obey the specified co-channel interference restrictions. The other parameters which affect the performance gain due to tiering are the inner tier area and transmit power. In a specific example, we have evaluated the optimal inner tier area and transmit power and found that their optimization results in significant capacity gains.

Timing skew has been the major limitation for high-speed synchronous operation of a VLSI system. In this paper, a statistical timing model that accounts for both static and random timing skew is proposed. Based on this model, we analyze the timing rules of a synchronous VLSI system consisting of multiple pipelined stages, establish the yield of the system as a function of its device characteristics, and derive the relationship between the maximum throughput of such a system and its timing skew. The following timing schemes are evaluated: conventional pipelining, in which the transmitter cannot initiate the next cycle until the receiver has received the data and wave pipelining, in which the transmitter initiates the next cycle as soon as the current data has been sent out. The results show that the yield of a VLSI system using either of the pipelining schemes exhibits threshold behavior for Gaussian distributed static skew. Furthermore, the system throughput is shown to be very sensitive to the random skew.

In this paper we present a exact linear formulation (mixed integer linear program) for designing a logical topology with no wavelength changers. Since the objective of our linear formulation is minimizing the maximum offered load on any link, which is called congestion, the resulting logical topology reflects the traffic intensities between the nodes. Our linear formulation yields a logical topology and routing and wavelength assignment for the logical links. Previously (see IEEE Journal on Selected Areas in Communications, vol.40, no.1, p.840-51, 1996) the problem of logical topology design is considered but the number of wavelengths the fiber can support is not a constraint. In this paper we take into consideration the number of wavelengths the fiber supports, the hop length of a logical link, and show the trade-offs involved in minimizing congestion. Since the whole problem is linearizable the solution obtained by relaxation of the integer constraints yields a lower bound on the congestion. This can be used to compare the efficiency of heuristic algorithms. We solve the problem exactly for a small size network and for large size networks we develop some heuristic algorithms to obtain a feasible solution using the solution obtained by relaxing the integer constraints. We introduce a cutting plane which enables us to reduce the previously obtained upper bounds on congestion. Numerical results for a six node wide area network and the National Science Foundation Network (NSFNET) are presented for various cases.

Improved channel assignment algorithms for cellular networks were designed by modelling the interference constraints in terms of a hypergraph (Sarkar and Sivarajan). However these algorithms only considered cochannel reuse constraints. Receiver filter responses impose restrictions on simultaneous adjacent channel usage in the same cell or in neighbouring cells. An asymptotically tight upper bound for the traffic carried by the system in the presence of arbitrary cochannel and adjacent channel reuse constraints was developed in Deora (1995). However this bound is computationally intractable even for small systems like a regular hexagonal cellular system of 19 cells. We have obtained approximations to this bound using the optimal solutions for cochannel reuse constraints only, and a further graph theoretic approach. Our approximations are computationally much more efficient and have turned out to track very closely the exact performance bounds in most cases of interest. We also present some heuristics for designing fixed channel assignment algorithms with a minimum number of channels satisfying both cochannel and adjacent channel reuse constraints.

This paper addresses the problem of providing per-connection end-to-end delay guarantees in a high-speed network. We assume that the network is connection oriented and enforces some admission control which ensures that the source traffic conforms to specified traffic characteristics. We concentrate on the class of rate-controlled service (RCS) disciplines, in which traffic from each connection is reshaped at every hop, and develop end-to-end delay bounds for the general case where different reshapers are used at each hop. In addition, we establish that these bounds can also be achieved when the shapers at each hop have the same "minimal" envelope. The main disadvantage of this class of service disciplines is that the end-to-end delay guarantees are obtained as the sum of the worst case delays at each node, but we show that this problem can be alleviated through "proper" reshaping of the traffic. We illustrate the impact of this reshaping by demonstrating its use in designing RCS disciplines that outperform generalized processor sharing-based service disciplines.

The problem of designing a logical topology over a wavelength-routed all-optical network (AON) physical topology is studied. The physical topology consists of the nodes and fiber links in the network. On an AON physical topology, we can set up lightpaths between pairs of nodes, where a lightpath represents a direct optical connection without any intermediate electronics. The set of lightpaths along with the nodes constitutes the logical topology. For a given network physical topology and traffic pattern, our objective is to design the logical topology and the routing algorithm so as to minimize the network congestion while constraining the average delay seen by a source-destination pair and the amount of processing required at the nodes (degree of the logical topology). Ignoring the delay constraints can result in fairly convoluted logical topologies with very long delays. On the other hand, in all our examples, imposing it results in a minimal increase in congestion. While the number of wavelengths required to imbed the resulting logical topology on the physical all optical topology is also a constraint in general, we find that in many cases of interest this number can be quite small. We formulate the combined logical topology design and routing problem described above as a mixed integer linear programming problem which we then solve for a number of cases of a six-node network. This programming problem is split into two subproblems: logical topology design, and routing. We then compare the performance of several heuristic topology design algorithms against that of randomly generated topologies, as well as lower bounds.

This paper addresses the problem of providing per-connection end-to-end delay guarantees in a high-speed network. We consider a network comprised of store-and-forward packet switches, in which a packet scheduler is available at each output link. We assume that the network is connection oriented and enforces some admission control which ensures that the source traffic conforms to specified traffic characteristics. We concentrate on the class of rate-controlled service (RCS) disciplines, in which traffic from each connection is reshaped at every hop, and develop end-to-end delay bounds for the general case where different reshapers are used at each hop. In addition, we establish that these bounds can also be achieved when the shapers at each hop have the same "minimal" envelope. The main disadvantage of this class of service discipline is that the end-to-end delay guarantees are obtained as the sum of the worst-case delays at each node, but we show that this problem can be alleviated through "proper" reshaping of the traffic. We illustrate the impact of this reshaping by demonstrating its use in designing RCS disciplines that outperform service disciplines that are based on generalized processor sharing (GPS). Furthermore, we show that we can restrict the space of "good" shapers to a family which is characterized by only one parameter. We also describe extensions to the service discipline that make it work conserving and as a result reduce the average end-to-end delays.

Considers routing connections in a reconfigurable optical network using WDM. Each connection between a pair of nodes in the network is assigned a path through the network and a wavelength on that path, such that connections whose paths share a common link in the network are assigned different wavelengths. The authors derive an upper bound on the carried traffic of connections (or equivalently, a lower bound on the blocking probability) for any routing and wavelength assignment (RWA) algorithm in such a network. The bound scales with the number of wavelengths and is achieved asymptotically (when a large number of wavelengths is available) by a fixed RWA algorithm. The bound can be used as a metric against which the performance of different RWA algorithms can be compared for networks of moderate size. The authors illustrate this by comparing the performance of a simple shortest-path RWA (SP-RWA) algorithm via simulation relative to the bound. They also derive a similar bound for optical networks using dynamic wavelength converters, which are equivalent to circuit-switched telephone networks, and compare the two cases. Finally, they quantify the amount of wavelength reuse achievable in large networks using the SP-RWA via simulation as a function of the number of wavelengths, number of edges, and number of nodes for randomly constructed networks as well as de Bruijn networks. They also quantify the difference in wavelength reuse between two different optical node architectures.>

The author consider the problem of routing connections in an optical network using wavelength division multiplexing, where each connection between a pair of nodes in the network is assigned a path through the network and a wavelength on that path, such that connections whose paths share a common link in the network are assigned different wavelengths. They derive an upper bound on the carried traffic of connections (or equivalently, a lower bound on the blocking probability) for any routing and wavelength assignment (RWA) algorithm in such a network. The bound scales with the number of wavelengths and is achieved asymptotically (when a large number of wavelengths is available) by a fixed RWA algorithm. Although computationally intensive, this bound can be used as a metric against which the performance of different RWA algorithms can be compared for networks of moderate size. They illustrate this by comparing the performance of a simple RWA algorithm via simulation with our bound. They also derive a similar bound for optical networks using dynamic wavelength converters, which are equivalent to circuit-switched telephone networks, and compare the two cases for different examples.>

We propose a new architecture for a high-speed packet-switched metropolitan-area lightwave network using a combination of wavelength division multiplexing over fiber and subcarrier multiplexing within each wavelength. Each station transmits on a fixed-wavelength (that may also be used by some other stations) at any one of many available subcarrier frequencies within that wavelength, and receives on some fixed wavelength and fixed subcarrier frequency. Rapid tuning between subcarrier frequencies allows a station to transmit packets to all stations that receive on some subcarrier channel on its transmit wavelength. Packets intended for stations that do not receive on the wavelength of the transmitting station must be routed through intermediate stations. By avoiding rapid tuning between wavelengths, we realise a practical multihop architecture for packet switching with one optical transmitter shared among many stations and one optical receiver per station. This architecture imposes a constraint on the multihop connectivity pattern in the network since all stations using a common transmit wavelength send packets directly to the same set of other stations. The same constraint is applicable to shared-channel multihop networks with a single transmitter and receiver per station. We introduce the notion of "clusterable" directed graphs to represent the connectivity patterns that are possible, and using the properties of these graphs, show that nodes can be added to and removed from the network with minimal disruption to the other nodes. We show that some well-known multihop topologies such as shufflenets and de Bruijn graphs are clusterable. Power budget calculations indicate the feasibility of a 32-wavelength network with five 200 Mb/s FSK subcarrier channels on each wavelength. Our throughput calculations indicate that such a network could support 160 stations with a throughput per station of 44 Mb/s.>

Studies the performance of channel assignment algorithms for "channelized" (e.g., FDMA or TDMA) cellular telephone systems, via mathematical models, each of which is characterized by a pair (H,p), where H is a hypergraph describing the channel reuse restrictions, and p is a probability vector describing the variation of traffic intensity from cell to cell. For a given channel assignment algorithm, the authors define T(r) to be the amount of carried traffic, as a function of the offered traffic, where both r and T(r) are measured in Erlangs per channel. They show that for a given H and p, there exists a function T/sub H,p/(r), which can be computed by linear programming, such that for every channel assignment algorithm, T(r)/spl les/T/sub H,p/(r). Moreover, they show that there exist channel assignment algorithms whose performance approaches T/sub H,p/(r) arbitrarily closely as the number of channels increases. As a corollary, they show that for a given (H,p) there is a number r/sub 0/, which also can be computed by linear programming, such that if the offered traffic exceeds r/sub 0/, then for any channel assignment algorithm, a positive fraction of all call requests must be blocked, whereas if the offered traffic is less than r/sub 0/, all call requests can be honored, if the number of channels is sufficiently large. The authors call r/sub 0/, whose units are Erlangs per channel, the capacity of the cellular system.>

Proposes de Bruijn graphs as logical topologies for multihop lightwave networks. After deriving bounds on the throughput and delay performance of any logical topology, the authors compute the throughput and delay performance of de Bruijn graphs for two different routing schemes and compare it with their bounds and the performance of shufflenets. For a given maximum nodal in- and out-degree and average number of hops between stations, a logical topology based on a de Bruijn graph can support a larger number of stations than a shufflenet and this number is close to the maximum that can be supported by any topology. The authors also propose de Bruijn graphs as good physical topologies for wavelength routing lightwave networks consisting of all-optical routing nodes interconnected by point-to-point fiber links. The worst-case loss experienced by a transmission is proportional to the maximum number of hops (diameter). For a given maximum nodal in- and out-degree and diameter, a physical topology based on a de Bruijn graph can support a large number of stations using a relatively small number of wavelengths.>

A media-access protocol for high-speed packet-switched multichannel networks that are based on a broadcast topology, such as optical passive star networks using wavelength-division multiple access, is described. The protocol supports connection-oriented traffic with or without bandwidth reservation, as well as datagram traffic to integrate transport-layer functions with the media-access layer. It uses the bandwidth efficiently while keeping the processing requirements low by requiring stations to compute their transmission and reception schedules only at the start and end of each connection. Analysis results show that low blocking probabilities for connections and high network throughput can be achieved.>

The authors present a study of the performance of a general class of channel assignment algorithms. These algorithms, which they call Omega -algorithms, are completely characterized by the set of carried-traffic "states" which they allow. They show that for any such algorithm, there is a closed-form expression for the carried traffic function, which lends itself to several kinds of asymptotic analysis. As an application, they study a particular Omega -algorithm, which has been previously studied under the name "maximum packing algorithm", and which is a "greedy" dynamic channel assignment algorithm, and show that its performance is in many cases inferior to that of simple fixed channel assignment algorithms. They show that the cause of this unexpected phenomenon is the tendency of dynamic algorithms to get trapped in states that are locally, but not globally, maximal.>

This paper proposes a new media-access protocol for high-speed packet-switched multichannel networks based on a broadcast topology, for example, optical passive star networks using wavelength-division multiple access. The protocol supports connection-oriented traffic with or without bandwidth reservation as well as datagram traffic, in an attempt to integrate transport-layer functions with the media-access layer. It utilizes the bandwidth efficiently while keeping the processing requirements low by requiring stations to compute their transmission and reception schedules only at the start and end of each connection. A simple analysis shows that we can achieve low blocking probabilities for connections, as well as high network throughput.

The authors de Bruijn graphs as logical topologies for multihop lightwave networks. The throughput and delay performance of networks based on de Bruijn graphs are compared with those of shufflenets. It is shown that for a given maximum nodal in- and out-degree and average number of hops between stations, a network based on a de Bruijn graph can support a much larger number of stations than a shufflenet. This increase in the number of stations is obtained at the expense of some nonuniformity in edge loading when the traffic distribution over the source-destination pairs is uniform. In the 1024-node example, this results in a slightly lower throughput for the network based on the de Bruijn graph compared to the shufflenet, but the former has lower delay at low offered loads.>