Patent Description:
An IGP is a type of protocol used for exchanging information among network elements (NEs), such as routers, switches, gateways, etc., within a network (also referred to herein as an "autonomous system (AS)" or a "domain"). This information exchanged using IGP may include routing information and/or state information. The information can be used to route data using network-layer protocols, such as Internet Protocol (IP).

IGPs can be divided into two categories: distance-vector routing protocols and link-state routing protocols. In a network implementing a distance-vector routing protocol, each NE in the network does not possess information about the full network topology. Instead, each NE advertises a distance value calculated to other routers and receives similar advertisements from other routers. Each NE in the network uses the advertisements to populate a local routing table.

In contrast, in a network implementing a link-state routing protocol, each NE stores network topology information about the complete network topology. Each NE then independently calculates the next best hop from the NE for every possible destination in the network using the network topology information. The NE then stores a routing table including the collection of next best hops to every possible destination. Examples of link-state routing protocols include Intermediate System to Intermediate System (IS-IS), Open Shortest Path First (OSPF) version <NUM> (OSPFv2), and OSPF version <NUM> (OSPFv3).

Each NE in the network forwards the information encoded according to an IGP to adjacent NEs, thereby flooding the network with the information that is saved at each of the NEs in the network. Therefore, NEs in a network implementing an IGP flood the network with messages that transmit information that can be used to establish a route or a network topology. <CIT> discloses a method for opportunistic compression of routing segment identifiers, including participating in routing of a first data packet through a first node in a network. The first data packet includes a first plurality of routing segment identifiers. The arrangement entered into includes representation of the first plurality of routing segment identifiers by a single compression identifier.

The disclosure should in no way be limited to the illustrative implementations, drawings, and techniques illustrated below, including the exemplary designs and implementations illustrated and described herein, but may be modified within the scope of the appended claims, which is the one defining the present invention.

<FIG> is a diagram illustrating a network <NUM> (also referred to herein as an "AS" or "domain") configured to transmit compressed messages using an IGP according to various embodiments of the disclosure. Network <NUM> is a network or subnetwork configured to implement an IGP, such as IS-IS, OSPFv2, or OSPFv3, according to various embodiments of the disclosure. The network <NUM> comprises a central entity <NUM> (also referred to herein as a "controller") and multiple NEs <NUM>-<NUM>. The central entity <NUM> is coupled to at least one of the NEs <NUM> via a link <NUM>, and the NEs <NUM>-<NUM> are interconnected by links <NUM>.

In an embodiment, the central entity <NUM> may be substantially similar to a Path Computation Element (PCE), which is further described in <NPL>. In an embodiment, the central entity <NUM> may be substantially similar to Software Defined Network Controller (SDNC), which is further described in the <NPL>. In an embodiment, the central entity <NUM> may be substantially similar to an Application Layer Traffic Optimization (ALTO) server, which is further described in the <NPL>.

NEs <NUM>-<NUM> (also referred to herein as "nodes") may each be a physical device, such as a router, a bridge, a network switch, or a logical device, such as a virtual machine, configured to forward data across the network <NUM> by encoding the data according to IGP. In an embodiment, at least some of the NEs <NUM>-<NUM> are headend nodes or edge nodes positioned at an edge of the network <NUM>. For example, one or more of NEs <NUM>-<NUM> may be an ingress node at which traffic (e.g., control packets and data packets) is received, and one or more of NEs <NUM>-<NUM> may be an egress node from which traffic is transmitted. Some of the NEs <NUM>-<NUM>, such as <NUM> and <NUM>, may be interior nodes that are configured to receive and forward traffic from another NE <NUM>-<NUM> in the network <NUM>.

The link <NUM> may be a wired link, wireless link, or interface interconnecting one of the NEs <NUM> and the central entity <NUM>. Similarly, the links <NUM> may be wired links, wireless links, or interfaces interconnecting each of the NEs <NUM>-<NUM>.

Although only nine NEs <NUM>-<NUM> are shown in <FIG>, it should be appreciated that the network <NUM> shown in <FIG> may include any number of NEs. In an embodiment, the central entity <NUM> and NEs <NUM>-<NUM> are configured to implement various packet forwarding protocols, such as, but not limited to, Multi-protocol Label Switching (MPLS), IP version <NUM> (IPv4), IP version <NUM> (IPv6), and Big Packet Protocol.

Each of the NEs <NUM>-<NUM> in the network <NUM> maintains one or more link state databases (LSDBs) storing link-state information about NEs <NUM>-<NUM> and links <NUM> in any given area or network. Link attributes stored in these LSDBs include local/remote IP address, local/remote interface identifiers, link metrics and traffic engineering (TE) metrics, link bandwidth, reserveable bandwidth, per Class-of-Service (CoS) class reservation state, preemption, and Shared Risk Link Groups (SLRGs). Each of the NEs <NUM>-<NUM> may retrieve topology information from the locally stored LSDBs and distribute the topology information to a consumer or central entity <NUM>.

The central entity <NUM> may determine the network topology using the advertisements sent by each of the NEs <NUM>-<NUM> in the network <NUM>, where the advertisements may include prefixes, security identifiers (SIDs), TE information, identifiers (IDs) of adjacent NEs, links, interfaces, ports, and routes. The central entity <NUM> is configured to collect TE information and link-state information from NEs <NUM>-<NUM> within the network <NUM>.

In some embodiments, the central entity <NUM> is configured to determine or construct paths between two NEs <NUM>-<NUM> positioned at edges of the network <NUM> using a network topology of the network <NUM> and capabilities of NEs <NUM>-<NUM> within network <NUM>. In an embodiment in which the network <NUM> implements preferred path routing, the central entity <NUM> is configured to determine a shortest path between the two NEs <NUM>-<NUM>, one or more preferred path routes (PPRs) between the two NEs <NUM>-<NUM>, and/or one or more PPR graphs between the two NEs <NUM>-<NUM>.

A shortest path refers to a path between two NEs or between a source and destination that is determined based on a metric, such as, for example, a cost or weight associated with each link on the path, a number of NEs on the path, a number of links on the path, etc. In an embodiment, a shortest path may be computed for a destination using a Dijkstra's Shortest Path First (SPF) algorithm. A PPR (also referred to herein as a "Non-Shortest Path (NSP)") refers to a custom path or any other path that may deviate from the shortest path computed between two NEs or between a source and destination. A PPR may also be the same as the shortest path. The PPRs may be determined based on an application or server request for a path between two NEs <NUM>-<NUM> or between a source and destination that satisfies one or more network characteristics (such as TE) or service requirements. PPRs are further defined in International Application No. <CIT>. A PPR graph refers to a collection of multiple PPRs between one or more ingress NEs <NUM>-<NUM> (also referred to herein as "sources") and one or more egress NEs <NUM>-<NUM> (also referred to herein as "destinations"). PPR graphs are further defined in International Application No. <CIT>. The shortest path, PPR, and PPR graphs may each comprise a sequential ordering of one or more NEs <NUM>-<NUM> and/or links <NUM>, which may be identified by labels, addresses, or IDs.

Upon determining a shortest path, PPR, and/or PPR graph that is to be provisioned by the NEs <NUM>-<NUM> in the network, the central entity <NUM> transmits information describing the shortest path, PPR, and/or PPR graph to one of the NEs <NUM> via the link <NUM>. In some cases, the central entity <NUM> may also transmit information describing the topology information of the network <NUM> to one of the NEs <NUM> via link <NUM>.

In either case, when the NE <NUM> receives information from the central entity <NUM>, or any other source or client, the NE <NUM> encodes the information using the IGP to transmit the information to the remaining NEs <NUM> and <NUM>-<NUM> in the network. For example, after NE <NUM> receives the information from the central entity <NUM>, or any other source or client, NE <NUM> stores the information locally, encodes the information into a message according to the IGP implemented by the network <NUM> (e.g., IS-IS, OSPFv2, or OSPFv3), and transmits the information to neighboring NEs <NUM> and <NUM>. Subsequently, NE <NUM> stores the information locally and forwards the information to neighboring NE <NUM>, and NE <NUM> stores the information locally and forwards the information to neighboring NEs <NUM> and <NUM>. NEs <NUM>, <NUM>, and <NUM> each similarly store the information and forward the information to the neighboring NEs <NUM>-<NUM>, and so on. In this manner, after NE <NUM> receives the information, the information is encoded according to the IGP and flooded to all the NEs <NUM>-<NUM> in the network <NUM>.

