패킷 분류 알고리즘 (Packet Classification)

네트워크 패킷의 헤더 필드(5-tuple 등)를 규칙 집합(ruleset)과 대조하여 해당 패킷의 처리 방식을 결정하는 패킷 분류(Packet Classification) 알고리즘의 이론과 구현을 다룹니다. 선형 탐색, 트라이, 결정 트리(HiCuts/HyperCuts), 튜플 공간 탐색(Tuple Space Search), RFC(Recursive Flow Classification), TCAM 등 주요 접근법의 원리·복잡도·트레이드오프를 비교하고, 리눅스 커널의 cls_u32, cls_flower, cls_bpf 및 하드웨어 오프로드 구현까지 살펴봅니다.

기초 개념 — 네트워크 패킷의 구조

패킷 분류를 이해하려면 먼저 네트워크 패킷이 무엇인지, 그리고 패킷의 어떤 부분을 보고 분류하는지를 알아야 합니다. 이 섹션에서는 네트워킹 초보자를 위해 기초 개념을 설명합니다.

패킷이란?

인터넷을 통해 데이터를 보낼 때, 데이터는 한꺼번에 전송되지 않고 작은 조각(패킷)으로 나뉘어 전송됩니다. 각 패킷에는 헤더(Header)와 페이로드(Payload)가 있습니다.

/* 네트워크 패킷의 기본 구조 */

┌─────────────────────────────────────────────────────┐
│                    이더넷 헤더 (14바이트)               │
│  ┌──────────┬──────────┬──────────┐                 │
│  │ 목적지 MAC │ 출발지 MAC │ EtherType│                 │
│  │  (6바이트) │  (6바이트) │ (2바이트) │                 │
│  └──────────┴──────────┴──────────┘                 │
├─────────────────────────────────────────────────────┤
│                     IP 헤더 (20바이트~)                │
│  ┌────┬────┬──────┬──────┬────────┬────────┐       │
│  │버전 │길이 │ TTL  │프로토콜│ 출발지 IP │ 목적지 IP │       │
│  │(4b)│(4b)│(8b)  │ (8b) │ (32비트) │ (32비트) │       │
│  └────┴────┴──────┴──────┴────────┴────────┘       │
├─────────────────────────────────────────────────────┤
│                  TCP/UDP 헤더 (8~20바이트)              │
│  ┌──────────┬──────────┬───────────────┐            │
│  │ 출발지 포트 │ 목적지 포트 │ 시퀀스/플래그... │            │
│  │  (16비트)  │  (16비트)  │               │            │
│  └──────────┴──────────┴───────────────┘            │
├─────────────────────────────────────────────────────┤
│                   페이로드 (실제 데이터)                 │
│  (웹 페이지, 파일, 이메일 내용 등)                        │
└─────────────────────────────────────────────────────┘

5-tuple — 패킷 분류의 핵심 필드

패킷 분류에서 가장 많이 사용하는 5개 필드를 5-tuple이라고 합니다. 이 5개 필드만으로도 "어떤 컴퓨터가 어떤 서비스에 어떻게 접속하는지"를 식별할 수 있습니다.

/* C 구조체로 표현한 5-tuple */
struct five_tuple {
    uint32_t src_ip;      /* 출발지 IP: 예) 192.168.1.100 = 0xC0A80164 */
    uint32_t dst_ip;      /* 목적지 IP: 예) 10.1.2.3     = 0x0A010203 */
    uint16_t src_port;    /* 출발지 포트: 예) 49152 (클라이언트 임시 포트) */
    uint16_t dst_port;    /* 목적지 포트: 예) 80 (HTTP 서버) */
    uint8_t  protocol;    /* 프로토콜: TCP=6, UDP=17, ICMP=1 */
};

/* 실제 패킷에서 5-tuple을 추출하는 함수 */
void extract_five_tuple(const uint8_t *pkt, struct five_tuple *ft)
{
    const struct iphdr *ip = (struct iphdr *)(pkt + 14); /* 이더넷 14바이트 */
    ft->src_ip   = ntohl(ip->saddr);        /* 네트워크 → 호스트 바이트 순서 */
    ft->dst_ip   = ntohl(ip->daddr);
    ft->protocol = ip->protocol;

    if (ip->protocol == IPPROTO_TCP || ip->protocol == IPPROTO_UDP) {
        const uint16_t *ports = (uint16_t *)(pkt + 14 + ip->ihl * 4);
        ft->src_port = ntohs(ports[0]);     /* TCP/UDP 헤더 첫 2바이트 */
        ft->dst_port = ntohs(ports[1]);     /* TCP/UDP 헤더 다음 2바이트 */
    } else {
        ft->src_port = ft->dst_port = 0;
    }
}

왜 패킷을 분류해야 하는가?

네트워크 장비(라우터, 방화벽, 스위치)는 초당 수백만~수십억 개의 패킷을 처리합니다. 각 패킷에 대해 "이 패킷을 어떻게 처리할 것인가?"를 빠르게 결정해야 합니다.

규칙(Rule)의 구조

패킷 분류 규칙은 "조건 + 액션"으로 구성됩니다. 조건은 5-tuple의 각 필드에 대한 매칭 조건이고, 액션은 매칭된 패킷에 적용할 처리입니다.

/* 분류 규칙의 C 구조체 */
struct classify_rule {
    /* === 매칭 조건 === */
    uint32_t src_ip;          /* 출발지 IP 주소 */
    uint32_t src_mask;        /* 출발지 서브넷 마스크 (예: /24 → 0xFFFFFF00) */
    uint32_t dst_ip;          /* 목적지 IP 주소 */
    uint32_t dst_mask;        /* 목적지 서브넷 마스크 */
    uint16_t src_port_min;    /* 출발지 포트 범위 시작 (0=와일드카드) */
    uint16_t src_port_max;    /* 출발지 포트 범위 끝   (65535=와일드카드) */
    uint16_t dst_port_min;    /* 목적지 포트 범위 시작 */
    uint16_t dst_port_max;    /* 목적지 포트 범위 끝 */
    uint8_t  protocol;        /* 프로토콜 (0=와일드카드) */

    /* === 메타데이터 === */
    int      priority;        /* 우선순위 (숫자가 작을수록 높음) */
    int      action;          /* 액션: ALLOW=1, DROP=0 */
    char     name[16];        /* 규칙 이름 (예: "R1") */
};

/* 패킷이 규칙에 매칭되는지 검사하는 함수 */
int rule_matches(const struct classify_rule *rule,
                 const struct five_tuple *pkt)
{
    /* 1. 출발지 IP: 서브넷 마스크를 적용하여 비교 */
    if ((pkt->src_ip & rule->src_mask) != (rule->src_ip & rule->src_mask))
        return 0;  /* 불매칭 */

    /* 2. 목적지 IP: 동일 방식 */
    if ((pkt->dst_ip & rule->dst_mask) != (rule->dst_ip & rule->dst_mask))
        return 0;

    /* 3. 프로토콜: 0이면 와일드카드 (모든 프로토콜 매칭) */
    if (rule->protocol != 0 && rule->protocol != pkt->protocol)
        return 0;

    /* 4. 출발지 포트: 범위 검사 */
    if (pkt->src_port < rule->src_port_min || pkt->src_port > rule->src_port_max)
        return 0;

    /* 5. 목적지 포트: 범위 검사 */
    if (pkt->dst_port < rule->dst_port_min || pkt->dst_port > rule->dst_port_max)
        return 0;

    return 1;  /* 모든 필드 매칭! */
}

/* 매칭 예시 추적:
 * 규칙: R1 = {src=192.168.1.0/24, dst=10.0.0.0/8, dport=80, proto=TCP}
 * 패킷: {src=192.168.1.100, dst=10.1.2.3, sport=49152, dport=80, proto=TCP}
 *
 * 단계 1: src_ip & mask = 192.168.1.100 & 0xFFFFFF00 = 192.168.1.0
 *         rule.src_ip & mask = 192.168.1.0 & 0xFFFFFF00 = 192.168.1.0 → 일치 ✓
 * 단계 2: dst_ip & mask = 10.1.2.3 & 0xFF000000 = 10.0.0.0
 *         rule.dst_ip & mask = 10.0.0.0 & 0xFF000000 = 10.0.0.0 → 일치 ✓
 * 단계 3: protocol = TCP(6) == TCP(6) → 일치 ✓
 * 단계 4: src_port 49152 ∈ [0, 65535] → 일치 ✓ (와일드카드)
 * 단계 5: dst_port 80 ∈ [80, 80] → 일치 ✓
 * 결과: R1 매칭!
 */

패킷 분류 문제 정의

다차원 매칭 문제

패킷 분류는 패킷 헤더의 d개 필드를 N개 규칙으로 구성된 규칙 집합(ruleset, classifier)과 대조하여, 매칭되는 가장 높은 우선순위의 규칙을 찾는 문제입니다. 전통적인 5-tuple 분류에서 각 규칙은 다음 필드를 지정합니다.

성능 지표

패킷 분류 알고리즘을 평가하는 세 가지 핵심 지표가 있습니다.

• 분류 속도(Classification Speed): 패킷당 메모리 접근 횟수 — 와이어 스피드를 달성하려면 소수의 접근으로 분류를 완료해야 합니다
• 메모리 사용량(Storage): 사전 계산 테이블이 차지하는 공간 — 캐시/SRAM 적합 여부가 실제 성능을 좌우합니다
• 업데이트 비용(Update Cost): 규칙 추가·삭제 시 자료구조 재구성 시간 — 동적 환경에서는 증분 업데이트가 필수입니다

기하학적 해석 (Geometric Interpretation)

패킷 분류를 기하학적으로 해석하면 본질적인 어려움이 더 명확해집니다. d차원 공간에서 각 규칙은 초직사각형(hyper-rectangle)을 정의하고, 패킷은 이 공간의 한 점입니다. 패킷 분류 문제는 곧 그 점을 포함하는 가장 높은 우선순위의 초직사각형을 찾는 것입니다.

• 각 필드의 접두사 조건 → 해당 차원의 구간(interval)
• 와일드카드 (*) → 전체 차원을 덮는 구간
• 5-tuple 규칙 하나 = 5차원 초직사각형
• 패킷 = 5차원 공간의 점 (SrcIP, DstIP, SrcPort, DstPort, Proto)

복잡도 하한 (Complexity Lower Bounds)

패킷 분류의 본질적인 어려움은 이론적으로 증명된 하한(lower bound)에서 드러납니다. 어떤 알고리즘을 설계해도 피할 수 없는 근본적인 제약이 존재합니다.

이 하한의 실용적 함의는: 어떤 소프트웨어 알고리즘도 "빠른 분류 + 작은 메모리 + 빠른 업데이트"를 동시에 달성할 수 없습니다. RFC는 메모리를 희생하여 분류 속도를 얻고, 튜플 공간은 다소 느린 분류 대신 업데이트 속도를 얻습니다. TCAM은 이 제약을 하드웨어 병렬성으로 우회하는 유일한 방법이지만, 전력과 비용 제약이 있습니다.

규칙 집합 예시

이후 모든 알고리즘 설명에서 공통으로 사용할 예시 규칙 집합을 정의합니다. 이 8개 규칙을 기준으로 각 알고리즘의 동작을 추적합니다.

테스트 패킷: Src=192.168.1.100, Dst=10.1.2.3, SrcPort=49152, DstPort=80, Proto=TCP

이 패킷은 R1(192.168.1.0/24 → 10.0.0.0/8, dport=80, TCP)과 R6(10.0.0.0/8은 Src 불일치), R8(와일드카드)에 매칭됩니다. 최고 우선순위 R1(ALLOW)이 선택되어야 합니다.

선형 탐색 (Linear Search)

가장 단순한 방식은 규칙을 우선순위 순서대로 순차 비교하는 것입니다. 첫 번째 매칭 규칙을 반환하거나, 모든 규칙을 비교하여 최고 우선순위 매칭을 선택합니다.

동작 과정

/* 의사코드: 선형 탐색 분류 */
function linear_classify(packet, rules[N]):
    best_match = DEFAULT_RULE
    for i = 0 to N-1:
        if match(packet, rules[i]):
            if rules[i].priority > best_match.priority:
                best_match = rules[i]
    return best_match

예시 규칙 집합으로 추적

테스트 패킷 (192.168.1.100, 10.1.2.3, 49152, 80, TCP)으로 선형 탐색을 추적합니다.

복잡도

리눅스 커널에서의 선형 탐색

리눅스 커널의 TC filter chain 평가 방식이 본질적으로 이 구조입니다. tc filter를 prio 순서로 순차 평가하며, 첫 매칭에서 종료하거나 continue 액션으로 다음 필터로 넘어갑니다.

/* net/sched/cls_api.c — tcf_classify() 핵심 루프 */

int tcf_classify(struct sk_buff *skb,
                const struct tcf_proto *tp,
                struct tcf_result *res, bool compat_mode)
{
    for (; tp; tp = rcu_dereference_bh(tp->next)) {
        /* 각 filter를 prio 순서로 순차 평가 */
        int err = tp->classify(skb, tp, res);
        if (err >= 0)
            return err;            /* 매칭! → 액션 적용 */
        if (err == TC_ACT_UNSPEC)
            continue;              /* continue → 다음 filter */
    }
    return TC_ACT_UNSPEC;               /* 매칭 없음 → 기본 정책 */
}

최적화 변형: 조기 종료

선형 탐색의 핵심 최적화는 조기 종료(early termination)입니다. 규칙을 우선순위 내림차순으로 정렬하면, 첫 매칭 시점에서 즉시 반환할 수 있습니다(이후 규칙은 모두 낮은 우선순위). 리눅스 TC의 prio 기반 체인이 이 방식입니다. 또한 필드 비교 시에도 첫 번째 불매칭 필드에서 해당 규칙을 건너뛰는 필드 수준 조기 종료가 가능합니다.

선형 탐색 최적화 기법 상세

단순한 조기 종료 외에도 선형 탐색의 성능을 실용적인 수준으로 끌어올리는 다양한 기법이 존재합니다.

블룸 필터 사전 검사 (Bloom Filter Pre-screening)

각 규칙 그룹에 대해 블룸 필터(Bloom Filter)를 구축하면, 불가능한 규칙 그룹 전체를 단 한 번의 해시 연산으로 건너뛸 수 있습니다. 블룸 필터는 공간 효율적인 확률적 자료구조로, 거짓 양성(false positive)은 가능하지만 거짓 음성(false negative)은 불가능합니다. 즉, "이 패킷이 이 그룹에 매칭 가능성 없음"은 100% 확실하지만, "매칭 가능성 있음"은 실제로 없을 수도 있습니다.

/* 블룸 필터 기반 선형 탐색 최적화 */
struct rule_group {
    bloom_filter_t  bf;          /* 그룹의 가능한 (srcip, dstip) 쌍 */
    rule_t          rules[];     /* 실제 규칙 배열 */
    int             num_rules;
};

int bloom_filter_classify(packet_t *pkt, rule_group_t groups[], int ng) {
    for (int g = 0; g < ng; g++) {
        /* O(k) 해시 연산으로 그룹 전체 skip 여부 결정 */
        if (!bloom_query(&groups[g].bf, pkt->srcip, pkt->dstip))
            continue;    /* 확실히 매칭 없음 → 그룹 전체 skip */

        /* 매칭 가능성 있는 그룹만 선형 탐색 */
        for (int r = 0; r < groups[g].num_rules; r++) {
            if (match(pkt, &groups[g].rules[r]))
                return groups[g].rules[r].action;
        }
    }
    return DEFAULT_ACTION;
}

블룸 필터의 오탐률(false positive rate)은 비트 배열 크기와 해시 함수 수로 조절합니다. 실용적인 설정에서 오탐률을 1% 이하로 유지하면서 99%의 그룹을 건너뛸 수 있습니다.

필드 순서 최적화 (Field Ordering)

선형 탐색에서 필드를 비교하는 순서는 평균 비교 횟수에 큰 영향을 미칩니다. 가장 많은 규칙을 제거하는(discriminating) 필드를 먼저 비교하면 조기 종료가 더 자주 발생합니다.

최적 필드 순서를 결정하는 기준은 해당 필드의 차별화 비율(discrimination ratio)입니다. 예를 들어, Protocol 필드가 와일드카드(*) 규칙 비율이 낮고 TCP/UDP/ICMP 등이 명시된 규칙 비율이 높다면, Protocol을 먼저 검사하는 것이 유리합니다.

/* 필드 순서 최적화: 통계 기반 */
/* 실제 트래픽 데이터로 각 필드의 discriminating power를 측정 */

/* 예: 규칙셋 통계 */
/* Protocol: 80% 규칙이 명시 → 높은 차별화 → 먼저 검사 */
/* DstPort:  60% 규칙이 명시 → 중간 차별화 */
/* SrcIP:    50% 규칙이 명시 → 중간 차별화 */
/* DstIP:    40% 규칙이 명시 → 낮은 차별화 → 나중에 검사 */
/* SrcPort:  20% 규칙이 명시 → 매우 낮음 (대부분 에페머럴 와일드카드) */

/* 최적 순서: Protocol → DstPort → SrcIP → DstIP → SrcPort */

int optimized_linear(packet_t *pkt, rule_t rules[], int N) {
    for (int i = 0; i < N; i++) {
        /* 차별화 순서대로 비교: 빠른 조기 종료 */
        if (rules[i].proto  != WILD && rules[i].proto  != pkt->proto)  continue;
        if (rules[i].dport  != WILD && rules[i].dport  != pkt->dport)  continue;
        if (!prefix_match(rules[i].srcip, pkt->srcip))                 continue;
        if (!prefix_match(rules[i].dstip, pkt->dstip))                 continue;
        if (rules[i].sport  != WILD && !range_match(rules[i].sport, pkt->sport)) continue;
        return rules[i].action;   /* 모든 필드 매칭 */
    }
    return DEFAULT_ACTION;
}

규칙 그룹화 (Rule Grouping)

공통 필드 패턴을 가진 규칙들을 그룹으로 묶으면, 첫 번째 공통 필드에서 불일치가 발생하면 그룹 전체를 건너뛸 수 있습니다. 이는 결정 트리의 단순화된 형태로 볼 수 있습니다.

/* 규칙 그룹화: Protocol별로 사전 분류 */
struct rule_group_by_proto {
    uint8_t   protocol;     /* 그룹 공통 필드 */
    rule_t    rules[];      /* 이 프로토콜의 모든 규칙 */
    int       count;
};

/* TCP 그룹: R1, R2, R5, R6 (모두 TCP 명시) */
/* UDP 그룹: R3 */
/* ICMP 그룹: R7 */
/* WILD 그룹: R4, R8 (프로토콜 와일드카드) */

int grouped_classify(packet_t *pkt, rule_groups_t groups[]) {
    int proto = pkt->proto;
    /* 해당 프로토콜 그룹만 선형 탐색 */
    search_group(&groups[proto]);      /* 예: TCP 그룹 4개 규칙 */
    search_group(&groups[WILD]);       /* 와일드카드 그룹 항상 */
}

완전한 C 구현 — 선형 탐색 분류기

아래는 실제로 컴파일하고 실행할 수 있는 수준의 선형 탐색 패킷 분류기 구현입니다. 앞서 정의한 8개 예시 규칙을 등록하고, 테스트 패킷을 분류하는 전체 과정을 보여줍니다.

/* linear_classifier.c — 완전한 선형 탐색 패킷 분류기
 *
 * 컴파일: gcc -O2 -o linear_classifier linear_classifier.c
 * 실행:   ./linear_classifier
 *
 * 이 코드는 패킷 분류의 가장 기본적인 구현을 보여줍니다.
 * 규칙을 우선순위 순서대로 순차 비교하여 첫 매칭을 반환합니다.
 */
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <arpa/inet.h>

/* ── 자료구조 정의 ── */

enum action { ACT_DROP = 0, ACT_ALLOW = 1 };

struct rule {
    char     name[8];
    int      priority;       /* 숫자가 작을수록 높은 우선순위 */
    uint32_t src_ip, src_mask;
    uint32_t dst_ip, dst_mask;
    uint16_t sport_min, sport_max;
    uint16_t dport_min, dport_max;
    uint8_t  proto;          /* 0 = 와일드카드 */
    enum action act;
};

struct packet {
    uint32_t src_ip, dst_ip;
    uint16_t src_port, dst_port;
    uint8_t  proto;
};

/* ── IP 주소 문자열 → 정수 변환 헬퍼 ── */
static uint32_t ip2u32(const char *s) {
    struct in_addr a;
    inet_pton(AF_INET, s, &a);
    return ntohl(a.s_addr);
}

static uint32_t prefix2mask(int prefix_len) {
    return prefix_len == 0 ? 0 : ~((1U << (32 - prefix_len)) - 1);
}

/* ── 단일 규칙 매칭 검사 ── */
static int match_rule(const struct rule *r, const struct packet *p)
{
    /* 각 필드를 순서대로 검사 — 하나라도 불일치하면 즉시 반환 */
    if ((p->src_ip & r->src_mask) != (r->src_ip & r->src_mask))
        return 0;
    if ((p->dst_ip & r->dst_mask) != (r->dst_ip & r->dst_mask))
        return 0;
    if (r->proto != 0 && r->proto != p->proto)
        return 0;
    if (p->src_port < r->sport_min || p->src_port > r->sport_max)
        return 0;
    if (p->dst_port < r->dport_min || p->dst_port > r->dport_max)
        return 0;
    return 1;
}

/* ── 선형 탐색 분류 ── */
static const struct rule *linear_classify(
    const struct rule rules[], int n,
    const struct packet *pkt)
{
    const struct rule *best = NULL;
    int comparisons = 0;

    for (int i = 0; i < n; i++) {
        comparisons++;
        if (match_rule(&rules[i], pkt)) {
            if (!best || rules[i].priority < best->priority)
                best = &rules[i];
            /* 최적화: 규칙이 우선순위 순이면 첫 매칭에서 종료 가능 */
        }
    }
    printf("  [선형 탐색] %d회 비교 수행\n", comparisons);
    return best;
}

