ネットワークノート

第一回 Introduction

回線交換とパケット交換

• 回線交換
  • 電話のように仮想回路を設定
  • 大域は保障、Jitgterなし(少ない)　=　送ったタイミングで受信
  • 時分割交換も使用
  • 使用時間に応じた請求書
• パケット交換
  • データをパケット単位に分割
  • 各パケットは独立に配送　=　経路も独立
  • データにはヘッダを添付
    • 宛先や発信元を指定
    • その他の情報
  • データを送るときに回線を占有
  • 送ってないときには開放
    • 回線利用効率の向上
      • 安い料金に出来る可能性
  • 問題点
    • パケット送信において、確実に届けることが難しい
    • 大域の保障なし

相手の指定

• 計算機が二台の場合
  • 通信相手の指定は不要
    • 相手に送ればよい
  • 本当は識別が必要
    • 自分に送る場合もある
• 計算機が複数ある場合
  • 通信相手の識別が必要
  • 自分を識別する必要もある
  • 識別子の例
    • Social Security Number(社会保障番号)
    • Driver License Number(運転免許証)

名前、アドレス、経路

• 名前
  • 位置に独立な識別子
  • 移動しても変化しない
• アドレス
  • 相手が移動しても変化しない識別子
  • 自分が移動したら変化する可能性
• 経路
  • 自分と相手の相互関係に依存
  • 片方が移動すると変化する
  • 移動しなくても、ネットワークの状態によって変化する可能性も

プロトコル

• 計算機同士の取り決め
  • きちんと定義する必要あり
  • 双方で同じプロトコルをサポート
  • 仲介する媒体もサポート
• 様々な要素が関係
  • 時間、状態、出夏、エラー検出
  • 打切り、再送、割り込み、時刻
  • コネクタ、エラー通知、輻輳(ふくそう)通知

RS232C

• 調歩非同期
  • 図
  • 通信しないときには-15V
  • 通信の開始はStart Bit
  • 通信の終了はParity Bit
  • その後Stop Bit

プロトコル

• 実際の通信には様々な取り決めが必要
• 全部がうまく動いて初めて通信が可能
  • 全部を考えるのは面倒
  • 階層的な整理をすることで解決
• OSI基本参照モデル
  • 7層のモデル
  • 実装モデルではない
• 下記のサービスを上位のサービスが利用
  • 図を参照

種々のプロトコル軍

• TCP/IP
  • IPv4, IPv6, ICMP, TCP, UDP, SNMP, RIP, OSPF, BGP, SMTP, TELNET, FTP
• OSI : ISO規格
  • IP, TP4, CMIP, IS-IS, IDRP
  • インターネットでも使用
    • IS-IS, ASN-1
• AppleTalk : MAC
  • 16bitアドレス、ローカルな環境
  • Plug-and-Play
• IEEE : LAN規格
  • 46bit/64bit MACアドレス
• プロトコルが異なると、相互の通信は不可能
  • 通訳できる箱を経由

第二回 Ethernet

単位

• Bit
  • 二進数一桁分の情報量
• byte
  • 8bitのこと
  • 9bitの場合もある
  • 36bit計算機(ACOS)
• octet
  • 8bitのことをきっちり表現
• dBm
  • 電力の単位
    • 0dBm = 1mW, 20dBm = 100mW

Ethernet

• 1972-1976 3Mbps版がXeroxで開発
  • 原型はAloha/衛星を用いた通信プロトコル
  • Bob Metcaffe
• 1980 Degital, Intel, Xerox
  • 10Mbps版
  • 広く普及
  • DIX版とも呼ばれる
• IEEE802委員会
  • 802.3 Ethernet

規格の入手法

• RFC
• ID(Internet-Drafts)
• IEEE
• ITU-T

Ethernet

• 元々は同軸ケーブルを使用
  • 固有インピーダンス 50Ω
  • 両端を50Ωの純抵抗で終端
    • 反射波が発生しないように
• 同軸ケーブル
  • 外界との遮断(シールド)効果が高い
    • ノイズが入らない、出さない

構成

• 各局はトランシーバに接続
  • ケーブルを切断してNコネクタを半田付け
  • Vampire Tapで同軸ケーブルに「噛み付く」
    • 専用工具で穴を開け装着
  • 最小間隔は2.5
    • 2.5m間隔で印
  • ケーブル上に信号の送受信
