Applied Research Laboratory
Publications by Author
Saied Hossieni-Khayat

Hosseini-Kayat, S.; and Cox, J.R."Optimal Solution of Off-line and On-line Generalized Caching": Network traffic can be reduced significantly if caching is utilized effectively. As an effort in this direction we study the replacement problem that arises in caching of multimedia objects. The size of objects and the cost of cache misses are assumed non-uniform. The non-uniformity of size is inherent in multimedia objects, and the non-uniformity of size of cost is due to the non-uniformity of size and the fact that the objects are scattered throughout the network. Although a special case of this problem, i.e. the case of uniform size and cost, has been extensively studied, the general case needs a great deal of study. We present a dynamic programming methods of optimally solving the off-line and on-line versions of this problem, and discuss the complexity of this methods.

Hosseini-Kayat, S.. "New Results on Generalized Caching": We report a number of new results in generalized caching. This problem arises in modern computer networks in which data objects of various sizes are transmitted frequently. First it is shown that its optimal solution is NP-complete. Then we explore two methods of obtaining nearly optimal answers based on the dynamic programming algorithm we provided in [5]. These methods enable a trade-off between optimality and speed. It is also shown that LFD (the longest forward distance algorithm which is the optimal policy in the classical case), is no longer optimal but is competitive. We also prove that LRU remains competitive in the generalized case. This is an extension of a famous result by Sleator and Tarjan [12] on LRU. Finally, it is confirmed in the general case that prefetch does not reduce the total cost if "cost" reflects only the number of bytes transmitted.

Saied Hosseini-Khayat, Andreas D. Bovopoulos, "A Simple and Efficient Bus Management Scheme that Supports Continuous Streams," ACM Transactions on Computer Systems, Vol. 13, No. 2, May 1995, Pages 122-140.: An efficient bandwidth management and access arbitration scheme for an I/O bus in a multimedia workstation is presented. It assumes that a multimedia workstation consists of a number of processing modules which are interconnected by a packet bus. The scheme is efficient in the sense that it allows the bus to support both continuous media transfers and regular random transactions in such a way that continuous streams can meet their real-time constraints independently of random traffic, and random traffic is not delayed significantly by continuous traffic except when traffic load is very high. Implementation guidelines are provided to show that the scheme is practical. Finally, the performance of this scheme is compared with alternative solutions through simulation.

Saied Hosseini Khayat, Andreas D. Bovopoulos, "A Proposed Bus Arbitration Scheme for Multimedia Workstations," Proceedings of the IEEE International Conference on Multimedia Computing and Systems, Boston, May 1994.: The integration of video and audio into computers requires the support of continuous data streams at the hardware level. This paper proposes a bus bandwidth management and access arbitration scheme for a multimedia workstation. It assumes that a multimedia workstation consists of several specialized processing modules which are linked by a packet-switched bus. Using the proposed scheme, the bus can support a mix of continuous media streams and random transactions while fulfilling special requirements of each traffic type. Specifically, the bus provides fast response to random transactions and serves continuous media streams in such a way that no packet falls behind its deadline. Furthermore, the performance with respect to continuous media traffic is maintained independent of time variations of random traffic. Practical implementation guidelines are provided. Finally, the performance of the proposed scheme is compared with alternative approaches.

Return to the top

Return to:

Prepared by Diana Ehrlich
Last modified November 1, 1996

Applied Research LaboratoryPublications by AuthorSaied Hossieni-Khayat