kcp - ⚡ KCP - 高速で信頼性の高いARQプロトコル

(:zap: KCP - A Fast and Reliable ARQ Protocol)

Created at: 2014-12-27 00:46:34
Language: C
URL: https://github.com/skywind3000/kcp
License: MIT

KCP - 高速で信頼性の高いARQプロトコル

電源 ビルドステータス オープンコレクティブの支援者 オープンコレクティブのスポンサー

英語の README

簡単な紹介

KCPは高速で信頼性の高いプロトコルであり、平均遅延の10%〜20%の削減と最大遅延の30倍の削減と引き換えに、TCPと比較して帯域幅の40%〜<>%を浪費します。 純粋なアルゴリズムの実装は、基になるプロトコル(UDPなど)の送受信を担当せず、ユーザーは下位層パケットの送信方法を定義し、コールバックの形式でKCPに提供する必要があります。 クロックも外部に渡す必要があり、内部では単一のシステムコールはありません。

プロトコル全体には、ikcp.hとikcp.cの2つのソースファイルしかなく、ユーザー独自のプロトコルスタックに簡単に統合できます。 P<>PまたはUDPベースのプロトコルを実装していて、ARQの信頼できるプロトコル実装の完全なセットが不足している場合は、これら<>つのファイルを既存のプロジェクトにコピーし、<>行のコードを少し記述するだけで使用できます。

技術的特徴

TCPはトラフィック(毎秒何キロバイトのデータを転送できるか)用に設計されており、帯域幅を最大限に活用することにこだわっています。 一方、KCPは、流量(10つのパケットが一方の端からもう一方の端に移動するのにかかる時間)に合わせて設計されており、帯域幅が20%〜30%無駄になるという犠牲を払って、TCPよりも40%〜<>%高速です。 TCPチャネルは、流量は遅いが毎秒の流量が多い大きな運河ですが、KCPは乱流のある小さな急流です。 KCPは通常モードと高速モードで利用可能であり、流量を増やす結果を達成するために次の戦略が使用されます。

RTOの倍増と非倍増:

TCPタイムアウトの計算はRTOx2であるため、パケットを8回連続で失うとRTOx2になり、非常に恐ろしいことであり、KCPは高速モードを開始した後のx1ではなくx5.1(実験では5.<>の値が比較的良好であることが証明されています)であり、伝送速度が向上します。

選択的再送信と完全再送信:

TCPパケット損失は、ドロップされたパケットからすべてのデータを再送信し、KCPは選択的再送信され、失われたパケットのみをファックスします。

迅速な再送信:

送信者は、いくつかのパケット1、2、3、4、5を送信し、リモートエンドのACKを受信します:1、3、4、5、ACK3が受信されると、KCPは2が1回スキップされたことを認識し、ACK4を受信すると、2が2回スキップされたことを認識し、この時点で2号が失われたと見なすことができ、タイムアウトを待たずに、パケット番号2を直接再送信し、パケット損失時の伝送速度を大幅に向上させます。

遅延ACKと非遅延ACK:

帯域幅を最大限に活用するために、TCPはACKの送信を遅らせる(NODELAYは役に立たない)ため、タイムアウト計算では大きなRTT時間が計算され、パケット損失時の判断プロセスが長くなります。 KCP の ACK を遅延させるかどうかは調整できます。

UNA 対 ACK + UNA:

ARQモデルの応答には、UNA(TCPなど、この番号より前に受信されたすべてのパケット)とACK(番号付きのパケットが受信された)の2種類があり、UNAのみを使用するとすべての再送信が発生し、ACKのみを使用するとコストが高すぎるため、前のプロトコルは2つのうちの1つであり、KCPプロトコルでは、個別のACKパッケージを除いて、すべてのパケットにUNA情報があります。

非譲許的フロー制御:

KCP の通常モードは、TCP のような公平バックオフ規則を使用します、つまり、送信ウィンドウのサイズは、送信キャッシュのサイズ、受信側の残りの受信キャッシュのサイズ、パケット損失、スロースタートの 4 つの要素によって決まります。 ただし、適時性の高い要件を持つ小さなデータを転送する場合は、構成の最後の2つのステップをスキップし、最初の2つのステップのみを使用して送信周波数を制御することを選択できます。 部分的な公平性と帯域幅使用率を犠牲にして、BTをオンにした状態でのスムーズな送信の効果と引き換えに。

