RETI A COMMUTAZIONE DI CIRCUITO

Prof. Ing. Maurizio Casoni

Dipartimento di Ingegneria “Enzo Ferrari”Università degli Studi di Modena e Reggio Emilia

COMMUTAZIONE DI CIRCUITO: GENERALITÀ

Per realizzare la comunicazione tra due utenti si stabilisce un circuito dedicato a loro uso esclusivo per l’ intera durata dellacomunicazione mediante allocazione statica delle risorseUna volta instaurato, il circuito risulta trasparente agli utentiper i quali sembra di disporre di un collegamento direttoConcepito per il traffico voce analogico può supportare pure quello numerico dati anche se in modo inefficienteSe la topologia di rete non è quella a maglia completa, sidistinguono due tipi principali di dispositivi:– stazioni o terminali di utente (telefono, computer,…)– nodi di commutazione: l’ insieme dei nodi si definisce Rete di

Telecomunicazioni

COMMUTAZIONE DI CIRCUITO: FASI

Ogni comunicazione che si avvale della commutazione di circuito si svolge in 3 fasi:Instaurazione o set-up del circuito: prima della trasmissione dell’ informazione occorre stabilire il circuito tra gli utenti terminali attraverso i nodi della rete mediante segnalazione utente-nodo e nodo-nodo Trasferimento dei dati: i dati transitano sui canali delle linee prestabilite e vengono commutati dai nodiAbbattimento o tear-down del circuito: al termine della comunicazione una delle stazioni mediante segnali di controllo notifica alla rete l’ intenzione di terminare e di rilasciare le risorse dedicate a loro fino a quel punto

CONFIGURAZIONE DI RETE

Una generica rete per telefonia è data da 5 elementi:Terminali di utenteTerminali di utenteNodi di accessoNodi di accesso (LE, Local Exchange, o CO, Central Office): interfacciano gli utenti con altri nodi della rete e fanno da ponte tra la rete di accesso e quella di trasportoNodi di transitoNodi di transito (TE, Transit Exchange): costituiscono la rete di trasportoLinee di utente Linee di utente (subscriber o local loop): collegano l’ utente con il nodo di accesso della reteLinee di giunzioneLinee di giunzione: interconnettono nodi della rete

CONFIGURAZIONE DI RETE

LE

TE

LINEE DI GIUNZIONE

Caratterizzate dalla capacità necessaria per un canale telefonico– segnale numerico PCM: 64 kbit/s

Il ramo che collega due nodi è di solito dato da molteplici giunzioni (fascio di giunzioni)Viene usata in tempi diversi da utenti diversi e può essere impegnata fino al 100% del tempoAnche la linea di utente ha la stessa capacità ma è usata solo da un certo utente

RETI

Reti di accesso– topologia a stella– raccoglie/distribuisce il traffico di utente– comprende solo linee di utente

Reti di trasporto– topologia a maglia completa o incompleta– comprende solo linee di giunzione– struttura gerarchica a 5 livelli

nodo di livello più basso ha copertura geografica meno estesa ma più capillare del territorio

GERARCHIA DEI NODI

Nord America Europa ITU-T

Classe 1 Regional center Quaternary center

Classe 2 Sectional center Ternary center

Classe 3 Primary center Secondary center

Classe 4 Toll center Primary center

Classe 5 End office Local exchange

NODO DI ACCESSO

Selettore di lineaSelettore di linea:– concentrazione delle chiamate ricevute dagli utenti locali– espansione delle chiamate ricevute e dirette ad utenti locali

Selettore di gruppoSelettore di gruppo:– distribuzione delle chiamate entranti-uscenti mediante connessione di

giunzioni entranti con giunzioni uscenti

Da altri nodi Verso altri nodi

Selettore Selettore Selettoredi linea di gruppo di linea

NODO DI ACCESSO: FUNZIONE DI CONCENTRAZIONE

Realizza la connessione tra n linee di utente ed m giunzioni con n>mSi mettono a disposizione degli n utenti m giunzioni che consentono fino ad m connessioni contemporanee verso utenti locali o remotiLinee di utente e di giunzione di pari capacità: 64 kbit/sFunzione svolta dal concentratore: capacità totale delle linee di ingresso > di quella delle linee di uscita (n>m)Possibilità che un utente non trovi una giunzione libera al momento della richiesta di una connessione (blocco)Obiettivo: condividere risorse interne della rete in modo da ridurne il costo di installazione ed esercizio per il singolo utenteIl rapporto n/m è il parametro chiave del concentratore: compromesso probabilità di blocco-efficienzaNodo di transito non ha il selettore di linea e quindi non opera la funzione di concentrazione/espansione– ha il solo selettore di gruppo: connette giunzioni di ingresso e uscita

