MULTIPLE PRIORITIES

Field of the Invention

The present invention relates to multiple access protocols for a communication system, and more particularly to a broadcast communication system having many users with multiple priorities.

Background of the Invention

Multiple access protocols are generally either classified as centralized or distributed based on where the decision is made on how/when to access the physical channel. FIG. 4 numeral 400, demonstrates the concept. The centralized approach 402, has a central node, 404, determining who/when/for how long users can have access to the channel, by broadcasting control information to all the stations 406 and having nodes determine if the control information is destined for the stations or if the control information is to be ignored. The distributed approach 408 requires users 410 to determine when said users may communicate to the central node 412 based on a set of rules specified in the type of medium access control (MAC) algorithm implemented: 1 ) random access; 2) deterministic; or 3) a stack algorithm. These algorithms are referred to as MAC protocols and the control and decision process is then moved from the central node to the users.

For each of these approaches the state of the user best describes the action, FIG. 5 numeral (500). In the centralized case, 502, the user remains in the idle state 504 until it is polled by the central node and the polled id is equal to the user 508. Then, the node transitions to the active state 506 and

transmits information to the central node. Once the node completes transferring the information, 509, the node returns to the idle state 504. If the user has no information to transmit, then bandwidth on the channel is wasted. The distributed user state diagram is similar to the state diagram for 508. A user is idle, 510, until the user is ready to transmit information, which is indicated by receiving a packet in the queue, 514. The user then transitions to the contention state 512 and, based on the multiple access protocol being used, attempts to transmit the information. Many schemes may be used here, with or without collision resolution. Upon successful transmission, the user returns to the idle state. A modification of this scheme incorporates reservations, 516. Then from contention, 518, a user can enter the active state, 520, by successfully transmitting in a slot if the user has more information to transmit in its queue, and when using a modulo counter, transmits in the same slot at all times until all information is transmitted. This approach is commonly used in a slotted system, where fixed size packet lengths exist, and a frame structure is used, meaning that X slots make a frame and after X slots the frame begins again, where X is a positive integer. It then returns to the idle state. All of these user state diagrams lack the flexibility required for multiple priority traffic types, due to the rigid frame structure of 514, the need to always compete in 508, and having to wait while all active/inactive users are polled in 502. In the hybrid case, where both are used, the state transition diagram of 516 is appropriate. The key difference between the hybrid approach and the reservation-based distributed approach is that in the active state, how users gain access to the channel is based on the centralized approach of 502. In other words, only active users will access the channel, and the centralized approach is used to schedule the active users. This is a major drawback to the prior art scheme.

The network topology in which hybrid solutions may be applied is shown in FIG. 6, numeral 600. This network topology includes a non-user central node that must communicate with many users via a broadcast downstream channel and a plurality of users that communicate with the central node through an upstream channel. Examples include: star topologies 602, bus topologies where separate channels are used to communicate 604, and ring topologies.

The network topology of FIG. 6 includes a non-user central node that must communicate with many users via a broadcast downstream. Each priority class is assured receipt of at least a minimum required service defined for the priority class, and users are provided with performance measures intermediate between the performance measures of a distributed class of access protocols at a low utilization and the performance measures of the centralized algorithms at a high utilization.

Thus, there is a need for device, router, method and system for providing a hybrid multiple access protocol for users with mutiple priorities.

Brief Description of the Drawings

FIG. 1 is a block diagram of one embodiment of a device in accordance with the present invention.

FIG. 2 is a flow chart of one embodiment of steps of a method in accordance with the present invention.

FIG. 3 shows an example of one embodiment of steps of the method utilized by stations in accordance with the present invention .

FIG. 4 is a diagrammatic representation showing how the prior art defines transmission.

FIG. 5 shows a user state diagram as is known in the art.

FIG. 6 illustrates prior art topolgies

FIG. 7 shows an example of one embodiment of the system topology and architecture in accordance with the present invention.

FIG. 8 illustrates a prior art method for classifying multiple access techniques based on control transfer

FIG. 9 illustrates one embodiment of the types of information the downstream channel carries in accordance with the present invention.

FIG. 10 shows a flow chart of one embodiment of the method utilized by the adaptive reservation manager in accordance with the present invention.

FIG. 1 1 shows a state transition diagram for one embodiment of the method utilized by the adaptive resevation manager in accordance with the present invention.

FIG. 12 shows a schematic representation of one embodiment of a control packet that may be used in accordance with the present invention.

Detailed Description of a Preferred Embodiment

