Optimal partition of QoS requirements with discrete cost functions - Selected Areas in Communications

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, VOL. 18, NO. 12, DECEMBER 2000 2593Optimal Partition of QoS Requirements with DiscreteCost FunctionsDanny Raz, Member, IEEE and Yuval Shavitt, Member, IEEEAbstract—The future Internet is expected to support applica- The QoS routing problem is to find a minimal cost path (ortions with quality of service (QoS) requirements. To this end, sev- a multicast tree) in the network that can support the connectioneral mechanisms are suggested in the IETF; the most promisingQoS requirements (such as delay). Along the selected path, re-among them is DiffServ. An important problem in this frameworksources (bandwidth, buffer space) should be optimally allocatedis how to partition the QoS requirements of an application along aselected path. The problem which is, in general, NP-complete, was to support the required QoS at a minimal cost. The latter can besolved for continuous convex cost functions by Lorenz and Orda. formulized as an optimization problem for the partition of theThis paper concentrates on discrete cost functions, which better end-to-end QoS requirements to local requirements along a pathmodel the existing and upcoming mechanisms in the Internet. We(or a multicast tree).present efficient exact and approximated solutions for various con-In general, the partition problem is intractable. The specialditions of the problem. We also show that although the more com-plex problem of QoS sensitive routing with ...