UNIX-way и генератор заданий по архитектуре компьютерных сетей

Прошлой зимой на нашей любимой кафедре произошло одно замечательное событие — курс проектирования компьютерных сетей был переформирован, в результате чего вместо одного семестра практических занятий образовались два семестра занятий лабораторных. С одной стороны, оба изменения — и качественное, и количественное — означали, что студенты получат больше времени на освоение предмета, а также занятия будут индивидуальными, а не групповыми — думать, вполне вероятно, придётся всем, а не «ядру» группы в четыре-пять человек. С другой стороны, это означало, что придётся разрабатывать эти самые индивидуальные задания, да так, чтобы они были все отличались друг от друга.

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


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

• максимальное количество узлов в сети — 8;
• максимальное количество линков, выходящих из узла — 3;
• максимальное количество линков в сети — 12.

Немного скучных технических деталей

Сам генератор состоит из генератора собственно графа сети, генератора непересекающихся диапазонов адресов, и генератора визуализации.

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

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

Как известно, в Tcl практически любой объект представим в виде текстовой строки. Не являются исключением и словари. Словарь в Tcl — список, содержащий пары «ключ» — «значение», а любой список, в свою очередь может быть записан в виде строки, в которой элементы списка разделены пробелами. Такая структура немного напоминает JSON, но имеет несколько более простую структуру.

Таким образом, использовать словарь как список связей между узлами сети: ключом является номер узла, а значение представляет собой список узлов, с которыми данный узел связан. Каждый из элементов, в свою очередь, также является словарём, в котором по умолчанию содержится один элемент, в котором ключ — номер узла, а значение пусто. Вышесказанное можно проиллюстрировать следующим образом:



Соответствующий словарь будет выглядеть так:

0 {
    1 2
    3 4
    5 6
    7 {
        8 2
        3 {}
    }
}

Преимуществом такой структуры является возможность выборки по пути к элементу: вызов

[dict get $tree 0 7 8]

позволяет «заглянуть» в список связей узла 8.

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

К слову, о генераторах. В первом приближении скрипт давал очень странные результаты, после чего я решил просмотреть результаты нескольких вызовов генератора случайных чисел. Когда я получил нечто вроде: 2 9 0 1 5 7 7 7 4 7 7 7..., мне пришлось слегка модифицировать процедуру getrandom, чтобы она не возвращала одинаковые значения подряд. Вероятно, знатоки генераторов случайных чисел закидают меня чем-нибудь, но такой подход в данном применении себя оправдал.

Ещё одним преимуществом выбранного способа хранения графа была простота проведения проверки на наличие всех узлов в сети — из текстового представления графа выбрасывались все скобки, в результате чего граф превращался в плоский список, после чего удалением повторяющихся элементов ([lsort -uniq]) из него легко получить список всех узлов графа.

Когда сеть сгенерирована, всё тот же скрипт на Tcl сохраняет граф в формате Graphviz dot, который преобразуется в EPS, пригодный для «скармливания» LaTeX'у. При выводе графа в dot в явном виде задаётся шрифт CMR12, чтобы в итоговом документе не было разнообразия шрифтовых гарнитур. Здесь, однако, кроется одна досадная неожиданность: в созданный таким образом EPS'е, естественно, не будут внедрены шрифты, но при итоговой сборке документа в выходной файл будут включены только те символы, которые используются LaTeX'ом. Поэтому для корректного отображения надписей пришлось в этот самый LaTeX'овый исходник добавить стоящую за полями бумаги букву «N».

Для сборки документа используется традиционный «конвейер» из LaTeX, dvips и ps2pdf.

«Дирижирует оркестром» небольшой Makefile, вызывающий скрипты, а также вышеназванные инструменты.

Что получилось в итоге

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



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

Кроме того, к заданиям прилагалась страничка с напутствием, а также пожеланием осознать, зачем же нужна динамическая маршрутизация :)

Реакция студентов на тысячестраничный PDF была примерно: «Эээ?!» Одно из предложений студентов меня повеселило: «А если я напишу программу, которая разбирает конфигурацию сети из этого PDF, а потом генерирует конфигурацию для Cisco, это будет засчитано?»

Генератор, который я выше описал, замечательно служит примером того, как можно, стыкуя различные программы между собой, получать желаемый результат без мучительного изобретения велосипедов. Конечно, немного повелосипедить пришлось, но всё было бы гораздо хуже, не будь в моём распоряжении таких замечательных инструментов, как TeXLive, Graphviz, а также моих любимых скриптовых языков.

В общем-то, это всё, что мне хотелось рассказать. Спасибо за внимание.

P. S. Интересующиеся могут найти исходные коды проекта по адресу: http://bitbucket.org/andrew_shadoura/netgen.