8. Layer3 : Routing

Routing Control Plane

• Router내의 Data / Control Plane
• 동작 성격 (Data forwarding / routing)에 따라 기능이 나뉘어진다

Data plane

• IP header 분석
• Datagram Forwarding
• Fragmentation (MTU - Maximum Transport Unit)

Control plane

• Routing algorithm
• ICMP (Internet Control Message Protocol)

 

Routing Algorithm

 

Routing의 forwarding Table == Routing Table

• 입력받은 Datagram에 대한 출력 port를 정하기 위해 각 Router가 보유한 표
• 어디로 Datagram을 보내야하는지 적혀있는 table

Routing algorithm

• Routing table을 만들기 위한 각 Router의 동작
• Decentralized

Forwarding Table에 들어있는 내용은 아래와 같다

• Source Node → Edge Network를 통해 들어온 Datagram → Edge Gateway에서 어디로 보낼지 묻는다 "어디 서버로 가?" → Destination IP로부터 라우터를 통해서 Edge Gateway에 붙은 라우터에게 어디로 가야될지 알려준다 (Backward)
• Control Plane에 의해 Forwarding Table 생성 → Data plane에서는 Forwarding Table을 이용해서 동작
• 아래와 같이 Packet의 Header정보를 가지고 Forwarding Table에 값을 넣어서 Output link를 구해서 맞는 다음 Router로 보낸다

Routing Algorithm의 최종목적

• Source Router → Destination Router 까지 최적의 route로 가는 것을 목표로 한다

 

Background (배경지식)

• Routing algorithm은 graph theory를 기본적으로 활용

Graph G = (N, E)

• N : node들의 집합 (router)
• E : Edge들의 집합 (router간 연결)
• Weight (Cost) = c (x, y)
• U → W로 가기위한 최적(최소)의 경로찾기 : Dijkstra Algorithm

 

Least Cost Path

• 총 Cost가 최소인 경로
• 트래픽이라는 것이 너무 가변적이라 현실적으로 적용이 어렵다
• u - z
• 실제 네트워크상 모든 경우에 대해 경로를 구할 수 가 없으므로, 각각의 router에서 자신의 주변 라우터랑만 비교한다 (Decentralized)

Shortest Path

• Cost를 고려하지 않고 가장짧은 Path
• 만약 Cost가 모두 동일하면 shortes path가 결정됨

 

Routing 알고리즘 종류

Global routing algorithm

• Node가 모든 link에 대한 정보를 가지는 방법이다
• complete / global knoweldge about network
• connectivity, link에 대한 정보
• Link-State(LS) algorithm

Decentralized routing algorithm

• Iterative, distributed manner
• Node가 주로 자신과 연결된 Link에 대한 정보만을 가지고 단계적으로 동작하는 방법이다
• Distance-Vector(DV) algorithm

Static routing algorithm

• routing table이 시간에 따라 변하지 않거나 거의 변하지 않는 경우
• (주로 사람의 조작에 의해서만 변한다)
• 회사 내부 망 등

Dynamic routing algorithm

• Traffic load 및 topology 변화에 의해 자동으로 routing table이 변하는 방법
  • topology : "토폴로지 (망구성방식)는 컴퓨터 네트워크의 요소들(링크, 노드 등)을 물리적으로 연결해 놓은 것, 또는 그 연결 방식을 말한다"
  • 트래픽의 변화는 너무 변칙적이라서 영향이 적고, topology변화에 맞춰서 변하는 편이다
• 잦은 테이블 변경으로 오류가 발생할 수 있다
  • oscillation : 핑퐁으로, a → b, b → a로 서로 절로 가는것이 낫다고 보낼수 있다
  • routing loop : 특정 구간에서 계속 돌고있는 경우로, routing 테이블이 잘못 만들어진 경우 발생

 

Fixed Routing (Static Routing)

Permanent route - 고정으로 routing 규칙을 지정

• IP address 특정 대역 등에 대해 out-port 지정
• 회사내에서 IP별로 특정 건물로 보낸다거나 할수 있다

활용시점

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

특징

• 간단하지만 Flexibility가 적고, 수고가 많이든다
• Network failure, congestion등의 Dynamic한 상황에 취약하다 (사람이 직접 해결해야한다)

 

Flooding

모든 neighbor들에게 Packet을 무조건 뿌린다

• 궁극적으로 destination은 multiple copy 형태로 수신한다
• Sequence Number를 통해서 duplication을 방지할 수 있다

특징

• 단순, 무식한 방법이다
• Routing protocol이나 Table등이 필요가 없으므로, Control plane관점에서 매우 Simple하다
• 네트워크 관점에서 Traffic load가 불필요하게 너무 크고, 재전송에 대한 제어가 필요하다
• 작은 네트워크 (서브 네트워크)에서는 사용이 가능하나, Global 인터넷에서는 사용하기 어렵다

 

