TN 206: Network Routers and

Routing Protocols

Routers and Routing

06/26/21 07:05 TN206 SemesterII2011 1

 Routers
 A router is a Layer 3 device. It performs all tasks of
devices in lower layers and selects the best route to
the destination based on Layer 3 information.
 Front view of 1841 Integrated Service Router (ISR)

 Rear view of 1841 ISR router:

06/26/21 07:05 TN206 SemesterII2011 2

 Routers

06/26/21 07:05 TN206 SemesterII2011 3

 Routers..
 Routers are the primary devices used to interconnect
networks. They are used to interconnect networks that use
different technologies. They have both LAN and WAN
interfaces. Each port on a router connects to a different
network and routes packets between the networks. Routers
have the ability to break up broadcast domains and
collision domains.

 The router's LAN interfaces connect to the LAN media. The

media is typically UTP cabling, but modules can be added
for using fiber-optics as well. Depending on the series or
model of router, there can be multiple interface types for
connection of LAN and WAN cabling.
06/26/21 07:05 TN206 SemesterII2011 4
 Router Interconnecting 2 LANs

06/26/21 07:05 TN206 SemesterII2011 5

Router Interconnecting a LAN to the Internet

06/26/21 07:05 TN206 SemesterII2011 6

 Choosing a Router
 When selecting a router, it is necessary to match the
characteristics of the router to the requirements of the
network. Factors for choosing a router include:

 Type of connectivity required

 Features available

 Cost

06/26/21 07:05 TN206 SemesterII2011 7

 Basic Parts of a Router
 A router has many of the same components as a computer:
 CPU
 Memory
 I/O Interfaces (mostly network interfaces)
 Operating System. For Cisco routers, the Internetwork
Operating System (IOS) software provides features that
enable a Cisco device to send and receive network traffic
using a wired or wireless network. IOS software is offered
to customers in modules called images. These images
support various features for businesses of every size.

06/26/21 07:05 TN206 SemesterII2011 8

 Router Hardware
 Input buffers (one for each network interface):
 Used to store incoming packets before they are processed
 Routing processor:
 This is often software running on a CPU which maintains and exchanges
routing data with other routers, and Controls the switching fabric to
forward packets
 With high-end routers, each network interface may have a local routing
processor (for forwarding) so that each can forward the packets in its own
input buffer independently
 Switching fabric:
 A network of connections between network interfaces (and their input and
output buffers)
 Output buffers (one for each network interface):
 Used to store outgoing packets after they are processed, but before the
network is available for transmission
06/26/21 07:05 TN206 SemesterII2011 9
 Routers: Network Interfaces
 Often, routers have modularized network interfaces
 One can add/remove/replace network interfaces as needs
change
 Some routers can accept network interface modules of
different types (e.g. Ethernet, Token Ring)

 Each network interface would have its own:

 Input buffer
 Output buffer
 Routing processor (in high-end routers)

06/26/21 07:05 TN206 SemesterII2011 10

 Routers: Input Buffers
 The incoming packets of a network interface are placed in
input buffers:
 These are banks of very high speed memory for packet queuing
prior to processing
 The packet is stored here until the routing processor is available
 The network interface may have a routing processor,
which would:
 have a copy of the forwarding table (to prevent concurrent
access)
 lookup the destination address in this forwarding table, to
determine the correct output port
 configure the switching fabric to forward the packet to the
correct output buffer
 Low-end routers would share one routing processor
06/26/21 07:05 TN206 SemesterII2011 11
 Routers: Routing Processors
 Routing processors have two functions:
 Maintain and exchange routing data with other routers in the
network. Often this involves computing the forwarding table
from data received by other routers
 Use the forwarding table data to configure the switching fabric
to forward the packet to the correct output port
 A routing processor is software which executes on a CPU.
 Off-the-shelf CPU
 These are very inexpensive
 However, the performance of these CPUs is low since they are
not optimized for the types of operations a router typically needs
to perform
 Application-Specific Integrated Circuit (ASIC)
 These are expensive to design (time and money)
 They are optimized for typical routing operations
 High-end routers use these to achieve higher performance
