И на блохе, как говорит наука,
Есть блохи меньшие, что кровь ее сосут;
А тех кусают еще меньшие букашки,
И так до бесконечности продолжить можно.
Джонатан Свифт
Обычно с фракталами у нас ассоциируются красивые цветные картинки, довольно часто украшавшие страницы околокомпьютерных журналов конца 80-х — начала 90-х годов. Тогда мания удивительных математических построений с бесконечно тонкой структурой охватила всех — от профессоров математики до системных программистов. До сих пор утилиты визуализации множеств Жюли (Julie) и Мандельброта (Mandelbrot) частые гости в различных сборниках бесплатного ПО. Кто бы мог подумать, что спустя два десятилетия после открытия самоподобных (self-similar) объектов их свойства будут обнаружены у обыкновенного Ethernet-трафика? Несмотря на кажущуюся абстрактность, это не досужие размышления теоретиков, а вполне реальная проблема современных высокоскоростных сетей.
Самоподобие — что это?
Когда мы говорим о сетевом трафике, то под самоподобием подразумевается повторяемость распределения нагрузки во времени при различных масштабах. Это означает, что если мы нарисуем график зависимости плотности информационного потока от времени, взяв за единицу измерения секунду, минуту, час и так далее, то каждый раз получим практически одинаковые диаграммы. На языке математики это звучит следующим образом. Если набор значений самоподобной функции (т. е. проявляющей признаки самокорреляции) разделить на равные группы, а затем просуммировать значения внутри групп, то набор сумм будет подчиняться той же самой корреляционной функции, что и исходные данные.
Вначале эту особенность удалось заметить в сетях Ethernet. После того как данный феномен был доказан, множество исследователей занялись проблемой самоподобия сетевого трафика. Например, сразу после изобретения WWW появились публикации и на тему повторяемости трафика в этой системе. Удалось определить, что возможная причина такого странного эффекта — в особенностях распределения файлов по серверам, их размерах, а также в типичном поведении пользователей.
А в ходе недавних исследований, проведенных под руководством Фенга (W. Feng) и Тиннакорнсрисуфа (P. Tinnakornsrisupha) при поддержке Лос-Аламосской национальной лаборатории (Los Alamos National Laboratory), была поставлена под сомнение основа основ глобальной сети — протокол TCP. Оказалось, что изначально не проявляющие свойств самоподобия потоки данных, пройдя обработку на узловых серверах и активных сетевых элементах, начинают подавать ярко выраженные признаки самокорреляции. Особенно сильно этот эффект заметен в высокоскоростных сетях. Эксперимент проводился с использованием ESnet (Energy Sciences network) — мощной сети, соединяющей национальные лаборатории в городах Лос-Аламосе (LANL) и Сандиа (SNL). Однако если прогнозы относительно радикального повышения производительности пользовательских решений "последней мили" и, соответственно, базовых каналов провайдеров сбудутся, то очень скоро проблема самоподобия сетевого трафика из разряда теоретических перейдет в категорию насущных.
Самоподобие — почему это плохо?
Логичный вопрос, на который существует безжалостный и не менее логичный ответ. Современные сети построены на основе принципа "усреднения". Согласно статистике, множество потоков данных со случайными вариациями плотностей дадут в результате некий усредненный трафик. К сожалению, этот идеалистический подход не работает: сети, построенные на базе TCP/IP, склонны к проявлению мощных пиковых выбросов. Такие своеобразные, локализованные во времени "столпотворения" (congestions) вызывают значительные потери пакетов, даже когда суммарная потребность всех потоков далека от максимально допустимых значений. Итак, автокорреляция во времени непосредственно сказывается на эффективности использования пропускной способности сетей.
Рассмотрим, как по-своему "плохо" отражается "фрактализация" на двух наиболее известных вариантах реализации протокола TCP: Reno и Vegas. Последний, предложенный в 1994 г. Лоуренсом Бракмо (Lawrence S. Brakmo), Шоном О’Мэлли (Sean W. O’Malley) и Ларри Петерсоном (Larry L. Peterson), называют наиболее прогрессивным, он должен стать заменой широко распространенному сегодня TCP Reno. Однако, как мы увидим далее, его совершенство не распространяется на явление самоподобия.
 |
 |
