Cell reassembly for packet based networks

• US 6,704,794 B1
• Filed: 03/03/2000
• Issued: 03/09/2004
• Est. Priority Date: 03/03/2000
• Status: Expired due to Fees

• Current Assignee: Nokia Solutions and Networks US LLC (Nokia Corporation)
• Original Assignee: Nokia Intelligent Edge Routers Inc. (Nokia Corporation)
• Inventors: Ho, Chi Fai, Kejriwal, Prabhas
• Primary Examiner(s): EL HADY, NABIL M
• Application Number:
  US09/518,662
• Time in Patent Office: 1,467 Days
• Field of Search: 709/236, 370/474, 370/397, 370/395, 370/398, 370/392, 370/359
• US Class Current: 709/236
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers
• CPC Class Codes: H04L 69/32 Architecture of open systems interconnection [OSI] 7-layer type protocol stacks, e.g. the interfaces between the data link level and the physical level
• CPC Class Codes: H04L 69/325 in the network layer [OSI layer 3], e.g. X.25 H04L69/16 takes precedence
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A cell processing pipeline is described having a plurality of stages for cell reassembly. The cell has a cell header and a cell payload. One of the stages is configured to parse packet header information located within the cell payload.

Claims

1. An apparatus, comprising:

a cell processing pipeline comprising a plurality of pipeline stages, said cell processing pipeline further comprising a pipeline stage to, within a pipeline cycle,

1) parse a payload of a cell if said cell payload carries a portion of a packet'"'"'s header and a portion of said packet'"'"'s payload;

2) determine packet state information, where, whether or not a following cell that carries a next portion of said packet carries a portion of said packet'"'"'s header can be determined from said packet state information;

said pipeline stage further comprising, to said parse and to said determine, a micro program sequencer and an execution unit coupled to said micro program sequencer, said pipeline stage coupled to a register, said register to provide said packet state information back to said pipeline stage if a next cell to be evaluated for parsing by said pipeline stage within a next pipeline cycle after said pipeline cycle is also said following cell.

2. The apparatus of claim 1 further comprising first register space and second register space, said first register space to store information that identifies a connection over which said cell arrived, said second register space to store information that identifies a connection over which said next cell arrived, said register to provide said packet state information back to said pipeline stage if the contents of said first and second register spaces indicate the same connection so as to indicate said next cell is also said following cell.

3. The apparatus of claim 2 wherein said first register space is accessible to a first pipeline stage that precedes said pipeline stage in said pipeline, and wherein, said second register space is accessible to a third pipeline stage that follows said pipeline stage in said pipeline.

4. The apparatus of claim 3 wherein said first and third pipeline stages are coupled to a memory, said memory to store packet state information determined by said pipeline stage upon its being sent from said third pipeline stage, said memory to provide said packet state information to said first pipeline stage upon said following cell being presented to said pipeline.

5. The apparatus of claim 4 wherein said memory is to further to store, along with said packet state information, said packet header portion parsed by said pipeline stage upon its being sent from said third pipeline stage, said memory to also provide said packet header portion to said first pipeline stage upon said following cell being said presented to said pipeline.

6. The apparatus of claim 5 further comprising a second memory coupled to said first stage, said second memory to provide said information that identifies a connection over which said cell arrived in response to a parameter associated with said cell.

7. The apparatus of claim 6 wherein said parameter is said cell'"'"'s VPI/VCI.

8. The apparatus of claim 7 wherein said second memory is a content addressable memory (CAM).

9. The apparatus of claim 1 further comprising a first pipeline stage that precedes said pipeline stage in said pipeline and a third pipeline stage that follows said pipeline stage in said pipeline, said first and third pipeline stages coupled to a memory, said memory to store packet state information determined by said pipeline stage upon its being sent from said third pipeline stage, said memory to provide said packet state information to said first pipeline stage upon said following cell being presented to said pipeline.

10. The apparatus of claim 9 wherein said memory is to further to store, along with said packet state information, said packet header portion parsed by said pipeline stage upon its being sent from said third pipeline stage, said memory to also provide said packet header portion to said first pipeline stage upon said following cell being said presented to said pipeline.

