1 Describe the difference between distance-vector and link-state dynamic routing protocols. Give an example of each.

Distance vector routing is so named because it involves two factors: the distance, or metric, of a destination, and the vector, or direction to take to get there. Routing information is only exchanged between directly connected neighbors. This means a router knows from which neighbor a route was learned, but it does not know where that neighbor learned the route; a router can't see beyond its own neighbors. This aspect of distance vector routing is sometimes referred to as "routing by rumor." Measures like split horizon and poison reverse are employed to avoid routing loops.

Link-state routing, in contrast, requires that all routers know about the paths reachable by all other routers in the network. Link-state information is flooded throughout the link-state domain (an area in OSPF or IS-IS) to ensure all routers poses a synchronized copy of the area's link-state database. From this common database, each router constructs its own relative shortest-path tree, with itself as the root, for all known routes.

A Comparison: Link State vs. Distance Vector

If all routers were running a Distance Vector protocol, the path or 'route' chosen would be from A B directly over the ISDN serial link, even though that link is about 10 times slower than the indirect route from A C D B.
[pic]
A Link State protocol would choose the A C D B path because it's using a faster medium (100 Mb Ethernet). In this example, it would be better to run a Link State routing protocol, but if all the links in the network are the same speed, then a Distance Vector protocol is better.

2 List problems that each routing type encounters when dealing with topology changes, and describe techniques to reduce the number of these problems. Give a scenario depicting the use of one routing type. Illustrate which problems the routing type addresses and how it addresses them.

Distance Vector
Distance vector based routing algorithms use the Bellman-Ford algorithm to calculate best route paths. They DO NOT know the topology of the network. They pass periodic copies of a routing table from router to router. Each router receives a routing table from its direct neighbor only. Assume Router 1 knows about network A and B, and Router 2 knows about B and C. After the next periodic exchange, Router 1 will know about networks A, B, and C and the distance is incremented in Router 1 to get to network C because it now has to go through the neighboring router. This process occurs in all directions between direct neighbor routers. If during the next transmission, a better path exists the routing table will be updated. Distance vector algorithms do not allow a router to know the exact topology of an internetwork. Examples include RIP (Routing Information Protocols) and IGRP (Interior Gateway Routing Protocol)

Benefits include:
Easy to implement – It takes very little configuration to get it up and running
Widely supported – Most devices support some type of Distance Vector routing protocols

Potential Problems:
Counting to infinity This condition continuously loops packets around the network, despite the fundamental fact that the destination network is down. While the routers are counting to infinity, the invalid information allows a routing loop to exist.
Routing Loops Routing Loops can occur if the internetwork's slow convergence on a new configuration causes inconsistent routing entries.

Implemented Solutions:
Split Horizon if you learn a protocol's route on an interface, do not send information about that route back out that interface.
Defining a Maximum Specify a maximum distance vector metric as infinity,
Hold down Timers Routers ignore network update information for some period.
Route poisoning Router keeps an entry for the network down state, allowing time for other routers to recompute for the topology change.

Link State
These are designed for larger networks and address the shortcomings of Distance Vector algorithms. They use the SPF algorithm to calculate best route paths. As a result they map the entire network topology unlike DVP’s. A “link” can be defined as a network interface on a router. A “link-state” is the status between two router interfaces. Link-state protocols use a topological database that is created on each router; entries describing each router; each router’s attached links, and each router’s neighboring routers are included in the database. Each router thus builds a complete map of the network. For routing updates, each router running an LSP locates routers directly connected to it. It then sends out link-state advertisements (LSAs) in its area, listing its neighbor’s names and route cost to each neighbor. Cost is the value that indicates relative speed of the link as indicated by the bandwidth on the link. A router that receives LSAs then forwards them to neighbor routers in the network cloud. The lowest cost paths are optimal yet multiple optimal paths allow load balancing. A router running a Link-State algorithm uses a hello packet to establish a formal connection with each directly connected together. Examples include OSPF (Open Shortest Path First).

Benefits include:
Quick Convergence – Incorporates route changes into the network and performs new route computation immediately
Support for VLSM – Allows multiple-level sub-networked IP addresses within a single network
Increased network node access – Supports large numbers of network nodes far beyond the previous 15-hop limitation
Sending of periodic routing updates – Only sends updates when there is a change in the topology
Optimizing route selection – Uses composite routing methods.

Potential Problems:
Processing and memory required – More memory is required due to the large amount of network information that needs to be managed. Recall that each router has a complete picture of the network.
Bandwidth consumed for initial link state “flood” – A lot of bandwidth is consumed during initial link-state startup. This issue is called flooding. This is caused from all routers trying to converge the network and understand the network topology.
Unsynchronized updates and inconsistent path decisions – This often happens when links become unavailable and the LSP has to be reconstructed. During the calculation other links go down as other come up. This creates problems.
Large network synchronization – This adds to the problems due to the complete network topology that each router contains. Larger networks will run Hybrid protocols.

Implemented Solutions:
Reduce the need for resources
Coordinate link-state updates