United States Patent (19)
`Crisler et al.
`
`(54) METHOD FOR CONTROLLING THE
`SCHEDULING OF MULTIPLE ACCESS TO
`COMMUNICATION RESOURCES
`(75) Inventors:
`Kenneth J. Crisler, Wheaton;
`Michael L. Needham, Palatine, both
`of Ill.
`73) Assignee: Motorola, Inc., Schaumburg, Ill.
`(21) Appl. No.: 676,653
`(22) Filed:
`Mar. 28, 1991
`(5) Int. Cl. ................................................ H04J 3/16
`52 U.S. C. ................................... 370/95.1; 370/85.2
`(58) Field of Search .................... 370/95.1, 85.2, 87.7,
`370/95.3, 104.1
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`4,774,707 9/1988 Raychaudhuri ................... 370/85.2
`4,888,765 12/1989 Dyke ................................., 370/95.
`OTHER PUBLICATIONS
`"Packet Reservation Multiple Access for Local Wire
`less Communications', Goodman et al., IEEE publica
`tion, pp. 701-706 (1988).
`Multiple Access Protocols for Data Communications
`via VSAT Networks, Wolejsza et al., IEEE Communi
`cations Magazine, pp. 30-39 (1987).
`Performance Analysis of Virtual Time CSMA, Meditch
`et al. IEEE Publication, pp. 242-251 (1986).
`Virtual. Time CSMA: Why Two Clocks Are Better
`
`USOO5142533A
`11) Patent Number:
`(45) Date of Patent:
`
`5,142,533
`Aug. 25, 1992
`
`Than One, Molie et al., IEEE Transactions on Commu
`nications, pp. 919–933 (Sep. 1985).
`Multiaccess Protocols in Packet Communication Sys
`tems, Tobagi, IEEE Transactions On Communications,
`pp. 468-488 (Apr. 1980).
`On Protocols For Satellite Packet Switching, Lam,
`IEEE Publication, pp. 58.6.1-58.6.6 (1979).
`An Analysis of the Reservation-ALOHA Protocol for
`Satellite Packet Switching, Lam, IEEE Publication, pp.
`27.3.1-27.3.5 (1978).
`Primary Examiner-Douglas W. Olms
`Assistant Examiner-Min Jung
`Attorney, Agent, or Firm-Steven G. Parmelee
`57)
`ABSTRACT
`A method of providing a communication unit (10) ac
`cess to a shared communication resource. In the com
`munication unit, a clock (123) is maintained, and the
`unit detects the time when an inhibit period on the
`shared communication resource begins, and the time at
`which it concludes. When access to the shared commu
`nication resource is desired, the unit attempts to access
`the communication resource based on the time at which
`access was desired, as well as the times at which a de
`tected inhibit condition began and concluded. A virtual
`time clock runs only during non-inhibit periods. Access
`to the communication resource is then based on when
`the virtual time clock equals the desired access time.
`13 Claims, 6 Drawing Sheets
`
`
`
`VIDEO
`DISPLAY
`TERINAL
`
`
`
`. CONTROLLER
`
`
`
`
`
`COMUNICATION
`UNIT
`
`f0.
`
`COMMUNICATION 10
`UNIT
`
`
`
`
`
`138
`
`100
`
`39
`
`f35
`
`CONTROLLER
`
`
`
`f37
`
`BASE
`f 36 STATION
`
`COPUTER
`
`IPR2020-00038
`MM EX1018, Page 1
`
`

`

`U.S. Patent
`
`Aug. 25, 1992
`
`Sheet 1 of 6
`
`5,142,533
`
`
`
`
`
`
`
`
`
`101 TINOIIVOINN MW00
`
`
`1.IN?)
`
`IPR2020-00038
`MM EX1018, Page 2
`
`

`

`U.S. Patent
`
`Aug. 25, 1992
`
`Sheet 2 of 6
`
`5,142,533
`
`8T 2 * 5) I „H
`
`
`
`W00 NW8.
`
`SS300W
`
`
`
`
`
`0BA83S38N[] 80 1S30038 NOIIWANGS38
`
`
`
`0NASI (INQ08100
`
`V 2 º 30 I „I
`
`T-T-T-T-T-T-T-T-T-T-I-
`
`
`
`902
`
`}WW}}} W01
`
`|---losM01
`
`IPR2020-00038
`MM EX1018, Page 3
`
`

`

