MPTCP OFO 패킷 큐 사이즈 측정 (in Linux kernel)

개요

본 페이지에선 OFO(Out-of-Order, OOO) 패킷이 무엇인지 알아보고 또한 OFO 패킷으로 인해 어떠한 현상이 일어나는지 살펴본다. 그 후 수신측 MPTCP에서 어떻게 OFO 패킷을 저장하는 큐의 사이즈를 측정하는지 알아보도록 한다.

 

OFO(Out-of-Order) 패킷이란?

OFO 패킷은 순서에 맞지 않게 도착한 패킷을 일컫는다.

 

OFO 패킷을 이해하기 위해서는 TCP 연결을 생각해보면 쉽게 이해가 될 것이다. (TCP의 Flow Control 개념)

 

TCP는 순서번호(Sequence Number)가 올바르게 정렬된 데이터만을 상위 계층(App Layer)으로 전달한다.

다시말해 TCP에서 수신측으로 순서번호가 높은 패킷이 순서번호가 낮은 패킷 보다 먼저 도착하게 되면 순서번호가 높은 패킷들은 큐에서 대기하게 될 것이다. 이러한 순서번호가 높은 패킷을 OFO 패킷이라고 하며 이러한 패킷들은 임시적으로 OFO 큐에 저장되어 관리 된다. 이 후 순서번호가 낮은 패킷이 도착하게 되면 순서번호가 높은 패킷은 OFO 큐에서 빠져나올 수 있게된다.

 

MPTCP도 마찬가지로 TCP와 같이 올바른 순서로 정렬된 데이터만을 상위 계층(App Layer)으로 전달한다.

MPTCP는 DSN(Data Sequence Number)이라는 필드를 통해 데이터들의 순서를 정렬하며 TCP와 마찬가지로 DSN 번호가 높은 패킷이 먼저 도착하게 되면 해당 패킷은 OFO 큐에서 대기하게 된다.

 

글로만 보면 이해가 안될 수도 있으니 그림으로 설명한다. (MPTCP 관점)

 

그림 참조 : https://ieeexplore.ieee.org/document/9440790

 

다음 그림은 송신측 App에서 데이터를 전송하기 위해 MPTCP의 Send Buffer에 데이터를 밀어넣는 모습이다.

이 후 송신측 MPTCP는 Send Buffer의 데이터들을 패킷(4Layer 세그먼트) 단위로 Scheduler에게 전달한다.

Scheduler는 패킷들을 특정 TCP Subflow #1~N으로 스케줄링하여 수신측(Peer)으로 전달되게끔 한다.

 

만약, 여러 TCP에서 사용되는 네트워크 환경이 비대칭적인 환경(Asymmetric Path)일 경우 수신측 MPTCP에서는 OFO 패킷이 생성된다. (비대칭적인 네트워크 환경은 모바일 네트워크를 생각하면 된다.)

 

위 그림에서 Scheduler가 Round Robin 방식일 경우에 OFO 패킷이 생성되는 것을 설명하기 위해 1. 부터 순차적으로 설명한다.

 

1. 스케줄러가 순서 번호가 낮은 패킷을 TCP Subflow #1에 할당
2. 스케줄러가 순서 번호가 높은 패킷을 TCP Subflow #n에 할당
3. Subflow #1이 느린 속도의 네트워크라서 순서 번호가 낮은 패킷들은 도착하기 까지 오랜시간이 걸림
4. Subflow #n은 빠른 속도의 네트워크라서 순서 번호가 높은 패킷들은 #1에 할당된 패킷보다 빠르게 도착
5. recevie buffer에 순서번호가 높은 패킷이 먼저 도착해 데이터를 상위 계층으로 전달하지 못하는 현상이 발생

 

다음 5.의 패킷들이 OFO 패킷이 되는 것이며 OFO 패킷은 #1에서 전송된 패킷이 도착할 때까지 OFO 큐에 대기하게 된다.

 

OFO 패킷으로 인해 HoL(Head-of-Line) Blocking이 발생된다.

