Light -Trees: 0pt ica I MuItica st ing for
Improved Performance in Wavelength-Routed Networks
Laxman H. Sahasrabuddhe and Biswanath Mukherjee University of California, Davis
We introduce the concept o f a light-tree in a wavelength-routed optical network. A light-tree is a point-to-multipoint generalizat i o n o f a lightpath. A lightpath is a point-to-point all-optical wavelength channel connecti n g a t r a n s m i t t e r a t a s o u r c e n o d e t o a receiver a t a d e s t i n a t i o n n o d e . L i g h t p a t h communication can significantly reduce the number o f hops (or lightpaths) a packet has t o traverse; and this reduction can, in turn, significantly improve t h e network’s t h r o u g h p u t . We extend the lightpath concept by incorporating an optical multicasting capability at the r o u t i n g nodes i n order t o increase t h e logical connectivity o f t h e n e t w o r k a n d f u r t h e r decrease its hop distance. We refer t o such a point-to-multipoint extension as a light-tree. Light-trees can n o t only provide improved performance f o r unicast traffic, b u t they naturally can better support multicast traffic and broadcast traffic. In this study, w e shall concentrate o n the application and advantages o f light-trees t o unicast and broadcast traffic. We f o r m u l a t e t h e light-tree-based virtual t o p o l o g y design p r o b l e m as an o p t i m i z a t i o n problem w i t h one o f t w o possible objective functions: f o r a given traffic matrix, (i) minimize the network-wide average packet hop distance, or (ii) minimize the t o t a l number o f transceivers i n t h e network. We demonstrate t h a t an o p t i m u m light-tree-based virtual t o p o l o g y has clear advantages over an o p t i m u m lightpath-based virtual t o p o l o g y w i t h respect t o the above t w o objectives.

ABSTRACT

introduce the concept of a in a waveW elength-routed optical(WDM). WDM divides the network which employs wavelength-division multiplexing light-tree tremendous bandwidth of a fiber (up to 50 THz) into many nonoverlapping wavelengths (WDM channels). Each channel can be operated asynchronously and in parallel at any desirable speed (e.g., peak electronic speed of a few gigabits per second). In order to understand how WDM networks differ from legacy networks, it is helpful to classify legacy networks into three generations based on the underlying physical-level technology employed [l, 21. First-generation networks do not employ fiber optic technology in the physical layer; instead, they employ “copper-based’’ or microwave technology. Thus, both transmission and switching of data is performed in the “electronic domain.” Ethernet is an example of a first-generation network. In second-generation networks, “copper links” and microwave links are replaced by optical fibers. Now, although data transmission is performed in the optical domain, switching is still performed in the electronic domain. Fiber distributed data interface (FDDI) is an example of a secondgeneration network. Recall that the available bandwidth in an optical fiber is on the order of 50 THz, while the peak electronic speed is only a few gigabits per second. Thus, secondgeneration networks tap into a very tiny fraction of the available optical fiber bandwidth. On the other hand, thirdgeneration networks (e.g., WDM networks) tap into a much larger fraction of thc tremendous optical fiber bandwidth by dividing it into many nonoverlapping channels, such that each
This work has been supported in part by the National Science Foundation (NSF) under Grant Nos. NCR-9508238 and ANI-9805285, and DARPA Contract Nos. DABT63-92-C-0031 and DAAH04-95-1-0487.

channel operates at peak electronic speed. Hence, it is not surprising that WDM networks are strong favorites for the next-generation Internet (NGI). WDM wide area networks (WANs) employ tunable lasers and filters at access nodes and opticalielectronic switchcs at routing nodcs (Fig. la).l An access node may transmit signals on different wavelengths, which are coupled into the fiber using wavelength multiplexers. An optical signal passing through an optical wavelength-routing switch (WRS) may be routed from an input fiber to an output fiber without undergoing opto-electronic conversion. A l i g h t p a t h is an all-optical channel which may be used to carry circuit-switched traffic, and it may span multiple fiber links. In the absence of wavelength converters,2 a lightpath would occupy the same wavelength on all fiber links through which it passes. This is called the wavelength-continuity constraint. For example, in Fig. la, the lightpath from host CA2 to ho:st NY (shown by a dashed line) must occupy the same wavelength on each link on the path from host CA2 to host NY. A lightpath can create logical (or virtual) neighbors out of nodes that may be geographically far apart in the network. Using lightpath communical ion, a large number of lightpaths may be set up on the network in order to embed a logical (or virtual) topology. Now, a lightpath carries not only the direct traffic between the nodes it interconnects, but also traffic from nodes upstream of the source (including the source) to nodes downstream of the destination (including the destination). A major objective of lightpath communication is to reduce the number of hops (or lightpaths) a packet has to traverse because this reduction can, in turn, significantly improve the network’s throughput [3] Under lightpath communication, the network employs an equal number of transmitters and receivers because each lightHowever, this path operates on a point-to-point basis [4]. approach may not be able to fully utilize all of the wavelengths on all of the fiber links in the network; also, it may not be able to fully exploit all the switching capability of each WRS [5].

1 Each link is bidirectional and consists of a pair offibers carrying information in opposite directions. 2 A wavelength converter is an optical device which changes the wavelength of the optical signal.

0163-6804/99/$10.00 0 1999 IEEE

IEEE Communications Magazine February 1999

(4
L
- - -

(b)

__

-

I

Figure 1. a) NSFNET backbone topology (link labels correspond to propagation delays.); b) virtual links induced by the light-tree consisting of source UT and destination nodes m,NE, and IL.

Thus, we extend the lightpath concept by incorporating an optical multicasting capability. That is, if there is a connection from transmitter A to receiver B on a certain wavelength and there exist free resources (fiber link and the same wavelength) to direct A’s transmission to some other receivers at C and D as well, why not do it? Now, A will have three logical downstream neighbors (B, C, and D) instead of one neighbor earlie r (B). Thus, the logical connectivity of the network is increased by employing more receivers than transmitters, and the hop distance is decreased. We refer to such a point-tomultipoint extension of a lightpath as a light-tree. Since a lighttree is a generalization of a lightpath, the set of light-tree-based virtual topologies is a superset of the set of lightpath-based virtual topologies. Hence, an “optimum” lighttree-based virtual topology is guaranteed to perform better than an “optimum” lightpath-based virtual topology. Note that light-trees not only can provide improved performance for unicast traffic (as outlined above), but naturally better support multicast traffic and broadcast traffic because of their inherent point-to-multipoint nature. In this study, we shall concentrate on the application and advantages of unicast and broadcast traffic only; application to multicast traffic is an ongoing area of study and will be reported at a later date. It should also be noted that optical multicasting (which is used to implement a light-tree) has some improved characteristics over electronic multicasting since “splitting light” is conceptually easier than copying a packet in electronic buffer. What are the corresponding issues in designing WDM optical switches that can support multicasting; how do we design algorithms for setting up the corresponding “light-trees”; and how do we quantify the corresponding performance benefits? Our study will attempt to answer these questions. A related issue which we will not analyze here is how to compensate for power penalties in signal splitting. In summary, a light-tree is a point-to-multipoint all-optical channel which may span multiple fiber links. Hence, a lighttree enables “single-hop” communication between a “source” node and a set of “destination” nodes; thus, a light-tree-based virtual topology can significantlyreduce the hop distance, thereby increasing the network throughput. Figure l a shows a lighttree (thick solid lines) which connects node UT to nodes TX, NE, and IL. Thus, an optical signal transmitted by node UT travels down the light-tree till it reaches node CO, where is it “split” by an “optical splitter” into two copies. One copy of the optical signal is routed to node TX, where it is terminated at a receiver. The other copy of the optical signal is routed towards node NE, where it is again split into two copies. At node NE, one copy of the optical signal is terminated at a receiver, while the other copy is routed towards node IL.3 Finally, a copy of the optical signal reaches node IL, where it is termi-

