• Nu S-Au Găsit Rezultate

Radu-Lucian Lup¸sa

N/A
N/A
Protected

Academic year: 2022

Share "Radu-Lucian Lup¸sa"

Copied!
410
0
0
Arată mai multe ( pagini)

Text complet

(1)

Principii

Radu-Lucian Lup¸sa

(2)

Casa C˘art¸ii de S¸tiint¸˘a, ˆın 2008, ISBN: 978-973-133-377-9.

Drepturile de autor apart¸in subsemnatului, Radu-Lucian Lup¸sa.

Subsemnatul, Radu-Lucian Lup¸sa, acord oricui dore¸ste dreptul de a copia cont¸inutul acestei c˘art¸i, integral sau part¸ial, cu condit¸ia atribuirii corecte autorului ¸si a p˘astr˘arii acestei notit¸e.

Cartea poate fi desc˘arcat˘a gratuit de la adresa http://www.cs.ubbcluj.ro/~rlupsa/works/retele.pdf

(3)
(4)
(5)

Cuprins

Principii

Cuprins 5

Prefat¸˘a 13

1 Introducere 15

1.1 Serviciile oferite de ret¸ea . . . . 15

1.2 Principalele elemente ale unei ret¸ele de calculatoare . . . . 20

1.3 Premise generale ˆın elaborarea ¸si implementarea protocoalelor ˆın ret¸ele . . . . 22

2 Not¸iuni de teoria informat¸iei 25 2.1 Problema codific˘arii informat¸iei pentru un canal discret . . . . 26

2.2 Coduri cu proprietatea de prefix . . . . 29

2.2.1 Reprezentarea arborescent˘a a codurilor prefix . . . . 29

2.2.2 Decodificarea ˆın cazul codurilor prefix . . . . 31

2.2.3 Lungimile cuvintelor unui cod prefix . . . . 33

2.3 Coduri optime . . . . 39

2.3.1 Cantitatea de informat¸ie . . . . 40

2.3.2 Lungimea medie a cuvintelor de cod . . . . 41

2.3.3 Generarea codului optim prin algoritmul lui Huffman . . . . 44

2.3.4 Compresia fi¸sierelor . . . . 50

2.4 Coduri detectoare ¸si corectoare de erori . . . . 51

2.4.1 Modelul erorilor . . . . 52

2.4.2 Principiile codurilor detectoare ¸si corectoare de erori . . . . 53

2.4.3 ateva coduri detectoare sau corectoare de erori . . . . 55

2.4.3.1 Bitul de paritate . . . . 55

2.4.3.2 Paritate pe linii ¸si coloane . . . . 55

2.4.3.3 Coduri polinomiale . . . . 56

2.4.4 Coduri detectoare ¸si corectoare de erori ˆın alte domenii . . . . . 57

(6)

6 Cuprins

3 Nivelul fizic 59

3.1 Problema transmisiei informat¸iei la nivelul fizic . . . . 59

3.2 Transmiterea semnalelor . . . . 60

3.2.1 Modific˘arile suferite de semnale . . . . 60

3.2.2 Analiza transmiterii semnalelor cu ajutorul transformatei Fourier . . . . 62

3.3 Codificarea informat¸iei prin semnale continue . . . . 65

3.3.1 Scheme de codificare . . . . 65

3.3.2 Modulat¸ia . . . . 68

3.3.3 Multiplexarea ˆın frecvent¸˘a . . . . 71

3.3.4 Capacitatea maxim˘a a unui canal de comunicat¸ie . . . . 71

3.4 Transmisia prin perechi de conductoare . . . . 72

3.4.1 Construct¸ia cablului . . . . 72

3.4.2 Propriet˘at¸i ale mediului . . . . 74

3.4.3 Leg˘atur˘a magistral˘a . . . . 75

3.4.4 Considerente practice . . . . 76

3.5 Transmisia prin unde radio . . . . 77

3.5.1 Propagarea undelor . . . . 78

3.5.1.1 Polarizarea . . . . 78

3.5.1.2 Absorbt¸ia ¸si reflexia . . . . 79

3.5.1.3 Difract¸ia . . . . 79

3.5.1.4 Interferent¸a undelor . . . . 80

3.5.1.5 Divergent¸a undelor . . . . 80

3.5.2 Antene . . . . 80

3.5.2.1 Directivitatea . . . . 81

3.5.2.2 Polarizarea . . . . 83

3.5.2.3 Tipuri de antene . . . . 83

3.5.3 Raza de act¸iune a unei leg˘aturi radio . . . . 83

3.5.3.1 Obstacolele . . . . 83

3.5.3.2 Linia orizontului . . . . 84

3.5.3.3 Utilizarea satelit¸ilor artificiali ai P˘amˆantului . . . . 84

3.5.3.4 Zgomotul . . . . 85

3.5.3.5 Sc˘aderea puterii cu distant¸a . . . . 86

3.5.3.6 Emisia direct¸ionat˘a ¸si polarizat˘a . . . . 86

3.5.4 Spectrul radio ¸si alocarea lui . . . . 86

3.5.5 Particularit˘at¸i ale sistemelor de comunicat¸ie prin radio . . . . . 88

3.5.5.1 Topologia leg˘aturii . . . . 88

3.5.5.2 Fiabilitatea . . . . 89

3.5.5.3 Securitatea . . . . 89

3.6 Transmisia optic˘a . . . . 89

3.6.1 Construct¸ia mediului . . . . 90

3.6.1.1 Conectarea fibrelor optice . . . . 91

3.6.2 Propagarea semnalului optic . . . . 91

3.6.2.1 Moduri de propagare . . . . 91

(7)

3.6.2.2 Caracteristici ale mediului . . . . 92

3.6.2.3 Multiplexarea ˆın lungimea de und˘a . . . . 92

3.6.3 Considerente practice . . . . 93

4 Nivelul leg˘aturii de date 95 4.1 Detectarea ¸si corectarea erorilor . . . . 96

4.2 Controlul accesului la mediu . . . . 97

4.2.1 Protocoale bazate pe asigurarea unui interval exclusiv de emisie . 98 4.2.2 Protocoale bazate pe coliziuni ¸si retransmitere . . . . 99

4.2.3 Protocoale mixte . . . 101

4.3 Retransmiterea pachetelor pierdute . . . 102

4.3.1 Principiul confirm˘arilor pozitive ¸si retransmiterilor . . . 103

4.3.2 Trimiterea ˆın avans a mai multor pachete . . . 108

4.3.3 Spat¸iul numerelor de confirmare . . . 109

4.4 Controlul fluxului . . . 114

4.4.1 Cereri de suspendare ¸si de continuare . . . 115

4.4.2 Mecanismul pas cu pas . . . 115

4.4.3 Mecanism combinat cu retransmiterea pachetelor pierdute . . . . 116

4.5 Multiplexarea ˆın timp . . . 117

5 Nivelul ret¸ea ¸si nivelul transport 119 5.1 Retransmiterea datelor de c˘atre nodurile intermediare . . . 120

5.1.1 Retransmiterea ˆın ret¸ele bazate pe datagrame . . . 122

5.1.2 Retransmiterea ˆın ret¸ele bazate pe conexiuni . . . 122

5.2 Algoritmi de dirijare . . . 125

5.2.1 Calculul drumurilor cu informat¸ii complete despre graful ret¸elei . 127 5.2.2 Calculul drumurilor optime prin schimb de informat¸ii de distant¸˘a . 128 5.2.3 Dirijarea ierarhic˘a . . . 136

5.2.4 Metode particulare de dirijare . . . 139

5.2.4.1 Inundarea . . . 139

5.2.4.2 ˆInv˘at¸area rutelor din adresele surs˘a ale pachetelor . . . 140

5.2.5 Metode de difuziune . . . 140

5.3 Funct¸ionarea la trafic ridicat . . . 141

5.3.1 Alegerea pachetelor de transmis . . . 142

5.3.2 Controlul congestiei . . . 143

5.3.3 Formarea (limitarea) traficului . . . 144

5.3.4 Rezervarea resurselor . . . 145

5.4 Nivelul transport . . . 146

5.5 Interconectarea ret¸elelor . . . 147

6 Metode ¸si protocoale criptografice 149 6.1 Asigurarea confident¸ialit˘at¸ii . . . 151

6.1.1 Introducere . . . 151

6.1.2 Refolosirea cheilor . . . 154

6.1.3 Problema spargerii unui cifru . . . 155

(8)

8 Cuprins

6.1.4 Algoritmi de criptare utilizat¸i ˆın practic˘a . . . 157

6.1.5 Criptografie asimetric˘a (cu cheie public˘a) . . . 163

6.1.5.1 Utilizarea criptografiei asimetrice . . . 164

6.2 Autentificarea mesajelor . . . 165

6.2.1 Funct¸ii de dispersie criptografice . . . 166

6.2.1.1 Utilizarea funct¸iilor de dispersie . . . 167

6.2.2 Funct¸ii de dispersie cu cheie . . . 168

6.2.3 Semn˘atura digital˘a . . . 169

6.2.4 Verificarea prospet¸imii mesajelor . . . 171

6.2.5 Combinarea cript˘arii, autentific˘arii ¸si verific˘arii prospet¸imii . . . 173

6.3 Stabilirea cheilor . . . 173

6.3.1 Stabilirea cheilor ˆın prezent¸a unui adversar pasiv . . . 176

6.3.1.1 Stabilirea cheilor prin criptografie asimetric˘a . . . 176

6.3.1.2 Stabilirea cheii prin metoda Diffie-Hellman . . . 177

6.3.1.3 Atacul man-in-the-middle . . . 178

6.3.2 Stabilirea cheilor ˆın prezent¸a unui adversar activ . . . 178

6.3.3 Stabilirea cheilor cu ajutorul unui tert¸ de ˆıncredere . . . 180

6.3.4 Certificarea cheilor publice . . . 182

6.3.5 Transportul prin utilizatori umani . . . 183

6.4 Numere aleatoare . . . 185

6.4.1 Generatoare fizice . . . 186

6.4.2 Generatoare de numere pseudoaleatoare . . . 186

6.4.3 Generatoare utilizate ˆın practic˘a . . . 188

6.5 Autentificarea utilizatorilor . . . 188

6.5.1 Stocarea parolelor . . . 188

6.5.2 Parole de unic˘a folosint¸˘a . . . 189

Protocoale Cuprins 195 7 Codific˘ari de interes practic 203 7.1 Probleme privind reprezentarea numerelor ˆıntregi . . . 203

7.1.1 Reprezent˘ari pe bit¸i . . . 203

7.1.1.1 Bitul . . . 204

7.1.1.2 S¸iruri de bit¸i . . . 204

7.1.1.3 Reprezentarea pe bit¸i a numerelor ˆıntregi . . . 205

7.1.2 Reprezent˘ari pe octet¸i . . . 206

7.1.2.1 Octet¸i . . . 206

7.1.2.2 S¸iruri de octet¸i . . . 208

7.1.2.3 Reprezentarea numerelor pe un num˘ar ˆıntreg de octet¸i . . . 208

7.1.2.4 Reprezentarea numerelor pe un ¸sir arbitar de bit¸i . . . 210

7.1.3 Probleme privind reprezentarea lungimii ¸sirurilor . . . 212

7.1.4 Alte metode de reprezentare a numerelor ˆıntregi . . . 214

(9)

7.2 Codificarea textelor . . . 215

7.2.1 Codificarea ASCII . . . 216

7.2.2 Codific˘arile ISO-8859 . . . 217

7.2.3 Codific˘arile Unicode . . . 218

7.2.3.1 Codificarea UTF-8 . . . 220

7.2.3.2 Codific˘arile UTF-16 . . . 220

7.2.3.3 Codific˘arile UTF-32 . . . 221

7.3 Reprezentarea datei ¸si orei . . . 221

7.3.1 asurarea timpului . . . 222

7.3.2 Obiectivele ˆın alegerea reprezent˘arii timpului ˆın calculator . . . . 224

7.3.3 Formate utilizate ˆın practic˘a . . . 225

7.3.3.1 Formatul utilizat de po¸sta electronic˘a . . . 225

7.3.3.2 ISO-8601 ¸si RFC-3339 . . . 226

7.3.3.3 Timpul POSIX . . . 227

7.3.3.4 TAI 64 . . . 227

7.4 Recodific˘ari . . . 228

7.4.1 Codificarea hexazecimal˘a . . . 228

7.4.2 Codificarea ˆın baza 64 . . . 229

7.4.3 Codific˘ari bazate pe secvent¸e de evitare . . . 229

8 Programarea ˆın ret¸ea — introducere 231 8.1 Interfat¸a de programaresocket BSD . . . 231

8.1.1 Comunicat¸ia prin conexiuni . . . 232

8.1.1.1 Deschiderea conexiunii de c˘atre client . . . 233

8.1.1.2 Deschiderea conexiunii de c˘atre server . . . 233

8.1.1.3 Comunicat¸ia propriu-zis˘a . . . 234

8.1.1.4 ˆInchiderea conexiunii . . . 234

8.1.2 Comunicat¸ia prin datagrame . . . 235

8.1.3 Principalele apeluri sistem . . . 237

8.1.3.1 Funct¸iasocket() . . . 237

8.1.3.2 Funct¸iaconnect() . . . 237

8.1.3.3 Funct¸iabind() . . . 238

8.1.3.4 Funct¸ialisten() . . . 239

8.1.3.5 Funct¸iaaccept() . . . 239

8.1.3.6 Formatul adreselor . . . 240

8.1.3.7 Interact¸iunea dintreconnect(),listen()¸siaccept() . . . 242

8.1.3.8 Funct¸iilegetsockname()¸si getpeername() . . . 242

8.1.3.9 Funct¸iilesend()¸si recv() . . . 243

8.1.3.10 Funct¸iileshutdown()¸siclose() . . . 245

8.1.3.11 Funct¸iilesendto()¸sirecvfrom() . . . 245

8.1.4 Exemple . . . 246

8.1.4.1 Comunicare prin conexiune . . . 246

8.1.4.2 Comunicare prin datagrame . . . 249

8.2 Formatarea datelor . . . 252

(10)

10 Cuprins

8.2.1 Formate binare . . . 252

8.2.1.1 Tipuri ˆıntregi . . . 252

8.2.1.2 S¸iruri de caractere ¸si tablouri . . . 254

8.2.1.3 Variabile compuse (struct-uri) . . . 255

8.2.1.4 Pointeri . . . 257

8.2.2 Formate text . . . 257

8.2.3 Probleme de robustet¸e ¸si securitate . . . 257

8.2.4 Probleme privind costul apelurilor sistem . . . 258

8.3 Probleme de concurent¸˘a ˆın comunicat¸ie . . . 260

9 Ret¸ele IEEE 802 263 9.1 Ret¸ele IEEE 802.3 (Ethernet) . . . 263

9.1.1 Leg˘aturi punct la punct prin perechi de conductoare . . . 266

9.1.2 Leg˘aturi prin fibre optice . . . 272

9.1.3 Leg˘aturi prin cablu magistral˘a . . . 274

9.1.4 Repetoarele ¸si comutatoarele . . . 277

9.1.5 Dirijarea efectuat˘a de comutatoare (switch-uri) . . . 279

9.1.6 Facilit˘at¸i avansate ale switch-urilor . . . 279

9.1.6.1 Switch-uri configurabile . . . 279

9.1.6.2 Filtrare pe baz˘a de adrese MAC . . . 280

9.1.6.3 Trunking . . . 280

9.1.6.4 Leg˘aturi redundante . . . 281

9.1.6.5 Ret¸ele virtuale (VLAN) . . . 281

9.1.7 Considerente privind proiectarea unei ret¸ele . . . 282

9.2 Ret¸ele IEEE 802.11 (Wireless) . . . 283

9.2.1 Arhitectura ret¸elei . . . 283

9.2.2 Accesul la mediu . . . 285

9.2.3 Generarea pachetelorbeacon . . . 286

9.2.4 Securitatea ret¸elelor 802.11 . . . 286

10 Internetul 291 10.1 Arhitectura ret¸elei . . . 291

10.2 Protocolul IP . . . 292

10.2.1 Structura pachetului IP . . . 293

10.2.2 Bazele dirij˘arii pachetelor IP . . . 294

10.2.2.1 Subret¸ele ¸si interfet¸e . . . 294

10.2.2.2 Prefixul de ret¸ea . . . 295

10.2.2.3 Tabela de dirijare . . . 296

10.2.3 Scrierea ca text a adreselor ¸si prefixelor . . . 298

10.2.3.1 Scrierea adreselor IP . . . 298

10.2.3.2 Scrierea prefixelor de ret¸ea . . . 300

10.2.4 Alocarea adreselor IP ¸si prefixelor de ret¸ea . . . 300

10.2.4.1 Alocarea pe utiliz˘ari . . . 301

10.2.4.2 Alocarea adreselor ¸si dirijarea ierarhic˘a . . . 301

(11)

10.2.5 Erori la dirijare ¸si protocolul ICMP . . . 302

10.2.5.1 Pachete nelivrabile . . . 303

10.2.5.2 Diagnosticarea funct¸ion˘arii rutelor . . . 305

10.2.5.3 Ciclarea pachetelor IP . . . 305

10.2.5.4 Congestia . . . 306

10.2.5.5 Redirect¸ionarea . . . 306

10.2.6 Alte chestiuni privind dirijarea pachetelor . . . 307

10.2.6.1 Dimensiunea maxim˘a a pachetelor ¸si fragmentarea . . . 307

10.2.6.2 Calitatea serviciului . . . 308

10.2.7 Configurarea ¸si testarea unei ret¸ele IP locale . . . 309

10.2.7.1 Alegerea parametrilor . . . 309

10.2.7.2 Configurarea parametrilor de ret¸ea pe diverse sisteme de op- erare . . . 312

10.2.7.3 Testarea ¸si depanarea ret¸elelor . . . 313

10.3 Nivelul transport . . . 314

10.3.1 Conexiuni cu livrare garantat˘a: protocolul TCP . . . 314

10.3.1.1 Principiul conexiunii TCP . . . 315

10.3.1.2 Comunicat¸ia bidirect¸ional˘a . . . 320

10.3.1.3 Deschiderea ¸si ˆınchiderea conexiunii . . . 320

10.3.1.4 Alegerea num˘arului init¸ial de secvent¸˘a . . . 323

10.3.1.5 ˆInchiderea fort¸at˘a a conexiunii . . . 324

10.3.1.6 Identificarea aplicat¸iei destinat¸ie . . . 325

10.3.1.7 Corespondent¸a ˆıntre funct¸iilesocket()¸si act¸iunile modulu- lui TCP . . . 326

10.3.1.8 Controlul fluxului . . . 327

10.3.1.9 Stabilirea time-out-ului pentru retransmiterea pachetelor . . 327

10.3.1.10Algoritmul lui Nagle ¸si optimizarea num˘arului de pachete . 328 10.3.1.11Trimiterea datelor speciale (out of band) . . . 328

10.3.2 Datagrame nesigure: UDP . . . 329

10.4 Identificarea nodurilor dup˘a nume: sistemul DNS . . . 330

10.4.1 Numele de domeniu . . . 330

10.4.2 Structura logic˘a a bazei de date DNS . . . 332

10.4.3 ˆImp˘art¸irea ˆın domenii de autoritate . . . 333

10.4.4 Mecanismul de interogare a serverelor . . . 334

10.4.5 Sincronizarea serverelor pentru un domeniu . . . 335

10.4.6 C˘autarea numelui dup˘a IP . . . 336

10.5 Leg˘aturile directe ˆıntre nodurile IP . . . 337

10.5.1 Rezolvarea adresei — ARP . . . 337

10.6 Configurarea automat˘a a stat¸iilor — DHCP . . . 339

10.7 Situat¸ii speciale ˆın dirijarea pachetelor . . . 341

10.7.1 Filtre de pachete (firewall) . . . 341

10.7.2 Ret¸ele private . . . 346

10.7.3 Translat¸ia adreselor (NAT) . . . 347

10.7.3.1 Translat¸ia adresei surs˘a . . . 347

(12)

12 Cuprins

10.7.3.2 Translat¸ia adresei destinat¸ie . . . 350

10.7.4 Tunelarea . . . 351

11 Aplicat¸ii ˆın ret¸ele 353 11.1 Po¸sta electronic˘a . . . 353

11.1.1 Formatul mesajelor . . . 354

11.1.1.1 Antetul mesajelor . . . 355

11.1.1.2 Extensii MIME . . . 358

11.1.1.3 Ata¸sarea fi¸sierelor ¸si mesaje din mai multe p˘art¸i . . . 359

11.1.1.4 Codificarea corpului mesajului ¸si a ata¸samentelor . . . 360

11.1.2 Transmiterea mesajelor . . . 362

11.1.2.1 Protocolul SMTP . . . 362

11.1.2.2 Determinarea urm˘atorului MTA . . . 365

11.1.2.3 Configurarea unui MTA . . . 366

11.1.3 Securitatea po¸stei electronice . . . 368

11.2 Sesiuni interactive la distant¸˘a . . . 371

11.2.1 Protocolulssh . . . 373

11.2.1.1 Conexiuneassh protejat˘a criptografic . . . 373

11.2.1.2 Metode de autentificare ˆınssh . . . 376

11.2.1.3 Multiplexarea conexiunii, tunelarea ¸si aplicat¸ii . . . 379

11.2.2 Sistemul X-Window . . . 379

11.3 Transferul fi¸sierelor ˆın ret¸ea . . . 380

11.3.1 Protocolulftp . . . 381

11.3.2 Protocolul HTTP . . . 382

11.3.2.1 Structura cererilor ¸si a r˘aspunsurilor . . . 383

11.3.2.2 URL-urile . . . 384

11.3.2.3 Alte facilit˘at¸i HTTP . . . 385

11.3.2.4 Proxy HTTP . . . 386

11.3.2.5 Conexiuni securizate: SSL/TLS . . . 387

11.3.2.6 Utilizarea TLS pentru web . . . 389

11.4 PGP/GPG . . . 390

11.4.1 Structura cheilor GnuPG . . . 390

11.4.1.1 Chei primare ¸si subchei . . . 391

11.4.1.2 Utilizatori ¸si identit˘at¸i . . . 392

11.4.1.3 Generarea ¸si modificarea cheilor . . . 392

11.4.1.4 Controlul perioadei de valabilitate a cheilor . . . 393

11.4.1.5 Gestiunea cheilor secrete . . . 395

11.4.2 Transmiterea ¸si certificarea cheilor publice . . . 395

11.4.2.1 Transmiterea cheilor publice . . . 395

11.4.2.2 Verificarea autenticit˘at¸ii cheilor . . . 397

11.4.3 Transmiterea mesajelor criptate sau semnate . . . 399

Bibliografie 401

Index 405

(13)

Prefat ¸˘ a

ˆIn contextul prezent al dezvolt˘arii ret¸elelor de calculatoare, este inutil s˘a mai subliniem important¸a acestui domeniu.

Lucrarea de fat¸˘a se adreseaz˘a ˆın principal programatorilor de aplicat¸ii ˆın ret¸ea ¸si administratorilor de ret¸ele complexe. Sunt presupuse, din partea cititorului, cuno¸stint¸e de baz˘a de programare, precum ¸si privind funct¸ionarea sistemelor de operare.

Ca un avertisment pentru programatori, ment¸ion˘am c˘a, de¸si lucrarea trateaz˘a chestiuni de nivel mult mai coborˆat decˆat cel al platformelor ¸si bib- liotecilor utilizate ˆın mod normal ˆın aplicat¸iile ˆın ret¸ea, este totu¸si util˘a ˆın vederea unei bune ˆınt¸elegeri a acestor platforme ¸si biblioteci.

Tot ceea ce are leg˘atur˘a ˆıntr-un fel sau altul cu calculatoare are dou˘a caracteristici: se dezvolt˘a foarte repede ¸si est foarte complex. Ret¸elele de calculatoare nu fac except¸ie. Ca urmare, este extrem de u¸sor pentru oricine s˘a se piard˘a ˆın nenum˘aratele detalii ˆın permanent˘a schimbare.

Consider˘am c˘a, ˆın orice domeniu, o bun˘a prezentare trebuie s˘a porneasc˘a de la principiile de baz˘a. Principiile de baz˘a se sunt (relativ) simple ¸si evolueaz˘a mult mai lent decˆat construct¸iile tehnice elaborate pe baza lor. ˆIn consecint¸˘a, prima parte a lucr˘arii de fat¸˘a,principii, este dedicat˘a studierii problemelor ce trebuie rezolvate de o ret¸ea de calculatoare, precum ¸si a principiilor construct¸iei posibilelor solut¸ii ale acestor probleme.

Partea a doua a lucr˘arii, protocoale, prezint˘a cˆateva dintre cele mai r˘aspˆandite protocoale ¸si mecanisme utilizate ˆın ret¸elele de calculatoare. Ea este construit˘a pentru a oferi cititorului o privire de ansamblu asupra protocoalelor studiate. Aceast˘a privire de ansamblu poate fi suficient˘a pentru unii cititori, ˆın caz contrar fiind probabil necesar˘a citirea efectiv˘a a standardelor.

Lucrarea de fat¸˘a este rodul experient¸ei autorului ˆın activit˘at¸i legate de administrarea ret¸elei de calculatoare a Departamentului de Informatic˘a al Facult˘at¸ii de Matematic˘a ¸si Informatic˘a din cadrul Universit˘at¸ii Babe¸s-Bolyai Cluj-Napoca, ˆın predarea unui curs de Ret¸ele de calculatoare la aceast˘a fac-

(14)

14 Prefat¸˘a

ultate, precum ¸si din activitatea de cercetare desf˘a¸surat˘a de-a lungul anilor, ˆın special 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 vehiculeaz˘a ˆın sistemul medical, precum

¸si nevoia de confident¸ialitate ¸si securitate a lor, cer o foarte bun˘a cunoa¸stere

¸si punere ˆın practic˘a a not¸iunilor legate de codificarea informat¸iei, de metode

¸si protocoale criptografice, de aplicat¸ii ˆın ret¸ele etc.

(15)

Capitolul 1

Introducere

Prin ret¸ea de calculatoare ˆınt¸elegem un sistem (constˆand din com- ponente hard ¸si soft) care interconecteaz˘a ni¸ste calculatoare, permit¸ˆand unor programe ce se execut˘a pe aceste calculatoare s˘a comunice ˆıntre ele.

De notat c˘a, ˆın uzul comun, termenul de ret¸ea de calculatoare mai are

¸si sensul desistem de calcul, construit din mai multe calculatoare interconec- tate ˆıntr-o ret¸ea, care se comport˘a ca un sistem unitar, de exemplu, prezint˘a acelea¸si conturi de utilizatori pe toate calculatoarele.

1.1. Serviciile oferite de ret ¸ea

Se spune c˘a orice problem˘a bine formulat˘a este pe jum˘atate rezolvat˘a.

Prin urmare, pentru ˆınceput, vom stabili mai exact ce se dore¸ste de la o ret¸ea de calculatoare.

ˆIntr-o ret¸ea de calculatoare avem mai multe calculatoare pe care se execut˘a procese utilizator. Rolul ret¸elei este de-a oferi acestor procese posi- bilitatea de-a comunica ˆıntre ele. Din punctul de vedere al programatorului acestor procese, ret¸eaua ofer˘a ni¸ste funct¸ii, din nucleul sistemului de oper- are sau din biblioteci standard, apelabile de c˘atre aceste procese (fig. 1.1).

Ansamblul acestor funct¸ii constituie interfat¸a de programare (engl. APIApplication Programming Interface) a ret¸elei.

Principalele funct¸ii oferite de ret¸ea, apelabile de c˘atre un proces uti- lizator, sunt o funct¸ie care trimite date de la procesul curent spre partenerul sau partenerii de comunicat¸ie ¸si o funct¸ie care recept¸ioneaz˘a datele trimise spre procesul curent. ˆIn aceste funct¸ii este necesar˘a desemnarea destinatarului spre care procesul emit¸˘ator dore¸ste transmiterea datelor, respectiv a emit¸˘atorului dinspre care procesul receptor solicit˘a s˘a primeasc˘a date. ˆIn acest scop, fiecare

(16)

16 1.1. Serviciile oferite de ret¸ea

calculator Proces surs˘a

Proces destinat¸ie calculator

Ret¸ea interfat¸a de

programare (API) send()

recv()

Figura 1.1: Ret¸eaua de calculatoare, din punctul de vedere al proceselor aplicat¸ie.

Funct¸ionalitatea ret¸elei este oferit˘a prin funct¸ii apelabile din procesele utilizator.

Ret¸eaua ofer˘a o aplicat¸iilor o cale de transmisie a datelor (linia punctat˘a). Construct¸ia efectiv˘a a ret¸elei nu este vizibil˘a aplicat¸iilor.

entitate ce poate comunica ˆın ret¸ea trebuie s˘a aib˘a asociat˘a o adres˘a (un ¸sir de bit¸i, construit dup˘a anumite reguli, identificˆand unic o anumit˘a entitate).

Pe lˆang˘a aceste funct¸ii de baz˘a, ret¸eaua mai ofer˘a funct¸ii pentru con- figurarea diferit¸ilor parametrii. O parte dintre ace¸sti parametri fixeaz˘a rolul

¸si locul diverselor componente ˆın cadrul ret¸elei (de exemplu, fiecare calculator trebuie s˘a-¸si cunoasc˘a propria adres˘a). Alt¸i parametrii sunt legat¸i de calitatea serviciilor oferite de ret¸ea (debit de transfer de date, timp de propagare, etc).

Datele transmise de procesele utilizator sunt de obicei ¸siruri arbitrare de octet¸i. Rolul ret¸elei este de-a transmite ˆıntocmai ¸sirul de octet¸i trimis de procesul surs˘a c˘atre procesul destinat¸ie. Semnificat¸ia, pentru procesul destinat¸ie, a unui ¸sir de octet¸i transmis face obiectul unei ˆınt¸elegeri (proto- col) ˆıntre procesele utilizator. La proiectarea ret¸elei nu ne intereseaz˘a ce fac procesele utilizator cu datele transferate; la proiectarea programelor utilizator nu ne intereseaz˘a cum lucreaz˘a ret¸eaua pentru a transmite datele.

ˆIn continuare vom trece ˆın revist˘a principalele caracteristici ale ser- viciului oferit de ret¸ea proceselor de aplicat¸ie.

O comunicat¸ie poate fi, dup˘a num˘arul destinatarilor:

punct la punct, dac˘a exist˘a un singur destinatar. ˆIn mod obi¸snuit, des- tinatarul este select¸ionat explicit de c˘atre procesul emit¸˘ator; o astfel de comunicat¸ie este numit˘a unicast. Uneori ˆıns˘a, de exemplu ˆın cazul ˆın care un serviciu este oferit de mai multeservere, echivalente din punctul de vedere al clientului, este favorabil ca ret¸eaua s˘a aleag˘a destinatarul comunicat¸iei, ˆın funct¸ie de distant¸a fat¸˘a de emit¸˘ator, dintr-o mult¸ime

(17)

specificat˘a de destinatari posibili. Un astfel de comunicat¸ie se nume¸ste anycast.

difuziune, dac˘a exist˘a mai mult¸i destinatari. Distingem difuziune com- plet˘a(engl.broadcast), ˆın care destinatari sunt toate calculatoarele dintr- o ret¸ea, ¸sidifuziune selectiv˘a (engl. multicast), ˆın care destinatarii sunt o submult¸ime aleas˘a a calculatoarelor din ret¸ea.

Serviciul de comunicat¸ie oferit de ret¸ea poate fi de tipconexiune sau de tip transport de datagrame:

ˆIn cazulconexiunilor, ˆın cadrul comunicat¸iei ˆıntre dou˘a procese se disting trei faze:

- deschiderea conexiunii, ˆın cadrul c˘areia sunt f˘acute ni¸ste preg˘atiri, inclusiv alocarea unor resurse pentru comunicat¸ie;

-comunicat¸ia propriu-zis˘a, ˆın care unul sau ambele procese transmite un ¸sir de pachete sau de bit¸i celuilalt proces;

-ˆınchiderea conexiunii, ˆın cadrul c˘areia se elibereaz˘a resursele alocate la deschidere.

ˆIn cazul transportului de datagrame, procesul emit¸˘ator preg˘ate¸ste un ansamblu, numit datagram˘a (prin analogie cu telegram˘a), cuprinzˆand un ¸sir de bit¸i destinat procesului receptor ¸si anumite informat¸ii necesare livr˘arii (adresa destinatarului). Apoi transmite datagrama ret¸elei de cal- culatoare, care o transmite procesului receptor. Mai multe datagrame trimise de acela¸si proces surs˘a c˘atre acela¸si proces destinat¸ie sunt trans- mise independent una de alta, ceea ce duce, ˆın general, la posibilitatea invers˘arii ordinii de recept¸ie fat¸˘a de ordinea de emisie a datagramelor.

Principalii parametri de calitate ai serviciului oferit de ret¸ea sunt:

Capacitateade transport oferit˘a de ret¸ea, saudebitul maxim acceptat, este raportul dintre num˘arul de bit¸i transportat¸i ˆın cadrul unei comunicat¸ii

¸si timpul ˆın care ace¸stia sunt transmi¸si. Echivalent, capacitatea este inversul duratei medii ˆıntre trecerea, printr-un punct dat al ret¸elei, a doi bit¸i consecutivi ai unei comunicat¸ii.

Timpul de transfer a unui bloc de date este timpul scurs de la trecerea, printr-un punct dat, a primului bit al blocului pˆan˘a la trecerea, prin acela¸si punct, a ultimului bit. Timpul de transfer este egal cu raportul dintre dimensiunea blocului ¸si debitul cu care se face transferul.

Capacitatea oferit˘a de ret¸ea unei leg˘aturi poate s˘a varieze datorit˘a variat¸iei debitului altor comunicat¸ii care partajeaz˘a acelea¸si echipamente.

(18)

18 1.1. Serviciile oferite de ret¸ea

Exist˘a aplicat¸ii, de exemplul legate de transfer de fi¸siere, pentru care este important ca ret¸eaua s˘a ofere o capacitate medie cˆat mai mare.

Penttru alte aplicat¸ii, cum ar fi telefonia, transmisia video (de exemplu pentru teleconferint¸e) sau alte aplicat¸ii ˆın timp real, este important s˘a nu scad˘a niciodat˘a capacitatea leg˘aturii sub o anumit˘a valoare minim˘a, ˆıns˘a o capacitate mai mare nu este util˘a.

