# US 8,149,713 B2 · Forwarding of packets based on a filtered forwarding information base > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,149,713 B2 - Document ID: US8149713B2 - Status: Granted - Kind: B2 - Application number: 12/569,712 - Filed: 2009-09-29 - Published: 2011-03-31 - Granted: 2012-04-03 - Earliest claimed: 2009-09-29 - Assignees: Cisco Technology, Inc. - Inventors: Fan Sun; David Delano Ward; Shyamsundar Nandkishor Maniyar; Clarence Filsfils - Web page: https://patentgrep.com/patent/US8149713B2 ## CPC - H04L 45/00: Routing or path finding of packets in data switching networks (routing or path finding in wireless networks H04W40/00) - H04L 45/03: by updating link state protocols - H04L 45/54: {Organization of routing tables} - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract A filtered Forwarding Information Base (FIB) (the “complete local FIB”) is used to determine how to forward packets, typically on line cards. The complete local FIB is generated by filtering (i.e., dropping or removing) extraneous entries in the standard global FIB of a router. This smaller FIB is then installed within the memory of a forwarding engine, possibly implemented as a single application-specific integrated circuit (ASIC), for use in determining how to forward packets, with the router forwarding packets accordingly. ## Claims ### Claim 1 A method, performed by a router, with said method comprising: communicating, by the router via one or more routing protocols, with other routers to generate a routing information base (RIB) for identifying topology information of, including routes within, a network attached to the router; generating, from the RIB, a global forwarding information base (FIB) containing entries, wherein the entries include: forwarding information for a plurality of routes, with said forwarding information including an identification of an egress interface of the router and next hop information; filtering the global FIB to generate a complete local FIB identifying forwarding information for a plurality of packets received by the router, wherein the complete local FIB includes a copy of less than all of the entries in the global FIB, and wherein the complete local FIB does not include all routes in the plurality of routes; determining how to forward each of the plurality of packets based on the complete local FIB; and forwarding each of the plurality of packets based on the complete local FIB. ### Claim 2 (depends on 1) The method of claim 1, wherein the router comprises: a line card; wherein the line card includes: a plurality of interfaces configured to send and receive packets; the global FIB; and a forwarding engine for performing said operation of determining how to forward each of the plurality of packets based on the complete local FIB; and wherein the forwarding engine includes the complete local FIB. ### Claim 3 (depends on 2) The method of claim 2, wherein the line card comprises an application-specific integrated circuit which includes the forwarding engine, which said includes the complete local FIB. ### Claim 4 (depends on 1) The method of claim 1, wherein the router comprises: a route processing subsystem and a line card; wherein said operations of communicating with other routers and generating the global FIB are performed by the route processing subsystem; wherein the method includes storing a copy of the global FIB onto the line card; wherein the line card includes: the global FIB said copied to it and a forwarding engine for performing said operation of determining how to forward each of the plurality of packets based on the complete local FIB stored on the line card; wherein the forwarding engine includes the complete local FIB; and wherein said operation of filtering of the global FIB to generate the complete local FIB is performed on the line card. ### Claim 5 (depends on 4) The method of claim 4, wherein the line card includes an application-specific integrated circuit which includes the forwarding engine, which said includes the complete local FIB. ### Claim 6 (depends on 1) The method of claim 1, wherein said operation of filtering is responsive to a configured predetermined role of the line card of the router. ### Claim 7 (depends on 1) The method of claim 1, wherein said one or more routing protocols include an interior gateway protocol (IGP). ### Claim 8 (depends on 7) The method of claim 7, wherein the global FIB includes marking information for identifying what portion of said forwarding information in the global FIB should and what should not be installed in the complete local FIB by said operation of filtering the global FIB; and wherein said marking information identifies that all forwarding information corresponding to routing information received from at least one specific routing protocol of said one or more routing protocols should be installed in the complete local FIB by said operation of filtering the global FIB. ### Claim 9 (depends on 1) The method of claim 1, wherein the global FIB includes marking information for identifying what portion of said forwarding information in the global FIB should and what should not be installed in the complete local FIB by said operation of filtering the global FIB. ### Claim 10 (depends on 9) The method of claim 9, comprising: marking routes in the RIB; wherein said operation of generating the global FIB causes said marking information to be included in the complete local FIB. ### Claim 11 (depends on 1) The method of claim 1, wherein the global FIB includes forwarding information including labels for a plurality of label-switched routes of the plurality of routes; and wherein said operation of filtering the global FIB filters out one or more of the plurality of label-switched routes that will not be used in forwarding packets by the line card based on said topology information. ### Claim 12 (depends on 1) The method of claim 1, wherein said operation of filtering the global FIB filters out one or more of the plurality of routes that will not be used in forwarding packets by the line card based on said topology information. ### Claim 13 (depends on 1) The method of claim 1, wherein said operation of filtering the global FIB in generating the complete local FIB in determining whether or not to include an entry in the local FIB is responsive to configuration settings received via a user interface. ### Claim 14 (depends on 1) The method of claim 1, wherein said operation of filtering the global FIB in generating the complete local FIB in determining whether or not to include an entry in the local FIB is responsive to administrative tags, prefix ranges, or masklengths of entries in the global FIB. ### Claim 15 (depends on 1) The method of claim 1, wherein the global FIB includes over a hundred different forwarding information entries; and wherein said operation of filtering the global FIB results in only forwarding information for a single default route being stored in the complete local FIB. ### Claim 16 (depends on 1) The method of claim 1, wherein the global FIB includes over one hundred thousand different forwarding information entries; and wherein said operation of filtering the global FIB results in less than ten thousand different forwarding entries being stored in the complete local FIB. ### Claim 17 A router, comprising: a route processing subsystem configured to communicate, via one or more routing protocols, with other routers to generate a routing information base (RIB) for identifying topology information of, including routes within, a network attached to the router; and configured to generate, from the RIB, a global forwarding information base (FIB) containing entries, wherein the entries include: forwarding information for a plurality of routes, with said forwarding information including an identification of an egress interface of the router and next hop information; a plurality of line cards communicatively coupled to the route processing subsystem, with each of the plurality of line cards including: a plurality of interfaces for communicating packets with other communications devices; storage configured to store a global forwarding information base (FIB) including forwarding information for how to forward corresponding packets from the router, with said forwarding information including an identification of next hop information and an egress interface of the router from which to forward a corresponding packet; a forwarding engine configured to store a complete local FIB, and configured to determine how to forward packets based on the complete local FIB; and one or more processors configured to filter the global FIB stored locally on the line card to generate the complete local FIB identifying forwarding information for packets, wherein the complete local FIB includes a copy of less than all of the entries in the global FIB. ### Claim 18 (depends on 17) The router of claim 17, wherein each of the plurality of line cards comprises an application-specific integrated circuit which includes the forwarding engine, which said includes the complete local FIB. ### Claim 19 (depends on 17) The router of claim 17, wherein the global FIB includes marking information for identifying what portion of said forwarding information in the global FIB should and what should not be installed in the complete local FIB by said one or more processors configured to filter the global FIB stored locally on the line card to generate the complete local FIB. ### Claim 20 A router, comprising: a plurality of line cards, with each of the plurality of line cards including: a plurality of interfaces configured to send and receive packets; storage configured to store a global forwarding information base (FIB) containing entries, wherein the entries include: forwarding information including an identification of next hop information and an egress interface of the router; a forwarding engine configured to store a complete local FIB, and configured to determine how to forward packets based on the complete local FIB; and one or more processing elements configured to filter the global FIB stored locally on the line card to generate the complete local FIB identifying forwarding information for packets, wherein the complete local FIB includes a copy of less than all of the entries in the global FIB; and one or more communications mechanism configured to communicate packets or information among the plurality of line cards. ### Claim 21 (depends on 20) The router of claim 20, wherein for each particular line card of the plurality of line cards said one or more processing elements configured to filter the global FIB are responsive to a configured predetermined role of the particular line card. ### Claim 22 (depends on 21) The router of claim 21, wherein a first line card of the plurality of line cards and a second line card of the plurality of line cards are each configured to have different predetermined roles, and wherein said one or more processing elements configured to filter the global FIB of the first and second line cards are configured to generate different complete local FIBs based on said different predetermined roles.