СИСТЕМА И СПОСОБ ЗОНИРОВАНИЯ В ПРОГРАММНО ОПРЕДЕЛЯЕМЫХ СЕТЯХ Российский патент 2018 года по МПК H04L29/06 

Область техники, к которой относится изобретение

Настоящее изобретение относится в целом к подходам зонирования в программно определяемых сетях (SDN) и, в определенных вариантах осуществления, к системе и способу зонирования.

Уровень техники

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

Раскрытие сущности изобретения

Вариант осуществления способа сетевого зонирования для программно определяемой сети (SDN), имеющей несколько сетевых узлов, включает в себя определение числа K зон в соответствии по меньшей мере с одним численным параметром зон. При заданном K несколько сетевых узлов SND разделяют по K зонам. K зонам соответственно приписывают K контроллеров SDN. Каждый из K контроллеров SDN выполнен с возможностью принимать решения по инжинирингу трафика и осуществлять распределенную оптимизацию сети для сетевых узлов, отнесенных к соответствующей зоне.

Вариант осуществления системы связи включает в себя несколько сетевых узлов, несколько контроллеров, контроллер зонирования и главный контроллер. Несколько потоков трафика проходит через несколько сетевых узлов по линиям связи. Задача инжиниринга трафика (ТЕ) задана для потоков трафика, линий связи и сетевых узлов. Контроллер зонирования выполнен с возможностью определять размер подмножества контроллеров зон, выбираемых из нескольких контроллеров. Контроллер зонирования также выполнен с возможностью выбирать подмножество контроллеров зон. Контроллер зонирования также выполнен с возможностью эвристически разделять несколько сетевых узлов на зоны и соответствующим образом приписывать зонам подмножество контроллеров зон. Главный контроллер выполнен с возможностью разбивать задачу ТЕ на подзадачи ТЕ, соответствующие зонам. Подмножество контроллеров зон сконфигурировано соответственно для решения подзадач ТЕ для зон.

Вариант осуществления контроллера зонирования включает в себя контроллер сетевого интерфейса (NIC) и процессор. NIC может соединяться с множеством контроллеров SDN и множеством сетевых узлов через уровень управления. Через множество сетевых узлов проходят потоки трафика, идущие по линиям связи уровня передачи данных. Задача ТЕ определена для множества сетевых узлов, потоков трафика и линий связи. Процессор выполнен с возможностью определять размер подмножества контроллеров зон в соответствии с ожидаемой сложностью ТЕ, размером сети, содержащей множество сетевых узлов, и интенсивностью трафика, содержащего потоки трафика. Процессор также выполнен с возможностью выбирать подмножество контроллеров зон из множества контроллеров SDN в соответствии с топологией контроллеров, сетевой топологией и интенсивностью трафика. Процессор также выполнен с возможностью разделять несколько сетевых узлов на зоны и соответствующим образом приписывать зонам подмножество контроллеров зон, причем в некоторых вариантах осуществления разделение выполняют эвристически.

Краткое описание чертежей

Для более полного понимания настоящего изобретения и его преимуществ теперь будет сделана ссылка на последующее описание, взятое в сочетании с сопровождающими чертежами, на которых:

на фиг. 1 приведена схема одного варианта осуществления зонированной сети;

на фиг. 2 приведен один вариант осуществления графа топологии;

на фиг. 3 приведен один вариант осуществления графа потоков;

на фиг. 4 приведена блок-схема одного варианта осуществления способа зонирования SDN;

на фиг. 5 приведена блок-схема одного варианта осуществления вычислительной системы;

на фиг. 6 приведен другой вариант осуществления графа топологии; на фиг. 7 показаны результаты географического зонирования с использованием подхода эвристической кластеризации;

на фиг. 8 показаны результаты географического зонирования с использованием подхода эвристического разделения;

на фиг. 9 показаны результаты географического зонирования с использованием подхода эвристического распределения задач;

на фиг. 10 показана задача оптимизации ТЕ на основе зон; и

на фиг. 11 показано построение графа потоков.

Осуществление изобретения

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

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

Задача инжиниринга трафика (ТЕ) заключается в том, чтобы определить маршруты для различных потоков трафика и выделить ресурсы, напр., полосу пропускания, на маршрутах в соответствии с требованиями к качеству обслуживания (QoS), так чтобы максимизировать использование сети. ТЕ - сложная задача, которая становится еще сложнее по мере увеличения сети. Особенность SDN заключается в том, что беспроводные сети можно динамически разделить на зоны, чтобы увеличить производительность. Более конкретно, понятно, что разделение беспроводной сети на зоны, т.е. зонирование сети, допускает распределенную оптимизацию задачи ТЕ, причем централизованное управление становится непрактичным или невыполнимым из-за размера или нагрузки на сеть. Зона включает в себя контроллер этой зоны, т.е. контроллер SDN, и соответствующие сетевые элементы, которые включают в себя узлы и линии связи. Также понятно, что беспроводную сеть можно разделить на географические зоны или логические зоны. Географические зоны формируют помимо прочих факторов в соответствии с пространственными соображениями, такими как местоположения пользовательского оборудования (UE), радиоузлов и маршрутизаторов, а также их плотности. Например, можно задать зону с единственным контроллером, который обслуживает все сетевые элементы в радиусе 10 миль. Как альтернатива, логические зоны формируют в соответствии с потоками сетевого трафика. Например, сетевые элементы, связанные с определенным потоком трафика, можно выделить одной логической зоне и одному контроллеру SDN. Географическое зонирование поддается оптимизации ТЕ с использованием модели потока по дуге. Логическое зонирование поддается оптимизации ТЕ с использованием модели потока по пути. Также понятно, что локальными контроллерами зон можно также управлять и осуществлять координацию с помощью главного контроллера зон или главного контроллера. Периодически контроллером зонирования может проводиться повторное зонирование и повторная оптимизация беспроводной сети по мере изменения трафика и перехода пользователей из одной зоны в другую.

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