/* ── 예시 규칙 집합 등록 ── */
int main(void)
{
    struct rule rules[] = {
      /*  name pri  src_ip       src_mask   dst_ip       dst_mask
       *                sport_min/max  dport_min/max  proto  action */
      { "R1", 1, 0xC0A80100, 0xFFFFFF00, 0x0A000000, 0xFF000000,
                 0, 65535,  80, 80,   6, ACT_ALLOW },
      { "R2", 2, 0xC0A80100, 0xFFFFFF00, 0x0A000000, 0xFF000000,
                 0, 65535, 443, 443,  6, ACT_ALLOW },
      { "R3", 3, 0xC0A80000, 0xFFFF0000, 0, 0,
                 0, 65535,  53, 53,  17, ACT_ALLOW },
      { "R4", 4, 0xAC100000, 0xFFF00000, 0xAC100000, 0xFFF00000,
                 0, 65535,   0, 65535, 0, ACT_ALLOW },
      { "R5", 5, 0, 0, 0, 0,
                 0, 65535,  22, 22,   6, ACT_DROP  },
      { "R6", 6, 0x0A000000, 0xFF000000, 0xC0A80000, 0xFFFF0000,
              1024, 65535,  80, 80,   6, ACT_ALLOW },
      { "R7", 7, 0, 0, 0, 0,
                 0, 65535,   0, 65535, 1, ACT_ALLOW },
      { "R8", 8, 0, 0, 0, 0,
                 0, 65535,   0, 65535, 0, ACT_DROP  },
    };
    int n = sizeof(rules) / sizeof(rules[0]);

    /* 테스트 패킷: (192.168.1.100, 10.1.2.3, 49152, 80, TCP) */
    struct packet pkt = {
        .src_ip   = ip2u32("192.168.1.100"),
        .dst_ip   = ip2u32("10.1.2.3"),
        .src_port = 49152,
        .dst_port = 80,
        .proto    = 6   /* TCP */
    };

    printf("=== 선형 탐색 패킷 분류기 ===\n");
    printf("패킷: src=192.168.1.100 dst=10.1.2.3 sport=49152 dport=80 proto=TCP\n\n");

    const struct rule *result = linear_classify(rules, n, &pkt);
    if (result)
        printf("  결과: %s (우선순위 %d) → %s\n",
               result->name, result->priority,
               result->act == ACT_ALLOW ? "ALLOW" : "DROP");
    else
        printf("  결과: 매칭 없음 → 기본 정책\n");

    return 0;
}

/* 실행 결과:
 * === 선형 탐색 패킷 분류기 ===
 * 패킷: src=192.168.1.100 dst=10.1.2.3 sport=49152 dport=80 proto=TCP
 *
 *   [선형 탐색] 8회 비교 수행
 *   결과: R1 (우선순위 1) → ALLOW
 */

트라이 기반 분류

단일 필드 LPM

IP 주소 하나에 대한 최장 접두사 매칭(LPM, Longest Prefix Match)은 이진 트라이(Binary Trie)나 LC-Trie로 효율적으로 해결됩니다. 리눅스 FIB(Forwarding Information Base)가 정확히 이 구조를 사용합니다.

/* 1차원 이진 트라이 LPM 의사코드 */
function trie_lpm(root, ip_address, W=32):
    node = root
    best_match = NULL
    for bit = W-1 downto 0:
        if node.has_prefix:        /* 이 노드에 접두사가 등록됨 */
            best_match = node.prefix /* 더 긴 매칭으로 갱신 */
        next_bit = (ip_address >> bit) & 1
        if node.child[next_bit] == NULL:
            break                  /* 더 이상 내려갈 수 없음 */
        node = node.child[next_bit]
    return best_match          /* O(W) 시간, W=32 for IPv4 */

다중 비트 트라이 (Multi-bit Trie)

1비트씩 처리하는 이진 트라이는 IPv4에서 최대 32단계의 메모리 접근이 필요합니다. 다중 비트 트라이(Multi-bit Trie)는 한 번에 k비트(스트라이드, stride)씩 처리하여 트리 깊이를 줄입니다.

/* 다중 비트 트라이 (stride=8): 4단계로 IPv4 LPM */
struct mbtrie_node {
    struct mbtrie_node *children[256];  /* 2^stride = 256 자식 */
    prefix_t            prefix;         /* 이 노드에 등록된 접두사 */
};

/* stride=8 → 4단계 (32/8=4) */
prefix_t mbtrie_lpm(mbtrie_t *root, uint32_t ip) {
    prefix_t best = NULL;
    mbtrie_node *node = root;
    for (int level = 0; level < 4 && node; level++) {
        uint8_t idx = (ip >> (24 - level*8)) & 0xFF;  /* 8비트씩 */
        if (node->prefix) best = node->prefix;
        node = node->children[idx];
    }
    return best;   /* O(4) 메모리 접근 vs 이진 트라이 O(32) */
}

리눅스 커널의 FIB 라우팅 테이블은 LC-Trie(Level Compressed Trie)를 사용하여 스트라이드를 동적으로 조절합니다. 자식이 없는 노드는 축소하고, 가득 찬 노드는 스트라이드를 늘려 메모리와 속도를 균형 있게 조절합니다.

다차원 확장의 한계

문제는 이를 d차원으로 확장할 때 발생합니다. 대표적인 접근법들입니다.

Grid-of-Tries

Srinivasan et al. (1998)이 제안한 Grid-of-Tries는 첫 번째 필드(SrcIP)의 트라이 리프에 두 번째 필드(DstIP)의 트라이를 연결합니다. switch pointer를 추가하여 불필요한 서브트라이 탐색을 생략합니다.

• 2차원에서는 O(2W) 시간, O(NW) 공간으로 효율적
• 3차원 이상에서는 공간이 O(N^d-1W)로 폭발하여 실용적이지 않음

Cross-producting

각 필드에서 독립적으로 LPM을 수행한 뒤, 결과의 교차곱(cross product) 테이블에서 최종 규칙을 조회합니다. RFC 알고리즘의 직접적인 원형입니다.

• 필드 1에서 p₁개 접두사 매칭, 필드 2에서 p₂개 → 교차곱 테이블 크기: p₁ × p₂ × ... × p_d
• 최악의 경우 O(N^d) 공간이 필요하여, 규칙이 많으면 비실용적
• RFC는 이 교차곱을 동치 클래스로 축소하여 실용적으로 만든 것

Set-pruning Trie

트라이의 각 노드에 해당 접두사와 매칭되는 규칙을 미리 복제하여 저장합니다. 탐색은 빠르지만(단일 트라이 탐색), 규칙 복제로 최악 O(N^d·W) 공간이 필요합니다.

결정 트리 방식 (HiCuts / HyperCuts)

결정 트리(Decision Tree) 방식은 규칙이 정의하는 다차원 공간을 재귀적으로 분할(cutting)하여, 리프 노드에 소수의 규칙만 남도록 합니다. 패킷이 도착하면 루트에서 리프까지 트리를 탐색하고, 리프의 소수 규칙만 선형 비교합니다.

HiCuts (Hierarchical Intelligent Cuttings)

Gupta & McKeown (2000)이 제안한 HiCuts는 각 트리 노드에서 단일 차원을 선택하여 균등하게 분할합니다.

알고리즘 상세

1. 차원 선택: 현재 노드에 포함된 규칙들 중, 가장 많은 고유 프로젝션(projection)을 가진 차원을 선택합니다. 직관적으로, 규칙들이 가장 "구별되는" 차원으로 분할하면 효과적입니다
2. 분할 수 결정: 분할 수 nc는 메모리 제약(spfac, space factor)에 의해 제한됩니다. 규칙 복제까지 고려한 총 자식 규칙 수가 spfac × N을 넘지 않도록 합니다
3. 종료 조건: 리프 노드의 규칙 수가 임계값 binth(보통 8~16) 이하가 되면 분할을 멈추고, 나머지는 선형 탐색합니다

/* HiCuts 트리 구축 의사코드 */
function build_hicuts(rules[], binth, spfac):
    if |rules| <= binth:
        return LeafNode(rules)   /* 선형 탐색 구간 */

    dim = select_dimension(rules)       /* 가장 구별되는 차원 */
    nc = compute_num_cuts(rules, dim, spfac)

    node = InternalNode(dim, nc)
    for i = 0 to nc-1:
        child_rules = { r ∈ rules : r[dim] overlaps interval i }
        node.child[i] = build_hicuts(child_rules, binth, spfac)

    return node

/* HiCuts 분류 의사코드 */
function hicuts_classify(node, packet):
    if node is LeafNode:
        return linear_search(node.rules, packet)  /* O(binth) */
    interval = compute_interval(packet[node.dim], node.nc)
    return hicuts_classify(node.child[interval], packet)

HyperCuts

Singh et al. (2003)이 제안한 HyperCuts는 HiCuts를 확장하여 여러 차원을 동시에 분할합니다.

• 각 노드에서 2개 이상의 필드를 동시에 분할 → 트리 깊이가 줄어듭니다
• 2차원을 각각 4등분하면 4 × 4 = 16개 자식 → HiCuts의 4개 자식 대비 트리 깊이 절반
• 메모리 사용량과 트리 깊이의 트레이드오프를 조절할 수 있습니다
• 규칙 복제가 더 심해질 수 있으므로, 분할할 차원과 분할 수의 조합을 신중히 선택해야 합니다

예시 규칙 집합으로 HiCuts 트리 구축 추적

앞서 정의한 8개 예시 규칙에 대해 HiCuts 트리를 단계별로 구축하면서, 실제 차원 선택·분할·복제 과정을 상세히 추적합니다. SrcIP와 DstIP 두 필드(2D)만 사용하는 단순화 버전으로 설명합니다.

Step 1: 루트 노드 — 차원 선택

루트에서 8개 규칙을 분석합니다. 각 차원의 고유 구간(distinct intervals) 수를 계산합니다.

• SrcIP: 192.168.1.0/24, 192.168.0.0/16, 172.16.0.0/12, 10.0.0.0/8, * → 5개 고유 구간
• DstIP: 10.0.0.0/8, 192.168.0.0/16, 172.16.0.0/12, * → 4개 고유 구간

HiCuts는 SrcIP 차원을 선택합니다 (더 많은 고유 구간). spfac=8로 설정하면 자식당 허용 규칙 수 = 8×8/5 ≈ 12. 이를 4구간으로 분할합니다.

Step 2: SrcIP 4-way 분할

/* SrcIP 공간 4구간 분할 */
구간 0: 0.0.0.0  - 9.255.255.255   → 규칙: R7(*, ICMP), R8(*,*) → 2개
구간 1: 10.0.0.0 - 99.255.255.255  → 규칙: R6(10/8), R7, R8     → 3개
구간 2: 100.0.0.0 - 172.31.255.255 → 규칙: R4(172.16/12), R7, R8 → 3개 (+R4 복제!)
구간 3: 172.32.0.0 - 255.255.255.255 → 포함: R1(192.168.1/24), R2, R3(192.168/16), R4★, R7, R8
                                     → 규칙: 6개 (R4 복제 발생!)

규칙 복제: R4(172.16.0.0/12)는 SrcIP 구간 2와 3 양쪽에 걸쳐 있어 두 자식 노드 모두에 복제됩니다. R7과 R8도 와일드카드이므로 모든 구간에 복제됩니다.

Step 3: 구간 3의 추가 분할 (DstIP 차원 선택)

구간 3에 6개 규칙이 있어 binth=4를 초과하므로 추가 분할합니다. 이번에는 DstIP 차원이 더 많은 고유 구간을 가지므로 선택됩니다.

/* 구간 3: DstIP 분할 */
구간 3.0: 0.0.0.0  - 9.255.255.255    → R1(Dst=10/8 포함), R2, R7, R8 → 4개
구간 3.1: 10.0.0.0 - 171.255.255.255  → R1★(복제), R2★, R7, R8        → 4개 (R1,R2 복제!)
구간 3.2: 172.0.0.0 - 191.255.255.255 → R3(Dst=192.168/16 경계), R7, R8 → 3개
구간 3.3: 192.168.0.0 - 255.255.255.255 → R3★, R4★, R7, R8            → 4개

이 예시에서 총 규칙 복제 수는: R4(2회) + R7(4회) + R8(4회) + R1(1회) + R2(1회) + R3(1회) = 원래 8개 규칙이 트리 전체에서 21개 슬롯으로 복제됩니다. 복제 비율 = 21/8 ≈ 2.6배. 실제 대규모 규칙셋에서는 복제 비율이 수십 배까지 높아질 수 있습니다.

EffiCuts — 규칙 복제 최적화

Vamanan et al. (2010)의 EffiCuts는 HyperCuts의 규칙 복제 문제를 해결하기 위해 규칙 분리(separable rules) 전략을 도입했습니다. 큰 와일드카드를 가진 규칙과 작은 범위의 규칙을 별도의 서브트리로 분리하여, 와일드카드 규칙의 대량 복제를 방지합니다.

규칙 복제 문제

결정 트리 방식의 가장 큰 약점은 규칙 복제(rule replication)입니다. 하나의 규칙이 여러 분할 구간에 걸치면, 그 규칙은 해당되는 모든 자식 노드에 복사되어야 합니다. 최악의 경우 메모리 사용량이 O(N^d)로 폭발할 수 있습니다.

예시 규칙 집합에서 R8(모든 필드 와일드카드)은 어떤 분할을 하든 모든 자식에 복제됩니다. R4(172.16.0.0/12)처럼 넓은 범위의 규칙도 여러 구간에 걸쳐 복제됩니다. 이런 "큰" 규칙이 많을수록 복제 비율이 급증합니다.

튜플 공간 탐색 (Tuple Space Search)

Srinivasan et al. (1999)이 제안한 튜플 공간 탐색(Tuple Space Search)은 규칙을 접두사 길이 조합(tuple)별로 분류하여, 각 튜플에 대해 해시 테이블을 구축하는 방법입니다.

핵심 아이디어

5-tuple 규칙의 각 필드에는 접두사 길이가 있습니다. 예를 들어 규칙 192.168.0.0/16, 10.0.0.0/8, *, *, TCP의 접두사 길이 튜플은 (16, 8, 0, 0, exact)입니다. 같은 튜플을 가진 규칙들은 하나의 해시 테이블에 모아두고, 패킷의 해당 필드를 마스킹한 값으로 해시 룩업합니다.

예시 규칙 집합의 튜플 분류

예시 규칙 8개를 접두사 길이 튜플별로 분류하면:

7개 튜플이 생성됩니다. 패킷 분류 시 최악 7번의 해시 룩업이 필요하지만, 8개 규칙을 모두 선형 탐색하는 것과 대비하면 각 룩업이 O(1)이므로 큰 차이가 없어 보입니다. 그러나 규칙이 10,000개로 늘어나도 튜플 수는 보통 수십~수백 개에 불과하므로, 규칙 수가 늘수록 이점이 커집니다.

완전한 C 구현 — 튜플 공간 탐색 분류기

아래는 튜플 공간 탐색(Tuple Space Search)의 핵심 아이디어를 보여주는 완전한 구현입니다. 규칙을 접두사 길이 조합(마스크)별로 그룹화하고, 각 그룹의 해시 테이블에서 O(1) 룩업을 수행합니다.

/* tuple_space_classifier.c — 튜플 공간 탐색 분류기
 *
 * 핵심 아이디어:
 *   1. 같은 마스크 패턴의 규칙끼리 그룹(튜플)으로 묶음
 *   2. 각 튜플에 해시 테이블 구축
 *   3. 패킷 도착 시: 각 튜플에서 마스킹 → 해시 룩업 (O(1))
 *   4. 모든 튜플 순회 → 최고 우선순위 매칭 선택
 *
 * 컴파일: gcc -O2 -o tss_classifier tuple_space_classifier.c
 */
#include <stdio.h>
#include <stdint.h>
#include <string.h>

#define MAX_RULES_PER_TUPLE 16
#define HASH_BUCKETS        64

/* ── 마스크 패턴: 각 필드의 접두사 길이 ── */
struct mask_pattern {
    uint32_t src_mask;    /* 예: /24 → 0xFFFFFF00 */
    uint32_t dst_mask;    /* 예: /8  → 0xFF000000 */
    uint16_t sport_mask;  /* 0xFFFF = exact, 0 = wildcard */
    uint16_t dport_mask;
    uint8_t  proto_mask;  /* 0xFF = exact, 0 = wildcard */
};

struct rule {
    char     name[8];
    int      priority;
    uint32_t src_ip, dst_ip;
    uint16_t src_port, dst_port;
    uint8_t  proto;
    int      action;     /* 1=ALLOW, 0=DROP */
};

/* ── 해시 테이블 엔트리 ── */
struct hash_entry {
    uint32_t key[5];     /* 마스킹된 5-tuple 키 */
    struct rule *rule;
    struct hash_entry *next; /* 체이닝 */
};

/* ── 튜플: 같은 마스크 패턴의 규칙 그룹 ── */
struct tuple {
    struct mask_pattern  mask;
    struct hash_entry   *buckets[HASH_BUCKETS];
    int                 rule_count;
    int                 hit_count;  /* 최근 히트 수 (정렬 우선순위) */
};

/* ── 간단한 해시 함수 ── */
static uint32_t hash5(uint32_t key[5]) {
    uint32_t h = 2166136261u;
    for (int i = 0; i < 5; i++)
        h = (h ^ key[i]) * 16777619u;
    return h % HASH_BUCKETS;
}

/* ── 규칙을 튜플의 해시 테이블에 삽입 ── */
static void tuple_insert(struct tuple *t, struct rule *r)
{
    /* 1. 규칙의 필드를 마스킹하여 해시 키 생성 */
    uint32_t key[5] = {
        r->src_ip   & t->mask.src_mask,
        r->dst_ip   & t->mask.dst_mask,
        r->src_port & t->mask.sport_mask,
        r->dst_port & t->mask.dport_mask,
        r->proto    & t->mask.proto_mask
    };

    /* 2. 해시 → 버킷 선택 → 체인에 추가 */
    uint32_t idx = hash5(key);
    static struct hash_entry pool[256];
    static int pool_idx = 0;
    struct hash_entry *e = &pool[pool_idx++];
    memcpy(e->key, key, sizeof(key));
    e->rule = r;
    e->next = t->buckets[idx];
    t->buckets[idx] = e;
    t->rule_count++;
}

/* ── 패킷을 튜플에서 룩업 ── */
static struct rule *tuple_lookup(struct tuple *t,
    uint32_t src_ip, uint32_t dst_ip,
    uint16_t sport, uint16_t dport, uint8_t proto)
{
    /* 1. 패킷 필드를 이 튜플의 마스크로 마스킹 */
    uint32_t key[5] = {
        src_ip  & t->mask.src_mask,
        dst_ip  & t->mask.dst_mask,
        sport   & t->mask.sport_mask,
        dport   & t->mask.dport_mask,
        proto   & t->mask.proto_mask
    };

    /* 2. 해시 → 버킷 → 키 비교 (O(1) 평균) */
    uint32_t idx = hash5(key);
    for (struct hash_entry *e = t->buckets[idx]; e; e = e->next) {
        if (memcmp(e->key, key, sizeof(key)) == 0) {
            t->hit_count++;
            return e->rule;  /* O(1) 매칭! */
        }
    }
    return NULL;  /* 이 튜플에서는 매칭 없음 */
}

/* ── 전체 TSS 분류 ── */
static struct rule *tss_classify(
    struct tuple tuples[], int nt,
    uint32_t src_ip, uint32_t dst_ip,
    uint16_t sport, uint16_t dport, uint8_t proto)
{
    struct rule *best = NULL;
    int lookups = 0;

    for (int i = 0; i < nt; i++) {
        lookups++;
        struct rule *r = tuple_lookup(&tuples[i],
                            src_ip, dst_ip, sport, dport, proto);
        if (r && (!best || r->priority < best->priority))
            best = r;
    }
    printf("  [TSS] %d개 튜플 룩업 수행 (vs 선형 탐색 8회 비교)\n", lookups);
    return best;
}

int main(void)
{
    /* 규칙 정의 (예시 규칙 집합) */
    struct rule rules[] = {
        {"R1", 1, 0xC0A80100, 0x0A000000, 0, 80, 6, 1},
        {"R2", 2, 0xC0A80100, 0x0A000000, 0, 443, 6, 1},
        {"R3", 3, 0xC0A80000, 0, 0, 53, 17, 1},
        {"R4", 4, 0xAC100000, 0xAC100000, 0, 0, 0, 1},
        {"R5", 5, 0, 0, 0, 22, 6, 0},
        {"R8", 8, 0, 0, 0, 0, 0, 0},
    };

    /* 튜플 정의: 각 규칙의 마스크 패턴별로 분류 */
    struct tuple tuples[6];
    memset(tuples, 0, sizeof(tuples));

    /* Tuple 0: (24, 8, 0, exact, exact) — R1, R2 */
    tuples[0].mask = (struct mask_pattern){
        0xFFFFFF00, 0xFF000000, 0, 0xFFFF, 0xFF};
    tuple_insert(&tuples[0], &rules[0]);  /* R1 */
    tuple_insert(&tuples[0], &rules[1]);  /* R2 */

    /* Tuple 1: (16, 0, 0, exact, exact) — R3 */
    tuples[1].mask = (struct mask_pattern){
        0xFFFF0000, 0, 0, 0xFFFF, 0xFF};
    tuple_insert(&tuples[1], &rules[2]);

    /* Tuple 2: (12, 12, 0, 0, 0) — R4 */
    tuples[2].mask = (struct mask_pattern){
        0xFFF00000, 0xFFF00000, 0, 0, 0};
    tuple_insert(&tuples[2], &rules[3]);

    /* Tuple 3: (0, 0, 0, exact, exact) — R5 */
    tuples[3].mask = (struct mask_pattern){
        0, 0, 0, 0xFFFF, 0xFF};
    tuple_insert(&tuples[3], &rules[4]);

    /* Tuple 4: (0, 0, 0, 0, 0) — R8 */
    tuples[4].mask = (struct mask_pattern){0, 0, 0, 0, 0};
    tuple_insert(&tuples[4], &rules[5]);

    /* 테스트 패킷 분류 */
    printf("=== 튜플 공간 탐색 분류기 ===\n");
    printf("패킷: src=192.168.1.100 dst=10.1.2.3 sport=49152 dport=80 TCP\n\n");

    struct rule *result = tss_classify(tuples, 5,
        0xC0A80164, 0x0A010203, 49152, 80, 6);

    if (result)
        printf("  결과: %s (우선순위 %d) → %s\n",
               result->name, result->priority,
               result->action ? "ALLOW" : "DROP");

    return 0;
}

