Multiple access protocol

Multiple access protocol- ALOHA, CSMA, CSMA/CA and CSMA/CD

Data Link Layer

The data link layer is used in a computer network to transmit the data between two devices or nodes. It divides the layer into parts such as data link control and the multiple access resolution/protocol. The upper layer has the responsibility to flow control and the error control in the data link layer, and hence it is termed as logical of data link control. Whereas the lower sub-layer is used to handle and reduce the collision or multiple access on a channel. Hence it is termed as media access control or the multiple access resolutions.

Data Link Control

A data link control is a reliable channel for transmitting data over a dedicated link using various techniques such as framing, error control and flow control of data packets in the computer network.

What is a multiple access protocol?

When a sender and receiver have a dedicated link to transmit data packets, the data link control is enough to handle the channel. Suppose there is no dedicated path to communicate or transfer the data between two devices. In that case, multiple stations access the channel and simultaneously transmits the data over the channel. It may create collision and cross talk. Hence, the multiple access protocol is required to reduce the collision and avoid crosstalk between the channels.

For example, suppose that there is a classroom full of students. When a teacher asks a question, all the students (small channels) in the class start answering the question at the same time (transferring the data simultaneously). All the students respond at the same time due to which data is overlap or data lost. Therefore it is the responsibility of a teacher (multiple access protocol) to manage the students and make them one answer.

Following are the types of multiple access protocol that is subdivided into the different process as:

A. Random Access Protocol

In this protocol, all the station has the equal priority to send the data over a channel. In random access protocol, one or more stations cannot depend on another station nor any station control another station. Depending on the channel's state (idle or busy), each station transmits the data frame. However, if more than one station sends the data over a channel, there may be a collision or data conflict. Due to the collision, the data frame packets may be lost or changed. And hence, it does not receive by the receiver end.

Following are the different methods of random-access protocols for broadcasting frames on the channel.

• Aloha
• CSMA
• CSMA/CD
• CSMA/CA

ALOHA Random Access Protocol

It is designed for wireless LAN (Local Area Network) but can also be used in a shared medium to transmit data. Using this method, any station can transmit data across a network simultaneously when a data frameset is available for transmission.

Aloha Rules

1. Any station can transmit data to a channel at any time.
2. It does not require any carrier sensing.
3. Collision and data frames may be lost during the transmission of data through multiple stations.
4. Acknowledgment of the frames exists in Aloha. Hence, there is no collision detection.
5. It requires retransmission of data after some random amount of time.

Pure Aloha

Whenever data is available for sending over a channel at stations, we use Pure Aloha. In pure Aloha, when each station transmits data to a channel without checking whether the channel is idle or not, the chances of collision may occur, and the data frame can be lost. When any station transmits the data frame to a channel, the pure Aloha waits for the receiver's acknowledgment. If it does not acknowledge the receiver end within the specified time, the station waits for a random amount of time, called the backoff time (Tb). And the station may assume the frame has been lost or destroyed. Therefore, it retransmits the frame until all the data are successfully transmitted to the receiver.

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

where G = Number of stations willing to transmit data

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%

As we can see in the figure above, there are four stations for accessing a shared channel and transmitting data frames. Some frames collide because most stations send their frames at the same time. Only two frames, frame 1.1 and frame 2.2, are successfully transmitted to the receiver end. At the same time, other frames are lost or destroyed. Whenever two frames fall on a shared channel simultaneously, collisions can occur, and both will suffer damage. If the new frame's first bit enters the channel before finishing the last bit of the second frame. Both frames are completely finished, and both stations must retransmit the data frame.

Slotted Aloha

The slotted Aloha is designed to overcome the pure Aloha's efficiency because pure Aloha has a very high possibility of frame hitting. In slotted Aloha, the shared channel is divided into a fixed time interval called slots. So that, if a station wants to send a frame to a shared channel, the frame can only be sent at the beginning of the slot, and only one frame is allowed to be sent to each slot. And if the stations are unable to send data to the beginning of the slot, the station will have to wait until the beginning of the slot for the next time. However, the possibility of a collision remains when trying to send a frame at the beginning of two or more station time slot.

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

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%

Example- 

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.

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 Tt	Vulnerable time in which collision may occur = Tt
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.

CSMA (Carrier Sense Multiple Access)

It is a carrier sense multiple access based on media access protocol to sense the traffic on a channel (idle or busy) before transmitting the data. It means that if the channel is idle, the station can send data to the channel. Otherwise, it must wait until the channel becomes idle. Hence, it reduces the chances of a collision on a transmission medium.

CSMA Access Modes

1-Persistent: In the 1-Persistent mode of CSMA that defines each node, first sense the shared channel and if the channel is idle, it immediately sends the data. Else it must wait and keep track of the status of the channel to be idle and broadcast the frame unconditionally as soon as the channel is idle.

Non-Persistent: It is the access mode of CSMA that defines before transmitting the data, each node must sense the channel, and if the channel is inactive, it immediately sends the data. Otherwise, the station must wait for a random time (not continuously), and when the channel is found to be idle, it transmits the frames.

P-Persistent: It is the combination of 1-Persistent and Non-persistent modes. The P-Persistent mode defines that each node senses the channel, and if the channel is inactive, it sends a frame with a P probability. If the data is not transmitted, it waits for a (q = 1-p probability) random time and resumes the frame with the next time slot.

O- Persistent: It is an O-persistent method that defines the superiority of the station before the transmission of the frame on the shared channel. If it is found that the channel is inactive, each station waits for its turn to retransmit the data.

CSMA/ CD

