US6578084B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Packet processing using encapsulation and decapsulation chains
Assignee: Cisco Technology Inc
•
Filing: 1999-10-15
•
Granted: 2003-06-10
•
Expires: 2019-10-15
Abstract
Abstract A method for processing packets in a router includes specifying operations on packets as chains of processing elements. Each chain is uniquely associated with one interface/protocol pair, and each processing element performs at least one function on a packet. An incoming packet is received, and processed, first by a demultiplexor element which determines the protocol of the next higher level used by the packet. Then, the packet is processed by the elements of a decapsulation chain associated with the interface on which the packet was received, and by the elements of an encapsulation chain associated with the interface on which the packet is to be transmitted. The demultiplexor element or operation passes the packet on to a decapsulation chain associated with the protocol and with the incoming interface, depending on protocol information contained in the incoming packet. Decapsulation and encapsulation chains can be built dynamically, by inserting new and removing old elements as necessary as new protocols are developed and new features added. A chain walker walks through the chains, passing the processed packet to each element in a chain, until either the end of the chain is reached and processing is complete, or until the packet is dropped because no function can process it, or because a packet is processed by an outside process or by hardware, which may optionally stop the chain walk. A chain walk may be temporarily halted, or may be terminated. If temporarily halted, the chain walk can be resumed at any element in the chain, depending on the packet's requirements. A chain walk can also begin at any element in a chain.
Inventors
- 👤 Kenneth A. Moberg
- 👤 Claude A. Cartee
- 👤 Gregory D. Stovall
- 👤 David R. Hampton
- 👤 Kirk Stewart Lougheed
- 👤 Pedro Marques
- 👤 Timothy D. Kolar
- 👤 Andrew J. Valencia
- 👤 William B. May, Jr.
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 13:23
CPC Classifications
H; H04; H04L; H04L47/00; H04L47/50; H04L47/62; H04L69/00; H04L69/30; H04L69/32; H04L69/322; H04L69/328; H04L9/00; H04L9/40; H04L69/12
Claims Analysis
Total Claims: 37
Claim 1
Independent Claim
118 words
A method for processing packets, comprising: specifying a chain of function elements, each element capable of performing an operation on a packet, the chain being associated with an interface and a protocol; processing the packet by walking through the elements of the chain; receiving an incoming packet at a first interface, the packet being encapsulated according to a first protocol, wherein processing of the packet is performed by a decapsulation chain associated with the first interface and with the first protocol; upon completion of processing by the decapsulation chain, passing the packet to and processing it in an encapsulation chain associated with a second interface and a second protocol; and transmitting the processed packet from the second interface.
Claim 2
Independent Claim
118 words
A method for processing packets, comprising: specifying a chain of function elements, each element capable of performing an operation on a packet, the chain being associated with an interface and a protocol; processing the packet by walking through the elements of the chain; receiving an incoming packet at a first interface, the packet being encapsulated according to a first protocol, wherein processing of the packet is performed by a decapsulation chain associated with the first interface and with the first protocol; upon completion of processing by the decapsulation chain, passing the packet to and processing it in an encapsulation chain associated with a second interface and a second protocol; and transmitting the processed packet from the second interface.
Claim 3
Dependent Claim
24 words
The method of claim 1 , wherein a plurality of chains is associated with the interface, each chain being associated with a unique protocol.
Claim 4
Dependent Claim
15 words
The method of claim 2 , wherein an element belongs to one or more chains.
Claim 5
Dependent Claim
14 words
The method of claim 2 , wherein a unique protocol comprises a bridge-level protocol.
Claim 6
Dependent Claim
13 words
The method of claim 2 wherein a unique protocol comprises a router-level protocol.
Claim 7
Dependent Claim
13 words
The method of claim 2 wherein a unique protocol comprises a tunneling protocol.
Claim 8
Dependent Claim
17 words
The method of claim 1 , wherein protocol information about a packet is contained in the packet.
Claim 9
Dependent Claim
12 words
The method of claim 1 , further comprising: building the chain dynamically.
Claim 10
Dependent Claim
18 words
The method of claim 8 wherein the chain is dynamically built for a session at the session's start.
Claim 11
Dependent Claim
15 words
The method of claim 1 wherein the first interface and the second interface are different.
Claim 12
Dependent Claim
17 words
The method of claim 1 if wherein the first interface and the second interface are the same.
Claim 13
Dependent Claim
13 words
The method of claim 1 if wherein an interface is a virtual interface.
Claim 14
Dependent Claim
16 words
The method of claim 1 if wherein the first protocol and the second protocol are different.
Claim 15
Dependent Claim
27 words
The method of claim 1 , wherein a demultiplexor chain, responsive to protocol information contained in the received packet, passes the packet on to the encapsulation chain.
Claim 16
Dependent Claim
22 words
The method of claim 1 , wherein the encapsulation chain performs any or all of: encapsulation, encryption, compression, flow control and filtering.
Claim 17
Dependent Claim
20 words
The method of claim 1 , wherein the decapsulation chain performs one or many of: decapsulation, decryption, decompression and filtering.
Claim 18
Dependent Claim
18 words
The method of claim 1 , further comprising: stopping a chain walk at any element in a chain.
Claim 19
Dependent Claim
23 words
The method of claim 17 , further comprising: upon stopping a chain walk, passing the packet to a process external to the chain.
Claim 20
Dependent Claim
14 words
The method of claim 18 , wherein the external process is implemented by software.
Claim 21
Dependent Claim
14 words
The method of claim 18 , wherein the external process is implemented by hardware.
Claim 22
Dependent Claim
19 words
The method of claim 18 , wherein the external process is implemented by a combination of software and hardware.
Claim 23
Dependent Claim
18 words
The method of claim 18 , further comprising: resuming a chain walk at any element in a chain.
Claim 24
Dependent Claim
18 words
The method of claim 1 , further comprising: starting a chain walk at any element in a chain.
Claim 25
Dependent Claim
50 words
The method of claim 1 , further comprising: generating the packet in a selected protocol; determining an interface through which to transmit the packet; processing the packet by walking through the elements of an encapsulation chain associated with the interface and the protocol; and transmitting the packet from the interface.
Claim 26
Dependent Claim
25 words
The method of claim 1 , further comprising: from each element in the chain, returning, to the chain walker, a pointer to the next element.
Claim 27
Dependent Claim
123 words
A router for a computer network, comprising: a plurality of interfaces, each interface associated with a demultiplexor chain, an array of protocol decapsulation chains, and an array of protocol encapsulation chains, each chain comprising at least one packet-processing element, the elements in a chain being linked; and a chain walker which, upon receipt of an incoming first protocol packet in a receiving interface, passes the packet to the demultiplexor chain associated with the receiving interface for processing, passes the processed packet to and walks through a decapsulation chain associated with the incoming interface and the first protocol, for further processing, and passes the further processed packet to and walks through an encapsulation chain associated with an identified transmitting interface and identified second protocol.
Claim 28
Dependent Claim
123 words
A router for a computer network, comprising: a plurality of interfaces, each interface associated with a demultiplexor chain, an array of protocol decapsulation chains, and an array of protocol encapsulation chains, each chain comprising at least one packet-processing element, the elements in a chain being linked; and a chain walker which, upon receipt of an incoming first protocol packet in a receiving interface, passes the packet to the demultiplexor chain associated with the receiving interface for processing, passes the processed packet to and walks through a decapsulation chain associated with the incoming interface and the first protocol, for further processing, and passes the further processed packet to and walks through an encapsulation chain associated with an identified transmitting interface and identified second protocol.
Claim 29
Dependent Claim
54 words
The router of claim 26 wherein the chain walker walks through a chain by executing the chain's elements, wherein each element either returns a reference to a next element in the chain to be executed, wherein the chain walker executes the referenced next element, or returns a null reference, wherein the chain walker stops.
Claim 30
Dependent Claim
54 words
The router of claim 27 , further comprising, for each interface, an associated interface descriptor block, each interface descriptor block comprising: a reference to the demultiplexor chain associated with the interface; a reference to the decapsulation chain array associated with the interface; and a reference to the encapsulation chain array associated with the interface.
Claim 31
Dependent Claim
23 words
The router of claim 28 , wherein each encapsulation or decapsulation array comprises references to chains of encapsulation or decapsulation processing elements, respectively.
Claim 32
Dependent Claim
141 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps of processing packets, the method steps comprising: specifying a chain of function elements, each element capable of performing an operation on a packet, the chain being associated with an interface and a protocol; processing the packet by walking through the elements of the chain; receiving an incoming packet at a first interface, the packet being encapsulated according to a first protocol, wherein processing of the packet is performed by a decapsulation chain associated with the first interface and with the first protocol; upon completion of processing by the decapsulation chain, passing the packet to and processing it in an encapsulation chain associated with a second interface and a second protocol; and transmitting the processed packet from the second interface.
Claim 33
Dependent Claim
141 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps of processing packets, the method steps comprising: specifying a chain of function elements, each element capable of performing an operation on a packet, the chain being associated with an interface and a protocol; processing the packet by walking through the elements of the chain; receiving an incoming packet at a first interface, the packet being encapsulated according to a first protocol, wherein processing of the packet is performed by a decapsulation chain associated with the first interface and with the first protocol; upon completion of processing by the decapsulation chain, passing the packet to and processing it in an encapsulation chain associated with a second interface and a second protocol; and transmitting the processed packet from the second interface.
Claim 34
Dependent Claim
191 words
A computer program product for use in a computer network router, the computer program product comprising a computer usable medium having computer readable program code means embodied in the medium for causing processing of a packet, the computer usable medium comprising: computer readable program code means for causing a router to specify a chain of function elements, each element capable of performing an operation on a packet, the chain being associated with an interface and a protocol; computer readable program code means for causing a router to process the packet by walking through the elements of the chain; computer readable program code means for receiving an incoming packet at a first interface, the packet being encapsulated according to a first protocol, wherein processing of the packet is performed by a decapsulation chain associated with the first interface and with the first protocol; computer readable program code means for passing, upon completion of processing by the decapsulation chain, the packet to and processing it in an encapsulation chain associated with a second interface and a second protocol; and computer readable program code means for transmitting the processed packet from the second interface.
Claim 35
Dependent Claim
191 words
A computer program product for use in a computer network router, the computer program product comprising a computer usable medium having computer readable program code means embodied in the medium for causing processing of a packet, the computer usable medium comprising: computer readable program code means for causing a router to specify a chain of function elements, each element capable of performing an operation on a packet, the chain being associated with an interface and a protocol; computer readable program code means for causing a router to process the packet by walking through the elements of the chain; computer readable program code means for receiving an incoming packet at a first interface, the packet being encapsulated according to a first protocol, wherein processing of the packet is performed by a decapsulation chain associated with the first interface and with the first protocol; computer readable program code means for passing, upon completion of processing by the decapsulation chain, the packet to and processing it in an encapsulation chain associated with a second interface and a second protocol; and computer readable program code means for transmitting the processed packet from the second interface.
Claim 36
Dependent Claim
225 words
An article of manufacture for use in a computer network router, the article of manufacture comprising a computer usable medium having computer readable program code means embodied in the medium, said program code means of causing processing of a packet, the program code means including: computer readable program code means embodied in said computer useable medium for causing a router to specify a chain of function elements, each element capable of performing an operation on a packet, the chain being associated with an interface and a protocol; computer readable program code means embodied in said computer useable medium for causing a router to process the packet by walking through the elements of the chain; computer readable program code means embodied in said computer useable medium for receiving an incoming packet at a first interface, the packet being encapsulated according to a first protocol, wherein processing of the packet is performed by a decapsulation chain associated with the first interface and with the first protocol; computer readable program code means embodied in said computer useable medium for passing, upon completion of processing by the decapsulation chain, the packet to and processing it in an encapsulation chain associated with a second interface and a second protocol; and computer readable program code means embodied in said computer useable medium for transmitting the processed packet from the second interface.
Claim 37
Dependent Claim
225 words
An article of manufacture for use in a computer network router, the article of manufacture comprising a computer usable medium having computer readable program code means embodied in the medium, said program code means of causing processing of a packet, the program code means including: computer readable program code means embodied in said computer useable medium for causing a router to specify a chain of function elements, each element capable of performing an operation on a packet, the chain being associated with an interface and a protocol; computer readable program code means embodied in said computer useable medium for causing a router to process the packet by walking through the elements of the chain; computer readable program code means embodied in said computer useable medium for receiving an incoming packet at a first interface, the packet being encapsulated according to a first protocol, wherein processing of the packet is performed by a decapsulation chain associated with the first interface and with the first protocol; computer readable program code means embodied in said computer useable medium for passing, upon completion of processing by the decapsulation chain, the packet to and processing it in an encapsulation chain associated with a second interface and a second protocol; and computer readable program code means embodied in said computer useable medium for transmitting the processed packet from the second interface.
References Cited (Backward Citations)
US5267239A
Cited
US5745758A
Cited
US5867666A
Cited
US5764920A
Cited
US6240084B1
Cited
US5983269A
Cited
US5982783A
Cited
US6236660B1
Cited
US6160811A
Cited
US6092110A
Cited
US6226267B1
Cited
US6320848B1
Cited
US6385194B2
Cited
US6219706B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-06-09 | 2006-12-09 | 2007-06-10 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-06-09 | 2010-12-09 | 2011-06-10 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-06-09 | 2014-12-09 | 2015-06-10 | $7700.00 | Window Closed / Lapsed |