Приложение A. Реализация Ack Vector
В этом приложении обсуждаются детали обработки подтверждений DCCP в контексте абстрактной реализации Ack Vector. Приложение является информативным, а не нормативным.
Первая часть нашей реализации работает на стороне HC-Receiver и, следовательно, подтверждает пакеты данных. Эта часть генерирует опции Ack Vector. Реализация имеет следующие характеристики:
- не более 1 байта состояния на пакет подтверждения;
- время O(1) затрачивается на обновление состояния при доставке нового пакета (нормальная ситуация);
- кумулятивные подтверждения;
- быстрое удаление старого состояния.
Базовая структура данных представляет собой кольцевой буфер, содержащий информацию о подтвержденных пакетах. Каждый байт этого буфера содержит состояние и групповой код (run length); состояние может принимать значения 0 (пакет получен), 1 (пакет имеет маркер ECN) или 3 (пакет еще не получен). Начало буфера находится слева. Реализация поддерживает 5 переменных в дополнение к содержимому буфера:
- переменные buf_head и buf_tail показывают активную часть буфера;
- buf_ackno содержит значение Acknowledgement Number самого свежего подтвержденного пакета в буфере; этой переменной соответствует указатель head;
- buf_nonce представляет собой однобитовую сумму (четность или Исключающее ИЛИ) значений ECN Nonce, полученных во всех пакетах, подтверждаемых буфером со статусом State 0.
Вид буфера подтверждений показан на рисунке:
+---------------------------------------------------------------+
|S,L|S,L|S,L|S,L| | | | |S,L|S,L|S,L|S,L|S,L|S,L|S,L|S,L|
+---------------------------------------------------------------+
^ ^
buf_tail buf_head, buf_ackno = A buf_nonce = E
<=== buf_head and buf_tail move this way <===
Каждая пара "S,L" представляет байт State/Run length. Мы будем показывать только активную часть кольцевого буфера и добавлять комментарии, показывающие Acknowledgement Number для последнего активного байта в буфере. Пример показан ниже.
+-----------------------------------------------+ A |S,L|S,L|S,L|S,L|S,L|S,L|S,L|S,L|S,L|S,L|S,L|S,L| T BN[E] +-----------------------------------------------+
Здесь переменная buf_nonce имеет значение E, а buf_ackno = A. Будем использовать этот буфер в качестве рабочего примера.
+---------------------------+ 10 |0,0|3,0|3,0|3,0|0,4|1,0|0,0| 0 BN[1] [Example Buffer] +---------------------------+
Словами содержимое буфера можно описать так:
- пакет 10 был получен (начало буфера имеет порядковый номер 10, состояние 0 и run length 0);
- пакеты 9, 8 и 7 еще не получены (три следующих байта показывают состояние 3 и run length 0.)4
- пакеты 6, 5, 4, 3 и 2 были получены;
- пакет 1 имеет маркер ECN;
- пакет 0 был получен.
- Однобитовая сумма значений ECN Nonce для пакетов 10, 6, 5, 4, 3, 2 и 0 равна 1.
Кроме того HC-Receiver нужно сохранять некоторые данные о недавно переданных значениях Ack Vector. Для этого каждый пакет, содержащий Ack Vector, запоминается в 4 переменных:
ack_seqno содержит значение Sequence Number, использованное для пакета; это порядковый номер HC-Receiver;
ack_ptr — значение buf_head в момент подтверждения;
ack_runlen — групповой код (run length), находящийся в байте буфера данных с позицией buf_head в момент подтверждения;
ack_ackno — значение Acknowledgement Number, использованное для пакета; это порядковый номер HC-Sender; поскольку подтверждения являются кумулятивными, один номер полностью задает всю информацию о пакете, подтверждаемом данным значением Ack Vector;
ack_nonce — 1-битовая сумма ECN Nonce для всех пакетов со State 0 в буфере между позициями buf_head и ack_ackno, включительно; изначально эта переменная равна значению Nonce Echo в Ack Vector подтверждения (или, если пакет подтверждения содержит несколько опций Ack Vector, «исключающее ИЛИ» для всех Ack Vector); значение переменной меняется по мере удаления данных о старых подтверждениях (сближение ack_ptr и buf_head) и прибытия старых пакетов (смена State 3 или State 1 на State 0).