『コンピュータネットワーク第5版』5.1-5.4 学習メモ

（ノートから一部書き起こしたものです）

Ch05 network_layer

目的

network_layer: パケットを送信元から宛先に届ける役割
- data_link_layerは、一端から他端にフレームを送るのみ
- → network_layerがe2eの転送の最下層
- 送信元と宛先が異なったnetworkにいるときの対応

5.1 network_layerの設計課題

目的
- network_layerの設計課題を見る
- transport_layerのサービスやnetwork内部の設計課題も含む
内容
- 蓄積転送方式のパケット交換
  - ユーザの持つルータもISPのルータも同じアルゴリズムで動く
- transport_layerに提供するサービス
  - e2e argument → connection less型のnetwork_service
    - internet
    - hostがエラー制御やフロー制御をする
  - 通信事業者 → connection型サービス
  - IP vs MPLS(Multiple Protocol Label Switching), VLAN
    - connection less vs connection
  - この自由度は未決着
- connection less型サービスの実装
  - データグラム: 電報と類似したパケットの振る舞い
    - datagram network
  - ↑→ connection型 → VC(Virtual Circuit) network
  - routing algorithm
  - IPが代表例
- connection型サービスの実装
  - label switching: connectionの識別子の出力を変えて、重複回避
  - e.g. MPLS @ISP
- network内でのVCとDatagramの比較
  - VPNのように長期利用ではVCがとても有効

5.2 routing algorithm

目的
- 経路選択アルゴリズムと、アルゴリズムが使うデータ構造の設計が、network_layerの設計で重要
  - routing_algorithm
    - VPNでのsession routing by VC
  - forwardingとroutingの区別
  - algorithmが満たす性質: 正確性、単純性、対故障性、安定性、公平性、効率性
  - non adaptive algorithm: static routing or adaptive algorithm: dynamic routing
内容
- 最適化原理
  - sink treeの発見
  - DAG
- 最短経路routing
  - ルータを頂点、間の通信戦を辺として、networkを表すグラフを構築
- flooding
  - broadcastには効果的
  - ロバスト性とても高い
  - 性能評価の尺度。floodingは常に最適
- 距離ベクトルルーティング
  - dynamic routing_algorithm
  - routing tableのエントリを保持
  - 無限カウント問題
- link_state_routing ← 距離ベクトルルーティング
  - 5 steps
    - 隣接ルータに関する情報収集
      - 指名ルータをルータNの役割とする
    - link costの設定
    - link state packetの構築
    - link state packetの分配
    - 新しい経路の計算
  - e.g. (旧)多くのISPがIS-IS(Intermediate System-IS) Link State Protocolを使っている
  - e.g. (新)OSPF(Open Shortest Path First)
  - ルータの故障の損失の最小化が重要
- 階層化routing
  - ルータをリージョンに分割
  - 代償: 経路長が増大
  - N個のルータのネットワークにはlnNのレベルが〇 → 各ルータは合計elnN個のエントリを持つ
- broadcast_routing
  - multidestination routing
  - flooding〇
  - reverse path forwarding◎
    - 送信元への経路が最短のときだけすべてのLinkに送信
    - 容易な実装と効率〇
  - spanning treeの使用
- multicast routing
  - groupの生成と破棄が必要。ルータがどのグループのメンバか特定
    - routing以外のタスク
  - 密なグループと疎のグループの2パターン
  - spanning treeの枝刈り
    - MOSPF(Multicast OSPF) @Link State Protocol
    - DVMRP(Distance Vector Multicast Routing Protocol)
      - 再帰的に枝刈りメッセージを返送
  - Core-based trees
    - → treeの共有で、storage, message送信、計算量の大幅削減
    - PIM(Protocol Independent Multicast)の一部
- any cast routing
  - グループ内で最も近いメンバにパケットを送信
  - DNSで利用
- mobile hostに対するルーティング
  - home location or network_layerよりも上の層の可動性 e.g. skype
    - home agent
    - care-of(気付) addressの取得 @移動先のネットワーク利用前
    - tunneling: 重要。home agentが新しいヘッダでカプセル化 → 気付アドレスに送信
    - triangle routing
    - → 大規模なnetwork中で多くのルータの経路の再計算を回避
- ad hoc networkにおけるrouting
  - MANET(Mobile Ad hoc NETwork)
  - AODV(Ad hoc Ondemand Distance Vector)
    - 経路の探索と維持

5.3 輻輳制御アルゴリズム

