电子科技大学：《先进计算机网络技术》课程教学资源（课件讲稿）Unit 2 Call-level Models and Admission Control

Feng Gang National Laboratory of Communication,UESTC Aug 2017 Ver 1.4 Unit 2 Call-level Models and Admission Control 2616009:Network Traffic Engineering 2:Call-level Models and Admission Control Page.1

2616009: Network Traffic Engineering Feng Gang National Laboratory of Communication, UESTC Aug 2017 Ver 1.4 2: Call-level Models and Admission Control Page.1 Unit 2 Call-level Models and Admission Control

Feng Gang National Laboratory of Communication,UESTC Aug 2017 Ver 1.4 Roadmap Review:Queuing Models for Birth-Death Process Multiservice Loss System and The Stochastic Knapsack 。 Admission Policies Optimization Concept Optimal Complete Partitioning Policies Optimal Coordinate Convex Policies Case Study:Call Admission Control for Multi-service Mobile Networks with Bandwidth Asymmetry between Uplink and Downlink 2616009:Network Traffic Engineering 2:Call-level Models and Admission Control Page.2

2616009: Network Traffic Engineering Feng Gang National Laboratory of Communication, UESTC Aug 2017 Ver 1.4 2: Call-level Models and Admission Control Page.2 Roadmap • Review: Queuing Models for Birth-Death Process • Multiservice Loss System and The Stochastic Knapsack • Admission Policies • Optimization Concept • Optimal Complete Partitioning Policies • Optimal Coordinate Convex Policies • Case Study: Call Admission Control for Multi-service Mobile Networks with Bandwidth Asymmetry between Uplink and Downlink

Feng Gang National Laboratory of Communication,UESTC Aug 2017 Ver 1.4 Review:Queuing model for Birth-Death Process A birth and death process is a continuous-time Markov chain with states {0,1,..}for which transitions from state n may go only to either state n-1 or state n+1. M servers N buffers 2616009:Network Traffic Engineering 2:Call-level Models and Admission Control Page.3

2616009: Network Traffic Engineering Feng Gang National Laboratory of Communication, UESTC Aug 2017 Ver 1.4 2: Call-level Models and Admission Control Page.3 Review: Queuing model for Birth-Death Process • A birth and death process is a continuous-time Markov chain with states {0,1,…} for which transitions from state n may go only to either state n-1 or state n+1. N buffers M servers

