(4)Manual Retele Calculatoare (de Stiut)

8/2/2019 (4)Manual Retele Calculatoare (de Stiut)

1/405

Retele de calculatoare

Principii

Radu-Lucian Lupsa


2/405

Aceasta este editia electronica a cartii Retele de calculatoare, publicata laCasa Cartii de Stiinta, n 2008, ISBN: 978-973-133-377-9.

Drepturile de autor apartin subsemnatului, Radu-Lucian Lupsa.Subsemnatul, Radu-Lucian Lupsa, acord oricui doreste dreptul de a copiacontinutul acestei carti, integral sau partial, cu conditia atribuirii corecte autorului sia pastrarii acestei notite.

Cartea poate fi descarcata gratuit de la adresahttp://www.cs.ubbcluj.ro/~rlupsa/works/retele.pdf


3/405

c 2008, Radu-Lucian Lupsa5

Cuprins

Principii

Cuprins 5

Prefata 13

1 Introducere 15

1.1 Serviciile oferite de retea . . . . . . . . . . . . . . . . . . . . . . . . . 151.2 Principalele elemente ale unei retele de calculatoare . . . . . . . . . . 201.3 Premise generale n elaborarea si implementarea protocoalelor n retele

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2 Notiuni de teoria informatiei 25

2.1 Problema codificarii informatiei pentru un canal discret . . . . . . . . 262.2 Coduri cu proprietatea de prefix . . . . . . . . . . . . . . . . . . . . . 29

2.2.1 Reprezentarea arborescenta a codurilor prefix . . . . . . . . . . . 292.2.2 Decodificarea n cazul codurilor prefix . . . . . . . . . . . . . . . 31

2.2.3 Lungimile cuvintelor unui cod prefix . . . . . . . . . . . . . . . . 332.3 Coduri optime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

2.3.1 Cantitatea de informatie . . . . . . . . . . . . . . . . . . . . . . 402.3.2 Lungimea medie a cuvintelor de cod . . . . . . . . . . . . . . . . 412.3.3 Generarea codului optim prin algoritmul lui Huffman . . . . . . 442.3.4 Compresia fisierelor . . . . . . . . . . . . . . . . . . . . . . . . . 50

2.4 Coduri detectoare si corectoare de erori . . . . . . . . . . . . . . . . . 512.4.1 Modelul erorilor . . . . . . . . . . . . . . . . . . . . . . . . . . . 522.4.2 Principiile codurilor detectoare si corectoare de erori . . . . . . . 532.4.3 Cateva coduri detectoare sau corectoare de erori . . . . . . . . . 55

2.4.3.1 Bitul de paritate . . . . . . . . . . . . . . . . . . . . . . . . 552.4.3.2 Paritate pe linii si coloane . . . . . . . . . . . . . . . . . . . 55

2.4.3.3 Coduri polinomiale . . . . . . . . . . . . . . . . . . . . . . . 562.4.4 Coduri detectoare si corectoare de erori n alte domenii . . . . . 57


4/405

c 2008, Radu-Lucian Lupsa6 Cuprins

3 Nivelul fizic 593.1 Problema transmisiei informatiei la nivelul fizic . . . . . . . . . . . . 59

3.2 Transmiterea semnalelor . . . . . . . . . . . . . . . . . . . . . . . . . 603.2.1 Modificarile suferite de semnale . . . . . . . . . . . . . . . . . . . 603.2.2 Analiza transmiterii semnalelor cu ajutorul transformatei Fourier

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 623.3 Codificarea informatiei prin semnale continue . . . . . . . . . . . . . 65

3.3.1 Scheme de codificare . . . . . . . . . . . . . . . . . . . . . . . . . 653.3.2 Modulatia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 683.3.3 Multiplexarea n frecventa . . . . . . . . . . . . . . . . . . . . . 713.3.4 Capacitatea maxima a unui canal de comunicatie . . . . . . . . . 71

3.4 Transmisia prin perechi de conductoare . . . . . . . . . . . . . . . . . 723.4.1 Constructia cablului . . . . . . . . . . . . . . . . . . . . . . . . . 72

3.4.2 Proprietati ale mediului . . . . . . . . . . . . . . . . . . . . . . . 743.4.3 Legatura magistrala . . . . . . . . . . . . . . . . . . . . . . . . . 753.4.4 Considerente practice . . . . . . . . . . . . . . . . . . . . . . . . 76

3.5 Transmisia prin unde radio . . . . . . . . . . . . . . . . . . . . . . . . 773.5.1 Propagarea undelor . . . . . . . . . . . . . . . . . . . . . . . . . 78

3.5.1.1 Polarizarea . . . . . . . . . . . . . . . . . . . . . . . . . . . 783.5.1.2 Absorbtia si reflexia . . . . . . . . . . . . . . . . . . . . . . 793.5.1.3 Difractia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 793.5.1.4 Interferenta undelor . . . . . . . . . . . . . . . . . . . . . . 803.5.1.5 Divergenta undelor . . . . . . . . . . . . . . . . . . . . . . . 80

3.5.2 Antene . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 803.5.2.1 Directivitatea . . . . . . . . . . . . . . . . . . . . . . . . . . 813.5.2.2 Polarizarea . . . . . . . . . . . . . . . . . . . . . . . . . . . 833.5.2.3 Tipuri de antene . . . . . . . . . . . . . . . . . . . . . . . . 83

3.5.3 Raza de actiune a unei legaturi radio . . . . . . . . . . . . . . . 833.5.3.1 Obstacolele . . . . . . . . . . . . . . . . . . . . . . . . . . . 833.5.3.2 Linia orizontului . . . . . . . . . . . . . . . . . . . . . . . . 843.5.3.3 Utilizarea satelitilor artificiali ai Pamantului . . . . . . . . . 843.5.3.4 Zgomotul . . . . . . . . . . . . . . . . . . . . . . . . . . . . 853.5.3.5 Scaderea puterii cu distanta . . . . . . . . . . . . . . . . . . 86

3.5.3.6 Emisia directionata si polarizata . . . . . . . . . . . . . . . 863.5.4 Spectrul radio si alocarea lui . . . . . . . . . . . . . . . . . . . . 863.5.5 Particularitati ale sistemelor de comunicatie prin radio . . . . . 88

3.5.5.1 Topologia legaturii . . . . . . . . . . . . . . . . . . . . . . . 883.5.5.2 Fiabilitatea . . . . . . . . . . . . . . . . . . . . . . . . . . . 893.5.5.3 Securitatea . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

3.6 Transmisia optica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 893.6.1 Constructia mediului . . . . . . . . . . . . . . . . . . . . . . . . 90

3.6.1.1 Conectarea fibrelor optice . . . . . . . . . . . . . . . . . . . 913.6.2 Propagarea semnalului optic . . . . . . . . . . . . . . . . . . . . 91

3.6.2.1 Moduri de propagare . . . . . . . . . . . . . . . . . . . . . . 91


5/405

c 2008, Radu-Lucian LupsaCuprins 7

3.6.2.2 Caracteristici ale mediului . . . . . . . . . . . . . . . . . . . 923.6.2.3 Multiplexarea n lungimea de unda . . . . . . . . . . . . . . 92

3.6.3 Considerente practice . . . . . . . . . . . . . . . . . . . . . . . . 934 Nivelul legaturii de date 95

4.1 Detectarea si corectarea erorilor . . . . . . . . . . . . . . . . . . . . . 964.2 Controlul accesului la mediu . . . . . . . . . . . . . . . . . . . . . . . 97

4.2.1 Protocoale bazate pe asigurarea unui interval exclusiv de emisie . 984.2.2 Protocoale bazate pe coliziuni si retransmitere . . . . . . . . . . 994.2.3 Protocoale mixte . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

4.3 Retransmiterea pachetelor pierdute . . . . . . . . . . . . . . . . . . . 1024.3.1 Principiul confirmarilor pozitive si retransmiterilor . . . . . . . . 1034.3.2 Trimiterea n avans a mai multor pachete . . . . . . . . . . . . . 108

4.3.3 Spatiul numerelor de confirmare . . . . . . . . . . . . . . . . . . 1094.4 Controlul fluxului . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

4.4.1 Cereri de suspendare si de continuare . . . . . . . . . . . . . . . 1154.4.2 Mecanismul pas cu pas . . . . . . . . . . . . . . . . . . . . . . . 1154.4.3 Mecanism combinat cu retransmiterea pachetelor pierdute . . . . 116

4.5 Multiplexarea n timp . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

5 Nivelul retea si nivelul transport 1195.1 Retransmiterea datelor de catre nodurile intermediare . . . . . . . . . 120

5.1.1 Retransmiterea n retele bazate pe datagrame . . . . . . . . . . . 1225.1.2 Retransmiterea n retele bazate pe conexiuni . . . . . . . . . . . 122

5.2 Algoritmi de dirijare . . . . . . . . . . . . . . . . . . . . . . . . . . . 1255.2.1 Calculul drumurilor cu informatii complete despre graful retelei . 1275.2.2 Calculul drumurilor optime prin schimb de informatii de distanta . 1285.2.3 Dirijarea ierarhica . . . . . . . . . . . . . . . . . . . . . . . . . . 1365.2.4 Metode particulare de dirijare . . . . . . . . . . . . . . . . . . . 139

5.2.4.1 Inundarea . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1395.2.4.2 Invatarea rutelor din adresele sursa ale pachetelor . . . . . 140

5.2.5 Metode de difuziune . . . . . . . . . . . . . . . . . . . . . . . . . 1405.3 Functionarea la trafic ridicat . . . . . . . . . . . . . . . . . . . . . . . 141

5.3.1 Alegerea pachetelor de transmis . . . . . . . . . . . . . . . . . . 142

5.3.2 Controlul congestiei . . . . . . . . . . . . . . . . . . . . . . . . . 1435.3.3 Formarea (limitarea) traficului . . . . . . . . . . . . . . . . . . . 1445.3.4 Rezervarea resurselor . . . . . . . . . . . . . . . . . . . . . . . . 145

5.4 Nivelul transport . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1465.5 Interconectarea retelelor . . . . . . . . . . . . . . . . . . . . . . . . . 147

6 Metode si protocoale criptografice 1496.1 Asigurarea confidentialitatii . . . . . . . . . . . . . . . . . . . . . . . 151

6.1.1 Introducere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1516.1.2 Refolosirea cheilor . . . . . . . . . . . . . . . . . . . . . . . . . . 1546.1.3 Problema spargerii unui cifru . . . . . . . . . . . . . . . . . . . . 155


6/405


6.1.4 Algoritmi de criptare utilizati n practica . . . . . . . . . . . . . 1576.1.5 Criptografie asimetrica (cu cheie publica) . . . . . . . . . . . . . 163

6.1.5.1 Utilizarea criptografiei asimetrice . . . . . . . . . . . . . . . 1646.2 Autentificarea mesajelor . . . . . . . . . . . . . . . . . . . . . . . . . 1656.2.1 Functii de dispersie criptografice . . . . . . . . . . . . . . . . . . 166

