Polling Network Analysis
2.3
2002/08/19
2005/06/09 10:46:37 GMT-5
Bart
Sinclair
bs@rice.edu
Charlet
Reedstrom
charlet@rice.edu
Bart
Sinclair
bs@rice.edu
computer communications network
computer network
distributed polling
exhaustive polling
gated polling
hub polling
M/G/1 queue with vacations
partially gated polling
poll
polling network
(Blank Abstract)
A polling network is a computer communications network that uses
polling to control access to the network. Each node
or station on the network is given exclusive access to the network
in a predetermined order. Permission to transmit on the network
is passed from station to station using a special message called a
poll. Polling may be centralized (often called
hub polling) or decentralized
(distributed). In hub polling, the polling order is
maintained by a single central station or hub. When
a station finishes its turn transmitting, it sends a message to
the hub, which then forwards the poll to the next station in the
polling sequence. In a decentralized polling scheme, each station
knows its successor in the polling sequence and send the poll
directly to that station. To simplify matters, we will assume a
distributed polling scheme.
The analysis of a polling network uses the results of the
analysis of an M/G/1 queue with vacations. Each vacation
corresponds to the transfer of the poll from one station to the
next in the polling cycle. We divide time into alternating
types of intervals: polling intervals, during which
the poll is transferred between stations, and transmission
intervals, during which the station with the poll
transmits packets.
Polling networks come in three flavors: gated, exhaustive, and
partially gated. In a gated system, each station
is allowed to transmit only those packets that arrived prior to
the start of the poll interval (i.e., prior to the start of the
vacation preceding the station's use of the network). An
exhaustive scheme allows a station to transmit any
packets that arrive before it transfers the poll to the next
station. A partially gated network allows stations
to transfer all packets that arrive by the time the poll does.
Polling networks will typically be partially gated or
exhaustive, not gated.
We assume that arrivals at each of the
m stations are independent Poisson
processes with rate
λ
m
. Note that "arrival" refers to a message arriving
from the "outside world" to a station in order to be transmitted
over the network; it does not mean the arrival of a message that
has been transmitted over the network.
gated system, m=1
We define the following notation:
-
X
- mean packet length in seconds
-
X
2
- second principal moment of the packet length
distribution
-
V
r
- r.v. for length of
r
th
polling interval.
V
r
are independent and identically distributed.
-
V
V
r
-
V
2
V
r
2
-
R i
- r.v. for residual time
data packet i must
wait in queue until end of current packet
transmission or polling interval
-
V
r
(
i
)
- r.v. for length of polling interval for data
packet i
-
ρ
λ
X
A packet which arrives in a gated system with one station must
first wait the residual service time for the packet currently
being transmitted or the residual length of the poll transfer
time, depending on when it arrives. It must then wait until
all of the packets queued for transmission at its arrival have
been serviced. Finally, it must wait until the next poll
transfer is finished (note that in this simplistic system, the
station sends the poll to itself).
W
i
R
i
N
i
X
V
r
(
i
)
The time-average for the residual service time can be obtained
as it was for the M/G/1 queue with vacations.
R
i
λ
X
2
2
1
ρ
V
2
2
V
Also as before,
i
N
i
X
i
λ
W
i
X
ρ
W
i
V
r
(
i
)
V
W
λ
X
2
2
1
ρ
V
2
2
V
ρ
W
V
λ
X
2
2
1
ρ
V
2
2
V
V
1
ρ
If
V
i
A
, a constant for all i,
this can be simplified to
W
λ
X
2
2
1
ρ
A
2
2
A
A
1
ρ
λ
X
2
2
1
ρ
A
1
ρ
2
A
2
1
ρ
λ
X
2
2
1
ρ
A
2
3
ρ
1
ρ
m>1
The case of one station has relatively little practical
application in computer networks, but the analysis does serve
as a convenient starting point for
m
1
stations. We first need to define some additional
notation:
-
Y
i
- r.v. for combined length of all of the whole
polling intervals during which packet
i must wait
-
N
i
- r.v. for total number of packets that must be
transmitted after the arrival of packet
i and before
i is transmitted (not
including any packet in service when
i arrives)
-
R
i
- r.v. for residual time for the packet or poll
in progress
-
Y
i
Y
i
A packet must wait
-
while the packet transmission or poll interval underway at
its arrival finishes;
-
for all packets which arrived before it but which had not
been serviced yet to be transmitted;
-
for the time required to transfer the polls from station
to station until the transmission interval in which the
packet will be transferred starts.
W
i
R
i
N
i
X
Y
i
As before
R
R
i
λ
X
2
2
1
ρ
r
0
m
1
V
r
2
2
r
0
m
1
V
r
Each packet transmitted before i
has an average transmission time
X
.
N
i
is not the number of packets ahead of
i in the queue at its arrival,
since packets might arrive at other stations after
i arrives, but actually be
transmitted before i because of
the polling cycle. However, by Little's Theorem,
i
N
i
X
λ
W
X
ρ
W
Consequently,
W
R
ρ
W
Y
R
Y
1
ρ
Y depends on the flavor (gated,
partially gated, or exhaustive) of polling network. We will
look at each.
Exhaustive System
α
j
k
is the expected value of
Y
i
given that packet i arrives in
user j's polling or data
interval and belongs to user
j
k
m
.
α
j
k
0
k
0
V
(
j
+
1
)
mod
m
…
V
(
j
+
k
)
mod
m
k
0
We first remove the condition that the packet belongs to
station
j
k
m
by assuming that a packet belongs to a particular
station with probability
1
m
for all stations. The expected value of
Y
i
given that packet i
arrives in user j's
polling or data interval is given by
1
m
k
1
m
1
α
j
k
k
1
m
1
m
k
m
V
(
j
+
k
)
mod
m
Since all users are identical, they have equal average length
data intervals in steady-state, and the steady-state
probability that a packet arrives in a particular user's data
interval is
ρ
m
. Similarly, the probability that a packet arrives
during a particular user's polling interval is
1
ρ
V
r
k
0
m
1
V
k
.
Y
r
0
m
1
ρ
m
1
ρ
V
r
k
0
m
1
V
k
j
1
m
1
m
r
m
V
(
r
+
j
)
mod
m
ρ
m
r
0
m
1
j
1
m
1
m
j
m
V
(
r
+
j
)
mod
m
1
ρ
k
0
m
1
V
k
r
0
m
1
V
r
j
1
m
1
m
j
m
V
(
r
+
j
)
mod
m
ρ
m
r
0
m
1
m
j
m
j
1
m
1
V
(
r
+
j
)
mod
m
1
ρ
k
0
m
1
V
k
r
0
m
1
j
1
m
1
m
j
m
V
r
V
(
r
+
j
)
mod
m
r
0
m
1
j
1
m
1
m
j
m
V
r
V
(
r
+
j
)
mod
m
r
0
m
1
j
0
m
1
m
j
m
V
r
V
(
r
+
j
)
mod
m
r
0
m
1
V
r
2
1
2
r
0
m
1
V
r
2
r
0
m
1
V
r
2
The mean polling interval length averaged over all users is
V
1
m
r
0
m
1
V
r
Thus
Y
ρ
m
j
1
m
1
m
j
V
1
ρ
2
m
V
m
V
2
r
0
m
1
V
r
2
ρ
V
m
j
1
m
1
m
j
1
ρ
m
V
2
1
ρ
r
0
m
1
V
r
2
2
m
V
ρ
V
m
1
m
1
ρ
m
V
2
1
ρ
r
0
m
1
V
r
2
2
m
V
m
ρ
V
2
1
ρ
r
0
m
1
V
r
2
2
m
V
Substituting these expressions for
R and
V
into the equation for
W,
W
λ
X
2
2
1
ρ
r
0
m
1
V
r
2
2
m
V
m
ρ
V
2
1
ρ
r
0
m
1
V
r
2
2
m
V
λ
X
2
2
1
ρ
m
ρ
V
2
1
ρ
r
0
m
1
V
r
2
V
r
2
2
m
V
Thus, for exhaustive gating,
W
λ
X
2
2
1
ρ
m
ρ
V
2
1
ρ
σ
V
2
2
V
Partially gated system
In the partially gated system, a packet that arrives during a
user's own data interval is delayed by an additional
m
V
on average, and this occurs with probability
ρ
m
, thus increasing Y by
ρ
V
compared to the exhaustive case.
W
λ
X
2
2
1
ρ
m
ρ
V
2
1
ρ
σ
V
2
2
V
Fully gated system
If the system is fully gated, then a packet that arrives
during a user's own polling interval is also delayed by an
average of
m
V
, and this is in addition to the extra delay incurred
in the partially gated case. The probability of this
occurring is
1
ρ
m
, thus increasing Y by
1
ρ
V
compared to the partially gated case.
W
λ
X
2
2
1
ρ
m
2
ρ
V
2
1
ρ
σ
V
2
2
V