This article has participated in the activity of "New person creation Ceremony", and started the road of digging gold creation together.

1. Data link layer Overview

A link is a physical line from a node to an adjacent node, while a data link is based on a link with some necessary hardware (such as network adapter) and software (such as protocol implementation).

  1. In the networkHost and routerEtc.Implement the data link layer.

  1. The host and switch in LAN realize data link layer.

  2. Look at the flow of data at a hierarchical level

  1. Only fromData link layerObserve the flow of frames

  1. Data link layerIn framesData transmission

(1) Channel of data link layer

  1. Point-to-point channel: Uses yesOne-to-one, point-to-point.
  2. The radio channel: Uses yesOne-to-many communicationTherefore, it must be usedShared channel protocol to assist these hosts in data transmission.

(2) Encapsulate into frames

Framing: Framing is that the data link layer adds a header and a tail to the data transmitted from the previous layer to form a frame.

One of the most important functions of the header and tail is frame delimiting.

(3) Error detection

Symptom: Bit errors may occur during transmission: 1 May become 0, and 0 May become 1.

(4) Reliable transmission

Unreliable transmission: If the receiver detects an error code in the received data, it will simply discard it.

Reliable transmission: the receiver receives what the sender sends.

(5) Broadcast channel

  1. As shown, the host A, B, C, D, E, interconnected by A bus, host A to send data to host C, on behalf of the frame of the signal is transferred through the bus to the bus on the other host, the host B, D, E, how to know the received frame is not sent to them, the host C how to know to send the frame is sent to yourself

Solution: Add the destination address of the frame to the transmission of the frame.

  1. Next is the data collision problem

Switched Lans using point-to-point links and link-layer switches have replaced shared Lans in the wired (local area network) realm. The shared channel technology is still used in wireless LAN.

2. Encapsulate a frame

(1) Encapsulate into frames

1. Frame encapsulation means that the data link layer adds frame header and frame tail to the protocol data unit delivered by the upper layer to make it a frame.

2. Frame sending process

After the data link layer of the sender encapsulates the protocol data unit delivered from the upper layer into frames, it also needs to convert each bit of the frame into an electrical signal and deliver it to the transmission media through the physical layer. Then how does the data link layer of the receiver extract frames one by one from the bit stream delivered by the physical layer?

Frame headers and endframes are required for frame demarcation. The headers and endframes contain important control information.

3. However, not every data link layer protocol frame contains the frame delimiter flag

Leading code explanation:

  • Synchronous code beforeRole is:Synchronize the receiver's clock.
  • Frame start delimiter: indicates that it is immediately followed by a MAC frame

Because the interval between frames is 96 bits, MAC frames do not require frame end delimiters.

(2) Transparent transmission

1. Basic concepts

Transparent transmission means that the data link layer has no restrictions on the transmission data delivered by the upper layer, as if the data link layer did not exist.

2. Existing problems

The frame demarcation flag is a specific data value, and if it happens to be included in the upper-layer protocol data unit, the receiver will not receive it correctly.

As shown in the figure below

The solution

  • Solution: Byte-oriented physical links use byte stuffing or character stuffing. Bit-oriented physical links use the method of bit stuffing to realize transparent transmission.

  • The data link layer at the sending end inserts an escape character “ESC” (whose hexadecimal code is 1B) before the occurrence of a control character in the data.

  • The data link layer at the receiving end removes the inserted escape character before sending the data to the network layer.

  • If the escape character is also present in the data, an escape character ESC should be inserted before the escape character. When the receiver receives two consecutive escape characters, it deletes the first one of them.

Character fill

Bit fill

(3) Description of frame length

  • In order toImprove the transmission efficiency of framesWe should beIncrease the size of the data portion of the frame appropriately.
  • Take into account various factors such as error control, each of whichData link layer protocols all specify an upper limit on the length of the data portion of a frame. namelyMaximum transmission unit MTU.

3. Error detection

Symptom: Bit errors may occur during transmission: 1 May become 0, and 0 May become 1.

