Method and apparatus for processing high and low priority frame data transmitted in a data communication system

• US 6,466,580 B1
• Filed: 02/23/1999
• Issued: 10/15/2002
• Est. Priority Date: 02/23/1999
• Status: Expired due to Fees

• Current Assignee: GlobalFoundries, Inc.
• Original Assignee: Advanced Micro Devices, Inc.
• Inventors: Leung, Eric Tsin-Ho
• Primary Examiner(s): Olms, Douglas
• Assistant Examiner(s): Sam, Phirin
• Application Number:
  US09/255,707
• Time in Patent Office: 1,330 Days
• Field of Search: 370/412, 370/413, 370/415, 370/417, 370/419, 370/422, 370/444, 370/455, 370/252, 370/395, 370/428, 370/351, 370/370, 370/362, 370/355, 370/356, 370/360, 370/359, 370/230, 370/229, 370/235, 370/352, 370/354, 370/395.42, 370/395.7, 370/395.71, 370/395.72, 370/400, 370/401, 340/825.5, 340/825.03, 340/825.51, 340/825.52
• US Class Current: 370/412
• CPC Class Codes: H04L 49/205 Quality of Service based
• 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/352 Gigabit ethernet switching [GBPS]

Abstract

A multiport data communication system for switching data packets between ports includes a plurality of receive ports for receiving data packets, a plurality of transmit ports for transmitting data packets, circuitry deciding whether each received data packet is one of high priority and low priority, and a memory for storing each received data packet. A memory location designator is provided for each data packet indicating where the corresponding data packet is stored in the memory and a plurality of queuing devices corresponding to the plurality of transmit ports queue the memory location designators. Each queuing device has a high priority queue queuing memory location designators corresponding to data packets of high priority to be retrieved from the memory an transmitted by the respective transmit port and a low priority queue queuing memory location designators corresponding to data packets of low priority to be retrieved from the memory and transmitted by the respective transmit port. Transferring circuitry transfers the data packets from the memory to a transmit queue corresponding to each respective transmit port and includes logic circuitry corresponding to each transmit queue. The logic circuitry determines whether the low priority queue of a respective queuing device has a memory location designator for a data packet to be retrieved from the memory and sent to the corresponding transmit queue only when the high priority queue of the respective queuing device is empty of memory location designators.

Claims

1. A multiport data communication system for switching data packets between ports, the data communication system comprising:

a plurality of receive ports for receiving data packets;

a plurality of transmit ports for transmitting data packets;

circuitry deciding whether each received data packet is one of high priority and low priority;

a common memory for storing each received data packet, the common memory including an overflow area;

circuitry providing a memory location designator for each data packet indicating where the corresponding data packet is stored in the common memory;

a plurality of queuing devices corresponding to the plurality of transmit ports, each queuing device having a high priority queue queuing memory location designators corresponding to data packets of high priority to be transmitted by the respective transmit port and a low priority queue queuing memory location designators corresponding to data packets of low priority to be transmitted by the respective transmit port, and each high priority queue and low priority queue including a write side and a read side configured to hold a predetermined number of memory location designators; and

transferring circuitry transferring the data packets from the common memory to a respective transmit port, the transferring circuitry including a common transmit queue for each transmit port and all data packets of high priority for a respective transmit port being transferred from the common memory and placed in the corresponding transmit queue prior to transferring any data packet of low priority for the respective transmit port, each data packet in each corresponding transmit queue being read from said each corresponding transmit queue without regard as to the priority of said each data packet, wherein

when a number of memory location designators held in a respective read side is less than the predetermined number, memory location designators are passed from the corresponding write side to said respective read side of each high priority queue and each low priority queue of each queuing device, and

when the number of memory location designators held in said respective read side of either the high priority queue and the low priority queue of said each of the queuing devices is equal to the predetermined number, memory location designators are passed from the corresponding write side to the overflow area of the common memory and then passed from the respective overflow area of the memory to the respective read side of the corresponding queuing device when the number of memory location designators held in the respective read side becomes less than the predetermined number.

2. A multiport data communication system for switching data packets between ports, the data communication system comprising:

a plurality of receive ports for receiving data packets;

a plurality of transmit ports for transmitting data packets;

circuitry deciding whether each received data packet is one of high priority and low priority;

a memory for storing each received data packet, the memory including an overflow area;

transferring circuitry transferring, from the memory to a respective transmit port, all data packets of high priority corresponding to the transmit port prior to transferring any data packet of low priority corresponding to the transmit port;

circuitry providing a memory location designator for each data packet indicating where the corresponding data packet is stored in the memory;

a plurality of queuing devices corresponding to the plurality of transmit ports, each queuing device having a high priority queue queuing memory location designators corresponding to data packets of high priority to be transmitting by the respective transmit port and a low priority queue queuing memory location designators corresponding to data packets of low priority to be transmitting by the respective transmit port;

the overflow area of the memory including a high priority area and a low priority area corresponding to each queuing device; and

each high priority queue and low priority queue including a write side and a read side configured to hold a predetermined number of memory location designators, wherein

when a number of memory location designators held in the read side of either the high priority queue and the low priority queue of each of the queuing devices is less than the predetermined number, memory location designators are passed from the respective write side to the corresponding read side of the queuing device,