6.2.1.1 Utilizarea functiilor de dispersie . . . . . . . . . . . . . . . . 1676.2.2 Functii de dispersie cu cheie . . . . . . . . . . . . . . . . . . . . . 1686.2.3 Semnatura digitala . . . . . . . . . . . . . . . . . . . . . . . . . . 1696.2.4 Verificarea prospetimii mesajelor . . . . . . . . . . . . . . . . . . 1716.2.5 Combinarea criptarii, autentificarii si verificarii prospetimii . . . 173

6.3 Stabilirea cheilor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1736.3.1 Stabilirea cheilor n prezenta unui adversar pasiv . . . . . . . . . 176

6.3.1.1 Stabilirea cheilor prin criptografie asimetrica . . . . . . . . 176

6.3.1.2 Stabilirea cheii prin metoda Diffie-Hellman . . . . . . . . . 1776.3.1.3 Atacul man-in-the-middle . . . . . . . . . . . . . . . . . . . 178

6.3.2 Stabilirea cheilor n prezenta unui adversar activ . . . . . . . . . 1786.3.3 Stabilirea cheilor cu ajutorul unui tert de ncredere . . . . . . . . 1806.3.4 Certificarea cheilor publice . . . . . . . . . . . . . . . . . . . . . 1826.3.5 Transportul prin utilizatori umani . . . . . . . . . . . . . . . . . 183

6.4 Numere aleatoare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1856.4.1 Generatoare fizice . . . . . . . . . . . . . . . . . . . . . . . . . . 1866.4.2 Generatoare de numere pseudoaleatoare . . . . . . . . . . . . . . 1866.4.3 Generatoare utilizate n practica . . . . . . . . . . . . . . . . . . 188

6.5 Autentificarea utilizatorilor . . . . . . . . . . . . . . . . . . . . . . . . 1886.5.1 Stocarea parolelor . . . . . . . . . . . . . . . . . . . . . . . . . . 1886.5.2 Parole de unica folosinta . . . . . . . . . . . . . . . . . . . . . . 189

Protocoale

Cuprins 195

7 Codificari de interes practic 2037.1 Probleme privind reprezentarea numerelor ntregi . . . . . . . . . . . 203

7.1.1 Reprezentari pe biti . . . . . . . . . . . . . . . . . . . . . . . . . 2037.1.1.1 Bitul . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2047.1.1.2 Siruri de biti . . . . . . . . . . . . . . . . . . . . . . . . . . 2047.1.1.3 Reprezentarea pe biti a numerelor ntregi . . . . . . . . . . 205

7.1.2 Reprezentari pe octeti . . . . . . . . . . . . . . . . . . . . . . . . 2067.1.2.1 Octeti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2067.1.2.2 Siruri de octeti . . . . . . . . . . . . . . . . . . . . . . . . . 2087.1.2.3 Reprezentarea numerelor pe un numar ntreg de octeti . . . 2087.1.2.4 Reprezentarea numerelor pe un sir arbitar de biti . . . . . . 210

7.1.3 Probleme privind reprezentarea lungimii sirurilor . . . . . . . . . 2127.1.4 Alte metode de reprezentare a numerelor ntregi . . . . . . . . . 214


7/405


7.2 Codificarea textelor . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2157.2.1 Codificarea ASCII . . . . . . . . . . . . . . . . . . . . . . . . . . 216

7.2.2 Codificarile ISO-8859 . . . . . . . . . . . . . . . . . . . . . . . . 2177.2.3 Codificarile Unicode . . . . . . . . . . . . . . . . . . . . . . . . . 2187.2.3.1 Codificarea UTF-8 . . . . . . . . . . . . . . . . . . . . . . . 2207.2.3.2 Codificarile UTF-16 . . . . . . . . . . . . . . . . . . . . . . 2207.2.3.3 Codificarile UTF-32 . . . . . . . . . . . . . . . . . . . . . . 221

7.3 Reprezentarea datei si orei . . . . . . . . . . . . . . . . . . . . . . . . 2217.3.1 Masurarea timpului . . . . . . . . . . . . . . . . . . . . . . . . . 2227.3.2 Obiectivele n alegerea reprezentarii timpului n calculator . . . . 2247.3.3 Formate utilizate n practica . . . . . . . . . . . . . . . . . . . . 225

7.3.3.1 Formatul utilizat de posta electronica . . . . . . . . . . . . 2257.3.3.2 ISO-8601 si RFC-3339 . . . . . . . . . . . . . . . . . . . . . 2267.3.3.3 Timpul POSIX . . . . . . . . . . . . . . . . . . . . . . . . . 2277.3.3.4 TAI 64 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227

7.4 Recodificari . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2287.4.1 Codificarea hexazecimala . . . . . . . . . . . . . . . . . . . . . . 2287.4.2 Codificarea n baza 64 . . . . . . . . . . . . . . . . . . . . . . . . 2297.4.3 Codificari bazate pe secvente de evitare . . . . . . . . . . . . . . 229

8 Programarea n retea introducere 2318.1 Interfata de programare socket BSD . . . . . . . . . . . . . . . . . . . 231

8.1.1 Comunicatia prin conexiuni . . . . . . . . . . . . . . . . . . . . . 232

8.1.1.1 Deschiderea conexiunii de catre client . . . . . . . . . . . . 2338.1.1.2 Deschiderea conexiunii de catre server . . . . . . . . . . . . 2338.1.1.3 Comunicatia propriu-zisa . . . . . . . . . . . . . . . . . . . 2348.1.1.4 Inchiderea conexiunii . . . . . . . . . . . . . . . . . . . . . . 234

8.1.2 Comunicatia prin datagrame . . . . . . . . . . . . . . . . . . . . 2358.1.3 Principalele apeluri sistem . . . . . . . . . . . . . . . . . . . . . 237

8.1.3.1 Functia socket() . . . . . . . . . . . . . . . . . . . . . . . . 2378.1.3.2 Functia connect() . . . . . . . . . . . . . . . . . . . . . . . 2378.1.3.3 Functia bind() . . . . . . . . . . . . . . . . . . . . . . . . . 2388.1.3.4 Functia listen() . . . . . . . . . . . . . . . . . . . . . . . . 239

8.1.3.5 Functia accept() . . . . . . . . . . . . . . . . . . . . . . . . 2398.1.3.6 Formatul adreselor . . . . . . . . . . . . . . . . . . . . . . . 2408.1.3.7 Interactiunea dintre connect(), listen() si accept() . . . 2428.1.3.8 Functiile getsockname() si getpeername() . . . . . . . . . 2428.1.3.9 Functiile send() si recv() . . . . . . . . . . . . . . . . . . 2438.1.3.10 Functiile shutdown() si close() . . . . . . . . . . . . . . . 2458.1.3.11 Functiile sendto() si recvfrom() . . . . . . . . . . . . . . 245

8.1.4 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2468.1.4.1 Comunicare prin conexiune . . . . . . . . . . . . . . . . . . 2468.1.4.2 Comunicare prin datagrame . . . . . . . . . . . . . . . . . . 249

8.2 Formatarea datelor . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252


8/405


8.2.1 Formate binare . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2528.2.1.1 Tipuri ntregi . . . . . . . . . . . . . . . . . . . . . . . . . . 252

8.2.1.2 Siruri de caractere si tablouri . . . . . . . . . . . . . . . . . 2548.2.1.3 Variabile compuse (struct-uri) . . . . . . . . . . . . . . . . 2558.2.1.4 Pointeri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257

8.2.2 Formate text . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2578.2.3 Probleme de robustete si securitate . . . . . . . . . . . . . . . . 2578.2.4 Probleme privind costul apelurilor sistem . . . . . . . . . . . . . 258

8.3 Probleme de concurenta n comunicatie . . . . . . . . . . . . . . . . . 260

9 Retele IEEE 802 2639.1 Retele IEEE 802.3 (Ethernet) . . . . . . . . . . . . . . . . . . . . . . 263

9.1.1 Legaturi punct la punct prin perechi de conductoare . . . . . . . 266

9.1.2 Legaturi prin fibre optice . . . . . . . . . . . . . . . . . . . . . . 2729.1.3 Legaturi prin cablu magistrala . . . . . . . . . . . . . . . . . . . 2749.1.4 Repetoarele si comutatoarele . . . . . . . . . . . . . . . . . . . . 2779.1.5 Dirijarea efectuata de comutatoare (switch-uri) . . . . . . . . . . 2799.1.6 Facilitati avansate ale switch-urilor . . . . . . . . . . . . . . . . . 279

9.1.6.1 Switch-uri configurabile . . . . . . . . . . . . . . . . . . . . 2799.1.6.2 Filtrare pe baza de adrese MAC . . . . . . . . . . . . . . . 2809.1.6.3 Trunking . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2809.1.6.4 Legaturi redundante . . . . . . . . . . . . . . . . . . . . . . 2819.1.6.5 Retele virtuale (VLAN) . . . . . . . . . . . . . . . . . . . . 281

9.1.7 Considerente privind proiectarea unei retele . . . . . . . . . . . . 2829.2 Retele IEEE 802.11 (Wireless) . . . . . . . . . . . . . . . . . . . . . . 283

9.2.1 Arhitectura retelei . . . . . . . . . . . . . . . . . . . . . . . . . . 2839.2.2 Accesul la mediu . . . . . . . . . . . . . . . . . . . . . . . . . . . 2859.2.3 Generarea pachetelor beacon . . . . . . . . . . . . . . . . . . . . 2869.2.4 Securitatea retelelor 802.11 . . . . . . . . . . . . . . . . . . . . . 286

10 Internetul 29110.1 Arhitectura retelei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29110.2 Protocolul IP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292

10.2.1 Structura pachetului IP . . . . . . . . . . . . . . . . . . . . . . . 29310.2.2 Bazele dirijarii pachetelor IP . . . . . . . . . . . . . . . . . . . . 29410.2.2.1 Subretele si interfete . . . . . . . . . . . . . . . . . . . . . . 29410.2.2.2 Prefixul de retea . . . . . . . . . . . . . . . . . . . . . . . . 29510.2.2.3 Tabela de dirijare . . . . . . . . . . . . . . . . . . . . . . . . 296

10.2.3 Scrierea ca text a adreselor si prefixelor . . . . . . . . . . . . . . 29810.2.3.1 Scrierea adreselor IP . . . . . . . . . . . . . . . . . . . . . . 29810.2.3.2 Scrierea prefixelor de retea . . . . . . . . . . . . . . . . . . . 300

10.2.4 Alocarea adreselor IP si prefixelor de retea . . . . . . . . . . . . 30010.2.4.1 Alocarea pe utilizari . . . . . . . . . . . . . . . . . . . . . . 30110.2.4.2 Alocarea adreselor si dirijarea ierarhica . . . . . . . . . . . . 301


9/405


