Routing

Routing in Packet Switching Networks

Packet switching에서 라우팅은 패킷을 출발지에서 목적지로 전달하도록 하는 주요 기능이다. 이를 위해 네트워크를 통해 경로가 설정되어야 하는데 아래와 같은 조건이 포함된다. 

• Correctness(정확) :  올바른 경로를 선택하고 패킷을 정확히 전달
• Simplicity(단순) : 라우팅 과정은 쉽게 구현되고 관리가 가능
• Robustness(강건) : 장애나 과부하가 발생해도 전달이 가능해야 하며 패킷 손실이나 단절 없이 전송
• Stability(안정) : 변화하는 환경에서도 큰 변화 없이 전송가능
• Fairness(공정) : 패킷과 station 간의 교환 우선순위가 공정하게 이뤄져야 한다. 
• Optimality(최적화) : 네트워크 성능을 극대화하도록 설계
• Efficiency(효율) : 라우팅 과정에서 오버헤드를 최소화

라우팅 경로를 설정하는 성능 기준

• minimum-hop : 네트워크를 통해 가정 적은 노드를 거치는 경로 선택(자원의 소비를 최소화)
• least-cost : minimum-hop의 일반화된 형태로, 연결된 station간에 비용이 적게 누적되는 경로를 선택

minimum-hop : 1-3-6(비용은 5+5 = 10)

least-cost : 1-4-5-6(비용은 1+1+2 = 4)

 

Routing Strategies

• Fixed Routing : least-cost기반의 하나의 영구적인 경로를 설정하는 방식이다. 구현이 쉽고 신뢰할 수 있는 환경에서는 안정적이지만  유연성이 부족해서 혼잡이나 장애에 반응하지 못함
• Flooding : network information을 필요로 하지 않는 방식으로 한 노드가 인접한 모든 노드로 전송하는 방식이다. 복사본이 도달할 경우 고유 식별자를 통해서 중복된 패킷은 폐기하는 방식이다. 그래서 모든 가능한 경로를 탐색하기에 자원이 과하게 소모되고 효율성이 떨어지고 보안문제가 존재함. 하지만 장애가 있어도 robust를 보장하기에 긴급상황에 적합
•  Random Routing : Flooding의 높은 트레픽 부하를 줄이는 방식이다. 노드는 들어온 패킷을 하나의 출력 링크로만 재전송하기에 트래픽 부하가 적다. 경로를 선택하는 방식은 랜덤이나 round robin방식으로 선택하고 동일하게 네트워크 정보는 필요 없다. 하지만 경로가 랜덤이기에 효율이 떨어지고 최적의 경로를 보장하지 않는다. 
• Adaptive Routing(적응형) : 가장 많이 쓰이는 방식으로 네트워크 상태에 따라 라우팅을 변경하는 방식이다. network information이 필요한 방식이고 이 정보를 통해서 장애나 혼잡이 발생하면 우회해서 경로를 선택한다. 그렇기에 유연하고 효율이 좋다. 하지만 라우팅 결정이 복잡해서 노드에서 처리해야 할 부담이 증가하고 정보를 자주 교환하면 품질은 좋지만 자원을 소모하기에 성능이 저하된다. 또한 반응 속도가 너무 빠르면 경로에 진동이 발생하고 너무 느려도 상태 정보가 이미 바뀌기에 무용지물이 된다. local, adjacent nodes, all nodes로 분류 가능

 

Internet Routing Protocol

• 패킷 송수신
• 동적 라우팅 지원
• 특수 프로토콜 사용

Autonomous Systems(AS) - 자율 시스템

AS는 하나의 조직에서 네트워크와 라우터가 운영되고 공통라우팅을 통해 내부 통신을 수행함. 장애가 없을 경우 노드간 연결성이 항상 유지됨

 

Interior Router Protocol(IRP)

IRP는 AS내부의 라우터들 간에 라우팅 정보를 전달하는 공유 라우팅 프로토콜, AS 내부에서만 사용

 

Exterior Router Protocol(ERP)

ERP는 다른 AS간의 라우터들 사이에서 라우팅 정보를 전달하기 위한 프로토콜, AS 내부 경로는 관여 x

 

Approaches to Routing(라우팅 접근 방식)

• Distance-vector routing : 인접한 라우터로부터 거리 정보를 받아 라우팅 테이블을 업데이트하는 방식
• Path-vector routing : AS 경로를 기반으로 경로 정보를 제공
• Link-state routing : 전체 topology를 계산하는 방식

Border Gateway Protocol(BGP)

AS 간 라우팅 정보를 교환하기 위한 주요 외부 라우터 프로토콜로 TCP기반으로 안정적이고 효율적임. 3가지 기능이 있음

1. Neighbor acquisition : 인접한 라우터 간의 연결 설정

2. Neighbor reachability : 인접한 라우터들끼리 지속적인 연결 상태 확인

3. Network reachability : 특정 목적지에 대한 경로 확인 및 공유

 

Open Shortest Path First(OSPF) Protocol

TCP/IP 네트워크 내에서 효율적인 내부 라우팅을 제공하기 위해 설계된 프로토콜

 

Dijkstra's Algorithm

출발 노드에서 다른 모든 노드까지의 최단 경로를 찾는 알고리즘, 경로길이가 증가하는 순서대로 경로 생성함

 

Bellman-Ford Algorithm

출발 노드에서 다른 모든 노드까지의 최단 경로를 찾는 알고리즘, 경로는 최대 링크수의 제한을 두어 점차적으로 계산하고 음수 가중치를 가진 그래프에서 동작함

 

Dijkstra와 Bellman-Ford 비교

특징	Dijktra	Bellman-Ford
정보 요구 수준	모든 링크 비용에 대한 정보	이웃 노드와의 정보만 필요
계산 방식	모든 노드와 정보 교환 필요	이웃 노드와의 정보만으로 교환(단계적 갱신)
적용 네트워크 크기	소규모 네트워크에 적합	대규모 네트워크에 적합
네트워크 변경 대처	전체 정보를 다시 수집해야함	적은 정보로 다시 갱신가능