levels
06/26/21 07:05 TN206 SemesterII2011 12
 Routers: Switching Fabric
 Switching fabric’s job is to move packets from the input buffer into the correct output
buffer
 The routing processor determines the correct output port, using the forwarding table .

 Switching fabric comes in 3 major types:

 In-memory switching fabric: The packets move along a shared bus (similar to a network bus)
to the correct output buffer
 Bus-based switching fabric: The packets move along a shared bus (similar to a network bus)
to the correct output buffer
 Crossbar switching fabric: The packets move along a grid of redundant buses. If any bus
fails, alternate paths exist so that forwarding can continue

 Application-Specific Integrated Circuit (ASIC)

 These are expensive to design (time and money)
 They are optimized for typical routing operations
 High-end routers use these to achieve higher performance levels

06/26/21 07:05 TN206 SemesterII2011 13

 Routers: Output Buffers
 The switching fabric gets the packet to the right output
port:

 However, that port’s network may not be immediately

available.

 The packets are stored in the output buffer until the network is
available.

06/26/21 07:05 TN206 SemesterII2011 14

 Multi-Protocol Label Switching (MPLS)
 MPLS is another way to improve router performance.
 Label switching tries to leverage some of the performance of
virtual circuit switched networks (e.g. ATM).
 Packets are assigned a label upon entering an MPLS network.
 This label is used (instead of the IP address) for making
forwarding decisions.
 An MPLS label is an arbitrary value:
 This value is typically a numeric identifier. However, labels could
also be the frequency (i.e. colour) of light used in multi-mode
optical fibre.
 The label can change from one label-switching router (LSR) to the
next
 The label must only be unique for the sending and receiving router.
IP addresses, in contrast, are usually unique across the network.
 A value could even be chosen to help the routing processor choose
the correct output port
06/26/21 07:05 TN206 SemesterII2011 15
 MPLS- Simplified Diagram

MPLS LSR MPLS LSR E-Mail Server

User

MPLS LSR MPLS LSR MPLS LSR

MPLS LSR

Web Server

06/26/21 07:05 TN206 SemesterII2011 16

 MPLS- Simplified Diagram

MPLS LSR MPLS LSR E-Mail Server

User

MPLS LSR MPLS LSR MPLS LSR

MPLS LSR
• Notice that two labels can be directed
down the same link Web Server
 MPLS: Label Values
31
31

MPLS LSR MPLS LSR E-Mail Server

User
7

15 7

MPLS LSR MPLS LSR MPLS LSR

47

MPLS LSR
• Notice that label values are not
globally unique Web Server
• Each pair of routers agrees on a label
 MPLS Packet
 MPLS adds a small pre-header to the start of any IPv4
(or IPv6, IPX, etc.) packet
 In other words, between the data link and network
headers
20 bits
Label The label value

3 bits Class of Service The QoS class of the packet attached (e.g. discardable?)
1 bit Stack Is there a stack of labels?

8 bits Hop Limit The hop limit, copied from/to the IP header
 MPLS and ATM
LSRs can be ATM-enabled
 An LSR can forward a packet (as cells) through an ATM
network. This can be for any number of hops through the
ATM network.
 In this situation the source and destination ATM switches
must be LSRs:
 Other switches in between can be normal ATM
switches, however, the source LSR will use AAL
segmentation to send the cells on the ATM network
using a VPI/VCI for the destination LSR.
 The destination LSR will extract the packet and
continue transmission using MPLS.

06/26/21 07:05 TN206 SemesterII2011 20

 Router Performance
Several methods to improve router performance have been
discussed:
 Use application-specific integrated circuits
 Optimized for routing operations
 Include much routing functionality otherwise executed as software
(in memory).
 Many routing functions can execute in parallel, adding new
functionality without decreasing throughput.
 Use efficient switching fabric:
 Bus or crossbar-based switching fabrics reduce the need for in-
memory processing
 However, that port’s network may not be immediately available.
 The packets are stored in the output buffer until the network is
available.
 Multi-Protocol Label Switching (MPLS)
06/26/21 07:05 TN206 SemesterII2011 21
 Router Components
 Hardware components of a router:
 Network interfaces Processor
 Interconnection network
 Processor with a memory and Memory CPU
CPU
 PC router:
 Interconnection network is the
(PCI) bus and interface cards are
NICs Interconnection Network
 All forwarding and routing is
done on central processor
 Commercial routers: Interface Card Interface Card Interface Card
 Interconnection network and
interface cards are sophisticated
 Processor is only responsible for
control functions (route
processor)
 Almost all forwarding is done on
interface cards
06/26/21 07:05 TN206 SemesterII2011 22
 Routing and Forwarding
 Routing functions include:
 route calculation
 maintenance of the routing table
 execution of routing protocols
 On commercial routers handled by a single general purpose
processor, called route processor

IP forwarding is per-packet processing

 On high-end commercial routers, IP forwarding is distributed
 Most work is done on the interface cards

06/26/21 07:05 TN206 SemesterII2011 23

 Functional Components

Routing
functions
routing
protocol
routing
protocol Control
routing table
updates

routing
table
Datapath:
routing table
lookup
per-packet
processing
IP
incoming IP Forwarding outgoing IP
datagrams datagrams

06/26/21 07:05 TN206 SemesterII2011 24

 Basic Architectural Components
Per-packet processing
Output
Routing Scheduling
Table
Switch Fabric

Routing
Decision

Routing
Table

Forwarding
Decision

Routing
Table

Forwarding
Decision
06/26/21 07:05 TN206 SemesterII2011 25 25
 Slotted Chassis

 Large routers are built as a slotted chassis

 Interface cards are inserted in the slots
 Route processor is also inserted as a slot

 This simplifies repairs and upgrades of components

06/26/21 07:05 TN206 SemesterII2011 26

 Evolution of Router Architectures
 Early routers were essentially general purpose computers
 Today, high-performance routers resemble supercomputers
 Exploit parallelism

 Special hardware components

 Until 1980s (1st generation): standard computer

 Early 1990s (2nd generation): delegate to interfaces
 Late 1990s (3rd generation): Distributed architecture

 Today: Distributed over multiple racks

06/26/21 07:05 TN206 SemesterII2011 27

 1st Generation Routers
 This architecture is still used in low
end routers
 Arriving packets are copied to main Route Processor
memory via direct memory access CPU Cache Memory
(DMA)
 Interconnection network is a
backplane (shared bus) Shared Bus
 All IP forwarding functions are
performed in the central processor. DMA DMA DMA
 Routing cache at processor can
Interface Interface Interface
accelerate the routing table lookup. Card Card Card
Drawbacks:
 Forwarding Performance is limited by MAC MAC MAC

CPU
 Capacity of shared bus limits the
number of interface cards that can be
connected
06/26/21 07:05 TN206 SemesterII2011 28
 2nd Generation Routers
 Keeps shared bus architecture, Route Processor

but offloads most IP forwarding

CPU Cache Memory
to interface cards
 Interface cards have local route
cache and processing elements Shared
Bus
Fast path: If routing entry is found
DMA DMA DMA
in local cache, forward packet
directly to outgoing interface Route Cache Route Cache Route Cache
Slow path: If routing table entry is
not in cache, packet must be Memory Memory Memory

handled by central CPU MAC MAC MAC

Drawbacks: Shared bus is still
bottleneck Interface
Cards

06/26/21 07:05 TN206 SemesterII2011 29

 Another 2nd Generation Architecture
 IP forwarding is done by Forwarding Forwarding
Route Processor
separate components Engine Engine

(Forwarding Engines) CPU CPU CPU

Forwarding operations: Cache Cache

Memory
1. Packet received on interface: Memory Memory
Store the packet in local
memory. Extracts IP header Control Bus
and sent to one forwarding Forwarding Bus
(IP headers only)
engine Data Bus

2. Forwarding engine does

lookup, updates IP header, Interface Memory Memory Memory
and sends it back to incoming Cards
interface MAC MAC MAC
3. Packet is reconstructed and
sent to outgoing interface.
06/26/21 07:05 TN206 SemesterII2011 30
 3rd Generation Architecture
 Interconnection network is a Switch
switch fabric (e.g., a crossbar Fabric

switch)
 Distributed architecture: Switch Switch Route
 Interface Fabric
cards operate Fabric
Interface Interface
Processor

independent of each other

Route Route
CPU
 No centralized processing Processing Processing

for IP forwarding Memory Memory

Memory
 These routers can be scaled to
many hundred interface cards MAC MAC

and to aggregate capacity of >

1 Terabit per second
06/26/21 07:05 TN206 SemesterII2011 31
 Router Pricing

Routers range in price quite dramatically:

 720Gbps (40 Gbps x 18 slots)
 Supports 10/100 Ethernet to 10Gbps Ethernet
 Around $10,000
 1280Gbps (40Gbps x 32 slots)
 Supports FDDI, ATM, Ethernet, Token Ring nets
 Supports RIP, OSPF, IS-IS, BGP, MPLS
 Supports IPv4, IPv6, IPX, IPX+
 Around $200,000

06/26/21 07:05 TN206 SemesterII2011 32

 Routing
 Routing is the method by which network devices direct
messages across networks to arrive at the correct
destination.
 Small business networks rely on routing to connect their
users to the Internet. As these networks grow, routing
becomes integral part of the LAN infrastructure as well.
 All routers must make routing decisions. They do this by
looking up information stored in their routing tables.
Every router contains a table of all locally-connected
networks and the interfaces that connect to them.
 These routing tables also contain information about the
routes, or paths, that the router uses to reach other remote
networks that are not locally attached.
06/26/21 07:05 TN206 SemesterII2011 33
 Routing..
 Routes can be statically assigned to the router by an
administrator, or they can be dynamically given to the
router by another router via a program called a routing
protocol.

06/26/21 07:05 TN206 SemesterII2011 34

 Routing..
 Every router uses a routing table to make decisions where to
send packets. The routing table contains a set of routes, where
each route describes which gateway or interface the router
needs to use to reach a specified network.
 A route has four main components:
 Destination value
 Mask
 Gateway or interface address
 Route cost or metric
 To direct a message to the correct destination, the router looks
at the destination IP address in the packet and then looks for
a matching route in the routing table. The destination values
in a routing table refer to destination network addresses.

06/26/21 07:05 TN206 SemesterII2011 35

 Routing..
 In order for the router to determine if it has a route to the
destination IP address in its table, it must first find out
which bits represent the destination network address.
 The router looks up the subnet mask assigned to each
potential route in the table. The router applies each subnet
mask to the destination IP address in the packet. The
resulting network address is then compared to the
network address of the route in the table.
 If a match is found, the packet is forwarded out the correct
interface, or to the appropriate gateway.

06/26/21 07:05 TN206 SemesterII2011 36

 Routing..

 When the network address matches more than one route in the
routing table, the router uses the route that has the most
specific, or longest, network address match from its routing
table.
 Sometimes there is more than one equal cost route to the same
destination network. There are routing protocol rules that
determine which route the router will use.

06/26/21 07:05 TN206 SemesterII2011 37

 Routing..
 Routing tables do not contain end-to-end information about
the entire path from a source network to a destination
network.
 They only contain information about the next hop along that
path. The next hop is always a directly-connected gateway on
the same subnet. Eventually the message gets passed to a
router that is directly connected to the destination host and
the message is delivered.
 Routing information between all the intermediate routers on a
path is in the form of network addresses not specific hosts. It
is only in the final router that the destination address in the
routing table points specifically to a host computer rather
than a network.
06/26/21 07:05 TN206 SemesterII2011 38
 Source Routing
 Source routing is a method that can be used to specify the
route that a packet should take through the network.
 In source routing the path through the network is set by the
source or a device that tells the network source the desired
path.
 It is assumed that the source of the packet knows about the
layout of the network and can specify the best path for the
packet.
 Usually network routing is used on the internet and most
networks rather than source routing. With network routing the
knowledge about the network layout is in the network routing
devices. Source routing can produce some security problems
such as hacking when used.

06/26/21 07:05 TN206 SemesterII2011 39

 Source Routing..
 When the packet with source routing specified is going through
the network, the network device that makes routing decisions
such as a router will look at the path specific information in the
network packet to determine where to forward the packet.
 When source routing is not used, the packet contains only the
destination address and the router will automatically determine
the best place to forward the packet.
 With network routing , as a packet travels through the
network, each router will look at the destination IP address and
determine the next hop to forward the packet to. The next hop
is the next router or network switching location where a
network routing decision will be made.
 When source routing is used, the sender of the data makes
some or all of the routing decisions.
06/26/21 07:05 TN206 SemesterII2011 40
 Source Routing
 Source routing can be used to do any of the following:
 Troubleshoot a network
 Map a network
 Increase network performance
 Hack a computer
 Source routing can be used for hacking purposes by
allowing an attacker to get data to a machine that would not
normally be reachable.
 Some machines are on private internet addresses such
as [Link] and they are not normally accessible
from the internet.
06/26/21 07:05 TN206 SemesterII2011 41
 Source Routing..
 If there is a machine on a private network that performs
routing and traffic may be routed through it between two other
networks, it may be possible for an attacker to specify their
data to go through the machine on the private network.

 The attacker may also fool the machine on the private network
into believing it is some other computer using IP spoofing.

 The best way to prevent this attack is to configure the router

on the private network to ignore source routed packets.

06/26/21 07:05 TN206 SemesterII2011 42

 Directly Connected Routes.
 When the router powers up, the configured interfaces are
enabled.
 As they become operational, the router stores the directly
attached local network addresses as connected routes in the
routing table.
 For Cisco routers, these routes are identified in the routing
table with the prefix C. These routes are automatically
updated whenever the interface is reconfigured or shutdown.
 For a Cisco router, the IOS command show ip route
displays the routes in the routing table.

06/26/21 07:05 TN206 SemesterII2011 43

 Static Routes.
 A network administrator can manually configure a static route
to a specific network.
 A static route does not change until the administrator manually
reconfigures it.
 For Cisco routes, these routes are identified in the routing
table with the prefix S.
 Since static routes are configured manually, network
administrators must add and delete static routes to reflect any
changes in network topology.
 On small networks with few possible changes, static routes
require very little maintenance. In a large network, the manual
maintenance of routing tables could require significant
administrative time. For this reason, larger networks generally
use dynamic routing rather than static routes.
06/26/21 07:05 TN206 SemesterII2011 44
 Dynamically-Updated Routes (Dynamic Routes)
 Dynamic routes are automatically created and maintained by
routing protocols.

 Routing protocols are implemented in programs that run on

routers and that exchange routing information with other
routers in the network.

 Dynamically-updated routes are identified in the routing

table with the prefix that corresponds to the type of routing
protocol that created the route, for example R is used for the
Routing Information Protocol (RIP).

06/26/21 07:05 TN206 SemesterII2011 45

 Default Route
 The default route is a type of static route which specifies a
gateway to use when the routing table does not contain a
path to use to reach the destination network.

 It is common for default routes to point to the next router in

the path to the Internet Service Provider.

 If a subnet has only one router, then that router is

automatically the default gateway, because all network
traffic to and from that local network has no option but to
travel through that router.

06/26/21 07:05 TN206 SemesterII2011 46

 IP Routing Algorithm
 Use subnet mask to compute the network address (N) for the datagram’s
destination address (D).
 If N is directly connected to this router, forward the packet at a network frame.
 Check the table for an entry for N:
 If one exists, lookup the port associated with N in the table entry (P), forward
the datagram to P
 If one does not exist, if a default route exists (D), forward the datagram to D
 Else send an error message (using ICMP)

 For a Cisco router, the IOS command show ip route displays the routes in the
routing table.

06/26/21 07:05 TN206 SemesterII2011 47

 Routing History

 Routing tables were originally managed manually.

 As new machines or networks were added, administrators
added new routing table entries to compensate
 The need for dynamic, auto-configurable routing tables
was obvious by the late 1980s when many networks were
joining the Internet
 At this time, routers were called ‘gateways’

06/26/21 07:05 TN206 SemesterII2011 48