This is a reading note for “Computer Networks: Top-down Approach”. Some knowledge points that are too simple and partial to the door will be ignored, such as the knowledge of the application layer, which is often contacted, need not be described.

Transport layer

Connectionless transport: UDP

UDP only implements multiplexing (port) and verification on the basis of IP protocol, does not guarantee delivery and sequential delivery, although simple but has the following advantages:

  • The application layer has more fine-grained control over when and what data to send;
  • No connection required;
  • No connection state;
  • The packet head has low overhead.

The header has only four fields: source port, destination port, length, and checksum. The UDP of the sender performs an inverse code operation on all 16-bit words in the packet segment, and any overflow encountered during summation is rolled back. At the receiver, the full 16-bit words (including checkouts and) are added together, and if no errors are introduced in this grouping, it is obvious that at the receiver the sum will be 1111111111111111.

Principle of reliable data transmission

How to realize reliable transmission on unreliable channel, we can get reliable transmission protocol step by step according to the characteristics of channel from simple to complex.

Reliable data transmission over fully reliable channels

In a reliable channel you simply send and receive.

  • The sender

  • The sender

Reliable data transmission over bit-error channels

This situation requires the Automatic Retransmission request protocol to handle and requires three mechanisms to handle bit errors:

  1. Error detection, which requires a mechanism for the receiver to detect when a bit error has occurred;
  2. Recipient feedback: Positive acknowledgement (ACK) and negative acknowledgement (NAK) by recipient;
  3. Retransmission: If the receiver receives an incorrect packet, the sender retransmits the packet.

An intuitive scenario is to send the next packet upon receipt of an ACK, resend it upon receipt of an NAK, and then confirm that the packet itself is corrupt. When the sender receives a damaged acknowledgement packet, it needs to retransmit the current packet. However, this approach introduces redundant packets in the sender to receiver channel, which requires the sender to number its data packets to confirm whether the received packets are retransmitted. In addition, if instead of sending an NAK, the sender sends an ACK for the packet that was correctly received last time, the sender knows that the recipient did not correctly receive the packet that followed the packet that was acknowledged twice.

  • The sender

  • The receiving party

Reliable data transmission over packet loss channels with bit errors

For packet loss channels, on the one hand, lost data needs to be retransmitted, and on the other hand, a backcount timer is needed to realize timeout retransmission. The sender needs to do:

  1. Each time a packet is sent, a timer is started.
  2. The response timer is interrupted.
  3. Terminate the timer.
  • The sender

Pipelined reliable data transfer protocol

The channel utilization rate of stop and wait protocol is low. A better method is to use pipeline to send and confirm multiple packets at a time. The protocol needs to make the following extensions:

  • Must increase serial number range;
  • Both sender and receiver of the protocol may have to cache multiple packets;
  • There are two basic methods to solve the error recovery of pipeline: N step back and selective retransmission.
Step back N

The number of unconfirmed packets in the pipeline cannot exceed the window size N. The packet pipeline seen by the protocol sender is as follows:

  • Base number is the number of the earliest unconfirmed group;
  • The next sequence number (nextseqnum) is the smallest unused sequence number;

The sender must respond to three types of events:

  • Upper-level call: when called by the upper layerrdt_send(), the sender first checks whether the send window is full. If the window is full, a group is generated and sent, and the variables are updated accordingly. If the window is full, the sender informs the upper layer that the window is full.
  • Receive an ACK: Acknowledgement of the packet numbered N is cumulative acknowledgement, indicating that the recipient has correctly received all previous and included packets numbered several.
  • Timeout event: If a timeout occurs, the sender retransmits all packets that have been sent but have not been acknowledged.

Thus the complete agreement is as follows:

  • The sender

  • The receiving party

Select the retransmission

If you roll back N steps, the received packets will be transmitted, resulting in a waste of sexual resources. However, you only need to retransmit the lost or damaged packets. The pipeline seen by the sender and receiver is as follows:

The sender’s events and actions are as follows:

  1. Receive data from the upper layer. The same as the N step rollback.
  2. Timeout. Now each packet must have its own logical timer because only one packet can be sent after a timeout occurs;
  3. Receives an ACK. If an ACK is received, the sender marks the acknowledged packet as received if the packet number is in the hole. If the group’s ordinal number is equal to send_base, the window base ordinal number moves forward to the unacknowledged group with the minimum ordinal number. If the window moves and the order number falls on unsent groups within the window, these groups are sent.

