2.5 確実な転送

前節で見たように、フレームが転送中に破損し、CRC といった符号によって誤りが検出されることがある。誤りを訂正できる強力な符号も存在するものの、ネットワークのリンクで発生する可能性のある多数のビット誤りやバースト誤りに対処するにはオーバーヘッドが大きすぎて現実的でないことが多い。また誤り訂正符号が使われる場合 (例えば無線リンク) でも、誤りが多すぎて訂正できない状況は発生する。そのため、破損したフレームの一部は破棄しなければならない。フレームを確実に転送する役目を持つリンクレベルのプロトコルは、どうにかして破棄された (失われた) フレームを復元しなければならない。

転送の確実性はリンクレベルで提供される可能性のある機能であるものの、現代のリンクテクノロジの多くはこの機能を省略している事実は注目に値する。さらに、確実な転送はトランスポート層、ときにはアプリケーション層といった上位のレベルで提供されることが多い。正確にどこで提供すべきかは多少の議論が必要なテーマであり、様々な要因によって変化する。確実な転送の基本的な考え方は層が変わっても同じなので、本節ではこの考え方を説明する。本節ではリンク層以外の層にも話題が及ぶことに注意してほしい。

多くの場合、確実な転送は二つの基礎的な仕組みを使って達成される ── 確認応答 (acknowledgment) とタイムアウト (timeout) である。確認応答 (ACK と略される) は送られたフレームを受け取ったことを伝えるために受信側が送信側に送り返す小さな制御用フレームを指す。「制御用フレーム」とはデータを持たないヘッダーだけのフレームを言う。ただし、もし逆方向に送信するデータフレームが ACK 以外に存在する場合は、そのフレームに確認応答の情報をピギーバック (piggyback, 便乗) させることができる。ACK を受信した送信側は、送信したフレームが正しく受信側へ到着したことを確信できる。送信側がフレームを送信してから一定の時間が経過しても ACK を受け取らない場合、そのフレームは再送 (retransmition) される。一定の時間がたっても操作の完了が確認できない場合に操作を最初からやり直すことをタイムアウトと呼ぶ。

確認応答とタイムアウトを利用して確実な転送を実装する一般的な戦略を ARQ (automatic repeat request, 自動再送要求) と呼ぶ場合がある。本節では異なる ARQ アルゴリズムを一般的な言葉で、つまり特定のプロトコルのヘッダーフィールドを詳しく示すことなく説明する。

2.5.1 ストップアンドウェイト

最も簡単な ARQ アルゴリズムはストップアンドウェイト (stop-and-wait) アルゴリズムと呼ばれる。その考え方は簡単で、送信側が一つのフレームを送信したらその確認応答を受け取るまで待機し、確認応答を受け取ってから次のフレームを送信するというものである。一定の時間が経過しても確認応答を受け取れない場合には、送信側は時間切れと判断してフレームを再送する。

この単純なアルゴリズムで発生する可能性のある四つの異なるシナリオのタイムラインを図 34 に示す。送信側が左に、受信側が右に示され、時間は上から下に向かって流れる。(a) ではタイムアウトの制限時間内に ACK が届き、(b) と (c) ではそれぞれフレームと ACK が喪失し、(d) ではタイムアウトが ACK の到着よりも早く発生する。ここで「喪失する」とは、フレームが転送中に破損し、その破損が受信側の誤り検出符号で検出され、最終的にフレームが破棄されることを意味する。

図 34 のようなパケットタイムラインはプロトコルの教育、説明、設計でよく使われる。分散システムの振る舞いを時系列に沿って視覚的に表現できるので、パケットタイムラインは有用性が高い ── 分散システムは分析が非常に難しくなる場合もある。プロトコルの設計では、予期しない事態への対処が必要な場合がよくある ── システムはクラッシュしたり、メッセージが喪失したり、すぐに終わると思っていた操作に長い時間がかかったりする。パケットタイムラインを使うと、そういったケースで何が正しく動かなくなるかが分かりやすくなり、プロトコル設計者は全てのイベントへの対処を考えやすくなる。