Error detection: it is one of the important problems to be solved in data link layer to use error detection code to detect whether there are bit errors in data transmission.

(1) Parity check code

Adds a parity check bit to the data to be sent. Make the number of 1s in the data part odd (odd check) or even (even check).

If error codes occur in an odd number of bits, then parity changes and error codes can be detected. If error codes occur in even bits, the parity does not change and error codes cannot be detected.

(2) CRC cyclic redundancy check code

  • To send and receive the two sidesAgree on a generating polynomial
  • The sender calculates the error detection code (redundancy code) based on the data to be sent and the generated polynomial and adds it to the data to be transmitted.
  • The receiving partythroughGenerate polynomials to calculate the received dataWhether or not error codes have occurred.

(3) Limitations

  • Check wrong words.ifOnly a frame error can be detected during transmissionBut it does not locate the error, soUnable to correct a mistake.
  • To correct errors in transmission, you can useRedundancy information more error correction codes for forward error correction. But error-correcting codes cost a lot and are seldom used in computer networks.
  • The cyclic redundancy check code CRC has good error detection capabilityAlthough the calculation is complicated, butVery easy to implement using hardwareTherefore, it is widely used in data link layer.

Cyclic redundancy check CRC is an error-checking method, while frame check sequence FCS is a redundancy code added to the end of the data.

4. Reliable transmission

Unreliable transmission: If the receiver detects an error code in the received data, it will simply discard it.

Reliable transmission: the receiver receives what the sender sends.

  • Bit errorIt’s just one of those transmission errors.
  • Transmission errors also includePacket loss,Packet disorderAs well asGrouping repeat.

(1) Grouping loss

The router input queue was almost full and actively discarded the received packets.

(2) Grouping out of order

Data does not arrive at the receiving end in the order in which it is sent

(3) Repeat in groups

For some reason, some group stranded in the network, didn’t arrive at the receiving end, which may cause the sender of the packet retransmission on network packet has arrived at the receiving end, retransmission packet reaches the receiver, but after a period of time, in the network packet has arrived at the receiving end, which group repeated transmission error.

5. Reliable transport protocol

Maintain protocols for reliable transport.

5.1 Stop – Wait for the protocol SW

1. Interpretation of the Agreement

When the sender sends a packet to the receiver, the sender will stop sending the next packet and wait for the ACK of the receiver to confirm the packet. If the receiver finds that the received packet contains error code, the receiver will discard it or send NAK to confirm the packet in serious cases. If the packet is discarded, the sender resends the packet when the timeout retransmission timer exceeds the timeout retransmission time. If an NAK acknowledgement packet is received or an ACK acknowledgement packet is lost, the sender resends the packet. Both the receiver and the sender have only one window of size 1.

An illustrative

To prevent group duplication, we need to label the groups.

2. Channel utilization

  • TD: indicates the transmission delay consumed by the sender to send data packets

  • RTT: indicates the round-trip time between the sender and the receiver

  • TA: is the transmission delay consumed by the receiver to send the confirmation packet

3. The shortcomings

  1. whenThe round-trip time RTT is greater than the data frame transmission delayWhen,Channel utilization is extremely low
  2. ifTimeout retransmission occurred.Data utilization should also be reduced

5.2 Rolling back THE N-frame PROTOCOL GBN

1. Interpretation of the Agreement

The size of the sending window ranges from 0 to 7, and the group number ranges from 0 to 7. However, the receiver has only one receiving window (the window size is 1). The sender can send more than one packet, but the receive window can only accept one packet at a time. When a packet is lost or a packet error occurs. All subsequent packets need to be retransmitted.

2. No errors

The sender sends multiple packets, and the window moves forward only when it receives the corresponding ACK acknowledgement packet from the recipient. The receiving party can confirm all the previous groups one by one or accumulative. Cumulative confirmation is the last confirmation of the sequential arrival of the group.

3. Something goes wrong

If the packet sent by the sender is lost, error codes are discarded, or the packet is confirmed to be lost, the sender will retransmit timeout, and all subsequent packets will also be retransmitted.

4. The size of the sending window is described

If the size of the send window exceeds the maximum value, the recipient will not be able to identify the old and new data groups.

5.3 Selecting the retransmission protocol SR

1. Interpretation of the Agreement

The window of the sender in this protocol can send multiple data groups (the window size is 1 to 4). Since the size of the receiving window of the back N frame protocol is 1, the efficiency is very low when the error occurs and the back operation is needed for retransmission. In this protocol, the size of the receive window (greater than 1, less than or equal to the send window, if it is 1, it is equivalent to back N frame protocol), and the receiver must accept the packet by the confirmation. In the case of no error, the sender will move the window only after receiving the corresponding confirmation group. In the case of error, the sender will only retransmit the corresponding confirmation group that does not receive the confirmation group without rollback.

2. No errors

In the case of no error, the sender will not move the window until it receives the corresponding acknowledgement group

3. Something goes wrong

If an error occurs, the sender only retransmits the packet that does not receive the confirmation group, and does not need to roll back.

4. Relevant instructions

6. Point-to-point protocol PPP

1. Point-to-point protocol PPP

A protocol used by the data link layer. Detect errors, not correct them; No serial number, no flow control; Multiple network layer protocols can be supported simultaneously.

2. Main link layer protocol

PPPoE is a link layer protocol used by hosts with broadband Internet access.

3. Relevant frame formats

Main fields:

  1. Flag field: Delimiter of a PPP frame. The value is 0x7E
  2. Address field: The value is 0xFF, reserved
  3. Control field: The value is 0x03, reserved
  4. Frame check sequence field: check bit calculated by CRC

4. Transparent transmission

The implementation of transparent transmission

  1. Byte-oriented asynchronous links: byte padding (insert “escape characters”)

Prefixes the escape character to the associated character

  1. Bit-oriented synchronous link: Bit fill method (insert “bit 0”)

The sender adds zeros after five consecutive ones

The receiver is deleting the zeros after the five consecutive ones

5. Error detection

The receiver directly discards the received data packet with error codes.

7. Media access control

The main problem to be solved in shared channel is how to coordinate the occupation of multiple transmitting and receiving sites for a shared transmission media, that is, media intervention control MAC.

1. Media intervention control

Statically divided channel

  • Frequency division multiplexing
  • Time-division multiplexing
  • Code division multiplexing

Dynamic access control

  • Controlled Access (obsolescence)

    • Centralized control
    • Decentralized control

  • Random access

8. Channel multiplexing technology

(1) Frequency division multiplexing

  1. The whole bandwidth is divided into multiple parts. After users are assigned a certain frequency band, they occupy this frequency band from beginning to end in the communication process.

  2. All users of frequency division multiplexing occupy different bandwidth resources at the same time (note that the “bandwidth” here is the frequency bandwidth rather than the data transmission rate).

(2) TDM

  1. TDM divides time into equal length TDM frames (TDM frames). Each TDM user occupies a fixed serial number of time slots in each TDM frame.

  2. The time slots occupied by each user occur periodically (the period is the length of TDM frames).

  3. TDM signal is also called isochronous signal.

  4. All users of TDM occupy the same bandwidth at different times.

TDM may cause the waste of line resources, so that the utilization rate of the allocated sub-channel is generally not high.

(3) Statistical TDM

(4) Wavelength division multiplexing

(5) Code division multiplexing

  1. The common term is Code Division Multiple Access (CDMA).

  2. Each user uses a specially selected different code type so that it does not interfere with each other.

  3. The signal sent by this system has strong anti-interference ability, and its spectrum is similar to white noise, which is difficult to be detected by the enemy.

9. CSMA/CD protocol

(1) Working principle of the agreement

  1. Multiple access MASaid:Many hosts are connected to a bus by multi-point access.
  2. Carrier sense CS: Is that every person standing atBefore sending the datafirstCheck to see if there are other computers on the bus sending dataIf yes, do not send data temporarily to avoid collisions.

  1. Collision detection: Every station that is sending data, once found on the busThere's a collision, it is necessary toStop sending immediatelySo we don’t waste any more network resources, andWait a random amount of time before sending again.

