• Types:
  • Within an "Autonomous System" (Intra-AS or Interior)
  • Between "Autonomous Systems" (Inter-AS or Exterior)
• Configurations:
  • Minimal - for isolated systems
  • Static
  • Dynamic

• 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

• 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

• 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

• 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)

• 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

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)

• 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)

• 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

• 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)

• 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

• 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