Создание нейронной сети для решения задач маршрутизации в компьютерных сетях.

Description

В соответствии с исследовательским статусом планирования трафика на уровне управления программно-конфигурируемой сетью (SDN) мы обнаруживаем текущие общие проблемы, включая один путь, легкую перегрузку, требования к качеству обслуживания (QoS) и высокую задержку. Чтобы решить эти четыре проблемы, мы разрабатываем и реализуем ориентированный на QoS алгоритм планирования глобального многопутевого трафика для SDN, называемый QOGMP. Во-первых, мы предлагаем алгоритм расчета веса звена, основанный на идее тяговых звеньев и глубокого обучения с подкреплением, и проводим экспериментальные проверки, связанные с тяговыми звеньями. Алгоритм учитывает требования QoS и устраняет проблемы легкой перегрузки и высокой задержки. Затем мы предлагаем алгоритм планирования трафика, основанный на весе канала и многопутевой схеме, который также учитывает требования QoS и решает проблему единственного пути. Окончательно, мы объединили алгоритм расчета веса канала и алгоритм планирования трафика для реализации QOGMP и провели сравнительные эксперименты во встроенной среде моделирования. Экспериментальные результаты показывают, что QOGMP лучше двух алгоритмов сравнения с точки зрения задержки и скорости повторного планирования.

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

С непрерывным увеличением количества и типов устройств, подключенных к сети, перед лицом быстро меняющейся бизнес-среды Интернета недостатки традиционной сети постепенно становятся очевидными . В новой ситуации быстрого развития сети и непрерывного появления сетевых приложений планирование трафика на основе традиционной сети имеет ограничения: (1) Это ставит под сомнение эффективность планирования трафика. Развитие облачных вычислений сделало спрос на крупномасштабные центры обработки данных все более и более очевидным. В процессе планирования сетевого трафика сетевые ресурсы должны использоваться более эффективно для снижения затрат и повышения общей производительности сети . Однако традиционная технология планирования сетевого трафика имеет такие проблемы, как низкая производительность и высокие накладные расходы при работе с крупномасштабными сетями. (2) Сеть склонна к перегрузке. При традиционном планировании сетевого трафика можно использовать только локальную информацию. Сетевой узел вычисляет путь к узлу назначения на основе самого себя. У него нет глобального представления сети, поэтому сложно выполнить хорошее планирование трафика , из-за чего вероятность перегрузки и других проблем в сети продолжает расти. (3) Планирование трафика не является гибким. Перед лицом быстрых изменений в сети и пользовательского спроса он очень слаб. После планирования трафика в соответствии с требованиями сетевых приложений, если спрос изменится, необходимо пересмотреть конфигурацию соответствующего сетевого оборудования (например, маршрутизаторов, коммутаторов и брандмауэров) в традиционной сети , чтобы перепланировать трафик, который это очень утомительный процесс.

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

Концепция проектирования SDN заключается в разделении уровня управления и уровня данных сети при реализации программируемого управления, которое может обеспечить возможности централизованного управления и динамического обслуживания для распределенных сетей , тем самым эффективно устраняя недостатки традиционной IP-сети в обслуживании. , расширение и экспериментальные инновации. Типичная архитектура SDN разделена на три уровня . Верхний уровень — это прикладной уровень, включающий различные сервисы и приложения. Средний уровень — это уровень управления, который в основном отвечает за обработку размещения ресурсов данных и поддержание такой информации, как топология и состояние сети. Основной частью уровня управления является логически централизованный и программируемый контроллер, который может обрабатывать информацию о глобальной сети, что удобно для операторов и научных исследователей для управления и настройки сети и развертывания новых протоколов. Нижний уровень — это уровень данных, который отвечает за обработку, пересылку и сбор данных о состоянии на основе таблицы потоков. Основная часть уровня данных — это множество простых коммутаторов (в отличие от традиционных двухуровневых коммутаторов, конкретно относится к оборудованию, используемому для пересылки данных). Эти коммутаторы обеспечивают только простые функции пересылки данных и могут быстро обрабатывать согласованные пакеты данных для удовлетворения растущего спроса на трафик. Открытый унифицированный интерфейс (например, OpenFlow ) используется для взаимодействия между уровнем управления и уровнем данных. Контроллер выдает коммутатору унифицированные стандартные правила через стандартный интерфейс, а коммутатору остается только выполнить соответствующие действия в соответствии со стандартными правилами.

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

Статус исследования

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

(1)
Единый путь. В литературе для решения проблемы однопутного распространения используются многолучевые передачи. Например, в литературе предложена схема равноценной многопутевой передачи (ECMP), которая в настоящее время широко используется. Однако у этого типа решения есть две основные проблемы: первая заключается в том, что схема многоканальной передачи, реализованная в конкретных условиях, не обладает универсальностью в среде SDN; во-вторых, планирование трафика может использовать только локальную информацию, что может вызвать проблемы с перегрузкой.

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

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

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

Содержание исследования
Основываясь на вышеуказанном статусе исследования, принимая во внимание четыре существующие проблемы в исследовании планирования трафика на уровне управления SDN, мы рассматриваем следующие решения: (1) Использование метода многопутевого планирования схемы ECMP для решения проблемы с одним путем. (2) Использование глобальной информации, предоставляемой централизованным контроллером SDN, для решения проблемы перегрузки. (3) Расчет правил переадресации трафика путем интеграции нескольких параметров канала (потеря пакетов, задержка, пропускная способность канала) и размера бизнес-трафика для обеспечения гарантии качества обслуживания. (4) Использование алгоритмов глубокого обучения с подкреплением для решения проблемы высокой задержки. Задача расчета пути пересылки подходит для глубокого обучения с подкреплением, а алгоритмы глубокого обучения с подкреплением могут преодолеть недостатки обучения с подкреплением и глубокого обучения.

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

Основное содержание исследования показано на рис. 1 .. Структура статьи выглядит следующим образом: (1) Во втором разделе мы предлагаем алгоритм расчета веса звена, основанный на идее тягового звена и глубокого обучения с подкреплением, и проводим соответствующие эксперименты для проверки эффективности тягового звена. Этот алгоритм обеспечивает гарантию QoS и устраняет проблемы легкой перегрузки и высокой задержки. (2) В третьем разделе мы предлагаем алгоритм планирования трафика, основанный на весе канала и многопутевой схеме, который также учитывает требования QoS и решает проблему единственного пути. (3) В четвертом разделе мы объединяем алгоритмы, предложенные во втором и третьем разделах, для реализации ориентированного на качество обслуживания глобального алгоритма планирования многопутевого трафика для SDN, или сокращенно QOGMP. Мы проводим сравнительные эксперименты в построенной тестовой среде моделирования.

Алгоритм расчета веса ссылки
Мы разрабатываем алгоритм расчета веса ссылки, основанный на идее тяговой связи и глубокого обучения с подкреплением.

Мы используем алгоритмы глубокого обучения с подкреплением для расчета весов ссылок. Агент системы обучения с подкреплением задается как нейронная сеть (сеть генерации стратегий), а его взаимодействие с окружающей средой моделируется как марковский процесс. Марковский процесс представлен четырьмя кортежами , где вероятность P по умолчанию равна 1, состояние среды является текущим просмотр трафика, действие — это значение веса ссылки, а вознаграждение — это стратегическая ценность обратной связи, предоставляемая средой для нейронной сети. Постоянно пробуя действия, получаетсяЕ= < Х, А , П, Р >x\in X a\in A r\in R \pi a=\pi (x)х е Ха ∈ Аг е Rπа = π( х ) может быть известно в состоянии x . Качество стратегии можно измерить с помощью функции ценности.

Сеть генерации стратегии реализована нейронной сетью , и ее параметр равен . Сеть стратегических ценностей реализуется нейронной сетью , и ее параметр равен .а = π( х | мк )мюВопрос (Икст,ат| θ)θ

Ценностная функция стратегии выражается в виде уравнения. .

Вопрос (Икст,ат) =рт+ γВопрос (Икст + 1,ат + 1) .
(1)
Функция вознаграждения стратегии выражается как Eq. .

утзнак равнорт+ γВопрос (Икст, п(Икст + 1) | θ ) .
(2)
Параметры сети создания ценности стратегии и сети генерации стратегии необходимо постоянно корректировать в зависимости от ошибки ценности и вознаграждения.

Обновление параметра сети стратегической ценности соответствует уравнению. .

▽θ= Е[ ( Вопрос (Икст,ат| θ)-ут)] .
(3)
Обновление параметров сети генерации стратегии осуществляется в соответствии с уравнением.

▽мю≈ Е[▽θQ ( х , π( Икс | μ ) | θ ) ]= Е[▽аQ ( Икс , а | θ )▽мюπ( Икс | μ ) ] .
(4)
Вход сети генерации стратегии — просмотр трафика и вознаграждение, а выход — значение веса ссылки, которое нам нужно. Представление трафика представляет собой сводку информации о ссылке, собранной и рассчитанной уровнем данных, включая такую ​​информацию, как узлы, ссылки и стоимость каждой ссылки. Поскольку разные требования QoS имеют разные требования к потере и задержке пакетов, мы выражаем стоимость канала как Eq. .

c о s т знак равно α ⋅ п а c k е т л о s s + β⋅ де л а й.
(5)
В уравнении , и — это коэффициенты, установленные в соответствии с потребностями пользователя ( ). В следующих экспериментах и установлены равными 0,5.αβα + β= 1αβ

Алгоритм расчета веса звена, основанный на тяговом звене и глубоком обучении с подкреплением, показан в Алгоритме 1.

Предполагая, что количество сетевых узлов равно n , максимальное количество необязательных ссылок увеличивается экспоненциально, как показано в уравнении.

С0п — 2+С1п — 2+ ⋯ +Сп — 2п — 2знак равно2п — 2.
(6)
Хотя алгоритмы глубокого обучения с подкреплением обладают высокой вычислительной мощностью, перед лицом такого огромного объема данных нам все же необходимо подумать об уменьшении количества необязательных ссылок. Мы принимаем идею тягового звена, чтобы облегчить эту проблему. Теория управления тягой указывает, что для управления крупномасштабными сетями необходимо применять управляющие сигналы только к некоторым узлам и реализовать распространение управляющих сигналов через отношения связи между узлами и, наконец, реализовать координацию всей сети. , чтобы достичь цели управления. Например, если имеется 100 исходных ссылок, первоначальный метод заключается в обновлении веса 100 ссылок и, наконец, получении схемы пути L. Теперь мы извлекаем 20 тяговых ссылок из исходных ссылок и обновляем веса этих 20 ссылок. . Согласно теории контроля тяги, с большой вероятностью конечной схемой пути по-прежнему является L.

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

Принимая в качестве входных данных граф ссылок, собранный уровнем данных, алгоритм извлечения тяговой связи показан в Алгоритме 2.

Мы используем график тягового звена, выдаваемый алгоритмом 2, в качестве входных данных алгоритма 1.

Алгоритм планирования трафика

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

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

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

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

Когда число каналов равно 3, компромисс производительности рассчитывается для различных схем отображения каналов и скоростей передачи. Число отображаемых ссылок равно n, то есть первые n ссылок выбираются для расчета снижения производительности.

можно сделать вывод  , что количество отображаемых ссылок с лучшим снижением производительности равно 2, когда количество ссылок равно 3.

Описанный выше экспериментальный процесс представляет собой вычисление от исходного количества ссылок до количества сопоставленных ссылок с наилучшей производительностью. Мы выполняем аналогичные расчеты и записи для разного количества ссылок и суммируем количество сопоставленных ссылок с наилучшей производительностью.

можно получить , что количество сопоставленных ссылок с наилучшей компрометацией производительности равно , когда количество сопоставленных ссылок равно n . Поэтому мы берем пути для распределения трафика.[н−−√][n][н−−√][n]

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

Мы обновляем вес ссылки в соответствии с выходными данными Алгоритма 1. Если вес не обновляется, значение по умолчанию равно 1. После вычисления взвешенных кратчайших путей итеративно с использованием алгоритма Дейкстры (выполнить алгоритм Дейкстры чтобы найти первый кратчайший путь от исходной точки до точки назначения, удалите первый и снова выполните алгоритм, чтобы найти второй кратчайший путь, и повторяйте до тех пор, пока пути), мы выполняем алгоритм 3, чтобы сгенерировать схему планирования трафика.[н−−√][n][н−−√]

Реализация моделирования и эксперимент

Реализация моделирования

Pycharm может не только запускать алгоритмы Python, но и создавать графические интерфейсы. Мы используем редактор pycharm-community-2019.1.1 для реализации алгоритма и создания среды моделирования.

Мы объединяем алгоритмы из второго и третьего разделов для реализации полного алгоритма планирования потоков QOGMP, который реализуется в следующем порядке: Алгоритм 2, Алгоритм 1 и Алгоритм 3. Мы выполняем упрощенное моделирование сетевой системы SDN.

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

В порядке выполнения конкретные идеи функционального проектирования следующие: (1) Функция сбора данных уровня данных: уровень данных собирает сетевую информацию, включая коммутатор V , канал E и параметры канала (стоимость C , пропускная способность канала W ) . (2) Функция контроллера для получения информации от уровня данных: контроллер получает представление о трафике G ( V ,  E ,  C ,  W) возвращается с уровня данных. (3) Функция контроллера для расчета схемы планирования потока: мы встраиваем алгоритм планирования трафика в контроллер как основной алгоритм контроллера. Мы принимаем представления трафика G 1 ( V ,  E ,  C ), G 2 ( V ,  E ,  W ) и требования пользователя (включая бизнес-поток и устойчивость к задержкам) в качестве входных данных. После выполнения основного алгоритма выводится схема планирования трафика. (4) Функция переадресации потока уровня данных: Уровень данных получает схему, сгенерированную контроллером, и перенаправляет поток в соответствии с ней (этапная задача — вычислить задержку передачи).

Проверочный эксперимент тягового звена

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