ВЫЧИСЛЕНИЕ ДОЛГОСРОЧНЫХ РАСПИСАНИЙ ДЛЯ ПЕРЕДАЧ ДАННЫХ ПО ГЛОБАЛЬНОЙ ВЫЧИСЛИТЕЛЬНОЙ СЕТИ Российский патент 2019 года по МПК H04L12/911 H04W72/00 

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

[0001] Глобальные вычислительные сети (WAN) становятся повсеместными, и относительно большие объемы данных зачастую передаются между вычислительными устройствами в WAN. Чтобы поддерживать передачу больших объемов данных, операторы соответствующих WAN инвестируют значительный объем ресурсов в компьютерные сетевые аппаратные средства, которые обеспечивают передачу данных между вычислительными устройствами в WAN. Следовательно, максимизация использования таких компьютерных сетевых аппаратных средств в WAN требуется с точки зрения эффективности.

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

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

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

[0004] В данном документе описаны различные технологии, связанные с расписанием передач данных в сети, такой как глобальная вычислительная сеть (WAN) на основе множества запросов на передачи данных, причем запросы имеют соответствующие крайние сроки, и причем передачи данных должны завершаться до соответствующих крайних сроков. В примерном варианте осуществления, сеть может содержать множество центров обработки и хранения данных (каждый из которых содержит множество вычислительных устройств), и запрос на передачу данных может представлять собой запрос на то, чтобы передавать данные из вычислительного устройства в первом центре обработки и хранения данных в вычислительное устройство во втором центре обработки и хранения данных. Центр обработки и хранения данных в сети может быть включен в открытое облако или закрытое облако. Открытое облако обеспечивает доступ к ресурсам центра обработки и хранения данных (например, приложениям и устройствам хранения) широкой публике посредством Интернета. Напротив, закрытое облако обеспечивает доступ к ресурсам центра обработки и хранения данных для частной организации, которая управляет центром обработки и хранения данных.

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

[0006] Сеть также включает в себя контроллерное вычислительное устройство, которое выполнено с возможностью диспетчеризации передач данных по сети. Например, контроллерное вычислительное устройство может принимать множество запросов, чтобы передавать данные между соответствующими вычислительными устройствами в сети, при этом каждый запрос может идентифицировать: 1) соответствующее вычислительное устройство-источник (например, из которого должны передаваться данные); 2) соответствующее вычислительное устройство-получатель (например, в которое должны передаваться данные); 3) соответствующий объем данных, который должен передаваться из вычислительного устройства-источника в вычислительное устройство-получатель; и 4) соответствующий крайний срок, при этом передача данных из вычислительного устройства-источника в вычислительное устройство-получатель должна завершаться до крайнего срока. Контроллерное вычислительное устройство может принимать эти запросы в произвольные времена, и запросы могут указывать различные объемы данных и различные крайние сроки. Например, первый запрос на передачу данных может приниматься в первый момент времени и может указывать то, что передача данных является относительно срочной, посредством указания крайнего срока, который находится рядом во времени с первым моментом времени. Второй запрос на передачу данных может приниматься во второй момент времени (причем первый момент времени и второй момент времени находятся рядом) и указывать то, что передача данных не является особенно чувствительной ко времени, посредством указания крайнего срока, который является относительно удаленным от второго момента времени.

[0007] Контроллерное вычислительное устройство принимает такие запросы и вычисляет долгосрочное расписание для передачи данных в сети. Долгосрочное расписание может покрывать множество (потенциально равномерных) единиц времени, причем поток данных через сеть задается в долгосрочном расписании для каждой единицы времени, покрываемой долгосрочным расписанием. Таким образом, долгосрочное расписание содержит детализированное расписание для каждой единицы времени, покрываемой долгосрочным расписанием. В неограничивающем примере, долгосрочное расписание может покрывать двенадцать 5-минутных интервалов, причем единицы времени являются 5-минутными интервалами. Для каждой из этих единиц времени в долгосрочном расписании, долгосрочное расписание может включать в себя соответствующее детализированное расписание. Детализированное расписание может идентифицировать то, какие вычислительные устройства должны выступать в качестве вычислительных устройств-источников для единицы времени детализированного расписания, соответствующие скорости, на которых вычислительные устройства должны выводить данные, соответствующие тракты, по которым данные должны перемещаться между вычислительными устройствами-источниками и вычислительными устройствами-получателями, и т.д. Следовательно, можно удостоверяться, что контроллерное вычислительное устройство вычисляет долгосрочное расписание, чтобы обеспечивать выполнение запрашиваемых передач данных до соответствующих крайних сроков при максимизации использования сетевых ресурсов. С этой целью, в примере, контроллерное вычислительное устройство может определять то, следует утверждать или отклонять запросы на передачу новых принимаемых данных, на основе долгосрочного расписания (например, контроллерное вычислительное устройство может определять то, может или нет запрашиваемая передача данных завершаться до указанного крайнего срока, на основе долгосрочного расписания, ранее принимаемых запросов, в которых передачи данных не завершены, и соответствующих крайних сроков). Контроллерное вычислительное устройство повторно вычисляет долгосрочное расписание во времени, чтобы учитывать новые принимаемые запросы, изменения в сети, удовлетворенные запросы (в которых соответствующие передачи данных завершены) и т.д. В примерном варианте осуществления, контроллерное вычислительное устройство может вычислять долгосрочное расписание посредством выполнения процесса оптимизации. Например, процесс оптимизации может включать в себя выполнение смешанного алгоритма укладки и покрытия.

[0008] Контроллерное вычислительное устройство дополнительно может вычислять краткосрочное расписание на основе долгосрочного расписания. Краткосрочное расписание может покрывать меньше единиц времени, чем долгосрочное расписание. Например, краткосрочное расписание может покрывать одну единицу времени, которая является непосредственно последующей во времени относительно текущей единицы времени (например, 5-минутный интервал). Краткосрочное расписание включает в себя: 1) таблицы маршрутизации для соответствующих устройств сетевой инфраструктуры в сети; и 2) инструкции для вычислительных устройств-источников, которые идентифицируют данные, которые должны выводиться посредством вычислительных устройств-источников, и соответствующие скорости, на которых данные должны выводиться посредством вычислительных устройств-источников. Контроллерное вычислительное устройство вычисляет краткосрочное расписание, чтобы обеспечить выполнение передач данных в соответствии с долгосрочным расписанием. Контроллерное вычислительное устройство передает таблицы маршрутизации и инструкции в краткосрочном расписании в соответствующие устройства сетевой инфраструктуры и вычислительные устройства-источники в сети.

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

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

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

[0011] Фиг. 1 является функциональной блок-схемой примерной системы, которая обеспечивает диспетчеризацию передач данных между вычислительными устройствами в сети.

[0012] Фиг. 2 является примерным долгосрочным расписанием для передач данных в сети.

[0013] Фиг. 3 является примерным краткосрочным расписанием для передач данных в сети.

[0014] Фиг. 4 является функциональной блок-схемой примерного компонента планировщика, который может формировать долгосрочное расписание и краткосрочное расписание для передач данных в WAN.

[0015] Фиг. 5 является примерным сетевым графом.

[0016] Фиг. 6 является примерным графическим пользовательским интерфейсом, который может быть доступным для клиента, чтобы обеспечивать прием запроса на передачу данных по сети.

[0017] Фиг. 7 является блок-схемой последовательности операций способа, иллюстрирующей примерную технологию для диспетчеризации передач данных в сети.

[0018] Фиг. 8 является блок-схемой последовательности операций способа, иллюстрирующей примерную технологию для вычисления долгосрочного расписания для передач данных в сети.

[0019] Фиг. 9 является блок-схемой последовательности операций способа, иллюстрирующей примерную технологию для обеспечения доступности ценовой сетки, соответствующей передаче данных в сети.

[0020] Фиг. 10 является примерной вычислительной системой.

Подробное описание изобретения

[0021] Далее описываются различные технологии, связанные с передачей данных между вычислительными устройствами в сети (такой как глобальная вычислительная сеть (WAN)) со ссылкой на чертежи, на всех из которых аналогичные ссылки с номерами используются для того, чтобы означать аналогичные элементы. В нижеследующем описании, для целей пояснения, многие конкретные детали пояснены для того, чтобы предоставлять полное понимание одного или более аспектов. Тем не менее, может быть очевидным, что такие аспекты могут применяться на практике без этих конкретных деталей. В других случаях, распространенные структуры и устройства показаны в форме блок-схемы, чтобы упрощать описание одного или более аспектов. Дополнительно, следует понимать, что функциональность, которая описывается как выполняемая посредством одного системного компонента, может выполняться посредством нескольких компонентов. Аналогично, например, один компонент может быть выполнен с возможностью осуществлять функциональность, которая описывается как выполняемая посредством нескольких компонентов.

