Method and apparatus for scheduling message processing

The present invention provides a method and apparatus for scheduling message processing. The present invention provides a scheduling mechanism, or scheduler (602), that receives messages (608) and stores the messages (610 or 614) in a first queue (604) or a second queue (606) based, in part, on various criteria associated with the messages. The criteria include message attributes, such as message priority, virtual private network (“VPN”) classification and destination software function. The first queue (604) can be a first-in-first-out queue, and the second queue (606) can be a multi-dimensional queue. The scheduler (602) then schedules the queued messages (612 or 616) for processing based, in part, on various operating criteria (618), such as historical operating data, current operating data and anti-starvation criteria. In addition, the scheduler (602) can be programmed to function in a variety of operating modes.

FIELD OF THE INVENTION

The present invention relates generally to the field of communications and, more particularly, to a method and apparatus for scheduling messages for processing.

BACKGROUND OF THE INVENTION

The increasing demand for data communications has fostered the development of techniques that provide more cost-effective and efficient means of using communication networks to handle more information and new types of information. One such technique is to segment the information, which may be a voice or data communication, into packets. A packet is typically a group of binary digits, including at least data and control information. Integrated packet networks (typically fast packet networks) are generally used to carry at least two (2) classes of traffic, which may include, for example, continuous bit-rate (“CBR”), speech (“Packet Voice”), data (“Framed Data”), image, and so forth. Packet networks source, sink and/or forward protocol packets.

Congestion and Quality of Service (“QoS”) problems inside these networks have not been solved satisfactorily and remain as outstanding issues to be resolved. Although, message scheduling helps alleviate these problems, the efficient scheduling of work with thousands of entities (instances) is not a simple matter. At present, most message scheduling is based on the simplest technique for queuing packets for transmission on an internodal trunk of a fast-packet network: a first-in-first-out (“FIFO”) queue. However, FIFO queuing techniques do not address QoS parameters. This technique can also allow overload periods for digitized speech packets and for Framed Data packets, which results in a greater share of bandwidth being provided to one at the expense of the other; an undesirable result.

Another technique, head-of-line-priority (“HOLP”), may give data priority over speech, but does not solve the problem of data and speech queues affecting the QoS of each other and of CBR data fast packets under high traffic conditions. In HOLP, where speech fast packets are given a high priority, speech fast packets may affect the QoS of lower priority queues. Likewise, queuing schemes designed only for data do not solve the problems of integrating other traffic types, such as speech and CBR data.

Most current techniques for scheduling messages depend upon the storage of messages either in FIFO order or priority order. Current messaging queues are not flexible because they do not take into account any current or historical operating conditions. In addition, current functionality is often dependent on a single central processing unit (“CPU”) and memory.

Accordingly, there is a need for a method and apparatus for scheduling messages based, in part, on current and historical operating conditions. There is also a need for a method and apparatus that reduces congestion while maintaining QoS for all message types.

SUMMARY OF THE INVENTION

The present invention provides a method and apparatus for scheduling messages based, in part, on current and historical operating conditions. The present invention also provides a method and apparatus that reduces congestion while maintaining QoS for all message types. The present invention is adaptable to accommodate new message types, multimedia applications and multi-service applications. It is flexible, with the ability to cater to a wide range of configurations and environments and improves the QoS of VoIP calls. Moreover, the present invention self-adjusts to traffic/congestion levels through its multiple operating modes. Furthermore, the mode switching points can be adjusted on the fly.

The representative embodiments described herein provide a scheduling mechanism, or scheduler, that receives messages and stores the messages in a first queue and a second queue based, in part, on various criteria associated with the messages. The criteria include message attributes, such as message priority, virtual private network (“VPN”) classification and destination software function. The first queue can be a first-in-first-out queue, and the second queue can be a multi-dimensional queue. The scheduler then schedules the queued messages for processing based, in part, on various operating criteria, such as historical operating data, current operating data and anti-starvation criteria. In addition, the scheduler can be programmed to function in a variety of operating modes.

