iPedia Free Information Center

Information about External Gateway Protocol

This article is about routing (or routeing) in computer networks. For other uses, see Routing (disambiguation).


Routing (or routeing) is the process of selecting paths in a network along which to send data or physical traffic. Routing is performed for many kinds of networks, including the telephone network, the Internet, and transport networks.

Routing directs forwarding, the passing of logically addressed packets from their source toward their ultimate destination through intermediary nodes; typically hardware devices called routers, bridges, gateways, firewalls, or switches. Ordinary computers with multiple network cards can also forward packets and perform routing, though with more limited performance. The routing process usually directs forwarding on the basis of routing tables which maintain a record of the routes to various network destinations. Thus constructing routing tables, which are held in the routers' memory, becomes very important for efficient routing.

Routing, in a more narrow sense of the term, is often contrasted with bridging in its assumption that network addresses are structured and that similar addresses imply proximity within the network. Because structured addresses allow a single routing table entry to represent the route to a group of devices, structured addressing (routing, in the narrow sense) outperforms unstructured addressing (bridging) in large networks, and has become the dominant form of addressing on the Internet, though bridging is still widely used, albeit within localized environments.

Delivery semantics

Routing Schemes
anycast
broadcast
multicast
unicast


Routing schemes differ in their delivery semantics:
  • unicast delivers a message to a single specified node;
  • broadcast delivers a message to all nodes in the network;
  • multicast delivers a message to a group of nodes that have expressed interest in receiving the message;
  • anycast delivers a message to any one out of a group of nodes, typically the one nearest to the source.
Unicast is the dominant form of message delivery on the Internet, and this article focuses on unicast routing algorithms.

Topology distribution

Small networks may involve manually configured routing tables, while larger networks involve complex topologies and may change rapidly, making the manual construction of routing tables infeasible. 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.

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

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 least-cost path from itself to every other node using a standard shortest paths algorithm such as Dijkstra's algorithm. The result is a tree rooted at the current node such that the path through the tree from the root to any other node is the least-cost path to that node. This tree then serves to construct the routing table, which specifies the best next hop to get from the current node to any other node.

Path vector protocol

Main article: Path vector protocol


Distance vector and link state routing are both intra-domain routing protocols. They are used inside an autonomous system, but not between autonomous systems. Both of these routing protocols become intractable in large networks and cannot be used in Inter-domain routing. Distance vector routing is subject to instability if there are more than few hops in the domain. Link state routing needs huge amount of resources to calculate routing tables. It also creates heavy traffic because of flooding.

Path vector routing is used for inter-domain routing. It is similar to Distance vector routing. In path vector routing we assume there is one node (there can be many) in each autonomous system which acts on behalf of the entire autonomous system. This node is called the speaker node. The speaker node creates a routing table and advertises it to neighboring speaker nodes in neighboring autonomous systems. The idea is the same as Distance vector routing except that only speaker nodes in each autonomous system can communicate with each other. The speaker node advertises the path, not the metric of the nodes, in its autonomous system or other autonomous systems.

Comparison of routing algorithms

Distance-vector routing protocols are simple and efficient in small networks, and require little, if any management. However, naïve distance-vector algorithms do not scale well (due to the count-to-infinity problem ), and have poor convergence properties, which has led to the development of more complex but more scalable algorithms for use in large networks, such as link-state routing protocols and loop-free distance-vector protocols (e.g. EIGRP). loop-free distance-vector protocols are as robust and manageable as distance-vector protocols, while avoiding counting to infinity and hence having good worst-case convergence times.

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.

Path selection

A routing metric is a value used by a routing algorithm 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.

As a routing metric is specific to a given routing protocol, multi-protocol routers must use some external heuristic in order to select between routes learned from different routing protocols. Cisco's routers, for example, attribute a value known as the administrative distance to each route, where smaller administrative distances indicate routes learned from a supposedly more reliable protocol.

Multiple agents

In some networks, routing is complicated by the fact that no single entity is responsible for selecting paths: instead, multiple entities are involved in selecting paths or even parts of a single path. Complications or inefficiency can result if these entities choose paths to selfishly optimize their own objectives, which may conflict with the objectives of other participants.

A classic example involves traffic in a road system, in which each driver selfishly picks a path which minimizes her own travel time. With such selfish routing, the equilibrium routes can be longer than optimal for all drivers. In particular, Braess' paradox shows that adding a new road can lengthen travel times for all drivers.

The Internet is partitioned into autonomous systems (ASs) such as internet service providers (ISPs), each of which has control over routes involving its network, at multiple levels. First, AS-level paths are selected via the BGP protocol, which produces a sequence of ASs through which packets will flow. Each AS may have multiple paths, offered by neighboring ASs, from which to choose. Its decision often involves business relationships with these neighboring ASs,[1] which may be unrelated to path quality or latency. Second, once an AS-level path has been selected, there are often multiple corresponding router-level paths, in part because two ISPs may be connected in multiple locations. In choosing the single router-level path, it is common practice for each ISP to employ hot-potato routing: sending traffic along the path that minimizes the distance through the ISP's own network—even if that path lengthens the total distance to the destination.

Consider two ISPs, A and B, which each have a presence in New York, connected by a fast link with latency 5 ms; and which each have a presence in London connected by a 5 ms link. Suppose both ISPs have trans-Atlantic links connecting their two networks, but A's link has latency 100 ms and B's has latency 120 ms. When routing a message from a source in A's London network to a destination in B's New York network, A may choose to immediately send the message to B in London. This saves A the work of sending it along an expensive trans-Atlantic link, but causes the message to experience latency 125 ms when the other route would have been 20 ms faster.

A 2003 measurement study of Internet routes found that, between pairs of neighboring ISPs, more than 30% of paths have inflated latency due to hot potato routing, with 5% of paths being delayed by at least 12 ms. Inflation due to AS-level path selection, while substantial, was attributed primarily to BGP's lack of a mechanism to directly optimize for latency, rather than to selfish routing policies. It was also suggested that, were an appropriate mechanism in place, ISPs would be willing to cooperate to reduce latency rather than use hot-potato routing.[2]

See also

Routing algorithms and techniques

Routing in specific networks

Routing protocols

References

1. ^ Matthew Caesar and Jennifer Rexford. BGP routing policies in ISP networks. IEEE Network Magazine, special issue on Interdomain Routing, Nov/Dec 2005.
2. ^ Neil Spring, Ratul Mahajan, and Thomas Anderson. Quantifying the Causes of Path Inflation. Proc. SIGCOMM 2003.
  • Ash, Gerald (1997). Dynamic Routing in Telecommunication Networks. McGraw-Hill. ISBN 0070064148. 
  • Doyle, Jeff and Carroll, Jennifer (2005). Routing TCP/IP, Volume I, Second Ed.. Cisco Press. ISBN 1587052024. Ciscopress ISBN 1587052024
  • Doyle, Jeff and Carroll, Jennifer (2001). Routing TCP/IP, Volume II,. Cisco Press. ISBN 1578700892. Ciscopress ISBN 1578700892
  • Huitema, Christian (2000). Routing in the Internet, Second Ed.. Prentice-Hall. ISBN 0321227352. 
  • Kurose, James E. and Ross, Keith W. (2004). Computer Networking, Third Ed.. Benjamin/Cummings. ISBN 0321227352. 
  • Medhi, Deepankar and Ramasamy, Karthikeyan (2007). Network Routing: Algorithms, Protocols, and Architectures. Morgan Kaufmann. ISBN 0120885883. 

External links

Routing may refer to:
  • Routing between computer networks
  • iproute2, the Linux routing tool
  • Routing (EDA), an integrated circuit design stage in electronic design automation

..... Click the link for more information.
In general, the term network can refer to any interconnected group or system. Several different types of networks exist, including:

Human network

  • Business network
  • Economic network
  • Entrepreneurial network
  • Old boy network
  • Sexual network

..... Click the link for more information.
The public switched telephone network (PSTN) is the network of the world's public circuit-switched telephone networks, in much the same way that the Internet is the network of the world's public IP-based packet-switched networks.
..... Click the link for more information.
Internet is a worldwide, publicly accessible series of interconnected computer networks that transmit data by packet switching using the standard Internet Protocol (IP). It is a "network of networks" that consists of millions of smaller domestic, academic, business, and government
..... Click the link for more information.
A transport network, or transportation network in American English, is typically a network roads, streets, pipes, aqueducts, power lines, or nearly any structure which permits either vehicular movement or flow of some commodity.
..... Click the link for more information.
Forwarding is the relaying of packets from one network segment to another by nodes in a computer network.

The simplest forwarding model - unicasting - involves a packet being relayed from link to link along a chain leading from the packet's source to its destination.
..... Click the link for more information.
A node is a device that is connected as part of a computer network. For example, a node may be a computer, personal digital assistant, cell phone, router, switch, or hub.
..... Click the link for more information.
router is a device that extracts the destination of a packet it receives, selects the best path to that destination, and forwards data packets to the next device along this path.[1] They connect networks together; a LAN to a WAN for example, to access the Internet.
..... Click the link for more information.
A network bridge connects multiple network segments at the data link layer (layer 2) of the OSI model. Bridges are similar to repeaters or network hubs, devices that connect network segments at the physical layer, however a bridge works by using bridging where traffic from one
..... Click the link for more information.
In telecommunications, the term gateway has the following meanings:
  • In a communications network, a network node equipped for interfacing with another network that uses different protocols.

..... Click the link for more information.
firewall is a hardware or software device which is configured to permit, deny, or proxy data through a computer network which has different levels of trust.

Function


..... Click the link for more information.
A network switch is a computer networking device that connects network segments.

Low-end network switches appear nearly identical to network hubs, but a switch contains more "intelligence" (and a slightly higher price tag) than a network hub.
..... Click the link for more information.
Network Card

A 1990s Ethernet network interface controller card which connects to the motherboard via the now-obsolete ISA bus.

Connects to:
  • Motherboard via one of

..... Click the link for more information.
In computer networking a routing table, or Routing Information Base (RIB), is an electronic table (file) or database type object that is stored in a router or a networked computer.
..... Click the link for more information.
Computer data storage, computer memory, and often casually storage or memory refer to computer components, devices and recording media that retain digital data used for computing for some interval of time.
..... Click the link for more information.
__FORCETOC__ Bridging is a forwarding technique used in packet-switched computer networks. Unlike routing, bridging makes no assumptions about where in a network a particular address is located. Instead, it depends on broadcasting to locate unknown devices.
..... Click the link for more information.
In computer networking, the term network address may refer to one of the following:
  • A network layer address, i.e. a logical address such as an IP address, X.25/X.21 address or IPX address.
  • The base address of a classful address range to an organization, i.e.

..... Click the link for more information.
Internet is a worldwide, publicly accessible series of interconnected computer networks that transmit data by packet switching using the standard Internet Protocol (IP). It is a "network of networks" that consists of millions of smaller domestic, academic, business, and government
..... Click the link for more information.
Anycast is a network addressing and routing scheme whereby data is routed to the "nearest" or "best" destination as viewed by the routing topology.

The term is intended to echo the terms unicast, broadcast and multicast.
..... Click the link for more information.
In computer networking, broadcasting refers to transmitting a packet that will be received (conceptually) by every device on the network. In practice, the scope of the broadcast is limited to a broadcast domain. Contrast unicasting and multicasting.
..... Click the link for more information.
Multicast is the delivery of information to a group of destinations simultaneously using the most efficient strategy to deliver the messages over each link of the network only once, creating copies only when the links to the destinations split.
..... Click the link for more information.
In computer networks, unicast is the sending of information packets to a single destination. "Unicast" is derived from the word broadcast, as unicast is the extreme opposite of broadcasting.
..... Click the link for more information.
In computer networks, unicast is the sending of information packets to a single destination. "Unicast" is derived from the word broadcast, as unicast is the extreme opposite of broadcasting.
..... Click the link for more information.
In computer networking, broadcasting refers to transmitting a packet that will be received (conceptually) by every device on the network. In practice, the scope of the broadcast is limited to a broadcast domain. Contrast unicasting and multicasting.
..... Click the link for more information.
Multicast is the delivery of information to a group of destinations simultaneously using the most efficient strategy to deliver the messages over each link of the network only once, creating copies only when the links to the destinations split.
..... Click the link for more information.
Anycast is a network addressing and routing scheme whereby data is routed to the "nearest" or "best" destination as viewed by the routing topology.

The term is intended to echo the terms unicast, broadcast and multicast.
..... Click the link for more information.
Network topology is the study of the arrangement or mapping of the elements (links, nodes, etc.) of a network, especially the physical (real) and logical (virtual) interconnections between nodes [1] [2] [3].
..... Click the link for more information.
The public switched telephone network (PSTN) is the network of the world's public circuit-switched telephone networks, in much the same way that the Internet is the network of the world's public IP-based packet-switched networks.
..... Click the link for more information.
In the context of the public switched telephone network, routing is the process by which telephone calls are routed around the telephone network. Telephone exchanges are connected together with trunks.
..... Click the link for more information.
A routing protocol is a protocol that specifies how routers communicate with each other to disseminate information that allows them to select routes between any two nodes on a network. Typically, each router has a priori knowledge only of its immediate neighbors.
..... Click the link for more information.


This article is copied from an article on Wikipedia.org - the free encyclopedia created and edited by online user community. The text was not checked or edited by anyone on our staff. Although the vast majority of the wikipedia encyclopedia articles provide accurate and timely information please do not assume the accuracy of any particular article. This article is distributed under the terms of GNU Free Documentation License.
Herod_Archelaus


page counter