[데이터 통신과 네트워킹] Unicast Routing

YJ·2024년 5월 19일

네트워킹 데이터 통신

데이터 통신과 네트워킹

목록 보기

11/14

Introduction

Routing

data packet이 수신측까지 도달하기 위한 route를 설정하는 과정이다.
rotue에 정보를 포함하는 Routing(or Forwarding) table이 만들어진다.
Unicast routing은 hierarchical routing을 사용해야만 수행될 수 있다.
- Internet에서의 수 많은 host와 router
- Routing은 서로 다른 routing algorithm을 사용하여 어러 단계로 수행될 수 있다.

General Idea

송신측과 수신측은 forwarding table이 필요하지 않다.
- 송신측은 default router에 패킷을 전달한다.
- 수신측은 default router로 부터 패킷을 수신한다.
- internet의 router에만 forwarding table이 필요하다.
internet에 그래픽 표현
- internet은 weighted graph로 모델링될 수 있다.
- graph는 cost와 관련된 node들과 edge들의 집합이다.

Least-Cost Routing

Least-Cost Routing

비용이 가장 적은 길을 찾겠다.
수신측 router로 부터 송신측 router까지 best route -> 둘 사이의 가능한 가능한 route에 최소 비용을 찾는다.

Least-Cost pahts

만약 N개의 router가 있다면, router로 부터 다른 router까지 (N-1)개의 가장 적은 비용의 path가 존재한다.
- 이는 N*(N-1)개의 최소 비용의 path가 전체 internet에 필요하다는 것을 의미한다.

Least-Cost Tree

tree에 root로 부터 모든 수신측까지의 가장 적은 비용의 경로
각 노드에 대해 가장 짧은 경로 트리

Routing Algorithm

몇몇의 routing algorithm이 설계되었다.
- Distance-Vector Routing
- Link-State Routing
- Path-Vecotor Routing
이러한 방법들의 차이
- least cost를 해석하는 방법
- 각 노드에 대해 최소 비용 트리를 생성하는 방법

Distance-Vector Routing

Distance-Vector

모든 노드에 대해 least-cost tree를 나타내기 위한 1차원 배열
distance-vector는 neighbor로 부터 정보를 사용해서 만들어진다.

Distance-Vector Routing

각 router가 자신과 각 수신측 사이의 거리를 계산한다.
최적의 경로를 찾기 위해, least-cost tree 를 사용한다.

neighbor 간에 정보 공유

Rotuer는 neighbor에게만 수집된 지식을 보낸다. 그리고 neighbor에게 받은 정보로 부터 테이블을 업데이트한다.
정보 공유는 30초 단위에 일정한 간격으로 이뤄진다.

Bellman-Ford Algorithm

DV routing에서 forwarding table을 만들기 위해 사용된다.
일부 중간 노드(a, b, c)를 통한 node(x)와 node(y) 사이에 최소 비용 (최단 거리)
새로운 노드(z)를 통해 기존 최소 비용인 Dxy 업데이트

node B 예시

각 노드들은 이웃 노드들의 정보를 가지고 distance vector를 만듦
이웃노드에게 전달한다.

B node의 Distance-Vector Routing Algorithm

문제점

Splitting horizon으로 해결할 수 있는 Count to infinity 문제가 있다.
Good news는 빠르게 Bad news는 느리게 퍼진다.
Persistent looping problem, 즉, loop가 영원히 존재한다.

Count to infinity

만약 link가 고장난다면, 모든 다른 router는 즉시 알지 못한다.
무한대에 도달할 떄까지 네트워크를 통해 천천히 전파된다.

Two Node Instability(Two-Node Loop)

Split Horizon

라우터가 학습된 인터페이스에 다시 경로를 advertising하는 것을 막음으로써 routing loop를 방지하는 것
노드B가 X에 도달하는 최적의 경로가 A를 거치는 것을 안다면 이 정보를 A에게 다시 advertise할 필요가 없다.
B에서 X로 가는길을 A한테 얻은 정보를 가지고 만들었다면 이렇게 만든 정보는 A에게 다시 전달하지 마라

Poisoned Reverse

route가 자신에게 연결된 실패한 link를 감지하면, router는 무한대로 할당하고 route를 poison 할 것이다. 그리고 그것을 neighbor에게 adevertising한다.
router가 poisoned route를 advertise한다면, neighbor는 originator에게 poisoned route를 돌려 줄 것이다. 이것을 poisoned reverse라고 부른다.
한 router가 poisoned route를 알려주면 그 neighbor는 다시 poisoned reverse로 다시 되돌려주는 것 (확인해줌)
poisoned route : 거리가 무한대로 설정된 길

Link-State Routing

Link-State Routing

각 router는 network에 모든 router들과 함께 자신의 neighbor에 대한 지식을 공유한다.
router는 flooding을 통해 neighbor에 대한 정보를 전송한다.
정보 공유는 변화가 있을때만 수행된다.
Dijkstra 알고리즘을 사용해서 forwarding table을 만든다.

Link-State

link-state는 link(edge)에 특성들이다.
link cost는 edge에 연관될 수 있다.
link에 특성 : Bandwidth, Delay, Load 등
- 거리만 따지게 되면 Distance vector와 동일함

Least-cost tree와 Forwarding table

least-cost tree를 만들기 위해

각 node는 network에 완전한 맵(각 link에 상태)을 가질필요가 있다.
- network 상태를 알아야한다.
각 rotuter는 다른 것들로 부터 Link State Packet(LSP)를 사용해서 정보를 수집하고 Link State Database (LSDB)를 만든다.

Link-State Packet(LSP)

LSP는 neighbors와 link cost에 대한 list를 포함한다.
LSP는 LSDB를 만들기 위해 flooding과 함께 분배된다.

Link-State Database(LSDB)

LSDB는 모든 router들에 대한 정보를 포함하는 list이다.
Area 내에 모든 rotuer들은 동일한 link-state database를 가진다.
- Area는 LSP flooding을 위한 작은 independent domain이다.

Link-state Routing

각 노드는 Link-State Routing으로서 Dijkstra's Short Path First (SPF) Algorithm으로 동작한다.

Dijkstra's Short Path First (SPF) Algorithm
1) 노드들은 자신을 tree에 root로 설정한다. 그리고 LSDB에 기반해 각 node에 전체 cost을 설정한다.
2) node는 root에서 가장 가까운 node를 선택하고 tree에 추가시킨다.
3) tree에 없는 다른 모든 노드의 비용을 변경해야 한다.
4) node는 2, 3번 과정을 반복한다.

Least-Cost Trees from A

Forwarding table

각 router는 link-state database에 있는 정보로 부터 Forwarindg table을 만든다.
모든 network에 대한 best way (next hop)를 보여준다.

문제점

large link state packet에 flooding과 sending에 의한 Heavy traffic
Flooding에 의해 무한 루프가 만들어질수 있다.
- Time to live(TTL) filed를 사용해서 해결될 수 있다.

Path-Vector Routing

least cost가 우선순위가 아닌 경우도 있다.
- link-state와 distance vector routing 둘다 least-cost 목표를 기반으로 한다.
송신자는 자신의 패킷이 특정 경로를 통과하는 것을 막는다.
- Link-state(LS)와 distance-vector(DV) routing은 송신자로부터 route에 특정 정책을 적용하는 것을 허용하지 않는다.
path-vector(PV) routing은 이러한 요구의 대안이다.

Path-Vector Routing에 기반한 Policy

best route는 policy를 사용하는 송신측에 의해 결정된다.
- 송신측은 path를 제어할 수 있다.
- policy 예 : 방문 노드 수
Internet에서 ISP간에 packet을 route하도록 설계되어 있다.

Spanning Tree

spanning tree는 cycle이 없는 모든 노드들을 연결하는 최소한의 edge 집합으로 정의될 수 있다.
송신측으로부터 수신측으로의 모든 path는 best spanning tree에 의해 결정된다.

Creation of Spanning Tree

Path-Vector는 neighbor로 부터의 정보에 의해 만들어진다.
각 node들은 자신의 path vector를 모든 자신의 neighbor에 보낸다.
각 node들은 그들의 path vector를 업데이트한다.
- 자체 정책(its own policy)를 적용하고 여러 경로 중 가장 적합한 경로를 선택한다.
- +는 경로에 처음에 x를 추가하는 것을 의미한다.

Path Vector와 Updating

Path-Vector Alogorithm

Unicast Routing Protocol

Routing Table = Forwarding Table

3개의 일반적인 Unicast Routing Protocol

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

이런 프로그램들이 router에 동작하며 forwarding table을 만듦
Interiror : 기관 내부에 동작함
Exterior : 기관 외부로 나가기 위함

Internet Structure

Internet은 변해왔다
- single backborn을 가진 tree 구조
  -> 다른 private corportion이 운영하는 multi-backborn 구조

Autonomous System(AS)

AS는 single routing policy를 가지는 매우 큰 network이다.
AS는 대학, 정부, 상업 조직이나 internet service provider (ISP)와 같은 single administrativce entity에 의해 관리되는 IP network들에 연결된 그룹이다.

Autonomous Systems Number (ASN)
-각 AS는 ICANN에 의해 고유한 AS Number(ASN)이 할당된다.

ASN은 16 비트 정수(0~65535) 각 network를 식별한다.
- Public ASN : 1~64511
- Private ASN : 64512~65535

The Allocation of Autonomous System Number

Hierachical Routing

Interiror routing protocol : RIP, OSPF
- intra-AS routing protocol, intra-domain routing procotol, interior gatway proctocol(IGP) 라고 불린다.
Exterior routing protocol : BGP
- global internet은 모든 ASs들을 연결하기 위해 global protocol을 동작한다.
- inter-AS routing protocol, inter-domain routing protocol, exterior gateway protocol(EGP)라고 불린다.

Autonmous Systems (AS)

AS(Autonomous Systems)

Stub AS : AS2, AS3, AS4
- 다른 AS에 하나만 연결된다.
- Data traffic을 시작하거나 종료할 수 있다.
- EX : customer network
Multi-homed AS:
- 다른 AS에 하나 이상이 연결된다.
- Data traffic이 통과하는 것을 허락하지 않는다.
- EX : 하나 이상의 서비스를 사용하는 customer AS
Transient AS : AS1
- 하나 이상의 다른 AS가 연결 되어 traffic이 AS를 통과하는 것을 허락한다.
- EX : provider network, backbone

Autonomous System Boundary Router (ASBR)

하나 이상의 routing protocol이 사용되어 연결된 router
다른 AS의 router와 routing information을 교환한다.
R1, R2, R5, R6, R9는ASBR
다른 것과 경계에 있는 router들
- BGP + 내부에서는 RIP or OSPF 동작

Routing Information Protocol (RIP)

RIP는 Distance-Vector Algorithm을 사용하는 Intra-Domain Routing Protocol이다.
- Unix의 Barkley Software Distribution(BSD) 버전의 UNIX는 RIP를 널리 사용한다.
RIP는 application layer에서 forwarding table을 만든다.
- RIP는 transport protocol로서 User Datagram Protocol (UDP)를 사용한다.
- RIP는 routed background daemon process로서 사용된다.
- 예약된 port number 520는 RIP에 할당된다.

Hop Counte in RIP

Forwarindg Table

Hop Count

RIP router는 다른 network에 도달하는 cost를 알린다.
cost는 hop의 수로 정리한다.
- source host에 network는 hop을 계산하기 위해 카운트하지 않는다.
- 경로에 최대 cost는 15이다.
- RIP는 AS 내부에서만 사용할 수 있다.

Forwarding Table

RIP Message

Request Message
- 처음 설치되었을때 router 또는 time-out entriy
Reply Message
- request message에 지정된 수신측에 대한 정보
- (25~35 초) 주기로 forward table에 변화가 있을때 보낸다.

RIP Message

정보에 변화가 broadcast에 의해 주기적으로 교환된다.
Full routing table이 업데이트로 전달된다.

Example of AS using RIP

세 RIP Timer

Periodic Timer : 25~35초
- 25초에서 35초 사이의 random number 사용하여 regular update message의 전달을 컨트롤하는 것
Timeout Timer(Expiration Timer) : 180초
- 180초 이내에 update가 수신되지 않으면 route는 만료된 것으로 간주되며 hop count는 16으로 설정된다.
Garbage Collection Timer : 120초
- route에 대한 정보가 유효하지 않을때, router는 table에서 route를 즉시 purge하지 않는다.
- router는 16으로 설정된 route를 알리고, 120초의 timer를 설정한다.
- timer가 0에 도달하면 rotuer는 table로부터 purge된다.

Open Shortest Path First (OSPF)

OSPF는 link-state routing protocol에 기반한 intra-domain routing protocol이다
- 모든 router들은 최단 경로를 가지는 newtork topology map인 link state database (LSDB)를 유지한다.
  - route에 cost는 bandwith, delay, load 등을 고려한다.
OSPF network는 area로 나누어서 관리한다.
- network 관리를 간단하게 할 수 있고 newtork traffic을 최적화 할 수 있다.

Metric

각 link는 throughput, round-trip time, reliability 등을 기준으로 가중치를 부여할 수 있다.
- 만약 Hop count가 cost value로 사용되면, forwarding table은 RIP와 같을 것이다.

Forwarding Table

각 router는 shortest-path tree를 찾은 후에 forwardig table을 만들 수 있다.

Area

AS는 area라고 불리는 작은 구역으로 구분된다.
- Area는 LSP flooding을 위한 작은 독립적인 도메인의 역할을 한다.
AS에 있는 area 중 하나는 backborn area로 지정된다.
- area를 연결하는 역할을 한다.

Router Types

Internal router
Area Border Rotuer : area를 연결해주는 router
Backbone Rotuer
Autonomous System Boundary Rotuer (ASBR)
- 하나 이상의 routing protocol이 동작한다.
- routing infomration을 다른 autonomous system과 교환한다.

Link-State Advertisement(LSA)

router는 link state database (LSDB)를 위해 각 link에 state 모든 neighbor들에게 보낸다.
5개의 다른 link state advertisement
Broadcast와 Flooding이 섞여서 사용됨

Type of OSPF Packet

Forming of Neighbor Relations

Exchanging DataBaseDescriptor (DBD's)

OSPF Message: Hello, DD, LSR, LSU, LSAck
1) Hello Packet (type-1)

router가 다른 인접한 router들을 찾을 수 있도록 greeting 형식으로 사용된다.

2) Database Description Packet (type-2)

AS 또는 area에 topology information

해당 area에 대한 link-state database에 내용을 전달한다.

3) Link State Request Packet (type-3)

router는 LSDB에 대한 업데이트된 information을 요청한다.

4) Link State Update Packet (type-4)

LSDB의 information을 업데이트하는데 사용된다.

5) Link State Acknowledgement (type-5)

Link State Update message 확인

OSPF Message: Hello, Database Description

OSPF Message: LS Request, LS Update, LS Ack

Border Gateway Protocol Version 4 (BGP4)

Path-Vector Routing

path 정보를 유지한다.
Forwariding이나 Path Table

Border Gateway Protocol Version 4 (BGP4)

오늘날 Internet에서 사용된다.
path-vecotor에 기반한 유일한 inter-domain routing protocol이다.
Internet에서 정보를 제공한다.
- Internal BGP (iBGP) : inside of AS
- External BGP (eBGP) : between AS

4개의 AS를 가지는 Sample Internet

Transient AS - AS1, Stub AS - AS2, AS3, AS4
- AS에 있는 각 rotuer : intra-domain protocol (RIP or OSPF)
Border rotuer : Intra-domain + iBGP, eBGP
Other router : Intra-domain + iBGP

eBGP의 동작

AS boundary router는 path vector 정보를 보낸다.
- 그들은 BGP 프로세스를 실행합니다.
BGP Peers or BGP Speakers
- eBGP peers는 직접 연결된다.
- 각 BGP에서 logical connection은 session이라 불린다.
eBGP와 iBGP는 port 179번에 TCP service를 사용한다.

자신이 알고있는 정보를 알려줌

iBGP의 동작

AS 안에 있는 router들의 사이에 session
- 만약 완전히 연결된 iBGP session이 있는 경우 (mesh)
eBGP peer로 부터 배운 새로운 경로는 모든 iBGP peer들에게 재분배된다.

전달받은 정보를 전달해줌

eBGP와 iBGP Session의 조합

Finalized BGP Path Tables

Injection of Information into Intra-domain Routing

BGP에 의해 만들어진 path table은 routing packet을 위해 사용될 수 없다.
그것들 Intra-domain forwarding table로 주입되어야한다. (RIP or OSPF)
- path table의 내용은 forwarding table로 끼워넣어야 함

Forwarding Table after Injection from BGP