Routing in Switched Data Network

Routing in Packet Switching Network

• 라우팅이 스위치 네트워크를 설계하는데 주요 설계 요소임
• 네트워크를 통해 엔드노드들 간의 루트를 선택하는 것이 라우팅임
• 라우팅 알고리즘이 가져야 하는 요구 조건
  • 정확성
  • 단순성
  • 견고성
  • 안정성
  • 공정성
  • 최적성
  • 효율성

Performance Criteria

• 라우팅 알고리즘 평가 기준
• 루트를 선택하기 위해 사용됨
• Minimum hop : 가장 간단한 형태
  • hop : 하나의 노드와 다음 노드 사이
  • 거리가 길더라도 hop이 적으면 서비스하는 데 걸리는 시간이 짧다고 봄
• 최소가격 알고리즘(least cost)
• 최소가격알고리즘은 융통성이 있어 minimum hop보다 일반적

Elements of Routing Techniques for Packet Switching Network

성능 평가 기준

• Hop의 수 - 적을수록 좋음
• 비용 - 적을수록 좋음
• 지연 - 적을수록 좋음
• 처리량(단위시간당 전송되는 패킷의 수) - 많을수록 좋음
• 공평성과 최적성 사이에 tradeoff 발생
  • 공평성 높이면 최적성이 떨어짐
• 어떤 라우팅 기술도 오버헤드를 가짐 → 오버헤드를 고려해줘야 함

루트 결정 시간

• Packet(datagram) : 패킷이 도착할 때
• Session(virtual circuit) : 전송하기 전에 회로 설정
• 고정적이거나 동적으로 변함

루트 결정 장소

• 각 노드(분산 시스템) : 복잡하지만 신뢰성이 높음
• 중심 노드(중앙 집중 시스템)
  • 단점 : 성능이 central node에서 결정됨, 중심 노드가 망가지면 전체에 문제가 생김
• 송신지(source)

네트워크 정보 수집

• None : 정보 없이
• Local : 자기 자신이 가지는 정보 노드, 노드에 연결된 링크에 관련된 queue
• Adjacent node : 인접 노드
• Nodes along route :경로에 해당하는 모든 노드
• All node : 모든 노드
  • 가장 정확한 결정을 내릴 수 있음
  • 프로세싱 오버헤드가 많고 모든 정보를 수집하기 위해 네트워크가 바빠질 수 있음

네트워크 정보 업데이트 시간

• 실시간
• 주기적
• 주요 부하 변화
• 새로운 링크가 생기거나 없어졌을 때(Topology change)

비용 결정 관점

• 거리가 멀면 높아짐
• 거리가 같더라도 트래픽 양이 많으면 높아짐

Routing Strategies

Fixed Routing

• 각 송신지와 수신지 쌍 사이에 하나의 영구적인 경로 사용
• 최소비용알고리즘으로 결정됨
• Topology가 변하지 않을 때까지 고정됨
• 트래픽이나 용량에 따라 결정됨
• 장점 : 단순함
• 단점 : 융통성이 부족
  • 네트워크 고장이나 혼잡발생 시 동작하지 않음

    

Flooding

• 패킷은 모든 이웃 노드에서 보내짐
• 목적지에 패킷이 두 개 이상 보내질 수 있음
• 목적지는 이미 받은 패킷인지 아닌지 구별할 수 있어야 함
• 중복해서 들어온 것은 무시해야 함
• 같은 순서번호(고유함)를 가진 것을 받으면 폐기해야 함 
• 패킷의 끊임없는 재전송을 제한해야 함
  • 노드는 재전송된 패킷의 identity를 기억해야 함
  • 패킷은 Hop count를 포함해야 함

    

성질

• 송신지와 수신지 사이의 모든 가능한 경로가 검색됨
• 수신지에 제일 먼저 도착한 패킷은 가장 최적화된 경로로 옴
• 적어도 하나의 경로가 존재하면 목적지 도착 가능
• 긴급한 메시지를 보내는 데 사용
• 직접적 또는 간접적으로 연결된 모든 노드는 방문이 이루어짐
• 장점
  • 라우팅 알고리즘 단순
  • 신뢰성 높음
  • 견고성이 있음 - 군사망에 사용
  • virtual circuit을 set up 하기 위해 사용
