Routing

Package Delivering

Routing Basic

Routing is about solving a simple question

Legacy Solutions

Flooding

each router send the package to each port except the incoming one

• Inefficient
• Package can keep looping in the network
• Simple, do not need to know any topology information about the whole network
• The router do not need any thing like forwarding table, they just copy and send packages

Source Routing

The path is specified in the package

• “End-to-end” solution, the jobs is delegated to host A, A is responsible for choosing path now.

• Routers just look the header and send the package, no forwarding table needed.

• Host A must know the topology of the network first

• The router list may be very very long

• Used when end user want to control the routing path

Nowaday Network

Forwarding Table

We already know this

• But how can a router generate the forwarding table ? Routers populate the forwarding tables.
• So we have pre-destination state(forwarding table) in the router,but the flow can still be mutable.

Spanning Tree

a tree with no loop, can each leaf node can reach the root

But how can we know which spanning tree is the most efficient?

Possible metrics

• minimum distance
• minimun hop-count
• minimun delay
• maximize the throughput
• most reliable path
• …..

Implementation

Weighted graph + Minimun cost spanning tree

• We give each path a wighth according to our metric

Next, you might think that we can run some kind of algorithm to generate the spanning tree then have the forwarding table

However, this is the Internet, it is dynamic(new devices keep coming in, old ones get evicted) and large(billions of nodes and paths), running a algorithm at such scale is unpractical.

So we have protocols!

We let router run the algorithm on small scale network and generate a “local forwarding table” and then populate it to others, in this way, we can let routers exchange topology information!

Multipath

send packages via multiple paths, try to distribute traffic evenly over the network

Multicast

Router will do some replication in a broadcast situation

Generate the minimum cost spanning tree

Distance Vector:Bellman Ford Algorithm

Assumption : The router know cost of each link of its neighbor and the current distance between $R$ and itself.

How can we find a minimun cost spnning tree to router $R$ in a network

1. Overall distance vector $\vec{C} = {C_1 , C_2 , …,C_n}$,$C_i$ is the current distance(cost) between $R_i$ and $R$
2. The distance vector is initialized to C = [∞ , ∞ , ... , ∞]

• Each $T$ seconds, $R_i$ send $C_i$ to its neighbors
• If $R_i$ learn lower cost path to $R$ , updating $C_i$
• Repeat

Example

def show(C , r):
    print("Distance Vector at round {}:".format(r) , C)

def update(i , newcost):
   current = C[i-1]
   if newcost < current:
       C[i-1] = newcost

# initialization
infty = 2**64
numberOfRouter = 8
C = [infty for i in range(numberOfRouter)]
show(C , 0)

# Round 1, R8 update its neighbors
C[2] = 4
C[4] = 6
C[6] = 1
C[5] = 2
show(C , 1)

# Round 2, [R3,R5,R7,R6] update their neighbors
# R3
R3 = C[2]
update(1 , 4 + R3)
update(2 , 5 + R3)

# R5
R5 = C[4]
update(2,1+R5)
update(4,2+R5)

# R7
R7 = C[6]
update(4,1+R7)

# R6
R6 = C[5]
update(4,4+R6)

show(C,2)

# Round 3 , each router will try to update its neighbors
R1,R2,R3,R4,R5,R6,R7,R8 = tuple(C)
update(2,1+R1)
update(3,4+R1)

update(1,1+R2)
update(3,5+R2)
update(5,1+R2)
update(4,4+R2)

update(1,4+R3)
update(2,5+R3)

update(2,4+R4)
update(5,2+R4)
update(7,1+R4)
update(6,4+R4)

update(2,1+R5)
update(4,2+R5)

update(4,4+R6)

update(4,1+R7)

show(C,3)

# Round 4 , each router will try to update its neighbors
for R in C:
    for neighbor in R.neighbors:
        update(neighbor,R+weight)
        
# Round after
....

$ python3 example.py
Distance Vector at round 0: [18446744073709551616, 18446744073709551616, 18446744073709551616, 18446744073709551616, 18446744073709551616, 18446744073709551616, 18446744073709551616, 18446744073709551616]
Distance Vector at round 1: [18446744073709551616, 18446744073709551616, 4, 18446744073709551616, 6, 2, 1, 18446744073709551616]
Distance Vector at round 2: [8, 7, 4, 2, 6, 2, 1, 18446744073709551616]
Distance Vector at round 3: [8, 6, 4, 2, 4, 2, 1, 18446744073709551616]
Distance Vector at round 4: [7, 5, 4, 2, 4, 2, 1, 18446744073709551616]
Distance Vector at round 5: [6, 5, 4, 2, 4, 2, 1, 18446744073709551616]
Distance Vector at round 6: [6, 5, 4, 2, 4, 2, 1, 18446744073709551616]
Distance Vector at round 7: [6, 5, 4, 2, 4, 2, 1, 18446744073709551616]
Distance Vector at round 8: [6, 5, 4, 2, 4, 2, 1, 18446744073709551616]

Analysis

• The algorithm always converge

• If cost changes or link fails, “bad news travels slowly”

  • the failed link cost become infty
  • Then neighbors will feed each other with the bad information

• Used in RIP(Router Information Protocol) in the past
• Distributed algorithm

Link State Algorithm : Dijkstra’s shortest path first algorithm

Each router tell its neighbor about its own link state(topology information), and then run Dijkstra independently

The algorithm

Adding nodes one by one

Analysis

• Each router need to know the entire link state and network topology
• Basis of OSPF(Open Shortest Path First)

Routing in Internet

The Internet is so large that we cannot run any kind of algorithm on it, and it is impossible for all router to use a same protocol. We divide network into autonomous systems(AS)

• Autonomous system gives different organization autonomies, they can configure their own network now
• The routers can be built with different hardware features, too

Hierarchy of the Internet

• Autonomous system is the basic building block
  • within a AS, the owner can decide how the routing is done.
  • between ASs, must be BGP-4(Border Gateway Protocol version 4)
• Finding the AS number

$ traceroute -a <ip>
$ dig <domain name or IP>

Interior Routing Protocol

RIP(Routing Information Protocol)

• Distance Vector
• No authentication of updating !!!
• Out of date

OSPF(Open Shortest Path First)

• Link state
• Dijkstra
• Authenticated updating
• Widely used nowadays

Exterior Routing Protocol : BGP-4

Basic

Path vector : IP 202.49.0.0/16 can be reached by [ AS102 , AS3259 , AS32 ,… ]

• ISP(Internet Service Provider) provide transit
• peer relationship