  The routing algorithms used by current operators aim at coping with the
demanded QoS requirements while optimizing the use of their network resources.
These algorithms rely on the optimal substructure property (OSP), which states
that an optimal path contains other optimal paths within it. However, we show
that QoS metrics such as queuing delay and buffer consumption do not satisfy
this property, which implies that the used algorithms lose their optimality
and/or completeness. This negatively impacts the operator economy by causing a
waste of network resources and/or violating Service Level Agreements (SLAs). In
this paper, we propose a new so-called Mn taxonomy defining new metric classes.
An Mn metric corresponds to a metric which requires the knowledge of the n
previously traversed edges to compute its value at a given edge. Based on this
taxonomy, we present three solutions for solving routing problems with the
newly defined classes of metrics. We show that state-of-the-art algorithms
based on the OSP indeed lose their original optimality and/or completeness
properties while our proposed solutions do not, at the price of an increased
computation time.