nated at a receiver. Thus, the “virtual topology” induced by this light-tree consists of three logical links as shown in Fig. l b . The link labels in Fig. l b indicate the fraction of the source node’s traffic destined for the link destination (note that the sum of these labels should be less than unity). We explore new architectures for the next generation of networks employing light-trees for wide-area (nation-wide) coverage. We examine an “optical” wide-area WDM network which utilizes multicast-capable optical switches at routing nodes so that a “highly connected” arbitrary virtual topology can be embedded on a given physical fiber network. We formulate the light-tree-based virtual topology design problem as an optimization problem with one of two possible objective functions. For a given traffic matrix: Minimize the network-wide average packet hop distance. Minimize the total number of transceivers in the network. We consider two types of traffic, unicast and broadcast. For broadcast traffic, we only consider the minimization of the total number of transceivers in the network. We demonstrate that: An optimum “light-tree”-basedvirtual topology has a lower value of average packet hop distance than the average packet hop distance of an optimum “lightpath”based virtual topology. An optimum “light-tree”-based virtual topology requires fewer opto-electronic components than the number of opto-electronic components required by an optimum “lightpath’’-based virtual topology.

AN ILLUSTRATIVE EXAMPLE
Consider the NSFNET backbone topology in Fig. la. The link labels indicate the fraction of the source node’s traffic that is destined for the link destination. The sum of these labels should be less than unity. Store-and-forward packet switching is performed at the network nodes. Consider a packet originating at node UT which is destined for node NE. Let us assume that the packet needs to be switched electronically at node CO. Thus, after a packet is transmitted by its source, it may have to be retransmitted (i.e., forwarded toward its destination) by other intermediate nodes; each such (re)transmission is referred to as an electronic packet hop, or hop for short. If the number of hops a packet encounters is decreased, the total throughput of the network can be increased. Hence, in this study we consider the following two optimization criteria. Given a traffic matrix, do one of the following:
This operation at node NE can also bepe$ormed by a “drop-and-continue” optical device.

68

IEEE Communications Magazine * February 1999

2 layer . l

L

I

Figure 2.Architecture of a wavelength-routed optical etwork and its layered-graphrepresentation. a) Illustrated are: a lightpath on wavelength from node A to node C, and a lightpath on wavelength hz from node A to node F; b ) layered-graphmodel with three

