Count-to-infinity problem

distance vector은 목적지와 거리 정보를 교환함으로 각 라우터들이 모든 목적지에 대한 가장 좋은 경로를 알 수 있게 되는 방식이였다.
하지만 문제점이 하나 존재하는데 어떤 네트워크의 변화가 생기었을때 적응하기까지 오래걸릴 수 있다. 이게 바로 Count-to-infinity problem이다.
• A problem in distance vector routing
• Consider the following network. After route table is finalized, the link between A and B breaks

A-C링크가 굉장히 오래걸리어서 사용하지 않는 것을 알 수 있다.

• B does not know how to reach A
• C sends its routing table to B

B의 routing table을 보면 A로 가는 cost가 사라진 것을 확인할 수 있다. 그러다가 C가 자신의 라우팅 테이블을 보내는시점이 오게 될 것이다.

하지만 잘 보면 C에서 A로 가는 길은 굉장히 길기 때문에 실제 원하는 결과와 달라지게 된다. 왜냐하면 C는 A-B가 끊어진 것을 모르기 때문이다.

• B thinks it can reach A via C with distance 3. – However, this path does not exist. (B->C->B->A)

• Now B sends its table to C and C updates its table
– The distance to C has changed.

B가 다시금 C에게 테이블을 보내니 C는 다시금 B를 next entry로 하는 것들에 대해서는 재계산해야만 한다. 그러면 C의 A로 가는 Cost는 4가 된다.

• C sends its table to B
• B updates its table

그러면 다시금 C를 next entry로 생각하는 B에 존재한 table을 수정하게 된다. 계속하다가 C가 A로 전송하는 순간 원래상태로 돌아오겠지만 너무 오랜시간이 걸리는 것을 확인할 수 있다.

• C will eventually change its path to A (direct path), but too much time is needed until C changes its path. : 결국 있는길로 바꾸기는 하겠지만 그렇게 하는데까지 너무나도 많은 시간이 걸린다.
• Also, too much route information is exchanged : route information도 너무 많이 교환된다.
– waste of network resource : 결국 네트워크 자원의 낭비이다.

• Cause of the problem
– When B receives route information from C, B does not know whether the route goes through itself.
– This problem arises because distance vector only records the next node (not the whole path)

이러한 이유가 생기는 이유는 결국 C에 있는 table이 어디를 거치어서 가게되는지를 모른다는 것이다. 만약에 중간 경로에 B를 다시 거친다거나 한다면 count-to-infinity problem이 발생할 수 있다는 것이다. 즉 자기자신에게 돌아온다면 문제가 생긴다는 것이다.

• Solutions to problem
– split horizon
– split horizon with poison reverse
– path vector routing

• Split horizon
– When C sends its route table to B, do not include routes that go through B : 라우터 C가 라우팅 테이블을 B로 전달할때 자신의 라우팅 테이블에서 B를 거치어서 가는 것들은 B에게 전달해주지 않는것이다. 하지만 이것도 C가 B에게 아무정보도 안주기 때문에 이 상태가 유지될 수 있다.

• Split horizon with poison reverse
– When C sends its route table to B, include routes that go
through B, but make their distance to be infinity : B를 거치어서 가는것을 알려는 주는데 그 distance를 infinity로 알려준다.

• Split horizon with poison reverse: limitation
하지만 위의 방식이 반드시 근본적인 문제를 해결할 수 있는 것은 아니다.
– 3-hop loop cannot be avoided

위와 같은 케이스에서는 먹히지 않을 수 있다. 일반통행인 경우

• Path vector routing 방법
– record the whole path (not just the next node) : 전체 경로를 저장하기 즉 다음이라는 부분에 path 전체를 저장한다.
– loop can be detected as soon as the table is received : 중간에 loop이 생기면 바로 문제가 생긴것을 알 수 있다.
– used in BGP (Border Gateway Protocol)

문제점은 데이터가 너무 커진다. 라우팅 테이블 교환시에도 path를 전체 주어야 한다. inter domain(BGP)에서만 사용한다.

Path vector routing

• record distance and the whole path

Routing Information Protocol (RIP)

distance vector을 이용한 라우팅 프로토콜. RIP에서는 advertisement라는 것을 30초마다 전달, 그리고 routing table이 업데이트 되어도 테이블을 전달해준다.
• A widely used routing protocol based on distance vector routing
• Each router sends advertisement messages
– Every 30 seconds, or
– If routing table is updated

• RIPv2 Packet Format

2. Link-state routing

distance vector은 이웃에게 모든 table을 교환
link-state는 나와 나의 이웃까지의 정보를 모든 망의 라우터들에게 전달

