Apparatus, system, and method for optimizing forwarding information bases on network devices

A method may include (1) identifying a set of prefixes that (A) facilitate forwarding traffic within a network and (B) are organized as a tree data structure in connection with a table stored on a network device, (2) identifying, in the set of prefixes organized as the tree data structure, a parent prefix and a child prefix that corresponds to the parent prefix, (3) determining that the parent prefix and the child prefix share a certain number of most-significant bits in common with one another, (4) determining that the parent prefix and the child prefix share a forwarding behavior in common with one another and then, in response to determining that the parent prefix and the child prefix share the certain number of most-significant bits and the forwarding behavior in common with one another, (5) compressing the table stored on the network device by merging the child prefix with the parent prefix within the table. Various other apparatuses, systems, and methods are also disclosed.

BACKGROUND

The Internet is built on and/or supported by network devices (such as routers) that facilitate the flow of traffic from one end-point to another. The current size of the Internet may include and/or involve approximately 800,000 Internet Protocol version 4 (IPv4) routes and approximately 35,000 Internet Protocol version 6 (IPv6) routes. A typical Internet router may include and/or store around 1,000,000 IPv4 routes and between 100,000 and 200,000 IPv6 routes. Due to their longer prefix lengths, IPv6 routes may consume 4 times as much space as IPv4 routes.

In some examples, network devices may store and/or install these IPv4 and IPv6 routes in expensive Forwarding Information Bases (FIBs). Such network devices may also store and/or install other routes like Multiprotocol Label Switching (MPLS) routes and/or multicast routes in the expensive FIBs. Upon installation of such routes, these network devices may have very little capacity remaining in their FIBs. Nevertheless, the size of the Internet may continue growing at a rate of approximately 10% per year. Accordingly, the FIBs of these network devices may soon be unable to store and/or install the full collection of routes that facilitate access to the Internet without further optimization. The instant disclosure, therefore, identifies and addresses a need for improved apparatuses, systems, and methods for optimizing FIBs on network devices.

SUMMARY

As will be described in greater detail below, the instant disclosure generally relates to apparatuses, systems, and methods for optimizing FIBs on network devices. In one example, a method for accomplishing such a task may include (1) identifying a set of prefixes that (A) facilitate forwarding traffic within a network and (B) are organized as a tree data structure in connection with a table stored on a network device, (2) identifying, in the set of prefixes organized as the tree data structure, a parent prefix and a child prefix that corresponds to the parent prefix, (3) determining that the parent prefix and the child prefix share a certain number of most-significant bits in common with one another, (4) determining that the parent prefix and the child prefix share a forwarding behavior in common with one another and then, in response to determining that the parent prefix and the child prefix share the certain number of most-significant bits and the forwarding behavior in common with one another, (5) compressing the table stored on the network device by merging the child prefix with the parent prefix within the table.

Similarly, a system that implements the above-identified method may include a physical processor configured to execute various modules stored in memory on a network device within a network. In one example, this system may include and/or execute (1) an identification module that (A) identifies a set of prefixes that (I) facilitate forwarding traffic within a network and (II) are organized as a tree data structure in connection with a table stored on a network device and (B) identifies, in the set of prefixes organized as the tree data structure, a parent prefix and a child prefix that corresponds to the parent prefix, (2) a determination module that (A) determines that the parent prefix and the child prefix share a certain number of most-significant bits in common with one another and (B) determines that the parent prefix and the child prefix share a forwarding behavior in common with one another, and (3) a compression module that compresses the table stored on the network device by merging the child prefix with the parent prefix within the table due at least in part to the parent prefix and the child prefix sharing the certain number of most-significant bits and the forwarding behavior in common with one another.

Additionally or alternatively, an apparatus that implements the above-identified method may include at least one storage device that stores a set of prefixes that (1) facilitate forwarding traffic within a network and (2) are organized as a tree data structure in connection with a table stored on a network device. The apparatus may also include at least one physical processor communicatively coupled to the storage device. In one example, the physical processor may (1) identifies, in the set of prefixes organized as the tree data structure, a parent prefix and a child prefix that corresponds to the parent prefix, (2) determines that the parent prefix and the child prefix share a certain number of most-significant bits in common with one another, (3) determines that the parent prefix and the child prefix share a forwarding behavior in common with one another, and then (4) compresses the table stored on the network device by merging the child prefix with the parent prefix within the table in response to determining that the parent prefix and the child prefix share the certain number of most-significant bits and the forwarding behavior in common with one another.

DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS

The present disclosure describes various apparatuses, systems, and methods for optimizing FIBs on network devices. As will be explained in greater detail below, embodiments of the instant disclosure may involve compressing FIBs of network devices by merging eligible child prefixes with their corresponding parent prefixes within those FIBs. For example, a router may identify a child prefix corresponding to a parent prefix installed on a FIB of the router. In this example, if the parent prefix and the child prefix share a certain number of most-significant bits in common and share a certain forwarding behavior in common, then the router may merge the child prefix with the parent prefix within the FIB. This merger may involve refusing to install the child prefix in the FIB and/or deleting the child prefix from the FIB.

The router may repeat such mergers for each eligible child prefix to compress the FIB. By compressing the FIB in this way, the router may be able to optimize the capacity and/or space in the FIB. In some examples, this optimization may effectively double the storage capacity of the FIB on the router.

The following will provide, with reference toFIGS.1-10detailed descriptions of exemplary apparatuses, systems, components, and corresponding implementations for optimizing FIBs on network devices. Detailed descriptions of computer-implemented methods for optimizing FIBs on network devices will be provided in connection withFIG.11. In addition, detailed descriptions of an exemplary computing system for carrying out these methods will be provided in connection withFIG.12.

