INF3190 Obligatorisk oppgave: Linklagets flytkontroll

Formelt:

Denne obligatoriske oppgaven skal l?ses individuelt.
Innleveringen m? v?re godkjent f?r innlevering av hjemmeeksamen 1.
For ? best? m? innleveringen oppfylle kravene som er dokumentert i avsnittet "Oppgave" og du m? kunne forklare l?sningen din.

Oppgave

I denne oppgaven skal du skrive den f?rste delen av et Linklag, flytkontrollen. Linklaget vil senere utvides med annen viktig funksjonalitet.

Dere vil fordype kunnskapen deres om programmering med UNIX-sockets. Det som trengs for ? kunne l?se oppgaven er "Berkeley UNIX System Calls and Interprocess Communication", beskrivelsen av glidende vinduer fra kapittel 3 i Tanenbaum, samt man-sidene p? Linux-maskinene. Oppgaven skal programmeres i C.

Programmet dere skal skrive skal starte p? to forskjellige maskiner i IFI sitt nettverk. Programmet skal ta et portnummer som kommandolinjeparameter. Mens programmet kj?rer tar det imot kommandoer fra tastaturet. Kommandoene skal brukes til oppkobling mot en annen maskin, for ? overf?re en fil til en oppkoblet maskin, og for ? avslutte programmet.

Oppkoblingen skjer ved ? opprette en "fysisk link" mellom to maskiner med hjelp av UDP-kommunikasjon. Programmet som initierer opprettelsen av forbindelsen kaller vi i det f?lgende klient, programmet som svarer p? opprettelsen kaller vi tjener.

Init-fase / Opprettelse av en "fysisk link"

Opprettelse av den "fysiske linken" skal skje som f?lger:

• Begge programmene er forberedt p? ? ta imot UDP-pakker.

• Klienten sender en UDP-pakke som inneholder beskjeden "CONNECT" (dere kan legge til tilleggsinformasjon hvis dere ?nsker det). Etter ? ha sendt UDP-pakken anser klienten den "fysiske linken" som connecting. Den "fysiske linken" tildeles et entydig nummer.

• N?r tjeneren tar imot "CONNECT"-pakken anser den forbindelsen til klienten som har sendt pakken som up. Den svarer med en UDP-pakke som inneholder beskjeden "UP" (dere kan ogs? her legge til tilleggsinformasjon hvis dere ?nsker det). P? tjeneren kalles funksjonen l1_linkup som skriver linknummeret ut til skjermen.

• N?r klienten tar imot "UP"-pakken anser den "fysiske linken" som up. P? klienten kalles funksjonen l1_linkup som skriver linknummeret ut til skjermen.

S? snart et program anser den "fysiske linken" som up kan den begynne ? sende rammer over den "fysiske linken".
(Tips: Det vil v?re lurt ? skrive oppkoblingsmekanismen slik at flere "fysiske linker" mellom flere maskiner kan opprettes. Dette er ikke et krav for ? f? obligen godkjent. En av hjemmeeksamenene vil kreve en slik utvidelse. Det kan ogs? v?re lurt ? tenke p? hvordan man setter opp rammestrukturen)

Flytkontrollen

Oppgaven krever en implementasjon av en flytkontrollmekanisme. Flytkontrollmekanismen skal v?re en glidende vindu mekanisme (sliding window). I denne oppgaven er stop-and-wait en lovlig l?sning, men med hensyn til neste oppgavene anbefaler vi ? implementere Go-Back-N eller Selective Repeat med opp til 10 utest?ende rammer (i hver retning).

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

• Linklaget tilbyr funksjonen l2_send til nettlaget for a sende en ramme over nettet.

• N?r linklaget mottar data skal de leveres ved ? kalle funksjonen l3_recv som leverer dataene til det h?yere laget.

Flere detaljer om funksjonene finnes i avsnitt Spesifikke krav til implementasjonen.

Utlevering