クイックインストール

vcpkg ライブラリマネージャーを使用して kcp をダウンロードしてインストールできます。

git clone https://github.com/Microsoft/vcpkg.git
cd vcpkg
./bootstrap-vcpkg.sh
./vcpkg integrate install
./vcpkg install kcp

vcpkg の kcp ライブラリは、マイクロソフトのチーム メンバーとコミュニティの共同作成者によって最新の状態に保たれています。 バージョンが古い場合は、問題を作成するか、vcpkg リポジトリに PR を提出してください。

基本的な使い方

  1. KCP オブジェクトを作成します。

    // 初始化 kcp对象，conv为一个表示会话编号的整数，和tcp的 conv一样，通信双
// 方需保证 conv相同，相互的数据包才能够被认可，user是一个给回调函数的指针
ikcpcb *kcp = ikcp_create(conv, user);

  2. コールバック関数を設定します。

    // KCP的下层协议输出函数，KCP需要发送数据时会调用它
// buf/len 表示缓存和长度
// user指针为 kcp对象创建时传入的值，用于区别多个 KCP对象
int udp_output(const char *buf, int len, ikcpcb *kcp, void *user)
{
  ....
}
// 设置回调函数
kcp->output = udp_output;

  3. ループ呼び出しの更新:

    // 以一定频率调用 ikcp_update来更新 kcp状态，并且传入当前时钟（毫秒单位）
// 如 10ms调用一次，或用 ikcp_check确定下次调用 update的时间不必每次调用
ikcp_update(kcp, millisec);

  4. ダウンレベルのパケットを入力します。

    // 收到一个下层数据包（比如UDP包）时需要调用：
ikcp_input(kcp, received_udp_packet, received_udp_size);

    下位層プロトコルの出力/入力を処理した後、KCPプロトコルは次のように正常に動作ikcp_send リモート エンドはデータを送信します。 もう一方の端は、ikcp_recv (kcp、ptr、サイズ) を使用してデータを受信します。

プロトコル構成

プロトコルのデフォルトモードは標準のARQであり、設定によってアクセラレーションスイッチをオンにする必要があります。

  1. 作業モード:

    int ikcp_nodelay(ikcpcb *kcp, int nodelay, int interval, int resend, int nc)
    • nodelay: nodelay モードが有効かどうか、0 は有効ではありません。 1 有効。
    • interval: プロトコルの内部操作のミリ秒単位の間隔 (10 ミリ秒や 20 ミリ秒など)
    • resent:高速再送信モード、デフォルト0オフ、2を設定できます(2つのACKクロッシングが直接再送信されます)
    • nc:フロー制御をオフにするかどうか、デフォルトは0がオフにならないことを意味し、1がオフにすることを意味します。
    • 通常モード: ikcp_nodelay(kcp, 0, 40, 0, 0);
    • スピードモード:ikcp_nodelay(kcp、1、10、2、1);

  2. 最大ウィンドウ:

    int ikcp_wndsize(ikcpcb *kcp, int sndwnd, int rcvwnd);

    この呼び出しにより、プロトコルの最大送信ウィンドウと最大受信ウィンドウ サイズが設定されます (既定値は 32)。 これはTCPのSND_BUFとRCV_BUFとして理解できるが、単位は異なるSND/RCV_BUF単位はバイトであり、この単位はパケットである。

  3. 最大伝送単位:

    純粋なアルゴリズムプロトコルはMTUのプローブを担当せず、デフォルトのMTUは1400バイトであり、値はikcp_setmtuを使用して設定できます。 この値は、パケット統合およびフラグメンテーション時の最大伝送単位に影響します。

  4. 最小 RTO :

    RTOを計算するのがTCPであろうとKCPであろうと、計算されたRTOが40msであっても、デフォルトのRTOは100msであるため、プロトコルは100ms、高速モードでは30ms後にパケット損失を検出できるため、手動で値を変更できます。

    kcp->rx_minrto = 10;

