Queueing-based analysis of broadcast optical networks.
We consider broadcast WDM networks operating with schedules that mask the transceiver tuning latency. We develop and analyze a queueing model of the network in order to obtain the queue-length distribution and the packet loss probability at the transmitting and receiving side of the nodes. The analysis is carried out assuming finite buffer sizes, non-uniform destination probabilities and two-state MMBP traffic sources; the latter naturally capture the notion of burstiness and correlation, two important characteristics of traffic in high-speed networks. We present results which establish that the performance of the network is a complex function of a number of system parameters, including the load balancing and scheduling algorithms, the number of available channels, and the buffer capacity. We also show that the behavior of the network in terms of packet loss probability as these parameters are varied cannot be predicted without an accurate analysis. Our work makes it possible to study the interactions among the system parameters, and to predict, explain and fine tune the performance of the network.
Introduction
It has long been recognized that Wavelength Division Multiplexing
(WDM) will be instrumental in bridging the gap
between the speed of electronics and the virtually unlimited
bandwidth available within the optical medium. The wave-length
domain adds a significant new degree of freedom to
network design, allowing new network concepts to be devel-
oped. For a local area environment with a small number
of users, the WDM broadcast-and-select architecture has
emerged as a simple and cost-effective solution. In such a
LAN, nodes are connected through a passive broadcast star
coupler and communicate using transceivers tunable across
the network bandwidth.
This work was supported in part by NSF grant NCR-9701113.
A significant amount of research effort has been devoted
to the study of WDM architectures in recent years [4]. The
performance analysis of these architectures has been typically
carried out assuming uniform traffic and memoryless
arrival processes [16, 3, 5]. However, it has been established
that, in order to study correctly the performance of a net-
work, one needs to use models that capture the notion of
burstiness and correlation in the traffic stream, and which
permit non-uniformly distributed destination probabilities
[8, 9]. Two studies of optical networks that use non-Poisson
traffic models appeared recently in [13, 14]. The work in
[13] derives a stability condition for the HiPeR-' reservation
protocol, while [14] studies the effects of wavelength conversion
in wavelength routing networks. We are not aware of
any queueing-based studies of broadcast WDM networks.
In this paper we revisit the well known broadcast-and-
select WDM architecture in an attempt to investigate the
performance of broadcast optical networks under more realistic
traffic assumptions and finite buffer capacity. Specif-
ically, we develop a queueing-based decomposition algorithm
to study the performance of a network operating under schedules
that mask the transceiver tuning latency [6, 12, 1, 2,
11]. The analysis is carried out using Markov Modulated
Bernoulli Process (MMBP) arrival models that naturally
capture the important characteristics of traffic in high-speed
networks. Additionally, our analysis allows for unequal traffic
flows to exist between sets of nodes. Our work makes
it possible to study the complex interaction among the various
system parameters such as the arrival processes, the
number of available channels, and the scheduling and load
balancing algorithms. To the best of our knowledge, such
a comprehensive performance analysis of a broadcast WDM
architecture has not been done before.
The next section presents the queueing and traffic model
and provides some background information. The performance
analysis of the network is presented in Sections 3 and
4, numerical results are given in Section 5, and we conclude
the paper in Section 6.
System Model
In this section we introduce a model for the media access
control (MAC) layer in a broadcast-and-select WDM LAN.
The model consists of two parts, a queueing network and a
transmission schedule. We also present a traffic model to
characterize the arrival processes to the network.
l l
l l
l l
l l
node N
CCfixed
optical
filters
l (1)
l (N)
passive star
transmitting
queues receiving
queues
to users
node 1
node N
node 1
tunable
lasers
from users

Figure

