ネットワークコンピューティング

URL


アクセスできたら、まず最初にブックマークに追加しておいてください。
講義ページ
https://lsnl.jp/l/netcomp

講義ページ (複数ページ版 (モバイル端末向け)、各回の資料のみ)
https://lsnl.jp/~ohsaki/lecture/netcomp/2024/toc.html

[授業開始時に提出] 出席確認フォーム (パスワードが必要です)
https://lsnl.jp/app/lecture/attend/show/netcomp

[授業中に使用] クリッカー (パスワードが必要です)
https://lsnl.jp/app/lecture/clicker/show/netcomp

[授業中に提出] リフレクションシート (パスワードが必要です)
https://lsnl.jp/app/lecture/refl/show/netcomp

[自習後に提出] レポート送信フォーム (パスワードが必要です)
https://lsnl.jp/app/lecture/report/show/netcomp

[授業中に提出] 確認テスト答案提出フォーム (パスワードが必要です)
https://lsnl.jp/app/lecture/quiz/show/netcomp

講義ビデオ (パスワードが必要です)
https://lsnl.jp/video/netcomp/2024/

連絡用メイリングリスト (教員に届きます)
netcomp-staff[atmark]lsnl.jp
本文には、必ず学生番号・氏名・メールアドレス (@kwansei.ac.jp のもの) を明記してください。

Kwanseiコンピテンシー
https://www.kwansei.ac.jp/about/kg_competencies

工学部 3つのポリシー
https://www.kwansei.ac.jp/s_engineering/philosophy/policy/

担当教員

大崎 博之
関西学院大学 理工学部 情報科学科
E-mail: netcomp-staff[atmark]lsnl.jp

ネットワークに関する疑問

Q1.インターネットを使えば、 メールしたり、 会話したり、 買物したり、 何でもできそうに思える。 インターネットはどういう仕組で動いているのだろうか? なぜ今の形になったのだろうか? インターネットのどこが優れているのだろうか? また弱点はどこだろうか?

Q2.インターネット上で、 次々と新しいサービスが登場している。 なぜあんなサービスが実現できるのだろうか? 他にどんな使い方ができるのだろうか? 自分で新しいサービスを作ることは可能だろうか? もし可能ならどうすればできるだろうか?

Q3.今のインターネットにできないことはあるだろうか? もしあるとすれはそれは何だろうか? できない理由は何だろうか? インターネットの限界を超えることは原理的に可能なのだろうか? 可能だとすればそれはなぜだろうか?

Q4.今、 ネットワーク研究の最先端では、 どんなネットワークが研究されているのだろうか? 新しいネットワークとはどのようなものだろうか? そのしくみはどうなっているのだろうか?

講義目的

クラウドコンピューティング、 新しいネットワークアーキテクチャ、 新しいネットワークサービスなど、 ネットワーキングとコンピューティングの融合によって実現される「ネットワークコンピューティング」に関する最新の知識を学ぶ。

到達目標

ネットワークコンピューティングの最新技術およびトレンドが理解できるようになる。

授業方法

講義形式で行う

成績評価

授業中試験 40%、平常リポート 60%

スケジュール

  2024/ 9/25 LAN の構成要素・通信プロトコル                                             
  2024/10/ 2 無線 LAN、VLAN (仮想 LAN)                                                          
  2024/10/ 9 インターネットの概要、TCP/IP                                             
  2024/10/16 IP プロトコル (1)                                                                  
  2024/10/23 IP プロトコル (2)                                                                  
  2024/10/30 前半の総復習                                                                
  2024/11/ 6 TCP プロトコル (1)                                                                 
  2024/11/13 TCP プロトコル (2)                                                                 
  2024/11/20 インターネットの要素技術 (経路制御)                                           
  2024/11/27 インターネットサービス (名前解決)                                            
  2024/12/ 4 DHCP、ネットワークアドレス変換                                             
  2024/12/11 HTTP
  2024/12/18 後半の総復習                                                                
  2025/ 1/ 8 授業中試験                                                                    



大崎が担当する科目に共通の連絡事項・アドバイス

注意事項、 教育方針、 学習のポイント、 病欠/公欠の時に何をすればよいか等を説明しています。

  大崎が担当する科目に共通の連絡事項・アドバイス
  https://lsnl.jp/~ohsaki/lecture/



LAN の構成要素・通信プロトコル

授業の流れ

1. 解説 (30 分)
2. グループワーク (55 分)
3. 確認テスト (10 分)
4. 採点・リフレクションシート記入 (5 分)

チーム分けの方針

- いろいろな人とチームになる
- チームの人数は自由に決めてよい

態度目標

- しゃべる
- 質問する
- 説明する
- 動く (立ち歩く)
- チームで協力する
- チームに貢献する

内容目標

- LAN (ローカルエリアネットワーク) とは何かを他人に説明できるようになる。

- MAC アドレスとは何かを他人に説明できるようになる。

- イーサネットの原理・特徴を他人に説明できるようになる。

- イーサネットの基本的な特性を簡単なモデルを用いて数理的に分析できるようになる。

注意事項

Wikipedia 日本語版およびブログ等を情報源として用いてはならない。

英語のトレーニングも兼ねて、 日頃から英語の文献を読むとよい。 英語を読み続けるのがつらい場合は、 日本語の文献を探すのではなく、 機械翻訳 (ChatGPT がおすすめ) を使って読むという方法もある。

テキスト

https://lsnl.jp/~ohsaki/lecture/netcomp/2024/priv/01.pdf

情報源

- 書籍

W. リチャード・スティーヴンス, ``詳解TCP/IP〈Vol.1〉プロトコル,'' ピ
アソンエデュケーション, 2000.

宮原 秀夫, 尾家 祐二, ``コンピュータネットワーク,'' 共立出版, 1999.

竹下 隆史, 村山 公保, 荒井 透, 苅田 幸雄, ``マスタリングTCP/IP 入門編
第5版,'' オーム社, 2012.

電子情報通信学会, ``電子情報通信ハンドブック,'' オーム社, 1988.

- オンラインドキュメント

Computer network
http://en.wikipedia.org/wiki/Computer_network

Local area network
http://en.wikipedia.org/wiki/Local_area_network

電子情報通信学会 知識ベース
http://www.ieice-hbkb.org/portal/

課題

課題 1

IV 号館 4F のグララボで PC を使用している時、 LAN、 ホスト、 スイッチ、 リンクはそれぞれ何に対応するか。 また、 それらはそれぞれどこにあるか。

課題 2

自身が使用している端末 (ノート PC もしくはスマートフォン) の MAC アドレスを答えよ。 また、 その MAC アドレスを割り当てた組織名を答えよ。

課題 3

イーサネットフレームに n (46 <= n <= 1500) オクテットのペイロードを格納する時の伝送効率 (リンクの通信容量のうちデータ転送に利用できる割合) を求めよ。 また、 伝送効率の最小値および最大値を求めよ。

課題 4

CSMA/CD の特性を近似的に解析したい。 (1) Q 台のホストが転送すべきデータを持っている、 (2) Q 台のホストはスロット単位で同期して動作する、 (3) 各ホストは各スロットにおいて確率 1/Q でフレーム伝送を試みる、 という単純化したモデルを考える。 このモデルでは、 Q 台のホストのうち 1 台のホストのみがフレーム伝送を試みた場合に限りフレーム伝送が行われる (0 台であれば未使用、 2 台以上であれば競合のため伝送に失敗する)。

あるスロットにおいて 1 台のホストのみがフレーム伝送を試みる確率 A を求めよ。 また、 いずれかのホストがフレーム伝送に成功するまでのスロット数の期待値 W を求めよ。

略解

課題 1

LAN →イーサネット LAN (グララボ、マルラボ、準備室)
ホスト→ Windows PC (グララボ)
スイッチ→イーサネットスイッチ (グララボ教卓横のラック内)
リンク→イーサネットケーブル (PC 背面から床下を通ってグララボ教卓横のラックまで)

課題 2

Windows であればコマンドプロンプトから ipconfig /all で確認できる。 iOS であれば、 設定→一般→情報の「Wi-Fi アドレス」で確認できる。

ipconfig
https://learn.microsoft.com/en-us/windows-server/administration/windows-commands/ipconfig

なお、 iOS 14 以降は MAC アドレスのランダム化を行っていることに注意。

Wi-Fi privacy
https://support.apple.com/guide/security/wi-fi-privacy-secb9cb3140c/web

MAC アドレスのブロックは IEEE が発行・管理しており、 MAC アドレスブロックのデータベースが公開されている。

IEEE Registration Authority
https://regauth.standards.ieee.org/standards-ra-web/pub/view.html#registries

例えば、 MAC アドレスが 94:EA:32:**:**:** であれば、 MAC Address Block Large (MA-L) (oui.txt) から Apple が割り当てたものであることがわかる。

94-EA-32   (hex)              Apple, Inc.
94EA32     (base 16)          Apple, Inc.
                              1 Infinite Loop
                              Cupertino  CA  95014
                              US

94:EA:32 のブロックは IEEE が割り当て、 そのブロック中の MAC アドレスは Apple が割り当てている。

課題 3

ヘッダが 7 + 1 + 6 + 6 + 2 で計 22 オクテット、 トレイラが 4 オクテットであるから、 イーサネットフレーム長は 22 + n + 4 = 26 + n オクテット。 26 + n オクテットのうち、 n オクテットだけがデータ伝送に利用されるから、 利用効率は

  n
------
26 + n

である。 n = 46 の時、 伝送効率は最小 (約 64 %) となり、 n = 1500 の時、 伝送効率は最大 (約 98%) となる。

課題 4

資料
Ethernet: Distributed Packet Switching for Local Computer Networks
http://magrawal.myweb.usf.edu/dcom/Ch3_MetcalfeBoggsCACM1976.pdf

ある 1 台のホストのみフレーム伝送を試みる確率は、 そのホストがフレーム伝送を試み、 他の Q - 1 台がフレーム伝送を試みない確率であるから

1/Q * (1 - 1/Q)^(Q - 1)

である。 あるスロットにおいて 1 台のホストのみがフレーム伝送を試みる確率 A は、 「フレーム伝送に成功する 1 台のホスト」が Q 通りあるから

A = Q * 1/Q * (1 - 1/Q)^(Q - 1) = (1 - 1/Q)^(Q - 1)

である。

待ちが発生しない確率が A、 1 スロットだけ待ちが発生する確率が (1 - A) * A (1 回伝送に失敗し、 2 回目で伝送に成功する確率) である。 同様に、 i スロットだけ待ちが発生する確率が (1 - A)^i * A (i 回伝送に失敗し、 次の i + 1 回目で伝送に成功する確率) である。 したがって、

      ∞
W =   Σ   i * (1 - A)^i * A = (1 - A) / A
    i = 0

である。

(補足)

W - (1 - A) W を考えると、

W - (1 - A) W = (1 - A) A + (1 - A)^2 A + (1 - A)^3 A + …

のように初項 (1 - A) A、 公比 1 - A の無限等比級数の和となっている。 これより、

W = (1 - A) / A

が求まる。

レポート課題 2024/09/25

授業終了後に自習を行い、 到達目標まで到達せよ。 疑問に思った点、 わからない点は各自で信頼できる文献を用いて調査せよ。

その後、「今週の作業内容」、 「『内容目標』をどの程度達成できた/できなかったか」、 「質問・要望・コメント」、 「感想」を「ネットワークコンピューティング」レポート送信フォームから送信せよ。

