INFORME FINAL GOBIERNO DE CHILE CONICYT FONDECVT

PROYECTO FON D ECYT REGULAR

1060695

2 AÑOS

1

2006

1

. ;DURACIO: MIGUEL FELIX RIOS OJEDA

;.;ANODEEJECUcTON.

RUT

INVESTIGADOR(A) RESPONSABLE

354-4291

DIRECCION

mrios©ing. puc.cI PERÍODO QUE INFORMA

15

/

DESDE

3

/

07

15

/

/

3

HASTA

08

CONTENIDO

(MARQUE CON UNA X EL CASILLERO QUE CORRESPONDA) INCLUYE Formulario de Informe Final Publicaciones Resumen de Tesis Título/Grado Información acerca de inventos y patentes

NO INCLUYE

X

X X X

Otros (especificar)____________________ Informe Incentivo Coop. Internacional (Si corresponde)

Firma Coinvestiga^or Vladimir Marianov

Christian Oberli



Firma Investigador(a esponsable

^ . 01-^, a: _14]_3J_2008

CONTENIDO DEL INFORME FINAL 1. CUMPLIMIENTO DE LOS OBJETIVOS PLANTEADOS EN EL PROYECTO. Marque con una X el casillero correspondiente.

Objetivos

Cumplimiento Total

Parcial

No

el cumplimiento Fundamentar parcial o incumplimiento

1 Wired and Wireless IP Networks X Modeling with Q0S constraints. General objective is the formulation of sorne models for the desígn problem of reliable IP networks with end-toend Q0S constraints. Specific goals of the modeis are findirig models through a) selection of the location of routers; b) selection of the router types; c) selection of the interface card types; d) design of the access and the backbone network; e) selection of the link types. 2 Voice over IP Q0S. Speciflc goals X are searching for: a) improved contraint based routing and traffic engineering methods, which aim at selecting the paths on which voice information is routed to guarantee acceptable delays as well as reserving sufficient capacity for the expected bandwidth better b) load; management and admission control rnethods, which handie requests for bandwidth allocation for VoIP calls and limit the number of calls in progress to cornply with the allocation; c) improved QoS for established voice calis methods; which ensure that accepted calls are given the proper priority so that the committed Q0S leve¡ can be rnet even if a link is congested due to non real time traffic; d) better adaptive coding methods, which reduce bandwidth consumption under congestion and still provide good QoS to calis in progress. Otro(s) aspecto(s) que Ud. considere importante(s) en la evaluación del cumplimiento de los objetivos planteados en la propuesta original o en las modificaciones autorizadas por los Consejos.

2

II. RESULTADOS OBTENIDOS Describa brevemente los resultados obtenidos en el proyecto en un máximo de cinco páginas, tamaño carta, espacio seguido. Para cada uno de los objetivos específicos, describa o resuma los resultados. Relacione las publicaciones y/o manuscritos enviados a publicación con los objetivos específicos. Incluya en anexos, la información de apoyo que estime pertinente y necesaria para la evaluación.

Se trabajó en los siguientes aspectos de la investigación propuesta: a) Wired and Wireless IP Networks Modelin g with QoS constraints. General objective is the formulation of sorne modeis for the design prob/ern of re/jable IP networks wíth end-to-end QoS constraints. Speciflc goals of the modeis are finding models through a) selection of the location of routers; b) se/ection of the router types; c) selection of the interface card types; d) design of the access and the backbone network; e) selection of the link types.

