Routing Fundamentals

Routing Fundamentals

What is Routing

Routing is the process of moving a packet of data from one network to another network based on the destination IP address. The Internet uses routing to move data from your computer, across several networks, to reach a final destination, like a website. Specialized computer devices that perform this routing function are referred to as routers.

Routers use the information contained in a route to make decisions about which network interface to forward a packet through in order to reach the destination address in the packet. Routers maintain a list of routes which is often referred to as a Routing table.

Routers look up routes in the routing table to figure out how to move data from one network to another network. Routes are simply the signposts that tell a router which network interface to forward a packet through in order to reach the packet's intended destination.

Types of Routes

There are two basic kinds of routes: static or dynamic.

Static Routes

Routes can be entered into a router by a person who administrates the network (the network administrator). Since these routes are entered by the administrator, and these routes don't change until the administrator changes them, they are referred to as static routes.

Cisco devices (and several other routing devices) use the following command to configure a static route:

ip route <destination network address> <network mask> <gateway/router address> <weight>

Example:   ip route 192.168.1.0 255.255.255.0 192.168.1.1

NULL ROUTES

A static route which points to the null 0 interface on a Cisco router is called a null route. Null routes are used to cause packets that have been sent to an unreachable network to be dropped from the network thereby preventing those packets from consuming bandwidth.

DEFAULT ROUTES

A default route is also referred to as the 'route of last resort'. This is the route a router uses when all other routes have been examined and none seem to be the right route to use.

Dynamic Routes

If the routes are learned on-the-fly from other routers, it is called a dynamically-learned route, or a dynamic route for short. Dynamic routes are learned from routing protocols.

Router

A router is specialized equipment connected to more than one network. It runs software that allows it to move data from one network to another. Routers operate at the network layer (OSI Model - Layer 3). The primary function of a router is to connect networks together and keep Layer 2 broadcast traffic under control.

WHY IS A ROUTER NECESSARY

Routers perform the following functions:

1. Restrict network broadcasts to the local LAN
2. Act as the default gateway.
3. Move data between networks
1. Routing
2. Protocol Translation
4. Best Path Calculations
5. Route Advertisement

Restrict Broadcasts to the LAN

Networks use broadcast traffic (transmissions sent to all hosts on the network) to communicate certain kinds of information that makes the network function (ARP, RARP, DHCP, IPX-SAP broadcasts etc.). As the number of hosts on the network increases, the amount of what is called "broadcast" traffic increases. If enough broadcast traffic is present on the network, then ordinary communication across the network becomes difficult.

To reduce broadcasts, a network administrator can break up a network with a large number of hosts into two smaller networks. Broadcasts are then restricted to each network, and the router performs as the 'default gateway' to reach the hosts on the other networks.

Act as the Default Gateway

Especially in today's networks, people are connecting to the Internet. When your computer wants to talk to a computer on another network, it does so by sending your data to the default gateway (your router). The router receives your data, looks for the destination address of the remote computer you're communicating with (a web server for example). The router makes a forwarding decision and forwards your data out a different network interface that is closer to that remote computer. When communicating across the Internet, there are always several routers between you and the remote computer, so several routers will take part in handing off the packet, much like a fireman's bucket brigade.

Move Data between Networks

The primary function of a router is to move packetized data from one network to another. This allows two networks managed by different organizations to exchange data. Because a router can accept data from any type of network it is attached to, and forward it to any other network, it can also allow networks that could not normally communicate with each other to exchange data.

When a packet reaches the router, the router can look at the network layer information in the packet and decide which network to forward the packet to. This process of reading the network layer information, performing a lookup of the network address and then making a forwarding decision based on the destination network address is called routing.

Protocol Translation

A router can take in an Ethernet frame, strip the Ethernet data away and then drop the IP data into a frame of another type. In this way a router can also perform 'protocol conversion' (such as converting Ethernet frames to Serial or Token Ring frames), provided the router has the appropriate hardware and software to support protocol conversion. The whole point of a router however, is to forward packetized data from the interface it received that data on, to another interface on the router that retransmits the received data onto the next network. Switches forward data based on the physical address (usually the MAC address) in the frame. Routers differ from switches because they make a routing decision based on the logical address in a packet, reformat the packet and then retransmit the packet on a different network.

Route Advertisement

Over time, routing protocols (RIP, OSPF, IS-IS, IGRP, EIGRP, BGP) have been invented so that very large network systems with lots of sub-networks can automatically learn where the various networks are tell other routers and move data between them automatically. This is how data makes it across the Internet.

Calculate the Best Path

All routers make decisions about the best path to reach a destination network. This process is determined by the administrator, or by the routing protocol being used. Routers that are connected to several other routers often participate in exchanging routes using a dynamic routing protocols such as RIP, OSPF, IS-IS, EIGRP or BGP. Routers learn about which networks exist from each other and make internal calculations, based in the routing information they receive, as to which path is the shortest to a remote network.  

Routing Protocol

A routing protocol is a standardized process by which routers learn and communicate connectivity information, called routes, each of which describes how to reach a destination  host and network. Routers that wish to exchange routing information must use the same routing protocol to communicate routing information.

ROUTING PROTOCOLS  are used by routers to dynamically learn all paths through a set of networks and forward data between the networks. Routing protocols are the software that allow routers to dynamically advertise and learn routes, determine which routes are available and which are the most efficient routes to a destination. Routing protocols used by the Internet Protocol suite include:

• Routing Information Protocol (RIP and RIP II)
• Open Shortest Path First (OSPF)
• Intermediate System to Intermediate System (IS-IS)
• Interior Gateway Routing Protocol (IGRP)
• Cisco's Enhanced Interior Gateway Routing Protocol (EIGRP)
• Border Gateway Protocol (BGP)

ROUTED PROTOCOLS

ROUTED PROTOCOLS are nothing more than data being transported across the networks. Routed protocols include:

• Internet Protocol
• Telnet
• Remote Procedure Call (RPC)
• SNMP
• SMTP
• Novell IPX
• Open Standards Institute networking protocol
• DECnet
• Appletalk
• Banyan Vines
• Xerox Network System (XNS)

Outside a network, specialized devices called ROUTERS are used to perform the routing process of forwarding packets between networks. Routers are connected to the edges of two or more networks to provide connectivity between them. These devices are usually dedicated machines with specialized hardware and software to speed up the routing process. These devices send and receive routing information to each other about networks that they can and cannot reach. Routers examine all routes to a destination, determine which routes have the best metric, and insert one or more routes into the IP routing table on the router. By maintaining a current list of known routes, routers can quick and efficiently send your information on it's way when received.

There are many companies that produce routers: Cisco, Juniper, Bay, Nortel, 3Com, Cabletron, etc. Each company's product is different in how it is configured, but most will interoperate so long as they share common physical and data link layer protocols (Cisco HDLC or PPP over serial, Ethernet etc.).

NON-ROUTABLE PROTOCOLS

NON-ROUTABLE PROTOCOLS cannot survive being routed. Non-routable protocols presume that all computers they will ever communicate with are on the same network (to get them working in a routed environment, you must bridge the networks). Today’s modern networks are not very tolerant of protocols that do not understand the concept of a multi-segment network and most of these protocols are dying or falling out of use.

• NetBEUI
• DLC
• LAT
• DRP
• MOP

What is Convergence

Dynamic routing protocols calculate routes by advertising the networks they are connected to and the routes they use to reach other routers connected to more networks. Once all the routers in a network know all routes to all destinations, the routing protocol has said to have 'converged'. If a user were to attempt to reach a destination before the routing protocol converged, the data might never get to its destination. There are two problems that occur when a network is having difficulty reaching the state of convergence: routing loops and black holes.

Routing Loops

If a packet reaches a router which does not know how to get to the destination and get dropped, or the packet might get forwarded through a circle of routers in what is called a 'routing loop'. If that happened, the packet would simply run around in circles till it grew old and died. Fortunately, most data is given a time to live. When data is forwarded from one router to the next, one more tick is taken off it's time to live. Eventually that time to live reaches zero and the data is thrown away. This prevents the network from becoming congested.

Black Holes

Black holes are what happens when a route sends data to the wrong place or can't get to the destination. The data is simply dropped and vanishes from the network. Packets go in and they don't come out. Nearly all 'black holes' are unintentional and are caused by problems occurring on the network. However, Internet providers will sometimes intentionally black hole destinations belonging to those who abuse their Internet privileges ( ex. Spammers). 

Why don't networks converge

When an interface on a router is rendered inoperable for any reason (the interface breaks or burns out, the connector gets bent, the cable breaks etc.), the routes pointing data to that interface are withdrawn from that router's announcements to other routers; thus, convergence can be a difficult thing to achieve on a network with very low reliability.

What are Advertisements

Advertisements are messages sent between routers that pass on information about how to reach destinations. Some routing protocols advertise the complete list of known routes, some protocols only advertise summarized lists of routes, or changes.

What are Metrics

Routing metrics are a scoring system for routes used to indicate how good or bad the route is. Metrics are calculated by routers to prioritize routes from best to worst. Routers use the metrics to select the best possible route or routes to a given destination. Metrics can include hop count (how many stops there are between here and the destination), media type (serial, FDDI, Token Ring, Ethernet, SONET etc.), availability (whether the machine is up or down) and several other factors including some set by the Network Administrator. A lower metric generally indicates a better route.