ストップアンドウェイトアルゴリズムには細かな工夫が必要となる重要な点が一つある。送信されたフレームに対して受信側が送り返した確認応答が喪失または遅延した状況を考えよう。これは図 34 の (c) または (d) に対応する。両方のケースにおいて、送信側はタイムアウトと判断してフレームを再送する。しかし受信側はそのフレームを既に受け取って確認応答も送信しているので、再送されたフレームを次のフレームとみなしてしまう。そのため何もしないと、重複するフレームが転送される可能性がある。この問題を解決するために、ストップアンドウェイトアルゴリズムを使うプロトコルの多くはヘッダーに 1 ビットのシーケンス番号 ── 0 か 1 の値を取るフレーム識別用の数値 ── を用意して、フレームごとに 0 と 1 を交互に使用する。この様子を図 35 に示す。例えば送信側がフレーム 0 を再送するときは、受信側はそれがフレーム 0 の二つ目のコピーであり、フレーム 1 の一つ目のコピーではないと判断できるので、既に受け取っている場合 (ACK が喪失した場合) には無視できる。

ストップアンドウェイトアルゴリズムの主な欠点は、任意の瞬間に処理中のフレームがリンク上に一つしか存在できないことである。一つのフレームはリンクの容量よりはるかに小さい可能性がある。例として、ラウンドトリップタイム (RTT) が 45 ms の 1.5 Mbps リンクを考えよう。このリンクは 67.6 Kb つまり約 8 KB の帯域遅延積を持つ。送信側は RTT ごとにフレームを一つしか送れないので、フレームのサイズを 1 KB とすれば転送レートは次のように計算できる:

これはリンクの容量の約 8 分の 1 でしかない。このリンクを使い切るには、送信側は確認応答の待機を始める前に 8 個のフレームを送信できなければならない。

2.5.2 スライディングウィンドウ

リンクの帯域遅延積が 8 KB でフレームが 1 KB のシナリオをもう一度考えよう。この場合、1 個目のフレームに対する ACK が送信側に返ってきたタイミングで 9 個目のフレームの転送準備が整うのが望ましい。これを可能にするアルゴリズムはスライディングウィンドウ (sliding window) と呼ばれる。このアルゴリズムのタイムラインを図 36 に示す。

アルゴリズム

スライディングウィンドウアルゴリズムは次のように動作する。まず、送信側はシーケンス番号 (sequence number) SeqNum を各フレームに割り当てる。最初は SeqNum が有限サイズのヘッダーフィールドで実装される事実を無視して、無限に大きくなれると仮定する。SeqNum の他に送信側は三つの変数を管理する:

• SWS: 一度に送信して処理中 (確認応答待ち) にできるフレーム数の最大値を表す (send widnow size)。
• LAR: 確認応答を受け取ったフレームのシーケンス番号の最大値を表す (last acknowledgment received)。
• LFS: 送信したフレームのシーケンス番号の最大値を表す (last frame sent)。

さらに、送信側は次の不変条件を常に成立させる:

この状況を図 37 に示す。

確認応答が到着すると LAR が右に移動するので、送信側は新しいフレームを一つ送信できるようになる。また、送信側は転送した各フレームにタイマーを設定し、一定時間で確認応答が返ってこなければフレームの再送を行う。確認応答が返ってくるまではフレームを再送のために取っておかなければならないので、送信側は最大で SWS 個のフレームをバッファする必要があることに注意してほしい。

受信側は次の三つの変数を管理する:

• RWS: 順番が前後した場合でも受け取ることができるフレーム数の最大値を表す (receive window size)。
• LAF: 受け取ることができるフレームのシーケンス番号の最大値を表す (largest acceptable frame)。
• LFR: 最後に確認応答を送信したフレームのシーケンス番号を表す (last frame received)。

さらに、受信側は次の不変条件を常に成立させる:

この状況を図 38 に示す。

シーケンス番号 SeqNum のフレームが到着したとき、受信側は次のように振る舞う。もし SeqNum <= LFR または SeqNum > LAFなら、そのフレームは受信側のウィンドウの外にあるので受信側はそれを破棄する。もし LFR < SeqNum <= LAF なら、フレームは受信側のウィンドウの内側にあるので受信側はそれを受け取る。続いて ACK を送信するかどうかの判断が行われる。SeqNumToAck を「シーケンス番号が SeqNumToAck 以下のフレームは全て受け取っている」かつ「シーケンス番号 SeqNumToAck のフレームに対する確認応答を送信していない」という条件が成り立つフレームのシーケンス番号の最大値とする。そして受信側は (もっと大きな番号を受け取っていたとしても) シーケンス番号 SeqNumToAck のフレームに対する確認応答を送信する。この確認応答は累積的 (comulative) であると呼ばれる。受信側はその後 LFR = SeqNumToAck に設定し、LAF = LFR + RWS と更新する。