In a first embodiment, the present invention provides an apparatus for scheduling messages that includes two (2) queues and a scheduler communicably coupled to the queues. The scheduler has at least two (2) operating modes. The first operating mode includes receiving messages, storing each message in the first queue based on a first-in-first-out order, and scheduling each queued message from the first queue based on the first-in-first-out order. The second operating mode includes receiving messages, storing each message in the second queue based one or more message attributes, and scheduling each queued message from the second queue based on operating criteria. The scheduler operates in the first operating mode until the number of messages in the first queue exceeds a predetermined value and the second queue is emptied; then it switches modes. The first operating mode may also be triggered by low message traffic conditions. Likewise, the second operating mode may be triggered by high message traffic conditions. Additional queues and operating mode can be added to extend the flexibility of the present invention.

In a second embodiment of the present invention, the scheduler includes a third operating mode. The scheduler switches to the third operating mode when the number of messages in the first queue equals or exceeds a predetermined value. At this point, the scheduler ceases storing messages in the first queue and begins storing messages in the second queue. However, the scheduler continues pulling messages for processing from the first queue until the first queue is empty. Once the first queue is emptied, the scheduler returns to operating in the second operating mode.

Another embodiment of the present invention includes a fourth operating mode in which the scheduler stores messages in the first queue and pulls messages from the second queue. The scheduler switches to the fourth operating mode when the number of messages in the second queue is equal to or less than a predetermined value. The fourth operating mode is maintained until the second queue is emptied. Then the scheduler returns to the first operating mode.

The present invention also provides a method for scheduling one or more messages in which the one or more messages are received, and a first queue is selected for input and output during a first operating mode and a second queue is selected for input and output during a second operating mode. Each message is stored in the first queue based on a first-in-first-out order whenever the first queue is selected for input or in the second queue based on one or more message attributes whenever the second queue is selected for input. Each queued message is scheduled from the first queue based on the first-in-first-out order whenever the first queue is selected for output or from the second queue based one or more operating criteria whenever the second queue is selected for output.

In addition, the present invention provides a communications switch that includes one or more ingress cards, one or more signal processing cards, one or more control cards, one or more egress cards, a switch fabric, a TDM bus, a scheduler, and a first and second queue. Each signal processing card contains an array of digital signal processors and each control card contains one or more processors. The switch fabric communicably couples the ingress cards, the signal processing cards, the control cards and the egress cards together. The TDM bus communicably couple the ingress cards, the signal processing cards, the control cards and the egress cards together. The scheduler communicably is coupled to each processor and has at least a first and second operating mode. The first and second queues are communicably coupled to the scheduler. The first operating mode includes the steps of receiving the one or more messages, storing each message in the first queue based on a first-in-first-out order, and scheduling each queued message from the first queue based on the first-in-first-out order. The second operating mode includes the steps of receiving the one or more messages, storing each message in the second queue based one or more message attributes, and scheduling each queued message from the second queue based one or more operating criteria.

DETAILED DESCRIPTION OF THE INVENTION

While the making and using of various embodiments of the present invention are discussed in detail below, it should be appreciated that the present invention provides many applicable inventive concepts that can be embodied in a wide variety of specific contexts. The specific embodiments discussed herein are merely illustrative of specific ways to make and use the invention and do not delimit the scope of the invention. The discussion herein relates to communications systems, and more particularly, to processing messages within a communications switch. It will be understood that, although the description herein refers to a communications environment, the concepts of the present invention are applicable to other environments, such as general data processing.

The present invention is adaptable to accommodate new message types, multimedia applications and multi-service applications. It is flexible, with the ability to cater to a wide range of configurations and environments and improves the QoS of VoIP calls. Moreover, the present invention self-adjusts to traffic/congestion levels through its multiple operating modes. Furthermore, the mode switching points can be adjusted on the fly.

The representative embodiments described herein provide a scheduling mechanism, or scheduler, that receives the messages and stores the messages in a first queue and a second queue based, in part, on various criteria associated with the messages. The criteria include message attributes, such as message priority, virtual private network (“VPN”) classification and destination software function. The first queue can be a first-in-first-out queue, and the second queue can be a multi-dimensional queue. The scheduler then schedules the queued messages for processing based, in part, on various operating criteria, such as historical operating data, current operating data and anti-starvation criteria. In addition, the scheduler can be programmed to function in a variety of operating modes.