Timpul de propagare ˆıntre dou˘a entit˘at¸i este timpul scurs ˆıntre mo- mentul ˆın care entitatea surs˘a emite un bit ¸si momentul ˆın care acel bit ajunge la destinat¸ie. Timpul de propagare rezult˘a din ˆınsumarea tim- pului de propagare a semnalului de-a lungul mediului de comunicat¸ie cu diver¸sii timpi de a¸steptare a datelor ˆın diverse zone tampon. De re- marcat c˘a timpul de propagare a semnalului este egal cu distant¸a de la emit¸˘ator la receptor ˆımp˘art¸it˘a la viteza de propagare a semnalului, iar viteza de propagare nu poate dep˘a¸si viteza luminii ˆın vid; din acest mo- tiv, de exemplu, timpul de propagare prin leg˘aturi prin satelit nu poate fi mai scurt de cˆateva zecimi de secund˘a.

Timpul scurs de la ˆınceputul transmisiei unui bloc de date de c˘atre emit¸˘ator pˆan˘a la finalul recept¸iei blocului de c˘atre receptor este egal cu suma dintre timpul de transfer ¸si timpul de propagare.

Uneori, ˆın loc de timpul de propagare se utilizeaz˘a o alt˘a m˘arime, timpul dus-ˆıntors, care este timpul scurs de la transmiterea unui mesaj de c˘atre o partenerul de comunicat¸ie pˆan˘a la primirea r˘aspunsului din partea acestuia. Timpul dus-ˆıntors este suma dintre timpii de propa- gare pentru cele dou˘a sensuri ¸si timpul de procesare pentru crearea r˘aspunsului.

Evident, timpul de propagare e bine s˘a fie cˆat mai scurt, ˆıns˘a diferite aplicat¸ii au cerint¸e diferite:

- La unele aplicat¸ii timpul de propagare nu este prea important. De exemplu, la transferul unui fi¸sier mare, la care oricum timpul de transfer este mare, timpul de propagare influent¸eaz˘a foarte put¸in timpul total necesar transmiterii fi¸sierului.

- La difuzarea de materiale audio sau video, un timp de propagare mare nu este deranjant, ˆıns˘a este important ca el s˘a fie constant ˆın timp. Aceasta pentru c˘a nu este deranjant dac˘a o transmisie de televiziune este cu cˆateva secunde ˆın ˆıntˆarziere fat¸˘a de eveni- mentele transmise, ˆıns˘a este important s˘a nu fie momente ˆın care imaginea ,,ˆıngheat¸˘a“ datorit˘a cre¸sterii timpului de propagare ¸si momente ˆın care imaginea ,,sare ˆınainte“ datorit˘a scurt˘arii timpu- lui de propagare.

(19)

- Timpul de propagare (sau, echivalent, timpul dus-ˆıntors) este im- portant s˘a fie scurt ˆın special pentru aplicat¸ii ˆın care entit˘at¸ile ce comunic˘a transmit mesaje scurte ¸si trebuie s˘a a¸stepte r˘aspunsul la mesajul precedent pentru a putea genera mesajul urm˘ator. Ex- emple de astfel de aplicat¸ii sunt: telefonie, videoconferint¸e, sesiuni interactive la distant¸˘a.

Posibilitatea existent¸ei erorilor de transmisie: Erorile de transmisie apar ca urmare a diverselor perturbat¸ii ce afecteaz˘a transmiterea sem- nalelor. Exist˘a metode de-a mic¸sora oricˆat de mult probabilitatea ca un mesaj s˘a fie afectat de erori, ˆıns˘a niciodat˘a aceast˘a probabilitate nu poate fi f˘acut˘a zero (probabilitatea unei erori poate fi f˘acut˘a ˆıns˘a mai mic˘a decˆat, de exemplu, probabilitatea unui cataclism devastator care s˘a distrug˘a toat˘a ret¸eaua). Metodele de reducere a probabilit˘at¸ii erorilor de transmisie sunt studiate ˆın§2.4 ¸si § 4.1.

Transmisia sigur˘aˆınseamn˘a ca fiecare mesaj al entit˘at¸ii surs˘a s˘a ajung˘a exact ˆıntr-un singur exemplar la destinat¸ie (s˘a nu se piard˘a ¸si s˘a nu fie duplicat) ¸si mai multe mesaje transmise de c˘atre o aceea¸si surs˘a spre o aceea¸si destinat¸ie s˘a ajung˘a la destinat¸ie ˆın ordinea ˆın care au fost trans- mise de surs˘a. Mesajele se pot pierde datorit˘a erorilor de transmisie, a supraaglomer˘arii sau a defect˘arii unor echipamente din ret¸ea sau chiar din cauz˘a c˘a emit¸˘atorul transmite cu debit mai mare decˆat este capa- bil receptorul s˘a preia informat¸ia transmis˘a. Duplicarea sau inversarea mesajelor pot fi cauzate de modific˘ari ale configuratiei sau ˆınc˘arc˘arii ret¸elei ˆın timpul trecerii pachetelor prin ret¸ea. Realizarea transmisiei sigure este studiat˘a ˆın §4.3 ¸si § 4.4.

Transmisia sigur˘a este evident util˘a, ˆıns˘a vine cu un anumit cost.

Cel mai adesea, costul este cre¸sterea ¸si fluctuat¸ia timpului de propagare, deoarece mesajele pierdute trebuie retransmise. La o transmisie audio- video, este adesea preferabil˘a p˘astrarea unui timp de propagare redus, cu pret¸ul pierderii, din cˆand ˆın cˆand, a unor fract¸iuni de secund˘a de material audio-video.

Securitatea comunicatieiˆınseamn˘a c˘a un adversar care controleaz˘a o parte din ret¸ea s˘a nu poat˘a obt¸ine informat¸ia transmis˘a, s˘a nu poat˘a modifica datele transmise f˘ar˘a ca acest lucru s˘a fie detectat de c˘atre receptor ¸si s˘a nu poat˘a impersona vreuna dintre entit˘at¸ile ce comunic˘a.

Securitatea comunicat¸iei se obt¸ine prin metode criptografice, studiate ˆın capitolul 6.

(20)

20 1.2. Principalele elemente ale unei ret¸ele de calculatoare

1.2. Principalele elemente ale unei ret ¸ele de calcula- toare

Pentru ca dou˘a dispozitive aflate la distant¸˘a unul de cel˘alalt s˘a poat˘a comunica, este nevoie ca cele dou˘a dispozitive s˘a fie legate printr-unmediu de comunicat¸iecare permite propagarea variat¸iei unei m˘arimi fizice. Mediul fizic, ˆımpreun˘a cu dispozitivele de adaptare ˆıntre reprezentarea local˘a a informat¸iei

¸si reprezentarea pe mediul de transmisie constituie nivelul fizic al ret¸elei.

Nivelul fizic este deci un modul care permite transmisia unui ¸sir de bit¸i ˆıntre dou˘a dispozitive legate direct unul de cel˘alalt. Constructiv, nivelul fizic este constituit din: cablul electric, fibra optic˘a sau, dup˘a caz, antenele de emisie- recept¸ie, eventuale amplificatoare sau repetoare, pl˘acile de ret¸ea din calcula- toare ¸sidriver-ele pl˘acilor de ret¸ea. Construct¸ia nivelului fizic este studiat˘a ˆın capitolul 3.

De obicei, serviciul oferit de nivelul fizic sufer˘a de anumite neajun- suri, cum ar fi probabilitatea mare a erorilor ¸si transmisia nesigur˘a. Pentru contracararea acestora, de-o parte ¸si de alta a nivelului fizic se plaseaz˘a cˆate un modul de adaptare; aceste dou˘a module constituienivelul leg˘aturii de date.

Nivelul leg˘aturii de date este construit part¸ial prin hard (parte a pl˘acii de ret¸ea) ¸si part¸ial prin soft (parte a driver-ului pl˘acii de ret¸ea). Construct¸ia nivelului leg˘aturii de date este studiat˘a ˆın capitolul 4.

Nivelul fizic ˆımpreun˘a cu nivelul leg˘aturii de date ofer˘a o leg˘atur˘a bun˘a ˆıntre dou˘a calculatoare conectate direct printr-un mediu fizic. Ar fi neeconomic s˘a cerem s˘a existe o leg˘atur˘a direct˘a ˆıntre oricare dou˘a calcula- toare; este preferabil s˘a putem transmite date prin intermediul unui lant¸ de calculatoare (sau alte dispozitive) legate fizic fiecare cu urm˘atorul din lant¸.

Realizarea unei astfel de leg˘aturi cade ˆın sarcina nivelului ret¸ea, constituit din cˆate un modul ˆın fiecare calculator al ret¸elei. Modulul de ret¸ea este con- struit prin soft, ˆın nucleul sistemului de operare al fiec˘arui calculator din ret¸ea.

Construct¸ia ¸si funct¸ionarea nivelului ret¸ea este studiat˘a ˆın capitolul 5.

De obicei, serviciul oferit direct de c˘atre nivelul ret¸ea nu poate fi utilizat direct de c˘atre programele utilizator. De aceea, ˆıntre modului de ret¸ea

