基礎から学ぶトラヒック理論 サンプルページ この本の定価 判型などは, 以下の URL からご覧いただけます. このサンプルページの内容は, 初版 1 刷発行時のものです.

Save this PDF as:
 WORD  PNG  TXT  JPG

Size: px
Start display at page:

Download "基礎から学ぶトラヒック理論 サンプルページ この本の定価 判型などは, 以下の URL からご覧いただけます. このサンプルページの内容は, 初版 1 刷発行時のものです."

Transcription

1

2 基礎から学ぶトラヒック理論 サンプルページ この本の定価 判型などは, 以下の URL からご覧いただけます. このサンプルページの内容は, 初版 1 刷発行時のものです.

3

4 i +α

5 ii

6 iii

7 iv M/M/S/S/N M/M/S/S M/M/S M/M/S/K M/M/ M/M/1/K M/G/ A 174 B 176 C 178 D 179 E 182 F 184

8 v G 186 H B 191 I C A α alpha B β beta Γ γ gamma Δ δ delta E ε epsilon Z ζ zeta H η eta Θ θ theta I ι iota K κ kappa Λ λ lambda M μ mu N ν nu Ξ ξ xi O o omicron Π π pi P ρ rho Σ σ sigma T τ tau Υ υ upsilon Φ φ phi X χ chi Ψ ψ psi Ω ω omega

9 vi (A) A nc k n k A c A F c (x) X E[X] X I Im[s] s i L max[x 1,...,x n] x 1,...,x n min[x 1,...,x n] x 1,...,x n N(μ, σ 2 ) μ σ 2 O 0 o(δt) Δt 0 Δt 0 np k n k P (A) A P (A, B) A B P (A B) B A Re[s] s A T A U( ) V [X] X Γ ( ) γ( ) δ( ) φ f ( k) f (k) F ˆP! ω A ω A (a, b) [a, b] (a, b] [a, b) ( ) n k f k f k f p ω A ω A a<x<b a x b a<x b a x<b n k nc k A(0,t] a a c B B S B(0,t] C S D(0,t] H H(t) h(t) h K (0,t] { } { } B (0,t] { } C (0,t] { } { } { } H { } H { } E[H]

10 vii L L q N P p i,j P (t) p i,j (t) Q q i,j q k S t W W (t) w(t) W q W q(t) Wq c(t) Wq c (0) X(t) {X(t)} γ Δt η λ λ k μ μ k π π j π(t) π j (t) ρ { } { } i j P (i, j) t i j t P(t) (i, j) i j Q (i, j) { } { } k { } W W W q Wq t {} k {} { } k { } π j t t j π(t) j 2 A, B F (x) F X (x) X F X,Y (x) X Y F X Y =y (x) Y = y X f(x) f X (x) X f X,Y (x) X Y f X Y =y (x) Y = y X p(x) p X (x) X p X,Y (x) X Y p X Y =y (x) Y = y X S X, Y Ω ω 3 I R T (0,t] (0,t] T c(0,t] (0,t] 4 L L q W n n W W q

11 viii 5 S i i T i,j i j z f i,j (n) i j n P (n) n p i,j (n) X(n) π(n) π j (n) i j n P (n) (i, j) n n n j π(n) j a i 6 i M {X m(t)} m p m m t n n t n t n {Y (t)} λ m 7 m 9 A A n a k C j J L n L(t) R r(t) T t(0,τ] U j Y Y (t) y(t) α n δ n + n k j n t R (0,τ] t j Y Y n n a s b k b S G S ν π S k

12 1 1 traffic congestion A B A B

13 A-B Agner Krarup Erlang 1

14 1 3 traffic theory 3 queueing 1 theory Paul Baran Donald Watts Davies 1 1 queuing queueing

15 Gbps 1 1KB G giga bps bit per second 1

16 trialsample sample space Ω event 2.1 Ω Ω = { } S S = {φ, { }, { }, { }} φ S (1) Ω S (2) A S A c = {ω; ω A} S (3) A S B S A B S

17 6 2 (1) (2) Ω c = φ (A c B c ) c = A B (2.1) (2) (3) A B A B A B A B = φ A B A B exclusive A B 1 B 2 A = { 3, 6 }, B 1 = { 1, 3, 5 }, B 2 = { 2, 4, 6 } A B 1 = { 1, 3, 5, 6 }, A B 1 = { 3 }, A c = { 1, 2, 4, 5 } B 1 B 2 = φ B 1 B 2 Ω A (1) 0 P (A) 1 (2) P (Ω) =1 ( ) (3) A 1,A 2,A 3,... P A i = i i P (A i ) P (A) A probability (1) (3) 2.3 Ω = { } { } { } P (Ω) =P ( ) =P ( )+P( ) =1 { } { } P ( ) =P ( ) = 1 2

18

19 n (n 1) + (n 2) = (n 1)n 2 (3.1) 3.2 switching system

20 switching exchange circuit switching store-and-forward switching

21 Internet LAN Local Area Network PDU Protocol Data Unit protocol 1 3 PDU PDU 2 3 PDU PDU buffer 3.2 router hub 1 PDU 48 3 PDU message packet cell PDU PDU

22 LAN Ethernet ( ) header 6 DA Destination Address 6 SA Source Address 2 PT Protocol Type 3 IP Internet Protocol I Information FCS Frame Check Sequence trailer 3.5 PDU PDU call 1

23 46 3 switching system 3.6 source trunk switching element N S N S 3.6 bottleneck 1 holding

24 holding time service time 1 1 loss system 2 waiting system loss lost call crossbar switch

25 48 3 (0,t] A(0,t] B(0,t] B B = B(0,t] A(0,t] (3.2) B loss probability h (0,t] T (0,t] T (0,t]=A(0,t] h (3.3) T (0,t] (0,t] offered traffic T (0,t] a a = T (0,t] t = A(0,t] h t (3.4) a offered load (3.4) erlang erl (0,t] T c (0,t] T c (0,t]=(A(0,t] B(0,t]) h (3.5) T c (0,t] (0,t] carried traffic carried load a c a c = T c(0,t] t = (A(0,t] B(0,t]) h t = A(0,t] h t ( 1 B(0,t] ) A(0,t] = a(1 B) (3.6) (3.6) B B = a a c (3.7) a a a c

26 a a c 3.8 S (0,t] T c (0,t] St St T c (0,t] η = T c(0,t] St = a c S (3.8) η utilization S =2 60 A(0, 60 ] = 13 [ ] B(0, 60 ] = 1 [ ] B B = B(0, 60 ] A(0, 60 ] =

27 Markov process Markov chain {X(n)} 2.16 n =0, 1, 2,

28 , 1, 2,...,n i 0,i 1,i 2,...,i n n +1 j P (X(n +1)=j X(0) = i 0,X(1) = i 1,...,X(n) =i n ) P (X(n +1)=j X(0) = i 0,X(1) = i 1,...,X(n) =i n ) = P (X(n +1)=j X(n) =i n ) (5.1) Markov property {X(n); n =0, 1, 2,...} i 0,i 1,...,i n j n (5.1) discrete-time Markov chain i j n P (X(n +1)=j X(n) =i) =P (X(1) = j X(0) = i) (5.2) stationary (5.2) p i,j P (X(1) = j X(0) = i) =p i,j (5.3) p i,j i j transition probability 5.2 state transition diagram p 0,0 =1 α, p 0,1 = α, p 0,2 =0, p 0,3 =0 p 1,0 =0, p 1,1 =0, p 1,2 =1, p 1,3 =0 p 2,0 =0, p 2,1 =0, p 2,2 =0, p 2,3 =1 p 3,0 =0, p 3,1 = β, p 3,2 =1 β, p 3,3 =0 5.2

