Routing and dimensioning in circuit switched networks pdf

We assume here that we are given a demand matrix with bandwidth entries. Each entry is lower or equal than the maximum capacity of a lightpath. In the following subsection we present the general solution approach and apply it to a network example.

More details can be found in 0. Solution Approach Due to the RWA problem alone, the whole problem becomes too complex to be solved by means of integer linear programs 0, 0. Therefore we divide the problem into three sub-problems, and solve each by a heuristic algorithm. In the first step we find a virtual topology such that the number of virtual links is minimized and the given IP demand is carried in a greedy manner 0.

Minimizing the virtual links corresponds to minimizing the lightpaths demanded from the WDM layer and thus the laser sources. In the next step, we route the lightpath demands in the optical network using a shortest path algorithm. In the last step we have to assign wavelengths to the paths taking into account the wavelength constraint in fibres and the wavelength continuity constraint in OXCs. In general, one is given a set of wavelengths which can be used network-wide, thus it is sufficient to obtain one feasible assignment.

The wavelength assignment problem is related to the graph colouring problem 0. Efficient graph colouring algorithms exist, which do not only perform a colour assignment but also minimize the number of colours wavelengths. We used this optimization approach for the wavelength assignment to provide efficient wavelength utilization throughout the network. It must be noted that there may be cases where the minimum number of colours obtained exceeds the cardinality of the wavelength set given through the system.

Case Study We used the described approach to configure the topology of the NSF network 14 nodes, 21 links used in 0, where we associated each link with a fibre pair and each node with a router connected to an OXC. In the case without constraints on the number of hops we obtain 19 virtual links this is half of the number of laser sources and 4 wavelengths. The number of 19 virtual links is close to 13, the minimum number of links needed to connect the network.

This is still reasonable, since many demand-pairs in 0 carry much more traffic in one direction than in the other. Moreover, all nodes have to be connected, even those that do not source or sink much traffic.

Both functions are decreasing monotonously and from 1 hop to 2 hops, the function graphs drop down very much, since IP multiplexing becomes possible. More results are included in 0. Thus, we do not take into account the cost of WDM equipment 0. In addition, the layer 2 topology does not necessarily follow the physical topology. We assume the physical topology to be given, i. The traffic matrix between layer 2 nodes is also known and traffic demands in layer 2 are routed along the shortest paths in layer 1 i.

We finally assume that the number of fibres on the links is unlimited. In 0, three scenarios to obtain a layer 2 topology are presented: 1. For large networks, finding an optimal solution is an NP-hard problem. Hence, a genetic algorithm GA is used to obtain a near-optimal layer 2 topology. From our point of view, the application of the chosen scenarios is most probable in the near future 0. Here we assume that in case of the shared protection type, the traffic load is equally divided between the working and backup interface.

Topologies with dual link and dual link dual router type of protection are more expensive, but their performance is better in terms of potential packet loss. It can be seen that with growing traffic load, the cost of optimal topology increases almost linearly. This is from the viewpoint of network evolution one of the most probable architectures for future IP backbones.

Assigning low-bandwidth electrical connections to high-speed optical lightpaths, also known as traffic grooming, is an important aspect in such networks 0. Routing on the electrical and optical layer is an essential component of every grooming strategy.

Efficient transport of dynamic traffic demands requires optimised multi-layer routing and grooming algorithms. Non-integrated routing schemes treat both layers separately while integrated schemes try to improve the performance by combining both layers. Most approaches for integrated routing, e. However, the overlay model is favoured from an operator point of view as information on transport networks is very sensitive and should be kept secret.

This model comprises an optical cross-connect OXC on the optical layer, which is assumed to be non-blocking. The electrical layer mainly consists of a non-blocking electronic cross-connect EXC , which is able to switch electrical connections at an arbitrary granularity.

The EXC thus allows for an effective grooming of electrical connections. In a centralized routing scheme, the routing control centre has to choose a path within the network for each connection request. Four basic grooming options can be identified: A single-hop grooming on existing lightpath: Assign connection to one existing direct lightpath.

B multi-hop grooming on existing lightpaths: Route on the electrical layer by using more than one existing lightpath. C single-hop grooming on new lightpath: Set up a new lightpath and route connection via this lightpath. D combined multi-hop grooming on new and existing lightpaths: Combination of A and C. Route connection by using a series of existing and new lightpaths.