• 同軸ケーブルは最大500m
• 最大100局
• 10Mbps: 1bitは100ns

bitの表現

• Manchester Coding
  • 図を参照
  • 0V 2.0Vの順にくれば1, 0V -2.0Vの順にくれば0
• Octetの表現
  • LSBからMSBへ送信 = リトルエンディアン
  • 図の例は01100
  • ただしFCSは例外

Ethernet Frame

• Ethernetのフレーム形式
  • Preamble:101010の繰り返し
    • 受信経路の同期を取る
  • SFD:Start Frame Delmiter{10101011}
  • Addressは6byte = 48bit

アルゴリズム

• 送信前に媒体をチェック
  • 他局が送信中なら終わるまで待つ
  • 96bit分間隔をあける(Inter Packet Gap)
• 送信中も媒体をチェック
  • 送信信号と受信信号の不一致
    • 衝突(collision)
  • 複数の局が同時に送信(同時に送信開始等) -> 衝突
    • フレーム送出を中止
    • Jam信号: 32bitのbit 1を送出

衝突時の挙動

• 同時送信
  • データの正しい伝送は不可能
  • しかし、Ethernetではさけられない
  • Jam signalを送出
  • サイド送信を試みる
• 衝突は事故ではない
  • 日常的に発生する
  • 送信データは廃棄せず、再送する
• Backoffアルゴリズム
  • 整数ウラン数(単位はslot time)だけ待つ
  • 0 <= r < 2^k
    • kは衝突回数
    • Binary Exponential Backoff
    • Backoffとは、待ち時間をどんどんと増やしていくというニュアンス
  • kの最大数は15

最低フレーム長

• 10Mbps Ethernet
  • 512bit: slot time
    • 64byte
    • Preambleを除く部分の最低長
    • Header + Data + FCS
  • Ethernetの端まで言って戻ってくる時間
    • slot timeより短くする
  • この条件で衝突を検出
  • Dataが短い場合にはpadding
• 最大フレーム長
  • Data部1500octet
  • 1518octet
    • preambleを除く

CSMA/CD

• Carrier Sense
  • 媒体を送信前にチェック
• Multiple Access
  • 複数が同時にアクセス
• Colision Detection
  • 衝突を回避

Ethernetの表記と変種

• 10Base5
  • 10Mbps
  • Baseband
  • 500m伸びる(概数)
• 10Base2
  • 細いケーブルで185mまで
  • BNC Tコネクタで直結
• 10Base-t
  • UTPとHubを使用
  • 100mまで
  • Twist Pairを使うのでT

Ethernetの変種

• 10Broad36
  • Broadband system
• 10Base-FL
  • 光ファイバー
• 100Base-TX
  • FastEthernet, UTP, 100m
• 100Base-FX
  • FastEthernet, 光ファイバー
• 1000Base-SX
  • GigabitEthernet
  • 光ファイバー, マルチモード, 850nm
• 1000Base-LX
  • GigabitEthernet
  • 光ファイバー, シングルモード, 1310nm
• 100Base-T
  • GigabitEthernet
  • UTP, 4対全部使用, 100m
• 10GBASE-SR
  • 10GigabitEthernet
  • マルチモードファイバー, 850nm, 26〜300m
• 10GBASE-LR
  • 10Gigabit Ethernet
  • シングルモードファイバー, 1310nm, 10km
• 10GBASE-ER
  • 10Gigabit
  • シングルモードファイバー, 1550nm 30〜40km
• 10GBASE-LW
  • C-192回線を使用, 9.6Gbps

第三回

Ethernet以外のデータリンク

• Token Ring/FDDI
  • リンク状にネットワークを構成
  • トークン(送信権)を巡回
  • トークンを持っている場合だけ送信可能
• Token Bus
  • トークンアルゴリズムを共有媒体で実現
• PPP : シリアル回線でのパケット転送
  • RFC1661, HDLC フレーム形式(RFC1662)
  • HDLC : 6bit連続1はflagのみ
    • zero-insertion/deletionで回避
• SONET
  • Syncronized Optical Network
  • 電話回線の構造化、オーバーヘッド
  • STS-1 : Frameを毎秒8000回
    • 90 * 9 *8000＝51。84Mbps
  • ただし、SPEは87 * 9 * 8000 = 50.112M
  • STS : Synchronous Transport Signal