En el tema de calidad de servicio (Q0S), se trabajó en la temática de control de admisión. En la mayor parte de las redes con arquitectura DiffServ existe un agente denominado "bandwidth broker" (BB) que controla y administra los recursos. Entre las funciones de este agente se encuentra el realizar un control de admisión de los flujos que entran la red, de modo de evitar que nuevos flujos deterioren la calidad de servicio que reciben los otros clientes. Cuando la demanda de la red es muy alta (muchas llamadas por minuto), la red es muy extensa, o el esquema de control es muy complejo, el broker puede llegar a convertirse en un problema. En estos casos el BB se actúa como un verdadero cuello de botella, limitando la cantidad de flujos que entran la red e incluso rechazando algunos cuando en realidad todavía hay recursos disponibles. Es por esto que se hace necesario desarrollar arquitecturas con varios BBs que manejen de forma distribuida y coordinada la red. Se propuso el algoritmo P0QBA, que entrega una nueva forma de realizar el control de admisión que se adapta perfectamente a los sistemas distribuidos y busca maximizar las ganancias de la red. Este nuevo esquema reduce el overhead que generan otras soluciones y presenta excelentes características para ser incorporado en redes de gran escala. Los resultados se presentaron en una Tesis de Magister en Ciencias de la Ingeniería, y en la Conferencia NBIS 2007 y se publicaron en la serie Lecture Notes on Computer Science. Una versión extendida del trabajo se envió a la revista Computer Communications. En el tema de localización de enrutadores, se trabajó en el diseño óptimo de una red jerárquica de dos niveles que permite interconectar todos los nodos de una red dada, proponiéndose un procedimiento de dos etapas, el cual también permite determinar la localización de los nodos origen y destino. Los resultados serán publicados en la revista Operations Research Letters. b) Voice over IP 005. Specific goa!s are searching for: a) improved contraint based routing and trafflc engineering methods, which aim at selecting the paths on which voice information is routed to guarantee acceptable delays as well as reserving sufficient capacity for the expected load; b) better bandwidth management and admiss ion control methods, which handle requests for baridwídth a/loca tion for VoIP ca/ls and limit the number of ca/ls in pro gress to comp/y with the a/loca tion; c) improved QoS for established voice ca/ls methods; which ensure that accepted ca/ls are given the proper priority 50 that the committed QoS level can be met even if a link is con gested due to non real time traffic; d) better ada ptive coding methods, which reduce bandwidth consumption under con gestion and still pro vide good Q0S to ca/ls in pro gress.

En el tema de algoritmos de enrutamiento, se trabajó en el tema de encolamiento equitativo (Fair Queueing). Estos algortimos se diseñan para proporcionar una localización de ancho banda equitativa y tienen muchas carateristicas que son deseables en el control de congestión en la Internet. Sin embargo, dichos algoritmos usualmente requieren mantener información de cada flujo, lo que significa problemas de complejidad que pueden hacerlos poco eficientes y poco escalables. Se propuso el algoritmo PFQA (Priority Fair Queueing Algorithm) que se orienta a reducir la complejidad de implementación, mientras se soporta un sistema con anchos de banda equitativos. La red se supone dividida en zonas en que se situan enrutadores de frontera y de interiores. Los enrutadores de frontera asignan prioridades aleatorias a los paquetes de los flujos de entrada. Los enrutadores de interior, encolan los paquetes de alta prioridad y proceden a descartar los paquetes de menor prioridad al momento que la cola alcanza el gg% de su capacidad. En tales condiciones, un subprograma se activa que reduce la tasa de entrada en etapas de 1% hasta que la congestión desaparece. El comportamiento de PFQA se compara favorablemente con otros algoritmos de encolamiento equitativo. Los resultados fueron publicados en el 2006 Summer Computer Simulation Conference.

En el tema de algoritmos de enrutamiento en redes Ad-Hoc, se trabajó en nuevos algoritmos de enrutarniento. Las redes Ad-Hoc son un tipo de redes inalámbricas conformadas por dispositivos los cuales funcionan como host y como enrutador en forma simultánea. Debido a esto, estas redes no necesitan infraestructura adicional ni dependen de una infraestructura central. Son sistemas autónomos cuya configuración es automática. En los últimos años se ha generado un interés creciente en este tipo de redes ya que éstas son capaces de satisfacer múltiples aplicaciones. La investigación ha sido orientada al diseño de un sistema compatible con la arquitectura OSI, desarrollando protocolos eficientes en torno a las dos restricciones más críticas de este tipo de redes: El ahorro de energía y el uso eficiente de ancho de banda. Estos dos conceptos han motivado el desarrollo de diversas técnicas de enrutamiento. Se ha puesto especial atención en el diseño de algoritmos capaces de funcionar en el medio inalámbrico y que puedan converger rápidamente a las rutas solicitadas. Los algoritmos existentes al día de hoy tienen limitaciones claras de escalabilidad y movilidad y muchos de estos utilizan una cantidad importante de ancho de banda para poder ser utilizados. La investigación se centró en la asignación eficiente de tiempos de expiración de rutas con el fin de evitar procesos de descubrimiento adicionales. La determinación de un tiempo de expiración óptimo es un problema poco explorado. Por lo general en la mayoría de las investigaciones se utilizan valores arbitrarios para este parámetro. Se ha investigado anteriormente la existencia de un tiempo de expiración óptimo en algoritmos de enrutamiento Ad-Hoc. Este parámetro corresponde a un valor fijo de configuración que se asigna a todas las rutas que se forman. Sin embargo se puede demostrar matemáticamente que la probabilidad de falla de una ruta en el tiempo depende de su tamaño. Por lo tanto el uso de tiempos de expiración fijos no es necesariamente eficiente. En esta investigación se propuso la asignación variable de tiempos de expiración para rutas en función de su tamaño y se desarrolló el método VTOA (Variable TimeOut Allocation). Los resultados se presentaron en una Tesis de Magíster en Ciencias de la Ingeniería y se enviaron a la revista Wireless Communications and Mobile Computing. Finalmente, un estudiante memorista, está trabajando en el tema de implementar una central telefónica IP sobre una arquitectura de nueva generación como lo es IMS (IP Multimedia Subsystem). Para lograr esto se instalarán dos equipos como servidores. Uno se habilitará para instalar la central telefónica, Asterisk, y en el segundo se instalarán módulos que pertenecen a la arquitectura IMS. Los resultados se presentarán en una Memoria de Ingeniero Civil de Industrias con Diploma en Ingeniería Eléctrica, en desarrollo.

