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

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

Title : Solving Multi-metric Network Problems: An Interplay Between Idempotent Semiring Rules
Authors :
Somasundaram, Kiran K
Baras, John, S.
Journal : LAA Special Issue on the occasion of 1st Montreal Workshop on Idempotent and Tropical Mathematics Volume 435, Issue 7, pp. 1494 -1512
October 01, 2011

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 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 of trusted routing in which logical security rules of admission control can be combined with delay performance metrics in the multi-criteria optimization framework.

Download Full Paper