提出方法: 「レポート送信フォーム」から送信せよ。 レポートが正しく提出されると、レポートの控えが自身のメールアドレス宛に送信される。 レポートの控えは成績発表まで保存しておくこと。 レポートが再提出された場合は、 新しいほうを採点対象とする。

提出期限: 次回の授業開始の 48 時間前とする (例えば、 9/25(水) の課題であれば、 10/2(水) 1:30pm の 48 時間前である 9/30(月) 1:30pm)。 期限を過ぎたものは受理しない。

注意事項: 「質問・要望・コメント」は匿名にした上で公開する (講義ページに掲載する)。 公開されて困る内容は「質問・要望・コメント」等に含めないこと。 個人的な質問・相談等は「感想」の覧に記入せよ。

質問

- 第1回の確認テストは答案提出フォームに提出しなくてもよかったのでしょうか。

  はい (不要です)。



無線 LAN、VLAN (仮想 LAN)

授業の流れ・チーム分けの方針・態度目標

2024/09/25 のものと同じ。

https://lsnl.jp/~ohsaki/lecture/netcomp/2024/#10-1

テキスト

https://lsnl.jp/~ohsaki/lecture/netcomp/2024/priv/02.pdf

内容目標

- 無線 LAN の概要・特徴を他人に説明できるようになる。

- 無線ネットワークの特性を理解し、それを定量的に説明できるようになる。

- CSMA/CD と CSMA/CA の違いを他人に説明できるようになる。

- VLAN の概要および原理を理解し、VLAN 導入の効果を定量的に説明できるようになる。

課題

課題 1

学内で Wi-Fi を使用している時、 LAN、 ホスト、 スイッチ、 リンクはそれぞれ何に対応するか。 また、 それらはそれぞれどこにあるか。

課題 2

(1) BER (Bit Error Rate) が p の無線ネットワークにおいて、 長さ N オクテットのフレームが誤りなく伝送される確率を求めよ。

(2) BER が 10^-4 の時に、 1250 オクテットのフレームが誤りなく伝送される確率を答えよ。

課題 3

CSMA/CD と CSMA/CA の主要な違いを 2 つ述べよ。 また、 これらの違いがある理由を、 無線ネットワークの特性をもとに説明せよ。

課題 4

下図のイーサネット LAN において、 各ホストが送出するブロードキャストフレームの数を等しく n とする。 LAN 中でフレームの損失は起きないものとする。

(1) VLAN を使用しない場合に、 リンク上を伝送されるブロードキャストフレームの総数を答えよ。

(2) 図ように VLAN を構成した場合に、 リンク上を伝送されるブロードキャストフレームの総数を答えよ。

(3) VLAN 使用によるトラヒック削減率 (伝送されるフレーム数の削減率) を答えよ。

略解

課題 1

LAN → 無線 LAN (教室周辺)
ホスト → KGU-WLAN に接続している PC もしくはスマートフォン (教室内)
スイッチ → Wi-Fi のアクセスポイント (教室周辺)
リンク → 無線 (電磁波) (教室内の空間)

課題 2

(1) N オクテットは 8 * N ビットである。 フレームの伝送成功率は、 すべてのビットが正しく伝送される確率で与えられる。

(1 - p)^(8 * N)

(2) 上記に p = 10^-4、N = 1250 を代入すると

(1 - 10^-4)^10000 = 0.36786...

従って約 37% である。

課題 3

送信局がキャリアセンス失敗時に指数バックオフを行うこと。 受信局がフレームの正常受信時に ACK を送信局に返送すること。 CSMA/CD はこれらを行わないが、 CSMA/CA はどちらも行う。

無線リンクでは複数局の同時送信によるフレーム衝突を検出できない。 従って、 送信局はキャリアセンス時の衝突確率を下げるために指数バックオフを行う。 同様に、 送信局がフレームの伝送の成否を判断できないため、 受信局がフレーム伝送の成功を送信局に通知する。

課題 4

(1) リンク数が 6 であるから、 あるホストが送出したブロードキャストフレームは 6 リンク上を伝送される。 従って、 1 ホストあたり 6 n のブロードキャストフレームが LAN 上を伝送される。 ホスト数が 4 であるから、 伝送されるブロードキャストフレームの総数は

4 * 6 n = 24 n

(2) 上側の VLAN 上を伝送されるブロードキャストフレームの総数は

2 * 3 n = 6 n

下側の VLAN 上を伝送されるブロードキャストフレームの総数は

2 * 4 n = 8 n

従って、伝送されるブロードキャストフレームの総数は

6 n + 8 n = 14 n

(3) 削減されたブロードキャストフレーム数は 24 n - 14 n = 10 n であるから、 フレーム数の削減率は

10 n / 24 n = 0.417 であるから約 41%。

レポート課題・質問・要望・コメント 2024/10/02

「レポート課題 2024/09/25」と同じ。

https://lsnl.jp/~ohsaki/lecture/netcomp/2024/#10-10

要望

- レポート提出期限を一週間後に変更して欲しいです。

  質問を収集して、翌週の授業で回答できるようにするために「次回の授業開始の 48
  時間前」に設定しています。



インターネットの概要、TCP/IP

授業の流れ・チーム分けの方針・態度目標

2024/09/25 のものと同じ。

https://lsnl.jp/~ohsaki/lecture/netcomp/2024/#10-1

テキスト

https://lsnl.jp/~ohsaki/lecture/netcomp/2024/priv/03.pdf

内容目標

- パケット交換方式と回線交換方式それぞれの原理を他人に説明できるようになる。

- パケット交換方式の利点と欠点を他人に説明できるようになる。

- IP アドレスの構造と意味を理解し、他人に説明できるようになる。

- パケット交換方式と回線交換方式の優劣を定量的に議論できるようになる。

課題

課題 1

回線交換方式で動作するネットワークについて、 以下の小問に答えよ。 ただし、 スイッチ間のリンクの利用率をすべて等しく p_1、 各リンクの伝搬遅延をすべて等しく τ [s]、 各スイッチにおける処理遅延をすべて等しく Δ [s] とする。 ホスト X からホスト Y までのホップ数を h とする。

(1) ホスト X〜ホスト Y 間の呼損率 q_1 を求めよ。

(2) ホスト X からホスト Y までメッセージを伝送する時の通信遅延 D_1 を求めよ。

課題 2

パケット交換方式で動作するネットワークについて、 以下の小問に答えよ。 ただし、 各スイッチにおけるパケット損失率をすべて等しく p_2、 各リンクの伝搬遅延をすべて等しく τ [s]、 各スイッチにおける処理遅延およびキューイング遅延をすべて等しく Δ [s] および W [s] とする。 ホスト X からホスト Y までのホップ数を h とする。

(1) ホスト X〜ホスト Y 間のパケット損失率 q_2 を求めよ。

(2) ホスト X からホスト Y までパケットを伝送する時の平均遅延 D_2 を求めよ。

課題 3

16 進数で C0DAA8CA の IP アドレスについて、以下の小問に答えよ。

(1) 10 進ドット表記で示せ。

(2) アドレスクラスを答えよ。

(3) サブネットに収容できるホスト数を答えよ。

課題 4

課題 1 および課題 2 において、 p_1 = 0.1、 p_2 = 0.01、 h = 5、 τ = 1 [ms]、 Δ = 0 [ms] の場合を考える。 以下の小問に答えよ。

(1) q_1、q_2、D_1、D_2 をそれぞれ求めよ。

(2) 上の条件下において、 W の値がどの程度までなら、 回線交換方式よりもパケット交換方式のほうが望ましいと考えられるかを論ぜよ。

略解

課題 1

ホスト X〜ホスト Y 間に存在するスイッチ数が h - 1、 スイッチ間のリンク数が h - 2 である。

(1) h - 2 本のリンクがすべて利用可能である時に限り呼損とならないから

q_1 = 1 - (1 - p_1)^(h - 2)

(2) ホスト X〜ホスト Y 間に存在するリンク数が h、 スイッチ数が h - 1 であるから

D_1 = τ * h + Δ * (h - 1)

課題 2

ホスト X〜ホスト Y 間に存在するスイッチ数が h - 1 である。

(1) h - 1 台のすべてのスイッチにおいてパケット損失が起きない時に限りパケット伝送が成功するから

q_2 = 1 - (1 - p_2)^(h - 1)

(2) ホスト X〜ホスト Y 間に存在するリンク数が h、 スイッチ数が h - 1 であるから

D_2 = τ * h + (Δ + W) * (h - 1)

課題 3

(1) 192.218.168.202

(2) クラス C

(3) 254

課題 4

(1) q_1 = 0.271、q_2 = 0.039404、D_1 = 5 [ms]、D_2 = 5 + 4 W [ms]

(2) 省略

レポート課題・質問・要望・コメント 2024/10/11

「レポート課題 2024/09/25」と同じ。

https://lsnl.jp/~ohsaki/lecture/netcomp/2024/#10-10

要望

- 上の条件下において、 W の値がどの程度までなら、 回線交換方式よりもパケット交換方式のほうが望ましいと考えられるかを論ぜよ。の問題について自習をした時に分からなかったので、解説を上げてもらえると嬉しいです。

  これは「答が一意に定まらない」問題です。「私ならこう考える」というのを論じて
  ください。呼損率/パケット損失率も、通信遅延も小さいほうがベターです。

  q_1 = 0.271、q_2 = 0.039404、D_1 = 5 [ms]、D_2 = 5 + 4 W [ms] という条件で、
  例えば W = 0 で、送信するパケット数が 1 なら、パケット交換方式のほうが良いに
  決まっています (同じ通信遅延でロス率が小さいから)。同様に、W = 10 で、送信す
  るパケット数が 1 ならどうでしょう? パケット交換方式のロス率は回線交換方式の
  約 1/7 ですが、パケット交換方式の通信遅延は回線交換方式の 9 倍です。この両者
  を天秤にかけた時、あなたならどちらが良いと考えますか? 同様に、送信するパケッ
  ト数がもっと多い場合はどうでしょうか?



IP プロトコル (1)

授業の流れ・チーム分けの方針・態度目標

2024/09/25 のものと同じ。

https://lsnl.jp/~ohsaki/lecture/netcomp/2024/#10-1

内容目標

- OSI 参照モデルとは何かを他人に説明できるようになる。

- IP では、何ができて、何ができないかを他人に説明できるようになる。

- パケット交換ネットワークの基本的な特性を数理的に分析できるようになる。

テキスト

https://lsnl.jp/~ohsaki/lecture/netcomp/2024/priv/04.pdf

課題

課題 1

OSI 参照モデル (OSI reference model) を説明する以下の文について、 下記の問に答えよ。

A seven-layer structure designed to describe computer network [ ア ] and the way that data passes through them. This model was developed by the ISO in 1978 to clearly define the [ イ ] in multivendor networks, and to provide users of those networks with conceptual [ ウ ] in the construction of such networks. See also: International Organization for Standardization. (RFC 1392)

(1) 1 層〜7 層の名称を答えよ。

(2) 空欄 [ ア ]〜[ ウ ] にあてはまる最も適切な用語を以下から選べ。

Internet、 architectures、 documents、 guidelines、 interfaces、 protocols、 servers、 softwares、 specifications

課題 2

Internet Protocol (IP, IPv4) を説明する以下の文について、 下記の問いに答えよ。

The Internet Protocol (version 4), defined in RFC 791, is the network layer for the TCP/IP Protocol Suite. It is a connectionless, best-effort packet switching protocol. See also: packet switching, TCP/IP Protocol Suite, Internet Protocol Version 6. (RFC 1983)

