Andalucía assesses the investment needed to deploy a fiber-optic network

ANDALUCÍA ASSESSES THE INVESTMENT NEEDED TO DEPLOY A FIBER-OPTIC NETWORK Pablo Cortes [email protected] Ingeniería de Organización. Escuela Superior de Ingenieros. Seville University. Camino de los Descubrimientos s/n, 41092. Seville (Spain) Jesus Muñuzuri [email protected] Asociación de Investigación y Cooperación Industrial de Andalucía (AICIA). Camino de los Descubrimientos s/n, 41092. Seville (Spain) Luis Onieva [email protected] Asociación de Investigación y Cooperación Industrial de Andalucía (AICIA). Camino de los Descubrimientos s/n, 41092. Seville (Spain) Juan Larrañeta [email protected] Ingeniería de Organización. Escuela Superior de Ingenieros. Seville University. Camino de los Descubrimientos s/n, 41092. Seville (Spain) Juan M. Vozmediano [email protected] Ingeniería Telemática Escuela Superior de Ingenieros. Seville University. Camino de los Descubrimientos s/n, 41092. Seville (Spain) Jose C. Alarcon [email protected] Secretaría General de Sistemas de Información y Telecomunicaciones. Consejería de la Presidencia. Junta de Andalucía. 1 Abstract. The setup of fiber-optic telecommunication networks involves high investment efforts. The Regional Government of Andalusia assigned us the development of a tool capable of evaluating the deployment cost of a network that was not to be limited only to connecting large cities, but also to include smaller towns, in order to prevent them from staying behind the progress of the Information Society. The Andalusian regional Government aimed to deploy a network capable of accessing most of the municipalities in the region, even those municipalities that could not be profitable from a monetary perspective. We developed a nonlinear mathematical programming model with special focus on the investment costs. The costs included the parts corresponding to the civilengineering works, as well as those related to the telematic link deployment. The solution of such a complex problem was found by a genetic algorithm, which was previously tested with a set of trial problems. The results were used to persuade private companies to expand their fiber-optic networks to reach small towns. The concept of information highway has come to mean high-speed telecommunication networks. These networks require an infrastructure that will support the long-distance exchange of information via electronic means, required for different business activities. The future information super-highway will have to combine in a single infrastructure the best features of all the required networks; it will need a bandwidth that will guarantee the quality necessary for television, interaction among customers, and secure financial and commercial transactions. The development of switching techniques, bandwidth sharing, and fiber-optic transmission makes possible networks that provide high quality, and integrate many services under the same user interface. 2 To establish a standard for the information highway, in the 1980s, the International Telecommunication Union (ITU) proposed deploying the fiber-optic network with transmission by means of synchronous digital hierarchy (SDH), and switching via the asynchronous transfer mode (ATM) (Sexton and Reid, 1997). While Europe adopted the SDH standard, the USA adapted the synchronous optical network (SONET), proposed by the American National Standards Institute (ANSI), which is a similar but somewhat different standard (table 1). The following table depicts the relation between standards, as well as the corresponding equivalent optical level and the capacity in Mbps. Optical level Capacity (Mbps) SDH (ITU) a SONET (ANSI) b OCc-1 51.84 STSd-1 - OC-3 155.52 STS-3 STMe-1 OC-9 466.56 STS-9 - OC-12 622.08 STS-12 STM-4 OC-18 933.12 STS-18 - OC-24 1244.16 STS-24 - OC-36 1866.24 STS-36 - OC-48 2488.32 STS-48 STM-16 Table 1: The European Union and the USA have adopted different transmission standards for fiber-optic networks. Depicted here is the relation between both standards, as well as the corresponding equivalent optical level and the capacity in Mbps (a Synchronous Digital Hierarchy - International Telecommunication Union; b Synchronous Optical NETwork - American National Standards Institute; c Optical Carrier level; d Synchronous Transport Signal level; e Synchronous Transport Module level). 3 In Spain, the deployment of cable networks is far less extensive than it is in other western countries such as the US and Belgium. The Andalusian Regional Government has been promoting the development of fiber-optic networks. The General Directorate for the Information Society in the Junta de Andalucía wanted a tool for evaluating the costs of setting up a fiber-optic network across the Andalusia region. It wanted that network to connect both large cities and small towns so that they would not fall behind in the information society. The Association for Industrial Research and Cooperation in Andalusia (AICIA), together with the Department of Management Engineering of the University of Seville worked together to develop a tool for estimating investment requirements. The Junta de Andalucía wanted to establish a network capable of accessing most of the municipalities in the region, even those that could not be profitable from a monetary perspective. It also wanted to use the evaluation results and the network specifications to persuade private companies to expand their own networks by using links in the “administration network” to reach small towns. Our technical study is the basis for the regional government’s current pilot project on the deployment of a universal telecommunication network in the Andalusia Region. On March 10th, 2004, the general manager of the General Directorate of Information Society of the Junta de Andalucía described the project to the press. Although it originally wanted to persuade companies to make a major effort to establish the network, the regional government is now building the network with its own funds and with funds from the European Union. The regional administration is still trying to persuade various companies to take part in establishing the network. Graph theory and other OR techniques have proved useful in network deployment (Cox et al., 1993). We developed a model that represents a telecommunications network 4 reasonably well, and a process for deploying a cost-effective network deployment for a geographic area the size of a region. Researchers who made important contributions in this area were Balakrishnan et al. (1998), who considered the optimal capacity investment problem, and Chang et al. (1995) and Saniee (1995), who studied the multiperiod case. Although their work was important, it did not reflect the technological complexity of deploying a telecommunications network, in the opinion of our technological partners from the University’s Telematic Department and from industry partners. As Michael Pidd (1999) asked, what is most important: adapting reality to the models or adapting the models to reality? To incorporate our technological partners’ comments and after discussing them, we remodeled the traditional multicommodity flow model, constructing an exhaustive and extremely complex model (Appendix). Another approach to dealing with the problem is real options theory used in investment analysis. It is an especially interesting approach because it considers sunk investment costs. Keppo (2003) uses this approach to deal with a telecommunication capacity investment problem, but we did not follow this line. Starting a multidisciplinary project: the discussion The team responsible for the project included engineers in the telematic engineering field, engineers working in operations research, engineers from the regional government, professionals from the telecommunications industry, and people from other academic backgrounds. Such a multidisciplinary team has great potential if its members can manage to reach agreements. The main problem with teamwork is that the different team members try to replicate methods they have found successful in the past and in which they specialize. Thus, while the operations research specialists tried to convince the other team members of 5 the need to apply models based on multicommodity flows, the telematic engineers and the telecommunication professionals voted for replicating well-known network structures, feeling no need for complex optimization methods. Everything seemed to be set in stone, and the only thing left was to look at the list of providers. However, the regional administrators wanted to minimize the overall cost. Besides, it wanted to avoid a multi-stage deployment; and its own technical staff was to implement the project. After the initial meetings in which consensus seemed remote, the members of the team started to really undertake teamwork. Those familiar with operations research began to understand the performance and technological composition of networks, and those in telematics understood that they were assuming the methods they knew were feasible based on commonplace heuristics, but that those methods might produce a solution that was far from optimal, and could be of lower quality than other untested solutions. The regional administration wanted a low-cost network with extensive coverage that would reach the most underdeveloped towns. It wanted to create an information society, and obtain a politically correct welfare solution. The European Union imposed some of these requirements in providing European Structural Funds: the network had to reach even those towns where deployment of a fiber-optic network would be of little or no interest to private companies. The team members had to come to agreement on a series of matters. First, it agreed the network structure would be hierarchical, would include the existing telecommunication networks, would have two levels, and would cover large groups of towns and increase the level of multiplexing within the territorial boundaries of Andalusia. Second, the team members agreed that the cost model would be built as a piecewise linear function (this objective was unattainable, according to the telematic engineers). Third, the model would represent the network structure and objective function, and the construction6 related restrictions typical for this type of network. The team members also agreed that the grade of survivability (paths connecting a pair of active nodes) would be 2, following established practice in the industry. Once the team built the model, it had to find a solution method. The OR members persuaded the other team members to use genetic algorithms. Without doubt, the most complex task of any in the project was reaching agreement to build a model that closely represented reality, and adapting to it, instead of trying to adapt reality to the model. The hierarchical structure of the model Private companies in the cable telecommunications sector set up their networks using hierarchical structures with different levels (Martinez and Parames, 2001). Modeling networks without hierarchical levels is an exercise in mathematical abstraction, but not a realistic application in the telecommunications industry. To represent hierarchical levels, one must introduce additional complexity in the models. Different graphs are associated with the various hierarchical levels in terms of nodes and links, and they are interrelated with the other graphs. In designing telecommunication networks, operation researchers in different theoretical areas have sought to use well known problems, such as the hub-location problem, the constrained minimum-spanning-tree problem, the Steiner tree problem or the capacitated-multicommodity-flow problem to solve the real problem. We developed a model that was less compact and elegant, but closer to reality. We considered three hierarchical levels. The lowest was passive nodes representing simple intersections in the network infrastructure. No data would be inserted or retrieved in the network via these nodes. At the next hierarchical level were towns, or 7 urban nodes, used for incorporating and receiving data from the network. Finally, at the highest level were switching centers, or hubs (assigned to defined geographical regions within the network deployment area), containing transmission equipment, such as the digital cross-connect system (DCS). Our model contains, then, two overlapping network structures: a physical network and a logical network. The physical network determines the physical location of ditches, that is, it represents needed civil-engineering work. It includes all the nodes in the three hierarchical levels. The logical network, on the other hand, is based on two hierarchical levels. The lowest logical level (the low-speed network) connects the urban nodes (in the second hierarchical level) and the hubs (in the third level). It includes links that handle all the communications between the urban node and its regional switching center (hub). The highest logical level (the high-speed network), handles communication between regional switching centers (hubs). It includes shared links that carry communications from different regions together, a switching center that separates them and reroutes them to their final destinations (Figure 1). 8 Figure 1: Network with three regions. This fiber-optic communications network has a hierarchical structure of nodes and links for flow transmission, featuring a ring-star logical structure, equivalent to a ring-tree physical structure. For intraregional communication between two urban nodes T 1 and T’1 ,information flows from T1 to H1 follow the dedicated intraregional link from T1 to H1 included in the logical network, which contains the conduits connecting T1 and 1, and 1 and H1 in the physical network. The switching center H1 sends the information to its correct destination T’1 , via the link (H1 , T’1), which includes conduits (H1 , 1) and (1 , T’1). For interregional communication between urban node T1 and urban node T2 , information flows from T1 to H1 follow the dedicated intraregional link (T1 , H1). After switching in hub H1, they go through the interregional shared link (H1 , H2), which can carry several interregional communications together at the same time, and which includes conduits (H1 , 2) and (2 , H2). Finally, after switching in H2 , the communication travels to the final node T2 via the dedicated intraregional link (H2 , T2), which includes conduits (H2 , 3), (3 , 4) and (4 , T2) of the physical network. The link connection (Figure 1) allows any network entity to communicate with any other. In practice, network planners commonly use second degree redundancy levels for the upper-level logical network (creating a ring structure), connecting urban nodes (of a lower hierarchical level) via a star-type logical connection, which corresponds to a treetype physical structure. Network operators, however, habitually reject as unfeasible those paths for transmitting communications that require too many switching processes in hubs. By setting this criterion they intend to minimize the delay in the path, because the switching process entails big delays (Appendix). 9 Matching delay levels [Appendix equation (12)] The model (Appendix) can be classified as a mixed-integer linear-programming problem. Because the problem has a combinatory structure, it is difficult to solve. For example consider the realistic case of a geographical area divided into five regions, with 20 municipalities (which imply about 28 possible interregional communications and 30 regional ones) and a graph with 600 links including an average of 200 fiber-optic links associated with each possible hub location inside the region and three alternative paths for each interregional communication. The model would require 1,644 binary variables, 209,974 continuous variables, and 206,739 restrictions, excluding non-negativity conditions. To deal with these dimensions, we tackled the problem using a procedure based on hierarchical decomposition. In the first phase, we concentrated on locating hubs and extending the physical network with reliability conditions, since most of the cost covered those activities (up to 85 percent). Note that a network survival to failures needs reliability over several of their links, especially in the trunk subnetwork. In the second phase we considered the associated problem of routing demand and assigning capacity. As one of the most important decisions we needed to locate hubs; their locations would strongly influence both the physical and the logical networks (figure 3). 16 65 4 3 2 1 7 165 4 3 2 B 7 65 4 3 2 1 C 7 65 4 3 2 1 D 7 3 165 4 2 B1 165 4 2 B2 16 4 2 B 3 3 5 4 3 2 C1 6 5 3 2 C2 65 4 3 2 C3 65 3 2 D 1 7 5 4 3 2 D 2 7 65 4 3 2 D3 7 A Figure 3: Considering network A which covers three regions, B, C, and D are possible hub locations. Each produces different physical and logical networks. In depicting networks among hubs; we have omitted the rest of the nodes (for example, we include node 1 when it is the hub for region 1, in structure B). At level 2 of the hierarchy, the municipalities will be associated with hubs according to the hub structure selected. Thus the hub in option B could support the groups of links for extending the fiber-optic network shown in B1, B2, and B3. C would result in C1, C2 or C3, and D in D1, D2 or D3. Additional alternatives for hub structures (up to 12) exist for locating switching centers. After the hub structure is fixed, one can determine the exact number of feasible links. Because each hub structure can support a number of sets of feasible links, determining the locations of hubs is a key issue. Our solution procedure relies on this fact. We formulated a genetic algorithm in which the chromosome encoding for different 17 individuals represented the different options for hub locations. We evaluated the fitness of each individual in the population using a two-phase hierarchical process. Thus, for each proposed hub structure, the first phase consisted of determining a connected network with a κk survivability grade. We sought a survivability grade κk =2 for the interregional network and a survivability grade κk =1 for the intrarregional one. We would thus achieve the configuration associated with the basic conduit infrastructure obtained by using two-tree techniques with survivability conditions, combining Steiner trees (Monma and Shallcross 1988 and Monma et al. 1990). In the second phase, we decided on the logical network in which the optical fiber links were set and its capacity was set. To solve this problem we formulated the Kuhn-Tucker optimality conditions associated with the reduced problem, in which restrictions (5), (7) and (9) do not need to be considered, since they are implicitly forced after we encode the individual’s chromosome in the genetic population. Associated with the optimality conditions, we developed a routing-demand and capacity-assignment algorithm that guaranteed it approximated the optimal solution in each iteration (Cortes et al 2001). The results Initially, we wanted to compare our results with the results from other similar regions in Spain or Europe. However, we could not because the private companies operating in this area considered such information confidential. Furthermore, the Administration (Regional, National or European) had not promoted previous experiences with such projects in the Spanish or European context. However, we compared the outcome of our model and algorithm with the results from the well-known two-step heuristic, (Sexton and Reid 1997), which private companies use when deploying telecommunications networks. 18 In this way, we validated our solution algorithms with 600 trial problems. We generated these trial problems randomly among diverse ranges, but within the problem constraints. To compare our genetic algorithm with this two-step heuristic, we conducted experiments (Table 5). Factor code Factor description L ower level (code “-“) U pper level (code “+”) 1. N N umber of nodes N ≤ 60 N > 60 2. DA A rcs density D A ≤ 1/2 D A > ½ 3. DR R egion density D R ≤ 1/3 D R > 1/3 4. DT Terminals density D T ≤ 1/2 D T > ½ 5. D D emand scenario B ase demand scenario H igh demand scenario 6. S R equired survivability L evel 2 in inte r -regional network M ore than level 2 in inte r -regional network Table 5: We analyzed the factors effect using the Experimental Design Theory. We considered six factors, four topological factors and two technological factors divided into two levels (a two levels codification). The Experimental Design Theory states that such codification guarantee that the variance analysis coincides with the minimum square error analysis. After that, we used Limdep v.7.0 (econometric software from NLogit) to adjust the mode and to analyze the effects of these factors on the cost of establishing the network and on the survivability level attained (SLA). 19 The number of nodes (N) includes the passive nodes as well as the municipalities (active nodes). We calculated arc density (DA) as A/MAXARC, where A represents the number of arcs in the underlying transport network and MAXARC the maximum number of arcs possible for the number of nodes in the graph. We calculated the density of the regions (DR) as R/T, where R represents the number of regions in the geographical area and T the number of urban nodes. We calculated the density of terminals (DT) as T/N. We classified our results by ranges according to Table 6. The problem range is given by the number of nodes, the terminals density and the region density. Problem range Genetic algorithm Two-step heuristic Genetic heuristic Nodes Terminal density (DT) Region density (DR) Cost Time Cost Time Cost reduction Arc density (DA) SLA SLA [0.1-0.6] 100% 100% [0.25-0.4] 12.91 4.7 18.11 5.1 29% (0.6-1.0] 100% 100% [0.1-0.6] 98% 97% [0.1-0.55] (0.4-0.6] 11.12 5.1 14.23 5.2 22% (0.6-1.0] 100% 100% [0.1-0.6] 97.5% 95% [0.25-0.4] 20.76 23.8 28.78 24.5 28% (0.6-1.0] 98.3% 98% [0.1-0.6] 88% 86% ≤ 40 (0.55-1.0] (0.4-0.6] 20.21 60.6 35.12 46.8 42% (0.6-1.0] 99% 98% [0.1-0.6] 98.9% 98% [0.25-0.4] 22.08 37.8 34.50 62.1 36% (0.6-1.0] 99% 99% [0.1-0.6] 98.5% 92.9% [0.1-0.55] (0.4-0.6] 29.47 92.6 45.24 95.5 35% (0.6-1.0] 100% 98% [0.1-0.6] 92.5% 86.8% [0.25-0.4] 43.91 208.8 60.74 150.1 28% (0.6-1.0] 96% 92.8% (40-80] (0.55-1.0] (0.4-0.6] 54.56 592.8 81.65 303.2 33% [0.1-0.6] 91% 90% 20 (0.6-1.0] 94.3% 89.5% [0.1-0.6] 99.5% 97% [0.25-0.4] 26.57 101.2 62.58 147 57.5% (0.6-1.0] 100% 100% [0.1-0.6] 99.8% 96% [0.1-0.55] (0.4-0.6] 23.72 80 33.21 99 28.6% (0.6-1.0] 100% 100% [0.1-0.6] 93.2% 90.4% [0.25-0.4] 54.53 560.5 82.05 495.8 33.5% (0.6-1.0] 95.3% 91.1% [0.1-0.6] 86.4% 80.3% (80-100] (0.55-1.0] (0.4-0.6] 62.45 1720 126.42 952.3 50.6% (0.6-1.0] 87.5% 81.1% Table 6: The results show that the genetic algorithm attains better results than the two-step heuristic for networks in all ranges. For large networks, the genetic algorithm reduces costs more than for small networks. Both terminal and region densities emerged as important explaining factors. The density-of-arcs parameter does not significantly affect cost or time for execution; but it is the main factor affecting SLA. Computation time for the two-step heuristic is lower than that for the genetic algorithm specific ranges because it is based on simpler rules and does not use iterative calculus as genetic algorithms do. However, we obtained all the results within feasible bounded execution times. In table, costs are in million of euros, average execution time are in seconds. The survivability level attained percentage is the final survivability level attained divided into the survivability level required. We found that coverage is associated with the density of the terminals, since coverage is calculated as the ratio between the activated nodes in the network (terminals, T) and the total number of nodes (N) in the network. The region’s density indicates the multiplexing level in the network: for a high value of DR, we will have a low level of multiplexing, and for a low value of DR, we will have a high level of multiplexing. Based on our results, we drew some general conclusions (figure 4). 21 Coverage (nodes) 810 12 14 16 18 20 22 0 1000 2000 3000 4000 5000 10 12 14 16 18 20 22 0 0,5 1 1,5 2 Coverage increase Cost increase Number of regions 3 4 5 6 7 8 9 10 2500 3000 3500 4000 4500 Good-engineering Under-engineering Over-engineering Demand increase Cost increase Figure 4: The network coverage is in a linear relationship with the cost for deploying it, although the cost increments are smaller than the increments in network coverage. On the other hand, the multiplexing affects the network cost depicting three interesting zones: a first area of over-engineering, where the multiplexing effect generated is excessive and the cost is not optimum; another one of under-engineering, where multiplexing levels are scarce and the cost raises; and finally one of good-engineering, where multiplexing levels result adequate and which corresponds to the optimum cost. Finally, costs remain the same when demand increases, mainly because of the high capacity of the fiber-optic links. The costs of deployment is very sensitive to the degree of coverage (the terminal nodes by the network) and to the multiplexing level (the relation between the number of regions and the number of terminals). We therefore checked the good-engineering zone before defining the hub structure and determining the region’s density. On the other 22 hand, the deployment topology is extremely robust, handling great increases in demand (figure 4). We used our results fine-tune and calibrate the algorithms. We then applied the tool to the different geographical areas in the Andalusian region (figures 5 and 6, table 7). Figure 5: We show the results obtained for the area of the Seville province. We show the case of a design based on four regions, after checking that this was the case which corresponded to the good-engineering multiplexing area. First, in this figure we depict the physical network that we proposed for the province of Seville. It reflects a ring-tree structure. The thin lines represent the tree outline corresponding to the intraregional communication sections and the thick line represents the ring outline corresponding to interregional communication. 23 Figure 6: The logic design network for the province of Seville reflects a ring-star structure. The thin line forms the star outline corresponding to the intraregional communication sections and the thick line represents the ring outline corresponding to interregional communication. The grey scales differentiate among the four regions of the Seville province. Note that white zones are noncovered areas, for example agricultural areas. The investment required to setup the fiber-optic network was 62.21 million euros. We also obtained ratios useful for analyzing costs with respect to certain parameters, for example setup cost with respect to the number of people reached (43.54 euros per person), and with respect to the number of households (126.24 euros per household); the latter is a better index for economic effort, because it is households that subscribe to cable telecommunication contents. Total setup cost 62.21 million € Percent of survivability grade specifications met 100 % Cost of setup with respect to population reached 43.54 €/inhabitant reached Cost of setup with respect to the number of households reached 126.74 €/household reached 24 Cost of setup with respect to the number of main residences reached 159.55 €/main household reached Table 7: Main economic ratios associated to the network setup in the area corresponding to the Seville province. The most interesting values are the total setup cost and the setup cost with respect to the number of households since they are the subscribers to the cable telecommunication contents. Also, we have included this ratio with respect to the number of main residences, taking into account the possibility of having several residences per household (as vacation residence for example). Conclusion The directorate general of the Andalusia Government for the information society regarded as very positive our contribution to the development of a tool for evaluating the levels of investment it would require to setup a fiber-optic network for the region. Our results allowed it to justify its interest in establishing a network that included small towns as well as large cities. The final result of our work was a technical study used as the basis for the current pilot project for the deployment of a universal telecommunication network in the Andalusia region. The regional government is currently implementing the pilot project and carrying out the first civil-engineering works. Furthermore, the proposal is helping to persuade to private operators in Andalusia of the advantages to be derived from establishing telecommunication capabilities, especially in attracting the early market. 25