IEICE TRANS. ??, VOL.Exx–??, NO.xx XXXX 200x

1

PAPER

An integrated routing mechanism for cross-layer traﬃc engineeringin IP over WDM networks
Yuki KOIZUMI† , Nonmember, Shin’ichi ARAKAWA† , Member, and Masayuki MURATA† , Fellow

SUMMARY
One approach to accommodating IP traﬃc on a wavelength division multiplexing (WDM) network is to construct a logical
topology, establishing a set of lightpaths between nodes. The lightpaths
carry IP traﬃc but do not require any electronic packet processing at intermediate nodes, thereby reducing the load on those nodes. When the IP and
WDM networks have independent routing functions, however, the lightpaths in the WDM network may not be fully utilized by the IP router. It
is therefore necessary to integrate the two routing mechanisms in order toutilize resources eﬃciently and adapt to changes in traﬃc. In this paper, we
propose an integrated routing mechanism for IP over WDM networks. The
key idea is to first prepare a set of virtual-links representing the lightpaths
that can be established by the WDM network, then calculate the minimum
cost route on an IP network including those links. Our simulation results
show that when traﬃc patterns do not change, the throughput of our method
is almost the same as that of a logical topology optimally designed for agiven traﬃc demand. When traﬃc patterns change, the throughput of our
method is about 50% higher than that of the logical topology.
key words: wavelength division multiplexing, IP over WDM, traﬃc engineering, routing, integrated routing algorithm

1.

Introduction

Wavelength Division Multiplexing (WDM) technology,
which carries multiple wavelength channels on a single
fiber, is expected to accommodate the bulk of traﬃc overthe current and future Internet. Since the majority of Internet traﬃc is IP, much research has been devoted to methodsof carrying IP packets directly over a WDM network, which
is an IP over WDM network [1–6]. One approach to accommodating IP traﬃc on a WDM network is to establish
a set of lightpaths (i.e., logical links) between nodes. Eachintermediate node of a lightpath has optical cross-connects(OXCs) that bind an input wavelength channel to a specified
output wavelength channel. The IP packets on lightpaths
are thus forwarded with no need for electronic packet processing by intermediate IP routers. In this way, lightpaths
can greatly reduce the load of packet processing on the IP
routers.
In order to fully utilize the bandwidth provided by
WDM networks, it is important to develop new approaches
to traﬃc engineering. Without traﬃc engineering, somelinks will be heavily congested while others are underutilized. The objective of traﬃc engineering can be achievedby selecting appropriate routes for balance the load on nodes
and links. There are two logical topology design methods
generally applied to problems of traﬃc engineering. One
Manuscript received January 1, 2003.
Manuscript revised January 1, 2003.
†
The authors are with the Graduate School of Information Science and Technology, Osaka University

approach is the static method, which configures a logical
topology based on the traﬃc statistics (e.g., traﬃc demandmatrices) measured for a certain period. Given the traﬃc demand, an optimal logical topology can be obtained by solving a Mixed Integer Linear Problem (MILP). Some heuristic
design methods can also configure nearly optimal topologies [7, 8]. Another approach is the dynamic method, whichconstructs logical topologies based on the current network
status (e.g., link utilization).
The static method can generate the optimal logical
topology for a given traﬃc demand matrix. It generally
takes a long time to measure a traﬃc demand matrix, however, and the matrix becomes even more diﬃcult to measure
as the number of nodes in the network increases [9]. Moreover, due to the nature of internet traﬃc, even after a traﬃcdemand matrix is obtained future traﬃc may not follow thesame pattern. In this case, a static design method cannot
flexibly adapt the logical topology to changes in the traﬃcpattern, which we will show in Sec. 5. One of the advantages of the dynamic method is that it does not require any
information from a traﬃc demand matrix.
In order to configure logical topologies dynamically,a method is needed to obtain current network informationsuch as link utilization. There are three diﬀerent internetworking models for IP over WDM networks: the peer,
augmented, and overlay models [10]. One of the most important diﬀerences between these models is the type of information shared between the IP layer and the optical layer.
In the peer model, the network topology and all other information (e.g., routing information and link state) are sharedby both layers, and a unified routing mechanism controls
the whole network (i.e., both IP and WDM). In the overlay
model, on the other hand, no network information is shared
between the IP and WDM layers. The WDM network and IP
network each have their own control planes; the routing protocols, topology information, and signaling protocols in the
IP network are independent of those in the WDM network.
The augmented model is a hybrid of the peer and overlay
models. Some agreed-upon information such as reachability is shared between the two layers, but the two layers aremanaged independently as in the overlay model.
The peer model excels at eﬃcient route control, since
all network information is available. However, collecting
this information requires the advertisement of the information of both the IP and WDM layers. This solution leads toan excessive update overhead, and therefore lacks scalability. In the overlay model, on the other hand, only the in-

IEICE TRANS. ??, VOL.Exx–??, NO.xx XXXX 200x2

