Spatially Adaptive Block-Based Super-Resolution

Spatially Adaptive Block-Based Super-Resolution

ABSTRACT:

Super-resolution technology provides an effectiveway to increase image resolution by incorporating additionalinformation from successive input images or training samples.Various super-resolution algorithms have been proposed basedon different assumptions, and their relative performances candiffer in regions of different characteristics within a single image.Based on this observation, an adaptive algorithm is proposedin this paper to integrate a higher level image classificationtask and a lower level super-resolution process, in which weincorporate reconstruction-based super-resolution algorithms,single-image enhancement, and image/video classification intoa single comprehensive framework. The target high-resolutionimage plane is divided into adaptive-sized blocks, and differentsuitable super-resolution algorithms are automatically selected forthe blocks. Then, a deblocking process is applied to reduce blockedge artifacts. A new benchmark is also utilized to measure theperformance of super-resolution algorithms. Experimental resultswith real-life videos indicate encouraging improvements with ourmethod.

SYSTEM REQUIREMENTS:

HARDWARE REQUIREMENTS:

  • System : Pentium Dual Core.
  • Hard Disk : 120 GB.
  • Monitor : 15’’LED
  • Input Devices : Keyboard, Mouse
  • Ram :1 GB

SOFTWARE REQUIREMENTS:

  • Operating system : Windows 7.
  • Coding Language :MATLAB
  • Tool : MATLAB R2013A

REFERENCE:

Heng Su, Liang Tang, Ying Wu, Senior Member, IEEE, Daniel Tretter, and Jie Zhou, Senior Member, IEEE, “Spatially Adaptive Block-Based Super-Resolution”, IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 21, NO. 3, MARCH 2012.

Sparse Color Interest Points for Image Retrieval and Object Categorization

Sparse Color Interest Points for Image Retrieval and Object Categorization

ABSTRACT:

Interest point detection is an important research areain the field of image processing and computer vision. In particular,image retrieval and object categorization heavily rely on interestpoint detection from which local image descriptors are computedfor image matching. In general, interest points are based on luminance,and color has been largely ignored. However, the use of colorincreases the distinctiveness of interest points. The use of colormay therefore provide selective search reducing the total numberof interest points used for image matching. This paper proposescolor interest points for sparse image representation. To reduce thesensitivity to varying imaging conditions, light-invariant interestpoints are introduced. Color statistics based on occurrence probabilitylead to color boosted points, which are obtained throughsaliency-based feature selection. Furthermore, a principal componentanalysis-based scale selectionmethod is proposed, which givesa robust scale estimation per interest point. From large-scale experiments,it is shown that the proposed color interest point detectorhas higher repeatability than a luminance-based one. Furthermore,in the context of image retrieval, a reduced and predictablenumber of color features show an increase in performancecompared to state-of-the-art interest points. Finally, in the contextof object recognition, for the Pascal VOC 2007 challenge, ourmethod gives comparable performance to state-of-the-artmethodsusing only a small fraction of the features, reducing the computingtime considerably.

SYSTEM REQUIREMENTS:

HARDWARE REQUIREMENTS:

  • System : Pentium Dual Core.
  • Hard Disk : 120 GB.
  • Monitor : 15’’LED
  • Input Devices : Keyboard, Mouse
  • Ram :1 GB

SOFTWARE REQUIREMENTS:

  • Operating system : Windows 7.
  • Coding Language :
  • Tool : MATLAB R2013A

REFERENCE:

Julian Stöttinger, Allan Hanbury, Nicu Sebe, Senior Member, IEEE, and Theo Gevers, Member, IEEE, “Sparse Color Interest Points for ImageRetrieval and Object Categorization”, IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 21, NO. 5, MAY 2012.

Sharpness Enhancement of Stereo Images Using Binocular Just-Noticeable Difference

Sharpness Enhancement of Stereo Images Using Binocular Just-Noticeable Difference

ABSTRACT:

In this paper, we propose a new sharpness enhancementalgorithm for stereo images. Although the stereo image andits applications are becoming increasingly prevalent, there hasbeen very limited research on specialized image enhancementsolutions for stereo images. Recently, a binocular just-noticeable-difference (BJND) model that describes the sensitivity of thehuman visual system to luminance changes in stereo images hasbeen presented. We introduce a novel application of the BJNDmodel for the sharpness enhancement of stereo images. To thisend, an overenhancement problem in the sharpness enhancementof stereo images is newly addressed, and an efficient solution forreducing the overenhancement is proposed. The solution is foundwithin an optimization framework with additional constraintterms to suppress the unnecessary increase in luminance values.In addition, the reliability of the BJND model is taken into accountby estimating the accuracy of stereo matching. Experimentalresults demonstrate that the proposed algorithm can providesharpness-enhanced stereo images without producing excessivedistortion.

SYSTEM REQUIREMENTS:

HARDWARE REQUIREMENTS:

  • System : Pentium Dual Core.
  • Hard Disk : 120 GB.
  • Monitor : 15’’LED
  • Input Devices : Keyboard, Mouse
  • Ram : 1 GB

SOFTWARE REQUIREMENTS:

  • Operating system : Windows 7.
  • Coding Language :
  • Tool : MATLAB R2013A

REFERENCE:

Seung-Won Jung, Jae-Yun Jeong, and Sung-Jea Ko, Senior Member, IEEE, “Sharpness Enhancement of Stereo Images UsingBinocular Just-Noticeable Difference”, IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 21, NO. 3, MARCH 2012.

Semi-supervised Biased Maximum Margin Analysis for Interactive Image Retrieval

Semi-supervised Biased Maximum Margin Analysis for Interactive Image Retrieval

ABSTRACT:

With many potential practical applications, content-based image retrieval (CBIR) has attracted substantial attention during the past few years. A variety of relevance feedback (RF) schemes have been developed as a powerful tool to bridge the semantic gap between low-level visual features and high-level semantic concepts, and thus to improve the performance of CBIR systems. Among various RF approaches, support-vector-machine (SVM)-based RF is one of the most popular techniques in CBIR. Despite the success, directly using SVM as an RF scheme has two main drawbacks. First, it treats the positive and negative feedbacks equally, which is not appropriate since the two groups of training feedbacks have distinct properties. Second, most of the SVM-based RF techniques do not take into account the unlabeled samples, although they are very helpful in constructing a good classifier. To explore solutions to overcome these two drawbacks, in this paper, we propose a biased maximum margin analysis (BMMA) and a semisupervised BMMA (SemiBMMA) for integrating the distinct properties of feedbacks and utilizing the information of unlabeled samples for SVM-based RF schemes. The BMMA differentiates positive feedbacks from negative ones based on local analysis, whereas the SemiBMMA can effectively integrate information of unlabeled samples by introducing a Laplacian regularizer to the BMMA. We formally formulate this problem into a general subspace learning task and then propose an automatic approach of determining the dimensionality of the embedded subspace for RF. Extensive experiments on a large real-world image database demonstrate that the proposed scheme combined with the SVM RF can significantly improve the performance of CBIR systems.

PROJECT OUTPUT VIDEO: (Click the below link to see the project output video):

SYSTEM ARCHITECTURE:

EXISTING SYSTEM:

A variety of relevance feedback (RF) schemes have been developed as a powerful tool to bridge the semantic gap between low-level visual features and high-level semantic concepts, and thus to improve the performance of CBIR systems. Among various RF approaches, support-vector-machine (SVM)-based RF is one of the most popular techniques in CBIR.

DISADVANTAGES OF EXISTING SYSTEM:

Despite the success, directly using SVM as an RF scheme has two main drawbacks. First, it treats the positive and negative feedbacks equally, which is not appropriate since the two groups of training feedbacks have distinct properties. Second, most of the SVM-based RF techniques do not take into account the unlabeled samples, although they are very helpful in constructing a good classifier.

The low-level features captured from the images may not accurately characterize the high-level semantic concepts

PROPOSED SYSTEM:

The proposed scheme is mainly based on the following:

1) The effectiveness of treating positive examples and negative examples unequally

2) The significance of the optimal subspace or feature subset in interactive CBIR;

3) The success of graph embedding in characterizing intrinsic geometric properties of the data set in high-dimensional space

4) The convenience of the graph-embedding framework in constructing semi-supervised learning techniques.

ADVANTAGES OF PROPOSED SYSTEM:

To explore solutions to these two aforementioned problems in the current technology, we propose a biased maximum margin analysis (BMMA)and a semisupervised BMMA(SemiBMMA) for the traditional SVM RF schemes, based on the graph-embedding framework With the incorporation of BMMA, labeled positive feedbacks are mapped as close as possible, whereas labeled negative feedbacks are separated from labeled positive feedbacks by a maximum margin in the reduced subspace.

The traditional SVM combined with BMMA can better model the RF process and reduce the performance degradation caused by distinct properties of the two groups of feedbacks. The SemiBMMA can incorporate the information of unlabeled samples into the RF and effectively alleviate the over fitting problem caused by the small size of labeled training samples.

To show the effectiveness of the proposed scheme combined with the SVM RF, we will compare it with the traditional SVM RF and some other relevant existing techniques for RF on a real-world image collection.

Experimental results demonstrate that the proposed scheme can significantly improve the performance of the SVMRF for image retrieval.

MODULES:

  • Training and Indexing Module
  • Graph-Embedding Framework
  • Features Extraction Based on Different Methods
  • Visualization of the Retrieval Results
  • Experiments on a Large-Scale Image Database:
  • Experiments on a Small-Scale Image Database

MODULES DESCRIPTION:

Training and Indexing Module

In this module, we index and train the system. Indexing the whole set of images is done for making the search efficient and time consuming. If we don’t index the system, then it takes more time as it searches the whole disk space..Indexing is done using an implementation of the Document Builder Interface. A simple approach is to use the Document Builder Factory, which creates Document Builder instances for all available features as well as popular combinations of features (e.g. all JPEG features or all avail-able features).  In a content based image retrieval system, target images are sorted by feature similarities with respect to the query (CBIR).In this indexing, we propose to classification of feature set obtained from the CBIR.First, it randomly selects k of the objects, each of which initially represents a cluster mean or center. For each of the remaining objects, an object is assigned to the cluster to which it is the most similar, based on the distance between the object and the cluster mean. It then computes the new mean for each cluster.

Graph-Embedding Framework

In order to describe our proposed approach clearly, we first review the graph-embedding framework Generally, for a classification problem, the sample set can be represented as matrix , where indicates the total number of the samples and is the feature dimensionality. Let be an undirected similarity graph, which is called an intrinsic graph, with vertices set and similarity matrix. The similarity matrix is real and symmetric, and measures the similarity between a pair of vertices; can be formed using various similarity criteria. The corresponding diagonal matrix and the Laplacian matrix of graph can G. Graph embedding of graph is defined as an algorithm to determine the low-dimensional vector representations of the vertex set, where is lower than for dimensionality. The column vector is the embedding vector for vertex, which preserves the similarities between pairs of vertices in the original high-dimensional space. Then, in order to characterize the difference between pairs of vertices in the original high-dimensional space, a penalty graph is also defined, where vertices are the same as those of, but the edge weight matrix corresponds to the similarity characteristics that are to be suppressed in the low-dimensional feature space. For a dimensionality reduction problem, direct graph embedding requires an intrinsic graph, whereas a penalty graph is not a necessary input.

Features Extraction Based on Different Methods

Six experiments are conducted for comparing the BMMA with the traditional LDA, the BDA method, and a graph-embedding approach, i.e., MFA, in finding the most discriminative directions. We plot the directions that correspond to the largest Eigen value of the decomposed matrices for LDA, BDA, MFA, and BMMA, respectively. From these examples, we can clearly notice that LDA can find the best discriminative direction when the data from each class are distributed as Gaussian with similar covariance matrices Biased toward the positive samples, BDA can find the direction that the positive samples are well separated with the negative samples when the positive samples have a Gaussian distribution, but it may also confuse when the distribution of the positive samples is more complicated. Biased toward positive samples, the BMMA method can find the most discriminative direction for all the six experiments based on local analysis, since it does not make any assumptions on the distributions of the positive and negative samples. It should be noted that BMMA is a linear method, and therefore, we only gave the comparison results of the aforementioned linear methods.

Visualization of the Retrieval Results

In the previous subsections, we have presented some statistically quantitative results of the proposed scheme. Here, we show the visualization of retrieval results.

In experiments, we randomly select some images (e.g., bobsled, cloud, cat, and car) as the queries and perform the RF process based on the ground truth. For each query image, we do four RF iterations. For each RF iteration, we randomly select some relevant and irrelevant images as positive and negative feedbacks from the first screen, which contains 20 images in total. The number of selected positive and negative feedbacks is about 4, respectively. We choose them according to the ground truth of the images, i.e., whether they share the same concept with the query image or not. The query images are given as the first image of each row. We show the top one to ten images of initial results without feedback and Semi BMMA SVM after four feedback iterations, respectively, and incorrect results are highlighted by green boxes. From the results, we can notice that our proposed scheme can significantly improve the performance of the system. For the first, second, and fourth query images, our system produces ten relevant images out of the top ten retrieved images. For the third query image, our system produces nine relevant images out of the top ten retrieved images. Therefore, Semi BMMA SVM can effectively detect the homogeneous concept shared by the positive samples and hence improve the performance of the retrieval system.

Experiments on a Large-Scale Image Database:

Here, we evaluate the performance of the proposed scheme on a real-world image database. We use precision–scope curve, precision rate, and standard deviation to evaluate the effectiveness of the image retrieval algorithms. The scope is specified by number of top-ranked images presented to the user. The precision is the major evaluation criterion, which evaluates the effectiveness of the algorithms. The precision–scope curve describes the precision with various scopes and can give the overall performance evaluation of the approaches. The precision rate is the ratio of the number of relevant images retrieved to the top retrieved images, which emphasizes the precision at a particular value of scope. Standard deviation describes the stability of different algorithms. Therefore, the precision evaluates the effectiveness of a given algorithm, and the corresponding standard deviation evaluates the robustness of the algorithm. We designed a slightly different feedback scheme to model the real world retrieval process. In a real image retrieval system, a query image is usually not in the image database. To simulate such an environment, we use fivefold cross validation to evaluate the algorithms. More precisely, we divide the whole image database into five subsets of equal size. Thus, there are 20% images per category in each subset. At each run of cross validation, one subset is selected as the query set, and the other four subsets are used as the database for retrieval. Then, 400 query samples are randomly selected from the query subset, and the RF is automatically implemented by the system. For each query image, the system retrieves and ranks the images in the database, and nine RF iterations are automatically executed.

