Образовательный комплекс Компьютерные сети

сети определяет алгоритм, согласно которому узлы сети получают доступ к

среде передачи данных и осуществляют передачу (включая мультиплексирование / демультиплексирование данных)
Мы рассмотрим следующие методы
ALOHA
CSMA/CD
CSMA/CА
CDMA
Маркерный доступ

для доступа к радиоканалу большого числа независимых узлов
Отправитель может выполнять

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

Access with Collision Detection (CSMA/CD)
Отправитель может начать передачу в любой

момент, когда он не принимает из среды передачи сигнал от другого узла
Если по среде передается кадр, по окончании его передачи выдерживается некоторая пауза (межкадровый интервал)
В случае возникновения коллизии, все участвовавшие в ней узлы делают паузу, после чего повторяют попытку передачи
Принципиальное отличие от алгоритма ALOHA (с точки зрения коллизий) заключается в том, что в ALOHA коллизии определяются на входе получателя, а в CSMA/CD – на выходе источника

эффективность алгоритма CSMA/CD зависит от того, насколько быстро передающий узел

определяет возникновение коллизии и прекращает передачу
С другой стороны, для четкого определения коллизии требуется, чтобы время передачи кадра минимального размера было больше удвоенного времени передачи сигнала между максимально удаленными узлами сети
Например, если узел A уже отправил весь кадр, но начало кадра еще не достигло узла B (как на рисунке), то узел B может начать передачу, в этом случае возникнет коллизия, но узел A не сможет определить что он является участником коллизии
Для обнаружения необходимо, чтобы в момент, когда сигнал, передаваемый узлом В, достигнет узла A, узел А еще не закончил передачу своего кадра

A

B

кадр

разновидность метода CSMA/CD
Если узел желает выполнить передачу, и в этот

момент по сети передается сигнал, то узел считает, что коллизия уже произошла и делает паузу случайной длительности
Данный алгоритм повышает эффективность (% использования пропускной способности), но существенно увеличивает среднее время доступа к среде передачи
Все разновидности CSMA/CD являются случайными методами доступа к сети

Access with Collision Avoidance (CSMA/CA)
Предположим, к среде передачи подключено N

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

передают станции 0 и 3, во втором – 0,1 и

2

