We propose a formal model to represent and solve the Constraint-Based Routing problem in networks. To attain this, we model the network adapting it to a weighted or graph (unicast delivery) or and-or graph (multicast delivery), where the weight on a connector corresponds to the cost of sending a packet on the network link modelled by that connector. We use the Soft Constraint Logic Programming (SCLP) framework as a convenient declarative programming environment in which to solve the routing problem. In particular, we show how the semantics of an SCLP program computes the best route in the corresponding graph. At last, we provide an implementation of the framework over scale-free networks.