Home | | Mobile Computing | Random Assignment Schemes

Chapter: Mobile Computing

Random Assignment Schemes

Pure Aloha: With Pure Aloha, stations are allowed access to the channel whenever they have data to transmit. Because the threat of data collision exists, each station must either monitor its transmission on the rebroadcast or await an acknowledgment from the destination station.



Pure Aloha


With Pure Aloha, stations are allowed access to the channel whenever they have data to transmit. Because the threat of data collision exists, each station must either monitor its transmission on the rebroadcast or await an acknowledgment from the destination station. By comparing the transmitted packet with the received packet or by the lack of an acknowledgement, the transmitting station can determine the success of the transmitted packet. If the transmission was unsuccessful it is resent after a random amount of time to reduce the probability of re-collision.


Slotted Aloha


The first of the contention based protocols we evaluate is the Slotted Aloha protocol. The channel bandwidth is a continuous stream of slots whose length is the time necessary to transmit one packet. A station with a packet to send will transmit on the next available slot boundary. In the event of a collision, each station involved in the collision retransmits at some random time in order to reduce the possibility of recollision.


Obviously the limits imposed which govern the random retransmission of the packet will have an effect on the delay associated with successful packet delivery. If the limit is too short, the probability of recollision is high. If the limit is too long the probability of recollision lessens but there is unnecessary delay in the retransmission. For the Mars regional network studied here, the resending of the packet will occur at some random time not greater than the burst factor times the propagation delay.


Another important simulation characteristic of the Slotted Aloha protocol is the action which takes place on transmission of the packet. Methods include blocking (i.e. prohibiting packet generation) until verification of successful transmission occurs. This is known as "stop-and-wait". Another method known as "go-back-n" allows continual transmission of queued packets, but on the detection of a collision, will retransmit all packets from the point of the collision.


This is done to preserve the order of the packets. In this simulation model queued packets are continually sent and only the packets involved in a collision are retransmitted. This is called "selective-repeat" and allows out of order transmission of packets. By making a small restriction in the transmission freedom of the individual stations, the throughput of the Aloha protocol can be doubled.


Assuming constant length packets, transmission time is broken into slots equivalent to the transmission time of a single packet. Stations are only allowed to transmit at slot boundaries. When packets collide they will overlap completely instead of partially. This has the effect of doubling the efficiency of the Aloha protocol and has come to be known as Slotted Aloha.



CSMA is a network access method used on shared network topologies such as Ethernet to control access to the network. Devices attached to the network cable listen (carrier sense) before transmitting. If the channel is in use, devices wait before transmitting. MA (Multiple Access) indicates that many devices can connect to and share the same network. All devices have equal access to use the network when it is clear.


In other words, a station that wants to communicate "listen" first on the media communication and awaits a "silence" of a preset time (called the Distributed Inter Frame Space or DIFS). After this compulsory period, the station starts a countdown for a random period considered. The maximum duration of this countdown is called the collision window (Window Collision, CW). If no equipment speaks before the end of the countdown, the station simply deliver its package. However, if it is overtaken by another station, it stops immediately its countdown and waits for the next silence. She then continued his account countdown where it left off.


The waiting time random has the advantage of allowing a statistically equitable distribution of speaking time between the various network equipment, while making little unlikely (but not impossible) that both devices speak exactly the same time. The countdown system prevents a station waiting too long before issuing its package. It's a bit what place in a meeting room when no master session (and all the World's polite) expected a silence, then a few moments before speaking, to allow time for someone else to speak. The time is and randomly assigned, that is to say, more or less equally.


Again, this is what we do naturally in a meeting room if many people speak exactly the same time, they are realizing account immediately (as they listen at the same time they speak), and they interrupt without completing their sentence. After a while, one of them speaks again. If a new collision occurs, the two are interrupted again and tend to wait a little longer before speaking again.


CSMA protocol was developed to overcome the problem found in ALOHA i.e. to minimize the chances of collision, so as to improve the performance. CSMA protocol is based on the principle of 'carrier sense'. The station senses the carrier or channel before transmitting a frame. It means the station checks the state of channel, whether it is idle or busy.


Even though devices attempt to sense whether the network is in use, there is a good chance that two stations will attempt to access it at the same time. On large networks, the transmission time between one end of the cable and another is enough that one station may access the cable even though another has already just accessed it.


The chances of collision still exist because of propagation delay. The frame transmitted by one station takes some time to reach other stations. In the meantime, other stations may sense the channel to be idle and transmit their frames. This results in the collision.


There Are Three Different Type of CSMA Protocols


(I) I-persistent CSMA


(ii) Non- Persistent CSMA

(iii)    p-persistent CSMA


(i) I-persistent CSMA


In this method, station that wants to transmit data continuously senses the channel to check whether the channel is idle or busy. If the channel is busy, the station waits until it becomes idle. When the station detects an idle-channel, it immediately transmits the frame with probability 1. Hence it is called I-persistent CSMA. This method has the highest chance of collision because two or more stations may find channel to be idle at the same time and transmit their frames. When the collision occurs, the stations wait a random amount of time and start all over again.


Drawback of I-persistent


The propagation delay time greatly affects this protocol. If after the station I begins its transmission, station 2 also became ready to send its data and senses the channel. If the station I signal has not yet reached station 2, station 2 will sense the channel to be idle and will begin its transmission. This will result in collision.

Even if propagation delay time is zero, collision will still occur. If two stations became  .ready in the middle of third station's transmission, both stations will wait until the transmission of first station ends and then both will begin their transmission exactly simultaneously. This will also result in collision.


(ii) Non-persistent CSMA


In this scheme, if a station wants to transmit a frame and it finds that the channel is busy (some other station is transmitting) then it will wait for fixed interval of time. After this time, it again checks the status of the channel and if the channel is free it will transmit. A station that has a frame to send senses the channel.


If the channel is idle, it sends immediately. If the channel is busy, it waits a random amount of time and then senses the channel again. In non-persistent CSMA the station does not continuously sense the channel for the purpose of capturing it when it detects the end of previous transmission.


Advantage of non-persistent


It reduces the chance of collision because the stations wait a random amount of time. It is unlikely that two or more stations will wait for same amount of time and will retransmit at the same time.


Disadvantage of non-persistent


It reduces the efficiency of network because the channel remains idle when there may be stations with frames to send. This is due to the fact that the stations wait a random amount of time after the collision.

(iii) p-persistent CSMA


This method is used when channel has time slots such that the time slot duration is equal to or greater than the maximum propagation delay time. Whenever a station becomes ready to send, it senses the channel. If channel is busy, station waits until next slot. If channel is idle, it transmits with a probability p.


With the probability q=l-p, the station then waits for the beginning of the next time slot. If the next slot is also idle, it either transmits or waits again with probabilities p and q. This process is repeated till either frame has been transmitted or another station has begun transmitting. In case of the transmission by another station, the station acts as though collision


has occurred and it waits a random amount of time and starts again.



Advantage of p-persistent


• It reduces the chance of collision and improves the efficiency of the network.


Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail
Mobile Computing : Random Assignment Schemes |

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

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