formation of each layer needs to be advertised. This model
thus scales well compared to the peer model, but has difficulty routing packets eﬃciently since information on the
network status is limited. Moreover, since each network has
its own routing mechanism in the overlay model, lightpaths
configured in the WDM network may not be fully utilized
by the IP network. It is necessary to integrate the two routing mechanisms, so that resources can be used eﬃciently
and the network can adapt to changes in traﬃc.
In this paper, we integrate IP routing and wavelength
routing for IP over WDM networks, and propose a routing method that always forwards IP packets along lightpaths configured by the wavelength routing process. For thispurpose, we introduce the concept of virtual-links, which
are configured between IP routers. A virtual-link is a logical link that is not configured as a lightpath, but can be
activated as a lightpath by requesting the required wavelength resources. In the IP network, our method first calculates routes on a topology including these virtual-links. If
a virtual-link is selected as part of a route for the IP packets,a lightpath corresponding to the virtual-link will be established. In this manner, we can calculate routes on the IP network and WDM lightpaths simultaneously. The cost function for virtual-links is chosen in order to minimize the loadon the nodes. The results of computer simulations show thatour proposed method is eﬀective in terms of both average
end-to-end delay and throughput.
As we will describe in Sec. 2, in many previous works
Multi-Protocol Label Switching (MPLS) technology has
been used to specify the routes of IP packets (MPLS-based
IP over WDM networks). Unlike these works, which investigate the blocking probability of Label Switched Path (LSP)
requests, we intend to reveal the behavior of IP directly over
WDM networks on the packet level. Since WDM technology increases the traﬃc that can be accommodated bya huge amount, however, computer simulations of traﬃc insuch networks are correspondingly more diﬃcult. We therefore also develop a simulation based on the fluid flow model,
which greatly reduces the number of packets that have to beprocessed. We compare the results of our flow-level simulation with the results of a packet-level simulation, and showthat the end-to-end packet delay is almost the same.
The rest of this paper is organized as follows. In Sec. 2,
we describe how IP routing methods perform in IP over
WDM networks and introduce other traﬃc engineering approaches. In Sec. 3, we describe our integrated routing algorithm. Before evaluating the performance of our method, we
describe the flow-level simulation that enables a computer tomodel network traﬃc on a reasonable time scale. We evaluate the performance of our routing method in Sec. 5. Finally,
we conclude this paper in Sec. 6.
2.

Traﬃc engineering in IP over WDM networks

As mentioned above, it is important to develop a traﬃc engineering approach that can fully utilize the bandwidth provided by WDM networks. Traﬃc engineering objectives canbe achieved by developing eﬃcient routing methods. In thissection, we describe routing methods for the overlay andpeer models of IP over WDM networks.
2.1

Routing in the overlay model

In the overlay model, a logical topology is constructed asfollows. First, lightpaths are established between nodes ofthe WDM network. Conventional IP routing protocols, suchas Open Shortest Path First (OSPF) and Intermediate System to Intermediate System (IS-IS), then work on the logical
topology of the WDM network. In this model, the routing
protocols are not modified to account for the properties ofthe WDM network. The IP routing mechanism and WDM
routing mechanism are designed independently, so the IP
mechanism does not necessarily select the links provided by
the WDM network. One typical example of such a problem
is the minimum delay routing of IP networks, illustrated inFig. 1. In this example, we assume that each optical fiber
has two wavelengths, and that the propagation delay of eachfiber is 1 time unit. The delay incurred by an IP router, including processing delay and queuing delay, is also 1 time
unit but that of an OXC is 0. In this figure, six lightpaths
are configured in the WDM network (l1 to l6 ), so the logical
topology has six links. l5 , the long hop lightpath, has been
configured using wavelength λ2 between nodes N2 and N4 .
l5 must take the longer path because wavelength λ2 has already been used by l2 on the optical fiber connecting nodes
N2 and N3 . There are thus two possible routes from nodeN2 to N4 : R1 and R2 . R1 is the one-hop route N2 → N4
using l5 , and R2 is the two-hop route N2 → N3 → N4 using l2 and l3 . The end-to-end delay of R1 is 4, while thatof R2 is 3. Thus, if the IP routing mechanism uses end-toend delay as its metric, R1 will never be used as the routefrom N2 to N4 . This leads to ineﬃcient utilization of the
wavelength resources. We therefore need an integrated routing mechanism, whose main goal is to utilize resources eﬃciently. Some integrated routing methods have already been
proposed, mainly assuming the peer model; that is, they use
information from both networks such as bandwidth availability (IP) and wavelength availability (WDM). In the following section, we summarize some related works on the
problem of integrated routing.
2.2

Integrated routing in the peer model

Integrated routing methods for the peer model are proposedin references [5, 6]. These papers investigate IP/MPLS over
WDM networks, where the routes of IP packets can be explicitly determined by the MPLS algorithm as LSPs. In
reference [5], MIRA (Minimum Interference Routing Algorithm) is proposed as an integrated routing algorithm for
LSPs and lightpaths. The IP/MPLS over WDM network has
a unified routing entity that collects all the topology information and link state information from both IP/MPLS and
WDM networks. For incrementally arriving traﬃc flows
where the required bandwidth is explicitly specified, MIRAKOIZUMI et al.: AN INTEGRATED ROUTING MECHANISM FOR CROSS-LAYER TRAFFIC ENGINEERING IN IP OVER WDM NETWORKS

3
IP Router

OSPF

Route Manager
Topology
Database

Electronic
SignalIP Layer
WDM Layer

Control
SignalWavelength
Availability
Information

WDM Interface

Routing
ControllerLightpath
Setting
Information

Lightpath
Request

OpticalSignalTopology
Database

WDM Layer
Control Plane

Wavelength
Demux

Signaling
Protocol

Wavelength
Mux

Data
SignalFig. 1 An example showing that IP routing does not always select thelinks provided by the WDM network.
Optical Cross Connect

