Routing

(Redirected from External gateway protocol)

Categories: Computer networks | Internet architecture | Routing

This article discusses routing in computer networks. For other meanings, see routing (disambiguation).

Routing is a means of discovering paths in computer networks along which information can be sent. Routing directs forwarding, the passing of logically addressed packets from their source toward their ultimate destination through intermediary nodes, called routers. Forwarding is usually directed by routing tables within the routers, which maintain a record of the best routes to various network destination locations; thus, the construction of routing tables is the primary goal of routing. Routing differs from bridging in its assumption that addresses are structured so that similar addresses are close together in the network, allowing the route to a group of addresses to be represented with a single routing table entry. Therefore, routing is better suited than bridging to large networks, and is the dominant form of path discovery on the Internet.

Small networks may involve hand configuration of routing tables. Large networks involve complex topologies and may change constantly, making the constructing of routing tables very problematic. Nevertheless, most of the PSTN uses pre-computed routing tables, with fallback routes if the most direct route is 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 allow the network to be nearly autonomous in avoiding network failures and blockages. Dynamic routing dominates the Internet. However, the configuration of the routing protocols often requires a skilled touch; it should not be supposed that networking technology has developed to the point where routing is a completely automatic operation.

In packet switched networks, such as the Internet, the data is split up into packets, each labeled with the complete destination address and routed individually. Circuit switched networks, such as the voice telephone network, also perform routing, to find paths for circuits, such as telephone calls, over which large amounts of data can be sent without continually repeating the complete destination address.

The hardware used in routing includes hubs, switches and routers.

Contents

[edit]

Dynamic routing basics

If a designated path is no longer available, the existing nodes must determine an alternate route to use to get their data to its destination. This is usually accomplished 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.

[edit]

Distance vector algorithms

Main article: Distance-vector routing protocol

Distance vector algorithms use the Bellman-Ford algorithm. When this is used, the link between each node in the network is assigned a number, the cost. 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 is very simple. When a node first starts, it only knows of its immediate neighbours, and the direct cost to them. (This information, the list of destinations, the total cost to each, and the next hop to send data to to get there, is 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. 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 a new routing table. This is then passed to all adjacent nodes, which then repeat the process. Eventually all the nodes are updated, and will then discover new paths to all the destinations which are still reachable.

[edit]

Link state algorithms

Main article: Link-state routing protocol

When link state algorithms are used, the fundamental data each node uses is 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 is connected to, and each node then independently assembles this information into a map. Using this map, each router then independently determines the best route from it to every other node.

The algorithm used to do this, Dijkstra's algorithm, does this by building another data structure, a tree, with the 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 have not yet been added to the tree, it adds the node which has the lowest cost to reach an adjacent node which is already in the tree. This continues until every node has been added to the tree.

This tree is then used to construct the routing table, giving the best next hop, etc, to get from the node itself to any other node in the network.'

[edit]

Routed versus routing protocol

There is often confusion 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. 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.
  • 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 is superior to 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.

Administrative distance is the feature used by routers to select the best path when there are 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 is 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: The impression in various Cisco marketing documents to the contrary, EIGRP is definitely not a link-state protocol, or 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: current version, BGPv4, was adopted around 1995)
[edit]

See also

[edit]

References

  • {{{Author|{{{Last|}}}}|1{{{1|}}}={{{3|}}}}}}|, {{{First}}}}}}}}}|1{{{1|}}}={{{3|}}}}}}| (2004)}}}|1{{{1|}}}={{{3|}}}}}}}}}}}}|.}}}|1{{{1|}}}={{{3|}}}}}}| "{{{Chapter}}}" in}} }|1{{{1|}}}={{{3|}}}}}}|{{{Editor}}} }}}|1{{{1|}}}={{{3|}}}}}}|2=[{{{URL}}}|3=}} Computer Networking}|1{{{1|}}}={{{3|}}}}}}|2=]|3=}}}|1{{{1|}}}={{{3|}}}}}}|, {{{Others}}}}}}|1{{{1|}}}={{{3|}}}}}}|, {{{Pages}}}}}}|1{{{1|}}}={{{3|}}}}}}|, Benjamin/Cummings}}}|1{{{1|}}}={{{3|}}}}}}|. ISBN 321227352}}
[edit]

External links

es:Encaminamiento fr:Routage he:ניתוב ja:ルーティング pl:Routing pt:Encaminhamento ru:Маршрутизация tr:Routing