Лекции по компютърни мрежи и комуникации

Той прочита адреса на получателя и по него определя към коя изходна линия да изпрати кадъра (за целта се поддържа специална таблица). Ще отбележим, че мостът предава кадъра само към определената от него изходна линия, а не по всички изходни линии. Подобно устройство е превключвателят (switch) - той също прочита адресите на постъпилите в него кадри. Преключвателите най-често се използват когато на всяка линия има по една канална станция. Всяка линия е самостоятелна, така че кадри не могат да бъдат изгубени поради колизии. За сметка на това в превключвателя трябва да има достатъчно буферно пространство за да може да се препращат кадрите. По-добра алтернатива е използването на cut-through превключвател, който препраща кадъра към съответната изходна линия (стига тя да е свободна) веднага след като е прочетен адресът на получателя.

Ако мрежата е с дейтаграми, решението трябва да се взима наново за всяка пристигнала дейтаграма, тъй като оптималният маршрут може да се е променил след последното изпращане. Ако мрежата използва виртуални канали, решенията по маршрутизацията се взимат само когато се създава виртуалният канал. Всички пристигнали пакети следват установения маршрут.

Освен това максимизирането на общия поток може да влезе в противоречие с изискването мрежовите ресурси да могат да се използват от всички потребители в мрежата.

Това прави неадаптивните алгоритми приложими само в малки мрежи, при които рядко настъпват промени.

Неадаптивните алгоритми се наричат още статични.

Ще разгледаме примерна маршрутна таблица.

Мрежата представяме като граф - върховете са възлите в мрежата, а дъгите са комуникационните линии.

Метриката в графа се определя на базата на дължината на линиите, време-закъснението за минаване на един пакет,

надеждност на линията, цена, брой хопове и др. Възможно е да се комбинират една или повече от изброените характеристики.

Нека е дадена следната мрежа:

Маршрутната таблица на възела J би могла да изглежда по следния начин:

A	A	0.63	I	0.21	H	0.16
B	A	0.46	H	0.31	I	0.23
C	A	0.34	I	0.33	H	0.33
D	H	0.50	A	0.25	I	0.25
E	A	0.40	I	0.40	H	0.20
F	A	0.34	H	0.33	I	0.33
G	H	0.46	A	0.31	K	0.23
H	H	0.63	K	0.21	A	0.16
I	I	0.65	A	0.22	H	0.13
J	--	--	--	--	--	--
K	K	0.67	H	0.22	A	0.11
L	K	0.42	H	0.42	A	0.16

между 0 и 1. Ако числото е  0.63, пакетът се изпраща към A, ако числото е > 0.63 и  0.84 пакетът се изпраща към I,

ако числото е > 0.84, пакетът се изпраща към H.
При адаптивните алгоритми маршрутните таблици се променят динамично за да отразяват промени в топологията и натовареността на трафика. Важна характеристика на един адаптивен алгоритъм е неговата скорост на сходимост - тя се определя от времето, което е необходимо да се преизчислят маршрутните таблици на всички маршрутизатори в мрежата при промяна в топологията или трафика.
Оптималните пътища между всеки два възела в мрежата се изчисляват по някои от алгоритмите за намиране на най-къс път в граф (след като е въведена метрика в графа, представящ мрежата). Всички тези алгоритми се базират на принципа за оптималност, който гласи че всяка част от оптимален път е също оптимален път между съответните два върха. Като следствие от този принцип, оптималните пътища от един връх към всички останали образуват дърво (sink tree).
Алгоритъм на Дейкстра
Алгоритъмът на Дейкстра е алгоритъм за намиране на най-къс път в граф от даден връх до всички останали върхове. Важно е да се отбележи, че при алгоритъма на Дейкстра теглата на ребрата трябва да са положителни.
При този алгоритъм на всеки връх се присвоява етикет, който съдържа дължината на най-добрия намерен път до върха за момента, както и непосредственият предшественик на върха по този път.
В началото всички върхове имат етикети  (достатъчно голямо число), само началният връх има етикет 0.

На всяка стъпка на алгоритъма се избира върха с най-малък етикет, който не е бил избиран до момента. Ако пътят до някой от съседите на избрания връх е по-лош отколкото пътя до този съсед, минаващ през избрания връх, то етикетът на съседа се променя.

След евентуалната промяна на етикетите на всички съседи на избрания връх се преминава към следващата стъпка на алгоритъма.

Резултатът от алгоритъма е дърво на оптималните пътища от дадения връх до всички останали.

Всеки маршрутизатор поддържа по един списък с номерата на пакетите, които са минали през него за всеки възел-източник.