[0022] Кроме того, термин "или" имеет намерение означать включающее "или" вместо исключающего "или". Таким образом, если иное не указано или не является очевидным из контекста, "X использует A или B" имеет намерение означать любую из естественных включающих перестановок. Таким образом, фраза "X использует A или B" удовлетворяется посредством любого из следующих случаев: "X использует A; X использует B; или X использует как A, так и B". Помимо этого, упоминание в единственном числе в настоящей заявке и прилагаемой формуле изобретения, в общем, должно истолковываться как подразумевающее "один или более", если иное не указано или не является очевидным из контекста, что направлено на форму единственного числа.

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

[0024] Со ссылкой теперь на фиг. 1, проиллюстрировано примерное контроллерное вычислительное устройство 100, которое выполнено с возможностью вычислять долгосрочное расписание для передач данных в сети 102. Например, сеть 102 может представлять собой WAN. Хотя контроллерное вычислительное устройство 100 показано как внешнее для сети, следует понимать, что это служит для целей иллюстрации, и что контроллерное вычислительное устройство 100 включено в сеть 102. Дополнительно, хотя контроллерное вычислительное устройство 100 показано и описано как одно вычислительное устройство, контроллерное вычислительное устройство 100 должно охватывать логически централизованную систему управления, при этом функциональность, описанная как выполняемая посредством контроллерного вычислительного устройства 100, может быть распределена по нескольким вычислительным устройствам.

[0025] Сеть 102 включает в себя множество вычислительных устройств 104-110, которые размещаются на краю сети 102. В примерном варианте осуществления, число вычислительных устройств во множестве вычислительного устройства 104-110 может составлять от десяти вычислительных устройств до 3000 вычислительных устройств. В другом примерном варианте осуществления, число вычислительных устройств во множестве вычислительных устройств 104-110 может составлять от десяти вычислительных устройств до 100000 вычислительных устройств. В примерном варианте осуществления, вычислительные устройства 104-110 могут представлять собой серверные вычислительные устройства, размещающиеся в соответствующих серверных стойках. Кроме того, вычислительные устройства 104-110, в примере, могут находиться в соответствующем различном центре обработки и хранения данных, при этом каждый центр обработки и хранения данных содержит соответствующее множество вычислительных устройств, поддерживающих связь между собой. Центр обработки и хранения данных может использоваться для того, чтобы обеспечивать предоставление ресурсов открытого и/или закрытого облака. Открытое облако обеспечивает доступ к ресурсам центра обработки и хранения данных для широкой публики (например, за плату) по Интернету, тогда как закрытое облако обеспечивает доступ к ресурсам центра обработки и хранения данных для организации, которая управляет центром обработки и хранения данных. Сеть 102 дополнительно содержит множество устройств 112-114 сетевой инфраструктуры, которые упрощают передачу данных между вычислительными устройствами 104-110. Например, устройства 112-114 сетевой инфраструктуры могут представлять собой или включать в себя коммутаторы, маршрутизаторы, концентраторы, шлюзы и т.п. В соответствии с примером, число устройств сетевой инфраструктуры во множестве устройств сетевой инфраструктуры может составлять от 10 устройств до 1000 устройств. В другом примере, число устройств сетевой инфраструктуры во множестве устройств сетевой инфраструктуры может составлять от 100 устройств до 10000 устройств.

[0026] В примере, владелец данных, сохраняемых на одном из вычислительных устройств 104-110, предпочтительно может передавать такие данные в другое из вычислительных устройств 104-110. Традиционно, например, когда принимается запрос на то, чтобы передавать данные из первого вычислительного устройства 104 в третье вычислительное устройство 108, диспетчеризация практически не применяется. Вместо этого, первое вычислительное устройство 104 начинает передавать данные на максимально возможной высокой скорости, и данные перемещаются вдоль одного или более трактов через сеть 102 в третье вычислительное устройство 108, потенциально нагружая инфраструктуру сети 102. В частности, устройства 112-114 сетевой инфраструктуры типично конфигурируются с инструкциями, чтобы балансировать загрузку, передаваемую через сетевые линии связи при направлении данных намеченному получателю (в третье вычислительное устройство 108). Этот подход является осуществимым для сетей с избыточным резервированием ресурсов, в которых оператор WAN 102 предоставляет достаточную пропускную способность сети с тем, чтобы удовлетворять максимальной потребности по передаче данных. Тем не менее, это зачастую является неэффективным использованием ресурсов сети 102.

[0027] Контроллерное вычислительное устройство 100, как подробнее описано ниже, вычисляет долгосрочное расписание для передач данных по сети 102, которое может приводить к сглаживанию объема трафика по сети 102 во времени, за счет этого повышая эффективность использования сети 102. С этой целью, контроллерное вычислительное устройство 100, в отличие от традиционных подходов, предполагает крайние сроки передачи (принимаемой в различные моменты времени и имеющей различную длительность) при вычислении долгосрочного расписания (плана) для передач данных в сети 102.

[0028] Если подробнее касательно вычисления долгосрочного расписания, контроллерное вычислительное устройство 100 включает в себя компонент 116 приемного устройства, который может принимать множество запросов на передачу данных. Например, сеть 102 может быть выполнена с возможностью одновременно поддерживать 100000 отдельных потоков трафика (например, передач данных между вычислительными устройствами в вычислительных устройствах 104-110). Запросы на передачу данных, принятые посредством компонента 116 приемного устройства, включают в себя соответствующие идентификационные данные источников данных, которые должны передаваться, соответствующие идентификационные данные намеченных получателей данных, которые должны передаваться, соответствующие объемы данных, которые должны передаваться по WAN 102, и соответствующие крайние сроки. Более конкретно, запрос на передачу данных, принимаемый посредством компонента 116 приемного устройства, включает в себя: 1) идентификационные данные вычислительного устройства-источника, из которого должны передаваться данные; 2) индикатор относительно данных, которые должны передаваться; 3) идентификационные данные вычислительного устройства-получателя, которое должно принимать данные, которые должны передаваться; 4) объем данных, которые должны передаваться из вычислительного устройства-источника в вычислительное устройство-получатель; и 5) крайний срок, при этом объем данных должен передаваться из вычислительного устройства-источника в вычислительное устройство-получатель до крайнего срока. Дополнительно, следует понимать, что запрос может включать в себя несколько потенциальных крайних сроков, причем плата за передачу варьируется в зависимости от крайнего срока. Компонент 116 приемного устройства может принимать запрос на передачу данных из вычислительного устройства-источника, из вычислительного устройства-получателя или из другого вычислительного устройства, управляемого владельцем данных, которые должны передаваться из вычислительного устройства-источника в вычислительное устройство-получатель. Запросы на передачу данных могут приниматься из любого из устройств в вычислительных устройствах 104-110 или могут приниматься из системы или компонента, который идентифицирует сервер(ы), из которого должны передаваться данные. В примере, система или компонент, упомянутая выше, не должна обязательно идентифицировать конкретные исходные и целевые вычислительные устройства в запросе; в силу чего запрос может быть более общим, запрашивая информацию относительно трактов в сети, скоростей передачи и т.д.

[0029] В неограничивающем примере, компонент 116 приемного устройства может принимать первый запрос на передачу данных, при этом первый запрос на передачу данных идентифицирует первое вычислительное устройство 104 в качестве вычислительного устройства-источника, идентифицирует данные, которые должны передаваться, идентифицирует третье вычислительное устройство 108 в качестве вычислительного устройства-получателя, идентифицирует то, что объем данных составляет 50 терабайт, и идентифицирует то, что такая передача должна завершаться до 16:00 на дату запроса на передачу данных. Аналогично, компонент 116 приемного устройства может принимать M-ый запрос на передачу данных, при этом M-ый запрос на передачу данных идентифицирует второе вычислительное устройство 106 как вычислительное устройство-источник, идентифицирует данные, которые должны передаваться, идентифицирует первое вычислительное устройство 104 как вычислительное устройство-получатель, идентифицирует то, что объем данных составляет 5 петабайтов, и идентифицирует то, что такая передача должна завершаться к 5:00 на следующий день.