Experiments on a Small-Scale Image Database

In order to show how efficient the proposed BMMA combined with SVM is in dealing with the asymmetric properties of feedback samples, the first evaluation experiment is executed on a small-scale database, which includes 3899 images with 30 different categories. We use all 3899 images in 30 categories as queries. Some example categories used in experiments. To avoid the potential problem caused by the asymmetric amount of positive and negative feedbacks, we selected an equal number of positive and negative feedbacks here. In practice, the first five query-relevant images and first five irrelevant images in the top 20 retrieved images in the previous iterations were automatically selected as positive and negative feedbacks, respectively.

HARDWARE REQUIREMENTS

  • PROCESSOR :  PENTIUM 4 CPU 2.40GHZ
  • RAM :   128 MB
  • HARD DISK :    40 GB
  • KEYBOARD    :    STANDARD
  • MONITOR     :    15”

SOFTWARE REQUIREMENTS

  • FRONT END :     MATLAB
  • TOOL :  MATLAB TOOLBOX
  • OPERATING SYSTEM :   WINDOWS XP/7
  • DOCUMENTATION :   MS-OFFICE 2007

REFERENCE:

Lining Zhang, Student Member, IEEE, LipoWang, Senior Member, IEEE, and Weisi Lin, Senior Member, IEEE, “Semisupervised Biased Maximum Margin Analysis for Interactive Image Retrieval”, IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 21, NO. 4, APRIL 2012.

A Privacy-Preserving Location Monitoring System for Wireless Sensor Networks

A Privacy-Preserving Location Monitoring System forWireless Sensor Networks

ABSTRACT:-

Monitoring personal locations with a potentially untrusted server poses privacy threats to the monitored individuals. Tothis end, we propose a privacy-preserving location monitoring system for wireless sensor networks. In our system, we design two innetworklocation anonymization algorithms, namely, resource- and quality-aware algorithms, that aim to enable the system to providehigh quality location monitoring services for system users, while preserving personal location privacy. Both algorithms rely on the wellestablished k-anonymity privacy concept, that is, a person is indistinguishable among k persons, to enable trusted sensor nodes to

provide the aggregate location information of monitored persons for our system. Each aggregate location is in a form of a monitoredarea A along with the number of monitored persons residing in A, where A contains at least k persons. The resource-aware algorithmaims to minimize communication and computational cost, while the quality-aware algorithm aims to maximize the accuracy of theaggregate locations by minimizing their monitored areas. To utilize the aggregate location information to provide location monitoringservices, we use a spatial histogram approach that estimates the distribution of the monitored persons based on the gathered aggregatelocation information. Then the estimated distribution is used to provide location monitoring services through answering range queries.

We evaluate our system through simulated experiments. The results show that our system provides high quality location monitoringservices for system users and guarantees the location privacy of the monitored persons.

PROJECT OUTPUT VIDEO: (Click the below link to see the project output video):

SYSTEM ARCHITECTURE

ALGORITHM

The Resource-Aware Algorithm

EXISTING SYSTEM

Existing locationmonitoring systems. In an identity-sensor location monitoring

System, since each sensor node reports the exactlocation information of each 0monitored object to theserver, the adversary can pinpoint each object’s exact location.On the other hand, in a counting-sensor locationmonitoring system, each sensor node reports the numberof objects in its sensing area to the server. The adversarycan map the monitored areas of the sensor nodes to thesystem layout. If the object count of a monitored area isvery small or equal to one,

PROPOSED SYSTEM

This paper proposes a privacy-preserving locationmonitoring system for wireless sensor networks to providemonitoring services. Our system relies on the wellestablished k-anonymity privacy concept, which requireseach person is indistinguishable among k persons. In oursystem, each sensor node blurs its sensing area into acloaked area, in which at least k persons are residing. Eachsensor node reports only aggregate location information,

We proposetwo in-network aggregate location anonymization algorithms, namely, resource- and quality-aware algorithms.Both algorithms require the sensor nodes to collaboratewith each other to blur their sensing areas into cloakedareas, such that each cloaked area contains at least kpersons to constitute a k-anonymous cloaked area. Theresource-aware algorithm aims to minimize communication

and computational cost, while the quality-awarealgorithm aims to minimize the size of the cloaked areas,in order to maximize the accuracy of the aggregatelocations reported to the server.

MODULES

  1. WSN Location Monitoring Module

The location monitoring system using identity sensors,the sensor nodes report the exact location information ofthe monitored persons to the server; thus using identitysensors immediately poses a major privacy breach. To tackle such a privacy breach, the concept of aggregatelocation information, that is, a collection of location datarelating to a group or category of persons from whichindividual identities have been removed , has beensuggested as an effective approach to preserve locationprivacy . Although the counting sensors by natureprovide aggregate location information, they wouldalso pose privacy breaches.

  1. Aggregate locations Module

We design two in-network location anonymization algorithms,namely, resource- and quality-aware algorithms that preserve personal location privacy, while enablingthe system to provide location monitoring services. Bothalgorithms rely on the well established k-anonymity privacyconcept that requires a person is indistinguishableamong k persons. In our system, sensor nodes executeour location anonymization algorithms to provide k-anonymous aggregate locations, in which each aggregatelocation is a cloaked area A

  1. Mapped Location monitoring Module

Sensor nodes.

Each sensor node is responsible for determining the number of objects in its sensing area, blurring its sensing area into a cloaked area A, which includes at least k objects, and reporting A with the number of objects located in A as aggregate location information to the server. We do not have any assumption about the network topology, as our system only requires a communication path from each sensor node to the server through a distributed tree . Each sensor node is also aware of its location and sensing area.

Server.

The server is responsible for collecting the aggregatelocations reported from the sensor nodes, usinga spatial histogram to estimate the distribution of themonitored objects, and answering range queries basedon the estimated object distribution. Furthermore, theadministrator can change the anonymized level k of thesystem at anytime by disseminating a message with anew value of k to all the sensor nodes.

System users.

Authenticated administrators and userscan issue range queries to our system through either theserver or the sensor nodes, as depicted in Above System Architecture figure. Theserver uses the spatial histogram to answer their queries.

  1. Minimum bounding rectangle (MBR)

We find the minimum bounding rectangle (MBR) of the sensing area of A. It is important to note that the sensing area can be in any polygon or irregular shape.

SOFTWARE REQUIREMENTS:

HARDWARE REQUIREMENT:

  • Minimum 1.1 GHz PROCESSOR should be on the computer.
  • 128 MB RAM.
  • 20 GB HDD.
  • 44 MB FDD.
  • 52x CD-ROM Drive.
  • MONITORS at 800×600 minimum resolution at 256 colors minimum.
  • I/O, One or two button mouse and standard 101-key keyboard.

SOFTWARE REQUIREMENT:

  • Operating System : Windows 95/98/2000/NT4.0.
  • Technology                    :  JAVA, JFC(Swing)
  • Development IDE           :  Eclipse 3.x

 

Data Leakage Detection

DATA LEAKAGE DETECTION

ABSTRACT:

A data distributor has given sensitive data to a set of supposedly trusted agents (third parties). Some of the data is leaked and found in an unauthorized place (e.g., on the web or somebody’s laptop). The distributor must assess the likelihood that the leaked data came from one or more agents, as opposed to having been independently gathered by other means. We propose data allocation strategies (across the agents) that improve the probability of identifying leakages. These methods do not rely on alterations of the released data (e.g., watermarks). In some cases we can also inject “realistic but fake” data records to further improve our chances of detecting leakage and identifying the guilty party.

PROJECT OUTPUT VIDEO: (Click the below link to see the project output video):

EXISTING SYSTEM:

  • Traditionally, leakage detection is handled by watermarking, e.g., a unique code is embedded in each distributed copy.
  • If that copy is later discovered in the hands of an unauthorized party, the leaker can be identified.
  • Disadvantages of Existing Systems:
  • Watermarks can be very useful in some cases, but again, involve some modification of the original data. Furthermore, watermarks can sometimes be destroyed if the data recipient is malicious. g. A hospital may give patient records to researchers who will devise new treatments.
  • Similarly, a company may have partnerships with other companies that require sharing customer data. Another enterprise may outsource its data processing, so data must be given to various other companies. We call the owner of the data the distributor and the supposedly trusted third parties the agents.

PROPOSED SYSTEM:

  • Our goal is to detect when the distributor’s sensitive data has been leaked by agents, and if possible to identify the agent that leaked the data.
  • Perturbation is a very useful technique where the data is modified and made “less sensitive” before being handed to agents.
  • We develop unobtrusive techniques for detecting leakage of a set of objects or records.
  • We develop a model for assessing the “guilt” of agents.
  • We also present algorithms for distributing objects to agents, in a way that improves our chances of identifying a leaker.
  • Finally, we also consider the option of adding “fake” objects to the distributed set. Such objects do not correspond to real entities but appear realistic to the agents.
  • In a sense, the fake objects acts as a type of watermark for the entire set, without modifying any individual members. If it turns out an agent was given one or more fake objects that were leaked, then the distributor can be more confident that agent was guilty.

Problem Setup and Notation:

A distributor owns a set T={t1,…,tm}of valuable data objects. The distributor wants to share some of the objects with a set of agents U1,U2,…Un, but does not wish the objects be leaked to other third parties. The objects in T could be of any type and size, e.g., they could be tuples in a relation, or relations in a database. An agent Ui receives a subset of objects, determined either by a sample request or an explicit request:

  1. Sample request
  2. Explicit request

Guilt Model Analysis:

Our model parameters interact and to check if the interactions match our intuition, in this section we study two simple scenarios as Impact of Probability p and Impact of Overlap between Ri and S. In each scenario we have a target that has obtained all the distributor’s objects, i.e., T = S.

MODULES:

  1. Data Allocation Module:

The main focus of our project is the data allocation problem as how can the distributor “intelligently” give data to agents in order to improve the chances of detecting a guilty agent.

  1. Fake Object Module:

Fake objects are objects generated by the distributor in order to increase the chances of detecting agents that leak data. The distributor may be able to add fake objects to the distributed data in order to improve his effectiveness in detecting guilty agents. Our use of fake objects is inspired by the use of “trace” records in mailing lists.

  1. Optimization Module:

The Optimization Module is the distributor’s data allocation to agents has one constraint and one objective. The distributor’s constraint is to satisfy agents’ requests, by providing them with the number of objects they request or with all available objects that satisfy their conditions. His objective is to be able to detect an agent who leaks any portion of his data.

  1. Data Distributor:

A data distributor has given sensitive data to a set of supposedly trusted agents (third parties). Some of the data is leaked and found in an unauthorized place (e.g., on the web or somebody’s laptop). The distributor must assess the likelihood that the leaked data came from one or more agents, as opposed to having been independently gathered by other means.

Hardware Required:

  • System : Pentium IV 2.4 GHz
  • Hard Disk : 40 GB
  • Floppy Drive : 44 MB
  • Monitor : 15 VGA colour
  • Mouse :Logitech
  • Keyboard : 110 keys enhanced.
  • RAM : 256 MB

Software Required:

  • O/S :         Windows XP.
  • Front End : JAVA/JSP
  • Data Base : MYSQL

REFERENCE:

Panagiotis Papadimitriou, and Hector Garcia-Molina, “Data Leakage Detection”, IEEE Transactions on Knowledge and Data Engineering, Vol. 23, NO.1, January 2011.

Supporting Efficient and Scalable Multicasting Over Mobile Ad Hoc Networks

Supporting Efficient and Scalable Multicasting Over Mobile Ad Hoc Networks

Abstract:-

Group communications are important in Mobile Ad hoc Networks (MANET). Multicast is an efficient method for implementing group communications. However, it is challenging to implement efficient and scalable multicast in MANET due to the difficulty in group membership management and multicast packet forwarding over a dynamic topology. We propose a novel Efficient Geographic Multicast Protocol (EGMP). EGMP uses a virtual-zone-based structure to implement scalable and efficient group membership management. A network-wide zone-based bi-directional tree is constructed to achieve more efficient membership management and multicast delivery. The position information is used to guide the zone structure building, multicast tree construction and multicast packet forwarding, which efficiently reduces the overhead for route searching and tree structure maintenance. Several strategies have been proposed to further improve the efficiency of the protocol, for example, introducing the concept of zone depth for building an optimal tree structure and integrating the location search of group members with the hierarchical group membership management. Finally, we design a scheme to handle empty zone problem faced by most routing protocols using a zone structure. The scalability and the efficiency of EGMP are evaluated through simulations and quantitative analysis. Our simulation results demonstrate that EGMP has high packet delivery ratio, and low control overhead and multicast group joining delay under all test scenarios, and is scalable to both group size and network size. Compared to Scalable Position-Based Multicast (SPBM), EGMP has significantly lower control overhead, data transmission overhead, and multicast group joining delay.

PROJECT OUTPUT VIDEO: (Click the below link to see the project output video):

Existing System:-

The existing geographic routing protocols generally assume mobile nodes are aware of their own positions through certain positioning system (e.g., GPS), and a source can obtain the destination position through some type of location service. In, an intermediate node makes its forwarding decisions based on the destination position inserted in the packet header by the source and the positions of its one-hop neighbors learned from the periodic beaconing of the neighbors. By default, the packets are greedily forwarded to the neighbor that allows for the greatest geographic progress to the destination. When no such a neighbor exists, perimeter forwarding is used to recover from the local void, where a packet traverses the face of the planarized local topology sub graph by applying the right-hand rule until the greedy forwarding can be resumed. 

Proposed System:-

ODMRP are proposed to enhance the robustness with the use of redundant paths between the source and the destination pair’s scalability due to the overhead incurred for route searching, group membership management, and creation and maintenance of the tree/mesh structure over the dynamic MANET.

