random assignment schemes in mobile computing ppt

Random Access Protocols - ALOHA, CSMA, CSMA/CA and CSMA/CD

Random Access Protocols - a fancy term for a way that computers share a communication channel. Think of it like a group chat, but with lots of people trying to talk at the same time. Random Access Protocols help to manage this chaos by dividing the channel into time slots or packets of data.

It is a Multiple access protocol that is divided into four categories which are ALOHA, CSMA, CSMA/CD, and CSMA/CA. In this article, we will cover all of these Random Access Protocols in detail.

Have you ever been to a railway station? And noticed the ticket counter over there?

What is a Random Access Protocols?

Above are the scenarios for approaching a ticket counter. Which one do you think is more productive? The ordered one, right? And we all know the reason why. Just to get things working and avoid problems we have some rules or protocols, like "please stand in the queue", "do not push each other", "wait for your turn", etc. in the same way computer network channels also have protocols like multiple access protocols , random access protocols , etc.

Let's say you are talking to your friend using a mobile phone. This means there is a link established between you and him. But the point to be remembered is that the communication channel between you and him (the sender & the receiver or vice-versa) is not always a dedicated link, which means the channels are not only providing service to you at that time but to others as well. This means multiple users might be communicating through the same channel.

How is that possible? The reason behind this is the multiple access protocols . If you refer to the OSI model you will come across the data link layer . Now divide the layers into 2 parts, the upper part of the layer will take care of the data link control , and the lower half will be taking care in resolving the access to the shared media , as shown in the above diagram.

The following diagram classifies the multiple-access protocol. In this article, we are going to cover Random Access Protocol.

Random Access Protocols

Once again, let's use the example of mobile phone communication. Whenever you call someone, a connection between you and the desired person is established, also anyone can call anyone. So here we have all the users (stations) at an equal priority, where any station can send data depending on the medium's state whether it is idle or busy, meaning that if your friend is talking to someone else through the mobile phone, then its status is busy and you cannot establish a connection and since all the users are assigned equal priority you can not disconnect your friend's ongoing call and connect yours.

The random access protocols consist of the following characteristics:

There is no time restriction for sending the data (you can talk to your friend without a time restriction).

There is a fixed sequence of stations that are transmitting the data.

As in the above diagram you might have observed that the random-access protocol is further divided into four categories, which are:

Let's cover each one of them, one by one.

ALOHA Random Access Protocol

The ALOHA protocol or also known as the ALOHA method is a random access protocol in which every transmitting station or source in a network will send the data whenever a frame is available for transmission. If we succeed and the frame reaches its destination, the next frame is lined-up for transmission. But remember, if the data frame is not received by the receiver (maybe due to collision) then the frame is sent again until it successfully reaches the receiver's end.

Whenever we talk about a wireless broadcast system or a half-duplex two-way link, the ALOHA method works efficiently. But as the network becomes more and more complex e.g. the ethernet. Now here in the ethernet, the system involves multiple sources and destinations which share a common data path or channel, then the conflict occurs because data-frames collide, and the information is lost. Following is the flow chart of Pure ALOHA .

So, to minimize these collisions and to optimize network efficiency as well as to increase the number of subscribers that can use a given network, the slotted ALOHA was developed. This system consists of signals termed beacons which are sent at precise time intervals and inform each source when the channel is clear to send the frame.

Now, as we came to know about ALOHA's 2 types i.e. Pure & Slotted ALOHA, the following is the difference between these protocols.

CSMA Random Access Protocol

CSMA stands for Carrier Sense Multiple Access . Till now we have understood that when 2 or more stations start sending data, then a collision occurs, so this CSMA method was developed to decrease the chances of collisions when 2 or more stations start sending their signals over the data link layer. But how do they do it? The CSMA makes each station to first check the medium (whether it is busy or not) before sending any data packet.

Here, Vulnerable time = Propagation Time

But, what to do if the channels are busy? Now, here the persistence methods can be applied to help the station act when the channel is busy or idle.

The CSMA has 4 access modes:

1-persistent mode : In this, first the node checks the channel, if the channel is idle then the node or station transmits data, otherwise it keeps on waiting and whenever the channel is idle, the stations transmit the data frame.

Non-persistent mode : In this, the station checks the channel similarly as the 1-persistent mode, but the only difference is that when the channel is busy it checks it again after a random amount of time, unlike the 1-persistent where the stations keep on checking continuously.

