9. Layer 3: Routing

course outline

• IP layer에서의 forwarding table 생성을 위한 기법에 대해 이해
• routing algorithm 기본 개념에 대해 이해
• Link stae algorithm, Distance Vector algorithm에 대한 개념 이해 → 주로 data 전달하는 forward table algorithm
• Internet 에서의 routing 매커니즘에 대해 이해

---

Routing Control Plane

• Router 내의 data plane, control plane
• 동작 성격에 따라 (Data forwarding / routing)에 따라 기능이 나뉘어짐

Data plane

• forwarding에 초점이 맞추어져 있다.
• data 관련
• IP header 분석
• Datagram forwarding: input port에 들어온 datagram을 output port 어디로 forwarding 해야할지 결정하는 역할
• Fragmentation (MTU)

Control plane

• routing에 초점이 맞춰져 있다.
• Routing algorithm으로 forwarding table 만든다.
• Routing algorithm
• ICMP
• datagram이 router 사이에서 어떻게 routing 되어야 할지를 결정한다

---

Routing Algorithm

초록색 화살표로 미국 router위치를 받아서 어느 쪽으로 가면 미국 router로 가겠다는 걸 알 수 있음 → forwarding table

router의 forwarding table(== routing table)만들기 위한 알고리즘

• 입력 datagram에 대한 출력 port를 정하기 위해 각 router가 보유한 표

routing algorithm

• routing table을 만들기 위한 각 router의 동작
• 서로 간의 메시지를 주고 받으며 table 생성
• decentralized: 각자 router가 본인 테이블을 본인이 알아서 만든다
• 알고리즘이 centralized routing algorithm와 decentralized routing algorithm가 있다

Centralized Routing은 모든 링크의 상태 정보를 중앙에 보내주면, 중앙에서 처리해서 적절한 Routing을 해주는 방식입니다.
중앙에서 처리해주는 만큼 정확할수는 있으나, 중앙까지 정보전달, 이후 정보 하달 까지의 시간이 생기기 때문에 중앙의 topology가 중요합니다.

distributed Routing은  분산처리 방식입니다. 모든 node들이 자기를 중심으로 해서 인접해있는 node까지 가는 정보를 서로 교환하는 방식입니다.
이렇게 하면 네트워크가 확장되거나, 다른 상황이 생길때 유용합니다. 또한 topology에 크게 영향을 안받는 것 역시 특징입니다.

forwarding table에 들어 있는 내용은 아래와 같다

• source node → edge network를 통해 들어온 datagram → edge gateway에서 어디로 보낼지 묻는다 "어디 서버로 가?" → destination IP로 부터 라우터를 통해서 edge gateway에 붙은 라우터에게 어디로 가야될지 알려준다.(backward)
• control plane 에 의해 forwarding table 생성 → data plane에서는 forwarding table을 이용해서 동작
• 아래와 같이 packet의 헤더 정보를 가지고 forwarding table에 값을 넣어서 output link를 구해서 맞는 다음 router로 보낸다.

Control plane

Control plane (routing algorithm)에 의해 forwarding table 생성

Data plane

data plande 에서는 forwarding table을 이용해서 동작 (데이터를 forwarding table 보고 전달)

• 이 IP address 목적지는 어느 port로 내보내야 궁극적으로 도달하는 가? → forwarding table 이용

Routing 알고리즘의 최종 목적

Source router - destination router간 가장 최적의 경로를 찾는 것

기기와 가장 가까운 router = Source router 가 있다. → 기기와 최적 경로 router가 있다. Source 쪽에 붙은 router는 Source router이다.

Background

• Routing algorithm은 graph theory를 기본적으로 활용한다.
• Graph G = (N, E)
• N: node들의 집합 (router), 통신에서는 link = router
• E: edge들의 집합 (router간 연결)
• Weight: cost = c(x,y), traffic node에서는 delay를 cost로 설정 → 높으면 높을 수록 안좋은 것을 cost로 설정한다.
  • x, y는 Neighbor
• path: (x1, x2, ... , xp)

Routing path

Least cost path

cost의 합이 최소인 경로 → 라우팅할 때 목적은 least cost paht이다.

• c(x1, x2) + c(x2, x3) + ... + c(xp-1, xp)

Shortest path

cost를 고려하지 않고 가장 짧은 path

모든 cost 가 같은 경우의 least cost path

• 네비게이션의 예가 있다.

u - z간 leat cost path를 구하고자 하면

• Centralized routing algorithm
  • 17가지 모든 경우의 수에 대해 해보면 답을 구할 수 있음
  • One locatoin, complete information
• Decentrallized routing algorithm: router들이 하는 방식

---

 

Routing Algorithm 종류

Global vs. Decentralized

