HK1220827B - A method of using bit vectors to allow expansion and collapse of header layers within packets for enabling flexible modifications and an apparatus thereof - Google Patents

Description

Method and apparatus for allowing expansion and collapse of header layer to achieve flexible modification

Technical Field

The present invention relates to packet header modification, and more particularly to a method and apparatus for using a bit vector to allow expansion and collapse of a header layer within a packet for flexible modification.

Background Art

Network packets carry data via protocols used by the Internet, such as Transmission Control Protocol/Internet Protocol/Ethernet (TCP/IP/Ethernet). A typical switch can modify various fields of an incoming packet before sending the packet out to its destination or to another switch. Incoming packets may be modified for a variety of reasons, such as where the packet will be forwarded, the protocols supported by the destination, the packet's priority, the format of the incoming protocol header, and so on. Because network protocols are constantly evolving, one or more fields in the protocol header may be optional, which complicates switch hardware because a given field within the protocol header may not always be at a fixed offset.

During modification of a packet, prior art switches process each protocol layer in the packet linearly. Such processing can produce performance issues related to the network, including latency, which may cause implementations to over-provision processing resources.

Summary of the Invention

An embodiment of an apparatus for modifying packet headers involves using a bit vector to allow expansion and collapse of protocol headers within a packet for flexible modification. A rewrite engine expands each protocol header into a universal format and applies various commands to modify the generalized protocol header. The rewrite engine maintains a bit vector for the generalized protocol header, where each bit in the bit vector represents a byte of the generalized protocol header. Bits marked as 0 in the bit vector correspond to invalid bytes, while bits marked as 1 in the bit vector correspond to valid bytes. The rewrite engine uses the bit vector to remove all invalid bytes after all commands have been applied to the generalized protocol header to thereby form a new protocol header.

In one aspect, a method for a rewrite engine is provided. The method includes maintaining a bit vector for a generalized protocol header. The generalized protocol header is a protocol header for a packet expanded into a general format. The general format includes all possible fields of the protocol. Regardless of which variant the protocol header corresponds to, each of the fields has the same offset. The bit vector includes a bit per byte for each byte of the generalized protocol header.

The method also includes updating the bit vector based on the modification to the at least one generalized protocol header.In some embodiments, the modification modifies the at least one generalized protocol header using at least one command from a set of general commands stored in a memory of the network switch.

The method also includes compressing at least one generalized protocol header using the updated bit vector. In some embodiments, before using the updated bit vector, an XOR operation is performed on the bit vector and the updated bit vector to determine how many bits have been changed, which allows the rewrite engine to take into account deleted and added bytes.

In another aspect, a method for a network switch is provided. The method includes receiving a packet at an incoming port of the network switch and generalizing each protocol header of the packet according to a common format for the protocol header. Missing fields are detected from the protocol header of the packet. Based on the detection, the protocol header is expanded to the common format by including the missing fields.

The method also includes maintaining a bit vector for each generalized protocol header. The bit vector includes bits marked as 0 for invalid fields and bits marked as 1 for valid fields.

The method also includes modifying at least one of the generalized protocol headers, thereby updating the bit vector. In some embodiments, the modification uses at least one command from a set of generalized commands stored in a memory of the network switch to modify the at least one generalized protocol header. In some embodiments, the modification of the at least one generalized protocol header is based on an egress port type of an egress port of the network switch.

The method also includes collapsing the updated bit vector.In some embodiments, the updated bit vector is collapsed by shifting the updated bit vector to remove each bit marked as 0 in the updated bit vector.

The method also includes forming a compact protocol header based on the collapsed bit vector. The packet having at least the compact protocol header is transmitted via an egress port of the network switch. In some embodiments, before transmitting the packet, the number of bytes added or deleted for all operations performed is counted.

In yet another aspect, a network switch is provided. The network switch includes an input port for receiving packets and a memory for storing a universal command set. The universal command set is used for header modification regardless of the incoming header. In some embodiments, the universal command set includes a delete command, a copy command, and a move command.

The network switch also includes a rewrite engine. The rewrite engine uses bit vectors to allow expansion and collapse of a packet's protocol header, thereby enabling flexible modification of the packet using a common command set.

In some embodiments, each of the protocol headers is generalized according to one of the software-defined mappings specific to the corresponding protocol. In some embodiments, the software-defined mapping is stored in a memory.

Each generalized protocol header includes a bit vector having bits marked as 0 for invalid fields and bits marked as 1 for valid fields. In some embodiments, the rewrite engine updates the bit vector after the generalized protocol header is modified. In some embodiments, the rewrite engine removes each bit marked as 0 in the updated bit vector to collapse the updated bit vector. A new header is formed based on the collapsed bit vector.

In some embodiments, the network switch also includes an egress port for transmitting the packet with the new header.

In yet another aspect, a network switch is provided. The network switch includes an input port for receiving packets, wherein the packets include a body and a protocol header. The network switch also includes an output port for transmitting modified packets. The network switch also includes a memory for storing a set of software-defined mappings of common formats for protocols and a set of common modification commands. Typically, the common modification command set is used for header modification regardless of the incoming header.

The network switch also includes a rewrite engine. The rewrite engine converts each protocol header of the protocol stack into a common format based on a software-defined mapping from a set of software-defined mappings, and maintains a bit vector for each converted protocol header. The bit vector includes a bit for each byte of the converted protocol header. The bit vector includes bits marked as 0 for invalid fields of the converted protocol header and bits marked as 1 for valid fields of the converted protocol header. The rewrite engine modifies each converted protocol header using a common modification command set, updates each bit vector following the bit vector, collapses each updated bit vector to thereby form a new protocol stack, and attaches a body to the new protocol stack for transmission via an output port.

BRIEF DESCRIPTION OF THE DRAWINGS

The foregoing will be apparent from the following more particular description of example embodiments of the invention, as illustrated in the accompanying drawings, in which like reference numerals refer to the same parts throughout the different views. The drawings are not necessarily to scale, emphasis instead being placed upon illustrating embodiments of the invention.

FIG. 1 illustrates an example protocol layer combination for a packet.

FIG2 illustrates an example structure of a local protocol table according to some embodiments of the present invention.

FIG3 illustrates an example method of a network switch according to some embodiments of the present invention.

FIG4 illustrates another example method of a network switch according to some embodiments of the present invention.

5 illustrates a diagram of header expansion of layers of an incoming packet into a common format according to some embodiments of the present invention.

6A-6B illustrate example generalizations of protocol headers according to some embodiments of the present invention.

7A-7C illustrate another example generalization of a protocol header according to some embodiments of the present invention.

8A-8C illustrate yet another example generalization of a protocol header according to some embodiments of the present invention.

9A-9F illustrate example modifications of a protocol header according to some embodiments of the present invention.

10A-10E illustrate another example modification of a protocol header according to some embodiments of the present invention.

FIG. 11 illustrates a method of rewriting an engine according to some embodiments of the present invention.

FIG. 12 illustrates yet another method of a network switch according to some embodiments of the present invention.

FIG. 13 illustrates yet another method of a network switch according to some embodiments of the present invention.

