Solving Multi-metric Network Problems: An Interplay Between Idempotent Semiring Rules

Kiran K. Somasundaram and John S. Baras

Linear Algebra and its Applications, Vol. 435, Issue 7, October 2011, pp. 1494-1512

Abstract:

We motivate computations in a multifunctional networked
system as instances of algebraic path problems on labeled
graphs. We illustrate, using examples, that composition operators
used in many function computations in a networked system follow
the semiring axioms. We present an abstract framework, using
a special idempotent semiring algebraic path problem, to handle
multiple metrics for composition. We show that using different
vector order relations in this abstract framework, we can obtain
different rules of compositions such as Pareto, lexicographic
and max-order efficiency. Under this framework, we identify
a class of tractable composition rules that can be solved in
different multi-criteria settings at affordable computational cost.
We demonstrate using an example from trusted routing that
logical security rules of admission control can be combined
with delay performance metrics in the multi-criteria optimization
framework.