Ако пристигнал пакет присъства в списъка, той не се препредава, в противен случай списъкът се актуализира и пакетът се предава. Списъците може да нарастнат много - при една голяма мрежа алгоритъмът не е приложим. За намаляване на дължината на един списък може да се добави допълнителен брояч k, който указва, че всички пакети до номер k са предадени. При това положение, пакетите с номера по-малки от k може да не присъстват в съответния списък.
Метод на случайното обхождане

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

Такава информация, обаче, ще има твърде голям обем.
Централизирани адаптивни алгоритми
При централизираните адаптивни алгоритми в мрежата се създава един маршрутен управляващ център. Той изчислява маршрутните таблици на всички възли и им ги изпраща. За да се адаптират маршрутните таблици към текущата топология и текущия трафик, всички възли трябва да изпращат информация към маршрутния център. На базата на получените сведения, маршрутният център изчислява теглата на ребрата и след това пресмята оптималният маршрут между всеки два възела. Добре е да се поддържат алтернативни пътища между възлите.

Информацията от по-близките до маршрутния център възли ще пристигне по-бързо отколкото от по-далечните. Поради тази причина, периодът на обновяване на маршрутните таблици трябва да е поне два пъти по-голям от времето за преминаване на пакет от маршрутния център до най-отдалечения от него възел.

Преизчислена маршрутна таблица, получена в един възел не трябва да се използва веднага, тъй като маршрутните таблици пристигат по различно време в различните възли.

Ако по някаква причина маршрутният център отпадне, мрежата остава без управление. За целта може да се дублира маршрутният център, но тогава служебният трафик би се увеличил твърде много.

Предполага се, че всеки маршрутизатор знае метриката на връзките до своите съседи. Ако метриката е брой хопове, разстоянието до всеки съсед е 1. Ако метриката е натоварване на възела, разстоянието до всеки съсед е броя на пакетите в изходящата опашка към този пакет. Ако метриката е време-закъснение, маршрутизаторът периодично изпраща “ехо” пакети до съседните му маршрутизатори и измерва закъснението на техния отговор.

Нека да предположим, че за метрика е избрано време-закъснението на пакетите.

Веднъж на всеки T милисекунди маршрутизаторите изпращат на своите съседи съдържанието на маршрутната си таблица.

Нека даден маршрутизатор J получи маршрутната таблица

на съседа си X, като X_i е обявеното от X закъснение до маршрутизаторът i. Ако закъснението от J до X е m, то от J до всеки маршрутизатор i има път през X със закъснение X_i + m.

Възможни са четири случая:

• 
  ако в маршрутната таблица на J няма ред за направлението i, то J добавя такъв ред и записва в него следваща стъпка X и закъснение X_i + m;
  
• 
  ако в маршрутната таблица на J има ред за направлението i и в него е записана следваща стъпка X, то стойността на закъснението се актуализира с X_i + m независимо дали тя е по-голяма или по-малка от предходната стойност;
  
• 
  ако в маршрутната таблица на J има ред за направлението i, в него е записана следваща стъпка различна от X и закъснение по-голямо от X_i + m, то редът се актуализира като за следваща стъпка се записва X, а за закъснение X_i + m;
  
• 
  ако в маршрутната таблица на J има ред за направлението i, в него е записана следваща стъпка различна от X и закъснение по-малко или равно на X_i + m, то редът не се променя.
  

Нека е дадена примерната мрежа

Векторите, които J получава от своите съседи A, I, H, K са следните:

Измерените закъснения между J и съседите му A, I, H, K са следните:

На базата на тази информация, новият вектор на разстоянията, изчислен от J е следния:

Да разгледаме следния пример с метрика в хопове.

Нека маршрутизаторът A в началото не е включен в мрежата.

Всички останали маршрутизатори знаят това - в маршрутната им таблица към направлението A е записано  (достатъчно голямо число, трябва да е поне с единица повече от диаметъра на мрежата). Това е отразено на първия ред по-горе.

След включването на A останалите маршрутизатори научават за това събитие чрез няколко обмена на своите вектори на разстоянията, всеки от които се извършва едновременно между всички съседни маршрутизатори. При първата обмяна B научава от А за път с дължина 0 до A и записва в своята таблица, че A е на разстояние 1. В този момент останалите маршрутизатори все още не са научили за включването на A. Това е отразено на втория ред по-горе. При следващия обмен C научава, че от B съществува път до A с дължина 1 и записва в своя вектор път до A през B на разстояние 2 и т.н. По-общо в мрежа с диаметър k хопа са необходими най-много k размени на съобщения за разпространяване на новината за появил се по-добър път.

Нека всички маршрутизатори в началото са включени в мрежата.