FIG. 14 illustrates yet another method of a network switch according to some embodiments of the present invention.

FIG. 15 illustrates yet another method of a network switch according to some embodiments of the present invention.

FIG16 illustrates another method of rewriting an engine according to some embodiments of the present invention.

FIG. 17 illustrates yet another method of a network switch according to some embodiments of the present invention.

FIG. 18 illustrates yet another method of rewriting an engine according to some embodiments of the present invention.

FIG. 19 illustrates yet another method of a network switch according to some embodiments of the present invention.

FIG20 illustrates an example diagram of a layer structure according to some embodiments of the present invention.

FIG. 21 illustrates yet another method of rewriting an engine switch according to some embodiments of the present invention.

FIG. 22 illustrates yet another method of a network switch according to some embodiments of the present invention.

DETAILED DESCRIPTION

In the following description, many details are set forth for illustrative purposes. However, one skilled in the art will recognize that the present invention can be practiced without these specific details. Therefore, the present invention is not intended to be limited to the embodiments shown, but is to be accorded the widest scope consistent with the principles and features described herein.

introduction

A network device, such as a network switch, is capable of switching/routing network traffic. The network switch includes at least one input/incoming port and at least one output/outgoing port for receiving and sending packets. In some embodiments, the network switch also includes a parser and a rewriter. The parser may include one or more parser engines for identifying the content of network packets, and the rewriter may include one or more rewrite engines for modifying packets before they are sent out of the network switch. The parser engine and the rewrite engine are flexible and operate on a programmable basis.

The network switch also includes a memory for storing data used by the network switch. For example, the memory stores a set of common commands. In short, the common commands are generally used to modify protocol headers. In another example, the memory also stores software-defined mappings of the common formats of the protocols. In short, each protocol header is represented according to one of the software-defined mappings specific to the corresponding protocol. As will become clear, these mappings can be used for different variants of the protocol and for different protocols, including new protocols. In yet another example, the memory also stores a protocol table. In short, the protocol table includes layer information for each protocol layer for each protocol layer combination programmed into the protocol table. In yet another example, the memory also stores counters and statistics.

In Ethernet, packets consist of multiple protocol layers. Each protocol layer carries different information. Some examples of well-known layers are:

Ethernet

PBB Ethernet

ARP

IPv4

IPv6

MPLS

FCOE

TCP

UDP

ICMP

IGMP

GRE

ICMPv6

VxLAN

TRILL

·CNM

In theory, the protocol layers can appear in any order. However, only some well-known combinations of these layers appear. Some examples of valid combinations of these layers are:

Ethernet

Ethernet, ARP

Ethernet, CNM

Ethernet, FCoE

Ethernet, IPv4

Ethernet, IPv4, ICMP

Ethernet, IPv4, IGMP

Unique group identifier

In some embodiments, the network switch supports 17 protocols and eight protocol layers. Therefore, there are ⁸¹⁷ possible protocol layer combinations. Figure 1 illustrates example protocol layer combinations for a packet. For example, a packet may include a three-protocol layer combination such as Ethernet, IPv4, and ICMP. For another example, a packet may include a seven-protocol layer combination such as Ethernet, IPv4, UDP, VxLAN, Ethernet, and ARP.

Although there are ⁸¹⁷ possible protocol layer combinations, only some known combinations of these layers occur. All known protocol layer combinations are uniquely identified and translated into a unique number called a packet identifier (PktID). The protocol table stored in the memory of the network switch is programmed to include layer information for each layer of each known protocol layer combination. In practice, the local protocol table includes fewer than 256 protocol layer combinations. In some embodiments, this local table includes 212 known protocol layer combinations. The local table can be programmed to include more or fewer protocol layer combinations.

FIG2 illustrates an example structure of a local protocol table 200 according to some embodiments of the present invention. Each protocol layer combination indexed by a PktID in the local table 200 includes information for each protocol layer of the protocol layer combination, which is shown as layer 0 information, layer 1 information, and layer N information. By indexing the PktID, information for all N layers of a packet can be accessed or obtained.

The information for each protocol layer includes at least the following information: layer type, layer data offset, and miscellaneous information. However, more information may be stored in the local table 200. In short, the layer type refers to the protocol associated with the protocol layer (e.g., IP/TCP/UDP/Ethernet), the layer data offset provides the starting position of the layer data in the protocol layer, and the miscellaneous information includes data such as checksum and length data.

Typically, the parser engine is able to identify the PktID of an incoming packet received at a network switch. The rewrite engine uses the PktID as a key to a protocol table, which provides the rewrite engine with all the information it needs to generalize each protocol layer of the packet for modification. In other words, the rewrite engine uses the PktID to access or obtain information for each of the protocol layers in the packet from the protocol table, rather than receiving parsing results from the parser engine.

Layer Type. A unique combination of the layer type and a hash of one or more fields of the packet provides the rewrite engine with a "universal format" for each protocol layer. In some embodiments, this unique combination specifies one of the software-defined mappings of the protocol's universal format stored in memory. The universal format is used by the rewrite engine to extend and modify protocol layers using software commands. This information also tells the rewrite engine where each protocol layer begins within the packet.

Layer Data Offset. The rewrite engine uses data to modify the incoming header layer. This data can be extended anywhere in the packet. Because layer sizes can vary, the offset to the data the rewrite engine needs to use during modification can vary, limiting the hardware flexibility of where and what data the rewrite engine can pick up.

The extracted data from the incoming packet header is arranged in a layered fashion. The extracted data structure is arranged so that the starting offset of the layer data structure is unique per PktID. The layer data offset for each layer is used to identify the location of the extracted data for modification. Since the structure of the layers within the packet and the location of the extracted data from the layers are identified by the packet's PktID, software and hardware use the same unique identifier to manage the extracted data, simplifying commands in the rewrite engine.

Miscellaneous information. Information such as checksum and length data informs the rewrite engine of special handling requirements for the associated protocol layer, such as checksum recalculation and header length update.

The packet generalization scheme allows software to define a small set of common commands that are completely based on a given protocol layer and independent of layers before or after it. The packet generalization scheme also provides hardware flexibility to future-proof itself against protocol changes and additions.

Figure 3 illustrates an example method 300 for a network switch according to some embodiments of the present invention.A network switch typically includes a parser engine and a rewrite engine.

The parser engine examines the incoming packet to identify the packet's PktID at step 305. In some embodiments, the parser engine passes the PktID to the rewrite engine instead of passing the parsed data of the packet to the rewrite engine.

The rewrite engine references a protocol table that defines different packet structures for packets received by the network switch at step 310. The rewrite engine uses the PktID as a key to the protocol table to extract information for each protocol layer of the packet necessary for modification.

In step 315, the rewrite engine modifies the packet based on the data stored in the protocol table. Typically, the rewrite engine extends each protocol layer of the packet before modifying the packet. Protocol layer extension and modification are discussed elsewhere.

Figure 4 illustrates another example method 400 for a network switch according to some embodiments of the present invention.A network switch typically includes memory and at least one incoming port.