`U.S. Patent
`
`Aug. 25, 1992
`
`Sheet 3 of 6
`
`5,142,533
`
`310
`
`300
`
`SET VIRTUAL TIVE .
`CLOCK=REAL TIME CLOCK
`
`320
`
`START REAL TIVE CLOCK
`
`
`
`
`
`VIRTUAL
`TIVECREAL
`TIVE
`
`YES
`
`360
`
`RUN VIRTUAL TIME CLOCK
`AT RATE = REAL TIME CLOCK
`
`RUN VIRTUAL TIME CLOCK
`AT RATEXREAL TIME CLOCK
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`RESOURCE
`IN RESERyED STATE
`
`STOP WIRTUAL CLOCK
`
`WAIT FOR RANDON
`ACCESS STATE
`
`A 6.3
`
`IPR2020-00038
`MM EX1018, Page 4
`
`

`

`U.S. Patent
`
`Aug. 25, 1992
`
`Sheet 4 of 6
`
`5,142,533
`
`77 6.4
`400
`
`DETERMINE DESIRED
`TRANSI TIVE
`
`PACKET PENDING
`
`START
`
`NEXT
`PACKET
`TO TRANSI
`
`PENDING
`PACKET TO
`TRANSI
`
`RESOURCE
`AVAILABLE FOR
`RANDO, ACCESS
`
`VIRTUAL
`TIME X DESIRED
`RANS! TIVE
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ACCESS
`COMUNICATION RESOURCE
`
`480
`
`IPR2020-00038
`MM EX1018, Page 5
`
`

`

`U.S. Patent
`
`Aug. 25, 1992
`
`Sheet 5 of 6
`
`5,142,533
`
`START
`
`
`
`
`
`SEND
`UNRESERVED
`DATA FACKE
`
`
`
`
`
`520
`
`TRANSIT IN
`RANDO ACCESS SLOT
`
`TRANSMIT RESERVATION REQUEST-520
`
`
`
`
`
`
`
`
`
`
`
`
`
`MONITOR STATUS FEEDBACK
`
`IS
`TIVE SLO, RESERVED
`
`
`
`IS
`RESERVATION
`GRANTED T9. THIS UNI
`
`
`
`TRANSMIT DATA PACKET
`
`RESERVATION FAILED;
`WAIT RANDON RETRY TIME,
`RESUBMIT PACKET FOR TRANSMIT
`
`7766
`
`IPR2020-00038
`MM EX1018, Page 6
`
`

`

`U.S. Patent
`
`Aug. 25, 1992
`
`Sheet 6 of 6
`
`5,142,533
`
`
`
`IS
`UNRESERVED
`DATA
`SLOT
`
`VALID RESERVATION
`REQUESTIN SLOT
`
`IPR2020-00038
`MM EX1018, Page 7
`
`

