Routing on the Internet
An Introduction
|
Prof. David Bernstein
James Madison University
|
|
Computer Science Department
|
bernstdh@jmu.edu
|
Overview
- 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
- 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.)
- 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)
- Specifications:
- 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
- Transport Layer Protocol:
- 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
- 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 - Relation to Bellman/Ford-Fulkerson/Moore Algorithm(s)
Finding Paths to E
- E advertises that it is 0 hops from itself
- C advertises that it is 1 hop from E; D advertises that it
is 1 hop from E
- 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
- 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
- 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)
- Specifications:
- 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.)
- 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)
- Specifications:
- 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
- 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