10.2.5 Erori la dirijare si protocolul ICMP . . . . . . . . . . . . . . . . 30210.2.5.1 Pachete nelivrabile . . . . . . . . . . . . . . . . . . . . . . . 303

10.2.5.2 Diagnosticarea functionarii rutelor . . . . . . . . . . . . . . 30510.2.5.3 Ciclarea pachetelor IP . . . . . . . . . . . . . . . . . . . . . 30510.2.5.4 Congestia . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30610.2.5.5 Redirectionarea . . . . . . . . . . . . . . . . . . . . . . . . . 306

10.2.6 Alte chestiuni privind dirijarea pachetelor . . . . . . . . . . . . . 30710.2.6.1 Dimensiunea maxima a pachetelor si fragmentarea . . . . . 30710.2.6.2 Calitatea serviciului . . . . . . . . . . . . . . . . . . . . . . 308

10.2.7 Configurarea si testarea unei retele IP locale . . . . . . . . . . . 30910.2.7.1 Alegerea parametrilor . . . . . . . . . . . . . . . . . . . . . 30910.2.7.2 Configurarea parametrilor de retea pe diverse sisteme de op-

erare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312

10.2.7.3 Testarea si depanarea retelelor . . . . . . . . . . . . . . . . 31310.3 Nivelul transport . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314

10.3.1 Conexiuni cu livrare garantata: protocolul TCP . . . . . . . . . 31410.3.1.1 Principiul conexiunii TCP . . . . . . . . . . . . . . . . . . . 31510.3.1.2 Comunicatia bidirectionala . . . . . . . . . . . . . . . . . . 32010.3.1.3 Deschiderea si nchiderea conexiunii . . . . . . . . . . . . . 32010.3.1.4 Alegerea numarului initial de secventa . . . . . . . . . . . . 32310.3.1.5 Inchiderea fortata a conexiunii . . . . . . . . . . . . . . . . 32410.3.1.6 Identificarea aplicatiei destinatie . . . . . . . . . . . . . . . 32510.3.1.7 Corespondenta ntre functiile socket() si actiunile modulu-

lui TCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32610.3.1.8 Controlul fluxului . . . . . . . . . . . . . . . . . . . . . . . . 32710.3.1.9 Stabilirea time-out-ului pentru retransmiterea pachetelor . . 32710.3.1.10Algoritmul lui Nagle si optimizarea numarului de pachete . 32810.3.1.11Trimiterea datelor speciale (out of band) . . . . . . . . . . . 328

10.3.2 Datagrame nesigure: UDP . . . . . . . . . . . . . . . . . . . . . 32910.4 Identificarea nodurilor dupa nume: sistemul DNS . . . . . . . . . . . 330

10.4.1 Numele de domeniu . . . . . . . . . . . . . . . . . . . . . . . . . 33010.4.2 Structura logica a bazei de date DNS . . . . . . . . . . . . . . . 33210.4.3 Impartirea n domenii de autoritate . . . . . . . . . . . . . . . . 333

10.4.4 Mecanismul de interogare a serverelor . . . . . . . . . . . . . . . 33410.4.5 Sincronizarea serverelor pentru un domeniu . . . . . . . . . . . . 33510.4.6 Cautarea numelui dupa IP . . . . . . . . . . . . . . . . . . . . . 336

10.5 Legaturile directe ntre nodurile IP . . . . . . . . . . . . . . . . . . . 33710.5.1 Rezolvarea adresei ARP . . . . . . . . . . . . . . . . . . . . . 337

10.6 Configurarea automata a statiilor DHCP . . . . . . . . . . . . . . 33910.7 Situatii speciale n dirijarea pachetelor . . . . . . . . . . . . . . . . . 341

10.7.1 Filtre de pachete (firewall) . . . . . . . . . . . . . . . . . . . . . 34110.7.2 Retele private . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34610.7.3 Translatia adreselor (NAT) . . . . . . . . . . . . . . . . . . . . . 347

10.7.3.1 Translatia adresei sursa . . . . . . . . . . . . . . . . . . . . 347


10/405


10.7.3.2 Translatia adresei destinatie . . . . . . . . . . . . . . . . . . 35010.7.4 Tunelarea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351

11 Aplicatii n retele 35311.1 Posta electronica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353

11.1.1 Formatul mesajelor . . . . . . . . . . . . . . . . . . . . . . . . . 35411.1.1.1 Antetul mesajelor . . . . . . . . . . . . . . . . . . . . . . . . 35511.1.1.2 Extensii MIME . . . . . . . . . . . . . . . . . . . . . . . . . 35811.1.1.3 Atasarea fisierelor si mesaje din mai multe parti . . . . . . 35911.1.1.4 Codificarea corpului mesajului si a atasamentelor . . . . . . 360

11.1.2 Transmiterea mesajelor . . . . . . . . . . . . . . . . . . . . . . . 36211.1.2.1 Protocolul SMTP . . . . . . . . . . . . . . . . . . . . . . . . 36211.1.2.2 Determinarea urmatorului MTA . . . . . . . . . . . . . . . 365

11.1.2.3 Configurarea unui MTA . . . . . . . . . . . . . . . . . . . . 36611.1.3 Securitatea postei electronice . . . . . . . . . . . . . . . . . . . . 368

11.2 Sesiuni interactive la distanta . . . . . . . . . . . . . . . . . . . . . . 37111.2.1 Protocolul ssh . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373

11.2.1.1 Conexiunea ssh protejata criptografic . . . . . . . . . . . . 37311.2.1.2 Metode de autentificare n ssh . . . . . . . . . . . . . . . . . 37611.2.1.3 Multiplexarea conexiunii, tunelarea si aplicatii . . . . . . . 379

11.2.2 Sistemul X-Window . . . . . . . . . . . . . . . . . . . . . . . . . 37911.3 Transferul fisierelor n retea . . . . . . . . . . . . . . . . . . . . . . . 380

11.3.1 Protocolul ftp . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38111.3.2 Protocolul HTTP . . . . . . . . . . . . . . . . . . . . . . . . . . 382

11.3.2.1 Structura cererilor si a raspunsurilor . . . . . . . . . . . . . 38311.3.2.2 URL-urile . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38411.3.2.3 Alte facilitati HTTP . . . . . . . . . . . . . . . . . . . . . . 38511.3.2.4 Proxy HTTP . . . . . . . . . . . . . . . . . . . . . . . . . . 38611.3.2.5 Conexiuni securizate: SSL/TLS . . . . . . . . . . . . . . . . 38711.3.2.6 Utilizarea TLS pentru web . . . . . . . . . . . . . . . . . . 389

11.4 PGP/GPG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39011.4.1 Structura cheilor GnuPG . . . . . . . . . . . . . . . . . . . . . . 390

11.4.1.1 Chei primare si subchei . . . . . . . . . . . . . . . . . . . . 39111.4.1.2 Utilizatori si identitati . . . . . . . . . . . . . . . . . . . . . 392

11.4.1.3 Generarea si modificarea cheilor . . . . . . . . . . . . . . . . 39211.4.1.4 Controlul perioadei de valabilitate a cheilor . . . . . . . . . 39311.4.1.5 Gestiunea cheilor secrete . . . . . . . . . . . . . . . . . . . . 395

11.4.2 Transmiterea si certificarea cheilor publice . . . . . . . . . . . . . 39511.4.2.1 Transmiterea cheilor publice . . . . . . . . . . . . . . . . . . 39511.4.2.2 Verificarea autenticitatii cheilor . . . . . . . . . . . . . . . . 397

11.4.3 Transmiterea mesajelor criptate sau semnate . . . . . . . . . . . 399

Bibliografie 401

Index 405


11/405


Prefata

In contextul prezent al dezvoltarii retelelor de calculatoare, este inutil

sa mai subliniem importanta acestui domeniu.Lucrarea de fata se adreseaza n principal programatorilor de aplicatiin retea si administratorilor de retele complexe. Sunt presupuse, din parteacititorului, cunostinte de baza de programare, precum si privind functionareasistemelor de operare.

Ca un avertisment pentru programatori, mentionam ca, desi lucrareatrateaza chestiuni de nivel mult mai coborat decat cel al platformelor si bib-liotecilor utilizate n mod normal n aplicatiile n retea, este totusi utila nvederea unei bune ntelegeri a acestor platforme si biblioteci.

Tot ceea ce are legatura ntr-un fel sau altul cu calculatoare are douacaracteristici: se dezvolta foarte repede si est foarte complex. Retelele decalculatoare nu fac exceptie. Ca urmare, este extrem de usor pentru oricinesa se piarda n nenumaratele detalii n permanenta schimbare.

Consideram ca, n orice domeniu, o buna prezentare trebuie sa porneascade la principiile de baza. Principiile de baza se sunt (relativ) simple si evolueazamult mai lent decat constructiile tehnice elaborate pe baza lor. In consecinta,prima parte a lucrarii de fata, principii, este dedicata studierii problemelor cetrebuie rezolvate de o retea de calculatoare, precum si a principiilor constructieiposibilelor solutii ale acestor probleme.

Partea a doua a lucrarii, protocoale, prezinta cateva dintre cele mairaspandite protocoale si mecanisme utilizate n retelele de calculatoare. Ea esteconstruita pentru a oferi cititorului o privire de ansamblu asupra protocoalelorstudiate. Aceasta privire de ansamblu poate fi suficienta pentru unii cititori,n caz contrar fiind probabil necesara citirea efectiva a standardelor.

Lucrarea de fata este rodul experientei autorului n activitati legatede administrarea retelei de calculatoare a Departamentului de Informatica alFacultatii de Matematica si Informatica din cadrul Universitatii Babes-BolyaiCluj-Napoca, n predarea unui curs de Retele de calculatoare la aceasta fac-


12/405

c 2008, Radu-Lucian Lupsa14 Prefata

ultate, precum si din activitatea de cercetare desfasurata de-a lungul anilor, nspecial de nevoile practice din cadrul contractului de cercetare PNII 11003/2007

- Sistem decizional bazat pe tehnici de tip multi-agent pentru generarea, opti-mizarea si managementul registrelor nationale de boli cronice netransmisibile -CRONIS. Seturile mari de date ce se vehiculeaza n sistemul medical, precumsi nevoia de confidentialitate si securitate a lor, cer o foarte buna cunoasteresi punere n practica a notiunilor legate de codificarea informatiei, de metodesi protocoale criptografice, de aplicatii n retele etc.


13/405


Capitolul 1

Introducere

Prin retea de calculatoare ntelegem un sistem (constand din com-ponente hard si soft) care interconecteaza niste calculatoare, permitand unorprograme ce se executa pe aceste calculatoare sa comunice ntre ele.

De notat ca, n uzul comun, termenul de retea de calculatoare mai aresi sensul de sistem de calcul, construit din mai multe calculatoare interconec-tate ntr-o retea, care se comporta ca un sistem unitar, de exemplu, prezintaaceleasi conturi de utilizatori pe toate calculatoarele.

1.1. Serviciile oferite de retea