`

`1.
`
`METHOD FOR CONTROLLING THE
`SCHEDULING OF MULTIPLE ACCESS TO
`COMMUNICATION RESOURCES
`
`FIELD OF THE INVENTION
`This invention relates generally to communication
`systems, including but not limited to methodologies that
`control access by a plurality of competing communica
`tion units to limited communication resources.
`BACKGROUND OF THE INVENTION
`Multiple access communication systems are well un
`derstood in the art. Multiple access communication
`systems are designed to provide access to limited com
`15
`munication resources for a plurality of communication
`units for the purpose of transmitting communication
`messages, referred to as packets. The access methodol
`ogy, referred to as a multiple access protocol, is chosen
`such that some appropriate set of performance con
`20
`straints are met. Typical performance constraints in
`clude efficiency of communication resource use, com
`munication message delay, and other similar factors.
`Multiple access protocols can be regarded as belonging
`to one of two general types, contention and non-conten
`tion.
`Non-contention protocols are designed such that a
`communication unit desiring to send a packet is permit
`ted exclusive use of a communication resource. One
`example of this type of protocol is time-division multi
`30
`ple access (TDMA) where the communication resource
`is divided into a plurality of time frames that are further
`subdivided into a plurality of time slots and each com
`munication unit is assigned exclusive use of one or more
`time slots in each time frame.
`35
`Contention protocols are characterized by communi
`cation units that actively compete with each other to
`gain access to the communication resource. The slotted
`ALOHA protocol is an example of this type of proto
`col. In slotted ALOHA, a communication resource is
`divided into a plurality of time slots. A communication
`unit desiring to send a packet may transmit in a first
`subsequent time slot, taking care not to transmit outside
`of the boundaries of that time slot. If no other communi
`cation unit transmitted in that time slot, the packet
`45
`transmission is considered successful. If, however, one
`or more other communication units transmitted a
`packet in the same time slot, the transmission will usu
`ally fail due to collision.
`Reservation protocols, a sub-class of contention pro
`50
`tocols, are also known. Reservation protocols attempt
`to combine certain aspects of contention and non-con
`tention protocols to provide improved performance for
`a wider variety of communication system conditions. In
`one particular reservation protocol, the Reservation
`55
`ALOHA (R-ALOHA) protocol, like TDMA, the com
`munication resource is divided into time frames that are
`further divided into time slots. When the communica
`tion resource is unused, the protocol operates similarly
`to slotted ALOHA. When a communication unit desires
`to send a packet, it transmits in one of the unused time
`slots, referred to as a randon access slot. If the transmis
`sion is successful, i.e., it does not collide with another
`transmission, the communication unit is permitted ex
`clusive use of the same time slot in subsequent time
`65
`frames, referred to as reserved access slots, until the
`packet is completely transmitted. Thus the initial
`ALOHA transmission results in a subsequent reserva
`
`10
`
`5,142,533
`2
`tion of a communication resource. Note that some
`method offeedback to the communication units regard
`ing the success or failure of initial ALOHA transmis
`sions is necessary in order for this protocol to be effec
`tive.
`R-ALOHA is quite efficient for communication sys
`tems accommodating a wide variety of packet frequen
`cies and sizes. Note, however, that when the communi.
`cation resource in an R-ALOHA system is in the re
`served state, the transmission of random access packets
`is inhibited for all communication units desiring to ac
`cess the resource. Random access packets are held
`pending the release of the resource. Once the resource
`returns to the random access state, the units may trans
`mit any pending random access packets.
`If all the waiting units access the resource as soon as
`the resource becomes available, the packets will all
`collide, with no transmission being successful. It is
`therefore generally beneficial to not have all the units
`with pending random access packets transmit as soon as
`the resource is available. One method that may be used
`to reduce the likelihood of collisions is to have all units
`wait a random time after the channel becomes available
`before transmitting. This method contributes to higher
`overall delays in the delivery of the packets. Further
`more, the delays incurred are not necessarily fairly
`distributed. That is, a unit that had a packet it wished to
`send early on during the time the resource was in a
`reserved state might have to wait for a long random
`delay after the resource becomes available, while a
`packet from another later unit might have little or no
`delay, based on the random delays chosen. Access to
`the resource does not occur on a first-come, first-served
`basis. The overall effect is a large variation in the deliv
`ery delays of packets, with the relative delays experi
`enced by different communication units being unrelated
`to the actual order in which their packets were gener
`ated.
`Accordingly, a need exists for a multiple access
`method that provides increased utilization of a commu
`nication resource by a plurality of communication units
`with widely varying communication requirements, and
`that provides a more fair ordering of access to the com
`munication resource by the plurality of communication
`Its.
`
`25
`
`SUMMARY OF THE INVENTION
`Briefly, according to the invention, a method of pro
`viding a communication unit access to a shared commu
`nication resource is disclosed herein. In the communica
`tion unit, a clock is maintained. The unit detects that an
`inhibit condition on the communication resource will
`subsequently occur, and then determines the time at
`which the inhibit period begins, and the time at which it
`concludes. When access to the shared communication
`resource is desired, the unit attempts to access the com
`munication resource based on the time at which access
`was desired, as well as the times at which a detected
`inhibit condition began and concluded.
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1 comprises a block diagram of a communica
`tion system utilizing the principles of the present inven
`tion.
`FIGS. 2A, 2B, and 2C show a channel format of the
`communication system of FIG. 1 utilizing the principles
`of the present invention.
`
`IPR2020-00038
`MM EX1018, Page 8
`
`

`