Да предположим, че A спира да работи или се прекъсва връзката от A до B, което от гледна точка на B е същото. При първия обмен B не получава информация от A, но получава информация от C, че има път до A с дължина 2. B не знае, че пътя от C до A минава през него - от негова гледна точка би могъл да съществува друг независим път от C до A, затова B записва в таблицата си в реда за A път с дължина 3 и следваща стъпка C. D и E не променят маршрутните си таблици при първия обмен на векторите на разстоянията. На следващия обмен C научава за два възможни пътя до A, и двата с дължина 4, единият през B, другият през D -

C избира и записва в маршрутната си таблица единия от тях в зависимост от реда на обработването на съобщенията от B и D.

Резултатът от продължаващия обмен е отразен в следващите редове по-горе. Той ще продължи докато стойностите по направленията към A и в четирите машрутизатора не достигнат .

Този проблем се нарича броене до безкрайност.

Едно частично негово решение е т.н. разделяне на хоризонта (split horizon). При него се въвежда ново правило - ако в маршрутната таблица на X в реда за Y е записана следваща стъпка Z, то X не изпраща към Z информация за маршрута към Y.

В горния пример на втория обмен на вектори, C не изпраща към B информация за маршрута към A, тъй като маршрутът от C към A минава през B.

Въвеждането на разделяне на хоризонта не решава напълно проблемът броене до безкрайност.

Да разгледаме следния пример.

В началото A и I имат пътища с дължина 2 стъпки до K през J,

а J има път с дължина 1 до K. Да предположим, че връзката между J и K отпадне. Тогава на първия последвал обмен J няма да получи информация за нов път до K през A или I по правилото за разделяне на хоризонта и правилно ще заключи, че K е недостижим. На следващия обмен А и I научават,

че няма път до K през J, но A научава за път до K през I с

дължина 3 и I научава за път до К през A с дължина 3.

Така въпреки разделянето на хоризонта, A и I ще броят до безкрайност.

(link state routing), всеки маршрутизатор трябва да извършва следните пет основни действия:

1. 
   Откриване на съседните маршрутизатори и техните мрежови адреси.
   
2. 
   Измерване на цените на връзките до съседните маршрутизатори.
   
3. 
   Конструиране на пакети с информация за състоянието на връзките.
   
4. 
   Изпращане на тези пакети до всички останали маршрутизатори.
   
5. 
   Изчисляване на най-късия път до всеки маршрутизатор в мрежата.
   

В резултат на тези пет действия се събира и разпространява до всички маршрутизатори информация за цялата топология на мрежата. Ще разгледаме по-подробно отделните действия.

“ехо” пакет по всяка от изходящите линии на маршрутизатора.

От своя страна, всеки от съседите отговаря като съобщава

името си. Това име трябва да бъде уникално в мрежата.

Ако два или повече маршрутизатора са свързани в мрежа с общодостъпно предаване (например Ethernet), откриването на съседите е малко по-сложно. Един възможен начин за представяне на връзките между тях е да се въведе допълнителен възел, който да отговаря на общата среда за предаване.
Измерване на цените на връзките
Всеки маршрутизатор трябва да може да определи време-закъснението до своите съседи. Най-простият начин е маршрутизаторът да изпрати "ехо" пакет към всеки свой съсед на който трябва директно да се отговори. Времето от изпращането на "ехо" пакета до получаване на отговора се дели на две и по този начин се получава времето-закъснение до съответния съсед. За по-точно измерване, този процес може да се повтори няколко пъти и да се вземе средната стойност. Този метод предполага, че връзките са симетрични, което не винаги е вярно.

Друг въпрос е дали при измерването да се взима предвид натовареността на възлите. Разликата се постига в зависимост от това кога маршрутизаторът стартира измерването - когато пакетът постъпва в съответната изходяща опашка или когато пакетът се придвижи в началото на опашката.

Включването на натовареността на възлите има предимства и недостатъци. Предимството е, че от две линии, които имат еднаква скорост за по-къса ще се счита по ненатоварената линия. Това ще доведе до по-голяма ефективност.

Недостатъкът може да се илюстрира със следния пример -

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

Пакетът трябва да съдържа уникалното име на подателя, пореден номер, срок на годност (ще разгледаме тези полета по-долу) и списък със съседите на подателя, като за всеки съсед е указана цената на връзката до него.

Определянето на момента, в който трябва да бъдат подготвени и изпратени пакетите е важна задача.

Един възможен начин е това да става през определени равни интервали от време. Друга по-добра възможност е пакетите да се подготвят и изпращат само при промяна в топологията на мрежата - след отпадане или поява на нов съсед или промяна в цената на някоя връзка.

Пакетите със състоянието за връзките за шестте маршрутизатора изглеждат по следния начин: