Link framing, errors, medium access and bridging
Goals and assumptions
Turn a bit stream into frames, calculate simple error-detection codes, reason about shared-medium access and trace a learning bridge. Prerequisites: XOR, binary polynomials and transmission/propagation delay from lesson 02. This lesson uses small mathematical codes for hand calculation; their bit order and initial state are explicitly simplified. Do not substitute these toy CRCs for Ethernet's actual FCS implementation. Unless stated otherwise, a bridge has one VLAN, active forwarding ports, no security filtering and no stale entries.
1. Finding frame boundaries
A receiver needs both a boundary and a way to distinguish control delimiters from payload. A length field supplies a count, but a damaged count can misalign interpretation. Delimiter schemes reserve a flag and escape payload occurrences. In byte stuffing, a special escape byte precedes or transforms reserved payload bytes according to the specified protocol. The receiver reverses that rule; stuffing is transparency, not compression or error correction.
For an HDLC-style bit-oriented example, the flag is 01111110. Between flags the sender inserts a zero after every run of five consecutive ones; the receiver removes that inserted zero. Flags themselves are not stuffed. Worked example: payload 01111110 becomes 011111010 between the flags. Read it as 0, five ones, inserted 0, remaining 1, final 0. Ten consecutive payload ones become 111110111110: two insertions. Count runs continuously across byte boundaries. Stuffing changes transmitted length and therefore transmission time.
2. Parity and checksums
A single even-parity bit makes the total number of ones even. For data 1011001 there are four ones, so append parity 0. Every odd number of bit flips changes parity and is detected; an even number can leave parity unchanged. Detection does not identify the corrupt bit or repair it.
The Internet checksum uses one's-complement addition of 16-bit words, followed by bitwise complement. Carry beyond 16 bits wraps back into the low end, potentially repeatedly. Example: 0xF234+0x2345=0x11579; fold the carry to obtain 0x157A; complement gives 0xEA85. Adding the data words and checksum with carry folding yields 0xFFFF. A passing checksum is evidence consistent with no detected error, not a proof that no corruption occurred. Some compensating changes cancel. An additive checksum is different from XOR polynomial division and neither mechanism authenticates a sender.
3. CRC calculation and guarantees
Represent bits as coefficients over GF(2). Addition and subtraction are XOR, without carries. Let the degree-r generator G have leading and constant coefficients 1. Append r zeros to data D, divide D×x^r by G and take the r-bit remainder R. Transmit T=D×x^r XOR R. T divides exactly by G in this simplified zero-initialized convention. The receiver divides the received bits by the same G; a nonzero remainder detects an error.
Worked example: D=1101 and G=1011 (degree 3). Start with 1101000. XOR the aligned generator 1011000 to obtain 0110000; then XOR 0101100 to get 0011100; XOR 0010110 to get 0001010; XOR 0001011 to obtain remainder 001. The transmitted codeword is 1101001. It is divisible by 1011. Do not append four zeros just because the generator contains four bits.
If E is the error polynomial, the corruption escapes detection exactly when G divides E. A degree-r generator with constant term 1 detects every burst of length at most r. A burst's length runs from first changed bit to last changed bit, including unchanged bits inside. The generator detects all odd-weight error patterns when it contains factor x+1. For 1011, G(1)=1 modulo 2, so that odd-weight guarantee does not apply. Indeed E=1011 itself is an undetected three-bit error pattern. Never claim that every CRC detects every possible error or that a zero remainder proves correct data. Error detection must be paired with retransmission or correction if recovery is required.
4. Medium access: who may transmit?
A shared medium needs a rule for competing stations. Channel partitioning divides time/frequency; polling and token passing coordinate turns; random access lets contenders attempt transmissions and recover from collisions. Reservations can waste unused turns, while contention wastes work during collisions. Their relative performance depends on traffic and overhead.
Under the ideal Poisson-attempt, equal-frame-length model, pure ALOHA has vulnerable interval 2T and normalized throughput S=G exp(-2G). Its maximum is 1/(2e) at G=1/2. Slotted ALOHA synchronizes starts, has vulnerable interval T and S=G exp(-G), reaching 1/e at G=1. G counts all transmission attempts per frame time, including retries; S counts successful frames per frame time. These are model results, not universal Ethernet efficiency formulas. Example: slotted ALOHA at G=0.5 gives S≈0.3033, while pure ALOHA at the same G gives S≈0.1839.
CSMA listens before transmitting, but a distant transmission may not have propagated yet, so sensing cannot eliminate collisions. In classic half-duplex Ethernet, CSMA/CD detects collisions while transmitting, aborts the attempt and retries after binary exponential backoff. After collision number n, the classic backoff chooses an integer uniformly from 0 through 2^min(n,10)−1 slot times. For collision number 3, the possible integers are 0…7, and the mean is 3.5 slots. This chooses a delay, not a guaranteed collision-free reservation.
For the idealized two-endpoint collision-detection bound, a sender must still be transmitting when a worst-case collision returns: L/R≥2τ, or L≥2Rτ. With R=10 Mb/s and one-way propagation τ=20 microseconds, L≥400 bits=50 bytes. This is a propagation-only mathematical bound, not a replacement for Ethernet's standardized minimum frame size; real rules include other timing allowances. In ordinary switched full-duplex Ethernet there is no shared collision domain on a point-to-point link and CSMA/CD is not used. Wireless collision avoidance uses other coordination, such as random backoff and acknowledgments; it does not promise that collisions never occur.
5. Ethernet learning bridges
A transparent bridge learns the source MAC address and ingress port of accepted frames. It looks up the destination MAC to choose an action. A known unicast on another port is forwarded there; a known destination on the ingress port is filtered; an unknown unicast is flooded on eligible ports other than ingress. Broadcast is also flooded within the broadcast domain. Learning the source and looking up the destination are different operations. Entries age out so that changes can eventually be relearned.
Trace a three-port bridge starting with an empty table. Host A is on port 1, B on port 2 and C on port 3. Frame A→B arriving on port 1 teaches A→1; B is unknown, so send copies on 2 and 3. B→A on port 2 teaches B→2; A is now known, so send only on 1. A→B subsequently uses only port 2. If another host D shares port 1 through a hub, a frame from A to an already learned D→1 is filtered rather than reflected onto that same segment.
Bridges separate collision domains but, absent VLAN/routing boundaries, do not separate the broadcast domain. Redundant physical links can form loops: flooded frames may circulate and MAC learning can oscillate. Ethernet frames have no IP-like hop limit to solve this. Spanning-tree mechanisms select a loop-free active topology by blocking some redundant paths; they do not require removing every redundant cable. Forwarding and learning states matter if a question specifies them.
Solve-and-check checklist
Identify the framing rule before counting overhead. For CRC, use generator degree and XOR, then verify the final codeword remainder. For access formulas, state traffic and duplex assumptions. For bridge traces, update the source entry first and distinguish forwarding, flooding and filtering. Keep collision domains distinct from broadcast domains.
Original practice: six single-correct MCQs
These original teaching questions are not previous-year questions. Choose exactly one answer.
P01. Using insertion of a zero after every five consecutive payload ones, how many zeros are stuffed into ten consecutive ones?
A. 0 B. 1 C. 2 D. 3
Answer: C
A: The transparency rule applies to both runs.
B: There are two runs of five, not one.
C: 111110111110 contains two inserted zeros.
D: Only two groups of five occur.
P02. With data 1101, generator 1011 and the simplified zero-initialized CRC rule, what codeword is sent?
A. 1101000 B. 1101001 C. 1101101 D. 1101011
Answer: B
A: This appends zeros without replacing them with the remainder.
B: The three-bit remainder is 001, so append 001 to 1101.
C: 101 is not the computed remainder.
D: Appending the generator tail is not polynomial division.
P03. Which error pattern is always detected by a single even-parity check?
A. Any two bit flips B. Any nonzero number of flips C. Any four bit flips D. Any odd number of bit flips
Answer: D
A: Two flips preserve parity.
B: Even-weight changes can escape.
C: Four flips preserve parity.
D: An odd number of flips changes the parity.
P04. In the ideal collision-detection model, R=20 Mb/s and one-way propagation is 10 microseconds. Minimum transmission length from L/R≥2τ?
A. 200 bits B. 400 bytes C. 400 bits D. 20 bits
Answer: C
A: This uses one-way time instead of round trip.
B: The calculation yields bits, not bytes.
C: 2×20×10^6×10×10^-6=400 bits.
D: This omits the stated rate and round-trip factor.
P05. An initially empty three-port bridge receives A→B on port 1. With all ports forwarding in one VLAN, what does it do?
A. Learn A→1 and flood on ports 2 and 3 B. Learn B→1 and forward only on port 2 C. Learn A→1 and send back on port 1 only D. Drop because B is unknown
Answer: A
A: It learns the source, then floods the unknown destination except on ingress.
B: Learning uses source A, and B has no known port yet.
C: Flooding excludes the ingress port.
D: Unknown unicast is flooded in the stated ordinary bridge model.
P06. Under the ideal slotted-ALOHA model S=G exp(-G), what is the maximum normalized throughput?
A. 1/(2e), at G=1/2 B. 1/e, at G=1 C. 1, at G=1 D. It grows without limit with G
Answer: B
A: That is the pure-ALOHA maximum.
B: Derivative exp(-G)(1-G) vanishes at G=1, the maximum.
C: Collisions leave only exp(-1) successful frames per frame time.
D: At high attempt load collisions reduce throughput.
Sources and scope
Aligned to the 2026 course. This lesson covers the stated slice, not the entire Computer Networks syllabus. All numerical examples and questions are original. No claim of 2027 completeness.
Sign in to keep your progress. Sign in