Repository logo

Browsing by Author "Jayasumana, Anura, advisor"

Now showing 1 - 7 of 7
  • Thumbnail Image
    ItemOpen Access
    Capture and reconstruction of the topology of undirected graphs from partial coordinates: a matrix completion based approach
    (Colorado State University. Libraries, 2017) Ramasamy, Sridhar, author; Jayasumana, Anura, advisor; Paffenroth, Randy, committee member; Ray, Indrajit, committee member; Pasricha, Sudeep, committee member
    With the advancement in science and technology, new types of complex networks have become common place across varied domains such as computer networks, Internet, bio-technological studies, sociology, and condensed matter physics. The surge of interest in research towards graphs and topology can be attributed to important applications such as graph representation of words in computational linguistics, identification of terrorists for national security, studying complicated atomic structures, and modeling connectivity in condensed matter physics. Well-known social networks, Facebook, and twitter, have millions of users, while the science citation index is a repository of millions of records and citations. These examples indicate the importance of efficient techniques for measuring, characterizing and mining large and complex networks. Often analysis of graph attributes to understand the graph topology and embedded properties on these complex graphs becomes difficult due to causes such need to process huge data volumes, lack of compressed representation forms and lack of complete information. Due to improper or inadequate acquiring processes, inaccessibility, etc., often we end up with partial graph representational data. Thus there is immense significance in being able to extract this missing information from the available data. Therefore obtaining the topology of a graph, such as a communication network or a social network from incomplete information is our research focus. Specifically, this research addresses the problem of capturing and reconstructing the topology of a network from a small set of path length measurements. An accurate solution for this problem also provides means of describing graphs with a compressed representation. A technique to obtain the topology from only a partial set of information about network paths is presented. Specifically, we demonstrate the capture of the network topology from a small set of measurements corresponding to a) shortest hop distances of nodes with respect to small set of nodes called as anchors, or b) a set of pairwise hop distances between random node pairs. These two measurement sets can be related to the Distance matrix D, a common representation of the topology, where an entry contains the shortest hop distance between two nodes. In an anchor based method, the shortest hop distances of nodes to a set of M anchors constitute what is known as a Virtual Coordinate (VC) matrix. This is a submatrix of columns of D corresponding to the anchor nodes. Random pairwise measurements correspond to a random subset of elements of D. The proposed technique depends on a low rank matrix completion method based on extended Robust Principal Component Analysis to extract the unknown elements. The application of the principles of matrix completion relies on the conjecture that many natural data sets are inherently low dimensional and thus corresponding matrix is relatively low ranked. We demonstrate that this is applicable to D of many large-scale networks as well. Thus we are able to use results from the theory of matrix completion for capturing the topology. Two important types of graphs have been used for evaluation of the proposed technique, namely, Wireless Sensor Network (WSN) graphs and social network graphs. For WSN examples, we use the Topology Preserving Map (TPM), which is a homeomorphic representation of the original layout, to evaluate the effectiveness of the technique from partial sets of entries of VC matrix. A double centering based approach is used to evaluate the TPMs from VCs, in comparison with the existing non-centered approach. Results are presented for both random anchors and nodes that are farthest apart on the boundaries. The idea of obtaining topology is extended towards social network link prediction. The significance of this result lies in the fact that with increasing privacy concerns, obtaining the data in the form of VC matrix or as hop distance matrix becomes difficult. This approach of predicting the unknown entries of a matrix provides a novel approach for social network link predictions, and is supported by the fact that the distance matrices of most real world networks are naturally low ranked. The accuracy of the proposed techniques is evaluated using 4 different WSN and 3 different social networks. Two 2D and two 3D networks have been used for WSNs with the number of nodes ranging from 500 to 1600. We are able to obtain accurate TPMs for both random anchors and extreme anchors with only 20% to 40% of VC matrix entries. The mean error quantifies the error introduced in TPMs due to unknown entries. The results indicate that even with 80% of entries missing, the mean error is around 35% to 45%. The Facebook, Collaboration and Enron Email sub networks, with 744, 4158, 3892 nodes respectively, have been used for social network capture. The results obtained are very promising. With 80% of information missing in the hop-distance matrix, a maximum error of only around 6% is incurred. The error in prediction of hop distance is less than 0.5 hops. This has also opened up the idea of compressed representation of networks by its VC matrix.
  • Thumbnail Image
    ItemOpen Access
    Coordinate repair and medial axis detection in virtual coordinate based sensor networks
    (Colorado State University. Libraries, 2014) Mahindre, Gunjan S., author; Jayasumana, Anura, advisor; Luo, J. Rockey, committee member; Malaiya, Yashwant, committee member
    Wireless Sensor Networks (WSNs) perform several operations like routing, topology extraction, data storage and data processing that depend on the efficiency of the localization scheme deployed in the network. Thus, WSNs need to be equipped with a good localization scheme as the addressing scheme affects the performance of the system as a whole. There are geographical as well as Virtual Coordinate Systems (VCS) for WSN localization. Although Virtual Coordinate (VC) based algorithms work well after system establishment, they are hampered by events such as node failure and link failure which are unpredictable and inevitable in WSNs where sensor nodes can have only a limited amount of energy to be used. This degrades the performance of algorithms and reduces the overall life of the network. WSNs, today, need a method to recover from such node failures at its foundation level and maintain its performance of various functions despite node failure events. The main focus of this thesis is preserving performance of virtual coordinate based algorithms in the presence of node failure. WSNs are subject to changes even during their operation. This implies that topology of the sensor networks can change dynamically throughout its life time. Knowing the shape, size and variations in the network topology helps to repair the algorithm better. Being centrally located in the network, medial nodes of a network provides us with information such as width of the network at a particular cross-section and distance of network nodes from boundary nodes. This information can be used as a foundation for applications such as network segmentation, VC system implementation, routing scheme implementation, topology extraction and efficient data storage and recovery. We propose a new approach for medial axis extraction in sensor networks. This distributed algorithm is very flexible with respect to the network shape and size. The main advantage of the algorithm is that, unlike existing algorithms, it works for networks with low node degrees. An algorithm for repairing VCS when network nodes fail is presented that eliminates the need for VC regeneration. This helps maintain efficient performance for all network sizes. The system performance degrades at higher node failure percentages with respect to the network size but the degradation is not abrupt and the system maintains a graceful degradation despite sudden node failure patterns. A hierarchical virtual coordinate system is proposed and evaluated for its response to network events like routing and node failures. We were also able to extract medial axis for various networks with the presented medial axis detection scheme. The networks used for testing fall under a range of shapes and an average node degree from 3 to 8. Discussions over the VC repair algorithm and the novel medial axis extraction scheme provide an insight into the nature of proposed schemes. We evaluate the scope and limitations for VCS repair algorithm and medial axis detection scheme. Performance of the VC repair algorithm in a WSN is evaluated over various conditions simulated to represent a practical node failure events to gauge the system response through routing percentage and average hop count over the network. We compare the results obtained through our medial axis detection scheme with existing state-of-the-art algorithm. The results show that this scheme overcomes the shortcomings of the medial axis detection schemes. The proposed medial axis detection technique enables us to extract the information held by a medial axis of a sensor network. The VC repair algorithm and the new medial axis extraction scheme perform very efficiently to make a WSN tolerant of node failure events.
  • Thumbnail Image
    ItemOpen Access
    Efficient representation, measurement, and recovery of spatial and social networks
    (Colorado State University. Libraries, 2021) Mahindre, Gunjan S., author; Jayasumana, Anura, advisor; Paffenroth, Randy, committee member; Maciejewski, Anthony, committee member; Kirby, Michael, committee member
    To view the abstract, please see the full text of the document.
  • Thumbnail Image
    ItemOpen Access
    Fully integrated network of networks
    (Colorado State University. Libraries, 2022) LaMar, Suzanna, author; Jayasumana, Anura, advisor; Cale, Jim, committee member; Guo, Yanlin, committee member; Simske, Steve, committee member
    There are many different facets to developing a fully integrated network of networks system that can facilitate seamless information exchange between nodes within a complex network topology. As an example, individual link resiliency, enhanced waveform capabilities, spectral and spatial diversity are all critical features in providing communications that can enable connectivity and interoperability for a fully networked system extending into multiple domains (ground, surface, air, and space). Steps taken toward achieving such an architecture are introduced with emerging millimeter wave (mmW) and high-band antenna technologies that can be integrated with future tactical multifunction software defined radios (SDRs) to enable information distribution between vital networked participants, including 5th generation aircraft. Small, lightweight mmW and high-band antenna designs that will enable small unit tactical operations to persist under electronic warfare conditions will be discussed. These small units are typically fielded with multiple communications radios but are limited in function and do not enable rapid communication on the move, or high-capacity data transfers at the halt. Additionally, a revolutionary cognitive antenna (CA) is introduced where artificial intelligence (AI) techniques are proposed to aid in improving antenna functions, support self-healing attributes, and promote autonomous communication operations. A CA designed for future spacecraft (S/C) communications systems that is environmentally perceptive will be presented where it can sense and transmit radio frequency (RF) signals and cooperate with a cognitive radio (CR) to modify waveform and beam pattern characteristics for enhanced resiliency and communications. As an extrapolation to interoperability and information exchanges, data must be always secured. Common communications payload security architectures are presented as a basis for offering data protection to not only the system itself, but also to networks that are part of the larger enterprise solution. Similarly, machine learning methods are proposed to combat malicious cyber-attacks within an enterprise security space-based communications architecture to offer a more resilient, protective adaptive framework. Additionally, the machine learning algorithms seek to provide a viable solution for identifying, classifying, and detecting possible intrusions in a highly dynamic environment. Machine learning is also applied to networking strategies to predict congestion before it happens; thereby, preventing bottlenecks within the network. This is especially important for critical, high-value information. A CONgestion Aware Intent-based Routing (CONAIR) architecture that facilitates faster and more reliable data exchanges between end users is proposed. The CONAIR architecture leverages platform and mission information to derive quality of service (QoS) metrics that can be used to support network route optimizations by using a network controller (NC) with machine learning to predict future network behaviors. Finally, the CA, multifunction SDRs and NC subsystems are integrated into a robust architecture on unmanned aerial vehicles (UAVs) to form collaborative cognitive communications systems that are responsive to stressing operating conditions. Through collaborative behaviors and interactions, communications can be optimized. These discriminating technologies support the continued ambition for maturating military communications systems to benefit cooperative interactions and information exchanges between various users in multi-hop, complex networks.
  • Thumbnail Image
    ItemOpen Access
    Multi-attribute query resolution in structured peer-to-peer networks
    (Colorado State University. Libraries, 2016) Chatterjee, Shibayan, author; Jayasumana, Anura, advisor; Pezeshki, Ali, committee member; Pallickara, Sangmi Lee, committee member
    Collaborative grid and cloud computing applications may be implemented by forming virtual clusters on demand. Formation of such clusters will require diverse resources with specific attributes to execute and support the specific application and its performance requirements. This thesis focuses on formation of such systems by looking up resources over a distributed peer-to-peer system. Discovery of appropriate resources from an enormous distributed pool of resources becomes tedious, but it should be resolved with minimum cost and latency. There can be a number of attributes characterizing each resource, and these attributes may have ranges of values depending upon the characteristics of the resources. Thus, when performing a look-up for appropriate resources with a peer-to-peer approach, the objective moves from a single-dimensional look-up problem to a multi-dimensional look-up problem. The look-up operation has to be optimized in terms of delay in resolution, hop-count, communication cost, and overhead cost. This thesis develops and evaluates an architecture aimed at resolving this n-dimensional peer-to-peer look-up problem. The optimality of the proposed solution is evaluated in terms of communication overhead, delay, and hop count for look up. The complexity of n-dimensional look-up problem is further reduced in terms of dimensionality by utilizing the correlation between different attribute characteristics. The proposed architecture uses a structured peer-to-peer network in the form of multiple rings, grouped together on the basis of individual attributes thus forming a Ring of Rings (ROR). Chord protocol is used to maintain the scalability and for having communication cost for lookup within logarithmic time complexity. Communication within the network is done using Bloom filters as a data structure, which represents the resources satisfying different attribute values. The novelty of the architecture and the communication methodology lies in the fact that architecture facilitates any number of attributes having any range of values. Furthermore, use of Bloom-filters for communication reduces the overhead normally required to carry around long lists of resources to perform the final intersection that resolves the query. Using Bloom-filters greatly reduces the communication overhead and the cost of communication. The ROR architecture coupled with Bloom-filter messages reduces the message sizes considerably, but it introduces a certain amount of false positives. The findings indicate that with the optimum number of hash-functions and the optimum sized Bloom-filter, a ROR peer-to-peer architecture to search for multi-attribute queries can be much more efficient than the conventional systems used for the resolution of same type of queries. Queries associated with many systems request attributes which are correlated to each other. The research also addresses the identification of such resources more efficiently based on correlation of the attributes. The ROR architecture can be tuned for resolving these kinds of queries. The new architectures proposed are localized caching and overlapped ring architecture. The network configuration responsible for resolving the query is the same structured peer-to-peer network, where caching and overlapped ring strategies fit in to resolve multiple correlated attributes. These architectures also use Bloom-filter as a data structure to resolve the queries with minimum communication cost and overhead. Performance of proposed architectures is evaluated using simulations, with the resource traces for simulation generated using the ResQue resource generation tool. The results obtained for a simulation environment consisting of 700 resources, each with 12 different types of attributes, and the number of nodes from 24 to 84 indicates a 30% reduction in communication overhead, 7% reduction in delay in response, and 10% reduction in average load per node. The optimum number of hash functions for the Bloom-filter is 6, and the m/n ratio is kept 10 where m is the size of Bloom-filter and n is the resource count. The optimum number of nodes responsible for each attribute is found to be 5. In case of correlated attributes, for the same set of resource count and number of nodes the caching and overlapped ring architecture (using Bloom-filters), provides 58.5% and 57.3% reductions in hop-count, 56.63% and 52.06% reductions in delay in response, message sizes gets reduced by 10% and the average load per node gets reduced by 9% and 34% respectively. The comparison is done over the ROR architecture using Bloom-filters. The number of hash functions for Bloom-filters is considered 4, m/n ratio to be 10 and with 4 nodes per attribute in case of co-related attribute resolution.
  • Thumbnail Image
    ItemOpen Access
    Security of virtual coordinate based wireless sensor networks
    (Colorado State University. Libraries, 2015) Bose, Divyanka, author; Jayasumana, Anura, advisor; Pasricha, Sudeep, committee member; Papadopoulos, Christos, committee member
    Wireless Sensor Networks (WSNs) perform critical functions in many applications such as, military surveillance, rescue operations, detection of fires and heath care monitoring. In these applications, nodes in the network carry critical and sensitive data. Thus, WSNs are prone to various kinds of attacks that target different protocols and layers of the network. Also, most of the WSNs are placed remotely that makes it difficult to implement security measures after deployment. Thus, security of WSNs needs to be considered at the initial stage of system design. In many applications, the nodes are deployed randomly, and thus are unpredictable in terms of physical network topology. Virtual Coordinate (VC) based WSNs possess significant advantages over Geographical Coordinate (GC) based WSNs. This is because VCs negate the need for physical localization of nodes, which require costly techniques like GPS. The VCs of the nodes in the network are very important for basic functionalities such as routing and self-organization. However, security of VCs has not been extensively researched even though routing algorithms rely on the correctness of the VCs for proper functioning. VC based WSNs are susceptible to attacks resulting from malicious modification of VCs of individual nodes. While the impact of some such attacks is localized, others such as Coordinate Deflation and Wormholes (tunneling) can cause severe disruptions. This thesis proposes techniques for the detection and mitigation of attacks, which are aimed at the VC based WSNs. We propose a novel approach where coordinate attacks are identified by detecting changes in the shape of the network, extracted using Topology Maps. A comprehensive solution for detection of coordinate-based attacks on VC systems is presented that combines Beta Reputation System and a reputation based routing scheme. Latter ensures safe communication that bypasses malicious nodes during detection process. The Coordinate Deflation and Wormhole attacks are discussed and the effect and intensity of these attacks are addressed. Two methods are proposed and compared for the detection of attacks. In the first method, the topology distortion is rated using clusters identifiable by existing VCs, thus requiring low computation and communication overhead. A measure of topology distortion is presented. The existence of a trusted base station is needed for this method. In the second method, the detection is distributed and removes the need for a base station/server. We compare the advantages and disadvantages of the two methods, and discuss the scenarios in which these algorithms maybe implemented. Simulation based evaluations demonstrate that both the schemes efficiently detects Deflation and Wormhole attacks. We choose a variety of dense networks with different topologies and deployment characteristics for evaluation. Networks with voids, representative of physical spaces with voids, as well as randomly deployed networks are considered, to ensure the correct operation and scalability of the algorithms. We show through simulations that the detection schemes can easily differentiate between the changes in the network due to node failures, e.g., caused by battery drain, from those due to an attack. Future sensor networks are predicted to be in the scale of millions of nodes. Thus, a need for security algorithms which can be scaled are highly desirable. We show in our simulations that the proposed detection schemes can be applied to networks of larger density successfully.
  • Thumbnail Image
    ItemOpen Access
    Towards emulation of large-scale IP networks using end-to-end packet delay characteristics
    (Colorado State University. Libraries, 2008) Vivanco, Daniel A., author; Jayasumana, Anura, advisor
    Network emulation combines concepts from network simulation and measurements and provides a emulated network testbed over which application and protocols can be tested. Existing network emulators are not scalable due to the limitations of available computer hardware infrastructure and the reliance on one-to-one packet mapping and modeling scheme. This research proposes a measurement-based modeling methodology for the design of a network-in-a-box emulator. Methodology aims at overcoming the limitation of computational overhead and end-to-end network system characterization. A framework for large scale IP network emulation, named Overall Trend Replicating Network Emulator Tool (OTRENET), is presented. OTRENET intercepts data packet streams and modify them, based on network system models, in real-time. The complexity and overhead of packet-by-packet mapping and modeling, while producing results consistent with measurements is achieved by a traffic sampling algorithm. Such algorithm monitors traffic metrics in a per-packet level, to dynamically separate it into frames. A comprehensive study of end-to-end packet delay dynamics, in the context of network system modeling, is presented. Theoretical basis, techniques and measurements for network packet delay dynamics characterization and modeling for various sending rate conditions and network stages have been developed. Goodness-of-fit results demonstrate the modeling accuracy for both packet delay and IPG processes for cases where sending bit rate is relatively small compared to the link capacity. However, as the sending bit rate increases, as a fraction of the bandwidth, IPG becomes a better alternative for network system modeling. A novel approach for online modeling end-to-end packet delay dynamics is proposed to address non-stationarity of network systems. Proposed methodology models and captures the network system characteristics taking into account the non-stationarity of the packet delay samples. In general, results presented show that analyzing packet delay processes by modeling the segmented traces yield a better understanding of the network system dynamics.