11. The apparatus of claim 9 further comprising a second memory coupled to said first stage, said second memory to provide information that identifies a connection over which said cell arrived in response to a parameter associated with said cell.

12. The apparatus of claim 11 said parameter is said cell'"'"'s VPI/VCI.

13. The apparatus of claim 11 wherein said second memory is a content addressable memory (CAM).

14. The apparatus of claim 1 wherein said packet state information includes a cell count that tracks how many cells of said packet have been evaluated for parsing by said pipeline stage.

15. The apparatus of claim 1 further comprising a micro-program memory coupled to said sequencer, said micro-program memory to store micro-programs that are executable by said pipeline stage.

16. The apparatus of claim 15 wherein at least one of said micro-programs is to be executed by said pipeline stage for cells carrying a portion of a specific type of packet.

17. The apparatus of claim 16 wherein said specific type of packet is IP.

18. The apparatus of claim 16 wherein said specific type of packet is MPLS.

19. The apparatus of claim 16 wherein said specific type of packet is Frame Relay.

20. The apparatus of claim 16 wherein said specific type of packet is AAL0.

21. The apparatus of claim 16 wherein said specific type of packet is AAL5.

22. The apparatus of claim 16 wherein said specific type of packet is Packet Over SONET.

23. The apparatus of claim 22 wherein said at least one of said micro-programs contains instructions sufficient for said pipeline stage to determine at least one of the following:

a) a length indicator;

b) a timestamp insert flag;

c) a record route flag.

24. The apparatus of claim 1 wherein said pipeline stage further comprises an interface to a free space lists manager so that a pointer can be retrieved within said pipeline cycle, said pointer to point to a location in a packet buffer where payload information (if any) of said packet carried by said following cell will be written into said packet buffer.

25. The apparatus of claim 24 further comprising register space accessible to said pipeline stage to which said pipeline stage provides said pointer, said packet state information and any parsed portion of said packet'"'"'s header.

26. The apparatus of claim 24 wherein said pipeline further comprises a following pipeline stage relative to said pipeline stage, said following pipeline stage coupled to said packet buffer so that said packet payload information (if any) carried by said following cell can be written to said location in said packet buffer pointed to by said pointer.

27. The apparatus of claim 26 further comprising another pipeline stage that precedes said pipeline stage in said pipeline, said following and another pipeline stages coupled to a memory, said memory to store packet state information determined by said pipeline stage upon its being sent from said following pipeline stage, said memory to provide said packet state information to said another pipeline stage upon said following cell being presented to said pipeline.

28. The apparatus of claim 1 wherein said pipeline stage does not said parse for Layer 2 flows.

29. A method, comprising:

a) within a first cycle of a pipeline;

parsing a cell payload if said cell payload carries a portion of a packet'"'"'s header and a portion of said packet'"'"'s payload;

determining packet state information for said packet, where, whether or not a following cell that carries a next portion of said packet carries a portion of said packet'"'"'s header can be determined from said packet state information; and

,

b) within a second cycle of said pipeline that immediately follows said first cycle and as a consequence of recognizing that a next cell that immediately follows said cell in the processing sequences of said pipeline is said following cell;

using said packet state information to determine whether or not said next cell carries a portion of said packet'"'"'s header.

30. The method of claim 29 further comprising within said first cycle:

looking up a connection that said next cell arrived on.

31. The method of claim 30 wherein an input parameter for said looking up employs at least a portion of said next cell'"'"'s header.

32. The method of claim 30 wherein said recognizing further comprises recognizing that said connection is the same connection that said cell arrived on.

33. The method of claim 29 further comprising executing a micro program to perform said parsing and said determining within said first pipeline cycle.

34. The method of claim 33 wherein said micro program is specific to the specific type of said packet.

35. The method of claim 34 wherein said specific type of packet is IP.

36. The method of claim 34 wherein said specific type of packet is MPLS.

37. The method of claim 34 wherein said specific type of packet is Frame Relay.

38. The method of claim 34 wherein said specific type of packet is AAL0.

39. The method of claim 34 wherein said specific type of packet is AAL5.

40. The method of claim 34 wherein said specific type of packet is Packet Over SONET.