Se spune ca orice problema bine formulata este pe jumatate rezolvata.Prin urmare, pentru nceput, vom stabili mai exact ce se doreste de la o reteade calculatoare.

Intr-o retea de calculatoare avem mai multe calculatoare pe care seexecuta procese utilizator. Rolul retelei este de-a oferi acestor procese posi-bilitatea de-a comunica ntre ele. Din punctul de vedere al programatorului

acestor procese, reteaua ofera niste functii, din nucleul sistemului de oper-are sau din biblioteci standard, apelabile de catre aceste procese (fig. 1.1).Ansamblul acestor functii constituie interfata de programare (engl. API Application Programming Interface) a retelei.

Principalele functii oferite de retea, apelabile de catre un proces uti-lizator, sunt o functie care trimite date de la procesul curent spre partenerulsau partenerii de comunicatie si o functie care receptioneaza datele trimise spreprocesul curent. In aceste functii este necesara desemnarea destinatarului sprecare procesul emitator doreste transmiterea datelor, respectiv a emitatoruluidinspre care procesul receptor solicita sa primeasca date. In acest scop, fiecare


14/405

c 2008, Radu-Lucian Lupsa16 1.1. Serviciile oferite de retea

calculator

Processursa

Procesdestinatie

calculator

Retea

interfata de

programare (API)

send()

recv()

Figura 1.1: Reteaua de calculatoare, din punctul de vedere al proceselor aplicatie.Functionalitatea retelei este oferita prin functii apelabile din procesele utilizator.Reteaua ofera o aplicatiilor o cale de transmisie a datelor (linia punctata). Constructiaefectiva a retelei nu este vizibila aplicatiilor.

entitate ce poate comunica n retea trebuie sa aiba asociata o adresa (un sirde biti, construit dupa anumite reguli, identificand unic o anumita entitate).

Pe langa aceste functii de baza, reteaua mai ofera functii pentru con-figurarea diferitilor parametrii. O parte dintre acesti parametri fixeaza rolulsi locul diverselor componente n cadrul retelei (de exemplu, fiecare calculatortrebuie sa-si cunoasca propria adresa). Alti parametrii sunt legati de calitateaserviciilor oferite de retea (debit de transfer de date, timp de propagare, etc).

Datele transmise de procesele utilizator sunt de obicei siruri arbitrarede octeti. Rolul retelei este de-a transmite ntocmai sirul de octeti trimisde procesul sursa catre procesul destinatie. Semnificatia, pentru procesuldestinatie, a unui sir de octeti transmis face obiectul unei ntelegeri (proto-col) ntre procesele utilizator. La proiectarea retelei nu ne intereseaza ce facprocesele utilizator cu datele transferate; la proiectarea programelor utilizatornu ne intereseaza cum lucreaza reteaua pentru a transmite datele.

In continuare vom trece n revista principalele caracteristici ale ser-viciului oferit de retea proceselor de aplicatie.

O comunicatie poate fi, dupa numarul destinatarilor:

punct la punct, daca exista un singur destinatar. In mod obisnuit, des-tinatarul este selectionat explicit de catre procesul emitator; o astfel decomunicatie este numita unicast. Uneori nsa, de exemplu n cazul ncare un serviciu este oferit de mai multe servere, echivalente din punctulde vedere al clientului, este favorabil ca reteaua sa aleaga destinatarulcomunicatiei, n functie de distanta fata de emitator, dintr-o multime


15/405

c 2008, Radu-Lucian LupsaCapitolul 1. Introducere 17

specificata de destinatari posibili. Un astfel de comunicatie se numesteanycast.

difuziune, daca exista mai multi destinatari. Distingem difuziune com-pleta (engl. broadcast), n care destinatari sunt toate calculatoarele dintr-o retea, si difuziune selectiva (engl. multicast), n care destinatarii sunto submultime aleasa a calculatoarelor din retea.

Serviciul de comunicatie oferit de retea poate fi de tip conexiune saude tip transport de datagrame :

In cazul conexiunilor, n cadrul comunicatiei ntre doua procese se distingtrei faze:

- deschiderea conexiunii, n cadrul careia sunt facute niste pregatiri,inclusiv alocarea unor resurse pentru comunicatie;

- comunicatia propriu-zisa, n care unul sau ambele procese transmiteun sir de pachete sau de biti celuilalt proces;

- nchiderea conexiunii, n cadrul careia se elibereaza resursele alocatela deschidere.

In cazul transportului de datagrame, procesul emitator pregateste unansamblu, numit datagrama (prin analogie cu telegrama), cuprinzand

un sir de biti destinat procesului receptor si anumite informatii necesarelivrarii (adresa destinatarului). Apoi transmite datagrama retelei de cal-culatoare, care o transmite procesului receptor. Mai multe datagrametrimise de acelasi proces sursa catre acelasi proces destinatie sunt trans-mise independent una de alta, ceea ce duce, n general, la posibilitateainversarii ordinii de receptie fata de ordinea de emisie a datagramelor.

Principalii parametri de calitate ai serviciului oferit de retea sunt:

Capacitatea de transport oferita de retea, sau debitul maxim acceptat, este

raportul dintre numarul de biti transportati n cadrul unei comunicatiisi timpul n care acestia sunt transmisi. Echivalent, capacitatea esteinversul duratei medii ntre trecerea, printr-un punct dat al retelei, adoi biti consecutivi ai unei comunicatii.

Timpul de transfer a unui bloc de date este timpul scurs de latrecerea, printr-un punct dat, a primului bit al blocului pana la trecerea,prin acelasi punct, a ultimului bit. Timpul de transfer este egal curaportul dintre dimensiunea blocului si debitul cu care se face transferul.

Capacitatea oferita de retea unei legaturi poate sa varieze datoritavariatiei debitului altor comunicatii care partajeaza aceleasi echipamente.


16/405

c 2008, Radu-Lucian Lupsa18 1.1. Serviciile oferite de retea

Exista aplicatii, de exemplul legate de transfer de fisiere, pentrucare este important ca reteaua sa ofere o capacitate medie cat mai mare.

Penttru alte aplicatii, cum ar fi telefonia, transmisia video (de exemplupentru teleconferinte) sau alte aplicatii n timp real, este important sanu scada niciodata capacitatea legaturii sub o anumita valoare minima,nsa o capacitate mai mare nu este utila.

Timpul de propagare ntre doua entitati este timpul scurs ntre mo-mentul n care entitatea sursa emite un bit si momentul n care acel bitajunge la destinatie. Timpul de propagare rezulta din nsumarea tim-pului de propagare a semnalului de-a lungul mediului de comunicat iecu diversii timpi de asteptare a datelor n diverse zone tampon. De re-

marcat ca timpul de propagare a semnalului este egal cu distanta de laemitator la receptor mpartita la viteza de propagare a semnalului, iarviteza de propagare nu poate depasi viteza luminii n vid; din acest mo-tiv, de exemplu, timpul de propagare prin legaturi prin satelit nu poatefi mai scurt de cateva zecimi de secunda.

Timpul scurs de la nceputul transmisiei unui bloc de date de catreemitator pana la finalul receptiei blocului de catre receptor este egal cusuma dintre timpul de transfer si timpul de propagare.

Uneori, n loc de timpul de propagare se utilizeaza o alta marime,timpul dus-ntors, care este timpul scurs de la transmiterea unui mesajde catre o partenerul de comunicatie pana la primirea raspunsului dinpartea acestuia. Timpul dus-ntors este suma dintre timpii de propa-gare pentru cele doua sensuri si timpul de procesare pentru crearearaspunsului.

Evident, timpul de propagare e bine sa fie cat mai scurt, nsadiferite aplicatii au cerinte diferite:

- La unele aplicatii timpul de propagare nu este prea important. Deexemplu, la transferul unui fisier mare, la care oricum timpul detransfer este mare, timpul de propagare influenteaza foarte putintimpul total necesar transmiterii fisierului.

- La difuzarea de materiale audio sau video, un timp de propagaremare nu este deranjant, nsa este important ca el sa fie constantn timp. Aceasta pentru ca nu este deranjant daca o transmisiede televiziune este cu cateva secunde n ntarziere fata de eveni-mentele transmise, nsa este important sa nu fie momente n careimaginea ,,ngheata datorita cresterii timpului de propagare simomente n care imaginea ,,sare nainte datorita scurtarii timpu-lui de propagare.


17/405


18/405

c 2008, Radu-Lucian Lupsa20 1.2. Principalele elemente ale unei retele de calculatoare

1.2. Principalele elemente ale unei retele de calcula-toare

Pentru ca doua dispozitive aflate la distanta unul de celalalt sa poatacomunica, este nevoie ca cele doua dispozitive sa fie legate printr-un mediu decomunicatie care permite propagarea variatiei unei marimi fizice. Mediul fizic,mpreuna cu dispozitivele de adaptare ntre reprezentarea locala a informatieisi reprezentarea pe mediul de transmisie constituie nivelul fizic al retelei.Nivelul fizic este deci un modul care permite transmisia unui sir de biti ntredoua dispozitive legate direct unul de celalalt. Constructiv, nivelul fizic esteconstituit din: cablul electric, fibra optica sau, dupa caz, antenele de emisie-

receptie, eventuale amplificatoare sau repetoare, placile de retea din calcula-toare si driver-ele placilor de retea. Constructia nivelului fizic este studiata ncapitolul 3.

De obicei, serviciul oferit de nivelul fizic sufera de anumite neajun-suri, cum ar fi probabilitatea mare a erorilor si transmisia nesigura. Pentrucontracararea acestora, de-o parte si de alta a nivelului fizic se plaseaza cateun modul de adaptare; aceste doua module constituie nivelul legaturii de date.Nivelul legaturii de date este construit partial prin hard (parte a placii deretea) si partial prin soft (parte a driver-ului placii de retea). Constructianivelului legaturii de date este studiata n capitolul 4.

Nivelul fizic mpreuna cu nivelul legaturii de date ofera o legaturabuna ntre doua calculatoare conectate direct printr-un mediu fizic. Ar fineeconomic sa cerem sa existe o legatura directa ntre oricare doua calcula-toare; este preferabil sa putem transmite date prin intermediul unui lant decalculatoare (sau alte dispozitive) legate fizic fiecare cu urmatorul din lant.Realizarea unei astfel de legaturi cade n sarcina nivelului retea, constituitdin cate un modul n fiecare calculator al retelei. Modulul de retea este con-struit prin soft, n nucleul sistemului de operare al fiecarui calculator din retea.Constructia si functionarea nivelului retea este studiata n capitolul 5.

De obicei, serviciul oferit direct de catre nivelul retea nu poate fiutilizat direct de catre programele utilizator. De aceea, ntre modului de reteasi programul utilizator se mai interpune un modul, constituind (mpreuna cumodulul omolog de pe calculatorul partener de comunicatii) nivelul transport.Nivelul transport este constituit din parti ale nucleului sistemului de operaresi, uneori, biblioteci legate n programele utilizator.

