Tehtävänanto

Ad-hoc verkon reititystaulu

Ns. ad-hoc verkko on mobiililaitteiden yhdessä muodostama yhteydenpitomenetelmä, eräänlainen tietoverkko, jossa ei ole keskitettyä hallintoa tai olemassaolevaa infrastruktuuria kuten kiinteässä verkossa.  Kun tällaisessa verkossa jokin laite haluaa lähettää tietoa toiselle laitteelle, ei ole olemassa valmiita tietorakenteita, joista heti tiedettäisiin, mitä kautta sanoma kannattaa reitittää.  Reittitieto joudutaan rakentamaan dynaamisesti.

Toiminnan perusperiaate on seuraava.  Oletetaan, että kone A haluaa lähettää viestin koneelle B, mutta kone B ei ole A:n läheisyydessä, vaan viestin tulee kulkea yhden tai usemman välisolmun kautta.

• A lähettää viestin kaikille A:n lähistöllä oleville koneille C_i, että etsitään reittiä B:hen.
• Jos jokin kone C_k tuntee voimassa olevan reitin B:hen, se lähettää tästä tiedon A:lle.  A lähettää tällöin sanoman C_k:lle luottaen siihen, että C_k osaa lähettää viestin A:n viestin eteenpäin oikeaa reittiä pitkin. 
  
• Muussa tapauksessa jokainen kone C_i lähettää vastaavasti omaan lähiympäristöönsä viestin, että A haluaa lähettää viestin B:lle.   Samalla C_i tallettaa itselleen tiedon, että sillä on yhteys A:han.  Jos  jokin C_i:n lähellä oleva kone D_i tietää reitin B:n,  se pystyy nyt lähettämään reitin löytymisestä tiedon A:lle.
• Näin edetään, kunnes yhteys löytyy, tai B:tä ei löydy lainkaan.
• Koko reittiä ei siis talleteta mihinkään solmuun, vaan jokainen solmu tietää, mihin suuntaan tietyltä koneelta toiselle lähetetty viesti tulee lähettää.
• Mikään kone ei lähetä uudestaan reitin etsintään, tai korjaukseen kuuluvaa viestiä, jonka se on kuullut jo aikaisemmin, jotta toimenpiteissä ei syntyisi silmukoita.
• Koska reittikyselyjä voi tulla runsaasti, niin kyselyihin liittyvät tiedot vanhentuvat.  Ts. jos jossakin koneessa C_i on tieto reitin etsimisestä B:hen, eikä C_i saa määräajan kuluessa tietoa reitin löytymisestä, C_i poistaa hakutiedon omista tietorakenteistaan.
• Olemassa oleva reitti voi katketa, jos jokin sen varrella oleva kone poistuu käytöstä tai etenee niin kauas, ettei pysty enää pitämään yhteyttä reittipolulla oleviin naapurikoneisiin.  Tällöin reitin rikkoutumisen huomaavan koneen on lähetettävä muille koneille tieto reitin rikkoutumisesta. Kone A voi tämän jälkeen aloittaa uuden reitin etsinnän.
• Koska verkko on luonteeltaan dynaaminen, on jokaisella reitillä voimassaoloaika, eikä vanhentuneita reittejä saa käyttää. Vanhentuneet reitit uusitaan hakemalla reitti uudestaan.

Reittien etsintään ja ylläpitoon liittyy kolmenlaisia viestejä. Route Request (RREQ) on viesti, jonka kone lähettää halutessaan löytää reitin. Route Reply (RREP) on vastausviesti RREQ-viestiin. Route Error (RERR) on ilmoitus reitin rikkoutumisesta.

Route Request

RREQ-viestissä on seuraavat kentät:

• Määränpääkoneen osoite. Sen koneen osoite, jonne reittiä haetaan.
• Määränpääkoneen aikaleima. Kertoo, mikä on viimeisin lähettäjäkoneen tuntema (mahdollisesti vanhentunut) reitti määränpääkoneeseen. Tyhjä, jos lähettäjäkoneella ei vielä minkäänlaista reittiä määränpääkoneeseen.
• Lähettäjäkoneen osoite. Sen koneen osoite, joka etsii reittiä määränpääkoneeseen.
• Lähettäjäkoneen aikaleima. Kertoo, milloin lähettäjäkone on lähettänyt tämän viestin.
• Edellinen solmu. Sen koneen osoite, josta tämän kone sai RREQ-paketin.

RREQ-viestin aikaleimojen avulla estetään vanhentuneiden reittitietojen käyttö. Kone, joka tuntee reitin haluttuun määränpääkoneeseen saa lähettää tiedot tuntemastaan reitistä vain, jos sen tuntema reitti ei ole vanhentunut ja sen aikaleima on uudempi kuin RREQ-viestissä oleva. Muussa tapauksessa koneen on lähetettävä RREQ-viesti eteenpäin.

Route Reply

RREP-viestissä on seuraavat kentät:

• Määränpääkoneen osoite. Sen koneen osoite, jonne reittiä on haettu.
• Määränpääkoneen aikaleima. Sen reitin aikaleima, jota tämä RREP-paketti edustaa.
• Lähettäjäkoneen osoite. Sen koneen osoite, joka alunperin lähetti reitinetsintäpyynnön.
• Elinaika. Kertoo kuinka kauan tämä reitti on voimassa.
• Edellinen Solmu. Sen koneen osoite, josta tämän kone sai RREP-paketin.

Elinaika alkaa määränpääkoneen aikaleimasta.

Route Error

RERR-viestissä on seuraavat kentät:

• Määränpääkoneen osoite. Kertoo mihin koneeseen rikkoutunut reitti johti.
• Määränpääkoneen aikaleima. Rikkoutuneeseen reittiin liittyvä aikaleima.
• Edellinen Solmu. Sen koneen osoite, josta tämän kone sai RERR-paketin.

Viestien välitys

Viestien välitys solmujen välillä voidaan olettaa virheettömäksi. Voidaan myös olettaa, että solmut osaavat ratkaista mahdolliset konfliktitilanteet (esimerkiksi kaksi solmua lähettää viestin samalle vastaanottajalle yhtä aikaa) järkevästi. Lis�äksi solmuilla on keino löytää ja pitää kirjaa naapurisolmuistaan. Naapurisolmujen v�älisen viestien lähetyksen ja vastaanoton rajapinta on seuraava:

• Recieve(message,nodeid) vastaanottaa viestin message naapurisolmulta nodeid.
• Send(message,nodeid) lähettää viestin message naapurisolmulle nodeid.
• Send(message) yleislähettää viestin message kaikille kuuluvuusalueella oleville solmuille.

Tehtävänanto

Suunnitelkaa tietorakenteet ja algoritmit, joilla solmussa olevat reittitiedot ja sanomien lähetystiedot ylläpidetään em. tilanteissa.

Kiinnittäkää huomiota seuraaviin asioihin:

• Mallintakaa viestit tietueina, luokkina, tms.
• Esittäkää reittiteitoja manipuloivat algoritmit. Algoritmien tulisi käyttää hyväkseen kurssilla esitettyjä abstraktioita.
• Mallintakaa käyttämänne abstraktiot.
• Pohtikaa eri vaihtoehtoja abstraktioiden toteuttamiseen ja analysoikaa eri vaihtoehdot.
• Rinnakkaisuuden hallintaa ei tarvitse ottaa huomioon.
• Viestien välityksen rajapintaa ei tarvitse mallintaa.