1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949
|
Network Working Group G. Parr
Request For Comments: 1029 University of Ulster
May 1988
A MORE FAULT TOLERANT APPROACH TO ADDRESS RESOLUTION FOR
A MULTI-LAN SYSTEM OF ETHERNETS
STATUS OF THIS MEMO
This memo discusses an extension to a Bridge Protocol to detect and
disclose changes in neighbouring host address parameters in a Multi-
LAN system of Ethernets. The problem is one which is appearing more
and more regularly as the interconnected systems grow larger on
Campuses and in Commercial Institutions. This RFC suggests a
protocol enhancement for the Internet community, and requests
discussion and suggestions for improvements. Distribution of this
memo is unlimited.
ABSTRACT
Executing a protocol P, a sending host S decides, through P's routing
mechanism, that it wants to transmit to a target host T located
somewhere on a connected piece of 10Mbit Ethernet cable which
conforms to IEEE 802.3. To actually transmit the Ethernet packet, a
48 bit Ethernet/hardware address must be generated. The addresses
assigned to hosts within protocol P are not always compatible with
the corresponding Ethernet address (being different address space
byte orderings or values). A protocol is presented which allows
dynamic distribution of the information required to build tables that
translate a host's address in protocol P's address space into a 48
bit Ethernet address. An extension is incorporated to allow such a
protocol to be flexible enough to exist in a Transparent Bridge, or
generic Host. The capability of the Bridge to detect host reboot
conditions in a multi-LAN environment is also discussed, emphasising
particularly the effect on channel bandwidth. To illustrate the
operation of the protocol mechanisms, the Internet Protocol (IP) is
used as a benchmark [6], [8]. Part 1 presents an introduction to
Address Resolution, whilst Part 2 discusses a reboot detection
process.
DEFINITIONS:
CATENET: a group of IP networks linked together
IP : Internet Protocol
Parr [Page 1]
RFC 1029 Fault Tolerant ARP for Multi-LANs May 1988
PART 1
INTRODUCTION
In the Ethernet, while all packets are broadcast, the hardware
interface selects only those with either the explicit hardware
broadcast address or the individual hardware address of this
interface. Packets which do not have one of these two addresses are
rejected by the interface and do not get passed to the host software.
This saves a great deal of otherwise wasted effort by the host
software having to examine packets and reject them. If the interface
hardware selected packets to pass to the host software by means of
the protocol address, there would be no need for any translation from
protocol to Ethernet address. Although it is very important to
minimize the number of packets which each host must examine, so
reducing especially needless inspections, use of the hardware
broadcast address should be confined to those situations where it is
uniquely beneficial. Perhaps if one were designing a new local
network one could eliminate the need for an address translation, but
in the real world of existing networks it fills a very important
purpose. A rare use of the broadcast hardware address, which avoids
putting any processing load on the other hosts of the Ethernet, is
where hosts obtain the information they need to use the specific and
individual hardware addresses to exchange most of their packets.
REASONING BEHIND ADDRESS RESOLUTION
The process of converting from the logical host address to the
physical Ethernet address has been termed ADDRESS RESOLUTION, and has
prompted research into a method which can be easily interfaced,
whilst at the same time remaining portable.
The Ethernet requires 48 bit addresses on the physical cable [11] due
to the fact that the manufacturers of the LAN interface controllers
assign a unique 48 bit address during production. Of course, Network
Managers do not want to be bothered using this address to identify
the destination at the higher-level. Rather, they would prefer to
assign their logical names to the hosts within their supervision, and
allow some lower level protocol to perform a resolving operation.
Most of these logical protocol addresses are not 48 bits long, nor do
they necessarily have any relationship to the 48 bit address space.
For example, IP addresses have a 32 bit address space [6], thus
giving rise to the need to distribute dynamically the correspondences
between a <PROTOCOLTYPE,PROTOCOL-ADDRESS> pair, and a 48 bit Ethernet
address.
Parr [Page 2]
RFC 1029 Fault Tolerant ARP for Multi-LANs May 1988
EXAMPLE ARP OPERATION
Here is a review of the operation of ARP as defined in RFC-826 [5].
Let hosts X and Y exist on the same Ethernet cable. They have
physical Ethernet addresses EA(X), and EA(Y), and DoD Internet
addresses IPA(X), and IPA(Y). Let the Ethernet type of Internet be
ET(IP). Host X begins an application, and sooner or later wishes to
communicate an Internet packet to host Y. Host X has knowledge of
the Internet address of Y, i.e., (IPA(Y)), and informs the lower
level that it wishes to talk to IPA(Y). The lower-level subsequently
consults the ARP Module (ARM) to convert <ET(IP),IPA(Y)> into a 48
bit Ethernet address but because X has not talked to Y previously, it
does not have this information in its Translation Cache (TC). It
discards (or queues) the Internet packet, and creates a new Address
Resolution packet with:
PACKET FIELD VALUE ASSIGNED
HRDTYP ETHERNET
PROTYP ET(IP)
HRDLEN length (EA(X))
PROTLEN length (IPA(X))
ARPOPC REQUEST
SOURCE HWR EA(X)
SOURCE PROT IPA(X)
TARGET HWR don't know
TARGET PROT IPA(Y)
It then broadcasts this packet to all hosts on the connecting cable.
Host Y picks up this packet and determines that it understands the
hardware type (Ethernet), that it speaks the indicated protocol
(Internet), and that the packet is for it, that is, TARGET PROTOCOL
ADDRESS = IPA(Y). Replacing any previous entry, it enters the
information that <ET(IP),IPA(X) translates to EA(X). It then learns
that this is an ARREQ packet, so it swaps fields, placing EA(Y) in
the new sender Ethernet address field SOURCE HARDWARE ADDRESS, EA(X)
as TARGET HARDWARE ADDRESS, IPA(X) as TARGET PROTOCOL ADDRESS, IPA(Y)
as SOURCE PROTOCOL ADDRESS, and sets the opcode to REPLY. The packet
is then sent with direct routing address information to EA(X). Thus,
Y now knows how to send to X, but X still doesn't know EA(Y).
Parr [Page 3]
RFC 1029 Fault Tolerant ARP for Multi-LANs May 1988
When X receives the ARREP packet from Y, it gets the address
information into its translation cache ET(IP),IPA(Y)>-->EA(Y),
notices that it is a REPLY, and discards the packet (i.e., disposes
of the dynamic packet buffer). However, if the original Internet
Module packet had been queued, it could have been accessed and given
the full addressing information from the translation cache.
Alternatively, had it been discarded, the higher level would have
succeeded on a subsequent attempt, and the Internet packet would be
transmitted immediately.
OBTAINING GREATER NETWORKING RANGE
There are many benefits to be gained in dividing a large multiuser
network into smaller, more manageable networks. These include : Data
Security; Overall Network Reliability; Performance Enhancement; not
to mention the most obvious: Greater Networking Range. In some
network technologies, cable length may be stipulated not to exceed a
certain range due to electrical limitations. By installing a Bridge,
this restriction is effectively eliminated. An important
consideration is the effect the induced Bridge delays will have on
the protocol timeouts in operation on each LAN/Subnet. Careful
analysis of upper bounds on timeouts would have to be made in order
to gain full benefit from the increased range. In the case of
Ethernet the following system parameters exist [11], [12]:
- the bus bandwidth is 10Mbit/s
- the maximum node-to-node cable length is 1500 m
- the maximum point-to-point link cable length is 1000 m
- the maximum number of repeaters between two nodes is two
- the worst case end-to-end bus propagation delay is 22.5 us
- the jam time after collision is 32bit
- the minimum interframe time is 9.6 us
- the slot size is 512 bit = 51.2 us
Once a decision has being taken to subnet, the resulting subLANs may
be connected by including a Bridge to link them together and
providing a protocol which makes the collection of subnets appear as
a single network. The basic idea of the Bridge providing 'repeater'
facilities would not suffice in this application. Moreover, the
Bridge would have to have further 'intelligence' to enable it to
select those packets which are destined for remote networks based on
Parr [Page 4]
RFC 1029 Fault Tolerant ARP for Multi-LANs May 1988
the protocol address of the target host. Thereby preventing it from
forwarding packets needlessly that will not be accepted. If this
procedure was not adhered to, the channel bandwidth on the remote
networks would be inundated with packets, causing local valid traffic
to backoff and the efficiency of the respective networks to rapidly
decrease.
One problem fundamental to the operation of the Bridge is how it
discovers on which LAN a particular host is interfaced. If there are
only two LANs in the system, each will have a dedicated cache at the
Bridge, and when a packet is received at the particular interface,
the source host's address parameters are entered in the respective
LAN cache. However, when we consider a Multi-LAN environment, the
procedure becomes more complicated.
___
|
|-----h3
| E4
|-----hq |-----------------------|
| _ | |
|-----hx | | B1 | |
|---------------| | | |
|-----h1 |_| | |
| | h19 | | ______
| | | | | -----|______| B4
| | | | | B3 |
|-----he |-------------------| E2 |_| |
| | | |
|-----h5 | | |
| | | |
| --- --- | |
--- | | |------- |
E1 | | B2 | |
| |-----------------| |
--- | |
| |---------------------
--- |
E3 |
|
FIGURE 1. A MULTI-LAN TOPOLOGY
In the normal set-up, whenever B3 or B4 would receive a packet on E4,
they would both update the caches on their E4 interface. In
addition, a method must be provided to permit B4 to distinguish
between packets arriving on E4 from E1, E2, E3, and those which
actually originated on E4.
Parr [Page 5]
RFC 1029 Fault Tolerant ARP for Multi-LANs May 1988
This is so that packets can be categorized as being of remote or
local source and processed accordingly. The most obvious solution is
for each Bridge to act as an AGENT and plug in its address as the
source of any packets it cascades to a remote network, instead of the
packet being cascaded with its original source address. At Bridge
boot, it may issue a broadcast request for all locally connected
hosts/devices to return their local network protocol addresses. On
subsequent receipt of this information, the Bridge could then update
the cache for each of its interfaces so that it would now have a base
from which to perform future operations.
The alternative to this automatic procedure is to permit manual
intervention in the Bridge software which could be activated by the
network manager in order to key in the addresses of the hosts
connected to each LAN interface.
Thus, having provided a means for the Bridge to obtain the original
state of the LAN addresses when it boots, how then does the Bridge
distinguish the arrival of a new host on the locally connected system
from transmissions which were sent from a remote source and cascaded
by an adjacent Bridge? Two approaches are currently under
consideration to solve this problem, namely Explicit Subnets, and
Transparent Subnets [4], [7], [9], [14].
In the Explicit Subnet approach, the location of the host in the
system is important. The address of the host in the protocol suite
will reflect which subnet the host is interfaced to. Consequently
the protocol address space is divided into a three level hierarchy of
<network,subnet,host>. Within the Internet there are five addressing
divisions in operation [10], classes A, B, C, D, and E. Classes D
and E relate to an addressing technique that will be used for
management of multi-casting groups and will not be discussed here.
With such a structure, it is possible to provide an address mask at
each interface so that received packets may have their source address
fields examined and compared with the address mask of this LAN. In
so doing, the component which is being verified is actually the
subnet address. If the masking operation is successful the source
must exist on this LAN, otherwise it must be remote.
With the Transparent scheme, the first time a newly booted host
'speaks' it will be looking for addressing information (probably
using BOOTSTRAP [1], RARP [2] or ARP [5]). Accordingly, the Bridge
will detect these respective requests and be in a position to perform
operations on the address parameters. The current approach in
Transparent Subnetting is that before any such requests can be
cascaded by the Bridge to an adjacent LAN, that Bridge will place its
interface address parameters into the source address fields, thus
acting as the AGENT. Therefore, this Bridge will 'see' either
Parr [Page 6]
RFC 1029 Fault Tolerant ARP for Multi-LANs May 1988
packets arriving from the remote Bridge address, or local packets.
By virtue of the RARP/ARP operation, which hosts perform when they
first come up, any hi-level packets received on to the network not
having the bridge address, and not having a mapping in the cache for
that LAN, can be considered as being remote.
Currently, there is a move toward the Transparent subnet proposal
originally described by Postel [7]. This has been due mainly to
practical problems of incompatible implementations from different
vendors, and the restrictions that the Explicit address space place
on the adaptability of the system to change (class C addresses are
not flexible enough for the Explicit scheme). It is also the opinion
of the Author of this paper that the Agent technique adopted by the
Bridges could have shortcomings in a dynamic environment which would
be detrimental to its operation; for example, where the bridges
themselves relocate or crash, or in the management of the "Agent For
Who" cache at the bridge. Insofar as Loop Resolution and
SelfStabilization after failure are Bridge problems that need to be
addressed, it is strongly felt their satisfactory solution will be
supported by elimination of the Agent technique [13].
BRIDGE OPERATIONS
Referring to figure 1, assume that at some stage during its
processing [E1H3] wishes to communicate with [E2H19]. [E1H3] obtains
knowledge of the Internet address of [E2H19] from its translation
cache, but will not require the knowledge that [E2H19] exists on a
completely different subnet. [E1H3] calls its Internet Module to
transmit the packet. As detailed, the usual procedure of passing
control to its ARM is performed in an attempt to obtain a
translation. If we assume that [E1H3], and [E2H19] have not talked
before, the ARM in [E1H3] will not be able to resolve the addresses
on the first attempt.
In such a case, an ARREQ packet is assembled and broadcast to all
hosts on the network [E1]. The packet traverses the cable and is
eventually picked up by the (B1) Bridge Address Resolution Module
(BARM), whereupon it determines whether or not it should intervene in
the request. If the target is determined as remote (i.e., having no
match in the local cache), the BARM examines its Global Translation
Cache (GTC) to determine if it has an entry for <protocol,[E2H19]>.
Should a mapping be obtained at the Bridge, there is no need for the
broadcast REQUEST packet to be cascaded on to the remote network
[E2]. It is therefore assumed that the entries in the GTC reflect
the most current addressing information. A match thus obtained, the
original ARREQ packet buffer is adapted as required and returned
directly to [E1H3] via the Bridges hardware interface IFE1.
Parr [Page 7]
RFC 1029 Fault Tolerant ARP for Multi-LANs May 1988
On the other hand, should the Bridges' GTC have no information on
[E2H19], the BARM would have to perform the following steps:
1. drop the current ARREQ from [E1H3],
2. create its own ARREQ using the Bridge source addresses
and copy the target_internet_addr from the original
[E1H3] ARREQ packet,
3. broadcast the ARREQ on network E2 via network interface
IFE2, and go into a timeout awaiting a REPLY.
Should this timeout period expire, a number of retries will be
permitted under control of the BARM. Alternatively, if a REPLY is
received within the timeout interval, then the BARM will update its
GTC. The ARM of [E1H3] next will attempt to transmit another ARREQ,
but this time a mapping will be obtained at the BARM'S GTC, and the
appropriate REPLY will be returned.
Part 1 has described the state of the art of the behaviour of Address
Resolution. Part 2 now extends the study to the more serious problem
of rebooting hosts in a multi-LAN system of Ethernets, and the
effects such changes have on the integrity of state information held
in ARP caches and routing tables.
PART 2
THE CAPTURE OF REBOOTS
Because Address Resolution packets are broadcast, all hosts on the
connecting cable including the Transparent Bridge will pick them up
and determine what they are. Referring to figure 1, it may well be
the case that a host on E1 wishes to communicate with a fellow host
on the same physical ether. Hence, if Hx wishes to talk to Hw on the
same ether, but has not done so previously, it will broadcast an
Address Resolution packet in the normal fashion. The Bridge will
also 'see' the packet as it passes by, and will act as described
above, unless that is, there is some method of preventing it doing
so; there is no point in the Bridge invoking its ARM, and wasting
processing time if the problem is going to be resolved locally.
It may occur however, that H1 wants to communicate with H5. If
however, H5 has not talked with anyone before (i.e., it has been
"dormant"), H1 will issue an ARREQ. The Bridge will not know that H5
is local because it won't have been entered in the local address
cache from previous conversations. To avoid broadcasting an ARREQ to
all networks/subnets, one way around this problem is to set up the
contents of the local cache at Bridge startup time. Therefore, the
Parr [Page 8]
RFC 1029 Fault Tolerant ARP for Multi-LANs May 1988
Bridge will already know not to intervene. Thus, if the Bridge (with
2 nets) finds that a particular IP destination address is not in the
local cache of interface 1, it would have to examine its GTC and scan
it for a mapping. Should no mapping be obtained at interface 2, one
of two possibilities exist:
1. the target host doesn't exist locally
2. the caches are corrupt (the eventuality of this should
be negligible!)
If it is assumed that each of the translation caches contains have
the most recent addressing information regarding its own domain of
the network then, in this example, if the Bridge does not get a
mapping at the GTC it would appear that the host must exist remotely
from E1, and E2.
Such a conclusion would ignore cases in which a host unplugs from a
particular hardware interface and plugs into another hardware
interface, or where logical names are reassigned to different
interfaces due to host user change. Either of these events could
happen had the host being accessed on E2, which would mean that a
REBOOT has taken place.
Anticipating these possiblities local caches are essential. In
normal operation, the Bridge will process and forward IP packets
received from one network, and destined for another. If the Bridge
picks up an ARREQ, it will first look for a mapping in its GTC before
discarding the original ARREQ, and transmitting its own to the remote
network. In any case, the Bridge will always examine the local cache
entries at the receiving interface, so that it may determine if the
target address is local or remote. When the Bridge first scans the
local cache, it does so with the source IP address as the key. If no
mapping is retrieved, it then scans the GTC with the same key.
Should a mapping now be obtained, it remains for the Bridge to insert
the source IP into the local cache, where it has either been
previously deleted or corrupted.
However, if the source IP exists in the respective local cache, the
validity of the source Ethernet address should also be verified by
examining the respective entry in the GTC. A scan of the GTC is then
performed with <protocol,source_prot_addr> as the key. If a mapping
is retrieved, the respective <et_addr> should be checked against the
source Ethernet address in the packet header. If the addresses do
not match, then we have uncovered a Hardware Reboot condition (i.e.,
a change in Ethernet ID). On the other hand, should the scan of the
GTC with <protocol,source_prot_addr> fail to obtain a mapping, then
the Bridge would scan the GTC with the current Ethernet address in
Parr [Page 9]
RFC 1029 Fault Tolerant ARP for Multi-LANs May 1988
the packet header. If this obtains a mapping, then a Protocol Reboot
condition (i.e., change in logical ID) has been detected.
In the next section, the implications of these forms of 'Reboot' are
discussed.
REBOOT SCENARIO
In normal operation, packets will uneventfully traverse each subnet
either as complete Internet packets, broadcast ARREQ's, or direct
ARREP's. The Bridge attached to each subnet will 'hear', and 'see'
all packets as they travel past its connected interfaces. Because of
the existence of the local caches at each interface, the Bridge can
decide whether or not to intervene. In general circumstances, each
host on the Catenet will have a translation cache containing
<protocol,source_prot_addr,source_et_addr> entries for all packets it
has observed. Most of these entries will have been due to processing
ARREQ packets, which were broadcast, and by receiving REPLY packets.
In accordance with the foregoing , the Bridge will have a cache
attached to each subnet interface containing entries for protocol
addresses.
Within the Bridge's Global Translation Cache (GTC) will be entries of
all <protocol,source_prot_addr,source_hrd_addr> triplets relating to
valid hosts which have been recognised. If we assume that we have
just connected up a Catenet such as that illustrated in figure 1,
then at power-up no stations will have knowledge about their
neighbours. If the Bridges are to remain transparent, the
translation caches at each host will be totally empty. The only
addressing details that will be in existence will be the protocol
addresses stored in the local caches of the Bridges.
The hosts subsequently begin to run applications and will want to
communicate with one another. The first ARREQ is broadcast on the
respective subnet and all hosts, including the Bridge's interface to
the subnet, will pick it up and store the details. If, for example,
Hx issues an ARREQ for Hq, the Bridge will not intervene since there
is no need (providing no reboot has occurred at Hq). However, if Hx
wishes to talk with Hz, B1 will determine that the target IP in the
respective ARREQ does not exist in the local cache of IFE1, so it
will examine the GTC, with the <protocol,target_prot_addr> of Hw as
the key.
It is assumed that there will be a timeout mechanism in operation at
the source of any packet. In addition, the Bridge may also place the
target address in a 'search list' of currently sought hosts, so as to
prevent ARREQs from different sources being cascaded for the same
target. Under these conditions, Hx may re-issue its original ARREQ,
Parr [Page 10]
RFC 1029 Fault Tolerant ARP for Multi-LANs May 1988
but will be ignored until the host Hw has replied to the ARREQ
transmitted by the Bridge.
NORMAL RUNNING STATE
Assuming that a few ARP's have been issued, IP packets will start
traversing the Catenet with full addressing information. Again, the
Bridges will 'see' all the packets. If we extend the situation one
step further, and assume that several conversations have taken place
across the Catenet, there will be entries in the translation caches
of the hosts concerned, regarding the
<protocol,target_prot_addr,target_hrd_addr> triplets of those hosts
with which the conversations took place. The Bridges also, will have
details in their GTC's for packets which they cascaded.
If a host is relocated, any connections initiated by that host will
still work, provided that its own translation cache is cleared when
it does physically move. However, any connections subsequently
initiated to it by other hosts on the Catenet will have no particular
reason to know to discard their old translation for that host.
Ideally, 48 bit Ethernet addresses will be unique and fixed for all
time.
RECOGNITION OF THESE REBOOT CONDITIONS
With reference to figure 1, assume that for some reason a fault
occurs on the hardware interface of <E1He>. The result of this is
that a new interface is installed with a newly acquired hardware
address. When <E1He> is powered up, the previous contents of its
translation cache are cleared and it has no recollection of local, or
remote host addresses. Accordingly, <E1He> begins to issue ARREQ's
to hosts it requires. Whenever <E1He> transmits its first ARREQ, it
could be termed a 'HELLO PACKET', since everyone on the subnet can
pick up the packet, and store the relevant information in their
translation caches. Within hosts, a mapping will be found on the old
<protocol,source_prot_addr> pair, and the current <et_addr> of the
packet header will replace whatever is entered in the translation
cache.
At this point it would be easy for each host with an entry to
recognise the Hardware Reboot situation and inform the subnet with a
respective broadcast reboot packet. But allowing such a procedure
would be extremly inefficient on the broadcast medium, and would
drastically outweigh any improvements in performance which might be
obtained in the long term. In any case, given the fact that the
ARREQ is broadcast, all stations on the subnet will recognise the
reboot. The important point to consider is the effect such a reboot
will have on subsequent conversations which are initiated remotely.
Parr [Page 11]
RFC 1029 Fault Tolerant ARP for Multi-LANs May 1988
Can redundant transmissions be thwarted before they tie up processing
time on hosts en-route to the rebooted target? How these
difficulties are resolved is critical to the level of performance
obtained in a Catenet configuration. Since it is not optimal for
hosts to inform the system of a reboot, it is left to the Bridge.
Whenever the Bridge receives a packet, be it IP, or ARP, it examines
the source address parameters in the packet header, in the hope of
detecting any incompatibilities between them and the entries in its
caches. There are three distinct possibilities, namely, a difference
in the 48 bit hardware address only, a difference in the protocol
address, and two completely new addresses. If an incompatibility is
discovered, a "REBOOT" packet is constructed and issued on all remote
interfaces containing the appropiate information, allowing Bridges to
update their GTC's and generic hosts their ARP caches.
The structure of the Reboot packet is as depicted in figure 2.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| P A C K E T O P C O D E |REB OPC| S O U R C E |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| H A R D W A R E A D D R E S S |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| S O U R C E P R O T O C O L A D D R E S S |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| M U L T I C A S T T A R G E T H A R D W A R E |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| A D D R E S S | M U L T I C A S T T A R G E T |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| P R O T O C O L |
+-+-+-+-+-+-+-+-+-+-+-+-+
---------> NEXT FOLLOWS A VARIANT FIELD ON REBOOT OPCODE
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| O L D S O U R C E H A R D W A R E |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| A D D R E S S |
+-+-+-+-+-+-+-+-+-+-+-+-+
OR
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| O L D S O U R C E P R O T O C O L A D D R E S S |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
FIGURE 2. REBOOT PACKET
Parr [Page 12]
RFC 1029 Fault Tolerant ARP for Multi-LANs May 1988
The following definitions apply:
PACKET FIELD VALUE
OPCODE REBOOT
REBOOT OPCODE HARDWARE
REBOOT OPCODE PROTOCOL
The format is then as follows:
48 bit broadcast Ethernet address for the destination,
48 bit Ethernet address of source Bridge,
16 bit Protocol type = PACKET OPCODE - REBOOT.
For completeness and error checking it may be an advantage to have a
field which specifies the length of addresses in the Ethernet and
protocol address spaces. Thus, the Reboot packet structure contains
the following:
FIELD FIELD SIZE DESCRIPTION
HRDLEN 4 bit byte length of Ethernet address
PROTLEN 4 bit byte length of Protocol address
SOURCE
PROTOCOL
ADDRESS 32 bit current protocol address of host
TARGET
PROTOCOL
ADDRESS 32 bit broadcast target protocol address
REBOOT
OPCODE 4 bit will be either PROTOCOL or HARDWARE
if PROTOCOL 32 bit old protocol address
else HARDWARE 48 bit old hardware address
Parr [Page 13]
RFC 1029 Fault Tolerant ARP for Multi-LANs May 1988
As shown, depending on the REBOOT-OPCODE, the structure will continue
with either the 48 bit old hardware address or the 32 bit old
protocol address. The choice of a variant packet structure is for
reasons of curtailing the size of the packet to the fields that are
truely necessary in each situation. From this Reboot packet
structure, the process of generating such a packet can be considered.
When the Bridge algorithm detects a reboot, it should create a reboot
packet structure containing the relevant addressing information and
subsequently multicast it on the interface(s) which access(es) the
remote subnet(s). The decision as to which interface(s) is/are
local, and which is/are remote, can be resolved automatically
whenever a packet is received. With respect to this packet transfer
the receive interface at the Bridge becomes local, and all others are
tagged as remote.
Thus, hosts on the subnet remote from the reboot are informed of the
situation immediately as it is detected by the Bridge. In the
Catenet configuration illustrated in fig 1, this will have the effect
of updating the Translation Cache within each host, whenever it
receives the packet. If for example, <E4Hw> reboots under hardware,
B3 will detect this occurance. There is no reason for the subnets
E1, E2, E3 to be aware of this episode. In normal operation, B3 will
recognise the reboot from the first ARREQ issued from <E4Hw>. With
this reboot detection facility, B3 will be in a position to inform
the hosts on E1, E2, and E3. B3 can then create and issue the Reboot
packet via its interface with E3. When B3 picks it up, it will
update its own caches and subsequently cascade the packet onto E2,
where it will be passed on to E1 via B1.
ARGUMENTS FOR REBOOT PACKETS
It is envisaged that introducing Reboot packets, will serve to
enhance the bandwidth achievable within a Catenet system. Problems
of addressing 'dead' hosts will no longer exist in a correctly
functioning configuration. Translation Caches will have on hand the
most recent addressing information available, which should also serve
to enhance the performance of the routing strategy in operation.
Multiple, redundant processing of packets destined for 'dead' hosts
will be avoided. Weighing this against the processing involved with
a single multicast of Reboot packets, it is expected that the latter
will be is the most economically viable in relation to the long-term
traffic presented to the system.
CONCLUSION
It appears that reboots are becoming increasingly common on internet
networks. Many sites use Personal Computers (PC) as terminals and
the typical way to finish a session is to switch them off! With the
Parr [Page 14]
RFC 1029 Fault Tolerant ARP for Multi-LANs May 1988
increasing popularity of multitasking Operating Systems on these
types of machines, problems are more likely to occur, particularly
when the PCs are diskless, or participating in a distributed file
system of some kind. Given the importance of correct addressing in
communications networks running Ethernet, it is anticipated the
reboot mechanism described will serve to improve the correctness and
validity of the protocol/network address mappings which may be stored
in the translation caches. To this degree, simulation is expected to
show that the volume of invalid traffic will decrease, to the benefit
of hosts, Bridges and servers alike. Likewise, ratification of the
routing policy is anticipated and since redundant/obsolete packets
will be thwarted, the efficient utilization of available channel
bandwidth across the catenet is also expected to improve. Thus,
effectively increasing Catenet throughput for 'valid' packets, and
therefore enhancing the level of service provided to the end users.
It is obvious that the proposed scheme implies the alteration of the
packet processing code in Bridges/Gateways. The point to remember is
the increased favour with which larger, more complex Multi-LAN
systems of Ethernets are being received. The recent adaption of
extra telephone cables to serve as the transmission media for the
Ethernet can only result in installation costs being reduced, therein
making the Ethernet more attractive within large corporate buildings,
etc. It is sensible to suggest that the probability of host address
re-assignment shall increase in proportion to the number of physical
systems attached, component failure rate (for whatever reason),
relocation of resources, and the size and turnover of the workforce
(i.e., people moving from one room to another). Simulation
experiments are currently being developed to analyse the resultant
traffic patterns under this scheme, and it is hoped to highlight
thresholds where adoption of the scheme becomes a necessity.
In addition, the Author is currently extending the boundaries of this
problem to encompass the reboot, or relocation of Bridges themselves.
Involved with this are the phenomena of loop resolution, load sharing
and duplicate packet suppression. It is envisaged that a Self-
Stabilizationg Bridge Protocol will result that will be more "light-
weight" than those adhering to the Spanning Tree Algorithm.
The Author would appreciate feedback/comments on this RFC. My
network address is: CBAD13%UCVAX.ULSTER.AC.UK@CUNYVM.CUNY.EDU.
ACKNOWLEDGEMENTS
The Author acknowledges with gratitute the help and comments
contributed by Mr. Piotr Bielkowitz (Supervisor) of the Computing
Science Department, and the time devoted my Mr. Raymond Robinson for
painstakingly preparing the first draft of this paper on 'Pagemaker'.
Parr [Page 15]
RFC 1029 Fault Tolerant ARP for Multi-LANs May 1988
Thanks are due also to Dr. M. W. A. Smith of Information Systems for
his assistance. Finally, this work was supported under a grant from
the Department of Education for Northern Ireland of which the Author
is extremely grateful.
REFERENCES
[1] Croft, Bill, and John Gilmore, "Bootstrap Protocol", RFC-951,
Stanford University, September 1985.
[2] Finlayson, Mann, Mogul, and Theimer, "A Reverse Address
Resolution Protocol", RFC-903, Computer Science Dept, Stanford
University, June 1984.
[3] Lorimer, Alan, and Jim Reid, "ARP Information Communique",
Computer Science Dept, Strathclyde University, 1987.
[4] Mogul, Jeffrey, "Internet Subnets", RFC-917, Computer Science
Dept, Stanford University, October 1984.
[5] Plummer, David, "An Ethernet Address Resolution Protocol", RFC-
826, MIT, November 1982.
[6] Postel, Jon, "DARPA Internet Program Protocol Specification",
RFC-791, USC/Information Sciences Institute, September 1981.
[7] Postel, Jon, "Multi-LAN Address Resolution", RFC-925,
USC/Information Sciences Institute, October 1984.
[8] Postel, Jon, Carl Sunshine, and Danny Cohen, "The ARPA Internet
Protocol", Computer Networks, no. 5, pp. 261-271, 1981.
[9] Postel, Jon, and Jeff Mogul, "Internet Standard Subnetting
Procedure", RFC-950, USC/Information Sciences Institute and
Stanford University, August 1985.
[10] Reynolds, Joyce, and Jon Postel, "Assigned Numbers", RFC-1010,
USC/Information Sciences Institute, May 1987.
[11] "The Ethernet: a local area network, data link layer and
physical layer specification", Version 1.0 DEC, Intel and Xerox
Corporations, USA 30 September 1980).
[12] Hughes, H.D., and L. Li, "Simulation model of an Ethernet",
Computer Performance, Vol 3, no. 4, December 1982.
[13] Parr, Gerald P., "Address Resolution For An Intelligent
Filtering Bridge Running On A Subnetted Ethernet System", ACM
Parr [Page 16]
RFC 1029 Fault Tolerant ARP for Multi-LANs May 1988
SIGCOMM Computer Communication Review, (July/August 1987), vol.
17, no. 3.
[14] Smoot, Carl-Mitchell, and John S. Quarterman, "Using ARP to
Implement Transparent Subnet Gateways", RFC-1027, Texas Internet
Consulting, October 1987.
Parr [Page 17]
|