FIG.1shows an exemplary system100that facilitates optimizing FIBs on network devices. As illustrated inFIG.1, system100may include one or more modules102for performing one or more tasks. As will be explained in greater detail below, modules102may include an identification module104, a determination module106, a compression module108, an installation module110, and a detection module112. Although illustrated as separate elements, one or more of modules102inFIG.1may represent portions of a single module, application, and/or operating system. For example, one or more of modules102may represent part of and/or be included in a table-compression application that simulates a table (such as a FIB) stored on a network device.

In certain embodiments, one or more of modules102inFIG.1may represent one or more software applications or programs that, when executed by a computing device, cause the computing device to perform one or more tasks. For example, and as will be described in greater detail below, one or more of modules102may represent modules stored and configured to run on one or more computing devices, such as the devices illustrated inFIG.2(e.g., network devices202,206,208,210(1)-(N), and/or212(1)-(N)), the devices illustrated inFIG.3(e.g., routing engine310, packet forwarding engine312, etc.), and/or the devices illustrated inFIG.12(e.g., computing system1200). One or more of modules102inFIG.1may also represent all or portions of one or more special-purpose computers configured to perform one or more tasks.

As illustrated inFIG.1, exemplary system100may further include one or more tables, such as table120. In some examples, table120may include and/or represent a FIB and/or a Routing Information Base (RIB). In one example, table120may include and/or represent a set of prefixes122(1)-(N) organized as a tree data structure in a FIB, a RIB, and/or a simulator. In this example, prefixes122(1)-(N) within table120may include and/or represent a copy of prefixes that are duplicated elsewhere on a network device. Additionally or alternatively, prefixes122(1)-(N) may constitute and/or represent routes, data, and/or information that identify or refer to a portion of a network, network device, and/or network interface.

In one example, prefixes122(1)-(N) may each identify and/or represent a path capable of carrying traffic within a network and/or across networks. Additionally or alternatively, prefixes122(1)-(N) may include and/or contain data representations of and/or references to one or more physical devices or interfaces (such an “ifd”), logical devices or interfaces (such as an “ifl”), next hops, and/or path segments. Examples of prefixes122(1)-(N) include, without limitation, Internet Protocol (IP) prefixes (such as IPv4 and/or IPv6 prefixes), Multiprotocol Label Switching (MPLS) prefixes, Virtual Private Local Area Network Service (VLAN) prefixes, Border Gateway Protocol (BGP) prefixes, Open Shortest Path First (OSPF) prefixes, variations or combinations of one or more of the same, and/or any other suitable prefixes.

In some examples, prefixes122(1)-(N) may include and/or represent a collection of parent prefixes and/or child prefixes. In one example, a parent prefix may include and/or represent a string of bits that define a network path. In this example, a child prefix corresponding to the parent prefix may include and/or represent a certain number of most-significant bits that match the parent prefix in addition to one or more least significant bits. Accordingly, the child prefix may be longer than the parent prefix and may include the same string of bits as the parent prefix in the left-most section as well as one or more additional bits in the right-most section.

As illustrated inFIG.1, exemplary system100may additionally include one or more compression libraries, such as compression library124. In some examples, compression library124may represent part of and/or be included in a table-compression application that simulates a FIB and/or RIB stored on a network device. In one example, compression library124may include and/or represent another copy of prefixes122(1)-(N). In this example, the simulation may enable the table-compression application to determine whether certain child prefixes stored in the FIB and/or RIB are eligible for merger with their corresponding parents without necessarily examining, reading from, and/or writing to the FIB and/or RIB itself.

An apparatus for optimizing FIBs on network devices may include all or portions of exemplary system100. In some examples, system100inFIG.1may be implemented in a variety of ways. For example, all or a portion of exemplary system100may represent portions of exemplary system200inFIG.2. As shown inFIG.2, system200may include a network204that facilitates communication among network device206, network devices210(1)-(N), network devices212(1)-(N), network device202, and/or network device208.

As illustrated inFIG.2, network204may include and/or represent various network devices and/or nodes that form and/or establish communication paths and/or segments. For example, network204may include a network device206that forwards traffic from network device202along one or more active paths toward network device208. In this example, an active path may include and/or represent network devices210(1)-(N), and another active path may include and/or represent network devices212(1)-(N).

In some embodiments, each of network devices202,206,208,210(1)-(N), and/or212(1)-(N) may include and/or represent an instance of memory140, an instance of physical processor130, an instance of table120, and/or an instance of compression library124. In one example, and as will be described in greater detail below, one or more of modules102may cause network device206to (1) identify a set of prefixes122(1)-(N) that (A) facilitate forwarding traffic within network204and (B) are organized as a tree data structure in connection with table120stored on network device206, (2) identify, in the set of prefixes122(1)-(N) organized as the tree data structure, a child prefix that corresponds to a parent prefix, (3) determine that the parent prefix and the child prefix share a certain number of most-significant bits in common with one another, (4) determine that the parent prefix and the child prefix share a forwarding behavior in common with one another and then, in response to determining that the parent prefix and the child prefix share the certain number of most-significant bits and the forwarding behavior in common with one another, (5) compress table120stored on network device206by merging the child prefix with the parent prefix within table120.

