kino@info.kanagawa-u.ac.jp p.1/76
p.2/76
( ) (2001). (2006). (2002). p.3/76
N n, n {1, 2,...N} 0 K k, k {1, 2,...,K} M M, m {1, 2,...,M} p.4/76
R =(r ij ), r ij = i j ( ): k s r(k, s) r(k, 1),r(k, 2),...,r(k, S(k)) 0:5 0:5 p.5/76
N =3,K =3,M =3 1 0.4 1 1 2 2 0.6 1 2 1 0.7 1 1 2 0.2 0.3 0.8 2 3 3 1 2 3 1 : F1(x) =1 e μ 1 x ( ) 2 : F2(x) =1 e μ 2 x ( ) 3 : F3(x) =1 e 2μ 3 x (1 + 2μ3x) ( ) p.6/76
1 1 2 3 2 3 4 1 2 3 p.7/76
P (c, y) = P (c)p (y c) P (c) = CΛ(m)Φ(u) N j=1 τ j (c j ) τ j (c j ) = θ j(m jl,k jl ) µ kl c N P (y c) = µ jl (1 F kjl (y jl )) j=1 c =(c 1, c 2,...,c N ): y =(y 1, y 1,...,y 1 ): l p.8/76
1 0 0 P (c y)dy =1 P (c) = CΛ(m)Φ(u) τ j (c j ) = θ j(m jl,k jl ) µ kl N j=1 τ j (c j ) m = ( m m (c) ) M : m m=1 m(c) c m u = ( ((ujmk (c)) K k=1 ) M m=1) N m, k j=1 : u jmk (c) c j p.9/76
2 C : µ jl : j l k jl : j l θ j (m jl,k jl ): j Λ(m): λ m (m) = Λ(m + e m) Λ(m) Φ(u): γ j (l, c) = Φ(u e j(m jl,k jl )) Φ(u) β j (l, c) p.10/76
: µ k (insensitive ) θ j (m, k) m u (c) (y) p.11/76
Λ(m) Φ(u) p.12/76
M/G p.13/76
M/G Poisson K k S k F k (x) =P (S k x), f k (x) E(S k )= 1 : k µ k p.14/76
(n ) 1 2 3 n y1 y2 y3 yn c2 c3 cn c1 : (c; y) =(c1; c2; :::;cn) ; y =(y1; y2; :::;yn) c c l : l, c l {1, 2,...,K} y l : l, 0 <y l c =(c 1,c 2,...,c n ), y =(y 1,y 2...,y n ) (c, y): c c p.15/76
c λ k (c): k, k =1, 2,...,K γ(l, c) = d dt y l: c l dt γ(l, c)dt y l + dy l = y l γ(l, c) p.16/76
cn k c ffi(`; c) c1 c` 1 c` c`+1 cn c1 c` 1 k c` cn 1 δ(l, c): l ( ) n+1 l=1 δ(l, c) =1 p.17/76
(global barance equation) = c { λcl (c [l] ) δ(l, c [l] ) f c l (y l ) P (c [l], y [l] )+ P (c, y)γ(l, c) } y l l=1 K { λk (c)p (c, y) k=1 c +1 l=1 γ(l, c + [l(k)] )P ( c + [l(k)], y+ [l(0)] )} p.18/76
P (c, y) = P (c)p (y c) P (c) = CΛ(w)Φ(w)τ(c) τ(c) = P (y c) = c l=1 c l=1 1 µ cl µ cl ( 1 Fcl (y l ) ) w =(w 1,w 2,...,w K ), w k : c k p.19/76
Λ(w) (w ) λ k (w) = Λ(w + e k) Λ(w) Φ(w) (w ) γ(l, c) = Φ(w e(c l)) Φ(w) β(l, c) β(l, c): c l c β(l, c) =1 l=1 p.20/76
c δ(l, c [l])=β(l, c) l =1, 2,..., c c [l] =(c 1,c 2,...,c l 1,c l+1,...,c c ) c l=1 Φ(w e(c l )) Φ(w) µ cl { δ(l, c [l] ) β(l, c)} =0 p.21/76
(symmetric queue) δ(l, c [l])=β(l, c) l c c l β(l, c) =δ(l, c [l] )= 1 c LCFS-PR : β(1, c) =δ(1, c [l])=1, 0 p.22/76
δ(l, c [l]) β(l, c) (K) c l=1 Φ(w e(c l )) Φ(w) µ cl { δ(l, c [l] ) β(l, c)} =0 FCFS: µ 1 = µ 2 = = µ K δ(l, c) = { 1 l = c +1 0, β(l, c) = { 1, l =1 0, p.23/76
Λ(w) k : λ k (w) = Λ(w + e k) Λ(w) Λ(w) =λ w 1 1 λw 2 2...λw K K S Λ(w) = { λ c, c S 1 0, S c λ k(w) =λ k λ k (w) = { λ, c S 0, S < c p.24/76
Φ(w) c l γ(l, c) = Φ(w e(c l)) Φ(w) β(l, c) Φ(w) =Φ( w )(= Φ( c )) Φ(n) = { n ν( c ) = Φ( c 1) Φ( c ) s=1, c =1, 2,... ν(s) } 1, n =1, 2,..., Φ(0) = 1 p.25/76
w z c1 c2 c` c n ffl $ ν(n) β(l, c) ν(n) fi(1;c) fi(n;c) fi(2;c) fi(`;c) ν(n) Φ(n) Φ(w) p.26/76
p.27/76
= c l=1 { λcl (c [l] ) δ(l, c [l] ) f c l (y l ) P (c [l], y [l] )+ y l P (c, y)γ(l, c) } K { λk (c)p (c, y) k=1 c +1 l=1 γ(l, c + [l(k)] )P ( c + [l(k)], y+ [l(0)] )} =0, =0 p.28/76
( ) (1) c l=1 {λ cl (c [l] ) δ(l, c [l] ) f c l (y l ) P (c [l], y [l] )+ y l P (c, y)γ(l, c)} =0 k =1, 2,...,K (2) λ k (c)p (c, y) c +1 l=1 γ(l, c + [l(k)] )P ( c + [l(k)], y+ [l(0)]) =0 (local balance equation) p.29/76
(2) (1) (3) c l=1 Φ(w e(c l )) Φ(w) f cl (y l ) { δ(l, c 1 F cl (y l ) [l] ) β(l, c)} =0 (3) (3) p.30/76
(3) c (4) δ(l, c [l]) β(l, c) =0, l =1, 2,..., c (4) p.31/76
δ(l, c [l] ) β(l, c) (3) 0 <y l f cl (y l ) 1 F cl (y l ) = (3) c l=1 Φ(w e(c l )) Φ(w) µ cl { δ(l, c [l] ) β(l, c)} =0 p.32/76
S:, q(x, x ): (x x ), π(x): x π(x) x S q(x, x )= x S π(x )q(x, x), x S S = S 1 S 2 S n S i π(x) q(x, x )= x S i π(x )q(x, x), x S i x S i p.33/76
X(t) X( t) X(t) X( t) ( ) X(t) π(x)q(x, x )=π(x )q(x, x), x, x S (detailed balance equation) M/M/1 p.34/76
M M x(t): K t (quasi-reversible) x(t 0 ) t 0 k x(t 0 ) t 0 k M M M M Poisson Poisson M M p.35/76
) p.36/76
p.37/76
c j =(c j1 ; c j2 ;:::;c jn ) c j` =(mj`;kj`) j : (c j ; y j ) 1 2 n c j` yj1 yj2 yjn (mj1;kj1) (mj2;kj2) (mjn;kjn) (mj`;kj`) =( `, ` ) c =(c 1, c 2,...,c N ) y =(y 1, y 2,...,y N ) (c, y) p.38/76
P (c, y) = P (c)p (y c) P (c) = CΛ(m)Φ(u) τ j (c j ) = c j l=1 N j=1 σ j (m jl,k jl ) σ j (m jl,k jl ) = θ j(m jl,k jl ) µ kjl τ j (c j ) P (y c) = N c j j=1 l=1 µ kjl ( 1 Fkjl (y jl ) ). p.39/76
(1) m jl : j, l k jl : j, l θ j (m jl,k jl ): (m jl,k jl ) m θ m =(θ m1, θ m2,...,θ mn ) θ mi = ( θ i (m, 1),θ i (m, 2),...,θ i (m, K) ), i =1, 2,...,N θ i (m, k): i m, k p.40/76
(2) r m ( (i, k), (j, h) ) : i k m j h m R(m) = R m (1, 1) R m (1, 2)... R m (1,N) R m (2, 1) R m (2, 2)... R m (2,N) f... R m (N,1) R m (N,2)... R m (N,N) m θ m = θ m R(m) 0 (1, θ m )=(1, θ m )R(m) p.41/76
j (m; h) from node i (3) rm(0; (j; h)) 1 out of the network i(m; k) j i i(m; k) i(m; k) rm((i; k); (j; h)) N p.42/76
m m λ m (m) = Λ(m + e(m)) Λ(m) Λ(m) =Λ 1 (m 1 )Λ 2 (m 2 )...Λ M (m M ) u jmk : j m, k x jm : j m u = ( ((ujmk ) K k=1 ) M m=1) N j=1, x = ( (x jm ) M m=1 ) N j=1 Φ(u) =Φ 1 (u 1 )Φ 2 (u 2 ) Φ N (u N ) u Φ(x) =Φ 1 (x 1 )Φ 2 (x 2 ) Φ N (x N ) x p.43/76
(c, y) x =(x 1, x 2,...,x N ), x j =(x j1,x j2,...,x jm ) x jm : j m M p.44/76
x =(x 1,x 2,...,x n ), ρ =(ρ 1,ρ 2,...,ρ n ) x = n, x = x 1 + x 2 + + x n x! =x 1!x 2! x n! ρ x = ρ x 1 1 ρx 2 2 ρx n n (a 1 + a 2 + + a n ) m = x 1 +x 2 + +x n =m m! x 1!x 2! x n! ax 1 1 ax 2 2 ax n n a m = x =m x! a x x! p.45/76
(1) x =(x 1, x 2,...,x N ) x j =(x j1,x j2,...,x jm ), j =1, 2,...,N x jm : j m K =(K 1,K 2,...,K M ), K m : m ( ) Φ(x) =Φ 1 ( x 1 )Φ 2 ( x 2 ) Φ N ( x N ) j n ν j (n) = Φ j(n 1) Φ j (n) Φ j (n) = 1 ν j (1)ν j (2) ν j (n), Φ j(0) = 1 p.46/76
(2) ν j (n) =ν j (1), n =1, 2,... ν j (n) =nν j (1), n =1, 2,... (S j ): ν j (n) = : ρ =(ρ 1, ρ 2,...,ρ N ) { nν j (1), n S j S j ν j (1), S j <n ρ j =(ρ j1,ρ j2,...,ρ jm ), j =1, 2,...,N K ρ jm = σ j (m, k), σ j (m, k) = θ j(m, k) µ k k=1 p.47/76
(3) ( ) P (x) = 1 G(K) N Φ j (x j )ϕ j (x j ), j=1 ϕ j (x j )= x j! ρ x j j x j! G(K): G(K) = x 1 +x 2 + +x N =K N j=1 Φ j (x j )ϕ j (x j ) G(K) x P (x) =1 N =10, M =3, K =(5, 5, 5) 80 p.48/76
( ) P (x) = 1 G(K) N j=1 q j (x j ) q j (x j ) = Φ j ( x j ) x j! x j! G(K): ρ x j j λxo j = Φ j ( x c j + x o j ) ( xc j + xo j )! x c j! xo j! (ρ c j) xc j (ρ o j ) xo o j λ xj p.49/76
(convolution). MVA(Mean Value Analysis): p.50/76
G(K) (over flow/under flow) p.51/76
x =(x 1,x 2,,x n ): a(x) b(x) : x c(x) =(a b)(x): a, b c(x) = (a b)(x) = a(x i) b(i) = 0 i x x 1 i 1 =0 x 2 i 2 =0 x n i n =0 a(x 1 i 1,x 2 i 2,,x n i n ) b(i 1,i 2,,i n ) (a b)(x) =(b a)(x), ((a b) c)(x) =(a (b c))(x) (a 1 a 2 a n )(x): a 1,a 2,...,a n p.52/76
M K P (x) = 1 G(K) N j=1 q j (x j ), q j (x j )=Φ j ( x j ) x j! x j! ρ x j j G(K) = x 1 +x 2 + +x N =K N j=1 q j (x j ) G(K) =(q 1 q 2 q N )(K) p.53/76
i- i : i 0 i x [i] =(x 1,...,x i 1, x i+1...,x N ) : i- i- P (x [i] )= 1 G [i] (K) N q j (x j ), j=1 j i q j (x j )=Φ j ( x j ) x j! x j! ρ x j j G(K) = x 1 + x i 1 +x i+1 + +x N =K N q j (x j ) j=1 j i (i 1,i 2,...,i m )- p.54/76
x 1 : G(K) = q 1 (x 1 ) N q j (x j ) 0 x 1 K x 2 + +x N =K x 1 j=2 N G [1] (K x 1 )= q j (x j ) x 2 + +x N =K x 1 j=2 1- q 1 G(K) = q 1 (x 1 )G [1] (K x 1 )=(q 1 G [1] )(K) 0 x 1 K G(K) =(q 1 q 2 G [1,2] )(K) = =(q 1 q 2 q N )(K) p.55/76
A A1: : 0 x K x =(x 1,x 2,...,x M ) G(x) { 1 x = 0 0 x 0 A2: j =1, 2,,N A3, A4, A5 A3: q j (x j ) : 0 x K x q(x) Φ j ( x ) x! x! A4: : k = K,, 1, 0 A5 A5: x = k, 0 x K x G(x) 0 y x ρ x j G(y)q(x y). p.56/76
A G(x) =G [j] (x)+ M m=1 ρ jm G(x e(m)) S A3,A4,A5 S S1: k =1, 2,, K S2 S2: x = k, 0 x K x G(x) G(x)+ M m=1 ρ jm G(x e(m)). p.57/76
K 2 h j1 h j2 K 1 G(x) ψ G [j](x) +h j1 G(x e(1)) + h j2 G(x e(2)) :G [j](x) :G(x) p.58/76
j G [j] (x),0 x K j G [j] (x) G(x) G(x) G [j] (x) p.59/76
p.60/76
I/O ( ) ( ) ( ) p.61/76
M OU %27 &-ÎÐÑÑ OU &$ÎÐÑÑ.QIÔÎÏÖ Ç}Ì OU 4GCF 4GCF 9TKVG OU OU OU OU 9TKVG (CPU,DB,Log)=(30,90,15)=ρ p.62/76
ÐÖÏÎ Ò Ò Ñ f ÐÖÏÎ Ò Ð Ó %27 &- &- ÐÖÏÎ Ò Ò Ñs f ÐÖÏÎ Ò 09 09 ÐÏÐÖÑÏÕ CPU 15 #2 &- &-... I/O s Ð Ó v Clients Server System p.63/76
I/O p.64/76
1987/2/2. 1988/7/18. C/S 1994/8/22. 400 C/S 19996/9/16. p.65/76
SE IT p.66/76
( ) SE p.67/76
70 ÒÖ ÐÐÑÕ Ñ ÐÖÔÖÔÎÏÖ ÐÖÏÎ ÒÐ ÓÕÒÖ 15 #2 &- &- %27 &- &- %27 &- &- ENKGPVU UGTXGT p.68/76
QM-X) p.69/76
PC, WS p.70/76
Tiny Topaz QM-Open ªªª ªªª ªªª ªªª h h h h ªªª ªªª ªªª ªªª ªªªª ªªªª ªªªª ªªªª ªªª ª ªªª ª ªªª ª ªªª ª hv hv hv hv ªªªª ªªªª ªªªª ªªªª ª ªªªªªª ªªªª ªªªªªª ªªªªªªªªª ªªªªªªªª ªªªªªªªª ªªªªªªªª ªªª ª ªªª ª ªªª ª ªªª ª ªªªªª ªªªª ªªªª ªªªª Ð Ó u u u u ««ªªª ªªª ªªªª vƒ 5QHVYCTG 5QHVYCTG 5QHVYCTG 5QHVYCTG RTQDG RTQDG RTQDG RTQDG p.71/76
Tiny Topaz ªªª EWS «ªªªªªª «TinyTOPAZ «All in one «Dynamic Hook Opal p.72/76
Tiny Topaz p.73/76
ρ ρ ρ ªªªª world s world ρ s u s p.74/76
NEC) p.75/76
I thank you for your attention. p.76/76