System and method for detecting lost messages transmitted between modules in a communication device

A method and module for tracking transmission of messages being sent from a transmitting module to a receiving module in a communication device is provided. The method includes the step of (a) receiving a message at the receiving module. The method also includes the step of (b) evaluating the received message to determine whether the received message was received by the receiving module in a proper sequence to a previous message, if any, sent by the transmitting module. The method further includes the step of (c) generating an acknowledgement message from the receiving module to the transmitting module, the acknowledgement message including an indicator, a value of the indicator indicating whether the previous message, if any, transmitted from the transmitting module to the receiving module immediately before the received message was received by the receiving module.

FIELD OF THE INVENTION

The invention relates to a system and method for tracking messages which are transmitted between two modules in a communication device. In particular, the invention relates to a method of detecting when a sent message is not received by the destination module.

BACKGROUND OF INVENTION

In a communication device, it is typical that functionality for the device is embodied into several modules. For example, in a communication switch, modules include line cards, switching fabrics and control systems. In turn, each module may itself comprise several submodules. This may continue iteratively for sub-modules. As circuit densities increase on integrated circuits, such circuits are commonly developed as a series of interconnected modules. Signals are communicated between modules through connections between modules. Due to the increasing densities and operating frequencies of the integrated circuits, signals carried on the connections are prone to contain errors.

For the modules of a communication device, a messaging system is commonly used. Therein, each module may generate a message having administrative and payload information. The administrative information may include the intended destination of the message, the size of the message and error management information. The message is transmitted over a communications link from the source module to the destination module.

Frequently, messages and data packets processed by a communication device must be maintained in some order. A known method of tracking data packets is to associate a sequence number with each packet. When a communication device receives a packet, its modules process the packet internally and eventually the device transmits the packet to another communication device. In order to facilitate the internal processing of the packets by the communication device, frequently a separate message is associated with each packet. The messages are transmitted between the modules in conjunction with the processing of the related packets by the modules. It will be appreciated that as the messages contain administrative information regarding their packets, the modules which process the messages may not necessarily be the same modules which process the packets. As an example, in processing a packet, one module may be responsible for determining an action for a packet (e.g. queue, discard, modify etc) and another module may perform the action.

When transmitting messages, a module which transmits a message needs to know whether a transmitted message was received by the destination module. A failure in the communications link or an error in the message itself may cause the message to be lost. As a solution, prior art messaging systems track messages by having a module which receives a message generate and transmit an acknowledgement (ACK) message back to the transmitting module. When the transmitting module eventually receives the ACK message, it knows that the transmitted message was received.

There are deficiencies with the transmit/ACK message scheme. For example, if a failure occurs when transmitting the initial message by the transmitting module, the intended receiving module will not receive the message and will not generate a replying ACK message. In this situation the transmitting module will be waiting, perhaps indefinitely, for the ACK message. If a failure occurs when transmitting the ACK message by the receiving module, the originating transmitting module will not receive the ACK message and will not have knowledge that the original message was, in fact, successfully received by the receiving module. These failures are not equivalent in that the receiving module is in a different state either having seen the original message or not. There are many situations in which the loss of a message may result in a persistent impairment to the system's operation. Given that the transmit/ACK messaging scheme does not differentiate between these failure mechanisms, the only corrective action to take may be to reset the system. Evidently, this will disrupt the operation of the system.

There is a need for a system and method for providing improved messaging scheme between two modules wherein individual failures of transmission of messages between the modules can be detected and accommodated.

SUMMARY OF INVENTION

In a first aspect, a method of tracking transmission of messages being sent from a transmitting module to a receiving module in a communication device is provided. The method includes the step of (a) receiving a message at the receiving module. The method also includes the step of (b) evaluating the received message to determine whether the received message was received by the receiving module in a proper sequence to a previous message, if any, sent by the transmitting module. The method further includes the step of (c) generating an acknowledgement message from the receiving module to the transmitting module, the acknowledgement message including an indicator, a value of the indicator indicating whether the previous message, if any, transmitted from the transmitting module to the receiving module immediately before the received message was received by the receiving module.

If step (b) determines that the received message was not received in the proper sequence, the value of the indicator may indicate that the previous message was not received by the receiving module.

The method may further include the step of (d) transmitting the acknowledgement message to the transmitting module.

The messages and the acknowledgement message may be associated with packets transmitted from the transmitting module to the receiving module.

Each the acknowledgement message may include a first field including a value indicating an acknowledgement response for the received message and a second field including one of: (i) the value of the indicator; and (ii) a value indicating an acknowledgement response for the previous message transmitted from the transmitting module to the receiving module immediately before the received message.

The acknowledgement response for the previous message and the acknowledgement response for the received message may indicate, respectively, whether the previous message and the received message were accepted by the receiving module.

The method may further include the steps of (e) receiving the acknowledgement message sent by the receiving module at the transmitting module and (f) determining whether the received acknowledgement message was received by the transmitting module in a proper sequence to a previous acknowledgement message, if any, sent by the receiving module.

Each acknowledgement message may further include a sequence number. If the step (b) determines that the received message was not received in the proper sequence, the step (c) may set the sequence number of the acknowledgement message to a value so indicating. The step (f) may determine whether the received acknowledgement message was received by the transmitting module in a proper sequence to a previous acknowledgement message based on the value of the sequence number of the received acknowledgement message.

The method may further include the step of (g) if the received acknowledgement message was not received by the transmitting module in the proper sequence, evaluating the value of the second field to determine whether the previous message transmitted from the transmitting module to the receiving module immediately before the received message was received by the receiving module.

The method may further include the step of (h1) if the received acknowledgement message was not received by the transmitting module in a proper sequence and if the value of the second field indicates that the previous message transmitted from the transmitting module was not received by the receiving module, synchronizing an internal state of the transmitting module with the receiving module to reflect loss of the previous message.

The method may further include the step of (h2) if the received acknowledgement message was not received by the transmitting module in a proper sequence and if the value of the second field indicates that the previous message transmitted from the transmitting module was received by the receiving module, processing the acknowledgement response for the previous message contained in the second field.

The transmitting module may allocates memory associated with the messages transmitted to the receiving module. The method may further include the step of (i) reallocating the memory in response to the value of the first field and the value of the second field.

In a second aspect, a method of tracking transmission of acknowledgement messages being sent from a receiving module to a transmitting module in a communication device is provided. Each of the acknowledgement messages is associated with a message sent from the transmitting module to the receiving module. The method includes the steps of (a) receiving an acknowledgement message sent by the receiving module at the transmitting module, the received acknowledgement message including an indicator, a value of the indicator indicating whether a previous message, if any, transmitted from the transmitting module to the receiving module immediately before a message associated with the received acknowledgement message was received by the receiving module. The method also includes the step of (b) determining whether the received acknowledgement message was received by the transmitting module in a proper sequence to a previous acknowledgement message, if any, sent by the receiving module.

In a third aspect, a receiving module for tracking transmission of messages being sent from a transmitting module to the receiving module in a communication device is provided. The receiving module includes a first input adapted to receive a message and a sequence evaluation unit adapted to evaluate the received message to determine whether the received message was received in a proper sequence to an earlier message, if any, sent by the transmitting module. The receiving module also includes an acknowledgement unit adapted to generate an acknowledgement message for transmission from the receiving module to the transmitting module, the acknowledgement message including an indicator, a value of the indicator indicating whether a previous message, if any, transmitted from the transmitting module to the receiving module immediately before the received message was received by the receiving module.

In a third aspect, a transmitting module for tracking transmission of acknowledgement messages being sent from a receiving module to the transmitting module in a communication device is provided. The transmitting module includes a first input adapted to receive an acknowledgement message sent by the receiving module at the transmitting module, the received acknowledgement message including an indicator, a value of the indicator indicating whether a previous message, if any, transmitted from the transmitting module to the receiving module immediately before a message associated with the received acknowledgement message was received by the receiving module. The transmitting module also includes a sequence evaluation unit adapted to determine whether the received acknowledgement message was received by the transmitting module in a proper sequence to a previous acknowledgement message, if any, sent by the receiving module.

In other aspects, various combinations and subset of the above aspects are provided.

DETAILED DESCRIPTION OF EMBODIMENTS

The description which follows, and the embodiments described therein, are provided by way of illustration of an example, or examples, of particular embodiments of the principles of the present invention. These examples are provided for the purposes of explanation, and not limitation, of those principles and of the invention. In the description which follows, like parts are marked throughout the specification and the drawings with the same respective reference numerals.

Prior Art Messaging Scheme

In order to illustrate the features of the embodiments, first, features and issues of a prior art messaging scheme are provided.

Referring toFIG. 1A, prior art communication device100in a communication switch is shown. Communication switch and, accordingly, communication device100process transmission of data traffic. As is known, in processing data traffic, the switch may segment the data traffic into a series of portions, or packets. An upstream device to the switch may also have already performed segmentation. Each packet is an ordered element relative to the other packets of the data traffic. The packets are each individually processed and transmitted by the communication device. To aid in tracking processing and transmission of the packets, communication device uses a series of discrete messages to track each packet. Device100has module102and module104to track the packets and their messages during processing of the packets. Modules102and104have internal memories108and110, respectfully, to store information relating to the packets and messages. Modules102and104transmit their messages to each other over communications link106.