when the number of memory location designators held in the read side of either the high priority queue and the low priority queue of said each of the queuing devices is equal to the predetermined number, memory location designators are passed from the write side to the respective priority area of the overflow area of the memory corresponding to the queuing device and memory location designators are passed from the respective overflow area of the memory to the read side of the corresponding queuing device when the number of memory location designators held in the read side of the corresponding queuing device becomes less than the predetermined number, and

the transferring circuitry includes

a transmit queue for each transmit port and said all data packets of high priority are transferred from the memory and placed in the transmit queue for said each transmit port prior to said any data packet of low priority, and

logic circuitry corresponding to each transmit queue, said logic circuitry determining whether the low priority queue of a respective queuing device has a memory location designator for a data packet to be retrieved from the memory and sent to the corresponding transmit queue only when the high priority queue of said respective queuing device is empty of memory location designators.

3. The system of claim 2, wherein

the high priority and low priority queues of each queuing device and each transmit queue are FIFO queues,

each logic circuitry retrieves memory location designators from the bottom of the high priority and low priority queues of the corresponding queuing device and sends data packets retrieved from the memory to the top of the respective transmit queue, and

all data packets queued in the respective transmit queue are transmitted from the transmit port in the order queued.

4. In a communication system having a plurality of receive ports for receiving data packets, a plurality of transmit ports for transmitting data packets with each transmit port including a common transmit queue, circuitry providing a memory location designator for each data packet indicating where the corresponding data packet is stored a common memory having an overflow area, and a plurality of queuing devices corresponding to said plurality of transmit ports, each queuing device having a high priority queue and a low priority queue with each high priority queue and each low priority queue including a write side and a read side configured to hold a predetermined number of memory location designators, a method of processing received data packets for transfer to the plurality of transmit ports comprising:

for each received data packet, deciding whether said each received data packet is one of high priority and low priority;

for each transmit port,

transferring data packets from said common memory to the corresponding transmit queue of said each transmit port which are of high priority prior to transferring any data packet from said common memory to the corresponding transmit queue of said each transmit port which is of low priority, and

reading each data packet from each corresponding transmit queue without regard as to the priority of said each data packet, wherein

when a number of memory location designators held in a respective read side of a corresponding queuing device is less than the predetermined number, memory location designators are passed from the corresponding write side to said respective read side of each high priority queue and each low priority queue of each queuing device, and

when the number of memory location designators held in said respective read side of the corresponding queuing device is equal to the predetermined number, memory location designators are passed from the corresponding write side to the overflow area of the common memory and then passed from the overflow area of the memory to the respective read side of the corresponding queuing device when the number of memory location designators held in the respective read side becomes less than the predetermined number.

5. In a communication system having a plurality of receive ports for receiving data packets and a plurality of transmit ports for transmitting data packets, a method of processing received data packets for transfer to the plurality of transmit ports comprising:

for each received data packet, deciding whether said each received data packet is one of high priority and low priority;

transferring the received data packets to a memory, the memory having an overflow area including a high priority area and a low priority area corresponding to each queuing device; and

for each transmit port, transferring data packets from said memory to said each transmit port which are of high priority prior to transferring any data packet from said memory to said each transmit port which is of low priority,

the communication system further having a plurality of queuing devices and a plurality of transmit queues each corresponding to said plurality of transmit ports, each queuing device having a high priority queue and a low priority queue with each high priority queue and each low priority queue including a write side and a read side configured to hold a predetermined number of memory location designators, and the method further comprising;

transferring the received data packets to the memory at a location indicated by a memory location indicator;

based on a result of said deciding, storing each memory location indicator in the respective read side of one of the high priority queue and low priority queue corresponding to each transmit port;

when a number of memory location designators held in the read side of the high priority queue and the low priority queue of each of the queuing devices is less than the predetermined number, passing memory location designators from the respective write side to the corresponding read side of the queuing device;

when the number of memory location designators held in the read side of the high priority queue and the low priority queue of said each of the queuing devices is equal to the predetermined number, passing memory location designators from the write side to the respective priority area of the overflow area of the memory corresponding to the queuing device and passing memory location designators from the respective overflow area of the memory to the read side of the corresponding queuing device when the number of memory location designators held in the read side of the corresponding queuing device becomes less than the predetermined number;

for each respective transmit port, transferring from said memory to the corresponding transmit queue all data packets corresponding to memory location indicators in the high priority queue of the respective queuing device prior to transferring from said memory to the corresponding transmit queue any data packet corresponding to a memory location indicator in the low priority queue of the respective queuing device; and

determining whether the low priority queue of the respective queuing device has a memory location indicator for a data packet to be retrieved from the memory and sent to the corresponding transmit queue only when the high priority queue of said respective queuing device is empty.

6. The method of claim 5, wherein

the high priority and low priority queues of each queuing device and each transmit queue are FIFO queues, and said method further comprising:

retrieving memory location indicators from the bottom of the high priorty and low priority queues of the respective queuing device and sending data packets retrieved from the memory to the top of the respective transmit queue; and

transmitting all data packets queued in the respective transmit queue from the transmit port in the order queued.