/* 실행 결과:
 * === 튜플 공간 탐색 분류기 ===
 * 패킷: src=192.168.1.100 dst=10.1.2.3 sport=49152 dport=80 TCP
 *
 *   [TSS] 5개 튜플 룩업 수행 (vs 선형 탐색 8회 비교)
 *   결과: R1 (우선순위 1) → ALLOW
 *
 * 규칙 10,000개, 튜플 50개인 경우:
 *   선형 탐색: 10,000회 비교 (×5 필드 = 50,000 연산)
 *   TSS:      50회 해시 룩업 (각 O(1) = 50 연산)  → 1,000배 빠름!
 */

Open vSwitch와 Megaflow Cache

Open vSwitch(OVS)의 megaflow cache는 튜플 공간 탐색의 대표적 실제 적용입니다. OVS는 플로우 테이블을 접두사 길이/마스크 조합별 해시 테이블로 관리하며, 패킷을 순차적으로 각 테이블에서 탐색합니다.

OVS의 3계층 캐시 구조

1. Microflow Cache (EMC): 정확한 5-tuple 해시 → O(1) 직접 매칭. 가장 빠르지만 용량이 제한적 (보통 8,192 엔트리)
2. Megaflow Cache (SMC/TSS): 튜플 공간 탐색 기반의 와일드카드 매칭. EMC 미스 시 사용. 마스크별 해시 테이블로 O(T) 룩업
3. Userspace Flow Table: 커널 캐시 미스 시 유저스페이스 ovs-vswitchd에 upcall. OpenFlow 테이블 전체 평가 후 megaflow 엔트리 설치

/* 의사코드: 튜플 공간 탐색 */
struct tuple_table {
    mask[d];          /* 각 필드의 접두사 마스크 */
    hash_table;       /* 마스킹된 키 → 규칙 해시 테이블 */
};

function tuple_space_classify(packet, tuples[T]):
    best_match = DEFAULT_RULE
    for each tuple in tuples:
        key = apply_mask(packet, tuple.mask)
        rule = hash_lookup(tuple.hash_table, key)
        if rule != NULL and rule.priority > best_match.priority:
            best_match = rule
    return best_match

Open vSwitch 커널 구현 상세

OVS(Open vSwitch)는 net/openvswitch/ 디렉토리에 커널 모듈을 포함합니다. 튜플 공간 탐색이 어떻게 커널 자료구조로 구현되는지 살펴봅니다.

/* net/openvswitch/flow_table.h — 핵심 자료구조 */

struct sw_flow {
    struct rcu_head         rcu;
    struct {
        struct hlist_node   node[2];  /* table_instance 해시 버킷 */
    } flow_table, ufid_table;
    int                     stats_last_writer;
    struct sw_flow_key      key;      /* 추출된 패킷 키 */
    struct sw_flow_id       id;       /* flow ID (mask + unmasked_key) */
    struct sw_flow_mask     *mask;    /* 해당 마스크 포인터 */
    struct sw_flow_actions __rcu *sf_acts;  /* 액션 배열 */
    struct sw_flow_stats    *stats;   /* per-CPU 통계 */
};

struct table_instance {
    struct flex_array  *buckets;   /* 해시 버킷 배열 */
    unsigned int       n_buckets;  /* 2의 거듭제곱 */
    struct rcu_head    rcu;
    int                node_ver;   /* 버전 (리사이즈 추적) */
    u32                hash_seed;  /* 해시 시드 */
    bool               keep_flows; /* 리사이즈 시 플로우 유지 여부 */
};

struct mask_array {
    struct rcu_head    rcu;
    int                count;      /* 현재 마스크 수 */
    int                max;        /* 최대 마스크 수 */
    struct sw_flow_mask __rcu *masks[];  /* 마스크 배열 */
};

/* net/openvswitch/flow_table.c — ovs_flow_tbl_lookup_stats() */

struct sw_flow *ovs_flow_tbl_lookup_stats(
    struct flow_table *tbl,
    const struct sw_flow_key *key,
    u32 skb_hash,
    u32 *n_mask_hit,
    u32 *n_cache_hit)
{
    struct mask_array *ma = rcu_dereference(tbl->mask_array);
    struct table_instance *ti = rcu_dereference(tbl->ti);
    struct sw_flow_mask *mask;
    struct sw_flow *flow;
    int i;

    /* 1. EMC (Exact Match Cache) 먼저 시도 */
    flow = emc_lookup(&tbl->emc_cache, key);
    if (flow) {
        (*n_cache_hit)++;
        return flow;
    }

    /* 2. SMC (Slow Miss Cache) 시도 */
    flow = smc_lookup(tbl, key);
    if (flow) {
        (*n_cache_hit)++;
        return flow;
    }

    /* 3. 마스크 배열 순회 (Tuple Space Search) */
    for (i = 0; i < ma->max; i++) {
        mask = rcu_dereference(ma->masks[i]);
        if (!mask)
            continue;
        (*n_mask_hit)++;
        /* 패킷 키에 마스크 적용 후 해시 룩업 */
        flow = masked_flow_lookup(ti, key, mask, skb_hash);
        if (flow) {
            /* EMC 업데이트 — 다음 패킷 빠른 경로 */
            emc_insert(&tbl->emc_cache, flow);
            return flow;
        }
    }
    return NULL;   /* 미스 → upcall → 유저스페이스 처리 */
}

메가플로우 캐시 무효화: OVS에서 규칙이 변경되면 관련 megaflow 엔트리가 무효화됩니다. EMC/SMC는 단순히 비워지고(emc_clear()), 마스크 배열은 원자적으로 교체됩니다. 이후 첫 패킷은 upcall 경로를 거쳐 새 megaflow 엔트리를 설치합니다.

튜플 공간 최적화 기법

튜플 병합 (Tuple Merge)

여러 개의 유사한 마스크를 하나의 더 일반적인 마스크로 병합하면 튜플 수 T가 줄어들어 탐색 속도가 향상됩니다. 단, 병합 후 해시 테이블의 버킷당 규칙 수가 증가합니다.

/* 튜플 병합 예시: 두 마스크를 하나로 */
/* 마스크 A: SrcIP/24, DstIP/8, DstPort/exact, Proto/exact */
/* 마스크 B: SrcIP/24, DstIP/8, DstPort/exact (Proto 와일드카드) */

/* 마스크 B는 마스크 A의 슈퍼셋 → 마스크 A를 마스크 B로 병합 가능 */
/* 단, 마스크 B 해시테이블에 Protocol을 무시한 키로 저장해야 함 */
/* → 버킷 충돌 증가 but 마스크 수 감소 */

튜플 우선순위 정렬 (Tuple Priority)

OVS는 최근에 매칭에 성공한 마스크를 배열 앞쪽으로 이동시킵니다. 네트워크 트래픽의 공간적 지역성(spatial locality) 덕분에, 동일한 플로우 타입이 연속으로 도착하면 첫 번째 마스크에서 매칭되어 나머지 마스크 탐색을 생략합니다.

부분 튜플 제거 (Partial Tuple Elimination)

와일드카드 필드가 많은 튜플은 해시 테이블에서 충돌이 많아집니다. 이런 퇴화 튜플(degenerate tuple)을 별도 선형 탐색 목록으로 분리하면, 해시 테이블의 성능을 유지하면서 와일드카드 규칙을 효율적으로 처리할 수 있습니다.

복잡도

RFC 알고리즘 (Recursive Flow Classification)

Gupta & McKeown (1999)이 제안한 RFC(Recursive Flow Classification)는 메모리를 대가로 극도로 빠른 분류 속도를 달성하는 알고리즘입니다. 핵심 아이디어는 다차원 매칭 문제를 여러 단계(phase)의 메모리 룩업으로 분해하여, 각 단계에서 동치 클래스(equivalence class)를 축소하는 것입니다.

핵심 아이디어 — 우체국 비유

핵심 개념 정의

RFC의 핵심 통찰을 정식으로 정의합니다.

동치 클래스 (Equivalence Class)

모든 규칙에 대해 동일한 매칭/비매칭 패턴을 보이는 값들의 집합입니다. 형식적으로, 필드 F에서 두 값 v₁과 v₂가 동치 클래스를 이루려면:

/* 동치 클래스 정의 */
v₁ ≡ v₂ (필드 F에 대해)
  ⟺ 모든 규칙 Rᵢ에 대해:
      Rᵢ.field_F가 v₁을 매칭하면, Rᵢ.field_F도 v₂를 매칭함 (역도 성립)

/* 비트맵으로 표현하면: */
bitmap(v₁) == bitmap(v₂)
  where bitmap(v)[i] = 1 iff rule Rᵢ matches value v on field F

예시: 규칙이 포트 80, 443, 22, 53만 구분하고 나머지를 와일드카드로 처리하면, 포트 0~21은 모두 같은 비트맵을 가집니다. 포트 23~52도 모두 같은 비트맵입니다. 이처럼 65,536개 포트 값이 단 5개의 그룹으로 축소됩니다.

eqID (Equivalence Class ID)

각 동치 클래스에 부여하는 정수 식별자입니다. 2¹⁶개의 가능한 포트 값이 실제로는 수십~수백 개의 eqID로 축소됩니다. eqID는 비트맵의 대리(proxy) 역할을 합니다 — eqID만 알면 어떤 규칙들이 매칭되는지 비트맵 없이도 결정할 수 있습니다.

다단계 축소 (Multi-phase Reduction)

Phase 0에서 각 필드를 독립적으로 eqID로 변환하고, 이후 단계에서 인접 eqID들의 교차곱을 새로운(더 작은) eqID로 축소합니다. 최종 단계의 eqID가 곧 매칭 규칙 번호입니다.

Phase 0 — 독립 필드 검색

Phase 0에서는 패킷 헤더의 각 필드를 독립적으로 검색하여 eqID로 변환합니다. 헤더를 청크(chunk)로 나누고, 각 청크에 대해 사전 계산된 테이블(배열)을 인덱싱합니다.

/* Phase 0: 헤더 필드 → eqID 매핑 */

/* 예: 16비트 출발지 포트를 eqID로 변환 */
eqID_srcport = phase0_table_srcport[packet.src_port];
/* 테이블 크기: 2^16 = 65536 엔트리 */
/* 출력: 0 ~ (동치 클래스 수 - 1) */

/* 32비트 IP는 16비트씩 나누어 2개 청크로 처리 */
eqID_srcip_hi = phase0_table_srcip_hi[packet.src_ip >> 16];
eqID_srcip_lo = phase0_table_srcip_lo[packet.src_ip & 0xFFFF];

5-tuple 분류의 경우, 32비트 IP 주소를 16비트씩 나누면 총 7개 청크가 됩니다.

청크 분할 설계 원리

청크 너비 W는 테이블 크기(2^W 엔트리)와 청크 개수(= Phase 수) 사이의 트레이드오프를 결정합니다. 너비가 넓을수록 테이블 하나는 크지만 Phase 수가 줄어 분류가 빠릅니다.

접두사가 청크 경계를 넘는 경우

RFC에서 가장 중요한 설계 문제 중 하나는 IP 접두사가 청크 경계를 넘을 때 발생합니다. 32비트 SrcIP를 16비트씩 나누면, /24 접두사(예: 192.168.1.0/24)는 두 청크에 걸칩니다.

• Chunk 0 (SrcIP[31:16]): 상위 16비트가 정확히 0xC0A8(= 192.168)여야 → 단순 exact match
• Chunk 1 (SrcIP[15:0]): 하위 16비트가 0x0100~0x01FF 범위여야 → 그러나 R3(/16)는 하위 16비트가 무엇이든 매칭

Phase 0는 두 청크를 독립적으로 처리하므로 R3의 하위 청크 비트맵은 0x0000~0xFFFF 전체(65,536개 값) 모두에 R3 비트를 설정합니다. 즉, chunk 1만 보면 R3가 과도 매칭(over-match)됩니다. 이 문제는 Phase 1의 AND 연산이 해결합니다.

Phase 0 비트맵 구축 상세 — SrcIP 상위 청크 추적

8개 규칙에 대해 Chunk 0 (SrcIP[31:16])의 비트맵 계산을 구체적으로 추적합니다. 각 16비트 값에 대해 어떤 규칙이 매칭되는지 계산합니다.

이 계산의 결과로, Chunk 0 테이블에는 4종류의 비트맵만 나타납니다.

65,536개 → 4개 eqID! 실제 규칙이 구별하는 값은 3개 범위뿐이므로(192.168, 10.x, 172.16.*), 나머지 수만 개의 값은 모두 동일한 비트맵을 가집니다.

/* Phase 0 비트맵 구축: 접두사를 값 범위로 전개 */
function build_phase0_bitmap(rules[N], chunk_width, chunk_offset):
    bitmap = array[2^chunk_width] of 0

    for r = 0 to N-1:
        field_cond = rules[r].field_for_chunk(chunk_offset, chunk_width)

        if field_cond.is_wildcard():
            /* 와일드카드: 모든 값에 비트 설정 */
            for v = 0 to 2^chunk_width - 1:
                bitmap[v] |= (1 << r)

        else if field_cond.is_prefix(prefix, prefix_len):
            /* 접두사: 해당 청크에서의 매칭 범위 계산 */
            chunk_bits = min(prefix_len - chunk_offset, chunk_width)
            if chunk_bits <= 0:
                /* 이 청크는 완전히 와일드카드 */
                for v = 0 to 2^chunk_width - 1:
                    bitmap[v] |= (1 << r)
            else:
                /* 접두사의 해당 청크 비트만 고정, 나머지는 와일드카드 */
                base = (prefix >> chunk_offset) & ((1 << chunk_width) - 1)
                base = base & ~((1 << (chunk_width - chunk_bits)) - 1)
                count = 1 << (chunk_width - chunk_bits)
                for v = base to base + count - 1:
                    bitmap[v] |= (1 << r)

    return bitmap

범위 필드의 비트맵 계산 — 포트 범위

IP 주소는 접두사(prefix) 매칭을 사용하지만, 포트 필드는 범위(range) 매칭을 사용합니다. RFC는 임의 범위를 자연스럽게 처리하는데, 이는 TCAM 대비 큰 장점입니다.

/* SrcPort 필드의 비트맵 계산 (예시 규칙셋) */
/* R1~R5: SrcPort = * (와일드카드) → 모든 값에서 매칭 */
/* R6: SrcPort = 1024-65535 (범위 매칭) */
/* R7~R8: SrcPort = * (와일드카드) → 모든 값에서 매칭 */

port=0    → bitmap = 11011111 /* R6 제외, 나머지 모두 */  → eqID = 0
port=1023 → bitmap = 11011111 /* 동일 */                  → eqID = 0
port=1024 → bitmap = 11111111 /* R6 포함, 전부 매칭 */    → eqID = 1
port=65535→ bitmap = 11111111 /* 동일 */                  → eqID = 1

/* 결과: 65,536개 → 2개 eqID */
/* 범위 경계(1024)가 eqID 경계를 생성 */
/* 포트 0~1023: eqID=0 (R6 비매칭) */
/* 포트 1024~65535: eqID=1 (R6 매칭) */

범위 경계(1024)가 정확히 하나의 추가 eqID 분할을 만듭니다. 포트 0~1023은 모두 동일한 비트맵, 포트 1024~65535도 모두 동일한 비트맵입니다. 반면 정확한 포트 값 매칭(예: dport=80)은 해당 포트에만 비트가 설정되어 별도 eqID를 만듭니다.

핵심은 동치 클래스 축소입니다. 65,536개의 가능한 포트 값이 실제 규칙셋에서는 보통 수십 개의 동치 클래스로 축소됩니다. 예를 들어, 규칙이 포트 80, 443, 1024-65535만 구분하면, 모든 포트는 4개 eqID(80, 443, 1024-65535, 나머지)로 분류됩니다.

Phase 1~N — 교차곱 축소

Phase 0에서 7개의 eqID를 얻었다면, 이제 인접한 eqID 쌍을 결합하여 새로운 eqID로 축소합니다. 이 과정을 여러 단계에 걸쳐 반복하면, 최종적으로 하나의 classID(매칭 규칙 번호)가 남습니다.

/* Phase 1: 인접 eqID 결합 */

/* eqID₀(48종) × eqID₁(24종) → 새로운 eqID (실제로는 ≪ 48×24) */
combined_01 = phase1_table_A[eqID₀ * num_eqID₁ + eqID₁];

/* 이론적 교차곱: 48 × 24 = 1,152 조합 */
/* 실제 동치 클래스: ~60개 (규칙셋 특성에 의한 축소) */

이 축소가 가능한 이유는, 교차곱의 많은 조합이 모든 규칙에 대해 동일한 매칭 결과를 보이기 때문입니다. 예를 들어, (eqID₀=12, eqID₁=3)과 (eqID₀=12, eqID₁=7)이 같은 규칙들에 매칭된다면, 이 두 조합은 같은 새 eqID를 받습니다.

결합 그룹 선택 전략 (Phase Topology)

Phase 0에서 7개의 eqID를 얻은 후, 어떤 eqID를 어떤 순서로 결합할지 결정하는 것이 위상(topology) 선택입니다. 이 선택은 Phase 1 테이블 크기와 총 메모리에 영향을 주지만, 분류 속도(Phase 수)는 바뀌지 않습니다.

실제 구현에서는 대부분 의미론적 근접 전략을 사용합니다. IP 주소의 상위/하위 청크는 강한 상관관계(같은 서브넷)가 있어, 교차곱이 이론값(48×24=1,152)의 5% 수준(~60개)으로 축소됩니다.

완전 교차곱 행렬 — DstPort × Protocol (20개 전체)

5×4=20개의 모든 조합에 대해 AND 연산 결과를 완전히 전개합니다. 비트맵 표기: R8R7R6R5R4R3R2R1 (MSB=R8, LSB=R1).

20개 중 null(port=53, TCP는 어떤 규칙도 매칭 안 함: R3는 UDP 전용, R1,R2,R5,R6는 다른 포트)은 기본 규칙으로 처리됩니다. 나머지 19개 유효 조합이 A, B, C, D, F, G, H 7개 eqID로 축소됩니다.

교차곱 축소의 정당성

비트맵 AND 연산이 "두 필드를 동시에 만족하는 규칙"을 올바르게 찾아냄을 형식적으로 확인할 수 있습니다.

• bitmap_A[i]=1은 "규칙 i가 필드 A의 이 값(eqID)에 매칭됨"을 의미합니다.
• bitmap_B[i]=1은 "규칙 i가 필드 B의 이 값(eqID)에 매칭됨"을 의미합니다.
• (bitmap_A AND bitmap_B)[i]=1 iff 규칙 i가 필드 A와 B 모두에 매칭됩니다.

두 (eqID_A, eqID_B) 조합의 AND 결과 비트맵이 동일하면, 그 두 조합에 대해 이후 모든 단계의 분류 결과가 같습니다. 따라서 같은 비트맵 → 같은 새 eqID 배정이 정당합니다. 이것이 RFC 교차곱 축소의 수학적 근거입니다.

전형적인 3단계 구성 (5-tuple)

Phase 2 — 최종 분류 상세

Phase 2는 Phase 1에서 나온 3개의 eqID(eqID_A: SrcIP, eqID_B: DstIP, eqID_C: Port+Proto)를 결합하여 최종 classID를 결정합니다. Phase 2 테이블의 각 엔트리는 해당 조합과 매칭되는 최고 우선순위 규칙 번호입니다.

우선순위 해소(priority resolution) 방법: 사전 계산 시 결합 비트맵에서 가장 낮은 인덱스(=가장 높은 우선순위)의 비트를 찾아 classID로 저장합니다.

/* Phase 2: classID = 최고 우선순위 규칙 (결합 비트맵의 첫 번째 1비트) */
function resolve_priority(combined_bitmap, N):
    for r = 0 to N-1:   /* 규칙 0이 최고 우선순위 */
        if combined_bitmap & (1 << r):
            return r   /* 첫 번째 매칭 규칙 = 최고 우선순위 */
    return DEFAULT_RULE  /* 비트맵=0: 매칭 규칙 없음 */

/* 예시: combined_bitmap = 00100001 (R1, R6) */
/* → r=0(R1) 먼저 검사 → 비트 1 → classID = R1 */
/* R1이 R6보다 우선순위가 높으므로 R6는 무시 */

/* Phase 2 테이블 인덱싱 */
classID = phase2[eqID_A * EB * EC + eqID_B * EC + eqID_C]
/* 테이블 크기: 60 × 83 × 35 = 174,300 엔트리 */
/* 각 엔트리: 1~2 bytes (classID = 규칙 번호) */
/* 총 메모리: 약 170~340 KB */

전체 5-tuple RFC의 메모리 산정

예시 규칙셋(1,000개 규칙 수준)에 대한 RFC 전체 메모리 소요를 단계별로 산출합니다.

사전 계산 과정

RFC 테이블의 사전 계산은 규칙 집합이 변경될 때 수행됩니다. 핵심은 각 필드 값에 대해 어떤 규칙들이 매칭되는지(class bitmap)를 계산하고, 동일한 비트맵을 가진 값들을 같은 eqID로 묶는 것입니다.

/* RFC 사전 계산 알고리즘 — Phase 0 */
function precompute_phase0(field_index, rules[N]):
    /* 1. 각 입력 값에 대해 매칭 규칙 비트맵 계산 */
    for value = 0 to (2^field_bits - 1):
        bitmap[value] = 0
        for r = 0 to N-1:
            if rules[r].field[field_index] matches value:
                bitmap[value] |= (1 << r)

    /* 2. 동일한 비트맵을 가진 값들을 같은 eqID로 매핑 */
    eqID_map = {}  /* bitmap → eqID 해시맵 */
    next_eqID = 0
    for value = 0 to (2^field_bits - 1):
        if bitmap[value] not in eqID_map:
            eqID_map[bitmap[value]] = next_eqID++
        table[value] = eqID_map[bitmap[value]]

    return table, eqID_count = next_eqID

/* RFC 사전 계산 알고리즘 — Phase k (k ≥ 1) */
function precompute_phase_k(eqIDs_A[], eqIDs_B[], bitmaps_A[], bitmaps_B[]):
    eqID_map = {}
    next_eqID = 0
    for a = 0 to |eqIDs_A| - 1:
        for b = 0 to |eqIDs_B| - 1:
            combined_bitmap = bitmaps_A[a] & bitmaps_B[b]
            if combined_bitmap == 0: continue  /* 매칭 규칙 없음 */
            if combined_bitmap not in eqID_map:
                eqID_map[combined_bitmap] = next_eqID++
            table[a * |eqIDs_B| + b] = eqID_map[combined_bitmap]

    return table, eqID_count = next_eqID

사전 계산 단계별 시간 복잡도 분석

각 단계별 실제 연산량을 구체적인 수치로 분석합니다.

