Routing protocols are key protocols on the public Internet and in enterprise networks. Routers exchange control messages to compute their routing tables. A bug in the processing of such messages could cause routers to crash or reboot, leading to wide scale disruptions. We propose a generic fuzzing approach that is able to automatically predict the structure of routing packets based on collected packet traces. We automatically extract header length, checksum and the Type-Length-Value structure of such protocols. We leverage this inferred structure to generate fuzzed routing messages and we apply this approach to three very different protocols: IS-IS, EIGRP and Babel. Our experiments reveal three major problems in an open-source implementation of EIGRP that have now been fixed by the maintainers and one problem in the IS-IS implementation.