The article refers to B station: Wang Dao Postgraduate entrance examination – computer network

1. Basic concepts

2. Encapsulation into frames and transparent transmission

Encapsulated into a frameIt’s just adding the data plus the head plus the tail, it’s like packaging the data

Transparent transmissionIn order to preventSpecial data cannot be transmitted properlyFor example, some of the tags in the data happen to overlap with the start/end tags during frame encapsulation

2.1 Application of transparent transmission

2.1.1 Character counting method

You do a count at the beginning of the frame to see if the data is wrong.

  • Disadvantages: If a byte after the marker bit is lost in one frame, it will affect subsequent frames: such as 3, 1, 1 and 4, 2, 2, 2. If the previous frame is lost to 3, 1, then the following 4 will be replaced to 3, 1, 4, resulting in an error.

2.1.2 Character Filling Method

This is done by adding heads and tails to mark the beginning and end of each, as opposed to the zero-bit padding method (see below).The start and end characters correspond to different characters

But it is possible that some bit stream data within the data is just rightDuplicate with the tag field, which leads to misjudgment.



Solution: Add escape characters

2.1.3 Zero-bit filling method

2.1.4 Violation of coding law

Because the Manchester encoding does not use high-high and low-low representations, it would be better to use high-high and low-low representations to start and end framesDoes not conflict with data

3. Error control

3.1 What is the error and where does it come from

Data link layer error detection isThe bitThe error

3.2 Why Is Error control performed at the Data Link Layer?

Because errors can be detected as early as possible, it will not be discovered after a wrong packet has been sent for a long time to reach the final destination, resulting in a waste of network resources

3.3 Error detection codes (parity check code, cyclic redundancy code CRC)

3.3.1 Parity check code

Cons: can only detect 1,3,5,7… And so on odd number error, detection success rate bit 50%

3.3.2 Cyclic redundancy code CRC

You divide the transmitted data by the generated polynomial to get the redundancy code



Practical example

Note:

1. The order is the highest digit, and then the number -1. For example, 10011 is 5-1=4,1011 is 4-1=3

2. Xor is the same to get 0, different to get 1, for example, 100 and 101 xor, the result is 001

3. The book and the last remainder are added to the data to be sent, calledFrame check sequence FCS



The receiver checks the data after receiving it



Something to watch out for

3.4 Error correction Code (Hamming Code)

Is divided into four steps

The first step is to confirm the parity digit R

The second step is to determine the location of the check code and data

Note: 1. Why is 10 the data bit? 2. Place the check code to the power of 2, and place the known information bits in the other places in order

The third step is to find the value of the check code

annotation

1. First determine the number of bits by binary. In this case, the largest bit 10 is 1010, so it is 4

2. Then start with P1 and check whether the value of the binary bit of P1 is the same as the value of the corresponding position of all information bits, and then find these bits

So this is a little bit hard to understand, so if I take p1 as an example, what I find here is P1,D1,D2,D4,D5



And then calculate the xor value, for example D1=1,D2=0,D4=1,D5=0, which means p1 has to sum at the same time0.1.0.1After xor, I get 0. I bold the original calculation to identify it

For example:0and1Xor gets 1,1 and0Xor gets 1,1 and1Xor gets 0, so p1 and 0 xor gets 0, so P1 is 0

3. In the same way, calculate P2,P3,P4 in order, then fill in the table

Step 4 detect and correct errors

As above, all check bits are computed and the result is the wrong bit

4. Traffic control and reliable transmission at the data link layer

4.1 Flow control and Reliable transmission

Flow control is to make the transmission process send speed and receive speed match, reduce transmission errors and waste of resources reliable transmission is what the sender sends, the receiver will receive

4.1.1 Stop-and-wait Protocol (STOP-and-wait)



Stop waiting for an agreementerror-freesituation

Note: Since there is only one at a time, 0 and 1 marks for ACK will do



Stop waiting for an agreementThere are mistakessituation







Stop waiting for protocol features

1. Simple

2. The channel usage is low. Most of the time the data is on the road, and the sender is idle for a long time, wasting resources

4.1.2 Back N Frame Protocol (GBN)

Since stopping the wait protocol is too time consuming, we try to use GBN to send consecutive data frames to increase channel utilization. If an acknowledgment frame is received, it and all frames before it are received by default. If an acknowledgment frame is not received, it and all subsequent frames are lost by default and retransmitted