4

III. PRODUCTOS GENERADOS POR EL PROYECTO En esta sección debe incluir todo documento o material cuyo contenido corresponda substancialmente a los objetivos del proyecto que se informa y en los que se indique el N° del proyecto FONDECYT. Aténgase a los formatos que se incluyen para cada tipo de producto generado. Adjunte copia de los documentos no enviados previamente a FONDECYT. Utilice las hojas adicionales que sean necesarias. Si Ud. tiene un proyecto de Incentivo a la Cooperación Internacional, destaque con (*) las publicaciones generadas como producto del mismo a continuación de las que corresponden al Regu!_____________________ 1. Artículos en revistas científicas nacionales o extranjeras con Comité Editorial. Marque con una "X" lo que corresponda. Para trabajos En Prensa/ Aceptados/ Enviados adjunte copia de carta de aceptación o de envío.

Autor(a)(es/as)

Enrique Peña, Miguel Ríos, Christian Oberli, Viadimir Marianov

Título (Idioma Original)

P0QBA: A New Path Admission Control for Diffserv Networks

Nombre Completo de la Revista.

Lecture Notes in Computer Science

Ref. bibliográfica

Año: 2007 Vol. 4658

Estado de la publicación a la fecha.*

• Publicada

Otras fuentes de financiamiento, si las hay

r^

Pág. 435-445

E Aceptada ¡En Prensa Proyecto ACT-32 1

LIJ

E En preparación

Enviada -

Autor(a)(es/as)

Juan Pablo BatIle, Miguel Ríos, Viadimir Marianov, Christian Oberli

Título (Idioma Original)

Variable Timeout Allocation for Reactive Routing Networks

JTñ1Dre Completo de la Revista.

Wireless Communications and Mobile Computing

Ref. bibliográfica

Año:

Estado de la publicación a la fecha.*

O

E Aceptada Publicada ¡En Prensa Proyecto ACT-32 Otras fuentes de financiamiento, si las hay 1



Protocols on Ad-hoc

V/'

Pág.

• Enviada

E

En preparación -

Autor(a)(es/as)

Carlos Obreque, Vladimir Marianov, Miguel Ríos

Título (Idioma Original)

Optimal Design of Hierarchical Networks with Free Main Path Extremes

Nombre Completo de la Revista.

Operations Research Letters

Ref. bibliográfica

En prensa

Estado de la publicación a la fecha.*

• Publicada

Otras fuentes de financiamiento, si las hay

E Aceptada ¡En Prensa Proyecto Fondecyt 1070741

E Enviada

E En preparación

/

Autor(a)(es/as)

Enrique Peña, Miguel Ríos

Título (Idioma Original)

Path Admission Control for Book Ahead Requests on Diffserv Networks

NomBre Completo de la Revista.

Computer Communications

Ref. bibliográfica

En prensa

Estado de la publicación a la fecha.*

O

Otras fuentes de financiamiento, si las hay

Publicada ¡En Prensa Proyecto ACT-32

El Aceptada

--

• Enviada

El En preparación

2. Otras publicaciones/productos. Autor(a) (es/as) Título (Idioma Original)

Tipo de publicación o producto Marque con una "X"Ioque

corresponda

El Monografía

El Libro El Capítulo de Libro E] Mapa E] Exposición de Arte Otro, Especificar:

Editor(es) (Libros o Capítulos de

Libros)

Nombre de la Editorial! Organización Lugar y Fecha de Publicación

País: Fecha:

El Seminario /Taller ¡Curso El Informe Técnico El Software

E] Patente

3. Presentaciones a Congresos Nacionales e Internacionales. Adjunte copia del resumen o texto de fa ponencia y de fa tapa de/libro de Resúmenes, si no la ha enviado previamente.

Autor(a)(es/as)

Enrique Peña, Miguel Ríos, Christian Oberli, Vladimir Marianov

Título (Idioma Origina)

P0QBA: A New Path Admission Control for Diffserv Networks

Nomre del Congreso First Internacional Conference on Network-Based Information Systems Ciudad:Regensburg

Fecha: Septiembre 2007

Lugar y Fecha

País: Alemania

Autor(a)(es/as)

Miguel Ríos, Vladimir Marianov, Yng lee

Título (Idioma Original)

Priority Fair Queueing Algorithm for Data Flows over internet Routers

Nombre del Congreso 2006 Summer Computer Sirriulation Conference Lugar y Fecha

Ciudad: Calgary

País: Canada

Fecha:]ulio 31- Agosto 2, 2006

Autor(a)(ésfas) Título (Idioma Original) Nombre del Congreso Lugar y Fecha

1Ciudad:

Fecha:

País:

Ciudad:

Fecha:

País:

Ciudad:

Fecha:

País:

-

Autor(a) (es/as) Título (Idioma Original) Nombre del Congreso Lugar y Fecha

Autor(a)(es/as) Título (Idioma Original) Nombre del Congreso Lugar Fecha

7

-

4. Tesis y /0 Memorias en ejecución y /0 terminadas en el marco del proyecto. Adjunte copia del resumen no informado anteriormente y certificación de aprobación, si corresponde.

Títuio de la Tesis

Path Admission Control for Book Ahead Requests on Diffserv Networks

Nombre y Apellidos del(de la)/de los(las) Alumno(a)(os/as) yjJtor(a) Título/ Grado

Enrique Peña Icaza

Institución, Facultad, Departamento

Magister en Ciencias de la Ingenien a Pontificia Universidad Católica de Chile, Ingeniería, Ingeniería Eléctrica

Lugar

País: Chile Ciudad: Santiago

Estaco de Tesis

En Ejecución:

Terminada: X

Fecha de Inicio Sep. 2005 Fecha de Termino Enero 2007

TtTO deiTesis Nombre y Apellidos del(de la)/de los(las) Alumno(a)(os/as) Título/ Grado Institución, Facultad, Departamento

Asignación Variable de Tiempos de Expiración de Rutas para Algoritmos Reactivos de Redes Ad-Hoc Juan Pablo BatIle Lathrop

Magister en Ciencias de la Ingeniería Pontificia Universidad Católica de Chile, Ingeniería, Ingeniería Eléctrica

Lugar

País: Chile Ciudad: Santiago

Estado de Tesis

En Ejecución:

Terminada: X

Fecha de Inicio Marzo 2006 Fecha de Termino Agosto 2007

iidTa Tesis Nombre y Apellidos del(de la)/de los(las) Alu mno(a) (os/as) yjtorja) Título! Grado Institución, Facultad, patarnento

Diseño e Implementación de una Plataforma Distribuida de Comunicaciones Multimedia Compatible con Arquitectura IMS Alvaro Hayato Ehijo Tsunekawa

Ingeniero Civil de Industrias con Diploma en Ingeniería Eléctrica Pontificia Universidad Católica de Chile, Ingeniería, Ingeniería Eléctrica

Lugar

País: Chile Ciudad: Santiago

Estado de Tesis

En Ejecución:

X Terminada:

Fecha de Inicio Septiembre 2007 Fecha de Termino Mayo 2008

IV. DESTAQUE OTROS LOGROS DEL PROYECTO TALES COMO:

• Estadías de investigación. • Formación de recursos humanos exceptuando tesistas ya informados. • Actividades de difusión y/o extensión en la temática del proyecto. • Cualquier otro logro no contemplado en los ítem anteriores y que Ud. quiera destacar.

