Useful Metrics for Analyzing Topology Candidates

Emerging high-bandwidth, low-latency network technology has made network-based architectures both feasible and potentially desirable for use in satellite payload architectures. Network architectures are capable of routing large amounts of traffic with reasonable latency, allowing considerable amounts of data between nodes to be shared. However, care must be exercised when developing these types of architectures. Improper network layout, routing algorithms, or other factors can cause undesirable results ranging from minor inefficiencies (i.e., increased power consumption) to catastrophic failure (i.e., loss of data).

Included below are a number of performance, reliability, and cost metrics that could be used to evaluate the topologies to determine suitability against system design constraints. This list is provided as an example and does not include all possible metrics by which topologies can be analyzed.

For more information, please refer to Sandia Report SAND2008-0069, Network Topology Analysis, David S. Lee and Jeffrey L. Kalb, 2008.

• Average Path Length: The average distance between two nodes in the network over all pairs of distinct nodes. Average path length is one of the most important factors when optimizing networks for speed and efficiency. Short average path lengths ensure that messages do not have to travel far to their destination and thus do not remain in the network for long periods of time. Short average path lengths decrease overall network utilization and reduce message latency.

• Diameter: The longest path in the network between two nodes. The diameter of a network is found by recording the shortest paths between all pairs of distinct nodes, and taking the maximum of this set.

• Node Degree: The degree of a node is equal to the number of links to which that node is connected.

• Number of Links: Increasing the number of links can potentially reduce latency, average path length, network congestion, and increase overall performance, but more links can increase cost and complexity of network wiring and routing due to increased node degree. Optimizing the number of links requires balancing the trade-off between high performance and redundancy vs. lower cost, power, and less inter-node links.

• Worst-case Connectivity: This is the minimum number of nodes that must fail (node connectivity κ(x)) or the minimum number of links that must fail (edge connectivity λ(x)) to cause any additional type of failure in the system. An example of a failure in this case would be the inability for any live node to communicate with any other presently live node due to, say, node failures of all a live node’s neighbors.

• Algebraic Connectivity: Algebraic connectivity is a metric derived from mathematical graph theory. Being “well-connected” implies good average path lengths as well as an abundance of loops to ensure good reliability and overall connectivity. Thus, graphs with high algebraic connectivity generally indicate efficient placement of links with many redundant paths between nodes, as well as good distribution of traffic (depending on the routing algorithm used).

• Scalability: The ease in which the number of nodes within a network may be changed. A high scalability is desired. Some topologies require a fixed number of nodes in a specific structure to operate; others may allow an arbitrary number of nodes. This is purely dependent on the topology chosen for use in the network.

• Routing Complexity: The complexity of routing algorithms must be considered, especially when in environments where the routing table must be dynamically generated due to node or link failure.

• Bottlenecks or Points-of-Failure: The presence of bottlenecks can introduce a slew of other problems, including potential for network overload (causing packet delays or drops), increased latency, and the introduction of certain nodes or links becoming critical points-of-failure. Networks with short average path lengths may lose the advantage of their short transmission distances if bottlenecks exist, restricting traffic flow between nodes. Note that bottlenecks may exist as either nodes or links.