MULTIPLE ACCESS PROTOCOLS, Collision Detection, A Bit-Map Protocol ,Wireless LAN Protocols, Computer Network all notes, Computer Network ,Network Hardware Components, Network Software Components

MULTIPLE ACCESS PROTOCOLS, Collision Detection, A Bit-Map Protocol ,Wireless LAN Protocols, Computer Network all notes, Computer Network ,Network Hardware Components, Network Software Components

 MULTIPLE ACCESS PROTOCOLS 

Any algorithms for allocating a multiple access channel are known. In the following sections, we will study a small sample of the more interesting ones and give some examples of how they are commonly used in practice.

ALOHA 

•  The story of our first MAC starts out in pristine Hawaii in the early 1970s. In this case, ‘‘pristine’’ can be interpreted as ‘‘not having a working telephone system.’’ This did not make life more pleasant for researcher Norman Abramson and his colleagues at the University of Hawaii who were trying to connect users on re- mote islands to the main computer in Honolulu. 

• The one they found used short-range radios, with each user terminal sharing the same upstream frequency to send frames to the central computer. It included a simple and elegant method to solve the channel allocation problem. 

•  Their work has been extended by many researchers since then (Schwartz and Abramson, 2009). Although Abramson’s work, called the ALOHA system, used ground- based radio broadcasting, the basic idea is applicable to any system in which uncoordinated users are competing for the use of a single shared channel. 

•  We will discuss two versions of ALOHA here: pure and slotted. They differ with respect to whether time is continuous, as in the pure version, or divided into discrete slots into which all frames must fit. 

Pure ALOHA 

• The basic idea of an ALOHA system is simple: let users transmit whenever they have data to be sent. There will be collisions, of course, and the colliding frames will be damaged. Senders need some way to find out if this is the case. In the ALOHA system, after each station has sent its frame to the central computer, this computer rebroadcasts the frame to all of the stations 

•  If the frame was destroyed, the sender just waits a random amount of time and sends it again. The waiting time must be random or the same frames will collide over and over, in lockstep, Systems in which multiple users share a common channel in a way that can lead to conflicts are known as contention systems. 

• A user is always in one of two states: typing or waiting. Initially, all users are in the typing state. When a line is finished, the user stops typing, waiting for a response. The station then transmits a frame containing the line over the shared channel to the central computer and checks the channel to see if it was successful. 

•  If N > 1, the user community is generating frames at a higher rate than the channel can handle, and nearly every frame will suffer a collision. For reasonable throughput, we would expect 0 < N < 1.

•  Let us further assume that the old and new frames combined are well modeled by a Poisson distribution, with mean of G frames per frame time. Clearly, G N. At low load (i.e., N 0), there will be few collisions, hence few retransmissions, so G N. At high load, there will be many collisions, so G > N.

•  If any other user has generated a frame between time t 0 and t 0 t, the end of that frame will collide with the beginning of the shaded one. 

• In fact, the shaded frame’s fate was already sealed even before the first bit was sent, but since in pure ALOHA a station does not listen to the channel before transmitting, it has no way of knowing that another frame was already underway. Similarly, any other frame started between t 0 t and t 0 2t will bump into the end of the shaded frame

• The probability that k frames are generated during a given frame time, in which G frames are expected, is given by the Poisson distribution 

• so the probability of zero frames is just e G. In an interval two frame times long, the mean number of frames generated is 2G. The probability of no frames being initiated during the entire vulnerable period is thus given by P 0 e 2G. Using S GP 0, we get 

  S Ge 2G  

•  The relation between the offered traffic and the throughput is shown in Fig. 4-3. The maximum throughput occurs at G 0.5, with S 1/2e, which is about 0.184. In other words, the best we can hope for is a channel utilization of 18%. This result is not very encouraging, but with everyone transmitting at will, we could hardly have expected a 100% success rate. 

Slotted ALOHA :

• Soon after ALOHA came onto the scene, Roberts (1972) published a method for doubling the capacity of an ALOHA system. His proposal was to divide time into discrete intervals called slots, each interval corresponding to one frame. 

•  In Roberts’ method, which has come to be known as slotted ALOHA—in contrast to Abramson’s pure ALOHA—a station is not permitted to send when- ever the user types a line.

