055-064.

5117901 3/17/03 3:42 PM Page 55

A review of 1 Background

O
ptical wavelength-division multiplexing (WDM)
is a promising technology to accommodate the
traffic grooming explosive growth of Internet and telecommuni-
cation traffic in wide-area, metro-area, and local-area net-

in WDM optical works. A single optical fiber strand has the potential
bandwidth of 50 THz. Using WDM, this bandwidth can
be divided into multiple non-overlapping frequency or
networks: wavelength channels. Each WDM channel may be oper-
ated at any speed, e.g., peak electronic speed of a few
gigabits per second (Gbps) [1,2]. Currently, commer-
architectures cially available optical fibers can support over a hundred
wavelength channels, each of which can have a transmis-

and challenges sion speed of over a gigabit per second (e.g., OC-48, OC-
192, and OC-768 in the near future).
While a single fiber strand has over a terabit-per-
second bandwidth and a wavelength channel has over a
gigabit-per-second transmission speed, the network may
still be required to support traffic connections at rates
Keyao Zhu that are lower than the full wavelength capacity. The ca-
Biswanath Mukherjee pacity requirement of these low-rate traffic connections
Computer Science Department can vary in range from STS-1 (51.84 Mbps or lower) up
University of California, Davis to full wavelength capacity. In order to save network cost
Davis, CA USA and to improve network performance, it is very important
for the network operator to be able to “groom” the multiple
low-speed traffic connections onto high-capacity circuit
pipes. Grooming is a term used to describe the optimiza-
tion of capacity utilization in transport systems by means
ABSTRACT of cross-connections of conversions between different
The transmission capacity of a link in today’s optical transport systems or layers within the same system [3].
networks has increased significantly due to wavelength- Different multiplexing techniques can be used for
division multiplexing (WDM) technology. The network traffic grooming in different domains of optical WDM
performance is now mainly limited by the processing networks.
capability of the network elements, which are mainly • Space-division multiplexing (SDM) — partitions the
electronic. By efficiently grooming low-speed traffic physical space to increase transport bandwidth, e.g.,
streams onto high-capacity optical channels, it is possi- bundling a set of fibers into a single cable, or using sev-
ble to minimize this electronic processing and eventu- eral cables within a network link [3].
ally increase the network performance. Traffic grooming • Frequency-division multiplexing (FDM) — partitions
is an emerging topic that has been gaining more re- the available frequency spectrum into a set of inde-
search and commercial attention. Most previous re- pendent channels. The use of FDM within an optical
search on traffic grooming is mainly based on the ring network is termed (dense) wavelength-division multi-
network topology. It is expected that there will be much plexing (DWDM or WDM) which enables a given
more interest on the mesh topology suitable for long- fiber to carry traffic on many distinct wavelengths.
haul, wide-area networks. This paper reviews most of WDM divides the optical spectrum into coarser units,
the recent research work on traffic grooming in WDM
ring and mesh networks. Various network and node ar- *This work has been supported by the National Science
chitectures for different traffic-grooming scenarios are Foundation (NSF) under Grant Nos. NCR-9508239 and
compared and discussed. ANI-9805286, and by Sprint Advanced Technology Labo-
ratories (ATL).

Optical Networks Magazine March/April 2003 55

055-064.5117901 3/17/03 3:42 PM Page 56

