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

1.3 Алгоритм покрывающего дерева (STA )

Алгоритм покрывающего дерева - Spanning Tree Algorith (STA) позволяет коммутаторам автоматически определять древовидную конфигурацию связей в сети при произвольном соединении портов между собой. Как уже отмечалось, для нормальной работы коммутатора требуется отсутствие замкнутых маршрутов в сети. Эти маршруты могут создаваться администратором специально для образования резервных связей или же возникать случайным образом, что вполне возможно, если сеть имеет многочисленные связи, а кабельная система плохо структурирована или документирована.

Поддерживающие алгоритм STA коммутаторы автоматически создают активную древовидную конфигурацию связей, то есть связную конфигурацию без петель, на множестве всех связей сети. Такая конфигурация называется покрывающим деревом - Spanning Tree (иногда ее называют основным деревом), и ее название дало имя всему алгоритму. Алгоритм Spanning Tree описан в стандарте IEEE 802.1D, том же стандарте, который определяет принципы работы прозрачных мостов.

Коммутаторы находят покрывающее дерево адаптивно, с помощью обмена служебными пакетами. Реализация в коммутаторе алгоритма STA очень важна для работы в больших сетях - если коммутатор не поддерживает этот алгоритм, то администратор должен самостоятельно определить, какие порты нужно перевести в заблокированное состояние, чтобы исключить петли. К тому же при отказе какого-либо кабеля, порта или коммутатора администратор должен, во-первых, обнаружить факт отказа, а во-вторых, ликвидировать последствия отказа, переведя резервную связь в рабочий режим путем активизации некоторых портов. При поддержке коммутаторами сети протокола Spanning Tree отказы обнаруживаются автоматически, за счет постоянного тестирования связности сети служебными пакетами. После обнаружения потери связности протокол строит новое покрывающее дерево, если это возможно, и сеть автоматически восстанавливает работоспособность. Алгоритм Spanning Tree определяет активную конфигурацию сети за три этапа.

Сначала в сети определяется корневой коммутатор (root switch), от которого строится дерево. Корневой коммутатор может быть выбран автоматически или назначен администратором. При автоматическом выборе корневым становится коммутатор с меньшим значением МАС-адреса его блока управления.

Затем, на втором этапе, для каждого коммутатора определяется корневой порт(root port) - это порт, который имеет по сети кратчайшее расстояние до корневого коммутатора (точнее, до любого из портов корневого коммутатора).

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

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

Рис.5 Построение покрывающего дерева по алгоритму STA

Расстояние до корня определяется как суммарное условное время на передачу одного бита данных от порта данного коммутатора до порта корневого коммутатора. При этом считается, что время внутренних передач данных (с порта на порт) коммутатором пренебрежимо мало, а учитывается только время на передачу данных по сегментам сети, соединяющим коммутаторы. Условное время сегмента рассчитывается как время, затрачиваемое на передачу одного бита информации в 10 наносекундных единицах между непосредственно связанными по сегменту сети портами. Так, для сегмента Ethernet это время равно 10 условным единицам, а для сегмента Token Ring 16 Мбит/с - 6,25. (Алгоритм STA не связан с каким-либо определенным стандартом канального уровня, он может применяться к коммутаторам, соединяющим сети различных технологий.)

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

Для автоматического определения начальной активной конфигурации дерева все коммутаторы сети после их инициализации начинают периодически обмениваться специальными пакетами, называемыми протокольными блоками данных моста - BPDU (Bridge Protocol Data Unit), что отражает факт первоначальной разработки алгоритма STA для мостов.

2 Специальная часть

2.1 Структуризация LAN с помощью мостов

2.1.1 Принципы работы мостов

Прозрачные мосты

Прозрачные мосты незаметны для сетевых адаптеров конечных узлов, так как они строят специальную адресную таблицу, на основании которой можно, передавать пришедший кадр в какой-либо другой сегмент или нет. Сетевые адаптеры при использовании прозрачных мостов работают точно так же, как и в случае их отсутствия, то есть не предпринимают никаких дополнительных действий, чтобы кадр прошел через мост. Алгоритм прозрачного моста не зависит от технологии локальной сети, в которой устанавливается мост, поэтому прозрачные мосты Ethernet работают точно так же, как прозрачные мосты FDDI. Прозрачный мост строит свою адресную таблицу на основании пассивного наблюдения за трафиком, циркулирующим в подключенных к его портам сегментах. При этом мост учитывает адреса источников кадров данных, поступающих на порты моста. По адресу источника кадра мост делает вывод о принадлежности этого хоста тому или иному сегменту сети. На рис.7 проиллюстрирован процесс работы прозрачного моста.

Недостатки сетей на мостах. Алгоритм покрывающего дерева.

· Слабая защита от широковещательного шторма.

· Невозможность поддержки петлеобразных конфигураций сети.

Пример сети с петлеобразной конфигурацией:

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

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

Зачастую для надежности в сетях ввозят избыточные связи.

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

Блокировка осуществляется как вручную, так и в автоматическом режиме.

Для автоматического блокирования используются специальные алгоритмы.

Альтернативные связи в сетях обычно используются двумя способами:

· в режиме резервирования, когда одно из них функционирует, а остальные находятся в «горячем» резерве для замены отказавшей связи

· в режиме баланса нагрузки; при этом данные передаются параллельно по всем альтернативным

Алгоритм покрывающего дерева - Spanning Tree Algorithm (STA) позволяет коммутаторам автоматически определять древовидную конфигурацию связей в сети при произвольном соединения портов между собой. Для нормальной работы коммутатора требуется отсутствие замкнутых маршрутов в сети.

Поддерживающие алгоритм STA коммутаторы автоматически создают активную древовидную конфигурацию связей (то есть связную конфигурацию без петель) на множестве всех связей сети. Такая конфигурация называется покрывающим деревом - Spanning Tree (иногда ее называют основным деревом), и ее название дало имя всему алгоритму. Алгоритм Spanning Tree описан в стандарте IEEE 802.1D.

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

Алгоритм Spanning Tree определяет активную конфигурацию сети за три этапа.

· Сначала в сети определяется корневой коммутатор (root switch), от которого строится дерево. Корневой коммутатор может быть выбран автоматически или назначен администратором. При автоматическом выборе корневым становится коммутатор с меньшим значением МАС - адреса его блока управления.

· Затем, на втором этапе, для каждого коммутатора определяется корневой порт (root port) - это порт, который имеет по сети кратчайшее расстояние до корневого коммутатора (точнее, до любого из портов корневого коммутатора).

· И наконец, на третьем этапе для каждого сегмента сети выбирается так называемый назначенный порт (designated port) - это порт, который имеет кратчайшее расстояние от данного сегмента до корневого коммутатора. После определения корневых и назначенных портов каждый коммутатор блокирует остальные порты, которые не попали в эти два класса портов. Можно математически доказать, что при таком выборе активных портов в сети исключаются петли и оставшиеся связи образуют покрывающее дерево (если оно может быть построено при существующих связях в сети).

Протокол HTTP

Hypertext Transfer Protocol (HTTP, протокол пересылки гипертекста) - это язык, которым клиенты и серверы World Wide Web пользуются для общения между собой. Кроме того, иногда HTTP фильтрует информацию и передает ее обратно пользователям - это происходит, например, когда в окне браузера отображаются коды ошибок сервера.

