Post on 14-Apr-2018
7/30/2019 Reti di Calcolatori - Slide 23
1/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 1/
Reti di Calcolatori
Architetture e Protocolli
Giorgio Ventre
Dipartimento di Informatica e SistemisticaUniversit di Napoli Federico II
7/30/2019 Reti di Calcolatori - Slide 23
2/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 2/
The OSI Reference Model
The Data Link Layer
7/30/2019 Reti di Calcolatori - Slide 23
3/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 3/
The OSI Reference Model: the Data Link Layer
In a LAN, the Data Link Layer is responsible foroffering access to the network to/from the upper
layers
Different technical solutions depending on the type
of service required by the applications
Office automation applications might ask forsimplicity and capillarity, while factory automationneeds performance guarantees in data delivery
7/30/2019 Reti di Calcolatori - Slide 23
4/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 4/
The OSI Reference Model: LAN Architectures
The MAP protocol suite Manifacturing Automation
Protocol Proposed by GM to haveperformance guaranteesin data delivery for
assembly lines Based on a token-passing
mechanism to have
fairness in media access
The TOP protocol suite Technical and Office
Protocol Proposed by Boeing as astandard for officeautomation
Designed for offering wideconnectivity andcommunication to
computers Based on a contentionmechanism
7/30/2019 Reti di Calcolatori - Slide 23
5/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 5/
The OSI Reference Model: LAN Architectures
The IEEE 802 Standard Needed to provide a standard for LAN manifacturers (1980)
Compromise over different technical solutions Offers a common interface to the implementation of upper
layers protocols
802.3 802.4 802.5 802.6
802.1 Bridging
802.2Logical LinkSub-Layer
MACSub-Layer
Physical LinkLayer
DataLinkLayer
802.9
802.10 Security & Privacy
802Overview
&Architecture
802.1Management
7/30/2019 Reti di Calcolatori - Slide 23
6/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 6/
The OSI Reference Model: LAN Architectures
IEEE 802.3 - Ethernet (1983) Bus Topology with contention based access
IEEE 802.4 - Token Bus (1983) Bus Topology with token-passing mechanism
IEEE 802.5 - Token Ring (1984) Ring Topology with token passing mechanism IEEE 802.6 - DQDB (1990)
Standard for Metropolitan Area Network
IEEE 802.9 - New for Isochronous LANs
7/30/2019 Reti di Calcolatori - Slide 23
7/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 7/
The OSI Reference Model: LAN Architectures
The IEEE 802.X Standards have been adoptedor recognized by
National Bureau of Standards International Standard Organisation (ISO) as the
8802.X Standard
European Computer Manifacturer Association
They have inspired other important standards
EIA/TIA 568 for Structured Cabling Systems
7/30/2019 Reti di Calcolatori - Slide 23
8/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 8/
ISO/OSI, IEEE 802, EIA/TIA 568
ApplicazionePresentazione
Sessione
Trasporto
Rete
Data Link
Fisico
6
54
3
21
7
IEEE 802
WAN
EIA/TIA 568 (*)
(*) in futuro ISO/IEC 11801
PA
BX
.
.
.
7/30/2019 Reti di Calcolatori - Slide 23
9/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 9/
IEEE 802.1
IEEE 802.1 lo standard che contiene lespecifiche generali del progetto 802
IEEE 802.1 uno standard composto da molteparti tra cui:
802.1 Part A: Overview and Architecture802.1 Part B: Addressing Internetworking andNetwork Management
802.1 Part D: MAC Bridges
7/30/2019 Reti di Calcolatori - Slide 23
10/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 10/
Il Data Link nelle LAN
Le LAN sono reti di tipo broadcast in cui ognistazione a livello data link riceve i frame inviati
da tutte le altre stazioni Il data link broadcast pu essere realizzato sia
con topologie broadcast quali il bus, sia contopologie punto a punto quali l'anello
I canali trasmissivi sono sufficientemente
affidabili e non necessario in generecorreggere gli errori a questo livello
7/30/2019 Reti di Calcolatori - Slide 23
11/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 11/
I Sottolivelli
Per tener conto delle precedenti peculiarit ilprogetto IEEE 802 ha suddiviso il livello data link
in due sottolivelli:LLC: Logical Link ControlMAC: Media Access Control
7/30/2019 Reti di Calcolatori - Slide 23
12/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 12/
LLC (Logical Link Control)
linterfaccia comune a tutte le LAN verso illivello network.
I servizi e i protocolli di questo sottolivello sonodescritti nello standard IEEE 802.2
7/30/2019 Reti di Calcolatori - Slide 23
13/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 13/
MAC (Media Access Control)
specifico per ogni LAN e risolve il problemadella condivisione del mezzo trasmissivo
Esistono vari tipi di MAC: ad allocazione dicanale fissa o dinamica, deterministici ostatistici, ecc.
7/30/2019 Reti di Calcolatori - Slide 23
14/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 14/
IEEE 802.3 (CSMA/CD)
Topologia: busCablaggio: bus, stellaArbitraggio del canale trasmissivo: tramite
contesa
Tipologia del protocollo: non deterministicoVelocit Trasmissiva: 10 Mb/s
Throughput massimo: 4 Mb/sEvoluzione della rete Ethernet proposta da
Digital, Intel, Xerox (DIX).
7/30/2019 Reti di Calcolatori - Slide 23
15/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 15/
IEEE 802.4 (Token Bus)
Topologia: busCablaggio: busArbitraggio del canale trasmissivo: token Tipologia del protocollo: deterministico
Velocit Trasmissiva: 10 Mb/s Throughput massimo: 8 Mb/s
Standard di rete utilizzato in ambito di fabbricaspecialmente in relazione al MAP(Manufacturing Automation Protocol)
7/30/2019 Reti di Calcolatori - Slide 23
16/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 16/
IEEE 802.5 (Token Ring)
Topologia: anelloCablaggio: stella o doppio anelloArbitraggio del canale trasmissivo: token Tipologia del protocollo: deterministico
Velocit Trasmissiva: 4 o 16 Mb/s Throughput massimo: 3 o 12 Mb/s
Evoluzione della rete Token Ring proposta daIBM in alternativa a Ethernet
7/30/2019 Reti di Calcolatori - Slide 23
17/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 17/
ISO 9314
Topologia: anelloCablaggio: doppio anello o stellaArbitraggio del canale trasmissivo: token Tipologia del protocollo: deterministico
Velocit Trasmissiva: 100 Mb/s Throughput massimo: 80 Mb/s
Primo standard per reti locali concepito peroperare su fibra ottica
(FDDI: Fiber Distributed Data Interface)
7/30/2019 Reti di Calcolatori - Slide 23
18/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 18/
Il pacchetto MAC
I campi principali di un pacchetto a livello MAC
sono:
IndirizzoDestinatario
IndirizzoMittente
DATI FCS
DSAP SSAP LLC-PDU CRC
OTTETTI 6 6 variabile 4
7/30/2019 Reti di Calcolatori - Slide 23
19/99
7/30/2019 Reti di Calcolatori - Slide 23
20/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 20/
Indirizzi MAC
Si compongono di due parti di 3 Byte: I tre byte pi significativi indicano il lotto di indirizziacquistato dal costruttore della scheda, detto
anche vendor code o OUI (Organization UniqueIdentifier). I tre meno significativi sono una numerazione
progressiva decisa dal costruttore
Esempio: una scheda con MAC address 08-00-2b-3c-07-9a una scheda prodotta da Digital inquanto il lotto 08-00-2b stato acquistato daDigital
Sono di tre tipi:Single: indirizzo di una singola stazioneMulticast: indirizzo di un gruppo di stazioniBroadcast: indirizzo di tutte le stazioni
7/30/2019 Reti di Calcolatori - Slide 23
21/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 21/
Indirizzo di Broadcast
Il broadcast un tipo particolare di multicast cheindica tutte le stazioni sulla rete locale
La sua codifica esadecimale ff-ff-ff-ff-ff-ff
7/30/2019 Reti di Calcolatori - Slide 23
22/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 22/
Ricezione
Scheda di Rete Locale
Rete locale
Transceiver
Quando la scheda LAN
deve passare la tramaricevuta alla CPU?
Transceivercable
7/30/2019 Reti di Calcolatori - Slide 23
23/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 23/
Ricezione
Ogni scheda di rete, quando riceve unpacchetto, lo passa ai livelli superiori nei
seguenti casi:Broadcast: sempreSingle: se il DSAP uguale a quello hardware della
scheda (scritto in una ROM) o a quello caricato dasoftware in un apposito buffer
Multicast: se stato abilitato via software
7/30/2019 Reti di Calcolatori - Slide 23
24/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 24/
Indirizzi di Gruppo
Servono tipicamente per scoprire i nodiadiacenti
Esistono due modi diversi di impiego:Solicitation: la stazione che interessata a scoprire
chi offre un dato servizio invia un pacchetto dimulticast allindirizzo di quel servizio. Le stazioni cheoffrono il servizio rispondono alla solicitation
Advertisement: le stazioni che offrono un serviziotrasmettono periodicamente un pacchetto dimulticast per informare di tale offerta tutte le altrestazioni
7/30/2019 Reti di Calcolatori - Slide 23
25/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 25/
Primitive di Servizio
A livello MAC esistono solo tre delle quattroprimitive presenti ai livelli superiori:
Request IndicationConfirm
La Response non usataConfirm viene generata o dal protocollo locale,
come indicazione dell'avvenuta trasmissione, odal protocollo remoto, come indicazionedell'avvenuta ricezione.
7/30/2019 Reti di Calcolatori - Slide 23
26/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 26/
Primitive di Servizio
LLC LAYER MACLAYER
CORRESPONDENTLLC LAYER
MA.DATA.requestMA.DATA.confirm
MA.DATA.request
MA.DATA.indication
MA.DATA.indication
TIMEMA.DATA.confirm
(a)
(b)
(a) usato da 802.3
(b) usato da 802.4, 802.5, FDDI
7/30/2019 Reti di Calcolatori - Slide 23
27/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 27/
LAN Architectures: Medium Access Control
The Medium Access Control Problem Where can we apply the control ?
Distributed Control Centralised Control
How can we enforce the control ?
Sinchronous techniques Asinchronous techniques
Which type of control can we apply ?
Continuous Traffic Bursty Traffic
Are the assumptions still valid today ?
7/30/2019 Reti di Calcolatori - Slide 23
28/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 28/
LAN Architectures: Medium Access Control
Reservation Static or dynamic channel assignment Centralised or distributed control
Suited for continuous traffic Round Robin
Static or dynamic cyclic channel assignment
Centralised or distributed control For bursty and continuous traffic
Contention
Inherently distributed (local) control Dynamic channel assignment Suited for bursty traffic
7/30/2019 Reti di Calcolatori - Slide 23
29/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 29/
LAN Architectures: Medium Access Control
Carrier Sensing Multiple Access (CSMA) Very simple model: multiple stations connected
through a shared media (bus) Random Access Contention
Derived from the ALOHA Protocols Two-state behavior of a system
Thinking
Transmitting Contention is perceived from destruction/garbling of
data on shared media
7/30/2019 Reti di Calcolatori - Slide 23
30/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 30/
LAN Architectures: Medium Access Control
Non persistent If no carrier, transmit
If channel occupied, wait time T=f(Prob) 1-Persistent
If no carrier, transmit
If channel occupied, wait until again free If collision (no ack), wait time T=Random
P-Persistent If no carrier, transmit with probability P If channel occupied, wait until again free
7/30/2019 Reti di Calcolatori - Slide 23
31/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 31/
LAN Architectures: Medium Access Control
CSMA suffers of inefficiency due to the problem ofdetecting collisions
The effective channel bandwidth is then reduced by theexistence of a contention state for the network
The duration of this state is linked to the
Frame dimension Technique used to detect collisions
Frame Frame Frame Frame
Contention Slots Idle Contention Interval
LAN A hi M di A C l
7/30/2019 Reti di Calcolatori - Slide 23
32/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 32/
LAN Architectures: Medium Access Control
CSMA/Collision Detect Collisions are detected by listening over the media
while transmitting a frame If no carrier, transmit If channel occupied, wait until again free
If collision, stop and transmit collision warning Wait for time T=f(Random Backoff)
The problem is now ensuring that
collisions can be detected all the stations can hear the collision warning the duration of the collision state be shortest possible
LAN A hi E h
7/30/2019 Reti di Calcolatori - Slide 23
33/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 33/
LAN Architectures: Ethernet
Ethernet Developed by Xerox PARC (Metcalfe-Boggs) in late
70 with contribution from Intel and DEC High reliability (no critical dependecies on anyone of
the network components)
Low installation and operation costs Distributed control Suited for data (burst) traffic Fits the typical office environment
CSMA/CD
LAN A hit t Eth t
7/30/2019 Reti di Calcolatori - Slide 23
34/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 34/
LAN Architectures: Ethernet
Coding should allowdetection of collision(Manchester)
Frames should be longenough to ensure collisiondetection
A maximum cable length isset to avoid non detectionsdue to attenuation
The longer the frame, the
longer the collision state Binary Exponential Back-Off
to reduce collision congestion
A B
A B
A B
A Bt = 2 T
LAN A hit t Eth t
7/30/2019 Reti di Calcolatori - Slide 23
35/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 35/
LAN Architectures: Ethernet
Preamble
Start of Frame (SFD)
Destination Addr.
Source Addr.
Length
Data
Pad
Frame Check
7 Bytes
1 Byte
6 Bytes
6 Bytes
2 Bytes
< 1518 Bytes
4 Bytes
Operational Parameters Bit Rate 10 Mbps Slot Time 512 Bit/t Interframe gap 9.6 sec
Backoff limit 10 Attempt limit 16 Jam size 32 bits Maximum Frame 1518 bytes
Minimum Frame 512 bytes
The bus topology allowsmulticasting
Destination Addr. is a Group Addr.to be programmed in the stationsbroadcasting
Destination Addr. is 111111
LAN Architectures Ethernet
7/30/2019 Reti di Calcolatori - Slide 23
36/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 36/
LAN Architectures: Ethernet
SIGNALRX ?
CARRIER = ONSYNC & WAIT SFD
START RX
FCS & SIZE?
SEND FRAMEUP
DROP FRAME
N
Y
N
N
Y
DEST_ADD?
Y
WAIT PACKETFORM FRAME
CARRIERON ?
WAIT FRAME GAPTX FRAME
COLLISION?
COMPLETE TXTX = OK
ATTE_MAX = TRUETX = NOK
TX JAMATTE ++
MAX ATTE?
BACKOFF = R(ATT)WAIT BACKOFF
Y
N
Y
N
N
Y
TXAlgorithm
RXAlgorithm
I mezzi trasmissivi IEEE 802 3
7/30/2019 Reti di Calcolatori - Slide 23
37/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 37/
I mezzi trasmissivi IEEE 802.3
Tipo diSegmento
Num Max.di MAU
LunghezzaMassima
Min. velocitdi propagaz.
10Base5
10Base2FOIRL10baseFL10baseFB
10BaseT
100
30222
2
500
185100020002000
100
0.77 c (*)
0.65 c0.66 c0.66 c0.66 c
0.59 c
2165
95050001000010000
565
RitardoMax. (ns)
* : c = 3 x 108 m/s (velocit della luce nel vuoto)
LAN Architectures: Ethernet
7/30/2019 Reti di Calcolatori - Slide 23
38/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 38/
LAN Architectures: Ethernet
How Ethernet performs ? The random-based contention makes impossible to get any
bounds on the transmission delay induced However, a worst case analysis can help us in figuring out
how efficient can be an Ethernet High, constant workload from Kstations
Constant transmission probability p(no Exp. backoff)
If A is the probability that the net is alreadyacquired in a slot, then
A = K p (1 - p)k-1
For p = 1 / Kthen A = A max = (1 - 1/K) k-1
So A tends to 1 if Ktends to infinite
LAN Architectures: Ethernet
7/30/2019 Reti di Calcolatori - Slide 23
39/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 39/
LAN Architectures: Ethernet
The probability a contention is made ofjslots isA (1-A)
j-1
and the mean number of slots per contention isSUMj jA (1-A)
j-1 = 1/A
A slot has duration 2 then mean contention interval wisw =2 /
If Pis the mean frame duration, then we can define theEfficiency Eas
E = P / (P + w) = P / (P +2 / A)
The longer the cable, the longer the contention interval, thesmaller the Efficiency!
LAN Architectures: Token Bus
7/30/2019 Reti di Calcolatori - Slide 23
40/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 40/
LAN Architectures: Token Bus
IEEE 802.4 - Token Bus For automation of assembly lines it is essential to
have deterministic bounds on the worst casetransmission delay Dmax A token passing mechanism over a ring seems a
simple solution, since with N stations and for Tframe transmission time, we haveDmax = NT
However, a ring topology is very sensitive tobreakage and does not fit well an assembly linearchitecture.
LAN Architectures: Token Bus
7/30/2019 Reti di Calcolatori - Slide 23
41/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 41/
LAN Architectures: Token Bus
The solution is to define a ring-based logical topologyover a bus architecture
Each node has a Predecessor and a Successor
A node passes over the token by broadcasting it on thebus where it is taken by its Successor
P = BS = C
P = DS = A
P = AS = E
P = ES = B
P = CS = D
A B C
D E
P = PredecessorS = Successor
LAN Architectures: Token Bus
7/30/2019 Reti di Calcolatori - Slide 23
42/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 42/
LAN Architectures: Token Bus
75 Broadband coax
Bus or Tree structure Transmission:
Modified Basebad
(Carrierband) Broadband
Requires modulation
equipment (sometime inDTE)
MAC
ProtocolFirmware
Mod/Dem& Control
Physical
InterfaceModule
DTE
MAC
Architectural choicesinfluenced by operativeenvironment (factory)
LAN Architectures: Token Bus
7/30/2019 Reti di Calcolatori - Slide 23
43/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 43/
LAN Architectures: Token Bus
As in baseband, carrierbandoccupies all the cablebandwidth (1 - 5 - 10 Mbps)
Signal is modulated phase-coherent frequency shift withno phase change from 1 to 0
2 Frequencies for 1 and 0 + 3frequencies for control
All other frequencies can befiltered out (noise)
Binary 1
Binary 0
1 Bit time
LAN Architectures: Token Bus
7/30/2019 Reti di Calcolatori - Slide 23
44/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 44/
LAN Architectures: Token Bus
A token based MAC is very sensitive to tokencorruption and station faults
The MAC protocol must manage events such as Stations joining or leaving the ring Faulty or powering down stations Corrupted tokens/frames
There is a Tmax maximum
waiting time for DTEsTmax = 2 * (TxD + ProcD) +
LAN Architectures: Token Bus
7/30/2019 Reti di Calcolatori - Slide 23
45/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 45/
Preamble
Start Delimiter (SD)
Destination Addr.
Data
CRCEnd Delimiter
=> 1 Byte
1 Byte
1 Byte
6 Bytes
6 Bytes
< 8191 Bytes
1 Bytes
Frame Control specifies if a framecontains data or control infoIf data, contains priority and ackgrant information
If control, contains message type:Token passingToken claim
(for ring initialization)Solicit successor
(station joining - periodic)Who follows me
(lost token)Resolve contention
(multiple new stations)Set successor
(station informs predec.about leaving)
Source Addr.
Frame Control
4 Bytes
LAN Architectures: Token Bus
7/30/2019 Reti di Calcolatori - Slide 23
46/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 46/
Basic network operation1) Wait for token2) Transmit Nmax frames in queue3) Pass token to successor4) Lissen new traffic
4.1) If valid frames, then my tx was ok4.2) If frames not valid, then there is a problem
4.2.1) Rigenerate new token
4.2.2) If still nothing, my successor is dead4.2.3) Who follows me ?4.2.4) Receive Set successor & Synchronize Net
LAN Architectures: Token Bus
7/30/2019 Reti di Calcolatori - Slide 23
47/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 47/
Priority operation Four Access Classes
Class 6: Urgent Messages, Alarms Class 4: Control and Management Class 2: Routine Operations
Class 0: Low priority (e.g. file transfer, downloading) Transmission regulated by two timers
Token Hold Timer (THT)
Maximum Transmission Time for a Station High-Priority THT (HP-THT)Maximum Transmission Time for Class 6 Packets
LAN Architectures: Token Bus
7/30/2019 Reti di Calcolatori - Slide 23
48/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 48/
When the token is received, the station transmits Class6 packets until HP-THT
Then, if THT has not expired, it is set to a timer calledToken Rotation Timer (TRT) measuring the time
expired since the last token reception
The station starts transmitting lower priority packets
until the difference between THT and a fixed valuecalled Target Token Rotation Time (TTRT) is positive
LAN Architectures: Token Bus
7/30/2019 Reti di Calcolatori - Slide 23
49/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 49/
B
B
B
HP-THT > 0THT > 0
HP-THT = 0THT := TRT
HP-THT = 0
THT = TTRT
TRT = t
TRT = 1
TRT = 2
Token
Class 6
Classes 0-4
LAN Architectures: Token Ring
7/30/2019 Reti di Calcolatori - Slide 23
50/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 50/
IEEE 802.5 Token Ring Standard originated from/compatible with IBM LAN
Based on a ring topology Stations connected through a serial line, not via a
bus
Media Access Control based on a token mechanism Bandwidth achievable 4 - 16 Mbps Star topology possible with concentrators
LAN Architectures: Token Ring
7/30/2019 Reti di Calcolatori - Slide 23
51/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 51/
A
D
C
B
F
A
D
C
B
T
A receivesthe Token
A
D
C
B
F
A tx aFrame to D
Frame returnsto Athrough D andis eliminated
A
D
C
B
T
A releasesthe Token to B Early Token
Release
A
D
C
B
F
A tx aFrame to D andreleases immediatelythe token
F
T
LAN Architectures: Token Ring
7/30/2019 Reti di Calcolatori - Slide 23
52/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 52/
The network media is a 2 pairs shielded cable The signal coding is Differential Manchester
The physical architecture can be a point-to-point ring orthrough a concentrator
MAC
ProtocolFirmware
TrunkCouplingUnit
DTE
MACRTR R RTT T
HUB
Drop Connection
Ring In Ring Out
LAN Architectures: Token Ring
7/30/2019 Reti di Calcolatori - Slide 23
53/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 53/
Since the ring is realised through point-to-point lines,the TCU must guarantee data by-passing when astation is inactive.
When it is not transmitting, a station is inlistening mode - 1 bit copy mechanism
Listening Mode
1 Bit Buffer / Copy Delay
In Out
DTE
Tx Mode
In Out
DTE
To/From Upper Layers
LAN Architectures: Token Ring
7/30/2019 Reti di Calcolatori - Slide 23
54/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 54/
Start Delimiter
Access Control
Destination Addr.
Data
CRC
End Delimiter
1 Byte
1 Byte
1 Byte
6 Bytes
6 Bytes
< 5000 Bytes
1 Bytes
Source Addr.
Frame Control
4 Bytes
Data Frame Format
Start Delimiter
Access Control (AC)
=> 1 Byte
1 Byte
1 ByteEnd Delimiter
Token Frame Format
Frame Status 1 Bytes
Access Control:Token, Monitor, Priority, Reserv.
Frame Control:For ring management
Frame Status:A bit - On, Destination OK
C bit - On, Frame OK
LAN Architectures: Token Ring
7/30/2019 Reti di Calcolatori - Slide 23
55/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 55/
Token Ring has also a priority mechanism: Each token has a priority assigned
When a station receives a token with priority P, itcan only transmit frames with priority F > = P
A station can book a token with a certain priority Mechanisms exists in order to avoid abuses This priority mechanism is not fair as the one
adopted in Token Bus
LAN Architectures: Token Ring
7/30/2019 Reti di Calcolatori - Slide 23
56/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 56/
Each MAC Layer maintains two sets of values: Priorities:
Pm: Max priority among the waiting frames Pr: Priority of the previous token Rr: Reservation contained in the previous token
Stacks: Sr: Stack for the previous Pr Sx: Stack for new priorities P
LAN Architectures: Token Ring
7/30/2019 Reti di Calcolatori - Slide 23
57/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 57/
MAC assignes priority to any tx frame P = Current token priority Pr
R = 0 (to be set by other stations) MAC generates a new token with:
P = Pr, R= Max(Rr,Pm) P constantif there are no more transmittable frames or noreservation request with higher P
P = Max(Rr,Pm), R = 0 P increasesif there are still transmittable frames pending orthere is a reservation request for higher priority
LAN Architectures: Token Ring
7/30/2019 Reti di Calcolatori - Slide 23
58/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 58/
We now need a mechanism to lower the priority:
The station who raises P becames thestacking station, i.e. a station keeping track of P This station will be responsible for
raising the priority for new reservations keeping it the same lowering it, as soon as new reservations ask for lower
priorities
LAN Architectures: Token Ring
7/30/2019 Reti di Calcolatori - Slide 23
59/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 59/
Ring Management - Inizialization When switched on, a station makes a Duplication Address
Test (DAT)
If OK, it send out a Standby Monitor Present (SMP) to informthe immediate downstream station about its existence.
Ring Management - Standby Monitor
Each ring has a monitor station, to check token passing andtransmitting periodic Active Monitor Present (AMP) signals In case there are no AMP, a station can send a Claim Token
(CT) frame to become the monitor (FCFS approach)
LAN Architectures: Token Ring
7/30/2019 Reti di Calcolatori - Slide 23
60/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 60/
Ring Management - Active Monitor When a station becomes the new monitor, it starts a clock
and sends out a Purge (PRG) frame to eliminate tokens and
frames It then sends out a AMP signal to inform the other stations,and creates a new token
The other stations move to a Standby Monitor State
Ring Management - Beaconing When a station receives no AMP or frames in an interval, it
transmits a Beacon (BCN) signal to verify the existence of aconnection
If the signal is not received back from the station, then thering is interrupted somewhere
LAN Architectures: High Speed LANs
7/30/2019 Reti di Calcolatori - Slide 23
61/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 61/
High Speed Lans The Performance Problem -
More stations More applications More usage
More media More capillarity
Demand for More Bandwidth
This must cope with the technological limitations ofsome LAN architectures
LAN Architectures: High Speed LANs
7/30/2019 Reti di Calcolatori - Slide 23
62/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 62/
An example: improving Ethernet performance If Tc is the delay to detect a collision, and Tix the
delay to transmit a frame, whenTc
7/30/2019 Reti di Calcolatori - Slide 23
63/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 63/
Case 1:Tp = 25 sec (Lenght = 2.5 Km)Fs = 10.000 bits (Frame size)
B = 10 Mbps (Bandwidth) Tp / Tix = 25 / 1000
Tc = 50 sec N = Tc x B = 500 (Bits wasted if collision)
Case 2: B = 100 Mbps, N = 5000 Case 3: B = 200 Mbps, N = 10000 (Frame)
CSMA/CD is not suited!
LAN Architectures: High Speed LANs
7/30/2019 Reti di Calcolatori - Slide 23
64/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 64/
FDDI : ISO 9314 Token based MAC
Fibre based (Copper based available - CDDI) Ring 1: Primary Ring Ring 2: Secondary Ring - Backup / Add. Tx
Single Attachment Stations (SAS) Dual Attachment Stations (DAS)
Longer distances - Higher speed
LAN Architectures: High Speed LANs
7/30/2019 Reti di Calcolatori - Slide 23
65/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 65/
M
S
M
S
A B
A
BA
B
Optical CouplingUnit
SAS
DAS
Wiring Concentrator
Media InterfaceConnector
Primary Ring
Secondary Ring
Primary Ring
Master Key
Slave Key
LAN Architectures: High Speed LANs
7/30/2019 Reti di Calcolatori - Slide 23
66/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 66/
FDDI is used as a High-Speed LAN for clustering top-end computing
systems (NOW)
as a High-Speed backbone for LAN interconnection
FDDI
Local Area Network
Bridge
Campus Network
BuildingBackbone
LAN Architectures: High Speed LANs
7/30/2019 Reti di Calcolatori - Slide 23
67/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 67/
Operation Mode At any time, only one ring is active and provides
timing 4B/5B Manchester Coding MAC based on ETR - Token Ring
Priority mechanism similar to Token Bus Isochronous FDDI defined but not standard
based on allocation of time-slots to isochronous
media - Synchronous Allocation Time (SAT)
LAN Architectures: Bridging
7/30/2019 Reti di Calcolatori - Slide 23
68/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 68/
The diffusion of LANs brings in severalproblems:
How to connect multiple LANs with similartechnologies How to divide a single LAN into separate entities
How to connect multiple LANs with differenttechnologies
How to limit and control the traffic flowing from LAN
to LAN (load balancing and security)
LAN Architectures: Bridging
7/30/2019 Reti di Calcolatori - Slide 23
69/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 69/
Backbone LAN
Buiding C
LAN 3
Buiding D
LAN 4
Bridge
Office LAN
ComputerBuiding A
LAN 1 Buiding B
LAN 2
Bridging keeps local all the frames to systems in the sameLAN and propagates only frames for external systems
LAN Architectures: Bridging
7/30/2019 Reti di Calcolatori - Slide 23
70/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 70/
Connecting LAN
Buiding A
LAN 3
BridgeOffice LAN
Computer
Buiding B
LAN 2
Bridging is a solution also for the existing limitationsover the extension of a LAN
2.5 Km
2.5 Km
2.5 Km
LAN Architectures: Bridging
7/30/2019 Reti di Calcolatori - Slide 23
71/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 71/
Backbone LAN
Buiding C
LAN 3
Buiding D
LAN 4
Bridge
Office LAN
ComputerBuiding A
LAN 1 Buiding B
LAN 2
Bridging keeps local all the problems due tofaulty networks or systems
Missing
Terminator
Faulty
Transceiver
Bridging Operation
7/30/2019 Reti di Calcolatori - Slide 23
72/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 72/
NET
LLC
MAC
PHY
NET
LLC
MAC
PHY
PKT
802.3 PKT
802.3 PKT
PKT
PKT
802.3 PKT
802.3 PKT
PKT
PKT
802.4 PKT
802.4 PKT
802.4 PKT
802.4 PKT
CSMA/CD Lan 802.4 Lan
Bridge
Host A Host B
Differences in formats and protocols make bridginga complex task.
Bridging Operation
7/30/2019 Reti di Calcolatori - Slide 23
73/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 73/
A long list of problems Different frames:
translation fragmentation
Different data rates:
buffering timing control from faster to slower
Different MACs
token vs. collision with different efficiency Different maximum frame length
no solution!
Bridging Disadvantages
7/30/2019 Reti di Calcolatori - Slide 23
74/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 74/
Store&Forward behaviour with additional delayintroduced
No flow-control at the MAC sublayer, withpossible buffer overflow when the output LAN isoverloaded
Differences in frame types demand for frameconversion, with possible multiple errors
introduced during frame relaying
Bridging Operation
7/30/2019 Reti di Calcolatori - Slide 23
75/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 75/
802.3 to 802.3: only load differences 802.4 to 802.3
Priority bits missing (bridge lie) Acknowledgement request (bridge lie)
802.5 to 802.3 A&C bits missing (bridge lie) Priority bits (bridge lie)
802.4 to 802.4 Acknowledgement request (bridge lie)
802.5 to 802.4
A&C bits Priority 802.5 to 802.5
A&C bits
Bridging Operation
7/30/2019 Reti di Calcolatori - Slide 23
76/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 76/
Transparent bridgingthe presence of one or multiple bridges is
transparent to the stations Bridges automatically initialize and configure
dynamically with no external intervention A bridge can have two or more bridge ports. In
this last case it is called a multiportbridge.
Bridges operate in promiscuous mode, i.e. theyreceive and buffer all frames received
Bridging Operation
7/30/2019 Reti di Calcolatori - Slide 23
77/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 77/
A bridge includes a MAC chipset with a portmanagement software
MACChipset
MACChipset
MemoryBuffers
PortMngmt
ProtocolEntity
Forw.DataBase
Station
Address
Port
Num.
Port 1 Port 2
Bridge learning
7/30/2019 Reti di Calcolatori - Slide 23
78/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 78/
The Forwarding Data Base (FDB) is formed bydynamic learning and interaction with otherbridges A newly inserted bridge has an empty FDB For each received frame, the source address and
the entry port are stored in the FDB
To ensure delivery, the frame is forwarded over allthe ports (flooding)
The procedure is repeated for each frame from anewsource
OK for static scenarios: no moving stations/links
Bridge learning
7/30/2019 Reti di Calcolatori - Slide 23
79/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 79/
The Inactivity Timer (IT) is a value in the FDB thatrecords the silence time of a source.
When IT > Tmax the entry is removed
In this way the FDB is formed only of active stationsand has a limited size
A spanning tree algorithm is used to evaluate theproper forwarding route in case of multiple paths
In large networks, stations can move and links can
change state so a new spanning tree must be created
Topology Initialization
7/30/2019 Reti di Calcolatori - Slide 23
80/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 80/
Bridges exchange regularly special frames calledBridges Protocol Data Units (BPDU). These frames arenot directly forwarded, but used to produce new
BPDUs Each bridge has an Id and a priority. The root bridge
has the highest priority and smallest Id
A new bridge starts to operate in the rootstate andtransmists over all ports the Configuration BPDUs
Id of the current root (itself initially) Path cost to the root (0 initially) Id of the transmitter Id of the port
Topology Initialization
7/30/2019 Reti di Calcolatori - Slide 23
81/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 81/
When a bridge receives a BPDU it compares the rootPriority and Id with its own values.
If this is the case, the bridge sets the new value for theroot and computes the new cost for the root path
A new Configuration BPDU is formed and forwarded toall the other ports
By knowing the costs to the root for each port, a bridgeis designatedto be its way to the root. It will be the onlyfrowarding bridge in that segment
The Id value is again the tie breaker value
Topology change
7/30/2019 Reti di Calcolatori - Slide 23
82/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 82/
The root bridge will transmit regularly ConfigurationBPDUs. These are processed by the bridges on thepath to inform all other bridges about changes
A Message Age Timer is kept for each port. In case ofa port/link failure, the MAT expires and a procedure isactivated to change topology
Topology Change Notification BPDUs are exchangedto inform the root about port status modifications Exists a procedure also to change the root and the
designated bridge
Il progetto IEEE 802: il sottolivello LLC
7/30/2019 Reti di Calcolatori - Slide 23
83/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 83/
FDDI802.3 802.4 802.5
FDDI
802.2 Logical Link ControlISO 8802.2
802.6
LIVELLONETWORK
LIVELLO
DATA LINK
LIVELLOFISICO
LLC
MAC
CSMA/CD TOKENBUS
TOKENRING
DQDB
Interfaccia unificata con il livello network
Tecnologie trasmissive differenziate
ISO8802.3
ISO8802.4
ISO8802.5
ISO8802.6
ISO9314
(Local and Metropolitan Area Network)
Il sottolivello LLC
7/30/2019 Reti di Calcolatori - Slide 23
84/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 84/
Definisce i protocolli usati per realizzare una opi connessioni logiche su di un singolo mezzofisico
LLC deve essere utilizzabile con uno qualunquedei MAC
PDU del LLC
7/30/2019 Reti di Calcolatori - Slide 23
85/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 85/
DESTINATION
ADDRESS
SOURCE
ADDRESS
CONTROL INFORMATION
1 1 1 o 2 variabileOTTETTI
Il campo control permette lesistenza di tre tipi dipacchetti:
Unnumbered Supervisor Information
7/30/2019 Reti di Calcolatori - Slide 23
86/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 86/
Livello 3
OSI
Livello 3
TCP/IP
Altro
livello 3
Sottolivello MAC
Sottolivello LLC
Scelta basatasu LLC-DSAP
SAP di LLC
7/30/2019 Reti di Calcolatori - Slide 23
87/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 87/
Servono ad indicare quale protocollo di livellosuperiore ha originato il pacchettoSono grandi un Byte
due bit I/G e U riservati64 indirizzi singoli, globali definibili
ff broadcast00 data link layer itself
1 0 1 1 1 1 01
I/G (Individual=0, Group=1)U (Non Universal=0, Universal=1)
SAP LLC Universal
7/30/2019 Reti di Calcolatori - Slide 23
88/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 88/
Gli indirizzi globali sono assegnati dallISO soloper i protocolli progettati da un comitato distandardizzazione
Esempi di SAP-LLC
7/30/2019 Reti di Calcolatori - Slide 23
89/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 89/
La codifica 0FEH indica il protocollo ISO 8473Internet Protocol
La codifica 042H indica il protocollo IEEE802.1D Spanning Tree Configuration La codifica 0AAH indica un pacchetto LLC
speciale detto SNAP
0FEH 0FEH UI
1 1 1 mOTTETTI
DSAP SSAP CONTROL INFO
Servizi LLC
7/30/2019 Reti di Calcolatori - Slide 23
90/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 90/
LLC offre al Livello 3 i seguenti tipi di servizio:Tipo 1: Unacknowledged Connectionless Service
Tipo 2: Connection Oriented ServiceTipo 3: Semireliable Service
LLC Tipo 1
7/30/2019 Reti di Calcolatori - Slide 23
91/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 91/
Unacknowledged Connectionless ServiceServizio non connesso
Non esiste un acknowledge (ACK)Se il messaggio perso o rovinato dai disturbi
non viene fatto nessun tentativo, a questo livello,
di recuperare l'erroreNessuna procedura di controllo di flusso: le
trame non sono numerate La trasmissione pu essere punto-punto,
multipunto o broadcast
Primitive per LLC tipo 1
Q i i LLC l li i hi d
7/30/2019 Reti di Calcolatori - Slide 23
92/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 92/
Questo servizio LLC molto semplice e richiedesolo due primitive:L.DATA.requestL.DATA.indication
USER LLCLAYER
CORRESPONDENTUSER
L.DATA.request
L.DATA.indication
LLC tipo 2
S i i
7/30/2019 Reti di Calcolatori - Slide 23
93/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 93/
Servizio connesso il servizio pi sofisticato che il livello data link
possa offrire al livello networkSorgente e destinazione aprono una connessione
prima di trasferire i dati e la chiudono al termine
I frame sono numerati e il livello 2 garantisce che:ogni frame inviato sia ricevuto correttamenteogni frame sia ricevuto esattamente solo una volta
tutti i frame siano ricevuti nell'ordine correttoEsistono meccanismi di controllo di flusso (flow
control)
Primitive LLC tipo 2
I t i d ll C i
7/30/2019 Reti di Calcolatori - Slide 23
94/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 94/
Instaurazione della Connessione:L.CONNECT.requestL.CONNECT.indicationL.CONNECT.confirm
Trasferimento dei dati:L.DATA_CONNECT.requestL.DATA_CONNECT.indicationL.DATA_CONNECT.confirm
Chiusura della Connessione:L.DISCONNECT.requestL.DISCONNECT.indicationL.DISCONNECT.confirm
LLC tipo 2
R t d ll C i
7/30/2019 Reti di Calcolatori - Slide 23
95/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 95/
Reset della Connessione:L.RESET.request
L.RESET.indicationL.RESET.confirm
Flow control:
L.FLOWCONTROL.requestL.FLOWCONTROL.indication
LLC tipo 2
Il t l l 1 2 B t
7/30/2019 Reti di Calcolatori - Slide 23
96/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 96/
Il campo control pu essere lungo 1 o 2 Byte Il campo control lungo 2 Byte:
I: information il pacchetto di dati. I numeri disequenza sono lunghi 7 bitRR: Receiver Ready un ACK frame quando non
esiste traffico per piggybackingRNR: Receiver Not Ready come RR, ma invita il
trasmettitore a sospendere la trasmissione
REJ: Reject indica un errore di trasmissione. Ilmittente deve ritrasmettere tutti i pacchetti a partireda quello errato
The ultimate winner in the LAN war
7/30/2019 Reti di Calcolatori - Slide 23
97/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 97/
The ultimate winner in the LAN war
7/30/2019 Reti di Calcolatori - Slide 23
98/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 98/
The ultimate winner in the LAN war
7/30/2019 Reti di Calcolatori - Slide 23
99/99
Dipartimento di Informatica e Sistemistica11/05/2007 GV/RC/A&P 99/