Wykład 03 Podstawowe pojęcia inżynierii ruchu


Wymiarowanie łączy w sieciach
telekomunikacyjnych
Podstawowe definicje i pojęcia
Maciej Stasiak, Mariusz Głąbowski
Arkadiusz Wiśniewski, Piotr Zwierzykowski
Strumień zgłoszeń
Wymiarowanie łączy w sieciach telekomunikacyjnych 2
Losowy proces punktowy
Tn
t
" Przykładowe realizacje procesu punktowego
Wymiarowanie łączy w sieciach telekomunikacyjnych 3
Parametry procesu
" 
o intensywność napływających zgłoszeń
" Pk(t)
o prawdopodobieństwo napływu k zgłoszeń w czasie t
" f(t)
o rozkład czasu pomiędzy zgłoszeniami
Wymiarowanie łączy w sieciach telekomunikacyjnych 4
Właściwości poissonowskiego procesu
napływu zgłoszeń
" Stacjonarność
o Intensywność strumienia nie zależy od czasu
o (t)=  =const.
" Bezpamięciowość (niezależność od momentów czasu)
o liczba zgłoszeń napływających w czasie t1 nie zależy od liczby
napływających zgłoszeń w czasie t2
" Pojedynczość
o w danym odcinku czasu może pojawić się tylko jedno
zgłoszenie
Wymiarowanie łączy w sieciach telekomunikacyjnych 5
Brak pamięci
" Funkcja rozkłady czasu pomiędzy kolejnymi
zgłoszeniami ma charakter wykładniczy:
F(t) = P(T < t) = 1- e-lt
" Zakładamy, że rozkład czasu pomiędzy kolejnymi
zgłoszeniami jest równy t. Określmy zatem warunkowe
P(T > t T > t)
prawdopodobieństwo że czas ten jest
mniejszy od .
P(T > t +t ) = P(T > t)P(T >t T > t)
" Tak więc
0
t T
t+t
Wymiarowanie łączy w sieciach telekomunikacyjnych 6
Właściwość braku pamięci
" Biorąc pod uwagę funkcję rozkładu, otrzymujemy
= > t >
e -l ( t +t ) e -l t P (T T t )
>
" Warunkowe prawdopodobieństwo P (T > t T t) może
przyjąć następującą wartość:
P(T >t T > t) = e-lt = P(T >t )
Wymiarowanie łączy w sieciach telekomunikacyjnych 7
Właściwość pojedynczości
" Rozważmy przedział czasu "t 0. Z właściwości
pojedynczości wynika, że prawdopodobieństwo
pojawienia się więcej niż jednego zgłoszenia w czasie "t
Pi >1 (Dt) = q (Dt)
jest bliskie zeru:
o gdzie q(Dt) jest nieskończenie małą wartością w porównaniu do "t
q (Dt)
lim = 0
Dt0
Dt
" Prawdopodobieństwa elementarne:
P1(D t) = l D t +q (D t)
P0(D t) = 1- l D t +q (D t)
Wymiarowanie łączy w sieciach telekomunikacyjnych 8
Parametry strumienia Poissona
" Parametr L(t) w punkcie czasu t jest definiowany jako
współczynnik graniczny:
Prawdopodobieństwo pojawienia się przynajmniej jednego zgłoszenie w czasie Dt+ t
długość przedziału czasu Dt 0:
P1(t + D t) P1(D t) lD t +q (D t)
L(t) = lim = lim = lim = l
Dt0 Dt0 Dt0
D t D t D t
Wymiarowanie łączy w sieciach telekomunikacyjnych 9
Właściwości strumienia Poissona
" Prawdopodobieństwo pojawianie się k zgłoszeń w czasie t:
(lt)k
Pk (t) = e-lt ,
k!
k
Tn
t
" dla k=0 i k=1 otrzymujemy:
P0(t) = e-lt
P1(t) = lte-lt
Wymiarowanie łączy w sieciach telekomunikacyjnych 10
Właściwości strumienia Poissona
" Rozkład czasu pomiędzy kolejnymi zgłoszeniami:
f (t) = le-lt ,
" Średnia wartość i wariancja czasu pomiędzy zgłoszeniami:
Ą
mT = f (t)dt = 1/l
t
0
Wymiarowanie łączy w sieciach telekomunikacyjnych 11
Operacje na strumieniach
" Dodawanie strumieni Poissona
Stream 1
Strumień 1
Stream 2
Strumień 2
l3 = l1 + l2.
Stream 3
Strumień 3
" Losowe przesiewanie strumieni Poissona
p p p p
Stream 1 l2 = pl1.
Strumień 1
1-p 1-p 1-p 1-p
Wymiarowanie łączy w sieciach telekomunikacyjnych 12
Operacje nas strumieniach
Stream 1
Strumień 1
" Dekompozycja strumienia
T1 T2 T3
Erlanga k-rzędu
Stream 2
T
l(lt)k -1
f (t) = e-lt ,
o rozkład czasu pomiędzy zgłoszeniami
(k -1)!
o średnia wartość czasu
mT = k / l,
pomiędzy zgłoszeniami
2
sT = k / l2,
o Wariancja w/w czasu
Wymiarowanie łączy w sieciach telekomunikacyjnych 13
Definicja procesu Markowa
" Procesem Markowa nazywamy proces losowy, którego
przyszła trajektoria procesu zależy tylko od aktualnego
stanu S(t0) w czasie t0 , ale jest niezależny od sposobu w
jaki ten stan został osiągnięty.
t < t
t > t
0 0
t
t0
past future
przeszłość przyszłość
Wymiarowanie łączy w sieciach telekomunikacyjnych 14
Proces Markowa w systemie M/M/2
" Proces obsługi w systemie M/M/2 (wiązka dwukałowa)
jest procesem Markowa gdy:
o proces napływu zgłoszeń jest procesem Poissona,
o czas obsługi ma charakter wykładniczy.
States
2
1
time
0
Trajektoria procesu obsługi w systemie M/M/2
Wymiarowanie łączy w sieciach telekomunikacyjnych 15
Proces obsługi
Wymiarowanie łączy w sieciach telekomunikacyjnych 16
Trajektoria procesu Markowa
Wymiarowanie łączy w sieciach telekomunikacyjnych 17
Wykładniczy czas obsługi
" Funkcja rozkładu:
F(t) = P(T < t) = 1- e-mt
" Funkcja gęstości:
dF(t)
f (t) = = me-mt
dt
" Wartość średnia i wariancja:
Ą
h = f (t)dt =1/m
t
0
Ą
2 2
s =
h
t f (t)dt-h2 =1/m2
0
Wymiarowanie łączy w sieciach telekomunikacyjnych 18
Strumień obsługi
" W czasie t występuje zajęcie k stanowisk obsługi.
Prawdopodobieństwo zakończenia obsługi i stanowisk
obsługi w przedziale czasu "t może być wyznaczone na
podstawie rozkładu Bernoulliego dla i pomyślnych
zdarzeń, gdy całkowita liczba zgłoszeń jest równa k:
k
ć
Pi (k, D t) = Pi (1- P )k -i

