デモ一覧へ戻る
Toeplitz スライディングウィンドウ
NIC がパケットをどの受信キューに入れるかを決めるハッシュ。テーブル参照も乗算もなく、シフトと XOR だけ。
デモは直接操作できます。1 ステップずつ進める、戻す、連続再生するほか、入力も変更できます。矢印キーで 1 ビットずつ移動し、スペースキーで再生／一時停止します。
このデモで見えるもの
メインの図は 320 ビットのキーのテープで、その上を 32 ビットのウィンドウが入力ビットごとに 1 つずつスライドします。いちばん説明しにくい点がひと目で分かります。Toeplitz 行列の i 行目は、キーを i ビット目から 32 ビット切り出したものにすぎません。行列全体が 1 本のレジスタに収まる理由はここにあります。
入力バイトはビット単位で並べられます。現在のビットが 1 なら result ^= window が実行されて赤く示され、0 ならスライドするだけです。window と result は同じ 32 列のグリッドで揃えてあるので XOR を縦に読め、反転したビットは赤枠で示されます。
最後のパネルは双方向の比較です。既定の 5 タプルに標準キーを使うと、順方向と逆方向が別のキューに入り、一つの TCP 接続が 2 つのコアに分かれてしまいます。対称キーに切り替えると両方向のハッシュが一致し、フロー全体が同じキューに戻ります。NAT、ステートフルファイアウォール、トラフィック解析では避けて通れない問題です。
ページ上の途中の状態はすべてその場で計算したもので、録画したアニメーションではありません。実装は Microsoft RSS 仕様の標準テストベクトルと照合済みです。