uTorrent 伝送プロトコル（uTP）は、Ludvig Strigeus、Greg Hazel、Stanislav Shalunov、Arvid Norberg、および Bram Cohen によって設計されました。
設計理由#
uTP プロトコルの動機は、BitTorrent クライアントがインターネット接続を中断せず、未使用の帯域幅を十分に活用できるようにすることです。
BitTorrent トラフィックは通常バックグラウンドで伝送され、その優先度は電子メールの確認、オフィス作業、ウェブブラウジングよりも低いべきですが、通常の TCP 接続を使用すると、BitTorrent は送信バッファを迅速に埋め尽くし、すべてのインタラクティブトラフィックに数秒の遅延を追加します。BitTorrent が複数の TCP 接続を使用する事実は、他のサービスと帯域幅を競合する際に不公平な利点をもたらし、BitTorrent がアップロード帯域幅を占有する効果を誇張します。これは、TCP が接続間で利用可能な帯域幅を均等に分配し、アプリケーションが使用する接続が多いほど、得られる帯域幅の割合が大きくなるためです。
この問題の従来の解決策は、BitTorrent クライアントのアップロード速度を上り帯域幅容量の 80% に制限することです。これにより、残りの上りおよび下りトラフィックにいくらかのスペースが残ります。この解決策の主な欠点は次のとおりです：
- ユーザーは自分の BitTorrent クライアントを設定する必要があり、即座に使用できるわけではありません。
- ユーザーは自分のインターネット接続の上限容量を知っている必要があります。この容量は変動する可能性があり、特に多くの異なるネットワークに接続する可能性のあるノートパソコンや携帯電話では特にそうです。
- 20% の余裕は比較的随意であり、帯域幅を無駄にします。インタラクティブトラフィックが BitTorrent と競合しないとき、追加の 20% が無駄になります。競合するインタラクティブトラフィックが存在する場合、それは単に 20% の容量を使用する必要がありません。
uTP は、モデムのキューサイズを送信速度のコントローラとして使用することでこの問題を解決します。キューが大きくなりすぎると、トラフィックを制御します。これにより、競合がないときに全てのアップロード容量を利用し、大量のインタラクティブトラフィックがあるときにはほぼゼロに減少させることができます。
概要#
この文書は、読者が TCP とウィンドウベースの輻輳制御の動作について一定の理解を持っていることを前提としています。uTP は UDP の上に構築された伝送プロトコルです。したがって、独自のネットワーク輻輳制御を実装する必要があります（そしてその能力があります）。TCP と比較して、主な違いは遅延に基づく輻輳制御です。
uTP は UDP の上に構築された伝送プロトコルであるため、独自の輻輳制御メカニズムを実装する必要があります。TCP と比較して、uTP の主な違いは遅延に基づく輻輳制御です。具体的な詳細は、輻輳制御の部分の説明を参照してください。TCP と同様に、uTP はウィンドウベースの輻輳制御を採用しています。各ソケットには、任意の時点で同時に送信できる最大バイト数を決定するための max_window があります。送信されたがまだ確認されていないデータパケットは、伝送中と見なされます。
- cur_window は、現在の伝送中のバイト数を示します。cur_window + packet_size が min (max_window, wnd_size) 以下である場合にのみ、ソケットはデータパケットを送信できます。packet_size はデータパケットのサイズを示し、異なる値を持つ可能性があります。
- wnd_size は、相手ポートが広告するウィンドウサイズです。これは、伝送中のデータパケットの数の上限を設定します。
- max_window がデータパケットサイズより小さい場合、データパケットの伝送速度を調整することで、平均 cur_window が max_window 以下になるようにすることは、上記のルールに違反する可能性があります。
- 各ソケットは、他のエンドポイントとの最後の遅延測定状態（reply_micro）を保持します。データパケットを受信するたびに、タイムスタンプ（マイクロ秒単位）からホストの現在の時間を引くことでこの状態を更新します。
- データパケットを送信するたびに、ソケットの reply_micro 値はデータパケットヘッダーの timestamp_difference_microseconds フィールドに配置されます。
- TCP と異なり、uTP のシーケンス番号と ACK はバイトではなくデータパケットに基づいています。これは、データを再送信する際に uTP がそれを再パッケージ化できないことを意味します。
- 各ソケットは、次にデータパケットを送信するためのシーケンス番号（seq_nr）と、最後に受信したデータパケットのシーケンス番号（ack_nr）の状態を保持します。最も古い未確認データパケットのシーケンス番号は seq_nr – cur_window です。
header フォーマット#
バージョン 1 ヘッダー：
0 4 8 16 24 32
+-------+-------+---------------+---------------+---------------+
| type | ver | extension | connection_id |
+-------+-------+---------------+---------------+---------------+
| timestamp_microseconds |
+---------------+---------------+---------------+---------------+
| timestamp_difference_microseconds |
+---------------+---------------+---------------+---------------+
| wnd_size |
+---------------+---------------+---------------+---------------+
| seq_nr | ack_nr |
+---------------+---------------+---------------+---------------+
すべてのフィールドはネットワークバイトオーダー（ビッグエンディアン）で配置されています。
バージョン#
これはプロトコルのバージョンです。現在のバージョンは 1 です。
connection_id#
これは、同じ接続に属するすべてのデータパケットを識別するためのランダムな一意の番号です。各ソケットには、データパケットを送信するための接続 ID と、データパケットを受信するための異なる接続 ID があります。接続を開始するエンドポイントがどの ID を使用するかを決定し、戻り経路は同じ ID + 1 になります。
timestamp_microseconds#
これは、このデータパケットを送信した時刻の「マイクロ秒」部分のタイムスタンプです。これは posix で gettimeofday () を使用し、Windows で QueryPerformanceTimer () を使用して設定されます。このタイムスタンプの解像度は高いほど良いです。設定が実際の伝送時間に近いほど良いです。
timestamp_difference_microseconds#
これは、ローカル時間と最後のデータパケット（最後のデータパケットを受信したとき）のタイムスタンプとの間の差です。これは、リモートピアからローカルコンピュータへのリンクの最新の一方向遅延測定です。ソケットが新しく開かれ、まだ遅延サンプルがない場合は、0 に設定する必要があります。
wnd_size#
広告された受信ウィンドウです。これは 32 ビット幅で、バイト単位で指定されます。ウィンドウサイズは、現在進行中のバイト数、すなわち送信されたが未確認のバイト数です。広告された受信ウィンドウは、相手側がウィンドウサイズを制限できるようにします。受信バッファが満杯になっている場合、より早く受信できない場合です。データパケットを送信する際には、ソケットの受信バッファ内の残りのバイト数に設定する必要があります。
extension#
拡張ヘッダーリンクリスト内の最初の拡張のタイプ。0 は拡張がないことを示します。
現在、1 つの拡張があります：
- 選択的確認
拡張はリンクされており、TCP オプションのように機能します。拡張フィールドがゼロでない場合、uTP ヘッダーの直後に続く 2 バイト：
0 8 16
+---------------+---------------+
| extension | len |
+---------------+---------------+
ここで、extension はリスト内の次の拡張のタイプを指定し、0 はリストを終了します。そして len はこの拡張のバイト数を指定します。未知の拡張は、単に len バイトを進めることでスキップできます。
SELECTIVE ACK#
選択的 ACK は、非順序的に選択的にデータパケットを ACK する拡張です。そのペイロードは、少なくとも 32 ビットのビットマスクで、32 ビットの倍数で表されます。各ビットは、送信ウィンドウ内の 1 つのデータパケットを表します。送信ウィンドウ外のビットは無視されます。設定されたビットはデータパケットが受信されたことを示し、クリアされたビットはデータパケットがまだ受信されていないことを示します。ヘッダーは次のようになります：
0 8 16
+---------------+---------------+---------------+---------------+
| extension | len | bitmask
+---------------+---------------+---------------+---------------+
|
+---------------+---------------+
拡張の len フィールドはバイトを参照し、この拡張では、バイトは少なくとも 4 であり、4 の倍数でなければなりません。
受信したストリームで少なくとも 1 つのシーケンス番号がスキップされた場合にのみ、選択的 ACK が送信されます。したがって、マスク内の最初のビットは ack_nr + 2 を示します。ack_nr + 1 は、このデータパケットを送信する際に破棄または失われたと仮定されます。設定されたビットは受信されたデータパケットを示し、クリアされたビットはまだ受信されていないデータパケットを示します。
ビットマスクのバイトオーダーは逆です。最初のバイトは、データパケット [ack_nr + 2、 ack_nr + 2 + 7] を逆順で表します。バイト内の最下位ビットは ack_nr + 2 を示し、バイト内の最上位ビットは ack_nr + 2 + 7 を示します。マスク内の次のバイトは、逆順で [ack_nr + 2 + 8、ack_nr + 2 + 15] を表し、以下同様です。ビットマスクは 32 ビットに制限されず、任意のサイズである可能性があります。
以下は、選択的 ACK ビットフィールドで表される最初の 32 個のデータパケット確認を示すビットマスクのレイアウトです：
0 8 16
+---------------+---------------+---------------+---------------+
| 9 8 ... 3 2 | 17 ... 10 | 25 ... 18 | 33 ... 26 |
+---------------+---------------+---------------+---------------+
図の数字は、ビットマスク内のビットを ack_nr に加算するオフセットにマッピングし、確認されているシーケンス番号を計算します。
type#
タイプフィールドはデータパケットのタイプを説明します。次のいずれかです：
ST_DATA = 0
通常のデータパケット。ソケットは接続状態にあり、送信するデータがあります。ST_DATA データパケットは常にデータペイロードを持っています。
ST_FIN = 1
接続を終了します。これは最後のデータパケットです。接続を閉じ、TCP FIN フラグに似ています。この接続のシーケンス番号は、このデータパケット内のシーケンス番号を超えることはありません。ソケットはこのシーケンス番号を eof_pkt として記録します。これにより、ソケットは ST_FIN データパケットを受信した後でも、まだ失われている可能性のあるデータパケットを待つことができます。
ST_STATE = 2
状態データパケット。データなしの ACK を伝送するために使用されます。ペイロードを含まないデータパケットは seq_nr を増加させません。
ST_RESET = 3
接続を強制終了します。TCP RST フラグに似ています。リモートホストはこの接続の状態を持っていません。それは時代遅れであり、終了すべきです。
ST_SYN = 4
TCP SYN フラグに似ており、このデータパケットは接続を開始します。シーケンス番号は 1 に初期化されます。接続 ID はランダム数に初期化されます。syn データパケットは特別であり、この接続上で送信されるすべての後続のデータパケット（ST_SYN の再送信を除く）は、接続 ID + 1 で送信されます。接続 ID は、他の端がその応答で使用すべき ID です。
ST_SYN を受信したときは、データパケットヘッダー内の ID を使用して新しいソケットを初期化する必要があります。ソケットの送信 ID は ID + 1 に初期化されるべきです。戻りチャネルのシーケンス番号はランダム数に初期化されます。もう一方は、ST_STATE データパケット（ACK のみ）を応答として必要とします。
seq_nr#
これはこのデータパケットのシーケンス番号です。TCP と異なり、uTP シーケンス番号はバイトではなくデータパケットを指します。シーケンス番号は、データパケットがアプリケーション層にどのように戻るべきかを他方に示します。
ack_nr#
これはデータパケットの送信者が別の方向で最後に受信したシーケンス番号です。
接続設定#
下の図は、接続を開始するための交換と状態を示しています。c.* はソケット自体の状態を示し、pkt.* はデータパケットヘッダー内のフィールドを示します。
initiating endpoint accepting endpoint
| c.state = CS_SYN_SENT |
| c.seq_nr = 1 |
| c.conn_id_recv = rand() |
| c.conn_id_send = c.conn_id_recv + 1 |
| |
| |
| ST_SYN |
| seq_nr=c.seq_nr++ |
| ack_nr=* |
| conn_id=c.rcv_conn_id |
| >-------------------------------------------> |
| c.receive_conn_id = pkt.conn_id+1 |
| c.send_conn_id = pkt.conn_id |
| c.seq_nr = rand() |
| c.ack_nr = pkt.seq_nr |
| c.state = CS_SYN_RECV |
| |
| |
| |
| |
| ST_STATE |
| seq_nr=c.seq_nr++ |
| ack_nr=c.ack_nr |
| conn_id=c.send_conn_id |
| <------------------------------------------< |
| c.state = CS_CONNECTED |
| c.ack_nr = pkt.seq_nr |
| |
| |
| |
| ST_DATA |
| seq_nr=c.seq_nr++ |
| ack_nr=c.ack_nr |
| conn_id=c.conn_id_send |
| >-------------------------------------------> |
| c.ack_nr = pkt.seq_nr |
| c.state = CS_CONNECTED |
| |
| | connection established
.. ..|.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..|.. ..
| |
| ST_DATA |
| seq_nr=c.seq_nr++ |
| ack_nr=c.ack_nr |
| conn_id=c.send_conn_id |
| <------------------------------------------< |
| c.ack_nr = pkt.seq_nr |
| |
| |
V V
接続はその conn_id ヘッダーで識別されます。新しい接続の接続 ID が既存の接続と衝突する場合、接続の試行は失敗します。なぜなら、ST_SYN データパケットは既存のストリーム内で予期しないものであり、無視されるからです。
パケット損失#
シーケンス番号が（seq_nr – cur_window）のデータパケットが未確認である場合（これは送信バッファ内で最も古いデータパケットであり、次のデータパケットが確認されることが予想されます）、しかしそのデータパケットを通過した 3 つ以上のデータパケット（選択的 ACK によって）によって、当該データパケットが失われたと見なされます。同様に、3 つの重複確認を受信した場合、ack_nr は + 1 が失われたと見なされます（そのシーケンス番号のデータパケットが送信されている場合）。
これは選択的確認にも適用されます。選択的確認メッセージで確認された各データパケットは、重複確認としてカウントされ、3 つ以上の場合は、少なくとも 3 つのデータパケットを含むデータパケットの再送信をトリガーする必要があります。
データパケットが失われた場合、max_window は 0.5 倍されて TCP をシミュレートします。
タイムアウト#
確認された各データパケットは、範囲（last_ack_nr、ack_nr] に落ちるか、選択的 ACK メッセージによって明示的に確認された場合、往復時間（RTT）および rtt_var（RTT 分散）測定値を更新するために適用されます。last_ack_nr は、ここで現在のデータパケットの前にソケットで受信された最後の ack_nr であり、ack_nr は現在受信されているデータパケット内のフィールドです。
RTT のみを対象としたデータパケットは一度だけ更新され、rtt_var も同様です。これにより、どのデータパケットが確認されたかを特定する問題が回避されます。
RTT は、以下の式を使用して rtt_var によって計算され、データパケットを確認するたびに更新されます：
delta = rtt - packet_rtt
rtt_var += (abs(delta) - rtt_var) / 4;
rtt += (packet_rtt - rtt) / 8;
ソケットに関連付けられたデータパケットのデフォルトのタイムアウトも、rtt および rtt_var の更新ごとに更新されます。これは次のように設定されます：
timeout = max(rtt + rtt_var * 4, 500);
ここで、タイムアウトはミリ秒単位で指定されます。すなわち、データパケットの最小タイムアウトは 1/2 秒です。
ソケットがデータパケットを送信または受信するたびに、タイムアウトカウンターが更新されます。前回のタイムアウトカウンターがリセットされた後、ミリ秒 timeout 内にデータパケットが到着しなかった場合、ソケットはタイムアウトをトリガーします。これにより、packet_size と max_window が最小のデータパケットサイズ（150 バイト）に設定されます。これにより、もう一度データパケットを送信できるようになり、ウィンドウサイズがゼロに減少した場合、ソケットが再び起動する方法となります。
初期タイムアウトは 1000 ミリ秒に設定され、その後上記の式に基づいて更新されます。タイムアウトされた各連続データパケットについて、タイムアウトは倍増します。
データパケットサイズ#
遅い輻輳リンクへの影響を最小限に抑えるために、uTP はデータパケットサイズを各データパケット 150 バイトに調整します。このように小さなデータパケットを使用する利点は、遅い上りリンクをブロックせず、シリアル化遅延が長くなることです。このように小さなデータパケットを使用する代償は、データパケットヘッダーのオーバーヘッドが大きくなることです。高速率では大きなデータパケットサイズを使用し、低速率では小さなデータパケットサイズを使用します。
輻輳制御#
uTP 輻輳制御の全体的な目標は、一方向バッファ遅延を主要な輻輳測定として使用し、データパケットの損失（TCP のように）を測定することです。重要なのは、データを送信する際に完全な送信バッファを使用しないようにすることです。DSL / ケーブルモデムにとっては、モデム内の送信バッファが通常数秒のデータを収容するスペースを持っているため、特に問題です。uTP（または任意のバックグラウンドトラフィックプロトコル）の理想的なバッファ利用率は、0 バイトのバッファ利用率で動作することです。つまり、他のトラフィックはいつでも送信でき、バックグラウンドトラフィックが送信バッファをブロックすることはありません。実際、uTP の目標遅延は 100 ミリ秒に設定されています。各ソケットの目標は、送信リンク上で 100 ミリ秒を超える遅延を決して見ないことです。そうであれば、スロットルを戻します。
これにより、uTP は任意の TCP トラフィックに屈服します。
これは、uTP を介して送信される各データパケットに高解像度のタイムスタンプを含めることで実現され、受信側は受信したデータパケット内のタイムスタンプとの間の差を計算します。この差をデータパケットの元の送信者（timestamp_difference_microseconds）にフィードバックします。この値は絶対値としては意味がありません。マシン内のクロックはおそらく同期しておらず、特にマイクロ秒単位の解像度に達していない場合、データパケットの伝送時間もこれらのタイムスタンプの差に含まれます。しかし、以前の値と比較して、この値は有用です。
各ソケットは、最後の 2 分間の最低値のスライディング最小値を保持します。この値は base_delay と呼ばれ、ホスト間の最小遅延の基準として使用されます。各データパケットのタイムスタンプ差から base_delay を引くことで、ソケット上の現在のバッファ遅延を測定できます。この測定は our_delay と呼ばれます。ノイズが多いですが、送信ウィンドウを増加させるか減少させるかを決定するためのドライバーとして使用されます。
CCONTROL_TARGET は、uTP が上りリンクで受け入れるバッファ遅延です。現在、遅延目標は 100 ミリ秒に設定されており、off_target は実際に測定された遅延と目標遅延の距離（CCONTROL_TARGET – our_delay に基づいて計算）です。
ソケット構造内のウィンドウサイズは、接続上で合計で未確認のバイト数を持つ可能性があることを指定します。送信速度はこのウィンドウサイズに直接関連しています。伝送中のバイト数が多いほど、送信速度が速くなります。コード内では、ウィンドウサイズは max_window と呼ばれます。そのサイズはおおよそ次の式によって制御されます：
delay_factor = off_target / CCONTROL_TARGET;
window_factor = outstanding_packet / max_window;
scaled_gain = MAX_CWND_INCREASE_PACKETS_PER_RTT * delay_factor * window_factor;
ここで、最初の要素は off_target を目標遅延単位にスケーリングします。
次に、scaled_gain を max_window に追加します：
max_window += scaled_gain;
off_target が 0 より大きい場合、ウィンドウは小さくなり、目標からの偏差が 0 より小さい場合、ウィンドウは大きくなります。
max_window が 0 より小さい場合は、0 に設定されます。ウィンドウサイズがゼロであることは、ソケットがデータパケットを送信できないことを示します。この状態では、ソケットはタイムアウトをトリガーし、ウィンドウサイズを 1 データパケットサイズに強制し、データパケットを送信します。詳細については、タイムアウトに関するセクションを参照してください。