211service.com
El nuevo enfoque de la conectividad de vértice podría maximizar el ancho de banda de las redes
Los informáticos buscan constantemente formas de extraer cada vez más ancho de banda de las redes de comunicaciones.
Ahora, un nuevo enfoque para comprender un concepto básico en la teoría de grafos, conocido como conectividad de vértice, podría conducir en última instancia a protocolos de comunicación, las reglas que gobiernan cómo se intercambian los mensajes digitales, que obtienen la mayor cantidad de ancho de banda posible de las redes.
La teoría de grafos juega un papel central en las matemáticas y la informática, y se utiliza para describir la relación entre diferentes objetos. Cada gráfico consta de una serie de nodos, o vértices, que representan los objetos y líneas de conexión entre ellos, conocidas como aristas, que significan las relaciones entre ellos. Una red de comunicaciones, por ejemplo, se puede representar como un gráfico con cada nodo de la red como un vértice y una conexión entre dos nodos representada como un borde.
Uno de los conceptos fundamentales dentro de la teoría de grafos es la conectividad, que tiene dos variantes: conectividad de borde y conectividad de vértice. Estos son números que determinan cuántas líneas o nodos deberían eliminarse de un gráfico dado para desconectarlo. Cuanto menor sea el número de conectividad de borde o de conectividad de vértice de un gráfico, por lo tanto, más fácil será desconectarlo o separarlo.
De esta manera, ambos conceptos muestran cuán robusta es una red contra fallas y cuánto flujo puede pasar a través de ella, ya sea el flujo de información en una red de comunicaciones, el flujo de tráfico en un sistema de transporte o el flujo de fluidos en la hidráulica.
Reducir el borde de la conectividad de borde
Sin embargo, si bien se ha llevado a cabo una gran cantidad de investigación en matemáticas para resolver problemas asociados con la conectividad de borde, ha habido relativamente poco éxito en responder preguntas sobre la conectividad de vértice.
Pero en el Simposio ACM-SIAM sobre algoritmos discretos en Portland, Oregon, en enero, Mohsen Ghaffari, un estudiante de posgrado en el Laboratorio de Informática e Inteligencia Artificial en el MIT, presentará una nueva técnica para abordar los problemas de conectividad de vértices.
En última instancia, esto podría ayudarnos a comprender cómo construir redes más robustas y rápidas, dice Ghaffari, quien desarrolló el nuevo enfoque junto con Keren Censor-Hillel en el Technion y Fabian Kuhn en la Universidad de Friburgo.
En la década de 1960, los matemáticos William Tutte y Crispin Nash-Williams desarrollaron por separado teorías sobre estructuras llamadas árboles de expansión disjuntos de bordes, que ahora sirven como una de las herramientas técnicas clave en muchos problemas sobre la conectividad de bordes.
Un árbol de expansión es un subgráfico, o un gráfico dentro de un gráfico, en el que todos los nodos están conectados por el menor número de bordes. Un conjunto de árboles de expansión dentro de un gráfico se denomina borde disjunto si no comparten ninguna de estas líneas de conexión.
Si una red contiene tres árboles de expansión disjuntos de borde, por ejemplo, la información puede fluir en paralelo a lo largo de cada uno de estos árboles al mismo tiempo, lo que significa tres veces más ancho de banda de lo que sería posible en un gráfico que contiene solo un árbol. Cuanto mayor sea el número de árboles de expansión disjuntos de bordes, mayor será el flujo de información, dice Ghaffari. Los resultados de Tutte y Nash-Williams muestran que cada gráfico contiene casi tantos árboles de expansión como su conectividad de borde, dice.
Ahora el equipo ha creado una teoría análoga sobre la conectividad de vértices. Lo hicieron dividiendo el gráfico en grupos separados de nodos, conocidos como conjuntos dominantes conectados. En la teoría de grafos, un grupo de nodos se denomina conjunto dominante conectado si todos los vértices que contiene están conectados entre sí, y cualquier otro nodo dentro del grafo es adyacente al menos a uno de los que están dentro del grupo.
De esta forma, la información se puede difundir entre los nodos del conjunto y luego pasar a cualquier otro nodo de la red.
Entonces, de manera similar a los resultados de Tutte y Nash-Williams para la conectividad de borde, cada gráfico contiene casi tantos conjuntos dominantes conectados disjuntos de vértice como su conectividad de vértice, dice Ghaffari.
Entonces, si piensa en una aplicación como transmitir información a través de una red, ahora podemos descomponer la red en muchos grupos, cada uno de los cuales es un conjunto dominante conectado, dice. Luego, cada uno de estos grupos será responsable de transmitir una serie de mensajes, y todos los grupos trabajarán en paralelo para transmitir todos los mensajes rápidamente, casi tan rápido como sea posible.
El equipo ha desarrollado ahora un algoritmo que puede descomponer cuidadosamente una red en muchos conjuntos dominantes conectados. De esta manera, puede estructurar las llamadas redes inalámbricas ad hoc, en las que los nodos individuales enrutan los datos pasándolos de uno a otro para garantizar la mejor velocidad posible de flujo de información. Queremos poder difundir tanta información como sea posible por unidad de tiempo, para crear redes cada vez más rápidas, dice Ghaffari. Y cuando un gráfico tiene una mejor conectividad de vértice, permite un mayor flujo [de información], agrega.
Aplicaciones para evaluar la robustez
Los investigadores también pueden utilizar su nuevo enfoque para analizar la solidez de una red frente a fallas aleatorias. Estas nuevas técnicas también nos permiten analizar si es probable que una red permanezca conectada cuando sus nodos fallan aleatoriamente con alguna probabilidad dada, dice Ghaffari. La confiabilidad contra fallas de borde aleatorias es bien conocida, pero sabíamos mucho menos sobre eso contra fallas de nodos, agrega.
Noga Alon, profesor de matemáticas y ciencias de la computación en la Universidad de Tel Aviv, dice que Ghaffari y sus colegas autores han identificado la noción que determina el mayor flujo alcanzable al transmitir mensajes utilizando enrutamiento en redes de comunicación.
La investigación de esta noción, vértices disjuntos conjuntos dominantes conectados, se trata en este artículo mediante una elegante combinación de técnicas combinatorias, probabilísticas y algorítmicas, dice.