Network devices202,206,208,210(1)-(N), and/or212(1)-(N) each generally represent any type or form of physical computing device capable of reading computer-executable instructions, handling network traffic, and/or optimizing FIBs. In one example, network devices202,206,208,210(1)-(N), and/or212(1)-(N) may each include and/or represent a router (such as a transit label switching router, a label edge router, a provider edge router, a hub router, a spoke router, an autonomous system boundary router, and/or an area border router). Additional examples of network devices202,206,208,210(1)-(N), and/or212(1)-(N) include, without limitation, switches, hubs, modems, bridges, repeaters, gateways (such as Broadband Network Gateways (BNGs)), multiplexers, network adapters, network interfaces, linecards, collectors, client devices, laptops, tablets, desktops, servers, cellular phones, Personal Digital Assistants (PDAs), multimedia players, embedded systems, wearable devices, gaming consoles, portions of one or more of the same, variations or combinations of one or more of the same, and/or any other suitable devices.

Network204generally represents any medium and/or architecture capable of facilitating communication, data transfer, and/or route changes. In one example, network204may include any or all of network devices202,206,208,210(1)-(N), and/or212(1)-(N) even though some of these devices are illustrated as being external to network204inFIG.2. Additionally or alternatively, network204may include other devices that facilitate communication among network devices202,206,208,210(1)-(N), and/or212(1)-(N). Network204may facilitate communication or data transfer using wireless and/or wired connections. Examples of network204include, without limitation, an intranet, an access network, a layer 2 network, a layer 3 network, an MPLS network, an IP network, a heterogeneous network (e.g., layer 2, layer 3, IP, and/or MPLS) network, a Wide Area Network (WAN), a Local Area Network (LAN), a Personal Area Network (PAN), the Internet, Power Line Communications (PLC), a cellular network (e.g., a Global System for Mobile Communications (GSM) network), portions of one or more of the same, variations or combinations of one or more of the same, and/or any other suitable network.

FIG.11is a flow diagram of an exemplary computer-implemented method1100for optimizing FIBs on network devices. The steps shown inFIG.11may be performed by any suitable computer-executable code and/or computing system, including system100inFIG.1, system200inFIG.2, network device206inFIG.3, system1200inFIG.12, and/or variations or combinations of one or more of the same. In addition, the steps shown inFIG.11may be performed by any suitable node, device, and/or component included in system100inFIG.1, system200inFIG.2, network device206inFIG.3, system1200inFIG.12, and/or the like. In one example, each of the steps shown inFIG.10may represent an algorithm whose structure includes and/or is represented by multiple sub-steps, examples of which will be provided in greater detail below.

As illustrated inFIG.11, at step1110one or more of the systems described herein may identify a set of prefixes that facilitate forwarding traffic within a network and are organized as a tree data structure in connection with a table stored on a network device. For example, identification module104may, as part of network device206inFIG.2, identify a set of prefixes122(1)-(N) that facilitate forwarding traffic within network204. In this example, set of prefixes122(1)-(N) may be organized as a tree data structure (such as a radix tree) in connection with table120. In some examples, table120may include and/or represent a FIB stored and/or implemented on a packet forwarding engine of network device206. Additionally or alternatively, table120may include and/or represent a RIB stored and/or implemented on a routing engine of network device206.

In some examples, the packet forwarding engine and/or routing engine may constitute and/or represent a hardware component or device incorporated into network device206. For example, the packet forwarding engine may include and/or represent an ASIC, a System on a Chip (SoC), a general-purpose processor, and/or any other suitable processing element. Additionally or alternatively, the routing engine may include and/or represent an ASIC, an SoC, a general-purpose processor, and/or any other suitable processing element.

The systems described herein may perform step1110in a variety of ways and/or contexts. In some examples, identification module104may represent part of and/or be included in a table-compression application implemented by network device206to simulate table120stored on network device206. In one example, the table-compression application may be implemented on and/or via the packet forwarding engine of network device206. In another example, the table-compression application may be implemented on and/or via the routing engine of network device206.

In one example, the table-compression application may maintain and/or access compression library124that includes a copy of prefixes122(1)-(N) and/or reflects the current state of table120. In this example, installation module110may install that copy of prefixes122(1)-(N) in table120and/or compression library124.

In some examples, installation module110may maintain prefixes122(1)-(N) as part of the table-compression application that simulates and/or emulates table120. For example, installation module110may duplicate route changes across table120and/or compression library124as such route changes reach and/or affect network device206. In this example, installation module110may detect a route change to be performed on the copy of prefixes stored in table120. Installation module110may then propagate the route change to the copy of prefixes maintained as part of the table-compression application. Such detection and/or propagation of route changes may be performed inline and/or in-band as those route changes reach and/or arrive at network device206.

In some examples, identification module104may search compression library124for a copy of the prefixes currently installed in the FIB of network device206. During this search of compression library124, identification module104may identify and/or locate a copy of prefixes122(1)-(N), which are organized as a tree data structure and collectively represent the current state of the FIB of network device206. In other examples, identification module104may search the FIB of network device206for the prefixes currently installed. During the search of the FIB, identification module104may identify and/or locate a copy of prefixes122(1)-(N) that are organized as a tree data structure. In further examples, identification module104may search the RIB of network device206for the prefixes currently installed. During the search of the RIB, identification module104may identify and/or locate a copy of prefixes122(1)-(N), which are organized as a tree data structure and reflect the current state of the FIB of network device206.

As illustrated inFIG.11, at step1120one or more of the systems described herein may identify, in the set of prefixes organized as the tree data structure, a parent prefix and a child prefix that corresponds to the parent prefix. For example, identification module104may, as part of network device206inFIG.2, identify a prefix122(1) as being a parent to prefix122(N). In this example, as the child, prefix122(N) may be longer than prefix122(1). Specifically, prefix122(1) may constitute and/or represent a subset of prefix122(N) positioned in the most-significant and/or left-most region of prefix122(N).

