ネットワークシステム (2023 年度後期)

ネットワークの平均次数を求めなさい。

ネットワークの次数分布を求めなさい。

ネットワークの平均経路長と直径をそれぞれ求めなさい。

クラスタ係数が最大となるノードを答えなさい。

8 / 3

p(1) = 1 / 6, p(2) = 1 / 6, p(3) = 1 / 2, p(4) = 1 / 6

• 平均経路長: 8 / 5
• 直径: 3

ノード 3

以下のア.〜ウ. は、次数中心性・近接中心性・媒介中心性のいずれかを説明 している。ア.〜ウ. の説明に対応する中心性指標の名称を回答しなさい。

• ア. 当該ノードを通過する最短経路の数がどの程度であるかを表す
• イ. 当該ノードから他ノードへの平均距離が短いほど、そのノードが重要である、ということを表す
• ウ. 当該ノードの次数に相当する

各ノードの近接中心性を求めなさい。

ノード 4 とノード 5 の媒介中心性を求めなさい。 ただし、値を正規化する必要はない。

• ア. 媒介中心性
• イ. 近接中心性
• ウ. 次数中心性

C(1) = 5 / 8, C(2) = 5 / 7, C(3) = 5 / 9, C(4) = 5 / 6, C(5) = 5 / 7, C(6) = 5 / 11

B(4) = 7, B(5) = 8

ER モデルに従って、 N = 5, p = 1 / 2 のランダムグラフを手作業で生成してみなさい。

以下の文章は、ランダムネットワークの次数分布 P(k) の導出を 説明している。この文章における空欄にあてはまる適切な数式や記号を答えなさい。

• あるノードに着目し、そのノードの次数が k である確率を考える。
• ノードの次数が k であるためには、(1) k 個のノードとつながり、 (2) 残りの N - 1 - k 個のノードとつながらない、ということを満たせばよい。
• あるノードが、k 個のノードと同時につながる確率は、[ ア ] である。 一方、残りの N - 1 - k 個のノードと同時につながらない確率は、 [ イ ] である。
• さらに、N -1 個のノードから k 個のノードを求める組み合わせが [ ウ ] であることを踏まえれば、 次数分布 P(k) は [ エ ] である。

スケールフリー性を表現するために、BA モデルが導入した二つの仕組みを答え、 それらを簡潔に説明しなさい。

以下に示すグラフに対して、 BA モデルに従って、 新たにノードを追加した時に、 優先的接続で各ノードにリンクが接続される確率を答えなさい。

1 ----- 2
| \     | \
|   \   |  5 --- 6
|     \ | /
3 ----- 4

(乱数に依るので) 省略

• ア: p^k
• イ: (1 - p)^(N - 1 - k)
• ウ: N - 1 C k
• エ N - 1 C k * p^k * (1 - p)^(N - 1 - k)

(講義資料を参照すればよいので) 省略

• ノード1: 3 / 16
• ノード2: 3 / 16
• ノード3: 2 / 16 (= 1 / 8)
• ノード4: 4 / 16 (= 1 / 4)
• ノード5: 3 / 16
• ノード6: 1 / 16

コミュニティ構造を有するネットワークの特徴を、「密」および「疎」という語句を用いながら、 説明しなさい。

以下に示す無向グラフにおいて 4-クリークは存在するかどうかを答えなさい。

1 ----- 2
| \     | \
|   \   |  5 --- 6
|     \ | /
3 ----- 4

演習 2 で対象としたグラフにおいて、 ノード v1, v2, v3, v4 がコミュニティを形成するものとしたときに、 このコミュニティは「強いコミュニティ」であるかどうかを理由とともに答えなさい。

ノード同士が密に接続されたコミュニティと、 疎に接続されたコミュニティから構成されたネットワーク。

存在しない。

「強いコミュニティ」の定義に基づいて、全てのノードに対して、 k^int_v > k^ext_v が成立しているかどうかを確認すると、

v1: 3 > 0
v2: 2 > 1
v3: 2 > 0
v4: 3 > 1

である。よって、全てのノードに対して、 k^int_v > k^ext_v が成立しているため、 ノード v1, v2, v3, v4 から成るコミュニティは「強いコミュニティ」である。

本演習では、以下に示す無向グラフを対象とする。このときに、次の ア.〜エ. のコミュニティ集合が、講義資料の p.7 における定義を満たしているかどう かを検証し、満たいしていないものを列挙しなさい。その理由も述べること。

1 ----- 2
| \     | \
|   \   |  5 --- 6
|     \ | /
3 ----- 4

• ア. C = {{1, 3, 4}, {2, 4, 5, 6}}
• イ. C = {{1, 3, 4}, {2, 5}}
• ウ. C = {{1, 2, 3}, {4, 5, 6}}
• エ. C = {{1, 2, 4}, {3, 5, 6}}

講義資料の p.12 における、 右半分の例 (講義ビデオ内で解説していない方の例) に対して、 モジュラリティを計算しなさい。

1 ----- 2
| \     | \
|   \   |  5 --- 6
|     \ | /
3 ----- 4

• ア. ノード 4 が複数のコミュニティで重複しているから
• イ. ノード 6 がいずれのコミュニティにも属していないから
• エ. c2 において、ノード 3 とノード 5 との間で、路が存在しないから

省略

講義資料の p.8 で紹介した数値計算に従って、 \(S(1)\) 、 \(I(1)\) 、 \(R(1)\) を手計算しなさい。 パラメータおよび初期値は次の通りとする; \(S(0)\) =9,990、 \(I(0)\) =10、\(R(0)\) =0、 \(\beta\) =0.4、\(\gamma\) =0.2

講義資料の p.8 で紹介した数値計算を行うプログラムを、 何らかのプログラミング言語で実装し、 講義資料の p.9 で掲載しているグラフを求めてみなさい。

• \(S(1)\) = 9,990 - (0.4 * 9,990 * 10) / 10,000 = 9986.004
• \(I(1)\) = 10 + (0.4 * 9,990 * 10) / 10,000 - 0.2 * 10 = 11.996
• \(R(1)\) = 0 + 0.2 * 10 = 2

• Python 言語の場合:

Google Colab
https://colab.research.google.com/drive/1fzc0MdkKuTWvXas-4-rYNOIl67oQ_s98?usp=sharing#scrollTo=e8jzirdi8mot

• C 言語の場合:

#include <stdio.h>

#define ARRAY_SIZE 1024
#define MAX_TIME 100

int N = 10000;
double BETA = 0.4;
double GAMMA = 0.2;
double DELTA = 1;

int
main()
{
  int k = 0;
  double S[ARRAY_SIZE], I[ARRAY_SIZE], R[ARRAY_SIZE];
  double T[ARRAY_SIZE];
  S[0] = 9990; I[0] = 10; R[0] = 0;
  T[0] = 0;

  for (k = 0; k < MAX_TIME / DELTA; k++) {
    T[k + 1] = T[k] + DELTA;
    // first-order approximation
    S[k + 1] = S[k] - BETA / N * S[k] * I[k] * DELTA;
    I[k + 1] = I[k] + (BETA / N * S[k] * I[k] - GAMMA * I[k]) * DELTA;
    R[k + 1] = R[k] + GAMMA * I[k] * DELTA;
  }

  for (k = 0; k < MAX_TIME / DELTA; k++) {
    printf("%.2f S %.4f\n", T[k], S[k]);
    printf("%.2f I %.4f\n", T[k], I[k]);
    printf("%.2f R %.4f\n", T[k], R[k]);
  }
}

SIR モデルにおける基本再生産数の定義を、 記号を用いながら、 答えなさい。

ネットワーク上の情報拡散を抑制するための方策を、 ネットワークを構成するグラフの観点から、 答えなさい。

(講義資料に記述されているので) 省略

例: ネットワークからノード/リンクを取り除く。

無線センサーネットワークにおける通信に、 WWAN 向けの規格が不適である理由を説明しなさい。

IEEE 802.15.4 で採用されている CSMA/CA は、 CSMA とどのように違うかを説明しなさい。

(WWAN 向けの規格は長距離の伝送を可能とするものの、) 消費電力が (WPAN 向けの規格と比較して相対的に) 大きいという性質が、 バッテリーで長時間稼動する、 ということが求められるセンサーには、 適していないため。

• 搬送波を検知する前にランダムなバックオフ時間を待機する。バックオフ時 間の最大値は、搬送波検知においてチャネルが使用中であることを検出する 度に、増大させる。
• フレームを受信した端末は、その送信者に、確認通知 (ACK) フレームを転送する

DTN を説明した以下の文章における空欄にあてはまる適切な語句を答えなさい。

• DTN は、Delay-Tolerant Networking の略称であり、(大きな) [ ア ] を許 容しながら通信を実現する技術である。
• DTN は、[ イ ]・[ ウ ]・[ エ ] 型の通信である。[ イ ] は、端末はメッ セージを一時的に蓄えることである。[ ウ ] は、メッセージを保持したま ま移動することである。[ エ ] は、他の端末と接触すると、メッセージの 複製を転送することである。
• DTN における初等的なメッセージルーティングを [ オ ] と呼ぶ。[ オ ] は、端末が他の端末と接触すると、必ずメッセージの複製を渡す、というも のであり、その結果として、メッセージが、疫病が広まるのと同じように、 広まっていく。

エピデミックブロードキャストの利点と欠点をそれぞれ説明しなさい。

DTN シミュレータをインストールし、シミュレーションを実行しなさい。

h-ohsaki/dtnsim
https://github.com/h-ohsaki/dtnsim

• ア: 遅延
• イ: 蓄積
• ウ: 運搬
• エ: 転送
• オ: エピデミックブロードキャスト

• 利点: 遅延をもっとも減らすことができること
• 欠点: ネットワーク資源を過剰に浪費すること

Linux であれば以下のようにすればよい。

> pip3 install dtnsim
> dtnsim

SDN の特徴を列挙しなさい。

• ルーティングに相当する制御プレーンとフォワーディングに相当するデータプレーンとを分離し、 制御プレーンをコントローラが集中的に管理する。
• パケットの宛先単位ではなくフロー単位で、パケットの処理を決定する。
• ソフトウェアによってネットワークをプログラム可能とする。

以下に示すネットワークを考える。

host1
      \
	cache --- server
      /
host2

このネットワークにおける各要素の役割は次の通りである。

• host1 および host2 は、 server が保持するコンテンツを要求する。
• cache は、自身を通過するコンテンツの複製を、一時的に保持することができる。
• server は、コンテンツのオリジナルを保持する。

このときに、 cache が有効に機能するシナリオを説明しなさい。

ネットワーク内のキャッシュからコンテンツを配信することの恩恵を、 通信品質の観点で、 説明しなさい。

host1 があるコンテンツを要求し、その後に、同一コンテンツを host2 も要求する、というシナリオ。

• コンテンツを取得するのに要する時間を削減できる
• ネットワーク内を転送されるトラヒック量を削減できる

以下のア. 〜ウ. は、 ICN におけるルータが有する主要なデータ構造の役割を簡潔に説明している。 ア. 〜ウ. の説明と合致するデータ構造の名称を答えなさい。

• ア. 要求パケットの転送先を管理する
• イ. 自身がキャッシュしているコンテンツを管理する
• ウ. パケットが到着したポート、つまり応答パケットの返送先を管理する

以下の文章は、ルータが要求/応答パケットを受信したときの処理の流れを 説明している。 以下の文章における空欄に当てはまる適切な語句を解答しなさい。

• ICN ルータが要求パケットを受信したときの処理の流れ
  1. [ ア ] に当該コンテンツがキャッシュされているかを確認する。 コンテンツが [ ア ] にキャッシュされていれば、コンテンツを返送する。
  2. コンテンツが [ ア ] にキャッシュされていなければ、 [ イ ] に、要求パケットに対応するエントリが存在するかを確認 する。エントリが存在すれば、要求パケットが流入した [ ウ ] を当該エントリに追加する。
  3. [ イ ] エントリが存在しなければ、[ エ ] に、 要求パケットに対応するエントリが存在するかを確認する。[ エ ] エントリが存在すれば、要求パケットを次ノードに転送する。
• ICN ルータが応答パケットを受信したときの処理の流れ
  1. [ オ ] に、応答パケットに対応するエントリが存在するかを確認する。
  2. 応答パケットを [ カ ] にキャッシュする。この時に、 [ カ ] が完全に占有されている場合には、 キャッシュ置き換えアルゴリズムに従って、 [ カ ] からコンテンツを破棄した上で、 新たにコンテンツを挿入する。
  3. [ オ ] エントリに含まれている全ての [ ウ ] に応答パケットを送出する。

• ア. FIB (転送情報ベース)
• イ. CS (コンテンツストア)
• ウ. PIT (ペンディング要求テーブル)

• ア: CS (コンテンツストア)
• イ: PIT (ペンディング要求テーブル)
• ウ: フェース/出力ポート
• エ: FIB (転送情報ベース)
• オ: PIT (ペンディング要求テーブル)
• カ: CS (コンテンツストア)