| dc.description.abstract | With the rapid growth of the Internet and the World Wide Web, we are seeing a relentless
demand for networks of higher and higher capacities, at lower and lower costs. Fiber
optics and wavelength-division multiplexing (WDM) are evolving as the technologies that
can satisfy the huge bandwidth requirements of the network today, providing cheap and
/
reliable high-speed communication over long distances. Traffic between pairs of nodes are
carried through lightpaths, a high-bandwidth end-to-end circuit, occupying a wavelength
on each link on the path between the two nodes. Nodes are equipped with optical crossconnects
(OXCs) which can selectively drop and add some of the wavelengths locally, switch
wavelengths from one input port to another and are able to change the wavelength of an
incoming lightpath to any of the outgoing wavelengths. With this wavelength conversion
capability, an optical network can be modelled on the same lines as a conventional circuit
switched network, for example, a telephone network. However, a nonstationarity condition
should be considered for an optical network as we will see.
We are interested in designing a WDM network so that it becomes capable of delivering
bandwidth in a flexible manner where and when needed and the operator can deliver the
connections immediately once the bandwidth is requested. The key aspect of designing
a flexible WDM network is the design of routing and dimensioning methods. The goal of
routing is to direct user traffic from source to destination through appropriate lightpaths
in accordance with the traffic抯 service requirements and the network抯 service restrictions.
A network dimensioning method determines the number, and more generally, the set of
wavelengths that must be provided to the WDM links so as to meet the network performance
while minimizing the cost. Moreover, it also determines the sizes of the network
in
elements. Traditional routing and dimensioning methods were designed based on blocking
probability models assuming the network was in a steady-state condition. For optical
networks, lightpaths are long-lived and the average holding time of a lightpath may be of
the order of several months or a year. Hence stationary blocking probability models are
not appropriate to handle the explosive growth of bandwidth demand today as the traffic
is growing constantly and unpredictably without reaching an equilibrium. Moreover, in
optical networks, lightpaths carry data at very high bit rates and are typically set up on
a p r o v i s i o n i n g b a s is . The longevity, combined with the cost of a high bandwidth lightpath
today, means that a network operator is unlikely to reject a lightpath request. Rather, he
would like to upgrade his network by the addition of more capacity on existing links in
order to accommodate the lightpath request. Hence an optical network should be designed
so that the operator can deliver bandwidths to all the customers anywhere, anytime and is
unlikely to lose any customer to the competition. Such a dramatic shift in the environment
requires a fundamental shift in network architectures.
It is difficult to predict the traffic patterns for over long periods of time due to its
dynamic nature created by emerging broadband and Internet applications. So, in contemporary
practice, the design of WDM networks is accomplished by forecasting a certain
fixed, traffic matrix between the nodes for a short time. This forecast is revised every six
months or so, and based on this forecast, the network is upgraded with the addition of more
capacities on the WDM links, or more links, or additional nodes, or a combination of these
approaches. In this work, we propose a routing and dimensioning method based on a t r a f f i c
g r o w t h m o d e l assuming the network topology and the traffic patterns are given, in lieu of a
sequence of fixed traffic matrices. We are interested in routing the traffic and dimensioning
the links so that the first lightpath request rejection will occur, with high probability,
after a specified period of time T . Here we introduce the concept of c a p a c i t y e x h a u s t io n
p r o b a b i l i t y or simply the e x h a u s t io n p r o b a b i l i t y -the probability that at least one lightpath
request will be rejected in the time period (0, T ) due to lack of bandwidth/capacity on
some link. So rather than designing a network to achieve a certain blocking probability, it
is more appropriate to design it to achieve a certain exhaustion probability over some time
period, say six months or one year. This is the time period for which the network has been
Synopsis____________________ ______________________ __________________________________ ^
Synopsis
designed and the capacities will need to be upgraded before the end of this period. This
provides a reasonable model for the design of an optical network today.
For the traffic growth model, we generally assume that the lightpath requests arrive randomly
according to a time-varying Poisson process and hold for a random time with a given
distribution of finite mean. We obtain an exact solution of the routing and dimensioning
problem under an asymptotic regime where both the capacities and the arrival rates are
large. We find that the least cost paths are the optimum routes and the capacities can be
obtained immediately from the asymptotic analysis of the individual links independent of
the lightpath holding time distribution. Least cost path routing also provides a recisonable
routing model for moderate link capacities.
For moderate capacities, the dimensioning method is proposed based on a traffic growth
model and it eventually results in a nonlinear optimization problem with cost minimization
as the objective and route exhaustion probabilities as the constraints. For exponential holding
time distribution, exhaustion probability can be computed from the transient analysis of
a multi-dimensional Markov chain model. However, computation of exact exhaustion probabilities
requires large computing resources and is thus feasible only for small networks. For
large networks, we introduce a reduced load approximation method to estimate the route
exhaustion probabilities based upon the assumption that the links are independent but
the arrival rates are thinned. We show that the estimates of the exhaustion probabilities
converge in a limiting regime in the desired range.
For a general holding time distribution, we propose a method to estimate the exhaustion
probability of a single link based on the asymptotic results. The route exhaustion probabilities
of a large network are estimated based on the individual link exhaustion probabilities
assuming the links are independent. We show that this method has a low computational
complexity and is quite accurate in the desired range.
We formulate the dimensioning problem as a nonlinear optimization problem with route
exhaustion probabilities as the constraints. This formulation involves a rather large number
of variables and many nonlinear constraints. Thus a straight forward approach to the
solution may not be feasible, except for some small networks. We propose a problem
transformation that significantly simplifies the problem and is useful in calculating the link
capacities using numerical techniques.
The traffic growth model is designed for time-varying Poisson arrivals where the arrival
rates are continuous functions of time. This model is also applicable for constant rates of
traffic arrivals, for which, the exhaustion probability of a single link can be obtained from
the transient analysis of a birth-death process involving the eigenvalues of the associated
transition rate matrix. However, the constant rate assumption is applicable only in restricted
environments where the traffic growths are low, though it significantly simplifies
the network design problem and thus reduces the computation. For exponential holding
time distribution and constant rates of traffic arrivals, we also solve the dimensioning problem
using the traditional blocking model for large circuit-switched networks. We show
how the exhaustion probability model outperforms the blocking probability model for a
moderately large network with time-invariant arrival rates.
The model we have considered is that of an optical network under a traffic growth model
assuming the traffic between different nodes is measured in terms of lightpath capacities.
This model is also applicable if the traffic is measured in terms of leased-line capacities.
Moreover, this model can be extended to the design of an optical network consisting optical
add/drop multiplexer (OADM) nodes with optical pass-through lightpaths. It can also be
extended to consider work as well as protection capacities. | |
