594784
The Dance Party Problem and its Application to Collective Communication in Computer Networks
Abstract Motivated by implementing collective communication operations on workstation clusters, a problem of scheduling a dance party is formulated. The problem is solved by two algorithms based on searching and divide-and-conquer that generate suboptimal schedules and an algorithm based on graph factorization that generates optimal schedules. It is shown how to use dance schedules to implement collective communication operations such as all—gather. Experiment data on a single ethernet segment of SUN SPARC-10 workstations and on a switch connected network, the IBM SP2, show that the all—gather implementation that simply uses the optimal schedule performs better for long messages than the implementations of system MPL from IBM and public-domain systems LAM and MPICH/p4.
1363387
Identifying BGP routing table transfers
BGP routing updates collected by monitoring projects such as RouteViews and RIPE have been a vital source to our understanding of the global routing system. The updates logged by these monitoring projects are generated either by individual route changes, or are part of BGP table transfer. In particular, a session reset between a monitoring station and its BGP peers can result in the peer sending its entire BGP routing table to the monitoring station. In this paper, we present a Minimum Collection Time (MCT) algorithm that accurately identify the start and duration of routing table transfers. Using three months of data from 14 different peers, MCT can identify routing table transfers triggered by BGP session resets with 100% accuracy, and can pinpoint the exact starting time of table transfers in 90% of the cases.
8791084
Collecting the internet AS-level topology
At the inter-domain level, the Internet topology can be represented by a graph with Autonomous Systems (ASes) as nodes and AS peerings as links. This AS-level topology graph has been widely used in a variety of research efforts. Conventionally this topology graph is derived from routing tables collected by Route Views or RIPE RIS. In this work, we assemble the most complete AS-level topology by extending the conventional method along two dimensions. First, in addition to using data from RouteViews and RIPE RIS, we also collect data from many other sources, including route servers, looking glasses, and routing registries. Second, in addition to using routing tables, we also accumulate topological information from routing updates over time. The resulting topology graph on a recent day contains 44% more links and 3% more nodes than that from using RouteViews routing tables alone. Our data collection and topology generation process have been automated, and we publish the latest topology on the web on a daily basis.
17767601
FRTR: a scalable mechanism for global routing table consistency
This paper presents a scalable mechanism, fast routing table recovery (FRTR), for detecting and correcting route inconsistencies between neighboring BGP routers. The large size of today's global routing table makes the conventional periodic update approach, used by most routing protocols, infeasible. FRTR lets neighboring routers periodically exchange Bloom filter digests of their routing state. The digest exchanges not only enable the detection of potential inconsistencies during normal operations, but also speed up recovery after a BGP session reset. FRTR achieves low bandwidth overhead by using small digests, and it achieves strong consistency by "salting" the digests with random seeds to remove false-positives. Our analysis and simulation results show that, with one round of message exchanges, FRTR can detect and recover over 91% of random errors that the current BGP would have missed with an overhead as low as 1.3% of a full routing table exchange. With salted digests FRTR can detect and recover all the errors with a probability close to 100% after a few rounds of message exchanges.
1040083
Understanding BGP behavior through a study of DoD prefixes
BGP is the de-facto inter-domain routing protocol and it is essential to understand how well BGP performs in the Internet. As a step toward this understanding, this paper studies the routing performance of a sample set of prefixes owned by the USA Department of Defense (DoD). We examine how reliably the sample set is connected to the Internet and how it affects the rest of the Internet. We show that our sample set receives reliable connectivity, with the exception of a few prefixes. We also show that, on average, the sample set has minimal impact on global routing, but certain BGP features used by DoD routers result in periods of excessive routing overhead. During some stressful periods, our sample set, only 0.2% of all prefixes, contributed over 80% of a particular BGP update class. We explain how the BGP design allows certain local changes to propagate globally and amplifies the impact of our sample prefixes.
5219400
Timer Interaction in Route Flap Damping
Route Flap Damping is a mechanism generally used in network routing protocols. Its goal is to limit the global impact of unstable routes by temporarily suppressing routes with rapid changes over short time periods. Although route damping is a clearly defined and simple procedure at each router, its effect in a large network setting is not well understood. We show that the current damping design leads to the intended behavior only under persistent route flapping. When the number of flaps is small, the global routing dynamics deviates significantly from the expected behavior with a longer convergence delay. Previous work observed that a single route flap can falsely trigger route suppression due to path exploration. However our simulations show that this false suppression only accounts for 30% of the convergence delay after a single route flap. Our study reveals previously unknown interactions between reuse timers at different routers. Route suppression and reuse at different routers are triggered at different times and thus affect the number of updates received by other routers. In turn, this impacts other routers' damping behavior. We propose to use Root Cause Notification to eliminate both false suppression and undesirable timer interaction
34947514
A coherent moral relativism
Moral relativism is an attractive position, but also one that it is difficult to formulate. In this paper, we propose an alternative way of formulating moral relativism that locates the relativity of morality in the property that makes moral claims true. Such an approach, we believe, has significant advantages over other possible ways of formulating moral relativism. We conclude by considering a few problems such a position might face.