RFC 3222

Terminology for Forwarding Information Base (FIB) based Router Performance

📅 published December 2001, from ietf

RFC 3222: Terminology for Forwarding Information Base (FIB) based Router Performance ✨

okay bestie, this one is from December 2001 and it's written by G. Trotter from Agilent Technologies 🧚 It's Informational, which means it's here to inform the Internet community and does not set any kind of standard 💅 The header doesn't list any RFCs it obsoletes or updates, so it's not replacing anything.

Status of This Memo

this memo is giving info for the Internet community 📚 it does not specify an Internet standard of any kind, and distribution of it is unlimited 🌸

Copyright (C) The Internet Society (2001). All Rights Reserved. 💜

Abstract

so this doc describes the terms you use in a methodology that figures out how fast an IP router can forward packets, depending on the forwarding information base (FIB) that's installed inside it 🦋 a router's forwarding performance can be tied to how big its FIB is and how that FIB is put together, which is lowkey the whole point 👑

Table of Contents

   1. Introduction.................................................... 2
   2. Overview........................................................ 3
   3. Existing Definitions............................................ 3
   4. Definition Format............................................... 3
   5. Definitions - parameters........................................ 4
   5.1 Network Prefix................................................. 4
   5.2 Network Prefix Length.......................................... 4
   5.3 Forwarding Information Base (FIB).............................. 5
   5.4 Forwarding Information Base Entry.............................. 6
   5.5 Forwarding Information Base Size............................... 6
   5.6 Longest Length Prefix Match Algorithm.......................... 7
   5.7 Forwarding Information Base Prefix Distribution................ 7
   5.8 Per-Interface or Per-Card Forwarding Information Base.......... 8
   5.9 Per-Interface Forwarding Information Base Cache................ 9
   5.10 Route Aggregation............................................ 10
   6. Definitions - metrics.......................................... 10
   6.1 Maximum Forwarding Information Base Size...................... 11
   6.2 Forwarding Information Base Learning Time..................... 11
   6.3 Forwarding Information Base-dependent Throughput.............. 12
   6.4 Forwarding Information Base-dependent Latency................. 12
   6.5 Forwarding Information Base-dependent Frame Loss Rate......... 13
   7. Security Considerations........................................ 13
   8. References..................................................... 13
   9. Author's Address............................................... 14
   10. Full Copyright Statement...................................... 15

1. Introduction ✨

this doc defines the terms you'll use in a methodology that checks how fast IP routers forward packets, based on the forwarding information base installed in the router 🎀

the goal here is to figure out how well routers perform as their FIBs keep getting bigger and more complicated 📈

this methodology uses the packet forwarding performance measurements from [2], and it also points to the terminology doc [3] for the terms 💖

2. Overview 🌈

so to measure FIB-based router performance, you install different FIBs (5.3) in the router 🧁 the two key things that describe a FIB are the FIB size (5.5) and the FIB prefix distribution (5.7) 💅 a router's performance can depend on these two big factors, especially if the prefix distribution leans toward longer network prefixes (5.1) 👀 you measure the FIB-dependent throughput, latency and frame loss rate (6.3, 6.4, 6.5) using fully meshed traffic flows [2], and that's how you see how the router's performance changes 🦋 you might have to test all the way up to the maximum FIB size (6.1) 🫶

