# Metric mean dimension, Hölder regularity and Assouad spectrum

Alexandre Baraviera  Instituto de Matemática e Estatística - UFRGS, Av. Bento
Gonçalves, 9500 - Agronomia, Porto Alegre - RS, 91509-900, Brasil
<EMAIL_ADDRESS>,  Maria Carvalho  CMUP & Departamento de Matemática,
Faculdade de Ciências da Universidade do Porto, Rua do Campo Alegre 687,
Porto, Portugal<EMAIL_ADDRESS>and  Gustavo Pessil  CMUP & Departamento
de Matemática, Faculdade de Ciências da Universidade do Porto, Rua do Campo
Alegre 687, Porto, Portugal<EMAIL_ADDRESS>
###### Abstract.

Metric mean dimension is a geometric invariant of dynamical systems with
infinite topological entropy. We relate this concept with the fractal
structure of the phase space and the Hölder regularity of the map. Afterwards
we improve our general estimates in a family of interval maps by computing the
metric mean dimension in a way similar to the Misiurewicz formula for the
entropy, which in particular shows that our bounds are sharp. Of independent
interest, we develop a dynamical analogue of Minkowski-Bouligand dimension for
maps acting on Ahlfors regular spaces.

###### Key words and phrases:

Metric mean dimension; Hölder regularity; Assouad spectrum; Ahlfors regularity

###### 2010 Mathematics Subject Classification:

Primary: 26A16, 28A80, 28D20, 54F45.

###### Contents

  1. 1 Introduction
    1. 1.1 Hölder regularity
    2. 1.2 Horseshoes in the interval
  2. 2 Preliminaries
    1. 2.1 Metric mean dimension
    2. 2.2 Other fractal dimensions
  3. 3 Subshifts of compact type
    1. 3.1 Spectral radius bounds
  4. 4 Ahlfors regular spaces
    1. 4.1 Minkowski–Bouligand dimension
    2. 4.2 Subshifts on Ahlfors alphabets
    3. 4.3 Proof of Theorem 4.3
  5. 5 Proof of Theorem A
  6. 6 Proof of Theorem B
  7. 7 Open questions
  8. 8 Acknowledgments

##  1\. Introduction

Since the introduction of the metric mean dimension by E. Lindenstrauss and B.
Weiss in [17], researchers have endeavored in finding connections between this
notion and other features of dynamical systems with infinite topological
entropy. In this article, we investigate about the interplay between the
metric mean dimension, the geometry of the underlying space and the regularity
of the map.

In [13], P. Hazard presented a family of Hölder continuous interval maps with
infinite entropy. Thus, it is worthwhile studying the metric mean dimension
within this family, and we wonder if and how it is related to the Hölder
exponents of the maps. We answer positively to this question for a
$2-$parameter family of interval maps, which comprises Hazard’s examples (see
Subsection 1.2 and Theorem B). The core of proof of this result is a formula
for the metric mean dimension in terms of a sequence of horseshoes and the
scales at which their dynamics can be detected, resembling Misiurewicz formula
for the entropy (cf. [19]). We deduce this formula by developing a dynamical
analogue of the Minkowski-Bouligand dimension on Ahlfors regular spaces (see
Section 4).

Taking into account that the metric mean dimension has both a dynamical and a
geometrical imprint, in a more general framework, where the phase space is not
as homogeneous as the interval, we need to deal with more refined geometric
structure, which may not be detected if one chooses an unfit notion of
dimension. It turns out that the more recent concept of Assouad spectrum (cf.
[11]) captures in a precise way the impact of the Hölder regularity on the
metric mean dimension (see Subsection 2.2 and Theorem A). The adequacy of the
Assouad spectrum in this setting is envinced by (7) and the local nature of
the metric mean dimension, as pointed out by M. Tsukamoto in [22, Theorem
1.1]. The essence of our approach is the application of [20, Theorem B and
Lemma 6.1] which provide bounds for the metric mean dimension in terms of the
spectral radii of matrices whose entries are ruled by the Hölder regularity of
the map.

In the next subsections, we will describe in detail our mathematical
contribution and discuss some examples. After a brief glossary with the main
definitions and preliminary information, we present the proofs. We end the
paper raising a few open questions suggested by this work.

###  1.1. Hölder regularity

Let $(X,d)$ be a compact metric space and $T\colon X\to X$ be a continuous
map. We say that $T$ is _Lipschitz_ if there is some $C>0$ such that

$d(T(x),T(y))\,\leq\,C\,d(x,y)\qquad\forall\,x,y\,\in\,X.$

It is known that the topological entropy of a Lipschitz map $T$ has a natural
upper bound in terms of the Lipschitz constant and the dimension of the phase
space (cf. [14, Theorem 3.2.9]), namely

$h_{top}(T)\,\leq\,\max\,\\{0,\log C\\}\,\overline{\dim}_{B}(X,d).$ (1)

However, if one is interested in maps satisfying weaker forms of regularity,
the phenomenon of infinite entropy may occur. Given $\alpha\in(0,1)$, we say
that $T$ is _$\alpha-$ Hölder_ if there exists a constant $C_{\alpha}>0$ such
that

$d(T(x),T(y))\,\leq\,C_{\alpha}\,d(x,y)^{\alpha}\qquad\forall\,x,y\,\in\,X.$

We sometimes refer to $\alpha$ as the _Hölder exponent of $T$._ Hazard (cf.
[13]) presented a family of interval endomorphisms with infinite topological
entropy which are Hölder continuous. This indicates that metric mean dimension
can be a useful tool to study such systems. We refer the reader to Subsection
1.2, where we discuss this type of maps.

The following result is an analogue of (1) for the metric mean dimension on
spaces with finite Assouad dimension. See the precise definitions in Section
2.

######  Theorem A.

Let $(X,d)$ be a compact metric space with finite Assouad dimension. If
$\alpha\,\in\,(0,1)$ and $T\colon X\to X$ is $\alpha-$Hölder, then

$\overline{\mathrm{mdim}}_{M}(X,d,T)\,\leq\,(1-\alpha)\dim_{A}^{\alpha}(X,d).$

If, in addition, $\dim_{A}(X,d)\,>\,0$ then

