Chapter 3 - data link layer

​

3.1 Functions of data link layer

The data link layer provides services to the network layer based on the services provided by the physical layer . Its main function is to strengthen the function of the physical layer to transmit the original bit stream , Transform the possible error physical connection provided by the physical layer into a logically error free data link , Make it an error free link to the network layer .

3.2 What is a frame

A frame is a protocol data unit of the data link layer , The protocol data unit of the network layer is IP The datagram （ Also called datagrams or packets 、 package ）, The data link layer passes down the network layer IP Datagrams are encapsulated into frames , At the same time, the IP The datagram is handed over to the network layer .

3.3 Package into frames

Add the first part and the last part of the packets passed down from the network layer , Used to mark the beginning and end of a frame . The frame length is equal to the length of the data part plus the length of the head and tail . The head and tail contain a lot of control information , One of their important functions is frame delimitation .

3.4 Transparent transmission

If the same bit combination as the frame delimiter happens to appear in the data ( Will mistake for “ End of transmission ” And discard the following data ), Then we must take effective measures to solve this problem, namely transparent transmission . In short , Transparent transmission means that no matter what kind of bit combination the transmitted data is , Should be able to transmit on the link .

3.4.1 Framing

The reason why the data link layer combines bits into frames for transmission , In order to retransmit only the wrong frame when there is an error , Instead of resending all the data , To improve efficiency . In order to enable the receiver to correctly accept and check the transmitted frame , The sender must package the packets submitted by the network layer into frames according to certain rules, which is called framing . Framing mainly solves frame delimitation 、 Frame synchronization 、 Transparent transmission and other issues ; There are four framing methods ：

Character counting

​​
Character counting refers to using a counting field in the frame header to indicate the number of characters in the frame . When the data link layer of the destination node receives the byte count value, it knows the following bytes , So as to determine the position at the end of the frame .

The biggest problem with this approach is that if the count field goes wrong , That is, the basis of frame boundary division is lost , Then the receiver cannot judge the end bit of the transmitted frame and the start bit of the next frame , Can't sync .

The beginning and end delimiter method of character filling

Character filling method uses specific characters to delimit the beginning or end of a frame , In the diagram above ‘SOH’ Represents the beginning of a frame ,‘EOT’ Represents the end of a frame . If... Appears in the frame EOT That is, a certain bit stream data in the data exactly overlaps with the tag field. The solution is as follows ;

In order to prevent the special character appearing in the information bit from being misjudged as the beginning and end delimiter of the frame , You can fill in an escape character before a special character (ESC) To distinguish , To realize the transparent transmission of data . After receiving the escape character, the receiver will know that the data information is immediately followed , Instead of controlling information .

Zero bit filling head and tail marking method

The zero bit filling method allows the data frame to contain any number of bits , The encoding of each character is also allowed to contain any number of bits . It uses a specific bit pattern , namely “01111110” To mark the beginning or end of a frame , In order to prevent misjudgment , Every time the sender data encounters 5 A continuous 1 A is automatically inserted after it 0; The receiver only needs to reverse the operation .

The zero bit filling method is easy to implement by hardware , Performance is better than character filling method .

Illegal coding

Because the Manchester code does not use high - high , low - Low to indicate , So if you use high - high , low - Low indicates that the start and end of the frame will not conflict with the data .

Due to the fragility of technical fields in byte counting method and the complexity and incompatibility in the implementation of character filling method , At present, the commonly used framing methods are bit filling method and illegal coding method

3.5 Error control

Due to channel noise, etc , Errors may occur in the transmission of frames . The method used by the sender to determine whether the receiver has correctly received the data sent by it is called error control .

Coding technology is usually used for error control , There are two main categories ： Automatic retransmission request ARQ— stay ARQ In the way , When the receiving end detects an error , Try to notify the sender to resend , Until it's right . Forward error correction FEC— stay FEC In the way , The receiver can not only find errors , And the error position of the bit string can be determined , So as to correct . therefore , Error control can be divided into error detection coding and error correction coding .

Error detection code