P-persistent mode : In this, the station checks the channel and if found idle then it transmits the data frame with the probability of P and if the data is not transmitted (1-P) then the station waits for a random amount of time and again transmits the data with the probability P and this cycle goes on continuously until the data-frame is successfully sent.

O-persistent: In this, the transmission occurs based on the superiority of stations which is decided beforehand and transmission occurs in that order. If the channel is idle, then the station waits for its turn to send the data frame.

Throughput & Efficiency of CSMA :

It is comparatively much greater than the throughput of pure and slotted ALOHA. Here, for the 1-persistent mode, the throughput is 50% when G=1; for the Non-persistent mode, the throughput can reach 90%.

CSMA/CD Random Access Protocol

CSMA/CD means CSMA with Collision Detection .

In this, whenever the station transmits data-frame it then monitors the channel or the medium to acknowledge the state of the transmission i.e. successfully transmitted or failed. If the transmission succeeds, then it prepares for the next frame otherwise it resends the previously failed data frame. The point to remember here is, that the frame transmission time should be at least twice the maximum propagation time, which can be deduced when the distance between the two stations involved in a collision is maximum.

CSMA/CA Random Access Protocol

CSMA/CA means CSMA with collision avoidance .

To detect the possible collisions, the sender receives the acknowledgment and if there is only one acknowledgment present (its own) then this means that the data frame has been sent successfully. But, if there are 2 or more acknowledgment signals then this indicates that the collision has occurred.

This method avoids collisions by:

Interframe space: in this case, assume that your station waits for the channel to become idle and found that the channel is idle, then it will not send the data frame immediately (in order to avoid collision due to propagation delay) it rather waits for some time called interframe space or IFS, and after this time the station again checks the medium for being idle. But it should be kept in mind that the IFS duration depends on the priority of the station.

Contention Window: here, the time is divided into slots. Say, if the sender is ready for transmission of the data, it then chooses a random number of slots as waiting time which doubles every time whenever the channel is busy. But, if the channel is not idle at that moment, then it does not restart the entire process but restarts the timer when the channel is found idle again.

Acknowledgment: as we discussed above that the sender station will re-transmit the data if acknowledgment is not received before the timer expires.

Random Access Protocols play a crucial role in ensuring the efficient and fair transmission of data in computer networks. ALOHA, CSMA, CSMA/CA, and CSMA/CD are some of the widely used Random Access Protocols, each with its unique features and advantages. Understanding these protocols' functioning and differences can help network administrators and engineers choose the appropriate protocol for their specific network requirements. Overall, Random Access Protocols have revolutionized data transmission in computer networks, making communication faster, more reliable, and more efficient.

Frequently Asked Questions(FAQs)

1. is aloha a random access protocol.

Yes, Aloha is a random access protocol in which every transmitting station or source in a network will send the data whenever a frame is available for transmission.

2. Which is better ALOHA or CSMA?

CSMA is better than Aloha random access protocol because the medium is detected before the transmission starts

3. Why are random access protocols used?

Random access protocols are used to allow devices to access the channel without waiting for a specific time slot or permission from a central authority. Instead, devices choose a random time to transmit their data, which reduces the likelihood of collisions.

4. What is CSMA/CD and how is it different from CSMA/CA?

CSMA/CD is a random access protocol used in wired networks. If a collision occurs, devices stop transmitting, wait for a random time, and then try again. CSMA/CA is used in wireless networks and uses the RTS/CTS mechanism to avoid collisions.

You may also like:

• Controlled Access Protocols
• Random Access Protocol
• Controlled Access Protocols - Reservation, Polling & Token Passing
• Carrier Sense Multiple Access

IF YOU LIKE IT, THEN SHARE IT

Related posts.

Chapter: Mobile Computing

Reservation based schemes.

RESERVATION BASED SCHEMES

Polling is the process where the computer or controlling device waits for an external device to check for its readiness or state, often with low-level hardware. For example, when a printer is connected via a parallel port, the computer waits until the printer has received the next character. These processes can be as minute as only reading one bit.

Polling is sometimes used synonymously with busy-wait polling. In this situation, when an I/O operation is required, the computer does nothing other than check the status of the I/O device until it is ready, at which point the device is accessed. In other words, the computer waits until the device is ready. Polling also refers to the situation where a device is repeatedly checked for readiness, and if it is not, the computer returns to a different task. Although not as wasteful of CPU cycles as busy waiting, this is generally not as efficient as the alternative to polling, interrupt-driven I/O.