The systems described herein may perform step1120in a variety of ways and/or contexts. In one example, identification module104may identify prefix122(1) as a node within the tree data structure. In this example, identification module104may walk through the tree data structure from prefix122(1) to prefix122(N). Upon arriving at prefix122(N), identification module104may identify prefix122(N) as another node within the tree data structure. In view of these observations and/or discoveries during the tree walk, identification module104may identify prefix122(N) as being a child to prefix122(1).

In some examples, prefixes122(1) and122(N) may be linked to one another within the tree data structure. For example, prefixes122(1) and122(N) may be positioned and/or located within the same branch of the tree data structure. In this example, prefix122(1) may be positioned and/or located above prefix122(N) toward the root node of the tree data structure. Accordingly, prefix122(N) may be positioned and/or located below prefix122(1) along the branch of the tree data structure.

As illustrated inFIG.11, at step1130one or more of the systems described herein may determine that the parent prefix and the child prefix share a certain number of most-significant bits in common with one another. For example, determination module106may, as part of network device206inFIG.2, determine that prefixes122(1) and122(N) share a certain number of most-significant bits in common with one another. In one example, the number of most-significant bits in question may correspond to and/or match the length of the parent prefix (e.g., prefix122(1)).

The systems described herein may perform step1130in a variety of ways and/or contexts. In some examples, determination module106may determine and/or discover a length of or number of bits in prefix122(1). In such examples, determination module106may compare prefix122(1) to the most-significant bits in prefix122(N). In one example, determination module106may then determine that prefixes122(1) and122(N) share a certain number of most-significant bits in common with one another based at least in part on the comparison.

As a specific example, prefix122(1) may represent a prefix “1.0.0.4/30”, and prefix122(N) may represent a prefix “1.0.0.6/31”. Converted to binary, prefix “1.0.0.4/30” may correspond to a binary representation “00000001.00000000.00000000.000001XX”, and prefix “1.0.0.6/31” may correspond to a binary representation “00000001.00000000.00000000.0000011X”. In this example, identification module104and/or determination module106may compare binary representation “00000001.00000000.00000000.000001XX” to binary representation “00000001.00000000.00000000.0000011X”. Identification module104and/or determination module106may then determine that the 30 most-significant bits of those prefixes are identical to one another based at least in part on the comparison.

As illustrated inFIG.11, at step1140one or more of the systems described herein may determine that the parent prefix and the child prefix share a forwarding behavior in common with one another. For example, determination module106may, as part of network device206inFIG.2, determine that prefixes122(1) and122(N) share a forwarding behavior in common with one another. In this example, the forwarding behavior in question may direct network device206to forward traffic to a specific next hop. Accordingly, prefixes122(1) and122(N) may both cause network device206to forward traffic to the same next hop. However, other prefixes with a parent-child relationship may cause network device206to forward traffic to different next hops. In other words, not all child prefixes may necessarily lead to the same next hop as their corresponding parent prefixes.

The systems described herein may perform step1140in a variety of ways and/or contexts. In some examples, determination module106may determine whether prefixes122(1) and122(N) lead to the same next hop as one another. For example, identification module104may search and/or examine the routes corresponding to prefixes122(1) and122(N) for addresses (e.g., the IP addresses) assigned to their respective next hops. In this example, during this search and/or examination, identification module104may identify and/or locate the next-hop addresses of those routes and then compare the next-hop addresses with one another. In one example, determination module106may determine that the next-hop addresses identified within the routes corresponding to prefixes122(1) and122(N) are identical to one another. As a result, determination module106may determine that prefixes122(1) and122(N) both cause network device206to forward traffic to the same next hop and thus have the same forwarding behavior.

In another example, identification module104may search and/or examine the routes corresponding to prefixes122(1) and122(N) for outgoing interfaces through which traffic is to egress. In this example, during this search and/or examination, identification module104may identify and/or locate the outgoing interfaces of those routes and then compare the outgoing interfaces addresses with one another. In one example, determination module106may determine that the outgoing interfaces identified within the routes corresponding to prefixes122(1) and122(N) are identical to one another. As a result, determination module106may determine that prefixes122(1) and122(N) both cause network device206to forward traffic to the same next hop and thus have the same forwarding behavior.

As illustrated inFIG.11, at step1150one or more of the systems described herein may compress the table stored on the network device by merging the child prefix with the parent prefix within the table in response to the determination that the parent prefix and the child prefix share the certain number of most-significant bits and the forwarding behavior in common. For example, compression module108may, as part of network device206inFIG.2, compress table120stored on network device206by merging prefix122(N) with prefix122(1) within table120. Accordingly, prefixes122(1) and122(N) may be consolidated into one node that applies to all traffic corresponding to those prefixes, thereby reducing the amount of space needed and/or consumed in table120to accommodate such traffic. Compression module108may initiate the compression and/or merger in response to the determination that prefixes122(1) and122(N) share the certain number of most-significant bits and the forwarding behavior in common with one another.

The systems described herein may perform step1150in a variety of ways and/or contexts. In some examples, compression module108may refuse to install prefix122(N) in table120stored on network device206. For example, a route change may arrive at network device206, and determination module106may determine that the route change involves a certain prefix. Specifically, determination module106may determine that the prefix involved in the route change shares a certain number of most-significant bits with another prefix to which the prefix would be adjacent within table120. In addition, determination module106may determine that the prefix involved in the route change shares a certain forwarding behavior with the other prefix to which the prefix would be adjacent within table120. In response to the determination that these prefixes share the certain number of most-significant bits and the certain forwarding behavior in common with one another, compression module108may refuse to install the prefix involved in the route change within table120stored on network device206, thereby conserving space within table120.

