Expiring flows in an XDP based router

Expiring flows in an XDP based router

[Edvard Fagerholm]

Hi,

I'm working on an in-house router and I'm looking for some advice on
whether to try to implement some functionality directly in an XDP
program or instead use AF_XDP sockets with the additional flexibility
provided by userspace.

We basically have a flow table, which contains entries of the form:

  (source ip, source port) -> (action, timestamp)

Every time we see a packet belonging to a flow, the timestamp is
updated and if the flow has been inactive for e.g. 10 seconds, the
flow is considered inactive and should be deleted. Actions are of the
form:

  "forward packet to a.b.c.d port X using source port Y"

The challenge that I have is how to clean up expired flows. Built-in
options would be BPF_MAP_TYPE_LRU_PERCPU_HASH. However, dropping an
active flow would be unacceptable.

I'm looking at at most 10k new flow entries being added per second per
router with a maximum number of concurrent flows at around 256k. Each
flow sends a packet at least every 5 seconds, but most every 50ms.
Does this allow me to tune the table size in such a way that no active
flows can be evicted? If not, are there any other reasonable
approaches for cleaning up the flows?

Our current system uses packet headers and is fully stateless, but
adds 16 bytes to every packet.

Best,
Edvard

Re: Expiring flows in an XDP based router

[Toke Høiland-Jørgensen]

Edvard Fagerholm <edvard.fagerholm@gmail.com> writes:

> Hi,
>
> I'm working on an in-house router and I'm looking for some advice on
> whether to try to implement some functionality directly in an XDP
> program or instead use AF_XDP sockets with the additional flexibility
> provided by userspace.
>
> We basically have a flow table, which contains entries of the form:
>
>   (source ip, source port) -> (action, timestamp)
>
> Every time we see a packet belonging to a flow, the timestamp is
> updated and if the flow has been inactive for e.g. 10 seconds, the
> flow is considered inactive and should be deleted. Actions are of the
> form:
>
>   "forward packet to a.b.c.d port X using source port Y"
>
> The challenge that I have is how to clean up expired flows. Built-in
> options would be BPF_MAP_TYPE_LRU_PERCPU_HASH. However, dropping an
> active flow would be unacceptable.
>
> I'm looking at at most 10k new flow entries being added per second per
> router with a maximum number of concurrent flows at around 256k. Each
> flow sends a packet at least every 5 seconds, but most every 50ms.
> Does this allow me to tune the table size in such a way that no active
> flows can be evicted? If not, are there any other reasonable
> approaches for cleaning up the flows?

Well, hard to tell with only the number of additions. I mean, 256.000 +
10.000 * 10 seconds means you'd need on the order of 356k entries in the
map, assuming flows expire at the same rate as they are added. Do you
assume any such guarantee?

Alternatively, you could have your XDP program start a BPF timer and
perform the periodic cleanup from that. There will be some overhead from
walking the map, and a potential for racy behaviour if the same flow is
expired and re-added frequently, but otherwise this should be quite
doable.

In any case, you'd need to size your map so that it doesn't fill up
before flows expire. So whether to use an LRU map is a case of whether
overflowing the map will result in overwriting existing entries, or
blocking the addition of new ones.

-Toke

Re: Expiring flows in an XDP based router

[Edvard Fagerholm]

On Sun, May 18, 2025 at 7:19 PM Toke Høiland-Jørgensen <toke@redhat.com> wrote:
>
> Edvard Fagerholm <edvard.fagerholm@gmail.com> writes:
>
> > Hi,
> >
> > I'm working on an in-house router and I'm looking for some advice on
> > whether to try to implement some functionality directly in an XDP
> > program or instead use AF_XDP sockets with the additional flexibility
> > provided by userspace.
> >
> > We basically have a flow table, which contains entries of the form:
> >
> >   (source ip, source port) -> (action, timestamp)
> >
> > Every time we see a packet belonging to a flow, the timestamp is
> > updated and if the flow has been inactive for e.g. 10 seconds, the
> > flow is considered inactive and should be deleted. Actions are of the
> > form:
> >
> >   "forward packet to a.b.c.d port X using source port Y"
> >
> > The challenge that I have is how to clean up expired flows. Built-in
> > options would be BPF_MAP_TYPE_LRU_PERCPU_HASH. However, dropping an
> > active flow would be unacceptable.
> >
> > I'm looking at at most 10k new flow entries being added per second per
> > router with a maximum number of concurrent flows at around 256k. Each
> > flow sends a packet at least every 5 seconds, but most every 50ms.
> > Does this allow me to tune the table size in such a way that no active
> > flows can be evicted? If not, are there any other reasonable
> > approaches for cleaning up the flows?
>
> Well, hard to tell with only the number of additions. I mean, 256.000 +
> 10.000 * 10 seconds means you'd need on the order of 356k entries in the
> map, assuming flows expire at the same rate as they are added. Do you
> assume any such guarantee?

