Efficient processing of linked lists using delta encoding

This application claims priority to and the benefit of both U.S. Provisional Patent Application No. 61/836,574 filed Jun. 18, 2013 and U.S. Provisional Patent Application No. 61/911,862 filed Dec. 24, 2013 the disclosures of which are incorporated by reference herein in their entirety.

The present disclosure relates to a network device that processes packets.

The background description provided herein is for the purpose of generally presenting the context of the disclosure. Work of the presently named inventors, to the extent it is described in the background section, as well as aspects of the description that may not otherwise qualify as prior art at the time of filing, are neither expressly nor impliedly admitted as prior art against the present disclosure.

As part of a data packet forwarding operation, network devices store data related to addresses for forwarding packets. The addresses are stored as attributes including information about a destination, such as a target port, a target MAC address, a priority, a VLAN, etc.

Further, a plurality of attributes corresponding to one forwarding address is stored by the network device as an element. In an example of a forwarding operation, the element is linked to one or more other elements as a linked list. Each of these other elements respectively corresponds to another forwarding address to which to forward a data packet.

One or more example embodiments of the disclosure generally relate to a forwarding operation by a network device having a packet processor. The forwarding operation uses a network device which stores a plurality of elements, such as a routing table, as a linked list with each element including a plurality of attributes which correspond to respective addresses. The network device compares differences between a first element and a second element of the linked list. The network device stores an indication of the difference at the second element, and subsequently the network device is capable of determining at least part of an address by reading the difference indicator at the second element instead of reading the attributes.

FIG. 1 shows a network device multicasting a packet from a network to one or more destinations according to example embodiments.

FIG. 2 shows a linked list structure corresponding to forwarding addresses stored by the network device according to example embodiments.

FIG. 3 shows a linked list structure resulting from a delta encoding operation according to example embodiments.

FIG. 4A shows a flowchart of a network processing operation for retrieving forwarding information from lines of memory.

FIG. 4B shows a flowchart of a network processing operation for retrieving forwarding information from delta encoded lines of memory according to example embodiments.

FIG. 5 shows a linked list structure with delta encoded elements and a corresponding cache operable during a network operation according to example embodiments.

FIG. 6 shows a delta encoded linked list and a new element inserted into the delta encoded linked list according to example embodiments.

FIG. 7 shows a network device unicasting a packet from a network to a destination according to example embodiments.

In the following discussion, descriptions of well-known functions and constructions are omitted for increased clarity and conciseness.

FIG. 1 shows a system 1000 including network 100 , a packet 101 , and destination 140 , destination 150 , destination 160 , and destination 170 . Each destination is a potential forwarding location to which a packet 101 , received from network 100 , is forwarded to by the network device 110 .

The network device 110 , a packet processing system, includes at least one processor core 111 , as at least a packet processor (denoted “CPU”), a delta encoder 112 , and a memory 113 . The memory 113 includes a linked list 120 and a cache 130 .

The delta encoder 112 is configured to delta encode the linked list 120 of the memory 113 which stores a plurality of forwarding address, for example addresses to each of the destinations 140 - 170 , as elements of the linked list 120 . According to an example embodiment, the packet 101 is multicast to destination 140 , destination 150 , and destination 170 . Although FIG. 1 illustrates four potential destinations and only three recipient destinations, any number of destinations may act as recipients of a multicast or unicast operation.

According to an example embodiment, the delta encoder 112 is further configured to decode a delta encoded portion of the linked list 120 thereby decoding forwarding addresses. Delta encoding and/or decoding reduces the computational requirements of finding a network forwarding address by allowing the processing of a linked list of network attributes such that the cache 130 caches the attributes of a first element of a linked list 120 and subsequently provides corresponding elements to the CPU 111 until a delta encoded flag indicates a difference between two elements of the linked list 120 . Therefore, each attribute of every element of the linked list need not be necessarily read by the packet processor in order to decode one or more forwarding addresses.

FIG. 2 shows a system 2000 including the network device 110 and an expanded view 121 of the linked list 120 , which implements a routing table, in an example embodiment. According to the example embodiment of FIG. 2 , the linked list 120 , as shown, is not yet delta encoded by the delta encoder 112 .

The expanded view 121 illustrates a plurality of elements of the linked list, such as element 120 - 0 , element 120 - 1 , and element 120 - 2 . Each of the elements of the linked list 120 includes a plurality of attributes, a null indicator (denoted “LAST=X”; where X is 0 when there are additional attributes and X is 1 when there are no additional attributes), and a next pointer (described below).

The plurality of attributes, in this example embodiment, are attributes of a network address and relate to one or more of a forwarding address, a destination address, a target port, a target MAC address, a priority, and/or a VLAN, or the like. The null indicator is used in an example embodiment to indicate whether there is another attribute of an address to which to forward a packet during a multicast operation. The next pointer is a pointer to a subsequent element of the linked list 120 .

It is noted that, by reading the attributes of the elements of the linked list 120 , the packet processing system is able to make a forwarding determination for a received packet 101 and, more particularly, a determination of at least part of a destination address.

Element 120 - 0 includes attribute 120 - 0 A, attribute 120 - 0 B, attributes 120 - 0 C, and attribute 120 - 0 D. Element 120 - 0 further includes null indicator 120 - 0 E and a next pointer 120 - 0 F. The next pointer 120 - 0 F points to element 120 - 1 .

Element 120 - 1 includes attribute 120 - 1 A, attribute 120 - 1 B, attributes 120 - 1 C, and attribute 120 - 1 D. Element 120 - 1 further includes null indicator 120 - 1 E and a next pointer 120 - 1 F. The next pointer 120 - 1 F points to element 120 - 2 .

Element 120 - 2 includes attribute 120 - 2 A, attribute 120 - 2 B, attributes 120 - 2 C, and attribute 120 - 2 D. Element 120 - 2 further includes null indicator 120 - 2 E and a next pointer 120 - 2 F. The next pointer 120 - 2 F points to a null node (not shown).

The network device 110 reads the elements of the linked list 120 to make forwarding determinations by retrieving from among the attributes pertinent parts of forwarding addresses and related network values involved in forwarding a packet.

FIG. 3 shows a system 3000 including the network device 110 and an expanded view 121 of the linked list 120 . In contrast to the example embodiment of FIG. 2 , the linked list 120 in FIG. 3 has been delta encoded by the delta encoder 112 . Although an example embodiment relating to creating such a delta encoded linked list is mentioned below, any approach to performing the delta encoding is acceptable, including delta encoding the entire list at once as well as maintaining a delta encoded list by applying suitable modifications as list elements are added or deleted.

The expanded view 121 illustrates a plurality of elements of the linked list, such as element 120 - 0 , element 120 - 1 , and element 120 - 2 . Each of the elements of the linked list 120 includes an indication of a plurality of attributes, a null indicator, and a next pointer.

In addition to the plurality of attributes discussed with respect to FIG. 2 , the linked list 120 of FIG. 3 additionally includes a difference indicator(s), a difference type indicator(s), and/or a difference value(s). According to an example embodiment, a difference indicator is implemented as a flag. For the sake of brevity, a difference indicator as mentioned herein may be referred to as a difference flag without regard to the particular concrete implementation.

The difference indicators each indicate whether there is a difference between any attributes of a current element and corresponding attributes of the preceding element. The corresponding attributes are attributes that occupy a corresponding position in each of the two elements. Each difference indicator indicates a difference between at least one of the attributes of a current element and an attribute at a corresponding position of the previous element. To explain further, with respect to FIG. 2 , attribute 120 - 0 B (at position “Attribute 2”) of element 120 - 0 and attribute 120 - 1 B of element 120 - 1 (also at position “Attribute 2”) occupy corresponding positions.

Furthermore, it is noted that, in the linked list, element 120 - 0 is seen to precede element 120 - 1 , and element 120 - 1 is seen to precede element 120 - 2 . It is also noted that the next pointer of a preceding element is seen to point to a current element.

Element 120 - 0 of FIG. 3 includes attribute 120 - 0 A, attribute 120 - 0 B, attributes 120 - 0 C, and attribute 120 - 0 D. Element 120 - 0 further includes null indicator 120 - 0 E and a next pointer 120 - 0 F. The next pointer 120 - 0 F points to element 120 - 1 .

In contrast to FIG. 2 , element 120 - 1 of FIG. 3 includes difference indicator 120 - 1 G, difference type indicator 120 - 1 H, difference value 120 - 1 I, and values 120 - 1 J. The values, according to an example embodiment, are additional difference indicators and attributes which are not delta encoded. Element 120 - 1 further includes null indicator 120 - 1 E and a next pointer 120 - 1 F. The next pointer 120 - 1 F points to element 120 - 2 .

In contrast to FIG. 2 , element 120 - 2 of FIG. 3 includes difference indicator 120 - 2 G, null indicator 120 - 2 H and a next pointer 120 - 2 F. The next pointer 120 - 2 F points to a null node (not shown).

In FIG. 3 , the difference indicator 120 - 1 G has a value of “DIFF=1”, according to an example embodiment, which indicates that some attribute or value in element 120 - 1 is different from the corresponding attribute or value in the preceding element, namely, element 120 - 0 . In an example embodiment, a single bit is used as a flag for difference indicator 120 - 1 G (and 120 - 2 G, etc., as well).

The difference type indicator 120 - 1 H in FIG. 3 has a value of “TYPE=ATTRIBUTE 2”, according to an example embodiment, which indicates that attribute 2 for element 120 - 1 is different from the corresponding attribute 2 in the preceding element, namely, element 120 - 0 . In general, by storing only the differences between elements, the amount of processing required for each element is reduced compared to the example embodiment shown in FIG. 2 , where the complete values of all elements are stored.

In FIG. 3 , attribute 120 - 1 I reflects the value of Attribute 2 in element 120 - 1 . According to one example embodiment, the attribute 120 - 1 I stores the complete value of Attribute 2; according to another example embodiment, the attribute 120 - 1 I stores an indicator of a difference in value between the two non-delta encoded Attribute 2 values (i.e., the value of attribute 2 for element 120 - 1 and the value of the corresponding attribute 2 in the preceding element, namely, element 120 - 0 as shown in FIG. 2 ).

In FIG. 3 , element 120 - 2 has a difference indicator 120 - 2 G that holds a value indicating no difference between any attribute in element 120 - 2 and the preceding element (namely, element 120 - 1 ).

FIG. 4A is a flow diagram 4000 A of an example algorithm and method, according to example embodiments, when a data packet is received by the network device. In other words, the example embodiment of FIG. 4A is an example of making at least a partial routing determination of at least part of a destination address responsive to a difference flag of an element of the linked list.

The example method of FIG. 4A applies to multiple example embodiments in which the network device is utilized, for example the system of FIG. 1 . Processing begins at S 401 at which the network device receives a data packet during a network session. The network device, using a packet processor, determines that a linked list contains a plurality of attributes corresponding to a plurality of forwarding addresses and network values for a forwarding operation. Processing continues at S 402 .

At S 402 , the packet processor processes a line of memory corresponding to a first element of the linked list, the first element containing attributes of a routing table, according to an example embodiment. The packet processor determines values, such as at least a part of a destination address, from the attributes stored at the line of the memory, and processing continues at S 403 .

At S 403 , the packet processor is pointed to a next line of memory by the previous element, the previous element stored at a previous line of memory. Processing continues at S 404 .

At S 404 , the packet processor reads the pointed-to line which also contains a set of attributes corresponding to additional values. The packet processor determines if the current element contains a difference indicated by a flag as a difference indicator or difference flag. If the difference flag of the current element indicates no difference between the current line (element) and the preceding line (element), then processing continues at S 404 A. If the difference flag of the current element indicates a difference, then processing continues at S 404 B.

At S 404 A, responsive to the value of the difference flag determined at S 404 , indicating that there is no difference between the element of the current line of memory and that of the previous line of memory, the packet processor processes the previous line of memory again to receive the same value that resulted from the processing of the previous line. Processing continues at S 405 . In an example embodiment, the processing is not itself repeated, but the prior result is re-used in place of carrying out such processing.

Returning to S 404 B, responsive to the value of the difference flag determined at S 404 , indicating that there is a difference between the element of the current line of memory and that of the previous line of memory, the packet processor processes the current line of memory to obtain a value different from the value determined from the previous line of memory. Since the delta encoded elements as shown in FIG. 3 are used, the processing, in an example embodiment, includes using the difference value 120 - 1 I, for example, to determine the correct value for Attribute 2. Processing continues at S 405 .

