Subjects | Gate Vidyalay

Category: Subjects

Stop and Wait Protocol | Practice Problems

Stop and Wait Protocol-

Before you go through this article, make sure that you have gone through the previous article on Stop and Wait Protocol.

We have discussed-

Stop and wait protocol is a simplest flow control protocol.
Sender sends a data packet to the receiver and then waits for its acknowledgement.
On receiving the acknowledgement, sender sends the next data packet.

Also Read- Stop and Wait ARQ

In this article, we will discuss practice problems based on stop and wait protocol.

PRACTICE PROBLEMS BASED ON STOP AND WAIT PROTOCOL-

Problem-01:

If the bandwidth of the line is 1.5 Mbps, RTT is 45 msec and packet size is 1 KB, then find the link utilization in stop and wait.

Solution-

Given-

Bandwidth = 1.5 Mbps
RTT = 45 msec
Packet size = 1 KB

Calculating Transmission Delay-

Transmission delay (T_t)

= Packet size / Bandwidth

= 1 KB / 1.5 Mbps

= (2¹⁰ x 8 bits) / (1.5 x 10⁶ bits per sec)

= 5.461 msec

Calculating Propagation Delay-

Propagation delay (T_p)

= Round Trip Time / 2

= 45 msec / 2

= 22.5 msec

Calculating Value Of ‘a’-

a = T_p / T_t

a = 22.5 msec / 5.461 msec

a = 4.12

Calculating Link Utilization-

Link Utilization or Efficiency (η)

= 1 / 1+2a

= 1 / (1 + 2 x 4.12)

= 1 / 9.24

= 0.108

= 10.8 %

Problem-02:

A channel has a bit rate of 4 Kbps and one way propagation delay of 20 msec. The channel uses stop and wait protocol. The transmission time of the acknowledgement frame is negligible. To get a channel efficiency of at least 50%, the minimum frame size should be-

80 bytes
80 bits
160 bytes
160 bits

Solution-

Given-

Bandwidth = 4 Kbps
Propagation delay (T_p) = 20 msec
Efficiency >= 50%

Let the required frame size = L bits.

Calculating Transmission Delay-

Transmission delay (T_t)

= Packet size / Bandwidth

= L bits / 4 Kbps

Calculating Value Of ‘a’-

a = T_p / T_t

a = 20 msec / ( L bits / 4 Kbps)

a = (20 msec x 4 Kbps) / L bits

Condition For Efficiency To Be At least 50%-

For efficiency to be at least 50%, we must have-

1 / 1+2a >= 1/2

a <= 1/2

Substituting the value of ‘a’, we get-

(20 msec x 4 Kbps) / L bits <= 1/2

L bits >= (20 msec x 4 Kbps) x 2

L bits >= (20 x 10^-3 sec x 4 x 10³ bits per sec) x 2

L bits >= 20 x 4 bits x 2

L >= 160

From here, frame size must be at least 160 bits.

Thus, Correct Option is (D).

Problem-03:

What is the throughput achievable in stop and wait protocol by a maximum packet size of 1000 bytes and network span of 10 km.

Assume the speed of light in cable is 70% of the speed of light in vaccum.

Solution-

We have-

In the given question, we are not provided with the network’s bandwidth.
So, in the above formula of throughput, we have ignored the term T_t from the denominator.
Although it is incorrect, but we still ignore it for solving the question.

Now, Given-

L = 1000 bytes
d = 10 km = 10⁴ m
v = 70% of 3 x 10⁸ m/sec = 2.1 x 10⁸ m/sec

Substituting the values in the above relation, we get-

Throughput

= 1000 bytes / [ 2 x 10⁴ m / (2.1 x 10⁸ m/sec)]

= 1.05 x 10⁷ bytes per sec

= 10.5 MBps

Problem-04:

If the packet size is 1 KB and propagation time is 15 msec, the channel capacity is 10⁹ b/sec, then find the transmission time and utilization of sender in stop and wait protocol.

Solution-

Given-

Packet size = 1 KB
Propagation time (T_p) = 15 msec
Channel capacity = Bandwidth (here) = 10⁹ b/sec

NOTE-

