21年度ネットワーク - LOG>>KYO2009

編集

「全二重伝送路のためのARQについて」

• ARQとは

ARQには、

• Stop-and-Wait ARQ
• Go-back-N ARQ
• Selective Repeat ARQ

がある.

ここでは、TCPに実装されていない話題をしており
TCPを頭においておくと誤爆の危険性がある。

・Stop-and-Wait ARQ

フレームを送られるとACKを返す。
フレームを送り、フレーム誤りが検出されると、NACKを返す。
フレームを送り、タイムアウトになると
再送される。
これが、Stop-and-Wait ARQである。
もちろんデータ遅延も考えられるので
片方向電波遅延のことも頭においておかなければならない

・Go-back-N ARQ

先ほどとは、ちがい、ACKを受け取ることなく
最大N個のデータフレームを送信することができる
N番目のデータフレームに誤りが生じた
もしくは、タイムアウトになった場合
N番目以降のデータフレームをすべて再送する
その場合N番目以降の受信したデータフレームは棄却される。

• Selective Repeat ARQ

Go-back-N ARQと、ほぼ一緒だが
誤りの生じたフレームしか再送しなという違い考えられる。

解答

(1)-
ⅠSWARQには、必要なく、GNARQには必要なもの

• 送信側ノードでの送信データフレーム数の管理

理由→SWでは、フレームの到達を確認してひとつずつ
フレームを送るので必要ないが、
GNでは、データフレームの番号を管理し、
再送するフレームを特定しないといけないから

• 受信側ノードでの受信済みデータフレーム番号の管理

理由→SWでは、受信は、フレーム番号どおりに来るので必要ないが
GNでは、フレーム番号を控えておかなければ再送の要求が
できないから

ⅡGNARQには、必要なく、SRARQには必要なもの

• 受信データフレームの並べ替え

理由→GNでは、誤りフレーム以後を順番どおりに再送するが
SRでは、誤りフレームだけを再送するので
受信側で並べ替えが必要になる。

• 受信側ノードでの最大N個分のデータフレームバッファの管理

並べ替える際に必要になるので

katの解答

(1)-
ⅠSWARQには、必要なく、GNARQには必要なもの

答え：　aとe

a：データフレーム番号によるデータフレームの識別
SWでは，ACK済みのフレームの次のフレーム以外を送信側が送出することはないので，受信側はフレーム番号を調べる必要がない．しかし，GNでは，パケット消失の場合に1個とばして次のフレームがくることがあるので，フレーム番号を管理する必要がある．

e：送信側ノードでの最大N個分のデータフレームバッファの管理
SWでは，再送するのは最後に送った1フレームだけなので必要ないが，GNの場合は第kフレームを送った場合で第k-N-1フレームのNACKが届くことがあり得る．再送のためにはNフレーム分の蓄積が必要である．

ⅡGNARQには、必要なく、SRARQには必要なもの

b，c，f…なので，選ぶなら絶対bとf！

b：受信側ノードでの受信データフレームの並び替え
損失したパケットだけがあとで送られてくるので，SRには並べ替えが必要．

c：受信側ノードでの受信済みデータフレーム番号の管理
欠落したフレームだけが送られてくるので，最近のNフレーム分は正常受信したフレーム番号を記憶しておく必要がある．

f：受信側ノードでの最大N個分のデータフレームバッファの管理
フレームkが失われて，k+1，k+2，…k+N-1，フレームk　というようにNフレームの後に再送されることがあり得る．よって，Nフレームを蓄積しておく必要がある．

（2）-
SWとGNの平均スループット

• 片方向遅延　40ms
• 通信速度1000bps
• フレームロス，誤り無し
• 100bitのデータフレームを99個送信
• ACK，NACｋフレームは20bit
• GNのNは3
• 平均スループットとは，送信側ノードにおける一つ目のデータフレーム送信開始から，最後のデータフレームに対するACKフレーム受信完了までの単位時間あたりのデータ量（単位はbps）

katの解答

SW：　500bps
GN：　990bps

100bit/100bps=100ms
20bit/1000bps=20ms

まずは，SWについて考える．
パケットが受信側に要する時間は，100+40=140ms
ACKが送信側に届くのに要する時間は，20+40=60ms

したがって，1フレームの送信から受信応答までに合計200msの時間を要する．

SWでは，各データフレームごとに送信動作が独立しているため，99フレームのスループットを求めなくともよい．
したがって，1フレームあたりの平均スループットを求めると
100bit/200ms=500bps

次に，GNについて考える．

3フレームを送り出すまでに要する時間は100×3=300ms
先頭フレームのACKが帰ってくるまでの時間は，SWと同じで200msである
したがって，Nフレーム送信し終るまでにACKが届き始めるため
フレームの送信は途切れることなくおこなわれる．

よって，送信の所要時間は100×99=9900ms
最後のフレームを送り出し終えてから，そのACKが帰ってくるまでの時間は40+40+20=100ms

