분할 알고리즘이란 무엇입니까?
1, 미터법 (미터법) 을 선택 기준으로 사용하여 최적 경로를 선택하는 기능.
2. 간단합니다.
3. 견고하고 질기다.
빠른 수렴 능력: 네트워크 변화에 적응하는 수렴 능력.
5, 유연성은 네트워크 오류, 복구 알고리즘을 신속하게 감지 할 수 있습니다.
--
둘째, 라우팅 알고리즘 분류
1, 정적 또는 동적 네트워크 변경, 정적, 정적 간단하지만 적합하지 않습니다. 네트워크 변화에 따라 동적으로 라우팅을 조정합니다. 동정이 결합되다.
2. 단일 경로 또는 다중 경로.
3. 평평하거나 높다.
레벨 없음: 모든 경로가 동일합니다.
계층: 코어와 비코어층이 있는 자치 시스템.
호스트가 라우팅을 결정하거나 라우터가 라우팅을 결정합니다.
호스트 결정 경로 지정: 호스트 결정을 보냅니다.
라우터가 라우팅을 결정합니다. 라우터가 다음에 수행할 작업을 결정합니다.
5. 도메인 내 또는 도메인 간 라우팅.
링크 상태 또는 거리 벡터 알고리즘.
--
셋째, 라우팅 알고리즘의 측정
1, 경로 길이.
2. 신뢰성.
3. 시간을 끌다.
4. 대역폭.
5. 로드합니다.
6. 통신 비용. ] 을 참조하십시오
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
첫째, 거리 벡터 라우팅 거리 벡터 라우팅 알고리즘 (V-D 알고리즘)
장점: 알고리즘은 간단하고 구현하기 쉽습니다.
단점:
경로 정보가 느리게 전파되어 경로 정보가 일치하지 않을 수 있습니다.
경로 정보 교환량이 많아 대규모 네트워크에 적합하지 않다.
무한대에서 무한대까지 카운트하여 수렴성이 떨어진다.
포인트 투 포인트 솔루션:
억압:
분할: 라우팅 R 이 이웃 N 을 통해 대상 D 로 전달되는 트래픽인 경우 R 에서 D 까지의 거리는 무한대입니다.
--
둘째, 링크 상태 라우팅 링크 상태 라우팅 알고리즘 (L-S 알고리즘)
V-D 알고리즘의 단점으로 인해 ARPA 네트워크는 현재 널리 사용되는 알고리즘인 1979 에서 L-S 알고리즘을 채택하기 시작했습니다.
작업 과정은 다음 다섯 단계로 나뉩니다.
1, 이웃을 찾아 네트워크 주소를 알아본다
2, 각 이웃의 지연 또는 비용 측정
3, 패키지 구성 (LSP 링크 상태 패키지), 방금 배운 모든 정보를 알려줍니다
4, 이 패킷을 다른 모든 라우터로 보냅니다
5, 다른 모든 라우터에 대한 최단 경로 계산
여기서 1 및 2 단계의 역할은 1 단계, 즉 각 라우터가 전체 네트워크 토폴로지를 나타내는 무향 그래프를 얻는 것입니다.
이웃을 알아보다
각 지점 간 회선의 모든 인접 노드 라우터에 HELLO 패킷을 보내고 응답 메시지를 수신합니다.
이 작업은 네트워크 구축 초기에 수행되었습니다.
2, 라인 비용 측정
이웃 라우터에 ECHO 패킷을 보내고 반환 패키지를 받은 후 반환 시간을 계산합니다.
왕복 시간을 2 로 나누면 두 점 사이의 지연 시간입니다.
계산 지연 시간은 또한 회로 부하를 고려할지 여부에 따라 달라집니다.
로드를 고려하면 응답 패킷이 대기열에 들어오자마자 타이밍이 시작됩니다.
로드를 고려하지 않으면 ECHO 는 대기열 헤더에 도달할 때 카운트를 시작합니다.
경로 선택은 하중과 관련이 있습니다.
대역폭이 같은 두 개의 회선이 있다면, 당연히 경재선을 경로로 선택한다.
3, 링크 상태 패키지 설정
메시지 형식 (LSP 메시지)
이 메시지에는 각 점과 인접한 모든 점 사이의 지연 시간이 나열됩니다.
메시지 생성 시간:
일정한 시간마다.
선 또는 인접 노드가 변경됩니다.
4, 링크 상태 패키지 배포
플러드는 네트워크의 모든 노드 라우터에 메시지를 보내는 데 사용되므로 트래픽이 여전히 큽니다.
메시지가 수신되면 각 스테이션은 다음을 확인합니다 (일련 번호 기준).
새 일련 번호인 경우 전송된 사이트 외부의 사이트로 전달됩니다.
모든 사이트 전달.
일련 번호가 중복되면 삭제됩니다.
일련 번호가 받은 일련 번호보다 작으면 거부됩니다.
이 알고리즘에는 몇 가지 문제가 있습니다.
(1) 일련 번호 개수 숫자 기간입니다. 초당 32 비트 길이의 메시지를 생성하는 경우 137 년을 사용할 수 있습니다.
(2) 라우터에 장애가 발생하여 작동을 중지하면 원래 일련 번호 트랙을 잃게 됩니다. 복구 시 0 부터 카운트를 시작하며 중복 메시지로 간주되기 때문에 다음 메시지가 거부됩니다.
(3) 일련 번호가 틀렸다. 4 여야 하는데 높은 자리에' 1' 이 있으면 65540 이 된다.
현실을 조성하고 65540 이 거부될 때까지 말이죠.
해결 방법
사용 시간 수 또는 수명 주기 "사용 기간", 사용 기간 값은 1 초 1 또는 라우터를 통과할 때마다 1 입니다. 연령 값이 0 이 되면 메시지는 삭제됩니다. 이로 인해 일부 메시지가 네트워크에서 영구적으로 전파되는 것을 막을 수 있습니다.
향상된 알고리즘:
라우터가 메시지를 수신하면 즉시 전송 대기열에 넣는 대신 동일한 송신 스테이션에서 전송된 메시지와 비교하여 새로 수신된 메시지를 비교하기 위해 보류 영역에서 잠시 기다립니다. 저장된 메시지보다 작거나 같으면 새 메시지는 삭제됩니다. 오류를 방지하기 위해 라우터 간에도 재전송을 위해 응답 메시지가 전송됩니다. 회선이 유휴 상태일 때 유지 영역을 순환하여 전송할 메시지 또는 응답 패키지를 선택합니다.
5, 새로운 경로 계산
Dijkstra 알고리즘을 사용합니다.
각 라우터는 자체 시스템을 소스 시스템으로 사용하여 모든 대상에 대한 최단 경로를 계산합니다.
링크 상태 알고리즘의 이점:
(1) 각 게이트웨이는 동일한 원시 데이터를 사용하여 경로를 독립적으로 계산합니다.
라우터 정보의 일관성
모든 숙기는 하나의 소스 기계에 해당하며, 오류 수정 검사가 쉽고 모든 라우터의 L-S 그래프의 일관성을 보장합니다.
좋은 수렴성
라우터는 로컬에서 경로 작업을 수행하며 서로 영향을 주지 않습니다. 라우터 연결 상태 정보는 한 방향으로만 전달되며 다른 라우터의 라우팅 테이블을 통과하지 않습니다. 그 대신 원래 라우터에 영향을 주어 경로의 수렴을 보장합니다.
(2) 대규모 네트워크에 적용
이 알고리즘은 라우터에 직접 연결된 라우터의 링크 상태만 브로드캐스트하고 메시지에는 인접한 노드만 포함되므로 메시지 크기는 네트워크 크기와 관련이 없습니다.