kcp
v1.7
README in English
KCP is a fast and reliable protocol that can reduce the average delay by 30%-40% and reduce the maximum delay by three times at the cost of 10%-20% more bandwidth than TCP. Pure algorithm implementation is not responsible for the sending and receiving of underlying protocols (such as UDP). Users need to define the sending method of lower-layer data packets and provide it to KCP in the form of callback. Even the clock needs to be passed in externally, and there will not be any system call internally.
The entire protocol only has two source files, ikcp.h and ikcp.c, which can be easily integrated into the user's own protocol stack. Maybe you have implemented a P2P or a UDP-based protocol but lack a complete and reliable ARQ protocol implementation. Then simply copy these two files to the existing project, write a few lines of code, and you can use it.
TCP is designed for traffic (how many KB of data can be transmitted per second), and the emphasis is on making full use of bandwidth. KCP is designed for flow rate (how long it takes for a single data packet to be sent from one end to another). It exchanges 10%-20% of bandwidth waste for a transmission speed that is 30%-40% faster than TCP. The TCP channel is a large canal with a slow flow rate but a large flow rate per second, while the KCP channel is a small rapid with rapid flow. KCP has two types: normal mode and fast mode. The result of increasing the flow rate is achieved through the following strategies:
The TCP timeout calculation is RTOx2. If you lose three packets in a row, it will become RTOx8, which is very scary. However, after KCP starts the fast mode, it is not x2, but only x1.5 (experiments have proved that the value of 1.5 is relatively good), which improves the transmission speed.
When TCP loses a packet, it will retransmit all data starting from the lost packet. KCP retransmits selectively and only retransmits the truly lost data packets.
The sender sent several packets 1, 2, 3, 4, and 5, and then received the ACK from the remote end: 1, 3, 4, 5. When receiving ACK3, KCP knew that 2 was skipped once, and received When ACK4 is received, it is known that packet 2 has been skipped twice. At this time, it can be considered that packet number 2 is lost. There is no need to wait for the timeout and packet number 2 can be directly retransmitted, which greatly improves the transmission speed when packets are lost.
In order to make full use of bandwidth, TCP delays sending ACK (NODELAY is useless). In this way, the timeout calculation will calculate a larger RTT time, which prolongs the judgment process when packet loss occurs. Whether KCP's ACK is sent delayed can be adjusted.
There are two types of ARQ model responses, UNA (all packets before this number have been received, such as TCP) and ACK (packets with this number have been received). Using UNA alone will cause all retransmissions, while using ACK alone will cause too high a loss cost. In the past, protocols were all about choosing one of the two, but in the KCP protocol, except for individual ACK packets, all packets have UNA information.
KCP normal mode uses the same fair concession rule as TCP, that is, the sending window size is determined by four factors: the sending buffer size, the remaining receiving buffer size at the receiving end, packet loss concession and slow start. However, when transmitting small data with high timeliness requirements, you can choose to skip the last two steps through configuration and only use the first two items to control the sending frequency. At the expense of partial fairness and bandwidth utilization, the effect of smooth transmission can be achieved even when BT is turned on.
You can download and install kcp using the vcpkg library manager:
git clone https://github.com/Microsoft/vcpkg.git
cd vcpkg
./bootstrap-vcpkg.sh
./vcpkg integrate install
./vcpkg install kcp
The kcp library in vcpkg is kept up to date by Microsoft team members and community contributors. If the version is out of date, please create an issue or raise a PR on the vcpkg repository.
Create KCP object:
// 初始化 kcp对象，conv为一个表示会话编号的整数，和tcp的 conv一样，通信双
// 方需保证 conv相同，相互的数据包才能够被认可，user是一个给回调函数的指针
ikcpcb *kcp = ikcp_create(conv, user);Set callback function:
// KCP的下层协议输出函数，KCP需要发送数据时会调用它
// buf/len 表示缓存和长度
// user指针为 kcp对象创建时传入的值，用于区别多个 KCP对象
int udp_output ( const char *buf, int len, ikcpcb *kcp, void *user)
{
....
}
// 设置回调函数
kcp->output = udp_output;Call update in a loop:
// 以一定频率调用 ikcp_update来更新 kcp状态，并且传入当前时钟（毫秒单位）
// 如 10ms调用一次，或用 ikcp_check确定下次调用 update的时间不必每次调用
ikcp_update (kcp, millisec);Enter a lower layer packet:
// 收到一个下层数据包（比如UDP包）时需要调用：
ikcp_input (kcp, received_udp_packet, received_udp_size);After processing the output/input of the lower layer protocol, the KCP protocol can work normally. Use ikcp_send to send data to the remote end. The other end uses ikcp_recv(kcp, ptr, size) to receive data.
The default mode of the protocol is a standard ARQ, and various acceleration switches need to be turned on through configuration:
Working mode:
int ikcp_nodelay (ikcpcb *kcp, int nodelay, int interval, int resend, int nc)Maximum window:
int ikcp_wndsize (ikcpcb *kcp, int sndwnd, int rcvwnd);This call will set the maximum sending window and maximum receiving window size of the protocol, which defaults to 32. This can be understood as TCP's SND_BUF and RCV_BUF, but the units are different. The SND/RCV_BUF unit is bytes, and this unit is packets.
Maximum transmission unit:
The pure algorithm protocol is not responsible for detecting the MTU. The default mtu is 1400 bytes. You can use ikcp_setmtu to set this value. This value will affect the maximum transmission unit when combining and fragmenting data packets.
Minimum RTO:
Whether it is TCP or KCP, there is a minimum RTO limit when calculating RTO. Even if the calculated RTO is 40ms, since the default RTO is 100ms, the protocol can only detect packet loss after 100ms. In fast mode, it is 30ms. This can be changed manually. value:
kcp->rx_minrto = 10 ;The use and configuration of the protocol are very simple. In most cases, you can basically use it after reading the above content. If you need further fine-grained control, such as changing the memory allocator of KCP, or you need to more efficiently schedule KCP connections on a large scale (such as more than 3500), or how to better integrate with TCP, then you can continue reading:
Related reading: "Genshin Impact" is also using KCP to speed up game news
KCP has been successfully run on multiple projects with hundreds of millions of users, providing them with a more responsive and silky network experience.
Welcome to tell us more cases
If the network never gets stuck, then KCP/TCP will behave similarly, but the network itself is unreliable, and packet loss and jitter are unavoidable (otherwise, why would we need various reliable protocols)? When compared directly in an almost ideal environment such as the intranet, everyone is almost the same. However, when placed on the public network, placed on a 3G/4G network, or using intranet packet loss simulation, the gap becomes obvious. The public network has an average packet loss of close to 10% during peak periods, and it is even worse under WiFi/3g/4g, which will cause transmission delays.
Thanks to zhangyuan, the author of asio-kcp, for a horizontal evaluation of KCP, enet, and udt. The conclusions are as follows:
For details, see: Horizontal comparison and evaluation data provide more guidance for those who are hesitant to choose.
The massive multiplayer game server engine SpatialOS made the same evaluation as TCP/RakNet after integrating the KCP protocol:
We compared the response time when maintaining 50 characters at the same time with a refresh rate of 60 Hz on the server side. Please see the detailed comparison report:
In recent years, online games and various social networks have grown exponentially. Regardless of online games or various interactive social networks, the interactivity and complexity are increasing rapidly, and they all need to deliver data simultaneously in a very short time. To a large number of users, transmission technology will naturally become an important factor restricting future development, and various well-known transmission protocols in the open source world, such as raknet/enet For example, when a release is made, the entire protocol stack is released together. This form is not conducive to diversification. My project can only choose to use you or not. It is difficult to choose "partially use you", but you design a set of protocol stacks. No matter how good it is, it is very difficult to meet various needs from different angles.
Therefore, KCP's method is to "disassemble" the protocol stack so that everyone can flexibly adjust and assemble it according to project needs. You can add a layer of reed solomon's erasure code below for FEC, and a layer above it for RC4/Salsa20. For stream encryption, an asymmetric key exchange is designed at the handshake, and a dynamic routing system is built at the underlying UDP transport layer to detect multiple paths at the same time and select the best path for transmission. These different "protocol units" can be freely combined as needed like building blocks to ensure "simplicity" and "detachability", so that they can flexibly adapt to changing business needs. If any module is not good, just replace it.
Future transmission solutions must be deeply customized according to usage scenarios, so we give everyone a "protocol unit" that can be freely combined to facilitate integration into your own protocol stack.
For more information, please see the Success Stories.
Author: Lin Wei (skywind3000)
Welcome to follow me on: personal blog and Twitter.
In my many years of development experience, I have always liked to study and solve some bottleneck problems in programs. In my early years, I liked game development. I followed "VGA Programming" to do game graphics, and read Michael Abrash's "Graphics Program Developer's Guide" to do soft rendering. I like to play with some code that can squeeze out the CPU and run faster. After joining the work, my interest shifted to server-side and network-related technologies.
In 2007, after making several traditional games, I began to study the synchronization problem of fast-action games. During this period, I wrote many articles. I was one of the earliest people in China to study synchronization problems. However, I found that no matter how to solve synchronization, we need to do something in terms of network transmission. After leaving the game and switching to the Internet, I also found that many fields have this need, so I started to spend time in the field of network transmission, trying to implement some conservative and reliable protocols based on UDP, and imitating the code of BSD Lite 4.4 to implement some TCP-like protocol, I found it quite interesting, and then implemented some toys related to P2P and dynamic routing networks. The KCP protocol was born in 2011. It is basically one of several toys made by itself in terms of transmission.
The author of Kcptun, xtaci, is my college classmate. We both major in communications, and we often study together how to optimize transmission.
Welcome to use Alipay to scan the QR code above to donate to this project. Donations will be used to continuously optimize the KCP protocol and improve documentation.
Thanks to: Mingming, Xingzi, Jin, Fan, Yanzhao, Binquan, Xiaodan, Yu Zheng, Hu, Shenggan, Xu Wei, Wang Chuan, Zhao Gangqiang, Hu Zhifeng, Wan Xinchao, He Xinchao, Liu Yang, Hou Xianhui, Wu Peiyi, Hua Bin, Rutao, Hu Jian. . . (I’m sorry I didn’t record the earlier list) We are waiting for the donations and support from our classmates.
Welcome to pay attention
KCP communication group: 364933586 (QQ group number), KCP integration, tuning, network transmission and related technical discussions
Gitter group: https://gitter.im/skywind3000/KCP
blog: http://www.skywind.me
This project exists thanks to all the people who contribute.