i
Ł ł
" Prawdopodobieństwo zakończenia obsługi w jednym
stanowisku obsługi w przedziale czasu "t :
P = F(Dt) = P(T < Dt) =1- e-mDt
Wymiarowanie łączy w sieciach telekomunikacyjnych 19
Strumień obsługi
" Dla i=0 otrzymujemy prawdopodobieństwo zdarzenia, że w
przedziale czasu "t, nie nastąpiło zakończenie obsługi
żadnego spośród k zajętych stanowisk obsługi:
P0(k, D t) = e-km D t
" Prawdopodobieństwo zakończenia obsługi chociaż przez
jedno stanowisku obsługi:
P1(D t) =1- P0(k, D t) =1- e-km D t
" P1 ("t ) dekompozycja (w seriach):
Ą
j j
P1
p1(D t) = 1- e-km D t = 1-
(-1) (km D t) 1 = km D t +q(D t)
j!
j =0

q
( D t ) ł
" Parametry strumieni obsługi:
N
(t ) = Dlim ęk m +
ś = k m
t 0
D
t

Wymiarowanie łączy w sieciach telekomunikacyjnych 20
Proces Markowa
Wymiarowanie łączy w sieciach telekomunikacyjnych 21
Proces urodzin i śmierci
w systemie M/M/2
" stan 0 wszystkie kanały są wolne
" stan 1 jeden kanał jest zajęty
" stan 2 dwa kanały są zajęte
stan blokady
l
l
1
0
1 2
m
m
2
Wymiarowanie łączy w sieciach telekomunikacyjnych 22
Proces urodzin i śmierci
w systemie M/M/2
l l
1
0
1 2
m
m
2
" nieskończona liczba zródeł ruchu
" skończona liczba zajętych stanowisk obsługi
Wymiarowanie łączy w sieciach telekomunikacyjnych 23
Równania Kołmogorowa
lDt
0
1
1- lDt
mDt
" Określenie prawdopodobieństwa P0(t + "t)
" Wydarzenia w czasie przedziału "t:
o proces był w stanie "0" i został przeniesiony do stanu "1":  "t
o proces był w stanie "0" i pozostał w stanie "0": 1-  "t
o proces był w stanie "1" i został przeniesiony do stanu "0": ź "t
Wymiarowanie łączy w sieciach telekomunikacyjnych 24
Równania Kołmogorowa
lDt
0 1
1- lDt
mDt
był w stanie "0" i pozostał w stanie "0" był w stanie "1" i przeszedł do stanu "0"
P0(t + Dt) = P0(t) [1- lDt]+ P1(t) mDt,
P0(t + Dt) - P0(t)
= -lP0(t) + mP1(t),
Dt
dP0(t)
= -lP0(t) + mP1(t).
dt
Wymiarowanie łączy w sieciach telekomunikacyjnych 25
Równania Kołmogorowa
Wymiarowanie łączy w sieciach telekomunikacyjnych 26
Równania Kołmogorowa
" Rozwiązanie:
1
P (t)
0
0.6
0.4
P (t)
1
0.2
P (t)
2
0 1 2 t
Rozwiązanie równań Kołmogorowa w systemie M/M/2/0 dla =ź=1, P0(0)=1
Wymiarowanie łączy w sieciach telekomunikacyjnych 27
Rozkład
W stacjonarnym stanie procesu prawdopodobieństwa
nie są zależne od czasu
dPi (t)
[ ]
pi V = lim Pi (t) = 0

