# US 2021/0243135 A1 · Techniques for Avoiding Collisions Among Communications Packets by Using Shared Transmission Queue

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2021/0243135 A1
- Document ID: US20210243135A1
- Status: Published application
- Kind: A1
- Application number: 17/248,623
- Filed: 2021-02-01
- Published: 2021-08-05
- Earliest claimed: 2020-01-30
- Assignees: The Regents of the University of California
- Applicants: The Regents of the University of California
- Inventors: Jose Joaquin Garcia-Luna-Aceves
- Web page: https://patentgrep.com/patent/US20210243135A1

## CPC

- H04L 47/522: {Dynamic queue service slot or variable bandwidth allocation}
- H04L 47/562: {Attaching a time tag to queues}
- H04L 47/622: {Queue service order}
- H04L 69/22: Parsing or analysis of headers
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

Techniques for transmitting data packets on a shared channel in a data communications network include storing, on a local node, a current number of turns in a transmitting queue and a current turn based on packets received from other nodes on the channel. For a first local data packet to transmit, a local transmit turn is obtained based on successfully transmitting the packet in a time interval following a last turn in the queue. A data link layer header includes queue fields for the current number of turns, the local transmit turn, and a request for adding the local transmit turn. While there is still a remaining packet to transmit and when the current turn is the local transmit turn, the packet is transmitted with queue fields indicating the current number of turns, the current turn, and an indication of no new turn. An acknowledgement control packet indicates successful transmission.

## Claims

### Claim 1

A method for transmitting data packets on a shared channel in a data communications network, the method comprising:
storing, on a local node of the data communications network, a current number of turns in a transmitting queue and a current turn based on zero or more data packets received from other nodes on the channel;
upon determining that there is a first local data packet of at least one local data packet to transmit, obtaining a local transmit turn for the local node in the queue based on successfully transmitting the first local data packet by the local node in a time interval following a last turn in the queue, wherein the time interval is less than a maximum time interval value, and a first data link layer header in the first data packet includes queue fields that hold data that indicate the current number of nodes in the transmitting queue, the local transmit turn, and a request for adding the local transmit turn, thereby ending the current turn;
while there is still a remaining local data packet of the at least one local data packet to transmit and the current turn is equal to the local transmit turn, transmitting the remaining local data packet in which the queue fields indicate the current number of turns in the transmitting queue, the current turn, and no request for adding a turn; and
determining that the local data packet was successfully transmitted when a successful acknowledgement control packet that uniquely indicates the local data packet is received.

### Claim 2 (depends on 1)

The method as recited in claim 1, wherein the queue fields also indicate whether the local node is relinquishing the local transmit turn after successful transmission of the transmitted local data packet.

### Claim 3 (depends on 1)

The method as recited in claim 1, wherein each new local transmit turn is added at an end of the queue, so that the current number of turns in the first local data packet is one greater than the current number of turns based on data packets received from other nodes on the channel.

### Claim 4 (depends on 2)

The method as recited in claim 2, wherein after the local node relinquishes the local transmit turn, the method further includes decrementing by one the current number of turns in the transmitting queue.

### Claim 5 (depends on 1)

The method as recited in claim 1, wherein the first local data packet is not transmitted while the current number of turns is equal to a maximum size for the transmitting queue.

### Claim 6 (depends on 5)

The method as recited in claim 5, wherein the maximum size for the transmitting queue is the maximum value represented by one byte of storage, and a length of the queue fields in the data link header is a sum of three bytes and two bits.

### Claim 7 (depends on 1)

The method as recited in claim 1, said step of storing the current number of turns in the transmitting queue and the current turn further comprises storing NULL values for the current number of turns in the transmitting queue and the current turn based on zero data packets received from other nodes since the local node entered the network.

### Claim 8 (depends on 1)

The method as recited in claim 1, wherein the maximum time interval value is a maximum channel access time (MCAT) that includes a maximum receive-to-transmit turn-around time, a time needed to transmit a largest data packet allowed, and a maximum propagation delay in the network.

### Claim 9 (depends on 1)

The method as recited in claim 1, wherein the request for adding the local transmit turn comprises a data field that holds data that indicates a unique identifier for a node that most recently joins the queue.

### Claim 10 (depends on 1)

The method as recited in claim 1, further comprising determining that the current turn ends when no carrier is sensed on the channel for a start time that is sufficient for a first bit to be sensed from a remote node that has started transmitting.

### Claim 11

A non-transitory computer-readable medium carrying one or more sequences of instructions, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to:
store, on a local node of the data communications network, a current number of turns in a transmitting queue and a current turn based on zero or more data packets received from other nodes on the channel;
upon determining that there is a first local data packet of at least one local data packet to transmit, obtain a local transmit turn for the local node in the queue based on successfully transmitting the first local data packet by the local node in a time interval following a last turn in the queue, wherein the time interval is less than a maximum time interval value, and a first data link layer header in the first data packet includes queue fields that hold data that indicate the current number of nodes in the transmitting queue, the local transmit turn, and a request for adding the local transmit turn, thereby ending the current turn;
while there is still a remaining local data packet of the at least one local data packet to transmit and the current turn is equal to the local transmit turn, transmit the remaining local data packet in which the queue fields indicate the current number of turns in the transmitting queue, the current turn, and no request for adding a turn; and
determine that the local data packet was successfully transmitted when a successful acknowledgement control packet that uniquely indicates the local data packet is received.

### Claim 12 (depends on 11)

The computer-readable medium as recited in claim 11, wherein the queue fields also indicate whether the local node is relinquishing the local transmit turn after successful transmission of the transmitted local data packet.

### Claim 13 (depends on 11)

The computer-readable medium as recited in claim 11, wherein each new local transmit turn is added at an end of the queue, so that the current number of turns in the first local data packet is one greater than the current number of turns based on data packets received from other nodes on the channel.

### Claim 14 (depends on 12)

The computer-readable medium as recited in claim 12, wherein after the local node relinquishes the local transmit turn, the one or more sequences of instructions further cause the one or more processors to decrement by one the current number of turns in the transmitting queue.

### Claim 15 (depends on 11)

The computer-readable medium as recited in claim 11, wherein the first local data packet is not transmitted while the current number of turns is equal to a maximum size for the transmitting queue.

### Claim 16 (depends on 15)

The computer-readable medium as recited in claim 15, wherein the maximum size for the transmitting queue is the maximum value represented by one byte of storage, and a length of the queue fields in the data link header is a sum of three bytes and two bits.

### Claim 17 (depends on 11)

The computer-readable medium as recited in claim 11, said step of storing the current number of turns in the transmitting queue and the current turn further comprises storing NULL values for the current number of turns in the transmitting queue and the current turn based on zero data packets received from other nodes since the local node entered the network.

### Claim 18 (depends on 11)

The computer-readable medium as recited in claim 11, wherein the maximum time interval value is a maximum channel access time (MCAT) that includes a maximum receive-to-transmit turn-around time, a time needed to transmit a largest data packet allowed, and a maximum propagation delay in the network.

### Claim 19 (depends on 11)

The computer-readable medium as recited in claim 11, wherein the request for adding the local transmit turn comprises a data field that holds data that indicates a unique identifier for a node that most recently joins the queue.

### Claim 20 (depends on 11)

The computer-readable medium as recited in claim 11, the one or more sequences of instructions further cause the one or more processors to determine that the current turn ends when no carrier is sensed on the channel for a start time that is sufficient for a first bit to be sensed from a remote node that has started transmitting.

### Claim 21

An apparatus comprising:
a communications transceiver;
at least one processor; and
at least one memory including one or more sequences of instructions,
the at least one memory and the one or more sequences of instructions configured to, with the at least one processor, cause the apparatus to perform at least the following,
store a current number of turns in a transmitting queue and a current turn based on zero or more data packets received from other nodes on the channel;
upon determining that there is a first local data packet of at least one local data packet to transmit, obtaining a local transmit turn for the local node in the queue based on successfully transmitting the first local data packet by the local node in a time interval following a last turn in the queue, wherein the time interval is less than a maximum time interval value, and a first data link layer header in the first data packet includes queue fields that hold data that indicate the current number of nodes in the transmitting queue, the local transmit turn, and a request for adding the local transmit turn, thereby ending the current turn;
while there is still a remaining local data packet of the at least one local data packet to transmit and the current turn is equal to the local transmit turn, transmitting the remaining local data packet in which the queue fields indicate the current number of turns in the transmitting queue, the current turn, and no request for adding a turn; and
determining that the local data packet was successfully transmitted when a successful acknowledgement control packet that uniquely indicates the local data packet is received.

