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. The term routing may refer to the following. ... Look up network, networking in Wiktionary, the free dictionary. ... The public switched telephone network (PSTN) is the concatenation of the worlds public circuit-switched telephone networks, in much the same way that the Internet is the concatenation of the worlds public IP-based packet-switched networks. ... 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. ...

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 they are not specialized hardware and may suffer from 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. Forwarding is the relaying of packets from one network segment to another by nodes in a computer network. ... Node(Latin nodus ‘knot’) is critical element of any computer network. ... This article is about a computer networking device. ... A network bridge connects multiple network segments at the data link layer (layer 2) of the OSI model. ... 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. ... Firewall may refer to: Firewall (construction), a physical barrier inside a building or vehicle, designed to limit the spread of fire, heat and structural collapse Firewall (networking), a logical barrier designed to prevent unauthorized or unwanted communications between sections of a computer network Firewall (film), a 2006 action film written... A network switch is a computer networking device that connects network segments. ... A network card, network adapter or NIC (network interface controller) is a piece of computer hardware designed to allow computers to communicate over a computer network. ... In computer networking a routing table is an electronic table (file) or database type object that is stored in a router or a networked computer. ... This article does not cite any references or sources. ...

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. Bridging is a forwarding technique used in packet-switched computer networks. ... In computer networking, the term network address may refer to one of the following: A network layer address, i. ...

Delivery semantics

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. In computer networks, unicast is the sending of information packets to a single destination. ... Routing Schemes anycast broadcast multicast unicast In computer networking, broadcasting refers to transmitting a packet that will be received (conceptually) by every device on the network. ... Multicast is sometimes also (incorrectly) used to refer to a multiplexed broadcast. ... Routing Schemes anycast broadcast multicast unicast Anycast is a network addressing and routing scheme whereby data is routed to the nearest or best destination as viewed by the routing topology. ...

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 unfeasible. 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. For other uses of topology, see topology (disambiguation). ... The public switched telephone network (PSTN) is the network of the worlds public circuit-switched telephone networks, in much the same way that the Internet is the network of the worlds public IP-based packet-switched networks. ... In the context of the public switched telephone network, routing is the process by which telephone calls are routed around the telephone network. ... The introduction to this article provides insufficient context for those unfamiliar with the subject matter. ...

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). A distance-vector routing protocol is one of the two major classes of routing protocols used in packet-switched networks for computer communications, the other major class being the link-state protocol. ... Bellman-Ford algorithm computes single-source shortest paths in a weighted graph (where some of the edge weights may be negative). ...

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. In computer networking a routing table is an electronic table (file) or database type object that is stored in a router or a networked computer. ...

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. A link-state routing protocol is one of the two main classes of routing protocols used in packet-switched networks for computer communications. ... For other uses, see Map (disambiguation). ... In graph theory, the single-source shortest path problem is the problem of finding a path between two vertices such that the sum of the weights of its constituent edges is minimized. ... Dijkstras algorithm, named after its discoverer, Dutch computer scientist Edsger Dijkstra, is a greedy algorithm that solves the single-source shortest path problem for a directed graph with non negative edge weights. ... A labeled tree with 6 vertices and 5 edges In graph theory, a tree is a graph in which any two vertices are connected by exactly one path. ...

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. A path vector protocol is a computer network routing protocol in which it maintains the path that update information takes as it diffuses through the network. ... In the Internet, an autonomous system (AS) is a collection of IP networks and routers under the control of one entity (or sometimes more) that presents a common routing policy to the Internet. ... In computing, inter-domain is a term used to describe interaction between domains. ...

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. Path vector routing is discussed in RFC 1322; the path vector routing algorithm is somewhat similar to the distance vector algorithm in the sense that each border router advertises the destinations it can reach to its neighboring router. However, instead of advertising networks in terms of a destination and the distance to that destination, networks are advertised as destination addresses and path descriptions to reach those destinations. A route is defined as a pairing between a destination and the attributes of the path to that destination, thus the name, path vector routing, where the routers receive a vector that contains paths to a set of destinations. The path, expressed in terms of the domains (or confederations) traversed so far, is carried in a special path attribute that records the sequence of routing domains through which the reachability information has passed. The path represented by the smallest number of domains becomes the preferred path to reach the destination.

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^[1]), and have poor convergence properties. A distance-vector routing protocol is one of the two major routing protocols used in routing of packet-switched networks in computer communications, as in for example the Routing Information Protocol for Internet traffic. ... Scale in the computing field is used as a verb. ... A distance-vector routing protocol is one of the two major classes of routing protocols used in packet-switched networks for computer communications, the other major class being the link-state protocol. ... In the absence of a more specific context, convergence denotes the approach toward a definite value, as time goes on; or to a definite point, a common view or opinion, or toward a fixed or equilibrium state. ...

This has led to the development of more complex but more scalable algorithms for use in large networks. Interior routing mostly uses link-state routing protocols such as OSPF and IS-IS. A link-state routing protocol is one of the two main classes of routing protocols used in packet-switched networks for computer communications. ... Open Shortest Path First (OSPF) is a link-state, hierarchical Interior Gateway Protocol (IGP) routing protocol. ... Is Is is Yeah Yeah Yeahs third EP, to be released on July 24, 2007. ...

A more recent development is that of 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. Enhanced Interior Gateway Routing Protocol (EIGRP) is a Cisco proprietary routing protocol based on their original IGRP. EIGRP is a distance vector routing protocol, with optimizations to minimize both the routing instability incurred after topology changes, as well as the use of bandwidth and processing power in the router. ...

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 (see e.g. this survey for a list of proposed routing metrics). The routing table stores only the best possible routes, while link-state or topological databases may store all other information as well. Bandwidth is the difference between the upper and lower cutoff frequencies of, for example, a filter, a communication channel, or a signal spectrum, and is typically measured in hertz. ... In its general sense, delay refers to a lapse of time. ... In telecommunication, the term hop count has the following meanings: In a data communications network, the number of legs traversed by a packet between its source and destination. ... In computer networking, the term Maximum Transmission Unit (MTU) refers to the size (in bytes) of the largest datagram that a given layer of a communications protocol can pass onwards. ... A Link-state routing protocol is one of the two main classes of routing protocols used in packet-switched networks for computer communications. ...

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. Cisco may refer to: Cisco Systems, a computer networking company Cisco IOS, an internet router operating system CISCO Security Private Limited, a security company in Singapore Commercial and Industrial Security Corporation, a statutory board in Singapore Abbreviation for San Francisco, California Cisco (wine) The Cisco Kid, a fictional character created... 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. ...

A local network administrator, in special cases, can setup host-specific routes to a particular machine which provides more control over network usage, permits testing and better overall security. This can come in handy when required to debug network connections or routing tables.

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. In game theory, the Nash equilibrium (named after John Forbes Nash, who proposed it) is a kind of solution concept of a game involving two or more players, where no player has anything to gain by changing only his or her own strategy unilaterally. ... Braess paradox, credited to the mathematician Dietrich Braess, states that adding extra capacity to a network can in some cases reduce overall performance. ...

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,^[2] 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. In the Internet, an autonomous system (AS) is a collection of IP networks and routers under the control of one entity (or sometimes more) that presents a common routing policy to the Internet. ... “ISP” redirects here. ... The Border Gateway Protocol (BGP) is the core routing protocol of the Internet. ... This article is about a computer networking device. ... In the jargon of routing technology, hot-potato routing is routing that forwards the packet towards the path with the lowest delay (as opposed, for example, to the more commonly used metric of least number of hops). ...

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. New York, New York and NYC redirect here. ... One millisecond is one-thousandth of a second. ... This article is about the capital of England and the United Kingdom. ...

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.^[3] Year 2003 (MMIII) was a common year starting on Wednesday of the Gregorian calendar. ...

See also

• Network address translation

In computer networking, Network Address Translation (NAT, also known as Network Masquerading, Native Address Translation or IP Masquerading) is a technique of transceiving network traffic through a router that involves re-writing the source and/or destination IP addresses and usually also the TCP/UDP port numbers of IP packets...

Routing algorithms and techniques

Adaptive routing describes the capability of a system, through which routes are characterised by their destination, to alter the path that the route takes through the system in response to a change in conditions. ... Deflection routing is a routing strategy for networks based on packet switching which does not require buffering of packets. ... Edge Disjoint Shortest Pair Algorithm The algorithm for generating a shortest pair of edge disjoint paths between a given pair of vertices is stated as follows Run the shortest pair algorithm for the given pair of vertices Replace each edge of the shortest path (equivalent to two oppositely directed arcs... Dijkstras algorithm, named after its discoverer, Dutch computer scientist Edsger Dijkstra, is a greedy algorithm that solves the single-source shortest path problem for a directed graph with non negative edge weights. ... Fuzzy routing is the application of fuzzy logic to routing protocols, particularly in the context of ad-hoc wireless networks and in networks supporting multiple quality of service classes. ... Geographic routing refers to a family of techniques to route data packets in a communication network. ... Hierarchical routing: Routing that is based on hierarchical addressing. ... An overlay network is a computer network which is built on top of another network. ... Key based routing (KBR) is a lookup method used in conjunction with distributed hash tables (DHTs). ... In computer science, Decentralized Object Location and Routing (DOLR) is a scalable, location-independent routing technology [1]. It uses location-independent names, or aliases, for each node in the network, and it is an example of peer-to-peer networking that uses a structured-overlay system called Tapestry[1]. It... Distributed hash tables (DHTs) are a class of decentralized distributed systems that provide a lookup service similar to a hash table: (name, value) pairs are stored in the DHT, and any participating node can efficiently retrieve the value associated with a given name. ... In computer networking, policy-based routing (PBR) is a technique used to make routing decisions based on policies set by the network administrator. ... In the fields of packet-switched networks and computer networking, the traffic engineering term Quality of Service, abbreviated QoS, refers to resource reservation control mechanisms. ... Static routing describes a system that does not implement adaptive routing. ...

Routing in specific networks

• Route assignment in transportation networks
• National Routeing Guide: passenger routing in the UK rail network
• Routing in the PSTN

Route assignment, route choice, or traffic assignment concerns the selection of routes (alternative called paths) between origins and destinations in transportation networks. ... The National Routeing Guide (note spelling routeing) is the definitive resource on the validity, or invalidity, of rail tickets for the purpose of rail travel in the United Kingdom; or as the Rail Regulator wrote [it] sets out passengers rights to use the network flexibly[1]. It is a book... In the context of the public switched telephone network, routing is the process by which telephone calls are routed around the telephone network. ...

Routing protocols

• Routing protocol
• Classless inter-domain routing (CIDR)
• MPLS routing
• ATM routing
• RPSL

The introduction to this article provides insufficient context for those unfamiliar with the subject matter. ... Warning! This Article contains disinformation. ... MPLS is a common abbreviation for Multiprotocol Label Switching. ... Asynchronous Transfer Mode (ATM) is a cell relay, packet switching network and data link layer protocol which encodes data traffic into small (53 bytes; 48 bytes of data and 5 bytes of header information) fixed-sized cells. ... The Routing Policy Specification Language (RPSL) is a language used by ISPs to describe their routing policies. ...

References

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

SIGCOMM is the Association for Computing Machinerys Special Interest Group on Data Communications, which specializes in the field of communication and computer networks. ...

External links

• Count-To-Infinity Problem
• "Stability Features" are ways of avoiding the "count to infinity" problem.
• Cisco IT Case Studies about Routing and Switching