По вашему запросу ничего не найдено :(
Убедитесь, что запрос написан правильно, или посмотрите другие
наши статьи:
Так как многие используют у себя в качестве платформы виртуализации Hyper-V, сегодня мы решили немного рассказать о том, как "правильно" использовать данную платформу – в плане сохранения ресурсов и просто с точки зрения логики. Рекомендации описанные ниже вполне смогут сохранить вам немного драгоценных вычислительных ресурсов. Поэтому ниже вы найдете 14 хинтов, которые могут помочь сохранить ресурсы.
Не плодите виртуальные сущности!
Первый хинт, и достаточно очевидный -не создавайте ненужных виртуальных машин и не оставляйте их запущенными! Процесс VMMS.exe постоянно проверяет статус всех виртуальных машин, в том числе и без каких-либо активных процессов, помимо ОС запущенных на них. Таким образом, на данный процесс тратятся дорогие ресурсы.
Далее, задумайтесь, сколько виртуальных коммутаторов у вас создано – подумайте, в каком случае вы можете просто использовать VLAN или другие механизмы сегментирования для логического разделения сети между виртуальными машинами. Причина такая же как и в предыдущем случае – VMMS.exe постоянно проверяет состояние виртуальных свитчей и тратит ресурсы!
Настройте антивирус так, чтобы он не проверял Hyper-V процессы и директории, так как такое ПО как антивирус постоянно производит I/O операции для файлов, и, соответственно, может отобрать ресурс у процессов, выполняемых между виртуальными машинами. То есть:
Процессы Hyper-V - VMMS.exe и VMWP.exe
Папки с виртуальными машинами - файлы с виртуальными жесткими дисками и файлы конфигурации
Папки со снэпшотами-V - снэпшоты и чекпоинты
Используйте официально поддерживаемы гостевые ОС – будет быстрее!
Старайтесь использовать только те гостевые системы, на которые возможно установить Integration Services – дополнения, которые включают в себя VMBUS и VSP/VSC компоненты, используется для значительного улучшения связи между Windows, на котором установлен Hyper-V и виртуальными машинами. Список поддерживаемых систем можно найти по ссылке: https://docs.microsoft.com
Кроме того, старайтесь хранить виртуальные машины, которые не поддерживают установку Integration Services на отдельном сервере Hyper-V. Если это невозможно – используйте отдельный виртуальный свитч. Дело в том, что они используют совершенно разные механизмы общения с оригинальной системой – коммуникации через VMBUS и коммуникации через эмуляцию. Эмуляция быстрее, но возможна только при установленных Integration Services.
Старайтесь использовать виртуальные машины Generation Type 2 (второго поколения), которые загружаются с помощью SCSI контроллера, вместо IDE (SCSI быстрее). Кроме того, машины второго поколения используют VMBUS и VSP/VSC архитектуру на boot уровне, что улучшает общую производительность.
Внимательнее относитесь к расположению виртуальных машин!
Не храните виртуальные машины на одном жестком диске вместе с системными файлами и файлами гипервизора – опять же из-за того, что ОС занимает свою долю в операциях ввода-ввывода, и у жесткого диска легко не может хватить производительности для задач, выполняемых на виртуальных машинах. Соответственно, всегда изменяйте папку хранения виртуальных машин по умолчанию на что-то иное. Изначально, путь выглядит так:C:ProgramDataWindowsHyper-VVirtual Machines
Если возможно – используйте для каждой виртуальной машины разные тома. Наличие нескольких виртуальных машин на одном логическом томе также повышает количество производимых I/O операций.
Регулярно дефрагментируйте жесткий диск перед созданием виртуального жесткого диска и просто проводите дефрагментацию разделов, где хранятся виртуальные машины.
Старайтесь использовать SCSi контроллеры для виртуальных жестких дисков – выиграйте по скорости. Для приложений вроде SQL лучше хранить логи и сами данные на разных SCSi разделах
При создании виртуальной машины лучше используйте виртуальные жесткие диски фиксированного размера – это так же даст прирост производительности.
В общем о ресурсах
В то же время, рекомендуется использовать динамически аллоцируемую оперативную память. Однако, для некоторых приложений также лучше будет использовать изначально большой объем фиксированной ОЗУ – но это применимо только к узкому ряду приложений, вроде Sharepoint.
Старайтесь использовать Windows Server Core Operating System, так как там нет графической оболочки, система потребляет меньше ресурсов.
Если же вы используете обычный Windows с обычным, всем очень хорошо знакомым GUI всегда закрывайте другие окна, приложения и так далее – все, что хотя бы теоретически может повлиять на производительность.
Создание VLAN-ов, как и все другие конфигурации на сетевом оборудование, достигается путем ввода соответствующих команд. В этой статье рассматриваются настройка разных типов VLAN на коммутаторах Cisco.
Диапазоны VLAN на коммутаторах Catalyst
В зависимости от модели, коммутаторы Cisco поддерживает разное число VLAN. Числа поддерживаемых VLAN обычно вполне достаточно для задач большинства компаний. Например, коммутаторы Cisco Catalyst 2960 и 3650 поддерживают больше 4000 виртуальных сетей. Нормальный диапазон VLAN начинается от 1 до 1005, а расширенный – от 1006 до 4094. На выводе внизу можно увидеть VLAN по умолчание на коммутаторе Cisco Catalyst 2960 с Cisco IOS 15 версии.
Switch# show vlan brief
VLAN Name Status Ports
---- ----------------- ------- --------------------
1 default active Fa0/1, Fa0/2, Fa0/3, Fa0/4
Fa0/5, Fa0/6, Fa0/7, Fa0/8
Fa0/9, Fa0/10, Fa0/11, Fa0/12
Fa0/13, Fa0/14, Fa0/15, Fa0/16
Fa0/17, Fa0/18, Fa0/19, Fa0/20
Fa0/21, Fa0/22, Fa0/23, Fa0/24
Gi0/1, Gi0/2
1002 fddi-default act/unsup
1003 token-ring-default act/unsup
1004 fddinet-default act/unsup
1005 trnet-default act/unsup
Нормальный диапазон VLAN
Ниже перечислены основные характеристики нормального диапазона:
Они используются в малых, средних и больших сетях;
Нумерация начинается от 1 до 1005;
Идентификаторы с 1002 до 1005 зарезервированы для устаревших сетей (Token Ring, FDDI);
Идентификаторы с 1002 до 1005 созданы автоматически и не могут быть удалены;
Созданные VLAN хранятся в памяти коммутатора в файле базы данных VLAN, именуемого vlan.dat;
VTP, если настроен, помогает распространять все VLAN между коммутаторами.
Расширенный диапазон
Ниже перечислены основные характеристики расширенного VLAN:
Используется провайдерами и очень большими компаниями;
Нумерация начинается с 1006 по 4094;
По умолчанию, они хранятся в running-config;
Имеют меньшую функциональность, чем нормальные VLAN;
Для настройки расширенного VLAN VTP должен работать в режиме transparent.
Примечание: Ограничение количества доступных VLAN продиктовано особенностями заголовка 802.1Q. Полю VLAN ID заголовка 802.1Q IEEE выделено всего 12 бит, поэтому 4096 -- верхняя граница доступных VLAN на коммутаторах Catalyst. А если нужно больше, то можно обратиться к такой технологии как VXLAN.
Команды для создания VLAN
Когда создается VLAN нормального диапазона, как уже было отмечено, эти настройки хранятся в файле vlan.dat, то есть не нужно вводить команды copy running-config startup-config или write memory. Тем не менее, чтобы не потерять изменения сделанные наряду с созданием VLAN, рекомендуется сохранять текущую конфигурацию.
В таблице ниже перечислены команды, которые нужно вводит для создания VLAN и присвоения им названия. Хорошей практикой считается давать VLAN понятные названия, чтобы облегчить поиск и устранение проблем в будущем.
ЗадачаIOS командаВойти в режим глобальной конфигурацииSwitch# configure terminalСоздать VLAN с валидным IDSwitch(config)# vlan vlan-idУказать уникальное имя для идентификации VLANSwitch(config-vlan)# name vlan-nameВернуться в привилегированный режим EXECSwitch(config-vlan)# end
Пример создания VLAN
В топологии ниже, порт к которому подключен ПК Stundent, еще не добавлен ни в один VLAN, но у него есть IP 172.17.20.22, который принадлежит VLAN 20.
Пример ниже демонстрирует настройку VLAN 20 с названием student на коммутаторе S1.
S1# configure terminal
S1(config)# vlan 20
S1(config-vlan)# name student
S1(config-vlan)# end
Примечание: Кроме создание VLAN-ов по одному, так же есть возможность создания нескольких влан, вводя их идентификаторы через запятые или дефис. Например, команда vlan 100,102,105-107 в режиме конфигурации создаст сразу 5 VLAN-ов с идентификаторами 100, 102, 105, 106, и 107
Добавление портов в VLAN
После создания VLAN, следующий шаг – это добавление нужных портов в конкретный VLAN.
В таблице ниже приведены команды для переведения порта в режим access и добавления в конкретный VLAN. Команда switchport mode access опциональна, но в целях безопасности рекомендуется вводить ее, так как она принудительно переводит порт в режим access, что помогает защищаться от атак вроде VLAN Hopping.
ЗадачаIOS командаВойти в режим глобальной конфигурацииSwitch# configure terminalВойти в режим конфигурации интерфейсаSwitch(config)# interface interface-idУстановить порт в режим accessSwitch(config-if)# switchport mode accessПрисвоить порт VLAN'у.Switch(config-if)# switchport access vlan vlan-idВернуться в привилегированный режим EXECSwitch(config-if)# end
Примечание: Для одновременной конфигурации нескольких портов можно воспользоваться командой interface range.
Пример присвоения порту VLAN
В топологии ниже порт F0/6 коммутатора S1 настроен в режиме access и добавлен в VLAN 20. Теперь любое устройство, подключенное к данному порту, будет в 20-ом VLAN-е, как и ПК2 в нашем случае.
А ниже приведен пример команд для реализации вышеуказанной цели.
S1# configure terminal
S1(config)# interface fa0/6
S1(config-if)# switchport mode access
S1(config-if)# switchport access vlan 20
S1(config-if)# end
VLAN настраивается на порту коммутатора, а не на конечном устройстве. ПК2 присвоен IP адреси маска подсети, которая относиться к VLAN 20, а последний указан на порту коммутатора. Если VLAN 20 настроить на другом коммутаторе, администратор сети должен настроить другой компьютер так, чтобы он был в одной подсети с ПК2 (172.17.20.0/24).
VLAN данных и голосовой VLAN
На порту коммутатора в режиме access можно настроить не более одного VLAN-а данных. Тем не менее, на том же порту можно настроить голосовой VLAN. Например, порт к которому подключены IP телефон и конечное устройство, может быть сразу в двух VLAN-ах, - голосовом и VLAN-е данных.
Например, в топологии ниже, ПК5 подключен к IP телефону, который в свою очередь подключен к порту F0/18 коммутатора S3. Для реализации данной идеи созданы VLAN данных и голосовой VLAN.
Пример голосового VLAN и VLAN данных
Чтобы настроить на интерфейсе голосовой VLAN используется команда switchport voice vlan [vlan-id] в режиме конфигурации порта на коммутаторе.
В сетях, где поддерживается голосовой трафик, обычно настраиваются различные QoS. Голосовой трафик должен быть маркирован доверенным, как только попадет на интерфейс. Чтобы пометить голосовой трафик как доверенный, а так же указать какое поле пакета используется для классификации трафика, применяется команда mls qos trust [cos | device cisco-phone | dscp | ip-precedence] в режиме конфигурации интерфейса.
Конфигурация в примере ниже создаст два VLAN-а и присвоит порту F0/18 коммутатора S3 VLAN данных с идентификатором 20, а также голосовой VLAN 150 и включит QoS, на основе CoS.
S3(config)# vlan 20
S3(config-vlan)# name student
S3(config-vlan)# vlan 150
S3(config-vlan)# name VOICE
S3(config-vlan)# exit
S3(config)# interface fa0/18
S3(config-if)# switchport mode access
S3(config-if)# switchport access vlan 20
S3(config-if)# mls qos trust cos
S3(config-if)# switchport voice vlan 150
S3(config-if)# end
Если на коммутаторе еще не создан нужный VLAN команда switchport access vlan принудительно создаст его. Например, VLAN 30 не выводится при вводе команды switchport vlan brief. Но если ввести команду switchport access vlan 30 без предварительного создания под любым интерфейсом на терминале выведется соответствующее сообщение:
% Access VLAN does not exist. Creating vlan 30
Проверка настроек VLAN
После настроек VLAN, правильность конфигурации можно проверить с помощью команды show с последующим ключевым словом.
Команда show vlan выводит список существующих VLAN. Данной команде можно задать разные параметры. Полный синтаксис команды такой: show vlan [brief | id vlan-id | name vlan-name | summary].
В таблице описываются параметры команды show vlan.
ЗадачаОпция командыОтображение имени, статуса и портов VLAN по одной VLAN на строкуbriefОтображение информации об определенном номере VLAN ID. Для vlan-id диапазон от 1 до 4094id vlan-idОтображение информации об определенном имени VLAN. Vlan-name - это строка ASCII от 1 до 32 символов.name vlan-nameОтображение сводной информации о VLANsummary
Команда show vlan summary выводит количество настроенных VLAN на коммутаторе:
S1# show vlan summary
Number of existing VLANs : 7
Number of existing VTP VLANs : 7
Number of existing extended VLANS : 0
Есть и другие полезные команды вроде show interfaces interface-id switchport и show interfaces vlan vlan-id. Например, команда show interfaces fa0/18 switchport может использоваться для проверки правильно ли присвоен интерфейс F0/18 к голосовому VLAN и VLAN данных.
S1# show interfaces fa0/18 switchport
Name: Fa0/18
Switchport: Enabled
Administrative Mode: static access
Operational Mode: static access
Administrative Trunking Encapsulation: dot1q
Operational Trunking Encapsulation: native
Negotiation of Trunking: Off
Access Mode VLAN: 20 (student)
Trunking Native Mode VLAN: 1 (default)
Voice VLAN: 150
Administrative private-vlan host-association: none
(Output omitted)
Переназначение VLAN на интерфейсе
Есть несколько вариантов переназначения интерфейсу VLAN-а.
Если неправильно сконфигурировали VLAN на интерфейсе, просто введите команду switchport access vlan vlan-id подставив нужный VLAN. Например, представим что порт F0/18 добавлен в VLAN по умолчанию VLAN 1. Чтобы поменять на VLAN 20, достаточно ввести switchport access vlan 20.
Чтобы вернуть обратно в VLAN по умолчанию в режиме конфигурации интерфейса введите команду no switchport access vlan.
На выводе ниже можно убедиться, что 18-ый порт коммутатора находится в VLAN по умолчанию.
S1(config)# interface fa0/18
S1(config-if)# no switchport access vlan
S1(config-if)# end
S1#
S1# show vlan brief
VLAN Name Status Ports
---- ------------------ --------- -------------------------------
1 default active Fa0/1, Fa0/2, Fa0/3, Fa0/4
Fa0/5, Fa0/6, Fa0/7, Fa0/8
Fa0/9, Fa0/10, Fa0/11, Fa0/12
Fa0/13, Fa0/14, Fa0/15, Fa0/16
Fa0/17, Fa0/18, Fa0/19, Fa0/20
Fa0/21, Fa0/22, Fa0/23, Fa0/24
Gi0/1, Gi0/2
20 student active
1002 fddi-default act/unsup
1003 token-ring-default act/unsup
1004 fddinet-default act/unsup
1005 trnet-default act/unsup
Следует заметить, что 20-ый VLAN все еще активен, несмотря на то, что под ним нет никакого интерфейса.
Чтобы убедиться, что на 18-ый порт в VLAN 1, можно воспользоваться командой show interfaces f0/18 switchport:
S1# show interfaces fa0/18 switchport
Name: Fa0/18
Switchport: Enabled
Administrative Mode: static access
Operational Mode: static access
Administrative Trunking Encapsulation: negotiate
Operational Trunking Encapsulation: native
Negotiation of Trunking: Off
Access Mode VLAN: 1 (default)
Trunking Native Mode VLAN: 1 (default)
Удаление VLAN
Для удаления VLAN используется команда no vlan vlan-id в глобальном режиме конфигурации.
Внимание: Прежде чем удалить VLAN убедитесь, что все интерфейсам с данным VLAN назначен другой.
Чтобы удалить весь файл vlan.dat введите команду delete flash:vlan.dat в привилегированном режиме EXEC. После перезагрузки все настроенные на коммутаторе VLAN удалятся.
Примечание: Чтобы сбросить коммутаторы Catalyst до заводских настроек отсоедините все кабели кроме кабеля питания и консольного кабеля, от коммутатора. Затем введите erase startup-config после него delete vlan.dat. После перезагрузки коммутатор сбросится до первоначальных настроек.
Настройка Trunk
После создания и настройки VLAN, пора перейти к конфигурации Trunk портов. Trunk это связь на втором уровне OSI между коммутаторами, который пропускает все VLAN (если список разрешенных VLAN явно не указан).
Для настройки интерфейса в режиме Trunk нужно воспользоваться команды, указанные ниже в таблице:
ЗадачаIOS командаВойти в режим глобальной конфигурацииSwitch# configure terminalВойти в режим конфигурации интерфейсаSwitch(config)# interface interface-idУстановите порт в режим постоянного транкингаSwitch(config-if)# switchport mode trunkУстанавливает для native VLAN значение, отличное от VLAN 1Switch(config-if)# switchport trunk native vlan vlan-idУкажите список VLAN, разрешенных для транкаSwitch(config-if)# switchport trunk allowed vlan vlan-listВернуться в привилегированный режим EXECSwitch(config-if)# end
Пример настройки Trunk
В топологии ниже VLAN 10, 20 и 30 обслуживают компьютеры Faculty, Student и Guest. Порт F0/1 коммутатора S1 настроек в режиме Trunk и пропускает VLAN-ы 10, 20, 30. VLAN 99 настроен в качестве native (VLAN по умолчанию).
В данном примере показывается настройка порта в режиме trunk, смена VLAN по умолчанию и ограничение разрешенных VLAN.
S1(config)# interface fastEthernet 0/1
S1(config-if)# switchport mode trunk
S1(config-if)# switchport trunk native vlan 99
S1(config-if)# switchport trunk allowed vlan 10,20,30,99
S1(config-if)# end
Примечание: В данном примере подразумевается, что используется коммутатор Cisco Catalyst 2960, в котором порты по умолчанию используют 802.1Q. На других коммутаторах может понадобиться ручная настройка режима энкапсуляции на интерфейсе. Так же следует настроить VLAN по умолчанию на обоих концах, иначе коммутатор будет выдавать ошибки.
Проверка настройки Trunk
Вывод ниже демонстрирует настройки интерфейса Fa0/1 коммутатора S1. Данный вывод получен с помощью команды show interfaces interface-ID switchport:
S1# show interfaces fa0/1 switchport
Name: Fa0/1
Switchport: Enabled
Administrative Mode: trunk
Operational Mode: trunk
Administrative Trunking Encapsulation: dot1q
Operational Trunking Encapsulation: dot1q
Negotiation of Trunking: On
Access Mode VLAN: 1 (default)
Trunking Native Mode VLAN: 99 (VLAN0099)
Administrative Native VLAN tagging: enabled
Voice VLAN: none
Administrative private-vlan host-association: none
Administrative private-vlan mapping: none
Administrative private-vlan trunk native VLAN: none
Administrative private-vlan trunk Native VLAN tagging: enabled
Administrative private-vlan trunk encapsulation: dot1q
Administrative private-vlan trunk normal VLANs: none
Administrative private-vlan trunk associations: none
Administrative private-vlan trunk mappings: none
Operational private-vlan: none
Trunking VLANs Enabled: ALL
Pruning VLANs Enabled: 2-1001
(output omitted)
Подчеркнутые части показывают режим работы интерфейса и нативный VLAN.
Сброс trunk до настроек по умолчанию
Для сброса настроек транкового интерфейса используйте команды no switchport trunk allowed vlan и no switchport trunk native vlan. После сброса настроек данный порт будет пропускать все VLAN-ы и VLAN-ом по умолчанию будет VLAN 1.
S1(config)# interface fa0/1
S1(config-if)# no switchport trunk allowed vlan
S1(config-if)# no switchport trunk native vlan
S1(config-if)# end
Вывод команды show interfaces f0/1 switchport показывает, что порт сброшен до настроек по умолчанию:
S1# show interfaces fa0/1 switchport
Name: Fa0/1
Switchport: Enabled
Administrative Mode: trunk
Operational Mode: trunk
Administrative Trunking Encapsulation: dot1q
Operational Trunking Encapsulation: dot1q
Negotiation of Trunking: On
Access Mode VLAN: 1 (default)
Trunking Native Mode VLAN: 1 (default)
Administrative Native VLAN tagging: enabled
Voice VLAN: none
Administrative private-vlan host-association: none
Administrative private-vlan mapping: none
Administrative private-vlan trunk native VLAN: none
Administrative private-vlan trunk Native VLAN tagging: enabled
Administrative private-vlan trunk encapsulation: dot1q
Administrative private-vlan trunk normal VLANs: none
Administrative private-vlan trunk associations: none
Administrative private-vlan trunk mappings: none
Operational private-vlan: none
Trunking VLANs Enabled: ALL
Pruning VLANs Enabled: 2-1001
(output omitted)
В вывод ниже показывает команды, которые используются для смены режима работы интерфейс с trunk на access.
S1(config)# interface fa0/1
S1(config-if)# switchport mode access
S1(config-if)# end
S1# show interfaces fa0/1 switchport
Name: Fa0/1
Switchport: Enabled
Administrative Mode: static access
Operational Mode: static access
Administrative Trunking Encapsulation: dot1q
Operational Trunking Encapsulation: native
Negotiation of Trunking: Off
Access Mode VLAN: 1 (default)
Trunking Native Mode VLAN: 1 (default)
Administrative Native VLAN tagging: enabled
(output omitted)
Bellman-Ford - один из наиболее простых для понимания протоколов, поскольку он обычно реализуется путем сравнения недавно полученной информации о пункте назначения с существующей информацией о том же пункте назначения. Если вновь обнаруженный маршрут лучше, чем известный в настоящее время, маршрут с более высокой стоимостью просто заменяется в списке путей - в соответствии с правилом кратчайшего пути для поиска путей без петель в сети. Таким образом, перебирая всю топологию, можно найти набор кратчайших путей к каждому месту назначения. Рисунок 7 используется для иллюстрации этого процесса.
Примечание. Хотя Bellman-Ford в основном известен своим распределенным вариантом, реализованным в широко распространенных протоколах, таких как Routing Information Protocol (RIP), он изначально был разработан как алгоритм поиска, выполняемый в единой структуре, описывающей топологию узлов и ребер. Беллман-Форд рассматривается здесь как алгоритм.
Алгоритм Bellman-Ford
Bellman-Ford рассчитывает Shortest Path Tree к каждому достижимому пункту назначения в наихудшем случае O (V * E), где V - количество узлов (вершин) в сети, а E - количество каналов (ребер). По сути, это означает, что время, необходимое Bellman-Ford для работы с топологией и вычисления Shortest Path Tree, линейно зависит от количества устройств и каналов. Удвоение количества любого из них удвоит время, необходимое для выполнения. Удвоение обеих одновременно увеличит время работы в 4 раза.
Таким образом, алгоритм Bellman-Ford является умеренно медленным при использовании против более крупных топологий, когда узлы в таблице топологии начинаются в порядке от самого дальнего от корня до ближайшего к корню. Если таблица топологии отсортирована от ближайшего к корню до самого дальнего, Bellman-Ford может завершить работу за O(E), что намного быстрее. В реальном мире трудно обеспечить любой порядок, поэтому фактическое время, необходимое для построения Shortest Path Tree, обычно находится где-то между O(V * E) и O(E).
Bellman-Ford - это greedy алгоритм, предполагающий, что каждый узел в сети, кроме локального, доступен только по бесконечным стоимостям, и заменяющий эти бесконечные стоимости фактическими стоимостями по мере прохождения топологии. Предположение, что все узлы бесконечно удалены, называется ослаблением вычислений, так как он использует приблизительное расстояние для всех неизвестных пунктов назначения в сети, заменяя их реальной стоимостью после ее расчета.
Фактическое время выполнения любого алгоритма, используемого для расчета Shortest Path Tree, обычно ограничивается количеством времени, требуемым для передачи информации об изменениях топологии по сети. Реализации всех этих протоколов, особенно в их распределенной форме, будут содержать ряд оптимизаций, чтобы сократить время их выполнения до уровня, намного меньшего, чем наихудший случай, поэтому, хотя наихудший случай дается в качестве контрольной точки, он часто имеет мало влияющие на производительность каждого алгоритма в реальных развернутых сетях.
Чтобы запустить алгоритм Bellman-Ford в этой топологии, ее необходимо сначала преобразовать в набор векторов и расстояний и сохранить в структуре данных, такой как показано в Таблице 1.
В этой таблице девять записей, потому что в сети девять звеньев (граней). Алгоритмы кратчайшего пути вычисляют однонаправленное дерево (в одном направлении вдоль графа). В сети на рисунке 7 показано, что SPT берет начало в узле 1, а расчет показан удаленным от узла 1, который будет точкой, из которой будут выполняться вычисления. Алгоритм в псевдокоде следующий:
// создаем набор для хранения ответа, по одной записи для каждого узла
// первый слот в результирующей структуре будет представлять узел 1,
// второй узел 2 и т. д.
define route[nodes] {
predecessor // как узел
cost // как целое число
}
// установите для источника (меня) значение 0
// позиция 1 в массиве - это запись исходной точки.
route[1].predecessor = NULL
route[1].cost = 0
// таблица 1, приведенная выше, содержится в массиве под именем topo
// Обходим таблицу вершин (граней) один раз для каждой записи в маршруте
// (результаты) таблица, замены более длинных записей на более короткие
i = nodes
while i > 0 {
j = 1
while j <= nodes { // перебирает каждую строку в топологии
table
source_router = topo[j].s
destination_router = topo[j].d
link_cost = topo[j].cost
if route[source_router].cost == NULL {
source_router_cost = INFINITY
} else {
source_router_cost = route[source_router].cost
}
if route[destination_router].cost == NULL {
destination_router_cost = INFINITY
} else {
destination_router_cost = route[destination_router].cost
}
if source_router_cost + link_cost <= destination_router_cost {
route[destination_router].cost = source_router_cost + link_
cost
route[destination_router].predecessor = source_router
}
j = j + 1 //or j++ depending on what pseudocode this is
representing
}
i = i - 1
}
Этот код обманчиво выглядит сложнее, чем есть на самом деле. Ключевой строкой является сравнение if route [topo [j] .s] .cost + topo [j] .cost route [topo [j] .d] .cost. Полезно сосредоточиться на этой строке в примере. При первом прохождении внешнего цикла (который выполняется один раз для каждой записи в таблице результатов, здесь называется маршрутом):
Для первой строки topo-таблицы:
j равно 1, поэтому topo[j] .s - это узел 6 (F), источник вектора в таблице граней
j равно 1, поэтому topo[j] .d - это узел 7 (G), адресат вектора в таблице граней.
route[6].cost = infinity, topo[1].cost = 1, and route[7].cost = infinity (где infinity - бесконечность)
infinity + 1 == infinity, поэтому условие не выполняется и больше ничего не происходит
Любая запись в topo-таблице с исходной стоимостью infinity даст тот же результат, что и infinity + все, что всегда будет равно infinity. Остальные строки, содержащие источник со стоимостью infinity, будут пропущены.
Для восьмой строки topo-таблицы (восьмая грань):
j равно 8, поэтому topo[j].s - это узел 1 (A), источник вектора в таблице граней
j равно 8, поэтому topo[j].d - это узел 2 (B), место назначения вектора в таблице граней.
route [1].cost = 0, topo[8].cost=2 и route[2].cost = infinity.
0 + 2 = infinity, поэтому условие выполняется
route[2].predecessor установлен на 1, а route [2].cost установлен на 2
Для девятой строки topo -таблицы (девятая грань):
j равно 9, поэтому topo[j].s - это узел 1 (A), источник вектора в таблице граней
j равно 9, поэтому topo[j].d - это узел 3 (C), место назначения вектора в таблице граней.
route[1].cost=0, topo[9].cost=1 и route[3].cost = infinity.
0 + 1 = infinity, поэтому условие выполняется
route[3].predecessor установлен на 1, а route[3].cost установлен на 1
Во втором прогоне внешнего цикла:
Для пятой строки topo-таблицы (пятая грань):
j равно 5, поэтому topo[j].s - это узел 2 (B), источник вектора в таблице граней
j равно 5, поэтому topo[j].d - это узел 6 (F), место назначения вектора в таблице граней.
route[2].cost=2,topo[5].cost=1 и route[6].cost = infinity.
2 + 1 = infinity, поэтому условие выполняется
route[6].predecessor установлен на 2, а route[6].cost установлен на 3
Для шестой строки topo -таблицы (шестая грань):
j равно 6, поэтому topo[j].s равно 2 (B), источник вектора в таблице граней
j равно 6, поэтому topo[j].d равно 5 (E), место назначения вектора в таблице граней
route[2].cost=2, topo[6].cost=2 и route[5].cost = infinity.
2 + 2 = infinity, поэтому условие выполняется
route[5].predecessor установлен на 2, а route[5].cost установлен на 4
Окончание этого прогона показан в Таблице 2.
В третьем прогоне внешнего цикла узел 8 представляет особый интерес, поскольку есть два пути к этому месту назначения. Для второй строки topo -таблицы (вторая грань):
j равно 2, поэтому topo[j].s - это узел 5 (E), источник вектора в таблице граней
j равно 2, поэтому topo[j].d - это узел 8 (H), место назначения вектора в таблице граней
route[5].cost=4, topo[2].cost=1 и route[8].cost = infinity.
4 + 1 = infinity, поэтому условие выполняется
route[8].predecessor установлен на 5, а route[8].cost установлен на 5
Для третьей строки topo -таблицы (третья грань):
j равно 3, поэтому topo[j].s - это узел 4 (D), источник вектора в в таблице граней
j равно 3, поэтому topo[j].d - это узел 8 (H), источник вектора в таблице граней
route[4].cost=2,topo[3].cost=2 и route[8].cost = 5.
2 + 2 = 4, поэтому условие выполняется
route[8].predecessor установлен на 4, а route[8].cost установлен на 4
Интересным моментом в третьем цикле в topo-таблице является то, что запись для грани [5,8] обрабатывается первой, которая устанавливает передатчик 8 (H) на 5 и стоимость на 5. Однако когда обрабатывается следующая строка в таблице topo [4,8], алгоритм обнаруживает более короткий путь к узлу 8 и заменяет существующий. Таблица 2 показывает состояние таблицы маршрутов при каждом проходе через таблицу topo.
В таблице 2 верхняя строка представляет запись в таблице маршрутизации и узел, доступный в сети. Например, A (1) представляет лучший путь к A, B (2) представляет лучший путь к B и т. д. Столбец P представляет предшественника или узел, через который A должен пройти, чтобы достичь указанного пункта назначения. C представляет собой стоимость достижения этого пункта назначения. Рассмотренный пример сети может быть завершен за три цикла, если алгоритм настроен так, чтобы обнаруживать завершение дерева. Псевдокод, как показано, не имеет никакого теста для этого завершения и в любом случае будет выполнять полные 8 циклов (по одному для каждого узла).
Теперь почитайте про алгоритм диффузного обновления DUAL.