The overall amount of information that needs to be flooded through a network <NUM> using the IGP is continuously growing, which results in an inefficient use of the resources within a network <NUM>. In addition, network characteristics, such as bandwidth, throughput, latency, error rate, etc., can be significantly affected when large amounts of data are flooded through the network <NUM> using the IGP. For example, networks <NUM> that implement PPR graphs may forward PPR graph type-length-values (TLVs) that describe each of the PPRs in a PPR graph to every single NE <NUM>-<NUM> in the network <NUM>. In addition, the encoding of the PPR graph includes PPR-Path Description Elements (PPR-PDEs) for each element on each of the PPRs, which typically carries a large amount of data.

However, certain IGPs impose limits as to how much data can be transmitted in a single message or TLV. For example, when the network <NUM> implements IS-IS as the IGP, the link state information is advertised across the network <NUM> using a link state packet (LSP), which contains various types of TLVs used to carry different types of link or node related information. Each TLV in an LSP is limited to <NUM> bytes (<NUM> octet). Additional information regarding IS-IS is described in the Network Working Group RFC <NUM>, entitled "Use of OSI IS-IS for Routing in TCP/IP and Dual Environments," dated December <NUM>, by R.

Similarly, when the network <NUM> implements OSPFv2 or OSPFv3, link state information is advertised across the network <NUM> using various types of LSAs, each of which may carry various TLVs. Each TLV in an LSA may be limited to <NUM>,<NUM> bytes (<NUM> octets). Additional information regarding OSPFv2 is described in the <NPL>. Additional information regarding OSPFv3 is described in the <NPL>. Therefore, the management of data transmission through a network using an IGP is becoming increasingly difficult.

Disclosed herein are embodiments directed to an enhanced protocol for compressing data that is forwarded through the network using an IGP. In an embodiment, each of the NEs <NUM>-<NUM> receives a message comprising a header and data that is to be compressed. The header includes a length of the data prior to compressing the data, a length of the data after compressing the data, and a compression identifier. The NE <NUM>-<NUM> receiving the message is configured to compress the data based on a compression scheme identified by the compression identifier to obtain compressed data. The NE <NUM>-<NUM> then forwards a compressed message including the header and the compressed data to other NEs <NUM>-<NUM> in the network <NUM>.

In some embodiments, the network <NUM> is configured to implement either a stateless compression scheme or a stateful compression scheme. In a stateless compression scheme, each of the NEs <NUM>-<NUM> is configured to compress the data based on the compression identifier carried in the header of the message, without regard to any data that has been previously transmitted through the network. In this embodiment, instructions corresponding to various different compression schemes are pre-configured or already stored at each of the NEs <NUM>-<NUM>. When the message is received by the NE <NUM>-<NUM>, the NE <NUM>-<NUM> automatically executes the instructions corresponding to the compression scheme identified by the compression identifier in the message to compress the data in the message and generate a compressed message. The NE <NUM>-<NUM> forwards the compressed message to neighboring NEs <NUM>-<NUM> based on the underlying IGP implemented by the network.

In a stateful compression scheme, one or more of the NEs <NUM>-<NUM> is designated as a compression controller of the network <NUM>. For example, as shown by <FIG>, NE <NUM> (shown with a box) can be designated as the compression controller (hereinafter referred to as the "compression controller <NUM>") of the network <NUM>. In one embodiment, multiple candidate compression controllers may transmit an advertisement describing the respective candidate compression controller through the network <NUM>. A candidate compression controller may be pre-configured by an operator of the network <NUM> or determined based on pre-configured information at each of the NEs <NUM>-<NUM>. For example, when NEs <NUM> and <NUM> are the candidate compression controllers for the network <NUM>, NEs <NUM> and <NUM> flood the network <NUM> with an advertisement carrying information describing the respective NE <NUM> and NE <NUM>. The advertisement describing NE <NUM> may carry, for example, an IP address of NE <NUM> and/or a pre-configured priority of NE <NUM>. Similarly, the advertisement describing NE <NUM> may carry, for example, an IP address of NE <NUM> and/or a pre-configured priority of NE <NUM>.

After all the NEs <NUM>-<NUM> in the network <NUM> receive the advertisements for NEs <NUM> and <NUM>, each of the NEs <NUM>-<NUM> may automatically determine the compression controller <NUM> based on the information carried in the advertisement. For example, each of the NEs <NUM>-<NUM> are pre-configured to select the candidate compression controller having the highest IP address or the highest priority as the compression controller <NUM> for the network <NUM>. In this case, when NE <NUM> has the highest IP address among the other candidate compression controllers, each of the other NEs <NUM>-<NUM> in the network <NUM> determines that the NE <NUM> is the compression controller <NUM> of the network <NUM>. When NE <NUM> has the highest pre-configured priority among the other candidate compression controllers, each of the other NEs <NUM>-<NUM> in the network <NUM> determines that the NE <NUM> is the compression controller <NUM> of the network <NUM>.

In an embodiment, the compression controller <NUM> monitors uncompressed messages that are being forwarded through the network <NUM> to determine one or more dictionaries that are to be used to compress data forwarded through the network <NUM>. For example, the compression controller <NUM> monitors the uncompressed messages that are being forward through the network <NUM> to determine that <NUM>% of the traffic being forwarded carries an IPv6 address having the same <NUM>-bit prefix. In this case, the compression controller <NUM> determines that the <NUM>-bit prefix is an uncompressed bit string that can be compressed into a codeword, which may be <NUM> bits or less. The compression controller <NUM> generates and stores a dictionary that includes a mapping of the uncompressed bit string (<NUM>-bit prefix) to the codeword.

In an embodiment, the compression controller <NUM> may identify multiple uncompressed bit strings that have a high rate of occurrence in the traffic that is being forwarded through the network <NUM>. In these embodiments, the compression controller <NUM> determines a codeword for each of the uncompressed bit strings that have a high rate of occurrence in the traffic. The compression controller <NUM> then adds a mapping between the uncompressed bit string and the codeword to the dictionary.

In an embodiment, the compression controller <NUM> generates and stores multiple different dictionaries. In each of the different dictionaries, the same uncompressed bit string may be mapped to different codewords or the same codeword. Each of the different dictionaries stores one or more mappings associating an uncompressed bit string with a corresponding codeword.

In an embodiment, the compression controller <NUM> determines and stores a dictionary identifier identifying the dictionary. Each dictionary may be associated with a unique dictionary identifier. The dictionary identifier may be an alphanumeric value or bit string uniquely identifying the dictionary.

After generating and storing the dictionary and the dictionary identifier, the compression controller <NUM> forwards the dictionary and the dictionary identifier through the network <NUM>. As described above, the compression controller <NUM> forwards the dictionary and the dictionary identifier to neighboring NEs <NUM> and <NUM>, NEs <NUM> and <NUM> forward the dictionary and the dictionary identifier to neighboring NEs <NUM>, <NUM>, and <NUM>, and so on.

Each of the receiving NEs <NUM>-<NUM> stores the dictionary and dictionary identifier locally in a memory of the receiving NE <NUM>-<NUM> for use in compressing data at a subsequent time. In an embodiment, each of the receiving NEs <NUM>-<NUM> waits a predetermined buffer time before beginning to compress data based on the dictionary and dictionary identifier. This predetermined buffer time helps ensure that all the other NEs <NUM>-<NUM> have stored the dictionary and dictionary identifier before the NEs <NUM>-<NUM> begin compressing data based on the dictionary and dictionary identifier.