[0030] Контроллерное вычислительное устройство 100 дополнительно содержит компонент 118 планировщика, который поддерживает связь с компонентом 116 приемного устройства. Контроллерное вычислительное устройство 100 имеет доступ к хранилищу 120 данных, при этом хранилище 120 данных включает в себя карту 122 сети. Карта 122 сети представляет физическую топографию сети 102. Например, карта 122 сети может представлять собой машинореализованный граф, который представляет сеть 102, при этом граф включает в себя узлы, которые представляют устройства (например, вычислительные устройства 104-110 и устройства 112-114 сетевой инфраструктуры) в сети 102, и ребра, которые представляют линии связи между соответствующими устройствами. Карта 122 сети дополнительно может включать в себя данные, которые идентифицируют ограничения сети 102, к примеру, пропускные способности соответствующих линий связи сети 102. В примерном варианте осуществления, карта 122 сети может время от времени обновляться на основе данных, принимаемых из устройств сети 102. Например, из устройства в сети 102 могут приниматься данные, которые указывают то, что конкретная линия связи является неактивной. В другом примере, из устройства в сети 102 могут приниматься данные, которые указывают то, что конкретная линия связи восстановлена. Карта 122 сети может обновляться время от времени, чтобы отражать эти изменения топологии сети 102.

[0031] Компонент 118 планировщика принимает множество запросов на передачу данных (во времени) и карту 122 сети из репозитория 120 данных, вычисляет долгосрочное расписание 124 для передач данных в сети 102 на основе запросов на передачу данных и карты 122 сети и сохраняет долгосрочное расписание 124 в репозитории 120 данных. Дополнительно, хотя не показано, компонент 118 планировщика может вычислять долгосрочное расписание на основе статистического использования сети. Например, если клиент статистически запрашивает передачу данных каждый день в конкретное время, компонент 118 планировщика может резервировать сетевые ресурсы для клиента в долгосрочном расписании, даже если компонент 116 приемного устройства по-прежнему должен принимать запрос на передачу данных от клиента. Еще дополнительно, компонент 118 планировщика может резервировать сетевые ресурсы для произвольно организующихся запросов при вычислении долгосрочного расписания, причем произвольно организующиеся запросы типично представляют собой произвольно организующиеся запросы, которые не имеют указанного крайнего срока и запрашивают относительно небольшой объем данных, которые должны передаваться по сети 102. В примере и как подробнее описано ниже, компонент 118 планировщика может выполнять процесс оптимизации при вычислении долгосрочного расписания 124, при этом процесс оптимизации может включать в себя выполнение смешанного алгоритма укладки и покрытия.

[0032] Далее изложены дополнительные подробности, связанные с долгосрочным расписанием 124. Долгосрочное расписание 124 покрывает множество единиц времени вперед во времени (например, будущих единиц времени). В примерном варианте осуществления, единицы времени, покрываемые долгосрочным расписанием 124, могут быть равномерными, так что единицы времени имеют общую длительность. В другом примерном варианте осуществления, единицы времени, покрываемые долгосрочным расписанием, могут быть неравномерными, при этом длительность единицы времени, покрываемой долгосрочным расписанием 124 рядом во времени с текущим временем, меньше по сравнению с единицей времени, покрываемой долгосрочным расписанием, которая является удаленной во времени от текущего времени. В соответствии с примером, долгосрочное расписание 124 может покрывать 240 последовательных одноминутных временных окон (например, для 4-часового суммарного временного окна), при этом единицы времени, покрываемые долгосрочным расписанием 124, являются одноминутными окнами. Долгосрочное расписание 124 включает в себя соответствующее детализированное расписание для каждой единицы времени, покрываемой долгосрочным расписанием 124, при этом детализированное расписание задает поток данных через сеть 102 в течение единицы времени.

[0033] Например, детализированное расписание может идентифицировать то, какие вычислительные устройства в вычислительных устройствах 104-110 представляют собой вычислительные устройства-источники, какие вычислительные устройства в вычислительных устройствах 104-110 представляют собой вычислительные устройства-получатели (при этом вычислительное устройство может представлять собой как вычислительное устройство-источник, так и вычислительное устройство-получатель), скорости, на которых соответствующие вычислительные устройства-источники должны выводить данные, и тракты, по которым данные должны передаваться из вычислительных устройств-источников в вычислительные устройства-получатели. Компонент 118 планировщика повторно вычисляет долгосрочное расписание 124 с течением времени, так что долгосрочное расписание покрывает временное окно с конкретной длительностью по мере прохождения времени. Повторное вычисление долгосрочного расписания дополнительно предоставляет возможность предположения новых запросов на передачу данных (произвольно организующихся или с указанными крайними сроками), предположения изменений топологии сети 102, предположения выполняемых запросов и т.д. Ниже изложен примерный процесс для выполнения этого вычисления долгосрочного расписания 124.

[0034] Компонент 118 планировщика может вычислять краткосрочное расписание 126 на основе долгосрочного расписания 124, и может сохранять краткосрочное расписание 126 в репозитории 120 данных. Краткосрочное расписание 126 задает поток данных через сеть 102 в течение единицы времени, которая является непосредственно последующей относительно текущей единицы времени (например, следующее одноминутное временное окно). Соответственно, краткосрочное расписание 126 покрывает меньше единиц времени, чем долгосрочное расписание 124. В примерном варианте осуществления, краткосрочное расписание 126 может покрывать одну единицу времени. Краткосрочное расписание 126 включает в себя: 1) таблицы маршрутизации для устройств 112-114 сетевой инфраструктуры, соответственно; и инструкции для вычислительных устройств-источников в вычислительных устройствах 104-110 в отношении того, следует или нет выводить конкретные данные в течение времени, покрываемого посредством краткосрочного расписания 126, и скорости, на которой можно выводить конкретные данные. Контроллерное вычислительное устройство 100 может передавать соответствующие таблицы маршрутизации в устройства 112-114 сетевой инфраструктуры и может передавать соответствующие инструкции в одно или более вычислительных устройств 104-110.

[0035] Следовательно, можно удостоверяться, что компонент 118 планировщика вычисляет долгосрочное расписание 124 и краткосрочное расписание 126, чтобы обеспечивать выполнение запрашиваемых передач данных, соответствующих утвержденным запросам на передачу данных, до соответствующих крайних сроков. В другом примере, в котором завершение передач данных является невозможным, компонент 118 планировщика может вычислять долгосрочное расписание 124, чтобы минимизировать потери дохода, обеспечивать возможность удовлетворения определенного процента от запросов (например, удовлетворения 95% всех запросов) и т.п. Дополнительно, как отмечено выше, компонент 118 планировщика может определять то, следует ли утверждать или отклонять принимаемый запрос на передачу данных, на основе долгосрочного расписания 124. В соответствии с примером, долгосрочное расписание 124 может указывать то, что в течение конкретного временного окна определенная линия связи в сети 102 запланирована для передачи данных с максимальной пропускной способностью. На основе этой информации, компонент 118 планировщика может выводить индикатор запрашивающей стороне в отношении того, что запрос на передачу данных не может быть завершен до крайнего срока (поскольку линия связи не поддерживает увеличенную пропускную способность, вызываемую посредством запроса на передачу данных). Компонент 118 планировщика дополнительно может выполнять другой анализ при диспетчеризации передач данных. Например, при работе в открытом облаке, компонент 118 планировщика может быть выполнен с возможностью определять то, следует утверждать или отклонять принимаемые запросы, чтобы максимизировать прибыль, минимизировать потери и т.д.

[0036] Контроллерное вычислительное устройство 100 дополнительно может включать в себя компонент 128 задания цен, который может обеспечивать доступность ценовой сетки для клиентов на основе долгосрочного расписания 124. Например, когда, по меньшей мере, одно из вычислительных устройств 104-110 включено в центр обработки и хранения данных, который обеспечивает доступ к ресурсам посредством открытого облака, клиенты открытого облака могут платить взносы за передачу данных. Компонент 128 задания цен может устанавливать цены для передач данных в качестве функции (длин) крайних сроков в запросах на передачи данных, времен, когда передачи должны завершаться, и т.д. Например, компонент 128 задания цен может устанавливать более низкую цену в расчете на передаваемую единицу данных, когда крайний срок запроса на передачу данных является удаленным во времени от текущего времени. Компонент 128 задания цен может вычислять ценовую сетку для того, чтобы активировать использование сети согласно требуемой рабочей точке. Иными словами, компонент 128 задания цен может устанавливать цены, чтобы обрабатывать потребность в передачах данных в сети 102 на основе основанных на крайних сроках запросов на передачу данных. Таким образом, инициаторы запросов на передачу данных могут быть стимулированы на то, чтобы предоставлять более длительные крайние сроки, с тем чтобы достигать сокращенных затрат. Кроме того, компонент 128 задания цен может быть выполнен с возможностью утверждать или отклонять ценовые предложения; например, запрос может идентифицировать несколько крайних сроков, причем каждый крайний срок имеет конкретную цену (например, в расчете на единицу, которая должна передаваться), связанную с ним. Например, запрос может указывать то, что если передача завершается к первому времени, запросчик готов заплатить первую цену, если передача завершается посредством ко второму времени, когда запросчик готов заплатить вторую цену, и т.д. Компонент 128 задания цен может действовать с возможностью выбирать цену (и в силу этого крайний срок), и долгосрочное расписание может вычисляться на основе действий компонента 128 задания цен.

