Принципи и алгоритми за маршрутизация в Интернет

4. принципи и алгоритми за маршрутизация за Интернет

4.1. маршрутизиране проблем в Интернет

Алгоритъмът за маршрутизиране е основата, върху която цялата работа на основната мрежа с TCP / IP архитектура. Осигуряване на надеждни услуги на мрежата изисква определена динамика за маршрутизация. Неочаквани промени в ядрото свързаност на мрежата трябва да се разглеждат като нормално явление и на правилно обработени, както и на натоварването на отделните области и канали.

Има редица изисквания, които трябва да бъдат взети под внимание при избора на подходящ алгоритъм за маршрутизация:
· Routing алгоритъм трябва да признае провала и възстановяване на комуникационни канали или други IP-рутери и да преминат към други подходящи маршрути. маршрут време за превключване трябва да бъде по-малък от протокол TCP типичния изчакване потребител (около 1 минута);
· Алгоритъм трябва да изключват образуването на цикъла, примките и ефекта на "пинг-понг" в предписаните маршрути между съседни на IP-маршрутизатори и дистанционно управление за IP-маршрутизатори. Наличието на по-горе ефекти не трябва да надвишава типичния изчакване Потребителят протокол TCP (около 1 минута);
· Load от съобщенията за контрол, които са необходими за маршрутния алгоритъм не трябва значително да влоши или да нарушат нормалната работа на мрежата. Промяна на състоянието на мрежата, която може да се прекъсне нормалната работа в някои локална мрежа, не трябва да засяга отдалечени обекти;
· Тъй като размера на мрежата се увеличава непрекъснато, е необходимо да се осигури ефективно използване на ресурсите на мрежата, като например промяна маршрути матрици за извършване на частично, преминава в глобалните мрежи е само добавка към базата данни за маршрутизация;
· Размер на маршрутите база данни не трябва да превишава някаква константа, която не зависи от топологията на мрежата, умножена по броя на възлите и средната свързаността на мрежата. Една добра реализация не трябва да изисква съхранение изчерпателна информация за маршрутизация във всяка IP-рутер;
· Ако използвате показател въз основа на множество е постижимо и забавянето в доставката на пакета, те не трябва да зависи от директна свързаност към всички други IP-базирани рутери или използване на механизми за излъчване, които са специфични за някои мрежи. процедури за разпити не могат да реализират значителни допълнителни разходи;
· Маршрути по подразбиране трябва да се използват като първоначалните допускания за определяне на маршрута до финала и след това да изберат посоката на предаване.

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

Например, немислимо е канал с висока скорост, за да улови целия обем на паметта на буфер, като не оставя нищо да се забави връзка. В един добър алгоритъм трябва да се вземе предвид "Вид" заглавна IP-пакет; IP-рутер да зададете по-висок приоритет за IP-предаван от ръководството или лична информация.

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

Определение. Частен случай на маршрутизация протокол, работещи в рамките на една автономна система се нарича вътрешна маршрутизация протокол (IGP - Интериор Gateway Protocol).

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

Определение. Протоколът за обмен на информация между официалния автономни системи се наричат ​​външна Gateway Protocol (EGP - Стая Gateway Protocol).

Всеки IP-рутер, трябва да се гарантира прилагането на протоколите от протоколите за физическо, предаване на данни, мрежови слой, както и за достъп до мрежата. Тъй като последните употребявани Ethernet протоколи, Frame Relay, банкомат, SLIP, РРР, и няколко други, и за мрежа с X.25 / 2 (LAP-B) архитектура ISO протокол.
В допълнение, IP-рутер е необходимо да се приложи алгоритъм за избор на маршрут маса маршрута, както и неговото актуализиране алгоритъм.

Има статични и динамични алгоритми актуализират масата.

Шлюзове, които са част от автономна система могат да изпълняват динамична маршрутен алгоритъм - протоколи на базата на алгоритъма и протоколите на Белман-Форд основава на алгоритъм Дейкстра.
Всяка дъга на графиката се определя реално число, наречено дължината на дъгата; тогава дължината на пътя е сумата от дължините на съставните ръбове.
Обикновено този номер perepriomov или средно забавяне пакет, но други показатели, например, капацитета на комуникационния канал, надеждност.