wavelength layers. Minimize the average packet hop distance. Minimize the total number of opto-electronic components that are required in the network. Our mathematical formulation for these optimization problems turns out to be a mixed-integer linear program (MILP). By solving the MILP, we demonstrate that: An optimum light-tree-based virtual topology has a lower value of average packet hop distance than the average packet hop distance of an optimum lightpath-based virtual topology. An optimum light-tree-based virtual topology requires fewer opto-electronic components than the number of opto-electronic components required by an optimum lightpath-based virtual topology. In our approach we consider two kinds of data traffic, unicast and broadcast! Today, a large fraction of the data traffic in computer networks is unicast in nature. A later section examines how to design an optimum light-tree-based virtual topology for a given unicast traffic matrix.5 Efficient delivery of broadcast traffic may be required by a WDM control network. To understand why, let us first consider the wavelength-routed optical network shown in Fig. 2a which may be modeled as a layered graph (Fig. 2b), in which each layer represents a wavelength, and each physical fiber link has a corresponding link on each wavelength layer [6, 71. Wavelength ho layer serves as the control network. For illustration, a broadcast tree is shown as the control network. Now, the switching state of each wavelength-routing switch (WRS) is managed by a controller. Controllers communicate with one another using a control network, either in-band, out-of-band, or in-fiber, out-of-band. I n in-fiber, out-of-band signaling (which we advocate for a WDM WAN), a wavelength layer is dedicated for the control network. For example, in Fig. 2b, the wavelength layer ho may be used for the control network, and controllers may employ multiple light-trees for fast information dissemination among themselves. Moreover, in the We consider only one kind of trafic at a time; thus, we first solve the problemfor only unicust trufic, thenfor only broadcast trafic.
4 5 A unicast trafic matrix is an N x N matrix, where matrix element (s d) correspondsto the trafsiccfromsource s to destination d

future, as multicast6 applications become more and more popular and bandwidth-intensive, there will emerge a pressing need to provide multicast support on WANs. Some multicast applications may have a large destination set which may be spread over a wide geographical area; for example, a live telecast of a popular music concert is one such application. A light-tree-based “broadcast layer” may provide an efficient transport mechanism for such multicast applications. A later section examines how to select an optimum light-tree-based virtual topology for broadcast traffic.7 Let us revisit the NSFNET backbone topology shown in Fig. la. Let us assume that the bit rate of each lightpath is normalized to one unit, and node UT wants to send a certain amount of packet traffic to nodes TX:, NE, and IL. For the purposes of this discussion, it is not important whether this traffic originated at node UT, or is being forwarded by node UT. Now, without loss of generality, let u,s assume that node U T wants to send 0.4 units of traffic to node TX, 0.2 units of traffic to node NE, and 0.3 units of traffic to node IL. Also, let us assume that we are allowed only one free wavelength on the links UT-CO, CO-NE, NE-IIL, and CO-TX. Then, a lightpathbased solution would consist of the following four lightpaths: From UT to CO From CO to NE From CO to TX From NE to IL Thus, the lightpath-based solution (shown in Fig. l a by dashed lines) requires an electronic switch at nodes CO and NE, and a total of eight transceivers (one transmitter and one receiver per lightpath). On the other hand, a light-tree-based solution consists of a single light-tree (shown in Fig. 1 by thick lines), which requires a totall of four transceivers (one transmitter at UT and one receiver per node at TX, NE, and IL) and does not utilize the electironic switch at node CO or NE. Of course, the benefits of employing light-trees do not
6 Multicasting is the ability of un anplication at a node to send a single message to the communication network and have it delivered to multiple recipients at different locations.

’ A broadcast tiafic “matrix” an N x 1 vector, where the entry in row i is corresponds to the “broadcast” tiaajyicgenerated by node i

IEEE Communications Magazine February 1999

69

I

I

come for free. First, we need multicast-capable wavelengthrouting switches (MWRS) at every node (or at least at some nodes) in the network (architectures of MWRSs are examined later). Second, we may need more optical amplifiers in the network. The reason we need more amplifieis in the iietwoik is quite obvious: if we make n copies of an optical signal by using one or more optical splitters, the signal power of at least one copy will be less than or equal to l/n timeq the original signal power; thus, more amplifiers may be required to maintain the optical signal power above a certain threshold so that the signal can be detected at their receivers. We believe that by employing a light-tree-based virtual topology, the savings obtained by reducing the number of transceivers and electronic switches will significantly offset the “extra” costs of implementing a light tree based virtual topology.

I

II ji

1-

P2

~

Divider 1
“2

I I-

L

L ---.[ tr... ,l.-. Er-- 1
Combiner
-c

7 ,,/,*\

kr-

-14

I

I
I
- -

-lj --

__

-- - --

_ .

‘24

_.

I

W Figure 3. Linear divide?-combiner. we use a1 = 0, a2 = 1, a3 = 0, and a4 = 1. To multicast the signal on input port 1 (i.e., to multicast PI1 to both output ports), we use al = 0.5, a3 = 0, and a4 = 0. In this example the value o f aZis inconsequential. Thus, multicasting is an inherent capability of an LDC.
AN MWRS BASED A S P L l n E R BANK ON We propose to implement multicasting in a WRS by using optical splitters. An optical splitter splits the input signal into multiple identical output signals. Since an optical splitter is a passive device, thc powcr from at least one output signal of an n-way optical splitter is less than or equal to l / n times the input power. To be detected, the optical signal power needs to be more than a threshold, and hence an optical network with multicast-capable optical switch may require a larger number of optical amplifiers. Figure 4 shows a 2 x 2 multicast-capable wavelength-routing switch (MWRS), which can support four wavelengths on each fibcr link. Thc information on each incoming link is first demultiplexed (demux) into separate wavelengths, each carrying a different signal. Then the separate signals, each on separate wavelengths, are switched by the optical switch (OSW). Signals that do not need duplication are sent directly to ports corresponding to their output links, while those signals which need to be duplicated are sent to a port connected to a splitter bank. The splitter bank may be enhanced to provide optical signal amplification, wavelength conversion, and signal regeneration for “multicast”as w l as “unicast”sig el nals. For example, in Fig. 4 wavelength 1 is a unicast signal, , and is a multicast signal. The output of the splitter is connected to a smaller optical switch, which routes the different copies of a signal to their respective outp i t links. Note that this architecture is not much different from the proposed blux architecture of a wavelength-convertible WRS [6], cxcept that the wavelcngth converter bank in [6] is now replaced by a power-splitter bank. Although the LDC switch architecture was presented earlier for completeness, the rest of this work will be based on using the MWRS as the multicasting facility in a wavelength-routed optical network.

MULTICAST ARCHITECTURES SWITCH
This section examines various switch architectures which have multicasting capability. First, we present a WDM network architecture (called a linear lightwave network [SI) which is based on a linear divider-combiner. Then we sludy a new switch architecture which can be implcmentcd by employing “off-the-shelf” optical components.

LINEARDIVIDER-COMBINER In 181, the author proposed a network architecture called a linear lightwave network (LLN), which has wavelength-insensitive multicasting capability. In this architecture, each node has a linear divider-combiner (LDC). Figure 3 shows an LDC with two input fibers (the Pis), two output fibers (the Pas), two dividers, two combiners, and four control signals (the a,s). A larger LDC will have more than two dividers and two combiners. The LDC acts as a generalized optical switch with the added functions of multicasting (signal dividing) and multiplexing (signal combining). In Fig. 3, the values of a l , a2, a3, and a4 (each of which can be varied independently and electronically between 0 and 1) control the pxoportion of the input power that can be sent to the output links. Let P! and P: be the power on the input links, and let PJ and P: be the output powers. Then, PJ = 1 a l ) (1 - a3)P: (1 - az)a3P: and P? = al(1 - a4)P, f a2a4P:. For example, to operate the LDC in the bar state

+

i-

r---l

Demux

- - ---__ r---7,

I

LiG HT-TREE: PROBLEM s FORMULATIONS
UNICAST TRAFFIC: THEGENERAL STATEMENT PROBLEM
----

I

-

-

-

p

-

-

-

-

p

p

p

p

-

-

-

_

I

Figure 4. multicast-capable wavelength-routing switch A

The problem of embedding a desired virtual topology on a given physical topology (fiber network) is formally stated below. Here, we state the problem for unicast traffic; the problem for broadcast traffic

70

IEEE CommunicationsMagazine February 1999

I
!

Lightpath solution

Transceivers

Wavelengths

5

1.48 11.42

1.38 (1.32

6
Light-tree solution Transceivers

1 1.30
8

1.38

I

Wavelengths

!
I I
4

I

4
1.23 1.21 1.19

6
1.13 1.12 1.09

virtual topology, a link between nodes i and j corresponds to a light-tree rooted at node i with node] as one of the “leaves” on the light-tree. (Noting that each such link of the virtual topology may be routed over one of several possible paths o n the physical topology, a n important design issue is “optimal routing” of all lighttrees so that the constraint on having a limited number of wavelengths per fiber is satisfied.)

1
~

1.08

I

5
6

1-07
1.07

i

UNICAST TRAFFIC: FORMULATIONOF THIE OPTIMIZATION PROBLEM
By extending the work in [5, 91, we formulate the problem of finding an optimum lightpath-based virtual topology as an optimization problem, using principles of multicommodity flow for routing of light-trees on the physical topology and for routing of packets on the virtual topology. The detailed formulation of the problem can be found in [lo], and it turns out to be an MILP. Below, we only provide an intuitive descrip, tion of the formulation.

I

- - _ - _ U Table 1. Averagepacket hop distance for lightpath-based and

light-tree-basedvirtual topologies.

I

Random
I
. .

1104
-

I102

I- Broadcast to neighbors 170 -

Table 2. The number of transceiversrequired by lighpath-based and light-tree-basedvirtual topologiesfor diffeerent trafic matrices.

1

54-

-

-

1

Optimization Criterion -- Minimize one of the two objective functions: Average packet hop distance Total number of transceivers required in the network Constraints - We divide the problem’s constraints into three categories as follows: Constraints arising from a limited number transceivers per node: A virtual topology is embedded on a physical topology by employing a set of light-trees, and each light-tree employs one transmitter at the source node and one or more receivers at the destination nodes. Thus, only those virtual topologies are possible that can be embedded by employing the available number of transceivers at each node. For example, if a node has only two transmitters, then at most two light-trees can originate at the node. Constraints arising from a limited number of wavelengths: Given a set of light-trees, we need to route and assign a wavelength to each of them. In the absence of wavelength converters, we also need to ensure that all the links belonging to a light-tree are assigned the same wavelength.9 Constraints arising from the limited bandwidth of a lighttree (multicommodity flow equations): In the network, the traffic from a source to a destination is treated as a unique “commodity.” Now, for a given traffic matrix and virtual topology, the multicommodity flow equations ensure that the packet routing strategy is “sound,” that is, for every (source, destination) pair, (1) the traffic leaving the source is routed to the destination, and (2) the total amount of traffic transmitted on a light-tree is less than the bandwidth of the light-tree.

can be stated in a similar fashion and is tackled later. We are given the following inputs to the problem: A physical topology Gp = (V,Ep) consisting of a weighted undirected graph, where V i s the set of network nodes, and Ep is the set of links connecting the ngdes. Undirected means that each link in the physical topology is bidirectional. Nodes correspond to network nodes (packet switches), and links correspond to the fibers between nodes; since links are undirected, each link may consist of two fibers or channels multiplexed (using any suitable mechanism) on the same fiber. Links a r e assigned weights, which may correspond to physical distances between nodes. A network node i is assumed to be equipped with a D J i ) x Dp(i) WRS, where Dp(i), the physical degree of node i, equals the number of physical fiber links emanating out of (as well as terminating at) node -. i.8 . ” . . . . .. . 1 he number of wavelength channels carried by each liber
=

w.

An N x N traffic matrix, where N is the number of network

nodes and the (i,j)th element is the average rate of traffic flow from node i to node j. Note that the traffic flows may be asymmetric, that is, flow from node i to node j may be different from the flow from node j to node i. The number of wavelength-tunable lasers (transmitters) ( T J and wavelength-tunable filters (receivers) (R,) at each node. Our goal is to determine the following. A virtual topology G, = (V,E,) as another graph where the out-degree of a node is the number of transmitters at that node and the in-degree of a node is the number of receivers at that node. The nodes of the virtual topology correspond to the nodes in the physical topology. In the
8 Note

BROADCAST TRAFFIC: FORMULATION THE OPTIMIZATION PRQBLEM OF

The general framework of the formulation for broadcast traffic is similar to that of unicast traffic described earlier. In the broadcast traffic case, each node needs to send data to all the other nodes in the network. Although the formulation pre91n order to make the formulation tractable, the formulation in [IO] assumes that the network has wavelength converters at each node; hence, it does not consider the wavelength-continuiv constraint.

that Dp(i) includes the fiberfs) corresponding to local connections, that is, for attaching an electronic switch to the Mu/RS.

IEEE CommunicationsMagazine February 1999

71

sented here is for the single-wavelength case, it can easily be extended to the multiwavelength case. The main difference in the formulation is in the routing of the broadcast traffic over the virtual topology. An intuitive description of the formulation is as follows.
Optimization Criterion - Minimize the total number of transceivers reauired in the network

- Equations which construct a spanning tree on the virtu-

a1 topology for each node in the network
- Equations which ensure that the total amount of broad-

cast traffic transmitted on a light-tree is less than the bandwidth of the light-tree

NUMERICAL EXAMPLES

This section presents numerical examples of the light treeConstraints - We divide the problem’s constraints into three based optimum virtual topology design problem using the categories, as follows. NSFNET backbone (Fig. l a ) as our physical topology The constraints arising fioni a liniited number transceivers traffic matrx is randomly generated, such that a certain fracper node: same as the unicast case tion F of the traffic is uniformly distributed over the range [0, Constraints arising from a limited number of waveCia] and the remaining traffic is uniformly distributed over lengths: same as the unicast case the range [0, C x Y i a ] ,where C is the light-tree channel Constraints arising from the limited bandwidth of a lightcapacity which is the sdme ds thc rdle dt which a transmitter tree. The equations foi routiiig bioadcast traffic consists can transmit, a is an arbitrary integer which may bc onc or of two parts: greater, and Y denotes the average ratio of traffic intensities between node pairs with high traffic val- - - - - ues and node pairs with low traffic valI I ues I n Table 1 we employ the first I optimization criterion, which is to miniI mize the network-wide average packet I hop distance Table 1 compares the opti__ --- _-- -7- I mal hop distance foi a hghtpath-based virtual topology (obtained from [S, 91) to 1 that for a light-tree-based virtual topology The values shown in the table were I -calculated by taking the average over 10 I I random traffic matrices, obtained with the parameters C = 1250, a = 20,Y = I , I 10, F = 0.7, fi = 0.8, K = 2, and a = 2. I 1 At each node the number of receivers wds thret: times the number oT trdnsmil(a) I ,I tcrs T Lwas varicd from 4 to 6, while W took on values 4, 6, and 8. As expected, the average packet hop distance in a light-tree-based virtual topology is much lower than that in a lightpath-based virtual topology, thereby demonstrating the advantage of using light-trees. In Table 2 we employ the second optimization criterion, which minimizes the I total number of transceivcrs (opto-clectronic components) required to construct the virtual topology Table 2 compares I the number of transceivers required in a light-tree-based virtual topology with the I number required in a Iightpath-based vir-_ I tual topology. It is interesting to note I - --that if we use rdndom trdffic matrices as ,’ ? ‘ .--_>-__ explained in the previous paragraph, the 4- number of transceivers required by a light-tree-based Solution is only a little lower than that required by a hghtpathI based solution. On the other hand, if we use an “ordered” (i.e., non-random) traf, fic matrix, the number of transceivers required in a light-tree-based solution i i may be significantly less. For example, --->, .. -_.. -- ,I (4 1 consider the following traffic matrix: every node send? a fixed amount of data to its physical neighbors and does not Figure 5. a ) A light-peeee-based solution on a single wavelength for implementing a “broadcastlayer” which consists of 21 transmitters (and hence 21 light-trees) and 35 send any data to any other node in the network (This kind of traffic matrur may receivers, b) virtual topology of the “broadcast layer.”Each node broadcasts Its inforresult from a network control layer which mation over a spanning tree on the “broadcast layer”; c) a spanning tree on the virtual periodically “broadcasts” its “state” to its topology which is rooted at node WA.

.-_ --.-. -

-_-/

- \ _

__

I’

, ’

r

1

I

_-- . ._
/-

/-

--

.-.-.

’

72

IEEE Communications Magazine February 1999

-

physical neighbors.) Then, for such a “broadcast-to-neighbors” traffic matrix, a light-tree-based solution requires significantly fewer transceivers. For example, let C = 1250 and p = 0.8, and let each node in Fig. l a send 250 units of data to each of its neighbors. Then, by solving the MILP, we find that the number of transceivers required by a lightpath-based solution is 70, while the number of transceivers required by a lighttree-based solution is 54, of which 21 are transmitters and 33 are receivers. Next, we demonstrate that by employing light-trees, we can significantly reduce the number of transceivers in the network for routing broadcast traffic. In this example, C = 1250, f3 = 0.8, and each node broadcasts 100 units of trafficlo Such a traffic pattern may be generated by a WDM control protocol which requires each node to periodically broadcast update messages. A complete physical topology embedding (i.e., a transmitter-receiver pair for every fiber link) will require 84 transceivers,while a light-tree-based solution, shown in Fig. 5b, requires only 56 transceivers, of which 21 are transmitters and the remaining 35 are receivers.1l Figure 5b shows 21 lighttrees (one light-tree per transmitter) of which nine are lightpaths (i.e., nine light-trees have one receiver, 10 light-trees have two receivers, and two light-trees have three receivers). Note that most of the light-trces connect a nodc to its immediate neighbors in the physical topology, with an exception being the light-tree from WA to (CA1,TX). The resulting virtual topology is shown in Fig. 5b, and Fig. 5c shows a spanning tree on the virtual topology rooted at node WA.

lower value of average packet hop distance than that of an optimum ‘‘lightpath’’-based virtual topology. An optimum “light-tree”-based virtual topology requires fewer opto-electronic components than does an optimum “lightpath”-based virtual topology We also find that by employing a set of light-trees, we can build a “broadcast layer” which uses significantly fewer transceivers than an equivalent lightpath-based topology.

REFERENCES
[ I ] P. E Green, Jr , Fiber Optic Networks, Englewood Cliffs, NJ: Prentice
Hall, 1993 (21 B. Mukherjee, Optical Communication Networks, New York: McGrawHill, 1997 [31 B Mukherjee et al., “Some principles for designing a wide-area optical network,” IEEUACM Trans Networking, vol. 4, Oct 1996, pp. 684-96. [41 I Chlamtac, A. Ganz, and G Karmi, ”Lightpath communications An approach to highbandwidth optical WAN’S,” /E€€ Trans Commun , vol 40, July 1992, pp 1171-82 [5] D. Banerjee and B Mukherjee, “Wavelength-routed optical networks: Linear formuLation, resource budgeting tradeoffs, and a reconfiguration study,” froc /€€E INFOCOM ’97, Kobe, Japan, Apr. 1997. 161 K.-C. Lee and V 0 K. Li, “A wavelength convertible optical network,” lE€EIOSA J Lightwave Tech , vol. 1 1, May/June 1993, pp 962-70 [71 C Chen and 5 Banerjee. “A new model for optimal routing and wavelength assignment in wavelength division multiplexed optical networks,” froc /€€E /NFOCOM ’96, San Francisco, CA, Mar. 1996, pp. 164-71 [8] K Bala, “Routing in Linear Lightwave Networks,“ PhD thesis, Columbia Univ , 1993 [9] D Banerjee, ”Design and Analysis of Wavelength-Routed Optical Networks,” Ph.D. thesis, U C Davis, 1996. [I 01 L H. Sahasrabuddhe and B Mukherjee, “Light-trees Exploiting optical multicasting tu improve the performance of unicast and broadcast traffic in wavelenght-routed optical networks,” Tech Rep CSE-98-6, U C Davis, Aug 1998.

CONCLUSION
We introduce the concept of a light-tree. We propose a multicast-capable wavelength-routing switch architecture in order to support a light-tree on a WDM wavelength-routed network. We formulate the light-tree-based virtual topology design as an optimization problem with one of two possible objective functions. For a given traffic matrix: Minimize the network-wide average packet hop distance. Minimize the total number of transceivers in the network. We consider two types of traffic, unicast and broadcast. We demonstrate that: An optimum “light-tree”-based virtual topology has a lo Although we assume that each node broadcasts the same amount of trafj?c, the problem fonnulation does not require the broadcast traflc generated at each node to be the same.

BIOGRAPHIES
LAXMAN SAHASFABUDOHE(sahasrab@cs ucdavis.edu) received a B.Tech. (Hons) degree from the Indian Institute of Technology, Kanpur, in 1992, and an M Tech. degree from the Indian Institute of Technology, Madras, in 1994 He is currently a research assistant with the Networks Research Laboratory at the University of California, Davis, where he is working toward a eh.D. degree. His research interests include architectures and protocols for WDM local-area and wide-area optical networks

if the amount of broadcast trufjic is very low, just one light-treeper (source) node would have sufficed; in this example, however, 100 units of broadcast trafficper node tend to fill up the capacities of some transmitters (virtual links), so more light-trees are needed.

11 We remark that

BISWANATHMUKHEWEE (mukherjee@cs.ucdavis.edu) received a B.Tech. (Hons) degree from lndidn Institute of Te Ph.D. degree from the University of Washington he held a GTE Teachi Foundation Fellowship In July 1987 he joined the Univer Davis, where he has been professor of computer science since July 1995, and chair of computer science since September 1997. He IS co-winner of paper awards presented at the 1991 and the 1994 National Security Conferences He serves on the editorial boards of /€€€/A actions on Networking, /E€€ Network, ACMIBaltzer Wireless In Networks (WINET), Journal of High-speed Networks, and Photonic Network communications He served as Technical Program ‘96. He i s author of the textbook Optical Corn (McGraw-Hill, 1997). His research interests include I work security, and wireless networks.

IEEE Communications Magazine Februaly 1999

73