Routing
From Wikipedia, the free encyclopedia
In computer networking the term routing (or routeing) refers to selecting paths in a computer network along which to send data.
Routing directs forwarding, the passing of logically addressed packets from their source network, toward their ultimate destination through intermediary nodes; typically hardware devices called routers. The routing process usually directs forwarding on the basis of routing tables which maintain a record of the best routes to various network destinations. Thus constructing routing tables, which are held in the routers' memory, becomes very important for efficient routing.
Routing differs from bridging in its assumption that address-structures imply the proximity of similar addresses within the network, thus allowing a single routing-table entry to represent the route to a group of addresses. Therefore, routing outperforms bridging in large networks, and it has become the dominant form of path-discovery on the Internet.
Small networks may involve manually configured routing tables, while larger networks involve complex topologies and may change constantly, making the manual construction of routing tables very problematic. Nevertheless, most of the public switched telephone network (PSTN) uses pre-computed routing tables, with fallback routes if the most direct route becomes blocked; see routing in the PSTN. Dynamic routing attempts to solve this problem by constructing routing tables automatically, based on information carried by routing protocols, and allowing the network to act nearly autonomously in avoiding network failures and blockages.
Dynamic routing dominates the Internet. However, the configuration of the routing protocols often requires a skilled touch; one should not suppose that networking technology has developed to the point of the complete automation of routing.
Packet-switched networks, such as the Internet, split data up into packets, each labeled with the complete destination address and each routed individually. Circuit switched networks, such as the voice telephone network, also perform routing, in order to find paths for circuits (such as telephone calls) over which they can send large amounts of data without continually repeating the complete destination address.
Traditional IP routing stays relatively simple because it uses next-hop routing where the router only needs to consider where it sends the packet, and does not need to consider the subsequent path of the packet on the remaining hops. However, more complex routing strategies can be, and are, often used in systems such as MPLS, ATM or Frame Relay, which are sometimes used as underlying technologies to support IP networks.
Contents |
[edit] Classes of routing algorithms
[edit] Distance vector algorithms
- Main article: Distance-vector routing protocol
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 neighbours, 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".
[edit] Link-state algorithms
- Main article: Link-state routing protocol
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.
[edit] Comparison of routing algorithms
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 [1].
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.
[edit] Routed versus routing protocols
Confusion often arises between "routed protocols" and "routing protocols".
[edit] Routed protocols
A routed protocol is any network 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 layer 3 protocols and those that are layered over them are routable, with IP being an example.
Layer 2 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.
[edit] Routing protocols
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.
[edit] Routing metrics
A routing metric consists of any value used by routing algorithms to determine whether one route should perform better than another. Metrics can cover such information as bandwidth, delay, hop count, path cost, load, MTU, reliability, and communication 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.
[edit] Classes of routing protocols
Depending on the relationship of the router relative to other autonomous systems, various classes of routing protocols exist:
- Ad hoc network routing protocols appear in networks with no or little infrastructure. For the proposed protocols, see the Ad hoc routing protocol list
- Interior Gateway Protocols (IGPs) exchange routing-information within a single autonomous system. Common examples include:
Note: pace various Cisco marketing documents, EIGRP definitely does not class as a link-state protocol or as any sort of "hybrid" thereof.
- Exterior Gateway Protocols (EGPs) route between separate autonomous systems. EGPs include:
- EGP (the original Exterior Gateway Protocol used to connect to the former Internet backbone network -- now obsolete)
- BGP (Border Gateway Protocol: the current version, BGPv4, dates from around 1995)
[edit] See also
- Routing algorithms:
- Deflection routing
- Policy based routing
- Wormhole routing
- Adaptive routing
- Alternative-path routing
- Multi-path routing
- Individual routing protocols:
- see the List of routing protocols
- Specific designs
- Classless inter-domain routing (CIDR)
- MPLS routing
- ATM routing
- Routing in the PSTN
- Topics related to packet-forwarding (not path-selection)
- Network address translation (NAT)
- IP spoofing (Security)
- Mathematical complexity of routing with multiple metrics
- Quality of Service in routing
- Overlay network routing schemes
- Key based routing (KBR)
- Decentralized object location and routing (DOLR)
- Group anycast and multicast (CAST)
- Distributed hash tables (DHT)
- RPSL
- Fuzzy routing
- Geographic routing
[edit] References
- Kurose, James E. and Ross, Keith W. (2004). Computer Networking. Benjamin/Cummings. ISBN 0321227352.
- Doyle, Jeff (2005). Routing TCP/IP, Volume I, Second Ed.. Cisco Press. ISBN 1-58705-202-4. Ciscopress ISBN 1587052024
[edit] External links
- Routing and Routed Protocols
- Routing, A diagram on how routing works
- Router Troubleshooting Primer - Steps to troubleshooting routing problems
- Count-To-Infinity Problem
- "Stability Features" are ways of avoiding the "count to infinity" problem.
- Cisco IT Case Studies about Routing and Switching