ドキュメント インデックス

プロトコルの使い方や設定は非常に簡単で、基本的には上記の内容を読んだ上で使えることがほとんどです。 KCPのメモリアロケータを変更するなど、さらにきめ細かい制御が必要な場合、KCPリンクをより効率的かつ大規模にスケジュールする必要がある場合(3500以上など)、またはTCPとの統合を改善する方法がある場合は、読み続けることができます。

オープンソースのケース

  • kcptun:kcp-goに基づく高速リモートポートフォワーディング(トンネリング)、ssh -Dを使用すると、シャドーソックスよりもスムーズにオンラインビデオを視聴できます。
  • ドッグトンネル:GOが開発したネットワークトンネルは、KCPを使用して伝送速度を大幅に向上させ、KCPのGOバージョンを移植しました
  • v2ray:有名なプロキシソフトウェア、シャドウソックスの交換、1.17以降の統合kcpプロトコル、UDP送信の使用、パケット特性なし。
  • HPソケット:HPソケット、高性能ネットワーク通信フレームワーク。
  • FRP:イントラネットサービスの公開を外部ネットワークサーバーにマッピングする高性能イントラネット浸透リバースプロキシソフトウェア。
  • asio-kcp:KCPの完全なUDPネットワークライブラリを使用して、UDPベースのリンク状態管理、セッション制御、KCPプロトコルスケジューリングなどを完全に実装します。
  • kcp-java: KCP プロトコル実装の Java バージョン。
  • kcp-netty: netty をベースにした kcp の Java 言語実装。
  • JAVA-KCP: NETTY 実装に基づく KCP の JAVA バージョン (FEC 機能を含む)
  • csharp-kcp: dotNetty に基づく KCP の csharp バージョン (fec 関数を含む)
  • kcp-cpp: アプリケーション内の単純なライブラリとしての KCP のマルチプラットフォーム (Windows、MacOS、Linux) C++ 実装。 すべてのプラットフォームのソケット処理とヘルパー関数が含まれています。
  • kcp-perl: kcp の Perl 実装で、オブジェクト指向で Perl ライクです。
  • kcp-go: UDP セッション管理の簡単な実装を含む、kcp の高セキュリティの GO 実装で、その後の開発のためのベースライブラリとして使用できます。
  • kcp-csharp: kcp の csharp 移植版にはコールバック管理機能も含まれており、上記の kcp-go サーバに接続することができます。
  • kcp-csharp: 新しいバージョンの KCP の CSHARP 移植版。 スレッドセーフ、実行時にALLOCなし、GCへの圧力なし。
  • kcp2k:オプションのサーバー/クライアントを上に配置したC#への行ごとの変換。
  • kcp-rs: KCP の錆びたポート
  • kcp-rust: 新しいバージョンの KCP 用の rust ポート
  • Tokio-kcp: Rust Tokio の kcp 統合
  • kcp-rust-native: Rust の kcp バインディング
  • lua-kcp: Lua サーバー用の KCP の Lua 拡張
  • ノード kcp: ノード js の KCP インターフェイス
  • nysocks:libuv実装に基づくノードアドオン、プロキシサービスのnodejsバージョンを提供し、クライアントアクセスはSOCKS5とssをサポートします
  • Shadowsocks-android:Android用Shadowsocksはkcptunを統合し、kcpプロトコルを使用してシャドウソックスを高速化します。
  • kcpuv: libuv を使用して開発された kcpuv ライブラリはまだデモ段階にあります
  • ランタン:より良いVPN、Github 50000,<>スター、kcpgoで加速
  • rpcx: RPC フレームワーク、1000+ つ星、kcpgo を使用して RPC を高速化する
  • xkcptun: c で実装された kcptun は、主に OpenWrt, LEDE によって開発されたルータプロジェクトに使用されます。
  • et-frame:C#フロントエンドとバックエンドのフレームワーク(フロントエンドunity3d)、ゲームの開発、フロントエンドとバックエンドのkcpプロトコルの実装のためのC#の統一された使用
  • yasio:任意のクライアントプログラムに焦点を当てたクロスプラットフォームの非同期ソケットライブラリ、使いやすく、同じAPI操作KCP/TCP/UDP、パフォーマンステスト結果:ベンチマークポンプ。
  • gouxp: Go を使用して、暗号化と復号化、使いやすい FEC サポートなど、コールバックに基づく KCP 開発パッケージを実装します。