Here is an example

Note: This picture is lost when sending 2 frames, so the receiver will directly discard the next few frames and send the ACK of the latest valid frame 1. The receiver will not accept the second frame and the next frame until the timeout retransmission mechanism of the second frame is triggered for retransmission and gets the ACK



The send window cannot be infinitely large, depending on the number of numbered bits used

Very simple, is 1 bit number 0 and 1, the same as 2 bits number 0-3, if you use 1 bit number, but to 4 window length, then the window data number can not be compiled, direct chaos

The advantages and disadvantages of GBN are also obvious. The advantage is that the channel utilization rate is improved, while the disadvantage is that the data already received needs to be discarded forcibly due to the retransmission mechanism, resulting in waste

4.1.3 Selecting the Retransmission Protocol (SR)

To address GBN’s shortcomings, we are going to try to retransmit only the wrong frames so that we don’t waste resources on retransmitting the received frames.

Compared with GBN, both have Windows. The difference between GBN and GBN is actually to make a data cache. The received frames need not be thrown away, and the confirmation can be made when the received frames are accidentally lost.

SR running process

Note: it is still sent after 2 frames are lost, but the window is only cached after 2 frames are lost, and no window is moved until 2-5 frames are confirmed once the last 2 frames are received



Also, because of numbering, the send window cannot be infinite

Send window last and receive windowThe same sizeIn this way, the utilization rate is higher

5. Media access control technology

So that the communication between nodes does not interfere with each other

5.1 Channel Division Media access control

Although using a shared channel, but through the combination of multiplexing technology for transmission, improve channel utilization

5.1.1 Frequency division multiplexing FDM

5.1.2 TDM multiplexing

The disadvantage of TDM is low utilization rate, so STDM is derived

5.1.3 TDM statistics

The principle of STDM is first come, first go, and when it is full, it will be delivered. Compared with TDM, STDM has improved the utilization rate

5.1.4 Code division multiplexing CDM

CDM is just for recording, but it is not needed for the time being. If necessary, please find information by yourself

5.2 Random Access Media Access control

All users can send messages randomly, taking up all bandwidth when sending, which is theoretically faster for individual use than for statically allocated channels

5.2.1 ALOHA agreement

Disadvantages of pure ALOHA protocol: Too random, resulting in low efficiency



Slotted ALOHA protocol

Compared with pure ALOHA protocol, the time of sending is fixed (only at the beginning of a time slice), which improves efficiency

5.2.2 CSMA protocol

The name of the describe advantages disadvantages
1 – insist on CSMA When sending information, monitor the channel and transmit it immediately as soon as it is idle. When the channel is busy, monitor it all the time. If there is a conflict when sending, wait for a random time to monitor it again Immediate sending, high utilization If multiple devices are listening at the same time, conflicts can occur
Not insist on CSMA When sending a message, the channel is monitored. If the channel is idle, it is transmitted immediately. If the channel is busy, it is monitored after a random period of time Conflict is less likely Because of the waiting, utilization is not high
P – insist on CSMA The channel is monitored when the message is sent. When it is idle, it is transmitted with probability P, and probability 1-P is not transmitted. Channel busy on the random wait for a period of time after monitoring Less conflict and higher efficiency Resources are wasted by insisting on sending data even when conflicts occur

5.2.3 requires CSMA/CD protocol

An overview of the

Because of the actual length of the link, it takes time to send data, which may be considered idle by other nodes and lead to collisions

The longest time you know you’re in a collision is 2τ (twicePropagation delay), just once



The influence of propagation delay on carrier sense is illustrated





From this we can think of the problem of the minimum frame length, because if the frame is too short, the collision will be detected and stopped after all the frames are sent, so the collision cannot be stopped

5.2.4 CSMA/CA protocol



5.2.5 Differences between CSMA/CD and CSMA/CA

5.3 Polling Access media Access control

It mainly includes two categories, one is polling protocol, the other is token passing protocol

5.3.1 Polling protocol

Is to select a representative and let him control all transmission comments: Polling overhead as the more nodes serve, the more data frames need to be used to query whether to send data or not, which will cause some overhead waiting delay. Because this is a rotating “invite”, it is inevitable that a node needs to send data, but the master node is still in the distant need of the node with demand. A single point of failure can be understood as a dead end

5.3.2 Token passing protocol