Generally, channel capacity is the total number of bits which a channel can hold. So, its unit is bits.
But here, channel capacity is actually given as bandwidth because its unit is b/sec.

Calculating Transmission Delay-

Transmission delay (T_t)

= Packet size / Bandwidth

= 1 KB / 10⁹ bits per sec

= 2¹⁰ bits / 10⁹ bits per sec

= 1.024 μsec

Calculating Value Of ‘a’-

a = T_p / T_t

a = 15 msec / 1.024 μsec

a = 15000 μsec / 1.024 μsec

a = 14648.46

Calculating Sender Utilization-

Sender Utilization or Efficiency (η)

= 1 / 1+2a

= 1 / (1 + 2 x 1468.46)

= 1 / 29297.92

= 0.0000341

= 0.00341 %

Problem-05:

Consider a MAN with average source and destination 20 Km apart and one way delay of 100 μsec. At what data rate does the round trip delay equals the transmission delay for a 1 KB packet?

Solution-

Given-

Distance = 20 Km
Propagation delay (T_p) = 100 μsec
Packet size = 1 KB

We need to have-

Round Trip Time = Transmission delay

2 x Propagation delay = Transmission delay

Substituting the values in the above relation, we get-

2 x 100 μsec = 1 KB / Bandwidth

Bandwidth = 1 KB / 200 μsec

Bandwidth = (2¹⁰ x 10⁶ / 200 ) bytes per sec

Bandwidth = 5.12 MBps or 40.96 Mbps

Problem-06:

Consider two hosts X and Y connected by a single direct link of rate 10⁶ bits/sec. The distance between the two hosts is 10,000 km and the propagation speed along the link is 2 x 10⁸ m/sec. Host X sends a file of 50,000 bytes as one large message to host Y continuously. Let the transmission and propagation delays be p milliseconds and q milliseconds respectively.

Then the value of p and q are-

p = 50 and q = 100
p = 50 and q = 400
p = 100 and q = 50
p = 400 and q = 50

Solution-

Given-

Bandwidth = 10⁶ bits/sec
Distance = 10,000 km
Propagation speed = 2 x 10⁸ m/sec
Packet size = 50,000 bytes

Calculating Transmission Delay-

Transmission delay (T_t)

= Packet size / Bandwidth

= 50000 bytes / 10⁶ bits per sec

= (5 x 10⁴ x 8 bits) / 10⁶ bits per sec

= ( 4 x 10⁵ bits ) / 10⁶ bits per sec

= 0.4 sec

= 400 msec

Calculating Propagation Delay-

Propagation delay (T_p)

= Distance / Propagation speed

= 10000 km / (2 x 10⁸ m/sec)

= 10⁷ m / (2 x 10⁸ m/sec)

= 50 msec

Thus, Option (D) is correct.

Problem-07:

The values of parameters for the stop and wait ARQ protocol are as given below-

Bit rate of the transmission channel = 1 Mbps
Propagation delay from sender to receiver = 0.75 ms
Time to process a frame = 0.25 ms
Number of bytes in the information frame = 1980
Number of bytes in the acknowledge frame = 20
Number of overhead bytes in the information frame = 20

Assume that there are no transmission errors. Then the transmission efficiency (in %) of the stop and wait ARQ protocol for the above parameters is ___________ . (correct to 2 decimal places)

Solution-

Given-

Bandwidth = 1 Mbps
Propagation delay (T_p) = 0.75 ms
Processing time (T_process) = 0.25 ms
Data frame size = 1980 bytes
Acknowledgement frame size = 20 bytes
Overhead in data frame = 20 bytes

Calculating Useful Time-

Useful data sent

= Transmission delay of useful data bytes sent

= Useful data bytes sent / Bandwidth

= (1980 bytes – 20 bytes) / 1 Mbps

= 1960 bytes / 1 Mbps

= (1960 x 8 bits) / (10⁶ bits per sec)

= 15680 μsec

= 15.680 msec

Calculating Total Time-

Total time

= Transmission delay of data frame + Propagation delay of data frame + Processing delay of data frame + Transmission delay of acknowledgement + Propagation delay of acknowledgement

= (1980 bytes / 1 Mbps) + 0.75 msec + 0.25 msec + (20 bytes / 1 Mbps) + 0.75 msec

