Briefing Slides
- CAIRN/DARTnet Collaboration PostScript | PowerPoint | PDF
- DCnet Research Network PostScript | PowerPoint | PDF
Importance of the Problem
Routing instability has always been the most destructive hazard to high survival internetwork services. If a critical network link carrying routing information fails, large portions of the network may be isolated and the entire network may become unstable. Lessons of the early ARPAnet years demonstrated that the design of the routing algorithm itself could contribute to unexpected congestive failures. While modern routing algorithm designs are highly resistive to such failures, there remain significant gaps in understanding the survivability issues when the number of network elements spanned by the routing system becomes very large.
There are a number of available simulators designed for network simulations with relatively small numbers of nodes, from tens to possibly hundreds of nodes. These simulators tend to focus on the detailed interactions between one node or protocol and another, with the remaining nodes acting as routers or generating noise. With very large networks, the interest is on macro behavior and global phenomena and closely watched local behavior is less important than global stability.
Brief Description of Work and Results
In order to explore the behavior of routing functions in very large networks, we have developed a discrete event simulator suitable for network simulations including many thousands of nodes. There are three components which together make up the simulator system. The first is a random topology generator which generates network graphs using a probabilistic algorithm modelled on principles developed by Waxman. Topology generation is an offline process and concluded with a data file that is input to the simulator itself.
The simulator itself uses a conventional deterministic, discrete event model, but with a very large virtual memory to hold the simulation entities and event queue. The simulator is equipped to generate random failures of one or more links or nodes according to a designated probability model. One of our workstations has been expanded to 640 megabytes of RAM, which at the present stage of development supports a network of 3,500 nodes.
The third component of the system is a suite of routing algorithm, including the venerable Bellman-Ford node-state algorithm and the Distance Vector Multicast Routing (DVMRP) Algorithm. The simulator implements these algorithms in the same way as on an actual network, including the effects caused by routing tables changing while the routing updates themselves are travelling between nodes, as well as random failures of the nodes and links and routing packets.
Future Plans
The goal of the project is to provide useful data in networks of the order of 10,000 nodes and perhaps three times this many links. We plan to explore the behavior in response to various kinds of failure models and failure/recovery rates and determine the character of these failures and how they might be predicted and avoided. We plan to explore other routing algorithms as well, in order to conduct comparative studies of the strengths and weaknesses of the selected algorithms within our experimental framework. Finally, we expect to test the algorithms developed for the Autonomous Configuration autoconfigure project using the simulator.
Selected Publications
- Redwinski, R.D. Simulated routing protocol survivability in networked environments. Thesis submitted for the degree of Master of Science, Electrical and Computer Engineering Department, University of Delaware, Spring 1999, 85 pp.