When a packet120arrives at module102, module102allocates memory122from internal memory108to store packet120. In processing the transmission of packet120, messages130are generated by modules102and104and transmitted to each other over communications link106. Module102transmits message130to module104over communications link106, indicated by arrow132, to process information related to packet120. When module104receives message130, it responds by transmitting an ACK134to module102over communications link106, indicated by arrow136.

Referring toFIG. 1B, in one prior art implementation, message130comprises 4 bytes and is segmented into a series of fields, including: message identifier field162′ (4 bits) containing message identifier162; sequence number field164′ (8 bits) containing sequence number164; message payload166′ (20 bits) containing message payload166. Referring toFIG. 1C, in one prior art implementation, ACK134comprises 2 bytes and is also segmented into a series of fields, including: message identifier field172′ (4 bits) containing message identifier172; sequence number field174′ (8 bits) containing sequence number174; reply field176′ (1 bit) containing reply176; and padding field178′ (3 bits). In this example, reply field176′ contains a response to its corresponding message130indicating whether the corresponding packet120should be accepted or discarded. Sequence numbers placed in fields164and174enable messages to be sequenced.

In a first scenario, a series of messages130and ACKs134are successfully exchanged between modules102and104. Therein, at time202, packet120(1) arrives at module102, which triggers module102to generate and transmit a message130(1) to module104. Module102transmits message130(1) to module104over communications link106, as indicated by arrow232(1). At time208, module104receives message130(1) and, responsive to receiving message130(1), generates ACK134(1). Accordingly, module104transmits ACK134(1) to module102, indicated by arrow236(1), which arrives at module102at time214. By receiving ACK134(1), module102can determine that message130(1) has been received by module104.

In a second scenario, a failure point is introduced in the exchange of messages130and ACKs134. Therein at time206, packet120(2) arrives at module102, triggering the generation and transmission of message130(2) to module104over communications link106, indicated by arrow232(2). At time212, module104receives message130(2) and generates ACK134(2), which is transmitted to module102, as indicated by arrow236(2). However, fault240in communications link106prevents ACK134(2) from being received at module102. Accordingly there is a disconnect of synchronization between the series of messages130and the corresponding series of processed packets120.

In a third scenario, a failure point is introduced in the messaging process from module102to module104. At time210, packet120(3) arrives at module102, triggering the generation and transmission of message130(3) to module104, indicated by arrow232(3). However, fault242prevents message130(3) from arriving at module104. Therefore, module104does not generate and transmit an ACK134for message130(3).

In the second and third scenarios, device100must respond to the fault condition to recapture memory and resynchronize the information contained in modules102and104. If this is not done, the coordination of the modules will likely be impaired or lost entirely and memory that has been used may not be reallocatable. As similar fault conditions happen again, additional memory may become unusable, eventually incapacitating the communication device.

Messages, including ACK messages, of prior art systems and the embodiment may use various error detection schemes (or error detection and correction schemes) including parity, CRC and other known encoding schemes. Encoding schemes that provide error detection and correction tend to not be bandwidth efficient. Error detection schemes can be very effective at preventing the passing of erroneous information, however, the response is generally limited to discarding the errored message.

Basic Features of the Embodiment

Briefly, a communication device of the embodiment has a first module and a second module communicating over a communications link between the first and second modules. In a typical messaging system, the first module transmits a message to the second module. The second module replies to the message with an acknowledgement message (“ACK message”, or simply “ACK”). The ACK signifies that the second module has received the current message. However, the ACK also contains an indication whether the second module had received a previous message, in particular, the last message which was sent before the current message. The messages have a sequence number to distinguish themselves from each other and to identify their order with each other. The second module also tracks the sequence number of a received message and can determine whether a previous message was received. The messaging scheme of the embodiment allows tracking of current messages against previously received messages and expected messages.

Messaging Scheme and Communication Device of an Embodiment

Referring toFIG. 3A, communication device300of an embodiment is similar to device100in that it has a first module302and a second module304connected by a communications link306. Differences relating to the invention are provided in a messaging scheme used for communications sent between the modules. In particular, module302has internal memory308and module304has internal memory310. Modules302and304in device300transmit messages330to one another to process packets (not shown) arriving at device300. When module304receives message330, it transmits an ACK334to module302. Modules302and304may be ASICs which process aspects of the packets being transmitted by the communication switch having appropriate control logic to implement the message processing described herein. Alternatively, the message processing may be embodied in appropriate software/firmware modules operating on the modules. In the embodiment, the communications link306is preferably an optical signalling link. Contents of messages330and ACKs334may have to be converted for transmission following the transmission protocols of communications link306. In different embodiments, modules302and304may be on the same functional element, e.g. the same line card, or they may be on different functional elements, e.g. module302may be on a line card and module304may be in the control system. In the particular implementation, the system being considered as a unit is a portion of a line card and the two modules are ASICs located on that line card.

In device300, each message330is associated with a sequence number which acts as a historical identifier, indicating its ordinal location in the set of messages330generated for the corresponding set of ordered packets. By tracking sequence numbers, when a module receives a message330, the module can extract the contained sequence number and determine whether the just-received message is in sequence with the message330received immediately before it. Also the module can determine what message330is expected to be received immediately after it. Sequence number generation can be performed in any manner in which sequence numbers do not repeat within a period of time (comparable to the transmission time for a transmission and receipt of a message/ACK signal sequence) and which can be independently generated in two locations with the same values. A counter (with wrap-around at maximum value) is a simple example that meets these requirements, it has the further advantage that it is simple to determine the preceding or following values from any given value. In this way, if module304stores the sequence number of the last message330it received, it can determine if the next message330it receives is in sequence or not. And if not, it can determine which message(s)330were not received. Similarly, if module302stores the sequence number of the last ACK334it received, it can determine if the next ACK334it receives is in sequence or not. And if not, it can determine which ACK(s)334were not received.

Referring toFIG. 3B, message330(generated by module302) comprises at least the following fields: message identifier field362′ (4 bits) containing message identifier362; sequence number field364′ (8 bits) containing sequence number364; and message payload field366′ (20 bits) containing payload366. For a received message330, module304can use the sequence number364to determine what message330should be received after the just received message330and can determine whether there is a message gap, i.e. a missing message330, between the message330received just before the just received message330. Gaps in the sequence are evaluated at module302by a sequence evaluation unit344.

Referring toFIG. 3C, ACK334is generated by acknowledgement unit348at module304for transmission to module302and is responsive to a received message330. ACK334has at least the following fields: message identifier field372′ (4 bits) containing message identifier372; sequence number field374′ (8 bits) containing sequence number374; first reply field376′ (1 bit) containing first reply376which is an acknowledgement response (accept or discard) for its corresponding message; second reply field378′ (2 bits) containing second reply378; and padding field380′ (1 bit). It will be appreciated that in the embodiment, ACK334is the same size as ACK134(FIG. 1C). Accordingly, there is low bandwidth overhead for the signalling scheme of the embodiment. Further, in many cases there may be no increase in signalling bandwidth requirements.

Second reply378provides an indication of the acknowledgement response of a first reply376sent in the immediately previous ACK334. Accordingly, module304stores first reply376of the immediately previous ACK334to populate second reply378of the next ACK334if no message gap occurs. Module302also stores sequence numbers374of previously received ACKs334and recognises when a gap in the sequence of ACKs334received occurs. Gaps in the sequence are evaluated at module302by a sequence evaluation unit344. A gap in the sequence prompts module302to read information from second reply378. From the information contained, module302receives information from a lost ACK334.

FIG. 3Aillustrates two scenarios of an exchange of messages330and ACKs334between modules302and304. Time axis312demarks times of transmission of messages330and ACKs334between modules302and304.

In a first scenario, a normal, successful series of messages330and ACKs334are exchanged between modules302and304. At time314, module302generates and transmits message330(1) to module304over communications link306, indicated by arrow332(1). Message330(1) is populated with sequence number364(1) and message payload366(1) which contains processing instructions for module304. Subsequently, message330(1) arrives at module304. Thereafter, at time318, acknowledgement unit348of module304generates ACK334(1) and populates it with sequence number374(1), first reply376(1) and second reply378(1). Sequence number374(1) contains a code, as a number, that is associated with sequence number364(1) of message330(1). In the embodiment, sequence number374for ACK334is set to the sequence number364for its message330. First reply376(1) contains the acknowledgement response for message330(1) (indicated by “A1”) while second reply378(1) contains the acknowledgement response for the previous message, message330(0) (not shown) (indicated by “A0”). Module304stores sequence number364(1) and first reply376(1) for future use. Module304transmits ACK334(1) to module302, indicated by arrow336(1), which arrives at time322. By tracking sequence numbers374with sequentially transmitted packets, when module302receives ACK334(1), sequence evaluation unit344can extract the sequence number374(1) therefrom and compare it with the previously received sequence numbers374. It does this by comparing a sequence number374stored to sequence number374(1) received. Sequence evaluation unit344can either count up from stored sequence number374or back from a next received sequence number374to determine whether there is a message gap. A gap in the sequence indicates that an ACK334was not received between the last two sequence numbers374, i.e. the last two received ACKs334. Sequence evaluation unit344determines that there is no message gap.

In a second scenario, an ACK334is lost en route to module302as a fault340is present in the communications link306shortly after time322. Therein, at time316, module302transmits message330(2) to module304over communications link306, indicated by arrow332(2). Subsequently, message330(2) arrives at module304. At time320, acknowledgement unit348generates ACK334(2) which comprises sequence number374(2), first reply376(2) and second reply378(2). Module304transmits ACK334(2) over communications link306, indicated by arrow334, but it does not arrive at module302due to fault340. Thereafter, at time320, module302transmits message330(3) to module304over communications link306, indicated by arrow332(3). Subsequently, message330(3) arrives at module304. At time324, acknowledgement unit348generates ACK334(3) and populates it with sequence number374(3), first reply376(3) and second reply378(3). Second reply378(3) contains the acknowledgement response provided to message330(2) that did not arrive at module302. Module304transmits ACK334(3) to module304, indicated by arrow336(3). ACK334(3) arrives at module302at time328. Sequence evaluation unit344again compares the received sequence number374(3) with the stored sequence number374(1). Sequence evaluation unit344does this by either counting up from stored sequence number374(1) or back from received sequence number374(3). As the sequence number374(3) for the current response is “3”, as illustrated, sequence evaluation unit344determines whether the sequence number has the expected next value for the received ACK334. As a “2” was expected for the “3” key and it was not provided, sequence evaluation unit344recognizes the discrepancy and notes that an error has occurred. Sequence evaluation unit344indicates this error to module302which then reads the information that was lost from second reply378(3). At this time, module302has been provided with the previously lost acknowledgement response to message330(2).

Next, referring toFIG. 4, module304tracks sequence numbers364to determine whether a previously transmitted message330was received. Module304determines whether there is a message gap by storing sequence numbers364from previous messages330. After receiving a message330with a sequence number364, module304compares sequence number364with the stored sequence number364. Module304can either count up from stored sequence number364or back from received sequence number364to determine whether the sequence number364received has the expected value. Gaps in the sequence are evaluated at module304by a sequence evaluation unit346. If module304determines that it did not receive a previously transmitted message330, second reply378in the current ACK334is set to a flagging value to indicate this condition by module304. ACKs334are generated at module304by an acknowledgement unit348. Module304generates a value for sequence number374that indicates a gap in the sequence of ACKs334. ACK334is transmitted to module302with sequence number374. Module302checks for gaps in sequence numbers374received. Gaps in the sequence are evaluated at module302by a sequence evaluation unit344. A gap in the sequence prompts module302to read information from second reply378where the flagging value acts as an indicator to indicate to module302that a previously transmitted message330was not received by module304. Module302can then resynchronize itself with module304by updating its internal state to reflect the loss of message330. Synchronization may be achieved by such means as discarding information relating to the lost message330or retransmitting the lost message330. Accordingly, module302may store transmitted messages330if they are to be retransmitted if a message gap occurs.

InFIG. 4, an example is illustrated of a message330being lost en route to module304of device300. Time axis400demarks times of transmissions of messages and ACKs between modules302and304. At time402, module302generates message330(11) for transmission to module304over communications link306, indicated by arrow432(11). Message330(11) is populated with sequence number364(11) and message payload366(11) which contains the processing parameters for module304. Subsequently, message330(11) arrives at module304.

Sequence evaluation unit346of module304compares sequence number364(11) with a previously stored sequence number364. Sequence evaluation unit346determines that no message gap has occurred.

At time406, acknowledgement unit348generates ACK334(11) and populates it with sequence number374(11), first reply376(11) and second reply378(11). First reply376(11) contains the acknowledgement response for message330(11) (indicated by “A11”) while second reply378(11) contains the acknowledgement response for the previous message, message330(10) (not shown) (indicated by “A10”). Module304stores sequence number364(11) and first reply376(11) for future use. Module304transmits ACK334(11) to module302, indicated by arrow436(11), which arrives at time410. Sequence evaluation unit344at module302similarly compares sequence number374(11) with a previously stored sequence number374and determines that no message gap has occurred.

At time404, module302generates and transmits message330(12) to module304over communications link306, indicated by arrow432(12). However, due to fault442, message330(12) does not arrive at module304. Therefore, acknowledgement unit348has no trigger to generate ACK334.

At time406, module302transmits message330(13) to module304over communications link306, indicated by arrow432(13). Subsequently, message330(13) arrives at module304. Sequence evaluation unit346extracts sequence number364(13) from message330(13) and compares it with stored sequence number364(11). Sequence evaluation unit346does this by either counting up from stored sequence number364(11) or back from received sequence number364(13). As the sequence number364(13) for the current message is “13”, as illustrated, Sequence evaluation unit346determines whether the sequence number has the expected next value for the last received message330. As a “12” was expected for the “13” key and it was not provided, an error has occurred. Accordingly, acknowledgement unit348will populate second reply378(13) with an “invalid” flag indicating that the previous message330was not received (indicated by “inv”).

At time410, acknowledgement unit348generates ACK334(13) and populates it with sequence number374(13), first reply376(13) and second reply378(13). Module304generates a value for sequence number374(13) that indicates a gap in the sequence of ACKs334. This is most easily achieved by copying the value for sequence number364(13) from message330(13). First reply376(13) contains the acknowledgement response for message330(13) (indicated by “A13”) while second reply378(13) contains the “invalid” flag.

Module304transmits ACK334(13) to module302, indicated by arrow436(13), which arrives at time414. Sequence evaluation unit344again checks for gaps in sequence numbers374received. Sequence evaluation unit344detects a gap in the sequence which prompts module302to read information from second reply378(13). The “invalid” flag in second reply378(13) indicates to module302that the previous message330(12) did not arrive at module304. Module302then resynchronizes itself with module304. In this example, module302transmits message330(14) to module304, indicated by arrow432(14), with the processing parameters that were lost due to fault442. This is indicated by the value “M12” in the message payload364(14) in message330(14), originally transmitted in message330(12). It will be appreciated that module302may resynchronize itself with module304by other means including discarding information relating to message payload364(12).

The basic algorithm and scheme of the embodiment described thus far does not track loss of a last ACK334to a set of messages330. Device300deals with this situation in the following manner, illustrated byFIG. 5. Therein, time axis500demarks times of transmission of messages330and ACKs334between modules302and304. A scenario is shown where the final ACK334(1) to message330(21) is lost en route to module304, indicated by arrow536(21)(i) terminating at fault540. Module304monitors communications link306for excess bandwidth. If there is bandwidth available on communications link306, module304retransmits ACK334(1) to module302, indicated by arrow536(21)(ii). Sequence evaluation unit344, checking for gaps in the sequence, determines that ACK334(21)(ii) is the next expected ACK334and processes it accordingly.

If the final message330from module302to module304is lost, then upon bandwidth being available on communications link306, module304retransmits the previous ACK334. The next ACK334contains the same information as the previous ACK334received by module302. Sequence evaluation unit344at module304, checking for gaps in the sequence, determines whether the sequence number374received matches the last sequence number374. Module302thereby recognizes that the final message330was lost and retransmits final message330.

Under idle conditions in which no messages are being transmitted from module302to module304, module304will transmit the last valid ACK334that it has sent previously as bandwidth is available. To conserve usage of bandwidth, it may be desireable to limit the rate at which ACKs334are sent rather than using all idle bandwidth for this. In the initialization case where no message330has been received, an ACK334will be generated indicating that there have been no valid messages330received. A number of methods may be used to indicate this. First reply376may have a “valid/invalid” bit added to it, sequence number374may be given an invalid value or sequence number374may be initialized to the value that precedes the initial value of sequence number374. For example if sequence number374is 8 bits long and module302initializes it to a binary number representing “0”, then in this condition module304will send ACK334messages with sequence number374having a binary number representing “255”.

Furthermore module302may provide a “time out” function in which if an ACK334is not received corresponding to a message330within some bounded period of time module302will consider message330to have been lost and react accordingly.

In the device of the embodiment, messaging between modules302and304is typically very reliable, i.e. relatively few messages330and ACKs334are lost compared to the number of messages330and ACKs334transmitted. However, for a high volume of messages330and ACKs334transmitted in device300this would still have modules302and304losing track of a notably large portion of their internal memories308and310, respectively. The method of transmitting messages330and ACKs334of the embodiment works well since there is a low occurrence rate of loss of consecutive messages330or ACKs334in the normal operation of device300. If the embodiment is not able to perform the corrections detailed above because the rate at which messages330and ACKs334are being lost in transmission exceeds the ability of the system to generate successfully transmitted messages between the modules, it may be assumed that a significant, non recoverable fault has occurred requiring the resetting of the system.

If the system described above loses messages330such that sequence number374received at module302indicates a gap of two or more sequence numbers374, the particular embodiment, as described, may not be able to correct the gap and may not be able to guarantee the level of system correctness that is possible with the loss of single messages330or ACKs334. In this case, module302can assume that the messages330for which an ACK334has not been received were lost, which module302may have already done due to the time out period being exceeded. Note that correct behaviour is not guaranteed since it may have been a number of ACK334messages that were lost. When a number of messages330and/or ACKs334are lost it is likley that link level error detection will raise alarms to a higher level device in the system which may trigger a system reset. If a sequence number374received at module302indicates a gap of two or more sequence numbers374, this may be used by module302to raise an alarm which can in turn be used to trigger a system reset.

An extension of the embodiment to support the recovery of the system from the loss of consecutive messages without requiring a system reset will be described next. The number of consecutive messages whose loss can be recovered from can be engineered according to the expected rate of consecutive errors.

Messaging Scheme and Communication Device of an Embodiment tracking Consecutive Lost ACKs or Messages

In situations where the loss of consecutive messages330or ACKs334is more likely to occur, the above described embodiment may be extended by increasing the length of the ACK334and transmitting a number of previous acknowledgement responses to the originating module. Accordingly, referring toFIG. 6A, communication device600is illustrated, which is an extension of an embodiment. Therein, device600is similar to device300in that it has a first module602and a second module604connected by a communications link606. Modules602and604both have internal memories (not shown). Modules602and604transmit messages630to one another to process packets arriving at device600. The module receiving the message630transmits an ACK634to the module originating the message630.

As described with respect to module304, sequence evaluation unit644at module604can track expected next messages630via the sequence number664and use sequence number664to determine whether there is a gap in sequence numbers664between the just received message630and the last received message630.

Referring toFIG. 6B, when module602generates a message630, the message630has at least the following fields: message identifier field662′ (4 bits) containing message identifier662; sequence number field664′ (8 bits) containing sequence number664; and message payload666′ (20 bits) containing message payload666.

Device600differs from device300in how it transmits ACKs634. An ACK634generated by acknowledgement unit648at module604includes a series of two bit replies to the previous messages630. In this embodiment, ACK634includes a reply to the previous message630and replies to the two previous messages630. Referring toFIG. 6C, when module604provides an ACK634to module602responsive to a received message630, ACK634has at least the following fields: message identifier field672′ (4 bits) containing message identifier672; sequence number field674′ (8 bits) containing sequence number674; first reply field676′ (1 bit) containing first reply676indicating whether the reply is to accept or decline; second reply field678′ (2 bits) containing second reply678providing a reply to the immediately previous message630; third reply field680′ (2 bits) containing third reply680providing a reply to the message630transmitted previous to the immediately previous message630; and padding field682′. If module602did not receive an immediately previous ACK634, second reply678acts as a retransmission of first reply676from the previous ACK634. If module602did not receive an immediately previous ACK634or the ACK634prior to the immediately previous ACK634, second reply678acts as a retransmission of first reply676from the immediately previous ACK634and third reply680acts as a retransmission of reply first676from the ACK634prior to the immediately previous ACK634. To provide these features, module602stores the sequence number674of the last ACK634that it receives, or equivalently the sequence number674of the next ACK634that it expects. When it receives an ACK634, gaps in the sequence number674can be detected and information read from the retransmitted information. Module604is required to store its previous ACK information, including whether an “invalid” flag was sent, to enable module604to retransmit information contained in previous ACKs634.

If sequence evaluation unit646at module604determines based on sequence numbers664that it did not receive at least one previously transmitted message630, acknowledgement unit648indicates this in the appropriate second reply678or third reply680. In this case, as before, sequence evaluation unit646module604determines that a gap occurred based on sequence numbers664received. Sequence evaluation unit644at module602similarly determines that a gap occurred based on sequence numbers674received and reads the “invalid” flag that was transmitted in one or both of second reply678and third reply680. Module602resynchronizes itself with module604based on the indication of which messages630were lost. Synchronization may be achieved by such means as discarding information relating to lost messages630or retransmitting lost messages630. Module602is required to store its previous message information if it is to retransmit previously transmitted messages630.

In a first scenario, a normal, successful series of messages630and ACKs634are exchanged between modules602and604. At time702, module602generates and transmits message630(29) to module604over communications link606, indicated by arrow632(29). Message630(29) comprises a sequence number664(29) and a message payload666(29) which contains the instructions for module604. Message630(29) arrives at module604. Sequence evaluation unit646at module604reads sequence number664(29) and determines that no message gap has occurred.

At time706, acknowledgement unit648generates ACK634(29) and populates it with sequence number674(29) and replies676(29),678(29),680(29). First reply676(29) contains the acknowledgement response for message630(29) (indicated by “A29”); second reply678(29) contains the acknowledgement response for the previous message, message630(28) (not shown) (indicated by “A28”); third reply68(29) contains the acknowledgement response for the next previous message, message630(27) (not shown) (indicated by “A27”). Module604transmits ACK634(29) to module602, indicated by arrow636(29), which arrives at time710. Module602receives ACK634(29) and sequence evaluation unit644reads sequence number674(29) and determines that no message gap has occurred.

A second scenario illustrates an example of a message630being lost en route to module604. At time704, module602generates and transmits message630(30) over communications link606, indicated by arrow632(30). Fault642prevents message630(30) from arriving at module604. Device600deals with this fault642in a similar manner as that of device300, providing the “invalid” flag in second reply678(31) as part of ACK634(31) to the next message630(31). Module604generates a value for sequence number674(31) that indicates a gap in the sequence of ACKs634. This is most easily achieved by copying the value for sequence number664(31) from message630(31).

Sequence evaluation unit644at module602checks for gaps in the sequence of sequence numbers674received in ACKs634. Sequence evaluation unit644determines that a gap has occurred and the last ACK634(30) was not received. Accordingly, module602reads the “invalid” flag from second reply678(31) which indicates that ACK634(30) was not generated since message634(30) was not received by module604. Module602then resynchronizes itself with module604. In this example, module602retransmits the processing parameters from message630(30) in a message630(33), indicated by “M30” in message payload666(33) which was originally transmitted in message payload666(30) of message630(30). It will be appreciated that module602may resynchronize itself with module604by other means including discarding information relating to message payload666(30).

It will also be appreciated that modules602and604can be adapted to track loss of a number of consecutive messages630, as the illustrated embodiment of ACK634is able to indicate the loss of two consecutive messages630to module604.

A third scenario illustrates an example of a series of ACKs634being lost en route to module602. At time708and time714, module602generates and transmits messages630(32) and630(33), respectively, to module604. Sequence evaluation unit646of module604determines that no message gap has occurred and acknowledgement unit648generates ACKs634(32) and634(33), respectively. Module604transmits these ACKS634over communications link606, indicated by arrows636(32) and636(33), respectively. Faults640(i) and640(ii) prevent ACKs634(32) and634(33) from arriving at module602. At time716, module602generates and transmits message630(34) to module604over communications link606, indicated by arrow632(34). Message630(34) comprises a sequence number664(34) and a message payload666(34) which contains processing parameters for module604. Message630(34) arrives at module604. Sequence evaluation unit646determines again that no message gap has occurred. At time720, acknowledgement unit648generates ACK634(34) and populates it with sequence number674(34) and replies676(34),678(34),680(34). First reply676(34) contains the acknowledgement response for message630(34) (indicated by “A34”); second reply678(34) contains the acknowledgement response for the previous message630(33) (indicated by “A33”); and third reply680(34) contains the acknowledgement response for the next previous message630(34) (indicated by “A32”). Module604transmits ACK634(34) to module602, indicated by arrow636(34), which arrives at time724.

Sequence evaluation unit644of module602checks for a gap in the sequence of sequence numbers674received. Sequence evaluation unit644determines that a gap has occurred and that the last two ACKs634(32) and634(33) were not received. Accordingly, module602reads second reply678(34) and third reply680(34) from ACK634(34). Module602is therefore provided with acknowledgement responses to messages630(32) and630(33) that were lost due to faults640(i) and640(ii), respectively.

It will be appreciated that ACK634may be further extended to carry more than three acknowledgement responses to provide support for the loss of more than two consecutive messages630or ACKs634.

In other embodiments, it will be appreciated that the sequence number system may be replaced with any ordered set of codes. Further, in other embodiments, ACKs may be populated with a sequence number of a previously responded to message in any one of the already described reply fields. In such an embodiment, the ACK contains two sequence numbers, thereby allowing direct determination of lost packets by exemplary modules302,602by simply extracting and comparing the values of the two sequence numbers. In still other embodiments, modules304and604may be modified to report in the ACK directly when there is a loss of a sent packet from modules302and602. Therein, modules304and604would track sequence numbers from received messages and determine whether gaps in sequence numbers are present. Upon detection of any such gap, a special message may be sent to modules302and602to immediately notify them of the missing message.

The embodiments described above may be implemented in software, firmware or hardware modules which have access to a cell stream and the required functionality to analyze the cell stream and insert data therein. Such extraction analysis and insertion techniques may incorporate techniques already known in the art, but having the additional functionality defined herein.

It is noted that those skilled in the art will appreciate that various modifications of detail may be made to the present embodiment, all of which would come within the scope of the invention.