data link layer

function

Provide services for network layer

Be careful ： If there is a connection, there must be confirmation

• No connection service without confirmation ： Ethernet
• Confirmed connectionless service ： wireless communication
• Connection oriented service with acknowledgement ： For occasions with high communication requirements

Framing

It mainly solves frame delimitation 、 Frame synchronization and transparent transmission . Because of the fragility of counting field in character counting method and the complexity and incompatibility of character filling method , Currently used Bit filling method and illegal coding method

Transparent transmission ： No matter what bit combination the transmitted data is , Should be able to transmit on the link

• Character counting ： A count field is used in the frame header to indicate the number of characters in the frame
• Character filling ： Use special characters to mark the beginning and end of a frame , Use escape characters to achieve transparent transmission
• First sign method of zero bit filling ： Use 01111110 To mark the beginning and end of a frame , Encountered... In the data section 5 A continuous "1" Will automatically add a... After it "0"
• Illegal coding ： The illegal coding sequence is used to mark the beginning and end of the frame , LAN IEEE802 The standard uses this method

Error control

• Parity code ： additional 1 After the check bit of bit , In codeword "1" The odd number of is called odd check ; In codeword "1" The even number of is called even check
• Cyclic redundancy code (Cyclic Redundancy Code,CRC)： It has the functions of error detection and correction
• Hamming code ： Error detection x position , Yardage >=x+1; error correction x position , Yardage >=2x+1

flow control

• Flow control between nodes （ Pay attention to the traffic control of the transport layer ）

Stop waiting

• Every time the sender sends a frame of data , You must wait for the receiver's reply signal before sending the next frame
• Every time the receiver receives a frame of data, it must feed back a response signal to the sender

The sliding window

• Send window ： The sequence number of a group of consecutive frames that the sender allows to send
• Receiving window ： The sequence number of a group of consecutive frames that the receiver is allowed to receive . The receiver will discard the frame whose frame sequence number is not within the receiving window
• Window movement ： Only the receiving window moves forward （ At the same time, an acknowledgement frame is sent ） when , Send window is possible （ It is only when the sender receives the acknowledgement frame ） Move forward
• The window size of the data link layer is fixed during transmission （ Note the difference from the transport layer ）

Reliable transmission

explain ： The data link layer of actual wired network seldom adopts reliable transmission

• Flow control and reliable transmission are intertwined
• Use confirm and Over time retransmission Two mechanisms to ensure reliable transmission , The commonly used protocol to ensure reliable transmission is the automatic retransmission request protocol (Automatic Repeat reQuest,ARQ). There are three types of traditional automatic retransmission requests , Stop equation （Stop-and-Wait）ARQ, Back off N frame （Go-Back-N,GBN）ARQ, And selective retransmission （Selective Repeat）ARQ. The latter two protocols are the combination of sliding window technology and request retransmission technology , Because the window size is large enough , Frames can flow continuously on the line , Therefore, it is also called continuous ARQ agreement .

stop it - wait for ARQ

• The sender is sending 1 After frame data , You must wait for the confirmation frame sent by the receiver , If for a while （ The timer timed out ） The confirmation frame has not been received yet , The sender sends the same data frame again .
• The transmitted frames are alternately 0 and 1 To mark , The confirmation frames are respectively ACK0 and ACK1 To express .
• The size of both sending and receiving windows is 1

back off N frame ARQ

• The sender sends data frames consecutively , The receiving party By receiving order And carry on Cumulative confirmation , If the sender sends a frame for a period of time （ The timer for this frame timed out ） No confirmation after , Then the sender will retransmit the frame and all subsequent frames .
• If the n Bit to frame number , be W_T ≤ 2ⁿ-1, If it is greater than 2ⁿ-1, The receiver will not be able to distinguish between the new frame and the old frame . Confirmation sent by the receiver ACKx Indicates that the... Has been correctly received x Frame number and all previous frames , Next time I hope to receive the x+1 Frame number （ It could be the 0 Frame number ）
• Send window 1 < W_T ≤ 2ⁿ-1 , Receiving window W_R = 1

Choose retransmission ARQ

• The sender sends data frames consecutively , The receiver can receive multiple data frames , And the received data of each frame is analyzed Confirm separately , If the receiver finds that there is a problem with the data of a frame , A negative frame will be sent NAK To the sender . If a certain frame of the sender （ The timer for this frame has timed out ） No confirmation or receipt after NAK, Then the sender will resend the frame
• Generally, the size of the sending window and the receiving window are the same （ Sending window larger than receiving window will cause overflow , It makes no sense that the sending window is smaller than the receiving window ）, If the n Number the frames , be W_T = W_R ≤ 2^n-1 , If this condition is not met , When the acknowledgement frame is lost , The sender retransmits the previous data frame , The receiver will not be able to tell whether it is a new data frame or a retransmitted data frame
• Send window and receive window ：1 < W_T = W_R ≤ 2ⁿ-1