Now briefly referring toFIGS. 1–3, a representative network (FIG. 1) and various message scheduling systems (FIGS. 2 and 3) will be described in accordance with the prior art.FIG. 1depicts a representative integrated network100in which phones102and faxes104are communicably coupled to a public switched telephone network (“PSTN”)106. A switch108is communicably coupled to the PSTN106and an Internet Protocol (“IP”) network110to convert time division multiplexing (“TDM”) based communications112to IP-based communications114. The switch108creates IP packets containing the necessary destination information so that the packets114can be properly routed to their destinations, which may include computers116or other devices communicably coupled to the IP network110. A network controller118is communicably coupled to the PSTN106and the switch108, and provides control signals to the switch108for proper processing of the TDM based communications112. The network controller118may also be communicably connected to the IP network110. Network controller118can function as a Media Gateway Control (“MGC”). The MGC protocol is one of a few proposed control and signal standards to compete with the older H.323 standard for the conversion of audio signals carried on telephone circuits, such as PSTN106to data packets carried over the Internet or other packet networks, such as IP network110. As will be appreciated by those skilled in the art, this example is not limited to the conversion of TDM based communications to IP-based communications; instead, the present invention may be applied to any conversion of a multiplexed communication to a packet-based communication.

IP specifies the format of packets, also called datagrams, and the addressing scheme. Most networks combine IP with a higher-level protocol called Transport Control Protocol (“TCP”), which establishes a virtual connection between a destination and a source. IP allows a packaged to be addressed and dropped in a system, but there is no direct link between the sender and the recipient. TCP/IP, on the other hand, establishes a connection between two hosts so that they can send messages back and forth for a period of time. IP network110receives and sends messages through switch108, ultimately to phone102and/or fax104. PCs116receive and send messages through IP network110in a packet-compatible format. Voice over IP (“VoIP”) is the ability to make telephone calls and send faxes over IP-based data networks, such as IP network110. An integrated voice/data network100allows more standardization and reduces total equipment needs. VoIP can support multimedia and multi-service applications.

FIGS. 2 and 3are schematic diagrams illustrating two message scheduling systems200and300in accordance with the prior art. InFIG. 2, messages202are received and stored in first-in-first-out (“FIFO”) queue204. Messages202are then sent to processor206in the order in which they were received. No processing prioritization other than arrival time is applied in queue204is applied. InFIG. 3, messages302enter data type sorter304where messages302are separated by data type. A FIFO queue306a,306b, . . .306nexists for each individual data type. Data type sorter304sends messages302to FIFO queues306a,306b, . . .306nbased on matching data types. Scheduler308then pulls messages302from FIFO queues306a,306, . . .306nand sends messages302to processor310. The primary prioritization is again based on arrival time in queues306a,306b, . . .306n. Scheduler308only coordinates the pulling of messages302for processing.

Now referring to the present invention and toFIG. 4, a packet network switch400will now be described. The packet network switch400can be used to process VoIP, voice over Frame Relay (“VoFR”) and other types of calls. Moreover, the packet network switch400is similar to an asynchronous transfer mode (“ATM”) switch. ATM is a connection-oriented technology used in both local area network (“LAN”) and wide area network (“WAN”) environments. It is a fast-packet switching technology that allows free allocation of capacity to each channel. Packet network switch400includes one or more ingress cards402aand402b, one or more signal processing cards404, one or more control cards406, one or more egress cards408aand408b, a switch fabric410and a TDM bus412. Each signal processing card404contains an array of digital signal processors (“DSP”) (not shown) and each control card406contains one or more processors (not shown). The switch fabric410communicably couples the ingress cards402, the signal processing cards404, the control cards406and the egress cards408together. The TDM bus412also communicably couples the ingress cards402, the signal processing cards404, the control cards406and the egress cards408together. Preferably cards402,404,406and408can be inserted in any order within packet network switch400. Moreover, the packet network switch400should include sufficient numbers of redundant cards to serve as backup cards in the event a card402,404,406and408fails.

