Компютърни мрежи



жүктеу 1.86 Mb.
бет17/23
Дата26.02.2018
өлшемі1.86 Mb.
1   ...   13   14   15   16   17   18   19   20   ...   23

5.3.Методи за маршрутизация.


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

Методите за маршрутизация се класифицират в две големи групи

а) Каталожни методи (стратегии)

б) Безкаталожни методи (стратегии)

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

5.3.1.Безкаталожни методи.


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

5.3.1.1.Метод с “наводнение” на пакетите.


Принципа на метода е представена на фиг.5.4


S@



Комуниакционна подистема



1

1

1


1

1





D@



1


Фиг. 5.4


Целта на метода да осигури пренос на пакети от мрежовия адрес-източник S@ до целевия мрежов адрес - D@ . Пакет #1 се предава по мрежовото съединение. За всеки възел, който получи този пакет се изпълнява размножаване и изпращане на копия на този пакет по всички изходни портове на текущия възел. Тези копия “наводняват” цялата мрежа. Първото пристигнало копие в D@ е преминало по най-“късия” път (оптималния матшрут). Този извод е аксиоматичен и не зависи от топологията, от производителността на възлите и пропускателната способност на линиите. След достоверното получаване на пакет #1 в възел D@ в мрежата продължават да се разпространяват копия на пакет #1. Тези копия натоварват комуникационната подсистема, без това натоварване на има приложен смисъл. Поставя се въпроса за ограничаване на разпространението на “паразитни” копия вече достоверно приетите пакети. Познати са два подхода за намаляване на броя на “паразитно” разпространяващите се пакети:

  • Подход с въвеждане на време на “живот” на пакета. За всеки пакетите се дефинира време на “живот”. Времето на “живот” се избира като стойност на базата на статистическа оценка – определят се най-отдалечените точки (възли) в мрежата и времето необходимо пакета да достигне до тях като това време е умножава по мащабен коефициент, изменящ се в интервала от 1,5 до 2,0. В тялото на пакета се записва времето за генериране на пакета, т.е. се запомня, кога е “роден” пакета. Ако при получаване на пакет в определен възел разликата от текущото време и времето на “раждане” е по-голяма от зададеното време на”живот”, то този пакет не се предава по изходните портове (пакета се “убива”). По този начин след изтичане на времето на “живот” в мрежата се остават “паразитни” копия на конкретния пакет;



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

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




5.3.1.2.Метод със “ случайна” маршрутизация.


М
Пакет #1

30 % от копията
етода е развитие на метода с “наводнение” на пакети – фиг.5.5.


Изх.1




Възел N


Пакет #1

Вх.1

Изх.2

Пакет #1

30 % от копията



Изх.3

Пакет #1

40 % от копията


Фиг.5.5


    При случайната маршрутизация подобно на “наводнението” копия на приетият пакет #1 се излъчват по всички изходни портове. Особеността при случайната мршрутизация е, че по изходните портове копията се излъчват с определена вероятност. Например, за Възел N (фиг.5.5) от пристигащите 100 пакета, копия на 30 от тях се излъчват по изход 1( с вероятност 30%), 30 – по изход 2 (с вероятност 30%) и 40 – по изход 3 (с вероятност 40%). Конфигурирането на изходните портове на възлите с определени стойности на вероятността за излъчване на пакети е възможност за пренасочване на трафик към зони с по-малко натоварване. Методът е като принцип е близък до метода с “наводнение” на пакетите. Усъвършенстванията са в посока управляемост на общото натоварване в мрежата и пренасочване на трафика към не натоварените зони В резултат на случайната маршрутизация се увеличава средната дължина на маршрутите и се създават условия за пресрочване на времето на “живот” преди пакета да е достигнал до целевия адрес.


5.3.2.Каталожни методи.


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

Видове каталози

А.От гледна точка на времето на валидност на каталозите те се разделят на статични и динамични каталози:


  • Статичен каталог

Когато таблицата, която описва състоянието и параметрите на комуникационната подсистема е постоянна за дълъг период от време, то тя се нарича статична(статичен каталог). Каталогът се генерира веднъж, основавайки се на модела на мрежата - тегловен граф. Информацията в каталога се натрупва при анализ на графовия модел и решаване на задачата за намиране минимални свързващи маршрути. В зависимост от избора на метрична оценка на теглото на дъгите (комуникационните линии) и възлите (транзитната времезадръжка във ретранлсиращите РОС) каталога позволява маршрутизиране по различни критерии.

  • Динамичния каталог