For MANET uni-cast routing, geographic routing protocols have been proposed in recent years for more scalable and robust packet transmissions we proposed an efficient and robust geographic multicast protocol for MANET. In this paper, we further introduce zone-supported geographic forwarding to reduce the routing failure, and provide mechanism to handle zone partitioning. In addition, we introduce a path optimization process to handle multiple paths, and provide a detailed cost analysis to demonstrate the scalability of the proposed routing scheme.

MODULES:

  1. Efficient Geographic Multicast Protocol
  2. Multicast Tree Construction
  3. Multicast group join
  4. Packet sending from the source
  5. Multicast data forwarding
  6. Multicast Route Maintenance and Optimization

MODULE DESCRIPTION:-

  1. Efficient Geographic Multicast Protocol

 EGMP supports scalable and reliable membership management and multicast forwarding through a two-tier virtual zone- based structure. At the lower layer, in reference to a pre-determined virtual origin, the nodes in the network self-organize themselves into a set of zones, and a leader is elected in a zone to manage the local group membership. At the upper layer, the leader serves as a representative for its zone to join or leave a multicast group as required. As a result, a network-wide zone-based multicast tree is built. For efficient and reliable management and transmissions, location information will be integrated with the design and used to guide the zone construction, group membership management, multicast tree construction and maintenance, and packet forwarding.

  1. Multicast Tree Construction 

We present the multicast tree creation and maintenance schemes. In EGMP, instead of connecting each group member directly to the tree, the tree is formed in the granularity of zone with the guidance of location information, which significantly reduces the tree management overhead. With a destination location, a control message can be transmitted immediately without incurring a high overhead and delay to find the path first, which enables quick group joining and leaving.

  1. Multicast group join 

When a node M wants to join the multicast group G, if it is not a leader node, it sends a JOIN REQ(M; PosM; G; fMoldg) message to its zLdr, carrying its address, position, and group to join. The address of the old group leader Mold is an option used when there is a leader handoff and a new leader sends an updated JOIN REQ message to its upstream zone. If M did not receive the NEW SESSION message or it just joined the network,

  1. Packet sending from the source 

After the multicast tree is constructed, all the sources of the group could send packets to the tree and the packets will be forwarded along the tree. In most tree-based multicast protocols, a data source needs to send the packets initially to the root of the tree. If this scheme is used and node 5 in Fig. 1 is a source, node 5 needs to uni-cast the packets initially to root zone (2, 2). The sending of packets to the root would introduce extra delay especially when a source is far away from the root. Instead, EGMP assumes a bi-directional tree- based forwarding strategy, with which the multicast packets can flow not only from an upstream node/zone down to its downstream nodes/zones, but also from a downstream node/zone up to its upstream node/zone.

  1. Multicast data forwarding

Maintain the multicast table, and the member zones normally cannot be reached within one hop from the source. When a node N has a multicast

Packet to forward to a list of destinations (D1; D2; D3; :), it decides the next hop node towards each destination (for a zone, its center is used) using the geographic forwarding strategy. After deciding the next hop nodes, N inserts the list of next hop nodes and the destinations associated with each next hop node in the packet header. An example list is (N1: D1; D3; N2: D2; :), where N1 is the next hop node for the destinations D1 and D3, and N2 is the next hop node for D2. Then N broadcasts the packet promiscuously (for reliability and efficiency). Upon receiving the packet, a neighbor node will keep the packet if it is one of the next hop nodes or destinations, and drop the packet otherwise. When the node is associated with some downstream destinations, it will continue forwarding packets similarly as done by node N.

  1. Multicast Route Maintenance and Optimization 

In the zone structure, due to the movement of nodes between different zones, some zones may become empty. It is critical to handle the empty zone problem in a zone-based protocol. Compared to managing the connections of individual nodes, however, there is a much lower rate of zone membership change and hence a much lower overhead in maintaining the zone-based tree.

When a member node moves to a new zone, it must rejoin the multicast tree through the new leader. When a leader is moving away from its current zone, it must handover its multicast table to the new leader in the zone, so that all the downstream zones and nodes will remain connected to the multicast tree.

System Requirements:

     

Hardware Requirement:

  • Minimum 1.1 GHz PROCESSOR should be on the computer.
  • 128 MB RAM.
  • 20 GB HDD.
  • 44 MB FDD.
  • 52x CD-ROM Drive.
  • MONITORS at 800×600 minimum resolution at 256 colors minimum.
  • I/O, One or two button mouse and standard 101-key keyboard.

 Software Requirement:

  • Operating System :  Windows 95/98/2000/XP
  • Technology                            :  JAVA, JFC(Swing)
  • Development IDE           :  Eclipse 3.x

REFERENCE:

X.Xiang, X.Wang, and Y. Yang, “Supporting Efficient and Scalable Multicasting over Mobile Ad Hoc Networks”, IEEE Transactions on Mobile Computing, Vol. 10, No.4, April 2011.

ProgME: Towards Programmable Network Measurement

ProgME: Towards Programmable Network Measurement 

ABSTRACT:

We present ProgME, a Programmable MEasurement architecture based on a novel concept of flowset – arbitrary set of flows defined according to application requirements and/or traffic conditions. Through a simple flowset composition language, ProgME can incorporate application requirements, adapt itself to circumvent the challenges on scalability posed by the large number of flows, and achieve a better application-perceived accuracy. ProgME can analyze and adapt to traffic statistics in real-time. Using sequential hypothesis test, ProgME can achieve fast and scalable heavy hitter identification.

PROJECT OUTPUT VIDEO: (Click the below link to see the project output video):

Existing System:

Traffic measurements provide critical input for a wide range of network management applications, including traffic engineering, accounting, and security analysis. Existing measurement tools collect traffic statistics based on some predetermined, inflexible concept of “flows”. They do not have sufficient built-in intelligence to understand the application requirements or adapt to the traffic conditions. Consequently, they have limited scalability with respect to the number of flows and the heterogeneity of monitoring applications. 

Proposed System:

We present a Programmable MEasurement architecture (ProgME) that can adapt to application requirements and traffic conditions in real time. Below figure shows the major components of ProgME. Our first proposal is to use a versatile definition of flowset – arbitrary set of flows – as the base of traffic statistics collection. In other words, ProgME keeps one counter per flowset. Compared to per-flow traffic statistics, per-flowset statistics enables one to achieve multiple resolutions within a traffic profile. Since flowsets can be defined arbitrarily, they do not necessarily map to the same number of unique flows or traffic volume. Therefore, one can track higher resolution statistics to maintain the desired accuracy for a sub-population of network traffic, while collecting coarse-grained aggregate statistics for the remaining traffic (e.g., through a flowset that catches uninteresting traffic) to reduce total number of counters required. Furthermore, since a flowset can contain arbitrary set of flows, one can construct flowsets that directly reflect the interest of management applications.

Modules:

  1. Flow Set
  2. Collect and Report Statistics
  3. Scalable Flowset-Based Query Answering (FQAE)
  4. Accuracy of FQAE 

Modules Description: 

  1. Flow Set 