Global routing algorithm

• complete / global knowledge about network → 네트워크에 대한 지식을 다 갖고 있는 것
  • connectivity (연결이 되었는가?), link (link의 cost는 얼마인가?)에 대한 정보
• 라우터 전체 정보를 갖고 있다
• Link state (LS) algorithm

Decentralized routing algorithm

• Iterative, distributed manner
• 특정 node가 모든 link에 대한 정보를 완벽하게 가지지 않으며, 주로 자신과 연결된 link에 대한 정보만 가지고 단계적으로 동작
• Distance vector(DV) algorithm

Static vs. Dynamic

static routing algorithms

• Routing table이 시간에 따라 변하지 않거나 거의 변하지 않음
• 주로 사람의 조작에 의해서만 변함
• 회사 내부망 등

Dynamic routing algorithms

• 인터넷에서 많이 사용
• Traffic load 및 topology(연결이 되어 있는 상태, 라우터와 라우터가 어떻게 연결되어있다.) 변화에 의해 자동으로 routing table이 변함
  • topology: 컴퓨터 네트워크의 요소들을 물리적으로 연결해 놓은 것, 또는 그 연결 방식
• 트래픽의 변화는 매우 변척적이라 영향이 적고, topology변화에 맞춰서 변하는 편이다.
• 잘못하면 routing loop, oscillation문제가 발생할 여지가 있음
  • oscilllation: 핑퐁으로 a → b, b → a로 서로 절로 가는 것이 낫다고 보낼 수 있다.
  • routing loop: 특정 구간에서 계속 돌고 있는 경우로, routing 테이블이 잘못 만들어진 경우 발생
• routing forwarding 보다는 덜 자주 일어난다. 너무 자주 일어나면 overhead가 일어남.

---

Static Routing

1. Fixed Routing

permanent rout: 고정으로 routing 규칙을 지정 → 주로 사람이 한다.

• IP address 특정 대역 등에 대해 out port 지정 → 사람이 미리 코딩해 둔다

활용시점

• 전체 관리가 사람에 의해 이루어 질때
• 부분적으로 고정된 규칙을 적용하고 싶을 때

간단하지만 flexibility가 적소 수고가 많이 든다.

Network failure, congestion 등의 dynamic한 상황에 취약함

2. Flooding

 

• 모든 neighbor들에게 packet을 무조건 뿌림 → 모든 연결된 link에 동일한 정보를 뿌린다. routing이 없고 연결된 모든 이웃들한테 뿌리고, 데이터를 받은 이웃도 동일하게 뿌려준다.
• 궁극적으로 destination은 multiple copy 형태로 수신
• sequence number 를 통해 duplication 방지 가능 → 같은 번호 받으면 무시
• 수신되는 링크를 제외한 나머지 링크에게 모두 뿌린다.

특징

• 단순하면서 무식한 방법이다.
• 장점: routing protocol이나 table등이 필요 없으므로, control plane관점에서 simple하다 → 이런 장점으로 data정보 보다 작은 control 정보를 뿌려줄 때 사용
• 단점: traffic load가 불필요하게 너무 크며 재전송에 대한 제어가 필요
• 작은 네트워크 (서브네트워크)에서는 사용이 가능하나, global인터넷에서는 사용하기 어렵다.

---

Dynamic routing

1. link state routing

• topology 및 모든 link cost를 파악하고 routing table 생성 → 글로벌한 routing 알고리즘
• link state broadcast algorithm을 통해 활용
• 각자의 identity와 link 별 cost 정보를 neighbor에게 전달하는 방식으로 작용
• 모든 node 가 동일한 routing정보를 공유할 수 있음 → 모든 node가 forwarding table을 갖고 있는 것과 다름
• Dijkstra's algorithm: least cost path 를 iterative하게 파악 → 이 알고리즘 방법을 사용해서 routing

dijkstra's 알고리즘 
N'에 source 노드만 넣고, source node로부터 이웃 노드만 D(v) 초기화
N'에 없는 노드 중에서 D(v)가 최소인 것을 찾아서 N'에 넣기 → 반복

Dijkstra's algorithm 기본 설정

• node 가 늘어날 수록 D() 값이 줄어든다
• p (이전노드)를 추척하면 path를 찾을 수 있음.
• 순차적으로 node를 넣고 least cost path를 갱신
• forwarding table의 결과는 routing path를 고려하여 destination별로 out port 지정

forwarding table의 결과 노드 u의 forwarding table

단점

• congestion sensitive routing 과정에서의 oscillation(진동)이 발생 할 수 밖에 없음 → link cost를 traffic load로 가정하면 traffic상태에 따라 routing 경로가 안정적이지 못하고 왔다갔다 할 수 있음

