|
Link state routing is a complex routing technique in which each router shares information with other routers about the reachability of other networks and the metric to reach the other networks in order to determine the best path. Routing is the process of moving packets across a network from one host to a another. It is usually performed by dedicated devices called routers. Packets are the fundamental unit of information transport in all modern computer networks, and increasingly in other communications networks as well. They are transmitted over packet switched networks, which are networks on which each message (i.e., data that is transmitted) is cut up into a set of small segments prior to transmission. The metric is based on number of hops, link speeds, traffic congestion and other factors as determined by the network designers. A hop is the trip that a packet takes from one router to another as it traverses a network on the way to its destination. In link state routing, every router on the network receives a map of the connectivity of the network in the form of a graph showing which nodes (i.e., routers, switches, computers and other network devices) are connected to which other nodes. Each router then independently calculates the best next hop for every possible destination in the network using only its local copy of the map and without communicating with any other node. The collection of best next hops forms the routing table for the router. Link state routers use Dijkstra's algorithm to calculate the lowest cost paths, and normally update other routers with which they are connected only when their own routing tables change. Invented by the Dutch computer scientist Edsger Dijkstra, this algorithm is a technique for finding the shortest path between two nodes in a weighted graph. Link state routing is an improvement over distance vector routing protocols, the other main class of routing protocols for packet switched networks. These protocols, such as RIP (routing information protocol), normally use only a single metric (such as hop count) and which exchange all of their table information with all other routers on a regular basis. Link state routing normally requires more memory and processing than distance vector routing, but there is less transmission overhead and it reacts more quickly to changes in network connectivity. Despite their differences, both algorithm types perform well in most circumstances. Link state routing was invented around 1978 by John McQuillan. Its first use in a network was for ARPANET (Advanced Research Project Agency Network), the precursor to the Internet; this was a result of problems with the distance vector routing protocol that was initially used for that network. The first comprehensive link state protocol was IS-IS (intermediate system to intermediate system), which became the precursor to OSPF (open shortest path first) and NLSP (NetWare link services protocol). Created November 1, 2005. |