Refereed Publications

F. Azzedin and M. Maheswaran, ``Trust Modeling for Peer-to-Peer based Computing Systems,'' 12th IEEE Heterogeneous Computing Workshop (HCW 2003), accepted to appear. [Paper (PDF)].

M. Migliardi, M. Maheswaran, B. Maniymaran, P. Card, and F. Azzedin, ``Mobile Interfaces to Computational, Data, and Service Grid Systems,'' ACM Mobile Computing and Communication Review, accepted to appear. [Paper (PDF)].

This article briefly describes the issues related to providing mobile access to computational, data, and service Grids. Then it describes our preliminary efforts to enhance computational and service Grids to handle mobile access. In particular, we focus on how the HARNESS mobile extensions project approaches the problem of enhancing Grid computers with mobile access and we describe how the InviNet project provides access to service Grids with consistent quality of service.
F. Azzedin, M. Maheswaran, and N. Arnason, ``A Synchronous Co-allocation Mechanism for Grid Computing Systems,'' Cluster Computing, The Journal of Networks, Software Tools and Applications, accepted to appear. [Paper (PDF)].

F. Azzedin and M. Maheswaran, ``Integrating Trust into Grid Resource Management Systems,'' 2002 International Conference on Parallel Processing (ICPP 2002), Aug. 2002, pp. 47-54. [Paper (PDF)].

Grid computing systems that have been the focus of much research activities in recent years provide a virtual framework for controlled sharing of resources across institutional boundaries. Security is one major concern in any system that enables remote execution. Several techniques can be used for providing security in Grid systems including sandboxing, encryption, and other access control and authentication mechanisms. The additional overhead caused by these mechanisms may negate the performance advantages gained by Grid computing. Hence, we contend that it is essential for the scheduler to consider the security implications while performing resource allocations. In this paper, we present a trust model for Grid systems and show how the model can be used to incorporate the security implications into scheduling algorithms. Three scheduling heuristics that can be used in a Grid system are modified to incorporate the trust notion and simulations are performed to evaluate the performance.
M. Maheswaran, B. Maniymaran, P. Card, and F. Azzedin, ``MetaGrid: A Scalable Framework for Wide-Area Service Deployment and Management,'' 16th International Symposium on High Performance Computing Systems and Applications (HPCS 2002), June 2002, accepted to appear. [Paper (PDF)].

This paper presents a novel architecture called the MetaGrid based on Grid computing concepts for resource provisioning for wide-area network-enabled applications. Resource provisioning for wide-area applications can involve coordinated allocation of computing and communication resources. A Grid computing systems provides a virtual framework that facilitates controlled resource sharing among different institutions. The MetaGrid extends the Grid computing systems in two major ways: (a) introduces a notion of SubGrid that provides a coarse-grained resource allocation class and (b) introduces a framework for interconnecting Grids by facilitating peering, trading, and brokering among the different Grids. This paper presents (a) the overall architecture of the MetaGrid with a description of the different functional components, (b) the resource allocation model that is introduced by the notion of SubGrids, and (c) strategies of interconnecting Grids.
M. Maheswaran, B. Maniymaran, P. Card, and F. Azzedin, ``Invisible Network: Concepts and Architecture,'' 2002 International Workshop on Invisible Computing, May 2002. [Paper (PDF)].

