Многие протоколы и алгоритмы требуют сериализации или перечисления связанных сущностей. Например, протокол связи должен знать, приходит ли какой-то пакет «до» или «после» другого пакета. В IETF ( Internet Engineering Task Force ) RFC 1982 попытки определить «серийный номер арифметику» для целей манипулирования и сопоставления этих порядковых номеров .
Эта задача гораздо сложнее, чем может показаться на первый взгляд, потому что большинство алгоритмов используют представления фиксированного размера ( двоичные ) для порядковых номеров. Часто важно, чтобы алгоритм не «ломался», когда числа становятся настолько большими, что они увеличиваются в последний раз и «оборачиваются» вокруг своих максимальных числовых диапазонов (мгновенно переходят от большого положительного числа к 0 или большому отрицательному числу. ). Некоторые протоколы предпочитают игнорировать эти проблемы и просто используют очень большие целые числа для своих счетчиков в надежде, что программа будет заменена (или они выйдут из эксплуатации) до того, как возникнет проблема (см. Y2K ).
Многие протоколы связи применяют арифметику серийных номеров к порядковым номерам пакетов в своей реализации протокола скользящего окна . Некоторые версии TCP используют защиту от упакованных порядковых номеров (PAWS) . PAWS применяет ту же арифметику серийных номеров к отметкам времени пакетов, используя отметку времени как расширение старших битов порядкового номера. [1]
Операции с порядковыми номерами [ править ]
Обсуждаются только добавление небольшого положительного целого числа к порядковому номеру и сравнение двух порядковых номеров. Обсуждаются только двоичные реализации без знака с произвольным размером в битах, отмеченным в RFC (и ниже) как «SERIAL_BITS».
Дополнение [ править ]
Добавление целого числа к порядковому номеру представляет собой простое сложение целого числа без знака, за которым следует операция по модулю без знака, чтобы вернуть результат в диапазон (обычно неявно в беззнаковом сложении на большинстве архитектур):
s '= (s + n) по модулю (2 ^ SERIAL_BITS)
Добавление значения вне диапазона
[0 .. (2 ^ (SERIAL_BITS - 1) - 1)]
не определено. По сути, добавление значений за пределами этого диапазона приведет к "переносу" результирующего порядкового номера и (часто) к получению числа, которое считается "меньше" исходного порядкового номера.
Сравнение [ править ]
Представлены средства сравнения двух порядковых номеров i1и i2(беззнаковые целочисленные представления порядковых номеров s 1 и s 2 ).
Равенство определяется как простое числовое равенство. Алгоритм, представленный для сравнения, является сложным, поскольку необходимо учитывать, близок ли первый порядковый номер к «концу» его диапазона значений, и, таким образом, меньшее «свернутое» число может фактически считаться «большим», чем первая последовательность. номер. Таким образом i1считается меньше, чем i2только если
(i1 <i2 и i2 - i1 <2 ^ (SERIAL_BITS - 1)) или(i1> i2 и i1 - i2> 2 ^ (SERIAL_BITS - 1))
Точно так же i1считается большим, чем i2только если
(i1 <i2 и i2 - i1> 2 ^ (SERIAL_BITS - 1)) или(i1> i2 и i1 - i2 <2 ^ (SERIAL_BITS - 1))
Недостатки [ править ]
Алгоритмы, представленные в RFC, имеют как минимум один существенный недостаток: существуют порядковые номера, для которых сравнение не определено. Поскольку многие алгоритмы независимо реализуются несколькими независимыми взаимодействующими сторонами, часто невозможно предотвратить возникновение всех таких ситуаций.
Авторы RFC 1982 признают это, не предлагая общего решения:
Хотя можно было бы определить тест таким образом, чтобы неравенство не обладало этим удивительным свойством, хотя оно было определено для всех пар значений, такое определение было бы излишне обременительным для реализации, трудным для понимания и все же разрешить случаи, когда
s1 <s2 и (s1 + 1)> (s2 + 1)что так же неинтуитивно.
Таким образом, проблемный случай остается неопределенным, реализации могут возвращать либо результат, либо отмечать ошибку, и пользователи должны позаботиться о том, чтобы не зависеть от какого-либо конкретного результата. Обычно это означает недопущение сосуществования этих конкретных пар чисел.
Таким образом, часто бывает трудно или невозможно избежать всех «неопределенных» сравнений порядковых номеров. Однако доступно относительно простое решение. Путем сопоставления беззнаковых порядковых номеров с дополнительными арифметическими операциями со знаком до двух определяется каждое сравнение любого порядкового номера, а сама операция сравнения значительно упрощается. Все сравнения, указанные в RFC, сохраняют свои исходные значения истинности; затронуты только ранее "неопределенные" сравнения.
Общее решение [ править ]
В RFC 1982 алгоритм определяет , что для N -разрядного порядковыми номерами, в которых есть 2 ( N - 1) - 1 значения считаются «больше чем» и 2 ( N - 1) - 1 считается «меньше чем». Сравнение с оставшимся значением (точно 2 N -1 ) считается «неопределенным».
Большинство современных аппаратных средств реализует двоичные арифметические операции с дополнением до двух со знаком. Эти операции полностью определены для всего диапазона значений для любых заданных им операндов, поскольку любое N- битное двоичное число может содержать 2 N различных значений, а поскольку одно из них занято значением 0, существует нечетное число. пятен осталось для всех ненулевых положительных и отрицательных чисел. Просто представимых отрицательных чисел на одно число больше, чем положительных. Например, 16-битное значение дополнения до 2 может содержать числа в диапазоне от -32768 до +32767.
Таким образом, если мы просто переопределим порядковые номера как целые числа с дополнением до 2 и допустим, что еще один порядковый номер считается «меньше чем», чем порядковые номера, считающиеся «больше чем», мы сможем вместо этого использовать простые арифметические сравнения со знаком логически неполной формулы, предложенной RFC.
Вот несколько примеров (снова в 16 битах), сравнивающих некоторые случайные порядковые номера с порядковым номером со значением 0:
беззнаковый двоичный подписанныйрасстояние значения последовательности-------- ------ -------- 32767 == 0x7FFF == 32767 1 == 0x0001 == 1 0 == 0x0000 == 0 65535 == 0xFFFF == -1 65534 == 0xFFFE == −2 32768 == 0x8000 == −32768
Легко видеть, что знаковая интерпретация порядковых номеров находится в правильном порядке, если мы «вращаем» рассматриваемый порядковый номер так, чтобы его 0 совпадал с порядковым номером, с которым мы его сравниваем. Оказывается, это просто делается с помощью беззнакового вычитания и простой интерпретации результата как знакового дополнения до двух. В результате получается «расстояние» со знаком между двумя порядковыми номерами. Еще раз, если i1и i2являются беззнаковыми двоичными представлениями порядковых номеров s 1 и s 2 , расстояние от s 1 до s 2 равно
расстояние = (со знаком ) ( i1 - i2 )Если расстояние равно 0, числа равны. Если он <0, то s 1 «меньше» или «до» s 2 . Просто, чисто, эффективно и полностью определено. Однако не обошлось и без сюрпризов.
Вся арифметика порядковых номеров должна иметь дело с «упаковкой» порядковых номеров; число 2 N -1 равноудалено в обоих направлениях в терминах порядковых номеров RFC 1982 . В нашей математике они оба считаются «меньше, чем» друг друга:
distance1 = ( подписано ) ( 0x8000 - 0x0 ) == ( подписан ) 0x8000 == -32768 < 0 distance2 = ( подписано ) ( 0x0 - 0x8000 ) == ( подписан ) 0x8000 == -32768 < 0Это, очевидно, верно для любых двух порядковых номеров с расстоянием между ними 0x8000.
Более того, реализация арифметики серийных номеров с использованием арифметики с дополнением до двух подразумевает серийные номера битовой длины, соответствующие целочисленным размерам машины; обычно 16, 32 и 64 бит. Реализация 20-битных серийных номеров требует сдвигов (при условии 32-битных целых чисел):
расстояние = (со знаком ) (( i1 << 12 ) - ( i2 << 12 ))См. Также [ править ]
Ссылки [ править ]
- ^ RFC 1323 : «Расширения TCP для высокой производительности», раздел 4.2.
Внешние ссылки [ править ]
- RFC 2182
- RFC 1982
