Mac layer Survey The Medium Access Sublayer mac: Medium Access Control

MAC Layer Survey

The Medium Access Sublayer

• MAC: Medium Access Control

• As opposed to “high access control” or “low access control”?
• NO!
• It means: controlling access to the medium.
• provides arbitration mechanism for shared medium

• What are arbitration mechanisms in this classroom?

• Raising your hand
• Verbal cues, e.g. “go ahead, Fred”.
• Eye contact

• Background: review of:

• Broadcast vs. Point-to-Point media
• Topologies: Bus, Ring

• Then: Static vs. Dynamic channel allocation

• Finally: ALOHA, and CSMA/CD (Ethernet)

Broadcast Networks vs. Point to Point networks

• typically use a “shared cable”

• typically are LAN technologies

• examples:

• Ethernet
• Cable Modems

The Channel Allocation Problem (continued)

• Statistical multiplexing is preferred to FDM and TDM.

• Arrange all the packets in a giant central queue, and share the bandwidth on a first come first served basis.
• Don’t pre-allocate bandwidth for users that may just waste it.
• For details, need to review some basic queuing theory, and know what an exponential and poisson distribution are.

Dynamic channel allocation

• Five characteristics of channel allocation models:

• 1) Station model: stations independent
• 2) Single channel assumption
• 3) Collisions
• 4) Continuous (free-for-all, pure Aloha) vs Discrete Time (time is slotted)
• 5) Carrier sense (polite, listen first) vs. no Carrier Sense (just blurt out)

Aloha

• 1970s Norman Abramson et. al, University of Hawaii

• Send packets on shared channel; if collisions occur, wait random amount of time, and try again.

• Original purpose:

• host to terminal communication (very bursty)
• ground-based radio channel; want to share it.

• However, basic ideas have application to any environment where there is a shared medium, and uncoordinated users

• a bus-topology LAN
• the up-link part of a Satellite channel

Two variations of Aloha

Efficiency of pure aloha...

• When does frame X suffer no collisions? When there are no frames that overlap with frame X… i.e., only one frame starts in an interval of 2t. (Frames that start after t0 + 2t are ok).

Channel allocation methods...

Carrier Sense Multiple Access

• Listen the channel before you transmit!

• If the channel is busy don’t transmit; if it’s idle, transmit.

• Most basic form: 1-persistent CSMA

• If busy, listen persistently until channel is idle, then transmit immediately with probability 1.

• Problem with 1-persistent CSMA:

• Q: If any two stations B,C become “ready” during A’s transmission, what happens
• A: guaranteed collision!

Carrier Sense Multiple Access

Problem with 1-persistent CSMA

Non-persistent and p-persistent CSMA

Performance of CSMA protocols vs. Aloha

Collision detection

• All of the previous protocol (ALOHA, CSMA) assume collision = a total loss.

• CSMA with Collision Detection (CSMA/CD) makes a different assumption:

• we can detect a collision,and abort immediately, so we don’t waste an entire slot.
• So, use 1-persistent CSMA, but if there is a collision, immediately stop, and wait a random period of time before trying again.

Detecting collisions on a Bus network...

• If  is the maximum propagation time on a bus network, then it can take up to twice that long (2) for a collision to be detected.

• This turns out to be a an important design parameter, as we will see.

If you need 2 to detect collisions...

• … then you need to make sure that a frame isn’t shorter then 2

• Otherwise, a station might send an entire frame, and not realize that it had collided with something!

• Thus, the minimum frame size in classic 10Mbps Ethernet = 64bytes.

• What about 100Mbps Ethernet…?

• If minimum frame size is the same, and bit rate is 10 times higher, and you still need 2 to detect collisions, then what must have changed?

• the maximum cable length has to be 10 times shorter.

Ethernet and 802.3

• Ethernet came first, invented at Xerox PARC (Palo Alto Research Center). (Bob Metcalfe was key figure; later went on to be a founder of 3COM.)

• Xerox, Digital, and Intel were the “partners” in original commercial Ethernet spec.

• Later, IEEE make 802.3 a standard

• lots of variations at various bit rates using various media,
• changed packet type field to a length field. (packet type values are all illegal lengths, so its easy to distinguish)

• For most purposes of our discussion, we’ll consider them one and the same, although purists would insist that they are different standards.

802.3 Collision Detection is analog process

• Station must read voltage on wire to see if it is the same as what the station is sending out.

• Collision of two “0 volt signals” would be hard to detect!

• This is a motivation for Manchester Encoding… Voltage is either 0.85 or -0.85, so if you add two signals together, with very high probability you will get an illegal voltage within a few bits.

Ethernet

• “dominant” LAN technology:

• cheap $20 for 100Mbs!

• first widely used LAN technology

• Simpler, cheaper than token LANs and ATM

• Kept up with speed race: 10, 100, 1000 Mbps

Ethernet Frame Structure

• Sending adapter encapsulates IP datagram (or other network layer protocol packet) in Ethernet frame