Relatiile dintre aceste componente sunt reprezentate n figura 1.2.

Fiecare dintre nivele ofera nivelului superior o interfata care cuprinden principal functii de trimitere si de receptie a datelor. Aceste functii sunt


19/405


Modullegatura

fizica

Modullegatura

fizica

Modullegatura

fizica

Modullegatura

fizica

Nod final

legaturade date

Modullegaturade date

Aplicatie

Modultransport

Modulde retea

Modulul de retea

Modul Modullegaturade date

Mediu fizic Mediu fizic

Nod final

Aplicatie

Modultransport

Modulde retea

Modullegaturade date

Nod intermediar

Nivelul aplicatie

Nivelul transport

Nivelul legaturii

de date

Nivelul retea

Nivelul fizic

Figura 1.2: Componentele unei parti dintr-o retea de calculatoare. Sunt figuratedoar componentele implicate n comunicatia dintre doua aplicatii. Cele doua aplicatiise executa pe doua calculatoare ntre care nu exista o legatura directa, dar exista olegatura printr-un nod intermediar.

similare celor oferite de retea aplicatiilor (asa cum am vazut n 1.1), dar ser-viciile oferite sunt mai primitive. Astfel, nivelul fizic ofera nivelului legaturii dedate servicii de transfer de date, dar numai ntre calculatoare conectate directsi cu riscul ca datele sa fie alterate n timpul transferului sau sa se piarda com-plet. Nivelul legaturii de date ofera nivelului retea servicii de transfer de datemai sigure, dar n continuare cu restrict ia ca transferul este posibil doar ntrecalculatoare conectate direct. Nivelul retea ofera nivelului transport serviciide transfer de date ntre orice doua calculatoare din retea, dar nca neadec-vate utilizarii directe de catre aplicatii (lipsa transmisiei sigure, comunicatie

posibila doar pentru un singur proces aplicatie la un moment dat, etc.).Constructia fiecaruia dintre nivele este independenta de constructiacelorlalte (conteaza doar interfata dintre ele si parametrii de calitate a servi-ciului oferit de un nivel celui imediat superior). De exemplu, n proiectareanivelului retea, nu ne intereseaza nici ce aplicatii vor utiliza reteaua (acelasinivel retea din Internet este utilizat de aplicatii de posta electronica, web,telefonie prin Internet si videoconferinte), nici cum este construit nivelul fizic(perechi de conductoare, fibre optice sau legaturi radio prin satelit).

Modulele, de pe acelasi nivel, din noduri diferite si transmit unulaltuia (utilizand n acest scop serviciile oferite de nivelul inferior) doua tipuri


20/405

c 2008, Radu-Lucian Lupsa22 1.2. Principalele elemente ale unei retele de calculatoare

de date: datele utile a caror transfer este cerut de nivelul superior si datede control necesare coordonarii activitatilor modulelor din cadrul nivelului.

Regulile de reprezentare a acestor date, de organizare a acestora n mesaje,precum si regulile dupa care se trimit mesajele ntre modulele aceluiasi nivelalcatuiesc protocolul de comunicatie al nivelului respectiv.

Functionarea corecta a unei retele necesita respectarea, de catre toatemodulele implicate, a protocoalelor de comunicatie stabilite.

1.3. Premise generale n elaborarea si implementareaprotocoalelor n retele

Pe langa ratiunile pur functionale, studiate pe larg n capitolele urma-toare, n elaborarea si implementarea protocoalelor intervin ratiuni practice,pe care le vom nsira pe scurt n continuare:

Deoarece o retea este formata din multe componente, frecventa cu carese ntampla ca cel putin o componenta a unei retele sa nu functionezecorect este mare. Este necesar ca o defectiune sa afecteze cat mai putindin retea, iar componentele a caror defectare duce la caderea ntregiiretele trebuie sa fie cat mai putine, eventual nici una.

Gasirea unei pene ntr-un sistem complex este, n general, dificila. Reteaua

trebuie sa ofere mecanisme prin care orice defectiune sa fie usor de lo-calizat.

Implementari diferite ale unui protocol se pot abate n moduri diferite dela specificatia protocolului. Este bine ca mici abateri ale parteneruluide comunicatie sa fie tolerate. Rezulta de aici principiul ca o imple-mentare trebuie sa fie stricta cu ceea ce transmite si toleranta cu ceeace receptioneaza.

Reteaua trebuie sa functioneze astazi, sau, un plan bun azi este mai bundecat un plan perfect maine (maxima atribuita generalului americanGeorge Patton, circa 1944). Momentul standardizarii unui protocol esteextrem de delicat: daca este standardizat nainte ca problema de rezolvatsa fie bine nteleasa si solutiile posibile bine analizate, rezulta un protocolprost; daca standardizarea apare prea tarziu, dupa ce s-a raspandit dejaun protocol acceptabil, exista riscul creerii unui protocol perfect, dar pecare nu-l foloseste nimeni deoarece nlocuirea sistemelor existente ar fimai scumpa decat avantajul adus de protocolul mai bun.

Protocoalele totusi evolueaza, iar oprirea ntregii retele n vederea schimbariiechipamentelor afectate de schimbarea protocolului nu este rezonabila.


21/405


Ca urmare, la o schimbare de protocol trebuie avut n vedere existentaunei perioade de tranzitie n timpul careia echipamentele noi trebuie sa

poata comunica cu cele vechi. Tranzitia este mult usurata daca proto-colul vechi prevede anumite facilitati. O posibilitate este ca n protocolsa se prevada o faza de negociere n care fiecare entitate anunta ce versi-uni de protocol si ce extensii de protocol cunoaste, iar apoi comunicatiadecurge conform versiunii celei mai recente si cu cele mai multe exten-sii suportate de ambii parteneri. Alta posibilitate este stabilirea, dela prima versiune a protocolului, a actiunilor unui dispozitiv, ce im-plementeaza o versiune veche a protocolului, la primirea unui mesajneprevazut n acea versiune.

Cerinte diferite ale diferitelor aplicatii duc la tendinta de-a elabora proto-coale complexe, care sa satisfaca pe toata lumea. Protocoale complexeduc la implementari scumpe si cu riscuri mari de-a avea erori. Estepreferabil un protocol care sa ofere cateva operatii simple care sa poatafi combinate dupa dorinta aplicatiei ce-l utilizeaza. Daca o astfel deabordare nu este fezabila, ducand la un protocol prea complex, se re-curge la protocoale ce au posibilitatea de-a fi implementate doar partial;metodele utilizabile n acest scop sunt similare cu cele descrise mai suspentru facilitarea evolutiei protocoalelor.


22/405

c 2008, Radu-Lucian Lupsa24 Capitolul 1. Introducere


23/405


Capitolul 2

Notiuni de teoria informatiei

Teoria informatiei se ocupa cu studiul metodelor de codificare a in-formatiei n vederea transmiterii sau stocarii acesteia. In cadrul teoriei infor-matiei se studiaza si cum se poate masura cantitatea de informatie transmisantr-un mesaj si cum se poate masura eficienta unei anumite codificari.

Prin informatie ntelegem cunostintele unei entitati.

In cele ce urmeaza, ne va interesa problema transmiterii unei infor-matii de la o sursa la o destinatie. Informatia de transmis nu este cunoscutainitial nici de destinatie, nici de sistemul de transmitere. Ca urmare, a prioriinformatia de transmis poate fi vazuta ca o variabila aleatoare.

Comunicatia dintre sursa si destinatie se desfasoara prin intermediulunui canal de comunicatie. Canalul de comunicatie este capabil sa transmitafie o marime variabila n timp, numita semnal (n esenta, o functie realacontinua), caz n care canalul este numit continuu, fie un sir de simboluridintr-o multime finita, caz n care canalul este numit discret.

Deoarece canalul nu poate transmite direct informatia sursei, ntresursa si canal avem nevoie de un dispozitiv, numit emit ator, care transformainformatia utila, produsa de sursa, ntr-un semnal sau, dupa caz, ntr-un sir de

simboluri. Similar, ntre canal si destinatie se plaseaza un dispozitiv, numitreceptor, al carui rol este de-a efectua operatia inversa, si anume de-a ex-trage din semnal sau din sirul de simboluri informatia utila pentru destinatie(fig. 2.1).

DestinatieSursa ReceptorCanalEmitator

Figura 2.1: Transmisia informatiei de la sursa la destinatie


24/405

c 2008, Radu-Lucian Lupsa26 Capitolul 2. Notiuni de teoria informatiei

Semnalul sau, dupa caz, sirul de simboluri ce tranziteaza canalul senumeste reprezentarea informatiei. Regulile de corespondenta dintre informa-

tia utila si reprezentarea sa poarta denumirea de schema de reprezentare ainformatiei, schema de codificare a informatiei sau cod.

Ca exemplu, o limba scrisa este o schema de reprezentare a infor-matiei, pentru un canal discret a carui multime de simboluri contine literelealfabetului limbii respective, precum si spatiul si semnele de punctuatie. Untext scris ntr-o limba este o reprezentare a informatiei, iar conceptele dintextul respectiv sunt efectiv informatia continuta n text.

Ca un al doilea exemplu, limba vorbita este o alta schema de reprezentarea informatiei, canalul pentru care este construita fiind de tip continuu.

Schema de codificare a informatiei se presupune ca este stabilita nprealabil si este cunoscuta atat emitatorului cat si receptorului. De asemenea,n constructia schemei de reprezentare a informatiei se tine cont de carac-teristicile canalului si de caracteristici generale ale informatiilor ce trebuie sase poata transmite, nsa la elaborarea ei nu se cunosc informatiile ce trebui-esc efectiv transmise. De exemplu, la elaborarea unei scheme de codificare aliterelor dintr-un text utilizand un canal ce poate transmite doar simbolurile0 si 1 se poate tine cont de frecventa obisnuita a literelor ntr-un text, dar nusi de textul efectiv de transmis.

Restul capitolului trateaza scheme de reprezentare a informatiei pen-tru canale discrete. Vom studia n continuare:

proprietati generale ale codurilor, problema minimizarii numarului de simboluri necesare a fi transmise prin

canal, precum si masurarea cantitatii de informatie,

problema codificarii n cazul n care canalul altereaza sirul de simboluripe care l transmite (canal cu perturbatii).

2.1. Problema codificarii informatiei pentru un canaldiscretIn cazul unui canal discret, canalul poate transmite un sir de sim-

boluri dintr-o multime S, numita multimea simbolurilor de cod sau alfabetulcanalului. Elementele lui S se numesc simboluri de cod sau, scurt, simboluri.Multimea S este finita si are cel putin doua elemente. De regula S = {0, 1}.

Pentru sirurile de simboluri de cod vom utiliza urmatoarele notatii:

S reprezinta multimea sirurilor finite de elemente din S.

u

v reprezinta concatenarea sirurilor u si v.


25/405

c 2008, Radu-Lucian LupsaCapitolul 2. Notiuni de teoria informatiei 27

