УЗЛОВОЕ УСТРОЙСТВО И ПРОГРАММА
NODE DEVICE AND PROGRAMME

Область техники, к которой относится изобретение
Настоящее изобретение относится к устройству и программе, способным выбирать маршрут в сети, содержащей множество узлов.
Уровень техники
По сетевым устройствам было проведено много исследований. Наиболее распространенное сетевое устройство использует IP-сеть (протокол маршрутизации в среде Интернет). MPLS (многопротокольная коммутация с использованием меток) является сетевым устройством, имеющим механизм автоматического создания маршрута. Кроме того, существуют AODV (заказной вектор по требованию) и OLSR (оптимизированная маршрутизация в соответствии с состоянием линии связи).
В устройстве IP-сети маршрут определяется в соответствии с IP-адресом. Поскольку IP-адрес имеет древовидную структуру, кадр может быть передан на конечный целевой терминал, передавая верхнюю часть IP-адреса на сетевое устройство, управляющее согласованием IP-сети. Маршрут определяется системой IP-адресов. То, какое сетевое устройство управляет какой IP-сетью, регулируется таблицей маршрутизации. Таблица маршрутизации устанавливается, главным образом, вручную, но может также автоматически обновляться с помощью RIP (протокола обмена данными для маршрутизации). RIP является системой широкого вещания для окружающих в IP-сети, управляемой сетевым устройством, и для подтверждения IP-сети, управляемой каждым сетевым устройством.
В MPLS сети разделены на сетевые устройства, называемые LSR (маршрутизаторы с коммутацией по меткам), и внешние сети. Кадр из внешней сети забирается во внутреннюю сеть сетевым, охватывающим внешнюю сеть и внутреннюю сеть устройством, называемым краевым узлом. В этом случае метка вставляется в заголовок внешнего кадра. Каждый LSR имеет таблицу передачи меток. Таблица передачи метки хранит метку входного кадра, метку выходного кадра и адресата. LSR восстанавливает метку входного кадра, находит соответствующую метку в таблице передачи меток, перезаписывает метку в метку выходного кадра и передает его соответствующему адресату. Это выполняется с помощью LDP (протокол распределения меток) таблицы передачи меток. LDP сначала создает таблицу маршрутизации с помощью RIP и т.д., добавляет к таблице метку и передает уведомление между соседними узлами.
AODV является способом нахождения маршрута к целевому узловому устройству после того, как другое узловое устройство связи узлов повторяет широковещательную передачу, используя ее при поиске маршрута. Узловое устройство связи передает кадр, называемый "запрос маршрута (RREQ)", окружающим, чтобы найти целевой маршрут. Кадр описывает идентификатор целевого узла связи, который должен быть восстановлен. Когда окружающее узловое устройство связи не восстанавливается само, оно вновь создает кадр RREQ и повторно выполняет широковещательную передачу окружающим. В этом случае каждое узловое устройство связи делает запись, от какого соседнего устройства узла связи передано принятое сообщение. Когда кадр RREQ достигает целевого устройства узла связи, целевое узловое устройство связи создает кадр "ответ с маршрутом (RREP)" и передает кадр RREP к исходному узлу, так чтобы маршрут переданного кадра RREQ мог быть прослежен. Таким образом, создается маршрут двусторонней связи.
В OLSR (оптимизированная маршрутизация в соответствии с состоянием линии связи) вся сеть охватывается периодическим обменом кадром среди устройств узлов связи и обнаружением маршрута к целевому узлу связи. Узловое устройство связи периодически передает кадр приветствия, чтобы уведомить друг друга о своем существовании. Когда существование устройства узла связи в качестве партнера по связи известно, далее создается маршрут для лавинной маршрутизации, по существу, распространения кадра по всей сети. Это называется "MPR (многоточечное предоставление)". Кадр MPR может эффективно передаваться от каждого устройства узла связи по всей сети. Затем, используя MPR, все узловые устройства могут быть информированы о топологии сети, распространяя между собой кадр ТС (управления топологией) в качестве сообщения друг другу о создании маршрута. Когда кадр должен быть передан целевому узловому устройству связи, топология сети, известная узловому устройству связи источника, ссылается на кадр и кадр направляется на узловое устройство связи соседнего адресата. Соседнее узловое устройство выполняет подобный процесс и, наконец, передает кадр на целевое узловое устройство.
В специальной сети беспроводной связи в качестве хорошо известной методики каждый узел широковещательно передает информацию в виде сообщения приветствия, содержащего информацию о существовании местного узла и метрике маршрута к местному узлу. Другой узел, который принимает сообщение приветствия, добавляет к принятой метрике метрику маршрута для маршрута между узлом, который широковещательно передал сообщение приветствия, и местным узлом. Результирующая метрика маршрута используется в способе (например, патентный документ 1). Метрика маршрута в этом случае может быть значением, указывающим затраты у источника и адресата, вычисленные с учетом таких факторов, как количество переходов, качество линии связи и т.д.
Патентный документ 1: Национальная публикация международной патентной заявки № 2006-526937.
Сущность изобретения
Устройство IP-сети и MPLS основаны на том, что сеть сама по себе имеет структуру, использующую адреса. Так как IP-адреса образуют древовидную структуру, маршрут определяется, выбирая направление, в котором процесс согласования адресов выполняется, по порядку, начиная с самого высокого порядка. Процесс основан на кабельном соединении. Так как кабельное соединение позволяет иметь стабильные соединения двумя терминалами связи, то есть никакой кадр не может быть принят оборудованием связи, которое не присоединено кабелем, маршрут может быть определен просто числом переходов блоков связи.
Однако, когда выполняется беспроводное соединение, система, описанная выше, имеет трудность при создании маршрута с высоким качеством связи. В беспроводной связи качество связи ниже, чем в кабельной связи, и другие оконечные устройства, которые напрямую не участвуют в связях, также оказываются затронуты. Качество связи также в значительной степени зависит от расстояния, окружающей среды и изменения во времени. Когда при этих обстоятельствах используется упомянутый выше протокол, то если маршрут определяется, основываясь только на количестве переходов, алгоритм может использовать маршрут, проходящий через оконечное устройство, находящееся на большом расстоянии. Однако, если расстояние большое, качество связи является низким и выбранный маршрут обладает очень низким качеством.
Когда маршрут создан, AODV нагружает сеть. Хотя если количество оконечных устройств мало, проблем не возникает, нагрузка на сеть возрастает по мере увеличения количества оконечных устройств и трафик становится тяжелым. В результате узловое устройство связи, чьи соединения уже установлены, оказываются затронутыми, и существует вероятность прекращения связи. Таким образом, имеется лишь очень небольшое количество узловых устройств, способных устанавливать связь, и для большинства устройств маршрут не может быть установлен. Кроме того, так как система основана на количестве переходов, как описано выше, созданный маршрут может иметь очень низкое качество связи.
В OLSR необходимо, чтобы все узловые устройства знали топологию сети. Поэтому существует ограниченный масштаб. Чтобы узнать топологию всех узловых устройств дополнительно требуется время.
Как описано выше, независимо от того, является ли соединение кабельным или беспроводным, качество связи может зависеть от качества связи между узловыми устройствами, что определяется состоянием трафика и окружающей средой. Особенно большому влиянию подвергается беспроводная связь. Поэтому, если сеть содержит очень большое количество узловых устройств, практически нецелесообразно иметь сервер для управления сетью и позволять серверу управлять сетью, поскольку из-за того, что количество узловых устройств большое, одна только передача команд управления от сервера налагает большую нагрузку. Поэтому, когда сеть выполнена с очень большим количеством узловых устройств, желательно, чтобы каждое узловое устройство автономно выбирало маршрут и контролировало активное/неактивное состояние.
Полагая, что каждое узловое устройство работает автономно, качество связи изменяется, как описано выше. Поэтому, когда кадр передачи, адресованный узловому устройству, ретранслируется, то для каждого узлового устройства необходимо хорошо представлять действующий в данное время маршрут. Например, в сети, имеющей фиксированную структуру и обычный способ поиска, использующий двоичное дерево, полное изображение сети или дерева известно на начальной стадии. Поэтому, легко определить, насколько далеко был проведен поиск. С другой стороны, в сети согласно настоящей заявке, в которой линия связи между узловыми устройствами изменяется, каждое узловое устройство не знает, какое узловое устройство присоединяется сверх окружающих узловых устройств, требуя, таким образом, от системы определять, насколько далеко был произведен поиск маршрута.
Настоящее изобретение обеспечивает узловое устройство и программу, способные автономно выбирать соответствующий маршрут, используя простую структуру, не создавая нагрузку на сеть.
Узловое устройство согласно варианту осуществления настоящего изобретения, в сети, имеющей множество узловых устройств, содержит: таблицу управления идентифицирующей информацией для хранения в виде информации о кадре, передаваемом местным узлом, идентифицирующей информации для уникальной идентификации кадра и информации об узле адресата кадра; таблицу весов узлов адресатов для хранения информации о весах для другого узла как адресата ретрансляции кадра для каждого конечного узла адресата кадра; устройство приема кадра для приема переданного кадра, адресованного местному узлу от другого узла; устройство обновления таблицы весов узла адресата для обновления данных таблицы весов узлов адресатов, соответствующей конечному адресату кадра для узла адресата, хранящегося связанным с идентифицирующей информацией, когда идентифицирующая информация о кадре, принятом устройством приема кадра, хранится в таблице управления информацией идентификации; и устройство определения адресата кадра для определения другого узла в качестве адресата для ретрансляции кадра путем ссылки к таблице весов узлов адресатов, соответствующей конечному узлу адресата кадра, когда идентифицирующая информация о кадре, принятом устройством приема кадра, не хранится в таблице управления информацией идентификации.
Когда кадр принят от другого узла, ссылаются к таблице весов узлов адресатов и определяют узел, которому передан кадр. Узел, которому передан кадр, определяется в соответствии с весом и вес обновляется в соответствии с возможностью передачи кадра другому узлу. Узловое устройство может автономно изучать маршрут.
Когда идентифицирующая информация для кадра, принятого устройством приема кадра, хранится в таблице управления идентифицирующей информацией, соседнее устройство обновления таблицы управления соседними узлами может обновлять вес узла адресата в таблице весов узлов адресатов, соответствующей конечному адресату кадра, так что для узла адресата, хранящегося как связанного с идентифицирующей информацией, приоритет может быть снижен.
Кроме того, узловое устройство может дополнительно содержать: таблицу управления соседними узлами для хранения информации о другом узле, существующем вокруг местного узла; устройство передачи сообщения приветствия для передачи в качестве сообщения приветствия информации о существовании местного узла и информации об окружающем маршруте, считанной из таблицы управления соседними узлами; устройство приема сообщения приветствия для приема сообщения приветствия, переданного от другого узла; и устройство обновления таблицы управления соседними узлами для обновления таблицы управления соседними узлами в соответствии с информацией об узле источника сообщения приветствия, принятого устройством приема сообщения приветствия. Когда в таблице управления соседними узлами обнаруживается первый узел, достигающий заданного состояния, устройство обновления таблицы весов узлов адресатов может обновить узел адресата в таблице весов узлов адресатов, так чтобы приоритет данных первого узла мог быть снижен.
Согласно узловому устройству варианта осуществления настоящего изобретения, каждое узловое устройство определяет узел, которому передается кадр, ссылаясь к хранящейся информации о весе, и обновляет информацию о весе в сети, в которой изменяется линия связи между узловыми устройствами. Таким образом, устройство может автономно изучить оптимальный маршрут и установить связь, не используя для этого всю сеть.
КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ
Фиг.1 - общая концепция системы связи;
Фиг.2 - обобщенное представление узлового устройства в соответствии с вариантом осуществления настоящего изобретения;
Фиг.3 - подробная схема узлового устройства в соответствии с вариантом осуществления настоящего изобретения;
Фиг.4 - структура таблицы управления соседними узлами;
Фиг.5 - пример формата кадра;
Фиг.6 - пояснительный пример формата кадра, указанного на фиг.5;
Фиг.7 - пояснительный пример процесса передачи данных в соответствии с таблицей управления соседними узлами;
Фиг.8 - пояснительный пример процесса обработки информации о весе, основываясь на результате передачи кадра;
Фиг.9 - пример таблицы управления FID;
Фиг.10 - часть (1) блок-схемы последовательности выполнения операций процесса приема кадра данных узлового устройства в соответствии с вариантом осуществления настоящего изобретения;
Фиг.11 - часть (2) блок-схемы последовательности выполнения операций процесса приема кадра данных узлового устройства в соответствии с вариантом осуществления настоящего изобретения;
Фиг.12 - формат заголовка приветствия;
Фиг.13 - пояснительный пример способа измерения качества связи посредством задержки в узловом устройстве в соответствии с вариантом осуществления настоящего изобретения;
Фиг.14 - подробный формат кадра приветствия, содержащего заголовок приветствия;
Фиг.15 - подробный пояснительный пример структуры таблицы весов;
Фиг.16 - подробная блок-схема (1) последовательности выполнения операций процесса приема кадра узловым устройством в соответствии с вариантом осуществления настоящего изобретения;
Фиг.17 - подробная блок-схема (2) последовательности выполнения операций процесса приема кадра узловым устройством в соответствии с вариантом осуществления настоящего изобретения;
Фиг.18 - подробная блок-схема (3) последовательности выполнения операций процесса приема кадра узловым устройством в соответствии с вариантом осуществления настоящего изобретения;
Фиг.19 - подробная блок-схема (4) последовательности выполнения операций процесса приема кадра узловым устройством в соответствии с вариантом осуществления настоящего изобретения;
Фиг.20 - подробная блок-схема (5) последовательности выполнения операций процесса приема кадра узловым устройством в соответствии с вариантом осуществления настоящего изобретения;
Фиг.21 - подробная блок-схема (6) последовательности выполнения операций процесса приема кадра узловым устройством в соответствии с вариантом осуществления настоящего изобретения;
Фиг.22 - последовательность обмена кадром приветствия; и
Фиг.23 - схема узлового устройства или оборудования, способного выполнять программу в соответствии с вариантом осуществления настоящего изобретения.
Описание вариантов осуществления
Предпочтительные варианты осуществления настоящего изобретения подробно описаны ниже со ссылкой на прилагаемые чертежи.
Сначала ниже описываются термины, использованные в настоящем описании.
"Кадр" относится к блоку данных, обрабатываемому в соответствии с протоколом. "Кадр" содержит, например, "кадр приветствия" и "кадр данных", но не ограничивается только ими.
"Кадр приветствия" относится к специальному кадру, передаваемому узловым устройством в соответствии с вариантом осуществления настоящего изобретения для подтверждения существования и состояния связи между устройством и другим узловым устройством.
"Кадр данных" относится к данным, которые должны быть переданы сетью от узла источника до целевого узла. Очевидно, что узловое устройство, соответствующее варианту осуществления настоящего изобретения, может содержать соответствующее устройство для отличия "кадра приветствия" от "кадра данных".
"Местный адресат (LD)" относится к идентификатору узла адресата, указывающему соседнее узловое устройство, которому должен быть передан кадр, когда узловое устройство рассматривается как объект. В настоящем описании LD может также упоминаться как "адрес местного адресата".
"Местный источник (LS)" относится к идентификатору узла, указывающему узловое устройство как прямой источник, который передает кадр к LD (то есть к устройству местного узла для LD). В настоящем описании LS может также упоминаться как "адрес местного источника".
"Глобальный адресат (GD)" относится к идентификатору узла, как к конечному адресату в ряду операций по распространению в интервале сети кадров данных. В настоящем описании GD может также упоминаться как "адрес глобального адресата".
"Глобальный источник (GS)" относится к идентификатору узла как первому источнику в ряду операций по распространению в сети кадров данных. В настоящем описании GS может также упоминаться как " адрес глобального источника".
"Идентификатор кадра (FID)" относится к уникальной идентификационной информации о каждом кадре. FID может быть, например, рядом чисел, но не ограничивается только этим.
"Вес" относится к значению, рассматриваемому при выборе маршрута распространения кадра. В настоящем описании вес показывается в качестве примера как вес линии связи входящего маршрута, вес линии связи исходящего маршрута, вес двунаправленной линии связи, вес качества входящего маршрута, вес качества исходящего маршрута и вес протяженности промежуточных линий связи, но не ограничивается ими. При описании в настоящем описании следует отметить, что "вес" или "информация о весе" могут относиться к значению, вычисляемому с использованием любого типа веса.
"Вес линии связи входящего маршрута" относится к весу кадра во входящем маршруте. Когда узловое устройство рассматривается как объект и если узловое устройство принимает кадр от другого соседнего узлового устройства, предполагается, что кадр прошел через "входящий маршрут".
"Вес линии связи исходящего маршрута" относится к весу кадра в исходящем маршруте. Когда узловое устройство рассматривается как объект и если узловое устройство передает кадр на другое соседнее узловое устройство, предполагается, что кадр проходит через "исходящий маршрут".
"Вес двунаправленной линии связи" относится к весу, вычисленному как комбинация упомянутых выше веса линии связи исходящего маршрута и веса линии связи входящего маршрута. В варианте осуществления настоящего изобретения "вес линии связи входящего маршрута", "вес линии связи исходящего маршрута" и "вес двунаправленной линии связи" являются данными, которые могут быть введены в таблицу управления соседними узлами, позднее описанной подробно. Однако в другом варианте осуществления могут быть введены любые другие комбинации.
"Вес качества маршрута" относится к значению, указывающему задержку маршрута в направлении к GD. "Вес качества входящего маршрута" относится к значению, указывающему качество связи от узлового устройства партнера к местному узловому устройству.
"Вес протяженности промежуточных линий связи" относится к значению, указывающему возможность передачи кадра между линиями связи. В варианте осуществления настоящего изобретения "вес качества направления связи", "вес качества входящего маршрута", и "вес протяженности промежуточных линий связи" являются данными, которые могут быть введены в таблицу весов, позднее описанную подробно. Однако в другом варианте осуществления могут быть введены любые другие комбинации.
На фиг.1 представлена полная концепция системы связи. Как показано на фиг.1, сеть содержит узловые устройства (a, b,..., s, t), соединенные друг с другом. В настоящей системе связи каждое узловое устройство работает как ретранслирующий элемент, передающий информацию от начального узла (узловое устройство b в примере на фиг.1) к целевому узлу (узловое устройство t в примере на фиг.1).
Каждое узловое устройство хранит уникальную идентифицирующую информацию (идентификатор, идентификация). Идентификатор, присвоенный каждому узловому устройству, здесь далее упоминается как идентификатор узла. Каждое узловое устройство не имеет представления о соседних узловых устройствах или всей сети. В начальном состоянии не существует никаких линий связи и каждое узловое устройство не имеет представления о существовании или состоянии других узловых устройств.
Для передачи информации от начального узла (b) к целевому узлу (t) в системе связи, показанной на фиг.1, необходимо сначала создать сеть. Процедура создания сети описана ниже.
Сначала обнаруживаются окружающие узловые устройства. Узловое устройство периодически уведомляет соседние узловые устройства о своем существовании. Уведомление окружающим узловым устройствам подается вместе с информацией, относящейся к созданию маршрута. После приема уведомления каждое узловое устройство создает список окружающих узловых устройств, чтобы представить себе существование окружающих узловых устройств вокруг узла.
Узловое устройство, которое обнаружило окружающие устройства узла, определяет узловое устройство как партнера, которому оно должно передать информацию согласно созданному списку, и передает информацию на узловое устройство.
Когда узловое устройство обнаруживает другое узловое устройство, которому должна быть передана информация, узловое устройство не знает, какому узловому устройству из множества окружающих узловых устройств должна быть направлена информация, чтобы информация смогла достигнуть целевого узла. Затем, узловое устройство, соответствующее настоящему варианту осуществления, создает таблицу весов, указывающую, какому узловому устройству из окружающих узловых устройств информация должна передаваться на приоритетной основе, и определяет узловое устройство, которому информация должна передаваться в соответствии с информацией о весе, хранящемся в таблице весов.
Узловое устройство, соответствующее настоящему варианту осуществления, описывается ниже в практической реализации.
На фиг.2 представлена схема узлового устройства, соответствующего варианту осуществления настоящего изобретения. Схема узлового устройства 1, показанная на фиг.2, имеет блок 2 обработки кадров, блок 3 управления линиями связи, блок 4 определения маршрута, таблицу 5 управления FID (идентификаторами кадров), таблицу 6 управления окружающими узлами и таблицу 7 весов. Хотя на фиг.2 это ясно не показано, любой тип запоминающего устройства (например, динамическое оперативное запоминающее устройство, DRAM, или флэш-память), известный в данной области техники, может хранить таблицу 5 управления FID (идентификаторами кадров), таблицу 6 управления окружающими узлами и таблицу 7 весов как таблицу данных.
Блок 2 обработки кадров выполняет процесс обмена кадром данных между блоком и узловым устройством, соседним с узловым устройством 1. После приема кадра данных блок 2 обработки кадров получает доступ к запоминающему устройству (не показано на фиг.2) и обнаруживает появление контура, используя таблицу 5 управления FID (соответствующую таблице управления идентифицирующей информацией).
Блок 3 управления линиями связи получает доступ к запоминающему устройству (не показано на фиг.2) и управляет активным/неактивным состоянием и мощностью на линиях связи, используя таблицу 6 управления соседними узлами.
Блок 4 определения маршрутов получает доступ к запоминающему устройству (не показано на фиг.2), обращается к таблице 7 весов (соответствующей таблице весов узлов адресатов, описанной в формуле изобретения) и определяет, какому следующему соседнему узловому устройству должен быть передан кадр. Таблица 7 весов создается для каждого из конечных адресатов (то есть глобальному адресату (GD)).
Каждое из множества узловых устройств, образующих сеть, показанную на фиг.1, имеет структуру, показанную на фиг.2, но в последующем описании узловые устройства различаются друг от друга и им присваивается ссылочный номер "1" или "la". Каждое узловое устройство может быть подключено с помощью беспроводного средства связи или кабеля. Если требуется, в варианте осуществления настоящего изобретения можно предположить, что устройство или программа, соответствующие варианту осуществления настоящего изобретения, могут быть применены в сети, в которой беспроводные и кабельные системы могут сосуществовать совместно.
На фиг.3 представлена подробная схема узлового устройства, соответствующего варианту осуществления настоящего изобретения. Следует отметить, что префикс "a", присвоенный ссылочному номеру позиции, соответствует элементу, имеющему тот же самый номер, или относится к подобному элементу. В настоящем описании, например, устройство XXX и устройство XXXa оба содержатся в варианте осуществления настоящего изобретения. Кроме того, суффикс в ссылочном номере может быть опущен и ссылаться на концепцию, содержащую элементы, имеющие и не имеющие суффикс. Например, когда указывается устройство XXX, оно также содержит устройство XXXa, пока не возникает какое-либо противоречие.
Узловое устройство la на фиг.3 содержит блок 2а обработки кадров, блок 3а управления линиями связи, блок 4а определения маршрутов, таблицу 5а управления FID, таблицу 6а управления соседними узлами, таблицу 7a весов, блок 10 приема и блок 20 передачи данных. Таблица 5a управления FID, таблица 6а управления соседними узлами и таблица 7a весов может храниться в любом соответствующем запоминающем устройстве. Запоминающее устройство может храниться в узловом устройстве la или обеспечиваться вне узлового устройства la. Для каждого узлового устройства могут быть обеспечены единое запоминающее устройство или множество запоминающих устройств.
Когда узловое устройство la, соответствующее упомянутому выше LS, принимает кадр (содержащий кадр данных и кадр приветствия) с помощью блока 10 приема, блок 12 размножения кадров идентифицирует тип кадра и размножает процесс в зависимости от его типа. Подробности описаны позже, но блок 12 размножения кадров может использовать идентификатор для указания типа и назначения его кадру.
Когда принятый кадр является кадром приветствия, блок 12 размножения кадров пропускает кадр к блоку 3а управления линиями связи. Блок 3а управления линиями связи получает доступ к запоминающему устройству, хранящему таблицу 6а управления соседними узлами, и управляет активным/неактивным состоянием и мощностью на линии связи соседних узловых устройств. Затем, когда контур обнаружен, блок 3а управления линиями связи получает доступ к запоминающему устройству, хранящему таблицу 7a весов, и регистрирует или обновляет информацию о весе (подробно описано ниже).
Когда принятый кадр является кадром данных, блок 12 размножения кадров пропускает кадр к блоку 2а обработки кадров. Блок 2а обработки кадров получает доступ к запоминающему устройству, хранящему таблицу 5а управления FID, и управляет информацией о FID, LD и GS. Затем блок 2а обработки кадров пропускает кадр к блоку 4а определения маршрутов. Когда контур обнаружен, блок 2а обработки кадров получает доступ к запоминающему устройству, хранящему таблицу 7a весов, и регистрирует или обновляет информацию о весе (подробно описано позже).
Блок 4а определения маршрутов получает доступ к запоминающему устройству, хранящему таблицу 7a весов, получает информацию о весе и определяет, какому узловому устройству должен быть передан кадр. Затем он передает кадр блоку 20 передачи данных.
Когда блок 20 передачи данных передает кадр, принятый от блока 4а определения маршрутов, на другое узловое устройство, он позволяет передающему блоку 22 получить доступ к запоминающему устройству, хранящему таблицу 5а управления FID, и регистрирует и обновляет информацию о FID, LD и GS.
В варианте осуществления настоящего варианта осуществления, как описано выше, используется такая таблица, как таблица управления соседними узлами, таблица управления FID (идентификаторами кадров), таблица весов и т.д. Сначала описывается таблица управления соседними узлами.
На фиг.4 представлена структура таблицы 6 или 6а управления соседними узлами. Таблица 6 или 6а управления соседними узлами содержит идентификатор узла, время последнего обновления и мощность на линии связи.
Идентификатор узла является идентифицирующей информацией, присвоенной каждому узловому устройству для идентификации узлового устройства, образующего сеть.
Время последнего обновления является информацией даты и времени, в которое последний раз была обновлена информация для узлового устройства, указанного каждым идентификатором узла. Фактически, например, информация даты и времени, в которое была обновлена мощность на линии связи, является временем последнего обновления.
Мощность на линии связи вычисляется на основании мощности на линии связи, содержащейся в кадре приветствия, принятом узловым устройством 1 или la от соседнего узлового устройства, и хранится в соответствующем запоминающем устройстве. Мощность на линии связи может быть вычислена, используя, например, радиочастотную мощность и частоту получения кадров. Мощность на линии связи соответствует, например, весу двунаправленной линии связи.
Как описано выше, чтобы в первый раз конфигурировать сеть заранее, производится обмен кадром уведомления (кадром приветствия) между соседними узлами. Затем в каждом узловом устройстве создаются таблица 6 управления соседними узлами, показанная на фиг.2, или таблица 6а управления соседними узлами, показанная на фиг.3, и таблица 7 весов, показанная на фиг.2, или таблица 7a весов, показанная на фиг.3. Как описано со ссылкой на фиг.1, в узловом устройстве 1, соответствующем настоящему варианту осуществления, нет необходимости представлять себе топологию сети.
Если таблица 6 или 6a управления узлами создана, узловое устройство, которому должен быть передан кадр, определяется из количества соседних узлов, хранящих информацию, соответствующую таблице 6 или 6а управления соседними узлами. Таблица 7 весов, на которую делается ссылка, когда узловое устройство, которому должен быть передан кадр, определено, обновляется в процессе после того, как кадр принят от соседнего узлового устройства.
На фиг.5 и 6 приводятся примеры форматов кадров. Кадр, показанный на фиг.5, содержит идентификатор узла для узла адресата (местный адресат) соседнего узла, идентификатор узла (LS) для исходного узла (местный источник) соседнего узла, идентификатор узла (GD) адресата (глобальный адресат), идентификатор узла (GS) исходного узла (глобальный источник), идентификатор кадра (FID), тип кадра (TYPE), длина данных (DATALEN) и тело данных (DATA).
LD хранит идентификатор узла для узла адресата, которому кадр должен быть передан, в соседних узлах узлового устройства 1.
LS хранит идентификатор узла исходного узлового устройства, которому кадр должен быть передан, в соседнем узловом устройстве как LD. Например, если LD обращается к идентификатору узла одного из узловых устройств, соседних с узловым устройством 1, то LS является идентификатором узла для узлового устройства 1.
GD хранит идентификатор узла конечного адресата кадра и GS хранит идентификатор узла первоначального источника кадра.
Идентификатор кадра хранит идентифицирующую информацию для идентификации кадра.
Тип кадра хранит информацию о типе кадра. Тип кадра является, например, кадром данных, кадром приветствия и т.д., но не ограничивается только ими.
Длина данных хранит длину тела данных (длина данных или также упоминается как размер кадра).
Тело данных хранит данные, которые должны распространяться в сети.
Следует заметить, что форматы, описанные здесь в настоящем описании, являются только примерами. В соответствии с другим вариантом осуществления настоящего изобретения могут использоваться другие форматы и этот другой вариант осуществления может содержаться в объеме настоящего изобретения.
На фиг.7 представлен пример процесса передачи данных, соответствующего таблице 6 или 6a управления соседними узлами варианта осуществления настоящего изобретения. На фиг.7(a) показана схема определения веса для каждого из соседних узловых устройств. На фиг.7(b) показан простой пример таблицы управления соседними узлами 6 или 6a.
Когда кадр принят от одного из соседних узловых устройств, узел 1 или la согласно варианту осуществления передает кадр узловому устройству, имеющему более высокий приоритет согласно информации о весе в узловых устройствах, кроме источника кадра, то есть узлового устройства, такого как LS. Узловое устройство 1 или la присваивает номер линии связи каждому из соседних узловых устройств, идентифицируя, таким образом, каждое соседнее узловое устройство.
В варианте осуществления значение, используемое как информация о весе (например, вес двунаправленной линии связи и т.д.), устанавливается в пределах диапазона, равного или большего, чем 0, и равного или меньшего, чем 1. Чем меньше значение, тем выше становится приоритет. Например, 0,5 устанавливается как начальное значение информации о весе, так чтобы значение изменялось в зависимости от возможности последующей передачи кадра и присутствия/отсутствия обнаружения контура.
Установка и обновление информации о весе выполняются с помощью функции операции веса (например, функции с учитываемой мощностью на линии связи), описанной далее. Так как функция операции веса влияет на поведение всей сети, необходимо ее изменять в зависимости от использования сети.
На фиг.7(a) показан способ определения узлового устройства, которому должен передаваться кадр в соответствии с информацией о весе, когда кадр принимается от соседнего узлового устройства, имеющего номер i линии связи.
После приема кадра, переданного от соседнего узлового устройства, имеющего номер i линии связи, узловое устройство 1 или la обращается к таблице весов, соответствующей узловому устройству GD в таблицах 6 и 6a управления соседними узлами. Затем принятый кадр должен быть передан соседнему узловому устройству, имеющему самый высокий приоритет, основанный на информации о весе, и имеющему номер линии связи, отличный от "i".
Как показано на фиг.7(b), таблица управления соседними узлами 6 или 6a хранит номер линии связи, присвоенный каждому соседнему узловому устройству, и вес соседнего узлового устройства, связанный с номером линии связи. Номер линии связи может заменяться идентификатором узла. Узловое устройство 1 или la обновляет таблицу 6 или 6a управления соседними узлами в соответствии с кадром, принятым от соседнего узлового устройства связи с номером i линии связи, и управляет информацией о весе.
На фиг.8 приводится пример представления процесса работы с информацией о весе, основываясь на результате передачи данных.
1
2
3
4
В примере на фиг.8 номера 1, 2, 3 и 4 линий связи и веса w, w, w и w устанавливаются соответственно в узловые устройства A, B, C и D как информация о весе.
Когда связь, например, между узловыми устройствами выполняется беспроводным способом, среда во время связи, расстояние между узловыми устройствами и т.д. могут влиять на качество связи. Когда связь между узловыми устройствами осуществляется по кабелю, то, например, трафик может влиять на качество связи. Учитывая влияние, начальное значение веса устанавливается в этом примере равным 0,5 и диапазон значения устанавливается на значение, равное или большее, чем 0, и равное или меньшее, чем 1. Однако они являются только примерами и в качестве веса в варианте осуществления могут использоваться другие значения. В этом варианте осуществления, чем меньше вес (ближе к 0), тем выше приоритет. Однако это также только пример. Возможен вариант осуществления, в котором приоритет может присваиваться другими способами (например, чем больше вес, тем выше приоритет).
Таблица весов может хранить информацию о соседнем узловом устройстве, на которое должен быть передан кадр, на приоритетной основе, когда кадр передан, и информацию о других узловых устройствах. Например, может быть подготовлен флажок и т.д. и значение устанавливается в таблице весов в зависимости от возможности передачи кадра.
1
2
3
4
Узловое устройство 1 или la работает с информацией о весе (например, о весе двунаправленной линии связи) в зависимости от результата передачи кадра на соседнее узловое устройство. Сначала отношения между значениями веса могут быть как w<w<w<w. Таким образом, предполагается, что приоритет соседнего узлового устройства A самый высокий, а приоритет соседнего узлового устройства D является самым низким.
В этом случае, когда узловое устройство 1 или la принимает кадр от соседнего узлового устройства i, отличного от соседних узловых устройств А-D, узловое устройство 1 или la пытается передать кадр по порядку от соседнего узлового устройства А, имеющего самый высокий приоритет. Если передача данных на соседнее узловое устройство А оказывается неудачной, данные передаются узловому устройству В, имеющему второй самый высокий приоритет.
Наконец, если передача данных терпит неудачу для соседних узловых устройств узла A и В, но данные успешно передаются на соседнее узловое устройство C, узловое устройство 1 или la присваивает наибольший вес (самое худшее значение) и самый низкий приоритет соседним узловым устройствам A и В, уменьшая, таким образом, вес и присваивая самый высокий приоритет соседнему узловому устройству C.
3
4
1
2
При следующей и последующих передачах кадров данных адресат (LD) передачи кадра определяется на основе отношения весов (w<w<w=w), обновляемых, как описано выше, и передача кадра предпринимается, начиная с соседнего узлового устройства C, имеющего самый высокий приоритет.
Далее описан способ обнаружения возникновения контура.
На фиг.9 приведен пример построения таблицы 5 или 5a управления FID. В варианте осуществления, показанном на фиг.9, таблица 5 или 5a управления FID является, например, буфером FIFO (первым пришел - первым обслужен). Таблица 5 или 5a управления FID содержит идентификатор кадра (FID), идентификатор узла для исходного узла GS, идентификатор узла для узла LD адресата передачи и идентификатор узла для исходного узла LS. Определение идентификатора узла для FID, GS/LD/LS подобно соответствующему полю в каждом кадре данных, показанном на фиг.6.
После приема кадра от соседнего узлового устройства, узловое устройство 1 или la сравнивает значения полей FID и GS кадра с записью, хранящейся в таблице 5 или 5a управления FID. В результате сравнения, если таблица 5 управления FID хранит запись, имеющую тот же самый FID и GS, что и принятый кадр, узловое устройство 1 или la решает, что кадр является тем же самым кадром, что и кадр, однажды полученный ранее, и предполагает, что "контур появился" или "отслеживание в обратном порядке произошло посредством прерывания в процессе маршрутизации". Если обнаружены появление контура или отслеживание в обратном порядке, таблица 7 или 7a весов обновляется и самое наихудшее значение (максимальное значение в этом варианте осуществления) присваивается информации о весе, соответствующей идентификатору узла LS кадра.
С другой стороны, если нет никакой записи, имеющей тот же самый FID и GS, то узловое устройство 1 или la восстанавливает значение из каждого поля FID, GS, LD и LS в принятом кадре и регистрирует одну запись в таблице 5 управления FID.
Описанное ниже с дополнительными подробностями является процессом, выполняемым, когда узловое устройство принимает кадр данных.
На фиг.10 и 11 приведены блок-схемы последовательностей выполнения операций процесса приема кадра данных узлового устройства 1 или la в соответствии с вариантом осуществления настоящего изобретения.
На этапе S1 выполняется процесс инициализации. В процессе инициализации на этапе S1, например, когда устанавливается связь с соседним узловым устройством посредством беспроводной связи, регулируется частота приема и определяется система модуляции. Процесс инициализации на этапе S1 выполняется только тогда, когда узловое устройство 1 или la обеспечивается в сети.
На этапе S2 ожидается прием кадра данных. Если кадр данных принимается на этапе S2, управление передается на этап S3 и определяется, является ли идентификатор узла, хранящийся в поле LD, идентификатором узла для местного узла. Если LD хранит идентификатор узла устройства, отличного от местного узла, управление возвращается к этапу S2 и сохраняется состояние ожидания.
Хотя процесс конфигурирования сети выполняется, используя кадр приветствия, как описано выше, между процессами на этапах S1 и S2, передача кадра приветствия выполняется в последовательности, отличной от последовательности выполнения операций в процессах, показанных на фиг.10 и 11. Поэтому описание здесь опущено.
Если на этапе S3 определено, что поле LD хранит идентификатор узла для местного устройства, управление передается на этап S4.
На этапе S4 определяется, является ли идентификатор узла, хранящийся в поле GD, идентификатором узла для местного устройства. Если на этапе S4 определено, что идентификатор узла для местного устройства хранится в поле GD, то затем это означает, что конечный адресат распространения ряда данных по сети является устройством местного узла. Поэтому управление передается на этап S10, принятый кадр данных обрабатывается (на иерархическом уровне более высокого порядка) и последовательность процессов заканчивается.
Если на этапе S4 определено, что идентификатор узла, хранящийся в поле GD, является идентификатором узла для устройства, отличного от местного устройства, управление передается на этап S5. На этапе S5 определяется, существует ли запись, имеющая комбинацию FID и GS, соответственно совпадающую с FID и GS принятого кадра данных.
Если на этапе S5 определено, что таблица 5 управления FID содержит запись, совпадающую с FID и GS кадра данных, управление передается на этап S6. На этапе S6 LD восстанавливается из записи, для которой определено, что FID и GS соответственно совпадают с FID и GS кадра данных. На этапе S7 для таблицы 7 или 7a весов, соответствующей GD кадра данных, обновляется запись, имеющая идентификатор узла, совпадающий с LD, восстановленным на этапе S6. Например, в настоящем варианте осуществления устанавливается идентификатор узла, который последним передает кадр, имеющий FID в таблице управления FID в качестве позиции Last (последний). Изменение делается таким образом, что информация о весе, соответствующая позиции Last, может быть самым плохим значением (например, 1,0) с самым низким приоритетом. Если таблица 7 или 7a весов обновляется, управление передается в точку (A) на фиг.11.
С другой стороны, на этапе 5, если определено, что не существует совпадения FID и GS в таблице 5 управления FID, управление передается на этап S8. На этапе S8 определяется, существует ли таблица 7 или 7a весов, соответствующая GD кадра данных.
Если на этапе S8 определено, что не существует таблицы 7 или 7a весов в отношении узлового устройства, указанного GD в кадре данных, управление передается на этап S9. Затем, на этапе S9 создается таблица 7 или 7a весов для GD кадра данных и управление передается в точку (A) на фиг.11.
В других вариантах осуществления, на этапе S9 таблица весов может быть создана со ссылкой, например, на мощность на линии связи из таблицы 6 или 6a управления соседними узлами, показанной на фиг.5.
Если определено, что существует таблица 7 или 7a весов для узлового устройства, указанного GD кадра данных на этапе S8, никакой процесс не выполняется и управление передается в точку (A) на фиг.11.
В процессе, показанном на фиг.11, управление сначала передается от точки (A) к этапу S11 и идентификатор узла, соответствующего значению оценки, имеющего самый высокий приоритет, получают из таблицы 7 или 7a весов. Затем, на этапе S12 определяется, может ли быть обнаружено подходящее узловое устройство, соответствующее полученному идентификатору узла.
Если на этапе S12 определено, что подходящее узловое устройство было обнаружено, управление передается на этап S13 и кадр данных передается идентификатору узла, полученному на этапе S11.
Затем, на этапе S14 FID, GS, LD и LS добавляются к таблице 5 управления FID, основываясь на данных, содержащихся в переданном кадре данных.
Затем, на этапе S15 определяется, в соответствии с обратным слежением от узлового устройства адресата передачи, была ли успешно выполнена передача кадра данных. Например, когда от узлового устройства адресата передачи принят сигнал подтверждения ACK, определяется, что передача была успешно выполнена. Если никакой сигнал ACK по истечении заданного времени не получен, принимается решение, что передача потерпела неудачу. Если решено, что передача была успешно выполнена, приоритет увеличивается, используя значение оценки, соответствующее идентификатору узла для узлового устройства адресата передачи для таблицы 7 или 7a весов узлового устройства, указанного GD кадра данных на этапе S16, и управление возвращается в точку (B) на фиг.10.
С другой стороны, если на этапе S15 определено, что передача кадра данных потерпела неудачу, то тогда приоритет снижается, используя значение оценки, соответствующее идентификатору узла узлового устройства адресата передачи на этапе S17, и управление возвращается на этап S11.
Впоследствии процессы до и после этапа S11 повторяются, пока передача кадра данных не будет успешно выполнена или пока никакой соответствующий идентификатор узла не сможет быть обнаружен в таблице весов.
Если на этапе S12 определено, что никакое подходящее узловое устройство (идентификатор узла) не может быть обнаружено из таблицы 7 или 7a весов, управление передается на этап S18, принятый кадр данных передается узловому устройству, указанному LS, и управление возвращается к точке (B) на фиг.10.
Как описано выше, когда кадр данных передан, узловое устройство 1 или 1a, соответствующее настоящему варианту осуществления, обращается к таблице 7 или 7a весов, определяет узловое устройство, которому данные должны быть переданы на приоритетной основе, и обновляет информацию о весе (например, значение оценки) в зависимости от возможности передачи данных. Определяя узловое устройство, которому кадр должен быть передан на приоритетной основе согласно информации о весе, возвращение кадра данных после образования контура и возвращение кадра данных, когда маршрут, по которому была установлена связь, прерывается из-за изменения состояния сети, обнаруживаются, основываясь на том, какой маршрут обходится, и связь может продолжаться по оптимальному маршруту. Как описано выше, таблица 7 или 7a весов создается для каждого GD, но следует отметить, что в настоящем варианте осуществления для понимания рассматривается только одна таблица весов.
В системе связи, показанной на фиг.1, каждое узловое устройство контролирует состояние сети. Способ контроля сети узловым устройством в соответствии с настоящим вариантом осуществления описан ниже.
Как описано выше, каждое узловое устройство содержит в кадре приветствия и передает информацию о качестве радиосигнала связи, принимаемого от другого узлового устройства. Узловое устройство обращается к кадру приветствия, принятому от другого узлового устройства, вычисляет качество связи соседнего узлового устройства и сохраняет информацию о вычисленном качестве связи в таблице 6 или 6a управления соседними узлами. В варианте осуществления качество связи определяется задержкой и числом переходов.
На фиг.12 показан формат заголовка приветствия, хранящегося в заданной области в кадре приветствия. Как показано на фиг.12, заголовок приветствия содержит глобальный адрес получателя (то есть GD), количество переходов h, вес d качества маршрута, вес качества входящего маршрута и тип узла.
Глобальный адрес получателя (GD) является информацией, например, о глобальном адресе получателя (GD), соответствующем таблице 7 весов, хранящейся узловым устройством в качестве первого источника (GS) кадра приветствия, содержащего заголовок приветствия, показанный на фиг.12.
Количество переходов является, например, информацией о количестве переходов, переданной от источника кадра приветствия к узловому устройству в качестве конечного адресата (GD).
Вес d качества маршрута хранит значение, полученное из задержки на маршруте до GD.
Вес качества входящего маршрута хранит значение, полученное, основываясь на качестве связи в направлении от узлового устройства партнера связи (в этом примере - от узлового устройства, которое передало кадр приветствия) к местному узловому устройству.
В качестве типа узла определяются такие типы как шлюз, повторитель, терминал и т.д.
Способ получения веса d качества маршрута из информации, хранящейся в заголовке приветствия, описан с практической точки зрения ниже со ссылкой на фиг.13.
На фиг.13 представлен пояснительный пример способа измерения качества связи посредством задержки в узловом устройстве 1, соответствующем варианту осуществления настоящего изобретения. Узловое устройство "источника" периодически передает кадр приветствия на внешний блок. Заштрихованная часть, показанная в виде овала на фиг.13, относится к области, в которой может быть принят кадр приветствия, переданный узловым устройством источника. Узловые устройства a и b принимают кадры приветствия, последовательно передаваемые от узлового устройства источника, и считают время, требующееся от приема одного кадра до приема следующего кадра. Здесь далее, время, требующееся для приема следующего кадра, также упоминается как "период приема".
На фиг.13 представлен график (по вертикальной оси указывается количество появлений, а по горизонтальной оси указывает период приема), показывающий взаимосвязь между периодом приема узловых устройств a и b и частотой приема. Как показано на фиг.13, соотношение между периодом приема и частотой приема в каждом узловом устройстве, в целом, соответствует нормальному распределению.
Обычно потеря кадра легко происходит в узловом устройстве b, расстояние которого от узлового устройства источника относительно велико. Поэтому в узловом устройстве b потеря приема для кадра происходит легче из-за потери кадра, чем в узловом устройстве a, удлиняя, таким образом, период до приема следующего кадра. Таким образом, в варианте осуществления настоящего изобретения, качество связи достигается с помощью периода T приема, выполняя аппроксимацию, в которой длинный период Т приема предполагается соответствующим длительной задержке.
1
1
1
2
1
i
Способ получения качества связи с помощью периода приема описан ниже. Сначала, предположим, что кадр приветствия принимается в момент времени t и следующий кадр приветствия принимается в момент времени t+t. В этом случае, период приема T=t. Предполагается, что ряд периодов приема, наблюдаемых в заданном периоде T {t, t..., t|n∈N}) (t(i=1, 2..., n), является значением наблюдения в каждой точке времени). Стандартная девиация, основанная на наблюдаемом периоде приема, выражается следующим уравнением (1). в уравнении является средним значением для значений наблюдения за период приема.
<img file="00000003.tif" he="13" wi="32" img-content="undefined" img-format="tif" />
(1)
Стандартная девиация, полученная посредством приведенного выше уравнения (1), сохраняется в заданном поле (не показано на прилагаемых чертежах) таблицы 6 или 6a управления соседними узлами в качестве веса входящей линии связи. Когда вес входящей линии связи, полученный с помощью уравнения (1), сохраняется в кадре приветствия и передается узловому устройству партнера, узловое устройство партнера получает вес исходящей линии связи из принятой информации. Таким образом, вес входящей линии связи получается в местном узле из кадра приветствия, принятого от узлового устройства партнера и полученный вес входящей линии связи сохраняется в кадре приветствия и обменивается с узловым устройством партнера, получая, таким образом, вес исходящей линии связи.
При вычислении веса двунаправленной линии связи, исходя из полученного веса исходящей линии связи и веса входящей линии связи, в соответствующей области техники предлагаются различные способы. Например, вес двунаправленной линии связи может быть вычислен согласно следующему уравнению (2).
(вес двунаправленной линии связи) = [{(вес исходящей линии связи)+1} {(вес входящей линии связи)+1}-1]<sup>1/2</sup>
(2)
На фиг.14 приведен подробный пример формата кадра приветствия, содержащего заголовок приветствия. В другом варианте осуществления настоящего изобретения может использоваться другой формат и другой вариант осуществления содержится в объеме настоящего изобретения.
Кадр, показанный на фиг.14, грубо делится на заказной заголовок, сжатый заголовок и полезную нагрузку.
В настоящем варианте осуществления заказной заголовок имеет поля "адреса местного адресата" (LD), "адреса местного источника" (LS), "типа кадра", указывающего тип кадра, и "размера кадра", указывающего размер сжатого кадра.
Сжатый заголовок имеет поле "тип сжатия", указывающее способ сжатия полезной нагрузки, и поле "размер кадра", указывающее размер распакованного кадра. Каждое узловое устройство может соответственно распаковать полезную нагрузку, учитывая тип сжатия.
Полезная нагрузка также содержит сжатые данные заголовка сообщения приветствия, одного или более заголовков приветствия и случайные данные, указывающие подпись. Сжатие в кадре в соответствии с настоящим вариантом осуществления должно достигать эффекта экономии диапазона связи, уменьшая размер кадра. Очевидно, что кадр с распакованными данными может быть введен в другой вариант осуществления настоящего изобретения.
Заголовок сообщения приветствия, введенный в полезную нагрузку, имеет поля "тип обслуживания", указывающее тип обслуживания, "информация о делении", указывающее состояния деления полезной нагрузки, "количество заголовков приветствия", указывающее количество заголовков, введенных в полезную нагрузку, "идентификатор устройства", указывающее идентификатор узлового устройства, и "ключ доступа" для декодирования кодированной информации. Поле "идентификатор устройства" может хранить идентификатор узлового устройства в качестве источника запроса приветствия, описанного ниже, как относящийся к процессу на фиг.22.
Один или более заголовков приветствия, внесенных в полезную нагрузку, имеет поля "глобального адреса источника" (GS), "количество переходов информации GW", указывающее количество переходов информации для шлюза (GW), упомянутое выше поле "вес качества маршрута" (d) и поле "вес качества входящей линии связи".
Упомянутые выше типы полей и их порядок являются только примерами. В других вариантах осуществления настоящего изобретения, упомянутые выше поля и любые другие поля, требующиеся для специалистов в данной области техники, могут быть организованы в каждом заголовке в соответствующем порядке.
На фиг.15 представлен подробный вид примера структуры таблицы 7 или 7a весов. Таблица 7 или 7a весов, показанная на фиг.15, содержит глобальный адрес получателя (GD), местный адрес получателя (LD), количество переходов h, вес w протяженности промежуточных линий связи, вес d качества маршрута и значение Е оценки. Хотя на фиг.15 не показано, таблица 7 или 7a весов может содержать другую информацию. Например, она может содержать данные времени последнего обновления, указывающие информацию о времени, когда данные были обновлены. Как описано выше, таблица весов сохраняется в каждом узловом устройстве.
Глобальный адрес получателя (GD) хранит данные в поле глобального адреса получателя (GD) в заголовке приветствия принятого кадра приветствия (в этом примере, он должен рассматриваться как кадр приветствия, принятый в любом процессе приема из множества процессов приема кадров приветствия, описанных ниже со ссылкой на фиг.16-21 и выполняемых после того, как узловое устройство активировано).
В адресе местного получателя (LD) хранятся данные, указанные в адресе местного источника (LS), содержащемся в принятом кадре приветствия. То есть, когда узловое устройство, принявшее кадр приветствия, рассматривается как объект, LS принятого кадра приветствия является кандидатом для LD, когда затем передается другой кадр.
Количество h переходов хранит количество переходов от узлового устройства, имеющего таблицу весов, к GD. То есть, он хранит значение, полученное добавлением 1 к значению, указанному количеством переходов в заголовке приветствия принятого кадра приветствия.
Тип узла определяет тип узла и хранит данные, указанные типом узла, в заголовке приветствия принятого кадра приветствия.
Вес w протяженности промежуточных линий связи в цифровой форме выражает возможность передачи кадра данных между линиями связи. В варианте осуществления данные, вычисленные на основе веса качества входящего маршрута в заголовке приветствия принятого кадра приветствия, хранятся как вес w протяженности промежуточных линий связи.
Вес d качества маршрута вычисляется на основе дисперсии периода приема кадра приветствия, как описано выше со ссылкой на фиг.12 и 13.
Значение E оценки хранит итоговую информацию оценки маршрута, вычисленную, используя количество переходов h, вес w протяженности промежуточных линий связи и вес d качества маршрутов в заголовке приветствия принятого кадра приветствия.
В этой области техники эмпирически известно, что нестабильность связи обладает экспоненциальным ростом при увеличении количества h переходов (пропускная способность снижается). Поэтому, например, значение Е оценки может быть выражено следующим уравнением (3).
E(h, w, e)=2<sup>(h+w)</sup>+d
(3)
Тем не менее, в дополнение к приведенному выше уравнению (3), может использоваться способ соответствующего получения значения E оценки и этот способ содержится в вариантах осуществления настоящего изобретения. В других вариантах осуществления настоящего изобретения значение E оценки может быть вычислено, используя, по меньшей мере, количество h переходов или вес d качества маршрута или вес w протяженности промежуточных линий связи или мощность принимаемого сигнала или любой параметр, считающийся подходящим в этой области техники. Например, значение E оценки может быть вычислено, используя уравнение E=d+h+5w+20/r (где d указывает вес качества маршрута, h указывает количество переходов, w указывает вес протяженности промежуточных линий связи, r указывает мощность принимаемого сигнала, когда принимается последний кадр приветствия).
Дополнительно, когда определен вес w протяженности линий связи и передача данных терпит неудачу, используется уравнение w=w+1. Если передача данных выполнена успешно, используется уравнение w=w-1 (например, минимальным значением является 0). Затем, используя w как входной параметр в приведенном выше уравнении (3), соседний узел во время передачи данных может быть точно отрегулирован.
Таким образом, узловое устройство 1 или la, соответствующее настоящему варианту осуществления, может контролировать состояние сети, основываясь на состоянии приема кадра приветствия от другого узлового устройства.
На фиг.16-21 представлены подробные блок-схемы последовательности выполнения операций процесса приема кадра приветствия узлового устройства в соответствии с вариантом осуществления настоящего изобретения. Последовательность процессов описывается ниже со ссылкой на чертежи. Процесс, выполняемый узловым устройством в соответствии с вариантом осуществления настоящего изобретения, в общих чертах описан ниже.
(i) На этапах S1600-S1614 обновляется таблица управления соседними узлами.
(ii) На этапах S1700-S1710' значение оценки источника (LS) кадра приветствия, зарегистрированное в таблице весов местного узлового устройства, обновляется для каждого GD заголовка приветствия, используя заголовок приветствия кадра приветствия.
(iii) На этапах S1850-S1700' обновляется значение оценки таблицы весов местного узлового устройства, GD которого является источником (LS) кадра приветствия.
(iv) На этапах S2000-S2010', если источник (LS) кадра приветствия не был зарегистрирован в таблице весов местного узлового устройства, он регистрируется вновь, и если GD заголовка приветствия не был зарегистрирован в таблице весов местного узлового устройства, он регистрируется вновь.
Последовательность выполнения процесса в настоящем варианте осуществления начинается, когда кадр приветствия принимается узловым устройством точки наблюдения (местное узловое устройство), показанным на фиг.16.
На этапах S1600-S1614 обновляется информация о весе в записи в таблице управления соседними узлами, соответствующей источнику (LS) кадра приветствия.
В соответствии с S1600, узловое устройство, которое приняло кадр приветствия ищет запись, соответствующую узловому устройству источника (LS) кадра приветствия в таблице управления соседними узлами узлового устройства. При поиске время приема предыдущего кадра приветствия от LS сравнивается со временем приема обрабатываемого кадра приветствия. Таким образом, подтверждается, существует ли несовместимое время приема, а также определяется, существует ли ложный LS (то есть передача которого происходит с управлением ложным LS).
На этапе S1602, если определено, что никакой источник (LS) кадра приветствия не обнаружен в таблице управления соседними узлами, то управление затем передается на этап S1604. Затем LS вновь добавляется в таблицу управления соседними узлами и устанавливается начальное значение веса входящего маршрута. На этапе S1602, если определено, что в таблице управления соседними узлами обнаружен источник (LS) кадра приветствия, то затем управление передается на этап S1606. Затем обновляется значение веса входящей линии связи в записи, соответствующей LS в таблице управления соседними узлами.
На последующем этапе S1608 информация (идентификатор и т.д.) о местном узловом устройстве разыскивается в заголовке приветствия кадра приветствия. В этом случае делается ссылка на информацию о качестве линии связи между узлами LS (то есть вес входящей линии связи от LS). Затем, если на этапе S1610 определено, что существует информация о местном узловом устройстве, управление передается на этап S1612 и вычисляется вес исходящей линии связи для соседнего узлового устройства.
На последующем этапе S1614 вычисляется вес двунаправленной линии связи соседнего узлового устройства. Затем управление передается в точку (I) на фиг.17.
На этапе S1700 на фиг.17 начинается итерационный процесс (процесс образования контура) для каждой записи в таблице весов местного узлового устройства. Затем для каждого заголовка приветствия, введенного в кадр приветствия на этапе S1710 вкладывается итерационный процесс.
На этапе S1712 определяется, соответствует ли GD таблицы весов GD тому, который находится в заголовке приветствия (то есть, введен ли он в таблицу весов источника (LS) в кадре приветствия).
'
Если на этапе S1714 GD таблицы весов не совпадает с GD в заголовке приветствия, управление передается в точку (IV) на фиг.17 и один итерационный цикл заканчивается на этапе S1710. Если на этапе S1714 GD таблицы весов совпадает с GD заголовка приветствия, управление передается на этап S1716.
На этапе S1716 LD, являющийся кандидатом на адресата, которому местное узловое устройство должно передавать кадр, разыскивается в таблице весов, соответствующей источнику (LS) кадра приветствия.
Если на этапе S1718 кандидат LD (кандидат в адресаты LD) в качестве адресата существует, количество h переходов на этапе S1720 обновляется как количество переходов + 1 заголовка приветствия в записи для кандидата LD в адресаты в таблице весов. На этапе S1722 вычисляется вес d качества маршрута для кадра приветствия и вес d качества маршрута для кандидата LD в адресаты обновляется. Вес d качества маршрута для кадра приветствия может быть получен, например, выполняя суммирование или любую арифметическую операцию с весом двунаправленной линии связи на всем маршруте (или, по меньшей мере, части всего маршрута), вычисленным, исходя из веса качества маршрута, рассматриваемого от источника кадра приветствия, и веса качества входящей линии связи, исходя из дисперсии периода приема кадра приветствия. То есть в узловом устройстве вес d качества маршрута для принятого кадра приветствия добавляется к весу d качества маршрута таблицы весов, и полученный и обновленный вес d качества маршрута используется в качестве веса качества маршрута, помещенного в кадр приветствия, который должен быть передан, передавая, таким образом, вес следующему узловому устройству. Короче говоря, накопление веса двунаправленной линии связи для каждого заголовка приветствия может быть весом d качества маршрута таблицы весов. В варианте осуществления каждый вес двунаправленной линии связи, полученный во время ряда итерационных процессов на этапах S1710-S1710' или итерационных процессов на этапах S1700-S1700', суммируется, позволяя, таким образом, вычислить вес d качества маршрута в таблице весов, которая будет обрабатываться в итерационных процессах. Затем управление переходит в точку (II) на фиг.18.
На этапе S1824 мощность приема для кандидата LD в адресаты (поле мощности приема не показано на фиг.15) обновляется в качестве мощности приема при приеме кадра приветствия. На этапе S1826 значение Е оценки кадра приветствия вычисляется, как описано выше, и значение E оценки для кандидата LD в адресаты обновляется. Затем на этапе S1828 счетчик выдержки для кандидата LD в адресаты (устройство для установки истечения срока действия таблицы весов) устанавливается в исходное состояние. Таким образом, управление передается на этап S1840, кандидаты LD в адресаты сортируются в порядке значения оценки, сужая, таким образом, круг предпочтительных кандидатов на приоритетной основе. На этапе S1710' итерационный цикл завершается.
'
Если на этапе S1718 никакой кандидат LD в адресаты не может быть обнаружен, источник (LS) кадра приветствия регистрируется вновь в таблице весов как кандидат LD в адресаты и управление передается на этап S1730. На этапе S1730 количество h переходов обновляется как количество переходов + 1 заголовка приветствия в записи для кандидата LD на новый адрес. На этапе S1732 вычисляется вес d качества маршрута кадра приветствия и вес d качества маршрута для кандидата LD в адресаты обновляется. Затем управление передается в точку (III) на фиг.18. На этапе S1834 мощность приема для кандидата LD в адресаты обновляется как мощность приема при приеме кадра приветствия. На этапе S1836 значение E оценки кадра приветствия вычисляется, как описано выше, и значение E оценки для кандидата LD в адресаты обновляется. На этапе S1838 счетчик выдержки для кандидата LD в адресаты устанавливается в исходное состояние. Затем управление передается на этап S1840, кандидаты LD в адресаты сортируются в порядке значения оценки, завершая, таким образом, итерационный цикл на этапе S1710.
'
Когда итерационные процессы на этапах S1710-S1710 заканчиваются, управление передается на этап S1850.
На этапе S1850 подтверждается, был ли кандидат LD в адресаты обновлен, используя заголовок приветствия в процессе итерационных процессов на этапах S1700-S1710', то есть было ли управление передано на этапы S1714-S1716. Если обновление было выполнено, управление передается в точку (VII) на фиг.19, и итерационный цикл заканчивается на этапе S1700'. Если обновление не было выполнено, управление передается на этап S1852. На этапе S1852 определяется, совпадает ли значение для узлового устройства (LS) как источника кадра приветствия с GD таблицы весов (как показано на фиг.15). Как вариант, производится оценка маршрутизация.
'
Если узловое устройство (LS) как источник кадра приветствия не совпадает с GD таблицы весов, управление передается в точку (VI) на фиг.19 и кандидаты LD в адресаты сортируются в порядке значения оценки на этапе S1930. На этапе S1700 итерационный цикл заканчивается.
Когда узловое устройство (LS) в качестве источника кадра приветствия совпадает с GD таблицы весов, управление передается на этап S1854. Затем кандидат на соседний узел разыскивается в таблице весов, соответствующей источнику (LS) кадра приветствия. Затем на этапе S1900 после точки (V) на фиг.19, когда кандидат LD в адресаты существует, управление передается на этап S1910. На этапе S1910 вычисляется вес d качества маршрута кадра приветствия и вес d качества маршрута для кандидата LD в адресаты обновляется. На этапе S1912 мощность приема для кандидата LD в адресаты обновляется как мощность приема, когда принимается кадр приветствия. На этапе S1914 значение E оценки для кадра приветствия вычисляется, как описано выше, и значение E оценки для кандидат LD в адресаты обновляется, затем на этапе S1916 счетчик выдержки для кандидата LD в адресаты устанавливается в исходное состояние. Хотя из-за ограничения ширины формы это опущено, когда имеется множество кандидатов LD в адресаты, процессы на этапах S1910-S1916 могут быть повторены для каждого из них. Затем управление передается на этап S1930, кандидат LD в адресаты сортируется в порядке значения оценки и итерационный цикл заканчивается на этапе S1700'.
'
С другой стороны, на этапе S1900, когда кандидата LD в адресаты нет, управление передается на этап S1920. На этапе S1920 количество переходов для нового кандидата LD в адресаты устанавливается как начальное значение (1 в этом примере). На этапе S1922 начальное значение (например, 0,5) устанавливается как вес w продолжительности промежуточных линий связи для кандидата LD в адресаты. На этапе S1924 вычисляется вес d качества маршрута для кадра приветствия и вес d качества маршрута для кандидата LD в адресаты обновляется. На этапе S1926 мощность приема для кандидата LD в адресаты обновляется как мощность приема при приеме кадра приветствия. На этапе S1928 значение E оценки для кадра приветствия вычисляется, как описано выше, и значение E оценки для кандидата LD в адресаты обновляется. Затем на этапе S1929, счетчик выдержки для кандидата LD в адресаты устанавливается в исходное состояние. Затем управление передается на этап S1930, кандидаты LD в адресаты сортируются в порядке значения оценки и итерационный цикл заканчивается на этапе S1700.
Когда итерационные процессы S1700-S1700' закончены для одного цикла, управление передается на этап S2000, показанный на фиг.20 после точки (VIII).
На этапе S2000 подтверждается, существует ли в таблице весов (группе) местного узлового устройства ввод, соответствующий узловому устройству (LS) (чьим LS является GD), как источник кадра приветствия. Когда таблица весов содержит ввод, управление передается на этап S2010. Если ввод не введен в таблицу весов, управление передается на этап S2001.
На этапе S2001 создается новая таблица весов, имеющая LS в качестве GD. На этапе S2002 количество переходов нового кандидата LD в адресаты устанавливается как начальное значение (1 в этом примере). На этапе S2003 начальное значение (например, 0,5) устанавливается как вес w протяженности промежуточных линий связи кандидата LD в адресаты. На этапе S2004 вычисляется вес d качества маршрута кадра приветствия и вес d качества маршрута кандидата LD в адресаты обновляется. На этапе S2005 мощность приема для кандидата LD в адресаты обновляется как мощность приема при приеме кадра приветствия. На этапе S2006 вычисляется значение E оценки для кадра приветствия, как описано выше, и значение E оценки для кандидата LD в адресаты обновляется. Затем на этапе S2007, счетчик выдержки для кандидата LD в адресаты устанавливается в начальное состояние. Управление передается на этап S2010.
На этапе S2010 итерационные процессы начинаются для каждого заголовка приветствия, содержащегося в кадре приветствия.
На этапе S2100 после точки (IX) подтверждается, существует ли GD заголовка приветствия в таблице весов местного узлового устройства. Когда существует ввод в таблицу весов, управление передается на этап S2010' и один итерационный цикл заканчивается. Если соответствующего ввода в таблицу весов не существует, управление передается на этап S2101.
'
На этапе S2101 создается новая таблица весов, соответствующая GD заголовка приветствия, и ввод, имеющий LS заказного заголовка кадра приветствия в качестве значения поля LD. На этапе S2102 количество h переходов нового кандидата LD в адресаты устанавливается как количество переходов + 1 для заголовка приветствия. На этапе S2103 начальное значение (например, 0,5) устанавливается в качестве веса w протяженности промежуточных линий связи для кандидата LD в адресаты. На этапе S2104 качество d маршрута вычисляется повторно, используя вес d качества маршрута для заголовка приветствия, и вес d качества маршрута для кандидата LD в адресаты инициируется. На этапе S2105 мощность приема для кандидата LD в адресаты обновляется как мощность приема при приеме кадра приветствия. На этапе S2106 вычисляется значение E оценки для заголовка приветствия и значение E оценки для кандидата LD в адресаты обновляется. На этапе S2107 счетчик выдержки для кандидата LD в адресаты устанавливается в исходное состояние. Затем управление передается на этап S2010 и итерационный цикл заканчивается.
Когда цикл итерационных процессов S2010-S2010' закончен, ряд процессов прекращается.
На фиг.22 представлена последовательность обмена кадром приветствия. Каждое узловое устройство широковещательно передает кадр приветствия на соседнее узловое устройство. Кадр приветствия содержит информацию линии связи, считающейся оптимальной в маршруте, каждому узлу. После приема кадра приветствия каждое узловое устройство сравнивает его с таблицей 6 из 6a управления соседними узлами и таблицей 7 или 7a весов и создает или обновляет информацию о весе каждого узла. Кроме того, информация линии связи о кадре приветствия обновляется со ссылкой на таблицу 6 или 6a управления соседними узлами, к которым она обращена. С помощью каждого узлового устройства, повторяющего операцию несколько раз, узловое устройство может получать многочисленные части информации об адресате линии связи, чтобы позволить каждому из них установить маршрут к другому узловому устройству.
В варианте осуществления, когда узловое устройство 1 или la в пределах заданного периода (например, в течение 30 минут) не может принять кадр приветствия, который был принят от конкретного узлового устройства, предполагается, что конкретное узловое устройство находится в состоянии, в котором никакие связи не могут быть установлены, и шлюзовое устройство информируется об этом. Затем, после принятия решения, исходя из содержания принятого кадра приветствия, шлюзовое устройство может быть информировано об аварийном состоянии, если оно обнаружено. Дополнительно, когда в узловом устройстве обнаруживается аномальное состояние, обращаясь к таблице 6 или 6a управления соседними узлами, приоритет узлового устройства может быть снижен, обновляя вес в соответствующей таблице 7 или 7a весов.
Дополнительно, в варианте осуществления, показанном на фиг.22, активное/неактивное состояние шлюзового устройства может быть проверено, передавая и принимая кадр приветствия к шлюзовому устройству и от него.
При контроле состояния между узловыми устройствами, когда в пределах заданного времени от узлового устройства партнера не принимается никакой кадр приветствия, кадр приветствия создает запрос, который передается на узловое устройство партнера, и состояние узлового устройства партнера проверяется в зависимости от того, принят ли кадр приветствия от узлового устройства партнера.
В варианте осуществления сеть проверяется в каждом узловом устройстве, как описано выше, информация об узловом устройстве на маршруте, через который прошел кадр приветствия, добавляется в кадр приветствия и сумма вычисляется сервером, таким образом контролирующим сеть.
В зависимости от вариантов осуществления настоящего изобретения, каждое узловое устройство контролирует сеть, используя кадр приветствия. Таким образом, нет необходимости отдельно передавать кадр, чтобы контролировать сеть, и сокращать количество переданных кадров. Кроме того, контролируя сеть с использованием передачи и приема кадра приветствия к соседнему узлу и от него, операция контроля почти в реальном времени может выполняться с меньшим реверсированием передачи по сравнению со случаем, в котором кадр контроля сети передается от центрального оборудования и состояние контролируется в зависимости от результата передачи.
На фиг.23 представлена схема оборудования, способного использовать для работы узловое устройство или выполнять программу в соответствии с вариантом осуществления настоящего изобретения.
2
2
2
На фиг.23 сначала представлен блок 2300 микропроцессора (MPU) для выполнения различных вычислительных процессов. Блок 2300 микропроцессора подключается для установления связи через кабельный физический процессор (PHY) 2312 и интерфейс 2310 MII (независимый от среды интерфейс)/MDIO (ввод/вывод данных управления) ("MII/MDIO" относится к "MII или MDIO"). MII и MDIO являются интерфейсами между физическим уровнем и подуровнем MAC (подуровень управления доступом к среде). Блок 2300 микропроцессора 2300 также подключается для установления связи через таймер IC 2322 для измерительного таймера и шину 2320 IC (межсоединений интегральных схем)/PIO (параллельного ввода-вывода) ("IC/PIO" относится к "IC или PIO"). Дополнительно, через шину 2330 PCI (межсоединение периферийных компонентов микропроцессор 2300 подключается для осуществления связи с динамическим оперативным запоминающим устройством (DRAM) 2332 и флэш-памятью 2334 в качестве запоминающих устройств и с процессором 2336 беспроводной местной сети (LAN) в качестве сетевого интерфейса. Очевидно, что устройства, отличные от показанных здесь, различных типов и стандартов могут соответственно использоваться в свете общего знания на предшествующем уровне техники.
MPU 2300 может выполнять различные процессы, загружая различные программы, такие как встроенное программное обеспечение, хранящееся во флэш-памяти 2334 в качестве устройства энергонезависимой памяти в DRAM 2332 и выполняющее программы. MPU 2300 может выполнять различные программы, такие как программа встроенного программного обеспечения, для того, чтобы управлять узловым устройством 1 при выполнении, например, вышеупомянутых процессов.
DRAM 2332 может также использоваться как буфер передачи и буфер приема для кадров. Флэш-память 2334 может хранить программы встроенного программного обеспечения и т.д., как описано выше. Кроме того, флэш-память 2334 может хранить определенную информацию (например, идентификатор узла и адрес MAC) в узловом устройстве 1 или la.
Кабельный процессор 2312 PHY является схемой для обработки физического уровня при проводном соединении. Процессор 2336 беспроводной местной сети является оборудованием для обработки на физическом уровне при подключении в беспроводной местной сети. Процессор 2336 беспроводной местной сети может содержать, например, антенну, ADC (аналого-цифровой преобразователь), DAC (цифроаналоговый преобразователь), модулятор, демодулятор, и т.д., и вести обработку на физическом уровне и подуровне MAC. Поэтому в настоящем варианте осуществления узловое устройство 1 или la может выполнять как с проводными, так и с беспроводными соединениями. Очевидно, что узловое устройство 1 и la может выполнять только проводное или только беспроводное соединение.
Таймер IC 2322 является схемой для счета истечения установленного времени и вывода сигнала прерывания, если прошло установленное время.
Узловые устройства описываются, главным образом, со ссылкой на упомянутый выше вариант осуществления, но программа управления для управления компьютером при выполнении упомянутого выше способа была также введена как пример варианта осуществления настоящего изобретения. Управляющая программа предоставляется после того, как она сохранена на считываемом компьютером носителе данных, таком как магнитный диск, магнитооптический диск, энергонезависимое полупроводниковое запоминающее устройство, оптический диск и т.д., загруженном в компьютер и выполняемом компьютером.
Компьютер для выполнения управляющей программы встраивается или подключается к узловому устройству, не показанному на приложенных чертежах, и управляет узлом, не показанным на приложенных чертежах, в соответствии с управляющей программой, так чтобы узловое устройство, не показанное на приложенных чертежах, могло работать подобным образом с узловым устройством 1 или 1а. Например, с другой точки зрения варианта осуществления, можно предположить, что MPU 2300 в качестве встроенного компьютера узлового устройства 1 или 1a управляет узловым устройством 1 или la в соответствии с управляющей программой, хранящейся во флэш-памяти 2334, а также управляет узловым устройством 1 или 1a для выполнения каждого процесса.
Как описано выше, соответственно узловому устройству варианта осуществления, хотя устройство применяется в большой сети связи, каждое узловое устройство может оптимизировать маршрут в соответствии с информацией, принятой от соседнего узлового устройства, и контролировать сеть.
Кроме того, в соответствии с настоящим вариантом осуществления, различные данные в табличном формате раскрыты для облегчения понимания. Однако настоящее изобретение не ограничивается этим примером и может использовать другие форматы управления, такие как XML, древовидная структура и т.д., через которые можно управлять связанными с ними данными.