The present invention provides the following benefits over existing solutions: 1 )support of multiple service categories; 2) insurance that each user admitted to the system receives the negotiated service guarantee designated for the user's service category; 3) by allowing the central controller to dynamically vary the frequency and number of contention subslots on a per service category basis, the present invention achieves an overall system performance that is comparable to centralized algorithms at high system loads, while allowing desirable performance levels of distributed access protocols at low system loads, 4) further system level efficiency is achieved by allowing transmission of variable number of packets, each with variable size, when access is granted to a user; and 5) reduction of the number of instances a user needs to content for access, thereby reducing collisions and overhead due to contention slots and improving system performance.

The users and the priority classes provided for the users in accordance with the present invention are shown in FIG. 7, numeral 700. Users 706, 708, 710, are coupled to a central station, 704, which may be any device which provides an interface to the network. For example, an environment such as a home having a potential to connect a computer, 708, a telephone, 706, and a cable television, 710, to a single outlet may be considered a user. In prior art these connections are using separate lines: one from the cable company and potentially two from lines from a telephone company, all of which are considered to be single users. But if a outlet to the system allowed all three to be attached to the network and operate independently of one another, then each is a separate user at a single connection.

The multiple priorities become apparent based upon quality of service issues, which separate the users into service categories. Obviously, if a phone conversation were in session and the delays for transfer of voice information to the final destination were large, e.g., on the order of a few seconds, most users would be dissatisfied with the service. Therefore, a requirement is placed onto the voice traffic, wherein, when information is generated, the information must reach the destination within a deterministic time or the quality of service is categorized as unacceptable.

Also, it is known that, upon transmission, some voice information may be lost, and yet the sound of the reproduced voice is still acceptable to the users. This may be compared to a computer user who types a few commands and then thinks for a while on the next action. Here, delay is not a concern, but the transfer of information must meet the requirement of a very small rate, e.g., 0.1 e-6. Therefore, when two users are requesting service and as ongoing service is continued, how the transmissions of the two users are prioritized by the central controller is based on a predetermined priority class for each user. The priority class identifies the type of service, quality and may also approximate how messages will arrive at the network. Each user is then treated differently, and the priority class provides a mechanism for the centralized approach to determine which user gains access to the channel and when the user gains access.

A hybrid solution is one which incorporates decision- making capabilities located at both the central node and users.

The hybrid solution was introduced since, in stand-alone operations, centralized approaches, such as traditional TDMA, large delays occur at low utilization in comparison with distributed random access techniques which have very little

delay at low utilization. At high utilization, in terms of average delay and throughput, the TDMA performance exceeds that of random access. To harness the best of both techniques and overcome the deficiencies of each, a hybrid solution was formed. The central node communicates broadcast control information, and the users respond by either using a distributed approach or respond only when the central control addresses a specific station, depending on the control packet contents. In both cases, generally the centralized approach initiates occurrence of the distributed actions based on an address identified or lack thereof.

In the prior art, a hybrid approach for all priority classes on the broadcast medium is based on a single class of users and is unable to accommodate a multiplicity of classes of users efficiently. The contention is based on a single class and is available in all unassigned slots, including slots without reservations, the hybrid approach further includes the use of a random access (slotted aloha) type of contention, and once a reservation has been made, the user is polled in a periodic fashion.

The random access approach in the prior art is not easily upgraded to multiple priority classes, since, as the number of users supported and number of contention slots available decreases, the slots become unable to support a multipriority user group.

Prior art devices for the central controller rely on a scheduler having only one class of users wherein all users are polled regardless of whether or not the users have information to send. Typical approaches are: roll call polling; and round robin polling.

A block diagram for a system wherein the invention is incorporated is shown in FIG. 7 numeral 700. The system includes a central controller, 702, that transmits to and receives transmission from, stations 704. The central controller has an adaptive reservation manager 712, a feedback generator 714, and a scheduler 716, (described further below). The stations 704 are typically further subdivided into users of a specific priority class , 706, 708, 710, which require a specific quality of service contract to be arranged with the central controller, 702.

The present invention includes a system for implementing a hybrid multiple access protocol for users with multiple priorities that provides efficient reservation of channel resources to accommodate users with randomly transmitted requests wherein the users have multiple priorities. The system typically includes a central controller device having: A) an adaptive reservation manager, coupled to a scheduler, for, upon receiving randomly transmitted requests from users, accepting reservations from the users, resolving contentions that arise, and providing contention feedback information to a feedback generator; B) the feedback generator coupled to the adaptive reservation manager and to the scheduler, for providing a transmission schedule and information to the users on a current state of contention; and

C) the scheduler, coupled to the adaptive reservation manager, for providing global system information to the reservation manager and for providing a transmission schedule for both the feedback generator and the users .

