|dc.description.abstract||Inter-domain routing scalability has always been one of the most challenging issues for the Internet. Recently,
it has raised strong concerns again. One reason is the growth of the Internet itself. In particular, the
practice that customer networks widely use provider independent (PI) addresses and deploy traffic engineering
solutions, is identified as the key reason. In addition, the Internet’s original hierarchical inter-domain topology
structure, which was designed for routing scalability, has evolved into a small world graph. On the other hand,
routing schemes based on routing aggregation cannot scale well on small world graphs, and tunnel-based solutions
relying on the reliable and effective Identifier/Locator mapping dissemination are proved to be un-scalable
either. This calls for other routing solutions that are scalable for the need.
In the literature, compact routing has been developed for a long time with routing scalability as the major
objective. Specifically, it has also been shown very promising in terms of routing scalability. However, this
promising performance of the literature compact routing schemes is for static networks. For dynamic networks,
their performances are not studied. Since most networks are dynamic in nature, due to, e.g., network upgrading,
network failure, and network maintenance, it is hence desired to design routing schemes that are robust and
scalable for such dynamic scenarios.
In this thesis, a totally distributed and scalable compact routing scheme is firstly developed. The study shows
that the developed compact routing scheme still keeps the good scalability in the dynamic network environment.
Then, the distributed compact routing scheme is enhanced by accounting for the nearby scale from topology at
the inter-domain level. The study shows that the enhanced scheme has smaller average routing stretch while
keeping the routing scalability. Thirdly, to gain deeper understanding of compact routing, the routing scalability
and stability of typical compact routing schemes are studied in the context of dynamic networks.
There is an implicit assumption in the Internet routing community: structured address labels are key for
routing scalability and the structured address labels must reflect the network topology to make the routing
algorithms scale well. The thesis finally investigates the validity of this assumption. Specifically, the thesis
formulates the concepts of address label and identifier in a mathematical manner and analyzes their properties
and mutual relations. It is observed that a fine address label is a sequence of address labels with different
granularities plus the identifier. With the logic predicate, the explicit relation between the address label and the
underlying network topology is modeled. It is shown that the total number of routing entries is decided by the
set of binary relation, which is defined by the logic predicate describing the relation between the address label
and the underlying network topologies. That is, the total number of routing entries is equal to the number of
equivalent class of address labels. Based on these, the key components of a routing system are identified and
a simple address label management model is developed. With this model, it is shown that no routing scheme
based on the flat address labels is scalable, i.e., without the proper construction and allocation of address labels
based on the specific network topologies, a routing algorithm with the good routing scalability is unachievable.
In all these studies, simulation has been used. However, for studying the inter-domain routing scalability,
the simulation of large-scale network routing with the business model taken into account imposes is highly
challenging. Currently, the popular BGP simulators are packet level, i.e., they are running on TCP/IP and actual
BGP messages are exchanged over BGP peers. In addition, the simulations with the popular BGP simulator
s are performed on the router level topologies. They demand formidable computing resources for simulating
large-scale networks. To overcome this limitation, various simulation tools have been developed in this thesis
work for the research objective by making a reasonable tradeoff between model accuracy and the interested
|dc.subject||Routing scalability, stability, reliability, dependability, extensibility, routing performance, routing aggregation, IP routing, inter-domain routing, BGP routing, compact routing, address label, identifier, locator, tunnel-based routing, flat label, stochastic routing, routing dynamics, ant-based routing||nb_NO