CST311 - Week 6

 

CST311 – Intro to Computer Networks 

We continue the course by reviewing the second plane of the Network layer this week, particularly the control plane. The routing function encompasses path selection, updating routing tables, and executing the appropriate protocol within a system. Routing algorithms come into play to compute the best paths or routes from the source to the destination. In Link-state LS, the links cost are known among all nodes. A protocol that uses LS is OSPF or Open Short Path First. Another type of decentralized algorithm that bases its calculation on the least cost path is the DV or Distance-Vector algorithm. The cost of a path is only available to neighboring nodes; however, information learned from estimated paths is exchanged among nodes to calculate the path with the lowest overall cost. DV is used with protocols like BGP and RIP.

The module introduces an important graph algorithm called Dijkstra’s algorithm, which is an efficient centralized algorithm for finding the least cost path for all source vertexes. The Big O time complexity of Dijkstra’s algorithm depends on how many nodes are searched overall; this happens to be n(n+1)/2, this complexity of O(n^2). Overall, the DV algorithm converges changes to direct neighbors only slowly, while the LS algorithm converges faster to all nodes.

We also viewed the autonomous systems (AS), which consist of a number of routers within an ISP. In the same AS, the protocol that runs the routing algorithm is the intra-autonomous system routing protocol - OSPF LS algorithm between the routers, allowing multiple path costs if found and ways to authenticate the exchanged information between routers AS systems communicate with each other by advertising on gateway router located at the edge of each AS. BGP is used for external connection (eBGP) or within the internal AS (iBGP) to exchange routing information. AS routing policy is used to facilitate desired traffic across inter-AS routing.

The module ends with a brief overview of SDN in the control plane and an introduction to the ICMP protocol, or Internet Control Message Protocol.