Patent US5699515A successfully refreshed from Google Patents.
US5699515A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Backoff scheme for access collision on a local area network
Assignee: Hewlett Packard Development Co LP
•
Filing: 1995-01-23
•
Granted: 1997-12-16
•
Expires: 2015-01-23
Abstract
Abstract Transmission of a first message over a local area network is delayed by a delay value. The delay value is calculated based on a backoff value in a backoff counter and a generated random number. Transmission of the first message is deferred when another node on the local area network begins transmission of another message while transmission of the first message is being delayed for the delay value. The backoff value in the backoff counter is incremented when the transmission of the first message is deferred. The backoff value in the backoff counter is incremented when transmission of the first message collides with transmission of another message by another node on the local area network. The backoff value in the backoff counter is decremented when the first message is transmitted without being deferred and without colliding with transmission of another message.
Inventors
- 👤 Alan Berkema
- 👤 Scott C. Petler
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 19:25
CPC Classifications
H; H04; H04L; H04L12/00; H04L12/28; H04L12/40; H04L12/407; H04L12/413
Claims Analysis
Total Claims: 25
Claim 1
Independent Claim
162 words
A method for transmitting a first message over a local area network comprising the steps of: (a) delaying transmission of the first message by a delay value; (b) calculating the delay value based on a backoff value in a backoff counter and a generated random number; (c) deferring transmission of the first message when another node on the local area network begins transmission of another message while transmission of the first message was being delayed in step (a); (d) incrementing the backoff value in the backoff counter when the transmission of the first message is deferred in step (c); (e) beginning transmission of the first message; (f) incrementing the backoff value in the backoff counter when transmission of the first message collides with transmission of another message by another node on the local area network; and, (g) decrementing the backoff value in the backoff counter when the first message is transmitted without being deferred and without colliding with transmission of another message.
Claim 2
Independent Claim
162 words
A method for transmitting a first message over a local area network comprising the steps of: (a) delaying transmission of the first message by a delay value; (b) calculating the delay value based on a backoff value in a backoff counter and a generated random number; (c) deferring transmission of the first message when another node on the local area network begins transmission of another message while transmission of the first message was being delayed in step (a); (d) incrementing the backoff value in the backoff counter when the transmission of the first message is deferred in step (c); (e) beginning transmission of the first message; (f) incrementing the backoff value in the backoff counter when transmission of the first message collides with transmission of another message by another node on the local area network; and, (g) decrementing the backoff value in the backoff counter when the first message is transmitted without being deferred and without colliding with transmission of another message.
Claim 3
Independent Claim
113 words
A method as in 1 wherein in step (b) the backoff value is a number between 0 and 15, and the delay value is calculated so that a probability of each delay value being calculated based on the backoff value and the generated random number is as in the following table: ______________________________________
Probability of
Backoff Value Delay Value Occurrence
______________________________________
0-3 0 microseconds
50%
0-3 100 microseconds
50%
4-7 0 microseconds
25%
4-7 100 microseconds
50%
4-7 200 microseconds
25%
8-11 100 microseconds
25%
8-11 200 microseconds
25%
8-11 300 microseconds
25%
8-11 400 microseconds
25%
11-15 100 microseconds
25%
11-15 400 microseconds
25%
11-15 600 microseconds
25%
11-15 800 microseconds
25%
______________________________________
Claim 4
Independent Claim
113 words
A method as in 1 wherein in step (b) the backoff value is a number between 0 and 15, and the delay value is calculated so that a probability of each delay value being calculated based on the backoff value and the generated random number is as in the following table: ______________________________________
Probability of
Backoff Value Delay Value Occurrence
______________________________________
0-3 0 microseconds
50%
0-3 100 microseconds
50%
4-7 0 microseconds
25%
4-7 100 microseconds
50%
4-7 200 microseconds
25%
8-11 100 microseconds
25%
8-11 200 microseconds
25%
8-11 300 microseconds
25%
8-11 400 microseconds
25%
11-15 100 microseconds
25%
11-15 400 microseconds
25%
11-15 600 microseconds
25%
11-15 800 microseconds
25%
______________________________________
Claim 5
Dependent Claim
65 words
A method as in claim 1 wherein step (c) includes the following substeps when transmission of the first message is deferred: (c.1) incrementing a deferral value in a deferral counter; (c.2) when the deferral value equals a predetermined maximum value, abandoning transmission of the first message; (c.3) if transmission of the first message is not abandoned in substep (c.2) repeating steps (a), (b) and (c).
Claim 6
Dependent Claim
86 words
A method as in claim 3 additionally comprising the following step: (h) when transmission of the first message collides with transmission of another message by another node on the local area network performing the following substeps: (h.1) incrementing a collision value in a collision counter; (h.2) when the collision value equals a predetermined maximum value, abandoning transmission of the first message; and, (h.3) if transmission of the first message is not abandoned in substep (h.2) repeating steps (a), (b), (c), (d), (e), (f), (g) and (h).
Claim 7
Dependent Claim
86 words
A method as in claim 1 additionally comprising the following step: (h) when transmission of the first message collides with transmission of another message by another node on the local area network performing the following substeps: (h.1) incrementing a collision value in a collision counter; (h.2) when the collision value equals a predetermined maximum value, abandoning transmission of the first message; and, (h.3) if transmission of the first message is not abandoned in substep (h.2) repeating steps (a), (b), (c), (d), (e), (f), (g) and (h).
Claim 8
Dependent Claim
22 words
A method as in claim 1 wherein in step (b) the generated random number is generated using a free running system clock.
Claim 9
Dependent Claim
34 words
A method as in claim 1, wherein in step (b) the delay value is calculated so that when the backoff value increases in value, a range of potential values of the delay value increases.
Claim 10
Independent Claim
124 words
A device for determining a delay value by which to delay transmission of a first message over a local area network, the device comprising: a random number generator which generates a random number; a timer; a backoff counter which contains a backoff value; delay value calculating means, coupled to the timer, the random number generator and the backoff count, for calculating a delay value based on the backoff value and the generated random number; and, control means coupled to the backoff counter, the timer, the random number generator and the delay value calculating means, for causing the backoff counter to increment the backoff value when transmission of the first message is deferred or when transmission of the first collides with transmission of another message.
Claim 11
Independent Claim
124 words
A device for determining a delay value by which to delay transmission of a first message over a local area network, the device comprising: a random number generator which generates a random number; a timer; a backoff counter which contains a backoff value; delay value calculating means, coupled to the timer, the random number generator and the backoff count, for calculating a delay value based on the backoff value and the generated random number; and, control means coupled to the backoff counter, the timer, the random number generator and the delay value calculating means, for causing the backoff counter to increment the backoff value when transmission of the first message is deferred or when transmission of the first collides with transmission of another message.
Claim 12
Dependent Claim
119 words
A device as in claim 8 wherein the backoff value in the backoff counter is a number between 0 and 15, and the delay value calculating means calculates the delay value so that a probability of each delay value being calculated based on the backoff value and the generated random number is as in the following table: ______________________________________
Probability of
Backoff Value Delay Value Occurrence
______________________________________
0-3 0 microseconds
50%
0-3 100 microseconds
50%
4-7 0 microseconds
25%
4-7 100 microseconds
50%
4-7 200 microseconds
25%
8-11 100 microseconds
25%
8-11 200 microseconds
25%
8-11 300 microseconds
25%
8-11 400 microseconds
25%
11-15 100 microseconds
25%
11-15 400 microseconds
25%
11-15 600 microseconds
25%
11-15 800 microseconds
25%
______________________________________
Claim 13
Dependent Claim
34 words
A device as in claim 8 additionally comprising a deferral counter coupled to the control means, the deferral counter containing a deferral value which is incremented when transmission of the first message is deferred.
Claim 14
Dependent Claim
42 words
A device as in claim 8 additionally comprising a collision counter coupled to the control means, the collision counter containing a collision value, the collision counter incrementing the collision value when transmission of the first message collides with transmission of another message.
Claim 15
Dependent Claim
21 words
A device as in claim 8 wherein the random number generator generates the random number using a free running system clock.
Claim 16
Dependent Claim
35 words
A device as in claim 8, wherein the delay value calculating means calculates the delay value so that when the backoff value increases in value, a range of potential values of the delay value increases.
Claim 17
Independent Claim
120 words
A method for determining a delay value by which to delay transmission of a first message over a local area network, the method comprising the steps of: (a) calculating the delay value based on a backoff value in a backoff counter and a generated random number; (b) incrementing the backoff value in the backoff counter when the transmission of the first message is deferred; (c) incrementing the backoff value in the backoff counter when transmission of the first message collides with transmission of another message by another node on the local area network; and, (d) decrementing the backoff value in the backoff counter when the first message is transmitted without being deferred and without colliding with transmission of another message.
Claim 18
Independent Claim
120 words
A method for determining a delay value by which to delay transmission of a first message over a local area network, the method comprising the steps of: (a) calculating the delay value based on a backoff value in a backoff counter and a generated random number; (b) incrementing the backoff value in the backoff counter when the transmission of the first message is deferred; (c) incrementing the backoff value in the backoff counter when transmission of the first message collides with transmission of another message by another node on the local area network; and, (d) decrementing the backoff value in the backoff counter when the first message is transmitted without being deferred and without colliding with transmission of another message.
Claim 19
Independent Claim
113 words
A method as in 14 wherein in step (a) the backoff value is a number between 0 and 15, and the delay value is calculated so that a probability of each delay value being calculated based on the backoff value and the generated random number is as in the following table: ______________________________________
Probability of
Backoff Value Delay Value Occurrence
______________________________________
0-3 0 microseconds
50%
0-3 100 microseconds
50%
4-7 0 microseconds
25%
4-7 100 microseconds
50%
4-7 200 microseconds
25%
8-11 100 microseconds
25%
8-11 200 microseconds
25%
8-11 300 microseconds
25%
8-11 400 microseconds
25%
11-15 100 microseconds
25%
11-15 400 microseconds
25%
11-15 600 microseconds
25%
11-15 800 microseconds
25%
______________________________________
Claim 20
Independent Claim
113 words
A method as in 14 wherein in step (a) the backoff value is a number between 0 and 15, and the delay value is calculated so that a probability of each delay value being calculated based on the backoff value and the generated random number is as in the following table: ______________________________________
Probability of
Backoff Value Delay Value Occurrence
______________________________________
0-3 0 microseconds
50%
0-3 100 microseconds
50%
4-7 0 microseconds
25%
4-7 100 microseconds
50%
4-7 200 microseconds
25%
8-11 100 microseconds
25%
8-11 200 microseconds
25%
8-11 300 microseconds
25%
8-11 400 microseconds
25%
11-15 100 microseconds
25%
11-15 400 microseconds
25%
11-15 600 microseconds
25%
11-15 800 microseconds
25%
______________________________________
Claim 21
Dependent Claim
64 words
A method as in claim 14 wherein step (b) includes the following substeps when transmission of the first message is deferred: (b.1) incrementing a deferral value in a deferral counter; (b.2) when the deferral value equals a predetermined maximum value, abandoning transmission of the first message; (b.3) if transmission of the first message is not abandoned in substep (c.2) repeating steps (a) and (b).
Claim 22
Dependent Claim
83 words
A method as in claim 16 additionally comprising the following step: (e) when transmission of the first message collides with transmission of another message by another node on the local area network performing the following substeps: (e.1) incrementing a collision value in a collision counter; (e.2) when the collision value equals a predetermined maximum value, abandoning transmission of the first message; and, (e.3) if transmission of the first message is not abandoned in substep (e.2) repeating steps (a), (b), (c), (d) and (e).
Claim 23
Dependent Claim
83 words
A method as in claim 14 additionally comprising the following step: (e) when transmission of the first message collides with transmission of another message by another node on the local area network performing the following substeps: (e.1) incrementing a collision value in a collision counter; (e.2) when the collision value equals a predetermined maximum value, abandoning transmission of the first message; and, (e.3) if transmission of the first message is not abandoned in substep (e.2) repeating steps (a), (b), (c), (d) and (e).
Claim 24
Dependent Claim
22 words
A method as in claim 14 wherein in step (1) the generated random number is generated using a free running system clock.
Claim 25
Dependent Claim
34 words
A method as in claim 14, wherein in step (a) the delay value is calculated so that when the backoff value increases in value, a range of potential values of the delay value increases.
References Cited (Backward Citations)
US4063220A
Cited
US4234952A
Cited
US4412326A
Cited
US4598285A
Cited
US5319641A
Cited
US5353287A
Cited
US5436903A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-12-15 | 2001-06-16 | 2001-12-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-12-15 | 2005-06-16 | 2005-12-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-12-15 | 2009-06-16 | 2009-12-16 | $7700.00 | Window Closed / Lapsed |