Utdelt kode inneholder rammeverket dere skal bygge videre p?. receiver skal brukes for ? skrive til fil (navngir filene automatisk med forskjellige navn). delayed_sendto skal brukes for ? sende data fra en maskin til en annet, som erstatning for write, send eller sendto. Den forsinker utsendingen av en viss pakke med 0.2 s per pakke som er foran denne i k?en - dette vil f?re til at flytkontrollen sl?r til. irq inneholder systemfunksjonen select. Vi anbefaler sterkt bruk av select framfor bruk av flere tr?der eller prosesser i oppgavene i INF3190.

Merk at  delayed_sendto  ikke tillater mer enn 10 utest?ende rammer p? hver link. Hvis dere fors?ker ? sende flere pakker mens det er 10 utest?ende i k? vil dere f? returverdien 0 (alts? ingen byte sendt).

Utdelt kode har mange filer. Dere kan endre p? alle filene om dere ?nsker det, men vi har uthevet de filene hvor funksjonaliteten til denne oppgaven ligger med fet tekst:

• delayed_sendto.c

• delayed_sendto.h

• irq.c 

• irq.h

• l1_phys.c

• l1_phys.h

• l2_link.c

• l2_link.h

• l3_net.c

• l3_net.h

• l4_trans.c

• l4_trans.h

• l5_app.c 

• l5_app.h

• main.c

• Makefile

• doxyfile

• receiver.c

• receiver.h

Filer markert i r?dt kan endres (kan v?re greit om dere ?nsker ? ?ke gjennomstr?ming eller teste/sette inn debug-statements), men disse blir overskrevet med originalfilene av obligretterne etter innlevering.

Koden inneholder alts? ogs? en doxyfile som kan brukes sammen med doxygen vha. kommandoen doxygen doxyfile (eller make doc) for ? generere dokumentasjon i .html-format for koden. Merk at dette krever doxygen og graphviz. Om dere ?nsker ? konfigurere doxygen, kan dere installere pakken doxygen-gui og kj?re kommandoen doxywizard doxyfile for ? endre instillinger.

