My Github address

Notes on data Structures and Algorithms

Notes for geek Time iOS Developer Class

IOS large factory interview high frequency algorithm summary

Summary of iOS interview materials

Reliable transport

Stop waiting for ARQ

  • ARQ (Automatic Repeat-reQuest) Automatic retransmission reQuest

Continuous ARQ + sliding window protocol

  • The size of the sliding window is determined by the recipient’s cache size.

SACK (Selective confirmation)

  • inTCPDuring communication, if a packet is lost in the middle of the sending sequence (e.gOne, two, three, four, fiveIn the3Lost)
  • TCPThe last confirmed packet will be retransmitted to subsequent packets (last confirmed is2The retransmission3，4，5)
  • Thus packets that were correctly transmitted before may also be sent repeatedly (e.g4, 5), decreasedTCPperformance
  • In order to improve the above situation, developedSACKThe Selective Acknowledgement technology
    • Tell the sender which data is missing and which data has been received in advance
    • Cause TCP to resend only lost packets (e.g3), instead of sending all subsequent groupings (e.g4, 5)
  • SACKThe information will be placedTCPThe options section of the header
    • KindAccounts for:1Bytes. A value of5Represents the isSACKoptions
    • LengthAccounts for:1Bytes. Show thatSACKThe total number of bytes used by options
    • Left EdgeAccounts for:4Byte, left margin
    • Right EdgeAccounts for:4Byte, right margin

  • A pair of boundary information needs to be occupied8Bytes due toTCPThe header has the most options40Two bytes, so
    • SACKMaximum number of options4Group boundary information
    • SACKThe maximum number of bytes for the option =4 times 8 plus 2 is 34

doubt

  • If a packet is retransmittedNWill it continue to be transmitted to success until it fails?
    • It depends on the system setup, like some systems, retransmission5It will be sent before the first attempt is successfulresetThe RST is disconnectedTCPThe connection

  • If the receive window can receive up to 4 packets, but the sender only sends 2 packets, how can the receiver determine if there are 2 packets to follow?
    • If there is no third packet after a certain amount of time, an acknowledgement is returned to the sender that two packets were received
  • Why do you choose to “slice” the data into multiple segments at the transport layer, rather than waiting for the network layer to slice the data to the data link layer?
    • Because it improves retransmission performance
    • To be clear: Reliable transport is controlled at the transport layer

      • If there is no fragmentation at the transport layer, the entire transport layer must be retransmitted once data is lost

      • If there are segments at the transport layer, once data is lost, only those segments need to be retransmitted

Flow control

  • If the receiver’s cache is full, the sender is still sending data like crazy
    • The receiver can only discard the received data packets. A large number of packet loss will greatly waste network resources
    • So flow control
  • What is flow control?
    • Make the sending rate of the sender not too fast, so that the receiver can receive processing in time
  • The principle of
    • The sending rate of the sender is controlled by acknowledging the window field in the packet
    • The size of the sender’s send window cannot exceed the size given by the receiver
    • When the sender receives the size of the receive window is0“, the sender will stop sending data

doubt

  • There is a special case
    • At the beginning, the receiver sent to the sender0The message segment of the window
    • Later, the receiver has some storage space to send to the sender0The message segment of the window is missing
    • The sender’s sending window remains at zero, and the two sides are at an impasse
  • The solution
    • When the sender receives0Window notification: The sender stops sending packets
    • At the same time, a timer is started and a test message is sent at intervals to ask the receiver about the latest window size
    • If the receiving window is still0, the sender refreshes the start timer again

Congestion control

  • Congestion control
    • Prevent too much data from being injected into the network
    • Avoid overload of routers or links on the network
  • Congestion control is a global process
    • It involves all hosts, routers
    • And all factors related to the degradation of network transmission performance
    • It was the result of our joint efforts
  • By contrast, flow control is the control of point-to-point communication

Slow start

  • The key word
    • MSS (Max Segment Size): The maximum size of the data part for each segment
      • Set when establishing a connection
    • RWND (receive window): Receiving window
    • CWND (Congestion window): Congested Windows
    • SWND (Send Window): Send window
      • swnd = Min (CWND, RWND)

  • cwndThe initial value of the packet is small, and then as the packet is acknowledged by the receiver (one is receivedACK)
    • cwndThey multiply

Congestion avoidance (obsolete, using fast recovery described below)

  • ssthresh(slow start threshold): Slow start threshold,cwndWhen a threshold is reached, it increases in a linear fashion
  • Congestion avoidance (increase in addition) : The congestion window slowly increases to prevent premature network congestion
  • Multiplication reduction: As long as the network congestion, thessthreshAt the same time, the slow start algorithm (cwndReturn to initial value)
    • When network congestion occurs frequently,ssthreshThe value goes down very quickly

Fast retransmission

  • The receiving party
    • Repeat acknowledgements are issued as soon as each out-of-order packet is received
    • To let the sender know in time that the packet has not arrived
    • Instead of waiting for your own data to be sent
  • The sender
    • As long as three consecutive repeated confirmations are received (total4The segment that has not been received by the other party should be retransmitted immediately
    • You do not have to wait for the retransmission timer to expire

Fast recovery

  • When the sender receives three repeated acknowledgements in a row, the “multiplication reduction” algorithm is performed, and thessthreshhalve
    • The difference from slow start is that the slow start algorithm is now not executed, i.ecwndDo not restore to initial value now
    • But thecwndValue is set tossthreshHalf the value
    • The congestion avoidance algorithm (” add up “) is then executed, slowly increasing the congestion window linearly

Maximum value of the send window

  • Maximum value of send window:SWND = min (CWND, RWND)
  • whenrwnd < cwndIs the maximum value of the sending window that is limited by the receiving capability of the receiver
  • whencwnd < rwndIs the maximum value of the network congestion limit send window