ビジネスケース

  • 原神:ミハヨウの原神はKCPを使用して、ゲームメッセージの送信時間を短縮し、操作体験を向上させます。
  • SpatialOS:BigWorldの後継である大規模マルチプレイヤー分散ゲームサーバーサイドエンジンで、KCPを使用してデータ転送を高速化します。
  • 西山 寿:ゲームデータの高速化にはKCPを使います。
  • CC:NetEase CCはkcpを使用してビデオストリーミングを高速化し、滑らかさを効果的に改善します
  • BOBO:NetEase BOBOはkcpを使用してストリーマーストリーミングを高速化します
  • UU: NetEase UU アクセラレータは、リモート伝送アクセラレーションに KCP/KCPTUN を使用します。
  • Alibaba Cloud: Alibaba Cloud のビデオ伝送アクセラレーションサービス (GRTN) は、KCP を使用してオーディオおよびビデオデータ伝送を最適化し、KCP はダイナミックアクセラレーション製品にも使用されます。
  • サイファンアクセラレーション:KCPは、ファイル転送とビデオストリーミングを高速化するために使用され、台湾のストリーマーによるストリーミングのスムーズさを最適化します。
  • 明日の帝国:ゲームK17用のGoogle Playは、KCPを使用してゲームメッセージングを加速し、世界中のプレーヤーを接続します
  • フェアリーウォーズ:4399のMOBAゲーム、KCPを使用してゲームの同期を最適化する

KCPは、数億人のユーザーがいる複数のプロジェクトで正常に実行され、より応答性が高く、シルキーなWebエクスペリエンスを提供します。

より多くのケースを歓迎します

プロトコルの比較

ネットワークがスタックしない場合、KCP / TCPは同様に動作しますが、ネットワーク自体は信頼できず、パケット損失とジッターを回避できません(そうでなければ、なぜさまざまな信頼できるプロトコルが必要なのですか)。 イントラネットのほぼ理想的な環境では、誰もが似ていますが、パブリックネットワークに配置するか、3G / 4Gネットワ ークの場合に配置するか、イントラネットパケット損失シミュレーションを使用すると、ギャップは明らかです。 パブリックネットワークでは、ピーク時の平均パケット損失が10%近くあり、WiFi / 3G / 4Gではさらに悪化し、送信がカードになります。

asio-kcpの著者であるZhangyuanのおかげで、KCPとenet、udtの水平レビューを行い、結論は次のとおりです。

  • ASIO-KCPは、無線LANおよび電話ネットワーク(3G、4G)で優れたパフォーマンスを発揮します。
  • kcpは、リアルタイムpvpゲームの最初の選択肢です。
  • ネットワークの遅延が発生した場合、遅延は 1 秒未満です。 ラグが発生した場合のenetの3倍優れています。
  • enetは、ゲームで2秒のラグが許可されている場合に適しています。
  • UDTは悪い考えです。 それは常にサーバル秒以上の遅れのひどい状況に沈みます。 そして、回復は期待されていません。
  • enet has the problem of lack of doc. And it has lots of functions that you may intrest.
  • kcp's doc is chinese. Good thing is the function detail which is writen in code is english. And you can use asio_kcp which is a good wrap.
  • The kcp is a simple thing. You will write more code if you want more feature.
  • UDT has a perfect doc. UDT may has more bug than others as I feeling.

具体见：横向比较 和 评测数据，为犹豫选择的人提供了更多指引。

大型多人游戏服务端引擎 SpatialOS 在集成 KCP 协议后做了同 TCP/RakNet 的评测：

对比了在服务端刷新率为 60 Hz 同时维护 50 个角色时的响应时间，详细对比报告见：

