Transcript The Routing Table: A Closer Look

The Routing Table: A
Closer Look
Routing Protocols and Concepts – Chapter 8
Modified by Tony Chen
04/01/2008
ITE PC v4.0
Chapter 1
© 2007 Cisco Systems, Inc. All rights reserved.
Cisco Public
1
Notes:

If you see any mistake on my PowerPoint slides or if
you have any questions about the materials, please
feel free to email me at [email protected].
Thanks!
Tony Chen
College of DuPage
Cisco Networking Academy
ITE PC v4.0
Chapter 1
© 2007 Cisco Systems, Inc. All rights reserved.
Cisco Public
2
Objectives

Describe the various route types found in the routing
table structure

Describe the routing table lookup process.

Describe routing behavior in routed networks.
ITE PC v4.0
Chapter 1
© 2007 Cisco Systems, Inc. All rights reserved.
Cisco Public
3
Introduction
 Chapter Focus
– Structure of the routing table
•Will examine the format of the routing table and learn about
level 1 and level 2 routes.
– Lookup process of the routing table
– Classless and classful routing behaviors
Cisco IP Routing, by Alex Zinin (ISBN 0-201-60473-6).
ITE PC v4.0
Chapter 1
© 2007 Cisco Systems, Inc. All rights reserved.
Cisco Public
4
Routing Table Structure
 Lab Topology
 3 router setup
-R1 and R2 share a common 172.16.0.0/16 network with
172.16.2.0/24 subnets.
-R2 and R3 are connected by the 192.168.1.0/24 network.
-R3 also has a 172.16.4.0/24 subnet, which is disconnected, or
discontiguous, from the 172.16.0.0 network that R1 and R2
share.
In a later section, we will configure
the interfaces for R2
ITE PC v4.0
Chapter 1
© 2007 Cisco Systems, Inc. All rights reserved.
Cisco Public
5
Routing Table Structure
 The figure shows routing table entries come from the
following sources
-Directly connected networks
-Static routes
-Dynamic routing protocols
ITE PC v4.0
Chapter 1
© 2007 Cisco Systems, Inc. All rights reserved.
Cisco Public
6
Routing Table Structure
 The figure shows what happens as the Serial 0/0/1 interface for R2 is
configured with the 192.168.1.1/24 address.
– R1 and R3 already have their interfaces configured with the appropriate
IP addresses and subnet masks.
–We will now configure the interfaces for R2 and use debug ip routing to
view the routing table process that is used to add these entries.
 As soon as the “no shutdown” command is issued the route is added
to routing table
debug ip routing
ITE PC v4.0
Chapter 1
© 2007 Cisco Systems, Inc. All rights reserved.
Cisco Public
7
Routing Table Structure
 Cisco IP routing table
is a hierarchical
structure
–The reason for this is
to speed up lookup
process
–The hierarchy
includes several
levels.
•level 1
•level 2
ITE PC v4.0
Chapter 1
© 2007 Cisco Systems, Inc. All rights reserved.
Cisco Public
8
Routing Table Structure
 Level 1 Routes
–Have a subnet mask equal to or less than the classful
mask of the network address.
–192.168.1.0/24 is a level 1 network route, because the
subnet mask is equal to the network's classful mask. /24
for class C networks, such as the 192.168.1.0 network.
 Level 1 route can function as
–Default route
•A default route is a static route with the address
0.0.0.0/0.
–Supernet route
•A supernet route is a network address with a mask
less than the classful mask.
–Network route
•A network route is a route that has a subnet mask
equal to that of the classful mask.
 The source of the level 1 route can be a directly
connected network, static route, or a dynamic routing
protocol.
ITE PC v4.0
Chapter 1
© 2007 Cisco Systems, Inc. All rights reserved.
Cisco Public
9
Routing Table Structure
 The level 1 route 192.168.1.0/24 can be further defined as an
ultimate route.
ultimate route includes either:
-A next-hop ip address (another path)
OR
-An exit interface
 The directly connected network 192.168.1.0/24
–It is a level 1 network route because it has a subnet mask that is the same as
its classful mask.
–This same route is also an ultimate route because it contains the exit interface
Serial 0/0/1.
ITE PC v4.0
Chapter 1
© 2007 Cisco Systems, Inc. All rights reserved.
Cisco Public
10
Parent and Child Routes
 A parent route is a level 1 route
–A parent route does not contain
any next-hop IP address or exit
interface information
 When the 172.16.3.0 subnet was
added to the routing table, another
route, 172.16.0.0, was also added.
–The first entry, 172.16.0.0/24, does
not contain any next-hop IP address
or exit interface information.
–This route is known as a level 1
parent route.
–A parent route is actually a heading
that indicates the presence of level 2
routes, also known as child routes.
ITE PC v4.0
Chapter 1
© 2007 Cisco Systems, Inc. All rights reserved.
Cisco Public
11
Routing Table Structure
 A level 1 parent route is automatically
created any time a subnet is added to
the routing table.
–In other words, a parent route is
created whenever a route with a mask
greater than the classful mask is
entered into the routing table.
–172.16.0.0/24 is subnetted, 1 subnets
 A level 2 route is a route that is a
subnet of a classful network address.
– Child routes are level 2 routes
– Child routes are a subnet of a
classful network address
–C 172.16.3.0 is directly connected,
FastEthernet0/0
ITE PC v4.0
Chapter 1
© 2007 Cisco Systems, Inc. All rights reserved.
Cisco Public
12
Routing Table Structure
 The parent route contains the 172.16.0.0 - The classful network
address for our subnet.
 Level 2 child routes contain 172.16.3.0, route source & the
network address of the route
–Notice that the subnet mask is not included with the subnet, the level
2 child route. The subnet mask for this child route (subnet) is the /24
mask included in its parent route, 172.16.0.0
 Level 2 child routes are also considered ultimate routes
–Reason: they contain the next hop address &/or exit interface
ITE PC v4.0
Chapter 1
© 2007 Cisco Systems, Inc. All rights reserved.
Cisco Public
13
Routing Table Structure
 The figure shows the
configuration of the Serial
0/0/0 interface on R2.
–The routing table shows
two child routes for the
same 172.16.0.0/24 parent
route.
•Both 172.16.2.0 and
172.16.3.0 are members
of the same parent route,
•because they are both
members of the
172.16.0.0/16 classful
network
ITE PC v4.0
Chapter 1
© 2007 Cisco Systems, Inc. All rights reserved.
Cisco Public
14
Routing Table Structure
 Both child routes have the same subnet mask
-This means the parent route maintains the /24 mask
Note: If there is only a
single level 2 child route
and that route is
removed, the level 1
parent route will be
automatically deleted. A
level 1 parent route
exists only when there
is at least one level 2
child route.
The
role of the parent route will be examined when we discuss the route lookup process.
ITE PC v4.0
Chapter 1
© 2007 Cisco Systems, Inc. All rights reserved.
Cisco Public
15
Routing Table Structure
 In classless networks, child routes do not have to share
the same subnet mask
–Whenever there are two or more child routes with different
subnet masks belonging to the same classful network, the
routing table presents a slightly different view, which states that
this parent network is variably subnetted.
ITE PC v4.0
Chapter 1
© 2007 Cisco Systems, Inc. All rights reserved.
Cisco Public
16
Routing Table Structure
 Parent & Child Routes: Classless Networks
ITE PC v4.0
Chapter 1
© 2007 Cisco Systems, Inc. All rights reserved.
Cisco Public
17
Routing Table Structure
 Parent & Child Routes: classful and classless Networks
classful
Network
Type
Parent
route’s
Classful
mask is
Displayed
Term
variably
subnetted
is seen in
parent
route in
routing
table
Includes
the # of
different
masks of
child
routes
Subnet
mask
included
with each
child route
entry
Classful
No
No
No
No
Classless
Yes
Yes
Yes
Yes
ITE PC v4.0
Chapter 1
classless
© 2007 Cisco Systems, Inc. All rights reserved.
Cisco Public
18
Routing Table Lookup Process

The Route Lookup Process
1.
2.
3.
4.
5.
ITE PC v4.0
Chapter 1
Examine level 1 routes
•
If best match a level 1 ultimate route
and is not a parent route this route is
used to forward packet
•
If the best match is a level 1 parent
route, proceed to Step 2
Router examines level 2 (child) routes
•
If there is a match with level 2 child
route then that subnet is used to
forward packet
•
If no match then proceed to Step 3
Router determines classful or
classless routing behavior
•
If classful then packet is dropped
•
If classless then router searches level
one supernet and default routes
If there exists a level 1 supernet or
default route match then Packet is
forwarded
If not packet is dropped
© 2007 Cisco Systems, Inc. All rights reserved.
Cisco Public
19
Routing Table Lookup Process
 Longest Match: Level 1 Network Routes
–Best match is also known as the longest match
–The best match is the one that has the most number of left
most bits matching between the destination IP address and the
route in the routing table.
 For example, in the figure we have a packet destined for
172.16.0.10. Many possible routes could match this packet. Three
possible routes are shown that do match this packet: 172.16.0.0/12,
172.16.0.0/18, and 172.16.0.0/26. Of the three routes,
172.16.0.0/26 has the longest match.
ITE PC v4.0
Chapter 1
© 2007 Cisco Systems, Inc. All rights reserved.
Cisco Public
20
Routing Table Lookup Process
 Finding the subnet mask
used to determine the
longest match
Scenario:
–PC1 pings 192.168.1.2
–Router examines level 1
route for best match
–There exist a match
between192.168.1.2 &
192.168.1.0 / 24
–Router forwards packets out
s0/0/0
ITE PC v4.0
Chapter 1
© 2007 Cisco Systems, Inc. All rights reserved.
Cisco Public
21
Routing Table Lookup Process
 The process of matching
–1st there must be a match made between the parent route &
destination IP
•If a match is made then an attempt at finding a match
between the destination IP and the child route is made.
•Do at least 16 of the left-most bits of the parent route match the
first 16 bits of the packet's destination IP address of 192.168.1.2?
–The answer, no,
ITE PC v4.0
Chapter 1
© 2007 Cisco Systems, Inc. All rights reserved.
Cisco Public
22
Routing Table Lookup Process
 Finding a match between packet’s destination IP address
and the next route in the routing table
–The figure shows a match between the destination IP of 192.168.1.0
and the level one IP of 192.168.1.0 / 24 then packet forwarded out
s0/0/0
–Not only does the minimum of 24 bits match, but a total of 30 bits
match, as shown in the figure.
ITE PC v4.0
Chapter 1
© 2007 Cisco Systems, Inc. All rights reserved.
Cisco Public
23
Routing Table Lookup Process
 In the example in the figure, PC1 sends a ping to PC2
at 172.16.3.10. What happens when there is a match
with a level 1 parent route?
 Before level 2 child routes are examined
-There must be a match between classful level one
parent route and destination IP address.
ITE PC v4.0
Chapter 1
© 2007 Cisco Systems, Inc. All rights reserved.
Cisco Public
24
Routing Table Lookup Process
 After the match with parent route has been made Level 2 child
routes will be examined for a match
-Route lookup process searches for child
routes with a match with destination IP
ITE PC v4.0
Chapter 1
© 2007 Cisco Systems, Inc. All rights reserved.
Cisco Public
25
Routing Table Lookup Process
 How a router finds a match with one of the level 2
child routes
–First router examines parent routes for a match
–If a match exists then:
•Child routes are examined
•Child route chosen is the one with the
longest match
 First, the router examines the parent route for a
match.
 The router checks the last child route for
172.16.3.0/24 and finds a match. The first 24 bits
do match. The routing table process will use this
route, 172.16.3.0/24, to forward the packet with
the destination IP address of 172.16.3.10 out the
exit interface of Serial 0/0/0.
 R 172.16.3.0 [120/1] via 172.16.2.2, 00:00:25,
Serial0/0/0
ITE PC v4.0
Chapter 1
© 2007 Cisco Systems, Inc. All rights reserved.
Cisco Public
26
Routing Table Lookup Process
 Example: Route Lookup
Process with VLSM
-The use of VLSM does not
change the lookup process
-If there is a match between
destination IP address and the
level 1 parent route then
-Level 2 child routes will be
searched
ITE PC v4.0
Chapter 1
© 2007 Cisco Systems, Inc. All rights reserved.
Cisco Public
27
Routing Behavior
 Classful & classless routing protocols
Influence how routing table is populated
 Classful & classless routing behaviors
Determines how routing table is searched after it is
filled
ITE PC v4.0
Chapter 1
© 2007 Cisco Systems, Inc. All rights reserved.
Cisco Public
28
Routing Behavior
 Classful Routing
Behavior: no ip
classless
 What happens if there is
not a match with any
level 2 child routes of the
parent?
-Router must determine if
the routing behavior is
classless or classful
-If router is utilizing classful
routing behavior then
-Lookup process is
terminated and
packet is dropped
ITE PC v4.0
Chapter 1
ip classless and no ip classless
© 2007 Cisco Systems, Inc. All rights reserved.
Cisco Public
29
Using the ip classless command (cont.)
http://www.networkking.net/out/IPClassless.htm
What is IP Classless?

The "ip classless" command prevents the existence of a single "subnet" route from blocking access via the
default route to other subnets of the same old-style network. Default only works with single-homed ISPs.

RFC 1879

IP classless command is not easy to understand, we know that. But I bet, after you read the following lines, you will
understand what it is all about.

First, you must understand a very simple logic. Here is the logic: Me and you are on a journey. If you break my leg,
then you must carry me all the way! If you understand this logic, you will understand "IP classless".

RIP is telling you: I am classful, if you break my class, then you have to show me every route there is, or I will drop
your packet. I will drop it even though there is a default route (0.0.0.0).

What is classful? Classful means that a class A subnet should be shown as x.0.0.0 such as 10.0.0.0 255.0.0.0

If you show it as 10.44.0.0 255.255.0.0, you are breaking its class.

Or, a class B subnet should be shown as x.x.0.0 255.255.0.0 such as 172.29.0.0 255.255.0.0

If you show it as 172.29.26.0 255.255.255.0, you are breaking its class.

Let’s assume RIP knows about 10.0.0.0

If you break 10.0.0.0 into three, for example to 10.1.0.0 and 10.2.0.0 and 10.3.0.0, and then give RIP a packet with a
destination of 10.4.0.1, RIP will drop it. Why? Why doesn’t RIP send the packet to the default route?

Because RIP told you, if you break my class, then you have to show me every damn route, otherwise I will drop it.
Here, you broke RIP's class so you must show him the way to 10.4.0.1 and every other 10.x.x.x route in the universe.
Otherwise RIP will drop the packet, even if there is a default route. RIP will not care about your default route or last
resort gateway; it will drop your packet.

How do you ask RIP not to drop your packet and send the unknown destinations to the default route, although you
have been so mean to him and have broken its class? You tell him: please, please, ip classless!

If no ip classless, drop the packet
If ip classless, send the packet to the default.
ITE PC v4.0
Chapter 1
© 2007 Cisco Systems, Inc. All rights reserved.
Cisco Public
30
Routing Behavior
 ip Classless
 Beginning with IOS 11.3, “ip classless”
was configured by default
–The command “no ip classless” means that the
route lookup process uses classful routing table
lookups by default.
 Classless routing behavior works for
-Discontiguous networks
And
-CIDR supernets
ITE PC v4.0
Chapter 1
© 2007 Cisco Systems, Inc. All rights reserved.
Cisco Public
31
Routing Behavior
“no ip classless”
 Classful Routing Behavior – Search Process
–when classful routing behavior is in effect (no ip
classless) the process will not continue searching
level 1 routes in the routing table. If a packet doesn't
match a child route for the parent network route, then
the router drops the packet.
 R2 receives a packet destined for PC3 at
