Open Access
Add to BibSonomyAbstract
We propose a two-step procedure to design flexgrid-based national networks. Locations are first partitioned into a set of metro areas interconnected through a flexgrid optical network. The problem is modeled as a Mixed Integer Linear Programming (ILP). Next, each network is designed separately. Optimal results show a future large (>200 nodes) flexgrid core network inter-connecting small (~10 nodes) metro regions.
©2013 Optical Society of America
1. Introduction
The problem of designing IP/MPLS networks consists of finding the configurations of the whole set of routers and links so as to transport a given traffic matrix whilst minimizing capital expenditure (CAPEX). As a consequence of link lengths, national IP/MPLS networks have been built on the top of optical networks, and thus the design problem has been typically addressed through a multilayer IP/MPLS-over-optical approach where IP/MPLS routers are placed side-by-side of optical cross-connect (OXC) [1]. Besides, due to the coarse granularity of the current fixed-grid wavelength division multiplexing technology used at the optical layer, aggregation networks are deployed between clients and core networks to groom client flows thus increasing the spectral efficiency of the optical layer.
However, flexgrid technology [2–4], providing a finer optical spectrum granularity, allows a new approach [5,6]: IP/MPLS routers equipped with multi-flow transponders (MF-TPs) [7] are connected to bandwidth-variable (BV) OXC [8], transforming the multilayer approach into a single-layer approach where a number of IP/MPLS metro area networks performing aggregation are connected through a flexgrid-based core network (Fig. 1 ).
Fig. 1 Network design: metro areas are equipped with IP/MPLS routers. The core network is based on the flexgrid technology. MF-TPs are used to access the core network.
In this paper we propose a two-step procedure to design such networks and investigate the optimal size of those aggregation metro areas so as to deploy spectrum-efficient flexgrid-based core optical networks.
2. Network design proposed procedure
Given a national network, such as BT’s, with over 1000 node locations, a full, single step network optimization is clearly impossible. In this paper we present a two-step network design procedure which takes advantage of the separation model described above:
- 1. The network is partitioned into metro areas, i.e. locations are grouped into a number of metro areas. Internal metro area traffic between locations in the same area and aggregated traffic between metro areas is computed. Aggregation traffic will be conveyed by the optical core network.
- 2. IP/MPLS metro and optical core networks are designed, taking as input each traffic matrix computed in 1) and a network topology. An adaptation of the integer linear programming model presented in [9] can be used for the design of the core network.
Figure 2 illustrates the proposed design procedure where some data needs to be pre-computed: candidates for metro nodes can be limited to those nodes with sufficient connectivity degree and each location can have a limited subset of potential metro nodes (e.g. based on distance). In this paper we focus on the first step and the next section states the partitioning problem.
3. Metro Area Partitioning (MAP) problem
The MAP problem targets at maximizing the total aggregated traffic to be conveyed by the core network. Note that by maximizing the aggregated traffic we are indirectly minimizing the internal traffic of the resulting metro areas. That is important since the cost per bit of the optical switching technology is generally cheaper than that of the IP/MPLS and the aggregated flows in the core network occupy many spectral resources, so are most cost effectively groomed and routed optically.
The MAP problem can be formally stated as:
Given:
- • a set L of locations,
- • a subset M⊆L of locations that can be selected as metro locations,
- • the subset M(l)⊆M of metro locations where each location l can belong,
- • the location-to-location traffic matrix, and
- • the considered slot width (Δf) for the flexgrid-based core network.
Output: The set of metro areas. For each metro area m, the locations belonging to that area and its internal traffic. The set of aggregated traffic between metro areas (bmm’).
Objective: Maximize the aggregated traffic exchanged between metro areas (∑m∊M∑m’∊M bmm’) subject to ensuring a minimum spectral efficiency for the core network.
Note that spectral efficiency links the two proposed steps so that the final network design eventually minimizes CAPEX. It is defined as follows, where Bmod represents the spectral efficiency of the chosen modulation format. Note that the ceiling operation computes the amount of slots to convey the requested data flow under the chosen slot width.
The MAP problem was modeled using MILP. However, its exact solution becomes impractical when real-sized network and traffic instances are considered. Thus, aiming at providing near-optimal solutions within reasonable computational effort, the next section presents a meta-heuristic method to solve the MAP problem.
4. BRKGA heuristic algorithm
Among meta-heuristics, BRKGA [10] has proven to effectively solve network problems such as multilayer optical networks [1]. Essentially, BRKGA is a class of genetic algorithm where a set of individuals, called a population, evolves over a number of generations with the aim to produce high quality solutions in short running times. Each individual represents a solution of the problem to be solved and is encoded by a chromosome consisting of m genes where each gene takes a value in the real interval [0,1]. A deterministic algorithm, called decoder, transforms any input chromosome into a feasible solution of the optimization problem and computes its fitness value. As stated in [10], the only problem-dependent parts to specify a BRKGA heuristic are the decoder and the chromosome internal structure.
Let L1 ⊆ L be a subset with those locations which can belong to only one metro area and L2 = L\L1 be the subset with the rest of locations. In our algorithm, one gene is used for each l∊L2 so to decide to which metro area location l is parented and hence, m = |L2| genes.
Table 1 presents the decoder algorithm. First, locations in L1 are parented to its metro area (lines 1-2). Next, the rest of locations are sorted using its specific gene and parented to the best metro area as a function of the resulting outgoing traffic (lines 3-8). Finally, the total outgoing traffic is computed and returned (lines 9-13).
Table 1. Decoder Algorithm
The performance of the BRKGA heuristic was compared against the optimal solution obtained solving the MILP model over small instances where the optimal solution was found in all the tests performed.
5. Illustrative numerical results
In this section, we present the obtained results from solving a close-to-real problem instance consisting of 1113 locations, based on the BT network. Those locations (323) with a connectivity degree of 4 or above were selected as potential metro locations. A 3.22 Pb/s traffic matrix was obtained by considering the number of residential and business premises in the proximity of each location. Locations could only be parented to a potential metro node if they were within a 100 km radius. Each result reported in the following is the average of four different executions of the heuristic algorithm, each running 48 hours.
Figure 3 plots the amount of aggregated traffic for each solution from solving the heuristic algorithm when the number of metro areas is fixed. The relationship between the amount of aggregated traffic and the number of metro areas is clearly shown: more metro areas entail higher aggregated traffic to be exchanged. On the contrary, it is worth noting that the amount of aggregated traffic does not depend on the slot width. As a result of the problem’s objective, i.e. maximizing the amount of aggregated traffic, its increment when all the 323 metro areas are opened is only 6% with respect to just 20 areas.
Fig. 3 Aggregated traffic (left) and spectral efficiency (right). The horizontal line (red) represents spectral efficiency = 0.8.
In order to understand the behavior of the core network spectral efficiency, this has been included as part of the objective function to be maximized. Therefore, plots in Fig. 3 show the maximum spectral efficiency of the solutions as a function of the slot width and the number of metro areas selected.
As illustrated, network spectral efficiency decreases sharply when the number of metro areas is increased since more flows with lower amount of traffic are transported over the core network. Note that the traffic matrix to be transported by the core network has |M|*(|M|-1) unidirectional flows. Let us consider a threshold for spectral efficiency of 80% (horizontal red line in Fig. 3). Then, the largest number of metro areas is 116, 165, 216, or 295 when the 50, 25, 12.5 and 6.25 GHz slot width, respectively, is selected. Obviously, the coarser the grid granularity chosen for the optical network, the larger the metro areas have to be for the spectral efficiency threshold selected and thus the lower the number of metro areas opened.
Figure 4 presents the details of the solutions as functions of the number of metro areas, while Table 2 focuses on the characteristics of those solutions in the defined spectral efficiency threshold for each slot width. Note that plots in Fig. 4, as for Fig. 3, are valid irrespective of the slot width used, since no spectral efficiency threshold was required.
Fig. 4 Details of the solutions against the number of metro areas. Max, min, and average plots are shown.
Table 2. Solutions Details (Spectral Efficiency = 0.8)
In Fig. 4(a), the size of the metro areas is represented. Note that in the reference interval [116, 295] the average number of locations in each metro area is lower than 10, being lower than 20 for the largest metro area. This limited metro area size simplifies the design of those IP/MPLS networks. Besides, switching capacity of metro edge IP/MPLS routers is proportional to the size of the metro areas as shown in Fig. 4(b). They require capacities of up to 58 Tb/s (28.5 Tb/s on average) when the 50GHz slot width is used, decreasing to 28.5 Tb/s (11 Tb/s on average) for 6.25GHz. Hence, finer slot widths might keep routers to single chassis size - far more efficient and cost effective.
Figure 4(c) surveys the size of the metro area internal data flows (flows where at least one end router is in a given metro area). In the reference interval, the size of the internal flows is up to 72 Gb/s, 32 Gb/s on average, when the 50GHz slot width is used, decreasing to 38 Gb/s, 15 Gb/s on average, when the 6.25 GHz slot width is used. Finally, Fig. 4(d) examines the size of the aggregated data flows in the core network. When the number of metro areas is low, the size of the aggregated flows is quite large but the overall size of the traffic matrix is quite small: the largest flow conveys 19 Tb/s although there are only 380 aggregated data flows. In comparison, when the number of metro areas is large, the size of the largest flow is smaller but the size of the core network traffic matrix is very large: the largest flow conveys 203 Gb/s but there are as many as 104,000 aggregated data flows.
In the reference interval (see Table 2), the size of the aggregated flows is up to 989 Gb/s, 264 Gb/s on average, when the 50GHz slot width is used, decreasing to 223 Gb/s, 39 Gb/s on average, when the 6.25 GHz slot width is used. The size of the optical network traffic matrix increases from 14,000 to 48,000 unidirectional flows when the 50 and 12.5 GHz slots widths are selected.
6. Conclusions
A two-step procedure to design flexgrid-based national networks consisting of a set of metro areas interconnected through a flexgrid optical core has been proposed. The MAP problem to partition the network into metro areas has been stated and solved for the BT network.
Results showed that simpler and smaller metro areas containing 10-15 locations are enough to obtain good spectral efficiency in the flexgrid-base core network when 12.5 or even 6.25 GHz slot widths are used.
Acknowledgments
The research leading to these results has received funding from the European Community’s Seventh Framework Programme FP7/2007-2013 under grant agreements no. 247674 STRONGEST and no. 317999 IDEALIST projects and by the MINECO through the TEC2011-27310 ELASTIC project.
References and links
1. M. Ruiz, O. Pedrola, L. Velasco, D. Careglio, J. Fernández-Palacios, and G. Junyent, “Survivable IP/MPLS-over-WSON multilayer network optimization,” J. Opt. Comm. Netw. 3(8), 629–640 (2011). [CrossRef]
2. M. Jinno, H. Takara, B. Kozicki, Y. Tsukishima, Y. Sone, and S. Matsuoka, “Spectrum-efficient and scalable elastic optical path network: architecture, benefits, and enabling technologies,” IEEE Commun. Mag. 47(11), 66–73 (2009). [CrossRef]
3. M. Jinno, B. Kozicki, H. Takara, A. Watanabe, Y. Sone, T. Tanaka, and A. Hirano, “Distance-adaptive spectrum resource allocation in spectrum-sliced elastic optical path network,” IEEE Commun. Mag. 48(8), 138–145 (2010). [CrossRef]
4. O. Pedrola, A. Castro, L. Velasco, M. Ruiz, J. P. Fernández-Palacios, and D. Careglio, “CAPEX Study for a multilayer IP/MPLS-over-flexgrid optical network,” J. Opt. Comm. Netw. 4(8), 639–650 (2012). [CrossRef]
5. O. Gerstel, “Flexible use of spectrum and photonic Grooming,” Proc. Photonics in Switching (2010).
6. M. Jinno, Y. Sone, H. Takara, A. Hirano, K. Yonenaga, and S. Kawai, “IP traffic offloading to elastic optical layer using multi-flow optical transponder,” Proc. ECOC (2011).
7. H. Takara, T. Goh, K. Shibahara, K. Yonenaga, S. Kawai, and M. Jinno, “Experimental demonstration of 400 Gb/s multi-flow, multirate, multi-reach optical transmitter for efficient elastic spectral routing,” Proc. ECOC (2011).
8. G. Wellbrock, “The convergence of L1/2/3 functionality in next generation network elements: a carrier’s perspective,” Proc. OFC/NFOEC (2011).
9. L. Velasco, M. Klinkowski, M. Ruiz, and J. Comellas, “Modeling the routing and spectrum allocation problem for flexgrid optical networks,” Springer Photonic Network Communications 24(3), 177–186 (2012). [CrossRef]
10. J. Goncalves and M. Resende, “Biased random-key genetic algorithms for combinatorial optimization,” J. Heuristics 17(5), 487–525 (2011). [CrossRef]