Feng Gang National Laboratory of Communication,UESTC Aug 2017 Ver 1.4 Queuing model for Birth-Death Process(cont'd) ·Notations -X=number of customers in the system(buffer and servers)at time t -=arrival rate of customers in state X,=n -n =departure rate of customers in state X,=n ·Assumptions P(X+w-X,=1X,=n)=n△t+o(△t) P(X,+-X,=-1|X,=n)=4n△t+o(△) P(X-X,>1X,=n)=0(At) where o(△)=0 o(△)=lim ar 1→0 2616009:Network Traffic Engineering 2:Call-level Models and Admission Control Page.4

2616009: Network Traffic Engineering Feng Gang National Laboratory of Communication, UESTC Aug 2017 Ver 1.4 2: Call-level Models and Admission Control Page.4 Queuing model for Birth-Death Process(cont’d) • Notations - Xt = number of customers in the system (buffer and servers) at time t  n = arrival rate of customers in state  n =departure rate of customers in state • Assumptions Xt  n Xt  n P(X X 1| X n) t o( t) tt  t  t   n   P(X X 1| X n) t o( t) tt  t   t    n   P(| X X | 1| X n) o( t) tt  t  t    where 0 ( ) ( ) lim 0        t o t o t t

Feng Gang National Laboratory of Communication,UESTC Aug 2017 Ver 1.4 Queuing model for Birth-Death Process(cont'd) ·Analysis Let P(t)=P(X,=n) △Pn(t+△t)=Pn(t+△t)-Pn(t) =*P()-()At*P(t)+A*(t) Taking the limit as△t-→o gives Pm(t)）=元n-Pn-1(t)）-(4n+n)Pn(t)+4n+1Pn+1(t) Stationary Conditions P(0)=1 B.=limp(t)P= ∑p=1 -f1a TIa n=1i=0 2616009:Network Traffic Engineering 2:Call-level Models and Admission Control Page.5

2616009: Network Traffic Engineering Feng Gang National Laboratory of Communication, UESTC Aug 2017 Ver 1.4 2: Call-level Models and Admission Control Page.5 Queuing model for Birth-Death Process(cont’d) • Analysis Let P (t) P(X n) n  t  * ( ) ( ) * ( ) * ( ) ( ) ( ) ( ) 1 1 1 1 t P t t P t t P t P t t P t t P t n n n n n n n n n n                       Taking the limit as gives t  o ( ) ( ) ( ) ( ) ( ) 1 1 1 1 ' P t P t P t P t n  n n  n  n n  n n Stationary Conditions P0 (0) 1 ( ) P limP t n t n    nPn  n1Pn1     0 1 i Pi 0 1 0 1 P / P n n n i i                            1 1 0 0 1 1/ 1 / n n i P i i

Feng Gang National Laboratory of Communication,UESTC Aug 2017 Ver 1.4 Queuing model for Birth-Death Process(cont'd) Some special Birth-death Processes Poisson Process:=0 for all n≥0 n=元for all n≥0 The probability of k arrivals in T: p(k)=(AT)e-i/k! Inter-arrival time:Exponential distribution: f(x)=le x≥0 -Queuing system M/M/1：元，=z for alln≥0 =u for alln≥0 Number of customers in the system geometric distribution: p(k)=(1-p)p The average waiting time from arrival until the end of service for FIFO discipline 1-p (p=元1） 2616009:Network Traffic Engineering 2:Call-level Models and Admission Control Page.6

2616009: Network Traffic Engineering Feng Gang National Laboratory of Communication, UESTC Aug 2017 Ver 1.4 2: Call-level Models and Admission Control Page.6 Queuing model for Birth-Death Process(cont’d) • Some special Birth-death Processes - Poisson Process : The probability of k arrivals in T: Inter-arrival time: Exponential distribution: - Queuing system M/M/1 :  0 for all n  0  n n   for all n  0  for all n  0  n   for all n  0 n  p(k) ( T) e / k! k T    ( )   0  f x e x x  Number of customers in the system : geometric distribution: k p(k)  (1 ) The average waiting time from arrival until the end of service for FIFO discipline     1 1/ T (   / )

Feng Gang National Laboratory of Communication,UESTC Aug 2017 Ver 1.4 Queuing model for Birth-Death Process(cont'd) The Erlang B Loss Formula When the number of sources is assumed to be infinite,with a total aggregate traffic load of A Erlangs and with assumption that calls which arrive when all C servers are busy are cleared from the system and do not return.The Erlang B loss formula is: A/C! B(C,A)= 41m (A=元10) 1=0 The Erlang B distribution for the number of busy servers is A"n! 三术因 2616009:Network Traffic Engineering 2:Call-level Models and Admission Control Page.7

2616009: Network Traffic Engineering Feng Gang National Laboratory of Communication, UESTC Aug 2017 Ver 1.4 2: Call-level Models and Admission Control Page.7 Queuing model for Birth-Death Process(cont’d) • The Erlang B Loss Formula - When the number of sources is assumed to be infinite, with a total aggregate traffic load of A Erlangs and with assumption that calls which arrive when all C servers are busy are cleared from the system and do not return. The Erlang B loss formula is: - The Erlang B distribution for the number of busy servers is   C n n C A n A C B C A 0 / ! / ! ( , )   C k k n n A k A n P 0 / ! / ! (A   / )

Feng Gang National Laboratory of Communication,UESTC Aug 2017 Ver 1.4 Queuing model for Birth-Death Process(cont'd) The Erlang-Engset Loss Formula If the number of source is finite while blocked calls are cleared The Probability of finding X servers busy is given by the Erlang- Engest distribution.Letting Sx denote the probability of finding X servers busy when there are S sources and the offered traffic per idle source is b Erlangs S: 2616009:Network Traffic Engineering 2:Call-level Models and Admission Control Page.8

2616009: Network Traffic Engineering Feng Gang National Laboratory of Communication, UESTC Aug 2017 Ver 1.4 2: Call-level Models and Admission Control Page.8 Queuing model for Birth-Death Process(cont’d) • The Erlang-Engset Loss Formula - If the number of source is finite while blocked calls are cleared . The Probability of finding X servers busy is given by the Erlang￾Engest distribution. Letting Sx denote the probability of finding X servers busy when there are S sources and the offered traffic per idle source is b Erlangs                   C i i x b i S X S S 0

Feng Gang National Laboratory of Communication,UESTC Aug 2017 Ver 1.4 Multiservice Loss Systems A loss system is a collection of resources to which calls,each with an associated holding time and class,arrive at random instances. 。 An arriving call either is admitted into the system or is blocked and lost 。 The admittance decision is based on the call's class and the system's state C bandwidth units=C servers ,41,b Collection of calls departure Resources :arrival rate System state n (Carried traffic) :service rate b,bandwidth class j Lost (blocked or overflow traffic streams) 2616009:Network Traffic Engineering 2:Call-level Models and Admission Control Page.9

2616009: Network Traffic Engineering Feng Gang National Laboratory of Communication, UESTC Aug 2017 Ver 1.4 2: Call-level Models and Admission Control Page.9 Multiservice Loss Systems • A loss system is a collection of resources to which calls, each with an associated holding time and class, arrive at random instances. • An arriving call either is admitted into the system or is blocked and lost • The admittance decision is based on the call’s class and the system’s state Collection of Resources System state n calls Lost (blocked or overflow traffic streams) departure j j j  ,  , b : arrivalrate  j :service rate  j : bandwidth class j j b C bandwidth units=C servers (Carried traffic)

Feng Gang National Laboratory of Communication,UESTC Aug 2017 Ver 1.4 Loss Networks with Fixed Routing PBX Central Example:A telephone network with star topology switch 6 classes System state:n=(n,...n),n:class k in progress PBX PBX -s:the set for all state -k:the set of state with room for another class-k call O PBX neS if and only if n+ees Where ex is the vector of all zeros except for a one in the kth component Clocking Probability of a class-k call B=1- G where -20器 and nes k=1 neSx 1=1 n! Pr=h/ue 2616009:Network Traffic Engineering 2:Call-level Models and Admission Control Page.10

2616009: Network Traffic Engineering Feng Gang National Laboratory of Communication, UESTC Aug 2017 Ver 1.4 2: Call-level Models and Admission Control Page.10 Loss Networks with Fixed Routing • Example: A telephone network with star topology - 6 classes - System state: , : class k in progress - S : the set for all state - Sk: the set of state with room for another class-k call - if and only if Where is the vector of all zeros except for a one in the kth component • Clocking Probability of a class-k call PBX PBX PBX PBX Central switch ( ,... ) n  n1 n6 nk k nS  S k n e k e G G B k k 1 where     n S 1 6 ! k k n k n ρ G k and     k l l l n l k n ρ G n S 1 6 !  k k k  /