It is a carrier sense multiple access/ collision detection network protocol to transmit data frames. The CSMA/CD protocol works with a medium access control layer. Therefore, it first senses the shared channel before broadcasting the frames, and if the channel is idle, it transmits a frame to check whether the transmission was successful. If the frame is successfully received, the station sends another frame. If any collision is detected in the CSMA/CD, the station sends a jam/ stop signal to the shared channel to terminate data transmission. After that, it waits for a random time before sending a frame to a channel.

CSMA/ CA

It is a carrier sense multiple access/collision avoidance network protocol for carrier transmission of data frames. It is a protocol that works with a medium access control layer. When a data frame is sent to a channel, it receives an acknowledgment to check whether the channel is clear. If the station receives only a single (own) acknowledgments, that means the data frame has been successfully transmitted to the receiver. But if it gets two signals (its own and one more in which the collision of frames), a collision of the frame occurs in the shared channel. Detects the collision of the frame when a sender receives an acknowledgment signal.

Difference between CSMA CA and CSMA CD

CSMA is a mechanism that senses the state of the shared channel to prevent or recover data packets from a collision. It is also used to control the flow of data packets over the network so that the packets are not get lost, and data integrity is maintained. In CSMA, when two or more data packets are sent at the same time on a shared channel, the chances of collision occurred. Due to the collision, the receiver does not get any information regarding the sender's data packets. And the lost information needs to be resented so that the receiver can get it. Therefore we need to sense the channel before transmitting data packets on a network. It is divided into two parts, CSMA CA (Collision Avoidance) and CSMA CD (Collision Detection).

CSMA CD

The Carrier Sense Multiple Access/ Collision Detection protocol is used to detect a collision in the media access control (MAC) layer. Once the collision was detected, the CSMA CD immediately stopped the transmission by sending the signal so that the sender does not waste all the time to send the data packet. Suppose a collision is detected from each station while broadcasting the packets. In that case, the CSMA CD immediately sends a jam signal to stop transmission and waits for a random time context before transmitting another data packet. If the channel is found free, it immediately sends the data and returns it.

Advantage and Disadvantage of CSMA/CD

Advantages of CSMA CD:

1. It is used for collision detection on a shared channel within a very short time.
2. CSMA CD is better than CSMA for collision detection.
3. CSMA CD is used to avoid any form of waste transmission.
4. When necessary, it is used to use or share the same amount of bandwidth at each station.
5. It has lower CSMA CD overhead as compared to the CSMA CA.

Disadvantage of CSMA/CD

1. It is not suitable for long-distance networks because as the distance increases, CSMA CD' efficiency decreases.
2. It can detect collision only up to 2500 meters, and beyond this range, it cannot detect collisions.
3. When multiple devices are added to a CSMA CD, collision detection performance is reduced.

CSMA/CA

CSMA stands for Carrier Sense Multiple Access with Collision Avoidance. It means that it is a network protocol that uses to avoid a collision rather than allowing it to occur, and it does not deal with the recovery of packets after a collision. It is similar to the CSMA CD protocol that operates in the media access control layer. In CSMA CA, whenever a station sends a data frame to a channel, it checks whether it is in use. If the shared channel is busy, the station waits until the channel enters idle mode. Hence, we can say that it reduces the chances of collisions and makes better use of the medium to send data packets more efficiently.

Advantage and Disadvantage of CSMA CA

Advantage of CSMA CA

1. When the size of data packets is large, the chances of collision in CSMA CA is less.
2. It controls the data packets and sends the data when the receiver wants to send them.
3. It is used to prevent collision rather than collision detection on the shared channel.
4. CSMA CA avoids wasted transmission of data over the channel.
5. It is best suited for wireless transmission in a network.
6. It avoids unnecessary data traffic on the network with the help of the RTS/ CTS extension.

The disadvantage of CSMA CA

1. Sometime CSMA/CA takes much waiting time as usual to transmit the data packet.
2. It consumes more bandwidth by each station.
3. Its efficiency is less than a CSMA CD.

Difference between CSMA CA and CSMA CD

S. No	CSMA CD	CSMA CA
1.	It is the type of CSMA to detect the collision on a shared channel.	It is the type of CSMA to avoid collision on a shared channel.
2.	It is the collision detection protocol.	It is the collision avoidance protocol.
3.	It is used in 802.3 Ethernet network cable.	It is used in the 802.11 Ethernet network.
4.	It works in wired networks.	It works in wireless networks.
5.	It is effective after collision detection on a network.	It is effective before collision detection on a network.
6.	Whenever a data packet conflicts in a shared channel, it resends the data frame.	Whereas the CSMA CA waits until the channel is busy and does not recover after a collision.
7.	It minimizes the recovery time.	It minimizes the risk of collision.
8.	The efficiency of CSMA CD is high as compared to CSMA.	The efficiency of CSMA CA is similar to CSMA.
9.	It is more popular than the CSMA CA protocol.	It is less popular than CSMA CD.

Interframe space: In this method, the station waits for the channel to become idle, and if it gets the channel is idle, it does not immediately send the data. Instead of this, it waits for some time, and this time period is called the Interframe space or IFS. However, the IFS time is often used to define the priority of the station.

Contention window: In the Contention window, the total time is divided into different slots. When the station/ sender is ready to transmit the data frame, it chooses a random slot number of slots as wait time. If the channel is still busy, it does not restart the entire process, except that it restarts the timer only to send data packets when the channel is inactive.

Acknowledgment: In the acknowledgment method, the sender station sends the data frame to the shared channel if the acknowledgment is not received ahead of time.

PRACTICE PROBLEMS:-

Problem-01: 

After the k^th consecutive collision, each colliding station waits for a random time chosen from the interval-

