この記事はYahoo! JAPAN 18 新卒 2 Advent Calendar 2018 16日目の記事です。
前回は@akawauchiさんの「会社のトイレが空いたかどうか、社内サイトからPCに通知させる」でした。
今日は、ネットワークの世界でよく話題に上がるSRv6について書きたいと思います。
はじめに
最近SRv6のドラフトを読んでいたのですが、このドラフトのタイトルは「SRv6 Network Programming」となっていました。Programmingって付いているので何かSRv6でプログラムっぽいことをしてみたくなりますよね。そこで、今回はSRv6を使って8パズルを解いてみたのでそれを紹介したいと思います。8パズルとは下のように3x3のマスに数字が並んでいて空白のマスをスライドさせながら右端の状態を目指すパズルです。
+---+---+---+ +---+---+---+ +---+---+---+
| 1 | 2 | 3 | | 1 | 2 | 3 | | 1 | 2 | 3 |
+---+---+---+ +---+---+---+ +---+---+---+
| 4 | | 5 | -> | 4 | 5 | | -> | 4 | 5 | 6 |
+---+---+---+ +---+---+---+ +---+---+---+
| 7 | 8 | 6 | | 7 | 8 | 6 | | 7 | 8 | |
+---+---+---+ +---+---+---+ +---+---+---+
そもそもSRv6が何かといいますと乱暴に一言で表せば、「Segment RoutingをIPv6で実現可能にするプロトコル」という説明になります。SRv6の特徴として<Locator>:<Function>のようにIPv6アドレスに「場所」+「挙動」の情報をもたせることがあります。これをソースルーティングで明示的に経由ノードを決めることでネットワーク上でのパケットの挙動を表現することが出来ます。この「挙動」に当たる部分をSRv6ではEndアクション等と呼びます。これがどのように活用されるか、そもそもSegment Routingとは何なのかなどの話は今回は省略したいと思います。他の資料等を参照していただければと思います。
8パズルソルバーの動作の様子
SRv6で8パズルを解くと言っても何をどうするのか想像がつきにくいかと思いますので、最初に自分が実装したソルバーの動いている様子を紹介します。次のようにtracerouteを使ってパケットを送ることでソルバーが8パズルを解きます。
traceroute to fd03::f (fd03::f), 30 hops max, 80 byte packets
1 * * *
2 * * *
3 * * *
4 * * *
5 fd02::1 (fd02::1) 0.617 ms 0.608 ms 0.610 ms
6 fd03::f (fd03::f) 1.730 ms 1.378 ms 1.369 ms
解いた結果は次のように受信側のifでパケットダンプを取ることで見ることが出来ます。16進ダンプなのでわかりにくいかと思いますが、0x0040から0x0070にソルバーの動いている様子が入っています。この範囲はSRv6用の拡張ヘッダであるSRHの経由ノードのアドレスが入っているフィールドになります。
0x0000: 600e 9fc7 0098 2b01 fd01 0000 0000 0000
0x0010: 0000 0000 0000 0001 fd03 0000 0000 0000
0x0020: 0000 0000 0000 000f 3a0a 0400 0400 0000
0x0030: fd03 0000 0000 0000 0000 0000 0000 000f
0x0040: fd00 0000 0000 0000 0000 0123 0f56 0478
0x0050: fd00 0000 0000 0000 0002 0123 0456 0f78
0x0060: fd00 0000 0000 0000 0004 0123 0456 07f8
0x0070: fd00 0000 0000 0000 0004 0123 0456 078f
0x0080: 8000 0c8a 05a4 0001 3fa9 0e5c 0000 0000
0x0090: 6068 0600 0000 0000 1011 1213 1415 1617
0x00a0: 1819 1a1b 1c1d 1e1f 2021 2223 2425 2627
0x00b0: 2829 2a2b 2c2d 2e2f 3031 3233 3435 3637
各列が示しているアドレスを書いてみると次のようになります。
0x0040: fd00::0:123:f56:478
0x0050: fd00::2:123:456:f78
0x0060: fd00::4:123:456:7f8
0x0070: fd00::4:123:456:78f
このアドレスの末尾3フィールドがパズルの実態に当たります。それぞれパズルの各列を示していて、0xfは空白を示します。パズルの形式で書いてみると次のようになります。
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
| 1 | 2 | 3 | | 1 | 2 | 3 | | 1 | 2 | 3 | | 1 | 2 | 3 |
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
| | 5 | 6 | -> | 4 | 5 | 6 | -> | 4 | 5 | 6 | -> | 4 | 5 | 6 |
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
| 4 | 7 | 8 | | | 7 | 8 | | 7 | | 8 | | 7 | 8 | |
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
ここまでくれば、実際に8パズルが解けていることがわかるかと思います。
パケットの流れ
実際に解けていることが確認出来たところでどの様にパケットを転送して8パズルを解いているかを解説したいと思います。先程パケットをtracerouteで送信していました、これはなぜかというとパズルを反復深化深さ優先探索で解いているからです。hop limitを使って探索の深さを制限して深さ優先探索を繰り返し行うことで、深さ優先探索で最短経路を求めることが出来ます。
深さ優先探索の実現方法ですが、単純にパケットの複製を行って送信することで実装しています。ソルバーがパケットを受け取ると、SRHの末尾のIPv6アドレスが持つパズルを確認します。このパズルが完成していたら本来の送信先にパケットを転送します。完成していなかった場合、空白マスを上下左右それぞれに動かしたパズルを持つIPv6アドレスをそれぞれ生成します。この生成したアドレスをSRHの末尾に追加しソルバーにもう一度転送します。これを繰り返すことで深さ優先探索を実装しています。
実装
最後にソルバーをどのように実装したのかを紹介して終わりたいと思います。SRv6をサポートしているオープンソースのソフトウェアには、VPPとLinuxなどがあります。今回は、Linuxを使って実装を行いました。Linuxで独自のEndアクションを実装する場合、主にinclude/uapi/linux/seg6_local.hとnet/ipv6/seg6_local.cを編集します。まずseg6_local.hで、次のようにアクションの種類を示す定数を定義します。
@@ -62,6 +62,8 @@ enum {
SEG6\_LOCAL\_ACTION\_END\_AM = 14,
/* custom BPF action */
SEG6_LOCAL_ACTION_END_BPF = 15,
+ /* 8puzzle solver */
+ SEG6_LOCAL_ACTION_END_PUZZLE = 16,
__SEG6_LOCAL_ACTION_MAX,
};
この定数を使ってseg6_local.cのseg6_action_tableに次のようにエントリを追加し、input_action_end_puzzleを実装すれば独自Endアクションが実装できます。
@@ -588,6 +738,11 @@ static struct seg6_action_desc seg6_action_table[] = {
.attrs = (1 << SEG6_LOCAL_BPF),
.input = input_action_end_bpf,
},
+ {
+ .action = SEG6_LOCAL_ACTION_END_PUZZLE,
+ .attrs = 0,
+ .input = input_action_end_puzzle,
+ },
};
実際に実装したものを以下に示します、自分が書いたすべてのコードはこちらにあります。int check_puzzle(uint64_t puzzle)でパズルが確認しているか確認して、完成していれば先頭のsegmentつまり本来の宛先にパケットを転送し、完成していない場合は空白部分を上下左右に移動させたアドレスをsegmentとして追加したパケットをそれぞれ送信するという処理になっています。
static int input_action_end_puzzle(struct sk_buff *skb, struct seg6_local_lwt *slwt)
{
struct ipv6_sr_hdr *srh;
struct in6_addr *segment;
uint64_t puzzle;
uint16_t prev_operation;
int pos;
srh = get_and_validate_srh(skb);
if (!srh) {
goto drop;
}
if (ipv6_hdr(skb)->hop_limit == 0) {
goto drop;
}
segment = srh->segments + srh->segments_left;
puzzle = ntohl(segment->s6_addr32[3])
+ ((uint64_t)(0xffff & ntohl(segment->s6_addr32[2])) << 32);
if (check_puzzle(puzzle)) {
srh->segments_left = 0;
ipv6_hdr(skb)->daddr = srh->segments[srh->segments_left];
seg6_lookup_nexthop(skb, NULL, 0);
return dst_input(skb);
}
prev_operation = segment->s6_addr16[4];
for (pos = 0; pos < 12 && ((puzzle >> (pos * 4)) & 0xf) != 0xf; pos++);
if (pos != 10 && pos != 6 && pos != 2 && prev_operation != SEG6_LOCAL_ACTION_END_PUZZLE_RIGHT) {
next_puzzle_operation(skb, puzzle, pos, SEG6_LOCAL_ACTION_END_PUZZLE_LEFT, segment);
}
if (pos != 8 && pos != 4 && pos != 0 && prev_operation != SEG6_LOCAL_ACTION_END_PUZZLE_LEFT) {
next_puzzle_operation(skb, puzzle, pos, SEG6_LOCAL_ACTION_END_PUZZLE_RIGHT, segment);
}
if (pos != 10 && pos != 9 && pos != 8 && prev_operation != SEG6_LOCAL_ACTION_END_PUZZLE_DOWN) {
next_puzzle_operation(skb, puzzle, pos, SEG6_LOCAL_ACTION_END_PUZZLE_UP, segment);
}
if (pos != 2 && pos != 1 && pos != 0 && prev_operation != SEG6_LOCAL_ACTION_END_PUZZLE_UP) {
next_puzzle_operation(skb, puzzle, pos, SEG6_LOCAL_ACTION_END_PUZZLE_DOWN, segment);
}
return 0;
drop:
kfree_skb(skb);
return -EINVAL;
}
以上になります。自分も実装してみるまではLinuxカーネルに機能を追加するのは難しいと思っていたのですが、少し機能追加をする程度なら上のコードのように簡単に実装できることがわかりました。みなさんもLinuxとSRv6で遊んでみませんか？