Subsequently, one of the NEs <NUM>-<NUM> may receive a message, either from the central entity <NUM> or an external client, including information that is to be flooded through the network <NUM>. In an embodiment, the message may include a header that includes the dictionary identifier identifying the dictionary to be used to compress data in the message. In this embodiment, the NE <NUM>-<NUM> compresses the data in the message using the dictionary by replacing the uncompressed bit strings in the data with the corresponding codeword defined by the mappings in the dictionary to obtain compressed data. After which the NE <NUM>-<NUM> forwards a compressed message including the compressed data through the network <NUM>.

In an embodiment, the message received by the NE <NUM>-<NUM> does not include the header but only includes the data to be compressed. In this case, the NE <NUM>-<NUM> may determine a dictionary to use for compressing the data based on the mappings in the dictionary. In an embodiment, NE <NUM>-<NUM> scans the data in the message to determine a number of uncompressed bit strings that match the uncompressed bit strings stored in each of the dictionaries. NE <NUM>-<NUM> determines a dictionary having a highest number of matching uncompressed bit strings identified in the message. In another embodiment, NEs <NUM>-<NUM> may be configured to use certain dictionaries for messages carrying different types of data or different TLVs. In another embodiment, NEs <NUM>-<NUM> may be configured to use a dictionary by default for all messages that are received that do not include a dictionary identifier.

After determining a dictionary to use for the message that does not include a header, the NE <NUM>-<NUM> adds a header to the message, in which the header carries a dictionary identifier corresponding to the dictionary that was determined for the message. In an embodiment, the header also carries a length of the data prior to compressing the data, a length of the data after compression, a type of the data, and/or any other information describing the message before and/or after compression.

Once the header has been added to the message, the NE <NUM>-<NUM> compresses the message based on the dictionary that has been determined for the message. The NE <NUM>-<NUM> compresses the data in the message using the dictionary by replacing the uncompressed bit strings in the data with the corresponding codeword defined by the mappings in the dictionary to obtain compressed data. The NE <NUM>-<NUM> creates a compressed message, in which the compressed message includes the header and the compressed data. The NE <NUM>-<NUM> transmits the compressed message to the neighboring NEs <NUM>-<NUM> to flood the network <NUM> with the compressed message.

Another NE <NUM>-<NUM> receiving the compressed message may decompress the message based on the dictionary identifier carried in the header of the compressed message. The NE <NUM>-<NUM> receiving the message has the dictionary identifier and the dictionary stored locally in a memory of the NE <NUM>-<NUM>. The NE <NUM>-<NUM> uses the locally stored dictionary corresponding to the dictionary identifier to determine the uncompressed bit strings corresponding to the codewords included in the compressed data to decompress the compressed data and obtain the data.

After performing decompression on the compressed data to obtain the data, the NE <NUM>-<NUM> may validate the data by determining that the length of the data after decompression matches the length of the data prior to compression, both of which included in the header of the message. If the length of the data after decompression does not match the length of the data prior to compression, the NE <NUM>-<NUM> may discard the message. If the length of the data after decompression matches the length of the data prior to compression, the NE <NUM>-<NUM> updates a local forwarding table and/or the LSDB to include the data carried in the message before continuing to forward the compressed message through the network <NUM>.

The embodiments disclosed herein are advantageous in that the network overhead can be significantly reduced by compressing the data that is to be forwarded through the network <NUM> and saved at every single NE <NUM>-<NUM> in the network <NUM>. For example, by compressing the data and reducing the amount of data transmitted through the network <NUM>, the network <NUM> inherently will have more bandwidth by which to transmit additional data, and throughput of the network <NUM> can be significantly increased. In addition, latency can be reduced due to the higher availability of network resources within the network <NUM>. In addition, the delay occurring between receiving packets/messages at a line card of each of the NEs <NUM>-<NUM> and being processed at the socket at each of the NEs <NUM>-<NUM> can also be greatly reduced by compressing the data. Accordingly, the embodiments disclosed herein enhance the IGP to provide a more efficient and resource effective manner by which to flood the network <NUM> with necessary information.

<FIG> is a schematic diagram of an NE <NUM> suitable for compressing data to be encoded using IGP according to various embodiments of the disclosure. In an embodiment, the NE <NUM> may be implemented as any one of NEs <NUM>-<NUM> or the central entity <NUM>.

The NE <NUM> comprises ports <NUM>, transceiver units (Tx/Rx) <NUM>, a processor <NUM>, and a memory <NUM>. The processor <NUM> comprises a compression module <NUM>. Ports <NUM> are coupled to Tx/Rx <NUM>, which may be transmitters, receivers, or combinations thereof. The Tx/Rx <NUM> may transmit and receive data via the ports <NUM>. Processor <NUM> is configured to process data. Memory <NUM> is configured to store data and instructions for implementing embodiments described herein. The NE <NUM> may also comprise electrical-to-optical (EO) components and optical-to-electrical (OE) components coupled to the ports <NUM> and Tx/Rx <NUM> for receiving and transmitting electrical signals and optical signals.

The processor <NUM> may be implemented by hardware and software. The processor <NUM> may be implemented as one or more central processing unit (CPU) and/or graphics processing unit (GPU) chips, logic units, cores (e.g., as a multi-core processor), field-programmable gate arrays (FPGAs), application specific integrated circuits (ASICs), and digital signal processors (DSPs). The processor <NUM> is in communication with the ports <NUM>, Tx/Rx <NUM>, and memory <NUM>. The compression module <NUM> is implemented by the processor <NUM> to execute the instructions for implementing various embodiments discussed herein. For example, the compression module <NUM> is configured to create a dictionary for use in compressing data to be encoded using an IGP and forwarded through the network <NUM>. The compression module <NUM> is also configured to compress data according to a compression identifier and/or a dictionary and decompress the data according to the compression identifier and/or the dictionary. The inclusion of the compression module <NUM> provides an improvement to the functionality of the NE <NUM>. The compression module <NUM> also effects a transformation of NE <NUM> to a different state. Alternatively, the compression module <NUM> is implemented as instructions stored in the memory <NUM>.

The memory <NUM> comprises one or more of disks, tape drives, or solid-state drives and may be used as an over-flow data storage device, to store programs when such programs are selected for execution, and to store instructions and data that are read during program execution. The memory <NUM> may be volatile and non-volatile and may be read-only memory (ROM), random-access memory (RAM), ternary content-addressable memory (TCAM), and static random-access memory (SRAM).

In an embodiment, the memory <NUM> is configured to store a compression identifier <NUM>, dictionary identifier <NUM>, dictionary <NUM>, LSDB <NUM>, forwarding database <NUM>, and/or instructions <NUM> for compression schemes. The compression identifier <NUM> is an identifier of a compression scheme that should be used for decompressing data in a message. The compression identifier <NUM> may uniquely identify pre-configured compression schemes. The pre-configured compression schemes may include any compression scheme that can be performed by NE <NUM>, such as, for example, the deflate compression scheme (as described in the Network Working Group RFC <NUM>, entitled "DEFLATE Compressed Data Formal Specification version <NUM>," dated May <NUM>, by P. Deutsch), the LZS compression scheme (as described in the Network Working Group RFC <NUM>, entitled "IP Payload Compressing Using LZS," dated October <NUM>, by R. Friend, et. ), the ITU-T V. <NUM> compression scheme (as described by the Network Working Group, RFC <NUM>, entitled "IP Payload Compression Using IT-T V. <NUM> Packet Method," dated January <NUM>, by J. ), and/or any other compression scheme. The instructions <NUM> for compression schemes include logic or code that can be executed for each of the pre-configured compression schemes that can be performed by the NE <NUM>. The dictionary identifier <NUM> is a value uniquely identifying the dictionary <NUM>, which stores mappings between uncompressed bit strings and corresponding codewords. The LSDB <NUM> stores information describing a network topology of network <NUM>. The forwarding database <NUM> includes routing information describing a next hop to every destination in the network <NUM> from the NE <NUM>.

