ExOR (протокол беспроводной сети) - ExOR (wireless network protocol)

Чрезвычайно оппортунистическая маршрутизация (ExOR) это комбинация протокол маршрутизации и контроль доступа к медиа для беспроводная одноранговая сеть, изобретенный Санджит Бисвас и Роберт Моррис из Лаборатория искусственного интеллекта Массачусетского технологического института и описан в статье 2005 года.[1] Очень похожая оппортунистическая схема маршрутизации была также независимо предложена Чжэньчжэнь Е и Инбо Хуа из Калифорнийский университет, Риверсайд и представлен в статье в 2005 году.[2]Ранее с открытым исходным кодом,[3] ExOR был доступен в 2005 году, но больше не доступен. Стратегии широковещательной и ретрансляции, используемые алгоритмом, уже описаны в литературе.[4][5][6][7][8][9] ExOR ценен тем, что может управлять доступными цифровыми радиостанциями для использования некоторых ранее непрактичных алгоритмических оптимизаций.

История

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

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

Прототип этого протокола был RoofNet, и многие авторитеты[кто? ] считают, что это протокол доступа к среде, развернутый Мераки телеграфировать Сан-Франциско.

Алгоритм

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

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

ExOR использует обычный протокол маршрутизации «RRTc» для сбора информации о вероятности успешной передачи между каждой парой цифровых радиостанций в сети.

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

Во-первых, на основе информации о маршрутизации передающая радиостанция составляет список радиостанций, которые могут пересылать данные от отправляющей радиостанции к месту назначения. Номера радиостанций помещены в список отсортированный по расстоянию до пункта назначения, от ближайшего до самого дальнего. Радиостанция назначения находится во главе списка. Кроме того, исходная радиостанция запускает список пакетов в пакете, чтобы измерить ход пакетов. Эта «пакетная карта» представляет собой массив номеров радиостанций, по одному на пакет. Каждый номер радиостанции - это радиостанция, которая передала этот пакет и была ближайшей к радиостанции назначения. Каждый пакет данных имеет список радиомодулей, и пакеты помещаются впереди. Список экономит место в каждом пакете за счет использования номеров радиостанций, а не IP-адресов. Затем радиостанция-отправитель передает первый пакет пакетов данных. Запускает таймер. Радиостанции, которые получают пакет, но не находятся в списке пакета, игнорируют пакеты данных. Эти радиостанции выбрасывают пакеты, как только они получены. Радиомодули, которые находятся в списке радиостанций пакета, сохраняют полученные пакеты данных. Они также обновляют свою пакетную карту. Когда время ожидания радиостанции истекает, она передает пакеты, которые ни одна радиостанция ближе к месту назначения не передала повторно. Эти пакеты включают в себя лучшую доступную информацию радиостанции о продвижении пакетов в пакете (то есть его пакетную карту). В частности, пакетная карта каждого пакета содержит радио-номер ретранслятора для каждого пакета, который он повторно передает. Когда радиостанция получает пакет, отправленный от радиостанции, которая находится ближе к месту назначения, она стирает свою собственную копию этого пакета. Нет необходимости повторно передавать этот пакет. Однако он также обновляет свою пакетную карту о ходе обработки пакетов в пакете. Таким образом, информация о продвижении пакетов течет обратно к источнику, поскольку радиостанции, находящиеся дальше от пункта назначения, обновляют свои пакетные карты, перехватывая повторные передачи.

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

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

Поскольку основной интернет-протокол TCP отправляет поток данных, ExOR использует локальные прокси-серверы данных для накопления блоков данных.

Преимущества и недостатки

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

Нет признать пакеты, и никаких коллизий с ними. Это экономит время радио.

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

Авторы говорят, что разница во времени доставки составляет 1/4 от других специальных сетей, и приписывают это использованию алгоритмом наилучшего доступного времени доставки.

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

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

Тестирование

Оценки эффективности ExOR основаны на реальной реализации с Linux набор инструментов для маршрутизации под названием click. Экспериментальные версии программного обеспечения были смоделированы и установлены в сети на крыше под названием "RoofNet" в Кембридже, штат Массачусетс. Эти данные сравнивались с опубликованными данными для аналогичной сети.[10]

Смотрите также

использованная литература

  1. ^ ExOR: Opportunistic Multi-Hop Routing для беспроводных сетей Санджит Бисвас, Роберт Моррис, Представлено на SIGCOMM '05, 2005, Copyright ACM, Philadelphia, Penn. 2005, ACM № 1-59593-009-4 / 05/0008
  2. ^ О политиках канального уровня пересылки данных через беспроводные реле Чжэньчжэнь Е, Инбо Хуа, Представлено на IEEE MILCOM '05, 2005, Copyright IEEE, Атлантик-Сити, Нью-Джерси, октябрь 2005 г.
  3. ^ [1][постоянная мертвая ссылка ]
  4. ^ «Использование распределенного пространственного разнообразия в сетях», Дж. Н. Ланеман, Г. Уорнелл; Анализирует некоторые теоретико-информационные схемы кооперативного разнесения, но радиостанции используют специальные методы для совместного использования спектра. ExOR адаптирует схему временных интервалов к более длительному масштабу времени, который может быть реализован в программном обеспечении с использованием обычных радиостанций.
  5. ^ «Выборочная переадресация с разнесением в многоскачковой сети пакетной радиосвязи с замирающими каналами и захватом», П. Ларссон, SIGMOBIL Mob. Comm. Ред. 5 (4): 47-564, 2001.
  6. ^ "OAR, Оппортунистический доступ к мультимедиа для многоскоростных сетей", Б. Садеги, В. Канодиа, А. Сабхарвал и Э. Найтли; Материалы ACM Mobicom 2002, сентябрь 2002 г.
  7. ^ «Использование разнесения путей в беспроводных одноранговых сетях канального уровня», Proc. 6-го симпозиума IEEE WoWMoM, июнь 2005 г.
  8. ^ «MAC Layer Anycasting в беспроводных сетях», Р. Рой Чоудхури и Н. Вайдья, Второй семинар по горячим темам в сетях (HotNets II), ноябрь 2003 г.
  9. ^ «Географическая случайная пересылка (GeRaf)», М. Зорзи, Р. Рао, IEEE Transactions on Mobile Computing, 2 (4), октябрь 2003 г.
  10. ^ «Измерения уровня канала в ячеистой сети 802.11b», Д. Агуайо, Дж. Бикет, С. Бисвас, Дж. Джадд и Р. Моррис; ACM SIGCOMM 2004, август 2004 г.