例として、LFR = 5 (受信側はフレーム 5 に対する ACK を最後に送信した) かつ RWS = 4 の場合を考えよう。このとき LAF = 9 が分かる。フレーム 7 とフレーム 8 が到着すると、それらは受信側のウィンドウに収まっているのでバッファされる。しかしフレーム 6 が到着していない (フレーム 7, 8 は順番が前後して到着した) ので、確認応答は送信されない (正確に言うと、このとき受信側はフレーム 5 の確認応答を送信しても構わない)。その後フレーム 6 が到着する ── 最初に到着したときに破損していたために再送が必要になったのかもしれないし、単に転送の遅延で遅れたのかもしれない¹ ── と、受信側はフレーム 8 に対する確認応答を送信する。その後 LFR は 8 に、LAF は 12 になる。フレーム 6 が本当に喪失した場合は、送信側でタイムアウトが起こり、フレーム 6 の再送が行われる。

タイムアウトが発生したとき送信側は再送したフレームの確認応答を受け取るまでウィンドウを動かせないので、転送状態にあるデータの量が減少することが分かる。これは、スライディングウィンドウアルゴリズムではパケットロスが発生するとパイプに隙間が生まれることを意味する。パケットロスの発生に気付くのが遅れると、この問題はそれだけ大きくなる。

先ほどの例において、受信側がフレーム 7 を受け取ったときにフレーム 6 に対する NACK (negative acknowledgment, 否定応答) を送信する工夫も考えられる。しかし、この工夫は必要ない: フレームが届かない状況はタイムアウトの仕組みがあれば十分検出でき、NACK の送信処理によって受信側の複雑さが増してしまう。加えて先述したように、フレーム 7 とフレーム 8 を受け取ったときに受信側がフレーム 5 に対する確認応答をもう一度送信しても構わず、送信側が重複して届く ACK をフレーム喪失のヒントとして利用できる場合もある。こういった工夫はパケットロスの素早い検出を可能にすることでパフォーマンスを改善する。

スライディングウィンドウのさらにもう一つの変種として、選択的確認応答 (selective acknowledgment) を使う方法がある。選択的確認応答を使うと、受け取った中で最もシーケンス番号の大きいフレームに対する確認応答だけではなく、受け取ったフレーム全てに対する確認応答が受信側から送信される。上で示した例では、フレーム 7, 8 に対する確認応答が受け取った時点で送信される。追加の情報を与えることで送信側はパイプの隙間を詰められるものの、実装は複雑になる。

送信ウィンドウサイズ (SWS) は考えているリンク上で同時に転送状態にしたいフレームの個数に応じて選択される。そのため帯域遅延積が分かれば SWS は簡単に決められる。これに対して、受信ウィンドウサイズ RWS は好きな値に設定できる。よく利用される値として RWS = 1 と RWS = SWS がある。RWS = 1 だと受信側は順番が前後して到着するフレームを一切バッファせず、RWS = SWS だと受信側は送信側が転送する任意のフレームをバッファできる。なお RWS > SWS とする意味はない: 順番が前後して SWS 個より多いフレームが届くことはない。

有限シーケンス番号とスライディングウィンドウ

前項でアルゴリズムを説明したときに置いた仮定をもう一度考えよう ── シーケンス番号は無限に大きくなれると仮定していた。実際にアルゴリズムを実装するときは、当然フレームのシーケンス番号は有限サイズのヘッダーフィールドで指定しなければならない。例えば、3 ビットのフィールドは 0 から 7 までの 8 つのシーケンス番号しか使えないことを意味する。このためシーケンス番号の再利用、言い換えればシーケンス番号のラップアラウンドが必要になり、異なる意味で使われる同じシーケンス番号の区別という問題が発生する。少なくとも、シーケンス番号の個数は一度に処理中になる可能性のあるフレームの個数より大きい必要がある。例えばストップアンドウェイトアルゴリズムでは一度に処理中になるフレームは一つだけなので、二つのシーケンス番号があれば十分だった。

