Muistipohjaisen reititysalgoritmin luonti
Karhu, Tuomo (2019)
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:amk-2019052712055
https://urn.fi/URN:NBN:fi:amk-2019052712055
Tiivistelmä
Opinnäytetyössä oli tavoitteena kehittää uusi nopeampi reitinhakualgoritmi, joka toimisi nopeammin kuin A*-reitinhakualgoritmi. Algoritmia on tarkoitus käyttää ruutupohjaisessa pelikartassa. Tarkoitus oli kehittää reitinhakualgoritmi siten, että reittejä ei etsitä kartalta vaan ne haetaan suoraan muistista. Tämä säästää aikaa ja vähentää suorittimen työkuormaa. Muistipohjaisen reitinhakualgoritmin kehittämiseksi aluksi oli kuitenkin tutkittava, onko olemassa laitteita, jotka pitävät reittejä muistissa.
Tutkimme aluksi, miten Dijkstran-algoritmi ja sitä hyödyntävä A*-reitinhakualgoritmi toimii. Syvensimme tutkimusta selvittämällä, miten Dijkstran-algoritmia hyödynnetään tietoverkkotekniikassa. Tietoverkkotekniikassa reitittimet käyttävät useita eri reititinprotokollia, jotka hyödyntävät Dijkstran-algoritmia. Päädyimme tutkimaan OSPF-reititinprotokollaa, joka toimii hyvin samankaltaisesti kuin A*-reitinhakualgoritmi. OSPF-protokolla kuitenkin pitää kaikki reitit muistissa ja on siten haluamamme muistipohjaisen reitinhakualgoritmin kaltainen. OSPF-protokollan pohjalta kehitimme oman protokollan, jolla kartan ruudut eli noodit pystyivät vaihtamaan reittitietoja keskenään. Tämä oli avaintekniikka, jolla pystyimme luomaan muistipohjaisen reitinhakualgoritmin.
Muistinkäyttö osoittautui kuitenkin haastavaksi, joten tiivistimme reittilistaa alueilla. Jaoimme kartan alueisiin IP-osoitteiden verkon osoitteiden kaltaisesti. Tämä tekniikka vähensi muistinkäyttöä riittävästi, että reitinhakualgoritmi voitiin todeta toimivaksi.
Opinnäytetyön tuloksena valmistui reitinhakualgoritmi, joka on moninkertaisesti A*-reitinhakualgoritmia tehokkaampi. Ainoaksi heikkoudeksi osoittautui kartan latauksen hitaus. Reittien muodostus vie aikansa ja hidastaa siten kartan latausaikaa. Muistinkäyttö on kuitenkin aluejaon ansiosta sopivan pieni.
Tutkimme aluksi, miten Dijkstran-algoritmi ja sitä hyödyntävä A*-reitinhakualgoritmi toimii. Syvensimme tutkimusta selvittämällä, miten Dijkstran-algoritmia hyödynnetään tietoverkkotekniikassa. Tietoverkkotekniikassa reitittimet käyttävät useita eri reititinprotokollia, jotka hyödyntävät Dijkstran-algoritmia. Päädyimme tutkimaan OSPF-reititinprotokollaa, joka toimii hyvin samankaltaisesti kuin A*-reitinhakualgoritmi. OSPF-protokolla kuitenkin pitää kaikki reitit muistissa ja on siten haluamamme muistipohjaisen reitinhakualgoritmin kaltainen. OSPF-protokollan pohjalta kehitimme oman protokollan, jolla kartan ruudut eli noodit pystyivät vaihtamaan reittitietoja keskenään. Tämä oli avaintekniikka, jolla pystyimme luomaan muistipohjaisen reitinhakualgoritmin.
Muistinkäyttö osoittautui kuitenkin haastavaksi, joten tiivistimme reittilistaa alueilla. Jaoimme kartan alueisiin IP-osoitteiden verkon osoitteiden kaltaisesti. Tämä tekniikka vähensi muistinkäyttöä riittävästi, että reitinhakualgoritmi voitiin todeta toimivaksi.
Opinnäytetyön tuloksena valmistui reitinhakualgoritmi, joka on moninkertaisesti A*-reitinhakualgoritmia tehokkaampi. Ainoaksi heikkoudeksi osoittautui kartan latauksen hitaus. Reittien muodostus vie aikansa ja hidastaa siten kartan latausaikaa. Muistinkäyttö on kuitenkin aluejaon ansiosta sopivan pieni.