= 15.840 msec + 0.75 msec + 0.25 msec + 0.160 msec + 0.75 msec

= 17.75 msec

Calculating Efficiency-

Efficiency (η)

= Useful time / Total time

= 15.680 msec / 17.75 msec

= 0.8833

= 88.33%

Problem-08:

A sender uses the stop and wait ARQ protocol for reliable transmission of frames. Frames are of size 1000 bytes and the transmission rate at the sender is 80 Kbps. Size of an acknowledgement is 100 bytes and the transmission rate at the receiver is 8 Kbps. The one way propagation delay is 100 msec.

Assuming no frame is lost, the sender throughput is __________ bytes/sec.

Solution-

Given-

Frame size = 1000 bytes
Sender bandwidth = 80 Kbps
Acknowledgement size = 100 bytes
Receiver bandwidth = 8 Kbps
Propagation delay (T_p) = 100 msec

Calculating Transmission Delay Of Data Frame-

Transmission delay (T_t)

= Frame size / Sender bandwidth

= 1000 bytes / 80 Kbps

= (1000 x 8 bits) / (80 x 10³ bits per sec)

= 0.1 sec

= 100 msec

Calculating Transmission Delay Of Acknowledgement-

Transmission delay (T_t)

= Acknowledgement size / Receiver bandwidth

= 100 bytes / 8 Kbps

= (100 x 8 bits) / (8 x 10³ bits per sec)

= 100 msec

Calculating Useful Time-

Useful Time

= Transmission delay of data frame

= 100 msec

Calculating Total Time-

Total Time

= Transmission delay of data frame + Propagation delay of data frame + Transmission delay of acknowledgement + Propagation delay of acknowledgement

= 100 msec + 100 msec + 100 msec + 100 msec

= 400 msec

Calculating Efficiency-

Efficiency (η)

= Useful time / Total time

= 100 msec / 400 msec

= 1 / 4

= 25%

Calculating Sender Throughput-

Sender throughput

= Efficiency (η) x Sender bandwidth

= 0.25 x 80 Kbps

= 20 Kbps

= (20 x 1000 / 8) bytes per sec

= 2500 bytes/sec

Problem-09:

Using stop and wait protocol, sender wants to transmit 10 data packets to the receiver. Out of these 10 data packets, every 4th data packet is lost. How many packets sender will have to send in total?

Solution-

Draw a time line diagram and analyze.

The packets will be sent as-

1, 2, 3, 4, 4, 5, 6, 7, 7, 8, 9, 10, 10

The lost packets are- 4, 7 and 10.

Thus, sender will have to send 13 data packets in total.

Next Article- Sliding Window Protocol

Get more notes and other study material of Computer Networks.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Distance Vector Routing Algorithm | Example

Computer Networks

Routing Algorithms-

Routing algorithms are meant for determining the routing of packets in a node.
Routing algorithms are classified as-

Static Routing Algorithms
Dynamic Routing Algorithms

In this article, we will discuss about distance vector routing.

Distance Vector Routing Algorithm-

Distance Vector Routing is a dynamic routing algorithm.

It works in the following steps-

Step-01:

Each router prepares its routing table. By their local knowledge. each router knows about-

All the routers present in the network
Distance to its neighboring routers

Step-02:

Each router exchanges its distance vector with its neighboring routers.
Each router prepares a new routing table using the distance vectors it has obtained from its neighbors.
This step is repeated for (n-2) times if there are n routers in the network.
After this, routing tables converge / become stable.

Distance Vector Routing Example-

Consider-

There is a network consisting of 4 routers.
The weights are mentioned on the edges.
Weights could be distances or costs or delays.

Step-01:

Each router prepares its routing table using its local knowledge.

Routing table prepared by each router is shown below-

At Router A-

Destination	Distance	Next Hop
A	0	A
B	2	B
C	∞	–
D	1	D

At Router B-

Destination	Distance	Next Hop
A	2	A
B	0	B
C	3	C
D	7	D

At Router C-

Destination	Distance	Next Hop
A	∞	–
B	3	B
C	0	C
D	11	D

At Router D-

Destination	Distance	Next Hop
A	1	A
B	7	B
C	11	C
D	0	D

Step-02:

Each router exchanges its distance vector obtained in Step-01 with its neighbors.
After exchanging the distance vectors, each router prepares a new routing table.

This is shown below-

At Router A-

Router A receives distance vectors from its neighbors B and D.
Router A prepares a new routing table as-

Cost of reaching destination B from router A = min { 2+0 , 1+7 } = 2 via B.
Cost of reaching destination C from router A = min { 2+3 , 1+11 } = 5 via B.
Cost of reaching destination D from router A = min { 2+7 , 1+0 } = 1 via D.

Explanation For Destination B

Router A can reach the destination router B via its neighbor B or neighbor D.
It chooses the path which gives the minimum cost.
Cost of reaching router B from router A via neighbor B = Cost (A→B) + Cost (B→B)= 2 + 0 = 2
Cost of reaching router B from router A via neighbor D = Cost (A→D) + Cost (D→B) = 1 + 7 = 8
Since the cost is minimum via neighbor B, so router A chooses the path via B.
It creates an entry (2, B) for destination B in its new routing table.
Similarly, we calculate the shortest path distance to each destination router at every router.

Thus, the new routing table at router A is-

Destination	Distance	Next Hop
A	0	A
B	2	B
C	5	B
D	1	D

At Router B-

Router B receives distance vectors from its neighbors A, C and D.
Router B prepares a new routing table as-

Cost of reaching destination A from router B = min { 2+0 , 3+∞ , 7+1 } = 2 via A.
Cost of reaching destination C from router B = min { 2+∞ , 3+0 , 7+11 } = 3 via C.
Cost of reaching destination D from router B = min { 2+1 , 3+11 , 7+0 } = 3 via A.

Thus, the new routing table at router B is-

Destination	Distance	Next Hop
A	2	A
B	0	B
C	3	C
D	3	A

At Router C-

Router C receives distance vectors from its neighbors B and D.
Router C prepares a new routing table as-

Cost of reaching destination A from router C = min { 3+2 , 11+1 } = 5 via B.
Cost of reaching destination B from router C = min { 3+0 , 11+7 } = 3 via B.
Cost of reaching destination D from router C = min { 3+7 , 11+0 } = 10 via B.

Thus, the new routing table at router C is-

Destination	Distance	Next Hop
A	5	B
B	3	B
C	0	C
D	10	B

At Router D-

Router D receives distance vectors from its neighbors A, B and C.
Router D prepares a new routing table as-

Cost of reaching destination A from router D = min { 1+0 , 7+2 , 11+∞ } = 1 via A.
Cost of reaching destination B from router D = min { 1+2 , 7+0 , 11+3 } = 3 via A.
Cost of reaching destination C from router D = min { 1+∞ , 7+3 , 11+0 } = 10 via B.

Thus, the new routing table at router D is-

Destination	Distance	Next Hop
A	1	A
B	3	A
C	10	B
D	0	D

Step-03:

Each router exchanges its distance vector obtained in Step-02 with its neighboring routers.
After exchanging the distance vectors, each router prepares a new routing table.

This is shown below-

At Router A-

Router A receives distance vectors from its neighbors B and D.
Router A prepares a new routing table as-

Cost of reaching destination B from router A = min { 2+0 , 1+3 } = 2 via B.
Cost of reaching destination C from router A = min { 2+3 , 1+10 } = 5 via B.
Cost of reaching destination D from router A = min { 2+3 , 1+0 } = 1 via D.

Thus, the new routing table at router A is-

Destination	Distance	Next Hop
A	0	A
B	2	B
C	5	B
D	1	D

At Router B-

Router B receives distance vectors from its neighbors A, C and D.
Router B prepares a new routing table as-

Cost of reaching destination A from router B = min { 2+0 , 3+5 , 3+1 } = 2 via A.
Cost of reaching destination C from router B = min { 2+5 , 3+0 , 3+10 } = 3 via C.
Cost of reaching destination D from router B = min { 2+1 , 3+10 , 3+0 } = 3 via A.

Thus, the new routing table at router B is-

Destination	Distance	Next Hop
A	2	A
B	0	B
C	3	C
D	3	A

At Router C-

Router C receives distance vectors from its neighbors B and D.
Router C prepares a new routing table as-

