Network Layer (2)

Network Layer (2)

Routing Algorithm

• Global or decentralized information?
  • global
    • 모든 router는 link cost info를 지녀야 함
    • "link state" algorithms
  • decentralized
    • router는 물리적으로 연결된 이웃과 해당 이웃과의 cost를 알아야 함
    • 연산의 결과에 대해 이웃과 정보 교환을 해야 함
    • "distance vector" algorithms
• Static or Dynamic?
  • static
    • routes가 시간에 따라 느리게 변화
  • dynamic
    • route가 보다 빨리 변경
    • 주기적인 update
    • link cost가 변함에 따라 변경

Link-State: Dijkstra's algorithm

• 모든 node들이 net 상의 link costs를 알고 있음
  • link state broadcast를 통해서!
  • 따라서 모든 node들은 같은 정보를 지니고 있음
• 한 node에서 다른 모든 node로 가는 가장 적은 cost의 path 연산
• 알고리즘 복잡도: n nodes
  • 다른 모든 node들 까지의 거리를 구해야 하므로, O(n^2)
  • 우선순위 큐를 활용하여 O(nlogn) 까지 성능 향상 가능

Distance Vector algorithm

• 각각의 node들은 각각의 이웃과의 cost를 알아야 함
• 시간에 따라 각 node들은 distance vector 추정치를 이웃들에게 전송

• link cost changes:
• node가 local link cost를 감지했을 때
• routing info를 update하고, distance vector 재연산
• DV가 변동되면 이웃에게 알림

Hierarchical routing algorithm

• 여태까지의 routing은 이상적인 case
• 실제로는 그처럼 이상적이지 않음
• 모든 목적지의 정보를 routing table에 저장할 수 없음

• router들을 region에 응집시킴 -> Autonomous Systems
• 같은 AS에 있는 router들은 같은 routing protocol을 따름
  • intra-AS routing protocol
• 다른 AS에 있는 router들은 다른 routing protocol 따름
• Gateway router가 각각의 AS의 입구에 존재
• 해당 AS를 다른 AS와 연결하는 역할

Intra-AS Routing

RIP: Routing Information Protocol

• use distance vector algorithm
• 각각의 link는 1 cost를 의미하며, hops 단위로 계산
• 30초 마다 advertisement를 통해 이웃 간 정보 교환

• 180초 이후에 advertisement 전송 안되면, 해당 이웃/link를 dead 판정
  • 해당 이웃 지나는 route 모두 무효 판정
  • 따라서 새로운 ad를 이웃들에게 보냄

OSPF: Open Shortest Path First

• use link state algorithm(다익스트라 알고리즘)
• 각각의 node에는 모든 cost 비용 존재
• OSPF advertisement는 이웃 당 하나의 entry 나름
  • advertisement는 전제 AS로 퍼짐
• 모든 OSPF 메시지는 악의적 침입을 막기 우해 authenticated
• RIP는 하나의 path만 허용하지만 OSPF에는 같은 cost의 길이 여러 개일 경우, 다수의 paths 허용
• 큰 domain에서는 hierarchical OSPF 사용

Internet inter-AS routing: BGP(Border Gateway Protocol)

• inter-domain routing protocol
• 두 개의 BGP router들이 BGP msg 교환
  • advertising paths to different dest
  • exchanged over semi-permanent TCP connection
• How does entry get in forwarding table?
  • Router가 다른 AS의 prefix임을 인지
    • BGP advertisement를 통해 다른 모든 router들에게 알림
  • 해당 prefix를 위한 router의 output port를 결정
    • BGP route selection을 통해 최적의 inter-AS route 설정
    • OSPF를 사용하여 inter-AS route로 향하는 최적의 intra-AS route를 설정
    • Router가 해당 경로의 prot를 idetify
  • prefix-port entry를 forwarding table에 입력

Why different Intra-, Inter-AS routing ?

• intra-AS: 성능에 초점을 둘 수 있음
• inter-AS: 성능보다 policy에 초점을 맞추어야 함

Broadcast routing

• source로부터 다른 모든 node들에게 패킷 전달
• source packet을 복제하는 것은 비효율적

In-network duplication

• flooding
  • node가 broadcast packet을 받으면 다른 모든 이웃들에게 복사본 전송
  • cycle 생길 위험 있음
• controlled flooding
  • node가 이전에 같은 packet을 broadcast하지 않았다면 해당 packet만 broadcast
  • 이미 broadcast 되었던 packet id를 트랙킹
• spanning tree
  • node들이 여분의 패킷을 전송받을 필요 없음

Spanning Tree

• node들이 spanning tree를 따라 copy를 전송
• 외에도 Shortest path tree, Reverse path forwarding, Steiner tree 등의 구조가 있을 수 있음