LINEE DI TRASMISSIONE

Servizio telefonico è di tipo full-duplex con uso opportuno di due principali linee di trasmissione:

Linee a due filiLinee a due fili: i segnali nelle due direzioni condividono lo stesso mezzo trasmissivo (doppino in rame)– si usa TDM o FDM– usate nella rete di accesso

Linee a quattro filiLinee a quattro fili: i segnali nelle due direzioni usano coppie distinte– una giunzione è un esempio di linea a quattro fili– usate nella rete di trasporto

FORCHETTADispositivo che interfaccia linee a due fili con linee a quattroSi trova nel nodo di accessoInvia il segnale trasmesso dall’ apparato locale sulla linea uscente e quello ricevuto sulla linea entrante sullo stesso doppino di utenteDispositivo passivo dato da trasformatori: non ideale– parte della potenza del segnale ricevuto sulla linea entrante finisce nella

linea uscente ritornando all’utente remoto producendo un fenomeno di eco– fino a 40 ms tale disturbo è irrilevante, oltre occorre prendere

provvedimenti (soppressore e cancellatore d’eco)

Forchetta ForchettaSegnaled’ eco

SOPPRESSORE E CANCELLATORE D’ECO

Soppressore di ecoSoppressore di eco:– inserisce un’ attenuazione molto alta (35 dB) sulla linea uscente

(entrante) se viene rilevato un segnale sulla linea entrante (uscente) del circuito a quattro fili

– evita che l’ eco giunga all’utente remoto o che sia ricevuto da quello locale

– Problema: se i due parlatori si sovrappongono si perde la prima parte del discorso del nuovo utente perché il tempo di commutazione del dispositivo è di circa 5 msec

Cancellatore di ecoCancellatore di eco:– sottrae algebricamente sulla linea uscente una replica del segnale

ricevuto sulla linea entrante con opportuno ritardo ed attenuazione

RETE TELEFONICA

Si considera l’esempio di TELECOM ITALIAFino agli anni ‘80 era perfettamente rispondente ai 5 livelli ITU-T

Telecom Italia Europa ITU-T

Classe 1 Centro di compartimentonazionale

Quaternary center

Classe 2 Centro dicompartimento

Ternary center

Classe 3 Centro di distretto Secondary center

Classe 4 Centro di settore Primary center

Classe 5 Centro di rete urbana Local exchange

RETE TELEFONICACon l’evoluzione verso reti numeriche la gerarchia si è semplificata a quattro livelli:Stadio di gruppo di transitoStadio di gruppo di transito (SGT): rete magliata a livello nazionale e svolge funzioni dei primi due livelli avendo un centro nazionale (CN) per commutare giunzioni attestate all’esteroStadio di gruppo urbanoStadio di gruppo urbano (SGU): serve 60.000-100.000 utenti ed è collegato ad almeno un SGT; per esigenze di traffico gli SGU possono anche essere collegati fra loroStadio di lineaStadio di linea (SL): interfaccia gli utenti ed opera la concentrazione; diversi SL sono connessi a stella ad un SGU

SGT

SGUSL

CN

PIANO DI NUMERAZIONEDefinisce la modalità di assegnazione del numero di utente in funzione della sua posizione geograficaDeve agevolare l’operazione di commutazione da parte dei nodi per l’instaurazione della chiamataUtenti sono raggruppati per aree geografiche e viene assegnato loro una parte uguale iniziale del loro numero telefonico (prefisso Stato o country code, prefisso di distretto)Vi sono due piani di numerazione:– uniforme

tutti i numeri di utente sono di lunghezza costante3 cifre di prefisso e 7 di utente, di cui 3 identificano il nodo di accesso e le altre 4 la linea di utente in quel nodo

– non uniformela lunghezza del numero è variabile e dipende dalla posizione dell’utentenumero di utente al massimo è di 15 cifre diminuito del prefisso dello Stato; dato da due campi di cui il primo è un prefisso (National Destination Code) ed il secondo indica il numero di utente (Subscriber Number); NDC può mancare nel piano di numerazione nazionale e questo avviene in Italia

TECNICHE DI INSTRADAMENTOObiettivo: instradare una chiamata sulla base del numero del chiamatoMolteplicità di percorsi possibili che collegano chiamante-chiamato comporta necessità di adottare in ogni nodo una politica di instradamento:– elenco di tutti i percorsi possibili– stabilirne un ordine

Uso di grafo per rappresentare la topologia della rete– nodo del grafo rappresenta un nodo della rete– ramo del grafo rappresenta un fascio di giunzioni