Definition of flowset – arbitrary set of flows – as the base of traffic statistics collection. In other words, ProgME keeps one counter per flowset. Compared to per-flow traffic statistics, per-flowset statistics enables one to achieve multiple resolutions within a traffic profile. Since flowsets can be defined arbitrarily, they do not necessarily map to the same number of unique flows or traffic volume. Therefore, one can track higher resolution statistics to maintain the desired accuracy for a sub-population of network traffic, while collecting coarse-grained aggregate statistics for the remaining traffic (e.g., through a flowset that catches uninteresting traffic) to reduce total number of counters required. Furthermore, since a flowset can contain arbitrary set of flows, one can construct flowsets that directly reflect the interest of management applications.

  1. Collect and Report Statistics:

During the measurement process, FQAE performs trafficaware optimization by sorting the order of candidates in the table of matching candidates based on the number of packets observed earlier (TrafficSort). Note that this seemingly simple optimization is possible only because FQAE make flowsets fully disjoint. If flowsets have non-empty intersections, finding the optimal order is NP-complete, and one will have to resolve to heuristics, as some have attempted in the context of packet  Filtering .

  1. Scalable Flowset-Based Query Answering (FQAE):

We propose a scalable Flowset-based Query Answering Engine (FQAE) to support arbitrary user queries. Used in conjunction with sampling,

FQAE can achieve the same accuracy for any given set of queries compared to an ideal flow-based measurement approach, while achieving orders of magnitude cost reduction in terms of memory requirements.

  1. Accuracy of FQAE:

The accuracy of measurement results is of paramount concern for every management application. Existing flow-based measurement tools use average per-flow error as the primary measure of accuracy. If there were no memory limitation and statistics could be maintained for every flow, per-flow statistics could achieve high per-query accuracy under any traffic condition. FQAE achieves the same effect by counting for each query directly.

System Configuration:-

H/W System Configuration:-

  • Processor                                          –    Pentium –III
  • Speed                                      –    1.1 Ghz
  • RAM                                       –    256  MB(min)
  • Hard Disk                                –   20 GB
  • Floppy Drive                           –    1.44 MB
  • Key Board                               –    Standard Windows Keyboard
  • Mouse                                     –    Two or Three Button Mouse
  • Monitor                                   –    SVGA

 S/W System Configuration:-

  • Operating System         :Windows95/98/2000/XP
  • Application Server         :   0/6.X
  • Front End :   HTML, Java, Jsp                            :
  • Server side Script :   Java Server Pages.
  • Database :   Ms-Access

REFERENCE:

Lihua Yuan, Chen-Nee Chuah, and Prasant Mohapatra, “ProgME: Towards Programmable Network Measurement”, IEEE/ACM Transactions on Networking, Vol. 19, No.1, February 2011.

Delay Analysis and Optimality of Scheduling Policies for Multi-Hop Wireless Networks

Delay Analysis and Optimality of Scheduling Policies for Multi-Hop Wireless Networks

Abstract: 

We analyze the delay performance of a multi-hop wireless network in which the routes between source-destination pairs are fixed. We develop a new queue grouping technique to handle the complex correlations of the service process resulting from the multi-hop nature of the flows and their mutual sharing of the wireless medium. A general set based interference model is assumed that imposes constraints on links that can be served simultaneously at any given time. These interference constraints are used to obtain a fundamental lower bound on the delay performance of any scheduling policy for the system. We present a systematic methodology to derive such lower bounds. For a special wireless system, namely the clique, we design a policy that is sample path delay optimal. For the tandem queue network, where the delay optimal policy is known, the expected delay of the optimal policy numerically coincides with the lower bound. The lower bound analysis provides useful insights into the design and analysis of optimal or nearly optimal scheduling policies.

PROJECT OUTPUT VIDEO: (Click the below link to see the project output video):

Existing System: 

A large number of studies on multi-hop wireless networks have been devoted to system stability while maximizing metrics like throughput or utility. These metrics measure the performance of a system over a long time-scale. For a large class of applications such as video or voice over IP, embedded network control and for system design; metrics like delay are of prime importance. The delay performance of wireless networks, however, has largely been an open problem. This problem is notoriously difficult even in the context of wireline networks, primarily because of the complex interactions in the network (e.g., superposition, routing, departure, etc.) that make its analysis amenable only in very special cases like the product form networks. The problem is further exacerbated by the mutual interference inherent in wireless networks which, complicates both the scheduling mechanisms and their analysis. Some novel analytical techniques to compute useful lower bound and delay estimates for wireless networks with singlehop traffic were developed in. However, the analysis is not directly applicable to multi-hop wireless network with multihop flows, due to the difficulty in characterizing the departure process at intermediate links. The metric of interest in this paper is the system-wide average delay of a packet from the source to its corresponding destination. We present a new, systematic methodology to obtain a fundamental lower bound on the average packet delay in the system under any scheduling policy. Furthermore, we re-engineer well known scheduling policies to achieve good delay performance viz-a-viz the lower bound. 

Proposed System:            

We analyze a multi-hop wireless network with multiple source-destination pairs, given routing and traffic information. Each source injects packets in the network, which traverses through the network until it reaches the destination. For example, a multi-hop wireless network with three flows is shown in Fig. 1. The exogenous arrival processes AI (t), AII (t) and AIII (t) correspond to the number of packets injected in the system at time t. A packet is queued at each node in its path where it waits for an opportunity to be transmitted. Since the transmission medium is shared, concurrent transmissions can interfere with each others’ transmissions. The set of links that do not cause interference with each other can be scheduled simultaneously, and we call them activation vectors (matchings). We do not impose any a priori restriction on the set of allowed activation vectors, i.e., they can characterize any combinatorial interference model. For example, in a K-hop interference model, the links scheduled simultaneously are separated by at least K hops. In the example show in Fig. 1, each link has unit capacity; i.e., at most one packet can be transmitted in a slot. For the above example, we assume a 1-hop interference model.

The delay performance of any scheduling policy is primarily limited by the interference, which causes many bottlenecks to be formed in the network. We demonstrated the use of exclusive sets for the purpose of deriving lower bounds on delay for a wireless network with single hop traffic. We further generalize the typical notion of a bottleneck. In our terminology, we define a (K, X)-bottleneck to be a set of links X such that no more than K of them can simultaneously transmit. Figure 1 shows (1, X) bottlenecks for a network under the 1-hop interference model. In this paper, we develop new analytical techniques that focus on the queuing due to the (K, X)-bottlenecks. One of the techniques, which we call the “reduction technique”, simplifies the analysis of the queuing upstream of a (K, X)-bottleneck to the study of a single queue system with K servers as indicated in the figure. Furthermore, our analysis needs only the exogenous inputs to the system and thereby avoids the need to characterize departure processes on intermediate links in the network. For a large class of input traffic, the lower bound on the expected delay can be computed using only the statistics of the exogenous arrival processes and not their sample paths. To obtain a lower bound on the system wide average queuing delay, we analyze queuing in multiple bottlenecks by relaxing the interference constraints in the system. Our relaxation approach is novel and leads to nontrivial lower bounds.

Theorem:

              For a (K,X)-bottleneck in the system, at any time T ≥ 0, the sum of the queue lengths SX in X, under any scheduling policy is no smaller than that of the reduced system, i.e., QX(T) ≤ SX(T). Proof: We prove the above theorem using the principle of mathematical induction. Base Case: The theorem holds true for T = 0, since the system is initially empty. Induction hypothesis: Assume that the theorem holds at a

