RFC 826 정리: Address Resolution Protocol (ARP)

태그:

왜 RFC 826을 정리했나?

RFC 826 글을 읽고 정리했다. 그냥 심심해서 읽고 정리한 것은 아니다. 아마 다른 포스팅에 정리하겠지만, 한 두 달 전부터 네트워크 프로토콜을 직접 구현해보며 시뮬레이션 해볼 수 있는 프로젝트를 진행하고 있다. 아직 많이 부족하지만 한 단계씩 천천히 진행하고 있으며, 이제 ARP를 구현할 차례가 되어 좀 더 ARP에 대해 자세하게 정리된 무언가가 필요하였고 그 중 하나가 RFC 문서였다.

사실 이제는 시간이 많이 지났고 많은 유명한 네트워크 책에서 ARP에 대해 자세히 설명해주는 글도 많지만 가장 먼저 특정 프로토콜이 제안된 문서를 읽어보면서 이 프로토콜이 왜 등장하였는가에 대한 맥락을 느끼고 싶었다. 또한 프로토콜의 패킷이 왜 이렇게 설계되어야했는지에 대한 의도도 엿볼 수 있을 것이라 기대했다. 마지막으로 RFC는 가독성이 좋지 않다 (문서의 양식, 폰트 등). 첫 스텝으로 ARP에 대한 RFC 문서를 정리해봄으로써 RFC 문서를 읽는 연습을 해보고싶었다.

정리는 기본적으로 번역을 기본으로 하되 매끄럽지 않은 부분은 의역을 하였다. 너무 디테일한 부분은 제외하였다.

정리

원문은 여기에서 살펴볼 수 있다.

Abstract

  • 프로토콜 P는 호스트 S가 P의 라우팅 규칙을 통해 Ethernet 패킷을 보낼 때 자신이 패킷을 보내고자 하는 타겟 호스트 T를 결정할 수 있게 한다. 실제로 Ethernet 패킷을 보내기 위해서는 48bit의 Ethernet 주소를 알아야 한다. 프로토콜 P 상에서 호스트의 주소들은 항상 Ethernet 주소 규칙에 맞지 않다. (길이가 다르거나 값이 값이 다르다.)
  • 이 문서에서는 프로토콜 P 상에 존재하는 주소 A를 Ethernet 주소 규약에 맞는 48bit 값으로 바꾸는 테이블을 만들기 위해서 정보를 주고받는데, 이 때 정보를 어떻게 주고 받을지에 대한 프로토콜에 대해서 서술하고자 한다.
  • 이 프로토콜은 다음과 같은 사람들의 논의를 통해 탄생하게 되었다. J. Noel Chiappa, Yogen Dalal, and James E. Kulp 그리고 David Moon이 코멘트를 해주었다.
  • 이 RFC는 프로토콜의 주소(예를 들어 IP 주소) 를 로컬 네트워크 주소(예를 들어 Ethernet 주소)로 변환하는 방법에 대해서 제시하고 있다.

Notes

  • 여기에 제시된 프로토콜은 초창기에 DEC/Intel/Xerox 10Mbit Ethernet을 위해서 디자인되었다. 그리고 다른 타입의 네트워크에서도 사용될 수 있도록 일반화되었다.
  • DOD Internet Protocol은 인터넷을 지칭한다.
  • 이 문서에서 제시된 숫자들은 Ethernet 표준을 따른다. high byte들이 앞으로 나온다. 머신마다 바이트 순서가 다르기 때문에 주의가 필요하다.

The Problem

  • 각 네트워크 레이어 별로 많은 꾸준히 사용될 수 있는 잠재력을 가지고 있는 프로토콜이 현재 존재하고 있다. 예를 들어 고수준에서는 TELNET, SUPDUP과 같은 것이 있으며 저수준에서 byte stream 프로토콜에 해당하는 것들 중에서는 CHAOS, DOD TCP Xreox, BSP와 같은 것들이 있다.
  • 10Mbit Ethernet은 위에서 언급한 다양한 프로토콜이 하나의 케이블에서 공존할 수 있게 만들었다. 이는 Ethernet 헤더만 제대로 명시해주면 가능하다.
  • 그런데 10Mbit Ethernet은 48bit의 주소를 케이블에서 필요로한다. 하지만 현존하는 대부분의 프로토콜 주소는 48bit가 아니며 프로토콜 주소는 Ethernet 주소와 딱히 관계를 가질 필요도 없다. 예를 들어 CHAOS 프로토콜의 주소는 16bit, DOD Internet 주소는 32bit이다.
  • 그렇기 때문에 대부분의 프로토콜은 <프로토콜, 프로토콜 주소>의 쌍과 Ethernet 주소를 항상 함께 다른 호스트로 전달해야한다.

