INF3190 - Hjemmeeksamen 1 - V?r 2013
Bridging p? linklaget

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" og ¡±Oppgavebeskrivelse¡± er oppfylt.

Utleverte filer

Det er mulig ? bruke oblig-koden, men du m? oppdatere noen filer. Se NOTES.txt for hva som m? endres. Det er ogs? mulig ? begynne fra bunnen om man ?nsker. Delayed_sendto og receiver kan forventes at blir erstattet etter innlevering med originale filer hvis disse er endret.

Oppgave

I denne oppgaven skal du implementere linklagskommunikasjon mellom flere maskiner p? linklaget. Alle maskiner skal virke b?de som endesystem og som bro. Linklaget skal tilby p?litelig full dupleks kommunikasjon som tjeneste til h?yere lag.

Du skal forutsette et "fysisk lag" (lag 1) som kan miste rammer (~20% pakketap), men som er fritt for bitfeil og som ikke kan forandre rekkef?lgen av rammer (kan forekomme om du sender pakkene over nettet!). Du kan ogs? forutsette at det eksisterer l?kker (loops) p? linklaget og du m? derfor implementere mekanismer som h?ndterer dette ved hjelp av for eksempel TTL.

Det er lov til ? implementere flytkontrollen med Stop-and-wait, Go-Back-N eller Selective Repeat. Stop-and-wait vil gi redusert uttelling.

For glidende vindu: vinduet skal ha plass for opp til 10 rammer.

Rammest?rrelsen er p? 100 bytes og en pakke sendes per 200 ms. Delayed_sendto kan kun ha 10 utest?ende rammer.