| Рис. 1 |
Прежде чем приступить к описанию проведенных измерений и обсуждению результатов, мы познакомимся с условиями эксперимента, а именно — со структурой "подопытной" сети (рис. 1). Как уже говорилось выше, в исследованиях участвовали лаборатории Лос-Аламоса и Сандиа, поэтому источники эмулированного трафика располагались в локальных сетях (100 Mbрs Ethernet) данных организаций. Каждая из них взаимодействует со своим маршрутизатором FDDI/ATM Cisco 7507, а они, в свою очередь, подключены к центральному ATM-коммутатору Fore ASX-200BX, расположенному в г. Альбукерке. Производительность соединений между коммутатором и маршрутизаторами составляет 155 Mbрs. Кроме этого, коммутатор имеет выход в Internet через такой же канал 155 Mbрs. Во время второй стадии измерений конфигурация сети была несколько изменена: пропускная способность всех внешних соединений повышена до 622 Mbрs, а локальные сети лабораторий апгрейдированы до 1 Gbрs, коммутаторы заменили на Cisco 7512 с большим размером буфера.
Суть проблемы заключается в методе предотвращения перегрузки сети. Как вы, наверняка, знаете, надежность доставки пакетов гарантируется механизмом подтверждений (ACK). Получатель для каждого принятого пакета отсылает своему "респонденту" сообщение, содержащее номер следующего ожидаемого им пакета. Протокол IP не гарантирует соблюдения последовательности доставки и синхронности передачи данных в обоих направлениях. Следовательно, единственным способом избежать длительных простоев системы в ожидании прохождения пакета и подтверждения является использование так называемых "окон". Высылающая сторона, не ожидая ничего взамен, передает сразу несколько пакетов (их количество определяется величиной или размерами окна). Копии отосланных пакетов помещаются в очередь повторной передачи, и для каждого из них "запускается" таймер, отсчитывающий определенный промежуток времени. Как только появляется подтверждение приема от получателя, все пакеты, для которых оно было сгенерировано, удаляются из очереди. Таким образом, до повторной отправки дело доходит только в случае неполучения подтверждения в указанный промежуток времени (он вычисляется динамически на основании замеров времени прохождения пакетов).
TCP Reno предусматривает варьирование размеров окна. Идея, конечно, заключается в достижении максимально возможного его размера, так как это снижает сетевые затраты на обработку подтверждений. Процесс увеличения состоит из двух стадий. Первая называется "медленный старт" (slow start), в ходе которой каждое принятое подтверждение приводит к увеличению длины передающего буфера (окна) на один пакет. Цикл продолжается вплоть до перехода границы, т. е. достижения некоего условного значения. После этого TCP Reno входит в состояние "избежания столпотворения" (congestion avoidance). Далее шаг наращивания окна снижается до величины 1/<текущая длина>. Любая потеря пакета приводит к переоценке отсылающей стороной своих возможностей: длина окна сбрасывается в единицу, а граница медленного старта устанавливается на половинное значение достигнутой в момент сбоя длины буфера, и все начинается сначала.
Когда детектирование потери происходит с помощью механизма быстрой повторной передачи (fast retransmit and fast-recovery mechanisms), границе медленного старта и текущему размеру окна присваиваются одинаковые значения. Как и в предыдущем случае, они равняются половине текущего размера окна. Быстрая повторная передача происходит, если система получает сразу несколько подтверждений с одинаковым номером следующего ожидаемого пакета. Это означает, что, хотя какой-то пакет из серии и был утерян или искажен, все последующие дошли до получателя в нормальном состоянии. В такой ситуации передающая сторона может сразу отправить копию требуемого пакета (и только его), не ожидая истечения времени по таймеру.
В ходе экспериментов TCP Reno показал себя далеко не с лучшей стороны. А высокоскоростное соединение во второй конфигурации вообще сбило его с толку. Проблемы с пропускной способностью (saturation) для него начинаются после подключения 20—25 клиентов. Однако при эмуляции потока данных всего от 8 клиентов стали проявляться резкие скачки плотности трафика. Дальше — хуже. Даже не добравшись до зоны насыщения, Reno по необъяснимым на первый взгляд причинам уже теряет пакеты. Примерно 0,26% данных не достигают места назначения. На скорости передачи 155 Mbрs эти мизерные проценты выливаются в 403 Kbрs искаженной информации. Во второй конфигурации при увеличении числа клиентов до 50 и более можно было наблюдать феноменальные рост частоты потерь пакетов — до 5%, что составляет уже 31 Mbрs для использованного канала 622 Mbрs.
По мнению исследователей, низкая эффективность протокола вызвана сильными флуктуациями размеров буфера-окна. Когда несколько соединений одновременно начинают "пробовать на прочность" канал, непомерно раздувая свои окна вплоть до первой потери пакета, создаются все условия для проявления автокорреляции. Система входит в своеобразный "сетевой резонанс", что не сулит ничего хорошего. Более того, увеличение размеров окна происходит очень медленно. Чтобы восстановить уровень производительности, достигнутый перед потерей пакета, требуется чересчур много времени.
В опубликованной исследователями статье приводится пример соединения с латентностью, выраженной параметром RTT (Round-Trip Time — время обращения), равным 100 мс. Допустим, что в момент потери пакета размер окна составлял 50 Mb, тогда в наилучшей ситуации (сработал механизм быстрой повторной передачи) на восстановление производительности соединения потребуется (1/2 50 Mb)/(1500 x x 8 b) = 2500 RTT. Умножив итоговую цифру на длительность одного RTT, получаем внушительные ~3,5 минуты. Это говорит только об одном — большую часть времени пропускная способность канала используется неэффективно (что равнозначно дополнительным потерям пакетов). А теперь добавим синхронность действий потоков, которые все вместе начинают наращивать буфера, одновременно теряют пакеты в образовавшемся заторе и, как по команде, выполняют откат. Довольно забавная ситуация.
В отличие от своего старшего и явно неудачного брата, TCP Vegas, как и одноименный город, выявляет признаки относительного благосостояния. Во всяком случае, в первом приближении. Его схема регулирования окна гораздо более совершенна и использует в качестве основного показателя параметр RTT. Вначале, как и в случае с Reno, идет процесс медленного старта. Однако здесь он еще более медленный, поскольку увеличение размера буфера на единицу происходит только после успешного прохождения двух пакетов. По достижении определенной границы стек протоколов входит в состояние избежания столпотворения.
Поведение системы определяют четыре параметра: a, b, минимальное значение RTT и текущее значение RTT. Разделив текущий размер окна на минимальный RTT и текущий RTT, Vegas отслеживает разницу между этими двумя значениями. a и b — это просто определенные числа, которые нормируются на размер окна. Пока вычисленная разница меньше нормированного a, буфер увеличивается. Когда она попадает в диапазон между a и b, ничего не меняется. В случае, если разница превысит нормированное значение b, окно начинает уменьшаться. Балансируя, подобно опытному эквилибристу, Vegas умудряется "донести свой морс", не "расплескав ни капли".
 |
 |
