По вашему запросу ничего не найдено :(
Убедитесь, что запрос написан правильно, или посмотрите другие
наши статьи:
В этой статье мы рассмотрим IPv6 (Internet Protocol version 6), причины, по которым он нам нужен, а также следующий аспект: различия с IPv4. Пока существует Интернет, используется протокол IPv4 для адресации и маршрутизации. Однако проблема с IPv4 заключается в том, что у нас закончились адреса.
Так что же случилось с IPv4? Что же пошло не так? У нас есть 32 бита, которые дают нам 4 294 467 295 IP-адресов. Когда появился Интернет, мы получили сети класса А, В или С. Класс С дает нам блок из 256 IP-адресов, класс B - это 65.535 IP-адресов, а класс A даже 16 777 216 IP-адресов. Крупные компании, такие как Apple, Microsoft, IBM и др. имеют одну или несколько сетей класса А. Но действительно ли им нужно 16 миллионов IP-адресов? Большинство из этих IP-адресов не были использованы.
Поэтому мы начали использовать VLSM, чтобы использовать любую маску подсети, которая нам нравится, и создавать более мелкие подсети, а не только сети класса A, B или C. У нас также имеется NAT и PAT, следовательно, мы имеем много частных IP-адресов за одним публичным IP-адресом.
Тем не менее интернет вырос так, как никто не ожидал 20 лет назад. Несмотря на все наши крутые трюки, такие как VLSM и NAT/PAT, нам нужно было больше IP-адресов, и поэтому родился IPv6.
А что случилось с IPv5? Хороший вопрос ... IP-версия 5 была использована для экспериментального проекта под названием "Протокол интернет-потока". Он определен в RFC, если вас интересуют исторические причины: http://www.faqs.org/rfcs/rfc1819.html
IPv6 имеет 128-битные адреса по сравнению с нашими 32-битными IPv4-адресами. Имейте в виду, что каждый дополнительный бит удваивает количество IP-адресов. Таким образом мы переходим от 4 миллиардов к 8 миллиардам, 16,32,64 и т. д. Продолжайте удвоение, пока не достигнете 128-битного уровня. Просто вы увидите, сколько IPv6-адресов это даст нам:
340,282,366,920,938,463,463,374,607,431,768,211,456;
Можем ли мы вообще произнести это? Давайте попробуем вот это:
340 - ундециллионов;
282 - дециллионов;
366 - нониллионов;
920 - октиллионов;
938 - септиллионов;
463 - секстиллионов;
463 - квинтильонов;
374 - квадрильонов;
607 - триллионов;
431 - биллионов;
768 - миллионов;
211 - тысяч;
456.
Это умопомрачительно... это дает нам достаточное количество IP-адресов для сетей на Земле, Луне, Марсе и остальной Вселенной. IPv6-адреса записываются в шестнадцатеричном формате.
IPv4 и IPv6 несовместимы друг с другом, поэтому многие протоколы были обновлены или заменены для работы с IPv6, вот некоторые примеры:
OSPF был обновлен с версии 2 (IPv4) до версии 3 (IPv6);
ICMP был обновлен до версии ICMP 6;
ARP был заменен на NDP (Neighborhood Discovery Protocol).
Заголовок пакета IPv6 содержит адреса источника и назначения, но по сравнению с IPv4 он стал намного проще:
Вместо того чтобы уже добавлять все поля в заголовок, заголовок IPv6 использует "следующий заголовок", который ссылается на необязательные заголовки. Поскольку заголовок намного проще, маршрутизаторам придется выполнять меньше работы.
А как насчет маршрутизации? Есть ли разница между IPv4 и IPv6? Давайте рассмотрим варианты маршрутизации:
Static Routing;
RIPng;
OSPFv3;
MP-BGP4;
EIGRP.
Вы все еще можете использовать статическую маршрутизацию, как и в IPv4, ничего нового здесь нет. RIP был обновлен и теперь называется RIPng или RIP Next Generation.
OSPF для IPv4 на самом деле является версией 2, а для IPv6 у нас есть версия 3. Это отдельный протокол, он работает только на IPv6. Есть только незначительные изменения, внесенные в OSPFv3.
BGP (Border Gateway Protocol) - это протокол маршрутизации, который объединяет Интернет вместе.MP-BGP расшифровывается как Multi-Protocol BGP, и он может маршрутизировать IPv6. EIGRP также поддерживает IPv6.
Просто имейте в виду, что OSPF и EIGRP поддерживают IPv6, но это отдельные протоколы. Если у вас есть сеть с IPv4 и IPv6, вы будете запускать протокол маршрутизации для IPv4 и еще один для IPv6. Запуск IPv4 и IPv6 одновременно называется двойным стеком.
Поскольку эти два протокола несовместимы, в будущем будет происходить переход с IPv4 на IPv6. Это означает, что вы будете запускать оба протокола в своей сети и, возможно, однажды вы сможете отключить IPv4, так как весь интернет будет настроен на IPv6.
Давайте взглянем на формат IPv6-адреса: 2041:0000:140F:0000:0000:0000:875B:131B
Во-первых, он шестнадцатеричный и гораздо длиннее, чем IPv4-адрес. Существует восемь частей, состоящих из 4 шестнадцатеричных цифр каждая, поэтому 128-битный адрес может быть представлен 32-битными шестнадцатеричными символами. Если вы забыли, как работает шестнадцатеричный код, взгляните на таблицу ниже:
В шестнадцатеричной системе счисления мы считаем от 0 до F точно так же, как мы считали бы от 0 до 15 в десятичной системе счисления:
A = 10;
B = 11;
C = 12;
D = 13;
E = 14;
F = 15.
Использование шестнадцатеричного кода помогает сделать наши адреса короче, но ввод адреса IPv6 - это все еще большая работа. Представьте себе, что вы звоните другу и спрашиваете его, может ли он пинговать IPv6-адрес 2041:0000:140F:0000:0000:0000:875B:131B, чтобы узнать, может ли он достучаться до своего шлюза по умолчанию.
Чтобы облегчить нам работу с такими адресами, можно сделать IPv6-адреса короче. Вот пример:
Оригинальный: 2041: 0000:140F:0000:0000:0000:875B:131B
Сокращенный: 2041: 0000:140F:: 875B:131B
Если есть строка нулей, вы можете удалить их, заменив их двойным двоеточием (::). В приведенном выше IPv6-адресе удалены нули, сделав адрес немного короче. Вы можете сделать это только один раз.
Мы можем сделать этот IPv6 адрес еще короче используя другой трюк:
Сокращенный: 2041: 0000:140F:: 875B:131B;
Еще короче: 2041:0:140F:: 875B:131B
Если у вас есть блок с 4 нулями, вы можете удалить их и оставить там только один ноль.
Мы также можем удалить все впередистоящие нули:
Оригинальный: 2001:0001:0002:0003:0004:0005:0006:0007;
Сокращенный: 2001:1:2:3:4:5:6:7
Подытожим небольшие правила:
Строку нулей можно удалить, оставив только двоеточие (::). Вы можете сделать только это однажды.;
4 нуля можно удалить, оставив только один ноль. Впередиидущие нули могут быть удалены в пределах одного блока.;
Вы не можете удалить все нули, иначе ваше устройство, работающее с IPv6 не поймет, где заполнить нули, чтобы снова сделать его 128-битным.;
Вычисление префикса IPV6 мы пропустим, так как ресурсов, рассказывающих об этом в сети Интернет, специальных книгах полно. Нет смысла повторяться.
Потребуется некоторое время, чтобы привыкнуть к IPv6-адресации и поиску префиксов, но чем больше вы этим занимаетесь, тем дальше становиться проще. В оставшейся части этой статьи мы еще немного поговорим о различных типах адресации IPv6. IPv4-адреса организованы с помощью "системы классов", где класс A, B и C предназначены для одноадресных IP-адресов, а класс D-для многоадресной передачи. Большинство IP-адресов в этих классах являются публичными IP-адресами, а некоторые-частными IP-адресами, предназначенными для наших внутренних сетей. Нет такой вещи, как классы для IPv6, но IANA действительно зарезервировал определенные диапазоны IPv6 для конкретных целей. У нас также есть частные и публичные IPv6-адреса. Первоначально идея IPv4 заключалась в том, что каждый хост, подключенный к Интернету, будет иметь общедоступный IP-адрес. Каждая компания получит сеть класса А, В или С, и сетевые инженеры в компании будут дополнительно подсоединять ее так, чтобы каждый хост и сетевое устройство имели общедоступный IP-адрес.
Проблема, однако, заключается в том, что адресное пространство IPv4 было слишком маленьким, и выдавать полные сети A, B или C было не очень разумно. Даже если вам требуется только небольшое количество IP-адресов, вы все равно получите сеть класса C, которая дает вам 254 пригодных для использования IP-адреса. Компания, которой требуется 2.000 IP-адресов, получит класс B, который дает вам более 65.000 IP-адресов.
Поскольку у нас заканчивались IP-адреса, мы начали использовать такие вещи, как VLSM (избавляясь от идеи класса A, B, C) и настраивали частные IP-адреса в наших локальных сетях, а вместо этого использовали NAT/PAT. Протокол IPv6 предлагает два варианта для одноадресной рассылки:
Global Unicast;
Unique Local.
Раньше существовал третий диапазон адресов, называемый "site local", который начинался с FEC0:: / 10. Этот диапазон изначально предназначался для использования во внутренних сетях, но был удален из стандарта IPv6.
Global Unicast передачи IPv6 похожи на публичные IPv4-адреса. Каждая компания, которая хочет подключиться к интернету с помощью IPv6, получит блок IPv6-адресов, которые они могут дополнительно разделить на более мелкие префиксы, чтобы все их устройства имели уникальный IPv6-адрес. Зарезервированный блок называется префиксом глобальной маршрутизации.
Поскольку адресное пространство IPv6 настолько велико, каждый может получить префикс глобальной маршрутизации. Давайте посмотрим, как назначаются префиксы IPv6-адресов. Допустим, компания получает префикс 2001:828:105:45::/64. Как они его получили?
Мы пройдемся по этой картине сверху вниз:
IANA отвечает за распределение всех префиксов IPv6. Они будут назначать реестрам различные блоки. ARIN - для Северной Америки, RIPE -для Европы, Ближнего Востока и Центральной Азии. Всего таких реестров насчитывается 5. IANA присваивает 2001: 800:: /23 RIPE и 2001: 0400::/23 ARIN (и многие другие префиксы).;
ISP, который попадает под реестр RIPE, запрашивает блок пространства IPv6. Они получают от них 2001: 0828:: / 32, которые в дальнейшем могут использовать для клиентов.;
ISP дополнительно подсоединит свое адресное пространство 2001:0828::/32 для своих пользователей. В этом примере клиент получает префикс 2001:828:105::/48.;
IANA зарезервировала определенные диапазоны адресов IPv6 для различных целей, точно так же, как это было сделано для IPv4. Первоначально они зарезервировали IPv6-адреса, которые с шестнадцатеричными 2 или 3 являются global unicast адресами. Это можно записать как 2000:: / 3. В настоящее время они используют все для global unicast рассылки, которая не зарезервирована для других целей.
Некоторые из зарезервированных префиксов являются:
FD: Unique Local;
FF: Multicast;
FE80: Link-Local.
Обсудим префиксы local и link-local
В моем примере клиент получил 2001: 828:105:: / 48 от провайдера, но прежде чем я смогу что-либо сделать с этим префиксом, мне придется разбить на подсети его для различных VLAN и point-to-point соединений, которые у меня могут быть. Подсети для IPv6 - это примерно то же самое, что и для IPv4, но математика в большинстве случаев проще. Поскольку адресное пространство настолько велико, почти все используют префикс /64 для подсетей. Нет смысла использовать меньшие подсети.
При использовании IPv4 у нас была часть "сеть" и "хост", а класс A, B или C определяет, сколько битов мы используем для сетевой части:
Когда мы используем подсети в IPv4 мы берем дополнительные биты от части хоста для создания большего количества подсетей:
И, конечно, в результате у нас будет меньше хостов на подсеть. Подсети для IPv6 используют аналогичную структуру, которая выглядит следующим образом:
Префикс global routing был назначен вам провайдером и в моем примере клиент получил его 2001:828:105::/48. Последние 64 бита называются идентификатором интерфейса, и это эквивалентно части хоста в IPv4.
Это оставляет нас с 16 битами в середине, которые я могу использовать для создания подсетей. Если я хочу, я могу взять еще несколько битов из идентификатора интерфейса, чтобы создать еще больше подсетей, но в этом нет необходимости.
Используя 16 бит, мы можем создать 65.536 подсетей ...более чем достаточно для большинства из нас. И с 64 битами для идентификатора интерфейса на подсеть, мы можем иметь восемнадцать квинтиллионов, четыреста сорок шесть квадриллионов, семьсот сорок четыре триллиона, семьдесят четыре миллиарда, семьсот девять миллионов, пятьсот пятьдесят одну тысячу, шестьсот с чем-то хостов на подсеть. Этого должно быть более чем достаточно!
Использование 64-битного идентификатора интерфейса также очень удобно, потому что он сокращает ваш IPv6-адрес ровно наполовину!
Допустим, наш клиент с префиксом 2001: 828: 105:: / 48 хочет создать несколько подсетей для своей внутренней сети. Какие адреса мы можем использовать?
16 бит дает нам 4 шестнадцатеричных символа. Таким образом, все возможные комбинации, которые мы можем сделать с этими 4 символами, являются нашими возможными подсетями. Все, что находится между 0000 и FFFF, является допустимыми подсетями:
2001:828:105:0000::/64;
2001:828:105:0001::/64;
2001:828:105:0002::/64;
2001:828:105:0003::/64;
2001:828:105:0004::/64;
2001:828:105:0005::/64;
2001:828:105:0006::/64;
2001:828:105:0007::/64;
2001:828:105:0008::/64;
2001:828:105:0009::/64;
2001:828:105:000A::/64;
2001:828:105:000B::/64;
2001:828:105:000C::/64;
2001:828:105:000D::/64;
2001:828:105:000E::/64;
2001:828:105:000F::/64;
2001:828:105:0010::/64;
2001:828:105:0011::/64;
2001:828:105:0012::/64;
2001:828:105:0013::/64;
2001:828:105:0014::/64;
И так далее.
Всего существует 65 535 возможных подсетей, поэтому, к сожалению, я не могу добавить их все в статью...теперь мы можем назначить эти префиксы различным соединениям типа point-to-point, VLAN и т. д.
Аннотация. Развитие информационных технологий на сегодняшний день является важной задачей не только нашего государства, но и всего мира. Переход общества в информационную сферу деятельности уже давно стало очевидной ступенью в развитии человечества. Развитие информационных технологий каждой страны зависят от уровня экономики и наличие ресурсов каждой страны, но несмотря на то, что в России хорошо развиты данные направления, страна не является лидером в создании информационно-коммуникационных технологий. Российская федерация активно предпринимает меры по развитию данной сферы.
Ключевые слова: информационные технологии, цифровизация экономики РФ, индекс развития стран в сфере информационно-коммуникационных технологий.
Общество всегда стремилось к развитию. Развитию промышленности, науки и техники, это всегда было первоочередной задачей всего человечества. Такое развитие позволяло людям проще жить, работать, а главное, массово производить те блага, что требовались для населения. Каждая страна по своему развивалась из-за количества ресурсов, которые имеются на территории, а также уровня национальной экономики, что сильно влияло на развитие основных сфер агитирующих прогресс. В середине 20 века произошла научно-техническая революция, которая, в последствии, привила современное общество к развитию различных технологий, которые используются в повседневной жизни.
Современные информационные технологии во многом влияют на повседневную жизнь любого человека. ИТ используют для создания электронных рынков переводя все совершаемые платежи в информационную сферу, где можно отследить и проконтролировать оплаты. Также развитие информационных технологий влияет на создание дополнительных рабочих мест и переквалификацию существующего персонала, что напрямую связанно с сокращением безработицы. Информационные технологии расширили возможности в медицинской, образовательной, правоохранительной сферах, что позволило усовершенствовать деятельность каждого института.
В настоящее время каждое государство стремится нарастить темпы развития информационных технологий, инвестируя в различные компании, разрабатывающие различные новые идеи. Сейчас практически каждая государственная организация снабжена новейшими техническими средствами ля исполнения их должностных обязанностей, а государство продолжает создавать различные проекты для цифровизации экономики и других сфер.
Российской Федерации очень важна переориентация экономики на ИТ-рынок, так как половина доходов в государственный бюджет составляет сырьевой рынок, что неблагоприятно сказывается на экономике из-за резких скачков и падений нефтяных котировок. Информационные технологии для государственных органов власти были предусмотрены не только для эффективной и быстрой работы должностных лиц, но и для минимизации рисков совершения ошибки из-за человеческого фактора, а также для исключения личного контакта с физическими и юридическими лицами, что является инструментом для профилактики против коррупции. С помощью развития технологий бумажный документооборот стал минимальным, а скорость передачи информации увеличилась в разы не только внутри элементов одной структуры, но и между другими большими структурами называя это как межведомственное взаимодействие. Это позволяет синхронизировать работу различных ведомств для более эффективного исполнения своих должностных обязанностей.
В Российской Федерации уделяют большое внимание на развитие информационных технологий, понимая, что нельзя уступать европейским и азиатским странам в разработке различных технологий. Для того что бы достичь назначенных целей Правительство РФ в 2019-2024 гг. планирует выделить 1 837 696 млн. руб. (из них 1 099 589 млн. руб. из федерального бюджета) на развитие проекта "Цифровая экономика Российской Федерации". Это важный шаг для создания идеального информационного общества с отлаженной информационной системой. Но не смотря на финансирование государства, Российская Федерация все равно сильно отстает по развитию информационно - коммуникационных технологий в отличии от стран лидеров.
Только за один год по индексу развития ИКТ Россия спустилась с 43 места на 45, что не очень положительно сказывается на репутации страны. С другой же стороны можно сказать, что в практических навыках использования ИКТ Российская Федерация входит в двадцатку лучших по сравнению с другими странами мира (табл. 1).
Таблица 1. Индекс развития стран в сфере информационно-коммуникационных технологий 2017 (в сравнении с 2016)
Индекс развития ИКТ
В том числе субиндексы
Доступ к ИКТ
Использование ИКТ
Практические навыки использования ИКТ
Место в рейтинге
Значение
Место в рейтинге
Значение
Место в рейтинге
Значение
Место в рейтинге
Значение
Исландия
1(+1)
8,98
2(0)
9,38
5(0)
8,7
9(+11)
8,75
Республика Крорея
2(-1)
8,85
7(0)
8,85
4(0)
8,71
2(+1)
9,15
Швейцария
3(+1)
8,74
8(0)
8,85
2(+1)
8,88
31(0)
8,21
Дания
4(-1)
8,71
14(0)
8,39
1(0)
8,94
6(0)
8,87
Великобритания
5(0)
8,65
4(0)
9,15
7(+1)
8,38
33 (-4)
8,17
Россия
45 (-2)
7,07
50 (+4)
7,23
51 (-4)
6,13
13 (+1)
8,62
Словакия
46(1)
7,06
51(-1)
7,22
36(+4)
6,67
50(-5)
7,54
Италия
47(-1)
7,04
47(+1)
7,33
42(+1)
6,35
43(-2)
7,86
Поскольку сейчас приоритетной задачей стоит развитие цифровой экономики и различных программ по улучшению цифровой инфраструктуры и созданию информационного общества, у нашей страны есть все шансы выбиться в лидеры. Сегодня перспективы развития информационных технологий в России определяются "Стратегией развития отрасли информационных технологий в Российской Федерации на 2014 - 2020 годы и на перспективу до 2025", "Стратегией развития информационного общества в Российской Федерации на 2017 - 2030 годы", государственной программой Российской Федерации "Информационное общество (2011 - 2020 годы)"
Россия, в перспективе, может стать мировым лидером в области программирования, поскольку уже сейчас наши специалисты имеют определенную практику по работе с информационными технологиями, что также доказывают показатели из таблицы 1. Такой путь развития является достаточно перспективным для России, потому что способен стать основным ресурсом для поднятия национальной экономики вместо природных богатств страны.
Стоит отметить следующие направления развития информационных технологий:
беспроводной, широкополосный Интернет;
мультимедиа;
ликвидация компьютерной безграмотности;
мобильность;
робототехника.
Исходя из вышеперечисленных стратегий развития, предполагается, что к 2025 году 97% российских домохозяйств будут иметь широкополосный доступ в интернет (100 Мбит/с), а в больших городах созданы мобильные сети 5G.
Развитие и снабжения современными информационными технологиями недостаточно для развития цифровой экономики в России, необходимо создать собственные центры по разработки и исследований различных информационных технологий для того, чтобы повысить свою конкурентоспособность на мировом рынке в данной сфере. Для такой цели необходимо создать не только специализированные центры, но и также высококвалифицированных специалистов. Из этого выходит, что большинство высших учебных заведений будут расширять и создавать специализированные учебные программы и специальности в этом направлении или же создание отдельных институтов для обучения будущих ИТ-специалистов.
Также основное направление в развитии информационных технологий в России является развитие системы безопасности для защиты конфиденциальной и стратегически важной информации от разливных угроз извне. Приоритетные задачи государства являются обеспечение национальной и экономической безопасности, что в переходе на цифровую платформу стало причиной развития системы защиты от внешних угроз и утечки информации.
Кроме этого, в утвержденной программе "Цифровая экономика РФ" следует отметить, что еще одной важной задачей для России является укрепление своих позиций на мировом рынок по оказанию услуг по обработке и хранению данных. Согласно данному направлению в перспективе у Российской Федерации занять 10% долю рынка к 2025 году.
В дальнейшем программу планируется дополнить отраслевыми проектами, прежде всего в сфере здравоохранения, государственного управления, создания "умных городов".
Исходя из всего вышесказанного, можно сказать, в современном мире развитие информационных технологий очень важно не только для развития и поддержание мировой экономики, но и также для развития общества в целом. Важно понимать, что современные информационные технологии позволяют человечеству совершать и творить то, на что не были способны веками. Благодаря развитию новейших технических средств люди способны практически мгновенно обмениваться информацией, улучшая эффективность работы различных государственных служб. При этом минимизировать риски совершения ошибки, случаев коррупции или иных видов преступления. Позволяет отследить работу каждого сотрудника.
В настоящее время Российская Федерация активно предпринимает различные действия по развитию информационных технологий, наличие различных национальных программ подтверждают это. Смотря на 2017 год, можно сказать, что индекс по развитию информационно-коммуникационных технологий не так хорош, как ожидалось, но все же российские специалисты по использованию IT-технологий входят в двадцатку лучших, что дает шансы на дальнейшее развитие. Хотя России стоит решить еще много проблемных вопросов такие как: привлечение средств российских инвесторов для вложения средств в разработку отечественных информационных технологий, открытое конкурсное размещение госзаказов на новые информационные технологии при гарантиях государственных закупок и открытый конкурсный отбор при реализации государственных проектов информатизации.
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.