41. The method of claim 29 further comprising retrieving, within said first pipeline cycle, a pointer that identifies where payload information (if any) of said packet carried by said following cell will be written into a buffer memory.

42. The method of claim 41 further comprising writing payload information of said packet carried by said following cell into said buffer memory after said second pipeline cycle.

43. The method of claim 42 further comprising performing said writing during a third pipeline cycle that immediately follows said second pipeline cycle.

44. The method of claim 43 further comprising, during said second pipeline cycle, updating said packet state information for said packet, so that, it can be determined whether or not a second following cell that carries a second next portion of said packet carries a portion of said packet'"'"'s header.

45. The method of claim 44 further comprising writing said updated packet state information into a memory during said third pipeline cycle.

46. The method of claim 45 further comprising looking up said updated packet state information with a term associated with said second following cell as a consequence of said second following cell being presented to said pipeline for processing.

47. The method of claim 46 where said term at least includes said cell'"'"'s VPI/VCI information.

48. The method of claim 29 further comprising, during said second pipeline cycle, updating said packet state information for said packet, so that, it can be determined whether or not a second following cell that carries a second next portion of said packet carries a portion of said packet'"'"'s header.

49. The method of claim 48 further comprising writing said updated packet state information into a memory during said third pipeline cycle.

50. The method of claim 49 further comprising looking up said updated packet state information with a term associated with said second following cell as a consequence of said second following cell being presented to said pipeline for processing.

51. The method of claim 50 where said term at least includes said cell'"'"'s VPI/VCI information.

52. An apparatus, comprising:

a) means for, within a first cycle,

parsing a cell payload if said cell payload carries a portion of a packet'"'"'s header and a portion of said packet'"'"'s payload;

determining packet state information for said packet, where, whether or not a following cell that carries a next portion of said packet carries a portion of said packet'"'"'s header can be determined from said packet state information; and

,

b) means for, within a second cycle that immediately follows said first cycle and as a consequence of recognizing that a next cell that immediately follows said cell in a series of pipelined processing sequences is said following cell,

using said packet state information to determine whether or not said next cell carries a portion of said packet'"'"'s header.

53. The apparatus of claim 52 further comprising means for, within said first cycle, looking up a connection that said next cell arrived on.

54. The apparatus of claim 52 further comprising means for retrieving, within said first cycle, a pointer that identifies where payload information (if any) of said packet carried by said following cell will be written into a buffer memory.

55. The apparatus of claim 52 further comprising means for writing said updated packet state information into a memory during a third cycle that immediately follows said second cycle.

56. The apparatus of claim 52 further comprising means for, during said second cycle, updating said packet state information for said packet, so that, it can be determined whether or not a second following cell that carries a second next portion of said packet carries a portion of said packet'"'"'s header.

57. The apparatus of claim 56 further comprising means for writing said updated packet state information into a memory during a third cycle that immediately follows said second cycle.

58. A machine readable medium containing a description of a design for a semiconductor circuit, said circuit comprising:

a cell processing pipeline comprising a plurality of pipeline stages, said cell processing pipeline further comprising a pipeline stage to, within a pipeline cycle,

1) parse a payload of a cell if said cell payload carries a portion of a packet'"'"'s header and a portion of said packet'"'"'s payload;

2) determine packet state information, where, whether or not a following cell that carries a next portion of said packet carries a portion of said packet'"'"'s header can be determined from said packet state information;

said pipeline stage further comprising, to said parse and to said determine, a micro program sequencer and an execution unit coupled to said micro program sequencer, said pipeline stage coupled to a register, said register to provide said packet state information back to said pipeline stage if a next cell to be evaluated for parsing by said pipeline stage within a next pipeline cycle after said pipeline cycle is also said following cell.

59. The machine readable medium of claim 58 wherein said circuit further comprises first register space and second register space, said first register space to store information that identifies a connection over which said cell arrived, said second register space to store information that identifies a connection over which said next cell arrived, said register to provide said packet state information back to said pipeline stage if the contents of said first and second register spaces indicate the same connection so as to indicate said next cell is also said following cell.

60. The machine readable medium of claim 59 wherein said first register space is accessible to a first pipeline stage that precedes said pipeline stage in said pipeline, and wherein, said second register space is accessible to a third pipeline stage that follows said pipeline stage in said pipeline.

