INF3190 - Vår 2010

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å. slow_receiver skal brukes for å skrive til fil. Den er laget slik at forsinkelser oppstår, slik at flytkontrollen slår til. delayed_sendto skal brukes for å sende data fra en maskin til en annet, som erstatning for write, send eller sendto. Den forsinker utsendingen - også 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.

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:

delayed_droping_sendto.c
delayed_droping_sendto.h
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
slow_receiver.c
slow_receiver.h

Bakgrunnsinformasjon

Dere skal implementere en linklagsprotokoll på toppen av en transportlagsprotokoll. Hvis dere synes at dette ikke er korrekt fordi lagdelingen blir ødelagt, så vil vi i det følgende gi noen eksempler på systemer som er utbredt i den virkelige verden, men som bryter strukturen på samme måten. For eksempel er ATM i dag som oftest brukt som linklagsprotokoll under IP, som er en protokoll på nettverkslaget. Men det er da ATMs transportlag som ligger under IP. Et annet eksempel finnes på IFI: Wireless LAN brukere må installere en PPTP klient for å få lov til å bruke nettet fra maskinen sin. PPTP er en protokoll som bruker nettverkslagets IP, men selv tilbyr linklagstjenester etter at klienten har autentifisert seg.
Det samme gjør vi her: vi bruker UDP som om den ikke tilbyr flere tjenester enn et fysisk lag som knytter to nabomaskiner direkte sammen.

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 flere ganger.
Hvis programmet leser "QUIT" fra tastaturet skal det avslutte.
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:

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.).
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: Fredag 26. februar 2010 klokken 18:00

Husk at du ikke kan levere kopi av andres besvarelser, men skal levere en egenprodusert løsning. Les kravene til innleveringer på www.ifi.uio.no/studier/studentinfo.html#krav.

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.