SE515407C2 - Slot reuse method for increasing throughput in DTM network - Google Patents

Abstract

The method involves extending the DTM block token format to include the parameters describing the segments between the source and destination node. The block token capacity is only reserved on the segments between the source and destination node. Two or more segment consecutive tokens representing the same slot range are merged into a single token, when existing in the free pool of a node. Simultaneous transmissions in the same slot are enabled over disjointed segments of the network. This is implemented in a central token management scheme or a distributed token management scheme.

Description

W 20 25 30 35 ø u - | u: n. .-. . . v. .n. , ._ ~ ~ ».u- 1. , .... 4 v. .. - -, »v. 1 | 1-4 n a. . .

A ß ~ v u n .. n. Sometimes global, type of service. network and a new terminal for each new Instead, a new integrated service network is needed that supports existing services as well as new services. The overall objectives for such a network are that it should be scalable up to global size and the utilization of expensive components will be maximum. Optical transmission technology has been shown to provide the necessary link capacity at a sufficiently low cost to make integrated service networks a realistic solution.

However, a new integrated optical network with much higher capacity will lead to new problems that do not exist in today's more specialized networks with lower performance. To begin with, when network capacity increases and propagation delay persists due to the speed of light, the increasing product of capacity and delay will place higher demands on the mechanisms that isolate a user's traffic from other parties' traffic.

A phone call, for example, should not be affected by another user opening a high capacity video channel.

Furthermore, applications and protocols will have to work reliably with an increasing amount of information in motion to take advantage of the increasing network capacity. This results in larger bursts of information and larger transactions in the network.

Today's networks that use unconnected packet-switched protocols, e.g. IP (Internet Protocol) They have been developed that connect only a small number of DARPA have proven to be very scalable. from small networks, (Defense Advanced Research Projects Agency) research computers in the mid-70s to today's universally distributed global Internet. Local area networks based on CSMA / CD Access / Collision Detection), shared media such as Carrier Sense Multiple token ring and FDDI (Fiber Distributed Data Interface) are used in the Internet as simple building blocks, connected with routers or bridges.

The combination of simple expansion, low-growing costs n »u. 10 15 20 25 30 35 515 407 w + ñ: * ß; aß: ~ = regarding nodes and tolerance of incorrect nodes, has resulted in simple, flexible and robust networks. In addition, shared media allows efficient application of new protocols for multicast such as. IP multicast.

A disadvantage of shared medium is that it typically allows only one terminal to transmit a certain time, and that not all network segments are used efficiently. A scheme that allows the medium's capacity to be reused may be realized, but this is often at the expense of hardware complexity. The control mechanisms for access to the shared medium are also heavily dependent on the size of the network and are usually effective only within local area networks (short distances).

The two most important network types are connection-oriented circuit-switched networks used in telephony, and connection-free packet-switched networks, exemplified by the Internet. When a circuit-switched network is used for data communication, the connections need to be continuously established between bursts of information, which results in poor utilization of the capacity in the network. This problem arises when disconnection and disconnection takes a long time compared to the dynamic variations in user needs. Another source of inefficiency in circuit-switched networks is the use of symmetrical bidirectional channels, which introduce 50% "overhead" when the information flow is unidirectional. This limitation also makes multicast connectors difficult to implement and inefficient. A connection-free packet-switched network, on the other hand, lacks resource reservation and must therefore add control information to each message before transmission can begin. In addition, the delay in a connection-free packet-switched network can not be accurately predicted and packets can even be lost due to overflow in buffers or incorrect package heads.

The last two factors make it difficult to support real-time services. Mechanisms that make it possible to avoid congestion can isolate different users' traffic flows. 15 20 25 30 35 '. . | .n 515 407 .I n.

However, these mechanisms are limited and only work on a time scale comparable to a packet delay round trip between transmitter and receiver.

To address the above problems, the communications industry focuses on the development of ATM ATM has been proposed for LANs (Asynchronous Transfer Mode). and many future public networks. CCITT (International Telegraph and Telephone Consultative Committee) has also adopted ATM as the transmission standard for B-ISDN (Broadband Integrated Services Digital Network). ATM networks are connection-oriented and establish virtual channels, similar to leased lines in circuit-switched networks, but use small packets of fixed size, cells, for information transmission. The ATM's packet-switched nature means that the network needs many new mechanisms, such as reservation of buffers and operating algorithms to be able to determine real-time guarantees for a leash, i.e. a virtual channel.

Another solution to be able to guarantee real-time concentrates on a circuit-switched network and thus has to address the problems of traditional circuit-switching, as they have been described above. A new shared media control protocol is also being applied, and thus the general problems of shared media must also be considered. This design, called DTM (Dynamic Synchronous Transfer Mode), (see eg Christer Bohm, Per Lindgren, Lars Ramfelt and Peter Sjödin, The DTM Gigabit Network, Journal 3 (2): lO9-126, 1994, Gauffin, Lars Håkansson, and Björn Pehrson, Multi-gigabit of High Speed Networks, and Lars networking based on DTM, Computer Networks and ISDN Systems, 24 (2) ll9-139, April 1992) channels as communication abstraction. makes use of These channels differ from telephone liaison in several different ways. To begin with, the connection delay is so short that resources can be switched on / off dynamically as soon as the user need changes character. Secondly, the channels are unidirectional and thus minimize "overhead" in municipal | | ~ | u f. u. 15 20 25 30 35 - o; . u 515 407 @ | > v 1 v The cation is unidirectional. Third, they offer multiple transmission capacities to support different types of needs of the users. Finally, the channels can have an unlimited number of destinations (multicast).

DTM channels share many good features with circuits.

There is no communication of control information after the channel has been established, which results in very high use of network resources for large data transmissions. The support of real-time traffic is natural; rings. no monitoring of users' behavior, congestion control or flow control is required within the network. The control information is different from user information, which makes communication (i.e. less than 125 us) tion to several destinations less complex. the delay is negligible and the risk of data disappearing due to lack of congestion, due to overcrowded queues such as within ATMs. The probability of bit errors depends directly on the underlying link technology, and the channel connections are simple and fast due to strict resource reservation when establishing the channel.

DTM can also perform well in areas where traditional circuit-switched networks have shortcomings: and as dynamic bandwidth allocation, source delay, networks with shared medium.

SUMMARY OF THE INVENTION One of the problems with using DTM is that a time slot for data cannot normally be used by two nodes simultaneously within the network.

