comunicación y concurrencia

Derechos Reservados-Universidad Virtual

Comunicación y ConcurrenciaComunicación y Concurrencia

Dr. Raúl Monroy BorjaDr. Raúl Monroy Borja

Aplicaciones de bisimilaridadAplicaciones de bisimilaridad


Ejemplos de aplicaciónEjemplos de aplicación

• Protocolo de comunicación• Protocolo CSMA/CD

• Protocolo de comunicación• Protocolo CSMA/CD


Protocolo de enlace de datosProtocolo de enlace de datos

• Considere un protocolo de enlace de datos, modo simplex, enlace punto a punto, con reconocimiento positivo.

• El medio de transmisión tiene capacidad infinita pero puede perder mensajes.

• Considere que el mensaje que contiene el reconocimiento de recepción jamás puede perderse

• Considere un protocolo de enlace de datos, modo simplex, enlace punto a punto, con reconocimiento positivo.

• El medio de transmisión tiene capacidad infinita pero puede perder mensajes.

• Considere que el mensaje que contiene el reconocimiento de recepción jamás puede perderse


Los componentesLos componentes

accept deliver

Sender

Medium

Receiverack ack

sm

sm

ms

ms

mr

mr

L={ack,sm,ms,mr}


El protocolo [Walker 87]El protocolo [Walker 87]• Especificación

– Service = accept(x).deliver(x).Service• Desarrollo

– Protocol = (Sender | Medium | Receiver)\ L• Donde L = {ack,sm,ms,mr}

– Sender = accept(x). sm(x).Sender'(x)– Sender'(x) = ms.sm(x).Sender'(x)+ack.Sender

• Especificación– Service = accept(x).deliver(x).Service

• Desarrollo– Protocol = (Sender | Medium | Receiver)\ L

• Donde L = {ack,sm,ms,mr}– Sender = accept(x). sm(x).Sender'(x)– Sender'(x) = ms.sm(x).Sender'(x)+ack.Sender

defdef

defdef

defdef

defdef


ContinúaContinúa

– Medium = sm(x).Medium’(x)– Medium’(x) = mr(x).Medium + .ms.Medium– Receiver = mr(x).deliver(x).ack.Receiver

• L (Protocol) = L (Service) = {accept,deliver}

– Medium = sm(x).Medium’(x)– Medium’(x) = mr(x).Medium + .ms.Medium– Receiver = mr(x).deliver(x).ack.Receiver

• L (Protocol) = L (Service) = {accept,deliver}

defdef

defdef

defdef


Sesión con CWBSesión con CWBagent Service = accept.'deliver.Service;

agent Protocol = (Sender | ...)\ L;

set L = {ack,sm,ms,mr};

• Algunos comandos:– sort Protocol; (* accept,’deliver *)– size Protocol; (* 7 states *) – graph Protocol; – states Protocol;

– eq(Protocol,Service); (* true *)

agent Service = accept.'deliver.Service;

agent Protocol = (Sender | ...)\ L;

set L = {ack,sm,ms,mr};

• Algunos comandos:– sort Protocol; (* accept,’deliver *)– size Protocol; (* 7 states *) – graph Protocol; – states Protocol;

– eq(Protocol,Service); (* true *)


Grafo de transición

ProtocolService

accept

deliver

accept

deliver

C

B

E

A

D

S´


Análisis del protocoloAnálisis del protocolo

• ¿Son Protocol y Service observablemente equivalentes?

• ¿Son Protocol y Service observablemente equivalentes?


Modelo y análisis del Protocolo CSMA/CDModelo y análisis del Protocolo CSMA/CD

• Caso de estudio tomado de

Parrow, J. Verifying a CSMA/CD-protocol with CCS. Protocol Specification, Testing and Verification VIII, Aggarwal, S. and Sabnam, K. (eds) Elsevier Science (North-Holland) IFIP, 1988.

• Caso de estudio tomado de

Parrow, J. Verifying a CSMA/CD-protocol with CCS. Protocol Specification, Testing and Verification VIII, Aggarwal, S. and Sabnam, K. (eds) Elsevier Science (North-Holland) IFIP, 1988.


GeneralidadesGeneralidades

• Especificación de servicio, capa n: comportamiento de capa, desde la perspectiva de capa n+1– Conjunto de primitivas

• Especificación de protocolo, capa n: conjunto de entidades, detallando el comportamiento e interconexión de cada una

• Verificación: la especificación del protocolo implica la especificación del servicio, capa n

• Especificación de servicio, capa n: comportamiento de capa, desde la perspectiva de capa n+1– Conjunto de primitivas

• Especificación de protocolo, capa n: conjunto de entidades, detallando el comportamiento e interconexión de cada una

• Verificación: la especificación del protocolo implica la especificación del servicio, capa n


Verificación de protocolos: una metodología

Verificación de protocolos: una metodología

• Defina Ln , cada acción corresponde a una primitiva de servicio, capa n. Similarmente, defina L n -1.

• Defina los siguientes agentes:• SSn , especificación de servicio n,

L (SSn ) = L n

• SSn-1 , especificación de servicio n-1,

L (SSn )= L n-1

• PE1, ..., PEk , entidad del protocolo

• Defina Ln , cada acción corresponde a una primitiva de servicio, capa n. Similarmente, defina L n -1.

• Defina los siguientes agentes:• SSn , especificación de servicio n,

L (SSn ) = L n

• SSn-1 , especificación de servicio n-1,

L (SSn )= L n-1

• PE1, ..., PEk , entidad del protocolo


• Pruebe que

•SSn ≈ (PE1 | ... | PEk | SSn -1 ) \ L n-1


El protocolo CSMA/CDEl protocolo CSMA/CD

• Carrier Sense Multiple Access with Collision Detection (ISO 8802/03)– Varios computadores conectados a un medio

compartido– Cada vez que es necesario, una terminal envía

datos al medio. – Si ocurre una colisión, los mensajes se pierden.

Las terminales en disputa esperan un tiempo aleatorio antes de intentar retransmitir.

• Carrier Sense Multiple Access with Collision Detection (ISO 8802/03)– Varios computadores conectados a un medio

compartido– Cada vez que es necesario, una terminal envía

datos al medio. – Si ocurre una colisión, los mensajes se pierden.

Las terminales en disputa esperan un tiempo aleatorio antes de intentar retransmitir.


continúacontinúa

• Estudiamos MAC (medium access control ), que se comunica con LLC (logical link control ) aceptando mensajes que MAC ha de enviar a PLS (physical signalling) repetidamente hasta que éste se entregue intacto

• Estudiamos MAC (medium access control ), que se comunica con LLC (logical link control ) aceptando mensajes que MAC ha de enviar a PLS (physical signalling) repetidamente hasta que éste se entregue intacto


Especificación del servicio(restricción: 2 computadores)

Especificación del servicio(restricción: 2 computadores)

• MAC provee comunicación virtual en dos direcciones– Usa un buffer unidireccional en cada dirección

• En cada buffer pueden haber a lo más dos transmisiones pendientes

• Los buffers comparten un recurso crítico, el canal– NB: Transmisión sólo si se posee el canal

• MAC provee comunicación virtual en dos direcciones– Usa un buffer unidireccional en cada dirección

• En cada buffer pueden haber a lo más dos transmisiones pendientes

• Los buffers comparten un recurso crítico, el canal– NB: Transmisión sólo si se posee el canal


Diseño de la especificación del servicio

B21

S

B12

rec1

rec2

send2

send1

P

P V

V

V

P

SS = (B12 S B21 ) \ {P,V}def


• B12 = send1.B’12

B’12 = p.(send1.rec2.v.B’12 + rec2.v.B12)

• B21 = send2. B’21


• S = p.v.S

• B12 = send1.B’12


• B21 = send2. B’21


• S = p.v.S

Diseño (continúa)Diseño (continúa)

defdef

defdef

defdef

defdef

defdef


Especificación del protocoloEspecificación del protocolo

• Consiste de 2 entidades MAC, MAC1 y MAC2, interconectadas por un medio, M

• El comportamiento de MAC debe formularse en términos de las interacciones con LLC y M – Con LLC, tenemos sendi y reci

– Con M, tenemos transmisión, recepción y detección en las colisiones de mensajes

• Consiste de 2 entidades MAC, MAC1 y MAC2, interconectadas por un medio, M

• El comportamiento de MAC debe formularse en términos de las interacciones con LLC y M – Con LLC, tenemos sendi y reci

– Con M, tenemos transmisión, recepción y detección en las colisiones de mensajes


Diseño de la especificación del protocoloDiseño de la especificación del protocolo

• Eventos:– b: comienza transmisión MAC a medio– e: termina transmisión MAC a medio– br: comienza transmisión medio a MAC– er: termina transmisión medio a MAC– c: notificación a MAC sobre colisión en medio

• Eventos:– b: comienza transmisión MAC a medio– e: termina transmisión MAC a medio– br: comienza transmisión medio a MAC– er: termina transmisión medio a MAC– c: notificación a MAC sobre colisión en medio


c

MACDiseño de ... Protocolo (continúa)

M

b1

e1

b2

e2

c1

c2

br1

er1

br2

er2

b

e

br

er

send rec


• MAC = send.MAC’

+ br. (er.(rec.MAC + send.rec.MAC’)

+ send.er.rec.MAC’)• MAC’ = b.(c.MAC’+ e.MAC)

+ br.er.rec.MAC’• MACi = MAC[ fi ]

• fi = i / , para toda en L (P), i en {1,2}

• MAC = send.MAC’

+ br. (er.(rec.MAC + send.rec.MAC’)

+ send.er.rec.MAC’)• MAC’ = b.(c.MAC’+ e.MAC)

+ br.er.rec.MAC’• MACi = MAC[ fi ]

• fi = i / , para toda en L (P), i en {1,2}


defdef

defdef

defdef

defdef


M = b1.(b2.M’+br2 . (b2.M’+e1.(b2.M’+er2.M)))

+ b2.(b1.M’+br1 . (b1.M’+e2.(b1.M’+er1.M)))

M’ = c1.c2.M + c2 .c1 .M

P = (MAC1 | MAC2 | M )\{bi,bri,ei,eri,ci},

con i en {1,2}

M = b1.(b2.M’+br2 . (b2.M’+e1.(b2.M’+er2.M)))

+ b2.(b1.M’+br1 . (b1.M’+e2.(b1.M’+er1.M)))

M’ = c1.c2.M + c2 .c1 .M

P = (MAC1 | MAC2 | M )\{bi,bri,ei,eri,ci},

con i en {1,2}


defdef

defdef

defdef


AnálisisAnálisis

• P tiene 35 estados• SS tiene 19 estados• P SS

• P tiene 35 estados• SS tiene 19 estados• P SS


ConclusionesConclusiones

• Una gran cantidad de sistemas de comunicación pueden modelarse mediante un conjunto de procesos, cada uno de ellos posee un espacio de estados finito.

• Una gran cantidad de sistemas de comunicación pueden modelarse mediante un conjunto de procesos, cada uno de ellos posee un espacio de estados finito.

comunicación y concurrencia

Documents