Address Resolution Protocol

Address Mapping

Position of ARP in TCP / IP Protocol Suite

• host 나 router 으로의 데이터 전송에는 IP, MAC 주소가 필요하다.
• packet 이 transport layer 에서 datalink layer 로 전송될 때, datalink layer 에서 일어날 hop to hop delivery 를 위한 MAC 주소를 header 에 명시해 주어야 한다.
• 이를 위해 logical, physical address 간의 mapping 관계가 필요하다.
• 이 mapping 관계를 구축해 나가는 것이 ARP 의 역할이다.
  즉, ARP 의 목표는 logical address 를 input 으로 받아 physical address 를 반환하는 것이다.
• ARP 의 mapping 은 static 할 수도, dynamic 할 수도 있다.

ARP operation

1. ARP request is broadcast
   

• System A 에서 141.23.56.23 의 IP 주소를 사용하는 device 를 찾는다고 가정하자.
• 해당 IP 를 사용하는 device 의 위치를 모르기 때문에, local 내의 모든 device 에게 MAC 주소를 알아내기 위한 ARP request 를 전송한다.
• 모든 곳으로 request 를 보내기 때문에 broadcast 인 것이다.

2. ARP reply is unicast
   

• IP 주소가 일치하는 system B 에서만 reply 가 가고, 나머지 device 는 보내지 않는다.
• 이 reply 는 다른 곳으로 갈 필요가 없기 때문에 sender 에게만 간다.
• 그러므로, ARP reply 는 unicast 인 것이다.

ARP packet

• ARP 의 정보가 표시되는 header 이다.

1. Hardware Type : 하드웨어 주소 유형을 나타내며, 이더넷 통신 시 1로 설정
2. Protocol Type : mapping 대상인 protocol 주소의 유형, IPV4 의 경우 0x0800 으로 설정
3. Hardare Address Length : byte 로 표시되는 하드웨어의 길이 이더넷에서 0x06 으로 설정
4. Protocol Address Length : 프로토콜 주소 길이, IPV4 의 경우 0x04 로 설정
5. Operation Code : ARP 의 구체적인 동작을 나타냄, 오른쪽의 표의 값을 표기

Encapsulation of ARP Packet

• 위 그림은 frame 의 구조를 나타낸 것이다.

1. Preamble : packet 의 시작임을 알려 정보를 읽을 준비를 시킨다.
2. Type : 상위 계층의 프로토콜 정보
   => IP : 0x0800, ARP : 0x0806
3. Data : 상위계층으로부터 전달받은 데이터, ARP header 이 이 곳에 위치한다.

• 130.23.43.20 을 사용하는 A 는 130.23.43.25 를 사용하는 device 의 MAC 주소를 알고 싶다.
• A 는 이를 알기 위해 request 를 보낸다. frame 의 data 영역을 살펴보자.

1. request 이기 때문에 operation code 는 1이다.
2. header 의 밑 부분에는 source 와 destination 의 주소가 적혀있다. destination 의 MAC 주소를 모르기 때문에, 0이 적혀있다. reciever 는 이 정보와 자신의 정보를 비교해, 일치하면 reply 를 unicast 하게 보낸다.

• frame 의 나머지 부분에는 source 와 destination 의 주소와 type 이 명시되어 있다.

1. broadcast 전송을 하기 때문에, destination 에는 broadcast 주소인 0xFFFFFFFF 가 적힌다.
2. type 에는 ARP 임을 명시하기 위해 0x0806 이 적힌다.

• request 를 받는 device 중, IP 주소가 일치하는 B 에서 reply 를 보낸다.
• header 의 operation code 를 2로 설정해 reply 임을 명시한다.

ARP Package

ARP Components

• ARP 의 요소들을 기능에 따라 module 로 분류한 그림이다.
• 각 module 들의 동작을 대략적으로 알아보자.
  1. Output Module
• IP packet 을 받아 ARP request 또는 frame 을 보낸다.
• 정답 즉, IP 주소에 mapping 된 MAC 주소를 아는 경우 MAC 주소가 명시된 frame 을 datalink layer 로 전송한다.
• 정답을 모를 경우, MAC 주소를 알아내기 위해 request 를 보낸다.
• 이 request 는 IP 주소 당 최초의 packet 에 대해서만 전송된다. 나머지 IP packet 들은 IP 주소에 할당된 고유의 queue 에 enqueue 된다. 같은 IP 주소에 대해 여러 개의 request 를 보내는 것은 비효율적이기 때문이다.
  2. Input Module
• ARP packet (request 또는 reply) 가 도착했을 때 작동한다.
• reply 를 받아 정답을 알게 되면, 해당 queue 내의 모든 frame 들을 전송한다.
• request 를 받으면 reply 를 보낸다.
  3. Cache Control Module
• 주기적으로 동작해 cache table 을 관리한다.

Cache Table

• 각 request 에 대한 정보를 기록하는 표
• 이 표는 cache control module 에 의해 주기적으로 관리된다.
  
• 정보의 상태를 나타해는 state 는 세 가지가 있다.