1: Queueing model of a broadcast WDM architecture
with N nodes and C wavelengths
2.1 The Queueing Model
We consider an optical network architecture with N nodes
communicating over a broadcast passive star that can support
Figure 1). Each
node is equipped with a laser that enables it to inject signals
into the optical medium, and a filter capable of receiving
optical signals. The laser at each node is tunable
over all available wavelengths. The optical filters, on the
other hand, are fixed to a given wavelength. Let -(j) denote
the receiving wavelength of node j. Since C - N ,
a set Rc of nodes may be sharing a single wavelength -c :
Each node consists of a transmitting side and a receiving
side, as Figure 1 illustrates. New packets (from users) arrive
at the transmitting side of a node i and are buffered at a finite
capacity queue, if the queue is not full. Otherwise, they
are dropped. As Figure 1 indicates, the buffer space at the
transmitting side of each node is assumed to be partitioned
into C independent queues. Each queue c;
at the transmitting side of node i contains packets destined
for the receivers which listen to wavelength -c . This arrangement
eliminates the head-of-line problem, and permits
a node to send several packets back-to-back when tuned to
a certain wavelength. We let B (in)
ic denote the capacity of
the transmitting queue at node i corresponding to channel
-c .
Packets buffered at a transmitting queue are sent on a
FIFO basis onto the optical medium by the node's laser. A
schedule (discussed shortly) ensures that transmissions on
a given channel will not collide, hence a transmitted packet
will be correctly received by its destination node. Upon
arriving at the receiving side of its destination node, a packet
is placed in another finite capacity buffer before it is passed
to the user for further processing. We let B (out)
j denote the
buffer capacity of the receiving queue at node j. Packets
arriving to find a full receiving queue are lost. Packets in a
receiving queue are also served on a FIFO basis.
Packets in the network have a fixed size and the nodes
operate in a slotted mode. Since there are N nodes but C -
N channels, the passive star (i.e., each of the C channels)
must run at a rate N
C times faster than the rate at which
users at each node can generate or receive packets ( N
need
not be an integer). In other words, the MAC-to-network
interface runs faster than the user-to-MAC interface. Thus,
we distinguish between arrival slots (which correspond to
the packet transmission time at the user rate) and service
slots (which are equal to the packet transmission time at the
channel rate within the network). Obviously, the duration of
a ga a ag g g1 N Nl c
Frame
(a)
(b)
arrival slot service slot
c
c

Figure

2: (a) Schedule for channel -c , and (b) detail corresponding
to node 2
a service slot is equal to C
N times that of an arrival slot. All
N nodes are synchronized at service slot boundaries. Using
timing information about service slots and the relationship
between service and arrival slots one can derive the timing
of arrival slots. Hence, we assume that all users are also
synchronized at arrival slot boundaries.
2.2 Transmission Schedules
One of the potentially difficult issues that arises in a WDM
environment, is that of coordinating the various transmit-
ters/receivers. Some form of coordination is necessary because
(a) a transmitter and a receiver must both be tuned
to the same channel for the duration of a packet's transmis-
sion, and (b) a simultaneous transmission by one or more
nodes on the same channel will result in a collision. The
issue of coordination is further complicated by the fact that
tunable transceivers need a non-negligible amount of time
to switch between wavelengths.
Several scheduling algorithms have been proposed for the
problem of scheduling packet transmissions in such an environment
[6, 12, 1, 2, 11]. Although these algorithms differ
in terms of their design and operation, surprisingly the resulting
schedules are very similar. A model that captures
the underlying structure of these schedules is shown in Figure
2. In such a schedule, node i is assigned a ic contiguous
service slots for transmitting packets on channel -c . These
a ic slots are followed by a gap of g ic - 0 slots during which
no node can transmit on -c . This gap may be necessary
to ensure that the laser at node i + 1 has sufficient time to
tune from wavelength -c\Gamma1 to -c before it starts transmis-
sion. Note that in Figure 2 we have assumed that an arrival
slot is an integer multiple of service slots. This may not
be true in general, and it is not a necessary assumption for
our model. Observe also that, although a schedule begins
and ends on arrival slot boundaries, the beginning or end of
transmissions by a node does not necessarily coincide with
the beginning or end of an arrival slot (although they are,
obviously, synchronized with service slots).
We assume that transmissions by the transmitting queues
onto wavelength -c follow a schedule as shown in Figure 2.
This schedule repeats over time. Each frame of the schedule
consists of M arrival slots. Quantity a ic
can be seen as the number of service slots per frame
allocated to node i, so that the node can satisfy the required
quality of service of its incoming traffic intended for
wavelength -c . By fixing a ic , we indirectly allocate a certain
amount of the bandwidth of wavelength -c to node i.
This bandwidth could, for instance, be equal to the effective
bandwidth [7] of the total traffic carried by node i on
wavelength -c . In general, the estimation of the quantities
a is part of the connection
admission algorithm [7], and it is beyond the scope of this
paper. We note that as the traffic varies, a ic may vary as
well. In this paper, we assume that quantities a ic are fixed,
since this variation will more likely take place over larger
scales in time.
2.3 Traffic Model
The arrival process to each transmitting queue of the net-work
is characterized by a two-state Markov Modulated Bernoulli
Process (MMBP), hereafter referred to as 2-MMBP.
A 2-MMBP is a Bernoulli process whose arrival rate varies
according to a two-state Markov chain. It captures the
notion of burstiness and the correlation of successive interarrival
times, two important characteristics of traffic in
high-speed networks. For details on the properties of the
2-MMBP, the reader is referred to [10]. (We note that the
algorithm for analyzing the network was developed so that
it can be readily extended to MMBPs with more than two
states.)
We assume that the arrival process to transmitting queue
given by a 2-
MMBP characterized by the transition probability matrix
by A ic as follows:
ic q (01)
ic
ic q (11)
ic
and A
ic
(1)
In (1), q (kl)
is the probability that the 2-
MMBP will make a transition to state l, given that it is
currently at state k. Obviously, q (k0)
Also, ff (0)
ic (ff (1)
ic ) is the probability that an arrival will occur
in a slot at state 0 (1). Transitions between states of the
occur only at the boundaries of arrival slots. We
assume that the arrival process to each transmitting queue is
given by a different 2-MMBP. From (1) and [10], the steady-state
arrival probability for the arrival process to this queue
is
ic ff (0)
ic ff (1)
ic
ic
(2)
the probability that a packet generated
at node i will have j as its destination node. We will refer
to as the routing probabilities; this description implies
that the routing probabilities can be node-dependent and
non-uniformly distributed. The destination probabilities of
successive packets are not correlated. That is, in a node,
the destination of one packet does not affect the destination
of the packet behind it. Given these assumptions, the
probability that a packet generated at node i will have to
be transmitted on wavelength -c is:
Obviously, the relationship between r ic and fl ic is given by
Queueing Analysis
In this section we analyze the queueing network shown in

