US20060092910A1 - Method and apparatus for organizing and scheduling multimedia data transfers over a wireless channel - Google Patents

Abstract

A radio frequency communications system (100) includes wireless terminals (102) and base sites (104). The wireless terminals communicate with the base sites over a radio frequency channel (106). The base sites are interconnected to each other and other network elements via a packet network. The communication system has a radio frequency channel (400) with time slots (406, 408) for transmission of both delay-sensitive data, such as streaming audio and video, and non-delay-sensitive data. A method and apparatus are provided for determining whether a time slot in the radio frequency channel is to be allocated to delay-sensitive data or non-delay-sensitive data (704, 706, 708). Each packet of data transmitted over the wireless channel has a type of service field (900). The type of service field has a precedence or priority value (902) and a service type (904). The priority values are used to determine which packet should be transmitted across the radio frequency channel next and the service type determines the transmission protocol.

Description

FIELD OF THE INVENTION
• The invention generally relates to communications systems, and in particular, to a method and apparatus for organizing and scheduling multimedia data transfers over a wireless channel in order to support delay-sensitive, streaming data, such as audio and video data, and non-delay-sensitive data, such as Web pages.
BACKGROUND OF THE INVENTION
• Wireless data communication systems for transmitting multimedia data, including audio, video and other data, are known. Recently, the explosion in the use of the Internet has dramatically increased multimedia data communication needs, including wireless data communication needs. Internet communications follow a packet-based protocol with wide variance in the size and frequency of packets. Generation of Internet packets generally occurs without regard to the actual physical networks that will carry the data. While this packet-based communication has great advantages, it presents numerous challenges for the efficient transmission of data over a particular physical network.
• Known wireless data communication systems that support Internet access are typically a “retrofit” of Internet packets on top of an existing physical network. Unfortunately, these retrofits do not typically efficiently use bandwidth. And, performance is either sacrificed or uncontrolled, where performance includes parameters such as delay and jitter. Most existing systems over engineer the available bandwidth to accommodate a predefined maximum amount of traffic. Although this may be acceptable in wired networks, the limitations on wireless networks do not permit such a luxury. While all wireless packetized data presents some challenge, packetized audio and video streaming data is particularly challenging since the performance, namely, delay and jitter, may inhibit effective communications, in particular in the case of a two-way conversation.
• Therefore, a need exists for a new paradigm in the communication of multimedia data over a wireless channel.
BRIEF DESCRIPTION OF THE DRAWINGS
• FIG. 1 is a block diagram of a wireless communications system in accordance with the present invention.
• FIG. 2 is a block diagram of a gatekeeper for controlling wireless multimedia communications in accordance with the present invention.
• FIG. 3 is a block diagram of a radio base site for wireless multimedia communications in accordance with the present invention.
• FIG. 4 is a schematic diagram illustrating an incoming and outgoing wireless channel in accordance with the present invention.
• FIG. 5 is a flow chart illustrating a method for determining and reserving bandwidth allocation over a wireless multimedia channel in accordance with the present invention.
• FIG. 6 is a flow chart illustrating a method for determining how a time slot in a wireless channel will be allocated in accordance with the present invention.
• FIG. 7 is a flow chart illustrating a method for determining whether a delay-sensitive slot is needed in a wireless channel in accordance with the present invention.
• FIG. 8 is a flow chart illustrating a method for determining whether an acknowledgement slot is needed in a wireless channel in accordance with the present invention.
• FIG. 9 is a schematic diagram illustrating a type of service field that is used to prioritize the transmission of packets in accordance with the present invention.
• FIG. 10 is a chart listing precedence values used to prioritize the transmission of packets in accordance with the present invention.
• FIG. 11 is chart listing service types defined by a type of service field and explaining how the service types are transmitted over a wireless channel in accordance with the present invention.
• FIG. 12 is a flow chart illustrating a method for assigning precedence values and service types to packets in accordance with the present invention.
DESCRIPTION OF THE PREFERRED EMBODIMENTS
• Briefly, in a wireless communication system having a wireless channel with time slots for transmission of both delay-sensitive data and non-delay-sensitive data, a method and apparatus are provided for determining whether a time slot in the wireless channel is to be allocated to delay-sensitive data or non-delay-sensitive data. First an ideal slot separation is determined for each delay-sensitive application using the wireless channel. Then, for each delay-sensitive application, a number of time slots since a time slot was granted to the delay-sensitive application is calculated. The number of slots since a time slot was last granted is compared with the ideal slot separation for the delay-sensitive application. A delay-sensitive time slot is allocated if a delay-sensitive application has the number of slots since a time slot was granted equal to or greater than the ideal slot separation for that delay-sensitive application. The delay-sensitive data time slot is granted to the delay-sensitive application that has its number of slots since a slot was granted the most above the ideal slot separation. That is, the delay-sensitive application that has waited the longest beyond its ideal slot separation is granted the delay-sensitive time slot on the wireless channel. Delay-sensitive time slots are granted on the wireless channel until there are no delay-sensitive applications at or beyond their ideal slot separation, meaning no delay-sensitive slot should be granted.
• When no delay-sensitive slots are needed, non-delay-sensitive data slots are granted. Preferably there are non-delay-sensitive slots for acknowledgements, random access and nonspecific non-delay-sensitive data. After a determination that there are no delay-sensitive slots needed, a determination is made as to whether any acknowledgement slots are needed. Acknowledgement slots are provided in the wireless channel to acknowledge transmitted packets. If no acknowledgement slots are currently needed in the wireless channel, then a determination is made as to whether any nonspecific non-delay-sensitive data slots are needed. If needed, nonspecific non-delay-sensitive data slots are granted on the wireless channel unless a maximum time period between random access slots has occurred. Random access slots are the means by which wireless terminals request channel resources, i.e., delay-sensitive slots and non-delay-sensitive slots. Therefore, random access slots must be provided periodically to guarantee access to the wireless channel.
• Each packet has a precedence or priority value and a service type. The priority values are used to determine among multiple packets waiting for transfer, the packet that should be transmitted next. Where multiple packets are suitable for a particular transmission, packets with the highest priority values are transmitted first. The service types are used to determine an error protocol and a channel access method for the packet. The priority values are set based on the content of the packet. For example, emergency data may be given priority over non-emergency data of the same type. Delay-sensitive data, such as audio and video data, may be given priority over non-delay-sensitive data. A default value of priority is provided for backward compatibility with software and systems not using priority values. Preferably, five service types are defined corresponding to the five service types used in an Internet protocol: (1) best effort; (2) minimize delay; (3) maximize throughput; (4) maximize reliability; and (5) minimize monetary cost.
• FIG. 1 is a block diagram of a preferred embodiment of amultimedia communication system100 in accordance with the present invention.System100 includeswireless terminals102 andradio base sites104.Wireless terminals102 communicate over the air withbase sites104. More specifically,wireless terminals102 andbase sites104 use a radio frequency communications channel, illustrated byarrows106, to communicate multimedia data, for example, audio, video and other data, to and from each other.
• Base sites104 are radio frequency transmitters and receivers that communicate withwireless terminals102. In addition,base sites104 are connected to a network of other elements to facilitate the transmission of data, including multimedia data. As shown inFIG. 1,base sites104 are connected torouters108 for the communication of data. Other network elements are interconnected torouters108 for the transmission of data throughout the network. InFIG. 1, agatekeeper112, aWeb server114, avideo server116 anddispatch station118 are shown interconnected to form a network. These network elements may form a closed private network, such as an intranet and may include access to a public network such as the Internet120.Communication links110 couple the various routers and network elements to each other. Any suitable communication links or trunks suffice forcommunication links110. In a preferred embodiment,communications links110 are Ethernet or other communication links, such as T1 communication links.
• Gatekeeper112 is preferably a computer that provides control and management functions associated with the wireless channel used for communication betweenwireless terminals102 andbase sites104.Dispatch station118 is preferably a computer that provides access for the dispatcher role associated with the wireless communication systems used for communication betweenbase sites104 andwireless terminals102.Web server114 is preferably a computer that provides a data communications function such as the provision and access to Web pages.Video server116 is preferably a computer that provides video services to network elements, includingwireless terminals102 anddispatch station118.
• Wireless terminals102 preferably include a computer122 coupled to a modem124. Modem124 preferably is connected to anantenna126 to radiate and receive radio frequency signals to implement the wireless communication channel betweenwireless terminals102 andbase sites104. Preferably computer122 implements an Internet protocol which generates packets that are transferred to modem124. Modem124 then converts the IP packets into packets or blocks for transmission over the wirelesschannel using antenna126 and an associated protocol for the wireless channel.
• In accordance with the present invention, the wireless channel provided for communication betweenwireless terminals102 andbase sites104 is managed in a manner to provide efficient bandwidth for diverse communications betweenwireless terminals102 andbase sites104. In particular, the wireless channel is managed to provide delay-sensitive data with guaranteed bandwidth over the channel and to accommodate non-delay-sensitive data over the same channel. The provision of these functions is discussed below with respect to the preferred embodiments.
• FIG. 2 is a block diagram of a preferred embodiment ofgatekeeper112.Gatekeeper112 is preferably a server-class, processor-based system.Gatekeeper112 includes aprocessor202, amemory204 and anetwork interface206.Processor202,memory204 andnetwork interface206 are coupled together for the communication of data and commands between these components.Processor202 executes a program stored inmemory204 to implement various functions, including management and control functions to determine and allocate resources associated with a wireless channel used for communication betweenwireless terminals102 andbase sites104.Processor202 communicates withnetwork interface206 for the receipt and transmission of data over the associated network.Network interface206 includes a connection tocommunication link110.
• In a preferred embodiment,processor202 preferably is a central processing unit, microprocessor, microcontroller, digital signal processor, or any combination of these.Memory204 preferably includes volatile and non-volatile memory, including dynamic random access memory, and disk storage. Preferably,network interface206 implements a TCP/IP network interface for the transmission of Internet protocol (IP) packets
• FIG. 3 is a block diagram of a preferred embodiment of abase site104 in accordance with the present invention.Base site104 includesprocessor302,memory304,network interface306,wireless modem308 andantenna310.Processor302,memory304,network interface306 andwireless modem308 are coupled or interconnected together for the communication of data and commands between these components.Processor302 executes programs stored inmemory304 for functions of the base site, including control overwireless modem308, which provides control over the wireless channelcoupling base site104 withwireless terminals102.Antenna310 receives and radiates radio frequency signals to implement the wireless channel betweenwireless terminals102 andbase sites104.Antenna310 is connected towireless modem308.Network interface306, under control ofprocessor302, provides access forbase site104 to other network elements.Network interface306 is connected tocommunication link110.
• FIG. 4 is a schematic diagram illustrating a preferred wireless radio frequency channel in accordance with the present invention.Wireless channel400 preferably includes anoutgoing channel402 and anincoming channel404.Outgoing channel402 represents the transmission of data from abase site104 over the air to a plurality ofwireless terminals102.Incoming channel404 represents a transmission from a plurality ofwireless terminals102 to abase site104. As an alternative to using a separate incoming and outgoing channel, time division multiplexing may be used to accommodate both incoming and outgoing communications in a single channel. Also, frequency division and multiplexing are alternatively applied to the channel.
• Outgoing channel402 is divided intoslots406, which occur contiguously over a period of time. Similarly,incoming channel404 is divided intoslots408, which occur contiguously over a period of time. In the preferred embodiment,outgoing channel402 has 100 to 400 slots per second occurring where each slot is capable of transmitting about 206 bytes of data.Incoming channel404 preferably has characteristics that matchoutgoing channel402. In a preferred embodiment, a frequency of 746 to 806 megahertz (MHz) is used forwireless channel400.
• To facilitate orderly and efficient use ofchannel400 bywireless terminals102 andbase sites104,slots406,408 are preferably organized into slot types, which define a type of data that is transmitted in a particular slot. In contrast to conventional time-division multiplexed channels,slots406,408 are not strictly periodically assigned to a particular device or function, rather the assignment of slot types is made selectively and dynamically in a manner to flexibly accommodate varying media and data types. The four slot types defined in a preferred embodiment are random access slots, acknowledgement “ACK” slots, delay-sensitive slots, and non-delay-sensitive slots.
• The random access slots are included inincoming channel404 to allowwireless terminals102 to reserve or request delay-sensitive slots and non-delay-sensitive slots. Random access slots are also used to transmit data. The random access slots are preferably a slotted-aloha type of slot that is used bywireless terminals102 as a point of access. In other words, the random access slots are used by wireless terminals to alert a device managing the channel that the wireless terminal has data to be transferred over another slot type. The random access slots are, as the name suggests, randomly accessed by wireless terminals when available, without any arbitration. This allows for the occurrence of collisions between contending wireless terminals.
• The delay-sensitive slots carry, as the name suggests, delay-sensitive, streaming data, such as a video data stream or an audio data stream. The non-delay-sensitive slots are allocated for data that is not delay-sensitive, for example Web site pages and the like. Non-delay-sensitive data typically is tolerant of some delay. The non-delay-sensitive slots are used for file transfer and the transmission of other error-intolerant data. The ACK slots are used for thewireless terminals102 andbase sites104 to acknowledge safe receipt of packets sent overchannel400.
• Eachwireless terminal102 andbase site104 has a unique media access control (MAC) address that identifies the device. Since there is competition among the wireless terminals to access theincoming channel slots408, access must be controlled in some manner. In a preferred embodiment, a channel scheduler is implemented usingprocessor302,memory304 andwireless modem308 to orderly schedule access toincoming slots408 bywireless terminals102. More specifically, the channel scheduler determines the allocation of delay-sensitive slots, non-delay-sensitive slots, and ACK slots toparticular wireless terminals102. Most preferably, theoutgoing channel402 includes designations within its slots that specify whichincoming channel slots408 may be used by aparticular wireless terminal102. That is, awireless terminal102 determines whichincoming slots408 it may use by decoding this information from a portion of theoutgoing channel402. The random access slots are not dedicated to aparticular wireless terminal102, and therefore may be accessed by anywireless terminal102. If more than onewireless terminal102 transmits on a random access slot, a collision occurs, and the access is not subsequently acknowledged. This requires the transmittingwireless terminals102 to retransmit on another available random access slot, preferably with some random time delay to reduce subsequent collisions.
• Theoutgoing channel402 has only one transmitter,base station104. Therefore, there is no contention for transmission onoutgoing channel402. Eachwireless terminal102 that is communicating withchannel400 is required to listen to a portion ofoutgoing channel402 and respond to data directed to it, as determined by the MAC address.
• A method for allocating or reserving resources onchannel400 for delay-sensitive applications such as audio and video transmission, is described below with respect toFIG. 5. This method is described below in the context of a preferred embodiment described above with respect toFIGS. 1-4.
• First a delay-sensitive application's requirements are sent to a bandwidth management device (500). This preferably occurs by an application onwireless terminal102 initiating the transfer of data to other network elements. An exemplary application is an H.323 multimedia call that needs to be placed by a computer122 of awireless terminal102. In accordance with the H.323 standard, certain requirements for the application, such as multimedia call type, codec, codec parameters and traffic profile are generated per the application. If the data transmission is to be directed over the wireless channel, then the modem124 must initiate an access to the channel. Preferably, the communications between the physical network, modem124, and the H.323 application occur via a layered network protocol.
• Preferably, the access to the channel to transfer the application requirements requires that thewireless terminal102 gain access to theincoming channel404. To gain access,wireless terminal102 must transmit on a random access slot the requirements for the desired application. If the random access slot transmission of the application requirements is successful, that is, there are no collisions, then the request is routed togatekeeper112, which preferably serves as the bandwidth management device. Another network element, such asbase site104, alternatively serves as the bandwidth management device.
• Aftergatekeeper112 receives the application requirements (500),gatekeeper112 converts the application requirements to channel requirements (502). This requires converting the specified application requirements, such as multimedia call type, codec, codec parameters and traffic profile, into channel resources, that is, slots per second, that will be required for the delay-sensitive application. The actual mapping of application requirements to channel requirements varies. Any suitable alternative is available for converting the application requirements to the channel requirements, including a look-up table indexed on an application requirement or an algorithm to dynamically convert the application requirements to the channel requirements. Preferably, a prior analysis of application requirements or exemplary applications is used to provide a fixed mapping from application requirements to channel requirements, that is, slots per second required.
• After the channel bandwidth requirement, in terms of slots per second, is determined (502), the bandwidth management device,gatekeeper112, determines if the required number of slots per second is available onchannel400.Gatekeeper112 stores data relating to the amount of bandwidth, or slots per second, available onchannel400. A comparison of the amount of bandwidth being currently used with the amount of bandwidth desired for the new delay-sensitive application determines whether there is bandwidth available on the channel. If the channel requirements cannot be met with the available bandwidth, then the applications request for transmission over the network is denied (506). This terminates the request and call (508), leaving the wireless terminal with the option to retry the request.
• On the other hand, if the required channel bandwidth is available (504), then the needed bandwidth, that is, slots per second, is reserved on the channel (510). A method by which bandwidth is actually reserved varies depending upon the actual implementation. A preferred method for allocating the required bandwidth is discussed in detail below with respect toFIG. 6. In summary, the preferred method of allocating the delay-sensitive bandwidth requires that a channel scheduler allocate the requesting wireless terminal a certain number or percentage of delay-sensitive slots in the incoming channel to support the application.
• After the bandwidth is reserved on the channel (510), the application set up can be completed such that the application will proceed with the call (512). Continuing with the H.323 example of an audio/video call, aftergatekeeper112 determines that bandwidth is available (504) and has been reserved (510), a message is sent to thewireless terminal102 that initiated the request (500). The H.323 application is notified that it should proceed with the call. This message fromgatekeeper112 is sent towireless terminal102 via the outgoing channel frombase site104.
• After application set up is complete (512), the application proceeds with the call and thesystem100 manages the bandwidth accordingly. More specifically, the application on the wireless terminal generates IP packets in accordance with the application and without regard to the channel requirement. These IP packets generated by computer122 are transferred to modem124 for formatting and transmission over theincoming channel404 ofwireless channel400. Typically the IP packets generated by the application must be transmitted in multiple slots overwireless channel400. Modem124 repackages the IP packets into slots for the wireless channel. After the data is repackaged for the channel slots, thewireless terminal102 transmits the channel specific packets in the delay-sensitive slots that are granted to thatparticular wireless terminal102.
• As the call proceeds and packets are transmitted by the wireless terminal to thecommunication system100, thecommunication system100 preferably continually assesses the traffic and channel requirements (500). That is,gatekeeper112, the bandwidth management device, preferably keeps or receives a count of the actual slots per second used by the application. This reflects the actual channel utilization used by the application. This actual channel utilization is preferably compared with the predicted channel bandwidth that is allocated or reserved to determine if an adjustment should be made to the bandwidth allocation. In accordance with this comparison adjustments are preferably made.
• In a preferred embodiment as described above, where channel slots are allocated on a device basis, if additional applications require delay-sensitive slots for an application on the device, then a new bandwidth request must be made (518). This new bandwidth request mirrors the request made instep500, described above. Based on the new bandwidth request, new channel requirements are determined (502) and the call is allowed to proceed if the new bandwidth request can be satisfied (504). If the additional bandwidth is not available, the request for a call is denied (506,508). If the new bandwidth request can be satisfied, then the bandwidth is reserved (510); the application is set up (512); and the call proceeds (514).
• FIG. 6 is a flow chart illustrating a method for determining the type of slot that will be scheduled next on theincoming channel404. More specifically, the channel scheduler determines whether the next slot in the incoming channel should be scheduled as a delay-sensitive slot, a non-delay-sensitive slot, an ACK slot or a random access slot. This slot scheduling determines the channel resources that are dedicated to the slot type. Also, the method guarantees that the allocated or reserved bandwidth for delay-sensitive, streaming data such as audio and video, is maintained.
• First the channel scheduler determines whether a delay-sensitive slot should be scheduled next to maintain an ideal slot separation based on the allocated or reserved channel bandwidth for delay-sensitive applications (600). The ideal slot separation is calculated by dividing the total number of slots that occur in one second on the incoming channel by the number of slots per second allocated or reserved for delay-sensitive applications for a particular wireless terminal. For example, for an incoming channel running at 100 slots per second, a wireless terminal that has delay-sensitive applications requiring 20 slots per second results in an ideal slot separation of five slots. Delay-sensitive slots should be scheduled to meet the ideal slot separation for a wireless terminal or if the time has passed for a delay-sensitive slot to be allocated to maintain the ideal slot separation, then a delay-sensitive slot is needed (602). A preferred method for calculating ideal slot separation and determining whether a delay-sensitive slot is required is discussed below with respect toFIG. 7. If a delay-sensitive slot is needed (602), then a delay-sensitive slot is assigned to the next available slot on the incoming channel404 (604). The method then restarts to determine what the next slot should be (606).
• If a delay-sensitive slot is not required (602) then the channel scheduler preferably determines whether an acknowledgment slot is needed (605). The channel scheduler is aware of whether a particular transfer during a slot represents the completion of an application packet, such as an IP packet. For IP packets that require an acknowledgement, the channel scheduler notes when the last slot of the packet data is transmitted and hence knows that an acknowledgement slot should be allocated to acknowledge receipt of the packet. If an acknowledgement slot is required (607), then the next slot is assigned as an acknowledgment slot (608). After the slot assignment is made, the method restarts for a determination of the next slot type (610).
• If no acknowledgment slot is needed (607) then the channel scheduler determines whether there are any non-delay-sensitive slots needed (612). The scheduler is aware of thewireless terminals102 requirements for non-delay-sensitive transfers by virtue of the requests to send non-delay-sensitive transfers, which requests are made over the random access slots. If no outstanding non-delay-sensitive requests are awaiting transfer, then the scheduler knows there are no non-delay-sensitive slots needed, and therefore, assigns the next slot as a random access slot (614). After assigning the random access slot the method restarts to determine the next available slot (616).
• If on the other hand, there are non-delay-sensitive slots needed by a wireless terminal, then the scheduler determines whether a maximum random access slot separation has been met (618). The maximum random access slot separation is a predetermined number of non-delay-sensitive slots that may occur before a random access slot is granted. The maximum random access slot separation is used to insure that random access slots, which serve as the point for initiating access by wireless terminals, occur at regular intervals over the incoming channel. If the maximum random access slot separation has not been met (618), then the next slot is assigned a non-delay-sensitive slot (620). After this slot assignment, the method returns to start to determine the next slot (622). On the other hand, if the maximum random access slot separation has been met (618) indicating that the maximum period between random access slots has occurred, then a random access slot is assigned (624). After this slot assignment is made, the method restarts for a determination of the next slot (626).
• In a preferred embodiment of the invention, the maximum random access slot separation is stored by the channel scheduler and a counter is initialized to zero after any random access slot is granted. The random access slot counter is incremented by 1 for every non-delay-sensitive slot that is granted after the random access slot is granted. A comparison between the random access slot counter and the maximum random access slot separation value is made to determine whether the maximum random access slot separation has been met. When the maximum random access slot separation is met, then a random access slot is assigned, rather than a non-delay-sensitive slot, as discussed above.
• FIG. 7 is a flow chart illustrating a preferred method for determining whether a delay-sensitive slot is needed on the incoming channel as described insteps600 and602 ofFIG. 6. First, a counter is established for each wireless terminal with delay-sensitive data (700). As discussed above with respect toFIG. 5, wireless terminals that need to transmit delay-sensitive data, such as audio and video data, receive an allocation of channel bandwidth in accordance with the applications requirements.
• Each counter for a wireless terminal is initialized to zero when the channel bandwidth is allocated or reserved for that terminal (702). The ideal slot separation for each terminal is calculated based on the reserved channel bandwidth (704). The ideal slot separation for a terminal is calculated by dividing the total number of slots that occur in one second on the incoming channel by the number of slots per second reserved or allocated to a particular terminal (seeFIG. 5).
• Each counter for each terminal is incremented by one for each slot that occurs on the incoming channel (706). That is, each counter keeps up with the number of slots occurring on the incoming channel since a slot was granted to the particular wireless terminal. For each slot allocation, the channel scheduler compares each terminal's counter with the terminal's ideal slot separation (708). If none of the terminal's counters is equal to or greater than the terminal's ideal slot separation (710), then no delay-sensitive slot needs to be scheduled by the channel scheduler (712). (Seestep602 ofFIG. 6).
• If, on the other hand, any terminal's counter is equal to or greater than the terminal's ideal slot separation (710), then a delay-sensitive slot should be scheduled for the terminal that has its counter value equal to or greater than the ideal slot separation (714). It is possible that more than one wireless terminal will have its counter equal to or greater than the terminal's ideal slot separation at any slot. In this case, the channel scheduler preferably selects one of the terminals to be assigned the delay-sensitive slot. Most preferably, a channel scheduler selects the terminal that has a counter value that exceeds its ideal slot separation by the greatest amount. Ties are resolved by any suitable method that guarantees fair access.
• For the wireless terminal that is granted the delay-sensitive slot, its counter is updated or re-initialized with the difference obtained from subtracting the ideal slot separation for that terminal from the counter value at the time the delay-sensitive slot was granted (716). In other words, the counters keep a count of the slots occurring since the last granted slot for a terminal. Once a terminal is granted a slot, the counter must be reset. To accommodate situations where a terminal's counter exceeds the ideal slot separation due to contention from other terminals, the counter is reset with a value that accounts for the wait time for the terminal, which allows the counter to maintain the ideal slot separation. For example, if a wireless terminal's ideal slot separation is 10 and due to contention, the counter for that terminal reaches 12 prior to the terminal being granted a slot, then after a slot is granted to the terminal, the counter is reset with a value of 2 (12-10) such that the new counter value is used to attempt to readjust the time for the next granted slot so that the average time is close to the ideal slot separation. After the delay-sensitive slot is assigned, the next slot assignment is determined (718).
• FIG. 8 is a flow chart illustrating a method for determining whether an ACK slot is needed for the incoming channel as described insteps605 and607 ofFIG. 6. First, the channel scheduler determines whether an incoming slot includes an end of packet indication for a packet requiring an acknowledgment slot (800). For each end of packet slot found that requires an ACK slot, an acknowledgement slot delay counter is initialized with a value of zero (802). Each acknowledgement slot delay counter is incremented for each slot allocated on the incoming channel (804). That is, the acknowledgment slot delay counter counts the number of slots occurring since a scheduler determined an acknowledgment slot was required.
• As each slot is allocated on the incoming channel, a comparison is made of the acknowledgment slot delay counters with an acknowledgment slot time out value (806). The acknowledgement slot time out value is a predetermined value entered into the system. The acknowledgement slot time out value reflects an ideal time for acknowledgments to be made. If no acknowledgement slot delay counter has reached the acknowledgement slot time out value (808), then no acknowledgement slot needs to be scheduled on the incoming channel. If on the other hand, an acknowledgment slot delay counter is equal to or greater than the acknowledgement slot time out value (808), then an ACK slot should be scheduled on the incoming channel (812). After an acknowledgment slot is granted for a corresponding acknowledgement slot delay counter, then the counter is stopped or ignored (814).
• FIG. 9 is a schematic diagram illustrating a preferred type of service field that is used in Internet packets in accordance with the present invention. An 8-bit type ofservice field900 is partition such that three bits are use for aprecedence value902 and four bits are use for aservice type904. A type of service field is defined by Internet protocol standards. In particular IPv4 defines a type of service field for inclusion in Internet packets. However, the standard does not completely specify a set of precedence values that are applicable for sending time-sensitive (delay-sensitive), streaming data and non-time-sensitive data. In accordance with the invention, the precedence values are defined in a manner to set priority levels applicable to time-sensitive, streaming data, such as video and audio, as well as emergency and other data. In addition, IPv4 defines five different service types. These service types are defined as minimize delay, maximize throughput, maximize reliability, minimize monetary cost, and best effort. In accordance with the present invention, these service types are made applicable to a wireless channel. The service type definitions determine the protocol used to transmit data over the wireless channel to accommodate inherent characteristics of wireless channels.
• FIG. 10 is achart1000 illustrating precedence values for a preferred arrangement in accordance with the invention.Chart1000 includes aprecedence value column1002, adata type column1004, and anexamples column1006.Precedence value column1002 list the precedence values in base two notation. The precedence values are used to set priorities for a particular packet. The higher the precedence value, the higher priority the packets. Therefore, for example, the precedence value of 6 is of higher priority, and in the case of contention, is sent before a packet with a precedence value of 2. The precedence values are placed in the type ofservice field900 at the source of packet generation. The precedence values1002 are used by any apparatus that must select a packet for transmission, for example, a wireless modem that must select among packets to be transmitted over a wireless channel. Thedata type column1004 list the type of data that is generally associated with a particular precedence value. Theexamples column1006 list examples of application data that use a particular precedence value.
• Chart1000 shows 8 precedence values, 7 through 0.Row1008 lists a precedence value of 7, which is the highest priority precedence value. The data type that is preferred for a precedence value of 7 is session based call control data, as listed inrow1008,column1004. Examples of this data include packets used to set up a voice, audio or video call.Row1010 lists a precedence value of 6. The data type preferred for this precedence value is network-control data for router protocols, as defined by the existing art. Examples of this data include internal maintenance download data.Row1012 lists a precedence value of 5. The data type preferred for this precedence value is high priority time critical data, such as emergency voice and video data.Row1014 lists a precedence value of four. The preferred data type for this precedence value is network-control data for router protocols, as defined by the existing art. Exemplary data used for this precedence value includes non-delay critical packets.Row1016 lists a precedence value of three, which preferably is used for time-critical (delay-sensitive) data, for example voice and video data.Row1018 lists a precedence value of 2, which is preferably used for higher priority data, for example, emergency data from an emergency database query.Row1020 lists a precedence value of 1, which is preferably used for non-emergency data, such as Web browser data and non-emergency database queries.Row1022 lists a precedence value of zero, which is the lowest priority precedence value and is also a default value inserted into packets not using any particular priority protocol. The zero precedence value allows for backward compatibility with all Internet packets. Any data not otherwise specified for a precedence value of 1 through 7, uses a precedence value of the zero.
• FIG. 11 is achart1100 illustrating the preferred manner and protocol used to send a particular packet based on the service type defined in the type of service field.Column1102 lists the bit pattern that defines the particular service type.Column1104 gives the name of the service type.Column1106 lists the type of error correction that is applied for the service type on both the incoming and outgoing channel.Column1108 lists the media access method (e.g., random access, delay-sensitive) used on the incoming channel. Notably, in the preferred embodiment, the outgoing channel does not have different media access methods. For incoming channel communications, the wireless modem on the wireless terminal uses the service type field to determine the type of error correction and the incoming channel media access method. For outgoing channel communications, the base station determines the type of error correction that is to be applied on the outgoing channel.
• In the preferred arrangement, the best effort service type, which is shown inrow1110, uses a default forward error correction on the incoming and outgoing channel (seerow1110, column1106) and uses a random access slot for incoming channel communications (seerow1110, column1108). A preferred default forward error correction protocol is a three-quarter rate, convolutional code. Alternative default forward error correction protocols include BCH (Bose-Chaudhuri-Hocquenghem) codes (binary and non binary), Reed-Solomon, Golay, Hamming and other linear block and cyclical codes. By virtue of the error correction selection and the channel access method, the best effort service type provides an acceptable delay vs. reliability trade-off. The best effort service type is a default value, which provides backward compatibility for packets unaware of the service types specified according to the invention.
• Preferably, the minimize delay service type, which is shown inrow1112, uses strong forward error correction on both the incoming and outgoing channel. The minimize delay service type uses reserved, delay-sensitive slots for the incoming channel media access method. A preferred protocol for strong forward error correction is a one-half rate, convolutional code. Alternative protocols for strong forward error correction include BCH (Bose-Chaudhuri-Hocquenghem) codes (binary and non binary), Reed-Solomon, Golay, Hamming and other linear block and cyclical codes. The minimize delay service type is preferably used for audio and video data.
• Preferably, the maximize throughput service type, which is shown inrow1114, uses no forward error correction on both the incoming and outgoing channel. The maximize throughput service type uses reserved, delay-sensitive slots for the incoming channel media access method. The maximize throughput service type is preferably used for audio and video data, in particular, for audio and video protocols where error correction is handled in a network protocol layer higher than the physical layer protocol. Exemplary audio and/or video protocols are IMBE (Improved Multi-Band Excitation) and H.263 with annexes to include built-in error handling.
• Preferably, the maximize reliability service type, which is shown inrow1116, uses the best combination of forward error correction and retransmission techniques for both the incoming and outgoing channels. This provides the highest degree of reliability. The incoming channel media access method is random access.
• Preferably, the minimize monetary cost service type, which is shown inrow1117, dynamically selects error correction based on the transmission charges and signal levels. That is, an error correction protocol is selected on the basis of cost and the signal levels associated with the particular transmission. The incoming channel media access method is dynamically selected as reserved (delay-sensitive or non-delay-sensitive) or random access based on monetary charges and signal levels.
• FIG. 12 is a flow chart illustrating a preferred method for sending packets over a wireless channel using the preferred type ofservice field900. The method is described with reference to the preferred embodiments discussed above. First, a computer122 of awireless terminal102 generates setup packets for a particular application and reserves bandwidth, if necessary (1200). For example, if an H.323 audio/video teleconference call is required, then setup packets must establish reserved, delay-sensitive bandwidth, as discussed above with reference toFIG. 5. In accordance with the preferred type ofservice field900, the setup packets, when generated by computer122, receive a type ofservice field900. Based on the preferred definitions of the precedence value and service type given inFIGS. 10 and 11, the setup call packets receive a precedence value of 7 and a service type of maximize reliability, best efforts or minimize monetary cost, depending upon the nature of the audio/video call. For an emergency audio/video call, maximize reliability may be the appropriate service type. For a non-emergency audio/video call, the best effort service type may be appropriate. For an audio/video call seeking to minimize expense, the minimize monetary cost service type may be most appropriate. In any event, the precedence value is used by the wireless modem124 to determine the priority for sending the setup call packets over the wireless channel. That is, the wireless modem124 uses the precedence value to resolve any contention between multiple packets waiting to be sent over the wireless channel. The service type is used to determine the type of error correction and incoming channel media access method used for transmitting the packet or packets associated with setup.
• If the setup procedure is successful (seeFIG. 5), that is, bandwidth is available (1201), then data packets associated with the call are assembled and assigned a precedence value and service type (1202). For the audio/video call example, the preferred type of service definitions dictate a precedence value of five or three for the actual audio and video packets. A precedence value of five is selected if the audio and video data relates to an emergency. On the other hand, if the video and audio data is not related to an emergency, a precedence value of three is used. The service type selected for the audio and video data packets is either minimize delay or maximize throughput, according to the preferred definitions. If error correction and retransmission is controlled through the network layer protocols, as opposed to the physical layer protocols, then the maximize throughput service type may be most appropriate. On the other hand, if the audio video application protocols do not to have error correction built-in, then the minimize delay service type may be most appropriate. The minimize delay service type and the maximize throughput service type use reserved, delay-sensitive slots on the wireless channel.
• After the type of service field is defined for the packet (1202), the wireless modem selects the packet that will be sent over the wireless channel next (1204). In particular, the wireless modem124 determines which packet from a plurality of applications will be sent over the wireless channel based on the precedence value for the packet and the service type for the packet. Also, the wireless modem124 determines which packet will be sent based on the type of slots scheduled by the channel scheduler (seeFIG. 6). Finally, the packets are sent (1206).
• Base site104 checks the precedence values and service types of packets it receives for transmission on the outgoing channel.Base site104 uses the precedence values to determine which packet is sent over the outgoing channel next. For both the wireless modem124 andbase site104, if there are ties in precedence values, the oldest packet of the highest priority value is sent next over the wireless channel, assuming an appropriate slot type in the channel.
• By virtue of the present invention, delay-sensitive applications, such as video and audio transmissions, are allocated bandwidth on a wireless channel to guarantee performance. The applications need not be aware of the wireless channel requirements or protocol. Delay-sensitive applications are allocated resources on the channel to guarantee a channel bandwidth to accommodate an application bandwidth. Packets to be transferred over the wireless channel use a type of service bit field to determine the priority of packets and an error correction and media access method. Advantageously, selective allocation of bandwidth permits efficient management of the wireless channel while guaranteeing performance.
• While the invention has been described in conjunction with specific embodiments thereof, additional advantages and modifications will readily occur to those skilled in the art. The invention, in its broader aspects, is therefore not limited to the specific details, representative apparatus, and illustrative examples shown and described. Various alterations, modifications and variations will be apparent to those skilled in the art in light of the foregoing description, but embraces all such alterations, modifications and variations in accordance with the spirit and scope of the appended claims.

