univesidad tecnológica del centro capítulo 2 - redes directamente conectadas 1 redes directamente...

Univesidad Tecnológica del Centro

Capítulo 2 - Redes Directamente Conectadas

1

Redes Directamente Conectadas

• Nodos

• Enlaces– Cables dedicados– Líneas alquiladas– Enlace última milla– Inalámbrico

COMPONENTES



2

Un nodo en la red

I/O bus

(To network)

CPU

Memory

NetworkadaptorCache

Memoria: Capacidad en aumento pero con tiempo de acceso limitado.

Procesador: Capacidad de procesamiento en aumento superior a la memoria.

En una red típica, es necesario considerar la relación entre capacidad de computo y capacidad de comunicacìón.



3

Espectro Electromagnético

Radio Infrared UVMicrowave

f(Hz)

FM

Coax

Satellite

TV

AM Terrestrial microwave

Fiber optics

X ray

100

104 105 106 107 108 109 1010 1011 1012 1013 1014 1015 1016

102 106 108 1010 1012 1014 1016 1018 1020 1022 1024104

Gamma ray



4

Enlaces

• Full-duplex y Half-duplex– Full– Half

• Tipos de cables– Par trenzado categoría 5 – 10 – 100 Mbs 100 metros– Coaxial – 200 a 300 m.– Fibra multimodo basado en LED, 2km– Fibra un solo modo basado en diodo laser, 40km

• Líneas alquiladas– DS1 (T1): 1.544Mbps, 24-circuitos digitales de voz de 64 Kbps c.u.– DS3 (T3): 44.736Mbps, 28 enlaces DS1 – STS-1 (OC-1): Señal de transporte síncrona, velocidad base del

enlace = 51.840Mbps– STS-3, 12, 48, 192 (OC-3, OC-12, OC-48, OC-192)

momento t momento u



5

Enlaces

• Enlaces de última milla– POTS: Plain Old Telephone System

– ISDN: Integrated Systems Digital Network

– ADSL: Asynchronous Digital Subscriber Line

– VDSL: Very high data rate Digital Subscriber Line

CODECLínea de voz28.8~56Kbps

Línea digital64-128Kbps

1.554-8.448Mbps16-640Kbps

STS-N12.96~55.2Mbps



6

Enlaces

• Enlaces inalámbricos - AMPS, PCS, GSM, Sistemas telefónicos móviles analógicos/digitales - IEEE 802.11: LAN inalámbrica hasta 54Mbps - Interfaz Blue Tooth: 1Mbps piconet en 10m



7

ADSL

Central Telefónica

Residencia A Residencia B

255 frecuencias para descarga31 para carga2 para control

Lejanos

• Adecuado para que los usuarios descargen archivos desde Internet.



8

Codificación - NRZSignalling component

Signal

Bits

Node NodeAdaptor Adaptor

Bits

NRZ

0 0 1 0 1 1 1 1 0 1 0 0 0 0 1 0

Problema 2: Se dificulta separar ceros seguidos o unos seguidos.

Problema 1: La señal es síncrona; los relojes fuente y destino se sincronizan con los cambios de nivel en la señal. Muchos uno o ceros seguidos no facilitan la sincronización

NRZ: Codifica 1 como nivel alto, 0 como nivel bajo.



9

Bits

NRZ

Clock

Manchester

NRZI

0 0 1 0 1 1 1 1 0 1 0 0 0 0 1 0

NRZI: Codifica 1 como transición; 0 se mantiene sin cambio.

Manchester: Codifica el XOR NRZ- entre la señal y el reloj.

La sincronización del reloj depende de la cantidad de transiciones que ocurran en la señal.

Codificación NRZI y Manchester



10

Resumen• NRZ: El reloj que mantiene el

sincronismo puede fluctuar y es difícil recuperarlo.

• NRZI: Se dificulta sincronizar el reloj cuando se presentan 0s seguidos.