1. (0 to 2^k) x RTT
2. (0 to 2^k-1) x RTT
3. (0 to 2^k-1) x Maximum Propagation delay
4. (0 to 2^k-1) x Maximum Propagation delay 

Solution- 

Clearly, Option (B) is correct.

Problem-02: 

In a CSMA / CD network running at 1 Gbps over 1 km cable with no repeaters, the signal speed in the cable is 200000 km/sec. What is minimum frame size?

Solution- 

Given-

• Bandwidth = 1 Gbps
• Distance = 1 km
• Speed = 200000 km/sec

 

Calculating Propagation Delay- 

Propagation delay (T_p)

= Distance / Propagation speed

= 1 km / (200000 km/sec)

= 0.5 x 10^-5 sec

= 5 x 10^-6 sec 

Calculating Minimum Frame Size- 

Minimum frame size

= 2 x Propagation delay x Bandwidth

= 2 x 5 x 10^-6 sec x 10⁹ bits per sec

= 10000 bits

 

Problem-03:

A 2 km long broadcast LAN has 10⁷ bps bandwidth and uses CSMA / CD. The signal travels along the wire at 2 x 10⁸ m/sec. What is the minimum packet size that can be used on this network?

1. 50 B
2. 100 B
3. 200 B
4. None of the above

Solution-

Given-

• Distance = 2 km
• Bandwidth = 10⁷ bps
• Speed = 2 x 10⁸ m/sec

Calculating Propagation Delay- 

Propagation delay (T_p)

= Distance / Propagation speed

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

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

= 10^-5 sec 

Calculating Minimum Frame Size- 

Minimum frame size

= 2 x Propagation delay x Bandwidth

= 2 x 10^-5 sec x 10⁷ bits per sec

= 200 bits or 25 bytes 

Thus, Option (D) is correct.

Problem-04: 

A and B are the only two stations on Ethernet. Each has a steady queue of frames to send. Both A and B attempts to transmit a frame, collide and A wins first back off race. At the end of this successful transmission by A, both A and B attempt to transmit and collide. The probability that A wins the second back off race is ___ .

1. 0.5
2. 0.625
3. 0.75
4. 1.0 

Solution- 

According to question, we have- 

1st Transmission Attempt- 

• Both the stations A and B attempts to transmit a frame.
• A collision occurs.
• Back Off Algorithm runs.
• Station A wins and successfully transmits its 1^st data packet. 

2nd Transmission Attempt- 

• Station A attempts to transmit its 2^nd data packet.
• Station B attempts to retransmit its 1^st data packet.
• A collision occurs.

Now,

• We have been asked the probability of station A to transmit its 2^nd data packet successfully after 2^nd collision.

• After the 2^nd collision occurs, we have- 

At Station A- 

• 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 from the range [0,2¹-1] = [0,1].
• Then, station A waits for back off time and then attempts to retransmit its data packet. 

At Station B- 

• 1^st data packet of station B undergoes collision for the 2^nd time.
• So, collision number for the 1^st data packet of station B = 2.
• Now, station B randomly chooses a number from the range [0,2²-1] = [0,3].
• Then, station B waits for back off time and then attempts to retransmit its data packet.

 Following 8 cases are possible- 

Station A	Station B	Remark
0	0	Collision
0	1	A wins
0	2	A wins
0	3	A wins
1	0	B wins
1	1	Collision
1	2	A wins
1	3	A wins

From here,

• Probability of A winning the 2^nd back off race = 5 / 8 = 0.625.
• Thus, Option (B) is correct.

 

Problem-05: 

Suppose nodes A and B are on same 10 Mbps Ethernet segment and the propagation delay between two nodes is 225 bit times. Suppose A and B send frames at t=0, the frames collide then at what time, they finish transmitting a jam signal. Assume a 48 bit jam signal. 

Solution- 

Propagation delay (T_p)

= 225 bit times

= 225 bit / 10 Mbps

= 22.5 x 10^-6 sec

= 22.5 μsec

At t = 0, 

• Nodes A and B start transmitting their frame.
• Since both the stations start simultaneously, so collision occurs at the mid way.
• Time after which collision occurs = Half of propagation delay.
• So, time after which collision occurs = 22.5 μsec / 2 = 11.25 μsec. 

 At t = 11.25 μsec, 

• After collision occurs at t = 11.25 μsec, collided signals start travelling back.
• Collided signals reach the respective nodes after time = Half of propagation delay
• Collided signals reach the respective nodes after time = 22.5 μsec / 2 = 11.25 μsec.
• Thus, at t = 22.5 μsec, collided signals reach the respective nodes. 

At t = 22.5 μsec, 

• As soon as nodes discover the collision, they immediately release the jam signal.
• Time taken to finish transmitting the jam signal = 48 bit time = 48 bits/ 10 Mbps = 4.8 μsec. 

Thus,

Time at which the jam signal is completely transmitted

= 22.5 μsec + 4.8 μsec

= 27.3 μsec or 273 bit times

 

Problem-06: 

Suppose nodes A and B are attached to opposite ends of the cable with propagation delay of 12.5 ms. Both nodes attempt to transmit at t=0. Frames collide and after first collision, A draws k=0 and B draws k=1 in the exponential back off protocol. Ignore the jam signal. At what time (in seconds), is A’s packet completely delivered at B if bandwidth of the link is 10 Mbps and packet size is 1000 bits. 

Solution-

Given-

• Propagation delay = 12.5 ms
• Bandwidth = 10 Mbps
• Packet size = 1000 bits 

Time At Which Collision Occurs- 

Collision occurs at the mid way after time

= Half of Propagation delay

= 12.5 ms / 2

= 6.25 ms

Thus, collision occurs at time t = 6.25 ms. 

Time At Which Collision is Discovered- 

