Medium Access Control Sublayer

The assumption in the datalink layer is one of direct, point-to-point connections. The (lack of) scalability of a fully-connected network means that at some point we have to use fewer wires than our point-to-point model requires. What then? We share the medium. The question that underlies the MAC sublayer is "how do we share a single physical medium?"

Characteristics of LANs: high speed (1Mbps minimum, 2Gbps max), geographically limited (1 meter to 10km)

LANs are used for

Motivation for MAC protocols

Is static channel allocation in LANs and MANs suitable? In other words, why worry about sharing one channel? We know why we have to worry about sharing one medium, but we could use some multiplexing to put multiple channels on to it.

Static FDM

Less than the number of preassigned stations using the channels  means bandwidth wasted. Simple queueing calculations show this: Capacity of the channel ---> C / mean frame length = C * mu frames/second
Queueing result Let's divide this channel into N independent subchannels each with capacity of C/N bps. The mean input rate of each is lambda / N (i.e. the same aggregate load is being offered, just split among N sources, each using 1/Nth of the BW available). The delay in this case is This says that the mean delay for N channels is N times worse than the single channel case. The same arguments that apply to FDM also apply to synchronous TDM. The problem is that lots of bandwidth is wasted in idle channels, and not available to the transmitting host. This problem is made even worse by the peaky nature of network traffic.

Asynchronous TDM

In ATDM a central concentrator performs the arbitration and thus avoids the collisions. In LANs stations are not physically located close to each other. Need other solutions.

Conclusion: we need dynamic channel allocation in LANs and MANs.

LAN Components

NIC - network interface cards Tranceiver

Connectors, Terminators, Repeaters

Media, Wiring Hubs, MAU

Medium Access Control

How to share access to medium?  Geograhpical distribution means that nodes are separated in time, so collisions will happen when two broadcast at once. We must either prevent collisions on the shared channel, or cope with them when they happen.

Aloha

The pioneering work, done in the 1970s, to connect computers via radio broadcast, on the islands of Hawaii.

Stations transmit whenever they have data to send. They then listen to the channel to determine if a collision took place. If so, they delay for a random amount of time then retransmit. Hopefully the colliding stations delay for different random delays and avoid collision the next time.

The analysis is based on queuing theory, which requires nice distributions for traffic arrival (Poisson). It is known now that this is a poor model for real network traffic, and that a fractal model is better.

The utilization of the channel is bad, but can be improved by synchronizing the stations (slotted Aloha).

<figure 4.3 on U of Aloha versus offered traffic>

CSMA

Big improvements can be made in U if a station first checks to see if the channel is in use before broadcasting.

CS - carrier can be sensed to determine if channel is in use
MA - multiple stations share single channel

Each packet includes a source and destination address so that the broadcast medium supports unicast messaging. Applied in bus and radio broadcast topologies.

Different strategies can be employed concerning how greedy a station is in grabbing the idle channel. These strategies improve  utilization of the channel.

CSMA/CD

The next improvement is to have each station monitor the channel while it is sending data. If a collision is detected the transmission is stopped immediately. This means less wasted time in collisions.

How long does the station transmit before being sure that they are the only ones using the channel? Consider two stations in the worst case, maximally far apart. If the propogation delay on the channel is tau, and both stations sense an idle channel and start broadcasting, then collision occurs. If the second station starts at tau - epsilon, when the channel still appears to be idle, then the first station won't know about the collision until it propogates back down the channel, at time 2tau.

This length of time 2tau determines the minimum frame length, as well as the amount of time that should be used when delaying after collision.

Used in the IEEE 802.3 LAN standarded known as Ethernet.

Control token

Simple rule: can't speak without the token. To be fair you pass the token around and everyone gets a chance to speak while still avoiding collisions. Since you avoid collisions completely, you get determinstic behavior under load. Since there is control via the token, you can also do priorities.

The means of passing the token is independent of the topology of the channel. For example, you could pass in a circle (a ring) even if you are using a bus channel topology.

Used in two IEEE 802 standards for LANs.

Slotted ring

The ring is divided into slots which are constantly circulating. When you want to transmit you grab an empty slot. Every host monitors the full/empty bit, and the dest address. After reading a frame the response bits are set. The source removes the data by marking the empty bit after the slot has circulated around the ring - examines response bits for further action.

IEEE Project 802

802 specifies standars for LANs. Many companies participate, many needs are addressed. The various standards differ by topology, speed, data link MAC protocol, media.

Addressing

International uniqueness versus address size: 16 and 48 bit addresses was compromise

802.1

802.2 802.3 802.4 802.5 802.6 802.7 802.8 802.9

Ethernet IEEE 802.3

Original work by Xerox (2.94Mbps - 100 workstations, 1km). DEC and Intel joined and standard for 10 Mbps was made. Newest standards are for 100Mbps. Ethernet on UTP has become the "copper local loop" of the LAN world.