• Instead, it is required to wait for the beginning of the next slot. Thus, the continuous time ALOHA is turned into a discrete time one. This halves the vulnerable period. To see this, look at Fig and imagine the collisions that are now possible. The probability of no other traffic during the same slot as our test frame is then e G, which leads to 

   S Ge G  

• slotted ALOHA peaks at G = 1, with a throughput of S = 1/e or about 0.368, twice that of pure ALOHA. If the system is operating at G 1, the probability of an empty slot is 0.368  The best we can hope for using slotted ALOHA is 37% of the slots empty, 37% successes, and 26% collisions. 

• Operating at higher values of G reduces the number of empties but increases the number of collisions exponentially. To see how this rapid growth of collisions with G comes about, consider the transmission of a test frame. The probability that it will avoid a collision is e G, which is the probability that all the other stations are silent in that slot. 

•  The probability of a collision is then just 1 e G. The probability of a transmission requiring exactly k attempts (i.e., k 1 collisions followed by one success) is 

   Pk e G (1 e G )k 1 

♦ Carrier Sense Multiple Access Protocols 

•  This low result is hardly surprising, since with stations transmitting at will, with- out knowing what the other stations are doing there are bound to be many collisions. 

• In LANs, however, it is often possible for stations to detect what other stations are doing, and thus adapt their behavior accordingly. These networks can achieve a much better utilization than 1/e. In this section, we will discuss some protocols for improving performance. 

• Protocols in which stations listen for a carrier (i.e., a transmission) and act accordingly are called carrier sense protocols.

•  A number of them have been proposed, and they were long ago analyzed in detail. For example, see Kleinrock and Tobagi (1975). Below we will look at several versions of carrier sense protocols.

Persistent and Nonpersistent CSMA 

• The first carrier sense protocol that we will study here is called 1-persistent CSMA (Carrier Sense Multiple Access). That is a bit of a mouthful for the simplest CSMA scheme. When a station has data to send, it first listens to the channel to see if anyone else is transmitting at that moment. 

•  If the first station’s signal has not yet reached the second one, the latter will sense an idle channel and will also begin sending, resulting in a collision. This chance depends on the number of frames that fit on the channel, or the bandwidth-delay product of the channel. 

•  This protocol has better performance than pure ALOHA because both stations have the decency to desist from interfering with the third station’s frame. Exactly the same holds for slotted ALOHA. 

•  A second carrier sense protocol is nonpersistent CSMA. In this protocol, a conscious attempt is made to be less greedy than in the previous one. As before, a station senses the channel when it wants to send a frame, and if no one else is sending, the station begins doing so itself. 

•  The last protocol is p-persistent CSMA. It applies to slotted channels and works as follows. When a station becomes ready to send, it senses the channel. If it is idle, it transmits with a probability p. With a probability q 1 p, it defers until the next slot. If that slot is also idle, it either transmits or defers again, with probabilities p and q. 

• This process is repeated until either the frame has been transmitted or another station has begun transmitting. In the latter case, the unlucky station acts as if there had been a collision (i.e., it waits a random time and starts again). If the station initially senses that the channel is busy, it waits until the next slot and applies the above algorithm. IEEE 802.11 uses a refinement of p-persistent CSMA .

 Fig. Comparison of the channel utilization versus load for various random access protocols. 

CSMA with Collision Detection 

•  Persistent and nonpersistent CSMA protocols are definitely an improvement over ALOHA because they ensure that no station begins to transmit while the channel is busy. 

•  Another improvement is for the stations to quickly detect the collision and abruptly stop transmitting, (rather than finishing them) since they are irretrievably garbled anyway. This strategy saves time and bandwidth. 

•  This protocol, known as CSMA/CD (CSMA with Collision Detection), is the basis of the classic Ethernet LAN, so it is worth devoting some time to looking at it in detail. It is important to realize that collision detection is an analog process. The station’s hardware must listen to the channel while it is transmitting. 

• CSMA/CD, as well as many other LAN protocols, uses the conceptual model of Fig. 4-5. At the point marked t 0, a station has finished transmitting its frame. Any other station having a frame to send may now attempt to do so. If two or more stations decide to transmit simultaneously, there will be a collision. 