• SONET : (ANSI)
  • STS-3 : STS-1を3つ octet interleave
    • 155.52Mbps / 150.336Mbps
  • STS-12 : 622.08Mbps / 601.344Mbps
  • STS-48 :
  • STS-192 :
  • OC-3/-12/-48/-192 : STS-nを光信号にしたもの
• SDH : Synchronous Digital Hierarchy (ITU-T)
  • STM : Synchronous Transport Module
    • n :1,4,16,64 (4分の１が正しいはずだが...)
• ATM : Asynchronous Transfer Mode
  • 「本当」は Layer-3 Protocol
    • でもInternetはATMをL2として使う
  • 53octetの固定長Cell
  • 回線交換
    • データ送出前に呼の確立が必要
  • VPI/VCI
    • データが所属している呼を指定
    • VC : Virtual Call
    • VP : Virtual Path(沢山のVCを束ねる)
  • SVC/PVC : switched/permanent virtual call

Ethernet アドレス

• 48bit MAC(Media Access control)アドレス
  • アドレスの表記 : 16進
  • 00:11:22:33:44:55 や 0011:2233:4455などの表記
• 通常はベンダが設定
  • ROMに個別にアドレスを焼きこむ
  • アドレスというよりもID
• 24bit単位で管理を分割

Ethernetの受信

• 各局は「全て」のフレームを受信
  • 自分宛のフレームを受理
  • ブロードキャストも受理
    • 宛先アドレス ff:ff:ff:ff:ff:ffは全員が聞かなくてはいけない
  • 必要なマルチキャストも受理
  • その他は廃棄
• 効率化のために
  • Ethernet i/f でこれらの処理
  • パケット受理の際に割り込み
• Primiscious mode
  • 全パケットを受理
  • アナライザやSecurity攻撃で使用

Ethernetの拡張

• 10Base5の場合
  • 500mを拡張したい
  • リピータの使用
    • Layer-1での転送
• マルチポートリピータ
  • Hubとも呼ばれる(スイッチとは違う)
• ループ不可(厳禁)
• リピータによる拡張
  • 波形の整形(時間軸、電圧)
  • 衝突は反対側に伝搬
  • 障害があるセグメントの分離
• 最小パケットで衝突が伝搬
  • リピータの最大数に制限
    • ケーブル中の伝搬遅延
    • リピータの伝搬遅延
  • "Cut Through"転送を可能
    • パケット全体を受信する前に転送開始

• リピータは
  • 衝突も転送
  • 拡張されたEthernetで一つの世界
• Collision Domain
  • 衝突が典範する領域
• リピータは
  • Collision Domainを拡張
• ブリッジは
  • Collision Domainを分割
  • ただし、Broadcastは単一Domain
    • ルータはBroadcast Domainを分割

Ethernetスイッチ

• 基本的にはBridge、ポート数は多い
• MACアドレスの学修
  • 不要なパケットの転送の抑制
  • 知らない宛先の場合は転送
  • マルチキャスト、ブロードキャストは転送
• 帯域の効率的な利用が可能
  • 1倍 - n倍, nはポート数

第七回

経路制御

• パケットをどの様にしてあて先に届けるか?
  • 最適な経路は?
  • Loopの発生をどう防ぐか?
  • ネットワークのトポロジヘの動的な対応
    • 収束が速い
  • Scaling
  • 大規模ネットワークに対応
• 176,499経路(2005/11/07時点)

• 他のサービスに依存してはならない
  • Bootstrap問題が発生
  • 隣接するノード間の接続性のみを使用
• 特定のノードに依存しない方式
  • 特定のノードがダウン
  • 特定のノードへのリンクがダウン
• 各ノードに設定する知識を最小限に
  • 分散的なアルゴリズムで経路の計算
• オーバーヘッドが小さいこと
  • 経路情報交換の帯域やメモリ
  • 計算に必要なCPUやメモリ
• IPは信頼性がない電送
  • 再送などは経路制御プロトコルで実施
• 経路制御の方式
  • Hop-by-hop
    • 宛て先アドレスに基づいて次段ルータを決定
    • 現在のインターネットで用いられている
  • Source Routing
    • 経路を発信元で決定
    • パケットに経路を明示
• 静的な経路制御
  • プロトコルは不要
  • ネットワークの規模と管理の手間
• 動的な経路制御
  • トポロジ変化に対応
    • ルータやリンクのダウン

経路計算の方式