Link State Routing

Topology 및 모든 Link Cost를 파악하고 Routing Table을 생성한다

• 즉 그래프 상 모든 노드들이 다른 노드 및 간선에 대한 정보를 가지고 있는 것
• 모든 Node가 동일한 Routing 정보를 공유할 수 있다
• 각자의 Identity와 Link별 Cost 정보를 neighbor Node에게 전달

Dijkstra Algoritm을 이용하여 Least Cost Path를 Iterative(반복적으로)하게 파악한다

Routing path를 고려해서 Destination 별로 out-port를 지정

 

Oscillation 문제점

Congestion - Senstive Routing 과정에서의 Oscillation 발생

• Link cost의 기준을 Traffic load로 가정하면 Traffic의 상태가 변함에 따라, Routing 경로가 안정적이지 못하고 왔다갔다 할수 있다

 

Distance Vector Routing

Link State (LS) routing과는 다르게 Asynchronous / Distributed 하다

Asynchronous - It does not require that all of its nodes operate in the lock step with each other

(모든 노드가 작동시 서로 잠금 상태이길 요구하지는 않는다, 즉 비동기적 접근)

• Neighbor node끼리만 정보를 주고받으면서 Routing을 계산
• 더이상 neighbor node끼리 정보를 주고 받을 일이 없을 때 까지 iterative하게 정보 교환 & 계산을 반복
• 각 node가 알아서 인접 노드만 확인해서 정보 교환을 하고 계산을 수행
  (LS는 각 노드가 모든 노드에 대해 알고 있었다)
• 자신이 가진 모든 노드에 대한 정보와, 자신의 인접 노드에 대한 정보를 가지고 계산, 이후 다른 노드와 Broadcasting을 통해 Distance Vector값만 받아옴

 

Broadcasting

송신 호스트가 전송한 데이터가 네트워크에 연결된 모든 호스트에 전송되는 방식

 

Bellan-Ford Equation 활용

- Dx(y) = MINv(C(x,v) + Dv(y))

여기서 v는 x의 인접 노드이다

 

x → y (2) / x → z (7) / y → z (1) 인 그래프에서 각 노드에서의 테이블 형성과정

각 노드는 자신의 인접 노드에 대한 정보만을 갖는다, 다른 노드에서 다른 노드로의 비용은 고려하지 않는다

각 노드가 인접 노드에 대해 계산하고 Distance Vector를 전달해주고, 해당 정보를 가지고 자신의 주변 노드에 대한 비용을 수정해서 Broadcasting 한다

위 작업을 반복하면서 더이상 값의 변화가 없으면 멈 춘다

 

Link cost change 1 - Cost Reduced

T0 : y node detects cost change (4 → 1)

- 변화를 감지한 y노드는 자신의 table을 수정해서 broadcasting한다

T1 : z node receives update (D(z → x) : 5 → 2)

- z노드는 원래 x노드까지의 비용이 5였는데 전달 받은 Distance Vector값을 반영해서 2로 수정한다

T2 : y node receives update (no change)

- y노드는 다시 z노드의 변화를 받지만 table에서 자신의 비용은 수정할게 없다 (x node도 마찬가지)

 

Link cost change 2 - Cost Increased

T0 : y node detects cost change (4 → 60)

- 현재 y노드는 y → x의 비용이 60바뀐걸 보고, z노드에서 준 정보를 보면 (Detect Before) z → x의 비용이 5로 나와있으니 y → z의 비용 1 + z → x의 비용 5 (Detect Before)인 6으로 변경해준다

T1 : z node receives update - D(y → x) : 4 → 6

- z노드는 y노드가 브로드캐스팅 해준 Distance Vector를 보고 기존 D(z → x)의 비용인 z → y → x 를 1 + 6 인 7로 바꿔준다

T2 : y node receives update - D(z → x) : 5 → 7

- y 노드는 y → x : cost 60보다 y → z + D(z → x) : cost 1 + 7의 비용이 더 싸므로 또 cost 8로 D(y → x)를 바꾸게 되고, 결국 50이 될때까지 반복하게 된다

⇒ Link Cost가 특정 값에 도달할 때까지 1씩(여기서는 y→z 비용) 증가하므로 To Much Iterations가 발생한다(오버헤드)

 

Link State vs. Distance Vector

DV

• 인접 노드끼리만 정보를 교환하고, 정보 내용은 모든 Node에 대한 Cost

LS

• 모든 노드끼리 정보를 교환하고, 정보 내용은 인접 Node에 대한 Cost