172.16.4.10.
–Even with the default route configured.
–The destination’s subnet mask is a /24 and none of
the child routes left most bits match the first 24 bits.
This means packet is dropped
ITE PC v4.0
Chapter 1
© 2007 Cisco Systems, Inc. All rights reserved.
Cisco Public
32
Routing Behavior
“no ip classless”
 Classful Routing Behavior – Search
Process
 The reason why the router will not search
beyond the child routes
At the beginning of the Internet's
growth, networks were all classful
This meant an organization could
subnet a major network address and
“enlighten” all the organization’s
routers about the subnetting
Therefore, if the subnet was not in the
routing table, the subnet did not exist
and packet was dropped
 The routing table process will not use the
default route, 0.0.0.0/0, or any other
route.
ITE PC v4.0
Chapter 1
© 2007 Cisco Systems, Inc. All rights reserved.
Cisco Public
33
Routing Behavior
“no ip classless”
 The routing table process will not
use the default route, 0.0.0.0/0, or
any other route.
A common error is to assume that a
default route will always be used if the
router does not have a better route.
In our example, R2's default route is
not examined nor used, although it is a
match.
 This is often a very surprising result
when a network administrator does not
understand the difference between
classful and classless routing
behavior.
ITE PC v4.0
Chapter 1
© 2007 Cisco Systems, Inc. All rights reserved.
Cisco Public
34
Routing Behavior
“ip classless”
 Classless Routing Behavior-
ip classless
 Step 3: If classless routing behavior in
effect then, continue searching level 1
supernet routes in the routing table for a
match, including the default route, if there is
one.
 Step 4: Match with supernet or default
Supernet routes Checked first
–If a match exists then forward packet
Default routes Checked second
 Step 5: If there is no match or no default
route then the Packet is dropped
ITE PC v4.0
Chapter 1
© 2007 Cisco Systems, Inc. All rights reserved.
Cisco Public
35
Routing Behavior
“ip classless”
 Classless Routing Behavior – Search Process
 Router begins search process by finding a match between
destination IP and parent route
After finding the above mentioned match, then
there is a search of the child route
 There is no match with the level 2 child routes.
ITE PC v4.0
Chapter 1
© 2007 Cisco Systems, Inc. All rights reserved.
Cisco Public
36
Routing Behavior
 If no match is found in child routes of
previous slide then
“ip classless”
–Router continues to search the
routing table for a match that may
have fewer than 16 bits in the match
 The 192.168.1.0/24 route does not
have 24 left-most bits that match the
destination IP address.
C 192.168.1.0/24 is directly connected, Serial0/0/1
ITE PC v4.0
Chapter 1
© 2007 Cisco Systems, Inc. All rights reserved.
Cisco Public
37
Routing Behavior
“ip classless”
S* 0.0.0.0/0 is directly connected, Serial0/0/1
 The mask is /0, which means
that zero or no bits need to
match.
 A default route will be the
lowest-bit match. In classless
routing behavior, if no other
route matches, the default route
will match.
–In this case the router will use the
default route, because it is the best
match. The packet will be forwarded
out the Serial 0/0/1 interface.
ITE PC v4.0
Chapter 1
© 2007 Cisco Systems, Inc. All rights reserved.
Cisco Public
38
Routing Behavior
 What does R3 do with return
traffic back to PC2 at
172.16.2.10?
 In this case, R3 uses the
172.16.0.0/16 child route and
forwards the traffic out Serial
0/0/1 back to R2.
ITE PC v4.0
Chapter 1
© 2007 Cisco Systems, Inc. All rights reserved.
Cisco Public
39
Routing Behavior
 Classful vs. Classless Routing Behavior
-It is recommended to use classless routing
behavior
Reason: so supernet and default routes can
be used whenever needed
ITE PC v4.0
Chapter 1
© 2007 Cisco Systems, Inc. All rights reserved.
Cisco Public
40
POP QUIZ
Longest Match
http://www.cisco.com/warp/public/105/21.html
 Let's look at the three routes we just installed in the routing table, and see
how they look on the router.
 router# show ip route
....
D 192.168.32.0/26 [90/25789217] via 10.1.1.1
---- (192.168.32.0 to 192.168.32.63)
R 192.168.32.0/24 [120/4] via 10.1.1.2
---- (192.168.32.0 to 192.168.32.255)
O 192.168.32.0/19 [110/229840] via 10.1.1.3
---- (192.168.32.0 to 192.168.63.255)
....
 If a packet arrives on a router interface destined for 192.168.32.1, which
route would the router choose?
 If a packet arrives on a router interface destined for 192.168.32.100,
which route would the router choose?
Answers are on the next page
ITE PC v4.0
Chapter 1
© 2007 Cisco Systems, Inc. All rights reserved.
Cisco Public
41
Longest Match
http://www.cisco.com/warp/public/105/21.html
 Let's look at the three routes we just installed in the routing table, and see how
they look on the router.
 router# show ip route
....
D 192.168.32.0/26 [90/25789217] via 10.1.1.1
R 192.168.32.0/24 [120/4] via 10.1.1.2
O 192.168.32.0/19 [110/229840] via 10.1.1.3
....
---- (192.168.32.0 to 192.168.32.63)
---- (192.168.32.0 to 192.168.32.255)
---- (192.168.32.0 to 192.168.63.255)
 If a packet destined to 192.168.32.1 is directed toward 10.1.1.1, because
192.168.32.1 falls within the 192.168.32.0/26 network (192.168.32.0 to
192.168.32.63). It also falls within the other two routes available, but the
192.168.32.0/26 has the longest prefix within the routing table (26 bits verses 24
or 19 bits).
 if a packet destined for 192.168.32.100 arrives on one of the router's interfaces,
it's forwarded to 10.1.1.2, because 192.168.32.100 doesn't fall within
192.168.32.0/26 (192.168.32.0 through 192.168.32.63), but it does fall within the
192.168.32.0/24 destination (192.168.32.0 through 192.168.32.255). Again, it also
falls into the range covered by 192.168.32.0/19, but 192.168.32.0/24 has a longer
prefix length
ITE PC v4.0
Chapter 1
© 2007 Cisco Systems, Inc. All rights reserved.
Cisco Public
42
Summary
Content/structure of a routing table
 Routing table entries
-Directly connected networks
-Static route
-Dynamic routing protocols
 Routing tables are hierarchical
-Level 1 route
Have a subnet mask that is less than or equal to
classful subnet mask for the network address
-Level 2 route
These are subnets of a network address
ITE PC v4.0
Chapter 1
© 2007 Cisco Systems, Inc. All rights reserved.
Cisco Public
43
Summary
Routing table lookup process
 Begins with examining level 1 routes for best match with packet’s destination IP
 If the best match = an ultimate route then
-Packet is forwarded -Else-Parent route is examined
If parent route & destination IP match then Level 2 (child)
routes are examined
Level 2 route examination
 If a match between destination IP and child route found then
Packet forwarded -Else
 If Router is using classful routing behavior then
Packet is dropped -Else
 If router is using classless routing behavior then
Router searches Level 1 supernet & default routes for a
match
 If a match is found then Packet if forwarded -Else
 Packet is dropped
ITE PC v4.0
Chapter 1
© 2007 Cisco Systems, Inc. All rights reserved.
Cisco Public
44
Summary
 Routing behaviors
-This refers to how a routing table is searched
 Classful routing behavior
-Indicated by the use of the no ip classless command
-Router will not look beyond child routes for a lesser
match
 Classless routing behavior
-Indicated by the use of the ip classless command
-Router will look beyond child routes for a lesser match
ITE PC v4.0
Chapter 1
© 2007 Cisco Systems, Inc. All rights reserved.
Cisco Public
45
ITE PC v4.0
Chapter 1
© 2007 Cisco Systems, Inc. All rights reserved.
Cisco Public
46