Routing
LESSON 10

Outline:
Routing

Network Configurations:

• Packet Switched vs. Circuit Switched Networks:
  • Packet:
    • Datagrams are routed over many different paths through an internetwork.
    • Out-order-delivery must be handled.
  • Circuit:
    • Circuit setup is done before any transmission. All information follows the same route.
    • All data arrives in-order.

Routing of IP Datagrams:

• Routing - refers to the process of choosing a path over which to send packets and a Router refers to any device making that choice.
• Routing is done internally and externally to a network. Since datagrams traverse many networks, it is called Internet Routing (IP routing) and must decide how to cross multiple physical networks.
• Best path to route over, depends upon the:
  • Network Load
  • Datagram Length
  • Type of service requested
  • Traffic patterns at a given time of the day
• Most routing schemes simply use the shortest path
• Multihomed Hosts and Gateways both participate in routing:
  • Gateways strictly (by definition) must route packets
  • Multihomed Hosts may or may not route packets.
• Hosts officially are not to perform routing, but are equipped with much of the software needed for routing, by default.

Forms of Routing:

• Two forms (not types) of routing:
  • Direct Routing - sending from one machine directly to another, where both machines reside on the same physical network. This is the basis of all Internet communication (LANs).
  • Indirect Routing - not directly attached and must be sent to a gateway. This enables datagrams to travel outside of an autonomous system.

Forms of Routing:
Direct

• Direct Routing:
  • To see if the destination is on the same physical network:
    • Extract the NETID portion of the destination IP address
    • Compare with source's NETID(s)
  • This method is extremely efficient because of the address structure.
• To send from node A to node B:
  • Encapsulate the datagram in a physical frame
  • Bind the IP address to the physical address (ARP, RARP)
  • Transmit the frame.
• The final gateway along the total route will always perform direct routing to the destination node.

Forms of Routing:
Indirect

• Indirect Routing:
  • More difficult because it must be sent to an appropriate gateway (or default gateway).
  • Gateways form a cooperative, interconnected structure which pass datagrams to each other until a gateway can deliver the datagram directly.
• Indirect routing involves:
  • Software extraction of the datagram from the frame.
  • Selecting an appropriate route based on routing algorithm used.
  • Re-encapsulation of datagram into a new frame.
  • Setting the appropriate physical addresses in the frame header.
  • Transmit the new frame onto the network.

Table-Driven Routing:

• Internet routing tables store information on possible destinations and how to reach each of them.
• Both hosts and gateways have routing tables.
• Routing tables only need to store the NETID portion of IP addresses for routing. This keeps them small and efficient.
• Entries in the routing tables take the following form:
  • (N, G) pairs, where:
  • N - Destination network IP address.
  • G - IP address of the next gateway along the route to the destination.
• Each pair specifies only one hop and always points to gateways that can be reached across a single network (directly connected).
• Tables only need to grow if new networks are attached, NOT hosts.
  

  TO REACH HOSTS	ROUTE TO
  ON NETWORK	THIS ADDRESS

  20.0.0.0	DELIVER DIRECTLY
  30.0.0.0	DELIVER DIRECTLY
  10.0.0.0	20.0.0.5
  40.0.0.0	30.0.0.7

• Consequences of this method:
  • Usually only use a static route and do not choose concurrent routes.
  • May not know the ultimate destination is down, so final gateway must report back if this is the case (complicated).
  • (A sends to B, B sends to A) may route over different paths. Gateways must cooperate to ensure two-way communication.
• The "default" gateway entry in routing tables helps keep table sizes down (less choices).
• When a gateway performs routing, it checks the local networks first. If they are not the correct destination, send to the default gateway.

Next-Hop Addresses:

• When a datagram traverses an internetwork, the source and destination IP addresses are never changed.
• An IP address (usually of the next gateway) is computed by the IP routing algorithm and software, and is known as the next-hop address.
• The next-hop address is NOT put in the datagram or stored at all. It is passed to the Network Interface Layer which:
  • Binds next-hop address to it’s physical address.
  • Forms a frame using that physical address.
  • Encapsulates the datagram in the data field of the frame.
  • Transmits the frame.
• Next-hop address computation is a lengthy process, why not just store physical addresses (IP to hardware address bindings) and use them to compute routes ?
• Two reasons:
  • IP software and routing tables reside above the address boundary. Routing tables provide a clean software interface between IP protocol and high-level routing software (helps in debugging by just checking the routing table).
  • The point (purpose) of IP is to build an abstraction that hides underlying details.
  

Incoming Packets:

• Packets are either accepted and processed by the host, or they're discarded.
• Only gateways can forward packets (if arriving at the incorrect destination).
• If datagram reached the correct destination:
  • IP addresses match, so extract the datagram and pass it to the IP protocol module for processing.
  • IP protocol determines which higher-layer protocol to pass the datagram to.
• When receiving a datagram at a multi-homed host:
  • Each IP address identifying it (one for each network card) must be compared to the incoming packet.
  • The IP module must also contend with broadcast and multicast addresses.
• If no local IP addresses match:
  • Decrement the time to live (TTL).
  • Compute a new checksum.
  • Route the datagram (Gateways ONLY!).
• Hosts not destined to be gateways should not route datagrams, but simply discard them. If not, they may unnecessarily cause extra traffic, errors that can cause chaos, overload, etc.

Establishing Routes:

• ? What values should gateway routing tables contain.
• ? How can those values be obtained by Gateways.
  
• The solution depends on the architecture complexity, size of the internetwork, and administration policies.
• Establishing routes involves:
  • Initialization - which depends on the operating system.
  • Updating - done when routes change, either automatically or manually.

Routing with Partial Information:

Hosts can route datagrams successfully even if they only have partial routing information because they can rely on gateways as default routes.
• Routing Analogy:
  • Travel is completely dependent on road signs just as datagram routing in an internetwork depends entirely on routing tables.
• ? How sure are we that signs lead to the final destination and the shortest-path to it.
  
• Signs list default paths as long as all explicit signs point along a shortest-path and the turns for shortest-paths to all destinations are marked.
• Problems with Routing:
  • No machine is fast enough to serve as a central routing switch for all traffic to pass through.
  • Maintaining all possible destinations in all gateways is impractical.
• Routing tables in a given gateway contain partial information about possible destinations.
• Routing using partial information allows sites autonomy in making local routing changes but introduces possible inconsistencies that may make some destinations unreachable from some sources.
• Routing inconsistencies arise from:
  • Errors in routing table algorithm computation.
  • Incorrect data supplied to algorithms.
  • Transmission errors when sending results to a gateway.

Core Gateways:

• Early on, the Internet used sets of core (Internet Network Operations Center) and non-core (individual groups) gateways.
• Core systems provided reliable, consistent, authoritative routes for all possible destinations. (Internet Glue!)
• Cores gateways shared routing information and were maintained by a central authority, making them highly reliable.
• The core system was motivated by the desire to connect LANs to the ARPANET.
• To ensure global consistency, a chain of default routes formed a large cycle where, in the worst case, a datagram needed to pass through all N gateways. (Inefficient but consistent!)
• Core gateways were designed to avoid default-route inefficiencies by sharing the routing information.
  

• The core system became impractical for several reasons: Internet topology changed and became more complex
• Additional structured routing was needed for sites without a core connected to the backbone.
• Core architecture did not scale well.

Peer Backbones:

• NSFNET (National Science Foundation Network) was added to the Internet and added to the complexity.
• NSFNET and ARPANET backbones connected in multiple places making them peer backbone networks.
  

• IP routing became more difficult for two reasons:
  • Optimal routing in a peer backbone architecture requires individual routes for individual hosts.
  • Routing loops can occur if backbone managers don’t agree on and keep routes consistent among all gateways.
• Must distinguish the network topology from the routing architecture (single core systems spanning multiple backbones).
• Cannot partition the core system into subsets <>b>without losing functionality (routing loops may occur for datagrams having non-existent destinations).

Choosing a Routing Protocol:

• There are many routing protocols to choose from, each with a distinct advantage / disadvantage to a network configuration.
• Types of routing protocols include:
  • Interior & Exterior Gateway Protocols (IGP, EGP)
  • Gateway to Gateway Protocol (GGP)
  • Routing Information Protocol (RIP)
  • Open Shortest Path First (OSPF)
• Routing protocols chosen from a number of criteria:
  • Availability.
  • Speed of adaptation to finding alternate routes.
  • Speed in resolving routing loops.
  • Overhead load placed on the network, by the protocol.
  • Scalability.
  • Security.

Route Propagation:

• The core system avoided using default routes by propagating routing information to continually update routes.
• Two main types of propagation updated methods used:
  • Vector-Distance algorithms.
  • Shortest-Path-First (SPF) algorithms.

Vector-Distance Route Propagation:
(Bellman-Ford)

• Vector-Distance class of algorithms: A list of routes are kept in a table with each entry identifying a destination network and the distance to it in hops.
• Vector-Distance is defined by information in pairs, that is sent in list form within messages.
  • List of pairs: (V, D)
    • V - identifies a destination (vector)
    • D - distance in hops to that destination.

Gateway to Gateway Protocol
(GGP):

• Gateway to Gateway Protocol (GGP) - a true vector-distance protocol used in the original core gateways to exchange routing information.
• List of pairs: (N, D)
  • N - IP network address
  • D - distance to it in gateway hops (gateway = 0 hops if directly connected).
• There are four types of Gateway-to-Gateway Protocol messages which are determined by the TYPE field:
  • Routing Update
  • Update Acknowledgment
  • Echo Request
  • Echo Reply

Routing Information Protocol
(RIP):

• RIP originated from the Xerox Network Systems protocol (XNS) and was originally distributed in BSD4.2 UNIX operating systems.
• RIP is commonly known by the program which implements its functionality:
  • Routed (or route daemon)
• RIP is a vector-distance protocol which uses the number of hops as it's measurement of performance. Max. number of hops = 15.
• RIP is very limited by the requirements of today’s larger networks:
  • Always picks the smallest number of hops, regardless of the speed and traffic patterns of alternate links.
  • Cannot support subnetworking.
  • Does not scale well, respond quickly to network failures and consumes a lot of bandwidth.

Link-State Route Propagation
(SPF):

• Vector-Distance algorithms don't scale well so the primary alternative is using Link-State class algorithms (Shortest- Path-First).
• Requires each node participating to have complete topology information (map of all networks and connections).
• Gateways compute routes by applying Dijkstra's algorithm. This determines the shortest-path to all destinations from a single source.

Open Shortest Path First
(OSPF):

• OSPF is a popular link state vector protocol used in TCP/IP networks.
• Open (of OSPF) is used to mean 'openly published and not controlled by a single vendor'. This reflects it participation in providing an open system of communication.
• OSPF works directly with IP and is defined as protocol number 89.
• OSPF shares many of the ideas and techniques which were developed for the OSI IS-IS routing protocol (used in the OSI Connectionless Network Protocol - CLNP)

Last Modification: (Sunday, August 25, 1996)

All work was written, produced, and is copyrighted by Daniel Z. Tabor Jr.
Page created by Daniel Z. Tabor Jr. Copyright ©1996 Illusion Industries Inc.