What is a valley-free violation in BGP?

Valley-free violation refers to a violation of a valley-free path in BGP routing, particularly in the context of AS path (Autonomous System path) advertisements.

To explain this concept clearly, let’s first break down the terms:

Valley-Free Path in BGP

BGP uses the AS path to record the sequence of Autonomous Systems (ASes) that a route has traversed. When an AS advertises a route to its BGP neighbors, it includes its AS number in the AS path attribute. A valley-free path is one where the AS path doesn't go backward or "valley" in the sequence. Specifically, it means that once an AS appears in the AS path, it should not appear again later in the path as it would imply that the route has passed through the same AS multiple times (which typically isn't desirable).

For example:

If AS1 advertises a route to AS2, the AS path might look like this:

• AS path: AS1, AS3, AS5

If AS5 then advertises the same route back to AS1, it would be a valley-free violation because the route has now gone back to an earlier AS in the sequence:

• Violation: AS path: AS5, AS3, AS1 — this is a valley-free violation because the path "valleys" back to AS1, which violates the principle that ASes should only advertise paths in one direction.

Valley-Free Path and Routing Loops

A valley-free path helps prevent routing loops in BGP. A routing loop occurs when data packets circulate endlessly between a set of ASes, without ever reaching their destination. If an AS were to advertise a route that passes through it more than once, it could indicate the possibility of a loop, which is problematic for efficient and stable routing.

In short:

• Valley-Free Path: A route that does not revisit an AS after it has already passed through it.
• Valley-Free Violation: When an AS path contains a cycle or revisits a previous AS, violating the valley-free property.

BGP Path Selection

BGP is designed to select the best route based on various factors, including AS path length and the valley-free principle. A valley-free violation can create suboptimal routing, as it suggests a loop or circular dependency that could lead to inefficient routing and possible instability.

Why is this important?

• Stability: Valley-free paths help maintain network stability by avoiding loops or incorrect routing updates.
• Efficiency: Ensuring a valley-free path helps optimize the routing process, reducing the chance of routing loops and ensuring that data reaches its destination without unnecessary detours.

In essence, a valley-free violation in BGP would indicate that a routing update has re-entered an AS that has already been traversed, which is undesirable and can cause issues in maintaining loop-free and efficient routing.