Planning a Ring-Tree Network to provide Telecommunication Services at Centres of Rural Population

WSEAS TRANS. on INFORMATION SCIENCE & APPLICATIONS Issue 4. Volume 3 April 2006 ISSN: 1790-0832 737 Planning a Ring-Tree Network to provide Telecommunication Services at Centres of Rural Population PABLO CORTES*, JESUS MUNUZURI, JOSE GUADIX, NICOLAS IBANEZ Department Ingenieria de Organizaci6n University of Seville c/ Camino de los Descubrimientos sin, 41092 -Seville SPAIN *[email protected] http://io.us.es/Componentes/P.Cortes/ Abstract: -Nowadays certain centres of rural population are experimenting difficulties to access high-speed telecommunication networks. This phenomenon avoids the possibility of accessing to the digital revolution for such areas. The private companies are focusing their investment efforts in other more profitable areas. In such conditions, the governments have to promote alternatives to bridge the digital divide between rural and urban areas. We present how ring-tree topologies can be used as an adequate architecture to incorporate such less favoured areas in the Information Society. We present a case study for Andalucia (a wide region in the south of Spain) where a decision support system based on a genetic algorithm is implemented providing cost effective solutions. We make use of real life data from the telecommunication industry and present different solutions separated by coverage as well as a sensitivity analysis based on the main factors of the cost function. Key-Words: -ring-tree network, digital divide, rural poptilation, genetic algorithms, fiber optic, case study 1 Introduction Nowadays certain centres of rural population are experimenting difficulties to access high-speed telecommunication networks. It supposes a great barrier for its development embedded into the modem digital society. Certainly, the access to information and communication technologies can . launch small and medium-sized finns directly into the heart of regional, national and global markets. Also, telemedicine can provide access to up-to date health and medical information to even the most remote communities. These technologies will facilitate low-cost distance learning. And they can empower civil society, strengthen democratic institutions and make governments more transparent and accountable, [lJ. There are not many scientific references dealing with this problem. Although, [2] shows how the use of new information technologies can improve the competitiveness in rural small businesses. However the proposals are in terms of business solutions, but not in terms of communication infrastructure. Unfortunately, those communities that most need the boost that the technologies of the information and communication can provide are least able to take advantage of it. Because, the Information Society evolution is supported through the telecommunication networks deployment. The high cost of such infrastructures forces the companies to focus their efforts in the profitable communities. To give a solution to it, the governments have to promote alternatives to bridge the digital divide between rural and urban areas. And in many cases these actions must include the funding of new telecommunication infrastructures. As in other parts of the world, in Spain, the private companies have focused their network extension and modernisation strategic plans on the more profitable communities. It is the case of the big cities of the country. Recently, the Andalusian Regional Government has been leading a series of initiatives aimed at promoting the development of fiber optic networks around the region. And its plan tries to promote the development of such networks, especially, for the less favoured areas. This objective is the starting point of our work. The General Directorate for the Information Society of the Junta de Andalucia asked us for a tool capable of evaluating the investment volume required to set up a fiber optic network. This network would have to arrive up to the less favoured areas of Andalucia and to connect them to the bigger cities. So our objective was the generation of a tool capable of designing a cost- 738 WSEAS TRANS. on INFORMATION SCIENCE & APPLICATIONS Issue 4, Volume 3, April 2006 ISSN: 1790-0832 efficient backbone network allowing bridging the digital divide and getting access to the less favoured rural zones. The rest of this paper deals with the identification of the digital divide in Andalucia, and the description of the technological background (respectively in section 2 and 3). Subsequently, we present the model considered to design the network in section 4, and the decision support system based on a genetic algorithm in section 5. The main results are showed in section 6. Finally we finish our paper with the more relevant conclusions. 2 The digital divide in Andalu�ia In Europe, the digital divide is a phenomenon that is produced due to the disconnection between the rural and urban communities. It is because the rural areas and its municipalities tend to be non profitable for the private companies. So the telecommunication networks do not reach those zones. Recently, the EU Conunission Staff working paper, [3], has stated the guidelines on criteria and modalities of implementation of structural funds in support of electronic communications. The working paper shows how the demand aggregation for broadband services should be encouraged in order to ensure critical mass of users in public administrations whilst avoiding dependence on one single operator. Furthermore the stimulation of demand for types or 'clusters' of SMEs allows increasing awareness and use of JCT. The actuations that the working paper states, must be useful to finance content, including e government, in particular local and regional services in order to boost demand for broadband on a sufficiently focused basis to develop supply. Also the Commission states that the Public authorities, and particularly the Regional authorities (as the case of the Junta de Andalucia is) and local authorities, have a key role to play in the development of the information society by (1) using information society applications and services in the process of modernisation of services provided to citizens and companies, (2) promoting the information society in the region and (3) monitoring the evolution of the communications networks and services provision on the region in order to avoid exclusion and contribute to the balanced development of regional activities. In order to attend to these guidelines, we divided Andalucia in three sets. Firstly, we consider as type A municipalities those where exist alternative infrastructure. So, they are cities where a commercial competition is produced (basically between ADSL and coaxial cable). Secondly, we state type B municipalities as those where only exist ADSL but they could have enough service demand to support another telecommunication operator. Finally, type C municipalities are those which has not ADSL infrastructure due to a strong lack of demand. 2.1 Classification of municipalities There are 18 type A municipalities: Almeria, Algeciras, Cadiz, Chiclana de la Frontera, Jerez de la Frontera, La Linea de la Concepcion, El Puerto de Santa Maria, Rota, San Fernando, Sanlucar de Barrameda, Cordoba, Granada, Huelva, Jaen, Malaga, Alcala de Guadaira, Dos Hermanas and Seville. It supposes 43% of the Andalucia entire population (3,164,329 inhabitants). The population living in type B municipalities is equal to 45% (3,292,609 inhabitants). There are 262 type B municipalities. Furthermore, we divide the type B municipalities between B 1 and B2. Type BI municipalities are those where the existence of another telecommunication operator would be profitable; and B2 municipalities those non-profitable. The separation between B 1 and B2 was done considering the expected Payback period, the Net Present Value (NPV) and the Internal Rate of Return (IRR) of each type B municipality. See [4] for an in depth discussion. In order to realize the analysis we considered the initial investment as a function of the municipality size. Basically, we considered the DSLAM cost (including a fixed part and another variable depending on the number of users). As incomes, Cl ENCE & APPLJCATIO S Issue 4, Volume 3. April 2006 ISS 1790-0832 739 we considered the monthly tariff multiplied by the expected demand. The demand was calculated by using different statistical approximation methods (moving average, exponential smoothing, Holt, linear regression and quadratic regression) and minimising the historical error observed by a parametric composition of them. [ 4] discusses in depth about the demand estimation. As costs, we considered the operation and maintenance costs as a 10% of the incomes (following habitual values from the Industry). Here the possible enlargement of the DSLAM capacities was also included. Finally, to difference between type B 1 and type B2 we selected an IRR upper than 120% and a NPV upper than 3 millions of euros for a 10 years horizon. The result was 43 type B 1 municipalities and 219 type B2. The analysis leads to a standard Bl town with 32,500 inhabitants and a standard B2 town with 8,600 inhabitants. The rest of the towns were considered type C. So we manage 490 municipalities that represent the 12% of the entire population of Andalucia, i.e. 883,637 inhabitants. Figure 1 represents the main characteristics of the municipalities (the demand is expressed as the expected number of "equivalent ADSL lines" for the final period of the horizon). Each "equivalent ADSL line" is considered with a capacity of 256 Kb/s. So, final users with capacities upper than 256 Kb/s are converted in the correspondent number of "equivalent ADSL lines". Amount of Population Number of munlclpalltles Demand volume Figure 1. Municipality classification The number of municipalities in the bad part of the digital divide is 709. It is a population equal to 2,780,327 inhabitants, and most of them are living in rural areas. It represents a great volume of the Andalusian population that will suffer strong difficulties to access to the Information Society and its benefits. Figure 2 details the main characteristics of the digital divide. Number of munlclpalltles C .... Population (.,,. t.MI.HO·, .. � Nl.1)1: 12� Demand and Population Figure 2. Main characteristics of the digital divide 3 Technological background There are a wide range of technological alternatives to allow the deployment of high-speed telecommunication networks. The first division that we have to undertake is between the access network (urban network) and the backbone network (inter-urban network). Next figure 3 depicts the different alternatives to be considered. r,....,., , . ., '•C Topological { : ���,��!,101 alternatives � R,ng. Multiple Stor •Ring· R:ing Backbone Access Network . :� !i ;� tt .::; ·, -�· t )' ./� '\ lechnological alternatives { • Switched netwo,k· PSTH l0SN, x0Sl) • Coble; HFC • Fixed eellulor: Wll·LMOS • MobMa cetlvklr· GSM. UMTS • Sotellil•. DVB Figure 3. Access network and backbone The most significant cost in the access network is the local loop. The access network presents a great technological heterogeneity. The physical media can be fiber optic, coaxial cables, copper cables cellular radio or even satellite. And the technology can include traditional public switched telephone networks, PSTN, IDSN or xDSL, as well as cable telecommunication networks (HFC), fixed cellular networks (WLL-LMDS) or mobile networks (GSM, UMTS) in addition to the satellite multicast (DVB). Figure 4 shows several of these alternatives. I :::· · .. 1111 =-�� Figure 4. Technological alternatives for access networks ISS 1790-0832 But the most important part of the deployment cost of a universal telecommunication networks is the cost of the backbone network. The backbone presents certain homogeneity due to the enormous advantages of the fiber optic (using SDH or WDM standards). Several alternatives can be used for the extension of trunk links in the backbone. They depend on the transmission capacity and the length of the link: •Fiber optic of high quality without regenerators. They achieve optical amplification each 100 kilometres. High quality monomode fiber is necessary, as well as erbium-doped fiber amplifiers. This system need not electro-optic conversion, and when it 1s combined with wavelength division multiplexer (WDM/DWDM) can reach capacities up to 100 Gb/s. •Fiber op tic with regenerators. This option does not require so efficient and also expensive equipment. Lower quality fiber can be used but it requires the installation of regenerators each certain distance (typically 40-50 kilometres). It is adequate for capacities up to 2.4 Gb/s and distances shorter than 150 kilometres. •Digital radio communication. It is limited to capacities up to 34 Mb/s. Furthermore the land orography must be taken into account. Next section 4 presents the design model. In it, we focus the problem in the backbone design, but considering the necessary terminal investment (the local loop). So the last mile corresponding to the selection among the technological alternatives is not considered here and it will depend on the final decision of the private company. The objective of the work is to set up an existing infrastructure capable of reaching the non profitable points of the rural Andalusian region. In order to conceptualise the problem we make use of Graph Theory together with bio-inspired algorithms to solve it. The process described in this paper shows the conceptualisation of a model that represents reasonably a telecommunication network, as well as the process followed in order to achieve a cost-effective network deployment for a regional-size geographic area. 4 Model The Theory of Graph defines a graph given by a set of nodes and arcs: G=(N,A). The nodes can represent municipalities (M) or simple intersections (S) in the underlying transport network where the telecommunications network is to be placed. So, they will be active nodes (municipalities) or passive ones (typically intersections of the graph not supplying or receiving information). Arcs represent roads linking two different nodes. We used the road network of Andalucia that allows the deployment of fiber optic cables. This initial graph was supplied by the Instituto de Cartografia de Andalucia (ICA) in Arc/Info format. The graph is shown in figure 5. Figure 5. Initial graph 4.1 Previous hypothesis Previously to the design of the network, the Junta de Andalucia stated some strategic decisions tha had to be taken: 1. The transmission media would be fiber optic. That allows to ensure a transmission with quality and capacity (speed in the order of hundred of Gbit/s). 2. The topology should permit the rerouting of the flows among the main municipalities in case of fails. So, the selection of a ring-tree topology was selected because it allowed this concern. The ring of such network would include all the type A murucipalities. Certainly, the bi-directional self-healing ring has been the most used topology in the case of 74 1 traditional public operators due to its re ilient wide coverage. 3. The ring should follow alternative fiber optic rings being currently property of operators different from the dominant operator. Thi is the case of the available fiber optic in the railway and electrical networks. This decision will make possible a faster deployment of the network in the less favoured areas carrying out the ring deployment in the last stage. Thi decision fixes the ring topology to the figure 6 case. ,r .. . .. ·. ·. ·" Figure 6. Resilient self-healing ring in the backbone The ring has two special characteristics. One of them is the direct connection between Seville and Huelva. This is to avoid the Dofiana Natural Park, one of the largest protected biosphere reserves in Europe. The other one is the direct connection Orgiva-Almeria. This is due to special difficulties in the road network. Both problems are solved by deploying a parallel double fiber optic cable. 4. The ring considers the data accumulation nodes for Internet connection located in Seville and Malaga. 4.2 Cost model The infrastructure costs are classified rn four categories: 1. Node costs: a. Fixed cost associated to the exjstence of the node, F; Vi EM. It corresponds to the terminal cable room adaptation 742 WSEAS TRANS. on INFORMATION SCIENCE & APPLICATIONS Issue 4 Volume 3 April 2006 ISSN: 1790-0832 to connect the fibers into the DSLAM. b. Cost depending on the capacity managed by the node. G;(C;), 'tlieM. It corresponds to the modular equipment, where the transmitters and receivers are placed. 2. Arc costs: a. Cost depending on the arc length, L;/Dif), tl(iJ)eA. It corresponds to the ditches and conduits. b. Cost depending on the arc length and its supported capacity, C/DiJ,Cmax), V(i,j)eA. It corresponds to the fiber optic links including transmitters, receivers and regenerators or optical amplifiers when needed. The node costs (part 1 ), as well as the arc costs depending only on the length (part 2.a) are detailed in appendix 1. On the other hand, two different technological alternatives are considered to calculate the 2.b cost part. The first option corresponds to high quality fiber optic link (without regenerators). It can be estimated as ( 1). (1) The second option corresponds to lower quality fiber optic link (with regenerators) that can be estimated as (2). C (D C )= /'SDH,i + l'soHd +P ·D +C -r11+2C ·lc-J u IJ' .... n� n, ft> tJ .., D.,.. DWDl>I c,OGb Where: (2) • PsDHo and PsDHd are the origin and destination SDH multiplexer costs. •n0 and nd are the number of links in the SDH equipment placed in node. Each SDH multiplexer can serve diverse digital links. •D/G is the arc distance. It is covered without regenerators. •D,i is the arc distance. It can be covered with regenerators. •P1 /G is the linear cost of a high quality cable of 24 monomode fibers plus the cost of connecting it. •P1 0 is the linear cost of a standard cable of 24 monomode fibers plus the cost of connecting it. •Coam is the cost of an optical amplification system. •Creg is the cost of a regenerator. •Dmax is the amplification maximum distance. Typically 140 kilometres for option 1 and 40 kilometres for option 2. •C,r is the cost of DWDM interface card (transmitter/receiver) with capacity up to 10 Gb/s. •Cmax is the capacity that must be equipped. Appendix I details the numerical values for both options. 4.3 Topological model As section 4.1 stated a ring-tree topology was selected. This topology consists of a hierarchical structure given by nodes of level I and nodes of level 2. Th goal of such architecture is to simplify the subsequent network management. The level 1 nodes are the ten larger cities of Andalusia: Almeria, Algeciras, Cadiz, Jerez de la Frontera, Cordoba, Granada, Huelva, Jaen, Malaga and Seville plus Orgiva (a small municipality selected as part of the ring due to its strategic geographic location) .. These nodes depict the ring of the backbone (figure 6). The rest of nodes are connected at one of these level 1 nodes by a tree structure. However the rest of nodes could be located into the ring structure or out of the ring. In the first case, the basic infrastructure has not to be constructed. There already exist the ditch and conduit, so we only have to consider the cost 2.b. In the other case ( out of the ring) we would have to consider the costs of civil · infrastructure (2.a) and transmission link (2.b). See figure 7. WSEAS TRA S. on JNFORMATIO all Nodes or ln•I 1 eHodes of le¥el 2 in IM r,ng QNodu of lenl 2 out of the ring \ Flows betwHn nodu -- Direct link betwHn nodes or level 1 (ring) Supar•branch. Link betwHn nodH of -- level 1 and ltvel 2 through lhe ring Branch. L.ink bttwHn nodes of level 2 and level 2 out of the ring 0 lnffutn,cture. Conduit and ditch 0 0 Figure 7. Topological structure 5 Decision Support System based on a genetic algorithm The decision support system (DSS) is based on a genetic algorithm engine. Genetic algorithms have recently been considered to deal with different kinds of telecommunication problems. Most of them are in the scope of theoretical applications. A wide-scope on genetic algorithm was presented by [5] to design network rings, and more recently [6] and [7]. [8] presented Gen0Sys that is a topology planning tool based on a genetic algorithm to design tree network infrastructures. In this scope, [9] developed a genetic algorithm for the design of topologies in optical networks. It is case similar to [ 1 O]. Also, genetic algorithms have been used for dynamic packing, [11]. Finally, a real life implementation can be found at [ 12]. 5.1 Decision support system structure The DSS inputs are the cartography supplied by the ICA and the socio economic data warehouse database provided by the Institute Estadistico de Andalucia (IEA). After processing the cartography and considering the technological model and the strategic decisions, we get the topological model, in terms of a graph. The result was a graph with Issue 4. Volume 3. April 2006 IS N 1790-0832 743 2 796 arcs and 1 920 nodes. 770 of those nodes ' ' are municipalities, the rest are simple intersections. Jn the other side, the socio economic data of the municipalities of Andalusia plus the historical demand data are used to estimate the telecommunication demand for each of the municipalities. The demand values plus the financial analysis of each urban node allows us to classify the municipalities between profitable and non-profitable. This allows identifying the digital divide. These three components (the topological model the cost model and the classification of ' municipalities) are introduced in the algorithm that provides the solution. See figure 8. � IEA(SIMA} � Sooo--eoonom,c databNe Digital divide ldentlfl�atlon n ���rtymg transport networt< Arc/Info coverages EJ n !T� modol !llmagic -1.lona Figure 8. Decision Support System structure 5.2 The genetic algorithm The dimensioning of the network, as well as the multiple topological alternatives to deploy such network makes the computationally complex problem. In fact, the problem can be proved as NP-Hard by simple reduction to the Steiner problem. Furthermore, given a feasible solution is easy to compute its evaluation (it can be done in polynomial time), so the problem is NP-Complete too. For this type of problems metaheuristics approaches have been proved to be suitable. And our proposal is based on a genetic algorithm. The utilization of genetic algorithms allows obtaining good solutions in problems with a high 744 WSEAS TRANS. on INFORMATION SCIENCE & APPLICATIONS Issue 4, Volume 3, April 2006 ISSN: 1790-0832 number of complex constraints with a difficult mathematical formulation, as this one is. The strategy consists of generating diverse feasible solutions (with easy evaluation) and recombining them without losing feasibility. Note how each feasible solution of our problem must include the predefined ring plus the tree (super branches and branches, see figure 7). The procedure follows the next three steps: 1. Constructing a supra-node corresponding to the ring. The ring is conceptualised in one only node composed by all the nodes in the ring (including municipalities and passive nodes) and with so many incident arcs as each node of the ring has. 2. Constructing a tree that contains the supra node and all the municipalities. The passive nodes (intersection of the transport network) can be conveniently used if necessary. The genetic algorithm generates the network proposal. 3. Dimensioning the capacity of the ring. 5.2.1 Characteristics of the genetic algorithm We proposed a genetic algorithm with an encoding of the individuals genome as shown in figure 9. The encoding consists of an array with so many registers as arcs exist in the graph. If the register is set to one then the arc will be included in the solution, otherwise the arc will not be in the solution. Additionally, the genome must ensure the feasibility of the solution. So non-feasible solutions are not accepted. After testing with different sizes, we have considered an initial population of 20 individuals. To generate them we have use the Kruskal algorithm to solve the minimum spanning tree problem -MST. Note that we are considering the ring as a supra-node. So, given 20 different sets with arc fictitious cost, we can solve the correspondent MSTs and afterwards the solutions are cleaned by erasing the passive nodes located in a terminal position. The population size is a major factor in the effectiveness of genetic algorithms. It has been proved that relatively small populations allow reaching successful solutions with little computation effort, [13]. Our experiments show that increasing the population size beyond 20, although increasing the computational effort, is not rewarded by a corresponding increase of performance. We have implemented two different genetic operators (see figure 9): crossover and mutation operators. The parent selection mechanism is random in order to enrich the genetic variety. It includes a mechanism of incest prevention to avoid the crossover of genetically similar parents. •Un iform crossover operator. If the genome of both parents includes the arc in their solution (i.e. it has the same register set to 1, or set to 0), then the arc is maintained in the offspring. Otherwise (only one parent has the arc) the arc is maintained with a probability equal to 0.5. •Mutation operator. The operator changes a register from 1 to 0, or vice versa. That is, once one register has been randomly selected, if the arc belongs to the solution, then the arc is erased. Otherwise, if the arc does not belong to the solution, then the arc is included. The application of the genetic operators can lead to unfeasible solutions. The possible infeasibilities are the following: •After applying a crossover operator two trees are connected. This situation generates a new graph and cycles appear. The cycles are broken by erasing a randomly selected arc of. each cycle. •After applying a mutation operator two situations can appear: oIf an arc is included in the solution, a cycle can appear. Then, the cycle is broken by erasing a randomly selected arc of the cycle. oIf an arc is erased in the solution, the tree is disconnected. Then, the tree is reconnected by means of the shortest path algorithm. W EAS TRANS. on INFORMATION SCIENCE & APPLICATIONS Issue 4, Volume 3, April 2006 ISSN 1790-0832 745 Genome encoding l1lol1!olojol1joj1j1j A, A1 A, A,. A.,. Crossover operator Parent 1 Mutation operator Figure 9. Genome encoding and genetic operators Tests were carried out with different probabilities for crossover and mutation operators. Varying the crossover probability from 50% to 100% had little effect on performance, with a value of 80-90% being marginally optimal for the tests carried out. A value of 80% is used in the main runs. For mutation, values between 5% and 20% were seen to be giving better results than typically smaller values. A value of 20% is used in the main runs in order to enrich the genetic variety of the population. However, it is to be noted that the genetic algorithm is robust. That is, the test problems' solutions were achieved on the whole with a wide range of parameter values, and with no fine-tuning required to achieve efficiency. The substitution of new individuals (offspring) by the old individuals (in previous population) is made by a ranking based replacement. We propose the use of hypergeometric functions allowing more probability of replacement for individuals with worse fitness and less probability of replacement for individuals with better fitness. So the individual in ranking position-i, have a re�lacement probability equal to q•( 1-q i, where q is the replacement probability of the worst individual. The value for the parameter q is progressive. It starts with a low value of q in order to explore the feasibility region and then the value is progressively increased to exploit the niche quality. Additionally, we incorporated an individual duplicity control in the population generation. The number of generations of the genetic algorithm can be a critical parameter when we try to reach efficiency of the solution and short time execution. Genetic algorithms are iterative, and, therefore, they can take very much time of execution. However the advantage of genetic algorithms is that they can be stopped at any time having the better solution at the moment. After several tests, we selected a number of 50 iterations. The learning curve of the algorithm is depicted in figure 10. 400,00 -1I I 295,00 ,h---���---.--,-----.-..-----.-------� � � m � � N � � � � ; � � Iteration Figure 10. Leaming curve I Next Table 1 summarizes the value of parameters selected. Table 1. Genetic al orithm arameters Po ulation size, N 20 Crossover operator probability (mutation 0,8 (0,2) 0,2/0,4/0,6/0,8a a Progressive increase of q each ten generations. The algorithm pseudocode is described in the appendix 2. 5.2.2 Final dimensioning of the ring capacity We proposed a bi-directional self-healing ring. This allows rerouting the demand flows in case of fail. The problem is to determine the capacity of the ring that allows rerouting all the flows in case of fail. As the ring capacity is directly related to the ring cost, we minimize the capacity capable of guaranteeing the demand flows.