It is noted that the processing of S 404 A and S 404 B, according to example embodiments, contributes to determining at least part of a destination address responsive to a value of the difference flag.

At S 405 , the packet processor forwards the data packet in a unicast or multicast forwarding operation to the address(es) determined, by the packet processor, as indicated by the lines of memory. Processing continues at S 403 .

FIG. 4B is a flow diagram 4000 B of an example algorithm and method, according to example embodiments, when a data packet is received by the network device. In other words, the example embodiment of FIG. 4B is noted as an example of making at least a partial routing determination by determining at least part of a destination address responsive to a value indicated by a difference flag. One difference between the example embodiments of FIG. 4A and the example embodiments of FIG. 4B is that the latter includes operations related to the cache 130 as shown in FIG. 5 and described below.

The example method of FIG. 4B applies to multiple example embodiments in which the network device is utilized, for example, the system of FIG. 1 . Processing begins at S 401 B at which the network device receives a data packet during a network session. The network device, having a packet processor, determines that a linked list contains a plurality of attributes corresponding to a plurality of forwarding addresses and network values for a forwarding operation. Processing continues at S 402 B.

At S 402 B, the packet processor processes a line of memory corresponding to a first element of the linked list containing the attributes. The packet processor determines values from the attributes stored at the line of the memory, and processing continues at S 403 B.

At S 403 B, the packet processor stores the processed attributes of the current element of memory in a cache. Processing continues at S 404 B.

At S 404 B, the packet processor determines that the current element of memory points to a next line of memory. The packet processor reads an element of the linked list at the next line of memory. Processing continues at S 405 B.

At S 405 B, the packet processor reads the pointed-to line which also contains a set of attributes corresponding to additional values. The packet processor determines if the current element contains a difference indicated by a flag as a difference indicator or difference flag. If the difference flag of the current element indicates no difference processing continues at S 407 B. If the difference flag of the current element indicates a difference then processing continues at S 406 B.

At S 406 B, the packet processor processes only the attributes that are indicated as different from the attributes stored in the cache 130 . It is noted that a difference indicated at some position of a current element also indicates a difference at a corresponding position of the cache 130 . The packet processor then updates the corresponding attributes stored in the cache 130 as a result of the indicated difference. Processing continues at S 407 B.

At S 407 B, the packet processor reads the values, or attributes, stored in the cache and outputs a forwarding address or a plurality of forwarding addresses by which to forward the data packet. Processing continues at S 404 B to determine additional forwarding addresses for the forwarding operation.

The use of a cache in conjunction with a packet processor is shown in FIG. 5 .

FIG. 5 shows a system S 000 including a network device 110 and an expanded view 121 of the linked list 120 and an expanded view 131 of the cache 130 according to an example embodiment. The expanded view 131 of the cache 130 shows a status of values, or attributes, stored by the cache at different times, time t 0 130 - 0 , time t 1 130 - 1 , and time t 2 130 - 2 . Although the values shown as stored by the cache 130 in FIG. 5 are numerical values, this is merely an example embodiment, and the values stored by the cache 130 include a target port, a target MAC address, a priority, a VLAN, etc.

As indicated by the expanded view 121 , the first element 120 - 0 of the linked list 120 includes attribute 1 120 - 0 A to attribute N 120 - 0 D and these attributes and values correspond to those stored by the table of cache 130 at time t 0 130 - 0 .

According to an example embodiment, the attribute 120 - 0 A has a value 4 , attribute 120 - 0 B has a value 7 , and attribute 120 - 0 D has a value 9 .

The element 120 - 1 includes a difference indicator 120 - 1 G and corresponding difference type indicator 120 - 1 H and difference value 120 - 1 L. Likewise, the table of cache 130 at time t 1 illustrates that attribute 2 has been changed to a value of 4. Accordingly, the processor core 111 , a packet processor, is configured to obtain a forwarding address by reading the values from the cache 130 without the necessity of reading the remaining attributes 120 - 1 J of element 120 - 1 . Because the processing core 111 does not necessarily read all of the attributes for every entry in the linked list, but instead mostly processes attributes of entries that are different respective of previous entries, the demand on use of processing resources is potentially reduced in an embodiment.