Накладные расходы уровня управления имеют несколько источников. Эти источники включают в себя инициализацию задачи ТЕ, отчет о состоянии сети, команды обеспечения сети и взаимодействие между контроллерами SDN. Накладные расходы инициализации задачи ТЕ возникают из-за того, что главный контроллер распространяет информацию о потоке трафика, такую как источник, назначение, запрос и т.д., на выбранные контроллеры зон. Состояние сети соответствует состоянию линий связи, соединенных с узлом, и состоянию узла. Линии связи, соединяющие узлы в пределах зоны, являются внутренними линиями связи, а линии связи, соединяющие узлы различных зон, являются граничными линиями связи. Распределение контроллеров SDN по различным зонам может ограничить отчеты о состоянии сети и обеспечение сети данной зоной, но может добавить накладные расходы в координацию различных зон. Неоптимально малое число зон увеличивает нагрузку на отдельные контроллеры SDN, связанную с передачей отчетов о состоянии сети и обеспечением сети, снижая при этом накладные расходы на координацию; а неоптимально большое число зон увеличивает накладные расходы на координацию, снижая при этом нагрузку на отдельные контроллеры SDN, связанную с передачей отчетов о состоянии сети и обеспечением сети. Таким образом, определение числа зон представляет собой задачу поиска равновесия при оптимизации зонирования. Определение числа зон выполняют с помощью контроллера зонирования в соответствии с ожидаемой сложностью ТЕ зоны, которую обычно выражают в единицах времени, размере сети и интенсивности трафика. Компонент ожидаемой сложности ТЕ зоны представляет собой производительность обработки определенного контроллера SDN. Другой компонент ожидаемой сложности ТЕ зоны представляет собой то, насколько быстро должна быть выполнена оптимизация ТЕ. Решение задачи ТЕ получают в пределах периода времени, определяемого по меньшей мере частично интенсивностью трафика и пропускной способностью. Если задача ТЕ не может быть решена достаточно быстро, то узлами, не знающими, как маршрутизировать трафик, будет вызвана перегрузка. Соответственно, если определенный контроллер SDN имеет недостаточную производительность обработки для решения подзадачи ТЕ, то число зон следует увеличить, тем самым дополнительно распределяя нагрузку обработки. Соотношение сложности ТЕ, размера сети и интенсивности трафика можно получить эмпирически, посредством различных системных измерений и базовых точек. Эти измерения и базовые точки могут быть сосредоточены, например, в базе данных управляющей информации (MIB). Как только становится известным требуемое число зон, сеть может быть разделена или разбита на зоны. Зоны, которые иногда называют частями или сегментами, в некоторых вариантах осуществления могут перекрываться, а в других вариантах осуществления - не перекрываться. Разделение выполняют в соответствии с решением задачи разделения или задачи зонирования. Решение задачи разделения может быть найдено с использованием нескольких подходов, некоторые из которых применяют для географических зон, а другие применяют для логических зон.

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

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

Для сети из N узлов, каждый из которых пересылает пакеты уровня передачи данных по линиям связи, соединяющим их с другими узлами. Узлы из подмножества S узлов выполнены с возможностью выступать в качестве контроллеров. Процесс зонирования создает зон, соединяя подмножества узлов уровня передачи данных с узлами контроллеров. Каждый узел уровня передачи данных связан с одним контроллером, который собирает информацию о состоянии сети и обеспечивает свои таблицы маршрутизации. Состояние сети соответствует состоянию линий связи, соединенных с узлом. Контроллеры взаимодействуют друг с другом на уровне управления и участвуют в распределенной оптимизации сети (DNO). Контроллеры работают вместе, чтобы решить задачу DNO, которую можно разбить на множество подзадач, соответствующих каждой зоне, и задачу координации. Распределенная оптимизация может быть выполнена итеративно. На каждой итерации решают подзадачи зон, чтобы получить выделение ресурсов для зон в соответствии с собранной информацией о состоянии сети для зоны и накладными расходами использования граничных линий связи. Выделение ресурсов для граничных линий связи может координироваться главным контроллером SDN, который решает координирующую задачу ТЕ.

