Method for prioritizing, selectively discarding, and multiplexing differing traffic type fast packets

• US 5,231,633 A
• Filed: 07/11/1990
• Issued: 07/27/1993
• Est. Priority Date: 07/11/1990
• Status: Expired due to Term

• Current Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Original Assignee: Codex Corporation (Motorola Solutions, Inc.)
• Inventors: Yin, Nanying, Bhargave, Amit, Hluchyj, Michael G.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): TON, DANG T
• Application Number:
  US07/551,712
• Time in Patent Office: 1,112 Days
• Field of Search: 370/94.1, 370/110.1, 370/60, 370/53, 370/56, 370/85.1, 370/108, 370/61, 370/58.1, 370/58.3, 240/825.5, 240/825.52, 240/825.51, 240/825.02, 395/650
• US Class Current: 370/429
• CPC Class Codes: H04J 3/247 ATM or packet multiplexing
• CPC Class Codes: H04L 2012/5632 Bandwidth allocation
• CPC Class Codes: H04L 2012/5647 Cell loss
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5672 Multiplexing, e.g. coding, scrambling
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections
• CPC Class Codes: Y10S 370/902 Packet switching

Abstract

A queueing and dequeueing mechanism for use in an integrated fast packet network, wherein fast packets from differing traffic types are multiplexed with one another through use of a weighted round-robin bandwidth allocation mechanism (517). Fast packets within a particular traffic type are selected for transmission through use of a head of line priority service (514), a packet discard mechanism (516), or both. The weighted round-robin bandwidth allocation mechanism functions, in part, based upon a credit counter for each queue group that represents a particular traffic type.

Claims

1. A method of post-switching multiplexing fast packets for differing traffic types, comprising the steps of:

A) receiving first traffic type fast packets from a plurality of first sources;

B) prioritizing at least some of the first traffic type fast packets pursuant to a first prioritization method, to prioritize first traffic type fast packets for transmission;

C) receiving second traffic type fast packets from a plurality of second sources, which second traffic type is different from the first traffic type;

D) prioritizing at least some of the second traffic type fast packets pursuant to a second prioritization method, which second prioritization method is different from the first prioritization method, to prioritize second traffic type fast packets for transmission;

E) multiplexing and transmitting the first and second traffic type fast packets, wherein the step of multiplexing the first and second traffic type fast packets includes the step of multiplexing the first and second traffic type fast packets pursuant to a weighted round robin bandwidth allocation protocol.

2. The method of claim 1 wherein the first prioritization method comprises a head-of-line prioritization method.

3. The method of claim 2 wherein the second prioritization method includes a packet discarding protocol.

4. The method of claim 3 wherein the packet discarding protocol includes the step of comparing a discard priority for a selected fast packet at the front of a selected fast packet queue with queue depth of at least one other fast packet queue.

5. A method of post-switching multiplexing fast packets for differing traffic types, comprising the steps of:

A) receiving differing traffic type fast packets;

B) prioritizing at least some of the fast packets for transmission as a function, at least in part, of a prioritization method, to provide prioritized fast packets;

C) selecting at least some of the prioritized fast packets for transmission as a function, at least in part, of a bandwidth allocation method, which bandwidth allocation method is different from the prioritization method, to provide multiplexed fast packets; and

D) transmitting the multiplexed fast packets, wherein;

a) the first prioritization method comprises a head-of-line prioritization method; and

b) the bandwidth allocation method comprises a weighted round robin bandwidth allocation mechanism.

6. A method of post-switching multiplexing fast packets for differing traffic types, comprising the steps of:

A) receiving continuous bit-stream oriented fast packets from a plurality of first sources;

B) prioritizing at least some of the continuous bit-stream oriented fast packets pursuant to a first prioritization method, to prioritize the continuous bit-stream oriented fast packets for transmission;

C) receiving framed data fast packets from a plurality of second sources;

D) prioritizing at least some of the framed data fast packets pursuant to the first prioritization method, to prioritize the framed data fast packets for transmission;

E) multiplexing at least some of the prioritized continuous bit-stream oriented fast packets and framed data fast packets as a function, at least in part, of a bandwidth allocation method, to provide multiplexed fast packets.

7. The method of claim 6, wherein the bandwidth allocation method comprises a weighted round robin bandwidth allocation method.

8. A method of post-switching multiplexing fast packets for differing traffic types, comprising the steps of:

A) receiving continuous bit-stream oriented fast packets from a plurality of first sources;

B) prioritizing at least some of the continuous bit-stream oriented fast packets pursuant to a first prioritization method, to prioritize the continuous bit-stream oriented fast packets for transmission;

C) receiving framed data fast packets from a plurality of second sources;

D) prioritizing at least some of the framed data fast packets pursuant to the first prioritization method, to prioritize the framed data fast packets for transmission;

E) multiplexing at least some of the prioritized continuous bit-stream oriented fast packets and framed data fast packets as a function, at least in part, of a bandwidth allocation method, to provide multiplexed fast packets, wherein;

a) the first method comprises a head-of-line prioritization method; and

b) the bandwidth allocation method comprises a weighted round robin bandwidth allocation method.

9. A method of post-switching multiplexing fast packets for differing traffic types, comprising the steps of:

A) receiving continuous bit-stream oriented fast packets from a plurality of first sources;

B) prioritizing at least some of the continuous bit-stream oriented fast packets pursuant to a first prioritization method, to prioritize the continuous bit-stream oriented fast packets for transmission;

C) receiving framed data fast packets from a plurality of second sources;

D) prioritizing at least some of the framed data fast packets pursuant to the first prioritization method, to prioritize the framed data fast packets for transmission;

E) receiving digitized voice fast packets from a plurality of third sources;

