Multicopy queue structure with searchable cache area

• US 6,061,351 A
• Filed: 12/18/1997
• Issued: 05/09/2000
• Est. Priority Date: 02/14/1997
• Status: Expired due to Term

• Current Assignee: Advanced Micro Devices, Inc.
• Original Assignee: Advanced Micro Devices, Inc.
• Inventors: Erimli, Bahadir, Runaldue, Thomas J.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): VANDERPUYE, KENNETH N
• Application Number:
  US08/993,880
• Time in Patent Office: 873 Days
• Field of Search: 370/390, 370/412, 370/413, 370/414, 370/415, 370/417, 370/428, 370/401, 711/117, 711/118, 711/113, 711/111
• US Class Current: 370/390
• CPC Class Codes: G06F 5/06 for changing the speed of data flow, i.e. speed regularising or timing, e.g. delay lines, FIFO buffers; over- or underrun control therefor G06F7/78 takes precedence
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast
• CPC Class Codes: H04L 41/0213 Standardised network management protocols, e.g. simple network management protocol [SNMP]
• CPC Class Codes: H04L 49/103 using a shared central buffer; using a shared memory
• CPC Class Codes: H04L 49/205 Quality of Service based
• CPC Class Codes: H04L 49/255 Control mechanisms for ATM switching fabrics
• CPC Class Codes: H04L 49/30 Peripheral units, e.g. input or output ports
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/3027 Output queuing
• CPC Class Codes: H04L 49/351 for local area network [LAN], e.g. Ethernet switches
• CPC Class Codes: H04L 49/354 for supporting virtual local area networks [VLAN]
• CPC Class Codes: H04L 49/45 Arrangements for providing or supporting expansion
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/901 using storage descriptor, e.g. read or write pointers
• CPC Class Codes: H04L 49/9047 including multiple buffers, e.g. buffer pools
• CPC Class Codes: H04L 49/9057 Arrangements for supporting packet reassembly or resequencing
• CPC Class Codes: H04L 49/9073 Early interruption upon arrival of a fraction of a packet
• CPC Class Codes: H04L 49/9078 using an external memory or storage device
• CPC Class Codes: H04Q 2213/1316 Service observation, testing
• CPC Class Codes: H04Q 2213/13162 Fault indication and localisation
• CPC Class Codes: H04Q 3/54591 : Supervision, e.g. fault localisation, traffic measurements, avoiding errors, failure recovery, monitoring, statistical analysis

Abstract

An arrangement and a method of maintaining a count of the number of copies of a frame that have been transmitted from a network switch uses a cache memory to store the number of copies of a frame to be transmitted from the network switch. A queue is used to queue entries that indicate the transmission of a copy of a frame, and these queued entries are released to a buffer manager. Whenever a transmission is made of a copy of this frame, and the buffer manager examines the entry indicating this transmission after the entry leaves the queue, the buffer manager searches for a corresponding entry in the cache memory and changes the copy number (i.e., the count of the number of transmissions) of that frame in the cache memory.

Claims

1. An arrangement for maintaining a count of the copies of a frame that are transmitted from a network switch, comprising:

a multicopy queue configured to receive and queue entries, each entry having a frame identifier and a copy number, each copy number being either a positive or negative value, a copy number with a positive value representing the total number of copies of that frame to be transmitted, a copy number with a negative value representing a transmission of one of the copies of that frame that has occurred;

a searchable first memory configured to receive and store the entries from the multicopy queue that have positive copy numbers; and

a buffer manager configured to examine the entries exiting the multicopy queue, and when an entry from the multicopy queue contains a negative copy number, search the first memory for an entry having the same frame identifier as the entry with the negative copy number, and decrement the copy number of the entry in the first memory having that frame identifier if the copy number of that entry in the first memory is greater than one, and delete that entry in the first memory if the copy number is equal to one.

2. The arrangement of claim 1, wherein the frame identifiers are frame pointers that point to a location in a second memory where the frame is stored.

3. The arrangement of claim 2, wherein the first memory is a cache memory.

4. The arrangement of claim 2, further comprising the second memory which is configured to store the frames in buffers.

5. The arrangement of claim 4, wherein the buffers in the second memory have buffer headers with a copy number area in which a copy number for the frame stored in that buffer is storeable.

6. The arrangement of claim 5, wherein the buffer manager is further configured to write an entry with a positive copy number exiting from the multicopy queue into the first memory, and if the first memory is full prior to writing the entry with the positive copy number, remove an oldest entry from the first memory and write the copy number of that entry into the copy number area of the buffer header of the buffer that stores the frame pointed to by the frame pointer in the entry removed by the buffer manager.

7. The arrangement of claim 6, wherein the buffer manager is further configured to retrieve the copy number from the copy number area of the buffer that stores the frame pointed to by the frame pointer in the entry containing the negative copy number, when the search of the first memory by the buffer manager does not locate in the first memory an entry having the same identifier as the entry with the negative copy number.

8. A memory arrangement comprising,

a first memory configured to store entries, each entry having a data pointer that points to data stored in a second memory and an associated data item;

and

a second memory configured to store the data at locations in the second memory pointed to by the data pointer, wherein the locations in the second memory are configured to store the associated data item with the data, such that the second memory is an extension of the first memory to store the associated data items;

wherein the first memory is a searchable cache, the data is a frame of data, the data pointer is a frame pointer, and the associated data item is a copy number indicating the number of copies of the frame are to be transmitted from a device.