Note: Tokens loop between nodes when there is no need to send or receive data between nodes. The process of sending data. This token is available when a node needs it. And then modify the token of the state (idle – > take up) and token combined with data frames, let it flow between the ring of the nodes, not a destination node receives the token is not accepted, skip directly, the target node receiving information and a copy to the local finish (transfer), because is a closed loop, so the sending node finally get the token “in the end, The node that sends the token checks the contents of the token and reissues the token if it finds any data error. The problem is basically the same as the polling protocol

6. Local area network (LAN)

6.1 Concepts of LAN

Summary: range size, fast speed, low latency, node equality

6.1.1 LAN Network Topology

Commonly used areBus topology

6.1.2 LAN Media

Local area network (LAN) Commonly used medium
Wired LAN Twisted pair, coaxial cable, optical fiber
Wireless LAN The electromagnetic wave

6.1.3 LAN media Access method

6.2 Classification of Lans

6.3 standard IEEE802

6.3.1 LAN Reference Model Described in IEEE802

6.4 Ethernet

6.4.1 Ethernet Concepts



6.4.2 Development of Ethernet

6.4.3 Adapter and MAC Address

6.4.4 Ethernet MAC Frames

Note: 1. The MAC layer here refers to the data link layer 2. The data link layer will add the previous IP packet header and tail header is the destination address (6 bytes), the source address (6 bytes), the type (2 bytes) and the tail is the FCS (frame check sequence), (4 bytes) 3. The leading code is not part of the MAC frame. The purpose is to synchronize the clock. 4. Since there is a minimum transfer byte of 64 bytes, MAC usage is 6+6+2+4=18, so data minimum 64-18= 46,1500 is the default maximum specified, there is no reason

6.4.5 10Base-T Ethernet

6.4.6 High-speed Ethernet

6.5 Wireless LAN



6.5.1 Two types of Wireless Lans



7. Wan

7.1 Overview of wan

To recap, one word

7.2 Point-to-point Protocol (PPP)

PPP is the most widely used data link layer protocol. Most dial-up protocols are PPP. PPP supports only full-duplex links

7.2.1 PPP Requirements

7.2.2 Requirements that THE PPP protocol does not need to meet

7.2.3 COMPONENTS and Functions of PPP

7.2.4 Frame Format of PPP

7.3 HDLC (High-level Data Link Control)

7.3.1 OVERVIEW of HDLC Protocol

7.3.2 Three stations of HDLC

7.3.3 Frame Format of HDLC

7.4 Comparison between PPP and HDLC

Why is HDLC more reliable, but we use PPP?

Because of the high network requirements, the data link layer is not reliable transmission, error control these complex to TCP and so on

8. Link layer devices

8.1 Hub

Ethernet can be extended, but the hub will mindlessly forward all messages from one device to all devices connected to the hub. Therefore, all connected devices will become a large conflict domain. Only two devices can communicate at the same time, and the more devices, the more conflicts. Thus was born the bridge

8.2 Network Bridge

If a network bridge is used, the network bridge is filtered according to the MAC addressNo conflict domains are formed

8.2.1 Two types of Bridges

Transparent Bridges

Build the forwarding table through self-learning. Each packet passing through the bridge will be recorded when the bridge receives the data corresponding to the address of the data and the bridge’s own interface, through the construction of many packets of cache, the bridge can know which packet in which interface, if you want to go through the packet will know which interface to send the packet

Original routed network bridge

When sending, place the best path directly at the head of the frame. So how do Bridges get the best path? If you want to broadcast to the target address, different paths may be generated through different routes at this time. After receiving the target address, each path will send a response frame to the bridge. The bridge will know which interface is the fastest after comparison

8.3 switch

As more Bridges interface, the bridge becomes a switch

8.4 Conflict Domains and Broadcast Domains

9. This chapter summarizes mind mapping

This chapter is usually written in Chinese and English

End system Modem Modem Coaxial cable Coaxial cable Fiber Optics Radio spectrum Coaxial cable Coaxial cable Transmission rate Packets Or group Routers Path Internet Service Provider (ISP) Frequency division multiplexing (FDM) TDM Time division multiplexing Statistical multiplexing Queuing delays Transmission delay Throughput Internet Backbone network delay Transmission delay Loss Indicates the Message or packet Segment. Datagram Indicates the data packet FramesCopy the code

2019 Wang Dao Entrance examination computer network