CiteULike: anhlc's library [28 articles]

Power-law distributions in empirical data

Aaron Clauset — 2007-06-13T16:25:35-00:00

(7 Jun 2007)

Power-law distributions occur in many situations of scientific interest and have significant consequences for our understanding of natural and man-made phenomena. Unfortunately, the empirical detection and characterization of power laws is made difficult by the large fluctuations that occur in the tail of the distribution. In particular, standard methods such as least-squares fitting are known to produce systematically biased estimates of parameters for power-law distributions and should not be used in most circumstances. Here we describe statistical techniques for making accurate parameter estimates for power-law data, based on maximum likelihood methods and the Kolmogorov-Smirnov statistic. We also show how to tell whether the data follow a power-law distribution at all, defining quantitative measures that indicate when the power law is a reasonable fit to the data and when it is not. We demonstrate these methods by applying them to twenty-four real-world data sets from a range of different disciplines. Each of the data sets has been conjectured previously to follow a power-law distribution. In some cases we find these conjectures to be consistent with the data while in others the power law is ruled out.

An epidemic model for information diffusion in manets

A Khelil — 2008-01-30T09:35:45-00:00

(2002)

Choosing appropriate information dissemination strategies is crucial in mobile ad hoc networks (MANET) due to the frequent topology changes. Flooding-based approaches like diffusion have a strong similarity with epidemic spreading of diseases. Applying epidemiological models to information diffusion allows the evaluation of such strategies depending on the MANET characteristics, e.g. the node density. In order to choose appropriate strategies at run time, the model should be easily evaluated.

P2P File Sharing System over MANET based on Swarm Intelligence: A Cross-Layer Design

Cheng-Chang Hoh — 2007-10-20T13:13:05-00:00

Wireless Communications and Networking Conference, 2007.WCNC 2007. IEEE (2007), pp. 2674-2679.

The dynamic nature of MANET causes many challenges in designing robust and scalable P2P system. Although flooding-based techniques are shown to be robust in highly dynamic network, it leads to poor efficiency in terms of bandwidth usage and scalability. In this paper, we propose an efficient and scalable P2P file sharing system based on swarm intelligence for MANET, referred to as P2PSI. By applying the behavior of the real ant colonies, P2PSI owns the capability of adaptive learning and is able to cope with mobility problem without flooding. Moreover, we also present a cross-layer architecture for P2PSI to reduce the redundant message overhead and query latency. Performance of our cross-layer design P2PSI is compared with two existing cross-layer design service discovery protocols, namely, CL<sub>dsr</sub> and CL<sub>dsr</sub> through simulations. The simulation results show that our cross-layer design P2PSI achieves better performance in terms of control overhead, request success ratio, and path length.

When peer-to-peer comes face-to-face: collaborative peer-to-peer computing in mobile ad-hoc networks

G Kortuem — 2008-01-09T10:10:32-00:00

Peer-to-Peer Computing, 2001. Proceedings. First International Conference on (2001), pp. 75-91.

This paper motivates and describes the notion of mobile ad-hoc information systems. Such a system consists of a decentralized and self-organizing network of autonomous, mobile devices that interact as peers. Connectivity is determined by distance between devices; as hosts change their physical location they establish pair-wise communication links based on mutual proximity. We describe application scenarios for mobile ad-hoc information systems and identify technical challenges of a generic software infrastructure. Moreover, we present the goals and architecture of Proem, a peer-to-peer system and development platform for mobile ad-hoc applications. Proem has successfully been used as instructional tool in an advanced software engineering course on peer-to-peer computing

A Cross-layer Decentralized BitTorrent for Mobile Ad hoc Networks

Sundaram Rajagopalan — 2008-01-09T10:07:20-00:00

Mobile and Ubiquitous Systems: Networking & Services, 2006 Third Annual International Conference on (2006), pp. 1-10.

