Charles M. Kozierok The TCP-IP Guide

Подождите немного. Документ загружается.

General Address Resolution Methods

In fact, not only do we need to have way of making this translation, we need to be

concerned with the manner in which it is done. Since the translation occurs for each hop of

every datagram sent over an internetwork, the efficiency of the process is extremely

important. We don't want to use a resolution method that takes a lot of network resources.

Address resolution can be accomplished in two basic ways:

☯ Direct Mapping: A formula is used to map the higher-layer address into the lower-

layer address. This is the simpler and more efficient technique but has some limita-

tions, especially regarding the size of the data link layer address compared to the

network layer address.

Figure 44: Why Address Resolution Is Necessary

In this example, a client on the local network is accessing a server somewhere on the Internet. Logically, this

connection can be made “directly” between the client and server, but in reality it is a sequence of physical links

at layer two. In this case there are six such links, most of them between routers that lie between the client and

server. At each step the decision of where to send the data is made based on a layer three address, but the

actual transmission must be performed using the layer two address of the next intended recipient in the route.

Internet Server

IP Addr: 21.44.191.36

Link #3

Link #2

Link #1

Link #5

Link #6

Link #4

Client Host

IP Addr: 10.2.14.77

Hardware Addr: 0A-A7-94-07-CB-D0

Local Router

LAN IP Addr: 10.2.14.1

Hardware Address: ??

☯ Dynamic Resolution: A special protocol is used that allows a device with only an IP

address to determine the corresponding data link layer address, even if they take

completely different forms. This is normally done by interrogating one or more other

devices on a local network to determine what data link layer address corresponds to a

given IP address. This is more complex and less efficient than direct mapping but is

more flexible.

The next two topics explore these two methods in more detail.

You should bear in mind that of necessity, it is not possible to have a fully general address

resolution method that works automatically. Since it deals with linking data link layer

addresses to network layer addresses, the implementation must be specific to the technol-

ogies used in each of these layers. The only method that could really be considered generic

would be the use of static, manually-updated tables that say “link this layer three address to

this layer two address”. This, of course, is not automatic and brings with it all the limitations

of manual configuration.

Address Resolution Through Direct Mapping

Network layer addresses must be resolved into data link layer addresses numerous times

during the travel of each datagram across an internetwork. We therefore want the process

to be as simple and efficient as possible. The easiest method of accomplishing this is to do

direct mapping between the two types of addresses.

The basic idea behind direct mapping is to choose a scheme for layer two and layer three

addresses so that you can determine one from the other using a simple algorithm. This

enables you to take the layer three address, and follow a short procedure to convert it into a

layer two address. In essence, whenever you have the layer three address you already

have the layer two address.

The simplest example of direct mapping would be if we used the same structure and

semantics for both data link and network layer addresses. This is generally impractical,

because the two types of addresses serve different purposes, and are therefore based on

incompatible standards. However, we can still perform direct mapping if we have the flexi-

bility of creating layer three addresses that are large enough to encode a complete data link

layer address within them. Then, determining the layer two address is a simple matter of

selecting a certain portion of the layer three address.

As an example, consider a simple LAN technology like ARCNet. It uses a short 8-bit data

link layer address, with valid values of 1 to 255, which can be assigned by an administrator.

We could easily set up an IP network on such a LAN by taking a class C (or /24) network

and using the ARCNet data link layer as the last octet. So, if our network were, for example,

222.101.33.0/24, we could assign the device with ARCNet address #1 the IP address

222.101.33.1, the device with ARCNet address #29 would be 222.101.33.29 and so forth,

as shown in Figure 45.

The appeal of this system is obvious. Conceptually, it is trivially simple to understand—to

get the hardware address for a device, you just use the final eight bits of the IP address. It's

also very simple to program devices to perform, and highly efficient, requiring no exchange

of data on the network at all.

Key Concept: When the layer two address is smaller than the layer three address, it

is possible to define a direct mapping between them, so that the hardware address

can be determined directly from the network layer address. This makes address

resolution extremely simple, but reduces flexibility in how addresses are assigned.

Direct Mapping Not Possible With Large Hardware Addresses

Unfortunately, direct mapping only works when it is possible to express the data link layer

address as a function of the network layer address. Consider instead the same IP address,

222.101.33.29, running on an Ethernet network. Here, the data link layer addresses are

“hard-wired” into the hardware itself (they can sometimes be overridden but usually this is

not done). More importantly, the MAC address is 48 bits wide, not 8. This means the layer

