PowerPoint プレゼンテーション

Center for Information Media Studies, Nagoya Univ.
パケット通信システム
誤り制御方式
名古屋大学
情報メディア教育センター
岡田啓
情報通信工学ⅡA
2004年6月14日
Center for Information Media Studies, Nagoya Univ.
パケット通信

パケット

情報をパケットと呼ばれる固まりにして，
固まり単位に宛名，差出人などのヘッダ情報を付加
→パケット単位で情報を送ることが可能
ヘッダ


コンピュータネットワークの分野で発達
基本的なアクセス方式



データ
Center for Information Media Studies, Nagoya Univ.
誤り制御方式


通信路上の雑音やパケットの
衝突などにより，誤りが発生
この誤りの影響を軽減する手
法が誤り制御方式である
1101001・・・



誤り検出符号
誤り訂正符号
パケットの再送
Automatic Repeat reQuest
雑音
通信路
1101101・・・
誤り
衝突
成功
伝送パケット
t
Center for Information Media Studies, Nagoya Univ.
誤り検出符号
情報に冗長を付加することで，誤りを検出

例：パリティ検査ビット


情報内の１の数が偶数または奇数になるように
検査ビットを付加
１の数を数えることで誤りを検出
検査ビット
1 0 1 1 0 1 1 1
0 1 1 0 1 0 1 0

他にCRC符号（巡回符号）などがある
Center for Information Media Studies, Nagoya Univ.
誤り訂正符号
情報に冗長を付加することで，誤りを訂正

例：繰り返し符号
1

111
伝送
101
復号化
1
代表的な誤り訂正符号




符号化
誤りが発生
ブロック符号・・・・ハミング符号，BCH符号，RS符号
畳み込み符号・・・畳み込み符号，岩垂符号
連接符号・・・・・・・ターボ符号，積符号
ＣＤ，携帯電話，デジタルＴＶ等，広範囲で利用
Center for Information Media Studies, Nagoya Univ.
Automatic Repeat reQuest (ARQ)
誤りのあるパケットを検出して，これを再送



誤りなく受信したとき，Ack (ACKnowledge) を返信
誤りを検出したとき，Nak (Not AcKnowledge) を返信
タイムアウトが起こったときも再送
Ack
送信

受信
Nak
送信
代表的なARQ方式



Stop and Wait ARQ
Go-back-n ARQ
Selective Repeat ARQ
受信
タ
イ
ム
ア
ウ
ト
送信
受信
Center for Information Media Studies, Nagoya Univ.
Stop and Wait ARQ
最も基本的なARQ方式



パケットを送信したら，
Ack/Nakを受信またはタイ
ムアウトが起こるまで待つ
Ackを受信したら次のパ
ケットを送信
Nakを受信，またはタイムア
ウトが発生したらパケットを
再送
Nak
再送
Ack
タ
イ
ム
ア
ウ
ト
再送
Ack
送信
受信
Center for Information Media Studies, Nagoya Univ.
Go-back-n ARQ



各送信パケットにシーケンス番号 (SN) を付加
送信側はAck/Nakを受け取らなくても次のパケットを送信
Nakを受け取ると，誤ったパケットに戻ってそのシーケンス
番号からパケットを送りなおす
1
2
3
4
5
6
7
3
4
5
6
7
送信
1
2
3
4
5
6
7
3
4
5
受信
Ack
Ack
Nak
廃棄
Ack
Ack
Ack
Center for Information Media Studies, Nagoya Univ.
Selective Repeat ARQ




各送信パケットにシーケンス番号 (SN) を付加
送信側はAck/Nakを受け取らなくても次のパケットを送信
Nakを受け取ると，誤ったパケットのみを再送
それ以降は再送する前のパケットの次のパケットを送信
1
2
3
4
5
6
7
3
8
5
9
10
送信
1
2
3
4
5
6
7
3
8
5
受信
Ack
Ack
Nak
Ack
Nak
Ack
Ack
Ack
Ack
Ack
Center for Information Media Studies, Nagoya Univ.
ウィンドウサイズ



Go-back-n ARQ や Selective Repeat ARQで使用
送信側はAck/Nakを受け取らなくても送ることができるパ
ケットの数をウィンドウサイズ W に制限
パケットを送る量を制限できる（フロー制御）
1
2
3
4
5
3
4
5
送信
1 Ack
2 Ack
3 Nak
4
廃棄
5
3 Ack
4 Ack
5 Ack
受信
Center for Information Media Studies, Nagoya Univ.
伝送効率（スループット）
その１
伝送効率（スループット）
伝送に成功するパケットの呼量（単位時間あたりの延べ保留時間）
Stop & Wait ARQ

Tp (1  p)
Tp  Tw
Go-back-n ARQ

Selective Repeat ARQ
Tp (1  p)
Tp  Tw p
ウィンドウサイズ W が
ない場合
ただし，
パケット長： Tp (s)
往復遅延時間： Tw (s)
パケット誤り率： p
  1 p
ウィンドウサイズ W が
ない場合
Tp
Tw
Nak
Tp
Tw
Ack
Center for Information Media Studies, Nagoya Univ.
伝送効率（スループット）
Stop & Wait ARQ の伝送効率
その２
Go-back-n ARQ の伝送効率

Download Report