1. 홈
  2. 질의 응답
  3. IP 서브넷 간의 갭을 계산하는 방법은 무엇입니까?

IP 서브넷 간의 갭을 계산하는 방법은 무엇입니까?

2017-11-20 18 views
3

입력 IP 서브넷 간의 모든 갭을 계산하는 가장 효율적인 알고리즘은 무엇입니까?IP 서브넷 간의 갭을 계산하는 방법은 무엇입니까?

예

입력

192.168.1.24/29 
192.168.1.40/30 
192.168.1.64/28

출력 예

192.168.1.0/28 <--- auto-created 
192.168.1.16/29 <--- auto-created 
192.168.1.24/29 <--- INPUT 
192.168.1.32/29 <--- auto-created 
192.168.1.40/30 <--- INPUT 
192.168.1.44/30 <--- auto-created 
192.168.1.48/28 <--- auto-created 
192.168.1.64/28 <--- INPUT 
192.168.1.80/28 <--- auto-created 
192.168.1.96/27 <--- auto-created 
192.168.1.128/25 <--- auto-created

지금까지 연구 : 입력 쌍

1 단계 : 192.168.1.0/28, 192.168.1.24/29

IP 서브넷의 숫자 표현 간의 차이점을 계산해 봅시다 :

diff = 3232235800 - 3232235776 = 24

그리고 기본 2 로그를 계산 :

log2 = log2(24) = 4.58

을 그리고 우리는 서브넷의 CIDR과 길이를 계산할 수 있습니다 :

: 

cidr = 32 - 4 = 28 
ipStart = 3232235776 
ipEnd = 3232235776 + 2^4 - 1 = 3232235776 + 15 = 3232235791

그래서 우리가 목록에 추가를 

192.168.1.0/28

그러나 여전히 간격이 있습니다.

diff = 3232235800 - 3232235792 = 8 
log2 = log2(8) = 3 
cidr = 32-3=29 
ipStart = 3232235792 
ipEnd = 3232235799

6,그래서 우리는 두 번째 추가 등

192.168.1.16/29

그리고있다. 그러나 갭을 찾아서 서브넷을 생성하는보다 효율적인 방법이 있습니까?

출처

2017-11-20 Politechniczny

+1

지금까지 해보신 것은 무엇입니까? 결과를 공유하십시오! – MrSmith42

+0

약간의 연구를 통해 제 질문을 편집했습니다. 하지만 내 솔루션은 여전히 ​​너무 복잡합니다. – Politechniczny

+2

"균등"경계에서 시작하지 않는 간격에주의하십시오. 192.168.1.4/30과 192.168.1.24/30 사이의 차이를 고려하십시오. 그것은 16 주소 차이이지만,/28 서브넷은 16으로 나눌 수있는 주소에서 시작해야하기 때문에 그 간격에 "192.168.1.8/28"을 넣을 수는 없습니다. –

답변

0

서브넷이 오름차순으로 나열된다고 가정합니다. 해당 서브넷 마스크의 길이 n과 함께 32 자리 이진 문자열을 고려합니다.

길이가 n 인 s의 접두어를 고려하십시오. 이 접두사가 나타내는 수에 1을 더함으로써 다음 서브넷의 첫 번째 주소 접두어를 얻습니다. 이것을 보시려면 접두어 오른쪽의 모든 것을 1로 채우는 것을 상상해보십시오. 이것은 s의 서브넷에서 가능한 가장 큰 주소이므로 다음 주소는 다음 서브넷에 있어야합니다. 서브넷 마스크의 주소 부분에 1을 더하면 그 부분을 직접 고려할 수 있습니다.

이것은 우리에게 필요한 비트 문자열을 제공하지만 해당 서브넷 마스크의 길이 n을 알려주지 않습니다. 확실히, n은 적어도 우리가 얻은 문자열의 0이 아닌 모든 숫자를 포함 할만큼 길어야합니다. 그렇지 않으면 현재 서브넷에 주소를 포함 할 것임을 알 수 있습니다. 그러나 목록의 다음 서브넷과 겹치지 않게하려면 0을 더 많이 사용해야 할 수도 있습니다. 우리는 새로운 서브넷이 목록의 다음 서브넷과 적어도 하나의 자릿수 (즉, 다음 주소의 마지막 0이 아닌 숫자)와 다르도록 충분한 0을 유지해야합니다.