Все HTTP-транзакции имеют один общий формат. Каждый запрос клиента и ответ сервера состоит из трех частей: строки запроса (ответа), раздела заголовка и тела. Клиент инициирует транзакцию следующим образом:

1) Клиент устанавливает связь с сервером по назначенному номеру порта (по умолчанию - 80). Затем клиент посылает запрос документа, указав HTTP-команду, называемую методом, адрес документа и номер версии HTTP.

GET /index.html HTTP/1.0

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

User-Agent: Mozilla/4.05 (WinNT; 1)

Accept: image/gif, image/x-xbitmap, image/jpeg, image/pjpeg, */*

3) Послав запрос и заголовки, клиент может отправить и дополнительные данные. Эти данные используются главным образом теми CGI-программами, которые применяют метод POST.

Сервер отвечает на запрос клиента следующим образом:

1) Первая часть ответа сервера - строка состояния, содержащая три поля: версию HTTP, код состояния и описание.

2) После строки состояния сервер передает клиенту информацию заголовка, содержащую данные о самом сервере и затребованном документе.

Server: Apache/2.2.6

Content-type: text/html

Content-length: 2482

3) Если запрос клиента успешен, то посылаются затребованные данные. Это может быть копия файла или результат выполнения CGI-программы. Если запрос клиента удовлетворить нельзя, передаются дополнительные данные в виде понятного для пользователя разъяснения причин, по которым сервер не смог выполнить данный запрос.

В HTTP 1.0 за передачей сервером затребованных данных следует разъединение с клиентом, и транзакция считается завершенной, если не передан заголовок Connection: Keep Alive.

Метод - это HTTP-команда, с которой начинается первая строка запроса клиента. Метод сообщает серверу о цели запроса. Для HTTP определены три основных метода: GET, HEAD и POST.

Метод POST позволяет посылать на сервер данные в запросе клиента. Эти данные направляются в программу обработки данных, к которой сервер имеет доступ. В качестве схемы кодирования с методом POST используется Ваsе64-кодирование.

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

Протокол SMTP

Основная задача протокола SMTP (Simple Mail Transfer Protocol) заключается в том, чтобы обеспечивать передачу электронных сообщений (почту). Для работы через протокол SMTP клиент создаёт TCP соединение с сервером через порт 25. Затем клиент и SMTP сервер обмениваются информацией пока соединение не будет закрыто или прервано. Основной процедурой в SMTP является передача почты (Mail Procedure). Далее идут процедуры форвардинга почты (Mail Forwarding), проверка имён почтового ящика и вывод списков почтовых групп. Самой первой процедурой является открытие канала передачи, а последней - его закрытие.

Команды SMTP указывают серверу, какую операцию хочет произвести клиент. Команды состоят из ключевых слов, за которыми следует один или более параметров. Ключевое слово состоит из 4-х символов и разделено от аргумента одним или несколькими пробелами. Каждая командная строка заканчивается символами перевода строки (CRLF). Вот синтаксис всех команд протокола SMTP (SP - пробел):

HELO

MAIL FROM:

RCPT TO:

DATA

RSET

SEND FROM:

SOML FROM:

SAML FROM:

VRFY

EXPN

HELP

NOOP

QUIT

Обычный ответ SMTP сервера состоит из номера ответа, за которым через пробел следует дополнительный текст. Номер ответа служит индикатором состояния сервера.

Первым делом подключаемся к SMTP серверу через порт 25. Теперь надо передать серверу команду HELLO и наш IP адрес (здесь и далее символически обозначены: С: - запрос клиента, S: - ответ сервера): С: HELLO 195.161.101.33 S: 250 smtp.mail.ru is ready

При отправке почты передаём некоторые нужные данные (отправитель, получатель и само письмо):

С: MAIL FROM: <отправитель>

С: RCPT ТО: <получатель>

указываем серверу, что будем передавать содержание письма (заголовок и тело письма)

S: 354 Start mail input; end with .

<само письмо>

передачу письма необходимо завершить символами CRLF.CRLF

Теперь завершаем работу, отправляем команду QUIT: S: QUIT С: 221 smtp.mail.ru is closing transmission channel

С: From: Drozd

C: To: Drol

C: Subject: Hello

C: 221 smtp.mail.ru is closing transmission channel

Протокол РОРЗ

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

РОРЗ - сервис, как правило, устанавливается на 110-й TCP-порт сервера, который будет находиться в режиме ожидания входящего соединения. Когда клиент хочет воспользоваться РОРЗ -сервисом, он просто устанавливает ТСР-соединение с портом ПО этого хоста. После установления соединения сервис РОРЗ отправляет подсоединившемуся клиенту приветственное сообщение. После этого клиент и сервер начинают обмен командами и данными. По окончании обмена РОРЗ -канал закрывается.

Ответы РОРЗ-сервера на команды состоят из строки статус-индикатора, ключевого слова, строки дополнительной информации и символов завершения строки - . Длина строки ответа может достигать 512 символов. Строка статус-индикатора принимает два значения: положительное ("+ОК") и отрицательное ("-ERR"). Любой сервер РОРЗ обязан отправлять строки статус-индикатора в верхнем регистре, тогда как другие команды и данные могут приниматься или отправляться как в нижнем, так и в верхнем регистрах.

РОРЗ-сессия состоит из нескольких частей. Как только открывается ТСР-соединение и РОРЗ-сервер отправляет приветствие, сессия должна быть зарегистрирована - состояние аутентификации (AUTHORIZATION state). Клиент должен зарегистрироваться в РОРЗ-сервере, т. е. ввести свой идентификатор и пароль. Это может быть выполнено либо с помощью команд USER и PASS - ввод открытых пользовательского идентификатора и пароля, либо командой АРОР - авторизации цифровой подписью, на базе секретного ключа.

После этого сервер предоставляет клиенту его почтовый ящик и открывает для данного клиента транзакцию - состояние начала транзакции обмена (TRANSACTION state). На этой стадии клиент может считать и удалить почту своего почтового ящика. Команда STAT (без аргументов) используется для просмотра состояния текущего почтового ящика.

В ответ РОРЗ- сервер возвращает строку, содержащую количество и общий размер в байтах сообщений, которые клиент может получить с РОРЗ- сервера. Сообщения, помеченные на удаление, не учитываются. Формат ответа: "+ОК nn mm", где пп - количество сообщений, mm - их общий объем:

Команда RETR - используется для передачи клиенту запрашиваемого сообщения:

После получения, сообщение, как правило, помечается на удаление из почтового ящика, при этом используется команда DELE:

После того как клиент заканчивает работу (передает команду QUIT), сессия переходит в состояние UPDATE - завершение транзакции. В этом состоянии РОРЗ-сервер закрывает транзакцию данного клиента (на языке баз данных -операция COMMIT) и закрывает ТСР-соединение. Аргумент команды: номер сообщения. Сообщения, помеченные на удаление, реально удаляются только после закрытия транзакции, на стадии UPDATE.

Для проверки состояния соединения с РОРЗ- сервером используется команда NOOP. При активном соединении ответом на нее будет положительный индикатор "+ОК":

Протокол FTP

FTP (RFC-959) обеспечивает файловый обмен между удаленными пользователями.

Работа FTP на пользовательском уровне содержит несколько этапов:

1. Идентификация (ввод имени-идентификатора и пароля).

2. Выбор каталога.

3. Определение режима обмена (поблочный, поточный, ascii или двоичный).

4. Выполнение команд обмена (get, mget, dir, mdel, mput или put).

Завершение процедуры (quit или close).

Команды и отклики передаются по управляющему соединению между клиентом и сервером в формате NVT ASCII. Клиент может отправить серверу более чем 30 различных FTP команд.

Отклики состоят из 3-циферных значений в формате ASCII, и необязательных сообщений, которые следуют за числами.

Отклик	Описание

lyz	Положительный предварительный отклик. Действие началось, однако необходимо дождаться еще одного отклика перед отправкой следующей команды.
2yz	Положительный отклик о завершении. Может быть отправлена новая команда.
3yz	Положительный промежуточный отклик. Команда принята, однако необходимо отправить еще одну команду.
4yz	Временный отрицательный отклик о завершении. Требуемое действие не произошло, однако ошибка временная, поэтому команду необходимо повторить позже.
5yz	Постоянный отрицательный отклик о завершении. Команда не была воспринята и повторять ее не стоит.
xOz	Синтаксическая ошибка.

xlz	Информация.
x2z	Соединения. Отклики имеют отношение либо к управляющему, либо к соединению данных.
x3z	Аутентификация и бюджет. Отклик имеет отношение к логирова-нию или командам, связанным с бюджетом.
x4z	Не определено.
x5z	Состояние файловой системы.

125 Соединение данных уже открыто; начало передачи.

200 Команда исполнена.

214 Сообщение о помощи (для пользователя).

331 Имя пользователя принято, требуется пароль.

425 Невозможно открыть соединение данных.

452 Ошибка записи файла.

500 Синтаксическая ошибка (неизвестная команда).

501 Синтаксическая ошибка (неверные аргументы).

502 Нереализованный тип MODE.

Управление соединением

Использовать соединение данных можно тремя способами.

1. Отправка файлов от клиента к серверу.

2. Отправка файлов от сервера к клиенту.

3.Отправка списка файлов или директорий от сервера к клиенту

Протокол Echo

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

Службы Echo на базе протокола TCP.

Один из вариантов эхо-сервиса определен как основанный на организации соединений приложение TCP. Эхо-сервер прослушивает соединения TCP на порту 7. После организации соединения все полученные через это соединение данные возвращаются отправителю. Процесс возврата полученных данных отправителю продолжается до тех пор, пока инициатор соединения не разорвет это соединение.

Службы Echo на базе протокола UDP.

Другой вариант эхо-сервиса не использует прямых соединений и основан на передаче дейтаграмм UDP. Эхо-сервер прослушивает порт 7 (UDP) и возвращает отправителю все принятые через этот порт дейтаграммы.

Данный протокол предназначен для синхронизации времени. В сети работают time-серверы, у которых можно запросить точное время. Следует заметить, что в настоящее время для синхронизации времени в глобальных сетях используется более сложный протокол - NTP - Network Time Protocol. В ответ на запрос клиента, сервер возвращает время в секундах (32х битное двоичное число), прошедшее с 00:00:00 1 января 1900 года.

Этот протокол может использовать в качестве транспортной службы как UDP-протокол, так и TCP-протокол. Стандартный порт протокола - 37.

Если в качестве транспортной службы используется TCP, взаимодействие осуществляется так:

SERVER: прослушивает 37 порт, ожидая соединений CLIENT: запрашивает соединение с портом 37 сервера SERVER: посылает время в виде двоичного 32х битного числа CLIENT: получает время SERVER: закрывает соединение CLIENT: закрывает соединение

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

Если в качестве транспортной службы используется UDP, взаимодействие осуществляется так:

SERVER: прослушивает 37 порт, ожидая соединений CLIENT: посылает серверу пустой UDP-пакет, номер порта = 37 SERVER: получает пустой UDP-пакет

SERVER: посылает UDP-пакет, содержащий время в виде двоичного 32х битного числа

CLIENT: получает UDP-пакет, содержащий время

Если сервер по каким-либо причинам не может определить время на своей стороне, он отбрасывает полученный пустой UDP-пакет и не посылает ничего в ответ.

Протокол DayTime определен в документе RFC867. Протокол может использовать в качестве транспортного протокола UDP и TCP. В случае использования UDP сервер занимает 13-й порт и ожидает поступления датаграмм. После получения датаграммы он отправляет по обратному адресу пакет, содержащий текущие дату и время в виде текстовой строки. Дополнительно, сервер выводит информацию о поступившем запросе на стандартный вывод. В случае использования TCP, как и в UDP, сервер занимает порт 13 и ожидает поступления запросов на установление соединения. После установления соединения, сервер отправляет клиенту строку, содержащую дату и время, и закрывает соединение.

Протокол Whois это информационный сервис. Несмотря на то, что любой узел может предоставить Whois сервис, наиболее широко используется InterNIC, rs.internic.net. Этот сервер содержит информацию обо всех зарегистрированных DNS доменах и о большинстве системных администраторов, которые ответственны за системы, подключенные к Internet. (Еще один подобный сервер nic.ddn.mil содержит информацию о сети MILNET.) К сожалению, не всегда предоставляется полная информация. RFC 954 документирует сервис Whois.

С точки зрения протокола, сервер Whois работает с заранее известным портом TCP 43. Он принимает от клиента запрос на соединение, после чего клиент отправляет на сервер запрос длиной в 1 строку. Сервер выдает информацию и закрывает соединение. Запросы и отклики передаются в формате NVT ASCII. Он практически идентичен серверу Finger, за исключением того, что запросы и отклики содержат разную информацию.

Широко используемый Unix клиент - программа whois, однако можно использовать Telnet и ввести команды самостоятельно. Сначала отправляется запрос, содержащий знак вопроса, на что возвращается более подробная информация о поддерживаемых запросах клиента.

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

Многие узлы не запускают Finger сервер по двум причинам. Во-первых, ошибки в программировании в ранних версиях сервера были одной из точек входа "червяка" в Internet в 1988 году. Во-вторых, протокол Finger может предоставить подробную информацию о пользователях (имя входа в систему, телефонные номера, время последнего входа и так далее), а эту информацию большинство администраторов считают частной. Раздел 3 RFC 1288 детально описывает аспекты секретности, соответствующие сервису Finger.

Сервер Finger использует заранее известный порт 79. Клиент осуществляет активное открытие на этот порт и отправляет запрос длиной в 1 строку. Сервер обрабатывает запрос, посылает назад вывод и закрывает соединение. Запрос и отклик в формате NVT ASCII, почти так же как мы видели в случае FTP и SMTP.

Обычно большинство пользователей Unix получают доступ к серверу Finger с использованием клиента finger, однако можно воспользоваться Telnet клиентом. Если запрос клиента состоит из пустой строки (которая в NVT ASCII передается как CR, за которой следует LF), это воспринимается как запрос на информацию о всех текущих пользователях.

Rlogin появился в 4.2BSD и был предназначен для захода удаленным терминалом между Unix хостами. Поэтому Rlogin проще, чем Telnet, так как он не требует определения параметров, которые для одной и той же операционной системы известны заранее и для клиента, и для сервера. Через несколько лет Rlogin был перенесен на не-Unix системы.

RFC 1282 содержит спецификацию протокола Rlogin. Однако, как и в случае с RFC посвященным RIP (Routing Information Protocol), он был написан после того, как Rlogin уже использовался в течении нескольких лет.Rlogin использует одно TCP соединение между клиентом и сервером. После того как TCP соединение установлено, между клиентом и сервером осуществляется следующая последовательность действий.

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

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

Сервер отвечает нулевым байтом.

У сервера есть опция, с помощью которой он просит ввести пароль. Это осуществляется как обычный обмен данными по Rlogin соединению - специальные протоколы не применяются. Сервер отправляет клиенту строку (которую клиент отображает на терминале), чаще всего эта строка выглядит как «Password:». Если клиент не вводит пароль в течение определенного времени (обычно 60 секунд), сервер закрывает соединение. Все что вводится в ответ на приглашение сервера ввести пароль, передается в виде открытого текста. Символы введенного пароля посылаются так, как они есть. Каждый, кто может прочитать пакеты в сети, может прочитать любой пароль.

Сервер обычно отправляет запрос клиенту, спрашивая размер окна терминала.

Клиент посылает за один раз серверу 1 байт, каждый байт сервер отражает эхо-откликом. Функционально все довольно просто: то, что вводит пользовтель, отправляется на сервер, а то, что сервер отправляет клиенту, отображается на терминале.

Telnet был разработан, для того чтобы работать между хостами работающими под управлениием любых операционных систем, а также с любыми терминалами. Его спецификация, приведенная в RFC 854 , определяет терминал, который может являться наиболее общим, и который называется виртуальным сетевым терминалом (NVT - network virtual terminal). NVT это воображаемое устройство, находящееся на обоих концах соединения, у клиента и сервера, с помощью которого устанавливается соответствие между их реальными терминалами. Таким образом, операционная система клиента должна определять соответствие между тем типом терминала, за которым работает пользователь, с NVT. В свою очередь, сервер должен устанавливать соответствие между NVT и теми типами терминалов, которые он (сервер) поддерживает.

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

Основные понятия CORBA.

Технология CORBA (архитектура брокера объектных запросов) была разработана концерном OMG (Object Management Group) для стандартизации технологии создания распределенных систем. Под распределенными системами здесь понимают программные комплексы, составные части которых функционируют на разных компьютерах в сети. Части комплексов взаимодействуют используя технологии самого различного уровня – от сокетов TCP/IP до технологий с высоким уровнем абстракции. Примнительно к CORBA универсальным считается решение, которое не зависит от языка программирования, аппаратной платформы, ОС, сетевого протокола передачи данных, двоичных стандартов и структур. На основании этого OMG декларировало технологию CORBA как универсальную технологию создания распределенных систем в интероперабельных средах.

Основные понятия:

CORBA-объект – виртуальное понятие: он представляет собой нечто, расположенное на брокере объектных запросов, посылающее запросы к другим CORBA-объектам – серверным объектам и получающее запросы от других CORBA-объектов – клиентов. Идентификатор объекта (object ID) – уникальное имя объекта внутри его объектного адаптера. Он представляет собой последовательность байт, которая ассоциируется с объектом в момент его создания. Сервант – серверная программа, написанная на каком-либо из языков программирования и выполняющая CORBA-объект. Скелетон – серверная программа, которая связывает сервант с объектным адаптером, позволяя объектному адаптеру перенаправлять запросы к соответствующему серванту. Активизация – запуск существующего CORBA-объекта для обработки клиентских запросов. Активизация предполагает, что интересующий клиента объект имеет подходящий сервант. Активизированные объекты бывают двух типов: устойчивые и временные. Деактивизация – действие, обратное активизации, останов CORBA-объекта, разрыв связки между объектом и сервантом, в общем случае без разрушения объекта. Инкарнация – это связывание серванта с CORBA-объектом для обработки клиентского запроса. Эфемеризация – в противоположность инкарнации разрушение связки CORBA-объект – сервант со стороны серванта. Карта активных объектов (Active Object Map) – таблица объектного адаптера, в которой он ведет реестр активных CORBA-объектов и связанных с ними сервантов.

Сервисы CORBA

1.Naming Service – сервис именования. Он представляет собой возможность связывания имен с объектами относительно именного контекста. Именной контекст является объектом содержащим множество уникальных именованных связей. Доступ к объекту производится механизмом разрешения имен. Это определение объекта по ассоциированному с ним имени в данном именном контексте.

2.Event Service – сервис событий. Он позволяет универсальным образом уведомлять объекты распределенной системы о происходящих событиях. Служит для организации Call Back вызовов (механизма обратного вызова). В настоящее время сервис является базовым для более развитого и обобщенного сервиса уведомлений.

3.Persistent Service – сервис долговременного хранения. Обеспечивает универсальный механизм сохранения состояний CORBA- объектов как в реляционных так и в объектных базах данных.

4.Life Cycle Service – сервис жизненного цикла. Отвечает за операцию создания, копирования перемещения и удаления объектов. Является набором интерфейсов, многие методы которых необходимо реализовывать самостоятельно. Работает в тесной связи с сервисом отношений.

5.Relationship Service – сервис отношений. Позволяет динамически устанавливать связи между объектами. Совокупности отношений образуют графы и рассматриваются как CORBA- объекты. Используются при копировании, перемещении или удалении группы связанных друг с другом объектов.

6.Properly Service – сервис свойств. Позволяет сопоставлять с объектами те или иные свойства виде пары имя-значение.

7.Security Service- сервис безопасности. Решает многие стандартные проблемы безопасности: Идентификация пользователя; Определение прав доступа; Защита информации при передачи и т.д. Распространение контекста безопасности осуществляется ORB.

8.Trading Service – трейдер сервис. Сервис поиска с помощью которого клиент получает нужную объектную ссылку. Поиск осуществляется не по имени, а по совокупности свойств объекта.

9.Externalization Service – сервис внешнего представления. Предназначен для построения образа объекта, взаимодействующего со стандартными потоками ввода-вывода (эквивалентен механизму сериализации в Java)

10.Transaction Service – сервис транзакции. Взаимодействует на уровне реализации с ORB и служит для управления транзакциями. Поддерживает двухфазное подтверждение транзакции и вложенную транзакцию.

11.Concurrency Control Service – сервис совместного доступа. Предназначен для универсального управления разделяемыми ресурсами. Осуществляет координацию параллельных транзакций.

12.Query Service – сервис запросов. Предназначен для выполнения поиска объектов соответствующих определенным критериям. Языком выполнения является либо OQL либо расширенный SQL. Результатом является совокупность объектов для манипуляции которыми используется сервис контейнеров.

13.Collections Service – сервис контейнеров. Позволяет определять группы объектов и управлять ими единообразным способом. Использует стандартные контейнеры: множества, наборы, последовательности и др. Для каждого контейнера определяется своя фабрика (интерфейс для создания контейнеров) и итератор.

14.Licensing Service – сервис лицензирования. Служит для отслеживания использования CORBA- объекта и для ограничения его применения по разным критериям. 15.Time Service – сервис времени. Служит для синхронизации часов на различных компьютерах. Основой является UTC.

Технология RMI. Основные понятия технологии JavaBeans.

Технология RMI (удаленный вызов методов) была разработана для языка Java для обеспечения передачи сообщений от объекта существующего в контексте одной виртуальной машины Java к объекту существующему в контексте другой.

RMI оказала влияние на технологии взаимодействия, которые использует CORBA.

RMI использует 2 стандартных протакола обмена:

Собственный неуниверсальный протокол обмена (RMP)

Стандартный для CORBA протокол (IIOP)

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

В свою очередь интеграция с RMI позволяет CORBA компенсировать отсутствие в настоящий момент собственной компонентной модели и универсального мониторинга транзакций.

В основу RMI заложены средства сериализации Java. Последовательность создания приложения с использованием RMI следующая:

· определение удаленных интерфейсов путем наследования стандартного интерфейса java.rmi.remote

· создание класса реализующего данный интерфейс. Это достигается путем наследования класса java.rmi.UnicastRemoteObject

· генерация специального кода заглушки, как для клиента так и для сервера с помощью компилятора rmic.

· запуск службы имен на стороне сервера rmi registry

· создание серверного приложения, которое использует классы заглушки. Это приложение служит для создания серверных объектов и регистрации их в службе имен.

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

Библиотека rmi большей частью использует интерфейсы и поэтому с помощью них предусматривается наличие подсистем поиска объектов по именам, управления безовасности, маршалинга (Маршалинг – способ вызова удаленного объекта который находится на другой машине или другой Java-машине без пересоздания кода вызывающего удаленный метод).

При создании удаленного объекта передается ссылка не на сам объект а на интерфейс по которому создается серверная заглушка, которая и проводит пересылку по сети.

Технология, в которых нашли применение как RMI так и CORBA образовав множество называемое RMI/IDL является технологией фирмы Sun Enterprise Java Beans (EJB).

Основные понятия технологии JavaBeans.

Среда JavaBeans является надстройкой над стандартной Java-технологией. Она наследует понятия и характеристики Java, такие как объектная ориентированность, многопоточность, использование виртуальной машины, независимость от аппаратно-программной платформы, информационная безопасность и т.п. В JavaBeans нет ничего, не выразимого в терминах языка Java. Основой среды JavaBeans является компонентная объектная модель, представляющая собой совокупность архитектуры и прикладных программных интерфейсов. Архитектуру образуют основные понятия и связи между ними. Прикладные программные интерфейсы характеризуют набор сервисов, предоставляемых элементами среды. Они описываются в терминах синтаксиса и семантики Java-классов и интерфейсов.

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

Неформально компонент ("кофейное зерно" - Java Bean) можно определить как многократно используемый программный объект, допускающий обработку в графическом инструментальном окружении и сохранение в долговременной памяти. С реализационной точки зрения компонент - это Java-класс и, возможно, набор ассоциированных дополнительных классов. Каждый компонент предоставляет набор методов, доступных для вызова из других компонентов и/или контейнеров. Компоненты могут обладать свойствами. Совокупность значений свойств определяет состояние компонента. Свойства могут быть доступны на чтение и/или запись посредством методов выборки и установки. Компоненты могут порождать события (быть источниками событий), извещая о них другие компоненты, зарегистрировавшиеся в качестве подписчиков. Извещение (называемое также распространением события) заключается в вызове определенного метода объектов-подписчиков. Типичным примером события является изменение свойств компонента. В общем случае компонент может предоставлять подписку на получение информации об изменении и на право запрещать изменение. Методы, свойства и события образуют набор афишируемых характеристик компонента, то есть характеристик, доступных инструментальному окружению и другим компонентам. Этот набор может быть выяснен посредством механизма интроспекции. Состояние компонентов может быть сохранено в долговременной памяти. Наличие методов для подобного сохранения выделяет компоненты JavaBeans среди произвольных Java-классов.

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

Жизненный цикл компонентов JavaBeans можно подразделить на три этапа:

· разработка и реализация компонента;

· сборка приложения из компонентов;

· выполнение приложения.

Разработка и реализация компонентов JavaBeans по сути не отличается от создания произвольных Java-объектов, хотя и может включать реализацию специфических методов. Сборка приложений выполняется, как правило, в инструментальном окружении, позволяющем проанализировать афишируемые характеристики компонентов, настроить значения свойств, зарегистрировать подписку на получение событий, организовав тем самым взаимодействие компонентов. Разработчик компонента может реализовать специальные методы для использования исключительно в инструментальном окружении (например, редактор свойств). Компоненты взаимодействуют между собой и с инструментальным окружением. Взаимодействие осуществляется двумя способами - вызывом методов и распространением событий. Спецификации JavaBeans описывают только локальное взаимодействие компонентов, осуществляемое в пределах одной виртуальной Java-машины. (Напомним, впрочем, что Java-апплеты рассчитаны на передачу по сети, так что возможно собрать приложение из компонентов, первоначально распределенных по сети.) Удаленные объекты могут связываться по протоколам архитектуры CORBA , с помощью удаленного вызова методов (Remote Method Invocation - RMI) или иными способами, не относящимися к области действия спецификации JavaBeans.

Основные понятия технологии Enterprise JavaBeans.

Enterprise JavaBeans (EJB) - спецификация технологии написания и поддержки серверных компонент, содержащих бизнес-логику. Является частью Java EE.

Сервер EJB – это среда времени выполнения, в которой могут функционировать компоненты. Его задача – обеспечить доступ к системным сервисам, необходимым для работы компонентов. Важнейшим из этих сервисов является сервис распределенных транзакций (JTS). Сервер EJB не взаимодействует непосредственно с компонентами – это задача так называемого Контейнера (Container) EJB. Контейнер EJB взаимодействует с сервером, когда одному или нескольким компонентам, находящимся под управлением Контейнера, необходим доступ к системным ресурсам. Контейнер представляет собой совокупность классов и программных средств, работающих в контексте Сервера EJB. Контейнер, в частности, обеспечивает:

Управление циклом жизни компонента – его созданием, инициализацией, сохранением его состояния в базе данных, если это необходимо;

Возможность поиска клиентом нужных ему объектов;

Гарантию того, что вызов методов происходит в контексте нужной транзакции;

Базовый уровень обеспечения безопасности;

Наличие инструментов разработчика, например, компилятора для генерации стабов.

Компонент EJB – это класс Java, который, собственно, и реализует всю необходимую функциональность. Необходимо четко понимать, что сам компонент в принципе недоступен для клиента. Клиент обращается к нему косвенно, через специальный интерфейсный объект-посредник (proxy). В литературе по EJB он обычно называется EJBObject. Время существования компонента и его proxy-объекта в общем случае различно. Сам компонент находится под управлением Контейнера, и пользователь в общем случае не может быть уверен, что два последовательных вызова клиента будут обслужены одним и тем же компонентом.

Транзакция, управляемая компонетом (Bean Managed Transaction, BMT) : Управление транзакцией берет на себя компонент. Только Session-компоненты могут использовать такой режим. Только в этом режиме вызов одного из удаленных методов может привести к началу транзакции, но не обязательно к ее завершению – несколько последующих вызовов могут происходить в контекст этой же транзакции.

Транзакция, управляемая Контейнером (Container Managed Transaction, CMT) : Режим разрешен как для Session-, так и для Entity-компонентов. Компонент не имеет возможности ни начать, ни завершить транзакцию (хотя любой из участников транзакции может потребовать ее отката (rollback) при завершении) – управление транзакцией полностью берет на себя Контейнер. Транзакция начинается при вызове каждого удаленного метода и завершается при возврате из него. Программист может установить один из нескольких разрешенных режимов, определяющих поведение транзакции.

Дескриптор развертывания (иногда используются термины «установки» или «поставки» - в настоящий момент еще нет устоявшегося термина на русском языке)- необходим для настройки созданного компонента на работу в конкретной операционной среде. Необходимость в нем возникает из-за того, что спецификация EJB четко определяет несколько этапов, который проходит компонент от своего создания до доставки конечному пользователю с окончательной настройкой.

«Построение сети с помощью алгоритма покрывающего дерева» - страница №1/1

Московский государственный институт электроники и математики

(технический университет)

Информационно-коммуникационные технологии

Расчётно-графическая работа №1 по дисциплине:

«Технические средства сетей ЭВМ»

«Построение сети с помощью алгоритма покрывающего дерева»

Вариант №5

Выполнил: студент гр. C-94

Новиков Р.О.

Преподаватель:

Леохин Ю.Л.

Москва 2008

Содержание

1. Введение	3
2. Техническое задание	6
3. Задача 1	7
4. Задача 2	8
5. Задача 3	9
6. Задача 4	10
Выводы	11

1. Введение

Алгоритм покрывающего дерева - Spanning Tree Algorithm (STA) позволяет коммутаторам автоматически определять древовидную конфигурацию связей в сети при произвольном соединении портов между собой. Как уже отмечалось, для нормальной работы коммутатора требуется отсутствие замкнутых маршрутов в сети. Эти маршруты могут создаваться администратором специально для образования резервных связей или же возникать случайным образом, что вполне возможно, если сеть имеет многочисленные связи, а кабельная система плохо структурирована или документирована.

Поддерживающие алгоритм STA коммутаторы автоматически создают активную древовидную конфигурацию связей (то есть связную конфигурацию без петель) на множестве всех связей сети. Такая конфигурация называется покрывающим деревом - Spanning Tree (иногда ее называют основным деревом), и ее название дало имя всему алгоритму. Алгоритм Spanning Tree описан в стандарте IEEE 802.1D, том же стандарте, который определяет принципы работы прозрачных мостов.

Алгоритм Spanning Tree определяет активную конфигурацию сети за три этапа.

Сначала в сети определяется корневой коммутатор (root switch), от которого строится дерево. Корневой коммутатор может быть выбран автоматически или назначен администратором. При автоматическом выборе корневым становится коммутатор с меньшим значением МАС - адреса его блока управления.
Затем, на втором этапе, для каждого коммутатора определяется корневой порт (root port) - это порт, который имеет по сети кратчайшее расстояние до корневого коммутатора (точнее, до любого из портов корневого коммутатора).
И наконец, на третьем этапе для каждого сегмента сети выбирается так называемый назначенный порт (designated port) - это порт, который имеет кратчайшее расстояние от данного сегмента до корневого коммутатора. После определения корневых и назначенных портов каждый коммутатор блокирует остальные порты, которые не попали в эти два класса портов. Можно математически доказать, что при таком выборе активных портов в сети исключаются петли и оставшиеся связи образуют покрывающее дерево (если оно может быть построено при существующих связях в сети).

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

Расстояние до корня определяется, как суммарное условное время на передачу одного бита данных от порта данного коммутатора до порта корневого коммутатора. При этом считается, что время внутренних передач данных (с порта на порт) коммутатором пренебрежимо мало, а учитывается только время на передачу данных по сегментам сети, соединяющим коммутаторы. Условное время сегмента рассчитывается как время, затрачиваемое на передачу одного бита информации в 10 наносекундных единицах между непосредственно связанными по сегменту сети портами. Так, для сегмента Ethernet это время равно 10 условным единицам, а для сегмента Token Ring 16 Мбит/с - 6,25. (Алгоритм STA не связан с каким-либо определенным стандартом канального уровня, он может применяться к коммутаторам, соединяющим сети различных технологий.)

Для автоматического определения начальной активной конфигурации дерева все коммутаторы сети после их инициализации начинают периодически обмениваться специальными пакетами, называемыми протокольными блоками данных моста - BPDU (Bridge Protocol Data Unit), что отражает факт первоначальной разработки алгоритма STA для мостов.

Идентификаторы коммутаторов состоят из 8 байт, причем младшие 6 являются МАС - адресом блока управления коммутатора. Старшие 2 байта в исходном состоянии заполнены нулями, но администратор может изменить значение этих байтов, тем самым назначив определенный коммутатор корневым.

После инициализации каждый коммутатор сначала считает себя корневым. Поэтому он начинает через интервал hello генерировать через все свои порты сообщения BPDU конфигурационного типа. В них он указывает свой идентификатор в качестве идентификатора корневого коммутатора (и в качестве идентификатора данного коммутатора также), расстояние до корня устанавливается в 0, а в качестве идентификатора порта указывается идентификатор того порта, через который передается BPDU. Как только коммутатор получает BPDU, в котором имеется идентификатор корневого коммутатора, со значением, меньшим его собственного, он перестает генерировать свои собственные кадры BPDU, а начинает ретранслировать только кадры нового претендента на звание корневого коммутатора. На рис. 4.38 у коммутатора 1 идентификатор имеет наименьшее значение, раз он стал в результате обмена кадрами корневым.

При ретрансляции кадров каждый коммутатор наращивает расстояние до корня, указанное в пришедшем BPDU, на условное время сегмента, по которому принят данный кадр. Тем самым в кадре BPDU, по мере прохождения через коммутаторы, накапливается расстояние до корневого коммутатора. Если считать, что все сегменты рассматриваемого примера являются сегментами Ethernet, то коммутатор 2, приняв от коммутатора BPDU по сегменту 1 с расстоянием, равным 0, наращивает его на 10 единиц.

Ретранслируя кадры, каждый коммутатор для каждого своего порта запоминает минимальное расстояние до корня, встретившееся во всех принятых этим портом кадрах BPDU. При завершении процедуры установления конфигурации покрывающего дерева (по времени) каждый коммутатор находит свой корневой порт - это порт, для которого минимальное расстояние до корня оказалось меньше, чем у других портов. Так, коммутатор 3 выбирает порт А в качестве корневого, поскольку по порту А минимальное расстояние до корня равно 10 (BPDU с таким расстоянием принят от корневого коммутатора через сегмент 1). Порт В коммутатора 3 обнаружил в принимаемых кадрах минимальное расстояние в 20 единиц - это соответствовало случаю прохождения кадра от порта В корневого моста через сегмент 2, затем через мост 4 и сегмент 3.

Кроме корневого порта коммутаторы распределенным образом выбирают для каждого сегмента сети назначенный порт. Для этого они исключают из рассмотрения свой корневой порт (для сегмента, к которому он подключен, всегда существует другой коммутатор, который ближе расположен к корню), а для всех своих оставшихся портов сравнивают принятые по ним минимальные расстояния до корня с расстоянием до корня своего корневого порта. Если у какого-либо своего порта принятые им расстояния до корня больше, чем расстояние маршрута, пролегающего через свой корневой порт, то это значит, что для сегмента, к которому подключен данный порт, кратчайшее расстояние к корневому коммутатору ведет именно через данный порт. Коммутатор делает все свои порты, у которых такое условие выполняется, назначенными.

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

2. Техническое задание

Для сети, состоящей из 5 сегментов Ethernet и 6 мостов, соединенных так, как это показано на рисунке определить корневой мост и корневые порты и назначенные порты у некорневых мостов, используя алгоритм покрывающего дерева.

Идентификаторы мостов и портов обозначены цифрой после однобуквенного имени моста (B) или порта (P). Сегменты идентификаторов не имеют, и их порядковые номера приведены только для удобства.

Условные обозначения:

Корневой порт

Отключенный порт

Назначенный порт

3. Задача 1

Условие

Все мосты и порты имеют равные приоритеты, все сегменты имеют равную пропускную способность и условное время для них = 1.

Решение

	B1.P1	B1.P2	B1.P3	B2.P1	B2.P2	B3.P1	B3.P2
minRPC	0	0	0	0	0	0	1
RPC	0	0	0	1	1	1	2
minB				B1		B1
minP				P2		P1

	B4.P1	B4.P2	B4.P3	B5.P1	B5.P2	B6.P1	B6.P2
minRPC	0	1	0	0	1	1	∞
RPC	1	2	1	1	2	2	∞
minB	B1			B1		B3
MinP	P3			P3		P2

4. Задача 2

Условие

Все параметры те же, что и в случае 1, но мост B1 отказал.

Решение

В заданных условиях корневым станет мост B2. Это произойдет в результате выполнения процедуры активной конфигурации, вызванной отказом моста B1.

	B2.P1	B2.P2	B3.P1	B3.P2	B4.P1	B4.P2	B4.P3	B5.P1	B5.P2	B6.P1	B6.P2
minRPC	0	0	1	1	0	1	2	0	1	1	∞
RPC	0	0	2	2	1	2	3	1	2	2
minB			B4		B2			B2		B3
minP			P3		P2			P2		P2

5. Задача 3

Условие

Все мосты работоспособны, но производительность сегментов S3 и S5 в три раза выше остальных, поэтому условное время остальных сегментов в три раза больше, чем у S3 и S5.

Решение

Мост B1 имеет минимальный идентификатор – следовательно, он корневой.

	B1.P1	B1.P2	B1.P3	B2.P1	B2.P2	B3.P1	B3.P2
minRPC	0	0	0	0	0	0	1
RPC	0	0	0	3	3	1	6
minB				B1		B1
minP				P2		P1

	B4.P1	B4.P2	B4.P3	B5.P1	B5.P2	B6.P1	B6.P2
minRPC	0	1	0	0	1	1	∞
RPC	3	6	1	3	6	6	∞
minB			B1	B1		B3
minP			P1	P3		P2

6. Задача 4

Условие

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

Решение

Мост B5 имеет максимальный приоритет – следовательно, он корневой.

	B1.P1	B1.P2	B1.P3	B2.P1	B2.P2	B3.P1	B3.P2
minRPC	1	1	0	1	0	1	0
RPC	2	2	1	2	1	2	1
minB			B5		B5		B5
minP			P1		P1		P2

	B4.P1	B4.P2	B4.P3	B5.P1	B5.P2	B6.P1	B6.P2
minRPC	0	0	1	0	0	0	∞
RPC	1	1	2	0	0	1	∞
minB	B5					B5
minP	P1					P2

Выводы

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

Математическая модель вычисления покрывающего дерева сети

Ключевые слова: покрывающее дерево, оптимизация затрат на трафик, нагрузка на рёбра, стоимость использования сети, интенсивность обмена трафиком.

Для произвольной заданной сети строится минимальное покрывающее дерево, учитывающее интенсивность обмена данными для каждой пары узлов исходной сети. Тем самым решается проблема выбора оптимального маршрута для обмена данными между каждой парой вершин заданного графа сети; решается задача выбора минимальных по стоимости провайдеров, обеспечивающего связь между узлами сети. Для этого сеть передачи данных представляется в виде неориентированного графа, для которого строится покрывающее дерево, обеспечивающее минимальные затраты на весь проходящий по сети трафик. Количество переданной информации в единицу времени между каждой парой узлов сети задаётся матрицей интенсивностей обмена данными. Граф сети задаётся матрицей смежности. Стоимость прохождения единицы информации по каждому из рёбер графа сети представляет собой матрицу весов. Для решения поставленной задачи разработан алгоритм и соответствующий программный продукт, строящий покрывающее дерево, которое позволяет передавать заранее заданные объёмы информации между всеми пользователями сети, при этом суммарная стоимость трафика будет минимальной. Помимо построенного покрывающего дерева алгоритм даёт также возможную минимальную стоимость передачи заданного объёма данных между всеми узлами сети. Алгоритм позволяет построить минимальное покрывающее дерево (покрывающее дерево минимального веса), однако для такой цели можно использовать уже имеющиеся алгоритмы, такие как, например, алгоритм Прима или Краскала. Однако с помощью указанных алгоритмов возможно построить лишь минимальное по весу покрывающее дерево. В отличие от них предложенный в работе алгоритм строит дерево с учётом нагрузок на рёбра и вершины исходного графа сети и, вычисляя общую стоимость всего проходящего по сети трафика, минимизирует её.

Анищенко А.А.,

соискатель, кафедра теории вероятностей и математической статистики РУДН, [email protected]

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

Пусть сеть представлена в виде связного неориентированного графа без петель С(У,Е) с множеством вершин V = \;п, и множеством ребер Е. (Здесь и далее используется терминология Харари = \;п- Если та^ = 0- то

вершины не смежные. Для удобства дальнейшего обозначения вводится равносильное обозначение та(!,]) = тЗц ■

Интенсивность передачи данных между узлами задана матрицей Л: Л = {Ху}={Х(ь])}% ¡, ] = \;п, /,У е ¡/(С)I где есть количество информации, переданное за единицу времени из вершины / в вершину /.

Заданы стоимости прохождения единицы трафика по каждому из ребер графа.

Ставится задача построения такого остовного дерева Т(У,ТЕ)> которое позволяет передавать заранее заданные объёмы информации между всеми пользователями сети (матрица Л). При этом суммарная стоимость трафика будет минимальной.

При обеспечении связи между парой вершин более чем одним провайдером (кратные ребра иа графе) рассматривается только ребро с минимальной стоимостью. Данный выбор оправдан, что доказано в ,

Поскольку граф в неориентированный, рёбра < /,} > и < _/,/ > представляют собой одно и то же ребро

и являются равноценными, то есть стоимость за единицу трафика, прошедшего по ним, одинакова.

Стоимость прохождения единицы трафика по каждому из ребер задаётся матрицей стоимостей или матрицей весов \УН = {и"/;7}-{м>г(¿,])}, ¡,] = \:п- Так как граф

С(У,Е) неориентированный, матрица №7? симметрична относительно главной диагонали. Тогда в матрице МБ

Если вершины / и / смежны,еели вершины;и] не смежны

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

Тогда, объединяя вершины в группы, можно добиться такого укрупнения графа С (V .Е"), при котором воз-

можно построение оптимального покрывающего дерева для укрупнённого графа. Л затем при необходимости и для графов, лежащих в вершинах укрупненного графа V. Для этого разбивка на группы записывается в матрицу В = {(¡¡!}, 1-\;т, / = I,/). Где т- количество групп, то есть |К"| =т, \У\ = п;

П,если /е/

V; т V, V/ е V щ =■" J

через узел, но не выходящими из него и не входящими в него.

Тогда для у круп- vifvj =

О, если i £ i

пенного графа С матрица обмена данными Л" вычисляется следующим образом: Л"= RAR1 . Таким образом, при большом количестве вершин поставленную задачу можно свести к меньшей, поэтому предполагается, что в исходном графе п достаточно мало, для того, чтобы были возможны вычисления.

Для решения поставленной задачи:

1. Строится произвольное покрывающее дерево T(V,TE), с матрицей смежности S={sy}={s(i,j)}t

ii j - п и прежней матрицей интенсивностей передачи данных Л.

2. Вычисляется матрица весов полученного дерева WRT = {wrtij } = {wrt(i,j)}: wrty = s„>

3. Для полученного дерева Т вычисляются нагрузки на ребра R = {r.. J = {r(i,j)}, i,j = \;п-

4. Вычисляется суммарная стоимость прохождения трафика по построенному покрывающему дереву

/ftMv S(¡./(¡)Щ y*/fl) Mi.jH)

