Detecting the presence of extrinsic nodes in a virtual network using a message induced graph

Modern society requires ubiquitous, secure, and reliable network communications. Connecting geographically distributed sites by layer two virtual private networks is a widely deployed, cost effective, and reliable technology. The key feature of L2 VPNs is confidentiality. Network users can easily observe that the only network nodes in the L2 virtual network are those desired by the network owner. However, L2 VPNs are being rapidly replaced by layer three virtual networks as common carriers expand the roles of their shared IP networks. The recent increase of interest in L3 virtual networks has led to renewed interest and new debate concerning their confidentiality.;A significant disadvantage of operating virtual networks over shared IP networks is that the configuration and operation of the virtual network is moved into the common carrier's network exclusively. All of the routing, forwarding, and management is done by the service provider and the network user has no visibility into the configuration and management of the virtual network. The retirement of legacy L2 virtual networks, the widespread availability of common carrier TCP/IP networks, and the migration to L3 virtual network technologies has resulted in the inability to determine if undesirable nodes are connected to a virtual network.;In this research we propose Message Induced Network Appraisal , a novel algorithm for detecting the presence of extrinsic nodes in L3 virtual networks. Network nodes that are undesirable are denoted as extrinsic. MINA is inspired by Kleinberg's HITS algorithm for ranking search results of web pages. The generalization of a HITS derived algorithm to detecting the presence of extrinsic nodes in virtual networks is novel.;Our MINA algorithm constructs the communication graph induced by message exchange, scores the participating nodes to identify key nodes, and detects the presence of extrinsic nodes. Using the MINA algorithm, network users are presented with a useful indicator about the confidentiality of their L3 virtual network. In this dissertation we describe MINA and demonstrate that our proposed method is capable of detecting the presence of extrinsic nodes in L3 virtual networks.