jain@erlang.DEC.COM (Raj Jain, DEC, 550 King St., Littleton, MA 01460) (05/06/89)
The following three DEC technical reports are now available for
distribution.
DEC-TR-566: `A Delay-Based Approach for Congestion Avoidance in
Interconnected Heterogeneous Computer Networks,' 16 pages.
DEC-TR-592: `Characteristics of Destination Address Locality in Computer
Networks: A Comparison of Caching Schemes,' 14 pages.
DEC-TR-593: `A Comparison of Hashing Schemes for Address Lookup in Computer
Networks,' 15 pages.
If you would like to receive a copy, please send me a message with subject
field containing the word DEC-TR along with the report numbers you want.
The message should be simply your US (or foreign) Mail address such that it
can be used directly on a mailing label. Any other words or sentences in
the message will simply delay the delivery.
Softcopies in Postscript are also available but they seem to print only on
LPS40 printers. To receive softcopies include the word LPS40 in the
subject field. Please include your US Mailing address anyway. In case of
network problems, hard copies will be mailed.
Thanks.
Raj Jain
Digital Equipment Corp.
550 King St. (LKG1-2/A19)
Littleton, MA 01460
Detailed abstracts of the reports are as follows:
DEC-TR-566
A Delay-Based Approach for Congestion Avoidance in
Interconnected Heterogeneous Computer Networks
by Raj Jain
In heterogeneous networks, achieving congestion avoidance is difficult
because the congestion feedback from one subnetwork may have no meaning to
sources on other subnetworks. We propose using changes in round-trip delay
as an implicit feedback. Using a black-box model of the network, we derive
an expression for the optimal window as a function of the gradient of the
delay-window curve.
The problems of selfish optimum and social optimum are also addressed. It
is shown that without a careful design, it is possible to get into a race
condition during heavy congestion, where each user wants more resources
than others, thereby leading to a diverging condition.
It is shown that congestion avoidance using round-trip delay is a promising
approach. The approach has the advantage that there is absolutely no
overhead for the network itself. It is exemplified by a simple scheme.
The performance of the scheme is analyzed using a simulation model. The
scheme is shown to be efficient, fair, convergent, and adaptive to changes
in network configuration.
The scheme as described works only for networks which can be modeled with
queueing servers with constant service times. Further research is required
to extend it for implementation in practical networks. Several directions
for future research have been suggested.
DEC-TR-592
Characteristics of Destination Address Locality in Computer Networks:
A Comparison of Caching Schemes
by Raj Jain
The size of computer networks, along with their bandwidths, is growing
exponentially. To support these large, high-speed networks, it is
necessary to be able to forward packets in a few microseconds. One part of
the forwarding operation consists of searching through a large address
database. This problem is encountered in the design of adapters, bridges,
routers, gateways, and name servers.
Caching can reduce the lookup time if there is a locality in the address
reference pattern. Using a destination reference trace measured on an
extended local area network, we attempt to see if the destination
references do have a significant locality.
We compared the performance of MIN, LRU, FIFO, and random cache replacement
algorithms and found that the interactive (terminal) traffic in our sample
had quite different locality behavior than that of the noninteractive
traffic. The interactive traffic did not follow the LRU stack model while
the noninteractive traffic did. Examples are shown of the environments in
which caching can help as well as those in which caching can hurt, unless
the cache size is large.
DEC-TR-593
A Comparison of Hashing Schemes for Address Lookup
in Computer Networks
by Raj Jain
The trend toward networks becoming larger and faster, and addresses
increasing in size, has impelled a need to explore alternatives for fast
address recognition. Hashing is one such alternative which can help
minimize the address search time in adapters, bridges, routers, gateways,
and name servers.
Using a trace of address references, we compared the efficiency of several
different hashing functions and found that the cyclic redundancy checking
(CRC) polynomials provide excellent hashing functions. For software
implementation, Fletcher checksum provides a good hashing function.
Straightforward folding of address octets using the exclusive-or operation
is also a good hashing function. For some applications, bit extraction
from the address can be used.