Способ определения маршрута ретрансляции пакета сообщения и устройство для его осуществления
Использование о ретрансляции информации, в частности кв многопролетны.х космических системах связи с коммутацией пакетов сообщений на борту и методах маршрутизации в этих системах. Сущность изобретения: перемещающиеся в пространстве станции-ретрансляторы, расположенные ча спутниках, периодически вычисляют собственные координаты и координаты спутников-соседей Получив пакет сообщений, содержащий географические координаты (ГК) получателя, станции-ретрансляторы сравнивают эти координаты с имеющимися в памяти собственными и с соседними и передают пакет сообщений по маршруту, выбранному по минимальной разнице координат получателя и ретранслятора По прибытии следующего пакета этой серии, вычисления ГК получателя из его служебной части и сравнения их с заполненными, обработку пакета прекращают, если они совпадают, и отправляют его по заполненному маршруту Устройство содержит отправитель 1 пакета сообщений, станции (спутники)-ретрансляторы 2 и 3, получатель 4 пакета сообщений, приемник 5 служебной информации , блок 6 записи координат, приемник 7 пакетов , селектор 8 координат получателя, наоигационный датчик 9. навигационный блок 10, блок 11 памяти пакета, таймер 12, блок 13 памяти координат, блок 14 сравнения координат, блоки 15 и 25 памяти координат получателя, сравнивающий блок 16, блок 17 формирования служебного сигнала, блок 18 определения минмального значения, формирователь 19 импульсов считывания, блок 20 элементов Исключающее или блок 21 передатчиков, мультиплексор 22. блок 23 формирователей строба, блок 24 триггеров 1 зпф-лы, 2 ил
(в) RU (и) 2001532 С1 (51) 5 Н 04 В 7 185
Комитет Российской Федерации но патентам It товарным знакам ЛСЕСИЯКАм
ОПИСАНИЕ ИЗОБРЕТЕНИЯ, ипити-тниичны .
БИБЛИОТЕК
К ПАТЕНТУ (21) 5031334/09 (22) 31.0192 (46) 15.10.93 Бюл. Ия 37-38 (76) Пичугин Сергей Борисович (54) СПОСОБ ОПРЕДЕЛЕНИЯ МАРШРУТА
РЕТРАНСЛЯЦИИ ПАКЕТА СООБЩЕНИЯ И
УСТРОЙСТВО ДЛ Я ЕГО ОСУЩЕСТВЛЕНИЯ (57) Использование в ретрансляции информации, в частности кв многопропетны:х космических системах связи с коммутацией пакетов сообщений на борту и методах маршрутизации в этих системах
Сущность изобретения: перемещающиеся в пространстве станции-ретрансляторы, расположенные на спутниках, периодически вычисляют собственные координаты и координаты спутников-соседей. Получив пакет сообщений. содержащий географические координаты (ГК) получателя, станции-ретрансляторы сравнивают эти координаты с имеющимися в памяти собственными и с соседними и передают пакет сообщений по маршруту, выбранному по минимальной разнице координат получателя и ретранслятора. По прибытии спедуощего пакета этой серии, вычисления ГК получателя из его служебной части и сравнения их с заполненными, обработку пакета прекращают, если они совпадают, и отправляют его ло заполненному маршруту. Устройство содержит отправитель 1 пакета сообщений, станции (спутники)-ретрансляторы 2 и 3, получатель 4 пакета сообщений, приемник 5 служебной инфор— мации, блок б записи координат, приемник 7 пакетов, селектор 8 координат попу ателя, навигацион— ный датчик 9. навигационный блок 10, блок 11 памлти пакета, таймер 12, блок 1Э памлти координат, блок 14 сравнения координат, блоки 15 и 25 памяти координат получателя, сравнивающий блок 16, блок
17 формирования служебного сигнала, блок 18 определения минмального значения, формирователь
19 импульсов считывания, блок 20 элементов "Исключающее или" блок 21 передатчиков, мультиплексор 22, блок 23 формирователей строба, блок
24 триггеров. 1 зп.ф-лы, 2 ил.
2001532
Изобретение относится к ретрансляции информации, в частности к подвижным системам с коммутацией пакетов.
Известен алгоритм маршрутизации сообщений в разветвленной сети связи, включающий запись в устройстве памяти узла коммутации специальной таблицы, содержащей адреса абонентов и идентификаторы номеров соединительных линий, присоединенных к данному узлу. При поступлении пакета с адресом получателя этот адрес сравнивается с адресами специальной таблицы и пакет ретранслируется по всем линиям, адрес которых совпал с адресом получателя, зэ исключением той линии, по которой пришел пакет.
Недостатком известного алгоритма является большое время обработки пакета.
Это вызвано необходимостью перебора большого количества адресов, содержащихся в специальной таблице.
Наиболее близким по технической сущности и достигаемому эффекту к изобретению является метод маршрутизации пакетов в пакетной сети связи, включающий присвоение каждому узлу сети идентификатора с информацией об его географических координатах, адресацию пакета путем записи в его служебную часть индентификатора конечного получателя (т,е. последнего получающего узла). Когда промежуточный узел получэет пакет, то он по собственным координатам и координатам получателя определяет дэльность и направление (пеленг) на последнего. После этого он анализирует историю своего взаимодействия с соседними узлами (нэдежность связи с данным соседом, зэтрэчивэемую мощность и т.д.) и выбирает среди них один для того, чтобы ретранслировать ему пакет.
Недостатком данного метода, принятого зэ прототип, является большой объем производимых вычислений. Укаэанный недостаток обусловлен тем, что каждый узел сети обязан вести и помнить историю своего взаимодействия с соседними узлами.
Цель изобретения — сокращение вычислений, Для этого в предлагаемом способе определения маршрута ретрансляции пакета, включающем определение узлом собственных географических координат, прием пакета, выделение из его служебной части географических координат (ГК) получателя, определение направления ретрансляции и передачу пакета. дополнительно узлы периодически обмениваются собственными ГК с соседями и запоминают их, при выборе направления ретрансляции сравнивают ГК получателя с ГК собственными и тех сосе5
55 дей, чьи ГК получены не позднее заданного периода. и выбирают то направление, для которого разность ГК получателя и запомненных ГК минимальна, после этого координаты получателя и номер соответствующего направления, куда был пакет ретранслирован, запоминают отдельно, когда приходит следующий пакет, ГК его получателя сравнивают с последними и при их совпадении с другими ГК не сравнивают.
Кроме этого, с целью экономии бортовой памяти, при ретрансляции пакета запоминают отдельно соответствующую разность ГК получателя и запомненных ГК, а при приходе следующего пакета вначале вычисляют разность ГК его получателя и ГК, соответствующих данному направлению, сравнивают полученную разность с отдельно запомненной и при их совпадении прекращают сравнивать ГК получателя с другими ГК.
На фиг.1 приведена структурная схема многопролетной спутниковой сети,содержащая отправитель 1 пакета сообщения; промежуточный спутник-ретранслятор 2, получивший пакет; промежуточный спутник-ретранслятор 3, которому был ретранслирован предыдущий пакет; получатель 4 пакета сообщения с координатами Хп, Yn,Hà фиг.2 приведена функциональная схема устройства, реализующего заявляемый способ.
Она содержит приемник 5 служебной информации (географических координат) от соседних спутников-ретрансляторов; блок 6 записи координат; приемник 7 пакетов; селектор 8 координат получателя; навигационный датчик (ИК-вертикаль) 9; навигационный блок 10; блок 11 памяти пакета; таймер 12; блок 13 памяти координат спутников; блок 14 сравнения координат; блок 15 памяти координат получателя; сравнивающий блок 16; блок 17 формирования служебного сигнала о географических координатах спутника-ретранслятора; блок 18 определения минимального значения; формирователь 19 импульсов считывания; блок 20 элементов "ИСКЛЮЧАЮЩЕЕ ИЛИ" блок 21 передатчиков; мультиплексор 22; блок 23 формирователей строба; блок 24 триггеров; второй блок 25 памяти координат получателя.
Способ определения маршрута ретрансляции пакета заключается в следующем.
Спутники-ретрансляторы 2 и 3 и другие, перемещаясь в пространстве относительно
Земли, периодически (обмениваются) вычисляют географические координаты своего местоположения (в проекции на земную поверхность). Этими координатами, также периодически, они обмениваются с
2001532 ближайшими соседями. Таим образом, каждый спутник имеет информацию о координатах собственных и соседей, Если сосед вышел иэ строя (неисправность, перегрузка и т.д.) и не передал свои координаты эа текущий период обмена, то информация о его координатах на соседних спутниках стирается. При восстановлении работоспособности она может быть возобновлена.
Получив пакет, спутник-ретранслятор иэ его служебной части выделяет географические координаты получателя 4 (их записывает отправитель 1 пакета), сравнивает с географическими координатами собственными и соседей и передает пакет тому соседу, разность координат которого и получателя оказалась минимальной.
Отправив пакет спутник запоминает координаты его получателя и номер направления в котором был отослан этот пакет.
Когда приходит следующий пакет, то выделенные из его служебной части географические координаты получателя вначале сравниваются с теми, что были запомнены при передаче предыдущего пакета. Если они совпали, то обработку пакета прекращают и отсылают его по запомненному направлению.
Таким образом, в том случае, когда передача пакетов ведется сериями, время обработки пакета сокращается. Помимо этого, время обработки сокращается иэ-за того, что выбор направления ретрансляции пакета проводят лишь исходя иэ информации о координатах ближайших соседей.
Пример 1. Отправитель 1 отправляет пакет сообщения получателю 4, Этот пакет достигает спутника 2, который, сравнив координаты Х>УП получателя с координатами . четырех (Х1У1, XzY2, ХЗУэ и Х4У4) соседних спутников и собственными ХрУр, ретранслирует пакет спутнику 3, поскольку (Х4 Хп) = мин; (У4 Уп) = мин;
Координаты ХпУп и номер направления на спутник 3 спутник 2 запоминает. По приходе следующего пакета, в котором записаны координаты получателя Х и У с ХлУл, если они совпали, отсылает в направлении спутника 3, Устройство для определения маршрута ретрансляции пакета работает следующим образом, Приемник 7 принимает пакет, передает его в блок памяти 11. где пакет запоминается, и в селектор 8, где из служебной части пакета выделяются координаты получателя
Хпуп, Структура пакета следующая: заголовок с Хпуп и другой служебной информацией (сообщение). трейлер со служебной информацией, Выделенные Хпуп поступают в блок памяти 15, а оттуда попадают на сравнивающий блок 16, где сравниваются с хранящимися в блоке 25 координатами получателя предыдущего пакета XlYl, Если XlYl=
= ХпУП, то на соответствующем выходе блока
16 (выход "Да") появляется импульс, запускающий формирователь 19 и считывающий информацию о направлении передачи пред"0 ыдущего пакета, записанную в блоке 24 триггеров, Импульс формирователя 19 считывает пакет из блока 11, который поступает на мультиплексор 22. Коммутация этого входа мультиплексора 22 с его соответствующим выходом осуществляется блоком 23 формирователей строба по соответствующей шине. В блоке 23 соответствующий формирователь запускается от блока 24 триггеров через блок 20, Пакет от блока 11
20 через мультиплексор 22 попадает на передатчик 21 и излучается следующему узлу или получател ю.
Если XIYI и ХпУП не совпали, то íà выходе "Нет" блока 16 формируется сигнал, запускающий блок сравнения 14, в котором вычисляются разности координат получателя и спутников. Эти разности поступают в блок 18, который определяет среди этих разностей и формирует на соответствующем выходе импульс для запуска формирователя иэ блока 23, а также импульс, запускающий формирователь 19, Импульсом блока 19 пакет из блока 11 считывается и поступает на мультиплексор
35 22 и далее на соответствующий передатчик блока 21.
При этом блок 20 не пропускает сигнал от блока триггеров 20 для запуска формирователей блока 23.
Сформированный в блоке 23 строб коммутирует соответствующий выход мультиплексора 22 и устанавливает соответствующий триггер блока 24 в "1"— это запоминается направление. Координа45 ты отправителя ретранслированного пакета импульсом блока 19 переписываются из блока 15 в блок 25, где хранятся до прихода следующего пакета.
Кроме того, спутники периодически обмениваются координатной информацией.
При этом Спутник определяет собственные координаты в блоке 10, куда поступают навигационные сигналы от датчика 9, запоминает свои координаты в блоке памяти 13, куда они поступают через блок записи координат. управляемый таймером.
Собственные координаты спутник передает ближайшим соседям, при этом координаты иэ блока 10 поступают в блок 17 формирования служебного сигнала и через
2001532 мультиплексор, который подключает соответствующие передатчики блока 21.
Работой мул ьтиплексора,управляет также блок 23, но запускаются в этом случае несколько формирователей импульсом от блока 17.
Формула изобретения
СНОСОВ 01!РЕДЕЛЕ11НЯ МЛРП11 У 1 A РЕ11 Л!1СЛЯ!
1!11! 11лкетл сООБпье1(ия и устРОЙстВО для
ЕГО ОСУЩЕСТВЛЕ11!!Я
1. Способ определения маршрута ретрансляции пакета сообщения, включающий пеРедачу пакета сообщений отправителем, прием пакета сообщений ближайшей станцией-ретранслятором. выделение из его служебной части географических координат (ГК) получателя. выбор направления
15 ретрансляции и прием пакета сообщений
20 получателем, отличающийся тем, что на станциях-ретрансляторах периодически определяют их собственные ГК и ГК соседних станций-ретрансляторов, запоминают их на заданный период, а ГК получателя, 25 содержащиеся в пакете сооб цений, сравнивают с запомненными ГК станций-ретрансляторов и выбирают для ретрансляции наименее удаленную от получателя станцию-ретранслятор и ретранс- 30 лируют через нее пакет сообщений, при этом запоминают на станциях-ретрансляторах номер маршрута отосланного пакета сообщений, а после получения следующего пакета этой серии выделяют иэ его служеб- 35 ной части ГК получателя. сравнивают с запомненными ГК предыдущего пакета и передают пакет сообщений по запомненному маршруту, кроме того. в служебную часть пакета сообщений записывают информацию о текущем числе ретрансляций, 2. Устройство для определения маршрута ретрансляции пакета сообщений, содержащее на станции-РетРанслятоРе 45 последовательно соединенные приемник пакетов сообщений, селектор географических координат получателя, первый блок памяти ГК получателя, а также блок памяти пакета, приемник служебной информации и блок передатчиков, отличающееся тем, что введены последовательно соединенные навигационный датчик, навигационный блок, блок записи координат, блок
nBM1!TN координат, блок сравнения координзт, блок определения минимального знаПринятый служебный сигнал приемником 5 записывается в блок 13 памяти координат с помощью блока 6 записи координат. (56) Патент США М 4939726, кл. Н 04 J 3/26, 1989. чения (min), блок элементов
ИСКЛЮЧАЮЩЕЕ ИЛИ, блок формирователей строба и мультиплексор, а также сравнивающий блок, второй блок памяти
ГК, блок триггеров. формирователь импульсов считывания, таймер, блок формирования служебного сигнала, причем первый вход блока памяти пакета подключен к выходу приемника пакетов, а второй вход, обьединенный с вторым входом первого блока памяти ГК получателя, соединен с выходом формирователя импульсов считывания, первый вход которого подключен к импульсному выходу блока определения min, а второй вход соединен с выходом "Да" сравнивающего блока и с управляющим входом блока триггеров, выход которого соединен с вторым входом блока элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, управляющий вход которого подключен к тактовому выходу блока формирования служебных сигналов, сигнальный выход которого соединен с первым входом мультиплексора, второй вход которого подключен к выходу блока памяти пакета, при этом управляющий вход мультиплексора обьединен с входом блока триггеров, а выход соединен с блоком и передатчиков, причем первый выход первого блока памяти ГК получателя соединен с первым входом сравнивающего блока и с первым входом блока сравнения координат, вход запуска которого подключен к выходу "Нет" сравнивающего блока, второй вход которого соединен с выходом второго блока памяти
ГК получателя, вход которого подключен к второму выходу первого блока памяти ГК получателя, при этом обьединенные тактовые входы навигационного блока и блоков записи координат, памяти координат и формирователя служебных сигналов соединены с выходом таймера, а выход приемника служебной информации подключен к второму входу блока записи координат, причем вход блока формирования служебных сигналов соединен с выходом навигационного блока.
2001532
Р ---l (l хд
7 g/ Я
/ / х
Фиг?
Заказ 3133
Тираж Подписное
НПО"Поиск" Роспатента
113035, Москва, Ж-35, Раушская наб., 4/5
Производственно-издательский комбинат "Патент", с. Ужгород, ул,Гагарина, 101
Составитель С.Пичугин
Редактор А,Купрякова Техред М.Моргентал Корректор M.ÌàêñèìèUjèíåö