It is understood that by programming and/or loading executable instructions onto the NE <NUM>, at least one of the processor <NUM> and/or memory <NUM> are changed, transforming the NE <NUM> in part into a particular machine or apparatus, e.g., a multi-core forwarding architecture, having the novel functionality taught by the present disclosure. It is fundamental to the electrical engineering and software engineering arts that functionality that can be implemented by loading executable software into a computer can be converted to a hardware implementation by well-known design rules. Decisions between implementing a concept in software versus hardware typically hinge on considerations of stability of the design and numbers of units to be produced rather than any issues involved in translating from the software domain to the hardware domain. Generally, a design that is still subject to frequent change may be preferred to be implemented in software, because re-spinning a hardware implementation is more expensive than re-spinning a software design. Generally, a design that is stable that will be produced in large volume may be preferred to be implemented in hardware, for example in an ASIC, because for large production runs the hardware implementation may be less expensive than the software implementation. Often a design may be developed and tested in a software form and later transformed, by well-known design rules, to an equivalent hardware implementation in an ASIC that hardwires the instructions of the software. In the same manner as a machine controlled by a new ASIC is a particular machine or apparatus, likewise a computer that has been programmed and/or loaded with executable instructions may be viewed as a particular machine or apparatus.

<FIG> is a diagram illustrating a dictionary <NUM> to be used for compressing data in a message according to various embodiments of the disclosure. The dictionary <NUM> corresponds to the dictionary identifier <NUM>, which, as described above, uniquely identifies the dictionary <NUM>. The dictionary <NUM> includes multiple mappings 310A-N. Each mapping 310A-N describes an association between an uncompressed bit string 303A-N to a compressed codeword 306A-N.

In an embodiment, the compression controller <NUM> may identify multiple uncompressed bit strings 303A-N that have a high rate of occurrence in the traffic that is being forwarded through the network <NUM>. In this embodiment, the compression controller <NUM> creates a mapping 310A-N for each of the uncompressed bit strings 303A-N, in which each mapping 310A-N defines an association between the uncompressed bit string 303A-N and the compressed codeword 306A-N.

Similar to the example described above with reference to <FIG>, the compression controller <NUM> may monitor the uncompressed messages that are being forwarded through the network <NUM> to determine that <NUM>% of the traffic being forwarded carries an IPv6 address having the same <NUM>-bit prefix. In this case, the compression controller <NUM> may determine that the <NUM>-bit prefix is an uncompressed bit string 303A that can be compressed into a codeword 306A, which may be <NUM> bits or less. The compression controller <NUM> generates and stores a dictionary <NUM> that includes a mapping 310A of the uncompressed bit string 303A (<NUM>-bit prefix) to the codeword 306A.

In an embodiment, the compression controller <NUM> generates and stores multiple different dictionaries <NUM>. In the different dictionaries <NUM>, an uncompressed bit string 303A-N may be mapped to different codewords 306A-N. Each of the different dictionaries <NUM> stores one or more mappings 310A-N that associates an uncompressed bit string 303A-N with a corresponding codeword 306A-N.

<FIG> are message sequence diagrams illustrating methods <NUM> and <NUM> of performing compression and decompression on data in messages according to various embodiments of the disclosure. In particular, <FIG> is a message sequence diagram illustrating a method <NUM> of performing compression and decompression on data in messages according to a stateful compression scheme. <FIG> is a message sequence diagram illustrating a method <NUM> of performing compression and decompression on data in messages according to a stateless compression scheme.

Referring now to <FIG>, the method <NUM> is performed by NE <NUM> (referred to with regard to <FIG> as the compression controller <NUM>), NE <NUM>, and NE <NUM>. The compression controller <NUM> is communicatively coupled to NE <NUM> and NE <NUM>. The method <NUM> is performed to implement a stateful compression scheme, which refers to a compression scheme that relies upon a compression controller <NUM> that defines dictionaries <NUM>, which are forwarded to all the NEs <NUM>-<NUM> in the network <NUM> and used for compressing data.

At step <NUM>, the compression controller <NUM> monitors uncompressed messages that are being forwarded through the network <NUM>. For example, NEs <NUM>-<NUM> in network <NUM> may constantly be forwarding messages carrying information (topology and/or routing information) that are saved by each of the NEs <NUM>-<NUM> in the network <NUM>. The compression controller <NUM> may not only save the information received in each of these messages, but also monitor and analyze the bit strings defined in the message as, for example, TLVs and sub-TLVs, to define a dictionary <NUM>.

In an embodiment, while monitoring the uncompressed messages, the compression controller <NUM> may identify multiple uncompressed bit strings 303A-N (hereinafter referred to as "uncompressed bit strings <NUM>") that have a high rate of occurrence in the traffic being forwarded through the network <NUM>. In an embodiment, the compression controller <NUM> determines a count for certain uncompressed bit strings <NUM> that are frequently included in messages that are forwarded through the network <NUM>. In this embodiment, when the compression controller <NUM> determines that the count for an uncompressed bit string <NUM> present in messages being forwarded through the network <NUM> exceeds a threshold within a predetermined period of time, the compression controller <NUM> generates a corresponding codeword 306A-N (herein after referred to as "codeword <NUM>") for the uncompressed bit string <NUM>.

In one embodiment, the compression controller <NUM> determines a percentage that an uncompressed bit string <NUM> is present in the traffic being forwarded through the network <NUM>. In this embodiment, the compression controller <NUM> generates a corresponding codeword <NUM> for the uncompressed bit strings <NUM> having a percentage higher than a preset threshold.

At step <NUM>, the compression controller <NUM> obtains, or generates, a dictionary <NUM> to use for compressing data forwarded through the network <NUM>. The dictionary <NUM> includes the mappings <NUM> between the uncompressed bit strings <NUM> and the corresponding codewords <NUM>. At step <NUM>, the compression controller <NUM> assigns a dictionary identifier <NUM> to the dictionary <NUM> obtained at step <NUM>. The compression controller <NUM> also stores the dictionary <NUM> and the dictionary identifier <NUM> locally in the memory <NUM>.

At step <NUM>, the compression controller <NUM> forwards the dictionary <NUM> and the dictionary identifier <NUM> to the neighboring NE <NUM>. Similarly, at step <NUM>, the compression controller <NUM> forwards the dictionary <NUM> and the dictionary identifier <NUM> to the other neighboring NE <NUM>.

After receiving the dictionary <NUM> and the dictionary identifier <NUM> from the compression controller <NUM>, NE <NUM> and NE <NUM> are configured to wait a predetermined buffer time before beginning to use the dictionary <NUM> and the dictionary identifier <NUM> to compress data. When a message is received by the NE <NUM> after receiving the dictionary <NUM> and the dictionary identifier <NUM> and waiting the predetermined buffer time, NE <NUM> may determine that the message includes data that should be compressed based on a particular dictionary <NUM>. In the case where the message does not include a header, at step <NUM>, NE <NUM> adds a header including a dictionary identifier <NUM> identifying the dictionary <NUM> and a compression identifier <NUM> identifying that the stateful compression should be implemented. In an embodiment, the header may also include the length of the message prior to compressing the data and the length of the message after compressing the data.

At step <NUM>, NE <NUM> compresses the data based on the compression identifier <NUM>, the dictionary identifier <NUM>, and the dictionary <NUM> corresponding to the dictionary identifier <NUM> to obtain compressed data. NE <NUM> compresses the data in the message by translating the uncompressed bit strings <NUM> identified in the data of the message into the corresponding codeword <NUM>, as defined by the mappings <NUM> of the dictionary <NUM>. NE <NUM> obtains, or creates, a compressed message including the header and the compressed data, and forwards the compressed message to neighboring NEs <NUM> and <NUM>, at steps <NUM> and <NUM>, respectively.

As should be appreciated, after receiving the dictionary identifier <NUM> and the dictionary <NUM> from the compression controller <NUM> and receiving a message for compression, NE <NUM> may also perform steps <NUM> and <NUM> to create a compressed message. NE <NUM> may also forward the compressed message to neighboring NEs <NUM> and <NUM>.