• Preamble:

• 7 bytes with pattern 10101010 followed by one byte with pattern 10101011

• used to synchronize receiver, sender clock rates

Ethernet Frame Structure (more)

• Addresses: 6 bytes, frame is received by all adapters on a LAN and dropped if address does not match

• Type: indicates the higher layer protocol, mostly IP but others may be supported such as Novell IPX and AppleTalk)

• CRC: checked at receiver, if error is detected, the frame is simply dropped

Ethernet: uses CSMA/CD

• A: sense channel, if idle

• then {
• transmit and monitor the channel;
• If detect another transmission
• then {
• abort and send jam signal;
• update # collisions;
• delay as required by exponential backoff algorithm;
• goto A
• }
• else {done with the frame; set collisions to zero}
• }
• else {wait until ongoing transmission is over and goto A}

Ethernet’s CSMA/CD (more)

• Jam Signal: make sure all other transmitters are aware of collision; 48 bits;

• Exponential Backoff:

• Goal: adapt retransmission attemtps to estimated current load

• heavy load: random wait will be longer

• first collision: choose K from {0,1}; delay is K x 512 bit transmission times

• after second collision: choose K from {0,1,2,3}…

• after ten or more collisions, choose K from {0,1,2,3,4,…,1023}

Ethernet Technologies: 10Base2

• 10: 10Mbps; 2: under 200 meters max cable length

• thin coaxial cable in a bus topology

• repeaters used to connect up to multiple segments

• repeater repeats bits it hears on one interface to its other interfaces: physical layer device only!

10BaseT and 100BaseT

• 10/100 Mbps rate; latter called “fast ethernet”

• T stands for Twisted Pair

• Hub to which nodes are connected by twisted pair, thus “star topology”

LAN Addresses and ARP

• 32-bit IP address:

• network-layer address

• used to get datagram to destination network (recall IP network definition)

• LAN (or MAC or physical) address:

• used to get datagram from one interface to another physically-connected interface (same network)

• 48 bit MAC address (for most LANs) burned in the adapter ROM

LAN Addresses and ARP

LAN Address (more)

• MAC address allocation administered by IEEE

• manufacturer buys portion of MAC address space (to assure uniqueness)

• Analogy:

• (a) MAC address: like Social Security Number

• (b) IP address: like postal address

• MAC flat address => portability

• can move LAN card from one LAN to another

• IP hierarchical address NOT portable

• depends on network to which one attaches

Recall earlier routing discussion

ARP: Address Resolution Protocol

• Each IP node (Host, Router) on LAN has ARP module, table

• ARP Table: IP/MAC address mappings for some LAN nodes

• < IP address; MAC address; TTL>

• < ………………………….. >

• TTL (Time To Live): time after which address mapping will be forgotten (typically 20 min)

ARP protocol

• A knows B's IP address, wants to learn physical address of B

• A broadcasts ARP query pkt, containing B's IP address

• all machines on LAN receive ARP query