[0037] Ссылаясь теперь на фиг. 2, показана примерная иллюстрация долгосрочного расписания 124, вычисленного посредством компонента 118 планировщика. Как можно удостоверяться, долгосрочное расписание 124 охватывает множество единиц времени (единица 1 времени - единица времени P). Соответственно, долгосрочное расписание 124 может восприниматься как включающее в себя множество детализированных расписаний 202-210, по одному детализированному расписанию для каждой единицы времени. Каждое детализированное расписание в детализированных расписаниях 202-210 может задавать то, как данные должны протекать через сеть 102 для соответствующей единицы времени. Например, первое детализированное расписание 202 в долгосрочном расписании 124 может задавать то, как данные должны протекать через сеть 102 для первой единицы времени (например, в течение 5 минут, представленных посредством первой единицы времени). Соответственно, первое детализированное расписание 202 может задавать, для каждой передачи данных между вычислительным устройством-источником и вычислительным устройством-получателем (потока трафика), скорость, на которой источник должен выводить данные, и тракт(ы), по которым выходные данные должны перемещаться, чтобы достигать вычислительного устройства-получателя. Следовательно, первое детализированное расписание 202 может конфигурировать (или указывать) скорость и тракт(ы) различных потоков трафика, причем каждый поток трафика имеет собственное вычислительное устройство-источник и вычислительное устройство-получатель, и каждый поток трафика имеет заданный тракт(ы), по которому поток трафика должен перемещаться из вычислительного устройства-источника в вычислительное устройство-получатель. Как указано выше, единицы 1-P времени могут иметь общую длительность, которой, в примере, может составлять от 1 минуты до 5 минут. В другом примере, единицы 1-P времени могут иметь различные длительности. Например, первая единица времени может иметь меньшую длительность, чем длительность P-той единицы времени. В соответствии с конкретным примером, первая единица времени для первого детализированного расписания 202 может иметь длительность в 1 минуту, в то время как P-тая единица времени для P-того расписания 210 может иметь длительность в 10 минут.

[0038] Теперь ссылаясь на фиг. 3, приведена примерная иллюстрация краткосрочного расписания 126. Краткосрочное расписание 126 покрывает непосредственно последующую единицу времени (единицу 0 времени). Краткосрочное расписание 126 содержит множество таблиц 302-306 маршрутизации, которые надлежащим образом соответствуют множеству устройств 112-114 сетевой инфраструктуры, и множество инструкций 308-312, которые надлежащим образом соответствуют множеству вычислительных устройств 104-110. Множество инструкций 308-312 задает то, какое из вычислительных устройств 104-110 должно начинать вывод данных, чтобы удовлетворять запросу на передачу данных, и скорость(и), на которой вычислительное устройство(а) должно выводить такие данные. Компонент 118 планировщика может передавать таблицы 302-306 маршрутизации в соответствующие устройства 112-114 сетевой инфраструктуры, и компонент 118 планировщика может передавать инструкции 308-312 в соответствующие вычислительные устройства 104-110. Таким образом, первая таблица 302 маршрутизации передается в первое устройство 112 сетевой инфраструктуры, и N-ая таблица 306 маршрутизации передается в N-ое устройство 114 сетевой инфраструктуры. Первое устройство 112 сетевой инфраструктуры, в ответ на прием первой таблицы 302 маршрутизации, сконфигурировано (для единицы 0 времени) с таблицей 302 маршрутизации и маршрутизирует данные, принятые посредством устройства 112 сетевой инфраструктуры, в соответствии с контентом первой таблицы 302 маршрутизации. Аналогично, первые инструкции 310 передаются в первое вычислительное устройство 304, и Z-ые инструкции 312 передаются в Z-ое вычислительное устройство 110. Соответственно, в примере, первое вычислительное устройство 104, в ответ на прием первых инструкций 310, выводит данные в соответствии с первыми инструкциями 310.

[0039] Со ссылкой теперь на фиг. 4, представлена подробная иллюстрация компонента 118 планировщика. Компонент 118 планировщика может осуществлять доступ к репозиторию 120 данных и извлекать карту 122 сети. Компонент 118 планировщика содержит компонент 401 конструктора сетевых графов, который принимает карту 122 сети и составляет сетевой граф 402 на основе карты 122 сети и числа единиц времени, покрываемых покрытиями долгосрочного расписания 124. Компонент 118 планировщика предписывает сохранение сетевого графа 402 в репозитории 120 данных. При составлении сетевого графа 402, компонент 401 конструктора сетевых графов может формировать несколько экземпляров карты 122 сети: по одному экземпляру для каждой единицы времени, покрываемой долгосрочным расписанием 124. Компонент 401 конструктора сетевых графов может соединять различные экземпляры карты 122 сети посредством формирования ребер, которые соединяют узлы в экземплярах карты 122 сети, которые представляют идентичное устройство.

[0040] Вкратце ссылаясь на фиг. 5, проиллюстрирован примерный сетевой граф 500, который может составляться посредством компонента 401 конструктора сетевых графов. Примерный сетевой граф 500 содержит первый экземпляр карты 501a сети для первой единицы времени и второй экземпляр карты 501b сети для второй единицы времени. Первый экземпляр 501a карты 122 сети содержит первое множество узлов 502a-508a, которые, соответственно, представляют вычислительные устройства 104-110 сети 102, и второе множество узлов 510a-512a, которые, соответственно, представляют устройства 112-114 сетевой инфраструктуры. Первый экземпляр 501a карты 122 сети включает в себя ребра (показаны сплошной линией), которые представляют физические линии связи между устройствами в сети 102. Второй экземпляр 501b карты 122 сети дополнительно включает в себя такие ребра. В примере, ребра могут быть взвешены по-разному в экземплярах карты 122 сети. Например, может быть желательным резервировать большую полосу пропускания по конкретной линии связи в сети 102 для первой единицы времени, по сравнению со второй единицей времени. Это может быть представлено в сетевом графе 500 через назначение различных весовых коэффициентов для линии связи в первом экземпляре 501a карты 122 сети и во втором экземпляре 501b карты 122 сети.

[0041] Сетевой граф 402 также включает в себя множество ребер 514-524, которые соединяют узлы между экземплярами 501a и 501b карты 122 сети, которые представляют идентичные устройства. Например, первое ребро 514 соединяет узел 504a с узлом 504b, при этом 504a и 504b представляют второе вычислительное устройство 106. Аналогично, второе ребро 516 соединяет узел 502a с узлом 502b, при этом оба узла 502a и 502b представляют первое вычислительное устройство 104 в сети 102. В примерном варианте осуществления, относительно высокие весовые коэффициенты могут назначаться ребрам 514-524. Соответственно, сеть 102 может быть представлена во множеств различных единиц времени посредством сетевого графа 402. Ребра, показанные в теле, могут быть взвешены, например, на основе пропускной способности физических сетевых линий связи, представленных посредством таких ребер, статистических потребностей физических линий связи в течение единиц времени, некоторой комбинации вышеозначенного и т.п. Хотя не показано, если сетевой граф 500 включает в себя третий экземпляр карты 122 сети, соответствующей третьей единице времени, то каждый узел в третьем экземпляре WAN-карты 122 должен соединяться со всеми узлами в сетевом графе 500, которые представляют идентичное устройство.

[0042] Возвращаясь к фиг. 4, компонент 118 планировщика дополнительно может включать в себя компонент 404 ограничителя трактов, который принимает сетевой граф 402 и применяет ограничения на основе трактов к сетевому графу 402. Например, чтобы сокращать сложность вычислений, компонент 404 ограничителя трактов может ограничивать число потенциальных трактов между источником и назначением некоторым пороговым числом трактов, может ограничивать тракты на основе числа сетевых перескоков между вычислительным устройством-источником и целевым вычислительным устройством (например, сетевые тракты, имеющие более порогового числа перескоков между источником и назначением, не рассматриваются при определении трактов между источником и получателем) или другого подходящего ограничения. В ответ на применение ограничений к сетевому графу 402, компонент 118 планировщика может сохранять ограниченный граф 406 в репозитории 120 данных.