Motivation

  • 10Mbit Ethernet은 시간이 지날수록 중요도가 증가하고 있다. 왜냐하면 점점 더 많은 제조사들이 DEC, Intel 그리고 Xerox에서 만든 표준에 맞춰서 하드웨어를 제작하고 있기 때문이다.
  • 그렇기 때문에 점점 더 많은 소프트웨어들이 이러한 인터페이스를 맞추는 방향으로 설계되고 있다.
  • 이러한 상황에서 우리는 두 가지 옵션에 대해서 생각해볼 수 있다.
  • 첫 번째는, 모든 소프트웨어에서 각자 다양한 프로토콜에 대해서 Ethernet 주소로 변환할 수 있는 만드는 것이다.
  • 두 번째는 모든 소프트웨어에서 다양한 프로토콜 주소를 Ethernet 주소로 변환할 수 있는 표준 소프트웨어를 사용하는 것이다.
  • 이 문서는 두 번째 방법에 설명한, ‘표준’에 대해서 설명한다.

Definitions

  • 다음은 Ethernet 패킷 헤더에 TYPE 필드에 넣을 값을 정의한다.
ether_type$XEROX_PUP,
ether_type$DOD_INTERNET,
ether_type$CHAOS,
  • 그리고 새롭게 하나를 추가한다.
ether_type$ADDRESS_RESOLUTION
  • 그리고 아래에서 이야기할 다음 값들도 정의한다.
ares_op$REQUEST (= 1, high byte transmitted first) and
ares_op$REPLY   (= 2),
ares_hrd$Ethernet (= 1)

Packet Format

  • <프로토콜, 프로토콜 주소>의 쌍을 48bit Ethernet 주소와 매핑시키기 위해서 다음과 같은 패킷 포맷이 필요하다.
Ethernet transmission layer:
	48.bit: target 호스트의 Ethernet 주소
	48.bit: sender 호스트의 Ethernet 주소
	16.bit: Protocol type = ether_type$ADDRESS_RESOLUTION

Ethernet packet data:
	16.bit: (ar$hrd) 하드웨어 주소 공간
  16.bit: (ar$pro) 프로토콜 주소 공간	
	 8.bit: (ar$hln) 하드웨어 주소의 byte 길이
	 8.bit: (ar$pln) 프로토콜 주소의 byte 길이
	16.bit: (ar$op)  opcode (ares_op$REQUEST | ares_op$REPLY)
	nbytes: (ar$sha) 이 패킷의 sender 호스트의 하드웨어 주소, n은 ar$hln 값으로부터 정해진다.
	mbytes: (ar$spa) 이 패킷의 sender 호스트의 프로토콜 주소, m은 ar$pln 값으로부터 정해진다.
	nbytes: (ar$tha) target 호스트의 하드웨어 주소, (만약 알고 있다면 해당 필드에 값이 존재).
	mbytes: (ar$tpa) target 호스트의 프로토콜 주소.	