Claims (12)

1-10. (canceled)

11. In a wireless communications system where packets of data are transmitted over a wireless channel, a method for determining which packet of a plurality of packets should be transmitted next over the wireless channel, the method comprising the steps of:

determining a precedence value for each packet to be transmitted over the wireless channel;

selecting a packet to be transmitted next over the wireless channel based on the precedence value, wherein the precedence value for each packet is determined based on whether the each packet includes data to set up communications over the wireless channel.

12. The method ofclaim 11 wherein the precedence value for each packet is determined based on whether the each packet includes audio or video data.

13. The method ofclaim 12 wherein the precedence value for each packet is determined based on whether the each packet includes emergency data.

14. The method ofclaim 13 wherein the precedence value for each packet is determined based on whether the each packet includes non-delay critical data.

15. The method ofclaim 11 wherein the precedence value for a packet that includes data to set up communications over the wireless channel is of a higher priority than precedence values for other packets.

29. In a wireless communications system where packets of data are transmitted over a wireless channel, an apparatus for determining which packet of a plurality of packets should be transmitted next over the wireless channel, the apparatus comprising:

a processor that:

determines a precedence value for each packet to be transmitted over the wireless channel; and

a wireless modem coupled to the processor that:

selects a packet to be transmitted next over the wireless channel based on the precedence value, wherein the precedence value for each packet is determined based on whether the each packet includes data to set up communications over the wireless channel.

30. The apparatus ofclaim 29 wherein the precedence value for each packet is determined based on whether the each packet includes audio or video data.

31. The apparatus ofclaim 30 wherein the precedence value for each packet is determined based on whether the each packet includes emergency data.

32. The apparatus ofclaim 31 wherein the precedence value for each packet is determined based on whether the each packet includes non-delay critical data.

33. The method ofclaim 29 wherein the precedence value for a packet that includes data to set up communications over the wireless channel is of a higher priority than precedence values for other packets.

34-36. (canceled)

Images