СПОСОБ И УСТРОЙСТВО ДЛЯ УПРАВЛЕНИЯ БУФЕРОМ ОЧЕРЕДИ Российский патент 2008 года по МПК H04L12/56 

Описание

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

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

Предшествующий уровень техники

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

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

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

Известно множество принципов управления очередью, включая такие принципы, в которых параметр длины очереди (например, абсолютная длина очереди или средняя длина) контролируется и сравнивается с пороговым значением длины, чтобы выполнить процедуру уведомления о перегрузке, если пороговое значение превышено. Такая процедура уведомления о перегрузке может состоять в отбрасывании блока данных и/или в маркировке блоков данных (например, установке флага уведомления о перегрузке в блоках данных). Различные примеры таких принципов управления, например отбрасывание при заполнении или случайное раннее обнаружение (RED), описаны во вводной части документа EP-А-1 249 972, поэтому повторять их здесь нет необходимости.

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

Задача изобретения

Задачей настоящего изобретения является создание усовершенствованного способа и устройства для управления буфером очереди.

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

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

В соответствии с настоящим изобретением в системе, в которой управление буфером очереди или администрирование буфера очереди содержит определение значения параметра длины, связанного с длиной очереди, сравнение этого значения с порогом и выполнение процедуры уведомления о перегрузке, если порог превышен, и в котором предусмотрена процедура адаптации, указанная процедура автоматической адаптации порога действует в одном из, по меньшей мере, первого и второго режима адаптации, где первый режим адаптации связан с минимизацией задержки в очереди, и адаптирует пороговое значение (Lth) на основе n·LC, где LC представляет оцененное значение емкости канала связи, и n=1, и второй режим адаптации связан с максимизацией использования и адаптирует упомянутое пороговое значение (Lth) на основе m·LC, где m>1 и m>n.

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

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

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

В соответствии с другим предпочтительным вариантом осуществления изобретения способ управления буфером очереди и контроллер буфера очереди выполнены таким образом, что события, которые указывают потенциальную потерю данных в потоке, который помещен в очередь в буфере очереди, также принимаются во внимание для динамической адаптации порогового значения длины в заданном режиме адаптации. Иными словами, после того как заданный режим установлен (например, вручную или автоматически, причем автоматическая установка может быть выполнена на основе измеренного числа событий указания потерь), что означает, что пороговое значение базовым образом адаптируется на основе соотношений n·LC или m·LC, где LC представляет емкость канала связи и m>n, динамическая последующая настройка может быть выполнена в зависимости от измеренного числа событий указания потерь.

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

Возможность автоматической адаптации порога для реализации в первом режиме или втором режиме означает, что заданной очередью в буфере управляют в соответствии с одним из режимов. Возможно, что буфер содержит множество очередей, каждая из которых связана с одним из доступных режимов (разумеется, может иметься более двух доступных режимов работы, например третий режим, в котором порог длины адаптируется на основе q·LC, где q>m). Иными словами, каждая очередь имеет свое соответствующее пороговое значение длины для сравнения с соответствующим измеренным параметром длины, и каждый порог длины адаптируется индивидуальным образом. В такой ситуации предпочтительным является вариант осуществления, в котором входящие блоки данных, которые должны быть помещены в очередь, разделяются на категории, связанные с режимами, и затем помещаются в очередь, управляемую в соответствии с указанным режимом. Например, контроллер буфера может осуществлять синтаксический анализ блока данных на наличие конкретной информации, например идентификатора протокола или идентификатора порта в заголовке, и назначать блоки данных, являющиеся чувствительными к задержке (например, блоки данных, транспортирующие сегменты из приложения Telnet), в очередь, управляемую в режиме для снижения задержки, и назначать блоки данных, являющиеся чувствительными к пропускной способности (например, блоки данных, транспортирующие сегменты из приложения ftp), в очередь, управляемую в режиме для максимизации использования.

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

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

фиг. 1 - схематичное представление блок-схемы буфера и контроллера буфера в соответствии с изобретением;

фиг. 2 - блок-схема варианта осуществления способа в соответствии с изобретением;

фиг. 3 - блок-схема другого варианта осуществления способа в соответствии с изобретением;

фиг. 4 - блок-схема базового варианта осуществления способа в соответствии с изобретением.

Детальное описание вариантов осуществления изобретения

