Mac layer protocols static and dynamic allocation

(rev. Mar 29, 2015)

Notes On Chapter Fourteen -- The IEEE MAC Sub-Layer

• 14.0 Study Guide

• Know the basics of how these controlled access protocols work: polling, reservation, and token passing.
• Understand the basics of how ALOHA, CSMA/CD, and CSMA/CA work.

• IEEE MAC sublayer
• Multi-access Protocols
• Static and Dynamic Channel Allocation

• Three approaches by which computers can coordinate access to a shared medium are:
  • Controlled Access Protocols - for example:
    • Reservation
    • Polling
    • Token Passing
    • ALOHA
    • CSMA/CD
    • CSMA/CA
    • FDMA
    • TDMA
    • CDMA
    • An FDM system can assign a channel for the exclusive use of a communicating pair of computers.
    • In some cases a static assignment will suffice.
    • In many cases the pairs communicating will vary over time, so channels need to be allocated and deallocated dynamically.
    • Examples:
      • FDMA - Frequency Division Multi-Access - for example:
        • 'New station' uses reserved control channel to make a request to a 'central controller'
        • Central controller chooses an unused channel and assigns it to the station
        • A station is assigned a time slot during which it is allowed to send
        • This could be a round-robin scheme -- so, for example, the station might be allowed to send every 3rd packet among a set of 25 stations.
        • All senders may send at the same time - they send "mutually orthogonal" data which is multiplexed by summing. This is comparable to interleaving at the bit level.
        • 14.5.1 Polling
          • Centralized controller polls 'stations',giving them an opportunity to send one packet
          • selection may be simple round robin or some priority scheme.
          • the controller sends a polling message to a station and the station responds, either by sending a packet, or 'passing'.
          • Stations send messages in rounds.
          • Typically for a period of time, stations send messages to a central controller saying whether they will have a need to send a message in the next round.
          • Then the controller transmits a list of stations that will be transmitting in the next round.
          • Stations then use the list to determine when to send during the next round.
          • Variation: there is a separate channel for controller to use to gather reservations.
          • This technique is often used with satellite transmission.
          • There is a special control message called the token .
          • The token is passed from station to station according to some preassigned 'circular order'.
          • When a station has the token, it is allowed to transmit a message.
          • The station passes the token immediately, or right after sending its message.
          • 14.6.1 ALOHA
            • A protocol used in an early data network in Hawaii.
            • The medium was radio frequency
            • ALOHA pioneered 'random access techniques'
            • A central station with a powerful transmitter is surrounded by outlying stations with weaker transmitters.
            • Transmissions of the central station can reach all outlying stations, and transmissions of all outlying stations can reach the central station.
            • Transmissions of most outlying stations can't reach all the other outlying stations.
            • The network employs two different frequencies - an outbound frequency for the central station to send messages to outlying stations, and an inbound frequency for outlying stations to send messages to the central station.
            • An outlying station that wants to send a packet to another outlying station transmits the packet to the central station on the inbound frequency. The central station then resends the packet on the outbound frequency. Both the intended receiver and the sender get a copy of the packet sent by the central station. The copy that is received by the original sender serves as an acknowledgment that the packet arrived safely.
            • Two outlying stations might send a packet at the same time. If so they interfere with each other ( collide ), are unintelligible to the central station, and are NOT resent by the central station on the outbound frequency.
            • If an outlying station sends a packet, and does not soon receive a copy of the packet back on the outbound frequency, then the outlying station will retransmit the packet, after a random delay .
            • Because retransmission delays are randomly chosen, there is a low probability that the two senders that collided before will collide again.
            • If the network is heavily utilized collisions can happen frequently despite these measures.
            • The original Ethernet (named after the luminiferous ether once theorized to be a medium that made the propagation of light possible) employs a single long cable (the ether) onto which all computers connect and transmit.
            • Ethernet Carrier Sense Multi-Access with Collision Detection (CSMA/CD) is similar to ALOHA but utilizes several innovations:
              • The "two-frequency idea" was dropped.
              • An NIC "carrier senses" and refrains from attempting to send while a transmission is in progress (this improves utilization).
              • Stations monitor the ether (the shared cable) while sending, and abort transmission if a collision is detected.
              • After detecting a collision, an NIC utilizes a binary exponential back-off strategy:
                • wait a random time (bounded by some constant d) and attempt to retransmit. [d is the max time it would take for a frame to travel from one host to another on the shared medium. The value of d is about 50 μs for 10 Mbs Ethernet, and about 5 μs for 100Mbs or 1Gbs Ethernets.]
                • If a second collision occurs, abort again and pick another random delay, this time bounded by 2d.
                • If collisions keep recurring while trying to send the same packet, keep doubling the maximum delay until success (or after trying some large number of times, give up.)