Diseño de redes de telecomunicación para el despliegue universal de servicios avanzados de telecomunicación

IX Congreso de Ingeniería de Organización Gijón, 8 y 9 de septiembre de 2005 Diseño de redes de telecomunicación para el despliegue universal de servicios avanzados de telecomunicación* Pablo Cortés1, Luis Onieva1, Juan Nicolás Ibáñez1, José Guadix1 1 Dpto. de Ingeniería de Organización. Escuela Técnica Superior de Ingenieros de Sevilla. c/ Camino de los Descubrimientos s/n, 41092 Sevilla. [email protected], on[email protected], juann[email protected], guad[email protected] Resumen La revolución digital promete grandes avances y progresos. Sin embargo, la Sociedad de la Información está fuertemente vinculada al desarrollo de las redes de telecomunicación. El elevado coste de estas infraestructuras está obligando a las compañías a centrar sus esfuerzos inversores en aquellos sectores en que se presumen mayores beneficios. En este sentido la puesta en marcha de mecanismos que permitan cruzar la brecha digital se está convirtiendo en una acción necesaria. Presentamos aquí el estudio de un caso correspondiente al diseño de una red de alta velocidad construida mediante un sistema de ayuda a la toma decisiones a partir de una serie de modelos que hacen uso de un motor de optimización basado en algoritmos genéticos. Para ello se hace uso de datos reales procedentes de la Industria de las Telecomunicaciones y se presenta una familia de soluciones separada por niveles de cobertura. Palabras clave: telecomunicaciones, redes, brecha digital 1. La brecha digital, el caso de Andalucía La revolución digital viene prometiendo grandes avances y progreso que redundarán en una mejora de la prosperidad. El acceso a las Tecnologías de la Información y Comunicaciones (TICs) puede promover el lanzamiento de pequeñas y medianas compañías directamente en el corazón de los mercados globales, nacionales y regionales. La telemedicina puede suministrar acceso actualizado al mejor conocimiento de la ciencia actual incluso desde aquellas comunidades más remotas. Las TIC también pueden facilitar el aprendizaje a distancia a bajo coste y pueden desarrollar el concepto de sociedad civil fortaleciendo las instituciones democráticas, a la vez que hacer más responsables y transparentes las actuaciones de los gobiernos, (Annan, 2002). Sin embargo, el despliegue de redes de telecomunicación se lleva a cabo por compañías privadas. Es por ello que los despliegues de red obedecen a decisiones orientadas a la rentabilidad económica y al beneficio de la compañía, más que otro tipo de decisiones basadas en el estado del bienestar. Por ello es habitual que se produzca el fenómeno denominado como “brecha digital” entre las zonas urbanas y desarrolladas y aquellas rurales menos desarrolladas donde se esperan rendimientos económicos menores. Abundando en estos aspectos la Comisión Europea a través de uno de sus informes (EU Com. Staff, 2003), * El trabajo se deriva de la participación de sus autores en el proyecto financiado por la Junta de Andalucía y titulado “Estudio sobre el despliegue universal de los servicios avanzados de telecomunicaciones en Andalucía”, así como por el M. Ciencia y Tecnolog. en el proyecto ref. TIC2003-04784-C02-01, titulado “Sistema inteligente de ayuda a la toma de decisiones para el despliegue universal de servicios avanzados de telecomunicación”. establece criterios y líneas de actuación para la disposición de fondos estructurales que promuevan el despliegue de servicios avanzados de telecomunicación. El informe defiende la promoción de redes independientes de operadores dominantes que permitan el acceso libre e independiente de criterios económicos asociados a la rentabilidad de la inversión requerida. Con este objeto, la Dirección General de Telecomunicaciones y Sistemas de Información de la Junta de Andalucía y la Escuela Superior de Ingenieros desarrollaron un convenio de colaboración, con objeto el estudio de la viabilidad del despliegue de redes de telecomunicación avanzadas que evitaran el desarrollo de la brecha digital. En este sentido, inicialmente se procedió a agrupar los municipios en una clasificación (ver figura 1). Population Demand Figura 1. Brecha digital en Andalucía: clasificación de municipios Así dicha clasificación incluía: aquellos municipios en los que actualmente existían más de una infraestructura de acceso a servicios avanzados de telecomunicación (ADSL y cable), que formarían el grupo A (Almería, Algeciras, Cádiz, Chiclana de la Frontera, Jerez de la Frontera, La Línea de la Concepción, El Puerto de Santa Maria, Rota, San Fernando, Sanlucar de Barrameda, Córdoba, Granada, Huelva, Jaén, Málaga, Alcalá de Guadaira, Dos Hermanas y Sevilla). La población de estos municipios supone el 43% (3.164.329 habitantes) del total de la oblación andaluza. Aquellos municipios en los que existe una única infraestructura, formando el grupo B (representa el 45%, 3.292,609 habitantes del total andaluz). Hay 262 municipios tipo B. Y, finalmente, aquellos en los que no existe infraestructura de red de alta velocidad, que conformarían el grupo C, 490 municipios el 12%, 883.637 habitantes. Además el grupo B se subdividió en: B1 para aquellos municipios en los que una infraestructura adicional a la existente podría ser rentable, y aquellos en los que no sería (grupo B2). La división entre municipios tipo B1 y B2 se realizó mediante un análisis financiero en el cual la inversión inicial era calculada en función del tamaño del municipio y básicamente dependía del coste de los equipos DSLAM. Los ingresos se estimaban a partir de la demanda esperada y la tarifa mensual de usuario. La demanda fue calculada haciendo uso de una composición del método de las medias móviles, ajuste exponencial, método de Holt y aproximaciones lineal y cuadrática, buscando la minimización del error histórico observado en la composición paramétrica. Los datos de partida eran históricos de los años 2002 y 2003 correspondientes a la instalación de líneas ADSL de alta velocidad (ver figura 2). Figura 2. Evolución de líneas ADSL en Andalucía por provincias en los años 2002-03 De esta forma, los municipios catalogados como tipo B2 y C son aquellos con una mayor dificultad para el despliegue de redes sin el concurso del apoyo estatal, y serán aquellos para los que haya que garantizar el acceso de la red. 2. Alternativas tecnológicas Existen diversas alternativas para el despliegue de redes de alta velocidad. En este sentido es habitual diferenciar entre red de acceso (red urbana) y red dorsal (red interurbana). Backbone Access Network • Switched network: PSTN, IDSN, xDSL) • Cable: HFC • Fixed cellular: WLL-LMDS •Mobile cellular: GSM, UMTS • Satellite: DVB Technological alternatives Topological alternatives •Multiple Star •Ring -Star • Ring - Multiple Star •Ring -Ring Figura 3. Red de acceso y red dorsal Dentro de la red de acceso el coste más importante es el referido al bucle local. En el acceso a red surgen una gran variedad de tecnologías heterogéneas en constante evolución. El medio físico empleado puede ser fibra óptica, cable coaxial, cables de pares, radio o incluso satélite. La tecnología puede estar basada en la tradicional red de telefonía (PSTN, IDSN o XDSL), telecomunicación por cable (redes HFC), redes celulares (WLL o LMDS) y móviles (GSM, UMTS) junto con redes por satélite DVB. Pero la mayor inversión se produce en el despliegue de la red dorsal. Ésta presenta una mayor homogeneidad debido a las ventajas de capacidad y velocidad que ofrece la fibra óptica (ya sea en sistemas tipo SDH o WDM). Aunque varias alternativas pueden ser utilizadas. Éstas dependen de la capacidad de transmisión y de la longitud cubierta por el enlace de red:  Fibra óptica de alta calidad sin regeneradores. Precisan amplificación óptica cada 100 Kms. Se utiliza fibra monomodo de alta calidad dopada con erbio. No precisan conversión electro-óptica y puede ser combinada con sistemas WDM para alcanzar capacidades de hasta 100 Gb/s.  Fibra óptica con regeneradores. Esta opción no requiere equipamiento tan eficiente ni caro. La fibra se regenera cada 40/50 Km. Adecuada para capacidades de hasta 2,4 Gb/s y distancias inferiores a 150 Km.  Radioenlaces. Sólo limitado a capacidades por debajo de 34 Mb/s y con la dificultad añadida de la orografía del terreno. El problema se centra en el diseño de la red dorsal, pero considerando la inversión en la red de acceso. Para la conceptualización del modelo se hace uso de la Teoría de Grafos. 3. Modelo 3.1. Modelo de red Se define un grafo G=(N,A). Los nodos representan municipios del grafo (M-son nodos activos) o simples intersecciones del viario (S-son nodos pasivos) de la red de transporte subyacente (en nuestro caso la red de carreteras y ferrocarril). Los arcos corresponden a la red de transporte definida que fue suministrada por el Instituto de Cartografía de Andalucía (ICA). Dentro del modelo de red se asumen una serie de hipótesis de partida (decisiones estratégicas) que condicionan la topología de red. Éstas son:  La topología de red debe permitir el reencaminado de la comunicación en caso de avería. Por ello se selecciona una topología anillo-árbol. El anillo incluirá a los municipios tipo A que son aquellos entre los que circula mayor cantidad de flujo. El anillo será biridireccional y seguirá, en la medida de lo posible, la red de fibra del anillo de RENFE con el objeto de poder evitar el despliegue del mismo en las primeras fases del proceso, permitiendo el alquiler de fibra oscura. La figura 3 recoge la topología del anillo. SEVILLA MALAGA CÓRDOBA GRANADA HUELVA JAEN ALGECIRAS JEREZ DE LA FRONTERA CADIZ ORGIVA ALMERIA Figura 4. Anillo bidireccional correspondiente a la red troncal de fibra óptica.  El anillo incluye dos peculiaridades. La conexión entre Sevilla-Huelva y Órgiva-Almería mediante dos enlaces paralelos. El primero evita la dificultad del Parque Natural de Doñana, el segundo se fundamenta en una cuestión económica, la lejanía de Almería hace inviable una doble conexión con la duplicidad de kilómetros de obra civil.  Los accesos de la red a Internet son Sevilla y Málaga. 3.2. Modelo de costes Los principales costes son: 1. Costes asociados a nodos: a. Coste fijo asociado a la existencia del nodo, Fi , i∈M. Corresponde a la sala de adecuación del terminal de adaptación de las fibras al DSLAM. b. Coste dependiente de la capacidad gestionada en el nodo. Gi(Ci), i∈M. Corresponde al equipamiento de tarjetas de emisor y receptor. 2. Costes asociados a los arcos: a. Coste dependiente de la longitud del arco, Lij(Dij), (i,j)∈A. Correspondiente a la obra civil (zanjas y conductos). b. Coste dependiente de la longitud del arco y la capacidad máxima que soporta, Cij(Dij,Cmax), (i,j)∈A. Corresponde a los enlaces de fibra óptica incluyendo transmisores, receptores, regeneradores o amplificadores ópticos. Los valores numéricos utilizados para estimar los costes de nodos, y los de arcos tipo 2.a, sólo dependen de la longitud. Mientras que para estimar los costes 2.b existen dos alternativas tecnológicas que se describen a continuación. La primera opción corresponde a fibra óptica de alta calidad sin regeneradores. () ⎥ ⎦ ⎥ ⎢ ⎣ ⎢ ⋅+ ⎥ ⎥ ⎥ ⎤ ⎢ ⎢ ⎢ ⎡ ⋅+⋅++= Gb tr sG ij oam sG ij sG fo d SDHd o SDHo sG ijij C C C D D CDP n P n P CDC 10 2max max max ,(1) Donde:  PSDHo y PSDHd son los costes de los multiplexores SDH origen y destino.  no y nd son el número de enlaces entrantes y salientes de los equipos SDH. Dado que un mismo multiplexor SDH puede atender a distintos enlaces (arcos), sólo debe imputarse la parte proporcional a dicho enlace.  DijsG es la distancia a cubrir sin regeneradores.  PfosG es el coste lineal del cable de fibras monomodo de baja atenuación ya instalado, habitualmente de 128 fibras, incluido tendido, permisos y obra civil asociada. Es necesario instalar un cable con capacidad igual al máximo necesario en el horizonte temporal de que se trate.  Coam es el coste de un sistema de amplificación óptica.  Dmax es la distancia máxima de amplificación, que oscila entre los 100 y 120 Km.  Ctr es el coste de tarjeta de interfaz DWDM con capacidad de 10Gb/s, si se usa DWDM, o el coste de la tarjeta de interfaz del régimen binario que se precise.  Cmax es la capacidad a equipar. Para la segunda opción se considera la instalación de fibras de menor calidad con sistemas de regeneración. () ⎥ ⎦ ⎥ ⎢ ⎣ ⎢ ⋅+ ⎥ ⎥ ⎤ ⎢ ⎢ ⎡ ⋅+⋅++= Gb DWDM ij regijfo d SDHd o SDHo ijij C C C D D CDP n P n P CDC 10 2max max max ,(2) Donde:  PSDHo y PSDHd son los costes de los multiplexores SDH origen y destino.  no y nd son el número de enlaces entrantes y salientes de los equipos SDH. Dado que un mismo multiplexor SDH puede atender a distintos enlaces (arcos), sólo debe imputarse la parte proporcional a dicho enlace.  D es la distancia total a cubrir.  Pfo es el coste lineal del cable de fibras monomodo estándar ya instalado, habitualmente de 128 fibras, incluido tendido, permisos y obra civil asociada.  Dmax es la distancia máxima de regeneración, que oscila entre los 30 y 50 Km.  Creg es el coste del regenerador  Ctr es el coste de tarjeta de interfaz DWDM con capacidad de 10Gb/s, si se usa DWDM, o el coste de la tarjeta de interfaz del régimen binario que se precise. 3.3. Topología La topología elegida fue anillo-árbol, tal y como se indicó en la sección 3.1. Esta topología consiste en una estructura jerárquica sobre nodos de nivel 1 nivel 2, de forma que se busca simplificar la actividad de operación de red. Los nodos de nivel 1 son los 10 municipios de mayor tamaño de Andalucía: Almería, Algeciras, Cádiz, Jerez de la Frontera, Córdoba, Granada, Huelva, Jaén, Málaga y Sevilla. Todos ellos municipios tipo A. Además Órgiva, un pequeño municipio pero con una localización estratégica es seleccionado para formar parte del anillo. Estos nodos conforman el anillo de la dorsal (ver figura 4). El resto de nodos se conectan a éstos a través de una estructura en árbol. Sin embargo, alguno de los nodos restantes puede aparecer incluido bajo la obra civil del propio anillo, en este caso la obra civil no es necesario acometerla, aunque sí el equipamiento telemático de las fibras (típicamente el coste 2.b). La figura 5 muestra el abanico de opciones que se presenta en la estructura indicada. Nodes of level 1 Nodes of level 2 in the ring Nodes of level 2 out of the ring Direct link between nodes of level 1 (ring) Super-branch. Link between nodes of level 1 and level 2 through the ring Branch. Link between nodes of level 2 and level 2 out of the ring Infrastructure. Conduit and ditch Flows between nodes Figura 5. Estructura topológica de la red 4. Algoritmo de solución Las dimensiones de la red, así como las múltiples alternativas topológicas hacen que el problema sea de extrema complejidad computacional. Es fácil comprobar el carácter NP-Duro del problema por simple reducción al de Steiner. Adicionalmente, dada una solución admisible su calidad puede ser computada en tiempo polinomial por lo que el problema es NP-Completo. Bajo estas condiciones, los algoritmos genéticos han mostrado su eficiencia. El empleo de algoritmos genéticos no ha sido muy utilizado en el diseño de redes de telecomunicación, algunos ejemplos de ello son Poon et al. (2000) o Cortés et al. (2001). Para la resolución del problema se acomete la siguiente estrategia de solución: 1. Abstracción del anillo de la red troncal como un supra-nodo. A este supra-nodo se conectarán el resto de municipios de la red. 2. Construcción de un árbol indexado en dicho supra-nodo que incluya al conjunto de nodos de Andalucía. Los nodos pasivos pueden ser utilizados convenientemente pero no han de ser necesariamente utilizados. El algoritmo genético genera esta propuesta de red. 3. Dimensionado de la capacidad del anillo. 4.1. Algoritmo genético 1. Individuos. La población inicial se genera mediante construcción de soluciones admisibles del problema. Posteriormente el proceso de evolución del algoritmo garantiza la conservación de la admisibilidad. La codificación del genoma, así como los operadores genéticos siguen la estructura definida en la figura 6. 2. Operadores genéticos o Operador Cruce. El operador genera soluciones mediante la superposición de estructuras admisibles. Esto genera una estructura no admisible con la aparición de ciclos. Posteriormente, la selección de los arcos a eliminar para generar una estructura admisible se lleva a cabo mediante su eliminación aleatoria. o Operador Mutación. El operador actúa modificando algún enlace de la estructura admisible. Esto genera una estructura no admisible con la aparición de un ciclo. El ciclo se deshace mediante la eliminación de alguno de los enlaces antiguos, seleccionado aleatoriamente. 3. Selección de padres. La selección de los padres se realiza aleatoriamente. Con ello se potencia la exploración del conjunto de soluciones admisibles. 4. Reemplazo de individuos. Sobre ranking basado en la calidad de las soluciones (habitualmente denominada fitness). Se propone una ley hipergeométrica para seleccionar el reemplazo de los individuos. Con ello se potencia la explotación de las mejores soluciones admisibles. 1 0 1 0 0 0 1 0 1 1 1 1 1 0 0 1 1 1 0 0 10/1 1 0 0 0/1 10/10/10/1 1 0 1 0 0 0 1 0 1 1 1 0 1 0 1 0 1 0 1 1 Crossover operator Mutation operator Genome encoding 1 0 1 0 0 0 1 0 1 1 p=1 p=1 p=1/2 p=1/2 mutation A1A2 A3 … Ai … An Parent 1 Parent 2 Offspring Figura 6. Codificación del genoma y operadores Los parámetros empleados en el proceso algorítmico están definidos en la Tabla 1. Tabla 1. Valores numéricos del algoritmo genético Tamaño de la población, N 50 Probabilidad de cruce, pc (Probabilidad de mutación, 1-pc) 0.8 (0.2) Probabilidad para el reemplazamiento basado en ranking, q 0.2/0.8a Máximo número de iteraciones, MAX_ITER 50 a Las primeras iteraciones con probabilidad de reemplazo igual a 0.2 para permitir la exploración geográfica. Las últimas iteraciones con probabilidad igual a 0.7 para incrementar la calidad de la solución mediante la explotación. 4.2. Dimensionado de capacidad en el anillo Una vez construida la red de estructura anillo-árbol, sólo queda establecer la capacidad necesaria del anillo, al ser éste bidireccional se contempla la posibilidad del reencaminado de demanda en caso de fallo en la red. El problema se reduce a determinar la capacidad del anillo que permita el reencaminado de todo el flujo en hipotético caso de fallo. Como el coste del anillo es directamente proporcional a la capacidad del mismo se minimiza la capacidad que garantice la demanda. El hipotético caso genérico se detalla en la figura 7. Internet Seville Internet Malaga CUT F1 F2 F3 F4 Z > maximum {F1, F2 ,F3 ,F4} Figura 7. Reencaminado genérico en caso de fallo A partir de aquí, el procedimiento seguido es similar al descrito en Vachani et al. (1996). Así típicamente se definen cuatro posibles flujos F1, F2, F3 y F4. F1 y F2 vienen impuestos por el corte de red, y F3 y F4 se seleccionan con el objeto de dividir el flujo total a partes iguales. La capacidad del anillo debe ser igual en todos los enlaces, Así se define el flujo de demanda total como la correspondiente a la del arco más saturado. Esto ha de comprobarse para todos los posibles cortes del anillo. 5. Solución de red La figura 8 muestra la solución alcanzada. En la figura se observan tres soluciones (S1, S2 y S3) correspondientes a otros tantos niveles de cobertura poblacional (80%, 90% y 100%). S1. Coverage 80% S2. Coverage 90% S3. Coverage 100% Figura 8. Soluciones de red para niveles de cobertura del 80%, 90% y 100% La solución S1 incluye 616 municipios. La S2 700 municipios, y la S3 incluye todos los municipios de Andalucía (un total de 770).