Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1999-11-29
2004-01-06
Courtenay, III, St. John (Department: 2126)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S241000, C709S241000
Reexamination Certificate
active
06675229
ABSTRACT:
RELATED APPLICATION
The present invention is related to the invention described in the U.S. patent application of J. Bruno et al., entitled “Methods and Apparatus for Ensuring Quality of Service in an Operating System,” which is filed concurrently herewith and incorporated by reference herein.
FIELD OF THE INVENTION
The present invention relates generally to computer systems, and more particularly to techniques for providing a desired quality of service (QoS) for an application running in a computer system.
BACKGROUND OF THE INVENTION
Conventional time-sharing operating systems cannot guarantee resource availability in the amount required by any given application. Examples of conventional time-sharing operating systems include Unix, as described in, e.g., M. McKusick et al., “The Design and Implementation of the 4.4 BSD Operating System,” Addison Wesley Pub. Co., Reading, Mass., 1996, and Windows NT, as described in, e.g., H. Custer, “Inside Windows NT,” Microsoft Press, 1993.
However, an increasing number of applications, e.g., multimedia, require sufficient resources, including central processing unit (CPU), memory, and disk and network bandwidth, in order to perform properly. Such applications may perform well, on conventional time-sharing operating systems in cases of overprovisioning, i.e., when the total amount of resources tends to be larger than a worst-case workload would demand. Overprovisioning is possible, e.g., on dedicated systems, in the absence of other load. On the other hand, conventional time-sharing operating systems cannot guarantee adequate performance of such applications, e.g., in the cases of server “hot spots” or network congestion.
For such applications to perform properly under arbitrary load, an operating system must provide quality of service (QoS) guarantees and admission control, i.e., the operating system should admit a request only if the system has set aside sufficient resources to guarantee that it will satisfy the request with the specified performance bounds. Many techniques for providing QoS guarantees have been developed recently, as described, e.g., in D. Stiliadis and A. Varma, “Frame-Based Fair Queuing: A New Traffic Scheduling Algorithm for Packet-Switched Networks,” Tech. Rep. UCSC-CRL-95-39, Univ. Calif. Santa Cruz, July 1995; J. Bennett and H. Zhang, “WF
2
Q: Worst-Case Fair Weighted Fair Queueing,” in Proceedings of INFOCOM'96, IEEE, March 1996, pp. 120-128; J. Bennett and H. Zhang, “Hierarchical Packet Fair Queueing Algorithms,” in Proceedings of SIGCOMM'96, ACM, August 1996; P. Goyal, X. Gao and H. Vin, “A Hierarchical CPU Scheduler for Multimedia Operating Systems,” in Proceedings of OSDI'96, USENIX, October 1996, pp. 107-121; and I. Stoica, H. Abdel-Wahab, K. Jeffay, S. Baruah, J. Gehrke and C. G. Plaxton, “A Proportional Share Resource Allocation Algorithm for Real-Time, Time-Shared Systems,” in Proceedings of Real Time Systems Symp., IEEE, December 1996.
A major shortcoming of these and other QoS techniques is that they typically require legacy applications to be modified in order to benefit from the improved guarantees that can be provided by the QoS techniques. Legacy applications are those developed before a given QoS technique. Modifying legacy applications can be costly or impractical.
SUMMARY OF THE INVENTION
The present invention provides techniques for running legacy applications automatically with quality of service (QoS) guarantees that match required QoS performance levels. In accordance with the invention, files are provided with a new attribute, referred to herein as a QoS requirement, and a requirement broker is interposed between legacy applications and the operating system. The requirement broker may be in the form of a modified version of a library that is dynamically linked with applications at load time. The modified library intercepts certain system calls and automatically requests QoS guarantees in accordance with the QoS requirement attributes of the accessed files, whether local or remote.
Advantageously, the invention allows an operating system to run unmodified legacy applications automatically with QoS guarantees that provide the required performance.
REFERENCES:
patent: 6189046 (2001-02-01), Moore et al.
patent: 6289462 (2001-09-01), McNabb et al.
patent: 6385638 (2002-05-01), Baker-Harvey
patent: 6408342 (2002-06-01), Moore et al.
patent: 6442748 (2002-08-01), Bowman-Amuah
I. Stoica et al., “A Proportional Share Resource Allocation Algorithm for Real-Time, Time-Shared Systems,” in Proceedings of Real Time Systems Symp., IEEE, pp. 1-12, Dec. 1996.
D. Stiliadis et al., “Frame-Based Fair Queuing: A New Traffic Scheduling Algorithm for Packet-Switched Networks,” Tech. Rep. UCSC-CRL-95-39, Univ. Calif. Santa Cruz, pp. 1-41, Jul. 1995.
J. Mogul et al., “Eliminating Receive Livelock in an Interrupt-driven Kernel,” in Proceedings of Annual Tech. Conf., USENIX, pp. i-viii and 1-46, 1996.
J. Bruno et al., “The Eclipse Operating System: Providing Quality of Service via Reservation Domains,” in Proceedings of Annual Tech. Conf., USENIX, pp. 235-246, Jun. 1998.
J. Bennet et al., “WF2Q: Worst-Case Fair Weighted Fair Queueing,” in Proceedings of INFOCOM'96, IEEE, pp. 120-128, Mar. 1996.
J. Bennet et al., “Hierarchical Packet Fair Queueing Algorithms,” in Proceedings of SIGCOMM'96, ACM, 7 pages, Aug. 1996.
P. Goyal et al., “A Hierarchical CPU Scheduler for Multimedia Operating Systems,” in Proceedings of OSDI'96, USENIX, pp. 107-121, Oct. 1996.
J. Bruno, et al., “Disk Scheduling with Quality of Service Guarantees,” in Proceedings of ICMCS'99, IEEE, 3 pages, Jun. 1999.
P. Druschel et al., “Lazy Receiver Processing (LRP): A Network Subsystem Architecture for Server Systems,” in Proceedings of OSDI'96, USENIX, pp. 261-275, Oct. 1996.
D. Ghormley et al., “SLIC: An Extensibility System for Commodity Operating Systems,” in Proceedings of Annual Tech. Conf., USENIX, 15 pages, Jun. 1998.
P. Goyal et al., “Start-Time Fair Queuing: A Scheduling Algorithm for Integrated Services Packet Switching Networks,” in Proceedings of SIGCOMM'96, ACM, pp. 1-14, Aug. 1996.
M. Jones et al., “CPU Reservations and Time Constraints: Efficient, Predictable Scheduling of Independent Activities,” in Proceedings of SOSP'97, ACM, pp. 198-211, Oct. 1997.
J. Nieh, “The Design, Implementation and Evaluation of SMART: A Scheduler for Multimedia Applications,” in Proceedings of SOSP'97, ACM, pp. 184-197, Oct. 1997.
P. J. Shenoy et al., “Cello: A Disk Scheduling Framework for Next Generation Operating Systems,” in Proceedings of SIGMETRICS'98, ACM, 6 pages, Jun. 1998.
G. Banga et al., “Resource Containers: A New Facility for Resource Management in Server Systems,” in Proceedings of OSDI'99, USENIX, pp. 45-58, Feb. 1999.
B.D. Noble et al., “Agile Application-Aware Adaptation for Mobility,” in Proceedings of SOSP'97, ACM, 6 pages, 1997.
G. Banga et al., “Better Operating System Features for Faster Network Servers,” in Proceedings of Workshop on Internet Server Performance, 6 pages, Jun. 1998.
Bruno John Louis
Brustoloni Jose Carlos
Gabber Eran
Ozden Banu
Silberschatz Abraham
Courtenay III St. John
Lucent Technologies - Inc.
LandOfFree
Methods and apparatus for providing quality of service for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for providing quality of service for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for providing quality of service for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3241477