Optimizarea protocolului OSPF pentru traficul de live video și voce

1. Introducere

Problema comis-voiajorului este una dintre cele mai vechi probleme de optimizare putând fi

prezentă într-un număr foarte mare de feluri, în diverse domenii, existând diverse metode de

rezolvare, optimizare după diverse criterii, în funcție de interesele domeniului și al

implementării efective.

Problema celui mai scurt drum între două noduri a fost rezolvată inițial prin atribuirea unei

valori reprezentative, cuantizate, fiecărui drum posibil între cele două, însumarea acestor valori

pentru toate drumurile posibile și alegerea celei mai mici valori. Problema s-a pus întotdeauna

legat de modul în care este cuantizată acea valoare atribuită legăturilor dintre noduri - muchiilor

- întrucât acesta reprezenta parte din procesul de optimizare. În mod evident, pentru orice tip

de problemă procesul de cuantizare trebuie să difere, întrucât factorii ce sunt luați în considerare

și ponderea acestora poate să se deosebească chiar și între două probleme din același domeniu

(de exemplu: transportul).

În realitate, pentru un transport între două puncte geografice, indiferent că sunt reprezentate de

țări diferite sau locații în cadrul aceluiași oraș, nu mai este suficient să luam în considerare doar

distanța în kilometri între acestea, întrucât intervin un număr foarte mare de factori - consumul

de carburant al modului ales de transport, vremea de pe traseu, traficul, încărcătura transportată

și multe alte detalii asemănătoare.

În cadrul lucrării noastre ne interesează să folosim algoritmul lui Dijkstra aplicat pentru

problemele de rutare în cadrul rețelelor de calculatoare. Plecând de la ideea de bază a

funcționării protocolului OSPF (Open Shortest Path First), ne dorim să luăm în considerare și

factorul întârzierii (delayului) pe lângă cel folosit de acesta - și anume lățimea de bandă.

OSPF-ul este un protocol modern, open-source, de rutare ce folosește lățimea de bandă pentru

a calcula cele mai scurte drumuri pentru fiecare pachet în parte. Acesta se diferențiază de alte

protocoale de rutare prin faptul că oferă o vedere de ansamblu asupra întregii topologii a unei

rețele, stocând o bază de date la nivelul fiecărui router în parte. Pe scurt, din absolut orice punct

al topologiei, se poate calcula cel mai scurt/eficient drum între orice două puncte, pe baza

informațiilor acumulate până la momentul respectiv. Baza de date este actualizată în

permanență de către routere cu ajutorul unor mesaje de tip LSA (Link State Advertisements) ce

asigură sincronizare între routere de fiecare dată când apare o modificare în topologia (crește

valoarea asociată unei legături, este adăugat un nou router etc.)

Pe scurt, OSPF reprezintă o implementare a algoritmului lui Dijkstra, ce folosește suma

lățimilor de bandă între două puncte pentru a calcula cel mai eficient drum între orice două

puncte. Ne propunem să eficientizăm în continuare să folosim acest proces, luând în considerare

și delay-ul introdus de fiecare router și folosind metoda bisecției, într-o formă mai restrânsă,

întrucât nu avem o ecuație cu care să lucrăm, nu putem efectua derivata

2. Prezentarea problemei

Am ales optimizarea în funcție de delay întrucât în zilele noastre, două tehnologii foarte

importante, depinde enorm de acesta: mai exact transmisia de voce și streaming-ul live video.

Dacă în linii mari, o viteză bună de transmisie a datelor este suficientă pentru a încărca datele,

în cadrul unei transmisii în timp real, delay-ul influențează într-o măsură destul de mare

calitatea transmisiei.

Pentru a putea beneficia de o transmisie de calitate a vocii, este necesar un delay constant în

cadrul întregului proces de comunicare, pentru a evita efectul de jitter (delay care variază foarte

mult și determină pachetele să ajungă la destinație într-o altă ordine decât au fost trimise). De

asemenea, valoarea acestui delay trebuie să fie relativ mică, pentru a nu deranja urechii umane.

Scopul final al lucrării este acela de a diferenția importanța delay-ului în cadrul unei

transmisiuni în funcție de datele ce sunt încapsulate și trimise între două puncte. Această

importanță este dată de către routere, care au acces la conținutul pachetului și la prioritatea

acestuia - în funcție de prioritate se poate stabili și tipul de date. Mai exact, în cadrul

transmisiunii unor date de tip HTTP, FTP, e-mail etc. delay-ul nu este foarte relevant, iar o

oarecare întârziere în transmisia pachetelor nu poate deranja utilizatorul mediu, deci importanța

acestuia ar trebui să fie scăzută. Totuși, în momentul în care este detectat un flow de date de

voce sau de streaming live video, importanța delay-ului crește iar calculul ”distanțelor” trebuie

recalculat în mod corespunzător.

Pentru prezentarea implementării realizate până la momentul actual, a fost folosită o topologie

teoretică în care sunt folosite 30 de routere - abordarea problemei poate fi însă adaptată pentru

topologii de dimensiuni mai mici sau mai mari.

Algoritmul OSPF se diferențiază de alte protocoale (RIP, IGRP, EIGRP) prin faptul că lucrează

cu o bază de date în care se păstrează o vedere de ansamblu asupra topologiei - această bază de

dată trebuie să se păstreze pe toate echipamentele sincronizată în orice moment de timp. La

momentul actual, în cadrul acestei baze de date, sunt păstrate distanțele către orice punct din

topologie, calculul acestora raportându-se doar la lățimea de bandă (mai exact, se adună lățimea

de bandă corespunzătoare întregului traseu între două puncte și se împarte la o valoare de

referință: 106). În cadrul propunerii de optimizare, ar urma sa fie stocate două baze de date la

nivelul fiecărui router în parte, pentru cele două tipuri de date propuse anterior.

Pentru simplificarea problemei, în cadrul topologiei, am presupus cele 30 de routere

interconectate în mod direct.