СПОСОБ УПРАВЛЕНИЯ РЕСУРСАМИ В ТЕЛЕКОММУНИКАЦИОННОЙ СЕТИ ИЛИ В ИНФОРМАЦИОННОЙ СИСТЕМЕ

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

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

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

В патентной заявке ЕР 1443445 описаны усовершенствованные способ и устройство управления календарем ресурсов. Однако, с одной стороны, описанные способ и устройство не обеспечивают эффективного управления перманентными резервированиями, то есть без конечной даты. С другой стороны, описанный календарь имеет фиксированную длину и управляет только временными периодами с фиксированной гранулярностью. Так, в случае резервирования, производимого заблаговременно, это может привести к принятию этого резервирования, тогда как сеть не имеет достаточных ресурсов для его поддержания. Наконец, он требует периодического осуществления дорогостоящей операции по О(M.log n), где n является размером календаря, выраженным числом меньших периодов, представленных в календаре, а М является числом резервирований, сделанных в календаре.

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

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

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

В предпочтительном варианте выполнения каждый узел дерева может содержать поле Q_n, равное сумме количеств ресурсов, зарезервированных для резервирований, имеющих упомянутый узел среди минимальных узлов, а также поле Q_f, равное нулю, если упомянутый узел не имеет узла-потомка, или равное максимуму Q_n+Q_f для всех узлов-потомков упомянутого узла, если упомянутый узел имеет по меньшей мере один узел-потомок.

В предпочтительном варианте выполнения способ может содержать этап вычисления количества Q_d ресурсов, не занятого в периоде Р резервирования. Если начальная дата периода Р следует за концом временного периода, который представляет корневой узел дерева, то количество Q_d равно Q_total-Q_p0-Q_p1, где Q_p0 является переменной, равной сумме количеств ресурсов, зарезервированных для перманентных резервирований, имеющих корневой узел дерева в качестве минимального узла, и Q_p1 является переменной, равной сумме количеств ресурсов, зарезервированных для перманентных резервирований, не имеющих корневой узел дерева в качестве минимального узла. В противном случае количество Q_d равно

Поскольку количество Q_r меньше количества Q_d, этап добавления узлов в дерево может дополнительно содержать, если добавлен узел-потомок существующего узла, инициализацию полей Q_n и Q_f упомянутого добавленного узла по нулевому значению. В противном случае, если добавлен узел и он является новым корневым узлом, то, если старый корневой узел является потомком, находящимся наиболее слева от нового корневого узла, этап добавления узлов в дерево может содержать присвоение значения Q_p0 полю Q_n нового корня и декрементацию на Q_p0 поля Q_n старого корня. В противном случае этап добавления узлов в дерево может включать в себя присвоение нулевого значения полю Q_n нового корня, инкрементацию на Q_p0 переменной Q_p1 и присвоение нулевого значения переменной Q_p0. Затем этап добавления узлов в дерево может включать в себя присвоение суммы полей Q_n и Q_f старого корня полю Q_f нового корня, добавление правых узлов-братьев старого корня, при этом значение Q_p1 присваивают полям Q_n упомянутых правых узлов-братьев и нулевое значение присваивают полям Q_f упомянутых правых узлов-братьев. Если период Р является перманентным периодом без конечной даты, этап добавления узлов в дерево может включать в себя инкрементацию Q_p0 на Q_r, если корень дерева является минимальным узлом, и инкрементацию Q_p1 на Q_r в противном случае. Этап добавления узлов в дерево может включать в себя суммирование количества Q_r с полями Q_n всех минимальных узлов периода Р и обновление полей Q_f всех узлов-предков упомянутых минимальных узлов.

Предпочтительно обновление дерева, чтобы изменить или аннулировать регистрацию в дереве периода Р резервирования количества Q_r ресурсов, может содержать этап изменения или исключения узлов в дереве. Этот этап может включать декрементацию на Q_r полей Q_n всех минимальных узлов периода Р, обновление полей Q_f всех узлов-предков упомянутых минимальных узлов и исключение листовых узлов дерева, имеющих поле Q_n, равное нулю. Если период Р является перманентным периодом без конечной даты, этот этап может включать в себя декрементацию Q_p0 на Q_r, если корень дерева является минимальным узлом, или в противном случае декрементацию Q_p1 на Q_r.

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

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

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

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

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

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

Фиг.1 - пример сетки календаря в соответствии с настоящим изобретением.

