Microsoft PowerPoint - chapter5_2013.ppt [互換モード]

Size: px

Start display at page:

Download "Microsoft PowerPoint - chapter5_2013.ppt [互換モード]"

いぶきしげい
5 years ago
Views:

1 5 章メディアアクセス制御電子情報工学科 3 年前期ネットワークアーキテクチャ情報科学センター / ネットワークデザイン研究センター福田豊 Agenda データリンク層 (Layer2) メディアアクセス制御競合型 :CSMA, CSMA/CD 制御型 : トークンリング,FDDI 固定割当方式 :TDMA 要求割当方式 : トークンパッシングアプリケーション層トランスポート層インターネット層データリンク層物理層 TCP/IP protocol stack 5. はじめに例 :TDMA データリンク層の機能上位層に対して誤りのない伝送路を提供する伝送路の形態 :2 種類各ノード間が専用の伝送媒体で接続各ノードがつの伝送媒体を共有つの伝送媒体を複数のノード間で共有複数のユーザが伝送媒体を効率よく利用するための機構が必要ホスト数が増加すると, 伝送遅延は増加トラヒックは多くないが, ホスト数が大きい場合, TDMA は有効な方式ではなくなるメディアアクセス制御の議論メディア ( 通信媒体 ) を効率よく利用したい! メディアアクセス制御 2 3 例 2:LAN ネットワーク構成は簡明なものにしたいバス型, リング型, スター型高速な伝送媒体を共有メディアアクセス制御が必要 LAN: データリンク層に MAC (Medium Access Control) 副層を定義メディアアクセス制御方式 () 各ホストが伝送媒体に情報を正しく伝送するための方式ネットワーク資源である伝送媒体を効率よく利用するための機構が必要大別して2 種類制御型競合型 4 5

2 メディアアクセス制御方式 (2) 制御型 : 伝送する権利の割当てを制御固定割当方式 (fixed assignment scheme) TDMA 要求適用割当方式 (demand adaptive assignment scheme) トークンパッシングメディアアクセス制御 (3) 競合型 : 伝送要求が生じたホストがその要求に従って随時伝送を行う方式複数のホストが同時に伝送媒体を使用する伝送媒体で競合が発生パケットの衝突 (collision) により伝送が正しく行えない再競合が生じないよう衝突したパケットの再送 6 7 メディアアクセス制御 (4) 競合型 : メディアアクセス制御アロハ方式, スロット化アロハ方式 CSMA CSMA/CD 制御型 : 要求適応割当方式トークンリング FDDI 5.2 アロハ方式 970 年代ハワイ大学大学本部の中央コンピュータと, ハワイ諸島に分散している各施設との通信 ( 無線 ) のために開発端末中央コンピュータ間の通信回線を共用するために純アロハ方式 ( 競合型 ) を考案 8 9 純アロハ方式 () 伝送データが発生すると, すぐに伝送を開始パケットの長さは全端末で同じ大きさ他に通信があるかどうかは調べない複数のパケットの伝送が同時に行われる可能性がある衝突 (collision) が発生! 衝突が発生すると, ランダム時間後に再送バックオフ純アロハ方式 (2) 例 : 固定バックオフアルゴリズム中央コンピュータパケットを正しく受信した場合は,ACK を返す送信側パケット送信終了後最大往復伝搬遅延時間 2τ 経過しても ACK が戻ってこない場合, 衝突を検出その後, 固定間隔 (0, K](K: 定数 ) の間の整数値 r をランダムに決定し,r x T( パケットの伝送時間 ) 後に再送 0 2

