QUICのパケット番号のエンコーディング/デコーディングについて

QUICクライアントの、接続の実装をしているときには動作に問題がなかったので気が付かなかったのですが、パケット番号のエンコーディング、デコーディングが必要になります。

パケット番号は0～2⁶²-1 までの値をとります。一方で、QUICのパケットのフォーマットを見ると、1～4バイトまでしか格納できません。なので、そのままではパケット番号を格納することができなくなります。

パケット番号を格納するために、パケット番号の下位ビットのみを含めます。これにより必要となるビット数を削減できます。

パケット番号のエンコーディングとデコーディングは、RFC 9000 17.1. Packet Number Encoding and Decoding で説明されています。

エンコーディング

エンコーディングでは、パケット番号の下位ビットのみを送るようにします。

これから送信するパケット番号と最大のACKされたパケット番号の差分の2倍を格納できるサイズを使います。

あるパケット番号空間でACKを受け取っていない場合は、パケット番号全体を使用します。

パケット番号のサイズは、今から送信しようとしているパケット番号と、最大のACKされているパケット番号の差分を表すのに必要なビット数+1ビットになります。

RFC 9000 のA.2. Sample Packet Number Encoding Algorithm に疑似コードが書かれています。

疑似コードでは、EncodePacketNumber(Full_pn, largest_acked) という関数でパケット番号のエンコーディングアルゴリズムを説明しています。

full_pn は、送信するパケットのパケット番号です。 largest_acked は、今のパケット番号空間でackされた最大のパケット番号です。

疑似コードは以下のようになっています。

EncodePacketNumber(full_pn, largest_acked):

  // The number of bits must be at least one more
  // than the base-2 logarithm of the number of contiguous
  // unacknowledged packet numbers, including the new packet.
  if largest_acked is None: // ①
    num_unacked = full_pn + 1 // ②
  else:
    num_unacked = full_pn - largest_acked // ③

  min_bits = log(num_unacked, 2) + 1 // ④
  num_bytes = ceil(min_bits / 8)  // ⑤

  // Encode the integer value and truncate to
  // the num_bytes least significant bytes.
  return encode(full_pn, num_bytes) // ⓺

まずACKされたパケット番号 (largest_acked)があるのかを確認します(①)。

もしACKされたパケットが存在しない場合、num_unackedは、これから送ろうとしているパケット番号+1にします(②)。

そうではない場合、num_unackedは、full_pn - largest_acked とします(③)。

次に、必要となるビット数を計算します（④）。

そして、min_bits を8で割ったもののceilをとり、必要となるバイト数を計算します（⑤）。

最後に、full_pnに対して、(1<<num_bytes)-1で & を取ります（⓺）。

具体例

RFC9000 には2つサンプルが書かれているのでそのうち1つを紹介します。

largest_ackedを 11266227 とします。 full_pn を 11295746 とします。

そうすると、この2つの差が29519となります。

この2倍 59,038 は 2進数で表すと 0b 1110'0110'1001'1110 となります。 なので16ビット必要です。なのでパケット番号は2バイト使います。

デコーディング

パケット番号のデコーディングは、RFC9000 の A.3. Sample Packet Number Decoding Algorithm に疑似コードが書かれています。

疑似コードでは、DecodePacketNumber(largest_pn, truncated_pn, pn_nbits) という関数でパケット番号のエンコーディングアルゴリズムを説明しています。

largest_pnは、現在のパケット番号空間で処理に成功した最大のパケット番号です。

truncated_pn は、パケット番号の値です

pn_nbits はパケット番号のビット数です。(8, 16, 24, 32)

疑似コードは以下のようになっています。

DecodePacketNumber(largest_pn, truncated_pn, pn_nbits):
   expected_pn  = largest_pn + 1 // ①
   pn_win       = 1 << pn_nbits // ②
   pn_hwin      = pn_win / 2 // ③
   pn_mask      = pn_win - 1 // ④
   // The incoming packet number should be greater than
   // expected_pn - pn_hwin and less than or equal to
   // expected_pn + pn_hwin
   //
   // This means we cannot just strip the trailing bits from
   // expected_pn and add the truncated_pn because that might
   // yield a value outside the window.
   //
   // The following code calculates a candidate value and
   // makes sure it's within the packet number window.
   // Note the extra checks to prevent overflow and underflow.
   candidate_pn = (expected_pn & ~pn_mask) | truncated_pn // ⑤
   if candidate_pn <= expected_pn - pn_hwin and // ⓺
      candidate_pn < (1 << 62) - pn_win: // ⑦
      return candidate_pn + pn_win // ⑧
   if candidate_pn > expected_pn + pn_hwin and // ⑨
      candidate_pn >= pn_win: // ⑩
      return candidate_pn - pn_win // ⑪
   return candidate_pn // ⑫

まず、次に受信するexpected_pnを計算します（①）。これは現在受信している最大のパケット番号+1 とします。

pn_winを計算します（②）。

pn_hwinを計算します（③）。

pn_maskを計算します(④)。

candidate_pnを計算します（⑤）。まず(expected_pn & ~pn_mask) を計算します。ここでは、次に来るパケット番号からパケット番号長のビットをクリアします。次に、(expected_pn & ~pn_mask) | truncated_pn で、マスクした部分の下位ビットに受信したエンコード済みのパケット番号をセットします。

⓺～⑪は考えてみましたが、どういう意図の処理なのかあまりよくわかりませんでした。疑似コードのコメントを読んだ感じだと範囲外になったときの調整のようです。

最後に、計算したcandidate_pn を返します（⑫）。

具体例

処理を行ったパケット番号を 2821665002 (0b1010'1000'0010'1111'0011'0000'1110'1011)とします。受信したパケット番号は39730 (0b1001'1011'0011'0010)とします。

expected_pn は 2821665003になります。

39730は0b1001'1011'0011'0010 なのでpn_nbitsは16ビットです。

pn_winは、0b1'0000'0000'0000'0000、pn_hwinは、0b1000'0000'0000'0000、pn_maskは、0b1111'1111'1111'1111 となります。

candidate_pnは以下のように計算できます。

(expected_pn & ~pn_mask) | truncated_pn 
= (0b1010'1000'0010'1111'0011'0000'1110'1011 & 0b1111'1111'1111'1111'0000'0000'0000'0000) | 0b1001'1011'0011'0010
= 0b1010'1000'0010'1111'0000'0000'0000'0000 | 0b1001'1011'0011'0010
= 0b1010'1000'0010'1111'1001'1011'0011'0010
= 2821692210

なぜ気が付かなかったのか

Initialパケット、Handshakeパケットのやり取りのみだと、パケット番号は小さい値しか使わないので、エンコード・デコードをしてもしなくてもおそらく値が変わりません。

接続確立後にechoを送り続けていました。そうすると、あるタイミングで応答が返ってこなくなりました。そこで、色々試行錯誤したりRFCを読み返したりしている中で、エンコーディング・デコーディングの必要性に気が付きました。

接続後もしばらくパケットを送り続けるケースを確認しておけばもっと早く気が付けたと思います。