ITRI CCL
IP Routing Primer
Paul C. Huang, Ph.D. ITRI / CCL / N300
CCL/N300; Paul Huang
1999/6/2
ITRI CCL
Basic Addressing / Subnetting
0 Network
Host Host Host 127 networks / 16,777,216 hosts Class A natural mask [Link] Mask of [Link] creates 127 networks, 256 subnets/network, and 65,636 hosts/subnet
Class A
Class B
1 0 Network
Network
Host
Host
16,384 networks / 65,5366 hosts Class B natural mask [Link]
Class C
1 1 0 Network
Network
Network
Host
2,097,152 networks / 256 hosts Class C natural mask [Link]
IP Address 10. 0.0.1 Mask [Link]
00001010 00000000 00000000 00000001 11111111 11111111 00000000 00000000 Network Subnet Host
CCL/N300; Paul Huang
1999/6/2
ITRI CCL
Variable Length Subnet Mask
Ability to configure one network with different masks
more flexibility in dividing a network into multiple subnets while still maintaining an adequate number of hosts in each subnet. Example: Class C address with mask 255.255.255.X
[Link] [Link] [Link] [Link] [Link] [Link] (1111 1100) (1111 1000) (1111 0000) (1110 0000) (1100 0000) (1000 0000) 64 subnets 32 subnets 16 subnets 8 subnets 4 subnets 2 subnets w/ 4 hosts each w/ 8 hosts each w/ 16 hosts each w/ 32 hosts each w/ 64 hosts each w/ 128 hosts each
If you need to divide a Class C network into 3 subnets with 100 hosts in one subnet and 50 hosts in the remaining two subnets, VLSM is required. RIPv1 and IGRP do not handle VLSM OSPF, EIGRP, ISIS, RIPv2 handle VLSM
CCL/N300; Paul Huang 1999/6/2 3
ITRI CCL
Handling IP depletion
Creative IP address space allocation
VLSM Non-permanent allocation of address blocks Contiguous class C network
Classless Interdomain Routing (CIDR)
RFC 1519
Private addressing and Network Address Translation (NAT)
RFC 1918 RFC 1631 Address allocation for private internets The IP Network Address Translator (NAT)
IP v6
New Address Space
CCL/N300; Paul Huang
1999/6/2
ITRI CCL
Classless Interdomain Routing (CIDR)
IP network represented by a <prefix, length>
No more traditional IP classes A/B/C Indicates a more hierarchical Internet architecture, where each domain takes its IP addresses from a higher hierarchical level Allows multiple classes of blocks to be lumped together as an Aggregate, CIDR block, or a Supernet
identified when the prefix length is shorter the network s natural mask. allows a list of contiguous IP networks to be summarized into one announcement.
Example: <[Link]/16>
illegal class C network supernet because 16 < 24 (less than natural mask length) [Link]/20 is identified as a more specific prefix of length 20
CCL/N300; Paul Huang 1999/6/2 5
ITRI CCL
Classless Interdomain Routing (CIDR)
Advantages
Move towards a more hierarchical, geographically-oriented network More efficient routing strategies and propagation
Tremendous savings in route propagation when summarization is done close to the leaf networks. Aggregation permits the ISP to advertise the addresses in a single notation rather than many.
Potential problems
CIDR works only if every customer connects to his provider
via one connection only (a scenario called single-homing) take its IP addresses from its provider s prefixes
Multi-homing connecting to multiple providers Already have previously applied IP address
CCL/N300; Paul Huang 1999/6/2 6
ITRI CCL
CIDR Example
NAP Without CIDR / With CIDR
[Link] [Link] [Link] [Link] [Link] thru [Link]
NAP
[Link]/8 [Link]/8
ISP 3
[Link] [Link] [Link] [Link] ~ [Link] [Link] [Link] ~ [Link]
ISP 3
[Link]/16 [Link]/16 [Link]/16 [Link]/16
ISP 1
ISP 2
ISP 1
ISP 2
[Link] [Link]
CCL/N300; Paul Huang
[Link]
[Link]
[Link] [Link]
1999/6/2
[Link]
[Link]
ITRI CCL
Longest Match Routing Rule
Routing is always done on a longest match basis
will always follow the longer mask for two different length prefix of the same network destinations connected to multiple domains must always be explicitly announced in their most specific, not aggregate forms. Example:
[Link]/24 via path 1 [Link]/16 via path 2
Traffic towards [Link]
19
Domain C
2. 8.3
1.
4 0/2
h1
Domain A
Pat
198.32
Path 2
Host [Link]
.0.0/1
Domain B
CCL/N300; Paul Huang
1999/6/2
ITRI CCL
Longest Prefix Match
Routing Table R1 = 0101 R2 = 0101101 R3 = 010110101011 IP = 010101101011 IP = 010110101101
Depth 32
232 leaves (IP Address)
CCL/N300; Paul Huang
1999/6/2
ITRI CCL
Routing Loop
Occurs when traffic circles back and forth between domains, never reaching its final destination.
Prevention
Must not follow a less specific route for a destination that matches one of its own aggregate routes. Drop all packets destined to an unreachable destination less specific than the aggregate route Beware of Black holes where traffic reaches and stops at a destination that is not its intended destination, but from which it cannot be forwarded.
[Link]/13
ISP 1 Samnet
Traffic to [Link]
ISP 2
[Link]/24 Default 0/0
NULL
10
CCL/N300; Paul Huang
1999/6/2
ITRI CCL
Multihoming Scenario:
Address taken from one provider
NAP
Advertising aggregates is tricky
no one is allowed to aggregate someone else s routes (proxy aggregation) unless
the aggregating party is a superset of the other party both parties are in total agreement
[Link]/13
[Link]/18
[Link]/13
Example
[Link]/18 will create a black hole for StubNet, because traffic will follow the longest match and end up in ISP 2 with no link to StubNet.
[Link]/21 [Link] ~ [Link] LindaNet
[Link]/13 [Link] ~ [Link] ISP 1
[Link]/13 [Link] ~ [Link] ISP 2
[Link]/21 [Link] ~ [Link] StubNet
[Link]/20 [Link] ~ [Link] JamesNet
CCL/N300; Paul Huang
1999/6/2
11
ITRI CCL
Multihoming Scenario:
Address taken from one provider
NAP
[Link]/13 [Link]/21 [Link]/20 [Link]/13 [Link]/21 [Link]/20
In this case, explicit aggregates must be advertised by both ISP 1 and ISP 2 If ISP 1 only advertise the lessspecific aggregate of [Link]/13, all traffic towards JamesNet and LindaNet would always follow the longest match via ISP2.
[Link]/21 [Link] ~ [Link] LindaNet
[Link]/13 [Link] ~ [Link] ISP 1
[Link]/13 [Link] ~ [Link] ISP 2
[Link]/21 [Link] ~ [Link] StubNet
[Link]/20 [Link] ~ [Link] JamesNet
CCL/N300; Paul Huang
1999/6/2
12
ITRI CCL
Multihoming Scenario:
Address taken from different provider
NAP
[Link]/13 [Link]/13
In this example, each provider will be able to aggregate its own address space without having to list specific ranges from the other provider. Major drawback
backup routes to multihomed organizations are not maintained. each only advertise its own block of addresses, not from other ISPs portions of network will be out if one of the ISPs is out.
[Link]/13 [Link] ~ [Link] ISP 1
[Link]/13 [Link] ~ [Link] ISP 2
[Link]/20 [Link] ~ [Link] JamesNet
[Link]/20 [Link] ~ [Link] StubNet
LargeNet
CCL/N300; Paul Huang
1999/6/2
13
ITRI CCL
Multihoming Scenario: Address taken from none of the provider
NAP
[Link]/13 [Link]/13 [Link]/13 [Link]/20
In this example, the address space is not from those of ISP 1 or ISP 2.
Both ISPs must advertise a specific aggregate on top of their own ranges.
Major drawback
increase the size of the routing table for all routers.
[Link]/13 [Link] ~ [Link] ISP 1
[Link]/13 [Link] ~ [Link] ISP 2
[Link]/20 [Link] ~ [Link] JamesNet
CCL/N300; Paul Huang
1999/6/2
14
ITRI CCL
Private Addressing and NAT
Global connectivity
Globally unique IP address that are recognized inside and outside the organization. hosts inside an organization have direct access to both internal hosts and Internet hosts.
Private connectivity
hosts inside an organization have direct access to internal hosts only, not Internet hosts.
Examples: ATM machines, cash registers, etc.
Proxy gateway required to access Internet host.
Companies have the responsibility of applying routing filters to prevent the private networks from being leaked to the Internet.
Advantages:
fewer unique global IP addresses required security for internal hosts
Disadvantages:
renumbering of all host required if later decide to join globally; problem may be mitigated by using DHCP (Dynamic Host Configuration Protocol)
CCL/N300; Paul Huang 1999/6/2 15
ITRI CCL
Private Addressing and NAT
Private Internet address space allocated
[Link] ~ [Link] (a single class A network number) [Link] ~ [Link] (16 contiguous class B network number) [Link] ~ [Link] (256 contiguous class C network number)
l l
Telnet requires a two step procedure NAT has to dynamically map private IP addresses to a smaller pool of global addresses
NAT Table Private [Link] [Link] Private Global 128.213.x.y 128.213.z.w
Host B [Link] Private
Filter private updates via NAT
Internet
[Link] Host A
CCL/N300; Paul Huang
Global
Global Host C
1999/6/2 16
ITRI CCL
Primary Class of Routing Protocols
l
Link-state protocols
ISIS, OSPF Information sent describes the state of the link attached to the router
IP network or subnets assigned cost of the links (inversely proportional to bandwidth)
Distance Vector protocol
RIP, IGRP Information sent
all the networks that the router knows about, not just the networks it is connected to. Advertising router increases the metric (typical hop-count) of the router it has heard about. (maximum hop-count 15)
Advantages:
greater scalability l no hop count l supports VLSM and CIDR l hierarchy allows aggregation faster convergence l immediate flooding of link states to the domain l less overhead from route exchanges load balancing via link costs
Advantages:
simple configuration
Disadvantages:
cannot take into account link speeds slower convergence large routing table exchange and maintenance. hold-down/flush timers slows convergence to minutes temporary routing loops less scalable, lacks hierarchy classful, lack VLSM or CIDR features
17
Disadvantages:
difficult to configure and troubleshoot.
CCL/N300; Paul Huang 1999/6/2
ITRI CCL
Choosing routing protocols
RIPv1
Networks with no redundant links or parallel paths and no requirements for VLSM (variable length subnet masking) or discontiguous major networks
RIPv2
Network that requires VLSM and/or discontiguous major networks and does not have redundant links or parallel paths
IGRP
Network that has redundant links or parallel paths and does not require VLSM or discontiguous major networks
OSPF, EIGRP, ISIS
Network with parallel paths and/or redundant links and that requires VLSM or discontiguous major networks
CCL/N300; Paul Huang
1999/6/2
18
ITRI CCL
Routing methodology
Static routing
routes to destination are listed manually network reachability is not dependent on the state of the network;
i.e. whether a destination is up or down, the static routes would remain in the routing table, and traffic will still be sent to that destination.
Default routing
last resort outlet for destination traffic that are unknown to the router. Easiest form of routing for a domain connected to a single exit point.
Dynamic routing
routes are learned via internal or external routing protocol network reachability is dependent on the existence and state of the network.
i.e. if a destination is down, the route would disappear from the routing table and traffic would not be sent toward that destination.
Most networks use a combination of all three routing methodology
1999/6/2 19
CCL/N300; Paul Huang
ITRI CCL
Autonomous System (AS)
AS is a set of routers having a single routing policy, running under a single technical administration.
A collection of IGPs working together to provide interior routing Each AS has an identifying number, assigned by an Internet Registry. Routing information between ASs is exchanged via an exterior gateway protocol such as BGPv4.
IGP
Autonomous Systems
IGP
IGP
CCL/N300; Paul Huang
1999/6/2
20
ITRI CCL
Stub AS
Reaches the network outside its domain via a single exit point.
All traffic defaults to the provider, therefore don t have to learn Internet routes from the provider Still need to advertise routes to the providers
via static entries -- good for small set of aggregate routes via IGP protocol -- stub AS have difficult time getting registered AS numbers because the routing policies tend to follow the provider and therefore don t require unique AS number. via BGP protocol -- Provider will give the customer a private AS number (65412 ~ 65535)
Provider
def ault
CCL/N300; Paul Huang 1999/6/2
Single Homed AS
21
ITRI CCL
Multihomed Nontransit AS
l
Multihomed
more than one exit point to the outside world
Nontransit
does not allow transit traffic to go through it
(IP source /destination address outside of AS) will not advertise routes it learned from other AS transit traffic can still be forced via default or static routing does not require BGP4
(n3,n4) (n3,n4) (n1,n2)
CCL/N300; Paul Huang
ISP1
ISP2
(n5,n6) (n5,n6)
(n1,n2)
1999/6/2
AS1
(n1,n2)
22
ITRI CCL
Multihomed Transit AS
l
Multihomed
more than one exit point to the outside world
Transit
Uses BGP inside an AS as a pipe to exchange BGP updates (IBGP) Routers running IBGP are called transit routers Routers running EBGP are called border routers Will advertise routes it learned from other AS
(n3,n4) (n3,n4) (n1,n2,n5,n6)
CCL/N300; Paul Huang
ISP1
ISP2
(n5,n6) (n5,n6)
(n1,n2)
1999/6/2
AS1
(n1,n2,n3,n4)
23
ITRI CCL
Router Configuration
[Link] [Link]
8.7 S0: 16 1.6.1
Major Net: Mask:
RB
8.71 S0: 16 .6.2
S1: [Link] S0: [Link]
.71.9.2
S0: [Link]
RA
S1: 168
.71.9.1
S1: 168
RC
l
S2: [Link]
Router A s Configuration
interface ethernet0 ip address [Link]/[Link] ip address [Link]/[Link] secondary interface serial0 ip address [Link]/[Link] bandwidth 128 interface serial1 ip address [Link]/[Link] bandwidth 128
1999/6/2
Router A s Configuration
router rip network 168.71.0 passive-interface Ethernet0 (prevents RIP from advertising routing updates out Ethernet0) ip route [Link] [Link] Ethernet0
CCL/N300; Paul Huang
24
ITRI CCL
Router Configuration
[Link] [Link]
8.7 S0: 16 1.6.1
Major Net: Mask:
RB
8.71 S0: 16 .6.2
S1: [Link] S0: [Link]
.71.9.2
S0: [Link]
RA
S1: 168
.71.9.1
S1: 168
RC
l
S2: [Link]
Router B s Configuration
interface serial0 ip address [Link]/[Link] bandwidth 128 interface serial1 ip address [Link]/[Link] bandwidth 64 router rip network [Link]
Router C s Configuration
interface tokenring0 ip address [Link]/[Link] interface serial0 ip address [Link]/[Link] bandwidth 64 interface serial1 ip address [Link]/[Link] router rip network [Link]
CCL/N300; Paul Huang
1999/6/2
25
ITRI CCL
What a Router does
[Link] [Link]
8.7 S0: 16 1.6.1
Major Net: Mask:
RB
8.71 S0: 16 .6.2
S1: [Link] S0: [Link]
S0: [Link]
RA
RC
S2: [Link]
Router A forwards a packet with destination address [Link]/[Link] to Router B
does not know nor care if [Link] is directly attached to Router B router terminology: network prefix [Link] is known via [Link], the advertising router.
CCL/N300; Paul Huang
1999/6/2
26
ITRI CCL
How forwarding decisions are made
Major Net: Mask:
[Link] [Link]
[Link]
RA
[Link]
[Link]
[Link]
[Link]
[Link]
RB
[Link]
[Link]
[Link]
[Link]
[Link]
Protocol IGRP Connected Connected
Network [Link] [Link] [Link]
Interface Serial0 Serial0 Token0
Next Hop [Link]
CCL/N300; Paul Huang
1999/6/2
27
ITRI CCL
Forwarding decisions for Multi-point Interfaces
[Link] [Link] ARP entry required
RouterB# show frame-relay map Serial0 (up): ip [Link] dlci 100(0x64, 0x1840), static, broadcast
Major Net: Mask:
[Link] [Link] [Link]
[Link]
RC
.2
RA
Frame Relay [Link]
.1
[Link] [Link]
.3
RB
[Link]
[Link]
[Link]
[Link]
Protocol IGRP Connected Connected IGRP
CCL/N300; Paul Huang 1999/6/2
Network [Link] [Link] [Link] [Link]
Interface Serial0 Serial0 Token0 Serial0
Next Hop [Link]
[Link]
28
ITRI CCL
End systems sending Packets to other subnets
Major Net: Mask:
[Link] [Link]
[Link]
RA
[Link]
[Link]
RB
[Link]
[Link]
[Link]
0000.0C00.1234 [Link]
0000.0C01.8793
Layer 2 Layer 3
0000.0F00.8674
0000.0D00.5463 [Link]
CCL/N300; Paul Huang
1999/6/2
29
ITRI CCL
More Routing Terminology
[Link]
RA
[Link]
[Link]
[Link]
RB
[Link]
[Link]
[Link] / 16
Major Net
refers to the network-only portion of an Internet address
Discontiguous network
IP subnet address from a major network are applied to physical networks that are separated by a network with a different major net.
Summarize
To report only the major net portion of an address, even though there are subnets of the address in the routing table.
Aggregation
To reduce the number of subnets in a routing advertisement by advertising only the common portion of the subnet address that is required to provide full IP connectivity.
CCL/N300; Paul Huang
1999/6/2
30
ITRI CCL
Deriving network masks
[Link]
RA
[Link]
[Link]
[Link]
RB
[Link]
[Link]
[Link] / 255.255.???.???
Two methods / rules
Advertisements for subnets that are part of the same major networks as the IP address of the interface they are receiving over will have the subnet mask of the receiving interface applied to them All other networks in the advertisement should be for major networks, not subnets (thru summarization)
Example: incorrect advertising subnet over a major net boundary
1. Ignore route advertisement 2. Install it with a mask of [Link], indicating that it is a host route 3. Guess the mask size.
CCL/N300; Paul Huang
1999/6/2
31
ITRI CCL
Understanding Summarization
Different major net = summarize [Link] [Link] [Link]
RA
[Link]
[Link]
[Link]
RB
[Link]
Different major net = summarize [Link] [Link]
Summarization rules
If a network or subnet in the table is part of the same network address space (major net) and has the same mask as the outbound interface, it is advertised over the interface. If a network or subnet is part of the same major net as the outbound interface but has a different mask, it is not advertised. If a network or subnet is part of a different address space, the outbound interface mask is ignored and only the summarized major network portion of the route is advertised.
CCL/N300; Paul Huang
1999/6/2
32
ITRI CCL
Understanding Subnet 0
Different major net = summarize [Link] [Link] [Link]
RA
[Link]
[Link]
[Link]
RB
[Link]
Different major net = summarize [Link] [Link]
Subnet 0 refers to the use of 0s in the subnet portion of an address covered by the subnet mask.
Network Address Subnet 0 mask Network Address Summarized mask Subnet 0 [Link] 10101000.01000111.00000000.00000000 11111111.11111111.11111111.00000000 [Link] Summarized Route [Link] 10101000.01000111.00000000.00000000 11111111.11111111.00000000.00000000 [Link]
CCL/N300; Paul Huang
1999/6/2
33
ITRI CCL
Summarization caused by discontiguous network
[Link]
RA
[Link]
[Link]
[Link]
RB
[Link]
RouterA# conf t RouterA#-config# interface s0 RouterA #-config-if# ip address [Link] [Link] RouterA# show interface serial 0 Serial0 is up, line protocol is up Internet address is [Link]/24 MTU 1500 bytes, BW 128 kbit, DLY 20000 usec, rely 255/255, load 1/255
RouterB# conf t RouterB#-config# interface s0 RouterB #-config-if# ip address [Link] [Link] RouterB# show interface serial 0 Serial0 is up, line protocol is up Internet address is [Link]/24 MTU 1500 bytes, BW 128 kbit, DLY 20000 usec, rely 255/255, load 1/255
Router rip network [Link] network [Link]
CCL/N300; Paul Huang 1999/6/2 34
ITRI CCL
RIP cannot reach discontiguous subnets
Different major net = summarize [Link] [Link] [Link]
RA
[Link]
[Link]
[Link]
RB
[Link]
Different major net = summarize [Link] [Link]
[Link]
Routers running RIP ignores summarized routes for networks to which they have connections; therefore RIP doesn t work with discontiguous networks.
Checks network number and mask with its interface before sending out a packet RA does not have a route installed to [Link] even though RB is advertising it; vice versa with RB therefore RA can t ping [Link] and RB can t ping [Link]
CCL/N300; Paul Huang
1999/6/2
35