(1) IPv4 が connectionless である理由を、その通信方式から説明せよ。

(2) IPv4 が best-effort である理由を、その通信方式から説明せよ。

課題 3

IP ネットワークはベストエフォート型であるため、 送信側ホストが送出したパケットが必ずしも宛先ホストに届くとは限らない。

IP ネットワークのみを用いて、 「送信側ホストが送出したパケットが宛先ホストに到着したか」を確実に知る方法はあるか。 あるならその方法を答えよ。 ないなら、 その理由を答えよ。

課題 4

パケット交換ネットワーク上で、 送信側ホストから宛先ホストまで単一のパケットを正常に転送するまでの時間の期待値 E[D] を求めたい。 ネットワーク中のパケット棄却率を p、 送信側ホストから宛先ホストまでの平均遅延を d [s] とする。 送信側ホストは、 パケット送出から T [s] 以内に宛先ホストからの ACK を受信しなければ同一パケットを再送するとする。

(1) k 回目のパケット送信で始めて宛先ホストにパケットが到着する確率 q_k を答えよ。

(2) E[D] を求めよ。

略解

課題 1

(1) 物理層、 データリンク層、 ネットワーク層、 トランスポート層、 セッション層、 プレゼンテーション層、 アプリケーション層

(2) ア: architectures、イ: interfaces、ウ: guidelines

課題 2

(1) IP の通信方式がパケット交換方式であるから。 宛先ホストと宛先ホストの間で事前にコネクションを確立することなく、 パケットを非同期でネットワーク中に送出するため。

(2) IP の通信方式がパケット交換方式であるから。 中継ノード (ルータ) は受信したパケットをバケツリレー形式で隣接するルータに中継する。 パケットはルータで待たされるかもしれないし、 廃棄されるかもしれないし、 バケツリレーによる中継が間違うかもしれないから。

課題 3

ない。

送信側ホストが、送出したパケットが宛先ホストに到着したかを知る

ことは

宛先ホストが、送信側ホストに対してパケットを受信できたかを伝える

ことと同じである (宛先ホスト→送信側ホストの逆方向の通信)。 順方向も逆方向もどちらも信頼性のない通信チャネルであるため、 「確実に知る」ことはできない。

※ なお、課題 4 のように、再送を繰り返すことによって情報伝送の成功確率 を上げることはできる (ただし、確率 1 にはできない)。

課題 4

(1) 過去 k - 1 回のパケット送信が失敗し、 次のパケット送信が成功する確率であるから

q_k = p^(k - 1) (1 - p)

(2) k 回目のパケット送信で始めて宛先ホストにパケットが到着した時の遅延時間 D_k は、 k - 1 回のタイムアウト時間 T [s] と、 送信側ホストから宛先ホストまでの片方向遅延 d [s] の和である。

D_k = (k - 1) T + d

したがって

         ∞
E[D] =   Σ   q_k D_k
        k = 1

          p
     = ------- T + d
        1 - p

類題

類題 1

なし

類題 2

以下は ChatGPT による「普通郵便」の説明です。

普通郵便とは、日本の郵便サービスにおいて最も一般的で基本的な郵便サービスのこ
とを指します。普通郵便は、特別な速達や追跡サービスがついていない通常の郵便物
の配送方法で、手紙やはがき、小包などを送る際に利用されます。配達速度は通常の
範囲内で、特に急ぎではない郵便物に適しています。料金も他のサービスに比べて比
較的安価で、日本全国に広く対応しています。

(1) 普通郵便が connectionless である理由を、その配送方式から説明せよ。

(2) 普通郵便が best-effort である理由を、その配送方式から説明せよ。

(略解) (1) ポストに投函された郵便物を収集し、宛先ポストに投函するという (あら かじめ配送経路を確保しない) 配送方式だから。(2) ポストに投函された郵便物を人手 で収集し、宛先ポストに人手で投函するという (郵便物の破損や紛失をゼロにはできな い) 配送方式だから。

類題 3

普通郵便はベストエフォート型であるため、 送信者が送出した郵便が必ずしも受取人に届くとは限らない。

普通郵便のみを用いて、 「送信者が送出した郵便が受取人に到着したか」を確実に知る方法はあるか。 あるならその方法を答えよ。 ないなら、 その理由を答えよ。

(略解) ない。受信人が、送信者に対して郵便を受信できたかを確実に伝えられないか ら。

類題 4

なし

ノート: Mathematica による数式処理

課題 4 の式は、 数式処理言語 (Mathematica) を使えば以下のように解ける。

ex.m:
(* Mathematica ではユーザ定義シンボルは小文字なので小文字を使用している *)
q[k_] := p^(k - 1) (1 - p)
d[k_] := (k - 1) t + d0
Sum[q[k] d[k], {k, 1, Infinity}] // FullSimplify

> WolframKernel <ex.m
Wolfram Language 13.0.1 Engine for Linux x86 (64-bit)
Copyright 1988-2024 Wolfram Research, Inc.

In[1]:=
In[2]:=
In[3]:=
In[4]:=
              p t
Out[4]= d0 - ------
             -1 + p

In[5]:=

レポート課題・質問・要望・コメント 2024/10/18

「レポート課題 2024/09/25」と同じ。

https://lsnl.jp/~ohsaki/lecture/netcomp/2024/#10-10

IP プロトコル (2)

授業の流れ・チーム分けの方針・態度目標

2024/09/25 のものと同じ。

https://lsnl.jp/~ohsaki/lecture/netcomp/2024/#10-1

内容目標

- IP パケットのヘッダフォーマットを理解し、IP パケットの 16 進ダンプから IP ヘッダの各フィールドの意味を読み取れるようになる。

- IP ヘッダのフォーマットから、IP プロトコルの仕様上の限界 (例: IP ヘッダの大きさ、ペイロードの大きさ) を理解できるようになる。

- データリンク層のフレームとネットワーク層のパケットの関係を理解し、ネットワークの伝送効率を計算できるようになる。

- 自身が使用している計算機の通信速度を計測できるようになり、計測結果からインターネットのボトルネックルータの状態を推測できるようになる。

テキスト (先週のものと同じ)

https://lsnl.jp/~ohsaki/lecture/netcomp/2024/priv/04.pdf

課題

課題 1

以下は IP パケットの 16 進ダンプである。 IP のバージョン、 ヘッダ長、 データグラム長、 ペイロード長、 プロトコルの種類を答えよ。

02:34:33.256082 IP dhcp39 > server-18-65-116-27.kix50.r.cloudfront.net: ICMP echo request, id 12850, seq 6, length 64
        0x0000:  4500 0054 8751 4000 4001 6c2c c0a8 0027
        0x0010:  1241 741b 0800 ce68 3232 0006 a940 4c63
        0x0020:  0000 0000 3fe8 0300 0000 0000 1011 1213
        0x0030:  1415 1617 1819 1a1b 1c1d 1e1f 2021 2223
        0x0040:  2425 2627 2829 2a2b 2c2d 2e2f 3031 3233
        0x0050:  3435 3637

IP ヘッダの詳細については RFC791 の 3.1. Internet Header Format を見よ。

RFC791: 3.1. Internet Header Format
https://www.rfc-editor.org/rfc/rfc791#section-3.1

課題 2

(1) IPv4 ヘッダの大きさは最小何オクテットか。理由もあわせて答えよ。

(2) IPv4 パケットのペイロードの大きさは最大何オクテットか。理由もあわせて答えよ。

課題 3

(1) 1500 オクテットのペイロードを持つイーサネットフレームに収容できる IPv4 パケットのペイロードの最大値を答えよ。

(2) この時の伝送効率 (リンクの通信容量のうちデータ転送に利用できる割合) を求めよ。

課題 4

(1) https://fast.com にアクセスし、 ダウンロード速度を計測せよ。

(2) 計測結果の「Show more info」をクリックし、 Unloaded および Loaded の遅延 (latency) を確認せよ。 これらの遅延の差から、 Loaded 状態において中継ルータのキュー長がどの程度増加したかを推測せよ。 なお、ボトルネックルータの帯域を 1 G [bit/s]、 イーサネットフレームの大きさを 1500 [byte] と仮定せよ。

略解

課題 1

IP のバージョンは第 1 オクテット (0x45) の上位 4 ビットであるから 4。

IHL (Internet Header Length) は第 1 オクテット (0x45) の下位 4 ビットであるから 5。 IHL の意味は

IHL:  4 bits
Internet Header Length is the length of the internet header in 32
bit words, and thus points to the beginning of the data.  Note that
the minimum value for a correct header is 5.

であるからヘッダ長は 5 × 32 ビット = 20 オクテット。

データグラム長は第 3 および第 4 オクテットの 0x0054 である。 ネットワークオーダ (ビッグエンディアン) であるから 0x0054 = 84 オクテット。

「ペイロード長 = データグラム長 - ヘッダ長」であるから 84 - 20 = 64 オクテット。

プロトコルの種類は第 10 オクテット (0x01) であるから 1。 なお、 プロトコル番号 1 は ICMP (Internet Control Message Protocol) である。

課題 2

(1) 20 オクテット。 Version から Destination Address までが必須で、 これらの合計が 20 オクテット。

(2) データグラム長は 16 ビットであるから最大値は 65,535 オクテット。 「最大ペイロード長 = 最大データグラム長 - 最小ヘッダ長」であるから、 最大ペイロード長は 65,535 - 20 = 65,515 オクテット。

※ IPv4 は 1970 年代に設計されたプロトコルであるため、 データグラム長はプロトコルの仕様により 64 KB に (プロトコル設計後 50 年以上経過した現代でも) 制限されている。

課題 3

(1) 「最大ペイロード長 = 1,500 オクテット - 最小ヘッダ長」であるから、 1500 - 20 = 1480 オクテット

(2) イーサネットフレームの大きさは 1500 + 22 (ヘッダ) + 4 (トレイラ) = 1526 オクテット。 したがって伝送効率は 1480 / 1526 = 約 0.97 であるから、 約 97 %。

※イーサネットの最大伝送効率は最大で約 98% であった (2024/9/25 課題 3)。 L2 にイーサネットを使った時の IPv4 の伝送効率は最大で約 97 % にとどまる。

課題 4

(1) 省略

(2) 例えば、 ダウンロード速度が 80 [Mbit/s]、 負荷なし (unloaded) の遅延が 10 [ms]、 負荷あり (loaded) の遅延が 40 [ms] であったとする。 従って、「負荷あり遅延 - 負荷なしの遅延」は 30 [ms] である。

ボトルネックルータの帯域 1 [Gbit/s] を、 packet/ms に単位換算すると

10^9 [bit/s] / 8 / 1500 [byte] / 1000 = 83.333 [packet/ms]

である。 つまり、 ルータは 1 [ms] 間に 83.333 パケットをキューから送出できることを意味する。

30 [ms] の遅延の増大に対応するキュー長の増大は

83.333 [packet/ms] * 30 [ms] = 2500 [packet]

である。

類題

類題 1

079-565-0123* という電話番号 (* は 0〜9 のいずれか) の、 市外局番、 所在地、 市内局番、 事業者名を答えよ。

市外局番や市内局番については以下の資料を参照せよ。

市外局番の一覧
https://www.soumu.go.jp/main_sosiki/joho_tsusin/top/tel_number/shigai_list.html

電気通信番号指定状況 (電気通信番号計画(令和元年総務省告示第6号)第1第4項による公表)
https://www.soumu.go.jp/main_sosiki/joho_tsusin/top/tel_number/number_shitei.html#kotei-denwa