The main function of a packet network switch400is to relay user data cells from input ports to the appropriate output ports. When a call or communication is to be handled by the packet network switch400, a network controller118(FIG. 1) provides the control card408with the necessary call setup information. Control card408uses this call setup information to assign a port in ingress cards402aor402bto receive the call from the PSTN106(FIG. 1), a DSP within processing card404to process the call, and a port in egress cards408aor408bto send the call to IP network110(FIG. 1). The TDM-based communications or messages112enter through ingress cards402aor402band are routed to the appropriate processing card404through TDM Bus412. The DSPs in processing card404convert messages between analog and digital information formats, and provide digital compression and switching functions. In one embodiment, each processing card404is capable of processing 1024 simultaneous sessions. The processing card404then sends the messages from the DSP to cell switch fabric410, which is primarily responsible for the routing and transferring of messages or data cells, the basic transmission unit, between switch elements. The switch fabric410may also provide cell buffering, traffic concentration and multiplexing, redundancy for fault tolerance, multicasting or broadcasting, and cell scheduling based on delay priorities and congestion monitoring. Switch fabric410ultimately routes the messages to egress cards408aor408b. In one embodiment, each egress card408is capable of handling at least 8000 calls. Egress cards408aand408btypically send the messages to a gigabit Ethernet (not shown). As its name indicates, the gigabit Ethernet supports data rates of one (1) gigabit (1,000 megabits) per second.

Turning now toFIG. 5, a schematic diagram illustrating a packet operating system500with redundant control cards502aand502bis shown. Control cards502aand502bare housed within a single chassis, such as switch400(FIG. 4). Messages504enter packet operating system500through interface506on control card502a. Messages504travel from interface506onto protocol stack508and then to peripheral component interconnect (“PCI”) bus510. PCI bus510sends messages504to either input/output (“I/O”) cards512or DSP cards514. Control card502bmirrors either a portion or all of the data of control card502a. Each control card502aand502bof packet operating system500has its own memory and thus avoids the typical problems associated with shared memory, such as recursive calls and have synchronization and corruption problems.

FIG. 6is a schematic diagram illustrating a message scheduling system600in accordance with the present invention. The scheduling system600of the present invention includes a scheduler602communicably coupled to a first queue604and a second queue606.

The first queue604may be a first-in-first-out (“FIFO”) queue. As a result, the scheduler602stores messages in the first queue604(line610) in the order they are received. Similarly, the scheduler602pulls or schedules queued messages from the first queue604(line612) in the order they were stored in the first queue604. The second queue606may be a multidimensional queue and may be described as a “set” of queues wherein the first square along the X-axis and Y-axis, such as square606A, represents the head of a queue. Note that the second queue606is not limited to a three-dimensional queue as depicted inFIG. 6. Each queue within the second queue606is designated to receive messages based on one or more of the attributes of the message. The one or more message attributes may include a message priority, a virtual private network (“VPN”) classification, a destination software function, other attributes that distinguish one message from another, or combinations thereof. Message priority can be based on QoS parameters or the type of message, such as data, fax, image, multimedia, voice, etc. VPN classification can be individual VPNs or groups of VPNs. For example, one possible configuration of the second queue606could be based on VPN classification in the X-direction, message priority in the Y-direction, and FIFO in the Z-direction.

The scheduler602stores messages608in the second queue606using a scheduling algorithm that is data driven based on one or more attributes of the messages608and may favor one attribute over another attribute. For example, the scheduling algorithm may favor higher priority messages. However, the scheduling algorithm will still balance the VPN. Additionally, it is also efficient to process messages608based on the processing entity (function); the same type of function will require the same type of processing. A semaphore or counter can drive the tasking.

The scheduler602pulls or schedules queued messages from the second queue606based on one or more operating criteria618, such as historical operating data, current operating data, one or more anti-starvation criteria, one or more of the message attributes as described above, or combinations thereof. For example, processor620may have spent a large amount of processing on messages602with a high priority. Therefore, the scheduling algorithm may drive scheduler602to begin selecting messages (line616) from the second queue606that have lower priorities but have a common VPN or processing entity (function). Once the scheduler602pulls or schedules a queued message, whether from the first queue604or the second queue606, the scheduler602sends the message to the processor620.

Alternatively, there can be multiple dispatchers with a preemption table such as:

DST 1LocalDispQueue #1DST 2RemoteNode YDST 3LocalDispQueue #2
The destination entity is looked up in the preemption table or message routing table. If the destination entity is remote, such as DST 2, the message is passed to the messaging system for transport to the appropriate node, such as Node Y, and the local dispatchers are not involved. If, however, the destination was local, such as DST 1 or DST 3, or if the messaging system delivers a received message for an entity which is local, then the message routing table will indicate which local dispatcher's queues should handle the message. The system could be designed so that, for example, messages placed in the queue for DST3, DispQueue #2, would take priority over messages placed in the queue for DST 1, DispQueue #1. As a result, processing on messages done by a lower priority dispatcher will immediately be preempted until the highest priority dispatcher has no messages left to process, at which time processing will resume in the next higher priority dispatcher that has messages left to process.

The scheduler602has at least two operating modes. The first operating mode includes receiving messages608, storing each message in the first queue604based on a first-in-first-out order (indicated by arrow610), and pulling or scheduling each queued message from the first queue604based on the first-in-first-out order (indicated by arrow612). The first operating mode is configured to quickly process messages608during low message traffic conditions. The second operating mode includes receiving messages608, storing each message in the second queue606based one or more message attributes (indicated by arrow614), and pulling or scheduling each queued message from the second queue606based on one or more operating criteria (indicated by arrow616). The second operating mode is configured to efficiently process messages608during high message traffic conditions to reduce congestion while maintaining QoS for all message types.

The scheduler602operates in the first operating mode during low message traffic conditions, which may be determined in the rate at that messages608are being received and processed or more simply by whether or not the number of messages in the first queue604exceeds a first predetermined value; then it switches modes. The first predetermined value may be a fixed number of messages or a variable number of messages based on the rate that messages608are being received and being processed, or based on other operating parameters. As will be appreciated by those skilled in the art, the present invention can be configured to operate with more than two queues and in numerous other operating modes to accommodate specific processing goals, applications or traffic conditions.

For example, the scheduler602of the present invention may include a third and fourth operating mode to serve as transitional operating modes when the scheduler602switches from the first operating mode to the second operating mode, and from the second operating mode to the first operating mode. The scheduler602may switch to the third operating mode when the number of messages in the first queue604equals or exceeds a first predetermined value or some other trigger point. At this point, the scheduler602ceases storing messages in the first queue604(line610) and begins storing messages in the second queue606(line614) based on one or more attributes of each message. However, the scheduler602continues pulling or scheduling queued messages for processing from the first queue604(line612) until the first queue604is empty. Once the first queue604is emptied, the scheduler602operates in the second operating mode and pulls or schedules queued messages for processing from the second queue606(line616) based on one or more operating criteria. During the fourth operating mode, the scheduler602stores messages in the first queue604and pulls or schedules queued messages from the second queue606based on one or more operating criteria. The scheduler602switches to the fourth operating mode when the number of messages in the second queue606is equal to or less than a second predetermined value or some other trigger point is reached. The second predetermined value may be a fixed number of messages or a variable number of messages based on the rate that messages608are being received and being processed, or based on other operating parameters. The fourth operating mode is maintained until the second queue606is emptied. Then the scheduler602returns to the first operating mode and pulls or schedules queued messages for processing from the first queue604(line612). The scheduler602operating modes can be summarized as follows:

Now referring toFIG. 7, a flowchart illustrating a method for storing messages into queues700in accordance with one embodiment of the present invention is shown and will also be described in reference toFIG. 6. The method700is based on a low message traffic mode (first operating mode), a high message traffic mode (second operating mode) and two transition modes (third and fourth operating modes). The method700begins in block702where the scheduler602is initialized with the desired operating parameters and starts off set to the first operating mode. The scheduler602receives the next message608in block704. If the scheduler602is operating in the first operating mode, as determined in decision block706, and under low message traffic conditions, as determined in decision block708, the scheduler602stores the message608in the first queue604in block710, which is also indicated by line610. The scheduler602then returns to block704to receive the next message608. If, however, the scheduler602is operating in the first operating mode, as determined in decision block706, and not under low message traffic conditions, as determined in decision block708, the scheduler602is set to the third operating mode in block712and determines where to store the message608in the second queue606based on one or more attributes of the message608in block714. The scheduler602then stores the message608in the second queue606in block716, which is also indicated by line614. The scheduler602then returns to block704to receive the next message608.

If, however, the scheduler602is not operating in the first operating mode, as determined in decision block706, and is operating in the third operating mode, as determined in decision block718, the scheduler602determines where to store the message608in the second queue606based on one or more attributes of the message608in block714. The scheduler602then stores the message608in the second queue606in block716, which is also indicated by line614. The scheduler602then returns to block704to receive the next message608.

If, however, the scheduler602is not operating in the third operating mode, as determined in decision block718, and is operating in the second operating mode, as determined in decision block720, and is operating in high message traffic conditions, as determined in decision block722, the scheduler602determines where to store the message608in the second queue606based on one or more attributes of the message608in block714. The scheduler602then stores the message608in the second queue606in block716, which is also indicated by line614. The scheduler602then returns to block704to receive the next message608. If, however, the scheduler602is not operating under high message traffic conditions, as determined in decision block722, the scheduler602is set to the fourth operating mode in block724. The scheduler602then stores the message608in the first queue604in block710, which is also indicated by line610, and returns to block704to receive the next message608. If, however, the scheduler602is not operating in the second operating mode, as determined in decision block720, which means the scheduler602is operating in the fourth operating mode, the scheduler602stores the message608in the first queue604in block710, which is also indicated by line610, and returns to block704to receive the next message608.

Referring now toFIG. 8, a flowchart illustrating a method for pulling or scheduling queued messages from queues for processing800in accordance with one embodiment of the present invention is shown and will also be described in reference toFIG. 6. The method800is based on a low message traffic mode (first operating mode), a high message traffic mode (second operating mode) and two transition modes (third and fourth operating modes). The method800begins in block802after the scheduler has been initialized with the desired operating parameters and starts off set to the first operating mode (see description associated with block702(FIG. 7)). If the scheduler602is operating in the first operating mode, as determined in decision block804, the scheduler602pulls or schedules the next queued message from the first queue604, as shown by line612, and sends it to the processor620in block806. The scheduler602then returns to decision block804to pull or schedule the next queued message for processing. If, however, the scheduler602is not operating in the first operating mode, as determined in decision block804, and is operating in the third operating mode, as determined in decision block808, and the first queue604is not empty, as determined in decision block810, the scheduler602pulls or schedules the next queued message from the first queue604, as shown by line612, and sends it to the processor620in block806. The scheduler602then returns to decision block804to pull or schedule the next queued message for processing. If, however, the first queue604is empty, as determined in decision block810, the scheduler602is set to the second operating mode in block812. The scheduler602then determines the next queued message to pull or schedule from the second queue606based on one or more operating criteria in block814.

Next, the scheduler602pulls or schedules the selected queued message from the second queue606, as shown by line616, and sends it to the processor620in block816. The scheduler602then returns to decision block804to pull or schedule the next queued message for processing.

If, however, the scheduler602is not operating in the third operating mode, as determined in decision block808, and is operating in the second operating mode, as determined in decision block818, the scheduler602determines the next queued message to pull or schedule from the second queue606based on one or more operating criteria in block814. Next, the scheduler602pulls or schedules the selected queued message from the second queue606, as shown by line616, and sends it to the processor620in block816. The scheduler602then returns to decision block804to pull or schedule the next queued message for processing. If, however, the scheduler602is not operating in the second operating mode, as determined in decision block818, which means the scheduler602is operating in the fourth operating mode, and the second queue606is not empty, as determined in decision block820, the scheduler602determines the next queued message to pull or schedule from the second queue606based on one or more operating criteria in block814. Next, the scheduler602pulls or schedules the selected queued message from the second queue606, as shown by line616, and sends it to the processor620in block816. The scheduler602then returns to decision block804to pull or schedule the next queued message for processing. If, however, the second queue606is empty, as determined in decision block822, the scheduler602is set to the first operating mode in block822. The scheduler602then pulls or schedules the next queued message from the first queue604, as shown by line612, and sends it to the processor620in block806. The scheduler602then returns to decision block804to pull or schedule the next queued message for processing.

Although preferred embodiments of the present invention have been described in detail, it will be understood by those skilled in the art that various modifications can be made therein without departing from the spirit and scope of the invention as set forth in the appended claims.