同時に処理中になる可能性のあるフレームの個数より多くのシーケンス番号を用意したとする。つまりシーケンス番号の個数 MaxSeqNum が SWS + 1 <= MaxSeqNum を満たすとする。これで十分だろうか？ 実は、十分かどうかは RWS の値に依存する。もし RWS = 1 なら、SWS + 1 <= MaxSeqNum で十分となる。しかし RWS が SWS と等しいなら、MaxSeqNum を送信ウィンドウサイズ RWS より一つ大きくするだけではシーケンス番号の見分けが付かなくなる問題を回避できない。この理由を理解するために、シーケンス番号が 0, ..., 7 の 8 個で、SWS = RWS = 7 である状況を考えよう。送信側がフレーム 0, ..., 6 を送信して全て正しく転送され、それらに対する ACK が全て喪失したとする。このとき、受信側が次に期待するのはシーケンス番号に 7, (最初に戻って) 0, ..., 5 が付いたフレーム 7, ..., 13 であるのに対して、送信側はタイムアウトを検知してフレーム 0, ..., 6 にシーケンス番号 0, ..., 6 を付けて再送する。そのため残念ながら、受信側は再送されたフレーム 1, ..., 6 をフレーム 8, ..., 13 と誤解してしまう。これはまさに避けようとしていた事態である。

送信ウィンドウサイズが RWS = SWS のときは、SWS を利用可能なシーケンス番号の半分以下とする必要があることが示せる。つまり次の不等式が成り立つ必要がある:

直感的に説明すれば、これはスライディングウィンドウアルゴリズムがシーケンス番号の空間を半分ずつ交互に使うということを言っている。これはストップアンドウェイトアルゴリズムが 0 と 1 を交互に使うのと同様である。ただしスライディングウィンドウアルゴリズムでは二つの空間が連続的に切り替わる点だけは異なる。ストップアンドウェイトアルゴリズムのように空間が離散的に一気に切り替わりはしない。

この不等式は RWS = SWS が成り立つときにだけ意味がある点に注意してほしい。RWS と SWS が任意の値を取る場合にも適用できる一般的な規則を求める問題は読者への練習問題とする。また、ここまでのウィンドウサイズとシーケンス番号の大きさに関する議論では、あまりにも明らかなために見過ごされやすい仮定を一つ置いている。それは「転送時にフレームの順番が並び替えられない」という仮定である。ポイントツーポイントリンクでは転送中にフレームが他のフレームを追い越すことはあり得ないので、この仮定は成り立つ。しかし、スライディングウィンドウアルゴリズムは異なる環境でも利用されており、そこでは別の規則が必要になることを後で見る。

スライディングウィンドウの実装

スライディングウィンドウアルゴリズムの送信側および受信側を実装するコードの例をここに示す。このコードは SWP (Sliding Window Protocol) という分かりやすい名前の付いた実際のプロトコルから取ったものである。プロトコルグラフで隣接する他のプロトコルを抽象化するために、SWP の上にあるプロトコルを HLP (high-level protocol, 上位プロトコル) と表記し、SWP の下にあるプロトコルを LLP (link-level protocol,リンクレベルプロトコル) と表記する。

まず二つの構造体を定義する。一つ目の非常に簡単な構造体 SwpHdr はフレームヘッダーを表す。SwpHdr はシーケンス番号 SeqNum と確認応答番号 AckNum、そしてフレームが ACK なのかデータを伝達するのかを表す Flags フィールドを持つ:

typedef uint8_t SwpSeqno;

typedef struct {
    SwpSeqno   SeqNum;   /* このフレームのシーケンス番号 */
    SwpSeqno   AckNum;   /* このフレームが ACK するフレームのシーケンス番号 */
    uint8_t     Flags;   /* 最大 8 ビットのフラグ */
} SwpHdr;

次に、スライディングウィンドウアルゴリズムの状態を表す構造体 SwpState がある。プロトコルの送信側の状態には本節で説明した LAR と LFS が含まれ、加えて転送されたものの確認応答がまだ届いていないフレームを保持するキュー sendQ、そしてsendWindowNotFull と呼ばれる計数セマフォ (counting semaphore) が含まれる。sendWindowNotFull の使い方は後で説明する。一般的に言うとセマフォは同期プリミティブであり、semWait と semSignal の操作をサポートする。semSignal を呼び出すとセマフォの値が 1 増加し、semWait を呼び出すとセマフォの値が 1 減少する。semWait を呼び出した結果セマフォの値が 0 未満になった場合、呼び出したプロセスはブロックする (待機状態になる)。semWait を呼び出してブロックしたプロセスは、他のプロセスが semSignal を呼び出すたびに一つずつ実行を再開する。