At step 405, a protocol table is stored in memory. The protocol table defines different packet structures for packets. Each packet structure in the packet structure is indexed by a PktID. Each packet structure in the packet structure represents a protocol layer combination and includes layer information for each protocol layer in the protocol layer combination. The protocol table can be updated to add new packet structures representing new protocols. The protocol table can also be updated to modify the packet structure in response to protocol changes.

At step 410, a packet is received at an incoming port.

At step 415, the PktID of the packet is identified. In some embodiments, the parser engine identifies the PktID of the packet.

In step 420, information for each protocol layer of the packet is accessed. Typically, the information is located in a protocol table. In some embodiments, the information is used to generalize the protocol header of the packet according to a common format for the corresponding protocol. The common format is defined by software in memory.

As described elsewhere, the generalized protocol header can be modified by applying at least one command to the generalized protocol header. In some embodiments, the generalized protocol header is modified by using information to determine the location of data used to modify the generalized protocol header. The rewrite engine of the network switch typically generalizes the protocol header and modifies the generalized protocol header.

General format

As briefly explained above, the rewrite engine represents each protocol header of a packet in a generic format specific to the corresponding protocol to enable programmable modification of the packet, resulting in hardware and software flexibility in modifying the packet headers.

FIG5 illustrates a diagram 500 of header expansion of layers of an incoming packet into a common format according to some embodiments of the present invention. In FIG5 , the incoming packet includes eight protocol layers. Each protocol layer has a header for a corresponding protocol. More or fewer protocol layers are possible as indicated above. The rewrite engine is able to detect missing fields from any of the protocol headers as shown in FIG5 and expand each protocol header into its common format. A canonical layer refers to a protocol layer that has been expanded into its common format. In short, each canonical layer includes a bit vector having bits marked as 0 for invalid fields and bits marked as 1 for valid fields.

Figures 6A-8C illustrate examples of how the rewrite engine operates for the Ethernet protocol according to some embodiments of the present invention. The examples shown in Figures 6A-8C demonstrate that the rewrite engine can operate for different variants of a protocol such as the Ethernet protocol. Each example illustrates an incoming header for the Ethernet protocol and its corresponding general format. Although other protocols are not discussed, it is noted that the rewrite engine operates similarly for other protocols.

FIG6A illustrates the format 600 of an example Ethernet packet header for an incoming packet. Ethernet packet header 600 is 22 bytes and includes five fields: a source address (SA) field, a destination address (DA) field, a service VLAN tag field, a customer VLAN tag field, and an EtherType field. The SA and DA fields are each 6 bytes. The service VLAN tag field and the customer VLAN tag field are each 4 bytes. The EtherType field is 2 bytes. A packet with Ethernet packet header 600 is the largest variant of an Ethernet packet and has a maximum size of 22 bytes.

