Method and apparatus for prioritizing the enqueueing of outbound data packets in a network device

• US 5,974,465 A
• Filed: 01/21/1998
• Issued: 10/26/1999
• Est. Priority Date: 01/21/1998
• Status: Expired due to Term

• Current Assignee: Bethlehem Steel Corporation (ArcelorMittal SA), Palo Alto Networks Incorporated
• Original Assignee: 3Com Corporation (HP Inc.)
• Inventors: Wong, Shian-Tung
• Primary Examiner(s): VU, VIET DUY
• Application Number:
  US09/010,432
• Time in Patent Office: 643 Days
• Field of Search: 709/103, 709/232, 709/233, 709/234, 709/235, 709/238, 709/240, 709/243, 709/244, 709/250, 709/300, 370/229, 370/230, 370/232, 370/235
• US Class Current: 709/234
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 69/324 in the data link layer [OSI layer 2], e.g. HDLC
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

In a switching device coupled to a computer network, a method for enqueing data packets for transmission over the computer network according to a priority scheme. Initially, the switching device is configured to define a hierarchy of priority levels. A number of queue buffers are reserved for each of the priority levels. Furthermore, each application program is assigned a particular priority, depending its relative importance and time-criticalness. When the application program generates an outbound packet, that packet is assigned a corresponding priority. The CPU checks the number of buffers in the queue which are currently available and compares it with the sum of the buffers which were reserved for all priority levels which are higher than the priority of the outbound packet. If the number of available buffers exceeds the sum of the buffers reserved for the priority levels higher than that of the packet, then the packet is stored in the queue. Otherwise, the packet is discarded. Thereby, a subsequent higher priority packet can be preferentially stored in place of a lower priority packet which was earlier received.

Claims

1. In a device coupled to a computer network, a method for enqueing data packets for transmission over the computer network according to a priority scheme, the method comprising the steps of:

defining a priority hierarchy comprised of a plurality of priority levels;

specifying a number of buffers of a plurality of buffers which comprise a queue memory which are to be reserved for each one of the plurality of priority levels;

assigning a priority to a data packet;

determining whether a number of buffers which is currently available in the queue memory is greater than a sum of all buffers which are reserved for priority levels which are higher than the priority of the data packet;

storing the data packet in the queue memory for eventual transmission over the computer network if the number of buffers which is currently available is greater than the sum of all buffers which are reserved for priority levels higher than the priority of the data packet, otherwise not storing the data packet in the queue memory if there is not enough buffers which are currently available that exceed the sum of all buffers reserved for priority levels higher than the priority of the data packet.

2. The method of claim 1 further comprising the step of assigning the priority of the data packet according to an application program which generated the data packet.

3. The method of claim 1 further comprising the step of discarding the data packet if the data packet is not stored in the queue memory.

4. The method of claim 1 further comprising the step of dividing a shared memory into a plurality of areas, each of the areas corresponding to a different queue.

5. The method of claim 4 further comprising the step of examining an address of the data packet to determine which of the plurality of queues the data packet is to be stored.

6. The method of claim 5 further comprising the step of forwarding packets from the plurality of queues to a plurality of interface devices for transmission over the computer network.

7. The method of claim 5 further comprising the step of temporarily storing data packets in a secondary storage area.

8. A network device capable of being coupled to a computer network, wherein packets of data are queued before being transmitted over the computer network according to a priority scheme, the network device comprising:

a bus;

a memory coupled to the bus for storing queued packets;

a processor coupled to the bus which assigns a priority hierarchy comprised of a plurality of priority levels for a plurality of application programs, the central processing unit also specifying an amount of memory which is to be reserved for each one of the plurality of priority levels, wherein a packet is enqueued in the memory only if an amount of memory which is currently available is greater than a sum of all memory which is reserved for priority levels which are higher than the priority of the packet;

an interface device coupled to the processor for transmitting enqueued packets in the memory over the computer network.

9. The apparatus of claim 8, wherein the processor assigns a priority to the packet according to which application program had generated the packet.

10. The apparatus of claim 8, wherein the processor discards the packet if the packet is not stored in the memory.

11. The apparatus of claim 8, wherein the memory is segregated into a plurality of areas, each of the areas corresponding to a different queue.

12. The apparatus of claim 8 further comprising a plurality of interface devices, wherein the packet is stored in a particular one of the plurality of queues and forwarded to a particular one of the interface devices according to an address contained within the packet.

13. The apparatus of claim 8 further comprising a secondary memory for temporarily storing packets before the packets are enqueued.

14. In a network device, an apparatus for enqueing data packets for transmission over a communications network according to a priority scheme, the apparatus comprising:

means for defining a priority hierarchy comprised of a plurality of priority levels;

means for specifying a number of buffers of a plurality of buffers which comprise a queue memory which are to be reserved for each one of the plurality of priority levels;

means for assigning a priority to a data packet;

means for determining whether a number of buffers which is currently available in the queue memory is greater than a sum of all buffers which are reserved for priority levels which are higher than the priority of the data packet;

means for storing the data packet in the queue memory for eventual transmission over the computer network if the number of buffers which is currently available is greater than the sum of all buffers which are reserved for priority levels higher than the priority of the data packet, otherwise not storing the data packet in the queue memory if there is not enough buffers which are currently available that exceed the sum of all buffers reserved for priority levels higher than the priority of the data packet.

15. The apparatus of claim 14 further comprising means for assigning the priority of the data packet according to an application program which generated the data packet.

16. The apparatus of claim 14 further comprising means for discarding the data packet if the data packet is not stored in the queue memory.

17. The apparatus of claim 14 further comprising means for dividing a shared memory into a plurality of areas, each of the areas corresponding to a different queue.

18. The apparatus of claim 17 further comprising means for examining an address of the data packet to determine which of the plurality of queues the data packet is to be stored.

19. The apparatus of claim 18 further comprising means for forwarding packets from the plurality of queues to a plurality of interface devices for transmission over the computer network.

20. The apparatus of claim 19 further comprising means for temporarily storing data packets in a secondary storage area.