Data Link Layer - HUST Computer Network

Basic Concepts of Data Link Layer#

Data link communication may use different protocols.

Link#

Refers to a segment of physical line (wired or wireless) from one node to an adjacent node, without any other switching nodes in between.

Data Link#

When transmitting data over the link (in terms of physical properties), in addition to the link itself, some necessary communication protocols are required to control the transmission of data. The hardware and software that implement these protocols added to the link (the physical realization) constitute the data link.

For example, network cards, network adapters, and their associated software drivers implement these protocols. Generally, network adapters include both the data link layer and physical layer functionalities.

Network Card (Data Link)= \left\{ \begin{align} &Data Link Layer \\ &Physical Layer \end{align} \right.

Frame#

The Protocol Data Unit (PDU) for logical communication between peer entities at the data link layer in the horizontal direction.

WAN and LAN#

WAN (Wide Area Network) uses point-to-point links (PPP, HDLC).

High bandwidth, long distance (high latency), large bandwidth delay.

LAN (Local Area Network) uses multipoint connections (Ethernet, Wireless LAN, VLAN).

Very convenient to connect nodes.
Once connected to a shared medium (or network switch), it can connect to all other nodes.
Multipoint access coordinates each node's access and use of the shared medium, considering conflicts after coordination.

Services Provided by the Data Link Layer#

Three problems that need to be solved: frame delimitation, transparent transmission, error detection.

Flow control: Speed matching between adjacent sending and receiving nodes.

Error detection: Errors caused by signal attenuation and noise; the receiver needs to detect errors and notify the sender to retransmit or discard the frame.

Frame Encapsulation, Transparent Transmission, Error Detection, Reliable Transmission#

Frame Encapsulation#

What the data link layer delivers to the upper layer is the Protocol Data Unit (PDU), which is encapsulated into a frame by adding a frame header and a frame trailer.

The frame header and trailer contain important control information.

One of the functions of the frame header and trailer is frame delimitation. (And ==not every data link layer protocol's frame contains frame delimitation flags==, such as MAC addresses using inter-frame spacing to delimit frames.)
==To improve the efficiency of data link layer frame transmission, the length of the frame's data payload should be made as large as possible compared to the length of the header and trailer.==
Considering the demand for buffer space and error control, each data link layer protocol specifies an upper limit on the length of the frame's data payload, known as the Maximum Transfer Unit (MTU). For example, the MTU for Ethernet is 1500 bytes.

Frame Encapsulation and MAC Address#

FCS field
Frame start delimiter
Pre-synchronization code

PPP Frame#

Identify Frame, Check Frame#

01m38s
Inter-frame spacing between preamble codes: 96 bits.

Transparent Transmission#

Frame delimitation error: If the data payload field of the frame contains the same field as the frame header or trailer, without taking other measures, the receiver's link layer will encounter a frame delimitation error.

Transparent transmission means that the data link layer imposes no restrictions on the Protocol Data Unit (PDU) delivered to the upper layer, as if the data link layer does not exist.

Methods to Achieve Transparent Transmission#

05m36s

Byte Stuffing - Using Escape Characters - Byte-Oriented Physical Link#

The sender scans the bit stream delivered at the physical layer.
Before delivering the frame to the physical layer, the data payload of the frame is scanned, and each time a frame delimiter appears, an escape character is inserted before it. The receiver knows that the first frame delimiter encountered is the start of the frame, and upon encountering the escape character, it knows that the following 1-byte content is data (even though it is the same as the frame delimiter). After removing the escape character, the subsequent content is extracted as data. When the frame delimiter is encountered again, it is received as data.

When the frame itself contains an escape character, an additional escape character is added before the escape character.
The escape character is a special control character, 1 byte in length, with a decimal value of 27, not the three characters ESC.

Bit Stuffing - Bit-Oriented Physical Link#

Add 0 after five consecutive 1s.

0 Bit Stuffing Exercise

Error Detection#

How does the receiver know that an error has occurred?

Bit errors: The actual communication link is not ideal, and errors can occur during the transmission of bits; 1 may become 0, and 0 may also become 1. (Affected by noise interference, transmission media quality, etc.)
Bit Error Rate (BER): The ratio of the number of erroneous bits transmitted over a period of time to the total number of bits transmitted is called the bit error rate.
- Improving the signal-to-noise ratio of the link can reduce the bit error rate. However, in actual communication links, it is impossible to reduce the bit error rate to zero.
Error detection detects bit errors.
1. Both the sender and receiver use the same error detection technique, using error detection codes.
2. The field at the end of the frame used to store the error detection code is called the Frame Check Sequence (FCS).
3. The error detection code can only detect that an error has occurred during the transmission of the frame, but it cannot locate the error, so it cannot correct the error; ==it only knows that there is an error, but does not know where the error is.==
4. To further ==correct errors==, more redundant error correction codes (such as Hamming codes) can be used for forward error correction. However, error correction codes have a relatively high overhead and are rarely used in computer networks.
5. Error correction retransmission methods can be used to correct errors during transmission, or simply discard frames that are detected to have errors.
  1. Retransmission is called reliable transmission service.
  2. Discarding is called unreliable transmission service.

Parity Check#

02m18s

Odd parity adds 1 parity bit to the data to be sent, making the total number of bits 1 odd after adding the parity bit.
Even parity adds 1 parity bit to the data to be sent, making the total number of bits 1 even after adding the parity bit.

If there are an odd number of bits that have errors in the transmitted data, the parity of the number of bits 1 will change, which can detect errors.
If there are an even number of bits that have errors in the transmitted data, the parity of the number of bits 1 will not change, which cannot detect errors (missed detection).
In practical use, parity checks can be further divided into vertical parity checks, horizontal parity checks, and horizontal vertical parity checks.

Cyclic Redundancy Check#

05m43s
The data link layer widely uses Cyclic Redundancy Check (CRC) error detection technology, which has a very low missed detection rate and is very easy to implement in hardware, so it is widely used in the data link layer.

The sender and receiver agree on a generating polynomial G(X).
The sender calculates the error detection code (redundant code) based on the data to be sent and the generating polynomial G(X) and appends the redundant code to the data to be sent.
The receiver, upon receiving the data and redundant code, calculates whether the received data and redundant code have errors using the generating polynomial G(X).

Generating Polynomial#

About Remainders#

When the number of bits can match the divisor, it is called sufficient for division, marked as 1 above.
When it cannot be matched, it is called insufficient for division, marked as 0 above.
10m03s

Reliable Transmission#

Wired links and wireless links provide different services.

Wired links: Low bit error rate, do not require the link layer to provide reliable transmission, error handling is done by the upper layer.
Generally, wired links have a relatively low bit error rate. To reduce overhead, reliable transmission service is not required from the data link layer to its upper layer. Even if errors occur, the issue of reliable transmission is handled by the upper layer.
Rarely used on low-error links (very reliable links themselves) (fiber optics, some twisted pairs): Ethernet.
Wireless links: High bit error rate, the link layer must provide reliable transmission.
Prone to interference, with a relatively high bit error rate, thus requiring the data link layer to provide reliable transmission services to its upper layer.
Reliable data transmission is needed on high-error links: Wireless LAN.

ARQ Protocol#

Automatic Repeat reQuest (ARQ) is one of the error correction protocols in the data link layer and transport layer of the OSI model.

Classification
Stop-and-Wait ARQ Protocol: Stop-and-Wait Protocol.
Continuous ARQ Protocol (combining window mechanism): Go-Back-N Protocol and Selective Repeat Protocol.

At which layer does ARQ actually operate?

==ARQ is a scheme that can reliably transmit data over an unreliable data channel==, so both the link layer and transport layer use ARQ, and it is not exclusive to any one layer.
Just because one layer uses ARQ does not mean that the communication of its upper layer is reliable. Because ARQ only guarantees that the point-to-point communication using it is reliable, for example, the data link layer only guarantees reliable communication between you and your router; the communication from your router to the neighborhood router may also be reliable, but the router itself may fail, congest, or lose packets, meaning that the point itself may have issues.
Therefore, it is necessary to add another layer of ARQ at the transport layer or application layer to ensure the reliability of the entire data channel. For example, if you write a program to communicate at the application layer but do not want to use TCP at the transport layer and want to use UDP, you can also implement reliability in your program using the ARQ protocol.

Types of Transmission Errors#

Reliability of Transmission at Each Layer#

Reliable transmission services are not limited to the data link layer; other layers can also choose to implement reliable transmission.
The implementation of reliable transmission is relatively complex and has a high overhead, whether to use reliable transmission depends on application requirements.

Mechanisms of Reliable Transmission (Three Types)#

Stop-and-Wait Protocol (SW) --- A type of ARQ#

01m08s

Mechanism: Acknowledgment and Negative Acknowledgment, Retransmission, Timeout Retransmission, Numbering Data Packets, Numbering Acknowledgment Packets.

The sender sends a data packet to the receiver. After receiving it, the receiver performs error detection. If no errors are detected, it accepts the data packet and sends an acknowledgment packet back to the sender, abbreviated as ACK. The sender can only send the next data packet after receiving the acknowledgment packet for the previously sent data packet. If the data packet experiences an error during transmission, the receiver discards the data packet and sends a negative acknowledgment packet back to the sender, abbreviated as NAK.
After the sender receives the negative acknowledgment packet for the previously sent data packet, it knows that the data packet it sent earlier has an error and was discarded by the receiver, so it immediately retransmits that data packet. When the receiver receives it, it performs error detection. If no errors are detected, it accepts the data packet and sends an acknowledgment packet back to the sender, ==therefore the sender cannot immediately delete the data packet from the sending buffer after sending it, as it may need to retransmit that data packet later.== Only after receiving the acknowledgment packet for that data packet can it be deleted from the sending buffer.

More Complex SW

04m48s
Loss occurs when the sender sends.
In point-to-point data link layers, loss is generally not a common occurrence.
However, in complex topologically interconnected networks, it may occur between routers.

The sender can start a timeout timer each time it sends a data packet. If the timeout timer reaches the set timeout retransmission time (RTO) but the sender still has not received the acknowledgment or negative acknowledgment from the receiver, it will retransmit the previously sent data packet. As shown in the figure, ==this time is the average round-trip time (RTT) between the sender and receiver==, and the timeout retransmission time (RTO) can generally be set to slightly greater than the average round-trip time (RTT) between the sender and receiver. When the sender's timeout timer times out, it immediately retransmits the previously sent data packet. If the receiver correctly receives the retransmitted data packet, it sends the corresponding acknowledgment packet back to the sender, and upon receiving it, the sender can send the next data packet. If the receiver correctly receives that data packet, it sends the corresponding acknowledgment packet back to the sender. Thus, we add a timeout retransmission mechanism to the stop-and-wait protocol based on the confirmation, negative acknowledgment, and retransmission mechanisms.

==Acknowledgment Packet Loss==
If the acknowledgment packet is lost during transmission, this will inevitably cause ==the sender to timeout and retransmit==, resulting in ==the receiver receiving two identical data packets==. If the receiver cannot ==identify that the received data packet is a duplicate of the previously received data packet==, it will ==lead to the transmission error of duplicate packets==. To ==avoid the transmission error of duplicate packets==, it is necessary to ==attach a sequence number to each packet==. As shown in the figure, for the stop-and-wait protocol, since ==each data packet is sent and then stopped and waited==, it is sufficient to ensure that ==each new data packet sent has a different sequence number from the last sent data packet==. Therefore, using one bit to number is sufficient, carrying sequence numbers 0 or 1; when the receiver continuously receives data packets with the same sequence number, it can identify the transmission error of duplicate packets. In this case, the receiver should discard the duplicate data packet and must send another acknowledgment packet back to the sender. Upon receiving it, the sender can send the next data packet, which has a different sequence number from the previous data packet. If the receiver correctly receives that data packet, it sends the corresponding acknowledgment packet back to the sender. Thus, we add a mechanism for numbering data packets to the stop-and-wait protocol based on the confirmation, negative acknowledgment, and retransmission, and timeout retransmission mechanisms.

Each packet is numbered, carrying an identifier to ensure it is only received once and not received twice due to retransmission.

==Acknowledgment Packet Numbering Issue==
The sender sends the 0 sequence data packet, and after the receiver correctly receives it, it sends an acknowledgment packet back to the sender. Due to some reason, this acknowledgment packet is delayed, which will inevitably lead to the sender timing out and retransmitting the 0 sequence data packet. During the retransmission of the 0 sequence data packet, the sender receives the delayed acknowledgment packet, and then sends the 1 sequence data packet. The receiver receives the retransmitted 0 sequence data packet and knows from the sequence number that this is a duplicate data packet, so it discards it and sends another acknowledgment packet for the 0 sequence data packet. Thus, the sender will receive two acknowledgments for the 0 sequence data packet. However, the sender will mistakenly interpret the second acknowledgment for the 0 sequence data packet as an acknowledgment for the 1 sequence data packet. If acknowledgment packets are also numbered, the sender can know that this is a duplicate acknowledgment for the 0 sequence data packet and can ignore it. After the receiver correctly receives the 1 sequence data packet, it sends an acknowledgment for the 1 sequence data packet back to the sender, with the acknowledgment number being 1. Upon receiving it, the sender sends the next data packet, with the sequence number being 0. Please note that this 0 sequence data packet is not the same as the previous 0 sequence data packet, and the receiver correctly receives it and sends the corresponding acknowledgment packet back with the acknowledgment number being 0.

Summary of considerations:

Channel Utilization of SW

11m33s

The horizontal axis represents time. For simplicity, assume there is a direct channel between the sender and receiver. After the sender sends a data packet, it stops sending and waits for the receiver's acknowledgment of that data packet. After receiving the acknowledgment packet, it can send the next data packet, and so on. This period is the sending delay incurred by the sender when sending the data packet, denoted as TD. This period is the time taken for the signal to travel back and forth between the sender and receiver, denoted as RTT.
This period is the sending delay incurred by the receiver when sending the acknowledgment packet, denoted as TA. This is the total time experienced by the sender from the start of sending a data packet to being able to send the next data packet using the stop-and-wait protocol. Since only the time TD is used to transmit useful data, which is the data packet, the channel utilization is good, and can be calculated using the following formula. TA is generally much smaller than TD because the length of the acknowledgment packet is generally much smaller than that of the data packet, so TA can be ignored.
When the time taken for the signal to travel back and forth between the sender and receiver (RTT) is much greater than the sending time of the data packet (TD), for example, the RTT of a geostationary satellite link is very large. If we use such a link and the data packet to be sent is small and the sending rate is high, the channel utilization will be very low. When RTT is much smaller than the sending time of the data packet (TD), for example, the RTT of a wireless LAN is generally much smaller than TD, the channel utilization is still relatively high. It should be noted that the above derivation does not consider the occurrence of timeout retransmissions; if timeout retransmissions occur, the channel utilization for transmitting useful data information will decrease further.
In summary, ==when the round-trip time (RTT) is relatively large, to improve channel utilization, it is not suitable for the sender and receiver to adopt the stop-and-wait protocol==, and it is better to choose to use the Go-Back-N protocol or Selective Repeat protocol.

Example Problem
14m13s

Summary

Go-Back-N Protocol (GBN)#

00m37s
In the SW protocol, we send once and wait for an acknowledgment each time, with each operation being 1 to 1, which is inefficient. GBN wants to send multiple packets at once, and these multiple packets are acknowledged collectively, so there is no need to go back and forth.

When using pipelined transmission, the sender cannot continuously send data packets without limit, as this may cause routers or receivers in the network to be unable to process these data packets in time, leading to packet loss, which is actually a waste of network resources. (Limit the number of packets sent.)
The Go-Back-N protocol uses a pipelined transmission method and utilizes a sending window to limit the number of data packets the sender can continuously send, which belongs to the continuous ARQ protocol.

Using n bits to number the packets, the range is 0-2^n-1. In this example, assume 3 bits are used to number the packets, so the range of sequence numbers is 0-7. When the sequence number increases to 7, the next sequence number starts again from 0.

The sender's sending window and the receiver's receiving window slide forward according to the above rules, so this type of protocol is also called a sliding window protocol.

No transmission errors

06m03s

Transmission errors, Go-Back-N
07m33s
The received ones turn green, where there is loss, where it stops, how many are received, the blue window moves several spaces.

Once an error occurs, it is necessary to go back and retransmit the previously sent N data packets.

12m17s Example Explanation

Sending window and receiving window

When the sending window Wt exceeds the range of values

Example Problem
18m04s

Selective Repeat Protocol (SR)#

Compared to the previous two

To ensure that the sender only retransmits the erroneous data packets, the receiver ==no longer uses cumulative acknowledgment==, but needs to acknowledge each correctly received data packet individually.
Wr is no longer equal to 1, so that ==the receiver can first accept out-of-order packets that are error-free and fall within the receiving window==, and after all missing packets are received, they can be delivered to the upper layer together.

Example Explanation
03m47s
The key logic here is that this method will intentionally wait a bit and only send the acknowledgment for the missing one, sacrificing a bit of occasional error issues to ensure overall stability.

Example Problem:
09m48s
Which one was not received, just return which one was not received.

Point-to-Point Protocol (PPP)#

Point-to-Point Protocol (PPP) is currently the ==most widely used== point-to-point ==data link layer protocol==.

Current Applications

Personal user computers connect to an ISP via PPP to access the Internet. The communication between personal users and ISPs at the data link layer is generally PPP (PPPoE is a protocol that works over Ethernet, allowing ISPs to provide interface services to users through digital subscriber line modems and broadband access technologies in the form of Ethernet interfaces).
Dedicated lines between wide area routers.

Composition of PPP#

Encapsulation methods for various protocol data packets (encapsulated into frames).
Link Control Protocol (LCP)
- Used to establish, configure, and test the connection of the data link.
A set of Network Control Protocols (NCPs)
- Each protocol supports different network layer protocols.

Format of PPP Frame#

PPP Solves the Transparent Transmission Problem, Frame Identification Appears in the Data Portion#

Byte-oriented asynchronous link (byte is the basic unit of information).
- Uses byte stuffing, inserting escape characters.
Bit-oriented synchronous link (bit is the basic unit of information).
- Uses bit stuffing, inserting 0.

Transparent Transmission of Byte-Oriented Asynchronous Link#

Bit-Oriented Synchronous Link#

Bit stuffing, inserting 0, previously done this way.

Error Detection of PPP Frame#

The FCS field at the end performs frame checking.
Uses cyclic redundancy check.

The receiver performs CRC check on each received PPP frame.

If the CRC check is correct, the frame is accepted; otherwise, the frame is discarded.

Using PPP at the data link layer provides unreliable data transmission service to the upper layer.

Example of PPP with Dial-Up Access#

10:15
Starts and ends in a stationary state.

Ethernet#

Three Ways of Data Communication#

[[Unicast]]: One-to-one communication.
[[Broadcast]]: One-to-all communication, the information sent must reach everyone.
- ==Local area networks mainly use shared channels== for communication, primarily through broadcasting.
- Ethernet, Wireless LAN.
[[Multicast]]: One-to-a-group communication, sending information to a specific group of users.

Differences in Link Layer between LAN and WAN#

Medium Access Control: Solves the conflict problem during data transmission in the channel.

In LAN, all nodes share the channel.
In WAN, point-to-point connections do not share channels, have no conflicts, and do not require medium access control.

Point-to-point data link (WAN) control (dial-up link).

No need for medium access control.
No need for explicit MAC addressing.
Common protocols: HDLC, PPP.

Two Ways to Allocate Channels#

Static Channel Allocation#

Pre-allocated to each user in a certain way, with different usage situations for different users.

For example: Frequency Division Multiplexing, Time Division Multiplexing.
As long as one user gets their own, there will be no conflict with others.

Dynamic Channel Allocation#

Multiple users share a single line, and the channel is dynamically allocated to users based on demand (using Multiple Access Protocol). The channel does not need to be pre-allocated and is open.

Random Access.
Characteristics: Sites or users compete for the channel, which may lead to conflicts.
Typical random access protocols: ALOHA Protocol, CSMA Protocol, CSMA/CD Protocol (used in shared Ethernet).
(Ordered) Controlled Access Protocol - sequential access.
Characteristics: Sites are explicitly assigned, and conflicts do not occur.
- For example, Token method.

Special Cases of Link Layer Handling Channels#

Broadcast Multiple Access Link (LAN): Due to potential media contention.
It can also be subdivided into:

Media Access Control Sub-layer.
- Media Access Control (MAC) sub-layer specializes in handling media access contention and conflict issues.
Logical Link Control Sub-layer.

Main Protocols of the Data Link Layer#

Point-to-Point Protocol (PPP).
Ethernet.
High-Level Data Link Protocol (HDLC).
Frame Relay.
Asynchronous Transfer Mode (ATM).

Common Standards for Local Area Networks (Ethernet is a limited local area network)#

IEEE 802.1 is a collection of protocols:
IEEE 802.1q defines the VLAN tagging protocol; IEEE 802.1s defines the Multiple Spanning Tree Protocol.
802.2 LLC: rarely used.
DIX Ethernet V2: does not require LLC sub-layer because it implements connectionless packet transmission service.
802.3 LAN: commonly referred to as Ethernet (uses CSMA/CD access control).
802.5 Token Ring Network.
802.4 Token Bus Network, etc.
802.11 Wireless LAN: operates using DCF (Distributed Control) and PCF (Central Control).

Ethernet#

The MAC layer of Ethernet does not have flow control, ARQ, and error correction functions. (This allows Ethernet hardware to be implemented very easily and efficiently, significantly reducing costs. It is precisely because it is cheap and sufficient that Ethernet has become so popular.)
The key premise for this reasonable design is Wired and LAN, which determines that the bit error rate is very low. Single-hop transmission rarely has errors; if errors occur, Ethernet will directly drop the packet, allowing the upper layer to detect packet loss and retransmit.
Of course, the overhead of retransmission at the upper layer is much greater than that of retransmission at the link layer. For example, having TCP perform retransmissions is inefficient because end-to-end retransmissions consume significantly more network capacity due to multiple hops; additionally, TCP's detection timing is not as timely as that of the link layer, leading to delayed triggers for retransmissions, which affects transmission performance.
If we shift our focus to WAN and wireless networks, the data link layer becomes much more complex. At this point, long-distance communication and wireless channels can lead to increased bit error rates. If the data link layer does not provide reliable transmission, relying too much on the upper layer is inefficient. For example, 802.11 has flow control. In mobile communications like 3G and 4G, it becomes even more complex.

Shared Ethernet#

Ethernet initially used passive cables (not including power lines) as a shared bus to transmit frames, belonging to baseband bus local area networks, with a transmission rate of 2.94Mb/s. (There are shared Ethernet using shared buses and shared Ethernet using hubs.)

Ethernet has now evolved from traditional shared Ethernet to switched Ethernet, with transmission rates increasing from 10Mb/s to 100Mb/s, 1Gb/s, and even 10Gb/s.
Ethernet is currently the most widely used local area network technology, replacing other LAN technologies such as Token Ring, FDDI, and ARCNET. (Ethernet is just one type of LAN technology.)

Network Adapter#

Communication between the network card and the CPU occurs over the I/O bus on the motherboard, using parallel transmission.
Communication between the network card and the external Ethernet (LAN) generally occurs through transmission media (coaxial cables, twisted pair cables, optical fibers) using serial transmission.
In addition to implementing the functions of the physical layer and data link layer, it also needs to:
- Convert between parallel and serial transmission.
- Since the transmission rate of the network and the transmission rate on the computer's internal bus are not the same, the core chip of the network card will include memory for buffering data.
The network card driver ==is responsible for driving the network card to send and receive frames.==

MAC Address#

When multiple hosts are connected to the same broadcast channel, to enable communication between two hosts, ==each host must have a unique identifier, i.e., a data link layer address==. (This allows the computer's network card to determine whether the data frame is sent to itself.)
Each frame sent by a host carries the data link layer addresses of the sending host (source host) and the receiving host (destination host). Since these addresses are used for Medium Access Control (MAC), they are called MAC addresses.

MAC addresses are generally hard-coded in the network card's electrically erasable programmable read-only memory (EEPROM), so MAC addresses are also referred to as hardware addresses.
MAC addresses are sometimes referred to as physical addresses. (Use the ipconfig/ip command to view TCP/IP configuration information.)
Do not be misled by the term "physical" in physical address, mistakenly thinking that physical addresses belong to the physical layer of the network architecture. (Physical addresses belong to the data link layer.)

==MAC addresses are unique identifiers for interfaces.==

Format of MAC Address#

Bluetooth also occupies MAC addresses.

Sending Order of MAC Addresses in IEEE 802 LAN#

Unicast and Broadcast MAC Address Examples#

17:31
Note the difference between receiving and accepting.

Each time the network card receives a frame from the network, it checks the destination MAC address in the frame header and processes it as follows:
(1) If the destination MAC address is the broadcast address (FF-FF-FF-FF-FF-FF), the frame is accepted.
(2) If the destination MAC address is the same as the globally unique unicast MAC address of the network card, the frame is accepted.

The globally unique unicast MAC address is like the ID number on an ID card, having uniqueness, and it is often tied to the user's personal information. Therefore, users should ensure that their globally unique unicast MAC address is not leaked.
To avoid security issues with MAC address leakage when user devices connect to Wi-Fi hotspots, most mobile devices now use random MAC address technology.

(3) If the destination MAC address is a multicast address supported by the network card, the frame is accepted.

(4) If none of the above (1), (2), and (3) conditions are met, the frame is discarded.

Basic Principles of CSMA/CD Protocol#

The goal is to address the issue of many pieces of information circulating simultaneously on the bus, where everyone walking together is likely to encounter collisions.

Shared Bus Ethernet has a natural ==broadcast characteristic==; even if a certain station sends a unicast frame to another station, the ==signal of the frame will also propagate to other== stations on the bus.

When a certain station sends a frame on the bus, ==the bus resources are monopolized by that station==. At this time, if other stations on the bus also want to send frames, a signal ==collision== will occur.
When two or more stations simultaneously use the bus to send frames, a signal collision will occur.

To solve the contention problem among stations on the bus, shared bus Ethernet uses a dedicated protocol CSMA/CD, which stands for Carrier Sense Multiple Access/Collision Detection.

The carrier sense detects that the bus is idle, but the bus is not necessarily idle.
On a shared bus Ethernet using the CSMA/CD protocol, each station only tries to avoid collisions and handles retransmissions after collisions occur, but cannot completely avoid collisions.
When using the CSMA/CD protocol, since the station sending the frame must "send the frame while detecting collisions," it ==is not possible for the station to send and receive simultaneously==, meaning it can only perform half-duplex communication (bidirectional alternating communication).

CDMA (Code Division Multiple Access) allows each user to communicate using the same frequency band at the same time.

TDMA (Time Division Multiple Access) allows all users to occupy the same frequency band at different times.

FDMA (Frequency Division Multiple Access) allows all users to simultaneously occupy different frequency band resources.

CSMA is a contention-based media access control protocol, where multiple stations connected to the same medium use this protocol to send data frames competitively, which may lead to conflicts (also known as collisions).

TDMA, FDMA, and CDMA are common physical layer channel multiplexing technologies that belong to static channel division for multi-user shared channels, which will not cause conflicts.

Utilization Period of Shared Ethernet#

Any station using the CSMA/CD protocol on a shared bus Ethernet may encounter collisions during the process of sending frames. How long must a certain station wait at most after starting to send a frame to detect that its sent frame has collided with frames sent by other stations?

A: Consider the situation where frames sent by two stations located at both ends of the shared bus Ethernet collide.

Example Problem:

Minimum and Maximum Frame Length of Shared Ethernet#

Minimum Frame Length: 64 B

Minimum Frame Length = Bus Propagation Delay * Data Transmission Rate * 2 (the shortest frame length is 64 B; if not, it will be padded).

Maximum Frame Length: 1518 B

Frames that are too long will keep the bus busy and have requirements for the buffer size of the receiving host.

Example Problem:

Backoff Algorithm of Shared Ethernet#

https://www.bilibili.com/video/BV1rd4y1P7Zh?t=3.6
In shared bus Ethernet using the CSMA/CD protocol, the station sending the frame detects collisions while sending the frame. When a collision is detected, it immediately stops sending, waits for a random period of time, and then retransmits.

Stations on shared bus Ethernet use the Truncated Binary Exponential Backoff algorithm to select the random backoff time.
If collisions occur multiple times in succession, it indicates that many stations may be competing for the channel. However, using the above backoff algorithm can make the average time needed to delay retransmission increase with the number of retransmissions (i.e., dynamic backoff), thus reducing the probability of collisions.
If retransmissions reach 16 times without success, it indicates that too many stations intend to send frames simultaneously, leading to continuous collisions. In this case, the station should give up retransmission and report to the upper layer.
A. When the number of retransmissions k <= 10, select the minimum of k and 10; when k > 10, select k = 10.
B. Randomly select a number n from 0, 1, 2, 3... 2^k - 1, and the retransmission time is n times the basic backoff time, i.e., 2τn.
C. When retransmissions reach 16 times, discard the frame and report an error to the upper layer.

Channel Utilization of Shared Ethernet#

Shared Ethernet Using Hubs#

Ethernet has developed a device called a hub that uses large-scale integrated circuits to replace the bus and has very high reliability.
The transmission media connecting stations to the hub also use cheaper and more flexible twisted pair cables.

Shared Bus Ethernet and Star Topology Ethernet#

The physical topology structures are different, but essentially they are the same, with the same working logic, using the CSMA/CD protocol to share (contention) network resources.

10BASE-T Star Ethernet#

Physical Layer Extended Ethernet#

Extending the Distance Between Stations and Hubs#

In coaxial cable shared bus Ethernet, repeaters are used to extend the distance.

In twisted pair hub shared Ethernet: the distance from each station to the hub is less than 100m, using optical modem to extend the distance.

Extending the Coverage and Number of Stations of Shared Ethernet#

If different collision domains use different data rates, they can be connected through hubs.

Data Link Layer Extended Ethernet (408 Not Tested)#

Using Bridges#

Bridges operate at the data link layer (including the underlying physical layer), so bridges possess capabilities related to the data link layer.
Bridges can identify the structure of frames.
Bridges can forward or discard received frames based on the destination MAC address in the frame header and the bridge's own frame forwarding table.
They can connect local area networks with different physical layers, different MAC sub-layers, and different rates.
Using store-and-forward increases delay.
When bridge segments with different MAC sub-fields are connected, the delay is greater.
Bridges do not have flow control functions at the MAC sub-layer.
They are only suitable for local area networks with few users and low communication volume; otherwise, network congestion may occur due to excessive information propagation.

Main Structure and Basic Working Principle of Bridges#

03m20s

Example:

Forwarding Broadcast Frames#

Transparent Bridge's Self-Learning and Frame Forwarding Process#

Transparent Bridges establish forwarding tables through a self-learning algorithm.
The "transparent" in transparent bridges means that the stations in the Ethernet do not know which bridges their sent frames will pass through to reach the destination station. In other words, the bridges in the Ethernet are invisible to the stations.
The standard for transparent bridges is IEEE 802.1D, which gradually builds its forwarding table through a self-learning algorithm based on the mutual communication between stations in the Ethernet.

Discard: When the interface in the forwarding table is the same as the interface through which the frame entered the bridge, the frame is discarded.

Spanning Tree Protocol of Transparent Bridges#

In a ring structure, broadcast frames or unicast frames without a destination address may circulate indefinitely in the loop.

Switched Ethernet (Full Duplex)#

Bridges typically have very few interfaces, usually only 2-4, and are generally used to connect different network segments.
==Ethernet switches== solve this problem, ==essentially being bridges with multiple interfaces==, also known as switching hubs or layer 2 switches.
- Layer 2 refers to Ethernet switches operating at the data link layer (including the physical layer).
Similar to bridges, the internal forwarding table of switches is also established gradually through a self-learning algorithm based on communication between hosts in the network.
- Additionally, switches also use the Spanning Tree Protocol (STP) to generate communication paths that connect the entire network without creating loops.
Ethernet that only uses switches (without hubs) is called switched Ethernet.

02m13s
Bridges can isolate collision domains.

Ethernet Switch#

Each interface of the switch can connect to a computer, a hub, or another switch. (Three connection methods).
When the switch's interface connects to a computer or switch, it can operate in full duplex mode and can simultaneously connect multiple pairs of interfaces internally, allowing each pair of communicating computers to transmit data without collisions, thus eliminating the need for the CSMA/CD protocol.
When the switch's interface connects to a hub, that interface can only use the CSMA/CD protocol and can only operate in half-duplex mode.
Modern switches and network cards in computers can automatically recognize these two situations and switch automatically to the corresponding working mode.
Switches generally have interfaces with multiple rates, such as 10 Mb/s, 100 Mb/s, 1 Gb/s, and even 10 Gb/s interfaces, most of which support multi-rate adaptation.

Self-Learning and Frame Forwarding of Switches#

03m06s

Switches blindly broadcast when there is no destination address, and send to the corresponding port when there is a destination address.
Ethernet switches are plug-and-play devices; when powered on, their internal frame switching table is empty. As communication occurs between hosts in the network, Ethernet switches automatically and gradually establish their frame switching tables through a self-learning algorithm.

Example Problem:

Storage Forwarding and Cut-Through Switching of Switches#

General switches use the "store-and-forward" method. To reduce the forwarding delay of switches, some switches adopt the cut-through switching method.
Switches using cut-through switching immediately determine the forwarding interface based on the destination MAC address of the frame while receiving the frame, and then forward it through their internal hardware-based crossbar matrix without having to cache the entire frame first.
The delay of cut-through switching is very small.
Cut-through switching does not check for errors and directly forwards frames, which may lead to some invalid frames being forwarded to other hosts.

Comparison of Shared Ethernet and Switched Ethernet (Differences Between Hubs and Switches)#

00m31s

Difference 1: Working Layer

Hubs operate at the physical layer, belonging to layer 1 devices. Every time data is sent, all ports can receive it, using a broadcast method, thus significantly limiting network performance.
Switches operate at the data link layer, belonging to layer 2 devices. After learning, each port forms a MAC address forwarding table, forwarding data based on the MAC address of the data packet rather than in a broadcast manner.
Difference 2: Forwarding Method
The working principle of hubs is in a broadcast manner; regardless of which port receives the data, it must broadcast to all ports. When many devices are connected, network performance is significantly affected. (They are in the same broadcast domain.)
Switches forward data based on MAC addresses. After receiving a data packet, they check the destination MAC address of the packet to find the corresponding port for forwarding, rather than broadcasting to all ports. (When the destination address uses the broadcast address FF-FF-FF-FF-FF-FF, it is a broadcast frame and is in the same broadcast domain.)
Difference 3: Transmission Mode
Hubs internally use a bus topology, where all nodes share a single bus for communication. The sending and receiving of data packets use the CSMA/CD protocol, and at any given time, it must be unidirectional, remaining in half-duplex mode. Two ports cannot send and receive data simultaneously, and when two ports communicate, other ports do not work. (Collisions will occur.)
When two ports on a switch communicate, their channels are independent, allowing for full-duplex communication. Two ports can send and receive data simultaneously. (No collisions will occur.)
Difference 4: Bandwidth Impact
Hubs share a single bandwidth regardless of how many ports there are; only two ports can transmit data at the same time, and they can only work in half-duplex mode.
Difference 5: Using Hubs and Switches to Connect Two Independent Shared Ethernet Networks

The network performance of switched Ethernet is far superior to that of shared Ethernet, and hubs have long been replaced by switches.

Broadcast Domain and Collision Domain

Broadcast Domain: A broadcast domain is a logical group of computers where all members receive the same broadcast information.
Collision Domain: In the same network, if any two computers communicate simultaneously, a collision will occur, then the network they form is a collision domain.
All nodes directly connected together and passing through the Ethernet bus can be considered to be in the same collision domain.
For example, under a hub, all terminals share a single link, so at the same time, even one device can send a data packet to occupy this link, which is called a collision domain.
Relationship Between the Two
Collision domains are based on the first layer (physical layer), while broadcast domains are based on the second layer (data link layer).
A broadcast domain refers to the range of stations that can receive a broadcast signal sent by a station. A collision domain refers to how many stations can receive a signal sent from one station to another, excluding the destination station.
All ports of a hub are in the same broadcast domain and collision domain.
Switches (layer 2 switches) have all ports in the same broadcast domain, while each port is a collision domain.
Layer 2 switching can isolate collision domains (and routers can do this too), while routers can isolate broadcast domains (VLANs can also do this) and can also isolate broadcast storms at layer 2.

MAC Frame Format of Ethernet (No Retransmission Mechanism)#

00m05s

The physical layer adds an 8-byte preamble (which can achieve clock synchronization).

Invalid MAC frames that the receiver may receive include the following types:

The length of the MAC frame is not an integer number of bytes.
The value of the FCS field in the MAC frame indicates that the frame has errors.
The length of the MAC frame is not between 64 and 1518 bytes.

When the receiver receives an invalid MAC frame, it simply discards it; the Ethernet data link layer does not have a retransmission mechanism.

Virtual Local Area Network (VLAN)#

The problems caused by a large broadcast domain formed by connections:

Broadcast Storm: Broadcast storms waste network resources and CPU resources of each host.
Difficult to manage and maintain, leading to potential security issues.
Many protocols in the TCP/IP protocol stack use broadcasts:
Address Resolution Protocol (ARP).
Routing Information Protocol (RIPv1).
Dynamic Host Configuration Protocol (DHCP).
NetBEUI: A broadcast protocol used in Windows (broadcast).
IPX/SPX: The protocol stack of Novell networks (broadcast).
Apple Talk: The network protocol stack of Apple Inc. (broadcast).

To isolate broadcast domains.

Methods to segment broadcast domains:

Using routers can isolate broadcast domains (costly).
Virtual Local Area Network technology has emerged.
- Virtual Local Area Network (VLAN): A technology that divides stations in a local area network into logical groups that are independent of physical location. A logical group is a VLAN, and stations within the same VLAN can communicate directly, while stations in different VLANs cannot communicate directly.
- Network administrators can configure switches in the local area network to establish multiple logically independent VLANs.
- Multiple stations connected to the same switch can belong to different VLANs, while multiple stations belonging to the same VLAN can be connected to different switches.

Virtual Local Area Network (VLAN) is not a new type of network; it is merely a service that local area networks can provide to users.

Implementation Mechanism of VLAN#

Based on the interfaces of Ethernet switches, Ethernet interfaces must meet the following conditions:

Able to process frames with VLAN tags, i.e., IEEE 802.1Q frames.
The interfaces of the switch can support different interface types, and the processing methods for frames differ based on the interface types.

IEEE 802.1Q Frame#

Extended from the MAC frame.
==A 4-byte VLAN tag (tag) field is inserted between the source address field and the type field.==

802.1Q frames are generally not processed by user hosts but are processed by Ethernet switches:
When a switch receives a regular Ethernet MAC frame, it inserts a 4-byte VLAN tag to make it an 802.1Q frame, a process referred to as "tagging."
When a switch forwards an 802.1Q frame, it may remove its 4-byte VLAN tag to revert it to a regular Ethernet MAC frame, a process referred to as "untagging." Whether to perform "untagging" depends on the interface type of the switch.

Types of Ethernet Switch Interfaces#

Based on the different ways interfaces handle frames when receiving and sending frames, as well as the different objects they connect to, Ethernet switch interfaces are generally divided into Access and Trunk types.
Differences between Access and Trunk:
Access ports only receive data packets without VID.
- For example, a PC is connected to this switch port via a cable, and when it sends data to the port, the received packet is a data packet without VID. The port then tags this frame with its own PVID.
When sending data packets, access ports remove the VID from all data packets, while trunk ports only remove the VID from data packets that match their PVID; others are forwarded directly.
- When receiving tagged frames (PVID), access ports first check the VID value in the frame and forward it after untagging.

07m26s