In recent years, a number of P2P systems, for instance, Gnutella, KaZaA, Napster, and BitTorrent, have been proposed for the wired Internet. However, these protocols are not immediately applicable to the mobile ad hoc networks (MANETs) owing to the extreme conditions MANETs operate under. Of the above protocols, although BitTorrent has several features which make it an ideal candidate for adapting to MANETs, the current specification of BitTorrent has several drawbacks which make a straightforward implementation of BitTorrent for MANETs an undesirable solution. In this paper, we investigate a straightforward implementation of BitTorrent in MANETs, termed BTI, and compare its performance with a cross-layer adaptation of BitTorrent for MANETs, termed BTM. We resolve the issues of centralized control and single point of failure in BTI by proposing mechanisms to decentralize the BitTorrent model for MANETs and provide resource/data redundancy to improve the protocol performance. In addition, the cross-layer model of BTM is more suited for use in a MANET. Our performance comparison studies show that BTM is able to outperform BTI in terms of goodput, and the number of pieces delivered, in the context of amortizing the client download expenses over more connections (that is, BTM has a higher average peer degree)

P2P over Manet: a comparison of cross-layer approaches

Mario Bisignano — 2008-01-09T10:03:43-00:00

Database and Expert Systems Applications, 2007. DEXA '07. 18th International Conference on (2007), pp. 814-818.

Mobile ad-hoc networks (Manet) and peer-to-peer (P2P) systems are recently emerged technologies which share a common underlying decentralized networking paradigm. However, the two fields have been mainly investigated by different research communities, without catching several cross-cutting issues. Both systems share some common issues and relevant differences: however, similarities could be exploited in a more synergic way when coupling the two systems. In particular, very recently, some cross-layer approaches have appeared, trying to improve the overall performance of a P2P-Manet system: in this paper, we analyze them in order to identify some common guidelines and the most promising approaches. Indeed, since many combinations of Manet routing algorithm and P2P overlay network building are possible, our analysis also aims to minimize common pitfalls in designing such kind of applications.

Usability of Legacy p2p Multicast in Multihop Ad Hoc Networks: An Experimental Study

Andrea Passarella — 2007-03-12T13:40:03-00:00

EURASIP Journal on Wireless Communications and Networking, Vol. 2007 (2007)

Exchange-Based Incentive Mechanisms for Peer-to-Peer File Sharing

Kostas Anagnostakis — 2006-10-26T10:33:15-00:00

(March 2004)

On the correlation between route dynamics and routing loops

Ashwin Sridharan — 2006-08-25T12:39:30-00:00

(2003)

Routing loops are caused by inconsistencies in the routing state of the network. Although undesirable from this aspect, they can provide insight into the routing dynamics that caused them. In this work we present a methodology that utilizes a priori knowledge of loops to study the correlation between routing loops and routing events that could have caused them. We apply our technique to associate route changes with packet loops detected in actual traffic traces collected from the Sprint Backbone. Our study shows that a strong correlation exists between loops and changes in the BGP routing state while the link state protocols ISIS is seldom responsible for such events. Our analysis also identifies factors that influence the distribution of loop path lengths as well as the effectiveness of our detection techniques.

Working around BGP: An incremental approach to improving security and accuracy in interdomain routing

G Goodell — 2006-07-18T07:59:31-00:00

(2003)

BGP is essential to the operation of the Internet, but is vulnerable to both accidental failures and malicious attacks. We propose a new protocol that works in concert with BGP, which Autonomous Systems will use to help detect and mitigate accidentally or maliciously introduced faulty routing information. The protocol differs from previous efforts at securing BGP in that it is receiver-driven, meaning that there is a mechanism for recipients of BGP UPDATE messages to corroborate the information ...

Detecting BGP Configuration Faults with Static Analysis

Nick Feamster — 2006-05-23T08:54:58-00:00

This paper describes the design and implementation of rcc, the router configuration checker, a tool that finds faults in BGP configurations using static analysis. rcc detects faults by checking constraints that are based on a high-level correctness specification. rcc detects two broad classes of faults: route validity faults, where routers may learn routes that do not correspond to usable paths, and path visibility faults, where routers may fail to learn routes for paths that exist in the network. rcc enables network operators to test and debug configurations before deploying them in an operational network, improving on the status quo where most faults are detected only during operation. rcc has been downloaded by more than sixty-five network operators to date, some of whom have shared their configurations with us. We analyze network-wide configurations from 17 different ASes to detect a wide variety of faults and use these findings to motivate improvements to the Internet routing infrastructure.

SPV: secure path vector routing for securing BGP

Yih-Chun Hu — 2006-04-28T14:50:05-00:00

SIGCOMM Comput. Commun. Rev., Vol. 34, No. 4. (October 2004), pp. 179-192.