192.168.1.24/29 
192.168.1.40/30 
192.168.1.64/28

우리는 지금

11000000 10101000 00000001 00011000/29 
11000000 10101000 00000001 00101000/30 
11000000 10101000 00000001 01000000/28

이러한 읽기 우리는 길이의 접두사를 고려해이

11000000 10101000 00000001 00011000/29

의 첫 번째를 고려할 것 : 여기

이 문제에 대한 예제입니다 29 :

,263,358,821,268,303,210

하나 추가

11000000 10101000 00000001 00100

우리의 N해야합니다, 그것은 더 이상 할 필요가 있는지 여부를 확인 우리의 목록에있는 다음 서브넷 고려하기 위해 적어도 27 일 :

이 
11000000 10101000 00000001 00101000/30 
11000000 10101000 00000001 00100 
          ^

우리의 서브넷이 다르다을 다음 서브넷의 오른쪽 끝이 0이 아닌 29 번째 위치의 다음 주소입니다. 따라서, n = 29; 우리는 새로운 서브넷 만든 : 우리가 방금 만든 서브넷에 동일한 절차를 적용하는 경우

11000000 10101000 00000001 00100000/29

을, 우리는 우리의 원래 목록에서 다음 서브넷에 해당하는 우리가 정확히 같은 접두사를 생성 찾을 것입니다. 우리는 이것을 발견 할 수 있으며 여기에 채울 간격이 더 이상 없다는 것을 인식하고 계속 나아갑니다.

11000000 10101000 00000001 01000000/28 
11000000 10101000 00000001 001011
:

는 
11000000 10101000 00000001 001011

다음 서브넷에 비교 : 길이 (30)의 접두사를 추가

11000000 10101000 00000001 001010 


11000000 10101000 00000001 00101000/30

입니다

다음 서브넷입니다

우리는 N 선택해야 = 최소 30, 그래서 우리는 서브넷 수 :

11000000 10101000 00000001 00101100/30

길이 (30)의 접두사를 고려 하나 추가 :

11000000 10101000 00000001 001011 
+        1 
================================= 
11000000 10101000 00000001 001100

다음에 비교 :

11000000 10101000 00000001 01000000/28 
11000000 10101000 00000001 001100

최소 28 개가 있어야합니다.

11000000 10101000 00000001 00110000/28

길이가 28 인 부분 문자열을 고려해 보겠습니다. 원본 목록의 다음 서브넷에 속한 문자열과 동일한 비트 문자열을 얻습니다. 우리는 이것이 우리가 틈을 메웠다는 것을 인식하고 계속 나아 간다.

원본 입력의 마지막 부분을보고 있으므로 입력 할 내용이 없습니다. 완전한.우리의 서브넷 :

11000000 10101000 00000001 00011000/29 
11000000 10101000 00000001 00100000/29 <<< 
11000000 10101000 00000001 00101000/30 
11000000 10101000 00000001 00101100/30 <<< 
11000000 10101000 00000001 00110000/28 <<< 
11000000 10101000 00000001 01000000/28

제공된 입력 이외의 서브넷 범위는 만들지 않습니다. 그렇게하고 싶다면 알고리즘이 최소 서브넷을 목록에 추가하고 목록에 최대 서브넷을 추가 할 수 있습니다. 의 최대 서브넷으로 최소 서브넷 광고 255.255.255.255/32로 0.0.0.0/1와 최소를하자 :

00000000 00000000 00000000 00000000/1 
0 
+1 
=1 
11000000 10101000 00000001 00011000/29 
^
=> n = 2 
=> 10000000 00000000 00000000 00000000/2 <<<<<<<<< 

10000000 00000000 00000000 00000000/2 
10 
+1 
=11 
11000000 10101000 00000001 00011000/29 
     ^