Redundancy coding technology is adopted for error detection coding , The core idea is that before effective data is sent , First attach a certain redundancy bit according to a certain relationship , Form a codeword that conforms to a certain rule and then send .

1. Parity code

If it's an odd check code , It consists of n-1 Bit information elements and 1 Bit check element composition , After attaching a check element 1 The number of is odd ;
If it's even check code , After attaching a check element 1 The number of is even .

2. Cyclic redundancy code （Cyclic Redundancy Code,CRC）

Any code composed of binary bit strings can be compared with a code containing only 0 and 1 The polynomials of the two coefficients establish a one-to-one correspondence

Generating polynomial if ：1101, Its polynomial form

Sending process at the sending end ↑

The receiving end accepts the process ↑

All frames received by the data link layer are error free by default .

Error correction encoding

The most common error correction code is Hamming code , Its principle is to add several check bits to the information effective bits to form Hamming code , Each binary bit of Hamming code is allocated to several parity groups . When someone makes a mistake , This will cause the values of several check bits to change , This can not only find dislocation , And can point out the position of dislocation .

4. error correction ＆ Error detection

3.6 flow control

Due to the difference of working rate and cache space between the sender and the receiver , The sending capacity of the sender may be greater than the receiving capacity of the receiver , If not limited , The received frame will be replaced by subsequent frames “ Flood ” Cause an error , Therefore, flow control is necessary .
Flow control involves the control of the transmission rate of frames on the circuit , So that the receiver has enough buffer space to receive each frame . for example , In the face of real automatic transmission request system , When the quantity to be confirmed increases , It is possible to exceed the buffer storage space and cause overload . The basic method of flow control is that the receiver controls the rate of sending data , There are two common ways ： stop it - Waiting for agreement *** and *** Sliding window protocol .

stop it - Waiting for agreement

​ On the premise of full duplex , Every frame sent by the sender , Wait for the response signal from the receiver , Then send the next frame . Can effectively solve bit errors 、 Underlying data packet loss 、 Flow control problems .

Channel utilization

stop it - Waiting for protocol features ： Simple ; Low channel utilization

Sliding window protocol

Basic principle of sliding window flow control

At any moment , The sender maintains a continuous sequence number of allowed frames , It's called the send window ; At the same time, the receiver also maintains a set of consecutive sequence numbers of frames that are allowed to be accepted , It's called the receiving window ; The protocol allows the sender to send multiple data packets before stopping and waiting for confirmation . Because the sender doesn't have to stop for confirmation every time a packet is sent . So the protocol can speed up the data transmission , Improve network throughput .

back off N Frame protocol （GO BACK-n,GBN）

GBN Three things the sender needs to respond to ：

1. The call of the upper layer ： When the upper layer wants to send data , The sender checks whether the sending window is full ; If the full , The sender only needs to return the data to the upper layer , Indicates that the upper window is full . The upper layer will send it later .
2. Received a ACK：GBN Agreement , Yes n The confirmation of frame No. 1 indicates that the receiver has received... By means of cumulative confirmation n Frame number and all frames before it .
3. Timeout Events ： If there is a timeout , The sender retransmits all confirmed frames of a relaxation unit .

GBN What the receiver has to do

1. If received correctly n Frame number , And in order , The recipient is n The frame sends a ACK, And deliver the data part of the frame to the upper layer .
2. Frames are discarded in other cases , And resend the most recently received frames in sequence ACK
   
   GBN The length of the window
   
   GBN summary
   

Choose retransmission protocol （selective repeat protocol ,SR）

In order to further improve the channel utilization

SR Three things the sender has to respond to

1. The call of the upper layer ： After receiving data from the upper layer ,SR The sender checks the next sequence number available for the frame , If the serial number is in the send window , Then send the data frame ; no It's like GBN equally , Or cache the data , Or return to the upper layer and then transmit .
2. Received a ACK： If you receive ACK, Add the frame number in the window , be SR The sender marks the acknowledged frame as received . If the frame number is window Lower bound of （ The sequence number corresponding to the first window on the far left ）, Then the window moves forward to the unacknowledged frame with the smallest sequence number . If the window moves
And there are unsent frames with sequence numbers in the window , Then send these frames .
3. Timeout Events ： Each frame has its own timer , Only one frame is retransmitted after a timeout event .

