Packet buffer device and packet switching device

• US 6,850,522 B2
• Filed: 12/26/2000
• Issued: 02/01/2005
• Est. Priority Date: 12/27/1999
• Status: Expired due to Fees

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Saito, Toshitada, Hasegawa, Jun, Shimojo, Yoshimitsu
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): SEFCHECK, GREGORY B
• Application Number:
  US09/745,474
• Publication Number:
  US 20010040891A1
• Time in Patent Office: 1,498 Days
• Field of Search: 370/254, 370/351, 370/400, 370/401, 370/408, 370/412, 370/428, 370/432, 370392-394, 370/390, 370/389
• US Class Current: 370/390
• CPC Class Codes: H04L 2012/5681 Buffer or queue management
• CPC Class Codes: H04L 49/30 Peripheral units, e.g. input or output ports
• CPC Class Codes: H04L 49/3018 Input queuing
• CPC Class Codes: H04L 49/3027 Output queuing
• CPC Class Codes: H04L 49/3081 ATM peripheral units, e.g. policing, insertion or extraction
• CPC Class Codes: H04L 49/351 for local area network [LAN], e.g. Ethernet switches
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

In respective leaf tables (LT(1) to LT(m)) of a coupling management table (20), there are provided delete operation identifiers (D(1) to D(m)) indicating that leaf queues (LQ) respectively next to them toward the upstream direction are under delete operation. When one of the leaf queues (LQ(n)) should be deleted, if the leaf queue (LQ(n)) to be deleted stores any element, the delete operation identifier (D(n+1)) is set to 1. Thereby, the leaf table (LT(n−1)) can acknowledge that the leaf queue (LQ(n)) is currently under delete operation. Therefore, the coupled packet queue after deletion of the leaf queue and the coupling management table can be maintained consistent.

Claims

1. A packet buffer device comprising:

a coupled packet queue prepared for each flow, the coupled packet queue having a plurality of leaf queues individually formed for individual copy destinations belonging to a common flow to accumulate packets as elements and sequentially transfer elements sent out from one of the leaf queues located upstream to one of the leaf queues located downstream such that packets are sequentially sent out from the copy destinations belonging to the common flow;

a coupling management table having a plurality of leaf tables individually associated with and prepared for the individual leaf queues to manage elements accumulated in the coupled packet queue; and

a detector configured to cause the leaf table, which is associated with the leaf queue located next to the leaf queue to be deleted toward the upstream direction to detect that the leaf queue to be deleted next toward the downstream direction is under delete operation, when the leaf queue to be deleted is performing a deleting process,

wherein the detector includes delete operation identifiers for the leaf queues, respectively, the delete operation identifiers indicating that the leaf queues are under the delete operation.

2. The packet buffer device according to claim 1 wherein the delete operation identifiers are individually provided in the individual leaf tables, which are next to the individual leaf tables associated with the leaf queues to be indicated as being under delete operation toward the downstream direction.

3. The packet buffer device according to claim 2 wherein the delete operation identifier of one of the leaf queues at the down stream end of the coupled packet queue is provided in a root table different from the leaf tables.

4. The packet buffer device according to claim 1 wherein the coupling management table includes a head pointer for pointing to an element accumulated at the head of the leaf queue, when any element is contained in the Ieaf queue.

5. The packet buffer device according to claim 4 wherein, when no element is accumulated in the leaf queue located next to the leaf queue to be deleted toward the downstream direction, the value of the head pointer of the leaf table to be deleted substitutes into the bead pointer of the leaf table located next to the leaf queue to be deleted toward the downstream direction.

6. The packet buffer device according to claim 5 wherein, when the leaf queue located next toward the downstream direction is detected to be under delete operation by the detector, it is prohibited that an element heretofore located at the head of the leaf queue next to the leaf queue to be deleted toward the upstream direction is changed as the head pointer of the leaf queue next to the leaf queue to be deleted toward the downstream direction.

7. The packet buffer device according to claim 6 wherein it is prohibited that an element is transferred from the leaf queue next to the leaf queue to be deleted toward the upstream direction to the leaf queue to be deleted.

8. The packet buffer device according to claim 1 wherein the coupling management table includes total number information that indicates die total number of elements accumulated in the coupled packet queue.

9. The packet buffer device according to claim 8 wherein to total number information is provided in a root table different from the leaf tables.

10. The packet buffer device according to claim 8 which further comprises a subtracter configured to subtract the number of elements accumulated in the leaf queue to be deleted from the total number information, when the leaf queue to be deleted is located at the downstream end of the coupled packet queue.

