Способ, устройство и система для совместной оптимизации

Способ, устройство и система для совместной оптимизации

Иллюстрации

Показать все

Реферат

Область техники

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

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

Задачей ISP (Internet Service Provider, поставщик (провайдер) услуг Internet), в целом, является обеспечение доступа к сети Интернет и требует решения задачи с регулированием трафика (ТЕ, Traffic Engineering), то есть определения оптимального маршрута для потока данных для минимизации перегрузки сети. Задачей СР (Content Provider, поставщик онлайновой информации) является поставка необходимой информации пользователю, и требует решения задачи выбора сервера (SS, Server Selection), то есть указание оптимального сервера для разных пользователей для минимизации сквозной задержки. Когда ISP и СР выполняют, в соответствующем порядке, ТЕ и SS, это не является оптимальным состоянием с точки зрения всей сети.

Для получения оптимальной производительности всей сети, на данный момент начинают пытаться выполнять совместную оптимизацию (Joint Optimization) с использованием решения Нэша (NBS, Nash Bargain Solution) и выпуклой оптимизации из теории игр для реализации кооперативной игры для заданных ТЕ и SS, которые являются двумя задачами оптимизации, так чтобы достичь общего оптимального баланса.

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

Сущность изобретения

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

Способ совместной оптимизации включает в себя:

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

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

получение оптимизированной входной пропускной способности для каждого внешнего порта подсети в соответствии с параметром оптимальной маршрутизации и параметром выбора сервера; и

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

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

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

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

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

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

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

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

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

В одном из вариантов осуществления настоящего изобретения предложена система для совместной оптимизации, включающая в себя:

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

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

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

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

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

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

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

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

на фиг.4 показано двухуровневое разбиение математической модели совместной оптимизации;

на фиг.5 показан вариант осуществления процесса выполнения совместной оптимизации для всей сети; и

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

Подробное описание вариантов осуществления

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

Ниже приведены примеры, иллюстрирующие сеть связи, применяемую в настоящем изобретении.

На фиг.1 показана сеть для выполнения совместной оптимизации, разбитая на два уровня, где первый уровень является уровнем доступа. BAS (Broadband Access Server, Широковещательный сервер доступа) взят в качестве структурного элемента для разделения сети, то есть BAS, коммутатор и DSLAM (Digital Subscriber Line Access Multiplexer, Концентратор цифровой абонентской линии доступа), соединенные с BAS, составляют подсеть, и BAS, граничный маршрутизатор (BR, Border Router) и основной маршрутизатор (CR, Core Router), соединенные вышеописанным способом, составляют подсети верхнего уровня. На уровне доступа, использование BAS в качестве структурного элемента разделения подсети является способом разделения подсети, а также граничный маршрутизатор или другое устройство может быть использовано как структурный элемент для разделения подсети.

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

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

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

Модуль сбора параметров отвечает за сбор информации о состоянии сети, информации о сервере, информации о требованиях пользователя и оптимизированной выходной пропускной способности, полученной от соседней подсети, и передает полученную входную информацию на модуль вычислений. Информация о состоянии сети включает в себя пропускную способность линии связи, качество обслуживания (QoS) для линии связи и стоимость передачи по линии связи. Информация о требованиях пользователя включает в себя набор пользователей и требования пользователя к содержанию. Информация о сервере включает в себя набор серверов и пропускную способность сервера. Набор серверов включает в себя сервер в подсети и виртуальный сервер на входе соседней сети. Оптимизированная выходная пропускная способность, выводимая соседней подсетью, является выходной пропускной способностью, которая может быть получена после выполнения вычисления совместной оптимизации в соседней подсети, и данная пропускная способность служит как пропускная способность виртуального сервера на входе соседней подсети.

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

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

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

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

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

