Новый подход к вершинной связности увеличит пропускную способность сетей

Технология способствует пониманию базового концепта теории графа, находя подобие в реберной связности.

Программисты постоянно пребывают в поиске методов еще большего сжатия полос пропускания систем коммуникаций.

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

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

Одна из фундаментальных концепций в пределах теории графа — связность, представленная в двух вариантах: реберная связность и вершинная связность. Фактически это числа, определяющие, сколько линий и узлов связи необходимо удалить из данного графа, чтобы разъединить его. Чем ниже число графа реберной связности или вершинной связности, тем легче разъединить или разрушить его.

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

Сокращение границ реберной связности

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

Однако на симпозиуме ACM-SIAM по дискретным алгоритмам, который состоялся в Портленде, штат Орегон, аспирант Мохсен Джаффари из Массачусетского технологического института презентовал новую технологию для анализа и решения задач в области вершинной связности.

«В итоге это поможет нам понять, как построить более стабильные и быстрые сети», сказал Джаффари.

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

Связующее дерево — это субграф, или граф в графе, в котором все узлы соединены мельчайшим числом ребер. Набор связующих деревьев в пределах графа называется реберно-дизъюнктивным, если эти деревья не имеют общих соединяющих линий.

Если сеть содержит три реберно-дизъюнктивных соединяющих дерева, например, информация способна течь параллельно каждому из деревьев в одно и то же время, это значит, что полоса пропускания в данном случае втрое больше той, что возможна в графе, содержащем лишь одно дерево. Чем выше число реберно-дизъюнктивных соединяющих деревьев, тем больше информационный поток, сообщил Джаффари. «Результаты Татте и Нэш-Уильямса показали, что каждый граф содержит почти столько же много соединяющих деревьев, что и реберная связность», добавил он.

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

Таким образом, информация способна распространяться среди узлов набора и затем передаваться любому узлу в сети.

Подобно результатам Татте и Нэш-Уильямса относительно реберной связности, «каждый граф содержит столько вершино-дизъюнктивных соединенных доминирующих наборов, сколько позволяет его вершинная связность», сказал Джаффари.

«Если вы думаете о применении подобно радиовещательной информации по сети, мы уже можем расчленить сеть на множество групп, каждая из которых будет связана с доминирующим набором», добавил ученый. „Каждая из таких групп будет ответственной за передачу некоторого набора сообщений, и все группы работают параллельно для передачи всех сообщений быстро — так быстро, как только возможно“.

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

«Мы намерены распространять максимально возможные объемы информации за единицу времени, чтобы разрабатывать все более быстрые сети», отметил Джаффари. „И когда граф обладает оптимальной вершинной связностью, он обеспечивает прохождение большего потока информации“.

Применение для оценки надежности

Исследователи также могут использовать новый подход для оценки надежности сети, способности противостоять случайным сбоям. «Новые методы также позволяют нам анализировать, останется ли сеть соединенной, когда ее узлы откажут в произвольном порядке с определенной долей вероятности», сказал Джаффари. „Надежность против случайных реберных сбоев хорошо изучена, а вот о надежности против отказов узлов известно мало“.

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

«Исследовнаие этого понятия, вершинных дизъюнктивных соединенных доминирующих сетей, рассматривается учеными с помощью элегантной комбинации комбинаторных, вероятностных и алгоритмических технологий», заключил он.

25.12.2013