SR What the receiver has to do

• All's fish that comes to his net （ For windows ⼝ Frames within ）：SR The receiver will confirm a correctly received frame regardless of whether it is in order . Out of order frames will be cached , And return a confirmation frame of the frame to the sender 【 Who receives it confirms who 】, Until all frames （ That is, frames with smaller sequence numbers ） All received , At this time, a batch of frames can be delivered to the upper layer in order , Then move the sliding window forward .
  
  SR Protocol sliding window length
  
  SR summary
  

3.7 Media access control

The main tasks of media access control ： Isolate signals transmitted from other nodes on the same channel for each node using the medium , To coordinate the transmission of active nodes .

3.7.1 Channel partition media access control （ Static division channel ）

Channel division media access control isolates each device using media from communication from other devices on the unified communication channel , The time domain and frequency domain resources are reasonably allocated to the devices on the network .
Multiplexing technology
Multiple signals are combined on a physical channel for transmission , Make multiple calculations Computers or terminal devices share channel resources , Improve channel utilization .

Frequency division multiplexing （Frequency-division multiplexing,FDM）

Frequency division multiplexing (FDM) is a method of modulating multiple baseband signals onto different frequency carriers , Multiplexing technology of superimposing to form a composite signal .

Time division multiplexing （Time-Division Multiplexing,TDM）

Time division multiplexing is to divide a physical channel into several time slices according to time , Assign to multiple signals in turn . Each time slice is occupied by a multiplexed signal , At some point ,TDM What is uploaded is only a signal between a certain pair of devices ; But for some time , It transmits multiplexed signals divided by time .

Due to the burst of computer data , A user's utilization of the allocated subchannels is generally not high . Statistical time division multiplexing （Statistical Time-Division Multiplexing,STDM） emerge as the times require ; It is TDM Improvement , use STDM frame ,STDM Time slots are not fixed , And dynamically allocate time slots on demand , When the terminal has data to transmit , Will be assigned to the time slice , Therefore, the utilization rate of the line can be improved .

Wavelength division multiplexing （Wave-Division Multiplexing, WDM）

Code division multiplexing （Code-Division Multiplexing,CDM）

3.7.2 Random access media access control

ALOHA agreement

When any site in the network needs to send data , You can send data without any detection . If a confirmation is received within a period of time , Then the site considers that there is a conflict in the transmission process . The result of a collision is ： Both sides must retransmit ;ALOHA The strategy adopted by the protocol is to make each station wait for a random period of time for retransmission . If the collision happens again , Continue retransmission .

Timeslot ALOHA agreement

Timeslot ALOHA The protocol synchronizes all stations in time , The time is divided into time slots of equal length （Slot）, It is specified that only one frame can be sent at the beginning of each time slot . Thus, the randomness of sending data by users is avoided , Improved channel utilization .

CSMA agreement （Carrier Sense Multiple Acess）

1- insist CSMA
Persistence refers to the persistence after the listening channel is busy .
1- insist CSMA thought ： If a host wants to send a message , Then it listens to the channel first .

• When idle, it is transmitted directly , Don't wait for .
• Keep listening when you're busy , Transfer until idle .
  If there is a conflict （ No positive reply has been received for some time ）, Then wait a random long time before listening , Repeat the process .
• advantage ： As long as the media is free , The site will send it right away , Avoid the loss of media utilization .
• shortcoming ： If two or more sites have data to send , Conflict is inevitable .

Non insistence CSMA
Non persistence means not to continue listening after the listening channel is busy .
Non insistence CSMA thought ： If a host wants to send a message , Then it listens to the channel first .

• When idle, it is transmitted directly , Don't wait for .
• Busy, wait for a random time before listening .

shortcoming ： It may be that everyone is in the process of delaying waiting , Make it possible for the media to remain idle , Reduced media usage .

p- insist CSMA

p- insist CSMA thought ： If a host wants to send a message , Then it listens to the channel first .

• When you are free, use p Probability direct transmission , Don't wait for ; probability 1-p Wait until the next time slot before transmitting .
• If busy, continue to listen until the channel is idle, and then continue to listen with p Probability transmission .
• If the channel is still idle in the next slot , So still with probability p send data , With 1-p Postpone to the next time slot until the transmission is successful or busy .
• If busy, postpone to the next time slot to continue listening .
• 

CSMA/CD agreement （Carrier Sense Multiple Acess With Collection Detection）

CSMA/CD Agreement is CSMA Improvement scheme of the agreement , Suitable for bus type half duplex network . Listen before sending , That is, before each station sends data, it must first detect whether other stations on the bus are sending data , If yes, it will not be sent for the time being , Wait for the channel to become idle before sending .CD—collision detection“ collision detection ” Is to listen while sending , That is, the adapter detects the voltage change on the channel while sending data , So as to judge whether others are sending data when sending data .

Retransmission timing after collision


The minimum frame length is selected

CSMA/CA agreement （Carrier Sense Multiple Acess With Collision Avoidance）

Due to the reasons in the above picture ,802.11 The standard defines the standards that are widely used in wireless LANs CSMA/CA agreement , Change collision detection to collision avoidance .“ Collision avoidance ” It does not mean that the agreement can completely avoid collision , It means that the protocol should be designed to minimize the probability of collision . because 802.11 WLAN doesn't use collision detection, so once the site starts sending a frame , The frame will be sent completely , However, the whole data frame is still sent when collision exists , It may reduce the efficiency of the network .

CSMA/CD And CSMA/CA The difference between

Polling access media access control ： Token passing protocol

3.8 LAN （Local Area Network, LAN）

LAN (LAN) It refers to a small geographical area , Put all kinds of computers 、 External equipment and database system are connected through twisted pair 、 Coaxial cables, etc. are connected together , The computer Internet that forms resources and information sharing .
The main factors that determine the LAN are ： Network topology , Transmission medium and medium access control method .

3.8.1 LAN topology

3.8.2 LAN propagation media

• Common media of wired LAN ： Twisted pair 、 Coaxial cable 、 Optical fiber .
• Common media of wireless LAN ： electromagnetic wave .

3.8.3 Medium control method of LAN

1. CSMA/CD： Commonly used in bus LAN , It is also used in tree networks .
2. Token bus ： Commonly used in bus LAN , It is also used in tree networks .
3. Token ring ： For ring LAN , Such as token ring network .

3.8.4 The classification of LAN

1. Ethernet ： Ethernet is the most widely used LAN , Including standard Ethernet （10Mbps）、 Fast with （100Mbps）、
   Gigabit Ethernet （1000Mbps） and 10G Ethernet , They all fit IEEE802.3 Series of standard specifications . Logical topology master line , Physical topology is star or extended star . Use CSMA/CD.
2. Token ring network ： Physically, star topology is adopted , Logically, it is a ring topology . Already “ chrysanthemums after the double ninth festival ”.
3. FDDI network ： Physically, the double ring topology is adopted , Logically, it is a ring topology .
4. ATM network ： Newer switching unit technology , Use 53 Byte fixed length units are exchanged .
5. WLAN ： use IEEE 802.11 standard .

3.8.5IEEE802 standard

IEEE 802 The series standard is IEEE 802 LAN/MAN LAN developed by the Standards Committee 、 Technical standard of man （1980 year 2 Month set up ）. One of the most widely used is Ethernet 、 Token ring 、 WLAN, etc . Each sub standard in this series of standards is in the charge of a special working group in the Committee .

LAC Sublayer and MAC Sublayer

3.9 Ethernet （Ethernet）

Ethernet provides no connection 、 Unreliable service ：

• There is no connection ： There is no communication between sender and receiver “ Handshake process ”.
• unreliable ： The data frame number of the sender is not , The receiver does not confirm to the sender , Error frames are discarded directly , Error correction is the responsibility of senior management .

The development of Ethernet transmission media and topology

10BASE-T Ethernet

Ethernet MAC The frame format

V2 Standards and IEEE802.3 The difference between ：

1. The third field is length / type .
2. When the length / type <0X0600 when , The data field must be loaded LCC Sublayer .

High speed Ethernet

3.10 IEEE 802.11（ Wireless LAN communication standard ）

3.10.1802.11 Of MAC Frame header format

3.10.2 WLAN with fixed infrastructure

3.10.3 Ad hoc network without fixed infrastructure WLAN

3.11 Wide area network （Wide Area Network,WAN）

A wide area network usually consists of two or more local area networks . The computer uses the equipment provided by the operator as the information transmission platform . For example, through the public network , Such as the telephone network 、 Fiber optic connection to Wan , It can also be connected by special line or satellite . The Internet is the largest wide area network at present .

3.11.1 PPP agreement （Point To Point）

Point to point protocol （Point to Point Protocol,PPP） It provides a standard method for uploading and transporting multi protocol packets in point-to-point connection .PPP It was originally designed for... Between two peer nodes IP Traffic transmission provides a encapsulation protocol （ Establish a point-to-point connection to send data through dial-up or private line ）.
Point to point protocol PPP（Point-to-Point Protocol） It is the most widely used data link layer protocol , When users use dial-up phones to access the Internet, they usually use PPP agreement .
Only full duplex links are supported .PPP The protocol is byte oriented .

PPP Requirements to be met by the agreement

PPP Part of the agreement

Link control protocol （LCP）. An extended link control protocol , For building 、 To configure 、 Test and manage the data link .
Network control protocol （NCP）.PPP The protocol allows multiple network layer protocols to be adopted at the same time , Each different network layer protocol should use a corresponding NCP To configure the , Establish and configure logical links for network layer protocols .
One will IP A method of encapsulating data packets into a serial link .IP The packet is in PPP The frame is its information part , The length of this information part is affected by the maximum transmission unit MTU The limitation of .

PPP Frame format

3.11.2 HDLC agreement （High-level Data Link Control）

HDLC yes ISO To formulate the Bit oriented Data link layer protocol . The protocol does not depend on any character encoding set ; Data message can be transmitted transparently , For transparent transmission “0 Bit insertion method ” Easy to implement in hardware ; Full duplex communication , It has high data link transmission efficiency ; use CRC test .

HDLC The station of

• The master station is responsible for controlling the operation of the link , The sent frame is called the command frame .
• The slave station is controlled by the master station , Operate according to the command of the master station ; The sent frame is called the response frame .
• It has the function of master station , It also has the function of slave station , Such frames are called composite stations . It can send both command frames and response frames

HDLC Frame format

3.11.3 HDLC Deal with the PPP Protocol comparison

3.12 Data link layer devices

3.12.1 The concept and basic principle of network bridge

A bridge is also called a bridge , It's a storage that connects two LANs / Forwarding device , It can turn a big LAN Split into multiple segments , Or more than two LAN Interconnection is a logic LAN, send LAN All users on can access the server . After two or more Ethernet are connected through a bridge , It becomes an Ethernet with greater coverage , The original Ethernet becomes a network segment . Bridge works in MAC Sublayer , It can make each Ethernet segment an isolated collision domain, also known as the collision domain .

Transparent bridge （ Not the best route ）

• If the source LAN And purpose LAN identical , Then discard the frame .
• If the source LAN And purpose LAN Different , Then forward the frame .
• If the purpose LAN Unknown , Then spread the frame .

Source routing bridge （ Choose the best route ）

A discovery frame is sent by broadcast for detection .

3.12.2 LAN switch

The main limitation of the bridge is that it can only forward one frame at any time , So there are LAN switches , Also known as Ethernet switch ; Ethernet switch is a multi port bridge , It works at the data link layer . Switches can economically divide the network into small conflict domains , Provide higher bandwidth for each workstation

Two LAN switches

Conflict domain and broadcast domain