Media access control （Media Access Control,MAC）

• Isolate signals transmitted from other nodes on the same channel for each node using the medium , To coordinate the transmission of active nodes
• The common media access control methods are channel partition media access control 、 Random access media access control and polling access media access control , The former is the method of static channel division , The latter two are dynamic channel allocation methods

Channel partition media access control

• Multiplexing technology ： In order to make full use of the transmission media , The technique of establishing multiple communication channels on a physical line

Frequency division multiplexing （FDM）

• The multi-channel baseband signals are modulated to carriers of different frequencies , The technique of superimposing modulated signals and transmitting them in a transmission medium （ That is, the transmission medium is divided into multiple non-interference channels according to frequency ）

Time division multiplexing （TDM）

• The transmission medium is divided into several time slices according to time , Transmit different signals in each time slice
• Synchronous time division multiplexing ： Whether or not the device has data to send , All occupy a fixed time slice
• Asynchronous time division multiplexing （ Statistical time division multiplexing ）： Dynamically allocate time slices , Time slice is allocated only when the device has data to send

Wavelength division multiplexing （WDM）

• That is, optical frequency division multiplexing technology , Optical signals of different wavelengths are transmitted here , Finally, each wavelength is decomposed by wavelength demultiplexer

Code division multiplexing （CDM）

• S And T Normalized inner product of ：$$S\cdot T=\frac{1}{n}\sum _{i=1}^n{S}_i{T}_i$$
• Each site is assigned a unique m(64 or 128) Bit chip sequence ( In sequence 0 use -1 Express ), The chip sequences of different sites are orthogonal to each other （ The normalized inner product is 0）
• When sending 1 when , Just send its chip sequence ; send out 0 The inverse code of the chip sequence is sent . If multiple sites send at the same time , Each chip sequence is linearly added in the channel .
• When decoding , Let the chip sequence received by the receiver be S, The chip sequence of the sender is T, Calculation S And S-T Normalized inner product of

Random access media access control

ALOHA agreement

• pure ALOHA agreement ： Send directly without detection , No confirmation means conflict , Conflict waiting for resend
• Timeslot ALOHA agreement ： Send data at the beginning of time slot , No confirmation means conflict , Conflict waiting for resend . Timeslot $T_0$ Each frame can be sent in exactly one time slot .

CSMA agreement （Carrier Sense Multiple Access）

• 1- insist CSMA： Listen to the channel first , If the channel is idle, it will be sent immediately ; If the channel is busy, continue listening until the channel is idle ; If there is a conflict, wait randomly for a period of time before listening to the channel again
• Non insistence CSMA： Listen to the channel first , If the channel is idle, it will be sent immediately ; If the channel is busy, wait for a period of time before listening ; If there is a conflict, wait randomly for a period of time before listening to the channel again
• p- insist CSMA： For time division channel , First, listen for the channel at the beginning of the time slot , When the channel is idle, the probability is p send out , With probability 1-p Put it off to the next slot ; If the channel is busy, continue listening at the beginning of the next time slot until the channel is idle ; If there is a conflict, wait randomly for a period of time before listening to the channel again

CSMA/CD agreement （Carrier Sense Multiple Access with Collision Detection）

• Suitable for bus network or half duplex network
• Listen first, then send , Listen and hair , Cessation of conflict , Random resend
• Minimum frame length = Bus propagation delay $\times$ Data transfer rate $\times$ 2
• Any station that receives a frame shorter than the minimum frame length will discard it , Because a conflict occurred during the contention period
• Binary exponential backoff algorithm ：
  （1） Determine the basic retreat time , The contention period
  （2） Defining parameters k, It is equal to the number of retransmissions but not more than 10,k = min[ Number of retransmissions ,10]
  （3） from [0,1,……,$2^k$-1] Select a number at random r, The retreat time is r Times the basic escape time
  （4） When re communicating 16 The first time was still unsuccessful , Discard this frame , And report the error to the senior management

CSMA/CA agreement （Carrier Sense Multiple Access with Collision Avoidance）

• Suitable for WLAN

Polling access media access control

Token passing protocol

• Applicable to ring bus , The physical topology does not have to be a ring , Logically it must be a ring
• When the network is idle , In the loop, only token frames are passed in a loop
• When a token is passed to a site that has data to send , The site modifies a flag bit in the token , And attach the data to be transmitted to the token , Turn the token into a data frame and send it out
• Data frames are transmitted along the loop , The receiving station views the destination address of the frame while forwarding the data , If the destination address is the same as your own address , The receiving station copies the data frame for further processing
• Data frames are transmitted along the loop , Until reaching the sending station . After receiving the frame sent by itself, the sending station will not forward it , meanwhile , Check whether the data transmission process is wrong by checking the returned frame , If there is an error, it will be retransmitted
• After the sending station transmits the data , Regenerate a token , And pass it to the next site

LAN

Wide area network

Data link layer devices

bridge

Switch