A Public Key Infrastructure for the Secure Border Gateway Protocol (S-BGP)

2006-04-28T14:32:56-00:00

Design and Analysis of the Secure Border Gateway Protocol (S-BGP)

2006-04-28T14:32:02-00:00

Locating BGP missing routes using multiple perspectives

Di-Fa Chang — 2006-04-25T09:11:52-00:00

(2004), pp. 301-306.

BorderGuard: detecting cold potatoes from peers

Nick Feamster — 2006-04-25T09:09:51-00:00

(2004), pp. 213-218.

Autonomous System Isolation under Bgp Session Attacks with RFD Exploitation

Kotikalapudi Sriram — 2006-04-25T08:53:17-00:00

IEEE JSAC special issue on High-Speed Network Security (2006)

There is a growing apprehension in the Internet community that there are potentially significant vulnerabilities in the deployed Border Gateway Protocol (BGP) routing system. Researchers speculate and debate the potential of targeted attacks to trigger large scale, potentially cascading, failures and persistent instability in the global routing system. To date, most modeling and analysis of BGP behavior under threatening scenarios has been limited to post mortem analysis of global routing exchanges during worm and virus attacks of Internet hosts; but these are not attacks focused on BGP. In this paper, we present results from our effort to conduct “what if” analyses of yet unseen attacks and to develop means to characterize the impact of various attacks on a distributed BGP routing system. In particular, we present a detailed study of the impact of BGP peering session attacks and the resulting exploitation of RFD that cause network-wide routing disruptions. Analytical results provide insights into the nature of the problem and impact of the attacks. Detailed packet level simulation results complement the analytical results and provide many useful insights as well. We also quantify the effect of BGP Graceful Restart mechanism on partial mitigation of the BGP vulnerability to peering session attacks.

Learning-based anomaly detection in BGP updates

Jian Zhang — 2006-04-25T08:47:55-00:00

(2005), pp. 219-220.

On Detection of Anomalous Routing Dynamics in Bgp

Ke Zhang — 2006-04-25T08:43:51-00:00

(2004), pp. 259-270.

BGP, the de facto inter-domain routing protocol, is the core component of current Internet infrastructure. BGP traffic deserves thorough exploration, since abnormal BGP routing dynamics could impair global Internet connectivity and stability. In this paper, two methods, signature-based detection and statistics-based detection, are designed and implemented to detect BGP anomalous routing dynamics in BGP UPDATEs. Signature-based detection utilizes a set of fixed patterns to search and identify routing anomalies. For the statistics-based detection, we devise five measures to model BGP UPDATEs traffic. In the training phase, the detector is trained to learn the expected behaviors of BGP from the historical longterm BGP UPDATEs dataset. It then examines the test dataset to detect ”anomalies” in the testing phase. An anomaly is flagged when the tested behavior significantly differs from the expected behaviors. We have applied these two approaches to examine the BGP data collected by RIPE-NCC servers for a number of IP prefixes. Through manual analysis, we specify possible causes of some detected anomalies. Finally, comparing the two approaches, we highlight the advantages and limitations of each. While our evaluation is still preliminary, we have demonstrated that, by combining both signature-based and statistics-based anomaly detection approaches, our system can effectively and accurately identify certain BGP events that are worthy of further investigation.

Combining visual and automated data mining for near-real-time anomaly detection and analysis in BGP

Soon Teoh — 2006-04-25T08:32:37-00:00

(2004), pp. 35-44.

Detection of BGP routing misbehavior against Cyber-Terrorism

G Siganos — 2006-04-24T16:00:46-00:00

Military Communications Conference, 2005. MILCOM 2005. IEEE (2005), pp. 1-7.

Attacks at the control and routing plane may be the next generation of threats for the Internet. Manipulation of the routing layer could originate from profiteering, malice, or simply human error. The community has recognized this danger and several promising approaches have been proposed to capture and block routing anomalies. In practice, the difficulty of deploying such approaches limits their usefulness. Our goal is to develop a scheme that can have immediate impact today. In this light, we propose a reactive approach that can help reduce the extent and impact of routing misbehaviors. We develop an approach and a tool to act as an expert advisor that will flag suspicious updates. Our main motivation is that problems spread quickly, so quick reaction is imperative. Additionally, the volume of routing updates makes it impossible for humans operators to manually identify malicious updates. Our approach uses the policies that Autonomous Systems register in the Internet Routing Registries. We use the policy of an AS as found in these registries to detect deviations between the intended policy and the actual policy seen in BGP. As a proof of concept, we use the RIPE registry to monitor the European Internet routing for ten days. With our approach, we are able to confirm the validity of the origin AS of 97% of the updates, while suggesting the need for further analysis of the remaining 3% of the updates.

