by Aurélien Lancin and Dimitri Papadimitriou
The expansion of Internet topology, which comprises thousands of Autonomous Systems (AS), has resulted in a number of important research challenges. The Border Gateway Protocol (BGP), which is used to make core routing decisions on the Internet, starts to show its limitations in terms of the number of routing table entries it can store locally, update in a timely fashion and dynamically exchange. Because it is impractical to deploy newly designed routing protocols on the Internet a large-scale, simulation is an unavoidable step to validate their properties. However, the increasing routing information processing (CPU) and storage (memory) introduces similar challenges for the simulation of state-full routing. For this purpose, we introduce DRMSim a Dynamic Routing Model simulator of routing models on large-scale networks.
Today’s Internet routing system relies on the Border Gateway Protocol (BGP). This path-vector routing protocol that matches both technical and economic aspects of Internetwork routing requires storage and timely updates of individual routing states at each node, i.e., it belongs to the class of adaptive stateful routing. The Internet backbone currently consists of more than 45,000 abstract nodes called Autonomous Systems (AS) and about 450,000 nodes called routers (part of the default-free zone). The number of AS increases at a rate ranging from 10 to 15 % per year, but there is no accompanying increase in the average shortest path length. However, as the Internet AS topology grows, the number of relationships between AS of a similar degree (peering or tangential relationships) increases faster than the number of relationships between low-degree to high-degree nodes (customer-provider or radial relationships). In addition, to address prefix de-aggregation practices (for traffic-engineering purposes), this excess of tangential links results in an increase in the number of BGP routing paths even though the network size itself doesn’t increase. As a consequence, BGP shows its objective performance limits in terms of:
- Memory space required to locally store the routing table entries while minimizing the stretch in the routing paths it produces;
- Communication cost and processing of routing table entries (resulting from the dynamics of the routing information exchanges, which in turn delay the routing system convergence time).
For this purpose, the three-year EULER exploratory research project (Grant No.258307), part of the Seventh European Framework Programme, which began in October 2010, aims to explore novel dynamic routing schemes adapted to the Internet’s short-term dynamics (driven by transient topological changes and traffic engineering decisions) and long-term evolution. These dynamic routing schemes are designed to meet the fundamental trade-off between memory space (routing table storage), routing path stretch, and adaptation cost (communication and computational complexity).
In order to validate the functionality and the performance properties of these routing schemes, we have designed and developed an efficient routing model simulator called DRMSim. This simulator comprises the following features and properties:
- Discrete-event routing model simulator developed in Java (running on any Java 1.5 platform or higher);
- Modular design: new topology generators, routing models and performance metrics as well as dynamicity models can be easily added to the simulator;
- Compared with other network simulators, it maintains for every node the local knowledge of the whole network; this technical challenge is addressed by means of efficient data structures.
DRMSim also includes:
- Topology model generators reproducing the properties of the Internet topology (such as Brite, Inet, and GLP);
- The capability to import external topologies (e.g., CAIDA maps);
- A set of standard routing models (such as distance-vector and source routing), compact routing, as well as existing Internet routing schemes such as BGP, allowing researchers to compare the performance of their routing scheme on topologies including up to 16,000 nodes;
- Store and load routing tables to execute simulation from conditions known to the experimenter;
- A metric computation module which automatically computes routing performance metrics such as the routing path stretch, the size of the routing tables, the communication cost (number of routing messages exchanged), etc.
DRMSim is under active development: geometric routing and greedy routing models will soon complement the set of routing models it supports.
Link: http://drmsim.gforge.inria.fr
Please contact:
Aurélien Lancin, Inria and Univ. Nice Sophia Antipolis, CNRS, I3S, UMR 7271, France
E-mail:
Dimitri Papadimitriou, Alcatel-Lucent Bell, Belgium
E-mail:
