Prioritizing data transmissions using the number of associated origin addresses

• US 7,835,350 B2
• Filed: 07/13/2005
• Issued: 11/16/2010
• Est. Priority Date: 02/09/2000
• Status: Expired due to Fees

• Current Assignee: CommWorks Solutions, LLC (IP Investments Group LLC)
• Original Assignee: Brookline Flolmstead LLC (Intellectual Ventures LLC)
• Inventors: Anderson, Keith R.
• Primary Examiner(s): Sheikh; Ayaz R
• Assistant Examiner(s): Weidner; Timothy J
• Application Number:
  US11/180,764
• Publication Number:
  US 20050249116A1
• Time in Patent Office: 1,952 Days
• Field of Search: None
• 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 switching station, comprising:

a cache configured to store information indicating, for a given destination of a data transmission received by the switching station, a quantity of different origins that are associated with the given destination;

a processor coupled to the cache, wherein the processor is configured to receive first and second data transmissions, and wherein the processor is configured to assign the second data transmission a higher transmission priority relative to the first data transmission based, at least in part, on whether a threshold quantity of different origins are associated with respective destinations of the first and second data transmissions, wherein the threshold quantity is greater than or equal to two; and

wherein the switching station is configured to transmit a packet in the second data transmission before transmitting a packet in the first data transmission in response to the second data transmission having the assigned higher transmission priority.

2. The switching station of claim 1, wherein the threshold quantity is four.

3. The switching station of claim 1, wherein the given destination is indicated by a MAC address corresponding to the given destination.

4. The switching station of claim 1, wherein the switching station is configured to periodically clear information from the cache.

5. The switching station of claim 1, wherein the switching station includes a plurality of buffers, individual ones of which are associated with a respective port of the switching station, and wherein the processor is configured to cyclically analyze packets stored in the plurality of buffers to determine relative transmission priorities of the stored packets.

6. The switching station of claim 1, wherein the processor is configured to receive the second data transmission subsequent to the first data transmission.

7. The switching station of claim 1, wherein the processor is configured to receive at least respective portions of the first and second data transmissions within an overlapping time period.

8. A method, comprising:

a switching device sampling at least first and second ones of a plurality of received data transmissions, wherein each received data transmission indicates an origin and a destination of the transmission;

the switching device storing information associating the destinations of the sampled data transmissions with the origins of the sampled data transmissions; and

the switching device determining transmission priorities for at least the first and second ones of the plurality of data transmissions based, at least in part, on the stored information, wherein determining the transmission priorities comprises;

assigning a highest transmission priority to data transmissions that include a destination associated with the greatest quantity of different origins as indicated by the stored information; and

iteratively assigning a next highest transmission priority to data transmissions that include a destination associated with the next greatest quantity of different origins as indicated by the stored information; and

the switching device transmitting a portion of data in the second data transmission before transmitting a portion of data in the first data transmission in response to the second data transmission having a higher assigned transmission priority than the first data transmission.

9. The method of claim 8, wherein the data transmissions comprise data packets.

10. The method of claim 8, wherein at least one of the plurality of received data transmissions is not assigned a transmission priority based, at least in part, on the at least one received data transmission including a destination that is not associated with at least a threshold quantity of different origins as indicated by the stored information.

11. The method of claim 8, wherein the at least a portion of the first data transmission is received before the at least a portion of the second data transmission.

12. A switching station, comprising:

a cache configured to store a set of information indicating that a destination of a first data transmission received by the switching station has been the target destination of two or more previous data transmissions, wherein the two or more previous data transmissions were directed from two or more different origins; and

first means for using the stored set of information to determine a priority of the first data transmission relative to other data transmissions received by the switching station;

wherein the switching station is configured to transmit a packet in the first data transmission before transmitting a packet in one of the other data transmissions in response to the determined priority of the first data transmission.

13. The switching station of claim 12, wherein the first means includes a processor and a memory storing program instructions executable by the processor to use at least some of the set of information stored in the cache to assign descending transmission priorities to data transmissions indicated by the cache as having successively fewer quantities of different origins associated with respective destinations of the data transmissions.

