Computer Network MAC

                                   MULTIPLE ACCESS

• 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 upper sub-layer of the DLL that is responsible for flow and error control is called the logical link control (LLC) layer;
• the lower sub-layer that is mostly responsible for multiple access resolution is called the media access control (MAC) layer.
• Many formal protocols have been devised to handle access to a shared links, We categorize them into three groups.

                            RANDOM ACCESS or CONTENTION METHOD

• In random access no station is superior to another station and none is assigned the control over another.
• 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).
• Two features of random access:
• 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. 
• 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. 
• If 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 or to resolve it when it happens, each station follows a procedure that answers the following questions:
• o When can the station access the medium?
• o What can the station do if the medium is busy?
• o How can the station determine the success or failure of the transmission?
• o What can the station do if there is an access conflict?
• The random access method using ALOHA  protocol which used 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.

                                           ALOHA

• ALOHA, the earliest random access method, was designed for a radio (wireless) LAN, but it can be used on any shared medium.
• When the medium is shared between the stations, the data from the two stations collide and become garbled.

                                                            Pure ALOHA

• The original ALOHA protocol is called pure ALOHA. 
• The idea is that each station sends a frame whenever it has a frame to send.
• When the channel is shared, there is the possibility of collision between frames from different stations. 

Below Figure shows an example of frame collisions in pure ALOHA.

• There are four stations 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. 
• Only two frames survive: frame 1.1 from station 1 and frame 3.2 from station 3.
• The pure ALOHA protocol relies on acknowledgments from the receiver.
• 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 2nd 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.

• 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
• In the below Figure, 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

The throughput for pure ALOHA is S =G x e-2G.

