Resolución HCD 3/12 (reglamentación desarrollo trabajo especial).

Tema: Banco de Pruebas y Evaluación Comparativa de Stacks de Protocolos para Comunicaciones Espaciales Tolerantes a Demoras (En desarrollo por Leandro Acosta)

Director: Dr. Juan A. Fraire

Resumen: La familia d redes tolerantes a demoras (Delay Tolerant Networks o DTN) permiten el uso de enlaces con alta latencia y con disrupciones prolongadas. Una de los casos de usos más populares es el dominio espacial, tanto para redes de órbita cercana a la tierra como de espacio profundo. A pesar de tolerar demoras, hay un marcado interés en que los stacks de protocolos DTNs (RFC 9171) a) puedan interoperar entre ellos para permitir cooperación entre agencias espaciales y b) entregar el máximo throughput posible para aprovechar las escasas oportunidades de contacto espacio-tierra. Por otro lado, existen esfuerzos de interfaces unificadas para que una misma aplicación pueda usar cualquier stack de protocolos DTN (ver unified BP API). En este mismo sentido, ya existen aplicaciones de evaluación de red que trabajan independientemente del stack (ver post Spatiam).

Idea: Este trabajo final tiene como objetivo desarrollar un banco de pruebas basado en software (e.g., máquinas virtuales o contenedores Docker, posiblemente inspirado en CORE) que contengan los stacks de código abierto DTN más populares: ION (de NASA JPL), HDTN (de NASA Glenn), y uD3TN (de D3TN). El banco de pruebas deberá implementar emuladores de enlace que imiten las demoras y disrupciones en los mismos. En base a este desarrollo, el trabajo conluirá con campañas de emulación que evalúen la compatibilidad bajo diferentes configuraciones y la performance de cada uno de estos stacks (e.g., realizar un benchmarking). Además, se presende hacer un profiling para detectar los cuellos de botellas (procesamiento y memoria) en cada implementación, y de ser posible, elaborar sugerencias para mejorar las implementaciones de cara a DTNs de alta capacidad en el futuro.

Contacto: juanfraire@unc.edu.ar

Tema: Estrategias de Aprendizaje Supervisado para la Predicción de Congestión en Redes Espaciales Tolerantes a Demoras

Director: Dr. Juan A. Fraire

Resumen: Las redes tolerantes a demoras (Delay Tolerant Networks o DTN) generalizan las redes tradicionales al permitir la operación en entornos con enlaces con alta latencia y disrupciones prolongadas (posiblemente de minutos u horas), como las evidenciadas por redes espaciales. Para este fin, los nodos DTN cuentan con almacenamiento temporario, mientras que los protocolos y aplicaciones de capa superior se diseñan para minimizar los intercambios de mensajes end-to-end. El principal problema de estas redes es que la carencia de feedback inmediato impide la implementación de mecanismos de mitigación de congestión reactivos como los que se usan en el protocolo TCP. En efecto, en redes DTN la única estrategia es anticiparse al problema, para lo cual los mecanismos de aprendizaje de máquinas tan en boga en la actualidad se presentan como una alternativa atractiva, aunque poco explorada (más detalle).

Idea: Este trabajo final comenzará por realizar una revisión en profundidad de las redes DTN aplicadas al espacio, y en particular sobre los problemas de congestión que las afectan (publicación de referencia). Luego, se retomará una serie de resultados preliminares de predicción de congestión utilizando un modelo Gradient Boosting Regressor (GBR) entrenado con data sets sintéticos generados por medio de simulaciones de evento discretos (link al repo). Durante este trabajo se pulirá el modelo y se lo estudiará en casos más generales para luego evaluar exhaustivamente su precisión. Finalmente, se estudiarán alternativas de implementación de mecanismos de red que permitan hacer uso práctico de las predicciones realizadas, y así, reducir los efectos de la congestión.

Contacto: juanfraire@unc.edu.ar

Tema: Algoritmos de Clustering No-Supervisados y Protocolos de Auto-Configuración para Redes Espaciales (En desarrollo por Pedro Escalera)

Director: Dr. Juan A. Fraire

Resumen: Mientras que Internet asume rutas estables, las redes espaciales y satelitales deben implementar arquitecturas tolerante a demoras (Delay Tolerant Networks o DTN) para operar en contextos de alta disrupción y demora de propagación. Debido a la consideración del aspecto temporal, la escalabilidad de estas redes espaciales ha resultado limitada, especialmente en lo que respecta a la gestión y despliegue de nuevos nodos. Para superar este problema, es necesario automatizar la configuración de regiones (particiones) de la topología así como diseñar mecanismos de auto-configuración. El primer objetivo se conoce bajo el nombre de Inter-Regional Forwarding (más detalle, extendido en esta tesis de maestría), mientras que el segundo supone lograr la asignación de URI a nuevos nodos en el sistema (más detalle).

