US6714985B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for efficiently reassembling fragments received at an intermediate station in a computer network
Assignee: Cisco Technology Inc
•
Filing: 2000-04-28
•
Granted: 2004-03-30
•
Expires: 2020-04-28
Abstract
Abstract An IP packet reassembly engine provides high-speed and efficient reassembly of IP fragments received at an intermediate station in a computer network. The IP packet reassembly engine comprises a main controller logic circuit configured to "speed-up" re-assembly of original packets from IP fragments stored in a frame buffer at multi-gigabit per second rates. To that end, the reassembly engine further includes a content addressable memory having a plurality of entries for maintaining status information for each received fragment and for each original packet being reassembled from the fragments.
Inventors
- 👤 Dante Malagrino
- 👤 Thomas J. Edsall
- 👤 Silvano Gai
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 10:04
CPC Classifications
H; H04; H04L; H04L69/00; H04L69/16; H04L69/166; H04L9/00; H04L9/40; H04L69/30; H04L69/32; H04L69/322; H04L69/329
Claims Analysis
Total Claims: 48
Claim 1
Independent Claim
90 words
Apparatus for providing high-speed and efficient reassembly of fragments received at an intermediate station in a computer network, the apparatus comprising: a frame buffer organized into a plurality of queues for storing the fragments; a main controller coupled to the frame buffer and configured to reassemble an original packet from the fragments at multi-gigabit per second rates; and a content addressable memory (CAM) subsystem coupled to the main controller, the CAM subsystem having a plurality of entries, each entry maintaining status information for each fragment received at the intermediate station.
Claim 2
Dependent Claim
90 words
Apparatus for providing high-speed and efficient reassembly of fragments received at an intermediate station in a computer network, the apparatus comprising: a frame buffer organized into a plurality of queues for storing the fragments; a main controller coupled to the frame buffer and configured to reassemble an original packet from the fragments at multi-gigabit per second rates; and a content addressable memory (CAM) subsystem coupled to the main controller, the CAM subsystem having a plurality of entries, each entry maintaining status information for each fragment received at the intermediate station.
Claim 3
Dependent Claim
18 words
The apparatus of claim 1 wherein the fragments received at the intermediate station are Internet Protocol (IP) fragments.
Claim 4
Dependent Claim
42 words
The apparatus of claim 2 wherein at least one entry of the CAM subsystem maintains information about an IP total length of each original packet reassembled by the main controller and a current length of each received fragment belonging to the packet.
Claim 5
Dependent Claim
33 words
The apparatus of claim 3 wherein the information relating to the IP total length and current length indicate whether all fragments belonging to the original packet have been received by the intermediate station.
Claim 6
Dependent Claim
39 words
The apparatus of claim 4 wherein the IP total length of the reassembled original packet equals a sum of an IP fragment offset of a last fragment of the packet and the IP total length of the last fragment.
Claim 7
Dependent Claim
29 words
The apparatus of claim 5 wherein a reassembly process of the intermediate station begins when the current length of the original packet equals the total length of that packet.
Claim 8
Dependent Claim
48 words
The apparatus of claim 6 wherein the original packet is assembled starting with a first fragment of the packet and wherein the first fragment is retrieved by the main controller from the frame buffer using a pointer referencing a location of the first fragment in the frame buffer.
Claim 9
Dependent Claim
17 words
The apparatus of claim 7 wherein the pointer is stored in an entry of the CAM subsystem.
Claim 10
Dependent Claim
14 words
The apparatus of claim 8 wherein the CAM subsystem is a ternary CAM subsystem.
Claim 11
Dependent Claim
33 words
The apparatus of claim 1 wherein the main controller comprises a frame buffer controller that cooperates with queuing and dequeuing logic to store and retrieve fragments to/from the queues of the frame buffer.
Claim 12
Dependent Claim
26 words
The apparatus of claim 10 wherein the main controller further comprises an input queue data structure for use in managing the queues of the frame buffer.
Claim 13
Dependent Claim
13 words
The apparatus of claim 11 wherein the intermediate station is a network switch.
Claim 14
Independent Claim
167 words
A method for high-speed reassembly of fragments received at an intermediate station in a computer network, the method comprising the steps of performing a first lookup operation into a content addressable memory (CAM) subsystem having a plurality of entries to locate a first offset zero fragment entry associated with a packet; retrieving contents of a pointer field, a total length field and a 4-tuple field of the located entry; using the content of the pointer field to obtain the first offset zero fragment from a queue of the frame buffer; performing subsequent lookup operations into the CAM subsystem for subsequent fragments of the packet stored in the frame buffer using the contents of the 4-tuple field to obtain pointers to respective queues in the buffer; obtaining the subsequent fragments from the queues using the pointers; and reassembling the fragments into proper order within an original packet by placing a data portion of each fragment in a relative position indicated by a fragment offset value of each fragment.
Claim 15
Independent Claim
167 words
A method for high-speed reassembly of fragments received at an intermediate station in a computer network, the method comprising the steps of performing a first lookup operation into a content addressable memory (CAM) subsystem having a plurality of entries to locate a first offset zero fragment entry associated with a packet; retrieving contents of a pointer field, a total length field and a 4-tuple field of the located entry; using the content of the pointer field to obtain the first offset zero fragment from a queue of the frame buffer; performing subsequent lookup operations into the CAM subsystem for subsequent fragments of the packet stored in the frame buffer using the contents of the 4-tuple field to obtain pointers to respective queues in the buffer; obtaining the subsequent fragments from the queues using the pointers; and reassembling the fragments into proper order within an original packet by placing a data portion of each fragment in a relative position indicated by a fragment offset value of each fragment.
Claim 16
Dependent Claim
43 words
The method of claim 13 wherein the fragments received at the intermediate station are Internet Protocol (IP) fragments and wherein the contents of the 4-tuple field comprise an IP destination address, an IP source address, an IP protocol and an IP identification value.
Claim 17
Dependent Claim
34 words
The method of claim 14 wherein the step of performing subsequent lookup operations into the CAM subsystem comprises the step of varying each lookup operation according to the fragment offset value of each fragment.
Claim 18
Dependent Claim
34 words
The method of claim 15 wherein the step of varying each lookup operation comprises the step of calculating the fragment offset value according to the equation FragmentOffset n+1 =FragmentOffset n +Total Length n .
Claim 19
Dependent Claim
31 words
The method of claim 16 wherein the step of reassembling the fragments comprises the step of completing a reassembly process when a last fragment is added to the reassembled original packet.
Claim 20
Dependent Claim
48 words
The method of claim 17 further comprising the steps of: comparing a current time with an expiration time stored in an expiration time field of each CAM entry; and deleting each entry of the CAM subsystem when the current time equals the expiration time associated with that entry.
Claim 21
Dependent Claim
35 words
The method of claim 18 wherein the step of deleting each entry comprises the step of deleting each entry of the CAM subsystem when the current time exceeds the expiration time associated with that entry.
Claim 22
Dependent Claim
15 words
The method of claim 19 wherein the CAM subsystem is a ternary CAM (TCAM) subsystem.
Claim 23
Dependent Claim
74 words
A router, comprising: a frame buffer organized into a plurality of queues for storing a plurality of fragments of a frame received at said router; a controller coupled to the frame buffer to reassemble an original packet from the fragments; and a content addressable memory (CAM) subsystem coupled to the controller, the CAM subsystem having a plurality of entries, each entry maintaining status information for each fragment of a frame received at the router.
Claim 24
Dependent Claim
74 words
A router, comprising: a frame buffer organized into a plurality of queues for storing a plurality of fragments of a frame received at said router; a controller coupled to the frame buffer to reassemble an original packet from the fragments; and a content addressable memory (CAM) subsystem coupled to the controller, the CAM subsystem having a plurality of entries, each entry maintaining status information for each fragment of a frame received at the router.
Claim 25
Dependent Claim
43 words
The router of claim 21 , further comprising: at least one entry of the CAM subsystem maintains information about an IP total length of each original packet reassembled by the controller and a current length of each received fragment belonging to the packet.
Claim 26
Dependent Claim
16 words
The router of claim 21 , further comprising: the CAM subsystem is a ternary CAM subsystem.
Claim 27
Dependent Claim
52 words
The router of claim 21 further comprising: an expiration time field of each CAM entry, and comparing a current time with an expiration time stored in the expiration time field; and means for deleting each entry of the CAM subsystem when the current time equals the expiration time associated with that entry.
Claim 28
Dependent Claim
28 words
The router of claim 24 further comprising: means for deleting each entry of the CAM subsystem when the current time exceeds the expiration time associated with that entry.
Claim 29
Independent Claim
46 words
A method for operating a router, comprising: storing a plurality of fragments of a frame received at said router; maintaining status information for each fragment of the frame in content addressable memory (CAM); reassembling an original packet from the fragments in response to the status information.
Claim 30
Independent Claim
46 words
A method for operating a router, comprising: storing a plurality of fragments of a frame received at said router; maintaining status information for each fragment of the frame in content addressable memory (CAM); reassembling an original packet from the fragments in response to the status information.
Claim 31
Dependent Claim
44 words
The method of claim 26 , further comprising: maintaining, in at least one entry of the CAM subsystem, information about an IP total length of each original packet reassembled by the controller and a current length of each received fragment belonging to the packet.
Claim 32
Dependent Claim
17 words
The method of claim 26 , further comprising: implementing the CAM subsystem as a ternary CAM subsystem.
Claim 33
Dependent Claim
45 words
The method of claim 26 further comprising: comparing a current time with an expiration time stored in an expiration time field of each CAM entry; and deleting each entry of the CAM subsystem when the current time equals the expiration time associated with that entry.
Claim 34
Dependent Claim
26 words
The method of claim 29 further comprising: deleting each entry of the CAM subsystem when the current time exceeds the expiration time associated with that entry.
Claim 35
Dependent Claim
17 words
The method of claim 26 , further comprising: the CAM subsystem is a ternary CAM (TCAM) subsystem.
Claim 36
Dependent Claim
49 words
A router, comprising: a frame buffer to store a plurality of fragments of a frame received at said router; content addressable memory (CAM) to maintain status information for each fragment of the frame; a controller to reassemble an original packet from the fragments in response to the status information.
Claim 37
Dependent Claim
49 words
A router, comprising: a frame buffer to store a plurality of fragments of a frame received at said router; content addressable memory (CAM) to maintain status information for each fragment of the frame; a controller to reassemble an original packet from the fragments in response to the status information.
Claim 38
Dependent Claim
43 words
The router of claim 32 , further comprising: at least one entry of the CAM subsystem maintains information about an IP total length of each original packet reassembled by the controller and a current length of each received fragment belonging to the packet.
Claim 39
Dependent Claim
16 words
The router of claim 32 , further comprising: the CAM subsystem is a ternary CAM subsystem.
Claim 40
Dependent Claim
48 words
A router, comprising: means for storing a plurality of fragments of a frame received at said router; means for maintaining status information for each fragment of the frame in content addressable memory (CAM); means for reassembling an original packet from the fragments in response to the status information.
Claim 41
Dependent Claim
48 words
A router, comprising: means for storing a plurality of fragments of a frame received at said router; means for maintaining status information for each fragment of the frame in content addressable memory (CAM); means for reassembling an original packet from the fragments in response to the status information.
Claim 42
Dependent Claim
46 words
The router of claim 35 , further comprising: means for maintaining, in at least one entry of the CAM subsystem, information about an IP total length of each original packet reassembled by the controller and a current length of each received fragment belonging to the packet.
Claim 43
Dependent Claim
19 words
The router of claim 35 , further comprising: means for implementing the CAM subsystem as a ternary CAM subsystem.
Claim 44
Dependent Claim
50 words
The router of claim 35 , further comprising: means for comparing a current time with an expiration time stored in an expiration time field of each CAM entry; and means for deleting each entry of the CAM subsystem when the current time equals the expiration time associated with that entry.
Claim 45
Dependent Claim
29 words
The router of claim 38 , further comprising: means for deleting each entry of the CAM subsystem when the current time exceeds the expiration time associated with that entry.
Claim 46
Dependent Claim
17 words
The router of claim 35 , further comprising: the CAM subsystem is a ternary CAM (TCAM) subsystem.
Claim 47
Dependent Claim
31 words
A computer readable media, comprising: said computer readable media having instructions written thereon for execution on a processor for the practice of the method of claim 13 or claim 26 .
Claim 48
Dependent Claim
31 words
Electromagnetic signals propagating on a computer network, comprising: said electromagnetic signals carrying instructions for execution on a processor for the practice of the method of claim 13 or claim 26 .
References Cited (Backward Citations)
US5408469A
Cited
US5481536A
Cited
US5560038A
Cited
US6061349A
Cited
US5859550A
Cited
US5881242A
Cited
US6054942A
Cited
US6480468B1
Cited
US6233243B1
Cited
US6131117A
Cited
US6115385A
Cited
US6226771B1
Cited
US6487211B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2007-03-30 | 2007-09-29 | 2008-03-30 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2011-03-30 | 2011-09-29 | 2012-03-30 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2015-03-30 | 2015-09-29 | 2016-03-30 | $7700.00 | Window Closed / Lapsed |