¸si programul utilizator se mai interpune un modul, constituind (ˆımpreun˘a cu modulul omolog de pe calculatorul partener de comunicat¸ii)nivelul transport.

Nivelul transport este constituit din p˘art¸i ale nucleului sistemului de operare

¸si, uneori, biblioteci legate ˆın programele utilizator.

Relat¸iile dintre aceste componente sunt reprezentate ˆın figura 1.2.

Fiecare dintre nivele ofer˘a nivelului superior o interfat¸˘a care cuprinde ˆın principal funct¸ii de trimitere ¸si de recept¸ie a datelor. Aceste funct¸ii sunt

(21)

Modul leg˘atur˘a fizic˘a

Modul leg˘atur˘a fizic˘a

Modul leg˘atur˘a fizic˘a

Modul leg˘atur˘a fizic˘a Nod final

legatur˘a de date

Modul legatur˘a de date Aplicat¸ie

Modul transport

Modul

de ret¸ea Modulul de ret¸ea

Modul Modul

legatur˘a de date

Mediu fizic Mediu fizic

Nod final Aplicat¸ie Modul transport

Modul de ret¸ea Modul legatur˘a de date Nod intermediar

Nivelul aplicat¸ie Nivelul transport

Nivelul leg˘aturii de date

Nivelul ret¸ea

Nivelul fizic

Figura 1.2: Componentele unei p˘art¸i dintr-o ret¸ea de calculatoare. Sunt figurate doar componentele implicate ˆın comunicat¸ia dintre dou˘a aplicat¸ii. Cele dou˘a aplicat¸ii se execut˘a pe dou˘a calculatoare ˆıntre care nu exist˘a o leg˘atur˘a direct˘a, dar exist˘a o leg˘atur˘a printr-un nod intermediar.

similare celor oferite de ret¸ea aplicat¸iilor (a¸sa cum am v˘azut ˆın§1.1), dar ser- viciile oferite sunt mai primitive. Astfel, nivelul fizic ofer˘a nivelului leg˘aturii de date servicii de transfer de date, dar numai ˆıntre calculatoare conectate direct

¸si cu riscul ca datele s˘a fie alterate ˆın timpul transferului sau s˘a se piard˘a com- plet. Nivelul leg˘aturii de date ofer˘a nivelului ret¸ea servicii de transfer de date mai sigure, dar ˆın continuare cu restrict¸ia c˘a transferul este posibil doar ˆıntre calculatoare conectate direct. Nivelul ret¸ea ofer˘a nivelului transport servicii de transfer de date ˆıntre orice dou˘a calculatoare din ret¸ea, dar ˆınc˘a neadec- vate utiliz˘arii directe de c˘atre aplicat¸ii (lipsa transmisiei sigure, comunicat¸ie posibil˘a doar pentru un singur proces aplicat¸ie la un moment dat, etc.).

Construct¸ia fiec˘aruia dintre nivele este independent˘a de construct¸ia celorlalte (conteaz˘a doar interfat¸a dintre ele ¸si parametrii de calitate a servi- ciului oferit de un nivel celui imediat superior). De exemplu, ˆın proiectarea nivelului ret¸ea, nu ne intereseaz˘a nici ce aplicat¸ii vor utiliza ret¸eaua (acela¸si nivel ret¸ea din Internet este utilizat de aplicat¸ii de po¸sta electronic˘a, web, telefonie prin Internet ¸si videoconferint¸e), nici cum este construit nivelul fizic (perechi de conductoare, fibre optice sau leg˘aturi radio prin satelit).

Modulele, de pe acela¸si nivel, din noduri diferite ˆı¸si transmit unul altuia (utilizˆand ˆın acest scop serviciile oferite de nivelul inferior) dou˘a tipuri

(22)

22 1.2. Principalele elemente ale unei ret¸ele de calculatoare

de date: datele utile a c˘aror transfer este cerut de nivelul superior ¸si date de control necesare coordon˘arii activit˘at¸ilor modulelor din cadrul nivelului.

Regulile de reprezentare a acestor date, de organizare a acestora ˆın mesaje, precum ¸si regulile dup˘a care se trimit mesajele ˆıntre modulele aceluia¸si nivel alc˘atuiesc protocolul de comunicat¸ie al nivelului respectiv.

Funct¸ionarea corect˘a a unei ret¸ele necesit˘a respectarea, de c˘atre toate modulele implicate, a protocoalelor de comunicat¸ie stabilite.

1.3. Premise generale ˆın elaborarea ¸ si implementarea protocoalelor ˆın ret ¸ele

Pe lˆang˘a rat¸iunile pur funct¸ionale, studiate pe larg ˆın capitolele urm˘a- toare, ˆın elaborarea ¸si implementarea protocoalelor intervin rat¸iuni practice, pe care le vom ˆın¸sira pe scurt ˆın continuare:

Deoarece o ret¸ea este format˘a din multe componente, frecvent¸a cu care se ˆıntˆampl˘a ca cel put¸in o component˘a a unei ret¸ele s˘a nu funct¸ioneze corect este mare. Este necesar ca o defect¸iune s˘a afecteze cˆat mai put¸in din ret¸ea, iar componentele a c˘aror defectare duce la c˘aderea ˆıntregii ret¸ele trebuie s˘a fie cˆat mai put¸ine, eventual nici una.

G˘asirea unei pene ˆıntr-un sistem complex este, ˆın general, dificil˘a. Ret¸eaua trebuie s˘a ofere mecanisme prin care orice defect¸iune s˘a fie u¸sor de lo- calizat.

Implement˘ari diferite ale unui protocol se pot abate ˆın moduri diferite de la specificat¸ia protocolului. Este bine ca mici abateri ale partenerului de comunicat¸ie s˘a fie tolerate. Rezult˘a de aici principiul c˘a o imple- mentare trebuie s˘a fie strict˘a cu ceea ce transmite ¸si tolerant˘a cu ceea ce recept¸ioneaz˘a.

Ret¸eaua trebuie s˘a funct¸ioneze ast˘azi, sau, un plan bun azi este mai bun decˆat un plan perfect mˆaine (maxim˘a atribuit˘a generalului american George Patton, circa 1944). Momentul standardiz˘arii unui protocol este extrem de delicat: dac˘a este standardizat ˆınainte ca problema de rezolvat s˘a fie bine ˆınt¸eleas˘a ¸si solut¸iile posibile bine analizate, rezult˘a un protocol prost; dac˘a standardizarea apare prea tˆarziu, dup˘a ce s-a r˘aspˆandit deja un protocol acceptabil, exist˘a riscul creerii unui protocol perfect, dar pe care nu-l folose¸ste nimeni deoarece ˆınlocuirea sistemelor existente ar fi mai scump˘a decˆat avantajul adus de protocolul mai bun.

Protocoalele totu¸si evolueaz˘a, iar oprirea ˆıntregii ret¸ele ˆın vederea schimb˘arii echipamentelor afectate de schimbarea protocolului nu este rezonabil˘a.

(23)

Ca urmare, la o schimbare de protocol trebuie avut ˆın vedere existent¸a unei perioade de tranzit¸ie ˆın timpul c˘areia echipamentele noi trebuie s˘a poat˘a comunica cu cele vechi. Tranzit¸ia este mult u¸surat˘a dac˘a proto- colul vechi prevede anumite facilit˘at¸i. O posibilitate este ca ˆın protocol s˘a se prevad˘a o faz˘a de negociere ˆın care fiecare entitate anunt¸˘a ce versi- uni de protocol ¸si ce extensii de protocol cunoa¸ste, iar apoi comunicat¸ia decurge conform versiunii celei mai recente ¸si cu cele mai multe exten- sii suportate de ambii parteneri. Alt˘a posibilitate este stabilirea, de la prima versiune a protocolului, a act¸iunilor unui dispozitiv, ce im- plementeaz˘a o versiune veche a protocolului, la primirea unui mesaj neprev˘azut ˆın acea versiune.

Cerint¸e diferite ale diferitelor aplicat¸ii duc la tendint¸a de-a elabora proto- coale complexe, care s˘a satisfac˘a pe toat˘a lumea. Protocoale complexe duc la implement˘ari scumpe ¸si cu riscuri mari de-a avea erori. Este preferabil un protocol care s˘a ofere cˆateva operat¸ii simple care s˘a poat˘a fi combinate dup˘a dorint¸a aplicat¸iei ce-l utilizeaz˘a. Dac˘a o astfel de abordare nu este fezabil˘a, ducˆand la un protocol prea complex, se re- curge la protocoale ce au posibilitatea de-a fi implementate doar part¸ial;

metodele utilizabile ˆın acest scop sunt similare cu cele descrise mai sus pentru facilitarea evolut¸iei protocoalelor.

(24)

24 Capitolul 1. Introducere

(25)

