University of Washington, Computing & Communications

[UW ] [COMPUTING AND COMMUNICATIONS]

Internet Routing (Part 2): Exterior Routing and State of Internet

CSE 588 lecture
May 15, 1997

Steve Corbató
corbato@cac.washington.edu

Networks and Distributed Computing, Computing & Communications
University of Washington

Tonight's plan

Exterior routing (EGP, BGP)
Current state of the Internet
Case study: UW current and future connectivity plans

IGP convergence scaling

Link-state: O(L * log L) ; Distance vector: O(R * L)
Dijkstra algorithm
- S: source node ; O: cost-ordered set of paths
- E: set of evaluated nodes ; R: set of unevaluated nodes

  E = S ; R = all other nodes ;  O = direct connects to S
  while(  valid paths in O ){
    P = shortest path in O
    remove P from O
    V = last node in P
    if( V is a member of R ){
       move V from R to E
       use V's links to generate new paths
       insert new paths into O and sort
    }
  }
  R <- unreachable

Exterior routing

hop-by-hop
outbound vs. inbound traffic
cooperative, yet loosely coordinated at best
surprisingly fragile

Exterior Gateway Protocol (EGP)

RFC 904 (Dave Mills)
deployed on Arpanet in early '80s
outmoded by late 80's
features
- partition exterior and interior routing
- core network and stubs
- autonomous systems (ASes)
- inter-AS metrics

Border Gateway Protocol (BGP)

reachability more than routing
RFC 1771
AS (16 bits, ~8000 ASNs assigned)
peerings
- 179/tcp
loop-free
- path vector (128.103/16 from AS73: 3940 3561 1)
classless (BGP-4)
persistent routes
EBGP and IBGP

Routing Information Base (RIB)

Adj-RIB-In
Loc-RIB
Adj-RIB-Out

BGP engine

TCP
- congestion susceptibility
- authentication necessary at TCP level (RST)
Packet types
- Open
- Update
- Keepalive
- Notification

BGP Attributes

Well-known mandatory
Well-known discretionary
Optional transitive
Optional non-transitive

Key Attributes

AS path (AS set or AS sequence)
Origin (IGP or EGP or Incomplete)
Next hop
Local preference

Multiexit Discriminant (MED)

          +----------------+
          |       AS1      |
          +----------------+
      MED=5  |          |  MED=10
          +----------------+
          |       AS2      |
          +----------------+

Atomic Aggregate
Aggregator

BGP decision algorithm

Deterministic (multiple paths -> one route)
Implementation specific
Cisco algorithm:
- highest local preference
- shortest AS path
- origin type (IGP < EGP < incomplete)
- lowest MED
- external path over internal path
- closest IGP neighbor
- lowest BGP router ID

Influencing inbound traffic

Multiply homed sites
- load balancing
- provider-symmetric routing
Limited influence at best
- AS-path prepend hack
- Dynamic Provider Attribute (DPA)?

IBGP scaling

nominally full mesh
- IBGP peer does not readvertise routes learned from another IBGP peer
- O( N * N )
Confederations
Route reflection

BGP Communities

optional transitive attribute
group of destinations with common properties
permits sub-AS granularity
predefined communities
- no-export
- no-advertise

CIDR and aggregation

Prefix/mask notation
Scalability of backbone routing tables
Congruence of addressing and topology
Provider assigned vs. provider independent addressing
- PAs usually non-portable

Longest match routing

24.0.1/24 vs 24/8
Multihoming difficulties

                 Internet
   124.0/16    /          \  124.0.1/24
              /            \
           ISP1           ISP2           
              \            /
  124.0.1/24   \          /  124.0.1/24  
                 Customer

Transit AS design

      NSP
        +--AS2      ISP
       /    |       AS4
      /     |        |?
    AS1----AS3----Customer
    NSP    ISP

Singly homed sites
- Statics (customer: default; ISP: customer route objects)
Multiply homed sites
- BGP
IGP
- OSPF to carry next hops and loopbacks
- IBGP to carry external and customer routes (EBGP and redistributed statics)
Policy
- filter customer announcements
- stable CIDR aggregation

Route servers

public exchange point BGP peerings: O(N * N)
route server peerings: O(N)
Routing Arbiter project (Merit/ISI)
- gated servers
- 3rd party reliance

Routing registries

route object and routing policy databases
distinct from IP address assignment database (InterNIC)
database formats
- NSFNET PRDB
- RIPE-181
- RPSL
Global Routing Registry (GRR)

EGP futures

IDRP
BGP-5

Internetwork design tips

Design for routing scalability
Build clear demarcations
Plan for richer interconnectivity
Avoid statics (except at the edges)
Optimize stability at the edges
- Don't trust customer announcements
Think globally (GRR, CIDR)
- Track NANOG, IEPG, IETF (OSPF, IDR, IDMR, RPSL, IPv6), ARIN

State of the Internet:
Recent and current history

NSFNET transition (1994-95)
- Multiple NSPs
- NAPs
- Routing arbiter
- vBNS
Current status
- Backbone BW
- Bilateral peerings
- NSPs vs. ISPs
- Peering vs. transit

Internet in transition

NSFNet backbone (1987-1995)
- Campus networks -> Regionals -> NSFNET
- Backbone: 1987 - T1, 1993 - DS3
- Traffic exponential growth (11 month doubling time)
1995: New architecture
- NSPs (MCI*, Sprint*, BBN/AT&T, UUNet, PSI, ANS/AOL)
  - DS3 backbones
- NAPs
- vBNS

Internet in transition (continued)

1996 status
- Exponential growth (4-8 month doubling times)
- MCI: OC-12 backbone, others -> OC-3
- Rising prices (DS3: $250k flat rate -> $750k measured rate)
- Private peerings between NSPs
- Increasing NSP entropy for higher ed
- Pressure for NSP cooperation (NOCs, statistics)
- 70-90% of higher ed traffic to non-EDU sites
- Over 3,000 ISPs nationally
1997 status
- Accelerating acquisitions (Verio<-NWNet, GTE<-BBN)
- Some NSPs stop peering with ISPs at exchange points

Technical details

Backbone routers
- Bandwidth (DS3, OC-3, need OC-12 and OC-48 soon)
- Vendors: Cisco, Ascend/Netstar, Bay
Transport
- ATM vs. PPP-over-SONET
Scalability issues
- Route flap
- Number of routers and peers
- L2/L3 integration

Internet Routing Table Size

Internet Routing Table - Mask Distribution

NSP prefix-length inbound filtering at exchange points

Internet Routing Table - Age Distribution

NSP route flap dampening

UW Internet Flows

Evolving UW Interconnectivity

Local exchange point: Seattle Network-to-Network Access Point (SNNAP)

An outgrowth of the interconnect for three K-20 sector networks
Two redundant, distributed, high-performance switches with border router attachments
SNNAP expansion
- Government & business networks, local ISPs
- Location of additional switches in downtown Seattle
- Bilateral peering agreements
Designed to keep locally destined traffic within the area
- Emergence of local content
- Complementary to primary Internet connectivity

SNNAP schematic

SNNAP: Rules of the road

Customer acknowledges absence of mandatory MLPA
Networks connect via dedicated switch port(s)
No negative impact on switch performance
BGP-4 for peering
No broadcast or multicast traffic across switch media
- MBONE traffic via DVMRP tunnels
No unauthorized use of another connectee's resources
Policy concerning transit among consenting nets?
SNNAP.ORG is the ultimate arbiter of policy
- may disable ports after warning for rule violation

vBNS: very high speed Backbone Network Service

NSF-sponsored network operated by MCI
5 NSF supercomputer centers + NAPs
1995: OC-3 backbone
Originally conceived as testbed network
- High performance networking
- Distributed supercomputing
- Not a 7x24 service
NSF 96-64: ~30 higher ed attachments annually
Liberalized AUP, production status
1997: OC-12 with federal network interconnects (DoE, NASA)
First manifestation of Internet2

Evolution of Acceptable Use Policies (AUPs)

NSFNET

           From/To      |    R&E    | Elsewhere  |
           -------------+-----------+------------+
            R&E         |    OK     |    OK      |
           -------------+-----------+------------+
            Elsewhere   |    OK     |     X      |
           -------------+-----------+------------+

New vBNS
- not a transit network for connected institutions (VCI)

           From/To      |    VCI    |  Fed nets  | Elsewhere  |
           -------------+-----------+------------+------------+
            VCI         |    OK     |    OK      |     X      |
           -------------+-----------+------------+------------+
            Fed nets    |    OK     |     X      |     X      |
           -------------+-----------+------------+------------+
            Elsewhere   |     X     |     X      |     X      |
           -------------+-----------+------------+------------+

Internet challenges facing higher education

Three fundamental problems
- Commodity Internet is congested and performance is variable
- No excess bandwidth for advanced application development
- Ubiquitous 1-10 Mbps
Internet2 will not solve all problems - just #2 and the intra-higher ed component of #1

Internet2 architectural principles

Common bearer service: IP
Best-effort packet delivery -> differentiated communications service
Application-driven network service characteristics
Advanced communications infrastructure for R&E
OC-12 backbone connecting GigaPOPs
- Transport: ATM-over-SONET or Packet-over-SONET
- Can we procure raw SONET?
Redundant Network Operations Centers
Open network performance statistics

Washington K-20 Telecommunications Network

Services
- Primary transport via leased SONET
- Intranet
- Switched video
- Satellite uplinks
Implementation
- Network of networks
  - 3 sectors: 4-year & 2-year colleges, K-12
- Phase 1: college main campuses and K-12 ESDs (9)
- Phase 2: college branch campuses and K-12 SDs (296)
- $42M state appropriation in 1996
- current: Phase 1 deployment

K-20 schematic

Washington K-20 Intranet

Bandwidth scaling and conservation
- Backbone and attachment connectivity: NxT1 (N=1-7) -> DS3
- Information caching
Designed for multiply interconnected networks
- SNNAP
Advanced IP application support
- Multimedia via native multicast
- CoS/QoS support