14. The switching station of claim 12, wherein the switching station is configured to receive, within an overlapping time period, data packets in at least one of the two or more previous data transmissions and data packets in the first data transmission.

15. An article of manufacture including a non-transitory computer-readable medium having instructions stored thereon, wherein execution of the instructions by a switching device causes the switching device to perform operations comprising:

storing information indicating, for individual ones of a plurality of different destination addresses previously received by the switching device, one or more associated addresses corresponding to different origins, wherein the stored information includes a first set of information indicating that a first destination address is associated with a first quantity of addresses corresponding to different origins, the first quantity being greater than or equal to two, and wherein the stored information includes a second set of information indicating that a second destination address is associated with a second quantity of addresses corresponding to different origins, wherein the second quantity is less than the first quantity;

receiving first and second sets of one or more data packets, wherein the first set of data packets includes information indicating that it is destined for the first destination address, and wherein the second set of packets includes information indicating that it is destined for the second destination address;

assigning the received first set of data packets a higher transmission priority than the received second set of data packets based, at least in part, upon the first and second sets of information; and

transmitting one or more packets in the first set of data packets before transmitting one or more packets in the second set of data packets in response to the first set of data packets having been assigned the higher transmission priority.

16. The article of manufacture of claim 15, wherein the destination addresses are MAC addresses.

17. The article of manufacture of claim 15, wherein the operations further include periodically clearing the stored information indicating associations between destination addresses and addresses corresponding to different origins.

18. The article of manufacture of claim 15, wherein said assigning the first set of data packets a higher transmission priority than the second set of data packets is based, at least in part, upon the first quantity being greater than the second quantity.

19. The article of manufacture of claim 15, wherein said assigning the first set of data packets a higher transmission priority than the second set of data packets is based, at least in part, upon a first comparison between the first quantity of addresses corresponding to different origins and a threshold quantity of addresses corresponding to different origins, wherein the threshold quantity is greater than or equal to two.

20. The article of manufacture of claim 19, wherein said assigning the first set of data packets a higher transmission priority than the second set of data packets is further based, at least in part, upon a second comparison between the second quantity of addresses corresponding to different origins and the threshold quantity of addresses corresponding to different origins.

21. The article of manufacture of claim 20, wherein said assigning the first set of data packets a higher transmission priority than the second set of data packets is based, at least in part, on the first quantity of addresses corresponding to different origins being greater than the threshold quantity of addresses corresponding to different origins and on the second quantity of addresses corresponding to different origins being less than or equal to the threshold quantity of addresses corresponding to different origins.

22. The article of manufacture of claim 15, wherein the one or more packets in the second set of data packets are received before the one or more packets in the first set of data packets.

23. A method, comprising:

a network device storing information indicating, for each of two or more of a plurality of different destination addresses previously received by the network device, one or more different origin addresses from which data transmissions to that destination address have originated, and wherein the stored information also indicates that the network device has previously received, from at least a first quantity of different origin addresses, data transmissions addressed to a first of the plurality of destination addresses;

the network device receiving first and second sets of one or more data packets, wherein the first set of data packets includes information indicating that it is destined for the first destination address; and

in response to the stored information indicating that the first quantity of different origin addresses is greater than a threshold quantity of different origin addresses, assigning the first set of data packets a higher transmission priority relative to at least the second set of data packets, wherein the threshold quantity is greater than or equal to two; and

the network device transmitting one or more packets in the first set of data packets before transmitting one or more packets in the second set of data packets in response to the first set of data packets having been assigned the higher transmission priority relative to at least the second set.

24. The method of claim 23, further comprising transmitting sets of data packets from ports of the network device in a round robin order in the absence of a determination by the network device that a stored set of data packets has a destination address associated with more than the threshold quantity of different origin addresses.

25. The method of claim 23, further comprising transmitting the first set of data packets from a first port of the network device, wherein the at least a second set of data packets is destined to be transmitted from a second port of the network device, and wherein said assigning includes prioritizing the first port relative to the second port.

26. The method of claim 23, wherein the plurality of different destination addresses and the one or more different origin addresses are specified by MAC addresses.