Packet Generation

  • 패킷이 네트워크 레이어를 타고 내려가면서, 다음으로 전달할 호스트의 프로토콜 주소를 결정해야 한다.
  • 10Mbit Ethernet의 경우 address resolution이 필요하고 이를 위해서는 저수준의 레이어에서 (아마 하드웨어까지 내려가야할 것이다.) Address Resolution 모듈을 통해 <프로토콜, 타겟의 프로토콜 주소> 쌍을 Ethernet 주소로 변환시켜야한다.
  • Address Resolution 모듈에서는 자신이 관리하는 테이블에서 <프로토콜, 타겟의 프로토콜 주소> 쌍을 찾는다.
  • 만약 찾는다면, Ethernet 주소를 해당 요청을 보낸 caller에 다시 전달한다.
  • 만약 찾지 못한다면, caller에게 caller가 보낸 패킷을 다른 곳으로 보낼 것이라는 사실을 알려줄 것이고 (이 것은 고수준의 네트워크 레이어에서 자신이 받은 패킷을 다시 caller로 보낼 것이라는 가정때문이다.), ether_type$ADDRESS_RESOLUTION 타입의 패킷을 생성하고 각각의 필드는 아래와 같은 값들로 채워진다.
    • ar$hrd 필드를 ares_hrd$Ethernet으로 입력한다.
    • ar$pro 필드를 자신이 변환시켜야하는 프로토콜 주소의 프로토콜 타입으로 입력한다.
    • ar$hln은 6으로 입력한다. Ethernet의 주소 길이는 48bit이고 이것의 byte 길이는 6이다.
    • ar$pln은 변환시켜야하는 프로토콜 주소의 길이로 입력한다.
    • ar$op은 ares_op$REQUEST으로 입력한다.
    • ar$sha은 자신의 Ethernet 주소를 입력한다.
    • ar$spa은 자신의 하드웨어 주소를 입력한다.
    • ar$tpa은 자신이 변환하고자하는 프로토콜 주소를 입력한다.
    • ar$tha은 아무 값도 입력하지 않는다. 왜냐하면 이 값은 우리가 이 프로토콜을 통해서 변환시켜야하는 최종 결과값이기 때문이다. 이 값을 하드웨어의 브로드캐스트 주소로 넣어도 된다. 만약 이렇게 구현한다면 자신과 Ethernet 케이블로 연결된 다른 호스트들로 이 요청이 전파될 것이다.

Packet Reception

  • 호스트가 address resolution 패킷을 받았을 때, Ethernet 모듈은 Address Resolution 모듈로 패킷을 전달할 것이고 아래에 서술한 알고리즘을 따를 것이다.
  • ‘아니다’에 해당하는 경우는 알고리즘을 종료하고 패킷을 버리는 과정을 따른다.
?ar$hrd 필드에 하드웨어 타입이 있는가?
'그렇다':
	[추가적으로 ar$hln 값이 존재하는지 체크한다.]
	?자신은 ar$pro에 명시된 프로토콜로 통신하고 있는가?
	'그렇다':
		[추가적으로 ar$pln 값이 존재하는지 체크한다.]
		Merge_flag := false
		만약 <protocol type, sender protocol address> 쌍이 나의 translation 테이블에 존재한다면
		sender의 하드웨어 주소를 자신이 받은 패킷의 값을 기반으로 업데이트한다. 
		만약에 업데이트를 하였다면 Merge_flag를 true로 세팅한다.
		?자신의 프로토콜 주소가 target 프로토콜 주소인가?
		'그렇다':
			만약 Merge_flag가 false이면 <protocol type, sender protocol address, sender hardware address> 쌍을 
			translation table에 추가한다.
			?패킷의 opcode가 ares_op$REQUEST인가?
			'그렇다':
				새 패킷을 만드는데 하드웨어와 프로토콜 필드를 자신의 것과 바꾸고, 
				자신의 하드웨어와 프로토콜 주소를 sender 필드에 넣는다.
				ar$op 필드를 ares_op$REPLY로 입력한다.
				패킷을 자신에게 보낸 하드웨어 주소로 보낸다. 
  • <protocol type, sender protocol address, sender hardware address> 쌍을 자신의 translation 테이블에 먼저 추가한다. 그리고나서 opcode를 확인한다.
  • 위와 같은 과정을 따르는 이유는 이 프로토콜의 통신 방향이 쌍방향이라는 가정때문이다. 만약에 A가 B와 통신할 이유가 있다면 B도 마찬가지로 A와 통신할 이유가 있을 것이다.
  • 그리고 <protocol type, sender protocol address> 쌍에 대한 데이터가 테이블에 존재한다면 자신이 받은 데이터를 최신으로 생각하고 하드웨어 주소를 업데이트 한다.
  • 일반화: ar$hrdar$hln 필드를 통해서 우리는 이 프로토콜이 non-10Mbit Ethernet에서도 사용할 수 있다. 10Mbit Ethernet은 <ar$hrd, ar$hln> 쌍이 <1, 6>이라는 값을 가질 것이고 다른 하드웨어 타입은 이와는 다른 값을 가질 것이다. 하지만 그 값은 마찬가지로 프로토콜 주소와 매핑될 것이고 그 결과 위의 알고리즘이 여전히 동작할 것이다.

Why is it done this way??

  • 주기적으로 브로드캐스팅을 하는 방식은 바람직하지 않다. 대부분 각각의 workstation들이 서로서로의 주소를 필요로하는 경우는 극히 드물다. 대부분의 상황에서는 파일 서버나 bridge와 같은 소수의 workstation 주소만 필요하다.
  • 그렇기 때문에 여기서 제시된 프로토콜은 주기적으로 브로드캐스팅하는 방식이 아니라 자신이 필요로하는 것이 생겼을 때만 동작하기 시작하고 한 머신에 대해서 한번씩만 메세지를 전파한다.
  • 프로토콜의 패킷 포맷 상 한 번의 통신에서 한 개 이상의 주소를 변환시킬 수 없다. 이것은 프로토콜의 단순함을 위해서이다. 만약에 하나의 패킷에서 여러개의 workstation들의 hardware 주소를 결정할 수 있다면 알고리즘이 훨씬 복잡해질 것이다. 그리고 굳이 한 개의 패킷에서 여러 개의 hardware 주소를 결정할 필요도 없다.
  • 이 문서에서 제시한 프로토콜의 패킷 포맷을 따르게 된다면 패킷 버퍼를 재사용할 수 있는 경우가 있다. 만약 응답값에 해당하는 패킷이 생성될 때 이는 자신이 받은 요청 패킷의 길이와 동일할 것이며, 같은 값을 가지는 필드들이 많다.
  • 하드웨어 필드 (ar$hrd)를 명시한 이유는 다음과 같다. 현재 하드웨어 필드에 지원하는 값은 10Mbit Ethernet (ares_hrd$Ethernet = 1) 밖에 없다. 하지만 이 프로토콜을 논의하는 시점에서 이 프로토콜을 Ethernet이 아닌 Packete Radio Network를 위해서 사용할 수 있을 것이라는 것이 논의되고 있으며, 이 때 하드웨어 필드에 1이 아닌 다른 값을 사용할 수 있을 것이다.
  • 이론적으로 길이에 대한 필드들 (ar$hln, ar$pln)은 반복된다. 왜냐하면 프로토콜 주소는 하드웨어 타입 (ar$hrd)과 프로토콜 타입 (ar$pro)에 의해서 결정되기 때문이다. 해당 필드들은 패킷의 일관성을 체크하기 위해서 도입되었고 모니터링과 디버깅을 위한 목적도 있다.
  • opcode에 대해서는 이 프로토콜을 고안한 시점에서는 단순히 ‘요청’과 ‘응답’이라는 두 가지 타입만 있으면 충분했고 그래서 16bit를 opcode를 위해서 할당하는 것은 너무 과도한 설계라고 생각했다. 단순한 플래그정도면 충분하다.
  • sender의 하드웨어 주소와 프로토콜 주소는 반드시 필요하다. 이 쌍이 translation table에 기록된다.
  • 요청 패킷에 target의 프로토콜 주소도 필수적이다. 해당 값이 존재해야 패킷을 받은 머신은 자신이 다른 workstation으로 다시 요청하는 패킷을 보낼지 응답 패킷을 보낼지 결정할 수 있기 때문이다. 응답 패킷에는 필수적이지 않을 수 있다. 해당 경우는 만약에 응답 패킷은 요청에 의해서만 생성된다는 보장이 있을 때 해당된다. target의 프로토콜 주소는 알고리즘을 단순하게 만들어주고 모니터링에 도움을 준다.
  • 요청 패킷에서는 target의 하드웨어 주소는 의미가 없다. 왜냐하면 해당 값이 이 프로토콜을 통해서 구하려는 값이기 때문이다.
  • 주소들 간에는 패딩 byte가 없다. 패킷 데이터는 단순히 byte 스트림으로 봐야하며 그 중 ar$hrd, ar$pro, ar$op에 해당 하는 3byte는 word들로 구성되어야한다. 그리고 해당 word들은 Ethernet/PDP-10 byte 스타일에 따라서 MSB에 포함되어야한다.