(略解) 79565 の 5 桁が市外局番 + 市内局番である。 「電気通信番号指定状況→ 7 から始まる市外局番」の資料から、 079、 兵庫県三田市、 565、 西日本電信株式会社であることがわかる。

類題 2

(1) 1cm × 1cm の角材を使って外形が 20cm x 30cm の額を作りたい。 どれだけの長さの角材が最低でも必要か。 理由もあわせて答えよ。

(略解) 枠の厚みが 1cm だから、 20 * 2 + (30 - 1 - 1) * 2 = 96cm

(2) 額の中に収められる紙の面積は最大何 cm^2 か。 理由もあわせて答えよ。

(略解) 18cm x 28cm = 504 cm^2

類題 3

(1) 類題 2 (1) の額 (額 A と呼ぶ) の中に、 1cm × 1cm の角材を使って作ったもう一つの額 (額 B と呼ぶ) を収めたい。 額 B に収められる紙の面積は最大何 cm^2 か。

(略解) 16cm x 26cm = 416 cm^2

(2) この時の収納率 (額が占める面積のうち収められる紙の面積の割合) を求めよ。

(略解) 416 / (20 * 30) = 0.693333... だから約 69%。

類題 4

(1) なし

(2) 学生が相談のために VIII 号館の事務室に入ってから出るまでの時間を測定したところ、 最短で 5 分、 最長で 60 分であった。 事務室が込んでいる時に相談の学生が何人待っていたかを推測せよ。 なお、 学生一人あたりの相談時間を 5 分と仮定せよ。

(略解) 最長で 60 分、 最短で 5 分だから、 55 分増加している。 一人あたりの相談時間が 5 分だから、 55/5 = 11 人の待ちが発生していたと考えられる。

レポート課題・質問・要望・コメント 2024/10/25

「レポート課題 2024/09/25」と同じ。

https://lsnl.jp/~ohsaki/lecture/netcomp/2024/#10-10

前半の総復習

授業の流れ

1. 解説 (90 分)
2. リフレクションシート記入 (10 分)

態度目標

- 解説された内容を判的思考で分析し、できるだけ多くを吸収する。

- 脳が覚醒した状態のままでいる。

- クリッカーに記入する質問は、可能な限り、正しい日本語で具体的に記入する。

- 始めて知ったこと、なるほどと思ったことはノートに記録する。

内容目標

- 前半の「内容目標」すべてに到達できるようになる。

- 前半の内容に関連して、理解が不十分なもの、疑問が残っているもの、もっと知りたいものを言語化して質問できるようになる。

- 前半の内容に関連する疑問を一つでも多く解消できるようになる。

クリッカー

[授業中に使用] クリッカー (パスワードが必要です)
https://lsnl.jp/app/lecture/clicker/show/netcomp

質問への回答

- IWON構想について、ネットワークの専門家としてどのように感じていますか?

よく知りません (ので、何も感じていません)。

- 先生が作って、いつも使っているOS?の開発期間はどのくらいでしたか?

私が普段使っているすべてのものを合わせると膨大な時間 (数千時間?)  だと思いま
す。ゲーム好きな人に「ゲームに何時間使ってますか?」を聞くのと同じような感覚
だと思います。

- 1.大崎研究室はどのくらい忙しいのでしょうか? 2.就職活動に充てる時間を十分確保できますか? 3.過去に大崎研から院卒でどのような企業に就職されていますか?

以下のページを見てみてください。

ネットワークアーキテクチャ研究室 (大崎博之研究室)
https://rm.lsnl.jp/projects/public/wiki/

- ネットワークを取り扱う会社では入社直後の新入社員研修で主にどのようなことを学ぶのですか?

よくわかってません。が、会社や職種によってぜんぜん違うと思います。

- 領域実習で配属されていない研究室に、4回生時の研究室として選択しても良いのでしょうか。また、その場合は面談など必要になるのでしょうか

何の問題もありません。面談は (領域実習で配属された人も) 必須だと思ってください。

- ネットワークについて手元のPCで遊んで学ぶ方法はありますか?先生がやっていた勉強方法があれば伺いたいです。

上の質問にもあったように、(1) 自宅にサーバを立ち上げて、出先からリモートで使
えるようにする、(2) Wi-Fi の通信速度を最適化する、等が楽しいと思います。(1)
だと、最初は Nextcloud あたりをセットアップしてみるといいと思います。

Nextcloud
https://nextcloud.com/

- 大学院で研究したい内容が見つからない場合でも、大学院に行くべきだと思いますか?

「べき」ではありませんが、学部卒を選択する明確な理由がないのであれば院に行く
ことを勧めます。

- 授業の課題でも英語で書かれた文章をこの授業では多く見かけます。多くの専門用語が文章内に入っており、読むことに苦労しています。先生がこのような専門的分野の英語で書かれた文章を読む際に気を付けていることや学生時代に理解のために行っていたことがありましたらお聞きしたいです。

私は、「最初から英語で読めば早かったのに、日本語の資料を探してずいぶん時間と
労力を無駄にした」という経験を何度もしたので英語で読んでます。こういう経験を
早い段階ですることが重要かと思います。

- 先生の大学時代の後悔は何でしょうか。

特にありません (人間の脳は嫌なことを忘れるようにできています)。

- どこの研究室にいこうと思っているか迷っています。研究室を判断する際に何かアドバイスはありますか?

(1) この人たちと一緒に学びたい、と思える教員や先輩がいる研究室を選ぶと良いで
しょう、(2) 大学院から研究室を変えることもできることは覚えておきましょう。

- 授業後の自習では、授業時に課題を解く中で理解が深まっていないと思う問題について改めて自分で調べることで理解を深めようと取り組んでいたのですが、その他おすすめの自習方法があれば教えてほしいです。

それで良いと思います。後は、自身の知的好奇心の趣くまままに取り組めばよいと思
います。

- システムを作成する上でどのような手順で作成していきますか?ある程度仕様を考えてから作り出すのか、作りながら考えるのかなど。

最小構成のものを作って、それを段階的に複雑にします。例えば、電卓なら、「加算
しかできない電卓プログラム」をまず作ります。ウィンドウマネージャなら、「アク
ティブウィンドウの切り替えだけできるプログラム」をまず作ります。テキストエディ
タなら、「テキストの表示だけができるプログラム」をまず作ります。それを改良し
ていって複雑なプログラムにします。

- 1番通信速度が速いと思うスマホ会社はどこですか?

通信キャリアという意味ですね? 条件にもよりますが、具体的な条件を指定しないの
なら NTT ドコモだろうと思います。

- オクテットとバイトの表現の使い分けに注意しなければいけない状況とはありますか

他の質問への回答を見てください。

- インターネットに接続するホストの増加によって、IPv4ではアドレス空間が不足するため、IPv6に移行が進められていますが、授業ではIPv4を扱う理由は何でしょうか? また、関学図書館の電子書籍を閲覧する際に、学内アクセスと学外アクセスというものがありますが、この二つの違いは何でしょうか?

2024 年時点でも IPv4 のトラヒックのほうが多く、なおかつ IPv4 のほうが基本的
だからです。発信元の IP アドレスの違いです (有料の電子講読サービスの一部は発
信元の IP アドレスでアクセスの可否を判断しています)。

- 現在世界的によく使われているipのバージョンは何ですか?

2024 年の時点では IPv4 です。

Internet Society Pulse
https://pulse.internetsociety.org/en/technologies/

- 卒研配属の決定方法は領域の時と違うと思うのですが、先生はどのようなことを重視して選んでいますか

学生の希望と成績です (成績が優秀な学生を取りたい、という意味ではなく、良い成
績の学生の希望が優先されるべきと考えているからです)。

- OSIモデルにおいて、オペレーティングシステムは各層の通信やデータ処理にどのように関与し、具体的にどのような役割を果たしていますか?

OSI 参照モデルでは、OS はアプリケーション層のさらに上です。

- アクセスが集中するとサーバが落ちるのはなぜですか?

一般には、TSS (Time Sharing System) では、負荷が増大しすぎるとコンテキストス
イッチにほぼすべての資源を浪費する、という状態になってしまうからです。

- 論文を探すときに利用しているサイトを教えてください

Mendeley、IEEE Xplore、Google Scholar をよく使います。

- ボトルネックルーターが意図的に使用されるシナリオにはどのようなものがありますか?

どういう意味でしょう? ボトルネックになるのは結果です (ある時点で、一番遅いルー
タがボトルネックルータになります)。

- AIに関する知識や興味・見解はなにかありますか?

どういう意味でしょう? LLM には興味はあります。

- Cygwinで、あるファイルのパスのみを与えてEnterキーを押すと、シェルスクリプトや実行ファイルの実行が行われますが、なぜか、読み取り権限さえ与えていれば、実行権限を与えていなくても実行されてしまい、適当なバイナリファイルをシェルスクリプトと解釈して暴発することが度々あります。これを防ぐ方法はありますでしょうか?

仕様のようです。(他にもっと優れたものがあるので) Cygwin を使わないのが一番だと思います。

File permissions
https://cygwin.com/cygwin-ug-net/using-filemodes.html

- 何かを学ぶときに、いい本を見つける方法はなんですか?

基本的には経験が大事なのだと思います。図書館や書店に行って、実際に手に取って
パラパラとめくって、少しでも参考になりそうなら気軽に借りる/買う、というのを
ずっと続けることだと思います。

- 自主学習をしている中で、TCP/IPとOSI参照モデルの階層を対応付けて説明しているものを見つけましたが、この考え方は良いのでしょうか? それぞれの階層について名称が異なるため、正しいのか疑問に感じました。

どの文献かわかりませんが、そういう疑問を持つことは重要ですね。

- 自習を行う書籍を決定するとき、使用する書籍を決定する基準はどこにおいていますか?また、書籍の良し悪しを決定する基準として何に重点を置いていますか?

複数の本を読みます (基本的に絞りません)。「本を買うお金は惜しまない」と大学
生くらいの頃に決めました。他の質問への回答も見てみてください。

- 神戸三田キャンパスは理系キャンパスかと思いますが、すべての教室にコンセントがないのはなぜでしょうか?

それぞれ設計した人が必要/不要と考えたのだと思います。

10 年前ならコンセントが欲しいと思いますが、今なら省電力の PC とモバイルバッ
テリがあるのでコンセントがなくても特に困らないと思います。つまり、(1) ノート
PC が長時間駆動できるように設定を最適化しましょう、(2) どこでも戦えるように
モバイルバッテリを携帯しましょう。

- 深く学びたいと思える学問に出会ってから大学院に社会人で進学しようという考えから,現在は就職しようと思っているのですが,無理にでも学部から大学院にはいくべきでしょうか?

自分の人生なので、自分の信じる道を行けばよいと思います。が、「就職したが、そ
の後、深く学びたいと思える学問に出会うことはなかった」となる可能性が大きいよ
うな気がします。学部卒を選択する明確な理由がないのであれば院に行くことを勧め
ます。

- 授業ではパケット交換方式と回線交換方式を学びましたが、この2つ以外の方式で、現在用いられている方式はあるのでしょうか?もしあれば、どのような方式がありますか?実現されていないものの、理論だけが示されている方式はありますか?

どのレベルの話かによりますが、「パケット交換方式 vs. 回線交換方式」という文
脈なら、「パケット交換方式、回線交換方式、そのハイブリッドの方式」の 3 種類
のみです。

