Pipeline processing type shaping apparatus and its method

• US 6,976,256 B2
• Filed: 05/25/2001
• Issued: 12/13/2005
• Est. Priority Date: 05/31/2000
• Status: Expired due to Fees

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Nishihara, Motoo
• Primary Examiner(s): An, Meng-Al T.
• Assistant Examiner(s): Tang, Kenneth
• Application Number:
  US09/864,300
• Publication Number:
  US 20010049711A1
• Time in Patent Office: 1,663 Days
• Field of Search: 718/1, 718100-108, 709200-253, 370/218
• US Class Current: 718/102
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/22 Traffic shaping
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]

Abstract

A pipeline processing type shaping apparatus and method in which strict shaping processing can also be implemented for a connection at various speed by adding a simplified circuit configuration. A cache portion is provided that links with the processing of a pipeline processing portion, and this cache portion manages flow information of a packet that is being processed in the pipeline processing portion. When there is a packet that belongs to the same flow, the cache portion transfers a parameter to the pipeline processing portion assuming a virtual packet in which relevant packets are all connected. The pipeline processing portion executes pipeline processing based on this virtual parameter. Consequently, also for a flow at an optional peak-rate speed (reciprocal of the input packet interval that belongs to the same flow) and in any high-speed transmission path interface, a predetermined scheduling time by shaping can always be calculated in real time.

Claims

1. A pipeline processing type shaping apparatus that calculates a transmission scheduling time for each input packet to said apparatus by performing pipeline processing by a pipeline processing portion which includes a plurality of processing blocks, said apparatus comprising:

a management memory that stores the most recent scheduling time allocated to a packet, which has been processed by said pipeline processing portion, for each of packet flow identifiers;

a storage portion that includes a plurality of internal registers, which are equal to the number of processing blocks in said pipeline processing portion, and each stores a number of packets and a total sum length of packets having the same packet flow identifier and currently being processed in said pipeline processing portion; and

a calculating part that calculates the transmission scheduling time of an input packet, being processed by said pipeline processing portion, in accordance with the most recent scheduling time being managed by said management memory and packet length for which said input packet length and said total sum length of packets stored in said internal register corresponding to the same packet flow identifier as said input packet are added.

2. The pipeline processing type shaping apparatus according to claim 1, wherein the calculating part comprising:

a reading block that transfers a packet flow identifier of said input packet to said storage portion and receives said total sum length of packets stored in said internal register corresponding to the same packet flow identifier; and

a calculating block that calculates the transmission scheduling time for said input packet in accordance with the most recent scheduling time being managed by the management memory and packet length for which said input packet length and said total sum length of packets received by said reading block are added.

3. The pipeline processing type shaping apparatus according to claim 1, wherein said storage portion further comprising:

a storage information update part that increments, in response to an input of packet to said pipeline processing portion, the number of packets and the total sum length of packets stored in one of said internal registers corresponding to a packet flow identifier of said input packet, and decrements, in response to an output of packet from said pipeline processing portion, the number of packets and the total sum length of packets stored in one of said internal registers corresponding to a packet flow identifier of said output packet.

4. The pipeline processing type shaping apparatus according to claim 2, wherein said storage portion further comprising:

a storage information update part that increments, in response to an input of packet to said pipeline processing portion, the number of packets and the total sum length of packets stored in one of said internal registers corresponding to a packet flow identifier of said input packet, and decrements, in response to an output of packet from said pipeline processing portion, the number of packets and the total sum length of packets stored in one of said internal resisters corresponding to a packet flow identifier of said output packet.

5. A pipeline processing type shaping method that performs the pipeline processing by a pipeline processing portion which includes a plurality of processing blocks for calculating a transmission scheduling time for each input packet to said pipeline processing portion, said method comprising:

storing, into a management memory, the most recent scheduling time allocated to a packet, which has been processed by said pipeline processing portion, for each of packet flow identifiers;

storing, into one of internal registers which are equal to the number of processing blocks in said pipeline processing portion, a number of packets and a total sum length of packets having the same packet flow identifier and currently being processed in said pipeline processing portion; and

calculating the transmission scheduling time of an input packet, being processed by said pipeline processing portion, in accordance with the most recent scheduling time managed by said management memory and packet length for which said input packet length and said total sum length of packets stored in said internal register corresponding to the same packet flow identifier as said input packet are added.

6. The pipeline processing type shaping method according to claim 5, wherein the calculating step comprising:

reading said total sum length of packets stored in one of said internal registers corresponding to the same packet flow identifier as said input packet; and

calculating the transmission scheduling time of said input packet in accordance with the most recent scheduling time managed by said management memory and packet length for which said input packet length and said total sum length of packets read in said reading step are added.

7. The pipeline processing type shaping method according to claim 5, further comprising:

incrementing, in response to an input of packet to said pipeline processing portion, the number of packets and the total sum length of packets stored in one of said internal registers corresponding to a packet flow identifier of said input packet; and

decrementing, in response to an output of packet from said pipeline processing portion, the number of packets and the total sum length of packets stored in one of said internal registers corresponding to a packet flow identifier of said output packet.

8. The pipeline processing type shaping method according to claim 6, further comprising:

incrementing, in response to an input of packet to said pipeline processing portion, the number of packets and the total sum length of packets stored in one of said internal registers corresponding to a packet flow identifier of said input packet; and

decrementing, in response to an output of packet from said pipeline processing portion, the number of packets and the total sum length of packets stored in one of said internal registers corresponding to a packet flow identifier of said output packet.

9. A recording medium that records a control program of a pipeline processing type shaping method that performs the pipeline processing by a pipeline processing portion which includes a plurality of processing blocks for calculating a transmission scheduling time for each input for performing the method step packet to said pipeline processing portion, said control program comprising:

storing, into a management memory, the most recent scheduling time allocated to a packet, which has been processed by said pipeline processing portion, for each of packet flow identifiers;

storing, into one of internal registers which are equal to the number of processing blocks in said pipeline processing portion, a number of packets and a total sum length of packets having the same packet flow identifier and currently being processed in said pipeline processing portion; and

calculating the transmission scheduling time of an input packet, being processed by said pipeline processing portion, in accordance with the most recent scheduling time managed by said management memory and packet length for which said input packet length and said total sum length of packets stored in said internal register corresponding to the same packet flow identifier as said input packet are added.

10. The recording medium that records a control program of a pipeline processing type shaping method according to claim 9, where the control program of the calculating step comprising:

reading said total sum length of packets stored in one of said internal registers corresponding to the same packet flow identifier as said input packet; and

calculating the transmission scheduling time of an input packet, being processed by said pipeline processing portion, in accordance with the most recent scheduling time managed by said management memory and packet length for which said input packet length and said total sum length of packets read in said reading step are added.

11. The recording medium according to claim 9, the control program further comprising a control program for:

incrementing, in response to an input of packet to said pipeline processing portion, the number of packets and the total sum length of packets stored one of said internal registers corresponding to a packet flow identifier of said input packet; and

decrementing, in response to an output packet from said pipeline processing portion, the number of packets and the total sum length of packets stored in one of said internal registers corresponding to a packet flow identifier of said output packet.

12. The recording medium according to claim 10, the control program further comprising a control program for:

incrementing, in response to an input of packet to said pipeline processing portion, the number of packets and the total sum length of packets stored in one of said internal registers corresponding to a packet flow identifier of said input packet; and

decrementing, in response to an output of packet from said pipeline processing portion, the number of packets and the total sum length of packets stored in one of said internal registers corresponding to a packet flow identifier of said output packet.