Token-based cache coherence protocols simultaneously capture the best attributes of the two predominant approaches to coherence: low-latency cache misses (like in snooping-based protocols) and no reliance on totally-ordered interconnects (like in directory-based protocols). The key aspect to get those features is the use of requests that do not need to be put in order. Unfortunately, unordered requests present a serious problem since, in case of contention, they generate protocol races, which may prevent them from succeeding in solving cache misses. Therefore, to eliminate races, ensure the completion of all requests, and eventually resolve all cache misses, protocols based on tokens require the use of a starvation prevention mechanism. The main drawbacks of token-based protocols are caused by the starvation prevention mechanism. Thus, although several alternative mechanisms have been proposed so far, all of them suffer from (1) being too inefficient, (2) requiring storage resources at each node that grow proportionally to the system size, and (3) requiring the use of broadcast messages. These problems compromise the scalability of token-based protocols because, as the system size increases, the protocol performs worse, the storage requirements at each node grows significantly, and the interconnect is more and more flooded with broadcast messages. However, these are not the only problems that compromise the protocol scalability, since token-based protocols require the use of non-silent invalidations, which threaten the scalability too. As long as shared-memory multiprocessors include an increasingly number of nodes, the use of efficient and scalable cache coherence protocols is required. Therefore, the contributions of this dissertation aim to improve the performance and scalability of token-based protocols by tackling the weakest aspects of the starvation prevention mechanisms and the non-silent invalidations. The most important contribution is the observation that simple routing algorithms can naturally avoid protocol races in cache coherence protocols that do not rely on either totally-ordered interconnects or directories to put requests in order. By using routing techniques based on ordered paths, we can easily create an efficient and scalable starvation prevention mechanism for token-based protocols. Additionally, those routing strategies can help us to develop techniques that improve the mechanism scalability by (1) minimizing its storage requirements and (2) considerably reducing the traffic overhead caused by broadcast messages. Besides, one of these techniques can be readily adapted to improve the problem of non-silent invalidations.