calculates the routes of traﬃc flow. MIRA also keeps trackof the residual bandwidth that can be used by future LSP
requests, and tries to maximize this resource. When there
is no appropriate route, LSP requests are blocked. In reference [1], another integrated routing method is developed
which takes into account inaccuracy in the link state information. This method incorporates the level of uncertainty
in link states and hop counts into its link cost metric for
LSPs. Reference [6] proposes an integrated routing method
for the peer model based on the Generalized MPLS (GMPLS) framework [11]. In this work, cost values are assigned
to links with the goal of reusing existing lightpaths for new
LSP setting requests as much as possible.
All these works assume that IP traﬃc is mapped onto
a series of bandwidth guaranteed LSP requests. Their main
objective is to minimize the blocking probability of LSP setting requests. Few works have focused on the performance
metrics of IP traﬃc (e.g., end-to-end delay or throughput).
The works just described have all assumed a peer model
network, which as mentioned above lacks scalability. Furthermore, very few works have studied integrated routing inan overlay model network. This paper therefore proposesa new integrated routing method within the overlay modelof IP over WDM networks, aimed at maximizing the traﬃcvolume that can be accommodated. In the next section, we
describe this new routing method.
3.

Integrated routing for cross-layer traﬃc engineering

In this section, we introduce our network model and the concept of a virtual-link, which is central to our integrated routing method. We then elaborate on our routing algorithm anddiscuss possible cost metrics.
3.1

Network model

We consider a network consisting of optical fiber links with
W independent wavelengths and nodes that consist of IP
routers with WDM interfaces, and OXCs. Figure 2 illustrates the node architecture used in this paper. The upper
part of this figure shows an IP router, and the lower partFig. 2

Node architecture.

shows an OXC. The IP router is connected to the OXC via a
WDM interface, which converts optical signals to electronic
signals and vice versa. The control plane in the WDM layer
manages the topology database and wavelength availability
information. The IP router has a route manager with threemain blocks: the routing controller, the topology database,and OSPF. The route manager calculates routes using an integrated algorithm based on the logical topology specified
in the topology database. This topology database includes
only information from the IP layer such as links, router status, and network connectivity, since we assume that the internetworking architecture follows the overlay model. The
OSPF-TE block advertises and collects IP link state information. Note that since we assume the overlay model, ourmethod does not require any extension of existing IP routing
protocols. The route manager in the IP layer sends setup orteardown lightpath requests to the WDM layer control plane
according to the results of its route calculation. The WDM
layer control plane carries out these requests and returns theresults to the IP route manager.
In our network architecture, a static lightpath is set up
between all adjacent nodes using one wavelength resource,
to ensure end-to-end reachability. We refer to these lightpaths as persistent lightpaths. The other wavelength resources are used for non-persistent lightpaths, which are set
up dynamically according to changes in traﬃc.
3.2

The concept of virtual-links

To integrate IP routing and wavelength routing, we propose
a concept of virtual-links. A virtual-link is a logical linkused by our routing algorithm. That is, they are configured
on a logical topology database, and the IP routing mechanism selects routes for IP traﬃc from that topology. An example of a network with virtual-links is shown in Fig. 3. In
this figure, persistent lightpaths are configured between all
adjacent nodes, and one non-persistent lightpath is configured from router R1 to router R6 . Three virtual-links (fromrouter R1 to routers R2 , R4 , and R5 ) are illustrated as dashedIEICE TRANS. ??, VOL.Exx–??, NO.xx XXXX 200x

4
f2
N6

N4

N2

N6

N4

N2
f2
added lightpath

N5

3.3.1

Integrated routing algorithm
Topology database

The OSPF component of the IP router advertises the linkstate information, and each IP router collects all the linkstate information. The IP routers then configure following the logical topology, which includes all virtual-links andtheir cost.
Step 1: Set virtual-links from the source node to all destination nodes for which there is no lightpath configured.
Step 2: Assign cost values to each virtual-link using the costfunction described in Sec. 3.4.
Step 3: Update the link cost values of existing nonpersistent lightpaths. The same cost function described in Sec. 3.4 is used.
Step 4: Set the link cost values of persistent lightpaths to 1.
We can set the cost values of all persistent lightpaths to 1
without loss of generality, as long as the cost of virtual-links
is scaled accordingly.
3.3.2

N5

N3

N1

f1

f1

(b) After configuring a lightpath

Congestion resulting from activating a virtual-link.

A network example with virtual-links.

arrows in the figure. Each link and virtual-link has an associated cost value, which is used by the IP routing mechanism.
Routes are therefore calculated from a logical topology that
includes virtual-links as well as existing lightpaths. Notethat in our proposal, the cost of the virtual-links has a great
impact on network performance. We discuss our choice of
cost function for the virtual-links in Sec. 3.4.
3.3

N1(a) Before configuring a lightpath
Fig. 4
Fig. 3

N3

Route selection

The routes of IP packets are calculated using the topology database obtained by the above procedure, and if any
virtual-links are selected as the part of IP routes then thecorresponding lightpath is dynamically configured on the
WDM network. Each node in the network performs following steps.
Step 1: Calculate the routes with minimum cost on the logical topology, including virtual-links and existing
lightpaths, via the IP routing algorithm.