| Рис. 2 |
В ходе эксперимента проблемы с пропускной способностью, обеспечиваемой протоколом, начинались на уровне загрузки, генерируемой 30 клиентами. Но, несмотря на это, даже 60 клиентов не смогли заставить его "уронить" хотя бы один пакет — график количества потерянных данных плотно "прижался" к нулевой отметке. Результаты измерений для обеих разновидностей протокола TCP показаны на рис. 2.
Превосходство более нового варианта реализации TCP было очевидно для ученых и ранее, однако не для провайдеров и коммуникационных компаний. Reno по-прежнему удерживает пальму своего сомнительного первенства по количеству инсталляций в мире.
"Степень самоподобия"
"Блеск", с которым Vegas справился с подстроенными каверзами дотошных экспериментаторов, ничего не означает — автокорреляция достаточно выразительно проявила себя в случае применения обоих вариантов протокола TCP. Чтобы оценить "степень самоподобия", использовались два показателя: c.o.v. и H. Первый из них расшифровывается как coefficient of variation и представляет собой величину среднего отклонения плотности трафика, разделенную на среднее значение этого самого трафика. Малое c.o.v. говорит об отсутствии большого количества выбросов и, следовательно, о справедливости теоремы о "статистическом сглаживании" множества объединенных потоков.
Параметр H (Hurst parameter) напрямую связан с корреляционной функцией и варьируется в пределах от 0,5 до 1. Чем ближе к единице, тем более сильная корреляционная функция оказывает влияние на трафик. Чтобы облегчить себе задачу, исследователи заставили клиентов формировать не беспорядочный поток данных, а подчиняющийся закону распределения Пуассона. Говоря проще, изменяли задержки между отсылкой пакетов таким образом, чтобы итоговое распределение плотности соответствовало закону Пуассона.
Для такого "идеологически выдержанного" трафика очень просто было вычислить теоретическое значение c.o.v., которое имело бы место быть, кабы не самоподобие. К нашему огорчению и к вящей радости Фенга и Тиннакорнсрисуфа, величина реально полученного параметра c.o.v. для 60 клиентов даже в первой конфигурации превысила теоретическое значение на 300% в случае применения TCP Reno и на 40% — при использовании TCP Vegas. После модернизации сети c.o.v. вырос относительно теоретически рассчитанного на 642 и 457% соответственно.
Если обратиться к параметру H, то его значение для TCP Reno иногда даже зашкаливало за 1, а для TCP Vegas практически вплотную подобралось к ней уже при 40 клиентах в первом варианте конфигурации. А ведь, согласно теории для потоков, изменяющихся по закону Пуассона, параметр Харста должен равняться 0,5.
Вывод очевиден: заведомо не проявляющий признаков самоподобия трафик, пройдя через стек протоколов TCP/IP, модулируется последним и превращается в самый настоящий "сетевой фрактал". Однако если цветные фракталы Мандельброта и Жюли, размещенные на глянцевых страницах популярных изданий, радуют глаз, то скрытые от наших органов чувств самоподобные сетевые потоки, в буквальном смысле пожирающие полезные данные, не представляют собой ничего приятного. Но более, чем описанные в данном материале проблемы, огорчает пугающее невежество коммерческих и научных организаций, продолжающих активное использование TCP Reno, несмотря на все его недостатки. При том, что альтернатива существует уже достаточно длительное время. Видимо, в ближайшем будущем, с приходом широкополосных коммуникаций, им и, к сожалению, нам придется испытать на себе всю глубину их недальновидности.