СПОСОБ, УСТРОЙСТВО И СИСТЕМА ДЛЯ СОВМЕСТНОЙ ОПТИМИЗАЦИИ

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

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

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

Задачей 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 в теории игр, математическую модель задачи совместной оптимизации в подсети устанавливают следующей:

максимизировать

при условии, что

, ,

, ,

, ,

переменные ; , ; ; .

В данной формуле (ТЕ₀, SS₀) представляют текущее состояние, то есть оптимальные значения, полученные, когда ТЕ и SS оптимизированы независимо; g_l(·) и h_l(·) являются функциями совместной оптимизации, полученными ТЕ и SS соответственно, и обе являются функциями линии 1 связи; и представляют собой, соответственно, фоновый трафик линии 1 связи и трафик первого выбранного СР линии 1 связи с точки зрения ISP; и представляют собой, соответственно, трафик СР линии 1 связи и первый выбранный фоновый трафик линии 1 связи с точки СР; представляет собой трафик, генерируемый парой (s, t) линии 1 связи; x_ij и представляют собой, соответственно, фоновый трафик пары (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. Переменные , , , и являются оптимальными переменными, которые должны быть решены в задаче совместной оптимизации.

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

.

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

(1.1): Подзадача S-NBS

максимизировать

при условии, что

, ,

, ,

переменные , ;

(1.2): Подзадача TE-NBS

максимизировать

при условии, что

, ,

переменные , ; .

(1.3): Основная подзадача Dual_TE-SS(λ_l, µ_l, ν_l)

Создадим H (λ_l, µ_l, ν_l) в качестве максимального значения целевой функции подзадачи SS-NBS, и G (λ_l, µ_l, ν_l) в качестве максимального значения целевой функции подзадачи TE-NBS, где

Основная задача может быть представлена как:

минимизировать

переменные ; ; .

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

2: Дополнительное разбиение подзадачи SS-NBS

Подзадача SS-NBS в (1.1) может быть дополнительно выражена как:

максимизировать

при условии, что

,

,

,

переменные , ; ,

где T(s) представляет собой набор пользователей, обслуживаемых сервером s, и S(t) представляет набор серверов, обслуживающих некоторого пользователя t. Последнее ограничительное условие означает, что для промежуточного узла v, который не является ни сервером, ни пользователем, трафик, поступающий на узел v, эквивалентен трафику, выходящему из узла v. То есть промежуточный узел v удовлетворяет закону обмена трафиком. Данная формула явно является верной, и, следовательно, не имеет значения, когда было сгенерировано выражение Лагранжа.

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

.

В данном случае, l∈L(s, t) представляет собой линию связи от сервера s до пользователя t.

Подзадача SS-NBS разбита, в соответствии с линией 1 связи и сервером s, на два типа подзадач SS-NBS-L и SS-NBS-S. Данные две подзадачи управляются основной задачей

Dual_SS-NBS(ρ_l, γ_l, η_l).

(2.1): Подзадача SS-NBS-L:

Линия 1 связи

максимизировать

переменные ; .

(2.2): Подзадача SS-NBS-S:

Сервер s

максимизировать

переменные .

(2.3): Основная задача SS-NBS: Dual_SS-NBS(ρ_l, γ_s, η_t)

Создадим L_SS-NBS-L(ρ_l) в качестве максимального значения целевой функции подзадачи SS-NBS-L, и S_SS-NBS-S(ρ_l, γ_s, η_t) в качестве максимального значения целевой функции подзадачи SS-NBS-S, где

;

.

Основная задача может быть представлена как:

минимизировать

переменные ; ;

3: Дополнительное разбиение подзадачи TE-NBS

Подзадача TE-NBS в (1.2) может быть дополнительно выражена как:

максимизировать

при условии, что

,

, ,

переменные , ; .

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

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

.

В данном случае, l∈L(i,j) представляет собой линию связи от I до j.

Подзадача TE-NBS разбита, в соответствии с линией 1 связи и конечной точкой j фонового трафика, на два типа подзадач TE-NBS-L и TE-NBS-J. Данные две подзадачи управляются основной задачей Dual_TE-NBS(ζ_l, τ_ij).

(3.1): Подзадача TE-NBS-L:

Линия 1 связи

максимизировать

переменные ; .

(3.2): Подзадача TE-NBS-J:

Конечная точка j фонового трафика

максимизировать

переменные .

(3.3): Основная задача TE-NBS: Dual_TE-NBS(ζ_l, τ_ij)

Создадим L_TE-NBS-L(ζ_l) в качестве максимального значения целевой функции подзадачи TE-NBS-L, и L_TE-NBS-J(ζ_l, τ_ij) в качестве максимального значения целевой функции подзадачи TE-NBS-J, где

;

.

Основная задача может быть представлена как:

минимизировать

переменные ; .

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

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

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

Весь процесс реализован следующим образом.

Этап 1: Предполагаемая начальная входная пропускная способность установлена для каждой подсети в сети нижнего уровня, модуль сбора параметров собирает информацию о состоянии сети (например, информацию о линии связи), информацию о сервере и пропускной способности и информацию о требованиях пользователя в подсети, и модуль вычислений вычисляет параметр оптимальной маршрутизации и параметр сервера подсети в соответствии со способом разбиения, показанным на фиг.4. Получают оптимизированную выходную пропускную способность, которую может обеспечить сервер, где оптимизированная выходная пропускная способность относится к наименьшей из максимальной выходной пропускной способности порта и максимальной пропускной способности, которую может обеспечить сервер в подсети. Получают оптимизированную входную пропускную способность подсети, где входная пропускная способность является пропускной способностью, которую должен обеспечить сервер вне подсети.

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

Этап 3: Для подсети наивысшего уровня, модуль сбора параметров системы для совместной оптимизации в подсети собирает оптимизированную выходную, пропускную способность, вычисленную соседней подсетью нижнего уровня, и информацию о состоянии сети (например, информацию о линии связи), информацию о сервере и пропускной способности и информацию о пропускной способности подсети. Модуль вычислений вычисляет параметр оптимальной маршрутизации и параметр сервера подсети в соответствии со способом разбиения, показанном на фиг.4. Получают оптимизированную выходную пропускную способность, обеспечиваемую подсетью для сети нижнего уровня, где оптимизированная выходная пропускная способность относится к наименьшей из максимальной выходной пропускной способности порта и максимальной пропускной способности, которую может обеспечить сервер в подсети. Получают оптимизированную входную пропускную способность подсети, где входная пропускная способность является пропускной способностью, которую должен обеспечить сервер вне подсети.

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

На фиг.6 показан вариант осуществления системы для совместной оптимизации. Система для совместной оптимизации включает в себя механизм маршрутизации содержания и вычислительное устройство для совместной оптимизации. В отношении структуры вычислительного устройства для совместной оптимизации, ссылка сделана на фиг.3. Фиг.6 дополнительно включает в себя отношение соединений между системой для совместной оптимизации и модулем прокси, механизмом разрешения имен, адаптером GET/PUT содержания, блоком сбора статистики трафика, блоком сбора статистики запросов, системой для совместной оптимизации одноранговой подсети, механизмом передачи/переадресации и модулем поддержки топологии.

Модуль прокси (Proxy): Является прокси для пользователя и устанавливает мост между терминалом пользователя и системой для совместной оптимизации, а также может быть использован для сбора запросов от пользователя. Модуль прокси может быть размещен на границе сети, например размещен на DSLAM.

Механизм маршрутизации содержания (Content Routing Engine): Определяет, как получить требуемое содержание. Когда механизм маршрутизации содержания обнаруживает, что требуемое содержание не находится в устройстве локального буфера, он использует механизм разрешения имен (Name Resolution Engine) для получения списка узлов, содержащих содержание, и берет список узлов в качестве информации о сервере, и выводит его на модуль сбора параметров. Механизм маршрутизации содержания получает, от модуля вывода вычислительного устройства для совместной оптимизации, политику изменения маршрута и политику выбора сервера, и преобразует их политику изменения маршрута и политику выбора сервера, которые могут быть реализованы и введены в действие, где политику изменения маршрута вводят в механизм передачи/переадресации для выполнения политики маршрутизации на нижнем уровне, и политику выбора сервера вводят в модуль поддержки топологии для выполнения выбора сервера на уровне содержания.

Механизм разрешения имен (Name Resolution Engine): В основном возвращает список подходящих узлов, содержащих содержание, требуемое пользователем.

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

Блок сбора статистики трафика (Traffic Statistics Collector): Собирает информацию о фоновом трафике, информацию о линии связи и т.п., и предоставляет собранную информацию модулю сбора параметров.

Блок сбора статистики запросов (Request Statistics Collector): Собирает требования пользователя и отправляет собранные требования пользователя модулю сбора параметра.

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

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

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

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

Механизм передачи/переадресации: Принимает инструкции от механизма маршрутизации содержания на уровне IP, выполняет передачу трафика и вводит результат в механизм маршрутизации содержания.

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

Интерактивный процесс системы для совместной оптимизации является следующим:

1: Модуль прокси завершает сбор запросов содержания от пользователя.

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

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

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

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

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

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

8. Механизм передачи/переадресации принимает политику изменения маршрута от механизма маршрутизации содержания для изменения маршрутизации нижнего уровня и выполнения политики изменения маршрута уровня IP.

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

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

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

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