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

• US 20010025301A1
• Filed: 12/27/2000
• Published: 09/27/2001
• Est. Priority Date: 02/09/2000
• Status: Active Grant

• Current Assignee: CommWorks Solutions, LLC (IP Investments Group LLC), Affymetrix, Inc. (Thermo Fisher Scientific Incorporated)
• Original Assignee: Brookline Flolmstead LLC (Intellectual Ventures LLC)
• Inventors: Anderson, Keith R.
• Granted Patent: US 6,931,003 B2
• Time in Patent Office: Days
• US Class Current: 709/207
• 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:

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; and

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

2. The method of

claim 1

, further comprising maintaining a database containing information from data transmissions through the switching station.

3. The method of

claim 2

, wherein the property is further obtained from the database.

4. The method of

claim 3

, wherein the property is further derived from a destination contained in the data transmission.

5. The method of

claim 4

, wherein the property further comprises a number of origins stored in the database, the origins having previously sent data transmissions to the destination through the switching station.

6. The method of

claim 5

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

7. The method of

claim 6

, wherein the threshold value is four (4) origins.

8. The method of

claim 2

, further comprising periodically clearing the database to ensure that the database remains current.

9. The method of

claim 1

, further being carried out by a packet prioritization station in communication with the switching station.

10. The method of

claim 9

, wherein the packet prioritization station is further configured to receive an origin and a destination for a data transmission from the switching station.

11. The method of

claim 10

, wherein the packet prioritization station is further configured to provide the priority to the switching station.

12. The method of

claim 11

, wherein the switching station communicates with the packet prioritization station through an interrupt controller, the interrupt controller providing an intransitive interrupt.

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

14. The method of

claim 13

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

15. A computer-readable medium containing instructions that cause a prioritization system configured to prioritize data transmissions from a switching station to perform a method comprising:

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; and

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

16. The computer-readable medium of

claim 15

, wherein the method further comprises maintaining a database containing a destination and one or more origins associated with the destination, the origins having previously sent data transmissions to the destination through the switching station.

17. The computer-readable medium of

claim 16

, wherein the priority is proportional to the number of origins associated with the destination of the data transmission.

18. A prioritization system configured to prioritize data transmissions from a switching station, the prioritization system 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;

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.

19. The prioritization system of

claim 18

, further comprising a cache containing a database, the database containing the property.

20. The prioritization system of

claim 19

, wherein the property is obtained from previous data transmissions through the switching station.

21. The prioritization system of

claim 20

, wherein the property corresponds to a destination of the data transmission.

22. The prioritization system of

claim 21

, wherein the property comprises a number of origins stored in the database, the origins having previously sent data transmissions to the destination through the switching station.

23. The prioritization system of

claim 22

, wherein the comparison module provides a high priority for a data transmission having more than a threshold number of origins, and a low priority for a data transmission having no more than a threshold number of origins.

24. The prioritization system of

claim 23

, wherein the threshold number of origins is four (4).

25. The prioritization system of

claim 24

, wherein the cache writing module further periodically deletes all destinations and origins from the database.

26. The prioritization system of

claim 18

, further comprising a marking module configured to designate a current port of a plurality of ports of a switching station.

27. The prioritization system of

claim 26

, further comprising an incrementing module configured to cyclically change the current port to permit alternating data transmissions of equal priority.

28. 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;

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.

29. The computer-readable medium of

claim 28

, wherein the property comprises a number of origins associated with a destination contained in the data transmission.

30. The computer-readable medium of

claim 29

, wherein the priority is proportional to the number of origins.

31. A switching system configured to route data transmissions between a plurality of locations, the switching system comprising:

a switching station configured to receive and send the data transmissions;

a packet prioritization station configured to determine a transmission order of the data transmissions; and

the transmission order reflecting a relative importance of the data transmissions.

32. The switching system of

claim 31

, wherein the switching station comprises:

a processor;

a program memory configured to provide instructions to the processor;

a buffer configured to store data transmissions;

a cache configured to store information from data transmissions;

a bus operably connected to provide communication between the processor, the buffer, and the cache; and

a plurality of ports connected to the buffer, the ports being in communication with a plurality of destinations.

33. The switching system of

claim 31

, further comprising an interrupt controller connected to the bus of the switching station and disposed to control communications between the switching station and the packet prioritization station.

34. The switching station of

claim 32

, wherein the packet prioritization station comprises a bus connected to the interrupt controller.

35. The switching station of

claim 31

, wherein the packet prioritization station comprises:

a processor;

a program memory configured to provide instructions to the processor;

a cache configured to store origins and destinations contained in data transmissions; and

a bus operably connected to provide communication between the processor, the program memory, and the cache.