Routing and dimensioning in optical networks under traffic growth models

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.