9. The memory arrangement of claim 8, further comprising a buffer manager configured to examine entries, and when an entry contains a negative copy number, search the cache for an entry having the same frame pointer as the entry with the negative copy number, and decrement the copy number of the entry in the cache having that frame pointer if the copy number of that entry in the cache is greater than one, and delete that entry in the cache if the copy number is equal to one.

10. The memory arrangement of claim 9, wherein the buffer manager is further configured to write an entry with a positive copy number into the cache, and if the cache is full prior to writing the entry with the positive copy number, remove an oldest entry from the cache and write the copy number of that entry into a copy number area at the location in the second memory that stores the frame pointed to by the frame pointer in the entry removed from the cache by the buffer manager.

11. The memory arrangement of claim 10, wherein the buffer manager is further configured to retrieve the copy number from the copy number area at the location that stores the frame pointed to by the frame pointer in the entry containing the negative copy number, when the search of the cache by the buffer manager does not locate in the cache an entry having the same identifier as the entry with the negative copy number.

12. An arrangement for maintaining a count of a number of copies of a data item to be transmitted from a device, comprising:

a first memory in which entries are stored, each entry stored in the first memory corresponding to a different data item of which multiple copies are to be transmitted from a device, each entry having a pointer which points to a location in a second memory in which the data item is stored and a copy number which indicates how many copies of the data item remain to be transmitted; and

a manager device configured to adjust the copy number in one of the entries stored in the first memory when a copy of the data item with the same pointer as that entry in the first memory is transmitted from the device.

13. The arrangement of claim 12, wherein the manager device is further configured to receive and examine entries in the device, wherein the entries in the device include the entries to be stored in the first memory, and entries that include said pointer and a negative copy number which indicates that one copy of the data item pointed to by the pointer has been transmitted from the device, and to adjust the copy number of one of the entries stored in the first memory when the manager device receives an entry with a negative copy and a pointer that matches the pointer of that entry stored in the first memory.

14. The arrangement of claim 13, wherein the device is a network switch, the manager device is a buffer manager of the multiport switch, the first memory is a cache memory, the data item is a frame of data, and the pointer is a frame pointer.

15. A multiport switch arrangement for a packet switched network, the switch configured to transmit multiple copies of a single frame, the switch arrangement comprising:

a multicopy queue configured to receive and queue entries, each entry having a frame pointer and a copy number, each copy number being either a positive or negative value, a copy number with a positive value representing the total number of copies of that frame to be transmitted, a copy number with a negative value representing a transmission of one of the copies of that frame that has occurred;

a searchable first memory configured to receive and store the entries from the multicopy queue that have positive copy numbers; and

a buffer manager configured to examine the entries exiting the multicopy queue, and when an entry from the multicopy queue contains a negative copy number, search the first memory for an entry having the same frame pointer as the entry with the negative copy number, and decrement the copy number of the entry in the first memory having that frame pointer if the copy number of that entry in the first memory is greater than one, and delete that entry in the first memory if the copy number is equal to one.

16. The switch arrangement of claim 15, wherein the frame pointer points to a location in a second memory where the frame is stored.

17. The switch arrangement of claim 16, further comprising the second memory which is configured to store the frames in buffers.

18. The switch arrangement of claim 17, wherein the buffers in the second memory have buffer headers with a copy number area in which a copy number for the frame stored in that buffer is storeable.

19. The switch arrangement of claim 18, wherein the buffer manager is further configured to write an entry with a positive copy number exiting from the multicopy queue into the first memory, and if the first memory is full prior to writing the entry with the positive copy number, remove an oldest entry from the first memory and write the copy number of that entry into the copy number area of the buffer header of the buffer that stores the frame pointed to by the frame pointer in the entry removed by the buffer manager.

20. The switch arrangement of claim 19, wherein the buffer manager is further configured to retrieve the copy number from the copy number area of the buffer that stores the frame pointed to by the frame pointer in the entry containing the negative copy number, when the search of the first memory by the buffer manager does not locate in the first memory an entry having the same identifier as the entry with the negative copy number.

21. A method of maintaining a count of the number of transmissions of a frame from a network switch, comprising the steps of:

loading a searchable first memory with entries, with each entry comprising a frame identifier and a copy number indicating the number of copies of that frame that remain to be transmitted from the network switch;

searching the first memory for an entry, when a frame is transmitted, that has the same frame identifier as the transmitted frame; and

decrementing the copy number of the entry in the first memory when the search of the first memory locates an entry with the same frame identifier as the transmitted frame.

22. The method of claim 21, further comprising the step of:

loading a multicopy queue with entries, each entry having a frame pointer and a copy number, each copy number being either a positive or negative value, a copy number with a positive value representing the total number of copies of that frame to be transmitted, a copy number with a negative value representing a transmission of one of the copies of that frame that has occurred; and

wherein the step of loading the first memory with entries includes loading only those entries exiting from the multicopy queue that have a positive copy number.

23. The method of claim 22, further comprising the step of determining whether the first memory is full of entries prior to writing the entry with the positive copy number, and if the first memory is full, removing an oldest entry from the first memory and writing the copy number of that entry into a copy number area of a location in a second memory that stores the frame pointed to by the frame pointer in the removed entry.

24. The method of claim 23, further comprising the steps of retrieving the copy number from the copy number area of the location that stores the frame pointed to by the frame pointer in the entry containing the negative copy number, when the search of the first memory does not locate in the first memory an entry having the same pointer as the entry with the negative copy number.