Для географического зонирования, где накладные расходы инициализации задачи ТЕ игнорируют, задачу разделения формулируют следующим образом:

так что

где

N - множество узлов в сети,

S - множество контроллеров, S⊆N,

m - главный контроллер, m∈S,

α - число единиц данных на отчет по узлам,

β - число единиц данных на отчет по линиям связи,

γ - число единиц вспомогательных данных на линию связи,

η - число итераций распределенной оптимизации сети,

μ - число единиц данных на обеспечение узла,

ν - число единиц данных на обеспечение линии связи,

τ - коэффициент допустимости дисбаланса зоны,

l_ij - индикатор связности i и j, ∀ i,j ∈ N, и

h_ij - расстояние перехода от i к j, ∀ i,j ∈ N.

Первое условие формулы определяет накладные расходы сбора на зону, . Каждый узел сообщает своему контроллеру информацию о себе и соединенных с ним линиях связи. Передача отчетов происходит в отдельных зонах, и общее число переданных битов подсчитывают в качестве накладных расходов на сбор. Второе условие описывает накладные расходы на координацию на зону, , которые включают в себя общее число битов, которые каждый подчиненный контроллер отправляет и принимает от главного контроллера. Каждый из них применяет число общих линий связи отдельных зон и число итераций координации. Третье условие определяет накладные расходы на обеспечение на зону, , которые подсчитывают аналогично накладным расходам на сбор на зону. Обеспечение выполняют для узлов и линий связи. Каждую линию связи обеспечивают дважды: по одному разу для каждого концевого узла. Четвертое условие представляет собой ограничение балансировки зон, где τ выбирают так, чтобы гарантировать возможность решения задачи. Пятое условие определяет, что решения по связи узел-контроллер должны быть бинарными. Последнее условие означает, что каждый узел связи связан с единственным контроллером. - переменные решения, которые показывают, связано ли i с s.

Как было сформулировано выше, существует несколько эвристических подходов к решению задачи разделения, т.е. зонирования, для географических зон, включая кластеризацию, разделение и распределение задач. Кластеризация связывает каждый узел с ближайшим контроллером, исходя из расстояния перехода или заданной меры расстояния. При разделении сеть разбивают на S соединенных компонентов, а затем назначают контроллеры. При распределении задач применяют философию МинМин. Эти эвристические подходы используют информацию о физической топологии, чтобы сформировать географические зоны. Информация о физической топологии включает в себя топологию уровня управления и топологию уровня передачи данных. Информация о топологии уровня управления включает в себя информацию о контроллерах SDN, маршрутизаторах и UE, соединениях между контроллерами SDN, соединениях между каждой парой сетевой компонент/контроллер SDN, соединениях между каждой парой UE/контроллер SDN и параметрах, связанных с узлами и соединениями. Параметры могут включать в себя плату за присоединение, возможности узла и др. Соединения могут быть реальными или виртуальными. Информация о топологии уровня передачи данных включает в себя информацию о маршрутизаторах и UE, физических линиях связи, которые включают в себя проводные и беспроводные линии, и параметрах, связанных с узлами и линиями связи. Эти параметры могут включать в себя вычислительную нагрузку, вносимую в задачу ТЕ.

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

При разделении сеть можно смоделировать сетевым графом, который разделяют на k связанных компонент сбалансированного размера с использованием отсечения с минимальной суммой весов линий связи. Иногда это называют задачей сбалансированного минимального k-отсечения. Эвристическое разделение основано на поиске сбалансированного минимального k-отсечения сетевого графа, где . Выполняют эту процедуру за два этапа. Сначала необходимо решить задачу сбалансированного минимального k-отсечения на естественным образом взвешенном сетевом графе, где каждый узел i имеет вес , а все линии связи имеют равный вес γ. Решение находят путем привлечения известной эвристики, такой как многоуровневое разделение. Затем каждому сегменту приписывают контроллер с целью минимизации общих затрат на осуществление связи между узлами и контроллерами и между главным и подчиненными контроллерами.

Задачу распределения моделируют в виде задачи распределения задач. Пусть обозначает множество сегментов, полученных на первом этапе разделения. содержит число сегментов, равное числу контроллеров, т.е. . Пусть B(P) обозначает границу сегмента , которая состоит из множества ребер, один конец которых находится в Р, а другой в . Для каждого ребра через обозначим конечную вершину, находящуюся в Р. Задача распределения формулируется следующим образом:

так что

где c_s,P - искомые переменные, которые показывают, отнесен ли контроллер s сегменту Р. Первые три условия определяют накладные расходы на сбор, на координацию и на обеспечение, возникающие при распределении соответствующих контроллеров по сегментам. Четвертое ограничение требует, чтобы решение было бинарным. Пятое ограничение предписывает, чтобы сегментам было приписано в точности по одному контроллеру. Шестое условие требует, чтобы каждый контроллер не мог быть отнесен более чем одному сегменту. Шестое условие допускает, чтобы контроллеров было больше, чем сегментов, обеспечивая гибкость. Контроллеры не обязательно содержатся в назначенной им географической зоне.

