Bandwidth reservation and collision resolution method for multiple access communication networks where remote hosts send reservation requests to a base station for randomly chosen minislots
First Claim
1. A method for conflict resolution among remote hosts in a wireless communications network, said network having a base station and a plurality of remote hosts, said base station and said remote hosts exchanging data via downlink and uplink frames respectively, each of said remote hosts having a respective uplink queue and being characterized by a stack level value indicative of whether or not said remote host has data in said queue for transmission to said base station, the method comprising the steps, in combination, of:
- configuring at least one of said uplink frames to include at least one reservation minislot for sending an access request for permission for uplink data transmission from a requesting one of said remote hosts to said base station;
assigning a stack level of "0" to each of said remote hosts that has received data for transmission to said base station at said respective uplink queue if said uplink queue was empty at the last time of uplink access request transmission and putting said remote host into a request state;
at any of said remote hosts that are in a request state, have a respective stack level value equal to "0", and did not transmit data during the last uplink data transmission, randomly picking a respective one of said reservation minislots;
transmitting an access request to said base station in said respective picked one of said reservation minislots from each respective one of said remote hosts;
determining at said base station a transmit status for each of said reservation minislots, said transmit status for a particular one of said reservation minislots being SUCCESS, IDLE, or COLLIDED depending respectively on whether said particular reservation minislot contained a successful access request, no access request, or an access request that was corrupted or in error;
transmitting from said base station a downlink acknowledgment message indicating the transmit status of each of said reservation minislots;
receiving at said plurality of remote hosts said acknowledgment message;
for each of said remote hosts that transmitted one of said access requests, randomly setting said respective stack level value of said remote host to one of "1" or "0" when said transmit status for said respective picked one of said reservation minislots received in said acknowledgment message indicates COLLIDED; and
for each of said remote hosts that transmitted one of said access requests, removing said remote host from said request state if said transmit status for said respective picked one of said reservation minislots received in said acknowledgment message indicates SUCCESS and said uplink queue at said remote host will be empty after the next uplink data transmission;
at each of said remote hosts having a respective stack level value greater than "0", inspecting said received acknowledgment message and counting the total number of said reservation minislot transmit statuses that indicate SUCCESS;
at each of said remote hosts having a respective stack level value greater than "0", decrementing said respective stack level value if said total number of reservation minislot transmit statuses equaling SUCCESS or IDLE is greater than or equal to a threshold value; and
at each of said remote hosts having a respective stack level greater than "0", incrementing said respective stack level value if said total number of reservation minislot transmit statuses equaling SUCCESS or IDLE is less than a threshold value.
3 Assignments
0 Petitions
Accused Products
Abstract
In a method for conflict resolution among remote hosts in a wireless network where remotes make bandwidth requests to the base station via uplink frames partitioned into one or more reservation minislots, a collision occurs where two or more remotes have transmitted a request in the same minislot. Each remote is characterized by a stack level, and only remotes with a stack level equal to 0 are permitted to transmit access request packets. Newly active remotes are allowed to join in with those remotes already having stack level 0 during any particular conflict resolution period by setting their stack levels to 0 and entering the request state. If the stack level of a remote is 0, the remote randomly picks a minislot for transmission of an access request. If the outcome is SUCCESS, and the queue at the remote is empty, the remote transmits the current packet after receiving a transmit permit and exits the request state. If the queue is not empty, then, after receiving a permit, the current packet is transmitted with a piggybacked reservation request for transmission of the next packet in the queue, continuing until the queue is empty. If the outcome of the reservation request was not SUCCESS, the remote participates in a random draw to determine whether to increment its stack level by 1 or leave it at 0. If the stack level of any remote is not 0, then in one embodiment if the outcome of the previous reservation request was COLLIDED, the remote increments its stack level by 1, otherwise decrementing it by 1. In an alternate embodiment, if the outcome of all the reservation requests during the previous cycle was COLLIDED for greater than or equal to some threshold, the remote increments its stack level by 1, otherwise decrementing it by 1. The number of reservation minislots available in any particular uplink frame may be dynamically changed based on the percentage of idle minislots and the total uplink queue length.
476 Citations
10 Claims
-
1. A method for conflict resolution among remote hosts in a wireless communications network, said network having a base station and a plurality of remote hosts, said base station and said remote hosts exchanging data via downlink and uplink frames respectively, each of said remote hosts having a respective uplink queue and being characterized by a stack level value indicative of whether or not said remote host has data in said queue for transmission to said base station, the method comprising the steps, in combination, of:
-
configuring at least one of said uplink frames to include at least one reservation minislot for sending an access request for permission for uplink data transmission from a requesting one of said remote hosts to said base station; assigning a stack level of "0" to each of said remote hosts that has received data for transmission to said base station at said respective uplink queue if said uplink queue was empty at the last time of uplink access request transmission and putting said remote host into a request state; at any of said remote hosts that are in a request state, have a respective stack level value equal to "0", and did not transmit data during the last uplink data transmission, randomly picking a respective one of said reservation minislots; transmitting an access request to said base station in said respective picked one of said reservation minislots from each respective one of said remote hosts; determining at said base station a transmit status for each of said reservation minislots, said transmit status for a particular one of said reservation minislots being SUCCESS, IDLE, or COLLIDED depending respectively on whether said particular reservation minislot contained a successful access request, no access request, or an access request that was corrupted or in error; transmitting from said base station a downlink acknowledgment message indicating the transmit status of each of said reservation minislots; receiving at said plurality of remote hosts said acknowledgment message; for each of said remote hosts that transmitted one of said access requests, randomly setting said respective stack level value of said remote host to one of "1" or "0" when said transmit status for said respective picked one of said reservation minislots received in said acknowledgment message indicates COLLIDED; and for each of said remote hosts that transmitted one of said access requests, removing said remote host from said request state if said transmit status for said respective picked one of said reservation minislots received in said acknowledgment message indicates SUCCESS and said uplink queue at said remote host will be empty after the next uplink data transmission; at each of said remote hosts having a respective stack level value greater than "0", inspecting said received acknowledgment message and counting the total number of said reservation minislot transmit statuses that indicate SUCCESS; at each of said remote hosts having a respective stack level value greater than "0", decrementing said respective stack level value if said total number of reservation minislot transmit statuses equaling SUCCESS or IDLE is greater than or equal to a threshold value; and at each of said remote hosts having a respective stack level greater than "0", incrementing said respective stack level value if said total number of reservation minislot transmit statuses equaling SUCCESS or IDLE is less than a threshold value. - View Dependent Claims (2, 3)
-
-
4. A method for conflict resolution among remote hosts in a wireless communications network, said network having a base station and a plurality of remote hosts, said base station and said remote hosts exchanging data via downlink and uplink frames respectively, each of said remote hosts having a respective uplink queue and being characterized by a stack level value indicative of whether or not said remote host has data in said queue for transmission to said base station, the method comprising the steps, in combination, of
configuring at least one of said uplink frames to include at least one reservation minislot for sending an access request for permission for uplink data transmission from a requesting one of said remote hosts to said base station; -
assigning a stack level of "0" to each of said remote hosts that has received data for transmission to said base station at said respective uplink queue if said uplink queue was empty at the last time of uplink access request transmission and putting said remote host into a request state; at any of said remote hosts that are in a request state, have a respective stack level value equal to "0", and did not transmit data during the last uplink data transmission, randomly picking a respective one of said reservation minislots; transmitting an access request to said base station in said respective picked one of said reservation minislots from each respective one of said remote hosts; determining at said base station a transmit status for each of said reservation minislots, said transmit status for a particular one of said reservation minislots being SUCCESS, IDLE, or COLLIDED depending respectively on whether said particular reservation minislot contained a successful access request, no access request, or an access request that was corrupted or in error; transmitting from said base station a downlink acknowledgment message indicating the transmit status of each of said reservation minislots; receiving at said plurality of remote hosts said acknowledgment message; for each of said remote hosts that transmitted one of said access requests, randomly setting said respective stack level value of said remote host to one of "1" or "0" when said transmit status for said respective picked one of said reservation minislots received in said acknowledgment message indicates COLLIDED; for each of said remote hosts that transmitted one of said access requests, removing said remote host from said request state if said transmit status for said respective picked one of said reservation minislots received in said acknowledgment message indicates SUCCESS and said uplink queue at said remote host will be empty after the next uplink data transmission; at each of said remote hosts having a respective stack level value greater than "0", inspecting said received acknowledgment message for the one of said transmit statuses corresponding to the one of said reservation minislots which said remote host most recently picked and used to make an access request; at each of said remote hosts having a respective stack level value greater than "0", decrementing said respective stack level value when said most recently picked reservation minislot transmit status indicates SUCCESS or IDLE; and at each of said remote hosts having a respective stack level greater than "0", incrementing said respective stack level if said reservation minislot transmit status indicates COLLIDED. - View Dependent Claims (5, 6)
-
-
7. A method for conflict resolution among remote hosts in a wireless communications network, said network having a base station and a plurality of remote hosts, said base station and said remote hosts exchanging data via downlink and uplink frames respectively, each of said remote hosts having a respective uplink queue and being characterized by a stack level value indicative of whether or not said remote host has data in said queue for transmission to said base station, the method comprising the steps, in combination, of:
-
configuring at least one of said uplink frames at at least one of said remote hosts to include at least one reservation minislot for sending an access request for permission for uplink data transmission from said remote host to said base station; assigning a stack level of "0" at any of said remote hosts that has received data for transmission to said base station at said respective uplink queue if said uplink queue was empty at the last time of uplink access request transmission and putting said remote host into a request state; at at least one of said remote hosts that is in a request state, has a respective stack level value equal to "0", and did not transmit data during the last uplink data transmission, randomly picking one of said reservation minislots; transmitting an access request to said base station in said picked one of said reservation minislots from said remote host for determination at said base station of a transmit status for each of said reservation minislots, said transmit status for a particular one of said reservation minislots being SUCCESS, IDLE, or COLLIDED depending respectively on whether said particular reservation minislot contained a successful access request, no access request, or an access request that was corrupted or in error; receiving at said remote host a downlink acknowledgment message from said base station indicating the transmit status of each of said reservation minislots; at any of said remote hosts that transmitted one of said access requests, randomly setting said respective stack level value of said remote host at one of "1" or "0" when said transmit status for said picked one of said reservation minislots received in said acknowledgment message indicates COLLIDED; at any of said remote hosts that transmitted one of said access requests, removing said remote host from said request state if said transmit status for said picked one of said reservation minislots received in said acknowledgment message indicates SUCCESS and said uplink queue at said remote host will be empty after the next uplink data transmission; at any of said remote hosts having a stack level value greater than "0", decrementing said stack level value if the total number of reservation minislot transmit statuses equaling SUCCESS or IDLE is greater than or equal to a threshold value; and at any of said remote hosts having a stack level value greater than "0", incrementing said stack level value if said total number of reservation minislot transmit statuses equaling SUCCESS or IDLE is less than a threshold value.
-
-
8. A method for conflict resolution among remote hosts in a wireless communications network, said network having a base station and a plurality of remote hosts, said base station and said remote hosts exchanging data via downlink and uplink frames respectively, each of said remote hosts having a respective uplink queue and being characterized by a stack level value indicative of whether or not said remote host has data in said queue for transmission to said base station, the method comprising the steps, in combination, of:
-
receiving an access request for permission for uplink data transmission at said base station from any of said remote hosts that has received data for transission to said base station at said respective uplink queue, has a stack level of "0", is in a request state, and did not transmit data during the last uplink data transmission, said access request being received in a randomly picked one of a plurality of reservation minislots configured in one of said uplink frames; determining at said base station a transmit status for each of said reservation minislots, said transmit status for a particular one of said reservation minislots being SUCCESS, IDLE, or COLLIDED depending respectively on whether said particular reservation minislot contained a successful access request, no access request, or an access request that was corrupted or in error; and transmitting from said base station a downlink acknowledgment message indicating the transmit status of each of said reservation minislots, said downlink acknowledgment message being received and responded to at said plurality of remote hosts in the following manner; for any of said remote hosts that transmitted one of said access requests, said stack level value of said remote host is randomly set to one of "1" or "0" when said transmit status for said picked one of said reservation minislots received in said acknowledgment message indicates COLLIDED; for any of said remote hosts that transmitted one of said access requests, said remote host is removed from said request state if said transmit status for said picked one of said reservation minislots received in said acknowledgment message indicates SUCCESS and said uplink queue at said remote host will be empty after the next uplink data transmission; for any of said remote hosts having a stack level value greater than "0", said stack level value is decremented if the total number of reservation minislot transmit statuses equaling SUCCESS or IDLE is greater than or equal to a threshold value; and for any of said remote hosts having a stack level value greater than "0", said stack level value is incremented if said total number of reservation minislot transmit statuses equaling SUCCESS or IDLE is less than a threshold value.
-
-
9. A method for conflict resolution among remote hosts in a wireless communications network, said network having a base station and a plurality of remote hosts, said base station and said remote hosts exchanging data via downlink and uplink frames respectively, each of said remote hosts having a respective uplink queue and being characterized by a stack level value indicative of whether or not said remote host has data in said queue for transmission to said base station, the method comprising the steps, in combination, of:
-
configuring at least one of said uplink frames at at least one of said remote hosts to include at least one reservation minislot for sending an access request for permission for uplink data transmission from said remote host to said base station; assigning a stack level of "0" at any of said remote hosts that has received data for transmission to said base station at said respective uplink queue if said uplink queue was empty at the last time of uplink access request transmission and putting said remote host into a request state; at at least one of said remote hosts that is in a request state, has a respective stack level value equal to "0", and did not transmit data during the last uplink data transmission, randomly picking one of said reservation minislots; transmitting an access request to said base station in said picked one of said reservation minislots from said remote host for determination at said base station of a transmit status for each of said reservation minislots, said transmit status for a particular one of said reservation minislots being SUCCESS, IDLE, or COLLIDED depending respectively on whether said particular reservation minislot contained a successful access request, no access request, or an access request that was corrupted or in error; receiving at said remote host a downlink acknowledgment message from said base station indicating the transmit status of each of said reservation minislots; at any of said remote hosts that transmitted one of said access requests, randomly setting said stack level value of said remote host at one of "1" or "0" when said transmit status for said picked one of said reservation minislots received in said acknowledgment message indicates COLLIDED; at any of said remote hosts that transmitted one of said access requests, removing said remote host from said request state if said transmit status for said picked one of said reservation minislots received in said acknowledgment message indicates SUCCESS and said uplink queue at said remote host will be empty after the next uplink data transmission; at any of said remote hosts having a stack level value greater than "0", inspecting said received acknowledgment message for the one of said transmit statuses corresponding to the one of said reservation minislots which said remote host most recently picked and used to make an access request; at any of said remote hosts having a stack level value greater than "0", decrementing said stack level value when said most recently picked reservation minislot transmit status indicates SUCCESS or IDLE; and at any of said remote hosts having a stack level value greater than "0", incrementing said stack level value if said reservation minislot transmit status indicates COLLIDED.
-
-
10. A method for conflict resolution among remote hosts in a wireless communications network, said network having a base station and a plurality of remote hosts, said base station and said remote hosts exchanging data via downlink and uplink frames respectively, each of said remote hosts having a respective uplink queue and being characterized by a stack level value indicative of whether or not said remote host has data in said queue for transmission to said base station, the method comprising the steps, in combination, of:
-
receiving an access request for permission for uplink data transmission at said base station from any of said remote hosts that has received data for transmission to said base station at said respective uplink queue, has a stack level of "0", is in a request state, and did not transmit data during the last uplink data transmission, said access request being received in a randomly picked one of a plurality of reservation minislots configured in one of said uplink frames; determining at said base station a transmit status for each of said reservation minislots, said transmit status for a particular one of said reservation minislots being SUCCESS, IDLE, or COLLIDED depending respectively on whether said particular reservation minislot contained a successful access request, no access request, or an access request that was corrupted or in error; and transmitting from said base station a downlink acknowledgment message indicating the transmit status of each of said reservation minislots, said downlink acknowledgment message being received and responded to at said plurality of remote hosts in the following manner; for any of said remote hosts that transmitted one of said access requests, said stack level value of said remote host is set at one of "1" or "0" when said transmit status for said respective picked one of said reservation minislots received in said acknowledgment message indicates COLLIDED; for any of said remote hosts that transmitted one of said access requests, said remote host is removed from said request state if said transmit status for said respective picked one of said reservation minislots received in said acknowledgment message indicates SUCCESS and said uplink queue at said remote host will be empty after the next uplink data transmission; for any of said remote hosts having a stack level value greater than "0", said received acknowledgment message is inspected for the one of said transmit statuses corresponding to the one of said reservation minislots which said remote host most recently picked and used to make an access request; for any of said remote hosts having a stack level value greater than "0", said stack level value is decremented when said most recently picked reservation minislot transmit status indicates SUCCESS or IDLE; and
for any of said remote hosts having a stack level value greater than "0", said stack level value is incremented if said reservation minislot transmit status indicates COLLIDED.
-
Specification