プロトコルの受信側の状態には、次に期待されるフレーム (next frame expected) を表す変数 NFE、そして本節で前に説明された LFR が含まれる。順番が前後して受信されたフレームを保持するキュー recvQ も送信側の状態は持っている。最後に、ここには示されていないものの、送信側と受信側のウィンドウサイズを表す定数 SWS と RWS がそれぞれ定義されている。

typedef struct {
    /* 送信側の状態 */
    SwpSeqno    LAR;        /* 最後に受信した ACK のシーケンス番号 */
    SwpSeqno    LFS;        /* 最後に送信したフレームのシーケンス番号 */
    Semaphore   sendWindowNotFull;
    SwpHdr      hdr;        /* 初期化される前のヘッダー */
    struct sendQ_slot {
        Event   timeout;    /* 送信タイムアウトに関連付けられるイベント */
        Msg     msg;
    }   sendQ[SWS];

    /* 受信側の状態 */
    SwpSeqno    NFE;       /* 次に期待されるフレームのシーケンス番号 */
    struct recvQ_slot {
        int     received;  /* msg は正当か？ */
        Msg     msg;
    }   recvQ[RWS];
} SwpState;

SWP の送信側は sendSWP 関数で実装される。この関数はそれほど難しくない。まず、semWait によって送信側から新しいフレームが送れるようになるまでブロックする。実効の進行を許されると、sendSWP はフレームのヘッダーにシーケンス番号を設定し、フレームを組み立て、転送キュー sendQ にフレームのコピーを保存し、フレームが確認応答されないときに備えてタイムアウトイベントをスケジュールし、最後に LINK で指定される下位のプロトコルを通してフレームを送信する。

static int sendSWP(SwpState *state, Msg *frame) {
    struct sendQ_slot *slot;
    hbuf[HLEN];

    /* 送信ウィンドウが空くのを待つ */
    semWait(&state->sendWindowNotFull);
    state->hdr.SeqNum = ++state->LFS;
    slot = &state->sendQ[state->hdr.SeqNum % SWS];
    store_swp_hdr(state->hdr, hbuf);
    msgAddHdr(frame, hbuf, HLEN);
    msgSaveCopy(&slot->msg, frame);
    slot->timeout = evSchedule(swpTimeout, slot, SWP_SEND_TIMEOUT);
    return send(LINK, frame);
}

sendSWP 関数で msgAddHdr を呼び出す前に store_swp_hdr 関数を呼び出していることは注目に値する。store_swp_hdr 関数は SWP ヘッダーを表す C 構造体 (state->hdr) をメッセージ列の先頭にそのまま加えられるバイト列に変換してバッファ (hbuf) に格納する。この関数 (省略されている) はヘッダーの整数フィールドをそれぞれネットワークバイトオーダーに変換し、加えてコンパイラが C 構造体に加えたパディングを全て削除する。バイトオーダーは簡単な問題ではないものの、今のところは store_swp_hdr 関数がマルチワードの整数の最上位ビットが最上位アドレスに来るようにバイトの順序を変更するのだと考えておけば十分である。

sendSWP 関数の複雑な部分としてもう一つ、semWait 関数と sendWindowNotFull セマフォの利用がある。sendWindowNotFull は送信側のスライディングウィンドウのサイズ SWS で初期化される (この初期化は示されていない)。送信側がフレームを送信しようとするたびに semWait 操作が sendWindowNotFull を 1 減らし、その結果 sendWindowNotFull が 0 より小さくなれば送信側をブロックする。ACK が受信されると deliverSWP 関数 (後述) で semSignal 操作が呼び出されてセマフォの値が増加し、待機中の送信側の一つが実行を再開する。