Message Complexity

• LS는 모든 노드랑 정보교환을 해야 하므로 많은 메시지 전송에 대한 오버헤드가 크다
• DV는 메시지에 모든 노드에 대한 Cost를 담고 있지만 교환은 인접 노드랑 만 하므로 정보교류에 관한 오버헤드가 작다
• DV는 인접 노드의 값의 변화가 크면 클수록 정보교환량이 증가한다

Speed of convergence(모든 라우터에 업데이트 정보가 전달되는 시간)

• DV - 가장 긴 min cost path의 hops의 수에 비례하며, DV가 LS보다 느리다,전체 라우터가 모두 동일한 정보로 수렴하기 까지 많은 시간이 걸리는 단점이 있다
• 업데이트 정보가 이웃 노드에게만 전달되고, loop에 빠져서 전달될 가능성이 있다
• LS - 모든 노드에 대한 경로 정보를 갖고 있으므로 변화가 발생해도 파악하는데 시간이 더 적게 든다

Robustness

• LS는 각자 노드들이 모든 정보를 가지고 계산하는 방식이므로 더 안정적이다

 

Hierarchical Routing

실제 Internet은 sub-network와 gateway router 형태로 계층적으로 네트워크를 형성한다

• Subnet간 packet Routing은 gateway router를 통해서만 이뤄진다

Autonomous System (AS) : 한 기관이 관리하는 router 및 네트워크 모음

• 하나의 서브네트워크에 대한 그룹을 지칭
• 동일한 routing protocol에 의해 밀접하게 동작한다

Intra-AS vs. Inter-AS routing

intra as : AS 내에서 일어나는 routing

inter as : AS 간에 일어나는 routing

 

Routing Information Protocol (RIP) - Intra AS routing

intra-AS routing에 주로 활용되는 routing algorithm

• Distance Vector protocol에 속하며 link cost가 모두 1이다 (Hop Count 용)
• Hop count가 cost metric이다 (max 15, 즉 최대 hop 15개까지만 전달)
• RIP response / advertisement message (30초에 한번 라우팅 정보를 브로드캐스팅 전달)
• 30초마다 RIP 응답메세지(RIP 패킷)를 브로드캐스팅하는데, 이 브로드캐스팅을 위한 IP address로 255.255.255.255로 하여 브로드캐스팅 주소로 사용한다
  • Advertisement / Advertising
  • - 라우터,무선노드 등 장비에서, 장비들 간에 일정주기 또는 필요시에, 자신 및 주변정보(라우팅 갱신정보 등)를 알리는 과정을 말함 

 

RIP Routing Table

• Distance vector 및 Forwarding table을 갖고 있다
• Routing advertisement message를 수신 후 Routing 정보를 갱신한다

180초 이상 routing advertisement message 수신이 없으면 No longer reachable이라 판단한다

• Routing table을 수정하고 advertisement message를 보낸다

RIP Request Message

• (수신을 안주면) 특정 destination에 대한 neighbor's cost를 달라고 요청한다 (UDP, port 520)

 

Open Shortest Path First (OSPF)

RIP의 다음 버전이며, 여러가지 개선된 기능을 갖는다, 따라서 Intra-AS에서 사용되는 프로토콜

• Dijkstra least-cost path algorithm 기반이며, Link State에 대한 flooding을 활용한다
• Complete topological map을 기반으로 모든 subnet에 대한 shortest-path를 구한다
• Link cost metric는 network administrator가 지정하기 나름이며, 모든 link cost를 1로 지정하면 minimum-hop routing이 된다

모든 router에게 link state information을 브로드캐스팅한다

• robustness를 위해 link change가 없어도 최소한 30분에 한번씩 수행한다

 

Border Gateway Protocol (BGP)

Internet에서의 Exterior router protocol

• AS 간 routing을 위한 protocol

역활 3가지

• 인접 AS 간 subnet reachability information 교환 (연결이 되있는지 확인)
• Reachability 정보에 대해 AS 내 라우터에게 전달 (연결 상태)
• subnet에 대한 routing 결정

 

Key Design Issue

• Routing Performance - 라우팅 수행
  • Correctness, Optimality (정확성, 최적성)
• Low Control overhead
  • 너무 잦은 메시지교환으로 오버헤드가 높아지면 안댐
  • Simplicity, Efficiency (간결성, 효율성)
• Robustness, Stability, Fariness(공정성, 서비스를 잘 고루 받아야한다)

 

결론

Routing

• Table이나 Distance Vector, Link State를 기반으로 라우팅을 결정

Forwarding

• forwarding table(= 라우팅 Table)을 기반으로 forwarding을 진행