|u| reprezinta lungimea sirului u; avem |u v| = |u| + |v|, u, v S.

este sirul vid; avem

|

|= 0 si u

=

u = u,

u

S.

Informatia transmisa de catre sursa consta dintr-un sir de mesaje.Fiecare mesaj este un element dintr-o multime M de mesaje posibile. Mesajeleprovin din universul utilizatorului sistemului; ele pot fi propozitii, litere, nu-mere, etc.

Multimea de mesaje M este nevida si cel mult numarabila. De celemai multe ori M este finita.

Definitia 2.1 Numim functie de codificare sau cod orice functie injectiva

c : M S

, unde M este multimea de mesaje, cel mult numarabila, iarS este multimea simbolurilor de cod, finita si avand cel putin doua elemente.

Fiecare mesaj m M va fi codificat prin sirul c(m) S.

Definitia 2.2 Numim cuvant de cod orice sir de simboluri de cod w S cu proprietatea ca exista un mesaj m M astfel ncat w = c(m).

Numim multimea cuvintelor de cod multimea W = c(M).

Un sir de mesaje (m1, . . . , mk) M (unde M desemneaza multimeasirurilor finite de mesaje din M) va fi codificat prin sirul format prin con-catenarea codificarilor mesajelor:

c(m1) c(m2) . . . c(mk).

De remarcat ca n urma concatenarii se pierd delimitarile dintre codificarilemesajelor individuale. Ca urmare, pentru ca receptorul sa poata decodificafara ambiguitati orice transmisie a emitatorului este necesara o proprietatesuplimentara a codului, aceea de-a fi unic decodabil:

Definitia 2.3 Un cod c : M S se numeste: cod unic decodabil, daca functia c : M S data prin

c(m1, m2, . . . , mk) = c(m1) c(m2) c(mk) (2.1)

este injectiva.

cod cu proprietatea de prefix sau cod prefix, daca nu exista m1, m2 M,cu m1 = m2, astfel ncat c(m1) sa fie prefix pentru c(m2) si n plusc(m)

= ,

m

M.


26/405

c 2008, Radu-Lucian Lupsa28 2.1. Problema codificarii informatiei pentru un canal discret

cod de lungime fixa, daca exista o constanta l IN \ {0} astfel ncat|c(m)| = l, m M; valoarea l se numeste lungimea codului;

Propozitia 2.4 Au loc urmatoarele proprietati:

1. Orice cod de lungime fixa este cod prefix.

2. Orice cod prefix este unic decodabil.

Demonstratia este imediata.

Exemplul 2.1: Consideram multimea mesajelor M = {a,b,c,d} si multimeasimbolurilor de cod S = {0, 1}. Urmatorul cod are proprietatea de prefix.

a

0

b 101c 11d 100

Exemplul 2.2: Urmatorul cod, obtinut prin oglindirea cuvintelor codului dinexemplul anterior, este unic decodabil dar nu are proprietatea de prefix:

a 0b 101c 11d 001

Codul nu este prefix ntrucat cuvantul de cod 0 care este codificarea mesajuluia este prefix al cuvantului de cod 001 care este codificarea mesajului d.

De notat ca un cod obtinut prin oglindirea cuvintelor unui cod prefixse numeste cod sufix si ntotdeauna este unic decodabil.

Exemplul 2.3: Codul de mai jos nu este unic decodabil:

a 0b 1c 01

Codul nu este unic decodabil ntrucat sirul de simboluri de cod 01 poate ficodifcarea mesajului c sau a sirului de mesaje ab.


27/405


2.2. Coduri cu proprietatea de prefixDesi simple, codurile de lungime fixa nu sunt adecvate n urmatoarele

doua cazuri:

pentru obtinerea unui cod eficient, adica avand cuvinte cat mai scurte,daca probabilitatile diverselor mesaje din M sunt diferite (M este mul-timea mesajelor sursei);

daca M nu este finita (de exemplu, M este multimea numerelor naturale).In aceste situatii, trebuie sa ne extindem la clase mai largi decat cea

a codurilor de lungime fixa. Asa cum vom vedea n continuarea paragrafuluide fata, clasa codurilor prefix este suficienta n situatiile enumerate mai sus si,

n acelasi timp, permite decodificarea destul de simpla a transmisiei.

2.2.1. Reprezentarea arborescenta a codurilor prefixUnui cod prefix c : M S i se poate atasa un arbore n care:

pentru fiecare nod intern, muchiile descendente sunt cel mult n numarde |S| si sunt etichetate cu simboluri distincte din S;

fiecare frunza este etichetata cu cate un mesaj distinct din M; cuvantul de cod al unui mesaj este format din simbolurile de cod ale

muchiilor de pe lantul ce uneste radacina cu frunza atasata mesajului.

Constructia arborelui se face conform algoritmului 2.1 (Genereaza ar-bore).

Exemplul 2.4: Pentru codul din exemplul 2.1 arborele este reprezentat nfigura 2.2.

0 1

a

0

0 1

1

d b

c

Figura 2.2: Arborele atasat unui cod prefix

Exemplul 2.5: Fie codul prefix pentru multimea mesajelor

M ={

a, b, c, d, e, f, g, h}


28/405

c 2008, Radu-Lucian Lupsa30 2.2. Coduri cu proprietatea de prefix

Algoritmul Genereaza arboreintrarea: M multime finita nevida

c : M S cod prefixiesirea: T arborele asociat codului calgoritmul:

creeaza T format doar din radacinar:=radacina lui Tpentru m M executa

(s1, . . . , sl):=c(m)x:=rpentru i:=1, l executa

daca nu exista muchie descendenta de la x etichetata cu si atuncidaca x are asociat un mesaj atunci

eroare: c nu este cod este prefixsfarsit daca

creaza y descendent al lui x si eticheteaza (x, y) cu sisfarsit daca

x:=descendentul lui x pe muchia etichetata sisfarsit pentru

daca x nu e frunza atuncieroare: c nu este cod este prefix

sfarsit daca

asociaza m nodului xsfarsit pentru

sfarsit algoritm

Algoritmul 2.1: Generarea arborelui asociat unui cod prefix


29/405


si multimea simbolurilor de cod S = {0, 1, 2}:

a 0b 10c 11d 12e 200f 201g 21h 22

Arborele atasat este reprezentat n figura 2.3.

0 1 2

0 1 2 0 1 2

0 1

a

b c d

e f

g h

Figura 2.3: Arborele atasat codului prefix din exemplul 2.5.

2.2.2. Decodificarea n cazul codurilor prefixDaca avem un sir de mesaje codificat printr-un cod prefix, decodifi-

carea se poate face prin algoritmul 2.2. Acesta ruleaza n timp proportionalcu numarul de simboluri de cod din reprezentarea datelor de decodificat.

De remarcat ca fiecare mesaj este decodificat de ndata ce ultimulsimbol din reprezentarea sa a fost citit si prelucrat. Acest lucru este posibilnumai pentru codurile prefix; din acest motiv, codurile prefix se mai numescsi coduri instantanee.

Exemplul 2.6: Fie codul prefix din exemplul 2.5 (vezi fig. 2.3) si fie sirul dedecodificat:

s = 0112000


30/405


Algoritmul Decodeazaintrarea: T arborele unui cod prefix c : M S

s = (s1, s2, . . . , sl) S un sir finit de simboluri de codiesirea: m = (m1, m2, . . . , mk)

M

sirul mesajelor a caror codificare este

s1, . . . , slalgoritmul:

m:=x:=radacina lui Tpentru i:=1, l executa

daca nu exista muchie descendenta de la x etichetata cu si atuncieroare: s nu este concatenare de cuvinte de cod

sfarsit daca

x:=descendentul ui x pe muchia etichetata cu si

daca x este frunza atunciadauga la m mesajul asociat lui xx:=radacina lui T

sfarsit daca

sfarsit pentru

daca x nu este radacina lui T atuncieroare: s nu este concatenare de cuvinte de cod

sfarsit daca

sfarsit algoritm

Algoritmul 2.2: Decodificarea unei reprezentari printr-un cod prefix


31/405


Decodificarea se face astfel: La nceput x este radacina arborelui. Luam dinsirul s primul element; acesta are valoarea 0. Coboram n arbore de-a lungul

muchiei etichetate cu 0 si ajungem la frunza etichetata ,,a. Deoarece amajuns la o frunza, punem mesajul din eticheta frunzai adica ,,a n sirulde mesaje decodificat si revenim la radacina. Urmeaza simbolul de cod 1;coboram de-a lungul muchiei 1 si ajungem n nodul parinte ale nodurilor ,,b,,,c si ,,d. Urmeaza simbolul 1; coboram de-a lungul muchiei 1 si ajungem lafrunza ,,c; adaugam ,,c la sirul de mesaje si revenim la radacina. Continuandn acelasi fel, vom obtine n continuare mesajele ,,e si ,,a. Sirul de mesajetransmis este deci ,,acea.

2.2.3. Lungimile cuvintelor unui cod prefixIn cele ce urmeaza, vom examina o conditie necesara si suficientapentru existenta unui cod prefix cu lungimi date ale cuvintelor, iar apoi vomarata ca aceasta conditie este de asemenea necesara pentru existenta unui codunic decodabil.

Teorema 2.5 Fiind data o multime de mesaje M cel mult numarabila si omultime de simboluri S finita avand cel putin 2 elemente distincte, pentruorice cod c : M S cu proprietatea de prefix, lungimile cuvintelor de codli =

|c(i)

|, i

M, satisfac urmatoarea inegalitate (inegalitatea lui Kraft):

iM

|S|li 1 (2.2)

si, reciproc, daca numerele naturale (li)iM satisfac inegalitatea (2.2) atunciexista un cod prefixc : M S avand lungimile cuvintelor|c(i)| = li, i M.

Demonstratie. Vom nota n continuare d = |S| si K =mM dlm .Vom demonstra ntai prima implicatie, pentru cazul n care multimea

mesajelor M este finita. Demonstratia va fi construita prin inductie dupamaximul k al lungimilor cuvintelor de cod (k = maxmM lm).

Pentru k = 1, nseamna ca toate cuvintele de cod sunt de lungime 1 sin consecinta sunt n numar de cel mult d. Ca urmare

K =mM

d1 = |M| d1 d d1 = 1.

Presupunand inegalitatea lui Kraft adevarata pentru coduri de lungimemaxima k = k0, pentru un k0 IN arbitrar, sa demonstram ca are loc sipentru coduri de lungime maxima k = k0 + 1. Pentru aceasta, sa construimmultimile de mesaje

Mx =

{m

M : primul simbol din c(m) este x

}, x

S.


32/405


Se observa imediat ca (Mx)xS sunt disjuncte doua cate doua si ca reuniunealor este M. Ca urmare

K =xS

mMx

dlm .

Pentru fiecare x M, restrictia lui c la Mx, c|Mx , este de asemenea un codprefix. Distingem n continuare trei cazuri:

Daca Mx are cel putin 2 elemente, rezulta ca toate cuvintele de cod aleelementelor din Mx au lungime mai mare sau egala cu 2, deoarece ncaz contrar singurul cuvant de cod de lungime 1, anume x, ar fi prefixpentru toate celelalte. Eliminand din toate cuvintele de cod primulsimbol obtinem un nou cod prefix pentru Mx. Acest cod prefix are

toate cuvintele de cod lungime cel mult k0 si ca urmare, conformipotezei de inductie, satisface inegalitatea lui Kraft, adica

mMx

d(lm1) 1,

de unde mMx

dlm 1d

.

Daca Mx are un singur element, cuvantul de cod asociat acestui ele-

ment are lungime cel putin 1 si ca urmare din noumMx

dlm 1d

.

Daca Mx = , avem

mMxdlm = 0 1

d.

Insumand acum pentru toate submultimile Mx, obtinem:

K =xS mMx d(lm) xS

1

d= 1.

In cazul unei multimi M numarabile, construim

Ml = {m M : |c(m)| l} , l IN

si notam

Kl =

mMk

d(lm).

Deoarece, pentru fiecare l IN, c|Ml este un cod prefix, rezulta Kl 1,

l

IN. Dar (Kl)lIN este un subsir al sirului sumelor partiale ale unei


33/405


Algoritmul Construieste codintrarea: (lm)mM IN satisfacand (2.2)iesirea: c : M S

cod prefix cu |c(m)| = lm, m Malgoritmul:

E:={}pentru l=1,maxmM lm executa

E:=pentru w E executa

pentru x S executaE:=E {w x}

sfarsit pentru

sfarsit pentru

E:=E

pentru m M : lm = l executac(m):= o valoare arbitrara din EE:=E\ {c(m)}

sfarsit pentru

sfarsit pentru

sfarsit algoritm

Algoritmul 2.3: Constructia unui cod prefix cu lungimi date ale cuvintelor de cod


34/405


permutari a seriei cu termeni pozitivi

mM dlm . De aici rezulta ca seria

este convergenta si suma ei K este la randul ei mai mica sau egala cu 1.

Sa demonstram acum reciproca, si anume ca inegalitatea lui Kraftimplica existenta unui cod prefix. Constructia codului va fi realizata dealgoritmul 2.3. Demonstram n continuare corectitudinea acestui algoritm.

Vom nota n cele ce urmeaza cu Ek valoarea lui E n cadrul iteratieil = k imediat dupa executia instructiunii E:=E.

Mai ntai, pentru a demonstra ca lungimile cuvintelor de cod suntntr-adevar cele dorite, sa aratam ca toate cuvintele din Ek au lungime k.Intr-adevar, la prima iteratie cuvintele din E1 se obtin prin concatenareacate unui simbol din S la sirul vid. Apoi, cuvintele din Ek+1 se obtin dincuvintele ramase din Ek dupa atribuirea unora ca si cuvinte de cod prinadaugarea la final a cate unui simbol din S. Ca urmare, cuvintele din Ek+1

sunt de lungime k.Sa aratam acum ca se obtine un cod prefix. Daca un cuvant din Ek

este atribuit unui mesaj, cuvantul de cod respectiv este eliminat din Ek.Cuvintele ce vor fi atribuite n continuare pot avea prefixe de lungime kdoar dintre cuvintele ramase n Ek.

Mai trebuie aratat ca exista ntotdeauna n E o valoare de atribuit luic(m). Pentru aceasta, vom arata ca

mMlmk

dklm |Ek| (2.3)

La prima iteratie, |Ek| = d simMlmk

dklm = d K d = |E|

Presupunand ca (2.3) are loc la iteratia cu l = k, la iteratia urmatoare, ncare l = k + 1, avem

mM

lmk+1

dk+1lm = d

mMlmk+1dklm =

= d

mMlmk

dklm mMlm=k

dklm

=

d(|Ek| | {m M : lm = k}|) == |Ek+1|

unde ultima egalitate rezulta din modul de constructie a lui Ek+1 din Ekprin eliminarea unui numar de elemente egal cu numarul de cuvinte de


35/405


cod de lungime k urmata de nlocuirea fiecarui cuvant ramas cu d cuvinteobtinute prin adaugarea fiecarei litere posibile din S.

Observam acum ca suma din inegalitatea (2.3) are un numar de termenide valoare 1 egal cu numarul de cuvinte de lungime k de obtinut si, caurmare, exista n Ek suficiente cuvinte.

Exemplul 2.7: Dorim construirea unui cod prefix pentru multimea M ={a, b, c, d, e} si multimea de simboluri de cod S = {0, 1} cu urmatoarelelungimi ale cuvintelor de cod: la = 3, lb = 1, lc = 3, ld = 3, le = 3.

Rezolvare: mai ntai verificam daca este satisfacuta inegalitatea luiKraft:

mM|S|lm = 23 + 21 + 23 + 23 + 23 = 1 1,

inegalitatea este satisfacuta si prin urmare exista un cod prefix.

Constructia propriu-zisa este aratata n figura 2.4. Cerculetele de-semneaza nodurile corespunzatoare elementelor din multimea E.

Radacinaarborelui

(a) Initializarea:E= {}

0 1

b

(b) Iteratial = 1: E ={1} si a fostplasat ,,b

0 1

0 1b

(c) Iteratia l = 2:E= {10, 11}

a

b

0 1

0 1

0 1 0 1

dc e

(d) Ultima iteratie, l = 3: E= si codul este complet generat

Figura 2.4: Constructia unui cod prefix cu lungimi fixate ale cuvintelor de cod(exemplul 2.7)


36/405


Vom arata n continuare ca inegalitatea lui Kraft este o condit ie nece-sara pentru existenta codurilor unic decodabile, nu doar a celor prefix. Avem:

Teorema 2.6 (McMillan) Pentru orice cod unic decodabil c : M |S| areloc inegalitatea:

nmM

dlm 1 (2.4)

unde lm = |c(m)|, m M si d = |S|.Demonstratie. Consideram mai ntai cazul cand M este finita. Sa notamcu E =

n

mM dlm . Sa luam un k IN arbitrar si sa calculam:

Ek =

(m1,...,mk)Mk

dlm1 . . . dlmk

=

(m1,...,mk)Mk

d(lm1+...+lmk )(2.5)

Regrupam acum termenii din (2.5) dupa valorile sumei lm1 + . . . + lmk .Pentru aceasta, vom nota cu N(k, l) numarul de termeni din dezvoltarea(2.5) pentru care lm1 + . . . + lmk = l. Cu alte cuvinte,

N(k, l) = (m1, . . . , mk) Mk : lm1 + . . . + lmk = l .

Mai observam cak lm1 + . . . + lmk lmax k

unde lmax este maximul lungimii cuvintelor de cod (lmax = maxmM lm).Obtinem:

Ek =

lmax kl=k

N(k, l) dl. (2.6)

Sa observam acum ca N(k, l) este numarul de siruri de k mesaje pentrucare lungimea codificarii sirului este l. Deoarece codul este unic decodabil,aceste codificari sunt distincte si ca urmare N(k, l) este cel mult egal cu

numarul de siruri distincte de l simboluri de cod, adica

N(k, l) dl.Inlocuind n (2.6), obtinem:

Ek lmax kl=k

dl dl = lmax k k + 1 lmax k, (2.7)

adicaEk

lmax

k. (2.8)


37/405


Aceasta inegalitate are loc pentru orice k IN. Daca am avea E > 1,atunci pentru un k suficient de mare am avea Ek > lmax k; prin urmareE 1.Daca M este numarabila, construim multimile

Mk = {m M : |c(m) k} , k IN

si notam Ek =

mMkdlm . Pentru fiecare k IN, Mk este finita si c|Mk

este un cod unic decodabil. Ca urmare, Ek 1 pentru fiecare k IN.Observam acum ca E = limk Ek 1.

Corolarul 2.7 Pentru orice cod unic decodabil, exista un cod prefix cu ace-leasi lungimi ale cuvintelor de cod.

2.3. Coduri optime

Deoarece stocarea sau transmiterea fiecarui simbol de cod implica un

cost (timp necesar transmisiei, spatiu fizic pe suportul de informatie, etc), estenatural sa cautam un cod pentru care numarul de simboluri de cod necesaretransmiterii sirului de mesaje al sursei este cat mai mic. Se impun nsa catevaprecizari cu privire la aceasta minimizare.

Mai ntai, codul trebuie elaborat necunoscand informatia particularape care urmeaza s-o trimita sursa. Prin urmare, nu se poate cere minimizarealungimii reprezentarii informatiei transmise efectiv de sursa. Se va minimizadeci numarul mediu de biti necesari reprezentarii unui mesaj al sursei.

In al doilea rand, acest numar mediu de biti se considera n sensprobabilistic, de valoare medie a unei variabile aleatoare. Anume, fiecare mesajal sursei poate fi considerat o variabila aleatoare cu valori din multimea Mde mesaje ale sursei. Lungimea reprezentarii mesajului este de asemenea ovariabila aleatoare, a carei valoare medie este ceea ce dorim sa minimizam.

Probabilitatile diferitelor mesaje ale sursei se pot estima pe diversecai fie analizand teoretic fenomenele pe baza carora functioneaza sursa, fieanalizand statistic siruri de mesa je trimise de sursa. Ca exemplu, daca mesajelesursei sunt litere ce alcatuiesc un text ntr-o anumita limba, se poate deter-mina statistic frecventa fiecarei litere, precum si frecventele unor succesiunide litere.


38/405

c 2008, Radu-Lucian Lupsa40 2.3. Coduri optime

2.3.1. Cantitatea de informatieCantitatea de informatie purtata de un mesaj este o masura a incer-

titudinii pe care destinatarul o avea imediat nainte de primirea mesajului sicare este eliminata n urma primirii mesajului.

Cantitatea de informatie purtata de un mesaj trebuie deci sa fie micadaca pentru destinatar evenimentul anuntat de mesaj era aproape sigur simare daca este un eveniment total neasteptat. Este de dorit, de asemenea,ca masura informatiei sa fie aditiva, n sensul ca privind ca un singur mesajo succesiune de doua mesaje, cantitatea de informatie purtata de mesajulcompus sa fie suma cantitatilor de informatie purtate de cele doua mesajeseparat.

Asa cum vom vedea n continuare, cantitatea de informatie purtatade un mesaj va fixa o limita inferioara teoretica a numarului de simboluri decod necesare codificarii mesajului.

De notat ca cantitatea de informatie nu are nici o legatura cu utili-tatea informatiei.

Definitia 2.8 Fie o sursa care emite un sir de mesaje m1, m2, . . . , mt M.Cantitatea de informatie adusa de mesajul mt este

info(mt) = log2 Pr(mt|m1, m2, . . . , mt1).Altfel spus, cantitatea de informatie adusa de un mesaj mt n contex-