time T = t, i.e., QX(t) ≤ SX(t).

Induction Step: The following two cases arise.

Case 1: QX(t) ≥ K

QX(t + 1) = QX(t) − K + AX(t)

≤ SX(t) − K + AX(t)

≤ SX(t) − IX(t) + AX(t)

= SX(t + 1).

Case 2: QX(t) < K.

Using Eq. (III.11), we have the following,

QX(t + 1) = AX(t)

≤ SX(t) − IX(t) + AX(t)

= SX(t + 1).

Hence, the theorem is holds for T = t + 1.

Thus by the principle of mathematical induction, the theorem holds for all T.

Modules: 

1) Multi-hop wireless network module

2) Delay performance of wireless networks

3) Back-Pressure Policy

4) Delay Analysis technique module

5) Design of Delay Efficient Policies module 

Modules Description: 

1) Multi-hop wireless network module

Multi-hop wireless network with multiple source-destination pairs, given routing and traffic information. Each source injects packets in the network, which traverses through the network until it reaches the destination.

2) Delay performance of wireless networks 

The delay performance of wireless networks, however, has largely been an open problem. This problem is notoriously difficult even in the context of wireline networks, primarily because of the complex interactions in the network (e.g., superposition, routing, departure, etc.) that make its analysis amenable only in very special cases like the product form networks. The problem is further exacerbated by the mutual interference inherent in wireless networks which, complicates both the scheduling mechanisms and their analysis. Some novel analytical techniques to compute useful lower bound and delay estimates for wireless networks with single hop traffic were developed. However, the analysis is not directly applicable to multi-hop wireless network with multihop flows, due to the difficulty in characterizing the departure process at intermediate links.

3) Back-Pressure Policy

The back-pressure policy may lead to large delays since the backlogs are progressively larger from the destination to the source. The packets are routed only from a longer queue to a shorter queue and certain links may have to remain idle until this condition is met. Hence, it is likely that all the queues upstream of a bottleneck will grow long leading to larger delays. A common observation of the optimal policies for the clique and the tandem network is that increasing the priority of packets which are close to the destination reduces the delay.

4) Delay Analysis technique module

The general research on the delay analysis of scheduling policies has progressed in the following main directions:

  • Heavy traffic regime using fluid models:

                                          Fluid models have typically been used to either establish the stability of the system or to study the workload process in the heavy traffic régime. The maximum-pressure policy (similar to the back-pressure policy) minimizes the workload process for a stochastic processing network in the heavy traffic regime when processor splitting is allowed.

  • Stochastic Bounds using Lyapunov drifts: 

This method is developed and is used to derive upper bounds on the average queue length for these systems. However, these results are order results and provide only a limited characterization of the delay of the system. For example, the maximal matching policies achieve O(1) delay for networks with single-hop traffic when the input load is in the reduced capacity region. This analysis however, has not been extended to the multi-hop traffic case, because of the lack of an analogous Lyapunov function for the back-pressure policy.

  • Large Deviations: Large deviation results for cellular and multi-hop systems with single hop traffic have been to estimate the decay rate of the queue-overflow probability. Similar analysis is much more difficult for the multi-hop wireless network considered here, due to the complex interactions between the arrival, service, and backlog process.

5) Design of Delay Efficient Policies module

A scheduler must satisfy the following properties.

  • Ensure high throughput: This is important because if the scheduling policy does not guarantee high throughput then the delay may become infinite under heavy loading.
  • Allocate resources equitably: The network resources must be shared among the flows so as not to starve some of the flows. Also, non-interfering links in the network have to be scheduled such that certain links are not starved for service. Starvation leads to an increase in the average delay in the system.

The above properties are difficult to achieve; given the dynamics of the network and the lack of apriori information of the packet arrival process. In the light of the previous work we choose to investigate the back-pressure policy with fixed routing. The back-pressure policy has been widely used to develop solutions for a variety of problems in the context of wireless networks and the importance of studying the trade-offs in stability, delay, and complexity of these solutions is now being realized by the research community. This policy tries to maintain the queues corresponding to each flow in decreasing order of size from the source to the destination. This is achieved by using the value of differential backlog (difference of backlogs at the two ends of a link) as the weight for the link and scheduling the matching with the highest weight. As a result, the policy is throughput optimal. Henceforth, we shall refer to this policy as only the back-pressure policy. We first study the delay optimal policy for a clique network.

System Requirements:

Hardware Requirements: 

  • System : Pentium IV 2.4 GHz.
  • Hard Disk : 40 GB.
  • Floppy Drive : 1.44 Mb.
  • Monitor : 15 VGA Colour.
  • Mouse : Logitech.
  • Ram : 512 Mb.

Software Requirements: 

  • Operating system : – Windows XP.
  • Coding Language : -JAVA, Swing, RMI, J2ME(Wireless Toolkit)
  • Tool Used : – Eclipse 3.3

REFERENCE:

Gagan Raj Gupta, Ness B. Shroff, “Delay Analysis and Optimality of Scheduling Policies for Multi-Hop Wireless Networks”, IEEE/ACM Transactions on Networking, Vol. 19, No.1, Feb 2011.

Selfish Overlay Network Creation and Maintenance

Selfish Overlay Network Creation and Maintenance

ABSTRACT:

A foundational issue underlying many overlay network applications ranging from routing to peer-to-peer file sharing is that of the network formation, i.e., folding new arrivals into an existing overlay, and rewiring to cope with changing network conditions. Previous work has considered the problem from two perspectives: devising practical heuristics for the case of cooperative peers and performing game-theoretic analysis for the case of selfish peers. In this paper, we unify the aforementioned thrusts by defining and studying the selfish neighbor selection (SNS) game and its application to overlay routing. At the heart of SNS stands the restriction that peers are allowed up to a certain number of neighbors. This makes SNS substantially different from existing network formation games that impose no bounds on peer degrees. Having bounded degrees has important practical consequences as it permits the creation of overlay structures that require $O(n)$ instead of $O(n^2)$link monitoring overhead. We show that a node’s “best response” wiring strategy amounts to solving a $k$ -median problem on asymmetric distance. Best-response wirings have substantial practical utility as they permit selfish nodes to reap substantial performance benefits when connecting to overlays of nonselfish nodes. A more intricate consequence is that even nonselfish nodes can benefit from the existence of some selfish nodes since the latter, via their local optimizations, create a highly optimized backbone, upon which even simple heuristic wirings yield good performance. To capitalize on the above properties, we design, build, and deploy EGOIST, an SNS-inspired prototype overlay routing system for PlanetLab. We demonstrate that EGOIST outperforms existing heuristic overlays on a variet- – y of performance metrics, including delay, available bandwidth, and node utilization, while it remains competitive with an optimal but unscalable full-mesh overlay.

PROJECT OUTPUT VIDEO: (Click the below link to see the project output video):

ALGORITHM USED:

Dijkstra’s algorithm

