CST 311 W6

This week we learned about routing and forwarding, Dijkstra’s Routing Algorithm for Link-state, the Distance Vector Routing Algorithm, intra-As Routing and OSPF, routing among ISPs and BGP, software defined networking, ICMP and traceroute, network management and SNMP.  

The two network-layer functions are forwarding in the data plane, and routing in the control plane.  Forwarding is where packets are moved from the routers input to the routers output. Routing is where the source to destination route taken by packets is determined. There are two ways to structure the network control plane: per-router control/traditional or using a logically centralized control/software defined networking. The per-router control plane is where routing algorithms in every router interact to make forwarding tables. In the logically centralized control plane, a remote controller interacts with the control agents in routers to make the forwarding tables.

            Dijkstra’s routing algorithm is a link-state routing algorithm where link costs are known to all of the nodes and they complete the least cost paths from a starting/source node to all of the other nodes, repeating k times. The algorithms complexity is O(n^2) and O(nlogn) in the best case.

            The Distance Vector Algorithm is where each node sends its cost to its neighbors and updates its own cost with the Bellman-Ford equation where the least-cost path from x to y is computed by the minimum value of the cost to its neighbor added to the cost from the neighbor to the destination. This algorithm is iterative due to the local link cost change, distributed because of the changes only occurring when a DV is changed, and asynchronous because of the update message from the neighbor. Due to its distributed nature, a cost change can result in a cascading effect to the other nodes and may result in a count to infinity problem.

            Intra-AS routing is where routing is among hosts and routers in the same AS/network. They all run the same intra-domain protocol but routers in different AS run different intra-domain routing protocols. The gateway router at the edge of the network links to the other routers in the other AS’es. Intra-As Routing is also known as interior gateway protocols (IGP): including Routing Information Protocol (RIP), Open Shortest Path First (IS-IS or OSPF), and Interior Gateway Routing Protocol (IGRP Cisco property until 2016)

Inter-AS routing is the routing between the various AS’es including the gateways to perform inter-domain routing. The different AS finds what destinations are reachable and propagate reachability to all routers in AS1.

In OSPF, it is open source and uses the link-state algorithm to link the state packet distribution, make a topology map, and compute the route with Dijkstra’s algorithm. It floods the link-state ads to all other routers in the AS by IP.