F) discarding at least some of the digitized voice packets, from time to time, pursuant to a packet discarding protocol, to provide digitized voice fast packets for transmission;

G) multiplexing at least some of the prioritized continuous bit-stream oriented fast packets and framed data fast packets and digitized voice fast packets, as a function, at least in part, of a bandwidth allocation method, which bandwidth allocation method to provide multiplexed fast packets.

10. The method of claim 9, wherein the first method comprises a head-of-line prioritization method.

11. The method of claim 9, wherein the bandwidth allocation method comprises a weighted round robin bandwidth allocation method.

12. The method of claim 9, wherein:

A) the first method comprises a head-of-line prioritization method; and

B) the bandwidth allocation method comprises a weighted round robin bandwidth allocation method.

13. The method of claim 9 wherein at least some of the digitized voice fast packets include discard priority information, and wherein the packet discarding protocol utilizes the discard priority information to identify packets to discard.

14. A method of post-switching multiplexing fast packets for differing traffic types, comprising the steps of:

A) receiving continuous bit-stream oriented fast packets from a plurality of first sources;

B) storing at least some of the continuous bit-stream oriented fast packets in at least a first queue and a second queue;

C) prioritizing at least some of the continuous bit-stream oriented fast packets as stored in the queues pursuant to a first prioritization method, to prioritize the continuous bit-stream oriented fast packets for transmission;

D) receiving framed data fast packets from a plurality of second sources;

E) storing at least some of the frame data fast packets in at least a third queue and a fourth queue;

F) prioritizing at least some of the framed data fast packets as stored in the third and fourth queues pursuant to the second prioritization method, to prioritize the framed data fast packets for transmission;

G) receiving digitized voice fast packets from a plurality of third sources;

H) discarding at least some of the digitized voice packets, from time to time, pursuant to a packet discarding protocol, to provide digitized voice fast packets for transmission;

I) multiplexing at least some of the prioritized continuous bit-stream oriented fast packets and framed data fast packets and digitized voice fast packets, as a function, at least in part, of a bandwidth allocation method, which bandwidth allocation method to provide multiplexed fast packets.

15. The method of claim 14, wherein the continuous bit-stream oriented fast packets are stored in the first queue and the second queue as a function in part of the packetization time of the CBO sources.

16. The method of claim 15, wherein the continuous bit-stream oriented fast packets from sources having a relatively small packetization time are stored in the first queue, and the fast packets having a relatively large packetization time are stored in the second queue.

17. The method of claim 16, wherein the step of storing the continuous bit-stream packets includes storing fast packets from sources with a relatively medium packetization times in additional queues that are served via HOLP with the first and second queues.

18. The method of claim 14, wherein the framed data fast packets are stored in the third queue and the fourth queue as a function in part of the burst size of the framed data sources.

19. The method of claim 18, wherein the framed data fast packets from sources having a relatively small burst size are stored in the third queue, and the fast packets having a relatively large burst size are stored in the fourth queue.

20. The method of claim 19, wherein the step of storing the framed data packets includes storing fast packets from sources with relatively medium burst sizes in additional queues that are served via HOLP with the third and fourth queues.

21. A method of post-switching multiplexing fast packets for differing traffic types, wherein fast packets for each traffic type are queued in a plurality of queues, such that queues that contain fast packets for a particular type are grouped together in a discrete group, comprising the steps of:

A) selecting a first group of queues;

B) determining whether a credit count associated with the first group of queues has any remaining credit contained therein;

C) when the credit count has credit at least a predetermined amount of remaining therein, determining whether a queue contained within the group has a fast packet queued therein;

D) when the queue has a fast packet queued therein, removing the fast packet from the queue;

E) when the fast packet queued in the queue is removed by transmission of the fast packet, altering the credit count.

22. The method of claim 21, wherein the step of altering the credit count includes the step of altering the credit count by an amount related to at least the length of the fast packet.

23. The method of claim 22, wherein step C further includes the step of:

C1) when the credit count has less than a predetermined amount of credit remaining therein, repeating from step A with a second group of queues.

24. The method of claim 22, and further including the step of:

F) repeating from step A.

25. The method of claim 24, wherein step C further includes the step of:

C1) when the credit count has less than a predetermined amount of credit remaining therein, repeating from step A with a second group of queues.

26. The method of claim 25, and further including the step of:

G) determining whether any of the groups of queues have any credit remaining in their respective credit counts;

H) when no credit remains with any of the groups of queues, establishing at least a predetermined credit count for at least some of the groups of queues.

27. The method of claim 25, wherein a predetermined credit count is established for each of the groups of queues.

28. The method of claim 27, wherein the predetermined credit count is different for at least some of the groups of queues.

29. The method of claim 22, wherein the fast packets are comprised of bytes and the step of altering the credit count by an amount related to at least the length of the fast packet includes reducing the credit count by an amount proportional to the number of bytes in the removed fast packet.

30. A method of post-switching multiplexing fast packets for differing traffic types, comprising the steps of:

A) receiving continuous bit-stream oriented fast packets from a plurality of first sources;

B) prioritizing at least some of the continuous bit-stream oriented fast packets pursuant to a first prioritization method, to prioritize the continuous bit-stream oriented fast packets for transmission;

C) receiving framed data fast packets from a plurality of second sources;

D) prioritizing at least some of the framed data fast packets pursuant to the first prioritization method, to prioritize the framed data fast packets for transmission;

E) multiplexing at least some of the prioritized continuous bit-stream oriented fast packets and framed data fast packets as a function, at least in part, of a bandwidth allocation method, to provide multiplexed fast packets,

wherein the bandwidth allocation method comprises a weighted round robin bandwidth allocation method.

31. The method of claim 30, wherein the first method comprises a head-of-line prioritization method.