The element 120 - 2 includes difference indicator 120 - 2 G, null indicator linked list 120 - 2 H, and next pointer 120 - 2 F. The difference indicator 120 - 2 G indicates that there is no difference between the attributes of element 120 - 2 and element 120 - 1 . Accordingly, the table of cache 130 at time t 1 130 - 1 is identical to the table stored at time t 2 130 - 2 .

Insertion of a new element into a delta encoded linked list is shown in FIG. 6 , according to an example embodiment.

FIG. 6 shows a comparison 6000 between a delta-encoded linked list 121 -A and a delta-encoded linked list 121 -B with an inserted element 120 -N.

The linked list 121 -A includes element 120 - 0 , element 120 - 1 , element 120 - 2 , and element 120 - 3 . Each element occupies a respective line of a memory.

The linked list 121 -B includes an inserted element 120 -N, causing differences between the elements of linked list 121 -A and the elements of linked list 121 -B as indicated by connector 601 .

The inserted element 120 -N does not affect any of the attributes or difference indicators of element 120 - 0 and element 120 - 1 . The next pointer of element 120 - 1 is updated to indicate that element 120 - 1 no longer points to element 120 - 2 , as in 121 -A, but now points to element 120 -N.

Additionally, a delta encoder and packet processor (not shown in FIG. 6 ) are used to determine a difference indicator to be stored at element linked list 120 -N as a difference between the attributes of element linked list 120 - 1 and linked list 120 -N.

Comparing linked list 121 -A with that of 121 -B, the linked list 121 -B includes a value field of element 120 -N which is different than a value at a corresponding position of element 120 - 1 . The element linked list 120 - 2 of linked list 121 -B includes a difference indicator in contrast with the difference indicator of the same element of linked list 121 -A; however, the attributes of the element 120 - 2 in each of linked list 121 -A and linked list 121 -B represent the same values of at least one destination address.

The delta encoder and packet processor update a difference indicator to be stored at element linked list 120 - 2 as a difference between the attributes of element linked list 120 -N and linked list 120 - 2 . As shown in linked list 121 -A, the difference indicator of element 120 - 2 indicates that there is no difference between element 120 - 1 and element 120 - 2 . As shown in linked list 121 -B, because at least one attribute, attribute 3, of element 120 -N is different than a corresponding attribute of element 120 - 1 , the difference indicator of element 120 - 2 is updated to represent a difference such that the at least one corresponding attribute, attribute 3, of element 120 - 2 is different than attribute 3 of element 120 -N.

Unicasting a packet by a packet processing system is now discussed with reference to FIG. 7 . FIG. 7 shows a system 7000 including network 100 , a packet 101 , and destination 104 . The destination is a forwarding location to which a packet 101 , received from network 100 , is forwarded or unicasted by the network device 110 .

The network device 110 , in the example seen, a packet processing system, includes at least one processor core 111 (denoted “CPU”), configured as at least a packet processor, a delta encoder 112 , and a memory 113 . The memory 113 includes a linked list 120 and a cache 130 .

The delta encoder/decoder 112 is configured to delta encode the linked list 120 of the memory 113 which stores a plurality of forwarding address and network values, including an address to the destination 104 , as elements of the linked list 120 . According to an example embodiment, the packet 101 is forwarded to destination 104 . Although FIG. 1 illustrates that the packet 101 is forwarded to a single destination, the memory 113 is configured to store a routing table in the linked list 120 by which any number of destinations are addressed through a packet multicasting operation.

Although the inventive concept has been described above with respect to the various example embodiments, it is noted that there can be a variety of permutations and modifications of the described features by those who are familiar with this field, without departing from the technical ideas and scope of the features, which shall be defined by the appended claims.

Further, while this specification contains many features, the features should not all be construed as limitations on the scope of the disclosure or the appended claims. Certain features described in the context of separate embodiments can also be implemented in combination. Conversely, various features described in the context of a single embodiment can also be implemented in multiple embodiments separately or in any suitable sub-combination.

Although the drawings describe operations in a specific order and/or show specific arrangements of components, one should not interpret that such specific order and/or arrangements are limited, or that all the operations performed and the components disclosed are needed to obtain a desired result. Accordingly, other implementations are within the scope of the following claims.