Du skal ogs? legge inn st?tte for sirkul?re nettverk slik at ingen pakker ender opp med ? bli sendt for evig. Dette skal gj?res ved bruk av TTL (initiell TTL kan v?re statisk definert med en #define, minimum 6).

Linklaget skal tilby en p?litelig full dupleks kommunikasjonstjeneste til h?yere lag p? f?lgende m?te:

• Linklaget tilbyr funksjonen l2_send til nettlaget for a sende data over nettet. l2_send har f?lgende prototype (som returnerer hvor mange bytes fra laget over som ble sendt):

  int l2_send( int src_mac_address, int dest_mac_address, const char* buf, int length );

• N?r det kommer data inn vil det fysiske laget kalle l2_recv som i prekoden til den obligatoriske oppgaven. Her skal du legge til din flytkontroll og din bridging-kode.

  void l2_recv( int device, const char* buf, int length );

• Hvis data leveres til lokal maskin m? din l2_recv implementasjon kalle l3_recv for ? levere dataene eller l2_send (eller tilsvarende) for ? videresende ut p? andre linker hvis pakken skal leveres til andr.

  int  l3_recv( int mac_address, const char* buf, int length ) 

N?r en pakke er ACKet s? har noden som ACKet ansvaret for at pakken den har tatt imot leveres til destinasjonen. ACKene skal derfor v?re lokale per noder p? en link og ikke ende-til-ende. Tiln?rmet alt av kode skal skrives p? l2. Dette betyr at du vil f? problemer om du fors?ker ? sende til en node som ikke eksisterer, men dette skal ikke tas hensyn til, med mindre du ?nsker ? g? for ekstraoppgaven.

Oppgavebeskrivelse

Mekanismene skal implementeres som del av et program som kan f?lgende:

• Opprette "fysiske linker" mellom to maskiner. Disse "fysiske linkene" opprettes ved hjelp av UDP pakker som sendes mellom maskinene. En maskin skal b?de kunne ta imot nye oppkoblinger fra andre maskiner og initiere nye oppkoblinger til andre maskiner. Programmet skal derfor starte med to parametre:

  • En port som parameter som andre maskiner kan sende UDP pakker til.

  • En virtuell MAC-adresse (brukes ogs? som nettverksadresse) som er maskinens unike identifikator.

  MAC-adressen m? gj?res kjent for linklaget (l2_init). Det er n?dvendig ? st?tte oppkobling til og fra flere maskiner samtidig. Det er ikke n?dvendig ? st?tte nedkobling av "fysiske linker".

• Ta imot input fra tastaturet og prosessere inputlinjer:

  • Hvis inputlinjen begynner med ordet "QUIT" skal programmet avsluttes men f?r det avsluttes m? du frigj?re minne du selv allokerer (husk ? kalle shutdown for slow_sender og receiver).

  • 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 (evt. andre instanser av programmet p? samme maskin)

  • Hvis inputlinjen begynner med ordet "SEND" skal det forventes at linjen har form "SEND <mac-adresse> <filnavn>. Filnavnet skal v?re navnet til en fil som skal leses inn, overf?res over nettet til maskinen med MAC-adressen <MAC-adresse> med hjelp av linklaget ditt, og lagres p? disk p? den andre maskinen.

• Ta imot rammer fra nettet og sjekke MAC-adressen (som m? v?re inkludert i rammen):

  • Hvis du tar imot en ramme p? en "fysisk link" og den er adressert til den lokale maskinen, utf?res flytkontrollmekanismen og pakken leveres til det lokale nettverkslaget.

  • Hvis du tar imot en ramme p? en "fysisk link" og den er adressert til en annen maskin sendes rammen videre ut p? en annen "fysisk link". Flytkontroll og retransmisjon m? utf?res separat for hver "fysiske link". Denne oppgaven krever ikke noen spesiell l?sning for situasjonen der en ramme m? videresendes av en bro mens det glidende vinduet p? den neste linken er fylt. Her kan du selv bestemme om du dropper rammen og stoler p? retransmisjonen fra den opprinnelige senderen eller ikke tar rammen ut av det glidende vinduet p? mottakersiden, eller lager en bro med en egen k?. Om du dropper rammen s? skal den ikke ACKes.

• Du skal ha utskrift i programmet hvor du skriver ut informasjon over sending og mottak av data og ACK over hvem det er fra og hvem som skal motta, samt informasjon om rammen du sender. Disse utskriftene skal kun finne sted om koden er kompilert med -DDEBUG (se make debug), s? de m? legges inn i blokker av #ifdef DEBUG og #endif. Huske ? printe til stderr (err).

• For ? skrive data til fil skal du bruke funksjonen receiver.

• For ? sende data til en socket skal du bruke funksjonen delayed_sendto som erstatning for den vanlige sendto funksjonen.

• Du er ogs? ansvarlig for ? s?rge for at overf?ringene over nettverk er trygge p? tvers av arkitekturer, 32-bits og 64-bits OS og eventuelle optimaliseringsflagg. Du m? s?rge for at det ikke finnes en mulighet for at du sender garbage (fjern struct padding) eller bruker datatyper som er forskjellige p? tvers av arkitekturer i data som sendes. Husk at det finnes structer som brukes i overf?ringen p? l3 og l4 - disse m? fikses p? samme m?te. Du trenger ikke ? ta hensyn til andre kompilatorer enn relativt "nye" gcc-kompilatorer (les: den p? login.ifi.uio.no).

Du skal levere f?lgende:

1. Et designdokument som inneholder:

   • En frontside med kandidatnummer, oppgavetittel, kurs og semester, vi vil ikke ha navn eller brukernavn.

   • En forklaring p? din implementasjon av glidende vindu (med mindre du bruker Stop-and-Wait), samt hvordan den l?ser flytkontroll og rammetap.

   • En diskusjon om mulighetene for p?litelig ende-til-ende kommunikasjon p? linklaget. Denne oppgaven krever at du implementerer p?litelig ende-til-ende kommunikasjon p? linklaget men ikke noen spesifikk l?sning. Forklar fordeler, ulemper og din beslutning.

   • Hvordan programmet er designet. Gjerne med en tegning (flytdiagram) som viser i hvilken rekkef?lge de forskjellige funksjonene blir kalt.

   • Protokollen du har laget.

   • En dokumentasjon av hvordan programmet skal startes evt. avsluttes.

   • Hvilke filer programmet best?r av (C-filer, headerfiler osv.).

   • Eventuelle andre s?regenheter.

2. Programfilene, hvor koden er fyldig kommentert (der det er n?dvendig). 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:

• En riktig, egen implementasjon av Go-Back-N gir full uttelling. En mer avansert mekanisme som for eksempel Selective Repeat kan gi noen f? ekstrapoeng. Stop-and-wait gir redusert uttelling.

• Strategien for (videre-) sending av rammer som er adressert til en annen maskin skal utf?res med flooding (videresende rammen p? alle linker unntatt den det kom fra).

• For eventuelle andre ekstrapoeng, se extraoppgaven under.

Ekstraoppgave

Under finner du en ekstraoppgave som gir noen ekstrapoeng. Om du fors?ker ? gj?re en ekstraoppgave, spesifiser det i designdokumentet.

Optimaliser TTL

Gitt f?lgende nettverk:

K1 ?nsker ? sende pakker til K6. Det er to ruter for ? komme frem til K6 uten ? v?re innom samme node to ganger. Den ene involverer 5 hopp (K1, K2, K3, K4, K5, K6) og den andre involverer 3 hopp (K1, K2, K5, K6). Lag en mekanisme som optimaliserer TTLen til ? v?re 3 straks det er kjent at det er det minimale antall hopp mellom nodene. P? denne m?ten unng?r man to hopp med un?dvendig trafikk.

Spesifikke krav til koden

Koden din skal kompilere og vil bli testet p? IFIs login-maskiner (login.ifi.uio.no).

Orakeltjeneste og administrative sp?rsm?l

F?r du problemer under implementasjonen anbefaler vi deg ? sjekke FAQ p? orakelsiden som ligger under INF3190 sin hjemmeside. Du kan ogs? sende en mail til orakel med addressen inf3190-orakel [at] ifi.uio.no

For administrative sp?rsm?l rundt hjemmeeksamen,ta kontakt med naeemk [at] ifi.uio.no

Besvarelse

Designdokumentet skal skrives vha. et egnet verkt?y, f.eks. LaTeX, OpenOffice, Word, osv. 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. Det som er viktig er ? kunne dokumentere forst?else for de emnene oppgaven ber?rer, i tillegg til selve gjennomf?ringen. Vi stiller krav til ryddighet og struktur.

Elektronisk innlevering

Eksamen er anonym. Bruk idchecker.sh for ? unders?ke om navnet ditt er i koden (./idchecker.sh dittBrukernavn og ./idchecker.sh enLitenDelAvDittNavn). Scriptet unders?ker om navnet ditt eksisterer i .tex, .c, .h og .txt-filer i mappa (husk ? legge til eventuelle andre filformater du bruker). Det er ditt ansvar ansvar at din innlevering ikke inneholder personlig informasjon.

Alt skal leveres elektronisk hvor alle filer (Makefile, *.c, *.h, design.pdf, README.txt, etc.) er samlet i en katalog med kandidatnummeret som navn. Av denne katalogen lager du en komprimert tar-ball -- bruk kommandoen make handin, husk ? modifisere din makefile til ? inneholde kandidatnummeret ditt f?r du gj?r dette. Den elektroniske innleveringen skal leveres via web. Linken Innlevering av oppgaven finnes p? kursets hjemmeside.

Etter innlevering anbefales det ? laste ned arkivet du leverte inn, extracte det og unders?ke at alt fungerer (inkludert at README og design er med). Det anbefales ogs? ? levere inn utkast av eksamnen i god tid f?r fristen i tilfelle du f?r tekniske problemer eller gj?r en alvorlig feil rett f?r innlevering.

Innleveringsfrist: S?ndag 7. april 2013 kl 23:59:59

Merk at denne tidsfirsten er HARD, oppgaver levert etter fristen vurderes med karakteren "F", alts? stryk.

Det forutsettes at studenten har lest forskrift om studier og eksamener ved Universitetet i Oslo for karaktergivende oppgaver.