We present a formal model to represent and solve the unicast/multicast routing problem in networks with quality-of-service (QoS) requirements. To attain this, first we translate the network adapting it to a weighted graph (unicast) or and-or graph (multicast), where the weight on a connector corresponds to the multidimensional cost of sending a packet on the related network link: each component of the weights vector represents a different QoS metric value (e. g., bandwidth). The second step consists in writing this graph as a program in soft-constraint logic programming (SCLP): the engine of this framework is then able to find the best paths/trees by optimizing their costs and solving the constraints imposed on them (e. g. delay <= 40 ms), thus finding a solution to QoS routing problems. C-semiring structures are a convenient tool to model QoS metrics. At last, we provide an implementation of the framework over scale-free networks and we suggest how the performance can be improved. The article highlights the expressivity of SCLP.
|Autori interni:||MONTANARI, UGO GIOVANNI ERASMO|
|Autori:||Bistarelli S; Montanari U; Rossi F; Santini F|
|Titolo:||Unicast and Multicast QoS Routing with Soft-Constraint Logic Programming|
|Anno del prodotto:||2010|
|Digital Object Identifier (DOI):||10.1145/1838552.1838557|
|Appare nelle tipologie:||1.1 Articolo in rivista|