Алгоритм двоично-экспоненциальной отсрочки

⇐ ПредыдущаяСтр 15 из 16Следующая ⇒

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

С учетом этой особенности видоизменим систему допущения( допущение №3): если абонент передает в окно, то к концу данного окна абонент достоверно узнает о том, какое из двух событий (У, К) произошли в окне. Если абонент не передает в окне, то абонент в этом окне никакой информации о событиях не сообщает.

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

К К У

х х

Х Х х

- очередь сообщений

Абонент может захватить на долгое время канал – не очень хорошо, такое явление носит название «эффект несправедливости».

Изменим идею, чтобы избежать несправедливости: если произошел успех и у абонента в буфере есть следующее сообщение, то он передает это сообщение с вероятностью Р₀ 1.

Введем ограничения – имеет смысл уменьшить вероятность до Р_min = , М – общее число абонентов.

Особенности реализации алгоритма в реальных системах

Алгоритм АЛОХА можно реализовать другим способом. Сравним ранее рассмотренный вариант – вероятностный с альтернативным вариантом – интервальным.

P вероятностный

P P P

max(I₁) =

M =

Pr = P

Pr = (1 – P)

W (интервальный)

W=const

I₂

Случайным образом на интервалах выбирает окно для передачи

max(I₂) = W

Pr =

M = M

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

= P =

I₁=

M =

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

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

Поясним это на временной диаграмме

И l П

t_c

t_c = – длительность передачи сообщения

где, с – скорость света

b – длина сообщения

х – скорость передачи

<< t_c

Замечание. У спутников связи соотношение нарушается.

С учетом отмеченной особенности абонент узнает о событии в канале за время существенно меньшее, чем время передачи (t_c).

Рис.3.14. Пример реальной системы

И₂ перед своей передачей «слушает канал» в течение некоторого времени. Он должен слушать время = максимальному времени распространения сигнала в системе.

Источник должен слушать канал , т.к. сигналы отражаются.

После окончания передачи источник принимает решение, передавать или нет, в соответствии с одним из ранее рассмотренных алгоритмов сл. доступа.

Описанная в данном примере идея реализована в стандарте Wi-Fi. Упрощенную работу стандарта IEEE 802.11х (х – версия стандарта) можно описать временной диаграммой:

И₁ кв

W₀

П₁ кв К

Т_ож

И₂

И₃

Рис.3.15. Работа стандарта IEEE 802.11.

Используя случайный механизм, И₂ и И₃ начинают передавать сообщения. Возможна ситуация, что их сообщения наложатся. В результате происходит конфликт, получатели не сформируют квитанции.

Анализ работы

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

Видоизменим допущения:

1) – время работы системы разбито на окна, длительность окна зависит от того события, которое происходит в окне.

Т_п = – длительность пустого окна;

Т_у = от начала передачи сообщения до получения квитанции;

Т_к = время передачи сообщения + время, оговоренное в стандарте на ожидание квитанции.

Т_п Т_у Т_к

Условно можно считать, что абоненты могут передавать сообщения в канале окна, т.к. меньше окон.

Проанализируем работу алгоритма АЛОХА для новой модели. Для упрощения вычислений будем считать, что

Т_у = 1, Т_к = 1 Т_п =

Ранее мы рассматривали случай, где = 1, _кр= е^-1, р =

Повторим вывод для _кр:

Р =

– интенсивность входящего потока

N = = =

= =

N =

М ^М-1 = = ^М-1 е^-1

= (1 – р)^м = = ^М е^-1

= 1 1 – 2е^-1

_кр N

Предположим, что Т_у = 1, а Т_к = Т_п = 0 _кр = 1 (подумайте, почему это так).

Сетевой уровень

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

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

10.14.01.20

Пример.

32 бита

Классификация IP - адресов

2³²

Множество Multicast. Может

быть доставлен несколькими получателями.

Множество Unicast адресов. Пакет, посланный по этому адресу может быть доставлен только одному получателю.

U ⋂ M = Ø

Служебные(127.0.0.1)

Рис. 4.1. Классификация IP- адресов

Вопросы: Как по IP-адресу определить, к U или M он относится? Чему равняется мощность множества U, M ?

Структура IP-пакета

Данные на сетевом уровне передаются с помощью так называемых IP-пакетов. Упрощенно структуру заголовка можно описать следующим образом:

t жизни

КС

Длина пакета

IP получателя

IP источника

ЗЗ

32 бита

8 бит

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

Сначала значение поля контрольной суммы устанавливается в 0. Затем заголовок разбивается на 16-битные числа. Эти числа складываются. Если в результате получилось число на более, чем 16 бит - оно тоже разбивается на два 16-битных числа; суммируем их. Полученное число переписываем в бинарном виде и инвертируем (ноль - в единицу, единицу - в ноль). Результат записывает в поле "Контрольная сумма".

В поле «время жизни пакета» некоторое значение. При прохождении определенного узла значение уменьшается на 1, если оно обнуляется, то пакет удаляется.

Понятие о маршрутных таблицах

Рассмотрим пример: пусть имеется фрагмент сети, и в соответствии с некоторыми правилами зафиксированы маршруты( в реальной сети маршруты могут меняться в зависимости от загрузки канала и промежуточных узлов).

IP₁ IP₄

IP₂IP₃IP₅

IP₉ IP₈IP₆IP₇

При элементарном построении маршрутных таблиц возникает проблема с тем, что в каждом промежуточном узле требуется хранить список IP-адресов, которые могут быть достигнуты из этого узла.

№	IP
1	IP₄
2	IP₉

Задание: самостоятельно разобраться с решением этой проблемы.

Маршрутная таблица – информация, которая хранится в каждом узле, используя которую, можно понять, куда дальше передать пакет.

Дата добавления: 2018-06-01; просмотров: 811; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 7 8 9 10 11 12 13 141516 Следующая ⇒

Мы поможем в написании ваших работ!