• Step 1: Phase 0 비트맵 구축 — 청크당 2^W 값 × N 규칙 = O(2^W × N). 16비트 청크, 1,000개 규칙: 65,536 × 1,000 = 65M 연산 × 7 청크 = 455M 연산. 현대 CPU 기준 약 0.5초.
• Step 2: Phase 0 eqID 배정(비트맵 중복 제거) — 각 값의 N비트 비트맵을 해시: O(2^W × N/64) 해시 연산. 1,000개 규칙, 128바이트 비트맵 해싱 × 65,536 값 → 청크당 실측 10~50 ms.
• Step 3: Phase 1 교차곱 — 각 (eqA, eqB) 쌍에 비트맵 AND: 결합 A(48×24=1,152), B(52×31=1,612), C(18×25×5=2,250). 각 AND는 O(N/64). 1,000개 규칙에서 Phase 1 전체 1 ms 미만.
• Step 4: Phase 2 교차곱 — 60×83×35=174,300 엔트리 × 비트맵 AND + 우선순위 해소. 1,000개 규칙에서 약 10~100 ms.

사전 계산 최적화 기법

• 비트맵 압축: 희소 비트맵(매칭 규칙이 적은 값)은 RLE(Run-Length Encoding)로 압축하여 해시 속도 향상.
• 병렬 사전 계산: 각 청크의 Phase 0 테이블은 완전 독립적 → 7개 스레드가 동시에 처리 가능. 병렬화 시 Phase 0 시간 7배 단축.
• 증분 업데이트: 규칙 하나를 추가/삭제할 때 영향받는 비트맵만 재계산. 단, Phase 2 테이블은 전체 재계산 필요.
• 지연 평가(Lazy evaluation): 교차곱에서 어느 한 비트맵이 0이면 AND 결과도 반드시 0이므로 해당 엔트리 계산 건너뜀. Phase 1/2 계산 시간 대폭 단축.

복잡도 분석

RFC 전체 추적 예시

예시 규칙 집합(R1~R8)에 대해 RFC의 동작을 구체적인 수치로 추적합니다. 간결함을 위해 Dst Port와 Protocol 두 필드만으로 축소한 2차원 예시입니다.

예시: Dst Port × Protocol (2차원 축소)

8개 규칙의 Dst Port와 Protocol 필드만 추출합니다.

Phase 0: Dst Port의 동치 클래스

65,536개 포트 값의 비트맵을 계산하고 동치 클래스로 축소합니다.

65,536개 → 5개 eqID로 축소! 포트 0~21, 23~52, 54~79, 81~442, 444~65535는 모두 같은 비트맵(R4, R8만 매칭)이므로 하나의 eqID로 통합됩니다.

Phase 0: Protocol의 동치 클래스

256개 → 4개 eqID로 축소!

Phase 1: 교차곱 축소

이론적 교차곱: 5 × 4 = 20 조합. 각 조합의 비트맵을 AND 연산합니다.

20개 조합 → 7개 동치 클래스로 축소! 테스트 패킷 (DstPort=80, Proto=TCP): Phase 0에서 DstPort eqID=2, Proto eqID=1 → Phase 1 테이블에서 (2,1)을 조회하면 eqID=B → 최우선 매칭 규칙은 R1.

전체 5-tuple RFC 분류 추적

이제 실제 5-tuple로 테스트 패킷 (Src=192.168.1.100, Dst=10.1.2.3, SrcPort=49152, DstPort=80, Proto=TCP)의 RFC 분류 과정을 추적합니다.

/* ═══════════════════════════════════════════════════════════ */
/* Phase 0: 7개 청크 → 7개 eqID (1회 병렬 메모리 접근)       */
/* ═══════════════════════════════════════════════════════════ */

/* Chunk 0: SrcIP[31:16] = 0xC0A8 (192.168) */
eqID₀ = phase0[0][0xC0A8]  → eqID = 12
  /* bitmap: R1,R2,R3 매칭 (192.168.x.x는 R1,R2,R3의 SrcIP에 포함) */

/* Chunk 1: SrcIP[15:0] = 0x0164 (1.100) */
eqID₁ = phase0[1][0x0164]  → eqID = 3
  /* bitmap: R1,R2에만 매칭 (/24이므로 1.x는 매칭, /16은 모두 매칭) */

/* Chunk 2: DstIP[31:16] = 0x0A01 (10.1) */
eqID₂ = phase0[2][0x0A01]  → eqID = 27
  /* bitmap: R1,R2 매칭 (10.x.x.x는 R1,R2의 DstIP /8에 포함) */

/* Chunk 3: DstIP[15:0] = 0x0203 (2.3) */
eqID₃ = phase0[3][0x0203]  → eqID = 8

/* Chunk 4: SrcPort = 49152 (0xC000) */
eqID₄ = phase0[4][0xC000]  → eqID = 2
  /* bitmap: R6 매칭 (1024-65535 범위) + R4,R8 (와일드카드) */

/* Chunk 5: DstPort = 80 (0x0050) */
eqID₅ = phase0[5][0x0050]  → eqID = 15
  /* bitmap: R1,R6 매칭 (port 80) + R4,R8 (와일드카드) */

/* Chunk 6: Protocol = 6 (TCP) */
eqID₆ = phase0[6][6]       → eqID = 1
  /* bitmap: R1,R2,R5,R6 매칭 (TCP) + R4,R8 (와일드카드) */

/* ═══════════════════════════════════════════════════════════ */
/* Phase 1: 3개 결합 (1회 메모리 접근)                        */
/* ═══════════════════════════════════════════════════════════ */

/* 결합 A: SrcIP 청크 결합 */
combined_A = phase1[A][eqID₀ * E₁ + eqID₁]   /* [12 * 24 + 3] */
           = phase1[A][291]  → eqID_A = 7
  /* SrcIP 전체로 보면: R1,R2 매칭 (192.168.1.0/24) */

/* 결합 B: DstIP 청크 결합 */
combined_B = phase1[B][eqID₂ * E₃ + eqID₃]   /* [27 * 32 + 8] */
           = phase1[B][872]  → eqID_B = 19
  /* DstIP 전체: R1,R2 매칭 (10.0.0.0/8) */

/* 결합 C: Port + Protocol 결합 */
combined_C = phase1[C][eqID₄ * E₅ * E₆ + eqID₅ * E₆ + eqID₆]
           → eqID_C = 5
  /* SrcPort=49152, DstPort=80, TCP: R1,R6 매칭 */

/* ═══════════════════════════════════════════════════════════ */
/* Phase 2: 최종 결합 (1회 메모리 접근)                       */
/* ═══════════════════════════════════════════════════════════ */

classID = phase2[eqID_A * EB * EC + eqID_B * EC + eqID_C]
        = phase2[7 * 83 * 35 + 19 * 35 + 5]
        → classID = R1 (ALLOW)

/* R1과 R8이 모두 매칭되지만, classID는 최우선 규칙 R1을 가리킴 */
/* 총 메모리 접근: Phase 0(7회 병렬) + Phase 1(3회 병렬) + Phase 2(1회) */
/* = 실질적으로 3회 순차 메모리 접근으로 분류 완료! */

완전한 C 구현 — 2차원 RFC 분류기

아래는 RFC 알고리즘의 핵심 아이디어를 Dst Port × Protocol 2차원으로 구현한 완전한 C 코드입니다. Phase 0(독립 필드 검색)과 Phase 1(교차곱 축소)의 전체 과정을 단계별로 추적할 수 있습니다.

/* rfc_classifier.c — 2차원 RFC 패킷 분류기
 *
 * Phase 0: Dst Port(65536값) → eqID, Protocol(256값) → eqID
 * Phase 1: (eqID_port × eqID_proto) → 최종 규칙
 *
 * 컴파일: gcc -O2 -o rfc_classifier rfc_classifier.c
 * 실행:   ./rfc_classifier
 */
#include <stdio.h>
#include <stdint.h>
#include <string.h>

#define MAX_RULES     16
#define PORT_SPACE    65536  /* 16비트 포트: 0 ~ 65535 */
#define PROTO_SPACE   256    /* 8비트 프로토콜: 0 ~ 255 */
#define MAX_EQID      64    /* 동치 클래스 최대 수 */

/* ── 규칙 구조체 ── */
struct rule {
    char     name[8];
    int      priority;
    uint16_t dport;        /* 0xFFFF = 와일드카드 */
    uint8_t  proto;        /* 0 = 와일드카드 */
    int      action;       /* 1=ALLOW, 0=DROP */
};

/* ── Phase 0 테이블 ── */
static uint8_t phase0_dport[PORT_SPACE];    /* 포트 → eqID */
static uint8_t phase0_proto[PROTO_SPACE];   /* 프로토콜 → eqID */
static int num_dport_eqid, num_proto_eqid;

/* ── Phase 1 테이블 ── */
static int phase1_table[MAX_EQID][MAX_EQID]; /* → 매칭 규칙 인덱스 */

/* ── 비트맵: 각 값에 대해 어떤 규칙이 매칭되는지 ── */
typedef uint16_t bitmap_t;  /* 최대 16개 규칙 지원 */

/* ── Phase 0 사전 계산: 입력값 → 비트맵 → eqID ── */
static int precompute_phase0_dport(
    const struct rule rules[], int nr)
{
    /* Step 1: 각 포트 값에 대해 매칭 규칙 비트맵 계산 */
    bitmap_t bitmaps[PORT_SPACE];
    for (int port = 0; port < PORT_SPACE; port++) {
        bitmaps[port] = 0;
        for (int r = 0; r < nr; r++) {
            if (rules[r].dport == 0xFFFF || rules[r].dport == port)
                bitmaps[port] |= (1 << r);
        }
    }

    /* Step 2: 동일 비트맵 → 동일 eqID 매핑 */
    bitmap_t unique[MAX_EQID];
    int n_eq = 0;
    for (int port = 0; port < PORT_SPACE; port++) {
        int found = -1;
        for (int e = 0; e < n_eq; e++) {
            if (unique[e] == bitmaps[port]) { found = e; break; }
        }
        if (found < 0) {
            found = n_eq;
            unique[n_eq++] = bitmaps[port];
        }
        phase0_dport[port] = found;
    }

    printf("  Phase 0 DstPort: %d개 포트 → %d개 eqID (축소율 %.2f%%)\n",
           PORT_SPACE, n_eq, (1.0 - (double)n_eq / PORT_SPACE) * 100);
    for (int e = 0; e < n_eq; e++) {
        printf("    eqID=%d: bitmap=%04X → 규칙: ", e, unique[e]);
        for (int r = 0; r < nr; r++)
            if (unique[e] & (1 << r)) printf("%s ", rules[r].name);
        printf("\n");
    }
    return n_eq;
}

static int precompute_phase0_proto(
    const struct rule rules[], int nr)
{
    bitmap_t bitmaps[PROTO_SPACE];
    for (int p = 0; p < PROTO_SPACE; p++) {
        bitmaps[p] = 0;
        for (int r = 0; r < nr; r++) {
            if (rules[r].proto == 0 || rules[r].proto == p)
                bitmaps[p] |= (1 << r);
        }
    }

    bitmap_t unique[MAX_EQID];
    int n_eq = 0;
    for (int p = 0; p < PROTO_SPACE; p++) {
        int found = -1;
        for (int e = 0; e < n_eq; e++) {
            if (unique[e] == bitmaps[p]) { found = e; break; }
        }
        if (found < 0) {
            found = n_eq;
            unique[n_eq++] = bitmaps[p];
        }
        phase0_proto[p] = found;
    }

    printf("  Phase 0 Protocol: %d개 값 → %d개 eqID (축소율 %.2f%%)\n",
           PROTO_SPACE, n_eq, (1.0 - (double)n_eq / PROTO_SPACE) * 100);
    return n_eq;
}

/* ── Phase 1 사전 계산: eqID 교차곱 → 최종 규칙 ── */
static void precompute_phase1(
    const struct rule rules[], int nr,
    int n_dport_eq, int n_proto_eq)
{
    /* 각 (eqID_dport, eqID_proto) 조합에 대해
     * 비트맵 AND → 최우선 매칭 규칙 결정 */
    bitmap_t dp_bitmaps[MAX_EQID], pr_bitmaps[MAX_EQID];

    /* eqID의 비트맵 수집 (Phase 0에서 이미 계산됨) */
    for (int port = 0; port < PORT_SPACE; port++)
        dp_bitmaps[phase0_dport[port]] = 0;
    for (int port = 0; port < PORT_SPACE; port++) {
        bitmap_t bm = 0;
        for (int r = 0; r < nr; r++)
            if (rules[r].dport == 0xFFFF || rules[r].dport == port)
                bm |= (1 << r);
        dp_bitmaps[phase0_dport[port]] = bm;
    }
    for (int p = 0; p < PROTO_SPACE; p++)
        pr_bitmaps[phase0_proto[p]] = 0;
    for (int p = 0; p < PROTO_SPACE; p++) {
        bitmap_t bm = 0;
        for (int r = 0; r < nr; r++)
            if (rules[r].proto == 0 || rules[r].proto == p)
                bm |= (1 << r);
        pr_bitmaps[phase0_proto[p]] = bm;
    }

    /* 교차곱 계산: AND 연산 → 최우선 규칙 */
    printf("\n  Phase 1: %d × %d = %d 조합 → 교차곱 축소\n",
           n_dport_eq, n_proto_eq, n_dport_eq * n_proto_eq);

    for (int d = 0; d < n_dport_eq; d++) {
        for (int p = 0; p < n_proto_eq; p++) {
            bitmap_t combined = dp_bitmaps[d] & pr_bitmaps[p];
            int best = -1;
            for (int r = 0; r < nr; r++) {
                if ((combined & (1 << r)) &&
                    (best < 0 || rules[r].priority < rules[best].priority))
                    best = r;
            }
            phase1_table[d][p] = best;
        }
    }
}

/* ── RFC 분류: 단 2회 메모리 접근! ── */
static int rfc_classify(uint16_t dport, uint8_t proto)
{
    /* Phase 0: 배열 인덱싱 (각 O(1)) */
    uint8_t eq_dport = phase0_dport[dport];    /* 1회 메모리 접근 */
    uint8_t eq_proto = phase0_proto[proto];    /* 1회 메모리 접근 */

    /* Phase 1: 교차곱 테이블 조회 (O(1)) */
    return phase1_table[eq_dport][eq_proto];   /* 1회 메모리 접근 */
    /* 총 3회 메모리 접근으로 분류 완료! */
}

int main(void)
{
    /* 예시 규칙 (DstPort × Protocol 2차원만) */
    struct rule rules[] = {
        {"R1", 1, 80,     6,  1},  /* dport=80,  TCP,  ALLOW */
        {"R2", 2, 443,    6,  1},  /* dport=443, TCP,  ALLOW */
        {"R3", 3, 53,     17, 1},  /* dport=53,  UDP,  ALLOW */
        {"R4", 4, 0xFFFF, 0,  1},  /* dport=*,   *,    ALLOW */
        {"R5", 5, 22,     6,  0},  /* dport=22,  TCP,  DROP  */
        {"R6", 6, 80,     6,  1},  /* dport=80,  TCP,  ALLOW */
        {"R7", 7, 0xFFFF, 1,  1},  /* dport=*,   ICMP, ALLOW */
        {"R8", 8, 0xFFFF, 0,  0},  /* dport=*,   *,    DROP  */
    };
    int nr = 8;

    printf("=== RFC 분류기 (2D: DstPort × Protocol) ===\n\n");
    printf("── 사전 계산 단계 ──\n");

    /* Phase 0 사전 계산 */
    int n_dport = precompute_phase0_dport(rules, nr);
    int n_proto = precompute_phase0_proto(rules, nr);

    /* Phase 1 사전 계산 */
    precompute_phase1(rules, nr, n_dport, n_proto);

    /* 분류 실행 — 매우 빠름! */
    printf("\n── 패킷 분류 (런타임) ──\n");

    struct { uint16_t dport; uint8_t proto; const char *desc; } tests[] = {
        {80,  6,  "dport=80, TCP  → 기대: R1(ALLOW)"},
        {443, 6,  "dport=443, TCP → 기대: R2(ALLOW)"},
        {53,  17, "dport=53, UDP  → 기대: R3(ALLOW)"},
        {22,  6,  "dport=22, TCP  → 기대: R5(DROP)"},
        {8080, 6, "dport=8080, TCP→ 기대: R4(ALLOW)"},
        {0,   1,  "dport=0, ICMP  → 기대: R7(ALLOW)"},
        {12345, 99, "dport=12345   → 기대: R8(DROP)"},
    };

    for (int i = 0; i < 7; i++) {
        int idx = rfc_classify(tests[i].dport, tests[i].proto);
        printf("  %s\n    → %s (%s)\n",
               tests[i].desc,
               idx >= 0 ? rules[idx].name : "NONE",
               idx >= 0 ? (rules[idx].action ? "ALLOW" : "DROP") : "DEFAULT");
    }

    printf("\n── 메모리 사용량 ──\n");
    printf("  Phase 0 DstPort 테이블: %zu bytes\n", sizeof(phase0_dport));
    printf("  Phase 0 Protocol 테이블: %zu bytes\n", sizeof(phase0_proto));
    printf("  Phase 1 교차곱 테이블: %zu bytes\n",
           (size_t)n_dport * n_proto * sizeof(int));
    printf("  총합: %zu bytes\n",
           sizeof(phase0_dport) + sizeof(phase0_proto) +
           (size_t)n_dport * n_proto * sizeof(int));
    printf("  (참고: 선형 탐색은 %zu bytes만 필요)\n",
           nr * sizeof(struct rule));

    return 0;
}

/* 실행 결과 (발췌):
 *
 * === RFC 분류기 (2D: DstPort × Protocol) ===
 *
 * ── 사전 계산 단계 ──
 *   Phase 0 DstPort: 65536개 포트 → 5개 eqID (축소율 99.99%)
 *     eqID=0: bitmap=00B8 → 규칙: R4 R5 R8
 *     eqID=1: bitmap=008C → 규칙: R3 R4 R8
 *     eqID=2: bitmap=00E9 → 규칙: R1 R4 R6 R8
 *     eqID=3: bitmap=009A → 규칙: R2 R4 R8
 *     eqID=4: bitmap=0088 → 규칙: R4 R8
 *   Phase 0 Protocol: 256개 값 → 4개 eqID (축소율 98.44%)
 *
 *   Phase 1: 5 × 4 = 20 조합 → 교차곱 축소
 *
 * ── 패킷 분류 (런타임) ──
 *   dport=80, TCP  → 기대: R1(ALLOW)
 *     → R1 (ALLOW)          ← 단 3회 메모리 접근!
 *   dport=22, TCP  → 기대: R5(DROP)
 *     → R5 (DROP)
 *
 * ── 메모리 사용량 ──
 *   Phase 0 DstPort 테이블: 65536 bytes
 *   Phase 0 Protocol 테이블: 256 bytes
 *   Phase 1 교차곱 테이블: 80 bytes
 *   총합: 65872 bytes (~64 KB)
 *   (참고: 선형 탐색은 128 bytes만 필요)
 *
 * → RFC는 64KB 메모리를 사용하지만,
 *   분류가 O(3) 상수 시간! (선형 탐색은 O(N×d))
 */

RFC 메모리 최적화 기법

RFC의 가장 큰 약점인 메모리 사용량을 줄이기 위한 여러 최적화 기법이 있습니다.

청크 크기 조절

Phase 0에서 16비트 청크 대신 8비트 청크를 사용하면 테이블 크기가 2¹⁶(64K) → 2⁸(256)으로 줄어듭니다. 대신 청크 수가 늘어나 Phase 단계가 더 필요합니다.

희소 교차곱 테이블

Phase 1 이상에서 교차곱 테이블의 많은 엔트리가 비어 있거나(매칭 규칙 없음) 동일한 eqID를 가집니다. 이를 해시 테이블이나 압축 배열로 대체하면 메모리를 절약할 수 있습니다. 단, 해시 룩업의 추가 지연이 발생합니다.

2단계 RFC (Two-phase RFC)

Gupta & McKeown의 원 논문에서도 제안된 변형으로, Phase 수를 2단계로 줄이는 대신 Phase 1의 교차곱 테이블이 커집니다. 반대로 4단계 이상으로 늘리면 각 테이블은 작아지지만 분류 시간이 증가합니다.

/* 2단계 RFC: 모든 Phase 0 eqID를 한 번에 결합 */
Phase 0: 7개 청크 → 7개 eqID (e₀, e₁, ..., e₆)
Phase 1: combined_eqID = table[e₀ × E₁ × ... + eₖ]  /* 단일 거대 테이블 */
         → classID (최종 규칙)

/* 장점: 2회 메모리 접근으로 분류 완료 */
/* 단점: Phase 1 테이블이 E₀×E₁×...×E₆ 크기 → 메모리 폭발 위험 */

/* 4단계 RFC: 더 세밀한 분할 */
Phase 0: 13개 청크 (8비트) → 13개 eqID
Phase 1: (e₀,e₁,e₂), (e₃,e₄,e₅), (e₆,e₇,e₈), (e₉,e₁₀,e₁₁,e₁₂)
Phase 2: (p1₀,p1₁), (p1₂,p1₃)
Phase 3: (p2₀,p2₁) → classID

/* 장점: 각 테이블이 작음 (메모리 절약) */
/* 단점: 4회 메모리 접근 (분류 시간 증가) */

실제 메모리 레이아웃과 캐시 최적화

RFC 테이블을 메모리에 배치하는 방식이 분류 성능에 직접 영향을 줍니다. CPU 캐시 계층 구조와 RFC 테이블 크기를 매핑하면 설계 선택을 최적화할 수 있습니다.

/* RFC 분류의 실제 메모리 접근 패턴 분석 */

/* Phase 0: 7개 청크 → 7회 독립 랜덤 접근 (64KB 테이블 7개) */
/* → 병렬 처리 가능, 각각 별도 64KB 영역 → 7개 잠재적 L2 미스 */
/* → 실제: 핫 트래픽은 동일 서브넷 → 같은 캐시 라인 재사용 많음 */

/* Phase 1: 3개 테이블, 합계 ~5KB → 거의 항상 L1 캐시 히트 */
/* → 3회 접근이지만 4ns × 3 = ~12ns에 불과 */

/* Phase 2: 1회 접근, 174,300 엔트리 × 2B = 340KB */
/* → 트래픽 지역성 있으면 L2 히트, 없으면 L3까지 */