При распределении задач задача зонирования структурирована так, что каждый узел представляет собой задачу, назначенную единственному контроллеру, чтобы минимизировать общие затраты. Затраты, С(Z), конфигурирования зонирования Z описывают следующим образом:

Где , и представляют собой затраты на внутризоновый сбор информации, затраты на координацию главный-подчиненный и затраты на обеспечение. Затраты вычисляют в соответствии с исходной формулировкой задачи, приведенной выше. ρ - это затраты на дисбаланс зоны относительно четвертого условия балансировки размера исходной задачи, а ω - весовой коэффициент.

В соответствии с эвристикой распределения, Z_s - зона с назначенным контроллером s, где s∈S. В начальной конфигурации зонирования Z^o каждый контроллер приписан зоне, содержащей только его в качестве единственного члена. Все узлы, не являющиеся контроллерами, относятся к множеству не назначенных узлов U. Границу U, F_s, определяют для зоны Z_s и повторяют для всех зон. Граница F_s включает в себя множество узлов в U, которые имеют линию связи с узлом в Z_s. После каждой итерации узел границы i перемещается из U в граничную зону Z_s. Перемещение выполняют в два этапа. На первом этапе для каждого узла i в каждой границе F_s увеличение затрат Δ(i,s) вычисляют для каждой граничной зоны Z_s при добавлении граничного узла i. Затраты новой конфигурации зонирования Z^t(i,s) вычисляют относительно предыдущей конфигурации зонирования Z^t в соответствии с уравнением Δ(i,s)=C(Z^t(i,s))-C(Z^t). На втором этапе идентифицируют граничный узел, для которого имеет место минимальный рост затрат, и этот узел перемещают. Если множество U пустое, то процедура завершается.

Логическая зона - это объединение возможных маршрутов потоков. Несколько логических зон могут физически перекрываться из-за совместного использования линий связи потоками. Как сформулировано выше, имеется несколько подходов к решению задачи зонирования для логических зон, включая эвристику распределения задач и эвристику разбиения графа. Эвристические алгоритмы используют информацию о потоках данных, чтобы сформировать логические зоны. Информация о потоках данных включает в себя возможные маршруты для потоков и параметры, связанные с каждым потоком. Параметры могут включать в себя вычислительную нагрузку, вносимую задачей ТЕ, связанные виртуальные сети и др. Подход разбиения графа использует граф потоков, который моделирует совместное использование линий связи потоками и решает задачу, используя теорию графов. Для логических зон сеть моделируют как имеющую множество узлов N и множество связей L. Узлы из подмножества узлов S выполнены в виде контроллеров, причем один из них является главным контроллером m. Для задачи ТЕ задано множество потоков трафика F. Предполагается, что маршруты для отдельных потоков известны. Процесс зонирования создает k зон, соединяя подмножества потоков с узлами контроллеров. Каждый поток привязан к единственному контроллеру, который собирает сетевой статус узлов и линий связи вдоль маршрутов. Контроллер информирует источники потоков о решениях ТЕ. Размер логической зоны определяют как общее число возможных путей потоков в зоне. Логические зоны формируют с целью минимизации затрат и балансирования размера зоны.

Конфигурацию зонирования Z для логического зонирования описывают матрицей связи поток-контроллер , где каждый вектор-столбец Z_s определяет зону, контролируемую подчиненным контроллером SDN, s. Для потока ƒ∈F и подчиненного контроллера s∈S α_fs=1, если ƒ связан с s, и 0 в противном случае. По определению, размер зоны Z_s вычисляют как , где - размер потока ƒ, который представляет собой число возможных путей для потока ƒ.

Для заданной конфигурации зонирования Z накладные расходы C(Z) включают в себя затраты на инициализацию C^init(Z), затраты на сбор C^coll(Z), затраты на обеспечение C^prow(Z) и затраты на координацию C^coor(Z), так что: C(Z)=C^init(Z)+C^coll(Z)+C^prow(Z)+C^coor(Z). Затраты на координацию возникают на итерациях оптимизации, в то время как три других вида затрат происходят единожды в начале или конце оптимизации.

Затраты на инициализацию возникают из-за того, что главный контроллер распространяет информацию о потоке, включая источник потока, назначение, запрос и т.д., на подчиненные контроллеры. Информация, распространяемая на заданный подчиненный контроллер, ограничена информацией потоков, связанных с подчиненным контроллером. Затраты на инициализацию имеют вид , где μ - число единиц данных на описание потока, а h_ms - накладные расходы на единицу данных для передачи от главного контроллера на подчиненный контроллер.

Затраты на сбор возникают вследствие того, что каждый подчиненный контроллер собирает информацию о состоянии узлов и линий связи в своей зоне. Затраты на сбор имеют вид , где и соответственно означают, связан ли узел i или линия связи l с подчиненным контроллером s, α - число единиц данных на отчет о состоянии узла, β - число единиц данных на отчет о состоянии линии связи, h_is - накладные расходы на единицу данных для передачи от узла на подчиненный контроллер, а - накладные расходы на единицу данных для линии связи между концевым узлом и подчиненным контроллером.