Collision is discovered in the time it takes the collided signals to reach the nodes

= Half of Propagation delay

= 12.5 ms / 2

= 6.25 ms

Thus, collision is discovered at time t = 6.25 ms + 6.25 ms = 12.5 ms. 

Scene After Collision- 

After the collision is discovered,

• Both the nodes wait for some random back off time.
• A chooses k=0 and then waits for back off time = 0 x 25 ms = 0 ms.
• B chooses k=1 and then waits for back off time = 1 x 25 ms = 25 ms.
• From here, A begins retransmission immediately while B waits for 25 ms. 

Waiting Time For A- 

• After winning the back off race, node A gets the authority to retransmit immediately.
• But node A does not retransmit immediately.
• It waits for the channel to clear from the last bit aborted by it on discovering the collision.
• Time taken by the last bit to get off the channel = Propagation delay = 12.5 ms.
• So, node A waits for time = 12.5 ms and then starts the retransmission.
• Thus, node A starts the retransmission at time t = 12.5 ms + 12.5 ms = 25 ms. 

Time Taken in Delivering Packet To Node B- 

Time taken to deliver the packet to node B

= Transmission delay + Propagation delay

= (1000 bits / 10 Mbps) + 12.5 ms

= 100 μs + 12.5 ms

= 0.1 ms + 12.5 ms

= 12.6 ms 

Thus, At time t = 25 ms + 12.6 ms = 37.6 ms, the packet is delivered to node B. 

Problem-07: 

The network consists of 4 hosts distributed as shown below- 

Assume this network uses CSMA / CD and signal travels with a speed of 3 x 10⁵ km/sec. If sender sends at 1 Mbps, what could be the minimum size of the packet?

1. 600 bits
2. 400 bits
3. 6000 bits
4. 1500 bits 

Solution- 

• CSMA / CD is a Access Control Method.
• It is used to provide the access to stations to a broadcast link.
• In the given network, all the links are point to point.
• So, there is actually no need of implementing CSMA / CD.
• Stations can transmit whenever they want to transmit.

In CSMA / CD, The condition to detect collision is- Packet size >= 2 x (distance / speed) x Bandwidth

 To solve the question,

• We assume that a packet of same length has to be used in the entire network.
• To get the minimum length of the packet, what distance we should choose?
• To get the minimum length of the packet, we should choose the minimum distance.
• But, then collision would be detected only in the links having distance less than or equal to that minimum distance.
• For the links, having distance greater than the minimum distance, collision would not be detected.
• So, we choose the maximum distance so that collision can be detected in all the links of the network. 

So, we use the values-

• Distance = 90 km
• Speed = 3 x 10⁵ km/sec
• Bandwidth = 1 Mbps

 

Substituting these values, we get-

Minimum size of data packet

= 2 x (90 km / 3 x 10⁵ km per sec) x 1 Mbps

= 2 x 30 x 10^-5 sec x 10⁶ bits per sec

= 600 bits 

Thus, Option (A) is correct.

B. Controlled Access Protocol

It is a method of reducing data frame collision on a shared channel. In the controlled access method, each station interacts and decides to send a data frame by a particular station approved by all other stations. It means that a single station cannot send the data frames unless all other stations are not approved. It has three types of controlled access: Reservation, Polling, and Token Passing.

1) Reservation in Computer Network

Whenever we travel on a train or an airplane, the first thing we do is to reserve our seats, similarly, here a station must make a reservation first before transmitting any data frames.

This reservation in the Computer Network timeline consists of two kinds of periods:

1. Reservation interval of a fixed time duration

2. Data transmission period of variable frames

Consider there are 4 stations then the reservation intervals are divided into 4 slots so that each station has a slot. This means if n number of stations are there then n slot will be allotted.

Now let us assume that these 4 stations are 4 friends, now if friend-1 speaks in his slot-1 then no other friend can speak at this time. Similarly, if station-1 transmits a 1-bit data frame in slot-1 then at that time no other station can transmit its data frames and they must wait for their time slot. After all the slots have been transmitted and checked then each station knows which station now wishes for transmission.

The biggest advantage of this method is since all stations agree on which station is next to transmit then there are no possible collisions.

The illustration below shows a scenario with five stations with a five-slot reservation frame. here, in the time interval stations 1,3,4 are the only stations with reservations, and in the second interval, station-1 is the only station with a reservation.

2) Polling in Computer Network

Recall your school or college classroom, what was the first thing the teacher does after entering the class? The answer is roll call or attendance. Let's compare the scenario. The teacher calls roll number 1 and gets a response if he/she is present then switches to the next roll number, say roll number two and roll number 2 is absent, so the teacher gets no response in return or say a negative response. Similarly, in a computer network, there is a primary station or controller (teacher) and all other stations are secondary (students), the primary station sends a message to each station. The message which is sent by the primary station consists of the address of the station which is selected for granting access.

The point to remember is that all the nodes receive the message but the addressed one responds and sends data in return, but if the station has no data to transmit then it sends a message called Poll Reject or NAK (negative acknowledgment).

But this method has some drawbacks like the high overhead of the polling messages and high dependence on the reliability of the primary station.

We calculate the efficiency of this method in terms of time for polling & time required for transmission of data.

Tpoll = time for polling

Tt = time required for transmission of data

So, efficiency = Tt / (Tt + Tpoll)

Whenever the primary station wants to receive the data, it asks the secondary stations present in its channel, this method is polling. In the first diagram, we see that the primary station asks station A if it has any data ready for transmission, since A does not have any data queued for transmission it sends NAK (negative acknowledgment), and then it asks station B since B has data ready for transmission, so it transmits the data and in return receives an acknowledgment from the primary station.