Хотя в некоторых из описываемых далее вариантов осуществления могут даваться ссылки на конкретные протоколы, такие как TCP/IP, настоящее изобретение может быть применено к любой системе, транспортирующей блоки данных, в которых используется схема управления очередью, где проводится процедура уведомления о перегрузке в зависимости от события достижения параметром длины очереди порогового значения длины. Настоящее изобретение не ограничивается каким-либо конкретным таким порогом длины и схемой уведомления о перегрузке, и поэтому, например, применимо к любой известной схеме RED, к схемам, которые отбрасывают блоки данных, когда очередь заполнена, например, с отбрасыванием концевого сегмента, случайным отбрасыванием или отбрасыванием переднего сегмента, и к любой известной схеме, которая выполняет уведомление о перегрузке в явной форме вместо или в дополнение к любому отбрасыванию блоков данных.

Предпочтительно применять способ и устройство, соответствующие настоящему изобретению, в связи с активным управлением очередью, раскрытым в ЕР-А-1249972. Все раскрытие данного документа и соответствующая ему заявка США включены в настоящее описание посредством ссылки.

На фиг. 1 показано схематичное представление контроллера 10 буфера очереди, обеспечивающего реализацию настоящего изобретения для управления блоками данных в буфере 20 очереди. Ссылочной позицией 3 обозначена коммуникационная сеть, по которой блоки 30 данных поступают в буфер 20 очереди для помещения в очередь 21, прежде чем передаваться по каналу 40 связи. Ссылочная позиция 50 относится к устройству передачи блоков данных, в котором предусмотрены буфер 20 и контроллер 10. Устройство передачи блоков данных может представлять собой, например, маршрутизатор или сервер, соединенный с коммуникационной сетью 3.

Блоки 30 данных, помещенные в очередь 21, могут принадлежать одному или более потокам. Поток в общем случае идентифицируется адресом источника и получателя, идентификатором пункта доступа к услугам (SAP) и идентификатором протокола. Определение и концепция потока хорошо известны в уровне техники, например, из TCP/IP, и в этом случае адреса источника и получателя называются IP-адресами, а SAP-идентификатор является адресом порта, так что дальнейшее объяснение здесь не требуется.

Далее описаны конкретные элементы для воплощения принципа настоящего изобретения в контроллере 10 буфера очереди. Следует отметить, что контроллер буфера очереди в общем случае содержит больше элементов, чем эти показанные элементы, в частности известные элементы для обработки принимаемых блоков данных и управления буфером, которые для простоты не описаны подробно. В частности, контроллер 10 может иметь дополнительные элементы, чтобы реализовать систему, описанную в ЕР-А-1 249 972.

Ссылочная позиция 101 относится к блоку определения длины очереди, предназначенному для определения значения параметра длины, связанного с длиной очереди 21. Кроме того, предусмотрен блок 102 сравнения для сравнения определенного значения длины с пороговым значением Lth длины, обеспечиваемым блоком 104 адаптации порога, который выполнен с возможностью автоматической адаптации пороговых значений путем оценивания значения LC емкости канала связи на основе скорости DR передачи данных канала 40 связи. Блок 102 сравнения соединен с блоком 103 уведомления о перегрузке, который выполняет процедуру уведомления о перегрузке, если определенное значение длины больше, чем пороговое значение длины. Как пояснено более детально ниже, параметр длины, который должен быть определен, может выбираться любым подходящим или желательным способом, например представлять собой абсолютную длину QL очереди или усредненную длину QLav очереди, и процедура уведомления о перегрузке может быть равным образом выбрана как подходящая или желательная, например, как процедура отбрасывания блоков данных и/или процедура маркировки блоков данных в явной форме.

Блок 103 уведомления о перегрузке предпочтительно содержит решающий блок 1031 для принятия решения о том, следует ли выполнить уведомление о перегрузке или нет по отношению к одному или более блокам данных в очереди 21. Иными словами, блок 103 уведомления о перегрузке выполняется таким образом, что он не обязательно выполняет уведомление о перегрузке, если параметр длины очереди превышает пороговое значение длины. Это, в принципе, известно из предшествующего уровня техники, например из системы RED или других систем, описанных в ЕР-А-1 249 972, где пороговое значение длины является первым или более низким порогом, и также предусмотрен второй или более высокий порог, причем если параметр длины очереди превышает первый порог, но не превышает второй порог, то принимается вероятностное решение для выполнения уведомления о перегрузке по отношению к одному или более блокам данных.

