The existing Envoy RouteConfiguration must be evaluated linearly and contains match criteria with hard to predict execution time (regular expressions). For scale-up Envoy instances where very large route configurations for a host may be present (let's say O(1m)) or multi-tenant Envoy instances, this becomes problematic.

There are many ways this could be solved:

1. Envoy could optimize based on presented configuration, for example a trie could be recovered from repeated patterns or a specific match order. This is challenging if the existing linear semantics are to be preserved and involves Envoy complexity.
2. We could have variants of regular expressions, e.g. prefix/suffix/glob or RE2 that are cheaper and more predictable to evaluate.
3. We could have a parallel RouteConfiguration with trie-like semantics, where evaluation order is designed for efficiency.

Some combination of (2) and (3) seems likely to yield a clean solution IMHO, but I'm keen to hear from others.

@jmarantz @mattklein123 @dmitri-d @yanavlasov