UTVRĐIVANJE I ISPRAVLJANJE POGREŠAKA

V. SLOJ PODATAKOVNE VEZE (Data Link)

• sloj podatakovne veze ili podatkovni sloj osigurava prijenos između dva direktno spojena računala
• "susjedna računala" fizički povezana pomoću komunikacijskog “wire-like” kanala
• glavna osobina takvog kanala: bitovi se dostavljaju u točno istom redoslijedu u kojem su poslani
   

1. ELEMENTI DIZAJNA SLOJA PODATAKOVNE VEZE
 

• funkcije:
  1. osiguravanje usluga za mrežni sloj (dobro definirano sučelje)
  2. određivanje načina grupiranja bitova fizičkog nivoa u okvire (frames)
  3. rješavanje pogreški pri prijenosu
  4. reguliranje toka okvira tako da ne dođe do zagušenja (kad je primaoc okvira spor, a pošiljaoc brz)

1.1 Usluge za mrežni sloj

• osnovna funkcija sloja podatkovne veze: prenijeti podatke (bitove) od mrežnog sloja izvora do mrežnog sloja odredišta

Slika: Modeli komunikacije između podatkovnih slojeva (Tanenbaum, 1996)

• najčešći  tipovi usluga (servisa):

  1. nepotvrđeni bespojni (unacknowledged connectionless service)

  2. potvrđeni bespojni  (acknowledged connectionless service)

  3. potvrđeni spojni (acknowledged connection-oriented service)
      

a. Nepotvrđeni bespojni

• šalju se neovisni okviri bez potvrde odredišnog računala o primitku
• ne vrši se obnavljanje okvira ako se neki izgubi
• servis prikladan:
  • ako je broj grešaka mali, pa je obnavljanje ostavljeno višim nivoima
  • kada važnije da podaci brzo stignu nego točnost podataka

b. Potvrđeni bespojni

• potvrda (acknowledgment) se šalje za svaki okvir posebno, pa pošiljaoc zna da li je okvir stigao ili nije
• ako okvir ne stigne u nekom propisanom vremenskom intervalu, šalje se ponovo
• ako se potvrda izgubi, okvir će se prenijeti više puta
• servis koristan za nepouzdane kanale kao na pr. bežične sisteme

c. Potvrđeni spojni

• najpouzdaniji servis, uspostavlja se veza prije slanja okvira
• svaki poslani okvir je numeriran i sloj garantira:
  • svaki okvir će biti primljen
  • svaki okvir će se primiti točno jednom
  • svi okviri će stići u pravom redosljedu
• 3 faze prijenosa:

1. uspostavlja se veza tako da obje strane inicijaliziraju brojače i varijable potrebne za vođenje računa o tome koji su okviri već stigli, a koji nisu
2. okviri se prenose
3. oslobađa se veza, tj. varijable i ostali resursi koji su bili potrebni za prijenos

1.2 Tvorba okvira (Framing)
 

• nedostatak: metoda vezana uz 8-bitne znakove tj. uz ASCII kôd, potrebna je metoda i za znakove bilo koje veličine:

0101111111111001 - niz podataka prije umetanja (poslao ga je mrežni sloj)

010111110111110001 - - niz podataka s umetnutim 0 bitom

• koristi se kôd pri kojem je podacima dodan jedan paritetni bit (parity bit) na kraj bloka podataka

• bit se odabire tako da ukupni broj 1 bitova u okviru bude npr. paran:

  10110101 => 101101011
  
  10110001 => 101100010
  
   

• kôdom s jednim paritetnim bitom, mogu se detektirati jednobitne greške (čim se jedan bit promijeni, poremeti se parnost)
  
   

T(x) = x^n-k D(x) Å  R(x)

(P(x) Q(x) Å  R(x))Å  R(x) = P(x) Q(x)

