técnicas de roteamento e atribuição de comprimento de onda em redes WDM(fribra ótica)

Prévia do material em texto

Dynamic Routing and Wavelength Assignment with Power Consideration
in WDM Networks
Naohiro Sakiyama, Akira Nagata, Takahiro Matsuda, and Miki Yamamoto
Graduate School of Engineering, Osaka University
2-1 Yamadaoka, Suita, Osaka, 565-0871, Japan
Tel: +81-6-6879-7742, Fax: +81-6-6875-5901
E-mail: naohiro@post.comm.eng.osaka-u.ac.jp
Abstract - One of the most important technical prob-
lems in optical WDM network is the dynamic routing and
wavelength assignment (dynamic RWA) problem, which is
to set up lightpaths and assign wavelengths dynamically in
order to establish a channel between optical source and des-
tination nodes. Previous studies have solved many vari-
ations of the dynamic RWA problem under the assump-
tion of ideal conditions regarding the power of a signal,
i.e. signal attenuation on a fiber and saturation of optical
amplifier are not taken into account. In practical net-
work environment, capability of connection establish-
ment in RWA problem should be smaller than this ideal
case. In this paper, we investigate the dynamic RWA prob-
lem taking account of degradation of routed signals by opti-
cal components, and propose a new routing algorithm with
power consideration. The proposed algorithm can reduce
forced termination probability of connections due to the
above power constraints. With a computer simulation, we
evaluate the proposed algorithm by comparing it with an
existing routing algorithm.
I. INTRODUCTION
Wavelength Division Multiplexing (WDM) technology is
globally used to cope with rapidly increasing bandwidth
demands in telecommunication networks [1]. An important
problem in WDM networks is the routing and wavelength as-
signment (RWA). The objective of the RWA problem involves
selecting the best combination of a route (path) and a wave-
length for each connection such that the number of connections
established is maximized under the condition that any connec-
tions sharing a common link does not use the same wavelength.
The RWA problem is categorized into two groups, static
RWA and dynamic RWA: depending upon whether the traffic
demand is considered statically or dynamically [2]. In the static
case, given a fixed demand matrix, where each entry specifies
the number of lightpaths requested from one station to another,
the objective is usually to satisfy the maximum number of re-
quested lightpaths. In the dynamic case, connections are gen-
erated and closed with some probability distribution and the
objective is usually to minimize the required number of wave-
lengths or fibers in the network.
In this paper, we focus on the dynamic RWA problem. The
dynamic RWA problem is important especially in IP over pho-
tonic networks [3, 4]. The number of users connected to the IP
networks has been increasing due to an explosive growth of the
Internet services. Since IP traffic demand is highly variable, it
is difficult to characterize the traffic profile beforehand. There-
fore, in order to realize IP over WDM networks with tremen-
dous capacity, setting up lightpaths should be solved by the
dynamic RWA approach.
Many previous studies have proposed solutions of dynamic
RWA. In most of them, the optical network is modeled under
the ideal assumption, i.e. signal attenuation on fiber not to be
considered, and only the logical aspects of the problem are con-
sidered. In these proposals, a connection between two stations,
which traverses optical fiber links and encounters different de-
vices, is assumed to maintain valid power levels on the entire
path from source to destination [5]. When the signal attenua-
tion is taken into account, the network design principle under
the ideal condition cannot be applied.
In this paper, we propose an effective routing algorithm with
power consideration. The proposed algorithm provides the sta-
ble communication by suppressing and avoiding the occurrence
of saturation in the amplifier which causes the forced termi-
nation of connections. The proposed algorithm is based on a
fixed-alternate routing algorithm, which selects a route to be
assigned from a limited number of fixed routes to each desti-
nation node. The fixed-alternate routing has two procedures,
making routing tables at each optical switch, and determin-
ing an adequate route from the routing table. Our proposed
algorithm takes account of the power constraint in both two
procedures and makes it enable to construct effective optical
networks in terms of network resource utilization and physical
conditions.
The rest of this paper is organized as follows. First, the prob-
lem description of the dynamic RWA with power consideration
will be presented. Next, a new dynamic RWA with power con-
sideration will be proposed . Finally, the numerical results are
discussed and the conclusions are given.
II. DYNAMIC RWA WITH POWER
CONSIDERATION
A. Problem Description
Many algorithms for the dynamic RWA problem have been
proposed in order to utilize network resources effectively and
maximize the number of lightpaths established. These stud-
ies, however, are evaluated under the ideal conditions without
physical constraints . In the optical network, signals on fiber is
decayed. Amplification, whether inside the switching devices
or on the fiber links, is needed to compensate for these power
losses. A proper power level for the individual signal in the
optical network must be maintained in such a way that the ag-
gregate power on a fiber does not exceed a certain threshold.
This is because saturation occurs when the total input power of
the amplifier exceeds a given threshold. When saturation oc-
curs, the amplifier cannot work at its full capacity, but rather its
gain is a decreasing function of the aggregate power. It is also
worth mentioning that one individual connection with a high
signal power might saturate the amplifier and reduce the gain
for other signals sharing the same amplifier [5]. When the gain
of a connection is reduced and received power is under an ad-
equate power level, this connection results in being terminated
by force.
The objective of the proposed routing algorithm is to find a
route that avoids saturation. In order to do this, from the above
discussion, it is required to minimize the total input power of
optical amplifier by reducing the transmission power of a sta-
tion.
B. Proposed Algorithm
Our proposed algorithm is based on fixed-alternate routing, which
can reduce computational costs for updating routing tables as
compared with other routing algorithms. In the fixed alternate
routing, each node in the network is required to maintain a rout-
ing table which contains an ordered list of some fixed routes to
each destination node. A direct route between a source node
s and a destination node d is defined as the first route in the
list of routes to d in the routing table at s. Alternate routes
between s and d are any route other than the first route in the
list of routes to d in the routing table at s.
The proposed algorithm is described as follows. When a
connection request is generated, the source node attempts to
find routes in sequence from the routing table, until a route with
a valid wavelength assignment is found. If no available route
is found from the routing table, the request is blocked and lost.
When a saturation occurs on the direct route, even if a valid
wavelength assignment is found, the connection request along
the direct route is blocked and an alternate route is chosen. We
anticipate that connections concentrate on the links which is
frequently used with shortest path. Proposed routing algorithm
allows to avoid saturation on that links.
In this paper, a routing table is assumed to contain two routes
for requested connection, a direct route and an alternate route.
These routes between s and d are determined by a following
procedure:
1: Set the shoretest route R1 from s to d for the directroute.
2: Compute (K− 1) routes Ri (2 ≤ i ≤ K) as candidate
routes, where Ri represents the ith shortest route.
3: For Ri, 2 ≤ i ≤ K, compute the transmission powers
pi,j (1 ≤ j ≤ Li) from each intermediate switch j on
Ri . Li means the number of switches on Ri. Find the
maximum transmission power Pimax = MAX(pi,j)
4: Find m such that Pmmax = MIN(Pimax) (2 ≤ i ≤ K),
which means the minimal of the maximum transmission
powers of all the candidate routes.
5: Select Rm as the alternate route
In this paper, we assume K = 3, i.e an alternate route is
selected from the second-shortest route and the third-shortest
route.
III. SIMULATION RESULTS
In this section, we evaluate the performance of the proposed
routing by a computer simulation. We compare the proposed
routing with the fixed-alternate routing proposed in [6] which
does not consider the power constraint.
In the computer simulation, the network model in [5]
with 21 switches and 114 unidirectional fiber links [5] (shown
in figure 1) is used . In this network, every link is assumed to
be capable of carrying 8 wavelengths. Amplifiers are placed on
the links every 100km. We employ the same model of amplifier
as in [5]. The gain available at an amplifier is given by the
following function:
G(Pin, SSG) = min{SSG, (Pmax − Pin)}
where Pin is the total input power in dBm; Pmax is the max-
imum amplifier output power in dBm, and SSG is the gain in
dB, which is obtained when saturation is not occurred. We as-
sume each switch is connected with an access node ni (1 ≤
i ≤ 21). Calls for node pair (ni, nj) (1 ≤ i, j ≤ 21, i 6= j) are
generated according to a Poisson process with an arrival rate λ.
The holding time for a call is exponentially distributed with an
average holding time h and is independent of generation and
holding times of other calls.
The blocking probability and the forced termination proba-
bility is used as performance metric. Blocking probability is
defined as a probability that a connection cannot be established
Figure 1: topology of the Italian network
due to resource contention along the desired route. Forced ter-
mination probability is defined as a probability that a connec-
tion is terminated by force due to saturation which is brought
by another new connection establishment. Figure 2 shows the
blocking probabilities and forced termination probabilities vs
traffic load ρ which is defined as ρ = λh.
From this figure, we can see that the forced termination
probability is drastically improved when using the proposed
routing algorithm. This is because the proposed routing avoids
occurrence of saturation along a direct route. Also we can see
that the blocking probability of proposed routing is slightly
higher than that of fixed-alternate routing. This is because
the proposed routing, even if a valid wavelength assignment
is found, blocks connection requests along the direct route
when saturation occurred.
In any communication system, we believe that it is more
important to reduce the forced termination probability than the
blocking probability because the forced termination has a more
damaging effect on users. Therefore, the proposed algorithm
can make it possible to provide high quality communication.
IV. CONCLUSIONS
In this paper, we have studied the dynamic RWA problem with
power considerations in all-optical WDM networks and pro-
posed a routing algorithm that suppresses and avoids the oc-
currence of saturation. To evaluate the performance, we com-
pared the proposed routing with the fixed-alternate routing by
simulation results. It has been shown that the proposed routing
Figure 2: blocking probability and forced termination
probability versus load
algorithm significantly reduces the forced termination proba-
bility. Power constraints that we have assumed in this paper
can be more often occurred in the situation that traffic load is
heavy rather than light. Therefore, the proposal is important es-
pecially in the next generation Internet that the traffic volume
will explosively increase.
REFERENCES
[1] B. Mukherjee, Optical Communication Networks, McGraw-Hill,
New York, 1997.
[2] H. Zang, J. P. Jue, L. Sahasrabuddhe, R. Ramamurthy,
B. Mukherjee, “Dynamic Lightpath Establishment in Wavelength
Routed WDM Networks,” IEEE Communication Magazine, Vol.39
No.9, pp.100-107, Sep. 2001.
[3] J. Spath, “Dynamic routing and resource allocation in WDM
transport networks,” Computer Networks 32 (2000), pp. 519-538.
[4] N. Ghani, S. Dixit, T. Wang, “On IP-over-WDM Integration,” IEEE
Communication Magazine, Vol.38, No.3, pp.72-84, Mar. 2000.
[5] M.Ali, B. Ramamurthy, J. S. Deogun, “ Routing and Wavelength
Assignment (RWA) with Power Considerations in All-Optical
Wavelength-Routed Networks, ” Proc., IEEE GLOBECOM ’99
pp.1437-43, Dec. 1999.
[6] S. Ramaurthy and B. Mukhrjee, “Fixed-Alternate Routing and
Wavelength Conversion in Wavelength-Routed Optical Networks,”
Proc., IEEE GLOBECOM ’98, Vol.4, pp.2295-2302, Nov.1998.