CS138-lecture-20210422

Routing algorithms #

image_2021-04-22-09-25-52 image_2021-04-22-09-26-33

Graph abstraction #

image_2021-04-22-09-26-37 image_2021-04-22-09-29-36

Algorithm classifications #

image_2021-04-22-09-31-12 image_2021-04-22-09-35-52

Dijkstra’s algorithm #

image_2021-04-22-09-36-17 image_2021-04-22-09-48-09 image_2021-04-22-09-55-53 image_2021-04-22-09-56-29 image_2021-04-22-10-16-55

Hierarchical routing #

image_2021-04-22-10-18-34 image_2021-04-22-10-20-20

There can be multiple links between regions.

image_2021-04-22-10-22-37 image_2021-04-22-10-24-17 image_2021-04-22-10-26-22 image_2021-04-22-10-27-51 image_2021-04-22-10-28-59

Routing the internet #

image_2021-04-22-10-30-24

OSPF #

image_2021-04-22-10-31-26 image_2021-04-22-10-32-01

Link state algorithms, because they are global, works perfect for smaller networks.

image_2021-04-22-10-34-07

BGP #

image_2021-04-22-10-34-39

To help remember: iBGP = internal border gateway protocol, eBGP = external border gateway protocol

image_2021-04-22-10-35-59 image_2021-04-22-10-37-46 image_2021-04-22-10-39-02 image_2021-04-22-10-42-25 image_2021-04-22-10-43-09 image_2021-04-22-10-43-16 image_2021-04-22-10-44-39 image_2021-04-22-10-46-03

Broadcast and multicast routing #

image_2021-04-22-10-47-59 image_2021-04-22-10-49-16 image_2021-04-22-10-56-58 image_2021-04-22-10-58-16