こんにちは、中野です。
2019年4月1日に、「シナプスの「技術者ブログ」はじめます!!」 として、この技術ブログを立ち上げて、4年が経ちました。
だいたい月2記事が投稿されていて、当初の予定どおりのペースで継続できています。 また、イベント等で他社エンジニアの方に会った際に、「技術ブログ、見てます!!」とお声がけいただく事もあり、ありがたい限りで、そういったお声が励みになったりもしています。
さて今回は、タイトルのとおりですが、RFCを読みながら、MRTと呼ばれるフォーマットよりBGP UpdateメッセージをRubyでパースするツールを作ってみたので、記事にしてみました。
シナプスは、鹿児島を主な営業エリアとするインターネット・サービス・プロバイダ(ISP)で、AS7511というAS番号でネットワーク運用を行っています。
運用する中で、他ネットワークとの通信ができない状況の際に、シナプスの所有するIPアドレスブロックが他のネットワークからどういう状態に見えているかを確認する事があり、様々なツール/サービスを利用しています。
その1つに「Route Views Project」というものがあり、そのプロジェクトにはBGPのルーティングテーブルを定期的にダンプしたものや、BGP Updateメッセージを記録しているものがあります。 今回作ったツールは、このBGP Updateメッセージを解釈し、検索・表示・再利用するためのものです。
Route Views Projectとは
Route Views Projectとは、インターネットのルーティングデータを収集し、研究や解析を目的としたリアルタイムの情報源として提供する、オレゴン大学のプロジェクトです。
世界37ヶ所にルーティングデータを収集するコレクタが設置され、異るロケーションから様々なBGPの情報を確認することが可能となっています。
また、収集された以下のデータはアーカイブとして、MRTフォーマットにて公開されています。
- 2時間毎のRIB(Routing Information Base)
- BGP Updateメッセージ
開発したツールは、BGP Updateメッセージを対象としています。
MRTとは
MRTフォーマットは、「RFC 6396 Multi-Threaded Routing Toolkit (MRT) Routing Information Export Format」に規定されている、さまざまな種類のルーティング情報の記録するためのバイナリフォーマットです。
主なところでは、以下の情報の格納をサポートしています。
- BGP RIB(Routing Information Base)
- BGP Message
- OSPFv2/v3 Message
- IS-IS Message
MRTのデータ構造
BGP Updateメッセージが格納されているMRTは、以下のような階層のデータ構造となっています。
MRTヘッダ
3. Extended Timestamp MRT Header 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Timestamp | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Subtype | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Microsecond Timestamp | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Message... (variable) +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 2: Extended Timestamp MRT Header 引用元: https://datatracker.ietf.org/doc/rfc6396/
Route Views Projectにて提供されているBGP Updateメッセージのアーカイブは、Type 17「BGP4MP_ET」、SubType 4「BGP4MP_MESSAGE_AS4」となっています。
フォーマットのタイトルに「Extended Timestamp MRT Header」とあるように、拡張タイムスタンプに対応していて、時刻はマイクロ秒まで記録されています。
そして、このフォーマットの「Message...」部分に、BGP4MP_MESSAGE_AS4のデータが格納されています。
BGP4MP_MESSAGE_AS4
4.4.3. BGP4MP_MESSAGE_AS4 Subtype 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Peer AS Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Local AS Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Interface Index | Address Family | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Peer IP Address (variable) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Local IP Address (variable) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | BGP Message... (variable) +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 13: BGP4MP_MESSAGE_AS4 Subtype 引用元: https://datatracker.ietf.org/doc/rfc6396/
BGP4MP_MESSAGE_AS4は、BGPピア間のメッセージを格納するフォーマットで、4オクテットASに対応しています。
また、BGPピアの自AS/相手AS、自IPアドレス/相手IPアドレス、AFIなどが格納されています。
このフォーマットの「BGP Message...」の部分に、BGPメッセージが格納されています。
BGPヘッダ
4.1. Message Header Format 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | + + | | + + | Marker | + + | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Length | Type | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 引用元: https://datatracker.ietf.org/doc/rfc4271/
ようやくBGPにきました、まずはBGPヘッダです。
「Marker」の16オクテットは、互換性維持のため全て1に設定されています。この互換性維持が気になるので、別途調べてみたいと思います。
「Type」が2の場合、BGP Updateを表しています。
このBGPヘッダのあとに、BGP Updateのデータが続いています。
BGP Update
4.3. UPDATE Message Format +-----------------------------------------------------+ | Withdrawn Routes Length (2 octets) | +-----------------------------------------------------+ | Withdrawn Routes (variable) | +-----------------------------------------------------+ | Total Path Attribute Length (2 octets) | +-----------------------------------------------------+ | Path Attributes (variable) | +-----------------------------------------------------+ | Network Layer Reachability Information (variable) | +-----------------------------------------------------+ 引用元: https://datatracker.ietf.org/doc/rfc4271/
BGP Updateメッセージは、分かりやすい構造となっています。
項目 | 内容 |
---|---|
Withdrawn Routes Length | 削除(Withdraw)する経路を格納したデータのオクテット長 |
Withdrawn Routes | 削除する経路(0個以上) |
Total Path Attribute Length | パスアトリビュートを格納したデータのオクテット長 |
Path Attributes | パスアトリビュートのデータ(0個以上) |
Network Layer Reachability Information | NLRIと呼ばれる、広報する経路情報(0個以上) |
このうち、NLRIのデータフォーマットが興味深い構造だったので、紹介します。
Network Layer Reachability Information
+---------------------------+ | Length (1 octet) | +---------------------------+ | Prefix (variable) | +---------------------------+ 引用元: https://datatracker.ietf.org/doc/rfc4271/
LengthとPrefixの2タプルからなるデータ構造で、「Length」は/16や/24などのプレフィックス長を表しています。
「Prefix」は、IPアドレスプレフィックスを表すもので、プレフィックス長が/16の場合はIPアドレスの先頭2オクテット、/24の場合はIPアドレスの先頭3オクテットのみを格納しています。
また、プレフィックス長が0の場合は「Prefix」のデータは空で、「0.0.0.0/0」を表します。
いくつか例を上げると、以下のようになります。
データ <length, prefix> | NLRI |
---|---|
00 | 0.0.0.0/0 |
08 0a | 10.0.0.0/8 |
0c ac 10 | 172.16.0.0/12 |
18 c0 a8 00 | 192.168.0.0/24 |
データ構造まとめ
データ構造をまとめると、下図のとおりになります。
RubyでMRTのバイナリデータをパース
最初に試したやり方と課題
前述のようなデータ構造のバイナリデータのパースは、当初「BinData」というgemを使っていました。
例えば、BGP Updateは、
4.3. UPDATE Message Format +-----------------------------------------------------+ | Withdrawn Routes Length (2 octets) | +-----------------------------------------------------+ | Withdrawn Routes (variable) | +-----------------------------------------------------+ | Total Path Attribute Length (2 octets) | +-----------------------------------------------------+ | Path Attributes (variable) | +-----------------------------------------------------+ | Network Layer Reachability Information (variable) | +-----------------------------------------------------+ 引用元: https://datatracker.ietf.org/doc/rfc4271/
以下のようなコードで、パースしていました。
require 'bindata' class BgpUpdateRecord < BinData::Record uint16be :withdrawn_routes_length string :withdrawn_routes, read_length: :withdrawn_routes_length uint16be :total_path_attribute_length string :path_attributes, read_length: :total_path_attribute_length rest :nlris end update = BgpUpdateRecord.read(message) withdrawn_routes = update.withdrawn_routes nlris = update.nlris path_attributes = update.path_attributes
データ構造を、そのままDSLにて宣言的に書けるため、非常に読みやすいコードになっています。
ただし、15分間のBGP Updateメッセージ(70,195個, 8.4MB)のデータ処理に、43 秒もかかってしまう状態でした。
そのため、「Stackprof」という、どのメソッドがどれくらい呼び出されたかを測定するプロファイラにかけてみたところ、以下のような結果でした。
================================== Mode: cpu(1000) Samples: 37886 (0.14% miss rate) GC: 3451 (9.11%) ================================== TOTAL (pct) SAMPLES (pct) FRAME 12444 (32.8%) 12444 (32.8%) IO#pos 7889 (20.8%) 7885 (20.8%) Kernel#define_singleton_method 2406 (6.4%) 2406 (6.4%) (sweeping) 1343 (3.5%) 1343 (3.5%) IO#read 1161 (3.1%) 1161 (3.1%) (marking) 8878 (23.4%) 989 (2.6%) BinData::Struct#define_field_accessors_for 714 (1.9%) 714 (1.9%) IO#write 639 (1.7%) 609 (1.6%) Kernel#clone 25526 (67.4%) 515 (1.4%) Class#new 502 (1.3%) 497 (1.3%) MrtParse::BGP::PathAttribute::Record#no_extended_length? 19100 (50.4%) 395 (1.0%) BinData::Base#read 1948 (5.1%) 321 (0.8%) BinData::IO::Read#read 308 (0.8%) 308 (0.8%) Module#extend_object 1043 (2.8%) 303 (0.8%) BinData::LazyEvaluator#resolve_symbol_in_parent_context 334 (0.9%) 248 (0.7%) BinData::Base#top_level_set 246 (0.6%) 246 (0.6%) Integer#to_s
全般的に、BinDataの処理が多い状況でした(Kernel#define_singleton_methodもBinDataから呼ばれていました)。
バイナリデータを読む別の方法をベンチマーク
BinDataの処理に時間がかかっていそうな状況だったため、Rubyにてバイナリデータを読み込む別の方法について、ベンチマークを取ってみました。
このベンチマークは、MRTのデータ構造を踏まえて、以下のような簡単な処理にしました。
- バイナリデータは、ネットワークバイトオーダーの8オクテット
- 前の4オクテット、後の4オクテットを、32bit 符号なし整数として取り出す
Rubyでバイナリを扱う際は文字列リテラル(Stringクラス)をEncoding:ASCII-8BITを使用し、バイナリデータの読み込む方法は、以下の5種類を試しました。
- String#[]
- String#slice
- String#byteslice
- StringIO
- BinData
require 'bindata' require 'stringio' require 'benchmark/ips' data = "\x01\x02\x03\x04\x05\x06\x07\x08".b def string_bracket(data) # String#[] position = 0 d1 = data[position, 4].unpack1('N') position += 4 d2 = data[position, 4].unpack1('N') [d1, d2] end def string_slice(data) # String#slice position = 0 d1 = data.slice(position, 4).unpack1('N') position += 4 d2 = data.slice(position, 4).unpack1('N') [d1, d2] end def string_byteslice(data) # String#byteslice position = 0 d1 = data.byteslice(position, 4).unpack1('N') position += 4 d2 = data.byteslice(position, 4).unpack1('N') [d1, d2] end def string_io(data) # StringIO#read io = StringIO.new(data) d1 = io.read(4).unpack1('N') d2 = io.read(4).unpack1('N') [d1, d2] end class Record < BinData::Record uint32be :d1 uint32be :d2 end def bindata(data) # BinData#read bindata = Record.read(data) [bindata.d1, bindata.d2] end Benchmark.ips do |x| x.report('String#[]') { string_bracket(data) } x.report('String#slice') { string_slice(data) } x.report('String#byteslice') { string_byteslice(data) } x.report('StringIO') { string_io(data) } x.report('BinData') { bindata(data) } x.compare! end
このベンチマークを手元の環境にて実行した結果は、以下のようになりました。
Warming up -------------------------------------- String#[] 361.086k i/100ms String#slice 349.344k i/100ms String#byteslice 366.191k i/100ms StringIO 233.600k i/100ms BinData 5.592k i/100ms Calculating ------------------------------------- String#[] 3.590M (± 0.8%) i/s - 18.054M in 5.029106s String#slice 3.581M (± 0.8%) i/s - 18.166M in 5.073289s String#byteslice 3.696M (± 0.7%) i/s - 18.676M in 5.053313s StringIO 2.367M (± 0.1%) i/s - 11.914M in 5.032642s BinData 56.169k (± 1.0%) i/s - 285.192k in 5.077897s Comparison: String#byteslice: 3695916.7 i/s String#[]: 3590167.0 i/s - 1.03x (± 0.00) slower String#slice: 3580908.4 i/s - 1.03x (± 0.00) slower StringIO: 2367270.0 i/s - 1.56x (± 0.00) slower BinData: 56168.8 i/s - 65.80x (± 0.00) slower
「String#byteslice」は「BinData」よりも 65.80 倍高速 という結果となりました。
この結果より、コード全体を「BinData」から「String#byteslice」に書き直したところ、15分間のBGP Updateメッセージ(70,195個, 8.4MB)のデータ処理は、43 秒から1.73 秒に短縮できました。
できあがったもの
BGP Updateをパースするコードを、「BinData」から「String#byteslice」に書き直した結果、以下のようになりました。
require_relative 'nlris' require_relative 'path_attributes' class MrtParse class BGP class Update attr_reader :type, :withdrawn_routes, :nlris, :path_attributes def self.parse(data, length) withdrawn_routes_length = data.read(2).unpack1('n') withdrawn_routes = NLRIs.parse(data, withdrawn_routes_length) total_path_attribute_length = data.read(2).unpack1('n') path_attributes = PathAttributes.parse(data, total_path_attribute_length) nlris = NLRIs.parse(data, length - 2 - withdrawn_routes_length - 2 - total_path_attribute_length) new(withdrawn_routes, nlris, path_attributes) end def initialize(withdrawn_routes, nlris, path_attributes) @type = :Update @withdrawn_routes = withdrawn_routes @nlris = nlris @path_attributes = path_attributes end end end end
「String#byteslice」を使う場合、読み出し位置(position)を管理し、読み出し毎に読んだバイト数をpositionに加算する必要があったため、Stringをラップしたクラスを作り、読み出しと読み出し位置を加算するようにし、data.read(読み出すバイト数)
のように処理するようにしています。
Rubyのライブラリとして利用する方法
Rubyのライブラリとして、MRTを読み込む場合は、以下のようにして利用します。
# バイナリデータの読み込み data = File.binread('./updates.20230112.0145') # バイナリデータからMRTをパースする mrt = MrtParse.parse(data) # パースした結果数 mrt.stats => {:bgp4mp_message_as4=>70195} # パースした先頭のデータを取得 mrt.bgp4mp_message_as4.first => MrtParse::BGP4MpMessageAS4のオブジェクト(後述)が返る # パースしたMRTより、オリジンASが「7511」のみを抽出 mrt.filter_by_origin_as(7511) => AS7511が経路生成元となっているMRTオブジェクト(0〜N個)が返る # パースしたMRTより、「202.208.160.0/19」の経路広報/経路削除を抽出 mrt.filter_by_nlri('202.208.160.0/19') => 202.208.160.0/19の経路広報/経路削除したMRTオブジェクト(0〜N個)が返る # パースしたMRTより、オリジンASが「7511」で、「202.208.160.0/19」の経路広報とマッチするものを抽出 mrt.filter_by_origin_as(7511).filter_by_nlri('202.208.160.0/19') => AS7511が経路生成元で、202.208.160.0/19の経路広報を含む、MRTオブジェクト(0〜N個)が返る # AS及びNLRIは、パース時にも指定可能 mrt = MrtParse.parse(data, as: 7511, nlri: '202.208.160.0/19') => AS7511が経路生成元で、202.208.160.0/19の経路広報を含む、MRTオブジェクト(0〜N個)が返る
MRTの1エントリをRubyのオブジェクトとして表現
パースしたMRTの1つのエントリは、Rubyの1つのオブジェクトとして表現しています。
以下のエントリは、「2023年1月12日 1時45分」のアーカイブデータより、シナプスのAS7511の経路が広報された際のMRTデータです。
#<MrtParse::BGP4MpMessageAS4:0x000000029068e7e0 @afi="AFI_IPv4", @interface_index=0, @local_as_number=6447, @local_ip="128.223.51.102", @message= #<MrtParse::BGP::Update:0x0000000111831d20 @nlris= [#<MrtParse::BGP::NLRI:0x000000015cd95118 @ip_prefix="202.95.32.0", @prefix=19>, #<MrtParse::BGP::NLRI:0x000000015cd94e98 @ip_prefix="219.100.8.0", @prefix=22>, #<MrtParse::BGP::NLRI:0x000000015cd94a88 @ip_prefix="203.145.96.0", @prefix=20>, #<MrtParse::BGP::NLRI:0x000000015cd94628 @ip_prefix="101.50.60.0", @prefix=22>, #<MrtParse::BGP::NLRI:0x000000015cd94330 @ip_prefix="103.53.120.0", @prefix=22>, #<MrtParse::BGP::NLRI:0x000000015cd93f98 @ip_prefix="124.146.64.0", @prefix=19>, #<MrtParse::BGP::NLRI:0x000000015cd93c28 @ip_prefix="110.92.32.0", @prefix=19>, #<MrtParse::BGP::NLRI:0x000000015cd93958 @ip_prefix="103.208.96.0", @prefix=22>, #<MrtParse::BGP::NLRI:0x000000015cd934a8 @ip_prefix="210.146.80.0", @prefix=20>, #<MrtParse::BGP::NLRI:0x000000015cd93070 @ip_prefix="203.111.192.0", @prefix=20>, #<MrtParse::BGP::NLRI:0x000000015cd92d28 @ip_prefix="203.147.112.0", @prefix=20>, #<MrtParse::BGP::NLRI:0x000000015cd92940 @ip_prefix="202.208.160.0", @prefix=19>, #<MrtParse::BGP::NLRI:0x000000015cd926e8 @ip_prefix="202.79.8.0", @prefix=22>, #<MrtParse::BGP::NLRI:0x000000015cd92350 @ip_prefix="210.237.32.0", @prefix=19>, #<MrtParse::BGP::NLRI:0x000000015cd92030 @ip_prefix="203.140.160.0", @prefix=20>, #<MrtParse::BGP::NLRI:0x000000015cd91c98 @ip_prefix="101.53.104.0", @prefix=21>, #<MrtParse::BGP::NLRI:0x000000015cd918d8 @ip_prefix="202.79.12.0", @prefix=22>, #<MrtParse::BGP::NLRI:0x000000015cd91608 @ip_prefix="202.79.0.0", @prefix=22>, #<MrtParse::BGP::NLRI:0x000000015cd912c0 @ip_prefix="124.146.96.0", @prefix=19>], @path_attributes= [#<MrtParse::BGP::PathAttribute::Origin:0x000000015cd95fc8 @flag=#<MrtParse::BGP::PathAttribute::AttributeFlag:0x0000000111832540 @extended_length=0, @optional=0, @partial=0, @transitive=1>, @origin=:IGP, @type=:ORIGIN>, #<MrtParse::BGP::PathAttribute::AsPath:0x000000015cd95ca8 @flag=#<MrtParse::BGP::PathAttribute::AttributeFlag:0x00000001118324a0 @extended_length=0, @optional=0, @partial=0, @transitive=1>, @path_data=[[:AS_SEQUENCE, [3741, 3356, 9607, 7511]]], @type=:AS_PATH>, #<MrtParse::BGP::PathAttribute::NextHop:0x000000015cd958c0 @flag=#<MrtParse::BGP::PathAttribute::AttributeFlag:0x00000001118323b0 @extended_length=0, @optional=0, @partial=0, @transitive=1>, @next_hop="168.209.255.56", @type=:NEXT_HOP>], @type="Update", @withdrawn_routes=[]>, @peer_as_number=3741, @peer_ip="168.209.255.56", @time=2023-01-12 10:57:18 65261/262144 +0900, @type="BGP4MP">
このように、Rubyのオブジェクトとしているため、AS番号やNLRI以外の情報をもとにした抽出や、各種分析や統計データの作成にも利用しやすくしています。
コマンドラインツールとして利用する方法
Rubyのライブラリとしての利用以外にも、コマンドラインツールとしても動くようにしています。
以下は、上記同様「2023年1月12日 1時45分」のアーカイブデータより、AS番号が「7511」でNLRIが「202.208.160.0/19」である情報を抽出し、出力させたものです。
$ ./mrt_parse updates.20230112.0145 -a 7511 -p '202.208.160.0/19' TIME: 2023-01-12T10:57:18.248950+09:00 TYPE: BGP4MP FROM: AS3741(168.209.255.56) TO: AS6447(128.223.51.102) AFI: AFI_IPv4 PATH_ATTRIBUTES: ORIGIN(Well-known mandatory): IGP AS_PATH(Well-known mandatory): AS_SEQUENCE 3741 3356 9607 7511 NEXT_HOP(Well-known mandatory): 168.209.255.56 ANNOUNCES: 202.95.32.0/19 219.100.8.0/22 203.145.96.0/20 101.50.60.0/22 103.53.120.0/22 124.146.64.0/19 110.92.32.0/19 103.208.96.0/22 210.146.80.0/20 203.111.192.0/20 203.147.112.0/20 202.208.160.0/19 202.79.8.0/22 210.237.32.0/19 203.140.160.0/20 101.53.104.0/21 202.79.12.0/22 202.79.0.0/22 124.146.96.0/19
まとめ
これまでもRFCを読む機会はそれなりにありましたが、それを元に実装をするのは初めての経験でBGPというプロトコルを更に理解するいい機会となりました。
BGPは、「Border Gateway Protocol (BGP) Parameters」にあるように、インターネットが拡大する中で、多数のRFCにより、安全性・安定性を高められ、また機能拡張が為されているようで、そこの理解も深めることができました。
次のチャレンジとして、MRTのRIB(Routing Information Base)のパースも開発してみようと思います。