Jump to content

Routing

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Thanhantorob (talk | contribs) at 21:15, 10 December 2006 (added Fuzzy Routing). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
This article discusses routing in computer networks. For other meanings, see routing (disambiguation).
Routing schemes
Unicast

Broadcast

Multicast

Anycast

In computer networking the term routing 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.

Dynamic routing basics

If a designated path becomes unavailable, the existing nodes must determine an alternate route to use to get their data to its destination. They usually accomplish this through the use of a routing protocol using one of two broad classes of routing algorithms: distance vector algorithms and link state algorithms, which together account for nearly every routing algorithm in use on the Internet.

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".

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 the network.

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.

Routed versus routing protocol

Confusion often arises between routed protocol and routing protocol:

  • Routed protocol : 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. IP is an example of a routed protocol; Ethernet is considered a non-routable protocol.
  • Routing protocols : facilitate the exchange of routing information between networks, allowing routers to build routing tables dynamically. Traditional IP routing stays 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.

Although this dynamic routing can become very complex, it makes the Internet very flexible, and has allowed it to grow in size by more than eight orders of magnitude over the years since adopting IP.

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.

Depending on the relationship of the router relative to other autonomous systems, various classes of routing protocols exist:

  • Interior Gateway Protocols (IGPs) exchange routing-information within a single autonomous system. Common examples include:
    • IGRP (Interior Gateway Routing Protocol)
    • EIGRP (Enhanced Interior Gateway Routing Protocol)
    • OSPF (Open Shortest Path First)
    • RIP (Routing Information Protocol)
    • IS-IS (Intermediate System to Intermediate System)

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)

See also

References

  • Kurose, James E. and Ross, Keith W. (2004). Computer Networking. Benjamin/Cummings. ISBN 321227352 .{{cite book}}: CS1 maint: multiple names: authors list (link)
  • Doyle, Jeff (2005). Routing TCP/IP, Volume I, Second Ed. Cisco Press. ISBN 1-58705-202-4.Ciscopress ISBN 1587052024
Retrieved from "https://en.wikipedia.org/w/index.php?title=Routing&oldid=93437519"