要約

  • RFC 1977では、圧縮結果が大きくなると元のPPP形式を送信したが、その試行で生じた辞書更新は残り、受信側も同じパケットを仮想的に圧縮して状態を合わせた。
  • ネイティブ形式にはLZWのCLEARコードを載せられないため、両端は同一の入力、コード幅、比率カウンターから同じ時点で適応的に辞書を消去する必要があった。
  • 16ビット系列番号は後続の圧縮パケットを復号する前に欠落や順序違反を示せる。Reset-Request/Reset-Ackは古い履歴を捨てて再出発する手段であり、過去の完全性や真正性を証明しない。

送られなかった圧縮結果

送信側は、パケットを見ただけでは圧縮が有利か判断できない。まずBSD Compressを実行し、得られた長さを元のデータグラムと比べる。大幅に膨張するなら、RFC 1977は元のPPPカプセル化で送ることを求めた。増加が3オクテット未満でも、リンクのMTUを越えない例外を除けばネイティブ形式が推奨された。

これは上位層に小さなMTUを強いるのを避ける選択だった。圧縮不能なデータに余分なラッパーを付ければ、元は収まるデータグラムがリンク上限を越えかねない。

しかし、捨てられたのは符号化された出力だけである。試行中にLZWは入力を読み、既存の句を照合し、新しい辞書項目を割り当て、コード幅や比率のカウンターを進めている。それまで巻き戻せば、次に送る圧縮パケットは受信側が知らない辞書を参照する。

そこで受信側は、対象範囲のPPPプロトコル番号を持つネイティブパケットを受け取ると、圧縮すれば膨張したものとみなす。付録のpf_bsd_incompは、出力を作らずに圧縮を模擬し、系列、入力長、仮想出力長、辞書項目を送信側と同じように更新する。

ワイヤ上で圧縮されていないことと、圧縮状態に参加していないことは同義ではなかった。

ファイルの終端を失ったLZW

Unixのcompressでは、ファイルの終わりが辞書の終わりでもあった。PPPへの適用では、履歴がデータグラムをまたいで続く。辞書は一台の作業メモではなく、別々に動く二つの実装が同じ入力順から再現する共有状態になった。

CCPの設定は出発点だけを揃える。オプション種別21がBSD Compressを示し、Versionは二進数001、Dictは最大コード幅9〜16ビットを示す。12ビットが一般的な選択として挙げられた一方、付録のコードは9〜15ビットに限られる。後者は例示実装の制限であり、仕様の交渉範囲ではない。

受信側に余分なメモリがあっても、独自に大きな辞書を使うことはできない。辞書が満杯になる時点、コード幅が増える境目、比率低下を判定する時点がずれるからだ。

元パケットのProtocolフィールドにも共通規則があった。値が0x100未満なら、PPPのProtocol-Field-Compressionが交渉済みかどうかにかかわらず、内側の入力では1オクテットにする。二つの端点が同じデータグラムから異なるバイト列を作らないための規則である。

PPPがNetwork-Layer Protocol段階に入り、CCPがOpenedになるまでは圧縮パケットを交換できない。設定へのACKは共通パラメーターの承認を示すが、カーネルと制御プロセス、あるいは異なる実装が以後の状態遷移を同じ順序で実行したことまでは示さない。

CLEARを送れない瞬間

古典的なBSD LZWでは予約値256がCLEARであり、符号列の末尾から辞書消去を通知できた。ところがPPPネイティブパケットにはLZWの符号列がない。圧縮しにくいデータが満杯の辞書をさらに悪化させても、そのパケット上に明示的なCLEARを置く場所はない。

RFC 1977は通知の代わりに計算の一致を使った。付録の実装は辞書が満杯になった後、入力10,000バイトごとに圧縮比を調べる。新しい比率が以前より悪いか、一対一を下回れば、pf_bsd_clearがコード幅を9ビットに戻し、最終項目と比率カウンターを初期化する。

送信側は試行圧縮からこの判断に到達し、受信側はネイティブパケットの模擬圧縮から同じ判断に到達する。対象パケット、入力バイト、仮想出力長、項目割り当てが一致して初めて、見えない消去の時点も一致する。

追加ヘッダーを避けてMTUを守る代わりに、アルゴリズムの細部が相互運用条件になった。しかも消去直後は辞書が乏しいため、最初の数パケットは圧縮効果が出ずネイティブで送られやすい。見た目だけでは、圧縮開始前の通常パケットと、新しい辞書を育てているパケットを区別できない。

系列番号が見えるのは後から

実際のBSD圧縮パケットには16ビット系列番号があり、上位オクテットから送られる。辞書消去後にゼロから始まり、ネイティブ送信を含む対象パケットごとに増え、65535の次でゼロへ戻る。受信側は復号前に値を検査すべきだとされた。

ただしネイティブパケット自身にはこのヘッダーがない。途中で一つ失われれば、送信側だけが辞書とカウンターを進め、受信側は欠落を直ちに観測できない。次の圧縮パケットが届いた時、その番号と受信側の期待値が合わず、初めて不連続が表面化する。

系列番号は誤った辞書で復号を続けるのを止める。どのパケットが失われたか、欠落か順序逆転か、失われた内容が何かは教えない。相手の認証にもならない。RFC 1977は破損フレームについてHDLC FCSと通常の廃棄処理に依存し、Security Considerationsでは安全性を論じていない。巡回カウンターもリンク検査値も、暗号学的な完全性証明ではない。

リセットは過去を直さない

予想外の系列を初めて見た受信側はCCP Reset-Requestを送り、Reset-Ackまで圧縮パケットを捨てる。送信側は以前のACKが届いたか分からないため、要求を受けるたび辞書を消去し、系列をゼロにして応答する。受信側も一致するACKごとに消去する。

RFCはこれを、一つの「ファイル」を放棄して別のファイルを始めることにたとえた。失われた辞書を修復するのではなく、二者が確認できる新しい起点を作る。Configure-RequestでCCPを再交渉する方法もあるが、より高価である。

混雑時には、エラーからACK到着まで複数の圧縮パケットが届き、すべて廃棄されうる。要求は少なくとも一つ到達するまで繰り返す必要がある一方、RTTより短い間隔は不要な辞書消去を増やす。文書の1秒は例にすぎない。

制御とデータを別の実行系が扱う実装では、さらに順序が問題になる。送信側の消去は圧縮再開を告げるConfigure-AckまたはReset-Ackと同期し、受信側の消去は次のパケット処理より先でなければならない。正しい制御メッセージが記録されても、内部の実行順を自動的には証明しない。

文書が定めるもの、運用が示すもの

RFC 1977は、対象入力、Version 1、コード幅上限、比率判定、系列演算、再始動という小さな共通規則を定めた。IANAにもCCPオプション21、圧縮データグラム用0x00FDと0x00FBが記録されている。

Lu Hengが述べるrunning-codeの観点から見れば、これはローカルに検証できる共通文法である。しかし個々のリンクで同じ履歴が作られたことは、全対象パケットの順序、ネイティブ入力、コード幅、比率、消去時点の記録で別に示さなければならない。

本稿はRFC 1962のCCP全史、RFC 1963のシリアルフレーム形式、RFC 1990のマルチリンク再順序化を扱わない。現在の普及率や製品性能も推定しない。歴史上の境界は一つで十分である。RFC 1977で「非圧縮」はワイヤ形式を表したが、辞書の停止を意味しなかった。

出典