`S
`
`5,142,533
`3
`4.
`FIG. 3 is an operation flow chart showing the opera
`Outbound communication packets are suitably for.
`tion of the real-time and virtual-time clocks in the chan
`matted for RF transmission at the base station (130) and
`nel access algorithm of the RF modem of FIG. 1 ac
`transmitted to the communication units (101) via the
`cording to the present invention.
`outbound RF communication channel. Since packets
`FIG. 4 is an operation flow chart of the channel ac
`traversing this communication path have only one
`cess procedure of the RF modem of FIG. 1 according
`source, the host computer (140), the packets are trans
`to the present invention.
`mitted by the base station (130) without contention.
`FIG. 5 is an operation flow chart of the RF modem of
`The RF modem (110) includes an RF receiver (111)
`FIG. 1 according to the present invention.
`that couples to an appropriate antenna (102) via a du
`FIG. 6 is an operation flow chart of the base station of
`O
`plexer (119) to receive RF communication signals and
`FIG. 1 according to the present invention.
`provide a received signal (114). A controller (115) oper
`ates on the received signal (114) in a known manner to
`DESCRIPTION OF A PREFERRED
`separate the user and control data portions of the re
`EMBODIMENT
`ceived signal (114). The user data signal (121) is applied
`Referring to FIG. 1, a block diagram of a communi
`to the video display terminal (120), which processes the
`cation system exemplifying the principles of the present
`user data signal for display to the user.
`invention can be seen as generally depicted by the nu
`Transmit user data (122) from the video display ter
`meral 100. The communication system (100) provides
`minal (120) is applied to the controller (115). A clock
`for radio frequency (RF) communications between a
`(123) provides a clock signal (124) that the controller
`plurality of communication units (101) and a base sta
`20
`(115) uses to note the time at which the transmit user
`tion (130). The base station (130) connects to a host
`data (122) was applied to the controller and also the
`computer (140), to which communication messages
`times during which the communication channel is re
`from the communication units (101) are delivered and
`served. The controller (115) operates in a manner to be
`from which communication messages directed to the
`described later to control transmission of the user data
`communication units (101) are accepted. A typical com
`25
`(122) according to the information contained in the
`munication unit (101) is comprised of a video display
`control data portion of the received signal (114) previ
`terminal (120) and an RF modem (110). The user of the
`ously applied to the controller (115), and, in the random
`communication unit (101) interacts with the video dis
`access case, according to the time at which the user data
`play terminal (120) (or other input device, as under
`(122) was applied to the controller. The controller (115)
`stood in the art) to exchange data messages with the
`30
`appropriately formats the transmit user data (122) and
`host computer (140). The RF modem (110) operates to
`adds appropriate control data to provide the transmit
`appropriately process the communication messages for
`signal (116). The transmit signal (116) is applied to a
`exchange with the base station (130).
`well known RF transmitter (117) that appropriately
`As depicted in FIG. 1, the communication units (101)
`modulates and amplifies the transmit signal (116) for
`are mobile and communicate with the base station (130)
`transmission by the antenna (102) via the duplexer (119).
`via a radio frequency (RF) communication channel.
`The base station (130) includes an RF receiver (131)
`Those of appropriate skill in the art should appreciate
`that couples to an appropriate receive antenna (132) to
`that the present invention may be applied to any com
`receive RF communication signals and provide a re
`munication system where a plurality of communication
`ceived signal (134) to the controller (135). The control
`units share a common communication channel; for ex
`ler (135) operates on the received signal (134) in a
`ample a local area network (LAN). Accordingly, the
`known manner to separate the user and control data
`communication system (100) operates to exchange com
`portions of the received signal (134). As will be de
`munication messages between the plurality of communi
`scribed later, the control data portion of the received
`cation units (101) and a host computer (140) via a com
`signal (134) is processed by the controller to provide a
`mon communication medium.
`45
`return control data signal for transmission to the RF
`The communication messages within the communica
`modem (110). The user data signal (141) is applied to the
`tion system (100) comprise inbound (towards the host
`host computer (140). A transmit user data signal (142)
`computer) and outbound (from the host computer) in
`from the host computer (140) is applied to the controller
`formation and control packets, which are communi
`(135). The controller (135) combines appropriate trans
`cated on the RF communication channel. The informa
`50
`mit control data with the transmit user data (142) to
`tion contained in the communicated packets may com
`form the transmit signal (136) applied to the RF trans
`prise any appropriately formatted data. As described
`mitter (137). The transmitter (137), being synchronized
`herein, an RF communication channel comprises a pair
`of radio spectrum bands, appropriately separated in
`by a timing reference (139), appropriately modulates
`and amplifies the transmit signal (136) for transmission
`frequency, such that one band is utilized for inbound
`55
`by an appropriate transmit antenna (138).
`communications and the other band is utilized for out
`bound communications. In the preferred embodiment,
`Referring to FIG. 2a, the communication channel
`(200), including both the receive and transmit frequen
`the RF communication channel is divided using time
`division multiplexing (TDM) into a plurality of time
`cies, is generally divided into repetitive time frames
`slots. The time slots may be reserved for use by the
`(205) that are further divided into a plurality of time
`communication units. When the inbound communica
`slots (210). The timeslots (210) are used for transmission
`tion channel is not currently reserved, a communication
`of inbound and outbound data packets. In the preferred
`unit may transmit unreserved information packets or
`embodiment, when no reserved inbound user data
`random access packets that include control packets to
`packet is currently being transmitted in a timeslot (210),
`secure reservations for exclusive use of subsequent in
`that inbound time slot may be used by communication
`65
`bound time slots for transmission of information pack
`units (101) to transmit random access control packets
`for the purpose of reserving a subsequent timeslot (210)
`ets. (An unreserved information packet is a self-con
`tained data message transmitted without a reservation.)
`in which to transmit a data packet. Alternatively, the
`
`35
`
`IPR2020-00038
`MM EX1018, Page 9
`
`