3 純アロハ方式 (3) スループット S の導出ある時間の間に新たに発生するパケットおよび再送されるパケットを合計したものがポアソン分布に従うと仮定 T : パケットの伝送時間 ( 全端末で同一 ) : 時間 T 当りに伝送されるパケットの平均数 ( 伝送率 ) T ( : 単位時間当りの到着数 ) i ( T ) T P( N( T ) i) e (3.) i! よって k! k k ( T ) e (5.) P 区間 T の間に合計 k 個のパケットが伝送される確率 2 純アロハ方式 (4) スループットの導出 ( 続き ) パケットの伝送が成功 : 2T 時間内に他のパケットが伝送されないその確率 : P 0 (2T)=e -2 スループットSは, 伝送率と, パケットが衝突しない確率 P 0 (2T) との積 2 S e (5.2) 衝突が生じる期間 (2T) T t 3 スループット S 純アロハ方式 (5) アロハ方式のスループット特性スロット化アロハ方式純アロハ方式スループット S アロハ方式のスループット特性スロット化アロハ方式純アロハ方式 A B 0 総トラヒック量総トラヒック量 4 双安定性 : 競合型に共通する特性あるスループットを達成するが2 点存在一方は安定, 一方は不安定な状態に陥りやすい一時的に多くの衝突が発生すると不安定な状態に陥りやすい 5 スロット化アロハ方式 () パケットを伝送する時間を単位時間に区切る回線は仮想的にその長さの時間 ( スロット ) ごとに分割衝突が発生した場合固定バックオフアルゴリズム ( 一様分布に従ってランダムに決定 ) スロット化アロハ方式 (2) スループット S の導出スループット : パケットが正しく伝送される割合スロット化アロハ方式 :スロットにただつのパケットが伝送される確率 ( 衝突が起きない確率 ) 簡単化のため, 再送されるパケットもスループットも含むスロット当たり平均パケットのポアソン分布に従って発生するとすると, S e (5.3) 6 7 3

4 スロット化アロハ方式 (3) スループット S アロハ方式のスループット特性スロット化アロハ方式純アロハ方式総トラヒック量最大利用率は 2 倍に向上! 8 CSMA 方式 () CSMA : Carrier Sense Multiple Access 搬送波検知多重アクセス伝送する前に通信路上の搬送波を調査し, 通信路が空いていればパケットを伝送するアロハ : データを即時送信開始信号が行き渡るには伝播遅延時間が必要なため, 完全に衝突を回避することはできない最大伝搬遅延時間が重要になる 29 A B C CSMA 方式 (2) CSMA 方式における伝送例ネットワークの最大伝播遅延時間 τ T A τ パケット発生パケット発生端末 A の伝送開始時間を T A とすると, 端末 A のパケット伝送を他の端末が確認できるのは時刻 T A +τ 後端末 B は搬送波を検知し, パケットの伝送を見送る端末 C では時刻 (T A, T A +τ ) の間にパケットが発生通信路が開いていると認識し, パケットを伝送 τ が大きいシステム ( 衛星通信等 ) では, CSMA 方式は有効でない 30 CSMA 方式 (3) 搬送波を検出したときの動作により 3つに分類できる nonpersistent CSMA -persistent CSMA p-persistent CSMA 3 CSMA 方式 (4) nonpersistent 方式搬送波を検出すると, 衝突が起きた時と同じ動作をし, 再送アルゴリズムに従って搬送波を再び検知するまでの時間を決定 -persistent 方式搬送波を検出すると通信路が空くまで待ち, 空くと直ちにパケットを伝送する p-persistent 方式通信路が開いている ( 搬送波が検出されない ) 場合は確率 p でパケットを伝送し, 確率 -p で τ だけ待って再び搬送波を調べる搬送波が検出された場合は, 通信路が空くのを待って, 上記の動作を行う 32 CSMA 方式 (5) nonpersistent CSMA 方式の最大スループット解析 (S- 特性 ) 最大伝播遅延時間 :τ パケットの伝送に要する時間 :T 正規化伝播遅延時間 :a = τ/ T 例伝搬遅延時間 : 0 msec. 重要なパラメータ! パケット長が 0Kbit, 伝送速度が 0 Mb/s の場合, T = msec. a = 0 / = 0 パケットの伝送時間 Tの間に発生するパケットおよび再送されるパケットを合計した数がポアソン分布に従うものと仮定時間 T 当りに伝送されるパケットの平均数 ( 伝送率 ): 33 4