В соответствии с настоящим изобретением блок 104 адаптации порога работает в одном из, по меньшей мере, двух режимов адаптации. Первый режим адаптации связан с минимизацией задержки очереди и осуществляет адаптацию порогового значения Lth длины на основе соотношения n·LC, где n ≥ 1. Например, n может быть равно 1, и первый режим адаптации устанавливает Lth = LC или Lth = LC + Δ1, где Δ1 - положительный коэффициент, меньший, чем LC, например 0 < Δ1 ≤ LC/10. Второй режим адаптации связан с максимизацией использования и осуществляет адаптацию порогового значения длины Lth на основе соотношения m·LC, где m>1 и m>n. Например, m может быть равно 3, и второй режим адаптации устанавливает Lth = 3·LC - Δ2, где Δ2 - положительный коэффициент, меньший, чем LC, например 0 < Δ2 ≤ LC/10. Если предусмотрена функция динамической адаптации по отношению к внешним событиям (таким, как события указания потерь) после установки режима, то вышеуказанные установки являются начальными и затем могут быть изменены в соответствии с появлением таких событий. Если не предусматривается функция динамической адаптации, то значение Lth может сохраняться в том виде, как установлено, но следует отметить, что значение LC в общем случае не является статическим, то есть LC будет изменяться во времени, что приведет к возможности изменения соответствующего значения Lth.

Коэффициенты m и n могут быть произвольными положительными числами, но предпочтительно являются положительными натуральными числами.

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

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

Поэтому емкость канала связи также можно понимать как произведение скорости передачи данных, обеспечиваемой каналом 40 связи для рассматриваемого потока, на время двустороннего распространения (RTT), связанное с упомянутым потоком для случая незагруженной сети. Незагруженная сеть означает, что отсутствует задержка очереди. Вследствие этого значение RTT для незагруженной сети равно разности между действительным RTT потока и всеми задержками очереди для упомянутого потока. Емкость канала связи также определяется иногда как емкость магистрали для гипотетической магистрали между конечными пунктами потока, причем данная магистраль имеет "ширину" DR и "длину", равную значению RTT для незагруженной сети.

Поэтому оценка значения емкости канала связи будет в общем случае заключаться в определении значения времени, указывающего на значение RTT незагруженной сети, и умножении этого значения на скорость DR передачи данных, обеспечиваемую каналом 40 связи для рассматриваемого потока. Определение этого значения RTT незагруженной сети может осуществляться любым подходящим или желательным способом. Одним примером этого является вычисление суммы постоянного значения RTTwc и значения RTT, обеспечиваемого каналом 40 связи. Значение RTTwc является оценкой наихудшего случая полного значения RTT незагруженной сети, исключая вклад, вносимый каналом 40 связи, и может иметь значение от 150 до 300 мс, более предпочтительно от 150 до 250 мс. Использование этого принципа имеет преимущество, заключающееся в том, что не требуется получать информацию, специфическую для потока.

Альтернативная возможность оценивания значения RTT незагруженной сети для данного потока состоит в вычислении задержки очереди в буфере 20, например, путем сохранения среднего значения времени, в течение которого буферизуемый блок 30 данных находится в очереди 21, и вычисления разности между действительным RTT потока и этой задержкой очереди. Значение действительного RTT для потока может, например, вводиться в блоки данных упомянутого потока отправителем и считываться контроллером 10.

Следует отметить, что оценка LC емкости канала связи, в общем случае, не будет идентичной текущей мгновенной емкости канала связи. Процесс оценивания емкости канала связи предпочтительно таков, что оцененное значение превышает действительную емкость канала связи, то есть оценка является консервативной. Это может быть реализовано любым подходящим или желательным способом, например, с использованием вышеупомянутых оценок наихудшего случая для RTT незагруженной сети и/или путем добавления предварительно определенных положительных коэффициентов к одному или более параметрам, используемым при оценивании емкости канала связи. Иными словами, можно добавить предварительно определенный коэффициент к значению RTT незагруженной сети и/или к значению RTT канала связи, и/или к значению DR, и можно добавить предварительно заданный положительный коэффициент ε к результату вычислений, то есть заменить вычисленное значение LC на LC + ε: LC ← LC + ε.

Выбор параметров n и m для первого и второго режима предпочтительно выполняется в соответствии с реакцией, которую отправитель блоков данных будет проявлять при приеме уведомления о перегрузке. Если отправитель относится к типу, который снижает свою нагрузку на сеть в соответствии с коэффициентом k, например делит свое окно передачи на k, если используется основанное на использовании окна управление потоком, то n предпочтительным образом выбирается как равное k-1, а m предпочтительным образом выбирается как k²-1. Причина этого поясняется ниже.

