Scheduling Real-time Divisible Loads in Cluster Computing Environment

Aryadipta, Abhinandan and Behera, Avinash (2012) Scheduling Real-time Divisible Loads in Cluster Computing Environment. BTech thesis.

PDF 871Kb

Abstract

The significance of cluster computing in solving massively parallel workloads is tremendous. Divisible Load Theory has proven to be very successful in optimizing the usage of the system resources by partitioning the arbitrarily divisible loads adequately among the cluster nodes. Arbitrarily divisible loads have significant real-world applications in high energy and particle physics. In this thesis, various algorithms for a cluster computing environment are studied including the ones dealing with divisible load theory confirming DLT based algorithms performing better in most cases. The loads that are considered in this thesis are hard real-time tasks with associated deadlines. Specifically, a comparison is made between clusters with one where the head node doesn't participate in processing of the work-loads with the other where the head node does participate in processing of the work-loads. A new mathematical formula is derived for the task execution time corresponding to the new scenario of head node possessing front-end processing capability. The existing algorithms corresponding to Real-Time Divisible Load Theory are then implemented using this new formula to examine the scheduling performance in this new scenario compared to the conventional scenario where the head node lacks front-end processing capability.

Static Slicing of Interprocedural Programs

Arya, Dheeraj Kumar and Kumar, Rakesh (2012) Static Slicing of Interprocedural Programs. BTech thesis.

PDF (Static Slicing of Interprocedural Programs) 746Kb

Abstract

Program slicing has many applications in a software development environment such as debugging, testing, anomaly detection, program understanding and many more. The concept being introduced by Weiser and it was started with static slicing calculation. Talking about static slicing, it is a subset of statements of a program which directly or indirectly affect the values of the variables computed providing a slicing criterion. In this project, we have developed an approach for creating an intermediate representation of a program in the form of System Dependence Graph (SDG) which is to be, again taken as input for computing the slicing of a program with respect to slicing criterion. The slicing approach computes the slices with respect to a given slicing criterion. For generating the graph, we have analysed the input program, identified the tokens and finally generated the relation between tokens as data dependent or control dependent. For calculating the slice, we have used two-phase graph reachability algorithm developed by Horwitz, Reps and Binkley, which creates a graph consisting of only those nodes that are dependent on slicing criterion. Finally we have plotted a graph between time taken to create graph versus number of functions used in program. Our approach of calculating slices has been limited only to C programs.

Routing in Delay Tolerant Networks

AlamMd., Md. Raiyan and Minz, Bibekanand (2012) Routing in Delay Tolerant Networks. BTech thesis.

PDF 873Kb

Abstract

Delay-tolerant networks (DTNs) have the great potential to connecting devices and regions of the world that are presently under-served by current networks. A vital challenge for Delay Tolerant Networks is to determine the routes through the network without ever having an end to end path, or knowing which routers will be connected at any given instant of time. The problem has an added constraint of limited size of buffers at each node. This situation limits the applicability of traditional routing techniques which categorize lack of path as failure of nodes and try to seek for existing end-to-end path. Approaches have been proposed which focus either on epidemic message replication or on previously known information about the connectivity schedule. The epidemic approach, which is basically a flooding technique, of replicating messages to all nodes has a very high overhead and does not perform well with increasing load. It can, however, operate without any prior information on the network configuration. On the other hand, the alternatives, i.e., having a prior knowledge about the connectivity, seems to be infeasible for a self-configuring network.

In this project we try to maximize the message delivery rate without compromising on the amount of message discarded. The amount of message discarded has a direct relation to the bandwidth used and the battery consumed. The more the message discarded more is the bandwidth used and battery consumed by every node in transmitting the message. At the same time, with the increase in the number of messages discarded, the cost for processing every message increases and this adversely affects the nodes. Therefore, we have proposed an algorithm where the messages are disseminated faster into the network with lesser number of replication of individual messages. The history of encounter of a node with other nodes gives noisy but valuable information about the network topology. Using this history, we try to route the packets from one node to another using an algorithm that depends on each node’s present available neighbours/contact and the nodes which it has encountered in the recent past. We have also focused on passing the messages to those nodes which are on the move away from the source/forwarder node, as the nodes moving away have a greater probability of disseminating the messages throughout the network and hence increases chances of delivering the message to the destination.

