Packet buffer device and packet switching device

• US 20010040891A1
• Filed: 12/26/2000
• Published: 11/15/2001
• Est. Priority Date: 12/27/1999
• Status: Active Grant

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Hasegawa, Jun, Shimojo, Yoshimitsu, Saito, Toshitada
• Granted Patent: US 6,850,522 B2
• Time in Patent Office: Days
• US Class Current: 370/412
• 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 send 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 performed a deleting process.

2. The packet buffer device according to

claim 1

wherein the detector is made by providing delete operation identifiers for the leaf queues, respectively, the delete operation identifiers indicating that the leaf queues are under delete operation, respectively.

3. The packet buffer device according to

claim 2

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.

4. The packet buffer device according to

claim 3

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.

5. The packet buffer device according to

claim 1

wherein the coupling management table includes a head pointer for pointing an element accumulated at the leading of the leaf queue, when any element is contained in the leaf queue.

6. The packet buffer device according to

claim 5

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 head pointer of the leaf table located next to the leaf queue to be deleted toward the downstream direction.

7. The packet buffer device according to

claim 6

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 leading 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.

8. The packet buffer device according to

claim 7

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.

9. The packet buffer device according to

claim 1

wherein the coupling management table includes total number information that indicates the total number of elements accumulated in the coupled packet queue.

10. The packet buffer device according to

claim 9

wherein the total number information is provided in a root table different from the leaf tables.

11. The packet buffer device according to

claim 9

which further comprises a subtractor 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.

12. The packet buffer device according to

claim 11

wherein, after the subtractor has subtracted, the number of elements sent out from the leaf queue to be deleted is no more subtracted from the total number information even if the leaf queue to be deleted sends out elements.

13. The packet buffer device according to

claim 12

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.

14. 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 send 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; and

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 performed a deleting process.

15. The packet buffer device according to

claim 14

wherein the coupling manager comprises a plurality of leaf tables individually associated with and prepared for the individual leaf queues.

16. The packet buffer device according to

claim 15

wherein the total number information storage is provided in a root table different from the leaf tables.

17. The packet buffer device according to

claim 14

wherein, after the subtractor has subtracted, the number of elements sent out from the leaf queue to be deleted is no more subtracted from the total number information stored in the total number information storage even if the leaf queue to be deleted sends out elements.

18. The packet buffer device according to

claim 14

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.

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 send 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 performed a deleting process.

20. 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 send 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; and

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 performed a deleting process.