目的
- congestion collapseの回避
- good put: 送信速度
- 帯域、リンクの送信速度のほかに、ルータのパケット処理速度も輻輳の原因になる
- congestion_control: 大域的問題、全ルータとホストが関係
- flow_control: 特定の送受信者間の問題
対応
- congestion_control手法
  - 緊急対策
    - provisioning(予防的)
    - traffic aware routing
    - admission control(流入制御)
    - load shedding(負荷遮断)
- traffic aware routing
  - routingが極めて不安定
  - → 流入量が緩やかに変化。routing protocolの外側から調整する: traffic engineering
- admission control
  - leaky bucketとtoken bucket
  - admission controlとtraffic aware routingの組み合わせ
- trafficの抑制
  - 輻輳回避
  - dnew = αdold + (1-α)s
    - α: EWMA(Exponentially Weighted Moving Average)
      - 過去の履歴を保持する期間 → 変動を平滑化
  - choke packet: 送信者へ返送
  - 明示的な輻輳通知(ECN: Explicit Congestion Notification)
    - 返送ではなく受信者に通知 → 送信者に返す
  - hopごとのchoke packet
- 負荷遮断
  - wine(古が〇)とmilk(新が〇)のポリシー
  - packetの重要性による判断
  - ランダム初期検知
    - RED(Random Early Detection): ルータで早めにパケットロスを発生
      - packet lossを検知 → transport_layerで送信速度を下げる
      - ECNの方が望ましい

5.4 QoS

目的
- over provisioning
- スループットのminとレイテンシのmaxを保証する必要
- 低コストでの実現
- QoSのための4つの課題
  - アプリケーションがネットワークに何を求めているか
  - ネットワークに流入するトラフィックをどのように制限するか
  - 性能保証のために、ルータのリソースをどのように予約するか
  - ネットワークが追加のトラフィックを安全に受け入れられるか
- → IntServ(Integrated Service)とDiffServ(Differentiated Service、差別化サービス)を見る
内容
- アプリケーションの要件
  - フローに要求されるQoS
    - jitter: 遅延やパケット到着時間の変化(標準偏差)
  - QoSの種類
- traffic shaping
  - バースト性とデータフローの平均レートを制限
  - 多様なトラフィックに対して、ネットワークのトラフィックパターンを単純かつ利用しやすい形式で記述する
  - ユーザとネットワークがフローのトラフィックパターンを合意
    - SLA: e.g. ある顧客のすべてのトラフィックなど、多数のフローと長い期間を対象にしたネットワークの取り決め
    - traffic policing ↓
  - → 音声や動画など、サービス品質に対する要求が高いリアルタイムデータの転送では極めて重要
  - leaky bucketとtoken bucket→トラフィックに特徴を持たせる
    - packetのshaping(@host OS), policing(@provider network interfaceのhardware)に使える
    - leaky bucket algorithm
    - token bucket algorithm
    - B + RS = MS → 許容可能なバースト継続時間を求める
    - token bucket algorithmにて、2つ目のtoken bucketを置き、R(tokenのたまる速度)を大幅に大きくする
    - → QoSの実現
- packet scheduling algorithm
  - ルータのリソースの割り当て
    - リソース: 帯域幅、バッファスペース、CPUサイクル
  - FIFO → QoSは低い
    - tail drop
  - RED
  - fair queueing
    - ≒ バイト単位のラウンドロビン
    - 必ずパケット単位の送信
    - 欠点: 全ホストが同一の優先度
      - → WFQ(Weighted FQ)
        
        Fi = max(Ai, Fi-1) + Li/W
        
        deficit(不足) round robin: packetごとにO(1)で済む
  - time stamp順のアルゴリズム
- 許諾制御
  - 厳密な保証。フローごとに互いに独立
  - QoS routing
  - flow spec: flowのparameterの集合
- 統合サービス: IntServ
  - a.c.a. flow-based algorithm → streaming multimediaのためのアーキテクチャ
  - RSVP(Resource reSerVation Protocol)
    - 複数送信者が複数受信グループにデータを送る
    - 受信者は自由にチャンネルを変えられ、同時に輻輳を排除
    - 帯域の予約が送信元の選択から分離
- 差別化サービス: DiffServ
  - class-basedのサービス品質: 単純 to IntServ
  - 管理ドメイン(ISPや地域の電話会社)を形成するルータの集合で形成
    - 対応する転送規則を備えたサービスクラスの集合を定義 by 管理者
    - PHB(Per Hop Behavior)
  - 優先転送(EF: Expedited Forwarding): 最も単純なクラス
  - 帯域保証転送(AF* Assured Forwarding)