Understanding Routing Algorithms

Routing Algorithms

• Routing algorithms are methods or protocols used to find the best path for data packets from source to destination.
• Key goals include optimality, scalability, and robustness.
• Optimality aims to find the best path.
• Scalability refers to being able to work in large networks.
• Robustness means handling failures gracefully.

How Routing Algorithms Function

• Routers accumulate data about the network topology.
• Open Shortest Path First (OSPF) utilizes Link-State Advertisements (LSAs).
• Path Calculation: Routers determine the best paths using algorithms like Dijkstra's algorithm in OSPF.
• Routing Table Update: Routers update their routing tables.
• An example would be a router adding an entry for destination 192.168.1.0/24.
• Forwarding Packets: Routers then forward packets based on the routing table.

Dynamic Routing Protocol Concepts

• Dynamic routing uses tables or databases for operations, which are stored in RAM.
• Routing protocols employ various messages to find neighboring routers and exchange routing information.
• Algorithms are used for facilitating routing information and best path determination.
• Routing Protocols determine the optimal path to each network.
• The route is offered to the routing table.
• The route is installed if no other routing source has a lower Administrative Distance (AD).

Importance of Routing Algorithms

• Routing algorithms provide fault tolerance by rerouting traffic in response to link failures.
• They enable network scalability which allows networks to grow without performance degradation.
• Quality of Service is achieved through efficient data delivery, taking the shortest or least congested path.
• Load balancing is achieved through distribution of traffic across multiple paths.
• Security is an important aspect.

Fault Tolerance

• A fault tolerant network limits the impact of failure by limiting the number of affected devices.
• Multiple paths are required for fault tolerance.
• Packet switching splits traffic into packets routed over a network for redundancy.
• In packet switching, each packet can take a different path to the destination.
• Circuit-switched networks, which establish dedicated circuits, cannot provide this level of fault tolerance.

Scalability

• A scalable network quickly and easily supports new users and applications without impacting service performance.
• Network designers adhere to accepted standards and protocols for scalable networks.

Quality of Service (QoS)

• Voice and live video transmissions need higher service expectations so QoS implementation assures reliable content delivery for all users.
• QoS can resolve issues like breaks/pauses in live video caused by high bandwidth demand.
• Routers manage data and voice traffic more effectively with a QoS policy.

Security

• Network security entails addressing infrastructure and information security.
• Infrastructure security involves physical device security and unauthorized software access prevention.
• Information security refers to data protection over the network.
• Three main goals are maintaining confidentiality, integrity, and availability.
• Confidentiality means only intended recipients can read the data.
• Integrity ensures data is unaltered during transmission
• Availability assures authorized users timely and reliable data access.

Packet Forwarding Decision Process

• The system receives a data link frame with an encapsulated IP packet via an ingress interface.
• The router checks the destination IP address of the packet header and consults the IP routing table.
• The router identifies the longest matching prefix in the routing table.
• The router encapsulates the packet in a data link frame which forwards through the egress interface.
• The egress interface forwards to the destination device or next-hop router.
• If there is no matching route entry, the packet is dropped.

Forwarding Packets to a Directly Connected Device

• If the route entry indicates that the egress interface is a directly connected network, the packet is forwarded directly to the destination device.
• This usually occurs with an Ethernet LAN.
• To encapsulate in the Ethernet frame, determine the correct destination media access control address matched to the destination IP address.
• The process varies based on if the packet is IPv4 or IPv6.

Forwarding Packets to the Next-Hop Router

• If the destination IP address is on a remote network, the packet is forwarded to the next-hop router specified in the route entry.
• A similar process like Address Resolution Protocol (ARP) and Internet Control Message Protocol version 6 (ICMPv6) Neighbor Discovery, the system will search for the IP address of the next-hop router instead of the destination IP address of the packet.
• This process can vary on other Layer 2 networks.

Drop the Packet

• If there is no match between the IP address and the prefix and there is no default route, the packet will be dropped.

End-To-End Packet Forwarding

• The key responsibility is to encapsulate packets in the fitting data link frame for the outgoing interface.
• For example, the data link frame format for a serial link could be one of the following:
  • Point-to-Point (PPP) protocol
  • High-Level Data Link Control (HDLC) protocol
  • Layer 2 protocol such Ethernet protocol

Packet Forwarding Mechanisms

• The packet forward function is to encapsulate packets in the fitting data link frame for the outgoing interface.
• The faster a router does this, the faster packets can be forwarded by it/
• The router includes the following three forwarding mechanisms:
  • Process switching
  • Fast switching
  • Cisco Express Forwarding (CEF)

Routing at Host

• An IP network layer key role is to direct packets across hosts.
• A host can send packets to itself for testing purposes through the loopback interface and address 127.0.0.1.
• Packets can be sent to a local host on the same local network as the sending host, which share same network address.
• Packets can be sent to a remote host on a remote network, which don't share the same network address.
• The system determines local or remote status through source and IPv4 address and the subnet mask.

Default Gateway

• The component that can route traffic out to other networks, traffic routes out local networks
• Occurs when the destination host exists external to the same local network as the sending host.
• The gateway will know how/where to send packets using its routing table.
• The sending gateway won't have to know how/where to send packets to the default gateway router.

Using the Default Gateway

• A routing table typically includes a gateway address, which is the IP address of the router for the host’s network.
• Host gets IPv4 address from Dynamic Host Configuration Protocol (DHCP) or may be manually installed.
• Once configured, it makes a default route in the routing table of a host, which sends a packet if it has to contact a network external to the local network.

Routing in Routers

• Three principles address proper dynamic or static routing configuration, between the source and destination devices.
• Every router makes decisions on its own, using the table data.
• Information in a table of one router may not match another.
• Route data doesn’t provide return directions necessarily.

Routing Table Principles

• A router can only forward packets using its own routing table
• The router will not know the routes in other tables like R2.
• R1 can have a route in its table to a network, but it doesn't mean R2 is aware of the same network.
• Using the source IP address, if R1 knows how to forward the packet out, it doesn't indicate it how to forward originating packets.

Route Sources

• Direct Connections: Added to the routing table once a local interface is configured with an Internet Protocol(IP) address, a subnet mask(prefix length) and has an active status.
• Remote: Networks that are disconnected from the router, and the router knows about it two ways.
  • Static route: Added when a route is manually configured.
  • Dynamic Routing Protocols: Protocols automatically add the table when dynamically learning external networks.
• Default: Designates a next-hop router if one does not contain a specific route that matches the destination IP address.
  • It can either be manually entered or learned automatically.
  • Has a /0 prefix length, so if you don't need to match any bits, you use this route.
  • It's referred to as a gateway of last resort.

Static Routes

• Static or dynamic routing provides access to remote networks once direct connections have been established.
• These routes are manually established.
• They identify explicit pathways between networking devices.
• They might not be updated automtically and would need to be reconfigured when changing in network topology.

Static Route Uses

• Helps with easing table maintenance within a smaller network.
• Has a single default route to designate an IP to any other network that doesn't fit in table.
• Static Routes helps make traffic move to and from stub/endpoint networks.
  • A stub network can send data only to one route.

Static Routes in the IP Routing Table

• The topology is simplified to one Local-Area Network (LAN) attached to a singular router.
• The IPv4 and IPv6 static routes have been configured on Router 1 to reach 10.0.4.0/24 and 2001:db8:acad:4::/64 networks on Router 2(R2).

Dynamic Routing Protocols

• Dynamic routing protocols allow routers to share information about the reachability and status of remote networks.
• Dynamic routing protocols activities includes network discovery and maintaining routing tables.

Default Route

• Specifies a next-hop router to use if there's not a specific route available to match the designation address.
• Has an IPv4/6 route entry, but with a single matched bit between two addresses.

IPv4 Routing Table Structure

• An enty indented is a "child" path If it is the Subnet of class A,B or C, then it will be indented as a child route
• Direct connections will always be indented as child paths because of the interface address on it's "/32" table.
  • The child will contain all forwarding/next-hop information.