called wavebands, which are further divided into wave- WDM is mainly used as a point-to-point transmission
length channels [3]. technology. Each wavelength in such a SONET/WDM
• Time-division multiplexing (TDM) — divides the network is operated at OC-N line rate, e.g., N
48. The
bandwidth’s time domain into repeated time-slots of SONET system’s hierarchical TDM schemes allow a
fixed length. Using TDM, multiple signals can share a high-speed OC-N channel to carry multiple OC-M chan-
given wavelength if they are non-overlapping in time [3]. nels (where M is smaller than or equal to N). The ratio of
• Dynamic statistical multiplexing or packet-division N and the smallest value of M carried by the network is
multiplexing (PDM) — provides “virtual circuit” serv- called “grooming ratio”. Electronic add-drop multiplexers
ice in an IP/MPLS over WDM network architecture. (ADMs) are used to add/drop traffic at intermediate nodes
The bandwidth of a WDM channel is shared between to/from the high-speed channels.
multiple IP traffic streams (virtual circuits). In a traditional SONET network, one ADM is
Although most research on traffic-grooming prob- needed for each wavelength at every node to perform traf-
lems in the literature concentrate on efficiently grooming fic add/drop on that particular wavelength. With the
low-speed circuits onto high-capacity WDM channels progress of WDM, over a hundred wavelengths can now
using a TDM approach, the generic grooming idea can be supported simultaneously by a single fiber. It is, there-
be applied to any optical network domain using the vari- fore, too costly to put the same amount of ADMs (each of
ous multiplexing techniques mentioned above. which has a significant cost) at every network node since a
Traffic grooming is composed of a rich set of prob- lot of traffic is only bypassing an intermediate node. With
lems, including network plannar, topology design (based the emerging optical components such as optical add-drop
on static traffic demand), and dynamic circuit provision- multiplexers (O-ADM) (also referred to as wavelength
ing (based on dynamic traffic demand). The traffic- add-drop multiplexers (W-ADM)), it is possible for a node
grooming problem based on static traffic demands is es- to bypass most of wavelength channels optically and only
sentially an optimization problem. It can be seen as a dual drop the wavelengths carrying the traffic destined to the
problem from different perspectives. One perspective is node. A fully optical wavelength circuit between the elec-
that, for a given traffic demand, satisfy all traffic requests tronic components at a node pair is called a “lightpath”.
as well as minimize the total network cost. The dual prob- Compared with the wavelength channel resource,
lem is that, for given resource limitation and traffic de- ADMs form the dominant cost in a SONET/WDM ring
mands, maximize network throughput, i.e., the total network. Hence, carefully arranging these optical bypasses
amount of traffic that is successfully carried by the network. can reduce a large amount of the network cost. Figure 1
In recent years, there has been an increasing amount shows different node architectures in a SONET/WDM
of research activity on the traffic-grooming problem, ring network. It is clear that using O-ADMs can decrease
both in academe and in industry. Researchers are realizing the number of SONET ADMs used in the network and
that traffic grooming is a practical and important prob- eventually bring down the network cost. Then the prob-
lem for WDM network design and implementation. In lems are, for a given low-speed set of traffic demands,
this paper, we review the state of the art of this research, which low-speed demands should be groomed together,
both on SONET ring networks and on arbitrary-topo- which wavelengths should be used to carry the traffic,
logy WDM mesh networks. Various network architectures which wavelengths should be dropped at a local node, and
are presented and discussed. how many ADMs are needed at a particular node?

2 Traffic Grooming in SONET Ring Networks 2.2 Single-hop grooming in SONET/

2.1 Node architecture WDM rings
SONET ring is the most widely used optical net- A SONET/WDM ring network can have the node
work infrastructure today. In a SONET ring network, architecture shown in Fig. 1(b). OC-M low-speed con-

Figure 1: Node architectures in a SONET/WDM ring network.

56 Optical Networks Magazine March/April 2003

055-064.5117901 3/17/03 3:42 PM Page 57

nections are groomed on to OC-N wavelength channels. It has been proven in [4,5] that the general traffic-
Assume that there is no wavelength converter at any net- grooming problem is NP-complete. The authors in [6]
work node. The traffic on a wavelength cannot be formulate the optimization problem as an integer linear
switched to other wavelengths. Based on this network program (ILP). When the network size is small, some
model, for a given traffic matrix, satisfying all the traffic commercial software can be used to solve the ILP equa-
demands as well as minimizing the total number of tions to obtain an optimal solution. The formulation in
ADMs is a network design/optimization problem and has [6] can be applied to both uniform and non-uniform traf-
been studied extensively in the literature. fic demands, as well as to unidirectional and bi-directional
Figures 2 and 3 show an example in which, by care- SONET/WDM ring networks. The limitation of the ILP
fully grooming traffic in the SONET/WDM rings, some approach is that the numbers of variables and equations
network cost savings can be achieved. Figure 2 shows a increase explosively as the size of the network increases.
SONET/WDM ring network with 6 unidirectional The computation complexity makes it hard to be useful
connection requests. Each node is also equipped with an on networks with practical size. By relaxing some of the
O-ADM (not shown in the figures). Assume that the constraints in the ILP formulation, it may be possible to
SONET ring is also unidirectional (clockwise), the capac- get some results, which are close to the optimal solution
ity of each wavelength is OC-N, and it can support two for reasonable-size networks. The results from the ILP
OC-M low-speed traffic requests in TDM fashion, i.e., may give some insights and intuition for the development
N
2M. In order to support all of the traffic requests, of good heuristic algorithms to handle the problem in a
8 ADMs are used in the network. Figure 3(a) shows a large network.
possible configuration. By interchanging the connections In [5,7,8], some lower-bound analysis is given for
(1,3) and (2,3), wavelength 2 (red) can be optically by- different traffic criteria (uniform and non-uniform) and
passed at node 2, which results in one ADM savings at network model (unidirectional ring and bi-directional
node 2. Figure 3(b) shows this configuration. ring). These lower-bound results can be used to evaluate

Figure 2: A SONET/WDM network with 4 nodes and 2 wavelengths.

Figure 3: Two possible configurations to support the traffic requests in Fig. 2.

Optical Networks Magazine March/April 2003 57

055-064.5117901 3/17/03 3:42 PM Page 58

the performance of traffic-grooming heuristic algorithms. 2.4 Dynamic grooming in SONET/WDM