FIG.3illustrates an exemplary implementation of network device206. In one example, a route change302may arrive at network device206. In this example, network device206may include and/or represent a routing engine310and a packet forwarding engine312. Network device206may instantiate and/or implement a table-compression application314in routing engine310and/or packet forwarding engine312. Table-compression application314may simulate table120stored on network device206via compression library124.

In one example, table-compression application314may analyze route change302via compression library124. In this example, table-compression application314may determine that at least one prefix involved in route change302is eligible for compression and/or merger with a would-be parent prefix in table120based at least in part on this analysis. In response to this determination, table-compression application314may refuse to install the prefix involved in route change302within table120due at least in part to the parent prefix already being installed in table120.

In some examples, compression module108may delete prefix122(N) from table120stored on network device206. For example, identification module104may walk the tree data structure in search of any child prefixes that are eligible for merger with corresponding parent prefixes within table120. In this example, the identification module104may identify a child prefix installed beneath a parent prefix within table120. Determination module106may then determine that the child prefix and the parent prefix share a certain number of most-significant bits in common with one another. In addition, determination module106may determine that the child prefix and the parent prefix share a certain forwarding behavior in common with one another. In response to the determination that these prefixes share the certain number of most-significant bits and the certain forwarding behavior in common with one another, compression module108may delete the child prefix from table120, thereby consolidating the child prefix with the parent prefix to reduce the amount of space needed to accommodate traffic with the same next hop.

FIG.4illustrates an exemplary tree structure400in which prefixes122(1)-(N) are organized within table120. As illustrated inFIG.4, tree structure400may include and/or represent a root402that branches into different hierarchies of prefixes. In one example, tree structure400may include and/or represent one branch that incorporates a parent prefix “1.0.0.4/30”. In this example, the parent prefix “1.0.0.4/30” may subsume and/or absorb child prefixes “1.0.0.6/31”, “1.0.0.4/32”, and/or “1.0.0.5/32”. Accordingly, child prefixes “1.0.0.6/31”, “1.0.0.4/32”, and/or “1.0.0.5/32” may be properly represented by parent prefix “1.0.0.4/30” within table120for the purpose of forwarding traffic to the same next hop.

Continuing with this example, tree structure400may include and/or represent another branch that incorporates a singleton prefix “1.0.0.8/31”. In this example, singleton prefix “1.0.0.8/31” may be neither a parent nor a child. For example, singleton prefix “1.0.0.8/31” may not be a parent to either singleton prefix “1.0.0.10/32” or singleton prefix “1.0.0.11/32”. Conversely, neither singleton prefix “1.0.0.10/32” nor singleton prefix “1.0.0.11/32” may be a child to singleton prefix “1.0.0.8/31”. As a result, singleton prefix “1.0.0.8/31” may be unable to subsume and/or absorb singleton prefixes “1.0.0.10/32” and/or “1.0.0.11/32”. Accordingly, singleton prefixes “1.0.0.10/32” and/or “1.0.0.11/32” may not be properly represented by singleton prefix “1.0.0.8/31” within table120for the purpose of forwarding traffic to the same next hop.

FIG.5illustrates exemplary prefix information500that identifies and/or enumerates the binary conversions, relationships, statuses, and next hops for the prefixes represented in tree structure400inFIG.4. As illustrated inFIG.5, prefix information500may indicate and/or show that prefix “1.0.0.4/30” is an installed parent whose binary conversion is “00000001.00000000.00000000.000001XX” and whose next hop is network device212(1). In addition, prefix information500may indicate and/or show that prefix “1.0.0.6/31” is an uninstalled child whose binary conversion is “00000001.00000000.00000000.0000011X” and whose next hop is network device212(1). Moreover, prefix information500may indicate and/or show that prefix “1.0.0.4/32” is an uninstalled child whose binary conversion is “00000001.00000000.00000000.00000100” and whose next hop is network device212(1). Further, prefix information500may indicate and/or show that prefix “1.0.0.5/32” is an uninstalled child whose binary conversion is “00000001.00000000.00000000.00000101” and whose next hop is network device212(1).

As illustrated inFIG.5, prefix information500may also indicate and/or show that prefix “1.0.0.8/31” is an installed singleton whose binary conversion is “00000001.00000000.00000000.0000100X” and whose next hop is network device210(1). In addition, prefix information500may indicate and/or show that prefix “1.0.0.10/32” is an installed singleton whose binary conversion is “00000001.00000000.00000000.00001100” and whose next hop is network device210(1). Further, prefix information500may indicate and/or show that prefix “1.0.0.11/32” is an installed singleton whose binary conversion is “00000001.00000000.00000000.00001101” and whose next hop is network device210(1).

In some examples, identification module104may walk the tree data structure and/or identify a set of prefixes that share one or more characteristics in common with one another. In one example, determination module106may determine that the set of prefixes are eligible for consolidation due at least in part to the characteristics being shared by those prefixes. In response to this determination, installation module110may install a parent prefix that serves as an aggregator for the set of prefixes to handle traffic directed to any of them. In this example, compression module108and/or installation module110may merge the set of prefixes with the parent prefix by deleting the set of prefixes from table120upon installation of the parent prefix.