Gateways работещи на алгоритъма на Белман-Форд. магазин векторни дължини на кратки маршрути до всички мрежи, които са част от обединена мрежа.
Периодично всяка врата прехвърля вектора на съседния автономна система на шлюзове и векторни елементи, взети от близката врата, състоящ се от дължини на изходящите линии.
Въз основа на получената маса се конструира нов вектор дължини на късите маршрути - Белман-Ford алгоритъм (DV - алгоритъм Разстояние Vector).
Протоколи на базата на DV-алгоритъм просто изпълнява, изискват малко памет и процесорно време, обаче, те споделят редица недостатъци. Когато броят на мрежи, които съставят автономна система значително увеличава размера на предоставената информация, тъй като DV-алгоритъм изисква всички шлюзове периодично предават дължина вектор маршрути.

Шлюзове, които работят в рамките на алгоритъм Дейкстра (краткия път Първо - SPF-алгоритъм), първо да се определи най-краткия маршрут към всички мрежи автономна система. За тази цел всяка врата е изградена пълна краткия път дърво корени в този портал.
Процедурата за изграждане на най-краткия път дървото използва принципа, че в първото дърво на най-късите пътища, включени дължина на дъгата с най-малките, така Дейкстра алгоритъм често се нарича първата най-краткия път.
След като шлюз построен най-краткия път дърво, промени в характеристиките на комуникационни линии, които определят дължините на съответните дъги, промените в топологията на мрежата доведе до малко допълнителни изчисления за коригиране на най-краткия път дървото.
Шлюзове обменят информация само за дължините на изходящи линии, отколкото дължината вектор на маршрути, както в случая на алгоритъм Белман-Ford. корекция Размер пакети с сервизна информация за маршрута е малък и не зависят от броя на мрежите в автономната система. Всяка врата изпраща тези пакети чрез наводняване. Когато сте в нов шлюз за мрежата или въвеждане на нова линия за комуникация промени в топологията на мрежата не се смятат при фрезоване за известно време, за да се гарантира, че информацията за промените, които са настъпили имал време да достигне до всички шлюзове на автономна система.

Като цяло, алгоритъм на Дейкстра в сравнение с алгоритъма на Белман-Форд дава по-реалистична оценка на ситуацията в мрежата, по-бърз отговор на важни промени в мрежата (като включването на новата връзка) и намалява пакет примка; Алгоритъм на Дейкстра, но по-трудна за изпълнение и изисква много пъти повече памет.

4.2. Интериорен Gateway Protocol

Съгласно протокол GGP (Портал Gateway Protocol, RFC 823) е разработена и внедрена от BBN за първи експериментален портал интернет.
Той все още се използва в шлюзовете на компанията BBN LSI / 11, въпреки че се смята, че GGP има сериозни пропуски и по-късно бе заменен от алгоритъм SPF.
GGP протокол алгоритъм определя маршрута с минимален брой perepriomov, т.е. това е просто мярка за дължина на броя на транзитната мрежа раздели между двойки шлюзове.
Той реализира разпределена алгоритъм за най-краткия път, който изисква глобално сближаване на таблици за маршрутизация, след промени в топологията или свързаност.

RIP протокол (Routing Информация протокол, RFC 1058, 1581, 1582, 1724), често се използва за клас от протоколи за маршрутизация въз основа на протокола XNS (система Xerox Network - Xerox Network System) Xerox компания.
Изпълнението на RIP за семейството на TCP / IP протокол е широко достъпна, като част от софтуера на операционната система UNIX, например, FreeBSD или Linux. Поради своята простота, протоколът RIP е най-вероятно да се превърне в "отворена» IGP протокол, т.е. протокол, който може да се използва за съвместни шлюзове, доставени от различни фирми.
Както RIP маршрутизиране показатели за измерване на броя на скока (стъпки) до целта. Този вид показател не отчита разликите в честотната лента или струпването отделни мрежови сегменти.
Всеки път се свързва с таймер тайм аут и "събирач на боклука". Таймер за таймаут се нулира всеки път, когато се инициализира маршрут или поправени. Ако от последното адаптиране отне 3 минути и получих съобщение, че вектора на разстояние е 16, маршрутът се счита за закрита, но записа за него не се изтриват, докато изтече времето "събиране на боклука" (2 минути). това превключване не се проявява с появата на еквивалентно маршрут.
RIP е доста проста, но не и лишена от недостатъци:
- това отнема много време, за да се възстанови връзката след авария в рутера (минути); в процеса на определяне на режима са налични цикли;
- броя на стъпките - важен, но не и единственият параметър на маршрута, както и 15-те стъпки - не на лимита за днешните мрежи.