「○○方式」と呼ばれる通信方式は他にも無数にありますが、話のレベルや文脈が違
います。

- 自作でchat gptのような応答AIを作成するとしたら費用や時間はどのぐらいかかりますか?

「のような」の程度によります。stanford_alpaca のようなものでよければ、無料で
自分のノート PC 上で動かせます。ダウンロードして動かすだけなので、数十分程度
です (ダウンロードに時間がかかります)。

stanford_alpaca
https://github.com/tatsu-lab/stanford_alpaca

OpenAI の ChatGPT と同程度の規模のサービスを実現するなら、数十億円規模のコス
トと年単位の時間がかかると思います。

レポート課題・質問・要望・コメント 2024/10/30

なし

TCP プロトコル (1)

授業の流れ・チーム分けの方針・態度目標

2024/09/25 のものと同じ。

https://lsnl.jp/~ohsaki/lecture/netcomp/2024/#10-1

内容目標

- TCP のフロー制御の必要性とその影響を理解し、他人に説明できるようになる。

- TCP のウィンドウフロー制御 (スロースタートフェーズおよび輻輳回避フェーズ) におけるウィンドウサイズの変化を理解し、他人に説明できるようになる。

- ネットワーク中でのパケット棄却率と TCP パケット再送回数の関係を簡単なシミュレーション実験によって計測し、それらの関係を定量的に理解できるようになる。

テキスト

https://lsnl.jp/~ohsaki/lecture/netcomp/2024/priv/04.pdf

課題

課題 1

TCP の宛先ホストにおける受信バッファの空きが常に 32 [Kbyte] である時、 TCP フローの最大スループットはいくらか。 ただし、 TCP フローのラウンドトリップ時間を 10 [ms] とする。

課題 2

TCP の初期ウィンドウサイズを 1 [Kbyte] とする。 スロースタートフェーズにおいて、 ウィンドウサイズが 1 [Gbyte] (= 1024 * 1024 [Kbyte]) に達するまでに要する時間の最小値を求めよ。 ただし、 TCP のセグメント長を 1 [Kbyte]、 ラウンドトリップ時間を 100 [ms] とする。

課題 3

ウィンドウサイズが 100 [Kbyte] の TCP フローが、 輻輳回避フェーズにおいて、 ウィンドウサイズが 1 [Gbyte] (= 1024 * 1024 [Kbyte]) に達するまでに要する時間の最小値を求めよ。 ただし、 TCP のセグメント長を 1 [Kbyte]、 ラウンドトリップ時間を 100 [ms] とする。

課題 4

TCP の送信元ホスト〜宛先ホスト間のパケット損失率を p とする。 100,000 個の TCP パケットを送信元ホストから宛先ホストまで伝送する時に、 最大で何回の再送が起きるかを計測するシミュレーションプログラムを作成せよ。

p = 0.1 と p = 0.5 の場合にシミュレーションをそれぞれ 3 回実行し、 再送回数の平均を求めよ。

略解

課題 1

TCP フローのスループットが最大となるのは、 宛先ホストにおける受信バッファの空きによって律速される場合である。 この時のウィンドウサイズが 32 [Kbyte] であるから、 最大スループットは

32 [Kbyte]
---------- = 26214400 [bit/s] = 26.2 [Mbit/s]
 10 [ms]

である。

課題 2

ネットワーク中でパケット損失が起きない場合、 スロースタートフェーズにおいてウィンドウサイズは最も高速に増加する。

この場合、 1 ラウンドトリップ時間 (= 100 [ms]) 後に初期ウィンドウサイズの 2 倍の 2 [Kbyte] になり、 2 ラウンドトリップ時間 (= 200 [ms]) 後に初期ウィンドウサイズの 4 倍の 4 [Kbyte] になる。 したがって、 n ラウンド後のウィンドウサイズは 2^n * 1 [Kbyte] である。

ウィンドウサイズが 1024*1024 [Kbyte] を超えるのは、n が

2^n >= 1024*1024

となる時である。上記を満たす最小の n は n = 20 である。

従って、20 ラウンド後である

100 [ms] * 20 = 2 [s]

が要する時間の最小値である。

課題 3

ネットワーク中でパケット損失が起きない場合、 輻輳回避フェーズにおいてウィンドウサイズは最も高速に増加する。

この場合、 1 ラウンドトリップ時間 (= 100 [ms]) 後にウィンドウサイズは 1 [Kbyte] だけ増加し、 2 ラウンドトリップ時間 (= 200 [ms]) 後にウィンドウサイズは 2 [Kbyte] だけ増加する。 したがって、 n ラウンド後のウィンドウサイズは 100 + n [Kbyte] である。

ウィンドウサイズが 1024*1024 [Kbyte] を超えるのは、n が

100 + n >= 1024*1024

となる時である。上記を満たす最小の n は n = 1024*1024 - 100 = 1048476 である。

従って、1048476 ラウンド後である

100 [ms] * 1048476 = 104847600 [ms] = 29.12 [hour]

が要する時間の最小値である。

課題 4

100,000 個の TCP パケットのうち、 それぞれを確率 1 - p で伝送に成功したとみなし、 確率 p で伝送に失敗したとみなす。 上記の試行を、 100,000 個の TCP パケットの伝送がすべて完了するまで繰り返せばよい。

tcp-sim.py
https://lsnl.jp/~ohsaki/lecture/netcomp/2024/tcp-sim.py

p = 0.5 の実行結果 (の例):
> python3 tcp-sim.py
0 100000
1 49984
2 24968
3 12425
4 6304
5 3152
6 1577
7 790
8 400
9 195
10 93
11 49
12 18
13 9
14 5
15 5
16 3

3 回の試行:
> python3 tcp-sim.py | tail -1 | awk '{ print $1 }'
17
> python3 tcp-sim.py | tail -1 | awk '{ print $1 }'
14
> python3 tcp-sim.py | tail -1 | awk '{ print $1 }'
19

平均: (17 + 14 + 19) / 3 = 16.66 [回]

類題

類題 1

1 台の車を使って、 神戸三田キャンパスと三田駅をピストン輸送すると、 1 時間に何人を三田駅に送れるか。 ただし、 神戸三田キャンパスと三田駅の往復に 20 分かかり、 三田駅のロータリーでは (市の条例により) 一度に降車できる人数が 4 に制限されているとする。

(略解) 20 分に 4 名送れるので、1 時間だと 12 名。

類題 2

新聞紙の厚みを 0.1 mm とする。 1 秒間に 1 枚ずつ新聞紙を積んでゆくとき、 積んだ新聞紙の高さが 100 km になるまでに要する時間を求めよ。

※ 現実には不可能だが、ここでは積みあげることができると仮定せよ。

(略解) 100 [km] / 0.1[mm] = 1000000000 であるから、 1000000000 [s] = 約 31.7 年。

類題 3

新聞紙の厚みを 0.1 mm とする。 1 秒間に 1 回ずつ新聞紙を半分に折り畳んでゆくとき、 折り畳んだ新聞紙の厚みが 100 km になるまでに要する時間を求めよ。

※ 現実には不可能だが、ここでは折り畳むことができると仮定せよ。

(略解) 折り畳んだ回数を n とすると、その時の厚みは 0.1 [mm] * 2^n。 これが 100 km を超えるのは 30 回目であるから 30 秒。

類題 4

1 回 100 円のくじがあり、1/2 の確率で当たりがでる。 情報工学課程 2 年生の 100 名全員が、 それぞれ当たりがでるまでくじを買った時、 最も多く支払った人は何円になるか。 シミュレーション実験で求めよ。

レポート課題・質問・要望・コメント 2024/11/06

「レポート課題 2024/09/25」と同じ。

https://lsnl.jp/~ohsaki/lecture/netcomp/2024/#10-10

質問

- 大崎先生はどのような構成で VPN サーバーを構築しておられますか?

  講義中にコメントします。



TCP プロトコル (2)

授業の流れ・チーム分けの方針・態度目標

2024/09/25 のものと同じ。

https://lsnl.jp/~ohsaki/lecture/netcomp/2024/#10-1

内容目標

- TCP パケットのヘッダにどのような情報が記載されており、TCP の制御にどのように利用されているのかを理解し、他人に説明できるようになる。

- トランスポートプロトコルにおけるタイムアウト時間を決定することの困難さを理解し、適切なタイムアウト時間をどのように設定できるようになる。

- チェックサムによる誤り制御の原理を理解し、16 ビットのチェックサムによってどの程度のメッセージ破壊を見逃すかを定量的に理解できるようになる。

テキスト

https://lsnl.jp/~ohsaki/lecture/netcomp/2024/priv/04.pdf

課題

課題 1

ある IP アドレスを持つホストが同時に確立できる TCP フロー数の最大値はいくらか。

課題 2

TCP のコネクション確立が、 2-way ハンドシェイクでも、 4-way ハンドシェイクでもなく、 3-way ハンドシェイクであるのはなぜか。

Connection establishment, Transmission Control Protocol
https://en.wikipedia.org/wiki/Transmission_Control_Protocol#Connection_establishment

課題 3

ホスト X からホスト Y までのラウンドトリップ時間が、 平均 100 [ms]、 標準偏差 20 [ms] の正規分布で近似できると仮定する。 この時、 TCP の誤り制御におけるパケット損失の誤検出率を 2.5% 程度にするためには、 TCP 再送タイムアウト時間 (RTO) がどのような値であればよいか。

課題 4

TCP はヘッダおよびペイロードの誤り検出のために 16 ビットのチェックサムを使用している。 メッセージ長が 1,500 バイトで、 ビット誤り率が大きい時に、 16 ビットのチェックサムによってメッセージ破壊を見落す (メッセージが破壊されているにもかかわらず、 それを検出できない) 確率はいくらか。

略解

課題 1

TCP フローの終端は「IP アドレス; ポート番号」で区別される。 従って、 ある IP アドレスに対して、 ポート番号の種類だけ TCP フローを確立することができる。 ポート番号は 16 ビットであるから、 同時に確立できる TCP フロー数の最大値は 65,536 である。

RFC793: 3.1. Header Format
https://www.rfc-editor.org/rfc/rfc793

課題 2

TCP コネクションは全二重 (full-duplex) であるから、 2 方向のストリームの確立が必要となる。 各ストリームの確立に、 コネクション確立の要求 (SYN) と確認 (SYN ACK) の送信が必要となる。

従って、 2-way ハンドシェイクでは全二重のコネクション確立を実現できない。

2 方向のストリームに対して、 それぞれ個別にコネクション確立の要求 (SYN) と確認 (SYN ACK) を行う 4-way ハンドシェイクであれば全二重のコネクション確立は実現できる。

しかし、 4-way ハンドシェイクは、 3-way ハンドシェイクに比べるとコネクション確立の時間が大きくなる (往路・復路の通信遅延が等しければ 4/3 倍になる) ため、 TCP では 3-way ハンドシェイクが用いられている。

課題 3

ラウンドトリップ時間の確率変数を X、 パケット損失の誤検出率が 2.5% となる RTO の値を T と表記する。 この時、

P(X > T) = 0.025

となるように T を定めればよい。

正規分布 N(μ, σ ^2) では、 平均μの± 2 σに分布の約 95 % が収まることが知られている (68-95-99.7 rule)。

68-95-99.7 rule
https://en.wikipedia.org/wiki/68%E2%80%9395%E2%80%9399.7_rule

従って、

T = μ + 2 σ = 100 [ms] + 2 * 20 [ms] = 140 [ms]

と設定すればパケット損失の誤検出率が 2.5% 程度となる。

