The cooperative output regulation (COR) problem of heterogeneous linear multi-agent networks [multi-agent systems (MASs)] is studied in the paper. Agents are allowed to be inherently heterogeneous linear time-invariant systems and the communication graph is not restricted to be acyclic. Both state-and output-feedback control protocols that make use of neighbors' output information are considered. In light of robust control theory and robust output regulation theory, small-gain solvability conditions with closed-loop pole specifications are first derived. Then, an H-infinity performance allocation approach is proposed for protocol design, where algorithms for optimizing graph weights and designing protocol gains are constructed, respectively. Both continuous-time (CT) and discrete-time MASs are investigated in a unified framework. In addition, solvability of the COR problem is further discussed from the graph, agent, and exosystem aspects, respectively. It is proved that the proposed approach pre-explicitly ensures the solvability of the COR problem for either of the three cases: the graph is acyclic; for CT MASs, agents are minimum-phase and right-invertible; and for CT MASs, the poles of the exosystem have zero real part and agents are right-invertible.