29 X(0) initial state i 0 i 1,i 2,...,i n P (X(0) = i 0,X(1) = i 1,...,X(n) =i n ) = P (X(0) = i 0,X(1) = i 1,...,X(n 1) = i n 1 ) P (X(0) = i 0,X(1) = i 1,...,X(n) =i n ) P (X(0) = i 0,X(1) = i 1,...,X(n 1) = i n 1 ) = P (X(0) = i 0,X(1) = i 1,...,X(n 1) = i n 1 ) P (X(n) =i n X(0) = i 0,X(1) = X 1,...,X(n 1) = i n 1 ) (5.4) (5.1) P (X(0) = i 0,X(1) = i 1,...,X(n) =i n ) = P (X(0) = i 0,X(1) = i 1,...,X(n 1) = i n 1 ) P (X(n) =i n X(n 1) = i n 1 ) = P (X(0) = i 0,X(1) = i 1,...,X(n 1) = i n 1 )p in 1,i n (5.5) P (X(0) = i 0,X(1) = i 1,...,X(n) =i n ) = P (X(0) = i 0 )p i0,i 1 p i1,i 2 p in 1,i n (5.6) i S i P (S i k) = k 1 m=0 p m i,i(1 p i,i ) (k =1, 2, 3,...) (5.7) S i S i i sojourn time

30 initial distribution p i,j (i, j =0, 1, 2,...) n X(n) j π j (n) P (X(n) =j) =π j (n) (5.8) π j (n) X(n) π j (n) j π(n) [ π 0 (n),π 1 (n),π 2 (n),...]=π(n) (5.9) n 0 i n j 1 p i,j (n) P (X(n) =j X(0) = i) =p i,j (n) (5.10) p i,j (n) i j n (5.10) n =1 (5.3) n =1 (1) p i,j i j m n P (X(m + n) =j X(m) =i) =P (X(n) =j X(0) = i) (5.11) i j n p i,j (n) (i, j) P (n) p 0,0 (n) p 0,1 (n) p 0,2 (n) p 1,0 (n) p 1,1 (n) p 1,2 (n) = P (n) (5.12) p 2,0 (n) p 2,1 (n) p 2,2 (n) P (n) n transition probability matrix P (0) = I (5.13) 1 1, 2, 3,...,n 1

31 74 5 I n =1 (1) P α α 0 0 P = β 1 β 0 n P (n) i j 0 p i,j (n) 1 (5.14) n i p i,j (n) = 1 (5.15) j P (n) 1 n j π j (n) = i π i (0)p i,j (n) (5.16) π(n) =π(0)p (n) (5.17) P (n) (i, j) p i,j (n) (5.10) p i,j (n) =P (X(n) =j X(0) = i) = P (X(0) = i, X(n) =j) P (X(0) = i) (5.18) (5.6) P (X(0) = i) i 1,i 2,...,i n 1 P (X(0) = i 0,X(1) = i 1,...,X(n) =i n ) P (X(0) = i i 2 i 0 ) n 1 i 1

32 = p i0,i 1 p i1,i 2 p in 1,i n i 1 i 2 i n 1 (5.19) p i,j (n) = p i,i1 p i1,i 2 p in 1,j i 1 i 2 i n 1 (5.20) P (n) =P n (5.21) (5.17) (5.21) π(n) =π(0)p n (5.22) π(0) P n π(n) P n (5.21) i m k n j i k j m n E p i,j (m + n) = k p i,k (m)p k,j (n) (5.23) P (m + n) =P (m)p (n) (5.24) (5.23) (5.24) Chapman Kolmogorov equation 1 (5.24) n =1 P (m +1)=P (m)p (5.25) Kolmogorov s forward equation 1 m =1 P (n +1)=PP(n) (5.26) Kolmogorov s backward equation (5.25) (5.26) (5.21)

33 α =0.7 β =0.5 π(0) = [ 0.15, 0.05, 0.5, 0.3 ] i j i j reachable i j i j j i i j i j i i i j j i i j j k i k equivalence class irreducible

34 211 e x 18, 26 FCFS 64 HOL 64 k 37 LCFS 64 M/G/1 150 M/M/1 137 M/M/1/K 143 M/M/S 124 M/M/S/K 130 M/M/S/S 117 M/M/S/S/N 110 n 73 n 73 PASTA 100 PDU 44 PR 64 PS 64 RR 64 t 84 t 84 2, 48 B 120 B 121, 191 C 127 C 128, , , , , , , , , , 86 75, 85 77, , 61 51, , , 93

35 , , , , , 84 73, , , , 83 81, , 91 53, 60 56, 60 2, 50, 60 76, 91 8, , , ,

36 213 47, , , , , , 65 77,

37 C FAX Printed in Japan ISBN