По вашему запросу ничего не найдено :(
Убедитесь, что запрос написан правильно, или посмотрите другие
наши статьи:
Виртуальные сети - это, в простейшем виде, создание логических топологий, построенных на основе физической топологии. Эти логические топологии часто называют виртуальными топологиями - отсюда и концепция виртуализации сети. Эти топологии могут состоять из одного виртуального канала в более крупной сети, называемого туннелем, или набора виртуальных каналов, которые кажутся полной сетью поверх физической сети, называемой наложением.
Этот раздел лекций начнется с обсуждения того, почему создаются и используются виртуальные топологии, проиллюстрированные двумя примерами использования. Во втором разделе этих лекций будут рассмотрены проблемы, которые должно решить любое решение виртуализации, а в третьем разделе будут рассмотрены сложности при виртуализации сети. Далее будут рассмотрены два примера технологий виртуализации: сегментная маршрутизация (segment routing-SR) и программно - определяемые глобальные сети (Software-Defined Wide Area Networks- SD-WAN).
Понимание виртуальных сетей
Виртуализация усложняет проектирование протоколов, сетей и устранение неполадок, так зачем же виртуализировать? Причины, как правило, сводятся к разделению нескольких потоков трафика в одной физической сети. Это может показаться подозрительно похожим на другую форму мультиплексирования, потому что это еще одна форма мультиплексирования. Основные различия между рассмотренными до сих пор формами мультиплексирования и виртуализацией заключаются в следующем:
Позволяет нескольким плоскостям управления работать с различными наборами информации о достижимости в рамках одной физической топологии;
Позволяет нескольким наборам достижимых пунктов назначения работать в одной физической топологии без взаимодействия друг с другом;
Рассмотренные до этого момента методы мультиплексирования были сосредоточены на том, чтобы позволить нескольким устройствам использовать одну физическую сеть (или набор проводов), позволяя каждому устройству взаимодействовать с любым другим устройством (при условии, что они знают друг о друге с точки зрения достижимости). Виртуализация направлена на разбиение одной физической сети на несколько доменов достижимости, где каждое устройство в домене достижимости может взаимодействовать с любым другим устройством в том же домене достижимости, но устройства не могут связываться между доменами достижимости (если нет какой-либо точки соединения между достижимостью домены).
На рисунке 1 показана сеть с виртуальной топологией, расположенной поверх физической топологии.
На рисунке 1 виртуальная топология была создана поверх физической сети, с виртуальным каналом [C,H], созданным для передачи трафика по сети. Чтобы создать виртуальную топологию, C и H должны иметь некоторую локальную информацию пересылки, отделяющую физическую топологию от виртуальной топологии, которая обычно проходит либо через E, либо через D. Это обычно принимает форму либо специального набора записей виртуального интерфейса в локальной таблице маршрутизации, либо таблицы виртуальной маршрутизации и пересылки (VRF), содержащей только информацию о виртуальной топологии.
Рассмотрение потока пакетов через виртуальную топологию может быть полезно для понимания этих концепций. Как бы выглядел поток пакетов, если бы C и H имели виртуальные интерфейсы? Рисунок 2 демонстрирует это.
На рисунке 2 процесс пересылки выполняется следующим образом:
A передает пакет к M.
C получает этот пакет и, исследуя свою локальную таблицу маршрутизации, находит, что кратчайший путь к месту назначения лежит через виртуальный интерфейс к H. Этот виртуальный интерфейс обычно называется туннельным интерфейсом; он выглядит с точки зрения таблицы маршрутизации, как и любой другой интерфейс маршрутизатора.
Виртуальный интерфейс, через который необходимо передать пакет, имеет инструкции перезаписи, которые включают добавление нового заголовка, заголовка туннеля или внешнего заголовка в пакет и пересылку полученного пакета. Исходный заголовок пакета теперь называется внутренним заголовком. C добавляет внешний заголовок и обрабатывает новый пакет для пересылки.
Теперь C исследует новый пункт назначения, которым является H (помните, что исходным пунктом назначения был M). H не подключен напрямую, поэтому C необходимо выяснить, как достичь H. Это называется рекурсивным поиском, поскольку C ищет путь к промежуточному месту назначения, чтобы доставить пакет к конечному месту назначения, но не к нему.
Теперь C поместит правильную информацию в пакет в заголовок link local, чтобы перенаправить трафик на E.
Когда E получает этот пакет, он удаляет внешнюю информацию о переадресации, Заголовок link local и пересылает трафик на основе первого заголовка C, помещенного в пакет, во время первоначального поиска. Этот внешний заголовок говорит E переслать пакет в H; E не видит и не включает исходный внутренний заголовок, помещенный на пакет A.
E добавит новый Заголовок link local, чтобы пакет был правильно переадресован в H, и передаст пакет по правильному интерфейсу.
Когда H получает пакет, он удаляет Заголовок link local и обнаруживает внешний заголовок. Внешний заголовок говорит, что пакет предназначен для самого H, поэтому он очистит этот заголовок и обнаружит исходный заголовок пакета или внутренний заголовок.
Теперь H посмотрит в своей локальной таблице маршрутизации и обнаружит, что M локально подключен. H поместит правильный Заголовок link local в пакет и передаст его через правильный интерфейс, чтобы пакет достиг M.
Если C и H используют VRF, а не туннельные интерфейсы, процесс в предыдущем списке изменяется на шагах 2 и 8. На шаге 2 C будет искать M как пункт назначения в VRF, связанном каналом [A, C]. Когда C обнаруживает, что трафик к M должен пересылаться через виртуальную топологию через H, он помещает внешний заголовок в пакет и снова обрабатывает пакет на основе этого внешнего заголовка через базовый VRF или, скорее, таблицу маршрутизации, представляющую физическую топологию. Когда H получает пакет, он удаляет внешний заголовок и снова обрабатывает пакет, используя VRF, к которому подключен M, для поиска информации, необходимой для пересылки трафика в его конечный пункт назначения. В этом случае интерфейс туннеля заменяется отдельной таблицей пересылки; вместо того, чтобы обрабатывать пакет через одну и ту же таблицу дважды с использованием двух разных адресатов, пакет обрабатывается через две разные таблицы пересылки.
Термин туннель имеет много различных определений; в этих статьях туннель будет использоваться для описания виртуального канала, где внешний заголовок используется для инкапсуляции внутреннего заголовка, и:
Внутренний заголовок находится на том же уровне или более низком уровне, чем внешний заголовок (например, заголовок Ethernet, переносимый внутри заголовка IPv6; обычно IPv6 переносится внутри Ethernet).
По крайней мере, некоторые сетевые устройства на пути, будь то виртуальные или физические, пересылают пакет только на основе внешнего заголовка.
Переход от виртуальных интерфейсов к VRFs концептуально отличается достаточно, чтобы породить различные описательные термины. Underlay -это физическая (или потенциально логическая!) топология, через которую туннелируется трафик. Overlay - это набор туннелей, составляющих виртуальную топологию. В большинстве случаев термины Underlay и Overlay не используются с отдельными туннелями или в случае службы, работающей через общедоступный Интернет. Сервис, который создает виртуальную топологию через общедоступный Интернет, часто называют сервисом over-the-top.
Опять же, эти термины используются в некоторой степени взаимозаменяемо и даже очень небрежно в более широком мире сетевой инженерии. На этом фоне пора перейти к вариантам использования, чтобы узнать о наборе проблем, которые необходимо решить виртуализацией.
Предоставление услуг Ethernet по IP-сети.
Хотя приложения не должны создаваться с использованием подключения Ethernet в качестве базового, многие из них это делают. Например:
Некоторые поставщики систем хранения данных и баз данных строят свои устройства с предположением, что подключение Ethernet означает короткое расстояние и короткую задержку, или они проектируют системы поверх проприетарных транспортных протоколов непосредственно поверх кадров Ethernet, а не поверх пакетов интернет-протокола (IP).
Некоторые продукты виртуализации включают в свои продукты предположения о возможности подключения, такие как надежность кеширования Ethernet для IP-адресов для шлюза по умолчанию и других доступных мест назначения.
Для таких приложений требуется то, что выглядит как соединение Ethernet между устройствами (физическими или виртуальными), на которых работают различные узлы или копии приложения. Помимо этого, некоторые сетевые операторы считают, что запуск большого плоского домена Ethernet проще, чем запуск крупномасштабного IP-домена, поэтому они предпочли бы создавать самые большие домены Ethernet, которые они могут ("коммутация, где можно, маршрутизация, где необходимо", была распространенная поговорка в те времена, когда коммутация выполнялось аппаратно, а маршрутизация выполнялась программно, поэтому коммутация пакетов выполнялась намного быстрее, чем их маршрутизация). Некоторые кампусы также построены с основной идеей - никогда не просить устройство коммутировать свой IP-адрес после подключения. Поскольку пользователи могут быть подключены к разным сегментам Ethernet в зависимости от их домена безопасности, каждый сегмент Ethernet должен быть доступен в каждой точке беспроводного доступа и часто на каждом порте Ethernet в кампусе.
Учитывая сеть, основанную на IP, которая предполагает Ethernet как один из многих транспортных средств, поверх которых будет работать IP, как вы можете обеспечить подключение Ethernet к устройствам, связанным по IP-сети? На рисунке 3 показаны задачи, которые необходимо решить.
На рисунке 3 процесс, работающий на A с IP-адресом 2001:db8:3e8:100::1, должен иметь возможность взаимодействовать со службой, работающей на B с IP-адресом 2001:db8:3e8:100::2, как если бы они находились в одном сегменте Ethernet (две службы должны видеть друг друга в обнаружении соседей и т. д.). Чтобы сделать проблему более сложной, служба на A также должна иметь возможность перемещаться в K без изменения своего локального кэша обнаружения соседей или маршрутизатора по умолчанию. Сама сеть, является маршрутизируемой сетью, работающей под управлением IPv6.
Что необходимо для выполнения требований?
Должен быть способ передачи кадров Ethernet по IP-сети, разделяющей серверы. Обычно это будет своего рода туннельная инкапсуляция, как описано в начале этого раздела. Туннелирование позволило бы принимать кадры Ethernet на C, например, инкапсулированные в какой-то внешний заголовок, чтобы их можно было транспортировать по маршрутизируемой сети. Когда пакет, содержащий кадр Ethernet, достигает D, этот внешний заголовок может быть удален, и кадр Ethernet пересылается локально. С точки зрения D, фрейм имеет локальное происхождение.
Должен быть способ узнать о пунктах назначения, доступных через туннель, и привлечь трафик в туннель. На самом деле это две отдельные, но взаимосвязанные проблемы. Привлечение трафика в туннель может включать запуск второй плоскости управления с ее собственными VRFs или добавление дополнительной информации в существующую плоскость управления об адресах Ethernet Media Access Control (MAC), доступных на каждом пограничном маршрутизаторе.
Может потребоваться перенести маркировку качества обслуживания (QoS) из внутреннего заголовка во внешний заголовок, чтобы трафик обрабатывался правильно при его пересылке.
Виртуальный частный доступ к корпоративной сети.
Почти в каждой организации есть какие-то удаленные сотрудники, либо на полную ставку, либо просто люди, которые перемещаются, и у большинства организаций есть какие-то удаленные офисы, где часть сотрудников работает вдали от главного офиса, чтобы напрямую взаимодействовать с местным организациями в некоторых отраслях, например, с покупателями или поставщиками. Все эти люди по-прежнему нуждаются в доступе к сетевым ресурсам, таким как электронная почта, системы путешествий, файлы и т. д. Эти службы, конечно, не могут быть доступны в общедоступном Интернете, поэтому необходимо предоставить какой-то другой механизм доступа. На рисунке 4 показаны типичное проблемное пространство.
В этом варианте использования есть две основные проблемы:
Как можно защитить трафик между отдельным хостом - B - и тремя хостами в небольшом офисе - C, D и E - от перехвата и чтения злоумышленником? Как можно защитить сами адреса назначения от попадания в публичную сеть? Эти проблемы связаны с некоторой защитой, которая, в свою очередь, подразумевает некоторую форму инкапсуляции пакетов.
Как можно управлять качеством работы пользователей в этих удаленных местах для поддержки передачи голоса по IP и других приложений в реальном времени? Поскольку провайдеры в Интернете не поддерживают QoS, необходимо обеспечить другие формы гарантии качества.
Таким образом, задача, которую необходимо решить, включает еще две общие проблемы.
Должен быть способ инкапсулировать трафик, передаваемый по общедоступной сети, без раскрытия исходной информации заголовка и без подвергания информации, содержащейся в пакете, для проверки. Самым простым решением этих проблем является туннелирование (часто в зашифрованном туннеле) трафика от A и F к граничному маршрутизатору в сети организации G, где инкапсуляция может быть удалена, а пакеты перенаправлены на A.
Должен быть способ объявить достижимые пункты назначения от G к удаленным пользователям, а также существование (или достижимость) удаленных пользователей к G и сети позади G. Эта информация о достижимости должна использоваться для привлечения трафика в туннели. В этом случае плоскости управления может потребоваться перенаправить трафик между различными точками входа и выхода в общедоступную сеть и попытаться контролировать путь трафика через сеть, чтобы обеспечить удаленным пользователям хорошее качество работы.
Подведем итоги
Два варианта использования, показанные выше, актуализируют два вопроса, которые должно решить каждое решение сетевой виртуализации:
Как трафик инкапсулируется в туннель, чтобы можно было отделить пакеты и информацию плоскости управления от базовой сети?
Решением этой проблемы обычно является некоторая форма инкапсуляции, в которую помещается исходный пакет, когда он передается по сети. Основное внимание при инкапсуляции - поддержка аппаратной коммутации в базовой сети, чтобы обеспечить эффективную пересылку инкапсулированных пакетов. Второстепенным соображением является размер формата инкапсулирующего пакета; каждый октет дополнительного заголовка инкапсуляции уменьшает объем полезной нагрузки, которую туннель может нести (если нет разницы между максимальной единицей передачи или MTU в сети, предназначенной для учета дополнительной информации заголовка, налагаемой туннелированием).
Примечание
Path MTU Detection (PMTUD) часто плохо определяет MTU инкапсулированных пакетов. Из-за этого часто требуется ручная настройка MTU в точке наложения заголовка туннеля.
Как пункты назначения достигаются через туннель, объявленный через сеть?
В более общих туннельных решениях туннель становится "просто еще одним звеном" в общей топологии сети. Пункты назначения, доступные через туннель, и дополнительная виртуальная связь просто включены как часть плоскости управления, как и любые другие пункты назначения и каналы. В этих решениях существует одна таблица маршрутизации или пересылки в каждом устройстве, и рекурсивный поиск используется для обработки пакета посредством пересылки в точке, где трафик входит в туннель или головной узел туннеля. Трафик привлекается в туннель путем изменения метрик таким образом, чтобы туннель был более желательным путем через сеть для тех пунктов назначения, которые оператор сети хотел бы получить через туннель. Это обычно означает в основном ручные решения проблемы привлечения трафика в туннель, такие как установка метрики туннеля ниже пути, по которому проходит туннель, а затем фильтрация пунктов назначения, объявленных через туннель, чтобы предотвратить объявления пунктов назначения, которые должны быть недоступны через туннель. На самом деле, если пункты назначения, достижимые через туннель, включают конечную точку туннеля (хвост туннеля), может образоваться постоянная петля маршрутизации, или туннель будет циклически переключаться между правильной переадресацией трафика и не переадресацией трафика вообще.
В решениях с overlay и over-the-top развертывается отдельная плоскость управления (или передается отдельная база данных с информацией о доступности для адресатов, достижимых в underlay и overlay в единой плоскости управления). Пункты назначения, доступные через underlay и overlay, помещаются в отдельные таблицы маршрутизации (VRF) на головной станции туннеля, а таблица, используемая для пересылки трафика, основана на некоторой форме системы классификации. Например, все пакеты, полученные на конкретном интерфейсе, могут быть автоматически помещены в оверлейный туннель, или все пакеты с определенным классом обслуживания, установленным в их заголовках пакетов, или весь трафик, предназначенный для определенного набора пунктов назначения. Механизмы полного наложения и верхней виртуализации обычно не полагаются на метрики для привлечения трафика в туннель на головной станции.
Еще одно необязательное требование - обеспечить качество обслуживания либо путем копирования информации QoS из внутреннего заголовка во внешний заголовок, либо путем использования какой-либо формы проектирования трафика для передачи трафика по наилучшему доступному пути.
Первая часть тут.
Вектор пути основан на хранении списка узлов, через которые проходит путь. Любой узел, который получает обновление с самим собой в пути, просто отбрасывает обновление, поскольку это не жизнеспособный путь. Рисунок 12 используется в качестве примера. На рисунке 12 каждое устройство объявляет информацию о местах назначения каждому соседнему устройству; для пункта назначения, прикрепленного к E:
E будет анонсировать F с самим собой в источнике, поэтому с путем [E], как B, так и D.
От B: B анонсирует F к A с путем [E, B].
Из D: D анонсирует F в C с путем [E, D].
От C: C анонсирует F к A с путем [E, D, C]
Какой путь предпочтет A? В системе вектора пути может быть ряд метрик, включая длину пути, предпочтения политики и т. д. Например, предположим, что есть метрика, которая устанавливается локально на каждом узле, переносимом с каждым маршрутом. Эта локальная метрика переносится между узлами, но никак не суммируется при прохождении через сеть, и каждый узел может устанавливать эту метрику независимо от других узлов (при условии, что узел использует одну и ту же метрику по отношению к каждому соседу). Например, локальная метрика E объявляется B, который затем устанавливает свою собственную локальную метрику для этого пункта назначения и объявляет результирующий маршрут A и т. д.
Чтобы определить лучший путь, каждый узел может затем
Отбросить любое место назначения с идентификатором локального узла в пути.
Сравнить метрику, выбрав наивысшую локальную метрику из полученных.
Сравнить длину пути, выбрав самый короткий из полученных.
Объявить только тот путь, который используется для пересылки трафика.
Примечание.Не имеет значения, выбирает ли каждый узел самую высокую или самую низкую метрику. Важно только то, что каждый узел выполняет одно и то же действие во всей сети. Однако при сравнении путей узел всегда должен выбирать более короткий путь.
Если каждый узел в сети всегда будет следовать этим трем правилам, то петля не образуется.
Например:
E объявляет F в B с путем [E] и метрикой 100.
B объявляет F к A с путем [E, B] и метрикой 100.
E объявляет F в D с путем [E] и метрикой 100.
D объявляет F в C с путем [E, D] и метрикой 100.
C объявляет F в A с путем [E, D, C] и метрикой 100.
У A есть два пути, оба с одинаковой метрикой, и, следовательно, будет использовано второе правило, чтобы выбрать один путь, который является наиболее коротким. В этом случае A выберет путь через [E, B]. A будет объявлять маршрут, который он использует, к C, но если C следует тому же набору правил, у него также будет два пути с доступной метрикой 100, один с путем [E, B, A], а второй с путем [E, D, C]. В этом случае должен быть механизм разрешения конфликтов, который C использует внутри для выбора между двумя маршрутами. Неважно, что это за механизм разрешения конфликтов, если он постоянно применяется в узле. Независимо от того, какой путь выберет C, трафик к F не будет закольцован. Предположим, однако, несколько иное стечение обстоятельств:
E объявляет F в B с путем [E] и метрикой 100.
B объявляет F к A с путем [E, B] и метрикой 100.
E объявляет F в D с путем [E] и метрикой 50.
D объявляет F в C с путем [E, D] и метрикой 50.
C объявляет F в A с путем [E, D, C] и метрикой 50.
У A есть два пути: один с метрикой 100, а другой с метрикой 50.
Следовательно:
A выберет более высокую из двух метрик, путь через [E, B], и объявит этот маршрут C
C выберет более высокую из двух метрик, путь через [E, B, A], и объявит этот маршрут D.
D выберет более высокий из двух метрик, путь через [E, B, A, C], и объявит этот маршрут E.
E отбросит этот маршрут, поскольку E уже находится на пути.
Следовательно, даже если метрика перекрывает длину пути в (почти) каждом узле, цикл не образуется.
Проблемы метрик
Каждый алгоритм, обсуждавшийся до этого момента, использовал одну метрику для вычисления путей без петель, за исключением вектора пути, а вектор пути использует две метрики очень ограниченным образом, причем одна всегда предпочтительнее другой. Путь, по сути, можно рассматривать как «фактор разрешения конфликтов», который вступает в игру только тогда, когда основная метрика, которая никак не связана с путем (поскольку она не суммируется шаг за шагом в сети), не соответствует предотвратить петлю. Некоторые протоколы могут использовать несколько метрик, но они всегда будут каким-то образом комбинировать эти метрики, поэтому для поиска путей без петель используется только одна комбинированная метрика. Почему?
С математической точки зрения, все методы, используемые для нахождения набора свободных от петель (или кратчайших) путей через сеть, разрешимы за полиномиальное или неэкспоненциальное время - или, скорее, они считаются проблемами класса P. Существует более широкий класс задач, содержащих P, который содержит любую задачу, решаемую с помощью (теоретической) недетерминированной машины Тьюринга. Среди NP-проблем есть набор задач, которые считаются NP-полными, что означает, что не существует известного эффективного способа решения проблемы. Другими словами, для решения проблемы необходимо перечислить все возможные комбинации и выбрать из этого набора наилучшее возможное решение.
Проблема с множественными метриками классифицируется как NP-complete, и, следовательно, хотя и разрешима, она никоим образом не решаема, что позволяет использовать ее в коммуникационных сетях, близких к реальному времени.
Алгоритмы непересекающихся путей
Рассмотрим ситуацию медицинской операции, выполняемой роботом, который следует за руками живого хирурга на другом конце света. Возможно, что для того, чтобы такая система работала, требуется, чтобы пакеты доставлялись от датчиков на руках хирурга к роботу в реальном времени, по порядку, с минимальным значением параметра jitter или без него, и никакие пакеты нельзя отбрасывать. Это один из примеров. Конечно, он может быть расширен для других различных ситуаций, включая финансовые системы и другие механические системы управления, где требуется доставка пакетов в реальном времени без сбоев.
В таких ситуациях часто требуется передать две копии каждого пакета, а затем позволить получателю выбрать пакет, наилучшим образом соответствующий характеристикам качества обслуживания (QoS) и потерям пакетов, необходимым для поддержки приложения. Однако все системы, рассмотренные до сих пор, могут найти только один путь без циклов и потенциально альтернативный путь (LFA и / или rLFA). Таким образом, с помощью алгоритмов непересекающихся путей решается следующая проблема:
Как можно построить пути в сети таким образом, чтобы они использовали наименьшее количество перекрывающихся ресурсов (устройств и каналов), насколько это возможно (следовательно, максимально непересекающиеся или максимально избыточные)?
В этой части лекций мы начнем с описания концепции двухсвязной сети, а затем рассмотрим два разных (но, казалось бы, связанных) способа вычисления непересекающихся топологий в двухсвязных сетях.
Двухсвязные сети
Двусвязная сеть - это любая сеть, в которой есть как минимум два пути между источником и местом назначения, которые не используют одни и те же устройства (узлы) или каналы (ребра). Обратите внимание на:
Сеть является двусвязной по отношению к определенному набору источников и пунктов назначения; большинство сетей не имеют двух соединений для каждого источника и каждого пункта назначения.
Небольшие блоки любой данной сети могут быть подключены двумя соединениями для некоторых источников и пунктов назначения, и эти блоки могут быть соединены между собой узкими одно- или двумя соединенными точками подключения.
Часто проще всего понять двусвязность на реальном примере. На рисунке 13 показана сеть, с выделенными блоками.
В блоке A есть как минимум два разных непересекающихся пути между X и F:
[X, A, B, E, F] и [X, C, F]
[X, A, B, F] и [X, C, F]
В блоке B есть одна пара непересекающихся путей из G в L: [G, K, L] и [G, H, L]. Непересекающихся путей к Z нет, так как этот узел односвязен. Между F и G также нет непересекающихся путей, так как они односвязны. Канал [F, G] можно рассматривать как узкую точку между этими двумя блоками топологии. В сети, показанной на рисунке 13, невозможно вычислить два непересекающихся пути между X и Z.
Алгоритм непересекающегося пути Суурбалле
В 1974 году Дж. Суурбалле опубликовал статью, описывающую, как использовать несколько запусков SPF-алгоритма Дейкстры для поиска нескольких непересекающихся топологий в сети. Алгоритм по существу вычисляет SPF один раз, удаляет подмножество линий, используемых в SPT, а затем вычисляет второй SPF по оставшимся линиям. Алгоритм Суурбалле труднее объяснить, чем проиллюстрировать на примере, поскольку он опирается на направленный характер связей, вычисляемых с помощью SPT. В качестве примеров используются рисунки 14-18.
На рисунке 14 показано состояние операций после завершения первого запуска SPF и вычисления начального SPT. Обратите внимание на стрелки направления на линиях. Не принято думать, что SPT является направленным, но на самом деле это так, когда каждая линия ориентирована в сторону от источника или корня дерева. Когда F вычисляет дерево обратно к X, оно также создает направленное дерево со стрелками, указывающими в противоположном направлении.
Ребра (или связи) на SPT называются ребрами дерева, а ребра (или связи), не входящие в результирующий SPT, называются ребрами не деревьев. На рис. 14 края дерева отмечены сплошным черным цветом со стрелками направления, а ребра не деревьев - более светлыми серыми пунктирными линиями.
Второй шаг показан на рисунке 15.
На рисунке 15 показано каждое звено с измененными затратами; каждая линия, которая была частью исходного SPT (каждое ребро дерева, показано сплошной линией), имеет две стоимости, по одной в каждом направлении, в то время как линии, которые изначально не были частью SPT (ребра, не входящие в состав дерева, показаны пунктирными линиями), имеют свои исходные расходы. Обратите внимание на стрелки, показывающие направление стоимости в каждом случае; это будет важно на следующем этапе расчета. Для расчета стоимости двух направленных линий для каждого ребра дерева:
Именуем один конец линии символом u, а другой конец линии символом v. Обратите внимание, что уравнение выполняется в обоих направлениях.
Вычтем стоимость источника до v из стоимости линии от u до v.
Добавим стоимость из источника к u.
Если источник s: d[sp](u,v) = d(u,v) ? d(s,v) + d(s,u)
По сути, это устанавливает стоимость ребер дерева равной 0, как можно увидеть, выполнив математические вычисления для ссылки [B, E]:
B - есть u, E - есть v, A - есть s
d(u,v) = 2, d(s,v) = 3, d(s,u) = 1
2 ? 3 + 1 = 0
Однако для всех ребер, не входящих в дерево, будет установлена некоторая (обычно большая) ненулевая стоимость. Для сети на рисунке 15:
Для линии [B, A] (примечание [A, B] не является линией в вычисляемом дереве направлений):
B - есть u, A - есть v, A - есть s
d(u,v) = 0, d(s,v) = 0, d(s,u) = 1
0 ? 0 + 1 = 1
Для линии [E,B]:
E – есть u, B – есть v, A - есть s
d(u,v) = 2, d(s,v) = 1, d(s,u) = 3
2 ? 1 + 3 = 4
Для линии [C,A]:
C – есть u, A – есть v, A – есть s
d(u,v) = 2, d(s,v) = 0, d(s,u) = 2
2 ? 0 + 2 = 4
Для линии [F,D]:
F – есть u, D – есть v, A – есть s
d(u,v) = 1, d(s,v) = 4, d(s,u) = 5
1 ? 4 + 5 = 2
Для линии [D,B]:
D – есть u, B – есть v, A – есть s
d(u,v) = 1, d(s,v) = 1, d(s,u) = 2
1 ? 1 + 2 = 2
Следующий шаг, показанный на рисунке 16, состоит в том, чтобы удалить все направленные ребра, указывающие на источник, который лежит вдоль исходного SPT к определенному месту назначения (в данном случае Z), изменить направление ребер с нулевой стоимостью (линий) вдоль этого же пути, а затем снова запустить SPF Дейкстры, создав второй SPT на той же топологии.
Возвращаясь к исходному SPT, путь от X до Z проходил по пути [A,B,D,F]. Таким образом, четыре ненулевых ребра (пунктирные линии), указывающие назад к источнику, А, вдоль этого пути были удалены. Вдоль того же пути [A, B,D,F] направление каждого ребра было изменено. Например, [A,B] первоначально указывало от A к B, а теперь указывает от B к A. Следующий шаг-запустить SPF по этому графику, помня, что трафик не может течь против направления линии. Полученное дерево показано на рисунке 17.
На рисунке 17 показано исходное дерево и вновь вычисленное дерево, наложенные на исходную топологию в виде двух различных пунктирных линий. Эти две топологии все еще имеют общую связь [B,D], так что они еще не совсем разобщены. В этой точке есть два кратчайших пути от X до Z:
[A,B,D,F]
[A,C,D,B,E,F]
Эти два графа объединяются, образуя набор ребер, и любые связи, которые включены в оба графа, но в противоположных направлениях, отбрасываются; комбинированный набор выглядит так: [A->B, B->E, E->F, A->C, C->D, D->F]
Обратите внимание на направленность каждой линии связи еще раз - очень важно отсечь перекрывающуюся линию, которая будет указана как [B-> D] и [D-> B]. С помощью этого подмножества возможных ребер на графе можно увидеть правильный набор кратчайших путей: [A, B, E, F] и [A, C, D, F].
Алгоритм Суурбалле сложен, но показывает основные моменты вычисления непересекающихся деревьев, в том числе то, насколько сложно их вычислить.
Максимально избыточные деревья
Более простой альтернативой алгоритму Суурбалла для вычисления непересекающихся деревьев является вычисление максимально избыточных деревьев (Maximally Redundant Trees-MRT). Чтобы лучше понять MRT - это изучить Depth First Search (DFS), особенно нумерованный DFS. Рисунок 18 используется в качестве иллюстрации.
На рисунке 18 левая сторона представляет простую топологию. Правая-ту же топологию, которая была пронумерована с помощью DFS. Предполагая, что алгоритм DFS, используемый для «обхода» дерева, всегда выбирает левый узел над правым, процесс будет выглядеть примерно так:
01 main {
02 dfs_number = 1
03 root.number = dfs_number
04 recurse_dfs(root)
05 }
06 recurse_dfs(current) {
07 for each neighbor of current {
08 child = left most neighbor (not visited)
09 if child.number == 0 {
10 dfs_number++
11 child.number = dfs_number
12 if child.children > 0 {
13 recurse_dfs(child)
14 }
15 }
16 }
17 }
Лучший способ понять этот код-пройти рекурсию несколько раз, чтобы увидеть, как она работает. Используя рисунок 18:
При первом вызове recurse_dfs в качестве текущего узла устанавливается A или root.
Оказавшись внутри recurse_dfs, выбирается крайний левый узел A или B.
B не имеет номера при входе в цикл, поэтому оператор if в строке 09 верен.
B назначается следующий номер DFS (строка 11).
У B есть дочерние элементы (строка 12), поэтому recurse_dfs вызывается снова с B в качестве текущего узла.
Оказавшись внутри (второго уровня) recurse_dfs, выбирается крайний левый сосед B, которым является E.
E не имеет номера DFS, поэтому оператор if в строке 09 верен.
E назначается следующий номер DFS (3)
E не имеет дочерних элементов, поэтому обработка возвращается к началу цикла.
F теперь является крайним левым соседом B, который не был посещен, поэтому он назначен дочернему элементу.
F не имеет числа, поэтому оператор if в строке 09 верен.
F назначается следующий номер DFS (4).
У B больше нет дочерних элементов, поэтому цикл for в строке 07 завершается ошибкой, и программа recurse_dfs завершается.
Однако на самом деле recurse_dfs не выходит - он просто «возвращается» к предыдущему уровню рекурсии, то есть к строке 14. Этот уровень рекурсии все еще обрабатывает соседей A.
C - следующий сосед A, который не был затронут, поэтому дочерний элемент установлен в C.
И так далее
Изучение номеров узлов в правой части рисунка 18 приводит к следующим интересным наблюдениям:
Если A всегда следует за возрастающим числом, чтобы достичь D,оно будет следовать по пути [A, C,G,D].
Если D всегда следует за уменьшающимся числом DFS, чтобы достичь A,он будет следовать по пути [D, A].
Эти два пути на самом деле не пересекаются.
Это свойство сохраняется для всех топологий, которым были присвоены номера в результате поиска DFS: путь, следующий за постоянно увеличивающимися числами, всегда будет не пересекаться с путем, который всегда следует за убывающими числами. Это именно то свойство, на котором MRT строят непересекающиеся пути. Однако проблема с нумерацией DFS заключается в том, что это трудно сделать почти в реальном времени. Должен быть какой-то избранный корень, трафик на локальном уровне неоптимален (во многом как Minimum Spanning Tree или MST), и любые изменения в топологии требуют перестройки всей схемы нумерации DFS. Чтобы обойти эти проблемы, MRT строит непересекающиеся топологии, используя тот же принцип, но другим способом. Рисунок 19 используется для пояснения.
Первым шагом в построении MRT является поиск короткого цикла в топологии от корня (обычно эти петли обнаруживаются с помощью алгоритма SPF Дейкстры). В этом случае в качестве корня будет выбран A, а цикл будет [A, B, C, D]. Этот первый цикл будет использоваться как первая из двух топологий, скажем, красная топология. Обращение цикла к [A, D, C, B] создает непересекающуюся топологию, скажем, синюю топологию. Эта первая пара топологий через этот короткий цикл называется «ухом».
Для расширения диапазона МРТ к первому добавляется второе ухо. Для этого открывается второй цикл, на этот раз через [A, D, F, E, B], а непересекающаяся топология - [A, B, E, F, D]. Возникает вопрос: какое из этих двух расширений топологии следует добавить к красной топологии, а какое - к синей? Здесь вступает в игру форма нумерации DFS.
Каждому устройству в сети уже должен быть назначен идентификатор либо администратором, либо через какой-либо другой механизм. Эти идентификаторы должны быть уникальными для каждого устройства. В схеме нумерации DFS также существует концепция нижней точки, которая указывает, где на конкретном дереве прикрепляется этот узел, а также какие узлы присоединяются к дереву через этот узел.
Учитывая эти уникальные идентификаторы и возможность вычислять нижнюю точку, каждый узел в сети может быть упорядочен так же, как ему был присвоен номер в процессе нумерации DFS. Ключ в том, чтобы знать, как порядок соответствует существующей красной и синей топологиям. Предположим, что нижняя точка B выше, чем C, если топология [A, B, C, D] является частью красной топологии. Для любого другого «уха» или петли в топологии, которая проходит через B и C, направление «уха», в котором B меньше C, должно быть помещено в красную топологию. Петля в обратном направлении должна быть размещена на синей топологии. Это объяснение является довольно поверхностным, но оно дает вам представление о том, как MRT образуют непересекающиеся топологии.
Двусторонняя связь
В этой и предыдущей лекциях было описано несколько различных способов вычисления пути без петель (или набора непересекающихся путей) через сеть. В каждом из этих случаев вычисленный путь является однонаправленным - от корня дерева до краев или достижимых мест назначения. Фактически, обратного пути не существует. Другими словами, источник может иметь возможность достичь пункта назначения по пути без петель, но может не быть обратного пути от пункта назначения к источнику. Это может быть необычный режим отказа в некоторых типах каналов, результат фильтрации информации о доступности или ряд других ситуаций в сети.
Примечание. Двусторонняя связь не всегда нужна. Рассмотрим, например, случай с подводной лодкой, которая должна получать информацию о своей текущей задаче, но не может передавать какую-либо информацию, не раскрывая своего текущего местоположения. Желательна возможность отправлять пакеты устройствам, расположенным на подводной лодке, даже если к ним нет двусторонней связи. Плоскости управления должны быть модифицированы или специально спроектированы для обработки такого необычного случая, поскольку обычно для правильной работы сети требуется двустороннее соединение.
Еще одна проблема, с которой должны столкнуться плоскости управления в области вычислительных трактов, - это обеспечение сквозной двусторонней связи.
Уровень управления может решить эту проблему несколькими способами:
Некоторые плоскости управления просто игнорируют эту проблему, что означает, что они предполагают, что какой-то другой протокол, например транспортный протокол, обнаружит это состояние.
Плоскость управления может проверить наличие этой проблемы во время расчета маршрута. Например, при вычислении маршрутов с использованием алгоритма Дейкстры можно выполнить проверку обратной связи при вычислении путей без петель. Выполнение этой проверки обратной линии связи на каждом этапе вычислений может гарантировать наличие двусторонней связи.
Плоскость управления может предполагать двустороннюю связь между соседями, обеспечивая сквозную двустороннюю связь. Плоскости управления, которые выполняют явные проверки двусторонней связи для каждого соседа, могут (как правило) безопасно предполагать, что любой путь через этих соседей также поддерживает двустороннюю связь.
В некоторых компаниях существует сменный график работы операторов. Как правило, в этом случае, они делят между собой рабочее место. То есть, когда приходит один оператор, то он вводит на общей рабочей станции свои учётные данные и работает под своей учётной записью, а когда приходит другой оператор - то делает то же самое, но под собственной учётной записью. Таким образом, компания экономит на необходимости организации отдельного рабочего места под каждого сотрудника.
Кстати, с IP-телефоном можно провести точно такой же трюк и для этого существует специальное понятие - Hot Desking. Как это сделать на IP-АТС Asterisk с помощью графической оболочки FreePBX, мы сейчас расскажем в этой статье.
Итак, для того чтобы настроить эту фичу, нам сначала нужно разделить привычный нам модуль Extensions на два отдельных модуля Devices и Users. Для этого открываем Advanced Settings, ищем опцию User & Devices Mode и меняем её значение на deviceanduser вместо extensions. Не забываем нажать Submit и Apply Config
Отлично! Теперь, если мы посмотрим в раздел Applications, то увидим там два новых модуля - Devices и чуть пониже - Users:
Рассмотрим модуль Devices. Данный модуль теперь управляет сущностями устройств, то есть – телефонов, софтфонов и других клиентов. Как видите, здесь уже находятся внутренние номера, которые были созданы ещё в модуле Extensions:
Однако теперь, доступный для настройки функционал немного изменился:
По умолчанию, на данном устройстве есть жёстко привязанный пользователь (в данном случае - 175. Мы рассмотрим его настройки в модуле Users). В такой конфигурации на данное устройство нельзя залогиниться с учётными данными другого пользователя. Чтобы это изменить, нужно поменять значение опции Device Type с Fixed на Adhoc. Дефолтного пользователя, который будет по умолчанию залогинен на данном устройстве, можно оставить без изменения, а можно поставить:
Теперь нужно сделать настройки для пользователей, которые будут логиниться на данное устройство в модуле Users. Как видите, пользователи также остались от тех, которые были созданы при модуле Extensions:
Для начала сделаем настройки для дефолтного пользователя на устройстве - 175. Самое главное здесь – это задать пароль (а точнее даже PIN) пользователя, чтобы функционал аутентификации заработал на устройстве. Пользователь вручную будет вводить этот пароль на устройстве, поэтому в качестве пароля можно указать только цифры:
Один настроенный пользователь нам ничего не даст, чтобы организовать сменную работу на устройстве, нам нужно их как минимум два. Для этого, в модуле Users, создадим ещё одного пользователя, который не будет привязан ни к какому устройству и зададим для него PIN код:
Супер, переходим к самому интересному. У нас есть софтфон DrayTek, который выступает в роли устройства с номером 175. По умолчанию, на нём сидит пользователь Алексей Добронравов с внутренним номером 175. Но сегодня в смену вступает созданный ранее пользователь - Крипто Виталий с внутренним номером 199.
Чтобы залогиниться на устройстве, Крипто Виталию нужно:
Набрать Feature Code - *11;
Он услышит в трубке предложение набрать свой внутренний номер (199) и нажать #;
Если такой внутренний номер существует, то ему будет предложено ввести пароль (PIN код) и нажать #;
Если пароль будет введён верно, то пользователя поблагодарят и сообщат, что оператор зарегистрирован.
Для того, чтобы удалить регистрацию, используйте фича код - *12
Сногсшибательно! Теперь на нашем устройстве (софтфоне) зарегистрирован другой пользователь (Крипто Виталий) и он может совершать звонки! Давайте проверим это, позвонив на другой внутренний номер, например - 188, на котором у нас зарегистрирован стационарный телефон:
Profit! Попробуйте реализовать этот функционал у себя и сократите затраты на организацию дополнительных мест!