• Manchester: Duplica la cantidad de transiciones facilitando la sincronización del reloj. Sin embargo, reduce en un 50% la cantidad de datos que pueden ser transmitidos por el enlace.



11

Codificación 4B/5B

• Inserta bits al flujo de datos para impedir que estén presentes secuencias largas de ceros o unos.

• No permite más de un cero al principio ni más de dos ceros al final del código.

4 bits 5 bitsf



12

Codificación 4B/5BDato de 4 bits Código de 5 bits

0000 11110

0001 01001

0010 10100

0011 10101

0100 01010

0101 01011

0110 01110

0111 01111

1000 10010

1001 10011

1010 10110

1011 10111

1100 11010

1101 11011

1110 11100

1111 11101

322

1625

4

16 códigos no son utilizados para representar datos, se utilizan para control:

11111 = línea inactiva

00000 = línea muerta

00100 = detener

9 códigos no se adaptan a la regla “un cero al principio, dos ceros al final”.



13

Entramado

Frames

Bits

Node A Node BAdaptor Adaptor

• Una secuencia de bits es enviada de un nodo A a un nodo B sobre un enlace punto a punto. El adaptor de red en el nodo B debe reconocer con exactitud donde comienza y donde termina una trama de datos.

Trama



14

Protocolos orientados a bytes

• Las tramas son tratadas como una secuencia de bytes

( o caracteres de un conjunto particular ).

Método Centinela:

Header Body

8 8 8 8 168

CRC IBM BISYNC, PPP

SYN: comienzo de trama

SOH: comienzo de encabezado

STX: comienzo de texto

ETX: final de texto

centinelas (caracteres especiales) Problema: ETX puede aparecer en el cuerpo de la trama.

Solución: inserción de caracteres. ETX es precedido en el cuerpo de la trama con un carácter de escape DLE. Si DLE también se presenta en el cuerpo de la

trama, es precedido con otro DLE.



15

Protocolos Orientados a Bytes

Método Contador: En lugar de utilizar marcadores para determinar los límites de una trama, se utiliza un contador que indica la cantidad de bytes en la trama.

Header Body

8 8 4214 168

CRCCount DECNET DDCMP

Dificultades: En el método centinela si se corrompe el carácter ETX y en el método contador se corrompe el valor en el contador, las tramas no pueden ser recibidas correctamente.



16

Protocolos orientados a bits• Las tramas son tratadas como secuencias de bits,

sin contemplar fronteras de bytes.

Header Body

8 16 16 8

CRCBeginningsequence

Endingsequence HDLC (ISO)

Secuencia de inicio = Secuencia de finalización = 01111110

• La secuencia de inicio y final de trama 01111110 puede aparecer dentro del cuerpo de la trama.

- Se utiliza inserción de bits. En la fuente de datos: 111111 se convierte en 1111101. En el receptor de datos : Si llega 11111 seguidos de un 0, el 0 es retirado ; si el siguiente bit es 1, entonces (1) este es el final de la trama, u (2) ocurrió un error en la transmisión y la trama es descartada .



17

Entramado basado en el reloj y SONET

• Red síncrona óptica (SONET): – Normalmente utilizada para comunicaciones de

larga distancia. • Utilizado para codificación y entramado.• No utiliza bits para relleno; todas las tramas tienen el

mismo tamaño.• Especifica múltiples enlaces lentos en uno rápido.

– Enlaces STS-1 (51.84Mbps) SONET :• 9 filas con 90 bytes cada una; los primeros 3 bytes de

cada fila son “overhead”.• Los primeros 2 bytes de la trama determinan el

comienzo-de-trama.– Si está sincronizado, el receptor espera la secuencia de

inicio cada 810 bytes.

• Codificación: A los datos se le aplica el XOR con un patrón especial de 127 bits para permitir la recuperación del reloj.



18

Overhead Payload

90 columns

9 rows



19

Multiplexado SONET

• SONET define la jerarquía del enlace STS (STS-N, para N=1, 3, 12, 48, 192, …)

