Question

Let \(A\) be the number of autonomous systems on the Internet, and let \(D\) (for diameter) be the maximum AS path length. (a) Give a connectivity model for which \(D\) is of order \(\log A\) and another for which \(D\) is of order \(\sqrt{A}\). (b) Assuming each AS number is 2 bytes and each network number is 4 bytes, give an estimate for the amount of data a BGP speaker must receive to keep track of the AS path to every network. Express your answer in terms of \(A, D\), and the number of networks \(N\).

Short answer

For \(D = \log A\), use a scale-free model. For \(D = \sqrt{A}\), use a grid network. The BGP speaker data requirement is \(N(2D + 4)\) bytes.

Step-by-step solution

Understanding the Problem

Given the number of autonomous systems (AS) denoted as \(A\) and the maximum AS path length (diameter) denoted as \(D\), we need to provide connectivity models for specific orders of \(D\). Additionally, we need to estimate the amount of data a BGP speaker must receive to keep track of the AS path to every network, given certain data assumptions.

Model with Diameter of Order \(\log A\)

A common model for which \(D\) (diameter) is of order \(\log A\) is a scale-free network (or small-world network), where the number of network hops needed to connect any two autonomous systems grows logarithmically with the size of the network. This type of network is characterized by the presence of hub nodes, which greatly reduce the path length between nodes.

Model with Diameter of Order \(\sqrt{A}\)

For a model where \(D\) is of order \(\sqrt{A}\), we can consider a grid network or a two-dimensional lattice. In such a network, the distance between nodes scales as the square root of the number of nodes, which is a characteristic property of such structures.

Data Estimate - Determine the Size of Information Per AS Path

Each AS number is 2 bytes and each network number is 4 bytes. The AS path to each network would consist of data for each of the \(D\) hops. Since the AS path includes AS numbers for each of the \(D\) hops and each network number, the size of information per AS path is \(2D + 4\) bytes.

Data Estimate - Compute the Total Data Size

The BGP speaker needs to keep track of the AS path to each of the \(N\) networks. Hence, the total amount of data is given by the product of the size of information per AS path and the number of networks, i.e., \(N(2D + 4)\) bytes.

Final Expression of the Estimate

Combine the results from previous steps. The total amount of data a BGP speaker must receive is \(N(2D + 4)\) bytes, where \(N\) is the number of networks, \(D\) is the diameter of the autonomous system network, and each network number and AS number occupy 4 and 2 bytes respectively.

Key concepts

BGP speaker data requirements

Border Gateway Protocol (BGP) is responsible for routing decisions in the internet by sharing information between different autonomous systems (ASes). A BGP speaker is an entity using BGP to exchange routing information with other BGP speakers.
When it comes to data requirements, every BGP speaker needs to keep track of the AS path to every network. Each Autonomous System (AS) number is 2 bytes, and each network number is 4 bytes. The overall data requirement for a BGP speaker is determined by the total number of networks, denoted as \(N\), and the maximum AS path length, denoted as \(D\). To calculate the total data requirement, consider that each AS path involves data for \(D\) hops with additional network specifications.
The size of information per AS path is \(2D + 4\) bytes. Therefore, the total amount of data a BGP speaker must receive can be represented by \(N(2D + 4)\) bytes. This calculation ensures that the BGP speaker has all the necessary data to maintain accurate routing information across the network.

AS path length models

AS path length models help determine the diameter \(D\), which is the maximum path length in terms of the number of AS hops between any two points in the network.
For instance, a scale-free network, or a small-world network, can model a situation where the number of network hops (diameter) grows logarithmically with the number of autonomous systems, \(A\). This means that \(D\) is roughly proportional to \(\log A\). Such networks are characterized by hub nodes that facilitate short paths between any two nodes.
Alternatively, a grid network model can show a scenario where \(D\) grows as the square root of the number of autonomous systems, \(\sqrt{A}\). This represents a network laid out in a two-dimensional lattice, where the distance between points expands more gradually compared to logarithmic growth.
Understanding these models assists network engineers in predicting how the AS path length will scale with the network's growth, crucial for ensuring efficient routing and scalability.

Network scalability

Network scalability refers to the ability of a network to handle growth in terms of nodes, connections, and traffic volume without detrimental performance impacts. In the context of computer networks, ensuring that the routing infrastructure scales efficiently is crucial.
Scalability is deeply influenced by the AS path length and the overall architecture of the network. If AS path lengths grow too quickly, it can lead to inefficiencies and excessive routing overhead. Hence, using models like the scale-free network, where the path length grows logarithmically, can significantly aid in maintaining scalable architectures.
Additionally, maintaining a minimal data requirement is essential for scalability. With exponential growth in the number of networks and autonomous systems, keeping the data overhead low ensures that BGP speakers can function efficiently without being overwhelmed. The formula \(N(2D + 4)\) bytes for data requirements illustrates the importance of controlling both the number of networks \(N\) and the AS path length \(D\).
By carefully considering these aspects, network designers can create scalable systems that support growth without sacrificing performance or reliability.