`

`5,142,533
`5
`6
`slots may be used for the transmission of unreserved
`mation that supports the operation of the inbound chan
`data packets.
`nel access protocol. The status feedback information is
`FIG. 2b shows exemplary time slot formats for the
`sourced by the base station controller (135) and reflects
`inbound communication channel according to the pre
`the current state of at least one of the inbound time slots,
`ferred embodiment. When a channel is available for
`either random access or reserved access. If the channel
`random access, the inbound time slots are used as ran
`state is reserved, the status feedback information further
`dom access slots (230). The random access slots (230)
`includes a communication unit identifier that permits
`include a guard time field (231) to avoid interference
`communication units (101) to uniquely determine their
`between adjacent time slots. A sync field (232) provides
`slot assignments. This indicator is also used in the access
`information to enable proper slot and bit timing to be
`control algorithm to determined when random access
`10
`recovered at the RF receiver (131). The remainder of
`may be attempted, as described below.
`-
`the packet may then be used for the transmission of a
`The access control algorithm according to the pres
`reservation packet or an unreserved data packet. (233).
`ent invention utilizes at least one time clock (and prefer
`The reservation packet comprises a control message
`ably two) in the communication unit. This time clock
`that indicates to the receiving base station (130) that the
`may include a real-time clock as depicted, or may be a
`RF moden (110) has a data packet to send using re
`counter or any other suitable device or software algo
`served access. An RF modem desiring to transmit a data
`rithm within the controller (115), to indicate or other
`packet in this mode will transmit a reservation packet in
`wise allow the calculation of the passage of time. The
`the random access slot (230), according to the access
`clock is used to keep track of those times when the
`control algorithm of the present invention. The reserva
`communication resource is unavailable for random ac
`20
`tion packet contains at least an identifier and informa
`cess, because of reserved communications. This infor
`tion regarding data packet length. The identifier permits
`mation is then used to control subsequent random ac
`the base station to identify the requesting communica
`cess to the resource by the communication unit when
`tion unit (101). Data packet length relates to the size of
`the resource does become available.
`the packet that the RF modem desires to send. The base
`Referring to FIG. 3, the operation and use of the
`25
`station can use this information to determine how many
`access control clocks in the communication units (115),
`time slots are required for transmission of the packet.
`in conjunction with the flow chart 300, is described for
`Upon receiving a valid reservation packet, time slot
`the preferred embodiment. In the communication unit,
`(210) configuration may be switched from random ac
`there are two time clocks hereafter referred to as the
`cess to reserved access format (240). Guard time and
`virtual time clock and the real time clock. Initially, the
`30
`sync fields are again provided. A data packet field (241)
`times on the two clocks are set to be equal (320). The
`real time clock runs continuously at a constant rate
`contains the user data information to be delivered to the
`host computer (140). (The size of the user data informa
`(330). The virtual time clock runs at the same rate as the
`tion may dictate that several reserved access time slots
`real time clock (350), except in those cases where it is
`(240) are required to completely transmit the packet. To
`determined to have fallen behind the real time clock
`35
`accommodate messages requiring more than one re
`(340), in which case it operates at a rate greater than the
`served access time slot, one or more time slots may be
`real time clock rate (360).
`reserved in multiple frames.) The reserved time slots
`The controller monitors the outbound resource for
`maintain the reserved access configuration (240) until
`reservation assignments. From these, the controller can
`the transmission of the data packet is complete, after
`determine that an inhibit condition will occur (i.e., the
`which the timeslots revert to the random access format.
`communication resource will soon be used by another
`Whenever a time slot is designated for reserved ac
`communication unit). Eventually, the communication
`cess, only the single communication unit (101) for
`resource will be place in the reserved access state, and
`whom the time slot was reserved is permitted to trans
`the controller will detect this condition. The state of the
`mit packets in that time slot. Other units wishing to
`virtual time clock is controlled such that when the re
`access the channel during this time are inhibited, and
`source is determined to be in the reserved access state
`may attempt access to the channel only when the slot is
`(370), the virtual time clock is stopped (380). The real
`re-designated as random access.
`time clock, meanwhile, keeps running, so that the vir
`As noted above, a random access time slot (230) can
`tual time clock falls behind the real time clock by an
`amount corresponding to the reserved period. When
`also be used to transmit a single packet or user data
`50
`information in the reservation request field (233). An
`the reserved period ends, and the resource is again
`RF modem desiring to send a data packet without a
`available for random access (390), the virtual time clock
`reservation may transmit an unreserved data packet in
`is started again, and runs at the appropriate rate deter
`the random access slot (230). When a valid unreserved
`mined by block 340.
`data packet is received at the base station (130), it is
`During the time that the resource is in a reserved
`processed as received user data, and the time slot (210)
`state, and the virtual time clock is stopped, all random
`configuration continues to be random access. Whenever
`access packets that would otherwise be sent during this
`a time slot is designated for random access, any of the
`period are inhibited from being transmitted. All com
`plurality of communication units (101) are permitted to
`munication units in the system operate in the same man
`transmit reservation or unreserved data packets in that
`ner. Therefore, the total time that the virtual time
`clocks fall behind due to reserved periods represents a
`time slot, as described below in more detail.
`system-wide backlog of pending random access pack
`Referring to FIG.2c, the outbound time slot format
`(250) includes a sync field, status feedback field (251),
`ets. If all the pending random access packets were to be
`and a data packet field. The sync field supports the same
`transmitted as soon as the channel returned to the ran
`purpose as that described in association with the in
`dom access state, they would all collide. Instead, ac
`65
`bound channel configurations. The data packet field
`cording to the present invention, the backlog may be
`comprises user data information from the host computer
`cleared in an orderly, first-come, first-served manner.
`(140). The status feedback field (251) comprises infor
`When a packet arrives at the RF modem, the value of
`
`55
`
`15
`
`45
`
`IPR2020-00038
`MM EX1018, Page 10
`
`

`

`10
`
`15
`
`25
`
`5,142,533
`7
`8
`nication outages due to fading or intervals during which
`the real time clock is noted and stored. If the virtual
`time clock value is less than this time, packet transmis
`the communication unit is powered off. To obtain all of
`sion is inhibited. The virtual time clocks begin running
`the benefits of the present invention, all communication
`as soon as the channel becomes available for random
`units (101) should have a substantially similar knowl
`access. The communication units are then allowed to
`edge of the state of the backlog of the communication
`transmit their pending random access packets only
`system. Nevertheless, due to outage periods, it is possi
`when the virtual time equals the stored real time at
`ble for some of the communication units to have sub
`which the packets were to be sent. In order for the
`stantially incorrect knowledge of the backlog state as
`virtual time clock to eventually catch up with the real
`gained through observation of the communication ac
`time clock, it must run at an increased rate until it is
`tivity. Therefore, it is beneficial in these circumstances
`caught up. In this manner, the packets generated during
`for the base station controller (135) to maintain a real
`the inhibit interval are transmitted, over a generally
`time clock and virtual time clock in a substantially simi
`compressed interval, when the resource becomes avail
`lar manner to that described for the communication unit
`able again. Importantly, the original ordering of packet
`controller (115). These base station clocks would serve
`transmissions throughout the system is maintained in a
`as the master clocks for the communication system
`distributed manner, and random rescheduling delays are
`(100). Via appropriate control messages transmitted
`not required.
`quasiperiodically by the base station, the current values
`Along these lines, and referring to FIG. 4, the partic
`of the master clocks can be communicated to the con
`ular operation (400) of the communication unit control
`munication units (101). These values are then used to set
`ler (115) will be described for the process of accessing
`the respective clocks of the communication unit, thus
`20
`the resource. The controller begins by detecting when
`insuring a substantially similar knowledge of the state of
`the backlog of the communication system.
`the communication unit has a new random access
`packet to send (420). (This packet may be either a reser
`In yet another embodiment, only the difference be
`vation request or an unreserved data packet.) When this
`tween the master real time clock and the master virtual
`occurs, the desired transmit time (i.e., the current time)
`time clock is communicated to the communication units
`of the packet is noted (430). This time represents the
`(101).
`time that the packet transmission would have been at
`Referring to FIG. 5, the operation (500) of the com
`tempted, if not for present or past periods during which
`munication unit controller (115) will now be described
`random access was inhibited. If no new packets are
`for the process of sending a packet after access to the
`present the controller determines whether any previ
`resource has been obtained.
`30
`ously unsent packets are still pending (440). If not, the
`The controller takes different actions depending on
`process reinitiates. When, however, a current or pend
`whether it intends to send a reservation request or an
`ing packet exists, the unit determines availability of the
`unreserved data packet (510). This determination may
`communication resource for random access (450). If not
`be made on the basis of data packet size or appropriate
`available, the transmission is inhibited and the packet
`control signals received from the user. If an unreserved
`put on pending status (460). If the resource is available
`data packet is to be sent, the controller transmits the
`for random access, the unit then compares the desired
`unreserved data packet in the available random access
`transmit time for the packet to the time on the virtual
`time slot (520).
`time clock (470). If the virtual time is less than the de
`If a reservation request is to be sent, the controller
`sired transmit time, this indicates that the system back
`transmits instead the reservation request (520). The
`log time, created during periods of random access un
`controller then begins to monitor status feedback fields
`availability, has not yet advanced a sufficient amount to
`on the outbound communication channel (530). First it
`allow transmission of the packet. The packet transmis
`determines if the time slot is now reserved (540). If not,
`sion is therefore inhibited, and put on pending status
`the reservation attempt has failed, and after waiting an
`appropriate length of time (570), the data packet is
`(460). The communication unit continues to monitor the
`status of pending packets (440) until the resource is
`resubmitted for access to the channel. If the time slot is
`available for random access, and the virtual time is
`reserved, the identifier portion of the status feedback
`equal to or greater than the desired transmit time. At
`field is examined to determine if the reservation has
`this point access to the shared communication resource
`been granted to this communication unit (550). If the
`may be attempted (480).
`time slot is reserved for this unit, the user data packet
`Another embodiment of the present invention in
`may then be transmitted in the reserved time slot (560).
`cludes dynamic selection of the virtual time clock rate.
`If the reservation is not for this unit, the reservation
`The selected virtual time clock rate may be in part a
`attempt has failed and the controller proceeds (570) to
`function of detected activity on the communication
`resubmit the data packet.
`channel or other appropriate observations of communi
`Referring to FIG. 6, the operation (600) of the base
`55
`cation system behavior. The selection of the virtual
`station controller (135) will now be described. The
`clock rate may be effected by the communication unit
`controller begins by configuring the inbound time slot
`controller (115) or by the base station controller (135).
`for random access (620). The controller then waits to
`When selection is made by the base station controller
`receive inbound random access data transmissions from
`(135), appropriate control data is transmitted to the
`the communication units (630). When data is received in
`communication unit (101) to inform the communication
`the random access slot, the controller determines if the