In most of the heuristic approaches, the traffic-grooming ring networks
problem is divided into several sub-problems and solved Instead of using a single static traffic matrix to char-
separately. These heuristics can be found in [4–9]. Greedy acterize the traffic requirement, it is also possible to de-
approach, approximation approach, and simulated an- scribe it by a set of traffic matrices. The traffic pattern
nealing approach are used in these heuristic algorithms. may change within this matrix set over a period of time,
say throughout a day or a month. The network needs to
2.3 Multi-hop grooming in SONET/ be reconfigured when the traffic pattern transits from one
WDM ring matrix to another matrix in the matrix set. The network
In single-hop (a single-lightpath hop) grooming, traf- design problem for supporting any traffic matrix in the
fic cannot be switched between different wavelengths. Fig- matrix set (in a non-blocking manner) as well as mini-
ure 4(a) shows this kind of a network configuration. An- mizing the overall cost is known as a dynamic grooming
other network architecture has been proposed in [8, 10], in problem in a SONET/WDM ring [11].
which there are some nodes equipped with Digital Cross- Unlike the dynamic provisioning and grooming
connects (DXCs). In Fig. 4(b), node 3 has a DXC installed. problem in a WDM mesh network, which will be intro-
This kind of node is called a hub node. Traffic from one duced in Section 3, the dynamic-grooming problem pro-
wavelength/time-slot can be switched to any other wave- posed in [11] is more likely a network design problem with
length/time-slot at the hub node. Because the traffic needs reconfiguration consideration. The authors of [11] have
to be converted from optical to electronic at the hub node formulated the general dynamic-grooming problem in a
when wavelength/time-slot exchange occurs, this groom- SONET/WDM ring as a bipartite graph-matching prob-
ing approach is called multi-hop (multi-lightpath hops) lem and provided several methods to reduce the number
grooming. Depending on the implementation, there can of ADMs. A particular traffic matrix set is then considered
be a single hub node or multiple hub nodes in the network. and the lower bound on the number of ADMs is derived.
A special case is that every node is a hub node, i.e., there is They also provide the necessary and sufficient conditions
a DXC at every node. This kind of network is called point- so that a network can support such a traffic pattern. This
to-point WDM ring network (PPWDM ring) [10]. kind of traffic matrix set is called a t-allowable traffic pat-
The work in [10] provides some excellent theoretical tern. For a given traffic matrix, if each node can source at
analysis on comparing network cost of PPWDM ring, a most t duplex circuits, we call this traffic matrix a t-allow-
SONET/WDM ring without hub node, a SONET/ able traffic matrix. The traffic matrix set, which only con-
WDM ring with one or multiple hub nodes, etc. The au- sist of t-allowable traffic matrices, is called a t-allowable
thors of [6] have compared the single-hop grooming with matrix set or a t-allowable traffic pattern. We use an exam-
multi-hop grooming (with one hub node) network per- ple from [12] to illustrate dynamic traffic grooming for a
formance using simulation. The results indicate that, t-allowable traffic pattern in a SONET/WDM ring.
when the grooming ratio is large, the multi-hop approach Figure 5 shows a 5-node SONET/WDM ring net-
tends to use fewer ADMs, but when the grooming ratio is work. Three wavelengths are supported in the network.
small, the single-hop approach tends to use fewer ADMs, Assume that each wavelength can support 2 low-speed
and in general, the multi-hop approach uses more wave- circuits. The network configuration in Fig. 5 is a 2-allow-
lengths than the single-hop approach. able configuration, i.e., it can support any 2-allowable

Figure 4: SONET/WDM ring with/without a hub node.

58 Optical Networks Magazine March/April 2003

055-064.5117901 3/17/03 3:42 PM Page 59

2.5 Grooming in Interconnected

SONET/WDM rings
Most traffic-grooming studies in SONET/WDM
ring networks have assumed a single-ring network topol-
ogy. The authors of [13] have extended the problem to an
interconnected-ring topology. Today’s backbone networks
are mainly constructed as a network of interconnected
Figure 5: Network design for 2-allowable traffic. rings. Extending the traffic-grooming study from a single-
ring topology to the interconnected-ring topology will be
very useful for a network operator to design their network
and to engineer the network traffic.
traffic matrix (set). For instance, consider a traffic matrix Figure 6(a) shows an interconnected SONET/
with request streams {1–2, 1–3, 2–3, 2–4, 3–4, 4–5, WDM ring network with a single junction node. Multi-
4–5}. The traffic matrix can be supported by assigning ple junction nodes may also exist in the interconnected-
{1–3, 2–3} on red wavelength, assigning {1–2, 2–4, 4–5, ring topology because of network survivability considera-
4–5} on blue wavelength, and assigning {3–4} on green tion. Various architectures can be used at the junction
wavelength. Note that, for a particular traffic matrix, node to interconnect the two SONET rings. Figures 6
there may be some redundant ADMs in the configura- (b)–(d) [13] show some of the node architectures.
tion. However, the configuration is able to support other In Fig. 6(b), an O-ADM is used to drop some wave-
potential t-allowable traffic matrices. Designing such con- lengths at the junction node. ADMs and a DXC are used
figurations to support any t-allowable traffic matrix while to switch the low-speed circuits between the inter-
minimizing the network cost is a very interesting research connected rings. This node architecture has wavelength-
problem. The authors in [11] provide an excellent analysis conversion and time-slot-interchange capability, i.e., a
on t-allowable traffic pattern. The study of dynamic-traffic time slot (low-speed circuit) on one wavelength can be
grooming in a SONET/WDM ring with other generic switched to another time slot on a different wavelength
traffic pattern can be potentially challenging research. through this junction node.

Figure 6: A sample interconnected-ring network topology and simplified architectures of the junction node.

Optical Networks Magazine March/April 2003 59

055-064.5117901 3/17/03 3:42 PM Page 60

Figure 6(c) uses an Optical Crossconnect (OXC) to When such a network is constructed, how to effi-
interconnect the two rings. There are transparent and ciently accommodate the incoming traffic requests is a
opaque technologies to build these OXCs. Transparent network-provisioning problem. The traffic request can be
refers to all-optical switching, and opaque refers to switch- static (measured by one or multiple fixed traffic matri-
ing with optical-electronic-optical (O-E-O) conversion. ces) or dynamic (measured by the arrival rate and the
Depending on the implementation, the OXC may be holding time statistics of a connection request). The work
equipped with or without wavelength- conversion capabil- in [14], based on static traffic demands, discusses the
ity. This node architecture can only switch the traffic at the node architectures in a WDM mesh network, which has
wavelength granularity between the interconnected rings. traffic-grooming capability.
Note that extra ADMs are needed to support local traffic Figure 7 shows such an OXC architecture, which has
originating from or terminating at the junction node. hierarchical switching and multiplexing functionality.
Figure 6(d) shows a hierarchical node architecture Instead of using a separate wavelength-switching system
with a switching capability on both wavelength and and a grooming system (Fig. 6(d)), the OXC in Fig. 7 can
lower-speed circuit granularity. directly support low-speed circuits and groom them onto
The different node architectures at the junction wavelength channels through a grooming fabric (G-Fabric)
nodes in the interconnected-ring network will add differ- and built-in transceiver arrays. This kind of OXC is
ent constraints to the traffic-grooming problem. The named as Grooming OXC (G-OXC) or Wavelength-
work in [13] presented the ILP formulation of the traffic- Grooming Crossconnect (WGXC) [15]. In a network
grooming problem in an interconnected-dual-ring topol- equipped with a G-OXC at every node, the grooming
ogy, and proposed a heuristic algorithm to handle the fabric and the size of the transceiver array provide another
problem for networks of practical size. Results are com- dimension of constraints on the network performance
pared between the various junction nodes’ interconnec- besides the wavelength-resource constraint. This is simi-
tion strategies and grooming ratios. When the number of lar to the ADM constraint for traffic grooming in
rings and the number of junction nodes increase in the SONET/WDM ring networks.
interconnected-ring network, the network topology tends The transceiver array used in the OXC can be either
to become an irregular mesh topology. tunable or fixed. The authors in [14] consider a static traf-
Section 3 discusses some recent studies on traffic fic matrix set as the network traffic demands. Each traffic
grooming on the WDM mesh topology. A comparison matrix in the matrix set represents a particular low-speed
between the interconnected-ring approach and the mesh circuit request class. For given network resource con-
approach will be a potential research challenge and hasn’t straints and traffic demands, the work in [14] studies how
been explored in the literature yet. to maximize the network throughput under the network
resource limitation. As stated in Section 1, minimizing
3 Traffic Grooming in Wavelength-Routed cost and maximizing network throughput lead to two dif-
ferent perspectives on the same traffic-grooming prob-
WDM Mesh Networks
lem. The authors in [14] formulate the problem as an
Most previous work on traffic grooming in the opti-
ILP. A small network is used to show ILP results and two
cal network literature is based on the ring network topol-
heuristic algorithms are proposed to study larger net-
ogy. Recently, traffic grooming in a WDM mesh network
works based on the observations from these results. Dif-
has started to get more attention. In this section, we re-
ferent network scenarios are considered and compared in
view some recent work, which have been reported on this
[14]. They are single-hop grooming vs. multi-hop groom-
subject. We will also show some potential research chal-
lenges and directions.

3.1 Network provisioning: static and

