Part II data link layer

There are two main types of channels used by the data link layer ：

1. Point to point communication . One-to-one point-to-point communication .
2. Broadcast communications . One to many broadcast communication mode .

Basic concepts of data link layer

link ： A physical link from a node to an adjacent node .

The data link ： link + Realization “ A communication protocol that controls the transmission of data ” Software and hardware .

Adapters are generally used （ network card ） Implement the software and hardware of data link layer and physical layer .

Data link layer of point-to-point channel Protocol data unit yes frame .

Why encapsulate data into frames ？

1. The need for packet switching （ Reduce the time delay ）;
2. The need for asynchronous transmission （ Different computers have different clocks ）;
3. The need for time division multiplexing （ Data is too big to occupy other people's resources ）.

The main steps of data link layer communication in point-to-point channel ：

1. node A The data link layer handed over the network layer IP The datagram adds the first part and the last part to package into a frame ;
2. node A Send the encapsulated frame to the node B Data link layer ;
3. If the node B The frame received by the data link layer is error free , Then... Will be extracted from the received frame IP The datagram is handed over to the upper network layer ; Otherwise, discard the frame .

Three basic questions *

Package into frames

It refers to adding a header and a footer before and after a piece of data , So you have a frame .

Frame length ： The length of the data part of the frame plus the length of the head and tail of the frame .

The role of the head and tail ： Frame delimitation ; Storage control information .

Why frame delimitation ？
Asynchronous communication is generally adopted , The error of clock shall not be accumulated too much . Frame delimitation adds an agreed mark before and after the frame , The receiver can identify the start and end of the frame according to the mark . So the clock error will not accumulate .

The length of the data part shall be larger than the head and tail ： Improve the transmission efficiency of frames ; The length of the data part cannot be too long ： Maximum transfer unit （MTU, Upper limit of data transmission ）.

The start of frame delimitation is SOH（00000001、01）,EOT（00000100,04）.

Transparent transmission

If... Appears in the data 04, So obviously the data transmission will stop prematurely . Therefore, it is necessary to introduce corresponding solutions .

So called transparent transmission , It means that you don't care about the transmission of special characters , As if not SOH、EOT The restrictions on these characters are the same .

Method （ Character padding ）： The control characters appear in the data in the data link layer of the sender SOH、EOT Insert an escape character before ESC（00011011,1B）; The data link layer at the receiving end deletes the inserted escape character before sending the data to the network layer .

Error checking

Bit error rate BER： The ratio of transmission error bits to the total number of transmitted bits .

The bit error rate is related to the signal-to-noise ratio and cannot be reduced to 0.

Cyclic redundancy test CRC The process of ： Assume that the data to be transmitted is M, The redundancy codes for error checking are $n$ position

1. Using binary modules 2 The operation is carried out $2^n\times M$ Arithmetic , This is equivalent to $M$ Add later $n$ individual 0;
2. Got $(k+n)bit$ The number of divided by the predetermined length is $(n+1)bit$ Number of numbers $P$, Gain quotient $Q$ And the remainder $R$（0 Don't omit ）;
3. $R$ Added as redundancy code in $M$ And send it out ;
4. At the receiving end , Divide the received frames by the same $P$, Just get the remainder $R$ Not for 0, It means that an error has been detected .

About the mould 2 operation , You can refer to This article . Each of the above steps is modular 2 operation .

Polynomials represent binary numbers , such as 1101 It can be expressed as $P(X)=X^3+X^2+1$.

explain ：

1. The remainder is equal to 0 It may be right , Or maybe there are too many mistakes .
2. CRC Just make sure there are no bit errors , But reliable transmission cannot be guaranteed （ And frame loss 、 Frame repeat 、 Frame out of order ）;
3. To achieve reliable transmission, it is necessary to add an acknowledgement and retransmission mechanism ;
4. model 2 division ： The operation is performed only when the remainder digit is greater than or equal to the divisor digit , Otherwise, let the business be 0, Fill a , Until we get to the last place ;