Bus topology, CSMA/CD protocol running 1, 10, or 100 Mbps.. All computers have unique 48 bit addresses (in NIC) managed by Xerox. For example 08:00:20:01:f4:ca. Theoretically there are 7x10^13 unique addresses. Space is carved up so you can tell which manufacturer an address has been assigned to. These addresses are datalink addresses and are needed because of the broadcast medium (in contrast to point-to-point).

At 10Mbps, max distance is 2.5km, 4 repeater to get this max distance. This is 51.2 micro seconds (worst case) between ends, with 0.1 us per bit (at 10Mbps) that's a cable that is 512 bits long.

Medium and components

Can be built with

Topology

Transmitting a frame

To send, the NIC senses the channel. Waits for it to be empty, sends frame. If collision happens it is detected, NIC generates noise burst (guarantees everyone knows that collision has taken place), then uses exponential binary backoff to delay.

Time slot is length of time that it takes a frame's first bit to propogate to all stations on cable. At 10Mbps, and 2.5km, and 2/3 speed of light = 25us or 50us for round trip. Add in safety margin + repeater time = 512 bits, or 51.2us.

Also limited by length of minimum frame size, since a sender could finish a short frame before collision is detected.

Random delay of number of slots (0,1), (0,1,2,3), ... After 10 collisions delay is maxed at 1023.  After 16 collisions the transmission stops.

The random delay allows for good performance under low loads, as well as solving high contention problems.

Acknowledgments can be handled like any other frame, competing for the channel, or the first slot after a frame may be reserved for an ACK frame.

Performance

Assume a constant retransmission probability in each slot (simpler). Assume heavy and constant load (k stations, always ready to transmit).

p = prob a station wants to transmit during a given slot
A = prob that a station actually transmits successfully during a given slot

A = k^p (1-p)^(k-1)

A is maximized when p = 1/k, and is equal to 1/e as k -> infinity