/* 최악 시나리오 (모든 미스) 지연 추정: */
/*   Phase 0: 7 × 15ns(L2) = 105ns (병렬 시 15ns) */
/*   Phase 1: 3 × 4ns(L1)  = 12ns                */
/*   Phase 2: 1 × 15ns(L2) = 15ns                */
/*   → 순차 합계: ~132ns, 병렬 Phase 0 시: ~42ns  */

/* 10Gbps, 64-byte 패킷: 14.88Mpps 필요 → 패킷당 67ns 예산 */
/* Phase 0 병렬화(SIMD 또는 out-of-order 실행) 시 충분히 가능 */

RFC 변형 및 발전 알고리즘

RFC의 핵심 아이디어(동치 클래스 기반 다단계 축소)는 이후 많은 연구에서 개선되었습니다. 각 변형은 RFC의 특정 약점(메모리 폭발, 업데이트 불가, IPv6 확장 등)을 해결하려는 시도입니다.

ABV (Aggregated Bit Vector)

Baboescu & Varghese (2001)이 제안한 ABV는 RFC의 비트맵(bit vector)을 집계(aggregation)하여 메모리를 절약하는 기법입니다.

핵심 아이디어

RFC에서 각 eqID는 N비트 비트맵을 유지합니다 (N = 규칙 수). 규칙이 10,000개이면 비트맵 하나가 1.25KB입니다. ABV는 이 긴 비트맵을 A비트 집계 비트맵으로 요약합니다.

/* ABV: 비트맵 집계 */
/* 원본 비트맵 (N=16 규칙 예시): */
bitmap = 0100 0000 1000 0010

/* 4비트 그룹별 집계 (A=4): */
/* 그룹0: 0100 → 1 (하나 이상 1) */
/* 그룹1: 0000 → 0 */
/* 그룹2: 1000 → 1 */
/* 그룹3: 0010 → 1 */
aggregated = 1011  /* N/4 = 4비트로 축소 */

/* 교차곱 시: aggregated 비트맵끼리 AND → 빠른 사전 필터링 */
/* 0인 그룹은 원본 비트맵 비교를 건너뜀 → 속도 향상 */

DRFC (Distributed RFC)

RFC를 여러 병렬 처리 유닛에 분산하여, 단일 메모리 한계를 극복하는 변형입니다. FPGA나 NPU(Network Processing Unit)에서 자주 사용됩니다.

분산 전략

• Phase-level 병렬: Phase 0의 7개 청크 테이블을 7개 처리 유닛에 분배. 각 유닛이 독립적으로 eqID를 계산하고, 결과를 결합 유닛으로 전달
• Pipeline 병렬: 패킷 1이 Phase 1을 처리하는 동안, 패킷 2가 Phase 0을 처리. 분류 지연은 줄지 않지만 처리량(throughput)이 Phase 수만큼 증가
• 규칙 분할: 규칙 집합을 여러 부분으로 나누어 각각 독립적인 RFC를 구축. 최종 결과를 우선순위 비교로 합병

Incremental RFC (증분 RFC)

원 RFC의 가장 큰 실무적 약점은 규칙 변경 시 전체 재계산이 필요하다는 것입니다. 증분 RFC(Incremental RFC)는 규칙 추가/삭제 시 영향받는 eqID만 부분 갱신하여 이 문제를 완화합니다.

증분 업데이트 원리

/* 증분 규칙 추가: 규칙 Rnew 추가 시 */

/* Step 1: Phase 0 — 영향받는 eqID 식별 */
for each chunk table T:
    for each value v in Rnew.field_range:
        old_bitmap = T.bitmap[v]
        new_bitmap = old_bitmap | (1 << Rnew.id)
        if new_bitmap != old_bitmap:
            /* 이 값의 비트맵이 변경됨 → eqID 재할당 필요 */
            T.bitmap[v] = new_bitmap
            if new_bitmap not in eqID_map:
                eqID_map[new_bitmap] = allocate_new_eqID()
            T.table[v] = eqID_map[new_bitmap]
            changed_eqIDs.add(T.table[v])

/* Step 2: Phase 1+ — 영향받는 교차곱만 재계산 */
for each changed_eqID in Phase k:
    /* 이 eqID가 포함된 교차곱 엔트리만 갱신 */
    for each partner_eqID in adjacent_table:
        recalculate_combined(changed_eqID, partner_eqID)
        /* 새 combined_bitmap → 새 eqID 할당 or 기존 eqID 재사용 */

확장 RFC (Extended RFC)

원 RFC는 IPv4 5-tuple(104비트)에 최적화되어 있지만, 현대 네트워크에서는 더 많은 필드가 필요합니다.

IPv6 확장

IPv6 주소는 128비트로, 16비트 청크로 나누면 출발지+목적지만 16개 청크가 필요합니다. Phase 0 테이블만 16 × 64KB = 1MB이지만, 이후 Phase에서 동치 클래스 축소가 IPv4보다 더 극적으로 발생합니다(IPv6 주소 공간의 대부분이 미사용이므로).

다중 필드 확장 (Beyond 5-tuple)

SDN/OpenFlow 환경에서는 5-tuple 외에도 VLAN ID, MPLS 라벨, 터널 ID, 메타데이터 등 최대 40+개 필드를 매칭해야 합니다. RFC를 이런 환경에 확장할 때의 고려사항:

• 필드 선택: 모든 필드를 Phase 0 청크로 포함하면 테이블이 폭발합니다. 실제 규칙에서 사용되는 필드만 동적으로 선택합니다
• 계층적 RFC: L2 필드(MAC, VLAN)와 L3/L4 필드(IP, Port)를 별도 RFC로 구축하고 결과를 합성합니다
• 와일드카드 필드 제외: 모든 규칙에서 와일드카드인 필드는 분류에 기여하지 않으므로 Phase 0에서 제외합니다

RFC의 하드웨어 구현

RFC의 규칙적인 메모리 접근 패턴은 하드웨어 구현에 매우 적합합니다. FPGA, ASIC, NPU에서의 구현 전략입니다.

FPGA 기반 RFC

/* FPGA에서의 RFC 구현 구조 */

/* Phase 0: BRAM(Block RAM)에 룩업 테이블 저장 */
/* 7개 청크 × 64KB = 448KB → FPGA BRAM에 적합 */
/* 7개 테이블을 7개 BRAM 포트에서 동시 접근 → 1 클럭 */

/* Phase 1: 3개 결합 테이블도 BRAM 저장 */
/* 결합 A: 48×24 = 1,152 엔트리 → 소형 BRAM */
/* 결합 B: 52×31 = 1,612 엔트리 → 소형 BRAM */
/* 결합 C: 18×25×5 = 2,250 엔트리 → 소형 BRAM */

/* Phase 2: 60×83×35 → 해시 기반 or 직접 테이블 */

/* 파이프라인: Phase 0 → 레지스터 → Phase 1 → 레지스터 → Phase 2 */
/* 총 지연: 3 클럭, 처리량: 1 패킷/클럭 */
/* 200MHz FPGA에서: 200M 패킷/초 ≈ 100Gbps (64B 패킷) */

SmartNIC ASIC (P4 + RFC)

현대 프로그래머블 스위치 ASIC(Intel Tofino, NVIDIA Spectrum 등)은 MAT(Match-Action Table) 파이프라인을 제공합니다. 이 파이프라인은 RFC의 다단계 구조와 자연스럽게 매핑됩니다:

• Stage 0 (Phase 0): 각 MAT 스테이지에서 하나의 헤더 필드를 exact/ternary 매칭 → eqID 할당 (액션으로 메타데이터에 저장)
• Stage 1+ (Phase 1+): 이전 스테이지의 메타데이터(eqID)를 입력으로 다음 MAT에서 결합 룩업
• 최종 Stage: classID로 최종 액션(fwd/drop/encap) 결정

RFC와 다른 알고리즘의 하이브리드

RFC + Tuple Space (Hybrid)

RFC의 빠른 분류 속도와 튜플 공간의 빠른 업데이트를 결합하는 하이브리드 접근입니다.

• 핫 규칙(Hot Rules): 자주 매칭되는 상위 규칙을 RFC로 사전 계산하여 초고속 분류
• 콜드 규칙(Cold Rules): 드물게 매칭되는 규칙은 튜플 공간 탐색으로 처리
• RFC 미스 시 튜플 공간으로 폴백 → 업데이트는 튜플 공간에서 즉시 반영
• 주기적으로(또는 규칙 변경 시) RFC를 재구축하여 핫 규칙 갱신

RFC + Decision Tree (CutSplit)

Li et al. (2016)의 CutSplit은 규칙셋을 큰 필드(IP 주소)와 작은 필드(Port, Protocol)로 분리하여, 큰 필드는 결정 트리(HiCuts)로, 작은 필드는 RFC-like 교차곱으로 처리합니다.

• IP 주소의 넓은 와일드카드 규칙이 결정 트리의 규칙 복제를 유발하는 문제를 회피
• Port/Protocol은 값 공간이 작으므로 RFC 교차곱이 관리 가능
• 두 단계의 분류 결과를 합성하여 최종 규칙 결정

NeuroCuts — 강화학습 기반 결정 트리

Liang et al. (2019)의 NeuroCuts는 강화학습(Reinforcement Learning)으로 결정 트리의 분할 전략을 학습합니다. HiCuts/HyperCuts의 휴리스틱(차원 선택, 분할 수)을 신경망이 대체하여, 규칙셋 특성에 맞는 최적 트리를 자동 생성합니다.

패킷 분류 알고리즘 발전 연대기

TCAM (Ternary Content-Addressable Memory)

TCAM(Ternary Content-Addressable Memory)은 하드웨어 수준에서 모든 엔트리를 동시에(병렬로) 비교하는 특수 메모리입니다. 각 비트 셀은 0, 1, X(don't care, 와일드카드) 세 가지 상태를 가질 수 있어, 접두사와 와일드카드를 자연스럽게 표현합니다.

동작 원리

1. 엔트리 저장: 각 규칙을 (Value, Mask) 쌍으로 TCAM에 프로그래밍합니다. Mask의 X 비트는 해당 위치를 무시합니다
2. 병렬 비교: 검색 키(패킷 헤더)가 입력되면, 모든 엔트리가 동시에 비교를 수행합니다
3. 우선순위 인코더: 매칭된 엔트리 중 가장 낮은 인덱스(= 가장 높은 우선순위)를 선택합니다
4. 액션 조회: 매칭 인덱스로 연관 SRAM(Associated RAM)에서 액션을 읽습니다

TCAM의 한계

범위-접두사 확장 (Range-to-Prefix Expansion)

TCAM은 접두사(prefix)만 자연스럽게 표현하므로, 포트 범위를 TCAM에 넣으려면 여러 접두사 엔트리로 분해해야 합니다. 이 확장이 실제 엔트리 소모를 크게 늘릴 수 있습니다.

예시: 포트 범위 1024-65535의 접두사 분해

/* 범위 1024-65535 (0x0400 - 0xFFFF) → 접두사로 분해 */
0x0400-0x07FF → 0000 01XX XXXX XXXX  /* /6  (1024-2047)  */
0x0800-0x0FFF → 0000 1XXX XXXX XXXX  /* /5  (2048-4095)  */
0x1000-0x1FFF → 0001 XXXX XXXX XXXX  /* /4  (4096-8191)  */
0x2000-0x3FFF → 001X XXXX XXXX XXXX  /* /3  (8192-16383) */
0x4000-0x7FFF → 01XX XXXX XXXX XXXX  /* /2  (16384-32767)*/
0x8000-0xFFFF → 1XXX XXXX XXXX XXXX  /* /1  (32768-65535)*/

/* 총 6개 TCAM 엔트리 필요 (1개 범위 → 6개로 확장) */

TCAM 최적화 알고리즘

TCAM 최소화 (TCAM Minimization)

동일한 분류 결과를 내면서 TCAM 엔트리 수를 최소화하는 것은 비용과 전력 절감에 직결됩니다. 주요 기법들입니다.

접두사 최소화 (Prefix Minimization): 인접하거나 겹치는 접두사 규칙을 더 짧은 접두사로 통합합니다.

/* 접두사 최소화 예시: ACCEPT 규칙 집합 */
/* 원본: 192.168.1.0/24, 192.168.2.0/24, 192.168.3.0/24 → 3개 엔트리 */
/* 최소화: 세 접두사가 192.168.0.0/22에 포함 → 1개 엔트리로 통합 */
/* 단, 192.168.0.0/24는 다른 규칙이면 분리 유지 필요 */

/* 중복 제거 (Redundancy Removal): */
/* R1: 192.168.0.0/16 → ALLOW */
/* R2: 192.168.1.0/24 → ALLOW  ← R1의 부분집합이고 같은 액션 → 중복! */
/* R2 제거 가능 — R1이 R2의 모든 패킷을 같은 액션으로 처리 */

삼진 시뮬레이션 (Ternary Simulation): 규칙 집합 전체에서 don't-care 비트를 최대화하여 엔트리 수를 줄이는 기법입니다. 이진 결정 다이어그램(BDD)으로 구현할 수 있습니다.

범위 인코딩 기법 (Range Encoding)

포트 범위를 TCAM 접두사로 변환할 때 필요한 엔트리 수를 최소화하는 인코딩 방법들입니다.

DIRPE(Database-Independent Range Pre-Encoding)는 모든 16비트 범위 [a, b]를 최대 W-1=15개의 TCAM 접두사로 표현할 수 있도록 주소 공간을 사전에 재매핑합니다. 이 인코딩은 규칙셋과 독립적으로 전체 포트 공간에 적용되므로 "데이터베이스 독립적"입니다.

TCAM 에너지 절약

TCAM의 가장 큰 약점은 병렬 비교로 인한 높은 전력 소모입니다. 에너지 절약 기법들입니다.

• 블록 기반 활성화(Block-based Activation): TCAM을 여러 블록으로 나누고, 패킷에 따라 관련 블록만 활성화합니다. 첫 번째 필드(예: Protocol)로 사전 분류하여 TCP 패킷은 TCP 블록만 탐색합니다
• 내용 기반 파티셔닝(Content-based Partitioning): 자주 매칭되는 규칙을 작은 크기의 별도 TCAM에 배치합니다. 히트율이 높은 "핫 규칙" TCAM만 상시 활성화하고, "콜드 규칙" TCAM은 첫 번째 미스 시에만 활성화합니다
• 분류 파이프라이닝: TCAM 탐색을 여러 사이클로 분산하여 순간 전력 소모를 낮춥니다. 지연(latency)은 증가하지만 처리량(throughput)은 유지됩니다

리눅스 커널 구현

리눅스 커널의 TC(Traffic Control) 서브시스템은 세 가지 주요 분류기(classifier)를 제공합니다. 각각 다른 패킷 분류 전략을 구현합니다.

cls_u32 내부

cls_u32(net/sched/cls_u32.c)는 리눅스 커널의 가장 오래된 범용 분류기로, 오프셋 기반 패턴 매칭과 해시 테이블을 결합합니다.

/* net/sched/cls_u32.c — 핵심 구조체 */

struct tc_u_hnode {
    struct tc_u_hnode __rcu  *next;
    u32                      handle;
    u32                      prio;
    int                      refcnt;
    unsigned int             divisor;   /* 해시 테이블 크기 */
    struct tc_u_knode __rcu  *ht[1];    /* 해시 버킷 배열 */
};

struct tc_u_knode {
    struct tc_u_knode __rcu  *next;
    u32                      handle;
    struct tc_u_hnode        *ht_up;    /* 상위 해시 노드 */
    struct tcf_exts          exts;      /* 액션 */
    struct tcf_result        res;
    struct tc_u_hnode        *ht_down;  /* 다음 레벨 해시 */
    struct tc_u32_sel        sel;       /* 매칭 셀렉터 */
};

struct tc_u32_sel {
    unsigned char  flags;
    unsigned char  offshift;    /* 오프셋 시프트 */
    unsigned char  nkeys;       /* 키 개수 */
    __be16         offmask;     /* 오프셋 마스크 */
    __u16          off;         /* 기본 오프셋 */
    short          offoff;      /* 오프셋의 오프셋 */
    short          hoff;        /* 해시 오프셋 */
    __be32         hmask;       /* 해시 마스크 */
    struct tc_u32_key keys[];   /* 매칭 키 배열 */
};

cls_u32의 분류 과정은 다음과 같습니다.

1. 패킷 데이터에서 지정된 오프셋의 32비트 값을 읽습니다
2. 해당 값에 마스크를 적용하고 해시 테이블의 버킷을 선택합니다
3. 버킷 내의 키 노드(tc_u_knode)를 순차 비교합니다
4. 모든 키가 매칭되면 액션을 적용하거나 다음 레벨 해시로 이동합니다

cls_u32 사용 예시

# 2단계 u32 분류: DstPort로 1차 해시, SrcIP로 2차 매칭

# Root 해시 테이블 (divisor=256, DstPort 하위 8비트로 해시)
$ tc filter add dev eth0 parent 1:0 prio 1 protocol ip \
    handle 1: u32 divisor 256

# DstPort=80 → bucket 80으로 분류하는 해시 키
$ tc filter add dev eth0 parent 1:0 prio 1 protocol ip \
    u32 ht 800:: match ip dport 80 0xffff \
    hashkey mask 0x000000ff at 20 \
    link 1:

# Bucket 80에서 SrcIP=192.168.1.0/24 매칭 → class 1:10
$ tc filter add dev eth0 parent 1:0 prio 1 protocol ip \
    u32 ht 1:50: match ip src 192.168.1.0/24 \
    flowid 1:10

cls_flower 내부

cls_flower(net/sched/cls_flower.c)는 마스크 기반 해시를 사용하는 현대적인 분류기로, tc flower 명령으로 사용됩니다.

/* net/sched/cls_flower.c — 핵심 구조체 */

struct cls_fl_head {
    struct rhashtable       ht;           /* 리사이즈 가능 해시 */
    struct list_head        masks;        /* 마스크 목록 */
    struct rcu_head         rcu;
};

struct fl_flow_key {
    struct flow_dissector_key_control control;
    struct flow_dissector_key_basic   basic;     /* n_proto, ip_proto */
    struct flow_dissector_key_ipv4_addrs ipv4;   /* src, dst */
    struct flow_dissector_key_ports   tp;        /* src, dst port */
    struct flow_dissector_key_vlan    vlan;
    struct flow_dissector_key_eth_addrs eth;
    /* ... 더 많은 필드 */
};

struct fl_flow_mask {
    struct fl_flow_key      key;          /* 마스크 값 */
    struct list_head        list;
    struct rhashtable       ht;           /* 이 마스크의 해시 테이블 */
    struct rhashtable_params filter_ht_params;
};

cls_flower의 분류는 튜플 공간 탐색과 유사합니다.

1. 패킷에서 fl_flow_key를 추출합니다 (fl_classify → skb_flow_dissect)
2. 등록된 각 마스크(fl_flow_mask)에 대해 키를 마스킹합니다
3. 마스킹된 키로 해당 마스크의 해시 테이블(rhashtable)에서 룩업합니다
4. 매칭되면 해당 필터의 액션을 반환합니다

cls_flower 사용 예시와 마스크 최적화

# 같은 마스크(SrcIP/24 + DstPort/exact)를 사용하는 규칙들
# → 하나의 마스크/해시 테이블로 통합 → 효율적
$ tc filter add dev eth0 ingress protocol ip flower \
    src_ip 192.168.1.0/24 ip_proto tcp dst_port 80 \
    action ok

$ tc filter add dev eth0 ingress protocol ip flower \
    src_ip 192.168.2.0/24 ip_proto tcp dst_port 80 \
    action ok

# 다른 마스크(DstIP/16)를 사용하는 규칙
# → 별도 마스크/해시 테이블 생성 → 마스크 수 증가
$ tc filter add dev eth0 ingress protocol ip flower \
    dst_ip 10.0.0.0/16 ip_proto udp dst_port 53 \
    action ok

# 마스크 수 확인
$ tc -s filter show dev eth0 ingress
# 마스크가 2개이면 최대 2회 해시 룩업

fl_classify() 커널 코드 분석

fl_classify()(net/sched/cls_flower.c)는 cls_flower의 핵심 분류 함수입니다. 마스크 순회와 rhashtable 룩업의 전체 흐름을 분석합니다.

/* net/sched/cls_flower.c — fl_classify() 핵심 흐름 */

static int fl_classify(struct sk_buff *skb, const struct tcf_proto *tp,
                      struct tcf_result *res)
{
    struct cls_fl_head *head = rcu_dereference_bh(tp->root);
    bool post_filter = !tc_skip_sw(tp->cls_flags);
    struct fl_flow_key skb_key;
    struct fl_flow_mask *mask;
    struct cls_fl_filter *f;

    /* 1단계: skb에서 fl_flow_key 추출 (flow dissector 사용) */
    fl_clear_hw_stats(skb, tp, post_filter);
    skb_flow_dissect_meta(skb, &skb_key);
    /* 패킷 헤더에서 MAC, VLAN, IP, L4 등 모든 필드 추출 */
    skb_flow_dissect(skb, &head->dissector,
                     &skb_key, FLOW_DISSECTOR_F_STOP_BEFORE_ENCAP);

    /* 2단계: 등록된 마스크 목록을 순차 순회 */
    list_for_each_entry_rcu(mask, &head->masks, list) {
        struct fl_flow_key mkey;

        /* 3단계: 패킷 키에 현재 마스크 적용 */
        fl_set_masked_key(&mkey, &skb_key, mask);

        /* 4단계: rhashtable에서 마스킹된 키로 O(1) 룩업 */
        f = rhashtable_lookup_fast(&mask->ht, &mkey,
                                   mask->filter_ht_params);
        if (f && f->flags & TCA_CLS_FLAGS_SKIP_SW)
            continue;

        if (f) {
            /* 매칭! 결과 저장 후 액션 평가 */
            *res = f->res;
            return tcf_exts_exec(skb, &f->exts, res);
        }
    }
    return -1;  /* 미스 — 다음 tc filter로 진행 */
}

/* fl_set_masked_key: skb_key & mask → mkey */
static void fl_set_masked_key(struct fl_flow_key *mkey,
                             struct fl_flow_key *key,
                             struct fl_flow_mask *mask)
{
    const long *lkey = (long *) key;
    const long *lmask = (long *) &mask->key;
    long *ldst = (long *) mkey;
    int i;

    /* 워드 단위 AND 연산으로 마스킹 — 매우 빠름 */
    for (i = 0; i < sizeof(*mkey) / sizeof(long); i++)
        ldst[i] = lkey[i] & lmask[i];
}

flow_dissect 통합: skb_flow_dissect()는 패킷 파싱을 담당하며, L2(Ethernet/VLAN), L3(IPv4/IPv6/MPLS), L4(TCP/UDP/ICMP), 터널(VXLAN/GRE) 헤더를 모두 파싱합니다. 결과는 fl_flow_key 구조체에 저장되며, 이후 마스킹과 해시 룩업에 사용됩니다.

u32_classify() 커널 코드 분석

u32_classify()(net/sched/cls_u32.c)는 해시 기반 분류를 수행합니다. 해시 계산과 버킷 선택, 키 매칭 루프를 분석합니다.

/* net/sched/cls_u32.c — u32_classify() 핵심 흐름 */

static int u32_classify(struct sk_buff *skb, const struct tcf_proto *tp,
                       struct tcf_result *res)
{
    struct {
        struct tc_u_knode *knode;
        unsigned int       off;
    } stack[TC_U32_MAXDEPTH];

    struct tc_u_hnode *ht = rcu_dereference_bh(tp->root);
    unsigned int       off = skb_network_offset(skb);  /* IP 헤더 오프셋 */
    struct tc_u_knode *n;
    int                sdepth = 0, depth = 0;

next_ht:
    /* 현재 해시 테이블에서 버킷 선택 */
    n = ht->ht[TC_U32_HASH(ht->handle)];  /* 루트 버킷으로 시작 */

next_knode:
    if (n) {
        struct tc_u32_key *key = n->sel.keys;
        int                i;

        /* 패킷 헤더에서 해시 값 계산 */
        if (n->sel.hmask) {
            unsigned int hval;
            unsigned int *data;

            /* hoff 오프셋의 32비트를 hmask로 AND → 해시 버킷 인덱스 */
            data  = skb_header_pointer(skb, off + n->sel.hoff,
                                       sizeof(hval), &hval);
            if (!data)
                goto out;
            hval = (__force unsigned int) *data & n->sel.hmask;
            hval ^= hval >> 16;
            hval ^= hval >>  8;
            n = ht->ht[TC_U32_HASH(hval)];  /* 버킷 선택 */
            goto next_knode;
        }

        /* 키 배열 순차 비교: 모든 key가 매칭되어야 함 */
        for (i = n->sel.nkeys; i > 0; i--, key++) {
            unsigned int *data;
            __be32        hdata;

            data = skb_header_pointer(skb, off + key->off,
                                      sizeof(hdata), &hdata);
            if (!data)
                goto next;
            /* (패킷 데이터 & key->mask) == key->val */
            if ((*data & key->mask) != key->val)
                goto next;      /* 불매칭 → 다음 knode */
        }

        /* 모든 키 매칭: ht_down이 있으면 다음 레벨로 */
        if (n->ht_down) {
            stack[sdepth].knode = n;
            stack[sdepth].off   = off;
            sdepth++;
            ht  = n->ht_down;
            off = off + n->sel.offmask;  /* 오프셋 조정 */
            goto next_ht;
        }

        /* 최종 매칭: 액션 적용 */
        *res = n->res;
        return tcf_exts_exec(skb, &n->exts, res);

next:
        n = rcu_dereference_bh(n->next);   /* 체인의 다음 knode */
        goto next_knode;
    }
out:
    return -1;
}

nftables 패킷 분류와의 비교

nftables는 TC 분류기와는 다른 방식으로 패킷 분류를 구현합니다. nf_tables_eval()을 통한 규칙 평가와 내장 set/map 인프라를 이해하면 TC 분류기와의 적절한 선택 기준을 알 수 있습니다.

/* net/netfilter/nf_tables_core.c — nf_tables_eval() */

unsigned int nft_do_chain(struct nft_pktinfo *pkt, void *priv)
{
    const struct nft_chain *chain = priv;
    const struct nft_rule_dp *rule = nft_rule_first(chain);
    unsigned int stackptr = 0;

next_rule:
    /* 규칙을 순차 평가 — 기본적으로 선형 탐색 */
    while (!nft_rule_is_last(chain, rule)) {
        const struct nft_expr *expr = nft_expr_first(rule);

        while (nft_expr_more(rule, expr)) {
            /* 각 매치/액션 표현식 평가 */
            if (expr->ops->eval(pkt, pkt->regs, expr) ==
                NFT_BREAK)
                goto next_rule;
            expr = nft_expr_next(expr);
        }
        /* 모든 표현식 통과 → verdict 반환 */
        switch (pkt->regs.verdict.code) {
        case NFT_CONTINUE:
            rule = nft_rule_next(rule);
            continue;
        case NFT_JUMP: case NFT_GOTO:
            /* 체인 점프: nft_set lookup으로 구현 */
            chain = pkt->regs.verdict.chain;
            goto next_rule;
        }
    }
    return nft_rule_default_verdict(chain);
}

/* nftables set: 다양한 백엔드 지원 */
/* hash set:   O(1) 룩업 — exact match */
/* rbtree set: O(log N) — ranges, intervals */
/* bitmap set: O(1) — small integer domains */
/* pipapo:     Piece-wise Incrementally Pruning AND-ing of Partial Overlaps */
/*             — 다차원 매칭 최적화 (kernel 5.6+) */

pipapo(Piece-wise Incrementally Pruning AND-ing of Partial Overlaps)는 nftables의 고급 set 백엔드로, 다차원 매칭(RFC와 유사한 비트맵 교차)을 구현합니다. 단순 hash/rbtree보다 복잡한 규칙셋에서 우수한 성능을 보입니다.

XDP 기반 초고속 분류

XDP(eXpress Data Path)는 NIC 드라이버에서 패킷을 받자마자 처리하는 가장 빠른 경로입니다. 커널 네트워크 스택을 우회하므로 TC보다 훨씬 낮은 오버헤드로 패킷을 분류할 수 있습니다.

XDP 분류의 이점:

• 스택 바이패스: sk_buff 할당 없음 → 메모리 할당 오버헤드 제거
• 매우 이른 처리: NIC 드라이버 수신 직후 → 최소 지연
• BPF 맵으로 고성능 분류 자료구조 활용 가능
• AF_XDP로 유저스페이스에 패킷 직접 전달 가능

/* XDP BPF 프로그램: LPM 트라이 + 해시 맵으로 5-tuple 분류 */
/* kernel/samples/bpf/ 스타일 예시 */

/* BPF 맵 정의 */
struct {
    __uint(type, BPF_MAP_TYPE_LPM_TRIE);  /* Src/Dst IP 접두사 */
    __uint(max_entries, 1024);
    __type(key, struct bpf_lpm_trie_key_u8);
    __type(value, __u32);                 /* 정책 ID */
    __uint(map_flags, BPF_F_NO_PREALLOC);
} ip_policy_map SEC(".maps");

struct {
    __uint(type, BPF_MAP_TYPE_HASH);      /* 5-tuple → 정책 */
    __uint(max_entries, 100000);
    __type(key, struct flow_key5);
    __type(value, __u32);
} flow_policy_map SEC(".maps");

struct flow_key5 {
    __u32 src_ip, dst_ip;
    __u16 src_port, dst_port;
    __u8  proto;
};

SEC("xdp")
int xdp_classifier(struct xdp_md *ctx)
{
    void *data     = (void *)(long)ctx->data;
    void *data_end = (void *)(long)ctx->data_end;
    struct ethhdr *eth = data;
    struct iphdr  *ip;
    struct tcphdr *tcp;
    struct flow_key5 key = {};
    __u32 *policy;

    /* 헤더 파싱 */
    if (eth + 1 > (struct ethhdr *)data_end)
        return XDP_DROP;
    if (eth->h_proto != bpf_htons(ETH_P_IP))
        return XDP_PASS;

    ip = (struct iphdr *)(eth + 1);
    if (ip + 1 > (struct iphdr *)data_end)
        return XDP_DROP;

    key.src_ip = ip->saddr;
    key.dst_ip = ip->daddr;
    key.proto  = ip->protocol;

    if (ip->protocol == IPPROTO_TCP) {
        tcp = (struct tcphdr *)((u8 *)ip + (ip->ihl << 2));
        if (tcp + 1 > (struct tcphdr *)data_end)
            return XDP_DROP;
        key.src_port = tcp->source;
        key.dst_port = tcp->dest;
    }

    /* 1단계: 5-tuple 해시 룩업 (정확 매칭) */
    policy = bpf_map_lookup_elem(&flow_policy_map, &key);
    if (policy)
        return (*policy == POLICY_DROP) ? XDP_DROP : XDP_PASS;

    /* 2단계: IP 접두사 LPM 트라이 룩업 */
    struct {
        struct bpf_lpm_trie_key_u8 lpm;
        __u32 addr;
    } lpm_key = { .lpm.prefixlen = 32, .addr = ip->daddr };

    policy = bpf_map_lookup_elem(&ip_policy_map, &lpm_key.lpm);
    if (policy && *policy == POLICY_DROP)
        return XDP_DROP;

    return XDP_PASS;
}

BPF 기반 다차원 분류

cls_bpf(net/sched/cls_bpf.c)는 BPF 프로그램으로 패킷을 분류합니다. BPF의 프로그래밍 자유도를 활용하면 RFC 아이디어를 포함한 다양한 분류 전략을 구현할 수 있습니다.

BPF 맵을 활용한 RFC-like 패턴

/* RFC 아이디어를 BPF 맵으로 구현하는 설계 예시 */

/* Phase 0 테이블: 각 필드별 해시 맵 */
struct {
    __uint(type, BPF_MAP_TYPE_HASH);
    __uint(max_entries, 65536);
    __type(key, __u16);        /* 필드 값 (예: dst port) */
    __type(value, __u8);       /* eqID */
} phase0_dport SEC(".maps");

/* Phase 1 테이블: 결합된 eqID → 최종 classID */
struct {
    __uint(type, BPF_MAP_TYPE_HASH);
    __uint(max_entries, 4096);
    __type(key, struct combined_key);  /* {eqID_src, eqID_dst, eqID_port} */
    __type(value, __u32);              /* classID → TC class */
} phase1_combined SEC(".maps");

SEC("classifier")
int rfc_classify(struct __sk_buff *skb)
{
    /* Phase 0: 각 필드에서 eqID 조회 */
    __u16 dport = skb->data[/* dst port offset */];
    __u8 *eq_dport = bpf_map_lookup_elem(&phase0_dport, &dport);

    /* ... 다른 필드도 동일하게 */

    /* Phase 1: 결합 조회 */
    struct combined_key ckey = { .eq_src = *eq_src, .eq_dst = *eq_dst, .eq_port = *eq_dport };
    __u32 *classid = bpf_map_lookup_elem(&phase1_combined, &ckey);

    return classid ? *classid : TC_ACT_OK;
}

이 패턴의 장점은 BPF 맵을 유저스페이스에서 업데이트할 수 있으므로, RFC의 사전 계산을 유저스페이스 데몬이 수행하고 커널의 BPF 프로그램은 순수한 룩업만 수행하는 구조가 가능합니다.

하드웨어 분류기

최신 NIC/SmartNIC은 하드웨어 수준의 패킷 분류를 제공하며, TC flower offload를 통해 리눅스 커널과 통합됩니다.

NIC TCAM / Flow Table

• Mellanox (mlx5): e-Switch의 FDB(Forwarding Database)에 TCAM/해시 기반 flow table을 내장. mlx5_eswitch_add_offloaded_rule()로 TC flower 규칙을 하드웨어에 오프로드합니다
• Intel (ice): Flow Director와 ACL TCAM을 이용한 하드웨어 분류. ice_tc_setup_fltr()로 TC flower 규칙을 프로그래밍합니다
• Broadcom (bnxt): CFA(Context Flow Architecture) 엔진의 EM(Exact Match)/WC(Wildcard Match) 테이블을 제공합니다

SmartNIC/DPU의 RFC-like 파이프라인

NVIDIA BlueField-3 같은 DPU는 하드웨어 내에 다단계 매칭 파이프라인을 구현하여, RFC 알고리즘과 유사한 방식으로 와이어 스피드 분류를 수행합니다.

/* TC flower offload → HW 분류기 매핑 흐름 */

/* 사용자 공간: tc flower 규칙 추가 */
$ tc filter add dev eth0 ingress protocol ip flower \
    src_ip 192.168.1.0/24 dst_port 80 \
    action drop

/* 커널 경로: */
/* 1. cls_flower.c: fl_change() → 규칙 파싱 */
/* 2. cls_flower.c: fl_hw_replace_filter() → NIC 드라이버 호출 */
/* 3. 드라이버: ndo_setup_tc() → HW flow table에 규칙 삽입 */
/* 4. HW에서 패킷 분류 수행 — CPU 바이패스 */

/* 오프로드 상태 확인 */
$ tc -s filter show dev eth0 ingress
/* in_hw → HW에서 처리 중 (CPU 바이패스) */
/* not_in_hw → SW 폴백 (CPU 처리) */

/* 소프트웨어 폴백 금지 (오프로드 실패 시 에러) */
$ tc filter add dev eth0 ingress protocol ip flower \
    skip_sw \
    src_ip 192.168.1.0/24 dst_port 80 \
    action drop
/* skip_sw: SW 경로 건너뛰기 → 오프로드 실패 시 EOPNOTSUPP */

알고리즘 비교

규칙 수별 권장 전략

conntrack과 패킷 분류의 관계

연결 추적(Connection Tracking, conntrack)은 패킷 분류의 오버헤드를 극적으로 줄이는 핵심 최적화 메커니즘입니다. 첫 번째 패킷만 전체 분류 과정을 거치고, 이후 동일 연결의 패킷들은 conntrack 항목에서 직접 결과를 조회합니다.

연결 추적 기반 빠른 경로

conntrack은 각 TCP/UDP 연결에 대한 상태 항목(nf_conn)을 유지합니다. 분류 결과를 이 항목에 캐싱하면 후속 패킷은 전체 규칙셋을 다시 탐색할 필요가 없습니다.

/* conntrack 기반 분류 최적화 흐름 */

/* 첫 번째 패킷 (NEW 상태): */
/* 1. conntrack 항목 생성 (nf_conntrack_in) */
/* 2. 전체 분류기 체인 평가 (cls_flower TSS) */
/* 3. 결과(classid, mark)를 nf_conn에 저장 */
/* 4. 패킷 처리 */

/* 후속 패킷 (ESTABLISHED 상태): */
/* 1. conntrack 해시에서 nf_conn 조회 → O(1) */
/* 2. nf_conn.mark로 즉시 분류 결정 */
/* 3. 패킷 처리 (분류기 체인 평가 생략!) */

/* 예시: ct mark 기반 빠른 분류 */
/* 첫 패킷: tc flower로 분류 → action connmark save */
$ tc filter add dev eth0 ingress protocol ip flower \
    src_ip 192.168.1.0/24 ip_proto tcp dst_port 80 \
    action connmark save mask 0xffff \     # ct mark 저장
    action mark set 0x0100 pipe \          # skb mark 설정
    action gact ok

/* 후속 패킷: connmark restore로 바로 결정 */
$ tc filter add dev eth0 ingress protocol ip prio 1 flower \
    action connmark restore mask 0xffff    # ct mark → skb mark 복원

ct zone과 mark 기반 빠른 경로

conntrack zone을 사용하면 서로 다른 네임스페이스나 VRF에서 동일한 IP 주소를 독립적으로 추적할 수 있습니다. zone + mark 조합으로 복잡한 정책도 첫 번째 패킷에만 평가하고 이후 패킷은 O(1)로 처리합니다.

/* ct zone 기반 분리 추적 */
$ tc filter add dev eth0 ingress protocol ip flower \
    action ct zone 10 commit            # zone 10에 연결 추적

/* conntrack 항목 직접 확인 */
$ conntrack -L -p tcp --dport 80
tcp 6 431999 ESTABLISHED src=192.168.1.100 dst=10.1.2.3 sport=49152 dport=80 \
    src=10.1.2.3 dst=192.168.1.100 sport=80 dport=49152 [ASSURED] \
    mark=256 zone=10 use=2

/* nf_conn.mark를 이용한 정책 우회 */
$ iptables -t mangle -A PREROUTING -m connmark --mark 0x100/0x100 \
    -j ACCEPT   # mark된 연결은 즉시 ACCEPT

conntrack 최적화 실용 패턴

/* 패턴 1: TC + connmark 조합 */
/* 첫 패킷에만 cls_flower 평가, 이후 connmark로 바이패스 */
$ tc filter add dev eth0 ingress prio 10 protocol ip flower \
    ct_state tracked                         # 추적된 연결은 connmark 확인
    action connmark restore mask 0xff00 pipe \
    action goto chain 100                    # chain 100에서 mark 기반 처리

/* 추적 안 된 패킷: 전체 분류 수행 후 mark 설정 */
$ tc filter add dev eth0 ingress prio 20 protocol ip flower \
    src_ip 192.168.1.0/24 ip_proto tcp dst_port 80 \
    action ct commit mark 0x0100 mask 0xff00 \  # ct mark 저장
    action ok

/* 패턴 2: BPF + sk_lookup으로 소켓 기반 분류 */
/* 이미 소켓이 있는 연결은 sk->sk_priority로 즉시 분류 */
SEC("tc") int classify_by_socket(struct __sk_buff *skb) {
    struct bpf_sock *sk = bpf_skc_lookup_tcp(skb, ...);
    if (sk) {
        int prio = sk->priority;   /* 소켓 우선순위로 분류 */
        bpf_sk_release(sk);
        return TC_ACT_OK;
    }
    /* 새 연결: 전체 분류 */
    return full_classify(skb);
}

최신 연구 및 실무 동향

패킷 분류 분야는 SDN, 클라우드 네트워킹, 스마트NIC의 발전에 따라 지속적으로 연구가 이루어지고 있습니다. 최근 주요 연구 성과와 실무 동향을 살펴봅니다.

PartitionSort (2017)

Daly et al. (2017)이 제안한 PartitionSort는 규칙 집합을 겹치지 않는 부분으로 분할하여 각 파티션 내에서 정렬 기반 탐색을 수행합니다. 파티션 내 규칙들은 우선순위 순서로 정렬되어 이진 탐색이 가능합니다.

• 특징: 와일드카드 규칙의 겹침(overlap)을 파티션 분리로 해결
• 복잡도: 분류 O(P·log(N/P)), 업데이트 O(log N) (P = 파티션 수)
• 강점: 대규모 ACL(100K+ 규칙)에서 RFC보다 메모리 효율적

NuevoMatch (2020)

Shalom et al. (2020)의 NuevoMatch는 신경망을 이용해 규칙 집합을 인코딩합니다. 규칙 집합의 구조적 패턴을 ReLU 네트워크가 학습하여, 분류를 행렬 곱셈으로 표현합니다.

• 핵심: 규칙 집합을 신경망 가중치로 인코딩 → GPU/TPU 가속 가능
• 정확도: 완벽한 정확도 보장 (근사치 아님)
• 강점: GPU 기반 병렬 분류로 초고속 처리 가능
• 약점: 규칙 변경 시 네트워크 재학습 필요, CPU 인퍼런스는 TCAM보다 느림

P4 프로그래머블 파이프라인

P4(Programming Protocol-independent Packet Processors)는 고정된 파이프라인을 프로그래밍 가능하게 만든 언어입니다. P4 스위치(Intel Tofino, NVIDIA Spectrum)에서 RFC-like 다단계 매칭 파이프라인을 구현할 수 있습니다.

/* P4 코드 예시: RFC Phase 0~1 패턴 */
table phase0_dstport {
    key   = { hdr.tcp.dstPort : exact; }  /* Phase 0: DstPort → eqID */
    actions = { set_dport_class; }
    size  = 65536;
}

table phase0_proto {
    key   = { hdr.ipv4.protocol : exact; } /* Phase 0: Protocol → eqID */
    actions = { set_proto_class; }
    size  = 256;
}

table phase1_combined {
    key = {                               /* Phase 1: 두 eqID 결합 */
        meta.dport_class : exact;
        meta.proto_class : exact;
    }
    actions = { apply_policy; }
    size  = 4096;
}

ML 기반 규칙 배치와 TCAM 최적화

최근 연구에서는 강화학습(RL)을 이용해 TCAM 엔트리 배치를 최적화합니다.

• RL-based TCAM Compaction: 트래픽 패턴을 학습하여 자주 히트하는 규칙을 TCAM 앞쪽에 배치 → 평균 에너지 소모 감소
• NeuroCuts (2019): 결정 트리의 분할 전략을 RL로 학습 → HiCuts/HyperCuts 휴리스틱보다 우수한 트리 생성
• AutoML for Packet Classification: 규칙셋 특성을 분석하여 최적 알고리즘을 자동 선택

eBPF + 하드웨어 co-design 동향

현재 가장 활발한 실무 동향은 eBPF와 SmartNIC의 협력 설계입니다.

• BPF Offload: XDP BPF 프로그램을 NIC에서 직접 실행 (SmartNIC 지원 시). Netronome Agilio 등 지원
• P4Runtime + eBPF: P4 컨트롤 플레인에서 eBPF 데이터 플레인 제어 — 하이브리드 분류
• DPDK + eBPF: DPDK 폴링 기반 패킷 처리에 eBPF 분류 로직 통합
• AF_XDP zero-copy: XDP 분류 후 매칭 패킷을 유저스페이스로 zero-copy 전달

실습 랩 — 직접 만들어보는 패킷 분류

이 섹션에서는 리눅스 네트워크 네임스페이스를 활용하여 실제 물리 인터페이스 없이도 패킷 분류기를 실습할 수 있는 환경을 구축하고, cls_flower, cls_u32, cls_bpf 세 가지 분류기를 직접 설정합니다.

실습 환경 구축

#!/bin/bash
# lab_setup.sh — 패킷 분류 실습 환경 구축
# 루트 권한 필요: sudo bash lab_setup.sh
#
# 구조:
#   ns-client (192.168.100.1) ←veth→ ns-router ←veth→ ns-server (10.0.0.1)
#   ns-router에서 TC 분류기를 설정하여 패킷을 분류합니다.

set -e

# 1. 네임스페이스 생성
ip netns add ns-client
ip netns add ns-router
ip netns add ns-server

# 2. veth 페어 생성 및 연결
ip link add veth-c type veth peer name veth-c-r
ip link set veth-c netns ns-client
ip link set veth-c-r netns ns-router

ip link add veth-s type veth peer name veth-s-r
ip link set veth-s netns ns-server
ip link set veth-s-r netns ns-router

# 3. IP 주소 설정
ip netns exec ns-client ip addr add 192.168.100.1/24 dev veth-c
ip netns exec ns-client ip link set veth-c up
ip netns exec ns-client ip link set lo up

ip netns exec ns-router ip addr add 192.168.100.254/24 dev veth-c-r
ip netns exec ns-router ip addr add 10.0.0.254/24 dev veth-s-r
ip netns exec ns-router ip link set veth-c-r up
ip netns exec ns-router ip link set veth-s-r up
ip netns exec ns-router ip link set lo up
# IP 포워딩 활성화
ip netns exec ns-router sysctl -w net.ipv4.ip_forward=1 > /dev/null

ip netns exec ns-server ip addr add 10.0.0.1/24 dev veth-s
ip netns exec ns-server ip link set veth-s up
ip netns exec ns-server ip link set lo up

# 4. 라우팅 설정
ip netns exec ns-client ip route add default via 192.168.100.254
ip netns exec ns-server ip route add default via 10.0.0.254

# 5. 연결 확인
echo "=== 연결 테스트 ==="
ip netns exec ns-client ping -c 1 10.0.0.1 && echo "✓ 연결 성공!" || echo "✗ 연결 실패"

echo ""
echo "=== 환경 구축 완료 ==="
echo "ns-client (192.168.100.1) ↔ ns-router ↔ ns-server (10.0.0.1)"
echo ""
echo "다음 단계: ns-router에서 TC 분류기를 설정합니다."

실습 1: cls_flower — 5-tuple 기반 분류

cls_flower는 가장 사용하기 쉬운 현대적 분류기입니다. 필드 이름을 직관적으로 지정하여 규칙을 작성합니다.

#!/bin/bash
# lab_flower.sh — cls_flower 분류기 실습
# ns-router에서 실행: sudo bash lab_flower.sh

NS="ip netns exec ns-router"

# 1. ingress qdisc 추가 (TC 분류기의 진입점)
$NS tc qdisc add dev veth-c-r ingress

echo "=== cls_flower 규칙 추가 ==="

# 규칙 1: HTTP 트래픽 (TCP/80) → 허용 (mark 0x10)
$NS tc filter add dev veth-c-r ingress \
    protocol ip prio 1 flower \
    ip_proto tcp dst_port 80 \
    action skbedit mark 0x10 pipe \
    action ok
echo "R1: TCP/80 → ALLOW (mark 0x10)"

# 규칙 2: HTTPS 트래픽 (TCP/443) → 허용 (mark 0x20)
$NS tc filter add dev veth-c-r ingress \
    protocol ip prio 2 flower \
    ip_proto tcp dst_port 443 \
    action skbedit mark 0x20 pipe \
    action ok
echo "R2: TCP/443 → ALLOW (mark 0x20)"

# 규칙 3: DNS 트래픽 (UDP/53) → 허용
$NS tc filter add dev veth-c-r ingress \
    protocol ip prio 3 flower \
    ip_proto udp dst_port 53 \
    action ok
echo "R3: UDP/53 → ALLOW"

# 규칙 4: SSH 트래픽 (TCP/22) → 차단
$NS tc filter add dev veth-c-r ingress \
    protocol ip prio 4 flower \
    ip_proto tcp dst_port 22 \
    action drop
echo "R4: TCP/22 → DROP"

# 규칙 5: 나머지 모든 트래픽 → 차단 (기본 정책)
$NS tc filter add dev veth-c-r ingress \
    protocol ip prio 100 matchall \
    action drop
echo "R5: 기본 → DROP"

# 2. 규칙 확인
echo ""
echo "=== 설치된 규칙 확인 ==="
$NS tc -s filter show dev veth-c-r ingress

# 3. 테스트
echo ""
echo "=== 분류 테스트 ==="

# HTTP 테스트 — 통과해야 함
echo -n "TCP/80 (HTTP):  "
ip netns exec ns-server python3 -c "
import socket; s=socket.socket(); s.setsockopt(socket.SOL_SOCKET,socket.SO_REUSEADDR,1)
s.bind(('0.0.0.0',80)); s.listen(1); s.settimeout(2)
try: c,_=s.accept(); c.close()
except: pass
s.close()
" &
sleep 0.2
ip netns exec ns-client timeout 1 bash -c \
  "echo test | nc -w1 10.0.0.1 80" 2>/dev/null \
  && echo "✓ 통과 (ALLOW)" || echo "✗ 차단됨 (DROP)"
wait 2>/dev/null

# SSH 테스트 — 차단되어야 함
echo -n "TCP/22 (SSH):   "
ip netns exec ns-client timeout 1 bash -c \
  "echo test | nc -w1 10.0.0.1 22" 2>/dev/null \
  && echo "✓ 통과 (ALLOW)" || echo "✗ 차단됨 (DROP) ← 정상!"

# 4. 패킷 카운터 확인
echo ""
echo "=== 패킷 카운터 ==="
$NS tc -s filter show dev veth-c-r ingress | grep -A2 'flower\|matchall'

실습 2: cls_u32 — 오프셋 기반 분류

cls_u32는 패킷의 특정 바이트 오프셋에서 값을 읽어 비교합니다. 유연하지만 설정이 복잡합니다. 아래 예시에서 IP 헤더의 프로토콜 필드와 TCP 목적지 포트를 직접 오프셋으로 지정합니다.

#!/bin/bash
# lab_u32.sh — cls_u32 분류기 실습
# u32는 패킷의 바이트 오프셋을 직접 지정하여 매칭합니다.
#
# IP 헤더 구조 (오프셋은 IP 헤더 시작 기준):
#   오프셋 0:  Version(4b) + IHL(4b) + DSCP(8b) + Total Length(16b)
#   오프셋 8:  TTL(8b) + Protocol(8b) + Checksum(16b)
#   오프셋 12: Source IP (32b)
#   오프셋 16: Destination IP (32b)
#
# TCP/UDP 헤더 (IP 헤더 다음):
#   오프셋 0:  Source Port(16b) + Destination Port(16b)

NS="ip netns exec ns-router"

# 이전 규칙 정리
$NS tc qdisc del dev veth-c-r ingress 2>/dev/null || true
$NS tc qdisc add dev veth-c-r ingress

echo "=== cls_u32 규칙 추가 ==="

# 규칙 1: IP 프로토콜 = TCP(6) AND 목적지 포트 = 80
# match u8 6 0xff at 9     → IP 헤더 오프셋 9에서 1바이트 = Protocol
# match u16 80 0xffff at 22 → IP 헤더 오프셋 20 + TCP 오프셋 2 = Dst Port
$NS tc filter add dev veth-c-r ingress \
    protocol ip prio 1 u32 \
    match ip protocol 6 0xff \
    match ip dport 80 0xffff \
    action ok
echo "R1: protocol=TCP(6) AND dport=80 → ALLOW"

# 규칙 2: 출발지 IP가 192.168.100.0/24 → mark 설정
$NS tc filter add dev veth-c-r ingress \
    protocol ip prio 2 u32 \
    match ip src 192.168.100.0/24 \
    action skbedit mark 0xFF pipe \
    action ok
echo "R2: src=192.168.100.0/24 → ALLOW (mark 0xFF)"

echo ""
echo "=== 설치된 u32 규칙 ==="
$NS tc filter show dev veth-c-r ingress

실습 3: cls_bpf — BPF 프로그램으로 분류

BPF는 가장 유연한 분류기로, 임의의 분류 로직을 프로그래밍할 수 있습니다. 아래는 RFC 아이디어를 활용한 XDP 기반 분류기의 완전한 구현입니다.

/* xdp_classifier.c — XDP 기반 패킷 분류기
 *
 * 이 프로그램은 XDP(eXpress Data Path)에서 동작하여
 * NIC 드라이버 수준에서 패킷을 분류합니다.
 *
 * 컴파일:
 *   clang -O2 -target bpf -c xdp_classifier.c -o xdp_classifier.o
 *
 * 로드:
 *   ip link set dev eth0 xdp obj xdp_classifier.o sec xdp
 *
 * 해제:
 *   ip link set dev eth0 xdp off
 */
#include <linux/bpf.h>
#include <linux/if_ether.h>
#include <linux/ip.h>
#include <linux/tcp.h>
#include <linux/udp.h>
#include <bpf/bpf_helpers.h>
#include <bpf/bpf_endian.h>

/* ── 분류 결과를 저장하는 BPF 맵 ── */

/* Phase 0 맵: 목적지 포트 → 동치 클래스 ID */
struct {
    __uint(type, BPF_MAP_TYPE_HASH);
    __uint(max_entries, 256);       /* 주요 포트만 등록 */
    __type(key, __u16);             /* 포트 번호 */
    __type(value, __u8);            /* eqID */
} port_class SEC(".maps");

/* Phase 1 맵: (eqID_port, protocol) → 액션 */
struct phase1_key {
    __u8 port_eq;
    __u8 proto;
};
struct phase1_val {
    __u32 action;   /* XDP_PASS=2, XDP_DROP=1 */
    __u64 packets;  /* 통계 카운터 */
};

struct {
    __uint(type, BPF_MAP_TYPE_HASH);
    __uint(max_entries, 1024);
    __type(key, struct phase1_key);
    __type(value, struct phase1_val);
} action_table SEC(".maps");

/* 통계: 프로토콜별 패킷 카운터 */
struct {
    __uint(type, BPF_MAP_TYPE_PERCPU_ARRAY);
    __uint(max_entries, 256);
    __type(key, __u32);
    __type(value, __u64);
} stats SEC(".maps");

SEC("xdp")
int xdp_classify(struct xdp_md *ctx)
{
    /* 1. 패킷 데이터 경계 확인 (BPF 검증기 필수) */
    void *data     = (void *)(long)ctx->data;
    void *data_end = (void *)(long)ctx->data_end;

    /* 2. 이더넷 헤더 파싱 */
    struct ethhdr *eth = data;
    if ((void *)(eth + 1) > data_end)
        return XDP_PASS;
    if (eth->h_proto != bpf_htons(ETH_P_IP))
        return XDP_PASS;   /* IPv4가 아니면 통과 */

    /* 3. IP 헤더 파싱 */
    struct iphdr *ip = (void *)(eth + 1);
    if ((void *)(ip + 1) > data_end)
        return XDP_PASS;

    /* 4. 프로토콜별 통계 갱신 */
    __u32 proto_key = ip->protocol;
    __u64 *cnt = bpf_map_lookup_elem(&stats, &proto_key);
    if (cnt)
        (*cnt)++;

    /* 5. TCP/UDP 목적지 포트 추출 */
    __u16 dport = 0;
    if (ip->protocol == IPPROTO_TCP) {
        struct tcphdr *tcp = (void *)ip + ip->ihl * 4;
        if ((void *)(tcp + 1) > data_end)
            return XDP_PASS;
        dport = bpf_ntohs(tcp->dest);
    } else if (ip->protocol == IPPROTO_UDP) {
        struct udphdr *udp = (void *)ip + ip->ihl * 4;
        if ((void *)(udp + 1) > data_end)
            return XDP_PASS;
        dport = bpf_ntohs(udp->dest);
    }

    /* 6. Phase 0: 포트 → eqID 변환 */
    __u8 port_eq = 0xFF;  /* 기본: "나머지" 클래스 */
    __u8 *eq = bpf_map_lookup_elem(&port_class, &dport);
    if (eq)
        port_eq = *eq;

    /* 7. Phase 1: (eqID, protocol) → 액션 조회 */
    struct phase1_key key = {
        .port_eq = port_eq,
        .proto   = ip->protocol
    };
    struct phase1_val *val = bpf_map_lookup_elem(&action_table, &key);
    if (val) {
        val->packets++;
        return val->action;  /* XDP_PASS 또는 XDP_DROP */
    }

    /* 8. 기본 정책: 통과 */
    return XDP_PASS;
}

char _license[] SEC("license") = "GPL";

#!/usr/bin/python3
# xdp_loader.py — XDP 분류기 규칙 로더 (유저스페이스)
#
# 이 스크립트는 BPF 맵에 분류 규칙을 삽입합니다.
# RFC의 "사전 계산"에 해당하는 단계입니다.
#
# 사용법: sudo python3 xdp_loader.py
# 전제: xdp_classifier.o가 이미 로드되어 있어야 합니다.

import struct
import subprocess

def populate_maps():
    # Phase 0: 포트 → eqID 매핑
    port_classes = {
        22:  0,   # SSH    → eqID 0
        53:  1,   # DNS    → eqID 1
        80:  2,   # HTTP   → eqID 2
        443: 3,   # HTTPS  → eqID 3
    }
    # 나머지 포트 → eqID 0xFF (기본)

    # Phase 1: (eqID, protocol) → 액션
    # XDP_PASS=2, XDP_DROP=1
    actions = {
        (2, 6):    2,   # port_eq=2(HTTP) + TCP  → PASS
        (3, 6):    2,   # port_eq=3(HTTPS) + TCP → PASS
        (1, 17):   2,   # port_eq=1(DNS) + UDP   → PASS
        (0, 6):    1,   # port_eq=0(SSH) + TCP   → DROP
        (0xFF, 6): 2,   # 기타 포트 + TCP        → PASS
    }

    print("Phase 0: 포트 → eqID 매핑")
    for port, eq in port_classes.items():
        print(f"  port {port:5d} → eqID {eq}")
        # bpftool map update 명령으로 맵에 삽입
        # bpftool map update pinned /sys/fs/bpf/port_class \
        #   key hex $(printf '%04x' port) \
        #   value hex $(printf '%02x' eq)

    print("\nPhase 1: (eqID, protocol) → 액션")
    for (eq, proto), act in actions.items():
        act_name = "PASS" if act == 2 else "DROP"
        print(f"  (eqID={eq}, proto={proto}) → {act_name}")

populate_maps()

실습 환경 정리

#!/bin/bash
# lab_cleanup.sh — 실습 환경 정리

ip netns del ns-client 2>/dev/null
ip netns del ns-router 2>/dev/null
ip netns del ns-server 2>/dev/null
echo "실습 환경이 정리되었습니다."

분류기 선택 가이드 — 실습 요약

성능 측정과 디버깅

분류기 성능 측정

# TC 필터 통계 확인 (패킷/바이트 카운터)
$ tc -s filter show dev eth0 ingress
filter protocol ip pref 1 flower chain 0 handle 0x1
  eth_type ipv4
  ip_proto tcp
  dst_port 80
  in_hw in_hw_count 1
  action order 1: gact action drop
   random type none pass val 0
   index 1 ref 1 bind 1 installed 35 sec used 2 sec
   Action statistics:
    Sent 1523456 bytes 12847 pkt (dropped 12847, overlimits 0 requeues 0)

# bpftrace로 cls_flower 분류 지연 측정
$ bpftrace -e '
kprobe:fl_classify { @start[tid] = nsecs; }
kretprobe:fl_classify /@start[tid]/ {
    @latency_ns = hist(nsecs - @start[tid]);
    delete(@start[tid]);
}
interval:s:5 { exit(); }'

# perf로 TC 분류 핫스팟 프로파일링
$ perf record -g -e cycles -a -- sleep 10
$ perf report --sort comm,dso,sym | grep -E 'cls_|tcf_'

상세 벤치마크 방법론

분류기 성능을 정확하게 측정하려면 실제 트래픽 패턴과 유사한 부하를 발생시키고, CPU 캐시·NUMA·IRQ 어피니티 등 시스템 요인을 제거해야 합니다.

pktgen을 이용한 패킷 생성

pktgen(커널 내장 고성능 패킷 생성기)은 수백만 PPS를 발생시킬 수 있어 분류기 포화 테스트에 적합합니다.

#!/bin/bash
# pktgen으로 멀티 스트림 트래픽 발생 — 5-tuple 무작위화 포함

# pktgen 스크립트 작성
cat > /tmp/pktgen_test.sh << 'PGSCRIPT'
#!/bin/bash
# CPU 0,1에서 각 1Gbps 트래픽 발생
for cpu in 0 1; do
  echo "rem_device_all" > /proc/net/pktgen/kpktgend_$cpu
  echo "add_device eth0@$cpu"   > /proc/net/pktgen/kpktgend_$cpu
  pgdev=/proc/net/pktgen/eth0@$cpu

  echo "count 5000000"         > $pgdev   # 500만 패킷
  echo "clone_skb 1"           > $pgdev   # SKB 재사용 (캐시 압박 최소화)
  echo "pkt_size 64"           > $pgdev   # 64바이트 최소 프레임
  echo "delay 0"               > $pgdev   # 최대 속도
  echo "dst_min 10.0.0.1"      > $pgdev
  echo "dst_max 10.0.3.255"    > $pgdev   # 목적지 IP 분산 (/22 범위)
  echo "src_min 192.168.0.1"   > $pgdev
  echo "src_max 192.168.3.255" > $pgdev   # 출발지 IP 분산
  echo "udp_src_min 1024"      > $pgdev
  echo "udp_src_max 65535"     > $pgdev   # Ephemeral 포트 범위
  echo "udp_dst_min 80"        > $pgdev
  echo "udp_dst_max 8080"      > $pgdev
  echo "flag UDPSRC_RND"       > $pgdev   # UDP src 포트 무작위화
  echo "flag UDPDST_RND"       > $pgdev   # UDP dst 포트 무작위화
  echo "flag IPSRC_RND"        > $pgdev   # IP src 무작위화
  echo "flag IPDST_RND"        > $pgdev   # IP dst 무작위화
done

echo "start" > /proc/net/pktgen/pgctrl
PGSCRIPT

bash /tmp/pktgen_test.sh
# 결과 확인
cat /proc/net/pktgen/eth0@0  | grep -E 'pps|errors|pkts'

tc-testing 프레임워크

커널 소스의 tools/testing/selftests/tc-testing/은 TC 분류기의 기능 검증과 기본 성능 측정을 위한 프레임워크를 제공합니다.

#!/bin/bash
# tc-testing 프레임워크를 활용한 분류기 성능 비교

# 테스트 네임스페이스 생성 (실 인터페이스 불필요)
ip netns add cls_bench
ip netns exec cls_bench ip link add veth0 type veth peer name veth1
ip netns exec cls_bench ip link set veth0 up
ip netns exec cls_bench ip link set veth1 up

# cls_flower: 100개 규칙 설치 후 처리량 측정
ip netns exec cls_bench tc qdisc add dev veth0 ingress
for i in $(seq 1 100); do
  DPORT=$(( 8000 + i ))
  ip netns exec cls_bench tc filter add dev veth0 ingress \
    protocol ip prio $i flower ip_proto tcp dst_port $DPORT \
    action drop
done
# 규칙 수 확인
ip netns exec cls_bench tc -s filter show dev veth0 ingress | grep -c 'flower'

# pktgen으로 트래픽 발생 → TC 통계 확인
# 10초 후 카운터 변화로 PPS 계산
BEFORE=$(ip netns exec cls_bench tc -s filter show dev veth0 ingress \
  | grep 'Sent' | awk '{sum+=$3} END {print sum}')
sleep 10
AFTER=$(ip netns exec cls_bench tc -s filter show dev veth0 ingress \
  | grep 'Sent' | awk '{sum+=$3} END {print sum}')
echo "10초간 처리 패킷: $(( (AFTER - BEFORE) )) packets"
echo "PPS: $(( (AFTER - BEFORE) / 10 ))"

# 정리
ip netns del cls_bench

perf stat을 이용한 캐시 메트릭 측정

분류기의 CPU 캐시 효율은 성능의 핵심입니다. perf stat으로 LLC(Last Level Cache) 미스율을 측정합니다.

# 분류기 실행 중 캐시 메트릭 측정
$ perf stat -e \
    cache-references,\
    cache-misses,\
    LLC-loads,\
    LLC-load-misses,\
    LLC-stores,\
    LLC-store-misses,\
    cycles,\
    instructions \
  -p $(pgrep ksoftirqd/0) -- sleep 5

 Performance counter stats for process id '1234':

       1,234,567      cache-references          #  123.4 M/sec
         456,789      cache-misses              #   37.0% of all cache refs
         234,567      LLC-loads                 #   23.4 M/sec
          89,012      LLC-load-misses           #   37.9% of all LLC loads
          67,890      LLC-stores                #    6.8 M/sec
           5,678      LLC-store-misses          #    8.4% of all LLC stores
      12,345,678      cycles                    #    1.234 GHz
       8,901,234      instructions              #    0.72  insn per cycle

# 분류기별 캐시 미스 차이 (일반적 관찰값)
# cls_flower (소규모, <20 마스크): LLC miss ~5-10%
# cls_u32 (해시 충돌 없음):        LLC miss ~8-15%
# cls_flower (대규모, >50 마스크): LLC miss ~25-40%
# iptables (500+ 규칙):           LLC miss ~30-50%

# perf record로 함수별 핫스팟 분석
$ perf record -g \
    -e cycles:u \
    -e cache-misses:u \
    --call-graph dwarf \
    -C 0 \
    -- sleep 10

# 분류기 관련 함수만 필터링
$ perf report --sort comm,dso,sym --no-children \
  | grep -E 'fl_classify|u32_classify|nft_do_chain|bpf_prog_run'

# flame graph 생성 (brendangregg/FlameGraph 필요)
$ perf script | stackcollapse-perf.pl | flamegraph.pl \
    --title "Packet Classifier Hot Path" \
    --width 1200 \
    > classifier_flamegraph.svg

NUMA 고려사항

멀티 소켓 서버에서 패킷 분류기는 NUMA 지역성에 민감합니다. NIC 인터럽트와 소프트IRQ 처리가 다른 NUMA 노드에서 발생하면 메모리 접근 지연이 급증합니다.

# NIC IRQ를 특정 NUMA 노드에 고정
# eth0이 PCIe 슬롯 → NUMA node 0에 연결된 경우

# IRQ 어피니티 확인
$ cat /proc/irq/$(grep eth0 /proc/interrupts | awk '{print $1}' | tr -d :)/smp_affinity_list
0-7   # 현재 모든 CPU에 분산

# NUMA node 0 CPU (0-7)에만 IRQ 핀
$ echo 0-7 > /proc/irq/XX/smp_affinity_list

# RPS (Receive Packet Steering)도 같은 노드로
$ echo ff > /sys/class/net/eth0/queues/rx-0/rps_cpus

# XPS (Transmit Packet Steering) 설정
$ echo ff > /sys/class/net/eth0/queues/tx-0/xps_cpus

# numactl로 벤치마크 실행 (NUMA node 0 메모리 강제)
$ numactl --cpunodebind=0 --membind=0 \
    ./packet_classifier_bench --rules 1000 --pps-target 10M

실측 성능 특성

다음은 일반적인 x86-64 서버 (Intel Xeon, 10GbE NIC)에서 측정한 분류기별 성능 수치입니다. 규칙 수와 트래픽 패턴에 따라 크게 달라질 수 있습니다.

캐시 미스 분석

분류기 성능 저하의 주요 원인은 규칙 테이블이 CPU 캐시 용량을 초과할 때 발생하는 LLC 캐시 미스입니다.

캐시 미스 최적화 전략:

• 규칙 정렬: 히트율이 높은 규칙을 앞으로 배치하여 캐시 워밍 효과를 극대화합니다. 80:20 법칙 적용 — 상위 20% 규칙이 80% 트래픽을 처리
• 데이터 구조 정렬: 분류 관련 구조체를 캐시 라인(64바이트) 단위로 정렬합니다. struct tc_u_knode의 sel과 res 필드는 같은 캐시 라인에 배치
• NUMA 어피니티: NIC가 연결된 PCIe 슬롯과 같은 NUMA 노드에서 softirq를 처리합니다. 반대 노드 접근 시 지연이 40-80ns 추가됩니다
• 프리페치: BPF 프로그램에서 bpf_skb_load_bytes()로 헤더를 스택에 복사하면 이후 필드 접근이 캐시에서 처리됩니다

분류기별 디버깅 포인트

흔한 실수와 주의사항

• TCAM 엔트리 범위 확장: 포트 범위를 TCAM에 넣을 때 접두사로 분해하면 엔트리 수가 급증합니다. 0-1023 → 10개 접두사, 1024-65535 → 6개 접두사. 5-tuple에서 두 포트 필드 모두 범위를 사용하면 곱셈적 확장이 발생합니다
• 분류기 선택 시 고려사항:
  • 규칙 업데이트 빈도가 높으면 RFC/HiCuts보다 튜플 공간이나 선형 탐색이 적합합니다
  • 와이어 스피드가 필요하면 소프트웨어 분류기만으로는 한계가 있으므로 HW 오프로드를 검토합니다
  • cls_flower는 마스크 수가 많아지면 성능이 저하됩니다 — 가능하면 동일 마스크로 규칙을 통일합니다
  • cls_u32의 해시 divisor는 2의 거듭제곱으로 설정합니다. 소수를 사용하면 해시 분포가 나빠집니다
• 오프로드 실패 무시: TC flower 오프로드가 조용히 실패(silent fallback)할 수 있습니다. 반드시 tc -s filter show로 in_hw 플래그를 확인하고, skip_sw 플래그로 소프트웨어 폴백을 금지하면 오프로드 실패 시 명시적으로 에러가 발생합니다
• 규칙 순서 의존성: TC filter는 prio 값 순서로 평가되므로, 더 구체적인 규칙을 낮은 prio(높은 우선순위)로 설정해야 합니다. prio를 지정하지 않으면 자동 할당되어 의도치 않은 순서가 될 수 있습니다
• cls_flower vs cls_u32 선택:
  • cls_flower는 HW 오프로드를 지원하고 사용이 간단하지만, 마스크 수에 민감합니다
  • cls_u32는 세밀한 오프셋 제어가 가능하지만, 설정이 복잡하고 오프로드 지원이 제한적입니다
  • 새로운 환경에서는 cls_flower를 우선 고려하고, 세밀한 제어가 필요할 때만 cls_u32를 사용합니다
• BPF 맵 크기 산정: RFC-like BPF 맵 패턴에서 Phase 0 맵은 입력 공간 크기(예: 65,536)로, Phase 1 맵은 교차곱 상한(eqID_A × eqID_B)으로 설정합니다. 과대 산정은 메모리 낭비, 과소 산정은 룩업 실패를 유발합니다
• connmark와 flowid 혼동: connmark는 conntrack이 추적하는 연결별 마크(32비트, nf_conn.mark)이고, flowid는 TC qdisc 계층에서 패킷을 특정 클래스로 보내는 qdisc 식별자입니다. 두 개념을 혼동하여 tc filter ... action connmark 대신 action skbedit mark를 사용하거나, 반대로 connmark 저장·복원 없이 flowid만 설정하면 상태가 유지되지 않습니다:

  # 잘못된 예: connmark 복원 없이 TC 분류 — 재분류 패킷에서 마크 소실
  tc filter add dev eth0 ingress protocol ip prio 1 \
    flower ip_proto tcp dst_port 80 \
    action skbedit mark 0x10        # ← skb 마크만, conntrack 미저장
  
  # 올바른 예: connmark save/restore 패턴
  # 첫 패킷에서 connmark에 저장
  tc filter add dev eth0 ingress protocol ip prio 1 \
    flower ip_proto tcp dst_port 80 \
    action skbedit mark 0x10 \
    action connmark save  # ← nf_conn.mark = skb.mark
  # 이후 패킷에서 connmark 복원
  tc filter add dev eth0 ingress protocol ip prio 100 \
    flower \
    action connmark restore  # ← skb.mark = nf_conn.mark (O(1))

• 체인 순서 오류: TC filter와 nftables 모두 낮은 우선순위 번호가 먼저 평가됩니다. 일반 규칙(DROP all)을 구체적 허용 규칙보다 낮은 prio로 넣으면 허용 규칙이 절대 도달되지 않습니다:

  # 잘못된 예: DROP-all이 prio 1 → 모든 패킷이 DROP됨
  tc filter add dev eth0 ingress prio 1 matchall action drop
  tc filter add dev eth0 ingress prio 2 flower dst_port 80 action pass
  
  # 올바른 예: 허용 규칙이 항상 DROP-all보다 낮은 숫자
  tc filter add dev eth0 ingress prio 1 flower dst_port 80 action pass
  tc filter add dev eth0 ingress prio 100 matchall action drop

• VLAN 태그 처리: VLAN 태그가 있는 패킷에서 IP 헤더 오프셋이 달라집니다. cls_u32에서 IP 헤더 필드를 고정 오프셋으로 접근하면 VLAN 패킷에서 오동작합니다. cls_flower는 vlan_id, vlan_prio 매치 키를 제공하므로 훨씬 안전합니다:

  # u32: VLAN 패킷에서 IP SRC 매칭 시 오프셋 보정 필요
  # 비 VLAN: IP 헤더 @ ETH(14) → src @ +12 = offset 26
  # VLAN: IP 헤더 @ ETH(14)+VLAN(4) = 18 → src @ +12 = offset 30
  tc filter add dev eth0 ingress u32 \
    offset at 0 mask 0xffff0000 shift 16 eat  # EtherType 기반 오프셋
    match ip src 10.0.0.1/32 \
    action drop
  
  # flower: VLAN 인식 자동 처리
  tc filter add dev eth0 ingress flower \
    vlan_id 100 \
    ip_proto tcp \
    src_ip 10.0.0.1 \
    action drop

• GRO/GSO와 분류기 상호작용: GRO(Generic Receive Offload)는 수신 경로에서 여러 패킷을 하나로 병합합니다. TC ingress에서 GRO 패킷을 분류할 때 skb->len이 실제 MTU를 초과할 수 있으며, IP 헤더의 total length도 논리적 총합이 됩니다. BPF 프로그램에서 패킷 크기 기반 분류를 할 때 이를 고려해야 합니다:

  /* BPF: GRO 집계 패킷 크기 확인 시 주의 */
  SEC("tc")
  int classifier(struct __sk_buff *skb) {
      /* skb->len은 GRO 집계 시 여러 MTU의 합 가능 */
      /* 예: 64KB GRO 패킷 → 1500바이트 기준 분류 오류 */
      if (skb->len > 1500) {
          /* GRO 집계 패킷일 수 있음 — gso_size로 실제 세그먼트 크기 확인 */
          __u32 gso_size = skb->gso_size;  /* 개별 세그먼트 크기 */
          if (gso_size > 0 && gso_size <= 1500)
              return TC_ACT_OK;  /* 정상 GRO 집계 */
      }
      /* GSO 송신 경로: 분류 후 세그멘테이션 발생 */
      /* TC egress에서 대형 패킷 → GSO가 나중에 분할 */
      return TC_ACT_OK;
  }

실전 체크리스트

실전 사례 연구

이론적 알고리즘이 실제 환경에서 어떻게 적용되는지 세 가지 대표 사례를 살펴봅니다.

사례 1: 데이터센터 ACL (10K+ 규칙)

클라우드 데이터센터의 가상머신 네트워크 격리에는 수만 개의 보안 그룹 규칙이 사용됩니다. AWS, GCP, Azure 모두 이 문제를 다양한 방식으로 해결합니다.

문제 구조:

• 하이퍼바이저당 200~2000개 VM, VM당 평균 20~50개 방화벽 규칙
• 총 규칙 수: 수만~수십만 개
• 트래픽 패턴: 대부분 동-서(East-West) VM 간 트래픽
• 업데이트 빈도: 보안 그룹 변경 시 실시간 반영 필요

핵심 설계 결정:

• 마스크 통합: 보안 그룹 규칙을 동일 마스크(예: 정확 IP + 정확 포트) 그룹으로 통합하여 TSS 마스크 수를 최소화합니다. 마스크 수가 50개 이상이면 TSS 성능이 급격히 저하됩니다
• 연결 추적 활용: 새 연결의 첫 패킷에서만 전체 ACL을 평가하고, 이후 패킷은 conntrack에서 O(1)으로 처리합니다. TCP 세션의 경우 평균 수천 패킷 중 단 1개만 전체 분류 수행
• 규칙 컴파일: 사용자 정의 보안 그룹 규칙을 OpenFlow 규칙으로 오프라인 컴파일합니다. 충돌·중복·그림자 규칙을 사전 제거하여 TSS 규칙 수를 최소화

사례 2: 5G UPF 패킷 분류

5G 네트워크의 UPF(User Plane Function)는 모바일 가입자의 QoS(Quality of Service) 정책을 강제합니다. 3GPP TS 23.501에 따른 QFI(QoS Flow Identifier) 기반 분류가 핵심입니다.

5G QoS 분류 요구사항:

• 가입자당 최대 64개 QoS 플로우 (QFI 0~63)
• 플로우별 보장 비트레이트(GBR)와 최대 비트레이트(MBR) 시행
• 업링크 및 다운링크 SDF(Service Data Flow) 템플릿 매칭
• GTP-U 터널 헤더 + 내부 IP 헤더 2중 분류

/* 5G UPF BPF 분류기: GTP-U 파싱 + 내부 헤더 매칭 */

struct gtp_hdr {
    __u8  flags;
    __u8  msg_type;
    __be16 length;
    __be32 teid;       /* Tunnel Endpoint ID */
};

struct sdf_template {
    __be32 src_ip;
    __be32 src_mask;
    __be32 dst_ip;
    __be32 dst_mask;
    __be16 src_port_min;
    __be16 src_port_max;
    __be16 dst_port_min;
    __be16 dst_port_max;
    __u8   protocol;
    __u8   qfi;        /* 매칭 시 할당할 QFI */
    __u32  precedence; /* 우선순위 (낮을수록 우선) */
};

/* TEID → QoS 정책 맵 (다운링크) */
struct {
    __uint(type, BPF_MAP_TYPE_HASH);
    __uint(max_entries, 1 << 20);  /* 100만 가입자 */
    __type(key, __be32);            /* TEID */
    __type(value, struct sdf_template[64]); /* 가입자별 64개 SDF */
} teid_policy_map SEC(".maps");

/* 가입자별 토큰 버킷 (GBR 시행) */
struct token_bucket {
    __u64 tokens;
    __u64 last_ts;
    __u64 rate_bps;     /* 허용 비트레이트 */
    __u64 burst_bytes;  /* 최대 버스트 */
};

struct {
    __uint(type, BPF_MAP_TYPE_PERCPU_HASH);
    __uint(max_entries, 1 << 20);
    __type(key, __u64);             /* (TEID << 8) | QFI */
    __type(value, struct token_bucket);
} tbucket_map SEC(".maps");

SEC("xdp")
int upf_classify(struct xdp_md *ctx) {
    void *data     = (void *)(long)ctx->data;
    void *data_end = (void *)(long)ctx->data_end;

    /* 1. GTP-U 파싱 (UDP/2152) */
    struct ethhdr *eth = data;
    struct iphdr  *iph = data + sizeof(*eth);
    struct udphdr *udp = data + sizeof(*eth) + sizeof(*iph);
    struct gtp_hdr *gtp = data + sizeof(*eth) + sizeof(*iph) + sizeof(*udp);
    if ((void *)(gtp + 1) > data_end) return XDP_PASS;

    if (udp->dest != bpf_htons(2152)) return XDP_PASS;  /* GTP-U 포트 아님 */
    __be32 teid = gtp->teid;

    /* 2. TEID → SDF 템플릿 룩업 */
    struct sdf_template (*sdfs)[64] = bpf_map_lookup_elem(&teid_policy_map, &teid);
    if (!sdfs) return XDP_PASS;  /* 알 수 없는 TEID → 상위로 */

    /* 3. 내부 IP 헤더 파싱 */
    struct iphdr *inner_iph = (void *)(gtp + 1);
    if ((void *)(inner_iph + 1) > data_end) return XDP_DROP;

    /* 4. SDF 템플릿 순차 매칭 (우선순위 순) */
    __u8 matched_qfi = 9;  /* 기본 QFI (Best Effort) */
    for (int i = 0; i < 64; i++) {
        struct sdf_template *t = &(*sdfs)[i];
        if (!t->qfi) break;  /* 빈 슬롯 */
        if ((inner_iph->saddr & t->src_mask) != t->src_ip) continue;
        if ((inner_iph->daddr & t->dst_mask) != t->dst_ip) continue;
        if (inner_iph->protocol != t->protocol) continue;
        matched_qfi = t->qfi;
        break;
    }

    /* 5. 토큰 버킷 GBR 시행 */
    __u64 key = ((__u64)bpf_ntohl(teid) << 8) | matched_qfi;
    struct token_bucket *tb = bpf_map_lookup_elem(&tbucket_map, &key);
    if (tb) {
        __u64 now = bpf_ktime_get_ns();
        __u64 elapsed = now - tb->last_ts;
        tb->tokens += (elapsed * tb->rate_bps) / 8000000000ULL;
        if (tb->tokens > tb->burst_bytes) tb->tokens = tb->burst_bytes;
        tb->last_ts = now;
        if (tb->tokens < ctx->data_end - ctx->data)
            return XDP_DROP;  /* GBR 초과 → 폐기 */
        tb->tokens -= (ctx->data_end - ctx->data);
    }

    /* 6. QFI 메타데이터 저장 → 이후 qdisc에서 DSCP 마킹 */
    bpf_xdp_store_bytes(ctx, 0, &matched_qfi, sizeof(matched_qfi));  /* 단순화 */
    return XDP_PASS;
}

5G UPF 분류 최적화 포인트:

• TEID 기반 1차 분류: GTP-U TEID가 가입자를 직접 식별하므로 5-tuple 전체 매칭 전에 TEID로 정책을 먼저 가져옵니다. 이로써 전체 가입자 정책을 스캔하지 않아도 됩니다
• PERCPU 맵 활용: 토큰 버킷에 BPF_MAP_TYPE_PERCPU_HASH를 사용하면 CPU 간 잠금 경합 없이 GBR을 시행할 수 있습니다. 단, 각 CPU가 독립적으로 토큰을 소진하므로 허용 총합이 CPU 수 × 설정값이 됩니다 — 여러 큐에 걸친 GBR 시행 시 추가 조정 필요
• SDF 개수 제한: BPF 루프 횟수 제한(verifier)으로 64회 이상은 컴파일 실패합니다. 3GPP 스펙의 최대 SDF 수(64)와 일치하므로 문제없지만, 구현 시 반드시 루프 바운드를 명시해야 합니다

사례 3: DDoS 방어 시스템 — 동적 규칙 업데이트

DDoS 방어는 공격 패턴이 실시간으로 변하므로 규칙 업데이트 성능이 트래픽 처리 성능만큼 중요합니다. 분류기 선택 기준이 일반 ACL과 다릅니다.

DDoS 방어의 특수 요구사항:

• 공격 서명 추가: 초당 수백~수천 건의 규칙 추가·삭제
• 원자적 업데이트: 규칙 업데이트 중에도 패킷 처리 중단 불허
• 차단 규칙 만료: TTL 기반 자동 규칙 삭제 (공격 종료 후 차단 해제)
• 통계 수집: 차단된 패킷 수, 출발지별 트래픽 볼륨 실시간 추적

/* DDoS 방어: 공격 IP TTL 기반 자동 만료 */

struct block_entry {
    __u64 expire_ns;  /* 0이면 영구 차단 */
    __u32 reason;     /* 차단 사유 코드 */
};

struct {
    __uint(type, BPF_MAP_TYPE_LPM_TRIE);
    __uint(max_entries, 1 << 20);   /* 최대 100만 접두사 */
    __type(key, struct bpf_lpm_trie_key_u8[8]);  /* prefix_len + addr */
    __type(value, struct block_entry);
    __uint(map_flags, BPF_F_NO_PREALLOC);  /* 동적 할당 */
} blocklist SEC(".maps");

SEC("xdp")
int ddos_filter(struct xdp_md *ctx) {
    void *data     = (void *)(long)ctx->data;
    void *data_end = (void *)(long)ctx->data_end;

    struct ethhdr *eth = data;
    struct iphdr  *iph = data + sizeof(*eth);
    if ((void *)(iph + 1) > data_end) return XDP_PASS;

    /* LPM Trie 차단 목록 조회 */
    struct {
        __u32 prefix_len;
        __u8  addr[4];
    } key = { .prefix_len = 32, .addr = {} };
    __builtin_memcpy(key.addr, &iph->saddr, 4);

    struct block_entry *entry = bpf_map_lookup_elem(&blocklist, &key);
    if (entry) {
        /* TTL 확인 */
        if (entry->expire_ns == 0 ||
            bpf_ktime_get_ns() < entry->expire_ns) {
            /* 통계 갱신 (PERCPU → 잠금 불필요) */
            update_stats(iph->saddr, data_end - data);
            return XDP_DROP;
        }
        /* 만료된 항목 — 삭제 (BPF에서 직접 삭제 가능) */
        bpf_map_delete_elem(&blocklist, &key);
    }

    return XDP_PASS;
}

#!/usr/bin/python3
# 유저스페이스 DDoS 제어 평면: 공격 감지 → 규칙 추가/삭제

import bcc from BPF
import ctypes, time, struct

# 공격 감지: 초당 1000패킷 이상 출발지 IP를 차단
THRESHOLD_PPS = 1000
BLOCK_TTL_SECS = 300  # 5분 후 자동 해제

def block_ip(blocklist_map, src_ip, ttl_secs):
    expire_ns = time.time_ns() + ttl_secs * 10**9
    key = struct.pack("=I4s", 32, src_ip.to_bytes(4, 'big'))
    value = struct.pack("=QI", expire_ns, 0x01)  # reason=rate_exceeded
    blocklist_map[key] = value
    print(f"차단 추가: {src_ip} TTL={ttl_secs}s")

def cleanup_expired(blocklist_map):
    now_ns = time.time_ns()
    expired = []
    for key, val in blocklist_map.items():
        expire_ns = struct.unpack("=Q", val[:8])[0]
        if expire_ns != 0 and expire_ns < now_ns:
            expired.append(key)
    for k in expired:
        del blocklist_map[k]
    if expired:
        print(f"만료 제거: {len(expired)}개 엔트리")

# 1초마다 통계 확인 및 만료 정리
while True:
    time.sleep(1)
    stats = bpf["stats"]
    for src_ip, count in stats.items():
        total = sum(count)  # PERCPU 합산
        if total > THRESHOLD_PPS:
            block_ip(bpf["blocklist"], src_ip.value, BLOCK_TTL_SECS)
    cleanup_expired(bpf["blocklist"])
    stats.clear()

DDoS 방어 분류기 선택 기준 요약:

참고자료

• P. Gupta, N. McKeown, "Packet Classification on Multiple Fields," ACM SIGCOMM 1999 — RFC 알고리즘 원 논문
• P. Gupta, N. McKeown, "Algorithms for Packet Classification," IEEE Network, 2001 — RFC 및 패킷 분류 알고리즘 서베이
• P. Gupta, N. McKeown, "Packet Classification using Hierarchical Intelligent Cuttings," Hot Interconnects VII, 2000 — HiCuts 원 논문
• S. Singh et al., "Packet Classification Using Multidimensional Cutting," ACM SIGCOMM 2003 — HyperCuts 원 논문
• D. E. Taylor, "Survey and Taxonomy of Packet Classification Techniques," ACM Computing Surveys, 2005 — 종합 서베이
• V. Srinivasan et al., "Fast and Scalable Layer Four Switching," ACM SIGCOMM 1998 — 튜플 공간 탐색
• net/sched/cls_u32.c — 리눅스 커널 u32 분류기 소스
• net/sched/cls_flower.c — 리눅스 커널 flower 분류기 소스
• net/sched/cls_bpf.c — 리눅스 커널 BPF 분류기 소스
• 커널 공식 문서: TC Actions — TC 액션 환경 규칙 공식 문서입니다
• man tc-u32(8) — u32 분류기 매뉴얼 페이지입니다
• man tc-flower(8) — flower 분류기 매뉴얼 페이지입니다
• man tc-bpf(8) — BPF 분류기 매뉴얼 페이지입니다
• LWN: BPF comes to firewalls (2018) — BPF 기반 패킷 분류와 필터링에 대한 LWN 기사입니다
• 커널 공식 문서: BPF — eBPF 서브시스템 공식 문서입니다
• net/sched/cls_matchall.c — 리눅스 커널 matchall 분류기 소스입니다

관련 문서

이 주제와 관련된 다른 문서를 더 깊이 이해하고 싶다면 다음을 참고하세요.

• TC (Traffic Control) — qdisc, class, filter, u32/flower/BPF 분류기 실무 가이드
• BPF/XDP — eBPF 프로그래밍과 XDP 패킷 처리
• LC-Trie (FIB Trie) — 1차원 LPM을 위한 라우팅 트라이 구현
• eSwitch (Embedded Switch) — eSwitch 아키텍처와 TC flower offload
• SmartNIC/DPU — DPU 아키텍처와 하드웨어 분류 파이프라인
• 라우팅 — 커널 라우팅 테이블과 FIB 구조
• 네트워크 스택 — TCP/IP 프로토콜 스택 전체 구조
• 텍스트 검색 알고리즘 — 패턴 매칭 알고리즘 (Aho-Corasick, BM, KMP)