INF3190 - Hjemmeeksamen 2 - Vår 2013
Nettverkslaget
Formelt
Denne oppgaven er karaktergivende og skal løses individuelt.
Karakteren som gis teller omlag 20 % på sluttkarakteren. Oppgaven blir vurdert etter hvor stor grad kravene i avsnittet "Oppgave" er oppfyllt.
Oppgave
I denne oppgaven skal du bygge videre oppå linklaget. Linklaget skal ikke benytte seg av bridgingfunksjonaliteten implementert i hjemmeeksamen 1. Du skal i stedet lage et nettverkslag med fullstandig rutingfunksjonalitet (lag 3).
To maskiner skal fremdeles kunne kommunisere med hverandre på tvers av flere maskiner. Nå skal maskinene som bare videresendte data fra senderen til mottakeren ta rollen som rutere og ikke som broer. Alle maskiner skal kunne fungere både som endesystem og som ruter. Rutingmekanismen som skal implementeres på nettverkslaget er Link State Routing. Nettverkslaget skal tilby pålitelig ende-til-ende kommunikasjon til transportlaget (lag 4).
Den sentrale delen av oppgaven er å implementere Link State Routing (LSR). Du skal implementere en rutingprotokoll på nettverkslaget som oppdaterer rutingtabeller slik LSR krever det. Rutingen skal skje dynamisk. For å kjenne den aktuelle avstanden til en direkte nabo må ruteren periodisk sende en pakke til naboen som blir besvart umiddelbart (ping). Dette er for å måle tiden det tar før svaret kommer fram. Rutingen på nettverkslaget må kunne håndtere løkker i nettet.
LSR-avstandsmålingspakker kan gå forbi nettverkslagets egne køer, men ingen rutingpakker skal gå forbi flytkontrollen på linklaget. Nettverkslaget (lag 3) skal ikke røre linklaget (lag 2).
Bridgingfunksjonene som var påkrevd i oppgave 2 kan enten kobles ut (#ifdef), eller slettes fra koden.
Det er ønskelig at du bygger på linklaget fra hjemmeeksamen 1. Gyldig flytkontroll i denne oppgaven er stop-and-wait eller bedre (enten den fra H1 eller du kan implementere en ny på L2). Det gis ikke ekstrapoeng for implementasjon av mer avansert flytkontroll.
Flere detaljer om funksjonene l3_send og l3_recv finnes i avsnitt Spesifikke krav til implementasjonen.
Mekanismene skal implementeres som del av et program som kan følgende:
-
Opprette "fysiske linker" mellom maskiner. Dette skal skje som i hjemmeeksamen 1. Linkslagsadresse og nettverkslagsadresse kan gjerne være like, men ruting må baseres på nettverkslagsadresser.
-
Ta imot input fra tastaturet og prosessere inputlinjer.
-
Hvis inputlinjen begynner med ordet "QUIT" skal programmet avsluttes.
-
Hvis inputlinjen begynner med ordet "CONNECT" skal det forventes at linjen har formen "CONNECT <hostname> <portnummer> ". Dette skal brukes for å opprette en "fysisk link" til den andre maskinen (det kan også være programmet som kjører en gang til på den samme maskinen med et annet portnummer)
-
Hvis inputlinjen begynner med ordet "SEND" skal det forventes at linjen har form "SEND <destinasjon> <filnavn>. Filnavnet skal være navnet til en fil som skal leses inn, overføres over nettet til prosessen på maskinen som kan finnes med adressen <destinasjon>. Filen skal lagres på disk på mottakermaskinen. Det er hensiktsmessig med en liten protokoll som overfører filnavn, start- og sluttmarkering, men en slik protokoll inngår ikke i poengfordelingen.
-
-
Nettverkslaget skal periodisk oppdatere rutingtabeller. Rutingalgoritmen som brukes skal være Link State Routing. Dette inkluderer måling av avstand mellom direkte nabomaskiner som en del av rutingprosessen. Maskiner inngår i rutingprosessen så snart de er koblet opp med CONNECT.
-
Nettverkslaget skal utføre forwarding av pakker i henhold til den aktuelle rutingtabllen.
-
For å levere data til høyere lag skal du bruke en funksjon l4_recv.
Oppgavebeskrivelse
Spesifikke krav om implementasjonen
Opprettelse av den emulerte "fysiske linken"
Dette er ikke noen del av denne oppgaven eller karaktergivende for denne oppgaven. Det er anbefalt å følge oppskriften fra den første oppgaven. Løsningen skal bygge på din egen kode fra hjemmeeksamen 1 eller prekoden. Begge alternativene vil kunne gi full uttelling.
l3_send
int l3_send(int dest_address, const char* buf, int length);
l3_send kalles av transportlaget for å sende data. Parameteret dest er nettverksadressen til mottakermaskinen. l3_send tar imot data fra transportlaget, legger til nettverkslagsheadere, finner den første maskinen på veien til mottakeren som pakken må sendes til og kaller linklagsfunksjoner for å sende pakken.
l3_recv
int l3_recv(int mac_address, const char* buf, int length);
l3_recv kalles av linklaget hvis den har mottatt en ny ramme.
l3_recv kalles med en pakke om gangen. l3_recv finner ut om dette er en pakke som tilhører rutingprotokollen, om det er en datapakke som må sendes videre til en annen maskin eller en datapakke adressert til seg selv. For datapakker adressert til seg selv kalles l4_recv med innholdet. Alle andre pakker håndteres slik LSR krever det.
Besvarelse
Dere skal levere følgende:
-
Et design dokument som inneholder:
-
En frontside med kandidatnummer, oppgavetittel, kurs og semester, vi vil ikke ha navn eller brukernavn. Bruk idchecker.sh slik som i forrige oppgave
-
En forklaring på implementasjonen av Link State Rounting
-
En diskusjon rundt grunnene for å utføre dynamisk ruting med LSR. Forklar hvorfor avstandsmålinger er relevant og hva slags fordeler og ulemper bruk av målingsbasert dynamisk ruting innebærer.
-
Hvordan programmet er designet. Gjerne med en tegning (flytdiagram) som viser hvilken rekkefølge de forskjellige funksjonene blir kalt.
-
En dokumentasjon av hvordan programmet skal startes evt. avsluttes.
-
Hvilke filer programmet består av (C filer, headerfiler osv.).
-
-
Programfilene, hvor koden er fyldig kommentert. Dokumenter alle variable og definisjoner. For hver funksjon i programmet skal følgende dokumenteres:
-
Hva funksjonen gjør
-
Hva inn og ut parametre betyr og brukes til
-
Hvilke globale variable funksjonen endrer
-
Hva funksjonen returnerer
-
Om poengfordelingen
-
Du kan bruke de samme verdiene for MAC-, nettverks- og transportadressen. Transportlaget er veldig enkelt og utfører ikke multiplexing-oppgaven som transportlaget har i virkelige operativsystemer - alt leveres til samme applikasjon.
-
En ruter har to oppgaver: Ruting og forwarding. Forwarding ligner veldig på videresending i en bro som du utviklet i hjemmeeksamen 1. Forwardingdelen er derfor ikke spesielt viktig. Hovedvekten ligger på LSR implementasjonen samt avstandsmåling.
-
Det gis ikke ekstrapoeng for ekstra funksjonalitet på linklaget.
-
Det gis ikke ekstrapoeng for ekstra funksjonalitet på transportlaget.
-
Det gis ikke poeng for en applikasjonslagsprotokoll som du kanskje skriver for å overføre filnavn og markere start og slutt av filen.
-
Korrekt bruk av Dijkstra shortest path for å regne rutingtabellene vil kunne gi ekstrapoeng.
Spesifikke krav til koden
Koden deres skal kompilere og vil bli testet på IFIs login-maskiner (login.ifi.uio.no).
Orakeltjeneste og administrative spørsmål
Får dere problemer under implementasjonen anbefaler vi dere å sjekke FAQ på orakelsiden som ligger under INF3190 sin hjemmeside. Dere kan også sende en mail til orakel med adressen inf3190-orakel [at] ifi [dot] uio [dot] no
For administrative spørsmål rundt hjemmeeksamen, ta kontakt med naeemk [at] ifi [dot] uio [dot] no
Levering
Designdokumentet skal skrives vha. et egnet verktøy, for eksempel LaTeX, Word, etc. Dokumentet skal inneholde besvarelsen og de etterspurte figurer, samt ha en forside hvor følgende opplysninger er angitt: kandidatnummer, oppgavetittel, kurs og semester
Før levering skal dokumentet konverteres til PDF format.
Omfanget av dokumentet trenger ikke nødvendigvis være så stort, men må inneholde tilstrekkelig informasjon til å oppfylle kravet som beskrevet under avsnittet oppgave. Vi stiller krav til ryddighet og struktur.
Elektronisk innlevering: Alt skal leveres elektronisk hvor alle filer (Makefile, *.c, *.h, README.pdf, etc.) er samlet i en katalog. Bruk make handin til dette.
Den elektroniske innleveringen skal leveres via web. Linken finnes på kursets hjemmeside.
Innleveringsfrist: Søndag 19. mai 2013, klokken 23:59
Merk at denne tidsfirsten er HARD, oppgaver levert etter fristen vurderes med karakteren "F", altså stryk.
Det forutsettes at studenten har lest forskriften om studier og eksamener ved Universitetet i Oslo, karaktergivende oppgave.