11. The packet buffer device according to claim 10 wherein, after to subtracter has subtracted, the number of elements sent out from the leaf queue to be deleted is no longer subtracted from the total number information even if the leaf queue to be deleted sends out elements.

12. The packet buffer device according to claim 11 wherein it is prohibited that an element is transferred from the leaf queue next to the leaf queue to be deleted toward the upstream direction to the leaf queue to be deleted.

13. A packet buffer device comprising:

a coupled packet queue prepared for each flow, the coupled packet queue having a plurality of leaf queues individually formed for individual copy destinations belonging to a common flow to accumulate packets as elements and sequentially transfer elements sent out from one of the leaf queues located upstream to one of the leaf queues located downstream such that packets are sequentially sent out from the copy destinations belonging to the common flow;

a coupling manager configured to manage elements accumulated in the coupled packet queue and having a total number information storage to be stored the total number of elements accumulated in the coupled packet queue;

a subtractor configured to subtract the number of elements accumulated in the leaf queue to be deleted from the total number information stored in the total number information storage, when the leaf queue to be deleted is located at the downstream end of the coupled packet queue and the leaf queue to be deleted is performing a deleting process; and

a detector configured to cause the leaf table, which is associated with the leaf queue located next to the leaf queue to be deleted toward the upstream direction, to detect that the leaf queue to be deleted next toward the downstream direction is under delete operation, when the leaf queue to be deleted is performing a deleting process,

wherein the detector includes delete operation identifiers for the leaf queues, respectively, the delete operation identifiers indicating that the leaf queues are under the delete operation, respectively.

14. The packet buffer device according to claim 13 wherein the coupling manager comprises plurality of leaf tables individually associated with and prepared for the individual leaf queues.

15. The packet buffer device according to claim 14 wherein the total number information storage is provided in a root table different from the leaf tables.

16. The packet buffer device according to claim 13 wherein, after the subtractor has subtracted, the number of elements sent out from the leaf queue to be deleted is no longer subtracted from the total number information stored in the total number information storage even if the leaf queue to be deleted sends out elements.

17. The packet buffer device according to claim 13 wherein it is prohibited that an element is transferred from the leaf queue next to the leaf queue to be deleted toward the upstream direction to the leaf queue to be deleted.

18. A packet switching device comprising:

a routing switch configured to switch each inputted packet, based on header information contained in the packet; and

at least one packet buffer device provided in front stage and/or rear stage of the routing switch,

wherein the packet buffer device including;

a coupled packet queue prepared for each flow, the coupled packet queue having a plurality of leaf queues individually formed for individual copy destinations belonging to a common flow to accumulate packets as elements and sequentially transfer elements sent out from one of the leaf queues located upstream to one of the leaf queues located downstream such that packets are sequentially sent out from the copy destinations belonging to the common flow;

a coupling management table having a plurality of leaf tables individually associated with and prepared for the individual leaf queues to manage elements accumulated in the coupled packet queue; and

a detector configured to cause the leaf table, which is associated with the leaf queue located next to the leaf queue to be deleted toward the upstream direction, to detect that the leaf queue to be deleted next toward the downstream direction is under delete operation, when the leaf queue to be deleted is performing a deleting process,

wherein the detector includes delete operation identifiers for the leaf queues, respectively, the delete operation identifiers indicating that the leaf queues are under the delete operation, respectively.

19. A packet switching device comprising:

a routing switch configured to switch each inputted packet, based on header information contained in the packet; and

at least one packet buffer device provided in front stage and/or rear stage of the routing switch,

wherein the packet buffer device including;

a coupled packet queue prepared for each flow, the coupled packet queue having a plurality of leaf queues individually formed for individual copy destinations belonging to a common flow to accumulate packets as elements and sequentially transfer elements sent out from one of the leaf queues located upstream to one of the leaf queues located downstream such that packets are sequentially sent out from the copy destinations belonging to the common flow;

a coupling manager configured to manage elements accumulated in the coupled packet queue and having a total number information storage to be stored the total number of elements accumulated in the coupled packet queue;

a subtractor configured to subtract the number of elements accumulated in the leaf queue to be deleted from the total number information stored in the total number information storage, when the leaf queue to be deleted is located at the downstream end of the coupled packet queue and the leaf queue to be deleted is performing a deleting process; and

a detector configured to cause the leaf table, which is associated with the leaf queue located next to the leaf queue to be deleted toward the upstream direction, to detect that the leaf queue to be deleted next toward the downstream direction is under delete operation, when the leaf queue to be deleted is performing a deleting process,

wherein the detector includes delete operation identifiers for the leaf queues, respectively, the delete operation identifiers indicating that the leaf queues are under the delete operation, respectively.