Баканов В.М. Сети ЭВМ и телекоммуникации (1086235), страница 8
Текст из файла (страница 8)
Определить минимум из этих расстояний – наименьшее суть R(a,b,d)=5,что и позволяет принять в качестве частичного минимального пути [a,b,d].В случае двух или более одинаковых значений можно взять любое (обычно берется первое).5. К списку вершин кратчайшего пути добавить только что определенныевершины b,d.6. Повторять пункты 2 ÷ 5 алгоритма, принимая в качестве исходной последнюю из списка вершин частичного кратчайшего пути (в рассмотренномслучае это вершина d) до тех пор, пока не будут проанализированы всевходящие в вершину n ребра(для графа на рис.5.1 их 3).Т.о. при каждой итерации продвигаемся к конечной вершине надве вершины (на два ребра), каждый раз выбирая минимум путина протяжении смежных ребер.После получения списка вершинкратчайшего пути его длина определяется примитивным суммированием метрик ребер (напр.,дляграфариc.5.1имеемminR (a,b,d,g,h,n)=12.Пользовательский интерфейспрограммы OSPF приведен нарис.5.3.
В окне ввода описанияграфа каждое ребро задаетсястрокой, где первые два слова –имена определяющих ребро вершин (длина имени не более 10символов), далее - метрика ребра(целое число); данные разделяются пробелами. Т.к. все ребра являются ненаправленными, порядок указания определяющих их Рисунок 5.2 — К описанию алгоритма Дейкстры нахождения минимального пути ввершин несущественен. Главноеграфе.меню является стандартным, вычисления начинаются выборомварианта ‘Calculate’, проект и результаты расчета могут быть сохранены в39файл для последующего использования, для получения дополнительной информации рекомендуется использовать вариант ‘Help’.
В применении к компьютерным сетям аналогом понятия ‘вершина’ является ‘узел’ (‘сетевойузел’), ‘ребро’ – ‘путь’ (‘межузловой путь’, ‘линия связи’).5.4 Необходимое оборудование – IBM PC-совместимая ЭВМ, предустановленные ОС Windows и программа OSPF.5.5 Порядок проведения работы. Студенты получают индивидуальныеварианты топологии сети (сеть представляется аналогично рис.5.1),выполняют описание графа в виде списка инцидентных вершин и метрики,вводят данные в программу OSPF и сохраняют проект задания, проводятрасчет и анализируют полученные результаты. По указанию преподавателямоделируется изменение сети (путем уничтожения части путей илидобавления новых) и операция поиска кратчайшего маршрута повторяется.Рисунок 5.3 — Пользовательский интерфейс программы OSPF.40Оформление отчета по работе.
В отчет вносится визуальное представление сети, полученный список инцидентных вершин, результаты маршрутизации (список составляющих минимальный путь вершин и результирующаядлина пути) для заданной серии расчетов.5.6 Вопросы для самопроверки.• В чем заключается суть процесса маршрутизации компьютерной сети? Какие обязательные процедуры должен включать процесс маршрутизации?• Какие алгоритмы маршрутизации используются в современных сетях? Какие из них более применимы к относительно небольшим и крупным сетям?• По какой причине для математического моделирования компьютерной сетиудобно использовать представление ее в виде графа?• Почему такой граф является взвешенным? Неориентированным? В какомслучае подобный граф может являться ориентированным?• Каким образом в данной модели можно учесть величину латентности покаждому выходному порту маршрутизатора?• Почему веса ребер должны быть неотрицательными? Каков физическийсмысл нулевой метрики ребра?416 Лабораторная работа 6.
Изучение и настройка аппаратной и программной поддержки сетевого обеспечения многопроцессорной вычислительной системы на основе Linux-машин6.1 Цель работы – приобретение практических знаний и навыков в настройке и рациональном использовании сетевого обеспечения многопроцессорной вычислительной системы (МВС) с распределенной памятью архитектуры MPP (Massively Parallel Processing, вычислительный кластер) на основе Linux-машин.6.2 Теоретические основы. Системное ПО многопроцессорных вычислительных систем (МВС) в подавляющем большинстве строится на основе сетевой ОС Linux как наиболее надежной в эксплуатации и гибкой в настройке (напр., допускающей эксплуатацию в режиме управления с команднойстрокой без использования лишнего в данном случае графического интерфейса). Значительная вариативность настройки Linux позволяет создавать на ее основе МВС, в которыхсотни и тысячи вычислительных узлов функционируют совместно [6], обеспечивая огромную производительность(конечно, при использовании специальных приемов алгоритмизации и программирования).Дальнейшее описание соответствует принципам одного изпервых высокоуспешных кластерных разработок - проектуBEOWULF (http://www.beowulf.org, название дано в честь героя древней скандинавской саги, см.
рис. справа).Основные положения проекта:• В качестве вычислительных узлов (ВУ) используются широкораспространенные (и готовые к употреблению) блоки - системные платы (motherboard) современных ПЭВМ с установленными процессорами (часто двухили четырехпроцессорные или с двух- или четырехядерными процессорами) и массивами оперативной памяти (ОП), причем загрузка ОС осуществляется со стандартных жестких дисков (бездисковые вычислительныеузлы с загрузкой по сети используются редко, т.к. для полноценной работы ОС все же необходим своппинг – возможность временного сброса части ОП на жесткий диск).
Практически всегда на каждом ВУ в данный момент времени выполняется одна пользовательская задача - не считая, конечно, сетевых и др. демонов (daemon - программа, выполняющаяся в фоновом режиме без выхода на консоль и обслуживающая запросы программ-клиентов), обеспечивающих функционирование данного ВУ какчасти МВС.• Для управления массивом вычислительных блоков служит управляющаяЭВМ (УМ); она же выполняет функцию ‘front-end машины’ (т.е. обеспечивающей доступ на вычислительный кластер удаленных пользователей по42сети InterNet или IntraNet). Именно на управляющей ЭВМ компилируется программа, она же осуществляет управление вычислительными узлами(с помощью команд семейства rlogin, rsh, rshall и т.п.).Все ВУ имеют доступ к копиям выполняемой программы с использованием протокола NFS (Network File System) файловой системы (определенный каталог является общим для УМ и всех ВУ; таким же образом реализуется сбор данных выходных файлов от всех экземпляров выполняемойпрограммы).
УМ одновременно может являться файл-сервером для хранения пользовательских программ (для этой цели возможно использовать истороннюю ЭВМ с дисковым массивом значительной емкости).• Для связи УМ и ВУ применяется коммуникационная среда, использующаястандартные (напр., Ethernet, Fast- или GigaBit Ethernet) или специализированные высокоскоростные низколатентные (Myrinet, SCI, InfiniBand) сетевые технологии.Обычно применяются две сети – сеть управления (именно она служитдля управления ВУ со стороны УМ) и сеть обмена данными (предназначена для обмена данными между ВУ); причем только от второй сети требуется максимальное быстродействие и минимальная латентность. Внаиболее производительных вычислительных кластерах в отдельную сетьиногда выделяют сеть поддержки NFS (оная интенсивно используется вмоменты старта/окончания задания и при выводе данных).Администрирование МВС осуществляется с УМ или посредством удаленного доступа(УД) суперпользователем root, рядовые пользователи имеют ограниченный доступ (в соответствие с присвоенными администратором правами, обычно только к определенномукаталогу файловой системы) к ресурсам кластера исключительно через УМ в режиме УД.Возможность захода (т.е.
перехвата управления удаленной ЭВМ со своего терминала посредством УД по сети) на ВУ имеет исключительно администратор (суперпользовательroot).Рисунок 6.1 — Укрупненная схема сетевых коммуникаций многопроцессорнойвычислительной системы (вычислительного кластера)43На рис.6.1 изображена укрупненная схема сетевых соединений для вычислительного кластера, удовлетворяющих минимуму вышеуказанных требований.Рисунок 6.2 — Схема сетевых соединений отдельных компонентов многопроцессорной вычислительной системы (вычислительного кластера кафедрыИТ-4 МГУПИ)44Более подробная схема сетевых соединений (с уточнением IP-адресов ииспользованием Fast Ethernet для сети управления и Gigabit Ethernet для сетиобмена данными) представлена на рис.6.2 (в данном случае используется топология ‘звезда’ относительно коммутатора, применяемый сетевой протокол– TCP/IP).Технология Gigabit Ethernet позволяет довести пропускную способностьсети до 60÷80 Мбайт/сек, однако латентность зачастую выше, чем уFast Ethernet [6].
Если для повышения быстродействия Fast Ethernet - сетивозможно применить технологию Channel Bonding (связывание каналов фактически их дублирование путем совместного использования несколькихсетевых плат и кабелей, причем в Linux начиная с ядер версии 2.4.x этавозможностьявляетсястандартновключаемой;см.http://linuxcluster.org.ru/bonding.php.htm), то снизить латентность реально лишь с помощью применения (существенно) более дорогостоящего сетевого оборудования.Технология SCI (Scalable Coherent Interface, фирма Dolphin Interconnect Solutions, Inc., http://www.dolphinics.com) является международным стандартом (IEEE1596) высокоскоростных соединений.