Routing protocols, distance vector vs link state
Solution 1:
Distance Vector
Pure distance vector protocols are rare; the only one really remaining in any sort of use is RIP. EIGRP, a Cisco proprietary protocol, is also technically distance vector, but it makes use of several optimisations that allow it to overcome the traditional shortcomings of distance vector protocols. Distance vector protocols do not distribute any topology information; they simply advertise the next hop to a route, along with a cost.
Pros:
- Minimal configuration required.
- Low CPU/memory overhead.
Cons:
- Prone to routing loops (less applicable to EIGRP).
- Slow convergence time.
- Different routers may have different perceptions as to the 'state' of the network.
Link state
Link-state protocols function by advertising each router's connected interfaces to every other device in the routing domain. Effectively, each device builds a database of the full network topology, and uses this database to determine the best path to each destination network.
The two major link-state protocols in use are OSPF and IS-IS; both are based around an implementation of Dijkstra's algorithm. OSPF is the more well-known of the two; IS-IS tends to be found more in service provider networks.
Pros:
- All routers in the network have a consistent view of the world.
- Loops are essentially impossible in a link-state network.
- Fast reconvergence.
Cons:
- Higher CPU/memory footprint required.
- Difficult to filter routes being advertised to specific routers, as link-state algorithms rely on the entire AS having a consistent view of the world.
Protocol choice
In terms of which protocol type you should use, it depends on your requirements. In general, unless you are being forced to do so by a vendor, RIP should not be used. If you are running an all Cisco network, EIGRP can be brought up with very little manual configuration. If interoperability between vendors is a requirement, OSPF may be a better choice. As mentioned in another answer, if you are going to be exchanging routes with a 3rd party, BGP is the protocol of choice.
One last point: dynamic routing protocols are useful only when your topology is redundant, and you need automatic failover. If you have a single router which supports all of your LAN environments and your ISP circuit, then a default route to your ISP would be more than sufficient.
Solution 2:
Personally I would choose your routing protocol not the way it works. Now days the right answer is practically always OSPF if its an internal network. If its an external network then the answer is probably BGP ( but you wouldn't be asking in that case ). Link state protocols have fast convergence.
OSPF is a link state protocol, an open standard.
RIP can still be used on tiny networks or to redistribute routing from simple devices to more complex devices ( or to inject default routes )