5 CSMA 方式 (6) 通信路の利用状況通信路上にパケットが伝送されている状態と, 何も伝送されていない状態が交互に現れるサイクル :サイクルに注目して解析パケット伝送稼動期間サイクルアイドル期間 34 CSMA 方式 (7) スループット S: 回線を有効に利用する割合 U S B I B : 稼動期間の平均長 I : 空きの期間の平均長 U : 伝送が成功した期間の平均長パケット伝送間隔 ( 指数分布 ) は無記憶性より I はパケットの平均伝送間隔に等しい I : 時間 T 当りに伝送されるパケットの平均数 ( 伝送率 ) 35 CSMA 方式 (8) パケットの伝送が成功するためには, その伝送開始から a の間に他のパケットが伝送されなければよいパケットの伝送時間はなので U e a ( P( N( T ) i) i! k Pk ( T ) e k! i T ) T e A B C D Y a CSMA 方式 (9) 稼動期間 B は期間 Y( あるパケットと衝突する最後のパケットが伝送されるまでの期間 ), パケットの伝送時間および伝播遅延時間 aの和 A a B B a Y C D Y CSMA 方式 (0) Y の確率分布 Y Prob e F ( y) Prob Y y a 0 ( a y) Y ydf Y a yの期間にパケットが伝送されない ( y ) a ( e したがって B 2 a ( e a ) a ) CSMA 方式 () S- 特性式 (nonpersistent CSMA 方式 ) a U e S a B I ( 2 a ) e lim S a 0 よって a=0 であれば理論的には = の時に最大スループット.0 が得られる正規化伝播遅延時間 :a = τ/ T

6 CSMA 方式 (2) nonpersistent CSMA 方式のスループット特性正規化伝播遅延時間 a に大きく依存 40 CSMA 方式 (3) -persistent CSMA 方式の最大スループット解析 (S- 特性 ) [ a ( a / 2 )] e S a ( 2 a ) ( e ) ( a ) e e ( ) lim S a 0 e a=0 の場合 : ( 2 a ) S はが無限に大きくなる e - に近づき, 最終的には nonpersistent CSMA 方式の場合とは異なり 0 になる ( a ) 4 CSMA 方式 (4) -persistent CSMA 方式のスループット特性例 : 正規化伝搬遅延時間伝送速度 (X): Mb/s パケット長 (L):0 Kbit T = L/X = 0 K/ M = 0 msec. 伝播遅延時間 :τ=0 msec. 正規化伝播遅延時間 :a = 0 / 0 = パケット長を 00Kbit とすると a = 0 / 00 = 0. a X L 正規化伝播遅延時間 a がスループットに影響 CSMA 方式 (5) 最大スループット特性 (a = 0.0) アクセス方式最大スループット純アロハ方式 0.84 スロット化アロハ方式 persistent CSMA 方式 nonpersistent CSMA 方式 persistent CSMA 方式 CSMA 方式 (6) 最大スループット特性搬送波検知機能の追加により,a が小さいときに特に性能向上 a が大きくなると, 方式による差がなくなる 45 6

7 イーサネット () 代表的な LAN(Local Area Network) WAN(Wide Area Network) 976 年 :XEROX 社のパロアルト研究所 978 年 :XEROX 社,Intel 社,DEC 社によって規格化 995 年 00Mb/s 802.3u 998 年 000Mb/s ( 光ファイバー ) 802.3z 999 年 000Mb/s ( ツイストペア ) 802.3ab 2002 年 0b/s ( 光ファイバー ) 802.3ae 2006 年 0b/s ( ツイストペア ) 802.3an 46 イーサネット (2) 仕様概要 : 物理層 0 BASE 00 BASE 伝送速度 0 Mb/s 00 Mb/s 端末間最大距離媒体 2.5 Km 同軸ケーブル UTP Category3, 5 ケーブル長最大 500 m( 同軸 ) 00 m (hub- 端末 ) UTP Category 5 最大 00 m (HUB- 端末 ) 47 イーサネット (3) 仕様概要 : データリンク層データリンク制御手順 CSMA/CD メッセージプロトコル可変長フレームイーサネット (4) 0BASE5/2 バス型セグメント (85/200) フレーム長最小 64~ 最大 58 oct * *:octet. 情報量の単位のひとつで octet は 8bit. ホストリピータ 3 つのセグメントを接続可能ホストイーサネット (5) 0BASE-T / 00BASE-T /000BASE-T スター型ホストブリッジイーサネット (6) 復習リピータ電気信号をそのまま伝えるブリッジコリジョンドメインに分割スイッチングハブ