Capitolul 2

Not ¸iuni de teoria informat ¸iei

Teoria informat¸iei se ocup˘a cu studiul metodelor de codificare a in- format¸iei ˆın vederea transmiterii sau stoc˘arii acesteia. ˆIn cadrul teoriei infor- mat¸iei se studiaz˘a ¸si cum se poate m˘asura cantitatea de informat¸ie transmis˘a ˆıntr-un mesaj ¸si cum se poate m˘asura eficient¸a unei anumite codific˘ari.

Prininformat¸ie ˆınt¸elegem cuno¸stint¸ele unei entit˘at¸i.

ˆIn cele ce urmeaz˘a, ne va interesa problema transmiterii unei infor- mat¸ii de la o surs˘a la odestinat¸ie. Informat¸ia de transmis nu este cunoscut˘a init¸ial nici de destinat¸ie, nici de sistemul de transmitere. Ca urmare, a priori informat¸ia de transmis poate fi v˘azut˘a ca o variabil˘a aleatoare.

Comunicat¸ia dintre surs˘a ¸si destinat¸ie se desf˘a¸soar˘a prin intermediul unui canal de comunicat¸ie. Canalul de comunicat¸ie este capabil s˘a transmit˘a fie o m˘arime variabil˘a ˆın timp, numit˘a semnal (ˆın esent¸˘a, o funct¸ie real˘a continu˘a), caz ˆın care canalul este numit continuu, fie un ¸sir de simboluri dintr-o mult¸ime finit˘a, caz ˆın care canalul este numitdiscret.

Deoarece canalul nu poate transmite direct informat¸ia sursei, ˆıntre surs˘a ¸si canal avem nevoie de un dispozitiv, numit emit¸˘ator, care transform˘a informat¸ia util˘a, produs˘a de surs˘a, ˆıntr-un semnal sau, dup˘a caz, ˆıntr-un ¸sir de simboluri. Similar, ˆıntre canal ¸si destinat¸ie se plaseaz˘a un dispozitiv, numit receptor, al c˘arui rol este de-a efectua operat¸ia invers˘a, ¸si anume de-a ex- trage din semnal sau din ¸sirul de simboluri informat¸ia util˘a pentru destinat¸ie (fig. 2.1).

Destinat¸ie Surs˘a Emit¸˘ator Canal Receptor

Figura 2.1: Transmisia informat¸iei de la surs˘a la destinat¸ie

(26)

26 Capitolul 2. Not¸iuni de teoria informat¸iei

Semnalul sau, dup˘a caz, ¸sirul de simboluri ce tranziteaz˘a canalul se nume¸stereprezentarea informat¸iei. Regulile de corespondent¸˘a dintre informa- t¸ia util˘a ¸si reprezentarea sa poart˘a denumirea de schem˘a de reprezentare a informat¸iei,schem˘a de codificare a informat¸iei saucod.

Ca exemplu, o limb˘a scris˘a este o schem˘a de reprezentare a infor- mat¸iei, pentru un canal discret a c˘arui mult¸ime de simboluri cont¸ine literele alfabetului limbii respective, precum ¸si spat¸iul ¸si semnele de punctuat¸ie. Un text scris ˆıntr-o limb˘a este o reprezentare a informat¸iei, iar conceptele din textul respectiv sunt efectiv informat¸ia cont¸inut˘a ˆın text.

Ca un al doilea exemplu, limba vorbit˘a este o alt˘a schem˘a de reprezentare a informat¸iei, canalul pentru care este construit˘a fiind de tip continuu.

Schema de codificare a informat¸iei se presupune c˘a este stabilit˘a ˆın prealabil ¸si este cunoscut˘a atˆat emit¸˘atorului cˆat ¸si receptorului. De asemenea, ˆın construct¸ia schemei de reprezentare a informat¸iei se t¸ine cont de carac- teristicile canalului ¸si de caracteristici generale ale informat¸iilor ce trebuie s˘a se poat˘a transmite, ˆıns˘a la elaborarea ei nu se cunosc informat¸iile ce trebui- esc efectiv transmise. De exemplu, la elaborarea unei scheme de codificare a literelor dintr-un text utilizˆand un canal ce poate transmite doar simbolurile 0 ¸si 1 se poate t¸ine cont de frecvent¸a obi¸snuit˘a a literelor ˆıntr-un text, dar nu

¸si de textul efectiv de transmis.

Restul capitolului trateaz˘a scheme de reprezentare a informat¸iei pen- tru canale discrete. Vom studia ˆın continuare:

propriet˘at¸i generale ale codurilor,

problema minimiz˘arii num˘arului de simboluri necesare a fi transmise prin canal, precum ¸si m˘asurarea cantit˘at¸ii de informat¸ie,

problema codific˘arii ˆın cazul ˆın care canalul altereaz˘a ¸sirul de simboluri pe care ˆıl transmite (canal cu perturbat¸ii).

2.1. Problema codific˘ arii informat ¸iei pentru un canal discret

ˆIn cazul unui canal discret, canalul poate transmite un ¸sir de sim- boluri dintr-o mult¸ime S, numit˘a mult¸imea simbolurilor de cod sau alfabetul canalului. Elementele lui S se numesc simboluri de cod sau, scurt, simboluri.

Mult¸imeaS este finit˘a ¸si are cel put¸in dou˘a elemente. De regul˘a S={0,1}. Pentru ¸sirurile de simboluri de cod vom utiliza urm˘atoarele notat¸ii:

S reprezint˘a mult¸imea ¸sirurilor finite de elemente dinS.

u·v reprezint˘a concatenarea ¸siruriloru ¸si v.

(27)

• |u|reprezint˘a lungimea ¸sirului u; avem |u·v|=|u|+|v|,∀u, v∈S.

εeste ¸sirul vid; avem |ε|= 0 ¸si u·ε=ε·u=u,∀u∈S.

Informat¸ia transmis˘a de c˘atre surs˘a const˘a dintr-un ¸sir de mesaje.

Fiecare mesaj este un element dintr-o mult¸imeM de mesaje posibile. Mesajele provin din universul utilizatorului sistemului; ele pot fi propozit¸ii, litere, nu- mere, etc.

Mult¸imea de mesaje M este nevid˘a ¸si cel mult num˘arabil˘a. De cele mai multe oriM este finit˘a.

Definit¸ia 2.1 Numim funct¸ie de codificare sau cod orice funct¸ie injectiv˘a c : M S, unde M este mult¸imea de mesaje, cel mult num˘arabil˘a, iar S este mult¸imea simbolurilor de cod, finit˘a ¸si avˆand cel put¸in dou˘a elemente.

Fiecare mesajm∈M va fi codificat prin ¸sirul c(m)∈S.

Definit¸ia 2.2 Numim cuvˆant de cod orice ¸sir de simboluri de codw∈S cu proprietatea c˘a exist˘a un mesajm∈M astfel ˆıncˆatw=c(m).

Numimmult¸imea cuvintelor de codmult¸imea W =c(M).

Un ¸sir de mesaje (m1, . . . , mk)∈M(undeMdesemneaz˘a mult¸imea

¸sirurilor finite de mesaje din M) va fi codificat prin ¸sirul format prin con- catenarea codific˘arilor mesajelor:

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

De remarcat c˘a ˆın urma concaten˘arii se pierd delimit˘arile dintre codific˘arile mesajelor individuale. Ca urmare, pentru ca receptorul s˘a poat˘a decodifica f˘ar˘a ambiguit˘at¸i orice transmisie a emit¸˘atorului este necesar˘a o proprietate suplimentar˘a a codului, aceea de-a fi unic decodabil:

Definit¸ia 2.3 Un cod c:M →S se nume¸ste:

cod unic decodabil, dac˘a funct¸ia ˆc:M →S dat˘a prin ˆ

c(m1, m2, . . . , mk) =c(m1)·c(m2)·c(mk) (2.1) este injectiv˘a.

cod cu proprietatea de prefix saucod prefix, dac˘a nu exist˘am1, m2 ∈M, cu m1 6= m2, astfel ˆıncˆat c(m1) s˘a fie prefix pentru c(m2) ¸si ˆın plus c(m)6=ε,∀m∈M.

(28)

28 2.1. Problema codific˘arii informat¸iei pentru un canal discret

cod de lungime fix˘a, dac˘a exist˘a o constant˘a l IN\ {0} astfel ˆıncˆat

|c(m)|=l,∀m∈M; valoareal se nume¸ste lungimea codului;

Propozit¸ia 2.4 Au loc urm˘atoarele propriet˘at¸i:

1. Orice cod de lungime fix˘a este cod prefix.

2. Orice cod prefix este unic decodabil.

Demonstrat¸ia este imediat˘a.

Exemplul 2.1: Consider˘am mult¸imea mesajelorM ={a, b, c, d}¸si mult¸imea simbolurilor de codS ={0,1}. Urm˘atorul cod are proprietatea de prefix.