Cost of reaching destination A from router C = min { 3+2 , 10+1 } = 5 via B.
Cost of reaching destination B from router C = min { 3+0 , 10+3 } = 3 via B.
Cost of reaching destination D from router C = min { 3+3 , 10+0 } = 6 via B.

Thus, the new routing table at router C is-

Destination	Distance	Next Hop
A	5	B
B	3	B
C	0	C
D	6	B

At Router D-

Router D receives distance vectors from its neighbors A, B and C.
Router D prepares a new routing table as-

Cost of reaching destination A from router D = min { 1+0 , 3+2 , 10+5 } = 1 via A.
Cost of reaching destination B from router D = min { 1+2 , 3+0 , 10+3 } = 3 via A.
Cost of reaching destination C from router D = min { 1+5 , 3+3 , 10+0 } = 6 via A.

Thus, the new routing table at router D is-

Destination	Distance	Next Hop
A	1	A
B	3	A
C	6	A
D	0	D

These will be the final routing tables at each router.

Identifying Unused Links-

After routing tables converge (becomes stable),

Some of the links connecting the routers may never be used.
In the above example, we can identify the unused links as-

We have-

The value of next hop in the final routing table of router A suggests that only edges AB and AD are used.
The value of next hop in the final routing table of router B suggests that only edges BA and BC are used.
The value of next hop in the final routing table of router C suggests that only edge CB is used.
The value of next hop in the final routing table of router D suggests that only edge DA is used.

Thus, edges BD and CD are never used.

Important Notes-

Note-01:

In Distance Vector Routing,

Only distance vectors are exchanged.
“Next hop”values are not exchanged.
This is because it results in exchanging the large amount of data which consumes more bandwidth.

Note-02:

While preparing a new routing table-

A router takes into consideration only the distance vectors it has obtained from its neighboring routers.
It does not take into consideration its old routing table.

Note-03:

The algorithm is called so because-

It involves exchanging of distance vectors between the routers.
Distance vector is nothing but an array of distances.

Note-04:

The algorithm keeps on repeating periodically and never stops.
This is to update the shortest path in case any link goes down or topology changes.

Note-05:

Routing tables are prepared total (n-1) times if there are n routers in the given network.
This is because shortest path between any 2 nodes contains at most n-1 edges if there are n nodes in the graph.

Note-06:

Distance Vector Routing suffers from count to infinity problem.
Distance Vector Routing uses UDP at transport layer.

Next Article- IP Address | Classes of IP Address

Get more notes and other study material of Computer Networks.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Aloha | Pure Aloha | Slotted Aloha

Computer Networks

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-

In this article, we will discuss about Aloha and its versions.

Aloha-

There are two different versions of Aloha-

Pure Aloha
Slotted Aloha

1. Pure Aloha-

It allows the stations to transmit data at any time whenever they want.
After transmitting the data packet, station waits for some time.

Then, following 2 cases are possible-

Case-01:

Transmitting station receives an acknowledgement from the receiving station.
In this case, transmitting station assumes that the transmission is successful.

Case-02:

Transmitting station does not receive any acknowledgement within specified time from the receiving station.
In this case, transmitting station assumes that the transmission is unsuccessful.

Then,

Transmitting station uses a Back Off Strategy and waits for some random amount of time.
After back off time, it transmits the data packet again.
It keeps trying until the back off limit is reached after which it aborts the transmission.

Efficiency-

Efficiency of Pure Aloha (η) = G x e^-2G

where G = Number of stations willing to transmit data

Maximum Efficiency-

For maximum efficiency,

We put dη / dG = 0
Maximum value of η occurs at G = 1/2
Substituting G = 1/2 in the above expression, we get-

Maximum efficiency of Pure Aloha

= 1/2 x e^{-2 x 1/2}

= 1 / 2e

= 0.184

= 18.4%

Thus,

Maximum Efficiency of Pure Aloha (η) = 18.4%

The maximum efficiency of Pure Aloha is very less due to large number of collisions.

2. Slotted Aloha-

Slotted Aloha divides the time of shared channel into discrete intervals called as time slots.
Any station can transmit its data in any time slot.
The only condition is that station must start its transmission from the beginning of the time slot.
If the beginning of the slot is missed, then station has to wait until the beginning of the next time slot.
A collision may occur if two or more stations try to transmit data at the beginning of the same time slot.

