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

перегрузка компьютерной сети, самоподобный трафик, модель трафика

Введение

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

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

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

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

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

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

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

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

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

Основной материал

Математическая модель трафика. В работе показано, что длина очереди в буфере узла канала определяется тремя основными параметрами: интенсивностью трафика X, параметром Фано F (отношение дисперсии числа событий на временном интервале к математическому ожиданию этой величины) и показателем Херста H. Большие значения параметра Фано соответствуют большему разбросу значений входного потока, который даже при небольшой интенсивности создает очереди. Показатель Херста характеризует долгосрочную зависимость процесса. В частности, это означает, что за высокими значениями процесса с большой вероятностью также будут следовать высокие, что не дает достаточно быстро освободиться буферу.

Модель трафика, предложенная в работе, представляет собой самоподобный случайный процесс с дискретным временем, основой которого является фрактальный гауссовский шум, полученный для заданного значения показателя Херста. Входными параметрами модели являются оценки интенсивности, параметра Фано и показателя Херста входного трафика. Временную реализацию модельного трафика предложено искать в виде Y = b • е , где X -реализация фрактального гауссовского шума, построенного методом последовательных случайных сложений; b,k - параметры, зависящие от интенсивности и параметра Фано входного трафика [9].

В табл. 1 представлены значения параметров X , F и H для некоторых из рассмотренных реализаций реального трафика. Величина B показывает среднюю длину очереди, образующуюся при имитационном моделировании прохождения трафика через коммутатор при 90% загрузке канала.

Таблица 1

Параметры трафика

На рис. 1 (а, б) приведено графическое изображение модельной и реальной реализаций трафиков для первого набора значений табл. 1.

Имитационное моделирование. В данной работе система связи состоит из буферной памяти коммутатора и канала и рассматривается как система массового обслуживания (СМО) [5].

Рассматриваемую СМО можно обозначить как G/D/C/B/d, где G означает, что входной трафик имеет произвольное распределение; D - детерминированное время обслуживания, равное единице; C -число обслуживающих приборов; ^B означает размер буфера, а d отмечает, что принимается во внимание дисциплина d, действующая в системе. Предполагается, что в СМО в каждый момент t дисциплина решает, какая из следующих альтернатив должна быть применена к пакету, находящемуся в системе: 1) начать передачу (обслуживание) пакета в момент t; 2) хранить пакет в буфере до момента t +1; 3) сбросить (потерять) пакет в момент времени t. Математическая модель самоподобного трафика позволяет проводить имитационное моделирование с заданными размерами буферной памяти и пропускной способности канала. Исследования, проведенные в работе, показали, что при загрузке системы на 80-90%, чтобы потери были минимальны, размер буфера должен превышать интенсивность трафика в сотни раз.

Результаты численного эксперимента позволяют для известного значения пропускной способности C и полученных параметров входного потока данных определять средний размер буферной памяти B , необходимый для нормального прохождения (потери данных не превышают 10%) участка трафика через коммутатор:

B = f(C,X,F,H). (1)

Для обобщения результатов при выполнении исследований были использованы следующие нормированные параметры: отношение параметра Фано к интенсивности трафика F/X, отношение среднего значения буфера к интенсивности B/X и отношение интенсивности трафика к пропускной способности (загрузка системы) X/C.

На рис.2 показана зависимость среднего размера буферной памяти B/X, необходимого для нормального прохождения участка трафика через узел связи, от параметра Фано при изменении загрузки системы от 50% до 90% при постоянном показателе Херста H =0,8.

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

Алгоритм прогнозирования перегрузки

В работе предложен следующий алгоритм прогнозирования перегрузки буфера путем мониторинга входной нагрузки (рис. 3):

1) во временном ряде, который соответствует трафику поступающему на вход коммутатора, выделяем окно X фиксированной длины T ;

2) находим оценки интенсивности X , параметра Фано F и показателя Херста H для участка трафика в выделенном окне;

3) в соответствии с полученной зависимостью (1) формируем прогноз размера буферной памяти Buf , необходимого для нормального прохождения данного участка трафика через коммутатор;

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

5) передвигаем окно X длины N вперед на заданную величину сдвига AT ;

6) осуществляем прогноз следующего значения Buf и т.д.

Выводы

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

Список литературы

1. Столлингс В. Современные компьютерные сети. СПб.: Питер, 2003 - 783 с.

2. Митилино С. Фрактальная катастрофа TCP/IP // Компьютерное Обозрение, 2001.

3. Олифер В.Г., Олифер Н.А., Компьютерные сети. Принципы, технологии, протоколы. издание: 3-е , СПб.: Питер, 2006. - 958 с.

4. Vern Paxson and Sally Floyd, Wide-Area Traffic: The Failure of Poisson Modeling IEEE/ACM Transactions on Networking, Vol. 3 No. 3. - Рр. 226-244, June 1995.

5. Цыбаков Б.С. Модель телетрафика на основе самоподобного случайного процесса // Радиотехника. - 199. - № 5. - С. 24-31

6. Leland W.E., Taqqu M.S., Willinger W., and Wilson D. V. On the self-similarnature of ethernet traffic // IEEE/ACM Transactions of Networking, 2(1), 1994. - P. 1-15

7. Norros I. The Management of Large Flows of Connectionless Traffic on the Basis of Self-Similar Modeling // ICC '95, IEEE International Conference on Communications. - Seattle, 1995.

8. Ryu B.K. Fractal Network Traffic: From Understanding to Implications. Ph.D. thesis. - Columbia University, 1996. -143 p.

9. Кириченко Л.О., Радивилова Т.А. Исследование влияния самоподобия трафика при проектировании фрагмента сети // Нов1 технологи. - 2007. - №1-2. - С. 124-129.

Поступила в редколлегию 12.10.2007

Рецензент: д-р техн. наук, проф. С.Г. Удовенко, Харьковский национальный университет радиоэлектроники, Харьков.