HoL Blocking이란 높은 순서번호 패킷은 도착하였지만 낮은 순서번호 패킷이 도착하지 못해 수신측 버퍼가 차단되는 현상을 뜻한다. 이러한 OFO 패킷으로 인해 HoL Blocking이 발생되면 App 영역으로 데이터를 전달하지 못해 App영역에서 실시간 서비스를 받는 애플리케이션 서비스들은 잦은 지연현상을 겪게 될 것이다.

 

즉, MPTCP에서 실시간 애플리케이션의 잦은 지연 문제를 해결하기 위해선 OFO 패킷을 줄이는 것이 핵심이 된다.

 

수신측 OFO 패킷 큐 사이즈 측정

다음은 필자가 어떠한 방법으로 수신측에서 OFO 패킷 큐 사이즈를 측정하였는지 설명한다.

이것을 읽는 독자 분들은 이것이 확실한 방법이 아니라는 것을 알아두면 좋겠다.

이것을 정리하는 주된 목적은 필자가 잊어먹지 않기 위해서 정리하는 것이다.

더 좋은 방법이 있다면 필자 또한 그 방법을 따를 것이다.

 

먼저 필자가 택한 방법은 Linux 커널에서 TCP 소켓을 관리하는 구조체인 tcp_sock 구조체를 사용한 방법이다.

이 tcp_sock 구조체의 필드 중 out_of_order_queue를 사용하였다.

out_of_order_queue는 rb_tree(red-black tree)로 관리되며 해당 트리를 순회하는 방법으로 OFO 큐 크기를 계산하였다. rb_tree의 순회방식은 중위 순회 방식이다.

 

본 페이지에서 OFO 큐 크기를 측정하기 위해선 rb_tree를 크게 이해하진 않아도 된다. 왜냐하면 rb_tree의 검색, 삭제 등의 연산을 하는 것이 아닌 모든 트리를 순회하여 큐의 크기를 알아보는 것이기 때문이다.

 

필자는 Upstream Linux Kernel이 아닌 MPTCP Linux Kernel v0.95 버전를 사용하였다.

해당 커널에서 OFO 패킷이 발생되면 net/tcp_input.c의 tcp_ofo_queue() 함수가 호출된다.

 

tcp_ofo_queue() 함수에서는 out_of_order_queue에 들어있는 OFO 패킷이 receive buffer로 들어갈 수 있는지 검사된다. 즉 OFO 패킷이 receive buffer에 순서에 맞게 배열될 수 있는지 검사된다.

 

✔ net/tcp_input.c의 tcp_ofo_queue() 함수

/* This one checks to see if we can put data from the
 * out_of_order queue into the receive_queue.
 */
void tcp_ofo_queue(struct sock *sk)
{
	struct tcp_sock *tp = tcp_sk(sk);
	__u32 dsack_high = tp->rcv_nxt;
	bool fin, fragstolen, eaten;
	struct sk_buff *skb, *tail;
	struct rb_node *p;

	p = rb_first(&tp->out_of_order_queue);
	while (p) {
		skb = rb_to_skb(p);
		if (after(TCP_SKB_CB(skb)->seq, tp->rcv_nxt))
			break;

		if (before(TCP_SKB_CB(skb)->seq, dsack_high)) {
			__u32 dsack = dsack_high;
			if (before(TCP_SKB_CB(skb)->end_seq, dsack_high))
				dsack_high = TCP_SKB_CB(skb)->end_seq;
			tcp_dsack_extend(sk, TCP_SKB_CB(skb)->seq, dsack);
		}
		p = rb_next(p);
		rb_erase(&skb->rbnode, &tp->out_of_order_queue);

		/* In case of MPTCP, the segment may be empty if it's a
		 	* non-data DATA_FIN. (see beginning of tcp_data_queue)
		 	*
		 	* But this only holds true for subflows, not for the
		 	* meta-socket.
		 	*/
		if (unlikely(!after(TCP_SKB_CB(skb)->end_seq, tp->rcv_nxt) &&
			     (is_meta_sk(sk) || !mptcp(tp) || TCP_SKB_CB(skb)->end_seq != TCP_SKB_CB(skb)->seq))) {
			SOCK_DEBUG(sk, "ofo packet was already received\n");
			tcp_drop(sk, skb);
			continue;
		}
		SOCK_DEBUG(sk, "ofo requeuing : rcv_next %X seq %X - %X\n",
			   tp->rcv_nxt, TCP_SKB_CB(skb)->seq,
			   TCP_SKB_CB(skb)->end_seq);

		tail = skb_peek_tail(&sk->sk_receive_queue);
		eaten = tail && tcp_try_coalesce(sk, tail, skb, &fragstolen);
		tcp_rcv_nxt_update(tp, TCP_SKB_CB(skb)->end_seq);
		fin = TCP_SKB_CB(skb)->tcp_flags & TCPHDR_FIN;
		if (!eaten)
			__skb_queue_tail(&sk->sk_receive_queue, skb);
		else
			kfree_skb_partial(skb, fragstolen);

		if (unlikely(fin)) {
			tcp_fin(sk);
			/* tcp_fin() purges tp->out_of_order_queue,
			 	* so we must end this loop right now.
			 	*/
			break;
		}
	}
    
    /* OFO 큐 크기 측정 */
    if( jiffies - old_jiffies >= HZ/10 ){
    	old_jiffies = jiffies;
        struct tcphdr* tcph = tcp_hdr(skb);
        if((be16_to_cpu(tcph->dest) == 5201) && mptcp(tp)){
        	int count = 0;
            	struct rb_node *node;
            	for(node=rb_first(&tp->out_of_order_queue); node; node=rb_next(node))
            		count++;
            	printk("queue len : %u", count);
        }
    }
}