In some cases, NE <NUM> may also receive a compressed message including a header and compressed data from another neighboring NE <NUM>. In this case, at step <NUM>, NE <NUM> decompresses the data based on the compression identifier <NUM> and the dictionary identifier <NUM> carried in the header of the compressed message to obtain the original data in the original message. NE <NUM> may first determine a dictionary <NUM> corresponding to the dictionary identifier <NUM> carried in the header of the compressed message. NE <NUM> may then determine the codewords <NUM> that are in the compressed data of the compressed message, and then translate the codewords <NUM> to the uncompressed bit strings <NUM> identified in the mappings <NUM> of the dictionary <NUM>. In an embodiment, NE <NUM> may validate the message after decompression by ensuring that the length of the message after compression matches the length of the message prior to compressing the data carried in the header of compressed message. In an embodiment, the NE <NUM> stores the data after decompressing the data in either the LSDB <NUM> or the forwarding database <NUM>, depending on the type of data in the message. At step <NUM>, the compression controller <NUM> performs similar steps to decompress the compressed message, validate the data, and store the data.

Referring now to <FIG>, the method <NUM> is performed by NE <NUM>, NE <NUM>, and NE <NUM>. The method <NUM> is performed to implement a stateless compression scheme, which refers to a pre-configured compression scheme that is stored as instructions <NUM> at each of the NEs <NUM>-<NUM> in the network <NUM>.

NE <NUM> receives a message from another NE <NUM>-<NUM> or <NUM>-<NUM> in the network <NUM>. In an embodiment, NE <NUM> determines that the message includes data that should be compressed before being forwarded through the network <NUM>, but the message does not include a header. In this embodiment, at step <NUM>, NE <NUM> adds a header to the message, in which the header carries a compression identifier <NUM> corresponding to a compression scheme for which instructions <NUM> are stored locally at each of the NEs <NUM>-<NUM> in the network <NUM>. For example, the NE <NUM> may add a compression identifier <NUM> corresponding to a default compression scheme that should be used to compress the data in the message. In an embodiment, the header may also include the length of the message prior to compressing the data and the length of the message after compressing the data.

In another embodiment, the message includes a header carrying a compression identifier <NUM>. In either case, at step <NUM>, NE <NUM> compresses the data in the message based on the instructions <NUM> corresponding to the compression scheme identified by the compression identifier <NUM> to obtain compressed data. NE <NUM> creates a compressed message including the compressed data and the header. NE <NUM> forwards the compressed message to neighboring NEs <NUM> and <NUM>, at steps <NUM> and <NUM>, respectively.

NE <NUM> receives the compressed message from NE <NUM>. At step <NUM>, NE <NUM> decompresses the compressed message based on the compression identifier <NUM> carried in the header of the compressed message. For example, NE <NUM> executes the instructions <NUM> that are pre-configured at all of the NEs <NUM>-<NUM> in the network <NUM> and that corresponds to the compression scheme identified by the compression identifier <NUM> to decompress the compressed data in the compressed message and obtain the original message. In an embodiment, NE <NUM> may validate the message after decompression by ensuring that the length of the message after compression matches the length of the message prior to compressing the data carried in the header of compressed message. In an embodiment, the NE <NUM> stores the data after decompressing the data in either the LSDB <NUM> or the forwarding database <NUM>, depending on the type of data in the message. NE <NUM> may perform similar steps after receiving the compressed message.

<FIG> is a message sequence diagram illustrating a method <NUM> for updating a dictionary <NUM> and forwarding the update to the dictionary <NUM> to other NEs <NUM>-<NUM> in the network <NUM> according to various embodiments of the disclosure. Method <NUM> is also performed by neighboring NEs <NUM>, <NUM>, and <NUM> when the network <NUM> implements a stateful compression scheme. Method <NUM> is performed after a dictionary <NUM> has been created and configured at all the NEs <NUM>-<NUM> in the network <NUM>.

At step <NUM>, the compression controller <NUM> continues to monitor all traffic (e.g., messages that are not compressed and compressed messages) that are being forwarded through the network <NUM>. This is similar to step <NUM> of method <NUM>, except that in method <NUM>, the compression controller <NUM> additionally monitors and examines compressed messages. During this step, the compression controller <NUM> identifies multiple uncompressed bit strings <NUM> in both types of messages that have a high rate of occurrence.

Based on the monitoring of these messages, at step <NUM>, the compression controller <NUM> determines an update to the dictionary <NUM>. For example, the compression controller <NUM> identifies another uncompressed bit string <NUM> that frequently occurs in the messages and compressed messages being forwarded through the network <NUM> and determines a corresponding codeword <NUM> for the uncompressed bit string <NUM>. The compression controller <NUM> determines an update to the dictionary <NUM> including a mapping <NUM> between the new uncompressed bit string <NUM> and the corresponding codeword <NUM> and stores the update to the dictionary <NUM>. The update to the dictionary <NUM> may refer to an update to an existing mapping <NUM> of the dictionary <NUM> or a new mapping <NUM> defining a new association between an uncompressed bit string <NUM> and a corresponding codeword <NUM>.

At step <NUM>, NE <NUM> forwards the dictionary identifier <NUM> corresponding to the dictionary <NUM> being updated and the update to the dictionary <NUM> (e.g., the new mapping <NUM>) to NE <NUM>. Similarly, at step <NUM>, NE <NUM> forwards the dictionary identifier <NUM> corresponding to the dictionary <NUM> being updated and the update to the dictionary <NUM> to NE <NUM>.

At step <NUM>, NE <NUM> updates the dictionary <NUM> to include the new mapping <NUM> received by NE <NUM> using the dictionary identifier <NUM>. The new mapping <NUM> may replace an existing mapping <NUM> in the locally stored dictionary <NUM> or be added as a new mapping <NUM> to the locally stored dictionary. At step <NUM>, NE <NUM> begins to compress data received in messages based on the update to the dictionary <NUM> to obtain a compressed message. Step <NUM> is similar to step <NUM> of method <NUM>. NE <NUM> may perform steps similar to steps <NUM> and <NUM>.

<FIG> is a diagram illustrating a message <NUM> and a compressed message <NUM> according to various embodiments of the disclosure. In some embodiments, <FIG> illustrates an intermediary step performed by an originating NE <NUM>-<NUM> before flooding the compressed message <NUM> through the network <NUM>. In an embodiment, an originating NE <NUM>-<NUM> first generates the message <NUM>. The NE <NUM>-<NUM> then compresses the data <NUM> in the message <NUM> according to a compression identifier <NUM> and/or a dictionary identifier <NUM> to form the compressed message <NUM>. The originating NE <NUM>-<NUM> then transmits the compressed message <NUM> to the other NEs <NUM>-<NUM> in the network <NUM>.

The message <NUM> includes a header <NUM> and the data <NUM> that has not been compressed. In an embodiment, the NE <NUM>-<NUM> receives the message <NUM> without the header <NUM> and adds the header <NUM> to the data <NUM>. In another embodiment, the NE <NUM>-<NUM> receives the message <NUM> including the header <NUM>.

The header <NUM> includes a type <NUM>, a compressed length <NUM>, a decompressed length <NUM>, a data type <NUM>, a compression identifier <NUM>, and/or a dictionary identifier <NUM>. As should be appreciated, the header <NUM> may include other data that may be used to compress and decompress the data <NUM>. The type <NUM> (also referred to as a TLV type) is a value that indicates that the message <NUM> should be compressed and/or carries compressed data. The value may be assigned by the Internet assigned numbers authority.

In an embodiment, the compressed length <NUM> (also referred to as length) is a length of the message <NUM> prior to compressing the data <NUM>. In an embodiment, the compressed length <NUM> is the length of the data <NUM> prior to compressing the data <NUM>. In an embodiment, the compressed length <NUM> does not include the length of the header <NUM>.

In an embodiment, the decompressed length <NUM> (also referred to as original TLV length) is a length of the message <NUM> after compressing the data <NUM>. In an embodiment, the decompressed length <NUM> is the data <NUM> after the data <NUM> is compressing the data <NUM>. In an embodiment, the decompressed length <NUM> does not include the length of the header <NUM>.

The data type <NUM> (also referred to as original TLV type) indicates a type of the data <NUM>. For example, the data type <NUM> includes a value representing the type of the data <NUM>. In an embodiment, the data type <NUM> is a value representing a type of TLV included in the data <NUM>. For example, the message <NUM> may carry multiple PPR-TLVs in the data <NUM>. In this case, the data type <NUM> is a value representing PPR-TLVs.