8 フレーム構成イーサネットフレーム PreambleDA SA Type DATA FCS Preamble(64bit) フレームの開始を知らせる.と0が交互に現れ最後にが2つ続く DA(Destination Address)/SA(Source Address) 48bitからなるMACアドレス前半 24bitは各ベンダーごとにIEEEが割り当て Type or Length Ethernetでは上位レイヤの種類を示す 802.3ではDATAの長さをバイト単位で示す DATA 46 ~500バイト FCS(Frame Check Sequence) 32bitのCRC(DA~DATAまでを対象として計算 ) ビット誤りを検出するために用いるメディアアクセス方式 CSMA 方式を改良した CSMA/CD 方式 CSMA/CD : 衝突検出機能付 CSMA (CSMA with Collision detection) フレームを伝送中も通信路を監視伝送中のフレームが, 他のフレームと衝突していないかどうかを調査メディアアクセス方式 () 衝突を検出した場合速やかにフレームの伝送を中止し, 通信路の無駄な使用を省く伝送中止 A メディアアクセス方式 (2) 衝突の検出最悪の場合 : 最大往復伝播遅延時間 2τ 必要 CSMA/CD 方式 τが小さい比較的小規模のネットワークに適している LAN イーサネットでは-persistent CSMA/CD 方式を採用 B フレーム発生伝送中止メディアアクセス方式 (3) 衝突検出後衝突を他の端末に知らせるために数バイトのジャム信号を送信衝突したフレームが伝送される最大時間は 2τ 2τの最大値 :5.2μs よってフレーム長の最小値は 64oct (52bit) 52bit / 0 Mb/s = 5.2 μs これより小さいと, 衝突の検出の前に送信が終了してしまう 56 メディアアクセス方式 (4) 再送までの時間は? バックオフアルゴリズムで決定アロハ方式では固定バックオフアルゴリズムイーサネットではフレームの衝突回数に比例して再送期間の最大値 Xを動的に変化させる 2 進指数 (binary exponential) バックオフアルゴリズム衝突を繰り返すごとに最大値 X を2 倍 n 2 ( n 0) X (5.) 0 2 (0 n 5) 0 X を満足する整数 γがランダムに決定され,γx 2τ 後に再送. 衝突が6 回繰り返された場合は, 上位層で判断する 57 8

9 CSMA/CD 方式の性能 () CSMA/CD 方式のスループット特性 CSMA/CD 方式の性能 (2) CSMA/CD 方式の S- 特性 S e a a( e a a e ) 2a( e a ) (2e a γ: ジャム信号の長さ ) 正規化伝搬遅延時間が小さいほどスループットは高い CSMA/CD 方式の性能 (3) a=0.0 における他の方式との比較 CSMA/CD 方式の性能 (4) CSMA 方式と同様, 正規化伝播遅延時間が小さい場合高い最大スループット正規化伝播遅延時間が大きい場合最大スループット特性は劣化 a = 0. 約 60% 程度まで劣化ただし, 衝突検出機構により, 正規化伝播遅延時間が大きい場合でも最大スループットは改善 60 6 igabit Ethernet() コンピュータネットワークの普及 LANの高速化が必要 igabit Ethernet 規格名と最大ケーブル長 000BASE-T:00m 000BASE-SX:550m 000BASE-LX:5km 000BASE-CX:25m igabit Ethernet(2) 000BASE-SX/LX SX: マルチモード光ファイバ LX: マルチ / シングルモード光ファイバ 000BASE-T Category 5e UTPの8 本 4 対 ( 送信と受信共用 ) をすべて利用 00BASE-T では 2 対 4 本のみ使用

igabit Ethernet(3) 000BASE-T: 最小フレームサイズが問題 64 バイト (52bit) 0M 5.2μs 00M 5.2μs 000M 0.

μs と仮定 (00BASE-T では 0.25μs 以下 ) ケーブル長は往復で 20 数 m ほど 00BASE-T から移行できない!

ダミーのデータを足して, 最小のフレームを 52 バイト (4096bit) にし, 距離を伸ばす 00BASE-T と同じ 00 m の距離を確保 64 65

