Динамическая маршрутизация. Протоколы и работа. Протокол BGP. Теория протоколов динамической маршрутизации
В любой науке есть стандартные обозначения, которые облегчают понимание идей. Например, в математике это умножение, деление, сложение и прочие символьные обозначения. Выражение (x + y * z) понять куда проще, чем «умножить y, с, z и прибавить к x». Представьте, до XVI века математика не имела символьных обозначений, все выражения прописывались словесно так, будто бы это художественный текст с описанием. А привычные для нас обозначения операций появились и того позже. Значение краткой символьной записи сложно переоценить. Исходя из таких соображений, в языки программирования были добавлены перегрузки операторов. Рассмотрим на примере.
Пример перегрузки операторов
Практически как и любой язык, C++ поддерживает множество операторов, работающих с типами данных, встроенными в стандарт языка. Но большинство программ используют пользовательские типы для решения тех или иных задач. Например, комплексная математика или реализуются в программе за счет представления комплексных чисел или матриц в виде пользовательских типов C++. Встроенные операторы не умеют распространять свою работу и совершать необходимые процедуры над пользовательскими классами, какими бы очевидными они не казались. Поэтому для сложения матриц, например, обычно создается отдельная функция. Очевидно, что вызов функции sum_matrix (A, B) в коде будет носить менее ясный характер, чем выражение A + B.
Рассмотрим примерный класс комплексных чисел:
//представим комплексное число в виде пары чисел с плавающей точкой. class complex { double re, im; public: complex (double r, double i) :re(r), im(i) {} //конструктор complex operator+(complex); //перегрузка сложения complex operator*(complex); //перегрузка умножения }; void main() { complex a{ 1, 2 }, b{ 3, 4 }, c{0, 0}; c = a + b; c = a.operator+(b); ////операторная функция может быть вызвана как любая функция, данная запись эквивалентна a+b c = a*b + complex(1, 3); //Выполняются обычные правила приоритета операций сложения и умножения }
Аналогичным образом можно сделать, например, перегрузку операторов ввода/вывода в C++ и приспособить их для вывода таких сложных структур как матрицы.
Операторы, доступные для перегрузки
Полный список всех операторов, для которых можно использовать механизм перегрузки:
Как видно из таблицы, перегрузка допустима для большинства операторов языка. Необходимости в перегрузке оператора быть не может. Это делается исключительно для удобства. Поэтому перегрузка операторов в Java, например, отсутствует. А теперь о следующем важном моменте.
Операторы, перегрузка которых запрещена
- Разрешение области видимости - «::»;
- Выбор члена - «.»;
- Выбор члена через указатель на член - «.*»;
- Тернарный условный оператор - «?:»;
- Оператор sizeof;
- Оператор typeid.
Правым операндом данных операторов является имя, а не значение. Поэтому разрешение их перегрузки могло бы привести к написанию множества неоднозначных конструкций и сильно усложнило бы жизнь программистов. Хотя есть множество языков программирования, в которых допускается перегрузка всех операторов - например, перегрузка
Ограничения
Ограничения перегрузки операторов:
- Нельзя изменить бинарный оператор на унарный и наоборот, как и нельзя добавить третий операнд.
- Нельзя создавать новые операторы помимо тех, что имеются. Данное ограничение способствует устранению множества неоднозначностей. Если есть необходимость в новом операторе, можно использовать для этих целей функцию, которая будет выполнять требуемое действие.
- Операторная функция может быть либо членом класса, либо иметь хотя бы один аргумент пользовательского типа. Исключением являются операторы new и delete. Такое правило запрещает изменять смысл выражений в случае, если они не содержат объектов типов, определенных пользователем. В частности, нельзя создать операторную функцию, которая работала бы исключительно с указателями или заставить оператор сложения работать как умножение. Исключением являются операторы "=", "&" и "," для объектов классов.
- Операторная функция с первым членом, принадлежащим к одному из встроенных типов данных языка C++, не может быть членом класса.
- Название любой операторной функции начинается с ключевого слова operator, за которым следует символьное обозначение самого оператора.
- Встроенные операторы определены таким образом, что между ними бывает связь. Например, следующие операторы эквивалентны друг другу: ++x; x + = 1; x = x + 1. После переопределения связь между ними не сохранится. О сохранении их совместной работы подобным образом с новыми типами программисту придется заботиться отдельно.
- Компилятор не умеет думать. Выражения z + 5 и 5 +z (где z - комплексное число) будут рассматриваться компилятором по-разному. Первое представляет собой «complex + число», а второе - «число + комплекс». Поэтому для каждого выражения нужно определить собственный оператор сложения.
- При поиске определения оператора компилятор не отдает преимущества ни функциям-членам класса, ни вспомогательным функциям, которые определяются вне класса. Для компилятора они равны.
Интерпретации бинарных и унарных операторов.
Бинарный оператор определяется как функция-член с одной переменной или как функция с двумя переменными. Для любого бинарного оператора @ в выражение a@b, @ справедливы конструкции:
a.operator@(b) или operator@(a, b).
Рассмотрим на примере класса комплексных чисел определение операций как членов класса и вспомогательных.
Class complex { double re, im; public: complex& operator+=(complex z); complex& operator*=(complex z); }; //вспомогательные функции complex operator+(complex z1, complex z2); complex operator+(complex z, double a);
Какой из операторов будет выбран, и будет ли вообще выбран, определяется внутренними механизмами языка, о которых речь пойдет ниже. Обычно это происходит по соответствию типов.
Выбор, описывать функцию как член класса или вне его - дело, в общем-то, вкуса. В примере выше принцип отбора был следующий: если операция изменяет левый операнд (например, a + = b), то записать ее внутри класса и использовать передачу переменной по адресу, для ее непосредственного изменения; если операция ничего не меняет и просто возвращает новое значение (например, a + b) - вынести за рамки определения класса.
Определение перегрузки унарных операторов в C++ происходит аналогичным образом, с той разницей, что они делятся на два вида:
- префиксный оператор, расположенный до операнда, - @a, например, ++i. o определяется как a.operator@() или operator@(aa);
- постфиксный оператор, расположенный после операнда, - b@, например, i++. o определяется как b.operator@(int) или operator@(b, int)
Точно так же, как и с бинарными операторами для случая, когда объявление оператора находится и в классе, и вне класса, выбор будет осуществляться механизмами C++.
Правила выбора оператора
Пусть бинарный оператор @ применяется к объектам x из класса X и y из класса Y. Правила для разрешения x@y будут следующие:
- если X представляет собой класс, искать внутри него определение оператора operator@ в качестве члена X, либо базового класса X;
- просмотреть контекст, в котором находится выражение x@y;
- если X относится к пространству имен N, искать объявление оператора в N;
- если Y относится к пространству имен M, искать объявление оператора в M.
В случае если в 1-4 было найдено несколько объявлений оператора operator@, выбор будет осуществляться по правилам разрешения перегруженных функций.
Поиск объявлений унарных операторов происходит точно таким же способом.
Уточненное определение класса complex
Теперь построим класс комплексных чисел более подробным образом, чтобы продемонстрировать ряд озвученных ранее правил.
Class complex { double re, im; public: complex& operator+=(complex z) { //работает с выражениями вида z1 += z2 re += z.re; im += z.im; return *this; } complex& operator+=(double a) { //работает с выражениями вида z1 += 5; re += a; return *this; } complex (): re(0), im(0) {} //конструктор для инициализации по умолчанию. Таким образом, все объявленные комплексные числа будут иметь начальные значения (0, 0) complex (double r): re(r), im(0) {} // конструктор делает возможным выражение вида complex z = 11; эквивалентная запись z = complex(11); complex (double r, double i): re(r), im(i) {} //конструктор }; complex operator+(complex z1, complex z2) { //работает с выражениями вида z1 + z2 complex res = z1; return res += z2; //использование оператора, определенного как функция-член } complex operator+(complex z, double a) { //обрабатывает выражения вида z+2 complex res = z; return res += a; } complex operator+(double a, complex z) { //обрабатывает выражения вида 7+z complex res = z; return res += a; } //…
Как видно из кода, перегрузка операторов имеет весьма сложный механизм, который может сильно разрастись. Однако такой детальный подход позволяет осуществлять перегрузку даже для очень сложных структур данных. Например, перегрузка операторов C++ в классе шаблонов.
Подобное создание функций для всех и вся может быть утомительным и приводить к ошибкам. Например, если добавить третий тип в рассмотренные функции, то нужно будет рассмотреть операции из соображений сочетания трех типов. Придется написать 3 функции с одним аргументом, 9 - с двумя и 27 - с тремя. Поэтому в ряде случаев реализация всех этих функций и значительное уменьшение их количества могут быть достигнуты за счет использования преобразования типов.
Особые операторы
Оператор индексации«» должен всегда определяться как член класса, так как сводит поведение объекта к массиву. При этом аргумент индексирования может быть любого типа, что позволяет создавать, например, ассоциативные массивы.
Оператор вызова функции «()» может рассматриваться как бинарная операция. Например, в конструкции «выражение(список выражений)» левым операндом бинарной операции () будет «выражение», а правым - список выражений. Функция operator()() должна быть членом класса.
Оператор последовательности «,» (запятая) вызывается для объектов, если рядом с ними есть запятая. Однако в перечислении аргументов функции оператор не участвует.
Оператор разыменования «->» также должен определяться в качестве члена функции. По своему смыслу его можно определить как унарный постфиксный оператор. При этом он в обязательном порядке должен возвращать либо ссылку, либо указатель, позволяющий обращаться к объекту.
Также определяется только в качестве члена класса из-за его связи с левым операндом.
Операторы присваивания «=», адреса «&» и последовательности «,» должны определяться в блоке public.
Итог
Перегрузка операторов помогает реализовать один из ключевых аспектов ООП о полиморфизме. Но важно понимать, что перегрузка - это не более чем иной способ вызова функций. Задача перегрузки операторов часто заключается в улучшении понимания кода, нежели в обеспечении выигрыша в каких-то вопросах.
И это еще не все. Также следует учитывать, что перегрузка операторов представляет собой сложный механизм с множеством подводных камней. Поэтому очень легко допустить ошибку. Это является основной причиной, по которой большинство программистов советуют воздержаться от использования перегрузки операторов и прибегать к ней только в крайнем случае и с полной уверенностью в своих действиях.
- Выполняйте перегрузку операторов только для имитации привычной записи. Для того чтобы сделать код более удобочитаемым. Если код становится сложнее по структуре или читабельности, следует отказаться от перегрузки операторов и использовать функции.
- Для больших операндов с целью экономии места используйте для передачи аргументы с типом константных ссылок.
- Оптимизируйте возвращаемые значения.
- Не трогайте операцию копирования, если она подходит для вашего класса.
- Если копирование по умолчанию не подходит, меняйте или явно запрещайте возможность копирования.
- Следует предпочитать функции-члены над функциями-нечленами в случаях, когда функции требуется доступ к представлению класса.
- Указывайте пространство имен и обозначайте связь функций с их классом.
- Используйте функции-нечлены для симметричных операторов.
- Используйте оператор () для индексов в многомерных массивах.
- С осторожностью используйте неявные преобразования.
Иногда хочется проявить творчество и облегчить программный код для себя и для других. Для себя написание, для других понимание. Скажем, если в нашей программе часто встречается функция добавления одной строки в конец другой, конечно, можно это реализовать разными способами. А если мы, в каком-то участке нашего кода, напишем, к примеру так:
Char str1 = "Hello "; char str2 = "world!"; str1 + str2;
и в результате получим строку «Hello world!». Правда, было бы замечательно? Ну так пожалуйста! Сегодня вы научитесь «объяснять» компьютеру, что оператором + вы хотите сложить не два числа, а две строки. И работа со строками — это один из самых удачных, на мой взгляд, примеров, чтобы начать разбираться с темой «Перегрузка операторов».
Приступим к практике. В этом примере мы перегрузим оператор + и заставим его к одной строке дописывать содержимое другой строки. А именно: мы соберем из четырех отдельных строк часть известного всем нам стиха А.С.Пушкина. Советую открыть вашу среду разработки и переписать этот пример. Если вам не все будет понятно в коде, не волнуйтесь, ниже будут приведены подробные объяснения.
#include
Разберемся:
Что-то новое в коде мы увидели в строке 16 void operator +(char*); Тут мы объявили прототип метода класса в котором перегрузим наш оператор + . Чтобы перегрузить оператор необходимо использовать зарезервированное слово operator . Выглядит это так, словно вы определяете обычную функцию: void operator+ () {//код} В теле этой функции мы размещаем код, который покажет компилятору, какие действия будет выполнять оператор + (или какой-либо другой оператор). Перегруженный оператор будет выполнять указанные для него действия только в пределах того класса, в котором он определен. Ниже, в строках 20 — 23 мы уже определяем какую роль будет играть + в нашем классе. А именно, с помощью функции strcat (str, s); он будет дописывать содержимое строки s , которую мы передали по указателю, в конец строки str . Строки 17, 25 — 28 это обычный метод класса, с помощью которого строка класса будет показана на экран. Если вам не понятно, как определять методы класса вне тела класса, т.е. такой момент как void StringsWork::getStr() {//определение} , то вам сначала желательно сходить сюда . Далее, уже в главной функции main() , в строках 34 — 37 ,создаем четыре указателя на строки и выделяем необходимое количество памяти для каждой из них, не забывая о том, что для символа "\0" так же надо зарезервировать одну ячейку char *str1 = new char ; . Затем копируем в них текст с помощью функции strcpy() и показываем их на экран — строки 39 — 47 . А в строке 49 создаем объект класса. При его создании сработает конструктор класса и строка класса будет очищена от лишних данных. Теперь нам остается только сложить строки в правильной последовательности, используя перегруженный оператор + — строки 50 — 53 и посмотреть, что получилось — строка 58 .
Результат работы программы:
1) У лукоморья дуб зелёный;
2) Всё ходит по цепи кругом;
3) И днём и ночью кот учёный
4) Златая цепь на дубе том:
========================================
Стих, после правильного сложения строк:
У лукоморья дуб зелёный;
Златая цепь на дубе том:
И днём и ночью кот учёный
Всё ходит по цепи кругом;
========================================
a = 5
b = 5
c = 5 + 5 = 10
Ограничения перегрузки операторов
- перегрузить можно практически любой оператор, за исключением следующих:
. точка (выбор элемента класса);
* звездочка (определение или разыменование указателя);
:: двойное двоеточие (область видимости метода);
?: знак вопроса с двоеточием (тернарный оператор сравнения);
# диез (символ препроцессора);
## двойной диез (символ препроцессора);
sizeof оператор нахождения размера объекта в байтах;
- с помощью перегрузки невозможно создавать новые символы для операций;
- перегрузка операторов не изменяет порядок выполнения операций и их приоритет;
- унарный оператор не может использоваться для переопределения бинарной операции так же, как и бинарный оператор не переопределит унарную операцию.
Не забывайте, что в программировании очень желательно, делать все возможное, чтобы ваш код был как можно более понятным. Этот принцип касается всего: названий, которые вы даете переменным, функциям, структурам, классам, также и тех действий, которые будет выполнять перегруженный оператор. Старайтесь определять эти действия, как можно ближе к логическому значению операторов. Например + для сложения строк или других объектов класса, - для удаления строки и т.д.
Нельзя не отметить, что многие программисты негативно относятся к перегрузке операторов. Сама возможность перегрузки операторов предоставлена для облегчения понимания и читаемости кода программ. В то же время, она наоборот может стать и причиной усложнения вашей программы и многим программистам будет тяжело ее понять. Помните о «золотой середине» и используйте перегрузку только тогда, когда она реально принесет пользу вам и другим. Вполне можно обойтись и без перегрузки операторов. Но это не значит, что можно проигнорировать данную тему. В ней следует разобраться хотя бы потому, что вам когда-то придется столкнуться с перегрузкой в чужом коде и вы сможете легко разобраться что к чему.
Вот мы очень коротко ознакомились с перегрузкой операторов в С++. Увидели, так сказать, вершину айсберга. А вашим домашним заданием (ДА-ДА — ДОМАШНИМ ЗАДАНИЕМ!) будет доработать программу, добавив в нее перегрузку оператора для удаления строки. Какой оператор перегружать выберите сами. Либо предложите свой вариант апгрейда кода, добавив в него то, что посчитаете нужным и интересным. Ваши «труды» можете добавлять в комментарии к этой статье. Нам интересно будет посмотреть ваши варианты решения. Удачи!
Рисунок 3.4 – Автономная система и домен маршрутизации
Автономная система (autonomous system, AS) – это набор сетей, которые находятся под единым административным управлением и в которых используются единая стратегия и правила маршрутизации. Автономная система для внешних сетей представляется как некий единый объект.
Домен маршрутизации – это совокупность сетей и маршрутизаторов, использующих один и тот же протокол маршрутизации.
В сети Интернет термин автономная система используется для описания крупных логически объединенных сетей, например сетей Internet провайдеров. Каждая такая AS имеет в качестве своего идентификатора шестна- дцати-битовое число. Для публичных сетей Internet провайдеров номер AS выдает и регистрирует Американский реестр Internet номеров (American Registry of Internet Numbers – ARIN), согласно RFC 2270 для частных AS выделен диапазон номеров 64512 – 65534, автономная система 65535 зарезервирована под служебные задачи.
Протоколы маршрутизации делятся на две категории: внутренние (Interior) и внешние (Exterior).
3.2.2 IGP – протоколы внутреннего шлюза
Внутренние протоколы имеют общее название IGP (Interior Gateway Protocol, протоколы внутреннего шлюза). К ним относятся любой протокол маршрутизации, используемый исключительно внутри автономной системы, к таким протоколам относятся, например RIP, EIGRP и OSPF. Каждый IGP протокол представляет один домен маршрутизации внутри AS. В пределах автономной системы может существовать множество IGP доменов (Рисунок 3.5).
Граничный |
|
маршрутизации | маршрутизатор |
Рисунок 3.5 – Домены маршрутизации внутри AS
Маршрутизаторы, поддерживающие один и тот же протокол IGP обмениваются информацией друг с другом в пределах домена маршрутизации. Маршрутизаторы, работающие более чем с одним протоколом IGP, например, использующие протоколы RIP и OSPF, являются участниками двух отдельным доменов маршрутизации. Такие маршрутизаторы называются граничными.
3.2.3 EGP – протоколы внешнего шлюза
Внешние протоколы – EGP (Exterior Gateway Protocol протоколы внешнего шлюза) – это протоколы маршрутизации, обеспечивающие маршрутизацию между различными автономными системами. Протокол BGP (Border Gateway Protocol, протокол пограничного шлюза) является одним из наиболее
Маршрутизация (англ. Routing) - процесс определения маршрута следования информации в сетях связи.
Протокол маршрутизации - сетевой протокол, используемый маршрутизаторами для определения возможных маршрутов следования данных в составной компьютерной сети. Применение протокола маршрутизации позволяет избежать ручного ввода всех допустимых маршрутов, что, в свою очередь, снижает количество ошибок, обеспечивает согласованность действий всех маршрутизаторов в сети и облегчает труд администраторов.
IP-Маршрутизация – процесс выбора пути для передачи пакета в сети. Под путем (маршрутом) понимается последовательность маршрутизаторов, через которые проходит пакет по пути к узлу-назначению. IP-маршрутизатор – это специальное устройство, предназначенное для объединения сетей и обеспечивающее определение пути прохождения пакетов в составной сети. Маршрутизатор должен иметь несколько IP-адресов с номерами сетей, соответствующими номерам объединяемых сетей.
Маршрутизация осуществляется на узле-отправителе в момент отправки IP-пакета, а затем на IP-маршрутизаторах.
В качестве IP-маршрутизатора может быть использован компьютер, системное программное обеспечение которого позволяет осуществлять IP-маршрутизацию. В частности, маршрутизатор можно организовать на базе компьютера под управлением любой из операционных систем семейства Microsoft Windows 2000 Server.
Для каждой автономной системы выбирается собственный протокол маршрутизации, с помощью которого осуществляется взаимодействие между маршрутизаторами в этой автономной системе. Такой протокол называется протоколом внутренних маршрутизаторов (IGP - interior gateway protocol) или протоколом внутридоменной маршрутизации (intradomain routing protocol). Наиболее популярный IGP - это протокол обмена информацией о маршрутизации (RIP - Routing Information Protocol). Более новый IGP это протокол Open Shortest Path First (OSPF). Он был разработан как замена для RIP.
OSPF(англ. Open Shortest Path First) - протокол динамической маршрутизации, основанный на технологии отслеживания состояния канала (link-state technology) и использующий для нахождения кратчайшего пути алгоритм Дейкстры. Протокол OSPF был разработан IETF в 1988 году.
Протокол OSPF представляет собой протокол внутреннего шлюза (Interior Gateway Protocol - IGP). Протокол OSPF распространяет информацию о доступных маршрутах между маршрутизаторами одной автономной системы.
OSPF имеет следующие преимущества:
· Высокая скорость сходимости по сравнению с дистанционно-векторными протоколами маршрутизации;
· Поддержка сетевых масок переменной длины (VLSM);
· Оптимальное использование пропускной способности с построением дерева кратчайших путей;
BGP (англ. Border Gateway Protocol, протокол граничного шлюза) - основной протокол динамической маршрутизации в Интернете.
Протокол BGP предназначен для обмена информацией о достижимости подсетей между автономными системами (АС), то есть группами маршрутизаторов под единым техническим управлением, использующими протокол внутридоменной маршрутизации для определения маршрутов внутри себя и протокол междоменной маршрутизации для определения маршрутов доставки пакетов в другие АС. Передаваемая информация включает в себя список АС, к которым имеется доступ через данную систему. Выбор наилучших маршрутов осуществляет исходя из правил, принятых в сети.
BGP поддерживает бесклассовую адресацию и использует суммирование маршрутов для уменьшения таблиц маршрутизации. С 1994 года действует четвёртая версия протокола, все предыдущие версии являются устаревшими.
BGP, наряду с DNS, является одним из главных механизмов, обеспечивающих функционирование Интернета.