Networking Theory and Fundamentals - Lecture 8

Tham khảo tài liệu 'networking theory and fundamentals - lecture 8', công nghệ thông tin, quản trị mạng phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Networking Theory and Fundamentals - Lecture 8 TCOM 501: Networking Theory & Fundamentals Lecture 8 March 19, 2003 Prof. Yannis A. Korilis 1 Topics 8-2 Closed Jackson Networks Convolution Algorithm Calculating the Throughput in a Closed Network Arrival Theorem for Closed Networks Mean-Value Analysis Norton’s Equivalent Closed Jackson Networks 8-3 µ1 µ2 λ2 λ1 µ5 r51 λ5 r53 λ4 λ3 µ3 µ4 M Closed Network: K nodes with exponential servers No external arrivals (γi=0) , no departures (ri0=0) Fixed number M of circulating customers Appropriate model for systems with “limited” resources, e.g., flow control mechanisms Steady-state distribution will be shown to be of “product-form” type Closed Jackson Network 8-4 µ1 µ2 λ2 λ1 Aggregate arrival rates µ5 λ5 r51 λi = ∑ j =1 λ j rji , i = 1, ..., K K r53 λ4 λ3 Relative arrival rates – visit ratios µ3 µ4 M Can only be determined up to a constant Use an additional equation to obtain unique solution to the above system, e.g. Set λj=1, for some node j Set λj=µj, for some node j Set λ1+ λ2+…+ λK=1 ni: number of customers at node i Possible states for the closed network n=(n1, n2,…,nK), with ni ≥ 0 and | n |≡ ∑ i =1 ni = M K Let F(M) denote the set of all such states Closed Jackson Network 8-5 Let xi be the number of customers at station i, at steady state Random variables x1, x2,…, xK are not independent – their sum must be equal to M The state x=(x1, x2,…, xK) of the closed network can take values n=(n1, n2,…,nK), with ni ≥ 0 and | n |≡ ∑ i =1 ni = M K Let F(M) denote the set of all such states Define ρi ≡ λi/µi – this is not the actual utilization factor of station i Jackson’s theorem for closed networks gives the stationary distribution p( n ) = P{ x = n} = P{ x1 = n1 ,…, xK = nK } Jackson’s Theorem for Closed Networks 8-6 Theorem 1: The stationary distribution of a closed Jackson network is 1 K ∏ ρi ni , for all n ∈ F ( M ) = {n : ni ≥ 0, | n |= M } p( n ) = G ( M ) i =1 where the normalization constant G(M) is a function of M G(M) guarantees that {p(n)} is a valid probability distribution K ∑ ∑ ∏ ρi n p( n ) = 1 ⇒ G ( M ) = i n∈F ( M ) n∈F ( M ) i =1 This stationary distribution is said to have a product-form However: at steady-state the queues are not independent {pi(ni)}: marginal stationary distribution of queue i p( n ) ≠ p1 ( n1 ) pK ( nK ) Jackson’s Theorem for Closed Networks (proof) 8-7 Theorem 2: The reversed chain of a stationary closed Jackson network is also a stationary closed Jackson network with the same service rates and routing probabilities: rij* = λ j rji / λi Proof of Theorems 1 & 2: Show that for the corresponding forward and reversed chains p( m)q* ( m, n ) = p( n )q( n, m), n, m ∈ F ( M ), n ≠ m Need to prove only for m=Tijn q( n, Tij n ) = µ i rij 1{ni > 0} q* (Tij n, n ) = q* ( n − ei + e j , n ) = µ j rj*i 1{ni + 1 > 0} = µ j (λ i rij / λ j ) p(Tij n )q* (Tij n, n ) = p( n )q( n, Tij n ) ⇔ p(Tij n )µ j (λi rij / λ j ) = p( n )µ i rij 1{ni > 0} p(Tij n ) = ρ j ρi−1 p( n )1{ni > 0} ⇔ Verify, exactly as in the open-network case, that: ∑ q( n, m) = ∑ q* ( n, m) = ∑ µi 1{ni > 0}, n ∈ F (M ) m≠ n m≠ n i Closed Jackson Network 8-8 Example: Closed network model for CPU (rate µ1) and p1 λ1 ...