本でデータを送受信 igabit Ethernet(6) 使用する本数を増やして, 通信速度を向上 4 対 8 本すべて利用 000/4 = 250 Mb/s (

10 igabit Ethernet(3) 000BASE-T: 最小フレームサイズが問題 64 バイト (52bit) 0M 5.2μs 00M 5.2μs 000M 0.52μs UTP ケーブル上を流れる電気信号真空中の光の速さの約 7 割 ( 光速は 30 万 Km/sec) LAN アダプタ内部での信号処理遅延時間 0.μs と仮定 (00BASE-T では 0.25μs 以下 ) ケーブル長は往復で 20 数 m ほど 00BASE-T から移行できない! SW ハブが普及したとはいえ, 過去との互換性も重要 igabit Ethernet(4) 問題の解決策キャリアエクステンション最小 64 バイトでは足りないダミーのデータを足して, 最小のフレームを 52 バイト (4096bit) にし, 距離を伸ばす 00BASE-T と同じ 00 m の距離を確保最小フレームサイズの拡張 () 最小フレームサイズの拡張 (2) igabit Ethernet(5) 伝送周波数問題 00BASE-T では,2 対 4 本でデータを送受信 igabit Ethernet(6) 使用する本数を増やして, 通信速度を向上 4 対 8 本すべて利用 000/4 = 250 Mb/s ( 対当り ) 00BASE-T と比較して対あたりの処理速度は 2.5 倍で済むしかし, ケーブルを伝わる電気信号の周波数としては高すぎる 00m の距離を確保するためには周波数を下げる必要がある

11 igabit Ethernet(7) 符号化方式 8BQ4(000BASE-T) で対応送信データ送信するデータを 8bit ごとに区切るエラー検出用に bit 加えて 9bit に変換 2 の 9 乗 (0~5 の 52 通り ) bit bit 8bit 9bit データを 8bit 単位に区切るエラー検出用に bit 追加 9bit のデータに変換 70 igabit Ethernet(8) 9bit(52 通り ) のデータを 4 組の 5 値符号に割り当てる 5 値符号とは? つの符号に 5 つの値を持たせる 000BASE-T の場合 :+.0V, +0.5V, 0V, -0.5V, -.0V という 5 段階の電圧差により 5 値を表す 4 対の UTP で別々に 5 値符号を送信一度に送信できる情報量 : 4 対あるので 5 の 4 乗で 625 通りつの値を表す信号を 4 個同時に送信する通りの残りの部分は制御用等に利用 7 igabit Ethernet(9) bps を達成するためには度に送信できるのは 8bit 分 bps / 8 bit = 25 MHz カテゴリカテゴリ最大周波数主な用途カテゴリ5 00MHz 00BASE-T カテゴリ 5e 350MHz 000BASE-T カテゴリ 5 は規格自体が 00MHz までの帯域しか規定されていないため, 広帯域のデータ転送に不安カテゴリ 5e 登場最近はカテゴリ 5e が主流 72 igabit Ethernet(0) 4 対のケーブルを使ってデータを送信疑問データの受信はどうするのか? 00BASE-T: 送信と受信に別々のより対線を利用しているので, 全 2 重通信の実現は簡単 000BASE-T: 4 対あるより対線を全部利用して bps のデータを送信しているので, 送信と受信を別々のケーブルで行うわけにはいかない... ハイブリット回路 73 送信回路受信回路 igabit Ethernet() ハイブリット回路 4 対すべてのケーブルでデータを同時に送受信する送信する信号 ( 右向き ) と受信する信号 ( 左向き ) をそれぞれの方向にだけ流せるように工夫ハイブリットハイブリットハイブリットハイブリット igabit Ethernet(2) ハイブリッド回路の例固定電話本のより対線を使って, 音声の送受信を実現問題点 : エコーが発生する : 送信した信号が受信側回路に流れ込んでしまうノイズはNICに内蔵されたDSP (Digital Signal Processor) により除去 DSP: Intel486 と同程度の複雑さ ( 約 20 万トランジスタ ) UTP 74 75

インターネット，LAN，ネットワークに関する知識

インターネット，LAN，ネットワークに関する知識第 9 回インターネット,LAN, ネットワークに関する知識大学のキャンパス内にはネットワークが敷設されており, 教室, 図書館, 学生ラウンジなどで利用することができる LAN(Local Area Network) とは, 大学のネットワークなどのように, 比較的狭い範囲のネットワークを指すこれに対して,LAN 同士を結んで, 遠隔地とデーターを交換することを目的としたネットワークを WAN(Wide