[0043] Компонент 118 планировщика дополнительно может включать в себя компонент 408 оптимизатора, который принимает ограниченный граф 406 и данные, связанные со всеми ожидающими запросами на передачу данных (например, ранее принятыми и утвержденными запросами на передачу данных, в которых соответствующие передачи данных являются неполными), и выводит долгосрочное расписание 124 на основе ожидающих запросов на передачу данных, их соответствующих состояний (например, объемов данных, которые должны передаваться, количества времени до соответствующих крайних сроков запросов и т.д.) и ограниченного графа 406. Как указано выше, компонент 408 оптимизатора может выполнять подходящий процесс оптимизации для того, чтобы вычислять долгосрочное расписание. В примерном варианте осуществления, процесс оптимизации может включать в себя выполнение смешанного алгоритма укладки и покрытия, при этом компонент 408 оптимизатора вычисляет долгосрочное расписание 124 (например) для того, чтобы сглаживать использование сети во времени и удовлетворять крайние сроки запросов. В примерном варианте осуществления, компонент 408 оптимизатора может выполнять параллелизованную версию смешанного алгоритма укладки и покрытия. Параллелизация может быть необходимой для того, чтобы предоставлять возможность повторного вычисления долгосрочного расписания 124 во времени по мере изменения обстоятельств. Другие типы подходов оптимизации, включающие в себя подходы на основе максимизации ожидания, линейные процессы программирования и т.п., могут использоваться для того, чтобы формировать долгосрочное расписание 124. Компонент 408 оптимизатора может формировать краткосрочное расписание 126 на основе долгосрочного расписания 124.

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

[0045] Когда временной шаг начинается, компонент 408 оптимизатора выявляет все долгосрочные запросы i, для которых . Дополнительно, компонент 408 оптимизатора может иметь оценку для части пропускной способности ребра e, которая может требоваться посредством запросов с высоким приоритетом (например, произвольно организующихся) во время . Поскольку является оценкой, фактическая часть пропускной способности, требуемая для того, чтобы обслуживать произвольно организующиеся запросы, становится известной в начале времени (наряду с долгосрочными запросами, выполняемыми в такое время).

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

[0047] Эти неравенства развиваются и изменяются во времени по нескольким причинам: поступают новые долгосрочные запросы; раскрывается стохастическая реализация использования с высоким приоритетом ребер (например, для того чтобы обслуживать произвольно организующиеся запросы); и неполное выделение ребер в далеком будущем уменьшается по мере прохождения времени. Компонент 408 оптимизатора регулирует переменные в ответ на изменение неравенств, за счет этого адаптируя расписание. Следует отметить, что этот подход улучшает схемы, которые вычисляют расписания только для текущего момента времени, поскольку компонент 408 оптимизатора диспетчеризует потоки относительно далеко в будущее, обеспечивая вывод перспективного для части потребности, которую принимает i-ый запрос.

[0048] Дополнительно, как указано, компонент 408 оптимизатора может корректировать (произвольно организующиеся) запросы на передачу данных с высоким приоритетом. является оценкой части пропускной способности ребра e, необходимой посредством запросов с высоким приоритетом во время . Таким образом, при формулировании вышеуказанных неравенств, вместо использования пропускной способности во время , компонент 408 оптимизатора может использовать . После того, как время достигнуто, и наблюдается реализация такой части, компонент 408 оптимизатора может находить то, что ребро e чрезмерно используется, например, суммарный поток на e превышает его пропускную способность. Когда это происходит, компонент 408 оптимизатора может уменьшать некоторые заранее диспетчеризованные потоки , для которых . Это может выполняться посредством формулирования небольшой линейной программы (размер которой зависит только от размера исходного машинореализованного графа G, и не зависит от ) таким образом, чтобы минимизировать влияние на перспективы , выводимые посредством компонента 408 оптимизатора.

[0049] Дополнительно, компонент 408 оптимизатора может быть выполнен с возможностью недостаточно использовать ребра, которые представляют собой далекое будущее (например, ограничивать граф G), и уменьшать это ограничение по мере прохождения времени. Например, параметр может использоваться для того, чтобы определять часть , которая может быть использована посредством компонента 408 оптимизатора во время . По мере прохождения времени , могут увеличиваться (например, ограничение недостаточного использования уменьшается).

[0050] В примерном варианте осуществления, компонент 408 оптимизатора может быть выполнен с возможностью максимизировать худшую перспективу α, которая соответствует цели "справедливости". Несмотря на максимизацию α, некоторые части сети 102 могут быть недостаточно использованы, и может выделяться больший поток. Чтобы разрешать эту проблему, компонент 408 оптимизатора может использовать вторичную функцию полезности; например, максимизировать среднюю перспективу δ, что приводит к расписанию, имеющему более высокое использование сети. Эта полезность может формулироваться в качестве неравенства покрытия.

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

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

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

[0054] Далее описывается компонент 408 оптимизатора в оффлайновом случае, в котором предполагается, что компонент 408 оптимизатора имеет сведения по всем запросам с начала, например, что для всех запросов . С учетом графа G и всех k запросов, может быть желательным находить наибольший α, так что часть, по меньшей мере, α потребности каждого запроса может маршрутизироваться с учетом ограничений пропускной способности. Это упоминается как задача "параллельных многопродуктовых потоков", частный случай задачи дробного решения системы линейных ограничений укладки/покрытия. С учетом α, система линейных неравенств, требуемая для того, чтобы решать оффлайновый случай (без полезности) посредством линейной программы, заключается в следующем:

В примере, изложенном выше, процесс оптимизации выполняет поиск итеративно на предмет наилучшего α (например, с использованием способов линейного поиска). В каждой итерации, выясняется то, является линейная программа осуществимой или нет; если является осуществимой, может выводиться осуществимое решение. Ниже представлен примерный процесс для решения задачи осуществимости.

Инициализация

пока выполнение

Поиск и s.t.:

если подобных и не существует, то

прерывание и возврат того, что нет допустимых решений

иначе

если то

возврат

[0055] Инициализация, упомянутая выше, и обновление s и s выполняются таким образом, что справедливо следующее:

(1)

(2)

[0056] На каждом этапе процесса, одна (тщательно выбранная) переменная потока увеличивается. Может выбираться переменная, для которой увеличение "худшего" ограничения укладки (например, линия связи в сети 102, пропускная которой способность является ближайшей к нарушению) меньше увеличения "худшего" ограничения покрытия (например, запроса, который находится дальше всего от ограничения потребности). Существующие процессы, связанные с задачами укладки и покрытия, могут удовлетворять этому требованию посредством использования сглаженных аппроксимаций операторов min и max; приблизительное требование проявляется в неравенстве (*), где могут рассматриваться в качестве внутренних переменных, представляющих ограничения укладки, тогда как - в качестве внутренних переменных, представляющих ограничения покрытия.

[0057] Вывод существующего алгоритма укладки и покрытия гарантирует то, что ограничения покрытия удовлетворяются (при условии, что α является осуществимым). Поскольку (*) является отношением производных сглаженных аппроксимаций max и min (в противоположность отношению изменений значения ограничений), вывод нарушает ограничения укладки посредством небольшого коэффициента умножения. Коэффициент монотонно снижается до единицы по мере того, как параметр точности снижается до нуля. Такая гарантия формализуется в следующей теореме.

Теорема 1: Если линейная программа является осуществимой, то для каждого , вывод процесса удовлетворяет:

Теорема 2: Для каждого , процесс проверки осуществимости завершается после самое большее итераций.

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

[0059] Как можно удостоверяться, максимизация α соответствует цели справедливости, при которой гарантируется то, что часть α из потребности каждого запроса маршрутизируется посредством крайнего срока. Одного этого может быть недостаточным, поскольку возможно то, что решение, которое достигает наилучшего α, может не использовать части сети, и по-прежнему может маршрутизироваться большее число потоков. Соответственно, можно использовать функцию дополнительной полезности, например, среднее , которая должна быть максимизирована вдоль всех оптимальных решений исходной цели справедливости (например, вышеуказанная максимизация "худшего" α).

[0060] Любая полезность следующей формы может вводиться: , где . В частности, вышеуказанная средняя полезность α может достигаться посредством выбора . Можно отметить, что может использоваться для того, чтобы моделировать "мягкие крайние сроки". Например, запрос i может быть фиксированным, и коэффициенты полезности могут учитываться для функции , которая затухает экспоненциально быстро для (D является некоторым временным шагом). Эти функции моделируют тот факт, что D является мягким крайним сроком для запроса i.

[0061] Следующее ограничение может добавляться в линейную программу, упомянутую выше: для некоторого предположения U максимального значения g. Поскольку традиционный алгоритм укладки и покрытия работает для любых ограничений укладки и покрытия, добавление вышеуказанного линейного ограничения покрытия является возможным. С учетом ограничения, следующие изменения могут быть внесены в процесс, упомянутый выше: добавляется внутренняя переменная r; r инициализируется равным 1; при увеличении , r обновляется следующим образом: ; условие (*) изменяется на:

;

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

. (3)

