Internetworking Basics

  •  

     Chapter 10


    Routing Fundamentals

    These notes guide you through the basics of routing.

    Introduction

    Routing 
            Routed vs Routing Protocols
            Routing vs Switching
            Routing Tables

    Routing Protocol Overview  
            Interior Routing Protocols
            Exterior Routing Protocols
            Dynamic and Static Routing

    How Routing Protocols Work 
            Routing Metric and Algorithms
            Distance-Vector Approach
            Link-State Approach
            VLSM

    Common Routing Protocols
            RIP
            IGRP
            EIGRP
            OSPF
            IS-IS
            BGP
            Routing Protocols Summary

    Summary

     
     

    Introduction

    On completion of these notes you should be able to...

    • Describe the purpose of routing.
    • Explain the difference between routed and routing protocols
    • Understand the basic differences between OSI Layer 2 switching and Layer 3 routing
    • Understand the purpose of routing protocols and how routing tables are built
    • Describe the difference between interior and exterior routing protocols
    • Explain the difference between static and dynamic routing
    • Understand the role of metrics in path selection
    • Describe the difference between distance-vector and link-state routing
    • Give examples of commonly used routing protocols
     

    Routing

    Routing involves moving information across networks using the most efficient path possible. As an OSI Layer 3 process, routing decisions are made using logical addressing information. The main device that routes data is the router and the most common logical addressing information used is the IP address contained in a TCP/IP packet, although Novell's IPX is another contender.

    A router is an important networking device. It can be used to divide a network into subnets, creating separate broadcast domains, increasing security and available bandwidth. It is used on the Internet to route data between different networks. A router needs to be able to...

    • maintain routing tables so it knows how to reach other networks
    • use it's routing table to calculate the best route for forwarding a packet to it's destination
    • send and receive routing information from other routers

    One of the main advantages of routers is that they can deal with hierarchal addressing schemes. On the Internet, data is routed from from router to router based on the IP address class contained in the packet. When the data arrives at the destination network, then more specific information such as subnet or host address can be used to send the data to the exact destination. The ability of routers to deal with groups of addresses means that they do not have to maintain huge routing tables, containing the address of every host in the world.

    Now, before going into details on routing, it is best to be clear in the terminology. The term network segment usually means a single cable link or a single collision domain. The term subnet or subnetwork usually means a single broadcast domain. An internetwork is just a very large network containing smaller networks. The terms routing protocol and routed protocol can also be confused and are explained next.

    ~~ Routed vs Routing Protocols ~~

    It is important not to confuse routing protocols with routed protocols. A routing protocol allows routers to figure out routing paths within an internetwork, whereas a routed protocol is simply a protocol than can be routed.

    ~~ Routed protocols ~~

    A routed protocol is a protocol that can be routed by a router, meaning it can be forwarded from one network or subnetwork to another. Some protocols can be routed, others cannot.

    • IP, IPX, Banyan VINES, XNS, DECnet and AppleTalk are examples of routable protocols; these types of packets can be forwarded from network to network.
        
    • NetBEUI, a protocol used by Microsoft Windows networking, is an examples of a non-routable protocol. Non-routable packets must stay within the same subnetwork; in other words, they cannot leave the broadcast domain where they were generated.

    ~~ Routing protocols ~~

    Routing protocols enable information about routes to be exchanged between routers. The routing protocol a router runs, calculates the best path for forwarding data and ensures that routing information is sent regularly between routers, so that information about known networks can be shared. This allows routers to build up information about network topologies and keep information about routes up-to-date.

    ~~ Routing vs Switching ~~

    You should recall that switches use OSI layer 2 MAC addresses to make forwarding decisions. If one host knows another host's IP address but not it's MAC address, a broadcast message called an ARP request is sent out, asking for the MAC address of that host. The broadcast message will reach all hosts within the broadcast domain.

    When a network contains one or more routers, the broadcast domain is divided into smaller broadcast domains. Each broadcast domain is effectively isolated from every other broadcast domain by the router. Routers are necessary when a network is subdivided into subnets and so each subnet is also a separate broadcast domain.

    If a packet is destined for host on a different network or subnetwork, it must be forwarded through the local router - the gateway router. The gateway router is the way out onto another network or subnetwork. Now, both switches and routers maintain tables to help make forwarding decisions. You may recall that a switch maintains a MAC address table and can forward data between network segments. However, a router maintains an ARP table and a routing table and can forward data between networks or subnetworks.

    A router's ARP table is intended to maintain information about the local network or subnetwork. The MAC/IP address of the device attached to each ethernet port on a router is recorded. This helps the router with Layer 2 communication on the local network or subnetwork - in other words, the local broadcast domain. However, another table, the routing table is required for routing information between networks or subnetworks.

    ~~ Routing Tables ~~

    To allow information to be passed outside the local broadcast domain to other networks or subnetworks, a routing table is maintained. Each entry in the routing table contains information about any reachable network the router has learned about, including the network address, hop count to the network, the interface for the link and how the information about the network was obtained. An example routing table is given below.

    Learned
    Network Address
    Hop
    Interface
    C
           10.0.10.0
    0
        Eth0
    C
           10.0.11.0
    0
        Eth1
    C
           200.200.4.0
    0
        S0
    R
           10.0.20.0
    1
        S0
    R
           10.0.21.0
    1
        S0

    The first row of the table states that network 10.0.10.0 is on interface Eth0 and the C in the 'Learned' column means the information was learned through a direct connection; in other words, the network is local to the router. The last row states that network 10.0.21.0 is on interface S0 and the R in the 'Learned' column means the information was learned through a routing protocol, in this case, the network is not local to the router. The picture below illustrates the network topology.

     

    Routing Protocol Overview

    The Internet is a collection of many independent networks. A network can be considered to be independent if it is under the control of a single administration entity - typically networks controlled by Internet service providers or very large organizations. Each independent network can be considered autonomous and is referred to as an autonomous system (AS.) Routing protocols are needed by routers internal and external to autonomous systems.

    ~~ Interior Routing Protocols ~~

    The routing protocol on one particular autonomous system (AS) can be different to that used on another system. A routing protocol used within an AS is referred to as an Internal Gateway Protocol (IGP). Examples of IGP's in use today are RIP, IGRP, EIGRP, IS-IS and OSPF.

    ~~ Exterior Routing Protocols ~~

    For routing between each autonomous system, another type of routing protocol is required - an Exterior Gateway Protocol (EGP) - often referred to as an inter-AS routing protocol. The most common EGP used today is Border Gateway Protocol (BGP.) The Internet Assigned Numbers Authority (IANA), the body that regulates the assignment of IP addresses, allocates a unique 16-bit number to each AS, known as the autonomous system number. BGP uses autonomous number information to route traffic between autonomous systems.

    ~~ Dynamic and Static Routing ~~

    Suppose you have a small network with a few routers and you are confident your network topology will remain unchanged for a long while yet. In such a case, for packets to be routed between your subnetworks you could manually configure each router, telling it the path to each subnetwork. This type or routing is called static routing; where fixed routes are manually entered into a routing table by an administrator. The drawback of static routing is that the routing table must be manually updated if the network topology changes. Thus, static routing is not suitable for large networks, or networks subject to lot of changes.

    Dynamic routing allows routers to automatically discover routes and create routing tables without manual configuration. Should the state of a network change, routing information updates are sent between routers allowing automatic discovery of these changes. Thus, dynamic routing is more suitable for larger networks or networks subject to lots of changes.

    With dynamic routing, routers constantly tell each other about routes through the network. They send messages to each other. The exact format of a message is controlled by the routing protocol used. Each router in an internetwork keeps the information on all networks in the internetwork within it's routing table and this allows it to accurately calculate the best path to a destination.

     

    How Routing Protocols Work

    You may well ask - how do routers select the best path amongst many paths to a destination? Well, I would ask you - how would you find the perfect path from a source to a destination? If you travel on the London Underground then you can answer that immediately - I hear you muttering about factors such as congestion, reliability, number of stops along a route etc. Routers can be configured to consider the same sort of factors - hop count, bandwidth, link delay, load and reliability of each link in a path. These factors are called metrics and each routing protocol comes with a built-in algorithm that uses one or more metric values to rate each path, enabling the best path to be selected out of many.

    ~~ Routing Metrics and Algorithms ~~

    Every routing protocol uses an algorithm to calculate the best path to a destination. Moreover, every routing algorithm uses metrics to calculate path costs. Metrics are simply values, such as hop count, bandwidth, delay, reliability and load. The metrics used depend on the routing protocol. For example, RIP uses the hop count metric only. IGRP uses bandwidth and delay by default although it can be configured to use other metrics too. The metrics most commonly used by routing protocols are shown below:-

    • Hop Count:
    the number of routers a packet has to travel through to reach it's destination
    • Bandwidth
    the capacity of a link, e.g. 10Mbps
    • Delay:
    how long it takes to move a packet across the link; this is dependent on factors such as bandwidth, congestion and, physical distance
    • Reliability:
    the error rate of the link
    • Load:
    how much the link is in active use
    • Cost:
    an arbitrary value that can be assigned by a network administrator

    A number of different routing protocols have been developed, as you will see later. However, each routing protocol will likely be categorized as either a distance-vector or link-state, which are two different methods of routing with respect to the complexity of metrics used and the regularity with which routers send routing table updates to their neighbours.

    ~~ Distance-Vector Approach ~~

    The distance-vector routing approach uses the distance to a link in an internetwork as it's routing metric. Distance can be hops or a combination of metrics calculated to represent a distance value; the further the distance, the higher the overall metric cost. Examples of distance-vector routing protocols and the metrics each one uses are:

    • RIP v1  (metric: hops used)
    • RIP v2  (metric: hops used)
    • IGRP    (metric: bandwidth and delay used)

    Whichever metrics are used to calculate distance, the path with the lowest cost is chosen as the best path. If hop count is used as the metric, then a path cost is the number of hops (routers) to the destination. All hops are seen as equal, regardless if any hop is slower than another. Routes with the lowest hop count are preferred.

    One major hallmark of a distance-vector routing protocol is that the routing algorithm ensures that routing table updates are sent by each router to neighbouring routers periodically. With this approach, a router passes it's routing table to its neighbours, telling them what it thinks the whole network looks like. When a router receives a neighbour's routing table, it can update it's own if necessary. These periodic updates can occur up to every 30 seconds and are good for ensuring a router has an up-to-date view of the network, but the downside is they occur even if no changes have occurred in the network topology.

    ~~ Link-State Approach ~~

    The link-state routing approach also favours paths with the lowest cost within an internetwork. Link-state routers are passed link information from neighbours; they then pass the information on to other neighbours. Eventually, all the routers have information about all the links on the network and build a kind of topology map of the network.

    Examples of link-state routing protocols are:

    • OSPF 
    • IS-IS 

    Link-state uses the Dijkstra shortest path first (SPF) algorithm to calculate the best path to a destination. However, whereas distance-vector periodically broadcasts it's routing table to it's neighbours, link-state only broadcasts every 30 minutes or so, or when the state of a link changes. If a link changes from up to down or vice-versa, a notification called a link-state advertisement (LSA) is flooded throughout the internetwork. All the routers note the change, and recompute their routes accordingly. With this approach, a router passes information to the whole network, telling them about it's neighbouring links only.This method generates less network traffic.

    Link-state routing responds more quickly to changes in network topology, such as new links or broken links and offers faster route convergence than distance-vector routing.

    ~~ VLSM ~~

    Variable Length Subnet Masking (VSLM), is the extension of the standard IP class subnet masks to include subnets. Some routing protocols support and understand subnetting while other do not. A routing protocol categorized as classful, does not send subnet mask information with route updates. This means that only the standard IP class network addresses are recognized and understood. A network containing subnets would encounter problems if a classful routing protocol used was used. Conversely, a classless routing protocol sends subnet information with any routing information which means that router can recognize subnets within a network.

     

    Common Routing Protocols

    A number of routing protocols have been developed over the years. The more common of these are described below:-

    ~~ RIP ~~

    RIP stands for Routing Information Protocol. It is one of the most frequently used routing protocol on internal networks. RIP is a distance-vector routing protocol that uses a hop count as its routing metric. If there are multiple paths to a destination, RIP chooses the path with the lowest hop count. Of course, the path with the fewest hops is not necessarily be the fastest as the diagram below illustrates.

    RIP comes in different version, RIP-1 and RIP-2. The later version was developed to overcome some limitations of the first version. Some of RIP-1 limitations are:-

    • Single hop count metric:
    This can be an inefficient method for calculating the best path on a network with mixed media. The slowest route with the fewest hops may be chosen over a faster route with a greater number of hops.
    • Hop count limit:
    RIP-1 cannot handle routes over 15 hops. Any network greater than 15 hops away is considered unreachable, so this protocol is unsuitable for larger networks.
    • Classful routing:
    RIP-1 only supports classful routing, so it is virtually impossible to subnet a network properly using this protocol.
    • Bandwidth:
    Every 30 seconds or so, routing information is broadcast. If the size of the internetwork is large, the routing information will also be large and take up valuable bandwidth.

    To allow the use of subnets, RIP-2 was developed in the 1990's. More information is contained inside an RIP-2 routing packet compared to an RIP-1 packet and a subnet mask field is included. Thus, RIP-2 can support classless routing and so a network divided into subnets with different subnet masks can be supported.

    ~~ IGRP ~~

    IGRP stands for Interior Gateway Routing Protocol - a proprietary routing protocol developed by Cisco Systems in the 1990's. At the time IGRP was developed RIP-1 was the most popular routing protocol in use, but RIP's use of hop count as the routing metric and the hop count limit of fifteen made it unsuitable for use on larger networks. So, Cisco decided to develop IGRP, a protocol without the inherent limitations of RIP, that could be used on larger networks. The maximum hop count of IGRP is 255. One of the drawbacks of IGRP is that it is a classful routing protocol and so subnetworks are not supported.

    Like RIP, IGRP is a distance-vector routing protocol but it uses a more complex routing metric to determine path costs. Factors such as delay, bandwidth, hop count and reliability can be used in determining the fastest path, although delay and bandwidth are used by default. The diagram below illustrates how the more complex metric of bandwidth and delay enables a superior path to be selected, compared to selection based solely on hop count.

    ~~ EIGRP ~~

    EIGRP stands for Extended Interior Gateway Routing Protocol is another protocol developed by Cisco System, which evolved from IGRP. EIGRP is also a distance-vector routing protocol but is much more sophisticated than IGRP or RIP, including features more often associated with link-state routing protocols like OSPF.

    To calculate path costs EIGRP, uses a 32 bit metric that combines an assessment of the link bandwidth and delay. Routes are calculated more efficiently using an algorithm called Diffusing Update Algorithm. One advantage of EIGRP is the higher rate of route convergence; in other words, routers exchange information and agree on routes more quickly. Another advantage is that EIGRP will query neighbouring routers for information only when needed, reducing the amount of traffic generated between routers.

    Unlike it's predecessor, EIGRP is able to deal with classless routing allowing the use of VLSM (variable length subnet masking.) One of the main disadvantages of EIGRP is that it only runs on Cisco equipment which may lead to an organization being locked in to this vendor.

    ~~ OSPF ~~

    OSPF stands for Open Shortest Path First - a protocol designed for large networks where other protocols such as RIP may be unsuitable. OSPF is a link-state routing protocol with a more advanced metric algorithm than RIP. It bases path selection on cost rather than hop count and is not limited to only 15 hops in a route, allowing a network to grow beyond what RIP could support.

    With OSPF, a large network can be separated into smaller areas, confining many of the routing processes to each individual area but allowing routers to communicate between areas. This cuts down on network traffic since a router does not have to recalculate its routing table unless a route in its own area changes. The separation of a network into areas is called hierarchical routing. In general, OSPF provides faster route convergence and generates less traffic between routers than RIP or IGRP.

    ~~ IS-IS ~~

    IS-IS stands for Intermediate System to Intermediate System - a protocol developed by the ISO as part of the OSI protocol stack and used to manage routing within Connectionless Network Protocol (CLNP) networks.

    Integrated IS-IS is a derivation of the original IS-IS which was developed to support the IP protocol. As a link-state routing protocol, IS-IS has the same basic features as OSPF, including link state advertisement where link state information is sent out across the network, allowing routers to maintain a current picture of network topology. Variable length subnet masking (VLSM) is also supported.

    ~~ BGP ~~

    BGP stands for Border Gateway Protocol and is an example of an Exterior Gateway Protocol (EGP), allowing routing information to be exchanged between autonomous systems. Autonomous systems are independent networks controlled by different organizations, each running an Interior Gateway Protocol of their choice. For routing between each autonomous system, another routing protocol is required - an Exterior Gateway Protocol. BGP is the principal EGP used by ISP's and large organizations on the Internet today. The version of BGP that allows for classless interdomain routing is BGP-4.

    ~~ Summary of Routing Protocols ~~

    The table below summarizes the Interior Routing Protocols.

    Type
    Characteristics
    Examples
    Specifics
    Distance Vector
    Hop count is the metric typically used. Copies of routing tables are frequently copied to neighbours
    RIP-1
    Uses classful addressing
    RIP-2
    Uses classless addressing
    IGRP
    Uses classful addressing
    Link State
    More complicated metrics are used. Copies of routing tables are only copied to neighbours when network changes are detected
    OSPF
    Hierarchal routing is used
    IS-IS
    Uses classless addressing
    Hybrid
    More complicated metrics are used like link-state but copies of routing tables are frequently copied to neighbours like distance-vector
    EIGRP
    Cisco often categorizes EIGRP is a distance-vector protocol rather than a hybrid
     

    Summary

    On completing these notes you should be able to:-

    • Understand the role of routers in creating subnets, decreasing the size of collision domains and increasing bandwidth.
    • Understand the purpose of routing in determining the best path to a destination.
    • Explain that routed protocols are protocols that are routable, while routing protocols allow information to be exchanged between routers, enabling each router to build a picture of the topology of the network and keep information about routes up-to-date.
    • Understand that switching deals with OSI Layer 2 MAC addresses while routers deal with Layer logical addresses. Also, that switches can forward data between nodes on local subnetworks while routers can forward data between subnetworks.
    • Understand that a router keeps a routing table so it can make path selection decisions.
    • Explain that interior routing protocols are used within autonomous systems, while exterior routing protocols are active between autonomous systems.
    • Explain that static routing is where routes are manually entered into a routing table whereas routes are automatically discovered and recorded in routing tables with dynamic routing.
    • Understand that path selection can be based on routing metrics such as hop count, bandwidth, delay, reliability and load. Also, that different protocols use different metrics or metric combinations.
    • Understand that a distance-vector routing protocol commonly uses hop count as the routing metric and routing table updates occur frequently even when a network topology hasn't changed.
    • Understand that a link-state routing protocol commonly uses combination of metrics and routing table updates occur less frequently and can be triggered by network topology changes.
    • Understand that the rate of route convergence varies with different routing protocols.
    • Explain that RIP is one of the most commonly uses interior routing protocols but it is unsuitable for large networks. Also that other routing protocols such as IGRP, EIGRP, OSPF and IS-IS offer other advantages.
    • Explain that BGP-4 is the most common exterior routing protocol in use today.
     
     

    Site Home

    Top

    Unit Home


       


      

     

     

       
    This Unit 

    Unit Information

    Assessment

    Syllabus

    Scheme of Work

    Learning Resources

    Notes & Lessons

    Assignments

    Quizzes

    Activities

    Resources

    Books & Things

    Links