Сеть ALOHA была разработана примерно в 1970 г. для обеспечения радиосвязи между центральной ЭВМ и различными терминалами данных, установленными в подразделениях Гавайского университета. Этот подход с использованием множественного доступа будет описан в разд. П.2.4, а сначала мы обсудим улучшенный вариант, называемый синхронная ALOHA. Основная идея этого алгоритма состоит в том, что каждый узел, не имеющий задолженности, просто передает новый поступивший пакет в первом окне после момента прихода, рискуя, таким образом, попасть в случайные конфликты, но это приводит к очень маленькой задержке, если конфликты возникают редко. Этот подход следует сравнивать с ВУ, при котором поступивший на один из т узлов пакет должен ожидать своей очереди на передачу в среднем m/2 окон. Таким образом, при синхронной системе ALOHA пакеты передаются почти немедленно, при этом иногда попадая в конфликты, тогда как при ВУ конфликты не возникают за счет больших задержек.
Когда в синхронной системе ALOHA возникает конфликт, в каждом узле, который передавал один из вступивших в конфликт пакетов, обнаруживается конфликт в конце окна и он становится задолжником. Если бы каждый узел с задолженностью просто повторял передачу в следующем окне, после того как оказался вовлеченным в конфликт, неизбежно возникал бы следующий конфликт. Вместо этого такие узлы пропускают некоторое случайное число окон перед повторной передачей.
Чтобы получить некоторое начальное интуитивное представление о синхронной системе ALOHA, мы начнем с поучительного, но не безупречного анализа. В силу предположения о бесконечном числе узлов (66) количество новых пакетов, переданных в окне, является пуассоновской случайной величиной с параметром l. Если повторные передачи узлов о задолженностью достаточно рандомизированы, то будет правдоподобной аппроксимация общего числа повторных передач и новых передач в заданном окне пуассоновской случайной величиной с некоторым параметром G > l.При таком приближении вероятность успешной передачи в окне равна Gе-G. Наконец, в состоянии равновесия скорость поступления l, в систему должна быть такой же, как скорость ухода Ge-G. Это соотношение иллюстрируется на рис. П.2.
Мы видим, что максимально возможная скорость ухода (согласно приведенному рассуждению) достигается при G = 1 и равна 1/e= 0,368. Мы также замечаем, правда, с некоторой неуверенностью в правоте, что для любой скорости поступления, меньшей, чем 1/е, существуют два значения G, при которых скорость поступления равна скорости ухода. Несовершенство этого элементарного подхода в том, что он не дает никакого представления о динамике системы. При изменении числа задолженных пакетов меняется параметр G; это ведет к обратному эффекту, приводящему к дальнейшему изменению числа задолженных пакетов. Чтобы понять эту динамику, следует проанализировать систему более тщательно. Однако приведенная простая модель правильно определяет максимальную пропускную способность синхронной ALOHA как равную 1/e и также показывает, что G, среднее число попыток передачи в окне, должно быть порядка 1, чтобы скорость передачи была близка к 1/е. При G < 1 появляется слишком много пустых окон, а при G > 1 возникает слишком много конфликтов.
Для построения более точной модели предположим, что каждый узел с задолженностью передает повторно с некоторой фиксированной вероятностью qrв каждом последующем окне до тех пор, пока не добьется успеха в передаче. Другими словами, число окон, которое проходит от конфликта до того момента, когда данный вовлеченный в конфликт узел произведет повторную передачу, является случайной величиной с геометрическим распределением, принимающей значение i>1 с вероятностью qr (1-qr)i-1. В первоначальной версии синхронной ALOHA применялось равномерное распределение момента повторной передачи, но это затрудняет анализ н не имеет ощутимых преимуществ по сравнению с геометрическим распределением. Мы будем использовать предположение ба об отсутствии буферов и примем несколько позже предположение 66 о бесконечном числе узлов.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.