METHOD OF USING BIT VECTORS TO ALLOW EXPANSION AND COLLAPSE OF HEADER LAYERS WITHIN PACKETS FOR ENABLING FLEXIBLE MODIFICATIONS AND AN APPARATUS THEREOF

• US 20150373160A1
• Filed: 06/19/2014
• Published: 12/24/2015
• Est. Priority Date: 06/19/2014
• Status: Active Grant

• Current Assignee: Marvell Asia Pte Limited (Marvell Technology Group Limited)
• Original Assignee: XPLIANT, INC. (Marvell Technology Group Limited)
• Inventors: Singh, Chirinjeev, Daniel, Tsahi, Schmidt, Gerald
• Granted Patent: US 9,635,146 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 69/04 Protocols for data compression, e.g. ROHC
• CPC Class Codes: H04L 69/08 Protocols for interworking; Protocol conversion
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

Embodiments of the apparatus for modifying packet headers relate to a use of bit vectors to allow expansion and collapse of protocol headers within packets for enabling flexible modification. A rewrite engine expands each protocol header into a generic format and applies various commands to modify the generalized protocol header. The rewrite engine maintains a bit vector for the generalized protocol header with each bit in the bit vector representing a byte of the generalized protocol header. A bit marked as 0 in the bit vector corresponds to an invalid byte, while a bit marked as 1 in the bit vector corresponds to a valid byte. The rewrite engine uses the bit vector to remove all the invalid bytes after all commands have been operated on the generalized protocol header to thereby form a new protocol header.

Claims

1. A method of a rewrite engine of a network device, the method comprising:

maintaining a bit vector for a generalized protocol header;

updating the bit vector based on modification of at least one generalized protocol header; and

using the updated bit vector to compress the at least one generalized protocol header.

2. The method of claim 1, wherein the generalized protocol header is a protocol header of a packet expanded to a generic format.

3. The method of claim 2, wherein the generic format includes all possible fields of the protocol, wherein each of the fields has the same offset irrespective of which variation of the protocol the protocol header corresponds to.

4. The method of claim 1, wherein the bit vector includes a bit per byte for each byte of the generalized protocol header.

5. The method of claim 1, wherein the modification uses at least one command from a set of generic commands that is stored in a memory of the network switch to modify the at least one generalized protocol header.

6. The method of claim 1, further comprising, prior to using the updated bit vector, performing an XOR operation on the bit vector and the updated bit vector to determine how many bits changed.

7. A method of a network switch, the method comprising:

receiving a packet at an incoming port of the network switch;

generalizing each protocol header of the packet according to a generic format for the protocol header;

maintaining a bit vector for each generalized protocol header, 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 headers by applying, thereby updating the bit vector;

collapsing the updated bit vector; and

forming a new protocol header based on the compressed bit vector.

8. The method of claim 7, wherein generalizing each protocol header includes:

detecting missing fields from the protocol header of the packet; and

based on the detection, expanding the protocol header to the generic format by including the missing fields.

9. The method of claim 7, wherein the modification uses at least one command from a set of generic commands that is stored in a memory of the network switch to modify the at least one generalized protocol header.

10. The method of claim 7, wherein the modification of the at least one generalized protocol header is based on egress portType of the outgoing port of the network switch.

11. The method of claim 7, wherein collapsing the updated bit vector includes shifting the updated bit vector by removing each bit marked as 0 in the updated bit vector.

12. The method of claim 7, further comprising transmitting the packet with at least the new protocol header via an outgoing port of the network switch.

13. The method of claim 12, further comprising, before transmitting the packet with at least the new protocol header, counting a number of bytes added or deleted for all operations performed.

14. A network switch comprising:

an input port for receiving a packet;

a memory storing a set of generic commands, wherein the set of generic commands is used for header modifications irrespective of incoming headers; and

a rewrite engine using bit vectors to allow expansion and collapse of protocols headers of the packet, thereby enabling flexible modification of the packet by using the set of generic commands.

15. The network switch of claim 14, wherein the set of generic commands include a Delete command, a Copy command and a Move command.

16. The network switch of claim 14, wherein each of the protocol headers is generalized according to one of software-defined mappings that is specific to a corresponding protocol.

17. The network switch of claim 14, wherein the software-defined mappings are stored in the memory.

18. The network switch of claim 16, wherein each generalized protocol header includes a bit vector with bits marked as 0 for invalid fields and bits marked as 1 for valid fields.

19. The network switch of claim 18, wherein the rewrite engine updates the bit vector after the generalized protocol header is modified.

20. The network switch of claim 19, wherein the rewrite engine removes each bit marked as 0 in the updated bit vector to collapse the updated bit vector.

21. The network switch of claim 20, wherein a new header is formed based on the collapsed bit vector.

22. The network switch of claim 20, further comprising an outgoing port for transmitting the packet with the new header.

23. A network switch comprising:

an input port for receiving a packet, wherein the packet includes a body and a protocol stack;

an output port for transmitting modified packets;

a memory to store a set of software-defined mappings of generic formats of protocols and a set of generic modification commands, wherein the set of generic modification commands is used for header modifications irrespective of incoming headers; and

a rewrite engine to;

convert each protocol header of the protocol stack into a generic format based on one from the set of software-defined mappings;

maintain a bit vector for each converted protocol header;

use the set of generic modifications commands to modify each converted protocol header;

update each bit vector after the bit vector;

collapse each updated bit vector to thereby form a new protocol stack; and

attach the new protocol stack with the body to be transmitted via the output port.

24. The network switch of claim 23, wherein the bit vector includes a bit per byte for each byte of the converted protocol header.

25. The network switch of claim 24, wherein 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.