two address is bigger than the layer three address, and there is no way to do direct

mapping, as Figure 46 illustrates.

Figure 45: Address Resolution Through Direct Mapping

When the hardware address is small, it is easy to define a mapping that directly corresponds to a portion of a

layer three address. In this example, an 8-bit MAC address, such as that used for ARCNet, is mapped to the

last byte of the device’s IP address, making address resolution a trivial matter.

222 101 33 29

11011110 01100101 00100001 00101001

8 1624320

00101001

32-bit IP Address

(222.101.33.29)

Decimal

Binary

Decimal

Binary

8-bit Hardware Address

(#29)

Note: In the case where the hardware address size exceeds the network layer

address size, we could do a “partial mapping”. For example, we could use the IP

address to get part of the MAC address and hope we don't have duplication in the

bits we didn't use. This method is not well-suited to regular transmissions, but is in fact used

for resolving multicast addresses in IPv4 to Ethernet addresses.

In general, then, direct mapping is not possible when the layer three address is smaller than

the layer two address. Consider that Ethernet is the most popular technology at layer two

and uses a 48-bit address, and IP is the most popular technology at layer three and uses a

32-bit address. This is one reason why direct mapping is a technique that is not only not

widely used, but that most people don't know about!

Inflexibility of Direct Mapping

Now let’s consider the next generation, IP version 6? IPv6 supports massive 128-bit

addresses. Furthermore, regular (unicast) addresses are even defined using a method that

creates them from data link layer addresses using a special mapping. This would in theory

allow IPv6 to use direct mapping for address resolution.

Figure 46: Address Resolution Problems With Large Hardware Address Size

When the layer two address is larger in size than the layer three address, it is not possible to define a mapping

between them that can be used for address resolution.

8 1624320

? ? ? ?

32-bit

IP Address

(?)

Decimal

Binary

Hexadecimal

Binary

48-bit Hardware Address

(0A-A7-94-07-CB-D0)

0A A7 94 07 CB D0

00001010 10100111 10010100 00000111 11001011 11010000

8 1624320 40 48

However, the decision was made to have IPv6 use dynamic resolution just as IPv4 does.

One reason might be historical, since IPv4 uses dynamic resolution. However, the bigger

reason is probably due to a disadvantage of direct mapping: its inflexibility. Dynamic

resolution is a more generalized solution, because it allows data link layer and network

layer addresses to be independent, and its disadvantages can be mostly neutralized

through careful implementation, as we will see.

In fact, evidence for this can be seen in the fact that dynamic resolution of IP is in fact

defined on ARCNet, the example we just used. We could do direct mapping there, but it

restricts us to a certain pattern of IP addressing that reduces flexibility.

Dynamic Address Resolution

Direct mapping provides a simple and highly efficient means of resolving network layer

addresses into data link layer addresses. Unfortunately, it is a technique that we either

cannot or should not use in a majority of cases. We cannot use it when the size of the data

link layer address is larger than that of the network layer address. We shouldn't use it when

we need flexibility, because direct mapping requires us to make layer three and layer two

addresses correspond.

The alternative to direct mapping is a technique called dynamic address resolution. To

understand how this works, we can consider a simple analogy. I'm sure you've seen

limousine drivers waiting to pick up a person at the airport they do not know personally.

(Well, you've seen it in a movie, haven't you?) This is similar to our problem: they know the

name of the person they must transport, but not the person's face (a type of “local address”

in a manner of speaking!) To find the person, they hold up a card bearing that person's

name. Everyone other than that person ignores the card, but hopefully the individual being

sought will recognize it and approach the driver.

We do the same thing with dynamic address resolution in a network. Let's say that device A

wants to send to device B but knows only device B's network layer address (its “name”) and

not its data link layer address (its “face”). It broadcasts a layer two frame containing the

layer three address of device B—this is like holding up the card with someone's name on it.

The devices other than B don't recognize this layer three address and ignore it. Device B,

however, knows its own network layer address. It recognizes this in the broadcast frame

and sends a direct response back to device A. This tells device A what device B's layer two

address is, and the resolution is complete. Figure 47 illustrates the process.

Key Concept: Dynamic address resolution is usually implemented using a special

protocol. A device that knows only the network layer address of another device can

use this protocol to request the other device’s hardware address.

Direct mapping is very simple, but as you can see, dynamic resolution isn't exactly rocket

science. It's a very simple technique that is easily implemented. Furthermore, it removes

the restrictions associated with direct mapping. There is no need for any specific

relationship between the network layer address and the data link layer address; they can

have a completely different structure and size.

There is one nagging issue though: the efficiency problem. Where direct mapping involves

a quick calculation, dynamic resolution requires us to use a protocol to send a message

over the network. Fortunately, there are techniques that we can employ to remove some of

the sting of this cost through careful implementation.

Dynamic Address Resolution Caching and Efficiency Issues

Dynamic address resolution removes the restrictions that we saw in our look at direct

mapping, and allows us to easily associate layer two and layer three addresses of any size

or structure. The only problem with it is that each address resolution requires us to send an

extra message that would not be required in direct mapping. Worse yet, since we don't

know the layer two identity of the recipient, we must use a broadcast message (or at least a

multicast), which means that many devices on the local network must take resources to

examine the data frame and check which IP address is being resolved.

Figure 47: Dynamic Address Resolution

Device A needs to send data to Device B but knows only its IP address (“IPB”), and not its hardware address.

A broadcasts a request asking to be sent the hardware address of the device using the IP address “IPB”. B

responds back to A directly with the hardware address.

Device A

IP Addr: IPA

Hardware Addr: #213

Device B

IP Addr: IPB

Hardware Addr: #79

Device D

IP Addr: IPD

Hardware Addr: #114

Device C

IP Addr: IPC

Hardware Addr: #46

Who Is IPB?

IPB is #79

LAN

Switch

Sure, sending one extra message may not seem like that big a deal, and the frame doesn't

have to be very large since it contains only a network layer address and some control infor-

mation. However, when we have to do this for every hop of every datagram transmission,

the overhead really adds up. For this reason, while basic dynamic address resolution as

described in the previous topic is simple and functional, it's usually not enough. We must

add some intelligence to the implementation of address resolution to reduce the impact on

performance of continual address resolutions.

The Benefits of Caching

Consider that most devices on a local network send to only a small handful of other physical

devices, and tend to do so over and over again. This is a phenomenon known as locality of

reference, and is observed in a variety of different areas in the field of computing. If you

send a request to an Internet Web site from your office PC, it will need to go first to your

company network's local router, so you will need to resolve the router's layer two address. If

you later click a link on that site, that request will also need to go to the router. In fact,

almost everything you do off your local network probably goes first to that same router

(commonly called a default gateway). Having to do a fresh resolution each time is, well,

stupid. It would be like having to look up the phone number of your best friend every time

you want to call to say hello. (Reminds me of that sketch on Saturday Night Live where the

guy had no short-term memory—but I digress.)

To avoid being accused of making address resolution protocols that are, well, stupid,

designers always include a caching mechanism. After a device's network layer address is

resolved to a data link layer address, the link between the two is kept in the memory of the

device for a period of time. When it needs the layer two address the next time, the device

just does a quick lookup in its cache. This means instead of doing a broadcast on every

datagram, we only do it once for a whole sequence of datagrams.

Caching is by far the most important performance-enhancing tool in dynamic resolution. It

transforms what would otherwise be a very wasteful process into one which most of the

time is no less efficient than direct mapping. It does, however, add complexity. The cache

table entries must be maintained. There is also the problem that the information in the table

may become stale over time; what happens if we change the network layer address or the

data link layer address of a device? For this reason, cache entries must be set to expire

periodically. The topic on caching in the TCP/IP ARP protocol shows some of the particulars

of how these issues are handled.

Other Enhancements to Dynamic Resolution

Other enhancements are also possible to the basic dynamic resolution scheme. Let's

consider again our example of sending a request to the Internet. We send a request that

needs to go to our local router, so we resolve its address and send it the request. A moment

later the reply comes back to the router to be sent to us, so the router needs our address.

Thus, it would have to do a dynamic resolution on us even though we just exchanged

frames. Again: stupid. Instead, we can improve efficiency through cross-resolution; when

device A resolves the address of device B, device B also adds the entry for device A to its

cache.

Another improvement can be made too. If you think about it, the devices on a local network

are going to talk to each other fairly often, even if they aren't chatting right now. If A is

resolving B's network layer address, it will broadcast a frame that devices C, D, E and so on

all see. Why not have them also update their cache tables with resolution information that

they see, for future use?

These and other enhancements all serve to cut down on the efficiency problems with

dynamic address resolution. They combine to make dynamic resolution close enough to

direct mapping in overall capability that there is no good reason not to use it. Once again,

you can see some more particulars of this in the topic that describes the TCP/IP ARP

protocol's caching feature.

Incidentally, one other performance-improving idea sometimes is brought up in this

discussion: instead of preceding a datagram transmission with an extra broadcast step for

address resolution, why not just broadcast the datagram and be done with it? We actually

could do this, and if the datagram were small enough it would be more efficient. Usually,

though, datagrams are large, while resolution frames can be quite compact; it makes sense

to do a small broadcast and then a large unicast rather than a large broadcast. Also,

suppose we did broadcast this one datagram: what about the next datagram and the one

after that? Each of these would then need to be broadcast also. When we do a resolution,

with caching, we need to broadcast only once in a while instead of continually.

TCP/IP Address Resolution Protocol (ARP)

The most widely used network layer protocol in the world—by far—is the TCP/IP Internet

Protocol. It's no surprise then, that the most important address resolution protocol is the

TCP/IP protocol bearing the same name as the technique itself: the Address Resolution

Protocol (ARP). ARP is a full-featured dynamic resolution protocol used to match IP

addresses to underlying data link layer addresses. Originally developed for Ethernet, it has

now been generalized to allow IP to operate over a wide variety of layer two technologies.

In this section I describe the operation and features of ARP. I begin with an overview of the

protocol, and a discussion of its defining standards and history. I briefly outline how

addresses are specified in ARP and its general operation, as well as describing the

message format used for ARP messages. I then turn to the important matter of caching in

ARP and how that is used to improve performance. I conclude with a discussion of proxying

in ARP, which is needed to support special network connectivity situations.

Background Information: The general explanation of address resolution, what it

is, and how it works, can be found in the preceding section on address resolution

concepts. Except for a brief recap at the start of the overview, I assume you have

familiarity with these concepts.

Note: The Address Resolution Protocol described here is used for resolving

unicast addresses in version 4 of the Internet Protocol. Multicast addresses under

IPv4 use a direct mapping method, described in a separate topic. IPv6 uses the

new Neighbor Discovery protocol instead of ARP; this is discussed in the overview of IPv6

address resolution.

Related Information: For a discussion of ARP-related issues in networks with

mobile IP devices, see the section on Mobile IP.

Related Information: The software application “arp”, which is used to administer

the TCP/IP ARP implementation on a host, is covered in its own topic in the

section on TCP/IP utilities.

ARP Overview, Standards and History

Physical networks function at layers one and two of the OSI Reference Model, and use data

link layer addresses. In contrast, internetworking protocols function at layer three, intercon-

necting these physical networks to create a possibly huge internetwork of devices specified

using network layer addresses. Address resolution is the process where network layer

addresses are resolved into data link layer addresses, to permit data to be sent one hop at

a time across an internetwork. I describe address resolution in detail in the preceding

section on concepts.

The problem of address resolution was apparent from the very start in the development of

the TCP/IP protocol suite. Much of the early development of IP was performed on the then-

fledgling Ethernet local area networking technology; this was even before Ethernet had

been officially standardized as IEEE 802.3. It was necessary to define a way to map IP

addresses to Ethernet addresses to allow communication over Ethernet networks.

There are two basic methods that resolution could have been used to accomplish this

correlation of addresses: direct mapping or dynamic resolution. However, Ethernet

addresses are 48 bits long while IP addresses are only 32 bits, which immediately rules out

direct mapping. Furthermore, the designers of IP wanted the flexibility that results from

using the dynamic resolution model. To this end, they developed the TCP/IP Address

Resolution Protocol (ARP). This protocol is described in one of the earliest of the Internet

RFCs still in common use: RFC 826, An Ethernet Address Resolution Protocol, published in

1982.

The name makes clear that ARP was originally developed for Ethernet. Thus, it represents

a nexus between the most popular layer two LAN protocol and the most popular layer three

internetworking protocol—this is true even two decades later. However, it was also obvious

from the beginning that even if Ethernet was a very common way of transporting IP, it would

not be the only one. Therefore, ARP was made a general protocol capable of resolving

addresses from IP to not just Ethernet but numerous other data link layer technologies.

The basic operation of ARP involves encoding the IP address of the intended recipient in a

broadcast message. It is sent on a local network to allow the intended recipient of an IP

datagram to respond to the source with its data link layer address. This is done using a

simple request/reply method described in the following topic on general operation. A special

format is used for ARP messages, which are passed down to the local data link layer for

transmission.

Key Concept: ARP was developed to facilitate dynamic address resolution between

IP and Ethernet, and can now be used on other layer two technologies as well. It

works by allowing an IP device to send a broadcast on the local network, requesting

that another device on the same local network respond with its hardware address.