Static Routing

Static routing is not really a routing protocol. Static routing is simply the process of manually entering routes into a device's routing table via a configuration file that is loaded when the routing device starts up. As an alternative, these routes can be entered by a network administrator who configures the routes manually. Since these manually configured routes don't change after they are configured (unless a human changes them) they are called 'static' routes.

Static routing is the simplest form of routing, but it is a manual process.

Use static routing when you have very few devices to configure (<5) and when you know the routes will probably never change.

Static routing also does not handle failures in external networks well because any route that is configured manually must be updated or reconfigured manually to fix or repair any lost connectivity.

  

Dynamic Routing

Dynamic routing protocols are supported by software applications running on the routing device (the router) which dynamically learn network destinations and how to get to them and also advertise those destinations to other routers. This advertisement function allows all the routers to learn about all the destination networks that exist and how to  those networks.

A router using dynamic routing will 'learn' the routes to all networks that are directly connected to the device. Next, the router will learn routes from other routers that run the same routing protocol (RIP, RIP2, EIGRP, OSPF, IS-IS, BGP etc). Each router will then sort through it's list of routes and select one or more 'best' routes for each network destination the router knows or has learned.

Dynamic routing protocols will then distribute this 'best route' information to other routers running the same routing protocol, thereby extending the information on what networks exist and can be reached. This gives dynamic routing protocols the ability to adapt to logical network topology changes, equipment failures or network outages 'on the fly'.

Single Path protocols learn routes and select a single best route to each destination. These protocols are incapable of load balancing traffic. An example of a single-path protocol is Border Gateway Protocol (BGP). BGP will advertise only the single best path it knows to a destination. It will only insert a single path to a destination in the IP routing table.

Multi-path protocols learn routes and can select more than one path to a destination. These protocols are better for performing load balancing. OSPF, RIP and several other protocols will learn several best paths and will route traffic accordingly, dividing up the bandwidth based on the protocol's metrics, or on the administrator's configuration.

Routing is unnecessary unless you have multiple networks on different address ranges different combinations of IP addresses and subnet masks, for example). If you don't, you need to look at bridging or switching. You don't need to run a routing protocol unless you have multiple networks served by more than one router (and even then, manual static routes are easier for small networks). Once you get beyond three routers, it's time to start thinking about dynamic routing protocols. If you are connecting your networks to the Internet, you will also need to think about running more than one kind of routing protocol.

INTERIOR GATEWAY PROTOCOLS

Interior Gateway Protocols (IGPs) handle routing within an Autonomous System (one routing domain). In plain English, IGP's figure out how to get from place to place between the routers you own. These dynamic routing protocols keep track of paths used to move data from one end system to another inside a network or set of networks that you administrate (all of the networks you manage combined are usually just one Autonomous System). IGP's are how you get all the networks communicating with each other.

IGP's fall into two categories:

  Distance Vector Protocols

     Routing Information Protocol (RIP)

     Interior Gateway Routing Protocol (IGRP)

  Link State Protocols 

     Open Shortest Path First (OSPF)

     Intermediate System to Intermediate System (IS-IS)

EXTERIOR GATEWAY PROTOCOLS

To get from place to place outside your network(s), i.e. on the Internet, you must use an Exterior Gateway Protocol. Exterior Gateway Protocols handle routing outside an Autonomous System and get you from your network, through your Internet provider's network and onto any other network.

BGP is used by companies with more than one Internet provider to allow them to have redundancy and load balancing of their data transported to and from the Internet.

Examples of an EGP:

    Border Gateway Protocol (BGP)

    Exterior Gateway Protocol (Replaced by BGP)

Flat vs. Hierarchical Routing Protocols

FLAT

Flat routing protocols distribute information as needed to any router that can be reached or receive information. No effort is made to organize the network or its traffic, only to discover the best route hop by hop to a destination by any path. Think of this as all routers sitting on a flat geometric plane. Routing Information Protocol (RIP) is an example of a flat routing protocol.

HIERARCHICAL

Hierarchical routing protocols often group routers together by function into a hierarchy. A hierarchical protocol allows an administrator to make best use of his fast powerful routers as backbone routers, and the slower, lower powered routers may be used for access purposes. In this way, the access routers form the first tier of the hierarchy, and the backbone routers form the second tier. Hierarchical protocols make an effort to keep local traffic local, that is, they will not forward traffic to the backbone if it is not necessary to reach a destination. Some hierarchical protocols also perform route aggregation to reduce the number of routes advertised (only summary routes are advertised).

Connections and data flow through the access routers, and only enter the backbone when trying to reach distant parts of the network that have no local connections other than the backbone routers. This allows traffic to flow freely locally, and concentrates long distance data onto the backbone links to flow efficiently to the opposite side minimizing congestion.

Open Shortest Path First (OSPF) and Intermediate-system to Intermediate-System (IS-IS) are two routing protocols that can be configured to organize a network hierarchically.

Overview

"Distance Vector" and "Link State" are terms used to describe routing protocols which are used by routers to forward packets between networks. The purpose of any routing protocol is to dynamically communicate information about all network paths used to reach a destination and to select the from those paths, the best path to reach a destination network. The terms distance vector and link state are used to group routing protocols into two broad categories based on whether the routing protocol selects the best routing path based on a distance metric (the distance) and an interface (the vector), or selects the best routing path by calculating the state of each link in a path and finding the path that has the lowest total metric to reach the destination.

DISTANCE VECTOR

Distance

Distance is the cost of reaching a destination, usually based on the number of hosts the path passes through, or the total of all the administrative metrics assigned to the links in the path.

Vector

From the standpoint of routing protocols, the vector is the interface traffic will be forwarded out in order to reach an given destination network along a route or path selected by the routing protocol as the best path to the destination network.

Distance vector protocols use a distance calculation plus an outgoing network interface (a vector) to choose the best path to a destination network. The network protocol (IPX, SPX, IP, Appletalk, DECnet etc.) will forward data using the best paths selected.

Common distance vector routing protocols include:

• Appletalk RTMP
• IPX RIP
• IP RIP
• IGRP

Advantages of Distance Vector Protocols

Well Supported Protocols such as RIP have been around a long time and most, if not all devices that perform routing will understand RIP.

 

LINK STATE  

Link State protocols track the status and connection type of each link and produces a calculated metric based on these and other factors, including some set by the network administrator. Link state protocols know whether a link is up or down and how fast it is and calculates a cost to 'get there'. Since routers run routing protocols to figure out how to get to a destination, you can think of the 'link states' as being the status of the interfaces on the router. 

Link State protocols will take a path which has more hops, but that uses a faster medium over a path using a slower medium with fewer hops.

Because of their awareness of media types and other factors, link state protocols require more processing power (more circuit logic in the case of ASICs) and memory. Distance vector algorithms being simpler require simpler hardware.

 A Comparison: Link State vs. Distance Vector

See Fig. 1-1 below. If all routers were running a Distance Vector protocol, the path or 'route' chosen would be from A  B directly over the ISDN serial link, even though that link is about 10 times slower than the indirect route from A  C  D  B.

A Link State protocol would choose the A  C  D  B path because it's using a faster medium (100 Mb ethernet). In this example, it would be better to run a Link State routing protocol, but if all the links in the network are the same speed, then a Distance Vector protocol is better.

FIG. 1-1

Source routing originates from the days when routers did not exist and hosts had to know how to reach the destination computers they were communicating with. This was most common in networks utilizing mainframes.

Source routing is handled by the end station (a computer, workstation or mainframe). Each end station keeps track of the paths to all destinations it needs to reach. All routing intelligence is in the transmitting host. Source routing protocols generally do a better job of picking the best path, however source routing protocols usually require a lot of traffic transmission to discover these paths. Often the end station hardware needs to be a bit more sophisticated (better CPU and more RAM) to be able to process this routing information and choose optimal paths to a destination.

A default gateway is the router to which your computer addresses packet information for data destined for a computer on another network.

If you have a set of computers that can talk to each other directly, you have a network. For computers on your network to talk to computers on another network, you need a default gateway. The default gateway is a computer to which other local computers send data that is destined for a non-local computer. On computers running IP, a default gateway address is needed to reach all computers that are not on the same local IP subnet. Traditionally, the network administrator configures a computer with routing capability with first address in a range of IP addresses as the default gateway and points all clients at it.

When computers attempt to communicate with other computers that are not local to the IP address range they belong to (the subnet they belong to), the local computers must send their data to the default gateway to be forwarded. This occurs as follows:

1. Is the remote computer's IP address on the same subnet?
2. YES. Use ARP to get the remote computer's physical address (MAC address).
3. NO. Use ARP to get the default gateway's physical address (MAC address).
4. Construct a physical frame containing:
1. The physical frame will be addressed to the physical address gathered in either step 2 or 3.
2. The payload of the physical/data link layer frame will contain the IP header which will contain the remote computer's IP address
• 
  
5. Transmit the frame
6. If the frame is addressed to the default gateway, the gateway will receive the packet, find a route that matches the remote computer's IP address.