• The minimum time to detect the collision is just the time it takes the signal to propagate from one station to the other. Based on this information, you might think that a station that has not heard a collision for a time equal to the full cable propagation time after starting its transmission can be sure it has seized the cable. 

•  o Consider the following worst-case scenario. Let the time for a signal to propagate between the two farthest stations be . At t 0, one station begins trans- mitting. At t 0 , an instant before the signal arrives at the most distant station, that station also begins transmitting. 

• it detects the collision al- most instantly and stops, but the little noise burst caused by the collision does not get back to the original station until time 2 . In other words, in the worst case a station cannot be sure that it has seized the channel until it has transmitted for 2 without hearing a collision. 

•  The difference for CSMA/CD compared to slotted ALOHA is that slots in which only one station transmits (i.e., in which the channel is seized) are followed by the rest of a frame. This difference will greatly improve performance if the frame time is much longer than the propagation time. 

A Bit-Map Protocol 

•  In our first collision-free protocol, the basic bit-map method, each contention period consists of exactly N slots. If station 0 has a frame to send, it transmits a 1 bit during the slot 0. 

• In general, station j may announce that it has a frame to send by inserting a 1 bit into slot j. After all N slots have passed by, each station has complete knowledge of which stations wish to transmit.

• Since everyone agrees on who goes next, there will never be any collisions. After the last ready station has transmitted its frame, an event all stations can easily monitor, another N-bit contention period is begun.

•  Protocols like this in which the desire to transmit is broadcast before the actual transmission are called reservation protocols because they reserve channel ownership in advance and prevent collisions. 

• Under conditions of low load, the bit map will simply be repeated over and over, for lack of data frames. Consider the situation from the point of view of a low numbered station, such as 0 or 1. Typically, when it becomes ready to send, the ‘‘current’’ slot will be somewhere in the middle of the bit map

Wireless LAN Protocols :

•  A system of laptop computers that communicate by radio can be regarded as a wireless LAN,  Such a LAN is an example of a broadcast channel. It also has somewhat different properties than a wired LAN, which leads to different MAC protocols. 

• There is an even more important difference between wireless LANs and wired LANs. A station on a wireless LAN may not be able to transmit frames to or receive frames from all other stations because of the limited radio range of the stations. 

•  The naive approach to using a wireless LAN might be to try CSMA: just listen for other transmissions and only transmit if no one else is doing so. The trouble is, this protocol is not really a good way to think about wireless because what matters for reception is interference at the receiver, not at the sender.

Fig. A wireless LAN. (a) A and C are hidden terminals when trans- mitting to B. (b) B and C are exposed terminals when transmitting to A and D. 

• First consider what happens when A and C transmit to B, as depicted in Fig.(a). If A sends and then C immediately senses the medium, it will not hear A because A is out of range. Thus C will falsely conclude that it can transmit to B. If C does start transmitting, it will interfere at B, wiping out the frame from A. 

• We want a MAC protocol that will prevent this kind of collision from happening because it wastes bandwidth. The problem of a station not being able to detect a potential competitor for the medium because the competitor is too far away is called the hidden terminal problem. 

• In fact, such a transmission would cause bad reception only in the zone between B and C, where neither of the intended receivers is located. We want a MAC protocol that prevents this kind of deferral from happening because it wastes bandwidth. The problem is called the exposed terminal problem. 

• We want this concurrency to happen as the cell gets larger and larger, in the same way that people at a party should not wait for everyone in the room to go silent before they talk; multiple conversations can take place at once in a large room as long as they are not directed to the same location. 

• An early and influential protocol that tackles these problems for wireless LANs is MACA (Multiple Access with Collision Avoidance) (Karn, 1990). The basic idea behind it is for the sender to stimulate the receiver into outputting a short frame, so stations nearby can data frames

•  MACA is illustrated Let us see how A sends a frame to B. A starts by sending an RTS (Request To Send) frame to B, as shown in Fig. (a). This short frame (30 bytes) contains the length of the data frame that will eventually follow. 

•  Then B replies with a CTS (Clear To Send) frame, as shown in Fig. (b). The CTS frame contains the data length (copied from the RTS frame). Upon receipt of the CTS frame, A begins transmission.