よって，全通信には9900+100=10000msを要する．
したがって，平均スループットは100bit×99÷10000ms=990bps

（3）-
片方向伝搬遅延200msでのSWとGNの平均スループット

• 片方向伝搬遅延を200msとする
• 他は，(2)と同じ条件でOK

katの解答

SW：　192.3bps
GN：　570bps

まずはSWについて考える．

前問と同様の議論で，
100bit÷（100+200+20+200）ms=100/520=192.3bps

次にGNについて考える．

3フレームを送り出しおわるまでの時間が300ms．
先頭のフレームのACKが返ってくるまでの時間は，
100+200+20+200=520ms．

よって，送信側は3フレーム送り出した後，220ms送信を止めてACｋを待つことになる．
3つのACKは100ms間隔で届くため，続く3つのフレームも休み無く送出される．
したがって，以降は300msの連続送信と200msのACK待ちを繰り替えることになる．

最初のフレームから第97フレームのACKが届き終るまでの時間は，
(300+220)×33=17160ms
それ以降，100ms間隔でACKが届くので，第99フレームのACKが届き終るまでには100+100=200msを要するため，
総時間は17160+200=17360ms．

したがって，平均スループットは，
100bit×99÷17360ms≒570bps

（4）-
0.1の確率でフレーム誤りが起きた場合の平均スループット

• 伝送媒体でのフレームロスは発生しない
• 確率0．1でフレーム誤りが発生する
• 他の条件は(2)と一緒

katの解答

SW：　454.5bps
GN：　826.7bps

まずはSWについて考える．

フレーム誤り1回あたりのタイムロスは，送信成功した場合のフレーム1個あたりの時間と同じ．
よって，エラーがない場合と比べて10％長く時間がかかる．
したがって，スループットが（10÷11）に悪化するので，
500bps×（10÷11）＝454.5454…≒454.5bps

つぎに，GNについて考える．

（2）と同様な議論で，第aフレームでフレームエラーが起きたことが第a+2フレームを送り終るまでに送信側に伝わるため，送信側は休み無くフレームまたは再送フレームを送信し続けることになる．
第aフレームのNACKが到着するまでの遅れは200msなので，送信側は第a+1フレームを送信した次に第aフレームを再送する．
この場合，第a+1フレームも再送されるので，誤り1回あたりに2フレームが再送されることになる．

誤り率は10％なので，再送を含めるとのべ1.2倍の個数のフレームを送信することになる．
よって，最後のフレームを送信し終るまでに要する時間は元の時間の1.2倍であるから，100×99×1.2=11880ms
最後のフレームを送り出し終えてから，そのACKが返ってくるまでの
時間は，40+20+40=100ms．
よって，全通信には11880+100=11980msを要する．

したがって，平均スループットは100bit×99÷11980ms≒826.7bps．

…だがしかし！

SWの場合をもう一回考えると，エラーで再送した時も，0.1の確率でフレーム誤りが起こるのでした．それを考慮すると，
500bps×（10÷11.1111…）=5000×（9/10）=450bps

あ，キレイな数字になったから，こっちが正解か．
ってことは，GNの方も間違ってるのか　orz

…先生！直す気力がないです！

（5）-
グラフの横軸特定

• 縦軸が平均スループット
• 横軸は不明
• 片方向伝搬遅延40msで，通信速度1000bps
• 長さ100bitのデータフレームを順次送りつけた場合の

　SW，GN，SRの平均スループットを示したグラフらしい

• まっすぐな線が2本．なんか曲がってるのが1本
• 明らかに1本は低く，残り2本は大体一緒

katの解答

スループットのグラフが右下がりで，右端で0になっていることから，
フレーム誤り確率またはフレーム消失確率が候補として考えられる．グラフの線はどれも連続であり，2本は直線である．
しかし，フレーム消失の場合，スライディングウインドウで隠蔽できないほどの消失率のところで折れ曲がりまたは変曲点が生じると考えられるため，候補からはずれる．
したがって，横軸はフレーム誤り確率である．

SWとSRは誤りが起きたフレームだけ再送するので，確率に対して直線のグラフになるはずである．
GNでは，1つの誤りに対して複数のフレームを再送するのでスループットはSRより悪いが，ACKを待たずにNパケット送信できる分，SWよりは良いと考えられる．したがってグラフの線は下から順に，SW，GN，SRとなる．

• tsuto
  -- (kyo!) 2009-07-16 16:45:37
• あとは、ｋａｔさんがやってくれます(笑) -- (kyo!) 2009-07-17 22:00:07
• お，ちょっとまってください
  っていうか，wordファイルで送っても良いですか
  （wikiの意味皆無w） -- (kat) 2009-07-17 22:33:03
• 大学院の過去門の解答って案外なかったりするもんだな -- (kyo!) 2009-07-19 11:45:32