Chapter 3: Computer Networks

Data Link Layer

Data Link Layer

The second layer in the communication model that deals with reliable and efficient communication of frames between two adjacent machines.

Frames

Whole units of information that are communicated between machines in the data link layer.

Communication Channel

The connection between two machines that acts conceptually like a wire, delivering bits in the same order they are sent.

Errors

Occasional mistakes or disruptions in communication channels that can affect the efficiency of data transfer.

Protocols

Sets of rules and algorithms used for communication that take into consideration errors, data rate, and propagation delay.

Reliable Communication

Ensuring that frames are delivered correctly and in the right order.

Efficient Communication

Maximizing the speed and effectiveness of data transfer.

Services Provided to the Network Layer

Functions of the data link layer including providing a well-defined service interface, framing sequences of bytes, detecting and correcting transmission errors, and regulating data flow.

Byte Count

A framing method that uses a field in the header to specify the number of bytes in a frame.

Flag Bytes with Byte Stuffing

A framing method that uses special bytes as delimiters to indicate the start and end of frames.

Flag Bits with Bit Stuffing

A framing method that uses special bits as delimiters to indicate the start and end of frames.

Physical Layer Coding Violations

A framing method that uses violations of physical layer coding rules to indicate the start and end of frames.

Byte stuffing

A technique used in data link layer design to solve the problem of flag bytes occurring in the data by inserting a special escape byte (ESC) before each accidental flag byte.

Escape byte

A special byte inserted before a flag byte in the data to distinguish it from a framing flag byte.

Bit stuffing

A method of framing at the bit level where frames can contain an arbitrary number of bits made up of units of any size, and five consecutive 1s in the data are automatically stuffed with a 0 bit.

Frame boundary

The boundary between two frames that can be unambiguously recognized by the flag pattern in bit stuffing.

Preamble

A well-defined pattern at the beginning of a frame used to prepare the receiver for an incoming packet.

Positive acknowledgement

A special control frame sent by the receiver to indicate that a frame has arrived safely.

Negative acknowledgement

A special control frame sent by the receiver to indicate that something has gone wrong and the frame must be retransmitted.

Timer

A mechanism used in the data link layer to set an interval for the frame to reach the destination and have the acknowledgement propagate back to the sender.

Sequence numbers

Numbers assigned to outgoing frames to distinguish retransmissions from originals and ensure each frame is passed to the network layer exactly once.

Feedback-based flow control

An approach to flow control where the receiver sends back information to the sender, giving it permission to send more data or informing the sender about its status.

Rate-based flow control

An approach to flow control where the protocol has a built-in mechanism that limits the rate at which senders may transmit data without using feedback from the receiver.

Error-detecting codes

Redundant information added to the data to allow the receiver to deduce that an error has occurred and request retransmission.

Error-correcting codes

Redundant information added to the data to enable the receiver to deduce what the transmitted data must have been.

Error-detecting code

A code used on channels with high reliability, such as fiber, that adds redundancy to each block to allow the receiver to figure out the originally transmitted block.

Error-correcting code

A code used on channels with many errors, such as wireless links, that uses error-detecting codes and retransmissions to correct errors.

Burst errors

Errors that occur in bursts rather than singly

—> often caused by physical processes like deep fades on wireless channels or transient electrical interference on wired channels.

Erasure channel

A channel where the location of an error is known, making it easier to correct errors compared to channels that flip bits.

Hamming distance

The number of bit positions in which two codewords differ, used to determine the error-correcting capability of a code.

Block code

A code where the check bits are computed solely as a function of the data bits they are associated with, often using XOR or modulo 2 addition.

Systematic code

A code where the data bits are sent directly along with the check bits, without being encoded themselves before transmission.

Code rate

The fraction of the codeword that carries information that is not redundant, represented as m/n.

Syndrome

The check results obtained by the receiver when redoing the check bit computations on the received codeword.

Hamming code

An error-correcting code that uses check bits to correct single errors or detect double errors, with a Hamming distance of 3.

Error Syndrome

The set of check results that indicates the presence and location of an error in a code.

Convolutional Code

A type of error-correcting code that processes a sequence of input bits and generates a sequence of output bits based on the current and previous input bits.

Constraint Length

The number of previous bits on which the output of a convolutional code depends.

Reed-Solomon Code

A linear block code that operates on m-bit symbols and uses redundancy to correct errors.

LDPC Code

Low-Density Parity Check code, a linear block code with a low density of 1s in its matrix representation, known for its excellent error-correction abilities.

Parity

A simple error-detecting code that appends a single parity bit to the data, ensuring that the number of 1 bits in the codeword is even or odd.

Checksums

Error-detecting codes that compute a sum or checksum of the data bits and include it in the transmission to detect errors.

Cyclic Redundancy Checks (CRCs)

Error-detecting codes that use polynomial division to compute a remainder, which is appended to the data and checked at the receiver to detect errors.

Interleaving

A technique used to improve protection against burst errors by computing parity bits over the data in a different order than the order in which the data bits are transmitted.

Interleaving

A technique used to convert a code that detects or corrects isolated errors into a code that detects or corrects burst errors.

Burst error

A type of error in which multiple bits in a sequence are affected, typically characterized by at least the first and last bits being wrong.

Parity bits

Additional bits added to a data sequence to detect errors, particularly burst errors. In the context of interleaving, parity bits on different columns can detect errors in the presence of burst errors.

Checksum

A group of check bits associated with a message, used to detect errors. It can be calculated using various methods, such as parity or a running sum of the data bits.

—> 1. divide the data into equally sized segments
—> 2. use 1s complement = sum of these segments

—> 3. calculate the sum - sent to the receiver. Ig sum = 0 the no error detected

Internet checksum

A 16-bit checksum used in the IP protocol to detect errors in Internet packets. It operates on words rather than bits, providing better error detection capabilities.

Cyclic Redundancy Check (CRC)

A type of error-detecting code widely used at the link layer. It treats bit strings as polynomials and uses polynomial arithmetic to compute a checksum that can detect errors.

Generator polynomial

A polynomial agreed upon by the sender and receiver in CRC-based error detection. The CRC is computed by dividing the frame by the generator polynomial, and if there is a remainder, a transmission error is detected.

Burst Length

The number of bits in a burst.

G(x)

The polynomial used for division in the CRC calculation.

Probability of Valid Frame

The likelihood of a frame being accepted as valid.

Error Burst

A burst of bits that contains an error.

Probability of Undetected Bad Frame

The likelihood of a bad frame going unnoticed.

CRC-32

The CRC polynomial used in the IEEE 802 standard.

Hamming Distance

The number of bit positions at which two CRC polynomials differ.

Shift Register Circuits

Hardware used to compute and verify CRCs.

Elementary Data Link Protocols

Protocols of increasing complexity used in data link layer communication.

Independent Processes

The assumption that the physical layer, data link layer, and network layer are separate processes.

Unidirectional Communication

The assumption that machine A wants to send data to machine B.

Reliable Machines and Processes

The assumption that machines do not crash.

Frame

A unit of data consisting of a packet, control information, and a checksum.

Frame Header

The control information fields in a frame.

Packet

The unit of information exchanged between the network layer and the data link layer.

Boolean

An enumerated type that can take on the values true and false.

Seq Nr

A small integer used to number frames for identification.

Frame Kind

An enumeration defining the type of frame (data, ack, or nak).

Wait for Event

A procedure that waits for an event to happen and returns its type.

From Network Layer

A procedure that fetches a packet from the network layer for transmission.

To Network Layer

A procedure that delivers information from an inbound frame to the network layer.

From Physical Layer

A procedure that retrieves an inbound frame from the physical layer.

To Physical Layer

A procedure that passes a frame to the physical layer for transmission.

Start Timer

A procedure that starts the clock running and enables the timeout event.

Stop Timer

A procedure that stops the clock and disables the timeout event.

Start Ack Timer

A procedure that starts an auxiliary timer and enables the ack timeout event.

Stop Ack Timer

A procedure that stops the auxiliary timer and disables the ack timeout event.

Enable Network Layer

A procedure that allows the network layer to cause a network layer ready event.

Disable Network Layer

A procedure that forbids the network layer from causing a network layer ready event.

Inc

A macro that increments a value circularly.

Network Layer Enable/Disable

Procedures used in sophisticated protocols to control the network layer's ability to interrupt and send packets.

Event = Network Layer Ready

An indication that the network layer is enabled and ready to send a packet.

Frame Sequence Numbers

Numbers assigned to frames in the range 0 to MAX SEQ (inclusive) to keep track of their order.

Inc

A macro that increments a sequence number by 1 circularly, wrapping around from MAX SEQ to 0.

Protocol Declarations

Declarations of variables and types used in the protocols, typically included in a header file.

Simplex Link-Layer Protocols

Basic protocols that handle one-directional data transmission.

Utopia Protocol

A simple protocol that assumes an error-free communication channel and infinite buffer space.

Sender1

Procedure in the Utopia protocol that continuously sends data packets from the network layer.

Receiver1

Procedure in the Utopia protocol that receives frames and passes the data to the network layer.

Stop-and-Wait

A flow control protocol where the sender waits for an acknowledgement before sending the next frame.

Sender2

Procedure in the Stop-and-Wait protocol that sends frames and waits for acknowledgements.

Receiver2

Procedure in the Stop-and-Wait protocol that receives frames, passes the data to the network layer, and sends acknowledgements.

Error Correction

The addition of sequence numbers and Automatic Repeat reQuest (ARQ) to handle errors in communication channels.

Sequence Numbers

Numbers added to frame headers to distinguish between new frames and duplicates.

Sequence Number

A field in the header of a data link protocol that identifies the order of frames being sent or received.