Stop waiting for agreement *

In the early days of computer network development , The communication link is unreliable , Therefore, reliable communication protocols are used when transmitting data at the link layer , This stop waiting protocol is a typical example . Now, , The data link layer no longer undertakes the guarantee of reliable transmission .

Stop waiting is to stop sending every time a packet is sent , Waiting for confirmation . Send the next packet after receiving the confirmation .

There are three situations , Here we will introduce respectively .

1. No mistakes ;
2. Something went wrong ;B receive M1 There was an error in the detection , Just throw away M1; perhaps M1 Lost in transit . In both cases ,B No messages will be sent .A As long as no confirmation is received for more than a period of time , I think the packet just sent is lost , Thus retransmission of the previously sent packets , This is called a timeout retransmission .
3. Confirm missing and confirm late ; The former refers to B Sent to M1 The confirmation of is lost ; The latter refers to B Sent to M1 We are late for confirmation . In both cases , about B Come on , Received duplicate M1 after , Return a confirmation frame , And discard the M1; about A Come on , After receiving the repeated confirmation frame , Take it , But do nothing .

An illustration of the above situation is shown below ：

explain ：

1. A After sending a packet , A copy of the sent packet must be retained , Clear only after receiving the corresponding confirmation ;
2. Both grouping and confirming grouping need to be numbered ;
3. The retransmission time set by the timeout timer should be longer than the average round-trip time of data re packet transmission , When sending a data frame , Just start a timeout timer .

The stop waiting protocol is used to retransmit out of error frame , What are the other advantages? ？
4. flow control ; The sender must wait until the other party has received the data before sending the confirmation message , Then the sender receives the confirmation information and sends the next frame , In this way, the receiving end will not have time to receive ;
5. Solved the problem of late starters and first arrivals .

What are the benefits of numbering frames ？
6. Avoid duplicate frames caused by loss of acknowledgement ;
7. Avoid duplicate frames caused by late acknowledgement .

Two descriptions of the stop wait algorithm are given below ：

explain ：

1. $V(S)$ It should be a local receive state variable ;$N(S)$ Is the number on the frame ;
2. The data enters into the sending cache ten times before sending , Finish some preparatory work ;
3. Two if Conditions remember ;
4. Be careful 7 and 8 Go to 3 and 4.
   

The above reliable transport protocol is often referred to as automatic retransmission request ARQ, The request for retransmission is automatic , The receiver does not need to tell the sender that the data is wrong .

Retransmission time

therefore , The retransmission time can be set to $$t_{out}=t_p+t_{pr}+t_a+t_p+t_{pr}$$

Advantages and disadvantages

advantage ： Simple ;
shortcoming ： Low channel utilization .

continuity ARQ agreement *

Stop waiting for the protocol after sending a frame , The channel is idle , It's a little wasteful , So this protocol is proposed to improve the channel utilization .

working principle

After sending a data frame , Several data frames can be sent consecutively （ In the send window ）.

Every time the sender receives a confirmation , Just slide the send window forward one packet .

Due to reduced waiting time , The throughput of the whole communication is improved .

explain ：

1. The receiver only receives data frames in sequence , All frames received after encountering errors are discarded , Then wait for the sender to send the error frame and the subsequent frame ;
2. node A Each time a data frame is sent, the timeout timer of the frame is set ;
3. continuity ARQ Also known as Go-back-N ARQ;

Besides , There is also a confirmation method called cumulative confirmation , After receiving several groups , Send a confirmation to the last packet arrived in sequence . The advantage is that it's easy to achieve , The disadvantage is that they can't give feedback in time .

The sliding window

explain ：

