Spectrum handoff causes performance degradation of the cognitive network when the primary user reclaims its right to access the licensed spectrum. In a multi-hop cognitive network, this problem becomes even worse since multiple links are involved. Spectrum handoff of multiple links seriously affects the network connectivity and routing. In this paper, we describe a cross-layer optimization approach to solve the spectrum handoff problem with joint consideration of spectrum handoff scheduling and routing. We propose a protocol, called Joint Spectrum Handoff Scheduling and Routing Protocol (JSHRP). This paper makes the following major contributions. First, the concept "spectrum handoff of single link" is extended to "spectrum handoff of multiple links", termed as "multi-link spectrum handoff". Second, we define the problem of coordinating the spectrum handoff of multiple links to minimize the total spectrum handoff latency under the constraint of the network connectivity. This problem is proven to be NP-hard, and we propose both centralized and distributed greedy algorithms to minimize the total latency of spectrum handoff for multiple links in a multi-hop cognitive network. Moreover, we jointly design the rerouting mechanism with spectrum handoff scheduling algorithm to improve the network throughput. Different from previous works in which rerouting is performed after spectrum handoff, our rerouting mechanism is executed before the spectrum handoff really happens. Simulation results show that JSHRP improves the network performance by 50% and the higher degree of interference the cognitive network experiences, the more improvement our solution will bring to the network.