Dijkstra’s algorithm solves the single-source shortest-path problem when all edges have non-negative weights. It is a greedy algorithm and similar to Prim’s algorithm. Algorithm starts at the source vertex, s, it grows a tree, T, that ultimately spans all vertices reachable from S. Vertices are added to T in order of distance i.e., first S, then the vertex closest to S, then the next closest, and so on. Following implementation assumes that graph G is represented by adjacency lists.

EXISTING SYSTEM:

In a typical overlay network, a node must select a fixed number (k) of immediate overlay neighbors for routing traffic. Previous work has considered this problem from two perspectives:

 (1) Devising practical heuristics for specific applications in real deployments, such asbootstrapping by choosing the k closest links (e.g., in terms ofTTL or IP prefix distance), or by choosing k random links in aP2P file-sharing system. Notice here that DHTs like Chord solve a different problem. They route queries, not data traffic.The latter is left to a separate subsystem that typicallyopens a direct connection to the target host.

 (2) Providing abstractions of the underlying fundamental neighbor selection problem that are analytically tractable, especially via game theoretic analysis. To date, however, the bulk of the work and main results in this area have centered on strategic games where edges are undirected, access costs are based on hop-counts, and nodes have potentially unbounded degrees. While this existing body of work is extremely helpful for laying a theoretical foundation and for building intuition, it is not clear how or whether the guidance provided by this prior work generalizes to situations of practical interest, in which underlying assumptions in these prior studies are not satisfied. Another aspect not considered in previous work is the consideration of settings in which some or even most players do not play optimally – a setting which we believe to be typical. Interesting questions along these lines include an assessment of the advantage to a player from employing an optimizing strategy, when most other players .Do not, or more broadly, whether employing an optimizing strategy by a relatively small number of players could be enough to achieve global efficiency.

PROPOSED SYSTEM:

In this Paper, Overlay networks  are used for a variety of popular applications including routing , content distribution , peer-to-peer (P2P) file sharing  and streaming , data-center applications , and online multi-player games . A foundational issue underlying many such overlay network applications is that of connectivity management. Connectivity management is called upon when having to wire a newcomer into the existing mesh of nodes (bootstrapping), or when having to rewire the links between overlay nodes to deal with churn and changing network conditions. Connectivity management is particularly challenging for overlay networks because overlays often consist of nodes that are distributed across multiple administrative domains, in which auditing or enforcing global behavior can be difficult or impossible. As such, these nodes may act selfishly and deviate from the default protocol, by utilizing knowledge they have about the network, to maximize the benefit they receive from it. Selfish behavior has been reported in studies relating to selfish (source) routing and free riding in P2P file sharing networks. Selfish behavior also has many implications for connectivity management. In particular, it creates additional incentives for nodes to rewire, not only for operational purposes (bootstrapping and substituting nodes that went offline), but also for seizing opportunities to incrementally maximize the local connection quality to the overlay. While much attention has been paid to the harmful downsides of selfish behavior in different settings , the impact of adopting selfish connectivity management techniques in real

overlay networks has been an open problem.

MODULES:

We start by relaxing and modifying some of the central modeling assumptions of previous work. In that regard, the central aspects of our model are:

  1. Bounded Degree
  2. Directed Edges
  3. Non-uniform preference vectors
  4. Selfish Neighbor Selection

MODULE DESCRIPTION:

Bounded Degree:

Most protocols used for implementing overlay routing or content sharing impose hard constraints on the maximum number of overlay neighbors. For example, in popular versions of BitTorrent a client may select up to 50 nodes from a neighbors’ list provided by the Tracker of a particular torrent file. In overlay routing systems, the number of immediate nodes has to be kept small so as to reduce the monitoring and reporting overhead imposed by the link-state routing protocol implemented at the overlay layer. Hard constraints on the number of first hop neighbors are also imposed in most P2P systems to address scalability issues, up-link fragmentation, and CPU consumption due to contention . Motivated by these systems, we explicitly model such hard constraints on node degrees. Notice that in the prior studies cited above, node degrees were implicitlybounded (as opposed to explicitly constrained) by virtue of the trade-off between the additional cost of setting up more links and the decreased communication distance achieved through the addition of new links. We also note that some of these earlier network creation games were proposed in the context of physical communication networks. In such networks, the cost of acquiring a link is instrumental to the design and operation of a critical infrastructure. Such concerns do not apply in the case of overlay networks such as those we consider in this paper.

Directed Edges:

Another important consideration in the settings we envision for our work relates to link directionality. Prior models have generally assumed bi-directional (undirected) links. This is an acceptable assumption that fits naturally with the unbounded node degree assumption for models that target physical telecommunication networks because actual wire-line communication links are almost exclusively bidirectional. In overlay settings we consider, this assumption needs to be relaxed since the fact that node v forwards traffic or requests to node u does not mean that node u may also forward traffic or requests to v. Undirected links are created by the establishment of two directed links.

Non-uniform preference vectors:

In our model, we supply each node with a vector that captures its local preference for all other destinations. In overlay routing such preference may capture the percentage of locally generated traffic that a node routes to each destination, and then the aggregation of all preference vectors would amount to a origin/destination traffic matrix. In P2P overlays such preference may amount to speculations from the local node about the quality of, or interest in, the content held by other nodes. Other considerations may also include subjective criteria such as the perceived capacity of the node, its geographic location, or its availability profile.

Selfish Neighbor Selection:

In a typical overlay network, a node must select a fixed number (k) of immediate overlay neighbors for routing traffic. Previous work has considered this problem from two perspectives:

 (1) Devising practical heuristics for specific applications in real deployments, such asbootstrapping by choosing the k closest links (e.g., in terms ofTTL or IP prefix distance), or by choosing k random links in aP2P file-sharing system. Notice here that DHTs like Chord solve a different problem. They route queries, not data traffic.The latter is left to a separate subsystem that typicallyopens a direct connection to the target host.

 (2) Providing abstractions of the underlying fundamental neighbor selection problem that are analytically tractable, especially via game theoreticanalysis. To date, however, the bulk of the work and main results in this area have centered on strategic games where edges are undirected, access costs are based on hop-counts, and nodes have potentially unbounded degrees. While this existing body of work is extremely helpful for laying a theoretical foundation and for building intuition, it is not clear how or whether the guidance provided by this prior work generalizes to situations of practical interest, in which underlying assumptions in these prior studies are not satisfied. Another aspect not considered in previous work is the consideration of settings in which some or even most players do not play optimally – a setting which we believe to be typical. Interesting questions along these lines include an assessment of the advantage to a player from employing an optimizing strategy, when most other players.Do not, or more broadly, whether employing an optimizing strategy by a relatively small number of players could beenough to achieve global efficiency.

SOFTWARE REQUIREMENTS:

HARDWARE REQUIREMENT:

  • Minimum 1.1 GHz PROCESSOR should be on the computer.
  • 128 MB RAM.
  • 20 GB HDD.
  • 44 MB FDD.
  • 52x CD-ROM Drive.
  • MONITORS at 800×600 minimum resolution at 256 colors minimum.
  • I/O, One or two button mouse and standard 101-key keyboard.

SOFTWARE REQUIREMENT:

  • Operating System : Windows 95/98/2000/NT4.0.
  • Technology                 :  JAVA, JFC(Swing)
  • Database Connectivity :