Today’s Internet is a collection of multi-domain networks where each domain is usually administrated and managed by a single network operator. Unfortunately, network operators share minimal information with each other and do not collaborate much to improve their routing decisions and the overall performance of the resulting large-scale mutli-domain network. Motivated by the need to solve this problem, in this paper, we look at this particular challenge and propose a novel collaborative multi-domain routing framework that is able to efficiently route the incoming flows through the different domains while ensuring their performance requirements in terms of delay and bandwidth and maximizing the overall network utilization. We hence propose an integer linear program to solve this problem and develop a greedy algorithm to cope with large-scale instances of the problem. Simulation results show that the proposed collaboration mechanism is able to significantly optimize network utilization and maximize the number of routed flows with guaranteed performance.