Below are the project's

**Graduate Research Assistants**

- Sandeep Nalakonda, MS Summer 1998, "Architectures for optical WDM networks: performance analysis."
- Tao Lin, MS, Fall 1999, "Wavelength division multiplexed (WDM) network with minimal transmitters and receivers."
- Ashutosh Gore, MS, Spring 2000, "Lightpath rearrangement in WDM networks."
- Seemant Choudhury, MS, Spring 2000, "Routing and dynamic traffic on wavelength routed networks."
- Ishwinder Singh, MS, Summer 2001, "Algorithms for bandwidth efficient protection in optical networks."
- Qi Deng, MS expected graduation date Summer 2002. She is studying design algorithms for survivable IP over WDM networks.
- Ramesh Kandula, MS expected graduation date Summer 2002. He is working on using bridge-and-roll migration to optimize bandwidth. He is also investigating optimal or near optimal topologies to minimize cost in tribuary traffic grooming.

Limited wavelength conversion can model real restrictions on
conversion devices. For example, wavelength conversion by *four wave
mixing* leads to wavelength shifting within a range of wavelengths.
If the wavelength conversion is done by
(optical-electrical-optical) O-E-O components then the limitation may
be due to constraints on the fan-out/fan-in of the components.
At any rate, we are interested in quantifying how wavelength shifting is
related to efficient utilization of optical bandwidth in a fiber.

We provided a measure of wavelength conversion called the
*channel degree* (or *wavelength degree*). If
a network node has a channel degree
*d* then a wavelength may shift to any one of a pre-defined
set of wavelengths, where the set has size at most *d*.
Thus, if a node had no wavelength conversion then its value of
*d* = 1 because the wavelength passes through without
being shifted. If a node has full wavelength conversion capability
then its value of *d* = *W*, where *W* is the number
of wavelengths.

Our aim was to study how wavelength conversion is related to
the bandwidth efficiency of a network. In addition, we were able
to identify network architectures that had small amounts of
wavelength conversion but were very bandwidth efficient. Our
objective was to derive mathematical results, and in particular
guarantees on performance. This lead us to use non-statistical
traffic models so that we could derive such performance guarantees.
The traffic models have a parameter *Rmax*,
which is the maximum traffic load on each fiber-link.
More specifically,
the amount of offered lightpaths to any link at any time is assumed
to be at most *Rmax*. Note that an offered lightpath
may be *blocked* from being set up in the network if
the network has no free wavelengths or cannot crossconnect
free wavelengths due to limitations on wavelength conversion.

We had two traffic models: *off-line* and *dynamic*.
Off-line corresponds to the scenario when the network is initially empty and
then all the lightpath traffic arrives at one time. Dynamic means
that lightpaths may arrive and depart at arbitrary times.
A network is said to be *nonblocking* for off-line
traffic if it does not block any offered lightpaths for any
such traffic. Similarly, a network is *nonblocking*
for dynamic traffic if it does not block any offered lightpaths
for any such traffic. In the case of dynamic traffic, we refer to
a nonblocking network to be *wide sense* nonblocking if
it does not rearrange any existing lightpaths. Note that
if a network is nonblocking for off-line traffic then it is
nonblocking for dynamic traffic with the same *Rmax* if it is allowed
to rearrange its existing lightpaths to make way for a new one.
Such networks are referred to as *rearrangeably* nonblocking
for dynamic traffic.

Note that dynamic traffic is a more realistic model of traffic. In addition, wide sense nonblocking networks are more practical because in real telecommunication networks, connections are rarely rearranged. The exceptions are usually for maintanence, e.g., replacing a faulty switch or link. However, we consider rearrangeably nonblocking networks because they use significantly less resources, as we shall see. Therefore, rearrangement of connections may be become practical when users are very cost sensitive, as it can be with Internet users.

Note that any network that has less than *Rmax* wavelengths
may suffer lightpath blocking and cannot be nonblocking. Also note
that a network with full conversion at every node and exactly *Rmax*
wavelengths will be nonblocking for both off-line and dynamic
traffic. Thus, full conversion at every node achieves the highest
bandwidth utilization. A theoretical issue that we addressed is
how efficent can a network be with a small channel degree. In particular,
if a network has a small channel degree,
how much larger does the number of wavelengths *W* have to be over
*Rmax* and still remain nonblocking.

