4.2 MULTIPLE ACCESS PROTOCOLS

• The story of our first MAC protocol 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 remote 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.
• Although Abramson’s work, called the ALOHA system, used groundbased

  radio broadcasting, the basic idea is applicable to any system in which uncoordinated users are competing for the use of a single shared channel.
• 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, as in the slotted version.
• Systems in which multiple users share a common channel

  in a way that can lead to conflicts are known as contention systems.
• 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 whenever the user types a line.
• 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
• 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.
• This chance depends on the number of frames that fit on the channel, or the bandwidth-delay product of the channel.
• 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 immediately.
• 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.
• 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.
• 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.
• 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.
• The essence of the bit-map protocol is that it lets every station transmit a frame in turn in a predefined order. Another way to accomplish the same thing is to pass a small message called a token from one station to the next in the same predefined order. The token represents permission to send. If a station has a frame queued for transmission when it receives the token,
• In a token ring protocol, the topology of the network is used to define the

  order in which stations send. The stations are connected one to the next in a single ring.
• Possession of the token allows a station to use the bus to send one frame.

  This protocol is called token bus. It is defined in IEEE 802.4, a standard that

  failed so badly that IEEE has withdrawn it.
• In the 1990s, a much faster token ring called FDDI (Fiber Distributed Data Interface) was beaten out by switched Ethernet. In the 2000s, a token ring called RPR (Resilient Packet Ring) was defined as IEEE 802.17 to standardize the mix of metropolitan area rings in use by ISPs.
• All addresses are assumed to be the same number of

  bits. The bits in each address position from different stations are BOOLEAN

  ORed together by the channel when they are sent at the same time. We will call this protocol binary countdown. It was used in Datakit (Fraser, 1983). It implicitly

  assumes that the transmission delays are negligible so that all stations see

  asserted bits essentially instantaneously.
• Such protocols, which we will call limited-contention protocols, do in fact exist, and will conclude our study of carrier sense networks.
• 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.
• 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.
• An early and quite influential protocol that tackles these problems for wireless

  LANs is MACA (Multiple Access with Collision Avoidance)
• A starts by sending an RTS (Request To Send) frame to B, as shown in Fig. 4-12(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. 4-12(b).