• Distance Vector (Bellman-Ford)型
  • 逐次的な計算
  • RIP, RIP-2, RIPng
  • Path Vector 型
    • BGP-4, IDRP
    • 付帯情報でのループの回避、経路選択
• Link State (Shortest Path First)型
  • トポロジデータベースの同期
  • 各ノードでSPFの計算
  • OSPF, IS-IS

RIP

• Distance Vector 型の経路制御プロトコル
  • 元々は Xerox XNS のプロトコル
    • IP番は RFC1058 で定義
  • Metric: 1 -- 16
  • 経路情報の広告は30秒毎
  • 180秒更新されない情報はholddown
    • Metricを16に
  • さらに120秒更新されないと削除
• 基本
  • 採用した経路を隣接ノードに30秒毎に広告
    • Metricは1以上増やして
  • 具体的にどうなるのかは配布資料(11/30 P1 上の図)。

Count to infinity

• 非常に遅い収束の例
  • 配布資料(11/30 P1 下の図)

RIP収束の改善

• Split Holizon
  • 宛て先dの経路の方向にはdを広告しない
• Split Holizon with Poisoned Reverse
  • 宛て先dの経路の方向にはdをmetric=16で広告
• Triggered update
  • 経路の更新時には、30秒待たずに広告
• いずれにしても収束は速くない
  • 小さなネットワークに限定
  • Metric最大値(無限大)は16

RIPパケット

• 配布資料(11/30 P2 左上)
• コマンド
  • 1 : request
  • 2 : response あるいは30秒毎の広告
• バージョン : 1
• 25回まで必要なら繰りかえす
  • 最大512octet

演習

• 配布資料(11/30 P1 上の図)
• Sに対する経路はどうなるか
• Split Holizon を用いるとどうなるか
• Split Holizon with Poisoned Reverse を用いるとどうなるか
• Triggered update を用いるとどうなるか?

OSPF

• OOSPF : Open Shortest Path First
  • 公開されたLink-State型経路制御プロトコル
  • 現在はOSPF version 2 で RFC2328に規定
    • 244 page 447kB (plain textで)
    • 全部丁寧に説明すると大変
  • OSPF version 3 は IPv6用(RFC2740)
• インターネットではIS-ISも使われる
  • とくに U.S. の ISP では

Link State 型経路制御

• 基本は簡単
  • ネットワークのトポロジのデータベースを作成
  • 各ノードでSpanning Treeを計算して経路表を作成
• 実際にはそんなに簡単じゃない
  • データベースは各ノードでコピーを保持
  • データベースの同期をどう取るかが問題
    • 効率や同期の速度、設定
    • 収束に影響

OSPFの基本

• データベース
  • LSAの集合
    • LinkState Advertisement
  • Router LSA : Type-1
    • 各OSPF ルータが生成する
    • 接続されているネットワーク情報を記述
  • Network LSA : Type-2
    • 各ブロードキャストネットワーク...
    • ...
    • ...

第八回

OSPF

• 配布資料(11/30 P2 左、上から2番)
• マルチアクセスネットワークをノードにする
• Type-1 LSA の作成

SPF計算

• データベース
  • 基本的には Type-1 LSA と Type-2 LSA
  • SPFの計算
• R1の場合 :
• 配布資料(11/30 P2,P3)

第九回

OSPF データベースの同期

• Point-to-Pointリンクは簡単
  • お互いに同期を取る
  • 差分があったら送る
  • 受け取ったらACK
• ブロードキャストネットワーク
  • 相手を設定すれば、プロトコルは楽
  • O(n^2)の設定の手間が必要
    • overheadも大きい
  • 設定は最小限にしたい
    • 自動でルータを発見したい
  • Network LSAの設定は誰がするの?
    • 自動的に決めたい

前提

• 各ルータには名前をつける
  • Router ID
  • 32bitの値
    • IPv4アドレスを使ってもよい
    • OSPFv3でも32bit
    • あくまで識別子
  • 重複があると大変!
• 解決法: O(n)で済ませたい
  • 一台のルータを代表ルータとして選定
  • 他のルータは代表ルータとDBを同期
  • 代表ルータがNetwork LSAを生成

Hello Protocol

• ブロードキャストネットワークの場合
  • Hello Protocolを用いる
  • AIISPFRoutersにマルチキャスト
    • 224.0.0.5
    • Ethernetマルチキャスト
  • 定期的: たとえば10秒に一回
  • Helloを最近受信したルータのリストを添付
    • 通信の双方向性を確認
