Sequence number

from Wikipedia, the free encyclopedia

Sequence numbers are used in reliable network protocols (such as TCP ) in order to implement a complete transmission in the correct order and without duplicates (i.e. a data stream ). Sequence numbers are also used in databases and operating systems to secure atomic operations .

Sequence numbers are a trivial form of the Logical Clock : They provide a means by which messages can be sorted according to their causality . However, only one actor is taken into account - if the causality is decisive for the overall system of all communication partners (as with some reliable multicast protocols), more complex logic clocks must be used, such as the Lamport clock or vector clocks .

General scheme

From the sequence numbers of the previous packets, the recipient knows which sequence number the next incoming packet should have. If a message with a lower sequence number is received, it is rejected because it has already been received once. If a message with a higher sequence number is received, this and all subsequent messages with an even higher sequence number are stored in a buffer. The messages from the buffer are only processed when the message has arrived with the correct sequence number.

If no message with the desired sequence number arrives within a certain period of time, the sender is asked to send this message again. If the requested message still does not arrive after a certain number of queries, communication is broken off with an error message.

Calculation of the sequence number space

Since one of the overhead by the sequence numbers in the packet header would like to minimize, one determines the size of the sequence number space by the following formula . Explanation of the parameters:

  • n denotes the number of bits in the sequence number space
  • MPL is the maximum packet lifetime in seconds
  • T is the maximum time in which a retransmission is carried out
  • A is the maximum time before the recipient sends an acknowledgment after receiving the data
  • R the maximum transmission rate of the sender (packets / second).

See also

time stamp