Graph Embedding Techniques in Communication Networks

OData support
Supervisor:
Dr. Heszberger Zalán Tamás
Department of Telecommunications and Media Informatics

The Internet is the network of networks. Nowadays, there are more than 2.4 billion users of the Internet and the number of devices connected to the Internet are 12.5 billion, and these numbers are rising dramatically. The research projects are talking about sensor networks, which are spread all over the world, increasing the size of the Internet, which basically needs new routing solutions. Today there are already several problems with the routing functions, the IP address space is already empty and the size of the routing tables are growing exponentially. Fundamentally new solutions are needed because the current system is not going to be sustainable for a long time.

During the embedding of a graph, the network topology mapped to handy address space, which means that virtual coordinates assigned to the vertices. This is a very useful tool, which has low memory requirement and it is able to resolve routing issues efficiently for general, large-scale networks: during a greedy embedding, we assign virtual coordinates to the nodes assuring that for every path between any two nodes, there is always a node closer to the destination than the actual node, so we always know where to forward the packet.

The first task of this thesis is to review the existing metric space embedding techniques and their usability for real Internet-like graphs. The second task is to create a suitable (has important properties for routing) model of the Internet's domain-level graph and describe an embedding of this model; finally analyze the embedding's advantages and disadvantages.

Downloads

Please sign in to download the files of this thesis.