In one embodiment, the contention feedback information may be selected to be a ternary feedback indicating one of: an idle, a success, and a collision. Where selected, the scheduler includes a process that is embodied in a computer program implemented by a microprocessor having the steps of: A)

mapping randomly transmitted requests from users and current states of users to a global system state; B) determining the transmission schedule for both the feedback generator and the users based on randomly transmitted requests from users and current states of users.

The hybrid approach of the present invention utilizes a hybrid multiple access protocol in which a combination of centralized and distributed access protocols are executed. The distributed approach allows users to contend for reservations wherein a preselected centralized MAC algorithm based on service requested and system resources available guarantees that a minimum service requirement is met, for example, an upper bound may be guaranteed on end to end delay for isochronous traffic, and a low error rate may be set for asynchronous traffic. The centralized approach determines which users may have access to the broadcast medium based on the priority class of the user, and when users that are inactive in the centralized approach will be allowed to contend for admission.

FIG. 7, numeral 700, illustrates the environment of the proposed method. The stations, 704, may consist of multiple users, 706, 708, 710, that may be grouped into priority classes based on the service that is negotiated during initialization, wherein the users are waiting to gain access to the upstream channel, 712. Each user/priority class may, for example, be classified into one of three states as shown in FIG. 5, numeral 500. These states are: 1 ) idle, 517, which corresponds to a priority class having no information to be transmitted; 2) contention, 518, which corresponds to the user contending, via a distributed MAC algorithm, for entrance into the central controllers MAC protocol; and 3) active, 520, which refers to active stations in the centralized MAC protocol located within the central controller, 502.

The upstream channel, 712, used by stations to communicate to the central node, is defined by the central controller. The upstream channel consists of variable length slots of at least a preselected minimum size, but smaller than a predetermined finite maximum length. The slots are typically further separated into one of two types: contention or dedicated, FIG. 8, numeral 800, which are determined by the central controller.

In one embodiment, the contention slot, 802, is typically further decomposed into m >=1 subslots, 806, m an integer, where the number of subslots is determined by the central controller depending on the system dynamics, e.g., the load on the system from each service category, the active/inactive state of users etc., and thus is variable for each contention slot. The users in the contention state, 518, contend only for subslots assigned with the same priority. The priority of the subslots is determined by the central controller. The dedicated bandwidth channel, 804, is assigned to active users that have secured a reservation and have been polled by the central controller.

The channel assignment and subslot allocation is dictated by the central controller based on priority and allowable numbers of stations cable of being supported by the central controller. This information is passed to the stations/users by a broadcast packet, 806, where the destination address indicates the user to receive the information. Feedback is ternary feedback from the previous contention slot 802, and the polling frame is the definition of the next contention slot 803.

The downstream broadcast channel contains variable length packets destined to specific users, or groups of users,

based upon upstream requests made to external sources, such as client servers, cable operators, telephone connections and control information from the central control unit. As external arrivals enter the system/router that implements the hybrid multiple access protocol for users with multiple priorities, the information for each user is supplied on the user's downstream channel. Due to the fact that the downstream channel is a broadcast channel, all downstream stations may read the incoming packets, decode the destination id and packet type, and decide to store or discard the packet.

One embodiment of the interface between the central controller and the stations is illustrated in FIG. 9 numeral 900. The central controller broadcasts control messages to the stations/users identifying by address the information that is being transmitted for each type of multiple access control that is to be employed in the next bandwidth allocation: centralized or distributed. Where the bandwidth allocation is centralized, 904, the destination id indicates a specific station/users that are allocated bandwidth on the upstream. Where the bandwidth allocation is distributed, 902, all users that are in the contention state for that priority class are allowed to contend based on the predetermined distributed MAC rules.

The central controller is described by the system shown in FIG. 1 , numeral 100, and contains the following functional units: the adaptive reservation manager, 102; the scheduler 104; and the feedback control 106. The adaptive reservation manager, 102, is a dynamic unit that: 1 ) processes information from the multiple access contentions, in the contention subslots, on the upstream channel, 108; 2) provides local state information to the scheduler, 1 14, for successful

contentions and priorities; 3) based on the contention results, dynamically defines the priorities of the subslots in the next contention slot; and 4) provides contention slot feedback and definition information to the feedback controller, 1 16. The state information may include, but is not limited to, user queue depth, size of the packet at the head of the queue, and the priority requested.

The scheduler, 104, gathers global, 1 12, and local information, 1 14, on the system and schedules a next group of stations/USERS to be polled based upon active users priorities, the maximum number of supportable users, and the service contracts made. The external information, 1 12, relates to information being passed through the router to the users, wherein the scheduler inserts the control packets being sent to the station/users in the information.

