In general, one aspect of the subject matter described in this specification can be embodied in a method that includes receiving at a first device a first request for a physical address of a second device different from the first device, wherein the first request specifies a network address of the second device, and determining that a set of pending requests has a maximum number of requests, wherein the set of pending requests is ordered based on when the requests were received by the first device. The method can further include removing an oldest request from the pending requests and adding the first request to the pending requests, and processing a newest request in the pending requests by sending a message to the second device and receiving the physical address responsive to the message.