Network TCP协议


TCP三次握手详解

在后端相关岗位的入职面试中,三次握手的出场频率非常的高,甚至说它是必考题也不为过。一般的答案都是说客户端如何发起 SYN 握手进入 SYN_SENT 状态,服务器响应 SYN 并回复 SYNACK,然后进入 SYN_RECV,……

其实三次握手在内核的实现中,并不只是简单的状态的流转,还包括半连接队列、syncookie、全连接队列、重传计时器等关键操作。

在基于 TCP 的服务开发中,三次握手的主要流程图如下。

服务器中的核心代码是创建 socket,绑定端口,listen 监听,最后 accept 接收客户端的请求。

//服务端核心代码
int main(int argc, char const *argv[])
{
 int fd = socket(AF_INET, SOCK_STREAM, 0);
 bind(fd, ...);
 listen(fd, 128);
 accept(fd, ...);
 ...
}

客户端的相关代码是创建 socket,然后调用 connect 连接 server。

//客户端核心代码
int main(){
 fd = socket(AF_INET,SOCK_STREAM, 0);
 connect(fd, ...);
 ...
}

围绕这个三次握手图,以及客户端,服务端的核心代码,我们来深度探索一下三次握手过程中的内部操作。我们从和三次握手过程关系比较大的 listen 讲起!

一、服务器的 listen

我们都知道,服务器在开始提供服务之前都需要先 listen 一下。但 listen 内部究竟干了啥,我们平时很少去琢磨。

今天就让我们详细来看看,直接上一段 listen 时执行到的内核代码。

//file: net/core/request_sock.c
int reqsk_queue_alloc(struct request_sock_queue *queue,
     unsigned int nr_table_entries)
{
 size_t lopt_size = sizeof(struct listen_sock);
 struct listen_sock *lopt;

 //计算半连接队列的长度
 nr_table_entries = min_t(u32, nr_table_entries, sysctl_max_syn_backlog);
 nr_table_entries = ......

 //为半连接队列申请内存
 lopt_size += nr_table_entries * sizeof(struct request_sock *);
 if (lopt_size > PAGE_SIZE)
  lopt = vzalloc(lopt_size);
 else
  lopt = kzalloc(lopt_size, GFP_KERNEL);

 //全连接队列头初始化
 queue->rskq_accept_head = NULL;

 //半连接队列设置
 lopt->nr_table_entries = nr_table_entries;
 queue->listen_opt = lopt;
 ......
}

在这段代码里,内核计算了半连接队列的长度。然后据此算出半连接队列所需要的实际内存大小,开始申请用于管理半连接队列对象的内存(半连接队列需要快速查找,所以内核是用哈希表来管理半连接队列的,具体在 listen_sock 下的 syn_table 下)。最后将半连接队列挂到了接收队列 queue 上。

另外 queue->rskq_accept_head 代表的是全连接队列,它是一个链表的形式。在 listen 这里因为还没有连接,所以将全连接队列头 queue->rskq_accept_head 设置成 NULL。

当全连接队列和半连接队列中有元素的时候,他们在内核中的结构图大致如下。

在服务器 listen 的时候,主要是进行了全/半连接队列的长度限制计算,以及相关的内存申请和初始化。全/连接队列初始化了以后才可以相应来自客户端的握手请求。

二、客户端 connect

客户端通过调用 connect 来发起连接。在 connect 系统调用中会进入到内核源码的 tcp_v4_connect。

//file: net/ipv4/tcp_ipv4.c
int tcp_v4_connect(struct sock *sk, struct sockaddr *uaddr, int addr_len)
{
 //设置 socket 状态为 TCP_SYN_SENT
 tcp_set_state(sk, TCP_SYN_SENT);

 //动态选择一个端口
 err = inet_hash_connect(&tcp_death_row, sk);

 //函数用来根据 sk 中的信息,构建一个完成的 syn 报文,并将它发送出去。
 err = tcp_connect(sk);
}

在这里将完成把 socket 状态设置为 TCP_SYN_SENT。再通过 inet_hash_connect 来动态地选择一个可用的端口后,进入到 tcp_connect 中。

//file:net/ipv4/tcp_output.c
int tcp_connect(struct sock *sk)
{
 tcp_connect_init(sk);

 //申请 skb 并构造为一个 SYN 包
 ......

 //添加到发送队列 sk_write_queue 上
 tcp_connect_queue_skb(sk, buff);

 //实际发出 syn
 err = tp->fastopen_req ? tcp_send_syn_data(sk, buff) :
    tcp_transmit_skb(sk, buff, 1, sk->sk_allocation);

 //启动重传定时器
 inet_csk_reset_xmit_timer(sk, ICSK_TIME_RETRANS,
      inet_csk(sk)->icsk_rto, TCP_RTO_MAX);
}

在 tcp_connect 申请和构造 SYN 包,然后将其发出。同时还启动了一个重传定时器,该定时器的作用是等到一定时间后收不到服务器的反馈的时候来开启重传。在 3.10 版本中首次超时时间是 1 s,一些老版本中是 3 s。

总结一下,客户端在 connect 的时候,把本地 socket 状态设置成了 TCP_SYN_SENT,选了一个可用的端口,接着发出 SYN 握手请求并启动重传定时器

三、服务器响应 SYN

在服务器端,所有的 TCP 包(包括客户端发来的 SYN 握手请求)都经过网卡、软中断,进入到 tcp_v4_rcv。在该函数中根据网络包(skb)TCP 头信息中的目的 IP 信息查到当前在 listen 的 socket。然后继续进入 tcp_v4_do_rcv 处理握手过程。

//file: net/ipv4/tcp_ipv4.c
int tcp_v4_do_rcv(struct sock *sk, struct sk_buff *skb)
{
 ...
 //服务器收到第一步握手 SYN 或者第三步 ACK 都会走到这里
 if (sk->sk_state == TCP_LISTEN) {
  struct sock *nsk = tcp_v4_hnd_req(sk, skb);
 }

 if (tcp_rcv_state_process(sk, skb, tcp_hdr(skb), skb->len)) {
  rsk = sk;
  goto reset;
 }
}

在 tcp_v4_do_rcv 中判断当前 socket 是 listen 状态后,首先会到 tcp_v4_hnd_req 去查看半连接队列。服务器第一次响应 SYN 的时候,半连接队列里必然是空空如也,所以相当于什么也没干就返回了。

//file:net/ipv4/tcp_ipv4.c
static struct sock *tcp_v4_hnd_req(struct sock *sk, struct sk_buff *skb)
{
 // 查找 listen socket 的半连接队列
 struct request_sock *req = inet_csk_search_req(sk, &prev, th->source,
          iph->saddr, iph->daddr);
 ...
 return sk;
}

在 tcp_rcv_state_process 里根据不同的 socket 状态进行不同的处理。

