Data Link Layer - HUST 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, with no 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 entity) constitute the data link.

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

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.

WAN and LAN#

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

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

LAN 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 and subsequent 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 frame trailer.

The frame header and trailer contain important control information.

One of the functions of the frame header and trailer is frame delimitation. (Not every data link layer protocol's frame contains frame delimitation flags; for example, MAC addresses use inter-frame spacing to define frames.)
==To improve the efficiency of data link layer transmission frames, the length of the frame's data payload should be as large as possible compared to the length of the header and trailer.==
Considering the need 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#

Identifying Frames, Checking Frames#

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 data link layer will have 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 Links#

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 whenever 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 when it encounters 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 next frame delimiter is encountered, it is for data reception.

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

Bit Stuffing - Inserting 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; errors can occur during the transmission of bits, where 1 may become 0, and 0 may become 1. (Affected by noise interference, transmission media quality, etc.)
Bit Error Rate (BER): The ratio of erroneous bits to the total number of transmitted bits over a period of time is called the bit error rate.
- Improving the signal-to-noise ratio of the link can reduce the bit error rate. However, it is impossible to reduce the bit error rate to zero on actual communication links.
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 occurred during the transmission of the frame but 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, the overhead of error correction codes is relatively large and is 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 as erroneous.
  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 ensure that the total number of 1 bits in the data (after adding the parity bit) is odd.
Even parity adds 1 parity bit to the data to ensure that the total number of 1 bits in the data (after adding the parity bit) is even.

If an odd number of bits in the transmitted data are erroneous, the parity of the number of 1 bits will change, allowing for error detection.
If an even number of bits in the transmitted data are erroneous, the parity of the number of 1 bits will not change, resulting in undetectable errors (missed detection).
In practical use, parity checks can be further divided into vertical parity check, horizontal parity check, and horizontal-vertical parity check.

Cyclic Redundancy Check#

05m43s
The data link layer widely uses Cyclic Redundancy Check (CRC) error detection technology, which has a very low undetectable error rate and is very easy to implement in hardware, thus 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), appending 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.
When it cannot be matched, it is called insufficient for division, marked as 0.
10m03s

Reliable Transmission#

Wired links and wireless links provide different services.

Wired links: Low bit error rate, do not require the data 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, the data link layer is not required to provide reliable transmission services 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 data link layer must provide reliable transmission.
Susceptible 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.

Which layer does ARQ actually operate on?

==ARQ is a scheme that can reliably transmit data over unreliable data channels==, so both the data 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; your router to the neighborhood router may also be reliable, but the router itself can fail, congest, or drop packets, meaning that the point itself can have problems.
Therefore, it is necessary to add another layer of ARQ in 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 in 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 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, abbreviated as ACK. The sender can only send the next data packet after receiving the acknowledgment number 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 sent data packet, it knows that the previously sent data packet encountered an error and was discarded by the receiver, so it immediately retransmits that data packet. After the receiver receives it, it performs error detection again. If no errors are detected, it accepts the data packet and sends an acknowledgment packet back to the sender. ==Therefore, after sending a data packet, the sender cannot immediately delete that data packet from the sending buffer, 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 not very common.
However, in complex topologically interconnected networks, it may occur between routers.

The sender can start a timeout timer after sending a data packet. If the timeout timer reaches the set retransmission timeout (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 retransmission timeout (RTO) is generally 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 the timeout retransmission mechanism to the basis of acknowledgment, negative acknowledgment, and retransmission.

==Acknowledgment Packet Loss==
If the acknowledgment packet is lost during transmission, this will inevitably lead to ==the sender's timeout retransmission==, causing ==the receiver to receive 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 ==result in duplicate packet transmission errors==. To ==avoid duplicate packet transmission errors==, it is necessary to ==number each packet==. As shown in the figure, for the stop-and-wait protocol, since ==each data packet is sent and then the sender waits==, it is sufficient to ensure that ==each new data packet sent has a different number from the last sent data packet==. Therefore, one bit is enough to number the packets, carrying either number 0 or 1. When the receiver receives two consecutive data packets with the same number, it can identify the duplicate packet transmission error. In this case, the receiver should discard the duplicate data packet and must send another acknowledgment packet back to the sender. After receiving it, the sender can send the next data packet, which has a different number from the previous one. If the receiver correctly receives this data packet, it sends the corresponding acknowledgment packet back to the sender. Thus, we add the mechanism of numbering data packets to the basis of acknowledgment, negative acknowledgment, retransmission, and timeout retransmission.

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

==Acknowledgment Packet Numbering Issue==
The sender sends a data packet with number 0, 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's timeout retransmission of the data packet with number 0. During the retransmission of the data packet with number 0, the sender receives the delayed acknowledgment packet, and then sends the data packet with number 1. The receiver receives the retransmitted data packet with number 0, and based on the number, it knows this is a duplicate data packet and discards it, sending another acknowledgment packet for the data packet with number 0. Thus, the sender will receive two acknowledgments for the data packet with number 0. However, the sender will mistakenly interpret the second acknowledgment for the data packet with number 0 as the acknowledgment for the data packet with number 1. If the acknowledgment packets are also numbered, the sender can know that this is a duplicate acknowledgment for the data packet with number 0 and can ignore it. After the receiver correctly receives the data packet with number 1, it sends the acknowledgment packet for the data packet with number 1 back to the sender, with acknowledgment number 1. After receiving it, the sender sends the next data packet, which has number 0. Please note that this data packet with number 0 is not the same as the previous data packet with number 0; the receiver correctly receives it and sends the corresponding acknowledgment packet back to the sender with acknowledgment number 0.

Notes and Summary:

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. Upon 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, i.e., the data packet, the channel utilization can be calculated as follows. 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 further decrease.
In summary, ==in cases where 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 they can 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 a reception 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 confirmed collectively, so there is no need to run 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 loss of data packets, which is actually a waste of network resources. (Limit the number of packets sent.)
The Go-Back-N protocol adopts a pipelined transmission method and uses a sending window to limit the number of data packets that 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 that 3 bits are used to number the packets, so the range of numbers is 0-7. When the number increases to 7, the next number starts again from 0.

The sending window of the sender and the receiving window of the receiver 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 the loss occurs stops, and the number received moves the blue window a few 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 value range

Example Problem
18m04s

Selective Repeat Protocol (SR)#

Comparison with 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, allowing the ==receiver to first accept out-of-order packets that are error-free and fall within the receiving window==, and once the missing packets are received, they can be sent 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 will be returned.

Point-to-Point Protocol (PPP)#

The 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, thus accessing 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 user 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 (encapsulation 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 Section#

Byte-oriented asynchronous links (bytes are the basic unit of information).
- Use byte stuffing, inserting escape characters.
Bit-oriented synchronous links (bits are the basic unit of information).
- Bit stuffing, inserting 0s.

Transparent Transmission of Byte-Oriented Asynchronous Links#

Bit Stuffing for Synchronous Links#

Bit stuffing, inserting 0s, was done this way before.

Error Detection of PPP Frames#

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

The receiver performs CRC checks 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 services.

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, where the sent information must reach everyone.
- ==Local area networks mainly use shared channels== for communication, primarily through broadcasting.
- Ethernet, Wireless LAN.
[[Multicast]]: One-to-a-group communication, where information is sent to a specific group of users.

Differences in Data 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 links)

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 channels are dynamically allocated to users based on demand (using Multiple Access Protocols). Channels do not need to be pre-allocated; they are open.

Random Access.
Characteristics: Sites or users compete for channel access, 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 (ring) method.

Special Cases of Link Layer Handling Channels#

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

Media Access Control Sub-layer
- Media Access Control (MAC) sub-layer specifically handles contention and conflict issues.
Logical Link Control Sub-layer.

Major 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 LAN)#

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 services.
802.3 LAN: commonly known as Ethernet (uses CSMA/CD access control).
802.5 Token Ring.
802.4 Token Bus, etc.
802.11 Wireless LAN: operates using DCF (Distributed Coordination Function) and PCF (Point Coordination Function).

Ethernet#

The MAC layer of Ethernet does not have flow control, ARQ, or error correction functions. (This allows for very easy and efficient implementation of Ethernet hardware, significantly reducing costs. It is precisely because it is cheap and usable 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 simply 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, the timing of TCP's detection 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 ensure reliable transmission, relying too much on the upper layer is inefficient. For example, 802.11 does have 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 LANs, 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 LAN 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 CPU occurs over the I/O bus on the motherboard, using parallel transmission.
Communication between the network card and external Ethernet (LAN) generally occurs through transmission media (coaxial cables, twisted pair cables, fiber optics) 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 achieve communication between two hosts, ==each host must have a unique identifier, which is a data link layer address==. (This allows the network card of the computer to determine whether the data frame is sent to itself.)
Each frame sent by each host carries the data link layer address 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 also 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, 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.

The network card checks the destination MAC address in the frame header for each frame received from the network 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 matches 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, which has uniqueness and 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 an inherent ==broadcast characteristic==, meaning that 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, it will result in signal ==collisions==.
When two or more stations simultaneously use the bus to send frames, signal collisions 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 with Collision Detection.

The carrier sensing detects that the bus is idle, but the bus may not necessarily be idle.
Stations on the shared bus Ethernet using the CSMA/CD protocol only try to avoid collisions and handle retransmissions after collisions occur, but cannot completely avoid collisions.
When using the CSMA/CD protocol, since the station sending the frame must "listen for collisions while sending the frame," it ==cannot simultaneously send and receive==, 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 compete to send data frames, 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 sharing, which will not cause conflicts.

The Seizing 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 sending 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 Lengths of Shared Ethernet#

Minimum Frame Length: 64 B

Minimum Frame Length = Total Bus Propagation Delay * Data Transmission Rate * 2 (the shortest frame length is 64 B; if not, padding is required).

Maximum Frame Length: 1518 B

Frames that are too long will keep the bus busy and impose requirements on 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. When a collision is detected, it immediately stops sending and waits for a random backoff time before retransmitting.

Stations in shared bus Ethernet use the Truncated Binary Exponential Backoff algorithm to select the random backoff time.
If multiple collisions occur consecutively, it indicates that many stations are competing for the channel. However, using the above backoff algorithm can make the average time needed to delay retransmissions increase with the number of retransmissions (i.e., dynamic backoff), thus reducing the probability of collisions.
When retransmissions reach 16 times without success, it indicates that too many stations intend to send frames simultaneously, resulting in 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, choose the minimum of k and 10; when k > 10, choose 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.

Comparison of 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 fiber optic modems 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 together 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 have 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 forwarding table.
They can connect LANs with different physical layers, different MAC sub-layers, and different rates.
Using store-and-forward increases delay.
When segments of bridges with different MAC sub-fields are connected, the delay is greater.
The MAC sub-layer does not have flow control functions.
It is only suitable for LANs with a small number of users and low communication volume; otherwise, it may cause network congestion 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 self-learning algorithms.
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 establishes its forwarding table based on the mutual communication between stations in the Ethernet through a self-learning algorithm.

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 segments.
==Ethernet switches== solve this problem, ==essentially being bridges with multiple interfaces==, also known as switching hubs or layer 2 switches.
- Layer 2 means that Ethernet switches operate at the data link layer (including the physical layer).
Similar to bridges, the internal forwarding table of the switch is also gradually established through a self-learning algorithm based on communication between hosts in the network.
- Additionally, switches also use the Spanning Tree Protocol (STP) to create communication paths that connect the entire network without creating loops.
An Ethernet that only uses switches (without hubs) is called switched Ethernet.

02m13s
Bridges can isolate collision domains.

Ethernet Switch#

Each interface of a switch can connect to a computer, or it can connect to a hub or another switch. (Three types of connections.)
When the switch's interface is connected to a computer or another switch, it can operate in full-duplex mode and can internally connect multiple pairs of interfaces simultaneously, 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 automatically switch to the appropriate working mode.
Switches generally have multiple rate interfaces, such as 10 Mb/s, 100 Mb/s, 1 Gb/s, and even 10 Gb/s interfaces, with most interfaces supporting multi-rate adaptability.

Self-Learning and Frame Forwarding of Switches#

03m06s

Switches blindly broadcast when there is no destination address, and when there is a destination address, they send it to the corresponding port.
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 table through a self-learning algorithm.

Example Problem:

Storage Forwarding and Cut-Through Switching of Switches#

General switches adopt the "store-and-forward" method, while some switches use the cut-through switching method to reduce forwarding delay.
Switches using cut-through switching immediately determine the forwarding interface based on the destination MAC address as they receive the frame, forwarding it through their internal hardware-based crossbar matrix without having to cache the entire frame first.
The delay for 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 and are layer 1 devices; every time data is sent, all ports can receive it, using a broadcast method, thus greatly limiting network performance.
Switches operate at the data link layer and are 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 a hub is in broadcast form; regardless of which port receives data, it must broadcast to all ports. When many devices are connected, network performance will be 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 and find the corresponding port to forward the data, 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, with each node sharing 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, maintaining a half-duplex mode. Two ports cannot send and receive data simultaneously, and when two ports are communicating, other ports are inactive. (Collisions may 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 across all ports, meaning that regardless of how many ports there are, only two ports can transmit data at the same time, and they can only operate in half-duplex mode.
Difference 5: Connecting Two Independent Shared Ethernet Networks Using Hubs and Switches

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, and 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, a data packet sent by one device can 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 within which a broadcast signal sent by a station can be received. 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.
A switch (layer 2 switch) has all ports in the same broadcast domain, while each port is a separate collision domain.
Layer 2 switches can isolate collision domains (and routers can do so as well), while routers can isolate broadcast domains (VLANs can also do this), and they can also isolate layer 2 broadcast storms.

MAC Frame Format of Ethernet (No Retransmission Mechanism)#

00m05s

The physical layer adds 8 bytes of preamble (for 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 FCS field of the MAC frame detects an error.
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 broadcasting:
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 divide broadcast domains include:

Using routers can isolate broadcast domains (costly).
Virtual Local Area Network technology has emerged.
- Virtual Local Area Network (VLAN): A technology that divides the stations in a LAN into logical groups that are independent of physical location. A logical group is a VLAN, and the stations within a VLAN have certain common application needs.
- Stations belonging to the same VLAN can communicate directly, while stations in different VLANs cannot communicate directly.
- Network administrators can configure switches in the LAN 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 Networks (VLANs) are not a new type of network; they are simply a service that LANs can provide to users.

Implementation Mechanism of VLAN#

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

They must be 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 handling of frames varies by interface type.

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 connected to this switch port sends data to the port, and the port receives a data packet without VID. It then tags this frame with its own PVID.
Access ports remove VID from all data packets when sending, while trunk ports only remove VID from data packets that match their PVID; others are forwarded directly.
- When receiving tagged frames (with PVID), access ports first check the VID value in the frame and then forward it after removing the tag.

07m26s

Trunk ports

Generally, these are the ports connecting switches to each other; port A connects the PC to the switch.