Efficiency-

Efficiency of Slotted Aloha (η) = G x e^-G

where G = Number of stations willing to transmit data at the beginning of the same time slot

Maximum Efficiency-

For maximum efficiency,

We put dη / dG = 0
Maximum value of η occurs at G = 1
Substituting G = 1 in the above expression, we get-

Maximum efficiency of Slotted Aloha

= 1 x e^-1

= 1 / e

= 0.368

= 36.8%

Thus,

Maximum Efficiency of Slotted Aloha (η) = 36.8%

The maximum efficiency of Slotted Aloha is high due to less number of collisions.

Difference Between Pure Aloha And Slotted Aloha-

Pure Aloha	Slotted Aloha
Any station can transmit the data at any time.	Any station can transmit the data at the beginning of any time slot.
The time is continuous and not globally synchronized.	The time is discrete and globally synchronized.
Vulnerable time in which collision may occur = 2 x T_t	Vulnerable time in which collision may occur = T_t
Probability of successful transmission of data packet = G x e-^2G	Probability of successful transmission of data packet = G x e-^G
Maximum efficiency = 18.4% (Occurs at G = 1/2)	Maximum efficiency = 36.8% ( Occurs at G = 1)
The main advantage of pure aloha is its simplicity in implementation.	The main advantage of slotted aloha is that it reduces the number of collisions to half and doubles the efficiency of pure aloha.

PRACTICE PROBLEM BASED ON PURE ALOHA AND SLOTTED ALOHA-

Problem-

A group of N stations share 100 Kbps slotted ALOHA channel. Each station output a 500 bits frame on an average of 5000 ms even if previous one has not been sent. What is the required value of N?

Solution-

Throughput Of One Station-

Throughput of each station

= Number of bits sent per second

= 500 bits / 5000 ms

= 500 bits / (5000 x 10^-3 sec)

= 100 bits/sec

Throughput Of Slotted Aloha-

Throughput of slotted aloha

= Efficiency x Bandwidth

= 0.368 x 100 Kbps

= 36.8 Kbps

Total Number Of Stations-

Throughput of slotted aloha = Total number of stations x Throughput of each station

Substituting the values, we get-

36.8 Kbps = N x 100 bits/sec

∴ N = 368

Thus, required value of N = 368.

To gain better understanding about Aloha,

Watch this Video Lecture

Next Article- Ethernet | Ethernet Frame Format

Get more notes and other study material of Computer Networks.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Token Passing | Token Ring in Networking

Computer Networks

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-

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-

Token
Ring Latency
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 (T_p) 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 T_t
Total Time = Cycle time = T_p + N x THT

Thus,

Token Holding Time depends on the strategy implemented.

Token Passing Strategies-

The following 2 strategies are used in token passing-

Delayed Token Reinsertion (DTR)
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 = T_p + N x bit delay
Assuming bit delay = 0 (in most cases), we get-

Token Holding Time = T_t + T_p

Efficiency-

Substituting THT = T_t + T_p 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 = T_t

Efficiency-

Substituting THT = T_t 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.

Binary Exponential BackOff Algorithm | CSMA CD

Computer Networks

CSMA / CD Protocol-

Before you go through this article, make sure that you have gone through the previous article on CSMA / CD Protocol.

We have discussed-

CSMA / CD stands for Carrier Sense Multiple Access / Collision Detection.
It allows the stations to sense the carrier and transmit data if the carrier is free.

The following CSMA / CD flowchart shows the CSMA / CD procedure-

Back Off Time-

In CSMA / CD protocol,

After the occurrence of collision, station waits for some random back off time and then retransmits.
This waiting time for which the station waits before retransmitting the data is called as back off time.
Back Off Algorithm is used for calculating the back off time.

Back Off Algorithm-

After undergoing the collision,

Transmitting station chooses a random number in the range [0, 2ⁿ-1] if the packet is undergoing collision for the n^th time.
If station chooses a number k, then-

Back off time = k x Time slot

where value of one time slot = 1 RTT

Example-

Consider the following scenario where stations A and D start transmitting their data simultaneously-

For simplicity,

