По вашему запросу ничего не найдено :(
Убедитесь, что запрос написан правильно, или посмотрите другие
наши статьи:
Возможно, вы уже слышали о термине "wirespeed" раньше. Это то, что отдел маркетинга любит использовать, когда речь заходит о продаже сетевого оборудования. Это означает, что пакеты могут быть переданы без какой-либо заметной задержки. Кстати, для остальной части этой статьи слова "многоуровневый коммутатор" и "маршрутизатор" - это одно и то же. Все, что я объясняю о многоуровневых коммутаторах отныне, также относится и к маршрутизаторам. Давайте посмотрим на разницу между коммутаторами 2уровня и многоуровневыми коммутаторами с точки зрения коммутации:
Вы знаете, что коммутаторы 2 уровня будут переключать только кадры Ethernet в пределах VLAN, и, если мы хотим, мы можем фильтровать трафик на основе уровня 2 (например, с защитой портов). Многоуровневый коммутатор может делать то же самое, но он также способен маршрутизировать между VLAN и фильтровать на уровне 3 или 4 с помощью списков доступа.
Переадресация на уровне 2 основана на конечном MAC-адресе. Наш коммутатор изучает исходные MAC-адреса на входящих кадрах и строит таблицу MAC-адресов. Всякий раз, когда фрейм Ethernet входит в один из наших интерфейсов, мы проверяем таблицу MAC-адресов, чтобы найти конечный MAC-адрес, и отправляем его в правильный интерфейс.
Переадресация на уровне 3 основана на IP-адресе назначения. Переадресация происходит, когда коммутатор получает IP-пакет, где исходный IP-адрес находится в другой подсети, чем конечный IP-адрес.
Когда наш многоуровневый коммутатор получает IP пакет со своим собственным MAC адресом в качестве назначения в заголовке Ethernet есть две возможности:
Если конечный IP-адрес является адресом, настроенным многоуровневом коммутаторе, то IP-пакет был предназначен для этого коммутатора.
Если конечный IP-адрес - это адрес, который не настроен на многоуровневом коммутаторе, то мы должны действовать как шлюз и "маршрутизировать" пакет. Это означает, что нам придется сделать поиск в таблице маршрутизации, чтобы проверить наличие самого полного совпадения. Кроме того, мы должны проверить, разрешен ли IP-пакет, если вы настроили ACL.
В те не далекие времена коммутация производилась на аппаратной скорости, а маршрутизация-на программной. В настоящее время как коммутация, так и маршрутизация выполняются на аппаратной скорости. В оставшейся части этой статьи вы узнаете почему.
Давайте рассмотрим разницу между обработкой кадров Ethernet и IP-пакетов:
Жизнь коммутатора уровня 2 проста
Коммутатор проверит контрольную сумму кадра Ethernet, чтобы убедиться, что он не поврежден или не изменен.
Коммутатор получает кадр Ethernet и добавляет исходный MAC-адрес в таблицу MAC-адресов.
Коммутатор направляет кадр Ethernet к правильному интерфейсу, если он знает конечный MAC-адрес. Если нет,то он будет отброшен (помечен как flood).
Там нет никакого изменения кадра Ethernet!
Теперь давайте посмотрим, что происходит, когда получает IP-пакет многоуровневый коммутатор:
В приведенном выше примере компьютер А посылает IP-пакет к компьютеру В. Обратите внимание, что они находятся в разных подсетях, поэтому нам придется его маршрутизировать. Когда наш многоуровневый коммутатор получит IP-пакет, вот что произойдет:
Коммутатор проверит контрольную сумму кадра Ethernet, чтобы убедиться, что он не поврежден или не изменен.
Коммутатор проверит контрольную сумму IP-пакета, чтобы убедиться, что он не поврежден или не изменен.
Многоуровневый коммутатор проверит таблицу маршрутизации, заметит, что 192.168.20 /24 напрямую подключен, и произойдет следующее:
Проверит таблицу ARP, чтобы увидеть, есть ли сопоставление уровня 2-3 для компьютера B. Если нет сопоставления, многоуровневый коммутатор отправит запрос ARP.
Конечный MAC-адрес изменится с FFF (многоуровневый коммутатор Fa0 / 1) на BBB (компьютер B).
Исходный MAC-адрес изменится с AAA (компьютер A) на GGG (многоуровневый коммутатор Fa0/2).
Поле TTL (time to live) в IP-пакете уменьшится на 1, и из-за этого контрольная сумма IP-заголовка будет пересчитана.
Контрольная сумма фрейма Ethernet должна быть пересчитана заново.
Фрейм Ethernet, несущий IP-пакет, будет отправлен из интерфейса к компьютеру B.
Как вы можете видеть, имеется довольно много шагов, связанных с маршрутизацией IP-пакетов.
Когда мы рассматриваем многоуровневый коммутатор возникает "разделение обязанностей". Мы должны построить таблицу для MAC-адресов, заполнить таблицу маршрутизации, ARP-запросы, проверить, соответствует ли IP-пакет списку доступа и т. д. И нам нужно переслать наши IP-пакеты. Эти задачи разделены между "плоскостью управления" и "плоскостью данных". Ниже приведен пример:
Плоскость управления отвечает за обмен информацией о маршрутизации с использованием протоколов маршрутизации, построение таблицы маршрутизации и таблицы ARP. Плоскость данных отвечает за фактическую пересылку IP-пакетов. Таблица маршрутизации не очень подходит для быстрой переадресации, потому что мы имеем дело с рекурсивной маршрутизацией.
Что такое рекурсивная маршрутизация?
Давайте рассмотрим пример:
В приведенном выше примере у нас есть три маршрутизатора. У R3 есть loopback интерфейс, к которому мы хотим получить доступ из R1. Будем использовать статические маршруты для достижения поставленной цели:
R1(config)#ip route 3.3.3.0 255.255.255.0 192.168.23.3
R1(config)#ip route 192.168.23.0 255.255.255.0 192.168.12.2
Первый статический маршрут предназначен для достижения интерфейса loopback0 R3 и указывает на интерфейс FastEthernet0/0 R3. Второй статический маршрут необходим для достижения сети 192.168.23.0/24.
Всякий раз, когда R1 хочет достичь 3.3.3.0/ 24, мы должны выполнить 3 поиска:
Первый поиск должен проверить запись для 3.3.3.0/24. Он должен быть там и должен быть IP-адрес следующего прыжка-192.168.23.3
Второй поиск относится к 192.168.23.3. Есть запись, и IP-адрес следующего прыжка - 192.168.12.2.
Третий и последний поиск относится к 192.168.12.2. Там имеется вход, и он напрямую подключен.
R1 должен проверить таблицу маршрутизации 3 раза, прежде чем он будет знать, куда отправлять свой трафик. Звучит не очень эффективно, верно? Выполнение нескольких поисков для достижения определенной сети называется рекурсивной маршрутизацией.
Большую часть времени все входящие и исходящие IP-пакеты будут обрабатываться и пересылаться плоскостью данных, но есть некоторые исключения, давайте сначала рассмотрим картинку ниже:
Большая часть IP-пакетов может быть передана плоскостью данных. Однако есть некоторые "специальные" IP-пакеты, которые не могут быть переданы плоскостью данных немедленно, и они отправляются на плоскость управления, вот некоторые примеры:
IP-пакеты, предназначенные для одного из IP-адресов многоуровневый коммутатора.
Трафик протокола маршрутизации, такой как OSPF, EIGRP или BGP.
IP-пакеты, которые имеют некоторые параметры, заданные в IP-заголовке.
IP-пакеты с истекшим сроком действия TTL
Плоскость управления может пересылать исходящие IP-пакеты на плоскость данных или использовать свой собственный механизм пересылки для определения исходящего интерфейса и следующего IP-адреса прыжка. Примером этого является маршрутизация на основе локальной политики.
Наш многоуровневый коммутатор выполняет больше шагов для пересылки пакетов, чем коммутаторы уровня 2, поэтому теоретически он должен работать медленнее, верно?
Одна из причин, по которой многоуровневые коммутаторы могут передавать кадры и пакеты на wirespeed, заключается в том, что в плате данных используется специальное оборудование, называемое ASICs.
Такая информация, как MAC-адреса, таблица маршрутизации или списки доступа, хранится в этих ASIC. Таблицы хранятся в content-addressable memory (Cam) и ternary content addressable memory (TCAM).
Таблица CAM используется для хранения информации уровня 2, например:
Исходный MAC-адрес.
Интерфейс, на котором мы узнали MAC-адрес.
К какой VLAN относится MAC-адрес.
Поиск таблицы происходит быстро! Всякий раз, когда коммутатор получает кадр Ethernet, он будет использовать алгоритм хэширования для создания "ключа" для целевого MAC-адреса + VLAN, и он будет сравнивать этот хэш с уже хэшированной информацией в таблице CAM. Таким образом, он может быстро искать информацию в таблице CAM.
Таблица TCAM используется для хранения информации "более высокого уровня", например:
Списки доступа.
Информацию о качестве обслуживания.
Таблицу маршрутизации.
Таблица TCAM может соответствовать 3 различным значениям:
0 = не просматривать.
1 = сравнивать
X = любое приемлемое значение.
Полезно для поиска, когда нам не нужно точное совпадение. (таблица маршрутизации или ACL, например).
Поскольку существует 3 значения, мы называем его троичным. Так почему же существует 2 типа таблиц?
Когда мы ищем MAC-адрес, нам всегда требуется точное совпадение. Нам нужен точный MAC-адрес, если мы хотим переслать кадр Ethernet. Таблица MAC-адресов хранится в таблице CAM.
Всякий раз, когда нам нужно сопоставить IP-пакет с таблицей маршрутизации или списком доступа, нам не всегда нужно точное соответствие. Например, IP-пакет с адресом назначения 192.168.20.44 будет соответствовать:
192.168.20.44 /32
192.168.20.0 /24
192.168.0.0 /16
По этой причине такая информация, как таблица маршрутизации, хранится в таблице TCAM. Мы можем решить, должны ли совпадать все или некоторые биты.
Пример таблицы TCAM
Если мы хотим сопоставить IP-адрес 192.168.10.22, многоуровневый коммутатор сначала посмотрит, есть ли "самое полное совпадение". Там ничего нет, что соответствовало бы полностью 192.168.10.22/32, поэтому мы продолжим сравнение на не полное соответствие. В этом случае есть запись, которая соответствует 192.168.10.0/24. Приведенный выше пример относится к поиску таблиц маршрутизации, спискам доступа, а также к качеству обслуживания, спискам доступа VLAN и многим другим.
Теперь вы знаете все шаги, которые должен выполнять многоуровневый коммутатор, когда он должен пересылать IP-пакеты, плоскость управления/данных и, что мы используем разные таблицы, хранящиеся в специальном оборудовании, называемом ASIC. Давайте подробнее рассмотрим фактическую "пересылку" IP-пакетов.
Существуют различные методы коммутации для пересылки IP-пакетов. Вот различные варианты коммутации:
Процессорная коммутация:
Все пакеты проверяются процессором, и все решения о пересылке принимаются в программном обеспечении...очень медленно!
Быстрая коммутация (также известное как кеширование маршрутов):
Первый пакет в потоке проверяется процессором; решение о пересылке кэшируется аппаратно для следующих пакетов в том же потоке. Это более быстрый метод.
(CEF) Cisco Express Forwarding (также известный как переключение на основе топологии):
Таблица пересылки, созданная в аппаратном обеспечении заранее. Все пакеты будут коммутироваться с использованием оборудования. Это самый быстрый метод, но есть некоторые ограничения. Многоуровневые коммутаторы и маршрутизаторы используют CEF.
При использовании процессорной коммутации маршрутизатор удалит заголовок каждого кадра Ethernet, ищет IP-адрес назначения в таблице маршрутизации для каждого IP-пакета, а затем пересылает кадр Ethernet с переписанными MAC-адресами и CRC на исходящий интерфейс. Все делается в программном обеспечении, так что это очень трудоемкий процесс.
Быстрая коммутация более эффективна, потому что она будет искать первый IP-пакет, но будет хранить решение о переадресации в кэше быстрой коммутации. Когда маршрутизаторы получают кадры Ethernet, несущие IP-пакеты в том же потоке, он может использовать информацию в кэше, чтобы переслать их к правильному исходящему интерфейсу.
По умолчанию для маршрутизаторов используется CEF (Cisco Express Forwarding):
Первая часть тут.
Вектор пути основан на хранении списка узлов, через которые проходит путь. Любой узел, который получает обновление с самим собой в пути, просто отбрасывает обновление, поскольку это не жизнеспособный путь. Рисунок 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 образуют непересекающиеся топологии.
Двусторонняя связь
В этой и предыдущей лекциях было описано несколько различных способов вычисления пути без петель (или набора непересекающихся путей) через сеть. В каждом из этих случаев вычисленный путь является однонаправленным - от корня дерева до краев или достижимых мест назначения. Фактически, обратного пути не существует. Другими словами, источник может иметь возможность достичь пункта назначения по пути без петель, но может не быть обратного пути от пункта назначения к источнику. Это может быть необычный режим отказа в некоторых типах каналов, результат фильтрации информации о доступности или ряд других ситуаций в сети.
Примечание. Двусторонняя связь не всегда нужна. Рассмотрим, например, случай с подводной лодкой, которая должна получать информацию о своей текущей задаче, но не может передавать какую-либо информацию, не раскрывая своего текущего местоположения. Желательна возможность отправлять пакеты устройствам, расположенным на подводной лодке, даже если к ним нет двусторонней связи. Плоскости управления должны быть модифицированы или специально спроектированы для обработки такого необычного случая, поскольку обычно для правильной работы сети требуется двустороннее соединение.
Еще одна проблема, с которой должны столкнуться плоскости управления в области вычислительных трактов, - это обеспечение сквозной двусторонней связи.
Уровень управления может решить эту проблему несколькими способами:
Некоторые плоскости управления просто игнорируют эту проблему, что означает, что они предполагают, что какой-то другой протокол, например транспортный протокол, обнаружит это состояние.
Плоскость управления может проверить наличие этой проблемы во время расчета маршрута. Например, при вычислении маршрутов с использованием алгоритма Дейкстры можно выполнить проверку обратной связи при вычислении путей без петель. Выполнение этой проверки обратной линии связи на каждом этапе вычислений может гарантировать наличие двусторонней связи.
Плоскость управления может предполагать двустороннюю связь между соседями, обеспечивая сквозную двустороннюю связь. Плоскости управления, которые выполняют явные проверки двусторонней связи для каждого соседа, могут (как правило) безопасно предполагать, что любой путь через этих соседей также поддерживает двустороннюю связь.
В этой статье мы расскажем как интегрировать Python c Excel и Word, чтобы без проблем создавать автоматические отчеты. Microsoft Excel и Microsoft Word – это, без доли сомнений, две наиболее широко используемые программы как в мире бизнеса, так и в некорпоративной сфере. Они практически являются синонимами слову «работа». Как правило, не проходит и недели, чтобы мы тем или иным способом не воспользовались их преимуществами. И хотя для обычных повседневных задач автоматизация не требуется, бывают случаи, когда она может стать необходимостью. А именно, когда у вас есть множество диаграмм, рисунков, таблиц и отчетов, которые необходимо сделать, это может стать очень утомительным занятием, если все это выполнять вручную. А это не должно быть так. На самом деле существует способ создать конвейер в Python, где можно будет легко интегрировать эти программы для создания электронных таблиц в Excel, а затем передавать результаты в Word для создания отчета практически мгновенно.
Openpyxl
Познакомьтесь с Openpyxl, возможно, одной из самых универсальных привязок в Python, которая превращает взаимодействие с Excel буквально в прогулку по парку. Используя этот пакет, вы сможете читать и записывать все новые и старые форматы Excel, то есть .xlsx и .xls. Openpyxl позволяет заполнять строки и столбцы, выполнять формулы, создавать 2D- и 3D-диаграммы, маркировать оси и заголовки, а также имеет множество других возможностей, которые могут пригодиться. Однако здесь наиболее важно то, что этот пакет позволяет вам перебирать бесконечное количество строк и столбцов Excel, тем самым избавляя вас от всех этих утомительных вычислений и построения графиков, которые вам приходилось делать ранее самим.
Python-docx
А затем появляется Python-docx – пакет для Word – то же, что Openpyxl для Excel. Если вы все еще не изучили их документацию, то вам все же стоит на нее взглянуть. Python-docx – без преувеличения один из самых простых и понятных наборов инструментов, с которыми я работал с тех пор, как начал работать с Python. Он позволяет автоматизировать создание документов, автоматически вставляя текст, заполняя таблицы и отображая изображения в отчете без каких-либо усилий.
Без лишних церемоний давайте создадим наш собственный автоматизированный конвейер. Запустите IDE по вашему выбору и установите следующие пакеты:
pip install openpyxlpip install python-docx
Автоматизация Microsoft Excel
Для начала загрузим уже созданную книгу Excel (как показано ниже):
workbook = xl.load_workbook('Book1.xlsx')
sheet_1 = workbook['Sheet1']
Затем мы пройдемся по всем строкам в нашей электронной таблице для того, чтобы вычислить и вставить значение мощности, которую мы получим, умножив ток на напряжение:
for row in range(2, sheet_1.max_row + 1):
current = sheet_1.cell(row, 2)
voltage = sheet_1.cell(row, 3)
power = float(current.value) * float(voltage.value)
power_cell = sheet_1.cell(row, 1)
power_cell.value = power
Как только мы сделаем это, то мы сможем использовать рассчитанные значения мощности для построения линейной диаграммы, которая будет вставлена в указанную ячейку, как показано ниже:
values = Reference(sheet_1, min_row = 2, max_row = sheet_1.max_row, min_col = 1, max_col = 1)
chart = LineChart()
chart.y_axis.title = 'Power'
chart.x_axis.title = 'Index'
chart.add_data(values)
sheet_1.add_chart(chart, 'e2')
workbook.save('Book1.xlsx')
Извлечение диаграммы
Теперь, когда мы построили нашу диаграмму, нам нужно ее извлечь в формате изображения для того, чтобы мы могли использовать ее в нашем отчете Word. Для начала объявим точное местоположения нашего файла Excel, а также место, куда мы хотим сохранить изображение получившейся диаграммы:
input_file = "C:/Users/.../Book1.xlsx"
output_image = "C:/Users/.../chart.png"
Затем необходимо получить доступ к таблице, используя следующий метод:
operation = win32com.client.Dispatch("Excel.Application")
operation.Visible = 0
operation.DisplayAlerts = 0
workbook_2 = operation.Workbooks.Open(input_file)
sheet_2 = operation.Sheets(1)
И далее вы можете перебрать все диаграммы в таблице (если их больше одной) и сохранить их в указанном месте:
for x, chart in enumerate(sheet_2.Shapes):
chart.Copy()
image = ImageGrab.grabclipboard()
image.save(output_image, 'png')
passworkbook_2.Close(True)
operation.Quit()
Автоматизация Microsoft Word
Теперь, когда у нас есть изображение диаграммы, мы должны создать шаблон документа, который представляет собой обычный документ Microsoft Word (.docx), сформированный именно так, как нам необходимо, чтобы наш отчет имел определенный тип и размер шрифта, нужное форматирование и структуру страницы. Далее, все, что нам необходимо сделать, это создать заполнители для нашего автоматизированного содержимого, то есть значений таблиц и изображений, и объявить их с переменными, как показано ниже.
Внутри двойных фигурных скобок {{variable_name}} может быть объявлен любое автоматизированное содержимое, включая текст и изображения. Для таблиц вам необходимо создать таблицу с шаблонной строкой, в которую включены все столбцы, а затем вам необходимо добавить еще одну строку выше и одну строку ниже со следующими обозначениями:
Первая строка:
{%tr for item in variable_name %}
Последняя строка:
{%tr endfor %}
На рисунке выше указаны следующие имена переменных:
table_contents для словаря Python, в котором будут храниться наши табличные данные.
Index для ключей словаря (первый столбец).
Power, Current и Voltage для значений словаря (второй, третий и четвертый столбцы).
Затем мы импортируем наш документ-шаблон в Python и создаем словарь, в котором будут храниться значения нашей таблицы:
template = DocxTemplate('template.docx')
table_contents = []for i in range(2, sheet_1.max_row + 1):
table_contents.append({
'Index': i-1,
'Power': sheet_1.cell(i, 1).value,
'Current': sheet_1.cell(i, 2).value,
'Voltage': sheet_1.cell(i, 3).value
})
Далее мы импортируем изображение диаграммы, которое ранее мы создали в Excel, и создаем еще один словарь для создания экземпляров всех переменных-заполнителей, объявленных в документе-шаблоне:
image = InlineImage(template,'chart.png',Cm(10))context = {
'title': 'Automated Report',
'day': datetime.datetime.now().strftime('%d'),
'month': datetime.datetime.now().strftime('%b'),
'year': datetime.datetime.now().strftime('%Y'),
'table_contents': table_contents,
'image': image
}
И, наконец, мы отображаем отчет с нашей таблицей значений и изображением диаграммы:
template.render(context)
template.save('Automated_report.docx')
Заключение
И вот, мы получили автоматически созданный отчет Microsoft Word с числами и диаграммами, созданными в Microsoft Excel. При этом у вас есть полностью автоматизированный конвейер, который можно использовать для создания любого количества таблиц, диаграмм и документов.
Исходный код программы
import openpyxl as xl
from openpyxl.chart import LineChart, Reference
import win32com.client
import PIL
from PIL import ImageGrab, Image
import os
import sys
from docx.shared import Cm
from docxtpl import DocxTemplate, InlineImage
from docx.shared import Cm, Inches, Mm, Emu
import random
import datetime
import matplotlib.pyplot as plt
######## Generate automated excel workbook ########
workbook = xl.load_workbook('Book1.xlsx')
sheet_1 = workbook['Sheet1']
for row in range(2, sheet_1.max_row + 1):
current = sheet_1.cell(row, 2)
voltage = sheet_1.cell(row, 3)
power = float(current.value) * float(voltage.value)
power_cell = sheet_1.cell(row, 1)
power_cell.value = power
values = Reference(sheet_1, min_row = 2, max_row = sheet_1.max_row, min_col = 1, max_col = 1)
chart = LineChart()
chart.y_axis.title = 'Power'
chart.x_axis.title = 'Index'
chart.add_data(values)
sheet_1.add_chart(chart, 'e2')
workbook.save('Book1.xlsx')
######## Extract chart image from Excel workbook ########
input_file = "C:/Users/.../Book1.xlsx"
output_image = "C:/Users/.../chart.png"
operation = win32com.client.Dispatch("Excel.Application")
operation.Visible = 0
operation.DisplayAlerts = 0
workbook_2 = operation.Workbooks.Open(input_file)
sheet_2 = operation.Sheets(1)
for x, chart in enumerate(sheet_2.Shapes):
chart.Copy()
image = ImageGrab.grabclipboard()
image.save(output_image, 'png')
pass
workbook_2.Close(True)
operation.Quit()
######## Generating automated word document ########
template = DocxTemplate('template.docx')
#Generate list of random values
table_contents = []
for i in range(2, sheet_1.max_row + 1):
table_contents.append({
'Index': i-1,
'Power': sheet_1.cell(i, 1).value,
'Current': sheet_1.cell(i, 2).value,
'Voltage': sheet_1.cell(i, 3).value
})
#Import saved figure
image = InlineImage(template,'chart.png',Cm(10))
#Declare template variables
context = {
'title': 'Automated Report',
'day': datetime.datetime.now().strftime('%d'),
'month': datetime.datetime.now().strftime('%b'),
'year': datetime.datetime.now().strftime('%Y'),
'table_contents': table_contents,
'image': image
}
#Render automated report
template.render(context)
template.save('Automated_report.docx')