=> n = 9 
=> 11000000 00000000 00000000 00000000/9 <<<<<<<<< 

11000000 00000000 00000000 00000000/9 
11000000 0 
+1 
= 11000000 1 
    11000000 10101000 00000001 00011000/29 
      ^
=> n = 11 
=> 11000000 10000000 00000000 00000000/11 <<<<<<<<< 

11000000 10000000 00000000 00000000/11 
11000000 100 
+1 
= 11000000 101 
    11000000 10101000 00000001 00011000/29 
      ^
=> n = 13 
=> 11000000 10100000 00000000 00000000/13 <<<<<<<<< 

11000000 10100000 00000000 00000000/13 
11000000 10100 
+1 
= 11000000 10101 
    11000000 10101000 00000001 00011000/29 
         ^
=> n = 24 
=> 11000000 10101000 00000000 00000000/24 <<<<<<<<< 

11000000 10101000 00000000 00000000/24 
11000000 10101000 00000000 
+1 
= 11000000 10101000 00000001 
    11000000 10101000 00000001 00011000/29 
           ^
=> n = 28 
=> 11000000 10101000 00000001 00000000/28 <<<<<<<<< 

11000000 10101000 00000001 00000000/28 
11000000 10101000 00000001 0000 
+1 
= 11000000 10101000 00000001 0001 
    11000000 10101000 00000001 00011000/29 
           ^
=> n = 29 
=> 11000000 10101000 00000001 00010000/29 <<<<<<<<<

다음 하나가 우리에게 첫 번째 실제 입력 서브넷을 줄 것이다. 서브넷은 지금 :

00000000 00000000 00000000 00000000/1 <<< 
10000000 00000000 00000000 00000000/2 <<< 
11000000 00000000 00000000 00000000/9 <<< 
11000000 10000000 00000000 00000000/11 <<< 
11000000 10100000 00000000 00000000/13 <<< 
11000000 10101000 00000000 00000000/24 <<< 
11000000 10101000 00000001 00000000/28 <<< 
11000000 10101000 00000001 00010000/29 <<< 

11000000 10101000 00000001 00011000/29 
11000000 10101000 00000001 00100000/29 <<< 
11000000 10101000 00000001 00101000/30 
11000000 10101000 00000001 00101100/30 <<< 
11000000 10101000 00000001 00110000/28 <<< 
11000000 10101000 00000001 01000000/28

우리는 다른 쪽 끝에있는 운동을 반복 할 수 있습니다 :

11000000 10101000 00000001 01000000/28 
11000000 10101000 00000001 0100 
+1 
= 11000000 10101000 00000001 0101 
    11111111 11111111 11111111 11111111 
           ^
=> n = 28 (must include rightmost 1 of s + 1) 
=> 11000000 10101000 00000001 01010000/28 <<<<<<< 

11000000 10101000 00000001 01010000/28 
11000000 10101000 00000001 0101 
+1 
= 11000000 10101000 00000001 0110 
    11111111 11111111 11111111 11111111 
          ^
=> n = 27 
=> 11000000 10101000 00000001 01100000/27 <<<<<<< 

11000000 10101000 00000001 01100000/27 
11000000 10101000 00000001 011 
+1 
= 11000000 10101000 00000001 100 
    11111111 11111111 11111111 11111111 
          ^
=> n = 25 
=> 11000000 10101000 00000001 10000000/25 <<<<<<< 

11000000 10101000 00000001 10000000/25 
11000000 10101000 00000001 1 
+1 
= 11000000 10101000 00000010 0 
    11111111 11111111 11111111 11111111 
         ^
=> n = 23 
=> 11000000 10101000 00000010 00000000/23 <<<<<<<

오히려 목록 밖으로 이상의 모든 조건, 즉 단조로운 얻기 위하여려고하고 있기 때문에, 우리는 알 수있을 때 우리를 그 0의 스트링을 가지면, n을 1 씩 줄이고 맨 왼쪽으로 한 공간을 왼쪽으로 이동합니다. 그래서 우리는 건너 뜁니다 :