The object of the invention is to solve this problem.

This is achieved by applying a method for reusing slot slots (slot reuse) and an arrangement that improves the use of shared links and as a result you get an increased throughput (througput) in the DTM network.

The method for reusing time slots according to the invention comprises an extension of the DTM block token format. . «| .u u »nu 20 25 30 35. n - v | | . - ~ | m 515 407 n. .m tet which calculates parameters which describe the segments between the source and the destination node, and reserves the block token capacity only on the segments between the source and the destination node, which allows simultaneous transmissions in the same slot over separate segments within the network.

Hatch reuse may also involve merging two or more segment consecutive tokens which represent the same group of time slots, into a single token, when it exists in a node's free pool.

The method and arrangement for reusing time slots according to the invention prevents the above-mentioned problems. The method allows channels to only reserve capacity on the segments between the source and the destination node. A single slot can then be used several times simultaneously within the network.

A very important advantage of the invention is that no changes to the hardware, compared to the original prototype implementation, are needed.

Another advantage of the invention is that it can be applied in both a central and a distributed model of tokens. for administration of the invention can also be applied in a combination of these two models.

Another advantage is that the performance gain is clear: on a double bus where the node pairs of the source and the destination are uniformly distributed, it has been shown that the throughput can be doubled.

An additional advantage is that the performance gain can be even higher in other types of networks; For example, in a doubling structure with source and destination nodes that are uniformly distributed, the throughput can be increased up to four times. If source and destination nodes are not uniformly distributed, the gain can be much higher.

Another advantage is that performance is improved when combined with a defragmentation method, which returns tokens to their home nodes, as a way to increase the probability of Ü 20 25 30 - ~ »« ». | a v. v. 515 407 that two consecutive tokens can be merged in the free pool of the nodes, which reduces fragmentation.

BRIEF DESCRIPTION OF THE DRAWINGS The invention will be described in more detail below, with reference to the accompanying drawing, in which Fig. 1 illustrates a dual bus DTM network. Fig. 2 illustrates a DTM 125 ms cycle with a determined home node for each data time slot according to the invention. Fig. 3 illustrates a token map showing the number of slots and segments, Fig. 4 illustrates a time slot segment map, which shows the reuse of slots according to the invention. Fig. 5 illustrates the performance (throughput and access delay, for small user (16 kbytes) simulated, versus the offered load) requirements and for different minimum acceptance capacities when using a distributed (token server) according to the invention, Fig. 6 shows the performance for small user requirements (16 kbytes) and for different number of permitted attempts before the request is blocked, which is simulated by means of a distributed token server according to the invention, Fig. 7 illustrates the access delay as a function of simulated time, with by means of A) the defragmentation scheme and no fragmentation at the start of the simulation, B) the defragmentation scheme according to the invention and maximum fragmentation at the start of the simulation, and C) no fragmentation scheme and maximum fragmentation at the start of the simulation. Fig. double bus versus offered load for a double bus DTM-8 illustrates theoretical throughput for a DTM network with and without reuse of time slots, Fig. 9 illustrates performance for the different packet sizes simulated using a central token. | «: U. M u- W U 20 25 30 35- 515 407. . 4 | f c »- = 1 un. . . «E> manager within a 10 km long double-bus DTM network without slot reuse. Fig. 10 illustrates performance for different packet sizes simulated using a central token manager within a 10 km long dual bus DTM network using time slots according to the invention, Fig. 11 illustrates performance for different packet sizes simulated using a central token manager within a 100 km long DTM network with reuse of time slots according to the invention, Fig. 12 illustrates performance for different packet sizes simulated by using a distributed token manager in a double bus network with defragmentation and reuse of time slots according to the invention, Fig. 13 illustrates the performance of different bus lengths simulated by a distributed token manager with defragmentation and reuse of time slots according to the invention, and Fig. 14 illustrates the performance of different traffic conditions simulated by a distributed token manager in a dual bus network with defragmentation and reuse of time slots according to the invention.

DETAILED DESCRIPTION OF THE DESIGN To begin with, DTM MAC Control (Medium Access Protocol) will be described. The basic topology of a DTM network is a bus with two unidirectional optical fibers that interconnect all nodes, as illustrated in Fig. 1. to form an arbitrary together Several buses with different speeds can multi-stage networks.In today's prototype implementation, buses can be combined into a two-dimensional network.A node at the junction of two buses can synchronously exchange data in time slots between the two buses.This allows efficient switching with constant delay through the node The primary communication abstraction in DTM is a channel I ».. -n un 20 25 30 35 ç. n ..: v but 515 407 which can be of different capacities and reach multiple receivers (multicast).

The DTM MAC protocol is a time-multiplexed schedule. (8 kHz), which in turn are divided into 64-bit time slots The bus bandwidth is divided into l25 ms cycles (or just slots, in short) which is illustrated in Fig. 2. The number of slots in a cycle is thus dependent on the network - the bit rate of the work; for example, on a 6.4 Gbit / s network, there are approximately 12,500 slots per cycle.

The slots are divided into two different groups, control slots and data slots. Control hatches are used to carry messages for the network's internal operation, such as messages for channel establishment and bandwidth redistribution. Data gaps are used to transmit user data and are not interpreted by intermediate network nodes. Intermediate nodes are nodes between the source and the destination.

Each network node has a node controller (NC or node controller), which checks the availability of data gaps and performs management operations, such as when the network is started up and troubleshooting. The most important tasks that the node controller has are to create and terminate channels when this is required by the users, and to manage the network resources in accordance with user requirements and in the background.

Control gaps are only used for messages between node controllers. Each node controller is allowed to write to at least one control slot in each cycle that it uses to send control messages downstream to other nodes. Since permission to write to control slots is exclusive, the node controller always has access to its control slots, regardless of other nodes and network load. The number of control slots used by a node may vary during network operation.

The network is not limited to a double bus, but can be applied with other types of structures, such as a ring structure with an arbitrary number of nodes. Transmissions- | - L 1 = p m n.

W 20 25 30 35 | | «- .u 515 407 u - | . .- u n. the medium may, in addition to optical fibers, be coaxial cable or any other type of high bandwidth transmission medium. Hereinafter, the transmission medium will be called optical fibers. The bandwidth of the DTM double bus in the preferred design is divided into 125 ms cycles, which in turn are divided into 64-bit time slots. The invention is not limited to DTM networks with this value, but can be used in networks with cycles and time slots of any size.

The principles of resource management (called token management) will be described below. The majority of the gaps within a cycle are data time slots. Access to data slots changes within a period of time, depending on traffic requirements. Permission to write to slots is controlled by slot tokens (or tokens only, for short). A node controller can enter data in a slot only if it owns the corresponding token. The token protocol guarantees that access to slots is free of conflicts, which means that several nodes do not enter data in the same slot.

Control messages for channel establishment and bandwidth allocation carry sets of slots or tokens A control message is, however, 64 bits This as parameters. and can therefore only have a small number of parameters. This means that if a user requests a large bandwidth transfer, it may be necessary to send several control messages to create the channel. This means extra access delay and devours signaling capacity.

We are considering a number of mechanisms to reduce the amount of information that needs to be transmitted during the creation of the channel and when redistributing tokens. The first optimal way in token management is to introduce block tokens. A block token is sent in a single control message and represents a group of tokens, but can only be used in special combinations of tokens.

For example, in the simulator, a block token is denoted by a slot number indicating the position of the slot in the cycle and a «~ v. -n ~ I «. -u n. u. 20 25 30 35. . -. w: 515 407. | - | v-number that divides the number of adjacent gaps in the group.

This optimal block token example assumes that the token pool is not fragmented into small parts. This will be called the token pool fragmentation.

The token protocol guarantees that a data slot can never be used by two nodes simultaneously on the bus. Sometimes this protocol is too conservative.

(A, B and C) channels. The nodes are connected by bus segments and Fig. 3 shows an example of how three tokens are reserved for the three channels typically use a subset of segments on the bus (gray color) and the rest are reserved but remain unused and thus waste a better alternative is to allow kana- (white color) shared resources. only reserve capacity on the segments between the transmitter and the receiver as the example in Fig. 4. In this example, a single slot can be used several times on the bus. Channels D and E use the same gaps as channels A and C, but on different segments. This is called slot reuse. Hatch reuse enables simultaneous transmissions in the same slot over separate segments on the bus.

Luck reuse is a general method for better use of shared links in ring and bus networks. The hatch reuse algorithms in DQDB Simple and CRMA (Distributed Queue Dual Bus), (Cyclic Reservation Multiple Access) depend on control information in the hatches. Buffer deployment networks, when combined with destination release (as in METARING, in individual links and resolving any conflict by ation release) can reuse the capacity to delay the incoming packet stream through an elastic buffer.

With luck reuse, the complexity of the access scheme increases, regardless of whether it is done in hardware such as in DQDB, Simple and CRMA; it is implemented in systems other than in DTM, also adds or in software, as in DTM. When the luck-reuse complex hardware to the critical a - e. nu ll I I 11 .: 5 '..'...' v »I .. 10 15 20 25 30 35 | | | . .- 515 407 | -. . .. the high-speed path through a node, and therefore the node delay is increased.

In order to allow slot reuse in DTM, the block token format of the invention is extended to include parameters that describe the segments it represents. The token management protocol is also modified according to the invention in order to avoid conflicts in the slot number dimension as well as in the segment dimension. The most important assumption is that no hardware changes in the original prototype implementation were allowed or required. The performance gain is thus very clear: on a double bus where the source and destination pairs are uniformly distributed, it has been shown that the throughput can be increased by twice. The performance gain can even be higher in other network types: for example in a double ring structure with source and destination nodes that are uniformly distributed, the throughput can be increased by four times. uniformly distributed, If source and destination nodes are not, the gain can be even higher.