Non-integrated routing schemes are capable of grooming on either existing or new lightpaths. Only with integrated routing does the routing control centre have enough information to also perform the combined grooming described in D. In contrast to the non-integrated routing schemes, WIR applies the different grooming strategies in parallel, including combined grooming. For a connection request, each possible path that results from a grooming strategy is rated according to a set of criteria.

Finally, the path with the best rating is chosen. Finding paths with combined grooming is harder than applying grooming purely on the electrical or optical layer.

Simulation Studies The presented simulation study was performed using a fictitious 9-node German network, the topology of which is shown in figure 3. This network was introduced and dimensioned for static traffic demands 0 such that links contain a certain number of fibres each holding 8 wavelengths. For more details on the simulation scenario see 0.

For a multi-layer node, the number z of transponders is a crucial parameter, from a performance as well as a cost point of view. Particularly, for a given network topology, transponders are the major variable cost factor. Hence, we introduce the fraction of transponders installed as the absolute number of transponders installed normalized by sum of all possible transponders in all nodes.

For more details on this see 0. The non-integrated routing scheme PreferOptical outperforms the scheme PreferElectrical by almost one order of magnitude. The integrated WIR achieves a request blocking probability that is about one order of magnitude below the best non-integrated scheme and slightly below SLRC. There is a noticeable bend in all curves at a fraction of about 0.

For lower fractions, the request probability is dominated by blocking at the transponders. For larger fractions, there are sufficient transponders available so that wavelength blocking dominates. They reduce the blocking probability in the network as well as increase the usage of the wavelength channels. Multi-layer traffic engineering in data-centric optical networks. The logical IP topology in multi-layer data-centric optical networks is supported by lightpaths, which can be set up or torn down dynamically in Intelligent Optical Networks IONs.

While regular traffic engineering TE typically only routes traffic in the IP layer, the ability to reconfigure the logical IP topology on demand leads to cross-layer traffic engineering capabilities.

What is Multi-layer Traffic Engineering and how does it work? Multi-layer Traffic Engineering allows reconfiguring the logical resources. To realize this however, a MTE process goes through three distinct phases 0. Firstly, the traffic over the logical topology needs to be monitored, either physically on the router interfaces, or by keeping track of bandwidth specification included in signalling messages.

Problems may be detected, optionally signalled through the network, so as to trigger the next step, the decision taking phase. Here, the MTE strategy will find an appropriate reconfiguration of the logical topology, given the monitoring data. It will decide which logical IP links to set up and tear down, and also which traffic to attract to newly established links.

Designing IP over WDM networks 97 Lastly, once the reconfiguration has been decided on, corresponding MTE actions still need to be performed during the realization phase. The logical network layer will use signalling to request new lightpaths from the optical layer, or to remove existing lightpaths.

It will also adjust IP routing to make sure the new logical topology is used efficiently. Issues in designing Multi-layer Traffic Engineering Strategies Strategies can be classified according to a number of properties, some of them having analogies in classic TE.

One aspect is the overall architecture of the network and strategy. Calculations may run either online or offline, and in the latter case, the strategy can be centralized, as opposed to being distributed. Also important is the distinction between peer also called integrated and overlay models in multi-layer networks. Furthermore, algorithms themselves can vary in complexity, because of the number of alternative actions considered, and the extent to which multi-layer actions interact with Single- layer Traffic Engineering STE actions i.

The specific objective of the strategy is another property. Not just what this objective is, but also how it is reached; either by keeping the network optimal at all times a proactive strategy , or by only reacting to certain problems that have been detected first a reactive strategy.

Further issues exist however, a certain amount of inertia may need to be introduced in the strategy to lower the number of lightpath operations, at the cost of a somewhat lower optimality of the logical topology. Care has to be taken then to avoid cumulative memory effects and other potential instabilities. A reactive strategy was chosen. It defines both lower and upper thresholds for bandwidth usage of an IP-link.

Exceeding these bounds triggers the process which removes underloaded links or sets up new links to remove congestion. The choice of the new link and also the amount of traffic attracted over it, are optimized so that load on routers is reduced as much as possible, and bandwidth utilization of both previously congested and newly established link approaches an ideal mean between both thresholds.

