The future Internet is expected to support applications with quality of ser
vice (QoS) requirements. To this end, several mechanisms are suggested in t
he IETF; the most promising among them is DiffServ, An important problem in
this framework is how to partition the QoS requirements of an application
along: a selected path. The problem which is, in general, NP-complete, was
solved for continuous convex cost functions by Lorenz and Orda, This paper
concentrates on discrete cost functions, which better model the existing an
d upcoming mechanisms in the Internet, We present efficient exact and appro
ximated solutions for various conditions of the problem, We also show that
although the more complex problem of QoS sensitive routing with discrete co
st functions is hard, it has a fully polynomial approximation scheme.