Distributed multimedia applications require negotiation of quality of service (QoS) and resource reservation for distributed application components and communication links. Negotiation of QoS for an application session is a balancing process between the QoS specified by a client, the resource capabilities of the distributed system and the functional capabilities of the distributed application. Negotiation requires application level QoS descriptions and an end-to-end view spanning the whole distributed application. XNRP, introduced in this paper, is a protocol meeting these requirements. XNRP performs negotiation based on client specified QoS value ranges and is independent of application level QoS semantics. It allows QoS negotiation and resource reservation in three phases and supports arbitrarily interconnected flowgraphs of application components.