Queste tecniche si suddividono in:–– tecniche invariantitecniche invarianti–– tecniche dinamichetecniche dinamiche: le decisioni possono cambiare in funzione della misura del

traffico, dell’istante di tempo, ecc.Inoltre, si può operare in due modi per la scelta del percorso:– criteri probabilistici: ad ogni percorso possibile è assegnata una probabilità– trabocco sequenziale: tutti i percorsi sono esplorati in sequenza secondo un certo

ordine e se un percorso è saturo si trabocca nel successivo

INSTRADAMENTO IN RETI GERARCHICHE

Obiettivo: costruzione della tabella di instradamento tra due nodi arbitrariSi assegna un peso ad ogni nodo della rete che si trova ad un livello superiore nella gerarchia rispetto ai nodi origine (O) e destinazione (D), che hanno invece peso zero– si determina il percorso più lungo attraverso la gerarchia tra O e D e si numerano i

nodi da D verso O in modo crescente cominciando da D=0– ad ogni nodo è assegnato il peso 2i-1 dove i è il numero assegnatogli

Il peso di un percorso è dato dalla somma dei pesi dei nodi attraversatiPercorso diretto o di prima scelta: percorso a peso zeroPercorso fondamentale o di ultima scelta: percorso di peso massimoUna chiamata è rigettata se non può essere servita neanche utilizzando il percorso fondamentaleTabella di instradamento può essere costruita ordinando i percorsi in ordine crescente di peso dal percorso diretto a quello fondamentale

INSTRADAMENTO IN RETI GERARCHICHE: ESEMPIO

A F

B E

C D

Relazione Percorso Peso

A-E ADEABEABDEABCEABCDE

14567

B-E BEBDEBCEBCDE

0123

C-D CD 0

C-F CEFCDEF

13

TECNICHE DI INSTRADAMENTO INVARIANTI

Si basano sulla segnalazione tra nodi che può essere di due tipi:Selezione passoSelezione passo--passopasso– ogni nodo della rete realizza un passo della selezione del percorso

corrispondente ad un certo ramo uscente– disponibilità di più percorsi comporta la scansione sequenziale dei rami

uscenti ed userà il primo non saturo– chiamata bloccata se tutti i rami sono già impegnati

Selezione coniugataSelezione coniugata– il nodo di origine seleziona tutto l’instradamento sulla base di una tabella

che riporta tutti i percorsi possibili– tale nodo verifica la disponibilità di giunzioni presso i nodi sul percorso

desiderato interrogandoli sequenzialmente– il controllo della chiamata rimane sempre al nodo origine– Prestazioni superiori a scapito di una maggiore complessità

ad ogni cambiamento topologico TUTTI i nodi devono aggiornare le proprie tabelle

TECNICHE DI INSTRADAMENTO INVARIANTI: ESEMPIO

Rete gerarchica con selezione passo-passo oconiugata

Relazione A-DPercorso Fasci

I 1 5II 3 2III 3 4 5

A

B

D

C

3 1 2 5

4

Si considera il trabocco sequenziale

TECNICHE DI INSTRADAMENTO DINAMICHE

Pensate per far fronte a picchi di traffico, guasti e, in generale, eventi non previsti al momento della progettazione e messa in opera della reteConsentono di adattare il processo di instradamento di una chiamata all’evoluzione della reteGli algoritmi che implementano tali tecniche vanno a modificare le tabelle di instradamentoConsiderando il modo di rilevazione dello stato della rete vi sono due classi principali:– Algoritmi temporali

modificano le tabelle periodicamente in funzione di previsioni di traffico– Algoritmi adattativi

modificano le tabelle in base a misure di traffico

ALGORITMI ADATTATIVI

Si suddividono in tre classi principali:

CentralizzatiCentralizzati– tabelle sono generate da singolo centro di controllo e poi distribuite

agli altri nodi della rete

DistribuitiDistribuiti– tabelle sono generate localmente nei singolo nodi sulla base di

misure di traffico scambiate con i nodi adiacenti

IsolatiIsolati– tabelle generate dai singoli nodi sulla base dei successi ed

insuccessi nell’ instaurazione delle proprie chiamate

ALGORITMO DNHR

Dynamic Non-Hyerarchical Routing (AT&T dal 1984 al 1991)Primo algoritmo dinamico adottato in rete telefonicaAlgoritmo di tipo temporale con tabelle configurate in base a previsioni del traffico in funzione della fascia oraria della giornata e del giorno della settimanaPer ogni destinazione il nodo dispone di una lista ordinata di nodi verso cui tentare l’ instradamento della chiamata

Mattina X Y Z W

Pomeriggio X Z Y W