• If not shown like the mentioned example, then there is no source code.
  • If there isn't a source code, that table is a "parent" route.

Administrative Distance

• Each route entry can be in the routing table at once with any size/length.
• Though the table can see the same network addresses with multiple sources there can be a specific set of circumstances.
• A separate or distinct path can reach a destination because of the metric or protocol.

Administrative Distance (AD)

• IOS uses administrative distance (AD) to help install the correct route.
• AD stands for "Trustworthiness." The lower the AD, the more trusted that route source is.

Static vs Dynamic

• Static and Dynamic Routing are not exactly exclusive.
• Though most connections use both Dynamic Protocols and Static Routes

When to use Static Routes

• When forwarding to a service provider
• You do not want to learn by dynamic routing protocols
• When a server needs to call/connect to a network
• For Stub networks that need to connect.
• Good for networks on smaller scales and want more control

When to use Dynamic Routing Protocols

• If needing more than a handful of routers.
• Needing to automatically determine changes in the topology
• For scalability and autolearning while networks become big.

Best Path

• Best path: Path with the lowest metric (quantitative value used to measure distance to network), decided by the routing protocol value.
• Protocols uses the rules and metrics to update or build the tables.

Routing Protocols Metrics

• Routing Information Protocol(RIP): Metric is the “hop count” with max 15 hops - each router hops the hop count.
• Open Shortest Path First (OSPF): Metric is “cost"- based from bandwidth from source to destination (faster links equals lower costs.)
• Enhanced Interior Gateway Routing Protocol (EIGRP): Calculates the metric by finding the slowest bandwidth/delay. It can potentially also take load/reliability.

Dynamic Protocol: Distance Vector

• Shares its vector with neighboring routers
• Vector includes all known networks and its distances.
• Has simple implementation and overhead in smaller networks
  • Also used in IP routing
• Has disadvantages such as:
  • Slower path time and routing loops

Dynamic Protocol: Link State

• Unlike the Distance-Vector Protocol, Link-State is sharing information of it all its link states, and builds maps of networks.
• Uses the Dijkstra Algorithm to find the shortest path.
• Uses (OSPF), or open source path.
• Advantages include:
  • Fast converge time
  • support of larger networks

Differences between Vector and Link State

• The table shows the comparison of the differences between Dynamic/Static Routing:
• Feature: -Convergence Time: - Vector: Slow - Link State: Fast
• Updates: - Vector: Often - Link State: Event Trigger
• Loops: - Vector: Easily Prone - Link State: Less Subject
• Configuration: - Vector: Easy - Link State: Difficult
• Network Types: - Vector: Broadcasts for updates - Link State: Multicasts updates
• Topology: - Vector: Doesn't know the network - Link State: Knows the network
• Summarization: - Vector: No - Link State: Yes
• Path Calculation: - Vector: Hop Count - Link State: Shortest Path
• Scalability: - Vector: Limited - Link State: High
• Protocol: - Vector: RIP, IGRP - Link State: OSPF, IS-IS
• Algorithm: - Vector: Bredford - Link State: Dijkstra
• manual route summarization - Vector and link state both have yes
• Metric: - Vector: Hop Count - Link State: Link

Challenges in Routing Algorithms

• Scalability, where algorithms need to handle large networks with millions of routes.
  • BGP scales to the internet.
• Convergence Time, or the time it takes for all routers to agree on network topology.
  • Slow convergence can cause routing loops.
• Security, where systems need to be protected against hijacking
  • BGPsec security is helpful.
• Load Balancing, which is distributing traffic across multiple paths
  • OSPF supports ECMP(Equal-Cost Multipath).

Load Balancing

• In the system, there needs to be equivalent metrics to forwared using the packet
• Configured correctly and with the correct performance it can cause better networking
• Automatic in dynamic routes.
• Enabled with static routes while the routes are the same, or near the same.

Commands to Verify Router Configuration

• Common verification commands include the following:
  • show ip interface brief
  • show running-config interface interface-type number
  • show interfaces -show ip interface
  • show ip route
  • ping
• Replace ip with ipv6 for IPv6.