В данной подсети, модель алгоритма совместной оптимизации основана на использовании технологии выпуклой оптимизации и NBS (Nash Bargaining Solution, решение Неша) из теории игр, то есть задачу ограниченной совместной оптимизации устанавливают, когда учитывают ограничивающие условия, такие как информация о линии связи, информация о сервере и пропускной способности и информация о требованиях пользователя. Задачу оптимизации решают для получения набора оптимальных значений, и набор оптимальных значений отражает политику изменения оптимального маршрута ТЕ и политику выбора оптимального сервера SS. В соответствии с данным набором оптимальных значений, может быть вычислено требование пользователя к пропускной способности сервера, и требование также включает в себя требование к пропускной способности на сервере вне подсети, то есть требование к пропускной способности виртуального сервера на устройстве на входе. Наименьшее из значения, полученного вычитанием фонового трафика из требуемой пропускной способности, и значения, полученного вычитанием фонового трафика из максимальной входной пропускной способности данного порта подсети, берут в качестве оптимизированной входной пропускной способности данного порта подсети. В соответствии с данным набором оптимальных значений, может быть дополнительно вычислена оставшаяся пропускная способность, которую сервер может обеспечить во внешний мир через порт подсети. Наименьшее значение из значения, полученного вычитанием фонового трафика из пропускной способности и значения, полученного вычитанием фонового трафика из максимальной выходной пропускной способности данного порта подсети, берут в качестве оптимизированной выходной пропускной способности данного порта подсети.

На фиг.4 показан вариант осуществления решения совместной оптимизации. После первого уровня разбиения первоначальной задачи совместной оптимизации, две подзадачи, SS-NBS и TE-NBS, дополнительно разбивают на втором уровне с точки зрения линии связи, сервера и конечной точки фонового трафика, для разбиения задач на меньшие решаемые подзадачи, что, таким образом, сокращает время выполнения алгоритма.

Принцип разбиения является следующим.

Сначала, на первом уровне, математическую модель совместной оптимизации сети разбивают в соответствии со способом парного разбиения, для разбиения на две подзадачи SS-NBS и TE-NBS, а также основную задачу Dual_TE-SS, и основная задача Dual_TE-SS управляет двумя подзадачами SS-NBS и TE-NBS через переменные λ_l, µ_l, и ν_l цены, которые введены способом разбиения. Поскольку две подзадачи SS-NBS и TE-NBS по-прежнему являются сложными задачами оптимизации, необходимо выполнить дополнительное разбиение. В данном случае, взяв линию 1 связи и сервер s в качестве структурных элементов, на втором уровне подзадачу SS-NBL разбивают на две подзадачи SS-NBL-L и SS-NBL-S, а также основную задачу DualSS-NBS, и основная задача DualSS-NBS управляет подзадачами SS-NBL-L и SS-NBL-S через переменные ρ_l, γ_s, и η_t цены, введенные на втором уровне разбиения. Поскольку две подзадачи SS-NBL-L и SS-NBL-S уже являются наименьшими решаемыми подзадачами, дополнительное разбиение двух подзадач не является необходимым. В противном случае, аналогичный способ разбиения по-прежнему нуждается в адаптации для дополнительного разбиения до получения наименьшей решаемой подзадачи. Аналогично, взяв линию 1 связи и конечную точку j фонового трафика в качестве структурных элементов, на втором уровне подзадачу TE-NBS разбивают на две подзадачи TE-NBS-L и TE-NBS-J, а также основную задачу DualTE-NBS, и основная задача DualTE-NBS управляет подзадачами TE-NBS-L и TE-NBS-J через переменные ξ_l и τ_ij цены, введенные на втором уровне разбиения. Поскольку две подзадачи TE-NBL-L и TE-NBL-J уже являются наименьшими решаемыми подзадачами, дополнительное разбиение двух подзадач не является необходимым. В противном случае, аналогичный способ разбиения по-прежнему нуждается в адаптации для дополнительного разбиения до получения наименьшей решаемой подзадачи.

Вышеописанный процесс двухуровнего разбиения будет дополнительно подробно описан ниже.

1: Первоначальная задача совместной оптимизации

При использовании технологии выпуклой оптимизации и NBS в теории игр, математическую модель задачи совместной оптимизации в подсети устанавливают следующей:

максимизировать log ( T E 0 − ∑ l g l ( f l b g + f ¯ l c p ) ) + log ( S S 0 − ∑ l h 1 ( f l c p + f ¯ l b g ) )

при условии, что f l c p = ∑ ( s , t ) x l s t ,  f l bg = ∑ ( i , j )   ∉   S × T x i j ⋅ r l i j ,   ∀ l

f ¯ l c p = f l c p ,   f ¯ l b g = f l b g ,  f l cp + f l b g ≤ C l ,   ∀ l