Затраты на обеспечение возникают вследствие того, что подчиненные контроллеры распространяют решения ТЕ по своим зонам. Затраты на обеспечение имеют вид , где v - число единиц данных в решении ТЕ на путь потока, а - накладные расходы на единицу данных для передачи от подчиненного контроллера на узел-источник потока.

Затраты на координацию возникают вследствие того, что главный контроллер осуществляет сбор и обновление состояний подзадач ТЕ для подчиненных контроллеров. Количество обмениваемых данных пропорционально числу линий связи, используемых зонами совместно. Затраты на координацию имеют вид , где показывает, принадлежит ли зоне Z_s один и только один из ƒ и g, η - число итераций оптимизации ТЕ, γ - число единиц данных на общую линию связи между зонами, h_sm и h_ms - накладные расходы для осуществления связи между подчиненным контроллером и главным контроллером, a n_fg - число линий связи, используемых совместно в ƒ и g, где ƒ, g∈F.

Как было описано выше, задача разделения представляет собой задачу минимизации накладных расходов C(Z) так что

,

,

,

где ∈ - коэффициент допустимости дисбаланса нагрузки.

Для решения задачи разделения с использованием подхода распределения задач для логических зон, при заданном коэффициенте дисбаланса затрат (ICF) ω задачу зонирования упрощают путем удаления условия балансировки размера и добавления штрафного члена p(Z). Новое уравнение затрат и штрафной член имеют вид:

Соответственно, задача зонирования принимает вид:

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

В подходе распределения задач множество потоков, для которых не было принято решения о назначении, обозначено через U. Изначально конфигурация зон Z представляет собой пустое множество, и U=F. На каждой итерации принимают решение о назначении для одного потока, приписывая этот поток ƒ подчиненному контроллеру s. Это представлено установкой . Затем поток удаляют из U.

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

На фиг. 1 приведена схема одного варианта осуществления зонированной сети 100. Зонированная сеть 100 включает в себя четыре контроллера 110-1, …, 110-4, главный контроллер 120, контроллер 150 зонирования и несколько сетевых узлов 140. Несколько сетевых узлов 140 по-разному распределены по зонированной сети 100. Сетевые узлы иногда называют точками доступа, NodeB или усовершенствованными NodeB (eNB). Контроллеры 110-1, …, 110-4 и главный контроллер 120 также представляют собой сетевые узлы с дополнительными возможностями и имеющие такую конфигурацию, чтобы выступать в качестве контроллеров. В общем, любой сетевой узел может реализовывать контроллер. Контроллеры 110-1, …, 110-4 иногда называют контроллерами SDN, контроллерами зоны или подчиненными контроллерами. Главный контроллер 120 также иногда называют контроллером SDN.

Контроллер 150 зонирования разделяет зонированную сеть 100 на четыре зоны 130-1, …, 130-4. Каждой из четырех зон приписан один из контроллеров 110-1, …, 110-4. Зоне 130-1 приписан контроллер 110-1, который обслуживает в ней три сетевых узла. Зоне 130-2 приписан контроллер 110-2, который обслуживает в ней четыре сетевых узла. Зоне 130-3 приписан контроллер 110-3, который обслуживает в ней четыре сетевых узла. Зоне 130-4 приписан контроллер 110-4, который обслуживает в ней три сетевых узла. Главный контроллер 120 координирует оптимизацию ТЕ среди контролеров 110-1, …, 110-4. Главный контроллер 120 и контроллер 150 зонирования представляют собой отдельные логические сетевые элементы. Главный контроллер 120 и контроллер 150 зонирования могут быть реализованы в одной вычислительной системе или в отдельных вычислительных системах.

На фиг. 2 приведен один вариант осуществления графа 200 топологии. Граф 200 топологии включает в себя сетевые узлы 200, десять из которых являются контроллерами 210. Сетевые узлы 220 представлены белыми кружками на графе 200 топологии, в то время как контроллеры 210 представлены черными кружками. Любой из контроллеров 210 также может быть назначен главным контроллером. Сетевые узлы 220 соединены ребрами 230, представляющими линии связи или переходы.

На фиг. 3 приведен один вариант осуществления графа 300 потоков. Граф 300 потоков включает в себя потоки 310 трафика, представленные белыми прямоугольниками, гипер-ребра 320, представленные серыми кружками, и линии 330. Потоки 310 трафика имеют соответствующие веса. Вес потока трафика вычисляют как произведение размера потока и числа потоков. Размер потока относится к числу возможных путей для потока. Число потоков относится к числу потоков без группировки, необходимых для реализации потоков между общим источником и общим пунктом назначения в виде одного сгруппированного потока. Например, на графе 300 потоков потоки нижнего ряда слева направо имеют вес 4,0, 5,0, 10,0, 8,0, 9,0 и 1,0. Гипер-ребра 320, иногда называемые просто ребрами, представляют физические линии связи. Линии 330 по-разному соединяют потоки 310 трафика с гипер-ребрами 320, показывая, что определенные потоки трафика совместно используют физические линии связи. Гипер-ребрам 320 также приписаны соответствующие веса, показывающие число путей потоков, проходящих через них.

