- Forward


Routing on the Internet
An Introduction


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Overview
Back SMYC Forward
  • Types:
    • Within an "Autonomous System" (Intra-AS or Interior)
    • Between "Autonomous Systems" (Inter-AS or Exterior)
  • Configurations:
    • Minimal - for isolated systems
    • Static
    • Dynamic
Routing Protocols
Back SMYC Forward
  • Routing Information Protocol (RIP):
    • Generally for small networks
    • Sometimes classified as a distance-vector routing protocol
  • Open Shortest Path First (OSPF):
    • Generally for larger networks
    • Sometimes classified as a link-state routing protocol
  • Border Gateway Protocol (BGP):
    • Used for inter-AS routing
Routing Protocols (cont.)
Back SMYC Forward
  • An Observation:
    • Routing protocols are often discussed in the context of the Internet Protocol
  • Something to be Aware Of:
    • Since these protocols use UDP or TCP they should be considered application layer protocols
Routing Information Protocol (RIP)
Back SMYC Forward
  • Specifications:
    • Version 1: RFC 1058
    • Version 2: RFC 2453
  • General Approach:
    • Based on algorithms discussed by Bellman; Ford and Fulkerson; and Moore
    • Uses distance tables (via intermediate nodes) where, in the words of the RFC, "1 is always used for the cost" (i.e., the distance is measured in hops)
    • Distances greater than 15 are treated as infinite
RIP Frames
Back SMYC Forward
  • Transport Layer Protocol:
    • UDP on port 520
  • Frame Format:
    • Command (8 bits) - either request (1) or response (2)
    • Version (8 bits)
    • Zero (16 bits)
    • Address Family Identifier (8 bits)
    • Zero (16 bits)
    • IP Address (32 bits)
    • Zero (32 bits)
    • Distance a.k.a. Metric (16 bits)
RIP - The Process
Back SMYC Forward
  • Initialization:
    • A host/router sends a request asking for distances from neighboring routers
  • Updates:
    • Distances are advertised every 30 seconds (which is counted-down using the update timer) using a response message
    • Distances are also advertised when a least cost path changes
    • When a new distance is received, the distance table is updated
RIP - An Example
Back SMYC Forward

Example

rip-network
rip-tables
RIP - Relation to Bellman/Ford-Fulkerson/Moore Algorithm(s)
Back SMYC Forward
rip-convergence

Finding Paths to E

  1. E advertises that it is 0 hops from itself
  2. C advertises that it is 1 hop from E; D advertises that it is 1 hop from E
  3. B advertises that it is 2 hops from E through C and that it is 2 hops from E through D; A advertises that it is 2 hops from E through C
  4. A learns that it is 3 hops from E through B but doesn't make a change (since that is worse than 2 hops to E through C)
RIP - Some Details
Back SMYC Forward
  • Issues:
    • v1 only supports classfull addresses (v2 supports CIDR)
    • Slow to converge (good news travels quickly, bad news travels slowly)
  • Link Failure and Recovery:
    • If no advertisement is heard for 180 sec (which is counted-down by the invalid/expiration timer) then the neighbor/link is declared dead
  • RIP in Linux:
    • Tables are managed by an application-level process named routed (that advertises using UDP)
Open Shortest Path First (OSPF)
Back SMYC Forward
  • Specifications:
    • Version 1: RFC 1131
    • Version 2: RFC 1247
  • General Approach:
    • Each node knows the entire network
    • Routes are calculated using a label setting algorithm (calculates the shortest path to all subnets)
    • Link costs/weights are determined by the system administrator (link costs/weights of 1 lead to minimum-hop routing but other values can be used)
  • Updates:
    • Advertisements are disseminated to the entire system
    • Even if a link's state has not changed it will be broadcast at least once every 30 minutes
Open Shortest Path First (cont.)
Back SMYC Forward
  • TCP is used (MOSPF provides extensions that support multicast)
  • Messages can be authenticated (preventing intruders from disseminating information)
  • Supports ties (i.e., multiple routes with the same cost)
  • Can be implemented hierarchically (by creating areas)
Border Gateway Protocol (BGP)
Back SMYC Forward
  • Specifications:
    • RFC 1163
    • Application: RFC 1164
  • General Approach:
    • Each border gateway broadcasts an entire path to its neighbors (rather than just the edge distance) using TCP over a semi-permanent connection (on port 179)
  • Why Not Use an Intra-AS Protocol?
    • May want to control who uses your network
    • May have different performance preferences
    • Different network scales
BGP Fundamentals
Back SMYC Forward
  • Terms:
    • BGP Peers - The two routers at the end of a semi-permanent connection between ASs
    • BGP Session - The connection and all of the messages sent over that connection
  • BGP Attributes:
    • AS-PATH contains the ASs through which the advertisement has passed
    • NEXT-HOP is the router that begins the AS-PATH
There's Always More to Learn
Back -