The compression identifier <NUM> (also referred to herein as the "compression algorithm") is an identifier of a compression scheme that should be used to compress and decompress the data <NUM>. In an embodiment, the compression identifier <NUM> is a value identifying a stateful compression scheme (as illustrated by methods <NUM> and <NUM>) or a particular type of stateless compression scheme (as illustrated by method <NUM>). For example, the compression identifier <NUM> may be set to <NUM> when a stateful compression scheme should be used to compress and decompress the data <NUM>, another compression identifier <NUM> may be set when a deflate compression scheme should be used to compress and decompress the data <NUM>, another compression identifier <NUM> may be set when an LZS compression scheme should be used to compress and decompress the data <NUM>, another compression identifier <NUM> may be set when the ITU-T V. <NUM> compression scheme should be used to compress and decompress the data <NUM>, etc..

The dictionary identifier <NUM> is an identifier of a dictionary <NUM> that should be used to compress and decompress the data <NUM>. In an embodiment, the dictionary identifier <NUM> may only be included in the header <NUM> when the compression identifier <NUM> indicates that a stateful compression scheme should be implemented. When the compression identifier <NUM> indicates that a stateless compression scheme (e.g., any other pre-configured compression scheme) should be implemented, the dictionary identifier <NUM> may be set to <NUM> or not included in the header <NUM>.

The data <NUM> may include any information that should be flooded through a network <NUM> and encoded according to an IGP (e.g., IS-IS, OSPFv2, or OSPFv3). For example, the data <NUM> may include topology information received from the central entity <NUM>, another NE <NUM>-<NUM> in the network <NUM>, or an external client that is to be stored at each of the NEs <NUM>-<NUM> in the network <NUM>. The data <NUM> may also include routing information received from the central entity <NUM>, another NE <NUM>-<NUM> in the network <NUM>, or an external client indicating a next hop to one or more destinations in the network <NUM> (or outside the network <NUM>). When the data <NUM> includes routing information, the data <NUM> may be encoded according to several different types of TLVs, or a particular data type <NUM>. For example, the data <NUM> may include uncompressed data 615A-N of a data type <NUM> associated with PPRs, which includes one or more PPR-TLVs describing one or more PPRs that are to be provisioned in the network <NUM>. As another example, the data <NUM> may include uncompressed data 615A-N of a data type <NUM> associated with PPR graphs, which includes one or more PPR Graph-TLVs describing one or more PPR graphs that are to be provisioned in the network <NUM>.

After an NE <NUM>-<NUM> compresses the uncompressed data 615A-N (hereinafter referred to as "data <NUM>") in the message <NUM>, the NE <NUM>-<NUM> obtains, or generates, the compressed message <NUM>. The header <NUM> in the compressed message <NUM> is the same as the header <NUM> of the message <NUM>. The compressed message <NUM> includes the compressed data 625A-N. The NE <NUM>-<NUM> compresses the data <NUM> to obtain the compressed data <NUM> based on the compression identifier <NUM> and/or the dictionary identifier <NUM> included in the header <NUM>.

The compressed data 625A-N (also referred to herein as "compressed data <NUM>") includes the same information as data <NUM>, except that the compressed data <NUM> is encoded according to a compression scheme and/or a dictionary <NUM>. For example, if the compression identifier <NUM> identifies a stateless compression scheme, then the compressed data <NUM> is encoded according to the stateless compression scheme identified by the compression identifier <NUM>. In this case, the NE <NUM>-<NUM> performs the compression scheme identified by the compression identifier <NUM> using the instructions <NUM> corresponding to the compression identifier <NUM> with the data <NUM> to output the compressed data <NUM>. If the compression identifier <NUM> identifies a stateful compression scheme, the compressed data <NUM> is encoded according to the dictionary <NUM> corresponding to the dictionary identifier <NUM> included in the header <NUM>. In this case, the NE <NUM>-<NUM> performs compression based on the dictionary <NUM> to output the compressed data <NUM>, which is then included in the compressed message <NUM> instead of the data <NUM>.

Similar to data <NUM>, the compressed data <NUM> may be encoded according to several different types of TLVs, or a particular data type <NUM>. For example, the compressed data <NUM> may include compressed data 625A-N of a data type <NUM> associated with PPRs, which includes one or more compressed PPR-TLVs describing one or more PPRs that are to be provisioned in the network <NUM>. As another example, the compressed data <NUM> may include compressed data 625A-N of a data type <NUM> associated with PPR graphs, which includes one or more compressed PPR Graph-TLVs describing one or more PPR graphs that are to be provisioned in the network <NUM>.

<FIG> is a diagram illustrating a message <NUM> and a compressed message <NUM> encoded according to IS-IS according to various embodiments of the disclosure. Message <NUM> is similar to message <NUM> (<FIG>), except that message <NUM> is encoded according to IS-IS, and as such, includes fields related to IS-IS. Similar to <FIG>, <FIG> illustrates an intermediary step performed by an originating NE <NUM>-<NUM> before flooding the compressed message <NUM> through the network <NUM>. In an embodiment, an originating NE <NUM>-<NUM> first generates the message <NUM>. The NE <NUM>-<NUM> then compresses the data <NUM> in the message <NUM> according to a compression identifier <NUM> and/or a dictionary identifier <NUM> to form the compressed message <NUM>. The originating NE <NUM>-<NUM> then transmits the compressed message <NUM> to the other NEs <NUM>-<NUM> in the network <NUM>.

The header <NUM> includes a TLV type field <NUM>, a length field <NUM>, a flags field <NUM>, a compression identifier field <NUM>, an original TLV type field <NUM>, an original TLV length field <NUM>, a sub-TLV type field <NUM>, a sub-TLV length field <NUM>, a dictionary identifier field <NUM>, and multiple uncompressed TLVs 720A-N. The multiple uncompressed TLVs 720A-N carry data <NUM>, which is uncompressed and similar to data <NUM> (<FIG>). As should be appreciated, the header <NUM> may include other fields carrying data <NUM> that may be used to compress and decompress the data <NUM>.

The TLV type field <NUM> carries the TLV type <NUM> (<FIG>). The length field <NUM> carries the compressed length <NUM> (<FIG>). The flags <NUM> field carries one or more flags that may be set to a value that is used for compressing or decompressing the data <NUM>. The compression identifier field <NUM> carries the compression identifier <NUM> (<FIG>). The original TLV type field <NUM> carries the data type (<FIG>). The original TLV length field <NUM> carries the decompressed length <NUM> (<FIG>). The dictionary identifier field <NUM> carries the dictionary identifier <NUM>.

When the message <NUM> contains additional TLVs that are not part of the data type <NUM> encoded in the original TLV type field <NUM>, the sub-TLV type field <NUM> carries a value indicating a type of the additional TLVs, and the sub-TLV length field <NUM> carries a length of the additional TLVs. The sub-TLV type field <NUM> and the sub-TLV length field <NUM> are optional fields that may be included in the message <NUM> when the message <NUM> includes the additional TLVs. The data <NUM> is encoded as the uncompressed TLVs 720A-N of the data type <NUM> carried in the carried in the original TLV type field <NUM>.

After compression is performed on the multiple uncompressed TLVs 720A-N, the compressed message <NUM> is obtained. The compressed message <NUM> includes the header <NUM> and the compressed data <NUM>, encoded as the compressed TLVs 725A-N. The compressed message <NUM> includes the same header <NUM> as the message <NUM>. The compressed TLVs 725A-N include the same information as the uncompressed TLVs 720A-N of the data type <NUM>, except the information in the compressed TLVs 725A-N is compressed according to the compression identifier <NUM> carried in the compression identifier field <NUM> and/or the dictionary identifier <NUM> carried in the dictionary identifier field <NUM>.

