「ネットワークノート」の版間の差分

提供: IS2005 Wiki
移動: 案内検索
(ページの作成:「 == 第一回 Introduction == ==== 回線交換とパケット交換 ==== *回線交換 **電話のように仮想回路を設定 **大域は保障、Jitgterな...」)
 
852行目: 852行目:
 
*Gapが(一部)埋まったとき
 
*Gapが(一部)埋まったとき
 
**直ちにACKを送出
 
**直ちにACKを送出
*4回、同じACKを受信した送信側
+
*3回、同じACKを受信した送信側
 
**ssthresh = max(Flightsize/2,2*MSS)
 
**ssthresh = max(Flightsize/2,2*MSS)
 
**直ちに再送
 
**直ちに再送

2007年5月13日 (日) 12:05時点における版


目次

第一回 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分の1が正しいはずだが...)
  • 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を送出
  • 3回、同じ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