tcp_ofo_queue() 함수의 마지막 줄 부분 코드를 추가하였으며 급하게 추가한지라 tcp_ofo_queue() 함수에 대한 자세한 분석은 하지 않았다.

 

함수를 대충 살펴보았을 때 OFO 큐에 존재하는 패킷이 순서가 맞춰지면 해당 패킷은 큐에서 삭제가 되는 것 같고 또한, receive buffer에 OFO 패킷이 이미 존재한다면 해당 OFO 패킷은 큐에서 삭제가 되는 것 같다. 그리고 OFO 패킷이 발생했지만 이미 연결이 FIN된 상태라면 out_of_order_queue 내부의 패킷들은 모두 삭제되는 것 같다. (확실하진 않으니 무조건적인 믿음은 양해 부탁드립니당..)

 

다시 본론으로 돌아와 tcp_ofo_queue() 함수의 끝에 줄에 있는 /* OFO 큐 크기 측정 */ 주석 아래 부분에 OFO 큐 크기를 측정하는 코드를 추가하였다.

 

해당 코드에서 보이는 jiffies와 HZ는 커널 내에 존재하는 전역변수로 생각하면 된다. jiffies와 HZ는 커널 타이머라고 이해하면 된다. HZ는 시스템의 초당 jiffies 반복 횟수이다. 즉 jiffies가 1초동안 HZ만큼 커지게 되는 것이다.

 

if(jiffies - old_jiffies >= HZ/10)을 통해서 알 수 있듯이 OFO 패킷 측정은 0.1초가 지난 이후에만 수행할 수 있도록 하였다. 만약 0.1초가 지났다면 out_of_order_queue에 저장되어 있던 소켓 버퍼인 skb의 TCP 패킷 부분을 캡쳐한 뒤 본 실험에서 타겟하는 포트인지 확인하고 또한, tcp_ofo_queue() 함수의 매개변수로 input된 소켓이 MPTCP 소켓인지 확인한다.

 

이러한 과정을 거치게되면 해당 패킷이 실험에서 타겟하는 프로그램에서 수신해야 하는 OFO 패킷임을 알 수 있게 된다. 최종적으로 out_of_order_queue의 가장 첫번째 노드부터 끝 노드까지의 총 노드의 개수를 세고 그렇게 되면 총 큐의 길이를 알 수 있게 된다. 추가적으로 총 큐의 길이에 skb의 필드 중 truesize(소켓 버퍼 사이즈)를 곱하여 총 OFO 큐 크기를 계산하였다. (해당 코드에는 존재하지 않으며 MPTCP 패킷을 분석해본 뒤 일반적으로 발생된 소켓 버퍼 사이즈로 곱해 주었다.)

 

---

Ref..

• https://github.com/multipath-tcp/mptcp/blob/mptcp_v0.95
• https://ieeexplore.ieee.org/document/9440790