We consider the value of time slot = 1 unit.
Thus, back off time = K units.

Scene-01: For 1st Data Packet Of Both Stations-

Both the stations start transmitting their 1^st data packet simultaneously.
This leads to a collision.
Clearly, the collision on both the packets is occurring for the 1^st time.
So, collision number for the 1^st data packet of both the stations = 1.

At Station A-

After detecting the collision,

Station A randomly chooses a number in the range [0, 2¹-1] = [0,1].
If station A chooses the number K_A, then back off time = K_A units.

At Station D-

After detecting the collision,

Station D randomly chooses a number in the range [0, 2¹-1] = [0,1].
If station D chooses the number K_D, then back off time = K_D units.

Following 4 cases are possible-

K_A	K_D	Remarks
0	0	In this case, both the stations start retransmitting their data immediately. This case leads to a collision again.
0	1	In this case, station A starts retransmitting its data immediately while station D waits for 1 unit of time. This case leads to A successfully retransmitting its data after the 1^st collision.
1	0	In this case, station A waits for 1 unit of time while station D starts retransmitting its data immediately. This case leads to D successfully retransmitting its data after the 1^st collision.
1	1	In this case, both the stations wait for 1 unit of time and then starts retransmitting their data simultaneously. This case leads to a collision again.

From here,

Probability of station A to successfully retransmit its data after the 1^st collision = 1 / 4
Probability of station D to successfully retransmit its data after the 1^st collision = 1 / 4
Probability of occurrence of collision again after the 1^st collision = 2 / 4 = 1 / 2

Now,

Consider case-02 occurs.
This causes station A to successfully retransmit its 1^st packet after the 1^st collision.

Scene-02: For 2nd Data Packet Of Station A And 1st Data Packet Of Station D-

Consider after some time,

Station A starts transmitting its 2^nd data packet and station D starts retransmitting its 1^st data packet simultaneously.
This leads to a collision.

At Station A-

The 2^nd data packet of station A undergoes collision for the 1^st time.
So, collision number for the 2^nd data packet of station A = 1.
Now, station A randomly chooses a number in the range [0, 2¹-1] = [0,1].
If station A chooses the number K_A, then back off time = K_A units.

At Station D-

The 1^st data packet of station D undergoes collision for the 2^nd time.
So, collision number for the 1^st data packet of station D = 2.
Now, station D randomly chooses a number in the range [0, 2²-1] = [0,3].
If station D chooses the number K_D, then back off time = K_D units.

Following 8 cases are possible-

K_A	K_D	Remarks
0	0	In this case, both the stations start retransmitting their data immediately. This case leads to a collision again.
0	1	In this case, station A starts retransmitting its data immediately while station D waits for 1 unit of time. This case leads to A successfully retransmitting its data after the 2^nd collision.
0	2	In this case, station A starts retransmitting its data immediately while station D waits for 2 unit of time. This case leads to A successfully retransmitting its data after the 2^nd collision.
0	3	In this case, station A starts retransmitting its data immediately while station D waits for 3 unit of time. This case leads to A successfully retransmitting its data after the 2^nd collision.
1	0	In this case, station A waits for 1 unit of time while station D starts retransmitting its data immediately. This case leads to D successfully retransmitting its data after the 2^nd collision.
1	1	In this case, both the stations wait for 1 unit of time and then starts retransmitting their data simultaneously. This case leads to a collision again.
1	2	In this case, station A waits for 1 unit of time while station D waits for 2 unit of time. This case leads to A successfully retransmitting its data after the 2^nd collision.
1	3	In this case, station A waits for 1 unit of time while station D waits for 3 unit of time. This case leads to A successfully retransmitting its data after the 2^nd collision.

From here,

Probability of station A to successfully retransmit its data after the 2^nd collision = 5 / 8
Probability of station D to successfully retransmit its data after the 2^nd collision = 1 / 8
Probability of occurrence of collision again after the 2^nd collision = 2 / 8 = 1 / 4

Now,

Consider case-03 occurs.
This causes station A to successfully retransmit its 2^nd packet after the 2^nd collision.

Scene-03: For 3rd Data Packet Of Station A And 1st Data Packet Of Station D-

Consider after some time,