dynamic traffic grooming
Although the SONET (interconnected) ring net-
work has been used as the first generation of the optical
network infrastructure, it has some limitations, which
make it hard to scale and to accommodate the increasing
Internet traffic. The next-generation optical network is
expected to be an intelligent wavelength-routed WDM
mesh network. This network will provide fast and con-
venient (point-and-click) automatic bandwidth provi-
sioning and efficient protection mechanisms; and it will
be based on an irregular mesh topology, which will make
it much easier to scale. Figure 7: An OXC with grooming capability.

60 Optical Networks Magazine March/April 2003

055-064.5117901 3/17/03 3:42 PM Page 61

ing, tunable transceivers vs. fixed transceivers, optimizing carry multiple fiber links. Assume that the cost of a fiber
network throughput vs. optimizing network revenue, etc. going through one conduit is one unit and the capacity of
Unlike the work in [14], the works in [15,16] con- a wavelength channel is OC-48. Five segments exist in Fig.
sider a dynamic traffic pattern in a WDM mesh network. 8(a): (A, B), (A, C), (A, D), (B, C), and (B, D). A segment
The work in [15] has proposed a connection admission is a sequence of fiber links that does not pass through an
control (CAC) scheme to ensure that the network will OXC [17]. There are two possible network design options
treat every connection fairly. It has been observed in [15] to accommodate the traffic demands, which are shown in
that, when most of the network nodes have grooming Figs. 8(b) and 8(c).
capability, the high-speed connection requests will have Option 1 (Fig. 8(b)):
higher blocking probability than the low-speed connection – Place a fiber on segments (A, B), (B, C), and
requests in the absence of any fairness control. CAC is (C, D).
needed to guarantee that every class of connection requests – Install a WDM system on each fiber.
will have similar blocking probability performance. The – Place an OXC with 4 ports at node B to inter-
work in [16] proposed a theoretical capacity-correlation connect the wavelength channels.
model to compute the blocking probability for WDM – There will be a total of 4 OXC ports used at
networks with constrained grooming capability. nodes A, C, and D to add and drop traffic.
The work in [14] has assumed that every node is a Total cost for option 1 will be:
WGXC node, and the grooming capability is constrained
by the grooming fabric and transceiver array at every node. Cost (option 1)
3 unit fiber cost  3
The work in [15] has assumed that only a few of the network WDM systems  8 OXC ports (overall)
nodes are WGXC nodes and there is no constraint on these
The two demands will be carried by the red wave-
nodes. It will be a good extension to combine these assump-
length and blue wavelength shown in Fig. 8(b).
tions and study the network performance as well as fairness
Option 2 (Fig. 8c)):
in a static as well as a dynamic environment. This extension
– Place a fiber on segments (A, C) and (A, D).
will be very practical and important to a service provider.
These fibers will bypass node B.
– Install a WDM system on each fiber.
3.2 Network design and plannar
– There will be a total of 4 OXC ports used at
Unlike the network-provisioning problem addressed
nodes A, C, and D to add and drop traffic.
in Section 3.1, the work in [17] studied how to plan and
Total cost for option 2 will be:
design such a WDM mesh network with certain forecast
traffic demands. The problem is a network design and Cost (option 2)
4 unit fiber cost  2
plannar methodology. The problem description is as fol- WDM systems  4 OXC ports (overall)
lows: given forecast traffic demand (static) and network
node (locations), determine how to connect the nodes The two demands will be carried by the red wave-
using fiber links and OXCs and route the traffic demands lengths shown in Fig. 8(c).
in order to satisfy all of the demands as well as minimize From this example, we can see that each network el-
the network cost. The network cost is measured by the ement has its own cost function and the definitions of
fiber cost, OXC or DXC port cost, and WDM system these cost functions will eventually determine how the
cost used in the network. network should be designed.
Figure 8 (from [17]) gives an example on this network The authors in [17] have addressed this network de-
design and plannar problem considering traffic grooming. sign and plannar problem. The problem is formulated as
Figure 8(a) shows a four-node network and the traffic de- an ILP. Two heuristic algorithms are proposed for the
mands. Each link in Fig. 8(a) is a fiber conduit, which may mesh network design and the ring network design sepa-

Figure 8: Two different designs for a 4-node network [17].

Optical Networks Magazine March/April 2003 61

055-064.5117901 3/17/03 3:42 PM Page 62

rately, i.e., design the network as an irregular mesh topol- cost is determined by the transmission cost and switching
ogy or an interconnected-ring topology. The authors cost in a manner similar to that described in Section 3.2.
compare the results between the mesh design and ring de- The bandwidth requirement of a connection can be a frac-
sign. They find that (a) the mesh topology design has a tion of a wavelength channel and some connections may
compelling cost advantage for sufficiently large distance be partially carried by the electronic network layer. The au-
scales; (b) for ring technologies such as OC-192 BLSR, thors of [18] show how much benefit there will be on net-
using WDM only results in cost savings when distances work cost by grooming the traffic onto the optical domain
are sufficiently large; and (c) costs can be very insensitive instead of carrying them purely on the electronic layer. An
to distance for ring technologies [17]. ILP formulation is given and a simple heuristic is pro-
posed. We believe that it is possible to improve the heuris-
3.3 Grooming with protection requirement tic and its performance presented in [18]. The study of
in WDM mesh networks traffic grooming with protection requirement in a dy-
The SONET/WDM ring networks have been namic environment is a challenge and interesting topic.
proven to have reliable link-protection schemes. There is
no need to consider the protection issue separately for 3.4 Grooming with multicast in WDM
groomed traffic in such a network. On the other hand, mesh networks
protection for groomed traffic should be studied in Multicast applications such as video-on-demand and
WDM mesh networks. interactive games are becoming more and more popular.
In a WDM mesh network, various protection schemes It is reasonable to estimate that there will be more such
can be used depending on the network operator’s preference multipoint applications which may require vast amount
and the customer’s requirements. Either link-protection of bandwidth in the near future such as video conferenc-
scheme or path-protection scheme may be applied on a ing, virtual reality entertainment, etc. Optical multicast-
WDM mesh network, and the protection resources can be ing using “light-tree” [19] may be a good solution for
dedicated or shared by the working circuits. Although these requirements. Since each wavelength will have ca-
WDM protection schemes in mesh networks have been pacity up to OC-192 (OC-768 in the future), multiple
studied extensively, protection with traffic grooming is an multicast sessions can be groomed to share the capacity
open research area and needs to be carefully addressed. on the same wavelength channel. In this case, the light-
Different low-speed circuits may ask for different paths or the light-trees can be established to accommo-
bandwidth requirement as well as protection service re- date multicast requests, which have lower capacity re-
quirement. The low-speed circuits may be protected on quirement than the bandwidth of a wavelength.
either the electronic layer or on the optical layer. Figure 9 Figure 10 shows a simplified switch architecture,
(from [18]) shows an example of path protection in a net- which can support multicast sessions with full wavelength
work with electronic layer and optical layer. In Fig. 9, the capacity requirement or partial wavelength capacity re-
green nodes are the nodes which are equipped with quirement. With this architecture, the data on a wave-
OXCs. Lightpaths can be established between these length channel from one incoming fiber or the local node
nodes, and low-speed connections can be groomed onto can be switched to multiple outgoing fibers, and a full
these lightpaths and transmitted in the optical domain. wavelength channel multicasting session can be main-
Given a static traffic matrix and the protection re- tained as much as possible in the optical domain. The
quirement for every request (no protection, 11 protec- DXC in Fig. 10 has multicast capability. This kind of
tion, m:n protection, etc.), the authors in [18] studied how electronic switch fabric is already commercially available.
to satisfy these connections’ bandwidth and protection re-
quirements while minimizing the network cost. Network

Figure 10: Switch architecture for supporting multicast groom-

Figure 9: A multi-layer protection example [18]. ing [19].

62 Optical Networks Magazine March/April 2003

055-064.5117901 3/17/03 3:42 PM Page 63

By combining this DXC with OE/EO conversion com- route-computation algorithms need to be used under dif-
ponents (electronic mux/demux and transceiver), a low- ferent network states.
speed multicast session can be groomed with other low-
speed unicast/muticast sessions. 4 Conclusion
The work in [20] reports on some preliminary stud- The objective of this paper was to provide an
ies on multicast grooming in WDM mesh networks. The overview of the architectures and the research activity on
problem is defined as follows: given a set of multicast ses- traffic grooming in WDM optical networks. Some prob-
sions with various capacity requirements, satisfy all of the lems on traffic grooming have been well studied (e.g.,
multicast sessions, and at the same time, minimize the grooming in SONET rings), and some are open (e.g.,
network cost. The network cost is measured by the wave- grooming in mesh networks). We expect that there will
length-link cost used in the network. The authors of [20] be more interesting research on this topic.
show an ILP formulation for this problem and present
some results based on some sample traffic matrices and 5 References
network topologies. It is hard to scale the ILP approach [1] B. Mukherjee, Optical Communication Networks,
to handle networks of practical size. Hence, simpler and McGraw-Hill, New York, 1997.
efficient algorithms need to be explored to achieve near- [2] R. Ramaswami and K. N. Sivarajan, Optical Net-
optimal solutions. Multicast with grooming is a new re- works: A Practical Perspective, Morgan Kaufmann
search area and is expected to receive more attention in Publisher Inc., San Francisco, 1998.
the optical networking literature. [3] R. S. Barr and R. A. Patterson, “Grooming Telecom-
munication Networks,” Optical Networks Magazine,
3.5 Protocols and algorithm extensions vol. 2, no. 3, pp. 20-23, May/June 2001.
for WDM network control [4] A. L. Chiu and E. H. Modiano, “Traffic Grooming
Traffic grooming is a very important problem whose in Algorithms for Reducing Electronic Multiplexing
solution will enable us to fully develop an intelligent WDM Costs in WDM Ring Networks,” IEEE/OSA Journal
optical transport network. The unified control plane of of Lightwave Technology, vol. 18, no. 1, pp. 2-12,
such a network is being standardized, and is known as Gen- January 2000.
eralized Multi-Protocol Label Switching (GMPLS) [21] in [5] P. J. Wan, G. Calinescu, L. Liu, and O. Frieder,
the Internet Engineering Task Force (IETF) forum. The “Grooming of Arbitrary Traffic in SONET/WDM
purpose of this network control plane is to provide an intel- BLSRs,” IEEE Journal on Selected Areas in Communi-
ligent, automatic, end-to-end circuit (virtual circuit) provi- cations, vol. 18, no. 10, pp. 1995-2003, Oct. 2000.
sioning/signaling scheme throughout the different network [6] J. Wang, V. R. Vemuri, W. Cho, and B. Mukherjee,
domains. Different multiplexing techniques such as PDM, “Improved Approaches for Cost-effective Traffic
TDM, WDM, and SDM may be used for such an end-to- Grooming in WDM Ring Networks: ILP Formula-
end circuit, and good grooming schemes are needed to effi- tions and Single-hop and Multihop Connections,”
ciently allocate network resources. IEEE/OSA Journal of Lightwave Technology, vol. 19,
There are three components in the control plane no. 11, pp. 1645-1653, Nov. 2001.
that need to be carefully designed to support traffic [7] X. Zhang and C. Qiao, “An Effective and Compre-
grooming, namely, resource-discovery protocol, signaling hensive Approach for Traffic Grooming and Wave-
protocol, and path-computation algorithms. Several re- length Assignment in SONET/WDM Rings,” IEEE/
source discovery protocols based on traffic engineering ACM Transactions on Networking, vol. 8, no. 5,
(TE) extensions of link-state protocols (OSPF, IS-IS) pp. 608-617, Oct. 2000.
[22–24] and link-management protocols [25] have been [8] J. M. Simmons, E. L. Goldstein, and A. A. M. Saleh,
proposed in IETF as the resource-discovery component “Quantifying the Benefit of Wavelength Add-Drop
in the control plane. The extensions of the MPLS signal- in WDM Rings with Distance-Independent and
ing protocols are proposed as the signaling protocol in Dependent Traffic,” IEEE/OSA Journal of Lightwave
this control plane. An open issue is the design of efficient Technology, vol. 17, no. 1, pp. 48-57, January 1999.
route-computation algorithms. The work in [26,27] has [9] O. Gerstel, P. Lin, and G. Sasaki, “Wavelength
reported some preliminary result on on-line schemes to Assignment in a WDM Ring to Minimize Cost of
provision connections with different bandwidth granu- embedded SONET Rings,” Proc., IEEE INFOCOM
larities (i.e., dynamic traffic grooming) in WDM mesh ’98, San Francisco, CA, pp. 94-101, March 1998.
networks, which employ the GMPLS distributed control [10] O. Gerstel, R. Ramaswami, and G. H. Sasaki,
plane. Various grooming policies have been proposed. A “Cost-Effective Traffic Grooming in WDM Rings,”
grooming policy reflects the intension of a network oper- IEEE/ACM Transaction on Networking, vol. 8, no. 5,
ator on how to engineer network traffic. It has been pp. 618-630, Oct. 2000.
shown that, in order to achieve good performance in a [11] R. Berry and E. Modiano, “Reducing Electronic
dynamic environment, different grooming polices and Multiplexing Costs in SONET/WDM Rings with

Optical Networks Magazine March/April 2003 63

055-064.5117901 3/17/03 3:42 PM Page 64

Dynamically Changing Traffic,” IEEE Journal on http://search.ietf.org/internet-rafts/draft-gasparini-