In the next case, if the primary station wants to send data to the secondary stations, it sends a select message, and if the secondary station accepts the request from the primary station, then it sends back an acknowledgment, and then the primary station transmits the data and in return receives an acknowledgment.

3) Token Passing in Computer Network

Now, say 4 people are sitting on a round table and only that person can speak who has the token. In computer networks, a token is a special bit pattern that allows the token-possessing system to send data or we can say that a token represents permission to transmit data. The token circulation around the table (or a network ring) is in a predefined order. A station can only pass the token to its adjacent station and not to any other station in the network. If a station has some data queued for transmission it can not transmit the data until it receives the token and makes sure it has transmitted all the data before passing on the received token.

This method has some drawbacks like duplication of tokens or sometimes the token being damaged or lost during circulation, or some times if we introduce a new station or remove an existing station from the network, this leads to a huge disturbance, which should be taken care of so that the efficiency of the method is not affected.

The performance of a token ring is governed by 2 parameters, which are delay and throughput.

Delay is a measure of the time; it is the time difference between a packet ready for transmission and when it is transmitted. Hence, the average time required to send a token to the next station is a/N.

Throughput is a measure of the successful traffic in the communication channel.

Throughput, S = 1/ (1 + a/N) for a<1

S = 1/[a(1+1/N)] for a>1, here N = number of stations & a = Tp/Tt

Tp = propagation delay &Tt = transmission delay

In the diagram below when station-1 possesses the token it starts transmitting all the data frames which are in its queue. now after transmission, station-1 passes the token to station-2 and so on. Station-1 can now transmit data again, only when all the stations in the network have transmitted their data and passed the token.

Note: A token can only work in that channel, for which it is generated, and not for any other.

Problem-01: 

Token ring station operates in which of the following modes?

1. Transit mode
2. Listen mode
3. Bypass mode and Receive mode
4. All of the above

 

Solution- 

• In transmit mode, a station transmits the data.
• In listen mode, a station listens from other station(s).
• In bypass mode, a station simply bypasses the data packet if it is not meant for it.
• In receive mode, a station receives the data packet if it is destined to it.

Therefore, a token ring station operates in all these modes.

Thus, Option (D) is correct.

 

Problem-02: 

Efficiency of the token ring is high if-

1. Reinsert the token after receiving the last bit of the frame
2. Reinsert the token after receiving the last bit of the header
3. Reinsert the token after last bit of the data packet is transferred
4. Reinsert the token after last bit of the header is transferred 

Solution- 

• There are two strategies used in token ring- Early Token Reinsertion (ETR) and Delayed Token Reinsertion (DTR).
• Efficiency of token ring is high in Early Token Reinsertion (ETR).

Thus, Option (C) is correct.

 

Problem-03: 

The sending station in IEEE 802.5 sets the address recognized (A) bit and frame copied (C) bit in MAC header as

1. 1,0
2. 0,0
3. 0,1
4. 1,1

Solution- 

• IEEE 802.5 is token ring.
• Sending station sets both the available bit and copied bit as 0.
• These bits are modified by the receiving station.
• If the receiving station is available, it sets the Available bit to 1.
• If the receiving station successfully copies the data, it sets the Copied bit to 1.

Thus, Option (B) is correct.

 

Problem-04: 

Which of the following fields in 802.5 MAC header is not included in CRC or FCS?

1. FC
2. Data field
3. FS
4. SA 

Solution-

• IEEE 802.5 is token ring.
• Frame Status (FS) field consists of the Available bit and Copied bit.
• These two bits are modified by the receiving station.
• So, CRC is not computed on Frame Status field otherwise receiving station will have to bear the overhead of recomputing the CRC.

Thus, Option (C) is correct.

 

Problem-05: 

What type of acknowledgement system is used in 802.5?

1. Cumulative ACK
2. Independent ACK
3. Piggybacking ACK
4. None 

Solution- 

• IEEE 802.5 is token ring.
• The two bits- Available bit and Copied bit acts as the acknowledgement for the sending station.
• The value of these bits suggests to the sending station that whether the receiving station has successfully copied the data or not.
• Because the two bits are contained in the data frame, so we can say that piggybacked acknowledgements are used in token ring.

Thus, Option (C) is correct.

Problem-06: 

In token ring, ______ field is present only in the data / command frame but not in the token frame.

1. SD
2. AC
3. ED
4. FS 

Solution- 

• Frame status (FS) field is present only in the data / command frame.
• A token frame consists of only 3 fields- SD, AC and ED.

Thus, Option (D) is correct. 

Problem-07: 

Consider a token ring with latency 500 μsec and packet size of 1500 bytes. What is the effective throughput rate for both single active host and for many active hosts that can be achieved if the ring has 3 Mbps bandwidth? Assume the strategy used is delayed token reinsertion.

1. 2.4 Mbps and 3 Mbps
2. 2.4 Mbps and 2 Mbps
3. 2 Mbps and 3 Mbps
4. 2.4 Mbps and 2.67 Mbps 

Solution- 

Given-

• Ring latency = 500 μsec
• Packet Size = 1500 bytes
• Bandwidth = 3 Mbps
• Strategy used is Delayed Token Reinsertion (DTR) 

Efficiency of Delayed Token Reinsertion (DTR) strategy is- 

 

Calculating Transmission delay-

We know,

Transmission delay (T_t)

= Packet size / Bandwidth

= 1500 bytes / 3 Mbps

= (1500 x 8 bits) / (3 x 10⁶ bits per sec)

= 4000 μsec 

Calculating value of ‘a’- 

We know,

a = T_p / T_t

a = Latency / T_t

a = 500 μsec / 4000 μsec

a = 0.125 

Calculating Throughput for single active host-

For single active host, N = 1.