Connection-oriented transportation: TCP

TCP implements a reliable end-to-end data transmission channel (reliable and ordered) over the unreliable IP protocol. TCP is a byte stream. The maximum length of packet segments is extracted from the buffer to form packets. The header of the TCP packet segment is as follows

  • 32 bit serial number field and 32 bit confirmation number field;
  • A 16-bit receive window field that indicates the number of bytes the receiver is willing to accept;
  • Header length field indicating the length of the TCP header in 32-bit words;
  • Optional and variable-length option field;
  • A 6-bit flag field, with ACK bits to indicate that the value in the acknowledgment field is valid, and RST, SYN, and FIN bits for connection establishment and disconnection.

TCP’s serial number is based on the byte stream transmitted, so the serial number of a packet segment is the byte stream number of the first byte of the packet segment, and the acknowledgement number that the host fills into the packet segment is the serial number of the next byte that the host expects to receive from the host. TCP uses cumulative acknowledgement.

The overall operation logic of the TCP sender is as follows

NextSeqNum=InitialSeqNumber
SendBase=InitialSeqNumber

loop (forever) {
    switch(event) {
        event: data received from application above
            create TCP segment with sequence number NextSeqNum
            if (timer currently not running)
                start timer
            pass segment to IP
            NextSeqNum=NextSeqNum+length(data)
            break;
        event: timer timeout
            retransmit not-yet-acknowledged segment with
            smallest sequence number
                start timer
            break;
        event: ACK received, with ACK field value of y
            if (y > SendBase) {
                SendBase=y
                if (there are currently any not-yet-acknowledged segments)
                    start timer
            }
            break; }}/* end of loop forever */
Copy the code

TCP involves the following technical points:

  • Round-trip time estimates and timeouts: The mean value of RTT (EstimatedRTT) and variance (DevRTI) need to be calculated, so that the timeout time can be calculated:;
  • Reliable data transmission
    • Double timeout interval: Each TCP retransmission sets the next timeout interval to twice the previous value.
    • Fast retransmission: TCP performs fast retransmission once three redundant ACKS are received.
    • Flow control: TCP does this by having the sender maintain a receive window, which tells the sender how much cache space the receiver has available.

A TCP connection is established through a three-way handshake

  1. The client sends a SYN packet with a randomly selected initial sequence number (client_ISN).
  2. The server replies with a SYNACK message informing the randomly selected initial number (server_ISN) and acknowledging the receipt of the client_ISN.
  3. The client replies with an ACK packet confirming the receipt of server_ISN.

A TCP shutdown requires four handshakes, with one party sending a FIN and the other replying an ACK.

TCP congestion control

Congestion causes many problems:

  • When the packet arrival rate is close to the link capacity, the packet experiences huge queuing delay.
  • The sender must perform retransmission to compensate for discarded (lost) packets due to cache overflow.
  • Unnecessary retransmission by the sender in the event of large time delays causes the router to use its link bandwidth to forward unnecessary packet copies.
  • When a packet is discarded along a path, the traffic capacity used by each upstream router to forward the packet to the discarded packet is eventually wasted.

TCP uses the congestion window CWND to limit the rate of sending traffic. TCP defines packet loss events as either timeout occurs or redundant ACKS are received from the receiver. The adjustment mechanism of congestion window is as follows:

The network layer

The Internet’s protocol provides best-of-service, which seems to be a euphemism for no service at all.

How routers work

  • Input port: functions include performing the physical layer function of connecting an input physical link to the router, performing the data link layer function that needs to interact with the data link layer at the far end of the human link, and determining the output port of the router by querying the forwarding table (longest prefix matching);
  • Switching structure: switching structure connects the input port and output port of the circuit breaker, including memory switching, bus switching and Internet switching three forms;
  • Output port: The output port stores the packets received from the switching structure and transmits them over the input link by performing the necessary link layer and physical layer functions;
  • Routing processor: The routing processor executes routing protocols, maintains routing tables and link-state information for connections, and computes forwarding tables for routers.

Queuing occurs when an output port waits for more than one packet, and packet loss occurs when there is no memory available to store incoming packets. A packet scheduler on the output port must select one of these queued packets to send, such as first-come-first-served scheduling, weighted fair queuing, and so on. If there is not enough memory to cache a person group, then the group must be selected for discarding, with policies such as tail discarding and active queue management (such as random early detection).

Internet protocol: Forwarding and addressing on the Internet

The header of an IPv4 datagram is defined as follows