Как отмечено выше, оцененная емкость LC канала связи такова, что как только отправленных блоков данных становится больше, чем это значение, возникает очередь. Как следствие, если достигнуто пороговое значение Lth длины, то объем отправленных данных равен LC+Lth. Вследствие этого, если инициированы уведомления о перегрузке, то основанный на использовании окна отправитель будет иметь окно передачи, равное LC+Lth.

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

,

что приводит к Lth=LC·(k-1).

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

,

которое, в свою очередь, приводит к Lth=LC·(k²-1).

В случае протокола TCP/IP, k=2, то есть передатчик уменьшает окно передачи при приеме уведомления о перегрузке или определении события указания потери блока данных. Вследствие этого, если для помещения в очередь сегментов TCP используется управляемый буфер, то n предпочтительно равно 1, а m предпочтительно равно 3.

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

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

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

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

На фиг. 4 показана блок-схема базового варианта осуществления способа, соответствующего настоящему изобретению, причем этот способ может быть выполнен с использованием контроллера 10, показанного на фиг. 1. На первом этапе S1 определяется значение параметра длины, связанное с длиной очереди 21. Этот параметр, связанный с длиной очереди, может быть связан с длиной очереди любым желательным или подходящим способом, например, представлять собой действительное или мгновенное значение QL длины очереди или параметр, выведенный из действительного или мгновенного значения длины очереди, такой как среднее значение QLav.

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

Qlav (новое) = Qlav (старое) х (1-1/2^wf) + (QL х 1/2^wf),

где QL представляет мгновенное значение длины очереди и wf - экспоненциальный весовой коэффициент, настраиваемый между 0 и 1.

Согласно фиг. 4 на этапе S2 параметр QL длины очереди сравнивается с пороговым значением Lth длины очереди. Если пороговое значение Lth длины очереди превышено, то выполняется процедура S3 уведомления о перегрузке, в противном случае процедура S3 уведомления о перегрузке пропускается.

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

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

В примере, показанном на фиг. 4, процедура управления затем продолжается на этапе S5, на котором выполняется процедура автоматической адаптации порога. Как определено выше, процедура S5 автоматической адаптации порога выполняется в одном из, по меньшей мере, первого и второго режима адаптации, причем первый режим адаптации связан с минимизацией задержки очереди и адаптацией порогового значения Lth на основе соотношения n·LC, где n=1, а второй режим адаптации связан с максимизацией использования и адаптацией порогового значения Lth на основе соотношения m·LC, где m>1 и m>n.

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

На фиг. 2 показан вариант осуществления способа, который содержит все этапы варианта, показанного на фиг. 4, так что повторное их описание не требуется, при этом процедура S4 обнаружения события указания потери добавлена после этапов S2, S3. Эта процедура S4 обнаружения события указания потери может обнаруживать события, которые указывают на потенциальную потерю блока данных в одном или более потоков, помещенных в очередь 21, где возникает эта потенциальная потеря блока данных вне устройства 15 передачи блоков данных. Например, процедура S4 обнаружения события указания потери может содержать контроль идентификаторов блоков данных помещенного в очередь потока, где пропуск блока данных из последовательности указывает на потенциальную потерю блока данных. Альтернативно или дополнительно, процедура обнаружения события указания потери может содержать контроль информации указания потери в блоках данных подтверждения, посланных от получателя потока к отправителю потока, причем эта информация указания потери может быть представлена в явной или неявной форме.

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

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

Например, если процедура обнаружения события указания потери указывает некоторое количество потенциальных потерь блоков данных вне устройства 50 передачи, то порог Lth, используемый для запуска процедуры уведомления о перегрузке, может быть увеличен относительно значения, которое было установлено в заданном режиме. Например, он может быть увеличен относительно оцененного значения LC емкости канала связи, которое могло бы являться начальным вариантом выбора для значения Lth в первом режиме. Увеличение будет составлять только долю от LC, например, до одной десятой LC, в качестве некоторого типа «тонкой настройки» в заданном режиме.

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

Следует обратить внимание на тот факт, что конкретный порядок этапов, показанный на фиг. 2 и 4, приведен только для примера. В частности, этапы S1, S2 и S3, которые совместно образуют процедуру принятия решения о запуске процедуры уведомления о перегрузке, не зависят от процедуры адаптации, воплощенной посредством этапа S5. Следовательно, этапы S1-S3 могут быть упорядочены независимо от этапа S5. Равным образом, этап S4 может реализовываться независимо от этапов S1-S3 и S5, например, как процедура, которая выполняется параллельно с другими и/или селективно вызывается в качестве подпрограммы.