• 단점
  • 네트워크 트래픽이 많음 → 망이 바쁨
  • 보안 문제

Random Routing

• 장점 : 단순
  • 정보 없이 상황에 따라 전송
  • 트래픽 양이 많지 않음
• 포워딩하기 위해 하나의 포트를 임의적으로 선정
• 선택은 랜덤 또는 round robin 방식으로 이루어짐
• 네트워크 정보 필요 없음
• 단점 :
  • 정확하지 않음
  • 성능이 좋지 않음
  • 오래 걸리 수 있음
• 랜덤 루트는 최소 비용도 아니고 최소 hop도 아님

Adaptive Routing

• 동적임
• 망에 상황에 따라 시시각각 루트가 변함
• 대부분의 패킷 스위칭 네트워크에 사용
• 네트워크 상태(실패, 혼잡)에 따라 경로 결정이 바뀜
• 네트워크 정보 필요
  • 정확한 정보를 받으면 성능이 좋아지고 나쁜 정보를 받으면 성능이 나빠짐
• 단점 :
  • 복잡
  • 네트워크 정보의 지로가 오버헤드 사이의 tradeoff
  • 너무 빨리 반응하면 oscillation 발생
  • 너무 느리게 반응하면 정보의 신뢰성 없음
• 장점
  • 성능 향상
  • 혼잡 관리에 도움
  • 이러한 장점들은 설계의 완전성과 부하의 속성에 따라 결정됨

Adaptive Routing 전략의 분류

• Information source에 따라 분류
• Local(고립된)
• 전송 버퍼, 수신 버퍼
• 버퍼의 패킷이 가장 적은 쪽으로 전송
• 인접 노드
• 이웃 간의 지연 정보를 수집하여 사용
• Distributed / centralized
• 모든 노드

Isolated Adaptive Routing

• Bias값 더해서 계산

Least Cost Algorithms

• 최소 비용 알고리즘
• 루트를 정하는 알고리즘
• 여러 개의 경로 중 어떤 경로를 선택할지 정하는 알고리즘
• Hop의 수를 최소화
• 각각의 링크의 비용은 1
• 길이가 같더라도 용량이 다르면 비용 다르게
• 용량이 크면 가격이 적음
• 두 노드 사이의 경로의 비용은 거쳐가는 링크의 모든 비용의 합
• 노드와 노드 사이는 양방향으로 연결됨
• 링크는 각 방향에 대해 비용을 다르게 가짐
• 네트워크에는 다양한 source & destination pair를 가짐
• 각각의 source & destination pair 중 최소가격경로를 정하고자 함
• 다익스트라 알고리즘, 벨만포드 알고리즘

  

다익스트라 알고리즘

• 주어진 소스로부터 다른 모든 노드까지의 최소 경로를 찾을 수 있음
• 경로의 길이가 늘어나는 순서대로 경로를 개발함
• 가장 짧은 다음 노드를 추가함
• 모든 노드가 T에 속하면 끝난다.
• 초기화
• 다음노드 선택
• 현재 노드까지의 경로 업데이트 

  

  

벨만포드 알고리즘

• 주어진 노드로부터 최소 경로 결정
• 처음에는 최대 하나의 링크만에 도달 가능한 것만 고려
• 두 번째는 최대 두 개의 링크만에 도달 가능한 것만 고려
• 초기값은 무한대로 

  

비교

• 벨만포드
  • 이웃 노드하고만 정보를 주고받으면 됨
• 다익스트라
  • 모든 노드가 네트워크의 topology를 알고 있어야 함

평가

• 결과는 같음
• 서로 다른 성능 가짐
• 처리 시간 짧을수록 좋음
• 복잡성 낮은 알고리즘
• 결정하기 위해서는 정보 필요
• 정보의 양
• 정보의 양이 많이 필요할수록 복잡성 증가
• 처리 오버헤드 증가
• 구현
• 고정된 topology와 비용을 가지면 같은 결과를 가짐
• 링크 비용이 변하면 비용에 따라 다른 경로를 찾아야 함
• 링크 비용은 트래픽에 의존적이다
• 링크 비용은 동적으로 변함
• Fully connected일 때
• 링크의 수 : N(N-1)/2