Idea: Luego de realizar una adecuada revisión bibliográfica de la temática, el trabajo se enfocará en el estudio y comparación de estrategias clustering (aprendizaje de máquina no-supervisado) mediante el cual se puedan generar regiones en estructuras de datos conocidas como contact plans o planes de contactos. Luego, se explorarán estrategias de auto-configuración que permitan la incorporación de nuevos nodos a la topología, adaptando dinámicamente la definición de regiones. Finalmente, las soluciones se evaluarán en plataformas de simulación como DTNSim (ver presentación, y paper del simulador).

Contacto: juanfraire@unc.edu.ar

Tema: Análisis de Grafos para Redes Tolerantes a Demoras (En desarrollo por Uziel Ludeña)

Director: Dr. Juan A. Fraire

Resumen: La Internet y sus protocolos asumen cierta estabilidad en los enlaces de comunicaciones, lo que permite el uso de estructuras de grafos estáticas para razonar sobre las topologías (i.e., enrutar, optimizar, etc.). Sin embargo, las redes tolerantes a demoras (Delay Tolerant Networks o DTN) -típicamente particionadas- (i.e., redes espaciales, vehiculares, y sub-acuaticas) requieren de estructuras de datos más generales. Una de ellas se conoce como grafos evolutivos en el tiempo (time-evolving graphs), en los que el tiempo se discretiza, para así aprovechar un grafo estático que describe la red en un intervalo de tiempo donde permanece estable (más detalle). Debido a la escasa escalabilidad de este enfoque, una estructura de datos alternativa llamada grafos de contactos (contact graphs) ha tomado relevancia, y es hoy parte de los stacks de protocolos DTN más populares, aunque existen pocos análisis que justifiquen su elección (más detalle).

Idea: Durante este trabajo se hará una revisión exhaustiva de la literatura alrededor de protocolos y modelos DTNs, así como de las estructuras de datos mencionadas (time-evolving graphs y contact graphs). En base a esto se desarrollará una herramienta de simulación y análisis que permita ganar intuición sobre el rendimiento de algoritmos (i.e., Dijkstra, Shortest-Path Tree, etc.) sobre cada una de ellas (ver prototipo). Los resultados obtenidos se basarán en casos de uso concretos y serán utilizados para validar un análisis teórico/formal que compare ambas estructuras de datos en general.

Contacto: juanfraire@unc.edu.ar

Tema: Diseño de Topologías de Red y Protocolos de Comunicaciones a Escala Interestelar (En desarrollo por Juan Costamagna)

Director: Dr. Juan A. Fraire

Resumen: El reciente descubrimiento de planetas potencialmente habitables en estrellas remotas (i.e., TRAPPIST-1) ha renovado el interés en la exploración interestelar. A pesar de que el objeto más lejano creado por el humano (Voyager 1) podría tomar miles de años en llegar la estrella más cercana (Próxima Centauri), numerosos proyectos han propuesto ideas de propulsión (y sistemas de energía) para reducir esta duración en órdenes de magnitud. Lo que aún requiere de mayor discusión (y que motiva este trabajo) es el análisis de estrategias y arquitecturas de comunicaciones para dar soporte al transporte de datos en dichas misiones. En particular, resulta inevitable recurrir a estrategias de múltiples saltos, lo que demandaría un sistema en red tolerantes a demoras de escala y latencia sin precedentes (más detalle).

Idea: Realizar una revisión bibliográfica en profundidad del entorno interestelar cercano, así como de las tecnologías recientemente propuestas. En base a estas, identificar mecanismos de diseño de topologías en red (i.e., métodos MILP, algoritmos de spanning tree) que permitan dotar de conectividad a misiones interestelares con la mínima latencia y recursos. Finalmente, y aprovechando las topologías obtenidas, se evaluará por medio de simulaciones de eventos discreto posibles protocolos de transporte de datos.

Contacto: juanfraire@unc.edu.ar

Tema: Algoritmos de Consenso para una Economía Interplanetaria. (En desarrollo por Ezekiel Carranza)

Director: Dr. Juan A. Fraire

Resumen: La cantidad de objetos creados por el hombre en el espacio crece exponencialmente en el marco del new space. Ya son corrientes las misiones de espacio profundo basadas en nanosatélites, que habilitarán aplicaciones futuristas basadas en redes federadas y autónomas a escala interplanetaria. En este marco, este trabajo propone explorar mecanismos de transferencia de valor digital entre naves en el espacio exterior tal como lo hacen Bitcoin o Ethereum hoy en tierra. Sin embargo, los mecanismos de consenso proof of work o proof of stake son inviables para el entorno espacial, por lo que deberían ser reemplazados por alternativas basadas en proof of authority o directed acyclic graphs (más detalle).