61. The machine readable medium of claim 58 of wherein said circuit is described in VHDL.

62. The machine readable medium of claim 58 wherein said circuit is described at a Register Transfer Level (RTL).

63. A networking system, comprising:

a packet aggregation layer to perform cell reassembly, said packet aggregation layer comprising;

a cell processing pipeline comprising a plurality of pipeline stages, said cell processing pipeline further comprising a pipeline stage to, within a pipeline cycle,

1) parse a payload of a cell if said cell payload carries a portion of a packet'"'"'s header and a portion of said packet'"'"'s payload;

2) determine packet state information, where, whether or not a following cell that carries a next portion of said packet carries a portion of said packet'"'"'s header can be determined from said packet state information;

said pipeline stage further comprising, to said parse and to said determine, a micro program sequencer and an execution unit coupled to said micro program sequencer, said pipeline stage coupled to a register, said register to provide said packet state information back to said pipeline stage if a next cell to be evaluated for parsing by said pipeline stage within a next pipeline cycle after said pipeline cycle is also said following cell.

64. The networking system of claim 63 wherein said packet aggregation layer further comprises first register space and second register space, said first register space to store information that identifies a connection over which said cell arrived, said second register space to store information that identifies a connection over which said next cell arrived, said register to provide said packet state information back to said pipeline stage if the contents of said first and second register spaces indicate the same connection so as to indicate said next cell is also said following cell.

65. The networking system of claim 64 wherein said first register space is accessible to a first pipeline stage that precedes said pipeline stage in said pipeline, and wherein, said second register space is accessible to a third pipeline stage that follows said pipeline stage in said pipeline.

66. The networking system of claim 65 wherein said first and third pipeline stages are coupled to a memory, said memory to store packet state information determined by said pipeline stage upon its being sent from said third pipeline stage, said memory to provide said packet state information to said first pipeline stage upon said following cell being presented to said pipeline.

67. The networking system of claim 66 wherein said memory is to further to store, along with said packet state information, said packet header portion parsed by said pipeline stage upon its being sent from said third pipeline stage, said memory to also provide said packet header portion to said first pipeline stage upon said following cell being said presented to said pipeline.

68. The networking system of claim 67 further comprising a second memory coupled to said first stage, said second memory to provide said information that identifies a connection over which said cell arrived in response to a parameter associated with said cell.

69. The networking system of claim 68 wherein said parameter is said cell'"'"'s VPI/VCI.

70. The networking system of claim 69 wherein said second memory is a content addressable memory (CAM).

71. The networking system of claim 63 further comprising a first pipeline stage that precedes said pipeline stage in said pipeline and a third pipeline stage that follows said pipeline stage in said pipeline, said first and third pipeline stages coupled to a memory, said memory to store packet state information determined by said pipeline stage upon its being sent from said third pipeline stage, said memory to provide said packet state information to said first pipeline stage upon said following cell being presented to said pipeline.

72. The networking system of claim 71 wherein said memory is to further to store, along with said packet state information, said packet header portion parsed by said pipeline stage upon its being sent from said third pipeline stage, said memory to also provide said packet header portion to said first pipeline stage upon said following cell being said presented to said pipeline.

73. The networking system of claim 63 wherein said packet state information includes a cell count that tracks how many cells of said packet have been evaluated for parsing by said pipeline stage.

74. The networking system of claim 63 further comprising a micro-program memory coupled to said sequencer, said micro-program memory to store micro-programs that are executable by said pipeline stage.

75. The networking system of claim 74 wherein at least one of said micro-programs is to be executed by said pipeline stage for cells carrying a portion of a specific type of packet.

76. The networking system of claim 74 wherein said at least one of said micro-programs contains instructions sufficient for said pipeline stage to determine at least one of the following:

a) a length indicator;

b) a timestamp insert flag;

c) a record route flag.

77. The networking system of claim 63 wherein said pipeline stage further comprises an interface to a free space lists manager so that a pointer can be retrieved within said pipeline cycle, said pointer to point to a location in a packet buffer where payload information (if any) of said packet carried by said following cell will be written into said packet buffer.