Материалы портала «Научная Россия»

Аспирант представил алгоритм теории графов, позволяющий добиться предельного быстродействия сетей

Аспирант представил алгоритм теории графов, позволяющий добиться предельного быстродействия сетей
Новое понимание базовой концепции теории графов, называемой вершинной связностью, может привести к созданию коммуникационных протоколов, наиболее полно использующих пропускную способность информационных сетей.

 Связность является фундаментальным понятием теории графов и может быть двух типов: вершинная и реберная. Она определяет, как много вершин или ребер должно быть удалено из графа, чтобы нарушить его связность. Применительно к коммуникационной сети вершины соответствуют ее узлам (компьютерам), а ребра — соединениям между двумя из них. Таким образом, чем меньше значение реберной или вершинной связности для данной сети, тем легче ее разъединить или разрушить. Вопросы реберной связности рассматривались во многих математических исследованиях, но вершинная связность до сих пор оставалась сравнительно малоизученной.

Однако, в январе на симпозиуме ACM-SIAM по дискретным алгоритмам в Портленде (штат Орегон) аспирант лаборатории CSAIL (Computer Science and Artificial Intelligence Laboratory) Массачусетского технологического института Мосен Гаффари (Mohsen Ghaffari) представит новую работу, посвященную проблемам вершинной связности. «Это может в конечном итоге помочь нам понять, как строить более надежные и быстрые сети, — комментирует Гаффари, разработавший свою методику совместно с коллегами из университета Технион (Израиль) и университета Фрайбурга (Германия). — Новая техника позволит анализировать сохранит ли сеть целостность, если ее узлы случайным образом выходят из строя с определенной вероятностью».

В 60-е годы прошлого века математики Уильям Тутте (William Tutte) и Криспин Нэш-Уильямс (Crispin Nash-Williams) независимо разработали теории о структурах, названных реберно-непересекающиеся остовные деревья (edge-disjoint spanning trees). Это субграфы, в которых все узлы соединяются наименьшим количеством ребер. Совокупность остовных деревьев в графе называется реберно-непересекающейся если они не имеют общих ребер. Если сеть включает, например, три таких непересекающихся остова, информация может распространяться по ним параллельно, а пропускная способность возрастет втрое по отношению к графу, содержащему всего одно остовное дерево. Полученные Тутте и Нэш-Уильямсом результаты показали, что для каждого графа количество остовных деревьев почти достигает величины его реберной связности.

Теперь, в MIT создана аналогичная теория для вершинной связности. Ее авторы разделили граф на связные доминирующие множества. Так называют группу узлов, внутри которой все вершины связаны между собой, а любой другой узел графа соседствует с каким-либо из узлов группы. Аналогично выводам Тутте и Нэша-Уильямса для реберной связности, Гаффари установил, что каждый граф содержит почти столько же вершинно-непересекающихся связанных доминирующих множеств, сколько в нем имеется связанных вершин. Разработанный исследовательским коллективом алгоритм позволяет осторожно разбить сеть на множество связанных доминирующих множеств. Каждая из этих подгрупп будет транслировать свой набор сообщений, причем все они будут работать параллельно, обеспечивая наивысшую возможную пропускную способность.

Источник: ko.com.ua

acm-siam вершинная связность дискретные алгоритмы информационные сети коммуникационный протокол мосен гаффари пропускная способность теория графов

Назад

Социальные сети

Комментарии

Авторизуйтесь, чтобы оставить комментарий