<FIG> are diagrams illustrating a message <NUM> and a compressed message <NUM> encoded according to OSPF Version <NUM> (OSPFv2) according to various embodiments of the disclosure. <FIG> shows the message <NUM> and <FIG> shows the compressed message <NUM>. Similar to <FIG>, <FIG> illustrate an intermediary step performed by an originating NE <NUM>-<NUM> before flooding the compressed message <NUM> of <FIG> through the network <NUM>. In an embodiment, an originating NE <NUM>-<NUM> first generates the message <NUM> of <FIG>. The NE <NUM>-<NUM> then compresses the data in the message <NUM> according to a compression identifier <NUM> and/or a dictionary identifier <NUM> to form the compressed message <NUM> of <FIG>. The originating NE <NUM>-<NUM> then transmits the compressed message <NUM> to the other NEs <NUM>-<NUM> in the network <NUM>.

Referring now to <FIG>, message <NUM> is similar to message <NUM> (<FIG>), except that message <NUM> is encoded according to OSPFv2, and as such, includes fields related to OSPFv2. In an embodiment, message <NUM> is encoded as an LSA according to OSPFv2, and includes new fields <NUM> that are not described by RFC <NUM>.

The message <NUM> includes a header <NUM> and the uncompressed LSAs <NUM> that have not been compressed. The header <NUM> includes an LS age field <NUM>, options <NUM>, an LS type field <NUM>, an opaque identifier field <NUM>, an advertising router field <NUM>, an LS sequence number field <NUM>, an LS checksum field <NUM>, a length field <NUM>, flags <NUM>, an original LS type field <NUM>, an original opaque type field <NUM>, a compression identifier field <NUM>, a decompressed length field <NUM>, and a dictionary identifier field <NUM>. As should be appreciated, the header <NUM> may include other fields carrying data that may be used to compress and decompress the LSAs. The multiple uncompressed LSAs <NUM> carry uncompressed data <NUM> or <NUM>.

The LS age field <NUM>, options <NUM>, LS type field <NUM>, opaque identifier field <NUM>, advertising router field <NUM>, LS sequence number field <NUM>, LS checksum field <NUM>, and length field <NUM> are described by RFC <NUM> as original fields of an OSPFv2 extended prefix opaque LSA. In an embodiment, the length field <NUM> carries the compressed length <NUM> (<FIG>). The new fields <NUM> of the message includes the flags <NUM>, original LS type field <NUM>, original opaque type field <NUM>, compression identifier field <NUM>, length of decompressed data field <NUM>, and the dictionary identifier field <NUM>. The flags <NUM> carry one more flags, or values, indicating information to be used for compressing or decompressing the LSAs <NUM>. The original LS type field <NUM> carries a checksum computed after forming the complete TLV with the compressed LSAs, as shown in <FIG>, and the original opaque type field <NUM> carries a length of the compressed LSAs, as shown in <FIG>. The compression identifier field <NUM> carries the compression identifier <NUM>. The decompressed length field <NUM> carries the decompressed length <NUM> (<FIG>). The dictionary identifier field <NUM> carries the dictionary identifier <NUM>, and this field is optional based on the compression identifier <NUM> carried in the compression identifier field <NUM>. For example, when the compression identifier <NUM> indicates a stateless compression scheme, the dictionary identifier field <NUM> may not be included in the header <NUM>. The uncompressed LSAs <NUM> carry data in the form of one or more LSAs, all of the same data type <NUM>.

Referring now to <FIG>, the compressed message <NUM> is similar to message <NUM> (<FIG>), except that the compressed message <NUM> is encoded according to OSPFv2, and as such, includes fields related to OSPFv2. In an embodiment, message <NUM> is encoded as an LSA according to OSPFv2. As shown by <FIG>, compressed message <NUM> is similar to message <NUM> in that compressed message <NUM> includes all the fields in the header <NUM>. However, the compressed message <NUM> includes compressed LSAs <NUM> instead of the uncompressed LSAs <NUM>. The compressed LSAs <NUM> include the same information as the information in the uncompressed LSAs <NUM>, except that the compressed LSAs <NUM> are compressed according to a compression scheme identified by the compression identifier <NUM> carried in the compression identifier field <NUM> and/or the dictionary identifier <NUM> carried in the dictionary identifier field <NUM>.

<FIG> are diagrams illustrating a message <NUM> and a compressed message <NUM> encoded according to OSPF Version <NUM> (OSPFv3) according to various embodiments of the disclosure. <FIG> shows the message <NUM>, and <FIG> shows the compressed message <NUM>. Similar to <FIG>, <FIG>, and <FIG>, <FIG> illustrate an intermediary step performed by an originating NE <NUM>-<NUM> before flooding the compressed message <NUM> of <FIG> through the network <NUM>. In an embodiment, an originating NE <NUM>-<NUM> first generates the message <NUM> of <FIG>. The NE <NUM>-<NUM> then compresses the data in the message <NUM> according to a compression identifier <NUM> and/or a dictionary identifier <NUM> to form the compressed message <NUM> of <FIG>. The originating NE <NUM>-<NUM> then transmits the compressed message <NUM> to the other NEs <NUM>-<NUM> in the network <NUM>.

Referring now to <FIG>, message <NUM> is similar to message <NUM> (<FIG>), except that message <NUM> is encoded according to OSPFv3, and as such, includes fields related to OSPFv3. In an embodiment, message <NUM> is encoded as an LSA according to OSPFv3, and includes new fields <NUM> that are not described by RFC <NUM>.

The message <NUM> includes a header <NUM> and the uncompressed LSAs <NUM> that have not been compressed. The header <NUM> includes an LS age field <NUM>, an LS type field <NUM>, an LS identifier field <NUM>, an advertising router field <NUM>, an LS sequence number field <NUM>, an LS checksum field <NUM>, a length field <NUM>, an original LS type field <NUM>, a compression identifier field <NUM>, flags <NUM>, a length of uncompressed data field <NUM>, and a dictionary identifier field <NUM>. As should be appreciated, the header <NUM> may include other fields carrying data that may be used to compress and decompress the LSAs. The multiple uncompressed LSAs <NUM> carry uncompressed data <NUM> or <NUM>.

The LS age field <NUM>, LS type field <NUM>, LS identifier field <NUM>, advertising router field <NUM>, LS sequence number field <NUM>, LS checksum field <NUM>, and length field <NUM>, are described by RFC <NUM> as original fields of an OSPFv3 LSA. In an embodiment, the length field <NUM> carries the compressed length <NUM> (<FIG>). The new fields <NUM> of the message <NUM> include an original LS type field <NUM>, a compression identifier field <NUM>, flags <NUM>, a length of uncompressed data field <NUM>, and a dictionary identifier field <NUM>. The original LS type field <NUM> carries the data type <NUM>. The compression identifier field <NUM> carries the compression identifier <NUM>. The flags <NUM> carry one more flags, or values, indicating information to be used for compressing or decompressing the LSAs <NUM>. The length of the uncompressed data field <NUM> carries the decompressed length <NUM> (<FIG>). The dictionary identifier field <NUM> carries the dictionary identifier <NUM>, and this field is optional based on the compression identifier <NUM> carried in the compression identifier field <NUM>. For example, when the compression identifier <NUM> indicates a stateless compression scheme, the dictionary identifier field <NUM> may not be included in the header <NUM>. The uncompressed LSAs <NUM> carry data in the form of one or more LSAs, all of the same data type <NUM>.

Referring now to <FIG>, the compressed message <NUM> is similar to compressed message <NUM> (<FIG>), except that compressed message <NUM> is encoded according to OSPFv3, and as such, includes fields related to OSPFv3. In an embodiment, compressed message <NUM> is encoded as an LSA according to OSPFv3. As shown by <FIG>, compressed message <NUM> is similar to message <NUM> in that compressed message <NUM> includes all the fields in the header <NUM>. However, the compressed message <NUM> includes compressed LSAs <NUM> instead of the uncompressed LSAs <NUM>. The compressed LSAs <NUM> include the same information as the information in the uncompressed LSAs <NUM>, except that the compressed LSAs <NUM> are compressed according to a compression scheme identified by the compression identifier <NUM> carried in the compression identifier field <NUM> and/or the dictionary identifier <NUM> carried in the dictionary identifier field <NUM>.