課題 4

チェックサムの大きさが 16 ビットであるため、 チェックサムで表現できる値の種類は 2^16 = 65,536 である。

ビット誤り率が大きい場合は、 破壊されたメッセージのチェックサムが、 元のメッセージのチェックサムと一致する確率は 1/2^16 = 0.0000153 である。

類題

類題 1

一人の人が、両手の指で表現できる情報は何通りか。ただし、それぞれの指を伸ばす/ 折り曲げるのどちらかしかできないとする。

(略解) 2^10 = 1,024 通り

類題 2

X さんと Y さんが自身の名前をそれぞれ確実に相手に伝えたい。X さんと Y さんで、 合計何回発話する必要があるか。

(略解) 3 回

X: 私の名前は太郎です。 Y: わかりました。私の名前は健太です。 X: わかりました。

類題 3

ヤフオクで、 これまで何度も取引きのある出品者からフィギュアを落札した。 この出品者は、 格安でフィギュアを出品してくれるのだが、 おっちょこちょいで発送作業を忘れることがある。 この出品者は、 (無事に発送された場合は) 落札から商品到着までの時間が平均 100 時間、 標準偏差 20 時間の正規分布で近似できることがわかっている。 発送済みにもかかわらず催促してしまう割合を 2.5% 程度にするためには、 落札からどれだけの時間を待ってから「発送いただいたでしょうか?」 と催促すればよいか。

(略解) 課題 3 の「秒」を「時間」に置き換えればよい。140 時間。

類題 4

一人の人が、 両手の指でチェックサム付きで情報を表現する。 8 本の指で 2^8 通りの情報を表し、 2 本の指をチェックサムに使うとする。

10 本の指で情報とチェックサムを表現した後、 いたずら好きの友人に指の曲げ伸ばしをあちこち変化させられた。 変化させられたことを、 2 本の指のチェックサムで検出できない確率はいくらか。

(略解) チェックサムの大きさが 2 ビットであるため、 チェックサムで表現できる値の種類は 2^2 = 4 である。

友人があちこちの指の曲げ伸ばしを変化させた場合は、 変化後の 8 本の指の情報のチェックサムが、 2 本の指のチェックサムと一致する確率であるから 1/4 である。

レポート課題・質問・要望・コメント 2024/11/13

「レポート課題 2024/09/25」と同じ。

https://lsnl.jp/~ohsaki/lecture/netcomp/2024/#10-10

インターネットの要素技術 (経路制御)

到達目標

- インターネットにおけるルーティングの仕組を、他人に説明できるようになる。

テキスト

https://lsnl.jp/~ohsaki/lecture/netcomp/2024/priv/05.pdf

課題

課題 1

下図のルーティングテーブルを持つルータに関して、以下の問いに答えよ。

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 アドレスを答えよ。

課題 2

ルータ a〜h で構成される以下のネットワークにおいて、 ディスタンスベクタ型のルーティングプロトコルを動作させた。

(1) すべてのルータが、 同時に、 一度だけ各隣接ルータと経路情報を交換した時の、 ルータ d のルーティングテーブル (各宛先ルータに対する次ホップと距離) を示せ。 ただし、 距離の定義はホップ数であるとする。

(2) (1) の直後に、 同時に、 もう一度各隣接ルータと経路情報を交換した時の、 ルータ d のルーティングテーブル (各宛先ルータに対する次ホップと距離) を示せ。

                +---+
           +----+ c +---+
           |    +---+   |
+---+    +-+-+        +-+-+     +---+
| a +----+ b +--------+ d +-----+ e |
+-+-+    +---+        +-+-+     +-+-+
  |                     |         |
  |  +---+              +-------+-+-+
  +--+ f +----------------------+ g |
     +-+-+                      +---+
       |
       |  +---+
       +--+ h |
          +---+

課題 3

課題 2 と同じネットワークにおいて、 リンクステート型のルーティングプロトコルを動作させた。 十分時間が経過した時の、 ルータ d のルーティングテーブル (各宛先ルータに対する次ホップとコスト) を示せ。 ただし、 各リンクのコストをすべて 1 とする。

課題 4

ネットワークのルータ数が N、 各ルータのインターフェース数の平均 (= 各ルータに接続されているリンク数の平均) を k とする。

(1) ネットワーク中の総リンク数 |E| を N および k を用いて表せ。

(2) このネットワークに対して Dijkstra 法を実行した時の最悪時間計算量を N および k を用いて表せ。

参考: Dijkstra's algorithm
https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

略解

課題 1

(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 がルーティングテーブル上のいずれのエントリにマッチしないから)

課題 2

(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

課題 3

十分時間が経過した後では、 各ルータ間の最短経路に基づくルーティングテーブルが作成される。

宛先ルータ | 次ホップ コスト
a         | b       2
b         | b       1
c         | c       1
e         | e       1
f         | g       2
g         | g       1
h         | g       3

課題 4

(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)

類題

類題 1

下図の案内がされている面接会場に関して、以下の問いに答えよ。

技術部 | 3F 1号室
人事部 | 4F 大会議室
経理部 | 4F 中会議室
その他 | 3F 2号室

(1) 面接会場の数はいくつか。

(2) 出身が工学部で、 技術部志望の学生の面接会場を答えよ。

(3) 出身が経済学部で、 知財部志望の学生の面接会場を答えよ。

(略解) (1) 4、3F 1 号室、3F 2号室

類題 2

お互いに名前を知らない 10 人の学生 a〜i が左から横一列に並んで座っている。 これらの学生が、 隣に座っている人にメモを渡すことで、 できるだけ多くの学生の名前をお互いに知りたい。

(1) すべての学生が、 同時に、 一度だけ隣に (左右にいれば左右それぞれに) 座っている学生にメモを渡した場合に、 学生 d の知ることができる学生の名前を示せ。

(2) (1) の直後に、 同時に、 もう一度隣に座っている学生にメモを渡した場合に、 学生 d の知ることができる学生の名前を示せ。

(略解) (1) c、e、(2) b、c、e、f

類題 3

類題 2 において、 隣に座っている学生にメモを渡す操作を繰り返し、 十分時間が経過した時を考える。 学生 d は、学生 a がどこに座っていると把握できるか。

(略解) 列の左端 (すべての学生が、学生 a〜i が左から横一列に並んで座っていることを知る (ことができる) から)

類題 4

1 クラスの生徒数が N、 各生徒の仲の良い友人の数の平均を k とする。

(1) このクラスで、仲の良い生徒同士のペアの組み合わせは何通りか。N および k を用いて表せ。

(2) 仲の良い生徒同士のペアで構成したネットワークに対して Dijkstra 法を実行した時の最悪時間計算量を N および k を用いて表せ。

参考: Dijkstra's algorithm
https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

(略解) 課題 4 の答と同じ

レポート課題・質問・要望・コメント 2024/11/20

「レポート課題 2024/09/25」と同じ。

https://lsnl.jp/~ohsaki/lecture/netcomp/2024/#10-10

要望

- Linuxの環境で、パワーポイントなどのOfficeのアプリケーションの編集をしたいときにどのようにして編集しているのか教えていただきたいです。

  基本的に、そういう特定のアプリケーションに固有のファイル形式を使用しません。
  どうしても編集が必要なら LibreOffice を使います。

  LibreOffice
  https://www.libreoffice.org/    



インターネットサービス (名前解決)

授業の流れ・チーム分けの方針・態度目標

2024/09/25 のものと同じ。

https://lsnl.jp/~ohsaki/lecture/netcomp/2024/#10-1

内容目標

- インターネットにおける名前解決の原理を、他人に説明できるようになる。

- DNS (Domain Name System) とは何かを、他人に説明できるようになる。

- DNS が TCP ではなく UDP を用いている理由を、定量的に説明できるようになる。

- nslookup コマンドを使って正引きおよび逆引きができるようになる。

課題

課題 1

DNS は Domain Name System の略である。 DNS の最後は S が、 サーバ (server) でもサービス (service) でもなく、 システム (system) である理由を論理的に説明せよ。

課題 2

すべてのホスト間において、 単一の IP データグラムの伝送時間が等しく 1 [ms] であるとする。 webmail.kwansei.ac.jp という名前を解決するまでに要する時間 D について、 以下の小問に答えよ。 ただし、 ネットワーク上のすべての DNS サーバが正常に稼働しており、 なおかつ、 すべてのホスト上で動作するソフトウェアの処理時間は無視できるほと小さいとする。

(1) D の最小値を答えよ。

(2) リゾルバが、 webmail.kwansei.ac.jp に対応するレコードを保持している最寄りの DNS サーバに問い合わせる時の D の値を答えよ。

(3) D の最大値を答えよ。

課題 3

DNS は名前解決に TCP ではなく UDP を用いる。 DNS が、もし UDP ではなく TCP を使っていたと仮定した時の、 課題 2 の (1)〜(3) に回答せよ。 ただし、DNS サーバへの問い合わせ時には毎回 TCP コネクションを確立するものとする。

課題 4

(1) webmail.kwansei.ac.jp に対応する IP アドレスを答えよ。

(2) www.kwansei.ac.jp に対応する IP アドレスを答えよ。

(3) 上の (1) と (2) で対応する IP アドレス数が異なるのはなぜか。

(4) 192.218.168.11 に対応する名前を答えよ (逆引きせよ)。

略解

課題 1

RFC 1034 より:
This RFC is an introduction to the Domain Name System (DNS), and omits
many details which can be found in a companion RFC, "Domain Names -
Implementation and Specification" [RFC-1035].  That RFC assumes that the
reader is familiar with the concepts discussed in this memo.

A subset of DNS functions and data types constitute an official
protocol.  The official protocol includes standard queries and their
responses and most of the Internet class data formats (e.g., host
addresses).

However, the domain system is intentionally extensible.  Researchers are
continuously proposing, implementing and experimenting with new data
types, query types, classes, functions, etc.  Thus while the components
of the official protocol are expected to stay essentially unchanged and
operate as a production service, experimental behavior should always be
expected in extensions beyond the official protocol.  Experimental or
obsolete features are clearly marked in these RFCs, and such information
should be used with caution.

DNS は、 名前を管理するシステム (name system) の名称であるので、 Domain Name *System* と呼ばれている。 DNS とは、 名前を解決するための、 分散型データベースシステムである。

一方、

RFC 1392 より:
Domain Name System (DNS)
   The DNS is a general purpose distributed, replicated, data query
   service.  The principal use is the lookup of host IP addresses
   based on host names.  The style of host names now used in the
   Internet is called "domain name", because they are the style of
   names used to look up anything in the DNS.  Some important domains
   are: .COM (commercial), .EDU (educational), .NET (network
   operations), .GOV (U.S. government), and .MIL (U.S. military).
   Most countries also have a domain.  For example, .US (United
   States), .UK (United Kingdom), .AU (Australia).  It is defined in
   STD 13, RFCs 1034 and 1035.  See also: Fully Qualified Domain
   Name.

のように、 名前を解決するためのサービスとも位置付けられているので、 Domain Name *Service* という名称でも良かったのかもしれない。 DNS の設計者は Domain Name *System* と名付けたが、 Domain Name *Service* という名前であったとしてもそれほどおかしくはなかったと思われる。

ただし、 Domain Name *Server* は、 「DNS に参加している / を構成する一つのサーバ」という英語になるのでおかしい。 Domain Name *Servers* であれば、 「システムを構成するサーバ群」という意味でありえた名前かもしれない。

課題 2

(1) リゾルバがキャッシュ済みの場合に最小となるから 0 [ms]。

(2) リゾルバから DNS サーバへの問い合わせ (query) に 1 [ms]、DNS サーバからリゾルバへの返答 (response) に 1 [ms] かかるため、合計で 2 [ms]。

(3) すべての DNS サーバがレコードをキャッシュしていない時に最も名前解決に時間がかかる。 この時、 a) リゾルバが最寄りの DNS サーバに問い合わせる、 b) 最寄りの DNS サーバがルートサーバに問い合わせる、 c) 最寄りの DNS サーバが jp ドメインを管理する DNS サーバに問い合わせる、 d) 最寄りの DNS サーバが ac.jp ドメインを管理する DNS サーバに問い合わせる、 e) 最寄りの DNS サーバが kwansei.ac.jp ドメインを管理する DNS サーバに問い合わせる、 という通信の流れになる。従って、

D = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 10 [ms]
    =====   =====   =====   =====   =====
      a)      b)      c)      d)      e)

である。

課題 3

(1) 0 [ms]

(2) 4 [ms]

TCP で名前解決を行う場合には、 問い合わせの前にコネクション確立が必要となる。 TCP の 3 ウェイハンドシェイクでは、 下図のように、 照会メッセージ (query) の前に a) SYN、 b) SYN + ACK、 c) ACK のやりとりが必要となる。 なお、c) ACK と d) query は連続して送出できる。 1 回の問い合わせに、 最低でも 2 往復の通信が必要となるので計 4 [ms] かかる。

問い合せ元      問い合わせ先
  |                  |
  |     a) SYN       |
  | ---------------> |
  |                  |
  |   b) SYN + ACK   |
  | <--------------  |
  |                  |
  |      c) ACK      |
  | ---------------> |
  |      d) query    |
  | ---------------> |
  |                  |
  |     e) response  |
  | <--------------- |
  |                  |

(3) 20 [ms]

課題 2 の略解 (3) における a)〜e) それぞれに TCP のコネクション確立が必要となる。 したがって、 課題 2 の (3) の 2 倍の通信時間がかかるため、 合計 20 [ms]。

課題 4

nslookup コマンドを使って調査すればよい。

実行結果の例:

(1)

> nslookup webmail.kwansei.ac.jp
Server:         106.187.2.33
Address:        106.187.2.33#53

Non-authoritative answer:
Name:   webmail.kwansei.ac.jp
Address: 192.218.168.202

(2)

> nslookup www.kwansei.ac.jp
Server:         106.187.2.33
Address:        106.187.2.33#53

Non-authoritative answer:
www.kwansei.ac.jp       canonical name = d277hm1gq2kzwt.cloudfront.net.
Name:   d277hm1gq2kzwt.cloudfront.net
Address: 54.230.130.73
Name:   d277hm1gq2kzwt.cloudfront.net
Address: 54.230.130.120
Name:   d277hm1gq2kzwt.cloudfront.net
Address: 54.230.130.38
Name:   d277hm1gq2kzwt.cloudfront.net
Address: 54.230.130.99

(3) www.kwansei.ac.jp は DNS ラウンドロビンによって (少なくとも) 4 台のサーバで負荷分散を行っているから。

(4)

> nslookup 192.218.168.11
11.168.218.192.in-addr.arpa     name = ns01.kwansei.ac.jp.

Authoritative answers can be found from:

類題

類題 1

任天堂のファミリーコンピュータの英語名は NES (Nintendo Entertainment System) である。 NES の最後の S が、 サーバ (server) でもサービス (service) でもなく、 システム (system) である理由を論理的に説明せよ。

(略解) NES 本体とテレビさえあれば、 一通りのものが揃うから system である。 NES は service を提供するものでもないし、 service を提供するものでもないから server でもない。

類題 2

ある会社 X では、 n 番目の職位の人は n + 1 番目の職位の人の名前だけを知っている。 例えば、 社長 A は副社長 B_1, ..., B_n の名前だけを知っており、 部長、 課長、 係長などの名前は知らない。 課長 D は、 同じ課に所属する係長 E_1, ..., E_m の名前だけを知っている。 職位は、 上から順に、 社長、 副社長、 部長、 課長、 係長とする。 このような会社において、 人事部人事課における採用担当の係長の名前を知るために要する質問回数を D とする。 以下の小問に答えよ。

(1) D の最小値を答えよ。

(2) 人事部人事課の課長に質問する時の D の値を答えよ。

(3) D の最大値を答えよ。

(略解) (1) 0 回 (もともと知っていた場合)、(2) 1 回 (人事部人事課の課長に聞けばすぐわかる)、(3) 4 回 (社長 → 副社長 → 部長 → 課長) と聞く場合)

類題 3

課題 2 において、質問する前に、質問してよいかどうかを確認する場合を考える。 例えば、課長に係長の名前を質問する場合は、

私: 「係長の名前は何ですか?」
課長 D: 「係長の名前は E_1, ..., E_m です。」

ではなく、

私: 「課長 D さん、係長の名前を教えてもらえますか?」
課長 D: 「いいですよ」
私: 「係長の名前は何ですか?」
課長 D: 「係長の名前は E_1, ..., E_m です。」

のように質問してよいかの質問が必要だとする。

このように仮定した時の、課題 2 の (1)〜(3) に回答せよ。

(略解) (1) 0 回、(2) 2 回、(3) 8 回 (質問数が 2 倍なので、質問回数も 2 倍になる)

類題 4

なし

レポート課題・質問・要望・コメント 2024/11/27

「レポート課題 2024/09/25」と同じ。

DHCP、ネットワークアドレス変換

授業の流れ・チーム分けの方針・態度目標

2024/09/25 のものと同じ。

https://lsnl.jp/~ohsaki/lecture/netcomp/2024/#10-1

内容目標

- DHCP (Dynamic Host Configuration Protocol) とは何かを他人に説明できるようになる。

- DHCP におけるメッセージ交換の手順を理解し、他人に説明できるようになる。

- NAT (Network Address Translation) とは何かを他人に説明できるようになる。

- 自身が使用している端末のネットワーク設定を調べられるようになる。

課題

Dynamic Host Configuration Protocol
https://en.wikipedia.org/wiki/Dynamic_Host_Configuration_Protocol

RFC 2131: Dynamic Host Configuration Protocol
https://datatracker.ietf.org/doc/html/rfc2131

Network address translation
https://en.wikipedia.org/wiki/Network_address_translation

課題 1

以下は DHCP クライアントとサーバ間のメッセージ交換の流れを表した図である (RFC 2131 より)。

(1) 空欄 [ a ]〜[ d ] に入るメッセージ名を答えよ。

           Server          Client          Server
       (not selected)                    (selected)

             v               v               v
             |               |               |
             |     Begins initialization     |
             |               |               |
             | _____________/|\____________  |
             |/   [  a  ]   |    [  a  ]    \|
             |               |               |
         Determines          |          Determines
        configuration        |         configuration
             |               |               |
             |\             |  ____________/ |
             | \________    | /  [  b  ]     |
             |  [  b  ] \   |/               |
             |           \  |                |
             |       Collects replies        |
             |             \|                |
             |     Selects configuration     |
             |               |               |
             | _____________/|\____________  |
             |/   [  c  ]    |    [  c  ]  \ |
             |               |               |
             |               |     Commits configuration
             |               |               |
             |               | _____________/|
             |               |/   [  d  ]    |
             |               |               |
             |    Initialization complete    |
             |               |               |
             .               .               .
             .               .               .
             |               |               |
             |      Graceful shutdown        |
             |               |               |
             |               |\ ____________ |
             |               | DHCPRELEASE  \|
             |               |               |
             |               |        Discards lease
             |               |               |
             v               v               v
Figure 3: Timeline diagram of messages exchanged between DHCP
          client and servers when allocating a new network address

(2) 図中において、 DHCP クライアントが割り当てられた IP アドレスを使用できるのはどの時点からどの時点までか。

課題 2

(1) 通常、 DHCP のメッセージ伝送にはユニキャストではななくブロードキャストが用いられる。 その理由を説明せよ。

(2) DHCP クライアントへの IP アドレス割り当てには、 DHCP クライアントとサーバ間で 2 回のメッセージ交換が行われる。 DHCPDISCOVER と DHCPOFFER の 1 回のメッセージ交換だけで DHCP クライアントに IP アドレスを割り当てるとどのような問題が生じるか。

課題 3

クライアントと、80 番ポートを使用する Web サーバの間で確立できる TCP コネクション数に関する以下の問に答えよ。 ただし、 すべてのホストは単一のインターフェースを有しているとする。

(1) クライアント X と Web サーバ Y の間で確立できる TCP コネクション数の最大値を答えよ。

(2) n 台のクライアント X1, ..., Xn を収容するプライベートネットワークが NAPT (Network Address and Port Translation) 対応ルータ R を介してインターネットに接続されている。 n 台のクライアントは均等に Web サーバ Y との間で複数の TCP コネクションを確立するとする。 この時、 クライアント Xi (1 <= i <= n) と Web サーバ Y の間で確立できる TCP コネクション数の最大値を n を用いて表せ。

課題 4

自身が使用している端末 (PC またはスマートフォン) について以下を調査せよ。

(1) IP アドレスと、そのアドレスクラス・アドレス種別 (グローバル/プライベート)・サブネットマスク

(2) デフォルトルータ (デフォルトゲートウェイ) の IP アドレス

(3) DNS サーバの IP アドレス

(4) DHCP サーバの IP アドレス

略解

課題 1

(1) a: DHCPDISCOVER、 b: DHCPOFFER、 c: DHCPREQUEST、 d: DHCPACK

(2) d: DHCPACK 受信から DHCPRELEASE の送出まで。

課題 2

(1) クライアントに IP アドレスが割り当てられるまではユニキャストで通信ができないため。

(2) DHCP サーバが複数存在する場合に、 DHCP クライアントは複数の DHCPOFFER を受信する。 この時に、 DHCP クライアントがどの IP アドレスを選択したのかがわからないため、 DHCP サーバは未使用の IP アドレスを割り当て済みと判断することになってしまう。

課題 3

TCP コネクションは、 4 つ組 (X_addr, X_port, Y_addr, Y_port) で区別される。 ここで、 X_addr および X_port はクライアント X の IP アドレスおよびポート番号である。 同様に、 Y_addr および Y_port は Web サーバ Y の IP アドレスおよびポート番号である。

(1) 65,536

X_addr、 Y_addr、 Y_port (80 番) は固定であるから、 X_port の種類数によって確立できる TCP コネクション数の上限が決まる。 TCP のポート番号は 16 ビットであるから 2^16。

(2) 65,536 / n

Web サーバ Y からは、 NAPT 対応ルータ R が TCP の終端に見える。 したがって、 n 台のクライアント X1, ..., Xn と Web サーバ Y の間で確立できる TCP コネクション数の最大値が 2^16。 今、 n 台のクライアントは均等に Web サーバ Y との間で複数の TCP コネクションを確立することから、 クライアント Xi (1 <= i <= n) と Web サーバ Y の間で確立できる TCP コネクション数の最大値は 65,536/ n。

課題 4

Linux 系オペレーティングシステムにおける実行例:

(1)

> ip addr
239: wlan0: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc noqueue state UP group default qlen 1000
    link/ether 2c:8d:b1:**:**:** ff:ff:ff:ff:ff:ff
    altname wlp0s20f3
    inet 192.168.0.37/24 brd 192.168.0.255 scope global dynamic wlan0
       valid_lft 170123sec preferred_lft 170123sec
      :
      :