Next we present our nonblocking network results for off-line traffic. The network topologies we focused on are rings because telecommunication fiber layouts are often rings for SONET. Then we present our results for dynamic traffic. Finally, we explain the other results of this project.

**2.1. OFF-LINE TRAFFIC**

**R. Ramaswami and G. Sasaki, "Multiwavelength optical networks with
limited wavelength conversion," IEEE/ACM Transactions Networking, vol. 6,
no. 6, pp. 744-754, Dec. 1998. Also appeared in Infocom 1997.**

*Summary*: We investigated
nonblocking networks for off-line traffic
with an emphasis on ring topologies. The off-line lightpath
traffic were assumed to have pre-compted routes. Thus, arriving
lightpaths only require a wavelength assignment, i.e., the wavelengths
they should use along the route.

We found ring network architectures that were very bandwidth
efficient and required very little channel degree. One of the
architectures had channel degree *d*=2 at two nodes and no conversion
at all other nodes. It is nonblocking if the number of wavelengths
*W* = *Rmax*, i.e., it has the highest bandwidth efficiency.
There is another architecture
with channel degree *d*=5 at one node and no conversion at all
other nodes. It is also nonblocking if *W* = *Rmax*.

For a ring network, we were able to show that if the channel degree
*d* = 1 at all nodes then a nonblocking network requires
*W* > *Rmax*. This provides a lower bound on the
amount of wavelengths required for a nonblocking network with
very limited wavelength conversion. We found a ring network
that showed that the bound is tight. The ring network has no
conversion at all other nodes except one, which also has
*d* = 1. The ring network is nonblocking if
*W* = *Rmax* + 1.

We also have some results for networks with other topologies.
For a star topology, there is a nonblocking network with channel
degree *d* = 1 and *W * = *Rmax*. For
arbitrary topology networks, there is a nonblocking
network with channel degree *d* = 1 and *W*
= *Rmax* as long as the lightpaths have length at most
2 hops. If the lightpaths have no restrictions on their
path lengths then we have a nonblocking network with
a mix of full conversion nodes and nodes with *d* = 1.
However, each node with *d* = 1 must have all of
its neighbors be full conversion nodes.

**2.2. DYNAMIC TRAFFIC**

**
O. Gerstel, S. Kutten, R. Ramaswami, and G. Sasaki,
"Worst-case analysis of dynamic wavelength allocation in optical networks,"
IEEE/ACM Transactions Networking, vol. 7, no. 6, pp. 8333-8456, Dec. 1999. **

*Summary*: We investigated dynamic traffic for wide-sense
nonblocking networks with limited or no wavelength conversion. The
lightpath traffic was assumed to have pre-computed routes.
We will first present results for networks with no conversion, and
then present results for networks with limited conversion.

For no conversion networks, our results are for ring and tree topologies.
For ring networks, we showed that
a wide-sense nonblocking network requires at least
(1/2)*Rmax* log *N* wavelengths, where *log* is
log base 2 and *N* is the number of nodes. Note that
the wavelength requirement (i.e., bandwidth inefficiency) increases
with the number of nodes. We also showed that for a ring with
no conversion, a nonblocking network requires approximately
*Rmax* log*N* + *Rmax* wavelengths. This
result assumes a particular strategy to assign lightpaths to
wavelengths which may not work well for "typical" traffic. A particular
strategy that does work well for typical traffic is *first fit*,
which is to use the lowest numbered available wavelength.
We showed that for first fit the number of wavelengths for
a nonblocking network is approximately 2.52*Rmax*log *N*
+ 5*Rmax* wavelengths. Thus, in the worst case, it is
a constant factor from the lower bound.

We also have similar results for tree topologies, excluding the first fit results.

Turning back to ring networks, we
found wide-sense nonblocking networks that have wavelength
requirements that do not grow with *N* at the
expense ov a small amount of wavelength conversion.
The network architecture has
channel degree *d* = 2 and the required number of
wavelengths is *Rmax* log (log *Rmax*) + 4 *Rmax*.
Note that the wavelength requirement is growing slightly faster
than O(*Rmax*).

For general topologies, we have results for networks with a sufficiently
large number of wavelengths *W* and channel degree *d*.
The channel degree *d* may be large but
fixed (i.e., not growing) with *Rmax* or
*N*. In addition, for the network, *W* is O(*Rmax*).
In particular, there is a constant *a* such that
*W* = *a* x *Rmax*. Thus, the wavelength
conversion is limited in the sense that *d* is
O(1) with respect to *W* and *Rmax*.