dt
Obliczenie
prawdopodobieństwa: Rozwiązanie
- l [p0] + m [p1] = 0,

2 2
(l / m)i

l [p0] - (l + m) [p1] + 2m [p2] = 0,

2 2 2
i!
[pi] = .

2
l [p1] - 2m [p2] = 0,
(l / m)1 (l / m)2
2 2

1+ +

[p0] +[p1] +[p2] =1. 1! 2!
2 2 2
Wymiarowanie łączy w sieciach telekomunikacyjnych 28
Stan stacjonarny
a) b)
l
l
l
0 1 2
2m
m
" Interpretacja prawdopodobieństwa [Pi]V:
" Prawdopodobieństwo stanu jest interpretowane jako
część czasu jaką system pozostaje w stanie i:
time spent in state i
Pi = limtimeĄ
observatio
n
observation time
Wymiarowanie łączy w sieciach telekomunikacyjnych 29
Wartość strumienia w stanie i
li = l P
i
l
Pi
t Ą
Wartość strumienia w stanie i dla:
time spent in statei
li = stream intensity = l Pi
observation time
Wymiarowanie łączy w sieciach telekomunikacyjnych 30
Równania stanu dla systemu M/M/2
a) b)
l
l
l
0 1 2
2m
m
" Dla systemu M/2/0
równania stanu przyjmują następującą formę:
- l [p0] + m [p1] = 0,

2 2

l [p0] - (l + m) [p1] + 2m [p2] = 0,

2 2 2

l [p1] - 2m [p2] = 0,
2 2


