Sign In to Follow Application
View All Documents & Correspondence

Crisscross Cancellation Protocol

Abstract: Technologies, systems, and methods for ordered message delivery that avoid message races or crisscrosses between communicating nodes. For example, if Node A sends message 3 towards Node B and, shortly thereafter, Node B sends message X to Node A, Node A would like to know whether or not message X reflects Node B"s state after receiving message 3. If Node B received message 3 prior to sending message X, then proper state may be maintained between the nodes. But if messages 3 and X crisscrossed, or if message 3 was never properly received by Node B, then the state between the nodes may be corrupt. Technologies, systems, and methods are provided to avoid such corruption.

Get Free WhatsApp Updates!
Notices, Deadlines & Correspondence

Patent Information

Application #
Filing Date
09 February 2010
Publication Number
32/2010
Publication Type
INA
Invention Field
COMMUNICATION
Status
Email
Parent Application

Applicants

MICROSOFT CORPORATION
ONE MICROSOFT WAY, REDMOND, WASHINGTON 98052-6399

Inventors

1. ADYA, ATUL
C/O MICROSOFT CORPORATION, INTERNATIONAL PATENTS, ONE MICROSOFT WAY, REDMOND, WASHINGTON 98052-6399
2. WOLMAN, ALASTAIR
C/O MICROSOFT CORPORATION, INTERNATIONAL PATENTS, ONE MICROSOFT WAY, REDMOND, WASHINGTON 98052-6399
3. DUNAGAN, JOHN D
C/O MICROSOFT CORPORATION, INTERNATIONAL PATENTS, ONE MICROSOFT WAY, REDMOND, WASHINGTON 98052-6399

Specification

BACKGROUND [0001] Distributed systems, such as networked computers, may need to know each other's state during communications. This typically requires that two systems communicate sequentially rather than simultaneously. If both systems send messages to each other simultaneously (or non-sequentially) resulting in crisscrossed messages, a race condition can develop which can lead to divergent and corrupted state information. SUMMARY [0002] The following presents a simplified summary of the disclosure in order to provide a basic understanding to the reader. This summary is not an extensive overview of the disclosure and it does not identify key/critical elements of the invention or delineate the scope of the invention. Its sole purpose is to present some concepts disclosed herein in a simplified form as a prelude to the more detailed description that is presented later. 10003] The present examples provide technologies for ordered message delivery that avoid message races or crisscrosses between communicating nodes. For example, if Node A sends message 3 towards Node B and, shortly thereafter. Node B sends message X to Node A, Node A would like to know whether or not message X reflects Node B's state after receiving message 3. If Node B received message 3 prior to sending message X, then proper state may be maintained between the nodes. But if messages 3 and X crisscrossed, or if message 3 was never properly received by Node B, then the state between the nodes may be corrupt. Technologies, systems, and methods are provided to avoid such corruption. [0004] Many of the attendant features will be more readily appreciated as the same become better understood by reference to the following detailed description considered in connection with the accompanying drawings. DESCRIPTION OF THE DRAWINGS 10005] The present description will be better understood from the following detailed description considered in connection with the accompanying drawings, wherein: [0006] FIG. 1 is a block diagram showing two example crisscross cancellation protocol-enabled nodes that are communicatively coupled. [0007] FIG. 2 is a block diagram showing an example crisscross cancelation protocol ("C3P") message including an example C3P header. [0008] FIG. 3 is a block diagram showing an example crisscross cancellation protocol state diagram. [00091 FIG. 4 is a block diagram showing an example method for initializing a crisscross cancellation protocol instance and for sending a message. [0010] FIG. 5 is a block diagram showing an example method for processing a crisscross cancellation protocol message and detecting a message crisscross. [0011 ] FIG. 6 is a timing diagram showing an example of ordered message transmissions between two example nodes. [0012] FIG. 7 is a block diagram showing an example method for processing a crisscross cancellation protocol message while in a race fix state. [0013] FIG. 8 is a timing diagram, an extension of the timing diagram of FIG. 6, showing an example of a message crisscross and a subsequent recovery. [0014] FIG. 9 is a block diagram showing an example computing environment in which the technologies described herein may be implemented. [0015] Like reference numerals are used to designate like parts in the accompanying drawings. DETAILED DESCRIPTION [0016] The detailed description provided below in connection with the accompanying drawings is intended as a description of the present examples and is not intended to represent the only forms in which the present examples may be constructed or utilized. The description sets forth at least some of the functions of the examples and/or the sequence of steps for constructing and operating examples. However, the same or equivalent functions and sequences may be accomplished by different examples. [0017] Although the present examples are described and illustrated herein as being implemented in a computing and networking environment, the environment described is provided as an example and not a limitation. As those skilled in the art will appreciate, the present examples are suitable for application in a variety of different types of computing and networking environments. [GOT 8] FIC. 1 is a block diagram showing two example crisscross cancellation protocol-enabled nodes that are communicatively coupled. Node A and Node B are coupled as indicated by line 190, which may be any type of coupling, connection, communications link, network, or the like. Each node includes an example application, such as applications 110a and 110b, which may be any program, system, device, software, device driver, firmware, or the like that may benefit from a crisscross cancellation protocol. Applications 11 Oa and 11 Ob may or may not be the same. Applications 110a and 1 lOb typically send and receive messages via a crisscross cancellation protocol ("C3P") layer, such as C3Ps 120a and 120b. The crisscross cancellation protocol maintains appropriate state information via state variables such as variables 121a-124a. A crisscross cancellation protocol typically makes use of a transport, such as transports 130a and 130b, to send and receive C3P messages over some form of communications link. [0019] The state fields or variables typically maintain the state of the C3P. Each C3P module or instance of the C3P includes: a counter, such as counter state variables 121aand 121b; a nonce, such as nonce state variables 122aand 122b; a remote counter, such as remote counter state variables 123a and 123b; and a remote nonce, such as remote nonce state variables 124a and 124b. In one example, each of these state variables is a 64-bit number. [0020] The nonce state variable (i.e., 122a) typically uniquely identifies the current C3P session. A C3P session is typically established when a C3P layer is initialized. A new instance of the C3P layer is typically established each time a C3P-enabled node needs to communicate with a new C3P-enabled node (for example, one that it has not previously communicated with). Generally, each time a C3P layer is initialized a new nonce is generated. 10021 ] The remote nonce state variable (i.e., 124a) Is typically used to record the nonce of a remote node (that is, the remote node's C3P layer) as Indicated by the header of the last valid C3P message received from the remote node. [0022] The term "nonce" as used herein refers to a cryptographic random nonce, a counter or random or pseudo-random number that is unlikely to be reused. Such a nonce is generally used by C3P to identify each session uniquely from any other session. Thus, in the event of a node crash or the like, the next time the C3P is initialized a new and unique nonce is established indicating a new and unique C3P session. [0023] The counter state variable (i.e., 121a) is typically a monotonically increasing variable that increments by one for each message sent, or a value identifying the last message sent. In one example, the counter is incremented each time a message is sent. [0024] The remote counter state variable (i.e., 123a) is typically used to record the counter of a remote node (that is, the remote node's C3P layer) as indicated by the header of the last valid C3P message received from the remote node. [0025] In general, an application passes a message to be sent to another node down to the C3P layer, the C3P layer typically adds a C3P header (as described in connection with FIC. 1), buffers the message in a send buffer, and passes the message to the transport which sends the message over the network to the target node. Each C3P layer typically buffers a single outgoing message in a send buffer. [0026] Upon receiving a valid C3P message, the message is stored in a C3P receive buffer after the target node's transport passes the C3P message up to the C3P layer. In one example, the receive buffer stores one or more incoming messages. The C3P layer verifies the messages are valid, removes the C3P header, and passes the message up to a corresponding application. In one example, once the application is done processing the received message, it instructs the C3P layer to empty this message from the receive buffer. In this example, the C3P layer will not send a message until the receive buffer is empty, as doing so would be equivalent to a message crisscross, with the application sending a new message without having processed a previously received message. [0027] The two communicating C3P layers interoperate to provide ordered message delivery for the applications and to avoid message races or crisscrosses. The term "message race" or "message crisscross" or "crisscross" as used herein refers to the situation when a first node sends a message to a second node and, before the second node receives the message from the first node, the second node sends a message to the first node. Such a situation results in a message crisscross or message race condition. This situation is described in more detail in connection with FIG. 8. [0028] As used herein, the term "node" refers to any computer system, device, or process that is uniquely addressable, or otherwise uniquely identifiable, over a network or the like, and that is operable to communicate with other nodes over the network. For example, and without limitation, a node may be a personal computer, a server computer, a hand-held or laptop device, a tablet device, a multiprocessor system, a microprocessor-based system, a set top box, a consumer electronic device, a network PC, a minicomputer, a mainframe computer, a uniquely-identifiable software application, or the like. One example of a node such as Node A and Node B, in the form of computer system 900, is set forth herein below with respect to FIG. 9. [0029] FIG. 2 is a block diagram showing an example crisscross cancelation protocol ("C3P") message 200 including an example C3P header 210. The C3P message 200 is typically comprised of an application message (a message, packet, data, or the like provided by an application) in the message field 220 and a C3P header 210. In one example, C3P header 210 includes state information in four fields: nonce 211, remote nonce 212, counter 213, and remote counter 214. In this example, the state values are 64-bit numbers. Nonce 211 and counter 213 values are typically taken from the sending C3P's corresponding state variables each time a message is sent. Remote nonce 212 and remote counter 214 values are typically taken from the sending C3P's remote nonce and remote counter state variables, the values of which are typically obtained from the header of the last valid C3P message received from the remote node. A C3P ping message is a version of C3P message 200 that does not include application message 220. [0030] FIG. 3 is a block diagram showing an example crisscross cancellation protocol state diagram 300. A particular C3P instance generally transitions between two states: C3P normal state 310 and C3P race fix state 320. Once the C3P instance is successfully initialized, it typically enters C3P normal state 310. Each time a normal (non-C3P ping) C3P message is sent, the C3P transitions bacl< into the C3P normal state as indicated by arrow 330. The C3P remains in the C3P normal state 330 until a C3P message crisscross is detected. If a C3P message crisscross is detected (as described in connection with FIG. 5), the C3P transitions into the C3P race fix state 320 as indicated by arrow 340. The C3P remains in the C3P race fix state 320 until a C3P message is received that is not a message crisscross. Each time any C3P message is received that has crisscrossed with another message , the C3P transitions back into the C3P race fix state 320 as indicated by arrow 350. When an in-order C3P message (either a C3P ping or a C3P message that does include an application message) is received or other appropriate conditions are met as described in connection with FIG. 7, the C3P transitions into the C3P normal state 310 as indicated by arrow 360. [0031] FIG. 4 is a block diagram showing an example method 400 for initializing a crisscross cancellation protocol instance and for sending a message. C3P initialization includes the steps indicated by blocks 410 and 420. Each time a hosting node starts a C3P instance the initialization steps are performed. This generally includes each time the node starts a new C3P instance to communicate with a particular new remote node, and each time the node restarts during a C3P session, such as a reboot or a crash restart. [0032] Block 410 indicates initializing the C3P's nonce state variable, as described in connection with FIG. 1. This is typically done by generating a new nonce value. In one example, a nonce is generated as a random number which Is typically different than a previous nonce. Once the nonce state variable is initialized, method 400 typically continues at block 420. [0033] Block 420 indicates initializing the C3P's counter state variable, as described in connection with FIG. 1. This is typically done by generating a new counter value. In one example, the counter is initialized to zero (0). Once the counter state variable is initialized, C3P initialization is typically complete and method 400 typically continues at block 430. [0034] Block 430 typically indicates waiting for an application message to send. Once the C3P is initialized, it waits for a message to be sent. Messages are typically provided by an application or the like. Once a message is available to be sent, method 400 typically continues at block 440. 10035] Block 440 typically indicates incrementing the counter state variable, as described in connection with FIG. 1. The counter state variable may be incremented by one or more. Once the counter state variable has been incremented, method 400 typically continues at block 450. [0036] Block 450 typically indicates formatting and sending a C3P message. Formatting is typically performed by adding a C3P header to the message provided by the application (see description for block 430). The C3P header and message are typically constructed as described in connection with FIG. 2. In one example, the C3P message is sent by providing it to a transport as described in connection with FIG. 1. Once the message is sent, method 400 typically continues at block 430. [0037] FIG. 5 is a block diagram showing an example method 500 for processing a crisscross cancellation protocol message and detecting a message crisscross. Method 500 is typically performed by a C3P instance receiving a C3P message while in the C3P normal state as described in connection with FIG. 3. In general, method 500 compares state information in the incoming message's header with state information stored in the C3P instance receiving the message, as described in connection with FIG. 1. [0038] Block 510 typically indicates receiving a C3P message. Such a message typically includes a C3P header including state information as described in connection with FIG. 2. Once a message is received, method 500 typically continues at block 520. [00391 Block 520 typically indicates determining if the nonce value of the incoming message's header is correct. In one example, the value in the nonce field of the incoming message's header (i.e., item 211, FIG. 2) is compared with the value stored in the remote nonce field of the receiving C3P instance's state information (i.e., item 124a, FIG. 1). If the two values do not match (e.g., are not equal), then the receiving C3P instance assumes that the sending C3P instance has crashed since the last message received. If the two values do not match, method 500 typically continues at block 530. Otherwise, method 500 typically continues at block 550. [0040] Block 530 typically indicates invalidating the receiving C3P instance's state information. In one example this is done by setting each of the remote state values (i.e., items 123a-124a, FIG. 1) to zero (0). Once the state information has been invalidated, the application is typically made aware that the remote C3P instance has experienced a crash, and then method 500 typically continues at block 540. [0041] Block 540 typically indicates setting the receiving C3P instance's remote nonce field (i.e., item 124a, FIG. 1) to the value in the nonce field of the incoming message (i.e., item 211, FIG. 2). Once the remote nonce state value is set, method 500 continues at block 550. [0042] Block 550 typically indicates determining if the counter value of the incoming message's header is correct. In one example, the value in the counter field of the incoming message's header (i.e., item 213, FIG. 2) is strictly greater than the value stored in the remote counter field of the receiving C3P instance's state information (i.e., item 123a, FIG. 1). If the incoming counter is not greater, then the receiving C3P instance assumes that it has already received the incoming message or a later message. If the incoming counter is not greater, then method 500 typically continues at block 552. Otherwise, method 500 typically continues at block 560. [0043] Block 5 52 typically indicates dropping the incoming message because it was either already received or because a later message was already received (see block 550). Once the incoming message is dropped, method 500 typically continues at block 510. [0044] Block 560 typically indicates setting the receiving C3P instance's remote counter field (i.e., item 123a, FIG. 1) to the value in the counter field of the incoming message (i.e., item 213, FIG. 2). Once the remote counter state value is set, method 500 continues at block 570. [0045] Block 570 typically indicates determining if the remote counter value and remote nonce value of the incoming message's header are correct, in one example, the value in the remote counter field of the incoming message's header (i.e., item 214, FIG. 2) matches (e.g., is equal to) the value stored in the counter field of the receiving C3P instance's state information (i.e., item 121a, FIC. 1) and the value in the remote nonce field of the incoming message's header (i.e., item 212, FIC. 2) is either zero or matches (e.g., is equal to) the value stored in the nonce field of the receiving C3P instance's state information (i.e., item 122a, FIC. 1). If the incoming remote counter does not match, or if the incoming remote nonce is neither zero nor matching, then the receiving C3P instance assumes that one or more messages have crisscrossed. If the incoming remote counter is not matching, or if the incoming remote nonce is neither zero nor matching, then method 500 typically continues at block 572. Otherwise, method 500 typically continues at block 580. [0046] Block 572 typically indicates the receiving C3P instance entering the C3P race fix state as described in connection with FIC. 3. Entering the C3P race fix state typically includes dropping the incoming message. Processing while in the C3P race fix state proceeds as described in connection with FIG. 7. [0047] Block 580 typically describes passing the incoming message up to a receiving application. At this point the incoming message is determined to be valid, in one example, the C3P header is stripped from the message before it is passed up. Once the message is passed, method 500 typically continues at block 510. [0048] FIC. 6 is a timing diagram 600 showing an example of ordered message transmissions between two example nodes. Arrow 610 is a timeline for Node A and arrow 611 is a corresponding timeline for Node B. State block 612 shows the example initial state of Node A and state block 613 shows the example initial state of Node B at the beginning of the timelines. State blocks 612, 613, and the like, and their included fields, correspond to those described in connection with FIC. 1. In particular, field 612a corresponds to field 121a of FIC. 1; field 612b corresponds to field 123a of FIC. 1; field 6112c corresponds to field 122a of FIC. 1; and field 612d corresponds to field 124a of FIC. 1. The values for the various state fields are examples only and may be any appropriate values in practice. Each node is typically initialized to the C3P normal state as described in connection with FIC. 3 and typically operates according to method 500 10049] As shown in tables A and B, examples of the Initial states of Nodes A and B , each node knows its own nonce, but not the other node's nonce (as indicated by the initial value of zero shown in hexadecimal (0x0) in the Remote Nonce fields). Further, in their initial states, each node knows its own counter (which may be initialized to zero as shown), but not the other node's counter (as indicated by the initial value of zero (0) in the remote counter fields). Nonce fields may be initialized with random values. In other examples, initial values other than zero may be used and/or initial values of the other node may be known. [0050] Timing diagram 600 shows Node B sending a first message to Node A, as indicated by arrow and message header 620. The message header includes the nonce value of Node B (N=98), the nonce of node A (RN = 0, currently unknown by Node B), the incremented counter value of Node B (C=l 1, incremented from C=10 of state 613 prior to sending message 620), and the counter value of Node A (RC=0, currently unknown by Node B). State block 61 5 indicates the state of Node B after sending message 620. [0051] Upon receiving message 620, Node A updates its state with the information from the header of message 620, as indicated by state block 614. At this point. Node A knows the nonce of Node B (RN=98) and the message counter of Node B (RC=11), and state 614 is updated to indicate such. Node A may know message 620 is a first message from Node B because Node A's state information for Node B (remote nonce and remote counter) was set to tlie initial state (zero) when message 620 was received. [0052] Per timing diagram 600, Node A now sends a message to Node B, as indicated by arrow and message header 630. The message header includes the nonce value of Node A (N=l 2), the incremented counter value of Node A (C=l, incremented from C=0 of state 612 prior to sending message 630), the nonce value of node B (RN=98, known by Node A via message 620), and the counter value of Node B (R=l 1, known by Node A via message 620). State block 616 indicates the state of Node A after sending message 630. [0053] Upon receiving message 630, Node B updates its state with the information from the header of message 630, as indicated by state block 617. At this point. Node B knows the nonce of Node A (RN=12) and the message counter of Node A (RC=1), and state 61 7 is updated to indicate such. Node B may know message 630 is a first message from Node A because Node B's state information for Node A (remote nonce and remote counter) was set to the initial state (zero) when message 630 was received. [0054] Per timing diagram 600, Node B now sends a second message to Node A, as indicated by arrow and message header 640. The message header includes the nonce value of Node B (N=98), the incremented counter value of Node B (C=l 2, incremented from C=l 1 of state 617 prior to sending message 640), the nonce value of Node A (RN=12, known by Node B via message 630) and the counter value of Node A (RC=1, known by Node B via message 630). State block 619 indicates the state of Node B after sending message 640. [0055] Upon receiving message 640, Node A determines that its state values for Node B (remote nonce and remote counter) are not set to the initial values. Therefore, Node A verifies that the nonce value in the message header 640 from Node B (N=98) matches that of its state 616 for Node B (RN=98). If there is a match, then Node A knows that the C3P session of Node B has not reset since the last message received from Node B. Node A further verifies that the counter value in message header 640 from Node B (C= 12) is greater than that of its state 616 for Node B (RC= 11). If the counter of the incoming message is greater tlian that of Node A's state for Node B, then Node A knows that message 640, or a later message, has not already been received. Node A further verifies that the remote counter value in message header 640 from Node B (RC=1) matches that of its state 616 for Node A's counter (C=l). If there is a match, then Node A l

