Summary

Functionality of Data Link Layer: Packetizing/Addressing/Flow Control/Error control/Media Access Control (MAC)

CRC is an error-checking technique for digital networks. It uses polynomial division to generate a checksum, which is appended to the data. The receiver performs the same calculation and compares its result with the received checksum. If they match, the data is assumed to be intact; otherwise, an error is detected.

Multiple-access resolution: Media Access Control (MAC)/Collision Detection and Avoidance/Scheduling/Priority Handling/Token Passing

Multiple Access Protocol, nodes or stations are connected and use a common link, called a multipoint or broadcast link, we need a multiple-access protocol to coordinate access to the link.

ALOHA is a multiple-access protocol that allows data to be transmitted via a shared network channel. Any station can transmit data to a channel at any time.

In Pure ALOHA, each station sends a frame whenever it has a frame to send. However, there is only one channel to share and there is the possibility of collision between frames from different stations.

Pure ALOHA Steps: Start/K=0/Send Frame/Wait timeout 2Tp / ACK / Success(Y) / K++(N) /K>Kmax /Abort(Y)/Random R(N)/ Wait time Tb = RTp

In Slotted Aloha, the shared channel is split into fixed time intervals called slots. As a result, if a station wants to send a frame to a shared channel, it can only do so at the start of the slot, and only one frame can be sent to each slot.

Pure Vs Slotted Aloha: start transmission: at any time/ at the time slot | Vulnerable Time: Vt = 2Tr / Tr | Max efficiency %: 18.4 / 36.8 | collision chance: high/less

CSMA stands for Carrier Sense Multiple Access is one of the network protocols which works on the principle of "carrier sense". This method was developed to decrease the chances of collisions when two or more stations start sending their signals over the data link layer. Here each station first checks the state of the medium before sending.

1-persistent: It senses the shared channel first and delivers the data right away if the channel is idle. If not, it must wait and continuously track for the channel to become idle and then broadcast the frame without condition as soon as it does.

non-persistent: It first assesses the channel before transmitting data; if the channel is idle, the node transmits data right away. If not, the station must wait for a random amount of time, and when it discovers the channel is empty, it sends the frames.

p-persistent: It consists of 1 & non-persistent. Each node observes the channel in the 1-Persistent mode, and if the channel is idle, it sends a frame with a P probability. If the data is not transferred, the frame restarts with the following time slot after waiting for a (q = 1-p probability) random period.

Advantages of CSMA: Increased efficiency/ Simplicity/ Flexibility/Low cost

CSMA/CD protocol works with a medium access control layer. 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.

Flow Diagram CSMA/CD: Start/K=0/Apply Persistence Method/Transmission Done/Transmit & received(N)/Collision detect/Success(N)/Send a Jamming Signal(Y)/K++(N) /K>Kmax /Abort(Y)/Random R(N)/ Wait time Tb = RTp

