Тема 14.

Маршрутизация със следене състоянието на връзката.


страницата се нуждае от дописване/преглеждане


Първите динамични маршрутни протоколи използват метода на дистантния вектор. С течение на времето и нарастването на рутираните мрежи, в частност - интернет, започват да се открояват техните недостатъци. Започва разработката на следващи поколения distance vector протоколи, но същевременно се разработва и изцяло нов клас маршрутни протоколи, следящи състоянието на връзката (link state).

Link state протоколите, за разлика от distance vector, строят в паметта си цялостна карта на графа от рутъри. По нея те прилагат алгоритъма на Dijkstra, за да изчислят дърво на най-късите пътища, с което после попълват маршрутната си таблица. За да се постигне това, е нужно всеки рутър да съдържа една и съща актуална карта, в която възможно най-бързо да се отразяват промените в състоянието на връзките, а съответно - и на маршрутите. Това те постигат чрез малки пакети, съдържащи състоянието на конкретна връзка (връзки), които се разпращат моментално при промяна на нейното състояние. Ако за distance vector протоколите е подходящо сравнението с навигация по пътни табели, то за link state може да се каже, че тяхната работа прилича на навигация по пътна карта - на нея са указани всички налични пътища с техните цени (дължини), а наблюдаващият картата си избира този път, който счита за оптимален.

Link state пакет

Основен момент в работата на един link state протокол е пакетът, носещ информацията за състоянието на връзката. Чрез такива пакети рутърите си обменят информация за своите непосредствени съседи и връзките си с тях. След употреба пакетите биват разпращани моментално до останалите съседи на рутъра, спазвайки правилото split horizon. Сравнително малките размери на пакетите позволяват при това наводнение мрежовата натовареност да остане в поносими граници.
routergraph.png
За тази позната конфигурация, пакет със състояние на връзките, изпратен от рутър J, би могъл да има следния вид:

ID на изпращащия рутър (J)
Пореден номер (sequence number)
Възраст на пакета (age)
A 8
I 10
H 12
K 16
  • ID - уникален идентификатор на рутъра в графа (или областта на действие на протокола)
  • Sequence number - служи за различаване на новите ъпдейти, пуснати от J, от старите, които може би още циркулират из мрежата.
  • Age - указва преди колко време пакетът е пуснат в обръщение, увеличава се при всяко следващо предаване. Ако нещо се случи на J и той излезе временно от строя, при връщането си, Sequence Number на новите му пакети ще е по-малко от това на старите, пуснати преди отпадането му. По възрастта обаче рутърите ще изберат най-новите пакети.
  • Списък от двойки съсед - метрика.

Стъпки при работата на link state протокол

Протоколите със следене състоянието на връзката изпълняват 5 основни стъпки.

  1. Уточняване на съседите. Рутърът открива своите съседи, свързани към неговите активни интерфейси.
  2. Измерване на състоянието (метриката). Чрез Hello пакети се измерва времето за пътуване на пакета, и по специфичен за протокола метод се определя метриката.
  3. Конструиране на link state пакет. Директните съседи се попълват в картата на графа и в маршрутната таблица, след което картата се копира в един или няколко пакета, предназначени за съседите на рутъра.
  4. Flooding. Готовият пакет се разпраща до всички съседи на рутъра, спазвайки правилото на разделения хоризонт.
  5. Събиране на пакети. Известно време протоколът слуша за изпратени link state пакети, които копира и препредава. След това върху събраната информация се прилага алгоритъмът на Dijkstra. Най-добрите маршрути се записват в маршрутната таблица.

Части от нещата, изброени по-долу, са специфични за протокола OSPF.

Уточняване на съседите

Чрез обмяна на специални съобщения, рутърът открива други рутъри, към които има директна свързаност в съответния локален сегмент (обикновено, всеки негов интерфейс се намира в различен локален сегмент). След това той пристъпва към оформяне на съседства (adjacencies). Ако в един локален сегмент има повече от два рутъра - тоест, връзката не е point-to-point - се избира designated router. Той представя рутърите в сегмента - оформя съседства, от тяхно име, получава предназначените за тях link state пакети и им ги препраща, получава изпращаните от тях пакети и ги подава на външния свят. По този начин се намалява потокът от служебни пакети, които наводняват връзката.

