Node: any device that runs a link-layer protocol. E.g. hosts, routers, switches, WiFi access points.
Link: communication channel that connects adjacent nodes along the communication path.
Over a given link, a transmitting node encapsulates the datagram in a link-layer frame and transmits the frame from one node to another.
Services Provided by the Link Layer
Possible services offered by a link-layer protocol include:
a) Framing
Almost all link-layer protocols encapsulate each network-layer datagram within a link-layer frame before transmission over the link;
b) Link access
A medium access control (MAC) protocol specifies the rules by which a frame is transmitted onto the link – when multiple nodes share a single broadcast link, MAC coordinates the frame transmission;
c) Reliable delivery
similar to transport-layer reliable delivery service, can be achieved with acknowledgments & retransmissions.
often used for links that are prone to high error rates e.g. wireless link.
Can be considered unnecessary overhead for low bit-error links e.g. wired link.
d) Error detection and correction
done by transmitting node including error-detection bits in the frame & receiving node performing error check.
Is more sophisticated & implemented in hardware compared to transport-layer error detection.
Where Is the Link Layer Implemented
A router’s link layer is implemented in the router’s line card;
A host’s link layered is implemented in Network adapter: a.k.a. network interface card (NIC).
link-layer controller: inside a network adapter, usually a single, special-purpose chip that implements many link-layer services in hardware.
While most of the link layer is implemented in hardware, part of it is implemented in software (running on the host’s CPU). E.g. assembling link-layer addressing information, activating the controller hardware.
Error-Detection and –Correction Techniques
Parity Checks
Parity checks with single parity bit: the total number of 1s in the d+1 bits (original information + parity bit) is even for even parity schemes, or odd for odd parity schemes.
In two-dimensional parity scheme, when a bit is flipped, receiver can use the column and row indices of the column and row with parity errors to identify the corrupted bit.
Forward error correction (EFC): The ability of the receiver to both detect and correct errors.
EFC techniques are important for real-time network apps or links with long propagation delays because by allowing for immediate correction at the receiver they avoid waiting for NAK & retransmitted packet.
Checksumming
Internet checksum: bytes of data are treated as 16-bit integers and summed, the 1s complement of this sum forms the checksum. --> receiver will take the 1s complement of the sum of received data (including checksum), see if the result is all 1 bits.
Compared to CRC, checksumming requires little packet overhead but weaker protection against errors.
Why is checksumming usually used at transport layer & CRC usually used at link layer?
1) transport-layer error detection is implemented in software, better to have a simple and fast error-detection scheme like checksumming;
2) link layer error detection is implemented in hardware, which can rapidly perform the more complex CRC operations.
CRC
Cyclic redundancy check (CRC) codes: a.k.a. polynomial codes.
-> Sender and receiver first agree on generator G (r+1 bits);
-> sender computes an R via
-> sender appends this additional R (r bits) to data D (d bits);
-> receiver divides (using modulo-2 arithmetic) the received d+r bits by G -- If remainder is nonzero, error has occurred. i.e.
Multiple Access Links and Protocols
There are 2 types of network links: point-to-point link and broadcast link.
point-to-point link: consists of a single sender at one end and a single receiver at the other end of the link. E.g. point-to-point protocol (PPP), high-level data link control (HDLC).
broadcast link: can have multiple sending and receiving nodes, all connected to the same single shared broadcast channel. E.g. Ethernet, wireless LANs.
Multiple access problem: how to coordinate the access of multiple sending and receiving nodes to a shared broadcast channel.
– when multiple nodes can transmit frames at the same time, transmitted frames will collide at receivers and make no sense thus waste broadcast channel.
Multiple access protocols: by which nodes regulate their transmission into the shared broadcast channel, avoiding collision.
Desirable characteristics of a multiple access protocol:
1) When only 1 node has data to send, the node has a throughput of R bps (R: the rate of the broadcast channel);
2) When M nodes have data to send, each has a throughput of R/M bps (average, not necessarily instantaneous);
3) decentralized i.e. there is no master node that represents a single point of failure for the network;
4) simple, inexpensive to implement.
Any multiple access protocol belongs to one of the 3 categories: channel partitioning protocols, random access protocols and taking-turns protocols.
Channel Partitioning Protocols
(suppose the channel supports N nodes and has a transmission rate of R bps)
1. Time-division multiplexing (TDM): divides time into time frames, further divides each time frame into N time slots, assign each time slot to one of the N nodes. Whenever a node has packet to send, it transmits the packet’s bit during its assigned time slot.
// “time frames” (as time unit) here should not be confused with “link-layer frame” (as data unit, referred as packet here).
Pros:
Avoids collisions & Fair -- each node gets a dedicated transmission rate of R/N bps.
Cons:
1) A node is limited to an average rate of R/N bps even when it is the only node with packets to send;
2) A node must always wait for its turn in the transmission sequence, even when it is the only node with packets to send.
2. Frequency-division multiplexing (FDM): divides the R bps channel into different frequencies, each with a bandwidth of R/N, and assign each frequency (i.e. smaller channel) to one of the N nodes.
Pros:
Avoid collision & Fair. (same as TDM)
Cons:
A node is limited a bandwidth of R/N even when it is the only node with packets to send.
e.g.
3. Code division multiple access (CDMA): Assigns a different code to each node, each node then uses its unique code to encode the data bits it sends.
Pros: if codes are chosen carefully, different nodes can transmit simultaneously yet have receivers correctly receive encoded data bits in spite of interfering transmissions by other nodes.
Random Access Protocols
In a random access protocol, a transmitting node always transmits at full rate of the channel (R bps).
When there is a collision, each node involved in the collision waits a random delay (chosen independently) before retransmission, repeatedly retransmits its frame until the frame gets through without a collision.
Random access protocols examples: ALOHA protocol, CSMA protocol, Ethernet.
ALOHA
Slotted ALOHA
-> divide time into slots;
-> requires slots to be synchronized in nodes.
-> (independently,) If a node detects a collision, it retransmits its frame in each subsequent slot with probability p until the frame is transmitted without a collision.
Pros:
- allows a node to transmit at full rate R when that node is the only active node; (*active node: node that has frames to send.)
- simple, highly decentralized;
Cons:
- efficiency is not high.
efficiency
* successful slot: A slot in which exactly one node transmits.
Slots that is not successful will be wasted.
- a: when there are multiple active nodes, some slots will have collision;
- b: when all active nodes refrain from transmitting due to retransmission probability.
Efficiency: the long-run fraction of successful slots when there are a large number of active nodes, each always having a large number of frames to send.
When there are N active nodes, the efficiency of slotted ALOHA is Np(1-p)N-1, with maximum efficiency 1/e=0.37.
ALOHA: Pure ALOHA does not require slotting or synchronization.
Node transmits its frame immediately when the network-layer datagram is passed down. When there is a collision, node will immediately retransmit the frame with probability p.
-- Fully decentralized.
When there are N active nodes, the efficiency of pure ALOHA is Np(1-p)2(N-1), with maximum efficiency 1/(2e), i.e. half of slotted ALOHA.
CSMA
The family of carrier sense multiple access (CSMA) and CSMA with collision detection (CSMA/CD) protocols embody 2 rules: carrier sensing and collision detection.
Carrier sensing: a node listens to the channel before transmitting. If a frame from another node is currently being transmitted into the channel, a node waits until it detects no transmissions for a short time and then begins transmission.
Collision detection: A node listens to the channel while it is transmitting. If it detects that another node is transmitting an interfering frame, it stops transmitting and waits a random amount of time (i.e. backoff time) before repeating the sense-and-transmit-when-idle cycle.
The end-to-end channel propagation delay of the broadcast channel plays a crucial role in determining CSMA’s performance -- the longer the delay, the larger the chance a carrier-sensing node not yet able to sense a transmission has already begun at another node.
Question: For CSMA/CD, what is a good interval of time from which to choose the random backoff time?
Answer: a short interval for a small number of colliding nodes, a long interval for a large number of colliding nodes.
Binary exponential backoff algorithm: solves the problem of picking good random backoff time interval.
-> When transmitting a frame that has already experienced n collisions, a node chooses value K at random from {0, 1, 2, …, 2n-1}.
-> K∝backoff time. the maximum value that n can take is capped at 10.
Thus the size of the sets from which K is chosen grows exponentially with the number of collision.
e.g. For Ethernet, a node waits K·512 bit times (K times the amount of time needed to send 512 bits into the Ethernet).
CMSA/CD Efficiency
dprop: the maximum time it takes signal energy to propagate between any two adapters;
dtrans: the time to transmit a maximum-size frame;
As dprop->0, colliding nodes can abort immediately without wasting the channel, thus Efficiency->1;
As dtrans->∞, a frame can hold on to the channel for a very long time, the channel will be doing productive work most of the time thus Efficiency->1.
Taking-Turns Protocols
Taking-turns protocols: multiple access protocols that achieve desired property “when M nodes are active, each active node has a throughput of nearly R/M bps”. e.g. polling protocol, token-passing protocol.
Polling protocol: e.g. 802.15 protocol; Bluetooth protocol.
-> designate one of the node as a master node.
-> The master node polls each node in a round-robin fashion:
--> master node sends a message to a node, saying that node can transmit up to some maximum number of frames;
--> after that node transmits some frames, master node go on to tell next node;
…;
pros: eliminate collision and empty slots.
cons: 1) introduces polling delay (time to notify a node); 2) if the master node fails, the entire channel fails.
Token-passing protocol: e.g. FDDI; IEEE 802.5 token ring protocol.
A token (*a small, special-purpose frame) is exchanged among nodes in some fixed order; e.g. (ode 1 always send the token to node 2, node 2 always send the token to node 3, …, node N always send to node 1).
-> When a node receives a token:
--> if it has frames to transmit, it sends up to a maximum number of frames, then forwards the token to the next node;
--> otherwise if it does not have frame to transmit, it immediately forwards to token to the next node;
Pros: decentralized, efficient;
Cons: one node’s failure can crash the entire channel.
DOCSIS
cable access network serves as an example of multiple access protocols in action (FDM, TDM, random access, centrally allocated time slots.)
Data-Over-Cable Service Interface Specifications (DOCSIS): specifies the cable data network architecture and its protocols.
*CMTS: cable modem termination system
- uses FDM to divide downstream (CMTS to modem) and upstream (modem to CMTS) network segments into multiple frequency channels;
- each upstream channel is divided into intervals of time (TDM-like), each containing a sequence of mini-slots (for transmitting a) minislot request frames and b)data frames);
- cable modems (that have data to send) send mini-slot-request frames to CMTS during a special set of mini-slots, in random access manner;
- CMTS sends a control message (MAP message) on downstream channel to specify which cable modem (that has data to send) can transmit during which mini-slot;
- cable modems infer its mini-slot-request frames experienced a collision if it does not receive a response in the next downstream control message, it uses binary exponential backoff to defer retransmission of its mini-slot request frame;
- When there is little traffic on upstream channel, cable modem may transmit data frames during slots nominally assigned for mini-slot-request frames (thus avoid waiting for mini-slot assignment).
Switched Local Area Networks
Switches operating at link layer don’t recognize network-layer IP addresses, (and don’t use routing algorithms like RIP or OSPF,) they use link-layer addresses instead.
Link-Layer Addressing
Switches operating at link layer don’t recognize network-layer IP addresses, (don’t use routing algorithms like RIP or OSPF,) instead they use link-layer addresses to forward layer frames.
MAC address
A host/router with multiple network interfaces (adapters) have multiple link-layer addresses associated with it. (same does multiple IP addresses);
Link-layer switches do not have link-layer addresses associated with their interfaces. – because a switch’s job is just to carry datagrams between hosts and routers, doesn’t have to explicitly address the frame to intervening switch.
MAC address: a.k.a. LAN address, physical address. link-layer address. For most LAN, MAC address is 6 bytes long (248 possibilities), with each byte expressed as a pair of hexadecimal numbers.
-> When an adapter wants to send a frame to some destination adapter, sending adapter inserts destination adapter’s MAC address into the frame and then sends the frame into LAN.
-> a switch occasionally broadcast an incoming frame onto all of its interfaces;
-> When an adapter receives a frame, it checks whether the destination MAC address in the frame matches its own MAC address.
--> a. If there is a match, the adapter extracts the enclosed datagram and passes it up the protocol stack;
--> b. If there isn’t a match, the adapter discards the frame.
-> If sending adapter does want all other adapters to receive its frame, it inserts a special MAC broadcast address into the frame’s destination address field. e.g. for LAN, broadcast address is a string of 48 consecutive 1s (FF-FF-FF-FF-FF-FF).
No two adapters have the same address.
=> IEEE manages MAC address space. When a company wants to manufacture adapters, IEEE allocates a chunk of address space (consisting of 224 addresses) with first 24 bits fixed. The company itself creates unique combination of the rest 24 bits.
MAC address has a flat structure, IP address has a hierarchical structure.
=> An adapter’s MAC address doesn’t change no matter where it goes. A host/router ’s IP address changes when it moves to another network.
Why hosts and routers interfaces have MAC address in addition to network-layer address?
=> 1) LANs are designed for arbitrary network-layer protocols, not just for IP/Internet. If adapter were assigned IP address only, they would not easily be able to support other network-layer protocols (e.g. IPX, DECnet).
2) if adapters were to use network-layer address instead of MAC address, network-layer address would have to be stored in adapter RAM and reconfigured every time the adapter is moved. (if not using any address in adapters and have adapters pass received data up the protocol stack for network layer to check network-layer address, the host would be interrupted by every frame sent on the LAN including frames not destined for it.)
ARP
Address Resolution Protocol (ARP): for hosts and router interfaces on the same subnet, resolves an IP address to a MAC address.
ARP table: Each host and router has an ARP table in its memory, which contains mappings IP addresses to MAC addresses and a time-to-live (TTL) value (indicating when each mapping will be deleted from the table).
ARP table gets built automatically, it doesn’t have to be configured by a system administrator.
If a host becomes disconnected from the subnet, its entry is eventually deleted from other ARP tables in the subnet.
e.g.