Network Technologies

C

alla piena capacità del link C > ). Supponiamo che un router debba multiplare su un link

m

di capacità C [bit/s] degli m flussi indipendenti di POISSON. Per semplicità supponiamo che

le velocità di arrivo siano λ, il che significa che arrivano λ pacchetti in media per unità di

tempo. m flussi. Supponiamo che le lunghezze dei pacchetti associate ai vari flussi siano v.a.

indipendenti i.d. memoryless. L bit. PDF esponenziale con valore medio di L bit.

• CASO 1 (TDM ): Supponiamo che quel multiplatore adotti una FDM od una TDM. La

C

capacità massima è ( ). Supponiamo di non considerare il ritardo di elaborazione. Con

m

{T }

una DM, F DM le risorse di trasmissione sarebbero allocate agli m flussi (m processi di

⇐⇒

POISSON indipendenti). Supponiamo il buffer di dimensione illimitata ( d = +∞).

Buffer molto grande in modo tale che non rappresenti un collo di bottiglia. Il

M/M/1. L

tempo medio di trasmissione di un pacchetto è: . Sarebbe il valore medio del tempo

(C/m)

di trasmissione. Il parametro della relativa PDF del tempo di servizio sarebbe quindi:

C {λ,

µ = . Per il singolo flusso potrei adottare un sistema a coda M/M/1 con µ} come

mL ¯ 1

parametri, ma ne devo considerare m di questi sottosistemi. Quindi abbiamo T = .

1 µ−λ

• CASO 2 (TDM statistico): Pensiamo all’altra possibilità (TDM statistica). Utilizzo

L

tutta la capacità del link, quindi =⇒ è il tempo medio di trasmissione di un pacchetto.

C

C L 1

Il reciproco, è invece la velocità del router. = . Abbiamo quindi un SERVITORE

L C mµ

a velocità mµ. Si immagini di fare il POOLING, il parametro risultante sarà dato dalla

somma di parametri. I clienti arrivano secondo un processo di POISSON (parametro dato

{mλ,

dalla somma dei parametri), quindi abbiamo parametri mµ}. Il ritardo medio è

quindi: 1 1

T̄ = =

2 − −

mµ mλ m(µ λ)

praticamente m volte inferiore a quello utilizzato da una TDM/FDM.

Exercise

The network of a small company has been designed according to a Hub-and-Spoke hierar-

chical topology (see figure below). The LAN in each branch office is connected to the main

office via a router and a link with capacity C equal to 128 Kbps (1 Kbit = 1000 bits). In one of

the sites the outgoing traffic flow has been mainly generated by CAD applications up to now.

With regard to that traffic, which can be modeled by a Poisson process with rate λ = 3 pkt/s,

0

it is required that the queuing delay in the router (for the queued packets) is less than 0.5s

with probability greater than 0.99. Following a new configuration of the business processes, it

is necessary to install a number of computers for office automation. It is expected that each

of them generates a flow of packets towards the central office at an average rate λ = 1 pkt/s.

For the latter flow, it is required that the average time spent in the router is less than or equal

to 1s. Packet sizes can be modeled by independent random variables which are exponentially

distributed with a mean value D = 500 bytes. 45

• 1) Assume that the output queue of the router has an infinite size and is shared by all the

traffic flows according to the FCFS policy. Determine the maximum number M of new

computers that can be installed;

• 2) Considering the above value M , evaluate the packet loss probability in case the output

queue size is limited to 10 packets.

Figura 2.1: Connection to the Main Office

”È stata progettata una rete di una piccola compagnia con una topologia gerarchica Hub-

And-Spoke. La LAN in ogni ufficio secondario è connessa all’ufficio principale tramite un router

ed un link con capacità C = 128 Kbps. Dove (1 Kbit = 1000 bits). In uno dei siti il flusso del

traffico in uscita è generato principalmente da applicazioni CAD fino ad adesso. Per quel traffico,

