Э. Таненбаум, Д. Уэзеролл - Компьютерные сети (1114668), страница 82
Текст из файла (страница 82)
При таких параметрах скоростьобслуживания канала равна μC кадров в секунду. Теория массового обслуживанияговорит о том, чтоT=1.µC ! "(Для любознательных: это результат для очереди M/M/1. Требуется, чтобы случайность длительности промежутков между кадрами и длины кадров соответствовалиэкспоненциальному распределению или, что эквивалентно, являлись результатомпуассоновского процесса.)В нашем примере C равно 100 Мбит/с, средняя длина кадра 1/μ = 10 000 бит, скорость прибытия кадров λ = 5000 кадров в секунду. Тогда T = 200 мкс.
Обратите внимание: если бы мы не учли задержки при формировании очереди и просто посчитали,сколько времени нужно на передачу кадра длиной 10 000 бит по сети с пропускнойспособностью 100 Мбит/с, то получили бы неправильный ответ: 100 мкс. Это числоприемлемо лишь при отсутствии борьбы за канал.Теперь давайте разделим канал на N независимых подканалов, у каждого из которых будет пропускная способность C/N бит/с. Средняя входная скорость в каждомподканале теперь будет равна λ/N кадров в секунду.
Сосчитав новое значение среднейзадержки T, получим:TN =1N== NT .µ(C/N) ! ("/N) µC ! "(4.1)Это означает, что для поделенного на несколько частей канала значение средней задержки стало в N раз хуже значения, которое было бы в канале, если бы все кадры быликаким-то волшебным образом организованы в одну общую очередь. Этот результаттакже демонстрирует, что в холле банка, где установлены банкоматы, лучше организовать людей в общую очередь, из которой они будут подходить к освободившимсямашинам, чем сохранять отдельную очередь к каждому банкомату.Аргументы, применимые к FDM, можно отнести и к другим способам статическогораспределения канала.
Если использовать временное уплотнение (TDM, Time Division284 Глава 4. Подуровень управления доступом к средеMultiplexing — мультиплексная передача с временным разделением) и выделятькаждому пользователю N-й интервал времени, то если интервал не используется абонентом, он просто пропадает. С тем же успехом можно разделить сети физически. Есливзять 100-Мбитную сеть и сделать из нее десять 10-Мбитных, статически распределивпо ним пользователей, то в результате средняя задержка возрастет с 200 мкс до 2 мс.Таким образом, ни один статический метод распределения каналов не годится дляпульсирующего трафика, поэтому далее мы рассмотрим динамические методы.4.1.2.
Допущения, связанные с динамическимраспределением каналовПрежде чем приступить к рассмотрению многочисленных методов распределенияканалов, следует тщательно сформулировать решаемую проблему. В основе всех разработок в данной области лежат следующие пять допущений.1. Независимый трафик. Модель состоит из N независимых станций (компьютеров,телефонов, персональных средств связи и т. д.), в каждой из которых программаили пользователь формирует кадры для передачи.
Ожидаемое число кадров в интервале времени Δt равно λΔt, где λ является константой (скорость прибытия новыхкадров). Как только кадр сформирован, станция блокируется и ничего не делает,пока кадр не будет успешно передан.2. Предположение о едином канале. Единый канал доступен для всех. Все станциимогут передавать и принимать данные по нему. Все станции считаются равными,хотя программно протокол может устанавливать для них различные роли (например, приоритеты).3. Наблюдаемые коллизии.
Если два кадра передаются одновременно, они перекрываются по времени, в результате сигнал искажается. Такое событие называется конфликтом, или коллизией. Все станции могут обнаруживать конфликты.Искаженный вследствие конфликта кадр должен быть передан повторно. Другихошибок, кроме тех, которые вызваны конфликтами, нет.4.
Непрерывное или дискретное время. Время может считаться непрерывным, и тогда передача кадров может начаться в любой момент. В противном случае время может быть разделено на дискретные интервалы (такты, иногда называемые слотами).Передача кадра может начаться только с началом такта.
Один временной интервалможет содержать 0, 1 или более кадров, что соответствует свободному интервалу,успешной передаче кадра или коллизии соответственно.5. Контроль несущей или отсутствие контроля. Если контроль несущей выполняется, станции могут определить, свободна или занята линия, до ее использования.Если канал занят, станции не будут пытаться передавать кадры по нему, пока он неосвободится. Если контроля несущей нет, то станции не могут определить, свободна или занята линия, пока не попытаются ее использовать.
Они просто начинаютпередачу. Только потом они могут определить, была ли передача успешной.О приведенных выше допущениях следует сказать несколько слов. Первое допущение утверждает, что кадры прибывают независимо друг от друга, как на разные4.1. Проблема распределения канала 285станции, так и в пределах одной станции, а также, что кадры формируются непредсказуемо, но с постоянной скоростью.
В действительности, это не очень хорошаямодель сетевого трафика, поскольку хорошо известно, что пакеты прибывают целымипоследовательностями в определенные диапазоны временной шкалы (Paxson, Floyd,1995; Leland и др., 1994). Тем не менее пуассоновские модели, как их часто называют,полезны, так как легко описываются математически. Они помогают анализироватьпротоколы, составляя общее представление об изменении производительности с течением времени и о разнице между различными реализациями.Допущение о едином канале является, на самом деле, центральным в данной модели.
Никаких внешних каналов связи нет. Станции не могут тянуть руки, привлекаяк себе внимание и убеждая учителя спросить их. Поэтому приходится искать лучшеерешение.Оставшиеся три допущения зависят от инженерной реализации системы, поэтомупри изучении конкретных протоколов мы будем указывать, какие допущения следуетсчитать верными.Допущение о коллизиях является основным. Станциям необходим способ обнаружения коллизий, если они собираются повторно пересылать кадры, а не миритьсяс их потерей. Для проводных каналов можно использовать оборудование, умеющееопределять коллизии. В этом случае станции заранее обрывают передачу, чтобы незасорять канал. В беспроводных каналах распознавать коллизии намного сложнее; обих возникновении приходится узнавать по факту, когда не прибывает ожидаемый кадрподтверждения. Также возможно успешное получение некоторых кадров, попавшихв коллизию, — это зависит от типа сигнала и оборудования на получающей стороне.Подобные ситуации встречаются нечасто, поэтому будем предполагать, что все кадры,участвующие в коллизии, попросту теряются.
Кроме того, мы познакомимся с протоколами, специально предназначенными для предотвращения коллизий, а не решениясоздаваемых ими проблем.Причина, почему для времени существует два альтернативных допущения, заключается в том, что дискретное время помогает иногда повышать производительность.Однако использующие его станции должны синхронизироваться с главными часамиили друг с другом. Это не всегда возможно. Мы рассмотрим оба варианта. В каждойконкретной системе работает только одно из возможных допущений.Аналогично этому, контроль несущей также реализован не во всех системах. Проводные сети обычно знают, когда линия занята, однако в беспроводных сетях контролянесущей чаще всего нет, потому что отдельно взятая станция не может «слышать» всеостальные из-за разницы частотных диапазонов.
Аналогично, в некоторых условиях,когда станция не может напрямую общаться с другими станциями (например, им приходится пересылать информацию через кабельный модем, играющий роль центрального узла), контроль несущей бывает недоступен. Обратите внимание на слово «несущая».В данном случае оно означает электрический сигнал, распространяющийся по каналу.Для того чтобы избежать недопонимания, стоит заметить, что ни один протоколколлективного доступа не гарантирует надежную доставку. Даже в случае отсутствияколлизий получатель может по каким-то причинам неправильно скопировать частькадра.
Надежность обеспечивают другие составляющие канального или более высоких уровней.286 Глава 4. Подуровень управления доступом к среде4.2. Протоколы коллективного доступаИзвестно множество алгоритмов коллективного доступа. В следующих разделахбудут рассмотрены наиболее интересные алгоритмы и даны примеры их примененияна практике.4.2.1. Система ALOHAИстория нашего первого MAC начинается на нетронутых цивилизацией Гавайяхв 1970-х годах. В данном случае «нетронутые цивилизацией» означает «не имеющиерабочей телефонной системы». Это не упрощало жизнь исследователя НорманаАбрамсона (Norman Abramson) и его коллег из Гавайского университета, которыепытались подключить пользователей на удаленных островах к главному компьютерув Гонолулу.
Идея протянуть кабели по дну Тихого океана даже не рассматривалась,так что исследователи искали другое решение.Найденное решение основывалось на использовании радиосистемы ближнегорадиуса действия. Терминал каждого пользователя передавал кадры на центральныйкомпьютер в пределах общей полосы частот. Также присутствовал простой и элегантный метод решения проблемы распределения каналов. Их труды впоследствии сталиосновой многих исследований (Schwartz, Abramson, 2009). Хотя в работе Абрамсона,получившей название системы ALOHA, использовалась широковещательная радиосвязь со стационарными передатчиками, основная идея применима к любой системе,в которой независимые пользователи соревнуются за право использования одногообщего канала.В данном разделе мы рассмотрим две версии системы ALOHA: чистую и дискретную.
Они отличаются тем, непрерывно ли время (чистая версия) или делится надискретные интервалы, в которые должны помещаться все кадры.Чистая система ALOHAВ основе системы ALOHA лежит простая идея: разрешить пользователям передачу,как только у них появляются данные для отсылки. Конечно, при этом будут столкновения, и столкнувшиеся кадры будут разрушены. Отправителям необходимо уметьобнаруживать такие ситуации. В системе ALOHA, после того как каждая станцияотправляет свой кадр центральному компьютеру, этот компьютер рассылает полученный кадр на все остальные станции. Отправитель прослушивает широковещательнуюпередачу, чтобы понять, насколько успешной была передача. В других системах, такихкак проводные локальные сети, у отправителя может быть возможность распознаватьколлизии во время передачи.Если кадр был уничтожен, отправитель просто выжидает некоторое случайноевремя и пытается переслать этот кадр снова.
Время ожидания должно быть случайным. В противном случае, при равных фиксированных интервалах времени ожиданияколлизии будут повторяться снова и снова. Системы, в которых несколько пользователей использует один общий канал таким способом, что время от времени возникаютконфликты, называются системами с конкуренцией.4.2. Протоколы коллективного доступа 287На рис. 4.1 показан пример формирования кадров в системе ALOHA. Все кадры нанашем рисунке имеют один размер, так как при этом пропускная способность системыстановится максимальной, именно за счет единого фиксированного размера кадров.Рис.
4.1. В чистой системе ALOHA кадры передаются в абсолютно произвольное времяКогда два кадра одновременно пытаются занять канал, они сталкиваются, и происходит коллизия (как видно на рис. 4.1). Оба кадра искажаются. Даже если только одинпервый бит второго кадра перекрывается с последним битом первого кадра, оба кадрауничтожаются полностью (их контрольные суммы не совпадут с правильными значениями). При этом оба кадра должны быть переданы позднее повторно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