Network monitoring and debugging

  • 위에 제시된 Address Resolution 프로토콜을 이용하면 해당 머신은 Ethernet 케이블에서 일어나는 일들을 고수준 프로토콜(CHAOS, INTERNET …) 단에서 알 수 있다. 모니터링 모듈은 꼭 고수준 프로토콜 모듈과 통신하며 어떤 값들이 넘어오는지 확인할 필요는 없다.
  • 모니터링 모듈은 Address Resolution 패킷을 받으면 <protocol type, sender protocol address, sender hardware address>를 해당 쌍들을 테이블에 저장한다. 그리고 패킷에서 하드웨어와 프로토콜 주소 길이를 알 수 있다.
  • 만약에 opcode가 REPLY라면 모니터링 모듈은 해당 패킷을 버리고, REQUEST라면 그리고 target 프로토콜 주소가 모니터링 모듈이 자신이 동작하고 있는 머신의 프로토콜 주소와 동일하면 모니터링 모듈이 Address Resolution 모듈 대신에 REPLY 패킷을 보낸다.

An Example

  • 머신 X, Y와 같은 10Mbit Ethernet 케이블 상에 존재한다고 하자. 각각은 Ethernet 주소 EA(X), EA(Y)를 가지고 있고 DOD Internet 주소 IPA(X), IPA(Y)를 가지고 있다. 그리고 Ethernet 타입을 ET(IP)라고 하자.
  • 머신 X가 Y에게 Internet 프로토콜 패킷을 보내고 싶어한다. X 입장에서는 자신은 IPA(Y)로 데이터를 보내고 싶어하고 하드웨어 드라이버 (Ethernet 드라이버)와 통신하여 <ET(IP), IPA(Y)> 쌍 데이터를 48bit Ethernet 주소로 변환하고자 한다.
  • 하지만 X는 Y에 대한 정보를 모르므로 Internet 프로토콜 패킷을 보내는 것이 아니라 대신 Address Resolution 프로토콜 패킷을 보낸다.
(ar$hrd) = ares_hrd$Ethernet
(ar$pro) = ET(IP)
(ar$hln) = length(EA(X))
(ar$pln) = length(IPA(X))
(ar$op)  = ares_op$REQUEST
(ar$sha) = EA(X)
(ar$spa) = IPA(X)
(ar$tha) = don't care
(ar$tpa) = IPA(Y) 
  • X가 보내는 Address Resolution 프로토콜 패킷은 위와 같을 것이고 해당 패킷을 케이블에 존재하는 모든 station들에 브로드캐스트한다.
  • Y는 X가 보낸 Address Resolution 프로토콜 패킷을 받았을 때 다음과 같은 사실들을 확인한다. Y 자신은 Ethernet 하드웨어 타입의 데이터를 이해할 수 있고 Internet 프로토콜도 이해할 수 있다. 마지막으로 ar$tpa 필드의 값이 IPA(Y)와 같은지 확인한다.
  • 그리고 Y는 <ET(IP), IPA<X>> 쌍 데이터를 EA(X)와 매핑시킨다.
  • 그리고 자신이 받은 패킷의 opcode가 ares_op$REQUEST인 것을 확인하고 ‘응답’에 대한 패킷을 만든다. EA(Y)ar$sha에 넣고, opcode를 ares_op$REPLY로 바꾼다. 그리고 패킷을 브로드캐스트하는 것이 아니라 ‘요청’을 보낸 workstation에게 곧장 보낸다.
  • Y가 X에게 ‘응답’ 패킷을 보낸 시점에서 Y는 X에게 어떻게 패킷을 보내는지 알지만 X는 아직 알지 못한다.
  • X가 Y가 보낸 응답 패킷을 받으면 자신의 translation table에 <ET(IP), IPA(Y)>쌍을 EA(Y)에 매핑시킨다. 그리고 opcode가 응답 데이터인 것을 확인하고 해당 패킷을 버린다.
  • 만약 다음번에 X가 다시 Y로 Internet 프로토콜 패킷을 보내려고할 때 Y의 10Mbit Ethernet 주소를 알기 때문에 해당 정보를 이용하여 Y로 패킷을 전송할 것이고, 성공할 것이다. (성공하지 않을 수도 있다.)
  • 반대로 Y가 X로 Internet 프로토콜 패킷을 보내려고 할 때도 이것이 Address Resolution 없이 가능할텐데 이것은 이전에 X가 Address Resolution 요청 패킷을 보냈을 때 해당 데이터를 기억하고 있기 때문이다.

