Packet prioritization protocol for a large-scale, high speed computer network

• US 6,931,003 B2
• Filed: 12/27/2000
• Issued: 08/16/2005
• Est. Priority Date: 02/09/2000
• Status: Expired due to Term

• Current Assignee: CommWorks Solutions, LLC (IP Investments Group LLC), Affymetrix, Inc. (Thermo Fisher Scientific Incorporated)
• Original Assignee: Bookline Flolmstead LLC
• Inventors: Anderson, Keith R.
• Primary Examiner(s): Nguyen, Chau
• Assistant Examiner(s): WAHBA, ANDREW W
• Application Number:
  US09/753,743
• Publication Number:
  US 20010025301A1
• Time in Patent Office: 1,693 Days
• Field of Search: 370/389, 370/392, 370401-406, 370/412
• US Class Current: 370/389
• CPC Class Codes: H04L 12/2856 Access arrangements, e.g. Internet access asynchronous transfer mode networks H04L12/5601; broadband local area networks H04L12/2801; optical access or distribution networks H04Q11/0067; access to open networks H04L12/5691; digital subscriber line end-user equipment and bit-level processing of data on a PSTN-based network H04M11/00; home network gateways H04L12/2834; wireless access networks H04W
• CPC Class Codes: H04L 12/2874 Processing of data for distribution to the subscribers
• CPC Class Codes: H04L 12/433 with asynchronous transmission, e.g. token ring, register insertion
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/522 Dynamic queue service slot or variable bandwidth allocation
• CPC Class Codes: H04L 47/56 implementing delay-aware scheduling
• CPC Class Codes: H04L 47/6255 queue load conditions, e.g. longest queue first
• CPC Class Codes: H04L 61/00 Network arrangements, protocols or services for addressing or naming
• CPC Class Codes: H04L 61/10 of different types
• CPC Class Codes: H04L 61/103 across network layers, e.g. resolution of network layer into physical layer addresses or address resolution protocol [ARP]
• CPC Class Codes: H04L 67/56 Provisioning of proxy services store-and-forward switching systems in data switching networks H04L12/54
• CPC Class Codes: H04L 67/568 Storing data temporarily at an intermediate stage, e.g. caching

Abstract

An apparatus, data structures, and method are provided for prioritizing data transmissions within a network. As applied to a switching station in a network, the method prioritizes transmissions from the network to determine which packets should be transmitted from the switching station first when multiple packets are routed to the same outgoing port of the switching station. A packet prioritization station is provided, preferably as an add-on to the switching station. The packet prioritization station has a cache in which the destination address of each incoming packet is associated with every origin from which it has received a transmission within a certain time period. The packet prioritization station operates to give priority to transmissions to those destinations that have a higher number of associated origins. Thus, packets that are probably en route to time-critical users or groups of users will be sent before those that are less time-sensitive.

Claims

1. A method for prioritizing data transmissions from a switching station, the method comprising:

maintaining a database containing information from data transmissions through the switching station;

receiving a data transmission of the data transmissions;

selecting a property corresponding to the data transmission, the property reflecting a relative importance of the data transmission, the property obtained from the database and derived from a destination contained in the data transmission, the property including a number of origins stored to the database, the origins having previously sent data transmissions to the destination through the switching station; and

determining a priority for the data transmission in accordance with the property.

2. The method of claim 1, wherein a data transmission having a number of origins greater than a threshold value receives a high priority, and a data transmission having a number of origins not greater than the threshold value receives a low priority.

3. The method of claim 2, wherein the threshold value is four (4) origins.

4. The method of claim 1, further comprising periodically clearing the database to ensure that the database remains current.

5. The method of claim 1, wherein the method is carried out by a packet prioritization station in communication with the switching station.

6. The method of claim 5, wherein the packet prioritization station is further configured to receive an origin and a destination for a data transmission from the switching station.

7. The method of claim 6, wherein the packet prioritization station is further configured to provide the priority to the switching station.

8. The method of claim 7, wherein the switching station communicates with the packet prioritization station through an interrupt controller, the interrupt controller providing an intransitive interrupt.

9. The method of claim 1, wherein determining a priority for the data transmission in accordance with the property comprises assigning a high priority to a data transmission with a high relative importance, and assigning a low priority to a data transmission with a low relative importance.

10. The method of claim 9, further comprising ordering data transmissions of equal priority in cyclical form according to a port through which the data transmission will be transmitted.

11. A computer-readable medium for a system configured to prioritize data transmissions from a switching station, the computer-readable medium storing data structures comprising:

a cache writing module configured to store a property corresponding to a data transmission, the property reflecting a relative importance of the data transmission, the property including a number of origins associated with a destination contained in the data transmission;

a cache reading module configured to receive the property; and

a comparison module configured to determine a priority of the data transmission in accordance with the property.

12. The computer-readable medium of claim 11, wherein the priority is proportional to the number of origins.