3.1 Overview of Data Link Layer Functions

  1. Some of the concepts

    • Node: host and router
    • Link: A physical channel between two nodes in a network. The transmission media of a link can be twisted-pair, optical fiber, or microwave. There are wired links and wireless links.
    • Data link: A logical channel between two nodes in a network. A data link is formed by adding the hardware and software that implement the control data transmission protocol to the link.
    • Frame: a link-layer protocol data unit that encapsulates a network-layer datagram

  2. Data link layer functions

    The data link layer is responsible for transmitting datagrams from one node through a data link to neighboring nodes directly connected to another physical link

    • Function 1: Provides services for the network layer. None Confirmation no connection service, Confirmation no connection service, and Confirmation Connection-oriented service.
    • Function 2: Link management, namely the establishment, maintenance and release of connections (for connection-oriented services)
    • Function three: Frame grouping
    • Function 4: Flow control
    • Function 5: Error control

3.2 Encapsulation into frames and transparent transmission

  1. Encapsulated into a frame

    You add a head and a tail before and after a piece of data. After receiving the bit stream submitted by the physical layer, the receiver can identify the beginning and end of the frame from the received bit stream according to the tags at the head and tail.

  2. Transparent transmission

    Transparent transmission means that the data transmitted should be able to be transmitted over the link regardless of the combination of bits. When the combination of bits in the transmitted data happens to be the same as a control message, appropriate measures must be taken so that the receiver will not mistake such data for a control message.

    • Character counting: the length of each frame is specified at the beginning

    • Character padding: Padding specific numbers at the beginning and end

      • When the frame is a text file (i.e., all ASCII), it can be transmitted
      • When the transmission frame is composed of non-ASCII text files (binary code program or image), transparent transmission is performed by character filling method

    • Zero bit filling method:

    • Code violations

    Because the byte-counting count field is fragile, a difference can be devastating. Character padding has complexity and incompatibility on the line, while bit padding and illegal coding are commonly used.

3.3 Error Control

  1. What is a mistake?

    • Misalignment: a bit error in which 1 becomes 0 and 0 becomes 1
    • The frame is wrong
      • The loss of
      • repeat
      • disorder

  2. How did the mistake come about?

    • Global: the electrical characteristics of the circuit itself
      • Solution: The error can be reduced by increasing the signal-to-noise ratio (S/N) through shannon’s formula mentioned in the physical layer
    • Locality: impact noise caused by external transient reasons is the main cause of errors
      • The solution: Coding

  3. Error control (bit error) method

(1) Error code detection

  • Parity check code

  • Cyclic redundancy code CRC

(2) Error correction code

  • Hamming code: find double – bit error, correct single – bit error

3.4 Flow control and reliable transmission mechanism

  1. High transmission speed and low acceptance capacity do not match, will cause transmission errors, so flow control is also an important work of the data link layer.

    • Traffic control at the data link layer is point-to-point, while traffic control at the transport layer is end-to-end.
    • Data link layer traffic control means: The receiver does not reply to confirm the receipt
    • Transport layer traffic control means: the receiver sends a window announcement to the sender

  2. Flow control methods:

    • Stop. – Wait for protocol

    • Sliding window protocol

      • Back N Frame Protocol (GBN)
      • Select retransmission Protocol (SR)

  3. Reliable transmission, sliding window, flow control

    • Reliable transmission: what the sender sends and what the receiver receives
    • Flow control: Control the sending speed so that the receiver has enough buffer space to accept each frame
    • Sliding Windows: flow control (limiting transmission size) and reliable transmission (retransmission mechanism)

3.4.1 Stop the Waiting protocol

  1. In the absence of mistakes

  2. If something goes wrong

    • Data frame loss or frame error detected

    • ACK is missing

    • ACK late

  3. Performance analysis

    Low channel utilization

  4. Channel utilization

3.4.2 line

Rdt3.0 is a well-functioning transport protocol, but the special performance of its stop-wait protocol (waiting for an ACK from the receiver before entering the state of waiting for a call from the upper layer) causes inefficiencies.

Workaround: Does not run in a pause mode, allowing the sender to send multiple packets without waiting for confirmation. This technique is calledAssembly line.

The impact of assembly line:

  • The ordinal range must be increased because each group must have a unique identifier
  • The sender and receiver of the protocol must cache multiple packets
  • The buffering requirements of the desired sequence number range depend on how the data transfer protocol handles lost, corrupted, and delayed packets. There are two basic methods to solve pipeline error recovery: N step back (GBN) and selective retransmission (SR)

3.4.3 Rolling Back the N-Step Protocol (GBN)

  1. N Step rollback protocol (GBN, sliding window protocol) : allows sending sending multiple packets without waiting for confirmation. However, the number of unconfirmed packets cannot exceed a certain maximum value N. The receiver window is 1.

  2. The reason for setting N is traffic control and congestion control

    If k bits are numbered, the n of the sending window should be 1<= n <= 2^ k-1. Because the window size is too large, the receiver cannot distinguish between the new frame and the old frame.

  3. Events that the GBN protocol responds to:

    • The sender:
      • When the upper layer calls
        • The window is full. Tell the sender to wait
        • The window is full, a packet is generated and transmitted
      • Received an ACK
        • The window slides to the right
        • In GBN protocol, cumulative confirmation is adopted for n-frame, that is, all frames before receiving N-frame are accepted.
      • Timeout event
        • The meaning of N frame rollback is that the timer will resend all the frames that have been sent but have not been confirmed when a frame is lost or with a long delay.
    • Receiver:
      • The packet numbered N is received correctly and, in order, an ACK is issued for n
      • In all other cases, the receiver discards the packet and resends the ACK by selecting the packet with the closest sequence