• B receives ARP packet, replies to A with its (B's) physical layer address

• A caches (saves) IP-to-physical address pairs until information becomes old (times out)

• soft state: information that times out (goes away) unless refreshed

Routing to another LAN

• walkthrough: routing from A to B via R

• In routing table at source Host, find router 111.111.111.110

• In ARP table at source, find MAC address E6-E9-00-17-BB-4B, etc

A creates IP packet with source A, destination B

• A creates IP packet with source A, destination B

• A uses ARP to get R’s physical layer address for 111.111.111.110

• A creates Ethernet frame with R's physical address as dest, Ethernet frame contains A-to-B IP datagram

• A’s data link layer sends Ethernet frame

• R’s data link layer receives Ethernet frame

• R removes IP datagram from Ethernet frame, sees its destined to B

• R uses ARP to get B’s physical layer address

• R creates frame containing A-to-B IP datagram sends to B

Bridges, Internetworking

• Before talking about bridges in the context of the MAC sub-layer, lets briefly skip ahead, and cover the differences among:

Repeaters

• Copy individual bits between cable segments, and that is all.

• Operate at physical layer only.

Bridges

• Operate at Data link layer, and may connect two similar LANs, or two dissimilar, but at least partially compatible LANs.

• For dissimilar LANs (e.g. 802.x to 802.y, where xy) differences in frame size, priority schemes, etc. create headaches and incompatibilities.

Routers

• Operate at Network layer. Usually connect two networks using same network layer.

• Tanenbaum discusses “multiprotocol routers”;

• Often these connect two networks that have multiple network protocols, but don’t do conversions from one to another. (This is how I have seen them used.)
• Tanenbaum implies: sometimes they convert from one network layer to another.

Gateways

• Operate at Transport and/or Application Layer

• Examples:

• a gateway between Internet (TCP/IP) SMTP-based email and a proprietary email system like IBM’s “PROFS” (based on SNA) or Digital’s (DECs) “All-in-one” or VAX/VMS Mail (based on DECnet).
• a gateway between SNA’s 3270 terminals and TCP/IP Telnet style terminal sessions.
• Proxy server

Summary: Repeaters, Bridges, Routers, Gateways

• The distinction lies mainly in the “highest” layer at which each operates.

• Although this terminology is fairly standard, and the preferred common usage, the term “gateway” is sometimes used in the Internet community as a synonym for “router”. (for example, in the name of the “Exterior Gateway Protocol”.)

• Now let’s turn our attention back to a possibly confusing questions about bridges…

• do bridges do routing?

• Ethernet Bridges for collisions/noise/traffic each segment looks like a separate Ethernet

• BUT, for forwarding frames to destination Ethernet addresses the entire network seems to be a single large Ethernet

• The bridges handle routing

Bridges can connect more than one LAN

• We can build an extended LAN by connecting up smaller LANs through bridges

• Goal:

• (LAN3, LAN4, LAN5, LAN6) separate for collisions, local traffic
• (LAN3, LAN4, LAN5, LAN6) all one LAN for sending, addressing
• Bridges functions as data-link layer routers

• Routing tables are self-configuring. Four (equiv.) names for this:

• adaptive bridges – backwards-learning bridges
• learning bridges – transparent bridges

How adaptive bridges learn

• The bridge B has this goal: only forward frames when necessary!

• don’t forward local traffic between hosts on seg. 1 to seg. 2, and vice-versa
• e.g., traffic between u and w should stay local to seg. 1

• How is this achieved?

• At first forwarding every incoming frame onto every destination lan (flooding)
• As the bridge “learns” where hosts are, it only forwards the frame if necessary.

• How does it learn where hosts “live”? By “backward learning”

• We figure out the destination seg. for packets going to y, by looking at the source seg. for packets coming from y.

Startup/Steady State

• The startup behavior is to forward every frame everywhere (flooding)

• The steady state is to forward frames ONLY where they belong.

Do Bridges Do Routing? Where the confusion can arise...

• In discussing bridge design, we may talk about “routing tables” in the bridges and how “routing” is done.

• e.g. sending a frame DA vs. DC vs. DH.

• We’re talking about routings packets at the Data Link Layer through an interconnection of LAN segments that make up an “extended LAN”.

• This is similar in function (in some ways) to routing at the network layer, but it is NOT the network layer; the network layer sits “above” all this.

Planning A Bridged Network

• Bridges allow parallelism, and isolate traffic.

• Simultaneously: (AB) (ED) (FH) without any collision.

• Exploit “locality of reference”; idea is that most accesses are to

• local file servers
• local printers

• So put users of a server/printer on the same bridged segment

• keep local traffic local

Bridging Between Buildings: Goal is to keep local traffic local!

Bridging Across Longer Distances: Keep local traffic off the long-distance link

A Cycle Of Bridges

• In transparent bridging: the idea is, you just plug and play

• the bridges configure themselves!
• but what if you put in a cycle?
• What will happen?

Problems with a cycle of bridges

• The fear:

• more than one bridge may forward a frame, creating wasteful duplicates
• loops may cause frames to be forwarded forever

• Example:

• Suppose that frame F is going to an “unknown” destination,
• Both bridge B1 and bridge B2 use flooding (send it everywhere)
• Now what happens when B1 sees frame F2, and B2 sees frame F1?
• They will forward it back to LAN1, creating frames F3 and F4…
• etc. etc. etc.

Easy solution for LANs: Create a Spanning Tree

• Lowest serial number bridge becomes the root of the tree (leader election problem). Perlman’s algorithm used to do computation.

• Note that this does not scale up to WANs; it would be wasteful to not use the capacity of the “non-tree” links.

• An example of how LAN routing (data link layer) differs from WAN routing (network layer)

Backward Learning in Transparent Bridges

• Transparency idea: “plug and play”; no configuration needed!

• Review of the algorithm:

• Build a hash table where key is Ethernet address, data is LAN id. (initially empty)
• When packet arrives, put source address in table along with LAN it came in on. (this is the backward learning part; we learn destinations, by looking at sources!)
• Look up destination address in table.
• if (found) if (source LAN==dest LAN) do nothing; frame is already where it needs to be else send out on destination LAN.
• else {we don’t know where it is, so send out on every interface (flooding.) }
• Periodically purge entries from table (“soft-state”) in case hosts move or LAN configuration changes.

Source Routing Bridges (used in IBM Token Ring, 802.5)

• Source chooses the route the host.

• Route chosen by using “discovery packets”

• broadcast packet from x saying “what is route to y”?
• bridges record route taken; use info to get reply back to x.
• x receives a reply for every possible route to y, and picks the best one.

• Advantage: can use the bandwidth more effectively. Transparent bridges only use the spanning tree.

• Disadvantages:

• Not transparent.(not “plug and play”). Administrator must configure bridge addresses to be unique among all bridges attached to a particular LAN
• Frame explosion problem; # discovery frames can grow exponentially. (only linear growth with flooding in spanning tree bridges.)