Figure

1, which represents the tunable-transmitter, fixed-
receiver optical network under study. The arrival process to
passive starN
l
filters
optical
fixed
l
c
c
corresponding
to
listening to
l
l
c
c
l c
l
c
transmitting queues
receiving queues

Figure

3: Queueing sub-network for wavelength -c
each transmitting queue is assumed to be a 2-MMBP, and
the access of the transmitting queues to the wavelengths
is governed by a schedule similar to the one described in
Section 2.2. We analyze this queueing network in order to
obtain the queue-length distribution in a transmitting or
receiving queue, from which performance measures such as
the packet-loss probability can be obtained.
3.1 Transmitting Side Analysis
We first note that the original queueing network can be decomposed
into C sub-networks, one per wavelength, as in

Figure

3. For each wavelength -c , the corresponding sub-network
consists of N transmitting queues, and all the receiving
queues that listen to wavelength -c . Each transmitting
queue i of the sub-network is the one associated with
wavelength -c in the i-th node. These transmitting queues
will transmit to the receiving queues of the sub-network over
wavelength -c . Note that, due to the independence among
the C queues at each node, the transmission schedule (i.e.,
the fact that different nodes transmit on the same wave-length
at different times), and the fact that each receiver
listens to a specific wavelength, this decomposition is exact.
In view of this decomposition, it suffices to analyze a single
sub-network, since the same analysis can be applied to all
other sub-networks.
Consider now the sub-network for wavelength -c . We
will analyze this sub-network by decomposing it into individual
transmitting and receiving queues. As discussed in
the previous section, each transmitting queue i of the sub-network
is only served for a ic consecutive service slots per
frame. During that time, no other transmitting queue is
served. Transmitting queue i is not served in the remaining
slots of the frame. In view of this, there is no dependence
among the transmitting queues of the sub-network, and consequently
each one can be analyzed in isolation in order to
obtain its queue-length distribution. (Each receiving queue
will also be considered in isolation in Section 3.2.)
From the queueing point of view, the queueing network
shown in Figure 3 can be seen as a polling system in discrete
time. Despite the fact that polling systems have been extensively
analyzed, we note that very little work has been done
within the context of discrete time (see, for example, [18]).
In addition, this particular problem differs from the typical
polling system since we consider receiving queues, which are
not typically analyzed in polling systems.
a ic
(a)
Frame
l c
(b)
observation instant
transition instant
service completion
instant
2-MMBP state
arrival instant

Figure

