Teaching material: Computer Network (7th edition) xie Xiren edition

Data link layer

1. Link and data link

  • Nodes: host and router
  • Link: A section of a physical line from one node to a neighboring node without any other switching nodes in between.
  • Data link: When data needs to be transmitted over a line, processing must have a physical line, there must also be some table of communication protocols to control the transmission of the data, these two protocols hardware and software added to the link, constitute the data link.

2. Three basic problems of the data link layer: frame encapsulation, transparent transmission and error detection

  • Encapsulation into frames: Add the header and tail of IP packets handed over by the network layer and encapsulate them into frames.

  • Transparent transmission:

SOH and EOT are the control symbols of the beginning and the control services of the end. Frame synchronization with a special bit stream makes it seem as if something that actually exists does not exist. Indicates that any combination of bits of data can pass through the data link layer as is and without error. As a result, the data is “invisible” to the link layer to prevent the data from being transmitted. In other words, the data link layer is transparent to this data.

In order to solve the problem of transparent transmission, we must try to make the possible “SOH” and “EOT” in the data not be interpreted as control characters at the receiving end. An escape character ESC can be inserted before the SOH or EOT and the data link layer at the receiving end deletes the inserted control character before sending the data to the network layer. This method is also called byte padding, character padding.

  • Error detection:

3. MTU Bit error rate Error-free acceptance reliable transmission Transmission errors: bit error, frame loss, frame duplication, and frame dissequence

  • Maximum transmission unit MTU: Each link layer protocol specifies the maximum length of the data portion of the frame that can be transmitted.
  • Bit error rate (BER) : The ratio of the transmitted error bits to the total number of transmitted bits during a period of time.
  • Error-free acceptance: All frames received by the data link layer at the receiving end can be considered with a probability of very close to 1 that these frames were transmitted error-free.
  • Reliable transmission: What the sender sends at the data link layer, the receiver receives.
  • Bit error: Bit error may occur during transmission. 1 May become 0 or 0 May become 1.
  • Frame loss: received [#1]-[#3] (lost [#2])
  • Frame repetition: Received [#1]-[#2]-[#2]-[#3] (received two [#2])
  • Frame disorder: received [#1]-[#3]-[#2]

4. Cyclic redundancy check code (CRC)

5. PPP(features, frame format, working status)

PPP point – to – point protocol is the most widely used data link layer protocol. PPP for dial-up access, point-to-point links between Ethernet switches and hosts. Unreliable transmission, full duplex.

5.1 characteristics:

  1. Simple: PPP protocol is not as complex as TCP or IP protocol, the data link layer protocol is not necessary to provide more functions than TCP/IP protocol, so the data link layer frame, do not need error correction, no sequence number, and do not need flow control. That’s why the IETF prioritized simplicity.

The protocol at the data link layer is very simple. Each time the receiver receives a frame, it performs a CRC check. If the CRC check is correct, it accepts the frame.

  1. Encapsulation into frames: THE PPP protocol must be framed according to the specified special characters. The SOH or EOT mentioned above.
  2. Transparency: PPP must be transparent with respect to special characters, that is, if the data happens to have the same combination of bits as the frame delimiter, special measures must be taken, such as byte padding mentioned above.
  3. Multiple network layer protocols: PPP must support multiple network layer protocols (such as IP and IPX) on the same physical link. It must also support the various network layer protocols that the LAN or router runs.
  4. Multiple types of links: PPP also supports multiple types of links, such as serial or parallel, synchronous or asynchronous, vulgar or high-speed.
  5. Error detection: PPP must be able to detect the frame received by the receiver and immediately lose the frame with error. If error detection is not possible, the faulty useless frames will continue on the link layer, wasting many network resources.
  6. Connection status detection: PPP must have a state that can automatically detect whether the link is working properly in a timely manner. Send it every few minutes.
  7. Maximum transmission unit (MTU) : PPP must set a maximum transmission unit (MTU) for point-to-point links. If a higher-level transmission packet is too long and exceeds the MTU value, PPP dismisses such a frame and returns an error. Emphasize that THE MTU is the maximum length of the data portion that a data link layer frame can load, not the frame length.
  8. Network layer address negotiation: PPP must provide such that the two communicating network layer entities (for example, two IP layer entities) can know or configure each other’s network addresses through negotiation.
  9. Data compression algorithms: Provides a way to negotiate the use of data compression algorithms, but PPP does not require data compression algorithms to be standardized.

Composition of PPP

  • A method to encapsulate IP datagrams into a serial link.
  • A link control protocol LCP used to establish, configure, and test data link layer connections.
  • A set of network control protocol NCP.

5.2 the frame format

  1. Meaning of each field

F: flag field A: address field C: control field

  1. Byte filling

When a bit (0x7E) with the meaning of the flag field appears in the information field, something must be done to prevent the bit, which is formally the same as the flag field, from appearing in the information field

  • Convert each 0x7E byte that appears in the information field into a 2-byte sequence (0x7D, 0x5E)
  • If a byte of 0x7D appears in the information field (that is, the same combination of bits as the escape character appears), the 0x7D byte is converted, and the sequence of 2 bytes (0x7D, 0x5D) is converted.
  • If an ASCII control character appears in the information field, add a 0x7D byte before the character and change the character encoding.
  1. Zero bit filling

When PPP is used on SONET/SDH links, it uses synchronous transmission (a sequence of bits) rather than asynchronous transmission (character by character). In this case, it is necessary to adopt zero-bit filling method to realize transparent transmission.

  • Scan the entire message field at the sending end.
  • As soon as five consecutive ones are found, a zero is immediately filled in.
  • The receiver receives a frame and first finds a flag character F to determine the boundary of the frame.
  • When five consecutive ones are found, a 0 after the five consecutive ones is deleted to restore the original information bitstream.

5.3 Working Status

  • The physical layer connection is established
  • Then negotiate the LCP configuration. If the negotiation fails, the link becomes static.
  • If authentication succeeds, the link is terminated if authentication fails
  • If authentication is successful or no authentication is required, the network layer protocol is entered to negotiate the NCP configuration.
  • After the configuration at the network layer is complete, the link is open for data communication.

Link Control Protocol (LCP) is the underlying PPP protocol, responsible for link control. Network Control Protocol (NCP) is the upper layer of PPP and is responsible for network control.

6. Technologies for sharing communication media resources

6.1 Static Channel Division

As mentioned in the previous chapter, frequency division multiplexing, time division multiplexing, WDM, WDM and code division multiplexing.

6.2 Dynamic Media Access Control (Multi-point Access)

Channels are not fixed to users when they communicate with each other.

  • Random access: All users can send information randomly. But if two or more users communicating happen to be sending messages at the same time, then a collision occurs on the shared media.

  • Controlled access: users cannot send messages randomly but must submit to certain controls. Typical examples of this are token ring lans with decentralized control and multipoint line inquiry with centralized control, also known as polling.

7. Mac address: I/G bits and G/L bits

7.1 Hardware Address of the Mac layer

A hardware address is also called a physical address or a MAC address

7.2 I/G

The lowest byte of the first byte in the address field is the I/G bit. When the I/G bit is 0, the address field represents the address of a single station. When the I/G bit is 1, it indicates the group address, which is used for multicast.

7.3 G/L

The lowest second byte of the first byte in the address field is set to G/L. When G/L is 0, the address is managed globally (no same address exists in the world). When G/L is 1, the address is managed locally.

7.4 the frame type

  1. Unit frame (one-to-one) : The MAC address of the received frame is the same as the hardware address of this site
  2. Broadcast frame (a pair of all) : A frame (with all 1 addresses) sent to all sites on the local area network
  3. Multicast frames (one-to-many) : Frames sent to some sites on the local area network (LAN).

7.5 the frame format

8. CSMA/CD protocol

Carrier sense, multipoint access, collision detection, in order to reduce the probability of collision. Unreliable transmission, half duplex.

  • Multipoint access: this means that this is a bus network and many computers are connected to the bus in a multipoint access mode. The protocol is actually carrier sense and collision detection
  • Carrier sense: Electronic detection of whether other computers on the bus are also transmitting. It’s the detection channel, whether before or during transmission, each station has to constantly check the channel.
  • Collision detection: While sending and listening, that is, the adapter is sending data while detecting the change of signal voltage on the channel, so as to determine whether other stations are also sending data.

Within an hour of each station sending its data, there is the possibility of a collision. This little segment is indeterminate, it depends on the distance from another transmitting station to this site. Therefore, Ethernet cannot guarantee that it can successfully send its own data frames within a certain period of time because of collision.

9. Contention period, collision window, and minimum frame length

  1. Contention period: From the figure above we can see that station A, which sent the data frame first, has at most elapsed time after sending the data frame2tYou know whether the data frame encountered suffered a collision, and therefore the Ethernet end-to-end round-trip time2tFor the contention period. If no collision has been detected after the contention period, you can be sure that this send will not send a collision.
  2. Collision Windows are also called contention periods and collision Windows
  3. Minimum frame length The minimum frame length is 64 bytes. Any frame less than 64 bytes is an invalid frame that terminates abnormally due to a collision. Whenever such an invalid frame is received, it should be discarded immediately.

10. Ethernet channel utilization

The Ethernet channel is occupied.

Only when parameter A is much less than 1 can we get the highest possible limit channel utilization.

11. Ethernet frame format

The Ethernet V2 MAC frame is simple and consists of five fields.

  • The first two fields are 6 fields long respectively.
  • The third field is the 2 field and type field. The protocol used to indicate what protocol is used by the previous layer in order to transfer data from received MAC frames to the previous layer.
  • The fourth field is the data field.
  • The last field is the frame check sequence FCS(using CRC checks)

12. Transparent bridge, spanning tree protocol

12.1 Transparent Bridge

Transparent Bridges are plug and play devices that work as long as the bridge is connected to the LAN without hardware or software changes, address switches, routing tables or parameters being loaded.

12.2 Spanning Tree Protocol

Without changing the actual topology of the network, some links are logically cut off, so that the path from one host to all other hosts is a loop-free tree structure, thus eliminating the phenomenon of all circles.

Prevents loops caused by redundant switch links. This parameter is used to ensure a loop-free logical topology on the Ethernet. In this way, broadcast storm is avoided, which occupies a lot of switch resources.

13. Switch versus hub: VLAN

13.1 Comparison between switches and Hubs

The switch made hubs obsolete. In the OSI/RM (OSI reference model), switches and hubs work at different layers. Hubs work at both layer 1 (physical layer) and Layer 2 (data link layer), while switches work at at least layer 2. More advanced switches can work at layer 3 (network layer) and Layer 4 (transport layer).

(2) different forms of data transfer switch hub of data transmission mode is a radio (broadcast) mode, and exchange of data transmission is purposeful, data is sent only to the destination node, only in their own MAC address table can’t find the first one to use broadcast way to send, then as switch MAC address learning function, After the second time, it was no longer a broadcast transmission, but a purposeful transmission. The benefits are that data transmission efficiency is improved, broadcast storms do not occur, and in terms of security, other nodes do not listen.

(3) the bandwidth in a different way In terms of bandwidth, the hub all ports is to share the total bandwidth, and switches, each port has its own bandwidth, thus the bandwidth of the switches, in fact, each port is much higher than a hub port available bandwidth, also decided to switch the transmission speed is much faster than a hub.

(4) Transmission mode Different hubs can only use half-duplex mode for transmission, because the hub is shared transmission media, so on the uplink channel, the hub can only transmit one task at a time, either to receive data or to send data.

13.1 VLAN Virtual LAN

A VIRTUAL local area network (VLAN) is a logical group consisting of local area network (LAN) segments that have common requirements and are independent of physical addresses. Each VLAN frame has a specific identifier that identifies which VLAN the computer that sent the frame belongs to.

Three virtual Lans VLAN1 VLAN2 VLAN3

You can see that each VLAN computer is in a different LAN, can also not be on the same floor.

14. Ethernet physical layer standards

The method adopted in 100Mbit/s Ethernet is to keep the minimum frame length constant. For copper 100Mbit/s Ethernet, the maximum length of a network segment is 100m, and its minimum frame length is 64 bytes, or 512 bits, so the contention period is 5.12us, and the minimum frame interval is now 0.96us. Both 10Mbit/s Ethernet 1/10.

15. Carrier extension, packet burst

Full dual working hours are not used

15.1 Carrier extension

In Gigabit Ethernet, the number of bits added to the end of a media access control frame. This allows the frame to be transmitted for a longer period of time to avoid collisions.

15.2 Packet Burst

To avoid the carrier extension overhead when sending short frames, when many short frames are to be sent, the first short frame is truthfully charged using the carrier extension method described above.

16. Exercises after class

The data to be sent in the first question (3-07) is 1101011011. The generation polynomial using CRC is P(X)=X^4+X+1, and the remainder should be added after the data. In the process of data transmission, the last 1 becomes a 0, and the receiver is asked whether it can find? What if both of these ones become zeros?

The data portion of a PPP frame (written in hexadecimal) in question 2 (3-09) is 7D 5E FE 27 7D 5D 7D 5D 5D 65 7D 5E. What is the real data?

PPP protocol uses synchronous transmission technology to transmit bit string 0110111111111100. What kind of bit string does it become after being filled with zero bits? If the data part of the PPP frame received by the receiver is 0001110111110111110110, what kind of bit string will it become after deleting the zero bit added by the sender?

The fourth question (3-14) commonly used LAN network topology has what kind? What is the most popular structure now?

Question 5 (3-16) what is the metaccoding transfer on physical media for an Ethernet with a data rate of 10Mbit/s?So it’s double, 2 times 10e6 symbols per second

Q: What is the meaning of 10, BASE and T in 10base-t?

Question 7 (3-20) assumes a data rate of 1Gbit/s for a 1km long CSMA/CD network. Let the transmission rate of the signal on the network be 200000 km/s. Find the shortest frame length that can use this protocol.

Question 8 (3-21) What is bit time, what are the benefits of using this unit of time, and how many microseconds is 100 bit time?

In question 9 (3-22), it is assumed that a station in a 10Mbit/s Ethernet using CSMA/CD protocol detects a collision while sending data, and the random number r=100 is selected when performing the backoff algorithm. How long does the station have to wait before sending data again? If the Ethernet is 100Mbit/s

Question 10 (3-24) assumes that site A and point B are on the same 10Mb/s Ethernet network segment. The propagation time between the two sites is 225 bits. Now suppose that A starts sending A frame and B also sends A frame before A finishes sending. If A is sending the shortest frame allowed by The Ethernet, can A finish sending its data before it detects A collision with B? In other words, if A does not detect A collision before it finishes sending, can you be sure that the frame sent by A will not collide with the frame sent by B? (Note: The calculation should take into account that each Ethernet frame is sent to the channel with a number of bytes of presync code and frame delimiter added before the MAC frame)These two questions directly look at the answer, the answer is very clear (too many words do not want to type)

Question 11 (3-25) Sites A and B in the previous question sent data frames at t=0 at the same time. When t=255 bit time, A and B simultaneously detect the collision and complete the transmission of interference signal at t=255+48=273 bit time. A and B choose different r values to retreat in CSMA/CD algorithm. Suppose the random numbers selected by A and B are rA=0 and rB=1, respectively. At what time do A and B each start to retransmit their data frames? At what time does the data frame retransmitted by A reach B? Will the data retransmitted by A collide again with the data retransmitted by B? Will B stop sending data at the scheduled retransmission time?

Question 12 (3-27) has 10 stations connected to the Ethernet. Try to calculate the bandwidth available to each station under the following three conditions. (1) all 10 stations are connected to a 10 MB /s Ethernet hub (2) all 10 stations are connected to a 100Mb/s Ethernet hub (3) all 10 stations are connected to a 10 MB /s Ethernet switch

An Ethernet switch has six ports, each connected to five hosts and one router. In the “Action” column in the following table, four frames were sent. Assume that at the beginning, the switch table of the Ethernet switch is empty. Try filling in all the other fields in the table

action Switch table status Which interfaces to forward frames to instructions
A sends frames to D
D sends A frame to A
E sends frames to A
A sends frames to E

The answer:

action Switch table status Which interfaces to forward frames to instructions
A sends frames to D So let’s say (A, 1) All interfaces The switch table starts empty and the switch does not know where to forward frames to the interface
D sends A frame to A So let’s say (D, 4) A The switch knows that A is connected to port 1
E sends frames to A So let’s say (E, 5) A The switch knows that A is connected to port 1
A sends frames to E The same E The switch knows that E is connected to port 5