В отношении примеров, показанных на фиг. 2 и 4, следует отметить, что все показанные этапы, в принципе, будут содержаться в более масштабном способе управления буфером 20 очереди, причем этот более масштабный способ имеет больше этапов и процедур, но эти дополнительные этапы и процедуры не показаны, поскольку они не касаются настоящего изобретения. Способы по фиг. 2 и 4, как и все варианты осуществления способов согласно изобретению, могут быть реализованы как программное обеспечение, где этапы S1-S3 могут быть реализованы, например, в одной цепочке программ, в то время как этап S5 может быть реализован в другой независимой цепочке программ. Этап S4 может быть реализован в еще одной независимой цепочке программ.

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

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

Процесс получения характеристического значения отсчета может быть выбран любым подходящим или желательным способом. Например, он может содержать определение числа событий указания потерь, возникающих вне устройства 50 передачи блоков данных в рассматриваемом помещенном в очередь потоке в каждом из р соответствующих предварительно определенных временных интервалов, где р - натуральное число, и затем выбор максимума из этих чисел в качестве характеристического значения отсчета. Если р равно 1, то это означает просто отсчет числа событий указания потерь в пределах предварительно определенного интервала и выдачу значения отсчета для каждого последовательного интервала. Для того чтобы сделать характеристическое значение отсчета менее восприимчивым к кратковременным флуктуациям, предпочтительно выбрать р большим, чем 1, например р=5. В этом случае процедура удерживает отсчитанное число событий указания потерь в пяти самых последних интервалах и выводит максимум из событий указания потерь самых последних пяти интервалов в качестве характеристического значения отсчета.

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

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

AV(новое)=AV(старое) x (1-q) + Num x q,

где AV представляет усредненное значение, q - весовой коэффициент, определяемый как 0<q<1, и Num представляет число событий указания потерь в самом последнем завершенном интервале.

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

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

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

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

Далее другой вариант осуществления настоящего изобретения описан со ссылкой на фиг. 3. Этапы S1 и S2 идентичны тем, которые уже были описаны со ссылкой на фиг. 2 и 4, так что нет необходимости в повторении этого описания. Однако в примере по фиг. 3 процедура S3 уведомления о перегрузке состоит из этапов S31, S32 и S33, которые отличаются от примера, показанного на фиг. 2 или 4. Этап S31 представляет процедуру S32 принятия решения о том, следует ли выполнять уведомление о перегрузке по отношению к одному или более блокам данных. Например, это может быть приведенным выше примером проверки функции вероятности. Если результат этой процедуры принятия решения утвердительный, то проводится этап S31, то есть процедура определения того, не произошло ли событие, указывающее на потенциальную потерю блока данных вне устройства 50 передачи данных для рассматриваемого потока, и если такое событие произошло, то решение о выполнении уведомления о перегрузке на этапе S31 отменяется. Иными словами, в этом случае не выполняется уведомление о перегрузке.

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

Иными словами, после обнаружения превышения параметром QL значения Lth, контролируется, произошло ли событие LIE указания потери в течение времени GT или нет. Если возникает событие указания потери, то принятое на этапе S31 решение об уведомлении о перегрузке отменяется или блокируется, то есть не выполняется, так как предполагается, что отправитель потока будет снижать свою нагрузку на сеть на основе указанной потери блоков данных вне устройства 50 передачи, так что выполнение уведомления о перегрузке могло бы привести к избыточному сокращению посылаемых блоков данных со стороны отправителя потока, тем самым, возможно, приводя к недоиспользованию канала 40 связи.

С другой стороны, если в процедуре на этапе S32 не обнаруживается события указания потери в течение защитного интервала времени GT, то уведомление о перегрузке, решение о котором принято на этапе S31, выполняется на этапе S33.

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