Selected Areas in Communications, vol. 18, no. 10, ccamp-gmpls-g709-ospf-isis-00.txt., Nov. 2001.
pp. 1961-1971, Oct. 2000. [25] J. P. Lang, et al., “Link Management Protocol
[12] E. Modiano and P. J. Lin, “Traffic Grooming in (LMP),” http://search.ietf.org/internet -drafts/draft-
WDM Networks,” IEEE Communications Maga- ietf-ccamp-lmp-02.txt, Nov. 2001.
zine, vol. 39, no. 7, pp. 124-129, July 2001. [26] K. Zhu and B. Mukherjee, “Dynamic Traffic
[13] J. Wang and B. Mukherjee, “Interconnected WDM Grooming in Optical WDM Mesh Networks With
Ring Networks: Strategies for Interconnection and Distributed Control,” Proc , SPIE APOC ’01, Bei-
Traffic Grooming,” Optical Networks Magazine, to jing, China, Nov. 2001.
appear 2002. [27] K. Zhu and B. Mukherjee, “On-Line Approaches
[14] K. Zhu and B. Mukherjee, “Traffic Grooming in an for Provisioning Connections of Different Band-
Optical WDM Mesh Network,” IEEE Journal on width Granularities in WDM Mesh Networks,”
Selected Areas in Communications, vol. 20, no 1., Proc., IEEE OFC ’02, Anaheim, CA, March 2002.
pp. 122-133, Jan. 2002.
[15] S. Thiagarajan and A. K. Somani, “Capacity Fair-
ness of WDM Networks with Grooming Capabili- Keyao Zhu
ties,” Optical Networks Magazine, vol. 2, no. 3, Computer Science Department
pp. 24-31, May/June 2001. University of California, Davis
[16] S. Thiagarajan and A. K. Somani, “A Capacity Cor- Davis, CA 95616
relation Model for WDM Networks with Con- [email protected]
strained Grooming Capabilities,” Proc., IEEE ICC Keyao Zhu received the B.S. degree from
’01, Helsinki, Finland, June 2001. Peking University, Beijing (China) in 1998
and the M.S. degree from the University of
[17] L. A. Cox and J. Sanchez, “Cost Savings from
California, Davis (USA), in July 2000. Currently, he is a Ph.D.
Optimized Packing and Grooming of Optical Cir- student in the Computer Science Department, University of Califor-
cuits: Mesh versus Ring Comparisons,” Optical nia, Davis, where he works as a research assistance in networks lab
Networks Magazine, vol. 2, no. 3, pp. 72-90, May/ under the supervision of professor Biswanath Mukherjee. His research
June 2001. interests include wavelength-routed WDM network design and
[18] A. Lardies, R. Gupta, and R. A. Patterson, “Traffic analysis, WDM network protection, restoration, and traffic grooming.
Grooming in A Multi-layer Network,” Optical Net-
works Magazine, vol. 2, no. 3, pp. 91-99, May/June
2001. Biswanath Mukherjee
[19] L. H. Sahasrabuddhe and B. Mukherjee, “LightTrees: Ph.D. Professor
Optical Multicasting for Improved Performance in Computer Science Department
Wavelength-Routed Networks,” IEEE Communica- University of California, Davis
tionsMagazine, vol. 37, no. 2, pp. 67-73, Feb. 1999. Davis, CA 95616
[20] N. Singhal and B. Mukherjee, “Architectures and [email protected]
Algorithms for Multicasting in Optical WDM Biswanath Mukherjee received the B.Tech.
Mesh Networks using Opaque and Transparent (Hons) degree from Indian Institute of
Technology, Kharagpur (India) in 1980 and the Ph.D. degree from
Optical Cross-connects,” Proc., IEEE OFC ’01, vol. 2,
University of Washington, Seattle, in June 1987. At Washington, he
pp. TuG8-T1-3, Anaheim, CA, March 2001. held a GTE Teaching Fellowship and a General Electric Founda-
[21] Y. Xu, et. al. “A Framework for Generalized Multi- tion Fellowship. In July 1987, he joined the University of Califor-
protocol Label Switching (GMPLS),” http://search. nia, Davis, where he has been Professor of Computer Science since
ietf.org/internet-drafts/draft-many-ccamp-gmpls- July 1995, and Chairman of Computer Science since September
framework-00.txt, Sep. 2001. 1997. He is co-winner of paper awards presented at the 1991 and
[22] D. Katz, D. Yueng, and K. Kompella, “Traffic En- the 1994 National Computer Security Conferences. He serves on
gineering Extensions to OSPF,” http://search.ietf. the editorial boards of the IEEE/ACM Transactions on Networking,
org/internet-drafts/draft-katz-yeung-ospf-traffic- IEEE Network, ACM/Baltzer Wireless Information Networks
06.txt, Oct. 2001. (WINET), Journal of High-Speed Networks, Photonic Network
[23] N. Bitar, R. Rao, and K. Muthukrishnan, “Traffic Communications, and Optical Network Magazine. He also served
as Editor-at-Large for optical networking and communications for
Engineering Extensions to OSPF,” http://search.ietf.
the IEEE Communications Society. He served as the Technical Pro-
org/internet-drafts/draft-bitar-rao-ospf-diffserv-mpls- gram Chair of the IEEE INFOCOM ’96 conference. Biwanath
01.txt., July 2001. Mukherjee is author of the textbook Optical Communication
[24] A. Bellato, M. Fontana, G. Gasparini, G. Grammel, Networks published by McGraw-Hill in 1997, a book which
J. Jones, and D. Papadimitriou “Traffic Engineering received the Association of American Publishers, Inc.’s 1997
Routing Extensions to OSPF and ISIS for GMPLS Honorable Mention in Computer Science. His research interests in-
Control of G. 709 Optical Transport Networks,” clude lightwave networks, network security, and wireless networks.

64 Optical Networks Magazine March/April 2003