• Una trama STS-N consiste de N sub-tramas STS-1 ( 810 bytes cada una )

• Un enlace STS-N opera a N * velocidad de STS-1 (51.84Mbps)

• Todas las tramas STS siempre tienen una longitud de 125 microsegundos.

• Enlaces STS concatenados:– STS-3 consiste en 3 enlaces paralelos STS-1 operando a

51.84 Mbps– STS-3c es un enlace único de 155.25Mbps.



20

STS-1Hdr STS-1Hdr STS-1Hdr

STS-3cHdr



21

Detección de Errores

• Añade k bits de datos redundantes a un mensaje de n bits. – Es deseable que k << n.– Ejemplo, k = 32 y n = 12,000 (1500 bytes) con CRC-32

• Bit de Paridad-• Algoritmo “Checksum” de Internet.• CRC – Revisión Cíclica Redundante.



22

Paridad

• Paridad impar.• Paridad Par.• Paridad en dos dimensiones.

0101001 1

1101001 0

1011110 1

0001110 1

0110100 1

1011111 0

1111011 0

Bits de Paridad

Byte de paridad

Datos



23

Algoritmo “Checksum” de Internet• Trata al mensajes como una secuencia de números enteros de 16 bits. • Obtiene el complemento a uno de cada número entero de 16 bits.• Suma cada número.• Incrementa el resultado cada vez que se presenta un acarreo de salida.• Ejemplo:

u_shortcksum(u_short *buf, int count){ register u_long sum = 0; while (count--) { sum += *buf++; if (sum & 0xFFFF0000) { // carry occurred, so wrap around sum &= 0xFFFF; sum++; } } return ~(sum & 0xFFFF);}

5: 0 00000000 000001013: 0 00000000 00000011

-5: 0 11111111 11111010-3: 0 11111111 11111100-5 + (-3): 1 11111111 11110110Con acarreo: 0 11111111 11110111Esto corresponde a -8

Mensaje en complemento a uno

• Por último se complementa a uno el resultado, ese es el “Checksum”



24

Verificación Cíclica Redundante CRC

• Representa a un mensaje de n bits como un polinomio de grado n – 1.– ejemplo., Mensaje=10011010 como M(x) = x7 + x4 + x3 + x1

• k es el grado de un polinomio divisor.– ejemplo, C(x) = x3 + x2 + 1

fuente destino

M(x)2k – M(x) 2k % C(x) = mensaje divisible por C(x): P(x)Si P(x) % C(x) == 0

P(x) fue enviado sin errores



25

CRC • Polinomio de la fuente M(x)

– M(x) = 10011010, C(x) = 1101, por lo tanto k = 3– M(x)23 = 10011010000 ( se concatenan 3 ceros)– M(x)23 % C(x) = 101– M(x)23– M(x)23 % C(x) = 10011010101 = P(x)

• Polinomio de ruido E(x)• Polinomio receptor P(x) + E(x)

– E(x) = 0 significa que no hubo errores.

• (P(x) + E(x)) % C(x) == 0 si:– E(x) es igual a cero (sin errores)– E(x) is exactamente divisible por C(x)

• Para recuperar M(x): P(x) + 101 / 23, (eliminar los tres últimos 3 bits)

añadido

últimos 3 bits de P(x)

10011010000 eor1101 1001 eor 1101 1000 eor 1101 1011 eor 1101 1100 eor 1101 1000 eor 1101 101



26

Cálculo CRC con Registros de Desplazamiento

sender receiver

M(x)

CRCCRC + M(x) M(x)

CRC’Si CRC == CRC’, sin error

000 01011001

x0 x1 x2x0 x1 x2

0 0 0

000 01011001 0 0

000 0101100 1 0

000 010110 0 1

000 01010 0 1

000 0100 0 1

000 011 0 1

000 00 1 1

Ejemplo: M(x) = 10011010

C(x) = 1101

1 0 0

0 1 0

0 0 1

1 0 1

000

00

0

101 será transferido



27

Limitaciones de los algoritmos para

detección/corrección de errores • Algunos algoritmos permiten detectar y corregir

errores– La sobrecarga es muy alta

• Algunos errores no pueden ser corregidos• Los protocolos se deben recuperar al existir

tramas pérdidas• Una trama pérdida: posiblemente por datos

dañados– Datos dañados detectados por el receptor >> la

trama es descartada• Se pueden utilizar reconocimentos y tiempos de

expiración para implementar transeferencias confiables ( ARQ )



28

Transmisión Confiable:Parar-y-Esperar ( Stop-and- Wait )

Sender Receiver

Frame

ACK

Sender Receiver

Frame

ACK

Frame

ACK

Sender Receiver

Frame

ACK

Frame

ACK

Sender Receiver

Frame

Frame

ACK

(a) (c)

(b) (d)



29

Tramas Duplicadas

• El transmisor envía una trama

• El receptor reconoce la llegada

• El reconocimiento se pierde o no llega a tiempo

• En el transmisor expira el tiempo y vuelve a transmitir la trama

• El receptor la acepta como una nueva trama – El receptor tiene tramas duplicadas



30

Tratamiento a Tramas Duplicadas

• El encabezado incluye un número de secuencia de 1 bit

• Los números de secuencia para las tramas se alternan

• El transmisor vuelve a transmitir la trama 0– receptor >> recibe nuevamente la

trama 0 >> la descarta ( sin embargo, devuelve el reconocimiento al transmisor)



31

Parar-y-Esperar con Número de Secuencia de 1 - bit

Sender Receiver

Frame 0

ACK 0

Frame 1

ACK 1

Frame 0

ACK 0



32

Deficiencias de Parar-y-Esperar

• Problema: Mantener el enlace lleno• Ejemplo

– Enlace de1.5Mbps; RTT 45ms; Demora x Ancho de Banda = 67.5Kb– Velocidad máxima de transmisión para Parar-y-Esperar =BitsPorTrama/TiempoPorTrama– Para tramas de 1KB, velocidad máxima de transmisión = (1024 x 8) / 0.045 = 182 Kbps– Utilización del enlace = .182 Mbps/1.5 Mbps = 1/8– Capacidad del enlace = 67.5Kb ~ 8KB

• Pudieran estar 8 tramas en el enlace en lugar de una sola • utilización = (1 trama)/(8 tramas) = 1/8 utilización del enlace

TramsmisorReceptor



33

Parar-y-Esperar Mejorado

Para el ejemplo anterior, desearíamos:

• Permitir al transmisor despachar 8 tramas antes de esperar por un reconocimiento ( ACK )

• El transmisor transmite la novena trama al mismo tiempo que llega el reconocimiento ( ACK ) de la primera trama.



34

Ventana Deslizante• Permite múltiples tramas sin

reconocimiento• Límite superior para las tramas

permitidas sin reconocimiento se denomina ventana

Sender Receiver



35

Ventana Deslizante: Transmisor• Asigna un número de secuencia para cada trama (SeqNum)• Mantiene tres variables de estado:

– Tamaño de ventana del transmisor (SWS)– último reconocimiento recibido (LAR)– Ultima trama transmitida (LFS)

• Mantiene fijo : LFS - LAR <= SWS

• Por ejemplo, para una ventana con tamaño, SWS, 7, se podría tener LFS = 30, LAR = 23

• Avanza LAR cuando llega un ACK • Mantiene tramas en un Buffer hasta el número máximo de tramas SWS • Después de que expira el tiempo para una trama, la vuelve a transmitir. Repite esto

hasta que llega el ACK de la trama

<

■ ■ ■ ■ ■ ■

─ SWS

LAR = 23 LFS = 30

26252423 27 28 29 30 3121 22 32

7



36

SW: Receiver

• Mantiene tres variables de estado– Tamaño de ventana del receptor (RWS) ( límite superior en la cantidad

de tramas fuera de orden que se pueden recibir ) – Trama más alta aceptable (LAF)– Última trama recibida (LFR)

• Mantiene fijo : LFA - LFR <= RWS

• Al llegar la trama SeqNum :– Si LFR < SeqNum < = LAF la trama es aceptada– Si SeqNum < = LFR o SeqNum > LAF la trama es descartada

• Envía ACKs acumulados

RWS

LFR = 25 LFA = 32

■ ■ ■ ■ ■ ■

< ─

25 28 3024 33 347



37

Reconocimiento Acumulado

• SeqNumToAck = la secuencia más larga de tramas recibidas pero aún no reconocidas

• Cuando han sido recibidas todas las tramas con números de secuencia <= SeqNumToAck– El receptor reconoce la llegada de la trama

SeqNumToAck ( aún si han sido recibidas tramas con números de secuencia superiores )

• Reconocimiento acumulado

• Luego el receptor establece LFR = SeqNumToAck ajusta LAF a LFR + RWS



38

• Llega la trama 27 • Llega la trama 26

• SeqNumToAck = 28• El receptor reconoce la llegada de la trama 28 lo cual

representa “Reconocimiento Acumulado”• El receptor establece LFR = 28 y ajusta LFA a LFR +

RWS = 28 + 7 = 39

RWS

LFR = 25 LAF = 32

■ ■ ■ ■ ■ ■

< ─

25 28 3024 33 342726

RWS

LFR = 28 LAF = 35

■ ■ ■ ■ ■ ■

< ─

2827 36 3730

RWS

LFR = 25 LAF = 32

■ ■ ■ ■ ■ ■

< ─

25 28 3024 33 34



39

Selección de SWS y RWS

• Objetivo: mantener el enlace lleno

• SWS: cantidad de tramas en el enlace – SWS es seleccionado basado en el

producto demora x ancho de banda

• Valores RWS comúnes: 1 y SWS



40

Números de Secuencia• El campo SeqNum es finito; los números de secuencia se repiten al llegar

al final• Para distinguir diferentes apariciones de los mismos números de secuencia

#s , suponga que cantidad de tramas pendientes < rango de númieros de secuencia ( el cual es igual a MaxSeqNum +1)

• SWS = MaxSeqNum no es suficiente– Asuma un campo de 3-bits para SeqNum (8 valores posibles para

SeqNum 0..7)– SWS=RWS=7 {(tramas faltantes=7)<( rango de números de

secuenca = 8)}– El transmisor envía las tramas 0..6– Las tramas llegan satisfactoriamente, pero se pierden los ACKs – El transmisor vuelve a trasmitir las tramas 0..6– El receptor espera las nuevas tramas 7, 0, 1, ...5, pero recibe las tramas

anteriores con #s 0..5• El receptor no puede distinguir entre las tramas anteriores y las

nuevas• Para RWS=SWS, lo indicado es SWS < (MaxSeqNum+1)/2• Intuitivamente, SeqNum alterna entre las dos mitades del rango de números

de secuencia



41

Canales Lógicos Concurrentes• Protocolo de enlace de datos utilizado en el ARPANET

– Mantiene el enlace lleno sin utilizar la ventana deslizante• Un nodo multiplexa 8 canales lógicas sobre un solo enlace• Se ejecuta parar-y-esperar en cada canal lógico• Mantiene tres bits de estado para cada canal

– Canal ocupado– Números de secuencia 0 o 1.– Siguiente número de secuencia esperado en una trama.

• Cuando el transmisor debe envíar una trama, utiliza al siguiente canal más bajo que este inactivo.• Tramas diferentes se pueden mantener en transito en cada canal.

– El transmisor puede mantener al enlace lleno • Encabezado: 3-bit número de canal, 1-bit número de secuencia

univesidad tecnológica del centro capítulo 2 - redes directamente conectadas 1 redes directamente...

Documents