# US 2019/0173791 A1 · Forwarding Table Management

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2019/0173791 A1
- Document ID: US20190173791A1
- Status: Published application
- Kind: A1
- Application number: 16/205,538
- Filed: 2018-11-30
- Published: 2019-06-06
- Earliest claimed: 2017-12-01
- Assignees: Extreme Networks, Inc.
- Applicants: Extreme Networks, Inc.
- Inventors: How T. LIM; Lok Y. HUI
- Web page: https://patentgrep.com/patent/US20190173791A1

## CPC

- H04L 45/748: using longest matching prefix
- H04L 45/54: {Organization of routing tables}
- H04L 45/60: Router architectures
- H04L 45/74591: {using content-addressable memories [CAM]}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

Disclosed herein are system, method, and computer program product embodiments for representing a forwarding information base (FIB) in a database. An embodiment operates by determining that a first routing prefix of a first forwarding entry in the FIB is a less specific routing prefix than a second routing prefix in a second forwarding entry in the FIB. The embodiment determines that a first next hop of the first routing prefix is equal to a second next hop of the second routing prefix. The embodiment removes the second forwarding entry from the FIB. The embodiment then inserts the first forwarding entry into a database (e.g., a longest exact match (LEM) database or a longest prefix match (LPM) database) based on a prefix length of the first routing prefix of the first forwarding entry.

## Claims

### Claim 1

A computer implemented method for representing a forwarding information base (FIB) in a database, comprising:
determining, by at least one processor, that a first routing prefix of a first forwarding entry in the FIB is a less specific routing prefix than a second routing prefix in a second forwarding entry in the FIB;
determining, by the at least one processor, a first next hop of the first routing prefix is equal to a second next hop of the second routing prefix;
removing, by the at least one processor, the second forwarding entry from the FIB based on the determination that the first next hop of the first routing prefix is equal to the second next hop of the second routing prefix; and
inserting, by the at least one processor, the first forwarding entry into a longest exact match (LEM) database or a longest prefix match (LPM) database based on a prefix length of the first routing prefix of the first forwarding entry.

### Claim 2 (depends on 1)

The method of claim 1, wherein the first next hop comprises a next hop address and an outgoing interface.

### Claim 3 (depends on 1)

The method of claim 1, wherein the inserting comprises inserting the first forwarding entry into the LPM database based on the prefix length of the first routing prefix of the first forwarding entry being different than 24 bits or 32 bits.

### Claim 4 (depends on 1)

The method of claim 1, wherein the inserting comprises inserting the first forwarding entry into the LEM database based on the prefix length of the first routing prefix of the first forwarding entry being 24 bits or 32 bits.

### Claim 5 (depends on 1)

The method of claim 1, wherein each of the LEM and LPM databases comprise ternary content-addressable memory (TCAM).

### Claim 6 (depends on 1)

The method of claim 1, further comprising:
generating a first sub routing prefix and a second sub routing prefix from a third routing prefix of a third forwarding entry in the FIB based on a prefix length of the third routing prefix being 23 bits.

### Claim 7 (depends on 6)

The method of claim 6, further comprising:
inserting the first sub routing prefix and the second sub routing prefix into the LEM database.

### Claim 8

A system, comprising:
a memory, and
at least one processor coupled to the memory and configured to:
determine that a first routing prefix of a first forwarding entry in a forwarding information base (FIB) is a less specific routing prefix than a second routing prefix in a second forwarding entry in the FIB;
determine a first next hop of the first routing prefix is equal to a second next hop of the second routing prefix;
remove the second forwarding entry from the FIB based on the determination that the first next hop of the first routing prefix is equal to the second next hop of the second routing prefix; and
insert the first forwarding entry into a database based on a prefix length of the first routing prefix of the first forwarding entry.

### Claim 9 (depends on 8)

The system of claim 8, wherein the first next hop comprises a next hop address and an outgoing interface.

### Claim 10 (depends on 8)

The system of claim 8, wherein to insert the first forwarding entry, the at least one processor is configured to insert the first forwarding entry into the database based on the prefix length of the first routing prefix of the first forwarding entry being different than 24 bits or 32 bits, wherein the database comprises a longest prefix match (LPM) database.

### Claim 11 (depends on 8)

The system of claim 8, wherein to insert the first forwarding entry, the at least one processor is configured to insert the first forwarding entry into the database based on the prefix length of the first routing prefix of the first forwarding entry being 24 bits or 32 bits, wherein the database comprises a longest exact match (LEM) database.

### Claim 12 (depends on 8)

The system of claim 8, wherein the database comprises temrnary content-addressable memory (TCAM).

### Claim 13 (depends on 8)

The system of claim 8, wherein the at least one processor is further configured to generate a first sub routing prefix and a second sub routing prefix from a third routing prefix of a third forwarding entry in the FIB based on a prefix length of the third routing prefix being 23 bits.

### Claim 14 (depends on 13)

The system of claim 13, wherein the at least one processor is further configured to insert the first sub routing prefix and the second sub routing prefix into the database.

### Claim 15

A non-transitory computer-readable device having instructions stored thereon that, when executed by at least one computing device, causes the at least one computing device to perform operations comprising:
determining that a first routing prefix of a first forwarding entry in a forwarding information base (FIB) is a less specific routing prefix than a second routing prefix in a second forwarding entry in the FIB;
determining a first next hop of the first routing prefix is equal to a second next hop of the second routing prefix;
removing the second forwarding entry from the FIB based on the determination that the first next hop of the first routing prefix is equal to the second next hop of the second routing prefix; and
inserting the first forwarding entry into an exact match database based on a prefix length of the first routing prefix of the first forwarding entry being 24 bits or 32 bits.

### Claim 16 (depends on 15)

The non-transitory computer-readable device of claim 15, wherein the inserting comprises inserting a third forwarding entry into a longest prefix match (LPM) database based on a prefix length of a third routing prefix of the third forwarding entry being different than 24 bits or 32 bits.

### Claim 17 (depends on 15)

The non-transitory computer-readable device of claim 15, wherein the FIB is organized using a trie data structure.

### Claim 18 (depends on 16)

The non-transitory computer-readable device of claim 16, wherein each of the exact and LPM databases comprise ternary content-addressable memory (TCAM).

### Claim 19 (depends on 15)

The non-transitory computer-readable device of claim 15, wherein the operations further comprise generating a first sub routing prefix and a second sub routing prefix from a third routing prefix of a third forwarding entry in the FIB based on a prefix length of the third routing prefix being 23 bits.

### Claim 20 (depends on 19)

The non-transitory computer-readable device of claim 19, wherein the operations further comprise inserting the first sub routing prefix and the second sub routing prefix into the exact database.