There are two things engineers yearn for in a good routing protocol: instantaneous convergence and no overhead. Since that is not possible, it is necessary to settle for a low overhead protocol with very fast convergence. But what defines low overhead? One major component of routing protocol overhead is interruption due to updates.
You don't want to use a routing protocol that interrupts every host on the network every 30 seconds with a routing update (like Routing Information Protocol [RIP] does). To combat update overhead, routing protocols attempt to reduce the scope and the frequency of interruptions.
One technique used by routing protocols is to reduce the scope of the updates, which means to reduce the number of hosts that will hear the update packet. Broadcast is the worst possible medium for sending updates—every host on the wire is forced to look at the packet and decide whether or not it is interesting. Only a few hosts on a network are interested in the routing updates, so using the broadcast mechanism to send routing updates is a massive waste of time and resources.
To get around this problem, routing protocols use either multicast or unicast routing updates. Open Shortest Path First (OSPF), Enhanced Interior Gateway Routing Protocol (EIGRP), and Intermediate System-to-Intermediate System (IS-IS) all use well-known multicast addresses for their routing updates so that hosts and other computers that aren't interested in the updates can filter them out at the hardware layer.
Border Gateway Protocol (BGP) uses unicast routing updates, which is even better, but does require special configuration to work (neighbor statements).
Another technique used to reduce the overhead in a routing protocol is to reduce the frequency of the updates. RIP, which advertises all known destinations every 30 seconds, uses a great deal of bandwidth.
OSPF is periodic, timing its table out every 30 minutes; 30 minutes is much more efficient than 30 seconds. In between these 30-minute intervals, OSPF counts on flooding unreachables as a mechanism for discovering invalid paths. EIGRP and BGP never time their tables out. BGP relies on a withdraw mechanism to discover invalid paths, and EIGRP relies on a system of queries to discover invalid paths.
Routing protocols reduce network overhead by reducing the number of packets
required to provide other routers with the routing information they need. Routing protocols use fancy encoding schemes to fit more information into each packet. For example, whereas RIP can fit 25 route updates in a single routing update packet, IGRP can fit 104.
Routing protocols also use incremental updates to reduce the number of packets required to do the job. Rather than a router advertising its full routing table every so often, it only advertises changes in its routing table. This reduces the amount of processing time required to recalculate when changes occur in the network, and it also reduces the amount of bandwidth the routing protocol consumes.
In general, routing protocol overhead should be considered when choosing which protocol to use. Because the design of the network has some bearing on what the overhead will be, there is no absolute answer. You need to understand the burden that every protocol will place on your network before deciding.