[0062] Далее изложена работа компонента 408 оптимизатора в онлайновом случае, в котором компонент 408 оптимизатора принимает запросы и адаптирует долгосрочное расписание в ответ на прием запроса. Допущение, сделанное в оффлайновом случае в отношении того, что компонент 408 оптимизатора имеет сведения по всем запросам во время , например, , может быть необоснованным. Примерный процесс, который может использоваться посредством компонента 408 оптимизатора при использовании онлайн, имеет три основных свойства: он обеспечивает онлайн-обработку запросов, он вносит инкрементные изменения в решение по мере того, как поступают новые запросы, и он постепенно обновляет перспективные значения α.

[0063] Относительно такого процесса, время может индексироваться посредством . Когда временной шаг начинается, процесс, используемый посредством компонента 408 оптимизатора, выявляет запросы i, время выявления которых составляет , например, . Совокупность запросов, которые являются релевантными во время , может обозначаться посредством . Извлечение такого процесса описывается в данном документе по стадиям.

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

.

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

[0065] Онлайновый процесс во время использует решение из предыдущего временного шага в качестве начальной точки. После этого, с учетом значений для , процесс выполняет оффлайновый алгоритм, чтобы определять то, имеется или нет осуществимое решение для данных значений . Процесс может определять значения , в качестве запросов i, которые не являются новыми, например, , уже имеют перспективное значение из предыдущего временного шага. Новые выявленные запросы i, например, , могут первоначально задаваться с возможностью иметь . Процесс может приводить к процессу "разбавления", в котором наименьшие α количественных показателей увеличиваются при условии, что является осуществимым.

[0066] Относительно оффлайнового процесса, могут быть внесены следующие изменения: условие (*) изменяется на:

;

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

;

условие остановки алгоритма заключается в том, что все "новые" ограничения покрытия удовлетворяются. Аналогично уравнению (1) и уравнению (2), и поддерживаются, чтобы признавать следующие определения:

(4)

. (5)

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

[0068] Чтобы поддерживать справедливость во времени, может вводиться принцип сглаживания трафика. Интуитивно, это может выполняться посредством ограничения пропускной способности, которую инкрементный онлайновый процесс может использовать, оставляя некоторую пропускную способность свободной для будущих запросов. Формально, может обозначать часть пропускной способности ребра e в будущее время t, которая может использоваться посредством онлайнового инкрементного процесса при выполнении на временном шаге . Это изменяет ограничение пропускной способности следующим образом:

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

[0069] На основе вышеприведенного, могут реализовываться следующие изменения уравнения (1): правило может обновляться для , где ; условие (*) изменяется на:

;

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

. (6)

[0070] В онлайновом случае, при работе во время , можно улучшать результаты, полученные посредством подхода на основе сглаживания трафика. Поскольку компонент 408 оптимизатора, при использовании онлайнового процесса, применяет разбавление на каждом временном шаге , может иметь место то, что некоторые значения α могут быть улучшены. На каждом временном шаге , после онлайнового процесса (с завершением сглаживания трафика), идентичный алгоритмический подход может применяться с ограничением полезности. может обозначать систему неравенств, которую онлайновый процесс должен решать во время с полезностью :

.

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

[0071] Второе ограничение утверждает то, что суммарный поток запроса i не должен превышать совокупную потребность (это является ограничением укладки). Третье ограничение утверждает то, что полная полезность составляет, по меньшей мере, некоторое данное значение F (это является ограничением покрытия). Можно отметить, что второе ограничение не требуется в и , но требуется здесь для .

[0072] При рассмотрении таких ограничений, следующие изменения уравнения (1) могут быть включены в компонент 408 оптимизатора: могут добавляться внутренние переменные , где ; при увеличении , обновляется следующим образом: ; условие (*) изменяется на:

;

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

(7)

(8)

[0073] Как указано в теореме 1, компонент 408 оптимизатора может формировать решение, которое нарушает ограничения пропускной способности посредством небольшого коэффициента умножения самое больше на . Это может происходить как в сглаживании трафика, так и во включении полезности. Тем не менее, это не представляет собой проблему, поскольку превышение единиц потока на ребре e во время t диспетчеризовано посредством онлайнового процесса во время и пропускной способности ребра. Этот подход предоставляет возможность принятия небольших нарушений пропускной способности, сформированных посредством компонента 408 оптимизатора, без фактического нарушения пропускной способности вообще в конечном выводе, что приводит к более высоким значениям α.

[0074] Можно удостоверяться, что онлайновый случай не имеет теоретических гарантий выполнения, хотя можно подтверждать, что когда надлежащая система неравенств является осуществимой, то процесс, используемый посредством компонента 408 оптимизатора, не застревает; т.е. всегда существует переменная , которая может увеличиваться с подразумеванием того, что отношение производной сглаживания худшего ограничения укладки и производной сглаживания худшего ограничения укладки имеет верхний предел в 1. Это справедливо для любого текущего решения . Это обобщается в следующей теореме:

Теорема 3: Для любого , если , и являются осуществимыми, то всегда и существуют такие, что справедливо соответствующее условие (*).

[0075] Как упомянуто выше, запросы с высоким приоритетом (например, произвольно организующиеся запросы) предпочтительно удовлетворяются. Можно предполагать, что все запросы с высоким приоритетом разбиты на небольшие порции, имеющие , например, каждый запрос с высоким приоритетом охватывает точно один временной шаг. Процесс, упомянутый выше, имеет предшествующую оценку части пропускной способности ребра e во время t, которая требуется для запросов с высоким приоритетом. Эта часть может обозначаться посредством . Это влечет за собой следующую адаптацию вышеуказанного процесса: заменяется на . Поскольку являются оценками, может иметь место то, что как только наступает временной шаг t, и процесс выявляет фактические запросы с высоким приоритетом, становится очевидным, что требуется более чем часть пропускной способности ребра e. В этом случае, процесс может быть выполнен с возможностью уменьшать некоторый заранее диспетчеризованный поток на ребре e, что может достигаться посредством формулирования небольшой линейной программы, которая корректирует заранее диспетчеризованный поток на ребре e при минимизации влияния на гарантии по перспективе, предоставленные посредством компонента 408 оптимизатора.

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

[0077] Решение потенциальной проблемы состоит в том, чтобы разбивать этот запрос на меньшие запросы. В частности, как только процесс выявляет запрос i, как указано выше во время , он считает, что его крайний срок представляет собой текущее конечное время окна переменной длительности: . Дополнительно, его потребность задается как пропорция от его исходной потребности, которая вписывается в текущее окно переменной длительности. Если подробнее, потребность может определяться посредством следующей формулы, когда онлайновый процесс компонента 408 оптимизатора находится во время :

если и

в противном случае.

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

[0078] Можно удостоверяться, что компонент 408 оптимизатора должен работать в относительно плотном масштабе времени. Соответственно, процесс, описанный выше, может модифицироваться, чтобы обеспечивать ускорение выполнения. Например, задача нахождения кратчайшего тракта может разлагаться. Нахождение кортежа , который удовлетворяет (*), может быть практически аналогичным выполнению процесса нахождения кратчайшего тракта для всех пар на расширенном графе, который включает в себя одну копию исходной сети для каждого момента времени. Тем не менее, выполнение этого может быть слишком затратным с учетом экземпляров крупных задач, которые могут рассматриваться посредством компонента 118 планировщика. Таким образом, как упомянуто выше, сетевой граф 402 может ограничиваться. Например, для каждой пары источника-назначения, отсортированный по длине список трактов может сохраняться для каждой копии графа (длина тракта является суммой длин его ребер; длина ребра задается посредством ). Кратчайший тракт для каждой исходной целевой пары может получаться посредством взятия тракта минимальной длины из числа всех копий; преимущество такого разложения состоит в том, что кратчайшие тракты могут находиться на гораздо меньших графах.

[0079] С учетом вышеизложенного, можно отметить, что в любой итерации процесса, кратчайший тракт может вычисляться только для момента времени, соответствующего последнему обновлению (например, если такой момент времени обозначается посредством t). Дополнительно, кратчайший тракт (соответствующий времени t) должен вычисляться только для пользователей, текущий кратчайший тракт которых имеет объединенные ребра с трактом, поток которого дополнен. Это приводит к меньшему числу обновлений в каждой итерации, что обеспечивает большую эффективность процесса.