//file:net/ipv4/tcp_input.c
int tcp_rcv_state_process(struct sock *sk, struct sk_buff *skb,
     const struct tcphdr *th, unsigned int len)
{
 switch (sk->sk_state) {
  //第一次握手
  case TCP_LISTEN:
   if (th->syn) { //判断是 SYN 握手包
    ...
    if (icsk->icsk_af_ops->conn_request(sk, skb) < 0)
     return 1;
 ......
}  

其中 conn_request 是一个函数指针,指向 tcp_v4_conn_request。服务器响应 SYN 的主要处理逻辑都在这个 tcp_v4_conn_request 里

//file: net/ipv4/tcp_ipv4.c
int tcp_v4_conn_request(struct sock *sk, struct sk_buff *skb)
{
 //看看半连接队列是否满了
 if (inet_csk_reqsk_queue_is_full(sk) && !isn) {
  want_cookie = tcp_syn_flood_action(sk, skb, "TCP");
  if (!want_cookie)
   goto drop;
 }

 //在全连接队列满的情况下,如果有 young_ack,那么直接丢
 if (sk_acceptq_is_full(sk) && inet_csk_reqsk_queue_young(sk) > 1) {
  NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_LISTENOVERFLOWS);
  goto drop;
 }
 ...
 //分配 request_sock 内核对象
 req = inet_reqsk_alloc(&tcp_request_sock_ops);

 //构造 syn+ack 包
 skb_synack = tcp_make_synack(sk, dst, req,
  fastopen_cookie_present(&valid_foc) ? &valid_foc : NULL);

 if (likely(!do_fastopen)) {
  //发送 syn + ack 响应
  err = ip_build_and_send_pkt(skb_synack, sk, ireq->loc_addr,
    ireq->rmt_addr, ireq->opt);

  //添加到半连接队列,并开启计时器
  inet_csk_reqsk_queue_hash_add(sk, req, TCP_TIMEOUT_INIT);
 }else ...
}

在这里首先判断半连接队列是否满了,如果满了的话进入 tcp_syn_flood_action 去判断是否开启了 tcp_syncookies 内核参数。如果队列满,且未开启 tcp_syncookies,那么该握手包将直接被丢弃!!

接着还要判断全连接队列是否满。因为全连接队列满也会导致握手异常的,那干脆就在第一次握手的时候也判断了。如果全连接队列满了,且有 young_ack 的话,那么同样也是直接丢弃。

young_ack 是半连接队列里保持着的一个计数器。记录的是刚有SYN到达,没有被SYN_ACK重传定时器重传过SYN_ACK,同时也没有完成过三次握手的sock数量

接下来是构造 synack 包,然后通过 ip_build_and_send_pkt 把它发送出去。

最后把当前握手信息添加到半连接队列,并开启计时器。计时器的作用是如果某个时间之内还收不到客户端的第三次握手的话,服务器会重传 synack 包。

总结一下,服务器响应 ack 是主要工作是判断下接收队列是否满了,满的话可能会丢弃该请求,否则发出 synack。申请 request_sock 添加到半连接队列中,同时启动定时器

四、客户端响应 SYNACK

客户端收到服务器端发来的 synack 包的时候,也会进入到 tcp_rcv_state_process 函数中来。不过由于自身 socket 的状态是 TCP_SYN_SENT,所以会进入到另一个不同的分支中去。

//file:net/ipv4/tcp_input.c
//除了 ESTABLISHED 和 TIME_WAIT,其他状态下的 TCP 处理都走这里
int tcp_rcv_state_process(struct sock *sk, struct sk_buff *skb,
     const struct tcphdr *th, unsigned int len)
{
 switch (sk->sk_state) {
  //服务器收到第一个ACK包
  case TCP_LISTEN:
   ...
  //客户端第二次握手处理 
  case TCP_SYN_SENT:
   //处理 synack 包
   queued = tcp_rcv_synsent_state_process(sk, skb, th, len);
   ...
   return 0;
}

tcp_rcv_synsent_state_process 是客户端响应 synack 的主要逻辑。

//file:net/ipv4/tcp_input.c
static int tcp_rcv_synsent_state_process(struct sock *sk, struct sk_buff *skb,
      const struct tcphdr *th, unsigned int len)
{
 ...

 tcp_ack(sk, skb, FLAG_SLOWPATH);

 //连接建立完成 
 tcp_finish_connect(sk, skb);

 if (sk->sk_write_pending ||
   icsk->icsk_accept_queue.rskq_defer_accept ||
   icsk->icsk_ack.pingpong)
  //延迟确认...
 else {
  tcp_send_ack(sk);
 }
} 

tcp_ack()->tcp_clean_rtx_queue()

//file: net/ipv4/tcp_input.c
static int tcp_clean_rtx_queue(struct sock *sk, int prior_fackets,
       u32 prior_snd_una)
{
 //删除发送队列
 ...

 //删除定时器
 tcp_rearm_rto(sk);
}
//file: net/ipv4/tcp_input.c
void tcp_finish_connect(struct sock *sk, struct sk_buff *skb)
{
 //修改 socket 状态
 tcp_set_state(sk, TCP_ESTABLISHED);

 //初始化拥塞控制
 tcp_init_congestion_control(sk);
 ...

 //保活计时器打开
 if (sock_flag(sk, SOCK_KEEPOPEN))
  inet_csk_reset_keepalive_timer(sk, keepalive_time_when(tp));
}

客户端修改自己的 socket 状态为 ESTABLISHED,接着打开 TCP 的保活计时器。

//file:net/ipv4/tcp_output.c
void tcp_send_ack(struct sock *sk)
{
 //申请和构造 ack 包
 buff = alloc_skb(MAX_TCP_HEADER, sk_gfp_atomic(sk, GFP_ATOMIC));
 ...

 //发送出去
 tcp_transmit_skb(sk, buff, 0, sk_gfp_atomic(sk, GFP_ATOMIC));
}

在 tcp_send_ack 中构造 ack 包,并把它发送了出去。

客户端响应来自服务器端的 synack 时清除了 connect 时设置的重传定时器,把当前 socket 状态设置为 ESTABLISHED,开启保活计时器后发出第三次握手的 ack 确认。

五、服务器响应 ACK

服务器响应第三次握手的 ack 时同样会进入到 tcp_v4_do_rcv

//file: net/ipv4/tcp_ipv4.c
int tcp_v4_do_rcv(struct sock *sk, struct sk_buff *skb)
{
 ...
 if (sk->sk_state == TCP_LISTEN) {
  struct sock *nsk = tcp_v4_hnd_req(sk, skb);
 }

 if (tcp_rcv_state_process(sk, skb, tcp_hdr(skb), skb->len)) {
  rsk = sk;
  goto reset;
 }
}

不过由于这已经是第三次握手了,半连接队列里会存在上次第一次握手时留下的半连接信息。所以 tcp_v4_hnd_req 的执行逻辑会不太一样。

//file:net/ipv4/tcp_ipv4.c
static struct sock *tcp_v4_hnd_req(struct sock *sk, struct sk_buff *skb)
{
 ...
 struct request_sock *req = inet_csk_search_req(sk, &prev, th->source,
          iph->saddr, iph->daddr);
 if (req)
  return tcp_check_req(sk, skb, req, prev, false);
 ...
}

inet_csk_search_req 负责在半连接队列里进行查找,找到以后返回一个半连接 request_sock 对象。然后进入到 tcp_check_req 中。

//file:net/ipv4/tcp_minisocks.c
struct sock *tcp_check_req(struct sock *sk, struct sk_buff *skb,
      struct request_sock *req,
      struct request_sock **prev,
      bool fastopen)
{
 ...
 //创建子 socket
 child = inet_csk(sk)->icsk_af_ops->syn_recv_sock(sk, skb, req, NULL);
 ...

 //清理半连接队列
 inet_csk_reqsk_queue_unlink(sk, req, prev);
 inet_csk_reqsk_queue_removed(sk, req);

 //添加全连接队列
 inet_csk_reqsk_queue_add(sk, req, child);
 return child;
}

5.1 创建子 socket

icsk_af_ops->syn_recv_sock 对应的是 tcp_v4_syn_recv_sock 函数。

//file:net/ipv4/tcp_ipv4.c
const struct inet_connection_sock_af_ops ipv4_specific = {
 ......
 .conn_request      = tcp_v4_conn_request,
 .syn_recv_sock     = tcp_v4_syn_recv_sock,

//三次握手接近就算是完毕了,这里创建 sock 内核对象
struct sock *tcp_v4_syn_recv_sock(struct sock *sk, struct sk_buff *skb,
      struct request_sock *req,
      struct dst_entry *dst)
{    
 //判断接收队列是不是满了
 if (sk_acceptq_is_full(sk))
  goto exit_overflow;

 //创建 sock && 初始化
 newsk = tcp_create_openreq_child(sk, req, skb);

注意,在第三次握手的这里又继续判断一次全连接队列是否满了,如果满了修改一下计数器就丢弃了。如果队列不满,那么就申请创建新的 sock 对象。

5.2 删除半连接队列

把连接请求块从半连接队列中删除。

//file: include/net/inet_connection_sock.h 
static inline void inet_csk_reqsk_queue_unlink(struct sock *sk, struct request_sock *req,
 struct request_sock **prev)
{
 reqsk_queue_unlink(&inet_csk(sk)->icsk_accept_queue, req, prev);
}

reqsk_queue_unlink 中把连接请求块从半连接队列中删除。

5.3 添加全连接队列

接着添加到全连接队列里边来。

//file:net/ipv4/syncookies.c
static inline void inet_csk_reqsk_queue_add(struct sock *sk,
      struct request_sock *req,
      struct sock *child)
{
 reqsk_queue_add(&inet_csk(sk)->icsk_accept_queue, req, sk, child);
}

在 reqsk_queue_add 中将握手成功的 request_sock 对象插入到全连接队列链表的尾部。

//file: include/net/request_sock.h
static inline void reqsk_queue_add(...)
{
 req->sk = child;
 sk_acceptq_added(parent);

 if (queue->rskq_accept_head == NULL)
  queue->rskq_accept_head = req;
 else
  queue->rskq_accept_tail->dl_next = req;

 queue->rskq_accept_tail = req;
 req->dl_next = NULL;
}

5.4 设置连接为 ESTABLISHED

//file:net/ipv4/tcp_input.c
int tcp_rcv_state_process(struct sock *sk, struct sk_buff *skb,
     const struct tcphdr *th, unsigned int len)
{
 ...
 switch (sk->sk_state) {

  //服务端第三次握手处理
  case TCP_SYN_RECV:

   //改变状态为连接
   tcp_set_state(sk, TCP_ESTABLISHED);
   ...
 }
}

将连接设置为 TCP_ESTABLISHED 状态。

服务器响应第三次握手 ack 所做的工作是把当前半连接对象删除,创建了新的 sock 后加入到全连接队列中,最后将新连接状态设置为 ESTABLISHED

六、服务器 accept

最后 accept 一步咱们长话短说。

//file: net/ipv4/inet_connection_sock.c
struct sock *inet_csk_accept(struct sock *sk, int flags, int *err)
{
 //从全连接队列中获取
 struct request_sock_queue *queue = &icsk->icsk_accept_queue;
 req = reqsk_queue_remove(queue);

 newsk = req->sk;
 return newsk;
}

reqsk_queue_remove 这个操作很简单,就是从全连接队列的链表里获取出第一个元素返回就行了。

//file:include/net/request_sock.h
static inline struct request_sock *reqsk_queue_remove(struct request_sock_queue *queue)
{
 struct request_sock *req = queue->rskq_accept_head;

 queue->rskq_accept_head = req->dl_next;
 if (queue->rskq_accept_head == NULL)
  queue->rskq_accept_tail = NULL;

 return req;
}

所以,accept 的重点工作就是从已经建立好的全连接队列中取出一个返回给用户进程。

七、总结

在后端相关岗位的入职面试中,三次握手的出场频率非常的高。其实在三次握手的过程中,不仅仅是一个握手包的发送 和 TCP 状态的流转。还包含了端口选择,连接队列创建与处理等很多关键技术点。

  1. 服务器 listen 时,计算了全/半连接队列的长度,还申请了相关内存并初始化。

  2. 客户端 connect 时,把本地 socket 状态设置成了 TCP_SYN_SENT,选则一个可用的端口,发出 SYN 握手请求并启动重传定时器。

  3. 服务器响应 ack 时,会判断下接收队列是否满了,满的话可能会丢弃该请求。否则发出 synack,申请 request_sock 添加到半连接队列中,同时启动定时器。

  4. 客户端响应 synack 时,清除了 connect 时设置的重传定时器,把当前 socket 状态设置为 ESTABLISHED,开启保活计时器后发出第三次握手的 ack 确认。

  5. 服务器响应 ack 时,把对应半连接对象删除,创建了新的 sock 后加入到全连接队列中,最后将新连接状态设置为 ESTABLISHED。

  6. accept 从已经建立好的全连接队列中取出一个返回给用户进程。

另外要注意的是,如果握手过程中发生丢包(网络问题,或者是连接队列溢出),内核会等待定时器到期后重试,重试时间间隔在 3.10 版本里分别是 1s 2s 4s …。在一些老版本里,比如 2.6 里,第一次重试时间是 3 秒。最大重试次数分别由 tcp_syn_retries 和 tcp_synack_retries 控制。

如果你的线上接口正常都是几十毫秒内返回,但偶尔出现了 1 s、或者 3 s 等这种偶发的响应耗时变长的问题,那么你就要去定位一下看看是不是出现了握手包的超时重传了。

TCP连接中客户端的端口号确定

在 TCP 连接中,客户端在发起连接请求前会先确定一个客户端端口,然后用这个端口去和服务器端进行握手建立连接。那么在 Linux 上,客户端的端口到底是如何被确定下来的呢?

事实上很多我们平时遇到的问题都和这个端口选择过程相关,如果能深度理解这个过程,将有助于我们对这些问题的深刻理解。

  • Cannot assign requested address 报错是怎么回事?
  • 一个客户端端口可以同时用在两条 TCP 连接上吗?
int main(){
 fd = socket(AF_INET,SOCK_STREAM, 0);
 connect(fd, ...);
 ...
}

一、创建 socket

客户端在发起连接的时候,需要事先创建一个 socket。在 c 语言中,就是调用 socket 函数,例如 socket(AF_INET,SOCK_STREAM, 0) 这句。

socket 函数执行完毕后,在用户层视角我们是看到返回了一个文件描述符 fd。但在内核中其实是一套内核对象组合,大体结构如下。

从上图我们看到,socket 在内核里并不是一个内核对象。而是包含 file、socket、sock 等多个相关内核对象构成,每个内核对象还定义了 ops 操作函数集合。在后面的内核源码执行过程中,我们需要时不时回头来看这些内核对象,这里先简单了解一下就行。

这些内核对象都是在 socket 系统调用执行过程中创建出来的。为了避免喧宾夺主,这里只列出入口代码,详细过程就不展开介绍了。

//file: net/socket.c
SYSCALL_DEFINE3(socket, int, family, int, type, int, protocol)
{
 //创建 socket、sock 等内核对象,并初始化
 sock_create(family, type, protocol, &sock);

 //创建 file 内核对象,申请 fd
 sock_map_fd(sock, flags & (O_CLOEXEC | O_NONBLOCK));

 ......
}

二、connect 发起连接

接下来我们就进入到 connect 函数的执行过程中来。由于这个过程比较长,所以我们分成几个小节来进行讨论。

2.1 connect 调用链展开

当我们在客户端机上调用 connect 函数的时候,事实上会进入到内核的系统调用源码中进行执行。

//file: net/socket.c
SYSCALL_DEFINE3(connect, int, fd, struct sockaddr __user *, uservaddr,
  int, addrlen)
{
 struct socket *sock;

 //根据用户 fd 查找内核中的 socket 对象
 sock = sockfd_lookup_light(fd, &err, &fput_needed);

 //进行 connect
 err = sock->ops->connect(sock, (struct sockaddr *)&address, addrlen,
     sock->file->f_flags);
 ...
}

这段代码首先根据用户传入的 fd(文件描述符)来查询对应的 socket 内核对象。在第一节中我们看了 socket 内核对象结构,据此可以知道接下来 sock->ops->connect 其实调用的是 inet_stream_connect 函数。

//file: ipv4/af_inet.c
int inet_stream_connect(struct socket *sock, ...)
{ 
 ...
 __inet_stream_connect(sock, uaddr, addr_len, flags);
}

int __inet_stream_connect(struct socket *sock, ...)
{
 struct sock *sk = sock->sk;

 switch (sock->state) {
  case SS_UNCONNECTED:
   err = sk->sk_prot->connect(sk, uaddr, addr_len);
   sock->state = SS_CONNECTING;
   break;
 }
 ...
}

刚创建完毕的 socket 的状态就是 SS_UNCONNECTED,所以在 __inet_stream_connect 中的 switch 判断会进入到 case SS_UNCONNECTED 的处理逻辑中。

上述代码中 sk 取的是 sock 对象。继续回顾第一节中 socket 的内核数据结构图,可以得知 sk->sk_prot->connect 实际上对应的是 tcp_v4_connect 方法。

我们来看 tcp_v4_connect 的代码,它位于 net/ipv4/tcp_ipv4.c。

//file: net/ipv4/tcp_ipv4.c
int tcp_v4_connect(struct sock *sk, struct sockaddr *uaddr, int addr_len)
{
 //设置 socket 状态为 TCP_SYN_SENT
 tcp_set_state(sk, TCP_SYN_SENT);

 //动态选择一个端口
 err = inet_hash_connect(&tcp_death_row, sk);

 //函数用来根据 sk 中的信息,构建一个完成的 syn 报文,并将它发送出去。
 err = tcp_connect(sk);
}

在 tcp_v4_connect 中我们终于看到了选择端口的函数,那就是 inet_hash_connect。

2.2 选择可用端口

我们找到 inet_hash_connect 的源码,我们来看看到底端口是如何选择出来的。

//file:net/ipv4/inet_hashtables.c
int inet_hash_connect(struct inet_timewait_death_row *death_row,
        struct sock *sk)
{
 return __inet_hash_connect(death_row, sk, inet_sk_port_offset(sk),
   __inet_check_established, __inet_hash_nolisten);
}

这里需要提一下在调用 __inet_hash_connect 时传入的两个重要参数。

  • inet_sk_port_offset(sk):这个函数是根据要连接的目的 IP 和端口等信息生成一个随机数。
  • __inet_check_established:检查是否和现有 ESTABLISH 的连接是否冲突的时候用的函数

了解了这两个参数后,让我们进入 __inet_hash_connect。这个函数比较长,为了方便理解,我们先看前面这一段。

//file:net/ipv4/inet_hashtables.c
int __inet_hash_connect(...)
{
 //是否绑定过端口
 const unsigned short snum = inet_sk(sk)->inet_num;

 //获取本地端口配置
 inet_get_local_port_range(&low, &high);
  remaining = (high - low) + 1;

 if (!snum) {
  //遍历查找
  for (i = 1; i <= remaining; i++) {
   port = low + (i + offset) % remaining;
   ...
  }
 }
}

在这个函数中首先判断了 inet_sk(sk)->inet_num,如果我们调用过 bind,那么这个函数会选择好端口并设置在 inet_num 上。这个我们后面专门分一小节介绍。这里我们假设没有调用过 bind,所以 snum 为 0。

接着调用 inet_get_local_port_range,这个函数读取的是 net.ipv4.ip_local_port_range 这个内核参数。来读取管理员配置的可用的端口范围。

该参数的默认值是 32768 61000,意味着端口总可用的数量是 61000 - 32768 = 28232 个。如果你觉得这个数字不够用,那就修改你的 net.ipv4.ip_local_port_range 内核参数。

接下来进入到了 for 循环中。其中offset 是我们前面说的,通过 inet_sk_port_offset(sk) 计算出的随机数。那这段循环的作用就是从某个随机数开始,把整个可用端口范围来遍历一遍。直到找到可用的端口后停止。

那么我们接着来看,如何来确定一个端口是否可以使用呢?

//file:net/ipv4/inet_hashtables.c
int __inet_hash_connect(...)
{
 for (i = 1; i <= remaining; i++) {
  port = low + (i + offset) % remaining;

  //查看是否是保留端口,是则跳过
  if (inet_is_reserved_local_port(port))
   continue;

  // 查找和遍历已经使用的端口的哈希链表
  head = &hinfo->bhash[inet_bhashfn(net, port,
    hinfo->bhash_size)];
  inet_bind_bucket_for_each(tb, &head->chain) {

   //如果端口已经被使用
   if (net_eq(ib_net(tb), net) &&
       tb->port == port) {

                //通过 check_established 继续检查是否可用
    if (!check_established(death_row, sk,
       port, &tw))
     goto ok;
   }
  }

  //未使用的话,直接 ok
  goto ok;
 }

 return -EADDRNOTAVAIL;
ok: 
 ...  
}

首先判断的是 inet_is_reserved_local_port,这个很简单就是判断要选择的端口是否在 net.ipv4.ip_local_reserved_ports 中,在的话就不能用。

如果你因为某种原因不希望某些端口被内核使用,那么就把它们写到 ip_local_reserved_ports 这个内核参数中就行了。

整个系统中会维护一个所有使用过的端口的哈希表,它就是 hinfo->bhash。接下来的代码就会在这里进行查找。如果在哈希表中没有找到,那么说明这个端口是可用的。至此端口就算是找到了。

遍历完所有端口都没找到合适的,就返回 -EADDRNOTAVAIL,你在用户程序上看到的就是 Cannot assign requested address 这个错误。怎么样,是不是很眼熟,你见过它的对吧,哈哈!

/* Cannot assign requested address */
#define EADDRNOTAVAIL 99 

以后当你再遇到 Cannot assign requested address 错误,你应该想到去查一下 net.ipv4.ip_local_port_range 中设置的可用端口的范围是不是太小了。

2.3 端口被使用过怎么办

回顾刚才的 __inet_hash_connect, 为了描述简单我们之前跳过了已经在 bhash 中存在时候的判断。这是由于其一这个过程比较长,其二这段逻辑很有价值,所以飞哥单独拉一小节出来。

//file:net/ipv4/inet_hashtables.c
int __inet_hash_connect(...)
{
 for (i = 1; i <= remaining; i++) {
  port = low + (i + offset) % remaining;

  ...
  //如果端口已经被使用
  if (net_eq(ib_net(tb), net) &&
       tb->port == port) {
   //通过 check_established 继续检查是否可用
   if (!check_established(death_row, sk, port, &tw))
    goto ok;
  }
 }
}

port 已经在 bhash 中如果已经存在,就表示有其它的连接使用过该端口了。请注意,如果 check_established 返回 0,该端口仍然可以接着使用!

这里可能会让很多同学困惑了,一个端口怎么可以被用多次呢?

回忆下四元组的概念,两对儿四元组中只要任意一个元素不同,都算是两条不同的连接。以下的两条 TCP 连接完全可以同时存在(假设 192.168.1.101 是客户端,192.168.1.100 是服务端)

  • 连接1:192.168.1.101 5000 192.168.1.100 8090
  • 连接2:192.168.1.101 5000 192.168.1.100 8091

check_established 作用就是检测现有的 TCP 连接中是否四元组和要建立的连接四元素完全一致。如果不完全一致,那么该端口仍然可用!!!

这个 check_established 是由调用方传入的,实际上使用的是 __inet_check_established。我们来看它的源码。

//file: net/ipv4/inet_hashtables.c
static int __inet_check_established(struct inet_timewait_death_row *death_row,
        struct sock *sk, __u16 lport,
        struct inet_timewait_sock **twp)
{
 //找到hash桶
 struct inet_ehash_bucket *head = inet_ehash_bucket(hinfo, hash);

 //遍历看看有没有四元组一样的,一样的话就报错
 sk_nulls_for_each(sk2, node, &head->chain) {
  if (sk2->sk_hash != hash)
   continue;
  if (likely(INET_MATCH(sk2, net, acookie,
          saddr, daddr, ports, dif)))
   goto not_unique;
 }

unique:
 //要用了,记录,返回 0 (成功)
 return 0;
not_unique:
 return -EADDRNOTAVAIL; 
}

该函数首先找到 inet_ehash_bucket,这个和 bhash 类似,只不过是所有 ESTABLISH 状态的 socket 组成的哈希表。然后遍历这个哈希表,使用 INET_MATCH 来判断是否可用。

这里 INET_MATCH 源码如下:

// include/net/inet_hashtables.h
#define INET_MATCH(__sk, __net, __cookie, __saddr, __daddr, __ports, __dif) \
 ((inet_sk(__sk)->inet_portpair == (__ports)) &&  \
  (inet_sk(__sk)->inet_daddr == (__saddr)) &&  \
  (inet_sk(__sk)->inet_rcv_saddr == (__daddr)) &&  \
  (!(__sk)->sk_bound_dev_if ||    \
    ((__sk)->sk_bound_dev_if == (__dif)))  &&  \
  net_eq(sock_net(__sk), (__net)))

在 INET_MATCH 中将 saddr、daddr、__ports 都进行了比较。当然除了 ip 和端口,INET_MATCH还比较了其它一些东东,所以 TCP 连接还有五元组、七元组之类的说法。为了统一,咱们还沿用四元组的说法。

如果 MATCH,就是说就四元组完全一致的连接,所以这个端口不可用。也返回 -EADDRNOTAVAIL。

如果不 MATCH,哪怕四元组中有一个元素不一样,例如服务器的端口号不一样,那么就 return 0,表示该端口仍然可用于建立新连接。

所以一台客户端机最大能建立的连接数并不是 65535。只要 server 足够多,单机发出百万条连接没有任何问题。

2.4 发起 syn 请求

再回到 tcp_v4_connect,这时我们的 inet_hash_connect 已经返回了一个可用端口了。接下来就进入到 tcp_connect,如下源码所示。

//file: net/ipv4/tcp_ipv4.c
int tcp_v4_connect(struct sock *sk, struct sockaddr *uaddr, int addr_len)
{
 ......

 //动态选择一个端口
 err = inet_hash_connect(&tcp_death_row, sk);

 //函数用来根据 sk 中的信息,构建一个完成的 syn 报文,并将它发送出去。
 err = tcp_connect(sk);
}

到这里其实就和本文要讨论的主题没有关系了,所以我们只是简单看一下。

//file:net/ipv4/tcp_output.c
int tcp_connect(struct sock *sk)
{
 //申请并设置 skb
 buff = alloc_skb_fclone(MAX_TCP_HEADER + 15, sk->sk_allocation);
 tcp_init_nondata_skb(buff, tp->write_seq++, TCPHDR_SYN);

 //添加到发送队列 sk_write_queue 上
 tcp_connect_queue_skb(sk, buff);

 //实际发出 syn
 err = tp->fastopen_req ? tcp_send_syn_data(sk, buff) :
       tcp_transmit_skb(sk, buff, 1, sk->sk_allocation);

 //启动重传定时器
 inet_csk_reset_xmit_timer(sk, ICSK_TIME_RETRANS,
      inet_csk(sk)->icsk_rto, TCP_RTO_MAX);
}

tcp_connect 一口气做了这么几件事

  • 申请一个 skb,并将其设置为 SYN 包
  • 添加到发送队列上
  • 调用 tcp_transmit_skb 将该包发出
  • 启动一个重传定时器,超时会重发

三、bind 时端口如何选择

在 2.2 小节中,我们看到 connect 选择端口之前先判断了 inet_sk(sk)->inet_num 有没有值。如果有的话就直接用这个,而会跳过端口选择过程。

那么这个值是从哪儿来的呢?不卖关子,它就是在对 socket 使用 bind 时设置的。

不只是服务器端,哪怕是对于客户端,也可以对 socket 使用 bind 来绑定 IP 或者端口。如果使用了 bind,那么在 bind 的时候就会确定好端口,并设置到 inet_num 变量中。

一般非常不推荐在客户端角色下使用 bind。因为这会打乱 connect 里的端口选择过程。

bind 的时候,如果传了端口,那么 bind 就会尝试使用该端口。如果端口号传的是 0 ,那么 bind 有一套独立的选择端口号的逻辑。

//file: net/ipv4/af_inet.c
int inet_bind(struct socket *sock, struct sockaddr *uaddr, int addr_len)
{
 struct sock *sk = sock->sk;
 ...

 //用户传入的端口号
 snum = ntohs(addr->sin_port);

 //不允许绑定 1024 以下的端口
 if (snum && snum < PROT_SOCK &&
     !ns_capable(net->user_ns, CAP_NET_BIND_SERVICE))
  goto out;

 //尝试确定端口号
 if (sk->sk_prot->get_port(sk, snum)) {
  inet->inet_saddr = inet->inet_rcv_saddr = 0;
  err = -EADDRINUSE;
  goto out_release_sock;
 }

根据第一节中的 socket 内核对象,能找到 sk->sk_prot->get_port 实际调用的是 inet_csk_get_port。该函数来尝试确定端口号,如果尝试失败,返回 EADDRINUSE。你的应用程序将会显示一条错误信息 “Address already in use”。

#define EADDRINUSE 226 /* Address already in use */

我们简单看一下如果用户没有传入端口(传入的为 0),bind 是怎么选择端口的。

//file: net/ipv4/inet_connection_sock.c
int inet_csk_get_port(struct sock *sk, unsigned short snum)
{
 ...

 if (!snum) {
  inet_get_local_port_range(&low, &high);
  remaining = (high - low) + 1;
  smallest_rover = rover = net_random() % remaining + low;

  do {
   if (inet_is_reserved_local_port(rover))
    goto next_nolock;

   head = &hashinfo->bhash[inet_bhashfn(net, rover,
      hashinfo->bhash_size)];
   inet_bind_bucket_for_each(tb, &head->chain)

    // 冲突检测
    if (!inet_csk(sk)->icsk_af_ops->bind_conflict(sk, tb, false)) {
     snum = rover;
     goto tb_found;
    }

  } while (--remaining > 0);
 }
}

这段逻辑和 connect 很像,通过 net_random 来从 net.ipv4.ip_local_port_range 指定的端口范围内一个随机位置开始遍历。也会跳开 ip_local_reserved_ports 保留端口配置。通过 inet_csk(sk)->icsk_af_ops->bind_conflict 进行冲突检测。

inet_csk_bind_conflict 这个函数整体比较复杂,不过我们只需要了解一点就好,该函数和 connect 中端口选择逻辑不同的是,并不会到 ESTABLISH 的哈希表进行可用检测,只在 bind 状态的 socket 里查。所以默认情况下,只要端口用过一次就不会再次使用

四、结论

客户端建立连接前需要确定一个端口,该端口会在两个位置进行确定。

第一个位置,也是最主要的确定时机是 connect 系统调用执行过程。在 connect 的时候,会随机地从 ip_local_port_range 选择一个位置开始循环判断。找到可用端口后,发出 syn 握手包。如果端口查找失败,会报错 “Cannot assign requested address”。这个时候你应该首先想到去检查一下服务器上的 net.ipv4.ip_local_port_range 参数,是不是可以再放的多一些。

如果你因为某种原因不希望某些端口被使用到,那么就把它们写到 ip_local_reserved_ports 这个内核参数中就行了,内核在选择的时候会跳过这些端口。

另外注意即使是一个端口是可以被用于多条 TCP 连接的。所以一台客户端机最大能建立的连接数并不是 65535。只要 server 足够多,单机发出百万条连接没有任何问题。

实验时候在客户机上实验时的实际截图,来实际看一下一个端口号确实是被用在了多条连接上了。

截图中左边的 192 是客户端,右边的 119 是服务器的 ip。可以看到客户端的 10000 这个端口号是用在了多条连接上了的。

第二个位置,如果在 connect 之前使用了 bind,将会使得 connect 时的端口选择方式无效。转而使用 bind 时确定的端口。bind 时如果传入了端口号,会尝试首先使用该端口号,如果传入了 0 ,也会自动选择一个。但默认情况下一个端口只会被使用一次。所以对于客户端角色的 socket,不建议使用 bind !

最后我再想多说一句,上面的选择端口的都是从 ip_local_port_range 范围中的某一个随机位置开始循环的。如果可用端口很充足,则能快一点找到可用端口,那循环很快就能退出。假设实际中 ip_local_port_range 中的端口快被用光了,这时候内核就大概率得把循环多执行很多轮才能找到,这会导致 connect 系统调用的 CPU 开销的上涨。

所以,最好不要等到端口不够用了才加大 ip_local_port_range 的范围,而是事先就应该保持一个充足的范围。

TCP 拥塞控制

1.拥塞控制简史

来看下维基百科对TCP/IP协议栈的一些介绍:

互联网协议套件是一个网络通信模型以及整个网络传输协议家族,由于该协议簇包含两个核心协议:TCP(传输控制协议)和IP(网际协议),因此常被通称为TCP/IP协议族。

TCP/IP协议对于数据应该如何封装、定址、传输、路由以及在目的地如何接收等基本过程都加以标准化。它将通信过程抽象化为四个层次,并采取协议堆栈的方式分别实现出不同通信协议,实际使用的四层结构是七层OSI模型的简化。

我们可以看到TCP/IP协议栈是一个简化的分层模型,是互联网世界连接一切的基石,一起来看一张七层模型vs四层模型的简图:

大约在1988年之前TCP/IP是没有拥塞控制的,但是随着网络接入规模的发展之前仅有的端到端窗口控制已经无法满足要求,在1986年引发大规模网络瘫痪,此时就要提到一个重量级人物:Van Jacobson范·雅各布森。

这位力挽狂澜的人物入选了计算机名人堂Internet Hall of Fame,Van Jacobson大神提出并设计实施了TCP/IP拥塞控制,解决了当时最大的问题,来简单看下Van Jacobson的维基百科简介:

范·雅各布森Van Jacobson是目前作为互联网技术基础的TCP/IP协议栈的主要起草者,他以其在网络性能的提升和优化的开创性成就而闻名。

2006年8月,他加入了帕洛阿尔托研究中心担任研究员,并在位于相邻的施乐建筑群的Packet Design公司担任首席科学家。在此之前,他曾是思科系统公司首席科学家,并在位于劳伦斯伯克利国家实验室的网络研究小组任领导者。

范·雅各布森因为在提高IP网络性能提升和优化所作的工作而为人们所知,1988到1989年间,他重新设计了TCP/IP的流控制算法(Jacobson算法),他因设计了RFC 1144中的TCP/IP头压缩协议即范·雅各布森TCP/IP头压缩协议而广为人知。此外他也曾与他人合作设计了一些被广泛使用的网络诊断工具,如traceroute,pathchar以及tcpdump 。

范·雅各布森于2012年4月入选第一批计算机名人堂,计算机名人堂简介:https://www.internethalloffame.org/inductees/van-jacobson

如图为Van Jacobson计算机名人堂的简介:

Van Jacobson和Michael J. Karels在1988年11月发布的关于拥塞避免和控制的论文,总计25页:

https://ee.lbl.gov/papers/congavoid.pdf

我们常用的tracetoute和tcpdump也是van-jacobson大神的杰作,作为互联网时代的受益者不由得对这些互联网发展早期做出巨大贡献的开拓者、创新者、变革者心生赞叹和敬意。

2.流量控制和拥塞控制

TCP是一种面向连接的、可靠的、全双工传输协议,前辈们写了很多复杂的算法为其保驾护航,其中有一组像海尔兄弟一样的算法:流量控制和拥塞控制,这也是我们今天的主角。

2.1 流量控制简介

流量控制和拥塞控制从汉语字面上并不能很好的区分,本质上这一对算法既有区别也有联系。

维基百科对于流量控制Flow Control的说明:

In data communications, flow control is the process of managing the rate of data transmission between two nodes to prevent a fast sender from overwhelming a slow receiver.

It provides a mechanism for the receiver to control the transmission speed, so that the receiving node is not overwhelmed with data from transmitting node.

翻译一下:

在数据通信中,流量控制是管理两个节点之间数据传输速率的过程,以防止快速发送方压倒慢速接收方。

它为接收机提供了一种控制传输速度的机制,这样接收节点就不会被来自发送节点的数据淹没。

可以看到流量控制是通信双方之间约定数据量的一种机制,具体来说是借助于TCP协议的确认ACK机制和窗口协议来完成的。

窗口分为固定窗口和可变窗口,可变窗口也就是滑动窗口,简单来说就是通信双方根据接收方的接收情况动态告诉发送端可以发送的数据量,从而实现发送方和接收方的数据收发能力匹配。

这个过程非常容易捕捉,使用wireshark在电脑上抓或者tcpdump在服务器上抓都可以看到,大白在自己电脑上用wireshark抓了一条:

我们以两个主机交互来简单理解流量控制过程:

接收方回复报文头部解释:

图中RcvBuffer是接收区总大小,buffered data是当前已经占用的数据,而free buffer space是当前剩余的空间,rwnd的就是free buffer space区域的字节数。

HostB把当前的rwnd值放入报文头部的接收窗口receive window字段中,以此通知HostA自己还有多少可用空间, 而HostA则将未确认的数据量控制在rwnd值的范围内,从而避免HostB的接收缓存溢出。

可见流量控制是端到端微观层面的数据策略,双方在数据通信的过程中并不关心链路带宽情况,只关心通信双方的接收发送缓冲区的空间大小,可以说是个速率流量匹配策略。

流量控制就像现实生活中物流领域中A和B两个仓库,A往B运送货物时只关心仓库B的剩余空间来调整自己的发货量,而不关心高速是否拥堵。

2.2 拥塞控制的必要性

前面我们提到了微观层面点到点的流量控制,但是我们不由地思考一个问题:只有流量控制够吗?答案是否定的。

我们还需要一个宏观层面的控去避免网络链路的拥堵,否则再好的端到端流量控制算法也面临丢包、乱序、重传问题,只能造成恶性循环。

我们从一个更高的角度去看大量TCP连接复用网络链路的通信过程:

所以拥塞控制和每一条端到端的连接关系非常大,这就是流量控制和拥塞控制的深层次联系,所谓每一条连接都顺畅那么整个复杂的网络链路也很大程度是通畅的。

在展开拥塞控制之前我们先考虑几个问题:

  • 如何感知拥塞

TCP连接的发送方在向对端发送数据的过程中,需要根据当前的网络状况来调整发送速率,所以感知能力很关键。

在TCP连接的发送方一般是基于丢包来判断当前网络是否发生拥塞,丢包可以由重传超时RTO和重复确认来做判断。

  • 如何利用带宽

诚然拥塞影响很大,但是一直低速发包对带宽利用率很低也是很不明智的做法,因此要充分利用带宽就不能过低过高发送数据,而是保持在一个动态稳定的速率来提高带宽利用率,这个还是比较难的,就像茫茫黑夜去躲避障碍物。

  • 拥塞时如何调整

拥塞发生时我们需要有一套应对措施来防止拥塞恶化并且恢复连接流量,这也是拥塞控制算法的精要所在。

3.理解拥塞控制

看到一篇文章说到TCP 传输层拥塞控制算法并不是简单的计算机网络的概念,也属于控制论范畴,感觉这个观点很道理。

TCP拥塞控制算法的目的可以简单概括为:公平竞争、充分利用网络带宽、降低网络延时、优化用户体验,然而就目前而言要实现这些目标就难免有权衡和取舍。

在理解拥塞控制算法之前我们需要明确一个核心的思想:闻道有先后 术业有专攻,笔者觉得这是一个非常重要的共识问题,把A踩在泥土里,把B吹捧到天上去,都不是很好的做法。

实际的网络环境十分复杂并且变化很快,并没有哪个拥塞控制算法可以全部搞定,每一种算法都有自己的特定和适用领域,每种算法都是对几个关键点的权衡,在无法兼得的条件下有的算法选择带宽利用率,有的算法选择通信延时等等。

在明确这个共识问题之后,我们对待各个拥塞控制算法的态度要平和一些,不要偏激地认为谁就是最好,几十年前的网络状况和现在是截然不同的,我们永远都是站在巨人的肩膀之上的,这也是科学和文明进步的推动力。

传统拥塞控制算法并不是一蹴而就的,复杂的网络环境和用户的高要求推动着拥塞控制算法的优化和迭代,我们看下基于丢包策略的传统拥塞控制算法的几个迭代版本,如图所示:

与此同时还有一类算法是基于RTT延时策略来进行控制的,但是这类算法在发包速率上可能不够激进,竞争性能不如其他算法,因此在共享网络带宽时有失公平性,但是算法速率曲线却是很平滑,我们暂且把这类算法当做君子吧!

其中比较有名的Vegas算法是大约在1995年由亚利桑那大学的研究人员拉里·彼得森和劳伦斯·布拉科夫提出,这个新的TCP拥塞算法以内华达州最大的城市拉斯维加斯命名,后成为TCP Vegas算法。

关于基于RTT的TCP Vegas算法的详细介绍可以查阅文档:

http://www.cs.cmu.edu/~srini/15-744/F02/readings/BP95.pdf

文档对Vegas算法和New Reno做了一些对比,我们从直观图形上可以看到Vegas算法更加平滑,相反New Reno则表现除了较大的波动呈锯齿状,如图所示:

实际上还有更细粒度的分类,由于不是今天的重点,就不再深入展开了,当前使用的拥塞控制算法还是基于丢包Loss-Based作为主流。

3.1 拥塞窗口cwnd

从流量控制可以知道接收方在header中给出了rwnd接收窗口大小,发送方不能自顾自地按照接收方的rwnd限制来发送数据,因为网络链路是复用的,需要考虑当前链路情况来确定数据量,这也是我们要提的另外一个变量cwnd,找了一个关于rwnd和cwnd的英文解释:

Congestion Window (cwnd) is a TCP state variable that limits the amount of data the TCP can send into the network before receiving an ACK.

The Receiver Window (rwnd) is a variable that advertises the amount of data that the destination side can receive.

Together, the two variables are used to regulate data flow in TCP connections, minimize congestion, and improve network performance.

rfc5681文档中cwnd的定义:

这个解释指出了cwnd是在发送方维护的,cwnd和rwnd并不冲突,发送方需要结合rwnd和cwnd两个变量来发送数据,如图所示:

cwnd的大小和MSS最大数据段有直接关系,MSS是TCP报文段中的数据字段的最大长度,即MSS=TCP报文段长度-TCP首部长度。

3.2 拥塞控制基本策略

拥塞控制是一个动态的过程,它既要提高带宽利用率发送尽量多的数据又要避免网络拥堵丢包RTT增大等问题,基于这种高要求并不是单一策略可以搞定的,因此TCP的拥塞控制策略实际上是分阶段分策略的综合过程:

注:有的版本的TCP算法不一定没有快速恢复阶段

如图为典型的包含4个策略的拥塞控制:

如图为发生超时重传RTO时的过程:

3.3 TCP拥塞控制算法常见版本

实际上TCP算法有很多版本,每个版本存在一些差异,在这里简单看一下维基百科的介绍:

  • 算法命名规则

TCP+算法名的命名方式最早出现在Kevin Fall和Sally Floyd1996年发布的论文中。

  • TCP Tahoe 和TCP Reno

这两个算法代号取自太浩湖Lake Tahoe和里诺市,两者算法大致一致,对于丢包事件判断都是以重传超时retransmission timeout和重复确认为条件,但是对于重复确认的处理两者有所不同,对于超时重传RTO情况两个算法都是将拥塞窗口降为1个MSS,然后进入慢启动阶段。

TCP Tahoe算法:如果收到三次重复确认即第四次收到相同确认号的分段确认,并且分段对应包无负载分段和无改变接收窗口的话,Tahoe算法则进入快速重传,将慢启动阈值改为当前拥塞窗口的一半,将拥塞窗口降为1个MSS,并重新进入慢启动阶段。

TCP Reno算法:如果收到三次重复确认,Reno算法则进入快速重传只将拥塞窗口减半来跳过慢启动阶段,将慢启动阈值设为当前新的拥塞窗口值,进入一个称为快速恢复的新设计阶段。

  • TCP New Reno

TCP New Reno是对TCP Reno中快速恢复阶段的重传进行改善的一种改进算法,New Reno在低错误率时运行效率和选择确认SACK相当,在高错误率仍优于Reno。

  • TCP BIC 和TCP CUBIC

TCP BIC旨在优化高速高延迟网络的拥塞控制,其拥塞窗口算法使用二分搜索算法尝试找到能长时间保持拥塞窗口最大值,Linux内核在2.6.8至2.6.18使用该算法作为默认TCP拥塞算法。

CUBIC则是比BIC更温和和系统化的分支版本,其使用三次函数代替二分算法作为其拥塞窗口算法,并且使用函数拐点作为拥塞窗口的设置值,Linux内核在2.6.19后使用该算法作为默认TCP拥塞算法。

  • TCP PRR

TCP PRR是旨在恢复期间提高发送数据的准确性,该算法确保恢复后的拥塞窗口大小尽可能接近慢启动阈值。在Google进行的测试中,能将平均延迟降低3~10%恢复超时减少5%,PRR算法后作为Linux内核3.2版本默认拥塞算法。

  • TCP BBR

TCP BBR是由Google设计于2016年发布的拥塞算法,该算法认为随着网络接口控制器逐渐进入千兆速度时,分组丢失不应该被认为是识别拥塞的主要决定因素,所以基于模型的拥塞控制算法能有更高的吞吐量和更低的延迟,可以用BBR来替代其他流行的拥塞算法。

Google在YouTube上应用该算法,将全球平均的YouTube网络吞吐量提高了4%,BBR之后移植入Linux内核4.9版本。

3.4 拥塞控制过程详解

我们以典型慢启动、拥塞避免、快速重传、快速恢复四个过程进行阐述。

  • 慢启动

慢启动就是对于刚启动的网络连接,发送速度不是一步到位而是试探性增长,具体来说:连接最初建立时发送方初始化拥塞窗口cwnd为m,之后发送方在一个RTT内每收到一个ACK数据包时cwnd线性自增1,发送方每经过一个RTT时间,cwnd=cwnd*2指数增长,经过一段时间增长直到cwnd达到慢启动阈值ssthresh。

之后cwnd不再呈指数增长从而进入拥塞避免阶段(注cwnd增长的单位是MSS),当然如果在慢启动阶段还未到达阈值ssthresh而出现丢包时进入快速重传等阶段,需要注意的是如果网络状况良好RTT时间很短,那么慢启动阶段将很快到达一个比较高的发送速率,所以将慢启动理解为试探启动更形象。

  • 拥塞避免

当慢启动阶段cwnd的值到达ssthresh时就不再疯狂增长,进入更加理性的线性阶段直至发送丢包,本次的阈值ssthresh是上一次发生丢包时cwnd的1/2,因此这是一个承上启下的过程。

本次发送丢包时仍然会调整ssthresh的值,具体拥塞避免增长过程:发送方每收到一个ACK数据包时将cwnd=cwnd+1/cwnd,每经过一个RTT将cwnd自增1。

  • 超时重传和快速重传

TCP作为一个可靠的协议面临的很大的问题就是丢包,丢包就要重传因此发送方需要根据接收方回复的ACK来确认是否丢包了,并且发送方在发送数据之后启动定时器,如图所示:

RTO是随着复杂网络环境而动态变化的,在拥塞控制中发生超时重传将会极大拉低cwnd,如果网络状况并没有那么多糟糕,偶尔出现网络抖动造成丢包或者阻塞也非常常见,因此触发的慢启动将降低通信性能,故出现了快速重传机制。

所谓快速重传时相比超时重传而言的,重发等待时间会降低并且后续尽量避免慢启动,来保证性能损失在最小的程度,如图所示:

快速重传和超时重传的区别在于cwnd在发生拥塞时的取值,超时重传会将cwnd修改为最初的值,也就是慢启动的值,快速重传将cwnd减半,二者都将ssthresh设置为cwnd的一半。

从二者的区别可以看到,快速重传更加主动,有利于保证链路的传输性能,但是有研究表明3个ACK的机制同样存在问题,本文就不做深入阐述了,感兴趣的读者可以自主查阅。

快速重传是基于对网络状况没有那么糟糕的假设,因此在实际网络确实还算好的时候,快速重传还是很有用的,在很差的网络环境很多算法都很难保证效率的。

  • 快速恢复

在快速重传之后就会进入快速恢复阶段,此时的cwnd为上次发生拥塞时的cwnd的1/2,之后cwnd再线性增加重复之前的过程。

4.弱网环境的AIMD特性

我们知道在网络链路中连接的数量是动态变化且数量巨大的,每一条连接都面临着一个黑盒子式的网络环境,这并不像我们平时出行时看看地图就知道哪里堵了,为了维护一个好的网络环境,每一条连接都需要遵守一些约定。

如果连接端都无所顾忌地发生数据包,那么网络链路很快就到了瓶颈了,数据通信完全无法保障,所以要到达一个稳定高效的网络环境还是需要费很大心思的,这其中有两个重要的概念:公平性和收敛性。

说来惭愧笔者在网络上找了很多资料去理解TCP拥塞控制的公平性和收敛性,但是仍然没有获得一个很好的权威解释,所以只能结合一些资料和自身的理解去阐述所谓的公平性和收敛性。

笔者认为公平性是相对于网络链路中的所有连接而言的,这些共享链路的连接启动和结束的时间不同,在实际的交互过程中每条连接占有带宽的机会是均等的,并且由于带宽限制连接双方通信的数据量是动态调整并且近似收敛于某个值,也就是呈现一个锯齿状或者更加平滑的波动曲线,对于基于丢包的拥塞控制算法而言AIMD线性增乘性减策略起了关键控制作用。

接下来我们来重点看下AIMD特性,先来贴一张经典的图,直观看AIMD的过程:

看看维基百科对于AIMD的定义:

The additive-increase/multiplicative-decrease(AIMD) algorithm is a feedback control algorithm best known for its use in TCP congestion control.

AIMD combines linear growth of the congestion window with an exponential reduction when congestion is detected.

Multiple flows using AIMD congestion control will eventually converge to use equal amounts of a shared link.

The related schemes of multiplicative-increase/multiplicative-decrease (MIMD) and additive-increase/additive-decrease (AIAD) do not reach stability.

简单翻译一下:线性增加乘性减少算法是一个反馈控制算法,因其在TCP拥塞控制中的使用而广为人知,AIMD将线性增加拥塞窗口和拥塞时乘性减少窗口相结合,基于AIMD的多个连接理想状态下会达到最终收敛,共享相同数量的网络带宽,与其相关的乘性增乘性减MIMD策略和增性加增性减少AIAD都无法保证稳定性。

AIMD相比MIMD和AIAD在连接进入拥塞避免阶段使用试探线性加策略而不是乘性加策略更加安全,在探测丢包时则大幅度乘性减少到1/2这样对于缓解拥塞会有比较好的效果更加快速,相反如果探测到丢包时采用线性减少AD可能拥塞持续的时间会更长,总体来说AIMD算是一个比较简单实用的工程版本的反馈控制,也具备可工程收敛性,因而被广泛实用。

时间拉回20多年前,在互联网早期几乎所有的设备都是通过有线网络进行连接通信的,这也是拥塞控制在设计之后一直都起到不错作用的重要因素,有线连接的网络稳定性比较好,因此把丢包作为网络拥堵的一个特征也很正常。

再拉回到现在,从2010年之后移动互联网蓬勃发展,移动终端的持有量已经可以称为海量,无线网络的引入让网络环境变得更加复杂,因此不稳定丢包变得更加频繁,但是这时的丢包就不一定是网络拥堵造成的了,因为整个数据包经过多重路由、交换机、基站等基础通信设备每个环节都可能发生异常。

在弱网环境下,尤其是移动互联网中之前的基于AIMD的拥塞控制策略可能会由于丢包的出现而大幅降低网络吞吐量,从而对网络带宽的利用率也大大下降,这时我们采用更加激进的控制策略,或许可以获得更好的效果和用户体验。

恶意丢包的情况下,基于AIMD的拥塞控制确实就相当于被限速了,因为AIMD确实有些保守谨慎了,这个其实也很好理解的哈。

我们都知道在移动网络环境下是由终端以无线形式和附近的基站交互数据,之后数据传输至核心网,最后落到具体的服务器所在的有线网络,其中最后一公里的区域属于高延时场景,有线网络属于低延时高带宽场景。

在国外有相关实验证明弱网环境下RTT的变化对于使用传统拥塞控制算法下网络吞吐量的影响,数据和曲线如图所示:

实验含义:RTT的增大影响了比如CUBIC这类拥塞控制算法的慢启动等阶段,我们知道慢启动阶段每经过1个RTT周期拥塞窗口cwnd将加倍,但是更大的RTT就意味着发送方以很低的速率发送数据,更多的时间是空闲的,发包的加速度极大将低了,所以整个吞吐量就下降很明显。

看下实验者的原文表述:

The delay before acknowledgment packets are received (= latency) will have an impact on how fast the TCP congestion window increases (hence the throughput).

When latency is high, it means that the sender spends more time idle (not sending any new packets), which reduces how fast throughput grows.

5.BBR算法基本原理

BBR算法是个主动的闭环反馈系统,通俗来说就是根据带宽和RTT延时来不断动态探索寻找合适的发送速率和发送量。

看下维基百科对BBR算法的说明和资料:

相关文献:https://queue.acm.org/detail.cfm?id=3022184

TCP BBR(Bottleneck Bandwidth and Round-trip propagation time)是由Google设计,并于2016年发布的拥塞算法,以往大部分拥塞算法是基于丢包来作为降低传输速率的信号,而BBR基于模型主动探测。

该算法使用网络最近出站数据分组当时的最大带宽和往返时间来创建网络的显式模型。数据包传输的每个累积或选择性确认用于生成记录在数据包传输过程和确认返回期间的时间内所传送数据量的采样率。

该算法认为随着网络接口控制器逐渐进入千兆速度时,分组丢失不应该被认为是识别拥塞的主要决定因素,所以基于模型的拥塞控制算法能有更高的吞吐量和更低的延迟,可以用BBR来替代其他流行的拥塞算法例如CUBIC。Google在YouTube上应用该算法,将全球平均的YouTube网络吞吐量提高了4%,在一些国家超过了14%。BBR之后移植入Linux内核4.9版本,并且对于QUIC可用。

5.1 基于丢包反馈策略可能在的问题

基于丢包反馈属于被动式机制,根源在于这些拥塞控制算法依据是否出现丢包事件来判断网络拥塞做减窗调整,这样就可能会出现一些问题:

  • 丢包即拥塞
    现实中网络环境很复杂会存在错误丢包,很多算法无法很好区分拥塞丢包和错误丢包,因此在存在一定错误丢包的前提下在某些网络场景中并不能充分利用带宽。
  • 缓冲区膨胀问题BufferBloat
    网络连接中路由器、交换机、核心网设备等等为了平滑网络波动而存在缓冲区,这些缓存区就像输液管的膨胀部分让数据更加平稳,但是Loss-Based策略在最初就像网络中发生数据类似于灌水,此时是将Buffer全部算在内的,一旦buffer满了,就可能出现RTT增加丢包等问题,就相当于有的容量本不该算在其中,但是策略是基于包含Buffer进行预测的,特别地在深缓冲区网络就会出现一些问题。
  • 网络负载高但无丢包事件
    假设网络中的负载已经很高了,只要没有丢包事件出现,算法就不会主动减窗降低发送速率,这种情况下虽然充分利用了网络带宽,同时由于一直没有丢包事件出现发送方仍然在加窗,表现出了较强的网络带宽侵略性,加重了网络负载压力。
  • 高负载丢包
    高负载无丢包情况下算法一直加窗,这样可以预测丢包事件可能很快就出现了,一旦丢包出现窗口将呈现乘性减少,由高位发送速率迅速降低会造成整个网络的瞬时抖动性,总体呈现较大的锯齿状波动。
  • 低负载高延时丢包
    在某些弱网环境下RTT会增加甚至出现非拥塞引起丢包,此时基于丢包反馈的拥塞算法的窗口会比较小,对带宽的利用率很低,吞吐量下降很明显,但是实际上网络负载并不高,所以在弱网环境下效果并不是非常理想。

5.2 TCP BBR算法基本原理

前面我们提到了一些Loss-Based算法存在的问题,TCP BBR算法是一种主动式机制,简单来说BBR算法不再基于丢包判断并且也不再使用AIMD线性增乘性减策略来维护拥塞窗口,而是分别采样估计极大带宽和极小延时,并用二者乘积作为发送窗口,并且BBR引入了Pacing Rate限制数据发送速率,配合cwnd使用来降低冲击。

5.2.1 一些术语

  • BDP

    BDP是Bandwidth-Delay Product的缩写,可以翻译为带宽延时积,我们知道带宽的单位是bps(bit per second),延时的单位是s,这样BDP的量纲单位就是bit,从而我们知道BDP就是衡量一段时间内链路的数据量的指标。这个可以形象理解为水管灌水问题,带宽就是水管的水流速度立方米/s,延时就是灌水时间单位s,二者乘积我们就可以知道当前水管内存储的水量了,这是BBR算法的一个关键指标,来看一张陶辉大神文章中的图以及一些网络场景中的BDP计算:

  • 长肥网络
    我们把具有长RTT往返时间和高带宽的网络成为长肥网络或者长肥管道,它的带宽延时积BDP很大大,这种网络理论上吞吐量很大也是研究的重点。
  • TCP Pacing机制
    可以简单地理解TCP Pacing机制就是将拥塞控制中数据包的做平滑发送处理,避免数据的突发降低网络抖动。

5.2.2 带宽和延时的测量

BBR算法的一些思想在之前的基于延时的拥塞控制算法中也有出现,其中必有有名的是TCP WestWood算法。

TCP Westwood改良自New Reno,不同于以往其他拥塞控制算法使用丢失来测量,其通过对确认包测量来确定一个合适的发送速度,并以此调整拥塞窗口和慢启动阈值。其改良了慢启动阶段算法为敏捷探测和设计了一种持续探测拥塞窗口的方法来控制进入敏捷探测,使链接尽可能地使用更多的带宽。

TCP WestWood算法也是基于带宽和延时乘积进行设计的,但是带宽和延时两个指标无法同时测量,因为这两个值是有些矛盾的极值,要测量最大带宽就要发送最大的数据量但是此时的RTT可能会很大,如果要测量最小的RTT那么久意味着数据量非常少最大带宽就无法获得。

TCP BBR算法采用交替采样测量两个指标,取一段时间内的带宽极大值和延时极小值作为估计值,具体的实现本文就不展开了。

5.2.3 发送速率和RTT曲线

前面提到了BBR算法核心是寻找BDP最优工作点,在相关论文中给出了一张组合的曲线图,我们一起来看下:

1.曲线图示说明:
这张图是由两个图组合而成,目前是展示[数据发送速率vs网络数据]和[RTTvs网络数据]的关系,横轴是网络数据数量。

两个纵轴从上到下分别为RTT和发送速率,并且整个过程分为了3个阶段:应用限制阶段、带宽限制阶段、缓冲区限制阶段。

2.曲线过程说明:

  • app limit应用限制阶段
    在这个阶段是应用程序开始发送数据,目前网络通畅RTT基本保持固定且很小,发送速率与RTT成反比,因此发送速率也是线性增加的,可以简单认为这个阶段有效带宽并没有达到上限,RTT是几乎固定的没有明显增长。
  • band limit带宽限制阶段
    随着发送速率提高,网络中的数据包越来越多开始占用链路Buffer,此时RTT开始增加发送速率不再上升,有效带宽开始出现瓶颈,但是此时链路中的缓存区并没有占满,因此数据还在增加,RTT也开始增加。
  • buffer limit缓冲区限制阶段
    随着链路中的Buffer被占满,开始出现丢包,这也是探测到的最大带宽,这个节点BDP+BufferSize也是基于丢包的控制策略的作用点。

3.一些看法

网上有一些资料都提及到了这张图,其中的一些解释也并不算非常清晰,结合这些资料和自己的认识,笔者认为在网络链路的缓存区没有被使用时RTT为最小延时MinRTT,在网络链路缓冲区被占满时出现最大带宽MaxBW(链路带宽+链路缓存),但是此时的MaxBW和MinRTT并不是最优的而是水位比较高的水平,有数据表明按照2ln2的增益计算此时为3BDP,整个过程中MinRTT和MaxBW是分开探测的,因为这二者是不能同时被测量的。

5.2.4 BBR算法的主要过程

BBR算法和CUBIC算法类似,也同样有几个过程:StartUp、Drain、Probe_BW、Probe_RTT,来看下这几个状态的迁移情况:

  • StartUp慢启动阶段
    BBR的慢启动阶段类似于CUBIC的慢启动,同样是进行探测式加速区别在于BBR的慢启动使用2ln2的增益加速,过程中即使发生丢包也不会引起速率的降低,而是依据返回的确认数据包来判断带宽增长,直到带宽不再增长时就停止慢启动而进入下一个阶段,需要注意的是在寻找最大带宽的过程中产生了多余的2BDP的数据量,关于这块可以看下英文原文的解释:

To handle Internet link bandwidths spanning 12 orders of magnitude, Startup implements a binary search for BtlBw by using a gain of 2/ln2 to double the sending rate while delivery rate is increasing. This discovers BtlBw in log2BDP RTTs but creates up to 2BDP excess queue in the process.

  • Drain排空阶段
    排空阶段是为了把慢启动结束时多余的2BDP的数据量清空,此阶段发送速率开始下降,也就是单位时间发送的数据包数量在下降,直到未确认的数据包数量<BDP时认为已经排空,也可以认为是RTT不再下降为止,排空阶段结束。
  • ProbeBW带宽探测阶段
    经过慢启动和排空之后,目前发送方进入稳定状态进行数据的发送,由于网络带宽的变化要比RTT更为频繁,因此ProbeBW阶段也是BBR的主要阶段,在探测期中增加发包速率如果数据包ACK并没有受影响那么就继续增加,探测到带宽降低时也进行发包速率下降。
  • ProbeRTT延时探测阶段
    前面三个过程在运行时都可能进入ProbeRTT阶段,当某个设定时间内都没有更新最小延时状态下开始降低数据包发送量,试图探测到更小的MinRTT,探测完成之后再根据最新数据来确定进入慢启动还是ProbeBW阶段。

我们来看一下这四个过程的示意图:

曲线说明:这两个坐标给出了10Mbps和40msRTT的网络环境下CUBIC和BBR的一个对比过程,在上面的图中蓝色表示接收者,红色表示CUBIC,绿色表示BBR,在下面的图中给出了对应上图过程中的RTT波动情况,红色代表CUBIC,绿色代表BBR。

5.3 TCP-BBR算法效果

有一些文章认为BBR有鲜明的特点,把拥塞控制算法分为BBR之前和BBR之后,可见BBR还是有一定影响,但是BBR算法也不是银弹,不过可以先看看BBR算法在谷歌推动下的一些应用效果,其中包括吞吐量、RTT、丢包率影响:

从图中我们可以看到在YouTube应用BBR算法之后,就吞吐量普遍有4%左右的提升,特别地在日本的提升达到14%,RTT的下降更为明显平均降低33%,其中IN(印度地区)达到50%以上,在丢包率测试中BBR并不想CUBIC那么敏感,在丢包率达到5%是吞吐量才开始明显下降。


文章作者: 杰克成
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 杰克成 !
评论
  目录