Cuprins
- 1. Introducere 3
- 2. Prezentarea problemei ...4
- 3. Algoritmul lui Dijkstra modificat ..7
- 4. Metoda bisecției 8
- 5. Rezultate experimentale 9
- 6. Anexe ..10
- 7. Bibliografie .18
Extras din proiect
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.
Bibliografie
1. http://www.vogella.com/tutorials/JavaAlgorithmsDijkstra/article.html
2. https://stackoverflow.com/questions/29757931/optimization-for-dijkstra-requiredunique-
algorithm
3. https://codereview.stackexchange.com/questions/67704/optimizing-dijkstraimplementation-
using-priorityqueue-in-java
4. http://www.cs.umd.edu/class/spring2004/cmsc420/sp04-part3v04/node44.html
Preview document
Conținut arhivă zip
- Optimizarea protocolului OSPF pentru traficul de live video si voce.pdf