Documents

Application Documents

# Name Date
1 779-CHENP-2010-AbandonedLetter.pdf 2018-04-23
1 abs 779-chenp-2010 abstract 09-02-2010.jpg 2010-02-09
2 779-chenp-2010 pct search report 09-02-2010.pdf 2010-02-09
2 779-CHENP-2010-FER.pdf 2017-10-06
3 779-chenp-2010 pct 09-02-2010.pdf 2010-02-09
3 779-CHENP-2010 FORM-18 08-09-2011.pdf 2011-09-08
4 779-chenp-2010 form-2 09-02-2010.pdf 2010-02-09
4 779-CHENP-2010 CORRESPONDENCE OTHERS 08-09-2011.pdf 2011-09-08
5 779-chenp-2010 drawings 09-02-2010.pdf 2010-02-09
5 779-chenp-2010 form-3 08-07-2010.pdf 2010-07-08
6 779-chenp-2010 description(complete) 09-02-2010.pdf 2010-02-09
6 779-chenp-2010 power of attorney 09-02-2010.pdf 2010-02-09
7 779-chenp-2010 claims 09-02-2010.pdf 2010-02-09
7 779-chenp-2010 correspondence others 09-02-2010.pdf 2010-02-09
8 779-chenp-2010 abstract 09-02-2010.pdf 2010-02-09
8 779-chenp-2010 form-1 09-02-2010.pdf 2010-02-09
9 779-chenp-2010 form-3 09-02-2010.pdf 2010-02-09
9 779-chenp-2010 form-5 09-02-2010.pdf 2010-02-09
10 779-chenp-2010 form-3 09-02-2010.pdf 2010-02-09
10 779-chenp-2010 form-5 09-02-2010.pdf 2010-02-09
11 779-chenp-2010 form-1 09-02-2010.pdf 2010-02-09
11 779-chenp-2010 abstract 09-02-2010.pdf 2010-02-09
12 779-chenp-2010 correspondence others 09-02-2010.pdf 2010-02-09
12 779-chenp-2010 claims 09-02-2010.pdf 2010-02-09
13 779-chenp-2010 power of attorney 09-02-2010.pdf 2010-02-09
13 779-chenp-2010 description(complete) 09-02-2010.pdf 2010-02-09
14 779-chenp-2010 form-3 08-07-2010.pdf 2010-07-08
14 779-chenp-2010 drawings 09-02-2010.pdf 2010-02-09
15 779-CHENP-2010 CORRESPONDENCE OTHERS 08-09-2011.pdf 2011-09-08
15 779-chenp-2010 form-2 09-02-2010.pdf 2010-02-09
16 779-CHENP-2010 FORM-18 08-09-2011.pdf 2011-09-08
16 779-chenp-2010 pct 09-02-2010.pdf 2010-02-09
17 779-chenp-2010 pct search report 09-02-2010.pdf 2010-02-09
17 779-CHENP-2010-FER.pdf 2017-10-06
18 abs 779-chenp-2010 abstract 09-02-2010.jpg 2010-02-09
18 779-CHENP-2010-AbandonedLetter.pdf 2018-04-23

Search Strategy

1 SearchQueries_06-10-2017.pdf