Далее описан еще один вариант осуществления. Возможность автоматической адаптации S5 порога или возможность работы блока 1094 адаптации порога в первом режиме или во втором режиме означает, что заданная очередь в управляемом буфере управляется в соответствии с одним из режимов. Возможно, что буфер поддерживает множество очередей, каждая из которых связана с одним или более из доступных режимов. Разумеется, может иметься больше, чем два режима, например третий режим, в котором порог длины адаптируется на основе sxLC, где s>m. Иными словами, каждая очередь имеет свое соответствующее пороговое значение длины для сравнения с соответствующим измеренным параметром длины, и каждый порог длины адаптируется индивидуально. В такой ситуации предложен вариант осуществления, в котором входящие блоки данных, которые должны помещаться в очередь, селектируются по категориям, связанным с режимами, и затем помещаются в очередь, управляемую в соответствии с выбранным режимом. Например, контроллер буфера может выполнять синтаксический анализ блока данных на наличие конкретной информации, например идентификатора протокола или идентификатора в заголовке, и относить блоки данных, чувствительных к задержке (например, блоки данных, транспортирующие сегменты из Telnet-приложения), к очереди, управляемой в режиме для снижения задержки, и относить блоки данных, чувствительных к пропускной способности (например, блоки данных, транспортирующие сегменты из ftp-приложения), к очереди, управляемой в режиме для максимизации использования.

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

Изобретение относится к области сетей передачи данных. Технический результат заключается в реализации двух различных режимов работы, один из которых предусмотрен для снижения задержки очереди, а другой - для увеличения использования. Сущность изобретения заключается в том, что система управления буфером очереди, в которой параметр QL длины очереди сравнивается с пороговым значением Lth для инициирования процедуры уведомления о перегрузке, содержит процедуру принятия решения для решения о том, следует ли выполнять уведомление о перегрузке или нет. Также предусмотрена процедура S5 автоматической адаптации порога для адаптации порога Lth на основе оцененного значения LC емкости канала связи. Процедура S5 автоматической адаптации порога действует в одном из, по меньшей мере, первого и второго режима адаптации, где первый режим адаптации связан с минимизацией задержки в очереди и адаптирует пороговое значение Lth на основе n·LC, где n≥1, и второй режим адаптации связан с максимизацией использования и адаптирует пороговое значение Lth на основе m·LC, где m>1 и m>n. 2 н. и 34 з.п. ф-лы, 4 ил.

1. Способ управления буфером (20) очереди в устройстве (50) передачи блоков данных, причем упомянутый буфер очереди предназначен для помещения блоков (30) данных в очередь (21) и соединен с каналом (40) связи, содержащий

определение (S1) значения (QL; QLav) параметра длины, связанного с длиной очереди,

сравнение (S2) этого значения (QL; QLav) с пороговым значением (Lth) и выполнения (S3) процедуры уведомления о перегрузке относительно одного или более блоков данных из упомянутой очереди, если упомянутое значение (QL; QLav) больше, чем упомянутое пороговое значение (Lth) длины, и

процедуру (S5) автоматической адаптации порога, которая содержит оценивание значения (LC) емкости канала связи на основе скорости (DR) передачи данных канала (40) связи и адаптацию порогового значения (Lth) на основе оцененного значения (LC) емкости канала связи,

отличающийся тем, что

процедура (S5) автоматической адаптации порога действует в одном из, по меньшей мере, первого и второго режима адаптации, где первый режим адаптации связан с минимизацией задержки в очереди и адаптирует пороговое значение (Lth) на основе n·LC, где LC представляет оцененное значение емкости канала связи, и n≥1, и второй режим адаптации связан с максимизацией использования и адаптирует упомянутое пороговое значение (Lth) на основе m·LC, где m>1 и m>n.

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

процедуру получения характеристического значения отсчета из отсчитанных чисел.

блок (101) определения длины очереди для определения значения параметра (QL; QLav) длины, связанного с длиной упомянутой очереди (21),

блок (102) сравнения для сравнения упомянутого значения с пороговым значением (Lth),

блок (103) уведомления о перегрузке для выполнения процедуры уведомления о перегрузке, если упомянутое значение больше, чем упомянутое пороговое значение длины, и

блок (104) адаптации порога для автоматической адаптации упомянутого порогового значения (Lth) длины путем оценивания значения (LC) емкости канала связи на основе скорости (DR) передачи данных упомянутого канала (40) связи и адаптации упомянутого порогового значения (Lth) длины на основе оцененного значения (LC) емкости канала связи,

отличающийся тем, что

упомянутый блок (104) адаптации порога действует в одном из, по меньшей мере, первого и второго режима адаптации, где первый режим адаптации связан с минимизацией задержки в очереди и адаптирует пороговое значение (Lth) на основе n·LC, где LC представляет оцененное значение емкости канала связи и n≥1,и второй режим адаптации связан с максимизацией использования и адаптирует упомянутое пороговое значение (Lth) на основе m·LC, где m>1 и m>n.