По вашему запросу ничего не найдено :(
Убедитесь, что запрос написан правильно, или посмотрите другие
наши статьи:
У облачного провайдера нам необходимо арендовать пул виртуальных серверов для создания на его основе облачного аналога перечисленной серверной части сети. К организованной облачной виртуальной инфраструктуре будут иметь доступ все отделения организации посредством VPN-туннелей.
Все виртуальные машины создаются посредством гипервизора. Аналогичным образом виртуальные машины могут быть созданы и в обычной сети, но также могут использоваться и отдельные физические серверы. Для облачных же услуг технология виртуализации является основополагающей, поэтому в этом разделе подробнее будет рассмотрена технология виртуализации.
В данном случае для организации собственных виртуальных серверов мы пользуемся услугами IaaS (чаще всего в списке услуг именуется как
"аренда виртуальных серверов" или похожим образом). Но для организации серверов для, например, корпоративной почты или базы данных можно воспользоваться уже готовыми PaaS и SaaS-решениями, которые предлагаются некоторыми облачными провайдерами.
При организации облачной инфраструктуры для крупной организации имеет смысл строить частное облако. Даже пусть оно иногда не будет покрывать все потребности организации и периодически придется превращать его в гибридное. Крупным компаниям нужна не столько экономия, столько полный контроль над обрабатываемыми данными - чтобы конфиденциальные данные не вышли за пределы компаний.
Для небольших и средних организаций можно создать облачную инфраструктуру на базе публичного облака. Если компания только начинает свою деятельность, нет смысла покупать физические серверы - можно сразу
арендовать виртуальные и сэкономить средства, которые можно потратить с большей пользой.
Перевод в облако сразу всей инфраструктуры обусловлен еще и взаимосвязями между серверами и скоростью обмена данными между ними. Поэтому следует учитывать взаимосвязь серверов между собой и тот факт, что из любого офиса теперь скорость скачивания файла из того же облачного хранилища будет ограничиваться максимальной скоростью на сетях интернет-провайдера, однако обмен данными в сетях облачного провайдера будет гораздо выше в силу специализированности построенной сети ЦОД.
Виртуальные машины
Гипервизор - это программное или микропрограммное обеспечение, позволяющее виртуализировать системные ресурсы. Виртуальные машины в гипервизоре логически отделены друг от друга и не привязаны к аппаратному обеспечению, поэтому вирусы и ошибки на одной виртуальной машине никак не влияют на другие на том же гипервизоре и на аппаратную часть сервера, и могут быть легко перемещены с одного сервера на другой. Гипервизор по своей сути аналогичен операционной системе.
Существуют 2 типа гипервизоров: гипервизор 1-го типа устанавливается поверх аппаратной части оборудования, 2-й тип устанавливается поверх операционной системы, а также гибридные.
В таблице 1 приведены некоторые примеры гипервизоров.
Таблица 1 Примеры гипервизоров
Гипервизор
Тип
Требуемые ОС для установки
Гостевые ОС
KVM
2
Linux, FreeBSD, illumos
FreeBSD, Linux, Solaris, Windows, Plan 9
VMware:
ESX Server
1
Не требует ОС
Windows, Linux, Solaris, FreeBSD, OSx86 (as FreeBSD), virtual appliances, Netware, OS/2, SCO,
BeOS, Haiku, Darwin, others: runs arbitrary OS
ESXi Server
1
Не требует ОС
Fusion
2
macOS
Server
2
Windows, Linux
Workstation
2
Windows, Linux
VMware ESXi (vSphere)
1
No host OS
Same as VMware ESX Server
Microsoft Hyper-V
Hyper-V
2
Windows
FreeBSD, Linux
(SUSE 10, RHEL 6, CentOS 6)
Hyper-V Server
1
Не требует ОС
Xen
гиб- рид
GNU/Liux, Unix-like
GNU/Linux, FreeBSD, MiniOS, NetBSD, Solaris, Windows 7/XP/Vista/Server 2008 (requires Intel VT-x (Vanderpool) or AMD-V (Pacifica)-capable CPU), Plan 9
VirtualBox
2
Windows, Linux, macOS, Solaris, FreeBSD, eComStation
DOS, Linux, macOS, FreeBSD, Haiku, OS/2, Solaris,
Syllable, Windows, and OpenBSD (with Intel VT-x or AMD-V
PowerVM
?
PowerVM Firmware
Linux PowerPC, x86; AIX, IBM i
Таким образом при проектировании корпоративной сети с помощью виртуальных серверов, следует заранее определиться с типом виртуальной
машины и совместимых с ней операционных систем. Для облачных виртуальных серверов достаточно учитывать совместимые гостевые ОС, обеспечение работоспособности физических серверов и гипервизора берет на себя облачный провайдер.
Создание виртуальной машины или виртуальной сети
Для переноса элементов корпоративной сети в облако необходимо арендовать у облачного провайдера один или несколько виртуальных серверов, на которых будут развернуты необходимые нам системы. Часто достаточно обойтись моделью предоставления услуги VPS/VDS, описанной в разделе 2, арендовав несколько виртуальных серверов для каждого элемента инфраструктуры.
Готовая виртуальная машина (ВМ) на сервере, по сути, будет представлять из себя два файла: файл конфигурации аппаратной части машины и образ диска этой машины, предназначенный для размещения в нем операционной системы. На диске ВМ помимо ОС размещается все программное обеспечение и файлы пользователей. Оба файла, а значит и вся ВМ целиком, могут быть без особых сложностей перенесены или дублированы с одного гипервизора и сервера на другой, что позволяет гибко распределять серверные ресурсы, создавать и восстанавливать резервные копии данных пользователей, а также помогать в процессе миграции на облачную инфраструктуру с уже заранее заготовленными образами систем.
Для создания виртуальной машины на сайте почти любого облачного провайдера можно найти параметры конфигурации и "ползунки" для точной настройки вычислительных ресурсов арендуемой виртуальной машины, подобрав все параметры под цели и задачи сервера. Либо же можно воспользоваться "кейсами" - готовыми наборами настроек. А также часто клиентам предлагаются услуги тестирования, платного или бесплатного,
арендуемого сервера, чтобы оценить его возможности и соответствие требованиям.
Примеры параметров настройки виртуального сервера приведены на рисунке 1. В первом случае идет выбор именно ресурсов сервера, для дальнейшего развертывания на нем "целого парка виртуальных машин". Во втором случае настраивается конкретно виртуальный сервер данный вариант хорошо подойдет.
Разворачивание частного облака позволяет создать и настроить необходимое количество виртуальных машин со своими приложениями, но организация и сопровождение такой структуры будет требовать больших затрат по сравнению с выделенным сервером.
После создания виртуального сервера на рабочем столе рабочей станции появляется значок подключения к виртуальному серверу.
Далее рассмотрим подробнее облачные решения для необходимых нам серверных структур.
Терминальный сервер
Как уже было упомянуто в разделе 1, терминальный сервер будет представлять собой сервер с заранее установленным на него приложением для удаленной работы с ним посредством "тонкого клиента". Например, такая возможность будет востребована при групповой работе с 1С. В таком случае сервер должен быть связан с сервером базы данных. Это означает, что клиенты подключаются к серверу приложения, а сервер приложения взаимодействует с сервером базы данных. Оба сервера должны находиться в облаке, чтобы между ними была хорошая связь.
К терминальному серверу приложений сотрудники могут осуществлять подключение посредством протокола RDP.
К приложению (1С, например) может быть организован доступ посредством публикации базы через web-сервер и, соответственно, работой с web-интерфейсом 1С, подключением с помощью "тонкого" или "толстого" клиента 1С или же подключением ко всему серверу терминалов по протоколам удаленного доступа (RDP и другие).
Файловый сервер
По сути, работа с файловым сервером в облаке ничем не отличается от того, если бы он был в локальной сети. Подключение к файловому серверу обычно осуществляется через протокол FTP (File Transport Protocol) с помощью файлового проводника.
Однако следует тщательно взвесить решение о переносе файлового сервера в облако, т.к. объем данных при сообщении с сервером может сильно повлиять на тарифы услуг Интернет.
Почтовый сервер
В качестве почтового сервера, согласно перечню облачных сервисов, представленному в разделе 2, чаще всего облачные провайдеры используют Microsoft Exchange Server. Он является одним из самых распространенных ПО для корпоративной почты.
Подключение к почтовому серверу может осуществляться аналогично другим терминальный приложениям: web, клиенты или удаленный доступ.
Также требует доступа к базам данных
Виртуальное рабочее место
VDI или виртуальное рабочее место позволяет сотрудникам организации использовать рабочую станцию с любой конфигурацией для работы из любого места и в любое время.
Для подключения к VDI чаще всего используется специальное клиентское ПО, или же иногда это может осуществляться из браузера.
Web-сервер
Формально web-приложение также должно быть соединено c сервером базы данных и может быть разбито на 3 части:
исполняемый модуль на стороне браузера клиента;
исполняемый модуль на стороне сервера;
база данных.
База данных представляет собой систематизированный набор данных для сетей и пользователей и управляемый посредством системы управления базами данных (СУБД). Пример СУБД MySQL.
Сервер печати
Следует учесть, что сервер печати однозначно не требует переноса в облако, т.к. выполняет задачу сообщения с офисным оборудованием, таким как принтеры и факсы.
Конфигурация сервера
Развертывание терминального сервера, а в частности внедрение продуктов 1С одна из самых распространенных задач системны администраторов. И подбор серверной аппаратной конфигурации под данную задачу может служить хорошим примером требований серверных систем к техническим параметрам оборудования.
Рассмотрим несколько вариантов организации и аппаратной конфигураций для развертывания 1С сервера с базой данных.
Можно предложить 3 варианта:
Один сервер с файловой 1С;
Один сервер с виртуальными машинами 1С и БД;
Два физических сервера: один терминальный 1С, второй с БД.
В первом случае будет организован терминальный сервер, на котором будет использоваться файловая версия 1С, таким образом БД будет находиться в файловой системе самого сервера вместе с программой 1С. Для большого количества пользователей разработчик рекомендует использовать систему "клиент-сервер". Организовать терминальный сервер, сервер БД и сервер 1С на одной операционной системе все равно можно, но это будет подвергать сомнению стабильность и информационную безопасность такой системы.
Во втором случае как раз-таки и используется такая система, но оба сервера будут виртуальными на одном физическом. Данный вариант и используется в облачной инфраструктуре. Первый сервер будет содержать серверную часть 1С, второй базу данных.
В третьем случае будут отдельно использоваться два сервера, а базы данных и программа будут разделены.
Для конфигурации общего терминального сервера с двумя виртуальными машинами с расчетом работы примерно на 50 человек должно хватить следующей конфигурации:
10 ядер центрального процессора:
по 6-8 терминальных сессий на одно ядро примерно 8 ядер,
1-2 ядра на базу данных,
дополнительно еще запас, но для облачных серверов можно в любой момент докупить дополнительную вычислительную мощность;
64 Гб оперативной памяти:
операционная система (например, Windows Server) 2 Гб
база данных 4-6 Гб
сервер 1С 2-4 Гб
примерно 700 Мб на каждого пользователя 35 Гб
SSD (для быстрых операций) и SAS (для хранения) память данных в условиях облачной инфраструктуры выбор дисковой подсистемы сводится к выбору конкретного типа дисков и их объемов: быстрых твердотельных накопителей (SSD) для быстрых операций чтения/записи и/или более медленных, но вместительных жестких дисков жестких дисков с интерфейсов SAS, подходящих для хранения баз данных.
Подключение к облаку
Для подключения сотрудников к корпоративному облаку могут применяться комбинации сразу нескольких решений, каждое из которых более детально рассмотрено в таблице 2.
Таблица 2 Способы подключения к инфраструктуре в облаке
Способ подключения
Назначение
Требования со стороны сервера
Требования со стороны клиента
Веб-доступ
Доступ к сайту, расположенному на web-сервере через протокол HTTP/HTTPS
Наличие выделенного терминального сервера + служба TS Web Access
Использование адреса сайта для доступа к ресурсу с помощью браузера
RDP
Доступ к виртуальным серверам
Наличие выделенного терминального сервера
Запуск клиента
RDP
RemoteApp
Доступ к терминальным сессиям
Наличие конфигурационног о файла со списком программ, имеющим доступ к приложению
Запуск сконфигурированного rdp-файла или иконки приложения для подключения к приложению по RDP
Remote access VPN
Подключение каждого пользователя к серверу через VPN-туннель
Наличие сконфигурированного VPN- устройства/сервера.
Запуск ярлыка для подключения к VPN-серверу.
Продолжение таблицы 2
VPN site-to-site
Подключение офиса к серверу через VPN- туннель
Наличие двух сконфигурированных VPN-серверов. Пример: VPN-сервер в компании и VPN- сервер в облаке.
Отсутствие необходимости создания и запуска ярлыка VPN- подключения.
Обращение к ресурсам филиала / центрального офиса / облака напрямую. При обращении к
ресурсам VPN- подключение организуется автоматически на уровне серверов.
DirectAccess
Автоматическая установка связи со всей корпоративной сетью сразу
Наличие одного или более серверов DirectAccess в составе домена. Наличие центра сертификации (PKI). Windows - инфраструктура.
Только Windows
Компьютер клиента должен входить в состав домена.
Отсутствие необходимости в создании и запуске ярлыка подключения.
VDI
Доступ к отдельному виртуальному рабочему месту
Развернутая инфраструктура виртуальных рабочих столов VDI
Пользователь получает свой собственный виртуальный рабочий стол, к которому можно подключаться с помощью тонкого клиента с любой рабочей станции.
Выбор каждого конкретного способа подключения может зависеть от потребностей пользователей, что будет быстрее и удобнее для работы.
Облачная инфраструктура корпоративной сети
Теперь мы можем составить схему облачной инфраструктуры корпоративной сети. Это будет модифицированная схема из раздела 1. Схема представлена на рисунке:
JSON (JavaScript Object Notation – нотация объектов JavaScript) – это популярный способ структурирования данных. Он используется для обмена информацией между веб-приложением и сервером. Но как прочитать файл JSON в Python?
В этой статье я покажу вам, как использовать методы json.loads() и json.load() для интерпретации (или как еще говорят парсинга) и чтения файлов и строк JSON.
Синтаксис JSON
Прежде чем мы приступим к интерпретации и чтению файла JSON, сначала нам нужно разобраться с основным синтаксисом. Подробнее про JSON можно почитать в этой статье. Синтаксис JSON выглядит как объектный литерал JavaScript с парами ключ-значение.
Вот пример данных JSON с данными организации:
{
"organization": "Company 1",
"website": "https://www.website.org/",
"formed": 2014,
"certifications": [
{
"name": "Responsive Web Design",
"courses": [
"HTML",
"CSS"
]
},
{
"name": "JavaScript Algorithms and Data Structures",
"courses": [
"JavaScript"
]
},
{
"name": "Front End Development Libraries",
"courses": [
"Bootstrap",
"jQuery",
"Sass",
"React",
"Redux"
]
},
{
"name": "Data Visualization",
"courses": [
"D3"
]
},
{
"name": "Relational Database Course",
"courses": [
"Linux",
"SQL",
"PostgreSQL",
"Bash Scripting",
"Git and GitHub",
"Nano"
]
},
{
"name": "Back End Development and APIs",
"courses": [
"MongoDB",
"Express",
"Node",
"NPM"
]
},
{
"name": "Quality Assurance",
"courses": [
"Testing with Chai",
"Express",
"Node"
]
},
{
"name": "Scientific Computing with Python",
"courses": [
"Python"
]
},
{
"name": "Data Analysis with Python",
"courses": [
"Numpy",
"Pandas",
"Matplotlib",
"Seaborn"
]
},
{
"name": "Information Security",
"courses": [
"HelmetJS"
]
},
{
"name": "Machine Learning with Python",
"courses": [
"Machine Learning",
"TensorFlow"
]
}
]
}
Как парсить строки JSON в Python
Python имеет встроенный модуль, который позволяет работать с данными в формате JSON. Вам необходимо будет импортировать модуль json.
import json
Если вам необходимо проинтерпретировать строку JSON, возвращающую словарь, то вы можете воспользоваться методом json.loads().
import json
# assigns a JSON string to a variable called jess
jess = '{"name": "Jessica Wilkins", "hobbies": ["music", "watching TV", "hanging out with friends"]}'
# parses the data and assigns it to a variable called jess_dict
jess_dict = json.loads(jess)
# Printed output: {"name": "Jessica Wilkins", "hobbies": ["music", "watching TV", "hanging out with friends"]}
print(jess_dict)
Как парсить и читать файлы JSON в Python
В данном примере мы имеем файл в формате JSON с именем fcc.json, который содержит те же данные, что и ранее, касающиеся курсов, которые предлагает сайт.
Если вы хотите прочитать этот файл, то для начала вам нужно использовать встроенную в Python функцию open() с режимом чтения. Мы используем ключевое слово with, чтобы убедиться, что файл закрыт.
with open('fcc.json', 'r') as fcc_file:
Если файл не может быть открыт, то мы получим ошибку OSError. Это пример ошибки "FileNotFoundError" при опечатке в имени файла fcc.json.
Затем мы можем проинтерпретировать файл, используя метод json.load() и присвоить его переменной с именем fcc_data.
fcc_data = json.load(fcc_file)
И в конце мы должны напечатать результат.
print(fcc_data)
Вот так будет выглядеть полный код:
import json
with open('fcc.json', 'r') as fcc_file:
fcc_data = json.load(fcc_file)
print(fcc_data)
Как красиво напечатать данные JSON в Python
Если мы посмотрим на то, как печатаются данные, то увидим, что все данные JSON печатаются в одной строке.
Однако такой формат вывода может быть затруднительным для чтения. И чтобы это исправить, мы можем реализовать метод json.dumps() с параметром indent (отступ).
В данном примере мы сделаем отступ в 4 пробела и будем печатать данные в более удобном для чтения формате.
print(json.dumps(fcc_data, indent=4))
Также мы можем отсортировать ключи в алфавитном порядке, используя параметр sort_keys и установив его значение на True.
print(json.dumps(fcc_data, indent=4, sort_keys=True))
Заключение
JSON – это популярный способ структурирования данных, который используется для обмена информацией между веб-приложением и сервером.
Если вам необходимо проинтерпретировать строку JSON, которая возвращает словарь, то вы можете использовать метод json.loads().
Если вам необходимо проинтерпретировать файл JSON, который возвращает словарь, то вы можете использовать метод json.load().
Первая часть тут.
Вектор пути основан на хранении списка узлов, через которые проходит путь. Любой узел, который получает обновление с самим собой в пути, просто отбрасывает обновление, поскольку это не жизнеспособный путь. Рисунок 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 образуют непересекающиеся топологии.
Двусторонняя связь
В этой и предыдущей лекциях было описано несколько различных способов вычисления пути без петель (или набора непересекающихся путей) через сеть. В каждом из этих случаев вычисленный путь является однонаправленным - от корня дерева до краев или достижимых мест назначения. Фактически, обратного пути не существует. Другими словами, источник может иметь возможность достичь пункта назначения по пути без петель, но может не быть обратного пути от пункта назначения к источнику. Это может быть необычный режим отказа в некоторых типах каналов, результат фильтрации информации о доступности или ряд других ситуаций в сети.
Примечание. Двусторонняя связь не всегда нужна. Рассмотрим, например, случай с подводной лодкой, которая должна получать информацию о своей текущей задаче, но не может передавать какую-либо информацию, не раскрывая своего текущего местоположения. Желательна возможность отправлять пакеты устройствам, расположенным на подводной лодке, даже если к ним нет двусторонней связи. Плоскости управления должны быть модифицированы или специально спроектированы для обработки такого необычного случая, поскольку обычно для правильной работы сети требуется двустороннее соединение.
Еще одна проблема, с которой должны столкнуться плоскости управления в области вычислительных трактов, - это обеспечение сквозной двусторонней связи.
Уровень управления может решить эту проблему несколькими способами:
Некоторые плоскости управления просто игнорируют эту проблему, что означает, что они предполагают, что какой-то другой протокол, например транспортный протокол, обнаружит это состояние.
Плоскость управления может проверить наличие этой проблемы во время расчета маршрута. Например, при вычислении маршрутов с использованием алгоритма Дейкстры можно выполнить проверку обратной связи при вычислении путей без петель. Выполнение этой проверки обратной линии связи на каждом этапе вычислений может гарантировать наличие двусторонней связи.
Плоскость управления может предполагать двустороннюю связь между соседями, обеспечивая сквозную двустороннюю связь. Плоскости управления, которые выполняют явные проверки двусторонней связи для каждого соседа, могут (как правило) безопасно предполагать, что любой путь через этих соседей также поддерживает двустороннюю связь.