Фиг.2 - пример календаря в соответствии с настоящим изобретением.

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

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

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

Каждый узел сетки показан пунктирным кружком и представляет период времени. Каждый узел является предком совокупности узлов-потомков, каждый из которых представляет часть периода времени узла-предка. Конкатенация всех периодов, представленных узлами-потомками, равна периоду, представленному узлом-предком. Например, каждые сутки представлены узлом, который, в свою очередь, имеет два узла-потомка, каждый их которых представляет половину суток, которые, в свою очередь, имеют два узла-потомка, каждый из которых представляет период в 6 часов и каждый из которых, в свою очередь, имеет три узла-потомка, каждый из которых представляет период в 2 часа и каждый из которых имеет, в свою очередь, два узла-потомка, каждый из которых представляет период в 1 час. Для упрощения чертежа на фиг.1 не показаны узлы, представляющие периоды в 1/2 часа. Таким образом, одни сутки могут быть представлены числом узлов от одного до бесконечности.

Любой календарь в соответствии с настоящим изобретением является экземпляром части сетки, показанной на фиг.1. Календарь в соответствии с настоящим изобретением является деревом, узлы которого созданы таким образом, чтобы:

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

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

Следует отметить, что для повышения эффективности изобретения предпочтительно, чтобы сетка соблюдала разбивку времени, обычно используемую для резервирований. Например, предпочтительно, чтобы узлы представляли сутки, 1/2 суток и периоды в 6, 2 и 1 час, а не 1024-е доли года.

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

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

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

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

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

На фиг.2 показан пример календаря в соответствии с настоящим изобретением, содержащего первое резервирование от 2 ч до 9 ч и второе перманентное резервирование, начинающееся в 5 ч. Дерево, соответствующее этому календарю, показано сплошными и толстыми линиями. Корень этого дерева указан на фиг.2. Минимальные узлы первого резервирования показаны черным цветом. Минимальные узлы второго резервирования отмечены крестиком.

Число минимальных узлов для одного резервирования не превышает 2·log₂(n)+2(o-2), где n является размером календаря, выраженным числом меньших периодов, представленных в дереве, то есть периодом листьев дерева низшего уровня, и о является порядком дерева. Прохождение этих минимальных узлов можно осуществлять по O(log(n)). В каждом узле дерева запоминают два значения:

- Q_n: сумма количеств ресурсов, зарезервированных для резервирований, имеющих этот узел в качестве минимального узла;

- Q_f: максимальное значение (Q_n+Q_f) между всеми узлами-потомками или ноль, если узел не имеет потомков.

Кроме описанного выше дерева, определяют две целые переменные:

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

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

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

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

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

Если начало периода Р больше или равно концу периода, покрываемого деревом, то незанятое количество на период Р равно Q_total-Q_p0-Q_p1.

В противном случае незанятое количество на период Р равно

где Q_n и Q_f являются нулевыми для узлов сетки, которые не созданы в дереве. Необходимо отметить, что прохождение совокупности минимальных узлов можно осуществлять со сложностью во времени по O(log n). Поскольку это прохождение осуществляют от корня дерева, сумму Q_n(j) можно вычислить очень легко.

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

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

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

если старый корень является самым левым потомком нового корня: то

Q_n(новый корень)=Q_p0;

Q_n(старый корень)=Q_n(старый корень)-Q_p0.

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

Q_n(новый корень)=0;

Q_p1=Q_p1+Q_p0;

Q_p0=0.

Q_f(новый корень)=Q_n(старый корень)+Q_f(старый корень).

Создание правых братьев старого корня происходит при:

Q_n=Q_p1;

Q_f=0.

Если новое резервирование является перманентным, то резервируемое количество ресурсов добавляют к Q_p0, если корень дерева является минимальным узлом, в противном случае - к Q_p1.

Предпочтительно операцию аннулирования резервирования можно производить посредством вычитания зарезервированного количества ресурсов из Q_n всех минимальных узлов резервирования с D_min в качестве минимальной даты и повторного вычисления Q_f для всех предков минимальных узлов.

Во время прохождения минимальных узлов листья дерева, имеющие нулевое Q_n, можно уничтожить.

Если аннулированное резервирование было перманентным, то зарезервированное количество ресурсов вычитают из Q_p0, если корень дерева является минимальным узлом, и в противном случае - из Q_p1.

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

Описанное изобретение является особенно эффективным при большом числе резервирований.