The maximum throughput Smax =0.184 when G =(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. 

Below figure shows an example of frame collisions in slotted ALOHA.

• 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. 
• The vulnerable time is now reduced to one-half, equal to Tfr.
• SlottedALOHA 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.

                          CARRIER SENSE MULTIPLE ACCESS (CSMA)

• 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. 
• The reason for this is propagation delay ( Stations are connected to a shared channel usually a dedicated medium).
• The possibility of collision still exists because of at time t1 station B senses the medium and finds it idle, so it sends a frame. 
• At time t2 (t2> t1) station C senses the medium and finds it idle because, at this time, the first bits from station B have not reached station C. So station C also sends a frame. 
• The two signals collide and both frames are destroyed.

Vulnerable Time : The vulnerable time for CSMA is the propagation time Tp . 

This is the time needed for a signal to propagate from one end of the medium to the other.

When a station sends a frame, and any other station tries to send a frame during this time, a collision will result.

                                               PERSISTENCE METHODS

1. What should a station do if the channel is busy? 
2. What should a station do if the channel is idle? 

Three persistence methods have been devised to answer these questions: 

• I-persistent method
• non-persistent method
• p-persistent method

                                                                          I-Persistent 

In this method, after the station finds the line idle, it sends its frame immediately (with probability I).

This method has the highest chance of collision because two or more stations may find the line idle and send their frames immediately. 

                                                                  Nonpersistent 

In this method, 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. 

The non-persistent approach reduces the chance of collision.

This method reduces the efficiency of the network because the medium remains idle when there may be stations with frames to send.

                                                   The p-persistent method

 It is used if the channel has time slots with a slot duration equal to or greater than the maximum propagation time. 

This approach reduces the chance of collision and improves efficiency. 

In this method, after the station finds the line idle it follows these steps:

1. With probability p, the station sends its frame.

2. With probability q = 1 - p, the station waits for 

   the beginning of the next time slot and 

   checks the line again.

a. If the line is idle, it goes to step 1.

b. If the line is busy, it acts as though a           

                        collision has occurred and uses the back-off                  

                        procedure.

FLOW DIAGRAM FOR THREE PERSISTENCE METHODS 

CARRIER SENSE MULTIPLE ACCESS WITH COLLISION DETECTION (CSMA/CD)

• CSMA/CD augments the algorithm to handle the collision.
• In this method, a station monitors the medium after it sends a frame to see if the transmission was successful. If so, the station is finished. 
• If, however, there is a collision, the frame is sent again.
• Procedure
• We need to sense the channel before we start sending the frame by using one of the persistence processes.
• Transmission and collision detection is a continuous process. We do not send the entire frame ( bit by bit)
• Sending of a short jamming signal that enforces the collision in case other stations have not yet sensed the collision.

CARRIER SENSE MULTIPLE ACCESS WITH COLLISION AVOIDANCE 

• CSMAlCA was invented to avoid collisions on wireless networks .
• Collisions are avoided through the use of CSMA/CA's three strategies:
• the interframe space (used to define the priority of a station)
• the contention window
• acknowledgments
• Interframe Space (IFS)
• When an idle channel is found, the station does not send immediately. It waits for a period of time called the interframe space or IFS. 
• Even though the channel may appear idle when it is sensed, a distant station may have already started transmitting. The distant station's signal has not yet reached this station. 

Contention Window

• The contention window is an amount of time divided into slots. A station that is ready to send chooses a random number of slots as its wait time.
• The station needs to sense the channel after each time slot. 
• However, if the station finds the channel busy, it does not restart the process; it just stops the timer and restarts it when the channel is sensed as idle. 
• This gives priority to the station with the longest waiting time.
• Acknowledgment
• With all these precautions, there still may be a collision resulting in destroyed data , and the data may be corrupted during the transmission. 
• The positive acknowledgment and the time-out timer can help guarantee that the receiver has received the frame.

                                                         CONTROLLED ACCESS

In controlled access, the stations consult one another to find which station has the right to send. 

A station cannot send unless it has been authorized by other stations. 

Three popular controlled-access methods:

1. Reservation
2. Polling
3. Token passing

                                                                     Reservation

• In the reservation method, a station needs to make a reservation before sending data.
• Time is divided into intervals. In each interval, a reservation frame precedes the data frames sent in that interval.

Below Figure shows a situation with five stations and a five-mini slot reservation frame. 

• In the first interval, only stations 1, 3, and 4 have made reservations. 
• In the second interval, only station 1 has made a reservation.

                                                                        Polling

• Here one device is designated as a primary station and the other devices are secondary stations. 
• All data exchanges must be made through the primary device .
• The primary device controls the link; the secondary devices follow its instructions. 
• The primary device is always the initiator of a session.
• If the primary wants to receive data it asks the secondary  if they have anything to send; this is called poll function. 
• If the primary wants to send data, it tells the secondary to get ready to receive; this is called select function.

                                                                    Token Passing

• In the token-passing method, the stations in a network are organized in a logical ring.
• For each station, there is a predecessor and a successor.

                                                                   CHANNELIZATION

Channelization is a multiple-access method in which the available bandwidth of a link is shared in time, frequency, or through code, between different stations. 

Three Channelization protocols:

1. FDMA
2. TDMA
3. CDMA

• In CDMA, one channel carries all transmissions simultaneously.
• Frequency Division Multiple Access or FDMA is a channel access method used in multiple-access protocols as a channelization protocol. FDMA gives users an individual allocation of one or several frequency bands, or channels. It is particularly commonplace in satellite communication.

TDMA

Time division multiple access (TDMA) is a channel access method for shared medium networks. It allows several users to share the same frequency channel by dividing the signal into different time slots. The users transmit in rapid succession, one after the other, each using its own time slot.

CDMA

 "Code Division Multiple Access.”is a wireless transmission technology that was developed during World War II by the English allies to avoid having their transmissions jammed. CDMA is a popular communications method used by many cell phone companies.

Unlike the GSM and TDMA technologies, CDMA transmits over the entire frequency range available. It does not assign a specific frequency to each user on the communications network. This method, called multiplexing, is what made the transmissions difficult to jam during World War II. Because CDMA does not limit each user's frequency range, there is more bandwidth available. This allows more users to communicate on the same network at one time than if each user was allotted a specific frequency range.

Because CDMA is a digital technology, analog audio signals must be digitized before being transmitted on the network. CDMA is used by 2G and 3G wireless communications and typically operates in the frequency range of 800 MHz to 1.9 GHz.