Efficient schemes for deploying and maintaining widearea services and accessing such services are essential if the Internet is to sustain itself as the communication medium for business critical applications. This paper presents the architecture of an overlay service network called the Invisible Network. It is based on a two-stage architecture. The first-stage is responsible for service addressing, discovery, and mobility. The second-stage is responsible for quality of service aware resource allocation for wide-area services. The two stages together provide a unique service network that makes the wide-area services "invisible" by hiding the locational and implementational details of the wide-area services.
K. Subramoniam, M. Maheswaran, and M. Toulouse, ``A Micro-Economic Model for Resource Allocation in Grid Computing Systems,'' IEEE Canadian Conference on Electrical & Computer Engineering (CCECE '02), May 2002. [Paper (PDF)].

Due to the expected scale of the Grid computing systems, we need to develop highly distributed and extensible resource allocation frameworks for such systems. Micro-economic principles such as auctioning and commodity market are two approaches that are being pursued by several researchers for the Grid resource allocation problem. In this paper, we use a commodity market based approach to allocate resources, where resources are classified into different classes based on the hardware components, network connectivity, and operating system. In commodity market, the prices of the commodities (``resources'') are fixed using individual supply and demand functions. In this paper we have developed an algorithm to determine the price of the resource. The simulation results show the performance of the pricing algorithm used in the commodity market.
F. Azzedin and M. Maheswaran, ``Evolving and Managing Trust in Grid Computing Systems,'' IEEE Canadian Conference on Electrical & Computer Engineering (CCECE '02), May 2002. [Paper (PDF)].

A Grid computing system is a geographically distributed environment with autonomous domains that share resources amongst themselves. One primary goal of such a Grid environment is to encourage domain-to-domain interactions and increase the confidence of domains to use or share resources (a) without losing control over their own resources, and (b) ensuring confidentiality for others. To achieve this, the ``trust" notion needs to be addressed so that trustworthiness makes such geographically distributed systems become more attractive and reliable for day-to-day use. In this paper, we view trust in two steps: (a) verifying the identity of an entity and what that identity is authorized to do, and (b) monitoring and managing the behavior of the entity and building a trust level based on that behavior. The identity trust has been the focus of many researchers, but unfortunately the behavior trust did not catch much attention. We present a formal definition of behavior trust and reputation and discuss a behavior trust management architecture that models the process of evolving and managing of behavior trust in Grid computing Systems.
F. Azzedin and M. Maheswaran, ``Towards Trust-Aware Resource Management in Grid Computing Systems,'' First IEEE International Workshop on Security and Grid Computing, May 2002. [Paper (PDF)].

Resource management is a central part of a Grid computing system. In a large-scale wide-area system such as the Grid, security is a prime concern. One approach is to be conservative and implement techniques such as sandboxing, encryption, and other access control mechanisms on all elements of the Grid. However, the overhead caused by such a design may negate the advantages of Grid computing. This study examines the integration of the notion of ``trust'' into resource management such that the allocation process is aware of the security implications. We present a formal definition of trust and discuss a model for incorporating trust into Grid systems. As an example application of the ideas proposed, a resource management algorithm that incorporates trust is presented. The performance of the algorithm is examined via simulations.
R. Min and M. Maheswaran, ``Scheduling Co-Reservations with Priorities in Grid Computing Systems,'' 2nd IEEE International Symposium on Cluster Computing and Grid (CCGrid '2002), May 2002, appeared as a short paper/poster. [Paper (PDF)].

C. Chen, M. Maheswaran, and M. Toulouse, ``Supporting Co-allocation in an Auctioning-based Resource Allocator for Grid Systems,'' 11th IEEE Heterogeneous Computing Workshop (HCW 2002), Apr. 2002. [Paper (PDF)].

In this paper, we present the overall design for an auctioning based resource trading/acquiring system that can be deployed in wide-area computing systems such as Grid systems. Selecting the winning bids is one of the core issues in any system that utilizes the auctioning paradigm. We identify the unique aspects of our system that impact the winner selection process. More specifically, the necessity to acquire or trade resources as a bundle (i.e., perform co-allocation) presents a challenge to traditional bidding mechanisms. We present a new bidding mechanism called ``co-bids'' to address this problem. Two heuristics for winner selection with co-bids are proposed. The performance of the heuristics are examined via simulations.
H. Chen and M. Maheswaran, ``Distributed Dynamic Scheduling of Composite Tasks on Grid Computing Systems,'' 11th IEEE Heterogeneous Computing Workshop (HCW 2002), Apr. 2002. [Paper (PDF)].

This paper examines the issue of dynamically scheduling applications on a wide-area network computing system. We construct a simulation model for wide-area task allocation problem and study the performance of the proposed algorithm under different conditions. The simulation results indicate that the wide-area scheduling algorithm is sensitive to several parameters including machine failure rates, the local queuing policies, and arrival rates.
K. S. Teng and M. Maheswaran, ``Limited Scope Probing: A Distributed Approach for QoS-based Routing,'' IEEE International Symposium on Network Computing and Applications (NCA '2002), Feb. 2002, pp. 350-353. [Paper (PDF)].

K. Krauter, R. Buyya, and M. Maheswaran, ``A Taxonomy and Survey of Grid Resource Management Systems,'' Software Practice and Experiance, Vol. 32, No. 2, Feb. 2002, pp. 135-164. [Paper (PDF)].

The resource management system is the central component of network computing systems. There have been many projects focused on network computing that have designed and implemented resource management systems with a variety of architectures and services. In this paper, an abstract model and a comprehensive taxonomy for describing resource management architectures is developed. The taxonomy is used to identify approaches followed in the implementation of existing resource management systems for very large-scale network computing systems known as Grids. The taxonomy and the survey results are used to identify architectural approaches and issues that have not been fully explored in the research.
P. Card, B. Maniymaran, M. Maheswaran, and F. Azzedin ``Invisible Networking: A Service Model for the Networks of the Future'' Advanced Topic Workshop on Middleware for Mobile Computing (held with IFIP/ACM Middleware 2001 Conference), Nov. 2001, appeared as a short paper/poster. [Paper (PDF)].

F. Azzedin and M. Maheswaran, ``Synchronous Queuing: A Co-allocation Mechanism for Multimedia Enabled Grids,'' Thirteenth IASTED International Conference on Parallel and Distributed Computing Systems (PDCS '01), Aug. 2001, pp. 27-32. [Paper (PDF)].

The multimedia enabled Grid (MEG) is an extension of the Grid concept to support the deployment of multimedia services. To provide an adequate level of service to multimedia applications, it is often necessary to simultaneously allocate the resources including predetermined capacities from the interconnecting networks to the applications. The simultaneous allocation of resources is often referred to as co-allocation in the Grid literature. In this paper, we propose a novel scheme called synchronous queuing (SQ) for implementing co-allocation with quality of service (QoS) assurances in Grids. Unlike existing approaches, SQ does not require advance reservation capabilities at the resources. In the simulation, we increase the imposed load with increasing number of machines to test SQ's effectiveness in addressing the co-allocation problem. This is because the co-allocation complexity is known to increase with the increase of the imposed load. The simulation studies performed to evaluate SQ indicate that it outperforms an admission control-based scheme by a significant margin.
R. Min and M. Maheswaran, ``Scheduling Advance Reservations with Priorities in Grid Computing Systems,'' Thirteenth IASTED International Conference on Parallel and Distributed Computing Systems (PDCS '01), Aug. 2001, pp. 172-176 [Paper (PDF)].

Grid computing systems utilize distributively owned and geographically dispersed resources for providing a wide variety of services for various applications. One of the key considerations in Grid computing systems is resource management with quality of service constraints. The quality of service constraints dictate that submitted tasks should be completed by the Grid in a timely fashion while delivering at least a certain level of service for the duration of execution. Because the Grid is a highly "dynamic" system due to the arrival and departure of tasks and resources, it is necessary to perform advance reservations of resources to ensure their availability to meet the requirements of the different tasks. This paper introduces a new scheduling algorithm for advance reservations. Simulations are performed to compare our algorithm with an existing approach. The results indicate that the proposed algorithm can improve the overall the performance by satisfying larger number of reservation requests.
S. Philopoulos and M. Maheswaran, ``Experimental Study of Parallel Downloading Schemes for Internet Mirror Sites,'' Thirteenth IASTED International Conference on Parallel and Distributed Computing Systems (PDCS '01), Aug. 2001, pp. 44-48 [Paper (PS)].

A common method used to reduce document retrieval times is the use of content replication i.e., mirror servers. The mirror servers provide several alternate sites to download a specific document and were traditionally used to increase the availability of content. Recently, several studies focused on using multiple mirror sites to concurrently download portions of a document from a set of mirror sites. Following are some of the issues involved in using multiple mirror sites concurrently: (a) selection of the ``best'' mirror servers from the client, (b) coping with dynamic overloading of the network and servers, and (c) coping with faults. This paper briefly examines two existing schemes for concurrent downloading or parallel-access downloading, or paraloading as it is called. It proposes a third paraloading scheme called the Dynamic Parallel Access. The performance of this scheme is experimentally evaluated. Recommendations for further improvements are also discussed.
C. Chen, M. Maheswaran, and M. Toulouse, ``On Bid Selection Heuristics for Real-Time Auctioning for Wide-Area Network Resource Management,'' 2001 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA 2001), July 2001 [Paper (PDF)].

We present an online auctioning based resource management system called the Computation Market (CM) for very large scale networked computing systems. Some of the distinguishing features of this system are scalability, localized control, adaptability, and on-demand resource acquisition. The core of the online auctioning process is a two-level bidding protocol. The first level of the protocol handles the resource management within a local market. The second level of the bidding protocol coordinates the inter-market resource flows. The CM differs from other systems in its capability to aggregate computing power. It uses local brokers to aggregate independently managed machines from the same network segment into a cluster. This aggregation at the supplier side allows co-allocation of resources that is essential to support parallel computing applications. The CM also allows the clients to bid for different combinations of machines and networks from the pool of resources. To achieve this, it uses a combinatorial auctioning mechanism. Selecting the "best" set of bids in such a combinatorial auctioning system is a NP-complete problem. In this paper, we present several fast heuristics for determining the winning bids. Simulations were performed to evaluate the performance of these heuristics under different situations and compare them with an upper bound of the optimal algorithm.
S. Pradhan, Y. Li, and M. Maheswaran, ``QoS-Aware Hierarchical Multicast Routing on Next Generation Internetworks,'' 20th IEEE International Performance, Computing, and Communications Conference (IPCCC 2001), Apr. 2001 [Paper PDF)].

Quality of service (QoS) based routing and scalability are two key features of multicast routing for the next generation Internetworks. This paper proposes a new protocol called QoS-aware hierarchical multicast routing protocol (QHMRP) that achieves scalability by organizing the network as a hierarchy of domains using the full-mesh aggregation technique. The protocol uses a novel reverse flooding approach with hierarchical, topological and QoS forwarding conditions to construct the multicast tree while minimizing message overhead and satisfying QoS requirements. The distributed algorithm used in the protocol constructs loop-free tree. Simulations are performed to evaluate the performance of QHMRP under different situations and compare it with a flat routing algorithm.
M. Maheswaran, ``Data dissemination approaches for performance discovery in Grid computing systems,'' 10th IEEE Heterogeneous Computing Workshop (HCW 2001), Apr. 2001 [Paper PS (gzipped) 112K].

A Grid system is essentially an infrastructure that allows location independent access to the resources and services that are provided by geographically distributed machines and networks. One fundamental operation necessary to support such a system is performance discovery in wide-area networks. Dissemination of resource status information is an important component of any performance discovery algorithm. The data dissemination for performance discovery in Grid systems has several distinct features and requirements that can be exploited to make the process efficient. Recently, several data dissemination algorithms based on a new concept called the Grid potential were proposed. This paper introduces a new algorithm for data dissemination and compares it with previously introduced schemes through simulation studies. The results indicate that the new algorithm further improves the performance of data dissemination.
K. Krauter and M. Maheswaran, `` Architecture for a Grid operating system,'' 1st IEEE/ACM International Workshop on Grid Computing (Grid 2000), Dec. 2000 [Paper PS (gzipped) 82K].

Grid computing systems are being positioned as a computing infrastructure of the future that will enable the usage of wide-area network computing systems for a variety of challenging applications. The architecture of the Grid will determine if it will meet these challenges. We propose a Grid architecture that is motivated by the large-scale routing principles in the Internet to provide an extensible, high-performance, scalable, and secure Grid. Central to the proposed architecture is a middleware called the Grid operating system (GridOS). This paper describes the components of the GridOS. The GridOS includes several novel ideas including (i) a flexible naming scheme called the "Gridspaces," (ii) a service mobility protocol, and (iii) a highly decentralized Grid scheduling mechanism called the router-allocator.
M. Maheswaran and K. Krauter, ``A Parameter-based approach to resource discovery in Grid computing systems,'' 1st IEEE/ACM International Workshop on Grid Computing (Grid 2000), Dec. 2000 [Paper PDF 45K].

A Grid system is essentially an infrastructure that allows location independent access to the resources and services that are provided by geographically distributed machines and networks. One of the fundamental operations needed to support location-independent computing is resource discovery. Generally, resource discovery schemes maintain and query a resource status database. Dissemination of the resource status information is one of the key operations required to keep the resource status databases consistent. This paper examines several approaches for resource status dissemination. A new concept called the Grid potential is introduced in this paper. This concept is used to control the extent of data dissemination in Grid systems.
T. Vaseeharan and M. Maheswaran, ``Towards a novel architecture for wide-area data caching and replication,'' First International Conference on Interent Computing (IC 2000), June 2000. [Paper PS (gzipped) 39K]

Caching and Replication play a critical role in alleviating network latency and server load. In this paper, we propose an Active Networks based architecture for improving caching/replication that operates by obtaining statistics from the network nodes to identify hot-spots in client access patterns. The objects are endowed with the intelligence to make their own replication decisions based on the access statistics. Existing schemes such as hierarchical proxy servers and DNS based server load balancing are not designed to the geographical and temporal spikes in user demand. Thus there is a clear need for schemes that are scalable and self-managed.
K. Krauter and M. Maheswaran, ``Towards and extensible high-performance Grid architecture,'' 14th International Symposium on High Performance Computing Systems and Applications (HPCS 2000), June 2000. [Paper PDF 200K]

Grid computing systems are being positioned as the high performance computing infrastructure of the future that will be used to solve grand challenge problems and also provide the infrastructure for wide area distributed network computing. The architecture of the Grid will determine if it will meet these challenges. We propose a Grid architecture that is secure, high performance and extensible. It is based on the concept of a small, lightweight Grid kernel that provides uniform resource management services and runs on both traditional network equipment and host computers. More comprehensive Grid services are layered on top of the Grid kernel.
M. Maheswaran, H. Chen, S. Pradhan, P. Pantel, L. Zheng, R. Min, and T. Groner, ``A resource management system for network computing using Java,'' 5th International Conference on Computer Sciences and Informatics (CSI '2000), Feb. 2000, pp. 453-457. [Paper PS (gzipped) 40K]

A network computing (NC) system is a virtual entity that can comprise of heterogeneous machines belonging to different administrative domains connected via high-speed networks. This paper describes the issues involved in designing and implementing a resource management system (RMS) using Java for NC systems. The issues addressed in this study include: (a) portability of the RMS across different platforms, (b) scalability of the RMS with the number of machines, (c) heterogeneity among the constituent machines, (d) learning task attributes (in particular, execution times) from previous actual execution times of the application, and (e) remote access to input and output data files. Initially, the RMS was designed for a dedicated networked computer system. Enhancements to extend the RMS to a non-dedicated environment are discussed. The scheduling component of the RMS can use different modes of scheduling. Two strategies are used in this study depending on the arrival rate of the tasks. Some results obtained from a timing study are also presented.
M. Maheswaran, S. Ali, H. J. Siegel, D. Hensgen, R. F. Freund, ``Dynamic mapping of a class of independent tasks onto heterogeneous computing systems,'' Journal of Parallel and Distributed Computing, Vol. 59, No. 2, Nov 1999, pp. 107-131. [Paper PS (gzipped) 60K]

Dynamic mapping (matching and scheduling) heuristics for a class of independent tasks using heterogeneous distributed computing systems are studied. Two types of mapping heuristics are considered: on-line and batch mode heuristics. Three new heuristics, one for batch and two for on-line, are introduced as part of this research. Simulation studies are performed to compare these heuristics with some existing ones. In total, five on-line heuristics and three batch heuristics are examined. The on-line heuristics consider, to varying degrees and in different ways, task affinity for different machines and machine ready times. The batch heuristics consider these factors, as well as aging of tasks waiting t o execute. The simulation results reveal that the choice of mapping heuristic depends on parameters such as: (a) the structure of the heterogeneity among tasks and machines, (b) the optimization requirements, and (c) the arrival rate of the tasks.
M. Maheswaran, S. Ali, H. J. Siegel, D. Hensgen, and R. Freund, ``Dynamic mapping of a class of independent tasks onto heterogeneous computing systems,'' 8th IEEE Heterogeneous Computing Workshop (HCW '99), Apr. 1999, pp. 30-44. [Paper PS (gzipped) 63K]

M. Maheswaran, T. D. Braun, H. J. Siegel, ``Heterogeneous distributed computing,'' in Encyclopedia of Electrical and Electronics Engineering, J. G. Webster, ed., John Wiley, New York, NY, 1999, Vol. 8, pp. 679-690. [Paper PS (gzipped) 312K]

This book chapter provides an introduction to many different aspects of heterogeneous distributed computing by summarizing relevant papers from a variety of research projects. A broad overview of heterogeneous computing (HC) is given, followed by several case studies that give more specific details of applications executing on HC systems. Then, a sampling of current HC tools and environments provides insights into the actual implementation of HC systems at many different levels. Next, methods of classifying HC systems are described. One of the long term goals of HC is the development of an environment that will automatically find a near optimal matching and scheduling for tasks and machines. The development of such an environment is described by the given conceptual model. The remaining concepts covered in this chapter are techniques for benchmarking machines, techniques for profiling tasks, and schemes that use the information regarding machines and tasks to derive a mapping of the tasks onto the machines.

Unrefereed Publications

M. Maheswaran, ``Quality of service driven resource management algorithms for network computing,'' 1999 International Conference on Parallel and Distributed Processing Technologies and Applications (PDPTA '99), June 1999, pp. 1090-1096. [Paper PS (gzipped) 35K]

This paper presents a novel approach that takes into account the quality of service (QoS) requested by the applications when scheduling the computational resources in a network computing system. The scheduling algorithms examined here are dynamic and centralized. The QoS model used in this study only uses metrics such as application deadlines and application priorities. However, the model is general enough to be extended to handle other QoS metrics. The level of service received by each application is quantified by a benefit function defined for that application. Maximizing the total benefit provided to the applications is the optimization criterion used in designing the dynamic scheduling algorithms. Simulations were performed to evaluate the performance of the algorithms. Some preliminary results from an evaluation study are presented here.

Technical Reports

T. Vaseeharan and M. Maheswaran, Active Data Objects: A Novel Architecture for Content Delivery in Internetworks, Technical Report TR-CS 00-11, Department of Computer Science, University of Manitoba, May 2000.

Internet content providers are increasingly resorting to outsourcing content delivery as user demand escalates. An objective of a content deliverer is to reduce end user access latency given a set of geographically distributed resources. In this paper, we present an architecture for locating data objects in optimal service provision points on the network to achieve this objective. It has two novel components: (a) distributed computation of client access patterns and (b) active data objects (ADOs) that analyze access statistics obtained from the network for replication/migration. We use active networks to place intelligence into the network to monitor and compute user access patterns in a distributed fashion. The ADO provides an software infrastructure that can be used by heuristics derived from facility location theories to optimally locate the data objects. We have implemented a prototype to test the architecture. It uses the Active Node Transfer System toolkit for active networking. The Webpolygraph suite is used to evaluate the operation of the prototype under different load conditions.
K. Krauter and M. Maheswaran, Architecture for a Grid Operating System, Technical Report TR-CS 00-12, Department of Computer Science, University of Manitoba, May 2000.

Grid computing systems are being positioned as a computing infrastructure of the future that will enable the usage of wide-area network computing systems for a variety of challenging applications. The architecture of the Grid will determine if it will meet these challenges. We propose a Grid architecture that is motivated by the large-scale routing principles in the Internet to provide an extensible, high-performance, scalable, and secure Grid. Central to the proposed architecture is a middleware called the Grid operating system (GridOS). This paper describes the components of the GridOS. The GridOS includes several novel ideas including (i) a flexible naming scheme called the Gridspaces, (ii) a service mobility protocol, and (iii) a highly decentralized Grid scheduling mechanism called the router-allocator.
M. Maheswaran and K. Krauter, A Parameter-based Approach to Resource Discovery in Grid Computing Systems, Technical Report TR-CS 00-13, Department of Computer Science, University of Manitoba, May 2000.

A Grid system is essentially an infrastructure that allows location independent access to the resources and services that are provided by geographically distributed machines and networks. To enhance the overall performance, sophisticated resource management schemes must be implemented on such systems. One of the fundamental operations needed to support location-independent computing is resource discovery. Because Grid systems are expected to scale to Internet proportions, it is essential to employ resource discovery schemes with low communication complexity. Generally, resource discovery schemes maintain and query a resource status database. Dissemination of the resource status information is one of the key operations required to keep the resource status databases consistent. This paper examines several approaches for resource status dissemination. A new concept called the Grid potential is introduced. This concept is used as a "time-to-live" to control extent of data dissemination in Grid systems. The Grid potential idea is motivated by the observation that a Grid system is likely to have heterogeneous sets of the machines and the usefulness of the status information of a machine is dependent on the relative "power" of the machine.

Theses

S. Pradhan, QoS-Aware Hierarchical Multicast Routing in Next Generation Internetworks, MSc Thesis, Department of Computer Science, University of Manitoba, Apr. 2000 (Advisor: M. Maheswaran). [Thesis PDF 192K]

Quality of service (QoS) based routing and scalability are two key features of multicast routing for the next generation Internetworks. This paper proposes a new protocol called QoS-aware hierarchical multicast routing protocol (QHMRP) that achieves scalability by organizing the network as a hierarchy of domains using the full-mesh aggregation technique. The protocol uses a novel reverse flooding approach with hierarchical, topological and QoS forwarding conditions to construct the multicast tree while minimizing message overhead and satisfying QoS requirements. The distributed algorithm used in the protocol constructs loop-free tree. Simulations are performed to evaluate the performance of QHMRP under different situations and compare it with a flat routing algorithm.
F. Azzedin, Synchronous Queuing: A Co-allocation Mechanism for Multimedia Enabled Grids, MSc Thesis, Department of Computer Science, University of Manitoba, May 2001 (Advisor: M. Maheswaran). [Thesis PDF]

Grid computing systems are being positioned as a computing infrastructure of the future that will enable the usage of wide-area network computing systems for a variety of challenging applications. The multimedia enabled Grid (MEG) is an extension of the Grid concept to support the deployment of multimedia services to meet the ever increasing demand for multimedia from users engaging in a wide range of activities such as scientific research, education, commerce, and entertainment. The MEG will provide several new services and sustain several enabling technologies to support multimedia. To provide an adequate level of service to multimedia applications, it is often necessary to simultaneously allocate the resources including predetermined capacities from the interconnecting networks to the applications. The simultaneous allocation of resources is often referred to as co-allocation in the Grid literature. In this thesis, I propose a novel scheme called synchronous queuing (SQ) for implementing co-allocation with quality of service (QoS) assurances in Grids. The SQ does not require advance reservation capabilities at the resources, which is a fundamental difference between SQ and the other existing schemes. I formally define the co-allocation problem and classify existing approaches based on a taxonomy that is presented here. Based on the taxonomy, I discuss the situations under which SQ can be used for co-allocation in MEGs. The SQ scheduler introduces new scheduling concepts such as the notion of accounting for the previous work, the notion of introducing intraQueue and interQueue schedulers and the notion of calculating the co-allocation skew. Simulation studies performed to evaluate SQ indicate that it outperforms admission control-based scheme by a significant margin.
H. Chen, Distributed Dynamic Scheduling of Composite Tasks on Grid Computing System, MSc Thesis, Department of Electrical and Computer Engineering, University of Manitoba, Sep. 2001 (Advisor: M. Maheswaran). [Thesis PDF]

Network computing attracts the attention of many computer researchers and scientists because it can better utilize existing computing resources. The key challenge of network computing is the search for the best method to distribute computing resources to submitted tasks. This thesis demonstrates a distributed dynamic scheduling of composite tasks on a grid computing system. It describes how a computer program was written to simulate a real world computer network. Submitted tasks consist of subtasks represented by DAGs. The adopted scheduling and mapping include two steps: one external and the other internal. External scheduling and mapping are performed on the task level, and internal scheduling and mapping are done on the subtask level. A task and its subtask must go through these two steps to be allocated computing resources. This research analyzes different factors on the distributed dynamic scheduling algorithm. The factors include Subtask Waiting Queue size, submitted task number, task submission interval, and network infrastructure. The percentage of tasks completed before deadline and average response times are used as indexes of network computing performance.
R. Min, Scheduling Advance Reservations with Priorities in Grid Computing Systems, MSc Thesis, Department of Electrical and Computer Engineering, University of Manitoba, Sep. 2001 (Advisor: M. Maheswaran). [Thesis PDF]

Grid computing systems utilize distributively owned and geographically dispersed resources for providing a wide variety of services for various applications. One of the key considerations in Grid computing systems is resource management with quality of service constraints. The quality of service constraints dictate that submitted tasks should be completed by the Grid in a timely fashion while delivering at least a certain level of service for the duration of execution. Because the Grid is a highly "dynamic" system due to the arrival and departure of tasks and resources, it is necessary to perform advance reservations of resources to ensure their availability, and to meet the requirements of the different tasks. This thesis introduces two new scheduling algorithms for advance reservations including co-reservations, namely, Reservation Scheduler with Priorities and Benefit Functions (RSPB) and Co-Reservation Scheduler with Priorities and Benefit Functions (Co-RSPB). The algorithms consider the relative priorities of various reservation requests while scheduling reservations. The benefit function is used to quantify the "profit" for the client in order to remove the re-negotiation overhead in case of resource scarcity. Simulations are performed to compare proposed algorithms with an existing approach or with some comparison algorithms developed as basic comparison line in this thesis. The results indicate that the proposed algorithms can improve the overall the performance by satisfying larger number of reservation requests.
A. Mitra, Design and Analysis of a Content-based Routing System for High Speed Networks, MSc Thesis, Department of Computer Science, University of Manitoba, Feb. 2002 (Advisor: M. Maheswaran). [Thesis PDF]

Content networking is an emerging technology, where the requests for content accesses are steered by ``content routers'' that examine not only the destinations but also content descriptors such as URLs and cookies. In the current deployments of content networking, ``content routing'' is mostly confined to selecting the most appropriate back-end server in virtualized web server clusters. With the deployment of mechanisms for wide-spread replication of content among geographically distributed servers, a question arises regarding the optimal form of request routing. In this thesis, we examine the following questions via simulation- based performance modelling: (a) Is content-aware routing superior to address-based routing with wide-area replica placements? (b) Under what conditions does performance differences exist between the two approaches? and (c) What attributes of the content should be considered for efficient wide-area content routing? As part of this study, we present a novel content-based routing mechanism called the Virtual Content Network for wide-area networks. Simulations are carried out to compare the performance of our content-based wide-area routing mechanism with a domain name based routing mechanism.
C. Chen, Computation Market: Design and Experiments, MSc Thesis, Department of Computer Science, University of Manitoba, June 2002 (Advisors: M. Maheswaran and M. Toulouse). [Thesis PDF]

P. Narula, Authorization Management Framework, MSc Thesis, Department of Electrical and Computer Engineering, University of Manitoba, Aug. 2002 (Advisor: M. Maheswaran). [Thesis PDF]