Step 2: If the resulting routes contain one or more virtuallinks, send requests to the WDM network to set up
the corresponding lightpaths. If some of those requests are blocked due to the lack of wavelength
resources, existing lightpaths are used for thoseroutes.
Step 3: Send teardown requests for all existing lightpaths
that are not used in the IP routes just calculated.
Here, an unused lightpath means that a link that is
not included in the minimum cost routes just calculated, and whose source node is the node performing these steps.
Routing in the IP and WDM layers is integrated by searching for minimum cost routes in a logical topology including
virtual-links. Using this method, IP traﬃc will be forwarded
on virtual-links (i.e., lightpaths) since lightpaths are selectedby the IP routing.
3.4

Cost assignment to virtual-links

The fundamental question in this approach is how to select a cost function for the virtual-links. Our main objective in choosing this cost function is to maximize the network throughput. Reducing the load on the IP routers istherefore an important criterion. Activating virtual-links aslightpaths may increase the load on some nodes, however,
because more traﬃc will pass through the destination nodesof lightpaths. We show a simple example of this scenario inFig. 4. In Fig. 4(a) two flows, f1 and f2 , are forwarded along
the routes N1 → N3 → N5 and N2 → N4 → N6 → N5 respectively. Figure 4(b) illustrates the network after a lightpath
has been configured from node N2 to N3 . Since the lightpath
has just been set, the route of flow f2 changes to N2 → N3 →N5 . In this case, f2 traﬃc that used to pass through nodes N4
and N6 now passes through node N3 . Consequently, the loadon N3 increases. We therefore use the load on the destination node of a virtual-link as the main parameter of our costfunction, to avoid concentrating traﬃc on frequently usednodes. Note that the IP router status can be obtained using
Simple Network Management Protocol (SNMP).
The cost function Ci j of a virtual-link between nodes iand j is thus given by
Ci j = v2j + β,(1)

KOIZUMI et al.: AN INTEGRATED ROUTING MECHANISM FOR CROSS-LAYER TRAFFIC ENGINEERING IN IP OVER WDM NETWORKS

5

where v j is the load on node j, and β is a constant oﬀset. As
noted above, our main purpose is to reduce the load on the
IP routers. By using a cost function that is quadratic in v j ,we expect to strongly discourage any increase in the nodeload factor. By setting β to 0.5, we prevent the IP routing
method from selecting routes with too many hops. Setting
the oﬀset value to 0.5 also forces the IP routing mechanism
to select persistent lightpaths whenever possible, since thecost of a persistent lightpath is always 1 and the sum of thecost of two virtual-links is more than 1.
The number of lightpaths Ni j connecting node i to node
j is decided by Ni j = bi j , where bi j is the incoming traﬃcvolume at node j from node i. This assumes that the traﬃcvolume going to node j can be measured at node i. A minimum of Ni j lightpaths will be configured so that the current
traﬃc volume can be satisfied.
4.

Flow-level simulation of packets in a WDM network

In this section, we describe a simulation of network traffic based on the fluid flow model (a flow-level simulation).
Conventionally, traﬃc flow is modeled with a discrete event
simulation that processes every packet (a packet-level simulation). A flow-level method is necessary, however, if simulations of large-scale networks are to finish in a reasonableamount of time. First, we detail the reasons that a flow-level
simulation is needed, and then we describe the fluid flow
approximation used by the simulation. Finally, we compare
the results of a flow-level simulation to those of a packetlevel simulation, in order to validate the method.
4.1

The diﬃculties of packet-level simulations

Computer simulations are commonly used to analyze andevaluate the performance of communication networks. Discrete event network simulators (such as OPNET [12] or NS2 [13]) simulate the movement of individual packets throughthe network. Although this method provides accurate insight into the network state and performance, a great many
events must be processed to properly simulate the network.
With the growth of the Internet, the scale of networks has
become even larger. Moreover, new network technologies
such as WDM provide high bandwidth links, significantly
increasing the traﬃc volume that networks can accommodate. The simulation of modern networks consumes an enormous amount of time and resources.
Many recent papers have described simulation methods
based on the fluid flow model [14, 15]. These works mainly
develop simulations for TCP-based networks; that is, they
focus on transient states of TCP flow. In this paper, however, we only focus on the state of IP traﬃc over the WDM
network. We therefore simplify the model of the simulation
method, and just apply the fluid flow model, which requires
fewer packets to be processed during simulations, and evaluate our integrated routing mechanism.

Fig. 54.2
4.2.1

Calculation of the number of packets at a node.

The flow-level simulation method
Fluid flow modelFirst, we describe the fluid flow approximation. In simulation methods based on the fluid flow model, data traﬃc ismodeled not as a sequence of packets but as a continuous
fluid. Network simulators based on the fluid flow approximation abstract the model further, focusing only on changes
in the arrival rates of traﬃc flow. This can lead to a significant decrease in computation time, although any information regarding the motion of individual packets is lost.
4.2.2

Application of the fluid flow model to network simulations

We define the following terms to explain the flow-level simulation.
tn :n-th timestep, when the arrival or departure of flows
can occur.

L(tn ):

Number of packets in a node at time tn .

a(tn ):

Packet arrival rate at a node at time tn .

ai :Packet arrival rate in flow i.

μ:Service rate of the node.

W(tn ): Delay in the node at time tn .
The packet arrival rate of each flow is drawn from a Poisson
distribution with constant average rate ai .
Figure 5 illustrates the algorithm for calculating thepacket arrival rate at a node. The figure illustrates threeflows (flow1 , flow2 , flow3 ) that arrive at the node at consecutive timesteps t1 , t2 , and t3 . The flows, which are not all thesame length, depart at times t6 , t4 , and t5 , respectively. Eachflowi has the parameter ai , which is the arrival rate of packets in the flowi . In other words, the time spacing between
individual packets in flowi is 1/ai . The packet arrival rate
for a given node a (denoted a(tn )) is the sum of the packet
arrival rates ai for each flow, so a(tn ) changes with the arrival/departure of flows as shown in the upper part of Fig. 5.
The increase in packet number at the node from

IEICE TRANS. ??, VOL.Exx–??, NO.xx XXXX 200x

6

time tn−1 to time tn can be represented by {a(tn−1 ) − μ} ×
(tn − tn−1 ). The factor a(tn−1 ) × (tn − tn−1 ) is the total number of packets arriving at the node between tn−1 and tn ,and the factor μ × (tn − tn−1 ) is the number of packets departing from the node in the same interval. Note that if{a(tn−1 ) − μ} × (tn − tn−1 ) < 0, the number of packets in thenode decreases. Since the number of packets at time tn−1 isdenoted L(tn−1 ), the total number of packets in the node attime tn can be expressed as

average end to end delay (ms)1000

L(tn ) = {a(tn−1 ) − μ} × (tn − tn−1 ) + L(tn−1 ).
Since L(tn ) must be a non-negative number, we further set
L(tn ) = 0 if the calculation results in L(tn ) < 0. The delay experienced at a node can be calculated as W(tn ) =L(tn )/a(tn ), applying Little’s theorem [16].
In the flow-level simulation, only the head and tailpackets of each flow are processed to update parametersa(tn ), L(tn ), and W(tn ). In a packet-level simulation, every
packet in the flow has to be processed; a(tn ), L(tn ), and W(tn )are updated whenever a packet arrives at the node.
4.3

Verification of the flow-level simulation method

To validate the fluid flow approximation, we compare theresults of a flow-level simulation with those of a packet-level
simulation.
We compare the two simulation methods under identical conditions: a NSFNET topology with 14 nodes and 21
edges. The number of wavelengths for each link is eight, andwavelength converters are not used in this simulation. The
bandwidth of each wavelength is assumed to be 10 Gbps.
The processing capacity of the IP router is set to 1 Gbps
to perform the packet-level simulation within a reasonableamount of time. The flow lengths are drawn from an exponential distribution with a mean value of 12 Mb. The flows
connecting each node pair i j arrive according to a Poissonprocess with average rate γ × di j , where D = {di j } is the traffic demand matrix and γ is a scale factor. We use the traﬃcdemand matrix given in Ref. [8]. Moreover, we use the same
sequence of random numbers for both simulations.
Figure 6 shows the average end-to-end delay as a function of the total amount of traﬃc, which is controlled bymeans of the scale factor γ. We observe that the average end-to-end delay obtained by the flow-level simulationagrees well with that obtained by the packet-level simulation. Although a diﬀerence appears at high loads (greaterthan 3.5 Gbps), the saturation point is almost the same. Networks are generally operated at loads much lower than thesaturation point, so we can ignore the diﬀerence between
these two methods. Evaluating the queue behavior at anode also confirms the validity of the flow-level simulation
method. Due to space limitations, we omit the results of thistest.
The flow-level method greatly reduces the simulation
time because only two packets per flow are processed. In
this validation, we chose a small average number of packets(1000) per flow, so that the packet-level simulation could

Flow-Level
Packet-Level

100

10

1
0

1

2
3
4
total amount of traffic (Gbps)

56Fig. 6 The average end-to-end delay of flow-level and packet-level simulations.

run in a reasonable time. The packet-level network simulator must therefore process 500 times more packets than
the flow-level simulator. The actual simulation time of theflow-level simulation for one choice of parameters was a few
seconds, while that of the packet-level simulation was morethan ten minutes (the exact times depend on the implementation). Moreover, the memory requirement of the flow-level
simulation is much less than that of the packet-level simulation. Computer simulations based on the fluid flow model
are therefore a very eﬀective method for evaluating the performance of high-bandwidth networks.
5.

The eﬀects of cross-layer traﬃc engineering in IP
over WDM networks

In this section, we evaluate the performance of the proposed
algorithm through flow-level computer simulations.
5.1

Simulation model

