Comments
Description
Transcript
2013.10.17(木1,2) コンピュータネットワーク 第2回
コンピュータネットワーク 2回目 物理層，データリンク層 佐藤 聡 [email protected] 2 物理層 物理層 3 理論的基礎 伝送媒体 電話交換網 まとめ 4 物理層 論理的基礎 複雑な波形 5 電圧や電源などの何らかの物理量を変化させる ことにより，電線上に情報を伝送することが可能． 物理量の値を時刻の一価関数 f(t) で表す． f(t)は複雑な波形となる． 複雑な波形は，振幅，周波数，位相の異なる波形 の重ね合わせで出来ている． 19世紀の初め フランスの数学者 フーリエ フーリエ解析 概念 6 引用： http://www.tdk.co.jp/techmag/knowledge/201002u/img/kl100202u.gif フーリエ解析(1/2) 7 周期 T のどんな周期関数 g(t) 1 g (t ) c an sin(2nft ) bn cos(2nft ) 2 n 1 n 1 f=1/T :基本周波数 an, bn : n番目の調和項の正弦振幅，余弦振幅 （フーリエ係数） c : 定数 フーリエ解析(2/2) 8 1 g (t ) c an sin(2nft ) bn cos(2nft ) 2 n 1 n 1 2 an T T 2 bn T T 2 c T T g (t ) sin(2nft )dt 0 g (t ) cos(2nft )dt 0 g (t )dt 0 フーリエ解析の例 9 ASCII文字 “b” 8ビット 出力例 ０１１０００１０ 1 an [cos(n / 4) cos(3n / 4) cos(6n / 4) cos(7n / 4)] n 1 bn [sin(3n / 4) sin(n / 4) sin(7n / 4) sin(6n / 4)] n c 3/ 4 信号の減衰 10 伝送設備において，異なるフーリエ成分が異なる 係数で減衰する → 信号に歪みが生じる． 通常，０から有る周波数までは減衰なく伝送され る． → この周波数の範囲を 帯域幅 という 帯域幅 は 媒体の構造，厚み，長さに依存する． 帯域幅とビット転送の関係 11 標本化定理 12 任意の信号の帯域をＨとする．このとき，毎秒2Ｈ 回だけ標本化すると，元の信号を完全に復元でき る． ナイキストの定理、ナイキスト・シャノンの定理、シャ ノン・染谷の定理とも呼ばれる。 提唱はナイキストだが、証明したのは、シャノンおよ び染谷 Ｈをナイキスト周波数，２Ｈをサンプリング周波数 と呼ばれる． 通信路の最高データ転送速度 13 標本化の定理によれば，雑音のない通信路では 最大データ転送速度＝2H log2Vビット/秒 (V: 信号を構成するレベルの数) 例） 雑音のない3KHzの通信路 2進信号(レベルが２) は最大6000ビット/秒 雑音のある通信路 14 信号対雑音比S/N (signal-to-noise ratio) を 考慮する必要がある． S/N の単位はデシベル(decibel)(dB) で 10log10S/N で表す． 例）S/N 比10は10dB，100は20dB，1000は30dB． 信号対雑音比 S/N の雑音がある通信路 最大ビット/秒 = H log2(1+S/N) 15 物理層 伝送媒体 伝送媒体 16 磁気媒体 磁気テープ，DVDなど 価格効率が高い より対線 同軸ケーブル 光ファイバ より対線 twistic pair 17 区分 Category Category Category Category Category Category 1 2 3 4 5 6 用途 電話線 ISDN 10Base-T トークンリング，ATM 100Base-TX 1000Base-T ,10GBaset-T 周波数 16MHzまで 100MHzまで 250MHzまで より対線 18 出典：IPA「教育用画像素材集サイト」 http://www2.edu.ipa.go.jp/gz/ 同軸ケーブル 19 広い帯域(1GHz)と優れた耐雑音性 出典：IPA「教育用画像素材集サイト」 http://www2.edu.ipa.go.jp/gz/ 光ファイバ 20 出典：IPA「教育用画像素材集サイト」 http://www2.edu.ipa.go.jp/gz/ 臨界角と全反射 21 絶対屈折率が大きいところから小さいところに光 が入る場合、αがある一定の角度(臨界角)以上だ と全反射する。 コアは絶対屈折率が大きく、クラッドは小さい 光ファイバの特性 22 コアとクラッドの境界で全反射を繰り返す → マルチモードファイバ ファイバの直径光の波長の数倍に等しいと，光は 直進し、遠くまで伝搬 → シングルモードファイバ 光ファイバの減衰 23 散乱，吸収 ファイバの不完全性，基本的構造による損失 ファイバの不純物が光エネルギーを吸収 減 衰 率 波長 ファイバの種類 24 シングルモードファイバ SMF 伝播モードが1つ 伝送損失が小さい 中長距離用 曲げに弱い 高価 波長 1.30μ/1.55μ コア 10μm以下 マルチモードファイバ ＭＭＦ 伝播モードが複数 短距離用 ファイバ同士の接続 が容易 比較的安価 波長 0.85μ/1.55μ コア 50μm,62.5μm SMFとMMFは替えが利くか? 25 発光源はコアが光を受け取る大きさにあわせて 光を出している（光軸） MMF用の光源から出す光はSMFには入りきらない SMFはMMFの代わりに使える もちろんモード分散ですぐ減衰すので短距離しか使 えない 急場しのぎに使用する 光ファイバネットワークの例 26 能動的リピータを有する光リングネットワーク 光電気変換 27 レーザーダイオード フォトダイオード 引用: http://jp.fujitsu.com/group/labs/techinfo/techguide/list/photonic-networks_p02.html 28 物理層 電話交換網 電話交換網 29 システムの構造 モデム ADSL 中継回線と多重 交換 電話回線を物理層として利用 30 電話回線は，もともと音声(アナログ信号）を送る ために発達した → 欠点 あらゆるところに張り巡らされている → 利点 帯域が制限されている(4kHz) デジタル回線としての利用 モデムを介して xDSL (Digital Subscriber Line) 電話システムの3つの主要要素 31 ローカル・ループ 中継回線 家庭や企業に至るアナログのより線 交換機を接続する光ファイバ 交換局 中継回線の間で，呼(call)を移動し，接続を行う 公衆電話網を用いた デジタルデータの伝送 32 変調 33 変調をする理由 データを伝送メディアに適した周波数に変換する． 変調の種類 デジタル変調 アナログ変調 アナログ変調 34 デジタル信号をアナログ信号に変換 周波数変調FSK(Frequency Shift Keying) デジタル符号に応じて周波数を離散的に変化 周波数の数が2倍になると送信できるビット数が1ビット増加 振幅変調 例:周波数を4つ用いる場合は2bit、8つなら3bit ASK(Amplitude Shift Keying) 振幅(電圧)を変化させる 位相変調 PSK(Phrase Shift Keying) 位相を変化させる アナログ変調を用いたモデム 35 デジタル信号 振幅変調 周波数変調 位相変調 モデムの速度を上げる 36 標本化速度を上げる 限界がある 標本あたり、より多くのビットを得る 位相を変化させる 4つの位相で2ビットを表す QPSK (Quadrature Phase Shiift Keying) 振幅と位相をともに変化させる QAM (Quadrature Amplitude Modulation) QAM （直交位相変調） 37 ASKとPSKの組み合わせ 例．8-QAM（2振幅、4位相） モデムの変調方式 38 配置パターン QPSK QAM-16 QAM-64 高速モデムの配置パターン 39 V.32 for 9600 bps. V32 bis for 14,400 bps. xDSL (Digital Subscriber Line) 40 モデムは速くならない 電話システムは、人間の音声を伝えるために最適化 されたもの 必ず、フィルタを通過する 加入者線を直接、フィルタを持たない別の交換機 に接続する ローカルループのすべての能力を利用できる 加入者線の距離による 伝送速度の変化 41 伝 送 速 度 距離 ADSL (Asymmetric DSL) 42 離散複数トーン変調を用いたADSLの動作 1.1MHzのローカルループ上のスペクトルを、 4kHzの256個の独立したチャネルに分解する。 それぞれのチャネルでは、V.34に似た変調方式 が用いられる。 典型的なADSL装置の構成 43 中継回線と多重化 44 周波数分割多重 波長分割多重 時分割多重 周波数分割 FDM 45 与えられた周波数帯を、より狭い複数の周波数帯 に分割し、それぞれをチャネルとして用いる。 波長分割多重 WDM 46 時分割多重 47 回線交換とパケット交換 48 49 物理層 まとめ ネットワーク設計における 物理層での考慮点 50 ネットワークを物理的に構成するメディアの性質 を知り、上位層の要求に応じてメディアを選択 メディアの持つ性質の切り分け 伝送遅延 信頼性(エラーレート、冗長性、稼働率) 帯域幅 コスト(インストールコスト、ランニングコスト) メディアを収容する機器による影響 51 データリンク層 データリンク層の役割 52 データグラムをノードか ら隣接ノードへリンクを 介して転送する リンク 通信パスに沿って隣接 ノードを接続する通信 チャネル フレーム データグラムをカプセ ル化 データリンク層 53 設計課題 誤り検知および訂正 基本的なデータリンクプロトコル スライディング・ウィンドウ・プロトコル 54 データリンク層 設計方針 設計方針 55 ネットワーク層に対して提供されるサービス 確認通知なしのコネクションレスサービス 確認通知つきのコネクションレスサービス 確認通知つきのコネクション指向サービス フレーミング(Flaming) フレームへの分割 エラー制御(Error Control) フロー制御(Flow Control) 確認通知なしコネクションレス 56 送信元はあて先に対して独立したフレームを送出 あて先では確認通知を返さない フレームが消失してもデータリンク層では回復は 試みない 誤り率が非常に低く、回復が上位で行われる場合 に適当 多くのＬＡＮでデータリンク層で使用 確認通知つきコネクションレス 57 各フレームは個々に確認通知される 送り手はフレームが正しく届いたかを確認可能 一定時間内に届かない場合にフレームを再送 信頼性の低いチャネルで有効 無線システム 確認通知つきコネクション指向 58 送信元と受信先で通信の前にコネクションを確立 データリンク層がさまざまな保証を行う 各フレームが受信された 各フレームは1度だけ受信されている フレームは正しい順序で受信される 信頼できるビットストリームを提供 ネットワーク層に対するサービス 59 仮想的な通信 実際の通信 データリンクプロトコルの機能 60 ルータ データリ ンク層 プロセス フレーム ルーティング プロセス データリンク プロトコル パケット ルータへの 転送路 誤り検知と誤り訂正 61 データリンク層は物理層からビットストリーム（0と 1の並び）を受け取る． 誤りの可能性あり 誤りの検知と訂正が必要 ビットストリームを細かく分割する フレーム化 フレーム単位で誤りをチェック フレーム化 62 文字数 フラグ・バイト（バイト詰めを伴う） 同じバイトを、開始の区切りと終了の区切りの両方に 用いる フラグ・バイトと同じビットパターンが現れた場合は、 エスケープ・バイト(ESC)を挿入 開始および終了フラグとビット詰め 文字数によるフレーム化 63 ヘッダー中のフィールドにフレーム中の文字数を示す方法 エラーなし エラーあり エラーがあった場合，次のフレームの始まりがわからない． フラグ・バイト 64 フレームが特別なバイトで始まり，特別なバイトで終わる． バイト（8ビット）を用いることに強く結びついている． ビット詰め(bit stuffing) 65 特別なビット列で始まり，終わる． 例） ０１１１１１１０ → 1が5つ並ぶと0を入れる ※データ中に1が6つ並ぶことがない． →フレームの最初がわかる 66 データリンク層 誤り検知と訂正 誤り検出と訂正 67 誤り訂正コード(Error-Correcting Codes) 誤る確率が高い場合 誤り検出コード(Error-Detecting Codes) 誤る確率が低い場合 再送する 符号語 68 送信側から送る長さnの記号を符号語 (codeword)という データm n=m+r ビット： 冗長ビット（パリティ） rビット 冗長ビットがrであるので、冗長データの数は全部 で2r個になる 長さnの系列の総数は2nであるので、冗長データ としてその一部を使うことになる 69 ハミング距離 (Hamming Distance) 2つの符号語を比較した時に、異なっているビット の数 10001001 10110001 00111000 排他的論理和(EOR)をとり、1の数を数える ハミング距離がdならば、一方を他方にするため に、d個の1ビット誤りが必要 誤り検出の簡単な例 70 パリティ・ビット(parity bit) 符号語の中の、1のビットの数が、偶数または奇数に なるように、誤りビットを付け加える 1011010 偶数パリティ→ 10110100 奇数パリティ→ 10110101 単一誤りを検出できる 誤っていることだけしかわからない 誤り訂正か検出か 71 多くの場合は検出＋再送の方が効率が良い 孤立的な誤りが10-6のチャネル（仮定） 1000ビットの誤り訂正は10ビット必要 1Mビットのデータに対して、1000X10= 要 10000ビット必 単一ビット誤りの検出ならブロックごとに1ビット 1000ブロックに一度再送（1001ビット） オーバーヘッド(2001ビット） 誤り検出のためのチェックビット(1000ビット） 再送のためのビット(1001ビット） 誤り訂正 ハミング符号 72 1ビットの誤りを訂正できる符号 仮定 m r メッセージm ビット チェックビットr ビット 全ビット数n = m＋r ビット 4 3 5 4 8 4 16 5 条件（必要なチェックビット数） 32 6 (n+1)・2m ≦ 2n (m + r + 1) ≦ 2r ハミング符号の生成（１） 73 mビットのメッセージに、r個のチェックビットを、2 のべき乗の位置に加える(m+r ビット） 左側が位の低いものとする（通常と逆） 左から、k番目のビットに対して、kを２のべき乗の 和として表す。 11 = 1+2+8 = 20+21+23 <1011>2進数 各kビットに対応する、チェックビットを洗い出して 表を作成する。 ハミング符号の生成（２） 74 H1 H2 M1 H4 M2 H3 M4 k 1 2 3 4 5 6 7 H1 ○ H2 H3 ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ 各チェックビットは、関係する、メッセージビットの偶数または奇数パリティ H1 ⊕ M1 ⊕ M2 ⊕ M4 = 0 → H1 = M1 ⊕ M2 ⊕ M4 偶数 H2 ⊕ M1 ⊕ M3 ⊕ M4 = 0 → H2 = M1 ⊕ M3 ⊕ M4 パリティ H4 ⊕ M2 ⊕ M3 ⊕ M4 = 0 → H4 = M2 ⊕ M3 ⊕ M4 のとき バースト誤りへの対処 75 単一のパリティビットだけではバースト誤りに対応 できない ブロックを長方行列として列ごとにパリティを計算 し行ごとに送信 ハミング符号の場合とよく似た対応策 実際は多項式符号が良く用いられる 多項式符号(CRC) 76 ビット列を係数が0か1の多項式の表現と見る kビットのフレームはk-1次の多項式 110001ならx5+x4+x0 演算は2の剰余系 加算や減算は排他的論理和と同一 あらかじめ生成多項式を決定しておく 最上位ビットと最下位ビットは1 チェックサムを加えると生成多項式で割り切れる 巡回符号と符号多項式 77 巡回符号は符号語を多項式で表現すると、符号 化や複合化の手順を簡単に取り扱うことができる。 符号語a に対しA(x)をaの多項式表現という。 符号語 : a an 1an 2 a1a0 符号多項式 : A( x) an 1 x n 1 an 2 x n2 a1 x a0 x 1 0 符号語長さnの符号は、係数が0または1のn-1次 以下の多項式の集合で表される。 符号語と符号多項式の例 n=7 78 1010011 x6 x4 x 1 (1 x 6 0 x 5 1 x 4 0 x 3 0 x 2 1 x1 11) 0100111 x5 x 2 x 1 1110100 x6 x5 x 4 x 2 符号多項式の係数は（2元符号であるので)0または1 巡回符号では、符号化や複合化の手順が符号多項式の四 則演算（加減乗除）によって表現される 符号多項式の加減乗除において、係数（0または1）の演算 は２を法とする演算 多項式の四則演算の例(1) 79 A(x)=x3+x (1010) B(x)=x+1 (0011) （たし算と引き算） A( x) B( x) x 3 x x 1 x 3 (1 1) x 1 x 3 1 A( x) B( x) x 3 x x 1 x 3 (1 1) x 1 x 3 1 A( x) B( x) 多項式の四則演算の例(2) 80 掛け算 A( x) B( x) ( x 3 x)( x 1) x ( x 1) x( x 1) x x x x 3 4 x x3 ) 1 x x x 4 x 4 x 3 x x 3 2 x 2 x 3 2 多項式の四則演算の例(3) 81 割り算 A( x) x 3 x x2 x B( x) x 1 x x 1) x 3 x 3 1 1 0 x 2 x x 2 x 2 x x 2 x 0 1 1 ) 1 0 1 0 1 1 0 1 1 1 1 0 0 0 0 0 巡回符号となる多項式 82 符号語の長さをn、符号多項式A(x)はn-1次とする。 A( x) an1 x n1 an2 x n2 a1 x1 a0 x 0 G(x)を定数項が１のr次(r<n-1)の多項式とする。 G( x) x r g r 1 x r 2 g1 x1 1 このG(x)の倍多項式で、n-1次以下のものC(x)を符 号多項式とする符号を考える。 C ( x) Q( x)G( x) ここで，Q( x)はn r 1次以下の任意の多項式である G(x)が特定の条件を満たすと巡回符号になる。 巡回符号となる多項式の例 83 例）n=7,r=4とし，G(x)を G(x)=x4+x3+x+1 とする． このときG(x)で作られる符 号は右の表のようになる． G(x)を生成多項式という チェックサム計算のアルゴリズム 84 rを生成多項式G(x)の次数とする。フレームの最 下位に0のビットをr個付加して、全体でm+rビッ トとし、D・2rを表すようにする。 D・2rを表すビット列をG(x)を表すビット列で2の 剰余系における割り算を用いて割る。 D・2rを表すビット列から2の剰余系における減算 を用いて余り（常にr個以下のビットを持つ）を引く。 結果が送信すべきチェックサムである。 ＣＲＣの計算例 85 D・2rをGで除算した 余りRを計算 D2 R remainder[ ] G r 86 データリンク層 基本的なプロトコル データリンクプロトコル 87 マシン Ａ マシン Ｂ バッファ バッファ 物理的な媒体 （物理層） 単方向 双方向 88 基本的なデータリンクプロトコル (1) 非制限単方向プロトコル（非現実的） データは、１方向のみ 誤りなし 処理時間を無視 無限のバッファ領域 単方向逐次確認プロトコル データは、１方向のみ 誤りなし 送信者が、受信者が処理できないほど速くデータを送るこ とを防ぐ 89 基本的なデータリンクプロトコル (2) 雑音がある場合の単方向プロトコル データは、１方向のみ 再送が必要 受信者側で、初めて見るフレームと再送されたものを区別 できるようにする必要がある → 各フレームヘッダに順序番号を付加 雑音がある場合の双方向プロトコル スライディング・ウィンドウ・プロトコル データリンクプロトコル 90 マシン Ａ マシン Ｂ データ バッファ バッファ 確認通知(ack) ピギーバック(piggybacking) 91 マシン Ａ マシン Ｂ データ バッファ バッファ データ 確認通知(ack) スライディング・ウィンドウ・プロトコル 92 大きさ＝１ 3ビットの順序番号 送信者 ・送信中， 送信済 ・確認通知が されていない 受信者 はじめ 最初のフレーム送信 最後のフレーム送信 Ackを受信 ・受信してよい フレーム番号 時間