[0080] Кроме того, процесс, изложенный выше, может быть параллелизован. Постепенное увеличение переменных потоков и обновление соответствующих внутренних переменных и может выполняться параллельно до тех пор, пока отсутствует конкуренция во временной размерности, и дополнительно запрос назначается только одному потоку выполнения за раз. Чтобы подчиняться этим ограничениям, общее время может разделяться на диапазоны времени, причем каждый диапазон времени назначается различному потоку выполнения. Конкретные диапазоны времени могут выбираться таким способом, который примерно выравнивает "нагрузку" (число запросов) в каждом диапазоне. Параллелизация является прямой, когда каждый запрос является "жизнеспособным" точно в одном диапазоне времени. Тем не менее, запросы могут охватывать несколько диапазонов времени. Чтобы разрешать эту сложность, запрос может назначаться конкретному диапазону времени с вероятностью, равной относительной массе запроса в этом диапазоне времени. Такое назначение гарантирует то, что ограничения, описанные выше, фактически принудительно активированы. В фазе разброса, каждый поток выполнения выполняет данное число итераций (которое может задаваться, например, 10⁴). Следующая фаза сбора затем обновляет значения всех переменных. В то время, когда некоторое ограничение покрытия остается неудовлетворенным, и осуществимые редактирования в на основе условия (*) остаются возможными, компонент оптимизации 408 повторяет вышеуказанные фазы разброса сбора. Следует отметить, что запрос, охватывающий несколько диапазонов времени, может назначаться различным потокам выполнения в различных фазах разброса. К концу выполнения, когда число неудовлетворенных запросов является небольшим, процесс может переключаться на однопоточное выполнение (например, объем служебной информации по параллелизации становится значимым).

[0081] Если обобщать, по меньшей мере, часть из вышеприведенного, примерный алгоритм, который может использоваться посредством компонента 408 оптимизатора, может быть классифицирован в качестве смешанного алгоритма укладки и покрытия. Процесс идентифицирует решение посредством внесения небольших, при этом доказуемо безопасных изменений в переменные, так что предусмотрен предел по нарушениям перерегулирования для ограничения укладки. Когда появляются новые ограничения (например, новые передачи в следующем временном шаге или изменение характеристик сети), процесс может использовать "старое" конвергированное состояние (например, задача не должна обязательно решаться с нуля, а может начинаться с предыдущего конвергированного состояния). Процесс предоставляет возможность задания перспектив для запрашивающих сторон, при этом перспектива гарантирует то, что запрос на передачу должен удовлетворяться, несмотря на новые поступления, (произвольно организующиеся) запросы с высоким приоритетом и изменение характеристик сети. Это может достигаться посредством откладывания конкретного объема будущих сетевых ресурсов: на следующем временном шаге (от текущего времени), ресурсы могут полностью выделяться, тогда как для временных шагов в будущем, увеличивающиеся объемы ресурсов могут оставаться невыделенным. Дополнительно, такой процесс может быть параллелизован для практической реализации.

[0082] Со ссылкой на фиг. 6, проиллюстрирован примерный графический пользовательский интерфейс 600, который может быть доступным для владельца данных, сохраняемых, по меньшей мере, в одном вычислительном устройстве сети 102. Графический пользовательский интерфейс 600 включает в себя поле 602 данных, которое выполнено с возможностью принимать идентификатор данных, которые должны передаваться из вычислительного устройства-источника в вычислительное устройство-получатель. Например, на основе идентификатора данных, на которые ссылаются в поле 602 данных, может выявляться объем данных, который запрашивается для передачи из вычислительного устройства-источника в вычислительное устройство-получатель.

[0083] Графический пользовательский интерфейс 600 дополнительно включает в себя поле 604 идентификатора получателя, которое идентифицирует вычислительное устройство-получатель в сети 102. Графический пользовательский интерфейс 600 необязательно может включать в себя поле 606 начала, которое выполнено с возможностью принимать идентификатор времени, когда может начинаться передача данных в вычислительное устройство-получатель, идентифицированное в поле 604 идентификатора получателя. Если поле 606 начала опускается из графического пользовательского интерфейса 600, или начальное время не указывается, то можно предполагать, что передача данных может сразу начинаться. Графический пользовательский интерфейс 600 также включает в себя поле 608 крайнего срока, которое может принимать индикатор относительно того, когда должна завершаться передача данных из вычислительного устройства-источника в вычислительное устройство-получатель, идентифицированное в поле 604 идентификатора получателя. На основе данных, изложенных в полях 602-608, ценовая информация может представляться в поле 610 цен. Ценовая информация может изменяться, например, по мере того, как изменяется крайний срок, изложенный в поле 608 крайнего срока, по мере того, как изменяется объем данных в поле 602 данных и т.д. Соответственно, можно удостоверяться, что графический пользовательский интерфейс 600 обеспечивает указание абсолютного крайнего срока, причем передача данных должна завершаться до крайнего срока. Компонент 118 планировщика может рассматривать крайний срок при определении того, следует утверждать или отклонять запрос, и может вычислять долгосрочное расписание 124 и краткосрочное расписание 126 на основе крайнего срока.

[0084] Фиг. 7-9 иллюстрируют примерные технологии, связанные с диспетчеризацией передач данных в сети. Хотя технологии показаны и описаны как последовательность этапов, которые выполняются друг за другом, следует понимать и принимать во внимание, что технологии не ограничены посредством порядка в последовательности. Например, некоторые этапы могут осуществляться в порядке, отличном от порядка, который описывается в данном документе. Помимо этого, этап может осуществляться одновременно с другим этапом. Дополнительно, в некоторых случаях, не все этапы могут требоваться для того, чтобы реализовывать технологию, описанную в данном документе.

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

[0086] Со ссылкой теперь на фиг. 7, проиллюстрирована примерная технология 700, которая обеспечивает вычисление долгосрочного расписания. Технология 700 начинается на 702, и на 704, принимается запрос на то, чтобы передавать данные из первого вычислительного устройства в сети во второе вычислительное устройство в сети. Как указано выше, запрос содержит первые данные, которые идентифицируют второе вычислительное устройство, вторые данные, которые идентифицируют объем данных, которые должны передаваться из первого вычислительного устройства во второе вычислительное устройство в соответствии с запросом, и третьи данные, которые идентифицируют крайний срок, при этом передача данных из первого вычислительного устройства во второе вычислительное устройство должна завершаться до крайнего срока.

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

[0088] На 708, на основе долгосрочного расписания, краткосрочное расписание формируется для передач данных в сети, при этом краткосрочное расписание формируется с возможностью обеспечивать выполнение передачи данных из первого вычислительного устройства во второе вычислительное устройство до крайнего срока. Краткосрочное расписание содержит таблицу маршрутизации для устройства сетевой инфраструктуры в сети. Таблица маршрутизации идентифицирует, по меньшей мере, одно устройство, в которое должны передаваться данные, принятые посредством устройства сетевой инфраструктуры. На 710, таблица маршрутизации передается в устройство сетевой инфраструктуры, и технология 700 завершается на 712.

[0089] Со ссылкой теперь на фиг. 8 проиллюстрирована примерная технология 800, которая обеспечивает формирование долгосрочного расписания. Технология 800 начинается на 802, и на 804, принимается карта сети. Как указано выше, карта сети содержит множество узлов, которые представляют устройства в WAN, и множество ребер, которые представляют сетевые линии связи между устройствами в сети. На 806, сетевой граф составляется на основе карты сети. Сетевой граф содержит множество экземпляров карты сети: по одному экземпляр карты сети для каждой единицы времени, покрываемой долгосрочным расписанием. На 808, принимаются ограничения тракта для передач данных. Такие ограничения тракта могут ограничивать тракты, по которым могут перемещаться данные, которые должны передаваться из вычислительного устройства-источника в вычислительное устройство-получатель.

[0090] На 810, принимается информация относительно ожидающих запросов на передачу данных. Эта информация может включать в себя соответствующий объем данных, остающийся для передачи для каждого запроса, соответствующий крайний срок запроса, в числе другой информации. На 812, смешанный алгоритм укладки и покрытия выполняется параллельно по сетевому графу на основе сетевого графа, ограничений тракта и принятой информации 810. Следует понимать, что предполагается, что другие типы алгоритмов предполагаются для вычисления долгосрочного расписания. Например, линейная программа может разрешаться в связи с вычислением долгосрочного расписания. Технология 800 завершается на 814.

[0091] Обращаясь теперь к фиг. 9, проиллюстрирована примерная технология 900, которая упрощает обеспечение доступности ценовой информации относительно передач данных по сети. Технология начинается на 902, и на 904 принимается долгосрочное расписание для передач данных по сети. На 906, на основе долгосрочного расписания, формируется ценовая сетка для передач данных. Эта ценовая сетка может быть выполнена с возможностью сглаживать потребность в передачах данных в сети во времени, за счет этого повышая эффективность использования аппаратных ресурсов сети. На 908, принимается запрос на передачу данных по WAN, при этом запрос включает в себя объем данных, которые должны передаваться, и крайний срок, до которого должна завершаться передача. На 910, доступность ценовой информации обеспечивается для запрашивающей стороны на основе ценовой сетки и принимаемого запроса. Запрашивающая сторона передачи данных затем может утверждать цену или модифицировать запрос на основе ценовой информации. Технология 900 завершается на 912.

[0092] Ссылаясь теперь на фиг. 10, приведена высокоуровневая иллюстрация примерного вычислительного устройства 1000, которое может использоваться в соответствии с системами и технологиями, раскрытыми в данном документе. Например, вычислительное устройство 1000 может использоваться в системе, которая поддерживает вычисление долгосрочного расписания для передач данных в сети. В качестве другого примера, вычислительное устройство 1000 может представлять собой вычислительное устройство-источник или вычислительное устройство-получатель в сети 102. Вычислительное устройство 1000 включает в себя, по меньшей мере, один процессор 1002, который выполняет инструкции, которые сохраняются в запоминающем устройстве 1004. Инструкции, например, могут представлять собой инструкции для реализации функциональности, описанной как выполняемой посредством одного или более компонентов, поясненных выше, или инструкции для реализации одного или более способов, описанных выше. Процессор 1002 может осуществлять доступ к запоминающему устройству 1004 посредством системной шины 1006. В дополнение к сохранению выполняемых инструкций, запоминающее устройство 1004 также может сохранять таблицы маршрутизации, долгосрочные расписания, краткосрочные расписания и т.д.

[0093] Вычислительное устройство 1000 дополнительно включает в себя хранилище 1008 данных, которое является доступным посредством процессора 1002 посредством системной шины 1006. Хранилище 1008 данных может включать в себя выполняемые инструкции, расписания передачи данных и т.д. Вычислительное устройство 1000 также включает в себя интерфейс 1010 ввода, который обеспечивает возможность внешним устройствам обмениваться данными с вычислительным устройством 1000. Например, интерфейс 1010 ввода может использоваться для того, чтобы принимать инструкции из внешнего компьютерного устройства, от пользователя и т.д. Вычислительное устройство 1000 также включает в себя интерфейс 1012 вывода, который обеспечивает взаимодействие вычислительного устройства 1000 с одним или более внешних устройств. Например, вычислительное устройство 1000 может отображать текст, изображения и т.д. посредством интерфейса 1012 вывода.

[0094] Предполагается, что внешние устройства, которые обмениваются данными с вычислительным устройством 1000 через интерфейс 1010 ввода и интерфейс 1012 вывода, могут быть включены в окружение, которое предоставляет практически любой тип пользовательского интерфейса, с которым может взаимодействовать пользователь. Примеры типов пользовательского интерфейса включают в себя графические пользовательские интерфейсы, естественные пользовательские интерфейсы и т.д. Например, графический пользовательский интерфейс может утверждать ввод от пользователя с использованием устройства ввода, такого как клавиатура, мышь, пульт дистанционного управления и т.п., и предоставлять вывод на устройстве вывода, таком как дисплей. Дополнительно, естественный пользовательский интерфейс может предоставлять возможность пользователю взаимодействовать с вычислительным устройством 1000 способом без ограничений, налагаемых посредством устройства ввода, такого как клавиатуры, мыши, пульты дистанционного управления и т.п. Вместо этого, естественный пользовательский интерфейс может основываться на распознавании речи, распознавании касаний и стилуса, распознавании жестов как на экране, так и рядом с экраном, воздушных жестах, слежении за положением головы и глаз, голосе и речи, зрении, касании, жестах, искусственном интеллекте и т.п.

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

[0096] Различные функции, описанные в данном документе, могут реализовываться в аппаратных средствах, программном обеспечении или в любой комбинации вышеозначенного. При реализации в программном обеспечении, функции могут быть сохранены или переданы как одна или более инструкций или код на машиночитаемом носителе. Машиночитаемые носители включают в себя машиночитаемые носители хранения данных. Машиночитаемые носители хранения данных могут представлять собой любые доступные носители хранения данных, к которым может осуществляться доступ посредством компьютера. В качестве примера, но не ограничения, эти машиночитаемые носители хранения данных могут содержать RAM, ROM, EEPROM, CD-ROM или другое устройство хранения данных на оптических дисках, устройство хранения данных на магнитных дисках или другие магнитные устройства хранения данных, либо любой другой носитель, который может быть использован для того, чтобы переносить или сохранять требуемый программный код в форме инструкций или структур данных, и к которому можно осуществлять доступ посредством компьютера. Диск (при использовании в данном документе включают в себя компакт-диск (CD), лазерный диск, оптический диск, универсальный цифровой диск (DVD), гибкий диск и диск Blu-Ray (BD), при этом диски либо обычно воспроизводят данные магнитно, либо обычно воспроизводят данные оптически с помощью лазеров. Дополнительно, распространяемый сигнал не включен в рамки машиночитаемых носителей хранения данных. Машиночитаемые носители также включают в себя среды связи, включающие в себя любую среду связи, которая обеспечивает перенос компьютерной программы из одного места в другое. Соединение, например, может представлять собой среду связи. Например, если программное обеспечение передается из веб-сайта, сервера или другого удаленного источника с помощью коаксиального кабеля, оптоволоконного кабеля, "витой пары", цифровой абонентской линии (DSL) или беспроводных технологий, таких как инфракрасные, радиопередающие и микроволновые среды, то коаксиальный кабель, оптоволоконный кабель, "витая пара", DSL или беспроводные технологии, такие как инфракрасные, радиопередающие и микроволновые среды, включены в определение среды связи. Комбинации вышеперечисленного также следует включать в число машиночитаемых носителей.

[0097] Альтернативно или помимо этого, функциональность, описанная в данном документе, может выполняться, по меньшей мере, частично, посредством одного или более аппаратных логических компонентов. Например, и без ограничения, иллюстративные типы аппаратных логических компонентов, которые могут быть использованы, включают в себя программируемые пользователем вентильные матрицы (FPGA), специализированные интегральные схемы (ASIC), специализированные микросхемы для массового производства (ASSP), внутрикристальные системы (SOC), комплексные программируемые логические устройства (CPLD) и т.д.

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

Изобретение относится к передаче данных и предназначено для передачи больших объемов данных между вычислительными устройствами в WAN. Технический результат – повышение эффективности использования сети за счет обеспечения сглаживания объема трафика в сети во времени. Изобретение описывает различные технологии, связанные с диспетчеризацией сетевого трафика в сети. Запрос передать данные из первого вычислительного устройства во второе вычислительное устройство включает в себя данные, которые идентифицируют объем данных, которые должны передаваться в крайний срок, причем данные должны передаваться до крайнего срока. Долгосрочное расписание вычисляется на основе запроса, при этом долгосрочное расписание задает поток трафика через сеть для относительно долгосрочного временного горизонта. Краткосрочное расписание вычисляется на основе долгосрочного расписания, причем устройства в сети сконфигурированы на основе краткосрочного расписания. 3 н. и 17 з.п. ф-лы, 10 ил.

1. Способ планирования передач данных в сети, содержащий этапы, на которых:

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

идентификационную информацию второго вычислительного устройства,

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

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

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

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

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

2. Способ по п. 1, дополнительно содержащий этапы, на которых:

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

формируют долгосрочное расписание на основе карты сети.

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

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

5. Способ по п. 1, дополнительно содержащий этапы, на которых:

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

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

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

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

идентификационную информацию четвертого вычислительного устройства,

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

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

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

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

передают вторую таблицу маршрутизации в устройство сетевой инфраструктуры.

7. Способ по п. 1, в котором долгосрочное расписание вычисляется параллельно в нескольких ядрах процессора.

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

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

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

11. Способ по п. 1, в котором упомянутое вычисление долгосрочного расписания содержит этап, на котором выполняют смешанный алгоритм укладки и покрытия для вычисления долгосрочного расписания.

12. Способ по п. 1, дополнительно содержащий этапы, на которых:

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

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

13. Контроллерное вычислительное устройство, выполненное с возможностью планирования передач данных в сети, при этом контроллерное вычислительное устройство содержит:

по меньшей мере один процессор; и

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

прием множества запросов передачи данных, причем каждый запрос содержит:

указание объема данных, которые должны быть переданы, и

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

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

вычисление краткосрочного расписания на основе долгосрочного расписания, причем краткосрочное расписание охватывает второе временное окно, которое короче первого временного окна и предшествует первому временному окну;

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

14. Вычислительное устройство по п. 13, в котором вычисление долгосрочного расписания содержит выполнение смешанного алгоритма укладки и покрытия.

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

16. Вычислительное устройство по п. 13, при этом упомянутое множество единиц времени имеют равномерную длительность во времени.

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

18. Вычислительное устройство по п. 13, в котором действия дополнительно содержат:

формирование ценовой сетки на основе долгосрочного расписания; и

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

19. Вычислительное устройство по п. 13, в котором действия дополнительно содержат:

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

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

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

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

идентификационную информацию второго вычислительного устройства,

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

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

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

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

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