The simulation model used here is almost the same as that
described in section 4.3. We change the router capacity to
100 Gbps, the link capacity to 40 Gbps. As the number ofwavelengths multiplexed on a single fiber increases, the processing capacity of electronic routers will become the bottleneck of a network. We therefore evaluate our method
and conventional methods under these parameter settings,
that is, the bottleneck of the network is processing capacity of electronic routers. We set the average flow length
to 75 Mbytes; the packet size is 1500 bytes, and the average length of a flow is 50000 packets. In addition to the
NSFNET topology, we also show results for the European
Optical Network (EON), which has 19 nodes and 39 bidirectional links. For the NSFNET topology, we use a random traﬃc demand matrix, generated according to an exponential distribution, in addition to the matrix described inRef. [8]. For the EON topology, we use only a randomly
generated traﬃc matrix.
For the purpose of comparison, we use three logical
topologies. First two logical topologies are designed by
the algorithms SHLDA (Shortest-Hop Logical topology Design Algorithm) [7] and MLDA (Minimum delay LogicalKOIZUMI et al.: AN INTEGRATED ROUTING MECHANISM FOR CROSS-LAYER TRAFFIC ENGINEERING IN IP OVER WDM NETWORKS

7

0
11
8
3

1

4

13

9

7

6

12

2
10
5

Fig. 7

Fig. 8NSFNET topology.

European Optical Network (EON) topology.

topology Design Algorithm) [8]. These algorithms generate logical topologies based on a given traﬃc demand matrix in order to achieve their namesake performance objectives. Since both MLDA and SHLDA have a prior knowledge about the traﬃc demand matrices, they generate nearly
optimal topologies. For the third logical topology, we use afull mesh topology, which is generated by configuring lightpaths between all node pairs by assuming that there are unlimited number of wavelengths on a fiber. All IP traﬃc in thefull mesh topology is directly forwarded from source nodes
to destination nodes. Since IP routers do not need to process the traﬃc for other node pairs, full mesh topologies
are optimal and give upper bounds of networks. We compare the results of our method to these near-optimal topologies in order to demonstrate the eﬃciency of our method.
In our simulation experiments, we use minimum hop routing for IP packets on the logical topologies generated by
MLDA/SHLDA. For the full mesh topology, we configure
the suﬃcient number of lightpaths for accommodating IP
traﬃc between nodes.
5.2

Performance evaluations

We evaluate the performance of our integrated routing
method with three metrics: the average end-to-end delay
in Sec. 5.2.1, the load on the nodes in Sec. 5.2.2, and the
network throughput in Sec. 5.2.3.
5.2.1

Average end-to-end delay

Figures 9(a) and 9(b) show the average end-to-end delay on

NSFNET. The horizontal axis shows the total traﬃc volume
in the network. The result in Fig. 9(a) is based on the traﬃcmatrix in [8]. The average end-to-end delay achieved by ourrouting method is slightly worse than that achieved by the
topologies generated by MLDA/SHLDA and the full meshtopology. Our method shows nearly optimal end-to-end delay performance without the information of traﬃc demandmatrix. In Fig. 9(b), we show results from the three methods
in a scenario where the traﬃc matrix is randomly regenerated four times in one simulation but the sum of the matrix(i.e., x-axis value in the figure) is held constant. Note that,for obtaining result of the full mesh topology, we configure
the suﬃcient number of lightpaths between nodes for eachof the regenerated traﬃc matrices. Thus, the results show
the upper bound of the performance. As expected, changing traﬃc patterns degrade the performance of the SHLDA
and MLDA methods drastically. Our algorithm, however,shows little increase in the average end-to-end delay in thissituation. Moreover, our method does not require any priorknowledge of traﬃc statistics whereas SHLDA and MLDA
create logical topologies according to previously measured
statistics. This feature is a great advantage, since it takes along time to measure traﬃc statistics accurately and IP traffic does not always follow the pattern described. Thus, statically generated logical topologies may not always perform
optimally, as shown in Fig. 9(b).
We next evaluate our proposed method on the NSFNET
topology using a random traﬃc matrix. Figures 9(c) and9(d) show the average end-to-end delay on the NSFNET
topology as a function of the total traﬃc. In this figure,
we observe that our routing method outperforms conventional logical topology design methods. Moreover, the average end-to-end delay in our method is constant regardless of
traﬃc change, while the delay using SHLDA or MLDA depends strongly on the traﬃc demand matrices. Figures 9(e)and 9(f) depict the results of our routing mechanism on the
EON topology. These figures show tendencies similar to
those observed on the NSFNET topology.
5.2.2

Load on nodes

To see the eﬃciency of our method more clearly, we show
the average load on each node in Fig. 10. The load on a nodeis the traﬃc volume processed in that node divided by theprocessing capacity of the node. In this simulation, we use
the NSFNET topology and the traﬃc demand matrix given
in Ref. [8]. In obtaining this figure, we set the total traﬃc demand to the point where the average end-to-end delay justbegins to increase, as seen in Fig. 9(a) and Fig. 9(b). We
set the total traﬃc volume in the network to 450 Gbps for
all methods, for both the static and dynamic traﬃc patterns.
Figure 10(b) shows that our algorithm balances the load at
an average value around 0.7 when slight congestion occurs
in the network. In the SHLDA and MLDA methods, on theother hand, most of the nodes remain under-utilized eventhough node 12 is saturated. Fig. 10(a), however, shows thatsome nodes are highly loaded in all methods. To investi-

IEICE TRANS. ??, VOL.Exx–??, NO.xx XXXX 200x

81000

Integrated

100
Full Mesh
SHLDA
MLDA

10

1000
Integrated
MLDA
SHLDA
Full Mesh100

Average end to end delay (ms)Integrated
MLDA
SHLDA
Full Mesh

Average end to end delay (ms)Average end to end delay (ms)1000

Integrated
SHLDA
MLDA

10

Integrated
MLDA
SHLDA
Full Mesh
Integrated

100

SHLDA
10
MLDA

Full Mesh
1

1
100

200
300
400
500
Total amount of traffic (Gbps)

600(a) Average end-to-end delay without traﬃcchange: NSFNET topology, the case of realistic
traﬃc demand matrix.

Integrated

100
SHLDA

200
300
400
500
Total amount of traffic (Gbps)

600

0

MLDA

10

Full Mesh
1

Integrated

SHLDA

MLDA

10

200
300
400
500
Total amount of traffic (Gbps)

600

100
SHLDA