Idea: Elaborar un estudio del estado del arte de los algoritmos de consenso disponibles. Identificar algoritmos o adaptaciones específicas que satisfagan las condiciones de cómputo y conectividad de las redes espacio profundo. Implementar un modelo analítico o de simulación (a definir en función de la alternativa identificada) que permita el estudio y validación del concepto (más detalle).

Contacto: juanfraire@unc.edu.ar

Tema: Actualización de formalización de Lua a su útlima versión.

Resumen: Lua es un lenguaje de programación dinámico, con mecanismos de meta-programación que permiten adaptar el lenguajes a dominios específicos. Incluye a su vez una API madura que facilita la tarea de embeber programas Lua dentro de aplicaciones escritas en C, permitiendo así extender las características ofrecidas por C con nuevas facilidades útiles para la rápida implementación de pequeñas aplicaciones (como tipado dinámico, junto con recolección de basura). Es ampliamente utilizado en la industria de los video juegos, o como lenguaje para implementar extensiones a aplicaciones [1].

A los fines de desarrollar herramientas que faciliten el análisis de código Lua, se precisa de una semántica formal del mismo. Actualmente se cuenta con una semántica para la versión 5.2 del lenguaje [2], utilizando un estilo operacional, junto con conceptos de reduction semantics [3]. A su vez se dispone de una mecanización de la semántica, utilizando la herramienta PLT Redex [4], lo que permitió testear el modelo con respecto a la suite de tests del intérprete oficial de Lua.

La versión estable más reciente del lenguaje es la 5.3 [5], en la cual se agregan nuevos operadores, nuevos servicios de librería estándar y cambios en la semántica de los mecanismos de metaprogramación.

Idea: La propuesta de este trabajo consiste en actualizar lo necesario del modelo presentado en [2], para adecuarlo a la versión 5.3. Esto incluye modificar el modelo formal, mecanizarlo en PLT Redex y testearlo. Por las características de la tarea hay un amplio margen de libertad para adecuar el trabajo a los tiempos/interés del/la tesista,

Directores: Beta Ziliani y Mallku Soldevila.

Referencias:

1. https://www.lua.org/uses.html
2. Soldevila M, Silvestre B, Ziliani B (2022) From Specification to Testing: Semantics Engineering for Lua 5.2. In: Journal of Automated Reasoning (pdf).
3. https://en.wikipedia.org/wiki/Operational_semantics#Reduction_semantics. También https://mitpress.mit.edu/books/semantics-engineering-plt-redex, libro en biblioteca.
4. https://redex.racket-lang.org/
5. https://www.lua.org/manual/5.3/manual.html

Tema: Modelado “liviano” de la semántica de Crystal mediante tests.

Resumen: El lenguaje de programación open source Crystal, nacido en Argentina, posee muchas características que lo hacen un lenguaje único. Con una sintaxis que se asemeja a Ruby, posee un sistema de tipos y es compilado a llvm, lo que lo hace eficiente y portable. Para no sobrecargar con información de tipos al/a la desarrollador/a, Crystal permite omitir la información de tipado, infiriéndola a partir del contexto.

Actualmente las semánticas del lenguaje y su inferidor de tipos se encuentran testeadas con una batería de tests surgidos de los reportes de bugs de les usuaries del lenguaje.

Idea: El objetivo de esta tesis será entonces extender la batería de tests con programas que busquen estresar los aspectos críticos del lenguaje, para así poder definir, mediante tests, la semántica esperada del lenguaje.

Director: Beta Ziliani

Tema: Procesamiento automático para diálogos ruidosos generados por estudiantes.

Resumen: En el marco de un proyecto de colaboración entre FAMAF y la Universidad de Stanford, se busca un estudiante avanzado de la Licenciatura en Ciencias de la Computación de FAMAF para realizar su trabajo final en el área de “Automatic processing of noisy student-generated dialogues”. El trabajo se realiza en cooperación con la empresa https://www.yup.com/, quien provee diálogos para su análisis automático.

Idea: Aquí podrán encontrar resultados preliminares del proyecto publicados en The 4th Workshop on Noisy User-generated Text (W-NUT), 2018 Conference on Empirical Methods for Natural Language Processing (EMNLP). Para los estudiantes interesados en conocer más detalles: contactar a la directora adjuntando un listado de materias aprobadas (que puede ser obtenido desde guarani) y describiendo brevemente su nivel de Inglés.

Director: Luciana Benotti