Internet routing anomaly detection and visualization

T Wong — 2006-04-24T15:49:29-00:00

Dependable Systems and Networks, 2005. DSN 2005. Proceedings. International Conference on (2005), pp. 172-181.

Diagnosing inter-domain routing problems in the Internet is hard. BGP, the defacto inter-domain glue, is designed for routing, not diagnosis. It is extremely chatty - the most minor connectivity change produces hundreds of BGP messages and a major peering loss can generate millions - and making sense of the deluge of data remains challenging. We have developed statistical techniques to extract the large-scale structure of BGP events and visualization techniques to display that structure in operationally meaningful ways. These tools can be used to detect routing anomalies in real-time. We show case studies of routing instabilities at a Tier-1 ISP and a large institutional network, automatically diagnosed by our tools. We present drawbacks in using BGP events alone to understand inter-domain routing, and discuss how to solve them through the integration of additional data sources.

Performing BGP experiments on a semi-realistic Internet testbed environment

K Zhang — 2006-04-24T15:47:25-00:00

Distributed Computing Systems Workshops, 2005. 25th IEEE International Conference on (2005), pp. 130-136.

We have built a router testbed that is connected to the Deter/Emist experimental infrastructure. Our goal is to create a semi-realistic testbed to conduct BGP experiments, measure and visualize their impact on network performance and stability. Such testbed is also useful for evaluating different security countermeasures. Our testbed architecture includes four components: routing topology, background traffic, data analysis and visualization. This paper describes how we launch two specific BGP attacks, (a) multiple origin AS and (b) route flap damping attacks, and the lessons learned.

An analysis on selective dropping attack in BGP

Ke Zhang — 2006-04-24T15:45:22-00:00

Performance, Computing, and Communications, 2004 IEEE International Conference on (2004), pp. 593-599.

Previous studies show that current inter-domain routing protocol, border gateway protocol (BGP), is vulnerable to various attacks. Previously, the major concern about BGP security is that malicious BGP routers can arbitrarily falsify BGP routing messages and spread out incorrect routing information. However, one type of attack, which we term as the selective dropping attack, has been largely neglected in literatures. A selective dropping attack occurs when a malicious router intentionally drops incoming and outgoing UPDATE messages, which results in data traffic being blackholed or trapped in a loop. In this paper, we conduct a thorough analysis on this type of attack and advocate that new security countermeasures should be developed to detect and prevent such attack.

A BGP attack against traffic engineering

J Kim — 2006-04-13T08:53:36-00:00

Simulation Conference, 2004. Proceedings of the 2004 Winter, Vol. 1 (2004)

As the Internet grows, traffic engineering has become a widely-used technique to control the flow of packets. For the inter-domain routing, traffic engineering relies on configurations of the border gateway protocol (BGP). While it is recognized that the misconfiguration of BGP can cause negative effects on the Internet, we consider attack methods that disable traffic engineering regardless of the correctness of configurations. We focus on the redirection of traffic as our attack objective, and present attack scenarios on some dominant sample network topologies to achieve this objective. We also evaluate and validate these attacks using two different discrete-event simulators, one that models BGP behavior on a network, and another that emulates it using direct-execution of working BGP code.

An analysis of BGP multiple origin AS (MOAS) conflicts

Xiaoliang Zhao — 2006-04-13T08:35:34-00:00

(2001), pp. 31-35.

Beware of BGP attacks

Ola Nordstrom — 2006-04-13T08:34:15-00:00

SIGCOMM Comput. Commun. Rev., Vol. 34, No. 2. (April 2004), pp. 1-8.

An internet routing forensics framework for discovering rules of abnormal BGP events

Jun Li — 2006-04-04T15:55:03-00:00

SIGCOMM Comput. Commun. Rev., Vol. 35, No. 5. (October 2005), pp. 55-66.