### Claim 22 (depends on 21)

The apparatus as recited in claim 21, wherein the queue fields also indicate whether the local node is relinquishing the local transmit turn after successful transmission of the transmitted local data packet.

### Claim 23 (depends on 21)

The apparatus as recited in claim 21, wherein each new local transmit turn is added at an end of the queue, so that the current number of turns in the first local data packet is one greater than the current number of turns based on data packets received from other nodes on the channel.

### Claim 24 (depends on 22)

The apparatus as recited in claim 22, wherein after the local node relinquishes the local transmit turn, the one or more sequences of instructions are further configured to cause the apparatus to decrement by one the current number of turns in the transmitting queue.

### Claim 25 (depends on 21)

The apparatus as recited in claim 21, wherein the first local data packet is not transmitted while the current number of turns is equal to a maximum size for the transmitting queue.

### Claim 26 (depends on 25)

The apparatus as recited in claim 25, wherein the maximum size for the transmitting queue is the maximum value represented by one byte of storage, and a length of the queue fields in the data link header is a sum of three bytes and two bits.

### Claim 27 (depends on 21)

The apparatus as recited in claim 21, said step of storing the current number of turns in the transmitting queue and the current turn further comprises storing NULL values for the current number of turns in the transmitting queue and the current turn based on zero data packets received from other nodes since the local node entered the network.

### Claim 28 (depends on 21)

The apparatus as recited in claim 21, wherein the maximum time interval value is a maximum channel access time (MCAT) that includes a maximum receive-to-transmit turn-around time, a time needed to transmit a largest data packet allowed, and a maximum propagation delay in the network.

### Claim 29 (depends on 21)

The apparatus as recited in claim 21, wherein the request for adding the local transmit turn comprises a data field that holds data that indicates a unique identifier for a node that most recently joins the queue.

### Claim 30 (depends on 21)

The apparatus as recited in claim 21, the one or more sequences of instructions are further configured to cause the apparatus to determine that the current turn ends when no carrier is sensed on the channel for a start time that is sufficient for a first bit to be sensed from a remote node that has started transmitting.

### Claim 31

A data structure stored on a non-transitory computer-readable medium, the data structure comprising a communications data packet that comprises a data link header that comprises:
a first field holding data that indicates a number of turns in a transmitting queue for a shared communications channel;
a different second field holding data that indicates a current turn within the transmitting queue;
a different third field holding data that indicates whether a new turn is being requested by a transmitting node; and
a different fourth field holding data that indicates whether the transmitting node is relinquishing an existing turn in the transmitting queue.

### Claim 32 (depends on 31)

The data structure as recited in claim 31, wherein: the first field is one byte in length; the second field is one byte in length; the third field is one bit in length; and, the fourth field is one bit in length.

### Claim 33 (depends on 31)

The data structure as recited in claim 31, wherein the third field holds data that indicates an unique identifier for a node that most recently joins the queue.

### Claim 34

A data structure stored on a non-transitory computer-readable medium of a node in a communications network, the data structure comprising:
a first field holding data that indicates a value for a number of turns in a transmitting queue for a shared communications channel;
a different second field holding data that indicates a value for a current turn within the transmitting queue;
a different third field holding data that indicates a value for a local node transmitting turn within the queue.

### Claim 35 (depends on 34)

The data structure as recited in claim 34, further comprising:
a fourth field holding data that indicates a value for a proposed entry turn when the third field indicates a NULL value; and
a fifth field holding data that indicates whether or not there was a successful attempt to join the queue at the end of a previous cycle through the queue.

### Claim 36 (depends on 34)

The data structure as recited in claim 34, wherein: the first field is one byte in length; the second field is one byte in length; and, the third field is one byte in length.

### Claim 37 (depends on 35)

The data structure as recited in claim 35, wherein: the fourth field is one byte in length; and, the fifth field is one bit in length.

### Claim 38 (depends on 35)

The data structure as recited in claim 35, wherein the fifth field holds data that indicates an unique identifier for a node that most recently joined the queue.
