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.
No comments:
Post a Comment