"HELLO" протокол. Fuzzball софтуер за LSI / шлюз 11 включва изпълнението на IGP име "здравей". За разлика от RIP има критерий за избор на маршрут е времето, а не разстоянието, така че "HELLO" изисква достатъчно точен време услуги за синхронизиране шлюзове.

IS-IS протокол. Като се има предвид, от една страна, широко разпространена мрежа архитектура ПЗР на / IP, от друга страна, на вниманието на правителството и търговските организации с EMVOS архитектура; Той очаква, че TCP / IP архитектура и EMVOS ще съществува от дълго време заедно. Ето защо е необходимо за шлюз, който да може да насочва и двете IP- и EMVOS трафик.
Протокол Е-Е (Средно система за междинно протокол система, RFC 1195), предвижда концепция за подкрепа на IP подмрежа, променлива маска на подмрежата, маршрутизация въз основа на стойността на полето "вид услуга" в пакета IP-горен и идеята за външна маршрут.
Е-Е протокол е динамична маршрутизация протокол построен на върха на SPF-алгоритъм.

4.3. Външна врата протокол

Външни протоколи за маршрутизация са предназначени предимно за комуникация между автономни (независими) системи.

Протокол EGP (Външен Gateway Protocol) е един от най-известните протоколи от този тип (RFC 827, 888, 904, 911, 1092, 1093).
RFC документ 827, предложен първият модел портал за взаимодействие с входове за други автономни системи, както и документ, RFC 888, което е развитието на този модел, налага значителни ограничения върху топологията на мрежата на Интернет, като се предполага едно дърво двустепенна структура, в основата на която е така наречената "гръбнак" автономна система състоящ се от "основни" шлюзове.
Основното предимство на този модел на образование се счита за невъзможно в едно дърво топологични структура на циклична маршрут между автономни системи.

С EGP протоколни шлюзове могат да обменят помежду си информация за достижимост на съседните шлюзове и шлюзове към съседните турове. В изпълнение на тази динамична изчисление на маршрута само шлюзове гръбнак автономна система, а след това резултатите могат да бъдат комуникирани nontrunk шлюзове.
Не-далечна Gateways могат да предоставят на маршрута за предаване на информация и nontrunk шлюзове, но те нямат право да преминават по маршрутите са изчислени въз основа на информация, получена от други портали. Това ограничение често е наричан ограничение на разпространението на "третата група".
EGP протокол включва механизъм за определяне на достижимост съседи (съседна наречени шлюзове, съвместно работещи EGP протокол) за контрол и осигуряване на достъпност за обмен на информация под формата на съобщение за актуализация. Целта на използването на достъпност алгоритъм - уверете се, че един съсед работи и може да предостави достоверна информация.
Не по-малко важна е задачата на филтриране на информацията, преди да го изпратите на други портали, за да се избегнат ненужни промени в базата данни.

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

, BGP (Border Gateway Protocol, RFC 1267) - протокол за маршрутизация между автономни системи в Интернет; тя е изградена въз основа на опита, натрупан в работата на протокол EGP.
Основната цел на BGP - за намаляване на транзитния трафик. Протоколът BGP използва удължена концепция за автономна система. В този случай, в рамките на една автономна система шлюзове могат да използват различни протоколи за маршрутизация и няколко показателя. Въпреки това, в рамките на автономната система трябва да бъде единен план за маршрутизиране позволява автономна система се разглежда като едно цяло.

BGP се използва като TCP протокола транспортен протокол.
хост компютър операционна BGP протокол, не е задължително да са в същото време е врата.
Компютърът хост, който не е врата могат да обменят информация за маршрутите с шлюзове, използвайки протокола EGP или вътрешна маршрутизация протокол.
Този хост компютъра, може да използвате протокола BGP за обмен на информация за маршрутите с друга граница портал автономна система.

Фиг. 4.1. на рутера архитектура

Фиг. 4.2. Обработка на входния порт