∑ l : l ∈ I n ( ν ) r l i j − ∑ l : l ∈ O u t ( ν ) r l i j = I ν = j , ∀ ( i , j ) ∉ S × T , ∀ ν ∈ V \ { i }

∑ s ∈ S ( ∑ l : l ∈ I n ( ν ) x l s t − ∑ l : l ∈ O u t ( ν ) x l s t ) = M t ⋅ I ν = t , ∀ ν ∉ S , ∀ t ∈ T

0 ≤ ∑ t ∈ T ( ∑ l : l ∈ O u t ( ν ) x l s t − ∑ l : l ∈ I n ( ν ) x l s t ) ≤ B s ⋅ I ν = s , ∀ ν ∉ T , ∀ s ∈ S

переменные x l s t ≥ 0 ; 0 ≤ r l i j ≤ 1 , ∀ ( i , j ) ∉ S × T ; f ¯ l c p ; f ¯ l b g                    ( 1 ) .

В данной формуле (ТЕ₀, SS₀) представляют текущее состояние, то есть оптимальные значения, полученные, когда ТЕ и SS оптимизированы независимо; g_l(·) и h_l(·) являются функциями совместной оптимизации, полученными ТЕ и SS соответственно, и обе являются функциями линии 1 связи; f l b g и f ¯ l c p представляют собой, соответственно, фоновый трафик линии 1 связи и трафик первого выбранного СР линии 1 связи с точки зрения ISP; f l c p и f ¯ l b g представляют собой, соответственно, трафик СР линии 1 связи и первый выбранный фоновый трафик линии 1 связи с точки СР; x l s t представляет собой трафик, генерируемый парой (s, t) линии 1 связи; x_ij и r l i j представляют собой, соответственно, фоновый трафик пары (i, j) и пропорцию фонового трафика, генерируемого парой (i, j) линии 1 связи; С_l, М_t, и B_s представляют собой, соответственно, емкость линии 1 связи, требования пользователя t и пропускную способность сервера s; I_ν=j, является индикаторной функцией, что означает, что функция принимает значение 1, когда узел v является узлом j, и функция принимает значение 0, когда узел v является узлом, отличным от узла i и узла j; смысл I_ν=t и I_ν=s аналогичен таковому для I_ν=j; l∈In(ν) и l∈Out(ν) представляют собой, соответственно, линию связи, через которую трафик поступает в узел v, и линию связи, через которую трафик выходит из узла v. Переменные x l s t , r l i j , f ¯ l c p , и f ¯ l b g являются оптимальными переменными, которые должны быть решены в задаче совместной оптимизации.

Выполним преобразование Лагранжа для части вышеприведенной формулы для получения:

L T E − S S ( x l s t , r l i j , f ¯ l c p , f ¯ l b g , λ l , μ l , ν l ) = log ( T E 0 − ∑ l g l ( f l b g + f ¯ l c p ) ) + ∑ l μ l ( f l b g − f ¯ l b g )

+ log ( S S 0 − ∑ l h l ( f l c p + f ¯ l b g ) ) + ∑ l ν l ( f l c p − f ¯ l c p )

+ ∑ l λ l ( C l − f l c p − f l b g )

= log ( T E 0 − ∑ l g l ( f l b g + f ¯ l c p ) ) + ∑ l ( μ l f l b g − ν l f ¯ l c p − λ l f l b g )

+ log ( S S 0 − ∑ l h l ( f l c p + f ¯ l b g ) ) + ∑ l ( ν l f l c p − μ l f ¯ l b g − λ l f l c p )

+ ∑ l λ l C l                                                                                 ( 2 ) .

При использовании способа парного разбиения, вышеприведенная формула может быть разбита на две подзадачи SS-NBS и TE-NBS, и две подзадачи управляются основной задачей Dual_TE-SS(λ_l, µ_l, ν_l).

(1.1): Подзадача S-NBS S S − N B S ( x l s t , f ¯ l b g )

максимизировать log ( S S 0 − ∑ l h l ( f l c p + f ¯ l b g ) ) + ∑ l ( ν l f l c p − μ l f ¯ l b g − λ l f l c p )

при условии, что f l c p = ∑ ( s , t ) x l s t ,