Related issue

  • translation table에 aging이나 timeout 개념이 들어가야할지도 모른다. 하지만 구현 단의 디테일은 이 문서의 범위를 벗어난다.
  • 만약에 어떤 호스트가 이동을 한다면 이동을 한 시점에 해당 호스트와 연결된 다른 호스트들은 이동에 대한 변화를 알아차릴 수 있을 것이다. 하지만 그렇지 않은 다른 호스트들은 이동한 호스트의 바뀐 정보를 알아차릴 방도가 없다. 다시 말하면 다른 호스트들의 translation table에서 이동한 호스트의 정보를 버려야할 트리거, 이유가 없다.
  • 48bit의 Ethernet 주소는 항상 유니크하고 하드웨어에 대해 변하지 않는 고유한 값이다. 호스트의 이름은 바뀔 수 있다. 그리고 잘못된 라우팅 정보가 소프트웨어나 하드웨어의 오작동으로 전파될 수 있으니 translation table의 데이터를 영구적으로 보관하고 있는 것은 바람직하지 않다.
  • 다른 호스트와 커넥션을 맺을 때 실패를 한다면 이 때가 Address Resolution 모듈이 테이블의 엔트리를 업데이트해야할 시점일지도 모른다. 커넥션에 실패를 한다면 Address Resolution 모듈은 해당 호스트에 대한 정보를 삭제해야할 것이다. 커넥션은 여러가지 이유에 의해서 실패할 수도 있다. 타겟 호스트가 잠시 다운되어있을 수도 있고 연결이 더 이상 유효하지 않을 수도 있다. 혹은 제대로 타겟 호스트가 응답했는데 패킷이 다시 도달하는데 시간이 오래걸려 타임아웃에 걸렸을 수도 있다.
  • 이와 같은 여러 요소를 고려하여 특정 시간 내에 타겟 호스트로부터 패킷을 전달받지 못하면 해당 호스트의 주소가 더 이상 유효하지 않다고 판단해야할 수 있다. 이 때 해당 호스트를 찾기 위해서 테이블 전체를 lookup해야할 수도 있는데 이것이 꽤 overhead가 걸릴 수 있다.
  • 그런데 기존의 알고리즘에서 자신이 sender의 ‘요청’ 패킷을 받았을 때, 만약에 translation table에 <protocol type, sender protocol address> 쌍이 존재한다면 sender의 하드웨어 주소를 기존의 엔트리의 데이터 중 하드웨어 주소를 대체한다. 그렇기 때문에 모든 station들에게 ‘요청’ 패킷이 브로드캐스트될 때 각각의 station들은 sender의 새로운 하드웨어 주소를 얻을 것이다.
  • 이는 어떤 호스트가 이동을 하여 프로토콜 주소가 바뀌었을 때 자신의 translation table을 복구하는데 걸리는 시간을 줄이는 방법 중에 하나가 될 수 있다.
  • 빠른 시간 안에 translation table을 항상 최신으로 맞춰 놓는 다른 방법 중에는 translation table의 데이터에 대해서 타임아웃을 관리하는 데몬을 띄우는 것이다. 데몬은 적당한 시간을 주기로 테이블의 엔트리를 이용하여 각각의 호스트에 대해 Address Resolution 프로토콜 패킷을 전송합니다. 이 때 엔트리의 데이터를 기반으로 곧바로 타겟 호스트로 패킷을 전송할 수 있다.
  • 만약에 빠른 시간 안에 ‘응답’ 패킷이 도착한다면 해당 호스트는 아직 자신의 테이블 데이터와 싱크가 맞는다고 생각하고 지우지 않는다. 만약에 특정 시간 내에 도달하지 못했다면 테이블에서 데이터를 삭제한다. 이 때 타임아웃 경계에 따라서 해당 알고리즘이 false positve로 동작할 가능성이 있다.
  • Address Resolution 프로토콜에서는 자신의 정보를 제외한 다른 사람의 정보는 전달하지 않기 때문에 자신을 리부팅하는 것이 translation table을 최신 상태로 맞춰놓는 방법 중 하나가 될 수 있다.