[컴퓨터망] Unicast Routing

• routing은 network계층에서 이루어짐

IP Packet 전달 방식

• Unicast
  1:1 통신 방식
• Multicast
  1:N 통신 방식
• Broadcast

---

Unicast routing의 아이디어

Unicast routing은 계층적 라우팅을 사용한다.

• Unicast routing의 host는 자신의 packet을 local network의 default router에 전달하게 되기 때문에 forwarding table이 필요 없다. (destination도 마찬가지)
• 때문에 forwarding table은 router들만 알면 된다.

---

Routing Algorithm

• Distance Vector Routing
  • 경로를 결정할 때 통과해야 하는 라우터의 수가 적은 쪽으로 결정
  • Bellman-Ford
  • 주기적으로 경로 설정
  • 이웃한 라우터와 routing table 교환
  • RIP, IGRP
• Link State Routing
  • 경로를 결정할 때 bandwidth, delay 등 다양한 요인을 고려하여 cost를 산정 및 경로를 결정
  • Dijkstra
  • 이벤트에 따른 갱신
  • link-state 정보만을 교환 (네트워크 전체 인식)
  • OSPF
    모두 least cost를 설명하기 위해 고안되었지만, least cost의 정의와 least cost tree를 만들기 위한 방법에 차이가 존재한다.
• Path Vector Routing
  • spanning tree
  • BGP

---

Distance-Vector Routing

Characteristics

• 각 router는 1차원 배열의 Distance-Vector를 가진다.
• 각 router는 이웃된 router에게만 자신의 정보를 전달한다.
• 각 router는 30초 간격마다 업데이트 된다.
  • Bellman-Ford 라우팅을 이용해 업데이트 한다.

---

Routing Loop

Distance Vector는 Routing topology를 이해하지 못하기에, Ethernet이 다운되어도 다른 router로부터 update를 받으면 다른 경로가 있다고 판단하여 생기는 문제.

solution

• Split Horizon
  • routing 정보를 수신한 인터페이스로 동일 라우팅 정보를 전송하지 않는 것
• Poisoned Reverse
  • router가 failed link를 감지하면, 자신은 destination까지의 최적 경로의 metric이 infinite(poisoned route) 하다고 전달

---

Link-State Routing

Link-State Packet(LSP)

router에 의해 생성되는 정보를 담은 패킷

• 인접 노드로부터 LSP를 전달받고 해당 LSP가 새것이면 다른 모든 router에 전송(Flooding)
• LSP를 기반으로 LSDB 생성
• LSDB를 기반으로 Dijkstra의 Short Path First(SPF) 알고리즘을 사용하여 Least-cost Tree 및 Forwarding table 생성

---

Link-State Database(LSDB)

• 전체 network를 설명하는 database
• 모든 Area는 같은 LSDB를 가짐

---

Path-Vector Routing

최소 비용을 목표로 하는 것이 아닌, 라우터에 특정한 규칙을 지정 가능

• Spanning-Tree를 이용하여 source-destination path를 결정
• 고유 규칙(policy)를 이용
• Bellman-Ford 방식과 유사하나, min이 아닌 best에 기반
  • 이웃과 path-vector를 교환

---

Unicast Routing Protocol

Unicast routing protocol은 일반적으로 3가지로 분류되며 각각 상단 세 가지 알고리즘에 기반해 forwarding table을 만든다.

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

RIP

RIP Packet

• 매 30초마다 위와 같은 packet을 broadcast
• 기본적으로 UDP에 실어 보냄

RIP message

• Request Message
• Reply Message

RIP Timer

• Periodic Timer: 25~35 seconds
• Timeout Timer: 180 seconds
  • 30초마다 업데이트가 지켜지지 않을 때, 180초를 기다린다
• Garbage Colection Timer: 120 sconds
  • route에 대한 정보가 없거나 metric이 16으로 set 되면, 120초의 유예기간을 둔다.

OSPF

• AS를 여러 area로 나누어 관리
• 각 router는 자신이 소속한 area에 대한 LSDB를 구성

OSPF Packet

5가지 type 존재

• Hello packet
• Database Description Packet
• Link State Request Packet
• Link State Update Packet
• Link State Acknowledgement

Border Gateway Protocol Version 4(BGP4)

서로 다른 AS간의 통신을 가능하게 하는 protocol
즉, 상이한 domain 간에 routing 정보를 교환하는 것이 주된 목적

• eBGP: 서로 다른 AS간 사용(TCP Peering)
• iBGP: AS 내부
• TCP 위에서 운용

Path Attributes

ICANN은 7가지 path attribute를 지정

BGP Message

Internet Structure

AS(Autonomous Systems)

• stub AS: 다른 AS와 하나의 connection
• Multi-homed AS
• Transient AS: 다른 AS와 둘 이상의 connection, allow data traffic

Autonomos System Boundary Router(ASBR)

• 하나 이상의 routing protocol과 연결된 router
• 다른 AS와 routing information 교환

Hierarchical Routing

RIP	OSPF	BGP
intra-AS(IGP)	intra-AS(IGP)	inter-AS(EGP)