1. F : free, 비어있는 칸
2. R : reply 를 통해 정답을 알아낸 resolved 상태. hardware address 에 MAC 주소가 표기되어 있다. time out 되면 정보가 사라진다.
3. P : reqeust 를 보냈으나, 아직 정답을 모르는 pending 상태. queue 에서 대기 중이기 때문에 queue 에 할당된 queue number 이 표시된다. attempt 는 request 를 보낸 횟수다. request 를 무한정 보낼 수 없기 때문에 최대치에 도달하면 정보가 삭제된다.

Output Module

• pseudocode 를 통해 동작을 자세히 살펴보자

ARP_OUTPUT_MODULE() {
sleep until an IP packet is recieved. // IP packet 도착 시 동작
lookup cache table for an entry corresponding to the destination of the IP packet

if (entry is found) { // cache table 에서 해당하는 IP 주소에 대한 정보를 찾음
	if (state is R) {
    		extract value of hardware address from entry
            send packet with address to datalink layer 
            // frame 을 제작하고 datalink 로 정보 전송
            return
    }
    if (state is P) {
    	enqueue the packet to the corresponding queue
    	// 모든 IP packet 에 대해 request 를 보내면 과부하 되기 때문에 queue 에 관리
    	return
    }
}

if (entry is not found) { // 저장되지 않은 새로운 IP 주소에서 IP packet 도착
	create a cache entry with state set to P // 정답을 모르기 때문에 P 로 설정된 entry 생성
    set ATTEMPT to 1 // 정답을 알기 위해 첫 request 를 보냄
    create a queue // 해당 IP 주소에 할당되는 queue 생성, 이후 도착하는 packet 관리
    enqueue the packet
    send an ARP request
    return
}

Input Module

ARP_INPUT_MODULE() {
sleep until an ARP packet arrives // ARP packet 도착 시 동작
lookup cache table to find corresponding entry

if (found) {
	update entry // ARP packet 의 최신 정보로 state 에 따라 table 정보 update
    // R state 였던 경우 timeout 값을 reset (아직 유효한 정보인 것이 검증됨)
    // P state 였던 경우 hardware address 와 timeout 값 update
    if (state is P) {
    	while (!queue is empty){
        	dequeue packet // 정답을 기다리던 packet 들을 dequeue 해 datalink layer 로 전송
            send packet with address to datalink layer
		}
    }
}

if (not found) {
	create entry and add entry to cache table
    if (packet is a request)
    	send ARP reply
    return
}

Cache Control Module

ARP_Cache_Control_Module() {
sleep until periodic timer matures // 일정 시간마다 동작해 cache table 관리
for (every entry in cache table) {
	if (state is F)
    	continue
        
    if (state is P) {
    	ATTEMPT++
        if (ATTEMPT > MAX_ATTEMPT) {
        	change state to F // 최대 전송 횟수 초과시 정보 파기
            destroy corresponding queue // 해당하는 queue 삭제
        } else send ARP request
    continue
    }
    
    if (state is R) {
    	TIMEOUT--
        if (TIMEOUT <= 0) { // timeout 된 정보 파기
        	change state to F
            destroy corresponding queue
        }
    }
    return
}

• ARP module 들의 동작과 그에 따른 cache table 의 변화를 살펴보자.
  1. 처음 상태
  
  2. Output module 이 destination address 가 114.5.6.89 인 IP packet 을 받음
  => R state 의 packet 이므로 cache table update 없이 hardware address 를 추출해 datalink layer 로 packet 전송
  
  3. 20초 후 Output module 이 destination address 가 116.1.7.22 인 IP packet 을 받음
  
  => 원래 없던 정보였으므로, F state 의 row 에 정보를 기입한다. queue 가 새로 생성되고,
  queue number 23 을 부여받는다. hardware address 를 알아내기 위해 ARP request 를 보내고, attepmt 가 1로 설정된다.
  => 만약 114.5.7.89 를 받았다면, timeout 값이 초기값인 900으로 초기화된다.
  
  4. 15초 후 ARP Inupt Module 이 target address 가 188.11.8.71 인 ARP packet 을 받는다.
  
  => P state 인 packet 이 정답을 알게 된 상태다.
  => hardware address 가 기입되고, R state 로 전이된다.
  => queue number 이 삭제되고, timeout 이 초기값인 900으로 설정된다.
  => queue 에서 대기 중이던 packet 들을 모두 datalink layer 로 전송한다.
  
  5. 25초 후 주기가 60초인 cache control module 이 작동한다.
  
  => R state 의 packet 들의 timeout 값이 변한다. 이들의 생성 시간을 추적해, 이전의 cache control module 작동 전에 생성된 packet 들의 timeout 은 60초 감소한다. 그렇지 않은 packet 들의 timeout 은 생성 후 지난 시간만큼만 감소한다. 188.11.8.71 의 경우, 4번에서 생성되었고, 생성된지 25초가 지났기 때문에 25만 줄어든 것을 확인할 수 있다.
  => packet 들의 attempt 가 1씩 증가하고, 각각의 request 가 전송된다. max attempt 인 5를 초과한 201.11.56.7 은 삭제된다.
  => 표에는 없지만, timeout 이 지난 packet 이 있었다면, 삭제된다.