Multiplex communications – Channel assignment techniques – Using time slots
Reexamination Certificate
1998-04-09
2002-03-19
Hsu, Alpus H. (Department: 2661)
Multiplex communications
Channel assignment techniques
Using time slots
C370S412000
Reexamination Certificate
active
06359900
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to resource allocation in a computer system, and particularly relates to a method and system for controlling access to a resource among several users of the resource.
BACKGROUND OF THE INVENTION
Electronic systems often have one or more resources which must be shared among several users. For example, in a single processor computer running a multi-tasking operating system, many tasks simultaneously contend for processor resources. Similarly, in a networked environment, many tasks contend for access to a fixed bandwidth communications channel to communicate information from one computer to another. During heavy use of the network, it is not unusual that contention for access to the channel becomes so high that data is not delivered from one computer to another computer in a timely fashion. For some purposes, such as data backup or printer traffic, delayed packet transmissions do not cause any serious problems. But for other applications delayed data transmissions can be extremely problematic. For example, applications which use a combination of data, audio, and video packets to create multimedia software programs are currently very popular. The transfer of audio and video packets over a network poses two problems. First, audio and video packets, and particularly video packets, use a significant amount of bandwidth. Second, if audio and video packets are not delivered in a timely fashion, a user will discern discontinuities in the audio or video presentation. In heavily congested networks, these discontinuities can be great enough to completely render the audio and/or video transmissions incomprehensible.
Because such multimedia traffic is becoming a larger portion of overall network traffic, and because many businesses have limited network bandwidth, there has been an effort in the computer industry to develop mechanisms which can provide Quality of Service transmission for multimedia packets over existing communication channels. Quality of Service (QOS) relates to the ability to deliver data, audio and video packets over a channel at a rate that eliminates perceptible video and/or audio discontinuities. QOS is required to deliver desirable multimedia applications. Some solutions have involved calculating “deadlines” for each packet, and/or maintaining each incoming packet in a sorted order. The problem with these scheduling mechanisms is that they are computationally expensive, and can use a substantial amount of a processor for the sole purpose of allocating the communications channel among several different requestors. Of course, processor utilization devoted to resource allocation is not available for other useful work. Ideally, mechanisms for controlling access to such a resource among many different users should be highly efficient to minimize any effect caused by the overhead of the allocation mechanism.
Such resource scheduling/allocation mechanisms ideally satisfy several conditions. First, the wait time for packets should be inversely proportional to a requestor's requested bandwidth of the channel. Also, non-multimedia traffic should equitably share the communications channel with multimedia traffic.
It is apparent that a method and system which efficiently controls access to a resource among several requestors, and can provide Quality of Service guarantees for multimedia traffic while still servicing non-multimedia traffic would be highly desirable.
SUMMARY OF THE INVENTION
It is one object of this invention to provide a method and system for scheduling access to a resource among a plurality of requestors in an efficient manner.
It is another object of the present invention to provide a method and system which can provide Quality of Service guarantees to multimedia traffic over a communications channel in a highly efficient manner.
It is yet another object of the present invention to provide a method and system which provides access to a communications channel in a manner such that the wait time for data packets is inversely proportional to a requestor's requested bandwidth.
It is still another object of the present invention to provide a method and system which provide Quality of Service guarantees to multimedia traffic while ensuring that non-multimedia traffic has timely access to the channel.
Additional objects, advantages and novel features of the invention will be set forth in part in the description which follows, and in part will become apparent to those skilled in the art upon examination of the following or may be learned by practice of the invention. The objects and advantages of the invention may be realized and obtained by means of the instrumentalities and combinations particularly pointed out in the appended claims.
To achieve the foregoing and other objects and in accordance with the purposes of the present invention as described above, a method and system for controlling access to a resource is provided. The method includes establishing a plurality of service queues, each service queue handling requests for a particular range of a requested amount of a resource. A plurality of slots are also established. A predetermined number of slots are assigned to each service queue. When a request for a resource from a requestor is received, the requestor is assigned to one of the service queues depending on the amount of the requested resource. A reference to the requestor is inserted in the number of slots that have been assigned to the service queue to which the requestor was appointed. This process creates a service order that defines the order and number of opportunities to access the resource each requestor has during any particular cycle through the schedule order.
According to one embodiment of the invention, each queue handles requests for a particular amount of the resource, and the amounts handled by each queue is a multiple of the amount handled by an adjacent queue. A plurality of slots are established, and a number of slots are assigned to each queue as a function of the amount of the resource handled by that queue.
According to one embodiment of the invention, before references to a requestor are allocated in slots, it is first determined which of the slots is least-loaded. The initial reference is then inserted into the least-loaded slot. Preferably, a slot interval is established for each queue. The slot interval is used to allocate references in the slots such that each slot in which a reference is allocated for a respective requestor is a uniform number of slots away from any other slots in which a reference is allocated for the respective requestor. The references in the slots establish a service order that is used to determine the order and frequency with which requestors have access to the resource.
According to another embodiment of this invention, a quota increment is established to further refine access to and use of the resource. The quota increment is established as a function of the requestor's requested use of the resource. As a requestor accesses the resource, its actual use of the resource is deducted from a cumulative quota associated with the requestor. The cumulative quota is incremented at the end of each cycle through the slots by an amount equal to the quota increment. If a requestor utilizes all of its cumulative quota during a cycle through the slots, it cannot further access the resource until its cumulative quota is replenished.
In a preferred embodiment of this invention, the resource is a communications channel, and the requestor is a source of a stream of data to be transmitted over the communications channel.
According to another embodiment of this invention, a plurality of service queues q
i
are established, where i ranges from 1 to n. The second and subsequent service queues are serviced N times as often as service queue q
(i−1)
. A number slots are established, the total number of slots being a multiple of N
(n−1)
. Each respective service queue is assigned a number of slots, and the ratio of the number of slots assigned to each re
Dinakar Sitaram
Seal Krishanu
Dinsmore & Shohl LLP
Hsu Alpus H.
Nguyen Brian
Novell Inc.
LandOfFree
Method and system for controlling access to a resource does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for controlling access to a resource, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for controlling access to a resource will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2881919