E-Notes 2.0

Unit-2
Multiple Access & LANs

Multiple Access:
It is consider that the data link layer is two sub link layers. The upper sub layer that is
responsible for flow and error control is called the logical link control (LLC) and the lower
sub layer that is mostly responsible for multiple access resolution is called the media access
control (MAC) layer.
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.
The problem of controlling the access to the medium is similar to the rules of speaking
in an assembly. The procedures guarantee that the right to speak is upheld and ensure
that two people do not speak at the same time, do not interrupt each other, do not
monopolize the discussion, and so on.
The situation is similar for multipoint networks. Many formal protocols have been devised
to handle access to a shared link. We categorize them into three groups. Protocols belonging
to each group are shown below.
It is categorized into three groups:
1. Random Access Protocols

2. Controlled Access Protocols
3. Channelization Protocols
(Multiple Access Protocols)
1. 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. This decision depends on the state of the medium
(idle or busy).
Each station can transmit when it desires on the condition that it follows the predefined
procedure, including the testing of the state of the medium. Two features give this method its name.
First, there is no scheduled time for a station to transmit. Transmission is random among the
stations. That is why these methods are called random access. Second, no rules specify which
station should send next. Stations compete with one another to access the medium. That is why
these methods are also called contention methods.
In a random access method, each station has the right to the medium without being controlled
by any other station. However, if more than one station tries to send, there is an access conflict-
collision-and the frames will be either destroyed or modified. ALOHA, is a very simple procedure
called multiple access (MA). The method was improved with the addition of a procedure that
forces the station to sense the medium before transmitting. This was called carrier sense
multiple access. This method later evolved into two parallel methods: carrier sense multiple access
with collision detection (CSMA/CD) and carrier sense multiple access with collision avoidance
(CSMA/CA). CSMA/CD tells the station what to do when a collision is detected. CSMA/CA tries
to avoid the collision.
1.1 ALOHA:
ALOHA, the earliest random access method, was developed at the University of Hawaii in early
1970. It was designed for a radio (wireless) LAN, but it can be used on any shared medium.
There are potential collisions in this arrangement. The medium is shared between the stations.
When a station sends data, another station may attempt to do so at the same time. The data from
the two stations collide and become garbled.
1.1.1 Pure ALOHA
The original ALOHA protocol is called pure ALOHA. This is a simple, but elegant protocol.
The idea is that each station sends a frame whenever it has a frame to send. However, since there
is only one channel to share, there is the possibility of collision between frames from different
stations. Fig. 1 shows an example of frame collisions in pure ALOHA.
Fig. 1. Frames in a pure ALOHA network

There are four stations (unrealistic assumption) that contend with one another for access to
the shared channel. The figure shows that each station sends two frames; there are a total of eight
frames on the shared medium. Some of these frames collide because multiple frames are in
contention for the shared channel. Fig. 1 shows that only two frames survive: frame 1.1 from
station 1 and frame 3.2 from station 3. We need to mention that even if one bit of a frame
coexists on the channel with one bit from another frame, there is a collision and both will
be destroyed. It is obvious that we need to resend the frames that have been destroyed during
transmission.
The pure ALOHA protocol relies on acknowledgments from the receiver. When a station
sends a frame, it expects the receiver to send an acknowledgment. If the acknowledgment
does not arrive after a time-out period, the station assumes that the frame (or the acknowledgment)
has been destroyed and resends the frame.
A collision involves two or more stations. If all these stations try to resend their frames after
the time-out, the frames will collide again. Pure ALOHA dictates that when the time-out period
passes, each station waits a random amount of time before resending its frame. The
randomness will help avoid more collisions. We call this time the back-off time TB.
Pure ALOHA has a second method to prevent congesting the channel with retransmitted
frames. After a maximum number of retransmission attempts Kmax' a station must give up and
try later. Fig. 2 shows the procedure for pure ALOHA based on the above strategy.
Fig. 2: Procedure for pure ALOHA Protocol