Doxygen-kommentarer starter med /**, har typisk <space>* p? begynnelsen av hver etterf?lgende kommentarlinje. Avsluttes som vanlige multi-line comments. Husk at n?r dere gj?r endringer i filene s? m? dere kj?re kommandoen for ? generere dokumentasjonen p? nytt for ? oppdatere den.

Startsiden for dokumentasjonen er doc/html/index.html og det anbefales ? g? rett til ?Files?-fanen ?verst p? siden. Her finner dere dokumentasjon for hver funksjon og call-graphs for disse samt mye mer sortert per fil.

Bakgrunnsinformasjon

Spesifikke krav til implementasjonen

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

Opprettelse av den emulerte "fysiske linken"

F?rst skal dere lage funksjoner som gj?r det mulig at naboer p? deres linklag kjenner hverandre. Noder som snakker direkte med hverandre er naboer p? det underliggende laget. I v?rt tilfelle kan det v?re to vilk?rlige maskiner p? Internett, siden alle IP-adresserbare maskiner er naboer p? transportlaget.

Funksjonene l1_connect og l1_linkup skal til sammen utgj?re de tjenestene som trengs for at linklaget kjenner en aktiv, bi-direksjonal "fysisk link" mellom to maskiner. Det ? opprette en "fysisk link" er en asymmetrisk aktivitet mellom to programmer, som da tar rollene som klient og tjener.

Det fysiske laget

l1_connect

int l1_connect( const char* hostname, int port );

l1_connect kalles for ? begynne opprettelsen av en "fysisk link" mellom den lokale maskinen og en annen maskin. Funksjonen returnerer etter ? ha sendt "CONNECT"-pakken uten ? vente p? suksessrik oppkobling. For ? sl? opp struct in_addr som tilh?rer et hostnavn vil man som oftest bruke systemfunksjonen gethostbyname. Siden programmet bruker UDP-kommunikasjon, trenger man ikke ? opprette en ny socket for hver forbindelse. I stedet kan man bruke den delte socketen, og benytte sendto/recvfrom.
Returverdien til l1_connect er enten 0 eller en melding om en feil i sendeoperasjonen.

l1_linkup

static void l1_linkup( phys_conn_t *conn, const char* other_hostname, int other_port, int other_mac_address );

l1_linkup er en melding fra det fysiske laget til linklaget om at en "fysisk link" til en nabomaskin er opprettet.

Etter l1_linkup kan linklaget bruke linknummeret for ? sende til naboen.

l1_linkup kalles etter mottak av en "CONNECT"-pakke, eller n?r det mottas svar p? en "CONNECT"-pakke.

I tilfellet hvor det ble mottatt svar p? en "CONNECT"-pakke vil det allerede v?re initialisert en phys_conn_t, og en sender da med en peker til denne. Det er gitt en funksjon get_phys_conn som kan brukes til ? sl? opp en allerede initialisert phys_conn_t.

Dersom l1_linkup kalles etter mottak av "CONNECT" kan en sende med NULL til conn-parameteret, og det er da l1_linkup sitt ansvar ? initialisere en ny phys_conn_t struct. Dette kan gj?res ved kall p? create_phys_conn. En benytter seg da av other_hostname og other_port, som er henholdsvis hostnavn og port for den aktuelle naboen som forbindelsen opprettes mot. Hostnavnet kan hentes fra en struct in_addr ved hjelp av gethostbyaddr(). Parameteret other_mac_address er naboens unike MAC-adresse, slik som spesifisert p? kommandolinjen.

l1_send

int l1_send( int device, const char* buf, int length )

l1_send kalles av linklagsfunksjoner for ? sende en ramme. Parameteret device identifiserer hvilken "fysisk link" det er som meldingen skal sendes p?. buf peker til et buffer der den meldingen som sendes ligger. length inneholder det antallet tegn som blir sendt. l1_send bruker parameteren device for ? initialisere alle parametere som sendeoperasjonen krever. S? bruker l1_send funksjonen delayed_sendto for ? sende dataene p? den "fysiske linken".

l1_handle_event

void l1_handle_event( );

l1_handle_event kalles av interrupt-handleren handle_event hvis nettverksaktivitet har oppst?tt. Dette er nesten garantert ? bety at data har ankommet p? en "fysisk link", dvs. at data m? leses (helst med systemfunksjonen recvfrom) fra UDP socketen. S? er det n?dvendig ? forst? hvilken "fysisk link" dataene har kommet fra, og enten kalle l1_linkup eller sende de videre til l2_recv.

Linklaget

Rammer skal ikke v?re lengre enn 100 bytes. Dette gjelder b?de rammer som inneholder data og rammer som inneholder acknowledgements. Det er anbefalt ? lage flere hjelpefunksjoner for h?ndtering av flytkontrollen, sending og mottak av rammer, og hvis dere bruker det, for timeout-h?ndtering.

Hver enkelt fysisk link har sin unike MAC-adresse i hver ende - tilsvarende nettverkskort. Hvis man vil st?tte flere samtidige linker, m? den lokale adressen initialiseres p? forh?nd med l2_init() for hver link.

Linklaget deres skal benytte recvfrom og delayed_sendto. recvfrom er en standard UNIX-funksjon, delayed_sendto f?lger med den utleverte koden og fungerer som UNIX-funksjonen sendto.

l2_send

int l2_send( int dest_mac_addr, const char* buf, int length )

l2_send kalles av nettverkslagsfunksjoner for ? sende en pakke. Parameteret mac_address identifiserer hvilken annen maskin det er som meldingen skal sendes til;. buf peker til et buffer der den meldingen som sendes ligger. length inneholder det antallet tegn som blir sendt. For hvert kall lager l2_send en ramme med opp til 100 bytes lengde. l2_send bruker ikke flere enn en ramme for ? sende buf. Hvis lengden er for stor sendes bare de f?rste 100 bytes (minus lengden til rammeheaderen). Hvis l2_send har en ?pning i det glidende vinduet for sending, vil den lagre rammen i vinduet og returnere 1. Hvis l2_send ikke har noen ?pning vil den returnere 0.

l2_recv

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

Alle rammer som linklaget mottar over nettet skal leveres til h?yerelagsprotokoller uten linklagsheadere, ved ? kalle l3_recv. Hvis l3_recv returnerer 1 kan linklaget anta at dataene har blitt levert korrekt. Hvis l3_recv returnerer 0 har det oppst?tt en feil, og programmet skal fors?ke ? levere dataene ved en senere anledning.

Alle data skal leveres til h?yrelagsfunksjonen l3_recv.

Programmet

Programmet benytter de funksjonene dere har laget over.

• Hvis programmet leser "CONNECT <maskinnavn> <portnummer>" fra tastaturet skal det 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). I denne oppgaven er det nok hvis programmet kan h?ndtere en "fysisk link".

• Hvis programmet leser "SEND <filnavn>" fra tastaturet skal det pr?ve ? ?pne filen, for ? sende filen til maskinen som den er koblet til. Hele filen skal sendes til den andre maskinen ved ? kalle p? l4_send.

• Hvis programmet leser "QUIT" fra tastaturet skal det avslutte. Her b?r du kalle funksjoner som delayed_send_shutdown().

• N?r det har kommet data fra socketen skal hovedprogrammet gi kontroll til det fysiske laget, som leser data fra UDP-socketen og kaller en funksjon p? linklaget.

• N?r linklaget tar imot en ramme skal det h?ndtere glidende-vindu-mekanismen, og pr?ve ? levere dataene som har kommet fram i riktig rekkef?lge til det h?yere laget ved ? kalle l3_recv. Hvis l3_recv returnerer 0 skal ikke linklaget slette dataene fra det glidende vinduet, men pr?ve ? levere om igjen ved senere anledning.

Innlevering

Dere skal levere f?lgende:

1. Et designdokument som inneholder:

   • En diskusjon vedr?rende m?tene ? h?ndtere flytkontroll p?, og hvilke fordeler de mer avanserte glidende-vindue-protokollene har over enklere protokoller som f.eks. stop-and-wait.

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

   • Protokollen deres (rammeinndeling, headerinformasjon, glidende vindu).

   • Dokumentasjon om hvordan programmet skal startes evt. avsluttes.

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

2. Programkoden, hvor koden er godt kommentert. Dokument¨¦r alle variabler 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.

   • Andre s?regenheter som er viktig ? vite om (f.eks. feilsituasjoner).

Krav til innleveringen

Designdokumentet skal skrives vha. et egnet verkt?y, f.eks. LaTeX, Word, etc. Dokumentet skal inneholde besvarelsen og de etterspurte figurer, samt ha en forside hvor f?lgende opplysninger er angitt: Navn - brukernavn - dato - kurs
F?r levering skal dokumentet konverteres til pdf format. Hverken et Word/Works/OpenOffice/TeX -dokument eller en vanlig editorfil (plain text) godtas.

Koden m? v?re kompilerbare tekstfiler.

Omfanget av dokumentet trenger ikke n?dvendigvis v?re s? stort, men m? inneholde tilstrekkelig informasjon til ? oppfylle kravet som beskrevet under 'oppgave'. Det som er viktig er ? dokumentere forst?else for de ber?rte emner, i tillegg til selve gjennomf?ringen.

Elektronisk innlevering: Alt skal leveres elektronisk hvor alle filer (Makefile, *.c, *.h, README.pdf, etc.) er samlet i en katalog med deres UIO-brukernavn som navn. Av denne katalogen lager dere en komprimert tar-ball -- bruk kommandoen tar zcvf username.tgz username. Link for den elektroniske innleveringen kommer p? INF3190 sine hjemmesider.

Innleveringsfrist: S?ndag 24. februar 2013 klokken 23:59:59

Husk at du ikke kan levere kopi av andres besvarelser, men skal levere en egenprodusert l?sning. Les kravene til innleveringer p? http://www.mn.uio.no/ifi/studier/admin/obliger/.

Forklaringskrav

Fagl?rere vil gjennomf?re stikkpr?ver blant de innleveringer som oppfyller kravene for godkjenning. Det innkalles til uformelt m?te. Forklaringen omfatter linklaget generelt, linklagsteknikker brukt oppgaven, innlevert kode og programflyt. Hvis forklaringen ikke er tilstrekkelig underkjennes innleveringen. Hvis innleveringen underkjennes pga stikkpr?ven kan man velge formell muntlig pr?ve med fagl?reren som omfatter det samme materialet og som gjelder godkjenning av obligen.