This is meant to document our discussion on this topic.

Edit: The proposed changes at the bottom of this post have been implemented, and this post no longer describes the current graph behaviour in Shadow.

Shadow has two modes of deriving latencies from network graphs. At the time of writing, these are:

1. If network.use_shortest_path is false, shadow will simply look up the latency in the graph. This requires the graph to be complete; all pairs of nodes must have an edge with non-zero latency. This includes self-loops, so for a node X there must also be an edge from X to X, which will be used if two hosts on the same node are communicating.

2. If network.use_shortest_path is true (the default), shadow will compute the shortest path latency between nodes in the graph. This works fine for computing the latency between two hosts on different nodes, but becomes an issue when two hosts on the same node are communicating. In this case, the shortest path from node X to node X will be 0. Since Shadow does not support latencies of 0, and in reality there should be a non-zero latency between any hosts even if they belong to the same node, Shadow needs a way to choose a non-zero latency for the communication between these nodes. To do this, Shadow currently computes the shortest path from node X to node X that includes at least one edge. This guarantees that Shadow has a non-zero latency for the path, but this behaviour may be unintuitive. For example, consider the following directed ring graph:

          ┌───┐
     ┌───►│ A ├────┐
     │    └───┘    ▼
   ┌─┴─┐         ┌───┐
   │ E │         │ B │
   └───┘         └──┬┘
    ▲               │
    │ ┌───┐   ┌───┐ │
    └─┤ D │◄──┤ C │◄┘
      └───┘   └───┘
   

   If two hosts on node A are communicating, shadow will use the latency (A->B) + (B->C) + (C->D) + (D->E) + (E->A) as it is the shortest (and only) path from A to A with at least one edge. This would be unintuitive if the user assumes that hosts on the same node would be near each other and have a relatively low latency. This can be fixed by specifying self-loops:

              ┌─┐
              │ ▼
             ┌┴──┐
        ┌───►│ A ├────┐
        │    └───┘    ▼
   ┌─►┌─┴─┐         ┌───┬──┐
   │  │ E │         │ B │  │
   └──┴───┘         └──┬┘◄─┘
       ▲               │
       │ ┌───┐   ┌───┐ │
       └─┤ D │◄──┤ C │◄┘
         └──┬┘   └──┬┘
          ▲ │     ▲ │
          └─┘     └─┘
   

   With self-loops, Shadow will include this self-loop in its shortest path calculation.

To avoid the confusing behaviour in the second case (when network.use_shortest_path is true), we plan on requiring self-loops for all nodes. This requires the user to explicitly specify a latency for communication between two hosts on the same graph node. We will also always use this self-loop latency for communication between hosts on the same node, and we will not compute the shortest path in this case.