CSMA/CA 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 ACK, that means the data frame has been successfully transmitted to the receiver. But if it gets two signals (its own and one 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.

Collisions are avoided by: The interframe space, the contention window, and acknowledgments.

Flow Diagram CSMA/CA: Start/K=0/Idel Channel/Wait IFS Time/Still Idle/Random R(N)/Send Frame/Wait time-out/ACK/Success(Y)/K++(N) /K>Kmax /Abort(Y)

Functionality of Data Link Layer

1. Packetizing: The Data Link Layer encapsulates network layer packets into frames, which are units of data that can be transmitted over the physical medium.
2. Addressing: It assigns physical addresses (MAC addresses) to devices on the same network segment to enable the delivery of frames to the correct destination.
3. Flow Control: It manages the flow of data between devices to ensure that a sender does not overwhelm a receiver with data. This is often done through techniques like buffering or windowing.
4. Error Control: The Data Link Layer is responsible for detecting and, if possible, correcting errors that occur during data transmission. This can involve techniques such as error detection codes or retransmission of corrupted frames.
5. Media Access Control (MAC): This sublayer of the Data Link Layer is responsible for controlling access to the physical transmission medium. It determines which device can transmit data at a given time and manages contention between multiple devices attempting to transmit simultaneously.

Error Control

CRC (Cyclic Redundancy Check):

CRC is a powerful error-checking technique widely used in digital networks and storage devices. It uses polynomial division to generate a checksum, which is appended to the data. The receiver performs the same calculation and compares its result with the received checksum. If they match, the data is assumed to be intact; otherwise, an error is detected.

Example:

Let's say we have a 4-bit message, 1011, and we want to append a 3-bit CRC.

When the receiver receives the message, it performs the same division. If the remainder is zero, it assumes no errors. Otherwise, an error is detected.

https://www.geeksforgeeks.org/modulo-2-binary-division/

Checksum

Checksum is a simpler technique compared to CRC. It involves adding up all the bytes in a message and appending the total (often complemented) to the message. The receiver adds up all the bytes (including the checksum) and checks whether the sum matches the expected value. If it matches, the data is assumed to be intact; otherwise, an error is detected.

Multiple Access

Data Link layer divided into 2 sublayers,

1. Data Link Control: It's responsible for controlling the flow of data, framing, error detection, and error correction in the transmission of data over a physical medium. Its primary functions include:
   • Framing: DLC encapsulates network layer packets into frames, which include a header and a trailer. These frames help in delineating the boundaries of data packets.
   • Flow Control: It manages the flow of data between devices to prevent data loss due to speed mismatches between sender and receiver.
   • Error Detection and Correction: DLC often employs techniques like CRC (Cyclic Redundancy Check) to detect errors in transmitted data. It may also implement error correction mechanisms to ensure data integrity.
   • Addressing: DLC may add addressing information to frames, enabling devices to determine the source and destination of data transmissions.
   • Access Control: It may include protocols for medium access control, especially in shared medium environments like Ethernet networks.
2. Multiple-access resolution: Multiple-Access Resolution is is responsible for managing access to a shared communication medium by multiple devices. Its main purpose is to resolve conflicts that arise when multiple devices attempt to transmit data simultaneously on the same medium. Key functions include:
   • Medium Access Control (MAC): MAC protocols determine how devices access and share a common communication medium, ensuring that only one device can transmit at any given time.
   • Collision Detection and Avoidance: In environments where multiple devices contend for access, collision detection mechanisms are employed to detect when two or more devices transmit simultaneously. Techniques such as CSMA/CD (Carrier Sense Multiple Access with Collision Detection) are used to handle collisions.
   • Scheduling: Some multiple-access resolution protocols involve scheduling mechanisms to allocate time slots or frequency bands to different devices, ensuring fair and efficient utilization of the communication medium.
   • Priority Handling: In networks with devices of varying priority levels, multiple-access resolution sublayers may implement mechanisms to prioritize access for high-priority devices.
   • Token Passing: In token-based access control schemes, a special token is passed from one device to another, granting the holder the right to transmit data. This method ensures orderly access to the medium.

Multiple-Access Protocol

When nodes or stations are connected and use a common link, called a multipoint or broadcast link, We need a multiple-access protocol to coordinate access to the link.

Random Access Protocols

In random access or contention methods, no station is superior to another station, and none is assigned the control over another. No station permits, or does not permit, another station to send. At each instance, a station that has data to send uses a procedure defined by the protocol to make a decision on whether or not to send.

• vIn a Random-access method, each station has the right to the medium without being controlled by any other station.
• vIf more than one station tries to send, there is an access conflict "COLLISION" and the frames will be either destroyed or modified.

To avoid access conflict, each station follows a procedure.

• vWhen can the station access the medium?
• vWhat can the station do if the medium is busy?
• vHow can the station determine the success or failure of the transmission?
• vWhat can the station do if there is an access conflict?

Types:

1. ALOHA
2. CSMA(Carrier Sense Multiple Access)
3. CSMA/CD(Carrier Sense Multiple Access with Collision Detection)
4. CSMA/CA(Carrier Sense Multiple Access with Collision Avoidance)

Controlled Access Protocols

Reservation, Polling, Token Passing

Channelization Protocols

FDMA, TDMA, CDMA

ALOHA

ALOHA is a multiple-access protocol that allows data to be transmitted via a shared network channel.

Base station is central controller and acts as a hop.

Rules of ALOHA in Computer Network

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

The two protocols of Aloha in computer networks are:

1. 1. Pure Aloha
2. 2. Slotted Aloha

Pure ALOHA

Each station sends a frame whenever it has a frames to send. However, there is only one channel to share and there is the possibility of collision between frames from different stations.

In pure Aloha, if each station transmits data to a channel without determining if the channel is idle or not, a collision may occur, and the data frame may be lost. When any station sends a data frame to a channel, the pure Aloha waits for the receiver's acknowledgment. If the receiver's acknowledgment is not received within the given time, the station waits for a random amount of time, known as the backoff time (Tb). Furthermore, the station may believe the frame has been lost or destroyed. As a result, it retransmits the frame until all of the data is properly delivered to the receiver.

Procedure for pure ALOHA protocol

1. The total vulnerable time of pure Aloha is 2 * Tfr.
2. Maximum throughput occurs when G = 1/ 2 that is 18.4%.
3. Successful transmission of data frame is S = G * e ^ - 2 G.

Acknowledgement

• After sending the frame, the station waits for an acknowledgment
• If it does not receive an acknowledgement during the 2 times of the maximum propagation delay between the two widely separated stations (2 x T_p)
• It assumes that the frame is lost; it tries sending again after a random amount of time (T_B =R x T_P, or R x T_fr).
  • T_p (Maximum propagation time)= distance / propagation speed
  • T_B (Back off time) : common formula is binary exponential back-off
    • R is random number chosen between 0 to 2^k - 1
    • K is the number of attempted unsuccessful transmissions
• T_fr (the average time required to send out a frame)

Slotted ALOHA

We divide the time into slots of T_fr s and force the station to send only at the beginning of the time slot.

Pure Aloha has a very high chance of hitting a frame, hence the slotted Aloha is intended to outperform its efficiency. In slotted Aloha, the shared channel is split into fixed time intervals called slots. As a result, if a station wants to send a frame to a shared channel, it can only do so at the start of the slot, and only one frame can be sent to each slot. Additionally, the station must wait until the beginning of the slot for the subsequent transmission if it is unable to transfer data at the beginning of the slot. However, sending a frame at the start of two or more station time slots still carries the risk of a collision.

Differences between Pure and Slotted ALOHA

Carrier Sense Multiple Access (CSMA)

CSMA stands for Carrier Sense Multiple Access (CSMA). CSMA is one of the network protocols which works on the principle of "carrier sense". This method was developed to decrease the chances of collisions when two or more stations start sending their signals over the data link layer. Carrier Sense multiple access requires that each station first check the state of the medium before sending.

• To minimize the chance of collision and, therefore, increase the performance, the CSMA method was developed.
• CSMA is based on the principle "sense before transmit" or "listen before talk".
• CSMA can reduce the possibility of collision, but it cannot eliminate it completely.
• The possibility of collision still exists because of propagation delay; a station may sense the medium and find it idle, only because the first bit sent by another station has not yet been received.

Persistence methods

Persistence strategy defines the procedures for a station that senses a busy medium. Three strategies have been developed;

1-persistent method:

It senses the shared channel first and delivers the data right away if the channel is idle. If not, it must wait and continuously track for the channel to become idle and then broadcast the frame without condition as soon as it does. It is an aggressive transmission algorithm.

after the station finds the line idle, it sends its frame immediately (with probability 1)

non-persistent method:

It first assesses the channel before transmitting data; if the channel is idle, the node transmits data right away. If not, the station must wait for an arbitrary amount of time (not continuously), and when it discovers the channel is empty, it sends the frames.

• A station that has a frame to send senses the line.
• If the line is idle, it sends immediately.
• If the line is not idle, it waits a random amount of time and then senses the line again.

p-persistent method:

It consists of the 1-Persistent and Non-Persistent modes combined. Each node observes the channel in the 1Persistent mode, and if the channel is idle, it sends a frame with a P probability. If the data is not transferred, the frame restarts with the following time slot after waiting for a (q = 1-p probability) random period.

After the station finds the line idle,

• With probability p, the station sends its frames
• With probability q=1-p, the station waits for the beginning of the next time slot and checks the line again.

Advantages of CSMA

1. Increased efficiency:CSMA ensures that only one device communicates on the network at a time, reducing collisions and improving network efficiency.
2. Simplicity:CSMA is a simple protocol that is easy to implement and does not require complex hardware or software.
3. Flexibility:CSMA is a flexible protocol that can be used in a wide range of network environments, including wired and wireless networks.
4. Low cost:CSMA does not require expensive hardware or software, making it a cost-effective solution for network communication.

Disadvantages of CSMA

1. Limited scalability:CSMA is not a scalable protocol and can become inefficient as the number of devices on the network increases.
2. Delay:In busy networks, the requirement to sense the medium and wait for an available channel can result in delays and increased latency.
3. Limited reliability:CSMA can be affected by interference, noise, and other factors, resulting in unreliable communication.
4. Vulnerability to attacks:CSMA can be vulnerable to certain types of attacks, such as jamming and denial-of-service attacks, which can disrupt network communication.

Comparison of various protocols:

Carrier Sense Multiple Access with Collision Detection (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/CD adds a procedure to handle the collision.

A station monitors the medium after it sends a frame to see if the transmission was successful.

• If so, the station is finished.
• If there is a collision, the frame is sent again.

Collision of the first bit in CSMA/CD is like below

Collision and abortion in CSMA/CD is like below,

In this method, a station monitors the medium after it sends a frame to see if the transmission was successful. If successful, the transmission is finished, if not, the frame is sent again.

In the diagram, starts sending the first bit of its frame at t1 and since C sees the channel idle at t2, starts sending its frame at t2. C detects A's frame at t3 and aborts transmission. A detects C's frame at t4 and aborts its transmission. Transmission time for C's frame is, therefore, t3-t2 and for A's frame is t4-t1.

So, the frame transmission time (Tfr) should be at least twice the maximum propagation time (Tp). This can be deduced when the two stations involved in a collision are a maximum distance apart.

frame transmission time (Tfr) ≥ 2 x propagation time (Tp)

Lenth of the Message(L) ≥ 2 x propagation time (Tp) X Bandwidth (BW)

Minimum Frame Size

• For CSMA/CD to work, we need a restriction on the frame size.
• The frame transmission time T_fr must be at least two times the maximum propagation time Tp

Flow Diagram CSMA/CD

Carrier Sense Multiple Access with Collision Avoidance (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) acknowledgment, 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.

• CSMA/CA was invented for the wireless networks to avoid collisions.
• vCollisions are avoided through the use of CSMA/CA's three strategies:
• vThe interframe space, the contention window, and acknowledgments.

The basic idea behind CSMA/CA is that the station should be able to receive while transmitting to detect a collision from different stations. In wired networks, if a collision has occurred then the energy of the received signal almost doubles, and the station can sense the possibility of collision. In the case of wireless networks, most of the energy is used for transmission, and the energy of the received signal increases by only 5-10% if a collision occurs. It can't be used by the station to sense collision. Therefore CSMA/CA has been specially designed for wireless networks.

Flow Diagram CSMA/CA