when you set up the router for these tests, you either enter the routes in by hand or they get advertised through a routing protocol 🛠️ it can take a while (that's the FIB learning time (6.2)) before the router has learned every route ⏳

when routes get advertised into the router, they should be advertised in a way that doesn't cause route aggregation (5.10) to happen 🙅‍♀️ you also need to account for the effect of a per-interface FIB cache (5.9) 💜

3. Existing Definitions 📚

you should check out [3] before you try to use this doc 🤓 [2] talks about a bunch of terms that matter for benchmarking network interconnect devices, so it's worth a read too 💕

4. Definition Format 🎀

the definition format is the same as the one in [3], and it's repeated here so you don't have to hunt for it 🫶 it looks like this:

X.x Term to be defined. (e.g., Latency)

Definition:
   The specific definition for the term.

Discussion:
   A brief discussion about the term, it's application and any
   restrictions on measurement procedures.

Measurement units:
   The units used to report measurements of this term, if applicable.

Issues:
   List of issues or conditions that effect this term.

See Also:
   List of other terms that are relevant to the discussion of this
   term.

5. Definitions - parameters 🌸

this section defines the parameters that control how the methodology runs to figure out a router's FIB-based forwarding performance 🧚

5.1 Network Prefix 🦋

Definition: "A network prefix is . . . a contiguous set of bits at the more significant end of the address that defines a set of systems; host numbers select among those systems."

(this definition is taken straight from section 2.2.5.2, "Classless Inter Domain Routing (CIDR)", in [4] 📖)

Discussion: in CIDR land, the network prefix is the network part of an IP address 💜 people often use "slash (/) notation" to show this part instead of a bitwise mask, and it's giving clean ✨ slash notation ties the network prefix length (see 5.2), in bits, to an IP address. for example, 141.184.128.0/17 means the network part of this IPv4 address is 17 bits wide 🍓

Measurement units: <n/a>

Issues:

See Also:

  • Network Prefix Length (5.2)

5.2 Network Prefix Length 🎀

Definition: The number of bits used to define the network prefix. Network prefixes, using CIDR terminology, are typically referred to as 15.35.128.0 /17, indicating that the network prefix is 17 bits long. 🌈

Discussion: when you're talking about groups of addresses, the network prefix length is often how you describe them as an equivalence class 🫶 for example, "100 /16 addresses" refers to 100 addresses whose network prefix length is 16 bits 💅

Measurement units: bits

Issues:

See Also:

  • network prefix (5.1)
  • forwarding information base prefix distribution (5.7)

5.3 Forwarding Information Base (FIB) 👑

Definition: according to the definition in Appendix B of [4]:

"The table containing the information necessary to forward IP Datagrams, in this document, is called the Forwarding Information Base. At minimum, this contains the interface identifier and next hop information for each reachable destination network prefix."

Discussion: the FIB is basically a database that maps network prefixes to router port identifiers 🗺️

a FIB is made up of [FIB size (5.5)] FIB entries (5.4) 🧱

the FIB is not the same thing as the "routing table" (also called the Routing Information Base), which holds all the routing information received from routing peers 🙅‍♀️

the FIB only holds unique paths. it does not hold secondary paths 💎

Measurement units: <none>

Issues:

See Also:

  • forwarding information base entry (5.4)
  • forwarding information base size (5.5)
  • forwarding information base prefix distribution (5.7)
  • maximum forwarding information base size (6.1)

5.4 Forwarding Information Base Entry 🧁

Definition: a single entry inside a forwarding information base 🎀 it holds the minimum info needed to make a forwarding decision for a particular packet. the typical parts of a FIB entry are a network prefix, a router port identifier and next hop information. it's an entry the router can use, and does use, to forward packets 🚀

Discussion: see (5.3). 💕

Measurement units: <n/a>

Issues:

See Also:

  • forwarding information base (5.3)
  • forwarding information base size (5.5)
  • forwarding information base prefix distribution (5.7)
  • maximum forwarding information base size (6.1)

5.5 Forwarding Information Base Size 📏

Definition: the number of forwarding information base entries inside a forwarding information base 🧮

Discussion: the number of entries in a FIB is one of the big key elements that can affect a router's forwarding performance 😤 generally speaking, the more entries there are, the longer it could take to find the longest matching network prefix in the FIB 🐢

Measurement units: Number of routes

Issues:

See Also:

  • forwarding information base (5.3)
  • forwarding information base entry (5.4)
  • forwarding information base prefix distribution (5.7)
  • maximum forwarding information base size (6.1)

5.6 Longest Length Prefix Match Algorithm 🔍

Definition: an algorithm a router uses to quickly match destination addresses in received IP packets to the exit interfaces on the router 🏃‍♀️

Discussion:

Measurement Units: <none>

Issues:

See Also:

5.7 Forwarding Information Base Prefix Distribution 🌈

Definition: The distribution of network prefix lengths within the forwarding information base. 💅

Discussion: okay so the FIB could have all entries at one single prefix length, but realistically the prefix lengths are spread across a whole range 🫶 Performance measurements will be run against FIBs filled with one prefix length, and also against FIBs with a mix of lengths ✨

The distribution can affect how fast a router forwards. The longer the prefix length, the longer the router takes to run the longest length prefix match algorithm, and the lower the router's performance could end up being 😭

Measurement units: The FIB prefix distribution is written as a list of prefix lengths, each paired with the percentage of FIB entries that have that prefix length. Here's an example 🎀

{[/16, 100], [/20, 360], [/24, 540]}

This means 100 entries have a 16 bit network prefix length, 360 have a 20 bit network prefix length, and 540 have a 24 bit network prefix length 🍓

Issues:

See Also:

  • forwarding information base (5.3)
  • forwarding information base entry (5.4)
  • forwarding information base size (5.5)
  • maximum forwarding information base size (6.1)

5.8 Per-Interface or Per-Card Forwarding Information Base 🦋

Definition: A complete copy of the FIB, installed on a router's card or individual physical interface so the destination address to network prefix lookup goes faster 🚀

Discussion: Router manufacturers have come up with lots of optimizations, and one of them is copying the FIB onto every interface or interface card in the router. Once that's done, destination address and network prefix lookups can happen right on the interface or card, which takes the load off the router's CPU 🧠✨

Measurement units: <n/a>

Issues:

See Also:

  • forwarding information base (5.3)
  • per-interface forwarding information base cache (5.9)

5.9 Per-Interface Forwarding Information Base Cache 💜

Definition: A subset of a FIB, installed on a router's interface card to speed up the destination address / network prefix lookup 🏃‍♀️

Discussion: Before routers started putting a full FIB copy on every interface, a popular trick was to install a cache of frequently used routes on the router's interface. Those most-used routes live in the FIB cache 💖

Packets whose destination address doesn't match a network prefix in the per-interface FIB cache get sent up to the router's central processor, which looks them up in the complete FIB 👑

This matters a lot for benchmarking. Packets whose destination address matches a cache entry can be forwarded faster than packets that don't match one ✨

To create useful benchmarks, you have to think about the per-interface forwarding cache. Benchmark tests that measure forwarding performance need the destination addresses in the incoming packets to be spread across the full set of network prefixes advertised into the router. That cancels out the cache's help, but it does stress the FIB-based forwarding performance of the router, which is the whole point 💅

Measurement units: <n/a>

Issues:

See Also:

  • forwarding information base (5.3)
  • per-interface forwarding information base (5.8)

5.10 Route Aggregation 🌸

Definition: The ability of a router to squash many FIB entries down into a single entry 🗜️

Discussion: A router may aggregate routes in its FIB into one entry to save space 💾

When you advertise routes into a router to run benchmarks that depend on the FIB installed inside it, you have to make sure the router doesn't aggregate the routes. Otherwise your results are kind of cooked 🙈

So when routes get advertised to the router or installed statically, you need to take care that the router doesn't aggregate them.

For example, say you advertise a set of /24 network prefixes into one particular port on the router. If you send 256 consecutive /24 routes that share a common leading 16 bits, all on a single port, the router will install one FIB entry saying that every network matching that particular /16 network prefix is reachable through that one entry. Not what you wanted! 😭

Route aggregation on a router can be turned off, but the routes should still be advertised into the router in a way that avoids aggregation anyway 🎀

Measurement units: <none>

Issues:

See Also:

6. Definitions - metrics 📊

This section defines the metrics, or results, that would characterize the FIB based forwarding performance of a router. 🧚

6.1 Maximum Forwarding Information Base Size 👑

Definition: The maximum number of FIB entries that can be supported within the FIB. The Maximum Forwarding Information Base Size is the size at which all entries can be used, and are used, to forward traffic. 🔥

Discussion: Knowing the maximum FIB size for a router is super useful. It tells you whether the router can handle the application space you're aiming for, and whether it'll keep up with projected network growth 📈

As a benchmarking value, you need to find this number so performance measurements can be made all the way up to the maximum possible FIB size 💖

Measurement units: Number of routes

Issues: Could this value vary with the forwarding information base prefix distribution? 🤔

See Also:

  • forwarding information base (5.3)
  • forwarding information base entry (5.4)
  • forwarding information base size (5.5)
  • forwarding information base prefix distribution (5.7)

6.2 Forwarding Information Base Learning Time ⏳

Definition: The time a router takes to process received routing messages, and to construct the FIB (and possibly distribute it, or a subset of it, among the interface cards in the router). This is measured from the moment the router is presented with the first routing message, until it can forward packets using any entry in the FIB 🎬

Discussion: It takes time for a router to build its FIB. The router has to process received routing packets, build the routing information database, select the best paths, build the FIB, and then possibly distribute the FIB or a subset of it to the interface cards. With very large FIBs, this whole process can take several minutes 😭

When you're benchmarking with the FIB taken into account, you have to give the router time to process the routing information and install the complete FIB inside itself before you start measuring performance 🕐✨

Measurement units: Prefixes per second.

Issues:

See Also:

  • forwarding information base (5.3)

6.3 Forwarding Information Base-dependent Throughput 🚀

Definition: Throughput, as defined in [3], used in a context where the FIB influences the throughput. 💅

Discussion: This definition of FIB-dependent throughput was added so that this measurement is clearly distinguished from the one defined in [3] 🫶

Measurement units: See [3].

Issues:

See Also:

  • forwarding information base-dependent latency (6.4)
  • forwarding information base-dependent frame loss rate (6.5)

6.4 Forwarding Information Base-dependent Latency ⏱️

Definition: Latency, as defined in [3], used in a context where the FIB influences the throughput. 🎀

Discussion: This definition of FIB-dependent latency was added so that this measurement is clearly distinguished from the one defined in [3] 💜

Measurement units: See [3].

Issues:

See Also:

  • forwarding information base-dependent throughput (6.3)
  • forwarding information base-dependent frame loss rate (6.5)

6.5 Forwarding Information Base-dependent Frame Loss Rate 📉

Definition: Frame Loss Rate, as defined in [3], used in a context where the FIB influences the throughput. 🌸

Discussion: This definition of FIB-dependent frame loss rate was added so that this measurement is clearly distinguished from the one defined in [3] 🦋

Measurement units: See [3].

Issues:

See Also:

  • forwarding information base-dependent throughput (6.3)
  • forwarding information base-dependent latency (6.4)

7. Security Considerations 🔐

As this document is solely for the purpose of providing metric methodology and describes neither a protocol nor a protocols implementation, there are no security considerations associated with this document. 🫶

8. References 📚

  • [1] Bradner, S., "The Internet Standards Process -- Revision 3", BCP 9, RFC 2026, October 1996.
  • [2] Bradner, S. and J. McQuaid, "Benchmarking Methodology for Network Interconnect Devices", RFC 2544, March 1999.
  • [3] Bradner, S., "Benchmarking Terminology for Network Interconnection Devices", RFC 1242, July 1991.
  • [4] Baker, F., "Requirements for IP Version 4 Routers", RFC 1812, June 1995.

9. Author's Address 🖊️

Guy Trotter
Agilent Technologies (Canada) Inc.
#2500 4710 Kingsway
Burnaby, British Columbia
Canada
V5H 4M2

Phone: +1 604 454 3516
EMail: Guy_Trotter@agilent.com

okay bestie, this is the legal bit 💅 and yes it's copyright, so the Internet Society gets its name on it 🌸

Copyright (C) The Internet Society (2001). All Rights Reserved. 🎀

so basically you can copy this doc and pass it around 📄 and you can make derivative works that comment on or explain it or help people implement it 🔥 just keep the copyright notice and this paragraph on everything you make ✨ the one thing you can't do is edit this doc itself 🙈, like you can't delete the copyright notice or the Internet Society references, unless it's for making Internet standards (then the Internet Standards process copyright procedures have to be followed) or you're translating it into a language that isn't English 🌈

the permissions are perpetual 💖 the Internet Society and its successors or assigns won't take them back 🫶

and now the disclaimer, which is not as fun but very important 😭 this doc and the information in it is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 💀 translation: no promises, no guarantees, use it at your own risk 🙈

Acknowledgement 🫶

funding for the RFC Editor function is currently provided by the Internet Society 🧚 so the people who keep these docs organised get their bills paid by the same crew that wrote the copyright notice, which is pretty iconic 💜

📦 where this page comes from