We have average session lengths over 30 seconds and a maximum of 256k
concurrents the way the servers are set up. The first number is a
conservative lower
bound and the latter a conservative upper bound, so from there you get 10k per
second as a conservative upper bound too. We see spikes sometimes during
updates with polling clients, but they stay below this too.

I read the description of the LRU implementation in the Cilium docs. For an
element to be expired, it would need to be put at the head of the active list
and propagate all the way down towards the tail until being moved over to
the head of the inactive list. Then propagate down the inactive list
and be cleaned
up.

If one could prove that being propagated in the lists to being cleaned
up takes longer
than the maximum interval every flow sees packets, then that's good enough.
Alternatively, if the table is always larger than the maximum number of flows by
some constant factor and one can prove some invariant that the kernel always
recycles enough "real" inactive flows before accidentally recycling an
active flow,
then that would also be enough.

However, I don't think I'm quite comfortable with such an approach,
since it relies
on implementation details of the data structure that are not part of
the promised API.

On the other hand, given the number of routers and load balancers using XDP,
I was kinda hoping there was some well-known robust solution that is also
performant.

The box in question is basically doing DDoS protection, so it needs to
be able to
handle traffic at line rate. I'm also trying to avoid doing any
expensive processing
that takes a long time, which could cause NIC buffers to fill up and
cause packet
loss. Our current header based solution spends a constant amount of time per
packet and is stateless.

> Alternatively, you could have your XDP program start a BPF timer and
> perform the periodic cleanup from that. There will be some overhead from
> walking the map, and a potential for racy behaviour if the same flow is
> expired and re-added frequently, but otherwise this should be quite
> doable.

I would need to look into timers. Never had to deal with these before in XDP.

> In any case, you'd need to size your map so that it doesn't fill up
> before flows expire. So whether to use an LRU map is a case of whether
> overflowing the map will result in overwriting existing entries, or
> blocking the addition of new ones.

We basically need both:

1. Table should be large enough to never block connections.
2. The error of the approximate LRU algorithm needs to be precise
enough to never recycle active flows.

Best,
Edvard

Re: Expiring flows in an XDP based router

[Toke Høiland-Jørgensen]

Edvard Fagerholm <edvard.fagerholm@gmail.com> writes:

> On Sun, May 18, 2025 at 7:19 PM Toke Høiland-Jørgensen <toke@redhat.com> wrote:
>>
>> Edvard Fagerholm <edvard.fagerholm@gmail.com> writes:
>>
>> > Hi,
>> >
>> > I'm working on an in-house router and I'm looking for some advice on
>> > whether to try to implement some functionality directly in an XDP
>> > program or instead use AF_XDP sockets with the additional flexibility
>> > provided by userspace.
>> >
>> > We basically have a flow table, which contains entries of the form:
>> >
>> >   (source ip, source port) -> (action, timestamp)
>> >
>> > Every time we see a packet belonging to a flow, the timestamp is
>> > updated and if the flow has been inactive for e.g. 10 seconds, the
>> > flow is considered inactive and should be deleted. Actions are of the
>> > form:
>> >
>> >   "forward packet to a.b.c.d port X using source port Y"
>> >
>> > The challenge that I have is how to clean up expired flows. Built-in
>> > options would be BPF_MAP_TYPE_LRU_PERCPU_HASH. However, dropping an
>> > active flow would be unacceptable.
>> >
>> > I'm looking at at most 10k new flow entries being added per second per
>> > router with a maximum number of concurrent flows at around 256k. Each
>> > flow sends a packet at least every 5 seconds, but most every 50ms.
>> > Does this allow me to tune the table size in such a way that no active
>> > flows can be evicted? If not, are there any other reasonable
>> > approaches for cleaning up the flows?
>>
>> Well, hard to tell with only the number of additions. I mean, 256.000 +
>> 10.000 * 10 seconds means you'd need on the order of 356k entries in the
>> map, assuming flows expire at the same rate as they are added. Do you
>> assume any such guarantee?
>
> We have average session lengths over 30 seconds and a maximum of 256k
> concurrents the way the servers are set up. The first number is a
> conservative lower
> bound and the latter a conservative upper bound, so from there you get 10k per
> second as a conservative upper bound too. We see spikes sometimes during
> updates with polling clients, but they stay below this too.
>
> I read the description of the LRU implementation in the Cilium docs. For an
> element to be expired, it would need to be put at the head of the active list
> and propagate all the way down towards the tail until being moved over to
> the head of the inactive list. Then propagate down the inactive list
> and be cleaned
> up.
>
> If one could prove that being propagated in the lists to being cleaned
> up takes longer
> than the maximum interval every flow sees packets, then that's good enough.
> Alternatively, if the table is always larger than the maximum number of flows by
> some constant factor and one can prove some invariant that the kernel always
> recycles enough "real" inactive flows before accidentally recycling an
> active flow,
> then that would also be enough.
>
> However, I don't think I'm quite comfortable with such an approach,
> since it relies
> on implementation details of the data structure that are not part of
> the promised API.
>
> On the other hand, given the number of routers and load balancers using XDP,
> I was kinda hoping there was some well-known robust solution that is also
> performant.
>
> The box in question is basically doing DDoS protection, so it needs to
> be able to
> handle traffic at line rate. I'm also trying to avoid doing any
> expensive processing
> that takes a long time, which could cause NIC buffers to fill up and
> cause packet
> loss. Our current header based solution spends a constant amount of time per
> packet and is stateless.
>
>> Alternatively, you could have your XDP program start a BPF timer and
>> perform the periodic cleanup from that. There will be some overhead from
>> walking the map, and a potential for racy behaviour if the same flow is
>> expired and re-added frequently, but otherwise this should be quite
>> doable.
>
> I would need to look into timers. Never had to deal with these before in XDP.
>
>> In any case, you'd need to size your map so that it doesn't fill up
>> before flows expire. So whether to use an LRU map is a case of whether
>> overflowing the map will result in overwriting existing entries, or
>> blocking the addition of new ones.
>
> We basically need both:
>
> 1. Table should be large enough to never block connections.
> 2. The error of the approximate LRU algorithm needs to be precise
> enough to never recycle active flows.

Right, I am not sure if such guarantees can be made given the current
implementation. Analysing the kernel source code would be the only way
to be sure of this (for the LRU side). If you do end up making such an
analysis, please share your results.

I also seem to recall that at some point there was some discussion about
making the LRU eviction policy configurable (by delegating it to a BPF
program, basically). Patches never materialised, but if this is a
compelling use case for you, actually implementing this could be a way
forward as well.

-Toke

Re: Expiring flows in an XDP based router

[Vadim Goncharov]

On Sun, 18 May 2025 20:11:13 +0300
Edvard Fagerholm <edvard.fagerholm@gmail.com> wrote:

> On Sun, May 18, 2025 at 7:19 PM Toke Høiland-Jørgensen <toke@redhat.com>
> wrote:
> >
> > Edvard Fagerholm <edvard.fagerholm@gmail.com> writes:
> >  
> > > Hi,
> > >
> > > I'm working on an in-house router and I'm looking for some advice on
> > > whether to try to implement some functionality directly in an XDP
> > > program or instead use AF_XDP sockets with the additional flexibility
> > > provided by userspace.
> > >
> > > We basically have a flow table, which contains entries of the form:
> > >
> > >   (source ip, source port) -> (action, timestamp)
> > >
> > > Every time we see a packet belonging to a flow, the timestamp is
> > > updated and if the flow has been inactive for e.g. 10 seconds, the
> > > flow is considered inactive and should be deleted. Actions are of the
> > > form:
> > >
> > >   "forward packet to a.b.c.d port X using source port Y"
> > >
> > > The challenge that I have is how to clean up expired flows. Built-in
> > > options would be BPF_MAP_TYPE_LRU_PERCPU_HASH. However, dropping an
> > > active flow would be unacceptable.
> > >
> > > I'm looking at at most 10k new flow entries being added per second per
> > > router with a maximum number of concurrent flows at around 256k. Each
> > > flow sends a packet at least every 5 seconds, but most every 50ms.
> > > Does this allow me to tune the table size in such a way that no active
> > > flows can be evicted? If not, are there any other reasonable
> > > approaches for cleaning up the flows?  
> >
> > Well, hard to tell with only the number of additions. I mean, 256.000 +
> > 10.000 * 10 seconds means you'd need on the order of 356k entries in the
> > map, assuming flows expire at the same rate as they are added. Do you
> > assume any such guarantee?  
> 
> We have average session lengths over 30 seconds and a maximum of 256k
> concurrents the way the servers are set up. The first number is a
> conservative lower
> bound and the latter a conservative upper bound, so from there you get 10k
> per second as a conservative upper bound too. We see spikes sometimes during
> updates with polling clients, but they stay below this too.
> 
> I read the description of the LRU implementation in the Cilium docs. For an
> element to be expired, it would need to be put at the head of the active list
> and propagate all the way down towards the tail until being moved over to
> the head of the inactive list. Then propagate down the inactive list
> and be cleaned
> up.
> 
> If one could prove that being propagated in the lists to being cleaned
> up takes longer
> than the maximum interval every flow sees packets, then that's good enough.
> Alternatively, if the table is always larger than the maximum number of
> flows by some constant factor and one can prove some invariant that the
> kernel always recycles enough "real" inactive flows before accidentally
> recycling an active flow,
> then that would also be enough.
> 
> However, I don't think I'm quite comfortable with such an approach,
> since it relies
> on implementation details of the data structure that are not part of
> the promised API.
> 
> On the other hand, given the number of routers and load balancers using XDP,
> I was kinda hoping there was some well-known robust solution that is also
> performant.

You can see https://lore.kernel.org/bpf/20241010224708.67f18726@nuclight.lan/T/
and https://lore.kernel.org/xdp-newbies/871q07ggv0.fsf@toke.dk/T/#e98aa7356d5e94ce91a4cb4454fc4710163e1c50a
mail threads, and the other which link I've forgotten, but the essential
quote is:

 Alexei Starovoitov May 26, 2021, 4:58 p.m. UTC | #25

It's an explicit non-goal for timer api to be used as GC for conntrack.
You'll be able to use it as such, but when it fails to scale
(as it's going to happen with any timer implementation) don't blame
infrastructure for that.

> The box in question is basically doing DDoS protection, so it needs to

Yes, this is quite typical, I've had same problem. Basically, all these
routers/balancers/DDoS-protectors/etc just give up when something is undoable
in eBPF (one product I've worked on passed some packets to AF_XDP).

XDP/eBPF is still not mature technology for such tasks.

> be able to
> handle traffic at line rate. I'm also trying to avoid doing any
> expensive processing
> that takes a long time, which could cause NIC buffers to fill up and
> cause packet
> loss. Our current header based solution spends a constant amount of time per
> packet and is stateless.
> 
> > Alternatively, you could have your XDP program start a BPF timer and
> > perform the periodic cleanup from that. There will be some overhead from
> > walking the map, and a potential for racy behaviour if the same flow is
> > expired and re-added frequently, but otherwise this should be quite
> > doable.  
> 
> I would need to look into timers. Never had to deal with these before in XDP.

You will need to put a timer into each record, spending about 128 bytes for
each... Alternative solutions like an "index" map which could could be
iterated by a single timer - miss needed methods (e.g. map_for_each in LPM) in
stock kernel.

> > In any case, you'd need to size your map so that it doesn't fill up
> > before flows expire. So whether to use an LRU map is a case of whether
> > overflowing the map will result in overwriting existing entries, or
> > blocking the addition of new ones.  
> 
> We basically need both:
> 
> 1. Table should be large enough to never block connections.
> 2. The error of the approximate LRU algorithm needs to be precise
> enough to never recycle active flows.


-- 
WBR, @nuclight