Path determination constraints may be encoded in the form of a program having one or more instructions. Each of instructions may include an operation code, and operands (or pointers to locations where operands are stored). In this way, an extensible, interoperable way for a nodes (e.g., label-switching routers) to communicate constraints within a network is provided. Such constraints may be inserted (e.g., as one or more CONSTRAINT objects) into signaling messages (e.g., a PATH RSVP message). By enabling the signaling of constraints, the determination of constraint-based (label-switched) paths can be distributed among a number of (label-switching) routers or other nodes. Upon receiving a message with constraints (e.g., a CONSTRAINT object(s)), a node may (i) ignore the constraints if the node is a tail-end node (label-switching router), (ii) apply the constraints to a link if the next hop in the (label-switched) path is strict, and/or (iii) perform a constraint-based path determination to a next hop if the next hop is loose.