• Send my "link state" information to all nodes in the network
– Link state packet (LSP)

• Link state packet
– ID of the sender : 전송자 ID
– (ID, distance) for each direct neighbor of the sender : 이웃의 ID와 distance의 값
– Sequence number (to find out if it is the newest info) : 내가 한 번 볼낼때마다 번호를 올린다. (sequence number을 이용해서 어떤것이 최신인지를 알려준다.)

• Once a node receives LSP from other nodes, it uses the Dijkstra algorithm to find out the shortest paths : 이때 최단거리를 계산하기 위해 다익스트라 알고리즘을 사용한다.

Dijkstra algorithm

• Input
– A graph with edge weights (distance) : 그래프와 엣지 그리고 distance

• Output
– Shortest paths from one node to all others : 어떤 노드에서부터 다른 노드까지 shortest path를 계산

Dijkstra algorithm

Dijkstra algorithm
• Initially C = {source} : 소스가 되는 노드를 집합에 넣고 시작한다.
• Loop N-1 times : N-1번 루프를 돈다.
– Find node M that is not included in C and is the closest to the source node : 아직 C에 포함되지 않으면서 소스 노드에 가장 가까운 노드 M을 C에 넣는다.
– Include M in C

Dijkstra algorithm: example

SPT(Shortest Path Tree)가 집합 C를 의미한다.
A를 일단 포함시키고 A의 이웃들을 확인해서 가장 작은 Distance를 가진 노드를 SPT에 포함한다. 그 다음부터는 D에 대해서는 신경쓰지 않아도 된다.

그 다음 D의 이웃에 대해서 생각해 본다. 이때 A가 D를 거치어서 가면 더 나아지는 것이 있는지 확인해야 한다. 예를 들어 D에서 B를 가는 것은 A에서 B를 가는 것에 비해서 비용이 많이든다. 그래서 업데이트 안해준다.

A가 D에서 C로 가는 것은 4가 된다. 그래서 바꾸어 준다.

B와 C, E 중에서 가장 짧은 것을 그 다음을 고른다. 이것에는 사용자가 특별한 규칙을 설정해 놓았으면 하는데 그게 아니면 그냥 랜덤으로 선택한다.

E는 아에 길이 없었기 때문에 그냥 넣어준다.

이번에는 E를 선택했으니 E에 대해서는 신경쓰지 않아도 된다. 그리고 E의 이웃들에 대해서 확인해 보자. 그리고 업데이트 할 것을 생각해 보자.

E를 거치어서 C로 가는것 그리고 E를 거치어서 F로 가는것을 추가해준다.

그 다음으로 길이기 짧은 것은 B이기 때문에 B를 추가해준다.

그 다음 B의 이웃 C이다. 하지만 거리가 5이기 때문에 바꾸지는 않는다.

그래서 C를 추가해준다.

C를 추가한 다음 F의 값을 구지 바꿀 필요가 없기 때문에 그냥 놔둔다.

Link-state routing

• Each node uses Dijkstra algorithm to find the shortest paths to destinationsIntroduction to Computer Networks

Link-state에서는 각 노드가 SPT를 찾아서 보내준다.

• packet forwarding

결국에는 그냥 목적지로 보내고 노드에 따라 다시 SPT에 맞는 경로로 보낸다.

• Link-state packet forwarding
  • send LSP to all nodes in the network
    • compare: distance vector sends only to direct neighbors
      Link state를 모두 알아야 한다. distance vector은 자기의 이웃에게만 보내준다.
  • Network-wide flooding
    네트워크의 다른 모든 노드들에게 보내주는 것을 Broadcasting이라고도 부르기도 하고 flooding이라고 부르기도 한다.

Flooding

• A sends LSP to all its neighbors
• Suppose node B receives A’s LSP
• B checks the sequence number of A’s LSP : 받은 쪽에서는 이게 최신정보인지 확인한다.
  • If it is the newest,
    • B updates its routing table, resends the LSP to all its neighbors excluding node A : A에서 받은 정보가 최신정보이면 자신의 routing table을 업데이트 한다. B가 업데이트 되었다면 자신의 이웃들에게 A의 정보를 forwarding해주어야 한다.
  • If it is not the newest
    • Discard the LSPIntroduction to Computer Networks

OSPF

link-state routing 알고리즘을 사용하는 프로토콜
• Open Shortest Path First
• A routing protocol based on link state routing
• Each router sends Link State Advertisement (LSA) packets : LSA를 주기적/업데이트 발생시 모든 노드들에게 보내준다.
– Periodically
– 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 exchange: (destination, distance to destination)
– Information sent to: direct neighbors
– Protocol: RI