Войти
Многие протоколы и алгоритмы требуют сериализации или перечисления связанных сущностей. Например, протокол связи должен знать, приходит ли какой-то пакет «до» или «после» другого пакета. IETF (Инженерная группа Интернета ) RFC 1982 пытается определить «Арифметику серийных номеров» с целью манипулирования и сравнения этих порядковые номера.
Эта задача намного сложнее, чем может показаться на первый взгляд, поскольку большинство алгоритмов используют представления фиксированного размера (двоичные ) для порядковых номеров. Часто важно, чтобы алгоритм не «ломался», когда числа становятся настолько большими, что они увеличиваются в последний раз и «оборачиваются» вокруг своих максимальных числовых диапазонов (мгновенно переходят от большого положительного числа к 0 или большому отрицательному числу). число). К сожалению, некоторые протоколы предпочитают игнорировать эти проблемы и просто используют очень большие целые числа для своих счетчиков в надежде, что программа будет заменена (или они будут выведены из эксплуатации) до того, как возникнет проблема (см. Y2K ).
Многие протоколы связи применяют арифметику серийных номеров к порядковым номерам пакетов в своей реализации протокола скользящего окна. Некоторые версии TCP используют защиту от упакованных порядковых номеров (PAWS). PAWS применяет ту же арифметику серийных номеров к отметкам времени пакетов, используя отметку времени как расширение старших битов порядкового номера.
Только добавление небольшого положительного числа целое число к порядковому номеру и сравнение двух порядковых номеров. Обсуждаются только двоичные реализации без знака с произвольным размером в битах, отмеченным в RFC (и ниже) как «SERIAL_BITS».
Добавление целого числа к порядковому номеру - это простое сложение целого числа без знака, за которым следует беззнаковая операция по модулю, чтобы вернуть результат в диапазон (обычно неявно в беззнаковом кроме того, на большинстве архитектур.)
s '= (s + n) по модулю (2 ^ SERIAL_BITS)
Добавление значения вне диапазона
[0.. (2 ^ (SERIAL_BITS - 1) - 1)]
не определено. По сути, добавление значений за пределами этого диапазона приведет к "переносу" результирующего порядкового номера и (часто) к получению числа, которое считается "меньше" исходного порядкового номера!
Представлено средство сравнения двух порядковых номеров i1 и i2 (беззнаковые целочисленные представления порядковых номеров s1 и s2).
Равенство определяется как простое числовое равенство. Алгоритм, представленный для сравнения, очень сложен, поскольку необходимо учитывать, близок ли первый порядковый номер к «концу» его диапазона значений, и, таким образом, меньшее «свернутое» число может фактически считаться «большим», чем первое. Последовательность чисел. Таким образом, i1 считается меньше i2, только если:
(i1 < i2 and i2 - i1 < 2^(SERIAL_BITS - 1)) or (i1>i2 и i1 - i2>2 ^ (SERIAL_BITS - 1))
Аналогично, i1 считается больше i2, только если:
(i1 < i2 and i2 - i1>2 ^ (SERIAL_BITS - 1)) или (i1>i2 и i1 - i2 < 2^(SERIAL_BITS - 1))
Алгоритмы, представленные в RFC, имеют По крайней мере, один существенный недостаток: существуют порядковые номера, для которых сравнение не определено. Поскольку многие алгоритмы независимо реализуются несколькими независимыми взаимодействующими сторонами, часто невозможно предотвратить возникновение всех таких ситуаций.
Хотя можно было бы определить тест таким образом, чтобы неравенство не обладало этим удивительным свойством, хотя определено для всех пар значений, такое определение было бы излишне обременительным для реализации и трудным для понимания, и все же допускало бы случаи, когда s1 < s2 and (s1 + 1)>(s2 + 1), что так же неинтуитивно. Таким образом, проблемный случай осталось неопределенным d, реализации могут возвращать либо результат, либо отмечать ошибку, и пользователи должны позаботиться о том, чтобы не зависеть от какого-либо конкретного результата. Обычно это означает недопущение сосуществования этих конкретных пар чисел.
Таким образом, часто бывает трудно или невозможно избежать всех «неопределенных» сравнений порядковых номеров. Однако доступно относительно простое решение. Путем отображения беззнаковых порядковых номеров на арифметические операции знакового дополнения до двух определяется каждое сравнение любого порядкового номера, а сама операция сравнения значительно упрощается. Все сравнения, указанные в RFC, сохраняют свои исходные значения истинности; затрагиваются только ранее "неопределенные" сравнения.
Алгоритм RFC 1982 определяет, что для N-битных порядковых номеров учитывается 2-1 значения «больше чем», а 2−1 считается «меньше чем». Сравнение с оставшимся значением (точно 2 отстоящих) считается «неопределенным».
Большинство современных аппаратных средств реализует подписанные двоичные дополнения двоичные арифметические операции. Эти операции полностью определены для всего диапазона значений для любых заданных им операндов - поскольку любое N-битное двоичное число может содержать 2 различных значения, и поскольку одно из них занято значением 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 являются беззнаковыми двоичными представлениями порядковых номеров s1 и s2, расстояние от s1 до s2 равно:
distance = (signed) (i1 - i2)
Если расстояние равно 0, числа равны. Если это < 0, then s1 is "less than" or "before" s2. Simple, clean and efficient, and fully defined. However, not without surprises.
Вся арифметика порядковых номеров должна иметь дело с "переносом" порядковых номеров; число 2 равноудалено в обоих направлениях в терминах порядковых номеров RFC 1982. В нашей математике они оба считаются "меньше" друг друга:
distance1 = (подписанный) (0x8000 - 0x0) == (подписанный) 0x8000 == -32768 < 0 distance2 = (signed)(0x0 - 0x8000) == (signed)0x8000 == -32768 < 0
Очевидно, что это верно для любых двух порядковые номера с расстоянием между ними 0x8000.
Кроме того, реализация арифметики серийных номеров с использованием арифметики дополнения до двух подразумевает серийные номера битовой длины, соответствующие целочисленным размерам машины; обычно 16-, 32- и 64-разрядные. Реализация 20-битных серийных номеров требует сдвигов (при условии 32-битных целых чисел):
distance = (signed) ((i1 << 12) - (i2 << 12))
