物理層・データリンク

物理層

ビットを信号として送る電気的、時間的インターフェース
通信路の限界

ナイキスト限界：雑音がない有限帯域通信路に対する最大転送速度
シャノン限界：雑音を持った通信路に対する最大転送速度

伝送媒体

有線:銅線、光ファイバ、電力線(線路)
無線:地上無線、衛星、レーザー(自由空間)

データリンク層

物理層とネットワーク層の架け橋
上位層から見た時、隣接したコンピュータをあたかも専用の電線で接続されているかのようにみせかける技術

IP層(パケット転送)
データリンク層
物理層(ビット転送)

データリンク層の機能

誤り検出・誤り訂正(物理層で生じる伝送誤り)
フロー制御(遅い伝送者が早い送信者のデータで溢れることがないように)
多重アクセス(LANの場合)
プロトコル(ネットワーク層に対してきちんと定義されたインターフェース)

これらを実現するためにフレーム化

LAN(Local area network)とWAN(Wide area network)

LAN(構内通信ネットワーク,家庭,オフィス,学内)端末とスイッチングハブの接続

データリンク層で多重アクセスチャネルの制御(MAC)が必要(MAC副層)

WAN(広域ネットワーク,都市,国,大陸)Point to Pointによる一対一のルータ間の接続
論理リンク層: 上位層に論理的なリンクをサービスとして提供
MAC副層: 多重アクセスチャネルの制御(LANに対してのみ必要)

ネットワーク層からみたデータリンク層

仮想的なデータパスとしてみえる
仮想リンクが繋がっているものとして処理
仮想リンクが提供するサービスはいくつかの候補が考えられる

データリンク層が上位層に提供可能なサービス

Ackなしコネクションレスサービス(イーサネット(有線))(誤りが少ない)
Ackありコネクションレスサービス(無線LAN)
Ackありコネクション指向サービス(衛星通信、長距離電話回線)(信頼性が低い)

フレーム化

物理層から与えられたビットストリームをいくつかのフレームに分ける

メリット

誤りがあった際に制御がしやすい
フレーム単位で検出・訂正(誤り制御)
流量の制御がしやすい
フレーム単位でフィードバック、細かい粒度で流量制御可能(フロー制御)
多重化しやすい

フレーム化の方法

Question 「どのようにフレームの切れ目を入れるのか」

バイト数によるフレーム化

フレームの先頭にフレーム長を記録=>誤りが生じた時、それ以降が全てエラーとなる。

バイト詰めを伴うフラグ・バイト

フレームの開始、終了を示すフラグ・バイトを導入(フラグ・バイトは特別なパターンのビット列を用いる)
Question 「ペイロード(データ)中にバイト・フラグと同じビット列が出現したらどうすれば良い？」
エスケープバイト
送信側がペイロード中のフラグバイトの前にエスケープバイトを挿入(ex ESC)
Question 「ペイロード中にESCが現れたら？」
ESCの前にESCを置く
受信側は先頭のESCは常に削除

ビット詰めを伴うフラグ・バイト

2のバイト詰めを1ビット単位で行う
連続する6つの1(111111)が到着したらフレームの終了、開始
ペイロード中に連続する5つの1(11111)が到着したら0を入れる。

物理層符号化違反

誤り制御

Question 「伝送中にビットに誤りが生じた場合、どのようにしてそれを検出すれば良いか」

誤り検出(符号): 受信側に再送を要求させる

コネクション指向では受信側がAck(確認応答)を送り、
送信側がAckの内容あるいはタイマーの値に応じてフレームを再送

光ファイバーや品質が高い銅線では誤り率がきわめて低いので、誤り検出が有効

誤り訂正(符号): 誤りが生じてもデータの中身がわかるようにする

無線リンク等の誤り率の高いリンクでは誤りが生じた際に受信側が元のデータを復元できるような冗長な情報をつける誤り訂正符号が有効
誤り訂正符号をつけないとほとんど通信が成立しない
CD,DVD,QRコードなど、「再送」が原理的に許されないケース

各フレームちょうど一回だけ上位層に届くように管理する

誤り検出符号

元データ(mビット),検査ビット(rビット)=>(n,m)符号
符号化率: m/n

パリティビット

符号語に含まれる1のビット数の偶奇
問題点
単一パリティビットではバーストエラーは検出できない可能性がある(誤りが偶数個ある場合検出不可)
工夫: ブロックの分割
工夫: インターリービング(横だけでなく縦でもパリティビットをとる)

チェックサム(メッセージの検査ビットの集合を計算し、メッセージの最後に置く)
巡回冗長検査(CRC)

強力な誤り検出符号<-データの偏りに性能が依存しない
デジタル回路で実装が容易
長さr以下の全てのバースト誤りを検出できる
r+1ビットよりも長いバーストが来ても検出されない確率は極めて小さい(1/2)^(r-1)
(G(x)を因数にもつエラーが生じると検出不可能)
線形性 CRC(x^y)=CRC(x)^CRC(y)

誤り訂正

簡単な誤り訂正
1bitに対して3bit送り、多数決で推定する
単一誤り訂正符号
水平・垂直にパリティ検査符号を計算=>誤りの位置特定
パリティ検査方程式
シンドロームs=yH

主要な誤り訂正符号

ハミング符号(高速,訂正能力低い)
畳み込み符号(携帯電話や衛星通信,802.11で広く使われる)
リードソロモン符号(訂正能力が高い,バーストエラーに強い)
低密度パリティ検査符号(訂正能力が極めて高い,シャノン限界に近い,10Gbpsイーサネットなどいろいろ)

フロー制御

データリンク・プロトコル

フレームかと誤り制御を組み合わせる->フロー制御を実現するデータリンクプロトコルを実現

基本的なデータリンクプロトコル

理想的な単方向プロトコル

データはsenderからreveiverの片方向
データの処理時間を無視
無限のバッファ(データ溢れなし)
データリンク層間の通信に誤りはない(再送の必要なし)

誤りがないチャネルの単方向逐次確認プロトコル

送信者のデータ転送速度>受信者の受信速度
=>データ溢れ->フロー制御が必要
単方向で誤りなしを考える
solution: 受信者が送信者にフィードバック(確認通知)を送る
送信者は確認通知を待つ=逐次確認(stop-and-wait)

雑音があるチャネルの単方向逐次確認プロトコル

受信者は再送なのかどうかを区別しなければならない
solution: 各フレームのヘッダに順序番号を付与する
次のデータを送る前に肯定的な確認通知を待つプロトコルをARQ(Automatic Repeat rQuest)という。
確認通知がこない場合タイムアウトメカニズムで再送する

実用的には単方向ではなく双方向にデータを伝送

スライディング・ウィンドウ・プロトコル
フレームを送受信する順序やサイズに関して自由度
を与える
順序番号の集合をつねに管理

パイプライン

遅延が高い環境では逐次確認していては帯域の利用率が上がらない (ex. TCP通信)
ウィンドウサイズの範囲内で複数のフレームを同時に送信=パイプライン

Question 「複数フレームをパイプラインで送受信している際のエラー訂正方法」

一括再送(Go-back-N ARQ)

誤りがあった場合それ以降のフレームは廃棄、確認通知は返さない
タイムアウト後、エラー個所以降を再送してもらう

選択的再送(Selective ARQ)

不正なフレームのみ廃棄、それ以降の正しいフレームはバッファにためる
誤りを検出した場合、否定的確認通知(NAK)を送信することで性能を向上(フィードバック)

まとめ

物理層の種別
データリンク層の役割
- フレーム化(物理層<=>データリンク層)
- 誤り制御
- フロー制御