value of the offender's TSAP. Any member that exhibits a detectable
and recoverable protocol violation and still responds willingly to
the quit[request] will be noted as having truly correct social
behavior.
0 7 8 15 16 23 24 31
---------------------------------------------------------- -----
| protocol | packet | type | client | |
| version | type | modifier | channel | |
---------------------------------------------------------- |
| | |
| source connection identifier | |
---------------------------------------------------------- |
| | |
| destination connection identifier |
---------------------------------------------------------- transport
| | header
| message acceptance criteria |
---------------------------------------------------------- |
| | |
| heartbeat | |
---------------------------------------------------------- |
| | | |
| window | retention | |
---------------------------------------------------------- -----
| |
| target TSAP |
| |
----------------------------------------------------------
Figure 11. quit packet
3.3 Terminating the transport
Transport termination is an advisory process that may be initiated by
any member of the web. No process should intentionally quit the web
while it has retransmittable data buffered. Stations should make
every reasonable attempt advise the master of their intentions to
withdraw, as their departure may collapse the topology of the web and
eliminate the need to carry multicast messages across network
boundaries.
3.3.1. Voluntary quits
Voluntary quit[requests] are unicast to the master's TSAP. When the
master receives a quit from a member of the web, it responds with a
quit[confirm] packet. At that time the member will be formally
removed from the web. The request should be retransmitted at
heartbeat intervals until the confirmation is received from the
master or as many times as the web's value of retention.
3.3.2. Master quit
If the master initiates the transport termination it effects all
members of the web. The master will retain all transmit tokens and
refuse to assign them. Once the tokens are acquired, the master will
multicast a quit[request] to the entire web. That request should be
acknowledged by every active member. When the master receives no
confirmations for retention transmissions, it may assume every member
has terminated its transport and then may follow suit.
3.3.3. Banishment
If the master receives any message other than a join[request] from a
member that it does not recognize, it should transmit a quit[request]
with that process as a target. This covers cases where the consumer
did not see the termination reply and retransmitted its original quit
request, as well as unannounced and rejected consumers.
3.4 Transport parameters
The following section provides guidelines and rationale for selecting
reasonable transport quality of service parameters. It also describes
some of the reasoning behind the ranges of values presented.
3.4.1. Quality of service
Active members of the web may suggest changes in the transport's
quality of service parameters during the lifetime of the transport.
Producers in general adjust the transport's parameters to encourage a
higher level of throughput. Since consumers are responsible for
certifying reliable delivery, it is expected that they will provide
the force encouraging more reliability and stability. Both are trying
to optimize the quality of service. The negotiation that took place
when members joined the web included the clients' desires with
regards to the worst case behavior that will be tolerated. If a
member cannot maintain the negotiated lower bound, it may asked to
withdraw from the web. That process will be sent a unicast message
(quit[request]) indicating that it should retire. There are
essentially three parameters maintained by the transport that reflect
the client's quality of service requirements: heartbeat, window and
retention. These three parameters can be adapted by the transport to
reflect the capability of the members, the type of application being
supported and the network topology. When members join the web, they
suggest values for the quality of service parameters to the master.
If the parameters are acceptable, the master will respond with the
web's current operating values. During the lifetime of the web, it is
expected that the parameters be modified by its members, though they
may never result in a quality of service less than the lower bounds
established by the joining procedure. Producers may try to improve
performance by reducing the heartbeat interval and increasing the
window size. This will have the effect of increasing the resources
committed to the transport at any time. In order to keep the
resources under control, the producer may also reduce the retention.
Consumers must rely on their clients to consume the data occupying
the resources of the transport. To do so the consumer transport
implementation must monitor the level of committed resources to
insure that it does not exceed its capabilities. Since MTP is a NAK
based protocol, the consumer is required to tell the producer if a
change in parameters is required. The new information must be
delivered to the producer(s) before the consumer's resource situation
becomes critical in order to avoid missing data.
For more stable operation, consumers would try to extend the
heartbeat interval and reduce the window. To a certain degree, they
could also attempt to reduce the value of retention in order to
reduce the amount of resources required to support the transport.
However, that requires a more stringent real-time capability.
3.4.2. Selecting parameter values
The value of heartbeat is approximately the transport time constant.
Assuming that the transport can be modelled as a closed loop system
function, reaction to feedback into the transport should settle out
in three time constants. In a transport that is constrained to a
single network, the dominant cause of processing delay of the
transport will most likely be page fault resolution time.
For example, using a one MIP processor on a ethernet and an industry
standard disk, the worst case page fault resolution requiring two
seeks (one to write out a dirty page, another to swap in the new
page) and an average seek time of 40 milliseconds, page fault
resolution should be less than 80 milliseconds. Allowing for some
additional overhead and scheduling delays, two times the worst case
page fault resolution time would appear to be the minimum suitable
transport time constant one could expect. So,
Heartbeat (minimum) = 160 - 200 milliseconds.
The transmit time for a full (ethernet) packet is approximately 1.2
milliseconds. Processing time should be less than 3 milliseconds
(ignoring possible overlapped processing). Assuming disk access (with
no faulting) is equivalent, and the total time per packet is the sum
of the parts, or 8.4 milliseconds. Therefore, the theoretical maximum
value would be approximately 17 packets per heartbeat. The transport
should be capable of approximately 120 packets per second, or 19.2
packets per heartbeat.
Window (maximum) = 17 - 20 packets per heartbeat.
The (theoretical) throughput with these parameters in effect is 180
kilobytes per second.
Reducing retention may introduce instability because the consumers
will have less opportunity to react to missing data. Data can be
missed for a variety of reasons. If constrained to the local net the
data lost due to data link corruption should be in the neighborhood
of one packet in every 50,000 (bit error rate of approximately 10-9).
Telephony links (between routers, for instance) exhibit similar
characteristics. Several orders of magnitude more packets are lost at
receiving processes, including packet switch routers, than over the
physical links. The losses are usually a result of congestion and
resource starvation at lower layers due to the processing of (nearly)
back to back packets. The incidental packet loss of this type is
virtually unavoidable. One can only require that a receiving process
be capable of receiving some number of back to back packets
successfully, and that number must be at least greater then the value
of window. And beyond that the probability of success can be made as
close to unity as required by providing the receiver the opportunity
to observe the data multiple times.
The receiving process must detect packet loss. The simplest method is
to notice gaps in the received message/packet sequence numbers. Such
detection should be done after receiving an end of window or other
state transition indication. As such, the naks cannot be transmitted,
let alone received, until the following heartbeat. In order to not
have any single packet loss cause transport failure, the naks should
have the opportunity to be transmitted at least twice.
When the loss is detected, the nak must be transmitted and should be
received at the producing process in less than two heartbeats after
the data it references was transmitted. Again, it is the detection
time that dominates, not the transmission of the nak.
Retention (minimum) = 3.
The resources committed to a producing transport using the above
assumptions are buffers sufficient for 80 packets of 1500 bytes each.
Each buffer will be committed for 600 - 800 milliseconds.
Transports that span multiple networks have unique problems. One such
problem is that if a router drops a packet, all the processes on the
remote network may attempt to send a nak[request] at the same time.
That is not likely to enhance the router's quality of service.
Furthermore, it is obvious that any one nak[request] will suffice to
prompt the producer to retransmit the desired packet. To reduce the
number of nak[requests] in this situation, the following scheme might
be employed.
First, extend the value of retention to a minimum value of N. Then
use a randomizing function that returns a value between zero and N -
2, choose how many heartbeat intervals to dally before sending the
nak[request], thus spreading out the transmissions over time. In
order for the method to be meaningful, the minimum value of retention
must be adjusted.
Retention (minimum) = 5 (for internet cases)
3.4.3. Caching member information
In order to reduce transport member interaction and to enhance
performance, a certain amount of caching should be employed by
producing members. These caches may be filled by gleaning information
from reliable sources such as multicast data or, when all else fails,
from responses solicited from the web's master by use of the
isMember[request]. IsMember[request] requests are unicast to a member
that is believed to have an accurate state of the web, at least to
the degree that it can answer the question posed. The destination of
such a message is usually the master. But in cases where a process
(such as the master) wants to verify that a process believes itself
to be valid, it can assign the target TSAP and the destination to be
the same. It is assumed that every process can verify itself.
If the member receiving the isMember[request] can confirm the
target's active membership status in the web, it responds with a
unicast isMember[confirm]. The data field contains the credibility
value of the confirmation, that is the time (in milliseconds) since
the information was confirmed from a reliable source.
Caches are risky as the information stored in them can become stale.
Consequently, with only a few exceptions, the entries should be aged,
and when sufficiently old, discarded. Ideally they may be renewed by
the same gleanable sources alluded to in the previous paragraph. If
not, they are simply discarded and refilled when needed.
Web membership may be gleaned from any packet that does not have a
value of unknown as the destination connection identifier. A
producing transport may extract the TSAP from such packets and either
create or refresh local caches. Then, if in the process of
transmitting and NAK is received from one of the members whose
identity is cached, no explicit request will be needed to verify the
source's membership.
The explicit source of membership information is the master.
Information can be requested by using the isMember message.
Information gathered in that manner should be treated the same as
gleaned information with respect to aging.
The aging is a function of the transport's time constant, or
heartbeat, and the retention. Information about a producing member
must be cached at least as long as that producer has incomplete
messages. It may be cached longer. The namespace for both sequence
numbers and connection identifiers is intentionally long to insure
that reuse of those namespaces will not likely collide.
A. Appendix: MTP as an Internet Protocol transport
MTP is a transport layer protocol, designed to be layered on top of a
number of different network layer protocols. Such a protocol must
provide certain facilities that MTP expects. In particular, the
underlying network level protocol must provide "ports" or "sockets"
to facilitate addressing of processes within a machine, and a
mechanism for multicast addressing of datagrams. These two
addressing facilities are also used to formulate the NSAP for MTP on
IP.
A.1 Internet Protocol multicast addressing
MTP on Internet Protocol uses the Internet Protocol multicast
mechanisms defined in RFC1112, "Host Extensions for IP
Multicasting". MTP requires "Level 2" conformance described in that
paper, for hosts which need to both send and receive multicast
packets, both on the local net and on an internet. MTP on Internet
Protocol uses the permanent host group address 224.0.1.9.
A.2 Encapsulation
The Internet Protocol does not provide a port mechanism - ports are
defined at the transport level instead. In order to encapsulate MTP
packet within Internet Protocol packets, a simple convergence or
"bridge" protocol must be defined to run on top of Internet Protocol,
which will provide MTP with the mechanism needed to deliver packets
to the proper processes. We will call this protocol the
"MTP/Internet Protocol Bridge Protocol", or just "Bridge". The
protocol header is encapsulated the Internet Protocol data - the
protocol field of the Internet Protocol packet carries the value
indicating this packet is an MTP packet (92 decimal). The MTP packet
itself is encapsulated in the Bridge data. Figure A.1 shows the
positions of the fields within the MTP packet while table A.1 defines
the contents of those fields.
A.3 Fields of the bridge protocol
0 7 8 15 16 23 24 31
----------------------------------------------------------
| | |
| destination port | source port |
----------------------------------------------------------
| | |
| length | checksum |
----------------------------------------------------------
| |
| client data |
----------------------------------------------------------
Figure A.1 MTP bridge protocol header fields
destination port The port to which the packet is destined or sinked.
source port The port from which the packet originates or is sourced.
length The length in octets of the bridged packet, including
header and all data (the MTP packet). The minimum value
in this field is 8, the maximum is 65535. The length
does not include any padding bytes that were used to
compute the checksum. Note that though this field allows
for very long packets, most networks have significantly
shorter maximum frame sizes - the allowable and optimal
packet size must be determined by means beyond the scope
of this specification.
checksum The 16 bit one's compliment of the one's compliment sum
of the entire bridge protocol header and data, padded
with a zero octet (if necessary) to make multiple 16 bit
quanities. A computed checksum of all zeros should be
changed to all ones. The checksum field is optional -
all zeros in the field indicate that checksums are not in
use.
data The data field is the field that carries the actual
transport data. A single MTP packet will be carried the
data field of each bridge packet.
A.4 Relationship to other Internet Protocol Transports
The astute reader might note that the MTP/Bridge Protocol looks much
like the User Datagram Protocol (UDP). UDP itself was not used
because the protocol field in the Internet Protocol packet should
reflect the fact that the higher level protocol of interest is MTP.
References
AFM91 Armstrong, S., A. Freier and K. Marzullo, "MTP: An Atomic
Multicast Transport Protocol", Xerox Webster Research Center
technical report X9100359, March 1991.
Bog83 Boggs, D., "Internet Broadcasting", Xerox PARC technical
report CSL-83-3, October 1983.
BSTM79 Boggs, D., J. Shoch, E. Taft, and R. Metcalfe, "Pup: An
Internetwork Architecture", IEEE Transactions on
Communications, COM-28(4), pages 612-624. April 1980.
DIX82 Digital Equipment Corp., Intel Corp., Xerox Corp., "The
Ethernet, a Local Area Network: Data Link and Physical Layer
Specifications", September 1982.
CLZ87 Clark, D., M. Lambert, and L. Zhang, "NETBLT: A high
throughput transport protocol", In Proceedings of ACM SIGCOMM
'87 Workshop, pages 353-359, 1987.
CM87 Chang J., and M. Maxemchuck. "Atomic broadcast", ACM
Transactions on Computer Systems, 2(3):251-273, August 1987.
Cri88 Cristian, F., "Reaching agreement on processor group
membership in synchronous distributed systems", In
Proceedings of the 18th International Conference on Fault-
Tolerant Computing. IEEE TOCS, 1988.
Dee89 Deering, S., "Host Extensions for IP Multicasting", RFC1112,
Stanford University, August 1989.
Fre84 Freier, A., "Compatability and interoperability", Open letter
to XNS Interest Group, Xerox Systems Developement Division,
December 13, 1984.
JB89 Joseph T., and K. Birman, "Reliable Broadcast Protocols",
pages 294-318, ACM Press, New York, 1989.
Pos81 Postel, J., "Transmission Control Protocol - DARPA Internet
Program Protocol Specification", RFC793, DARPA, September
1981.
Xer81 Xerox Corp., "Internet Transport Protocols", Xerox System
Integration Standard 028112, Stamford, Connecticut. December
1981.
Footnotes
[1] The network layer is not specified by MTP. One of the goals is to
specify a transport that can be implemented with equal functionality
on many network architectures.
[2] There's only one such multicast connection identifier per web. If
there are multiple processes on the same machine participating in a
web, the transport must descriminate between those processes by using
the connnection identifier.
[3] Determining the network service access point (NSAP) for a given
instantiation of a web is not addressed by this protocol. This
document may define some policy, but the actual means are left for
other mechanisms.
[4] Best effort delivery is also known as highly reliable delivery.
It is somewhat unique that the qualifying adjective highly weakens
the definition of reliable in this context.
[5] The resource being flow controlled is packets carrying client
data. Consequently, full data units provide the greatest efficiency.
[6] There seems to be an opportunity to suppress retransmissions to
networks that were not represented in the set of naks received.
Security Considerations
Security issues are not discussed in this memo.
Authors' Addresses
Susan M. Armstrong
Xerox Webster Research Center
800 Phillips Rd. MS 128-27E
Webster, NY 14580
Phone: (716) 422-6437
EMail: armstrong@wrc.xerox.com
Alan O. Freier
Apple Computer, Inc.
20525 Mariani Ave. MS 3-PK
Cupertino, CA 95014
Phone: (408) 974-9196
EMail: freier@apple.com
Keith A. Marzullo
Cornell University
Department of Computer Science
Upson Hall
Ithaca, NY 14853-7501
Phone: (607) 255-9188
EMail: marzullo@cs.cornell.edu
Keith Marzullo is supported in part by the Defense Advanced
Research Projects Agency (DoD) under NASA Ames grant number NAG
2-593, Contract N00140-87-C-8904. The views, opinions and
findings contained in this report are those of the authors and
should not be construed as an official Department of Defense
position, policy, or decision.