SWP の受信側に話を進める前に、見かけ上の非一貫性を一つ指摘しておく。一方では、これまで本書は「上位のプロトコルは下位のプロトコルのサービスを呼び出す」と説明してきた。よって SWP でメッセージを送信したいプロトコルは send(SWP, packet) を呼び出すだろうと期待される。しかしもう一方では、SWP の送信操作を実装する関数は sendSWP と呼ばれており、その第一引数は状態変数 SwpState である。どういうことだろうか？ この疑問への答えは「一般的な send の呼び出しをプロトコル固有の sendSWP の呼び出しに変換するグルーコードがオペレーティングシステムから提供される」となる。このグルーコードは send の第一引数 (プロトコルを表すマジックナンバー SWP) を sendSWP への関数ポインタと SWP が必要とするプロトコルの状態へのポインタに変換する。上位プロトコルが一般的な関数を通して間接的にプロトコル固有の関数を呼び出す理由は、上位プロトコルのコードに埋め込まれる下位プロトコルに関する情報を少なくするためである。こうするとプロトコルグラフの構成が変更しやすくなることを後で見る。

続いて受信操作の SWP プロトコル固有の実装に進もう。この操作は次の deliverSWP 関数が実装する。この関数は二つの異なる種類のメッセージを処理する。その二つとは、このノードから送信されたデータフレームに対する ACK と、このノードに送信されたデータフレームである。ある意味で、この関数の ACK を処理する部分は送信側の関数 sendSWP に対応すると言える。受け取ったメッセージが ACK かデータフレームかの判断はヘッダーの Flags フィールドをチェックすることで行われる。なお、ここに示した実装はデータフレームを使ったピギーバックに対応しない。

static int deliverSWP(SwpState state, Msg *frame) {
    SwpHdr   hdr;
    char     *hbuf;

    hbuf = msgStripHdr(frame, HLEN);
    load_swp_hdr(&hdr, hbuf)
    if (hdr->Flags & FLAG_ACK_VALID) {
        /* ACK を受信したので、送信側の処理を行う */
        if (swpInWindow(hdr.AckNum, state->LAR + 1, state->LFS)) {
            do {
                struct sendQ_slot *slot;

                slot = &state->sendQ[++state->LAR % SWS];
                evCancel(slot->timeout);
                msgDestroy(&slot->msg);
                semSignal(&state->sendWindowNotFull);
            } while (state->LAR != hdr.AckNum);
        }
    }

    if (hdr.Flags & FLAG_HAS_DATA) {
        struct recvQ_slot *slot;

        /* データパケットを受信したので、受信側の処理を行う */
        slot = &state->recvQ[hdr.SeqNum % RWS];
        if (!swpInWindow(hdr.SeqNum, state->NFE, state->NFE + RWS - 1)) {
            /* メッセージを破棄する */
            return SUCCESS;
        }
        msgSaveCopy(&slot->msg, frame);
        slot->received = TRUE;
        if (hdr.SeqNum == state->NFE) {
            Msg m;

            while (slot->received) {
                deliver(HLP, &slot->msg);
                msgDestroy(&slot->msg);
                slot->received = FALSE;
                slot = &state->recvQ[++state->NFE % RWS];
            }
            /* ACK を送信する */
            prepare_ack(&m, state->NFE - 1);
            send(LINK, &m);
            msgDestroy(&m);
        }
    }
    return SUCCESS;
}

受け取ったフレームが ACK なら、deliverSWP は ACK に対応するフレームを転送キュー (sendQ) から取り出し、タイムアウトイベントをキャンセルし、スロットに保存されたフレームを解放する。ACK は累積的なので、以上の処理は LAR から始まるループで行われる。このループの外側にある swpInWindow を使った if 文は、受け取った ACK に対応するフレームのシーケンス番号が現在のウィンドウ (受信を期待するフレームのシーケンス番号の範囲) に収まることを確認する。

受け取ったフレームがデータを含むなら、deliverSWP は msgStripHdr と load_swp_hdr を最初に呼び出してフレームからヘッダーを取り出す。load_swp_hdr は先ほど説明した store_swp_hdr と対になる関数であり、送られてきたバイト列を SWP ヘッダーを保持する C 構造体に変換する。続いて swpInWindow が呼び出され、受け取ったフレームのシーケンス番号が期待するシーケンス番号の範囲に収まっていることが確認される。もし収まっていれば、deliverSWP 関数は受け取ったフレームから到着済みのフレームを走査し、それぞれを deliverHLP 関数で上位プロトコルに渡していく。累積的な ACK の送信も行われる。ACK するシーケンス番号の計算では受け取ったフレームの走査で更新された state->NFE が使われており、本節の文章を使った説明で登場した SeqNumToAck は使われていない。

最後に、swpInWindow は与えられたシーケンス番号が最大値と最大値の間に収まるかどうかを判定する簡単な関数である:

static bool swpInWindow(SwpSeqno seqno, SwpSeqno min, SwpSeqno max) {
    SwpSeqno pos, maxpos;

    pos    = seqno - min;       /* pos は [0..MAX) に移る*はず* */
    maxpos = max - min + 1;     /* maxpos は [0..MAX] に含まれる */
    return pos < maxpos;
}

フレームの順序とフロー制御

スライディングウィンドウはおそらくコンピューターネットワークの分野で最もよく知られたアルゴリズムである。しかし、スライディングウィンドウが三つの異なる用途に利用できる事実は見過ごされることが多い。一つ目の用途として、本節で説明してきた処理 ── 信頼性の低いリンクを通したフレームの確実な転送 ── がある (一般に、信頼性の低いネットワークを通したメッセージの確実な転送に利用できる)。これはスライディングウィンドウアルゴリズムの中心的な機能である。

二つ目の用途として、転送されるフレームが届く順序の保証がある。これは受信側で簡単に行える ── 各フレームにシーケンス番号が付いているから、自身よりシーケンス番号が小さいフレームが全て届いたフレームだけを上位のプロトコルに渡すだけで済む。このとき、受信側は順番が前後して届くフレームを (そのまま渡すのではなく) バッファしていると捉えられる。本節で説明したバージョンのスライディングウィンドウアルゴリズムはフレームの順序を保存するものの、届いていないフレームを待つことなく届いたフレームを上位プロトコルにすぐに渡す変種も簡単に考えられるだろう。スライディングウィンドウを用いるプロトコルを使ったフレームの順序保証をリンクレベルで本当に実装すべきなのか、それともスタックのもっと上位にあるプロトコルでこの機能を実装すべきなのかはよく考える必要がある。

三つ目の用途として、スライディングウィンドウアルゴリズムはフロー制御 (flow control) のサポートに使われることがある。フロー制御とは、送信するデータの量を制限するよう受信側から送信側に要求するフィードバックの仕組みを言う。これは通常、確認応答に加えて受信用の空間が存在するフレームの個数を受信側が送信側に伝えるようにスライディングウィンドウを使うプロトコルを拡張することで行われる。受信側が受け取れるフレームの個数はバッファ空間の大きさに対応する。順序を保証した転送と同じように、スライディングウィンドウを用いるプロトコルにフロー制御を取り込むときは、リンクレベルでフロー制御が必要なことを最初に確かめる必要がある。

2.5.3 並行論理チャンネル

オリジナルの ARPANET で用いられたデータリンクプロトコルはスライディングウィンドウアルゴリズムを採用せず、単純なストップアンドウェイトアルゴリズムを使いつつもパイプに大きな隙間が生まれないという意味で興味深い手法を使っていた。このアプローチの重要な帰結の一つとして、リンク越しに送信されたフレームが届く順番が保存されない点が挙げられる。さらに、このプロトコルではフロー制御を行えない。

ARPANET のプロトコルの裏にあるアイデアは、単一のポイントツーポイントリンクで複数の論理チャンネルを多重化し、論理チャンネルのそれぞれでストップアンドウェイトアルゴリズムを実行するというものである。このアイデアを本書では並行論理チャンネル (concurrent logical channel) と呼ぶ。論理チャンネルから送信されるフレーム間の関係性は一切管理されないものの、論理チャンネルのそれぞれが異なるフレームを処理できるのでリンクに隙間は生まれない。

具体的に言うと、送信側はチャンネルごとに 3 ビットの状態を管理する。その内訳は、現在ビジーかどうかを表す 1 ビット、次にフレームを送るときに使うべきシーケンス番号を表す 1 ビット、そして次に届くフレームで使われる予定のシーケンス番号を表す 1 ビットである。ノードがフレームを送信するときは最も番号の小さいアイドルチャンネルを最初に選択し、それ以降はストップアンドウェイトアルゴリズムと同様となる。

実際の ARPANET は地上回線では 8 個の論理チャンネル、衛星回線では 16 個の論理チャンネルをサポートした。地上回線における各フレームのヘッダーは 3 ビットのチャンネル番号と 1 ビットのシーケンス番号の 4 ビットだった。これは RWS = SWS と設定するスライディングウィンドウアルゴリズムを用いるプロトコルで 8 個のフレームを処理中にできるようにするために必要となるビット数とちょうど同じである。