Abstract:
In some disclosed aspects, a method of delivering messages over an electronic network includes retrieving, via an electronic processor, a first message from a message pool, determining, via the electronic processor, a delay associated with obtaining an identity of a remote receiver device of the retrieved first message, transmitting the first message to the remote receiver device if the delay is less than a threshold and storing the first message in a data store if the delay is greater than the threshold.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
       [0001]    This application is a continuation of U.S. patent application Ser. No. 10/794,411, filed Mar. 4, 2004, and entitled “ASYNCHRONOUS MECHANISM AND MESSAGE POOL,” which claims priority to U.S. Provisional Application No. 60/451,953, filed on Mar. 5, 2003, both of which are assigned to the assignee hereof. The disclosures of these prior applications are hereby incorporated by reference in their entirety. 
     
    
     BACKGROUND OF THE INVENTION 
       [0002]    1. Field of the Invention 
         [0003]    The invention relates generally to communication systems. The handling, transmission and storage of wireless and wired messages, using a protocol such as TCP/IP, can be problematic due to slowness in the handling of incoming traffic and delivery of outbound traffic. Incoming handling can be slowed by slow file creation, fragmentation and overhead delays arising from the storage of individual messages as files in a storage system. Outbound message delivery speed can be limited by the slow and unpredictable nature of looking up domain name servers, slow or delayed remote server response, remote systems being busy or down, and finite computer resources, such as size of the memory. 
         [0004]    2. Description of the Related Art 
         [0005]    Systems for handling messages are described in U.S. Pat. Nos. 6,058,389 and 6,353,834, which provide an extensive background for the field and definitions of various components used to process data. 
         [0006]    For wireless handheld and computer devices, particularly as related to the Internet, there needs to be a more efficient method of receiving and delivering messages. 
       SUMMARY OF THE INVENTION 
       [0007]    A system and method for handling incoming and outgoing messages is provided that includes a message processing system operable to write messages in batches to a message cell pool structure. A data processor receives messages that are retained in a memory. The data processor is operable to process the messages from the memory and write the messages in batches to individual cells of a message cell pool structure. The cells receive and retain the messages. The message cell pool structure is provided on a storage system with the cell pool having a number of cells of predetermined size. The message cell pool structure can be of the form of a first-in first-out (FIFO) queue where messages are written in an order that generally corresponds to receipt. A table map keeps track of the message location and status or other message information within the cells. Messages are written in batches, so as to eliminate the need to write each individual message as a file to the storage system. Further, because of the queue structure of the message cell pool, fragmentation of the writing of the batches to the storage system can be eliminated. 
         [0008]    A delivery processor is provided to oversee the delivery processing of the stored messages. The delivery processor can read messages from the message cell pool structure and attempt delivery. Associated with the delivery processor can be one or more output queues. The output queues can be used to receive messages from the message cell pool structure (e.g., at a time when messages from the message cell pool structure are ready for delivery) for further processing by the delivery processor. The output queues can be serviced in accordance with a predefined ordering or policy (e.g., implementing quality of service differentiation for different classes of messages). Alternatively, output queues can be used only for storage of messages that are delayed, or otherwise difficult to deliver. 
         [0009]    Aspects of the invention may include none, one or more of the following advantages. The messages need not remain in the memory longer than a given messaging protocol requires for server acknowledgement. The system allows for batching of messages that have been received. A message can be written to one or more cells. The cells can be optimized to accommodate the size of the message, for example, the cells can be sized to store at least 80% of the average sized message. Portions of a message can be written to cells prior to completely receiving a given message. Completely received messages can be written to the cells prior to completely receiving other messages. Thus, if only a portion of a first message in time is received before the entirety of a second message in time is received, the system need not wait to receive the entirety of the first message before processing the second message (i.e., writing the second message as part of a batch to the message cell pool structure). When the system receives a long message, the system may not need to wait to receive the entire message before processing a shorter message that is received in full. The system can have a plurality of interfaces and can contemporaneously receive a plurality of messages that are processed for subsequent transmission. 
         [0010]    Cells can be written after either a predetermined time or after a predefined number of messages have been received. Messages can be written to and retrieved from the message cell pool structure in a first-in-first-out sequence. Writing to cells can minimize disk fragmentation. 
         [0011]    A number of connections can be made for each delivery attempt. Multiple threads can be used to process the messages. During the course of delivering messages, the system can switch between awaiting connections, skipping over delayed transmissions. For delayed messages, the system only takes action on an awaiting connection when the receiver notifies the system that it is ready for further processing of the message. Messages with delivery failure can be returned and identified as returned by marking the message. Failed messages can be kept in separate storage for later processing. Storing a message in separate storage for later processing can reduce the bottleneck of message transmittal caused by returned messages. The methods used by the system can be applied to persistent store and forward systems that handle files rather than messages. 
         [0012]    The proposed message processing system solves the problems associated with large volumes of incoming messages resulting in storage management bottlenecks and slow delivery due to limited system resources and unpredictability in the real world messaging environment. The proposed message processing system avoids the problem of slow handling of returned messages. The use of a message pool and batch writing increases storage management speed. Asynchronous delivery ensures the incoming messages are delivered without choking of the outgoing message system. Backup storage provides for efficient processing of returned messages to reduce the system burden. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0013]      FIG. 1  is a block diagram of message processing system for receipt and storage of messages; 
           [0014]      FIG. 2  is a flow diagram of message receipt and storage; and 
           [0015]      FIG. 3  is a flow diagram of message processing for delivery. 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
       [0016]    As shown in  FIG. 1 , a message processing system  10  is provided for processing messages received from one or more wired or wireless devices. In one implementation, message processing system  10  is embodied in a multimedia messaging service center (MMSC) employing a data processing unit  20 . The message processing system  10  handles incoming  12  and outbound  14  messages. Message processing system  10  receives messages from wired and wireless devices  102 ,  104 ,  106 , such as the Internet, PCs, PDAs, cell phones, etc. Data processing unit  20  includes a storage memory  30  for receiving messages  12 ; an input processor  32  for processing the messages  12 ; a message cell pool  34  with a plurality of cells  117  of predetermined size; and a table map  36  for identifying messages. 
         [0017]    Optionally, message processing system  10  can have a separate delivery processor  40  and an output queue structure including one or more output queues  38  for delivery of messages. One or more of output queues  38  can be used to store messages that have failed to be transmitted to a remote receiver after a predetermined time lag, or that are returned from the remote system for various reasons, such as lack of storage and invalid recipient identity. The messages that have failed to be transmitted and that are returned messages can be processed independently of the messages that have not been returned or failed to be transmitted. Output queues  38  are discussed in greater detail below. 
         [0018]    The message processing system  10  receives messages  12  from the clients, such as the computer  102  and the wireless client, e.g. palm pilot  104  or mobile phone  106 . The messages  12  are received at storage memory  30  in a successive order as indicated by Msg1 , msg2, msg3, etc.  112  and retained in the storage memory  30  during a protocol lag. The protocol lag defines the time period in which an acknowledgment signal must be returned to a message sender in accordance with the messaging protocol being used. Absent the acknowledgement signal, the message sender may attempt retransmission of the message or otherwise indicate message failure. Messages can include meta-data, such as the address of the sender and the address of the intended recipient(s). In one implementation, storage memory  30  is a random access memory (RAM). Input processor  32  is operable to identify the receipt of a first message and gather messages for batch writing to message cell pool  34 . After the predetermined time of the protocol lag has expired for the first message, the message is acknowledged and all of the messages received during the lag are transferred in a batch to individual cells  117  in the message cell pool  34 . In one implementation, messages  112  are marked prior to being written to the message cell pool  34  (e.g., in one implementation, messages headers are marked) so as to be able to identify returned messages. Message handling by input processor  32  is described in greater detail below in association with  FIG. 2 . 
         [0019]    The message cell pool  34  is allocated in a storage system of a computer readable medium, which in one implementation is a hard disk. The message cell pool  34  comprises cells  117  of a specific predetermined size or number of bytes. The size of the cells  117  can be selected in relation to the size of the anticipated messages, where the size can be sufficient to store the average sized message in a single cell. In one implementation, the cells  117  are sized to allow each message  120  to be stored in a single cell. In one implementation, cells are sized such that at least substantially 80% of the received messages fit into a single cell. The messaging environment can determine the pool size, such that the capacity of the message cell pool  34  typically can be capable of handling the anticipated volume of messages. Messages  120  larger than the capacity of a single cell can spill over into the next cell. Each cell  117  can be filled in accordance with their respective position in the message cell pool  34  in a numerical order. 
         [0020]    The table map  36  can comprise a number of entries, where each entry is a row comprising a number of datum, each datum in an individual column. Each entry has data, such as the location  124  of a cell  117  in relation to a message  120 , the size  126  of the message  120 , whether the cell  117  contains the end of the message  130 , whether the message  120  has been processed, e.g. transmitted, what the status of the message is and other message-related information. The table map  36  can have additional data, such as a time stamp. The table map  36  can be on the same data storage entity (as the message cell pool  34 ) or a different entity that is connected to the same or a different data processor. The table map can be referred to when randomly accessing messages from storage, as described further below. 
         [0021]    The messages  120  that are stored in the message cell pool  34  are then processed, such as by delivering the messages. An asynchronous delivery mechanism can be employed. Other actions that can be performed in the processing are virus scanning, spam detection, pornography detection, etc. In one implementation, input processor  32  processes the messages for delivery. Alternatively, a separate delivery processor  40  can be provided. Input processor  32  and delivery processor  40  can be a same processor. For purposes of simplicity of the description, the delivery processing will be described in an implementation that includes a delivery processor. Other implementations are possible. 
         [0022]    In one implementation, delivery processor  40  operates to process each message individually in the order written into the message cell pool  34 , reading each message from the cells  117  based on the table map  36  information and attempting to transmit the message to the designated receiver. A delivery attempt may include opening a TCP/IP connection and exchanging protocols. After a successful delivery, the successful delivery can be recorded in the table map  36 . 
         [0023]    In one implementation, delivery processor  40  uses a pool of threads. Each thread simultaneously opens a number of TCP/IP connections for operations such as the DNS lookup or protocol exchange or data transmission, and manages the state of message processing for all the connections. In case of a delay in the remote system, such as DNS service taking a long time to resolve an IP address from a domain name, or when the remote server is busy handling other requests and is irresponsive, or the remote server is temporarily down, the thread will set a message aside by recording the current state of message processing in a memory, such as memory  50 , and utilize the same thread to handle another message using another connection. Delivery processor  40  can use a callback mechanism to notify the thread when the set aside message is ready for further action. In one implementation, the callback mechanism originates from an underlying computer network layer I/O device driver. In one implementation, a thread can complete a transmission in progress prior to taking up the set aside message for further processing. When multiple connections with messages are ready at a same time, the thread can be configured to take on each message one by one. In the event that the remote system disconnects a set aside message, because the processor is busy handling other messages, that set aside message can be characterized as a failed transmission and moved to a backup storage (not shown). Set aside messages can be stored, such as in processor memory  50 . 
         [0024]    When a message is returned from the remote server due to a system error, such as a wrong address or an out of quota or simply the remote system is down, the message can be saved in the message cell pool  34  just as other newly received messages. When the delivery processor  40  tries to deliver the returned message, the delivery processor  40  can recognize the message as returned by analyzing the message header or any other identifiable feature that indicates the message was sent out from the message processing system  10 . The delivery processor  40  can store returned messages in a file-based or backup system and remove the message from the message cell pool  34 . Periodically the system can process returned messages until either they are successfully handled or have reached a maximum number of attempts for processing and are discarded. Delivery processing is described in greater detail below in association with  FIG. 3 . 
         [0025]    A message processing system including the components described above can be use to receive a message, as described below and in  FIG. 2 . Clients transmit messages to the system. Each message includes data, the address of the sender and the recipient(s) and can optionally include a traversing path, such as IP address. Typically the messages are broken up into multiple packets for transmitting. Referring now to  FIGS. 1 and 2 , a packet is received by the system  1021  , such as the data processing in unit  20  of an MMSC. The data processing unit  20  determines whether the packet is the first of a group of packets, i.e., a message, or whether the packet belongs to a group of packets that the system has already begun to receive  1025 . If the memory does not already contain packets from a corresponding message (the “yes” branch), a new message is designated. If the received packet belongs with packets of a corresponding message (the “no” branch), the packet is stored i.e., in storage memory  30 , with the rest of the received packets from the corresponding message  1036 . The packets for each message have a sequence in which they can be ordered. 
         [0026]    The data processing unit  20  determines whether the message to which the packet was added is complete  1041 . If the message is not complete (the “no” branch), the data processing unit awaits a new packet  1021 . If the message is complete (the “yes” branch), the data processing unit determines whether a trigger event has occurred  1057 . In one implementation, the trigger event can be the receipt of a predetermined number of messages. Other trigger events are discussed below. If the predetermined number of completed messages have not been received (the “no” branch), the processor continues to received packets  1021 . If the predetermined number of complete messages have been received (the “yes” branch), i.e., the capture period has elapsed, the completed messages are batched  1054 . The batched messages are written to a persistent storage (i.e. message cell pool  34 )  1059 . In one implementation, portions of a message can be written as part of a batch, that is, input processor  32  can be configured to include in a batch a portion of message that has been received such that the portion can be written to message cell pool  34  prior to receipt of the entire message. In one implementation, when a write to cell function occurs, all portions of messages and complete messages are written to cells (i.e., input processor  32  does not wait for complete messages to be received before writing to the message cell pool  34 ). 
         [0027]    Each message is either written into a single cell or more than one cell when the message is greater than the capacity of the cell. When a message is written to the cell, the location of the cell is recorded as an entry in the table map  1064  along with any other relevant information, such as size, and whether the message is complete in a cell or subsequent cell. This process is repeated with each successive write to the cells. In one implementation, message processing system  10  does not treat each individual message as a separate file. Rather, groups of cells  117  or all of the cells  117  in the cell message pool  34  are processed as one file. Treating groups of cells as files or the entire cell structure as a single file can reduce disk fragmentation. 
         [0028]    In one implementation, the trigger event described in step  1057  is the expiration of the protocol lag time. More specifically, the initial message received in a capture period defines the beginning of the capture period. The end of the capture period (i.e., the expiration of the protocol lag time) triggers the end of the capture period. Messages received during the capture period can then be batched and written to the message cell pool  34 . In one implementation, the trigger is a time period that is determined by the protocol lag. In such an implementation, input processor  32  may immediately send acknowledgement signals or alternatively may send acknowledgment signals coincident with the batching process (i.e., the acknowledgement signals may not be sent immediately after receipt of a given message and instead delayed so as to allow for the efficient batching of messages in the storage memory  30 ). Messages arriving within the capture period form a batch of messages written to the message cell pool  34 . The SMTP or SMPP protocol permits a predetermined lag before acknowledgement which time lag can be as long as 10 minutes. During this time lag, the input processor  32  can wait for additional messages from any client prior to batch writing messages to message cell pool  34 . 
         [0029]    In one implementation, the trigger event described in step  1057  can be defined in other ways including by the expiration of a system predefined time, such as 1/10 of a second or another time adequate for the system traffic and storage capacity of the memory. However, other ways of determining when to trigger the batch write operation can be selected. 
         [0030]    A message can have information added to the message, such as a header to notify the system of the processing history of the message. Such additional information can include the identity of the system. The additional information permits recognition that the message has been processed by the system in the event the message is returned to the system. In the case of email, the system may indicate in the header that the system has received the message. 
         [0031]    As the number of received messages increases, cells are filled in the order in which the messages are received until the message cell pool  34  is filled. In one implementation, when the message cell pool  34  is filled, no new messages can be written to the message cell pool  34 . As a practical matter, the message cell pool  34  is usually available for new messages, without requiring the memory to store messages while waiting for the message cell pool  34  to become available. However, in the event that the availability of the message cell pool  34  is more limited than the system requires, one or more additional message cell pools can be provided. When all messages have been processed, as evidenced by the table map, as either having been successfully transmitted or having been sent to a backup database, new messages can be entered overwriting messages in cells from the beginning of the cell bank. In one implementation, not all of the messages in the message cell pool  34  are required to be processed prior to the overwriting of older messages. That is, in one implementation, pointers to the head and the tail of the message cell pool  34  can be used to read and write messages from the message cell pool  34  (i.e., so that new messages can be written to appropriate locations of the message cell pool  34  and so that the oldest messages in the message cell pool  34  can be processed for delivery). 
         [0032]    Messages received from a client may be subject to various interruptions, e.g., there may be stoppages of transmission from the client. The system can disconnect from a remote system after a configurable predetermined period of time. If the handshake is unsuccessful or the message is in an unrecognizable form, the system can disconnect. When only a partial message is received, the partial message can be discarded. 
         [0033]      FIG. 3  shows a flow diagram for operation of the delivery processor  40  when delivering a message to a recipient. Referring now to  FIGS. 1 and 3 , the delivery processor  40  begins by retrieving one or more messages from the message cell pool  34  in block  2000  of  FIG. 3 . In one implementation, the delivery processor  40  removes one message at a time from the message cell pool  34  in block  2000  of  FIG. 3 . In another implementation, the delivery processor  40  retrieves a block of messages from the message cell pool  34  prior to processing. 
         [0034]    Delivery processor  40  seeks a remote receiver identity in block  2004 , where normally there will be a delay. Delivery processor  40  determines whether the delay is beyond a predetermined period in block  2006 . If the delay is beyond the predetermined period, (the “yes” branch), the message is set aside in block  2007  and another message is processed at block  2000 . If there is no delay or the delay is not beyond the predetermined period, (the “no” branch), the message enters into protocol exchange in block  2008  with the recipient. Delivery processor  40  determines whether the protocol exchange was successful in block  2011 . If for any reason the protocol exchange is not successful (the “no” branch), the message is then set aside at block  2007 . After a successful protocol exchange (the “yes” branch), the message is transmitted to the remote receiver in block  2014 . If the message is successfully transmitted (the “yes” branch) in block  2022 , the successful transmission is recorded in the table map in block  2027 . If for any reason there is an interruption or a failure in transmitting the message (the “no” branch of block  2022 ), the message is set aside in block  2007 . 
         [0035]    The messages set aside in block  2007  are retained until the messages are ready for transmission to the remote receiver. Delivery processor  40  can track the amount of time that a message has been set aside via block  2030 . If a prescribed amount of time has passed and no signal or response has been received from the remote receiver (the “yes” branch of block  2030 ), the message is sent to backup in block  2042 . When a message is sent to backup, the status of the message as processed is recorded in a table map in block  2050 . At any time the remote receiver can call back or send a signal to the delivery processor  40  indicating that it is ready to receive the message and the system can receive the sent signal in block  2037 . When the delivery processor  40  receives the signal indicating that the remote receiver is ready to receive the message and the system receives this signal (the “yes” “branch” of block  2037 ), the message can be processed and is transmitted via block  2014 . Otherwise, the system continues to wait for the signal or the prescribed time to pass (the “no” branch of block  2030 ) via block  2007 . 
         [0036]    When a message is returned to the system via block  2061  , such returned message can be stored in the backup database in block  2042 . Messages in the backup storage are subject to being overwritten in the message cell pool  34 . The delivery processor  40  can periodically check whether there are messages that need to be delivered in the backup storage and transfer the messages to the system for transmission. The number of attempts to transmit a message can be recorded by the delivery processor  40 . When the maximum number of attempts defined by the system has been reached, the message can be erased. 
         [0037]    The delivery processor  40  can deliver the messages in the order that the messages were received by the message processing system  10 . Alternatively, the delivery processor  40  can deliver the messages out of the order in which the messages were received, as described further below. 
         [0038]    In one implementation, the delivery processor  40  retrieves messages and writes the retrieved messages into one of multiple output queues  38 . The delivery processor  40  can be configured to write messages to one of the output queues  38  based on information in the message, such as a domain name or priority indication on the message. The delivery processor  40  can then process the messages from the one or more output queues  38 , where each queue can have a priority associated with it. For example, messages of high priority can be written to a first queue, messages of a standard priority can be written to a second queue and messages of a low priority can be written to a third queue. The delivery processor  40  can access the first queue 50% of the time for delivering messages, access the second queue 35% of the time for delivering messages and access the third queue 15% of the time. Other priority systems, such as different allocations (i.e., quality of service (QOS)) of accessing the various queues can be configured. In another implementation, the delivery processor  40  can randomly access the output queues  38 . In yet another implementation, QOS can be provided by assigning one queue to messages that have not yet been sent out of the system. The other queues can be reserved for messages that have been returned to the system or that have not been delivered due to a transmission failure. The queue for messages that have not yet been sent out of the system can be prioritized over the other queues. 
         [0039]    The subject system can be readily applied to a wide variety of applications. The methods described above can be applied to wireless messaging, such as SMS systems, email systems, stock or commodity exchange systems, and the like. In addition to messaging, the system can be applied to any persistent store and forward application. In place of storing and processing messages, files can be stored and processed. Each file can be parsed into packets for transfer. 
         [0040]    All references referred to in the text are incorporated herein by reference as if fully set forth herein. The relevant portions associated with this document will be evident to those of skill in the art. Any discrepancies between this application and such reference will be resolved in favor of the view set forth in this application. 
         [0041]    Although the invention has been described with reference to the above examples, it will be understood the modifications and variations are encompassed within the spirit and scope of the invention. Accordingly, the invention is limited only by the following claims.