TDAT2004 Datakommunikasjon med nettverksprogrammering
Gruppe 12: Ingvild Broen, Even Dalen og Rebekka Heggebø 

Innledning

Sjekksum er et hjelpemiddel for å finne korrupte bits i data. Det er en kalkulert bitstreng der verdien avhenger av innholdet i dataen som blir overført. 

Sjekksummen blir kalkulert av avsender og lagt ved i pakkehodet. Mottaker regner ut den samme sjekksummen på pakken den har mottatt og sammenligner verdien med den originale sjekksummen. Dersom de to sjekksummene er ulike kan man konkludere med at dataen er korrupt, og avsender kan bli bedt om å sende pakken på nytt. Sjekksum brukes som virkemiddel både i internettprotokoller som TCP og UDP, og på lenkelaget. I denne wikien er det fokus på hvordan sjekksum blir brukt på lenkelaget.

På lenkelaget finner vi ulike protokoller som kontrollerer hvordan sjekksum skal fungere. Ethernet og andre IEEE 802-protokoller utviklet av Institute of Electrical and Electronics Engineers bruker sjekksummer i sine protokoller. Det samme gjør blant annet High-Level Data Link Protocol, som er utviklet av ISO.

Cyclic Redundancy Check (CRC) ble oppfunnet i 1961 av W. Wesley Peterson, og ble benyttet i Ethernet i 1975.

 

Ønsket funksjonalitet

Oppgaven til CRC er å oppdage skadde rammer, som tilfeldige feilendringer av rådata. Dette er viktig for lenkelaget, fordi laget strukturerer pakker fra nettverkslaget til rammer som sendes til det fysiske laget, hvor databits kan bli overført og organisert riktig. Mottakeren kan kalle på CRC slik at den kan bekrefte at innholdet ikke er skadet.

 

Virkemåte

Etter lenkelaget har lagt inn sin header-data, blir det avslutningsvis lagt til en ramme rundt pakken. I starten av pakken blir det lagt inn en introduksjon (Preamble), og på slutten blir en sjekksum lagt til (FCS – Frame Check Sequence). Sjekksummen har blir regnet ut fra hele pakken, med unntak av introduksjonen.

Eksempel : Sjekksum

Avsender ønsker å sende “beskjeden” under til mottaker. Avsender og mottaker har bestemt seg i mellom et tall de skal dele på, i dette tilfellet 16.

2511127134


Det første som skjer er at avsender adderer alle tallene og finner summen 72. Så deler avstender 72 på 16, og finner resten 8. Dette tallet blir så lagt til i pakkehodet, og beskjeden ser nå ut som i figuren under.

25111271348


Når mottaker får beskjeden regner den også ut summen, deler på det avtalte tallet, og finner resten. Dersom resten stemmer overens med tallet i pakkehodet (8) er det greit, og man går videre. Hvis tallet mottaker finner er ulikt tallet i pakkehodet er det noe som har gått galt, og avsender kan bli bedt om å sende pakken på nytt.

Eksempel: CRC

I CRC bruker avsender og mottaker en felles deler/polynom for å validere meldingen.
I dette eksempelet bruker vi en 6-bits melding med en 3-bits CRC lengde og en 4-bits deler/polynom.
CRC bruker XOR for utregning. ,
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 0 

Melding: 101110
Deler/polynom = x3 + x = 1010
Lengen er definert av den høyeste graden til polynomet og her er lengden lik 3.

Meldingen fra avsender får antall nuller plassert bak etter hvor mange bits CRC lengden har.

Melding: 101110
Melding med lengde: 101110 000
Deler/polynom: 1010

Avsender:
1010 | 101110 000  <- Meldingen med tre nuller bak
       1010        <- Deleren blir plassert på starten
       000110 000  <- XOR benyttes for utregning. Resterende bits fra meldingen plasseres bak.
          101 0    <- Deleren flyttes videre til første ener
       000011 000
           10 10
       000001 100
            1 010
-----------------
       000000 110  <- Rest (3 bits). Divisjonsalgoritmen stopper når meldingen kun består av nuller.


Meldingen som blir sendt til mottaker er meldingen med 3-bits resten bak (101110 110). Når mottaker skal validere meldingen fra avsender brukes den samme deleren og divisjonsalgoritme. Resten skal være lik null for at valideringen av meldingen skal være godkjent og uten påvist feil.

 

Mottaker:
1010 | 101110 110  <- Meldingen med resten
       1010        <- Deleren
       000110 110
          101 0
       000011 110
           10 10
       000001 010
            1 010
-----------------
       000000 000  <- Rest. Sjekksummen er lik null.
 

 

Kilder

Stone, Jonathan, and Craig Partridge. "When The CRC And TCP Checksum Disagree". Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication - SIGCOMM '00 (2000): n. pag. Web. 29 Mar. 2017.

"Frame Check Sequence". En.wikipedia.org. N. p., 2017. Web. 29 Mar. 2017.

Checksum. (2014). [video] Youtube: Eddie Woo. (web: https://www.youtube.com/watch?v=RFOGDY2e0mQ)

Cyclic Redundancy Check. (2016). [video] Youtube: MisterCode. (web: https://www.youtube.com/watch?v=IeSzUKCQYjM)

 



 



  • No labels