University of Washington, Computing & Communications

[UW ] [COMPUTING AND COMMUNICATIONS]

Internet Routing (Part 1): Introduction and Interior Routing

CSE 588 lecture
May 8, 1997

Steve Corbató
corbato@cac.washington.edu

Networks and Distributed Computing
Computing & Communications
University of Washington

Tonight's plan

Phenomenological, not theoretical
Topics
- Generalities
- Distance Vector Protocols (RIP, IGRP)
- Link-State Protocols (OSPF, IS-IS)
- Multicast (DVMRP, PIM)
- Case Study: UW's next-generation router search
Next week: Exterior routing and State of Internet

Routing

Determination of optimum path(s)
- Route: Destination, Metric, Next Hop/Interface, Age
Propagation of information
Protocols
Variant: Source-dependent routing
- Acceptable Use Policies

Routing distinctions

Static vs. Dynamic
Interior vs. Exterior
Distance Vector vs. Link State
Classful vs. Classless Routing
Unicast vs. Multicast
IPv4 vs. IPv6
Congruent vs. Tunneled

Router implementation issues

Routing table(s)
- Redistribution
Forwarding table
Cache
Default route
Vendors: Cisco, Ascend (Netstar), Bay (Wellfleet), 3Com, Ipsilon, Juniper(?)

IP address hierarchy

Classful addresses
- Class A = 0 + 7 network bits + 24 host bits
  - (Network Mask 255.0.0.0)
- Class B = 10 + 14 network bits + 16 host bits
- Class C = 110 + 21 network bits + 8 host bits
Subnetting
- original host field -> subnet + host fields
- 128.95.1.0 (Network+Subnet Mask: 255.255.255.0)
Classless addresses (CIDR)
- Prefix/mask notation
- 128.95/16, 128.95.1/24, 198.104/14, 24.0.1/24
Classless routing

Routing daemons (Unix)

routed (RIPv1)
gated (RIPv[12], OSPF, BGP-4, multicast)
- network management tool
- http://www.gated.org

IP Routing for hosts

Single exit or multihomed?
Static default
DHCP
ICMP Router Discovery (irdpd)
Router interface readdressing

Handy tools from Van Jacobson

% traceroute mail1.microsoft.com
traceroute to mail1.microsoft.com (131.107.3.41), 30 hops max, 40 byte packets
 1  innovac.cac.washington.edu (140.142.100.100)  4 ms  0 ms  4 ms
 2  uwbr2.cac.washington.edu (140.142.150.24)  4 ms  4 ms  0 ms
 3  seabr1-gw.nwnet.net (204.200.8.5)  66 ms  12 ms  4 ms
 4  microsoft-t3-gw.nwnet.net (198.104.192.9)  4 ms  0 ms  0 ms
 5  204.200.31.1 (204.200.31.1)  4 ms  4 ms  4 ms
 6  131.107.2.99 (131.107.2.99)  4 ms  4 ms  4 ms
 7  mail1.microsoft.com (131.107.3.41)  8 ms  8 ms  4 ms

Loose source routing (-g option)
pathchar

Distance vector protocols

Bellman-Ford algorithm
Each router announces its links to neighbors
Information propagates hop-by-hop
Periodic rebroadcast
Triggered updates

RIPv1 (Routing Information Protocol)

now Historic!
520/udp
broadcasts on MA networks
metric: 1-15 hops
timers: 30 s update, 180 s timeout

RIP convergence and looping

                        A     B     C     D   
                     +------------------------
      A-----B      A |  0     1     1    - (2)
      |     |      B |  1     0    - (2)  1
      |     |      C |  1    - (2)  0     1
      C-----D      D | - (2)  1     1     0

Count-to-infinity loops
Split horizon
Poison reverse

RIP limitations

hop count
slow convergence
no VLSM support
overhead
synchronization

RIP extensions:

RIPv2
- classless
- authentication
- additional information
RIPng
- IPv6

IGRP & EIGRP

Cisco proprietary protocols
IGRP (Inter-Gateway Routing Protocol)
- Distance-vector
- Richer metric (delay, bandwidth, reliability, load)
- Timing (1988: RIP, no OSPF)
- Chuck Hedrick paper
EIGRP (Enhanced IGRP)
- Classless
- Enhanced D-V algorithm

Link state protocols

flooding of link states
faster convergence
- O(L * log L) [DV: O(R * L)]
loopfree response to topology changes

OSPF

"open" + "shortest path first"
IP protocol 89
multicast
Dijkstra calculation and database on each router
Packets
- hello
- exchange
- flooding

OSPF features

Faster convergence
Equal cost multipath
TOS-based routing
Network support: PP, Broadcast, NBMA
Classless (VLSM support)
Authentication

OSPF topology

Autonomous system (AS)
Areas
- Backbone area
Area Border Router
AS Border Router
Designated Router & Backup

OSPF network schematic

                                   Area 1
                                +---------+
                                |      R4 |
              Backbone (Area 0) |(ABR) |  |
         +---------------------------+ |  |
         |                      | R3---+  |
         |  R2--+   ASBR        +-|--|----+   
         |      +----R1-----------+  |   
         +---------------------------+
                  Internet

OSPF scaling issues

Number of routers per area
Number of adjacencies per router
Number of areas per Area BR
Router memory

IS-IS

OSI standard (designed for CLNP)
link state protocol
- similar to OSPF
- IP routing (RFC 994)
IGP for many NSPs

Multicast principles

Efficient one-to-many delivery (multimedia, real-time data)
Group
- Class D address: 1110 + 28-bit group ID
Flooding
Joins
- IGMP
Prunes
Leaf networks
Role of switches?
- IGMPv2, IEEE 802.1p

DVMRP

host-based implementation (mrouted)
tunnels
unicast non-congruency
pruning
administrative scope
MBONE

Reverse path forwarding (RPF)

       Source (S)                   
          |                  MR forwards packets 
          | Ifc 1            out Ifc N only if 
    Multicast Router (MR)    MR's route to S is
          | Ifc N            via Ifc 1 
          |

Campus DVMRP tunnel snapshot

mcast.cac.washington.edu% mrinfo 
127.0.0.1 (localhost) [version 3.8,prune,genid,mtrace]:
  140.142.116.1 -> 0.0.0.0 (local) 
      [1/1/disabled]
  140.142.116.1 -> 204.70.164.29 (dec3800-1-fddi-0.Sacramento.mci.net)
      [1/64/tunnel/leaf]
  140.142.116.1 -> 198.48.92.100 (viking.cac.washington.edu) 
      [1/1/tunnel/leaf]
  140.142.116.1 -> 192.220.249.66 (seamr2-gw.nwnet.net) 
      [1/32/tunnel/leaf]
  140.142.116.1 -> 128.95.176.140 (eos.atmos.washington.edu) 
      [1/1/tunnel]

PIM (Protocol Independent Multicast)

native
unicast/multicast congruency
Dense mode
- flood/prune
Sparse mode
- rendezvous points (RP)

Case study: UW campus backbone

Campus backbone traffic growth

"Legacy" UW campus network

Postscript version of this schematic

Next generation campus network objectives

Bandwidth scalability
- Dedicated 10-Mbps to most desktops
- Dedicated 100-Mbps to key servers
Reliable native multicast support
CoS/QoS options
Affordability

Envisioned UW campus network upgrade

Postscript version of this schematic

Ideal Next Generation Router Specification

Click here