Back to 'the problem'

The original problem, illustrated (again)

The following figure illustrates the challenge described in the preamble section of this article, on the formalized graph described in the immediately preceding pages. As previously discussed, in this model, each node on the graph represents a BGP router, and each edge represents an eBGP peering between two nodes (as well as a viable data-plane forwarding path).

The new additions to this figure are the path-tracings between nodes labeled “S0.1 Z0.1” and “S0.0 Z0.3”.

“Sn.m” signifies an index value in the “site” hierarchy (“S”). “n” indicates the number of parent/child relationships between the node and the root of the “site” hierarchy (which is equivalent to number of edges between it and the root of the site-tree.)

“Zn.m” signifies and index value in the “zone” hierarchy (“S”). “n” indicates the number of parent/child relationships between the node and the root of the “zone” hierarchy (which is equivalent to number of edges between it and the root of the zone-tree.)

Paths on the graph; paths on a network

In the preceding figure, three paths have been high-lighted between nodes “S0.1-Z0.1” and “S0.3-Z0.3”. These are the three “shortest” paths between those two nodes, and they are all equally short. On our graph, we count the number of edges (6) in the path to determine the “length” of that path. This represents the AS-path length of the corresponding path in the “real” networks that we are modeling.

As with the scenario in the preamble of this paper, the challenge we have set ourselves is to develop a path selection algorithm from which:

The source/destination-inverted flows of a flow-pair between two nodes with differing zone and site values will traverse the same set of stateful nodes as each other.

An important refinement of this problem statement is to qualify it with the following:

The path selection algorithm must:

• Execute on each node, selecting the the next edge in the path
  • Using only the following inputs:
    • Topology data it has received through BGP advertisements
    • Static local configuration/variables
    • The destination/end-point node’s “network name”
      • The source/start-point node’s “network-name” may not be used

In other words, it has to “act like a routing protocol” (and no source-based routing is allowed.)

But, what kind of routing protocol?

The scenario discussed in the preamble involved an enterprise network using eBGP, and that is the the scenario that our path-selection algorithm will build on, and that we describe here in terms of assumptions about the behavior of nodes on our graph:

• Each node has a unique identifier (we’ll call it a “network name” for now)
• Each node sends/receives messages from the nodes that it shares edges with.
  • The messages are functionally analagous to BGP UPDATE messages
    • The “network name” parameter acts as both ASN, router-ID, and network.
    • Node “1” sends an update of “1” to node 2
    • Node “2” receives the update, and adds an entry to its forwarding table (
      • Reach “1” via the edge I just received the update on (the edge between “1” and “2” on the graph)
    • Node “2” prepends that same update with its own “network name” and a space (“2 1”) and sends it to nodes 5,6,7
  • The behavior of the nodes is equivalent to that of an eBGP peer

The graph in the following figure modifies the previous figure by removing the previous explicit textual annotations for site, and zone properties and adding a “network name” value to each node. The previously discussed properties of the nodes and edges are depicted visually (refer to the key to the left of the graph in the figure.)

We’ve changed the labels on our graph, but the previously identified 3 “equidistant” paths between two nodes in different “sites” and “zones” still applies. Those paths are between nodes now labeled as “14” and “22”.

Comparing the paths

The three equi-distant paths between nodes 14 and 22 are compared below.

Path “a”

• Traverses two stateful nodes
  • 11 (zone 0.1), and 13 (zone 0.3)
    • Both in the same “site” as 22 (but not the same site as 14)

Path “b”

• Traverses two stateful nodes
  • 5 (zone 0.1), and 7 (zone 0.3)
    • Both in the same “site” as 14 (but not the same site as 22)

Path “c”

• Traverses two stateful nodes
  • 5 (zone 0.1), and 13 (zone 0.3)
    • 5 is in the same site as 14 (but not the same site as 22)
    • 13 is in the same site as 22 (but not the same site as 14)

Restating the problem (again)

We need a forwarding-decision process that can execute on each node of the graph and which results in the src/dst-inverted flow-pairs for any two hosts traversing the same set of stateful nodes. In this particular instance of that problem, that boils down to we need to choose path “A”, “B”, or “C” (consistently) for both the 14 -> 22 path and the 22 -> 14 path.