Traffic volume is increased in steps, and from 60 sec. The reactive strategy however can keep PLR satisfactory small by provisioning additional lightpaths, at the cost of slightly higher optical bandwidth usage under nominal traffic sec. More details on this case study and further studies can be found in 0, 0 and 0. MTE algorithms can be approached from a number of different perspectives, and once some design issues have been taken care of, they yield significantly better performance than strategies which use statically dimensioned logical topologies.

Influence of traffic asymmetry on the network design IP traffic is, in contrast to telephone traffic, asymmetric. The degree of asymmetry depends of course on the exact location in the network access versus backbone network, in the surrounding of a server farm or not, etc.

Using unidirectional WDM line-systems instead of the currently in use bidirectional ones, could thus lead to a significant cost reduction. In this section, this cost advantage will be quantified for three of the COST optical backbone topologies discussed in the introductory chapter. More details can be found in 0, 0, 0 and 0, from which most of this section is extracted.

Assumptions and definitions First the traffic model explained in chapter 1. The capacity installation problem in the optical layer was then solved for a the case that the line-systems in the optical layer are bidirectional and b the case that these line-systems are unidirectional, and this for the BT, RT and TT.

The cost of a bidirectional line-system was assumed to be twice the cost of a unidirectional one. The logical layer on top of these optical networks was in all cases assumed to be a full mesh.

Results The result of these network designs is shown in figure 3. Regardless of the AF of the traffic demand, the design for the ring network is always the most expensive one, while that of the triangular network is the least expensive. The cost of a network design is then determined by the total length of used fibre, and not by the total duct length.

The total length of used fibre is largest for the RT, as the connections have to follow on average a longer path between source and destination than in the BT and TT shortest path in km. This is of course due to the fact that the average filling of the bidirectional line-systems decreases as the AF of the traffic demand increases: only one direction of the bidirectional line-systems gets properly filled. With unidirectional line-systems, less line-systems can be installed on one direction of a link than on the other, and all line-systems are thus properly filled up.

Providing Optical VPN services 3. The term virtual network denotes that the network is not built physically and separately, but is only an allocated part of the resources of a public network of a provider. It is private since it serves a closed group of users.

The open objective is how to set these OVPNs in such a manner that all user needs are satisfied while using as few network resources as possible. Overview Figure 3. Since these routers are not connected in a full mesh by wavelength paths, the optical edge switches O1-O4 will have to provide MPLS router functionality as well between certain domains and users. The objective of the optimisation is in all cases to reduce resource usage at higher electrical layers i. The last two are based on the MPLS technology.

The deployment of VPNs grows in Enterprise networks according to 0. This paper also mentions provisioning end-to-end VPN services across multiple service providers and carriers. VPNs share the link bandwidth and the node resources among each other. This idea has several advantages. We do not have to build separate private physical networks, but only to configure VPNs. This reduces costs and speeds up provisioning. Furthermore, the VPNs can be dynamically reconfigured or re- dimensioned in contrast to physical networks.

This allows sharing resources between various VPNs. In 0 dynamic relations are in scope with capacity resizing and stochastic fair sharing, but without protection.

The resource allocation in conjunction with the routing design has been analyzed in 0, 0 and 0 over multi-service networks with QoS constraints. Various tools are used, e. Network dimensioning is addressed in 0 and the methodology is presented for determining the sizes of VPNs. An algorithm of very low complexity is presented in 0, however, the traffic streams are not handled separately pipe model , but an aggregate traffic which has source or sink in one network node are handled jointly hose model.

The protection is not handled at all. All above papers configure VPNs over a network capable of performing multiplexing, e.

There are multiple papers discussing the architecture and configuration of VPNs 0 0. However, very few papers deal with the protection of these VPNs. Links of different VPNs can share a single wavelength path. This wastes the resources in some cases, however the control is simple. If the capacity of a wavelength path is not sufficient to accommodate a link of the VPN we allow use of multiple even parallel wavelength paths.

