김효원, Swindler, coolx 님의 홈페이지

Computer ???

No.

Name.

swindler

Subject.

ROUTING ALGORITHM

Main Cate.

Internet일반

Sub Cate.

Date.

2005-07-06 15:09

Hit.

3352 (211.109.70.164)

File.

ROUTING ALGORITHM
　

1. 개 요
Routing Algorithm은 네트웍을 통한 최적 경로를 결정하기 위한 산출 과정으로서 네트웍을 통해 어떤 정보를 전송시 사용할 경로를 결정함에 있어, Router는 통신을 원하는 Source와 Destination System간의 Distance에 의해 결정한다.

여기서 Distance의 의미는 지역적 거리가 아닌 Source와 Destination간의 통신시 반드시 거쳐야 할 Router의 수인 Hopping Account를 의미한다. 이러한 Routing Algorithm으로 구현되는 Routing Protocol에는 일반적으로 Distance Vector Algorithm의 RIP, IGRP, EIGRP 등이 있으며, Link State Algorithm에는 OSPF, NLSP 등이 있다.

　

2. ROUTING ALGORITHM이 갖춰야할 사항
최적성 : 최적의 Routing을 위해서 Metrics와 Metrics의 가중치를 계산하는 것으로, Routing Protocol에 따라 Metrics의 가중치를 계산하는 방식이 다르다.
단순성 : Routing Algorithm은 가능한 간단하게 만들어야 한다. 이는 한정된 환경(물리적 자원, Memory, CPU 등)에서 운영되어야 하므로 필요한 최소의 Software와 최소의 Utilization Overhead를 갖고 기능적인 효과를 얻어야만 한다.
안정성 : Routing Algorithm은 예측 불가능한 여러가지 환경(Hardware Fault, High Load, 잘못된 실행 등)하에서도 정확하고 안정되게 운영되여야 한다. 이를 위한 네트웍에서의 다양한 실험이 요구된다.
유연성 : Routing Algorithm은 신속히 변화에 대응해야한다. 네트웍에 어떤 변화(Router Down, Up 등)가 생겼을 경우 신속하게 최적 Routes 계산하여 Update 해야 하고, Update된 정보를 신속하게 알려야한다. 만일 신속하게 대처하지 못할 경우 같은 Routing Table이 네트웍상의 Router에 존재하여 Routing Loop이나 네트웍 휴지의 원인이될 수 있다.
　

3. ROUTING ALGORITHM TYPES
1) Routing Table 관리 방법에 따른 구분
- Static Routing Algorithm과 Dynamic Routing Algorithm
Static Routing Algorithm은 관리자가 직접 Static Routing Table Mapping을 설정하는 것을 말하며, 관리자가 변경하지 않을 경우 Table의 내용이 변경되지 않는다. Staic Algorithm은 상대적으로 네트웍 설계가 간단하고 네트웍 Traffic 예측이 쉬운 환경에 적절하다. 그러나 네트웍의 상황이 변하였을 경우 관리자는 다시 적당한 환경을 설정해야만 한다.

Dynamic Routing Algorithm은 네트웍 환경 변화 정보를 능동적으로 분석하여 자신의 Routing Table을 Update하고 새로운 Routing Update Message를 주위에 알린다. 자발적으로 변화에 대처하기 때문에 관리자는 환경을 다시 설정할 필요가 없다.

2) 설정 경로수에 따른 구분
- Single-Path 방식과 Multipath 방식
Routing Protocol에 따라 같은 Destination에 복수의 경로을 설정하여 Traffic을 분산할 수 있다. Routing에 대한 Reliability와 처리율을 제공할 수 있다.

3) Router 구성 방법에 따른 구분
- Flat Routing System과 Hierachical Routing System
Flat Routing System에서는 연결되어 있는 모든 Router들이 동등한 위치에서 서로 정보를 교환하는 구조를 말한다. RIP, IGRP 같은 Distance Vector Algorithm들이 이에 속한다. Hierachical Routing System은 Backbone Router와 NonBackbone Router를 두어 Backbone Router를 통해서 목적지에 도달하는 구조를 말한다.

다시 말하면 Node들을 논리적인 그룹(Domain)으로 묶어, Domain에서 Domain으로 통신시 Domain의 경계을 이루는 Backbone Router를 통하여 통신하는 것을 말한다. 일반적으로 Map에 근거를 두고 설계하는 구조로 OSPF가 이에 속한다.

4) 경로설정 방법에 따른 구분
- Host-Intelligent Algorithm과 Router-Intelligent Algorithm
Source에서 Destination까지 미리 경로가 설정되어 있어서 Router는 단지 Store-and-forward시키는 Routing Algorithm을 Host-Intelligent Algorithm이라 하고, Routing에 대한 정보가 없어 그때그때 계산하면서 경로를 찾는것을 Router-Intelligent라 한다.

5) Routing 범위에 따른 구분
- Intradomain Routing과 Interdomain Routing
단지 Domain내에서만 Routing하는 것과 Domain사이에서 Routing하는 Algorithm이 있다.

6) 환경정보 교환방법에 따른 구분
- Link-State Algorithm과 Distance Vector Algorithm
Link-State Algorithm은 Hopping Account는 물론 Cost, Line Speed, Transmission Delay, 네트웍 Topology등의 다양한 변수를 고려한 신뢰성 있는 Routing Table을 작성 유지하면서, Routing Table환경 정보 변화시 그 변화된 정보만을 관련된 네트웍상의 모든 Router에 알림으로써 Covergence Time과 네트웍 Overhead를 감소시켜 전체적인 네트웍 Performance를 향상시키는 Algorithm을 말하며, Distance-Vector Algorithm은 Smallest Hopping Account(Routing Table 정보) 를 갖고 수시로 환경정보를 자동교환 하는데, 환경정보 교환시 Routing Table의 전체 내용을 네트웍상의 모든 Router로 전송하므로 Covergence Time과 네트웍 Overhead를 증가 시킨다.

　

4. METRICS
Routing Table에는 Switching Software가 최적의 Routing을 위한 정보가 있다. 이러한 정보들을 Metrics라하는데 Routing Algorithm에 따라 여러가지 Metircs을 갖고 있다. 가장 일반적인 Metrics는 다음과 같다.

Path length : 가장 일반적인 Routing Metic로 Hop Count라고도 한다. 각 네트웍에 Cost를 부여하고 Source에서 Destination까지의 Cost의 총합을 말한다.
Reliability : 각 네트웍 연결 상태에 있어서 얼마만큼의 신용도(일반적으로 bit-error율)를 유지하느냐를 수치로 표현한 것을 말한다.
Delay : 하나의 Packet이 Internetwork을 통해서 Source에서 Destination까지 가는데 걸리는 시간을 말하며, 매질의 Bandwidth, 실제거리, Port Queue, 네트웍 Congestion등 여러 요인에 의해 결정된다.
Banwidth : 연결된 네트웍 구간에서 사용 가능한 Traffic 양을 말한다.
Load : 네트웍 자원의 Busy여부를 말한다. CPU Utilization을포함해서 초당 Packet처리율 등 다양한 방법에 의해서 계산한다.
　

5. ROUTING
Routing Algorithm을 이용하여 Routing을 하기 위해서는 먼저 Routing Table을 작성하여 유지하고, 수신한 Packet에 포함된 정보와 Routing Table을 참조하여 최적의 Next Hop을 판단한 후 전송한다.

[바로가기 링크] : http://coolx.net/cboard/computer/63


[Modify] [Delete]		[Reply] [List]