[p0] +[p1] +[p2] =1.
2 2 2
W stanie i:
suma wchodzących strumieni = suma wychodzących strumieni
Wymiarowanie łączy w sieciach telekomunikacyjnych 31
Uogólniony proces urodzin i śmierci
" Diagram przejść
l l l
l l l
0 1 2
i -1 i i +1
i i+1
0 1 2
l
m m
m
m m
m
1 3
2
i i +1 i +2
l0[p0] = m1[p1] ,

V V
- l0[p0] + m1[p1] = 0,

V V

l1[p1] = m2[p2] ,

V V

l0[p0] - (l1 + m1)[p1] + m2[p2] = 0,
V V V


L,


L,

li
[pi] = mi+1[pi+1] ,
więc:
V V
li-1

[pi-1] - (li + mi )[pi] + mi+1[pi+1] = 0,
V V V
L,


L,


[p ] = 1.
i
V


[p ] =1.
i
V ił0

ił0
Wymiarowanie łączy w sieciach telekomunikacyjnych 32
Lokalne równania równowagi
" Strumienia pomiędzy stanami sąsiednimi są w
równowadze
l
i
li[pi] = mi+1[pi+1]
V V
i i+1
m
i+1
" Rozwiązanie procesu
k
l0l1Llk -1
i-1
[pk] = [p0] = = Ck[p0]
V l [p0]V V
V
m1m2Lmk mi
i=1
[p0] = 1/
gdzie:
C
k
V
kł0
Wymiarowanie łączy w sieciach telekomunikacyjnych 33
Lokalne równania równowagi
dla M/M/2
a) b)
l [p0] = m [p1] ,

l
l
2 2
l
l
0 1 2
[p1] = 2m [p2] ,

2 2 2m
m

[p0] +[p1] +[p2] =1
2 2 2

l
[p1] = [p0] ,

2 2
1
m

[p0] =
2
l l l l l ł

[p2] = [p0] ,

2 2 ę1+ + 2m m ś
m
2m m



l l l ł
[p0] =1
2 ę1+ + 2m m ś

m


Wymiarowanie łączy w sieciach telekomunikacyjnych 34
Koncepcja ruchu
Wymiarowanie łączy w sieciach telekomunikacyjnych 35
Ruch w telekomunikacji
" Ruch jako proces zajętości jednostek alokacji
T
Avol(T ) =
n(t) dt
0
gdzie n(t)  liczba zajętych jednostek w czasie T
" Jednostki:
o 1 SM (speech-minutes)
o 1 Eh (Erlang-hour)
o 1 Eh = 60 SM
Wymiarowanie łączy w sieciach telekomunikacyjnych 36
Natężenie ruchu
T
" Natężenie ruchu:
n(t)dt
0
A =
T
o gdzie n(t)  liczba zajętych jednostek w czasie T
" Jednostki: 1 Erlang ( 1 Erl.)
o 1 Erlang = 1 zgłoszenie obsługiwane przez czas t gdy czas
obserwacji wynosi t
Wymiarowanie łączy w sieciach telekomunikacyjnych 37
Pojęcie natężenia ruchu
czas obsługi
czas obsługi
czas obsługi
t1 t2 t3
T
T T
Avol(T )=
Zajętość zasobów w czasie T:
n(t)dt = 1(t)dt = t1 + t2 + t3
0 0
Avol(T ) t1 + t2 + t3
=
Natężenie ruchu : A =
T T
Wymiarowanie łączy w sieciach telekomunikacyjnych 38
Natężenie ruchu
service time
service time
service time
t1 t2
t3
T
busy time idle time
t1 t2
t3
T
% of idle time
% of busy time
T=100% =time unit
t1 + t2 + t3 tbusy fraction of time unit occupancy
A = = =
T T time unit
Wymiarowanie łączy w sieciach telekomunikacyjnych 39
Natężenie ruchu
" Parameters:
o V=4  liczba kanałów,
o N=5  liczba okresów obserwacji,
o tobs=5T  rozważany okres,
o ti,j - zajętość j-tego kanału w i-tym
przedziale czasu
o l - intensywność strumienia zgłoszeń
o h - średni czas obsługi.
Wymiarowanie łączy w sieciach telekomunikacyjnych 40
Natężenie ruchu Def. 1
" Natężenie ruchu jest równe średniej liczbie
równocześnie zajętych kanałów w czasie okresu
obserwacji.
N V
2 +
A(Def .1) =
t / tobs. = (4 +1+ 5T 2 +1)T = 2Erl.
i, j
i=1 j=1
t
0 1T 2T 3T 4T 5T
Wymiarowanie łączy w sieciach telekomunikacyjnych 41
Natężenie ruchu Def. 2
" Natężenie ruchu jest równe stosunkowi sumy zajętych
kanałów w czasie obserwacji do czasu obserwacji.
N V
A(Def .2) =
t / tobs. = (3+ 2 + 2 + 3)T = 2Erl.
i, j
5T
i=1 j=1
t
0 1T 2T 3T 4T 5T
Wymiarowanie łączy w sieciach telekomunikacyjnych 42
Natężenie ruchu Def. 3
" Jest iloczynem średniej liczby
o zgłoszeń (ruch oferowany)
o połączeń (ruch obsługiwany)
" Na jednostkę czasu i średni czas trwania połączenia.
8 10T
ć ć
A(Def .3) = ch = = 2Erl.

5T 8
Ł łŁ ł
t
0 1T 2T 3T 4T 5T
Wymiarowanie łączy w sieciach telekomunikacyjnych 43
Natężenie ruchu Def. 4
Średnia liczba zgłoszeń (połączeń) na średni czas obsługi
ruch oferowany ruch załatwiany
8 10T
ć ć
A(Def .4) = ls = = 2 Erl.

5T 8
Ł łŁ ł
t
0 1T 2T 3T 4T 5T
Wymiarowanie łączy w sieciach telekomunikacyjnych 44
Rodzaje ruchu
Y
A
System
Ruch załatwiany
Ruch oferowany
Ruch oferowany System Ruch obsłużony
telekomunikacyjny
Ruch odrzucony
Ruch tracony
A
A = Y + A'
Uwaga!
Zwykle pod pojęciem ruchu rozumiemy natężenie ruchu.
Wymiarowanie łączy w sieciach telekomunikacyjnych 45
Rodzaje ruchu
" Ruch załatwiany
o ruch obsługiwany przez wiązkę w czasie T
" Ruch oferowany
o Ruch który powinien zostać przeniesiony jeśli żadne zgłoszenia nie
zostałyby odrzucone z powodu braku pojemności, tzn.
nieograniczona liczba stanowisk obsługi. Ruch oferowany jest
wartością teoretyczną i nie można go zmierzyć.
" Ruch tracony
o różnica pomiędzy ruchem oferowanym i załatwianym
Wymiarowanie łączy w sieciach telekomunikacyjnych 46
Jakość usług w systemach
telekomunikacyjnych
Wymiarowanie łączy w sieciach telekomunikacyjnych 47
Poziom pakietów i zgłoszeń w sieci
Wymiarowanie łączy w sieciach telekomunikacyjnych 48
Koncepcja blokady
" Prawdopodobieństwem strat zgłoszeń B(t1, t2 ) w czasie
(t1, t2) jest stosunkiem zgłoszeń odrzuconych z powodu
blokady (brak pojemności) Nlost(t1, t2 ) do wszystkich
zgłoszeń oferowanych systemowi Noffered(t1, t2 )
N ( t1, t2)- N ( t1, t2)
Nlost ( t1, t2)
offered carried
B ( t1, t2) = =
N ( t1, t2) N ( t1, t2)
offered offerd
Wymiarowanie łączy w sieciach telekomunikacyjnych 49
Koncepcja blokady
" Prawdopodobieństwem blokady E(t1, t2 ) w czasie (t1, t2)
jest stosunek czasu Tblocking(t1 , t2) w którym wszystkie
stanowiska obsługi były zajęte do całkowitego czasu
obserwacji T(t1, t2)
Tblocking(t1,t2)
E(t1,t2) =
T (t1,t2)
Wymiarowanie łączy w sieciach telekomunikacyjnych 50
Podstawowe pojęcia i parametry
" Pojemność ruchowa systemu
o Wartość ruchu oferowanego, który może zostać obsłużony przy
założonej wartości prawdopodobieństw blokady
" Obciążenie
o wartość ruchu przenoszonego przez system
" Blokada
o Stan systemu w którym zgłoszenia pojawiające się na wejściu
systemu nie mogą być obsługiwane z powodu zajętości zasobów
systemu
" Przepustowość
o Prawdopodobieństwo zdarzenia że dane zgłoszenie będzie
obsługiwane w systemie
Wymiarowanie łączy w sieciach telekomunikacyjnychTE 51
Quality of service w systemach telekomunikacyjnych
" Opóznienie pakietu (opóznienie komórki)
o Opóznienie pomiędzy momentem przesłania i odebrania
pakietu (w danym węzle)
" Parametry opóznienia (np. w sieci ATM)
o CDTmean - Mean Cell Transfer Delay  statystyczne średnie
opóznienie pakietu
o CTDmax - Maximum Cell Transfer Delay  maksymalne
opóznienie pakietu, gwarantowane przez sieć z
prawdopodobieństwem 1-ą
o CDVpeak-peak - Peak to Peak Cell Delay Variation 
maksymalne opóznienie zmniejszone przez stałe opóznienie
systemu (tj. opóznienie propagacji. czas przetwarzania w węzle)
Wymiarowanie łączy w sieciach telekomunikacyjnych 52
Jakość obsługi w systemach telekomunikacyjnych (QoS)
" Interpretacja parametrów opóznienia
1-ą ą= loss ratio
delay
constant
max delay variation
max delay
Wymiarowanie łączy w sieciach telekomunikacyjnych 53
Delay distribution
Powody występowania
opóznienia w sieci
" Stałe i niezależne opóznienie sieci
o czas propagacji w łączu fizycznym
o czas przetwarzania w węzle sieciowym
o minimalny czas który węzeł oczekuje na potwierdzenie pakietu
o przepływność łącza wyjściowego jest większa od
przepustowości łącza wyjściowego
Wymiarowanie łączy w sieciach telekomunikacyjnych 54
Powody występowania
opóznienia w sieci
" Zależne od obciążenia sieci
o kolejkowanie w buforach
o dyscyplina kolejek,
o priorytety dla danej lasy pakietów,
o mechanizm kształtowania strumienia pakietów,
o rezerwacja zasobów dla danej klasy pakietów
server
buffer
incoming stream outgoing stream
Wymiarowanie łączy w sieciach telekomunikacyjnych 55
Rodzaje ruchu na poziomie pakietów
" W większości pakietów sieciowych rodzaje ruchu
związane są z parametrami obsługiwanych usług
" Możemy zawsze wyróżnić następujące strumienie
ruchu
o ruch o stałej przepływności bitowej (Constant bit rate)
o ruch o zmiennej przepływności bitowej (Variable bit rate)
" ruch strumieniowy, stałe parametry transmisji
" ruch adaptacyjny
" ruch elastyczny
Wymiarowanie łączy w sieciach telekomunikacyjnych 56
Wymiarowanie łączy w sieciach
telekomunikacyjnych
Podstawowe definicje i pojęcia
Maciej Stasiak, Mariusz Głąbowski
Arkadiusz Wiśniewski, Piotr Zwierzykowski


Wyszukiwarka

Podobne podstrony:
Wyklad 03 Podstawy Genetyki AI
Podstawowe pojecia w teorii ruchu
47 06 Podstawy inzynierii ruchu
1Komunikowanie o zdrowiu wykład1a podstawowe pojęcia
Podstawowe pojęcia MO wykład
Wyklad 1 Polityka pieniezna podstawowe pojecia
PODSTAWOWE POJĘCIA UŻYWANE W PRAWIE O RUCHU DROGOWYM
Wykład ekonomiczne podstawy
Wykład 2 Środowisko pracy pojęcia i zadania
wyklad 03
Lipidy cz I Wykład z 7 03 2007
Wykład 3 5 03 2013
Inzynieria Ruchu Pytania Egzaminacyjne IV 2009(1)
Drogi i ulice wyklad 03
1 podstawowe pojecia zwiazane z ekologia
469 W02 SKiTI wprowadzenie podstawowe pojecia

więcej podobnych podstron