Substituting N = 1 in efficiency formula, we get-

Efficiency (η)

= 1 / (1 + 2a)

= 1 / (1 + 2 x 0.125)

= 1 / 1.25

= 0.8 

Now,

Throughput

= Efficiency (η) x Bandwidth

= 0.8 x 3 Mbps

= 2.4 Mbps

Calculating Throughput for many active host- 

For many active host, N = ∞.

Substituting N = ∞ in efficiency formula, we get-

Efficiency (η)

= 1 / (1 + a)

= 1 / (1 + 0.125)

= 1 / 1.125

= 0.89 

Now,

Throughput

= Efficiency (η) x Bandwidth

= 0.89 x 3 Mbps

= 2.67 Mbps

Thus, Option (D) is correct.

Problem-08: 

In 802.5, the condition to find out the minimum size of the ring is-

1. Latency of the ring = Transmission delay of the data frame
2. Latency of the ring = Transmission delay of the token frame
3. Latency of the ring = RTT
4. Latency > RTT 

Solution- 

• IEEE 802.5 is token ring.
• The condition to find out the minimum size of the ring is-

Latency of the ring >= Transmission delay of the token frame

• In worst case, all the stations goes down and only the monitor station is alive.
• Monitor station sends the token and the token comes back to it.
• To avoid the collision between the first and the last bit of the token, propagation delay of the token must be at least equal to its transmission delay.

Thus, Option (B) is correct.

 

Problem-09:

The stacking station is a station in 802.5 and it can be described as-

1. when it drains the frame and creates a token, it then stores both the old and new priority of the token
2. A station which stack the token till it gets the last bit of the token
3. It is nothing but monitor station
4. None of the above 

Solution-

• IEEE 802.5 is token ring.
• A station which increases the priority of the token should next decrease the priority of the token.
• Otherwise once the priority of the token reaches the highest value, it would ever remain there and thus only the station with the highest packet would drain (take) the token and use it.
• Thus, a stacking station must remember both the old and new priorities so that when it later receives the token with new priority, it changes it to old priority.
• This is implemented by using 2 stacks. Each station maintains 2 stacks where one station keeps track of the old priority and other stack keeps track of the new priority.

Thus, Option (A) is correct.

 

Problem-10: 

In early token release, the station releases a token as soon as it completes the frame transmission whether or not the frame header has returned to the station, then what will be the priority of the token released?

1. The priority in the frame that completes frame transmission
2. Without changing the priority, token will be released
3. Default priority is used
4. The priority in the reservation field of the most recently received frame 

Solution- 

Option (D) is correct. 

Problem-11: 

Find the efficiency of the ring where data rate of the link is 4 Mbps, number of stations are 20, separated by 100 meters and bit delay in each station is 2.5 bits. Assume early token reinsertion with packet size of 1000 bits and transmission speed is 2 x 10⁸ m/sec.

Solution- 

Given-

• Data rate = Bandwidth = 4 Mbps
• Number of stations = 20
• Distance between two stations = 100 meters
• Bit delay = 25 bits
• Packet size = 1000 bits
• Strategy used is Early Token Reinsertion (ETR) 

Calculating length of ring wire- 

Total length of ring wire

= Number of stations x Distance between 2 stations

= 20 x 100 meters

= 2000 meters

= 2 km 

Calculating Transmission delay- 

Transmission delay (T_t)

= Packet size / Bandwidth

= 1000 bits / 4 Mbps

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

= 250 μsec 

Calculating Propagation delay- 

Propagation delay (T_t)

= Distance / Speed

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

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

= 10^-5 sec

= 10 μsec 

Calculating Bit delay in seconds- 

Bit delay

= 25 bits

= 2.5 bits / 4 Mbps

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

= 0.625 μsec 

Calculating Ring latency- 

Ring latency

= Propagation delay + N x Bit delay

= 10 μsec + 20 x 0.625 μsec

= 10 μsec + 12.5 μsec

= 22.5 μsec

Calculating value of ‘a’- 

a= Ring latency / T_t

= 22.5 μsec / 250 μsec

= 0.09 

Calculating Efficiency- 

Efficiency(η)

= 1 / (1 + a/N)

= 1 / (1 + 0.09 / 20)

= 1 / 1.0045

= 0.9955

= 99.55%

 

Problem-12: 

A token ring LAN network interconnects M stations using Star Topology in the following way. All the input and output lines of the token ring station interface are connected to a cabinet where the actual ring is placed. Suppose that distance from each station to a cabinet is 100 m and ring latency per station is 8 bits, packets are 1250 B and bandwidth is 25 Mbps.

1. Find the ring latency normalized to packet transmission time.
2. Find the minimum number of packets transmitted by stations, if stations are allowed to transmit an unlimited number of packet / token. (v = 2 x 10⁸ m/sec) 

Solution- 

Based on the given information, the token ring LAN network looks like- 

(The sketch is for 4 stations)

Part-01: 

Calculating Transmission delay- 

Transmission delay

= Packet size / Bandwidth

= 1250 B / 25 Mbps

= (1250 x 8 bits) / (25 x 10⁶ bits per sec)

= 400 μsec 

Calculating Propagation delay- 

Propagation delay

= Distance / Speed

= (200 x M meters) / (2 x 10⁸ m/sec)

= (200 x M) / (2 x 10⁸) sec

= 100 x M x 10^-8 sec

= M μsec 

Calculating Bit delay in seconds- 

Bit delay

= Ring latency per station

= 8 bits

= 8 bits / 25 Mbps

= 0.32 μsec

Calculating Ring latency- 

Ring latency

= Propagation delay + N x Bit delay

= M μsec + M x 0.32 μsec

