Transcript 投影片 1

Chapter 4
Fundamental Queueing System
1
2
Ref: Mischa Schwartz “Telecommunication Networks” Addison-Wesley
publishing company 1988
3
4
p  T  T m
  T
5
 x
6
 : arrived rate
 : service rate
7
8
9
surface 1     Pn  Pn 1  Pn 1 n  1
surface 2  Pn  Pn 1
10
11
12
(input rate/output rate) (the probability that the system is nonempty)
The throughput (customer/see) = λ
13
=r
net arrival rate=
throughput (customer / see)   (1  PB )
The throughput r/μ=
(1  P0 )  1 
1 
 (1   N )

(1   N 1 )
1   N 1
14
15
16
i  
i  
p

p
n 0
n

m
1
17
WQ 
T
1

W 
1


NQ

PQ
m  
18
19
20
Example 1 Statistical Multiplexing Compared with TDM and FDM
Assume m statistically iid Poisson packet streams each with an arrival rate
of  m packets/sec.
The packet lengths for all streams are independent and exponentially
distributed.
The average transmission time is 1  .
If the streams are merged into a single Poisson stream, with rate  , the
average delay per packet is
T 
1
 
If, the transmission capacity is divided into m equal portions, as in TDM
and FDM, each portion behaves like an M/M/1 queue with arrival rate  m
and average service rate  m . Therefore, the average delay per
m
packet is
T
 
21
Example 2
Using One vs. Using Multiple Channels Statistical MUX(1)
A communication link serving m independent Poisson traffic streams with
overall rate  .
Packet transmission times on each channel are exponentially distributed with
mean 1  . The system can be modeled by the same Markov chain as the
M/M/m queue. The average delay per packet is given by
PQ
1
T 
 m  
An M/M/1 system with the same arrival rate  and service rate m (statistical
multiplexing with one channel having m times larger capacity), the average
delay per packet is
PˆQ
1
Tˆ 

m m  
PQ and p̂ Q denote the queueing probability
22
When

<< 1 (light load) PQ  0 , p̂ Q  0 , and
T
m
ˆ
T
At light load, statistical MUX with m channels produces a delay almost m times
larger than the delay of statistical MUX with the m channels combined in one.
When
  1 , PQ
 1 , p̂ Q
 1, 1  << 1 (m   ) , and
T
1
ˆ
T
At heavy load, the ratio of the two delays is close to 1.
23
4.6
f ( x) 
1
1
 1 x2
x 2 doesn ' t exist
24
25
26
27
W  R   W
W  R  W
28
A.
29
second moment of service time and load
IF
X2 
W 
30
2
31
32
33


34
Roll-call Polling
Stations are interrogated sequentially, one by one, by the central system, which
asks if they have any messages to transmit.
time
Wi : walk time
ti
: frame transmission time
35
The scan or cycle time
t c is given by
The average scan time
tc
wi , t are the ave. walk time and the ave. time to transmit pkt at station i .
i
L is the total walk time of the complete poling system.
36
For station i , let
i : the ave. pkt arrival rate
 : the ave. packet length
 : the number of overhead bits
C : the channel capacity in bps
mi : the ave. frame length in time
mi  (    ) / C
The average number of packets waiting to be transmitted when station
polled is  t , the time required to transmit is
i
With
c
is
ti  i tc mi  i t c
 i  i mi
N
i
the traffic intensity, the average scan time t c is given
N
With     i   i mi representing the total traffic intensity on the common
i 1
channel. i 1
37
For small  the average access delay should be tc / 2 .
Assume that each station has the same
and the same w .

, same frame-length statistics,
The average access delay is
  N m
.
m 2 is the second moment of the frame length,
The access delay is the average time a packet must wait at a station from the
time it first arrives until the time transmission begins. Access delay is thus
the average wait time in an M/G/1 queue.
Ref: Mischa Schwarty: “Telecommunication Networks, Protocols Modeling and
Analysis”, Addison-Wesley Publishing Company, 1988, PP. 408-422
38
Hub Polling
• Control is passed sequentially from one station to another.
• Let the polling message be a fixed value, tp sec in length.
• The time required per station to synchronize to a polling message is ts
sec.
• The total propagation delay for the entire N-station system is   sec.
39
Hub Polling (Cont’)
• The total walk time for roll-call polling is L  Nt p  Nts    .
• Let the stations all be equally spaced, and the round-trip propagation
delay between the controller and station N be τ sec.
• The overall propagation delay  is just

   (1  N )
2
• The analysis of the hub-polling strategy is identical to that of roll-call
polling.
• The only difference is that the walk time L is reduced through the use of
hub polling.
• For hub polling, Lhub    Nt s .
40