In some examples, identification module104may identify a further child prefix that corresponds to the aggregator parent prefix. In one example, identification module104may identify an additional characteristic shared by the aggregator parent prefix and the further child prefix. Additionally or alternatively, determination module106may determine that the aggregator parent prefix and the further child prefix may share the original one or more characteristics in common with one another. Either way, determination module106may determine that the aggregator parent prefix and the further child prefix are eligible for further consolidation due at least in part to the additional characteristic and/or the original characteristics being shared by those prefixes. In response to this determination, installation module110may install an additional parent prefix that serves as an additional aggregator for the original aggregator parent prefix and the further child prefix to handle corresponding traffic. In this example, compression module108and/or installation module110may merge the original aggregator parent prefix and the further child prefix by deleting the original aggregator parent prefix and the further child prefix from table120upon installation of the additional parent prefix.

FIGS.6-9illustrates an exemplary tree structure600in which prefixes122(1)-(N) are organized within table120. As illustrated inFIGS.6-9, tree structure600may include and/or represent a root602that branches into different subsets of prefixes. In one example, tree structure600inFIG.6may include and/or represent one branch that incorporates prefixes “1.0.0.4/32” and/or “1.0.0.5/32”. In this example, tree structure600inFIG.6may include and/or represent another branch that incorporates prefixes “1.0.0.10/32” and/or “1.0.0.11/32”.

As a specific example, identification module104may walk tree structure600along one branch and/or identify prefixes “1.0.0.4/32” and “1.0.0.5/32” as sharing the 31 most-significant bits in common with one another. In this example, determination module106may determine that prefixes “1.0.0.4/32” and “1.0.0.5/32” are eligible for consolidation due at least in part to them sharing the 31 most-significant bits in common with one another. In response to this determination, installation module110may install a parent prefix “1.0.0.4/31” into tree structure600inFIG.7. As illustrated inFIG.7, parent prefix “1.0.0.4/31” may serve as an aggregator for prefixes “1.0.0.4/32” and “1.0.0.5/32” to handle traffic directed to either of prefixes “1.0.0.4/32” and “1.0.0.5/32”. Compression module108and/or installation module110may then merge prefixes “1.0.0.4/32” and “1.0.0.5/32” with parent prefix “1.0.0.4/31” by deleting prefixes “1.0.0.4/32” and “1.0.0.5/32” from table120upon installation of the parent prefix.

In another example, identification module104may walk tree structure600along another branch and/or identify prefixes “1.0.0.10/32” and “1.0.0.11/32” as sharing the 31 most-significant bits in common with one another. In this example, determination module106may determine that prefixes “1.0.0.10/32” and “1.0.0.11/32” are eligible for consolidation due at least in part to them sharing the 31 most-significant bits in common with one another. In response to this determination, installation module110may install a parent prefix “1.0.0.10/31” into tree structure600inFIG.7. As illustrated inFIG.7, parent prefix “1.0.0.10/31” may serve as an aggregator for prefixes “1.0.0.10/32” and “1.0.0.11/32” to handle traffic directed to either of prefixes “1.0.0.10/32” and “1.0.0.11/32”. Compression module108and/or installation module110may then merge prefixes “1.0.0.10/32” and “1.0.0.11/32” with parent prefix “1.0.0.10/31” by deleting prefixes “1.0.0.10/32” and “1.0.0.11/32” from table120upon installation of the parent prefix.

As illustrated inFIG.8, installation module110may subsequently install prefixes “1.0.0.6/31” and “1.0.0.8/31” above prefixes “1.0.0.4/31” and “1.0.0.10/31”, respectively, toward root602in tree structure600. In one example, identification module104may walk tree structure600along one branch and/or identify prefixes “1.0.0.4/31” and “1.0.0.6/31” as sharing the 30 most-significant bits in common with one another. In this example, determination module106may determine that prefixes “1.0.0.4/31” and “1.0.0.6/31” are eligible for consolidation due at least in part to them sharing the 30 most-significant bits in common with one another. In response to this determination, installation module110may devise and install an additional parent prefix “1.0.0.4/30” into tree structure600inFIG.9. As illustrated inFIG.9, additional parent prefix “1.0.0.4/30” may serve as an aggregator for prefixes “1.0.0.4/31” and “1.0.0.6/31” to handle traffic directed to any of prefixes “1.0.0.4/32”, “1.0.0.5/32”, “1.0.0.4/31”, and “1.0.0.6/31”. Compression module108and/or installation module110may then merge prefixes “1.0.0.4/31” and “1.0.0.6/31” with additional parent prefix “1.0.0.4/30” by deleting prefixes “1.0.0.4/31” and “1.0.0.6/31” from table120upon installation of the additional parent prefix.

In another example, identification module104may walk tree structure600along another branch and/or identify prefixes “1.0.0.8/31” and “1.0.0.10/31” as sharing the 30 most-significant bits in common with one another. In this example, determination module106may determine that prefixes “1.0.0.8/31” and “1.0.0.10/31” are eligible for consolidation due at least in part to them sharing the 30 most-significant bits in common with one another. In response to this determination, installation module110may devise and install an additional parent prefix “1.0.0.8/30” into tree structure600inFIG.9. As illustrated inFIG.9, additional parent prefix “1.0.0.8/30” may serve as an aggregator for prefixes “1.0.0.8/31” and “1.0.0.10/31” to handle traffic directed to any of prefixes “1.0.0.10/32”, “1.0.0.11/32”, “1.0.0.10/31”, and “1.0.0.8/31”. Compression module108and/or installation module110may then merge prefixes “1.0.0.10/31” and “1.0.0.8/31” with additional parent prefix “1.0.0.8/30” by deleting prefixes “1.0.0.10/31” and “1.0.0.8/31” from table120upon installation of the additional parent prefix.

