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

Очевидно, что при условии выполнения следующего соотношения каждому поступающему в рассматриваемый маршрутизатор потоку предоставляются гарантии по полосе пропускания (bandwidth guarantees):

Выполнение лишь этого условия справедливо только для случая непрерывного времени (fluid flow) [LeBoudec02], в то время как в реальных сетях на базе протокола IP нагрузка может быть только лишь аппроксимирована непрерывной функцией в связи с тем, что дисперсия размеров пакетов достаточно велика. Таким образом, для предоставления гарантий по полосе пропускания для реальной сети необходимо выполнение двух условий:

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

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

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

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

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

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

Очевидно, что недостатком является невозможность правильной оценки скорости потока с высокой пачечностью. Более сложным, и в то же время более эффективным, является алгоритм, представленный на рис. 2.10. При поступлении некоторого пакета, длиной Ь, в момент времени г, скорость потока измеряется как количество байт этого потока, поступивших за последние XV секунд, поделенное на значение \У. Далее осуществляется сравнение суммы байт, поступивших за последние \У секунд и размера Ь поступившего пакета с номинальным значением допустимой скорости М, определяемой как максимально допустимое количество байт в некоторый промежуток времени. В случае, если сумма не превышает значение N, поступивший пакет помешается в очередь, иначе - сбрасывается. Данный алгоритм требует, чтобы timestamp каждого поступающего пакета был сохранен для последующих вычислений. Это требование накладывает определенные ограничения на его практическое использование.

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

Рис. 2.10. Метакод алгоритма измерения скорости потока

Рис. 2.11. Метакод алгоритма измерения скорости потока при помощи «скользящего окна» подобной проблемы может быть попытка осуществления как можно более точной аппроксимации моментальной скорости. Используя алгоритм «скользящее окно», можно построить аппроксимацию описанной выше процедуры измерения, или, говоря более точно, аппроксимировать среднюю скорость потока. Аппроксимация состоит в том, что вводится предположение о непрерывности времени. Среди недостатков данного алгоритма необходимо отметить сложность инициализации, конкретнее - выбора значения параметра размера скользящего окна W. Метакод алгоритма представлен на рис. 2.11.

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

⇐Контроль нагрузки и политика управления нагрузкой | Управление трафиком и качество обслужевания в сети | Алгоритм leaky bucket⇒