최장 프리픽스 경로 선택
80분 안팎
학습 목표
목적지와 라우팅 표를 입력받아 최장 일치 경로와 다음 홉을 출력합니다.
개념
학교 서버로 가는 출구를 고릅니다
학생 단말에서 10.20.30.11로 보내는 패킷은 목적지 주소를 기준으로 경로를 선택합니다. 같은 표에 10.20.0.0/16, 10.20.30.0/24, 기본 경로가 있으면 여러 행이 동시에 일치합니다. 행을 위에서부터 읽고 처음 맞는 것을 고르는 방식은 표의 정렬 상태에 따라 결과를 바꾸므로 적절하지 않습니다. 이번 목표는 모든 후보를 찾고 가장 긴 프리픽스를 선택해 그 경로와 다음 홉을 출력하는 것입니다.
주소가 아니라 대역을 비교합니다
/24는 앞의 24비트가 같아야 한다는 조건입니다. 10.20.30.11과 10.20.30.200은 10.20.30.0/24에 속하지만 10.20.31.0은 속하지 않습니다. 문자열 startswith로 비교하면 점의 경계와 이진 마스크를 잘못 다루기 쉽습니다. Python 표준 라이브러리 ipaddress의 IPv4Address와 IPv4Network를 사용하면 목적지 포함 여부를 비트 조건으로 계산할 수 있습니다. 네트워크 주소에 호스트 비트가 들어간 입력은 이번 계약에서 오류로 거부합니다.
최장 일치를 단계별로 계산합니다
먼저 목적지를 IPv4Address로 변환합니다. 각 행의 CIDR을 IPv4Network로 만들고 목적지가 그 대역에 포함되는지 검사합니다. 포함된 후보 중 prefixlen이 큰 행을 남깁니다. /32는 한 주소만 나타내므로 /24보다 구체적이며 /0은 모든 IPv4 주소를 포함합니다. 기본 경로는 별도 마법이 아니라 가장 넓은 후보입니다. 목적지에 맞는 더 구체적인 행이 없다면 기본 경로가 선택됩니다.
metric은 프리픽스를 대신하지 않습니다
실습 모형은 프리픽스 길이를 먼저 비교하고 동일 길이에서는 metric이 낮은 행을 선택합니다. metric 900인 /24와 metric 1인 /0이 모두 맞으면 /24가 우선합니다. 길이와 metric까지 같으면 입력 순서를 유지하는 결정 규칙을 둡니다. 이것은 채점용 단순화이며 실제 Linux의 정책 라우팅, 여러 테이블, 경로 종류와 다중 다음 홉을 모두 구현하지 않습니다. 모형의 출력이 실제 커널 전달을 증명한다고 쓰지 않습니다.
다음 홉과 목적지는 다른 값입니다
출력의 CIDR은 선택된 경로이고 next_hop은 이번 링크에서 패킷을 넘길 상대입니다. 직접 연결 대역에서는 라우터 대신 목적지 단말을 이웃으로 찾으므로 next_hop을 하이픈으로 표현합니다. 다음 홉 주소가 목적지 서버와 같아야 하는 것은 아닙니다. 라우터를 거쳐도 IP 목적지는 서버로 유지되고 Ethernet 목적지가 현재 링크의 다음 홉으로 정해집니다. NAT에 따른 주소 변화는 뒤 모듈에서 별도로 다룹니다.
브라우저 입력 계약을 고정합니다
표준 입력은 JSON 객체이며 destination은 IPv4 문자열, routes는 경로 객체 배열입니다. 각 경로는 cidr, next_hop, metric 세 필드를 가집니다. metric은 0 이상의 정수이고 bool은 정수로 취급하지 않습니다. next_hop은 하이픈 또는 IPv4 주소입니다. 정상 출력은 CIDR과 다음 홉을 공백 하나로 구분한 한 줄이며 후보가 없으면 NO_ROUTE, 입력 오류는 ERROR입니다. 빈 배열은 유효한 표이며 오류가 아니라 경로 없음입니다.
오류를 경로 없음과 분리합니다
잘못된 JSON, IPv6 목적지, 누락 필드, 음수 metric, 호스트 비트가 있는 CIDR은 ERROR로 처리합니다. 아직 일치하는 후보를 찾지 못했다는 이유로 다음 행의 형식 검사를 건너뛰지 않습니다. 표 전체가 유효한지 확인해야 잘못된 운영 입력을 성공처럼 숨기지 않습니다. Traceback은 Python 실행 실패이며 NO_ROUTE라는 정상 판정과 다릅니다. except Exception으로 모든 버그를 덮기보다 예상 입력 오류만 잡습니다.
경계 사례로 알고리즘을 검토합니다
10.20.30.0과 10.20.30.255도 대역 포함 계산에서는 /24에 속합니다. 다만 포함 여부가 단말 주소로 배정 가능한지와 같은 질문은 아닙니다. 테스트는 /32 우선, 기본 경로만 존재, 빈 표, 대역 밖, 동일 길이 metric 비교를 나눕니다. 표 순서를 뒤집어도 서로 다른 프리픽스의 결과가 유지돼야 합니다. 같은 길이와 같은 metric에서만 이번 계약의 입력 순서가 영향을 줍니다.
결과를 실제 망에 적용할 때의 경계
계산기가 10.20.30.0/24를 선택해도 인터페이스가 내려가 있거나 다음 홉의 ARP가 실패하면 패킷은 전달되지 않습니다. 따라서 경로 선택 계산과 연결 확인을 별도 증거로 남깁니다. 이 모듈의 로컬 실습은 앞 모듈 미션 solution을 이어받으며 Linux VM의 ip netns에서만 커널 명령을 실행합니다. 맥에서는 Python 문서 검사를 실행하고 Linux 명령의 출력은 외부 확인 전 비워 둡니다. 실습 환경 안내는 이 첫 레슨을 기준으로 사용합니다.
입력 검사를 구현할 때의 순서
JSON을 읽은 뒤 destination과 routes의 자료형을 먼저 확인합니다. routes의 각 항목이 객체인지 확인하고 cidr과 next_hop이 문자열인지 검사합니다. 기본 경로에 맞는 목적지를 찾았다고 반복문을 종료하면 뒤쪽의 잘못된 행이 누락됩니다. 따라서 후보 수집과 전체 입력 유효성 판정을 한 번의 반복에서 수행하되 출력은 반복이 끝난 뒤 결정합니다. 결정적인 출력 한 줄 외에 디버깅 문장을 stdout에 쓰면 채점 계약이 깨지므로 디버깅은 제거한 뒤 제출합니다.
선택 결과를 말로 설명합니다
동료에게 목적지 10.20.30.11과 /16·/24·/32 후보를 주고 왜 /32가 선택됐는지 설명합니다. “숫자가 커서”가 아니라 목적지의 더 많은 앞 비트를 고정한 대역이므로 더 좁은 범위를 나타낸다고 말합니다. /32가 없어졌을 때 /24로, 그 행도 없어졌을 때 /16으로 내려가는지 확인합니다. 경로 하나가 삭제돼도 바로 NO_ROUTE가 아닐 수 있다는 성질은 이후 응답 경로 결함 실험에서 대체 기본 경로를 제거하는 이유와 연결됩니다.
따라하기
대역 포함을 계산합니다
단말 할당 가능성과 대역 포함은 다른 판정입니다.
import ipaddress
n=ipaddress.IPv4Network('10.20.30.0/24')
for a in ['10.20.30.0','10.20.30.255','10.20.31.0']:
print(a, ipaddress.IPv4Address(a) in n)실행 결과
10.20.30.0 True 10.20.30.255 True 10.20.31.0 False
중첩 후보를 정렬합니다
길이를 먼저, metric을 다음에 비교합니다.
routes=[(0,1,'default'),(24,900,'server'),(16,10,'school')]
print(sorted(routes,key=lambda r:(-r[0],r[1]))[0][2])실행 결과
server
기본 경로의 범위를 봅니다
이 계산은 가상 입력이며 외부 패킷을 전송하지 않습니다.
import ipaddress
print(ipaddress.IPv4Address('203.0.113.8') in ipaddress.IPv4Network('0.0.0.0/0'))실행 결과
True
확인 문제
실습
본문의 JSON 계약대로 최장 일치 경로를 출력합니다. 전체 표를 검사하고 길이 내림차순·metric 오름차순·입력 순서로 선택합니다. 경로 없음은 NO_ROUTE, 입력 오류는 ERROR입니다.
모범 답안
import sys,json,ipaddress
try:
data=json.load(sys.stdin)
if not isinstance(data,dict) or not isinstance(data.get('destination'),str) or not isinstance(data.get('routes'),list): raise ValueError()
dest=ipaddress.IPv4Address(data['destination'])
candidates=[]
for i,row in enumerate(data['routes']):
if not isinstance(row,dict) or not isinstance(row.get('cidr'),str) or not isinstance(row.get('next_hop'),str): raise ValueError()
net=ipaddress.IPv4Network(row['cidr'])
metric=row['metric'];hop=row['next_hop']
if type(metric) is not int or metric<0: raise ValueError()
if hop!='-': ipaddress.IPv4Address(hop)
if dest in net: candidates.append((-net.prefixlen,metric,i,str(net),hop))
if candidates:
best=min(candidates);print(best[3],best[4])
else: print('NO_ROUTE')
except (ValueError,KeyError,TypeError):
print('ERROR')
더 읽기
면접 질문
- 같은 서브넷과 다른 서브넷으로 통신하는 흐름을 설명합니다.