12th - OF に longest match がない話

つい最近、知人が（あまり OpenFlow に詳しくない人から）従来的 IP ルーティングを実現したかったのか、Longest Match が無いんですけど、と言われたそうだ。
ルータがパケットをフォワーディングするとき、ルーティングテーブルにはそのパケットがマッチするルールが複数あるかもしれない。ルータはこのとき、マッチしたルールのうちネットマスク長のより長いものを採用する。 一般にこの振る舞いを longest match と呼ぶ。
そう、OpenFlow には longest match がない。だから普通のルータを OpenFlow で実現するのはちょっと面倒だ。
すぐ思いつく実現方法は、マッチフィールドにはワイルドカードがビット単位で指定でき、またフローエントリにはプライオリティが設定できる事を利用するもの。 つまりワイルドカードの長さを短くしながら徐々にプライオリティを低くしたフローエントリの列を用意する。
ぱっと検索するとACM SIGCOMM 2013 - HotSDN'13 Workshop にそれっぽい記述のあるポスターが引っ掛かった。
"These are sorted in order of prefix to implement longest prefix matching; longer prefixes adopt a higher priority in the rule table than shorter prefixes."
この人達は QuagFlow などを手がけていたようで、まあ続いていると言うことか。
さて本題はここからで、しかし longest match はもともと L3 switch ASIC には組み込まれている機能だったりしないか？と思ってしまう。（本当のところを知らないのですが、あるだろうなあ、と）
で、OpenFlow の従来的スイッチング ASIC への実装というのは、割と L2/L3 に対するマッチについては（貴重な）TCAM を使わずスイッチが元々持っている L2, L3 テーブルとその処理機構の上に行われていたりする。 だからうまくスイッチ側の OpenFlow ドライバを実装すると（あるいは普通に実装すると必然的にそうなるかもしれない）、上に書いたようなワイルドカードを使用した longest match を実現するためのフローエントリの列は、内部的にはまさにスイッチングチップが本来持つ longest match 機構を利用するように変換される。
これはちょっと面白い感じで、コントローラとスイッチはルーティングを実現しようとしているが、そのための「言語」としての OpenFlow プロトコルにはその「言葉」がないので、直接的に言うことができない状況だ。
（代替手段として明示的にプライオリティをつけて指令することになる。）
なんか両端のコントローラとスイッチが、途中の OpenFlow にバレないように隠語を使って話してるようでちょっと面白い。（これが言いたかっただけなのに長くなって申し訳ない。）

References