Тема 11.

Маршрутни алгоритми - обхождане, наводняване, метод на Берън.


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


Малко история

Локалните мрежи в развитието си, започвайки от два компютъра, свързани един с друг, достигат етапа на споделения канал. С увеличаването на броя хостове в канала обаче, както и с разрастване по територия на мрежите1 се оказва, че споделеният канал не може да поддържа ефективно нарастващия трафик. Разумно решение на проблема се явява обособяването на специални устройства, отначало наричани портали (gateways), които да управляват потока от пакети в мрежата2. Подобно развитие на нещата се осъществява и в ARPAnet. В началото на съществуването си, тя се състои от (малко на брой) мрежови хостове, свързани към т. нар. IMP (Interface Message Processors), които управляват доставката на пакетите.

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

Работа на рутъра

router-queues.PNG

Рутърът е активно мрежово устройство. Той има входни и изходни линии (интерфейси), свързани чрез канални адаптери към канали (най-често двуточкови)3. Интерфейсите са поне 2, тъй като по същество задачата на устройството е да свързва локални мрежи. Кадрите, изпращани му от мрежовите хостове, постъпват по входните линии, декапсулират се до пакети, разглежда се целевият (destination) адрес и, според съдържанието на маршрутната таблица на устройството, се намира най-оптималният път за пакета и той се препраща по съответния изходящ интерфейс4. Важна особеност е, че, за разлика от обикновените хостове, тук информацията се разглобява само до пакети (PDU от трето ниво по OSI модела), след което се сглобява наново - затова и рутърът се определя като устройство от ниво 3.

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

Една от основните предпоставки за успеха на пакетните мрежи е ограничената големина на пакета. За рутъра това означава, че при проектирането му може да се предвиди определено количество памет, която да е достатъчна за временно съхраняване на прилично голям брой пакети, и която същевременно да е хардуерно реализирана, т. е. бързодействаща.5. В IP максималната дължина на пакета е 65536 октета.

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

За маршрутизирането с любов

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

Наводняване (flooding)

Най-прост метод. Пакетът се копира и се препраща по всички интерфейси, с изключение на този, по който е получен (split horizon). При получаване на копие от пакета (цикъл в графа), копието се унищожава.

  • Елементарен метод, гарантира най-бързо достигане на целта, работи без предварително познаване на мрежовата топология. Ползва се понякога.
  • За сметка на това натоварва неимоверно мрежата - трафикът нараства експоненциално заради излишни копия.

Обхождане ("случайно блуждаене", random routing)

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

  • Не се натоварва трафикът в мрежата.
  • Няма обаче гаранция, че целта ще бъде достигната.

Метод на Берън ("горещ картоф", hot potato routing)

Още известен като deflection routing. Предложен от Пол Берън още преди ARPAnet. Подобен на случайното обхождане. Тук обаче рутърът не разглежда оптимални маршрути - приема, че всичките са такива - а цели да поддържа балансирано натоварване на опашките си. Затова той прехвърля получения пакет в най-късата опашка, като го задържа за възможно най-малко време - бърза да се "отърве" от пакета, сякаш той е горещ картоф.

В днешно време…

Допълнение към лекциите - за собствено сведение, не за пищова.
Маршрутизирането се извършва най-често чрез маршрутната таблица на устройството. Общо казано, тя съдържа записи с адреси на мрежи, адрес на рутър, през който минава най-добрият път до тези мрежи, и цена на пътя. Таблицата се попълва по три начина:

  • Директно свързани мрежи - те се вписват автоматично при активиране на съответния интерфейс.
  • Статично - на ръка от администратор се въвеждат маршрутите към съответните мрежи. Не натоварва мрежата с излишен трафик. Изисква познаване на мрежовата топология и се поддържа трудно. Подходящ за специфични маршрути, които не се променят често.
  • Динамично - чрез протоколи за маршрутизация - RIP, OSPF, EIGRP, BGP, IS-IS и други. В сравнение с изброените по-горе методи (блуждаене, Берън), този осигурява най-добър (в повечето случаи) маршрут и приемливо служебно натоварване на мрежата. За сметка на това, изисква познания за мрежовата топология и доста по-голяма изчислителна мощ на устройството.

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

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