1. The sending end and the receiving end set the sending window and the receiving window respectively ;
2. The sending window controls the flow of the sending end ;
3. Send window size $W_T$ Represents the maximum number of data frames that the sender can send without receiving the other party's confirmation information ;
4. continuity ARQ Agreement , The receiving window size is generally set to $W_R=1$;
5. If the received data frame falls outside the receiving window , Then all of them will be discarded ;
6. Every time a frame with the correct sequence number is received , The receiving window slides forward one frame , Send the confirmation of the frame at the same time ;
7. The size of the sending window and the receiving window are both equal to 1 Is to stop waiting for the agreement .

The maximum value of the send window

When used $n$ When the bits are numbered , If the receiving window size is 1, Only in the size of the send window $W_T\le 2^n-1$ when , continuity ARQ The protocol will work correctly .

PPP agreement *

PPP The requirements that the agreement should meet ：

1. Simple ;
2. Package into frames ;
3. transparency ;
4. Multiple network layer protocols ;
5. Multiple types of links ;
6. Error checking ;
7. Verify the connection status ;
8. Maximum transfer unit ;
9. Network layer address negotiation ;
10. Data compression negotiation ;

PPP Requirements that the protocol does not need to meet ：

1. error correction ;
2. flow control ;
3. Serial number ;
4. More lines ;
5. Half duplex or simplex ;

PPP The composition of the agreement

PPP The protocol is reflected in the frame setting . It consists of three components ：

1. One will IP The method of data packet encapsulation to serial link ;
2. Link control protocol LCP;
3. Network control protocol NCP.

explain ：

1. 0x7E Represents the start and end fields （01111110）;
2. A、C It's no use ;
3. 0xC021 when , Indicates that the data part is some basic information of the frame ;
4. 0x8021 when , The representation data section describes IP request ;
5. 0x0021 when , Indicates that the data part is the normal content .

Transparent transmission problem

Zero bit filling

When PPP When synchronous transmission is adopted , According to the protocol, hardware is used to complete the bit filling .

1. At the sending end , Scan the entire information field first ;
2. As long as we find that there is 5 A continuous 1, Fill in a... Immediately 0;
3. When receiving a frame, the receiver finds the flag field first F To determine the boundary of a frame ;
4. Scan the bit stream with hardware ;
5. Every discovery 5 A continuous 1, Put the 1 hinder 0 Delete , Restore the original bitstream .

Character filling

When PPP When asynchronous transmission is adopted , Use this method .

1. Put every... That appears in the information field 0x7E Bytes into 2 Byte sequence (0x7D,0x5E);
2. If a... Appears in the message field 0x7D byte , Then turn it into (0x7D,0x5D);
3. If the information field appears ASCII Code control characters （ The value is less than 0x20）, Insert... Before it 0x7D;
4. Reverse the operation at the receiving end .

PPP Working status of the agreement

Establishment process ： Physical layer connectivity 、LCP Connect 、NCP Connect ; The release sequence is the reverse .

Use the data link layer of the broadcast channel

This section discusses LAN .

LAN Overview

The main characteristic of LAN is ： The network is owned by one unit and the geographical scope and number of sites are limited .

Its advantages are ：

1. With broadcast function , A site can access the whole network and share hardware and software resources ;
2. Facilitate the expansion and evolution of the system ;
3. Improve the reliability of the system 、 Availability and survivability .

radio broadcast

The characteristics of the bus are as follows ： When a computer sends data , All computers on the bus can detect this data .

In order to realize one-to-one communication on the bus , You can make each computer's adapter have a different address than any other adapter .

When sending data frames , Write the address of the receiving station at the beginning of the frame .

Only when the destination address in the data frame is consistent with the hardware address stored in the adapter , Only this adapter can accept this data frame .

For the convenience of communication , Ethernet adopts two measures ：

1. Adopt a more flexible way without connection , That is, you don't have to establish a connection to send data directly . The adapter does not number the transmitted data frames , Also does not require the other party to send back confirmation .
2. The data sent by Ethernet are all Manchester encoded signals. .

CSMA/CD agreement *

“ Multipoint access ” It means that many computers are connected to a bus by means of multi-point access ;

