Chapter20 Unicast Routing

• Internet에서의 Unicast routing은 hierarchical routing을 사용해야만 한다.

---

General Idea

• In unicast routing, a packet is routed, hop by hop, from its source to its destination by the help of forwarding tables. The source host needs no forwarding table because it delivers its packet to the default router in its local network.
• The destination host needs no forwarding table either because it receives the packet from its default router in its local network.
• This means that only the routers that glue together the networks in the internet need forwarding tables.

---

Least-Cost Routing

• Weighted graph로 internet이 model되었을 때, 당연히 가장 비용이 적게드는 path를 골라야한다.

---

Routing Algorithms

• Several routing algorithms have been designed. The differences between these methods are in the way they interpret the least cost and the way the create the least-cost tree for each node.

---

Distance-Vector Routing

• Distance-vector(DV) routing은 가장 좋은 길을 찾아준다. In DV routing, the first thing each node creates is its own least-cost tree with the rudimentary information it has about its immediate neighbors.
• The incomplete tress are cxchanged between immediate neighbors to make the trees more and more complete and to represent the whole internet.
• A router continuously tells all of its neighbors what it knows about the whole internet.

Distance vector algorithm

failure가 발생하면 무한루프를 돌게 된다.

• • link cost가 감소한 경우 업데이트가 빠름
    1. t0: y가 link cost 변화를 탐지하고 자신의 DV를 업데이트한 후, 이웃들에게 이를 알림
    2. t1: z가 y로부터 업데이트 정보를 받고, 자신의 테이블을 업데이트. x로의 최소 비용을 업데이트 한 후, 이웃들에게 자신의 DV 보냄
    3. t2: y가 z로부터 업데이트된 정보로를 받고, 자신의 테이블을 업데이트. y의 최소 비용 테이블은 변하지 않았으므로 z에게 메시지를 보내지 않음 => 업데이트 끝!
  • link cost가 증가한 경우는 업데이트가 느림
    • z가 x로 갈 때, y를 통한 경로보다 x로 바로 가는 것이 cheap하다는 것을 깨달을 때까지 44번의 반복이 발생 -> 'count to infinity' 문제
    • poinson reverse를 이용해 문제 해결
• Distance vector: poisoned reverse
  • 만약 Z가 X를 얻기 위해 Y를 통해 간다면:
    • z에서 y 거리를 ∞ 주고 업데이트 하도록 함
  • 즉, 업데이트된 곳 반대를 ∞로 설정해주고 업데이트하면 빠름
  • poisoned reverse가 infinity problem을 대부분 해결하기는 하나, 세 개 이상의 이웃 노드를 포함한 루프인 경우 감지하지 못한다.

---

Link-State Routing

• creating leat-cost tree와 forwarding table을 만드는 routing algorithm은 link-state(LS) routing이다.
• node끼리의 cost가 infinity라면 길이 존재하지 않는다는 뜻이다.

 

---

Unicast Routing Protocols

Unicast Routing Protocol에는 3가지 종류가 있다.

• RIP(Routing Information Protocol), based on the distance-vector algorithm
• OSPF(Open Shortest Path First), based on the link-state algorithm
• BGP(Border Gateway Protocol), based on the path vector algorithm

---

Internet Structure

Internet Structure는 single backbone인 tree-like structure에서 multi backbone structure로 변형되었다.

• Scalability problem과 administrative issue 때문에 Internet에서의 routing은 single protocol로만 이루어질 수 없다.
• Hierarchical routing은 각각의 ISP를 AS(autonomous systme)으로 고려하는 것이다.
• 각각의 AS는 원하는 routing protocol를 실행할 수 있지만, global Internet은 AS를 glue하기 위해서 global protocol을 사용한다.
• 각각의 AS에서 실행되는 routing protocol은 intra-AS routing protocol, intradomain routing protocol, interior gateway protocol(IGP)라고 불리운다.
• Global routing protocol은 inter-AS routing protocol, interdomain routing protocol, exterior gateway protocol(EGP)이라고 불린다.

---

Routing Information Protocol

• Routing Information Protocol(RIP)는 가장 널리 사용되는 intradomain routing protocols로 distance-vector routing algorithm에 기반을 두고 있다.
• RIP는 Xeror Network System(XNS)의 일부분으로 시작하였지만 RIP를 널리 쓰이게 한 것은 유닉스의 Berkeley Software Distribution (BSD) version이다.

---

Open Shortest Path First

• Open Shortest Path First(OSPF)는 intradomain routing protocol로 link-state routing protocol을 기반으로 한다.
• OSPF is an open protocol, which means that the specification is a public document.

---

Border Gateway Protocol

• Border Gateway Protocol version 4 (BGP4)는 Internet에 사용되고 있는 interdomain routing protocol이다.
• BGP4는 path-vector algorithm을 기반으로 한다.