The rewrite engine processes Ethernet packet header 600 and determines that no fields are missing from Ethernet packet header 600. The general format of Ethernet packet header 600 is therefore the same as the general format of Ethernet packet header 600, as Ethernet packet header 600 contains all possible fields. FIG6B illustrates a bit vector 605 representing the Ethernet packet header 600 of FIG6A. Each bit of bit vector 605 corresponds to one byte of the 22 bytes of Ethernet packet header 600. Bit vector 605 contains all 1s, as all fields of Ethernet packet header 600 are valid or have values due to their presence in Ethernet packet header 600. Thus, Ethernet packet header 600 is represented by the general format {22'b111111_111111_1111_1111_11}.

FIG7A illustrates another example Ethernet packet header format 700 for an incoming packet. Ethernet packet header 700 is 18 bytes and includes only four fields: an SA field, a DA field, a Customer VLAN tag field, and an EtherType field. Ethernet packet header 700 lacks a Service VLAN tag field. A packet with Ethernet packet header 700 is another variant of an Ethernet packet.

The rewrite engine processes the Ethernet packet header 700 and determines that the Service VLAN Tag field is missing from the Ethernet packet header 700. The rewrite engine then extends the Ethernet packet header 700 to its maximum size of 22 bytes by including the missing Service VLAN Tag field at the appropriate location in the general format of the Ethernet packet header 700. FIG7B illustrates the general format 700′ of the extended Ethernet packet header. The extended Ethernet packet header 700′ includes all possible fields of the Ethernet protocol, including the missing Service VLAN Tag field. Valid fields in the extended Ethernet packet header 700′ are the SA field, the DA field, the Customer VLAN Tag field, and the EtherType field, as they exist in the Ethernet packet header 700. The invalid field in the extended Ethernet packet header 700′ is the Service VLAN Tag field, as it does not exist in the Ethernet packet header 700 but is added to the extended Ethernet packet header 700′.

FIG7C illustrates a bit vector 705 representing the extended Ethernet packet header 700′ of FIG7B . Each bit of bit vector 705 corresponds to one of the 22 bytes of the extended Ethernet packet header 700′. Bit vector 705 contains 1s for all valid fields, which are the SA field, DA field, customer VLAN tag field, and Ethertype field. Bit vector 705 contains 0s for all invalid fields, which is only the service VLAN tag field. Thus, Ethernet packet header 700 is represented by the general format {22′b111111_111111_0000_1111_11}.

FIG8A illustrates another example Ethernet packet header format 800 for an incoming packet. Ethernet packet header 800 is 14 bytes and includes only three fields: an SA field, a DA field, and an Ethertype field. Ethernet packet header 800 lacks a Service VLAN Tag field and a Customer VLAN Tag field. A packet with Ethernet packet header 800 is a minimal variant of an Ethernet packet.

The rewrite engine processes Ethernet header 800 and determines that the service VLAN tag field and the customer VLAN tag field are missing from Ethernet packet header 800. It then extends Ethernet packet header 800 to its maximum size of 22 bytes by including the missing service VLAN tag field and the missing customer VLAN tag field at appropriate locations in the general format of Ethernet packet header 800. FIG8B illustrates the general format 800′ of the extended Ethernet packet header. Extended Ethernet packet header 800′ includes all possible fields of the Ethernet protocol, including the missing service VLAN tag field and the missing customer VLAN tag field. Valid fields in extended Ethernet packet header 800′ are the SA field, the DA field, and the Ethertype field, as they exist in Ethernet packet header 800. Invalid fields in extended Ethernet packet header 800′ are the service VLAN tag field and the customer VLAN tag field, as they do not exist in Ethernet packet header 800 but are added to the extended Ethernet packet header 800′.

FIG8C illustrates a bit vector 805 of the extended Ethernet packet header 800′ of FIG8B . Each bit of bit vector 805 corresponds to one of the 22 bytes of the extended Ethernet packet header 800′. Bit vector 805 contains 1s for all valid fields, which are the SA field, the DA field, and the Ethertype field. Bit vector 805 contains 0s for all invalid fields, which are the Service VLAN Tag field and the Customer VLAN Tag field. Thus, Ethernet packet header 800 is represented by the general format {22′b111111_111111_0000_0000_11}.

As shown in Figures 6A-8C, regardless of variations in the incoming Ethernet header, once the Ethernet header expansion to a common format is performed, the field offsets remain the same as for a maximum-sized Ethernet header (e.g., Ethernet packet header 600 of Figure 6A). Header expansion advantageously allows the same set of software commands to operate regardless of the incoming Ethernet header because the Ethernet header is expanded to the maximum-sized Ethernet header. Thus, a command to modify the EtherType field, for example, will always point to the same offset regardless of which Ethernet header is received.

The common format of the header creates hardware and software flexibility in modifying the packet header. The hardware can modify the packet header regardless of where the fields reside within the packet header. The hardware can be programmed by software to support new protocols. The software programs the common format in the hardware tables for the various header protocols.

Assumption 1 (Incoming Packet is a Single-Tagged Ethernet Packet, Outgoing Packet is an Untagged Ethernet Packet): Assume that an input Ethernet port of a network switch is receiving packets with a customer VLAN tag, and the packets need to be forwarded untagged to an output Ethernet port. FIG9A illustrates the format 900 of an example Ethernet packet header for a packet received at this incoming Ethernet port. For a packet received at this incoming Ethernet port, the software programs the general format of the Ethernet header as {22'b111111_111111_0000_1111_11}. The rewrite engine receives the header protocol layer and indexes into memory, which tells the hardware that the general format for this header protocol is {22'b111111_111111_0000_1111_11}. In this case, the hardware expects the first 12 consecutive bytes (each labeled 1) and the next six bytes (each labeled 1) to be shifted by four bytes. The four bytes corresponding to the four bits labeled 0 in the bit vector are invalid.

Based on the general format {22'b111111_111111_0000_1111_11}, the rewrite engine extends the incoming header protocol layer into the extended header 905 shown in FIG9B and maintains a per-byte bit for each byte of the extended header layer 905. The corresponding bit vector 910 for the extended header 905 is shown in FIG9C. The bit vector 910 tells the hardware which bytes are valid and which are invalid.

Based on the forwarding decision, in this assumption 1, the packet needs to be forwarded untagged. The hardware indexes into a command table based on the egress port type of the outgoing Ethernet port, which tells the hardware to remove the customer VLAN tag. The customer VLAN tag always starts at a fixed offset, namely 16. Since the commands are applied to the general format, the command to remove the customer VLAN tag is "delete 4 bytes (of the customer VLAN tag) starting at position 16." The hardware simply marks these four bytes as invalid and deletes them. Figure 9D illustrates the untagged Ethernet header 915 in the general format. Figure 9E illustrates the bit vector 920 for the untagged Ethernet header 915. After removing all invalid bytes, the hardware forms the new header 925 shown in Figure 9F. The packet with the new header 925 is sent out via the outgoing Ethernet port.

Assumption 2 (Incoming Packet is a Double-Tagged Ethernet Packet, Outgoing Packet is an Untagged Ethernet Packet): Assume that an input Ethernet port of a network switch receives a packet with a service VLAN tag and a customer VLAN tag, and the packet needs to be forwarded untagged to an output Ethernet port. FIG10A illustrates the format 1000 of an example Ethernet packet header for a packet received at this incoming Ethernet port. For a packet received at this incoming Ethernet port, the software programs the general format of the Ethernet header as {22'b111111_111111_1111_1111_11}. The rewrite engine receives the header protocol layer and indexes into memory, which tells the hardware that the general format for this header protocol is {22'b111111_11111_1111_1111_11}. In this case, the hardware expects all 22 consecutive bytes (each labeled 1) to be 1.

Based on the general format {22'b111111_111111_1111_1111_11}, the rewrite engine does not need to expand the incoming header protocol layer because the header protocol is already at its maximum size. The corresponding bit vector 1005 for the header 1000 is shown in Figure 10B. The bit vector 1005 tells the hardware which bytes are valid and which are invalid.

Based on the forwarding decision, in this assumption 2, the packet needs to be forwarded untagged. The hardware indexes into a command table based on the egress port type of the outgoing Ethernet port, which tells the hardware to remove the customer VLAN tag and the service VLAN tag. The customer VLAN tag always starts at a fixed offset, namely 16. Similarly, the service VLAN tag always starts at a fixed offset, namely 12. Since the commands are applied to the universal format, the command to remove the customer VLAN tag is "delete 4 bytes (of the customer VLAN tag) starting at position 16," while the command to remove the service VLAN tag is "delete 4 bytes (of the service VLAN tag) starting at position 12." The hardware simply marks these eight bytes as invalid and deletes them. Figure 10C illustrates the untagged Ethernet header 1010 in the universal format. Figure 10D illustrates the bit vector 1015 for the untagged Ethernet header 1010. After removing all invalid bytes, the hardware forms the new header 1020 shown in Figure 10E. The packet with the new header 1020 is sent out via the outgoing Ethernet port.

Assumption 3 (Incoming packet is an untagged, single-tagged, or double-tagged Ethernet packet, outgoing packet is a double-tagged Ethernet packet): Assume that an input Ethernet port of a network switch is receiving a packet that is untagged, has a service VLAN tag, a customer VLAN tag, or both tags, and the packet needs to be forwarded to an output Ethernet port as a double-tagged packet, but with a new tag. If the incoming packet is double-tagged, the software programs the Ethernet header in the general format of {22'b111111_111111_1111_1111_11}. If the incoming packet is untagged, the software programs the Ethernet header in the general format of {22'b111111_111111_0000_0000_11}. If the incoming packet is single-tagged, the software programs the Ethernet header in the general format of {22'b111111_111111_0000_1111_11}.

Based on the forwarding decision, in this assumption 3, the packet needs to be forwarded with a double tag. The hardware indexes into a command table based on the egress port type of the outgoing Ethernet port, which tells the hardware to replace the customer VLAN tag and the service VLAN tag. The customer VLAN tag always starts at a fixed offset, namely 16. Similarly, the service VLAN tag always starts at a fixed offset, namely 12. For each of these cases, the commands are the same. Since the commands are applied to the common format, the commands are "copy 4 bytes from layerdata.positionX to start position=12 (for service VLAN tag)" and "copy 4 bytes from layerdata.positionY to start position=16 (for customer VLAN tag)", where the content is copied from the locations specified by layerdata.positionX and layerdata.positionY.

As demonstrated in assumptions 1-3, the rewrite engine is simplified in hardware and keeps the set of software commands in memory small. Thus, the hardware memory required to hold the commands is shallow.

Figure 11 illustrates a method 1100 of a rewrite engine according to some embodiments of the present invention. At step 1105, the rewrite engine detects missing fields from the protocol header of an incoming packet.

At step 1110, based on the detection, the rewrite engine expands the protocol header into a common format for the corresponding protocol. The common format includes all fields of the protocol. Each field in the field has the same offset regardless of which variant of the protocol the protocol header corresponds to. The rewrite engine maintains a bit vector for the expanded protocol header, where the bit vector includes a bit per byte for each byte of the expanded protocol header. The rewrite engine marks a bit as available for each byte of each valid field, where each valid field is a field that exists in the protocol header of the incoming packet. The rewrite engine marks a bit as invalid for each byte of each invalid field, where each invalid field is a field that does not exist in the protocol header of the incoming packet.

In some embodiments, steps 1105 and 1110 are performed for each protocol layer of the incoming packet.

FIG12 illustrates another method 1200 for a network switch according to some embodiments of the present invention. In some embodiments, the network switch allows software-defined mapping of common formats for protocols and stores the software-defined mapping in memory of the network switch. The network switch includes a rewrite engine for generalizing protocol headers. In step 1205, a packet is received at an incoming port of the network switch.

At step 1210, the protocol header of the packet is generalized according to a common format for the corresponding protocol. As described above, the hardware extends the protocol header according to one of the mappings stored in the memory of the network switch. The bit vector for the extended protocol header tells the hardware which bytes are valid and which are invalid.

The generalized protocol header is modified by applying at least one command to the generalized protocol header at step 1215. As explained above, the hardware indexes into the command table based on the egress port type of the outgoing Ethernet port to determine at least one command to apply to the protocol header.

At step 1220, all invalid bytes of the modified protocol header are removed to form a new header.

At step 1225, the packet with the new header is sent out via the egress port of the network switch.

Figure 13 illustrates another method 1300 of a network switch according to some embodiments of the present invention. At step 1305, the network switch is configured to include a software-defined mapping of a common format for a protocol. The software-defined mapping is stored in a memory of the network switch.

At step 1310, a packet is received at an incoming port of a network switch.

At step 1315, the protocol header of the packet is generalized based on one of the mappings defined by the software.

A bit vector is maintained for the generalized protocol header at step 1320. The bit vector includes a bit per byte for each byte of the generalized protocol header.

Optimized representation of generalized protocol headers

Each incoming layer can contain any number of bytes, such as 64 bytes or 128 bytes or even a larger number of bytes. In the above example, the extended Ethernet header has 22 bytes. Representing all bytes of the protocol layer in a bit vector is not efficient because the allocation for the worst-case protocol is memory intensive. In modern system-on-chip (SOC) designs, the area and power budget of embedded memory often dominates the overall chip budget. As a result, efficiently utilizing limited memory resources is critical.

If most protocols have a few "holes" or invalid bytes, it is more cost-effective to represent the universal format header with a counter of consecutive bytes and a smaller bit vector representing the non-consecutive bytes. In some embodiments, the size of this smaller bit vector is generally fixed, but the size can be programmable. The size can be adjusted based on protocol statistics that determine the maximum number of non-consecutive bytes that must be stored to represent the protocol.

In some embodiments, each generic format header of a packet is represented in an optimized manner using a data structure comprising two fields: a continuation_bytes field and a bit vector field. The continuation_bytes field indicates the number of consecutive valid bytes from the beginning of the protocol layer. The bit vector field is a bit representation of each byte of the protocol layer. The bit vector field indicates "holes" or invalid bytes. The bit vector field can accommodate most protocols, if not all. Therefore, the optimized representation can be represented by {continuation_bytes, bit vector}. This data structure is independent of the size of the protocol header.

For example, a compact representation of the bit vector 605 of Figure 6B is {22,00000000_0000_000}, which represents 22 consecutive bytes from the beginning of the Ethernet packet header 600 of Figure 6A. The bit vector field contains all zeros because there are no invalid bytes.

For another example, the compact representation of the bit vector 705 of FIG. 7C is {12,00001111_1100_000}, which represents 12 consecutive bytes from the beginning of the extended Ethernet packet header 300' of FIG. 7B, followed by four invalid bytes, and then six valid bytes.

For yet another example, the compact representation of the bit vector 805 of FIG. 8C is {12, 000000000_1100_0000), which represents 12 consecutive bytes from the beginning of the extended Ethernet packet header 800′ of FIG. 8B , followed by eight invalid bytes, and then two valid bytes.

FIG14 illustrates another method 1400 for a network switch according to some embodiments of the present invention. At step 1405, an extended protocol header is obtained. As discussed above, an extended protocol header is a protocol header of an incoming packet that has been generalized according to a common format for a corresponding protocol. Typically, a rewrite engine generalizes a protocol header by detecting missing fields from the protocol header and, based on the detection, extending the protocol header according to the common format. The common format includes all possible fields of the protocol, with each field having the same offset regardless of the protocol variant to which the protocol header corresponds.

A representation of the extended protocol header is maintained at step 1410. The representation is a data structure including a continuation_byte field and a bit vector field.

At step 1415, the Continue_Bytes field is set to the number of consecutive valid bytes from the start of the extended protocol header.

At step 1420, for each byte of each invalid field following consecutive valid bytes, a bit of the bit vector field is marked as unavailable. Each invalid field is a field that is not present in the protocol header of the incoming packet.

At step 1425, for each byte of each valid field following the consecutive valid bytes, a bit of the bit vector field is marked as available. Each valid field is a field present in the protocol header of the incoming packet.

Figure 15 illustrates yet another method 1500 of a network switch according to some embodiments of the present invention.At step 1505, a packet is received at an incoming port of the network switch.

At step 1510, the protocol headers of the packets are generalized according to a common format for the corresponding protocol. Typically, the rewrite engine is configured to generalize the protocol headers.

The generalized protocol header is represented in a data structure that is independent of the size of the protocol header at step 1515. In some embodiments, the data structure includes a continuation_bytes field and a bit vector field, wherein the continuation_bytes field indicates the number of consecutive valid bytes from the beginning of the protocol header, and the bit vector field is a bit representation of each byte of the protocol header.

This data structure helps to generalize the representation for various protocol layers and removes the dependency on the size of the protocol header layer.The compact representation of the bit vectors advantageously reduces hardware costs.

General commands for header modification

The modification uses a set of common commands that are applied to the extended protocol header. All commands are therefore common since they are independent of the incoming header (eg size and protocol).

Table 1 lists the generic commands used by the rewrite engine for protocol header modification. This small set of generic commands is used for header modification regardless of the incoming packet header (e.g., size, protocol) because the packet header is normalized before modification. Typically, the generic commands are expressed as microcode for software programming.

Table 1

The DELETE command deletes Size bytes starting at the Start position within the current generalized protocol layer by invalidating those bytes, marking the bits of the bit vector representing those bytes as 0.

The COPY command copies Size bytes of data from the SourceOffset of the Source to the DestinationOffset of the current generalized header layer. The COPY command makes the corresponding destination byte valid or invalid depending on whether the validity of the data is valid in the Source. The bits of the bit vector representing invalid bytes are marked as 0. The bits of the bit vector representing valid bytes are marked as 1. The COPY command can also use Bitmask for bit mask operations. The COPY command can also use copyConstantBitMask and copyConstantData. If copyConstantBitMask contains "1" at the bit position, the corresponding positioned bytes from copyConstantData are copied to the current generalized header layer at the corresponding position. In some embodiments, constant data is stored in a table. In some embodiments, constant data is defined by software.

The MOVE command moves Size bytes within the current generalized protocol layer from StartOffset to DestinationOffset. The MOVE command validates or invalidates the corresponding destination bytes, depending on whether the data is valid in Source, and invalidates the source bytes. Bits in the bit vector representing invalid bytes are marked as 0. Bits in the bit vector representing valid bytes are marked as 1.

The number of bytes added or deleted is counted for all operations performed using at least one counter. The at least one counter is a hardware counter. Alternatively, the at least one counter is a software counter. The at least one counter keeps track of the count for statistical purposes and for other reasons. In some embodiments, the rewrite engine performs an XOR operation on two bit vectors—the original bit vector and the modified bit vector—to inform the hardware of how many bits have changed, which is used to account for the number of bytes deleted or added.

Figure 16 illustrates another method 1600 of a rewrite engine according to some embodiments of the present invention. The rewrite engine is part of a network switch and modifies packets before they are sent out of the network switch. In step 1605, the protocol header is generalized according to a common format for each protocol header of the packet. The common format includes all possible fields of the protocol. In this way, no matter which variant of the protocol the protocol header corresponds to, each field has the same offset. Each generalized protocol header includes a bit vector. The bit vector includes a bit for each byte of the generalized protocol header. The bit vector includes bits marked as 0 for invalid fields and bits marked as 1 for valid fields. Here, an invalid field is a field that does not exist in the protocol header of the received packet, and a valid field is a field that exists in the protocol header of the received packet.

At step 1610, at least one command from a set of general commands stored in a memory of the network switch is used to modify at least one generalized protocol header. The modification of the at least one generalized protocol header is based on an egress port type of an egress port of the network switch. The modification of the at least one generalized protocol header causes a bit vector to be updated.

Since the common command set is used for header modification regardless of the incoming packet header, the common command set can be used to modify the packet header of the first variant of the protocol and to modify the packet header of the second variant of the protocol. Similarly, the common command set can be used to modify the packet header of the first protocol and to modify the packet header of the second protocol.

Figure 17 illustrates yet another method 1700 of a network switch according to some embodiments of the present invention. At step 1705, a common command set is maintained in a memory of the network switch.

At step 1710, a packet is received at an incoming port of a network switch.

At step 1715, each protocol header of the packet is generalized according to a common format for the protocol header. Missing fields from the protocol header of the packet are detected. Based on the detection, the protocol header is expanded to the common format by including the missing fields. Each generalized protocol header includes a bit vector having bits marked as 0 for invalid fields and bits marked as 1 for valid fields. Here, an invalid field is a field that is not present in the protocol header of the received packet, and a valid field is a field that is present in the protocol header of the received packet.

At step 1720, the generalized protocol headers are modified by applying at least one command from the common command set to at least one of the generalized protocol headers, thereby updating the bit vector.

At step 1725, a new protocol header is formed based on the updated bit vector.

The packet with the new protocol header is transmitted via the egress port of the network switch at step 1730. In some embodiments, before transmitting the packet with the new protocol header, the number of bytes added or deleted is counted for all operations performed.

Using bit vectors to collapse modified protocol headers

The rewrite engine not only uses the bit vector for each protocol header to allow modification of the extension of the protocol header based on the general format, but also uses the bit vector to allow the protocol header to be collapsed from the general format into a "regular" header. In general, each bit in the bit vector represents a byte of the generalized protocol header. Bits marked as 0 in the bit vector correspond to invalid bytes, while bits marked as 1 in the bit vector correspond to valid bytes. The rewrite engine uses the bit vector to remove all invalid bytes after all commands have been operated on the generalized protocol header to thereby form a new protocol header. The rewrite engine therefore uses the bit vector to allow the expansion and collapse of the protocol header of the packet, thereby achieving flexible modification of the packet by using a general set of commands.

For example, referring back to Hypothesis 1, bit vector 920 of FIG. 9E represents the modified protocol header 915 of FIG. 9D after a delete command has been applied to the generalized protocol header 905 of FIG. 9B . In this Hypothesis 1, the customer VLAN tag is deleted, thereby invalidating four bytes of the customer VLAN tag. Thus, the bits corresponding to the customer VLAN tag in bit vector 920 are marked as 0. After all commands have been executed, namely the delete command in Hypothesis 1, the rewrite engine uses bit vector 920 to remove all invalid bytes, thereby collapsing bit vector 920. A new protocol header is formed based on the collapsed bit vector. FIG. 9F illustrates the new protocol header 925 after all invalid bytes have been removed. The packet in Hypothesis 1 with the new header 925 is transmitted via the outgoing Ethernet port.

For another example, referring back to Hypothesis 2, bit vector 1015 of FIG. 10D represents the modified protocol header 1010 of FIG. 10C after a delete command has been applied to protocol header 1000 of FIG. 10A . In this Hypothesis 2, the service VLAN tag and the customer VLAN tag are deleted, thereby invalidating four bytes of the service VLAN tag and four bytes of the customer VLAN tag. Thus, the bits corresponding to the service VLAN tag and the customer VLAN tag in bit vector 1015 are marked as 0. After all commands have been executed, namely the two delete commands in Hypothesis 2, the rewrite engine uses bit vector 1015 to remove all invalid bytes, thereby collapsing bit vector 1015. A new protocol header is formed based on the collapsed bit vector. FIG. 10E illustrates the new protocol header 1020 after all invalid bytes have been removed. The packet in Hypothesis 2 with the new header 1020 is transmitted via the outgoing Ethernet port.

FIG18 illustrates another method 1800 of a rewrite engine according to some embodiments of the present invention. The rewrite engine is part of a network switch and modifies packets before they are sent out of the network switch. At step 1805, a bit vector is maintained for each generalized protocol header. A generalized protocol header is a protocol header for a packet expanded into a general format. The general format includes all possible fields of the protocol. Regardless of which variant the protocol header corresponds to, each field has the same offset. The bit vector includes a bit per byte for each byte of the generalized protocol header.

At step 1810, a bit vector is updated based on a modification to at least one generalized protocol header.The modification modifies the at least one generalized protocol header using at least one command from a set of general commands stored in a memory of the network switch.

At least one generalized protocol header is compressed using the updated bit vector at step 1815. In some embodiments, prior to step 1815, an XOR operation is performed on the bit vector and the updated bit vector to determine how many bits changed, which allows the rewrite engine to account for deleted and added bytes.

Figure 19 illustrates yet another method 1900 of a network switch according to some embodiments of the present invention.At step 1905, a packet is received at an incoming port of the network switch.

At step 1910, the protocol header is generalized according to a common format for each protocol header of the packet. Missing fields are detected from the protocol header of the packet. Based on the detection, the protocol header is extended to the common format by including the missing fields.

A bit vector is maintained for each generalized protocol header at step 1915. The bit vector includes bits marked as 0 for invalid fields and bits marked as 1 for valid fields.

At step 1920, at least one of the generalized protocol headers is modified, thereby updating the bit vector. The modification uses at least one command from a set of generalized commands stored in a memory of the network switch to modify the at least one generalized protocol header. The modification of the at least one generalized protocol header is based on an egress port type of an egress port of the network switch.

At step 1925 , the updated bit vector is collapsed by shifting the updated bit vector to remove each bit marked as 0 in the updated bit vector.

At step 1930, a compact protocol header is formed based on the collapsed bit vector. The packet with at least the compact protocol header is transmitted via an egress port of the network switch. In some embodiments, before transmitting the packet, the number of bytes added or deleted for all operations performed is counted.

Pointer structure

The pointer structure can be used to extract the different protocol layers within the generalized incoming packet and reconstruct the packet after the modification of the protocol layers. The pointer structure includes N+1 layer pointers and the total size of all headers of the packet. Typically, the pointer structure is initially updated with the following data, which is provided by the parser engine for the rewrite engine to use to split the packet into various layers and then intelligently splice them back together. After the packet is split into various layers, the rewrite engine generalizes the protocol header, modifies the generalized protocol header, and compresses the generalized protocol header by removing all invalid fields. The layer pointers are updated by the rewrite engine after each layer is modified. These updated layer pointers are used to splice the different protocol layers back together before sending the packet out of the network switch.

FIG20 illustrates an example diagram 2000 of a layer structure according to some embodiments of the present invention. Assume that an incoming packet includes the following protocol layers: proprietary header, Ethernet, IPv4, UDP, VxLAN, and Ethernet. Also assume that the parser engine of the network switch is capable of parsing up to eight layers while the rewrite engine can only modify the first N, say N=4, protocol layers (due to software requirements and/or hardware capabilities). In some embodiments, the parser engine provides data to the rewrite engine, such as the starting position of each protocol header of the packet.

Since the rewrite engine is able to modify the first four protocol layers of a packet, the rewrite engine only uses the relevant data from the parser engine, namely data about the first four protocol layers as follows: proprietary header, Ethernet, IPv4 and UDP. Using this data, the pointer structure for the packet is initialized: layer pointer 0 is set to 0, which is the starting position within the packet for the proprietary header (i.e., layer 0), layer pointer 1 is set to 16, which is the starting position within the packet for the Ethernet header (i.e., layer 1), layer pointer 2 is set to 36, which is the starting position within the packet for the IPv4 header (i.e., layer 2), layer pointer 3 is set to 48, which is the starting position within the packet for the UDP header (i.e., layer 3), and layer pointer 4 is set to 56, which is the starting position for the remainder of the header that the rewrite engine does not modify. In some embodiments, the rewrite engine calculates the size of the header and sets the header size (i.e., the total size of all headers) to 223.

By using the layer pointer, the rewrite engine generalizes the first four protocol layers (i.e., private header, Ethernet, IPv4, UDP) as discussed above for modification. After modification, the rewrite engine compresses the modified protocol header by removing all invalid bytes. Typically, the layer pointer is updated after modifying the protocol header.

The layer pointer forms the tail pointer. The tail pointer, along with the header size, is associated with the body of the header, which is the portion of the header that is unmodified and forwarded for subsequent splicing. After all modifications have been performed and the modified protocol header has been compressed, the modified layer pointer is used to splice the modified header back together with the body of the header.

The rewrite engine can be limited to the number of layers it can modify. In some embodiments, the rewrite engine can also be limited to how much it can expand any given protocol layer. In such an embodiment, the rewrite engine extracts the size of a protocol layer by subtracting two adjacent layer pointers. If the layer size exceeds the rewrite engine's hardware capabilities, the rewrite engine simply uses the previous layer pointer and intelligently forms the body.

Assume that the protocol layer cannot be extended by more than 40 bytes, but the maximum variant of the associated protocol is 64 bytes. In some embodiments, the rewrite engine extends the header protocol to a maximum of 40 bytes for modification. After the modification, using the layer pointer, the rewrite engine can similarly splice the remaining bytes to the modified bytes.

Using layer pointers significantly reduces hardware logic and complexity, as it only needs to address a given protocol layer. Hardware commands are limited in scope to a given layer. Since the command engine has no dependencies on previous or subsequent layers, the command hardware can be used in a multi-pass fashion if more commands are required per layer. In other words, since commands have no internal state associated with them, multiple commands can be used in parallel. Similarly, multiple layers can be modified in parallel.

FIG21 illustrates another method 2100 of a rewrite engine according to some embodiments of the present invention. The rewrite engine is part of a network switch and modifies packets before they are sent out of the network switch. In step 2105, a pointer structure is maintained for each packet. The pointer structure includes a layer pointer and the total size of all headers of the packet. Each layer pointer corresponds to the starting position of the associated layer in the packet.

The pointer structure consists of N+1 layer pointers. The rewrite engine modifies N layers of the packet. The layer pointers form the tail pointer. The tail pointer, along with the total size, indicates the header body. The header body is the portion of the header that is not modified by the rewrite engine.

At step 2110, the layers of the packet are split for layer modification based on the layer pointers. Missing fields are detected from the protocol header of the packet. Based on the detection, the protocol header is expanded into a common format for the corresponding protocol. The common format includes all possible fields of the protocol. Regardless of the protocol variant to which the protocol header corresponds, each field has the same offset. Each generalized protocol header includes a bit vector having bits marked as unavailable or 0 for invalid fields and bits marked as available or 1 for valid fields. The generalized protocol header is modified using at least one command from the common command set. Typically, the bit vector is updated after the modification.

In step 2115, the layer pointer is updated based on the layer modification.

At step 2120, the layers are stitched back together based on the updated layer pointers.

Figure 22 illustrates yet another method 2200 of a network switch according to some embodiments of the present invention.At step 2205, a packet is received at an incoming port of the network switch.

At step 2210, a pointer structure is used to separate the protocol layers of the packet. The pointer structure includes N+1 layer pointers pointing to N+1 locations in the packet and the total size of all headers of the packet. The location includes the starting position of the protocol layer. The pointer structure is initialized based on the parsed data of the packet.

At step 2215, the separated protocol layers are generalized for modification. For each layer, the size of the layer is extracted to determine whether the size exceeds the hardware capabilities for modifying the layer. The size is extracted by subtracting two adjacent layer pointers in the pointer structure. Based on this determination, the first of the two adjacent layer pointers is used and the body is formed.

At step 2220, the pointer structure is updated based on the modification.

At step 2225, the updated pointer structure is used to intelligently stitch the modified protocol layers back together to form a new protocol header.

At step 2230, the packet with the new protocol header is sent out via the egress port of the network switch.

Those skilled in the art will recognize that other uses and advantages exist. Although the present invention has been described with reference to numerous specific details, those skilled in the art will recognize that the present invention can be embodied in other specific forms without departing from the spirit of the invention. Therefore, those skilled in the art will understand that the present invention is not limited by the foregoing illustrative details, but is defined by the appended claims.

Claims (24)

1. A method for rewriting an engine of a network switch, the method comprising: maintaining a bit vector for a generalized protocol header layer of a packet, wherein the bit vector comprises a plurality of values, each value representing a byte of the generalized protocol header layer, wherein the generalized protocol header layer is a protocol header layer of the packet extended to a common format; updating the bit vector based on modifications to the generalized protocol header layer; and The generalized protocol header layer is compressed using the updated bit vector by removing fields from the generalized protocol header layer based on the updated bit vector. 2. A method for rewriting an engine of a network device, the method comprising: A generalized protocol header layer maintenance bit vector for the packet; updating the bit vector based on modifications to the generalized protocol header layer; and The generalized protocol header layer is compressed using the updated bit vector, wherein the generalized protocol header is the protocol header layer of the packet extended into a common format, and further wherein the common format includes all possible fields supported by a protocol of the protocol header layer, wherein each of the fields has the same offset regardless of which variant of the protocol the protocol header layer corresponds to. 3. The method of claim 1, wherein the bit vector comprises a bit for each byte of the generalized protocol header layer. 4. The method of claim 1 , wherein the modifying modifies the generalized protocol header layer using at least one command from a generic command set stored in a memory of the network switch, wherein the generic command set includes a delete command, a copy command, and a move command. 5. A method for rewriting an engine of a network device, the method comprising: maintaining a bit vector for a generalized protocol header, wherein the generalized protocol header is a protocol header extended to a common format; updating the bit vector based on a modification to at least one generalized protocol header; compressing the at least one generalized protocol header using the updated bit vector; and Before using the updated bit vector, an XOR operation is performed on the bit vector and the updated bit vector to determine how many bits are changed. 6. A method for a network switch, the method comprising: receiving a packet at an incoming port of the network switch, the packet having a header including a plurality of protocol header layers; generalizing each of the protocol header layers according to a common format for the protocol header layers of the packet, thereby forming a generalized protocol header layer; maintaining a bit vector for each of the generalized protocol header layers, wherein the bit vector comprises a plurality of values, each value representing a byte of the generalized protocol header layer, and further wherein the bit vector comprises bits marked as 0 for invalid fields and bits marked as 1 for valid fields; modifying at least one of the generalized protocol header layers and updating a bit vector associated with the at least one of the generalized protocol header layers, thereby forming an updated bit vector; compressing the updated bit vector to form a compressed bit vector; and A new protocol header is formed based on the compressed bit vector. 7. The method of claim 6 , wherein generalizing each of the protocol header layers comprises: detecting missing fields from the protocol header layer of the packet; and Based on the detecting, the protocol header layer is extended to the common format by including the missing fields. 8. The method of claim 6 , wherein the modifying modifies the at least one generalized protocol header layer in the generalized protocol header layer using at least one command from a general command set stored in a memory of the network switch, wherein the general command set includes a delete command, a copy command, and a move command. 9. The method of claim 6, wherein the modification of the at least one of the generalized protocol header layers is based on an egress port type of an egress port of the network switch. 10. A method for a network switch, the method comprising: receiving a packet at an incoming port of the network switch, the packet having a header including a plurality of protocol header layers; generalizing each of the protocol header layers according to a common format for the protocol header layers of the packet, thereby forming a generalized protocol header layer; maintaining a bit vector for each of the generalized protocol header layers, wherein the bit vector includes bits marked as 0 for invalid fields and bits marked as 1 for valid fields; modifying at least one of the generalized protocol header layers and updating the bit vector to form an updated bit vector; compressing the updated bit vector to form a compressed bit vector; and A new protocol header is formed based on the compressed bit vector, wherein compressing the updated bit vector includes shifting the updated bit vector by removing each bit marked as 0 in the updated bit vector. 11. The method of claim 6, further comprising transmitting the packet with at least the new protocol header via an egress port of the network switch. 12. A method for a network switch, the method comprising: receiving a packet at an incoming port of the network switch, the packet having a header including a plurality of protocol header layers; generalizing each of the protocol header layers according to a common format for the protocol header layers of the packets, thereby forming a generalized protocol header layer; maintaining a bit vector for each of the generalized protocol header layers, wherein the bit vector includes bits marked as 0 for invalid fields and bits marked as 1 for valid fields, each of the bits indicating the validity of each byte in a field of the corresponding protocol header layer; modifying at least one of the generalized protocol header layers and updating the bit vector to form an updated bit vector; compressing the updated bit vector to form a compressed bit vector; forming a new protocol header based on the compressed bit vector; and Before transmitting said packet with at least said new protocol header, the number of bytes added or deleted for all operations performed is counted. 13. A network switch comprising: Input port, used to receive packets; a memory storing a universal command set, wherein the universal command set is used for protocol header layer modification regardless of which of the supported protocol variants the incoming protocol header layer is, wherein the universal command set includes a delete command, a copy command, and a move command; and a rewrite engine that uses bit vectors to allow expansion and compression of the protocol header layer of the packet, thereby enabling flexible modification of the packet by using the universal command set, wherein each bit vector in the bit vectors includes a plurality of values, each value representing a byte of the protocol header layer to which the bit vector corresponds, and wherein the protocol header layer is the protocol header layer of the packet expanded into a universal format. 14. The network switch of claim 13 , wherein each of the protocol header layers is generalized according to one of a plurality of software-defined mappings specific to the protocol of the protocol header layer, wherein the generalized protocol header layer is a protocol header layer of the packet extended to a common format. 15. The network switch of claim 14, wherein the software-defined mapping is stored in the memory. 16. The network switch of claim 14, wherein each generalized protocol header layer includes a bit vector having bits marked as 0 for invalid fields and bits marked as 1 for valid fields. 17. The network switch of claim 16, wherein the rewrite engine updates the bit vector after the generalized protocol header layer is modified. 18. The network switch of claim 17, wherein the rewrite engine compresses the updated bit vector by removing each bit marked as 0 in the updated bit vector. 19. The network switch of claim 18, wherein a new protocol header layer is formed based on the compressed bit vector. 20. The network switch of claim 19, further comprising an egress port for transmitting the packet with the new protocol header layer. 21. A network switch comprising: an input port for receiving a packet, wherein the packet includes a body and a header having a plurality of protocol header layers forming a protocol stack; an output port for transmitting the modified packet; a memory for storing a set of software-defined mappings in a common format for the protocol and a common command set, wherein the common command set is used for protocol header layer modification regardless of which of the supported protocol variants the incoming protocol header layer is, wherein the common command set includes a delete command, a copy command, and a move command; and Rewriting engine for: converting each of the protocol header layers of the protocol stack into a common format based on a mapping from the set of software-defined mappings, thereby forming a converted protocol header layer; maintaining a bit vector for each of the converted protocol header layers, wherein each of the bit vectors includes a plurality of values, each value representing a byte of the converted protocol header layer to which the bit vector corresponds; modifying each of the converted protocol header layers using the common command set; updating each of the bit vectors subsequent to the bit vector, thereby forming an updated bit vector; compressing each of the updated bit vectors to thereby form a new protocol stack; and The body is attached to the new protocol stack for transmission via the output port. 22. The network switch of claim 21, wherein the bit vector includes a bit for each byte of the converted protocol header. 23. The network switch of claim 22, wherein the bit vector comprises bits marked as 0 for invalid fields of the converted protocol header layer and bits marked as 1 for valid fields of the converted protocol header layer. 24. The network switch of claim 13 , wherein the rewrite engine is configured to expand each of the protocol header layers into a common format, the common format corresponding to the protocol of the protocol header layer and including all fields supported by the protocol of the protocol header layer, wherein each of the fields has the same offset regardless of which variant of the protocol the protocol header layer corresponds to.