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 |