Key fields are as follows:

  • Version: IPv4 or IPv6;
  • Head length;
  • Service type;
  • Datagram length;
  • Logo, logo, slice offset: related to 1P sharding;
  • Life: The value of this field is reduced by one each time a datagram is processed by a router. If the TTL field is reduced to 0, the datagram must be discarded.
  • Protocol: Which specific transport layer protocol the data portion should be assigned to;
  • Header checksum: the checksum must be recalculated and stored again on each router because the TTL field and possible option fields will change;
  • Source and destination IP addresses;
  • Options;
  • The data.

When the packet size exceeds the maximum transmission unit of the link, the sender needs to fragment the packet. The fragmented packet is assembled by the final receiver using the identifier, flag, and slice offset field. A typical shard is as follows

slice byte ID The offset mark
1 piece 1480 777 0 1
2 pieces 1480 777 185 1
3 pieces 1020 777 370 0

IP addresses can be assigned manually or dynamically by DHCP. The DHCP process is as follows:

  • DHCP server discovery: The newly added host broadcasts a DHCP discovery message.
  • DHCP server provides: Broadcasts a DHCP service message to respond to the customer.
  • DHCP request: provides a DHCP request message to the selected server.
  • DHCP ACK: The server verifies the required parameters with A DHCP ACK message.

Routing algorithm

The routing problem can be summed up as the shortest path problem. The algorithm can be divided into global routing algorithm (link state algorithm) and distributed routing algorithm (distance vector algorithm) according to whether it is global or distributed, and can be divided into static routing algorithm and dynamic routing algorithm according to whether it is static or dynamic. According to the load sensitive or load insensitive algorithm can be divided into load sensitive algorithm and load insensitive algorithm.

  • Link state algorithm: let each node broadcast link state group to all other nodes in the network, and then use the shortest path algorithm to find the path;
  • Distance vector algorithm: Retrieves routing information from adjacent routes and updates the routing table using the Bellman-Ford formulaHowever, distance vector algorithms existInfinite countProblem, needToxicity of reverseTechnical solution.

The difference between the two is as follows

Link state algorithm Distance vector algorithm
Message complexity high low
The rate of convergence fast slow
Robustness, high low

The link layer

Link layer protocols are responsible for data transmission over a single link. Possible services include framing, link access, reliable delivery, error detection, and correction. Link layer protocols are typically implemented by network adapters.

Error detection and correction techniques

  • Parity check: data plus parity bits of the number of 1 is even or odd, using the parity check can even achieve error correction.
  • Tests and methods: The data is processed as a sequence of k-bit integers, the k-bit integers are added up, and the resulting sum is used as error detection bits.
  • Cyclic redundancy detection: For d bit data, the receiver uses G (R + L bits) to remove the received D + R bits. If the remainder is non-zero, the receiver knows that there is an error. Otherwise, the data is accepted as correct.

Switched LAN

The link layer addresses MAC addresses. MAC addresses and IP addresses correspond to ARP. Each host or router has an ARP table in its memory, which contains the mapping between IP addresses and MAC addresses and a TTL value. When a host encounters an unknown IP address, it constructs and broadcasts an ARP packet. The host that matches the ARP packet responds to the ARP packet.

The frame format of the Ethernet protocol is as follows

  • Data fields: The maximum transmission unit of Ethernet is 1500 bytes;
  • Destination address and source address;
  • Type field: know to which network layer protocol the contents of the data segment will be passed;
  • CRC: Detects whether an error has been introduced into the frame.
  • Pre-sync code: The first seven bytes of the pre-sync code are 10101010 and the last byte is 10101011.

The link layer switch maintains the switch table to complete forwarding and filtering, assuming that the destination address is XX and frames arrive from switch interface X:

  • For xx entries, the switch forwards a copy of the frame to the output cache in front of all interfaces other than interface X.
  • There is an entry in the table that associates XX with interface X. Discard this frame.
  • An entry in the table connects xx to interface Y! =x, the switch forwards the frame by placing it in the output cache of interface Y.

Switch tables are self-learning:

  1. The switch table is initially empty;
  2. For each incoming frame received at each interface, the switch stores it in its table;
  3. If, after a period of time, the switch does not receive a frame with that address as the source address, the address is removed from the table.

The advantages of link layer switches include collision elimination, heterogeneous links, and easy management. Disadvantages of a link layer switch over a router include: inability to handle broadcast frame loops, ARP tables related to device numbers, and inability to handle broadcast storms.