9-ma’ruza. Marshrutizatsiya algoritmlarning klassifikatsiyasi va ularga qoʼyiladigan talablar

BIRTH:
11 May 1930, Rotterdam, The Netherlands (Gollandiya)
DEATH:
6 August 2002, Nuenen, The Netherlands.
Эдсгер Вибе Дейкстра машҳур
дастурчи ва назарий физик
Флойд алгоритми - йўналтирилган графнинг барча баландликлари орасидаги энг қисқа масофани топиш учун динамик алгоритм ҳисобланади. У 1962 йилда Роберт Флойд томонидан ишлаб чиқилган, 1959 йилда Бернард Рой (Bernard Roy) худди шу алгоритмни эълон қилган бўлса-да, аммо бу аҳамиятсиз бўлиб қолди.
Бу алгоритм Дейкстри алгоритмига қараганда умумийроқ ҳисобланади, чунки у исталган иккита тармоқ тугунлари орасидаги энг қисқа йўлларни топади. Бу алгоритмда тармоқ n сатрлар ва n устунларга эга бўлган квадрат матрица шаклида берилган. (i, j) элемент i тугундан ј тугунгача бўлган dij масофага тенг, у агар (i, j) ёй мавжуд бўлса чекли қийматга эга ва акс ҳолда чексизликка тенг бўлади.
Дейкстра алгоритми
Флойда алгоритми
Энг яқин маршрут: R1→R3→R6→R5→R9
Маршрутизация алгоритмлари турлари бўйича қуйидагича таснифланиши мумкин:

• Статик ёки динамик;
• Битта маршрутли ёки кўп маршрутли;
• Бир даражали ёки иерархик;
• Бош ҳисоблаш машинаси ёки маршрутизатордаги интеллектли;
• Домен ичида ёки доменлараро;
• Канал ҳолати ёки масофа вектори алгоритмлари.

Статик ёки динамик алгоритмлар
Статик маршрутизация алгоритмлари маршррутизация жадвалларининг тақсимотини маршрутизация бошлангунча тармоқ маъмури томонидан ўрнатилади. Статик маршрутизация алгоритмлари тармоқдаги ўзгаришларга таъсир эта олмайди, улар доимо ўзгарадиган замонавий йирик тармоқлар учун яроқсиз ҳисобланади.
Динамик маршрутизация алгоритмлари тармоқнинг ўзгариши ҳолатларига реал вақт режимида мослашади. Улар бири-бирларига жўнатадиган маршрутизация параметрларининг янгиланиши ҳақидаги хабарларни таҳлил қилиш йўли орқали бажаради.

Бир маршрутли ёки кўп маршрутли алгоритмлар
Айрим маршрутизация протоколлари қабул қилиш пунктига маршрутларни кўп томонламалигини таъминлайди. Бундай кўп маршрутли алгоритмлар кўп сонли линиялар бўйича трафикни мультиплексрли узатишни мумкин қилади. Кўп маршрутли алгоритмларнинг афзаллиги маълум, улар сезиларли катта ўтказиш қобилияти ва ишончлиликни таъминлаши мумкин.