Pattern Clustering using Soft-Computing Approaches

Agrawal, Mohit (2012) Pattern Clustering using Soft-Computing Approaches. BTech thesis.

PDF 576Kb

Abstract

Clustering is the process of partitioning or grouping a given set of patterns into disjoint clusters. This is done such that patterns in the same cluster are alike and patterns belonging to two dierent clusters are dierent. . Clustering Process can be divided into two parts
Cluster formation
Cluster validation
The most trivial K-means algorithm is rst implemented on the data set obtained from UCI machine repository. The comparison is extended to Fuzzy C-means algorithm where each data is a member of every cluster but with a certain degree known as membership value. Finally, to obtain the optimal value of K Genetic K-means algorithm in implemented in which GA nds the value of K as generation evolves.The
ecieny of the three algorithms can be judged on the two measuring index such as :
the silhouette index and Davies-Bouldin Index .

Secure Messaging Service on Google App Engine using ECC and RSA Encryption

Agarwal, Keshav (2012) Secure Messaging Service on Google App Engine using ECC and RSA Encryption. BTech thesis.

PDF 694Kb

Abstract

The idea behind this project was to develop a simple Secure Message Passing System based on Public Key encryption schemes of ECC and RSA. A Secure Messaging System is used to share information beyond corporate boundaries. Such information is highly sensitive and thus must be kept secret. Advantages of use of Secure Messaging Service over a generic Email service is that no extra software installation and key sharing will be necessary to kept the message safe against any kind of eavesdropping.The
motivation behind the project was the need for a message passing system completely free from any leaks in information.
The System was to be developed on the cloud platform thus harnessing its Software as a Service feature. Google App Engine was chosen for the deployment of the Application.

ESAR: Energy Saving Ad Hoc Routing Protocol for Mobile Ad Hoc Networks

 Utkarsh and Mishra, Mukesh Kumar (2012) ESAR: Energy Saving Ad Hoc Routing Protocol for Mobile Ad Hoc Networks. BTech thesis.

PDF 790Kb

Abstract

Mobile ad hoc networks support multi hop routing where the deployment of central base station is neither economic nor easy. Efficient routing of the packets is a major challenge in the ad hoc networks. There exist several proactive (like DSDV etc.) and reactive (Like AODV etc.) routing algorithms for the dynamic networks.The ESAR algorithm selects the path with minimum cost value indicating that the path has the shortest distance to the destination and has the maximum of the minimum available battery power of the node among the different paths. This selected path is chosen as the best path for packet transmission till any node in the path exhausts battery power beyond a threshold value. At this point of time, a backup path having the next lower cost is selected as an alternate path for packet transmission. The process is repeated till all the paths from the same source to destination are exhausted with their battery power. When this situation occurs, the cost of the paths is re-calculated and the process continues. The simulation result of the proposed algorithm ESAR enhances the network life time over the AODV and EEAODR algorithm.

Heuristics for license plate localization and hardware implementation of Automatic License Plate Recognition (ALPR) system

Chhabada, Sandeep Singh (2012) Heuristics for license plate localization and hardware implementation of Automatic License Plate Recognition (ALPR) system. BTech thesis.

PDF 1566Kb

Abstract

The project “Heuristics for license plate localization and hardware implementation of Automatic License Plate Recognition (ALPR) system” deals with detection and recognition of license plate from a captured front view of any car. The work follows all the steps in an ALPR system like preprocessing, segmentation, and license plate identification, extraction of individual characters and finally recognition of each character to form a string to match with the registered License plate numbers. The main contribution in the work is to expedite the number plate isolation from a set of segmented candidates. It utilizes a set of heuristics typically transition from object to background and vice-versa, aspect ratio of the bounding boxes. This narrow down the number of candidates for further processing and further, we suggest a rank based identification of each character in the number plate. The process scheme along with the existing methodologies is integrated to develop the overall ALPR system. A set of standard images collected from internet as well as self-collected car images of staff vehicles are used for simulation. The experiments are conducted using OpenCV. For validation, a working ALPR hardware prototype is developed using AVR development board (ATmega32 microcontroller), GP2D120 distance measurement sensor (IR-sensor).Interfacing between PC and controller-board is done using serial port. The model works with an accuracy of 80%. The ALPR system has a further scope to improve the recognition speed using parallel processing of various sub-steps.