Networking Theory and Fundamentals - Lecture 7

Tham khảo tài liệu 'networking theory and fundamentals - lecture 7', 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 7 TCOM 501: Networking Theory & Fundamentals Lecture 7 February 25, 2003 Prof. Yannis A. Korilis 1 Topics 7-2 Open Jackson Networks Network Flows State-Dependent Service Rates Networks of Transmission Lines Kleinrock’s Assumption Networks of ./M/1 Queues 8-3 k γ1 rik j rij i ri 0 γi Network of K nodes; Node i is ./M/1-FCFS queue with service rate µi External arrivals independent Poisson processes γi: rate of external arrivals at node i Markovian routing: customer completing service at node i is routed to node j with probability rij or exits the network with probability ri0=1-∑jrij Routing matrix R=[rij] irreducible ⇒ external arrivals eventually exit the system Networks of ./M/1 Queues 8-4 Definition: A Jackson network is the continuous time Markov chain {N(t)}, with N(t)=(N1(t),…, NK(t)) that describes the evolution of the previously defined network Possible states: n=(n1, n2,…, nK), ni=1,2,…, i=1,2,..,K For any state n define the following operators: Ai n = n + ei arrival at i Di n = n − ei departure from i Tij n = n − ei + e j transition from i to j Transition rates for the Jackson network: q( n, Ai n ) = γ i q( n, Di n ) = µi ri 0 ⋅ 1{ni > 0} i, j = 1, ..., K q( n, Tij n ) = µi rij ⋅ 1{ni > 0} while q(n,m)=0 for all other states m Jackson’s Theorem for Open Networks 8-5 λi: total arrival rate at node i λi = γ i + ∑ j =1 λ j rji , i = 1, ..., K K Open network: for some node j: γj >0 Linear system has a unique solution λ1, λ2,…, λK Theorem 13: Consider a Jackson network, where ρi=λ/µi Jackson’s Theorem (proof) 8-6 Guess the reverse Markov chain and use Theorem 4 Claim: The network reversed in time is a Jackson network with the same service rates, while the arrival rates and routing probabilities are λ j rji γi γ * = λi ri 0 , rij* = , ri* = i 0 λi λi Verify that for any states n and m≠n, p( m)q* ( m, n ) = p( n )q( n, m) Need to prove only for m=Ain, Din, Tijn. We show the proof for the first two cases – the third is similar q* ( Ai n, n ) = q* ( Ai n, Di Ai n ) = µ i ri* = µ i ( γ i / λ i ) 0 p( Ai n )q ( Ai n, n ) = p( n )q( n, Ai n ) ⇔ p( Ai n )µi ( γ i / λi ) = p( n )γ i ⇔ p( Ai n ) = ρi p( n ) * q* ( Di n, n ) = q* ( Di n, Ai Di n ) = γ * = λ i ri 0 i p( Di n )q ( Di n, n ) = p( n )q( n, Di n ) ⇔ p( Di n )λi ri 0 = p( n )µ i ri 0 1{ni > 0} * ⇔ ρi p( Di n ) = p( n )1{ni > 0} Jackson’s Theorem (proof cont.) 8-7 Finally, verify that for any state n: ∑ q ( n, m ) = ∑ q * ( n, m ) m≠ n m≠ n ∑ q(n, m) = ∑ γ i + ∑ µi r 1{ni > 0} + ∑ µi ri 01{ni > 0} ij m ≠n i i, j i = ∑ γ i + ∑ µi [∑ rij + ri 0 ] ⋅ 1{ni > 0} i i j = ∑ γ i + ∑ µi 1{ni > 0} i i ∑ q* (n, m) = ∑ γ* + ∑ µi1{ni > 0} = ∑ λ i ri 0 + ∑ µi1{ni > 0} i m ≠n i i i i Thus, we need to show that ∑iγi =∑i λiri0 ∑ λi ri 0 = ∑ λi − ∑ ∑ λ i rij = ∑ λ i − ∑ ∑ λ i rij i i i j i j i = ∑ λ i − ∑ (λ j − γ j ) = ∑ γ j i j j Output Theorem for Jackson Networks 8-8 Theorem 14: The reversed chain of a stationary open Jackson network is also a stationary open Jackson network with the same service rates, while the arrival rates and routing probabilities are λ j rji γi γ * = λi ri 0 , rij* = , ri* = i 0 λi λi Theorem 15: In a stationary open Jackson network the departure process from the system at node i is Poisson with rate λiri0. The departure processes are independent of each other, and at any time t, their past up to t is independent of the state of the system N(t). Remark: The total arrival process at a given node is not Poisson. The departure process from the node is not Poisson either. However, the process of the customers that exit the network at the node is Poisson. Arrival Theorem in Open Jackson Networks 8-9 The composite arrival pro ...