(d) Average end-to-end delay with traﬃcchange: NSFNET topology, the case of random
traﬃc demand matrix.

Integrated

MLDA

Full Mesh

10

Full Mesh1

0

100 200 300 400 500 600 700 800 900 1000
Total amount of traffic (Gbps)

0(e) Average end-to-end delay without traﬃcchange: EON topology, the case of random traffic demand matrix.
Fig. 9100 200 300 400 500 600 700 800 900 1000
Total amount of traffic (Gbps)(f) Average end-to-end delay with traﬃcchange: EON topology, the case of random traffic demand matrix.

Average end-to-end delay.

gate the reasons for this, we classify the traﬃc volume into
three types; ingress traﬃc, egress traﬃc, and transit traﬃc.
Ingress traﬃc is traﬃc that arrives at the node from outside
the network, and egress traﬃc is traﬃc that leaves the network at the node. Transit traﬃc is traﬃc that is being forwarded from the ingress line card to the egress line card.
Figure 11 shows the load on each node caused by each kindof traﬃc. In obtaining this result, we evaluate our method on
the NSFNET topology without traﬃc change. It is revealed
that most of the volume is either ingress or egress traﬃc,which must be processed at the nodes. Since the ingress andegress traﬃc depend on the traﬃc demand matrix, hereafter
we focus on the behavior of the transit traﬃc. Note that theamount of transit traﬃc processed at nodes with high ingressand egress traﬃc (nodes 6, 7, and 12) is nearly 0. In general, the transit traﬃc in loaded nodes is much less than thatin nodes with little load. This means that our method detours
IP traﬃc through the less active nodes, and achieves the central goal of load balancing. SHLDA and MLDA balance theload on nodes using the information of the traﬃc demandmatrix. Our method, on the other hand, does not require any
information of traﬃc demand matrix, and balances the load
on nodes using the information of nodal load. In the fullmesh logical topology, IP routers does not need to processtransit traﬃc, and therefore, the load on nodes is the lowest
among all methods. Our method, however, shows almost
the same performance as the full mesh logical topology bybalancing the load.

1.2
Total
Ingress+EgressTransit1
Average load on nodes

100

600

Integrated
MLDA
SHLDA
Fulll Mesh

1

0

200
300
400
500
Total amount of traffic (Gbps)

1000

Integrated
MLDA
SHLDA
Full Mesh100100(c) Average end-to-end delay without traﬃcchange: NSFNET topology, the case of random
traﬃc demand matrix.

1000
Average end to end delay (ms)Average end to end delay (ms)Integrated
MLDA
SHLDA
Full Mesh

100(b) Average end-to-end delay with traﬃcchange: NSFNET topology, the case of realistic
traﬃc demand matrix.

1000

Full Mesh

10

Average end to end delay (ms)

0

Total

0.8
0.6
Ingress+Egress

0.4

Transit
0.2
0
0

1

2

3

4

5

6

7

8

9

10 11 12 13

Node ID

Fig. 11 Classified load on nodes without traﬃc change: the integrated
routing method.

5.2.3

Network throughput

We next measure the network throughput achieved by crosslayer traﬃc engineering. We define network throughput as
the maximum traﬃc volume that the network can accommodate while keeping the average end-to-end delay under
10 ms. This simulation also uses the NSFNET topology.
Fig. 12 shows the throughput using the traﬃc demand matrix given in Ref. [8]. The throughput of our method isslightly lower than that of MLDA, SHLDA, and full meshtopology when traﬃc does not change. Changing traﬃc patterns, however, degrade the throughput of MLDA/SHLDA
dramatically. Under these conditions, the logical topology
generated by SHLDA can accommodate only 68% of theKOIZUMI et al.: AN INTEGRATED ROUTING MECHANISM FOR CROSS-LAYER TRAFFIC ENGINEERING IN IP OVER WDM NETWORKS

9
1.2

1.2
Integrated
MLDA
SHLDA
Full Mesh

0.8
0.6
0.4
0.2

Integrated
MLDA
SHLDA
Full Mesh

1
Average load on nodes

Average load on nodes

1

Integrated

Full Mesh

SHLDA

MLDA

2

5

7

0.8
0.6
0.4

Full Mesh

0.2

0

0
0

1

3

4

6

8

9

10 11 12 1301

Node ID

Fig. 10

3

4

5

6

7

8

9

10 11 12 13(b) Load on nodes with traﬃc change: NSFNET topology, total
traﬃc volume is 450 Gbps for all method.

Average load on each node.

400

ulation ran about 500 times faster than the packet-level simulation and reduced the required memory, so it is a goodtechnique for modeling large scale and high-bandwidth networks.

300

References

Without traffic changeWith traffic change

500

Throughput (Gbps)

2

Node ID(a) Load on nodes without traﬃc change: NSFNET topology,
total traﬃc volume is 450 Gbps for all method.

200

100

0

Integrated

Fig. 12

MLDA

SHLDA

Full Mesh

Network throughput.

static traﬃc throughput. The logical topology generated by
MLDA can accommodate 63% of the static traﬃc throughput. Changing traﬃc patterns does not greatly aﬀect thethroughput of our method.
6.

MLDA
SHLDA
Integrated

Conclusion

