Istanbul Technical University, Institute of Sciences and Technology, April 2003
Abstract:
Communication networks reach more people everyday, providing new means
of information exchange. Consequently, traffic demand is growing rapidly,
mainly due to data-centric applications. Today,
the major technology that is promising to meet this high bandwidth demand
of networks is optical networking. Optical networks use optical fibres
as transport medium and they are designed to exploit the fibre's unique
properties. The bandwidth of a single fibre is nearly 50 Tb/s, which
can be used by dividing it into smaller bands or channels,
and using these channels concurrently. This is accomplished by wavelength
division multiplexing (WDM), where each channel operates at a different
wavelength and the electronic equipment should operate
only at the bitrate of a wavelength channel (up to 40 Gb/s), which can be
chosen arbitrarily.
It is becoming clear that IP-over-WDM (Internet Protocol over WDM) architecture will be the winning combination of the futur e, due to the success of IP as a convergence layer, and WDM as a bandwidth-rich physical layer. The challenge is to design an intelligent control plane that could realise the integration of the two layers, by solving interactive issues, such as, lightpath routing coupled with IP routing and resource management, reconfigurability, survivability, online service provisioning, monitoring.
The future's perspective for optical networking can be divided into two categories: Circuit switched, and packet switched. Packet switching technology is still in a very early stage, seen as a far future possibility by most researchers, because of several technical obstacles. Circuit switching is considered to be a realistic approach to design the optical networks for the near future. This thesis is based on a circuit switched optical layer, i.e., the main topic is wavelength-routed optical WDM networks.
Wavelength-routing is a major advantage of a WDM optical network. A wavelength-routed WDM network can provide end-to-end optical communication channels through optical fibres and intermediate nodes with optical cross-connects, even the source and destination nodes are not connected by a fibre directly. These optical channels (lightpaths) eliminate extra signal processing at intermediate nodes along the physical path through which the lightpath is routed. With the set up of a lightpath, two nodes become virtually neighbors. However, it may not be possible to establish a lightpath for every node pair, because of scalability and economic concerns. Hence, some traffic may need to be switched electronically from one lightpath to another at intermediate nodes until it reaches its destination; this approach is called multi-hopping. The processes of setting up individual lightpaths are clearly related to one another since a lightpath may carry multi-hop traffic besides the single-hop traffic between the two nodes it directly connects. For this reason, the design of the lightpath topology (virtual topology) is a combined problem of optimizing the use of network resources and network throughput, for a given traffic demand.
On the other hand, the traffic rates between node pairs of a network fluctuate distinguishably over time. The network resources can be arranged to accommodate a specific traffic matrix; however, the traffic matrix itself changes through time. In such case, a virtual topology which is optimized for a given traffic demand --which would be a snapshot of the changing traffic matrix-- may not be able to respond with equal efficiency to a different traffic demand. Thus, the virtual topology should also be changed to match itself with the changing traffic. The dynamic structure of the optical cross-connects, i.e., the ability of switching the wavelengths from any input fibre to any output fibre dynamically, allows this change in the optical layer. This is known as reconfiguration of the virtual topology. Reconfiguration problem includes the virtual topology problem by its definition. Therefore, it is also an optimisation problem of several metrics, which needs to be solved on-line, in contrast to virtual topology design problem.
WDM networks have been a popular research area in the past decade, and many algorithms have been proposed to solve the design, routing, resource allocation, and reconfiguration problems. The objective of this thesis is to provide a new perspective for the reconfiguration of wide-area WDM networks. This objective is motivated by the problems originating from the usual view of the previous approaches. As a general assumption, reconfiguration studies are based on the idea that the decision of reconfiguration is sudden, triggered by an event, and consequently virtual topology change is an interrupted process. In this view a virtual topology $V_{1}$ designed for traffic matrix $T_{1}$ remains the same until the traffic changes to a matrix $T_{2}$, which in turn triggers the design of another virtual topology $V_{2}$. On the other hand, previous studies lack to design a proper triggering mechanisms, i.e., when and how to decide to reconfigure the virtual topology in a backbone network. Another problem with this two-step approach is that the future traffic is assumed to be known. In practise, a flexible reconfiguration method should deal with dynamic traffic, even when the future traffic is different than the expected matrix. Furthermore, since the reconfiguration is a complex problem, most of the methods proposed are useful for small-size networks, even though they are local search methods. For large networks, simple and effective algorithms are needed to provide on-line reconfiguration of the optical layer.
Observations on real networks show that the traffic rates between node pairs fluctuate distinguishably over time. The difference between the traffic intensity at highest point (busy hours) and the traffic intensity at lowest point (non-busy hours) is usually remarkable. Thus, reconfiguration may be very beneficial in terms of economical use of the bandwidths. One can also observe that there are two types of variations in traffic intensity, short-term variations (typically seconds or minutes) and long-term variations (typically hours). In long-term variations, which are the reason of reconfiguration, the amount of traffic between nodes changes in a smooth and continuous manner. Therefore, a virtual topology adaptation mechanism that changes the topology slowly, can be beneficial for backbone networks that have similar traffic behaviour.
The new perspective introduced in this thesis for reconfiguring the virtual topology in WDM networks under dynamic traffic is called virtual topology adaptation. Here, the problem is defined from a new point of view, different from the traditional two-step reconfiguration. The new approach sees the reconfiguration as a continuous process of observations and adjustments. This approach eliminates the need for traffic forecasts and critical triggering decisions, while providing robustness and speed.
The new approach introduced in this thesis can be viewed as a one-step reconfiguration approach in contrast to the previous methods. It is composed of continuous observation-adjustment cycles, where small changes may occur in the virtual topology. The traffic on each lightpath is observed continuously, and a new lightpath is added to or an existing lightpath is removed from the virtual topology when a change is necessary. The adaptation process is a continuous system where small adjustments are made, instead of waiting for a noticeable drop in system efficiency and changing the entire topology. With this new definition of the problem, the aim is to solve the issues of unpredictability of the traffic, critical triggering decisions, and the delay that is introduced by complicated reconfiguration algorithms. The ultimate goal is to obtain a scheme, which is practical for real backbone networks.
The basis of the new adaptation method is to apply simple adjustments to the virtual topology when it is necessary. The periodical measurements on network traffic provides information on the lightpath loads. This information is used to decide whether or not an adjustment is needed. Basically, a new lightpath is added when a congestion is encountered, i.e., a lightpath load is dangerously high, and a lightpath is deleted if it is being under-utilized, i.e., its load is very low. Therefore, this scheme tends to balance the traffic loads evenly to the lightpaths, and to modify the connectivity of nodes when the balance changes. Two system parameters are introduced to detect the lightpath-usage efficiencies: High watermark $W_{H}$ and low watermark $W_{L}$. The traffic loads on lightpaths are measured at the end of each {\em observation period}, which is typically hundreds of seconds. At the end of an observation period, if the load of one or more lightpaths is higher than $W_{H}$, a new lightpath is establishe d to decrease that load. When the load of a link drops below $W_{L}$, that link will be torn down with one condition: if alternate paths exist for diverting the traffic that uses the considered lightpath.
The approach proposed can be used by an ISP to minimise the operational cost of its virtual topology by leasing only the appropriate amount of lightpaths as it considers to be really necessary. Previous reconfiguration and virtual topology design studies usually maximises the number of lightpaths in a virtual topology. The aim of these methods is to use all possible network resources to carry maximum amount of traffic.
On the other hand the fibre infrastructure may not belong to the ISP, in which case the ISP has to lease the lightpaths. This is a common business model in real world, hence, the topology design and reconfiguration methods are required to provide cost-efficient solutions. The new adaptation method is novel also in this sense, since it maintains only the necessary lightpaths. The new adaptation scheme is computationally simple when compared to previous studies. Simplicity is vital for a reconfiguration method, because the process should be on-line.
In this study, the adaptation method is first stated formally as a mixed-integer linear program (MILP). The performance of the new adaptation scheme is compared to an earlier reconfiguration method (optimal reconfiguration), by solving the MILP formulation. The results of this comparison shows that the adaptation scheme can reconfigure the topology using far fewer lightpath changes compared to the optimal reconfiguration.
Formulations aiming to find an optimal solution for the reconfiguration in large networks are intractable, hence heuristic approaches are needed. Therefore, in the next step, a heuristic algorithm is introduced for the virtual topology adaptation method proposed. Simulation experiments are conducted to investigate the fitness of the adaptation approach and to expose the effect of various system parameters. Various performance metrics are employed to reveal the different aspects of the adaptation scheme, such as, the average time between consecutive reconfiguration steps, the traffic-weighted average hop distance , number of lightpaths in the virtual topology, and the percentage of links with loads in the balanced region defined as $[W_{L},W_{H}]$. Through these metrics, the effects of changing the system parameters are examined, specifically, high watermark, low watermark, and length of observation period. These experiments showed that the algorithm is reacting to the load changes as expected, and the two main system parameters, namely high and low watermarks, can be effectively used to regulate the operation of the proposed virtual-topology adaptation method.
As a second contribution, this thesis proposes a bandwidth reconfiguration method called CATZ (Capacity Allocation with Time Zones), that exploits the daily traffic fluctuations and time-zone based traffic shifts to cost-effectively operate a world-wide WDM backbone network. The main assumption of this method is that, in the near future the bandwidth markets will allow fast online bandwidth provisioning for service providers. Here, the reconfiguration problem in an IP-over-WDM network is investigated from the point of view of an ISP under the light of the new challenges posed by the emerging bandwidth markets, and different service types in leasing bandwidths.
Previous studies on virtual topology design concentrate on routing the IP traffic appropriately, so that the lightpath connectivity can carry a large amount of traffic. These studies consider a constant capacity for any lightpath and do not take into account the sub-wavelength bandwidth granularities. They also contravene the objective of the ISP, to minimise the network cost for high profit; because they try to set up as many lightpaths as possible, instead of an appropriate and cost-effective working set of lightpaths. Network reconfiguration studies are similar to design studies in both aspects, and their application to future real networks is difficult.
In this work, a cost-efficient method is investigated for bandwidth allocation and bandwidth reconfiguration for global IP-over-WDM backbone networks. IP traffic is very dynamic, but in a backbone network, due to traffic aggregation, this dynamism becomes smoother, following a well-shaped daily profile. This property can be exploited by WDM technology, since wavelength-routed WDM networks provide a flexible infrastructure that can adjust the network topology (connectivity and bandwidth) by reconfiguring the optical cross-connects. On the other hand, when a world-wide network traffic structure is examined, another dimension of dynamism can be seen: traffic shifts based on the time zones. A typical traffic profile between two nodes follow a sinusoidal shape, where the peak is around midday and the valley around early hours of the morning, e.g. 03.00. Since different locations in the world are in different time zones, each node will create a traffic whose intensity changes according to that node's time zone. When this new type of dynamism is considered, the bandwidth cost of the network can be reduced, even in the design step of the virtual topology. The study in this thesis show that a large reduction on bandwidth cost can be achieved by reconfiguring the lightpath capacities.
In CATZ, the channels are observed periodically to measure the traffic intensities flowing through them, and the bandwidth of the channel for the next period is set according to these intensities. In this method, the capacities of the channels are allowed to change, since the underlying transport system, optical switches, and the global carriers are assumed to provide on-line bandwidth services. The amount of step increase or decrease can be a multiple of OC-1, since the bandwidth markets provide optical channels at capacities of OC-3, OC-12, OC-48, or OC-192. Parallel channels are also possible between nodes, as long as there are enough transceivers. The new approach is compared with two static bandwidth allocation schemes using network bandwidth cost as the performance metric. The experiments show that an important cost improvement can be obtained by using a bandwidth reconfiguration scheme that takes into consideration the dynamism of the traffic.
In summary, this thesis brings the virtual-topology reconfiguration problem to a new perspective where it is considered as a continuous process, and by using this new approach, it proposes two new methods for fast online topology adaptation. The results obtained in this thesis are encouraging for building the backbone reconfigurable WDM networks, since they show that simple and efficient algorithms that could properly manage the network resources can be designed. The new view introduced in this work, namely adaptation instead of reconfiguration, may propel new methods that are more efficient for the network operators.