In a simple single-purpose system, even busy-wait is perfectly appropriate if no action is possible until the I/O access, but more often than not this was traditionally a consequence of simple hardware or non-multitasking operating systems. Polling is often intimately involved with very low-level hardware. For example, polling a parallel printer port to check whether it is ready for another character involves examining as little as one bit of a byte.

That bit represents, at the time of reading, whether a single wire in the printer cable is at low or high voltage. The I/O instruction that reads this byte directly transfers the voltage state of eight real world wires to the eight circuits (flip flops) that make up one byte of a CPU register. Polling has the disadvantage that if there are too many devices to check, the time required to poll them can exceed the time available to service the I/O device. ≠

Polling can be described in following steps:

1.       The host repeatedly reads the busy bit of the controller until it becomes clear.

2.       When clear, the host writes in the command register and writes a byte into the data-out register.

3.       The host sets the command-ready bit (set to 1).

4.       When the controller senses command-ready bit is set, it sets busy bit.

5.       The controller reads the command register and since write bit is set, it performs necessary I/O operations on the device. If the read bit is set to one instead of write bit, data from device is loaded into data-in register, which is further read by the host.

6.       The controller clears the command-ready bit once everything is over, it clears error bit to show successful operation and reset busy bit (0).

A polling cycle is the time in which each element is monitored once. The optimal polling cycle will vary according to several factors, including the desired speed of response and the overhead (e.g., processor time and bandwidth) of the polling.

In roll call polling, the polling device or process queries each element on a list in a fixed sequence. Because it waits for a response from each element, a timing mechanism is necessary to prevent lock-ups caused by non-responding elements. Roll call polling can be inefficient if the overhead for the polling messages is high, there are numerous elements to be polled in each polling cycle and only a few elements are active.

In hub polling, also referred to as token polling, each element polls the next element in some fixed sequence. This continues until the first element is reached, at which time the polling cycle starts all over again.

Polling can be employed in various computing contexts in order to control the execution or transmission sequence of the elements involved. For example, in multitasking operating systems, polling can be used to allocate processor time and other resources to the various competing processes. In networks, polling is used to determine which nodes want to access the network. It is also used by routing protocols to retrieve routing information, as is the case with EGP (exterior gateway protocol).

An alternative to polling is the use of interrupts, which are signals generated by devices or processes to indicate that they need attention, want to communicate, etc. Although polling can be very simple, in many situations (e.g., multitasking operating systems) it is more efficient to use interrupts because it can reduce processor usage and/or bandwidth consumption.

Token Bus is described in the IEEE 802.4 specification, and is a Local Area Network (LAN) in which the stations on the bus or tree form a logical ring. Each station is assigned a place in an ordered sequence, with the last station in the sequence being followed by the first, as shown below. Each station knows the address of the station to its "left" and "right" in the sequence.

This type of network, like a Token Ring network, employs a small data frame only a few bytes in size, known as a token, to grant individual stations exclusive access to the network transmission medium. Token-passing networks are deterministic in the way that they control access to the network, with each node playing an active role in the process. When a station acquires control of the token, it is allowed to transmit one or more data frames, depending on the time limit imposed by the network.

When the station has finished using the token to transmit data, or the time limit has expired, it relinquishes control of the token, which is then available to the next station in the logical sequence. When the ring is initialised, the station with the highest number in the sequence has control of the token. The physical topology of the network is either a bus or a tree, although the order in which stations are connected to the network is not important.

The network topology means that we are essentially dealing with a broadcast network, and every frame transmitted is received by all attached stations. With the exception of broadcast frames, however, frames will only be read by the station to which they are addressed, and ignored by all other stations. As the token frame is transmitted, it carries the destination address of the next station in the logical sequence. As each individual station is powered on, it is allocated a place in the ring sequence (note that in the diagram above, station two is not participating in the ring). The Token Bus medium access control protocol allows stations to join the ring or leave the ring on an ad-hoc basis. Token Bus networks were conceived to meet the needs of automated industrial manufacturing systems and owe much to a proposal by General Motors for a networking system to be used in their own manufacturing plants -Manufacturing Automation Protocol (MAP).