01^k는 10^k가되고 n은 k만큼 감소합니다. 그래서 우리는 다시

=> 11000000 10110000 00000000 00000000/12 <<<<<<< 
=> 11000000 11000000 00000000 00000000/10 <<<<<<< 
=> 11000001 00000000 00000000 00000000/8  <<<<<<<

돌아 가기 # 1을 지배하는 추가 건너 뛰 :

=> 11000010 00000000 00000000 00000000/7  <<<<<<< 
=> 11000100 00000000 00000000 00000000/6  <<<<<<< 
=> 11001000 00000000 00000000 00000000/5  <<<<<<< 
=> 11010000 00000000 00000000 00000000/4  <<<<<<<

다음 이동, 우리는 우리의 범위의 끝과 일치하는 서브넷을 얻을, 그래서 우리는 여분의 제로 포함되어야합니다 그것은 별도로 작성 : 우리가 정말 255.255.255.255 서브넷에 대해 신경 경우

=> 11100000 00000000 00000000 00000000/4  <<<<<<<

은 올바른 방법이 하나가 27 개 이상의 서브넷 뭔가를 얻을 때마다 N과 1의 수를 증가하여이를 계속하는 것입니다. 그러나 우리가 격차를 입력 할 경우, 우리는 우리의 현재 상태를 인식 할 수 및 추가 :이 가 255.255.255.255를 포함하는 범위의 나머지 부분을 커버

=> 11110000 00000000 00000000 00000000/4  <<<<<<<<

, 그래서에 대한 해결책이 아니다 증대 된 문제 그 자체이지만 갭을 메우는 원래의 문제는 해결됩니다. 우리의 전체 목록은 다음과 같습니다가 상당하기 때문에 대신에 위에서 설명한대로 두/4 서브넷을 갖는

00000000 00000000 00000000 00000000/1 <<< 
10000000 00000000 00000000 00000000/2 <<< 
11000000 00000000 00000000 00000000/9 <<< 
11000000 10000000 00000000 00000000/11 <<< 
11000000 10100000 00000000 00000000/13 <<< 
11000000 10101000 00000000 00000000/24 <<< 
11000000 10101000 00000001 00000000/28 <<< 
11000000 10101000 00000001 00010000/29 <<< 

11000000 10101000 00000001 00011000/29 
11000000 10101000 00000001 00100000/29 <<< 
11000000 10101000 00000001 00101000/30 
11000000 10101000 00000001 00101100/30 <<< 
11000000 10101000 00000001 00110000/28 <<< 
11000000 10101000 00000001 01000000/28 

11000000 10101000 00000001 01010000/28 <<< 
11000000 10101000 00000001 01100000/27 <<< 
11000000 10101000 00000001 10000000/25 <<< 
11000000 10101000 00000010 00000000/23 <<< 
11000000 10101000 00000100 00000000/22 <<< 
11000000 10101000 00001000 00000000/21 <<< 
11000000 10101000 00010000 00000000/20 <<< 
11000000 10101000 00100000 00000000/19 <<< 
11000000 10101000 01000000 00000000/18 <<< 
11000000 10101000 10000000 00000000/17 <<< 
11000000 10101001 00000000 00000000/16 <<< 
11000000 10101010 00000000 00000000/15 <<< 
11000000 10101100 00000000 00000000/14 <<< 
11000000 10110000 00000000 00000000/12 <<< 
11000000 11000000 00000000 00000000/10 <<< 
11000001 00000000 00000000 00000000/8 <<< 
11000010 00000000 00000000 00000000/7 <<< 
11000100 00000000 00000000 00000000/6 <<< 
11001000 00000000 00000000 00000000/5 <<< 
11010000 00000000 00000000 00000000/4 <<< 
11100000 00000000 00000000 00000000/3 <<<

, 나는이 목록에 단일/3 서브넷을 넣어.

출처

2017-11-20 15:31:49 Patrick87

 관련 문제

  • 관련 문제 없음^_^