4: (a) Service period of transmitting queue i on channel
-c , and (b) detail showing the relationship among service
completion, arrival, 2-MMBP state transition, and observation
instants within a service and an arrival slot
3.1.1 The Queue-Length Distribution of a Transmitting
Queue
Consider transmitting queue i of the sub-network for -c in
isolation. This queue receives exactly a ic service slots on
wavelength -c , as shown in Figure 4(a). The block of a ic
service slots may not be aligned with the boundaries of the
arrival slots. For instance, in the example shown in Figure
4(a), the block of a ic service slots begins at the second service
slot of arrival slot x \Gamma 1, and it ends at the end of the
second service slot in arrival slot x
number within a frame.
For each arrival slot, define v ic (x) as the number of service
slots allocated to transmitting queue i, that lie within
arrival slot x 1 . Then, in the example in Figure 4(a), we
0 for all other x 0 . Obviously, we have
We analyze transmitting queue i by constructing its underlying
Markov chain embedded at arrival slot boundaries.
The order of events is as follows. The service (i.e., trans-
mission) completion of a packet occurs at an instant just
before the end of a service slot. An arrival may occur at
an instant just before the end of an arrival slot, but after
the service completion instant of a service slot whose end
is aligned with the end of an arrival slot. The 2-MMBP
describing the arrival process to the queue makes a state
transition immediately after the arrival instant. Finally, the
Markov chain is observed at the boundary of each arrival
slot, after the state transition by the 2-MMBP. The order
of these events is shown in Figure 4(b).
The state of the transmitting queue is described by the
tuple (x;
In

Figure

4, we assume that each arrival slot contains an integral
number of service slots. If this is not the case, v ic (x) is defined as
the number of service slots that end within arrival slot x (i.e., if there
is a service slot that lies partially within arrival slots x and x
will be counted in v ic
ffl x represents the arrival slot number within a frame
ffl y indicates the number of packets in the transmitting
queue
ic ), and
ffl z indicates the state of the 2-MMBP describing the
arrival process to this queue, that is,
It is straightforward to verify that, as the state of the
queue evolves in time, it defines a Markov chain. Let \Phi
denote modulo-M addition, where M is the number of arrival
slots per frame. Then, the transition probabilities out
of state (x; y; z) are given in Table 1. Note that, the next
state after (x; always has an arrival slot number equal
to x \Phi 1. In the first row of Table 1 we assume that the 2-
MMBP makes a transition from state z to state z 0 (from (1),
this event has a probability q (zz 0 )
ic of occurring), and that no
packet arrives to this queue during the current slot (from
(1) and (3), this occurs with probability
at most v ic are serviced during arrival slot
x \Phi 1, and since no packet arrives, the queue length at the
end of the slot is equal to maxf0; y 1)g. In the
second row of Table 1 we assume that the 2-MMBP makes
a transition from state z to state z 0 and a packet arrives to
the queue. This arriving packet cannot be serviced during
this slot, and has to be added to the queue. Finally, the
expression for the new queue length ensures that it will not
exceed the capacity B (in)
ic of the transmitting queue.
The probability transition matrix of this Markov chain is
straightforward to derive from Table 1. This matrix defines
a p-cyclic Markov chain [15], and therefore it can be solved
using any of the techniques for p-cyclic Markov chains in
[15, ch. 7]. We have used the LU decomposition method in
[15] to obtain the steady state probability - ic (x; z) that at
the end of arrival slot x, the 2-MMBP is in state z and the
transmitting queue has y packets. The steady-state probability
that the queue has y packets at the end of slot x,
independent of the state of the 2-MMBP is:
Finally, we note that all of the results obtained in this
subsection can be readily extended to MMBP-type arrival
processes with more than two states.
3.2 Receiving Side Analysis
Consider the sub-network for wavelength -c in Figure 3, and
observe that the arrival process to the receiving queues sharing
-c is the combination of the departure processes from
the transmitting queues corresponding to -c . An interesting
aspect of the departure process from the transmitting
queues is that for each frame, during the sub-period a ic we
only have departures from the i-th queue. This period is
then followed by a gap g ic during which no departure occurs.
This cycle repeats for the next transmitting queue. Thus,
in order to characterize the overall departure process offered
as the arrival process to these receiving queues, it suffices to
characterize the departure process from each transmitting
queue, and then combine them. (We note that this overall
departure process is quite different from the typical superposition
of a number of departure processes into a single
stream, where, at each slot, more than one packet may be
departing.) The overall departure process is completely defined
given the queue-length distribution of all transmitting

Table

1: Transition probabilities out of state (x; y; z) of the Markov chain
Current State Next State Transition Probability
ic ff (z)
ic
queues in the sub-network (which may be obtained using
the analysis in Section 3.1), since then the probability that
a packet will be transmitted on channel -c in any given service
slot is known.
However, the individual arrival processes to each of the
receiving queues listening on -c are not independent. Specif-
ically, if j and j 0 are two receivers on -c , and there is a
transmission from transmitting queue i to receiving queue
j in a given service slot, then there can be no arrival to
receiving queue j 0 in the same service slot. We will nevertheless
make the assumption that these arrival processes
are indeed independent, and that each is an appropriately
thinned (based on the routing probabilities) version of the
departure process from the transmitting queues. Note that
this is an approximation only when there are multiple nodes
with receivers fixed on channel -c . This assumption allows
us to decompose the sub-network of Figure 3 into individual
receiving queues and to analyze each of them in isolation 2 .
3.2.1 The Queue-Length Distribution of a Receiving Queue
As in the previous section, we obtain the queue-length distribution
of receiving queue j at arrival slot boundaries. During
an arrival slot x a packet may be transmitted to the user
from the receiving queue. However, during slot x, there may
be several arrivals to this receiving queue from the transmitting
queues. Let (x; w) be the state associated with receiving
queue j, where
ffl x indicates the arrival slot number within the frame
ffl w indicates the number of packets at the receiving
queue
We assume the following order of events. A packet will
begin to depart from the receiving queue at an instant immediately
after the beginning of an arrival slot and the departure
will be completed just before the end of the slot.
A packet from a transmitting queue arrives at an instant
just before the end of a service slot, but before the end-of-
departure instant of an arrival slot whose end is aligned with
the end of the service slot. Finally, the state of the queue
is observed just before the end of an arrival slot and after
the arrival associated with the last service slot has occurred
(see

Figure

5(b)).
We also note that the approach of analyzing each receiving queue
in isolation gives correct results for the individual receiving queues;
after all, in steady-state, the probability that a packet transmitted
by node i on - c will have j as its destination will equal the routing
This approach is an approximation only when one attempts
to combine results from individual receiving queues to obtain
the overall performance for the network. It is possible to apply techniques
to adjust for this approximation when aggregating individual
results [17]. We will not consider such techniques here, instead we
will only concentrate on individual queues.
(a)
a i+1,c
a ic
Frame
l c
(b)
instant at which
departure starts
observation instant
arrival instant
instant at which
departure ends
x
x

Figure

5: (a) Arrivals to receiving queue j from transmitting
queues i and detail showing the relationship
of departure, arrival, and observation instants
Let u j (x) be the number of service slots of any transmitting
queue on channel -c within arrival slot x. We have:
where v ic (x) is as defined in (4). Quantity u j (x) represents
the maximum number of packets that may arrive to
receiving queue j within slot x. In the example of Figure
5(a) where we show the arrival slots during which packets
from transmitting queues i and may arrive to
receiving queue j, we have: u
Observe now that (a) at each state transition x advances
by one (modulo-M ), (b) exactly one packet departs from
the queue as long as the queue is not empty, (c) a number
packets may be transmitted from the
transmitting queues to receiving queue j within arrival slot
x \Phi 1, and that (d) the queue capacity is B (out)
. Then, the
transition probabilities out of state (x; w) for this Markov
chain can be obtained from Table 2.
In

Table

is the probability that transmitting
queue packets to receiving queue j given that
the system is at the end of arrival slot x (in other words, it
is the probability that s i packets are transmitted within slot
To obtain L
ij as the conditional
3 Since in most cases only one or two transmitting queues will transmit
to the same channel within an arrival slot (refer also to Figure
2), the summation and product in the expression in the last column
of

Table

2 do not necessarily run over all N values of i, only over one

Table

2: Transition probabilities out of state (x; w) of the Markov chain
Current State Next State Transition Probability
probability that a packet is destined for node j, given that
the packet is destined to be transmitted on -c , the receive
wavelength of node j:
r ic
as the conditional probability of having
y packets at the i-th transmitting queue given that the
system is observed at the end of slot x:
Then, for r 0
is given by
ic
Expression can be explained by noting that transmitting
queue i will transmit s i packets to receiving queue j during
arrival slot x \Phi 1 if (a) v ic
packets in its transmitting queue for -c at the beginning of
the slot (equivalently, at the end of slot x), and (c) exactly
s i of minfy; v ic (x \Phi 1)g packets that will be transmitted by
this queue in this arrival slot are for receiver j. Expression
represents the "thinning" of the arrival processes to the
various receiving queues of the sub-network using the r 0
routing probabilities, and discounts the correlation among
arrival streams to the different queues. Expression (9) is
the crux of our approximation for the receiving side of the
network.
If r 0
1, in which case j is the only node listening
on wavelength -c , the expression for must be
modified as follows (recall that there is no approximation in
this case):
ic
Expressions and (10) are based on the assumption
that v ic
ic which we believe is a reasonable one.
In the general case, quantity v ic (x \Phi 1) in both expressions
must be replaced by minfv ic
ic g.
The transition matrix of the Markov chain defined by the
evolution of the state (x; w) of receiving queue j also defines
a p-cyclic Markov chain. We have used the LU decomposition
method as prescribed in [15] to obtain - j (x; w), the
steady-state probability that receiving queue j has w packets
at the end of slot x.
or two values of i. Thus, this expression can be computed very fast,
not in exponential time as implied by the general form presented in
the table.
4 Packet-Loss Probability
We now use the queue-length distributions - ic (x; y) and
derived in the previous section, to obtain the packet-loss
probability at the transmitting and receiving queues.
4.1 The Packet-Loss Probability at a Transmitting Queue
Let\Omega ic be the packet-loss probability at the c-th transmitting
queue of node i, i.e., the probability that a packet arriving
to that queue will be
lost.\Omega ic can be expressed as:
lost per frame at queue c; node i]
E[# arrivals per frame at queue c; node i]
The expectation in the denominator can be seen to be
equal to M fl ic , where fl ic is the steady-state arrival probability
of the arrival process to this queue from (2). To
obtain the expectation in the numerator, let us refer to Figure
which shows the service completion, arrival, and
observation instants within slot x. We observe that, due to
the fact that at most one packet may arrive in slot x, if the
number v ic (x) of slots during which this queue is serviced
within arrival slot x is not zero (i.e., v ic (x) ? 0), no arriving
packet will be lost. Even if the c-th queue at node i is full at
the beginning of slot x, v ic packets will be serviced
during this slot, and the order of service completion and
arrival instants in Figure 4(b) guarantees that an arriving
packet will be accepted. On the other hand, if v ic
for slot x, then an arriving packet will be discarded if and
only if the queue is full at the beginning of x (equivalently,
at the end of the slot before x). Since the 2-MMBP can
be in one of two states, we have that the numerator of (11)
is equal to
x:v ic (x)=0
z=0 ff (z)
\Psi denotes regular subtraction with the exception that, if
and the summation runs over
all x for which v ic Using these expressions and the
fact that - ic
M for all x, we obtain an expression for
\Omega ic as follows:
x:v ic (x)=0
z=0 ff (z)
4.2 The Packet-Loss Probability at a Receiving Queue
The packet-loss probability at a receiving queue is more complicated
to calculate, since we may have multiple packet
arrivals to a given queue within a single arrival slot (re-
fer to

Figure

5(a)). Let us
as the conditional
probability that n packets will be lost at receiving
queue j given that the current arrival slot is x. A receiving
queue will lose n packets in slot x if (a) the queue had
packets at the beginning of slot x, and
(b) exactly B (out)
arrived during slot x. We
can then write:
pkts arrive to j j x](13)
similar to (8). The last
probability in (13) can be easily obtained using (9) or (10),
as in the last column of Table 2.
Note that at most u j (x) packets may arrive (and get
lost) in arrival slot x. Using (13), we can then compute the
expected number of packets lost in slot x as:
E[number of packets lost at
The expected number of arrivals to receiving queue j in slot
x can be computed as:
E[# arrivals to j j
sPr[s pkts arrive to j j x] (15)
Finally, the
probability\Omega j that an arriving packet to node
j will be lost regardless of the arrival slot x can be found as
follows:
x=0 E[number of lost packets at j j x]
x=0 E[number of arrivals to j j x]
5 Numerical Results
We now apply our analysis to a network with nodes.
The arrival process to each of the transmitting queues of the
network is described by a different 2-MMBP. The 2-MMBPs
selected exhibit a wide range of behavior in terms of two
important parameters, the mean interarrival time and the
squared coefficient of variation of the interarrival time. The
routing probabilities we used are:
ae
That is, receiver 1 is a hot spot, receiving 10% of the total
traffic, while the remaining traffic is evenly distributed
to the other 15 nodes. The total rate at which packets are
generated by users of the network is 1.98 packets per arrival
slot. Most of the traffic is generated at node 1, as the rate
of new packets generated at this node is 0.583 packets per
arrival slot. The packet generation rate decreases monotonically
for nodes 2 to 16. For load balancing purposes, we have
allocated one of the C channels exclusively to node 1, since
this node receives a considerable fraction of the total traffic.
The remaining are shared by the other 15
receivers. The allocation of the receivers to the remaining
wavelengths was performed in a round-robin fashion, and is
given in Table 3 for
The quantities a ic of the schedule, i.e., the number of
packets to be transmitted by node i onto channel -c per
frame (refer to Section 2.2 and Figure 2) were fixed to be as
close to (but no less than) 0.5 arrival slots as possible. Recall
that, while the length of an arrival slot is independent of C
and is taken as our unit of time, the length of a service slot

Table

3: Channel sharing for
depends on the number of channels. In cases in which 0.5
arrival slots is not an integral number of service slots, the
value a ic is rounded up to the next integer to ensure that
every queue is granted at least 0.5 arrival slots of service
during each frame 4 (i.e., a
In constructing
the schedules, we have assumed that the time it takes a laser
to tune from one channel to another is equal to one arrival
slot 5 . Finally, for all of the results we present in this section
we have let all transmitting and receiving queues have the
same buffer capacity B (i.e., B (in)
to reduce
the number of parameters that need to be controlled.
In

Figure

6 we show the part of the schedule corresponding
to channel -1 for three different values of the number
of channels and 8; the parts of the schedules for
other channels are very similar. The schedules will help explain
the performance results to be presented shortly. Since
the number of nodes each arrival slot
is exactly four service slots long. Each node is allocated
arrival slots, or 2 service slots for transmissions on each
channel, as Figure 6(a) illustrates. For the network is
bandwidth limited [12], that is, the length of the schedule is
determined by the bandwidth requirements on each channel
arrival slots), not the transmission and tuning
requirements of each node (= 4 \Theta 0:5
slots). The schedule for Figure 6(b) is an example
where there is a non-integral number of service slots within
each arrival slot. More precisely, one arrival slot contains
6 , or 2 2
service slots. Each node is assigned two service
slots (a for transmissions on each channel, since
one service slot is less than 0.5 arrival slots. For the
network is again bandwidth limited, and the total schedule
length becomes service slots, or 12 arrival slots.
Finally, when
slots, and the corresponding schedule is shown in Figure
6(c). However, in this case the network is tuning limited [12],
i.e., the node transmission and tuning requirements determine
the schedule length. Since each node has to transmit
for 0.5 arrival slots on each channel, and to tune to each
of the 8 channels (recall that the tuning time is one arrival
4 Other schemes for allocating a ic have been implemented, including
setting a ic proportional to r ic , setting a ic proportional to
ic g, and setting a ic to the effective bandwidth [7] of node
i's total traffic carried on channel - c . Although the packet loss probability
results do depend on the actual values of a ic , the overall conclusions
drawn regarding our analysis are very similar. Thus, we have
decided to include only the simplest case here.
5 Again, due to the synchronous nature of this network, if one arrival
slot is not an integral number of service slots, the number of
service slots for which a transmitter cannot transmit is rounded up
to the next integer, thereby setting the required time for tuning to
some value slightly greater than one arrival slot. As a result, the
tuning time is always d N
C e service slots.
(a)
(c)
Transmitting queue number
denotes unused slot)
arrival slot
arrival slot
arrival slot
service slot
service slot
service slot

Figure

Transmission schedules for -1 and
slot), the total schedule length is 8 \Theta 0:5
slots. But the transmissions on each channel only take
arrival slots; the remaining 4 arrival slots in

Figure

6(c) are not used.

Figures

7-10 show the packet loss probability (PLP) at
four different transmitting queues as a function of the buffer
size B for 8. We only show results for two nodes,
namely, the node with the highest traffic intensity (node 1)
in

Figures

7 and 9, and a representative intermediate node
(node Figures 8 and 10. We also consider only transmitting
queues 1 and 2 (out of C) at each node. Queue 1
at each node is for traffic to be carried on wavelength -1 ,
which is dedicated to receiver 1 (the "hot spot"). Thus, the
amount of traffic received by this queue does not change as
we vary the number of channels, since the first channel is
dedicated to receiver 1. Queue 2 at each node is for traffic
to be carried on wavelength -2 . The amount of traffic received
by this queue will decrease as the number of channels
increases, since channel -2 will be shared by fewer receivers.
The behavior of queue 2 is representative of the behavior of
the other

Figure

7 plots the
PLP\Omega 1;1 (i.e., the PLP at transmitting
queue 1 of node 1) as a function of the buffer size B for
8. As expected, the PLP decreases as the buffer
size increases. For a given buffer size, however, the PLP
changes dramatically and counter to intuition, as the number
C of channels is varied. Specifically, the PLP increases
with C; that is, adding more channels results in worse per-
formance. When B is 10, there is roughly nine orders of
magnitude difference between the PLP for
and three orders of magnitude difference between
As we discussed above, the traffic load of this queue
does not change with C; the queue receives the traffic for
destination 1, which is always 10% of the total traffic generated
at node 1 (see (17)). What does change as C varies
is the service rate of the queue, and this change can help
explain the results in Figure 7. Referring to Figure 6, we
note that when 4, each frame of the schedule is
arrival slots long, and 2. Hence, at most 8 packets
may arrive to this queue during a frame while as many as 2
packets will be serviced. When
indicating a decrease in the service rate of the queue. Simi-
larly, for further decrease in
available service per frame for this queue. This decrease is
the reason behind the sharp increase in PLP with C in Figure
7. Very similar behavior is observed in Figure 8 where we
plot\Omega 8;1 , the PLP at transmitting queue 1 of node 8. The
main difference between Figures 7 and 8 is in the absolute
values values of PLP. The very small PLP numbers
are due to the fact that the amount of traffic entering queue
1 of node 8 (0.004 packets per arrival slot) is significantly
smaller than the traffic entering the same queue of node 1
(0.058 packets per arrival slot - recall that the traffic source
were chosen so that the packet generation rate decreases as
the node index increases). In fact, for buffer sizes
our analysis gave PLP values that
are essentially zero; these values are not plotted in Figure
8 because we believe that they are the result of round-off
errors.

Figures

plot the PLP at transmitting queue 2
of nodes 1 and 8, respectively, against the buffer size. From

Table

3 we note that the traffic received by this
queue decreases from 30% of the overall network traffic when
or 8; this decrease is due to the
fact that 5 receivers share wavelength -2 when
only 3 receivers share it when 8. Thus, the PLP
behavior at this queue will depend not only on the change
in the service rate as C varies, but also on the change in the
amount of traffic received due to addition of new channels.
In

Figure

9, and for a given buffer size, the PLP decreases as
C increases from 4 to 6 (compare to Figure 7). In this case,
the decrease in the traffic arrival rate (from an average rate
of 0.175 to 0.105 packets per arrival slot) more than offsets
the decrease in the service rate that we discussed above. On
the other hand, the PLP values for are less than those
for (transmitting queue 2 of node 8) due
to the fact that the decrease in the offered load (from 0.012
to 0.007 packets per arrival slot) is not substantial enough
to offset the decrease in the service rate; still, this increase
is less severe than the one in Figure 8 where there was no
decrease in the arrival rate. As C increases to 8 there is no
change in the offered traffic for either queue; as expected,
the PLP rises with the decrease in the service rate.
Finally, Figures 11 and 12 plot the PLP at receiving
queues 1 and 8, respectively. Receiving queue 8 is representative
of queues 2 through 16 in that it receives 6% of
the total network traffic (see (17)). Again, the PLP decreases
with increasing buffer size. Also, the lower values of
PLP in

Figure

12 compared to Figure 11 reflect the fact that
only 6% of the total traffic is destined to receiving queue 8,
as opposed to 10% for the hot spot queue 1. What is surprising
in Figures 11 and 12, however, is that, for a given
buffer size, the PLP decreases as the number C of channels
increases. This behavior is in sharp contrast to the one we
observed in the transmitting side case, and can be explained
as follows. First, higher losses at the transmitting queues for
larger values of C means that fewer packets will make it to
the receiving queues, thus losses will be lower at the latter.
But the dominant factor in the PLP behavior in Figures
11 and 12 is the change in the service rate of the receiving
queues as C varies (refer to Figure 6). For 4, as many
as packets may arrive to each receiving queue within a
frame, and 8 packets may be served (i.e., transmitted to the
users). When the number of potential arrivals in a
frame remains at 32, but the frame is 12 arrival slots long,
meaning that up to 12 packets may be served, leading to a
drop in the PLP. Finally, for the number of packets
served in a frame is the same as in but the maximum
number of packets that may arrive becomes only 16,
explaining the dramatic drop in the PLP.
6 Concluding Remarks
In this paper we introduced a model for the media access
control (MAC) layer of optical WDM broadcast-and-select
LANs. The model consists of a queueing network of transmitting
and receiving queues, and a schedule that masks the
transceiver tuning latency. We developed a decomposition
algorithm to obtain the queue-length distributions at the
transmitting and receiving queues of the network. We also
obtained analytic expressions for the packet-loss probability
at the various queues. Finally, we presented a study case
to illustrate the significance of our work in predicting and
explaining the performance of the network in terms of the
packet-loss probability.
Overall, the results presented in this paper indicate that
the performance of a WDM optical network can exhibit behavior
that is counter to intuition, and which may not be
predictable without an accurate analysis. The performance
curves shown also establish that the packet-loss probability
in such an environment depends strongly on the interaction
among the scheduling and load balancing algorithms, the
routing probabilities, and the number of available channels.
Our work has made it possible to investigate the behavior
of optical networks under more realistic assumptions regarding
the traffic sources and the system parameters (e.g., finite
buffer capacities) than was possible before, and it represents
a first step towards a more thorough understanding of net-work
performance in a WDM environment. Our analysis
also suggests that simple slot allocation schemes similar to
the ones used for our study case are not successful in utilizing
the additional capacity provided by an increase in the
number of channels. The specification and evaluation of
more efficient slot allocation schemes should be explored in
future research.



--R

Impact of tuning delay on the performance of bandwidth-limited optical broadcast networks with uniform traffic
Efficient scheduling of nonuniform packet traffic in a WDM/TDM local lightwave network with arbitrary transceiver tuning laten- cies
A media-access protocol for packet-switched wavelength division multiaccess metropolitan area networks



Call admission control schemes: A review.
area traffic: The failure of poisson modeling.
Queueing systems for modelling ATM networks.
Approximate analysis of discrete-time tandem queueing networks with bursty and correleated input traffic and customer loss
Scheduling transmissions in WDM broadcast-and-select networks
Packet scheduling in broadcast WDM networks with arbitrary transceiver tuning latencies.

A performance model for wavelength conversion with non-poisson traffic
Numerical Solutions of Markov Chains.
The MaTPi protocol: Masking tuning times through pipelining in WDM optical networks.
Stochastic Modeling and the Theory of Queues.
Approximate analysis of a discrete-time polling system with bursty arrivals
--TR
Scheduling transmissions in WDM broadcast-and-select networks
area traffic
Packet scheduling in broadcast WDM networks with arbitrary transceiver tuning latencies
Scheduling of multicast traffic in tunable-receiver WDM networks with non-negligible tuning latencies
Queueing systems for modelling ATM networks
Approximate Analysis of a Discrete-Time Polling System with Bursty Arrivals
HiPeR-l
A Performance Model for Wavelength Conversion with Non-Poisson Traffic
markov modulated bernoulli process;discrete-time queueing networks;optical networks;wavelength division multiplexing