The advantage is that the traffic of different VPNs is separated and isolated , which simplifies management and enhances security. Compared to T1 it also decreases the load of the electrical layer. If we have demands of low capacity, T1 is preferred, while for point-to-point connections approaching the capacity of a wavelength T3 is preferred. In all cases we assume traffic grooming 0, i. In all Virtual Router nodes these traffic streams can be re-multiplexed. This can be done at the electrical layer only since re- multiplexing, i.

For this reason, taking not only the optical, but both, optical and electrical layer into account when configuring the system is demanded. These methods can be generalised for the design of OVPNs, as well. Our goal is to configure the VPNs and the lightpath system optimally without separating the network layers.

This improves the quality of the results; however, the complexity of the problem grows. Based on the level of decomposition we differentiate three methods denoted as M1, M2 and M3 for the OVPN configuration and they are described in detail in 0 and 0. Although this gives the globally optimal solution it is useless, due to its complexity. Therefore, less complex methods are needed that provide results close to the global optimum.

The complexity is significantly lower; however, the quality of the results can be poor. For example setting up the first VPN can hinder setting up some other VPN by monopolising some of the common resources. Furthermore, this approach heavily depends on the order in which the VPNs are set up. This method is very useful if the demands for VPNs are not known in advance, appear one-by-one, and have to be satisfied without waiting for the other demands for VPNs that will arrive.

This is the simplest method; however, the results might be poor. Here we need some heuristic tricks. A promising approach is to sort demands, and to start by those that need larger bandwidth, and are limited in length.

Another possible heuristic approach is to decrease the cost of the links that are already used by the considered VPN when one new demand of that VPN has to be routed. The third heuristic decreases the costs of those wavelengths that are already used by the considered VPN.

Using these three heuristics jointly improves the obtained results significantly, 0 presents these results. In case of Internal protection, the OVPN users get enough resources not only to carry their traffic in a failure-free case, but also to switch to alternative paths in case of a failure.

This will of course require adequate resource management and protection mechanisms. External protection is simpler for users, but more complex for the operators.

The protection paths can be made either link or node disjoint with the working path. Furthermore, dedicated and shared protection can be differentiated. The focus was limited to circuit-switched optical networks. The impact of the client network — in the future this will typically be an IP-MPLS network — and recovery capabilities were often taken into account due to their importance. The first topic studied concerns control plane architectures for such networks.

There exist several control plane models for IP over Optical networks. In the overlay model, both layers have an independent control plane. The peer model integrates both control planes into a single integrated control plane controlling both layers which is mainly favourable from a technical perspective.

The augmented model is a compromise between both extremes. In order to enable more advanced and flexible provisioning scenarios of a global reach e. For this purpose the novel MPE architectures, incorporating dynamically provisioned inter-domain interconnections, and leveraging flexibility of peer and augmented interconnection schemes, has been proposed and studied. Both have technical pros and cons, and both need many extensions and adaptations because neither of them completely supports all the optical control plane requirements.

In a first case study, two novel RWA algorithms have been compared with each other. TABUCOL searches the shortest path based on a routing weight that increases with an increasing number of occupied wavelength channels on a link. RWA searches all disjoint shortest paths and selects the less congested one. It was shown that the former one performs best in case of a rather high number of wavelength channels per fibre, while the latter performs best in case of less wavelength channels per fibre.

It was also found that the use of wavelength converters would often not reduce the number of required fibres. This technique reduces the signalling overhead by flooding new link states after a fixed number of wavelength channels changed their status and provides bypass routes to circumvent potential blocking on links defined as being congested. In a second part, the RWA-problem is extended to incorporate network recovery.

It has been shown that the capacity efficiency of shared-span protection and p-cycles is comparable to that of shared path protection. The capacity efficiency of dedicated path protection and m:n protection are also comparable to each other but is significantly higher than that of the previously mentioned recovery schemes. Finally, dedicated span protection requires the highest amount of spare capacity. It was also found that the wavelength continuity constraint in network without wavelength converters severely impacts the capacity efficiency of p-cycles.

Not only the impact of network recovery in meshed networks was investigated, but also a heuristic has been developed to design multi-ring networks. In the last case study, it was shown that the impact of the uncertainty — modelled as a probability distribution function — on the expected traffic volumes may become very large, when a tight confidence interval is considered.

The third topic studied in this chapter differs from the second one in the sense that it studies the design of multi-layer IP-over-WDM networks. A distinction is made between static and dynamic techniques. For the static case, the first case study showed that limiting the number of hops along the shortest path in the logical IP network may significantly increase the number of logical links needed in the logical IP network and thus also the number of required wavelengths in the underlying optical network.

By having an integrated routing strategy, allowing the connection to be routed over a chain of existing and new lightpaths, the blocking probability is reduced even further. This case also showed the important impact of the fraction of installed transponders on the blocking probability. In the second case study, the benefit of dynamically reconfiguring the logical IP network was illustrated: it allows keeping the packet loss ratio reasonably low, while the physical resources are only used in case they are really needed.

In addition to that, some other issues concerning dynamic reconfiguration of the logical IP network have been discussed e. In the last case study, the impact of the typical asymmetric nature of the IP traffic has been investigated: the higher the traffic asymmetry, the more beneficial it becomes to deploy unidirectional line-systems, compared to bi- directional line-systems having the same amount of capacity in both directions.

The fourth topic studied in this chapter classified optical VPNs, and proposed methods for their configuration including protection alternatives.

Since this problem is very complex, it must be decomposed into smaller sub-problems, which can be solved for networks of practical interest. One of the most useful decomposition strategies is to route the demands one-by-one, sorted according to their bandwidth requirements and distance, as well as to apply a link-cost scheme, that prioritizes the use of wavelengths and links that are already used by demands of the considered VPN.

The demand-by-demand decomposition allows using any method for routing and wavelength assignment or protection described in the preceding sections of this chapter. Future research will need to focus on the control plane architectural components, their functionalities and the way they organize in the distributed MPE overlay to support different interconnection models. In this context modelling of the multi-layer exchange point, which is the basic building block of this architecture, needs to be given special attention.

The aim is also to generalize this 2-layers model to a multi- layer hierarchy. Future research should also focus on improving and concretizing the O-PNNI protocol to support all the optical control plane requirements.

With respect to the second topic studied in this chapter, i. It will be crucial that this is done in such a way that the performance of these RWA algorithms does not deteriorate.

Future research should also focus on extending the BBOR mechanism in order to make it applicable to networks with conversion capabilities: this may result in novel routing algorithms.

Based on this, the impact of the conversion capabilities on the blocking probability will be examined: this may lead to the conclusion that the BBOR mechanism can act as potential alternative solution for improving the network performance to the solution that simply adds wavelength converters.

Another research topic might concern analyzing the potential usage of the BBOR mechanism when proposing integrated routing strategies which take into account the collaboration of both the IP and optical layers.

Taking into account the available signal and switching capabilities of optics, it would be interesting to develop new protection schemes specifically tailored to the WDM layer. Efficient heuristics are needed when an ILP formulation is not tractable. Another key issue for future research is the robustness of the network design when the dynamism of the traffic pattern in the transport networks increases and when traffic patterns become more unpredictable. Colle, M. Kompella, and Y. Tomic, A.

Bungarzeanu, J. Ehrensberger, D. References [17] P. Strahm, and C. Baroni, and P. Grover, and D. Schupke, C. Gruber, and A. Ghani, S. Dixit, and T. Schupke, and D. Ramaswami, and K. Ljolje, R. Inkret, B. Necker, C. Gauger, S. Zhu, B. References [37] M. Kodialam, T. More Filters. The realisation of optical network architectures may hold the key to delivering the enormous bandwidth demands of next generation Internet applications and services.

Highly Influenced. View 19 excerpts, cites background and methods. View 4 excerpts, cites methods and background. Calculation of the performance measurements for elastic optical OFDM networks. Photonic Network Communications. View 6 excerpts, cites methods and background. Abstract We develop an analytical method for calculating the burst loss probabilities in a tandem Optical Burst Switched OBS network with a bursty arrival process, depicted by an Interrupted Poison … Expand.

View 10 excerpts, cites background and methods. A two-moment performance analysis of optical burst switched networks with shared fibre delay lines in a feedback configuration. View 8 excerpts, cites background and methods. Analytical model of optical burst switched networks with share-per-node buffers. View 4 excerpts, cites methods.

View 6 excerpts, cites background and methods. Simplified overflow analysis of an optical burst switch with fibre delay lines.