a 7→ 0 b 7→ 101 c 7→ 11 d 7→ 100

Exemplul 2.2: Urm˘atorul cod, obt¸inut prin oglindirea cuvintelor codului din exemplul anterior, este unic decodabil dar nu are proprietatea de prefix:

a 7→ 0 b 7→ 101 c 7→ 11 d 7→ 001

Codul nu este prefix ˆıntrucˆat cuvˆantul de cod 0 care este codificarea mesajului aeste prefix al cuvˆantului de cod 001 care este codificarea mesajuluid.

De notat c˘a un cod obt¸inut prin oglindirea cuvintelor unui cod prefix se nume¸stecod sufix ¸si ˆıntotdeauna este unic decodabil.

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

a 7→ 0 b 7→ 1 c 7→ 01

Codul nu este unic decodabil ˆıntrucˆat ¸sirul de simboluri de cod 01 poate fi codifcarea mesajului csau a ¸sirului de mesaje ab.

(29)

2.2. Coduri cu proprietatea de prefix

De¸si simple, codurile de lungime fix˘a nu sunt adecvate ˆın urm˘atoarele dou˘a cazuri:

pentru obt¸inerea unui cod eficient, adic˘a avˆand cuvinte cˆat mai scurte, dac˘a probabilit˘at¸ile diverselor mesaje dinM sunt diferite (M este mul- t¸imea mesajelor sursei);

dac˘aMnu este finit˘a (de exemplu,M este mult¸imea numerelor naturale).

ˆIn aceste situat¸ii, trebuie s˘a ne extindem la clase mai largi decˆat cea a codurilor de lungime fix˘a. A¸sa cum vom vedea ˆın continuarea paragrafului de fat¸˘a, clasa codurilor prefix este suficient˘a ˆın situat¸iile enumerate mai sus ¸si, ˆın acela¸si timp, permite decodificarea destul de simpl˘a a transmisiei.

2.2.1. Reprezentarea arborescent˘a a codurilor prefix

Unui cod prefixc:M →S i se poate ata¸sa un arbore ˆın care:

pentru fiecare nod intern, muchiile descendente sunt cel mult ˆın num˘ar de|S|¸si sunt etichetate cu simboluri distincte din S;

fiecare frunz˘a este etichetat˘a cu cˆate un mesaj distinct dinM;

cuvˆantul de cod al unui mesaj este format din simbolurile de cod ale muchiilor de pe lant¸ul ce une¸ste r˘ad˘acina cu frunza ata¸sat˘a mesajului.

Construct¸ia arborelui se face conform algoritmului 2.1 (Genereaz˘a ar- bore).

Exemplul 2.4: Pentru codul din exemplul 2.1 arborele este reprezentat ˆın figura 2.2.

0 1

a

0

0 1

1

d b

c

Figura 2.2: Arborele ata¸sat unui cod prefix Exemplul 2.5: Fie codul prefix pentru mult¸imea mesajelor

M ={a,b,c,d,e,f,g,h}

(30)

30 2.2. Coduri cu proprietatea de prefix

AlgoritmulGenereaz˘a arbore intrarea: M mult¸ime finit˘a nevid˘a

c:M →S cod prefix

ie¸sirea: T arborele asociat coduluic algoritmul:

creeaz˘aT format doar din r˘ad˘acin˘a r:=r˘ad˘acina luiT

pentrum∈M execut˘a (s1, . . . , sl):=c(m) x:=r

pentrui:=1, l execut˘a

dac˘anu exist˘a muchie descendent˘a de laxetichetat˘a cusi atunci dac˘a xare asociat un mesaj atunci

eroare: c nu este cod este prefix sfˆar¸sit dac˘a

creaz˘a y descendent al luix¸si eticheteaz˘a (x, y) cusi

sfˆar¸sit dac˘a

x:=descendentul lui x pe muchia etichetat˘asi sfˆar¸sit pentru

dac˘a x nu e frunz˘a atunci

eroare: c nu este cod este prefix sfˆar¸sit dac˘a

asociaz˘a m noduluix sfˆar¸sit pentru

sfˆar¸sit algoritm

Algoritmul 2.1: Generarea arborelui asociat unui cod prefix

Referințe

DOCUMENTE SIMILARE

Rezumat: Pentru evaluarea performanţelor sistemelor de îngrijiri şi a impactului acestora asupra stării de sănătate a populaţiei sunt utilizate mai multe tipuri de

Grija cu care sunt elaborate încaperile in- dica calitatea de gest a templului: un gest pur, a carui tinta este sacrul - care, indiferent de maniera mai mult sau mai putin

Pentru aceasta este necesar, mai întîi, sa precizam care sunt institutiile supuse studiului si care sunt mecanismele crizei prezente în constitutii.. La baza

Procedeul de ortogonalizare descris mai sus poate fi aplicat ¸si ˆın spat¸iile vectoriale euclidiene reale care nu sunt finit dimensionale, unui sistem num˘ arabil de vectori

ˆIn cazul construct¸iei cercului ˆınscris ˆıntr-un triunghi, realizat˘a mai sus, trebuie s˘a demonstr˘am c˘a cercul pe care l-am construit este, ˆıntr-adev˘ar, cercul

Pe lˆ ang˘ a cele trei principii de baz˘ a, ˆın mecanica clasic˘ a se accept˘ a ¸si principiul act¸iunii locale: Efectele lumii ˆınconjur˘ atoare asupra punctului material P

Opt¸iuni de vˆ anzare ¸si cump˘ arare ˆın piet¸e financiare la vedere 35 adic˘ a pret¸ul minimal pe care vˆ anz˘ atorul este decis s˘ a ˆıl accepte coincide cu pret¸ul

De¸si ˆıntreb˘arile au un caracter general, ˆın sensul c˘a ¸si le poate pune orice profesor de matematic˘a (sau om de ¸stiint¸a, sau ¸si mai general, orice om) r˘aspunsurile

Indiferent de vârstă, complicaţiile cele mai frecvente care apar la femei şi într-un număr mult mai mare faţă de bărbaţi sunt reprezentate de insuficienţa cardiacă

CFB — Cipher Feedback: CFB ¸si urm˘ atorul mod, OFB, sunt utilizate ˆın special acolo unde mesajele sunt mult mai scurte decˆ at dimensiunea blocului, ˆıns˘ a emit¸˘

Pentru a suprprinde acest aspect, cuvintele care apar m˘ acar de 5 ori ˆın datele de antrenament ¸si dac˘ a apar de 5 ori mai des ˆın glume decˆ at ˆın non-glume sunt p˘

Dac˘ a not˘ am ST - mult¸imea spat¸iilor topologice, SM - mult¸imea spat¸iilor metrice (care sunt ¸si spat¸ii topologice), SN - mult¸imea spat¸iilor normate (care sunt ¸si

Argumentul semnul este opt , ional s , i reprezint˘a semnul care se dores , te s˘a apar˘a; dac˘a nu se scrie, va apare implicit urm˘atorul semn dedicat notelor de subsol (as , a cum

unei boli care se răspândește la câțiva oameni, apoi de la aceștia la și mai multe persoane și așa mai departe, până când un mare număr de persoane sunt infectate, numai

Cele mai utilizate forme Lisp pentru controlul explicit al evaluării sunt if şi cond. Forma if poate fi chemată cu doi sau trei parametri.. Sintactic, ea este

Prin urmare instituţiile trebuie să se asigure că tehnologiile moderne sunt prelucrate şi utilizate în mod inteligent nu numai de către profesori, dar şi de

I Isolation - chiar daca mai multe tranzactii sunt executate concurent trebuie ca sistemul sa asigure ca oricare ar fi doua dintre acestea T i si T j , din punctul de vedere a lui T i

Ca funct¸ie ˆın cadrul unei ret¸ele, atˆ at repetorul cˆ at ¸si comutatorul este un dispozitiv la care sunt conectate mai multe cabluri de ret¸ea ¸si care, la primirea unui pachet

Principalele contribuţii revendicate: dezvoltarea unei metode proprii şi pe baza ei a unui algoritm original de determinare a tipului golului de tensiune conform clasificării

Cea mai mare parte din ei sunt Ruteni sau Ro- mâni, cari trăind în părţile unde poporul nostru este mai puţin resistent şi-au uitat limba maternă şi acum

– Serverul creaza un numar de procese copil cand este pornit, si apoi acestia sunt gata sa serveasca

De¸si ar putea p˘ area c˘ a am utilizat efectiv relat¸ia care este construita peste R[U ], ˆın fapt nu am facut decˆ at s˘ a modific˘ am schema de realat¸ie R[U ] ¸si s˘

Modul în care ar trebui să ne gândim la costul de oportuni- tate al banilor este că, atunci când cheltuim bani pe ceva, sunt bani pe care nu îi putem cheltui pe altceva, nici în