# Which services sit behind this router? Infrahub Graph Traversal

Every CAB[^/posts/infrahub-graph-traversal/#cab] asks the same question: if this asset goes down tonight, which services do we touch? Too often, the answer lives in the head of one engineer, in a spreadsheet, or in a diagram that was true two years ago. [Infrahub](<https://github.com/opsmill/infrahub>) added Graph Traversal in version 1.10 to answer it from the source of truth itself. I tested it in my lab. It answers in under a second, but it lists the services that are exposed, not the services that break.

Exposure is still worth a lot: it tells you which owners to notify and which services to watch. The post covers two features. Graph Traversal answers the question on demand. A check turns the answer into a rule that runs on every proposed change: here, it blocks any PCI-DSS[^/posts/infrahub-graph-traversal/#pci] service that reaches the backbone without a certified firewall, before the change widens the audit scope.

This post follows [the Infrahub branching deep dive](<https://blog.antoinekh.dev/posts/infrahub-branching-cost/index.md>), which explains how a branch is stored, what it costs, and how a custom check gates a maintenance change. It uses the same lab and the same version.

> [!NOTE]
>
> **Changelog**
>
> - **2026-11-13:** I added a diagram and the queries of [how Path mode finds the paths](<#path-how-two-objects-are-connected>), and a link to the OpsMill reachability demo at the end of [the PCI-DSS rule](<#a-rule-on-paths-pci-dss-services-behind-certified-firewalls>).

## TL;DR

- **The graph makes it possible, Infrahub makes it usable.** Relationships are native in a graph database; Infrahub adds the traversal, the checks, and a branch and a time on every edge.
- **Exposure, not impact.** Graph Traversal lists what is connected to an object, not what breaks. Impact needs a rule that knows your design.
- **You do not write the path.** Give a start object, the target kinds and a max depth: Infrahub finds the paths from the schema, in the UI or in GraphQL, on any branch.
- **The schema decides the answer.** A dependency that is not modeled does not exist for it.
- **Keep the depth tight.** Set it to the length of the path you modeled: each extra hop multiplies the work, rarely the answer.
- **In a check, a path becomes a rule.** A short Python check blocks any PCI-DSS service that reaches a PE without a certified firewall, and shows the faulty path.
- **Built for focused questions.** Answers stop at 200 objects. For a large blast radius, use plain GraphQL.

> [!NOTE]
>
> **The lab: Infrahub 1.11.9**
>
> All tests in this post ran in October 2026 on Infrahub 1.11.9: Community edition, release compose file, Neo4j 2026.05.0 Community, 4 API workers and 2 task workers. Graph Traversal works the same in 1.11.12, the latest release when this post came out.
>
> The lab of the first post: the OpsMill demo data, plus my small BGP backbone schema, `Net`. This post uses the large graph: 152 sites of 2 P routers, 4 PE routers and 1 route reflector (RR), 151k nodes. The [lab README](<https://github.com/antoinekh/labs/tree/master/infrahub_branching>) has the details.

## Four hops from a route reflector to a service

Tonight, `rr-lys-01` goes into maintenance. With my schema, its services are four hops away: the RR, its BGP session, the peer session on the PE, the PE, the service.

[![The Net schema in the Infrahub schema graph: five kinds, their attributes and their relationships](<https://blog.antoinekh.dev/assets/images/infrahub-branching/schema-graph.png>)](<https://blog.antoinekh.dev/assets/images/infrahub-branching/schema-graph.png>)

Infrahub draws the model itself, in the Graph view of the schema. The key is the `peer` relationship: it links the two ends of a BGP session, so a PE finds its route reflectors, and a route reflector finds its PEs. Without it, the question has no answer.

Every PE peers with two route reflectors, its local one and the one of Paris (or Lyon, for the Paris PEs), and carries two services.

> [!NOTE]
>
> **Simplified on purpose**
>
> This model keeps only what the question needs. A real network needs much more, as [the section on modeling](<#the-real-work-model-the-dependencies>) shows.

## Graph Traversal

**Graph Traversal** is under Object Management, Path Traversal. It has two modes, Dependencies and Path, and both run on the branch and at the time selected at the top of the page.

### Dependencies: everything of a kind behind an object

Dependency mode takes a source object and the kinds you care about, and returns every reachable object of those kinds, each with the path that reaches it. I chose the router `rr-lys-01` as source and Application service as target kind:

[![Dependency mode from rr-lys-01: 16 application services behind 8 PEs, one path highlighted](<https://blog.antoinekh.dev/assets/images/infrahub-branching/traversal-dependencies-full.png>)](<https://blog.antoinekh.dev/assets/images/infrahub-branching/traversal-dependencies-full.png>)

16 services, two on each of the 8 PEs that peer with `rr-lys-01`: the four PEs of Lyon, for which it is the local route reflector, and the four PEs of Paris, for which it is the second one.

This is the list a CAB asks for, but none of these services goes down: every PE keeps a second route reflector, so tonight the PEs lose redundancy, not traffic. Graph Traversal cannot see this, because it does not know your redundancy design. Its answer is a list of exposure: the service owners to notify, the services to watch during the maintenance window, the scope of the change. To know what breaks, you need a rule, like the route reflector redundancy check of [the first post](<https://blog.antoinekh.dev/posts/infrahub-branching-cost/index.md#ci-on-a-branch-custom-checks>).

Select a result to highlight its path. The edges carry the relationship names, which shows why an object is in the answer:

[![One path zoomed: Bgp Sessions, Peer, Device, Services](<https://blog.antoinekh.dev/assets/images/infrahub-branching/traversal-dependencies-path.png>)](<https://blog.antoinekh.dev/assets/images/infrahub-branching/traversal-dependencies-path.png>)

The same query exists in GraphQL, so a script or a check can use it:

```graphql
query Impact($source: String!) {
  InfrahubReachableNodes(data: {source_id: $source, target_kinds: ["NetAppService"], max_depth: 5, max_results: 200}) {
    count
    dependencies {
      depth
      node { display_label }
      path { hops { node { kind display_label } } }
    }
  }
}
```

It runs on any branch and at any time, because Infrahub stamps every edge of the graph with its branch and its validity period: you can ask the question on the planned state of a change, before the merge, or on the past.

### How Infrahub finds the dependencies

In a plain GraphQL query, you write the path, so you must already know it. In Dependency mode, you give only a start object, the target kinds and a max depth, and Infrahub finds the dependencies in three steps:

1. **Plan on the schema.** Infrahub keeps every relationship that can lead from the source kind to a target kind within the max depth, except the kinds that you cannot read.
2. **Walk the data.** From the source object, it follows only these relationships, hop by hop, on the selected branch and time.
3. **Return the targets.** Each target comes with its path, up to the max results.

> [!NOTE]
>
> **In the Infrahub code**
>
> The same steps in the Infrahub 1.11.9 source code:
>
> - **Plan:** [`SchemaPlanner._populate_plan`](<https://github.com/opsmill/infrahub/blob/infrahub-v1.11.9/backend/infrahub/graph_traversal/planning/planner.py#L208-L243>) walks the kinds out from the source kind, then back from the target kinds, and keeps a hop only when the full route fits in the max depth. [`_record_hop_if_allowed`](<https://github.com/opsmill/infrahub/blob/infrahub-v1.11.9/backend/infrahub/graph_traversal/planning/planner.py#L282-L311>) leaves out the kinds that you cannot read and the excluded namespaces.
> - **Walk:** [the Cypher query](<https://github.com/opsmill/infrahub/blob/infrahub-v1.11.9/backend/infrahub/graph_traversal/_cypher.py#L851-L880>) has one step per hop. Each step accepts only the planned hops, removes the duplicate objects, and keeps no more than the max results. [`_BRANCH_VISIBLE`](<https://github.com/opsmill/infrahub/blob/infrahub-v1.11.9/backend/infrahub/graph_traversal/_cypher.py#L144-L148>) reads the edges of the branch at the selected time, and the edges of `main` at the time the branch was created.
> - **Results:** [`ReachableNodesExecutor`](<https://github.com/opsmill/infrahub/blob/infrahub-v1.11.9/backend/infrahub/graph_traversal/executor.py#L324-L439>) lists the paths to the targets one depth at a time, the shortest first.

### Path: how two objects are connected

Path mode answers another question: how are these two objects connected? It explains why an object is in an answer, and it tells you whether two objects are connected, which is what the PCI check below needs. Between `pe-par-01` and `pe-lys-01`, it finds three paths of six hops, one through each route reflector that the two PEs share: `rr-lys-01`, `rr-par-01`, and `rr-mrs-01`, the backup added in [the first post](<https://blog.antoinekh.dev/posts/infrahub-branching-cost/index.md#ci-on-a-branch-custom-checks>).

[![Path mode: three paths from pe-par-01 to pe-lys-01, one per shared route reflector, with the search options](<https://blog.antoinekh.dev/assets/images/infrahub-branching/traversal-path-mode.png>)](<https://blog.antoinekh.dev/assets/images/infrahub-branching/traversal-path-mode.png>)

Path mode uses the same plan, but it knows both ends. It has two methods, and the option *Shortest paths only* selects one:

With *Shortest paths only*, the default:

1. **Search from both ends.** Infrahub grows one search from each object, one hop at a time, and records each object once, at its shortest distance. Each search stops at half the depth. A search from one end would go past the route reflectors and spread to every PE before it reaches the other end.
2. **Join in the middle.** A path of *d* hops is split into ⌊*d*/2⌋ hops out of the source and ⌈*d*/2⌉ hops into the destination. The objects at exactly these distances are the middles. One query per depth starts only from them and rebuilds the paths, shortest first.

Without it, as in the PCI check below, Infrahub does not search from both ends. For each depth, it lists every path without a loop of ⌊*d*/2⌋ hops out of the source, then every path of ⌈*d*/2⌉ hops from their end objects into the destination, and joins them in memory. It drops a pair that shares an object, and it stops when the halves become too many; the answer then gives the depth where it stopped.

> [!NOTE]
>
> **The queries behind Path mode**
>
> Each search hop is one query that returns distinct objects, not paths. The join of a tier, the paths of one depth, is the only query that lists paths, and only through the middles. Simplified from [`_cypher.py`](<https://github.com/opsmill/infrahub/blob/infrahub-v1.11.9/backend/infrahub/graph_traversal/_cypher.py#L291-L343>): the conditions in angle brackets stand for the branch, time and plan filters.
>
> One hop of a search ([`_run_bfs_hop`](<https://github.com/opsmill/infrahub/blob/infrahub-v1.11.9/backend/infrahub/graph_traversal/executor.py#L172-L199>)):
>
> ```cypher
> UNWIND $frontier AS fid
> MATCH (a:Node {uuid: fid})-[ri:IS_RELATED]-(rel:Relationship)-[ro:IS_RELATED]-(b:Node)
> WHERE <ri and ro valid on the branch at the selected time>
>   AND [a.kind, rel.name, b.kind] IN $hop_triples
> RETURN collect(DISTINCT b.uuid) AS frontier
> ```
>
> The join of tier 6 ([`_run_shortest`](<https://github.com/opsmill/infrahub/blob/infrahub-v1.11.9/backend/infrahub/graph_traversal/executor.py#L89-L170>)):
>
> ```cypher
> MATCH lpath = (source) ((a)-[:IS_RELATED]-(:Relationship)-[:IS_RELATED]-(b:Node)
>                         WHERE <valid and planned>){3} (mid:Node)
> WHERE mid.uuid IN $tier_middles
> MATCH rpath = (mid) ((c)-[:IS_RELATED]-(:Relationship)-[:IS_RELATED]-(d:Node)
>                      WHERE <valid and planned>){3} (target)
> WITH <hops of lpath> + <hops of rpath> AS hops
> WHERE <no object twice in the path>
> ORDER BY <relationship and UUID of each hop> LIMIT $tier_limit
> RETURN hops
> ```
>
> Without *Shortest paths only*, two queries list the half-paths of each tier ([`_run_exhaustive`](<https://github.com/opsmill/infrahub/blob/infrahub-v1.11.9/backend/infrahub/graph_traversal/executor.py#L201-L284>)), and [`_join_tier`](<https://github.com/opsmill/infrahub/blob/infrahub-v1.11.9/backend/infrahub/graph_traversal/executor.py#L286-L321>) joins them in Python. This method cannot use the search from both ends: that search keeps each object only at its shortest distance, so it misses a path whose middle is farther away. The search stops at the tier where a side has more than 10,000 half-paths.

> [!NOTE]
>
> **Search options**
>
> Both modes share the main options:
>
> | Option | Dependencies | Path |
> | --- | --- | --- |
> | Max depth | 5 by default, 30 at most | 5 by default, 30 at most |
> | Max results (distinct targets) | 50 by default, 200 at most | no |
> | Max paths | 500 by default, 5,000 at most | 10 by default, 100 at most |
> | Kinds to include or exclude | no | yes |
> | Shortest paths only | on by default | on by default |
>
> **Shortest paths only** changes the meaning of the answer: with it, each target comes back with its shortest path only; without it, you get every path without a loop within the depth.
>
> Some namespaces are always excluded: `Core`, `Internal`, `Builtin`, `Lineage`, `Profile` and `Template`, and the IP namespaces unless you include them again. In GraphQL, Path mode can also follow only the relationships that you name in `relationship_filter`, for example `net_bgp_session__peer`.

### Depth is the cost

Every hop multiplies the paths: each object links to many others, and each of those to many more. Infrahub counts each object only once when it looks for the targets, but it must list every path to them. A larger depth also lets more routes into the plan: at depth 5, the route through the physical links is already in it. So the depth decides the work, much more than the size of the answer.

In my tests, the same 16 services came back in under half a second at depth 5, and in 32 to 51 s at depth 8 to 10 on the first run. From another route reflector, the same question at depth 10 did not return at all. Set the max depth to the length of the path that your schema models.

## A rule on paths: PCI-DSS services behind certified firewalls

A [custom check](<https://blog.antoinekh.dev/posts/infrahub-branching-cost/index.md#ci-on-a-branch-custom-checks>), the CI of the first post, runs the traversal again on every proposed change, and blocks the merge when the answer breaks a rule. The Infrahub documentation names three patterns: two objects must stay connected, two objects must never be connected, and everything an object depends on must meet a policy. I built the third one:

> A PCI-DSS service reaches the backbone only through a PCI-DSS certified firewall.

Segmentation keeps the rest of the network out of the PCI-DSS audit scope, and one path that skips the firewall brings it back in. Yet this rule usually lives in a design document and in the memory of the reviewers, so one extra attachment, added in a hurry, breaks it without anyone noticing.

The schema got a `firewall` role and `pci_certified` on the device, and `compliance` on the application service. On `main`, two firewalls hang off `pe-par-01`: `fw-par-01` is certified, `fw-par-02` is not.

For each PCI service, the check asks two traversal questions. First, in Dependency mode: which PEs does the service reach within 5 hops? Then, in Path mode: what are all the paths from the service to each of those PEs? Every path must cross a certified firewall. The check asks for every path, not only the shortest one, because the shortest path can hide a second, longer path that skips the firewall. And when the server cuts a path search short, the check fails: a missing path could be the bypass.

checks/pci\_firewalls.py

```python
from typing import Any

from infrahub_sdk.checks import InfrahubCheck

# Service, firewall, firewall interface, interco, PE interface, PE.
SERVICE_TO_PE_DEPTH = 5


class PciFirewalls(InfrahubCheck):
    query = "pci_services"

    async def validate(self, data: dict[str, Any]) -> None:
        devices = {edge["node"]["id"]: edge["node"] for edge in data["NetDevice"]["edges"]}
        pe_ids = {device_id for device_id, device in devices.items() if device["role"]["value"] == "pe"}
        certified = {
            device_id
            for device_id, device in devices.items()
            if device["role"]["value"] == "firewall" and device["pci_certified"]["value"]
        }
        for edge in data["NetAppService"]["edges"]:
            service = edge["node"]
            reachable = await self.client.reachable_nodes(
                service["id"], ["NetDevice"], max_depth=SERVICE_TO_PE_DEPTH, branch=self.branch_name
            )
            service_name = service["name"]["value"]
            for pe_id in [dependency.node.id for dependency in reachable.dependencies if dependency.node.id in pe_ids]:
                pe_name = devices[pe_id]["name"]["value"]
                # Every path counts: the shortest one alone would hide a longer bypass.
                result = await self.client.traverse_paths(
                    service["id"],
                    pe_id,
                    max_depth=SERVICE_TO_PE_DEPTH,
                    shortest_paths_only=False,
                    branch=self.branch_name,
                )
                # A search cut short by the server may miss the bypass path.
                if result.truncated_at_depth is not None:
                    self.log_error(
                        message=f"{service_name} to {pe_name}: the path search stopped at depth {result.truncated_at_depth}, so the rule cannot be confirmed",
                        object_id=service_name,
                        object_type="NetAppService",
                    )
                for path in result.paths:
                    if any(hop.node.id in certified for hop in path.hops):
                        continue
                    hops = " > ".join(hop.node.display_label for hop in path.hops)
                    self.log_error(
                        message=f"{service_name} reaches {pe_name} without a PCI-DSS certified firewall: {hops}",
                        object_id=service_name,
                        object_type="NetAppService",
                    )
```

> [!NOTE]
>
> **The `pci_services` query**
>
> The check declares `query = "pci_services"`: Infrahub runs this GraphQL query on the branch and passes the result to `validate` as `data`. It returns the PCI services, and the PEs and firewalls with their role and certification.
>
> queries/pci\_services.gql
>
> ```graphql
> query pci_services {
>   NetAppService(compliance__value: "pci_dss") {
>     edges {
>       node {
>         id
>         name { value }
>       }
>     }
>   }
>   NetDevice(role__values: ["pe", "firewall"]) {
>     edges {
>       node {
>         id
>         name { value }
>         role { value }
>         pci_certified { value }
>       }
>     }
>   }
> }
> ```

The scenario: on a branch `pci-onboarding`, I set `svc-pe-par-01-1` to PCI-DSS and attached it to `fw-par-02`, but left its old direct attachment to `pe-par-01`, as a hurried change would. I opened a proposed change, and the check failed on both mistakes:

[![The proposed change: the PCI-DSS check fails with two paths, the other checks pass](<https://blog.antoinekh.dev/assets/images/infrahub-branching/traversal-pci-check-failed.png>)](<https://blog.antoinekh.dev/assets/images/infrahub-branching/traversal-pci-check-failed.png>)

```text
svc-pe-par-01-1 reaches pe-par-01 without a PCI-DSS certified firewall: svc-pe-par-01-1 > pe-par-01
svc-pe-par-01-1 reaches pe-par-01 without a PCI-DSS certified firewall: svc-pe-par-01-1 > fw-par-02 > fw-par-02 eth1 > fw-par-02--pe-par-01 > pe-par-01 1/1/c4 > pe-par-01
```

The first path is the bypass: the service still sits directly on the PE. The second one crosses a firewall, but not a certified one. Each message carries the full path, so the reviewer sees why the rule failed, not only that it failed. The fix, on the same branch: attach the service to `fw-par-01` only. All checks pass, including the route reflector redundancy rule of [the first post](<https://blog.antoinekh.dev/posts/infrahub-branching-cost/index.md#ci-on-a-branch-custom-checks>):

[![After the fix: all checks pass](<https://blog.antoinekh.dev/assets/images/infrahub-branching/traversal-pci-check-passed.png>)](<https://blog.antoinekh.dev/assets/images/infrahub-branching/traversal-pci-check-passed.png>)

This check keeps its rule in Python. OpsMill goes one step further in a [reachability demo](<https://github.com/opsmill/infrahub-demo-reachability-check>) by Iddo Cohen ([video](<https://www.youtube.com/watch?v=guyEHTsqruI>)): the rule is an object of the schema (`TopologyReachabilityRule`), so a team adds a new rule as data on a branch, and the check code does not change.

What I learned on the way:

- **Find the PEs with Dependency mode, list the paths with Path mode.** Dependency mode alone, asked for every path, went past the PE into the BGP sessions of the route reflectors and hit the timeout. Path mode, with a known destination, did not.
- **Import the check before you create the branch.** A check runs from the repository commit of the branch. A branch created before the import keeps the old commit, and runs the old checks until you rebase it.
- **Size the timeout to the queries.** The check sends one traversal query per PCI service, plus one per PE that it reaches, and all of them share the check timeout, 60 s by default. Raise it with the `timeout` attribute of the check class.

## The real work: model the dependencies

Graph Traversal is the easy part. Its answer is only as good as the graph, and a real service chain is much longer than four hops. Four things decide whether you can trust it:

- **The full chain.** A customer service sits on a VRF, access ports, a LAG, a carrier circuit, sometimes two PEs. Each missing relationship is a service that the traversal does not see.
- **Shared risks.** Links in the same duct and routers on the same power feed fail together. If the duct or the feed is not in the graph, no traversal finds it.
- **Fresh data.** Dependencies entered by hand drift after the next change. They must come from the automation that builds the network, or be checked against it; otherwise the answer is wrong, with full confidence.
- **An owner.** Someone decides which kinds exist, which relationships are dependencies, and how deep a question goes.

Start with the question that your change board asks most, model the path that it needs, and grow from there.

## Three limits to know before you rely on it

- **It follows relationships, not meaning.** It does not know that a BGP session carries routes and a physical link does not: a service linked to the router only by physical links comes back as if it depended on it.
- **It ignores attribute values.** Graph Traversal filters on kinds and relationships, not on values: a link in `down` is still a path, and so is a BGP session in `shutdown`. A check can drop these paths itself, because it can read the status of each hop, as [the route reflector check of the first post](<https://blog.antoinekh.dev/posts/infrahub-branching-cost/index.md#the-check>) does: it counts only the `established` sessions.
- **The answer is capped at 200 objects.** For a larger blast radius, use plain GraphQL.

## What I take away

**The graph does the hard part.** In a graph database, a relationship is a stored link, so following a dependency of unknown length is a native step. With NetBox, I answered this question with scripts: a fixed query for a fixed perimeter, written for each case, because in relational tables a path of unknown length is a chain of joins that you must write in advance.

**Infrahub builds the cake on top of it.** Three layers turn the graph into a tool:

- **Graph Traversal** finds the dependencies and the paths from the schema, without a path written in advance.
- **Custom checks** turn a path into a rule that runs on every proposed change, like CI on a merge request.
- **Branch and time on every edge**: Infrahub splits each object into vertices and stamps every edge with its branch and its validity period, as [the first post](<https://blog.antoinekh.dev/posts/infrahub-branching-cost/index.md#vertices-and-edges>) shows. So every question also works on a branch and in the past.

**For the business, this changes how a change is run.** You prepare the change on a branch, you see what it exposes before the merge, and you can see what an asset carried at any time in the past. The list for the CAB comes from the data, not from the memory of the person in the room, and a rule like the PCI-DSS one stops a mistake in review, before it widens the audit scope.

One condition decides all of it: the dependencies you model decide what the traversal can see.

[^/posts/infrahub-graph-traversal/#cab]: Change Advisory Board.

[^/posts/infrahub-graph-traversal/#pci]: Payment Card Industry Data Security Standard: the security standard for the systems that store, process or transmit payment card data.