che può essere modellato come un processo di Poisson con rate λ = 3 pkt/s, è richiesto che il

0

queueing delay nel router (per i pacchetti in coda) sia meno di 0.5 secondi con probabilità più

grande di 0.99. A seguito di una nuova configurazione dei processi di business, è anche necessario

installare un numero di computer per l’automazione degi uffici. Ci si aspetta che ognuno di loro

generi un flusso di pacchetti verso l’ufficio centrale ad un average rate di λ = 1 pkt/s. Per

quest’ultimo flusso, è richiesto che l’average time speso nel router sia minore od uguale ad 1s.

Le dimensioni dei pacchetti possono essere modellate da variabili casuali indipendenti che

sono esponenzialmente distribuite con valore medio D = 500bytes.

• Si assuma che la coda di output del router abbia capacità infinita e sia condivisa da tutti

i flussi di traffico secondo disciplina di coda FCFS. Si determini il massimo numero M di

nuovi computer che possono essere installati;

• Considerando il valore M , si valuti la packet loss probability nel caso la dimensione della

coda di output sia limitata a 10 pacchetti.

46

Abbiamo una topologia Hub-And-Spoke. (centro-e-raggi, topologia stellare). C = 128 Kbps.

∧

Dove (1 Kbit = 1000 bits) =⇒ C = 128000 bit/s. λ = 3 pkt/s λ = 1 pkt/s. Si richiede

o

che il ritardo di accodamento nel router sia minore di 0.5s con probabilità maggiore di 0.99. Le

lunghezze dei pacchetti sono distribuite esponenzialmente di media 500 bytes. Politica FCFS.

Quanto è il numero massimo di computer installabili M ?

Supponiamo di indicare con W la v.a. che rappresenta il ritardo di accodamento; il vincolo

è il seguente, con (τ = 0.5s), s = threshold = 0.99:

|

Pr{W < (τ = 0.5s) si f accia coda} > (0.99 = s) ≤

Indichiamo con R̄ il ritardo di accodamento per l’ultimo flusso. Deve valere: R̄ 1s.

Cerchiamo di risolvere il sistema con M/M/1. Abbiamo già delle ipotesi, ma dovremo farne di

aggiuntive. Modelliamo quindi il router con un sistema a coda M/M/1:

Abbiamo un buffer output, ed un trasmettitore collegato in serie che è associato al link di

uscita. Ipotesi: flusso secondo il quale arrivano i pacchetti di POISSON (pacchetti applicazioni

CAD). Stiamo trascurando il ritardo di elaborazione router. Capacità di elaborazione talmente

elevata da ritenersi trascurabile (NO BOTTLENECK). Inoltre: (d = +∞). Il router opera con

FCFS (quella contemplata dal sistema a coda M/M/1). Ipotesi aggiuntiva: certo numero di

flussi, M riguardanti i computer dell’Office Automation. Processo degli arrivi di POISSON.

Ipotesi di indipendenza abbastanza scontata, dal momento che i vari utenti non si influenze-

ranno a vicenda. M λ. Ipotesi aggiuntiva: supponiamo che gli arrivi dei pacchetti relativi ai

computer Office Automation siano indipendenti da quelli delle applicazioni CAD. Effettuando

il POOLING, abbiamo che la distribuzione risultante è sempre un processo di POISSON con

0 0

parametro dato dalla somma dei parametri: λ = λ + M λ. Quindi λ è la velocità di arrivo

0

dei clienti nel sistema a coda, µ è la velocità di servizio del router, ovvero il numero medio di

pacchetti elaborati dal router per unità di tempo quando il router è costantemente occupato.

Abbiamo dei tempi di servizio indipendenti, identicamente distribuiti ed indipendenti dai tempi

di interarrivo. Nel sistema i tempi di servizio corrispondono ai tempi di trasmissione. Questo

