Skip to main content

Introduction

Summary

keywords

TODO

HW

Exercise*

Next time

Distance Vector

Bellman-ford equation​

ask the neighboring router about the minimum cost for reaching to destination. add each told cost to the cost needed to reach that router, and find the minimum.

when local link cost is changed, update message it to the neighboring router.

  • The neighboring router will also recompute.
  • self-stopping.

Good news travels fast. -> update of the the minimumhappens Bad news travels slow. -> count-to-infinity problem happens.

44 iterations. in example slide 5-44

solution will be a "poisoned reverse"

Comparison of LS and DV algorithms

1) DV is better in message complexity.​

DV: takes big data exchange, but only needs neighbor exchange. self stopping. LS : broadcasts the data to every other node in the network. $n*E$ messages sent

2) LS is better in Speed of Convergence​

LS : $O(n^2)$ oscilations. calculatable. DV : convergence time varies.

3) LS is better in Robustness​

LS : advertises incorrect link cost. the issue will be fixed when the node is back.

DV : error will propagate through the entire network.

So, Inside network(intra-isp) they use LS exchanging with exterior network they use DV.

How is this internet

Intra-ISP routing -> OSPF​

When Runs in one Autonomous System(AS), or one service provider.

Inter-ISP routing -> BGP​

Broader gateway protocol ( type of DV) for backbone network. inter-AS efficient in defining policies.

Why do we need to mix-use two types?​

  1. so many destination(IPv4 needs $2^32$ nodes) to make the DV table.
  2. LS need too many exchanges. the network will be conjested by itself.

Autonomous System.​

Intra-AS : within one AS

  • run on same routing algorithm. (OSPF mostly)

Inter-AS : among ASses.

  • gateway routers perform inter-domain routing.
  • The gateway router is the router that has links to the other AS.

Broader Gateway Protocol​

glue that holds the internet together.

eBGP​

propagates reachability information to neighboring ASes

iBGP​

propagates reachability information to all AS-internal routers

gateway routers will run eBGP and iBGP, and internal routers only run iBGP.