• パラメータ
  • Hello Interval
    • Helloの通信間隔
    • 例えば10秒
  • RouterDeadInterval
    • ルータがダウンしたと判定する時間
    • 例えば40秒
  • Priority
    • ルータがDRによる順位
  • パラメータは共通でなければならない
    • 異なったパラメータのHelloは無視

DRの選出

• DR: 指定ルータ
  • LAN内のルータデータベースの同期の責任
  • ネットワークに代わり、Network LSAを生成
  • 非常に重要
• Priorityが大きいルータがDRになる
  • Priority 0はDRには決してならない
  • 既にDRが決まっている場合にはそれに従う
    • Priorityの大きなルータに後で変更しない
  • Backup DRも決めておく
• ルータの関係
  • DR--その他のルータ: Adjustment
  • その他のルータ間: Neighbor

LSAの同期

• Adjustmentが確立した: Init
• Master/Slaveの確認: ExStart
  • Router IDが小さい方がMaster
  • 初期シーケンス番号も確認
• LSAタイトルの確認: Exchange
  • 必要なLSAをメモしておく
    • 不足しているもの
    • 自分の知っている方法がないもの
• 必要なLSAの交換:Loading
• LS Request / LS Update
• 同期が完了した: Full

LSAの更新

• マルチアクセスネットワークの場合
  • ルータ --> 指定ルータ --> その他のルータ
  • マルチキャストの利用
  • Ackが来ない場合
    • 陽に再送
    • この場合にはUnicast

NBMA

• NBMA: Non-Broadcast Multi-Access Network
  • ブロードキャストをサポートしていない網
    • ATM, Frame Relay, X 25
  • 指定ルータでは網状のルータを全部指定
    • 面倒だがやむを得ない
• その他はブロードキャストネットワークと同じ

実際のOSPF

• エリア
  • 経路ドメインをエリアに分割
  • バックボーンエリア
    • Area ID 0.0.0.0
  • その他のエリアはバックボーンに隣接
    • そうでない場合にはVisual Link
    • バックボーンを仮想的に拡張
  • エリア間では経路のサマリをやり取り
    • Type-3 LSA
    • SPFはエリア内部に限定
• 外部経路
  • ASBRに対する経路
    • Type-4 LSA
  • 外部経路
    • Type-5 LSA

距離ベクトル型とリンク状態型

• どちらがよいか、は簡単ではない
  • RIPが良くないのはまあ自明だけど
• 比較基準
  • 収束速度、メモリ、大域、計算量
• リンク状態型のほうがやや良いか
  • 更新されたLSAは直ちに送信
  • 経路計算はその後実施
  • 距離ベクトル型では計算後に送出

経路制御の階層

• 実際のインターネット
  • 共通のポリシで管理されている領域
    • Autonomous System (AS)
    • Routing Domainとも呼ぶ
  • ASが相互接続されてインターネットを形成
• リンクの維持にはコスト
  • 使っていい人といけない人を分離したい
    • 顧客は使っていい
    • 顧客の顧客も使っていい
  • -> ポリシルーティング

ポリシの例

• AS-1 <--> AS-2
  • AS-1 / AS-2 で費用を支出
  • 顧客関係にないAS-3の仕様不可
• 実現方法
  • Distance Vector Protocol
    • AS-1にはAS-3の経路を教えない
• 関係例
  • AS-1はAS-2の顧客
  • AS-2はAS-3の顧客
  • -> AS-1はAS-3 <--> AS-4を通ってよい
• 実装例
  • AS-3は(AS-1, AS-2, AS-3)の経路をAS-4に送出
• 問題点
• 解決法
  • 経路にAS情報を添付する
• 嬉しい点
  • AS単位での広告・受理・優先度制御が可能
  • AS情報でのループ検出も可能
• インターネットでは
  • AS: アドレス(経路)とは独立の番号
    • 16bit
    • レジストリによる割り当て・管理
• 経路制御の階層
  • IGP: AS内部での経路制御
    • Interior Gateway Protocol
  • EGP: AS相互間の経路制御
    • Exterior Gateway Protocol

BGP

• Border Gateway Protocol
  • RFC1771で定義
  • BGP version 4
• 現在は多くのRFCで機能追加
  • RFC2858 複数のプロトコルへの拡張
  • RFC2545 IPv6への拡張
• 経路情報の送受
  • TCPを使用
