Shulou(Shulou.com)06/01 Report--

II. Important functions of the data link layer

(1) dividing the boundaries of frames (frame synchronization)

Method 1: character counting (character-oriented)

A counting field is used at the head of the frame to represent the number of characters (including themselves) in the entire frame.

How it works: the first character received by the receiver is put into the counter, and then each character received reduces the value of the counter by one. When the counter is reduced to 0, the frame ends and the next frame begins.

Advantages: the receiving mechanism is simple.

Disadvantages: the demarcation of each frame depends on the previous frame. Once a frame delimiting error occurs, the subsequent frame cannot be delimited.

Method 2: first character demarcation with character filling (character-oriented)

Mark the beginning of the frame with DLE STX and the end of the frame with DLE ETX

In order to prevent the DLE in the data from being mistaken for the start and end flag, double the DLE when it appears in the data.

Advantages: each frame is delimited separately, and an error in one frame will not affect the following frames.

Disadvantages: the channel is wasted, the receiver can not use the counter to judge whether it is over or not, and the processing is complex (the sender needs to scan the effective data to prevent dle from appearing in the frame).

Method 3: head-tail mark demarcation method with bit filling (character-oriented)

Use "01111110" to identify the beginning and end of a frame

In order to prevent the "01111110" in the data from being mistakenly regarded as the start and end sign, it is necessary to add a "0" to every 5 ones in the data.

For example: 0111111001101111101011111000101111110

The advantages and disadvantages are the same as the second method.

Method 4: physical layer coding violation method (character-oriented)

Is suitable for physical layer coding redundant networks (such as Manchester coding continuously high level or continuous low level is redundant coding (2) error control

The main contents are as follows: 1. The form of error occurrence: random, several consecutive bursts.

2. Causes of errors: disturbed by noise (changes in electrical characteristics, signal reflection, crosstalk, start and stop of high-power electricity (such as sudden high current when fluorescent tubes are turned on))

3. The form of error:

Error in frame (including sending frame and response frame): the recipient received it, but the data is invalid

Loss of frames (including sending and response frames): not received by the recipient

4. the purpose of error control: to ensure that the frame is correct and submit it to the upper layer in order (to ensure that it is submitted in the original correct order sent by the sender).

5. Error control methods:

In theory, error control is divided into automatic error correction and error detection feedback aggravating mechanism. In the actual network, the second one is the most widely used, that is, the receiver detects the error first, and then the receiver gives feedback by the way of positive response. For the sender, once the timer expires, the data is retransmitted.

The following is a theoretical analysis of the error detection or correction mechanism.

If a frame wants to send m-bit data, in order that errors in the m-bit data can be found, it is necessary to add r-bit parity bits, which are redundant bits that are not directly related to the data. the increase of parity bits will increase the pressure on the network channel. We usually call the data of mechr a codeword.

If enough parity-check bits are added to a data, so that the receiver knows not only that there is an error, but also which bits are wrong, this kind of code is called error correction code (error-correcting code). However, if redundant bits are added to let the receiver know that there is an error, but do not know what has happened, the only way to request a retransmission is called error detection code (error- decting code).

Obviously, in order to achieve the same error detection rate, error correction codes (parity codes, with one bit after each bit of data) add more redundant bits than error detection codes (hamming codes, with 4 bits after every 7 bits of data). That is, it takes a long time to occupy the channel.

In the data link layer of computer networks, the most frequently used method is called cyclic redundancy check (CRC).

6. Cyclic redundancy check (CRC, polynomial coding)

For example: data 110001, expressed as a polynomial: X ^ 5 + x ^ 4 + 1

Before sending data, both sides of the communication should agree on a generating polynomial G (x) (defined at the time of the formulation of the data link layer protocol), whose highest and lowest bits must be 1, which must be shorter than the corresponding polynomial of the transmission information.

The basic idea is that the r bit added by CRC is the error detection code (checksum), added at the end of the frame, and if the convention is satisfied: after adding the redundant bit of r bit, the whole polynomial n bit (MCRR bit) can be divisible by the generated polynomial G (x).

CRC code algorithm:

Let the generating polynomial G (x) be of order r, and add r zeros (shift r bit to the left) at the end of the frame, so that the frame is mendr bit, and the corresponding polynomial is x ^ RM (x).

Use the bit string of the corresponding G (x) to remove the bit string corresponding to x ^ RM (x) by modulo 2 division.

Subtract the remainder (equal to or less than r bits) from the bit string corresponding to x ^ RM (x) by modular 2 division, resulting in a polynomial T (x) with a checksum to be transmitted.

That is: t (x) = x ^ RM (x) + {x ^ RM (x) MOD2 G (x)}

Why would CRC add a checksum to the tail? According to the principle of the algorithm, the addition of CRC to the tail can be sent while calculating, which is helpful to improve the processing capacity.

The error detection rate of CRC is not 100%, and when the error bit string happens to be divisible by the generated polynomial, the error cannot be detected.

(3) flow control

1. How is the data sent?

For the sender, when the upper layer requires the data link layer to transmit data, the sender of the data link layer constructs the data into a frame (the protocol data unit of the data link layer). It should be noted that the data is passively accepted by the lower layer, and these frames are not sent directly to the upper layer, but are stored in the cache and then sent. When the confirmation frame is sent successfully, the data in the cache can be deleted.

For the receiver, there is also a cache, because the data must be correct when it is submitted to the high level, so a checksum needs to be calculated in the cache to ensure that the data is correct. Secondly, it needs to be submitted in order, and if it is sent in segments, it can not be submitted to the upper layer until all the frames have arrived and merged. When the data is correctly sent to the high level and acknowledges receipt, the data in the cache can be deleted.

If the mechanism of positive reply plus timeout retransmission is used for error detection and recovery, when will the reply of data be sent? A reply is generated only after the data is submitted to the high-level buffer to clear.

2. Different layers solve different problems of flow control.

H represents the host and R represents the router.

Flow control mainly solves the problem that the receiver does not have enough capacity to process data due to the mismatch of the processing capacity of the transceiver.

For the data link layer, it mainly solves the problem of two points (point to point) in which a physical link is directly connected, and the network layer solves the problem from source node to destination node. the transport layer is to solve the problem between the source host and the destination host (end-to-end). Although each level deals with different problems, the way of dealing with them is more or less the same.

3. Basic methods of flow control.

(1) Simplex stop and wait agreement (ideal)

Suppose the ideal situation: the communication is based on simplex channel transmission, the sender and receiver are fixed and work endlessly (the sender has unlimited information to send, the receiver's buffer is infinite), and the transmission rate is lower than the reception rate. The communication line does not damage the frame without loss of information. (no mistake)

Working process:

Sending process: getting data, forming frames, sending frames

Receiving process: waiting, receiving frame, sending data to high level

(2) Simplex stop and wait agreement (error-free)

Add constraints: the receiver cannot receive endlessly (for example, the number of buffers is limited and the receiving rate is lower than the sending rate)

Solution: every time the receiver receives a frame, it sends back a reply to the sender, and the sender cannot send a subsequent frame until it receives the reply.

Working process:

Sending process: get the data, form the frame, send the frame, wait for the reply frame

Receiving process: waiting, receiving frame, sending data to high level, sending reply frame

(3) Simplex stop and wait agreement (if there is an error)

Add constraints: there is an error in the channel and the information may be damaged or lost.

Solution: A. use positive response + timeout retransmission mechanism to solve the error problem.

B. The data serial number adopts the cyclic serial number mechanism (the serial number is to ensure the continuity of the data, and the data serial number will be used in a loop).

C, two ways of answering:

Single frame reply: the response sequence number is a correct sequence number (simplified model use)

Batch reply: the reply sequence number is the next expected sequence number (used in the actual network environment, parsing: the actual computer communication is duplex communication. If you need to make the frame reach the destination correctly, you need to add the header and trailer. This will cause a waste of channel, so it is necessary to let the data frame carry the reply information to avoid wasting bandwidth in separate frames.)

In practice, although the simplex stop and wait protocol can control the flow, its efficiency and throughput are very low. Can we think of a way to use the channel itself as a buffer? So people invented the continuous stop protocol (pipelined protocol).

(4) continuous stop protocol (pipelined protocol)

How it works: you can continuously send the following subsequent frames without receiving a reply frame

Post-error processing:

Processing strategy 1: after the error, he will resend all subsequent frames of this frame, and the receiver only needs a buffer (all retransmit pipeline protocol) (wasting channel bandwidth).

Processing strategy 2: after the error, he only resends the wrong frame, and the receiver buffer needs to cache the previously received frame and wait for the desired frame to be sent, which requires the receiver to have enough buffers (choose retransmission pipeline protocol).

(a buffer large enough is required)

In the actual process, the pipelining protocol can not meet the problem of dynamic buffer allocation, which may lead to insufficient or waste of resource allocation or deadlock. Therefore, sliding window negotiation, which is the most widely used protocol in the computer system, has emerged.

(5) sliding window protocol

The sliding window protocol is an improvement on the continuous stopping protocol, which can control the number of sent but unacknowledged data frames (that is, the size of the sliding window).

A, send window

Window size: specifies the number of unanswered frames allowed to be sent continuously (the size is the same as the number of buffers)

Upper bound (leading edge): the sequence number of the next transmission, that is, the frame number of the next frame to be sent

Lower bound (trailing edge): the sequence number of the next reply, that is, the sequence number of the response frame it expects to get.

Conditions under which data is allowed to be sent: upper bound-lower bound

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.