= 1.32 x M μsec 

Calculating Ring latency normalized to packet transmission delay- 

Ring latency normalized to packet transmission time

= Ring latency / Packet transmission time

= 1.32 x M μsec / 400 μsec

= 0.0033 x M 

Part-02: 

• The number of packets a station can transmit after holding a token depends on Token Holding Time and the strategy used.
• Since no information is given in the question about the Time Holding Time, so we assume that there is no restriction on holding the token.
• Thus, a station can send infinite number of packets after getting a token.

 

Problem-13: 

A very heavily loaded 1 km long, 10 Mbps token ring has a propagation speed of 200 m/μsec. 50 stations are uniformly spaced around the ring. Data frames are 256 bits including 32 bits of overhead. Acknowledgements are piggybacked onto the data frames and are thus included as spare bits within the data frames and are effectively free. The token is 8 bits long. Is the effective data rate of this ring higher or lower than the effective data rate of a 10 Mbps CSMA / CD network? Assume ‘Early Token Release’ policy. 

Solution- 

Remember Token Ring always beats the Ethernet in terms of effective bandwidth.

Analysis- 

Efficiency of CSMA / CD- 

Efficiency of token ring in early token retransmission is given by-

Efficiency(η) = 1 / (1 + 6.44 x a)

This expression is valid when number of stations are very large i.e. N → ∞

 

Efficiency of Token Ring- 

Case-01: 

Efficiency of token ring in early token retransmission is given by-

Efficiency(η) = 1 / (1 + a/N)

When N → ∞, Efficiency(η) = 100% 

Case-02: 

Efficiency of token ring in delayed token retransmission is given by-

Efficiency(η) = 1 / [1 + a(1 + 1/N)]

When N → ∞, Efficiency(η) = 1 / (1+a) 

The above analysis clearly shows-

Efficiency of Token Ring in ETR > Efficiency of Token Ring in DTR > Efficiency of Token Ring in CSMA / CD.

 

Problem-14: 

A fibre optic token ring used as a MAN is 200 km long and runs at 100 Mbps. After sending a frame, a station drains the frame from the ring before regenerating the token. The signal propagation speed in the fibre is 200,000 km/sec and maximum frame size is 1 KB. What is the maximum efficiency at N=1? 

Solution- 

Given-

• Distance = 200 km
• Bandwidth = 100 Mbps
• Propagation speed = 200,000 km/sec = 2 x 10⁸ m/sec
• Frame size = 1 KB
• Number of stations = 1
• Strategy used is Delayed Token Reinsertion 

Calculating Transmission delay- 

Transmission delay

= Frame size / Bandwidth

= 1 KB / 100 Mbps

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

= 81.92 μsec 

Calculating Propagation delay- 

Propagation delay

= Distance / Speed

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

= (200 x 10³ m) / (2 x 10⁸ m/sec)

= 10^-3 sec

= 1 msec 

Calculating value of ‘a’- 

a

= T_p / T_t

= 1 msec / 81.92 μsec

= 0.0122 x 10³

= 12.2 

Calculating Efficiency- 

Efficiency(η)

= 1 / [1 + a x (1+ 1/N)]

= 1 / [1 + 12.2 x (1+1)]

= 1 / 25.4

= 0.0394

= 3.94% 

• The reason behind this much less efficiency is that the distance is too large here.
• Ethernet and Token Ring are meant for LANs.
• If used for MANs or WANs, the efficiency will fall drastically.

 

Problem-15: 

At a propagation speed of 200 m/μsec, what is the effective length added to a ring by a bit delay at each repeater or station for-

1. 1 Mbps line
2. 40 Mbps line 

Solution- 

Part-01: 

Effective length added to a ring by a bit delay

= 1 bit / 1 Mbps

= 1 μsec

= 1 μsec x 200 m/μsec

= 200 m 

Part-02: 

Effective length added to a ring by a bit delay

= 1 bit / 40 Mbps

= 0.025 μsec

= 0.025 μsec x 200 m/μsec

= 5 m

 

Problem-16: 

Consider a 10 Mbps token ring LAN with a ring latency of 400 μs. A host that needs to transmit seizes the toke. Then it sends a frame of 1000 bytes, removes the frame after it has circulated all around the ring and finally releases the token. This process is repeated for every frame. Assuming that only a single host wishes to transmit, the effective data rate is _____ .

1. 1 Mbps
2. 2 Mbps
3. 5 Mbps
4. 6 Mbps 

Solution- 

Given-

• Bandwidth = 10 Mbps
• Ring latency = 400 μsec
• Frame size = 1000 bytes
• Number of stations = 1
• Strategy used is Delayed Toke Reinsertion 

Calculating Transmission delay- 

Transmission delay

= Frame size / Bandwidth

= 1000 bytes / 10 Mbps

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

= 800 μsec 

Calculating value of ‘a’- 

a

= Ring latency / T_t

= 400 μsec / 800 μsec

= 0.5 

Calculating Efficiency- 

Efficiency(η)

= 1 / [1 + a x (1+ 1/N)]

= 1 / [1 + 0.5 x (1+1)]

= 1 / 2

= 0.50

= 50% 

Calculating Effective data rate- 

Effective data rate

= Throughput

= Efficiency(η) x Bandwidth

= 0.5 x 10 Mbps

= 5 Mbps

Thus, Option (C) is correct.

C. Channelization Protocols

It is a channelization protocol that allows the total usable bandwidth in a shared channel to be shared across multiple stations based on their time, distance and codes. It can access all the stations at the same time to send the data frames to the channel.

Following are the various methods to access the channel based on their time, distance and codes:

1. FDMA (Frequency Division Multiple Access)
2. TDMA (Time Division Multiple Access)
3. CDMA (Code Division Multiple Access)

