Routers and Routing

Routing Tables and Route Summarisation

   Nick Urbanik <nicku@nicku.org>

Copyright Conditions: Open Publication License

     (see http://www.opencontent.org/openpub/)

A computing department

Routing Modern Routing Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . slide 2 The Routing Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . slide 3 Longest Prefix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . slide 4 Example: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . slide 5

CIDR The Big Emergency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . slide 6 The Solution: CIDR and NAT . . . . . . . . . . . . . . . . . . . . . . slide 7 Address Depletion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . slide 8 Router Table Explosion . . . . . . . . . . . . . . . . . . . . . . . . . . . slide 9 How does CIDR solve them? . . . . . . . . . . . . . . . . . . . . . . slide 10

Aggregating Routes Aggregating routes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . slide 11 Without Route Summarisation . . . . . . . . . . . . . . . . . . . . . slide 12 With Route Summarisation . . . . . . . . . . . . . . . . . . . . . . . slide 13 Explanation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . slide 14 How the Routes were Summarised. . . . . . . . . . . . . . . . . . . slide 15 Route Aggregation: NetAddr::IP . . . . . . . . . . . . . . . . . . . slide 16 route-aggregate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . slide 17

Addressing Scheme Designing an Addressing Scheme. . . . . . . . . . . . . . . . . . . . slide 18 Example Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . slide 19 Example Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . slide 20 Solution — Links. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . slide 21 Solution — Larger Subnets — 1 . . . . . . . . . . . . . . . . . . . . slide 22 Solution — Larger Subnets — 2 . . . . . . . . . . . . . . . . . . . . slide 23

Gateway Protocols Classes of Routing Protocols. . . . . . . . . . . . . . . . . . . . . . . slide 25 Gateway Protocols. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . slide 26

BGP: AS Types Border Gateway Protocol BGP . . . . . . . . . . . . . . . . . . . . . slide 27 Single-homed Autonomous Systems. . . . . . . . . . . . . . . . . . slide 28 Single-homed Autonomous Systems. . . . . . . . . . . . . . . . . . slide 29 Multi-homed Non-transit AS . . . . . . . . . . . . . . . . . . . . . . slide 30 Multi-homed Transit AS. . . . . . . . . . . . . . . . . . . . . . . . . . slide 31 Multi-homed Transit AS. . . . . . . . . . . . . . . . . . . . . . . . . . slide 32 BGP: to use or not to use. . . . . . . . . . . . . . . . . . . . . . . . . slide 33 BGP Attributes

BGP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . slide 35 BGP Attributes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . slide 36 BGP Weight Attribute. . . . . . . . . . . . . . . . . . . . . . . . . . . slide 37

Preferring One Link BGP Local Preference Attribute . . . . . . . . . . . . . . . . . . . . slide 38 BGP LOCAL PREF. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . slide 39 BGP MED Attribute . . . . . . . . . . . . . . . . . . . . . . . . . . . . slide 40 BGP MULTI EXIT DISC. . . . . . . . . . . . . . . . . . . . . . . . . . . slide 41 BGP: Selecting one Link . . . . . . . . . . . . . . . . . . . . . . . . . slide 42 BGP AS path Attribute . . . . . . . . . . . . . . . . . . . . . . . . . . slide 43

BGP Messages BGP Message Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . slide 44 BGP Packet Formats . . . . . . . . . . . . . . . . . . . . . . . . . . . . slide 45 Open Message . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . slide 46 Update Message . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . slide 47 Notification Message . . . . . . . . . . . . . . . . . . . . . . . . . . . . slide 48

Modern Routing Tables

• Each entry in a routing table has 3 main items:

• A network address (the destination)

• A netmask length

• A next hop address

   $ route -n
   Kernel IP routing table
   Destination     Gateway         Genmask         Flags Iface
   172.19.64.0     0.0.0.0         255.255.192.0   U     eth0
   127.0.0.0       0.0.0.0         255.0.0.0       U     lo
   0.0.0.0         172.19.127.254  0.0.0.0         UG    eth0

SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 2

The Routing Algorithm

• For a given destination IP address

• Search the routing table for the longest prefix match for the address

• Extract the next hop address from the routing table entry

• Send the packet to the next hop address

• If no match found, report that the destination is unreachable.

SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 3

Longest Prefix

• So what does “longest prefix match” mean?

• To see if the prefix matches, ∘ Bitwise AND netmask with destination ∘ Bitwise AND netmask with network from routing table entry ∘ If the two results are equal, then the prefix matches

• If we do the same for all entries in the routing table, the match

with the longest netmask wins.

SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 4

Example:

• Given this routing table, where does the packet with destination 192.168.0.3 go to?

   192.168.0.0     0.0.0.0         255.255.255.0   U     eth0
   192.168.25.0    0.0.0.0         255.255.255.0   U     vmnet1
   192.168.0.0     172.19.35.254   255.255.0.0     UG    ppp1
   0.0.0.0         202.180.160.251 0.0.0.0         UG    ppp0

• How about 192.168.128.48?

• 192.168.25.10?

• 192.169.0.1?

SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 5

The Big Emergency

• In the early 90s, it became apparent that two problems were

quickly going to become overwhelming:

∘ Address depletion — we were running out of IP addresses ∘ Router table explosion — the routing tables were growing too

fast for the router hardware to cope

SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 6

The Solution: CIDR and NAT

• Two solutions were developed:

• cidr (Classless Internet Domain Routing), and

• nat (Network Address Translation).

∘ nat allows a firewall or router to present one address to the

outside world, but many to the inside. ∘ In Linux, use iptables. ∘ Use private addresses: ∘ 192.168.0.0/16 ∘ 172.12.0.0/12 ∘ 10.0.0.0/8

SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 7

Address Depletion

• Class C was too small for medium sized enterprises

• Class B was too big

• Many organisations asked for (and received) class B networks when they needed only a /22 or /21 network

• This used up the available 2^{32} addresses too fast

• Later there was a need for small Internet allocations of 1 or 2

addresses.

∘ Class C was too wasteful for this.

SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 8

Router Table Explosion

• As class B addresses became scarce, smes were given a number of class C network allocations

• But each class C needed a separate routing table advertisement • Local information about the internal network structure of a com-

pany needed to be advertised world wide

• This did not scale

• By now routing would need much more cpu and ram than is

currently used, and the Internet would have slowed further.

SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 9

How does CIDR solve them?

• New address allocations can be sized accurately to the need

∘ When requesting addresses, the authority (http://www.apnic.net/) will reserve some addresses for future growth if you specify you will need them

• New address allocations are made taking into account neighbouring networks

• Aim is to summarise many routes into as few routes as possible.

SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 10

Aggregating routes

• Routers summarise routes themselves when they use classless rout-

ing protocols such as:

∘ rip2 ∘ ospf ∘ bgp

SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 11

Without Route Summarisation

SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 12

With Route Summarisation

SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 13

Explanation

• The first diagram shows all subnets behind router A advertised everywhere

∘ This is because the routers are unable to summarise the routes

• The second diagram shows the subnets behind A summarised into two routes instead of 5

∘ The routers must be running a classless routing protocol such

as ospf or rip2.

SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 14

How the Routes were Summarised

• 200.200.24.0/24: 24_{10} = 00011000_{2}

• 200.200.25.0/24: 25_{10} = 00011001_{2}

• 200.200.26.0/24: 26_{10} = 00011010_{2}

• 200.200.27.0/24: 27_{10} = 00011011_{2} ∘ So these can be summarised into: ∘ 200.200.24.0/22

• 200.200.28.0/24: 28_{10} = 00011100_{2}

∘ This cannot be summarised with the other routes, so it must

be advertised separately.

SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 15

Route Aggregation: NetAddr::IP

• There is a Perl module for working with IP addresses (of course):

• NetAddr::IP

• Includes the method compact(), which takes a list of networks and returns a list of summarised address blocks.

• The next slide shows a little program that will aggregate address

blocks given on the command line or on standard input.

SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 16

route-aggregate
#! /usr/bin/perl -w
use NetAddr::IP;
$| = 1;
our ( @ips, @ip );
if ( @ARGV ) {
    @ips = @ARGV
} else {
    @ips = <STDIN>;
}
foreach my $ip ( @ips ) {
    push @ip, NetAddr::IP->new( $ip );
}
my @aggregated = NetAddr::IP::compact( @ip );
print "@aggregated\n";

SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 17

Designing an Addressing Scheme

• Given one (or two) blocks of addresses, how do we allocate addresses to a network involving routers?

• Need also to allocate addresses to links between routers—these

need their own little subnet

SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 18

Example Problem

• Given a physical network layout as shown in the figure below • Has 10 subnets (excluding the link Z)

• All three routers support cidr addressing

SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 19

Example Problem

• You are given:

∘ The information on previous slide

∘ Two address blocks: – 172.19.0/20

– 172.19.128/28

• Requirements are:

∘ Subnets 1 to 8 must each support up to 140 computers ∘ Subnets must be assigned to allow maximum route aggrega-

tion ∘ Any unused addresses must be kept in single blocks so that

they can be used elsewhere or for future expansion

SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 20

Solution — Links

• General strategy: determine the lower and upper limits on each subnet. Allocate networks in the order of smallest to largest.

• The smallest block of addresses is only suitable for allocating to the links, so allocate them first.

• Minimum size of each serial link is 4, as 2^{⌈log_{2}(2+2)⌉} = 2^{2}, giving a prefix size of 32 − 2 = 30, i.e., /30.

• Allocate adjacent subnets to links X and Y, so that router C can aggregate routes to them.

subnet  network
subnet X 172.19.128.0/30
subnet Y 172.19.128.4/30

SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 21

Solution — Larger Subnets — 1

• For each of the larger subnets, minimum size is 256, i.e., a /24 subnet

• 2^{8} is the lowest power of 2 that contains 140+2. (2^{⌈log_{2}(140+2)⌉} = 2^{8};

so prefix length = 32 − 8 = 24).

SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 22

Solution — Larger Subnets — 2

• Let us allocate the lowest 8 /24 blocks from 172.19.0/20:

subnet network
subnet 1 172.19.0.0/24
subnet 2 172.19.1.0/24
subnet 3 172.19.2.0/24
subnet 4 172.19.3.0/24
subnet 5 172.19.4.0/24
subnet 6 172.19.5.0/24
subnet 7 172.19.6.0/24
subnet 8 172.19.7.0/24

• In a tutorial exercise, you will determine what routes each router

advertises.

SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 23

Gateway Protocols Border Gateway Protocol — BGP

Classes of Routing Protocols

• Distance Vector or Link-State are two types of routing protocols.

• Another way to classify routing protocols is as follows:

• Intra-Domain routing:

∘ routing of packets within the same Autonomous System (AS) ∘ Interior Gateway Protocol igp, rip 2, ospf, …

• Inter-Domain routing:

∘ Inter-Domain routing is between multiple Autonomous Sys-

tems. ∘ Exterior Gateway Protocol egp, Border Gateway Protocol

bgp

• Autonomous System (as) refers to a group of routers (i.e. networks) administered by the same organization.

• Each as is assigned a number. as numbers range from 1 to 65,535,

with 64512 to 65535 reserved for private (internal networks) use.

SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 25

Gateway Protocols

• Inter-domain and Intra-domain routing protocols are also referred as Exterior and Interior routing protocols respectively.

• The first widely used exterior gateway protocol is called Exterior Gateway Protocol (egp), it was designed to communicate reachability among the core routers of arpanet.

• egp is more a reachability protocol than a routing protocol, it only tests reachability but not makes intelligent routing decisions.

• egp is replaced by the Border Gateway Protocol (bgp). The current version of bgp is version 4

∘ earlier versions don’t support cidr, so are obsolete

SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 26

Border Gateway Protocol BGP

• bgp is an inter-domain (inter-as) routing protocol. However, bgp can also be used within an as.

• When used between as, bgp is referred as Exterior bgp (ebgp).

• When used within an as, bgp is referred as Interior bgp (ibgp).

• bgp is mainly used in core routers in the Internet, for connections between Internet Service Providers. Large networks (universities and big enterprises) also use bgp to connect to isps. Within these networks, however, other Interior Gateway Protocols (such as rip or ospf) are used rather than ibgp.

SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 27

Single-homed Autonomous Systems Single-homed Autonomous Systems

• Single homed as, or stub as

∘ An as has only one exit point to outside networks. Quite often, a single-homed as is referred as a stub network.

• An isp can use three different methods to advertise a customer’s network, a single-homed as, so that the Internet community can learn about such a network.

∘ Using static/default routes

∘ Using igp, such as ospf and rip

∘ Using egp, such as bgp

• In most cases, simple static routes are used.

• bgp is not commonly used due to the difficulty stub networks have

with getting a registered as number.

SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 29

Multi-homed Non-transit AS

• An as is a multi-homed system if it has more than one exit point to the outside networks. An as connected to the Internet can be multi-homed to a single isp or multiple isps.

• Non-transit refers to the fact that transit traffic does not pass through the as. A non-transit as would advertise only its own routes to the isps to which it connects, it would not advertise routes that it learned from one isp to another.

• A multi-homed Non-transit as does not really need to run bgp with their isps. Other routing methods can be used instead. However, some isps may prefer the customers to use bgp.

SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 30

Multi-homed Transit AS

SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 31

Multi-homed Transit AS

• A multi-homed transit as can be used for transit traffic of other autonomous systems. bgp can be used internally so that multiple border routers in the same as can share bgp information.

• ibgp is run inside the as. Routers that route ibgp traffic are transit routers.

• ebgp is run between the local and the external ass. Routers on the boundary of an as that use ebgp to exchange information with the isp are border (or edge) routers.

SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 32

BGP: to use or not to use

• If the routing policy of an as is consistent with the isp’s policy, it is not necessary to use bgp to exchange routing information with the isp. If the as and isp’s policy are different, bgp is preferred.

• If the as uses different isps for redundancy, (or load sharing) a combination of static and default routes could be used instead of bgp.

• If the as uses multiple connections to isps that are active at the

same time, bgp is preferred.

SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 33

BGP Attributes

BGP

• BPG is designed to be used on the Internet. Many route parameters, called attributes, can be used with bgp so that better routing policies are provided.

• bgp supports cidr which helps reduce the routing table size.

• bgp packets are carried through tcp connection. When two neighbor routers wish to exchange bgp route information, a tcp connection is established first.

• bgp routers do not send periodic updates. Full routing information are exchanged when the tcp connection is first established, afterward, only changed routes will be advertised. Also, only the optimal path (i.e. there are alternate paths) to a destination network is advertised through routing updates.

SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 35

BGP Attributes

• Routes learned via bgp have associated properties that are used to determine the best route to a destination when multiple paths exist. These properties are referred to as bgp attributes.

• The following bgp attributes can be used to determine the best path:

∘ Weight (Cisco proprietary, highest priority)

∘ Local Preference

∘ as Path

∘ Origin

∘ Multi-Exit Discriminator (lowest priority)

SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 36

BGP Weight Attribute

• Weight is a Cisco-defined attribute that is local to a router. The weight attribute is not advertised to neighboring routers.

• If the router learns about more than one route to the same destination, the route with the highest weight will be preferred.

• When there are two routes/paths to a destination, both will be maintained in the bgp routing table. However, only the route with the highest weight will be installed in the ip routing table. That is, when forwarding ip packets, the route with the highest weight is used.

SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 37

BGP Local Preference Attribute

• The local preference attribute is used to prefer an exit point from the local autonomous system as. If there are multiple exit points from the as, the local preference attribute is used to select the exit point for a specific route.

• For example, two routers (A & B) connect a local as100 to another as200, and both routers receive route advertisement for a particular network 10.0.0.0/8. If router A is set a local preference value of 50 while router B is set a value of 55, the route through router B will be used to forward traffic from local as to the particular network 10.0.0.0/8.

• Weight attribute is similar to the local preference attribute in that they are used to set an outgoing path. Their difference is that weight attribute is local to a router while local preference attribute is propagated throughout the local as.

SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 38

BGP LOCAL PREF

BGP MED Attribute

• The multi-exit discriminator (med) is used to suggest an external as regarding the preferred route into the local as that is advertising the route.

• The external as, which receive the meds, may not take the “suggestion” and may use other bgp attributes for route selection.

• meds are advertised throughout the local as.

SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 40

BGP MULTI EXIT DISC

SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 41

BGP: Selecting one Link BGP AS path Attribute

• When a route advertisement passes through an autonomous system, the as number is added to an ordered list of as numbers that the route advertisement has traversed.

• The AS path attribute can be used to detect routing loops.

∘ If a router receives a route advertisement with an ordered list containing an as number the same as the as that the router belongs to, it ignores the route advertisement.

• The AS path attribute can be used to select the better path.

∘ The route that contains the shortest AS path (i.e. the order

list that contains the shortest list of as numbers) is selected.

SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 43

BGP Message Types

• Four bgp message types are specified in RFC 1771 (i.e. bgp version 4).

• The Open Message opens a bgp communication session between peers and is the first message sent by each side after a tcp connection is established.

• The Update Message is used to provide routing updates to other bgp systems, allowing routers to construct a consistent view of the network topology. Update messages can withdraw one or more unfeasible routes from the routing table and simultaneously can advertise a route.

• The Notification Message is sent when error condition is detected. Notifications are used to close an active session.

• The Keep-alive Message notifies bgp peers that a device is active.

SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 44

BGP Packet Formats

• All bgp message types use the basic packet header

• The basic packet header contains:

∘ a 16-byte marker field which contains authentication value ∘ a 2-byte length field which contains the total length of the

message ∘ a 1-byte type field which specifies the message type ∘ data of variable length, this field carry the upper-layer infor-

mation

SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 45

Additional Fields: Open Message

• Open, update and notification messages have additional fields, but keep-alive messages use only the basic packet header.

• Additional fields of the Open Message contains:

∘ bgp version number (i.e., 4) ∘ AS number of sender ∘ hold-time ∘ bgp identifier of the sender (ip address) ∘ optional parameters such as authentication data.

BGP Additional Fields: Update Message

• Additional fields of Update Message contains:

∘ Withdrawn routes: a list of IP address prefixes for the routes

being withdrawn ∘ Network layer reachability information: a list of ip address

prefixes (e.g. 10.1.1.0/24) for the advertised routes ∘ Path attributes (such as origin, as path, med,

LOCAL PREF, …) that describe the characteristics of the advertised path.

∘ Unfeasible routes length, i.e., length of withdrawn routes field ∘ Total path attribute length, i.e., length of the path attributes

field

SNM — ver. 1.3 Routing Tables and Route Summarisation — slide 47

BGP Additional Fields: Notification Message

• Additional fields of Notification Message contains: ∘ Error code that indicates the type of error that occurred. ∘ Error sub code ∘ error data.