Sera Y X Z W

Relazione A - B

ALGORITMO DCRDynamic Controlled RoutingImpiegato da Stentor Canada, Bell Canada, Sprint, MCI (1991-1995)Controllo centralizzato che impiega come variabile di decisione la capacitàresidua dei fasci al momento della rilevazione periodica dello stato della reteOgni 10 sec circa il nodo centrale riceve informazioni sullo stato di occupazione dei fasci, elabora le nuove tabelle di instradamento da impiegare nell’intervallo successivo e le trasmette a tutti i nodi della reteConsideriamo una generica relazione di traffico dal nodo i al nodo j

– il percorso di prima scelta è quello diretto, se esiste– N(i,k): numero di giunzioni nel fascio da i a k– x(i,k): numero di giunzioni che si prevedono occupate (o quello ora occupate)– r(i,k): numero di giunzioni che nel fascio da i a k sono riservate per il traffico diretto i-

k (soglia di protezione del traffico diretto)– per instradare il traffico da i a j attraverso un generico nodo k occorre verificare la

disponibilità d(i,k) e d(k,j) di giunzioni sui due fasci in serie per determinare il percorso di seconda scelta e sarà

d(i,k) = max[N(i,k) - x(i,k) - r(i,k), 0]

ALGORITMO DCR (segue)

Essendo un percorso di due passi, la disponibilità da i a j è data da:C(i,k,j) = min [d(i,k) , d(k,j)]

La via di seconda scelta attraverso il generico k viene selezionata in modo aleatorio con probabilità:

in cui Π(i,j) è l’insieme dei nodi di transito per i percorsi a due passi da i a jSi scelgono di più i percorsi con maggior disponibilità e l’aspetto probabilistico riduce gli effetti di previsioni errate

∑Π∈

=

),(

),,(),,(),;(

jin

jniCjkiCjikp

ALGORITMO DCR: ESEMPIO

Ipotesi: N(i,k)=30 e r(i,k)=3 giunzioni su ogni collegamento

C

B

A

D

E

F

4 7

4

15

8

25 3 6

A 2 0 .0 4 B - - C 2 3 0 .4 1 D 1 2 0 .2 1 E - - F 1 9 0 .3 4

Transito C(B,k,E) p(k,B,E)

Numero di giunzioni occupate in ogni fascio

ALGORITMO RTNR

Real Time Network Routing, usato da AT&T dal 1991Algoritmo che ha per prima scelta il fascio diretto e, se saturo, seleziona come seconda scelta quello meno carico tra quelli a due passiAlgoritmo di tipo distribuito– nodi adiacenti si scambiano informazioni sul livello di

utilizzazione dei singoli fasci– si può definire una soglia di fasci occupati, ad esempio 60%, e

trasmettere con singolo bit=0 il superamento o meno (bit=1) di tale soglia

– informazione su N nodi di reca quindi con una stringa di N bitMediante operazioni di AND logico tra stringhe e possibile determinare i nodi da utilizzare per i percorsi migliori

ALGORITMO RTNR: ESEMPIO

C

B

A

D

E

F

4 7

4

15

8

25 3 6

30 giunzioni disponibili su ogni linksoglia=60%=18 giunzioni

Determinare i migliori percorsi a 2 passitra B ed E

A B C D E F A B C D E FB:0 0 1 1 0 1 E: 1 0 1 1 0 1

AND0 0 1 1 0 1

Se, come ulteriore vincolo, si autorizzasse il trasito solo attraverso certi nodi:

1 0 1 0 0 1 AND0 0 1 0 0 1

Conclusione: i percorsi migliori a 2 passi sono attraverso i nodi C e F

ALGORITMO DAR

Dynamic Alternative Routing, usato da BT e NorwegianTelecom nel 1996Algoritmo di tipo isolato da parte di ogni singolo nodoPercorso di prima scelta è sempre il fascio diretto mentre quello di seconda scelta è sempre a due passi e coincide con quello scelto per la chiamata precedente per gli stessi nodi origine e destinazioneNel caso in cui quest’ ultimo è bloccato, si sceglie aleatoriamente un nuovo percorso a due passi che sostituisce il precedenteAlgoritmo che combina l’instradamento a trabocco con quello a ripartizione di carico

RIEPILOGO

Dinamica Algoritmo Elaborazione instradamento

Variabile decisionale

Frequenza

Temporale DNHR Centralizzata Capacità Residua fasci

Ore/giorni

Adattativa DCR Centralizzata Capacità Residua fasci

10 sec

RTNR Distribuita Capacità Residua fasci

Di chiamata

DAR Isolata Insuccesso chiamata

precedente

Di chiamata