<FIG> is a flowchart illustrating a method <NUM> for compressing data using an IGP according to various embodiments of the disclosure. Method <NUM> may be performed by one of the NEs <NUM>-<NUM> in the network <NUM> or by NE <NUM> implemented as one of the NEs <NUM>-<NUM>. Method <NUM> is performed after instructions <NUM> corresponding to different compression schemes, compression identifiers <NUM> identifying the different compression schemes, dictionaries <NUM>, and/or dictionary identifiers <NUM> are pre-stored at each of the NEs <NUM>-<NUM>.

At step <NUM>, one of the NEs <NUM>-<NUM> generates a message comprising a header and data. The message may be similar to the message <NUM>, <NUM>, <NUM>, or <NUM>. The header may be similar to the header <NUM>, <NUM>, <NUM>, or <NUM>. The data may be similar to data <NUM> or <NUM> or uncompressed LSAs <NUM> or <NUM>. In an embodiment, the header comprises a decompressed length <NUM>, which refers to a length of the data prior to compressing the data. The header also comprises a compressed length <NUM>, which refers to a length of the data after compressing the data. The header may also comprise the compression identifier <NUM>. In an embodiment, Tx/Rx <NUM> receives the message from another NE <NUM>-<NUM> in the network, the central entity <NUM>, or an external device or client.

At step <NUM>, NE <NUM>-<NUM> compresses the data based on a compression scheme identified by the compression identifier <NUM> to obtain compressed data, such as the compressed data <NUM> or <NUM> or compressed LSAs <NUM> or <NUM>. For example, the processor <NUM> executes the compression module <NUM> to perform compression on the data based on the compression scheme identified by the compression identifier <NUM>.

For example, when the compression identifier <NUM> identifies a particular stateless compression scheme (e.g., deflate compression scheme, LZS compression scheme, ITU-T V. <NUM> compression scheme, etc.), NE <NUM>-<NUM> searches the memory <NUM> for instructions <NUM> corresponding to the stateless compression scheme. NE <NUM>-<NUM> executes the instructions <NUM> to compress the data and output the compression data. NE <NUM>-<NUM> generates a compressed message, such as message <NUM>, <NUM>, <NUM>, or <NUM>, by replacing the data with the compressed data.

At step <NUM>, NE <NUM>-<NUM> forwards the compressed message comprising to the header and the compressed data to other NEs <NUM>-<NUM> in the network <NUM>. For example, the Tx/Rx forwards the compressed message to other NEs <NUM>-<NUM> in the network <NUM> to flood the network <NUM> with the compressed message.

The NE <NUM>-<NUM> that receives the compressed message decompresses the message based on the compression identifier <NUM> when the compression identifier <NUM> indicates a stateless compression scheme. Alternatively, the NE <NUM>-<NUM> that receives the compressed message decompresses the message based on the compression identifier <NUM> and the dictionary identifier <NUM> when the compression identifier <NUM> indicates a stateful compression scheme.

In an embodiment, the NE <NUM>-<NUM> that receives the compressed data may store the compressed message locally in the LSDB <NUM> and/or the forwarding database <NUM>. In an embodiment, the NE <NUM>-<NUM> that receives the compressed message first decompresses the compressed message to obtain the original message. Then, the NE <NUM>-<NUM> stores the data that has been decompressed in the LSDB <NUM> and/or the forwarding database <NUM>.

<FIG> is a diagram illustrating an apparatus <NUM> for compressing data using an IGP according to various embodiments of the disclosure. The apparatus <NUM> comprises a means for generating <NUM>, a means for compressing <NUM>, and a means for forwarding <NUM>. The means for generating <NUM> comprises a means for generating a message comprising a header and data, wherein the header comprises a length of the data prior to compressing the data, a length of the data after compressing the data, and a compression identifier. The means for compressing <NUM> comprises a means for compressing the data based on a compression scheme identified by the compression identifier to obtain compressed data. The means for forwarding <NUM> comprises a means for forwarding a compressed message comprising the header and the compressed data to other NEs in the network.

<FIG> is a flowchart illustrating a method <NUM> for decompressing data using an IGP according to various embodiments of the disclosure. Method <NUM> may be performed by one of the NEs <NUM>-<NUM> in the network <NUM> or by NE <NUM> implemented as one of the NEs <NUM>-<NUM>. Method <NUM> is performed after instructions <NUM> corresponding to different compression schemes, compression identifiers <NUM> identifying the different compression schemes, dictionaries <NUM>, and/or dictionary identifiers <NUM> are pre-stored at each of the NEs <NUM>-<NUM>.

At step <NUM>, one of the NEs <NUM>-<NUM> receives a message comprising a header and compressed data. The message may be similar to the message <NUM>, <NUM>, <NUM>, or <NUM>. The header may be similar to the header <NUM>, <NUM>, <NUM>, or <NUM>. The compressed data may be similar to compressed data <NUM> or <NUM> or compressed LSAs <NUM> or <NUM>. In an embodiment, the header comprises a decompressed length <NUM>, which refers to a length of the data prior to compressing the data. The header also comprises a compressed length <NUM>, which refers to a length of the data after compressing the data. The header may also comprise the compression identifier <NUM>. In an embodiment, Tx/Rx <NUM> receives the message from another NE <NUM>-<NUM> in the network, the central entity <NUM>, or an external device or client.

At step <NUM>, NE <NUM>-<NUM> decompresses the compressed data based on a compression scheme identified by the compression identifier <NUM> to obtain uncompressed data (e.g., data prior to compression), such as data <NUM> or <NUM> or uncompressed LSAs <NUM> or <NUM>. For example, the processor <NUM> executes the compression module <NUM> to perform decompression on the data based on the compression scheme identified by the compression identifier <NUM>.

For example, when the compression identifier <NUM> identifies a particular stateless compression scheme (e.g., deflate compression scheme, LZS compression scheme, ITU-T V. <NUM> compression scheme, etc.), NE <NUM>-<NUM> searches the memory <NUM> for instructions <NUM> corresponding to the stateless compression scheme. NE <NUM>-<NUM> executes the instructions <NUM> to decompress the compressed data and output the uncompressed data.

At step <NUM>, NE <NUM>-<NUM> stores at least one of the uncompressed data or the compressed data in the memory <NUM>. The compressed data, such as compressed data <NUM> or <NUM> or compressed LSAs <NUM> or <NUM>, may be stored in the LSDB <NUM> and/or the forwarding database <NUM>. The uncompressed data, such as data <NUM> or <NUM> or uncompressed LSAs <NUM> or <NUM>, may be stored in the LSDB <NUM> and/or the forwarding database <NUM>, to facilitate efficiency of the network <NUM>.

<FIG> is a diagram illustrating an apparatus <NUM> for decompressing data using an IGP according to various embodiments of the disclosure. The apparatus <NUM> comprises a means for receiving <NUM>, a means for decompressing <NUM>, and a means for storing <NUM>. The means for receiving <NUM> comprises a means for receiving a message comprising a header and data, wherein the header comprises a length of data prior to compression, a length of the compressed data, and a compression identifier. The means for decompressing <NUM> comprises a means for decompressing the compressed data based on a compression scheme identified by the compression identifier to obtain uncompressed data. The means for storing <NUM> comprises a means for storing at least one of the compressed data or the uncompressed data in a local memory <NUM>.

Claim 1:
A method performed by a network element, NE, in a network implementing an Interior Gateway Protocol, IGP, comprising:
generating a message carrying topology and/or routing information to be flooded through the network, the message comprising a header and data to be compressed and to be forwarded through the network using the IGP, wherein the header comprises a length of the data prior to compressing the data, and a compression identifier;
compressing the data based on a compression scheme identified by the compression identifier to obtain compressed data; and
forwarding, using the IGP, a compressed message comprising the header and the compressed data to other NEs in the network, wherein the header comprises a length of the compressed data,
and the header further comprises a first type field, a decompressed length field, a compression identifier field, a second type field, and a compressed length field, wherein the first type field carries a value indicating that the compressed message carries the compressed data, wherein the decompressed length field carries the length of the data prior to compressing the data, wherein the compressed length field carries the length of the compressed data, wherein the compression identifier field carries the compression identifier, and wherein the second type field carries a value identifying a type of the data being compressed.