关于协议

近年来，网络游戏和各类社交网络都在成几何倍数的增长，不管网络游戏还是各类互动社交网络，交互性和复杂度都在迅速提高，都需要在极短的时间内将数据同时投递给大量用户，因此传输技术自然变为未来制约发展的一个重要因素，而开源界里各种著名的传输协议，如 raknet/enet 之类，一发布都是整套协议栈一起发布，这种形式是不利于多样化的，我的项目只能选择用或者不用你，很难选择 “部分用你”，然而你一套协议栈设计的再好，是非常难以满足不同角度的各种需求的。

因此 KCP 的方式是把协议栈 “拆开”，让大家可以根据项目需求进行灵活的调整和组装，你可以下面加一层 reed solomon 的纠删码做 FEC，上面加一层类 RC4/Salsa20 做流加密，握手处再设计一套非对称密钥交换，底层 UDP 传输层再做一套动态路由系统，同时探测多条路径，选最好路径进行传输。这些不同的 “协议单元” 可以像搭建积木一般根据需要自由组合，保证 “简单性” 和 “可拆分性”，这样才能灵活适配多变的业务需求，哪个模块不好，换了就是。

未来传输方面的解决方案必然是根据使用场景深度定制的，因此给大家一个可以自由组合的 “协议单元” ，方便大家集成在自己的协议栈中。

For more information, please see the Success Stories.

关于作者

作者：林伟 (skywind3000)

欢迎关注我的：twitter 和 zhihu。

我在多年的开发经历中，一直都喜欢研究解决程序中的一些瓶颈问题，早年喜欢游戏开发，照着《VGA编程》来做游戏图形，读 Michael Abrash 的《图形程序开发人员指南》做软渲染器，爱好摆弄一些能够榨干 CPU 能够运行更快的代码，参加工作后，兴趣转移到服务端和网络相关的技术。

2007年、いくつかの伝統的なゲームをやった後、高速アクションゲームの同期問題を研究し始め、その間に多くの記事を書き、中国で最も早く同期問題を研究したと考えられていましたが、同期を解決する方法に関係なく、ネットワーク伝送に突破口を開き、その後、ゲームを離れてインターネットに切り替え、多くの地域がこの需要を持っていることにも気づき、ネットワーク伝送の分野で時間を費やし始め、BSD Lite 4.4をモデルにしたUDPに基づく保守的で信頼性の高いプロトコルを実装しようとしました。 このコードは、私が興味深いと思うTCPのようなプロトコルをいくつか実装し、次にいくつかのP2Pおよび動的ルーティングネットワーク関連のおもちゃを実装します。 KCPプロトコルは2011年に誕生し、基本的に独自の送信に関して作られたいくつかのおもちゃの<>つです。

Kcptunの作者であるxtaciは私の大学の同級生であり、私たちはコミュニケーションを研究し、送信を最適化する方法についてしばしば一緒に働きました。

寄付は大歓迎です

Alipayを使用してプロジェクトに寄付することを歓迎します

Alipayを使用して上記のQRコードをスキャンしてプロジェクトに寄付することを歓迎します。 寄付金は、KCPプロトコルを継続的に最適化し、ドキュメントを改善するために使用されます。

ありがとう:ミンミン、シンザイ、ジン、ファン、フージャオ、ビンクアン、シャオダン、ユーチェン、フー、シェンダーン、シューウェイ、ワンチュアン、チャオガンチャン、フージフェン、ワンシンチャオ、ホーシンチャオ、リウヤン、ホウシアンフイ、ウーペイイー、フアビン、ルータオ、フージェン... (以前のリストを記録せずに申し訳ありません)そして他の学生の寄付と支援。

フォローへようこそ

KCP通信グループ:364933586(QQグループ番号)、KCP統合、チューニング、ネットワーク伝送および関連する技術的議論

ギッターグループ:https://gitter.im/skywind3000/KCP

ブログ: http://www.skywind.me

貢献

このプロジェクトは、貢献するすべての人々のおかげで存在します。

About

Author：skywind3000

Watch
Star
Fork