Разпространяване на пакетите с информация за състоянието на връзката

За разпространението на пакетите се използва методът на наводняването (flooding). При него всеки пакет се изпраща по всички линии, освен линията по която е пристигнал.

Обработката на всеки пристигнал пакет започва с проверка дали пакетът има по-голям пореден номер в сравнение с най-големия пореден номер, който е пристигнал до този момент от този източник. Ако номерът е по-голям, информацията от пакета се записва в таблицата с информация за състояние на връзките и пакетът се предава по останалите линии. Ако номерът е по-малък или равен, пакетът се отхвърля.
Този алгоритъм има някои проблеми. Ако поредният номер не е достатъчно голям, той може да се превърти. Затова се използват 32-битови поредни номера. Ако на всяка секунда пристига по един пакет, то за превъртане на номера ще са необходими около 137 години, което е достатъчно много.

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

Ако в B пристигне дубликат на някой от пакетите в таблицата, то съответните флагове трябва да се актуализират. Например, ако пристигне дубликат на пакета със състоянието на C от F, преди този пакет да бъде препратен към F, то флаговете за изпращане на пакета ще се променят на 100, а флаговете за потвърждение - на 011.

Изчислените маршрути се записват в маршрутните таблици.

Необходимата памет за съхраняване на информацията за състоянието на връзките за мрежа с n маршрутизатори, всеки от които има по k съседи е пропорционална на nk.

Така големите по размер мрежи изискват използване на маршрутизатори с голям обем памет.

Пълната таблица за маршрутизатора 1A съдържа 17 реда и има следния вид:

Съкратената таблица за маршрутизатора 1A съдържа 7 реда и има следния вид:

В нея са запазени маршрутите към направленията в

"област 1". Маршрутите към направленията в останалите области са обобщени в един ред, като се използва маршрутизатора от съответната област, който е най-близо до маршрутизатора 1A. Спестяването на памет от маршрутните таблици има отрицателен ефект - някои от пътищата увеличават своята дължина. Например, най-късият път от 1A до 5C минава през "област 2", но при йерархично маршрутизиране ще се използва пътят през "област 3", тъй като това е по-добре за повечето маршрутизатори

от "област 5".

Задръстването може да се причини от няколко фактора.

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

Бавни процесори също могат да причинят задръстване.

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

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

Пристигнал пакет постъпва във входен буфер, след това преминава в изходен буфер, след това се изпраща потвърждение към източника.

Нека възелът има K изходни буфера, m е максималният брой буфери на една изходна линия, s е броят на изходните линии. Ако K = m, тогава е възможно всички изходни буфери да се ангажират с една натоварена линия, което ще довете до задръстване. Оптимално натоварване на възела се постига при m = K/.

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

Най-просто е да се отстраняват произволни пакети.

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

От друга страна, при трансфер на мултимедия, по-новите пакети са по-важни от по-старите, тъй като се цели

минимално закъснение.
Трета стратегия е ограничаването на общия брой пакети в мрежата. За целта в мрежата се пускат служебни

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

По този начин броят на пакетите в мрежата се контролира от броя на разрешенията. Този алгоритъм е сложен за поддръжка.
Последната стратегия е регулиране на входа при задръстване. Във всеки маршрутизатор се следи натовареността на изходните линии. Когато се надвиши някакъв праг на натовареност линията се слага в състояние на предупреждение. Когато линията е в такова състояние в обратна посока се изпращат специални задръстващи пакети. Чрез тях изпращача разбира, че трябва да намали скоростта на предаване. В крайна сметка задръстващите пакети достигат до хоста, който генерира пакетите, довели до задръстването и го уведомяват да намали темпото на предаване. Проблем е, че регулирането на входа при задръстване не се прави на транспортно ниво, където е известен пътя между хостовете и затова е трудно задръстващите пакети да намерят пътя си до хоста-източник.
Друг голям проблем при управление на натоварването на мрежите е проблемът deadlock. Да разгледаме пример с три възела A, B и C. Буферите и на трите възела са пълни. A има пакети за предаване към B, B има за C, a C има за A. По този начин трите възела са блокирани. Кръгът от блокирани възли може да е много по-голям.

Проблемът е, че трудно се установява наличието на deadlock в мрежата. Поради това deadlock трябва да се предотвратява.

Комуникацията в Internet най-общо се извършва по следния начин: транспортното ниво взима потоци от байтове и ги разделя на дейтаграми. Дейтаграмите могат на теория да достигнат 64Kb, но на практика те не са по-големи от 1500b. Всяка дейтаграма се изпраща самостоятелно, като по пътя тя може да се фрагментира на по-малки единици. Когато тези единици достигнат до получателя те се реасемблират от мрежовото ниво за получаване на оригиналната дейтаграма. По-нататък тази дейтаграма се подава на транспортното ниво на получателя, което я вмъква в съответния поток от байтове.

Ще разгледаме формата на IP-дейтаграмата във версия 4 (4-байтови адреси). Ще отбележим, че дейтаграмата се предава в

Big-Endian формат, т.е. от старшите към младшите битове.

IP-дейтаграмата се състои от заглавна част и част за данни. Заглавната част е 20B+опции с променлива дължина и има следния формат:

Полето Version указва версията на протокола, към който принадлежи дейтаграмата.

Полето IHL указва дължината на заглавната част в 32-битови думи. То е необходимо, тъй като полето Options има променлива дължина. Минималната стойност на това поле е 5, което отговаря на случая когато полето Options е празно. Максималната стойност е 15, което ограничава заглавната част до 60B, т.е. полето за опции до 40B.

Полето Type of service показва какво обслужване очаква дейтаграмата. Различните видове данни, например видеоизображение, глас, файлове предполагат различно обслужване. Практически сегашните маршрутизатори не обръщат внимание на това поле.

Полето Total length съдържа общата дължина на дейтаграмата (заглавна част + данни). Максималната дължина е 65535 байта.

Полето Identification съдържа номер на дейтаграмата. Всички фрагменти на една и съща дейтаграма имат еднакъв номер и по този начин получателя разбира кой фрагмент към коя дейтаграма принадлежи.

Флагът DF(don’t fragment) указва на маршрутизаторите да не фрагментират дейтаграмата. Всички автономни системи трябва да могат да приемат фрагменти от поне 576B. Ако размерът на фрагментите е по-голям и флагът DF е 1, то дейтаграмата може да пропусне някоя автономна система с по-малка дължина на пакета, дори тя да се намира на оптималния маршрут.

Флагът MF(more fragments) за всички фрагменти на дейтаграмата, освен последния е 1, а за последния е 0, т.е. той показва дали получен фрагмент е последен в дейтаграмата или не.

Полето Fragment offset указва къде се намира фрагмента в оригиналната дейтаграма. Всички фрагменти, освен последния трябва да са с дължина кратна на 8B. Тъй като полето Fragment offset е 13 бита максималният брой фрагменти в една дейтаграма е 8192.

Полето Time to live е брояч, който ограничава продължителността на живота на дейтаграмата. То отброява времето в секунди, има дължина 8 бита, така че максималното време за живот е 255 секунди. Това поле се намаля с единица на всеки hop, а освен това се намаля с единица и за всяка секунда престой в маршрутизатор. Когато полето стане 0, дейтаграмата се премахва и в обратна посока се изпраща предупредителен пакет.

Полето Protocol указва протокола на транспортно ниво, към който трябва да се предаде дейтаграмата. Той може да бъде TCP (transmission control protocol), UDP (user datagram protocol) или някой друг.

Полето Header checksum е контролна сума само на заглавната част. Тя трябва да се преизчислява на всеки hop, тъй като поне едно поле се променя - Time to live.

Полетата Source Address и Destination address съдържат съответно адрес на източника и адрес на получателя.

Възможни са различни опции в полето Options.

Първата опция е Security – тя обявява секретност на дейтаграмата.

Втората опция е Strict source routing и тя дава целия път от източника до получателя като последователност от IP-адреси. Дейтаграмата трябва задължително да следва този път.

Третата опция е Loose source routing и тя указва дадена последователност от маршрутизатори да бъде посетена в указания ред от дейтаграмата, но е възможно тя да премине и през други маршрутизатори.

Четвъртата опция е Record route и тя указва маршрутизаторите по пътя на дейтаграмата да добавят своя IP-адрес към полето на опцията. Това позволява да се проследят грешки при маршрутизирането.

Последната опция е Timestamp, която е подобна на опцията Record route, но с тази разлика, че маршрутизаторите освен IP-адреса си записват и времето по което е минала дейтаграмата.
Всеки хост и маршрутизатор в мрежата има IP-адрес.

Всички IP-адреси са 32-битови. Всеки IP-адрес се дели на две части – номер на мрежа и номер на хост. Номерът на мрежата е непрекъсната порция от битове в лявата част на адреса, а номерът на хоста е останалата непрекъсната порция от битове в дясната част на адреса.

В зависимост от структурата си IP-адресите се делят на следните пет класа:

Указаните битове в началото на адреса, които определят неговия клас се наричат сигнални битове.

В клас A са възможни 127 мрежи, всяка с приблизително 16000000 хоста.

В клас B са възможни приблизително 16000 мрежи, всяка с приблизително 65000 хоста.

В клас C са възможни приблизително 2000000 мрежи, всяка с по 254 хоста.

Клас D е предназначен за работа с групови адреси, а клас E е резервиран за бъдеща употреба.

Числото 0 се интерпретира по специален начин в IP-адресите – то означава тази мрежа или този хост. Адрес, който съдържа само единица се интепретира като broadcast-адрес, т.е. адресират се всички хостове в дадена мрежа.

Всяка мрежа трябва да има уникален номер и всички хостове в дадена мрежа трябва да имат един и същ номер на мрежата.

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

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

Например за един адрес от клас B вместо 14 бита за номер на мрежата и 16 бита за номер на хост се използват 20 бита за номер на мрежа, като десните 6 от тях са за номер на подмрежа и 10 бита за номер на хост.

За имплементация на подмрежите маршрутизаторите се нуждаят от мрежова маска, която определя границата между номера на мрежата + номера на подмрежата и номера на хоста. В горния пример мрежовата маска изглежда по следния начин:

Освен това всеки хост при първоначалното си стартиране уведомява чрез broadcast съобщение от вида “I am X.X.X.X and my Ethernet adress is hh:hh:hh:hh:hh:hh”, където X.X.X.X и hh:hh:hh:hh:hh:hh са съответно IP адреса и Ethernet адреса на хоста, всички останали хостове в локалната мрежа, които ще запишат тази информация в своите кешове.

Чрез ARP могат да се определят физическите адреси само на хостове, които са включени в локалната мрежа и имат IP адреси от IP мрежата (подмрежата) на изпращача. Дейтаграмите, чийто получател е хост от друга IP мрежа (подмрежа), се изпращат към маршрутизатора, включен в локалната мрежа. Неговият Ethernet адрес се получава чрез ARP заявка, ако не е кеширан. Този маршрутизатор избира маршрут и препраща дейтаграмата към нейния получател.
Протоколът RARP (reverse address resolution protocol) е за намиране на IP адреси по Ethernet адреси. Обикновено IP адресът на хоста е записан в конфигурационен файл, който се намира на твърдия диск на машината. При първоначално зареждане на операционната система файлът се прочита от твърдия диск и хостът научава своя IP адрес. В случай, че в локалната мрежа е включена машина, която не притежава собствен твърд диск, за определяне на нейният IP адрес се използва RARP протоколът. За целта в мрежата трябва да е включен хост, който функционира като RARP сървър. Този сървър съхранява съответствието между Ethernet и IP адреси на станциите в мрежата. Действието на RARP се основава на наличието на уникален физически Ethernet адрес на всяка система в локалната мрежа. При инициализиране на машината без твърди дискове RARP протоколът прочита този адрес от интерфейсната карта и предава до всички станции в мрежата пакет-заявка. RARP сървърът отговаря на тази заявка, като в пакета-отговор се съдържа IP адресът, съответстващ на изпратения Ethernet адрес.
14. Маршрутни протоколи RIP. Рутери.
RIP (routing information protocol) e широко използван маршрутизиращ протокол с вектор на разстоянието. Той е подходящ предимно за малки мрежи, в които относително рядко настъпват промени в топологията.

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

Както повечето маршрутизиращи протоколи, RIP също използва таймери. Обикновено на всеки 30 секудни се изпраща копие на маршрутната таблица към съседните маршрутизатори. Този интервал се задава от таймера за обновяване (route update timer) и е общ за всички маршрути. Таймерът за невалиден маршрут (route timeout timer) определя интервала от време, след който даден маршрут се счита за невалиден, ако маршрутизаторът не е получил съобщения за него. Когато даден път бъде отбелязан като невалиден, се изпращат съобщения с тази информация към съседните маршрутизатори и се преустановява използването му. Тези съобщения се изпращат до изтичането на таймера за изтриване на маршрут (garbage-collection timer), след което пътя се изтрива от маршрутната таблица.

Първата версия на RIP не поддържа подмаски, т.е. от гледна точка на IP не поддържа подмрежи, затова в края на 80-те години се разработва втора версия на RIP. Формата на пакетите на версия RIP-2 е следния:

Първите три полета Command, Version и Routing domain представляват заглавната част на пакета, а останалите шест полета съдържат данни за маршрути и комбинация от тях може да се повтаря до 25 пъти в един RIP-2 пакет. За пренасяне на информацията от по-големи маршутни таблици се използват няколко RIP-2 пакета.

Полето Command указва дали пакетът съдържа заявка или отговор. Командата “Заявка” изисква отговарящата система да изпрати цялата или част от маршрутната си таблица. Командата “Отговор” представлява отговор на получена команда “Заявка” или периодично съобщение за обновяване на маршрутите, в което се включва цялата маршрутна таблица.

Полето Version указва версията на протокола, за RIP-2 тази стойност е 2.

Полето Routing domain не се използва.

Полето Address family е идентификатор на адресна фамилия. Въвежда се идентификация на група от маршрутизатори. Всички маршутизатори в една група имат една и съща адресна фамилия.

Полето Route tag указва дали информацията за даден маршрут произхожда от RIP или от друг вътрешен или външен маршутизиращ протокол.

Полето IP address съдържа IP адреса на мрежа или хост, която представлява местоназначението на описвания маршрут.

Полето Net mask е мрежовата маска, отнасяща се за горния IP адрес.

Полето Next hop IP address съдържа IP адрес на най-близкия машрутизатор, към който ще се изпрати пакета.

Полето Metric указва броя хопове до съответното местоназначение и може да има стойност от 1 (директно свързана мрежа) до 16 (недостъпен маршрут – безкрайност).
В първия от 25-те записа на RIP-2 пакета полето Address family може да има стойност 0xFFFF, която указва че следва идентификационна информация за подателя на пакета. В този случай полето Route tag определя използвания алгоритъм, а следващите 16 байта съдържат парола. Използването на този механизъм намалява максималния брой маршрути в един RIP-2 пакет на 24.
При промяна в топологията на мрежата се налага всички маршрутизатори да преизчислят своите вектори на разстоянията и да достигнат до непротиворечиво описание на новата топология. За увеличаване на скоростта на сходимост на RIP се използват различни методи, например разделяне на хоризонта. Тези методи намаляват вероятността за поява на цикли в маршрутите, но не могат да гарантират отсъствието им.

Максималният брой хопове в RIP е 15. Всяко местоназначение, което е на разстояние над 15 хопа се приема за недостижимо. Това прави невъзможно прилагането на RIP в мрежи с диаметър над 15 хопа, но ограничава ситуацията “броене до безкрайност”, при която могат да се получат цикли в маршрутите.

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

• 
  
  Изтегляне 1.22 Mb.
  
  Сподели с приятели: