- インターネットにおけるルーティングの仕組を、他人に説明できるようになる。
https://lsnl.jp/~ohsaki/lecture/netcomp/2024/priv/05.pdf下図のルーティングテーブルを持つルータに関して、以下の問いに答えよ。
192.168.1.0/24 | 192.168.1.250
192.168.2.0/24 | 192.168.2.188
192.168.3.0/24 | 192.168.3.74
192.168.4.0/24 | 192.168.4.11
デフォルト | 192.168.1.250(1) ルータの有効なインターフェース数はいくつか。
(2) 送信元 IP アドレスが 192.168.3.12 で、 宛先 IP アドレスが 192.168.4.82 のパケットが送出されるインターフェースの IP アドレスを答えよ。
(3) 送信元 IP アドレスが 192.168.4.10 で、 宛先 IP アドレスが 192.168.0.11 のパケットが送出されるインターフェースの IP アドレスを答えよ。
ルータ a〜h で構成される以下のネットワークにおいて、 ディスタンスベクタ型のルーティングプロトコルを動作させた。
(1) すべてのルータが、 同時に、 一度だけ各隣接ルータと経路情報を交換した時の、 ルータ d のルーティングテーブル (各宛先ルータに対する次ホップと距離) を示せ。 ただし、 距離の定義はホップ数であるとする。
(2) (1) の直後に、 同時に、 もう一度各隣接ルータと経路情報を交換した時の、 ルータ d のルーティングテーブル (各宛先ルータに対する次ホップと距離) を示せ。
+---+
+----+ c +---+
| +---+ |
+---+ +-+-+ +-+-+ +---+
| a +----+ b +--------+ d +-----+ e |
+-+-+ +---+ +-+-+ +-+-+
| | |
| +---+ +-------+-+-+
+--+ f +----------------------+ g |
+-+-+ +---+
|
| +---+
+--+ h |
+---+課題 2 と同じネットワークにおいて、 リンクステート型のルーティングプロトコルを動作させた。 十分時間が経過した時の、 ルータ d のルーティングテーブル (各宛先ルータに対する次ホップとコスト) を示せ。 ただし、 各リンクのコストをすべて 1 とする。
ネットワークのルータ数が N、 各ルータのインターフェース数の平均 (= 各ルータに接続されているリンク数の平均) を k とする。
(1) ネットワーク中の総リンク数 |E| を N および k を用いて表せ。
(2) このネットワークに対して Dijkstra 法を実行した時の最悪時間計算量を N および k を用いて表せ。
参考: Dijkstra's algorithm
https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm(1) 4 (ルーティングテーブルに含まれるインターフェース数が 4 だから)
(2) 192.168.4.11 (宛先 IP アドレス 192.168.4.82 が 192.168.4.0/24 にマッチするから)
(3) 192.168.1.250 (宛先 IP アドレス 192.168.0.11 がルーティングテーブル上のいずれのエントリにマッチしないから)
(1) この場合、 隣接ルータのみから経路情報が取得できる。
宛先ルータ | 次ホップ 距離
b | b 1
c | c 1
e | e 1
g | g 1(2) この場合、 2 ホップ先のルータまでの経路情報が取得できる。
宛先ルータ | 次ホップ 距離
a | b 2
b | b 1
c | c 1
e | e 1
g | g 1
f | g 2十分時間が経過した後では、 各ルータ間の最短経路に基づくルーティングテーブルが作成される。
宛先ルータ | 次ホップ コスト
a | b 2
b | b 1
c | c 1
e | e 1
f | g 2
g | g 1
h | g 3(1) 各ルータのインターフェース数の平均が k、 1 本のリンクは 2 つのインターフェースに接続されるから
|E| = N * k / 2(2) Dijkstra 法の最悪時間計算量が O(|E| + |V| log |V|) であるから
O(|E| + |V| log |V|) = O(N * k / 2 + N log N) = O(N log N)下図の案内がされている面接会場に関して、以下の問いに答えよ。
技術部 | 3F 1号室
人事部 | 4F 大会議室
経理部 | 4F 中会議室
その他 | 3F 2号室(1) 面接会場の数はいくつか。
(2) 出身が工学部で、 技術部志望の学生の面接会場を答えよ。
(3) 出身が経済学部で、 知財部志望の学生の面接会場を答えよ。
(略解) (1) 4、3F 1 号室、3F 2号室
お互いに名前を知らない 10 人の学生 a〜i が左から横一列に並んで座っている。 これらの学生が、 隣に座っている人にメモを渡すことで、 できるだけ多くの学生の名前をお互いに知りたい。
(1) すべての学生が、 同時に、 一度だけ隣に (左右にいれば左右それぞれに) 座っている学生にメモを渡した場合に、 学生 d の知ることができる学生の名前を示せ。
(2) (1) の直後に、 同時に、 もう一度隣に座っている学生にメモを渡した場合に、 学生 d の知ることができる学生の名前を示せ。
(略解) (1) c、e、(2) b、c、e、f
類題 2 において、 隣に座っている学生にメモを渡す操作を繰り返し、 十分時間が経過した時を考える。 学生 d は、学生 a がどこに座っていると把握できるか。
(略解) 列の左端 (すべての学生が、学生 a〜i が左から横一列に並んで座っていることを知る (ことができる) から)
1 クラスの生徒数が N、 各生徒の仲の良い友人の数の平均を k とする。
(1) このクラスで、仲の良い生徒同士のペアの組み合わせは何通りか。N および k を用いて表せ。
(2) 仲の良い生徒同士のペアで構成したネットワークに対して Dijkstra 法を実行した時の最悪時間計算量を N および k を用いて表せ。
参考: Dijkstra's algorithm
https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm(略解) 課題 4 の答と同じ
「レポート課題 2024/09/25」と同じ。
https://lsnl.jp/~ohsaki/lecture/netcomp/2024/#10-10