General working principle diagram

Sending process

Accept the process

(2) Competition period

Collisions can be detected at a maximum propagation time of 2T for the sending host to travel end-to-end round trips over Ethernet, so this time is called the race period.

(3) Minimum frame length

The minimum frame length is set to 64 bytes when the frame cannot be retransmitted due to a collision between a host and the sender after sending the frame. The frame was not sent before the collision. Therefore, any frame less than 64 bytes is invalid.

(4) Maximum frame length

The frame length cannot be too large. Otherwise, the bus is always busy and other hosts cannot send frames.

(5) Channel utilization rate

(6) Importance

  1. Ethernet using THE CSMA/CD protocol cannot carry out full duplex communication but only two-way alternating communication (half duplex communication).

  2. For a short period of time after each station sends data, there is the possibility of a collision.

  3. This uncertainty of transmission causes the average traffic across Ethernet to be much less than the highest data rate of Ethernet.

Ethernet is now based on switches and full duplex connections, with no collisions, so there is no need to use the CSMA/CS protocol.

10. CMSA/CA protocol

Protocol used by wireless LAN.

(1) Working principle of the agreement

The source site sends the first data frame after a DIFS interval when it discovers that the channel is idle, and the destination site receives the data frame after a SIFS interval before sending the confirmation frame. If other sites found channel busy will use retreat retreat algorithm, when the discovery channel and passed a DIFS time interval after will send the frame, the channel is busy, then other sites detected freezing will retreat the timer, then again wait for the countdown to the corresponding idle state.

An illustrative

  1. Why does the source station wait for DIFS for a while after detecting an idle channel?

Consider that there may be other stations with high priority frames to send. If so, let the higher-priority frames be sent first

  1. Why does the destination station wait some time after receiving the data frame correctly before SIFS can send an ACK frame?

SIFS is the minimum frame interval used to separate frames belonging to a conversation, during which time a site should be able to switch from sending to receiving.

  1. After the channel turns from busy to idle and DIFS time passes, there is a random time to back off before the channel can be used?

Prevent collisions when multiple sites send data at the same time.

(2) Channel reservation and carrier monitoring

  1. Why make channel reservation?

Data frames are larger, so collisions are more likely to occur and the overhead is higher. However, RTS frame and CTS frame are relatively small, so the probability of collision is small, and the cost of collision is also small, so the channel reservation is carried out first.

11. The MAC address

A MAC address is an address used by the MAC sub-layer of the Ethernet. It belongs to the data link layer and is also called a physical address or a hardware address.

  • useThe data link layer of a point-to-point channel does not use addresses

  • useThe data link layer of a broadcast channel must use addresses to distinguish hosts

  • On each hostThe sent frame must carry the address identifying the sending and receiving hosts. Due to theThis type of address is used for media access control MAC addresses, soSuch addresses are called MAC addresses.

  • Strictly speaking,A MAC address uniquely identifies an interface on a networkAnd theIt is not a unique identifier for each device on the network.

(1) Unicast

The sender adds its MAC address to the source address and the MAC address of the host to be received to the destination address. After receiving the MAC address, the recipient compares the MAC address with its own. If the MAC address is the same as its own, the recipient accepts the MAC address. If the MAC address is different, the recipient discards the MAC address.

(2) Broadcasting

The sender enters the broadcast address (all F in hexadecimal) in the destination address field at the head of the frame, and its MAC address in the source address field.

(3) Multicast

12. The IP address

IP address is the IP address used by the TCP/IP architecture Internet layer, which belongs to the category of the network layer.

An IP address is an address used by hosts and routers on the Internet to identify two parts of information

  1. The network number:logoMillions on the Internetnetwork.
  2. Host number:logoDifferent on the same networkHost (or router).

Related instructions:

  • If onlyA separate networkWithout access to the Internet, yesJust use the MAC address
  • If the host is on the networkTo access the Internet,Both IP and MAC addresses are required.

(1) Changes of IP address and MAC address during packet forwarding

  1. The source IP address and destination IP address remain unchanged
  2. The source MAC address and destination MAC address change link by link (or network by network).

13. ARP (Address Resolution Protocol)

(1) Relevant instructions

ARP belongs to the Internet layer of the TCP/IP architecture. It is used to obtain the MAC address of a device by knowing the IP address assigned to the device. Belongs to the network layer category.

(2) Working principle of the agreement

The source host searches for the MAC address corresponding to the IP address of the destination host in the ARP cache table. If the source host finds the MAC address, it encapsulates a MAC frame and sends the packet. If not, an ARP request is sent (encapsulated in a broadcast MAC frame). After receiving the ARP request, the destination host records the IP address and MAC address of the source host in its ARO cache table, and then sends an ARP response (encapsulated in a unicast MAC frame) to the source host. The ARP response contains the IP address and MAC address of the destination host. After receiving the ARP response, the source host records the IP address and MAC address of the destination host in its cache table. Then, the source host can encapsulate the MAC address and send it to the destination host.

(3) The scope of ARP

Segment by segment or network by network

14. Differences between hubs and switches

(1) Hub

Hosts connected by a hub. If one host sends a unicast frame, it is transmitted to other hosts on the hub. If a broadcast frame is sent, it is sent to other hosts on the hub. Collisions can occur if multiple hosts send frames together. Hubs expand the broadcast domain and also expand the collision domain.

(2) Switch

A switch can connect multiple smaller Ethernets into one larger Ethernet.

Hosts connected by a switch. If one host sends a unicast frame, it is transmitted to the corresponding destination host. If a broadcast frame is sent, it is sent to other hosts on the switch. The switch expands the broadcast domain but isolates the collision domain.

(3) Illustration

15. The process of Ethernet self-learning and frame sending

Assume that the frame switching table of the Ethernet switch is empty and each host knows the MAC address of another host. When a frame arrives, the Switch registers the frame to improve the frame switching table of the Ethernet switch. This process is a self-learning process. Then it searches the frame exchange table for frame transmission. If there is no corresponding record in the frame exchange table, it will blindly forward (flooding). When the corresponding host sends a response frame, the switch also logs it. Each record has its own validity period and is automatically deleted when it expires. The mapping between MAC addresses and interfaces is not permanent.

Spanning Tree Protocol (STP)

(1) How to improve Ethernet reliability?

Add redundant links. But it can cause network loops.

Problems caused by network loops

  1. The broadcast storm
  2. The host received a duplicate broadcast frame
  3. The switch’s frame switch table flaps

2. Spanning Tree Protocol (STP)

Protocol Principle:

  1. Regardless of the physical connection between switches, switches can automatically calculate and build a network that has no logical loop. The logical topology must be tree (no logical loop)

  2. The tree logical topology of the final spanning tree ensures that the entire network is connected.

17. Virtual LAN VLAN

(1) Why to introduce virtual LAN VLAN?

  1. The Ethernet switch works inData link layer (also physical layer)
  2. useSwitched Ethernet with one or more Ethernet switches interconnected, all of its sitesBelongs to a broadcast domain.
  3. With the increase of broadcast domain, there are many disadvantages:Broadcast storm, difficult to manage and maintain, potential security issues.

Routers can isolate broadcast domains, but at a high cost.

(2) Virtual LAN VLAN

concept

Is a technique for dividing devices on a local area network into logical groups independent of physical location that have certain common requirements. Each VLAN is a broadcast domain.

(3) Relevant implementation mechanism

Virtual LAN VLAN technology is implemented on the switch, which needs to be able to achieve the following functions

  1. Capable of processing frames with VLAN tags — IEEE 802.1Q frames

  2. Ports on the switch support different types of ports. Ports of different types process frames differently.

1.Access port: connects the switch to the user’s computer

2.Truck ports: Interconnect between switches or between switches and routers

3.Hybrid port: Used for interconnection between switches, between switches and routers, and between switches and users’ computers.