The probability that a contention interval has j slots in it (takes j slots to resolve contention) is A(1-A)^(j-1) so the average number of slots in a contention interval is

 sum j=0 to inf {j^ A (1-A)^(j-1) = 1/A

Since each slot has a duration of 2tau, where tau is the worst-case propogation time, the mean contention interval
 w = 2tau/A

Assuming optimal p, the mean number of contention slots is never more than e, so w = 2 tau e = 5.4tau

tau - cable length in seconds (2tau = slot time)
B = network bandwidth
L = cable length in meters
c = signal propogation speed

If a mean frame takes P seconds to transmit then the channel utilization is

U = P / (P + 2tau/A)

This is why the cable length has to be limited in Ethernet.  The longer the cable, the longer tau, and the lower the channel utilization.  Putting this into terms of cable length, frame length, speed of propogation, optimal contention case of e slots per frame gives

 U = 1 / (1 + 2BLe/cF)

Frame format

preamble SOF dest addr source addr length of data data payload checksum
7 bytes 1 2 or 6 2 or 6 2 46-1500 4
5.6us for clock synchronization 10101011 bit 47 - broadcast bit 46 - local/global in bytes
Need a minimum of 64 bytes so sender can't finish before first bit has reached end of cable (for collision detection). Pad field (46 bytes) is used to make frame a minimum of 64 bytes.

IEEE 802.5 Token Ring

Several nice things about rings

Media and components

Trunk cable is usually shielded twisted pair running 1, 4 or 16Mbps
Differential Manchester encoding, 3-4.5 volt amplitude
Wiring may be point-to-point in a ring, or use wiring concentrators in a "star fish" topology

Trunk control unit

Reliability against media failures is improved by wiring in a star-fish pattern

Transmitting a frame

Unidirectional flow of token (permission to transmit). Sender waits until it receives token, transmits information frame. All stations pass bits around, receiver keeps copy of data. Sender removes bits from network. Receiver sets response bits in tail of frame. Sender passes token on after done transmitting.

Monitor station keeps TR running smoothly  - new one elected if monitor dies.

The length of a ring in bits is important to how the TR operates.

At R Mbps, and 2/3 speed of light, a bit is generated every 1/R us and is 200/R meters long. For example, at 1Mbps, a bit is 200 meters long.

When all stations are idle, the idle token circulates among the stations.  This means that the token must fit on the ring.  Since stations which are powered off don't delay the bit (just pass it through) then the designer of the ring must make sure that the ring remains long enough, even when stations are turned off.  May need to introduce artificial delay. This is done by the active ring monitor.

Stations seize idle token by changing one bit in the second byte, converting the first two bytes into a start-of-frame sequence for their own data-holding token.

Priority

Multiple priorities are incorporated by making a station wait for a token of a priority less than or equal to the priority of the frame it wants to transmit.

A station can reserve a token by setting the reservation bits (but only if they aren't already set higher).  When the current token holder regenerates the token, it will generate a token of the priority being reserved.

Low priority stations may starve in this scheme under heavy traffic

The priority keeps going up (like a ratchet) so the station responsible for raising the priority also is responsible for lowering it.

Frame reception

Control frames are always copied by every host. Data frames are copied by the host being addressed. The A & C bits are set as appropriate before being repeated.

Token format

start delim access control frame control dest addr source addr data checksum end delim frame status
1 byte 1 1 2 or 6 2 or 6 0 - ? 4 1 1
uses illegal Manchester signal token bit, priority, reservation, etc 802 std 802 std max is determined only by token hold time uses illegal Manchester signal used for ack
AC = PPP T M RRR FC = FF ZZZZZZ

Performance

Lower efficiency than CSMA/CD for light loads, but more predictability. 100% utilization possible for heavy loads without sending frame delay through the ceiling.

No limit to data length, but each station is limited to holding the token to some period of time (default is 10ms).  Can send any number or length of packets in that time (with proper priority).

Average packet delay is crucial thing in TR, since throughput U can be 1

tau - ring latency
C = network capacity
L = cable length in meters
c = signal propogation speed
F= frame size
U = throughput
N = number of stations
a' = normalized ring latency
a'  = tau / F/R

T = F/C + tau/2 + tau(1  - Ua'/N) / (2(1  - Ua')  +  Ua'tau/2(1-Ua')

max U is 1 for a' < 1 and 1/a' for a' > 1

<plots from Miller Internetworking book>

Ring maintenance

The ring must be maintained Control frames Each token ring has a special station which is the ring monitor. Any station on a TR is capable of acting as ring monitor. If the ring monitor is lost, a new one is elected by stations  circulating a CLAIM TOKEN frame.  If your CLAIM TOKEN  frame navigates the ring before you see another CLAIM  TOKEN frame from an address greater than yours you  become the ring monitor.

Problems

Initialization of ring Dealing with broken rings Dealing with garbled frames Dealing with orphaned frames

IEEE 802.4 Token Bus

In Ethernet, no priorities and no upper bound on delay are not good for real-time problems - factory automation type apps needed more reliable behavior. A bus is a good topological match to an assembly line. Token bus puts a logical ring on top of a physical bus for the robustness and topology of Ethernet with worst-case characteristics of token ring.

More complex than Ethernet, totally incompatible (the bus topology is the only thing in common). Speeds of 1, 5, 10 Mbps.

Ring is formed by control protocol, depends on addresses of NICs. Order of stations in ring and on bus are independent of each other.

Complex: 10 timers/station, 30 internal variables, 200 pages in the spec

Medium and components

75 ohm broadband co-ax cable use (cable TV stuff), single and dual-cable systems supported. Three forms of broadband modulation are permitted. Broadband signalling allows for better noise immunity.

Transmitting a frame

Stations are ordered on the ring by their address (high to low). Stations transmit for a maximum token holding time (like TR), which may allow for multiple short frames to be sent. The token that is exchanged is a special control frame.

Four priority levels (0, 2, 4, 6 ) (low to high). Think of four separate substations in each station (one for each priority), where each substation maintains a queue of frames it wishes to transmit.

When the token enters a station it is passed  from high priority substation (6) to low priority (0) then on to the next station in the ring. Each substation gets to send data on the wire (if it has frames) until it's timer expires, at which time it passes. In effect the substations time multiplex the total station token hold time. By adjusting the timers you can guarantee a fixed portion of the capacity available to the high priority (6) traffic.

Priority 6 can be used for real-time data.

Frame format

preamble SOF control dest addr source addr data checksum EOF
1 1 1 2 or 6 2 or 6 0-8182 4 1
synchronization of clock uses signal violation to mark start of frame priority for data frames, else control info frames 802 std 802 std long max for efficiency, timers control hogging 802 std signal violations used

Token bus control

Control frames are exchanged to keep the bus properly running, define the ring of stations, add and remove stations, deal with token errors, etc.

Each station has a successor and a predecesor station; these define the ring.

SOLICIT SUCCESSOR 1- for leaving/entering ring

SET SUCCESSOR - for leaving the ring WHO FOLLOWS - entering ring, dealing with dead stations CLAIM TOKEN - for initialization

Problems

Multiple dead stations Token lost (dead station) Multiple tokens

Comparison of LAN technology

 
802 LAN Advantages Disadvantages
802.3, Ethernet
  • market dominance means cheap components, widespread availability
  • simple algorithm
  • stations join/leave easily
  • passive cable
  • baseband signalling
  • no delay at light load
  • analog circuitry for CD limits integration, costs money
  • minimum valid frame is 64 bytes, mostly padding
  • nondeterminstic delay behavior
  • no priorities
  • cable length and/or speed limits
802.5, Token Ring
  • point-to-point means all digital circuitry, better integration
  • variety of media possible (no need to tap)
  • wire centers make reliable
  • priorities possible
  • utilization for high load is good
  • known bound on frame delay
  • short minimum frame
  • more complex protocol
  • central monitor could be source of failure (sick is worse than dead)
  • non-zero delay at light loads
802.4, Token Bus
  • reliable componentry similar to cable television equipment
  • utilization for high load is good
  • known bound on frame delay
  • short minimum frames (20 bytes)
  • priorities, reservation of capacity support real-time apps
  • physical medium can be FDM for other channels
  • lots of analog circuitry, so more expensive, not prone to mass production like digital circuits
  • non-zero delay at light loads
  • complex protocol
  • small installed base (special purpose LAN)