Connexions

You are here: Home » Content » Polling Network Analysis
Content Actions

Polling Network Analysis

Module by: Bart Sinclair

Summary: (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 mm stations are independent Poisson processes with rate λm λ 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.
Example 1: gated system, m=1 
We define the following notation:
  • X¯ X - mean packet length in seconds
  • X2¯ X 2 - second principal moment of the packet length distribution
  • V r V r - r.v. for length of r th r th polling interval. V r V r are independent and identically distributed.
  • V¯=E V r V V r
  • V2¯=E V r 2 V 2 V r 2
  • R i R i - r.v. for residual time data packet ii must wait in queue until end of current packet transmission or polling interval
  • V r ( i ) V r ( i ) - r.v. for length of polling interval for data packet ii
  • ρ=λX¯ ρ λ 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). E W i =E R i +E N i X¯+E V r ( i ) 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. E R i =λX2¯2+1-ρV2¯2V¯ R i λ X 2 2 1 ρ V 2 2 V Also as before, limi→∞E N i X¯=limi→∞λE W i X¯=ρW i N i X i λ W i X ρ W limi→∞E V r ( i ) =V¯ i V r ( i ) V W=λX2¯2+1-ρV2¯2V¯+ρW+V¯=λX2¯21-ρ+V2¯2V¯+V¯1-ρ 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 V i A , a constant for all ii, this can be simplified to W=λX2¯21-ρ+A22A+A1-ρ=λX2¯21-ρ+A1-ρ+2A21-ρ=λX2¯21-ρ+A23-ρ1-ρ 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 ρ
Example 2: 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 m 1 stations. We first need to define some additional notation:
  • Y i Y i - r.v. for combined length of all of the whole polling intervals during which packet ii must wait
  • N i N i - r.v. for total number of packets that must be transmitted after the arrival of packet ii and before ii is transmitted (not including any packet in service when ii arrives)
  • R i R i - r.v. for residual time for the packet or poll in progress
  • Y=limi→∞E Y i Y i Y i
A packet must wait
  1. while the packet transmission or poll interval underway at its arrival finishes;
  2. for all packets which arrived before it but which had not been serviced yet to be transmitted;
  3. for the time required to transfer the polls from station to station until the transmission interval in which the packet will be transferred starts.
E W i =E R i +E N i X¯+E Y i W i R i N i X Y i As before R=E R i =λX2¯2+1-ρ∑r=0m-1 V r 2¯2∑r=0m-1 V r ¯ 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 ii has an average transmission time X¯ X . N i N i is not the number of packets ahead of ii in the queue at its arrival, since packets might arrive at other stations after ii arrives, but actually be transmitted before ii because of the polling cycle. However, by Little's Theorem, limi→∞E N i X¯=λWX¯=ρW i N i X λ W X ρ W Consequently, W=R+ρW+Y=R+Y1-ρ W R ρ W Y R Y 1 ρ YY depends on the flavor (gated, partially gated, or exhaustive) of polling network. We will look at each.

Exhaustive System

α j k α j k is the expected value of Y i Y i given that packet ii arrives in user jj's polling or data interval and belongs to user j+kmodm j k m . α j k =0ifk=0 V ( j + 1 ) mod m ¯+…+ V ( j + k ) mod m ¯ifk>0 α 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+kmodm j k m by assuming that a packet belongs to a particular station with probability 1m 1 m for all stations. The expected value of Y i Y i given that packet ii arrives in user jj's polling or data interval is given by 1m∑k=1m-1 α j k =∑k=1m-1m-km V ( j + k ) mod m ¯ 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 ρ m . Similarly, the probability that a packet arrives during a particular user's polling interval is 1-ρ V r ¯∑k=0m-1 V k ¯ 1 ρ V r k 0 m 1 V k .
Y=∑r=0m-1ρm+1-ρ V r ¯∑k=0m-1 V k ¯∑j=1m-1m-rm V ( r + j ) mod m ¯=ρm∑r=0m-1∑j=1m-1m-jm V ( r + j ) mod m ¯+1-ρ∑k=0m-1 V k ¯∑r=0m-1 V r ¯∑j=1m-1m-jm V ( r + j ) mod m ¯=ρm∑r=0m-1m-jm∑j=1m-1 V ( r + j ) mod m ¯+1-ρ∑k=0m-1 V k ¯∑r=0m-1∑j=1m-1m-jm V r ¯ V ( r + j ) mod m ¯ 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 (1)
∑r=0m-1∑j=1m-1m-jm V r ¯ V ( r + j ) mod m ¯=∑r=0m-1∑j=0m-1m-jm V r ¯ V ( r + j ) mod m ¯-∑r=0m-1 V r 2¯=12∑r=0m-1 V r ¯2-∑r=0m-1 V r 2¯ 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 (2)
The mean polling interval length averaged over all users is V¯=1m∑r=0m-1 V r ¯ V 1 m r 0 m 1 V r Thus
Y=ρm∑j=1m-1m-jV¯+1-ρ2mV¯mV¯2-∑r=0m-1 V r 2¯=ρV¯m∑j=1m-1m-j+1-ρmV¯2-1-ρ∑r=0m-1 V r 2¯2mV¯=ρV¯m-1m+1-ρmV¯2-1-ρ∑r=0m-1 V r 2¯2mV¯=m-ρV¯2-1-ρ∑r=0m-1 V r 2¯2mV¯ 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 (3)
Substituting these expressions for RR and V¯ V into the equation for WW,
W=λX2¯21-ρ+∑r=0m-1 V r 2¯2mV¯+m-ρV¯21-ρ-∑r=0m-1 V r 2¯2mV¯=λX2¯21-ρ+m-ρV¯21-ρ+∑r=0m-1 V r 2¯- V r 2¯2mV¯ 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 (4)
Thus, for exhaustive gating, W=λX2¯21-ρ+m+ρV¯21-ρ+ σ V 22V¯ 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 mV¯ m V on average, and this occurs with probability ρm ρ m , thus increasing YY by ρV¯ ρ V compared to the exhaustive case. W=λX2¯21-ρ+m+ρV¯21-ρ+ σ V 22V¯ 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 mV¯ 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 1 ρ m , thus increasing YY by 1-ρV¯ 1 ρ V compared to the partially gated case. W=λX2¯21-ρ+m+2-ρV¯21-ρ+ σ V 22V¯ W λ X 2 2 1 ρ m 2 ρ V 2 1 ρ σ V 2 2 V

Comments, questions, feedback, criticisms?

Send feedback