inet-henge 利用例: Batfish ネットワークトポロジーの可視化

inet-henge を使うと、ネットワーク図を簡単に描画できます。

github.com

必要なのは「このデバイスは、あのデバイスとつながっている」という構成情報のみ。

{
  "nodes": [
    { "name": "A" },
    { "name": "B" }
  ],

  "links": [
    { "source": "A", "target": "B" }
  ]
}

このエントリーでは、Batfish が持っているネットワークトポロジーをinet-henge をつかって可視化してみます。 たとえば、👇のようなネットワーク図が描けます。

Batfish とは

Batfish はネットワークコンフィグ分析ツールで、実機に投入せずとも confiuration validation / 各種プロトコルの状態確認 / ルーティングテーブルやACL分析が可能です。

その一環として、IPアドレスを元に layer-3 interface adjacencies を判定しネットワーク構成をデータ化する、ということもやっています。

詳細は こちら をご覧ください。

API で、Batfish ネットワークトポロジーを取得する

Batfish が持っているネットワークトポロジーは、👇のようなURLからAPIで取得できます。

http://<batfish_server>:9996/v2/networks/<network>/snapshots/<snapshot>/topology

チュートリアルの Getting Started with Batfish を試す場合でいえば、Batfish サーバーである 9996/tcp を公開しておけばOKです。

$ docker run --rm -p 8888:8888 -p9996:9996 batfish/allinone
[I 17:02:05.649 NotebookApp] Writing notebook server cookie secret to /data/.local/share/jupyter/runtime/notebook_cookie_secret
[I 17:02:05.892 NotebookApp] Serving notebooks from local directory: /notebooks
[I 17:02:05.892 NotebookApp] The Jupyter Notebook is running at:
[I 17:02:05.892 NotebookApp] http://(5df00b13e028 or 127.0.0.1):8888/?token=2a0b09ed8f6a1aea73fc1f4e9360696224ec1d4bcbe646b5
[I 17:02:05.892 NotebookApp] Use Control-C to stop this server and shut down all kernels (twice to skip confirmation).
[W 17:02:05.895 NotebookApp] No web browser found: could not locate runnable browser.
[C 17:02:05.895 NotebookApp]

    To access the notebook, open this file in a browser:
        file:///data/.local/share/jupyter/runtime/nbserver-9-open.html
    Or copy and paste one of these URLs:
        http://(5df00b13e028 or 127.0.0.1):8888/?token=2a0b09ed8f6a1aea73fc1f4e9360696224ec1d4bcbe646b5

APIリクエストにX-Batfish-Version: 0.36.0 のようなHTTPヘッダーが必要な点にもご注意ください。

レスポンス例

$ curl -H "X-Batfish-Version: 0.36.0" http://localhost:9996/v2/networks/example_network/snapshots/example_snapshot/topology
[ {
  "node1" : "as1border1",
  "node1interface" : "GigabitEthernet0/0",
  "node2" : "as1core1",
  "node2interface" : "GigabitEthernet1/0"
}, {

...

inet-henge による可視化

Batfish が吐くデータ構造を、inet-henge が期待する形に変換します。

サンプルをこちらに掲載しますが、さほど複雑ではありません。 https://gist.github.com/codeout/07f3f711a7f0b5adec7fc8065b0f3958

コマンド等による前処理が面倒なため、ブラウザからBatfish APIを呼んでいます。

inet-henge によるネットワーク図

拡大するとインターフェイス名が現れます。

チュートリアル中にあるネットワーク図

(https://github.com/batfish/pybatfish/blob/master/jupyter_notebooks/Getting%20started%20with%20Batfish.ipynb)

まとめ

inet-henge によるネットワーク図は オートレイアウトのため、ひょっとすると好みの出力を得られないかもしれません。しかしながら「見てわかる」程度のネットワーク図を描くことが可能です。

HTMLをひとつ置いておくだけで、前処理なしでBatfish のネットワーク図が見れるというのは便利ですね！

設定ファイルエディターをつくる方へ

JANOG43 でライトニングトークしてきました

speakerdeck.com]

• NETCONF向けのコマンド(xml) とCLI向けのコマンド(text) が似ているため、XMLスキーマから抽象構文木が作れる
• 抽象構文木からエディターを作れる
• ためしにJunos向けの実装をしてみたが、他ベンダー向けもできるはず

簡単にいうと このような内容の発表をしてきました。

時間の関係で話せなかったことなどを、こちらにまとめておきます。

頂いた質問に答えます

いくつか質問を頂きました。ありがとうございます！

Q: オフラインでも使えますか？

A: 使えます。

任意のCLI階層におりたとき、次に続くかもしれないキーワードのリストをXMLスキーマを参照して取得すると…

発表ではこのような説明をしましたが、実際にはXMLスキーマを扱いやすい形 *1 に変換し、vscode拡張の中に同梱しています。ネットワーク機器との通信は不要で、オフラインでもOKです。

Q: XSDとYANG、どちらを使いました？

A: XSDを使いました。

詳しくは後述しますが、結果的にJunosではXSDを使ったものの、他でやるならまずYANGを試してみると思います。

設定ファイルエディターをつくる方へ

さて 本題ですが、あまりに誰得すぎて発表前に消したスライドがあります。実際にエディターを書く人向け。

せっかくなので、このスライドについて 補足します。

XSDとYANG、どちらを取るか

とりあえずはYANGがオススメです。

• 標準化されたフォーマットだから
  • 抽象構文木を作成するにあたり、単一手法で複数プラットフォーム対応できる可能性がある
• パーサー実装があるから
• サイズが小さいから
  • たとえばJUNOS 17.4 の場合、XSD 102MB に対して YANG は18MB しかありません。だいぶ楽

しかしながらJunosの場合、XSDのほうが便利そうだった

一番のポイントは、大量のメタデータが使えることでした。下は一例ですが、エディター実装時にはとても役立つ情報です。

                <xsd:annotation>
                  <xsd:documentation>Policy Name</xsd:documentation>
                  <xsd:appinfo>
                    <flag>mustquote</flag>
                    <flag>identifier</flag>
                    <flag>nokeyword</flag>
                    <flag>current-product-support</flag>
                    <regex-match deprecate="deprecate">^.{1,64}$</regex-match>
                    <regex-match-error deprecate="deprecate">Must be string of 64 characters or less</regex-match-error>
                    <match>
                      <pattern>^.{1,64}$</pattern>
                      <message>Must be string of 64 characters or less</message>
                    </match>
                      <identifier/>
                  </xsd:appinfo>
                </xsd:annotation>

• それが識別子であるか、クォートが必要かどうか、など
• バリデーション失敗時のメッセージ

    <xsd:annotation>
      <xsd:documentation>Source address filters</xsd:documentation>
      <xsd:appinfo>
        <flag>oneliner</flag>
        <flag>homogeneous</flag>
        <flag>autosort</flag>

• CLI で、一行表現可能かどうか
  • これがないと正しくCLIコマンドをパースできません

                    <xsd:annotation>
                      <xsd:documentation>List of captive portal content delivery rules</xsd:documentation>
                      <xsd:appinfo>
                        <flag>current-product-support</flag>
                        <products>
                          <product>mx960</product>
                          <product>mx480</product>
                          <product>mx240</product>
                          <product>mx80</product>
                          <product>mx80-48t</product>
                          <product>mx5-t</product>
                          <product>mx10-t</product>
                          <product>mx40-t</product>
                          <product>mx80-t</product>
                          <product>mx80-p</product>
                          <product>mx2020</product>
                          <product>mx2010</product>
                          <product>ex9204</product>
                          <product>ex9208</product>
                          <product>ex9214</product>
                          <product>mx104</product>
                          <product>vmx</product>
                          <product>vrr</product>
                          <product>mx2008</product>
                          <product>mxtsr80</product>
                          <product>mx10001</product>
                          <product>mx10002</product>
                          <product>ex9251</product>
                        </products>
                    </xsd:appinfo>
                  </xsd:annotation>

• サポートするプラットフォーム一覧

一方、IOS-XR はYANGがよさそう

• メタ情報が少ない
• ファイル構造がほとんどYANGと同じ

このような理由で、もしIOS-XRでやるなら YANGを試すと思います。

NETCONFコマンドとCLIコマンドに差分がある場合の対応

Junosの場合 感覚的には「95% くらい同じ」と言えますが、やはり若干の差があります。

代表的なものは隠しコマンドの扱いです。XSD や YANG に隠しコマンドは記述されていません。

抽象構文木(AST) 生成元であるXSD / YANG は、ベンダーの都合で更新されます。それに引きずられることなく文法修正するために、一旦オレオレ記法で中間ファイルを作っておき、そこにパッチしていくと便利です。

XSDの場合には、大幅にサイズ削減できるという効果も狙っています。エディターに同梱するのは最終形態なので結果同じにはなりますが、開発中に何度もXSD本体をパースする必要はありません。

ライセンス

今回発表したやり方でいくと XSD / YANG をエディター処理系のデータ構造に変換し、エディターに同梱し、二次利用することになります。

問題ないことが多いとは思いますが、これがベンダーのライセンスに抵触するかどうかについて 確認しておくと安心です。

*1:JavaScriptで、巨大なObject

libwireshark のdissector を借りて、バイト列をパケットとしてデコードする

Wireshark という強力なプロトコルアナライザーがあります。多くのプロトコルをサポートし、「どんなパケットが流れているか分からないが、プロトコルスタックの深いところまで解析したい」場合には 非常に頼りになります。

この記事では、いくつかのプログラミング言語上のバイト列を libwireshark を使ってパケット解析してみます。

直面している問題

ネットワーク運用のために、sflow をきちんと解析したいと思っています。netflow では、ネットワークの制約により 欲しい統計が取れないことがあるためです。

• トラフィック制御のために、Q-in-Q、IPIP、GRE などのトンネルプロトコルの出番が増えた
• バックボーンを流れるときには、さらにMPLS ラベルやSegment Routing Header がつく

このようにプロトコルスタックが深い場合、高価なASICであったとしても ネットワークデバイスでデコードする前提のnetflow には限界があります。それより、単純に「先頭のNバイトをまるっとコピーしてexport し、コレクター側でなんとかする」というsflow アプローチのほうが、目的に合うこともあるでしょう。N は100~200B 程度なので、そこそこ上位レイヤーまで解析可能です。

sflow をきちんと解析したい別な理由として、マーチャントシリコンを搭載したスイッチ製品が普及し 単純にsflow を扱うケースが増えた、というのもあります。

具体的な問題の例

👇のデータを見てください。fluent-plugin-sflow を使って収集しているレコードのひとつです。

{
  "datagram_source_ip": "192.168.0.2",
  "datagram_size": 220,
  "unix_seconds_utc": 1537117560,
  "datagram_version": 5,
  "agent_sub_id": 0,
  "agent": "169.254.0.2",
  "packet_sequence_no": 766,
  "sys_up_time": 4513318,
  "samples_in_packet": 1,
  "sample_type_tag": "0:1",
  "sample_type": "flow_sample",
  "sample_sequence_no": 1227,
  "source_id": "0:512",
  "mean_skip_count": 1,
  "sample_pool": 1228,
  "drop_events": 0,
  "input_port": 512,
  "output_port": 0,
  "flow_block_tag": "0:1001",
  "header_protocol": 1,
  "sampled_packet_size": 106,
  "stripped_bytes": 4,
  "header_len": 102,
  "header_bytes": "02-05-86-71-74-03-02-05-86-71-64-03-88-47-00-01-01-40-45-00-00-54-4A-95-00-00-40-01-AE-C0-C0-A8-00-02-C0-A8-00-01-08-00-B3-1D-40-0E-00-4D-5B-1D-85-C7-00-08-38-97-08-09-0A-0B-0C-0D-0E-0F-10-11-12-13-14-15-16-17-18-19-1A-1B-1C-1D-1E-1F-20-21-22-23-24-25-26-27-28-29-2A-2B-2C-2D-2E-2F-30-31-32-33-34-35-36-37",
  "dst_mac": "020586717403",
  "src_mac": "020586716403",
  "in_vlan": 0,
  "in_priority": 0,
  "out_vlan": 0,
  "out_priority": 0
}

Ethernet であることはわかりますが、それより上のレイヤーはデコードできていません。これでは何のことかぜんぜんわからない。

Wireshark 👇で見るとわかるように、実際はMPLS ラベルがついたICMP パケットです。

fluent-plugin-sflow は、sflow を策定しているInMon 公式のsFlow Tools を内包し、なるべく普及している方法でデコードを試みていますが、そのプログラムがMPLS に対応していません。

現実問題として あらゆるプロトコルスタックに対応するのは無理なのですが、Wireshark を使えばかなりイイ線いけそうではあります。

やってみる

現在のところ、残念ながらlibwireshark に「バイト列を受け取ってデコード結果を返す」というAPI がありません。Wireshark ファミリーのプログラム向けに、libpcap を用いて

• ファイル
• ネットワークインターフェイス
• パイプ

からバイト列を読むAPI があるだけです。

とはいうものの、libpcap の部分をすっ飛ばして「外から受け取ったバイト列をもつフレームをでっち上げる」ことは難しくなさそうです。

void rawshark_process_packet(uint8_t *data, int len, FILE *file) {
    guint32 cum_bytes = 0;
    gint64 data_offset = 0;
    frame_data fdata;
    epan_dissect_t *edt;

    // パケット解析器を初期化する
    cfile.epan = epan_new();
    cfile.epan->get_frame_ts = raw_get_frame_ts;
    cfile.epan->get_interface_name = NULL;
    cfile.epan->get_interface_description = NULL;

    edt = epan_dissect_new(cfile.epan, TRUE, TRUE);

    // NIC やpcap ファイルからフレームを読み出す代わり、
    // 外から受け取ったバイト列を持つフレームをでっち上げる
    struct wtap_pkthdr *whdr = g_malloc(sizeof(struct wtap_pkthdr));

    whdr->rec_type = REC_TYPE_PACKET;
    whdr->pkt_encap = wtap_pcap_encap_to_wtap_encap(1); /* ETHERNET */
    whdr->caplen = len;
    whdr->len = whdr->caplen;
    whdr->opt_comment = NULL;

    cfile.count++;

    frame_data_init(&fdata, cfile.count, whdr, data_offset, cum_bytes);
    frame_data_set_before_dissect(&fdata, &cfile.elapsed_time, &ref, prev_dis);

    if (ref == &fdata) {
        ref_frame = fdata;
        ref = &ref_frame;
    }

    // 解析する
    epan_dissect_run(edt, cfile.cd_t, whdr, frame_tvbuff_new(&fdata, data), &fdata, &cfile.cinfo);

    // フレームと解析器を解放し、結果を JSON で返す
    frame_data_destroy(&fdata);
    g_free(whdr);

    frame_data_set_after_dissect(&fdata, &cum_bytes);
    prev_dis_frame = fdata;
    prev_dis = &prev_dis_frame;

    prev_cap_frame = fdata;
    prev_cap = &prev_cap_frame;

    write_json_proto_tree(NULL, print_dissections_expanded,
                          TRUE, NULL, PF_NONE,
                          edt, file);

    epan_dissect_free(edt);
    edt = NULL;

    epan_free(cfile.epan);
}

これを native extension 化すれば、たとえばfluentd 向けに「Ruby の世界のバイト列を C の世界にもっていってlibwireshark で解析し、Ruby の世界に戻す」ことが可能です。

Ruby + libwireshark

Ruby と C の橋渡し部分。

VALUE rb_rawshark_process_packet(VALUE self, VALUE data) {
    uint8_t *raw = (uint8_t *) StringValuePtr(data);
    int rawlen = (int) RSTRING_LEN(data);
    VALUE json;

    char *buf = NULL;
    size_t buflen = 0;
    FILE *out = open_memstream(&buf, &buflen);

    rawshark_process_packet(raw, rawlen, out);
    fclose(out);

    if (buflen > 4) {
        // NOTE: Truncate leading "  ,\n"
        json = rb_str_new2(buf + 4 * sizeof(char));
    }

    free(buf);
    return json;
}

完全なサンプルは 👇にあります。

github.com

Ruby での利用例。

require 'wireshark'

Wireshark.load

raw = File.read(File.expand_path('../raw_frame', __FILE__))
puts Wireshark.dissect(raw)

Wireshark.unload

Python + libwireshark

C の (uint8_t *) に持って来られればもとの言語はなんでもよく、たとえば Python であればCython をつかって

def dissect(data):
    cdef char *buf = NULL;
    cdef size_t buflen = 0;
    cdef FILE *out = open_memstream(&buf, &buflen)

    rawshark_process_packet(data, len(data), out)
    fclose(out)

    if buflen > 4:
        json = buf[4:buflen]

    free(buf)
    return json.decode()

のようにできます。

こちらも完全なサンプルは 👇。

github.com

Python での利用例

import os
import wireshark

base_dir = os.path.dirname(os.path.abspath(__file__))

with open(os.path.join(base_dir, 'raw_frame'), 'rb') as raw:
    wireshark.load()
    print(wireshark.dissect(raw.read()))
    wireshark.unload()

デコード結果

長くなるので掲載しませんが、なんとWireshark で見る相当のデータがJSON で手に入ります 🎉🎉🎉

もし興味があれば👇のgist をご覧ください。Ethernet Frame の奥のMPLS ラベルの奥のIP パケットの奥のICMP ヘッダが取れています。

Decoded sFlow data with libwireshark · GitHub

最後に、注意点をいくつか

libwireshark は遅い

libwireshark は非常に多くのプロトコルをサポートします。subdissector によって可能な限り再帰的に、上位レイヤーに向かってプロトコル解析するという動作のため、パフォーマンスは望めません。

( 図: 先のMPLS ラベルつきICMP パケットの解析パフォーマンス )

ruby version:      2.5.1
python version:    3.6.5
compiler:          GCC 7.3.0
platform:          Linux-4.15.0-34-generic-x86_64-with-Ubuntu-18.04-bionic
cpu model:         Intel(R) Core(TM) i7-4980HQ CPU @ 2.80GHz  # 2793.532 MHz

gprof 結果。libwireshark に実装されている、フレーム初期化部分が重そうなことがわかります。

  %   cumulative   self              self     total
 time   seconds   seconds    calls  Ts/call  Ts/call  name
  0.00      0.00     0.00    10000     0.00     0.00  frame_tvbuff_new
  0.00      0.00     0.00    10000     0.00     0.00  rawshark_process_packet
  0.00      0.00     0.00        1     0.00     0.00  cap_file_init
  0.00      0.00     0.00        1     0.00     0.00  rawshark_clean
  0.00      0.00     0.00        1     0.00     0.00  rawshark_init

もし「プロトコルスタックが固定で、高速にデコードしたい」「固定ではないが、最大でも3レイヤーデコードすればOK」のような場合は適さないかもしれません。

( libwireshark でも「3レイヤーまで」などの指定は可能かもしれませんが、未調査です )

libwireshark のライセンス

Wireshark は、GPL v2 です。これを動的リンクするプログラムもGPL v2 にする必要があります。

まとめ

Ruby や Python 向けに (もちろんその2つに限らずですが)、libwireshark をリンクした native extension を作っておくと便利です。

プログラムから高速に経路ルックアップするアプローチ

やりたいこと

開発中のプログラム内で、高速に経路ルックアップしたい場合があります。

私の場合、いま直面しているのは「netflow なり sflow なりを収集するとき、collector 側で経路ルックアップして Origin AS を解決したい」です。

デフォルトルートや MPLS を利用しているなど、そもそも exporter (ルーター / スイッチ) が必要な経路情報を持っていない場合があるためです。

TL; DR

• ホスト内に gobgpd が動いているという前提で gRPC する、簡易実装でベンチマークした
• ruby クライアントでも、 6k ルックアップ/s くらいはいけそう
  • たとえば go にしても劇的に速くはならない
• 速いとは言えないが、間に合うケースもある気がする
  • gobgpd に gRPC する簡易実装で、これ以上はつらそう

2018-06-08 追記

• API についてアドバイスいただいて再計測すると、36k ルックアップ/s だった

アプローチ

考えられるアプローチは大きく2つ。

1. collector プロセスがフルルートを持つ
2. collector プロセスが、bgpd の経路をAPI でルックアップする

それぞれ pros/cons を考えてみます。

• ネットワーク遅延の観点から、フルルートは collector ホスト内に持っておきたい
• フルルートの注入は BGP が楽

というのは共通です。

1. collector プロセスがフルルートを持つ

collector プロセスが外部のルーター(図中の右ルーター)と BGP セッションを張り、自分自身でフルルートの RIB を持つアプローチです。

この場合、問題になりそうなのは collector プロセスのスケールアウトでしょう。collector は fluentd + fluent-plugin-netflow (or fluent-plugin-sflow) あるいは goflow + flow-pipeline を想定しますが、1 ホスト上に複数プロセス待ち受けたいです。

複数 collector プロセスが 各々 TCP ポートを分けつつ同じ外部ルーターとピアできるかというと、疑問があります。 *1 一回ソフトウェアルーターで経路受信するなど 工夫が必要でしょう。

別の問題として、RIB の実装があります。Patricia Trie が一般的ですが、これを自前でやる必要があります。

実装は複雑そうですが collector としては良いパフォーマンスが期待できます。

2. collector プロセスが、API 経由で経路ルックアップする

collector プロセスが、ホスト内で動作する bgpd の API を利用して経路ルックアップするアプローチです。

この場合、問題になりそうなのは bgpd の経路ルックアップパフォーマンスです。フルルートの注入に 10~20秒かかりそうなのはどちらのアプローチでも同じですが、bgpd の経路探索スピードは簡単にボトルネックになりえます。

一方で collector プロセスの実装はかなりシンプルになります。

まずトライするべきはこちらでしょうか。すごく高速に動く気はしませんが、十分なスピードで動いてくれる可能性はあります。

API で経路ルックアップできる bgpd (たとえば gobgpd)

まず思いつくのがgobgpd です。

今回は gobgpd に注目して、経路ルックアップのパフォーマンスを調査しますが… 「これもいけるらしいですよ」という実装がありましたら ぜひ教えてください！

ruby + gRPC で gobgpd 経路ルックアップ

collector として たとえば fluentd を利用する場合、ruby で gRPC することになります。

• MacBook Pro (Mid 2015) / Intel(R) Core(TM) i7-4980HQ CPU @ 2.80GHz
• ruby 2.5.1p57 (2018-03-29 revision 63029) [x86_64-darwin16]
• grpc (1.12.0 universal-darwin)
• go1.10.2 darwin/amd64
• gobgpd v1.32

の環境で

$ gobgpd &
$ gobgp global as 65000 router-id 10.0.0.1 listen-port 10179
$ wget http://archive.routeviews.org/route-views.wide/bgpdata/2018.06/RIBS/rib.20180604.0000.bz2
$ bunzip2 rib.20180604.0000.bz2
$ gobgp mrt inject global rib.20180604.0000

して

Table ipv4-unicast
Destination: 704550, Path: 1394586

をロードし、以下の ruby クライアントから接続します。

$ gem install grpc-tools grpc
$ GOBGP_API=$GOPATH/src/github.com/osrg/gobgp/api
$ protoc -I $GOBGP_API --ruby_out=. --grpc_out=. --plugin=protoc-gen-grpc=`which grpc_tools_ruby_protoc_plugin` $GOBGP_API/gobgp.proto
$ bgpdump -M rib.20180604.0000 | grep 202.249.2.86 | awk -F \| 'NR%1000==0 { print $6 }' > routes
$ ruby -I. bench.rb

# bench.rb

require 'benchmark'
require 'ipaddr'
require 'gobgp_pb'
require 'gobgp_services_pb'


def request(prefix)
  Gobgpapi::GetRibRequest.new(
      table: Gobgpapi::Table::new(
          family: Gobgpapi::Family::IPv4,
          destinations: [
              Gobgpapi::Destination.new(prefix: prefix)
          ]
      )
  )
end

stub = Gobgpapi::GobgpApi::Stub.new('localhost:50051', :this_channel_is_insecure)
stub.get_rib(request('1.1.1.1'))  # The first call is super slow

puts File.read('routes').split.map {|prefix|
  prefix = IPAddr.new(prefix).succ.to_s

  Benchmark.realtime {
    10.times do
      stub.get_rib(request(prefix))
    end
  } / 10
}.join(', ')

何をしているかというと、

1. 1000 経路にひとつの割合で prefix をピックアップ
2. prefix の先頭のアドレスについて、10回ルックアップ
3. 平均の応答時間を出力

です。

横軸に prefix を並べていますが 値に意味はありません。「prefix が違っても応答時間はほぼ一定」という点がポイントです。gobgpd の RIB は単純な Hash であり、理屈は通っています。

さて、ここで気になるのは「longest match による経路ルックアップを、Hash でどのように実現しているか」ですね。たとえば 1.1.1.1 をルックアップした場合に 1.1.1.0/24 を返してほしい。

gobgpd (v1.32) では、若干力技の実装になっています。IPv4 であれば /32、/31、... のように prefix length を縮めながらマッチするまで探索します。RIB に存在する prefix そのものを探索した場合(赤) とRIB に存在しない longer prefix を探索した場合(緑) で特徴的な差があるのはこれが原因でしょう。

ここまでで、この環境なら ruby クライアントで 3~4k lookup/s くらいのパフォーマンスが期待できることがわかりました。

go + gRPC でgobgpd 経路ルックアップ

比較のために、go クライアントでも試してみます。goflow を利用する場合はおそらく go になるでしょう。

# bench.go

package main

import (
    "github.com/osrg/gobgp/client"
    "os"
    "bufio"
    "github.com/osrg/gobgp/packet/bgp"
    "github.com/osrg/gobgp/table"
)

func main() {
    client, _ := client.New("localhost:50051")
    fp, _ := os.Open("routes")

    scanner := bufio.NewScanner(fp)
    for scanner.Scan() {
        for i := 0; i < 10; i++ {
            client.GetRIB(bgp.RF_IPv4_UC, []*table.LookupPrefix{
                &table.LookupPrefix{scanner.Text(), table.LOOKUP_EXACT},
            })
        }
    }
}

$ go build bench.go
$ time ./bench
./bench  0.81s user 0.76s system 112% cpu 1.399 total

これは 5k lookup/s くらいに相当しますが 劇的に高速になるわけではなさそうです。原因とししてはgRPC のオーバーヘッド、あるいは gobgpd 自身のパフォーマンスが考えられます。

一般に netflow / sflow には複数のフローエントリーが含まれ、さらに src ip address / dst ip address 双方を検索すると… 10 entries/flow としても flow packet あたり20回のルックアップが必要です。この場合 5k lookup/s = 250 pkt/s 程度であり、不安が残ります。

マルチスレッドで若干改善できるはず

ruby でも go でも遅いのですが、gRPC オーバーヘッドを考えるとマルチスレッド化することで改善が期待できるはずです。

たとえば ruby クライアントのスレッド数を 2 にすると

# bench.rb

require 'benchmark'
require 'ipaddr'
require 'gobgp_pb'
require 'gobgp_services_pb'
require 'thread'


def request(prefix)
  Gobgpapi::GetRibRequest.new(
      table: Gobgpapi::Table::new(
          family: Gobgpapi::Family::IPv4,
          destinations: [
              Gobgpapi::Destination.new(prefix: prefix)
          ]
      )
  )
end

stub = Gobgpapi::GobgpApi::Stub.new('localhost:50051', :this_channel_is_insecure)
stub.get_rib(request('1.1.1.1')) # The first call is super slow

queue = Queue.new
File.read('routes').split.each do |prefix|
  10.times do
    queue << prefix
  end
end

puts Benchmark::CAPTION
puts Benchmark::measure {
  threads = []
  2.times do
    threads << Thread.new {
      while !queue.empty?
        stub.get_rib(request(queue.pop))
      end
    }
  end
  threads.each {|t| t.join}
}

こんな感じなります。

1 スレッド

$ gobgp_performance $ ruby -I . bench.rb
user     system      total        real
0.877157   0.564896   1.442053 (  1.707599)

2 スレッド

$ gobgp_performance $ ruby -I . bench.rb
user     system      total        real
1.139738   0.852233   1.991971 (  1.258576)

若干ですが速くなっていますね。グラフにするとこんな感じ 👇 になります。

さらに ごくわずかですが処理をブロックしているスキマがありそうなので、ruby クライアント側で Origin AS をデコードしてみます。

def origin_as(table)
  path_attrs = table.table.destinations[0].paths.find {|p| p.best}.pattrs.map {|i| i.unpack('C*')}
  as_path = path_attrs.find {|a| a[1] == 2}

  case as_path[0]
  when 64 # 2 byte AS
    (as_path[-2] << 8) + as_path[-1]
  when 80 # 4 byte AS
    (as_path[-4] << 24) + (as_path[-3] << 16) + (as_path[-2] << 8) + as_path[-1]
  end
end

クライアント側でデコードしているのは gRPC を待つ CPU 時間をデコードにあてたいからで、ruby でやっているのは FFI + GC を ruby <-> go 間で面倒みたくないためです。

マルチスレッドにすることで、6k lookup/s くらいはいけそうです 🎉

まとめ

プログラムから経路ルックアップする場合のアプローチはいくつか考えられますが、簡易な実装で gobgpd を題材にベンチマークしてみました。

ruby クライアントであっても 6k lookup/s くらいのパフォーマンスは出そうですが、十分とは言えません。flow collector と一緒に使った場合、ここでつまる可能性があります。 しばらく運用してみて問題があったら RIB を内包するパターンの実装をトライする予定です。

また、実際の fluent plugin コード、flow-pipeline 向け kafka consumer は後日公開できるかもしれません。

2018-06-08 追記

tamihiro さんに「gobgpd の GetRib API、複数 prefix 渡せますよ」とご指摘いただき、再計測しました。

完全に見過ごしていた！

パラメーターが多くて見づらいのですが、1~5 スレッドごとに 8 本のバーチャートを引いてあり、上から順に

gRPC あたりの prefix 数	Origin AS デコード
1	❌
1	⭕️
5	❌
5	⭕️
10	❌
10	⭕️
20	❌
20	⭕️

です。

• worker スレッドを増やしても さほど効果はないのは同じ
• gRPC あたりの prefix 数を増やす = gRPC 数を減らす と劇的にパフォーマンス改善する
  • gobgpd の経路ルックアップというよりは、gRPC オーバーヘッドが効いていたと予想できる
• クライアントでOrigin AS デコードした場合、ある程度のところまではいくが頭打ちになる

という結果です。私には reasonable に見えます。

いずれにせよ、カンタンに 4~5倍 のスピードが手に入りました。🎉 ご指摘ありがとうございました！

*1:実装によるかもしれませんが、ハードウェアルーターでは難しいと思われます

inet-henge で、好みのネットワーク図を描くヒント

「構成管理DB から自動でネットワーク図を描く」というコンセプトで、inet-henge というライブラリを開発しています。

ネットワークは日々変化しますが、ネットワーク図の更新が面倒です。「このデバイスはあのデバイスとつながっている」くらいの接続情報の集まりから、オートレイアウトでネットワーク図を描きたい。これがモチベーションです。

ここでは、最近入った機能を使って 好みのネットワーク図を描くためのヒントを紹介します。

計算結果のキャッシュ

描画のたびに計算結果である位置情報をキャッシュし、それをヒントにすることで2回目以降の表示が高速になりました。

• キャッシュはブラウザに保存される
• 入力データが変わった場合はキャッシュを使わない

キャッシュを参照せず常に計算を行うには、次のように positionCache オプションを false にします。

<script>
  var diagram = new Diagram('#diagram', 'bar.json', {positionCache: false});
  diagram.init('bandwidth', 'interface');
</script>

計算ステップ数を調整する

2回目以降はキャッシュを使えるという前提のもと、計算ステップを増やすことで よりよい配置を得つつ (2回目以降の) 表示速度を落とさない、ということが可能になりました。

このオプションを理解するために、内部で利用している D3.js のforce layout について説明します。

force layout はノード間に引力や斥力が働く場を想定し、初期配置から小刻みに時間ステップを進めながらノード配置を計算して収束させるD3.js モジュールです。ノード数やリンク数が増えるにつれ、一般的には収束までに必要な時間ステップ数が増加します。よりよいネットワーク図を得る代わりに表示時間が長くなるトレードオフがあったわけです。

これについて、過去のinet-henge では 最大時間ステップ数 = 1000 を決め打っていました 💦
表示のたびに再計算する仕様 & スピード優先 でした。

ここが可変になり、ネットワーク規模に合わせたステップ数を設定できます。デフォルトは今まで通りの 1000 です。

<script>
  var diagram = new Diagram('#diagram', 'bar.json', {
    ticks: 2000  // 2000 ステップまで計算する
  });
  diagram.init('bandwidth', 'interface');
</script>

CSS スタイリング

次のようなJSONデータを

{
  "nodes": [
    { "name": "POP1-A" },
    { "name": "POP1-B" },
    { "name": "POP2-A", "icon": "https://inet-henge.herokuapp.com/images/router.png" },
    { "name": "POP2-B", "icon": "https://inet-henge.herokuapp.com/images/router.png" },
    { "name": "POP3-A", "icon": "https://inet-henge.herokuapp.com/images/router.png" }
  ],

  "links": [
    { "source": "POP1-A", "target": "POP1-B",
      "meta": { "interface": { "source": "ge-0/{0,1}/0", "target": "Te0/{0,1}/0/0" }, "bandwidth": "20G" } },
    { "source": "POP2-A", "target": "POP2-B",
      "meta": { "interface": { "source": "ge-0/{0,1}/0", "target": "Te0/0/{0,1}/0" }, "bandwidth": "20G" } },
    { "source": "POP1-A", "target": "POP2-A",
      "meta": { "interface": { "source": "ge-0/0/1", "target": "Te0/0/0/1" }, "bandwidth": "10G" } },
    { "source": "POP1-B", "target": "POP2-B",
      "meta": { "interface": { "source": "ge-0/0/1", "target": "Te0/0/0/1" }, "bandwidth": "10G" } },
    { "source": "POP3-A", "target": "POP2-B"}
  ]
}

次のHTMLのように描画するとします。

<!DOCTYPE html>
<html>

<head>
  <meta charset="utf-8" />
  <script src="https://cdnjs.cloudflare.com/ajax/libs/d3/3.5.17/d3.js"></script>
  <script src="https://inet-henge.herokuapp.com/js/cola.min.js"></script>
  <script src="https://inet-henge.herokuapp.com/js/inet-henge.js"></script>
</head>

<body>
  <div id="diagram"></div>
</body>

<script>
  var diagram = new Diagram('#diagram', 'bar.json', { pop: /^([^\s-]+)-/ });
  diagram.init('bandwidth', 'interface');
</script>

</html>

デフォルトで左のような図になりますが、右のようにCSS で要素ごとにスタイルを変えることが可能です。

• グループ、ノード、リンク全体にスタイルを当てる
• 特定グループにスタイルを当てる (POP1)
• 特定ノードにスタイルを当てる (POP1-A)
• 特定リンクにスタイルを当てる (POP1-A - POP1-B 間)

下のCSSは、右の図を出力するサンプルです。
配色を変えているのに加え、リンクにマウスオーバーすると強調表示するようになっています。

(リンクラベルが重なって読めませんが、後ほど調節します)

.group rect { opacity: 0.5; }
.node, .group rect { cursor: move; }

/* 特定 node, link のみスタイルを当てる */
.group.pop1 rect { fill: #4ecdc4 !important; }
.node.pop1-a rect { fill: #c7f464 !important; }
.link.pop1-a-pop1-b { stroke: #c44d58; }

/* リンクにマウスオーバーすると、リンクを太く & ラベル表示 */
.link:hover { stroke-width: 5px; }
.link:hover ~ .path-label {
   font-weight: bold;
   visibility: visible !important;
}

リンク長さの調節

先ほどの例で、マウスオーバーしたときのリンクラベルが重なっていました。

これは、次のようにリンク長さを調節することで解決できます。

<script>
  var diagram = new Diagram('#diagram', 'bar.json', {
    pop: /^([^\s-]+)-/,
    distance: function(force) { force.jaccardLinkLengths(100, 2); }
  });
  diagram.init('bandwidth', 'interface');
</script>

• ジャッカード距離を計算に使う
• 共通ノードを持たないノード間の、ベースとなる長さを 100
• ジャッカード距離に対する係数を 2

としています。

描画したい ノード数、リンク数 によっていい感じのパラメーターが変わってきますので、「見づらいな」と感じたら時々調節してみることをオススメします。

(調節はコンセプトに反するので、ラベルの重なり検知は課題のひとつ💪)

ネットワークステータスの反映

下のように、障害のあるルーターやリンクを強調表示できます。

データ:

{
  "nodes": [
    { "name": "POP1-A" },
    { "name": "POP1-B" },
    { "name": "POP2-A", "icon": "https://inet-henge.herokuapp.com/images/router.png" },
    { "name": "POP2-B", "icon": "https://inet-henge.herokuapp.com/images/faulty_router.png" },  // アイコン差し替え
    { "name": "POP3-A", "icon": "https://inet-henge.herokuapp.com/images/router.png" }
  ],

  "links": [
    { "source": "POP1-A", "target": "POP1-B",
      "meta": { "interface": { "source": "ge-0/{0,1}/0", "target": "Te0/{0,1}/0/0" }, "bandwidth": "20G" } },
    { "source": "POP2-A", "target": "POP2-B",
      "meta": { "interface": { "source": "ge-0/{0,1}/0", "target": "Te0/0/{0,1}/0" }, "bandwidth": "20G" } },
    { "source": "POP1-A", "target": "POP2-A",
      "meta": { "interface": { "source": "ge-0/0/1", "target": "Te0/0/0/1" }, "bandwidth": "10G" } },
    { "source": "POP1-B", "target": "POP2-B",
      "meta": { "interface": { "source": "ge-0/0/1", "target": "Te0/0/0/1" }, "bandwidth": "10G" } },
    { "source": "POP3-A", "target": "POP2-B", "class": "fault" }  // クラス指定
  ]
}

CSS:

.link.fault {
  stroke: #c44d58;
  stroke-dasharray: 5, 5;
}

出力:

ノードはアイコンの差し替えを、リンクは class 属性の追加によりスタイルを操作します。

補足: ほかのCSS ヒント

CSS スタイリングについて、別の記事も書きました。こちらも参考にしてみてください。

codeout.hatenablog.com

補足: JANOG41 で登壇しました

ずいぶん経ってしまいましたが、JANOG41 でinet-henge について話してきました。
LT で、事前投票 上位のトークが採択されるシステムでしたが…なんと一位 🎉🎉🎉

会期中やその後に「使ってみました」「ここ、こうなりませんか？」などなど多数のフィードバックを頂きまして、めちゃくちゃ有意義なミーティングでした。ありがとうございました！

今回紹介したヒントのほとんどが、そのときの話を参考に実装したものです。
まだまだフィードバックお待ちしてます！

JUNOS 17.2 の PEGパーサーで文法チェックする

ネットワーク運用のために、生成した / 手書きしたコンフィグを CIでテストしています。

おおよそ次のような単純なワークフローです。

1. コンフィグジェネレーターを実行、生成されたコンフィグをGitHub にpush
   • あるいは、手書きしてpush
2. Travis CI、Jenkins などでテスト
3. レビュー
4. マージ & デプロイ

乱暴に「コンフィグをテスト」と言いましたが、ここでは文法チェックを指しています。わざわざパーサー書くほど？ 意味あんの？ と思ってしまいますが、その理由は後ほど。

junoser

PEG パーサー + CI による文法チェックを実現するため、junoser というライブラリーをメンテしています。内部にコンフィグ構文木を持ち、JUNOS を使わず文法チェックしてくれるものです。

github.com

NETCONF(XML RPC) のスキーマからCLI 構文が連想できるという特徴を利用し、NETCONF XSD から構文木を生成しているのですが、この文法のもとになる XSD が JUNOS 17.2 になりましたよ、という話です。

JUNOS 17.2 になって変わった点

変更前は 12.1 でした。古い…

サポートされる文法が大幅に増えた

どれだけ増えたかは表現しづらいのですが、例えばサイズでいうと

Version	Lines of XSD	MB
12.1	616,701	27
17.2	1,674,019	76

行数、ファイルサイズとも x2.7 くらいの分量です。

より厳密な構文木を作れるようになった

interfaces xe-0/0/0 description foo

たとえばこの文法の例でいえば JUNOS 12.1 では次のような XSD でした。

<xsd:complexType name="interfaces-type">
  <xsd:sequence>
    <xsd:element name="name">
      <xsd:complexType>
        <xsd:simpleContent>
          <xsd:restriction base="key-attribute-string-type">
            <xsd:enumeration value="interface-name">
              <xsd:annotation>
                <xsd:documentation>Interface name</xsd:documentation>
                <xsd:appinfo>
                  <flag>mustquote</flag>
                  <flag>text-choice</flag>
                  <flag>current-product-support</flag>
                </xsd:appinfo>
              </xsd:annotation>
            </xsd:enumeration>
          </xsd:restriction>
        </xsd:simpleContent>
      </xsd:complexType>
    </xsd:element>
    <!-- </name> -->
    <xsd:choice minOccurs="0" maxOccurs="unbounded">
      <xsd:element ref="undocumented" minOccurs="0"/>
      <xsd:element ref="junos:comment" minOccurs="0"/>
        ...
      <xsd:element name="description" minOccurs="0" type="xsd:string">
      </xsd:element>
      <!-- </description> -->
    </xsd:choice>
  </xsd:sequence>
</xsd:complexType>

<xsd:element name="name"> の部分に注目してください。この要素、CLI 上 name というキーワードが必要なのか、不要なのか XSD からは判別不能でした。そのためライブラリ内部で文脈ごとに独自判断し、構文木を生成していました。

「ベタな文法はサポートされているが、マニアックな文法はサポートされない」「パッチがモグラ叩きのよう」だったのはこのためです。

いっぽう、 17.2 では次のような XSD になっています。

<xsd:complexType name="interfaces-type">
  <xsd:sequence>
    <xsd:element name="name">
      <xsd:annotation>
        <xsd:appinfo>
          <flag>identifier</flag>
          <flag>nokeyword</flag>                       <!-- !!! -->
          <flag>current-product-support</flag>
          <identifier/>
        </xsd:appinfo>
      </xsd:annotation>
      <xsd:complexType>
        <xsd:simpleContent>
          <xsd:restriction base="key-attribute-string-type">
            <xsd:enumeration value="$junos-interface-ifd-name">
            </xsd:enumeration>
            <xsd:enumeration value="interface-name">
              <xsd:annotation>
                <xsd:documentation>Interface name</xsd:documentation>
                <xsd:appinfo>
                  <flag>mustquote</flag>
                  <flag>nokeyword</flag>                <!-- !!! -->
                  <flag>text-choice</flag>
                  <flag>current-product-support</flag>
                </xsd:appinfo>
              </xsd:annotation>
            </xsd:enumeration>
          </xsd:restriction>
        </xsd:simpleContent>
      </xsd:complexType>
    </xsd:element>
    <!-- </name> -->
    <xsd:choice minOccurs="0" maxOccurs="unbounded">
      <xsd:element ref="undocumented" minOccurs="0"/>
      <xsd:element ref="junos:comment" minOccurs="0"/>
      <xsd:element name="description" minOccurs="0" type="xsd:string">
        ...
      </xsd:element>
      <!-- </description> -->
    </xsd:choice>
  </xsd:sequence>
</xsd:complexType>

nokeyword フラグにより「name はCLI キーワードではなく XSD 的なプレースホルダーですよ」ということが判別可能になっています。

なお、16.X の XSD を確認していないため もう少し早い段階で nokeyword フラグが導入されていたかもしれません。

ほんの一例ですが、このようなスキーマ定義の改善によって より厳密な構文木が生成できるようになりました。その結果、モグラ叩き的パッチがマシになると期待できます。

しかしながら、おそらくパッチはゼロにはなりません。 XSD にバグがあるためです。

• CLI には存在するが、XSD に存在しない文法がある
• 必要なフラグが記述されていない

など、JUNOS 17.2 ベースのjunoser でもいくつか独自対応しています。サポートされない文法がありましたら、お気軽にコンタクトください。おそらくさくっとパッチできると思います。

遅くなった 😫

JUNOS 12.1 と17.2 で、

• XSD の行数
• XSD から生成したjunoser のパフォーマンス (秒間の処理コンフィグ行数)

を比較します。

今回 17.2 に上げると同時に、取得元プラットフォームを vSRX → vMX に変更しました。いくつかの組み合わせでプロットしたものが下のチャートです。

なお、JUNOS 15.1 の XSD は理解できなかったため、そのバージョンのjunoser を生成できていません。

XSD が x2.7 倍になったことにより、残念ながらパフォーマンスは 1/2.7 になっていることが分かります 😢

TODO

さきほど少し触れたように、おそらくXSD のバグによってサポートできていない文法が存在します。モグラ叩きはしばらく続きそうです。Juniper 社にフィードバックできるチャンスがあれば、XSD について報告したいと思っています。

最適化も必要です。たかだか2,000行くらいの設定ファイルに10秒オーダーかかってしまいます。

現在のところruby による実装ですが、go への移植も含めて検討する予定です。

また XSD 行数から想像すると、恐ろしいことに…プラットフォームによって XSD が全く異なるようです。 ユニバーサルなパーサーを生成するためには XSD をマージしないといけない可能性があります。

なぜPEG パーサーで文法チェックをするのか

最後に、後回しにしていた PEG パーサーの必要性について。

junoser の話をすると、割と「それは検証機でやればいいのにw」という反応をされます。

検証機を使った場合、junoser では不可能な文脈のチェック、たとえば「定義されていないポリシーを呼びだしている」ようなことも確認できます。それは素晴らしいことなのですが 残念ながらコストに合わないんですよ、という話をします。

ネットワークエンジニアリングの場合、たとえば実機で単体テストを行い 接続したシミュレーターとルーティングプロトコルを走らせて通信まで確認できたとしても、十分な安心感がありません。標準どおり / 期待通りに動作することはテストできても、通信相手 (場合によっては会社が違う) である特定のハードウェアと思ったように通信できるとは限らないためです。残念なことに それほどデバイスごとの癖に悩まされます。

仮にハードウェアがすべて標準どおりに動き、ベンダー間の相性問題が皆無だとしても AS(自社ネットワーク)全体として想定通りに動作するとは限りません。ネットワークデバイスはルーティングプロトコルによって互いに影響を及ぼし合います。その連鎖のぐあいは、なかなかに想像を超えてきます。

ネットワークの端っこのデバイスをちょこっといじると、通信もしてないし全く関係ないと思われた反対のほうでトラブルが！ みたいな予想外の事故にビビりながら運用しています。ネットワークが変にコケると 上に乗っているシステムやサービスを巻き込む可能性が高いため、とても神経質になります。

反対のほうでトラブルが！ の「反対のほう」は、場合によっては USの西海岸とかだったり いくつか通信事業者をまたいだ向こうだったりするため、正直「やってみないと分からん」といったことも山ほどあります。

ネットワークエンジニアリングでは、肌感覚として気軽にテストすることが困難です。正確には、気軽にできるテストで得られる安心感は限定的。「ある変更を加えた結果 全体としてどうか」を確かめないと安心を得られない、さらにはあまり事故れないことから、テストセットアップが大規模になり投資コストや人的リソースがかかりがち。テスト自動化はやるべきですが、それによって削減できるのは人的リソースのみです。いずれにせよ投資が必要。

ようやく本題ですが、直接収益を産まないわりに Lab環境は高価です。それを文法チェックごときに使いたくない。しかしながらそれをサボると、限られたメンテナンスウィンドウ中に Typo と戦うハメになります。なので、なるべく凡ミスは安い・カンタン・速い方法で対処するべきだ という思いがあります。

重い問題、たとえばベンダー間の相性やIntra-ASのルーティングは高価な Labテストで拾うしかありませんが、軽い Typo は安く速く潰したい。

こういうモチベーションで junoser をメンテしています。IOS-XR でも同じことをやりたいのですが、それはまた別の話。

お願い

さまざまなJuniper プラットフォーム、バージョンごとのxsd を求めています。相談に乗ってもいいよという方、是非ともご連絡ください！

パブリックデータから経路リークを探る

2017/08/25 12:30 (JST) ごろ、日本国内で大規模な通信障害が観測されました。

通信障害の内容について、とても詳細にまとめられている記事があります。

d.hatena.ne.jp

障害の内容はさておき、このエントリでは障害のしくみについて探ってみようと思います。

MRT Dump から見るBGP Update 数の急増

MRT Dump をもとに、該当時刻のBGP Update 数(毎分) をバーチャートにしました。

• 横軸: 時刻(UTC)
• 縦軸: BGP Update されたのべPrefix 数
  • 正: NLRI
  • 負: Withdraw

単純にBGP Update の回数をカウントしているため、Path Attribute だけの変更だったり、NLRI → Withdraw → 同じNLRI の場合でも すべて1回と数えています。

普段と比べるとUpdate 数が激増している期間があります。03:23 ~ 03:35 (UTC) の間です。

www.asahi.com

報道によれば「８分以内に正しい情報に修正した」とのことですが、実際にはすぐにBGP Update が収束しているわけではなさそうで、AS2497 からの経路変化でみると 発生(03:23) ~ 収束(03:34) とすこし時間幅が大きくなっています。これはおそらく経路を仲介しているAS の設計に依存し、MRAI などで伝搬を遅延させる影響を受けていると考えられます。

意図せずトランジットされた経路数はおよそ10万経路。直接の影響を受けたASは3000程度。また、通信先がこの吸い込みに影響されていた場合には直接影響のあったASではなくても多くの利用者がおかしいなあと思ったはず

— Yoshinobu Matsuzaki (@maz_zzz) 2017年8月25日

トータルでおおよそ10万経路が影響を受けていることは、MRT Dump からも観測できます。

route_leak=# SELECT count(DISTINCT prefix) FROM updates WHERE ix='wide' AND neighbor_as=2497 AND time > '2017-08-25 03:23'::TIMESTAMP AND time < '2017-08-25 03:35'::TIMESTAMP;
 count
--------
 114965
(1 row)

経路の急増が引き起こす問題

現在 IPv4 経路数はおおよそ70万弱とされているため、フルルートが一時的に 70万→80万 に増加したことになります。運悪くちょうどRIB / FIB キャパシティが限界を迎えることは十分ありえます。

この影響により、バックボーンルーター(ISP間など上位ネットワークで通信を行う装置)が、全体的に高負荷な状況に陥り、結果として16:16頃、弊社サーバー群と繋がるバックボーンルーターの一部が停止いたしました

http://hiroba.dqx.jp/sc/news/detail/a495eebbfa243b79c5b9b224c482d0c2/

限界値はさまざまですが、

1. フルルート運用している場合で、フルルートが閾値を超えた
2. パーシャルルート運用だが、経路フィルターを通過する経路が閾値を超えた

どちらの場合もルーターが不安定になったり、あるネットワークに通信できなくなったりします。

これは問題の原因のひとつと思われますが、これにあたった事業者はおそらく少数なのでは？と想像しています。

経路の中身は？

次のテーブルは観測されたAS_PATH の一例です。一部報道のとおり、AS15169 (Google) が経路をトランジットしているのがわかります。

route_leak=# SELECT aspath, count(distinct prefix) FROM updates WHERE ix='wide' AND neighbor_as=2497 GROUP BY aspath ORDER BY count DESC LIMIT 10;
          aspath           | count
---------------------------+-------
 2497 701 15169 4713       | 24831
 2497 701 15169 7029       |  7308
 2497 701 15169 8151       |  4639
 2497 701 15169 9121       |  4606
 2497 701 15169 9264 1659  |  3014
 2497 701 15169 9394       |  2129
 2497 701 15169 3209       |  1757
 2497 701 15169 7303       |  1580
 2497 701 15169 4230 28573 |  1475
 2497 701 15169 7545       |  1420
(10 rows)

少しおかしいですね。AS4713 (OCN) がAS15169 (Google) を介してインターネット接続しているかのようなAS_PATH です。

AS15169 (Google) から見るとAS4713 (OCN) はピアであり、本来であればトランジットであるAS701 (Verizon) に経路広告するべきではありません。このような経路が10万あったということですね。

注: 正確に言えば広告しても構わないのですが、流れてくるトラフィックをさばける回線キャパシティを担保するべきです。

AS701 に流れた経路は、そのままAS2497 (IIJ) に流れます。では、AS2497 はその経路をベストパスとして選択し、パケット転送するでしょうか？

通常ならAS_PATH 勝負で負けるため この経路がベストになることはありませんが、実はこの経路 Prefix Length が違っていました。

route_leak=# SELECT masklen(prefix) AS len, count(distinct prefix) FROM updates WHERE ix='wide' AND neighbor_as=2497 AND aspath ='2497 701 15169 4713' GROUP BY len ORDER BY count DESC LIMIT 10;
 len | count
-----+-------
  24 | 16594
  22 |  3035
  23 |  2432
  21 |  1764
  20 |   868
  19 |    79
  16 |    29
  18 |    15
  17 |    10
  15 |     3
(10 rows)

OCN クラスのISP であれば/12 ~ /20 くらいの大きなPrefix でルーティングすることが多いですが、障害中に観測された経路は/24 が大半です。Longest Match ルールにのっとってこの経路がベストになった、ということは容易に想像できます。

経路の中身について、ここまでまとめ

8/25 の障害時には、一例として AS2497 (IIJ) は「AS4713 (OCN) へのベストパスはAS15169 (Google) 経由」としていたことがMRT Dump から読み取れました。

ここからは想像ですが、10万経路ぶんのトラフィックがAS701、AS15169 に向かったため、

• 通信路のどこかで輻輳する
• 事業者の通信ポリシーによって通信が遮断される
• 遅延が増える (AS701、AS15169 は日本とは限らない)

ことが考えられます。

OCN と IIJ は一例であることに注意

ここまでIIJ → OCN 向きのトラフィックで説明しましたが、これは一例です。始点はIIJ に限らず、終点はOCN に限りません。アイボール側、コンテンツ側、どちらが影響を受けても通信が成り立たないことに注意です。

また、このエントリはMRT Dump を出発点にしています。限られた情報であり、障害時に起こっていた経路変化がすべてDump されているとは思えない = 見えていない影響も当然あると思われます。

大量の/24 はどこから来たか？

MRT Dump 上でみると、これら/24 のOrigin AS は4713 です。「4713 がOriginate した」と考えるのが自然です。

BGPMON の記事 でもそう考察されています。

ピアリング回線が複数あり、特定のトラフィックを特定の回線に乗せるためのトラフィックエンジニアリングですね。「経路はふつうAS15169 で止まるが、誤ってリークした」というのはありそうです。

いっぽう、AS4713 以外の事業者が生成している可能性ありそう、とも考えています。

「途中の事業者がPrefix を分割する」ようなケースです。ふつうはあまりやらないTE ですが、可能性を考えるためにAS15169 の右隣 != Origin AS なAS_PATH に注目してみましょう。観測されたAS_PATH のうち15169 より右を抜き出します。

route_leak=# SELECT substring(aspath from '15169.*') AS path, count(distinct prefix) FROM updates WHERE ix='wide' AND neighbor_as=2497 GROUP BY substring(aspath from '15169.*') ORDER BY count DESC LIMIT 10;
       path       | count
------------------+-------
 15169 4713       | 24831
 15169 7029       |  7308
 15169 8151       |  4639
 15169 9121       |  4606
 15169 9264 1659  |  3014
 15169 9394       |  2129
 15169 3209       |  1757
 15169 7303       |  1580
 15169 4230 28573 |  1475
 15169 7545       |  1420
(10 rows)

たとえば 15169 9264 1659。 Prefix でいうと61.60.96.0/24 など。

RIPEstat によれば、この経路は障害発生中にのみ存在しています。

https://stat.ripe.net/widget/bgplay#w.resource=61.60.96.0/24&w.ignoreReannouncements=false&w.starttime=1503551751&w.endtime=1503810951&w.rrcs=0,1,2,5,6,7,10,11,13,14,15,16,18,20&w.instant=null&w.type=bgp

あくまで想像の域を出ませんが、次のような可能性も考えられます。

経路だけをみれば、AS1659 (TANet) はAS9264 (ASNET) との間に複数回線もち、BGP によるTE を行なっているようです。この影響がAS15169 (Google) に漏れ聞こえ、インターネットに広告されているわけですが、この経路は障害のあった時間帯しか存在しません。

通常のルーティングとしては何か不自然です。AS9264 が他にも広告するためインターネットで常に観測されそうなのに、それがない。どちらかといえば、想像ですが「間の事業者が内部利用のために経路を生成した。それが漏れてしまった」と考えるほうがしっくりきます。

このように障害中のみ観測された経路、かなりの数あるようです。

海外に目を向ける

では、日本以外ではどうでしょう？

Route Views Project はグローバルにコレクターを配置しており、一部海外IX での経路変化を記録しています。

障害のあった期間中のBGP Update 総数を数えてみれば影響のあった事業者、なかった事業者のあたりをつけることができます。次のテーブル中で、count が小さいAS (neighbor_as) ほど影響が軽微だったと考えられます。

(count は観測されたBGP Update のユニークprefix 数、neighbor_as はRouteViews コレクターとピアしているneighbor AS )

route_leak=# SELECT ix, neighbor_as, count(distinct prefix) FROM updates GROUP BY ix, neighbor_addr, neighbor_as ORDER BY ix, count DESC;
    ix    | neighbor_as | count
----------+-------------+--------
 3        |         286 | 101331
 3        |       45352 |      5
 3        |      134708 |      3
 3        |        5645 |      3
 3        |        6939 |      3
 3        |       40387 |      3
 4        |       45177 |  97396
 4        |       48526 |  85617
 4        |       38726 |  75787
 4        |       34288 |  74560
 4        |       36236 |  74365
 4        |       24482 |      8
 4        |       24516 |      7
 4        |       24516 |      7
 4        |       63956 |      5
 4        |       38883 |      3
 4        |       58682 |      3
 4        |       58511 |      3
 4        |       58511 |      3
 4        |       58511 |      3
 4        |       38726 |      3
 4        |        1351 |      3
 6        |       31019 |    100
 6        |       53364 |     10
 eqix     |        3257 |     10
 eqix     |       41095 |      4
 eqix     |       11039 |      3
 eqix     |        6939 |      3
 isc      |        2497 | 114601
 isc      |        6939 |      3
 linx     |       41695 |  91612
 linx     |       34288 |  74560
 linx     |       37271 |     98
 linx     |       37271 |     98
 linx     |       58511 |     28
 linx     |       58511 |     28
 linx     |        3257 |     10
 linx     |       13030 |      5
 linx     |       13030 |      5
 linx     |       14537 |      4
 linx     |        6667 |      3
 linx     |        6939 |      3
 linx     |       37271 |      3
 linx     |       58511 |      3
 linx     |       37271 |      3
 linx     |       58511 |      3
 nwax     |        1798 |     98
 nwax     |       15301 |      3
 nwax     |       54073 |      3
 oregon   |        2497 | 114973
 oregon   |         286 | 101781
 oregon   |         701 |  98183
 oregon   |        7660 |  94091
 oregon   |       23673 |      8
 oregon   |      393406 |      7
 oregon   |       62567 |      7
 oregon   |       31019 |      5
 oregon   |        1221 |      5
 oregon   |       13030 |      5
 oregon   |       37100 |      4
 oregon   |       40191 |      4
 oregon   |        3303 |      4
 oregon   |       11686 |      4
 oregon   |       20912 |      3
 oregon   |        6762 |      3
 oregon   |        6939 |      3
 oregon   |        8492 |      3
 oregon   |       57463 |      3
 oregon   |       58511 |      3
 oregon   |       18106 |      3
 oregon   |       54728 |      3
 oregon   |         293 |      3
 oregon   |       47872 |      1
 perth    |       24516 |      5
 saopaulo |      262757 |  93512
 saopaulo |       53013 |  19034
 saopaulo |       53013 |  18707
 saopaulo |      262612 |  18692
 saopaulo |       52863 |  16650
 saopaulo |       28138 |     11
 saopaulo |       52940 |      7
 saopaulo |       28571 |      7
 saopaulo |      262354 |      7
 saopaulo |      262750 |      7
 saopaulo |       52888 |      7
 saopaulo |      264268 |      7
 saopaulo |      263047 |      4
 saopaulo |       52720 |      4
 saopaulo |        1916 |      4
 saopaulo |      262317 |      4
 saopaulo |       26162 |      4
 saopaulo |      263945 |      4
 saopaulo |       26162 |      4
 saopaulo |       26162 |      4
 saopaulo |       28329 |      3
 sfmix    |       32212 |  73638
 sg       |       59318 |     69
 sg       |       24482 |      7
 sg       |      133165 |      5
 sg       |       24115 |      3
 sg       |       24115 |      3
 sg       |       38880 |      3
 sg       |        9902 |      3
 sg       |       18106 |      3
 sydney   |       58511 |      3
 sydney   |        4739 |      3
 sydney   |       38809 |      3
 sydney   |        4826 |      3
 sydney   |       38880 |      2
 telxatl  |        6082 |      3
 telxatl  |       53828 |      3
 telxatl  |        6939 |      3
 wide     |        2497 | 114965
 wide     |        7500 | 100240
(114 rows)

日本ほどの影響度は少数派ですね？ それはなぜか？

よくわかりませんw

わかりませんが、障害トリガーとなった経路は「AS701 (Verizon) 経由でインターネットに流れた」と考えて差し支えなさそうです。観測されたAS_PATH のうち、15169 とすぐ左隣だけ抜き出します。

route_leak=# SELECT substring(aspath from '\d+ 15169') AS transit, count(distinct prefix) FROM updates GROUP BY transit ORDER BY count
   transit    | count
--------------+--------
 701 15169    | 162205
 1798 15169   |     98
 37271 15169  |     98
 43531 15169  |     72
 59318 15169  |     69
 58511 15169  |     28
 31019 15169  |     28
 394625 15169 |     10
 3257 15169   |     10
 62567 15169  |      3
 393406 15169 |      3
 11492 15169  |      1
(12 rows)

では、AS15169 (Google) はAS701 にのみリークしたのか？ もちろんその可能性は十分ありますが、もしそうではなく「他のトランジットにもリークしたが、そっちは問題にならなかった」のであれば学ぶべきポイントがありそうですよね。

普通、Tier1 プロバイダーは顧客向けBGP セッションに経路フィルターを設定します。多くの場合Peering DB やIRR から自動生成され、顧客が100% 制御できる かつオペミスを防げるようになっています。

1. AS701 にはそれがなく、他のトランジット事業者にはあった
2. AS701 にもあったが、特殊なアレンジをしていた。もしくは顧客がバイパスしていた
3. 経路がピアを経由する際、うまくmax-prefix filter が効いた

いろいろ想像できますが、根拠がないため想像しても意味はなさそう。。。もし可能であればこのあたりのカラクリを知りたいもんです。

なぜこのエントリーを書いたか

できれば障害から学びたいと思ったからです。次に同じことが起こったとき、防げる気がしない。

BGP におけるネットワークが Autonomous System (自律システム) と呼ばれる通り、これまでのインターネットは各AS が自律的にルーティングすることでうまく動いてきました。隣のAS がミスをしたとき、できれば自分のところで影響を小さくして インターネット全体をなんとなく維持させたいと考えています。

そのために、ご近所さんのルーティングポリシーは可能な範囲で知っておきたい。最悪を想定するためでもあります。各事業者がビジネスでやっている以上「やめてほしい」は通らないかもですが、たぶん備えることはできます。

「BGP 脆弱やん」というご指摘はごもっともで、今後も同じシステムでインターネットを運用できるのかは怪しいです。しかしながら まだ打てる手はありそうで、「なぜ海外で問題なかったか」はヒントになりそうな…という感じがしています。*1

意外と「日本人マイクロマネージメントしすぎ」みたいな話題に流れていくかもしれません。

以上、「Postmortem 見たいです」のラブレターでした。

*1:Path Validation のようなハードル高い必殺技もあります