TAILIEUCHUNG - Lecture Networking theory & fundamentals - Chapter 7
The following will be discussed in this chapter: Open jackson networks, network flows, state-dependent service rates, networks of transmission lines, kleinrock’s assumption. | Lecture Networking theory & fundamentals - Chapter 7 TCOM 501: Networking Theory & Fundamentals Lecture 7 February 25, 2003 Prof. Yannis A. Korilis 1 7-2 Topics Open Jackson Networks Network Flows State-Dependent Service Rates Networks of Transmission Lines Kleinrock’s Assumption 8-3 Networks of ./M/1 Queues k γ1 rik j i rij γi ri 0 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 8-4 Networks of ./M/1 Queues 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 8-5 Jackson’s Theorem for Open Networks λ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=λ/µi8-6 Jackson’s Theorem (proof) 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 = λi ri 0 , rij* = , ri*0 = λi λi Verify .
đang nạp các trang xem trước