The potential problem of slot reuse in a DTM network is, however, the higher algorithm complexity and ultimately the higher burden on the node controller and signaling channels in short). (especially if the average channel duration is Two token management schemes have been evaluated. The first and simplest is to let a single node controller control all free tokens for a fiber. This type of centralized (server) mechanism has also been used in systems such as for example, CRMA, where the main end node distributes the fiber capacity to all other nodes.The simulator was set up in such a way that for each fiber there was a node that was one third of the distance from the gap generator, and this was the token server (with 100 nodes on a bus node, number 33 and number 67 become "token servers"), which corresponds to the midpoint of the requirement for each of the two device-oriented fibers in such a way that a token manager will have the same amount of traffic on both sides.

Q - v «uu 12 = nu ':: = z' = .. = ... =. . -. a n i .. 20 25 30 35 515 497 13 Each time a user request arrives at a node, the node first requires tokens from its manager and then locks them for the entire channel lifetime. When the user sends the message that the channel should be disconnected, tokens are sent back to their manager immediately. All requests are delayed during the token request and the access itself is serialized by a central manager.

The distributed "token manager" is fundamentally more complicated than the centralized one. We tried to keep it as simple as possible. In our method, each emergency regularly sends status information regarding how many free tokens it has. The other nodes store this information in their status tables. A distress that wants increased capacity consults its status table in order to decide on the basis of which node it is to request gaps. The protocol on the initiating page works as follows. When a user request arrives in an emergency: l. If the node has enough free tokens to satisfy the requirement, the node allocates the required amount of slots to the user, and starts up the channel by sending an establishment message to the destination node, and the user then sends data through to use the reserved gaps. Otherwise, the node marks its available tokens as reserved, and then checks its status table: if the total amount of free tokens in the network is not sufficient to satisfy the requirement, the requirement is rejected (blocking). Otherwise, the node requests tokens from nodes with unused capacity.

If one of these nodes receiving a token request does not have the required amount of free slots, it will in any case leave all its available slots. In each case, it sends a response to the requesting node. A node fulfills incoming requirements in strict FIFO (First In First Out) order.

. | I - .- n f .. 20 25 30 35 515 407 šfššfšïi äfzfïïfïïï '14 I i I'. ' .. 'i When a node receives a response to a token request, it marks the gaps it receives in the response (if it receives any tokens) as reserved. Once the node has received a response to all requests it has sent, it either starts the channels or rejects the user request, depending on whether it has or has not received enough, the capacities are marked. If the user requirement is rejected, the gaps are reserved as free again.

At startup, all free tokens are distributed among the network nodes and each node takes at least one of which moves it (them) to an active (them) as a control slot (s).

User requests can now be accepted and tokens can move their free tokens, condition and advertise it between nodes on request.

A weakness with this schedule is that reallocation of time slots can only be started with the help of user requests, and user requests are delayed pending reallocation of tokens. An optimization that we have implemented to remedy this is to also exercise reallocation of time slots in the background. This results in a smaller need to reallocate tokens for requirements that are small and up to medium size.

The pool that contains free tokens can be distributed in other ways than even ones to increase the probability of successful redistribution and to increase the utilization rate.

If fewer nodes manage the pool, the channel blockage is reduced due to the risk that the token reallocation will fail is less. The complete token pool is in this case proportionally distributed (nodes that are close to the slot generator receive more tokens than the nodes that are far from it) among all nodes. Token transfers can occur between any node pair instead of always engaging (server) the node. When the local node contains enough tokens to satisfy an incoming user request, the request can be accepted without any token reallocation. In addition, it is the case that 10 20 25 30 | | ~. vu 515 407 as long as the incoming user requests fit well with the pool distribution, no reallocation is required. Several questions need to be answered before any decision can be made on how the token pool should be distributed.

We will consider the following here: 1. When the local resources in the node are not sufficient to satisfy a user request, which other node should then be asked for more tokens? 2. If a node requests tokens from multiple nodes, how many tokens should it request and should the node reject the request if it receives a fraction of the requested capacity? 3. If the tokens move freely among the nodes, will the token pool be fragmented into small pieces and show that the block token optimization scheme is useless? It was decided that status messages would be used to distribute information about the pool with free tokens.

Status message information is used to help a node select an appropriate node when requesting additional resources. This method concerns the first question mentioned above.

Our schedule works as follows. Each node regularly sends status information about how many free tokens it has. The other nodes store this information in their status tables. A node that needs more capacity consults its status table to determine from which node it can request gaps. The transmitted relationship information provides an approximate view of the current relationship of token information, so that token claims can be rejected because they were sent to nodes that no longer had any tokens to leave.

Status tables are soft information in such a way that the system works even if they are outdated or not available. However, they should improve the likelihood of reallocation procedures succeeding. . | «. = u -1 ø. .m, u. 1: nu. . 1 se a 1 - n ~ - 15 1 1 n. I. u a. N. V | | I f. M n .. 10 20 25 30 35 u ~ | . .- 515 407 ~ - - «m When comparing the centralized (fig. 9) and (fig. 12) one can see that there is a new kind of rejection of the distributed" token manager "basic performance that is frequent in the distributed version when resources are still unused in the system.

A node uses the status table to select node (s) from which it can request tokens. When the requirement reaches the target node, the amount of available capacity may have changed and a smaller amount than the requested one may be returned to the requesting node, resulting in a user rejection.

This situation results in even more unnecessary token relocation and therefore also increases the probability that other nodes receive fewer tokens than they requested. These tokens that are moved in this way are also locked and unused during the transfer.

If the pool is proportionally distributed among a (100s) size to become quite small. When the load is high, large number of nodes, the normal pool will reduce the number of free tokens in the pools even more. If nodes also establish and release channels at a high rate, the amount of free capacity in the individual nodes will jump between maintaining a very small amount of capacity and none at all. If now the average capacity required by a user is large compared to the number of free tokens in a node, several nodes will need to be queried to be able to satisfy the requirement. At this time, the probability increases that one of the requested nodes has no free capacity, which leads to user rejection.

There are several ways to deal with this problem without returning to a centralized model. First of all, we may not need to donate any tokens at all when the complete request cannot be satisfied.

This protocol is used only if only a single node is asked for free tokens, but for multiple nodes. | -. u. n u »nu I u» v nu ». . . .u f. u u ~ f 16 n u n. .- n u u. - - | - nu m u- 20 25 30 35 n: mn 515 407 u - | If asked, it can still result in the cloth being moved or locked in an unused condition. Second, if tokens have been requested and we receive fewer tokens than we requested, we can simply try a new token request procedure several times. This increases the likelihood that a user request will be accepted and that the obtained tools will be used. The cost of a new attempt will be increased signaling and increased access delay, and this may impair the performance of an overloaded network. In addition, the user's retry introduces a longer "set-up" delay for claims to be retried. Third, the user may sometimes want to accept a channel with a lower capacity than what was originally required, rather than being rejected.

For example, if a user receives 50% of what is requested, he may accept this. In Fig. 5, the throughput, which is the ration between the transported user data and the total number of bits transmitted by the fibers, and the asset delay, which is the time between the arrival of a user request and the transmission of the first requested (16 kbytes) minimum acceptable capacities ( l00% 40 slots), 50% (20 data, for small user requirements with varying slots) and 5% (1 slot) planned versus offered cargo.

A lower average minimum of acceptable bandwidth will result in higher throughput. Fig. 6 shows the performance that results if the user (who requests a lb kbyte data transfer) retries up to 8 times before the request is finally blocked. Utilization increases (and blocking decreases) at the expense of increased signaling and longer delays. Several repeated attempts counteract productivity if it happens often.

It is clear that if the user has a flexible requirement, the probability of being rejected will be lower and the throughput will be higher and higher. Any of the configurations presented in Fig. 5 and Fig. 6 can be determined at the time of arrival of a request. A user who has strict requirements for a channel's capacity can do a u 'nu v n. Nu ~ u »v nu. u. n -o n. a n n u 17 n o a. sv o u; : om f. nu W 20 25 30 35 | a - | -n 515 407 retries until sufficient capacity has been allocated, but another may prefer to accept a channel with lower capacity than the requested amount. The remaining simulations presented here are the acceptable minimum bandwidth defined as 50% of the requested capacity.

In general, the average number of adjacent free blocks in a node is small, due to the random movement of tokens, and the varying capacity of users' requirements. This fragmentation makes block token optimization useless, and the access delay is relatively long (milliseconds) for high capacity channels. In order to make block allocation efficient, it is necessary to reduce the fragmentation of free tokens, otherwise fragmentation will be the main contributing factor to access delays for high bandwidth channels at relatively high loads. Channels with low capacity will almost always have a very short channel establishment delay, regardless of the current degree of fragmentation. In the case of door reuse, the fragmentation problem is even greater, as fragmentation can occur in both door and segment dimensions (time and space dimension) (see Fig. 4). In a centralized server version, this is a special application of the general dynamic storage allocation problem. In a distributed token manager, most of the fragmentation is a result of the use of many free pools (one for each node). Two free adjacent tokens can only be joined if they are within the same node.

A distributed scheme that tries to avoid fragmentation if possible and that increases the average size of free token blocks in the nodes has been implemented. This schedule is used both with and without slot reuse.

The scheme works as follows: l. Fix a home node for each token when the network is started and distribute tokens in such a way that tokens that share the same home node always fix an uninterrupted slot- »o -. Q- »a»: v u. H. I .a nu. . \ n _; n n o u 1 18 n n u. n u n n. - v »n nu 15 20 25 30 35 - | ». 1 n u - n | | vv u. nu 1 o ».n o. n a a »n u n». n »n nu a o v q u - n | vu: | | | | vv .u ß: - .n u v .. y n = n .n n n a n n 1 1 1-9 o n u, H | v. _.,,. f., range. The result is a large average token area in the token map shown in Fig. 4.

When two consecutive tokens with slots with the same slot or segment range exist in the free pool, they must be merged into a single token (sometimes a split and merge operation is required). When merging takes place, segment merging must always be prioritized before the slot number merging. (The reason for this is that the tokens 'range over only a small number of segments is less useful for other nodes than when the tokens' range extends over many segments.) Two tokens in succession in segments, which represent at least partly the same slot. range and which exists in a node's free pool, is split to achieve tokens that follow one another in segments and represent the same slot range, which are merged into a single token.

When a node receives a token request from its local user or a user who is at a long distance, a token from the token pool must be selected using the best-fit algorithm in a slot number and segment number dimension. (see Fig. 4). The value of a token is calculated as the area of a token in the token map and we try to select the token that has the smallest area that still satisfies the requested capacity. A cost function can also be defined as a function of, for example, the number of gaps, the number of segments, placement of gaps and placement of segments; however, this feature should be minimized but can still satisfy the required capacity. This mechanism can also be used by servers as they use a centralized token manager.

When a node needs to request tokens from other nodes, it does not ask for small bits from multiple nodes if it is possible to demand larger bits from fewer nodes. The status tables provide this information. Moving tokens is therefore more efficient. . | | . >. . | . u. 515 407 Éïïzzïïïïzf 20. . . . Iaf-n 'z and leads to fewer establishment messages and less fragmentation. Free tokens are sent back to the home nodes when they have been inactive for a significant period of time or after a long relocation.

This scheme returns tokens to the home nodes as a way to increase the probability that two consecutive tokens can be merged into the free list that reduces fragmentation. If the "gravity" of the home node is too strong, the result of the schedule will be fewer shared resources and unnecessary signaling. If it is too weak, fragmentation will remain a problem. The "gravity" can be changed during the operation of the bus.

In order to evaluate the defragmentation mechanism, we performed some other simulations. Three different simulators (A, B, C) were configured. Simulator A was configured so that it would not have any fragmentation at the start time of the simulation and that it would use the defragmentation scheme described above. B started with the maximum fragmentation of the complete resource pool. All tokens had a single slot and no tokens in the "home" nodes before the defragmentation mechanism was activated. Finally, simulator C was started without using the defragmentation mechanism and with maximum fragmentation in the pool. In all cases, hatch reuse was activated and the load was determined to be 80%.

Fig. 7 shows the access delay as a function of simulated time for a 10 km long network. Simulator C started with a long access delay and the delay increased as the signaling channels became congested and the message queues grew. Simulator B, which used the defragmentation mechanism, functioned as poorly as C at start-up, but even after 10 milliseconds, the average access delay was less than 500 microseconds when one second of simulated time had elapsed. Later, the B-curve almost catches up with A, i.e. it merges in. ->. .n f. u. 10 20 25 30 35. ». . : o - - | . u »515 407 -. . «» V the simulator's performance even though it starts almost without any fragmentation at all. The convergence speed depends on the amount of free capacity within the network and thus also on the load. The load during all these simulations was 80%. The defragmentation mechanism clearly improves the access delay and also makes block token optimization meaningful in the distributed model.

Two types of performance measurements are of utmost importance: utilization rate and access delay. The utilization rate is the part of nominal network capacity that is actually used for data transfer, and it measures the efficiency of the network. Access delay is the time from the arrival of a user request to the transmission of the first data in the request, which is an important measure of how traffic from computer communication can be supported.

To begin with, there are two important factors that influence the degree of utilization in DTM. First, each node has signaling capacity in the form of control slots, which means that there are fewer available slots for data transfer on a bus with many nodes, for a given link capacity. Second, "overhead" is introduced with token reallocation because when a slot token is reallocated between nodes, the corresponding slot cannot be used for data transfer. Access delay depends mainly on the load on the control hatches, and on how many control messages need to be sent in order to establish a channel. The access delay is typically a summary of some delays: eg a node controller's process delay (5 ms), delay in searching and allocating free tokens (100 ms), waiting for the first available control (50 ms), the first allocated data slot data (62.5 ms). delayed in queues at the entrance gate the door should pass and finally the wait to be filled with use- that messages become node controllers In addition, waiting for their process. In the simulations that have 21 = = w-.f:; = s '= .. = ... =' = -. f | n. n u. Ü 20 25 30 -. s ~ 1 I «| -. .-. - 4 «1. 515,407 presented below, the average delay is up to a few hundred microseconds.

Results from simulations where DTM is exposed to traffic patterns that are more similar to the relatively short-lived over- (4-4000 kbytes) will be presented here. conducts that can be seen in data communication The types of traffic take place with erratic times between arrivals, client-server-oriented as well as with exponentially distributed arrival times. In the simulation model, each transmission begins with the arrival of a new "packet" of information. The node controller tries to allocate resources for the transmission, transmits the data and finally releases the channel.

This is a simplification of the mechanisms within a real system, where the establishment of the channel, data transfer and the release of the channel are independent operations initiated by the user. As an example, a user who knows that a transmission is to take place can "hide" the channel establishment delay by requesting a channel in advance, so that it is already established when the transmission begins. In the period between the establishment and a release, the capacity within the channel is entirely reserved for the user. The most straightforward use of a channel is for a single transmission, such as a file transmission or a video transmission.

Depending on the characteristics of the application, it may be possible to optimize the use of a channel. A channel can, for example, be used to transmit sequences associated with higher-level messages such as ATM cells or IP packets (this is similar to the use of a single VC for all IP traffic in an ATM network). If the channel has several destinations (multicast), messages to different destinations can be multiplexed on the channel. This means that each message will reach each receiver on the multicast channel and the recipients must be able to filter the messages.

An alternative solution is to create and destroy the channel for each message, but reserve tokens between med- ».. now - .I u v. Ss _. .- -. u o I 22 v u. . n u n n. . <| u 4 »» m W 20 25 ~. «. @. . - 1. n- 515 407 - | - | »- 23 subdivisions so that these tokens will always be available for the following message in the sequence.

This type of user behavior is not incorporated in the simulations, as they are optimizations for specific applications. Instead, the focus is on how the network works without user-level optimizations.

The transmitter can start transmitting data as soon as the resources have been allocated, even before the receiver receives the channel establishment message. This is called fast channel establishment. The receiver will eventually respond with a check message confirming or rejecting the channel.

The user request has the following parameters: I Packet size, which is the amount of user data that is moved between the channel establishment and the channel release. We simulate the packet sizes from a few kbytes up to a few Mbytes. 0 Requested capacity for a channel, which is the number of slots that a node is trying to allocate. For all simulations in this text, the requested capacity is fixed at 40 slots or 20.48 Mbit / s. 0 The minimum acceptable capacity. A node blocks a request if it cannot allocate this number of slots.

This is normally set to 40 or 20 slots (100% or 50% of the required capacity). 0 Source address. 0 Destination address.

The source and destination addresses are generated randomly (all nodes with the same probability) and the times between a user's arrival times are exponentially distributed.

The simulations examine how the effect of signaling capacity and "overhead" due to luck reallocation affects the degree of utilization, channel establishment delay and blocking. We simulate varying traffic conditions, for a topology with the following characteristics: n in »n n» 20 25 35 | . -. ». - »~ | : - 515 407. - -: u u 0 A double-bus network with 100 nodes. Although it is theoretically possible to connect many more nodes to a bus, we believe that network management of networks with more than 100 nodes on a bus will be impractical.

With 100 nodes, the capacity sharing is significant enough to exercise and test the token management protocol.

Each bus has a capacity of 6.4 Gbit / s. We believe that this is realistic for what is feasible within a year or two; 2.4 Gbit / s optical links have been available for a few years, and it has been announced that 10 Gbit / s links will soon be on the market. 6.4 Gbit / s corresponds to 100 MHz slot frequency, which is the speed at which the slot-processing MAC hardware would work at existing CMOS technology. at this achievable speed The total signal capacity is the same for all nodes, but the slots are divided between two fiber directions proportionally, depending on where the nodes are located on the bus. The closer a node is to the slot generator, the more control capacity is needed.

However, the sum of control capacity on both buses will be the same for all nodes. In the network with two token "servers", these "servers" have more control capacity and higher processing capacity than the other nodes.

The length of the bus is 10 km, which provides a sufficiently large network, so that the effects of the spread are not negligible. Results from studies of the effects of spread delay in simulations with different bus lengths are presented in Figures 11 and 13.

Two different models for token management are simulated: an asymmetric scheme where all tokens on a fiber are managed by a single token server and a symmetric scheme where each node controller manages a small part of the global token pool. ~ u »nu n -n w» - u. . v. n 1 1 u u 24 I u. , nu n .I u »- | «| n ».n u. 20 25 30 35. - «. «» »Ø» | nu 515 407 | - | | »O When analyzing the performance of the DTM dual bus network, the question of maximum theoretical performance must be considered and compared with the simulated performance. The maximum theoretical performance is also used in this text to compare the different models and implementations that we evaluate.

The maximum throughput in a double-bus system without door reuse can be defined as twice the link capacity, if the ratio is such that both fibers receive the same traffic. In a system with slot reuse, the throughput of the system also depends on the distribution of source / destination pairs. In order for the double bus to be able to obtain this throughput, we used a Monte Carlo simulation where source and destination addresses were uniformly distributed (Fig. 8). configuration as defined below when using a (see left graph of When compared to a DTM network (simulator-centralized token manager) where the user requests large (4 MB at 20 Mbit / s capacity) the signaling capacity is not a bottleneck (see right transfers and graph of Fig. 8), the utilization is almost ideal.

Real traffic that behaves this way is bulk data transfers and audio / video streams. The differences shown are the result of: Some capacity within DTM is used by control slots that reduce the number of available slots that can be used for data transfers. The random number generators for the DTM system do not generate exactly the same amount of traffic in the upstream and downstream directions. This can result in blocking one of the directions when capacity is available in the other. During channel establishment, resources can be temporarily locked unused, which wastes some capacity.

In the case of the central token manager mentioned earlier, the two nodes responsible for maintenance need more signaling capacity than the other nodes (eight times more control slots are assigned to a server node than to the other nodes). . . <. .u - -. I v »- | x. ~ n - 1 a. »25 - -. ß u ~ H K .. -, 1 - u. a »n. 15 20 25 30 35 | - »-» - 515 407 §ÉÉ = §ÉI§ï = n u 1. n: u v. A 'nu .n c n z n. 1 26 vn »1 n. N nu u» The results from the first set of simulations are presented in Fig. 9. Channels with 20 Mbit / S user request, the times between arrivals are exponentially distributed (generated by a Poisson process) and the simulations are performed with different package sizes. If the entire capacity of a channel cannot be allocated, the request is rejected and the tokens are returned to their token server. Packet sizes vary from 4 Mbytes to 4 Kbytes, at this point you start to see a deterioration of the throughput.

Impairment of the throughput can occur if the process capacity in the nodes or the capacity in the control channel is too small. The server nodes can be particularly congested. The result is that the queues that contain control messages begin to become very large.

The control token represents unused capacity, and therefore the throughput deteriorates.

In the simulations for 4 kbytes per channel, the control capacity is the limiting factor, and if more control slots (signaling capacity) are added, 4 kbytes and even smaller packets can be supported more efficiently.

The following set of curves in Fig. 10 shows how the slot reuse mechanism improves system performance. The throughput increases by almost a factor of two before any significant number of channels are rejected. The uniform distribution of source and destination addresses for the channels limits the amount of increased capacity gained from slot reuse. It has been shown that if the source and destination are evenly generated, as we have done, the throughput can be doubled on a double bus. In the simulations, you can also see that beyond an offered load of 2.5, you can actually get a throughput that is higher than 2.0. However, this level of throughput cannot be achieved without some channels being rejected. The channels with the highest probability of being rejected are those that use many gaps or segments. For this reason, the system filters the less greedy user requirements and discards the others. This is not normally acceptable. -. I I; u m. l5 20 25 30 35 - | -. f u. »-. now 515 407 behavior and we therefore do not investigate this further.

Flow deterioration occurs with an offered load of 1 for transmissions of 4 kbytes. Although sufficient resources are available within the token server, it is not possible to establish and release channels quickly enough because the control channel is overloaded. In addition, one can also see a throughput deterioration of 8 kbyte simulations at an offered load of 1.8, for the same reason.

It can be concluded from the simulations in Fig. 10 that the slot reuse mechanism almost doubles the throughput of the system with only minor changes in the centralized token protocol, as long as the control and server processing capacity is not a bottleneck. In the curves, it can also be unexpectedly seen that the access delay actually decreases when the load increases from 0.1 to 0.5. This is a result of how the slots are allocated within a channel and not from a faster token claim process. The time it takes to request tokens from a server is strictly increasing.

When comparing the DTM performance in Fig. 10 and the theoretical values in Fig. 8, it can be seen that even the short bursts (duration of a few milliseconds) can be effectively supported.

When a single token server is used, each channel establishment requires a token to be requested from a server before the node can establish the channel. If the bus length is increased, the token request will take longer and can therefore limit the throughput and increase the access delay.

In fig. Which the bus length is increased from 100 to 1000 km (node to node distance is now 50 ms). ll show the results of the simulations, in Both the access delay and the throughput are now limited by the propagation time round trip to a token server. The access delay in this case depends on the distance to the servers, but is independent of the transmission size. The degree of utilization depends a lot on the transfer - - nu I nu nu »nu v -fl u vn u -. 1 n q a a n 27 - u n. s »n n n.

. . ,. .I u u. 15 20 25 35 «- ~. a. 515 407 ~ u -. .n., n .nu. n n ~ 28 u o n - m »c nu ef; size because the establishment phase can be amortized during a long data transfer phase. Channels that transmit large amounts of information, such as 256 kbytes, with a duration of one tenth of a second can still be effectively supported when the bus length is 1000 km.

When a centralized token manager is used, you get many benefits. Clients can be simple, as they only contain state information related to their own open channels. Luck reuse is also simple and efficient, as a token server has all the available tokens to choose from when trying to satisfy a user requirement. A server can also implement other policy-related functions such as access control and fairness. The fragmentation of the free pool within a server is normally very modest, which results in very few establishment messages per channel, even when it comes to user requirements that require high capacity.

There are also disadvantages. A user who often establishes and releases channels can introduce excessive signaling by always returning tokens after use, and then requesting these tokens again within a short period of time. The processing capacity of the server node can be overloaded if there are many nodes on the bus or if the average packet size is very small. If the media length is very large in relation to the product of bit period, bits per packet and media speed. The return speed to a server can also limit performance. Finally, the server node contains state information, on which all nodes depend in order to create channels. The failure of a server node can therefore have an effect on all nodes.

In the next paragraph, the properties of a fully distributed token manager are simulated and examined.

When evaluating the performance of a distributed token manager with luck reuse and defragment | ~ - - nu U ..- 15 20 25 30 35 1 a. , .n u. nu I u v: v .... .n v | nu u | n z n n. n. u | u u. n .a u u u u en; u n »; «-« m a; 1 .. ~ n. V - ~. - 1 u 4 .I n n | n r n. .n n »- -n 29 i I I ring, the same traffic and parameters are used as in the case of a central token manager, but with a policy where the requirements are accepted if 50% of the requested capacity can be allocated.

The results presented in Fig. 12 are from a luck reuse simulator, a fully distributed token manager, status messages describing how much capacity a node owns, and the defragmentation scheme. All nodes have the same processing capacity and the processing load is very 10 received. smaller, which results in a higher reliability- lower than that of the receivers in Fig. The dependence between the nodes is also very degree. The system works better than any other system that does not provide door recycling, but not as well as the centralized door recycling system described earlier.

When comparing the performance of this configuration 10, that the blocking is higher and certain requirements can be blocked at and the centralized token manager in fig., One sees a much lower load in the distributed implementation.

An unexpected result was that performance actually decreased as the package size increased! After a further check of the results, it was found that a large average transmission size results in less token movement and that the relational information actually gives an even worse view of free resources within the network than for short transmissions. In this case, a request is rejected if you do not think you should find any resources. This mechanism was introduced to avoid wasting control capacity when resources were depleted.

The reason for this is that the status messages only describe "global" tokens that cover all segments of the bus. A global token can be used by any node and is the only type of token in a DTM system without slot reuse. At a load higher than 1.00 n -u- 20 25 30 35 nu m. ~ -V 'v-I 1 nu u. N 1 n u _ u- v v .- | n »f n u> n n 4- n 1. . «U» v v. .u u »vn. - 1 o o n a o n n. f; u v »., 30 o vo segment a large number of tokens and the reuse scheme needs them to be able to use them for new requests. Therefore, the mechanism of status messages used (and developed for a system without reuse) is limited in its ability to meet new requirements in their search for available capacity, and can in the worst case result in higher blocking.

The throughput and access delay in a distributed token manager with bus lengths from 1 km to 13. A small 16 kbyte packet is sent between the establishment and release of a channel, for (100s of kbytes) in the system much less affected by the bus length. The 1000 km buses are presented in Fig. Large packages, the throughput performance which is 1 km and 100 km gives approximately the same result in terms of throughput and access delay as the 10 km long bus, since the delay introduced when a 125 ms cycle is used dominates the propagation time within the system . Regarding the 1000 km long bus, you can see that the access delay is much shorter than in the 1000 km system when using a centralized token server, especially at low load, when you find tokens very close to the node to which the user request arrives and the delay is about the same in all system. Even at very high loads, the access delay is approximately one millisecond shorter than in the system with a centralized SGIVGI.

The centralized token manager system has the same performance almost independently of the traffic as long as the processing and signaling capacity is sufficient. To be able to evaluate the distributed system, we used two other traffic generators. First, we used a generator that simulates user requirements that arrive in showers. When a request arrives, we defined that a new request would arrive with 90% probability after 200 ms.

The result was that a shower of receivables arrives at a node and forces a high temporal location at the source addresses. Second, to generate traffic that is more similar to w .n 20 25 30 35 - | -. .u 515 407. »- | .w client-server behavior, the amount of traffic that arrived at 25, 50, 75 and 99 increased. the ability to find a server destination is also higher. to 5 server nodes: number O, Probable- Fig. 14 shows the performance of throughput and access delay in the distributed token server system.

It is obvious that the distributed model has several advantages but also disadvantages compared to a centralized token server. The nodes can share the processing load, the need for high-performance token servers is lower, the redundancy can be higher and the access delay can be shorter for lower capacity requirements. The disadvantages are higher blocking for an inflexible user who may therefore have to repeat attempts many times to gain access to the necessary resources. It is also obvious that status messages and the status table mechanism must be changed to avoid unnecessary blocking when door reuse is allowed.

When the burden increases above a certain degree, it becomes difficult to find free tokens, the blockage becomes significant and the utilization increases only marginally with the load. The degree of blockage at a given load depends mostly on the minimum capacity requirements in the user's request. The lower the minimum capacity, the higher the probability that the need will be able to satisfy the requirement. In addition, only one round of token requirements is sent out for each user request in these simulations. Utilization can be increased if you perform several rounds (ie use retry), at the expense of a longer access delay.

Assuming that the above waiting times are independent, the average access delay, if there is a single control slot and if the network has a light load, and the borrowing is not dense, will result in an average access delay of approximately l25 ms (a single cycle ). 31 Z C 2 Z '..' 2 '..'...' ~ ~. - .o m n. 20 25 30 35 515 407 In addition, many control messages may be needed to be able to establish a channel, due to fragmentation, which increases the load on the control channel even more, and thus also the access delay. In fact, without an effective "defragmentation scheme", fragmentation becomes the dominant contributing factor to the access delay in the simulations.

One consequence of DTM's luck reallocation mechanism is that it takes longer to establish channels that require high bandwidth. This compromise can be justified: the type of traffic that needs a short average access delay is usually less sensitive to the amount of bandwidth that has been allocated for the transmission, and such traffic can therefore be accepted without much commitment from the reallocation protocol. For transmissions that require high bandwidth, the access delay will be much longer and will almost always involve the reallocation protocol. In general, however, width transmissions are likely to be less sensitive, high bandwidth- for access delay.

These simulations have shown that DTM's protocol for fast circuit switching shows good performance for a double bus with shared medium. Two models for token management have been analyzed and both perform well and can benefit from luck reuse. The centralized model provides the performance that most closely resembles the ideal case and also results in a simple implementation. The distributed system is more sensitive to user behavior and must therefore be dependent on status information that is sent frequently and on a defragmentation method, in order to reduce the number of control messages required for channel establishment and slot reallocation. If the defragmentation method is used on long buses, the distributed model shows better performance than the centralized model (compare Figures 11 and 13). A resource management system that combines the centralized | - | . . u 1 | ~ .H. a »v u .. - f - .u 0 n». . 32 u I q. f »u n m. .1 ..-« ~ - «.n 515 407 and the distributed model using a small set of token server nodes is also possible.

In addition, "overhead" due to channel tapping can be kept very low, which results in higher utilization even within small (a few kbytes) transmissions. The access delay is found to be a few hundred microseconds even at high loads. The luck reuse method and arrangement of the invention can increase performance by a factor of two without introducing any additional hardware into the nodes. When using the door reuse method, it is important to use the defragmentation method, as fragmentation can occur in both the door and segment dimensions. ~ | -. c. v. , _ n, ha. n. u n .. 1 m 1 o -u f f e 1. 33 u n; i s. v m u. n. u.

Claims (1)

10 15 20 25 30. - - - <- .. ..- 34 515 407 PATENT REQUIREMENTS l. Plan for reusing time slots for increasing throughput in a DTM (Dynamic Synchronous Transfer Mode) network, characterized by - that the DTM block token format is extended so that it includes parameters describing the segment (s) between the source and destination nodes, - that the block token capacity is reserved only for the segment (s) between the source and destination nodes, - that two or more tokens representing the same time slots for the accompanying segment are merged into one single token when they exist within a node's free pole, and - that simultaneous transmissions within the same slot over separate segments within the network are made possible. Schedule for reuse of time slots according to claim 1, characterized in that it is implemented with a centralized method for administering tokens. Schedule for reuse of time slots according to claim 1, characterized in that it is implemented with a distributed method for administering tokens. A plan for reusing time slots according to claim 1, characterized in that it is implemented in a system for managing resources, which combines the centralized and the distributed models, and thereby uses a small set of token server nodes. Schedule for reuse of time slots according to one of Claims 1 to 4, characterized in that it is combined with a defragmentation method, in which - a home node is defined for each token at the start-up of the network or during the work of the network in such a way that the tokens share the same home node always defines a «. . . .- 1 §. . -ø n -f- W Ü 20 25 30. 1 -. .u 515 407 at least partially uninterrupted group of continuous time slots, P - free tokens are returned to their respective home nodes when a significant time has elapsed, and - two or more successive tokens representing the same group of time slots are merged into a single token when they exist in a node free pool. Time slot reuse plan according to claim 5, characterized in that two or more tokens with the same range of time slots or segments are merged into a single token when they exist in a node's free pool. Schedule for reuse of time slots according to claim 6, characterized in that when merging of slots and / or segment-accompanying tokens that have the same slot or segment range, a segment merging is always prioritized before a slot number merging, even if the number of tokens increases. Time slot reuse plan according to one of Claims 1 to 7, characterized in that when a node receives a request for tokens from a local user or a remote user, a token is selected from the token pool by means of an algorithm for the best possible adaptation. in terms of the number and from this time slots and segment length, the algorithm selects the token that has the smallest area in the token map and that can satisfy the requested capacity. Time slot reuse plan according to one of Claims 1 to 7, characterized in that when a node needs to request a token from other nodes and there is no token that can satisfy the requested capacity, the number of tokens that are pre-requisitioned is minimized. Throughput in a DTM (Dynamic Synchronous Transfer Mode) Plan for reusing time slots for network augmentation, characterized in that it includes. | ,. 1 n 11 x .. h. 1 1 | v nu s 1 1 .1 1 a v 1 1 35 1 1 1 V 1. 1 11 H1. . 1 1 1 1 1. 111 10 »a wn 515 407 - an extended DTM block token format, including parameters describing segment (s) between source and destination node, - nodes arranged to reserve block token capacity only on segment (s) between source and destination nodes, - two or more tokens representing the same time slots for accompanying segments and existing within a node's free pole are merged into a single token, and - enabling simultaneous transmissions within the same slot across separate segments of the network. , - v .q u n; u p. «-.» »I .1, I. u 1.-: v I n. . . -; u 36 a a n i s; n .a m. ~. . -IN