Mi)+\i(i) -сЫ\) - Ui.f(i))-Mf(i) j) -

YjMftüs \(i. z))+ys ui. zj.fdjj)

MO=ifeff +)=tiWJ)+KW);

5. Полученная стоимость сравнивается с предыдущей наименьшей стоимостью и сохраняется только наименьшая.

6. Строится следующее покрывающее дерево, и алгоритм возвращается к п.2.

Таким образом, перебирая все возможные покрывающие деревья, используя, например, алгоритм Кри-стофидеса } = { f(i)} является на каждом

этапе вектором вершин, смежных с концевыми. (После каждого этапа вектор обнуляется).

dw(i)- «дуговая» нагрузка на i -ю вершину. Для вершины с номером f (i), смежной с концевой вершиной /

Usv(f(i).h),i)+WMfOJA)))

SV -{svy }-{sv(i,j)}> /,7=1,« - матрица, в /-й

строке которой записана последовательность пройденных и удалённых вершин до вершины i;

K = fkj} = {k(i)}, i - \;n - вектор-счётчик количества элементов в строке I матрицы S V .

После того, как вычислены все транзитные нагрузки И>(/) на вершины i = 1/и, можно вычислить и нагрузки на ребра дерева Т:

V/ - й г(/,/(0) - г(/Ш) - Mf) - scMi) + lam(i) -- X \lam(i,sv(i, z) + /am{5v(i, z)ti).

Так как исходный граф G неориентированный и вычисленные нагрузки на ребра r(i, /") являются суммарными нагрузками на ребро < i,j > в обе стороны, то есть из / в / и из / в /, то матрица нагрузок па ребра графа = симметрична.

Блок- схема алгоритма вычисления нагрузок на рёбра покрывающего дерева Т представлена на рис. I.

Задача о нахождении минимального остовного или покрывающего дерева для взвешенного связанного неориентированного графа возникала давно и встречается довольно часто в различных областях. Существует немало алгоритмов реализующих поиск минимального по весу покрывающего дерева для г рафа. Самыми известными из них являются алгоритмы Крас кала. Прима, Бо-рувки . Однако в применении к сетям такие алгоритмы не всегда подходят, поскольку они не учитывают нагрузки на узлы и каналы сети.

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

Mathematical model of finding a network spanning tree

Anishchenko AA, Peoples" Friendship University, Moscow, Russia, [email protected]

Abstract. The minimal spanning tree is created for any given network which takes into account the intensity of the data communication for each pair of nodes of the given network. So the problem of choosing the optimal route for the data com-munication between each pair of vertices of the given network graph is solved, the problem of choosing the providers with minimum cost of communication be-tween nodes is solved. For this data network is represented as an undirected graph for which is created a spanning tree with the minimum traffic overhead. Amount of data transmitted per unit of time between each pair of network nodes is represented as a matrix of the data exchange intensity. Graph of the network is given by the adjacency matrix. The cost of a unity of information on each of the edges of the network is a matrix of weights. An algorithm and corresponding software package were developed to solve this problem. Throgh the usage of minimal spanning tree the software allows a user to deliver a known amount of information to all nodes at minimal traffic cost.Besides the constructed spanning tree algorithm computes the minimal cost of transfer a given amount of data between all nodes. In addition algorithm can construct a minimum spanning tree (spanning tree with the lowest total cost), for this is possible use of the existing algorithms such as the Prim"s or Kruskal"s algorithm, for example. But using these algorithms allows building a spanning tree with the lowest total cost. In contrast, the proposed algorithm creates a tree taking into account loads on the edges and vertices of the original network graph and computes and minimizes the total cost of all traffic in the network. Keywords: spanning tee, cost optimization for traffic, load on the edges, the cost of using the network, the data exchange intensity.

Второй метод, использующийся для повышения отказоустойчивости компьютерной сети, это Spanning Tree Protocol. Разработанный достаточно давно, в 1983 г., он до сих пор остается актуальным. В сетях Ethernet, коммутаторы поддерживают только древовидные, т. е. не содержащие петель связи. Это означает, что для организации альтернативных каналов требуются особые протоколы и технологии, выходящие за рамки базовых, к которым относится Ethernet.

Можно положиться на сетевого администратора, который должен исключить возможность образования петель в сети, но такое решение крайне нежелательно. Даже если администратор имеет время и желание для предотвращения таких вещей, он не застрахован от ошибок. Используя алгоритм покрывающего дерева, администратор сети может не заботиться о возникновении петель, мосты сами об этом позаботятся. Алгоритм Spanning Tree (STA) позволяет коммутаторам автоматически определять древовидную конфигурацию связей в сети при произвольном соединения портов между собой. Коммутаторы, поддерживающие протокол STP автоматически создают древовидную конфигурацию связей без петель в компьютерной сети. Такая конфигурация называется покрывающим деревом - Spanning Tree (иногда ее называют остовным деревом). Конфигурация покрывающего дерева строится коммутаторами автоматически с использованием обмена служебными пакетами.

Рассмотрим подробно работу протокола STP:

1. Для построения древовидной структуры сети без петель в сети должен быть определен корневой коммутатор (root switch), от которого и строится это дерево. В качестве корневого коммутатора выбирается коммутатор с наименьшим значением идентификатора. Идентификатор коммутатора - это число длиной восемь байт, шесть младших байтов которого составляет МАС-адрес его блока управления, а два старших байта конфигурируются вручную. Это позволяет администратору сети влиять на процесс выбора корневого коммутатора. Если администратор не вмешается в этот процесс, корневой коммутатор будет выбран случайным образом - им станет устройство с минимальным MAC-адресом блока управления. Такой выбор может оказаться далеко не рациональным. Поэтому следует выбрать корневой коммутатор, исходя из имеющейся топологии сети, и назначить ему вручную наименьший идентификатор. При автоматическом выборе корневым становится коммутатор с меньшим значением МАС-адреса его блока управления.

2. Далее, для каждого коммутатора определяется корневой порт (root port) - это порт, который имеет по сети кратчайшее расстояние до корневого коммутатора. Он у каждого коммутатора только один!

3. После этого для каждого сегмента сети просчитывается кратчайший путь к корневому коммутатору. Коммутатор, через который проходит этот путь, становиться назначенным для этой сети (Designated Bridge). Непосредственно подключенный к сети порт коммутатора – назначенным портом. Назначенный порт сегмента имеет наименьшее расстояние до корневого моста, среди всех портов, подключенных к данному сегменту.