Congestion management and latency prediction in CSMA media
First Claim
Patent Images
1. A non-transitory computer-readable medium comprising executable program code that when executed by a processing element implements a method to determine data-transmission congestion between a first network node and a second network node, the method comprising:
- monitoring a series of received and dropped messages communicated between the first network node and the second network node, wherein the received messages are associated with a first bit and the dropped messages are associated with a second bit;
generating a log of data as each new message is monitored, wherein the log of data is an ordered series of the first bits and the second bits ordered from a current bit associated with a current message to an oldest bit associated with an oldest message, wherein a first new bit or a second new bit associated with the new monitored message is added to the log of data as the current bit, and wherein the oldest bit is removed from the log of data;
dividing, as each new message is monitored, the log of data into a first log portion containing bits associated with messages monitored during a first time period and a second log portion containing bits associated with messages monitored during a second time period, wherein the second time period is earlier than the first time period;
determining, as each new message is monitored, a first number, wherein the first number corresponds to a number of the first bits in the first log portion;
determining, as each new message is monitored, a second number, wherein the second number corresponds to a number of the first bits in the second log portion;
if the first number is at least equal to the second number by a predetermined criterion, continuing to generate the log of data as a next message is provided; and
if the first number is less than the second number by the predetermined criterion, discarding the second log portion and continuing to generate the log of data using a new number of bits as the next message is provided, wherein the new number of bits corresponds to the number of the bits in the first log portion,wherein the first number equals the number of the first bits in the first log portion, andwherein the second number equals the number of the first bits in the second log portion.
3 Assignments
0 Petitions
Accused Products
Abstract
A facility for congestion management and latency prediction is described. In various embodiments, the facility sums a series of fractional transmission delays wherein each fractional transmission delay is measured as a probability of a failed transmission attempt multiplied by the cost of the failed transmission attempt, and provides the sum.
18 Citations
10 Claims
-
1. A non-transitory computer-readable medium comprising executable program code that when executed by a processing element implements a method to determine data-transmission congestion between a first network node and a second network node, the method comprising:
-
monitoring a series of received and dropped messages communicated between the first network node and the second network node, wherein the received messages are associated with a first bit and the dropped messages are associated with a second bit; generating a log of data as each new message is monitored, wherein the log of data is an ordered series of the first bits and the second bits ordered from a current bit associated with a current message to an oldest bit associated with an oldest message, wherein a first new bit or a second new bit associated with the new monitored message is added to the log of data as the current bit, and wherein the oldest bit is removed from the log of data; dividing, as each new message is monitored, the log of data into a first log portion containing bits associated with messages monitored during a first time period and a second log portion containing bits associated with messages monitored during a second time period, wherein the second time period is earlier than the first time period; determining, as each new message is monitored, a first number, wherein the first number corresponds to a number of the first bits in the first log portion; determining, as each new message is monitored, a second number, wherein the second number corresponds to a number of the first bits in the second log portion; if the first number is at least equal to the second number by a predetermined criterion, continuing to generate the log of data as a next message is provided; and if the first number is less than the second number by the predetermined criterion, discarding the second log portion and continuing to generate the log of data using a new number of bits as the next message is provided, wherein the new number of bits corresponds to the number of the bits in the first log portion, wherein the first number equals the number of the first bits in the first log portion, and wherein the second number equals the number of the first bits in the second log portion.
-
-
2. A non-transitory computer-readable medium comprising executable program code that when executed by a processing element implements a method to determine data-transmission congestion between a first network node and a second network node, the method comprising:
-
monitoring a series of received and dropped messages communicated between the first network node and the second network node, wherein the received messages are associated with a first bit and the dropped messages are associated with a second bit; generating a log of data as each new message is monitored, wherein the log of data is an ordered series of the first bits and the second bits ordered from a current bit associated with a current message to an oldest bit associated with an oldest message, wherein a first new bit or a second new bit associated with the new monitored message is added to the log of data as the current bit, and wherein the oldest bit is removed from the log of data; dividing, as each new message is monitored, the log of data into a first log portion containing bits associated with messages monitored during a first time period and a second log portion containing bits associated with messages monitored during a second time period, wherein the second time period is earlier than the first time period; determining, as each new message is monitored, a first number, wherein the first number corresponds to a number of the first bits in the first log portion; determining, as each new message is monitored, a second number, wherein the second number corresponds to a number of the first bits in the second log portion; if the first number is at least equal to the second number by a predetermined criterion, continuing to generate the log of data as a next message is provided; and if the first number is less than the second number by the predetermined criterion, discarding the second log portion and continuing to generate the log of data using a new number of bits as the next message is provided, wherein the new number of bits corresponds to the number of the bits in the first log portion, wherein the first number equals a number of the second bits in the first log portion, and wherein the second number equals a number of the second bits in the second log portion.
-
-
3. A method to determine data-transmission congestion between a first network node and a second network node, the method comprising:
-
monitoring a series of new messages between the first network node and the second network node, wherein received messages are associated with a first bit and dropped messages are associated with a second bit; generating, in response to monitoring each new message, a log of data comprising a total number of bits corresponding to a predefined number of monitored messages, wherein the log of data is an ordered series of the first and second bits ordered from a current bit associated with a current message to an oldest bit associated with an oldest message, wherein a new bit associated with the new monitored message is added as the current bit into the log of data, and wherein a bit associated with the oldest message is removed from the log of data; dividing, in response to monitoring each new message, the log of data into a first log portion containing a first number of bits associated with a first number of messages monitored during a first time period and a second log portion containing a second number of bits associated with a second number of messages monitored during a second time period, wherein the second time period is earlier than the first time period, and wherein the first number of bits associated with the first number of messages and the second number of bits associated with the second number of messages equals the total number of bits; determining, in response to monitoring each new message, a first number corresponding to a number of the first bits in the first log portion; determining, as each new message is monitored, a second number corresponding to a number of the first bits in the second log portion; comparing, as each new message is monitored, the first number and the second number; if the first number is at least equal to the second number by a predetermined criterion, continuing to generate the log of data using the total number of bits as a next message is monitored; and if the first number is less than the second number by the predetermined criterion, discarding the second log portion and continuing to generate the log of data using a new number of bits as the next message is monitored, wherein the new number of bits corresponds to the first number of bits in the first log portion, wherein the first time period and the second time period correspond to a time period in which the predefined number of monitored messages are monitored.
-
-
4. A method to determine data-transmission congestion between a first network node and a second network node, the method comprising:
-
monitoring a series of new messages between the first network node and the second network node, wherein received messages are associated with a first bit and dropped messages are associated with a second bit; generating, in response to monitoring each new message, a log of data comprising a total number of bits corresponding to a predefined number of monitored messages, wherein the log of data is an ordered series of the first and second bits ordered from a current bit associated with a current message to an oldest bit associated with an oldest message, wherein a new bit associated with the new monitored message is added as the current bit into the log of data, and wherein a bit associated with the oldest message is removed from the log of data; dividing, in response to monitoring each new message, the log of data into a first log portion containing a first number of bits associated with a first number of messages monitored during a first time period and a second log portion containing a second number of bits associated with a second number of messages monitored during a second time period, wherein the second time period is earlier than the first time period, and wherein the first number of bits associated with the first number of messages and the second number of bits associated with the second number of messages equals the total number of bits; determining, in response to monitoring each new message, a first number corresponding to a number of the first bits in the first log portion; determining, as each new message is monitored, a second number corresponding to a number of the first bits in the second log portion; comparing, as each new message is monitored, the first number and the second number; if the first number is at least equal to the second number by a predetermined criterion, continuing to generate the log of data using the total number of bits as a next message is monitored; and if the first number is less than the second number by the predetermined criterion, discarding the second log portion and continuing to generate the log of data using a new number of bits as the next message is monitored, wherein the new number of bits corresponds to the first number of bits in the first log portion, wherein the first and second log portions comprise two halves of the log of data.
-
-
5. A method to determine data-transmission congestion between a first network node and a second network node, the method comprising:
-
monitoring a series of new messages between the first network node and the second network node, wherein received messages are associated with a first bit and dropped messages are associated with a second bit; generating, in response to monitoring each new message, a log of data comprising a total number of bits corresponding to a predefined number of monitored messages, wherein the log of data is an ordered series of the first and second bits ordered from a current bit associated with a current message to an oldest bit associated with an oldest message, wherein a new bit associated with the new monitored message is added as the current bit into the log of data, and wherein a bit associated with the oldest message is removed from the log of data; dividing, in response to monitoring each new message, the log of data into a first log portion containing a first number of bits associated with a first number of messages monitored during a first time period and a second log portion containing a second number of bits associated with a second number of messages monitored during a second time period, wherein the second time period is earlier than the first time period, and wherein the first number of bits associated with the first number of messages and the second number of bits associated with the second number of messages equals the total number of bits; determining, in response to monitoring each new message, a first number corresponding to a number of the first bits in the first log portion; determining, as each new message is monitored, a second number corresponding to a number of the first bits in the second log portion; comparing, as each new message is monitored, the first number and the second number; if the first number is at least equal to the second number by a predetermined criterion, continuing to generate the log of data using the total number of bits as a next message is monitored; and if the first number is less than the second number by the predetermined criterion, discarding the second log portion and continuing to generate the log of data using a new number of bits as the next message is monitored, wherein the new number of bits corresponds to the first number of bits in the first log portion, wherein each first bit is one of a first binary number that indicates that the message was received and each second bit is a second binary number that indicates that the message was dropped.
-
-
6. A method to determine data-transmission congestion between a first network node and a second network node, the method comprising:
-
monitoring a series of new messages between the first network node and the second network node, wherein received messages are associated with a first bit and dropped messages are associated with a second bit; generating, in response to monitoring each new message, a log of data comprising a total number of bits corresponding to a predefined number of monitored messages, wherein the log of data is an ordered series of the first and second bits ordered from a current bit associated with a current message to an oldest bit associated with an oldest message, wherein a new bit associated with the new monitored message is added as the current bit into the log of data, and wherein a bit associated with the oldest message is removed from the log of data; dividing, in response to monitoring each new message, the log of data into a first log portion containing a first number of bits associated with a first number of messages monitored during a first time period and a second log portion containing a second number of bits associated with a second number of messages monitored during a second time period, wherein the second time period is earlier than the first time period, and wherein the first number of bits associated with the first number of messages and the second number of bits associated with the second number of messages equals the total number of bits; determining, in response to monitoring each new message, a first number corresponding to a number of the first bits in the first log portion; determining, as each new message is monitored, a second number corresponding to a number of the first bits in the second log portion; comparing, as each new message is monitored, the first number and the second number; if the first number is at least equal to the second number by a predetermined criterion, continuing to generate the log of data using the total number of bits as a next message is monitored; and if the first number is less than the second number by the predetermined criterion, discarding the second log portion and continuing to generate the log of data using a new number of bits as the next message is monitored, wherein the new number of bits corresponds to the first number of bits in the first log portion, wherein the first number equals the number of the first bits in the first log portion, and wherein the second number equals the number of the first bits in the second log portion.
-
-
7. A method to determine data-transmission congestion between a first network node and a second network node, the method comprising:
-
monitoring a series of new messages between the first network node and the second network node, wherein received messages are associated with a first bit and dropped messages are associated with a second bit; generating, in response to monitoring each new message, a log of data comprising a total number of bits corresponding to a predefined number of monitored messages, wherein the log of data is an ordered series of the first and second bits ordered from a current bit associated with a current message to an oldest bit associated with an oldest message, wherein a new bit associated with the new monitored message is added as the current bit into the log of data, and wherein a bit associated with the oldest message is removed from the log of data; dividing, in response to monitoring each new message, the log of data into a first log portion containing a first number of bits associated with a first number of messages monitored during a first time period and a second log portion containing a second number of bits associated with a second number of messages monitored during a second time period, wherein the second time period is earlier than the first time period, and wherein the first number of bits associated with the first number of messages and the second number of bits associated with the second number of messages equals the total number of bits; determining, in response to monitoring each new message, a first number corresponding to a number of the first bits in the first log portion; determining, as each new message is monitored, a second number corresponding to a number of the first bits in the second log portion; comparing, as each new message is monitored, the first number and the second number; if the first number is at least equal to the second number by a predetermined criterion, continuing to generate the log of data using the total number of bits as a next message is monitored; and if the first number is less than the second number by the predetermined criterion, discarding the second log portion and continuing to generate the log of data using a new number of bits as the next message is monitored, wherein the new number of bits corresponds to the first number of bits in the first log portion, wherein the first number equals a number of the second bits in the first log portion, and wherein the second number equals a number of the second bits in the second log portion.
-
-
8. A method to determine data-transmission congestion between a first network node and a second network node, the method comprising:
-
monitoring a series of new messages between the first network node and the second network node, wherein received messages are associated with a first bit and dropped messages are associated with a second bit; generating, in response to monitoring each new message, a log of data comprising a total number of bits corresponding to a predefined number of monitored messages, wherein the log of data is an ordered series of the first and second bits ordered from a current bit associated with a current message to an oldest bit associated with an oldest message, wherein a new bit associated with the new monitored message is added as the current bit into the log of data, and wherein a bit associated with the oldest message is removed from the log of data; dividing, in response to monitoring each new message, the log of data into a first log portion containing a first number of bits associated with a first number of messages monitored during a first time period and a second log portion containing a second number of bits associated with a second number of messages monitored during a second time period, wherein the second time period is earlier than the first time period, and wherein the first number of bits associated with the first number of messages and the second number of bits associated with the second number of messages equals the total number of bits; determining, in response to monitoring each new message, a first number corresponding to a number of the first bits in the first log portion; determining, as each new message is monitored, a second number corresponding to a number of the first bits in the second log portion; comparing, as each new message is monitored, the first number and the second number; if the first number is at least equal to the second number by a predetermined criterion, continuing to generate the log of data using the total number of bits as a next message is monitored; and if the first number is less than the second number by the predetermined criterion, discarding the second log portion and continuing to generate the log of data using a new number of bits as the next message is monitored, wherein the new number of bits corresponds to the first number of bits in the first log portion, wherein the first number corresponds to a ratio of first bits to a total number of bits in the first log portion, and wherein the second number corresponds to a ratio of first bits to a total number of bits in the second log portion.
-
-
9. A method to determine data-transmission congestion between a first network node and a second network node, wherein received messages are associated with a first bit and dropped messages are associated with a second bit, the method comprising:
-
generating, as each new message is monitored, a log of data comprising a total number of bits corresponding to a number of monitored messages, wherein the log of data is an ordered series of the first bits and the second bits ordered from a current bit associated with a current message to an oldest bit associated with an oldest message, wherein the bit associated with the new monitored message is added as the current bit into the log of data, and wherein a bit associated with the oldest message is removed from the log of data; dividing, as each new message is monitored, the log of data into a first log portion containing the first bits and the second bits associated with messages monitored during a first time period and a second log portion containing the first bits and the second bits associated with messages monitored during a second time period, wherein the second time period is earlier than the first time period; determining, as each new message is monitored, a first number corresponding to a number of the first bits in the first log portion; determining, as each new message is monitored, a second number corresponding to a number of the first bits in the second log portion; comparing, as each new message is monitored, the first number and the second number; if the first number is at least equal to the second number by a predetermined criterion, continuing to generate the log of data using the total number of bits; and if the first number is less than the second number by the predetermined criterion, discarding the second log portion and continuing to generate the log of data using a new number of bits as a next message is provided, wherein the new number of bits corresponds to the number of the first bits and the second bits in the first log portion, wherein the first number equals the number of the first bits in the first log portion, and wherein the second number equals the number of the first bits in the second log portion.
-
-
10. A method to determine data-transmission congestion between a first network node and a second network node, wherein received messages are associated with a first bit and dropped messages are associated with a second bit, the method comprising:
-
generating, as each new message is monitored, a log of data comprising a total number of bits corresponding to a number of monitored messages, wherein the log of data is an ordered series of the first bits and the second bits ordered from a current bit associated with a current message to an oldest bit associated with an oldest message, wherein the bit associated with the new monitored message is added as the current bit into the log of data, and wherein a bit associated with the oldest message is removed from the log of data; dividing, as each new message is monitored, the log of data into a first log portion containing the first bits and the second bits associated with messages monitored during a first time period and a second log portion containing the first bits and the second bits associated with messages monitored during a second time period, wherein the second time period is earlier than the first time period; determining, as each new message is monitored, a first number corresponding to a number of the first bits in the first log portion; determining, as each new message is monitored, a second number corresponding to a number of the first bits in the second log portion; comparing, as each new message is monitored, the first number and the second number; if the first number is at least equal to the second number by a predetermined criterion, continuing to generate the log of data using the total number of bits; and if the first number is less than the second number by the predetermined criterion, discarding the second log portion and continuing to generate the log of data using a new number of bits as a next message is provided, wherein the new number of bits corresponds to the number of the first bits and the second bits in the first log portion, wherein the first number equals a number of the second bits in the first log portion, and wherein the second number equals a number of the second bits in the second log portion.
-
Specification