IP アドレスは 192.168.0.37、サブネットマスクは /24 なので 255.255.255.0。 クラス C のプライベートアドレス。

(2)

> ip route
default via 192.168.0.1 dev wlan0 
192.168.0.0/24 dev wlan0 proto kernel scope link src 192.168.0.37 

デフォルトルータは 192.168.0.1。

(3)

DNS サーバはリゾルバの設定ファイルに書かれている。

> cat /etc/resolv.conf 
nameserver 106.187.2.33
nameserver 106.187.2.41

DNS サーバは 106.187.2.33 と 106.187.2.41。

(4)

DHCP サーバの情報は、 DHCP プロトコルを実行する DHCP クライアントソフトウェア (例: /usr/sbin/dhclient) が知っている。 dhclient は syslog(3) にアドレス取得時のログを記録している。

> journalctl | grep DHCP
    :
    :
Dec 06 14:08:50 **** dhclient[3737001]: DHCPDISCOVER on wlan0 to 255.255.255.255 port 67 interval 7
Dec 06 14:08:51 **** dhclient[3737001]: DHCPOFFER of 192.168.0.37 from 192.168.0.2
Dec 06 14:08:51 **** dhclient[3737001]: DHCPREQUEST for 192.168.0.37 on wlan0 to 255.255.255.255 port 67
Dec 06 14:08:51 **** dhclient[3737001]: DHCPACK of 192.168.0.37 from 192.168.0.2
Dec 06 14:08:51 **** dhclient[3737001]: bound to 192.168.0.37 -- renewal in 70311 seconds.
      :
      :

DHCP サーバは 192.168.0.2。

類題

類題 1

小学生である C さんは、 今日、 学校に「はさみ」を持ってくるのを忘れてしまった。 図工の時間に、 教室内の誰かから「はさみ」を借りたい。

C さんが、教室内の特定の人に対して話せず、 教室内の全員に対して話す (ブロードキャストする) ことしかできないとする。

この場合、「はさみ」を借りる手順は以下のようになる。

1. C さんが教室内で「はさみ」を貸してくれる人を探す (DISCOVER)
2. 教室内の誰か (複数かもしれない) が「はさみ」を貸してあげるよ、と提示する (OFFER)
3. C さんが提示してくれた中から S さんを選択し、S さんに「貸してください」と依頼する (REQUEST)
4. S さんは C さんに「はさみ」を貸してあげる (ACK)

(1) 省略

(2) 上記において、C さんが「はさみ」を使用できるのはどの時点からか。

(略解) 4. で「はさみ」を借りた時点

類題 2

(1) 省略

(2) 課題 1 の「はさみ」を借りるプロトコル (手順) では、 C さんと「はさみ」を貸す人の間で 2 回のメッセージ交換が行われる。 手順 1.と手順 2.の 1 回のメッセージ交換だけで C さんに「はさみ」を貸し出すとどのような問題が生じるか。

(略解) C さんは「はさみ」を一つしか使用しないのに、 複数の「はさみ」を同時に借りることになってしまう。

類題 3

なし

類題 4

なし

レポート課題・質問・要望・コメント 2024/12/04

「レポート課題 2024/09/21」と同じ。

HTTP

授業の流れ・チーム分けの方針・態度目標

2024/09/25 のものと同じ。

https://lsnl.jp/~ohsaki/lecture/netcomp/2024/#10-1

内容目標

- リゾルバが利用する hosts ファイルを利用することの利点および欠点を理解し、他人に説明できるようになる。

- アプリケーション層プロトコルである HTTP の仕組みを理解し、他人に説明できるようになる。

- HTTP/1.0 と HTTP/1.1 の違いを理解し、プロトコルの違いが通信性能に与える影響を定量的に理解できるようになる。

- Web ブラウザ等のソフトウェアを使用せず、Web サーバと HTTP プロトコルで対話できるようになる。

課題

資料

RFC 1945 Hypertext Transfer Protocol -- HTTP/1.0. T. Berners-Lee, R. Fielding, H. Frystyk. May 1996. https://www.rfc-editor.org/rfc/rfc1945

RFC 2616 Hypertext Transfer Protocol -- HTTP/1.1. R. Fielding, J. Gettys, J. Mogul, H. Frystyk, L. Masinter, P. Leach, T. Berners-Lee. June 1999. https://www.rfc-editor.org/rfc/rfc2616

HTTP の進化 https://developer.mozilla.org/ja/docs/Web/HTTP/Basics_of_HTTP/Evolution_of_HTTP

課題 1

通常、 リゾルバにおける名前解決では、 DNS よりもローカルの設定ファイルを優先する。 UNIX 系オペレーティングシステムでは /etc/hosts ファイルが、 Windows の場合は Windows/System32/drivers/etc/lmhosts ファイルが参照される。

頻繁に利用する Web サーバのホスト名と IP アドレスを、 オペレーティングシステムの hosts ファイルや lmhosts ファイルに記述しておくことの利点および欠点を説明せよ。

課題 2

HTTP/1.0 の GET リクエストを用いて、 Web サーバ上の 2 つのコンテンツ (/index.html と /logo.png) を取得する時にネットワーク中を転送されるパケット数 N の最小値 N_minはいくらか。 ただし、 2 つのコンテンツは十分に小さいものとする。

課題 3

HTTP/1.1 の GET リクエストを用いて、 Web サーバ上の 2 つのコンテンツ (/index.html と /logo.png) を取得する時にネットワーク中を転送されるパケット数 N の最小値 N_minはいくらか。 ただし、 2 つのコンテンツは十分に小さいものとする。

課題 4

Web ブラウザ等の HTTP プロトコルを解釈するソフトウェアを利用せずに、 http://google.co.jp/ を取得せよ。

略解

課題 1

利点: DNS による名前解決が不要となるため、初回のアクセスが高速となる。

欠点: サーバの IP アドレスが変化した時にアクセスできなくなる。

課題 2

HTTP/1.0 では、コンテンツの取得ごとに TCP コネクションを確立する。 このため、転送されるパケット数 N は

N = DNS による名前解決のために転送されるパケット数 N1
    + HTTP による /index.html の取得のために転送されるパケット数 N2
    + HTTP による /logo.png の取得のために転送されるパケット数 N3

で与えられる。

リゾルバがキャッシュしていた場合に N1 は最小値 0 を取る。

N2 と N3 はともに、以下の場合最小となるから N2 = N3 = 6。

クライアント      Web サーバ
  |                  |
  |      a) SYN      |
  | ---------------> |
  |                  |
  |   b) SYN + ACK   |
  | <--------------  |
  |                  |
  |      c) ACK      |
  | ---------------> |
  |                  |
  |  d) GET request  |
  | ---------------> |
  |                  |
  |  e) response+ACK | /index.html の転送
  | <--------------- |
  |                  |
  |      f) ACK      |
  | ---------------> |

したがって、転送されるパケット数の最小値 N_min = 0 + 6 + 6 = 12。

課題 3

HTTP/1.1 では、 単一の TCP コネクションを利用 (再利用) して、 複数コンテンツを取得できる。

単一の TCP コネクションで複数のコンテンツを取得した場合、 転送されるパケット数 N は、

N = DNS による名前解決のために転送されるパケット数 N1
    + HTTP による /index.html と /logo.png の取得のために転送されるパケット数 N2'

で与えられる。

リゾルバがキャッシュしていた場合に N1 は最小値 0 を取る。

N2' は以下の場合最小となるから N2' = 9。

クライアント      Web サーバ
  |                  |
  |      a) SYN      |
  | ---------------> |
  |                  |
  |   b) SYN + ACK   |
  | <--------------  |
  |                  |
  |      c) ACK      |
  | ---------------> |
  |                  |
  |  d) GET request  |
  | ---------------> |
  |                  |
  |  e) response+ACK | /index.html の転送
  | <--------------- |
  |                  |
  |      f) ACK      |
  | ---------------> |
  |                  |
  |  g) GET request  |
  | ---------------> |
  |                  |
  |  h) response+ACK | /logo.png の転送
  | <--------------- |
  |                  |
  |      i) ACK      |
  | ---------------> |

したがって、転送されるパケット数の最小値 N_min = 0 + 9 = 9。

課題 4

Web サーバ (google.co.jp) の 80 番ポートに対して TCP コネクションを確立し、 HTTP/1.0 の GET リクエストを送信すればよい。

> telnet google.co.jp 80
Trying 142.250.206.227...
Connected to google.co.jp.
Escape character is '^]'.
GET / HTTP/1.0                 ← ここは自分で入力
                               ← ここも自分で入力 (Enter を 2 回押す)
HTTP/1.0 200 OK                    
Date: Wed, 13 Dec 2024 02:10:41 GMT
Expires: -1                        
Cache-Control: private, max-age=0  
Content-Type: text/html; charset=ISO-8859-1
Content-Security-Policy-Report-Only: object-src 'none';base-uri 'self';script-src 'nonce-o2iUKfXDa-HUs6hhyu6HeA' 'strict-dynamic' 'report-sample' 'unsafe-eval' 'unsafe-inline' https: http:;report-uri https://csp.withgoogle.com/csp/gws/other-hp    
P3P: CP="This is not a P3P policy! See g.co/p3phelp for more info."
Server: gws                        
X-XSS-Protection: 0                
X-Frame-Options: SAMEORIGIN        
Set-Cookie: 1P_JAR=2024-12-13-02; expires=Fri, 12-Jan-2024 02:10:41 GMT; path=/; domain=.google.com; Secure                                  
Set-Cookie: AEC=Ackid1SYifYm8j3dMTzhAb4hyP6mIcMMILdgP1ZKJpN3Ol-3zoa1w3fjpA; expires=Mon, 10-Jun-2024 02:10:41 GMT; path=/; domain=.google.com; Secure; HttpOnly; SameSite=lax
Set-Cookie: NID=511=KkiZxX3u9TTDzWi5aN_8bY68Ts5Cb82xkdVhz6dOulVH9Rg1K6Rd7hJDhKL4yKexymTag_UQExiYrmrzCvjDBbmfMKWlwKQR7Wpv37y_QEDeWFmybi5x-ocFyAZwgRvuT9MxgwaUYxBRqI3st3KuZB71TD6C6sp4Vh2qW483BRo; expires=Thu, 13-Jun-2024 02:10:41 GMT; path=/; domain=.google.com; HttpOnly
Accept-Ranges: none                
Vary: Accept-Encoding              
                                   
<!doctype html><html itemscope="" itemtype="http://schema.org/WebPage" lang="ja"><head>...
   :
   :

レポート課題・質問・要望・コメント 2024/12/11

「レポート課題 2024/09/21」と同じ。

後半の総復習

授業の流れ

1. 解説 (90 分)
2. リフレクションシート記入 (10 分)

態度目標

- 解説された内容を判的思考で分析し、できるだけ多くを吸収する。

- 脳が覚醒した状態のままでいる。

- クリッカーに記入する質問は、可能な限り、正しい日本語で具体的に記入する。

- 始めて知ったこと、なるほどと思ったことはノートに記録する。

内容目標

- 後半の「内容目標」すべてに到達できるようになる。

- 後半の内容に関連して、理解が不十分なもの、疑問が残っているもの、もっと知りたいものを言語化して質問できるようになる。

- 後半の内容に関連する疑問を一つでも多く解消できるようになる。

レポート課題 2024/12/18

なし


Hiroyuki Ohsaki (ohsaki[atmark]lsnl.jp)