En Septiembre de 2007, se realizó una estadía de investigación al KOM Multimedia Communications Lab, de la Universidad Técnica de Darmstadt, Alemania, con una invitación del profesor Raif Steinmetz, Director del laboratorio. En la visita se realizó una charla y se mantuvo conversaciones con varios miembros del laboratorio, dirigidas a establecer un programa de investigación conjunto. Como resultado de estas conversaciones, la Pontificia Universidad Católica de Chile y la Universidad Técnica de Darmstadt firmaron Acuerdos de Colaboración. También, recientemente, se ha integrado a las actividades del proyecto una estudiante de intercambio, proveniente de la Universidad Politécnica de Cataluña, quien realizará su memoria de grado en la temática del proyecto.

V. RESUMEN Describa en forma precisa y breve el tópico general del proyecto, sus metas y objetivos y los resultados alcanzados. Utilice un lenguaje apropiado para la comprensión del público no especialista en el tema. Esta información podrá ser difundida. (No debe exceder este espacio en fuente Verdana 9)

Las redes de comunicaciones móviles futures deberán soportar accesos heterogeneos a los canales de radio y ofrecer servicios independientes de las tecnologías utilizadas. La tendencia actual es que tales redes estarán basadas en el empleo de protocolos IP. Uno de los aspectos claves para conseguir esos objetivos es el de la calidad de servicio (Q0S). Esta investigación abarcó una serie de temas en esa dirección. a) Control de admisión: En la mayor parte de las redes con arquitectura DiffServ existe un agente denominado "bandwidth broker" (BB) que controla y administra los recursos. Entre las funciones de este agente se encuentra el realizar un control de admisión de los flujos que entran la red, de modo de evitar que nuevos flujos deterioren la calidad de servicio que reciben los otros clientes. Cuando la demanda de la red es muy alta (muchas llamadas por minuto), la red es muy extensa, o el esquema de control es muy complejo, el broker puede llegar a convertirse en un problema. En estos casos el BB se actúa como un verdadero cuello de botella, limitando la cantidad de flujos que entran la red e incluso rechazando algunos cuando en realidad todavía hay recursos disponibles. Es por esto que se hace necesario desarrollar arquitecturas con varios BBs que manejen de forma distribuida y coordinada la red. Se propuso el algoritmo PoQBA, que entrega una nueva forma de realizar el control de admisión que se adapta perfectamente a los sistemas distribuidos y busca maximizar las ganancias de la red. b) Algoritmos de enrutamiento: se trabajó en el tema de encolamiento equitativo (Fair Queueing). Estos algortimos se diseñan para proporcionar una localización de ancho banda equitativa y tienen muchas caraterísticas que son deseables en el control de congestión en la Internet. Sin embargo, dichos algoritmos usualmente requieren mantener información de cada flujo, lo que significa problemas de complejidad que pueden hacerlos poco eficientes y poco escalables. Se propuso el algoritmo PFQA (Priority Fair Queueing Algorithm) que se orienta a reducir la complejidad de implementación, mientras se soporta un sistema con anchos de banda equitativos. c) Enrutamiento en redes Ad-Hoc: se trabajó en nuevos algoritmos de enrutamiento. Las redes Ad-Hoc son un tipo de redes inalámbricas conformadas por dispositivos móviles los cuales funcionan, a la vez, como terminales y como enrutadores. Debido a esto, estas redes no necesitan una infraestructura adicional ni dependen de una infraestructura central. La investigación se centró en la asignación eficiente de los tiempos de expiración de rutas, las cuales varían en el tiempo, con el fin de evitar procesos de descubrimiento de ruta adicionales. La determinación de un tiempo de expiración óptimo es un problema poco explorado. Por lo general en la mayoría de las investigaciones se utilizan valores arbitrarios para este parámetro. Se ha investigado anteriormente la existencia de un tiempo de expiración óptimo en algoritmos de enrutmiento Ad-Hoc. Este parámetro corresponde a un valor fijo de configuración que se asigna a todas las rutas que se forman. Sin embargo se puede demostrar matemáticamente que la probabilidad de falla de una ruta en el tiempo depende de su tamaño. Por lo tanto el uso de tiempos de expiración fijos no es necesariamente eficiente. En esta investigación se propuso la asignación variable de tiempos de expiración para rutas en función de su tamaño y se desarrolló el método VTOA (Variable TimeOut Allocation).

10