Module3-Multiple Access.pptx

Module 2: Part III MULTIPLE ACCESS  Outline Three Categories Random Access Protocols Controlled Access Protocols Channelization Protocols  Multiple Access  In data link control protocols, dedicated link between the sender and receiver.  Dat...

Module 2: Part III MULTIPLE ACCESS  Outline Three Categories Random Access Protocols Controlled Access Protocols Channelization Protocols  Multiple Access  In data link control protocols, dedicated link between the sender and receiver.  Data link layer divided into two functionality-oriented sublayers  Upper sublayer is responsible for data link (flow and error) control (Link Layer Control - LLC).  Lower sublayer is responsible for resolving access to the shared media (Medium Access Control - MAC).  Multiple access protocol coordinates to access the link (media).  Multiple Access Protocols Multiple Access Protocols Random Controlled Access Channelization Access Protocols Protocols Protocols Aloha Reservation FDMA CSMA Polling TDMA Token CSMA-CD CDMA Passing CSMA-CA  Random Access Protocols  Rules of random access protocol  no station is master to another station  Every station is equal  No station permits, or not permit another station to send.  Instantly, a station that has data to send uses protocol (decision) on whether or not to send.  Random Access Protocols…  Two features of RAP are Transmission is random among stations. Stations compete with one another to access the medium.  Collision: An access conflict occurs when more than one station tries to send, the frame is either destroyed or modified.  Aloha  Developed at the University of Hawaii (US) in early 1970 and designed for wireless LAN, but can be used on any shared medium.  Original ALOHA protocol is called pure ALOHA  A node sends the frame whenever it has a frame to send.  Medium is shared between the stations, there is possibility of collision between frames from different stations. Pure Aloha  Aloha…  A collision involves two more stations. If all the stations try to send their frames after the time-out, the frames will collide again.  To avoid collision stations will try again in random period, this time is the back-off time TB.  In pure ALOHA, several key factors determine the performance of the system, including the vulnerable time, backoff time, and throughput. 1. Vulnerable Time in Pure ALOHA The vulnerable time is the time during which a collision can occur if another station transmits a packet overlapping with the current packet being transmitted. The transmission time for a packet is denoted by T. In pure ALOHA, since there are no synchronized slots, collisions can occur if another packet is transmitted at any point during the T seconds before or the T seconds after the start of a transmission. Thus, the vulnerable time = 2T (twice the packet transmission time).  2. Backoff Time in Pure ALOHA When a collision occurs in pure ALOHA, the station involved in the collision needs to retransmit the packet after waiting for a random time. This waiting period is called the backoff time. The backoff time is chosen randomly to minimize the chance of repeated collisions. The station typically waits for a random time chosen from a uniform distribution within a predefined range. The backoff time is often represented as a random value between 0 and K × T, where: T is the packet transmission time. K is a constant that increases with each successive collision to ensure that retransmissions are spaced out to avoid repeated collisions.  3. Throughput in Pure ALOHA  The throughput is the fraction of the total transmission attempts that are successful. In pure ALOHA, it is heavily affected by the probability of collisions because stations transmit at random times. Let G represent the average number of packet transmission attempts per packet time T. The probability that a transmission is successful is given by the probability that no other packets are transmitted in the vulnerable time, which is 2T. The probability of no collisions is P(success)=e−2GP(\text{success}) = e^{-2G}P(success)=e−2G. 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.  When G (the traffic intensity) is low, collisions are less likely, and the probability of successful transmission is higher. As G increases, the probability of success decreases rapidly due to more frequent collisions. The maximum throughput (success rate) occurs when G = 0.5, giving a maximum success probability of 1/e ≈ 0.37.  Thus, the maximum efficiency of pure ALOHA is about 18.4%, which occurs at this optimal value of G.  Maximum Throughput:  The throughput S in pure ALOHA is the product of the traffic intensity G and the probability of a successful transmission, which is:  , the maximum throughput of pure ALOHA is about 18.4%. Vulnerable time in pure ALOHA: 2 × T (twice the packet transmission time). Backoff time in pure ALOHA: Randomly chosen from an interval, often 0,K×T0, K × T0,K×T, with K increasing after each collision to space out retransmissions. Throughput in pure ALOHA: Given by S=G⋅e−2GS = G \ cdot e^{-2G}S=G⋅e−2G, with a maximum throughput of about 18.4% occurring at G = 0.5.  All frames are of same size.  Time is divided into slots of size L/R seconds time (equal size slots)  L: Bandwidth and R: Time to transmit 1 frame  Start to transmit frames only at beginning of slots Slotted  Nodes are synchronized so that each node knows Aloha when the slots begin.  If two or more frames collide in a slot, then all the nodes detect the collision event before the slot ends.   When node obtains fresh frame, it transmits in next slot  If no collision is detected , node can send new frame in next slot Slotted  If collision, node retransmits frame in each subsequent Aloha… slot with prob. p until success  The number of collisions is reduced. Hence, the performance become much better compared to Pure Aloha. S.no. On the basis Pure Aloha Slotted Aloha of 1. Basic In pure aloha, data can be transmitted at In slotted aloha, data can be any time by any station. transmitted at the beginning of the time slot. 3. Time Time is not synchronized in pure aloha. Time is globally synchronized in slotted Time is continuous in it. aloha. Time is discrete in it. 4. Number of It does not decrease the number of On the other hand, slotted aloha collisions collisions to half. enhances the efficiency of pure aloha. It decreases the number of collisions to half. 5. Vulnerabl In pure aloha, the vulnerable time is = 2 x Whereas, in slotted aloha, the e time Tt vulnerable time is = Tt 6. Successful In pure aloha, the probability of the In slotted aloha, the probability of the transmissi successful transmission of the frame is - successful transmission of the frame is - on S = G * e-2G S = G * e-G 7. Throughp The maximum throughput in pure aloha is The maximum throughput in slotted ut about 18%. aloha is about 37%. CSMA – Carrier Sense Multiple Access  To minimize the collision CSMA was developed, chance of collision was reduced  Station senses the channel before accessing medium.  The possibility of collision still exists because of propagation delay  Types of CSMA  1-Persistent Method  Non- Persistent Method  P-Persistent Method  1- Persistent Method  If the channel is idle it sends its frame immediately with probability 1  When two or more stations find the line idle and send their frames immediately to create collisions  Non-Persistent Method  If the line is idle it sends its frame immediately.  If the line is busy it waits random amount of time and then senses the line again.  Reduces the collision because it is unlikely that two or more stations will wait the same amount of time and retry  P-Persistent Method  It applies to slotted channels.  It senses the channel, if it is idle, it transmits with a probability p.  With a probability q = 1 - p, it waits for the next slot.  If that slot is idle, it goes to step 1  If the line is busy it act as though collision has occurred and uses the back off procedure. Carrier Sense Multiple Access with Collision Detection (CSMA-CD)  Abort their transmissions as soon as they detect a collision  Waits a random period of time, and then tries again, assuming that no other station has started transmitting in the meantime.  Frame transmission time must be two times the maximum propagation time: Tfr = 2 × Tp  Energy levels: zero, Normal Abnormal. Energy Level during transmission, idleness, or collision  Carrier Sense Multiple Access with Collision Avoidan (CSMA-CA) When there is collision the station receives two signals: its own and the signal transmitted by a second station. In wired network received signal is the same as the sent signal (Losses are less). In wireless network much of the sent energy is lost in transmission (Transmission Losses). Avoid collision on wireless network because they cannot be detected.  CSMA-CA …  When channel is free waits for period of time called the interframe space or IFS.  After IFS time the station still waits to a time equal to the contention time  Contention window is an amount of time divided into slots. Timing in CSMA-CA  Controlled Access Protocols  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.  The three types of Controlled Access Protocols are  Reservation  Polling  Token Passing  Reservation Access Method  A station must make a reservation before sending data  Time is divided into intervals  A reservation frame proceeds each time interval  Number of stations and number of time slots in the reservation frame are equal  Each time slot belongs to a particular station Reservation Access Method…  Polling Method  Devices are categorized as  Primary Station (PS)  Secondary Station (SS)  All data exchange must go through the primary station  Primary station controls the link and initiates the session  Secondary station obey the instructions of PS. 1. PS polls stations  Asking SS if they have something to send 2. PS select a SS  Telling it to get ready to receive data Primary Station (PS) polls stations Primary Station select a Secondary Station  Token Passing Method  Stations in a network are organized in a logical ring, for each station, there is a predecessor and a successor  For a station to access the channel, it must posses a token (special packet) that gives the station the right to access the channel and send its data  Once the station has finished its task, the token will then be passed to the successor (next station)  The station cannot send data until it receives the token again in the next round  Token management is necessary  Every station is limited in the time of token possession  Token must be monitored to ensure no lose or destroyed  Assign priorities to the stations and to the types of data transmitted  To make low-priority stations release the token to high priority stations Token Passing Procedure  Channelization Method  Channelization is a multiple-access method. Here, available bandwidth of a link is shared in time, frequency, or through code, between different stations.  There are three types  Frequency-Division Multiple Access (FDMA)  Time-Division Multiple Access (TDMA)  Code-Division Multiple Access (CDMA)  Frequency Division Multiple Access (FDMA) In FDMA, the available bandwidth of the common channel is divided into bands that are separated by guard bands. Frequency-division multiple access (FDMA)  Time-Division Multiple Access (TDMA) In TDMA, the bandwidth is just one channel that is timeshared between different stations. Time-Division Multiple Access (TDMA)  Code-Division Multiple Access (CDMA) In CDMA, one channel carries all transmissions simultaneously. Code-Division Multiple Access (CDMA)  Frame Formation in Datalink Layer  Bit Stuffing Method  Byte Stuffing Method Bit stuffing refers to the insertion of one or more bits into a data transmission as a way to provide signaling information to a receiver. The receiver knows how to detect, remove or disregard the stuffed bits. Byte stuffing, also known as character stuffing, is a method that adds an extra byte to a data stream or frame to prevent errors:  Bit Stuffing Method  Allows frame to contain arbitrary number of bits and arbitrary character size. The frames are separated by separating flag.  Each frame begins and ends with a special bit pattern, 01111110 called a flag byte. When five consecutive l's are encountered in the data, it automatically stuffs a '0' bit into outgoing bit stream.  In this method, frames contain an arbitrary number of bits and allow character codes with an arbitrary number of bits per character. In this case, each frame starts and ends with a special bit pattern, 01111110.  In the data a 0 bit is automatically stuffed into the outgoing bit stream whenever the sender's data link layer finds five consecutive 1s. Bit Stuffing Method… (a) 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 (b) 0 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 0 010 Stuffed Bits (c) 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0  Byte Stuffing Method  Start and end of frame are recognized with the help of flag bytes.  Each frames starts with and ends with a “Flag Byte”.  Two consecutive flag bytes indicate the end of one frame and start of the next one.  The flag bytes used is named as “ESC” flag byte.  A frame delimited by flag bytes.  Disadvantage:  It is applicable for 8-bit character codes  Byte Stuffing Method… FLAG Heade Payload Field Trailer FLAG r A FLAG B A ESC FLAG B A ESC B A ESC ECS B A ESC FLAG B A ESC ESC ECS FLA B G A ESC ESC B A ESC ESC ECS ESC B a. b. After Original Stuffing  Referenc es  Computer Networks: A Systems Approach, Larry Peterson and Bruce Davie, 5th Ed, The Morgan Kaufmann Series, Elsevier, 2011.  Computer Networking: A Top-Down Approach Featuring the Internet, J. F. Kurose and K. W. Ross, 6th Ed., Pearson Education, 2012.  Data Communications and Networking, Behrouz A. Forouzan, McGraw Hill Education, 5th Ed., 2012  TCP/IP Protocol Suite, Behrouz A. Forouzan, McGraw-Hill Education, 4 Ed., 2009  Data and Computer Communications, William Stallings, Pearson Education, 10th Ed, 2013.