FIG.10illustrates exemplary prefix information1000that identifies and/or enumerates the binary conversions, relationships, statuses, and next hops for the prefixes represented in tree structure600inFIGS.6-9. As illustrated inFIG.10, prefix information1000may indicate and/or show that prefix “1.0.0.4/30” is an installed parent whose binary conversion is “00000001.00000000.00000000.000001XX” and whose next hop is network device212(1). In addition, prefix information1000may indicate and/or show that prefix “1.0.0.6/31” is an uninstalled child whose binary conversion is “00000001.00000000.00000000.0000011X” and whose next hop is network device212(1). Moreover, prefix information1000may indicate and/or show that prefix “1.0.0.4/31” is an uninstalled child whose binary conversion is “00000001.00000000.00000000.0000010X” and whose next hop is network device212(1). Prefix information1000may also indicate and/or show that prefix “1.0.0.4/32” is an uninstalled child whose binary conversion is “00000001.00000000.00000000.00000100” and whose next hop is network device212(1). Additionally, prefix information500may indicate and/or show that prefix “1.0.0.5/32” is an uninstalled child whose binary conversion is “00000001.00000000.00000000.00000101” and whose next hop is network device212(1).

As illustrated inFIG.10, prefix information1000may further indicate and/or show that prefix “1.0.0.8/30” is an installed parent whose binary conversion is “00000001.00000000.00000000.000010XX” and whose next hop is network device210(1). In addition, prefix information1000may indicate and/or show that prefix “1.0.0.8/31” is an uninstalled child whose binary conversion is “00000001.00000000.00000000.0000100X” and whose next hop is network device210(1). Further, prefix information1000may indicate and/or show that prefix “1.0.0.10/31” is an uninstalled child whose binary conversion is “00000001.00000000.00000000.0000101X” and whose next hop is network device210(1). Moreover, prefix information1000may indicate and/or show that prefix “1.0.0.10/32” is an uninstalled child whose binary conversion is “00000001.00000000.00000000.00001010” and whose next hop is network device210(1). Finally, prefix information1000may indicate and/or show that prefix “1.0.0.11/32” is an uninstalled child whose binary conversion is “00000001.00000000.00000000.00001011” and whose next hop is network device210(1).

In some examples, compression module108may limit and/or mitigate route churns by applying a distance limit that prevents consolidations and/or mergers of any parent and child prefixes separated from one another beyond a certain distance. In one example, identification module104may identify a child prefix that corresponds to a parent prefix within table120. In this example, determination module106may determine that the parent prefix and the child prefix share a certain number of most-significant bits in common with one another. In addition, determination module106may determine that the parent prefix and the child prefix share a certain forwarding behavior in common with one another. However, determination module106may also determine that the parent prefix and the child prefix are separated from one another by the certain distance or more.

In response to the determination that the parent prefix and the child prefix are separated from one another by the certain distance or more, compression module108and/or installation module110may refuse to merge the child prefix with the parent prefix even though the parent prefix and the child prefix share the certain number of most-significant bits and the certain forwarding behavior in common within one another. By applying the distance limit in this way, compression module108and/or installation module110may ensure that a single route change does not cause and/or trigger an excessive number of hardware or memory writes in connection with table compression and/or prefix mergers.

FIG.12is a block diagram of an exemplary computing system1200capable of implementing and/or being used in connection with one or more of the embodiments described and/or illustrated herein. In some embodiments, all or a portion of computing system1200may perform and/or be a means for performing, either alone or in combination with other elements, one or more of the steps described in connection withFIG.3. All or a portion of computing system1200may also perform and/or be a means for performing and/or implementing any other steps, methods, or processes described and/or illustrated herein.

Computing system1200broadly represents any type or form of electrical load, including a single or multi-processor computing device or system capable of executing computer-readable instructions. Examples of computing system1200include, without limitation, workstations, laptops, client-side terminals, servers, distributed computing systems, mobile devices, network switches, network routers (e.g., backbone routers, edge routers, core routers, mobile service routers, broadband routers, etc.), network appliances (e.g., network security appliances, network control appliances, network timing appliances, SSL VPN (Secure Sockets Layer Virtual Private Network) appliances, etc.), network controllers, gateways (e.g., service gateways, mobile packet gateways, multi-access gateways, security gateways, etc.), and/or any other type or form of computing system or device.

Computing system1200may be programmed, configured, and/or otherwise designed to comply with one or more networking protocols. According to certain embodiments, computing system1200may be designed to work with protocols of one or more layers of the Open Systems Interconnection (OSI) reference model, such as a physical layer protocol, a link layer protocol, a network layer protocol, a transport layer protocol, a session layer protocol, a presentation layer protocol, and/or an application layer protocol. For example, computing system1200may include a network device configured according to a Universal Serial Bus (USB) protocol, an Institute of Electrical and Electronics Engineers (IEEE) 1394 protocol, an Ethernet protocol, a T1 protocol, a Synchronous Optical Networking (SONET) protocol, a Synchronous Digital Hierarchy (SDH) protocol, an Integrated Services Digital Network (ISDN) protocol, an Asynchronous Transfer Mode (ATM) protocol, a Point-to-Point Protocol (PPP), a Point-to-Point Protocol over Ethernet (PPPoE), a Point-to-Point Protocol over ATM (PPPoA), a Bluetooth protocol, an IEEE 802.XX protocol, a frame relay protocol, a token ring protocol, a spanning tree protocol, and/or any other suitable protocol.