The global information to the scheduler is provided by another portion of the system/router that is responsible for providing a link to the wide area network to which the central controller is attached. The scheduler also relays predetermined specific global information to the adaptive reservation manager, 107. Then, the adaptive reservation manager adaptively determines which service priorities are allowed to compete in the next contention slots. The scheduler also provides the scheduling information, the amount of bandwidth allocated to each user to the feedback control, 106, so that downstream control information may be broadcast to the users.

The feedback control, 108, combines information from the adaptive reservation manager, 1 07, being contention assignment and results, with that provided by the scheduler, 104, in a predetermined format. The information is passed to the downstream channel interface units queue where it is

stored until broadcasted. Thus, the feedback control strategically places the control packets into the queue such that nodes receive the information at the correct time and may transmit immediately after decoding and processing the i nformation.

Where selected, the device of FIG. 1 may include contention feedback information that is a ternary feedback indicating one of: an idle, a success, and a collision. Also, the device may be a microprocessor. The scheduler may execute a process that is embodied in a computer program implemented by a microprocessor having the steps of: A) mapping randomly transmitted requests from users and current states of users to a global system state; and B) determining the transmission schedule for both the feedback generator and the users based on randomly transmitted requests from users and current states of users.

FIG. 10, numeral 1000, shows a flow diagram of one embodiment of steps implemented by the reservation manager in accordance with the present invention. These steps are executed only after a contention slot, on the upstream, has been received by the central controller which passes the results to the adaptive reservation manager. The information that is passed is typically ternary: 1 ) none for no attempted reservations made; 2) single, for one successful reservation; and 3) error, for two or more users requesting a reservation in the same subslot. If a request was successful, the users' state information that was sent in the contention subslot is attached. This is the users' local information, for example, size of packet at the head of the queue or the depth of the queue. Where the request was successful information is passed to the scheduler, 1002, while a global information update is requested. The global information contains the number of available users/priority classes that may be supported on the

upstream channel, 1004. A predetermined predictive algorithm is then executed to estimate the aggregate arrival rate for each priority class. This information is critical to the adaptive reservation manager's assignment of priority classes to the subslots in the next contention slot, 1006. The information is then passed to the feedback generator 1008 such that when the scheduler assigns the next contention slot, the control packet for the contention slot is available.

There exist many standard methods for the users to determine eligibility to contend in the contention slot, such as tree splitting algorithms, but the adaptive reservation manager supplies the contention slot definition. The assignment of priorities to the subslots in the contention slot has a direct impact on the distributed MACs protocols execution and performance. An example of a system with a fixed two priority process, where m=2 for all contention slots, is shown in FIG. 1 1 , numeral 1 100. The values (maxx, N), 1 122 are global information supplied by the scheduler and represent the maximum allowable users for priority class X and the present number of active users, N, for that class. The value N is required since the ARM (adaptive reservation manager) does not keep track of active users that no longer require service. PRIx , 1 121 , is the predictive aggregate arrival rate on a specific channel for priority class x and determined in 1004.

Block1 123 shows the results of the present contention subslot assignment and results, which may be none/single or collision. A blank box represents the condition none/single, and the shaded box an error condition for the specific class. State 1 102 is the steady state position. The ARM will stay in the state if condition 1 108 holds true, that is, there are no collisions or there was a collision in the L (low) priority and PRIι_ (predictive arrival rate for priority L) is less then 0.48. Where a single contention slot is used and an arrival rate of new users of less than 0.48 exists, the system is stable. To

transition from 1 102, one of two conditions must prevail. If there is a error in the high priority contention slot 1 1 10, then regardless of the state of the low priority contention, state 1 106, HH, is entered for the next contention definition. If contending users are allowed to compete for more then one slot, the probability of reducing the contention time is increased along the with stability of the system for a higher arrival rate. This scheme is required to help with the QOS (Quality Of Service) issues for high priority users which usually have delay constraints applied to them. The priority contention remains in 1 106 until no further collisions occur in either of the two contention subslots, 1 120. If the results of both contention subslots are none/single, 1 1 18, the next slot definition returns to 1 102, or HL. To enter state 1 104, condition 1 1 16 must be met: the maximum number of high priority (H) users, or the maximum for that channel, must have been reached or there has been a collision in the low priority and PRI|_ is greater then 0.48. The priority contention stays in 1 104 until the number of active high priority users falls below MAXH (where MAXH is a predetermined maximum high priority); thus condition 1 1 12 is met and the next contention state definition is HL. Clearly, this algorithm may be expanded for cases where greater than two priority classes exist.

The scheduler, 104, may use any of the existing approximate scheduling algorithms. An approximate algorithm is used for problems in the class of algorithms classified as nonpolynomial time. For example, the known bin packing algorithm would be sufficient with the modification that each bin has a movable upper bound on the present number of users for that priority class which can be supported and the amount of information that can be transferred. If a bin is supplied to each priority with a bandwidth capacity limiting the size of the bin, and if there exists any unused portion of a bin, the unused portion may be transferred to the next lower priority

class. This type of transferral may be repeated until the last bin. The scheduling of the contention slot is a novel feature of the invention. Since the slot is a fixed size slot, in the worst case, whenever the system returns to one particular class due to a large number of active users requiring service, the contention slot is allocated. If the system is underutilized, then the contention slot may be placed into multiple bins to reduce the queuing delay as seen by the first packet of a contention user. The contention slot also supplies the system with coarser local state information so that the accuracy of scheduling and the adaptive reservation manager's predictive schemes are increased.

The feedback generator, 104, is the gatherer and executer for the scheduler. The feedback generator is supplied with the schedules that are continuously updated, and based on the state information, creates a control feedback packet to be supplied to all users with the appropriate control information. FIG. 12, numeral 1200, shows an example of typical information that is transferred in the control packet. Unit

1202 contains the address that the packet is destined for, since the control information address is all zeros, indicating availability for all users. Unit 1204 contains the feedback of the last contention subslots, i.e., the ternary feedback, 0, 1 , or e (error). Unit 1206 identifies the priorities associated with the current contention slot. An example of the feedback for m=2 is 0000 1 e HL, which represents the address field, 0000, and the results of the last contention slot, being a success and error. Since the stations know the priority assignments from the previous slot, the central controller does not have to repeat priority assignments. HL represents the next subslot's definition high and low priority.

FIG. 2, numeral 200, shows a flow chart for one embodiment of steps for a method for efficient reservation of

channel resources to accommodate users with randomly transmitted requests wherein the users have multiple priorities in accordance with the present invention. The method includes the steps of: A) accepting 202, upon receiving randomly transmitted requests from users, reservations from users and resolving, by a reservation manager, contentions that arise; B) providing contention feedback information to a feedback generator 204; C) providing 206, by the feedback generator, a transmission schedule and information to the users on a current state of contention; D) providing 208, by the scheduler, global system state information to the reservation manager; and E) providing a transmission schedule for both the feedback generator and the users 210. The contention feedback information may be a ternary feedback indicating one of: an idle, a success, and a collision. The scheduler may include a process that is embodied in a computer program implemented by a microprocessor having the steps of: A) mapping randomly transmitted requests from users and current states of users to a global system state; B) determining the transmission schedule for both the feedback generator and the users based on randomly transmitted requests from users and current states of users.

The stations receive the broadcast packet and act in one of two ways based on individual priority class states. FIG. 3, numeral 300, shows one embodiment of each station's priority class response. Step 302 is executed when a control packet is received. The stations decode the control packet to determine whether there is a contention poll 304. The result of 304 dictates if the station executes the centralized or distributed MAC protocol. If the control packet is destined to a specific user, and not all users, path 305 holds true. A comparison to the stations' id is evaluated, 306. If the station is the destination, the station updates the local state information and transmits the allocated amount to the central

node, 308. If the destination address fails to match the station's id, the process waits for the next contention poll (meaning destination id equals 0000). Upon receipt of a contention poll, path 306 is entered, and the distributed MAC protocol is executed. The stations then process the feedback information for the individual particular priority class, if available, and determine eligibility. Eligibility may be determined in many ways, for example, using tree splitting algorithms, probablistically, or deterministically. If the station is not in a contention state, the contention procedure is done 324. If the station is in a contention state, 312, and the station contended in a previous subslot, 314, the station determines from the feedback supplied what the result of the contention attempt was. If the station is in a contention state, 312, and no outstanding request exists, the station determines whether it is eligible to compete in the contention slot 320. For example, if the feedback for that subslot was 1 , success, then the station moves into the active state and waits to be polled by the central controller, 318. Otherwise, 320, the station determines how many contention slots exist for the priority class, and chooses one with equal probability, or 1 /(number of slots assigned to priority class). If no priority subslots exist for that particular class, the station must wait until the next contention period to determine whether it may compete, 324. If the station may contend, then in 322, the station creates a packet with the predetermined local information and contends in the slot chosen. The station then waits for the next contention control packet to arrive to determine the results.

We claim: