1"use strict";(self.webpackChunkkinvolk=self.webpackChunkkinvolk||[]).push([[3554],{71229:(e,t,n)=>{n.r(t),n.d(t,{assets:()=>l,contentTitle:()=>a,default:()=>d,frontMatter:()=>r,metadata:()=>o,toc:()=>h});var s=n(74848),i=n(28453);const r={authors:["mauricio-vasquez","alban-crequy","imran-pochi"],description:"Performance Benchmark Analysis of Egress Filtering on Linux",draft:!1,tags:["benchmark","filtering","egress","iptables","bpf","ebpf","ipsets","linux"],title:"Performance Benchmark Analysis of Egress Filtering on Linux",image:"./thomas-jensen-ISG-rUel0Uw-unsplash.jpg",slug:"2020/09/egress-filtering-testing"},a=void 0,o={permalink:"/blog/2020/09/egress-filtering-testing",source:"@site/blog/2020-09-10-egress-filtering-testing/index.md",title:"Performance Benchmark Analysis of Egress Filtering on Linux",description:"Performance Benchmark Analysis of Egress Filtering on Linux",date:"2020-09-10T00:00:00.000Z",tags:[{inline:!0,label:"benchmark",permalink:"/blog/tags/benchmark"},{inline:!0,label:"filtering",permalink:"/blog/tags/filtering"},{inline:!0,label:"egress",permalink:"/blog/tags/egress"},{inline:!0,label:"iptables",permalink:"/blog/tags/iptables"},{inline:!0,label:"bpf",permalink:"/blog/tags/bpf"},{inline:!0,label:"ebpf",permalink:"/blog/tags/ebpf"},{inline:!0,label:"ipsets",permalink:"/blog/tags/ipsets"},{inline:!0,label:"linux",permalink:"/blog/tags/linux"}],hasTruncateMarker:!1,authors:[{name:"Mauricio V\xe1squez Bernal",key:"mauricio-vasquez"},{name:"Alban Crequy",key:"alban-crequy"},{name:"Imran Pochi",key:"imran-pochi"}],frontMatter:{authors:["mauricio-vasquez","alban-crequy","imran-pochi"],description:"Performance Benchmark Analysis of Egress Filtering on Linux",draft:!1,tags:["benchmark","filtering","egress","iptables","bpf","ebpf","ipsets","linux"],title:"Performance Benchmark Analysis of Egress Filtering on Linux",image:"./thomas-jensen-ISG-rUel0Uw-unsplash.jpg",slug:"2020/09/egress-filtering-testing"},unlisted:!1,prevItem:{title:"Let's talk about the Business of Open Source",permalink:"/blog/2020/09/lets-talk-about-the-business-of-open-source"},nextItem:{title:"OpenTelemetry Python Implementation Deep Dive",permalink:"/blog/2020/06/opentelemetry-python-implementation-deep-dive"}},l={image:n(86313).A,authorsImageUrls:[void 0,void 0,void 0]},h=[{value:"Goals",id:"goals",level:2},{value:"Scenario",id:"scenario",level:2},{value:"Metrics",id:"metrics",level:2},{value:"Linux Filtering Mechanisms",id:"linux-filtering-mechanisms",level:2},{value:"eBPF",id:"ebpf",level:3},{value:"iptables",id:"iptables",level:3},{value:"IP Sets",id:"ip-sets",level:3},{value:"Benchmark Set-up",id:"benchmark-set-up",level:2},{value:"Reproducibility",id:"reproducibility",level:2},{value:"Results",id:"results",level:2},{value:"Test #1 - TCP Throughput",id:"test-1---tcp-throughput",level:3},{value:"Test #2 - UDP Throughput",id:"test-2---udp-throughput",level:3},{value:"Test #3 - CPU usage",id:"test-3---cpu-usage",level:3},{value:"Test #4 - Latency",id:"test-4---latency",level:3},{value:"Test #5 - Setup Time",id:"test-5---setup-time",level:3},{value:"Test #6 - Throughput with too Many Rules",id:"test-6---throughput-with-too-many-rules",level:3},{value:"Profiling the CPU usage",id:"profiling-the-cpu-usage",level:2},{value:"Iptables",id:"iptables-1",level:3},{value:"eBPF",id:"ebpf-1",level:3},{value:"IP Sets",id:"ip-sets-1",level:3},{value:"Conclusion",id:"conclusion",level:2},{value:"Notes",id:"notes",level:2}];function c(e){const t={a:"a",code:"code",h2:"h2",h3:"h3",li:"li",ol:"ol",p:"p",pre:"pre",section:"section",strong:"strong",sup:"sup",ul:"ul",...(0,i.R)(),...e.components};return(0,s.jsxs)(s.Fragment,{children:[(0,s.jsx)(t.p,{children:"Traffic filtering is a common technique used to protect networks and hosts from malicious activity. The\nfiltering can be done in the incoming and outgoing flows, better known as ingress and egress filtering. There\nare many examples of use cases for ingress filtering: mitigating DDoS attacks, avoiding SPAM, blocking access\nto services for specific geographic regions and so on."}),"\n",(0,s.jsxs)(t.p,{children:["One common application of egress filtering is to prevent applications and users from reaching remote hosts.\nThese kinds of filters are usually based on a large deny-list of IP address ranges, like ",(0,s.jsx)(t.a,{href:"https://www.icann.org/news/blog/reputation-block-lists-protecting-users-everywhere",children:"Reputation Block\nLists"}),". The technology\nused to perform this task has to be able to handle a high number of restricted hosts, up to millions in some\ncases."]}),"\n",(0,s.jsx)(t.p,{children:"Our friends at SAP asked us to perform a benchmark of the common Linux technologies available for this task.\nThis blog post presents the methodology and results from benchmarking some of the Linux filtering\ntechnologies: eBPF, IP sets and iptables."}),"\n",(0,s.jsxs)(t.p,{children:[(0,s.jsx)(t.strong,{children:"Update 2020-09-14:"})," we have received some great feedback and suggestions about other options to try,\nincluding eBPF JIT optimization (that we left inadvertently disabled) and inline eBPF map lookup. We will take\na look at this and update this post as soon as possible."]}),"\n",(0,s.jsxs)(t.p,{children:[(0,s.jsx)(t.strong,{children:"Update 2020-12-17:"})," acting on the valuable feedback received, the latest test results by the benchmark are\ndone with the eBPF JIT compiler enabled. The results showed a marked improvement by enabling eBPF JIT\ncompiler. Latest versions of Flatcar Container Linux Alpha channel now come with eBPF JIT compiler enabled by\ndefault."]}),"\n",(0,s.jsx)(t.h2,{id:"goals",children:"Goals"}),"\n",(0,s.jsx)(t.p,{children:"We had the following goals going into this study:"}),"\n",(0,s.jsxs)(t.ul,{children:["\n",(0,s.jsx)(t.li,{children:"Provide a reproducible benchmark framework that anyone else can download and use."}),"\n",(0,s.jsx)(t.li,{children:"Evaluate the different mechanisms in the Linux networking stack to filter out a large amount of IP addresses\nand assess their scalability when the amount of IP ranges to block reaches 1 million."}),"\n"]}),"\n",(0,s.jsx)(t.h2,{id:"scenario",children:"Scenario"}),"\n",(0,s.jsx)(t.p,{children:"We aim to understand the cost of performing egress filtering based on the destination IP in a large set of IP\nranges."}),"\n",(0,s.jsx)(t.p,{children:"The scenario we consider is composed of a client and a server computer that c
1ommunicate through an IP network.\nThe egress filtering is performed on the client machine and there is no filtering performed on the server\nside."}),"\n",(0,s.jsx)("figure",{class:"img-fluid",role:"presentation",children:(0,s.jsx)("img",{src:"./2020-09-10-egress-filtering-testing/scenario.svg",class:"img-fluid",alt:""})}),"\n",(0,s.jsx)(t.h2,{id:"metrics",children:"Metrics"}),"\n",(0,s.jsx)(t.p,{children:"An egress filter has to perform a matching operation to understand if a packet can continue its way or has to\nbe dropped. This operation could be costly if the number of blocked IPs is high. This kind of filter impacts\nthe throughput of IP connections, it consumes extra CPU and increases the latency. We decided to take into\nconsideration these metrics under the following conditions:"}),"\n",(0,s.jsxs)(t.ul,{children:["\n",(0,s.jsx)(t.li,{children:"Throughput"}),"\n",(0,s.jsx)(t.li,{children:"CPU usage"}),"\n",(0,s.jsx)(t.li,{children:"Latency"}),"\n"]}),"\n",(0,s.jsx)(t.h2,{id:"linux-filtering-mechanisms",children:"Linux Filtering Mechanisms"}),"\n",(0,s.jsx)(t.p,{children:"The Linux kernel provides different mechanisms to filter network packets. In this benchmark we considered the\nmost known ones. iptables is the historical and probably more known filtering utility in Linux. IP sets\nsupport high speed matching for sets of specific types, like IP ranges for instance. eBPF is very flexible and\ncustomizable. The following section provides more details of how we used those mechanisms in our benchmark."}),"\n",(0,s.jsx)(t.h3,{id:"ebpf",children:"eBPF"}),"\n",(0,s.jsx)(t.p,{children:"eBPF is a virtual machine built in the Linux kernel. In the networking scope, it allows the user to load\nprograms that are executed each time a packet arrives or is sent out of a networking interface. Those eBPF\nprograms can modify, redirect or drop the packets."}),"\n",(0,s.jsx)(t.p,{children:"There are different types of networking eBPF programs, CGROUP_SKB for per-cgroup filtering, SCHED_CLS and\nSCHED_ACT for filtering at the traffic control level, and XDP for filtering at the network interface level."}),"\n",(0,s.jsx)("figure",{class:"img-fluid",role:"presentation",children:(0,s.jsx)("img",{src:"./2020-09-10-egress-filtering-testing/ebpf.svg",class:"img-fluid",alt:""})}),"\n",(0,s.jsxs)(t.p,{children:["In our scenario, we want to apply the same filtering regardless of the cgroup of the application generating\nthe traffic. The traffic coming from non-local applications or forwarded traffic should be filtered as well.\nThis makes filtering at the socket level unfit for our scenario. XDP programs can only be attached to the\ningress",(0,s.jsx)(t.sup,{children:(0,s.jsx)(t.a,{href:"#user-content-fn-1-c04400",id:"user-content-fnref-1-c04400","data-footnote-ref":!0,"aria-describedby":"footnote-label",children:"1"})})," path, removing it from consideration in our tests also. By process of elimination, we only\nconsider eBPF programs attached to the traffic control layer."]}),"\n",(0,s.jsxs)(t.p,{children:["Given that we want to keep the tests as simple as possible we decided to implement ",(0,s.jsx)(t.a,{href:"https://github.com/kinvolk/egress-filtering-benchmark/blob/master/pkg/filters/tc-bpf/datapath/bpf.c",children:"our\nown"})," filtering\nprogram in eBPF that will be attached to the traffic control layer with a clsact qdisc. The clsact qdisc was\nintroduced in Linux 4.5, it\u2019s a pseudo qdisc that allows to attach eBPF programs in ingress and egress using\nthe ",(0,s.jsx)(t.a,{href:"https://qmonnet.github.io/whirl-offload/2020/04/11/tc-bpf-direct-action/",children:"direct-action"})," mode."]}),"\n",(0,s.jsxs)(t.p,{children:["Our filter implementation uses an ",(0,s.jsx)(t.a,{href:"https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=b95a5c4db09bc7c253636cb84dc9b12c577fd5a0",children:"LPM\nmap"}),"\nto save the list of IP addresses to block. eBPF implements the ",(0,s.jsx)(t.a,{href:"https://en.wikipedia.org/wiki/Longest_prefix_match",children:"LPM"})," algorithm with a ",(0,s.jsx)(t.a,{href:"https://en.wikipedia.org/wiki/Trie",children:"digital\ntree"}),"."]}),"\n",(0,s.jsx)("figure",{class:"img-fluid",role:"presentation",children:(0,s.jsx)("img",{src:"./2020-09-10-egress-filtering-testing/ebpflookup.svg",class:"img-fluid",alt:""})}),"\n",(0,s.jsx)(t.h3,{id:"iptables",children:"iptables"}),"\n",(0,s.jsx)(t.p,{children:"We tested the standard iptables implementation by adding DROP rules to the OUTPUT chain in the filter table.\nThe rules we used have the following format"}),"\n",(0,s.jsx)(t.p,{children:(0,s.jsx)(t.code,{children:'-A OUTPUT -d 192.168.0.0/16 -o eth0 -m comment --comment "benchmark" -j DROP'})}),"\n",(0,s.jsxs)(t.p,{children:["While implementing this filter we found that appending each rule independently was too slow and we had to use\nthe ",(0,s.jsx)(t.code,{children:"iptables-restore"})," utility to do it."]}),"\n",(0,s.jsx)(t.p,{children:"iptables uses a linear search algorithm for rule matching."}),"\n",(0,s.jsx)("figure",{class:"img-fluid",role:"presentation",children:(0,s.jsx)("img",{src:"./2020-09-10-egress-filtering-testing/iptableslookup.svg",class:"img-fluid",alt:""})}),"\n",(0,s.jsx)(t.h3,{id:"ip-sets",children:"IP Sets"}),"\n",(0,s.jsxs)(t.p,{children:["We also performed the testing with the ",(0,s.jsx)(t.a,{href:"https://ipset.netfilter.org/",children:"IP sets"})," framework. We used an IP set of\ntype ",(0,s.jsx)(t.a,{href:"https://ipset.netfilter.org/ipset.man.html#lbAZ",children:(0,s.jsx)(t.code,{children:"hash:net"})})," and linked it to iptables by using the\nfollowing rule:"]}),"\n",(0,s.jsxs)(t.p,{children:[(0,s.jsx)(t.code,{children:"-A OUTPUT -o eth0 -m set --match-set myset dst -m comment --comment benchmark -j DROP"}),"."]}),"\n",(0,s.jsxs)(t.p,{children:["The IP address to check is hashed and the result of the hash is used as the index in a hash table. Each bucket\nof the hash table contains an array of networks for that hash. When an IP address is checked against an IP set\nof type \u201chash",":net","\u201d, it is not known what network size will match. The IP set implementation hashes the IP\naddress for all possible network sizes. For instance, if the IP to match is 1.2.3.4, it looks for 1.2.3.4/32,\nfor 1.2.3.4/31 and s
1o on until all the 32 possible network sizes have been tested."]}),"\n",(0,s.jsx)("figure",{class:"img-fluid",role:"presentation",children:(0,s.jsx)("img",{src:"./2020-09-10-egress-filtering-testing/ipsetslookup.svg",class:"img-fluid",alt:""})}),"\n",(0,s.jsx)(t.h2,{id:"benchmark-set-up",children:"Benchmark Set-up"}),"\n",(0,s.jsxs)(t.p,{children:["We used ",(0,s.jsx)(t.code,{children:"iperf3"})," to measure the performance of TCP, UDP and the CPU usage. The standard ",(0,s.jsx)(t.code,{children:"ping"})," utility was\nused to measure the latency. We tested with 10, 100, 1k, 10k, 100k and 1M rules and each test was run 5 times\nto get statistical robustness."]}),"\n",(0,s.jsxs)(t.p,{children:["We used two bare metal servers - running on ",(0,s.jsx)(t.a,{href:"https://www.packet.com/",children:"Packet"})," - as client and server machines.\nThe specifications of such servers are:"]}),"\n",(0,s.jsx)(t.pre,{children:(0,s.jsx)(t.code,{children:"c2.medium.x86\n1x AMD EPYC 7401P 24-Core Processor @ 2.0GHz\n2x 120GB SSD\n2x 480GB SSD\n64GB RAM\n2x 10Gbps\n"})}),"\n",(0,s.jsx)(t.p,{children:"The exact versions of the tools we used are:"}),"\n",(0,s.jsxs)(t.ul,{children:["\n",(0,s.jsxs)(t.li,{children:[(0,s.jsx)(t.a,{href:"https://www.flatcar-linux.org/",children:"Flatcar Container Linux"})," by Kinvolk alpha\n(",(0,s.jsx)(t.a,{href:"https://www.flatcar-linux.org/releases/#release-2705.0.0",children:"2705.0.0"}),")"]}),"\n",(0,s.jsx)(t.li,{children:"Linux kernel 5.9.11"}),"\n",(0,s.jsx)(t.li,{children:"iperf 3.6 (in a Docker container with the host network)"}),"\n",(0,s.jsx)(t.li,{children:"iptables v1.6.2"}),"\n",(0,s.jsx)(t.li,{children:"ipset v7.6, protocol version: 7"}),"\n"]}),"\n",(0,s.jsx)(t.h2,{id:"reproducibility",children:"Reproducibility"}),"\n",(0,s.jsxs)(t.p,{children:[(0,s.jsx)(t.a,{href:"https://github.com/kinvolk/k8s-egress-filtering-benchmark",children:"https://github.com/kinvolk/egress-filtering-benchmark"}),"\nhas all the tools and instructions to reproduce these tests."]}),"\n",(0,s.jsx)(t.h2,{id:"results",children:"Results"}),"\n",(0,s.jsx)(t.h3,{id:"test-1---tcp-throughput",children:"Test #1 - TCP Throughput"}),"\n",(0,s.jsx)("figure",{class:"img-fluid",children:(0,s.jsx)("img",{src:"./2020-09-10-egress-filtering-testing/bpf-jit-enabled/throughput-tcp-linerate.svg",class:"img-fluid",alt:"Graph for test #1"})}),"\n",(0,s.jsx)(t.p,{children:"The throughput graph shows that the test is reaching line rate, 10Gbps because we are using a single\nconnection hence only one of the interfaces on the bonding is used in most of the cases. Only iptables with\nmore than 10k rules is not able to handle that performance. From this test we can conclude that iptables\ndoesn\u2019t scale well after 100k, but unfortunately we cannot conclude anything from other tests as network\nperformance is the bottleneck."}),"\n",(0,s.jsx)(t.p,{children:"In order to stress the CPU more, we performed another test using UDP."}),"\n",(0,s.jsx)(t.h3,{id:"test-2---udp-throughput",children:"Test #2 - UDP Throughput"}),"\n",(0,s.jsx)("figure",{class:"img-fluid",children:(0,s.jsx)("img",{src:"./2020-09-10-egress-filtering-testing/bpf-jit-enabled/throughput-udp.svg",class:"img-fluid",alt:"Graph for test #2"})}),"\n",(0,s.jsxs)(t.p,{children:["The goal of this test is to saturate the CPU. We used UDP packets with a size of 1470 bytes and the ",(0,s.jsx)(t.code,{children:" -b 10G"}),"\nparameter to try to reach line rate. The graph shows that none of the cases reaches the 10Gbps line rate, it\u2019s\ngood for this test because it means the network is not the bottleneck anymore."]}),"\n",(0,s.jsx)(t.p,{children:"We can see that iptables does not scale well beyond 1k rules and that IP sets give a slightly higher\nthroughput than eBPF on the clsact qdisc for high number of rules."}),"\n",(0,s.jsx)(t.h3,{id:"test-3---cpu-usage",children:"Test #3 - CPU usage"}),"\n",(0,s.jsx)("figure",{class:"img-fluid",children:(0,s.jsx)("img",{src:"./2020-09-10-egress-filtering-testing/bpf-jit-enabled/cpu.svg",class:"img-fluid",alt:"Graph for test #3"})}),"\n",(0,s.jsxs)(t.p,{children:["We used ",(0,s.jsx)(t.code,{children:"iperf"})," with a target bandwidth of 1Gbps (",(0,s.jsx)(t.code,{children:"-b 1G"}),") to avoid saturating the CPU and be able to compare\nthe CPU usage with the different filters. We take the CPU usage reported by ",(0,s.jsx)(t.code,{children:"iperf"})," that includes all the\napplications running on the host. From the above graph we can see that the CPU usage with iptables increases\nwhen using more than 1k rules. The CPU usage with eBPF and IP sets filters stays just about equal and almost\nconstant despite the increasing number of rules."]}),"\n",(0,s.jsx)(t.h3,{id:"test-4---latency",children:"Test #4 - Latency"}),"\n",(0,s.jsx)("figure",{class:"img-fluid",children:(0,s.jsx)("img",{src:"./2020-09-10-egress-filtering-testing/bpf-jit-enabled/latency.svg",class:"img-fluid",alt:"Graph for test #4"})}),"\n",(0,s.jsxs)(t.p,{children:["We used the standard Linux ping utility to measure the latency with the ",(0,s.jsx)(t.code,{children:"-i 0.001"})," and ",(0,s.jsx)(t.code,{children:"-c 1000"})," parameters,\nsending 1000 pings at a 1 millisecond interval. The above graph shows that the latency is not affected by the\nnumber of rules in the eBPF and IP sets filters, it\u2019s ~27\xb5s in those cases. On the other hand, it increases\nlinearly with the number of rules for the iptables case."]}),"\n",(0,s.jsx)(t.h3,{id:"test-5---setup-time",children:"Test #5 - Setup Time"}),"\n",(0,s.jsx)(t.p,{children:"This test aims to measure the time it takes to install the filtering rules on the system. It doesn\u2019t take into\nconsideration fixed times like loading the eBPF program, creating the IP set
1s but instead focuses on measuring\nthe time it takes to update the rules themselves and how it changes with the number of rules."}),"\n",(0,s.jsx)("figure",{class:"img-fluid",children:(0,s.jsx)("img",{src:"./2020-09-10-egress-filtering-testing/bpf-jit-enabled/setup.svg",class:"img-fluid",alt:"Graph for test #5"})}),"\n",(0,s.jsx)(t.p,{children:"The above graph shows that the time required to set up the rules in all the filters increases linearly with\nthe number of rules."}),"\n",(0,s.jsx)(t.p,{children:"With 100.000 IPs, the setup time is still less than one second. For 1 million IPs, the setup time is less than\n10 seconds. This shows that in practice, all 3 methods have an acceptable setup time."}),"\n",(0,s.jsx)(t.p,{children:"The setup time is very dependent on the benchmark implementation rather than being inherent to the filtering\nmethod. Each filtering method could be optimised in the benchmark code if it were deemed necessary."}),"\n",(0,s.jsxs)(t.ul,{children:["\n",(0,s.jsxs)(t.li,{children:["\n",(0,s.jsxs)(t.p,{children:["For the bpf filter: the benchmark performs one bpf() system call for every IP. From Linux 5.6, it is\npossible to ",(0,s.jsx)(t.a,{href:"https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=aa2e93b8e58e18442edfb2427446732415bc215e",children:"perform several updates in a eBPF map with a single bpf()\ncall"}),"."]}),"\n"]}),"\n",(0,s.jsxs)(t.li,{children:["\n",(0,s.jsxs)(t.p,{children:["For the iptables and IP sets filters, the benchmark executes external commands and feeds each IP range\nindividually over a pipe. We could avoid that by communicating the list to the kernel using the Netlink\nprotocol directly. There are ",(0,s.jsx)(t.a,{href:"https://github.com/vishvananda/netlink/search?q=ipset&type=Issues",children:"some\nattempts"})," to implement IP Sets support in\nGolang with the vishvananda/netlink library."]}),"\n"]}),"\n"]}),"\n",(0,s.jsx)(t.p,{children:"For this reason, the reader should be cautious before comparing the setup time of one filter to another. This\nshould not be interpreted as one method being better than another but rather to show expected setup\nperformance and that setup time is unlikely to be a problem for any filtering method."}),"\n",(0,s.jsx)(t.h3,{id:"test-6---throughput-with-too-many-rules",children:"Test #6 - Throughput with too Many Rules"}),"\n",(0,s.jsx)(t.p,{children:"The throughput in the tests one and two is almost the same regardless of the number of rules for the eBPF and\nIP Sets filters. We wanted to know if this behaviour changed with a higher number rules, i.e., up to 100\nmillions."}),"\n",(0,s.jsxs)(t.p,{children:["We found that it\u2019s not possible to run a test with 100M entries in the eBPF case as this would require more\nthan 4GB of memory for the LPM map and ",(0,s.jsx)(t.a,{href:"https://github.com/torvalds/linux/blob/v5.4/kernel/bpf/syscall.c#L209",children:"it\u2019s not allowed\nby"})," the Linux kernel",(0,s.jsx)(t.sup,{children:(0,s.jsx)(t.a,{href:"#user-content-fn-2-c04400",id:"user-content-fnref-2-c04400","data-footnote-ref":!0,"aria-describedby":"footnote-label",children:"2"})}),". We decided to\ntest with 10M and 50M rules."]}),"\n",(0,s.jsx)("figure",{class:"img-fluid",children:(0,s.jsx)("img",{src:"./2020-09-10-egress-filtering-testing/bpf-jit-enabled/many-rules-throughput.svg",class:"img-fluid",alt:"Chart for test #6"})}),"\n",(0,s.jsx)(t.p,{children:"From the above chart we can see that the difference in throughput between IP sets and eBPF is almost\nnegligible even with 10M and 50M rules."}),"\n",(0,s.jsx)(t.h2,{id:"profiling-the-cpu-usage",children:"Profiling the CPU usage"}),"\n",(0,s.jsx)(t.p,{children:"If you want to understand more about each implementation and read the relevant source code, a good way to get\nstarted is to profile the CPU usage to find out which functions take most of the CPU time."}),"\n",(0,s.jsxs)(t.p,{children:["In the UDP tests, the CPU is saturated and is not able to reach the 10Gbps line rate. We can use the BCC\n",(0,s.jsx)(t.a,{href:"https://github.com/iovisor/bcc/blob/master/tools/profile_example.txt",children:"profile"}
1)," tool to get the list of\nfunctions that are executed in the tests for each filtering method."]}),"\n",(0,s.jsxs)(t.p,{children:["We have to run the tool with the ",(0,s.jsx)(t.code,{children:"-K"})," parameter to get the traces from the kernel."]}),"\n",(0,s.jsx)(t.pre,{children:(0,s.jsx)(t.code,{children:"sudo /usr/share/bcc/tools/profile -K\n"})}),"\n",(0,s.jsx)(t.h3,{id:"iptables-1",children:"Iptables"}),"\n",(0,s.jsx)(t.p,{children:"For the iptables case, it prints the following trace:"}),"\n",(0,s.jsx)(t.pre,{children:(0,s.jsx)(t.code,{children:"ipt_do_table\nipt_do_table\nnf_hook_slow\n__ip_local_out\nip_local_out\n__ip_queue_xmit\n__tcp_transmit_skb\n"})}),"\n",(0,s.jsxs)(t.p,{children:["The order of calls is from the bottom to the top, we can see how the\n",(0,s.jsx)(t.a,{href:"https://github.com/torvalds/linux/blob/v5.4/net/netfilter/core.c#L505",children:"nf_hook_slow"})," function calls\n",(0,s.jsx)(t.a,{href:"https://github.com/torvalds/linux/blob/v5.4/net/ipv4/netfilter/ip_tables.c#L225",children:"ipt_do_table"})," in an\niterative manner. It is a simple \u201cfor\u201d loop that iterates over each rule, explaining the performance\ndecreasing linearly with the amount of rules."]}),"\n",(0,s.jsx)(t.h3,{id:"ebpf-1",children:"eBPF"}),"\n",(0,s.jsx)(t.p,{children:"We got the following trace for the eBPF case:"}),"\n",(0,s.jsx)(t.pre,{children:(0,s.jsx)(t.code,{children:"longest_prefix_match.isra.0\nlongest_prefix_match.isra.0\ntrie_lookup_elem\ncleanup_module\ncleanup_module\ntcf_classify\n__dev_queue_xmit\nip_finish_output2\nip_output\n"})}),"\n",(0,s.jsxs)(t.p,{children:["In this case the first important call is to\n",(0,s.jsx)(t.a,{href:"https://github.com/torvalds/linux/blob/v5.4/net/sched/cls_api.c#L1569",children:"tcf_classify"})," and the lookup in the\nLPM is performed in ",(0,s.jsx)(t.a,{href:"https://github.com/torvalds/linux/blob/v5.4/kernel/bpf/lpm_trie.c#L227",children:"trie_lookup_elem"}),"\nand ",(0,s.jsx)(t.a,{href:"https://github.com/torvalds/linux/blob/v5.4/kernel/bpf/lpm_trie.c#L164",children:"longest_prefix_match"}),". It is\nwalking the ",(0,s.jsx)(t.a,{href:"https://en.wikipedia.org/wiki/Trie",children:"trie"}),". This explains the better performance, since walking\nover the trie takes maximum 32 steps with IPv4 addresses."]}),"\n",(0,s.jsxs)(t.p,{children:["Without eBPF JIT enabled we would have expected to see ",(0,s.jsx)(t.code,{children:"__bpf_prog_run"})," and ",(0,s.jsx)(t.code,{children:"__bpf_prog_run32"})," just before the\n",(0,s.jsx)(t.code,{children:"trie_lookup_elem"}),". These calls interpret the eBPF program instructions and convert into eBPF bytecode. The\nnon-presence of these calls shows that eBPF JIT compiler is in effect."]}),"\n",(0,s.jsx)(t.h3,{id:"ip-sets-1",children:"IP Sets"}),"\n",(0,s.jsx)(t.p,{children:"The traces for IP sets are the following:"}),"\n",(0,s.jsx)(t.pre,{children:(0,s.jsx)(t.code,{children:"hash_net4_test\nhash_net4_test\nhash_net4_kadt\nip_set_test\nset_match_v4\nipt_do_table\niptable_filter_hook\nnf_hook_slow\n__ip_local_out\nip_local_out\nip_send_sk\nudp_send_skb.isra.0\nudp_sendmsg\n"})}
1),"\n",(0,s.jsxs)(t.p,{children:["For the IP sets case we can see how the first part of the stack is the same as iptables, nf_hook_slow ->\niptable_filter_hook-> ipt_do_table. Then\n",(0,s.jsx)(t.a,{href:"https://github.com/torvalds/linux/blob/v5.4/net/netfilter/xt_set.c#L189",children:"set_match_v4"})," and after it specific\nIP set logic is executed:\n",(0,s.jsx)(t.a,{href:"https://github.com/torvalds/linux/blob/v5.4/net/netfilter/ipset/ip_set_core.c#L561",children:"ip_set_test"}),",\n",(0,s.jsx)(t.a,{href:"https://github.com/torvalds/linux/blob/v5.4/net/netfilter/ipset/ip_set_hash_net.c#L112",children:"hash_net4_kadt"})," and\n",(0,s.jsx)(t.a,{href:"https://github.com/torvalds/linux/blob/v5.4/net/netfilter/ipset/ip_set_hash_gen.h#L983",children:"hash_net4_test"}),", that\nlookups all possible network sizes for a given IP."]}),"\n",(0,s.jsx)(t.h2,{id:"conclusion",children:"Conclusion"}),"\n",(0,s.jsx)(t.p,{children:"The throughput, CPU usage and latency tests show that IP sets and eBPF filters scale well even with 1 million\nIPs. On the other hand, iptables doesn\u2019t scale that well and even with a low number of rules like 1k or 10k\nshows a considerable difference to the other filters. This is expected as iptables performs a linear search on\nthe rule list."}),"\n",(0,s.jsxs)(t.p,{children:["IP sets fared marginally better than eBPF with an LPM map on a clsact qdisc, it has a slightly higher\nthroughput in the UDP test and uses less CPU. We suspect this is because the random CIDR's generated in the\nbenchmark test were with the subnet mask ",(0,s.jsx)(t.code,{children:"/24"})," and ",(0,s.jsx)(t.code,{children:"/16"}),", this resulted in faster lookups on the hash table.\nThe lookup time grows linearly with the number of different prefix values added to the set. Hence we cannot\ncompare the performance between IP sets and eBPF in the general case at this point."]}),"\n",(0,s.jsx)(t.p,{children:"After enabling the eBPF JIT compiler, eBPF managed to bridge the performance gap versus IP sets, being more\nnoticable in nearly equal CPU usage and throughput when the number of rules reached upto 50M."}),"\n",(0,s.jsx)(t.p,{children:"eBPF cannot handle more than ~89M entries due to restrictions in the Linux kernel."}),"\n",(0,s.jsx)(t.p,{children:"We suggest the decision of what tool to use shouldn\u2019t be strictly based on the results of this benchmark but\nshould take into consideration other aspects like whether the technology is already used on the hosts, whether\nthere are other needed features (now or in the future) that could be provided by some of the technologies, the\nway traffic statistics can be exposed to a monitoring tool, etc."}),"\n",(0,s.jsx)(t.p,{children:"Keep in mind that this benchmark only tests a specific use case: filtering a large deny-list of IP address\nranges on egress. A more realistic cluster would have other filters, including on ingress."}),"\n",(0,s.jsx)(t.h2,{id:"notes",children:"Notes"}),"\n","\n",(0,s.jsxs)(t.section,{"data-footnotes":!0,className:"footnotes",children:[(0,s.jsx)(t.h2,{className:"sr-only",id:"footnote-label",children:"Footnotes"}),"\n",(0,s.jsxs)(t.ol,{children:["\n",(0,s.jsxs)(t.li,{id:"user-content-fn-1-c04400",children:["\n",(0,s.jsxs)(t.p,{children:["There are some proposals to ",(0,s.jsx)(t.a,{href:"https://lwn.net/Articles/813406/",children:"add support"})," for the egress path but they\naren\u2019t merged at the time of writing. ",(0,s.jsx)(t.a,{href:"#user-content-fnref-1-c04400","data-footnote-backref":"","aria-label":"Back to reference 1",className:"data-footnote-backref",children:"\u21a9"})]}),"\n"]}),"\n",(0,s.jsxs)(t.li,{id:"user-content-fn-2-c04400",children:["\n",(0,s.jsxs)(t.p,{children:["Each element on the LPM map\n",(0,s.jsx)(t.a,{href:"https://github.com/torvalds/linux/blob/v5.4/kernel/bpf/lpm_trie.c#L570",children:"requires"})," 48 bytes in our case\n(40 from ",(0,s.jsx)(t.code,{children:"sizeof(struct lpm_trie_node)"})," + 4 from ",(0,s.jsx)(t.code,{children:"attr->value_size"})," and 4 from ",(0,s.jsx)(t.code,{children:"trie->data_size"}),"). It\nmeans the maximum number of possible elements in the map is (2^32/48) ~89M. ",(0,s.jsx)(t.a,{href:"#user-content-fnref-2-c04400","data-footnote-backref":"","aria-label":"Back to reference 2",className:"data-footnote-backref",children:"\u21a9"})]}),"\n"]}),"\n"]}),"\n"]})]})}function d(e={}){const{wrapper:t}={...(0,i.R)(),...e.components};return t?(0,s.jsx)(t,{...e,children:(0,s.jsx)(c,{...e})}):c(e)}},86313:(e,t,n)=>{n.d(t,{A:()=>s});const s=n.p+"assets/images/thomas-jensen-ISG-rUel0Uw-unsplash-bf27ebd5412b9e74d566ffb93fdbf91c.jpg"},28453:(e,t,n)=>{n.d(t,{R:()=>a,x:()=>o});var s=n(96540);const i={},r=s.createContext(i);function a(e){const t=s.useContext(r);return s.useMemo((function(){return"function"==typeof e?e(t):{...t,...e}}),[t,e])}function o(e){let t;return t=e.disableParentContext?"function"==typeof e.components?e.components(i):e.components||i:a(e.components),s.createElement(r.Provider,{value:t},e.children)}}}]);
Line numbers count LF bytes from the start of the resource, as the search results do. Vendor segments are library code the classifier recognised; they are stored but not indexed. Bytes are shown as Latin1 characters, one per byte.