tempo di servizio è legato al parametro (valore medio) D della distribuzione esponenziale che

caratterizza la lunghezza dei pacchetti. Quindi abbiamo che il tempo medio di trasmissione è

1 D C 1

= [s], ed abbiamo quindi µ = = = 32 [pkt/s], ovvero abbiamo 32 pacchetti in media

µ C D D/C

quando il router è costantemente occupato.

• Parte 1

Tutte le ipotesi del sistema a coda M/M/1 sono rispettate. Possiamo quindi utilizzarne

0

{λ

i risultati: , µ}. Dobbiamo andare ad imporre quelle due condizioni. Per un M/M/1,

1

il ritardo per cliente è R̄ = . Il ritardo per cliente è una v.a. distribuita esponen-

(µ−λ)

⇐⇒ ∼ −

zialmente [R EXP (µ λ)]. Guardando adesso all’altra condizione, si dimostra

che: −µ(1−ρ)y

≤ − ≥

[F (y) = Pr{W y} = 1 ρ e , y 0]

W

Tale è la CDF del Ritardo del cliente nella CODA! (Nella sola coda). W sarebbe il tempo

di permanenza del cliente nella SOLA coda del sistema a coda M/M/1. Distribuzione

valutata su tutti i clienti (anche per quelli che non ci interessano). Dobbiamo condizionarla

≤ −

al fatto che si faccia coda. Quando (y = 0), esce Pr{W 0} = (1 ρ). Ovvero

−

la probabilità che il tempo di permanenza in fila di attesa sia nullo è pari a (1 ρ).

−

Pr{W = 0} = 1 ρ. Si tratta di una v.a. mista. ρ è il fattore di utilizzazione del router.

0 (a)

λ −

Nel sistema a coda M/M/1, ρ = ( ). Nell’M/M/1, (1 ρ) = π , ovvero la frazione di

0

µ 47

tempo a regime nel quale nel sistema a coda non vi sono clienti. La probabilità che il

tempo di permanenza sia nullo è PARI alla probabilità che all’arrivo la fila di attesa SIA

VUOTA! −

[Pr{W = 0} = 1 ρ = π ]

0

Questa è pari alla probabilità che un cliente AL SUO ARRIVO vada subito al router. In

(a) 6

generale: π = π , laddove il primo membro della disuguaglianza riflette la visione dei

i

i

clienti all’arrivo, valutata solo sugli istanti di arrivo, mentre il secondo membro riflette la

visione all’esterno del sistema, considerando tutto l’asse temporale. π , ponendo l’ERGO-

i (a)

DICITÀ, rappresenta la frazione di tempo nel quale vi sono i clienti a regime. Mentre π i

è la probabilità calcolata valutando SOLTANTO GLI ISTANTI DI ARRIVO! Frazione

degli ARRIVI che trovano il sistema (a regime) nello stato i. Infatti potremmo avere ad

(0) (0) (0)

23

1

{{π } ∧ {π

esempio: = , π = = 1, π = 0, π = 0}}.

1 0 0 1 2

3

Theorem 11. P.A.S.T.A. POISSON ARRIVALS SEE TIME AVERAGES



π = lim Pr{N (t) = i}

i

 t→∞

(a) |

π = lim Pr{N (t) = i un arrivo subito dopo t}

 i t→∞ (a)

Se gli arrivi dei clienti si susseguono con processo di POISSON, abbiamo che: π =

i

∞

P iπ

π , N̄ = i

i i=0

Dove la prima equazione è una quantità calcolata sull’insieme delle realizzazioni. (Media

di insiemi). Ma se vale L’ERGODICITÀ, allora le medie d’insieme coincidono con le medie

TEMPORALI. π rappresenta la frazione del tempo nella quale vi sono a regime i clienti

i

(a)

nel sistema; π rappresenta la frazione dei clienti che, all’arrivo trovano il sistema nello

i

stato i. Coincide con la