Измерване

С изпращане на Hello пакети се измерва времето за получаване на отговор (round-trip time), което служи за определяне на метриката. Различните протоколи ползват различни фактори за изчисляване на метриката, като скорост на връзката (bandwidth), закъснение (delay), натоварване (load).
Често първата и втората фаза се извършват едновременно.

Link state пакет

Нека мрежата да изглежда така (учебникарска конфигурация):
hexagon.png
В този момент на рутърите са известни само директните им съседи. По тази информация се конструират следните пакети:

A B C D E F
Seq Seq Seq Seq Seq Seq
Age Age Age Age Age Age
B 4 A 4 B 2 C 3 A 5 B 6
E 5 C 2 D 3 F 7 C 1 D 7
F 6 E 1 F 8 E 8

Flooding

След като пакетът е готов, възниква въпросът - какво да се прави с него? Начините за разпращане са няколко. Първият е подобен на distance vector: през определен интервал от време, да се разпращат пакетите. Това, обаче, натоварва комуникационната мрежа. Затова най-често работи вторият механизъм: triggered updates - пакети с ъпдейти се сглобяват и разпращат само при промяна състоянието на някоя връзка - например, когато някой канал се претовари, когато на рутъра му угасне токът, или конкуренцията му резне кабелите. Понякога се разпращат и цялостни описания на мрежовите карти - например, когато OSPF рутър се включи към мрежата, той цели максимално бързо да попълни своята карта.

При получаване на link state пакет, който е нов за рутъра, рутърът си записва данните от него, а също и ID, Sequence number и Age, след което записва пакета в буфер и го разпраща към своите съседи. При получаване на нови пакети със същия ID, те се сравняват по Age и Sequence number - по-старите се изтриват, а по-новите се записват на мястото на досега пазения пакет и отново се наводнява с тях мрежата. При получаване на един и същи пакет втори път, той се унищожава.

За безпроблемна работа, е необходимо полетоо Sequence number да е достатъчно голямо. При късо поле, често ще се прехвърля максимумът и новите пакети ще почват от 0 - пакетите няма да остаряват достатъчно и протоколът ще се бърка, съответно - ще конверира по-бавно. Определено е, че с 32-битово поле и изпращане на пакет всяка секунда, максимумът ще се прехвърли след повече от един век непрестанна работа.
Ако Sequence number се повреди при преноса на пакета, може да се случи така, че стойнотта изведнъж да скочи много. Това би довело до изхвърлянето на множество валидни пакети. Тук се намесва полето Age - протоколът решава дали да приеме пакета, или да го изхвърли. Чрез сравняване на двете се откриват събития като рестартиране на рутър.

Събиране и изчисляване

Рутърът има две възможности: или след време да спре да приема ъпдейти и да пресметне дървото на пътищата, или непрекъснато да събира и периодично да пресмята.
При мерене на закъснението, може отговорът да се изпрати моментално, или да се нареди в опашка в рутъра. При втория вариант, се отчита размерът на съобщението1.
Лесен за изпълнение вариант е метриката на всяка дъга да се счита за единица. Този случай не отразява добре състоянието на мрежата, но се изчислява бързо. Освен това, при него липсва осцилация на трафика: В графа по-горе, маршрутите ABCD и AECD имат еднаква цена. Тъй като в дървото има единствен път, само единият маршрут ще се запише в таблицата. Когато трафикът започне да се движи по него, метриката му ще се повиши и той ще стане неоптимален, при което другият ще го смени. Тогава пък неговата метрика ще стане висока, и така нататък. При фиксирано тегло, натоварването не участва в метриката и осцилация не се случва. Повечето протоколи, ползващи комплексна метрика, позволяват load balancing: всики маршрути с еднакво тегло се записват в таблицата, като маршрутизаторът ги използва последователно.

Колкото по-голяма е мрежата, толкова по-сложен става графът и изчисленията стават твърде тежки в големи мрежи. Тъй като тук няма максимален мрежов диаметър, ограничения върху растежа на мрежата налага изчислителната възможност на устройствата, чието действие се забавя с уголемяването на графа. Съществува механизъм, който намалява натоварването върху рутърите. Как точно - в следващата тема.

Още по въпроса

Distance vector vs. Link state

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License