5: Link Layer and LAN Flashcards
what is the role of the link layer? what services does it provide?
data-link layer has responsibility of
transferring datagram from one node
to physically adjacent node over a link
- framing
- reliable delivery
- flow control
- error detection
- error correction
what is a cyclic redundancy check?
treat the data as a binary number, perform a division operation. if there’s a non-zero remainder, an error is detected
what is the motivation behind a multiple access protocol?
we have a single shared broadcast channel, want to avoid simultaneous transmissions causing interference and collision
so we need a distributed algorithm that determines how nodes share the channel i.e when they can transmit
what classes of MAC protocl are there? (3)
channel partitioning, dividing the channel into smaller peices (time slots, frequencies). a node gets a piece for exclusive use
random acess
channel isn’t divided, allows collisions. we “recover” from them instead
“taking turns”
nodes take turns, but nodes with more to send
what is TDMA?
time division multiple access - a channel partitioning MAC protocol
access to channel in “rounds”
• each station gets fixed length slot (length = packet
transmission time) in each round
• unused slots go idle
• example: 6-station LAN, 1,3,4 have packets to send, slots
2,5,6 idle
what is FDMA?
a channel partitioning MAC protocol
FDMA: frequency division multiple access
• channel spectrum divided into frequency bands
• each station assigned fixed frequency band
• unused transmission time in frequency bands go idle
• example: 6-station LAN, 1,3,4 have packet to send,
frequency bands 2,5,6 idle
what is a random access MAC protcol? an example pls
when node has packet to send • transmit at full channel data rate R. • no a priori coordination among nodes • two or more transmitting nodes ➜ “collision” , • random access MAC protocol specifies: • how to detect collisions • how to recover from collisions (e.g., via delayed retransmissions) • examples of random access MAC protocols: • slotted ALOHA • ALOHA • CSMA, CSMA/CD, CSMA/CA
Pros: • single active node can continuously transmit at full rate of channel • highly decentralised: only slots in nodes need to be in sync • simple Cons: • collisions, wasting slots • idle slots • nodes may be able to detect collision in less than time to transmit packet • clock synchronisation
CSMA: listen before transmit:
if channel sensed idle: transmit entire frame
• if channel sensed busy, defer transmission
• human analogy: don’t interrupt others
describe the CSMA/CD algorithm
1. NIC receives datagram
from network layer,
creates frame
2. If NIC senses channel
idle, starts frame
transmission. If NIC
senses channel busy,
waits until channel idle,
then transmits.
3. If NIC transmits entire
frame without detecting
another transmission,
NIC is done with frame !
4. If NIC detects another
transmission while
transmitting, aborts and
sends jam signal
5. After aborting, NIC
enters binary
(exponential) backoff:
• after mth collision, NIC chooses
K at random from {0,1,2, …, 2m1}. NIC waits K·512 bit times,
returns to Step 2
• longer backoff interval with
more collisionshow do channel partitioning and random access MAC protocols compare? where does taking turns fit in this
channel partitioning MAC protocols:
share channel efficiently and fairly at high load
inefficient at low load: delay in channel access, 1/N bandwidth
allocated even if only 1 active node!
random access MAC protocols
efficient at low load: single node can fully utilise channel
high load: collision overhead
“taking turns” protocols
look for best of both worlds!
describe 2 optionsfor taking turns MAC protocols and their pitfalls
polling: • master node “invites” slave nodes to transmit in turn • typically used with “dumb” slave devices • concerns: • polling overhead • latency • single point of failure (master)
token passing: control token passed from one node to next sequentially. token message concerns: token overhead latency single point of failure (token)
what is ARP? how does it work within and out of a LAN?
address resolution protocol
how to determine
interface’s MAC address,
knowing its IP address?
ARP table: each IP node (host, router) on LAN has 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)
A wants to send datagram to B • B’s MAC address not in A’s ARP table. • A broadcasts ARP query packet, containing B's IP address • destination MAC address = FF-FF-FF-FF-FF-FF • all nodes on LAN receive ARP query • B receives ARP packet, replies to A with its (B's) MAC address • frame sent to A’s MAC address (unicast)
A caches (saves) IP-toMAC address pair in its ARP table until information becomes old (times out) • soft state: information that times out (goes away) unless refreshed • ARP is “plug-and-play” \: • nodes create their ARP tables without intervention from net administrator
to another LAN:
A creates IP datagram with IP source A, destination B
A creates link-layer frame with R’s MAC address as destination
address, frame contains A-to-B IP datagram
frame sent from A to R
R forwards datagram with IP source A, destination B
R creates link-layer frame with B’s MAC address as destination
address, frame contains A-to-B IP datagram
what was the ethernet topology of old and how has it changed? why?
• bus: popular through mid 90s
• all nodes in same collision domain (can collide with each other)
• star: prevails today
• active switch in center
• each “spoke” runs a (separate) Ethernet protocol (nodes do not collide
with each other)
• each link is its own collision domain
what is the purpose of the preamble in the ethernet frame?
• 7 bytes with pattern 10101010 followed by one byte with
pattern 10101011
• used to synchronise receiver, sender clock rates
is ethernet reliable? why?
is ethernet connectionless?
what MAC protocol does ethernet use?
connectionless: no handshaking between sending and receiving
NICs
• unreliable: receiving NIC doesn’t send acks or nacks to sending
NIC
• data in dropped frames recovered only if initial sender uses
higher layer rdt (e.g., TCP), otherwise dropped data lost
• Ethernet’s MAC protocol: unslotted CSMA/CD with binary backoff
what does transparency mean in terms of an ethernet switch?
• hosts are unaware of presence of switches
