Bruno Dias Joaquim Macedo Grupo de Comunicações por ...marco.uminho.pt/~dias/MICEI/CC-I/aulas/MICEI-CCI-2006-20007-a.pdf · GCOM -Grupo de Comunicações por Computador Mestrado

Universidade do MinhoEscola de Engenharia

Comunicações por Computador I

Bruno DiasJoaquim Macedo

Grupo de Comunicações por ComputadorDepartamento de Informática

Universidade do Minho

GCOM - Grupo de Comunicações por Computador Mestrado & Curso de Especialização em

Informática 2


Departamento de InformáticaPrograma

Pilhas Protocolares: OSI vs Internet; evoluções tecnológicas.Tecnologias de Redes de Computadores: redes digitais por

pacotes, mensagens ou células; tecnologias de acesso e meios de transmissão; endereçamento de nível dois.

Redes IP: integração por encapsulamento/multiplexagem; endereçamento e encaminhamento interno e externo; evolução do IPv4 para o IPv6; redes unicast, multicast e anycast; segurança em redes IP.

Protocolos de Transporte Internet: TCP vs UDP; endereçamento e multiplexagem.

Protocolos Aplicacionais na Internet: evolução dos protocolos principais e introdução às aplicações distribuídas mais recentes; arquitecturas de gestão de redes.

Suporte a Aplicações Multimédia em Tempo Real: fundamentos de áudio e vídeo; introdução à comunicação em grupo; requisitos de qualidade serviço e desempenho da rede.


Informática 3


Departamento de InformáticaBibliografia Essencial

Computer Networking: A Top-Down Approach Featuring theInternet – 3rd Ed., James F. Kurose & Keith W. Ross, Addison-Wesley, 2004.

Computer Networks and Internets – 4th Ed., Douglas E. Comer, Prentice Hall, 2003.

Quality of Service for Internet Multimedia, Jitae Shin, Daniel C. Lee, C.-C. Jay Kuo, Prentice Hall, 2003.


Informática 4


Departamento de InformáticaVisão Genérica


Informática 5


Departamento de InformáticaSistemas Terminais


Informática 6


Departamento de InformáticaCamada de Rede


Informática 7


Departamento de Informática

Subnet Router

Host

LAN

Fonte: Computer Networks - 3rd Ed., A. Tanenbaum, Prentice Hall, 1996

Hosts, Nets & SubNets


Informática 8


Departamento de InformáticaRouter: Uma Super-Simplificação

Buffer (de pacotes) interno

Linha E

ntrada(/Saída)

Linha (Entrada/)Saída

CPU +


Informática 9



Layer 5

Layer 4

Layer 3

Layer 2

Layer 1

Host 1

Layer 4/5 interface

Layer 3/4 interface

Layer 2/3 interface

Layer 1/2 interface

Layer 5 protocolLayer 5

Layer 4

Layer 3

Layer 2

Layer 1

Host 2

Layer 4 protocol

Layer 3 protocol

Layer 2 protocol

Layer 1 protocol

Physical medium


Camadas e Protocolos


Informática 10



Name of unit exchanged

Presentation

Application

Session

Transport

Network

Data link

Physical

7

6

5

4

3

2

1

Interface

Interface

Host A

APDU

PPDU

SPDU

TPDU

Packet

Frame

Bit

Presentation

Application

Session

Transport

Network

Data link

Physical

Host B

Network Network

Data link Data link

Physical Physical

Router Router

Internal subnet protocol

Application protocol

Presentation protocol

Transport protocol

Session protocol

Communication subnet boundary

Network layer host-router protocol

Data link layer host-router protocolPhysical layer host-router protocol


Modelo de Referência OSI


Informática 11



H2H3

H4

M1

T2

H2

H3

M2

T2

H2

H3

H4

M1

T2

H2

H3

M2

T

2H3H4

M1

H3

M2

H3

H4

M1

H3

M2

H4 M H4 M

M M

Layer 2

protocol2

Layer 3

protocol

Layer 4 protocol

Layer 5 protocol

3

4

5

1

Layer

Source machine Destination machine

Suporte à comunicação…


Informática 12



Applicationlayer

Sessionlayer

Transportlayer

Networklayer

Data link layer

Physicallayer

Presentationlayer

Applicationlayer

Sessionlayer

Transportlayer

Networklayer

Data link layer

Physicallayer

Presentationlayer

Networkprotocol

Actual data transmission path

Transportprotocol

Session protocol

Presentation protocol

Application protocol

Data

Data

Data

Data

Data

Data

Data

Bits

AH

PH

SH

TH

NH

DH DT

SendingProcess

ReceivingProcess


Cabeçalhos & Overhead


Informática 13



TCP/IPOSI

Application

Presentation

Session

Transport

Network

Data link

Physical

7

6

5

4

3

2

1

Application

Transport

Internet

Host-to-network

Not presentin the model

Modelos de Referência TCP/IP vs OSI


Informática 14



Pilha TCP/IP inicial: Protocolos e redes de suporte

ARPANET

Protocols

Networks

TELNET

TCP UDP Transport

LAN

DNS Application

Layer (OSI names)

Packetradio

Physical +data link

SMTP

SATNET

FTP

IP Network


Informática 15



Computer Computer

ModemEndoffice

Tolloffice

Endoffice

Modem

Digital(short cable)

Digital(short cable)

Analog(localloop)

Digital(telephonecompanytrunks)

Analog(localloop)

Codec Codec

Customer premisesequipment

Customer premisesequipment

The use of both analogand digital transmission for acomputer to computer call. Conversion is done by the modemsand codecs.

Transmissão: Digital-Analógico-Digital



Informática 16



(a)

(b)

Switching office

Physical copperconnection set upwhen call is made

Packets queued upfor subsequenttransmission

Computer

Computer

Comutação: Circuitos e Pacotes


Informática 17



Coppertwisted pair

Switchingoffice

High-bandwidthfiber trunk

Junctionbox

(a)

House

Fiber

Fiber to the Curb: (a) Using the telephone network.


Redes e Ligações de Acesso


Informática 18



Switch

(b)

High-bandwidthfiber trunk

Coppercable TVwire

House

Junction box

Fiber

(b) Using the cable TV network.Fiber to the Curb:


Redes e Ligações de Acesso


Informática 19


Departamento de InformáticaModelo Abstracto de Rede


Informática 20


Departamento de InformáticaCamada de Rede


Informática 21


Departamento de InformáticaRede: Circuito Virtual


Informática 22


Departamento de InformáticaRede: Datagramas


Informática 23



Data

Pkt 1

Pkt 2

Pkt 3

Pkt 1

Pkt 2

Pkt 3

Pkt 1

Pkt 2

Pkt 3

A B C D

Msg

Msg

Msg

A B C DA B C D

Propagationdelay

Queuingdelay

Call request signal

Timespent

huntingfor an

outgoingtrunk

Call acceptsignal

ABtrunk

BCtrunk

CDtrunk

(a) (b) (c)

Time

Comutação



Informática 24



• Sem garantia de Serviço

• BE – Best Effort

• LBE – Less than Best Effort

• UBR – Unspecified Bit Rate

• Com garantia de Serviço

• CBR – Constant Bit Rate

• VBR – Variable Bit Rate (rt/nrt – real time/no)

• ABR – Available Bit Rate

Modelos de Serviço


Informática 25



Issue DQDB SMDS X.25

Frame

Relay

ATM

AAL

Connection oriented SIM NÃO SIM SIM SIM

Normal speed (Mbps) 45 45 0.064 1.5 155

Switched NÃO SIM SIM NÃO SIM

Fixed-size payload SIM NÃO NÃO NÃO NÃO

Max payload 44 9188 128 1600 Variável

Permanent VCs NÃO NÃO SIM SIM SIM

Multicasting NÃO SIM NÃO NÃO SIM

Diferentes Serviços de Rede


Informática 26



Network

Architect.

Service

Model

Bandwidth

Guarantee

No Loss

Guarante

e

Ordering TimingCongestion

indication

IPBest

EffortNone None

Any order

possibleNo None

ATM CBRGuaranteed

constant rateYes In order Yes No Congestion

ATM VBRGuaranteed

variable rateYes In order Yes No Congestion

ATM ABRGuaranteed

minimum rateNone In order No

Congestion

indication

ATM UBR None None In order No None

Tecnologia ATM vs IP


Informática 27



Router /

EncaminhadorRouter / Router /

EncaminhadorEncaminhador

Link / Link /

LigaçãoLigação

Custo LinkCusto LinkROTAROTA

LL1111

LL1212

LL1313

Redes e Rotas


Informática 28



2L13DE

............

3L13DC

............

0AA

CustoLinkPróximo NóDestino

NNÓÓ AA

Tabela de Encaminhamento


Informática 29


Departamento de InformáticaEncaminhamento IP

Fonte: Computer Networking: A Top-Down Approach Featuring the Internet

J. Kurose, Addison-Wesley, 2001


Informática 30


Departamento de InformáticaInternet: Estado Out/2002Routing Table Report 20:00 +10GMT Fri 18 Oct, 2002

Analysis Summary----------------

BGP routing table entries examined: 116.117Prefixes after maximum aggregation: 74.648Unique aggregates announced to Internet: 55.576

Total ASes present in the Internet Routing Table: 13.917...Number of addresses announced to Internet: 1.176.988.512...

Percentage of available address space announced: 31.8%Percentage of allocated address space announced: 58.2%Percentage of available address space allocated: 54.6%

Total # prefixes smaller than registry allocations: 48.263

...

End of report


Informática 31


Departamento de InformáticaInternet: Estado Out/2003Routing Table Report 04:00 +10GMT Sat 04 Oct,

2003

Analysis Summary----------------BGP routing table entries examined: 128.816

Prefixes after maximum aggregation: 80.246Unique aggregates announced to Internet: 62.008

Total ASes present in the Internet Routing Table: 15.914...Number of addresses announced to Internet: 1.245.394.468...Percentage of available address space announced: 33.6%

Percentage of allocated address space announced: 60.0%Percentage of available address space allocated: 56.0%

Total # prefixes smaller than registry allocations: 57.8263

...End of report


Informática 32


Departamento de InformáticaEncaminhamento: Abstracção

Abstracção Grafo:• Nós do grafo: são

routers

• Arcos do grafo: sãoligações físicas• Custo do link: atraso,

K/capacidade, nívelcongestão, custo €

Objectivo: determinar um “bom” caminho src-dst(sequência de routers)

Protocolo Routing

A

ED

CB

F

2

2

13

1

1

2

53

5

• “Bom” caminho:• Tipicamente significa“custo mínimo”

• Mas… há outras def’s


Informática 33



Informação:Global:• Todos os routers têm

conhecimento completo de topologia e custo dos links

• Algoritmos estado das ligações(LS-“link state”)

Distribuída: • Router só conhece vizinhos

(fisicam/ ligados) e custo doslinks respectivos

• Processo de computação iterativa, troca de informação com vizinhos

• Algoritmos de vector de distância(DV-“distance vector”)

Actualização:Estáticos:

• Rotas não mudamcom o tempo

Dinâmicos:

• Rotas variam com o tempo

• Em resposta à variação do custo das ligações

• Actualização periódica e/ouassíncrona

Algoritmos de Encaminhamento


Informática 34



Encaminhamento:Algoritmos DV

Fonte: Computer Networking: A Top-Down Approach Featuring the Internet, J. Kurose, Addison-Wesley, 2001


Informática 35



Da Tabela de Distânciasà Tabela de Encaminhamento

D ()

A

B

C

D

A

1

7

6

4

B

14

8

9

11

D

5

5

4

2

ECusto p/ o destino via

des tinat ion

A

B

C

D

A,1

D,5

D,4

D,2

Link Saída, custo

des tinat ion

Tabela Distâncias Tabela de Routing


Informática 36


Departamento de InformáticaAlgoritmo DVIterativo, assíncrono:• Cada iteração local é

causada por:• mudança no custo do

link local ou• recepção de mensagem

do vizinho (vizinhoanuncia novo custo)

Distribuído:• Cada nó notifica

vizinhos só quandomuda o menor custopara qualquer destino(se necessário, vizinhosnotificam vizinhos)

Esperar msg do vizinho com informação de alteração de menor custo do link

Recalcular tabela distâncias

Se mudou(menor-custo(qq-DEST)

então avisar vizinhos

Em cada nó:


Informática 37



Distance Vector (DV) Algorithm. At each node, X:

1 Initialization:

2 for all adjacent nodes v:

3 DX(*,v) = infty /* the * operator means "for all rows" */

4 DX(X,v) = c(X,v)

5 for all destinations, y

6 send minwD(y,w) to each neighbor /* w over all X's neighbors */

7 loop forever8 wait (until I see a link cost change to neighbor V 9 or until I receive update from neighbor V)…



Algoritmo DV


Informática 38



10 if (c(X,V) changes by d)

11 /* change cost to all dest's via neighbor v by d */

12 /* note: d could be positive or negative */

13 for all destinations y: DX(y,V) = DX(y,V) + d

14

15 else if (update received from V wrt destination Y)

16 /* shortest path from V to some Y has changed */

17 /* V has sent a new value for its minwDV(Y,w) */

18 /* call this received new value is "newval" */

19 for the single destination y: DX(Y,V) = c(X,V) + newval

20

21 if we have a new minwDX(Y,w) for any destination Y

22 send new value of minwDX(Y,w) to all neighbors



Algoritmo DV


Informática 39





Algoritmo DV


Informática 40


Departamento de InformáticaAlgoritmo DV - Exemplo

X Z

12

7

Y

D (Y,Z)X

c(X,Z) + min {D (Y,w)}w=

= 7+1 = 8

Z

D (Z,Y)X

c(X,Y) + min {D (Z,w)}w=

= 2+1 = 3

Y


Informática 41


Departamento de InformáticaDV: Good News Travel Fast


Informática 42



DV: Bad News…Count to Infinity!


Informática 43


Departamento de InformáticaDV – Actualizações forçadas


Informática 44



Link State (LS) Algorithm:

1 Initialization:

2 N = {A}

3 for all nodes v

4 if v adjacent to A

5 then D(v) = c(A,v)

6 else D(v) = infty

7 Loop

8 find w not in N such that D(w) is a minimum

9 add w to N

10 update D(v) for all v adjacent to w and not in N:

11 D(v) = min( D(v), D(w) + c(w,v) )

12 /* new cost to v is either old cost to v or known

13 shortest path cost to w plus cost from w to v */

14 until all nodes in N

Encaminhamento: Algoritmos deEstado das Ligações (LS)

Fonte: Comp. Net.: A Top-Down Approach[…], J. Kurose, Addison-Wesley, 2001


Informática 45



step N D(B),p(B) D(C),p(C) D(D),p(D) D(E),p(E) D(F),p(F)

0 A 2,A 5,A 1,A infty infty

Algoritmo LS: Exemplo


Informática 46





1 AD 2,A 4,D 2,D infty



Informática 47






2 ADE 2,A 3,E 4,E



Informática 48






2 ADE 2,A 3,E 4,E

3 ADEB 3,E 4,E



Informática 49






2 ADE 2,A 3,E 4,E

3 ADEB 3,E 4,E

4 ADEBC 4,E



Informática 50






2 ADE 2,A 3,E 4,E

3 ADEB 3,E 4,E

4 ADEBC 4,E

5 ADEBCF



Informática 51


Departamento de InformáticaLSA – Oscilações

Fonte: Computer Networking: A Top-Down Approach Featuring the Internet,



Informática 52


Departamento de InformáticaInternet: Camada de Rede

routingtable

Routing protocols•path selection•RIP, OSPF, BGP

IP protocol•addressing conventions•datagram format•packet handling conventions

ICMP protocol•error reporting•router “signaling”

Transport layer: TCP, UDP

Link layer

physical layer

Networklayer


Informática 53


Departamento de InformáticaEndereçamento IP• Endereço IP – identificador de

32-bit parameters ligação entre

equipamento e link físico:

• Os routers têm,

obrigatoriamente, múltiplas

interfaces lógicas (>1)

• Os hosts podem ter múltiplas

interfaces lógicas

• Os endereços IP associam-

se a interfaces físicos e

identificam interfaces lógicos

(não a hosts ou a routers)

223.1.1.1

223.1.1.2

223.1.1.3

223.1.1.4 223.1.2.9

223.1.2.2

223.1.2.1

223.1.3.2223.1.3.1

223.1.3.27

223.1.1.1 = 11011111 00000001 223.1.1.1 = 11011111 00000001 223.1.1.1 = 11011111 00000001 223.1.1.1 = 11011111 00000001 00000001000000010000000100000001 00000001000000010000000100000001

223 1 11


Informática 54



• Endereço IP:

• Parte da Rede (high order

bits or MSBs);

• Parte do Interface (low order

bits or LSBs).

• Que é uma Rede IP, em termos

de endereçamento?

• Conjunto de Interfaces de

dispositivos com a mesma

identificação/parte de rede e

fisicamente atingíveis entre si

sem intervenção de router.

Interligações entre três redes IP.

Endereçamento IP

LAN

223.1.1.1

223.1.1.2

223.1.1.3

223.1.1.4 223.1.2.9

223.1.2.2

223.1.2.1

223.1.3.2223.1.3.1

223.1.3.27


Informática 55



- Como encontrar e

representar redes?

223.1.3.2223.1.3.1

223.1.3.27

223.1.1.1

223.1.1.3

223.1.1.4

223.1.2.2223.1.2.1

223.1.2.6

223.1.1.2

223.1.7.0

223.1.7.1

223.1.8.0223.1.8.1

223.1.9.1

223.1.9.2

Sistema com seisredes Interligadas.

Endereçamento IP


Informática 56



0 network host

10 network host

110 network host

1110 multicast address

A

B

C

D

class

1.0.0.0 to127.255.255.255

128.0.0.0 to191.255.255.255

192.0.0.0 to223.255.255.255

224.0.0.0 to239.255.255.255

32 bits

Em Classes -“classfull” (endereçamento “clássico”):

Endereçamento IP


Informática 57



• Endereçamento Classful:

• Uso ineficiente do espaço de endereçamento, exaustão de espaço

(p.ex., uma classe B aloca 65K hosts, mesmo que existam apenas 2K hosts)

• CIDR: Classless InterDomain Routing

• Divisão (do endereço) com comprimento arbitrário;

• Formato: A.B.C.D/X, em que X é o número de bits para identificação da

rede; 32-X será a correspondente ao interface.

11001000 00010111 00010000 00000000rede host

200.23.16.0/23

Endereçamento IP


Informática 58



Hosts (parte de identificação do interface na rede):

• Hard-coded em ficheiro de sistema p/ administrador, ou

• DHCP (Dynamic Host Configuration Protocol)

Obter endereço dinamicamente (plug-and-play):

1. host faz broadcast da msg DHCP discover;

2. servidor DHCP responde c/ msg DHCP offer;

3. host pede endereço IP com msg DHCP request;

4. servidor DHCP envia endereço na msg DHCP ack.

Endereçamento IP: Definição

Network (parte de identificação da rede):

• Alocado via espaço de endereçamento do ISP.


Informática 59



ISP: 11001000 00010111 00010000 00000000 - 200.23.16.0/20

Org. 0: 11001000 00010111 00010000 00000000 - 200.23.16.0/23

Org. 1: 11001000 00010111 00010010 00000000 - 200.23.18.0/23

Org. 2: 11001000 00010111 00010100 00000000 - 200.23.20.0/23

… … … …

Org. 7: 11001000 00010111 00011110 00000000 - 200.23.30.0/23

Endereçamento IP: Definição


Informática 60



Endereçamento Hierárquico permite a Agregação de rotas

e anúncios eficientes de informação de routing.

“Qualquer endereçocomeçado por200.23.16.0/20”

200.23.16.0/23

200.23.18.0/23

200.23.30.0/23

ISP X

Organização 0

Organização 7Internet

Organização 1

ISPs-R-UsComeçado por199.31.0.0/16”

200.23.20.0/23Organizaçao 2

...

...

Endereçamento IP: CIDR


Informática 61



>> ISPs-R-Us tem uma rota mais específica para a Organização 1.

200.23.16.0/23

200.23.18.0/23

200.23.30.0/23

ISP X

Organização 0

Organização 7Internet

Organização 1

ISPs-R-UsComeçado por199.31.0.0/16ou200.23.18.0/23

200.23.20.0/23Organização 2

...

...

“Qualquer endereçocomeçado por200.23.16.0/20”

Endereçamento IP: CIDR


Informática 62



Como obter um bloco de endereços (ISPs)?

• A nível europeu: RIPE

(Reseaux IP Européenes).

• A nível mundial: ICANN

(Internet Corporation for Assigned Names & Numbers).

> Fazem alocação de endereços (IP, portas, protocolos, etc);

> Fazem gestão de DNS;

> Fazem atribuição de nomes de domínios;

> Resolvem disputas, etc.

Endereçamento IP

Documents

Bruno Dias Joaquim Macedo Grupo de Comunicações por ...marco.uminho.pt/~dias/MICEI/CC-I/aulas/MICEI-CCI-2006-20007-a.pdf · GCOM -Grupo de Comunicações por Computador Mestrado