• ostatak R(x)  je zaštitni kôd (F(x)), lako se generira:

  • uzme se x^n-k D(x) (D(x) se nadopuni sa n-k nula desno),

  • rezultat se podijeli sa P(x)

  • uzme se n-k ostatak i oduzme (ili zbroji mod 2) od x^n-k D(x)

  • => rezultat je n-bitni okvir T(x)

• kada na strani primaoca stigne T(x), podijeli se s P(x), ako nije bilo pogreški pri prijenosu, nema ostatka

• ukoliko je nastala pogreška, primaocu je stiglo: T(x) Å  E(x)

• pri dijeljenju je ostatak E(x)/P(x)

• pogreška se NEĆE ustanoviti ako je s E(x) djeljiv s P(x) odnosno CRC neće otkriti one pogreške-polinome E(x)koji sadrže kao faktor P(x)

• na primjer, ako je pogreška jednobitna E(x) = xⁱ (i je krivi bit), uvijek će se pronaći ako P(x) sadrži barem 2 člana

• za dvobitne pogreške P(x) mora imati barem 3 člana, itd.

• najčešće korišteni djelitelji su:

CRC-12 = X¹² + X¹¹ + X³ +X² + X + 1

CRC-16 = X¹⁶ + X¹⁵ +X² + 1

CRC-CCITT = X¹⁶ + X¹² + X⁵ + 1

CRC-32 = X³² + X²⁶ + X²³ +X²² + X¹⁶ + X¹² + X¹¹ + X¹⁰ + X⁸ + X⁷ + X⁵ + X⁴ +X² + X + 1

CRC-32 - za IEEE 802 LAN standarde

2.2 Kodovi za ispravljanje pogrešaka (Error-Correctong Codes)

• uz svaki blok podataka uključuje se dovoljno redundantnih informacija koje će omogućiti primaocu da zaključi kakav mora biti preneseni znak

• obično k-bitni blok podataka preslikava (pomoću nekog od algoritama za kodiranje) u n-bitni okvir (n > k) - naziva se n-bitna kodna riječ (codeword)

• pošiljaoc provjerava kodnu riječ, moguće je:

  • nije bilo pogreški

  • pogreške su utvrđene i ispravljne

  • pogreške su utvrđene, ali se ne mogu ispraviti

  • pogreške nisu utvrđene - rezultat je neispravan k-blok podataka

• jedan od načina: korištenje Hammingove udaljenosti (Hamming distance)

• za dvije kodne riječi definira se Hammingova udaljenost d kao broj različitih bitova na odgovarajućim pozicijama, npr:

V₁ = 10001000

V₂ = 10110001

d=4
 

• ako je udaljenost dviju kodnih riječi d, potrebno je d jednobitnih greški da se jedna kodna riječ pretvori u drugu

• kod prijenosa podataka najveći mogući broj kodnih riječi je 2ⁿ (n je dužina riječi) ali se obično sve ne koriste;
  iz čitave liste legalnih kodnih riječi pronalazi se par čija je Hammingova udaljenost minimalna i to je Hammingova udaljenost cijelog koda o kojoj ovisi pronalaženje i ispravljanje greški

• da se pronađe k greški, potreban je kôd sa k+1 razlikom jer tako ne može k jednobitnih greški promijeniti jednu ispravnu kodnu riječ u drugu

• da se ispravi k greški, potreban je kôd sa razlikom od 2k+1 jer su tada legalne kodne riječi tako daleko jedna od druge da se i sa k promjena može pronaći originalna ispravna kodna riječ (ispravna riječ je najbliža pogrešnoj riječi u odnosu na bilo koju drugu kodnu riječ)

Primjer:

• kôd sa samo 4 ispravne kodne riječi:

0000000000, 0000011111, 1111100000, 1111111111

• Hammingova udaljenost kôda je 5
• mogu se ispravljati 2 bitne greške (k=2, jer je 2k +1 = 5)
• ako npr. stigne 0000000111, primaoc zna da original mora biti 0000011111
• ako je došlo do 3-struke greške, npr. umjesto 0000000000 stiglo 0000000111, greška neće biti korektno ispravljena