Routing and Routed ProtocolsEdit
Confusion often arises between "routed protocols" and "routing protocols".
A routed protocol is any network layer protocol that provides enough information in its network layer address to allow a packet to be forwarded from one host to another host based on the addressing scheme, without knowing the entire path from source to destination. Routed protocols define the format and use of the fields within a packet. Packets generally are conveyed from end system to end system. Almost all network layer protocols and those that are layered over them are routable, with IP being an example.
Data Link protocols such as Ethernet are necessarily non-routable protocols, since they contain only a link-layer address, which is insufficient for routing: some higher-level protocols based directly on these without the addition of a network layer address, such as 'NetBIOS', are also non-routable.
Routing protocols are used in the implementation of routing algorithms to facilitate the exchange of routing information between networks, allowing routers to build routing tables dynamically. In some cases, routing protocols can themselves run over routed protocols: for example, BGP runs over TCP: care is taken in the implementation of such systems not to create a circular dependency between the routing and routed protocols.
A list of routing protocols can be found in the list of routing protocols.
A routing metric consists of any value used by routing algorithms to determine to choose one route over another. Metrics can take into account such information as bandwidth, delay, hop count, load, MTU, reliability, and cost. The routing table stores only the best possible routes, while link-state or topological databases may store all other information as well.
Routers use the feature known as administrative distance to select the best path when they "know" of two or more different routes to the same destination from two different routing protocols. Administrative distance defines the reliability of a routing protocol. Each routing protocol gets prioritized in order of most to least reliable using an administrative-distance value. A static route has a lower (better) administrative-distance than a route by OSPF, which is better than RIP.
Classes of routing algorithmsEdit
Distance vector algorithmsEdit
Distance vector algorithms use the Bellman-Ford algorithm. This approach assigns a number, the cost, to each of the links between each node in the network. Nodes will send information from point A to point B via the path that results in the lowest total cost (i.e. the sum of the costs of the links between the nodes used).
The algorithm operates in a very simple manner. When a node first starts, it only knows of its immediate neighbors, and the direct cost involved in reaching them. (This information, the list of destinations, the total cost to each, and the next hop to send data to get there, makes up the routing table, or distance table.) Each node, on a regular basis, sends to each neighbour its own current idea of the total cost to get to all the destinations it knows of. The neighbouring node(s) examine this information, and compare it to what they already 'know'; anything which represents an improvement on what they already have, they insert in their own routing table(s). Over time, all the nodes in the network will discover the best next hop for all destinations, and the best total cost.
When one of the nodes involved goes down, those nodes which used it as their next hop for certain destinations discard those entries, and create new routing-table information. They then pass this information to all adjacent nodes, which then repeat the process. Eventually all the nodes in the network receive the updated information, and will then discover new paths to all the destinations which they can still "reach".
When applying link-state algorithms, each node uses as its fundamental data a map of the network in the form of a graph. To produce this, each node floods the entire network with information about what other nodes it can connect to, and each node then independently assembles this information into a map. Using this map, each router then independently determines the best route from itself to every other node.
The algorithm used to do this, Dijkstra's algorithm, does this by building another data structure, a tree, with the current node itself as the root, and containing every other node in the network. It starts with a tree containing only itself. Then, one at a time, from the set of nodes which it has not yet added to the tree, it adds the node which has the lowest cost to reach an adjacent node which already appears in the tree. This continues until every node appears in the tree.
This tree then serves to construct the routing table, giving the best next hop, etc., to get from the node itself to any other network.
Comparison of routing algorithmsEdit
Distance-vector routing protocols are simple and efficient in small networks, and require little, if any management. However, they do not scale well, and have poor convergence properties, which has led to the development of more complex but more scalable link-state routing protocols for use in large networks. Distance-vector protocols suffer from the count-to-infinity problem .
The primary advantage of link-state routing is that it reacts more quickly, and in a bounded amount of time, to connectivity changes. Also, the link-state packets that are sent over the network are smaller than the packets used in distance-vector routing. Distance-vector routing requires a node's entire routing table to be transmitted, while in link-state routing only information about the node's immediate neighbours are transmitted. Therefore, these packets are small enough that they do not use network resources to any significant degree. The primary disadvantage of link-state routing is that it requires more storage and more computing to run than distance-vector routing.
Routers talk to one another about the state of the network and of nearby devices. The protocols they use for to talk to each other, routing protocols, should not be confused with ROUTED protocols like IP and IPX that carry data on the network.
Common routing protocols include RIP, RIPv2, IGRP, EIGRP, IS-IS and BGP. For the CCNA exam you will need to be well versed in RIP, RIPv2, IGRP and EIGRP. You should be aware of IS-IS and BGP, and be able to configure basic OSPF.
Two main types of routing protocols exist - distance vector and link state. A third type known as balanced hybrid (Known now as "Advanced Distance Vector") combines features of both link state and distance vector protocols.
Examples of Distance Vector routing protocolsEdit
Examples of Link State routing protocolsEdit
- OSPF (Open Shortest Path First)
Examples of Advanced Distance Vector routing protocolsEdit
- EIGRP "Enhance inter Gateway Routing Protocol"
Routers may be configured with static routes, i.e. the network administrator configures the router with information about routes on a network, OR routers may be learn routes dynamically by using a routing protocol.