Tag: Token Passing in Computer Networks

Token Passing | Token Ring in Networking

Access Control in Networking-

 

Before you go through this article, make sure that you have gone through the previous article on Access Control.

 

We have discussed-

  • Access Control is a mechanism that controls the access of stations to the transmission link.
  • Broadcast links require the access control mechanism.
  • There are various access control methods-

 

 

  1. Time Division Multiplexing
  2. Polling
  3. CSMA / CD
  4. Token Passing
  5. Aloha

 

In this article, we will discuss about Token Passing.

 

Before discussing Token Passing, let us discuss few important concepts required for the discussion.

 

Time Conversions-

 

In token passing,

  • Time may be expressed in seconds, bits or meters.
  • To convert the time from one unit to another, we use the following conversion chart-

 

 

Conversion Chart

 

Token Passing Terminology-

 

The following terms are frequently used-

  1. Token
  2. Ring Latency
  3. Cycle Time

 

1. Token-

 

  • A token is a small message composed of a special bit pattern.
  • It represents the permission to send the data packet.
  • A station is allowed to transmit a data packet if and only if it possess the token otherwise not.

 

2. Ring Latency-

 

Time taken by a bit to complete one revolution of the ring is called as ring latency.

 

 

Let us derive the expression for ring latency.

If-

  • Length of the ring = d
  • Speed of the bit = v
  • Number of stations = N
  • Bit delay at each station = b

(Bit delay is the time for which a station holds the bit before transmitting to the other side)

Then-

 

 

Notes-

 

  • d / v is the propagation delay (Tp) expressed in seconds.
  • Generally, bit delay is expressed in bits.
  • So, both the terms (d / v and N x b) have different units.
  • While calculating the ring latency, both the terms are brought into the same unit.
  • The above conversion chart is used for conversion.

 

After conversion, we have-

 

 

3. Cycle Time-

 

Time taken by the token to complete one revolution of the ring is called as cycle time.

 

If-

  • Length of the ring = d
  • Speed of the bit = v
  • Number of stations = N
  • Token Holding Time = THT

(Token Holding Time is the time for which a station holds the token before transmitting to the other side)

Then-

 

 

Now, we start discussing about Token Passing Access Control Method.

 

Token Passing-

 

In this access control method,

  • All the stations are logically connected to each other in the form of a ring.
  • The access of stations to the transmission link is governed by a token.
  • A station is allowed to transmit a data packet if and only if it possess the token otherwise not.
  • Each station passes the token to its neighboring station either clockwise or anti-clockwise.

 

 

Assumptions-

 

Token passing method assumes-

  • Each station in the ring has the data to send.
  • Each station sends exactly one data packet after acquiring the token.

 

Efficiency-

 

Efficiency (η) = Useful Time / Total Time

 

In one cycle,

  • Useful time = Sum of transmission delay of N stations since each station sends 1 data packet = N x Tt
  • Total Time = Cycle time = Tp + N x THT

Thus,

 

 

Token Holding Time depends on the strategy implemented.

 

Token Passing Strategies-

 

The following 2 strategies are used in token passing-

 

 

  1. Delayed Token Reinsertion (DTR)
  2. Early Token Reinsertion (ETR)

 

1. Delayed Token Reinsertion-

 

In this strategy,

  • Station keeps holding the token until the last bit of the data packet transmitted by it takes the complete revolution of the ring and comes back to it.

 

Working-

 

After a station acquires the token,

  • It transmits its data packet.
  • It holds the token until the data packet reaches back to it.
  • After data packet reaches to it, it discards its data packet as its journey is completed.
  • It releases the token.

 

The following diagram illustrates these steps for station-1. Same procedure is repeated at every station.

 

 

Token Holding Time-

 

Token Holding Time (THT) = Transmission delay + Ring Latency

 

We know,

  • Ring Latency = Tp + N x bit delay
  • Assuming bit delay = 0 (in most cases), we get-

 

Token Holding Time = Tt + Tp

 

Efficiency-

 

Substituting THT = Tt + Tp in the efficiency expression, we get-

 

 

2. Early Token Reinsertion-

 

In this strategy,

  • Station releases the token immediately after putting its data packet to be transmitted on the ring.

 

Working-

 

 

Step-01: At Station-1:

 

Station-1

  • Acquires the token
  • Transmits packet-1
  • Releases the token

 

Step-02: At Station-2:

 

Station-2

  • Receives packet-1
  • Transmits packet-1
  • Acquires the token
  • Transmits packet-2
  • Releases the token

 

Step-03: At Station-3:

 

Station-3

  • Receives packet-1
  • Transmits packet-1
  • Receives packet-2
  • Transmits packet-2
  • Acquires the token
  • Transmits packet-3
  • Releases the token

 

Step-04: At Station-4:

 

Station-4

  • Receives packet-1
  • Transmits packet-1
  • Receives packet-2
  • Transmits packet-2
  • Receives packet-3
  • Transmits packet-3
  • Acquires the token
  • Transmits packet-4
  • Releases the token

 

Step-05: At Station-1:

 

  • Receives packet-1
  • Discards packet-1 (as its journey is completed)
  • Receives packet-2
  • Transmits packet-2
  • Receives packet-3
  • Transmits packet-3
  • Receives packet-4
  • Transmits packet-4
  • Acquires the token
  • Transmits packet-1 (new)
  • Releases the token

In this manner, the cycle continues.

 

Token Holding Time-

 

Token Holding Time (THT) = Transmission delay of data packet = Tt

 

Efficiency-

 

Substituting THT = Tt in the efficiency expression, we get-

 

 

Differences between DTR and ETR-

 

Delay Token Retransmission (DTR)Early Token Retransmission (ETR)
Each station holds the token until its data packet reaches back to it.Each station releases the token immediately after putting its data packet on the ring.
There exists only one data packet on the ring at any given instance.There exists more than one data packet on the ring at any given instance.
It is more reliable than ETR.It is less reliable than DTR.
It has low efficiency as compared to ETR.It has high efficiency as compared to ETR.

 

Important Notes-

 

Note-01:

 

In token passing,

  • It is the responsibility of each transmitting station to remove its own data packet from the ring.

 

Note-02:

 

While solving questions,

  • If the strategy used is not mentioned, then consider Early Token Retransmission strategy.

 

To gain better understanding about Token Passing Method,

Watch this Video Lecture

 

Next Article- Practice Problems On Token Passing

 

Get more notes and other study material of Computer Networks.

Watch video lectures by visiting our YouTube channel LearnVidFun.