Network science | EPFL Graph Search

Network science is an academic field which studies complex networks such as telecommunication networks, computer networks, biological networks, cognitive and semantic networks, and social networks, considering distinct elements or actors represented by nodes (or vertices) and the connections between the elements or actors as links (or edges). The field draws on theories and methods including graph theory from mathematics, statistical mechanics from physics, data mining and information visualization from computer science, inferential modeling from statistics, and social structure from sociology. The United States National Research Council defines network science as "the study of network representations of physical, biological, and social phenomena leading to predictive models of these phenomena." Background and history The study of networks has emerged in diverse disciplines as a means of analyzing complex relational data. The earliest known paper in this field is the famo

Denial-of-service resilience in peer-to-peer file sharing systems

Dan Mihai Dumitriu, Willy Zwaenepoel

Peer-to-peer (p2p) file sharing systems are characterized by highly replicated content distributed among nodes with enormous aggregate resources for storage and communication. These properties alone are not sufficient, however, to render p2p networks immune to denial-of-service (DoS) attack. In this paper, we study, by means of analytical modeling and simulation, the resilience of p2p file sharing systems against DoS attacks, in which malicious nodes respond to queries with erroneous responses. We consider the filetargeted attacks in current use in the Internet, and we introduce a new class of p2p-network-targeted attacks. In file-targeted attacks, the attacker puts a large number of corrupted versions of a single file on the network. We demonstrate that the effectiveness of these attacks is highly dependent on the clients’ behavior. For the attacks to succeed over the long term, clients must be unwilling to share files, slow in removing corrupted files from their machines, and quick to give up downloading when the system is under attack. In network-targeted attacks, attackers respond to queries for any file with erroneous information. Our results indicate that these attacks are highly scalable: increasing the number of malicious nodes yields a hyperexponential decrease in system goodput, and a moderate number of attackers suffices to cause a near-collapse of the entire system. The key factors inducing this vulnerability are (i) hierarchical topologies with misbehaving “supernodes,” (ii) high path-length networks in which attackers have increased opportunity to falsify control information, and (iii) power-law networks in which attackers insert themselves into high-degree points in the graph. Finally, we consider the effects of client counter-strategies such as randomized reply selection, redundant and parallel download, and reputation systems. Some counter-strategies (e.g., randomized reply selection) provide considerable immunity to attack (reducing the scaling from hyperexponential to linear), yet significantly hurt performance in the absence of an attack. Other counter-strategies yield little benefit (or penalty). In particular, reputation systems show little impact unless they operate with near perfection.

2005

Graph Signal Processing for Machine Learning: A Review and New Perspectives

Michael Bronstein, Xiaowen Dong, Pascal Frossard, Laura Toni

The effective representation, processing, analysis, and visualization of large-scale structured data, especially those related to complex domains, such as networks and graphs, are one of the key questions in modern machine learning. Graph signal processing (GSP), a vibrant branch of signal processing models and algorithms that aims at handling data supported on graphs, opens new paths of research to address this challenge. In this article, we review a few important contributions made by GSP concepts and tools, such as graph filters and transforms, to the development of novel machine learning algorithms. In particular, our discussion focuses on the following three aspects: exploiting data structure and relational priors, improving data and computational efficiency, and enhancing model interpretability. Furthermore, we provide new perspectives on the future development of GSP techniques that may serve as a bridge between applied mathematics and signal processing on one side and machine learning and network science on the other. Cross-fertilization across these different disciplines may help unlock the numerous challenges of complex data analysis in the modern age.

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2020

Object-oriented method and architecture for virtual private network service management

One of the major trends in the evolution of current corporate networking is an increasing need for high performance long distance communications. Provided as an alternative to leased lines networks, virtual private networks (VPNs) are gaining increasing acceptance among customers and network providers by providing corporate networking between geographically dispersed customer premises based on a shared public switched network infrastructure. As a contribution towards this evolution, the present thesis proposes a generic object-oriented architecture for open distributed VPN services integrating service and management issues all along the modeling process. The aim of this VPN architecture is not only to provide a descriptive model of VPNs but also to illustrate possible ways of operating on that model to solve VPN related service or management issues. The architecture proposed is generic in the sense that, firstly, it is network technology independent and, secondly, that it captures the fundamental characteristics common to all VPNs. This latter aspect is very important as, due to the lack of standardization in this area, current VPNs are more marketable products than well-defined telecommunications services. The notion of distribution is also very important as telecommunications systems in general, and VPNs in particular, are intrinsically distributed. Indeed, a VPN can be seen as a distributed application running on the multiple nodes of telecommunications networks. To effectively deal with this de facto distribution and to exploit at best the benefits it can provide the VPN service and management services have been conceived from the very beginning as distributed applications. For this purpose, and due to the lack of satisfactory existing solutions in this area, an object-oriented method for the specification and design of open distributed telecommunications and management services has been developed. The proposed method combines the ODP (Open Distributed Processing) concepts and stucturing rules with the systematic development process advocated by an object-oriented software engineering method called Fusion. This method provides an architectural framework and a seamless thread from problem definition to the realization of the distributed telecommunications system, based on hierarchically related abstraction levels. Mapping rules, guidelines and notations are proposed on how and when enterprise, information and computational models should be built, in particular based on models performed at a higher abstraction level. The method has then been applied to the specification of the generic VPN architecture itself. In the enterprise viewpoint the scope of the VPN service has been refined and limited to the provision, within the public domain boundary, of internetworking services between customer premises networks. The main actors involved in using, providing and managing the VPN service have been described as well as interactions between them. Based on their requirements, fundamental VPN characteristics have been identified, among which the notions of virtual resource and of closed user group are the most relevant. In the information viewpoint, a generic object-oriented network information model has been developed based on standard network resources. This model has been recursively applied to specify the object models pertaining to the different layers of the VPN architecture. Based on this architecture, a management service allowing customers to dynamically configure the logical connectivity of their VPN has been specified down to the network elements level. The realization of this functionality in terms of application components suitable for distribution and interactions between them has been the purpose of the computational viewpoint. Finally, the generic VPN architecture has been refined and applied to the particular context of ATM-based VPNs. In addition to describing how VPNs can be built on ATM networks this case study addresses a very important issue in such an environment, narnely bandwidth management. In this respect, an open distributed VPN bandwidth management service has been specified that allows VPN customers to dynamically modify the bandwidth allocated to the virtual path connections connecting the different sites of their organization. The final outcome of this specification process is the definition of a computational architecture for VPN bandwidth management extending from VPN level down to the physical network elements. This work has been carried out in the frame of the RACE (Research and Development in Advanced Communications Technologies in Europe) project R2041 PRISM (Pan-European Reference Configuration for IBC Services Management).

EPFL1996

Denial-of-service resilience in peer-to-peer file sharing systems

Dan Mihai Dumitriu, Willy Zwaenepoel

2005

Object-oriented method and architecture for virtual private network service management

EPFL1996