Когато таблицата се актуализира през малки интервали от време с цел адаптиране към текущо състояние на мрежата, то тя се нарича динамична. Интервала време на валидност на каталога се нарича слот. По време на слота се натрупва статисктика за състоянието на мрежата. На базата на тази статистика се построява графовия и се преизчислява новото състояние на каталога. Актуализираният каталог се прилага за целите на маршрутизирането по времето на следващия. В момента t0 се генерира началната версия на каталога Т1. По време на слота С1 (t1- t0) се натрупва статистика по която се прогнозира състоянието на мрежата за следващия слот С2 (t2- t1) и се актуализира каталога Т1 до новата версия – Т2 – фиг.5.6.


Каталог Т1

Статистика за слот С2

Каталог Т2

Статистика за слот С3

Каталог Т3

Статистика за слот С4





..



Слот С1

Слот С2

Слот С3



t

t0

t1

t2

t3

tn

Фиг. 5.6


Процеса се повтаря циклично. Един от базовите проблеми на този метод е продължителността на слота. При “къс” слот, адаптивността на протокола е по-ефективна, тъй като прогнозата от статистиката е валидна за по-малък период от време и вероятността за промяна на профила на информационното натоварване е минимална. Ефекта на “късия” слот предизвиква нарастване на изискванията за изчислителна мощност на ретранслационните РОС, тъй като актуализирането на каталозите е процес, консумиращ ресурси : процесорно време, буферно пространство и др.

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



В реалните мрежови конфигурации дължината на слота е функция на топологията на мрежата, приложните съединения и несиметричността на генерираното информационно натоварване. Опита показва[] , че в средата на ARPANET се прилага за определяне на размера на слота експериментален подход. Използват се група тестови съединения, като тестовете се провеждат при различни стойности на размера на слота и се следи кога се постига най-високо качество на мрежовото обслужване. На определени периоди от време слота се подлага на допълнително калибриране, което отразява общи тенденции в развитието на съответната преносна среда.

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




  • Частичният каталог съдържа информация на част от мрежовата конфигурация. Обикновено в текущия възел се съхранява каталог, съдържащ информация за маршрутите, преминаващи през този възел. Организацията е подобна на тази при съставяне на гаровите разписания за влаковете. На всяка гара има “извлечение” (частичен каталог) от общото разписание на влаковете, като се описват само влаковете (маршрутите), преминаващи през конкретната гара. Прилагането на частични каталози намалява обема на маршрутните таблици и ограниченията по отношение на ресурсите, необходими за обработка и съхранение на тези таблици в архитектурата на ретранслиращите РОС.

  • Пълният каталог съдържа информация за цялата мрежова конфигурация. Възлите в комуникационната система, на базата на пълни каталози притежават функционалността да маршрутизират независимо един от друг. Ако при използването на частични каталози маршрутизирането е “каскадно”. т.е. всеки текущ възел маршрутизира като определя кой е следващият възле по маршрута до целевия мрежов адрес, то при прилагането на пълен каталог е възможно маршрута за се запише в тялото на пакета, а възлите от маршрута да изпълняват “инструкциите” за маршрутизиране, съдържащи се в самия пакет. Недостатък на пълния каталог е адаптивността към промени в топологията и профила на информационното натоварване. От една страна консумацията на изчислителни ресурси е значителна (голям обем на информацията в каталога), от друга стана, каталога може да се приеме, че е актуализиран, едва когато всички негови копия са актуализирани. Съществен проблем при маршрутизирането би създала ситуация, при която част от възлите оперират с една версия на пълния каталог, а друга част – с друга..


Б.От гледна точка на управлението на процесите по съставяне и поддържане на актуалността на каталозите те се разделят на каталози с глобално(централизирано управление) и каталози с локално управление (локлани каталози):


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

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




Достарыңызбен бөлісу:
1   ...   13   14   15   16   17   18   19   20   ...   23


©kzref.org 2017
әкімшілігінің қараңыз

    Басты бет