2. Distance Vector Routing

• LS routing 과는 다르게 asynchronous /distributed함
• neighbor node 끼리만 정보를 주고 받으면서 routing 계산
• 더 이상 neighbor node 끼리 정보를 주고 받을 일이 없을 때까지 iterative하게 정보 교환 / 계산을 반복
• 각 node가 알아서 정보 교환을 하고 계산 수행
• Bellman ford equation 활용

• 기본적인 routing algorithm 방향은 각 node x는 Dx(y) 값을 특정 초기 값으로 적절히 설정하고 Distance vector Dx에 대해 아래 정보를 통해 지속적으로 update한다.

• Dx: 노드 x의 거리 벡터, 즉 [Dx(y): y in N], 모든 목적지에 대한 x의 비용 추정치
• Dv: x의 각 이웃 v에 대한 각 이웃의 거리 벡터, [Dv(y): y in N]
• Dx(y) = min{c(x,y)+Dx(y), c(x,z)+Dz)y}
• 이웃의 Dv정보만 이용하며 Dv정보 교환을 각 node가 알아서 asynchronous하게 함

이웃 Dv정보만 이용하며 Dv 정보 교환을 각 node가 알아서 asynchronous하게 한다.

• 먼저 각 출발 노드는 이웃에 대해 최소거리를 갱신한다. 그리고 상태가 변경되었으므로 이를 이웃들에게 알린다
• 이웃들에게 알라고 나면 위와 같이 갱신된 상태를 전달받아 자신의 거리 벡터 또한 갱신한다
• 벨만 포트 식을 사용하여 최솟 값을 재계산하고, 변화가 있다면 이를 또 이웃에게 알린다.
• 이웃으로 부터 갱신된 거리 벡터를 전달받고, 자신의 라우팅 엔트리를 재계산하고, 목적지까지 최소비용 경로의 비용 변경값을 알리는 과정은 더 이상 갱신 메세지가 없을 때까지 지속된다. 더 이상 변화가 없다면 알고리즘은 정지 상태가 된다

📡 [Network] 거리 벡터 (Distance Vector) 라우팅 알고리즘이란? 문제와 해결책 (Poisones Reverse)

Link cost change1: cost reduced

• T0: y node detects cost change (4 →1) : 변화를 감지한 y노드는 자신의 table을 수정해서 broadcasting한다.
• T1: x node receives update (Dz(x): 5 → 2) : z 노드는 원래 x 노드까지의 비용이 5 였는데 전달 받은 disance vector값을 반영해서 2로 수정한다.
• T2: y node receives update (no change) : y 노드는 다시 z 노드의 변화를 받지만 table에서 자신의 비용은 수정할 게 없다.
• 줄어든 cost 알려서 정보 update하면 문제 발생하지 않음

Link cost change2: cost increased

 

• T0: y node detects (4 → 60), Dy(x) = Dy(z) + Dz(x) =6)
  • 현재 y 노드는 c(x,y) = 60로 바뀐걸 보고, Dy(x)  = min(c(y,x) + Dx(x) = 60, c(y,z) + Dz(x) = 6)를 비교해서 6으로 변경해준다. (Detect Before: Dy(x) = 5)
• T1: z receives update (Dy(x) : 5 → 7)
  • z노드는 y노드가 broadcating해준 distance vector를 보고 기존 Dz(x)의 비용인 5를 min(c(z,x)=50, c(z,y) + Dy(x) = 7) 7로 바꿔준다
• T2: y node receives update(Dy(x) = 7)
  • y 노드는 c(y,x) = 60 보다 c(y,z) + Dz(x) = 8이 더 싸므로 Dy(x) = 8로 update한다.
• 이후 계속해서 Dy(x)와 Dz(x)를 link cost가 50이 될때까지 1씩 증가한다.
• list cost가 특정 값에 도달할 때까지 1씩 (여기서는 y → x 비용) 증가하므로 to much iteration가 발생하낟. (오버헤드)

Link State vs. Distance Vector

DV: 인접 node끼리만 정보 교환, 정보 내용은 모든 node에 대한 cost
LS: 모든 node와 정보 교환, 정보 내용은 인접 node에 대한 cost

message complexity
⊙ LS는 많은 메시지 전송이 필요, DV는 link cost 변화 빈도에 따라 메시지 전송 횟수 증가 → LS는 n^2의 계산 복잡도이고, DV는 n계산 복잡도. DV가 message 교환 복잡도가 낮다.

Speed of convergence: DV가 convergence 속도가 느림 → 알고리즘이 수렴하는 동안 라우팅 루프가 발생할 수 있다.

Robustness(강인함): LS는 각자 routing을 계산하는 방식이라 더 안정적임.

https://carpediem9911.tistory.com/16

https://tjdahr25.tistory.com/m/56

https://choiblack.tistory.com/33

CH5 : Network Layer Control Plane (1)

Routing Algorithm(라우팅 알고리즘)

 

---

Hierarchical Routing

• 실제 internet은 subnetwork와 gateway router형태로 계층적으로 네트워크 형성
• subnet간 packet routing은 gateway router를 통해서만 이루어짐 → subnet을 들어오거나 나갈 때 gateway 통과

autonomous system (AS): 한 기관이 관리하는 router 및 network 모음

• 동일한 routing protocol에 의해서 밀접하게 동작하는 동일한 routing 알고리즘을 공유하고 있는 집합
• subnet이 모여있는 형태
• AS안에서는 다른 routing 알고리즘을 사용하고 바깥에서는 다른 routing 알고리즘을 사용해서 여러가지 routing 방식을 사용하는데 여기서 안에 있는 router들 끼리는 LS를 사용하고, 글로벌하게 전 세계적으로(큰 AS간에)는 DV를 사용한다.
• 한 AS도 gateway를 통해서 routing을 수행 할 수 있다.
• AS 내의 라우터들은 서로 동일한 라우팅 프로토콜을 사용한다.
• AS 내의 네트워크와 라우터들은 한 조직에 의해 관리된다.

intra vs. inter-AS routing

• intra AS routing: AS 안에서 일어나는 routing
• inter-AS routing: AS간에 일어나는 routing

---

Routing Informaiton Protocol (RIP)

• intra AS routing에 주로 활용되는 routing algorithm →여러 버전이 있는데 v3까지 나왔다.
• distance vector protocol에 속하며, link cost가 모두 1이다. → link cost가 갑자기 증가하는 경우 발생할 문제를 방지하기 위해서
• hop count가 cost metric이다. (max cost: 15) → 15 이상 갈거면 나누거나...(정보제한)

RIP response / advertisement message (30초에 한번 전송): 라우터들끼리 주고 받는 메시지

• advertisement message: 30초에 한번씩 주변에 알리는 메시지 보낸다
• 네트워크 failuer 등의 상황을 알기위해서 30초에 한번씩 주고 받는다.

routing table

D의 routing table

• distance vertor 및 forwarding table을 가지고 있다.
• routing advertisement massage 수신 후 routing 정보 갱신
• 인터넷에 여러 예제 찾아보기

180초 이상 routing advertisement message 수신이 없으면 (주변에 있는 router가 수신이 없으면)

• no longer reachable이라고 판단 (해당 router를 routing table에서 제외)하고 routing table을 수정하고 advertisement를 보냄

RIP request  message

• (수신을 안 주면)특정 destination 에 대한 neighbor's cost를 요청 (UDP, prot 520)
• 질의를 하는 것임. 주변에 destination이나 ip address가 있냐?라고 물어보는 메시지
• response안에 그에 대한 답이 들어있음

---

Open Shortest Path First (OSPF)

• RIP 다음 버전이며, 여러가지 개선된 기능을 가짐 (routing 알고리즘인데, RIP를 자주 사용한다)
• Dijkstra least cost path algorithm기반이며, link state에 대한 flooding 활용
  • complete topological map을 기반으로 모든 subnet에 대한 shortest path 계산
  • link cost는 network administrator(네트워크 관리자)가 지정하기 나름이며, 모든 link cost를 1로 설정하면 miminum hop routing이 된다.
• 모든 router에게 link state information을 broadcasting함
• robustness를 위해서 link change가 없어도 최소한 30분에 한번씩 수행 → RIP에서의 DV보다는 천천히 한다.(30초에 한번씩 수행)

---

Border Gateway Protocol (BGP)

• DV 기반으로 동작
• 인터넷에서 글로벌하게 동작하기 위해서는 BGP라는 것이 AS 간에 routing을 수행하는 것이기에 distribute하게 동작할 수 밖에 없다.
• AS 끝단에 있는 gate: border gateway
• 작년에 KT 네트워크 문제가 생겼었는데 BGP protocol에서 문제가 생겼던것
• internet에서의 exterior router protocol (바깥의 rotuer와 메시지 전달 protocol)
  • AS간 routing을 위한 protocol
• 아래 세가지 역할 수행
  1. 인접 AS간 subnet reachability information 교환
  2. reachability 정보에 대해 AS내 router에게 전달
  3. subnet에 대한 routing 결정

---

Key Design Issue

라우팅 디자인 하는데 고려사항

• Routing performance
  • correctness, optimality
• low control overhead
  • simplicity, efficiency
• robustness, stabiliy(안전성), fairness(공평성) : 라우터의 처리가 공평해야 한다.