СИСТЕМА И СПОСОБ ОСУЩЕСТВЛЕНИЯ СВЯЗИ С ВЫСОКОЙ ПРОПУСКНОЙ СПОСОБНОСТЬЮ В СЕТИ С ГИБРИДНОЙ ЯЧЕИСТОЙ ТОПОЛОГИЕЙ
SYSTEM AND METHOD FOR COMMUNICATION WITH HIGH BANDWIDTH IN A NETWORK WITH HYBRID MESH TOPOLOGY

Уровень техники
В сети с ячеистой топологией (mesh network) маршрут между узлом источника и узлом назначения проходит через узлы ретрансляции. Эти узлы ретрансляции принимают участие в ретрансляции сообщение, отправленного из узла источника в узел назначения. При передаче сообщения в стандартной сети с ячеистой топологией по единому физическому носителю каждый сетевой узел должен остановить передачу и освободить физический носитель, чтобы позволить передачу по тому же самому физическому носителю другому устройству. Это ограничение может предотвратить конфликты между сообщениями, отправленными из разных узлов, ведущих передачу одновременно. Таким образом, ограничивающим фактором в сетях с ячеистой топологией является количество раз, которое необходимо повторно передать (ретранслировать) сообщение на его маршруте из узла источника в узел назначения в сети. Задержка одной ретрансляции зависит от длины сообщения и времени обработки узла сети и других параметров. Узлы ретрансляции на маршруте могут вызывать задержку, поскольку они должны закончить прием сообщения перед началом его вторичной отправки. Это ограничение вызывает задержку, которая по существу является произведением количества ретрансляционных узлов на длительность времени ретрансляции.
x
В результате, разные узлы в сети с ячеистой топологией могут иметь различное время доступа в зависимости от количества ретрансляций. Кроме того, средняя задержка передачи между двумя узлами в сети с ячеистой топологией может возрастать с увеличением количества узлов сети пропорционально LOG(N), где N - количество узлов в сети, а Х - среднее количество соседних узлов (узлов с прямым соединением) на каждый узел.
Раскрытие изобретения
В соответствии с вариантами осуществления настоящего изобретения предлагается сеть с гибридной ячеистой топологией, причем сеть может содержать множество физических сред и множество узлов, соединенных через физические среды с образованием, по меньшей мере, одного маршрута наивысшей пропускной способности сети с гибридной ячеистой топологией (маршрут UTMH, ultimate throughput mesh hybrid route), содержащего множество узлов ретрансляции, соединенных через первую физическую среду с первым узлом и через вторую физическую среду со вторым узлом, причем между первым узлом и вторым узлом не может быть соединения через какую-либо из физических сред, а два узла маршрута UTMH, которые соединены через одну из физических сред, не могут иметь каких-либо соединений через ту же самую физическую среду с любым другим узлом в маршруте UTMH.
Кроме того, в соответствии с вариантами осуществления настоящего изобретения, узлы ретрансляции могут быть выполнены с возможностью начала ретрансляции сообщения, принятого из первого узла через первую физическую среду, во второй узел через вторую физическую среду до завершения приема сообщения.
Кроме того, в соответствии с вариантами осуществления настоящего изобретения, узлы могут строить дерево маршрутов UTMH в сети на основе топологии сети и доступных соединений между узлами в физических средах. Альтернативно, ведущее устройство может строить дерево маршрутов UTMH в сети на основе топологии сети и доступных соединений между узлами в физических средах и может сообщать данные, указывающие дерево, в узлы.
Кроме того, в соответствии с вариантами осуществления настоящего изобретения, маршруты могут вычисляться посредством назначения веса 1 для соединений в маршрутах UTMH, посредством назначения веса, эквивалентного средней длине сообщения, для других соединений в сети и посредством решения проблемы кратчайшего маршрута из заданного исходного пункта для графа с неотрицательными стоимостями маршрута для ребер.
Кроме того, в соответствии с вариантами осуществления настоящего изобретения, предлагается узел в сети с гибридной ячеистой топологией, причем узел может включать физический уровень, соединенный с множеством физических сред, и уровень соединений передачи данных, соединенный с физическим уровнем, причем физический уровень и уровень соединений передачи данных могут быть выполнены с возможностью начала ретрансляции сообщения, принятого через одну из физических сред, через другую физическую среду до завершения приема сообщения.
Кроме того, в соответствии с вариантами осуществления настоящего изобретения предлагается способ для осуществления связи с высокой пропускной способностью в сети с гибридной ячеистой топологией. Способ может включать соединение множества узлов ретрансляции через первую физическую среду с первым узлом и через вторую физическую среду со вторым узлом с образованием маршрута UTMH, причем между первым узлом и вторым узлом отсутствует соединение через какую-либо из физических сред, а два узла маршрута UTMH, которые соединены через одну из физических сред, не могут иметь каких-либо соединений через ту же самую физическую среду с любым другим узлом в маршруте UTMH.
Кроме того, в соответствии с вариантами осуществления настоящего изобретения, способ может включать начало ретрансляции сообщения, принятого из первого узла через первую физическую среду, во второй узел через вторую физическую среду до завершения приема сообщения.
Кроме того, в соответствии с вариантами осуществления настоящего изобретения, способ может включать построение дерева маршрутов UTMH в сети на основе топологии сети и доступных соединений между узлами через физические среды и сообщение данных, указывающих дерево, в узлы.
Кроме того, в соответствии с вариантами осуществления настоящего изобретения, способ может включать назначение веса 1 для соединений в маршруте UTMH, назначение веса, эквивалентного средней длине сообщения, для других соединений в сети и решение проблемы кратчайшего маршрута из заданного исходного пункта для графа с неотрицательными стоимостями маршрута для ребер.
Краткое описание чертежей
Сущность изобретения конкретно выражена и непосредственно заявлена в заключительной части описания. Изобретение, однако, по отношению к организации и способу функционирования, совместно с его задачами, признаками и преимуществами может быть наилучшим образом понято с учетом последующего детального описания при его прочтении с сопровождающими чертежами.
На фиг.1 представлена схематичная диаграмма, иллюстрирующая пример топологии сети с гибридной ячеистой топологией в соответствии с вариантами осуществления настоящего изобретения.
На фиг.2 показана схематичная иллюстрация трех узлов, относящихся к сети с гибридной ячеистой топологией, обеспечивающей возможность использования режима повышенной пропускной способности для сети с гибридной ячеистой топологией (режим ITMH) или режима наивысшей пропускной способности для сети с гибридной ячеистой топологией (режим UTMH) в соответствии с вариантами осуществления изобретения.
На фиг.3 показана схематичная диаграмма, иллюстрирующая примерный маршрут в сети с гибридной ячеистой топологией в соответствии с вариантами осуществления изобретения.
На фиг.4 показана схематичная диаграмма, иллюстрирующая пример топологии сети с гибридной ячеистой топологией, которая поддерживает режим UTMH в соответствии с вариантами осуществления настоящего изобретения.
На фиг.5 показана диаграмма, иллюстрирующая способ реализации режима ITMH в соответствии с вариантами осуществления изобретения.
На фиг.6 показана диаграмма, иллюстрирующая способ реализации режима UTMH в соответствии с вариантами осуществления изобретения.
Очевидно, что для простоты и ясности иллюстрирования, элементы, показанные на фигурах, не обязательно показаны в масштабе. Например, размеры некоторых элементов могут быть преувеличены по отношению к другим элементам для понятности. Кроме того, в тех случаях, когда это допустимо, цифровые обозначения могут повторяться на фигурах для обозначения соответствующих или аналогичных элементов.
Осуществление изобретения
В последующем детальном описании даны многочисленные конкретные детали для обеспечения полного понимания изобретения. Однако для специалиста в данной области техники должно быть понятно, что настоящее изобретение может применяться на практике без этих конкретных деталей. В других примерах хорошо известные способы, процедуры и компоненты детально не описаны для того, чтобы не делать изобретение неясным.
Хотя варианты осуществления изобретения не ограничены в этом отношении, описания, использующие такие термины, как, например, «обработка», «вычисление», «расчет», «определение», «установление», «анализ», «проверка» и т.п. могут относиться к операции (операциям) и/или процессу (процессам) компьютера, компьютерной платформы, компьютерной системы или другого электронного вычислительного устройства, которое преобразует и/или трансформирует данные, представленные как физические (например, электронные) величины в компьютерных регистрах и/или памяти в другие данные, аналогично представленные как физические величины в компьютерных регистрах и/или памяти или другом носителе информации, который может хранить инструкции по выполнению операций и/или процессов.
Хотя варианты осуществления не ограничены в этом отношении, термины «много» и «множество» при использовании могут включать в себя, например, «несколько» или «два или более». Термины «много» или «множество» могут быть использованы в описании для описания двух или более компонентов, устройств, элементов, единиц, параметров и т.п. Если не выражено явным образом, варианты осуществления способа, описанные здесь, не ограничены конкретным порядком или последовательностью. Кроме того, некоторые из описанных вариантов осуществления способа или его элементов могут происходить или осуществляться в один и тот же момент времени.
Система связи с ячеистой топологией обычно может включать в себя узел (узлы) повтора или ретрансляции для покрытия предварительно заданной области или предварительно определенной группы узлов сети альтернативными путями связи. Поскольку каждый узел изначально имеет возможности осуществления связи, каждый узел может быть использован в качестве повторителя (ретранслятора), который может сообщать данные и/или информационное содержание.
Обычные сети с ячеистой топологией могут включать в себя одну физическую среду для передачи данных. Сеть с гибридной ячеистой топологией в соответствии с вариантами осуществления настоящего изобретения может включать в себя более чем одну физическую среду, как описано в патентной заявке №12/364727, которая полностью включена в настоящее описание посредством ссылки. Сеть с гибридной ячеистой топологией может передавать данные через множество физических сред. Например, сеть с гибридной ячеистой топологией может передавать данные через две раздельных физических среды, такие как, но без ограничения, линии передачи по электрическим сетям (PLC, power line communication) или радиочастотные (РЧ) линии. В соответствии с вариантами осуществления настоящего изобретения, необязательно наличие физического соединения между каждой парой узлов через обе физические среды. Например, в сети с гибридной ячеистой топологией, имеющей две физических среды, каждая пара узлов может иметь физическое соединение только в первой среде, только во второй среде или в обеих.
В соответствии с вариантами осуществления настоящего изобретения в сети с гибридной ячеистой топологией каждый из узлов сети, или концевых устройств, может быть соединен с одним или более другим концевым устройством сети с ячеистой топологией через одну или более физических сред. Взаимосвязь в каждой из физических сред может быть получена посредством выделенного соединения между каждым из узлов или через общую физическую среду.
В некоторых общих физических средах качество и сила физического соединения между каждой парой узлов могут быть непостоянными. Качество и сила могут зависеть от динамических условий окружающей среды и физических условий, таких как, например, расстояние между узлами, внешние помехи, другие узлы, передающие в той же среде и т.п. В случаях, когда качество и сила физического соединения среди группы узлов, подключенных к общей среде, хорошее, конфликты могут происходить в тех случаях, когда конфликтующие узлы осуществляют передачу в одно и то же время. Однако некоторые узлы, передающие в общей физической среде, могут не иметь возможности осуществлять связь с некоторыми другими узлами, имеющими доступ к той же общей среде, если внешняя и физическая обстановка обеспечивает изоляцию между разными областями, осуществляющими между собой связь. Таким образом, в общей физической среде без конфликтов могут осуществляться несколько связей, если внешняя и физическая обстановка обеспечивает изоляцию между разными областями, осуществляющими между собой связь. Это свойство может быть использовано для повторного одновременного использования общей среды, когда это возможно. Примером такой системы является сотовая беспроводная связь, в которой один и тот же РЧ канал может быть одновременно использован разными узлами, если узлы расположены в изолированных сотах.
Обратимся к фиг.1, на которой показана схематичная диаграмма, иллюстрирующая пример топологии сети 100 с гибридной ячеистой топологией в соответствии с вариантами осуществления настоящего изобретения. В соответствии с вариантами осуществления настоящего изобретения сеть 100 может содержать множество узлов 110, 112, 114, 116, 118, 120, 122, 124, 126, 128, 130 и 132 и, по меньшей мере, две физические среды, именно, 150, показанная точечной линией, и 160, показанная штриховой линией. По меньшей мере, часть узлов 112, 114, 116, 118, 122, 124, 126, 128 и 130 могут быть выполнены с возможностью осуществления связи, по меньшей мере, через две физические среды 150 и 160.
Сообщение, отправленное из узла 110 в узел 126, может следовать маршрутом 170 через узлы 112, 114, 116, 118, 120 и 124. Соответственно, узел 110 может функционировать в качестве узла источника, узел 126 может функционировать в качестве узла назначения, а узлы 112, 114, 116, 118, 120 и 124 могут функционировать в качестве узлов ретрансляции. Для специалиста в данной области техники очевидно, что могут существовать альтернативные маршруты, соединяющие узел 110 с узлом 126. Например, сообщение, отправленное из узла 110, может попасть в узел 126 через узлы 112, 114, 122, 118, 120, 124 и 126.
Поскольку в соответствии с примером, представленным на фиг.1, узлы 110, 112 и 114 могут быть соединены друг с другом через одну физическую среду 150, узлу 112 ретрансляции может потребоваться завершить прием сообщения до того, как узел 112 сможет начать вторичную отправку сообщения. Однако, поскольку узел 114 ретрансляции может быть соединен с узлом 116 ретрансляции через другую физическую среду 160, узел 114 может начать ретрансляцию сообщения до того, как узел 114 закончит прием сообщения. Минимальная теоретическая задержка в этом сценарии может быть равна времени, необходимому узлу 114 для приема и ретрансляции одного бита. Минимальная практическая задержка для ретрансляции первого бита в сообщении также может включать в себя задержку доступа к соединению. Время, необходимое для приема и ретрансляции одного бита, далее будет называться задержкой в один бит. Узел 114 может ретранслировать сообщение, по существу, с задержкой в один бит, поскольку, когда первый бит сообщения ретранслирован, оставшиеся линии на последующем маршруте могут быть по существу свободными и по существу отсутствуют другие биты, идущие одновременно. Узел 116 может ретранслировать сообщение, принятое из узла 114, в узел 118 ретрансляции с задержкой в один бит, поскольку узлы 114 и 116 соединены друг с другом через физическую среду 160, а узлы 116 и 118 соединены через другую физическую среду 150. Узел 118 ретрансляции возможно должен завершить прием сообщения из узла 116 перед тем, как узел 118 начнет вторичную отправку сообщения в узел 120, поскольку узлы 116, 118 и 120 могут быть соединены друг с другом через одну физическую среду 150. Аналогично, узел 120 возможно должен завершить прием сообщения из узла 118 перед тем, как узел 120 начнет вторичную отправку сообщения в узел 124, поскольку узлы 118, 120 и 124 соединены друг с другом через одну физическую среду 150. Узел 124 может ретранслировать сообщение, принятое из узла 120, в узел 126 с задержкой в один бит, поскольку узлы 120 и 124 соединены друг с другом через физическую среду 150, а узлы 124 и 126 соединены друг с другом через другую физическую среду 160.
В соответствии с вариантами осуществления изобретения сетевые узлы могут содержать физический уровень, соединенный с множеством физических сред, и уровень соединений передачи данных, соединенный с физическим уровнем. Ретрансляция сообщения, принятого через одну физическую среду, через отличающуюся физическую среду до завершения приема сообщения может быть выполнена физическим уровнем и уровнем соединений передачи данных сетевого узла и, следовательно, по существу может не вовлекать дополнительную обработку узлом повторения (ретрансляции), как детально описано в патентной заявке США №12/364727.
Рабочий режим сети с гибридной ячеистой топологией, в котором, по меньшей мере, один узел ретрансляции выполнен с возможностью ретрансляции сообщений с использованием преимущества наличия множества физических сред с задержкой в один бит далее может называться режимом повышенной пропускной способности для сети с гибридной ячеистой топологией (ITMH, improved throughput mesh hybrid). Рабочий режим сети с гибридной ячеистой топологией, в котором все узлы ретрансляции во всех предварительно заданных маршрутах выполнены с возможностью ретрансляции сообщений с задержкой в один бит, далее может называться режимом наибольшей пропускной способности сети с гибридной ячеистой топологией (UTMH, ultimate throughput mesh hybrid route). Необходимо отметить, что все предварительно заданные маршруты в режиме UTMH могут исходить из одного узла или заканчиваться в одном узле сети.
С целью установления режима ITMH или режима UTMH могут быть определены выделенные маршруты для соединения узлов источников с узлами назначения. Маршруты могут быть предварительно заданы и могут указывать, какие конкретные узлы должны участвовать в маршрутах, чтобы избежать конфликта во множестве физических сред.
При реализации сети 100 с гибридной ячеистой топологией в соответствии с вариантами осуществления изобретения, один узел может быть определен в качестве ведущего устройства 132. Ведущее устройство 132 может строить пути или маршруты связи в сети на основе топологии сети и доступных путей соединения между узлами в различных физических средах. Топология этих путей или маршрутов может быть описана в качестве дерева. Это дерево может быть использовано всеми остальными узлами в сети с гибридной ячеистой топологией в качестве топологии пути, используемой по умолчанию. В случае объявления соединения не работающим или разорванным, ведущее устройство 132 может перестроить дерево путей связи для покрытия или компенсации разорванного соединения.
В соответствии с вариантами осуществления изобретения сеть 100 может реализовывать, по меньшей мере, один дополнительный режим связи, такой как, но не ограничиваясь, стандартный точка-точка, многоадресный, широковещательный и т.п. для управления и конфигурирования маршрутов. Этот режим связи, далее называемый режимом управления и конфигурации, может использоваться ведущим устройством 132 для сообщения данных, указывающих маршруты, которые могут быть использованы в режиме ITMH или UTMH, в узлы сети 100 и управления сетью 100 во время использования режима ITMH или UTMH для передачи данных. Режим управления и конфигурации также может быть использован ведущим устройством 132 для непрерывного или периодического наблюдения за маршрутами между узлами и для получения информации о соединениях, доступных в топологии сети с ячеистой топологией. В соответствии с некоторыми вариантами осуществления изобретения ведущее устройство 132 использует алгоритмы маршрутизации и управляет сетью таким образом, чтобы иметь возможность реализовать режим UTMH в сети с гибридной ячеистой топологией. Например, ведущее устройство 132 может конфигурировать выбранные узлы для осуществления связи с другими узлами только через одну физическую среду из множества физических сред, доступных для обеспечения возможности ретрансляции сообщений с задержкой в один бит.
Маршруты, формируемые ведущим устройством 132, могут храниться централизованным образом, например, ведущее устройство 132 может содержать носитель информации для хранения, среди прочего, маршрутов, сформированных ведущим устройством 132. Дополнительно или альтернативно маршруты, сформированные ведущим устройством 132, могут храниться распределенным образом носителями информации в различных узлах в сети 100. Эти маршруты могут постоянно или динамически обновляться в соответствии со спецификациями сети 100 и в соответствии с происходящими событиями, такими как сбой соединения, добавление в сеть новых узлов, изменение внешних помех, загрузка сети и т.п.
В соответствии с вариантами осуществления изобретения, ведущее устройство 132 может оптимизировать маршруты для существенной минимизации задержки маршрутов. Например, часть 175 маршрута 170, соединяющая узел 110 с узлом 114 через узел 112, может быть заменена маршрутом 180, соединяющим узел 110 с узлом 114 через узлы 128 и 130. Маршрут 180 может быть длиннее части 175, поскольку маршрут 180 содержит больше соединенных друг с другом узлов, чем часть 175. Однако задержка передачи сообщения по маршруту 180 в соответствии с вариантами осуществления изобретения может быть меньше, чем задержка передачи сообщения по части 175. При передаче по части 175 узлу 112 может потребоваться завершить прием сообщения перед тем, как узел 112 начнет вторично передавать сообщение. Однако при передаче сообщения по маршруту 180 каждый из узлов 128 и 130 может осуществлять ретранслирование с задержкой в один бит.
В соответствии с вариантами осуществления изобретения узлы могут иметь данные, указывающие топологию сети и доступные соединения, сохраненные в средствах хранения, связанных с этим узлом. Как описано ранее, эти данные могут собираться ведущим устройством. Альтернативно, топология сети и доступные соединения могут быть распределены среди узлов сети без ведущего устройства, реализуя распределенное управление сетью. В этом случае, по меньшей мере, часть узлов может иметь достаточную информацию для построения дерева маршрутов в сети на основе топологии сети и доступных маршрутов взаимного соединения или связей между множеством узлов во множестве физических сред. Варианты осуществления настоящего изобретения не ограничены конкретной техникой управления сетью.
Далее рассматривается фиг.2, на которой показана схематическая иллюстрация трех узлов 210, 220 и 230 из множества возможных узлов (не показаны), относящихся к сети с гибридной ячеистой топологией, обладающей возможностью использования режима ITMH или UTMH в соответствии с вариантами осуществления изобретения. Сеть с гибридной ячеистой топологией может содержать две физических среды, именно, 240, показанную точечной линией, и 250, показанную штриховой линией. Предшествующий узел 210 может передавать сообщение или ретранслировать сообщение, принятое из других узлов в сети (не показаны), в узел 230 через узел 220 ретрансляции. Последующий узел 230 может быть конечным узлом назначения сообщения или может ретранслировать сообщение в другой узел по маршруту, например, в узел 260. Узел 220 может представлять собой любой узел ретрансляции в сети, который может ретранслировать сообщение с задержкой в один бит. Предшествующий узел 210 может представлять собой любой предшествующий узел по отношению к узлу ретрансляции в отношении направления перемещения сообщения по маршруту из узлов, и последующий узел 230 может представлять собой любой следующий узел относительно узла ретрансляции по отношению к направлению перемещения сообщения по маршруту. Узлы 210 и 230 могут быть соседними для узла 220. В соответствии с вариантами осуществления изобретения, узел ретрансляции может ретранслировать сообщение с задержкой в один бит, если удовлетворены следующие правила UTMH:
- Отсутствуют физические соединения в какой-либо физической среде между предшествующим узлом 210 и последующим узлом 230; это правило обеспечивает то, что когда узел 230 ретранслирует сообщение, оно не будет создавать помех передаче из узла 210.
- Существует одно физическое соединение в одной из физических сред между предшествующим узлом 210 и узлом 220 ретрансляции и одно физическое соединение в другой физической среде между узлом 220 ретрансляции и последующим узлом 230; это правило обеспечивает то, что узел 230 может принимать передачу из узла 220 без помех от узла 210.
- Два узла в пути с прямым соединением в одной физической среде не имеют каких-либо дополнительных прямых соединений в той же физической среде с какими-либо другими узлами пути. Таким образом, даже несмотря на то, что оба узла на одном пути могут передавать в одно и то же время в одной и той же общей среде, они могут не создавать помех. Это может происходить в реальной эксплуатационной ситуации, например, если внешняя и физическая обстановка обеспечивает изоляцию между разными областями связи в физической среде. Например, четвертый узел 260 имеет соединение 270 через физическую среду 240 только с узлом 230. Если узел 260 имел бы физические соединения с другими узлами на пути через физическую среду 240, соединение 270 могло бы получать помехи от других узлов. Например, если узел 260 имел бы физическое соединением с узлом 210 через физическую среду 240, соединение 270 могло бы получать помехи от передач узла 210.
Далее рассматривается фиг.3, на которой показана схематичная диаграмма, иллюстрирующая пример маршрута 300 в сети с гибридной ячеистой топологией в соответствии с вариантами осуществления изобретения. Узел 310 может быть узлом источника, узел 350 может быть узлом назначения, а узлы 320, 330 и 340 могут быть узлами ретрансляции по маршруту 300. Физические среды 360 и 370 могут быть двумя отдельными физическими средами. Может быть очевидно, что все узлы ретрансляции по маршруту 300 могут соответствовать правилам UTMH, указанным выше по отношению к фиг.2. В частности, не могут присутствовать физические соединения в какой-либо из физических сред 360 и 370 между узлами 310 и 330, узлами 320 и 340 и узлами 330 и 350. Не могут присутствовать прямые физические соединения через физическую среду 360 между узлами 310 и 340 и через физическую среду 370 между узлами 320 и 350. Может быть только одно физическое соединение в одной из физических сред 360 или 370 между каждой парой соседних узлов 310-320, 320-330, 330-340 и 340-350, и каждый узел 320, 330 и 340 ретрансляции может иметь соединение с двумя соседними узлами в разных физических средах 360 и 370. Таким образом, все узлы 320, 330 и 340 ретрансляции в маршруте 300 могут осуществлять ретрансляцию с задержкой в один бит. Следовательно, каждый из узлов 320, 330 и 340 ретрансляции в маршруте 300 может вносить задержку в один бит в общую задержку между узлами 310 и 350. Общая задержка маршрута 300 может быть по существу равна трем задержкам в один бит. В общем случае, в котором маршрут имеет М узлов ретрансляции, каждый из которых удовлетворяет правилам UTMH, накопленная задержка на маршруте может по существу быть равной М задержкам в один бит.
Далее рассматривается фиг.4, на которой показана схематичная диаграмма, иллюстрирующая пример топологии сети 400 с гибридной ячеистой топологией, которая поддерживает режим UTMH в соответствии с вариантами осуществления изобретения. В соответствии с вариантами осуществления изобретения сеть 400 может содержать множество узлов А1, В1, В2, В3, С1, С2, С3, С4, D1, D2, D3, D4 и D5 и, по меньшей мере, две физические среды 410 и 420. По меньшей мере, некоторые узлы, например, В2, С2 и С3 могут быть выполнены с возможностью осуществления связи через, по меньшей мере, две физические среды 150 и 160.
Сеть 400 может поддерживать режим UTMH относительно узла А1, таким образом, все предварительно заданные маршруты в режиме UTMH могут исходить из узла А1 или заканчиваться в узле А1. Таблица 1 ниже перечисляет возможные пути из узла А1 в другие узлы в системе. Можно увидеть, что каждый маршрут удовлетворяет правилам UTMH.
Таблица 1
Маршруты, соединяющие А1 со всеми остальными узлами
Узел назначения:
Маршрут:
В1
А1-В1
В2
А1-В1-В2
В3
А1-В3
С1
А1-В1-С1
С2
А1-В1-С2
С3
А1-В3-С3
С4
А1-В3-С4
D1
A1-B1-C1-D1
D2
A1-B1-C1-D2
D3
A1-B3-C3-D3
D4
A1-B3-C4-D4
D5
A1-B3-C4-D5
Как указывалось выше, накопленная задержка на маршруте UTMH с М узлов ретрансляции может по существу равняться М задержек в один бит. Термин «маршрут UTMH» может относиться к маршрутам, в которых все узлы повторения соответствуют правилам UTMH и осуществляют ретрансляцию с задержкой в один бит. Термин «обычный маршрут» может относиться к маршрутам, где ни один из узлов не поддерживает режим UTMH. Задержки маршрута UTMH может быть относительно малой по сравнению с обычным маршрутом в случаях маршрутов UTMH с относительно малым количеством узлов повторения и длинных сообщений. Однако, если передаваемые сообщения короткие, а количество узлов повторения в маршруте UTMH велико, общая задержка маршрута UTMH может быть велика относительно задержки обычного маршрута. Если, например, имеются два маршрута, соединяющих узел источника с узлом назначения, причем первый маршрут является маршрутом UTMH с относительно большим количеством узлов повторения, а второй маршрут является обычным маршрутом с относительно малым количеством узлов повторения, и если передаваемое сообщение короткое, то задержка обычного маршрута может быть меньше, чем задержка маршрута UTMH. Следовательно, если передаваемые сообщения короткие, и сеть не ограничивает длину маршрутов, то задержки в один бит могут учитываться при конструировании маршрутов в сети с целью минимизации задержек в сети.
Примерный способ вычисления наилучших маршрутов в заданной сети, учитывающий задержку в один бит в соответствии с вариантами осуществления изобретения, может быть основан на алгоритме, который находит кратчайшие маршруты между узлами в задаче графа при использовании назначения уникальных весов для каждого соединения между узлами. То есть, решается проблема нахождения пути между двумя вершинами (или узлами) так, чтобы сумма весов составляющих его ребер была минимизирована. Веса графа могут быть установлены следующими:
i. В каждом маршруте UTMH для каждого соединения маршрута назначается значение 1.
ii. Для всех остальных соединений сети назначается значение L, причем L может быть эквивалентным средней или максимальной длине сообщения.
Указанные веса могут гарантировать, что если сумма всех задержек в один бит в маршруте UTMH меньше, чем задержка обычного маршрута с обычными ретрансляциями, может быть выбран маршрут UTMH, в противном случае может быть использован кратчайший обычный маршрут.
Построение дерева маршрутов связи может достигаться решением проблемы кратчайшего маршрута из заданного исходного пункта для графа с неотрицательными стоимостями маршрута для ребер. Например, получение дерева кратчайшего маршрута может быть основано на алгоритме Дейкстры с назначением весов для возможных соединений в соответствии с вышеуказанными правилами i и ii. Альтернативно может использоваться и другой подходящий алгоритм.
Следующие вычисления могут демонстрировать среднее снижение задержки режима UTMH в соответствии с вариантами осуществления изобретения по сравнению со стандартным рабочим режимом сети с ячеистой топологией. Оценка общей временной задержки сообщения, переданного из узла источника в узел назначения в стандартном, не ITMH или UTMH, режиме, может быть вычислена следующим образом:
где N - количество узлов в сети;
j - количество битов в сообщении;
Х - среднее количество прямых соединений, которые может иметь каждый узел в сети;
ВремяДоступа - время задержки каждого кадра битов в сообщении, вызванной физическим уровнем; задержка включает в себя время, необходимое физическому уровню для демодуляции входящего бита и повторной его модуляции для ретрансляции вторым физическим уровнем. Для простоты вычислений считается, что в одном кадре может быть передано полное сообщение из j бит, следовательно, это значение рассматривается как постоянный коэффициент, называемый «задержка в один бит»;
TXtime (j) - время передачи j битов через физическую среду. Это значение включает в себя фактическую бодовую скорость в линии и игнорирует распространение сигнала и другие по существу пренебрежимые задержки.
x
Log(N) - глубина сети, которая является максимальной высотой любого минимального остовного дерева (MST, minimum spanning tree) сети. Алгоритм MST может быть использован для создания топологии путей, используемой по умолчанию, для узлов в стандартных сетях с ячеистой топологией, например, путем реализации жадного поиска в дереве, как это известно в уровне техники.
Общая временная задержка сообщения, переданного из узла источника в узел назначения в режиме UTMH, вычисляется следующим образом:
x
ВремяДоступа*Log(N) много меньше, чем TXtime (j) и TXtime (j)*Log(N), и поэтому может быть проигнорировано. Отношение между Временем передачи не в режиме UTMH и Временем передачи UTMH может быть вычислено следующим образом:
x
Следовательно, средняя задержка для передачи сообщений в режиме UTMH в соответствии с вариантами осуществления изобретения может быть снижена, по существу, в Log(N) раз по сравнению со стандартной сетью с ячеистой топологией.
В соответствии с вариантами осуществления изобретения задержка передачи всего сообщения по маршруту в режиме UTMH по существу равна количеству узлов ретрансляции, умноженному на задержку в один бит, плюс TXtime (j). Поскольку TXtime (j) обычно может быть много больше, чем количество узлов ретрансляции, умноженное на задержку в один бит, способ маршрутизации в режиме UTMH позволяет по существу одинаковое время доступа к каждому узлу в сети независимо от количества необходимых ретрансляций.
Далее обращается внимание на фиг.5, которая является диаграммой, иллюстрирующей способ осуществления режима ITMH в соответствии с вариантами осуществления изобретения. В соответствии с вариантами осуществления изобретения сеть с гибридной ячеистой топологией может быть выполнена с возможностью передачи сообщений в режиме ITMH (блок 510). Могут быть заданы и распределены по узлам сети маршруты, и узлы, которые могут удовлетворять правилам UTMH, могут быть выполнены с возможностью ретрансляции сообщений с задержкой в один бит. Сообщение может быть отправлено из узла источника (блок 520). Если следующий узел в маршруте не является узлом назначения (блок 530), то следующий узел может быть узлом ретрансляции. В блоке 540 может быть проверено, соответствует ли узел ретрансляции правилам UTMH. Если узел ретрансляции не соответствует правилам UTMH, то узлу ретрансляции может потребоваться завершить прием сообщения до ретрансляции сообщения (блок 560). Если, однако, узел ретрансляции соответствует правилам UTMH, то узел ретрансляции может ретранслировать сообщение с задержкой в один бит в другой физической среде (блок 550). Когда сообщение достигает узла назначения, оно может быть принято узлом назначения (блок 570).
Далее обращается внимание на фиг.6, которая является диаграммой, иллюстрирующей способ осуществления режима UTMH в соответствии с вариантами осуществления изобретения. В соответствии с вариантами осуществления изобретения сеть с гибридной ячеистой топологией может быть выполнена с возможностью передачи сообщений в режиме UTMH (блок 610). Могут быть заданы маршруты, удовлетворяющие правилам UTMH. Эти маршруты могут быть распределены по узлам сети. Может потребоваться сконфигурировать сетевые соединения между узлами в разных физических средах так, чтобы узлы ретрансляции смогли удовлетворять правилам UTMH. Сообщение может быть отправлено из узла источника (блок 620). Если следующий узел в маршруте не является узлом назначения (блок 630), то этот узел может быть узлом ретрансляции. Узлы ретрансляции могут ретранслировать сообщения по маршруту с задержкой в один бит (блок 640). Когда сообщение достигает узла назначения, оно может быть принято узлом назначения (блок 650).
Некоторые варианты осуществления настоящего изобретения могут быть реализованы программно для выполнения системой на основе процессора, например, ведущим устройством 132. Например, варианты осуществления изобретения могут быть выполнены в коде и могут быть сохранены на носителе информации; содержащем сохраненные на нем команды, которые могут быть использованы для программирования системы для выполнения команд. Носитель информации может включать, не ограничиваясь этим, любой тип диска, включая флоппи-диски, оптические диски, неперезаписываемые компакт-диски (CD-ROM), перезаписываемые компакт-диски (CD-RW) и магнитооптические диски, полупроводниковые устройства, такие как постоянные запоминающие устройства (ПЗУ), оперативные запоминающие устройства (ОЗУ), такие как динамические ОЗУ (DRAM), стираемые программируемые постоянные запоминающие устройства (EPROM), флеш-память, электрическим образом стираемые программируемые постоянные запоминающие устройства (EEPROM), магнитные или оптические карты или любой другой тип носителя, пригодный для хранения электронных команд, включая программируемые запоминающие устройства. Другие реализации вариантов осуществления изобретения могут содержать выделенное, заказное, выполненное по специальному заказу или готовое аппаратное обеспечение, встроенное программное обеспечение или их комбинации.
Варианты осуществления настоящего изобретения могут быть реализованы системой, которая может включать в себя такие компоненты, как, но не ограничиваясь этим, множество центральных модулей обработки (CPU, central processing unit) или другие подходящие многоцелевые или специализированные процессоры или контроллеры, множество входящих модулей, множество исходящих модулей, множество модулей памяти и множество модулей хранения. Такие системы могут дополнительно содержать другие подходящие аппаратные компоненты и/или программные компоненты.
В то время как здесь описаны и проиллюстрированы определенные признаки изобретения, специалисту в данной области техники должны быть очевидны множество модификацией, замен, изменений и эквивалентов. Следовательно, должно быть понятно, что прилагаемая формула изобретения покрывает все такие модификации и изменения, подпадающие по действительную сущность настоящего изобретения.