$\sup\,\\{\alpha\in(0,1)\,:\,T\text{ is
}\alpha-\text{H\"{o}lder}\\}\,\leq\,1\,-\,\frac{\overline{\mathrm{mdim}}_{M}(X,d,T)}{\dim_{A}(X,d)}.$

The previous inequalities are sharp: we refer the reader to Subsection 1.2,
where we present a family of examples for which the equalities are attained.
Theorem A answers positively the questions raised at the end of [1].

Recall that, if a compact metric space admits a Lipschitz map with infinite
entropy, then by (1) its box dimension is necessarily infinite. Taking into
account the connection (8) between the box dimension and the Assouad spectrum,
we deduce from Theorem A that the existence of a Hölder endomorphism with full
metric mean dimension also imposes constraints on the fractal structure of the
underlying space.

######  Corollary A.

Let $(X,d)$ be a compact metric space with finite Assouad dimension and
$T\colon X\to X$ be a continuous map such that
$\overline{\mathrm{mdim}}_{M}(X,d,T)=\overline{\dim}_{B}(X,d)$. Then

$\dim_{A}^{\alpha}(X,d)\,=\,\frac{\overline{\dim}_{B}(X,d)}{1-\alpha}\quad\quad\forall\,\alpha\,\in\,{\mathcal{H}}(T),$

where ${\mathcal{H}}(T)\,=\,\\{\alpha\in(0,1)\,:\,T\text{ is
}\alpha-\text{H\"{o}lder}\\}\,\cup\,\\{0\\}\,.$

In particular, if the space is sufficiently homogeneous so that the upper box
and Assouad dimensions coincide, then it does not admit a Hölder endomorphism
with full upper metric mean dimension. This is the case when the space is
Ahlfors regular (see Definition 4.2).

######  Corollary B.

Let $(X,d)$ be a compact metric space such that

$0<\overline{\dim}_{B}(X,d)=\dim_{A}(X,d)<+\infty$

and $T\colon X\to X$ be a continuous map such that
$\overline{\mathrm{mdim}}_{M}(X,d,T)=\overline{\dim}_{B}(X,d)$. Then $T$ is
not $\alpha-$Hölder for any $\alpha\,\in\,(0,1).$

Since a $C^{0}-$Baire generic homeomorphism on a compact manifold of dimension
grater than one has full metric mean dimension (cf. [4]), the previous
corollary provides an alternative proof of the well-known fact that a
$C^{0}-$generic homeomorphism is not $\alpha-$Hölder for any $\alpha\in(0,1)$.
A similar conclusion holds for a $C^{0}-$generic endomorphism of the interval.

Here are two concrete examples on which we may apply Theorem A. Consider the
interval $[0,1]$ with the Euclidean distance, which we denote by $|\cdot|$.

######  Example 1.1 (Weierstrass function).

Fix a positive odd integer $b>1$ and consider the map
$W\colon[0,1]\,\to\,[0,1]$ defined by

$W(x)\,=\,\sum_{n=0}^{\infty}b^{-n}\,\cos(b^{n}\pi x).$

It is known that $W$ is $\alpha-$Hölder for every $\alpha\in(0,1)$, though it
is not Lipschitz. By Theorem A we conclude that

$\textrm{mdim}_{M}([0,1],|\cdot|,W)\,=\,0.$

######  Example 1.2 (Hypersensitive zipper maps).

Let us consider the parameterized family of maps defined in [15, Section 1.1].
Given a pair of points $p=(p_{1},p_{2})$ in the open unit square subject to
some geometric conditions, a hypersensitive zipper map is the unique fixed
point of an operator which depends on $p$ and acts on the space of continuous
interval maps fixing $0$ and $1$. Let it be $Z_{p}\colon[0,1]\to[0,1]$. The
point $p$ brings forward $4$ parameters, denoted by
$1<\lambda_{\min}(p)\leq\lambda_{\max}(p)$ and $0<h_{min}(p)\leq
h_{max}(p)<1$, which describe geometric properties of the operator and impart
dynamical information about $Z_{p}$. For instance, in [15, Theorem D] it was
shown that

$\frac{\log\lambda_{min}}{|\log
h_{min}|}\,\,\leq\,\,\underline{\textrm{mdim}}_{M}([0,1],|\cdot|,Z_{p}).$

Besides, $Z_{p}$ is $\alpha-$Hölder for
$\alpha=1\,-\,\frac{\log\lambda_{max}}{|\log h_{max}|}$ (cf. [15, Proposition
2.2]). Combining this information with Theorem A, we obtain

$\frac{\log\lambda_{min}}{|\log
h_{min}|}\,\,\leq\,\,\underline{\textrm{mdim}}_{M}([0,1],|\cdot|,Z_{p})\,\,\leq\,\,\overline{\textrm{mdim}}_{M}([0,1],|\cdot|,Z_{p})\,\,\leq\,\,\frac{\log\lambda_{max}}{|\log
h_{max}|}.$

###  1.2. Horseshoes in the interval

In this subsection we consider the interval $[0,1]$ with the Euclidean
distance and the Lebesgue measure, which we denote by $\operatorname{{Leb}}$.
We will compute the metric mean dimension of a $2-$parameter family of
interval maps firstly introduced by Kolyada and Snoha (cf. [16]). This formula
refines the information provided by Theorem A for this family, revealing that
any loss in regularity is translated into metric mean dimension and vice-
versa.

Fix a sequence $a\,=\,(a_{k})_{k\geq 0}$ of real numbers and a sequence
$b\,=\,(b_{k})_{k\geq 1}$ of positive odd integers satisfying the following
conditions:

  * (C1)

$0=a_{0}<a_{1}<...<a_{k}\to 1$.

  * (C2)

$(a_{k}-a_{k-1})_{k}$ decreases to zero.

  * (C3)

$(b_{k})_{k}$ is strictly increasing.

For each $k\in\mathbb{N}$, denote by $f_{k}\colon[0,1]\to[0,1]$ the unique
continuous piecewise affine map with $b_{k}$ equidistributed full branches
such that $f_{k}$ is increasing in the first one - and since $b_{k}$ is odd,
also in the last. Let $J_{k}=[a_{k-1},a_{k}]$ and $T_{k}\colon J_{k}\to[0,1]$
be the unique increasing affine map from $J_{k}$ onto $[0,1]$. Define

$\begin{array}[]{rccc}T_{a,b}\colon&[0,1]&\rightarrow&[0,1]\\\ &x\in
J_{k}&\mapsto&T_{k}^{-1}\circ f_{k}\circ T_{k}\\\ &x=1&\mapsto&1\end{array}$
(2)

Figure 1. Graph of the map $T_{a,b}$.

Each map is determined by a sequence of horseshoes accumulating at the extreme
point $1$ (see Figure 1). The sequence $(a_{k})_{k}$ defines the intervals
$J_{k}$ where each horseshoe lies, and each $b_{k}$ represents the number of
branches in the $k-$th horseshoe. In particular, the topological entropy of
$T_{a,b}$ restricted to $J_{k}$ is $\log b_{k}$. To fix notation we write
$\varepsilon_{k}=|J_{k}|/b_{k}$, which represents the length of the
injectivity domains in $J_{k}$.

Clearly, $T_{a,b}$ has infinite topological entropy for every $a$ and $b$ (see
[16]). The metric mean dimension has been computed for specific choices of the
parameters (see for instance [23] and [3]). Similar maps were studied by
Hazard in [13], though without any mention to metric mean dimension. Actually,
the main focus there was to construct interval maps which are $\alpha-$Hölder,
for $\alpha\in(0,1),$ and whose topological entropy is infinite.

A classical result of Misiurewicz [19] states that if $T\colon[0,1]\to[0,1]$
is a continuous map then for every $n\in\mathbb{N}$ there exists

  * •

an interval $J_{n}$

  * •

a collection ${\mathcal{D}}_{n}$ of pairwise disjoint subintervals of $J_{n}$

  * •

$k_{n}\in\mathbb{N}$

such that $J_{n}\subset T^{k_{n}}(I)$ for every $I\in{\mathcal{D}}_{n}$ and

$h_{top}(T)\,=\,\limsup_{n\,\to\,+\infty}\frac{\log\\#{\mathcal{D}}_{n}}{k_{n}}.$
(3)

Observe that Misiurewicz formula (3) for the maps $T_{a,b}$ defined in (2)
becomes

$h_{top}(T_{a,b})\,=\,\limsup_{k\,\to\,+\infty}\,\log b_{k}\,=\,+\infty.$

We will obtain a formula similar to (3) for the metric mean dimension with
respect to the Euclidean distance within the family $T_{a,b}.$ As a
consequence, we also establish a connection between the upper metric mean
dimension and the Hölder regularity of $T_{a,b}$, which shows that the
estimates in Theorem A are sharp.

######  Theorem B.

Let $a\,=\,(a_{k})_{k\geq 0}$ and $b\,=\,(b_{k})_{k\geq 1}$ be two sequences
satisfying the conditions _(C1)-(C3)_ and $T_{a,b}$ be the corresponding
interval map. Then

$\displaystyle\overline{\mathrm{mdim}}_{M}([0,1],|\cdot|,T_{a,b})$
$\displaystyle=$ $\displaystyle\limsup_{k\,\to\,+\infty}\,\frac{\log
b_{k}}{\log(1/\varepsilon_{k})}$
$\displaystyle\underline{\mathrm{mdim}}_{M}([0,1],|\cdot|,T_{a,b})$
$\displaystyle=$ $\displaystyle\liminf_{k\,\to\,+\infty}\,\frac{\log
b_{k}}{\log(1/\varepsilon_{k})}.$

Moreover,

$\sup\,{\mathcal{H}}(T)\,=\,1\,-\,\overline{\mathrm{mdim}}_{M}([0,1],|\cdot|,T_{a,b}),$
(4)

where ${\mathcal{H}}(T)\,=\,\\{0\\}\,\cup\,\\{\alpha\in(0,1)\,:\,T\text{ is
}\alpha-\text{H\"{o}lder}\\}.$

For example, by Theorem B:

  * (i)

If $a_{k}\,=\,\sum_{n=1}^{k}6/\pi n^{2}$ and $b_{k}\,=\,3^{k}$, then
$\mathrm{mdim}_{M}([0,1],|\cdot|,T_{a,b})\,=\,1$ and $T_{a,b}$ is not
$\alpha-$Hölder for any $\alpha\in(0,1)$.

  * (ii)

Given $0<\beta<1$, if
$a_{k}\,=\,\sum_{n=1}^{k}C(\beta)\,3^{n\,(1-\frac{1}{\beta})}$, where
$C(\beta)\,=\,\big{(}\sum_{n=1}^{\infty}3^{n\,(1-\frac{1}{\beta})}\big{)}^{-1}$,
and $b_{k}\,=\,3^{k}$, then
$\mathrm{mdim}_{M}([0,1],|\cdot|,T_{a,b})\,=\,\beta$ and $T_{a,b}$ is
$\alpha-$Hölder for every $\alpha\in(0,1-\beta)$.

  * (iii)

If $a_{k}\,=\,1/2^{k}$ and $b_{k}\,=\,2k+1$, then
$\mathrm{mdim}_{M}([0,1],|\cdot|,T_{a,b})\,=\,0$ and $T_{a,b}$ is
$\alpha-$Hölder for every $\alpha\in(0,1).$

We stress that the lack of regularity imposed by the presence of metric mean
dimension in Theorem B is of a different nature from the one studied by Hazard
in [13]. The maps in [13] are defined like we did for $T_{a,b}$, considering
$a=(2^{-k})_{k}$ and $b=(2k+1)_{k}$ but replacing each $f_{k}$ by
$g_{k}=\phi_{\alpha}\circ f_{k}\circ\phi_{\alpha}^{-1}$, where
$\phi_{\alpha}(x)\,=\,x^{\alpha}$. Thus, these maps have zero metric mean
dimension, and their irregularity is due to the appearance of cusps. On the
other hand, we consider maps composed by sequences of piecewise _linear_
horseshoes whose lack of regularity comes from the distortion ratio between
lengths of the injectivity domains of the horseshoes and their images, or
equivalently, the ratio between the number of branches and the scales at which
they separate. This is precisely what metric mean dimension quantifies.

##  2\. Preliminaries

In this section we introduce some basic terminology.

###  2.1. Metric mean dimension

Let $(X,d)$ be a compact metric space and $T\colon X\to X$ be a continuous
map. For each $n\in\mathbb{N}$, define the Bowen metric

$d_{n}(x,y)\,=\,\max_{0\,\leq\,j\,\leq\,n-1}\,d(T^{j}(x),\,T^{j}(y))\qquad\forall\,x,y\in
X$

which is equivalent to $d$. We sometimes refer to balls with respect to this
metric as dynamical balls.

Given $\varepsilon>0$ and $K\subset X$, consider the following minimum

$S(K,d,\varepsilon)\,=\,\min\left\\{\ell\colon\,\\{U_{i}\\}_{1\,\leq\,i\,\leq\,\ell}\text{
is a finite open cover of $K$ with
$\mathrm{diam}(U_{i},d)\leq\varepsilon$}\right\\}$ (5)

and the limit

$h_{\varepsilon}(K,d,T)\,=\,\lim_{n\,\to\,+\infty}\frac{1}{n}\log
S(K,d_{n},\varepsilon),$

which exists since the sequence $\big{(}\log
S(K,d_{n},\varepsilon)\big{)}_{n}$ is sub-additive in the variable $n$. Recall
that the _topological entropy_ is given by
$h_{top}(X,T)\,=\,\lim_{\varepsilon\,\to\,0^{+}}h_{\varepsilon}(X,d,T).$

######  Definition 2.1.

_The upper/lower metric mean dimension of $(X,d,T)$ are given, respectively,
by_

$\overline{\mathrm{mdim}}_{M}(X,d,T)\,=\,\limsup_{\varepsilon\,\to\,0^{+}}\,\frac{h_{\varepsilon}(X,d,T)}{\log\,(1/\varepsilon)}$

_and_

$\underline{\mathrm{mdim}}_{M}(X,d,T)\,=\,\liminf_{\varepsilon\,\to\,0^{+}}\,\frac{h_{\varepsilon}(X,d,T)}{\log\,(1/\varepsilon)}.$

A subset $E\subset X$ is said to be $\varepsilon-$separated with respect to
the metric $d$ if $d(x,y)\geq\varepsilon$ for every $x,y\in E$; it is
$\varepsilon-$spanning with respect to the metric $d$ if for every $x\in K$
there exists some $y\in E$ such that $d(x,y)\leq\varepsilon.$ The notion of
upper/lower metric mean dimension can be equivalently defined if one replaces
$S(X,d,\varepsilon)$ by either

$S_{1}(X,d,\varepsilon)\,=\,\sup\Big{\\{}\\#E\colon\,E\subset X\text{ is
$\varepsilon-$separated}\Big{\\}}$

or

$S_{2}(X,d,\varepsilon)\,=\,\inf\Big{\\{}\\#E\colon\,E\subset X\textrm{ is
$\varepsilon-$spanning}\Big{\\}}$

and instead of the limit in $n$, we take either $\limsup_{n}$ or
$\liminf_{n}.$

The _upper/lower box dimension of $(X,d)$_ are, respectively, defined as

$\overline{\dim}_{B}(X,d)\,=\,\limsup_{\varepsilon\,\to\,0^{+}}\,\frac{S(X,d,\varepsilon)}{\log(1/\varepsilon)}\quad\text{and}\quad\underline{\dim}_{B}(X,d)\,=\,\liminf_{\varepsilon\,\to\,0^{+}}\,\frac{S(X,d,\varepsilon)}{\log(1/\varepsilon)}.$

If the above limits exist, we denote it by $\dim_{B}(X,d)$ (or simply by
$\dim_{B}X$ if the metric is clear) and refer to it as the _box dimension of
$X$_.

We recall (cf. [23]) that

$\begin{split}\overline{\mathrm{mdim}}_{M}(X,d,T)\,&\leq\,\overline{\mathrm{dim}}_{B}(X,d)\\\
\underline{\mathrm{mdim}}_{M}(X,d,T)\,&\leq\,\underline{\mathrm{dim}}_{B}(X,d)\end{split}.$
(6)

###  2.2. Other fractal dimensions

In what follows, we denote by $B_{\varepsilon}(x)$ the open ball on the metric
space $(X,d)$ centered at $x$ with radius $\varepsilon.$

######  Definition 2.2.

_The Assouad dimension of $(X,d)$ is defined as_

$\dim_{A}(X,d)\,=\,\inf\,\Bigg{\\{}s\,:\,\begin{matrix}\exists\,C,\varepsilon_{0}>0\,\,\,:\,\,\,\forall\,0<r<R<\varepsilon_{0}\,\,\,\forall\,x\in
X\\\
S\big{(}B_{R}(x),d,r\big{)}\,\leq\,C\,\Big{(}\frac{R}{r}\Big{)}^{s}\end{matrix}\Bigg{\\}}.$

The Assouad dimension quantifies the maximal local complexity of a fractal,
since it provides the maximal exponential growth rate of
$\sup_{x\,\in\,X}\,S\big{(}B_{R}(x),d,r\big{)}$ as the parameters $0<r<R$ vary
independently. In particular, it is always an upper bound to the box
dimension, which is a more averaged measurement of complexity over the whole
space. Fraser and Yu proposed in [11] an interpolation between these notions
of complexity, obtained by fixing the relation between the scales $r$ and $R$
in the definition of Assouad dimension. For each fixed $\theta\in(0,1)$, the
scales are chosen to satisfy $R=r^{\theta}$, yielding a $1-$parameter family
of dimensions.

######  Definition 2.3.

_The Assouad spectrum of $(X,d)$ is the map_

$\theta\in(0,1)\,\mapsto\,\dim_{A}^{\theta}(X,d)\,=\,\inf\,\Bigg{\\{}s\,:\,\begin{matrix}\exists\,C,\varepsilon_{0}>0\,\,\,:\,\,\,\forall\,0<R<\varepsilon_{0}\,\,\,\forall\,x\in
X\\\
S\big{(}B_{R}(x),d,R^{1/\theta}\big{)}\,\leq\,C\,\Big{(}\frac{R}{R^{1/\theta}}\Big{)}^{s}\end{matrix}\Bigg{\\}}.$

Since the Assouad spectrum is defined in terms of a unique decreasing scale,
it can also be expressed as a limit. In order to maintain a unified notation
we write $\varepsilon\,=\,r\,=\,R^{1/\theta}$, obtaining

$\dim_{A}^{\theta}(X,d)\,=\,\limsup_{\varepsilon\,\to\,0^{+}}\,\sup_{x\,\in\,X}\,\frac{\log
S\big{(}B_{\varepsilon^{\theta}}(x),d,\varepsilon\big{)}}{(1-\theta)\log(1/\varepsilon)}.$
(7)

The aforementioned notions of dimension are related by the inequalities
established in [11, Proposition 3.1]: for every $\theta\in(0,1),$

$\overline{\dim}_{B}(X,d)\,\leq\,\dim_{A}^{\theta}(X,d)\,\leq\,\min\bigg{\\{}\,\frac{\overline{\dim}_{B}(X,d)}{1-\theta},\,\dim_{A}(X,d)\bigg{\\}}.$
(8)

Moreover, the Assouad spectrum varies continuously in $(0,1)$ and can be
extended to $\theta=0$ by $\dim_{A}^{0}(X,d)=\overline{\dim}_{B}(X,d)$. It is
also known that, as $\theta\to 1^{-}$, the spectrum converges to the so called
_quasi-Assouad dimension_ , which is always finite whenever the Assouad
dimension is (see [9]). We observe that the Assouad dimension is finite if and
only if $(X,d)$ is _doubling_ , that is, there exists some $K>0$, which we
refer to as the _doubling constant of_ $(X,d)$, such that any ball of radius
$\varepsilon$ can be covered by $K$ balls of radius $\varepsilon/2$, for every
$\varepsilon>0$ (see [9, Theorem 13.1.1]).

For explicit computations and more information on the Assouad spectrum - and
its dual notion, the lower spectrum - we refer the reader to the comprehensive
references [10, 11].

##  3\. Subshifts of compact type

Let $(X,d)$ be a compact metric space. In what follows we endow the product
space $X^{\mathbb{N}}$ with the metric

$d^{\mathbb{N}}(x,y)\,=\,\sup_{i\,\in\,\mathbb{N}}\frac{d(x_{i},y_{i})}{2^{i-1}}.$

A subset $Y\subset X^{\mathbb{N}}$ is called a _subshift_ if it is closed and
invariant by the shift action

$\sigma_{\mathbb{N}}\big{(}(x_{i})_{i\,\in\,\mathbb{N}}\big{)}=(x_{i+1})_{i\,\in\,\mathbb{N}}.$

Consider a subset $\Gamma\,\subset X\times X$, whose role will be to prescribe
transitions, and the induced set of admissible sequences

$\Gamma_{\mathbb{N}}\,=\,\\{(x_{i})_{i\,\in\,\mathbb{N}}\,\colon(x_{i},x_{i+1})\in\Gamma,\,\,\forall\,i\in\mathbb{N}\\},$

which is invariant and we always assume to be non-empty. We refer to
$\overline{\Gamma_{\mathbb{N}}}$ as a _subshift of compact type_ , and note
that $\Gamma_{\mathbb{N}}$ is already closed whenever $\Gamma$ is.

In particular, we may consider the transition set given by a continuous map
$T\colon X\to X$, that is

$\Gamma\,=\,\operatorname{{graph}}(T).$

It was shown in [20] that the metric mean dimensions of $T$ in $(X,d)$ and of
$\sigma_{\mathbb{N}}$ in $(\Gamma_{\mathbb{N}},d^{\mathbb{N}})$ coincide:

$\begin{split}\overline{\mathrm{mdim}}_{M}(X,d,T)&\,=\,\overline{\mathrm{mdim}}_{M}(\Gamma_{\mathbb{N}},d^{\mathbb{N}},\sigma_{\mathbb{N}})\\\
\underline{\mathrm{mdim}}_{M}(X,d,T)&\,=\,\underline{\mathrm{mdim}}_{M}(\Gamma_{\mathbb{N}},d^{\mathbb{N}},\sigma_{\mathbb{N}}).\end{split}$
(9)

In order to prove Theorem A, we will make use of the upper bound for the
$\varepsilon-$entropy of subshifts of compact type in terms of the spectral
radius of a suitable matrix, developed in [20]. For the sake of completeness,
we briefly recall them here.

###  3.1. Spectral radius bounds

Fix a compact metric space $(X,d)$ and a subset $\Gamma\,\subset\,X\times X.$
Given $\varepsilon>0$, let
${\mathcal{U}}(\varepsilon)=\\{U_{1},...,U_{M(\varepsilon)}\\}$ be an open
$\varepsilon-$cover of $X.$ Consider the $M(\varepsilon)\times M(\varepsilon)$
matrix $\Gamma^{\varepsilon}$ given by

$\Gamma_{i,j}^{\epsilon}=\left\\{\begin{matrix}1&\textrm{if
}\big{(}U_{i}\times U_{j}\big{)}\cap\Gamma\neq\emptyset\\\
0&\textrm{otherwise.}\end{matrix}\right.$ (10)

By counting arguments similar to the ones used for subshifts of finite type,
we know that $||(\Gamma^{\epsilon})^{k}||$ many cylinders composed by elements
of ${\mathcal{U}}(\varepsilon)$ of size $k$ are enough to cover
$\Gamma_{\mathbb{N}}$, where $||\cdot||$ denotes the sum norm in the space of
$M(\varepsilon)\times M(\varepsilon)$ matrices. This estimate yields the
following equivalent formulation of [8, Lemma 4.1], where $r(A)$ stands for
the spectral radius of the matrix $A$.

######  Lemma 3.1.

Let $(X,d)$ be a compact metric space and $\Gamma\subset X\times X$. Then

$h_{\varepsilon}(\Gamma_{\mathbb{N}},d^{\mathbb{N}},\sigma_{\mathbb{N}})\leq\log
r(\Gamma^{\epsilon}).$

We will combine the previous lemma with the following property of matrices to
estimate the metric mean dimension.

######  Theorem 3.2 (Gershgorin Circle Theorem, [12]).

Let $n\in\mathbb{N}$ and $A\,=\,(a_{ij})_{i,j}$ be a complex $n\times n$
matrix. Then every eigenvalue of $A$ is contained in the union

$\bigcup_{i=1}^{n}B^{\mathbb{C}}_{R_{i}}(a_{ii}),$

where $B^{\mathbb{C}}_{\delta}(z)\,=\,\\{w\in\mathbb{C}:|z-w|\leq\delta\\}$
and $R_{i}\,=\,\sum_{j\neq i}|a_{ij}|$ for every $i=1,...,n.$

In particular, if we apply Theorem 3.2 to a $0-1$ matrix $A$ and its
transpose, we get

$\displaystyle r(A)\,\,$
$\displaystyle\leq\,\,\,\,\max_{i}\\#\\{j\,:\,a_{ij}=1\\}$ (11) $\displaystyle
r(A)\,=\,$ $\displaystyle r(A^{T})\,$
$\displaystyle\leq\,\,\,\,\max_{j}\\#\\{i\,:\,a_{ij}=1\\}.$ (12)

In the case $X\,=\,[0,1]$ (and also in higher dimensions), the matrix
$\Gamma^{\varepsilon}$ can be replaced by another one constructed by using
intersections with an $\varepsilon-$grid instead of an open cover. This
alternative definition was used by the third named author in [20, Theorem C]
to prove that the metric mean dimension of full branched interval maps with
infinitely many critical points coincides with the box dimension of the set of
such points. To compute this value, the upper bound was obtained by estimating
the number of $1$’s in any given _column_ , that is, using (12). In this paper
the estimates will be made for _rows_ and we prove Theorem A by using (11).

##  4\. Ahlfors regular spaces

As a consequence of [3, Proposition 8.7] we know that the local box dimension
structure of an alphabet is closely related to the metric mean dimension of
the corresponding full shift. In particular, when the space $(X,d)$ is box-
dimensionally homogeneous111We say that $(X,d)$ is _box-dimensionally
homogeneous_ if
$\mathrm{dim}_{B}(B_{\varepsilon}(x))\,=\,\mathrm{dim}_{B}(X),$ for every
$x\in X$ and $\varepsilon>0.$, for every continuous potential $\varphi\colon
X^{\mathbb{N}}\,\to\,\mathbb{R}$ we have (cf. [3, Theorem D])

$\overline{\mathrm{mdim}}_{M}(X^{\mathbb{N}},d^{\mathbb{N}},\sigma_{\mathbb{N}},\varphi)\,=\,\dim_{B}(X,d)\,+\,\max_{\mu\in{\mathcal{E}}_{\sigma_{\mathbb{N}}}(X^{\mathbb{N}})}\,\int\varphi\,d\mu,$

where the upper metric mean dimension with potential was defined in [21] and
${\mathcal{E}}_{\sigma_{\mathbb{N}}}(X^{\mathbb{N}})$ stands for the set of
Borel ergodic $\sigma_{\mathbb{N}}-$invariant probability measures on
$X^{\mathbb{N}}.$ In what follows, we will approach dimensional homogeneity
through a measure-theoretic perspective, which provides a stronger notion of
homogeneity, yielding a new formulation for the metric mean dimension.

For a compact metric space $Z$, denote by ${\mathcal{P}}(Z)$ the space of
Borel probability measures on $Z$.

######  Definition 4.1.

_Given a compact metric space $(X,d)$, we say that $\mu\in{\mathcal{P}}(X)$ is
Ahlfors regular if_

$\exists\delta,C_{1},C_{2}>0:\qquad
C_{1}\,\varepsilon^{\delta}\,\leq\,\mu(B_{\varepsilon}(x))\,\leq\,C_{2}\,\varepsilon^{\delta}\qquad\forall
x\in\operatorname{{supp}}(\mu),\,\forall\varepsilon>0.$

Whenever $(X,d)$ admits an Ahlfors regular probability measure $\mu$, we will
restrict our study to $\operatorname{{supp}}(\mu).$ Therefore, without loss of
generality, in what follows we will assume $\operatorname{{supp}}(\mu)=X$.

The existence of an Ahlfors regular measure on a compact metric space $(X,d)$
reflects the ultimate form of dimensional homogeneity. Namely, it ensures that
the Assouad and lower dimension, which quantify, respectively, the highest and
the lowest local complexity in terms of dimension, coincide and are equal to
the exponent $\delta$ (see [9, Theorem 6.4.1]). In particular, all the
intermediate notions of dimension such as lower spectrum, packing dimension,
Hausdorff dimension, intermediate dimension, box dimension and Assouad
spectrum coincide (see [6],[7],[9] and references therein). Thus, we will
always denote $\delta\,=\,\dim(X,d)$, abbreviating into $\dim X$ if the metric
is clear.

######  Definition 4.2.

_A triplet $(X,d,\mu)$ is an _Ahlfors regular space_ if_

$\exists C_{1},C_{2}>0:\qquad C_{1}\,\varepsilon^{\dim
X}\,\leq\,\mu(B_{\varepsilon}(x))\,\leq\,C_{2}\,\varepsilon^{\dim
X}\qquad\forall x\in X,\,\forall\varepsilon>0.$ (13)

The main examples we have in mind are the Euclidean cube $[0,1]^{D}$ with the
Lebesgue measure, a compact Riemannian manifold with the volume measure and
(finitely generated) self-similar/self-conformal sets satisfying the open-set-
condition with the right dimensional Hausdorff measure (cf. [9, Corollary
6.4.4]). In fact, the classical notion of Ahlfors regularity is defined with
the Hausdorff measure, though it may be formulated for a more general $\mu$
satisfying (13).

Every Ahlfors regular space is box-dimensionally homogeneous. However, not
every box-dimensionally homogeneous metric space admits an Ahlfors regular
measure. An example is the Bedford-McMullen carpet, whose Hausdorff and box
dimensions are distinct (cf. [2],[18]).

###  4.1. Minkowski–Bouligand dimension

The box dimension for compact subsets of the Euclidean space admits an
equivalent formulation, the so called Minkowski–Bouligand dimension (see [6,
Proposition 2.4]). We briefly recall it here.

Let $D\in\mathbb{N}$ and $F\subset\mathbb{R}^{D}$ be a compact subset of zero
Lebesgue measure (otherwise its box dimension is equal to D) and, for
$\varepsilon>0,$ consider its $\varepsilon-$neighbourhood

$B_{\varepsilon}(F)\,=\,\\{x\in\mathbb{R}^{D}:\textrm{dist}(x,F)\,<\,\varepsilon\\},$

where $\textrm{dist}(x,F)\,=\,\inf_{a\,\in\,F}\,|x-a|$. This is an open set
and it is natural to ask how fast its Lebesgue measure decreases as
$\varepsilon\,\to\,0^{+}$. It turns out that this rate provides information on
the dimension, namely,

$\overline{\mathrm{dim}}_{B}(F,|\cdot|)\,=\,D+\limsup_{\varepsilon\,\to\,0^{+}}\frac{Leb(B_{\varepsilon}(F))}{\log(1/\varepsilon)}\quad\text{and}\quad\underline{\mathrm{dim}}_{B}(F,|\cdot|)\,=\,D+\liminf_{\varepsilon\,\to\,0^{+}}\frac{Leb(B_{\varepsilon}(F))}{\log(1/\varepsilon)}.$

We are heading to an analogous result in the dynamical setting. To this end,
we need an ambient product space where we can embed and thicken, using
$\varepsilon-$neighbourhoods, the space of time $n$ orbits. Afterwards, we
evaluate the exponential rate of the $n-$dimensional volume as time increases,
and then compute the decay of this quantity as the scale $\varepsilon$ goes to
zero. Subshifts of the Euclidean cube are natural candidates for this
procedure. In what follows, we consider more general Ahlfors regular
alphabets.

###  4.2. Subshifts on Ahlfors alphabets

The main result in this section is an equivalent formulation of the metric
mean dimension of subshifts which makes use of the homogeneous structure of
the alphabet. For each $n\geq 1$, denote the product measure by
$\mu^{n}\in{\mathcal{P}}(X^{n}).$ Given an arbitrary subshift $Y\subset
X^{\mathbb{N}}$ and $\varepsilon>0$, let

$Y(n,\varepsilon)\,:=\,\bigcup_{y\,=\,(y_{i})_{i\in\mathbb{N}}\,\in\,Y}B_{\varepsilon}(y_{1})\times
B_{\varepsilon}(y_{2})\times\cdots\times
B_{\varepsilon}(y_{n})\,\subset\,X^{n}.$

We note that $Y(n,\varepsilon)$ is precisely the set
$B_{\varepsilon}(\pi_{n}(Y))$ with respect to the supremum norm
$||\cdot||_{\infty}$.

######  Theorem 4.3.

Let $(X,d,\mu)$ be an Ahlfors regular space. For every subshift
$Y\,\subset\,X^{\mathbb{N}}$, we have

$\begin{split}\overline{\mathrm{mdim}}_{M}(Y,d^{\mathbb{N}},\sigma_{\mathbb{N}})\,&=\,\mathrm{dim}(X,d)\,+\,\limsup_{\varepsilon\,\to\,0^{+}}\frac{1}{\log(1/\varepsilon)}\limsup_{n\,\to\,+\infty}\frac{1}{n}\log\mu^{n}\big{(}Y(n,\varepsilon)\big{)}\\\
&=\,\mathrm{dim}(X,d)\,+\,\limsup_{\varepsilon\,\to\,0^{+}}\frac{1}{\log(1/\varepsilon)}\liminf_{n\,\to\,+\infty}\frac{1}{n}\log\mu^{n}\big{(}Y(n,\varepsilon)\big{)}\end{split}$
(14)

and

$\begin{split}\underline{\mathrm{mdim}}_{M}(Y,d^{\mathbb{N}},\sigma_{\mathbb{N}})\,&=\,\mathrm{dim}(X,d)\,+\,\liminf_{\varepsilon\,\to\,0^{+}}\frac{1}{\log(1/\varepsilon)}\limsup_{n\,\to\,+\infty}\frac{1}{n}\log\mu^{n}\big{(}Y(n,\varepsilon)\big{)}\\\
&=\,\mathrm{dim}(X,d)\,+\,\liminf_{\varepsilon\,\to\,0^{+}}\frac{1}{\log(1/\varepsilon)}\liminf_{n\,\to\,+\infty}\frac{1}{n}\log\mu^{n}\big{(}Y(n,\varepsilon)\big{)}.\end{split}$

Motivated by (9), the third named author extended in [20, Definition 1.5] the
notion of metric mean dimension to discontinuous maps on compact metric spaces
by considering the graph of the map as a transition set and the corresponding
subshift of compact type. As an application of Theorem 4.3, we obtain an
alternative formula for the metric mean dimension of a (possibly
discontinuous) map acting on an Ahlfors regular space, which has the advantage
of providing an interpretation of the difference between the metric mean
dimension of the map and the dimension of the underlying space.

######  Corollary 4.4.

Let $(X,d,\mu)$ be an Ahlfors regular space and $T\colon X\to X$ be a
(possibly discontinuous) map. Then

$\begin{split}\overline{\mathrm{mdim}}_{M}(X,d,T)\,&=\,\mathrm{dim}(X,d)\,+\,\limsup_{\varepsilon\,\to\,0^{+}}\frac{1}{\log(1/\varepsilon)}\limsup_{n\,\to\,+\infty}\frac{1}{n}\log\mu^{n}\big{(}Y(T,n,\varepsilon)\big{)}\\\
&=\,\mathrm{dim}(X,d)\,+\,\limsup_{\varepsilon\,\to\,0^{+}}\frac{1}{\log(1/\varepsilon)}\liminf_{n\,\to\,+\infty}\frac{1}{n}\log\mu^{n}\big{(}Y(T,n,\varepsilon)\big{)}\end{split}$
(15)

and

$\begin{split}\underline{\mathrm{mdim}}_{M}(X,d,T)\,&=\,\mathrm{dim}(X,d)\,+\,\liminf_{\varepsilon\,\to\,0^{+}}\frac{1}{\log(1/\varepsilon)}\limsup_{n\,\to\,+\infty}\frac{1}{n}\log\mu^{n}\big{(}Y(T,n,\varepsilon)\big{)}\\\
&=\,\mathrm{dim}(X,d)\,+\,\liminf_{\varepsilon\,\to\,0^{+}}\frac{1}{\log(1/\varepsilon)}\liminf_{n\,\to\,+\infty}\frac{1}{n}\log\mu^{n}\big{(}Y(T,n,\varepsilon)\big{)},\end{split}$
(16)

where

$Y(T,n,\varepsilon)\,=\,\bigcup_{x\,\in\,X}B_{\varepsilon}(x)\times
B_{\varepsilon}(T(x))\times\cdots\times B_{\varepsilon}(T^{n-1}(x)).$

The previous corollary turns out to be a useful tool to explicitly compute the
metric mean dimension on Ahlfors regular spaces. See for instance the maps
$T_{a,b}$ in Subsection 1.2 and Proposition 6.1.

###  4.3. Proof of Theorem 4.3

We will only prove the first equality in (14) since the remaining ones follow
from analogous arguments. The proof is an immediate adaptation of the one in
[6, Proposition 2.4].

Recall that a dynamical ball in the shift space
$(X^{\mathbb{N}},d^{\mathbb{N}},\sigma_{\mathbb{N}})$ is given by

$B_{\varepsilon}(x,d_{n})\,=\,B_{\varepsilon}(x_{1})\times
B_{\varepsilon}(x_{2})\times\cdots B_{\varepsilon}(x_{n})\times
B_{2\varepsilon}(x_{n+1})\times\cdots\times
B_{2^{\ell}\varepsilon}(x_{n+\ell})\times X\times X\times\cdots$

where $\ell=\ell(\varepsilon)$ is the smallest positive integer satisfying
$\varepsilon 2^{\ell}\geq\operatorname{{diam}}(X)$. Observe that, for every
$\varepsilon>0$ and $n\geq 1$, the measure $\mu^{\mathbb{N}}$ satisfies

$\displaystyle\mu^{n+\ell}\big{(}Y(n+\ell,\varepsilon)\big{)}\,$
$\displaystyle=\,\mu^{n+\ell}\bigg{(}\bigcup_{y\,\in\,Y}B_{\varepsilon}(y_{1})\times\cdots\times
B_{\varepsilon}(y_{n+\ell})\bigg{)}$
$\displaystyle\leq\,\mu^{\mathbb{N}}\bigg{(}\bigcup_{y\,\in\,Y}B_{\varepsilon}(y,d_{n})\bigg{)}$
$\displaystyle\leq\,\mu^{n}\bigg{(}\bigcup_{y\,\in\,Y}B_{\varepsilon}(y_{1})\times\cdots\times
B_{\varepsilon}(y_{n})\bigg{)}\,=\,\mu^{n}\big{(}Y(n,\varepsilon)\big{)}.$

In particular, for the proof we can replace
$\mu^{n}\big{(}Y(n,\varepsilon)\big{)}$ by
$\mu^{\mathbb{N}}\big{(}Y_{n,\varepsilon}\big{)}$, where

$Y_{n,\varepsilon}\,=\,\big{\\{}x\,\in\,X^{\mathbb{N}}:d_{n}(x,Y)\leq\varepsilon\big{\\}}.$

Fix $\varepsilon>0$ and $n\geq 1$. If $Y$ can be covered by $N$ distinct
$(n,\varepsilon)-$dynamical balls, then $Y_{n,\varepsilon}$ can be covered by
the concentric dynamical balls of radius $2\varepsilon.$ Then

$\mu^{\mathbb{N}}\big{(}Y_{n,\varepsilon}\big{)}\,\leq\,N\big{(}C_{2}(2\varepsilon)^{\mathrm{dim}X}\big{)}^{n},$

and therefore

$\limsup_{n\,\to\,+\infty}\frac{1}{n}\log\mu^{\mathbb{N}}\big{(}Y_{n,\varepsilon}\big{)}\,\leq\,\limsup_{n\,\to\,+\infty}\frac{1}{n}\log
N+\log\big{(}C_{2}(2\varepsilon)^{\mathrm{dim}X}\big{)}.$

Hence,

$\limsup_{\varepsilon\,\to\,0^{+}}\frac{1}{\log(1/\varepsilon)}\limsup_{n\,\to\,+\infty}\frac{1}{n}\log\mu^{\mathbb{N}}\big{(}Y_{n,\varepsilon}\big{)}\,\leq\,\overline{\mathrm{mdim}}_{M}(Y,d^{\mathbb{N}},\sigma_{\mathbb{N}})\,-\,\dim
X.$

For the converse inequality, if there are $S$ distinct
$(n,\varepsilon)-$separated points $y_{1},\cdots,y_{S}\in Y$, then the
$(n,\varepsilon/3)-$dynamical balls centered at these points are disjoint.
Then

$\mu^{\mathbb{N}}\big{(}Y_{n,\varepsilon}\big{)}\,\geq\,\sum_{i=1}^{S}\mu^{\mathbb{N}}\big{(}B_{\varepsilon/3}(y_{i},d_{n})\big{)}\,\geq\,S\big{(}C_{1}(\varepsilon/3)^{\dim
X}\big{)}^{n+l(\varepsilon)},$

so

$\limsup_{n\,\to\,+\infty}\frac{1}{n}\log\mu^{\mathbb{N}}\big{(}Y_{n,\varepsilon}\big{)}\,\geq\,\limsup_{n\,\to\,+\infty}\frac{1}{n}\log
S+\log(C_{1}(\varepsilon/3)^{\dim X}).$

Thus,

$\limsup_{\varepsilon\,\to\,0^{+}}\frac{1}{\log(1/\varepsilon)}\limsup_{n\,\to\,+\infty}\frac{1}{n}\log\mu^{\mathbb{N}}\big{(}Y_{n,\varepsilon}\big{)}\,\geq\,\overline{\mathrm{mdim}}_{M}(Y,d^{\mathbb{N}},\sigma_{\mathbb{N}})\,-\,\dim
X,$

which concludes the proof. ∎

##  5\. Proof of Theorem A

Let $(X,d)$ be a compact metric space with finite Assouad dimension and
$T\colon X\to X$ be $\alpha-$Hölder for some $\alpha\,\in\,(0,1)$. We will
make use of the information in Section 3 to estimate the metric mean dimension
of $T$, by relating its Hölder exponent, the transition matrix (10) and the
Assouad spectrum of parameter $\theta=\alpha$ (see Definition 2.3).

Fix $\varepsilon>0$. Let $x_{1},...,x_{N}\,\in\,X$ be a maximal collection of
$\varepsilon-$ separated points and consider the open cover
${\mathcal{U}}(2\varepsilon)\,=\,\\{B_{\varepsilon}(x_{1}),...,B_{\varepsilon}(x_{N})\\}$
of $X$, whose diameter is $2\varepsilon$. Let us estimate the amount of
elements in this cover that can intersect a given ball.

######  Lemma 5.1.

For every $z\in X$ and $R>2\varepsilon>0$,

$\\#\\{i:B_{\varepsilon}(x_{i})\,\cap\,B_{R}(z)\neq\emptyset\\}\,\leq\,K\,\sup_{x\,\in\,X}\,S\big{(}B_{R}(x),d,\varepsilon\big{)},$

where $K$ is the doubling constant of $(X,d).$

###### Proof.

Recall that the balls $\\{B_{\varepsilon/2}(x_{i}):i=1,...,N\\}$ are pairwise
disjoint. Reordering if necessary, assume that the elements of
${\mathcal{U}}(2\varepsilon)$ that intersect $B_{R}(z)$ are
$B_{\varepsilon}(x_{1}),...,B_{\varepsilon}(x_{q}).$ Then
$\bigcup_{i=1}^{q}B_{\varepsilon/2}(x_{i})\,\subset B_{R+2\varepsilon}(z)$,
where the union is disjoint. Hence

$q\,\leq\,S\big{(}B_{R+2\varepsilon}(z),d,\varepsilon\big{)}\,\leq\,S\big{(}B_{2R}(z),d,\varepsilon\big{)}\,\leq\,K\,\sup_{x\,\in\,X}\,S\big{(}B_{R}(x),d,\varepsilon\big{)}.$

∎

Define the matrix $\Gamma^{2\varepsilon}$ associated to the cover
${\mathcal{U}}(2\varepsilon)$ as in (10). Since the map $T$ is
$\alpha-$Hölder, for every $i=1,...,N$ there exists some $z_{i}\in X$ such
that
$T\big{(}B_{\varepsilon}(x_{i})\big{)}\,\subset\,B_{C_{\alpha}\,\varepsilon^{\alpha}}(z_{i})$.
By the previous Lemma, $T\big{(}B_{\varepsilon}(x_{i})\big{)}$ can intersect
at most

$K\,\sup_{x\,\in\,X}\,S\big{(}B_{C_{\alpha}\,\varepsilon^{\alpha}}(x),d,\varepsilon\big{)}\,\leq\,K^{1+M}\,\sup_{x\,\in\,X}\,S\big{(}B_{\varepsilon^{\alpha}}(x),d,\varepsilon\big{)}$
(17)

elements of ${\mathcal{U}}(2\varepsilon)$ for every $i=1,...,N$, where
$M=\big{\lceil}\frac{\log 2}{\log C_{\alpha}}\big{\rceil}$. This means that
(17) provides an upper bound for the number of $1$’s on each line of
$\Gamma^{2\varepsilon}$. By Lemma 3.1 and (11) we have

$h_{2\varepsilon}(\Gamma_{\mathbb{N}},d^{\mathbb{N}},\sigma_{\mathbb{N}})\,\leq\,\log
r(\Gamma^{2\varepsilon})\,\leq\,(1+M)\log K\,+\,\sup_{x\,\in\,X}\,\log
S\big{(}B_{\varepsilon^{\alpha}}(x),d,\varepsilon\big{)},$

where $\Gamma_{\mathbb{N}}$ is the subshift of compact type induced by
$\Gamma\,=\,\operatorname{{graph}}(T)$. Combining the above estimate with (9)
we conclude that

$\overline{\mathrm{mdim}}_{M}(X,d,T)\,=\,\overline{\mathrm{mdim}}_{M}(\Gamma_{\mathbb{N}},d^{\mathbb{N}},\sigma_{\mathbb{N}})\,\leq\,(1-\alpha)\,\dim_{A}^{\alpha}(X,d).$

This ends the proof of the first part of Theorem A. The second part is a
straightforward consequence of the last inequality when $\dim_{A}(X,d)>0$ and
(8).

∎

##  6\. Proof of Theorem B

We will split the statement of Theorem B in two. Let’s start by applying
Corollary 4.4 to compute the upper and lower metric mean dimensions of
$T_{a,b}$ (defined in Subsection 1.2) with respect to the Euclidean metric.

######  Proposition 6.1.

Let $T_{a,b}$ be the map satisfying the conditions (C1)-(C3) in Theorem B.
Then

$\displaystyle\overline{\mathrm{mdim}}_{M}([0,1],|\cdot|,T_{a,b})$
$\displaystyle=$ $\displaystyle\limsup_{k\,\to\,+\infty}\frac{\log
b_{k}}{\log(1/\varepsilon_{k})}$
$\displaystyle\underline{\mathrm{mdim}}_{M}([0,1],|\cdot|,T_{a,b})$
$\displaystyle=$ $\displaystyle\liminf_{k\,\to\,+\infty}\frac{\log
b_{k}}{\log(1/\varepsilon_{k})}.$

###### Proof.

We start recalling that, for every $s\geq 1$ and $n\geq 1$, we can partition
$J_{s}$ in $b_{s}^{n}$ subintervals $J_{s}(i_{1},\cdots,i_{n})$, for
$i_{1},...,i_{n}\in\\{1,\cdots,b_{s}\\}$, satisfying (see Example $10.3$ in
[3])

$T_{a,b}^{j}(J_{s}(i_{1},\cdots,i_{n}))\,=\,J_{s}(i_{j+1},\cdots,i_{n})\qquad\forall
j\in\\{1,\cdots,n-1\\}.$

Given $\varepsilon>0$, let $k=k(\varepsilon)$ be the unique positive integer
satisfying $\varepsilon_{k+1}\,\leq\,\varepsilon\,<\,\varepsilon_{k}$.
Consider a positive integer $M=M(\varepsilon)\gg k$ such that
$a_{M-1}>1-\varepsilon.$ Then, for every $n\geq 1,$

$\displaystyle Y(n,\varepsilon)\,$
$\displaystyle=\,\bigcup_{x\,\in\,[0,1]}B_{\varepsilon}(x)\times
B_{\varepsilon}(T(x))\times\cdots\times B_{\varepsilon}(T^{n-1}(x))$
$\displaystyle=\,\bigcup_{s=1}^{M}\,\Bigg{(}\,\bigcup_{x\,\in\,J_{s}}B_{\varepsilon}(x)\times
B_{\varepsilon}(T(x))\times\cdots\times B_{\varepsilon}(T^{n-1}(x))\,\Bigg{)}$
$\displaystyle:=\,Y([0,a_{k}],n,\varepsilon)\,\cup\,Y([a_{k},a_{M}],n,\varepsilon),$

where

$\displaystyle Y([0,a_{k}],n,\varepsilon)$ $\displaystyle=$
$\displaystyle\bigcup_{s=1}^{k}\,\Bigg{(}\,\bigcup_{x\,\in\,J_{s}}B_{\varepsilon}(x)\times
B_{\varepsilon}(T(x))\times\cdots\times B_{\varepsilon}(T^{n-1}(x))\,\Bigg{)}$
$\displaystyle Y([a_{k},a_{M}],n,\varepsilon)$ $\displaystyle=$
$\displaystyle\bigcup_{s=k+1}^{M}\,\Bigg{(}\,\bigcup_{x\,\in\,J_{s}}B_{\varepsilon}(x)\times
B_{\varepsilon}(T(x))\times\cdots\times
B_{\varepsilon}(T^{n-1}(x))\,\Bigg{)}.$

Let us estimate the $n-$th Lebesgue measure of each of these sets separately.
Consider a minimal $(n,\varepsilon)-$spanning set $x_{1},\cdots,x_{N}$ in
$[0,a_{k}].$ Then

$Y([0,a_{k}],n,\varepsilon)\,\subset\,\bigcup_{i=1}^{N}B_{2\varepsilon}(x_{i})\times
B_{2\varepsilon}(T(x_{i}))\times\cdots\times
B_{2\varepsilon}(T^{n-1}(x_{i})),$

and therefore

$\displaystyle\limsup_{n\,\to\,+\infty}\frac{1}{n}\log\operatorname{{Leb}}^{n}\big{(}Y([0,a_{k}],n,\varepsilon)\big{)}\,$
$\displaystyle\leq\,h_{\varepsilon}([0,a_{k}])\,+\,\log(4\varepsilon)$
$\displaystyle\leq\,\log b_{k}\,+\,\log\varepsilon_{k}\,+\,\log 4$
$\displaystyle=\,\log|J_{k}|+\log 4.$ (18)

Besides, by invariance of each $J_{s}$, we can consider the coarse estimate

$Y([a_{k},a_{M}],n,\varepsilon)\,\subset\,\bigcup_{s=k+1}^{M}\big{(}B_{\varepsilon}(J_{s})\big{)}^{n}.$

As $(|J_{s}|)_{s}$ is decreasing, we get

$\displaystyle\operatorname{{Leb}}^{n}\big{(}Y([a_{k},a_{M}],n,\varepsilon)\big{)}\,$
$\displaystyle\leq\,\sum_{s=k+1}^{M}\big{(}|J_{s}|+2\varepsilon\big{)}^{n}$
$\displaystyle\leq\,\big{(}M(\varepsilon)-k(\varepsilon)\big{)}\,\cdot\,\big{(}|J_{k}|+2\varepsilon_{k}\big{)}^{n}$
$\displaystyle=\,\big{(}M(\varepsilon)-k(\varepsilon)\big{)}\,\cdot\,|J_{k}|^{n}\,\cdot\,\big{(}1+\frac{2}{b_{k}}\big{)}^{n},$

so

$\limsup_{n\,\to\,+\infty}\frac{1}{n}\log\operatorname{{Leb}}^{n}\big{(}Y([a_{k},a_{M}],n,\varepsilon)\big{)}\,\leq\,\log|J_{k}|\,+\,\log(1+\frac{2}{b_{k}})\,\leq\,\log|J_{k}|\,+\,\log
4.$ (19)

Bringing together (18) and (19) we obtain

$\limsup_{n\,\to\,+\infty}\frac{1}{n}\log\operatorname{{Leb}}^{n}\big{(}Y(n,\varepsilon)\big{)}\,\leq\,\log|J_{k}|\,+\,\log
4.$ (20)

On the other hand, it is easy to see that for every $n\geq 1$,
$J_{k+1}^{n}\subset Y(n,\varepsilon)$. Indeed, given $(x_{1},\cdots,x_{n})\in
J_{k+1}^{n}$ there exists $i_{j}$ such that $x_{j}\,\in\,J_{k+1}(i_{j})$ for
every $j=1,...,n$. Then, any element $y\in J_{k+1}(i_{1},\cdots,i_{n})$
$\varepsilon_{k+1}-$shadows this trajectory along the first $n$ iterates and
therefore,

$(x_{1},\cdots,x_{n})\,\in B_{\varepsilon}(y)\times
B_{\varepsilon}(T(y))\times\cdots\times
B_{\varepsilon}(T^{n-1}(x))\,\subset\,Y(n,\varepsilon).$

Combining this information with (20) we get

$\log|J_{k+1}|\,\leq\,\limsup_{n\,\to\,+\infty}\frac{1}{n}\log\operatorname{{Leb}}^{n}\big{(}Y(n,\varepsilon)\big{)}\,\leq\,\log|J_{k}|+\log
4,$

thus

$\frac{\log|J_{k+1}|}{\log(1/\varepsilon_{k+1})}\,\leq\,\frac{1}{\log(1/\varepsilon)}\limsup_{n\,\to\,+\infty}\frac{1}{n}\log\operatorname{{Leb}}^{n}\big{(}Y(n,\varepsilon)\big{)}\,\leq\,\frac{\log|J_{k}|+\log
4}{\log(1/\varepsilon_{k})}.$

The result now follows from Corollary 4.4 and the fact that

$1\,+\,\frac{\log|J_{s}|}{\log(1/\varepsilon_{s})}\,=\,\frac{\log
b_{s}}{\log(1/\varepsilon_{s})}\qquad\forall s\geq 1.$

∎

The previous reasoning does not depend on the affine structure of the
$f_{k}$’s. In fact, not even continuity was used: as long as, for every $k\geq
1$, $\tilde{f}_{k}$ satisfies both the geometric constraint (equidistribution
of critical points) and the topological constraint (strictly monotone full
branches), the maps $\tilde{T}_{a,b}$ and $T_{a,b}$ have the same upper and
lower metric mean dimensions.

To end the proof of Theorem B we are left to link the upper metric mean
dimension and the Hölder regularity of the map $T_{a,b}$.

######  Proposition 6.2.

Let $T_{a,b}$ be the map satisfying the conditions (C1)-(C3) in Theorem B.
Then,

$\sup{\mathcal{H}}(T_{a,b})\,=\,1\,-\,\overline{\mathrm{mdim}}_{M}([0,1],|\cdot|,T_{a,b}),$

where
${\mathcal{H}}(T_{a,b})\,=\,\\{\alpha\in(0,1):T_{a,b}\,\,\,\text{is}\,\,\,\alpha-\text{H\"{o}lder}\\}\,\cup\,\\{0\\}.$

###### Proof.

Let $T=T_{a,b}$. By Theorem A and (6) we already know that

$\sup{\mathcal{H}}(T)\,\leq\,1\,-\,\overline{\mathrm{mdim}}_{M}([0,1],|\cdot|,T).$

For the converse inequality, we may assume that
$\overline{\mathrm{mdim}}_{M}([0,1],|\cdot|,T)<1$, otherwise there is nothing
else to prove. Let
$\alpha\,\in\,(0,\,1-\overline{\mathrm{mdim}}_{M}([0,1],|\cdot|,T))$. Our aim
is to bound

$\sup_{x\,\neq\,y\,\in\,[0,1]}\frac{|T(x)-T(y)|}{|x-y|^{\alpha}}.$

To this end we will consider the possible different location of the points
$x,y$ with respect to the decomposition provided by $(J_{k})_{k}.$

Case 1: $x,y\in J_{k}$ for some $k\geq 1.$

Let

$H_{k}(\alpha)\,=\,\sup_{x\,\neq\,y\,\in\,J_{k}}\frac{|T(x)-T(y)|}{|x-y|^{\alpha}}\,=\,\frac{|T(a_{k-1})-T(a_{k-1}+\varepsilon_{k})|}{\varepsilon_{k}^{\alpha}}\,=\,\frac{|J_{k}|}{\varepsilon_{k}^{\alpha}}\,=\,\frac{b_{k}^{\alpha}}{|J_{k}|^{\alpha-1}}.$
(21)

Observe that

$\displaystyle\log H_{k}(\alpha)$ $\displaystyle=$ $\displaystyle\alpha\,\log
b_{k}\,-\,(\alpha\,-\,1)\,\log|J_{k}|$ (22) $\displaystyle=$
$\displaystyle\log
b_{k}\,\Big{(}(\alpha\,-\,1)\big{(}1\,-\,\frac{\log|J_{k}|}{\log
b_{k}}\big{)}\,+1\Big{)}$ $\displaystyle=$ $\displaystyle\log
b_{k}\,\Big{(}(\alpha\,-\,1)\big{(}\frac{\log(1/\varepsilon_{k})}{\log
b_{k}}\big{)}\,+1\Big{)}.$

The maximal distortion inside $J_{k}$ is given precisely by $H_{k}(\alpha)$.
By choice of $\alpha$, we know that

$\limsup_{k\,\to\,+\infty}\Big{(}(\alpha-1)(\frac{\log(1/\varepsilon_{k})}{\log
b_{k}})+1\Big{)}\,<\,0.$

In particular, combining this information with (22) we obtain that
$H_{k}(\alpha)$ is strictly smaller than $1$ for large enough $k$. Hence,
$(H_{k}(\alpha))_{k}$ is uniformly bounded and we obtain

$\sup_{k\,\geq\,1}\,\sup_{x\,\neq\,y\,\in\,J_{k}}\frac{|T(x)-T(y)|}{|x-y|^{\alpha}}\,=\,\sup_{k\,\geq\,1}H_{k}(\alpha)\,<\,+\infty.$
(23)

Case 2: $x\in J_{k}$ for some $k\geq 1$ and $y=1$.

The maximal distortion between $1$ and some element in $x\in J_{k}$ is
attained at $x=a_{k}-\varepsilon_{k}$, namely

$\sup_{x\,\in\,J_{k}}\frac{|1-T(x)|}{|1-x|^{\alpha}}\,=\,\frac{1-a_{k-1}}{(1-a_{k}+\varepsilon_{k})^{\alpha}}.$

By concavity of the map $t\mapsto t^{\alpha}$, we have

$\displaystyle\frac{1-a_{k-1}}{(1-a_{k}+\varepsilon_{k})^{\alpha}}\,$
$\displaystyle=\,\frac{(1-a_{k})\,+\,|J_{k}|}{(1-a_{k}+\varepsilon_{k})^{\alpha}}$
$\displaystyle\leq\,2^{1-\alpha}\Big{(}\frac{(1-a_{k})\,+\,|J_{k}|}{(1-a_{k})^{\alpha}+\varepsilon_{k}^{\alpha}}\Big{)}$
$\displaystyle\leq\,2^{1-\alpha}\Big{(}(1-a_{k})^{1-\alpha}+\frac{|J_{k}|}{\varepsilon_{k}^{\alpha}}\Big{)}$
$\displaystyle\leq\,2^{1-\alpha}\Big{(}1+H_{k}(\alpha)\Big{)}.$

Thus,

$\sup_{k\,\geq\,1}\,\sup_{x\,\in\,J_{k}}\frac{|1-T(x)|}{|1-x|^{\alpha}}\,<\,+\infty.$
(24)

Case 3: $x\in J_{k}$ and $y\in J_{k+n}$ for some $k,n\geq 1$.

The maximal distortion between $x\in J_{k}$ and $y\in J_{k+n}$ is attained at
$x=a_{k}-\varepsilon_{k}$ and $y=a_{k+n-1}+\varepsilon_{k+n}$, namely

$\sup_{x\,\in\,J_{k},\,y\,\in\,J_{k+n}}\frac{|T(y)-T(x)|}{|y-x|^{\alpha}}\,=\,\frac{a_{k+n}-a_{k-1}}{(a_{k+n-1}+\varepsilon_{k+n}-a_{k}+\varepsilon_{k})^{\alpha}}\,=\,\frac{\sum_{i=k}^{k+n}|J_{i}|}{(\varepsilon_{k}+\sum_{i=k+1}^{k+n-1}|J_{i}|+\varepsilon_{k+n})^{\alpha}},$

where the denominator is $(\varepsilon_{k}\,+\,\varepsilon_{k+n})^{\alpha}$ if
$n=1.$ Again by concavity, we obtain

$\displaystyle\frac{\sum_{i=k}^{k+n}|J_{i}|}{(\varepsilon_{k}+\sum_{i=k+1}^{k+n-1}|J_{i}|+\varepsilon_{k+n})^{\alpha}}\,$
$\displaystyle\leq\,3^{1-\alpha}\Big{(}\frac{|J_{k}|\,+\,\sum_{i=k+1}^{k+n-1}|J_{i}|\,+\,|J_{k+n}|}{\varepsilon_{k}^{\alpha}+(\sum_{i=k+1}^{k+n-1}|J_{i}|)^{\alpha}+\varepsilon_{k+n}^{\alpha}}\Big{)}$
$\displaystyle\leq\,3^{1-\alpha}\Big{(}\frac{|J_{k}|}{\varepsilon_{k}^{\alpha}}\,+\,(\sum_{i=k+1}^{k+n-1}|J_{i}|)^{1-\alpha}\,+\,\frac{|J_{k+n}|}{\varepsilon_{k+n}^{\alpha}}\Big{)}$
$\displaystyle\leq\,3^{1-\alpha}\Big{(}H_{k}(\alpha)\,+\,1\,+\,H_{k+n}(\alpha)\Big{)}.$

Hence,

$\sup_{k,n\,\geq\,1}\,\sup_{x\,\in\,J_{k},\,y\,\in\,J_{k+n}}\frac{|T(y)-T(x)|}{|y-x|^{\alpha}}\,<\,+\infty.$
(25)

Bringing (23), (24) and (25) together we conclude that

$\sup_{x\,\neq\,y\,\in\,[0,1]}\frac{|T(y)-T(x)|}{|y-x|^{\alpha}}\,<\,+\infty,$

which means that $T$ is $\alpha-$Hölder as claimed.

∎

##  7\. Open questions

In [5] the authors showed that, given a compact manifold $X$ of dimension
greater than one, the closure of the space of bi-Lipschitz homeomorphisms of
$X$ with respect to the Hölder topology contains a residual subset of
homeomorphisms with infinite topological entropy. Theorem A suggests that we
ask:

######  Question 1.

Given a compact Riemannian manifold $(X,d)$ with dimension $\dim X\,\geq\,2$
and $\alpha\in(0,1)$, let ${\mathcal{L}}_{\alpha}$ be the closure of the space
of bi-Lipschitz homeomorphisms of $X$ with respect to the $\alpha-$Hölder norm

$||T||_{\alpha}\,=\,||T||_{\infty}\,+\,\sup_{x\neq
y\,\in\,X}\frac{d(T(x),T(y))}{d(x,y)^{\alpha}}.$

Is it true that a generic map $T\in{\mathcal{L}}_{\alpha}$ satisfies

$\overline{\mathrm{mdim}}_{M}(X,d,T)\,=\,(1-\alpha)\,\dim X?$

In Theorem B we express the metric mean dimension of a family of interval maps
in terms of the data of a sequence of horseshoes in a manner similar to
Misiurewicz formula for the entropy. The main difference is the relevance of
the scales at which the dynamics of each horseshoe can be detected. This is
not surprising since the metric mean dimension, contrary to the entropy, is
not purely topological, depending also on the geometry of the underlying
space.

######  Question 2.

Given a continuous interval endomorphism with positive metric mean dimension,
can we find a sequence of horseshoes for iterates of the map and a sequence of
scales upon which we may build a formula for the metric mean dimension similar
to the one of Misiurewicz?

##  8\. Acknowledgments

The authors are greatful to Paulo Varandas for valuable discussions during the
preparation of this paper. MC and GP were partially supported by CMUP, member
of LASI, which is financed by national funds through FCT - Fundação para a
Ciência e a Tecnologia, I.P., under the projects with references
UIDB/00144/2020 and UIDP/00144/2020. MC also acknowledges financial support
from the project PTDC/MAT-PUR/4048/2021. GP has been awarded a PhD grant by
FCT, with reference UI/BD/152212/2021.

## References

  * [1] J. Acevedo, S. Romaña and R. Arias  Hölder continuous maps on the interval with positive metric mean dimension.  Revista Colombiana de Matemáticas 57 (2023) 57–76.
  * [2] T. Bedford.  Crinkly curves, Markov partitions and box dimensions in self-similar sets.  Ph.D dissertation, University of Warwick, 1984.
  * [3] M. Carvalho, G. Pessil and P. Varandas.  A convex analysis approach to the metric mean dimension: limits of scaled pressures and variational principles.  Adv. Math. 436 (2024) 109407.
  * [4] M. Carvalho, F. Rodrigues and P. Varandas.  Generic homeomorphisms have full metric mean dimension.  Ergodic Theory Dynam. Systems, 42:1 (2022) 40–64.
  * [5] E. Faria, P. Hazard and C. Tresser.  Infinite entropy is generic in Hölder and Sobolev spaces.  C. R. Acad. Sci. Paris, Ser.I 355 (2017) 1185–1189.
  * [6] K. Falconer.  Fractal Geometry - Mathematical Foundations and Applications.  John Wiley & Sons, Ltd., 2014.
  * [7] K. Falconer, J. M. Fraser and T. Kempton.  Intermediate dimensions.  Mathematische Zeitschrift 296 (2020) 813–830.
  * [8] S. Friedland.  Entropy of graphs, semigroups and groups.  Ergodic Theory of $Z^{d}-$Actions, London Math. Soc. Lecture Notes Ser. 228, 319–343, Cambridge Univ. Press, 1996.
  * [9] J. M. Fraser.  Assouad Dimension and Fractal Geometry.  Cambridge Tracts in Mathematics 222 Cambridge University Press, 2020.
  * [10] J. M. Fraser and H. Yu.  Assouad type spectra for some fractal families.  Indiana University Mathematics Journal 67 (2018) 2005–2043.
  * [11] J. M. Fraser and H. Yu.  New dimension spectra: finer information on scaling and homogeneity.  Adv. Math. 329 (2018) 273–328.
  * [12] S. Gerschgorin.  Über die Abgrenzung der Eigenwerte einer Matrix.  Izv. Akad. Nauk. (1931), USSR Otd. Fiz.-Mat. Nauk (in German) 6, 749–754.
  * [13] P. Hazard.  Maps in dimension one with infinite entropy.  Ark. Mat. 58 (2020) 95–119.
  * [14] A. Katok and B. Hasselblat.  Introduction to the Modern Theory of Dynamical Systems.  Encyclopedia of Mathematics and its Applications 54, Cambridge University Press, 1995.
  * [15] B. Kloeckner and M. Mihalache.  An invitation to rough dynamics: zipper maps.  Preprint, 2022, arXiv:2210.13038v1.
  * [16] S. Kolyada and L. Snoha.  Topological entropy of nonautonomous dynamical systems.  Random and Computational Dynamics 4:2 (1996) 205–233.
  * [17] E. Lindenstrauss and B. Weiss.  Mean topological dimension.  Israel J. Math. 115 (2000) 1–24.
  * [18] C. McMullen.  The Hausdorff dimension of general Sierpinski carpets.  Nagoya Math. J. 96 (1984) 1–9.
  * [19] M. Misiurewicz.  Horseshoes for continuous mappings of an interval.  In: Marchioro, C. (eds) Dynamical Systems. C.I.M.E. Summer Schools, vol 78. Springer, Berlin, Heidelberg, 2010.
  * [20] G. Pessil.  Metric mean dimension via subshifts of compact type.  Preprint, 2024, arXiv: 2407.07682v1.
  * [21] M. Tsukamoto.  Double variational principle for mean dimension with potential.  Adv. Math. 361 (2020) 106935.
  * [22] M. Tsukamoto.  Remark on the local nature of metric mean dimension.  Kyushu J. Math. 76 (2022) 143–162
  * [23] A. Velozo and R. Velozo.  Rate distortion theory, metric mean dimension and measure theoretic entropy.  Preprint, 2017, arXiv:1707.05762


# Boosting Performance for Software Defined Networks from Traffic Engineering
Perspective
††thanks:

Mohammed I. Salman  Department of Computer Science and Engineering
Wright State University
Dayton, Ohio
<EMAIL_ADDRESS>Bin Wang  Department of Computer Science and Engineering
Wright State University
Dayton, Ohio
<EMAIL_ADDRESS>
###### Abstract

Paths selection algorithms and rate adaptation objective functions are usually
studied separately. In contrast, this paper evaluates some traffic engineering
(TE) systems for software defined networking obtained by combining path
selection techniques with average delay and load balancing, the two most
popular TE objective functions. Based on TE simulation results, the best TE
system suitable for software defined networks is a system where the paths are
calculated using an oblivious routing model and its adaptation rate calculated
using an average delay objective function. Thus, we propose the RACKE+AD
system combining path sets computed using Räcke’s oblivious routing and a
traffic splitting objective function using average delay. This model
outperforms current state-of-the-art models, maximizes throughput, achieves
better network resource utilization, and minimizes delay. The proposed system
outperformed SMORE and SWAN by 4.2% and 9.6% respectively, achieving 27%
better utilization and delivering 34% more traffic with 50% less latency
compared with both systems on a GÉANT network.

###### Index Terms:

Traffic engineering, routing schemes, software defined networking, oblivious
routing, simulation, optimization

##  I Introduction

Centralized traffic engineering (TE) has gained much attention following new
software defined networking (SDN) developments. Large technology companies
such as Microsoft [1] and Google [2] have shifted to this technology over the
last few years.

Some previous studies have deviated from the standard SDN centralization
feature to improve scalability and fast adaptation to changing traffic
conditions, e.g. Contra [3], HULA [4], MP-HULA [5], and DASH [6] balance load
traffic entirely in the data plane to reduce controller overhead. These
solutions provide scalable systems with short response time, but degrade
performance, with resulting distributed solutions far from optimal [7].

Performance can also be affected by the traffic splitting objective function.
Some TE systems balance load over some paths by minimizing maximum link
utilization (MLU) [1, 8]. However, minimizing MLU does balance load and
enhance performance for low traffic and degrades performance significantly
during peak hours since it requires additional constraints to satisfy all the
demands [9]. Other TE systems use meta-heuristic [10] or heuristic [11]
solutions that can provide fast routing convergence, but the solutions are
sub-optimal since they may be only local optima. Prior to SDN, several studies
considered different objectives [12, 13]. To our knowledge, performance
impacts from these objectives and path selection strategies have not been
properly considered for SDN. Any TE system has two key ingredients: which set
of paths is used for forwarding traffic, and how to split traffic over these
selected paths. To the best of our knowledge, no previous study has focused on
boosting performance by optimizing combinations of these key ingredients, in
contrast, previous work has focused on either path selection algorithms or
traffic-splitting objective functions, but not both.

Many studies suggest that a set of shortest paths should be used in TE systems
to achieve reliable performance [1, 14, 15]. Unfortunately, choosing shortest
paths may exacerbate congestion for topologies with high link capacity
heterogeneity. Oblivious routing111We use “Oblivious routing” and “Räcke’s
oblivious routing” interchangeably strategies offer network demand independent
routing schemes, i.e., the routing scheme that is oblivious to the demands
[16, 17, 18, 19]. Although oblivious routing schemes can be devised with
guaranteed congestion ratio, the resulting routing scheme is static and unable
to adapt to changing traffic conditions. Several studies have shown that route
allocations calculated using an oblivious routing model achieve comparable
quality to adaptive solutions [8, 20]. Selected paths from this approach are
capacity-aware and diverse, which improves not only system performance, but
also robustness.

The capacity aware concept not only applies to path selection only, but also
to sending rates. For example, the Kleinrock delay objective function [21]
minimizes congestion by increasing highly utilized link costs, thus, avoiding
highly congested links. The widely used load balancing (LB) objective function
[1, 8, 22, 23, 24] minimizes utilization (relative load) for all links, and
can also be considered a capacity-aware objective function. The main goal for
demand aware objectives is to mitigate proportional increases for all demands
[12] by minimizing MLU. However, all source destination (SD) pair demands do
not increase at the same rate, and it is not trivial to predict future
demands. Thus, sending rates should not only be capacity aware, but also
demand aware.

Therefore, we constructed a new simulator, and motivated by SMORE [8] and AD
objective functions [23, 24, 25] we propose RACKE+AD, a centralized, adaptive,
semi-oblivious, demand aware, near optimal TE system with static routes
allocated using Räcke’s oblivious routing model [16, 18, 19] and dynamic rate
adaptation by approximating the average delay (AD) objective function.
RACKE+AD outperformed SWAN [1] and SMORE [8] for throughput, congestion, and
latency evaluated on GÉANT and ATT topologies.

Contributions. Critical contributions from the current paper are as follows:

  1. 1.

We present a routing scheme that outperforms current state-of-the-art
techniques.

  2. 2.

We introduce RACKE+AD, a new efficient TE simulator that can test many routing
schemes simultaneously. RACKE+AD is optimized for testing different route
selection algorithm and objective function combinations and can be easily
extended to test future TE systems.

  3. 3.

We demonstrate that a TE system with static routes and adaptive traffic
splitting offers many benefits, including performance, throughput, and
resource utilization.

##  II System Model

All TE systems comprise two phases: identifying a set of paths to be used to
forward traffic (path selection), and identifying splitting ratios to
distribute traffic over these paths (rate adaptation). Generally, routes
selected in the path selection phase are static, i.e., selected once and only
recalculated when the network topology changes. Path selection is usually
offline because updating end-to-end paths may take hundreds of seconds for
wide area networks. In contrast, the rate adaptation phase must update path
weights regularly due to frequent demand changes. However, the time required
to update path weights is considerably less than the time required to update
paths in the network. Among many techniques of paths selection algorithms and
rate adaptation objective functions, the aim of this research is to find the
best combination of these phases to enhance network performance.

Path and Rate Adaptation Properties: Intuitively, independently chosen paths
may not provide better performance than dependently chosen paths. However,
SMORE showed that path selection has considerable effect on performance [8].
Selected paths should be low stretch to minimize latency and naturally load
balanced to provide better performance. Low stretch motivated us to compare
SMORE performance and latency against k-shortest paths (KSP) approaches. SMORE
is naturally load balanced since route computation in Räcke’s oblivious
routing model is not independent and incorporates some randomness, i.e., the
obtained route set may not be the same if we were to run the model again.
Thus, we expect different performance for each run. On the other hand, KSP
selected paths are not capacity aware, whereas Räcke’s model selected paths
are capacity-aware due to the natural load balancing. Performance can be
further boosted if we use the same concept for splitting traffic over the
selected paths, and we expect best performance may be achieved using phases,
path selection, and rate adaptation.

###  II-A Rate Adaptation Models

####  II-A1 Load Balance

The load balance (LB) objective is also known as minimizing MLU, Wozencraft
objective [26], or minimizing congestion, where LB minimizes the load on the
most congested link. Thus, the LB problem can be expressed as [24]

min $\displaystyle F(x)=r$ (1) s.t. $\displaystyle\sum_{p\in
P_{d}}x_{dp}=h_{d},$ $\displaystyle d$ $\displaystyle\in D$ (1a)
$\displaystyle\sum_{d\in D~{}}\sum_{p\in P_{d}}\delta_{dpl}x_{dp}\leq c_{l}r,$
$\displaystyle l$ $\displaystyle\in L$ (1b)

where: $x_{dp}$ is the flow on path $p$ for demand $d$; $h_{d}$ is the volume
for demand $d$; $c_{l}$ is the capacity for link $l$; $P_{d}$ is the number of
candidate paths for demand $d$; $\delta_{dpl}$ = 0, 1 is a link-path
indicator, with $\delta_{dpl}$ = 1 if path $p$ for demand $d$ uses link $l$,
and 0 otherwise.

Two constraints are applied. The demand constraint (1a) ensures that all
demands are satisfied over some paths. The capacity constraint (1b) ensures
that load does not exceed the link capacity where $r\leq 1$, after solving
(1). The linear program formulation above is the final form of the problem
whereas the original problem is non-linear. The reader is referred to Chapter
4 of [24] for details on how the problem can be converted to the current form.

####  II-A2 Average Delay

For this objective function, delay for any network link can be modeled as
$y/(c-y)$, as shown in (Figure 1, solid line). Similar to the LB objective,
the original AD problem is non-linear and cannot be formulated directly as a
linear program. Thus, the delay function is a piecewise linear approximation
(2) (Figure 1, dotted line)

Figure 1: Piecewise linear approximation of the delay function.

$g(z)=\begin{cases}(3/2)z&\text{for $1\leq z<1/3$}\\\ (9/2)z-1&\text{for
$1/3\leq z<2/3$}\\\ 15z-8&\text{for $2/3\leq z<4/5$}\\\ 50z-36&\text{for
$4/5\leq z<9/10$}\\\ 200z-171&\text{for $9/10\leq z<19/20$}\\\
4000z-3781&\text{for $z\geq 19/20$}\end{cases}$ (2)

The linear program for this AD problem is

min $\displaystyle F=\sum_{l=1}^{L}\frac{r_{l}}{c_{l}}$ (3) s.t.
$\displaystyle\sum_{p=1}^{P_{d}}x_{dp}=h_{d},\quad d=1,2,...,D$ (3a)
$\displaystyle\sum_{d=1}^{D}\sum_{p=1}^{P_{d}}\delta_{dpl}x_{dp}=y_{l},\quad
l=1,2,...,L$ (3b) $\displaystyle r_{l}\geq\frac{3}{2}y_{l},\quad l=1,2,...,L$
(3c) $\displaystyle r_{l}\geq\frac{9}{2}y_{l}-c_{l},\quad l=1,2,...,L$ (3d)
$\displaystyle r_{l}\geq 15y_{l}-8c_{l},\quad l=1,2,...,L$ (3e) $\displaystyle
r_{l}\geq 50y_{l}-36c_{l},\quad l=1,2,...,L$ (3f) $\displaystyle r_{l}\geq
200y_{l}-171c_{l},\quad l=1,2,...,L$ (3g) $\displaystyle r_{l}\geq
4000y_{l}-3781c_{l},\quad l=1,2,...,L$ (3h) $\displaystyle x_{dp}\geq 0,\quad
p=1,2,...,P_{k},d=1,2,...,D$ (3i) $\displaystyle y_{l}\geq 0,\quad
l=1,2,...,L$ (3j)

which is considerably more accurate [24] than the Fortz et al. [27]
approximation.

###  II-B Paths Selection Algorithms

####  II-B1 Räcke’s oblivious routing model

Räcke’s oblivious routing model iteratively computes a distribution over
randomized routing trees using an approximation algorithm. Link weights are
adjusted for each iteration based on how much the link has been utilized in
previous routing tree sets. A routing tree has leaves corresponding to nodes
in the original topology. Thus, a path can be obtained between nodes $u$ and
$v$ in the original graph by finding corresponding leaves for $u$ and $v$ in
the routing tree.

However, paths for Räcke’s oblivious routing model are computed without
considering demands, thus, they do not overfit to a specific scenario [8].
Similar to SMORE, we also adopt the simple mechanism used to impose the number
of paths for each SD node pair. We use 4 paths for each SD pair of nodes that
have the highest weights.

####  II-B2 K-shortest paths

The proposed KSP algorithm is based on Yen’s algorithm, the most commonly used
algorithm for TE. KSP is a generalization of the shortest path routing
problem. The algorithm returns loopless $k$ shortest paths ordered from
shortest to longest. We use four paths for each SD pair, i.e., $k=4$.

##  III Simulator Framework

We built a simulator to model and test different TE scenarios, with particular
attention to efficiency, simplicity, and extendibility. Although many network
simulators have been proposed previously [28, 29, 30, 31], they are generally
not optimized for modeling TE approaches and/or do not provide ease of use or
extendibility. The proposed simulator was built in Python and can test many TE
models in parallel while recording statistics in the background. We use Gurobi
optimization [32] to solve the linear programming problems, by integrating it
with Python. The framework, data and Räcke’s oblivious routing model
implementation are all available
online222https://github.com/MohammedSalman/TE-SIMULATOR.

Simulator inputs, (e.g. topology, demands, path selection algorithms,
objective functions, etc.) are all specified in a Python script or
configuration file. The simulation produces visualized throughput graphs for
each TE system. The graphs are updated periodically as throughput data becomes
available. Three time-series metrics for each TE system are recorded in the
background during simulation: overall throughput, congestion per link, and
latency per path. Topology and traffic matrices are provided as input files,
where the user provides the location to these files in the configuration file.
If the locations are unavailable, random topology and traffic matrices will be
generated according to provided parameters, including number of nodes $N$,
number of links $L$, and traffic distribution matrix.

##  IV Simulation Setup

###  IV-A Evaluating Routing Scheme Quality

We evaluate TE systems based on congestion, throughput, and delay. Congestion
reflects how a TE system utilizes network resources, and we mostly care about
congestion when traffic demand exceeds link capacity. Thus, avoiding
congestion can be considered as preserving as much residual capacity as
possible, which is important for unexpected traffic surges that could cause
bottlenecks. Congestion has negative impact on delay due to queuing. We
measure path delay by summing queuing delay for each link along that path,
$l/(c-l)$, where $l$ is the absolute link load and $c$ is the link capacity.
Throughput is the proportion of total demand that is successfully delivered to
the destinations.

###  IV-B Simulation Settings

Path selection algorithms. We use three approaches for path selection (i)
paths selected using Räcke’s oblivious routing model, (ii) paths selected
using KSP algorithm, and (iii) select all available simple paths. We refer to
these RACKE, KSP, and OPTIMAL, respectively.

Rate adaptation objective functions. We use two objective functions for rate
adaptation: AD and LB. We refer to a routing scheme with paths selected using
KSP and rate adaptation using LB objective function as KSP+LB. Similarly,
models where the routing scheme selects all available paths and rate
adaptation uses AD is referred to as OPTIMAL (AD), etc. The RACKE+LB routing
scheme parallels that used in SMORE [8], and KSP+LB is an approximation to the
SWAN scheme [1]. Table I shows the TE systems used in our experiment.

TABLE I: Implemented TE algorithms  TE System | Description
---|---
KSP+LB |  k-Shortest Paths (KSP) for paths, LB for weights
KSP+AD |  k-Shortest Paths (KSP) for paths, AD for weights
RACKE+LB | Räcke’s oblivious routing for paths, LB for weights
RACKE+AD | Räcke’s oblivious routing for paths, AD for weights
OPTIMAL(LB)333The best load balance is achieved with this system. | All paths, LB for weights
OPTIMAL(AD)444The best average delay is achieved with this system. | All paths, AD for weights

Path budget. Similar to SMORE and SWAN, and to ensure a fair comparison, we
use 4 paths to evaluate any routing scheme. If the Räcke’s oblivious routing
model produces a routing scheme with SD pairs that has more than 4 paths, we
use the 4 highest weight paths, similar to SMORE.

Traffic matrix generation. We use the gravity model to generate the traffic
matrix (TM) [8, 17]. The gravity model approximates real-world TMs for a
production network [33]. TMs are deduced based on incoming/outgoing flow for
each forwarding device. Since that information is not available, we use a
capacity based heuristic rather than incoming/outgoing flow information [17].

Topologies. We evaluate many TE systems for ATT and GÉANT555dataset available
at: http://www.topology-zoo.org/dataset.html production topologies. The GÉANT
network (European academic network) contains 38 nodes and 104 directed links
with heterogeneous capacities. Fig. 2 shows the link capacity distribution for
this network. Different TE systems may behave differently depending on link
capacity distributions. Shortest-path TE systems may introduce a bottleneck in
heterogeneous link capacities as many SD pairs compete for the same resources.

Figure 2: Capacity distribution for GÉANT network (log scaled).

##  V Results

We evaluated multiple routing schemes using criteria focused on:

  * •

how each TE system performs regarding throughput and congestion, and

  * •

SMORE and KSP TE system impacts on latency.

###  V-A Throughput

Performance for many TE systems were evaluated on GÉANT and ATT networks with
path budget = 4 for a fair comparison with SMORE. Figures 3(a) and 3(b) show
throughput and corresponding throughput distribution for GÉANT network,
respectively. Rate adaptation using AD objective function significantly
increases throughput, achieving 4.2% and 9.6% improvement over SMORE and
KSP+LB, respectively, which confirms path selection effectiveness using
Räcke’s oblivious routing algorithm.

(a) Throughput

(b) Throughput distribution

Figure 3: Throughput for GÉANT topology

Similar to GÉANT topology, a higher throughput was achieved for ATT topology
using the AD adaptation rate objective function. KSP had slightly better
throughput than Räcke’s oblivious routing path selection algorithm (Figs. 4(a)
and 4(b)).

(a) Throughput

(b) Throughput distribution

Figure 4: Throughput on ATT topology

Räcke’s oblivious routing model with LB adaptation rate performed 1.14% better
than KSP on average. This may confirm that AD favors shortest paths when all
links have the same capacity. However, there is no guarantee that SMORE will
always outperform (or underperform) KSP under the same conditions due to
oblivious routing scheme randomness. Figure 5 shows throughput distributions
for KSP+AD with a different Räcke’s oblivious routing TE systems obtained by
repeatedly calculating the oblivious routing scheme. Output from KSP+AD
remained constant since KSP+AD is deterministic. Räcke’s oblivious routing
scheme outperformed KSP for 5 runs and underperformed for 1 run. Thus, there
is a worst case scenario where KSP may perform better than SMORE. The best run
had 2.29% higher throughput than KSP+AD. Therefore, a network operator may
choose to run Räcke’s scheme several times and choose the best outcome.

Figure 5: Throughput distribution for ATT topology for 1 KSP and 6 Räcke
schemes

###  V-B Congestion

Figures 6(a) and 6(b) show network congestion for GÉANT topology using AD and
LB. The AD objective function scheduled link loading differently from LB.
Figure 6(a) shows the maximum congested link over time. All TE systems
scheduled link loads that exceeded specific link capacities since we
deliberately fed the system with high volume demands to investigate TE system
performance well under stressed conditions. AD (Fig. 6(a)) seems to have
higher MLU whereas Fig. 6(b)) shows that the AD objective utilizes link loads
much better than LB. TE systems with LB caused a bottleneck for more than 40%
of links whereas TE systems with AD objective caused a bottleneck for 13% of
links. This low congestion ratio for AD is the main reason for the higher
throughput (Fig. 3).

The LB objective always distributes traffic perfectly across the available
routes, in the sense that all paths are used and all nodes send and receive
traffic with quite similar link utilization (relative load) for all links.
Thus, all links might be over-utilized under high demands when the system is
not feasible. On the other hand, AD deals more with delay and throughput, but
generates worse MLU than from LB. However, MLU is not a true network metric as
it only considers congestion for a single link rather than the whole network.
Thus, congestion distribution seems like a more reasonable metric, and we only
measured MLU to make that point since it is heavily used in the literature.

Thus, two factors contributed to better throughput and less congestion: routes
selected using Räcke’s oblivious routing algorithm, and using the AD
objective. Similar results were obtained for ATT topology (Figs. 7(a) and
7(b)).

(a) Max link congestion, GÉANT topology

(b) CDF of link congestions, GÉANT topology

Figure 6: Max link congestion and links’ congestion distribution on GÉANT
topology

(a) Max link congestion, ATT topology

(b) CDF of link congestions, ATT topology

Figure 7: Max link congestion and links’ congestion distribution on ATT
topology

###  V-C Latency

Figure 8 shows link delay distribution with respect to traffic delivered
within that delay for GÉANT and ATT topologies. Latency for each path was
computed by summing the link delays to obtain the path delay. Including AD
selection outperforms LB, achieving significantly lower latency. Figure 8(a)
shows that LB and AD TE systems different considerably for GÉANT topology. TE
systems with AD objective initially deliver approximately 34% traffic more
than those with LB objective, which also has latency 50% lower latency than TE
systems with AD. RACKE+AD routing delivered slightly more traffic than
OPTIMAL(AD) since OPTIMAL(AD) goal is to reduce total delay rather than
throughput. Figure 8(b) shows that routing schemes with AD also delivered more
traffic than those with LB for ATT topology. However, the gap between the two
groups is somewhat smaller than for GÉANT topologies (Fig. 8(a)) because ATT
network links are heterogeneous, hence smaller performance differences between
individual links.

(a) GÉANT topology.

(b) ATT topology.

Figure 8: Latency distribution

##  VI Related Work

The classic approach for TE problems is to solve them as a linear program (LP)
[24, 26], referred to as a multi-commodity flow problem, where the objective
function usually minimizes MLU. The approximation of AD objective function is
not as widely as used. However, this classical approach does not consider
decoupling TE system phases because all available paths are provided as
inputs. Choosing all available paths has two limitations: more paths means
more decision variables in the LP, and forwarding devices, such routers and
switches, have limited TCAM memory, hence fewer number paths is always
preferable to keep the routing table as small as possible.

The conventional approach adjusts link weights to find a good routing scheme
that can increase throughput or minimize congestion in the network [27, 34].
However, OSPF can never reach optimal because it uses the equal cost multi-
path approach that splits traffic evenly among available shortest paths
without rate adaptation. Furthermore, optimizing link weights is an NP-hard
problem.

Potentially centralized TE approaches recently became viable due to software-
defined networking (SDN) developments, that clearly decouple the two TE
phases. SWAN [1] distributes traffic over a set of k-shortest paths using an
LP that reserves a small amount of scratch capacity on links to apply updates
in a congestion-free manner. SOL [22] uses a greedy approach to randomly
select paths with the promise that this random selection will help load
balancing traffic across the network. This latter approach is somewhat similar
to valiant load balancing [35] but can lead to unnecessarily long paths and
consequently increased latency.

Oblivious routing [16, 17, 18] has also been proposed to find a routing scheme
that performs well under all possible demands. The Räcke oblivious routing
model [16] guarantees a congestion rate that is never worse than O(log n) of
optimal, where $n$ is the number of nodes in the graph. However, despite the
guaranteed congestion ratio, this approach cannot outperform systems like SWAN
since it considers all possible traffic demands. On the other hand, the
oblivious routing approach has inspired several studies (including the current
study) to investigate a careful path selection approach. SMORE [8] was
inspired by Räcke’s oblivious routing model to carefully select paths that
increase TE system performance and robustness. Paths selected this way have
low stretch, which is important to decrease latency, and are capacity aware,
which is important for load balancing. The proposed approach in this paper
suggests that careful route selection is not sufficient performance
enhancement to reach the expected maximum performance. However, a different
objective function from the commonly employed LB could further enhance
performance. Hence we were inspired to compare LB and AD objective function
performance, and subsequently propose the RACKE+AD TE system using oblivious
routing for path selection with AD to achieve better link delay and network
performance.

##  VII Discussion

This section discusses the reason behind the high gap in performance and delay
between LB and AD objective functions and one potential limitation for this
work. The LB objective function tends to make the relative load the same for
all links when all SD pairs are sending and receiving traffic. This can
enhance performance to some extent but causes bottlenecks between some SD
pairs under stressed conditions and unpredicted demands, with consequential
congestion loss. On the other hand, the AD objective function increases the
cost for highly utilized links to avoid utilizing them if other less heavily
utilized links are available. Thus, AD is more demand aware than LB and hence
offers better contribution to performance. However, solving LP for LB is much
faster than for AD, particularly for larger networks due to the increased
number of constraints and decision variables.

##  VIII Conclusion

Although a few TE systems have been optimized previously using different path
selection algorithms, few studies have investigates performance enhancement by
testing many objective functions for splitting traffic. These phases have only
been studied in isolation previously, with no prior studies testing all
possible combinations to find a routing scheme with the best available
performance.

This paper proposed RACKE+AD TE system and validated its performance
advantages by testing many possible combinations. RACKE+AD selects routes
using Räcke’s oblivious routing model and the average delay objective
function. Although the intuitive AD goal is to minimize network delay, it also
provides surprisingly better throughput than minimizing MLU (commonly known as
load balancing).

Simulations confirmed the proposed RACKE+AD system outperformed state-of-the-
art routing TE systems in terms of throughput, congestion, and delay. We
discussed a caveat when running Räcke’s oblivious routing model, where
k-shortest paths may give better performance due to randomness in oblivious
routing, and also discussed the importance of excluding the maximum congestion
metric when evaluating TE systems, particularly system that split traffic not
based on the LB objective function.

## Acknowledgment

We would like to thank the anonymous reviewers for their helpful comments and
suggestions. We also would like to thank Praveen Kumar from Cornell University
for addressing all the questions we had regarding the SMORE traffic
engineering system.

## References

  * [1] Chi-Yao Hong et al.  “Achieving High Utilization with Software-Driven WAN”  In _Proceedings of the ACM SIGCOMM 2013 Conference on SIGCOMM_ , SIGCOMM ’13  Hong Kong, China: Association for Computing Machinery, 2013, pp. 15–26  DOI: 10.1145/2486001.2486012
  * [2] Sushant Jain et al.  “B4: Experience with a Globally-Deployed Software Defined Wan”  In _SIGCOMM Comput. Commun. Rev._ 43.4 New York, NY, USA: Association for Computing Machinery, 2013, pp. 3–14  DOI: 10.1145/2534169.2486019
  * [3] Kuo-Feng Hsu et al.  “Contra: A Programmable System for Performance-aware Routing”  In _17th USENIX Symposium on Networked Systems Design and Implementation (NSDI 20)_ Santa Clara, CA: USENIX Association, 2020, pp. 701–721  URL: https://www.usenix.org/conference/nsdi20/presentation/hsu
  * [4] Naga Katta et al.  “HULA: Scalable Load Balancing Using Programmable Data Planes”  In _Proceedings of the Symposium on SDN Research_ , SOSR ’16  Santa Clara, CA, USA: Association for Computing Machinery, 2016  DOI: 10.1145/2890955.2890968
  * [5] Cristian Hernandez Benet, Andreas J. Kassler, Theophilus Benson and Gergely Pongracz  “MP-HULA: Multipath Transport Aware Load Balancing Using Programmable Data Planes”  In _Proceedings of the 2018 Morning Workshop on In-Network Computing_ , NetCompute ’18  Budapest, Hungary: Association for Computing Machinery, 2018, pp. 7–13  DOI: 10.1145/3229591.3229596
  * [6] Kuo-Feng Hsu et al.  “Adaptive Weighted Traffic Splitting in Programmable Data Planes”  In _Proceedings of the Symposium on SDN Research_ , SOSR ’20  San Jose, CA, USA: Association for Computing Machinery, 2020, pp. 103–109  DOI: 10.1145/3373360.3380841
  * [7] Mohammad Alizadeh et al.  “CONGA: Distributed Congestion-Aware Load Balancing for Datacenters”  In _Proceedings of the 2014 ACM Conference on SIGCOMM_ , SIGCOMM ’14  Chicago, Illinois, USA: Association for Computing Machinery, 2014, pp. 503–514  DOI: 10.1145/2619239.2626316
  * [8] Praveen Kumar et al.  “Semi-Oblivious Traffic Engineering: The Road Not Taken”  In _Proceedings of the 15th USENIX Conference on Networked Systems Design and Implementation_ , NSDI’18  Renton, WA, USA: USENIX Association, 2018, pp. 157–170
  * [9] C. Zhang et al.  “Scalable Traffic Engineering for Higher Throughput in Heavily-loaded Software Defined Networks”  In _NOMS 2020 - 2020 IEEE/IFIP Network Operations and Management Symposium_ , 2020, pp. 1–7  DOI: 10.1109/NOMS47738.2020.9110259
  * [10] M.. Tajiki et al.  “CECT: computationally efficient congestion-avoidance and traffic engineering in software-defined cloud data centers”  In _Cluster Computing_ 21.4, 2018, pp. 1881–1897  DOI: 10.1007/s10586-018-2815-6
  * [11] W. Quan et al.  “Adaptive Transmission Control for Software Defined Vehicular Networks”  In _IEEE Wireless Communications Letters_ 8.3, 2019, pp. 653–656  DOI: 10.1109/LWC.2018.2879514
  * [12] Eric Gourdin and Olivier Klopfenstein  “Comparison of Different QoS-oriented Objectives for Multicommodity Flow Routing Optimization”  In _Proceedings of the International Conference on Telecommunications (ICT_ , 2006
  * [13] Simon Balon, Fabian Skivée and Guy Leduc  “How Well Do Traffic Engineering Objective Functions Meet TE Requirements?”  In _NETWORKING 2006. Networking Technologies, Services, and Protocols; Performance of Computer and Communication Networks; Mobile and Wireless Communications Systems_ Berlin, Heidelberg: Springer Berlin Heidelberg, 2006, pp. 75–86
  * [14] B. Fortz, J. Rexford and M. Thorup  “Traffic engineering with traditional IP routing protocols”  In _IEEE Communications Magazine_ 40.10, 2002, pp. 118–124
  * [15] Zhanyou Ye, Shi Hong Marcus Wu and Themistoklis Prodromakis  “Computing Shortest Paths in 2D and 3D Memristive Networks”  In _Memristor Networks_ Cham: Springer International Publishing, 2014, pp. 537–552  DOI: 10.1007/978-3-319-02630-5˙24
  * [16] H. Racke  “Minimizing congestion in general networks”  In _The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings._ , 2002, pp. 43–52
  * [17] D. Applegate and E. Cohen  “Making Routing Robust to Changing Traffic Demands: Algorithms and Evaluation”  In _IEEE/ACM Transactions on Networking_ 14.6, 2006, pp. 1193–1206  DOI: 10.1109/TNET.2006.886296
  * [18] Harald Räcke  “Optimal Hierarchical Decompositions for Congestion Minimization in Networks”  In _Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing_ , STOC ’08  Victoria, British Columbia, Canada: Association for Computing Machinery, 2008, pp. 255–264  DOI: 10.1145/1374376.1374415
  * [19] Philipp Czerner and Harald Räcke  “Compact Oblivious Routing in Weighted Graphs”, 2020  arXiv:2007.02427 [cs.NI]
  * [20] M. Chiesa, G. Rétvári and M. Schapira  “Oblivious Routing in IP Networks”  In _IEEE/ACM Transactions on Networking_ 26.3, 2018, pp. 1292–1305  DOI: 10.1109/TNET.2018.2832020
  * [21] Leonard Kleinrock  “Communication Nets; Stochastic Message Flow and Delay”  USA: Dover Publications, Inc., 1972
  * [22] Victor Heorhiadi, Michael K. Reiter and Vyas Sekar  “Simplifying Software-Defined Network Optimization Using SOL”  In _Proceedings of the 13th Usenix Conference on Networked Systems Design and Implementation_ , NSDI’16  Santa Clara, CA: USENIX Association, 2016, pp. 223–237
  * [23] X. Liu, S. Mohanraj, M. Pióro and D. Medhi  “Multipath Routing from a Traffic Engineering Perspective: How Beneficial Is It?”  In _2014 IEEE 22nd International Conference on Network Protocols_ , 2014, pp. 143–154  DOI: 10.1109/ICNP.2014.34
  * [24] Deep Medhi and Karthik Ramasamy  “Chapter 4 - Network Flow Models”  In _Network Routing (Second Edition)_ , The Morgan Kaufmann Series in Networking  Boston: Morgan Kaufmann, 2018, pp. 114–157  DOI: https://doi.org/10.1016/B978-0-12-800737-2.00005-3
  * [25] B. Fortz, L. Gouveia and M. Joyce-Moniz  “On the convex piecewise linear unsplittable multicommodity flow problem”  In _2016 12th International Conference on the Design of Reliable Communication Networks (DRCN)_ , 2016, pp. 9–13  DOI: 10.1109/DRCN.2016.7470829
  * [26] R.. Gallager, A. Segall and J.. Wozencraft  “Data network reliability”, Massachusetts Inst. of Tech. Report, 1976
  * [27] B. Fortz and M. Thorup  “Internet traffic engineering by optimizing OSPF weights”  In _Proceedings IEEE INFOCOM 2000. Conference on Computer Communications. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (Cat. No.00CH37064)_ 2, 2000, pp. 519–528 vol.2  DOI: 10.1109/INFCOM.2000.832225
  * [28] George F. Riley and Thomas R. Henderson  “The ns-3 Network Simulator”  In _Modeling and Tools for Network Simulation_ Berlin, Heidelberg: Springer Berlin Heidelberg, 2010, pp. 15–34  DOI: 10.1007/978-3-642-12331-3˙2
  * [29] “Opnet Projects”, http:opnetprojects.com/ URL: http://opnetprojects.com/
  * [30] Praveen Kumar et al.  “YATES: Rapid Prototyping for Traffic Engineering Systems”  In _Proceedings of the Symposium on SDN Research_ , SOSR ’18  Los Angeles, CA, USA: Association for Computing Machinery, 2018  DOI: 10.1145/3185467.3185498
  * [31] Steven Gay, Pierre Schaus and Stefano Vissicchio  “REPETITA: Repeatable Experiments for Performance Evaluation of Traffic-Engineering Algorithms”  In _CoRR_ abs/1710.08665, 2017  arXiv: http://arxiv.org/abs/1710.08665
  * [32] LLC Gurobi Optimization  “Gurobi Optimizer Reference Manual”, 2020  URL: http://www.gurobi.com
  * [33] Matthew Roughan  “Simplifying the Synthesis of Internet Traffic Matrices”  In _SIGCOMM Comput. Commun. Rev._ 35.5 New York, NY, USA: Association for Computing Machinery, 2005, pp. 93–96  DOI: 10.1145/1096536.1096551
  * [34] Srikanth Sundaresan, Cristian Lumezanu, Nick Feamster and Pierre Francois  “Autonomous Traffic Engineering with Self-Configuring Topologies”  In _Proceedings of the ACM SIGCOMM 2010 Conference_ , SIGCOMM ’10  New Delhi, India: Association for Computing Machinery, 2010, pp. 417–418  DOI: 10.1145/1851182.1851239
  * [35] L.. Valiant  “A Scheme for Fast Parallel Communication”  In _SIAM Journal on Computing_ 11.2, 1982, pp. 350–361  DOI: 10.1137/0211027