Computing system1200may include various network and/or computing components. For example, computing system1200may include at least one processor1214and a system memory1216. Processor1214generally represents any type or form of processing unit capable of processing data or interpreting and executing instructions. For example, processor1214may represent an ASIC, a system on a chip (e.g., a network processor), a hardware accelerator, a general purpose processor, and/or any other suitable processing element.

Processor1214may process data according to one or more of the networking protocols discussed above. For example, processor1214may execute or implement a portion of a protocol stack, may process packets, may perform memory operations (e.g., queuing packets for later processing), may execute end-user applications, and/or may perform any other processing tasks.

System memory1216generally represents any type or form of volatile or non-volatile storage device or medium capable of storing data and/or other computer-readable instructions. Examples of system memory1216include, without limitation, Random Access Memory (RAM), Read Only Memory (ROM), flash memory, or any other suitable memory device. Although not required, in certain embodiments computing system1200may include both a volatile memory unit (such as, for example, system memory1216) and a non-volatile storage device (such as, for example, primary storage device1232, as described in detail below). System memory1216may be implemented as shared memory and/or distributed memory in a network device. Furthermore, system memory1216may store packets and/or other information used in networking operations.

In certain embodiments, exemplary computing system1200may also include one or more components or elements in addition to processor1214and system memory1216. For example, as illustrated inFIG.12, computing system1200may include a memory controller1218, an Input/Output (I/O) controller1220, and a communication interface1222, each of which may be interconnected via communication infrastructure1212. Communication infrastructure1212generally represents any type or form of infrastructure capable of facilitating communication between one or more components of a computing device. Examples of communication infrastructure1212include, without limitation, a communication bus (such as a Serial ATA (SATA), an Industry Standard Architecture (ISA), a Peripheral Component Interconnect (PCI), a PCI Express (PCIe), and/or any other suitable bus), and a network.

Memory controller1218generally represents any type or form of device capable of handling memory or data or controlling communication between one or more components of computing system1200. For example, in certain embodiments memory controller1218may control communication between processor1214, system memory1216, and I/O controller1220via communication infrastructure1212. In some embodiments, memory controller1218may include a Direct Memory Access (DMA) unit that may transfer data (e.g., packets) to or from a link adapter.

I/O controller1220generally represents any type or form of device or module capable of coordinating and/or controlling the input and output functions of a computing device. For example, in certain embodiments I/O controller1220may control or facilitate transfer of data between one or more elements of computing system1200, such as processor1214, system memory1216, communication interface1222, and storage interface1230.

Communication interface1222broadly represents any type or form of communication device or adapter capable of facilitating communication between exemplary computing system1200and one or more additional devices. For example, in certain embodiments communication interface1222may facilitate communication between computing system1200and a private or public network including additional computing systems. Examples of communication interface1222include, without limitation, a link adapter, a wired network interface (such as a network interface card), a wireless network interface (such as a wireless network interface card), and any other suitable interface. In at least one embodiment, communication interface1222may provide a direct connection to a remote server via a direct link to a network, such as the Internet. Communication interface1222may also indirectly provide such a connection through, for example, a local area network (such as an Ethernet network), a personal area network, a wide area network, a private network (e.g., a virtual private network), a telephone or cable network, a cellular telephone connection, a satellite data connection, or any other suitable connection.

In certain embodiments, communication interface1222may also represent a host adapter configured to facilitate communication between computing system1200and one or more additional network or storage devices via an external bus or communications channel. Examples of host adapters include, without limitation, Small Computer System Interface (SCSI) host adapters, Universal Serial Bus (USB) host adapters, IEEE 1394 host adapters, Advanced Technology Attachment (ATA), Parallel ATA (PATA), Serial ATA (SATA), and External SATA (eSATA) host adapters, Fibre Channel interface adapters, Ethernet adapters, or the like. Communication interface1222may also enable computing system1200to engage in distributed or remote computing. For example, communication interface1222may receive instructions from a remote device or send instructions to a remote device for execution.

As illustrated inFIG.12, exemplary computing system1200may also include a primary storage device1232and/or a backup storage device1234coupled to communication infrastructure1212via a storage interface1230. Storage devices1232and1234generally represent any type or form of storage device or medium capable of storing data and/or other computer-readable instructions. For example, storage devices1232and1234may represent a magnetic disk drive (e.g., a so-called hard drive), a solid state drive, a floppy disk drive, a magnetic tape drive, an optical disk drive, a flash drive, or the like. Storage interface1230generally represents any type or form of interface or device for transferring data between storage devices1232and1234and other components of computing system1200.

In certain embodiments, storage devices1232and1234may be configured to read from and/or write to a removable storage unit configured to store computer software, data, or other computer-readable information. Examples of suitable removable storage units include, without limitation, a floppy disk, a magnetic tape, an optical disk, a flash memory device, or the like. Storage devices1232and1234may also include other similar structures or devices for allowing computer software, data, or other computer-readable instructions to be loaded into computing system1200. For example, storage devices1232and1234may be configured to read and write software, data, or other computer-readable information. Storage devices1232and1234may be a part of computing system1200or may be separate devices accessed through other interface systems.

In some examples, all or a portion of system100inFIG.1may represent portions of a cloud-computing or network-based environment. Cloud-computing and network-based environments may provide various services and applications via the Internet. These cloud-computing and network-based services (e.g., software as a service, platform as a service, infrastructure as a service, etc.) may be accessible through a web browser or other remote interface. Various functions described herein may also provide network switching capabilities, gateway access capabilities, network security functions, content caching and delivery services for a network, network control services, and/or and other networking functionality.