Ethernet was not considered suitable for factory automation systems because of the contention-based nature of its medium access control protocol, which meant that the length of time a station might have to wait to send a frame was unpredictable. Ethernet also lacked a priority system, so there was no way to ensure that more important data would not be held up by less urgent traffic.

A token-passing system in which each station takes turns to transmit a frame was considered a better option, because if there are n stations, and each station takes T seconds to send a frame, no station has to wait longer than T seconds to acquire the token. The ring topology of existing token-passing systems, however, was not such an attractive idea, since a break in the ring would cause a general network failure.

A ring topology was also considered to be incompatible with the linear topology of assembly-line or process control systems. Token Bus was a hybrid system that provided the robustness and linearity of a bus or tree topology, whilst retaining the known worst-case performance of a token-passing medium access control method. The transmission medium most often used for broadband Token Bus networks is 75 Ohm coaxial cable (the same type of cable used for cable TV), although alternative cabling configurations are available. Both single and dual cable systems may be used, with or without head-ends.

Related Topics

Privacy Policy , Terms and Conditions , DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.

• Engineering Mathematics
• Discrete Mathematics
• Operating System
• Computer Networks
• Digital Logic and Design
• C Programming
• Data Structures
• Theory of Computation
• Compiler Design
• Computer Org and Architecture

Classification of MAC protocols

• Types of Authentication Protocols
• Constrained Application Protocol (CoAP)
• Classes of Routing Protocols
• S-MAC Protocol in WSNs
• Wireless Application Protocol
• Network Protocols and Communications
• Application Layer Protocols in TCP/IP
• Session Initiation Protocol
• Critique of OSI Model and Protocols
• Classification of TCP Performance Schemes in Wireless Network
• ARP Protocol Packet Format
• Principles of Network Applications
• Noisy Channels Protocols
• JavaScript Location protocol Property
• Application Protocol | System Design
• java.net.ProtocolFamily Class in Java
• Communication Protocols In System Design
• How can Communication Protocols Enhance System Security?
• Types of Internet Protocols

MAC protocol is the first protocol layer above the Physical Layer in ad hoc .The primary task of any MAC protocol is to control the access of the nodes to shared medium.

Classification of MAC protocols : These are as following below.

• Bandwidth are not reserved.
• No guarantees.
• Bandwidth is reserved for transmission.
• Guarantees can be given.
• Distributed scheduling is done between nodes.
• Combine multiple features of other protocols.
• It can also use a completely new approach.

1. Contention-based protocols without reservation/scheduling –

• Single-channel sender initiated. For example, MACAW, FAMA.
• Multiple-channel sender initiated protocols. For example, BTMA, DBTMA, ICSMA.
• Receiver-initiated protocols : The connection is initiated by the receiver node. For example, RI-BTMA, MACA-BI, MARCH.

2. Contention-based protocols with reservation mechanisms –

• Synchronous protocols : All node are kept synchronized. For example, D-PRMA, CATA, HRMA, SRMA/PA, FPRP.
• Asynchronous protocols : Relative time information is used to achieve effecting reservations. For example, MACA/PR, RTMAC..

Contention-based protocols with scheduling mechanisms – All the nodes are treated equally and no node is get deprived of bandwidth. For example, Eg. DPS, DWOP, DLPS.

Other protocols – These MAC protocols do not strictly fall into any above category. For example, MMAC, MCSMA, PCM, RBAR.

Please Login to comment...

Similar reads, improve your coding skills with practice.

What kind of Experience do you want to share?

Computer Network

• Operating Systems
• Computer Fundamentals
• Interview Q

Physical Layer

Data link layer, network layer, routing algorithm, transport layer, application layer, application protocols, network security.

Interview Questions

• Send your Feedback to [email protected]

Help Others, Please Share

Learn Latest Tutorials

Transact-SQL

Reinforcement Learning

R Programming

React Native

Python Design Patterns

Python Pillow

Python Turtle

Preparation

Verbal Ability

Company Questions

Trending Technologies

Artificial Intelligence

Cloud Computing

Data Science

Machine Learning

B.Tech / MCA

Data Structures

Operating System

Compiler Design

Computer Organization

Discrete Mathematics

Ethical Hacking

Computer Graphics

Software Engineering

Web Technology

Cyber Security

C Programming

Control System

Data Mining

Data Warehouse