In this paper, we propose a new integrated routing algorithm that uses virtual-links in selecting routes for IP packets, and demonstrate the necessity of dynamic lightpath configuration in IP over WDM networks. The main objectivesof our algorithm are to reduce the load on IP routers andmaximize the traﬃc volume that can be accommodated by
the network. Simulation results show that our method balances the load on IP routers where static logical topology
design methods cannot. Under changing traﬃc patterns, thethroughput of our method was 38–50% higher than that oftwo static logical topology design methods. To reduce thecosts of computer simulation, we developed a method using the fluid flow model. The flow-level simulations werevalidated by comparing them to conventional packet-level
simulations. The flow-level and packet-level simulations
achieved similar results with respect to average end-to-end
delay and number of packets per node. The flow-level sim-

[1] J. Li, G. Mohan, E. C. Tien, and K. C. Chua, “Dynamic routing
with inaccurate link state information in integrated IP over WDM
networks,” Computer Networks, vol. 46, pp. 829–851, Dec. 2004.
[2] T. Ye, Q. Zeng, Y. Su, L. Leng, W. Wei, Z. Zhang, W. Guo, andY. Jin, “On-line integrated routing in dynamic multifiber IP/WDM
networks,” IEEE Journal on Selected Areas in Communications,vol. 22, pp. 1681–1691, Nov. 2004.
[3] S. Arakawa, M. Murata, and H. Miyahara, “Functional partitioning for multi-layer survivability in IP over WDM networks,” IEICE
Transactions on Communications, vol. E83-B, pp. 2224–2233, Oct.
2000.
[4] N. Ghani, S. Dixit, and T.-S. Wang, “On IP-over-WDM integration,”
IEEE Communications Magazine, vol. 38, pp. 72–84, Mar. 2000.
[5] M. Kodialam and T. V. Lakshman, “Integrated dynamic IP and wavelength routing in IP over WDM networks,” in Proceedings of IEEE
INFOCOM, pp. 358–366, Apr. 2001.
[6] J. Comellas, R. Martinez, J. Prat, V. Sales, and G. Junyent, “Integrated IP/WDM routing in GMPLS-based optical networks,” IEEE
Network Magazine, vol. 17, pp. 22–27, Mar./Apr. 2003.
[7] J. Katou, S. Arakawa, and M. Murata, “A design method for logical
topologies with stable packet routing in IP over WDM networks,”
IEICE Transactions on Communications, vol. E86-B, pp. 2350–
2357, Aug. 2003.
[8] R. Ramaswami and K. N. Sivarajan, “Design of logical topologies
for wavelength-routed optical networks,” IEEE Journal on Selected
Areas in Communications, vol. 14, pp. 840–851, June 1996.
[9] A. Medina, N. Taft, K. Salamatian, S. Bhattacharyya, and C. Diot,“Traﬃc matrix estimation: Existing techniques and new directions,”in Proceedings of ACM SIGCOMM, pp. 161–174, Aug. 2002.
[10] S. Koo, G. Sahin, and S. Subramaniam, “Dynamic LSP provisioning in overlay, augmented, and peer architectures for IP/MPLS over
WDM networks,” in Proceedings of IEEE INFOCOM, pp. 514–523,
Mar. 2004.
[11] E. Mannie, “Generalized multi-protocol label switching (GMPLS)
architecture.” RFC 3945 (Proposed Standard), Oct. 2004.
[12] “OPNET.” http://www.opnet.com/.
[13] “The network simulator - ns-2.” http://www.isi.edu/nsnam/ns/.
[14] C. Kiddle, R. Simmonds, C. L. Williamson, and B. Unger, “Hy-IEICE TRANS. ??, VOL.Exx–??, NO.xx XXXX 200x10brid packet/fluid flow network simulation,” in Proceedings of the
17th Workshop on Parallel and Distributed Simulation, pp. 143–152,
June 2003.
[15] F. Baccelli and D. Hong, “Flow level simulation of large IP networks,” in Proceedings of IEEE INFOCOM, pp. 1911–1921, Mar.
2003.
[16] D. Bertsekas and R. Gallager, Data Networks. Englewood Cliﬀs,
New Jersey: Prentice Hall, Inc., Englewood Cliﬀs, 1987.

Yuki Koizumi
received the M.E. degrees
from Osaka University, Japan, in 2006. He
is currently a doctoral student at the Graduate
School of Information Science and Technology,
Osaka University, Japan. His research interest
includes traﬃc engineering and routing in photonic networks.

Shin’ichi Arakawa
received the M.E. and
D.E. degrees in Informatics and Mathematical
Science from Osaka University, Japan, in 2000
and 2003, respectively. He is currently a Research Assistant at the Graduate School of Information Science and Technology, Osaka University, Japan. His research work is in the areaof photonic networks. He is a member of IEEEand IEICE.

Masayuki Murata
received the M.E. and
D.E. degrees in Information and Computer Sciences from Osaka University, Japan, in 1984 and1988, respectively. In April 1984, he joined
IBM Japan’s Tokyo Research Laboratory, asa Researcher. From September 1987 to January 1989, he was an Assistant Professor with
the Computation Center, Osaka University. In
February 1989, he moved to the Department ofInformation and Computer Sciences, Faculty ofEngineering Science, Osaka University. In April
1999, he became a Professor of Osaka University, and since April 2004, hehas been with the Graduate School of Information Science and Technology, Osaka University. He has contributed more than four hundred andfifty papers to international and domestic journals and conferences. His
research interests include computer communication networks and performance modeling and evaluation. He is an IEICE Fellow. He is a memberof IEEE, ACM, The Internet Society, IEICE and IPSJ.