На фиг. 4 приведена блок-схема одного варианта осуществления способа зонирования SDN. SDN содержит несколько сетевых узлов и несколько контроллеров SDN. Способ начинают с начального этапа 410. На этапе 420 количества зон определяют, на сколько зон следует разбить сеть. Это число K определяют в соответствии по меньшей мере с одним численным параметром зон. Численные параметры зон включают в себя ожидаемую сложность ТЕ зон, размер сети, интенсивность трафика и информацию о потоках. Более конкретно, при определении рассматривают взаимосвязь между сложностью ТЕ и размером сети, интенсивностью трафика и информацией о потоках. Сложность ТЕ является функцией возможностей обработки контроллера и технических требований, касающихся того, насколько быстро должна быть выполнена оптимизация ТЕ.

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

Продолжая вариант осуществления на фиг. 4, на этапе 430 зонирования множество сетевых узлов разделяют на K зон. В некоторых вариантах осуществления K зон представляют собой географические зоны. В других вариантах осуществления K зон представляют собой логические зоны. Целью разделения является минимизация накладных расходов в процессе оптимизации ТЕ. Накладные расходы при оптимизации ТЕ включают в себя затраты на связь при сборе информации о состоянии узлов и линий связи, затраты на связь при обеспечении и затраты на связь при осуществлении координации контроллеров. Разделение выполняют в соответствии с эвристическим способом. Можно применять несколько эвристических подходов, включая подход кластеризации, разделения и распределения задач для географических зон, распределения задач и разбиения графа для логических зон. Контроллеры приписывают соответствующим зонам на этапе 440 распределения. Способ завершают на конечном этапе 450.

На фиг. 5 показана блок-схема вычислительной системы 500, которую можно использовать для реализации устройств и способов, описанных в этом документе. Отдельные устройства могут использовать все показанные компоненты или только некоторое подмножество компонентов, а уровни интеграции могут меняться от устройства к устройству. Более того, устройство может содержать несколько экземпляров компонента, например, несколько блоков обработки, процессоров, запоминающих устройств, передатчиков, приемников и т.д. Вычислительная система 500 может содержать процессор 502, оснащенный одним или несколькими устройствами ввода/вывода, такими как громкоговоритель, микрофон, мышь, сенсорный экран, панель клавиш, клавиатура, принтер, дисплей и т.п. Процессор может включать в себя центральный процессор (CPU) 514, память 508, запоминающее устройство 504 большой емкости, видеоадаптер 510 и интерфейс 512 ввода/вывода (I/O), подключенные к шине 520.

Шина 520 может представлять собой шину любого из нескольких типов архитектуры шин, включающих в себя шину памяти или контроллер памяти, периферийную шину, видео шину и т.п. CPU 514 может содержать электронный процессор для обработки данных любого типа. Память 508 может содержать постоянную системную память любого типа, например, статическую память с произвольным доступом (SRAM), динамическую память с произвольным доступом (DRAM), синхронную DRAM (SDRAM), постоянную память (ROM), их сочетание и т.п. В одном варианте осуществления память 508 может включать в себя ROM, используемую при загрузке, и DRAM для хранения программ и данных, предназначенную для использования во время выполнения программ.

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

Видеоадаптер 510 и интерфейс 512 I/O обеспечивают интерфейсы для подключения внешних устройство ввода и вывода к процессору 502. Как показано, примеры устройств ввода и вывода включают в себя дисплей 518, подключенный к видеоадаптеру 510, и мышь/клавиатуру/принтер 516, подключенные к интерфейсу 512 I/O. К процессору 502 могут быть подключены другие устройства, и может использоваться большее или меньшее число интерфейсных карт. Например, последовательный интерфейс, такой как универсальная последовательная шина (USB) (не показан) может использоваться для обеспечения интерфейса для принтера.

Процессор 502 также включает в себя один или несколько сетевых интерфейсов 506, которые могут содержать проводные соединения, такие как кабель Ethernet и т.п., и/или беспроводные соединения, для доступа к узлам различных сетей. Сетевые интерфейсы 506 позволяют процессору 502 осуществлять связь с удаленными блоками через сети. Например, сетевые интерфейсы 506 могут обеспечивать беспроводную связь через один или несколько передатчиков/передающих антенн и один или несколько приемников/приемных антенн. В одном варианте осуществления процессор 502 подключен к локальной сети 522 или глобальной сети для обработки данных и осуществления связи с удаленными устройствами, такими как другие процессоры, Интернет, удаленными хранилищами и т.п.

На фиг. 6 приведен другой вариант осуществления графа 600 топологии. Граф 600 топологии включает в себя сетевые узлы 610, восемь из которых обозначены как контроллеры 620. Как на фиг. 2, сетевые узлы 610 представлены белыми кружками, а контроллеры 620 представлены черными кружками. Линии 630 представляют линии связи между различными сетевыми узлами.

На фиг. 7 показаны результаты 700 географического зонирования, полученные с использованием варианта осуществления подхода эвристической кластеризации. Результаты 700 зонирования включают в себя восемь географических зон 710, 720, 730, 740, 750, 760, 770 и 780. Восемь зон охватывают все сетевые узлы на графе топологии на фиг. 6. Контроллеры 620, также на фиг. 6, приписаны восьми географическим зонам. Зоны показаны группами по-разному затененных кружков, представляющих сетевые узлы и смежные с ними линиями связи. Результаты 700 зонирования также включают в себя пунктирные линии между контроллерами 620 и каждым из соответствующих сетевых узлов в соответствующих их зонах.

На фиг. 8 показаны результаты географического зонирования, полученные с использованием варианта осуществления подхода эвристического разделения. Результаты 800 зонирования включают в себя восемь географических зон 810, 820, 830, 840, 850, 860, 870 и 880. Восемь зон охватывают все сетевые узлы на графе топологии на фиг. 6. Контроллеры 620, также на фиг. 6, приписаны восьми географическим зонам. Зоны показаны группами по-разному затененных кружков, представляющих сетевые узлы и смежные с ними линиями связи. Результаты 800 зонирования также включают в себя пунктирные линии между контроллерами 620 и каждым из соответствующих сетевых узлов в соответствующих их зонах.

На фиг. 9 показаны результаты географического зонирования, полученные с использованием варианта осуществления подхода распределения задач. Результаты 900 зонирования включают в себя восемь географических зон 910, 920, 930, 940, 950, 960, 970 и 980. Восемь зон охватывают все сетевые узлы на графе топологии на фиг. 6. Контроллеры 620, также на фиг. 6, приписаны восьми географическим зонам. Зоны показаны группами по-разному затененных кружков, представляющих сетевые узлы и смежные с ними линиями связи. Результаты 900 зонирования также включают в себя пунктирные линии между контроллерами 620 и каждым из соответствующих сетевых узлов в соответствующих их зонах.

На фиг. 10 показана задача оптимизации ТЕ на основе зон для SDN 1000. SND 1000 включает в себя главный контроллер 101, подчиненные контроллеры 1020 и сетевые узлы 1030. В отличие от главного контроллера 101, решающего задачу оптимизации ТЕ, задачу оптимизации ТЕ разбивают на подзадачи, которые могут быть решены подчиненными контроллерами 1020. Каждый из подчиненных контроллеров 1020 приписан зоне 1040. Зоны 1040 образованы так, чтобы минимизировать накладные расходы. Определенные затраты привязаны к определенной зоне. Например, сбор информации об узлах и линиях связи и обеспечение, представленные пунктирными линиями 1050, привязаны к каждой зоне. В то время как дополнительные зоны и подчиненные контроллеры распределяют эти затраты, накладные расходы, связанные с координацией главный-подчиненный, представленные сплошными линиями 1060, увеличиваются при добавлении подчиненных контроллеров.

На фиг. 11 показано построение графа 1100-В потоков в соответствии с топологией 1100-А. Топология 1100-А включает в себя три потока трафика 1110, 1120 и 1130. Потоки трафика по-разному проходят через девять сетевых узлов 1140, которые пронумерованы от 1 до 9. Первый поток 1110 начинается в узле 1 и приходит в узел 8. Поток 1110 трафика имеет два маршрута: 1-2-5-7-8 и 1-3-5-7-8. Второй поток 1120 начинается в узле 4 и также приходит в узел 8. Поток 1120 трафика имеет один маршрут: 4-5-7-8. Третий поток 1130 начинается в узле 6 и приходит в узел 9. Поток 1130 трафика имеет два маршрута: 6-7-8-9 и 6-8-9.

Граф 1100-В потока показывает потоки трафика 1110, 1120 и 1130 белыми прямоугольниками. Каждому из потоков трафика приписан вес, показанный в скобках. Вес представляет собой произведение числа возможных маршрутов, т.е. размера потока, и числа потоков. В этом примере число потоков равно одному для каждого из потоков трафика 1110, 1120 и 1130. Следовательно, соответствующие веса потоков трафика отражают число возможных маршрутов. На графе 1100-В потоков также показано гипер-ребро 1150 и гипер-ребро 1160. Гипер-ребро 1150 представляет физическую линию связи между узлами 7 и 8, которую совместно используют все три потока трафика. Гипер-ребро 1160 представляет физическую линию связи между узлами 5 и 7, которую совместно используют потоки трафика 1110 и 1120. В этом примере никакие другие линии связи не используются совместно, и они не представлены на графе 1100-В потоков. Гипер-ребрам 1150 и 1160 также приписаны веса, которые представляют число возможных маршрутов, проходящих через представленные физические линии связи. Гипер-ребро 1150 имеет вес четыре, соответствующий двум маршрутам для потока 1100 трафика, одному маршруту для потока 1120 трафика и маршруту 6-7-8-9 для потока 1130 трафика. Аналогично, гипер-ребро 1160 имеет вес 3, соответствующий двум маршрутам для потока 1100 трафика и одному маршруту для потока 1120 трафика.

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

