Routing

• deciding path on which packets are forwarded
• Method for routers to construct the forwarding table

Routing protocols taxonomy

Autonomous System(AS)

• Internet : Network of Networks
• Autonomous System : a large network or a group of networks that has a unified routing policy
• Controlled by ISP or an organization

Intra vs. Inter domain Routin

• Intra-domain (Intra-AS) routing

  • routing among hosts, routers in same AS("network")

  • AS에 있는 모든 router들은 same intra-domain protocol을 돌려야 한다

  • 다른 AS에 있는 router들은 different intra-domain routing protocol을 돌릴 수 있다.

  • gateway router : AS의 'edge'에 있는 router. 다른 AS의 router와의 link가 있다

• Inter-domain (Inter-AS) routing
  • routing among AS'es
  • gateways perform inter-domain routing
    as well as intra-domain routing

---

Distance vector routing

• 각 destination마다 next node를 기록한다
• neighbor끼리 table을 교환하고, 그 정보를 이용해서 내 table을 update한다
• 정보는 routing table에 저장된다
  • (destination, distance, next node) -> distance vector

Algorithm

What is the shortest path from A to C?

• A의 routing table에는 각각의 destination을 위한 "distance vector"가 저장된다.

1. 처음에는 direct neighbor에 대한 경로만 저장한다.
   

2. 이제, direct neighbor끼리 table을 교환한다
   Each node sends its routing table to all its direct neighbors

   • Node D가 E에게 table을 보내고, 그걸 보고 E가 자신의 table을 update한다
     

   • Node B -> Node A
     

   • Node E -> Node A
     

이런 방식으로 All nodes exchange tables

• send my table to all my neighbors
• If my table is updated, send my table again
• Also, nodes send its table periodically

3. The final state of routing tables
   

Suppose the link between D and E breaks!

1. 일단 D와 E가 제일 먼저 detect하고 본인들의 table을 update한다

2. D와 E가 neigbors에게 update된 table들을 또 보내고 각자 또 update한다
   (결국은 다시 converge가 된다)
   

• Node들은 주기적으로 direct neigbors와 routing table을 교환한다
• 만약 network 상에 어떤 변화가 있으면, routing table이 그 변화를 반영하기 위해 update된다
• 각각의 route information은 timer가 있다. 만약 특정 시간 내에 route가 update되지 않으면, 그것은 invalidated(무효화)된다.

Count-to-infinity problem

After rout table is finalized, the link between A and B breaks

1. B는 A로 가는 길을 모르게 되고(A : -, C : 1), C가 routing table(A : 2, B : 1)을 B에게 보내준다
   문제는 C는 저 길이 끊어진지 모르고 그 길을 통해 A로 가는 정보를 B에게 보내준다는 것이다

2. 그걸 받고 B는 table을 update한다 (A : 3, C : 1)
   그리고 이걸 C한테 보낸다

3. C는 기존에 A로 가는 길이 B를 거쳐서 갔기 때문에, B가 A로 가는 길을 update한 걸 보고, 본인의 table을 update한다. (A : 4, B : 1)
   그리고 이걸 B한테 보낸다

4. B도 역시 A로 가는 길을 C 거쳐서 가는 것으로 했기 때문에 또 update한다 (A : 5, C : 1)

5. 이 왔다갔다를 계속해서 진행하다가,
   C 입장에서 값이 25를 넘어가는 순간, C는 direct로 A로 가는 길을 선택할 것이다. 그제서야 각 table의 update가 멈춘다

• 결국, converge가 되긴 하는데, too much time이 소요되고 too much route information이 교환된다.
  waste of network resource

문제의 원인

• B가 C에게 table을 받을 때, A로 가는 그 값이 자신을 통해서 간다는 것을 모른다
• 결국, distance vector는 오로지 다음 node만 기록하고, 전체 경로를 기록하지 않기 때문에 이러한 문제가 생긴다.

Solution

split horizon

• C가 B에게 table을 보낼 때, B를 거쳐서 가는 route는 포함하지 않는다.
  (걔가 next stop인 entry는 빼고 준다)

split horizon with poison reverse

• C가 B에게 table을 보낼 때, B를 거쳐서 가는 route를 주긴 하는데, 그 값을 infinity로 해서 준다.
• 하지만 이것도 한계가 있다
  • 둘 사이에서만 가능하고, 3-hop loop에서는 해결책이 되지 못한다(왜??)
    

path vector routing

• 모든 경로를 다 기록한다
• loop can be detected as soon as the table is received
• used in BGP
  

---

RIP

• Routing Information Protocol

• distance vector routing을 기반으로 널리 사용되는 routing protocol이다

• Each router sends advertisement messages

  • Every 30 seconds or if routing table is updated

  

---

Link-state routing

• network에 있는 모든 노드에게 나의 link state 정보를 보낸다
  • Link state packet (LSP)

• Link state packet
  • ID of the sender
  • (ID, distance) for each direct neighbor of the sender
  • Sequence number (to find out if it is the newest info)

• 한 노드가 다른 노드로부터 LSP를 받으면, Dijkstra algorithm을 이용해서 shortest path를 찾는다

---

Dijkstra algorithm

• input : A graph with edge weights (distance)
• output : Shortest paths from one node to all others
• initially C = {source}
• Loop N-1 times
  • Find node M that is NOT included in C
    and is the closest to the source node
  • Include M in C

1. D(x)는 distance, P(x)는 parent를 나타낸다
   step0 (direct 연결)에서 가장 작은 값을 child로 붙여서
   step1을 update한다
   
   만약 가장 작은 게 여러개라면 아무거나 선택해도 된다.
   그 경우, path는 달라질 수 있지만, 값은 동일하게 나온다

2. 이런 방식으로 이전 step에서 가장 작은 값을 chil로 붙여서 모든 노드를 다 붙이면 마무리한다
   

---

• Packet forwarding
  

• Link state packet forwarding에서는
  network 상의 모든 노드에게 LSP를 보낸다
  (distance vector에서는 direct neighbor에게만 보냈다)

• Network-wide flooding

Flooding

• A가 전체에게 LSP를 보낸다

• B가 A의 LSP를 받는다

• B는 A의 LSP의 sequence number를 체크한다

  • 만약 그게 가장 최신이면,
    B가 자신의 table을 update하고,
    A를 제외한 모두에게 LSP를 재전송한다
  • 최신이 아니면,
    discard the LSP

---

OSPF

• Open shortest path first

• A routing protocol based on link state routing

• Each router sends Link State Advertisement(LSA) packets

  • periodically or
  • on updates

• LSA packet format
  

---

Summary

• Link state
  가까운 애에 대한 정보를 멀리까지 보낸다
  • Information exchanged : (neighbor ID, distance to neighbor)
  • Information sent to : all nodes in the network
  • protocol : OSPF

• Distance vector
  내 모든 정보를 가까운 애들한테만 보낸다
  • Information exchanged : (destination, distance to destination)
  • Information sent to : direct neighbors
  • protocol : RIP