к среде передачи подключено N узлов (N

приоритет от 0 до N-1
После передачи каждого кадра делается пауза, в которой определяются K временных интервалов (если кадр не передавался, узлы должны быть каким-либо образом синхронизированы)
Если узел готов к передаче, он передает свой приоритет по биту в интервал (нулю соответствует обычный уровень сигнала, единице – пониженный)
Если принятый сигнал соответствует тому, что передавал узел (если несколько узлов передают единицу, результат воспринимается как единица), узел продолжает передачу битов своего приоритета, если нет – считает, что выполнять передачу должен узел с более высоким приоритетом и отказывается от передачи
Если узел успешно передал все биты приоритета, он передает кадр

из соревнования после первого интервала, узел 1000 – после четвертого
1
1
1
0
0
0
кадр

Access (CDMA)
Каждому узлу выдается уникальный m-битный код (типичные значения m

– 64, 128; коды выбираются так, чтобы при замене битов со значением 0 на -1 быть взаимно ортогональными)
Каждый битовый интервал делится на m коротких интервалов, называемых чипами
Для передачи единицы станция посылает свой код (по одному биту за интервал), для передачи 0 – дополнение своего кода до 1
Принимающая станция умножает принятый сигнал на коды всех узлов
Если при перемножении на код узла результат равен 0 – узел не выполнял передачу
Если результат равен -1 – узел передавал 0
Если результат равен +1 – узел передавал 1
Таким образом, теоретически CDMA позволяет выполнять передачу всем узлам одновременно

доступа используют маркер (токен) – небольшой пакет специального вида
В сети

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

доступа – детерминированный, в отличие от CSMA/CD, который является случайным
Метод

маркерного доступа обеспечивает гарантированное время доступа к среде передачи и при высокой загрузке сети гораздо эффективнее случайных методов (в частности, в силу отсутствия потерь времени из-за коллизий)

момент стандарт локальных сетей
1972 г. – Xerox организовала экспериментальную сеть
1980

г. – DEC, Intel и Xerox разработали и опубликовали стандарт Ethernet II (Ethernet DIX)
На основе стандарта Ethernet DIX был разработан стандарт IEEE 802.3
На основе стандарта Ethernet DIX/IEEE 802.3 разработаны расширения Fast Ethernet и Gigabit Ethernet
Стандарт Ethernet DIX/IEEE 802.3 содержит следующие спецификации физического уровня
10Base-5 (толстый коаксиальный кабель)
10Base-2 (тонкий коаксиальный кабель)
10Base-T (витая пара)
10Base-FL (оптоволоконный кабель)
10Base-FB (оптоволоконный кабель)

следующие параметры
Сетевая топология – шина
Сетевой кабель – коаксиальный кабель
Скорость передачи

– 10 МБит/с
Максимальная длина сети – 2500 м
Максимальное количество узлов – 1024
Максимальная длина сегмента сети – 500 м
Максимальное количество узлов в одном сегменте – 100
Метод доступа – CSMA/CD
Метод кодирования – Манчестер-II

прекращает передачу и передает специальную 32-битную jam-последовательность, усиливающую коллизию
Длина паузы

при коллизии вычисляется по формуле
Длина паузы = L * 512 битовых интервалов (51,2 мкс),
где L – значение равномерной случайной величины из интервала [0, 2N],
N = max(10,номер_попытки_передачи)

временем был дополнен дополнительными спецификациями физического уровня
10Base-5 (толстый коаксиальный кабель)
10Base-2

(тонкий коаксиальный кабель)
10Base-T (витая пара)
10Base-FL (оптоволоконный кабель)
10Base-FB (оптоволоконный кабель)
Численные параметры перечисленных спецификаций мы рассмотрели в лекции 7 "Сетевые кабели"

что обусловлено историческими причинами
При использовании разных форматах возможна некорректная работа

аппаратного и программного обеспечения, но
современная аппаратура, как правило, способна работать с кадрами любого типа
Мы рассмотрим один из форматов (802.3/LLC)

байт содержат 10101010
последний байт – 10101011 (признак начала кадра, Start

of Frame Delimiter, SFD )
MAC-адрес приемника (6 байт)
MAC-адрес источника (6 байт)
Длина поля данных кадра (2 байта)
Поле данных (от 0 до 1500 байт)
Поле заполнения (от 0 до 46 байт)
если длина поля данных меньше 46 байт, данное поле дополняет данные до 46 байт
Контрольная сумма (4 байта)
Frame Check Sequence (FCS) содержит 32-разрядную циклическую контрольную сумму пакета (CRC-32)

10101010

10101010

10101010

10101010

10101010

10101010

10101010

10101011

SA (6 байт)

DA (6 байт)

Length (2 байта)

Data
(0-1500 байт)

FCS (4 байта)

версии Ethernet, в узком смысле Ethernet – это технология описанная

в стандарте IEEE 802.3, но большинство современных устройств поддерживают все версии
При отсутствии коллизий коэффициент использования сети имеет максимальное значение 0,96
В реальных условиях при коэффициентах использования сети больших 0,5 ее производительность резко падает из-за роста числа коллизий

альтернатива Ethernet
1980 г. – IBM разработала первый вариант Token Ring
1985

г. – принимается стандарт IEEE 802.5
Несмотря на то, что Ethernet является лидирующей технологией, миллионы узлов используют технологию Token Ring

– кабель витой пары
Скорость передачи – 4 или 16 МБит/с
Максимальная

длина кабеля – 100 м (STP)
Максимальная длина кольца – 4000 м
Максимальное количество узлов – 260
Метод доступа – маркерный доступ

При использовании кабеля неэкранированной витой пары
Максимальная длина кабеля – 45 м
Максимальное количество узлов – 72

захватить маркер на 10 мс (изъяв его из кольца)
За это

время узел может передать один или несколько кадров
Максимальный размер кадра – 4 Кбайт для 4 Мбит/с, 16 Кбайт для 16 Мбит/с

Т

кадр A

узел может освободить маркер сразу после завершения передачи кадра
Такой алгоритм

называется Early Marker Release – алгоритм раннего освобождения маркера

Т

кадр A

кадр D

могут назначаться приоритеты
Узел может захватить маркер только если приоритет его

сообщения не ниже приоритета маркера
Для контроля сети один из узлов выполняет роль активного монитора (выбирается при инициализации кольца, обычно – узел с максимальным MAC-адресом)
Создает маркер
Удаляет дубли маркера и кадры, не удаленные источником
Оповещает остальные узлы о своем присутствии (если в течении 7 секунд активный монитор не отправил специальный кадр, производятся его перевыборы)

3 различных формата кадров
Маркер
Кадр данных
Прерывающая последовательность

Delimiter (SD) размещается в начале каждого кадра
Он содержит четыре нестандартных

битовых интервала, которые не могут встречаться при передача битов данных
Управление доступом (1 байт, PPPTMRRR)
Access Control содержит следующие поля
PPP – приоритет
T – признак маркера доступа
M – признак того, что маркер передан активным монитором
RRR – зарезервировано
Конечный разделитель (1 байт)
End Delimiter (ED) размещается в конце каждого кадра
Он содержит четыре нестандартных битовых интервала, которые не могут встречаться при передача битов данных
I (Intermediate) – признак того, что кадр является последним в серии
E (Error) – признак ошибки (устанавливается любым узлом, обнаружившим в кадре ошибку)

SD (1 б)
XXXXXXXX

AC (1 б)
PPPTMRRR

ED (1 б)
XXXXXXIE

Delimiter, 1 байт)
Управление кадром (Frame Control, 1 байт)
Определяет тип кадра

(существует 6 типов управляющих кадров)
MAC-адрес получателя (Destination Address, 6 байт)
MAC-адрес отправителя (Source Address, 6 байт)
Данные (0-4 Кб или 0-16Кб)
Передаваемые данные или информация для управления обменом
Контрольная сумма (4 байта)
Frame Check Sequence (FCS) – CRC-32
Конечный разделитель (End Delimiter, 1 байт)
Статус кадра (Frame Status, 1 байт)
Позволяет определить, был ли пакет корректно принят получателем

SD (1 б)

ED (1 б)

FC (1 б)

DA (6 б)

DATA
0-16 Кб

SA (6 б)

FCS (4 б)

FS (1 б)

момент, но производительность ее оригинальной версии сильно деградирует при большой

нагрузке
Token Ring менее популярна, зато надежна и обеспечивает хорошую производительность даже при максимальной нагрузке

в сети

Принципы, технологии, протоколы. СПб: Питер, 2001.
Семенов Ю.А. Алгоритмы телекоммуникационных сетей. Часть

1. Алгоритмы и протоколы каналов и сетей передачи данных БИНОМ. Лаборатория знаний, Интернет-университет информационных технологий – ИНТУИТ.ру, 2007
Новиков Ю.В., Кондратенко С.В. Основы локальных сетей. М: ИНТУИТ.ру, 2005