Оригинальное название статьи - Sally Floyd. Validation Experiences with the NS Simulator.
Оригинальное расположение статьи - http://www.icir.org/floyd/papers/NIST.Apr99.pdf

Опыт проверки на правильность сетевого симулятора NS Simulator

Салли Флойд (Sally Floyd)
19 апреля 1999 г.

Краткий обзор

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

1. Современные сетевые имитационные модели или средства

Я использовала имитации как ключевой компонент моих сетевых исследований с тех пор, как я начала работать в этой области около десяти лет назад. Пока некоторые работы по имитации (напр., по синхронизированным маршрутизируемым сообщениям или по надежному масштабируемому широковещанию (Scalable Reliable Multicast) выполнялись на специализированных имитаторах, которые я написала для исследования частичных результатов, большинство из моих имитаторов были сделаны на основе NS Network Simulator и предшествующих имитаторов (NS-1, еще раньше - 'tcpsim' и его младшие версии), разарботанных Стивом Маккейном (Steve McCanne) и мной в LBL. Симулятор NS [NS95] был построен на основе сетевого имитатора, разработанного Стивом Маккейном в 1990 г., и основывается на сетевом имитаторе REAL. Несколько лет Стив и я были единственными пользователями этого имитатора. Я использовала имитатор для исследования таких результатов, как динамика TCP, управление очередями RED, явное уведомление о накоплении, и планирование CBQ, и была ответственна за компоненты этих модулей в имитаторе. Сетевой имитатор LBL Network Simulator (написанный на C) сначала был основан на сетевом симуляторе NS-1 (написанном на C++ и Tcl и общедоступном с 1995 г.), а потом на NS-2 (окончательная версия которого была сделана 1997 г.). За последние три года разработчики NS начали работать вместе с ISI/USC, Xerox PARC, LBNL, Xerox PARC, и UC Berkeley над проектом VINT, и NS стал широко использоваться научном сообществе, занимающемся сетями. Кроме использования NS в моих собственных исследованиях, я, как член проекта VINT, вместе с разработчиками NS также была заинтересована в более общем использовании в научном сообществе, занимающемся сетями.

2. Современные техники проверки на правильность

Радж Джейн [Jai91] определил проверку на правильность как "убеждение, что предположения, использующиеся при разработки модели, обоснованны, и, если они правильно заданы, модель будет выдавать результаты, близкие к наблюдаемым в реальных системах", и определил проверку зависимой от правильности реализации. В этой статья я буду обсуждать и проверку на правильность, и верификацию.

Развивающийся набор тестов проверки на правильность для NS существовал, начиная с первого поколения сетевого имитатора LBL Network Simulator в 1990 г. Я была заинтересована в динамике, присущей и лежащей в основе у алгоритмов TCP для непрерывного контроля накопления. Я создала набор тестов для проверки на правильность для собственного использования, чтобы проверить, что механизм контроля накопления в имитаторе соответствует спланированной модели (не для проверки, что механизм контроля накопления соответствует некоторой реальной реализации этой модели). Оглядываясь назад, могу сказать, что это подтвердило мои предположения. Например, реальная реализация механизма увеличения окна в Reno TCP включала в себя существенный недостаток - добавление увеличивающегося фактора для увеличения окна при предотвращении накопления; целью моих исследований был не обзор поведения этих существующих реализаций TCP, а обзор динамики, присущей и лежащей в основе механизмf контроля накопления.

Некоторые из моих исследований затрагивали разработки и анализ протоколов и механизмов, для которых не было реальных аналогов. Примером этого служат активное управление очередью RED, явное уведомление о накоплении (Explicit Congestion Notification), планирование CBQ, и опция выборочного подтверждения (Selective Acknowledgement) для TCP. Таким образом, для этих моделей тесты проверки на правильность служили для проверки, что модели в имитаторе показывают поведение, ожидаемое от модели, лежащей в основе.

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

Тесты проверки на правильность, которые я написала для NS, не являются полными. Например, я уверена, что некоторой код в модулях не выполнялся или проверялся никакими тестами на правильность, и, естественно, множество комбинаций событий не подвергались проверке ни в одном из тестов. Изначально, при каждом добавлении нового параметра или поведения, я хотела также добавлять тест проверки на правильность для проверки, что этот параметр работает так, как я планировала; однако, многие из этих тестов проверки на правильность не могли пережить многочисленные изменения лежащего в их основе симулятора (от изначального сетевого симулятора LBL к tcpsim, к NS-1, к NS-2, и т.д).

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

Я написала короткую статью, обсуждая некоторые из тестов проверки на правильность TCP в 1994 г. (до того, как имитатор был сделан общедоступным) [Flo95], в ответах на вопросы из писем о том, как другие исследователи проверяют из реализации TCP в их собственных имитаторах. Статья описывает базовые тесты, проверяющие, что стартовое замедление (Slow-Start) Tahoe TCP, избежание накопления (Congestion Avoidance), и механизм быстрой повторной трансляции (Fast Retransmit), механизм быстрого возврата (Fast Recovery) Reno TCP, и механизм SACK TCP работают в имитаторе так, как планируется. Остальные документы описывают тесты проверки на правильность для механизма планирования CBQ [Flo97b], для механизма управления активными очередями RED [Flo97c], для механизма явного уведомления о накоплении [Flo98], для двустороннего TCP [FFH97], и для механизма контроля накопления TCP [FF96]. Я также написала несколько тестов проверки на правильность для NS (напр, для большей инициализации окон TCP, и для таймеров повторной передачи TCP), которые не описаны в сопровождающих документах, кроме как коротким текстовым файлом, распространяемым вместе с имитатором.

3. Самооценка эффективности техник проверки на правильность

Есть два ключевых результата при определении модели, используемой для исследования Интернет. Первый - Интернет по сути трудно характеризовать, ему присуща неоднородность и быстрое изменение топологии, характеристик каналов связей, протоколов, механизмов маршрутизации, приложений и смешанного трафика [PF97, Flo97a]. Второй ключевой результат состоит в том, что исследователи сети предлагают или анализируют протоколы или механизмы для будущего Интернета, причины для управления имитацией часто нужны для понимания возможной значимости этих предложений в будущей эволюции Интернет. То есть, мы может интересоваться не поведением этих протоколов в настоящем Интернете, а их поведением в Интернет таком, каким он может стать через несколько лет.

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

Одним из примеров неподходящего использования моделей является множество документов, предлагающих внести радикальные изменения в инфраструктуру Интернета для решения проблем, вызываемых недостатком надежности Reno TCP при большой потеке пакетов из окна данных. Есть первое исправление этой проблемы Reno TCP - оно заключается в небольшом изменении алгоритма контроля накопления (напр., NewReno bkb SACK TCP). Новые реализации TCP находятся в процессе развертывания в глобальном Интернете. Сейчас разрабатываются другие изменения, которые минимизируют проблему Reno TCP, связанную с большими потерями пакетов при использовании управления активной очередью (напр., RED). Я рационально доверяю эффективности техник проверки на правильность для моих собственных исследований. Мои собственные исследования используют NS не для численного сравнения между конкурирующими механизмами, а для обзора и иллюстрации механизмов, предложенных для будущего Интернета. Поведение, иллюстрируемое и обозреваемое с помощью имитаторов, также может быть объяснено с помощью непосредственного анализа, включающего фазовый эффект TCP (значительная зависимость пропускной способности TCP при малых изменениях параметров имитации) [FJ92]; зависимость между поведением между пропускной способностью TCP и временем полного обхода или количеством накопленных шлюзов; и ухудшение производительности TCP через ATM из-за большого скопления при отсутствии отменяемых политик. Для исследования таких проектов, пока я требовала, чтобы имитация проходила без ошибок, я верила, что результаты моих исследований надежны, и не основаны на неправильной имитации.

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

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

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

Предупреждение является достаточно серьезным, и те только как формальное отказ от ответственности как разработчиков NS. Тесты проверки на правильность являются не только средством для использования его разработчиками для минимизации первичных ненайденных ошибок, а также являются средством для пользователей для самостоятельного понимания моделей, реализованных имитатором, и для идентификации тех аспектов моделей, заключенных в тестах проверки на правильность. Чтобы помочь пользователям при решении этой задачи, модель и реализация описаны в документации к NS [FV99]. К сожалению, лежащая в основе модель не является формально или полностью специфицированной, и вполне может изменяться со временем. Во многих случаях, есть набор опций в терминах лежащей в основе модели: односторонняя реализация TCP, например, отражает упрощенную лежащую в основе модель односторонней передачи данных в пакетах фиксированного размера, без специализированных пакетов SYN или FIN. Расширенная двусторонняя реализация TCP позволяет двустороннюю передачу данных, задавать совокупность размеров пакетов данных без одиночного соединения, а также устанавливать и завершать соединение с помощью пакетов SYN и FIN. Важно, чтобы пользователь понимал модель, лежащую в основе его собственных имитаций.

4. Ключевые сложности при попытке проверки модели на правильность

Ключевая сложность определяется, когда нужно добавить поведение к тестам проверки на правильность. Некоторые описанные проблемы в NS не проверяются ни одним из тестов проверки на правильность. Примером этого является описанная проблема в поведении TCP ECN с задержкой при получении пакета ACK; эта частичная проблема была описана пользователем NS, и соответствовала неправильной лежащей в основе модели.

Другие описанные проблемы были для поведения, при котором на имитаторе модель работала корректно, а ошибка обнаруживалась на одной из модификация имитатора (от более раннего имитатора LBL к tcpsim, к NS-1 и, наконец, к NS-2 ). Две модификации от более раннего имитатора LBL к tcpsim, и от tcpsim к NS-1, требовали, чтобы тесты проверки на правильность были полностью переписаны в новом формате, и многие тесты проверки на правильность не пережили все преобразования. Модификация от NS-1 к NS-2, как условие, включает в себя то, чтобы NS-2 мог запустить скрипты для проверки на правильность из NS-1 в режиме обратной совместимости, без полного переписывания всех скриптов для проверки на правильность в новый формат.

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

Ccылки

[FF96] K. Fall and S. Floyd. Simulation-based comparisons of tahoe, reno, and sack tcp. ACM Computer Communication Review, Jul. 1996. URL http://www-nrg.ee.lbl.gov/nrg-papers.html.

[FFH97] K. Fall, S. Floyd, and T. Henderson. Ns simulator tests for reno fulltcp. URL http://www.aciri.org/floyd/papers/fulltcpsims.ps, Jul. 1997.

[FJ92] S. Floyd and V. Jacobson. On traffic phase effects in packet-switched gateways. Internetworking: Research and Experience, 3(3):115-156, Sep. 1992.

[Flo95] S. Floyd. Simulator tests. URL http://wwwnrg. ee.lbl.gov/nrg-papers.html, Jul. 1995.

[Flo97a] S. Floyd. Internet simulations: Issues in defining the model. URL http://www.aciri.org/floyd/talks/sf-dimacs-97.ps.Z, Oct. 1997.

[Flo97b] S. Floyd. Ns simulator tests for class-based queueing. Unpublished draft, Apr. 1997. URL ftp://ftp.ee.lbl.gov/papers/cbqsims.ps.Z.

[Flo97c] S. Floyd. Ns simulator tests for random early detection (red) queue management. URL http://www.aciri.org/floyd/papers/redsims.ps.Z, Apr. 1997.

[Flo98] S. Floyd. Ecn implementations in the ns simulator. URL http://www.aciri.org/floyd/papers/ecnsims.ps, Dec. 1998.

[FV99] K. Fall and K. Varadhan. Ns notes and documentation. Technical report, 1999. URL http://wwwmash. cs.berkeley.edu/ns/ns-documentation.html.

[Jai91] R. Jain. The Art of Computer Systems Performance Analysis. John Wiley and Sons, Inc., 1991.

[NS95] Ns (network simulator), 1995. URL http://wwwmash. cs.berkeley.edu/ns/.

[PF97] V. Paxson and S. Floyd. Why we don't know how to simulate the internet. Proceedings of the 1997 Winter Simulation Conference, Dec. 1997. URL http://www.aciri.org/floyd/papers/wsc97.ps.