“ carrier sense ” It means that each station should check whether there are other computers on some buses sending data before sending data ;

“ collision detection ” The computer detects the signal voltage on the channel while sending data （ When several stations send data on the bus at the same time , The signal voltage swing on the bus will increase ）.

In the event of a collision , The signal transmitted on the bus has serious distortion , There is no way to recover useful information . therefore , Once a collision is found , Stop sending immediately .

To make a long story short , This agreement is about two things ： Continuously detect the idle degree of the channel ; Stop immediately in case of collision .

among $\tau$ Is the propagation delay of the signal over the channel ,$\delta$ Is the propagation delay required by the signal .

Contention period

End to end round trip delay $2\tau$ Called contention period or collision window .

Only after the contention period has passed and no collision has been detected can we be sure that no collision will occur in this transmission .

Important features

Use CSMA/CD Ethernet protocol can not carry out full duplex communication, but can only carry out half duplex communication .

Each station is in a short period of time after sending data , There is a possibility of collision .

This transmission uncertainty makes the average traffic of the entire Ethernet less than the maximum data rate of the Ethernet .

The shortest effective frame length

If we take $51.2\mu s$ Is the length of the contention period , So for $10Mb/s$ For Ethernet , During the contention period, you can send 512bit, namely 64 byte .

If there is a conflict, it must be before sending 64 In bytes .

Ethernet has a minimum effective frame length of 64 byte , Any frame smaller than this value is an invalid frame that terminates abnormally due to collision .

Strengthen the collision

Once the station sending data finds that a collision has occurred , In addition to stopping sending data immediately , We will continue to send several bits of jamming signals , In order to let all users know that there has been a collision .

Minimum space between frames

The minimum interval between frames is $9.6\mu s$, A station detects that the bus is starting to idle , Wait for this time before sending data , The purpose is to clean up the receiving cache of the station that has just received the data frame , Be ready to accept the next frame .

Binary exponential type backoff algorithm *

Ethernet MAC layer

MAC The hardware address of the layer

1. Hardware address is also called physical address or MAC Address , common 48bit.
2. Cured at the end of the adapter ROM among , Once the adapter is replaced , Then the address also changes ; If there are multiple adapters , There are also many MAC Address .

The network card receives every one from the network MAC The frame is first checked with the hardware address MAC In the frame MAC Address . If the frame is sent to the site, accept it , Otherwise, discard .

There are three types of frames sent to this station ：

1. unicast ;
2. radio broadcast ;
3. multicast .

MAC Frame protocol / Format （V2）*

Because of the CSMA/CD The minimum frame length is required to be 64 byte , So here IP The minimum length of the datagram is 64-18=46.

When the length of the data field is less than 46 Byte time , You need to add a padding field of integer bytes .

invalid MAC The frame is ：

1. The true length is not an integer byte ;
2. Check sequence of received frames FCS Find out what's wrong ;
3. The length of the data field is no longer 46～1500 Between bytes .

It is worth mentioning that ,PPP The protocol is used in Wan 、MAC Frame protocol is used in LAN .

Extended Ethernet

Extending Ethernet at the physical layer

A hub can be used to connect to a larger LAN .

The disadvantage is that ：

1. The collision domain has increased , The total throughput is not improved ;
2. Different collision domains use different data rates , Then you can't connect them with a hub .

Extending the LAN at the data link layer

The bridge is used .

The bridge has frame filtered content , First check the purpose of the frame MAC Address , Then determine which port to forward it to .

advantage	shortcoming
Filter traffic , The LAN segments are isolated into different collision domains	Store and forward increase delay
Expand the scope of Physics	No flow control function , There will be frame loss
Improved reliability . A broken network segment will not affect others	Broadcast storm
Different physical layers can be connected 、 Different MAC Sublayers and LANs with different rates	Different MAC The delay under the sublayer is larger

The bridge must execute before forwarding CSMA/CD Algorithm .