Station A starts transmitting its 3^rd data packet and station D starts retransmitting its 1^st data packet simultaneously.
This leads to a collision.

At Station A-

The 3^rd data packet of station A undergoes collision for the 1^st time.
So, collision number for the 3^rd data packet of station A = 1.
Now, station A randomly chooses a number in the range [0, 2¹-1] = [0,1].
If station A chooses the number K_A, then back off time = K_A unit.

At Station D-

The 1^st data packet of station D undergoes collision for the 3^rd time.
So, collision number for the 1^st data packet of station D = 3.
Now, station D randomly chooses a number in the range [0, 2³-1] = [0,7].
If station D chooses the number K_D, then back off time = K_D unit.

Following 16 cases are possible-

K_A	K_D	Remarks
0	0	In this case, both the stations start retransmitting their data immediately. This case leads to a collision again.
0	1	In this case, station A starts retransmitting its data immediately while station D waits for 1 unit of time. This case leads to A successfully retransmitting its data after the 3^rd collision.
0	2	In this case, station A starts retransmitting its data immediately while station D waits for 2 unit of time. This case leads to A successfully retransmitting its data after the 3^rd collision.
0	3	In this case, station A starts retransmitting its data immediately while station D waits for 3 unit of time. This case leads to A successfully retransmitting its data after the 3^rd collision.
0	4	In this case, station A starts retransmitting its data immediately while station D waits for 4 unit of time. This case leads to A successfully retransmitting its data after the 3^rd collision.
0	5	In this case, station A starts retransmitting its data immediately while station D waits for 5 unit of time. This case leads to A successfully retransmitting its data after the 3^rd collision.
0	6	In this case, station A starts retransmitting its data immediately while station D waits for 6 unit of time. This case leads to A successfully retransmitting its data after the 3^rd collision.
0	7	In this case, station A starts retransmitting its data immediately while station D waits for 7 unit of time. This case leads to A successfully retransmitting its data after the 3^rd collision.
1	0	In this case, station A waits for 1 unit of time while station D starts retransmitting its data immediately. This case leads to D successfully retransmitting its data after the 3^rd collision.
1	1	In this case, both the stations wait for 1 unit of time and then starts retransmitting their data simultaneously. This case leads to a collision again.
1	2	In this case, station A waits for 1 unit of time while station D waits for 2 unit of time. This case leads to A successfully retransmitting its data after the 3^rd collision.
1	3	In this case, station A waits for 1 unit of time while station D waits for 3 unit of time. This case leads to A successfully retransmitting its data after the 3^rd collision.
1	4	In this case, station A waits for 1 unit of time while station D waits for 4 unit of time. This case leads to A successfully retransmitting its data after the 3^rd collision.
1	5	In this case, station A waits for 1 unit of time while station D waits for 5 unit of time. This case leads to A successfully retransmitting its data after the 3^rd collision.
1	6	In this case, station A waits for 1 unit of time while station D waits for 6 unit of time. This case leads to A successfully retransmitting its data after the 3^rd collision.
1	7	In this case, station A waits for 1 unit of time while station D waits for 7 unit of time. This case leads to A successfully retransmitting its data after the 3^rd collision.

From here,

Probability of station A to successfully retransmit its data after the 3^rd collision = 13 / 16
Probability of station D to successfully retransmit its data after the 3^rd collision = 1 / 16
Probability of occurrence of collision again after the 3^rd collision = 1 / 16

In the similar manner, the procedure continues.

Important Notes-

Note-01:

With each successive collision-

Back off time increases exponentially.
Collision probability decreases exponentially.

Note-02:

Back Off Algorithm is also known as Binary Exponential Back Off Algorithm because-

It works for only two stations.
The back off time increases exponentially.
Collision probability decreases exponentially.

Note-03:

One disadvantage of Back Off Algorithm is that it shows capture effect.
It means if a particular station wins the collision one time, then its probability of winning the successive collisions increases exponentially.

To gain better understanding about Back Off Algorithm,

Watch this Video Lecture

Next Article- Practice Problems On CSMA / CD & Back Off Algorithm

Get more notes and other study material of Computer Networks.

Watch video lectures by visiting our YouTube channel LearnVidFun.

← Older Posts

Newer Posts →