The network is wide-sense nonblocking. The allowable wavelength
shifting at nodes has a pattern that is defined using "expander"
graphs. Thus, the channel degree *d* is
O(1) with respect to W and *Rmax*, and
*W* is O(*Rmax*). Note that this is
an improvement over the other ring architectures, which
have their wavelength requirements growing faster than
O(*Rmax*) or growing with *N*. However,
*d* is a big constant, and so the result is
only of theoretical importance for now.

We also considered dynamic traffic that never departs, which
we refer to as *incremental* traffic.
This models lightpaths that carry high capacity traffic, which are
likely to have long durations. For this traffic,
We found ring networks that are wide-sense nonblocking and have
wavelength requirements *W* = max{0, *Rmax*-*d*}.
Note that as *d* increases, the bandwidth efficiency gets
better. In fact, when *d* = *Rmax* then
*W* = *Rmax*, which makes sense because the
network has full wavelength conversion.
When *d*= 1 then *W* = 2 *Rmax* - 1.

Finally, note that the wide-sense nonblocking ring networks above that
have limited wavelength conversion have wavelength requirements
that are much larger than *Rmax*. This should be compared
to the wavelength requirements for the nonblocking ring networks for
off-line traffic. The requirements are *Rmax*, which is
necessary for any nonblocking network. These networks are also
rearrangeably nonblocking for dynamic traffic. This illustrates that
rearrangement could considerably improve bandwidth efficiency.

**2.3. OTHER RESULTS**

**T. Lin and G. Sasaki, "Nonblocking WDM networks with fixed-tuned
transmitters and tunable receivers," Proc. 37th Annual Allerton
Conference on Communication, Control, and Computing, Monticello IL,
Sept. 1999, 400-401.
Postscript.
**

*Summary*: The networks considered have limited wavelength
conversion in the following sense. The receivers are tunable but
the transmitters are fixed-tuned. In practical systems, tunable
transmitters are more difficult to build or expensive and so it
is reasonable to investigate systems that have fixed-tuned transmitters.

The networks we considered were rearrangebly nonblocking networks with
fixed-tuned transmitters and tunable receivers. Wavelength shifting at
an intermediate node may be
accomplished by a receiver-transmitter pair that receives a signal at
an arbitrary wavelength, and regenerates it at the wavelength of the
fixed-tuned transmitter. For grid topology networks, if there is just a
single transmitter-receiver pair per node then the number of required
wavelengths is at least (*N*-6)/5, where *N* is the number of nodes. On the
other hand, if there are two transmitter-receiver pairs per node then the
number of required wavelengths is at most 2 sqrt(*N*). Thus, there is a
significant reduction of wavelengths by slightly increasing the number of
transmitters and receivers per node.

**G. Sasaki, C.-F. Su, D. Blight, "Simple layout algorithms to
maintain network connectivity under faults," Proc. 38th Annual Allerton
Conf. on Communication, Control and Computing, Sept., 2000.
PDF.
**

*Summary*:
A problem of survivable layout of an IP network topology on a WDM
network is considered. The problem is to layout the IP network
so that any fiber-link cut will still leave the network connected.
Simple layout algorithms are given that perform much better than
simple shortest path routing, but have comparable time complexities.

**R. Kandula and G. Sasaki, "Grooming of dynamic tributary
traffic in WDM rings with rearrangements," 39th Allerton Conference,
Monticello IL, Oct. 2001.
PDF.
**

*Summary*: We considered the problem of setting-up traffic connections,
when the traffic is tributary traffic, i.e., sub-wavelength traffic.
The traffic is assumed to be dynamic, i.e., arrives and leaves at
arbitrary times. Thus, it is similar to dynamic lightpath traffic,
because it has bounds on offered traffic per link, but it also has
bounds on the amount of traffic that can terminate at any node.

We studied a particular WDM architecture for ring networks that allows lightpaths to pass through optically. These networks reduce the number of transponders in the network which are a significant contributor to cost. In fact for certain network sizes and uniform traffic, the architecture can lead to a 44% reduction in transponders compared to networks that do not allow optical pass through.

By using *bridge-and-roll* we show that existing connections
can migrate gracefully to make way for new ones, and have the architecture
perform as well as a network that does not allow optical pass through.
We provide bounds on the number of bridge-and-roll needed per
new connection.