The time-out period is equal to the maximum possible round-trip propagation delay, which is
twice the amount of time required to send a frame between the two most widely separated stations
(2 x Tp)' The back-off time TB is a random value that normally depends on K (the number of
attempted unsuccessful transmissions). The formula for TB depends on the implementation. One
common formula is the binary exponential back-off. In this method, for each retransmission, a
multiplier in the range 0 to 2K - 1 is randomly chosen and multiplied by Tp (maximum propagation
time) or Trr (the average time required to send out a frame) to find TB' Note that in this procedure,
the range of the random numbers increases after each collision. The value of Kmax is usually chosen
as 15.
Vulnerable time let us find the length of time, the vulnerable time, in which there is a possibility
of collision. We assume that the stations send fixed-length frames with each frame taking Tfr S to
send. Fig. 3 shows the vulnerable time for station A.
Fig. 3. Vulnerable time for pure ALOHA protocol

Station A sends a frame at time t. Now imagine station B has already sent a frame between t -
Tfr and t. This leads to a collision between the frames from station A and station B. The end of B's
frame collides with the beginning of A's frame. On the other hand, suppose that station C sends a
frame between t and t + Tfr . Here, there is a collision between frames from station A and station
C. The beginning of C's frame collides with the end of A's frame.
Looking at Fig. 3, we see that the vulnerable time, during which a collision may occur in
pure ALOHA, is 2 times the frame transmission time. Pure ALOHA vulnerable time = 2 x Tfr.
1.1.2 Slotted ALOHA

Pure ALOHA has a vulnerable time of 2 x Tfr . This is so because there is no rule that defines when
the station can send. A station may send soon after another station has started or soon before
another station has finished. Slotted ALOHA was invented to improve the efficiency of pure
ALOHA.
In slotted ALOHA we divide the time into slots of Tfr s and force the station to send only at the
beginning of the time slot. Fig. 4 shows an example of frame collisions in slotted ALOHA.
Fig. 4: Frames in a slotted ALOHA network

Because a station is allowed to send only at the beginning of the synchronized time slot, if a station
misses this moment, it must wait until the beginning of the next time slot. This means that the
station which started at the beginning of this slot has already finished sending its frame. Of course,
there is still the possibility of collision if two stations try to send at the beginning of the same time
slot. However, the vulnerable time is now reduced to one-half, equal to Tfr Fig. 5 shows the
situation.
Fig. 5: Vulnerable time for slotted ALOHA protocol

Fig. 5 shows that the vulnerable time for slotted ALOHA is one-half that of pure ALOHA.
Slotted ALOHA vulnerable time = Tfr
Throughput: It can be proved that the average number of successful transmissions for slotted
ALOHA is S = G x e-G. The maximum throughput Smax is 0.368, when G = 1. In other words, if a
frame is generated during one frame transmission time, then 36.8 percent of these frames reach
their destination successfully. This result can be expected because the vulnerable time is equal to
the frame transmission time. Therefore, if a station generates only one frame in this vulnerable
time (and no other station generates a frame during this time), the frame will reach its destination
successfully.
The throughput for slotted ALOHA is S =: G x e-G.
The maximum throughput Smax == 0.368 when G=1.

E-Notes 2.0

Uploaded by

Copyright:

Available Formats

E-Notes 2.0

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

E-Notes 2.0

Uploaded by

Copyright:

Available Formats

Unit-2

Multiple Access & LANs

It is categorized into three groups:

1. Random Access Protocols

1. Random Access Protocols

Fig. 1. Frames in a pure ALOHA network

Fig. 2: Procedure for pure ALOHA Protocol

Fig. 3. Vulnerable time for pure ALOHA protocol

1.1.2 Slotted ALOHA

Fig. 4: Frames in a slotted ALOHA network

Fig. 5: Vulnerable time for slotted ALOHA protocol

You might also like