FDMA

It is a frequency division multiple access (FDMA) method used to divide the available bandwidth into equal bands so that multiple users can send data through a different frequency to the subchannel. Each station is reserved with a particular band to prevent the crosstalk between the channels and interferences of stations.

TDMA

Time Division Multiple Access (TDMA) is a channel access method. It allows the same frequency bandwidth to be shared across multiple stations. And to avoid collisions in the shared channel, it divides the channel into different frequency slots that allocate stations to transmit the data frames. The same frequency bandwidth into the shared channel by dividing the signal into various time slots to transmit it. However, TDMA has an overhead of synchronization that specifies each station's time slot by adding synchronization bits to each slot.

CDMA

CDMA stands for Code Division Multiple Access. It is a channel access method used by several radio communication technologies. It is a digital cellular technology and an example of multiple access. It is generally used for mobile communication.

Multiple access means that several transmitters can send information simultaneously over a single communication channel. In this system, different CDMA codes are assigned to different users, and the user can access the whole bandwidth for the entire duration. It optimizes the use of available bandwidth as it transmits over the entire frequency range and does not limit the user's frequency range.

Thus, CDMA allows several users to share a band of frequencies without undue interference between the users. It is used as an access method in many mobile phone standards.

CDMA technology was developed during World War II. It was developed by English allies to protect their wireless transmissions from jamming. When the war ended, Qualcomm patented this technology and made it commercially available. The first CDMA system was launched in September 1995 in Hong Kong by Hutchison Telephone Co.

Usage

• It is used in the Global Positioning System (GPS).
• It is used by several mobile phone companies (e.g., Qualcomm standard IS-2000, also known as CDMA2000)
• W-CDMA is used in UTMS 3G mobile phone standards.
• CDMA has been used in OmniTRACS satellite system for transportation.

Categories of CDMA

• Synchronous CDMA (orthogonal codes)
• Asynchronous CDMA (pseudorandom codes)

Difference between CDMA and GSM

The major difference between CDMA and GSM are given below.

Criteria	CDMA	GSM
Technology	CDMA is based on spread-spectrum technology, which makes the optimum use of available bandwidth.	GSM operates on the wedge spectrum. It uses both time division multiple access (TDMA) and frequency division multiple access (FDMA). TDMA provides multi-user access by cutting up the channel into different time slices, and FDMA provides multi-user access by separating the used frequency.
Security	CDMA is more secure than GSM.	GSM is less secure than CDMA.
Global reach	CDMA is used in the USA and some parts of Canada and Japan. CDMA is used only by 24% of users worldwide.	GSM is used in over 80% of the world network in over 210 countries. GSM is used by 76% of users worldwide.
Data Transfer Rate	CDMA has faster data transfer as compared to GSM.	GSM has slower data transfer as compared to CDMA.
Radiation exposure	CDMA phones emit less radiation than GSM phones.	GSM phones emit continuous wave pulses and emit almost 28 times more radiation than CDMA phones.

How is CDMA operative?

The cellular architecture of wireless CDMA networks is formed by cell clusters. In a cell cluster, each cell has a transceiver with the necessary transmitting power, and mobile units are scattered around the cell's coverage area. Every mobile unit has a transceiver, which is made up of a sensitive receiver and a low-power transmitter that operates in a wireless cellular environment. Access interference, fading, and multipath propagation are some features of the cellular environment.

The quality of service (QoS) for CDMA systems is significantly influenced by the near-far (N-F) impact. A broadcast from a user who is near the base station can interfere with and overpower a weaker transmission signal from a user who is further away.

In order to do this, CDMA network providers employ receivers that are immune to the N-F effect as well as stringent power management techniques.

The CDMA channel has a nominal width of 1.23 MHz. Soft handoff is a technique used by CDMA networks to reduce signal loss as a handset moves from one cell to another. Spread spectrum and digital together allow for substantially more signals per unit of bandwidth than analogue modes do. Due to CDMA's compatibility with other cellular technologies, nationwide roaming is possible. In its single-channel and eight-channel configurations, the original CDMA technology, also known as CDMA One, only enables transmission speeds of up to 14.4 and 115 kilobits per second, respectively. W-CDMA and CDMA2000 send data at rates that are many times quicker.

The CDMA2000 family of standards includes Single-carrier Radio Transmission Technology (1xRTT), Evolution-Data Optimized Release 0, EVDO Revision A, and EVDO Revision B. The physical layer multiplexing protocol CDMA is frequently confused with the CDMA2000 family of protocols, which Verizon and Sprint both support.

New 5g technology

Older protocols will be replaced by 5G cellular technology, and CDMA will lose even more significance as 5G wireless systems evolve. Data transfer speeds on cellular networks are expected to significantly increase with 5G, making them competitive

with fiber-optic networks. Beyond what is achievable with 4G, the technology provides better broadband capacity, reliability, and bandwidth. 5G is mainly powered by millimeter wave (MM wave) bands at 26, 28, 38, and 60 GHz. These frequency ranges allow for data transport rates up to 20 gigabits per second (Gbps). Massive multiple input, multiple outputs (MIMO) 64-256 antennas enable 5G to provide speeds that are at least ten times faster than those offered by 4G networks.

Low-band and mid-band 5G cellular technologies operate between 600 MHz and 6 GHz, with the majority operating between 3.5 and 4.2 GHz. The 3,100 to 3,550 MHz and 3,700 to 4,200 MHz 5G wireless frequency bands are already in use in the United States. While Asia uses the 3,300-3,600 MHz, 4,400-4,500 MHz, and 4,800-4,990 MHz bands, Europe employs the 3,400-3,800 MHz range.