Изобретение относится к сетевому зонированию для программно определяемой сети (SDN). Технический результат – обеспечение распределенной оптимизации проблемы регулирования трафика в ситуации, когда централизованное управление становится нецелесообразным, что позволяет более эффективно определять пути маршрутизации для различных потоков трафика и выделять ресурсы, например полосу частот, вдоль этих путей в соответствии с требованиями к качеству обслуживания (QoS), так что степень использования сети оказывается максимальной. Для этого способ включает в себя определение числа K зон в соответствии по меньшей мере с одним количественным параметром зон, содержащим сложность регулирования трафика (ТЕ). При заданном K множество сетевых узлов SND разделяют на K зон. K зонам соответственно приписано K контроллеров SDN. K контроллеров SDN выполнены с возможностью принимать решения по регулированию трафика и осуществлять распределенную оптимизацию сети для соответствующих приписанных сетевых узлов из множества сетевых узлов. 3 н. и 17 з.п. ф-лы, 11 ил.

1. Способ зонирования сети для программно определяемой сети (SDN), имеющей множество сетевых узлов, содержащий этапы, на которых:

определяют число K зон в соответствии по меньшей мере с одним количественным параметром зон, содержащим сложность регулирования трафика (TE);

разделяют упомянутое множество сетевых узлов SDN на K зон; и

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

2. Способ по п. 1, дополнительно содержащий этап, на котором выбирают первую группу из K контроллеров SDN.

3. Способ по п. 2, в котором выбор осуществляют одновременно с соответствующим приписыванием.

4. Способ по п. 2, в котором выбор осуществляют до разделения и до соответствующего приписывания.

5. Способ по п. 4, дополнительно содержащий этап, на котором повторно выбирают вторую группу из K контроллеров SDN одновременно с соответствующим приписыванием для замены первой группы из K контроллеров SDN.

6. Способ по п. 2, в котором на этапе выбора выбирают первую группу из K контроллеров SDN из множества контроллеров-кандидатов SDN в соответствии с соответствующими расстояниями между контроллерами для упомянутого множества контроллеров-кандидатов SDN, при этом на этапе выбора дополнительно максимизируют соответствующие расстояния между контроллерами для первой группы из K контроллеров SDN.

7. Способ по п. 6, в котором соответствующие расстояния между контроллерами содержат число переходов.

8. Способ по п. 6, в котором соответствующие расстояния между контроллерами являются взвешенными.

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

10. Способ по п. 1, в котором на этапе разделения делят SDN на географические зоны в соответствии с эвристическим алгоритмом, причем эвристический алгоритм использует информацию о физической топологии для формирования географических зон.

11. Способ по п. 10, в котором на этапе разделения дополнительно формируют географические зоны в соответствии с эвристическим алгоритмом кластеризации, или эвристическим алгоритмом разделения, или эвристическим алгоритмом распределения задач.

12. Способ по п. 1, в котором на этапе разделения делят SDN на логические зоны в соответствии с эвристическим алгоритмом, причем эвристический алгоритм использует информацию о потоках данных для формирования логических зон.

13. Способ по п. 12, в котором на этапе разделения дополнительно формируют логические зоны в соответствии с эвристическим алгоритмом распределения задач или эвристическим алгоритмом разбиения графа.

14. Способ по п. 1, в котором этап разделения осуществляют до соответствующего приписывания или одновременно с соответствующим приписыванием.

15. Система связи, содержащая:

множество сетевых узлов, между которыми по линиям связи проходят множество потоков трафика и для которых определена задача регулирования трафика (ТЕ);

множество контроллеров, из которых можно выбрать подмножество контроллеров зон;

контроллер зонирования, выполненный с возможностью:

определять размер подмножества контроллеров зон,

выбирать подмножество контроллеров зон,

эвристически разделять множество сетевых узлов на зоны, и

соответственно приписывать подмножество контроллеров зон зонам; и

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

16. Система связи по п. 15, в которой подмножество контроллеров зон выполнено с возможностью предоставлять сетевые ресурсы множеству сетевых узлов в соответствии с соответственными решениями подзадач ТЕ.

17. Система связи по п. 15, в которой главный контроллер дополнительно выполнен с возможностью осуществлять связь с подмножеством контроллеров зон для координации состояния подзадач ТЕ.

18. Контроллер зонирования, содержащий:

контроллер сетевого интерфейса (NIC), соединяемый с множеством контроллеров SDN и множеством сетевых узлов через уровень управления, причем множество сетевых узлов выполнено с возможностью пропускания через себя потоков трафика по линиям связи уровня передачи данных, при этом для множества сетевых узлов, потоков трафика и линий связи может быть задана задача регулирования трафика (ТЕ); и

процессор, выполненный с возможностью:

определять размер подмножества контроллеров зон в соответствии с ожидаемой сложностью TE, размером сети, содержащей множество сетевых узлов, и интенсивностью трафика, содержащего потоки трафика,

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

разделять множество сетевых узлов на зоны, и

соответственно приписывать подмножество контроллеров зон зонам.

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

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