| | | | | |
| 3 requests | 4 | 3 | 4 | 3 |
This means that the CPU is allocated to T1 29% ( 4/14 ) of the
available time, whereas D1 obtains service 14% ( 1/7 ) of the time,
assuming processing requirements for all service requests to be
equal. Now assume that, on average, there is a service request
arriving for one out of three of the service requirement type D
connections. The CPU is then allocated to the T type 40% ( 4/10 )
while the D type is allocated 10% ( 1/10 ).
4.2 Buffer management.
Buffers are used as temporary storage areas for data on its way to
or arriving from the network. Decisions must be made about buffer
management in two areas. The first is the overall strategy for
managing buffers in a multi-layered protocol environment. The
second is specifically how to allocate buffers within the
transport entity.
In the formal description no details of buffer strategy are given,
since such strategy depends so heavily on the implementation
environment. Only a general mechanism is discussed in the formal
description for allocating receive credit to a transport connection,
without any expression as to how this resource is managed.
Good buffer management should correlate to the traffic presented by
the applications using the transport service. This traffic has
implications as well for the performance of the protocol. At present,
the relationship of buffer strategy to optimal service for a given
traffic distribution is not well understood. Some work has been
done, however, and the reader is referred to the work of Jeffery
Spirn [SPI82, SPI83] and to the experiment plan for research by the
NBS [HEA85] on the effect of application traffic patterns on the
performance of Class 4 transport.
4.2.1 Overall buffer strategy.
Three schemes for management of buffers in a multilayered
environment are described here. These represent a spectrum of
possibilities available to the implementor. The first of these is a
strictly layered approach in which each entity in the protocol
hierarchy, as a process, manages its own pool of buffers
independently of entities at other layers. One advantage of this
approach is simplicity; it is not necessary for an entity to
coordinate buffer usage with a resource manager which is serving
the needs of numerous protocol entities. Another advantage is
modularity. The interface presented to entities in other layers is
well defined; protocol service requests and responses are passed
between layers by value (copying) versus by reference (pointer
copying). In particular, this is a strict interpretation of the OSI
reference model, IS 7498 [ISO84b], and the protocol entities hide
message details from each other, simplifying handling at the entity
interfaces.
The single disadvantage to a strictly layered scheme derives from
the value-passing nature of the interface. Each time protocol
data and control information is passed from one layer to another
it must be copied from one layer's buffers to those of another layer.
Copying between layers in a multi-layered environment is
expensive and imposes a severe penalty on the performance of the
communications system, as well as the computer system on which it is
running as a whole.
The second scheme for managing buffers among multiple protocol
layers is buffer sharing. In this approach, buffers are a
shared resource among multiple protocol entities; protocol data and
control information contained in the buffers is exchanged by passing
a buffer pointer, or reference, rather than the values as in the
strictly layered approach described above. The advantage to
passing buffers by reference is that only a small amount of
information, the buffer pointer, is copied from layer to layer.
The resulting performance is much better than that of the strictly
layered approach.
There are several requirements that must be met to implement
buffer sharing. First, the host system architecture must allow
memory sharing among protocol entities that are sharing the
buffers. This can be achieved in a variety of ways: multiple
protocol entities may be implemented as one process, all sharing
the same process space (e.g., kernel space), or the host system
architecture may allow processes to map portions of their address
space to common buffer areas at some known location in physical
memory.
A buffer manager is another requirement for implementing shared
buffers. The buffer manager has the responsibility of providing
buffers to protocol entities when needed from a list of free
buffers and recycling used buffers back into the free list. The
pool may consist of one or more lists, depending on the level of
control desired. For example, there could be separate lists of
buffers for outgoing and incoming messages.
The protocol entities must be implemented in such a way as to
cooperate with the buffer manager. While this appears to be an
obvious condition, it has important implications for the strategy
used by implementors to develop the communications system. This
cooperation can be described as follows: an entity at layer N
requests and is allocated a buffer by the manager; each such buffer
is returned to the manager by some entity at layer N - k (outgoing
data) or N + k (incoming data).
Protocol entities also must be designed to cooperate with each
other. As buffers are allocated and sent towards the network from
higher layers, allowance must be made for protocol control
information to be added at lower layers. This usually means
allocating oversized buffers to allow space for headers to be
prepended at lower layers. Similarly, as buffers move upward from
the network, each protocol entity processes its headers before
passing the buffer on. These manipulations can be handled by
managing pointers into the buffer header space.
In their pure forms, both strictly layered and shared buffer
schemes are not practical. In the former, there is a performance
penalty for copying buffers. On the other hand, it is not practical
to implement buffers that are shared by entities in all layers of the
protocol hierarchy: the lower protocol layers (OSI layers 1 - 4)
have essentially static buffer requirements, whereas the upper
protocol layers (OSI layers 5 - 7) tend to be dynamic in their buffer
requirements. That is, several different applications may be running
concurrently, with buffer requirements varying as the set of
applications varies. However, at the transport layer, this latter
variation is not visible and variations in buffer requirements will
depend more on service quality considerations than on the specific
nature of the applications being served. This suggests a hybrid
scheme in which the entities in OSI layers 1 - 4 share buffers while
the entities in each of the OSI layers 5 - 7 share in a buffer pool
associated with each layer. This approach provides most of the
efficiency of a pure shared buffer scheme and allows for simple,
modular interfaces where they are most appropriate.
4.2.2 Buffer management in the transport entity.
Buffers are allocated in the transport entity for two purposes:
sending and receiving data. For sending data, the decision of how
much buffer space to allocate is relatively simple; enough space
should be allocated for outgoing data to hold the maximum number of
data messages that the entity will have outstanding (i.e., sent but
unacknowledged) at any time. The send buffer space is determined by
one of two values, whichever is lower: the send credit received
from the receiving transport entity, or a maximum value imposed by
the local implementation, based on such factors as overall
buffer capacity.
The allocation of receive buffers is a more interesting problem
because it is directly related to the credit value transmitted the
peer transport entity in CR (or CC) and AK TPDUs. If the total
credit offered to the peer entity exceeds the total available buffer
space and credit reduction is not implemented, deadlock may
occur, causing termination of one or more transport connections. For
the purposes of this discussion, offered credit is assumed to be
equivalent to available buffer space.
The simplest scheme for receive buffer allocation is allocation of
a fixed amount per transport connection. This amount is allocated
regardless of how the connection is to be used. This scheme is
fair in that all connections are treated equally. The implementation
approach in Part 2.3, in which each transport connection is handled
by a physically separate processor, obviously could use this scheme,
since the allocation would be in the form of memory chips assigned by
the system designer when the system is built.
A more flexible method of allocating receive buffer space is
based on the connection quality of service (QOS) requested by the
user. For instance, a QOS indicating high throughput would be given
more send and receive buffer space than one a QOS indicating low
delay. Similarly, connection priority can be used to determine
send and receive buffer allocation, with important (i.e., high
priority) connections allocated more buffer space.
A slightly more complex scheme is to apportion send and receive
buffer space using both QOS and priority. For each connection, QOS
indicates a general category of operation (e.g., high throughput or
low delay). Within the general category, priority determines the
specific amount of buffer space allocated from a range of
possible values. The general categories may well overlap, resulting,
for example, in a high priority connection with low throughput
requirements being allocated more buffer space than low priority
connection requiring a high throughput.
5 Management of Transport service endpoints.
As mentioned in Part 1.2.1.1, a transport entity needs some way of
referencing a transport connection endpoint within the end system: a
TCEP_id. There are several factors influencing the management of
TCEP_ids:
1) IPC mechanism between the transport entity and the session
entity (Part 3.3);
2) transport entity resources and resource management (Part 4);
3) number of distinct TSAPs supported by the entity (Part 1.2.2.1);
and
4) user process rendezvous mechanism (the means by which session
processes identify themselves to the transport entity, at a
given TSAP, for association with a transport connection);
The IPC mechanism and the user process rendezvous mechanism have more
direct influence than the other two factors on how the TCEP_id
management is implemented.
The number of TCEP_ids available should reflect the resources that
are available to the transport entity, since each TCEP_id in use
represents a potential transport connection. The formal description
assumes that there is a function in the TPE which can decide, on the
basis of current resource availability, whether or not to issue a
TCEP_id for any connection request received. If the TCEP_id is
issued, then resources are allocated for the connection endpoint.
However, there is a somewhat different problem for the users of
transport. Here, the transport entity must somehow inform the
session entity as to the TCEP_ids available at a given TSAP.
In the formal description, a T-CONNECT-request is permitted to enter
at any TSAP/TCEP_id. A function in the TPE considers whether or not
resources are availble to support the requested connection. There is
also a function which checks to see if a TSAP/TCEP_id is busy by
seeing if there is a TPM allocated to it. But this function is not
useful to the session entity which does not have access to the
transport entity's operations. This description of the procedure is
clearly too loose for an implementation.
One solution to this problem is to provide a new (abstract) service,
T-REGISTER, locally, at the interface between transport and session.
___________________________________________________________________
| Primitives Parameters |
|_________________________________________________________________|
| T-REGISTER request | Session process identifier |
|________________________________|________________________________|
| T-REGISTER indication | Transport endpoint identifier,|
| | Session process identifier |
|________________________________|________________________________|
| T-REGISTER refusal | Session process identifier |
|________________________________|________________________________|
This service is used as follows:
1) A session process is identified to the transport entity by a
T-REGISTER-request event. If a TCEP_id is available, the
transport entity selects a TCEP_id and places it into a table
corresponding to the TSAP at which the T-REGISTER-request
event occurred, along with the session process identifier. The
TCEP_id and the session process identifier are then
transmitted to the session entity by means of the T-REGISTER-
indication event. If no TCEP_id is available, then a T-
REGISTER-refusal event carrying the session process identifier
is returned. At any time that an assigned TCEP_id is not
associated with an active transport connection process
(allocated TPM), the transport entity can issue a T-REGISTER-
refusal to the session entity to indicate, for example, that
resources are no longer available to support a connection,
since TC resources are not allocated at registration time.
2) If the session entity is to initiate the transport connection,
it issues a T-CONNECT-request with the TCEP_id as a parameter.
(Note that this procedure is at a slight variance to the
procedure in N3756, which specifies no such parameter, due to
the requirement of alignment of the formal description with
the service description of transport and the definition of the
session protocol.) If the session entity is expecting a
connection request from a remote peer at this TSAP, then the
transport does nothing with the TCEP_id until a CR TPDU
addressed to the TSAP arrives. When such a CR TPDU arrives,
the transport entity issues a T-CONNECT-indication to the
session entity with a TCEP_id as a parameter. As a management
aid, the table entry for the TCEP_id can be marked "busy" when
the TCEP_id is associated with an allocated TPM.
3) If a CR TPDU is received and no TCEP_id is in the table for
the TSAP addressed, then the transport selects a TCEP_id,
includes it as a parameter in the T-CONNECT-indication sent to
the session entity, and places it in the table. The T-
CONNECT-response returned by the session entity will carry the
TCEP_id and the session process identifier. If the session
process identifier is already in the table, the new one is
discarded; otherwise it is placed into the table. This
procedure is also followed if the table has entries but they
are all marked busy or are empty. If the table is full and
all entries ar marked busy, then the transport entity
transmits a DR TPDU to the peer transport entity to indicate
that the connection cannot be made. Note that the transport
entity can disable a TSAP by marking all its table entries
busy.
The realization of the T-REGISTER service will depend on the IPC
mechanisms available between the transport and session entities. The
problem of user process rendezvous is solved in general by the T-
REGISTER service, which is based on a solution proposed by Michael
Chernik of the NBS [CHK85].
6 Management of Network service endpoints in Transport.
6.1 Endpoint identification.
The identification of endpoints at an NSAP is different from that for
the TSAP. The nature of the services at distinct TSAPs is
fundamentally the same, although the quality could vary, as a local
choice. However, it is possible for distinct NSAPs to represent
access to essentially different network services. For example, one
NSAP may provide access to a connectionless network service by means
of an internetwork protocol. Another NSAP may provide access to a
connection-oriented service, for use in communicating on a local
subnetwork. It is also possible to have several distinct NSAPs on
the same subnetwork, each of which provides some service features of
local interest that distinguishes it from the other NSAPs.
A transport entity accessing an X.25 service could use the logical
channel numbers for the virtual circuits as NCEP_ids. An NSAP
providing access only to a permanent virtual circuit would need only
a single NCEP_id to multiplex the transport connections. Similarly,
a CSMA/CD network would need only a single NCEP_id, although the
network is connectionless.
6.2 Management issues.
The Class 4 transport protocol has been succesfully operated over
both connectionless and connection-oriented network services. In
both modes of operation there exists some information about the
network service that a transport implementation could make use of to
enhance performance. For example, knowledge of expected delay to a
destination would permit optimal selection of retransmission timer
value for a connection instance. The information that transport
implementations could use and the mechanisms for obtaining and
managing that information are, as a group, not well understood.
Projects are underway within ISO committees to address the management
of OSI as an architecture and the management of the transport layer
as a layer.
For operation of the Class 4 transport protocol over
connection-oriented network service several issues must be addressed
including:
a. When should a new network connection be opened to support a
transport connection (versus multiplexing)?
b. When a network connection is no longer being used by any
transport connection, should the network connection be closed
or remain open awaiting a new transport connection?
c. When a network connection is aborted, how should the peer
transport entities that were using the connection cooperate to
re-establish it? If splitting is not to be used, how can this
re-establishment be achieved such that one and only one
network connection results?
The Class 4 transport specification permits a transport entity to
multiplex several transport connections (TCs) over a single network
connection (NC) and to split a single TC across several NCs. The
implementor must decide whether to support these options and, if so,
how. Even when the implementor decides never to initiate splitting
or multiplexing the transport entity must be prepared to accept this
behavior from other transport implementations. When multiplexing is
used TPDUs from multiple TCs can be concatenated into a single
network service data unit (NSDU). Therefore, damage to an NSDU may
effect several TCs. In general, Class 2 connections should not be
multiplexed with Class 4 connections. The reason for this is that if
the error rate on the network connection is high enough that the
error recovery capability of Class 4 is needed, then it is too high
for Class 2 operation. The deciding criterion is the tolerance of
the user for frequent disconnection and data errors.
Several issues in splitting must be considered:
1) maximum number of NCs that can be assigned to a given TC;
2) minimum number of NCs required by a TC to maintain the "quality
of service" expected (default of 1);
3) when to split;
4) inactivity control;
5) assignment of received TPDU to TC; and
6) notification to TC of NC status (assigned, dissociated, etc ).
All of these except 3) are covered in the formal description. The
methods used in the formal description need not be used explicitly,
but they suggest approaches to implementation.
To support the possibility of multiplexing and splitting the
implementor must provide a common function below the TC state
machines that maps a set of TCs to a set of NCs. The formal
description provides a general means of doing this, requiring mainly
implementation environment details to complete the mechanism.
Decisions about when network connections are to be opened or closed
can be made locally using local decision criteria. Factors that may
effect the decision include costs of establishing an NC, costs of
maintaining an open NC with little traffic flowing, and estimates of
the probability of data flow between the source node and known
destinations. Management of this type is feasible when a priori
knowledge exists but is very difficult when a need exists to adapt to
dynamic traffic patterns and/or fluctuating network charging
mechanisms.
To handle the issue of re-establishment of the NC after failure, the
ISO has proposed an addendum N3279 [ISO85c] to the basic transport
standard describing a network connection management subprotocol
(NCMS) to be used in conjunction with the transport protocol.
7 Enhanced checksum algorithm.
7.1 Effect of checksum on transport performance.
Performance experiments with Class 4 transport at the NBS have
revealed that straightforward implementation of the Fletcher checksum
using the algorithm recommended in the ISO transport standard leads
to severe reduction of transport throughput. Early modeling
indicated throughput drops of as much as 66% when using the checksum.
Work by Anastase Nakassis [NAK85] of the NBS led to several improved
implementations. The performance degradation due to checksum is now
in the range of 40-55%, when using the improved implementations.
It is possible that transport may be used over a network that does
not provide error detection. In such a case the transport checksum
is necessary to ensure data integrity. In many instances, the
underlying subnetwork provides some error checking mechanism. The
HDLC frame check sequence as used by X.25, IEEE 802.3 and 802.4 rely
on a 32 bit cyclic redundancy check and satellite link hardware
frequently provides the HDLC frame check sequence. However, these
are all link or physical layer error detection mechanisms which
operate only point-to-point and not end-to-end as the transport
checksum does. Some links provide error recovery while other links
simply discard damaged messages. If adequate error recovery is
provided, then the transport checksum is extra overhead, since
transport will detect when the link mechanism has discarded a message
and will retransmit the message. Even when the IP fragments the
TPDU, the receiving IP will discover a hole in the reassembly buffer
and discard the partially assembled datagram (i.e., TPDU). Transport
will detect this missing TPDU and recover by means of the
retransmission mechanism.
7.2 Enhanced algorithm.
The Fletcher checksum algorithm given in an annex to IS 8073 is not
part of the standard, and is included in the annex as a suggestion to
implementors. This was done so that as improvements or new
algorithms came along, they could be incorporated without the
necessity to change the standard.
Nakassis has provided three ways of coding the algorithm, shown
below, to provide implementors with insight rather than universally
transportable code. One version uses a high order language (C). A
second version uses C and VAX assembler, while a third uses only VAX
assembler. In all the versions, the constant MODX appears. This
represents the maximum number of sums that can be taken without
experiencing overflow. This constant depends on the processor's word
size and the arithmetic mode, as follows:
Choose n such that
(n+1)*(254 + 255*n/2) <= 2**N - 1
where N is the number of usable bits for signed (unsigned)
arithmetic. Nakassis shows [NAK85] that it is sufficient
to take
n <= sqrt( 2*(2**N - 1)/255 )
and that n = sqrt( 2*(2**N - 1)/255 ) - 2 generally yields
usable values. The constant MODX then is taken to be n.
Some typical values for MODX are given in the following table.
BITS/WORD MODX ARITHMETIC
15 14 signed
16 21 unsigned
31 4102 signed
32 5802 unsigned
This constant is used to reduce the number of times mod 255 addition
is invoked, by way of speeding up the algorithm.
It should be noted that it is also possible to implement the checksum
in separate hardware. However, because of the placement of the
checksum within the TPDU header rather than at the end of the TPDU,
implementing this with registers and an adder will require
significant associated logic to access and process each octet of the
TPDU and to move the checksum octets in to the proper positions in the
TPDU. An alternative to designing this supporting logic is to use a
fast, microcoded 8-bit CPU to handle this access and the computation.
Although there is some speed penalty over separate logic, savings
may be realized through a reduced chip count and development time.
7.2.1 C language algorithm.
#define MODX 4102
encodecc( mess,len,k )
unsigned char mess[] ; /* the TPDU to be checksummed */
int len,
k; /* position of first checksum octet
as an offset from mess[0] */
{ int ip,
iq,
ir,
c0,
c1;
unsigned char *p,*p1,*p2,*p3 ;
p = mess ; p3 = mess + len ;
if ( k > 0) { mess[k-1] = 0x00 ; mess[k] = 0x00 ; }
/* insert zeros for checksum octets */
c0 = 0 ; c1 = 0 ; p1 = mess ;
while (p1 < p3) /* outer sum accumulation loop */
{
p2 = p1 + MODX ; if (p2 > p3) p2 = p3 ;
for (p = p1 ; p < p2 ; p++) /* inner sum accumulation loop */
{ c0 = c0 + (*p) ; c1 = c1 + c0 ;
}
c0 = c0%255 ; c1 = c1%255 ; p1 = p2 ;
/* adjust accumulated sums to mod 255 */
}
ip = (c1 << 8) + c0 ; /* concatenate c1 and c0 */
if (k > 0)
{ /* compute and insert checksum octets */
iq = ((len-k)*c0 - c1)%255 ; if (iq <= 0) iq = iq + 255 ;
mess[k-1] = iq ;
ir = (510 - c0 - iq) ;
if (ir > 255) ir = ir - 255 ; mess[k] = ir ;
}
return(ip) ;
}
7.2.2 C/assembler algorithm.
#include <math>
encodecm(mess,len,k)
unsigned char *mess ;
int len,k ;
{
int i,ip,c0,c1 ;
if (k > 0) { mess[k-1] = 0x00 ; mess[k] = 0x00 ; }
ip = optm1(mess,len,&c0,&c1) ;
if (k > 0)
{ i = ( (len-k)*c0 - c1)%255 ; if (i <= 0) i = i + 255 ;
mess[k-1] = i ;
i = (510 - c0 - i) ; if (i > 255) i = i - 255 ;
mess[k] = i ;
}
return(ip) ;
}
; calling sequence optm(message,length,&c0,&c1) where
; message is an array of bytes
; length is the length of the array
; &c0 and &c1 are the addresses of the counters to hold the
; remainder of; the first and second order partial sums
; mod(255).
.ENTRY optm1,^M<r2,r3,r4,r5,r6,r7,r8,r9,r10,r11>
movl 4(ap),r8 ; r8---> message
movl 8(ap),r9 ; r9=length
clrq r4 ; r5=r4=0
clrq r6 ; r7=r6=0
clrl r3 ; clear high order bytes of r3
movl #255,r10 ; r10 holds the value 255
movl #4102,r11 ; r11= MODX
xloop: movl r11,r7 ; if r7=MODX
cmpl r9,r7 ; is r9>=r7 ?
bgeq yloop ; if yes, go and execute the inner
; loop MODX times.
movl r9,r7 ; otherwise set r7, the inner loop
; counter,
yloop: movb (r8)+,r3 ;
addl2 r3,r4 ; sum1=sum1+byte
addl2 r4,r6 ; sum2=sum2+sum1
sobgtr r7,yloop ; while r7>0 return to iloop
; for mod 255 addition
ediv r10,r6,r0,r6 ; r6=remainder
ediv r10,r4,r0,r4 ;
subl2 r11,r9 ; adjust r9
bgtr xloop ; go for another loop if necessary
movl r4,@12(ap) ; first argument
movl r6,@16(ap) ; second argument
ashl #8,r6,r0 ;
addl2 r4,r0 ;
ret
7.2.3 Assembler algorithm.
buff0: .blkb 3 ; allocate 3 bytes so that aloop is
; optimally aligned
; macro implementation of Fletcher's algorithm.
; calling sequence ip=encodemm(message,length,k) where
; message is an array of bytes
; length is the length of the array
; k is the location of the check octets if >0,
; an indication not to encode if 0.
;
movl 4(ap),r8 ; r8---> message
movl 8(ap),r9 ; r9=length
clrq r4 ; r5=r4=0
clrq r6 ; r7=r6=0
clrl r3 ; clear high order bytes of r3
movl #255,r10 ; r10 holds the value 255
movl 12(ap),r2 ; r2=k
bleq bloop ; if r2<=0, we do not encode
subl3 r2,r9,r11 ; set r11=L-k
addl2 r8,r2 ; r2---> octet k+1
clrb (r2) ; clear check octet k+1
clrb -(r2) ; clear check octet k, r2---> octet k.
bloop: movw #4102,r7 ; set r7 (inner loop counter) = to MODX
cmpl r9,r7 ; if r9>=MODX, then go directly to adjust r9
bgeq aloop ; and execute the inner loop MODX times.
movl r9,r7 ; otherwise set r7, the inner loop counter,
; equal to r9, the number of the
; unprocessed characters
aloop: movb (r8)+,r3 ;
addl2 r3,r4 ; c0=c0+byte
addl2 r4,r6 ; sum2=sum2+sum1
sobgtr r7,aloop ; while r7>0 return to iloop
; for mod 255 addition
ediv r10,r6,r0,r6 ; r6=remainder
ediv r10,r4,r0,r4 ;
subl2 #4102,r9 ;
bgtr bloop ; go for another loop if necessary
ashl #8,r6,r0 ; r0=256*r6
addl2 r4,r0 ; r0=256*r6+r4
cmpl r2,r7 ; since r7=0, we are checking if r2 is
bleq exit ; zero or less: if yes we bypass
; the encoding.
movl r6,r8 ; r8=c1
mull3 r11,r4,r6 ; r6=(L-k)*c0
ediv r10,r6,r7,r6 ; r6 = (L-k)*c0 mod(255)
subl2 r8,r6 ; r6= ((L-k)*c0)%255 -c1 and if negative,
bgtr byte1 ; we must
addl2 r10,r6 ; add 255
byte1: movb r6,(r2)+ ; save the octet and let r2---> octet k+1
addl2 r6,r4 ; r4=r4+r6=(x+c0)
subl3 r4,r10,r4 ; r4=255-(x+c0)
bgtr byte2 ; if >0 r4=octet (k+1)
addl2 r10,r4 ; r4=255+r4
byte2: movb r4,(r2) ; save y in octet k+1
exit: ret
8 Parameter selection.
8.1 Connection control.
Expressions for timer values used to control the general transport
connection behavior are given in IS 8073. However, values for the
specific factors in the expressions are not given and the expressions
are only estimates. The derivation of timer values from these
expressions is not mandatory in the standard. The timer value
expressions in IS 8073 are for a connection-oriented network service
and may not apply to a connectionless network service.
The following symbols are used to denote factors contributing to
timer values, throughout the remainder of this Part.
Elr = expected maximum transit delay, local to remote
Erl = expected maximum transit delay, remote to local
Ar = time needed by remote entity to generate an acknowledgement
Al = time needed by local entity to generate an acknowledgement
x = local processing time for an incoming TPDU
Mlr = maximum NSDU lifetime, local to remote
Mrl = maximum NSDU lifetime, remote to local
T1 = bound for maximum time local entity will wait for
acknowledgement before retransmitting a TPDU
R = bound for maximum local entity will continue to transmit a
TPDU that requires acknowledgment
N = bound for maximum number of times local entity will transmit
a TPDU requiring acknowledgement
L = bound for the maximum time between the transmission of a
TPDU and the receipt of any acknowledgment relating to it.
I = bound for the time after which an entity will initiate
procedures to terminate a transport connection if a TPDU is
not received from the peer entity
W = bound for the maximum time an entity will wait before
transmitting up-to-date window information
These symbols and their definitions correspond to those given in
Clause 12 of IS 8073.
8.1.1 Give-up timer.
The give-up timer determines the amount of time the transport
entity will continue to await an acknowledgement (or other
appropriate reply) of a transmitted message after the message
has been retransmitted the maximum number of times. The
recommendation given in IS 8073 for values of this timer is
expressed by
T1 + W + Mrl, for DT and ED TPDUs
T1 + Mrl, for CR, CC, and DR TPDUs,
where
T1 = Elr + Erl + Ar + x.
However, it should be noted that Ar will not be known for either the
CR or the CC TPDU, and that Elr and Erl may vary considerably due to
routing in some conectionless network services. In Part 8.3.1, the
determination of values for T1 is discussed in more detail. Values
for Mrl generally are relatively fixed for a given network service.
Since Mrl is usually much larger than expected values of T1, a
rule-of-thumb for the give-up timer value is 2*Mrl + Al + x for the
CR, CC and DR TPDUs and 2*Mrl + W for DT and ED TPDUs.
8.1.2 Inactivity timer.
This timer measures the maximum time period during which a
transport connection can be inactive, i.e., the maximum time an
entity can wait without receiving incoming messages. A usable value
for the inactivity timer is
I = 2*( max( T1,W )*N ).
This accounts for the possibility that the remote peer is using a
window timer value different from that of the local peer. Note that
an inactivity timer is important for operation over connectionless
network services, since the periodic receipt of AK TPDUs is the only
way that the local entity can be certain that its peer is still
functioning.
8.1.3 Window timer.
The window timer has two purposes. It is used to assure that the
remote peer entity periodically receives the current state of the
local entity's flow control, and it ensures that the remote peer
entity is aware that the local entity is still functioning. The
first purpose is necessary to place an upper bound on the time
necessary to resynchronize the flow control should an AK TPDU which
notifies the remote peer of increases in credit be lost. The second
purpose is necessary to prevent the inactivity timer of the remote
peerfrom expiring. The value for the window timer, W, depends on
several factors, among which are the transit delay, the
acknowledgement strategy, and the probability of TPDU loss in the
network. Generally, W should satisfy the following condition:
W > C*(Erl + x)
where C is the maximum amount of credit offered. The rationale for
this condition is that the right-hand side represents the maximum
time for receiving the entire window. The protocol requires that all
data received be acknowledged when the upper edge of the window is
seen as a sequence number in a received DT TPDU. Since the window
timer is reset each time an AK TPDU is transmitted, there is usually
no need to set the timer to any less than the value on the right-hand
side of the condition. An exception is when both C and the maximum
TPDU size are large, and Erl is large.
When the probability that a TPDU will be lost is small, the value of
W can be quite large, on the order of several minutes. However, this
increases the delay the peer entity will experience in detecting the
deactivation of the local transport entity. Thus, the value of W
should be given some consideration in terms of how soon the peer
entity needs to detect inactivity. This could be done by placing
such information into a quality of service record associated with the
peer's address.
When the expected network error rate is high, it may be necessary to
reduce the value of W to ensure that AK TPDUs are being received by
the remote entity, especially when both entities are quiescent for
some period of time.
8.1.4 Reference timer.
The reference timer measures the time period during which a
source reference must not be reassigned to another transport
connection, in order that spurious duplicate messages not
interfere with a new connection. The value for this timer
given in IS 8073 is
L = Mlr + Mrl + R + Ar
where
R = T1*N + z
in which z is a small tolerance quantity to allow for factors
internal to the entity. The use of L as a bound, however, must be
considered carefully. In some cases, L may be very large, and not
realistic as an upper or a lower bound. Such cases may be
encountered on routes over several catenated networks where R is set
high to provide adequate recovery from TPDU loss. In other cases L
may be very small, as when transmission is carried out over a LAN and
R is set small due to low probability of TPDU loss. When L is
computed to be very small, the reference need not be timed out at
all, since the probability of interference is zero. On the other
hand, if L is computed to be very large a smaller value can be used.
One choice for the value might be
L = min( R,(Mrl + Mlr)/2 )
If the reference number assigned to a new connection by an
entity is monotonically incremented for each new connection through
the entire available reference space (maximum 2**16 - 1), the timer
is not critical: the sequence space is large enough that it is likely
that there will be no spurious messages in the network by the time
reference numbers are reused.
8.2 Flow control.
The peer-to-peer flow control mechanism in the transport protocol
determines the upper bound on the pace of data exchange that occurs
on transport connections. The transport entity at each end of
a connection offers a credit to its peer representing the number of
data messages it is currently willing to accept. All received
data messages are acknowledged, with the acknowledgement message
containing the current receive credit information. The three
credit allocation schemes discussed below present a diverse set
of examples of how one might derive receive credit values.
8.2.1 Pessimistic credit allocation.
Pessimistic credit allocation is perhaps the simplest form of flow
control. It is similar in concept to X-on/X-off control. In this
method, the receiver always offers a credit of one TPDU. When the DT
TPDU is received, the receiver responds with an AK TPDU carrying a
credit of zero. When the DT TPDU has been processed by the receiving
entity, an additional AK TPDU carrying a credit of one will be sent.
The advantage to this approach is that the data exchange is very
tightly controlled by the receiving entity. The disadvantages are:
1) the exchange is slow, every data message requiring at least
the time of two round trips to complete the transfer transfer, and 2)
the ratio of acknowledgement to data messages sent is 2:1. While not
recommeneded, this scheme illustrates one extreme method of credit
allocation.
8.2.2 Optimistic credit allocation.
At the other extreme from pessimistic credit allocation is optimistic
credit allocation, in which the receiver offers more credit than
it has buffers. This scheme has two dangers. First, if the
receiving user is not accepting data at a fast enough rate, the
receiving transport's buffers will become filled. Since the
credit offered was optimistic, the sending entity will continue to
transmit data, which must be dropped by the receiving entity for
lack of buffers. Eventually, the sender may reach the maximum
number of retransmissions and terminate the connection.
The second danger in using optimistic flow control is that the
sending entity may transmit faster than the receiving entity can
consume. This could result from the sender being implemented on
a faster machine or being a more efficient implementation. The
resultant behavior is essentially the same as described above:
receive buffer saturation, dropped data messages, and connection
termination.
The two dangers cited above can be ameliorated by implementing
the credit reduction scheme as specified in the protocol. However,
optimistic credit allocation works well only in limited
circumstances. In most situations it is inappropriate and
inefficient even when using credit reduction. Rather than seeking
to avoid congestion, optimistic allocation causes it, in most cases,
and credit reduction simply allows one to recover from congestion
once it has happened. Note that optimistic credit allocation
combined with caching out-of-sequence messages requires a
sophisticated buffer management scheme to avoid reasssembly deadlock
and subsequent loss of the transport connection.
8.2.3 Buffer-based credit allocation.
Basing the receive credit offered on the actual availability of
receive buffers is a better method for achieving flow control.
Indeed, with few exceptions, the implementations that have been
studied used this method. It continuous flow of data and
eliminating the need for the credit-restoring acknowledgements.
Since only available buffer space is offered, the dangers of
optimistic credit allocation are also avoided.
The amount of buffer space needed to maintain a continuous bulk
data transfer, which represents the maximum buffer requirement, is
dependent on round trip delay and network speed. Generally, one
would want the buffer space, and hence the credit, large enough to
allow the sender to send continuously, so that incremental credit
updates arrive just prior to the sending entity exhausting the
available credit. One example is a single-hop satellite link
operating at 1.544 Mbits/sec. One report [COL85] indicates that
the buffer requirement necessary for continuous flow is approximately
120 Kbytes. For 10 Mbits/sec. IEEE 802.3 and 802.4 LANs, the figure
is on the order of 10K to 15K bytes [BRI85, INT85, MIL85].
An interesting modification to the buffer-based credit allocation
scheme is suggested by R.K. Jain [JAI85]. Whereas the approach
described above is based strictly on the available buffer space, Jain
suggests a scheme in which credit is reduced voluntarily by the
sending entity when network congestion is detected. Congestion
is implied by the occurrence of retransmissions. The sending
entity, recognizing retransmissions, reduces the local value of
credit to one, slowly raising it to the actual receive credit
allocation as error-free transmissions continue to occur. This
technique can overcome various types of network congestion occurring
when a fast sender overruns a slow receiver when no link level flow
control is available.
8.2.4 Acknowledgement policies.
It is useful first to review the four uses of the acknowledgement
message in Class 4 transport. An acknowledgement message:
1) confirms correct receipt of data messages,
2) contains a credit allocation, indicating how many
data messages the entity is willing to receive
from the correspondent entity,
3) may optionally contain fields which confirm
receipt of critical acknowledgement messages,
known as flow control confirmation (FCC), and
4) is sent upon expiration of the window timer to
maintain a minimum level of traffic on an
otherwise quiescent connection.
In choosing an acknowledgement strategy, the first and third uses
mentioned above, data confirmation and FCC, are the most relevant;
the second, credit allocation, is determined according to the
flow control strategy chosen, and the fourth, the window
acknowledgement, is only mentioned briefly in the discussion on
flow control confirmation.
8.2.4.1 Acknowledgement of data.
The primary purpose of the acknowledgement message is to confirm
correct receipt of data messages. There are several choices that
the implementor must make when designing a specific
implementation. Which choice to make is based largely on the
operating environment (e.g., network error characteristics).
The issues to be decided upon are discussed in the sections below.
8.2.4.1.1 Misordered data messages.
Data messages received out of order due to network misordering
or loss can be cached or discarded. There is no single determinant
that guides the implementor to one or the other choice. Rather,
there are a number of issues to be considered.
One issue is the importance of maintaining a low delay as perceived
by the user. If transport data messages are lost or damaged in
transit, the absence of a positive acknowledgement will trigger a
retransmission at the sending entity. When the retransmitted data
message arrives at the receiving transport, it can be delivered
to the user. If subsequent data messages had been cached, they
could be delivered to the user at the same time. The delay
between the sending and receiving users would, on average, be
shorter than if messages subsequent to a lost message were
dependent on retransmission for recovery.
A second factor that influences the caching choice is the cost of
transmission. If transmission costs are high, it is more economical
to cache misordered data, in conjunction with the use of
selective acknowledgement (described below), to avoid
retransmissions.
There are two resources that are conserved by not caching misordered
data: design and implementation time for the transport entity and CPU
processing time during execution. Savings in both categories
accrue because a non-caching implementation is simpler in its buffer
management. Data TPDUs are discarded rather than being reordered.
This avoids the overhead of managing the gaps in the received
data sequence space, searching of sequenced message lists, and
inserting retransmitted data messages into the lists.
8.2.4.1.2 Nth acknowledgement.
In general, an acknowledgement message is sent after receipt of
every N data messages on a connection. If N is small compared to the
credit offered, then a finer granularity of buffer control is
afforded to the data sender's buffer management function. Data
messages are confirmed in small groups, allowing buffers to be
reused sooner than if N were larger. The cost of having N small is
twofold. First, more acknowledgement messages must be generated by
one transport entity and processed by another, consuming some of the
CPU resource at both ends of a connection. Second, the
acknowledgement messages consume transmission bandwidth, which may
be expensive or limited.
For larger N, buffer management is less efficient because the
granularity with which buffers are controlled is N times the maximum
TPDU size. For example, when data messages are transmitted to a
receiving entity employing this strategy with large N, N data
messages must be sent before an acknowledgement is returned
(although the window timer causes the acknowledgement to be sent
eventually regardless of N). If the minimum credit allocation for
continuous operation is actually a fraction of N, a credit of N
must still be offered, and N receive buffers reserved, to achieve a
continuous flow of data messages. Thus, more receive buffers
are used than are actually needed. (Alternatively, if one relies on
the timer, which must be adjusted to the receipt time for N and
will not expire until some time after the fraction of N has been
sent, there may be idle time.)
The choice of values for N depends on several factors. First, if the
rate at which DT TDPUs are arriving is relatively low, then there is
not much justification for using a value for N that exceeds 2. On
the other hand, if the DT TPDU arrival rates is high or the TPDU's
arrive in large groups (e.g., in a frame from a satellite link), then
it may be reasonable to use a larger value for N, simply to avoid the
overhead of generating and sending the acknowledgements while
procesing the DT TPDUs. Second, the value of N should be related to
the maximum credit to be offered. Letting C be the maximum credit to
be offered, one should choose N < C/2, since the receipt of C TPDUs
without acknowledging will provoke sending one in any case. However,
since the extended formats option for transport provides max C =
2**16 - 1, a choice of N = 2**15 - 2 is likely to cause some of the
sender's retransmission timers to expire. Since the retransmitted
TPDU's will arrive out of sequence, they will provoke the sending of
AK TPDU's. Thus, not much is gained by using an N large. A better
choice is N = log C (base 2). Third, the value of should be related
to the maximum TPDU size used on the connection and the overall
buffer management. For example, the buffer management may be tied to
the largest TPDU that any connection will use, with each connection
managing the actual way in which the negotiated TPDU size relates to
this buffer size. In such case, if a connection has negotiated a
maximum TPDU size of 128 octets and the buffers are 2048 octets, it
may provide better management to partially fill a buffer before
acknowledging. If the example connection has two buffers and has
based offered credit on this, then one choice for N could be 2*log(
2048/128 ) = 8. This would mean that an AK TPDU would be sent when a
buffer is half filled ( 2048/128 = 16 ), and a double buffering
scheme used to manage the use of the two buffers. the use of the t