• BGPのモデル
• 経路と属性
  • 経路(の集合)に属性を添付
    • AS Path広告されてきたASのリスト
    • NextHop: 転送先のアドレス
    • MED: 複数のAS間のリンクを選択
• Abilene(AS11537)から見た経路の例

BGPの運用

• 16bit中およそ半分が割り当て済み

IPでの経路制御

• 経路はPrefixで表現
• アドレスとそのmask長
• 例:
  • 133.11.0.0/16
  • 157.82.33.32/27
• 同一経路が存在する場合
• Best Match(最長一致)を優先
• 例:
  • 133.11.0.0/16
  • 133.11.20.0/20
  • 133.11.21.128/25

IPでの経路表

• Best Match(最長一致)
  • 単純な表では探索効率が悪い
    • 最長一致でなくてもそうだけど
• 木構造の経路表を使用する場合が多い
  • Patricia Tree
    • BSD UNIXで使用
  • 縮退した二分木
    • TRIE
    • ハードウェアでの実現
    • 例: 日立 GR2000

Best Matchの問題

• Default routeとの関連
  • Default route: 0.0.0.0/0
    • 全ての宛先にmatch
• ループが発生する可能性
  • 解決策
    • R2で133.11.0.0/16を設定
    • Null0に133.11.0.0/16を設定
    • ->ICMP destination unreachable
• 経路表検索の複雑さ
  • 単純な表検索ではすまない
    • ハードウェアの実現が面倒
  • Trieを探索するハードウェアは既に稼動
    • 日立GR-2000
• Prefix Lengthの長い経路が優先される
  • 正当な/16と誤った/24
  • 経路表のhijackが可能

第十回

Acknowledgement

• TCPセグメントの受領確認
  • Ack#でどこまで受信したのかを示す
    • Ack#は次に受信するべきOctetのSEQ#
• Ackが来ない場合
  • データ(Ack)の損失の可能性
  • 単に遅れている可能性
• 正しくデータを送るためには
  • ある時間でタイムアウト
  • Ackされていないデータを再送
  • 再送のため、Ackされていないデータは保持
• Ack送出タイミング
  • Delayed Ack
    • ちょっとだけ待つ
    • 複数のセグメント到着に単一Ack

タイムアウト

• 問題 : いつタイムアウトするか
  • SRTT : Smoothed Round Trip Time
    • SRTT = α*SRTT + (1-α)*RTT
  • RTO : Retransmission TimeOut
    • RTO = min[UBOUND, max[LBOUND, β*SRTT]]
  • UBOUND : 上限、例えば1分
  • LBOUND : 加減、例えば1秒
  • α : Smooting factor(0.8 -- 0.9)
  • β : delay variance factor (1.3 -- 2.0)
• 初期値
  • 3way handshake時のRTTのβ倍を目安

TCPセッションの例

• 配布資料(12/21 上)

TCPの辛いところ

• 仮定しているネットワーク層
  • 信頼性がないサービス
  • パケット損失時の通知も無い
• 全てのTCPメッセージに損失の可能性
  • データは届いたがAckが失われた可能性
    • どちらが失われたか区別出来ない
• タイムアウトで再送するしかない
  • タイムアウトの設定が鍵
• Aggressiveな再送
  • 効率の低下
  • 公平性の観点から問題
• 環境の変化
  • 競合するトラフィックは動的に変化
  • 経路も変化する可能性

パケット損失

• パケット損失の発生
  • 回線上の残留エラー
    • ルータ等のバッファ上のbit化け
  • ルータ等でのバッファ問題
    • 入力queueのオーバフロー
    • カードからのバックプレーン等への帯域
    • スイッチング能力不足
    • 出力queueのオーバフロー
  • Ethernetのcollision
    • 10回連続したcollision
    • duplex mismatch : 誤設定

Silly Window Syndrome

• Windowがちょっと開く
  • ちょっとだけ送信できる
• これが繰り返されると
  • 小さなTCPセグメントが飛び交う
  • ネットワークの効率が低下
    • TCP/IPヘッダは40octet
    • ルータでのパケット単位の処理
• 対策
  • 送信側は、MSS分Windowが開くまで我慢
  • MSS:Maximum Segment Size

Karn's Algorithm

• TCPでのRTO
  • RTTの観測に基づく
    • リンクの負荷の変動
    • 経路が変わる可能性
