Internet Topology
Encyclopedia
Internet topology deals with finding the topological
structure of the Internet
. It is daunting to map the entire hierarchy due to the rate at which the network
is growing. The effort to map the Internet
is usually incomplete and out of date the moment it appears. Internet
topology
has attracted interest from various disciplines including mathematical sciences
, computer science
and physics
.
The networking
researcher's
motivation
for studying Internet
-specific topologies
is to enable prediction of how new technologies, policies, or economic conditions will impact the Internet’s
connectivity structure at different layers, whereas a physicist
is interested in studying the Internet
as any other complex network. This has led to many models being proposed including the Jellyfish and Bow Tie models to physically represent the structure of the Internet
.
web pages that form a clique
; that is, a web page exists in this core if and only if it connects to every other page in it. From there, a distinction is made between pages of single degree and those of higher order degree. Pages with many links form rings around the center, with all such pages that are a single link away from the core making up the first ring, all such pages that are two links away from the core making up the second ring, and so on. Then from each ring, pages of single degree are depicted as hanging downward, with a page linked by the core hanging from the center, for example. In this manner, the rings form a sort of dome away from the center that is reminiscent of a jellyfish, with the hanging nodes making up the creature's tentacles. More info on Jellyfish Concept and Image can be found on the following Web Page:
http://www.mundi.net/maps/maps_020/
pages such that there is a path from any page within the core to any other page. In other words, starting from any node within the core, it is possible to visit any other node in the core just by clicking hyperlinks. There are then two other large groups, roughly of equal size. One consists of all pages that link to the strongly connected core, but which have no links from the core back out to them. This is the "Origination" or "In" group, as it contains links that lead into the core when originating from it. The counterpart to this is the group of all pages that the strongly connected core links to, but which have no links back into the core. This is the "Termination" or "Out" group, as it contains links that lead out of the core and terminate from it. The fourth and final group is all other disconnected pages, which neither link to the core nor are linked from it.
A more comprehensive representation of the Bow Tie model has been presented with additional, smaller groups of web pages. In this version, both the "In" and "Out" groups have smaller "tendrils" leading to and from them. These consist of pages that link to and from the "In" and "Out" group but are not part of either to begin with, in essence the "Origination" and "Termination" groups of the larger "In" and "Out". This can be carried on ad nauseam, adding tendrils to the tendrils, and so on. Additionally, this more detailed version contains another important group known as the "Tubes". This group consists of pages accessible from "In" and which link to "Out", but which are not part of the large core. Visually, they form alternative routes from "In" to "Out", like tubes bending around the central strongly connected component.
Topology
Topology is a major area of mathematics concerned with properties that are preserved under continuous deformations of objects, such as deformations that involve stretching, but no tearing or gluing...
structure of the Internet
Internet
The Internet is a global system of interconnected computer networks that use the standard Internet protocol suite to serve billions of users worldwide...
. It is daunting to map the entire hierarchy due to the rate at which the network
Computer network
A computer network, often simply referred to as a network, is a collection of hardware components and computers interconnected by communication channels that allow sharing of resources and information....
is growing. The effort to map the Internet
Internet
The Internet is a global system of interconnected computer networks that use the standard Internet protocol suite to serve billions of users worldwide...
is usually incomplete and out of date the moment it appears. Internet
Internet
The Internet is a global system of interconnected computer networks that use the standard Internet protocol suite to serve billions of users worldwide...
topology
Topology
Topology is a major area of mathematics concerned with properties that are preserved under continuous deformations of objects, such as deformations that involve stretching, but no tearing or gluing...
has attracted interest from various disciplines including mathematical sciences
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
and physics
Physics
Physics is a natural science that involves the study of matter and its motion through spacetime, along with related concepts such as energy and force. More broadly, it is the general analysis of nature, conducted in order to understand how the universe behaves.Physics is one of the oldest academic...
.
The networking
Computer network
A computer network, often simply referred to as a network, is a collection of hardware components and computers interconnected by communication channels that allow sharing of resources and information....
researcher's
Researcher
A researcher is somebody who performs research, the search for knowledge or in general any systematic investigation to establish facts. Researchers can work in academic, industrial, government, or private institutions.-Examples of research institutions:...
motivation
Motivation
Motivation is the driving force by which humans achieve their goals. Motivation is said to be intrinsic or extrinsic. The term is generally used for humans but it can also be used to describe the causes for animal behavior as well. This article refers to human motivation...
for studying Internet
Internet
The Internet is a global system of interconnected computer networks that use the standard Internet protocol suite to serve billions of users worldwide...
-specific topologies
Topology
Topology is a major area of mathematics concerned with properties that are preserved under continuous deformations of objects, such as deformations that involve stretching, but no tearing or gluing...
is to enable prediction of how new technologies, policies, or economic conditions will impact the Internet’s
Internet
The Internet is a global system of interconnected computer networks that use the standard Internet protocol suite to serve billions of users worldwide...
connectivity structure at different layers, whereas a physicist
Physicist
A physicist is a scientist who studies or practices physics. Physicists study a wide range of physical phenomena in many branches of physics spanning all length scales: from sub-atomic particles of which all ordinary matter is made to the behavior of the material Universe as a whole...
is interested in studying the Internet
Internet
The Internet is a global system of interconnected computer networks that use the standard Internet protocol suite to serve billions of users worldwide...
as any other complex network. This has led to many models being proposed including the Jellyfish and Bow Tie models to physically represent the structure of the Internet
Internet
The Internet is a global system of interconnected computer networks that use the standard Internet protocol suite to serve billions of users worldwide...
.
Internet Architecture
Internet Architecture is organized into several planes. The data plane represents how data is actually forwarded between routers. Topologies based on the data plane reflect physical nodes and connections but these topology graphs are hard to create and harder to validate for correctness or completeness. The control plane represents how ISP's create and configure organizational routing policy. While the data plane is responsible for forwarding data based on policy, the control plane is responsible for configuring policy. As far as topology is concerned, nodes in this plane are autonomous systems, (AS) and links between nodes represent some type of relationship. There are two types of relationships. Customer-Provider links involve one AS providing Internet access to a smaller AS at a monetary cost. Peering links are agreements between two AS networks to exchange certain types of traffic free of charge. These types of Internet topologies have become a hot area of research in academia. There is a third less known plane called the management plane but the topology maps it produces are incredibly inaccurate since its data can be directly modified by network operators with no effects on routing dynamics.Jellyfish Model
The simplistic Jellyfish model of the Internet centers around a large core of high-degreeDegree (graph theory)
In graph theory, the degree of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice. The degree of a vertex v is denoted \deg. The maximum degree of a graph G, denoted by Δ, and the minimum degree of a graph, denoted by δ, are the maximum and minimum degree...
web pages that form a clique
Clique (graph theory)
In the mathematical area of graph theory, a clique in an undirected graph is a subset of its vertices such that every two vertices in the subset are connected by an edge. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs...
; that is, a web page exists in this core if and only if it connects to every other page in it. From there, a distinction is made between pages of single degree and those of higher order degree. Pages with many links form rings around the center, with all such pages that are a single link away from the core making up the first ring, all such pages that are two links away from the core making up the second ring, and so on. Then from each ring, pages of single degree are depicted as hanging downward, with a page linked by the core hanging from the center, for example. In this manner, the rings form a sort of dome away from the center that is reminiscent of a jellyfish, with the hanging nodes making up the creature's tentacles. More info on Jellyfish Concept and Image can be found on the following Web Page:
http://www.mundi.net/maps/maps_020/
Bow Tie Model
The most common Bow Tie model consists of four main groups of web pages. Like with the Jellyfish model, the first is a core of strongly connectedStrongly connected component
A directed graph is called strongly connected if there is a path from each vertex in the graph to every other vertex. In particular, this means paths in each direction; a path from a to b and also a path from b to a....
pages such that there is a path from any page within the core to any other page. In other words, starting from any node within the core, it is possible to visit any other node in the core just by clicking hyperlinks. There are then two other large groups, roughly of equal size. One consists of all pages that link to the strongly connected core, but which have no links from the core back out to them. This is the "Origination" or "In" group, as it contains links that lead into the core when originating from it. The counterpart to this is the group of all pages that the strongly connected core links to, but which have no links back into the core. This is the "Termination" or "Out" group, as it contains links that lead out of the core and terminate from it. The fourth and final group is all other disconnected pages, which neither link to the core nor are linked from it.
A more comprehensive representation of the Bow Tie model has been presented with additional, smaller groups of web pages. In this version, both the "In" and "Out" groups have smaller "tendrils" leading to and from them. These consist of pages that link to and from the "In" and "Out" group but are not part of either to begin with, in essence the "Origination" and "Termination" groups of the larger "In" and "Out". This can be carried on ad nauseam, adding tendrils to the tendrils, and so on. Additionally, this more detailed version contains another important group known as the "Tubes". This group consists of pages accessible from "In" and which link to "Out", but which are not part of the large core. Visually, they form alternative routes from "In" to "Out", like tubes bending around the central strongly connected component.
External links
- Internet Topology Mapping Tools developed by M. Engin Tozal at UT-Dallas
- [ftp://ftp.caida.org/publications/papers/2006/wit/wit.pdf The Workshop on Internet Topology (WIT) Report]
- Perl program that generates synthetic Internet-like topologies
- Computing the unmeasured: An algebraic approach to Internet mapping