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

K. Somasundaram and J. S. Baras

LAA Special Issue on the occasion of 1st Montreal Workshop on Idempotent and Tropical Mathematics, Volume 435, Issue 7, pp. 1494–1512, 1 October 2011.

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.

Keywords- Pareto efficiency, lexicographic optimality, maxorder optimality, partial orders, idempotent semirings, trusted routing.