• 再送したsegmentのRTT
  • 区別は困難
    • 最初のsegmentに対するACK
    • 再送したsegmentに対するACK
  • なので、SRTTの計算には組み入れない

再送

• 再送時には、同じデータを送る必要は無い
  • TCPはStream Protocol
    • Sequenced Packet Protocolではない
• 再送時に追加データがある場合
  • それを含めて送ってよい
    • 回線利用効率の向上
• Interactive sessionでは有効
  • 再送時に新しいデータがあるかも

Slow Start

• TCPセッション
  • ほかのTCP/UDP通信と帯域を共有(競合)
  • わがまま厳禁
    • 公平な帯域の利用が必要
• 過度な送信
  • 利用可能な帯域以上の送信
  • パケット損失
    • 過負荷によることが多い
• パケット損失 : 通信効率の低下
  • 同一内容を再送信 : 回線利用効率低下
  • タイムアウト待ち : TCPの性能低下
• 如何にパケット損失なしに高性能を得るか
  • 下から徐々に帯域の限界を攻める
• rwnd : 受信したwindowの最新値
• cwnd : Congestion Window
  • TCP初期化時には1MSSにセット
  • min(cwnd, rwnd)に基づいて送出
    • ある意味「自主規制」
• ssthresh : Slow Start Threshold
  • 初期化値は例えばrwnd
• cwnd < ssthresh
  • Slow Start
• cwnd > ssthresh
  • Congestion Avoidance
• Slow Start時
  • 重複の無いACK受信時
    • cwnd += MSS
• Congestion Avoidance時
  • 重複の無いACK受信時
    • cwnd += MSS * MSS / cwnd
    • 1RTT毎に += MSS
• タイムアウト時
  • ssthresh = max(Flightsize/2, 2*MSS)
    • Flight Size :未 ackの送信済みデータ量
  • cwnd = MSS
    • Slow Startをやり直し

Fast Retransmit/Fast Recovery

• Out of order セグメント受信時
  • 直ちにduplicate ACKを送出
• Gapが(一部)埋まったとき
  • 直ちにACKを送出
• 4回、同じACKを受信した送信側
  • ssthresh = max(Flightsize/2,2*MSS)
  • 直ちに再送
    • 再送タイムアウトを待たずに
  • cwnd = ssthresh + 3*MSS
  • さらに重複ACKを受信すると
    • cwnd += MSS
• 新規ACK受信時
  • cnwd = ssthresh

SACK

• Selective ACK : RFC2018
  • TCP Optionを使用
  • 通常は、連続ブロックの最後だけACK
  • SACKでは受信ブロックを明示
    • どこからどこまで、のリスト
  • SACKされていないデータを再送
• 使用に先立ちネゴ
  • SYNのみにSACK-permitted option
    • SACKを送ってもよい表明

Window Scaling

• Window size : 64k Octet
• RTTが大きい場合問題
  • 150ms : 3.5Mbps max
  • 300ms : 1.7Mbps max
• Window sizeを2^nに拡張 : RFC1323
  • 解釈のみを変更
  • windowフィールドは16bit
• SYN, SYN|ACKにWindow Scale option
  • シフトカウントnを明示
• 例
  • n=8 (256倍)
  • Window sizeは最大16MBに
  • 300ms : 420Mbps max

DNS

• ドメイン名空間
  • 機構増の階層型名前空間
  • "."を頂点
  • 配布資料(12/21 中段)に図
• 階層型の名前空間
  • 命名管理権限のdelegate
    • 集中管理する必要ない
    • Scaleする
• ラベル : 63文字以下、0-9, A-Z, -
  • 大文字小文字は区別しない
• ドメイン名 : ラベルを'.'で区切ったもの
  • 253文字以下
  • TLDを最後に
    • U.S.の住居表示の様に
• 名前の解決
  • 名前から各種情報を検索
    • 例 : IPアドレス

名前の解決

• 基本的には、木をRootから辿る
  • 答えを返す
  • 答えを知っていそうなサーバを紹介する
    • 配布資料(12/21 下段)に図。
• DNSサーバ
  • Recursiveサーバ
    • 問い合わせの最終回答を返す
  • Authoritativeサーバ
    • 自分が管理している情報のみを提供
    • 下位ドメインのDNSサーバへの参照も提供
  • Root DNSサーバ
    • 問い合わせの最初のサーバ
    • 全てのDNSサーバが知っている
    • root.cache