Routing
Encyclopedia
Routing is the process of selecting paths in a network along which to send network traffic. Routing is performed for many kinds of networks, including the telephone network (Circuit switching
), electronic data networks
(such as the Internet
), and transportation networks
. This article is concerned primarily with routing in electronic data networks using packet switching
technology.
In packet switching networks, routing directs packet forwarding, the transit of logically addressed packets from their source toward their ultimate destination through intermediate nodes
, typically hardware devices called routers, bridges
, gateways
, firewall
s, or switches
. General-purpose computer
s 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 table
s which maintain a record of the routes to various network destinations. Thus, constructing routing tables, which are held in the router's memory
, is very important for efficient routing. Most routing algorithms use only one network path at a time, but multipath routing
techniques enable the use of multiple alternative paths.
Routing, in a more narrow sense of the term, is often contrasted with bridging
in its assumption that network address
es 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 within localized environments.
Unicast is the dominant form of message delivery on the Internet, and this article focuses on unicast routing algorithms.
(or non-adaptive routing), small networks may use manually configured routing tables. Larger networks have complex topologies
that can 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
). Adaptive routing
, or dynamic routing, attempts to solve this problem by constructing routing tables automatically, based on information carried by routing protocol
s, and allowing the network to act nearly autonomously in avoiding network failures and blockages.
Examples of adaptive-routing algorithms are the Routing Information Protocol (RIP
) and the Open-Shortest-Path-First protocol (OSPF). Adaptive routing dominates the Internet. However, the configuration of the routing protocols often requires a skilled touch; networking technology has not developed to the point of the complete automation of routing.
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".
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.
s (MPRs). MPRs distinguish OLSR from other link state routing protocols.
, 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 a 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.
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.
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 protocol
s such as OSPF and IS-IS
.
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 naive distance-vector protocols, but avoid counting to infinity, and have good worst-case convergence times.
to multiple routes, in order to select (or predict) the best route.
In the case of computer networking, the metric is computed by a routing algorithm, and can cover such information as bandwidth
, network 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.
Because 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.
A local network administrator, in special cases, can set up 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.
A classic example involves traffic in a road system, in which each driver picks a path which minimizes their own travel time. With such 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 another model, for example used for routing automated guided vehicle
s (AGVs) on a terminal, reservations are made for each vehicle to prevent simultaneous use of the same part of an infrastructure. This approach is also referred to as context-aware routing.
The Internet is partitioned into autonomous system
s (ASs) such as internet service provider
s (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, 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.
Such a mechanism was later published by the same authors, first for the case of two ISPs and then for the global case.
there has been increased interest in techniques and methods to monitor
the routing posture of networks. Incorrect routing or routing issues
cause undesirable performance degradation, flapping and/or downtime. Monitoring
routing in a network is achieved using Route analytics
tools and techniques
Circuit switching
Circuit switching is a methodology of implementing a telecommunications network in which two network nodes establish a dedicated communications channel through the network before the nodes may communicate. The circuit guarantees the full bandwidth of the channel and remains connected for the...
), electronic data networks
Computer network
A computer network, often simply referred to as a network, is a collection of hardware components and computers interconnected by communication channels that allow sharing of resources and information....
(such as the Internet
Internet
The Internet is a global system of interconnected computer networks that use the standard Internet protocol suite to serve billions of users worldwide...
), and transportation networks
Transport network
A transport network, or transportation network in American English, is typically a network of roads, streets, pipes, aqueducts, power lines, or nearly any structure which permits either vehicular movement or flow of some commodity....
. This article is concerned primarily with routing in electronic data networks using packet switching
Packet switching
Packet switching is a digital networking communications method that groups all transmitted data – regardless of content, type, or structure – into suitably sized blocks, called packets. Packet switching features delivery of variable-bit-rate data streams over a shared network...
technology.
In packet switching networks, routing directs packet forwarding, the transit of logically addressed packets from their source toward their ultimate destination through intermediate nodes
Node (networking)
In communication networks, a node is a connection point, either a redistribution point or a communication endpoint . The definition of a node depends on the network and protocol layer referred to...
, typically hardware devices called routers, bridges
Bridging (networking)
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 flooding and examination of source addresses in received packet headers to locate unknown...
, gateways
Gateway (telecommunications)
In telecommunications, the term gateway has the following meaning:*In a communications network, a network node equipped for interfacing with another network that uses different protocols....
, firewall
Firewall (computing)
A firewall is a device or set of devices designed to permit or deny network transmissions based upon a set of rules and is frequently used to protect networks from unauthorized access while permitting legitimate communications to pass....
s, or switches
Network switch
A network switch or switching hub is a computer networking device that connects network segments.The term commonly refers to a multi-port network bridge that processes and routes data at the data link layer of the OSI model...
. General-purpose computer
Computer
A computer is a programmable machine designed to sequentially and automatically carry out a sequence of arithmetic or logical operations. The particular sequence of operations can be changed readily, allowing the computer to solve more than one kind of problem...
s 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 table
Routing table
In computer networking a routing table, or Routing Information Base , is a data table stored in a router or a networked computer that lists the routes to particular network destinations, and in some cases, metrics associated with those routes. The routing table contains information about the...
s which maintain a record of the routes to various network destinations. Thus, constructing routing tables, which are held in the router's memory
Computer storage
Computer data storage, often called storage or memory, refers to computer components and recording media that retain digital data. Data storage is one of the core functions and fundamental components of computers....
, is very important for efficient routing. Most routing algorithms use only one network path at a time, but multipath routing
Multipath routing
Multipath routing is the routing technique of using multiple alternative paths through a network, which can yield a variety of benefits such as fault tolerance, increased bandwidth, or improved security. The multiple paths computed might be overlapped, edge-disjointed or node-disjointed with each...
techniques enable the use of multiple alternative paths.
Routing, in a more narrow sense of the term, is often contrasted with bridging
Bridging (networking)
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 flooding and examination of source addresses in received packet headers to locate unknown...
in its assumption that network address
Network address
Network address may refer to:*Base address*Classful address*IP address*IPX address*Logical address*Network layer address,*X.25/X.21 address*MAC address-See also:*Autonomous system *Host address*Link layer*Subnet mask...
es 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 within localized environments.
Delivery semantics
Routing schemes differ in their delivery semantics:- unicastUnicastright|200pxIn computer networking, unicast transmission is the sending of messages to a single network destination identified by a unique address.-Addressing methodologies:...
delivers a message to a single specific node; - broadcast delivers a message to all nodes in the network;
- multicastMulticastIn computer networking, multicast is the delivery of a message or information to a group of destination computers simultaneously in a single transmission from the source creating copies automatically in other network elements, such as routers, only when the topology of the network requires...
delivers a message to a group of nodes that have expressed interest in receiving the message; - anycastAnycastAnycast is a network addressing and routing methodology in which datagrams from a single sender are routed to the topologically nearest node in a group of potential receivers all identified by the same destination address.-Addressing methodologies:...
delivers a message to any one out of a group of nodes, typically the one nearest to the source. - geocastGeocastGeocast refers to the delivery of information to a group of destinations in a network identified by their geographical locations. It is a specialized form of multicast addressing used by some routing protocols for mobile ad hoc networks....
delivers a message to a geographic area
Unicast is the dominant form of message delivery on the Internet, and this article focuses on unicast routing algorithms.
Topology distribution
In a practice known as static routingStatic routing
Static routing is a data communication concept describing one way of configuring path selection of routers in computer networks. It is the type of routing characterized by the absence of communication between routers regarding the current topology of the network. This is achieved by manually adding...
(or non-adaptive routing), small networks may use manually configured routing tables. Larger networks have complex topologies
Network topology
Network topology is the layout pattern of interconnections of the various elements of a computer or biological network....
that can change rapidly, making the manual construction of routing tables unfeasible. Nevertheless, most of the public switched telephone network
Public switched telephone network
The public switched telephone network is the network of the world's public circuit-switched telephone networks. It consists of telephone lines, fiber optic cables, microwave transmission links, cellular networks, communications satellites, and undersea telephone cables, all inter-connected by...
(PSTN) uses pre-computed routing tables, with fallback routes if the most direct route becomes blocked (see routing in the PSTN
Routing in the PSTN
Routing in the PSTN is the process used to route telephone calls across the public switched telephone network. This process is the same whether the call is made between two phones in the same locality, or across two different continents....
). Adaptive routing
Adaptive routing
Adaptive routing describes the capability of a system, through which routes are characterized by their destination, to alter the path that the route takes through the system in response to a change in conditions...
, or dynamic routing, attempts to solve this problem by constructing routing tables automatically, based on information carried by routing protocol
Routing protocol
A routing protocol is a protocol that specifies how routers communicate with each other, disseminating information that enables them to select routes between any two nodes on a computer network, the choice of the route being done by routing algorithms. Each router has a priori knowledge only of...
s, and allowing the network to act nearly autonomously in avoiding network failures and blockages.
Examples of adaptive-routing algorithms are the Routing Information Protocol (RIP
Routing Information Protocol
The Routing Information Protocol is a distance-vector routing protocol, which employs the hop count as a routing metric. RIP prevents routing loops by implementing a limit on the number of hops allowed in a path from the source to a destination. The maximum number of hops allowed for RIP is 15....
) and the Open-Shortest-Path-First protocol (OSPF). Adaptive routing dominates the Internet. However, the configuration of the routing protocols often requires a skilled touch; networking technology has not developed to the point of the complete automation of routing.
Distance vector algorithms
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
When applying link-state algorithms, each node uses as its fundamental data a mapMap
A map is a visual representation of an area—a symbolic depiction highlighting relationships between elements of that space such as objects, regions, and themes....
of the network in the form of a graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
. 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
Shortest path problem
In graph theory, the shortest path problem is the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized...
algorithm such as Dijkstra's algorithm
Dijkstra's algorithm
Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree...
. The result is a tree
Tree (graph theory)
In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles 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.
Optimised Link State Routing algorithm
A link-state routing algorithm optimised for mobile ad-hoc networks is the Optimised Link State Routing Protocol (OLSR). OLSR is proactive; it uses Hello and Topology Control (TC) messages to discover and disseminate link state information through the mobile ad-hoc network. Using Hello messages, each node discovers 2-hop neighbor information and elects a set of multipoint relayMultipoint relay
Multi Point Relays are nodes in wireless Ad-Hoc networks that do the job of relaying messages between nodes, they also have the main role in routing and selecting the proper route from any source to any desired destination node - Arash Modaresi....
s (MPRs). MPRs distinguish OLSR from other link state routing protocols.
Path vector protocol
Distance vector and link state routing are both intra-domain routing protocols. They are used inside an autonomous systemAutonomous system (Internet)
Within the Internet, an Autonomous System is a collection of connected Internet Protocol routing prefixes under the control of one or more network operators that presents a common, clearly defined routing policy to the Internet....
, but not between autonomous systems. Both of these routing protocols become intractable in large networks and cannot be used in Inter-domain
Inter-domain
inter-domain is a term used to describe data flow control and interaction between Primary Domain Controller computers. This type of computer uses various computer protocols and services to operate. It is most commonly used to multicast between internet domains.-Internet use:An Internet service...
routing. Distance vector routing is subject to instability if there are more than a 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.
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.
Comparison of routing algorithms
Distance-vector routing protocols are simple and efficient in small networks and require little, if any, management. However, traditional distance-vector algorithms have poor convergence properties due to the count-to-infinity problem.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 protocol
Link-state routing protocol
A link-state routing protocol is one of the two main classes of routing protocols used in packet switching networks for computer communications . Examples of link-state routing protocols include OSPF and IS-IS....
s such as OSPF and IS-IS
IS-IS
Intermediate System To Intermediate System , is a routing protocol designed to move information efficiently within a computer network, a group of physically connected computers or similar devices....
.
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 naive distance-vector protocols, but avoid counting to infinity, and have good worst-case convergence times.
Path selection
Path selection involves applying a routing metricMetrics (networking)
Metrics is a property of a route in computer networking, consisting of any value used by routing algorithms to determine whether one route should perform better than another. The routing table stores only the best possible routes, while link-state or topological databases may store all other...
to multiple routes, in order to select (or predict) the best route.
In the case of computer networking, the metric is computed by a routing algorithm, and can cover such information as bandwidth
Bandwidth (computing)
In computer networking and computer science, bandwidth, network bandwidth, data bandwidth, or digital bandwidth is a measure of available or consumed data communication resources expressed in bits/second or multiples of it .Note that in textbooks on wireless communications, modem data transmission,...
, network delay
Network delay
Network delay is an important design and performance characteristic of a computer network or telecommunications network. The delay of a network specifies how long it takes for a bit of data to travel across the network from one node or endpoint to another. It is typically measured in multiples or...
, hop count
Hop count
In computer networking, hop count refers to the number of routers through which data must pass between source and destination. Each router along the data path constitutes a hop, as the data is moved from one Layer 3 network to another...
, 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.
Because 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
Cisco
Cisco may refer to:Companies:*Cisco Systems, a computer networking company* Certis CISCO, corporatised entity of the former Commercial and Industrial Security Corporation in Singapore...
's routers, for example, attribute a value known as the administrative distance
Administrative distance
Administrative distance is the measure used by Cisco 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...
to each route, where smaller administrative distances indicate routes learned from a supposedly more reliable protocol.
A local network administrator, in special cases, can set up 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 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 picks a path which minimizes their own travel time. With such routing, the equilibrium
Nash equilibrium
In game theory, Nash equilibrium is a solution concept of a game involving two or more players, in which each player is assumed to know the equilibrium strategies of the other players, and no player has anything to gain by changing only his own strategy unilaterally...
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 another model, for example used for routing automated guided vehicle
Automated Guided Vehicle
An automated guided vehicle or automatic guided vehicle is a mobile robot that follows markers or wires in the floor, or uses vision or lasers. They are most often used in industrial applications to move materials around a manufacturing facility or a warehouse...
s (AGVs) on a terminal, reservations are made for each vehicle to prevent simultaneous use of the same part of an infrastructure. This approach is also referred to as context-aware routing.
The Internet is partitioned into autonomous system
Autonomous system (Internet)
Within the Internet, an Autonomous System is a collection of connected Internet Protocol routing prefixes under the control of one or more network operators that presents a common, clearly defined routing policy to the Internet....
s (ASs) such as internet service provider
Internet service provider
An Internet service provider is a company that provides access to the Internet. Access ISPs directly connect customers to the Internet using copper wires, wireless or fiber-optic connections. Hosting ISPs lease server space for smaller businesses and host other people servers...
s (ISPs), each of which has control over routes involving its network, at multiple levels. First, AS-level paths are selected via the BGP
Border Gateway Protocol
The Border Gateway Protocol is the protocol backing the core routing decisions on the Internet. It maintains a table of IP networks or 'prefixes' which designate network reachability among autonomous systems . It is described as a path vector protocol...
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, 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
New York City
New York is the most populous city in the United States and the center of the New York Metropolitan Area, one of the most populous metropolitan areas in the world. New York exerts a significant impact upon global commerce, finance, media, art, fashion, research, technology, education, and...
, connected by a fast link with latency 5 ms
Millisecond
A millisecond is a thousandth of a second.10 milliseconds are called a centisecond....
; and which each have a presence in London
London
London is the capital city of :England and the :United Kingdom, the largest metropolitan area in the United Kingdom, and the largest urban zone in the European Union by most measures. Located on the River Thames, London has been a major settlement for two millennia, its history going back to its...
connected by a 5 ms link. Suppose both ISPs have trans-Atlantic links connecting their two networks, but A
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.
Such a mechanism was later published by the same authors, first for the case of two ISPs and then for the global case.
Route Analytics
As the Internet and IP networks become mission critical business tools,there has been increased interest in techniques and methods to monitor
the routing posture of networks. Incorrect routing or routing issues
cause undesirable performance degradation, flapping and/or downtime. Monitoring
routing in a network is achieved using Route analytics
Route analytics
Route analytics is an emerging network monitoring technology specifically developed to analyze the routing protocols and structures in meshed IP Networks...
tools and techniques
Routing in specific networks
- Route assignmentRoute assignmentRoute assignment, route choice, or traffic assignment concerns the selection of routes between origins and destinations in transportation networks. It is the fourth step in the conventional transportation forecasting model, following trip generation, trip distribution, and mode choice...
in transportation networks - National Routeing GuideNational Routeing GuideThe National Routeing Guide is a document, the definitive resource on the validity of rail tickets for the purpose of rail travel in England, Wales, and Scotland . As stated by the Rail Regulator, "[it] sets out passengers' rights to use the network flexibly"...
: passenger routing in the UK rail network - Routing in the PSTNRouting in the PSTNRouting in the PSTN is the process used to route telephone calls across the public switched telephone network. This process is the same whether the call is made between two phones in the same locality, or across two different continents....
- Small world routingSmall world routingIn network theory, small world routing refers to routing methods for small-world networks. Networks of this type are peculiar in that relatively short paths exist between any two nodes...
- the internet is approximately a small world network
Routing protocols
- Routing protocolRouting protocolA routing protocol is a protocol that specifies how routers communicate with each other, disseminating information that enables them to select routes between any two nodes on a computer network, the choice of the route being done by routing algorithms. Each router has a priori knowledge only of...
- Classless inter-domain routingClassless Inter-Domain RoutingClassless Inter-Domain Routing is a method for allocating IP addresses and routing Internet Protocol packets. The Internet Engineering Task Force introduced CIDR in 1993 to replace the previous addressing architecture of classful network design in the Internet...
(CIDR) - MPLSMultiprotocol Label SwitchingMultiprotocol Label Switching is a mechanism in high-performance telecommunications networks that directs data from one network node to the next based on short path labels rather than long network addresses, avoiding complex lookups in a routing table. The labels identify virtual links between...
routing - ATMAsynchronous Transfer ModeAsynchronous Transfer Mode is a standard switching technique designed to unify telecommunication and computer networks. It uses asynchronous time-division multiplexing, and it encodes data into small, fixed-sized cells. This differs from approaches such as the Internet Protocol or Ethernet that...
routing - RPSL
- RSMLT
- Routing in optical mesh networkOptical mesh networkOptical mesh networks are a type of telecommunications network.Transport networks, the underlying optical fiber-based layer of telecommunications networks, have evolved from DCS -based mesh architectures in the 1980s, to SONET/SDH ring architectures in the 1990s...
s
Router Platforms
- Network operating systemNetwork operating systemA networking operating system , also referred to as the Dialoguer, is the software that runs on a server and enables the server to manage data, users, groups, security, applications, and other networking functions...
- NOS - XORPXORPXORP is an open source Internet Protocol routing software suite originally designed at the International Computer Science Institute in Berkeley, California...
- the eXtensible Open Router Platform - JunosJunosJuniper Junos is the software or the network operating system used in Juniper Networks hardware systems. It is an operating system that is used in Juniper's routing, switching and security devices. Juniper offers a Software Development Kit to partners and customers to allow additional customization...
- Cisco IOSCisco IOSCisco IOS is the software used on the vast majority of Cisco Systems routers and current Cisco network switches...
- NX-OSNX-OSNX-OS is a network operating system designed by Cisco Systems for their own Nexus series Ethernet switches and MDS series Fibre Channel storage area network switches. NX-OS is designed to support high performance, high reliability server access switches used in the data center...
- CatOS
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