Example:

3.4.4 Selecting the Retransmission Protocol (SR)

  1. GBN protocol problems:

    In order to ensure the correct order of grouping, the sliding window protocol retransmits data, but considering the large window length and bandwidth, it will cause efficiency problems caused by repeated transmission.

  2. Select the event to retransmit the response

    • The sender:
      • When the upper layer calls
        • The window is full. Tell the sender to wait
        • The window is full, a packet is generated and transmitted
      • Received an ACK
        • If the minimum window ordinal number is received, the window slides right to the next unacknowledged frame.
        • In other cases, the received frames are cached.
      • Timeout event
        • When each frame has its own timer, a frame is retransmitted when it times out.
    • Receiver:
      • Received a frame regardless of the serial number is cached, and return a confirmation frame, until all the frames in the sliding window have been accepted before a batch of frames are delivered to the upper layer, and then the window sliding.

Example:

3.5 Media Access Control

  1. Two types of links used to transmit data

    • Point-to-point link
      • Two adjacent nodes are connected by a link without a third party
      • Application: PPP protocol, commonly used in wide area networks
    • Broadcast link
      • All hosts share media
      • Applications: Early Ethernet, wireless LAN, often used for LAN
      • Classic topology: bus, star

  2. Media access control

    Some measures should be taken to prevent the communication between two pairs of nodes from interfering with each other

    Contrast:

3.5.1 Channel Division Media access control

Channel division Media access control: isolate communication between each device using media and other devices on the same channel, and allocate resources in time domain and frequency domain reasonably to devices on the network

  • Frequency division multiplexing (FDM) : All users use different bandwidth resources at the same time.

  • TDM: All users occupy the same bandwidth at different times.

    STDM is improved TDM, which can dynamically allocate time slots

  • Wavelength Division multiplexing (WDM) : Frequency division multiplexing of light.

  • Code division multiplexing CDM: Differentiating according to transmitted data codes at the same time and frequency

3.5.2 Random Access Media Access control

  • ALOHA agreement

    • Pure ALOHA agreement

    • Slotted ALOHA protocol

    • Information transmission is inefficient

  • CSMA (Carrier Sense Multiple Access Protocol) : A channel is monitored before a frame is sent.

    • If the channel is busy: delay sending
    • If the channel is free:

      • 1 – insist on CSMA

      • Not insist on CSMA

      • P – insist on CSMA

      • To compare

  • CSMA/CD (Carrier Sense Multipoint Access/Collision Protocol)

    • The influence of propagation delay on carrier monitoring: the transmission of electromagnetic wave needs time, which may cause conflicts

    • The retransmission mechanism

    • The minimum frame length for Ethernet is 64B

  • CSMA/CA (Carrier Sense Multipoint Access/Collision Avoidance Protocol)

    • The working principle of

    • Contrast CSMA/CD

3.5.3 Polling media Access control

  • Polling protocol

  • Token passing protocol

3.6 LAN

  1. Network topology

    Bus lines are better and are now in common use

  2. Transmission medium

  3. Media access control method

  4. Classification of LAN

  5. IEEE 802 series standards

    EEE 802, also known as LAN /MAN Standards Committee (LMSC), studies services and protocols defined in the physical layer and MAC layer of LAN and MAN, corresponding to the lowest two layers (physical layer and data link layer) of OSI network reference model.

  6. MAC sub-layer and LLC sub-layer

3.6.1 Ethernet

  1. Ethernet provides connectionless and unreliable services

    • No connection: There is no handshake between the sender and the receiver
    • Unreliable: the data frame number of the sender is not correct, the receiver does not confirm to the sender, the error frame is discarded directly, and the error correction is the responsibility of the high level

  2. Ethernet transmission media and the development of topology

  3. 10 base-t Ethernet

  4. Adapter and MAC address

  5. MAC frames for Ethernet

  6. High speed Ethernet

3.6.2 Wireless LAN

IEEE802.11 is a universal standard of wireless LAN. It is a wireless network communication standard defined by IEEE

  1. 802.11 MAC frame header format

  2. Wireless LAN classification

    • Wireless LAN with fixed infrastructure

    • A self-organizing network with no fixed infrastructure wireless LAN

3.7 the wan

3.7.1 PPP protocol

Point-to-point Protocol (PPP) is the most widely used data link layer Protocol. PPP is generally used when users access the Internet through dial-up phones

  1. Features: Only full-duplex links are supported

  2. Requirements met:

    • Simple: no error correction, no serial number, no flow control
    • Encapsulated into a frame
    • Transparent transmission
      • Asynchronous line: byte fill
      • Synchronous line: bit fill
    • Multiple network layer protocols: Encapsulated IP datagrams can use multiple protocols
    • Multiple types of links: serial/parallel, synchronous/asynchronous, electrical/optical
    • Error checking: Errors are discarded
    • Check the connection status: Whether the link is working properly
    • Maximum transmission unit: MTU, the maximum length of the data part
    • Network-layer address negotiation: The communication parties must know each other’s addresses
    • Data compression negotiation

  3. Requirements that need not be met

    • Error correction
    • Flow control
    • The serial number
    • Multi-point lines are not supported

  4. PPP consists of three parts

  5. PPP status diagram

  6. PPP frame format

3.7.2 in HDLC protocol

  1. In HDLC stand

  1. HDLC frame format

3.7.3 Comparison between PPP and HDLC

3.8 Devices at the Link Layer

  1. Classification of network Bridges

    • Transparent Bridges

    • Source routing bridge

  2. Multi-interface bridge – Ethernet switch

  3. Conflict domains and broadcast domains