tul (adica urmand dupa) m1, m2, . . . ,mt1 este minus logaritmul probabilitatiica al t-lea mesaj sa fie mt, conditionata de faptul ca mesajele precedente aufost m1, m2, . . . ,mt1.

In cazul unei surse ergotice, adica pentru care probabilitatea ca unmesaj sa aiba o anumita valoare este independenta de mesajele anterioare side pozitia (numarul de ordine) mesajului n sirul de mesaje, putem, pentrufiecare m M, sa notam cu pm probabilitatea ca un anumit mesaj din sirulde mesaje sa aiba valoarea m. Atunci cantitatea de informatie adusa de un

mesaj m este info(m) = log2pm.Unitatea de masura pentru cantitatea de informatie este bitul.A nu se confunda bitul cu sensul de unitate de masura pentru canti-

tatea de informatie cu bitul cu sensul de cifra binara. Exista o legatura ntreaceste notiuni, si anume, asa cum vom vedea, pentru a transmite un bit deinformatie avem nevoie cel putin de un bit (cifra binara).

Exemplul 2.8: Daca emitatorul anunta receptorului rezultatul aruncarii uneimonede, mesajul a cazut cu fata n sus poarta o cantitate de informatie egalacu

log2

1

2

=

(

1) = 1bit.


39/405


Exemplul 2.9: In textul acestei lucrari, 10,7% dintre litere sunt ,,a, si doar1,1% sunt ,,b. Cu aceste cunostinte, receptorul se va astepta de la fiecare

litera sa fie ,,a cu probabilitate de 10,7% si ,,b cu probabilitate de 1,1%. Inaceste conditii, fiecare litera ,,a poarta log2 0,107 3,224 biti de informatie,si fiecare litera ,,b poarta log2 0,011 6,5 biti.

Exemplul 2.10: Presupunem ca emitatorul informeaza receptorul asuprarezultatului aruncarii unui zar. Daca emitatorul trimite mesajul numarul estentre 1 si 4 cantitatea de informatie este log2 46 0,58 biti. Daca emitatorulanunta acum ca numarul este 3, probabilitatea acestui caz, cu informatiiledisponibile imediat nainte, este 14 , de unde cantitatea de informatie purtata

de mesajul numarul este 3 este log21

4 = 2 biti. Sa observam ca, dacaemitatorul ar fi spus de la nceput numarul este 3, cantitatea de informatietransmisa ar fi fost log2 16 2,58 biti.

Definitia 2.9 Fie o sursa de informatie ce emite mesaje dintr-o multime M,fiecare mesaj m M avand o probabilitate pm de-a fi emis. Se numesteentropia sursei de informatie cantitatea

H = mM

pm logpm (2.9)

Cu alte cuvinte, entropia este cantitatea medie de informatie permesaj.

2.3.2. Lungimea medie a cuvintelor de cod

Definitia 2.10 Fie o sursa ce emite mesaje dintr-o multimeM. Pentru fiecarem M, fie pm probabilitatea mesajului m si fie c : M S un cod unicdecodabil. Se numeste lungimea medie a cuvintelor codului c valoarea

l =

mM

pm |c(m)|.

Definitia 2.11 Un cod unic decodabil c : M S se numeste cod optimdaca lungimea medie a cuvintelor sale este mai mica sau egala decat lungimeamedie a cuvintelor oricarui cod unic decodabil c : M S.

Exista urmatoarea limita inferioara pentru lungimea medie a cuvin-telor de cod:


40/405


Teorema 2.12 Fie o sursa ce emite mesaje dintr-o multimeM, fieH entropiasursei si fie c : M S un cod unic decodabil. Atunci lungimea medie l acuvintelor codului c satisface

l Hlog2 |S|

. (2.10)

In particular, daca |S| = 2, atunci rezulta l H. Cu alte cuvinteavem nevoie cel putin de un simbol binar (un bit) pentru a transmite un bitde informatie.

Definitia 2.13 Se numeste eficienta unui cod raportul = Hl log2 |S|

, unde H

este entropia sursei, l este lungimea medie a cuvintelor de cod, iar S estemultimea simbolurilor de cod.Se numeste redundanta relativa valoarea 1 .Eficienta si redundanta relativa sunt numere cuprinse ntre 0 si 1.Valoarea minima, data teorema 2.12, pentru lungimea medie a cu-

vintelor de cod poate fi atinsa efectiv, adica se poate obtine eficienta = 1,doar n anumite cazuri. Motivul pentru care ea nu poate fi ntotdeauna atinsaeste data de natura discreta a simbolurilor de cod. Ideal, lungimea cuvintelorde cod ar trebui sa fie lm = log|S|pm. Pentru aceste valori inegalitatea luiKraft este satisfacuta:

mM

|S|lm =

mM

|S|( log|S| pm) =

mM

pm = 1 1,

prin urmare ar exista un cod unic decodabil si limita din teorema 2.12 ar fiatinsa:

l =

mM

pm log|S|pm

=

mM

pm log2pmlog2 |S|

= 1log2 |S|

mM

pm log2pm = Hlog2 |S| .Acest lucru se poate realiza nsa numai daca lm = log|S|pm sunt toatentregi.

In cazul general putem doar sa alegem ca lungimi ale cuvintelor decod valorile mai mari, lm = log|S|pm. Pentru aceste valori avem

log|S|pm lm < log|S|pm + 1de unde rezulta:


41/405


Teorema 2.14 Fie o sursa ergotica ce emite mesaje dintr-o multime M, fieH entropia sursei si fie S o multime de simboluri de cod. Atunci exista un

cod c : M S

unic decodabil a carui lungime medie l a cuvintelor de codsatisface

H

log2 |S| l < H

log2 |S|+ 1. (2.11)

Rezultatul teoremei precedente poate fi mbunatatit daca n loc saconsideram mesajele sursei ca fiind mesajele din M consideram succesiunide mesaje din M, construim un cod pentru acestea din urma si determinamraportul dintre lungimea medie a cuvantului de cod si numarul de mesaje dinM codificate prin acesta. In detaliu, constructia este urmatoarea:

Fixam k IN. Consideram o a doua sursa, ale carei mesaje vor fi suc-cesiuni de k mesaje ale sursei originale. Multimea de mesaje ale noii surse esteprin urmare Mk. Probabilitatile mesajelor sunt p(m1,...,mk) = pm1 . . . pmk .Vom nota cu Hk entropia noii surse. Avem

Hk =

(m1,...,mk)Mk

p(m1,...,mk) log2p(m1,...,mk) =

=

(m1,...,mk)Mk

pm1 . . . pmk (log2pm1 + . . . + log2pmk) =

= k

i=1

(m1,...,mk)Mk

pm1 . . . pmk log2pmi =

=k

i=1

(m1,...,mi1,mi+1,...,mk)Mk1

pm1 . . . pmi1 pmi+1 . . . pmk

miM

pmi log2pmi

=

=k

i=1

1 H =

=k H

Conform teoremei 2.14, exista un cod c : Mk S pentru carelungimea medie a cuvintelor de cod, l(k), satisface

Hk

log2 |S| l(k) 1 executa

alege e1, . . . , ed E cu pei pe , i {1, . . . , d} , e E \{e1, . . . , ed}

creaza t unicpentru i

{1, . . . , d

}executa

pune ei ca fiu al lui ts(t,ei):=si

sfarsit pentru

pt:=d

i=1peiE:=(E\ {e1, . . . , ed}) {t}d:=d

sfarsit cat timp

c:=codul prefix asociat unicului arbore din Esfarsit algoritm

Algoritmul 2.4: Algoritmul lui Huffman


44/405


cod optim. Sa alegem ,,b cu ,,c. Calculam si probabilitatea arboreluirezultat: 0,15 + 0,15 = 0,3. (fig. 2.5(b)).

In continuare unim din nou arborii de probabilitati minime; acum acestiasunt ,,d si ,,e (fig. 2.5(c)).

Avem acum doua posibilitati: arborele ce contine pe ,,b si pe ,,c poatefi unit fie cu arborele format din ,,a, fie cu arborele format din ,,d si,,e. Alegem a doua varianta.

In final unim cei doi arbori ramasi.Avem acum codurile mesajelor: c(a) = 0, c(b) = 100, c(c) = 101, c(d) = 110,c(e) = 111. Lungimea medie a cuvintelor de cod este

l = 0,35 1 + 0,15 3 + 0,15 3 + 0,15 3 + 0,2 3 = 2,3

Pentru comparatie, entropia este

H = 0,35 log2 0,35 + 0,15log2 0,15 + 0,15log2 0,15++ 0,15 log2 0,15 + 0,2log2 0,2

2,226121

d

0.35 0.15 0.15 0.15

ba

0.20

ec

(a) Pasul 1

b c

0.35

a

0.30

d

0.15 0.20

e

(b) Pasul 2

0.35

a

0.30

cb

0.35

d e

(c) Pasul 3

0.35

a

cb d e

0.65

(d) Pasul 4

a

cb d e

0 1

0 1 10

10

(e) Arborele final

Figura 2.5: Functionarea algoritmului Huffman, exemplul 2.11


45/405


Daca la pasul 4 s-ar fi ales cealalta posibilitate, ar fi rezultat multimeade arbori din figura 2.6(a) si n final arborele asociat codului prefix din figura 2.6(b).

Sa observam ca se obtine exact aceeasi lungime medie a cuvintelor de cod:

l = 0,35 2 + 0,15 3 + 0,15 3 + 0,15 2 + 0,2 2 = 2,3

b c

0.65

a

0.35

ed

(a) Pasul 4

b c

a

ed

0 1

0 1 1

0 1

0

(b) Arborele final

Figura 2.6: Varianta alternativa pentru pasii 4 si 5 (exemplul 2.11)

Exemplul 2.12: Fie o sursa avand multimea mesajelor posibile

M = {a, b, c, d, e, f}cu probabilitatile corepsunzatoare pa = 0,4, pb = 0,15, pc = 0,15, pd = 0,1,

pe = 0,1, pf = 0,1 si fie alfabetul canalului S = {0, 1, 2}.Constructia codului prin algoritmul lui Huffman este prezentata n

figura 2.7. Lungimea medie a cuvintelor de cod este l = 1,6, entropia esteH 2,346439 si avem

H

log2 |S| 2,346439

1,5849625 1,4804382 1,6 = l

Teorema 2.15 Codul obtinut prin algoritmul Huffman este optim.

Pentru demonstratie avem nevoie de cateva leme ce descriu pro-prietati ale unui cod optim. In cele ce urmeaza vom nota cu L(c) lungimeamedie a cuvintelor unui cod c.

Lema 2.16 Fie M multimea mesajelor sursei, fie pm, m M, probabilitatilemesajelor sursei, fie S alfabetul canalului si fie c : M S un cod optim.Pentru orice mesaje m1, m2

M, daca pm1 < pm2 atunci

|c(m1)

| |c(m2)

|.

(4)Manual Retele Calculatoare (de Stiut)

Documents

Transcript of (4)Manual Retele Calculatoare (de Stiut)