Slot reuse method for increasing throughput in DTM network

(54) (56)

OMBUD LA Groth & Co KB

NAME Reuse of time slots, plans and arrangements CALLED PUBLICATIONS:

EP Al 451 426

Computer networks and ISDN systems, vol 24 (1992), no. 2, April 1992, Amsterdam, L Gauffin et al. Multi-gigabit networking based on DTM, a DTM medium access technology with dynamic bandwidth allocation, p.119-130 (57) SUMMARY:

The present invention relates to a method for re-use of time slots and an arrangement for increasing throughput in a DTM (Dynamic Synchronous Transfer Mode) network. Reuse of time slots according to the invention includes extending the DTM block token format so that it also includes parameters that describe segment (s) between the cold and destination node, and reserves block token capacity only on segment (s) between the source and destination node, and allows simultaneous transmissions within the same gap across separate segments of the network. The time slot reuse method may also include merging two or more segment-accompanying tokens, representing the same group of time slots, into a single token when they exist within a node's free pool.

<img file="SE515407C2_D0001.tif" />

The numbers in brackets indicate international identification code, INID code. Letters in clamps indicate international document code.

515 407

TECHNICAL FIELD OF THE INVENTION

The present invention relates to a method for re-use of time slots and an arrangement for increasing throughput in a DTM (Dynamic Synchronous Transfer Mode) network.

DESCRIPTION OF THE RELATED AREA

New communication networks and high-capacity protocols are continuously being developed by the communications industry and in academic research. Developments are often changing and new results are important for those working on developing applications that integrate real-time audio, video and asynchronous communication services. The applications are available in a wide range of networked terminals. The terminals act as hosts and can be almost any electronic device, including small pocket telephones or televisions, multimedia workstations, as well as million-dollar supercomputers. The hosts may have widely different requirements for processing power, and in their needs for communication services. These disparate needs are presently felt in a set of independent network classes. Each network class is optimized for its particular traffic and application: The cable television network uses one-way communication to all users, the capacity of the cable TV networks is divided into channels of fixed capacity transmit video. A telephone network requires 64 kbit / s bidirectional communication, guaranteed capacity and small variations in the delay. Data networks, such as the Internet, allow a large number of parallel network sessions through the use of connectionless packet switching. They also use statistical resource sharing to make effective use of the links. A network for mobile systems requires extra control capacity to flexibly keep track of all active terminals.

With this broad spectrum of applications that exist today and will grow in the future, it is unlikely that one will be able to continue to invent new,

515 407 sometimes global, networks and a new terminal for each new type of service. Instead, a new integrated service network is needed that supports existing services as well as new services. The overall objectives of such a network are to be scalable up to global size and the utilization of costly components is maximized. Optical transmission technology has proven 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 cause new problems that are not present in today's more specialized networks with lower performance. To begin with, as 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. For example, a phone call 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 network that uses connectionless packet switching protocols, e.g. IP (Internet Protocol) has proven to be very scalable. They have evolved from small networks that connect only a small number of DARPA (Defense Advanced Research Projects Agency) research computers in the mid-70s to today's universally spread global Internet. Local networks based on shared media such as CSMA / CD (Carrier Sense Multiple Access / Collision Detection), token ring and FDDI (Fiber Distributed Data Interface) are used within the Internet as simple building blocks, connected with routers or bridges. The combination of simple expansion, low growing costs

515 407 regarding nodes as well as tolerance of incorrect nodes have resulted in simple, flexible and robust networks. In addition, shared medium allows efficient application of new multicast protocols such as IP multicast.

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

The two most important types of networks 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 constantly established between bursts of information, which results in poor utilization of the capacity of the network. This problem arises when switching on and off 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 connecting with multiple receivers (multicast) difficult to implement and they become ineffective. A connection-free packet switched network, on the other hand, lacks resource reservation and thus must supply control information to each message before transmission can begin. In addition, the delay in a connection-free packet switched network cannot be predicted with accuracy and packets can even be lost due to overflow in buffers or incorrect packet 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.

515 407

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

To address the aforementioned problems, the communications industry is focusing on the development of ATM (Asynchronous Transfer Mode). ATM has been proposed for LAN's 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 circuitry networks, but use small fixed size packets, cells, for information transfer. ATM's packet-switched nature means that the network needs many new mechanisms, such as reservation of buffers and service algorithms to determine real-time guarantees for a leash, ie a virtual channel.

Another solution to be able to guarantee real-time concentrates on a circuit-switched network and thus must address the problems of traditional circuit-switching, as described above. A new control protocol for shared media is also applied, and thus the general problems of shared media must also be considered. This design, called DTM (Dynamic Synchronous Transfer Mode), (see ex. Christer Bohm, Per Lindgren, Lars Ramfelt and Peter Sjödin, The DTM Gigabit Network, Journal of High Speed ​​Networks, 3 (2): 109-126, 1994, and Lars Gauffin, Lars Håkansson, and Björn Pehrson, Multi-gigabit networking based on DTM, Computer Networks and ISDN Systems, 24 (2): 119-139, April 1992) use channels as communication abstraction. These channels differ from telephone switches in several ways. For starters, the connection delay is so short that resources can be dynamically allocated / rejected as soon as user needs change character. Second, the channels are unidirectional and thus minimize overhead at communica- tions

515 The 407 cation is single-aligned. Third, they offer multiple transfer capabilities to support different types of needs of users. Finally, the channels can have unlimited destinations (multicast).

DTM channels share many good features with circuits.

No communication of control information occurs after the channel is established, which results in very high utilization of network resources for large data transmissions. The support of real-time traffic is natural; no monitoring of user behavior, congestion control or flow control is required within the network. The control information is different from user information, which makes communication to several destinations less complex. The source delay is negligible (ie less than 125 ps) and the risk of data disappearing due to missing congestion due to overcrowded queues such as within ATM. The probability of bit errors depends directly on the underlying link technology, and the channel connections are simple and fast because of strict resource reservation at the channel establishment.

DTM can also show good performance in areas where traditional circuit-switched networks show shortcomings: dynamic bandwidth allocation, source delay, and as a network 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 accomplished by applying a slot reuse method and an arrangement that improves the use of shared links and as a result, an increased throughput (througput) in the DTM network.

The method for reusing time slots according to the invention comprises an extension of DTM block token form

515 407 which calculates parameters describing the segments between the source and the destination node, and reserves the block token capacity solely on the segments between the source and the destination node, allowing simultaneous transmissions in the same slot across separated segments within the network.

Luck reuse can also include merging two or more segment consecutive tokens representing the same group of time slots, into a single token, when it exists in a node's free pool.

The method and arrangement for the reuse of time slots according to the invention prevents the above mentioned problems. The method allows channels to reserve capacity only 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, as 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 for administering tokens. 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 source and destination node pairs are uniformly distributed, it has been shown that the throughput can be doubled.

A further advantage is that performance gains can be even higher in other types of networks; for example, in a double ring 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, profits can be much higher.

Another benefit is that performance is enhanced when combined with a defragmentation method, which returns tokens to their home nodes, as a way to increase the likelihood

515 407 that two consecutive tokens can be merged into the free pool of nodes, reducing fragmentation.

BRIEF DESCRIPTION OF THE DRAWINGS

The invention will be described in more detail below, with reference to the accompanying drawing, in which Figure 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 showing the reuse of slots according to the invention.

Fig. 5 illustrates the performance (throughput and access delay, versus the load offered) for small user requirements (16 kbytes) and for different minimum acceptance capabilities simulated when using a distributed (token server) according to the invention; 6 shows the performance for small user requirements (16 kbytes) and for different number of allowed attempts before the request is blocked, which has been simulated by means of a distributed token server according to the invention, fig. 7 illustrates the access delay as a function of simulated time, using 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. 8 illustrates theoretical throughput for a DTM double bus versus offered load for a dual bus DTM network with and without reuse of time slots; Fig. 9 illustrates the performance of the different packet sizes simulated using a central token

515 407 ^....... ·· 'manager within a 10 km long double bus DTM network without luck reuse.

Fig. 10 illustrates performance for different packet sizes simulated using a central token manager within a 10 km long dual bus DTM network with re-use of time slots according to the invention; Fig. 11 illustrates performance for different packet sizes simulated using a central token manager within a 1,000 km long DTM network with reuse of time slots according to the invention, fig. 12 illustrates performance for different packet sizes simulated using a distributed token manager in a dual bus network with defragmentation and re-use of time slots according to the invention; time slots according to the invention, and fig. 14 illustrates the performance of different traffic conditions simulated with the help of a distributed token manager in a dual bus network with defragmentation and reuse of time slots according to the invention.

DETAILED DESCRIPTION OF THE CHAIRMAN

To begin with, the DTM MAC (Medium Access Control) protocol should be described. The basic topology of a DTM network is a bus with two unidirectional optical fibers that interconnects all nodes, as illustrated in Fig. 1. Multiple buses at different speeds can be connected together to form an arbitrary multi-stage network. 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

515 407 which can be of different capacities and reach multiple receivers (multicast).

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

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

In each network node there is a node controller (NC or node controller), which controls the availability of data slots and performs management operations, such as during network start-up and troubleshooting. The most important tasks that the node controller has are to create and terminate channels when required by the users, and to manage the network resources in accordance with user requirements and in the background.

Control hatches are used only 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. Because 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 a node uses may vary during network operation.

The network is not limited to a double bus, but can be applied with other types of structures, for example a ring structure with an arbitrary number of nodes. Transmissions

515 In addition to optical fibers, the medium may be coaxial cable or some other high bandwidth transmission medium. Hereafter, the transmission medium will be referred to as optical fibers. The bandwidth of the DTM dual bus within 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 within networks with cycles and time slots of any size.

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

Channel establishment and bandwidth allocation control messages carry sets of slots or tokens as parameters. However, a control message is 64 bits and can therefore only have a small number of parameters. This means that if a user requests a large bandwidth transmission, it may be necessary to send multiple control messages to create the channel. This means extra access delay and slows down signaling capacity.

We are considering a number of mechanisms to reduce the amount of information that needs to be transmitted during channel creation and redistribution of tokens. The first optimal way in token management is to introduce block tokens. A block token is transmitted in a single control message and represents a group of tokens, but can only be used in specific combinations of tokens. For example, in the simulator, a block token is denoted by a slot number indicating the position of the door in the cycle and one

515 407 numbers that divide 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 referred to as 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. Fig. 3 shows an example of how three tokens (A, B and C) are reserved for three channels. The nodes are interconnected by bus segments and the channels typically use a subset of segments on the bus (gray color) and the rest are reserved (white color) but remain unused and thus waste with shared resources. A better alternative is to have the channels 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 slots as channels A and C, but on different segments. This is called slot reuse. Luck reuse enables simultaneous transmissions in the same slot across separate segments of the bus.

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

With slot reuse, the complexity of the access scheme increases, whether it is done in hardware like in DQDB, Simple and CRMA; or in software, as in DTM. When implemented in systems other than DTM, slot reuse also adds complex hardware to the critical

515 407 high-speed road 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 describing the segments it represents. According to the invention, the token management protocol is also modified 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 found that throughput can be increased by double. The performance gain may even be higher in other network types: for example, in a double-ring structure with source and destination nodes that are uniformly distributed, throughput can be increased by four-fold. If source and destination nodes are not uniformly distributed, the profit can be even higher.

However, the potential problem of slot reuse in a DTM network is, however, the higher algorithm complexity and finally higher load for the node controller and signaling channels (especially if the average channel duration is short).

Two token management schedules have been evaluated. The first and simplest is to let a single node controller control all the free tokens for a fiber. This type of centralized (server) mechanism has also been used in systems such as CRMA, where the main end node distributes fiber capacity to all other nodes. The simulator was set up in such a way that for each fiber there was a node that remained at a third of the distance from the slot generator, and this was the token server (with 100 nodes on a bus node being number 33 and number 67 token servers). This 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.

515 407

Each time a user request arrives at a node, the node firstly requires the tokens from its manager and then locks them throughout the channel lifetime. When the user sends the message that the channel should be disconnected, the tokens are immediately returned to their manager. All requests are delayed during the request of the token 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 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 wants increased capacity consult its status table to determine from which node it will request gaps. The protocol on the initiating page works as follows. When a user request arrives at a node:

1st If the node has enough free tokens to satisfy the requirement, the node allocates the required amount of slots to the user, and launches the channel by sending an establishment message to the destination node, and the user then sends the data using the reserved slots.

2nd Otherwise, the node marks its available tokens as reserved, and then checks its status table: if the total amount of available 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 that receives a token request does not have the required amount of available slots, it will in any case leave all of its available slots. In any case, it sends a response to the demanding node. A node fulfills incoming requirements in strict FIFO (First In First Out) order.

515 407

When a node receives a response to a token requirement, it marks the gaps it receives in the response (if it receives any tokens) as reserved. When the node has received a response to all requests it has sent, it either starts the channels or rejects the user, depending on whether or not it has sufficient capacity. If the user requirement is rejected, the reserved hatches are marked vacant again.

At the start, all free tokens are distributed among the network nodes and each node takes at least one of its free tokens, moves it (s) to an active state and advertises it (s) as a control slot (s). User requests can now be accepted and tokens can be moved between nodes upon request.

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

The pool containing free tokens can be distributed in ways other than equal 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 because the risk of the token reallocation failing is less. In this case, the complete token pool is proportionally distributed (nodes close to the slot generator receive more tokens than nodes far from it) among all nodes. Token transfers can occur between any node pair instead of always engaging the (server) node. When the local node contains enough tokens to satisfy an incoming user request, the requirement can be accepted without any token reallocation. In addition, it is so that

515 407 as long as the arriving user requests fit well with the pool distribution, no reallocation is needed.

Several questions need to be answered before any decision can be made on how to distribute the token pool. We shall consider the following here:

1st When the local resources in the node are not sufficient to satisfy a user request, what other node should be asked for more tokens?

2nd 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?

3rd 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 pool information with free tokens. Status message information is used to help a node select a suitable node when requesting additional resources. This method applies to the first question mentioned above.

Our schedule works as follows. Each node regularly sends status information about how many available 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 ratio information provides an approximate view of the current token information ratio, so that token requirements 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 unavailable. However, they should improve the likelihood of reallocation procedures succeeding.

515 407

When comparing the centralized (Fig. 9) and distributed (Fig. 12) token manager basic performance, one can see that there is a new kind of rejection that is frequent in the distributed version when resources are still unused in the system.

A node uses the status table to select the 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 can be returned to the requesting node, resulting in a user rejection.

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

If the pool is proportionally distributed among a large number of (100's) nodes, the size of the normal pool will be quite small. When the load is high, the number of available tokens in the pools decreases 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 retaining 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 likelihood that one of the requested nodes has no available capacity increases, which results in user rejection.

There are several ways to deal with this problem without reverting 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 requested for free tokens, but for multiple nodes

515 407, it can still result in the tokens being moved or locked in an unused state. Second, if tokens have become in demand and we get fewer tokens than we requested, we can simply try a new token request procedure several times. This increases the likelihood that a user request is accepted and that obtained tokens will be used. The cost of a new trial will be increased signaling as well as increased access delay, and this can degrade the performance of an overloaded network. In addition, the user's retry introduces longer set-up delay for claims to be retried. Third, the user may sometimes want to accept a channel with a lower capacity than originally required rather than being rejected.

For example, if a user receives 50% of the requested, he may accept it. In Fig. 5, the throughput, which is the ration between 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 data, for small (16 kbyte) user requirements with varying minimum acceptable capacities (100% 40 hatches), 50% (20 hatches) and 5% (1 hatch) planned versus offered load. A lower average minimum of acceptable bandwidth will result in higher throughput. Figure 6 shows the performance that results if the user (who requests a 16 kb data transfer) retries up to 8 times before the request is finally blocked. The utilization increases (and the blocking decreases) at the expense of increased signaling and longer delay. A number of 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 all the better. 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 so

515 407 retry until sufficient capacity has been allocated, but another might rather accept a channel with lower capacity than the amount requested. 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 user requirements. This fragmentation makes the block token optimization useless, and the access delay is relatively long (milliseconds) for high capacity channels. In order to make block allocation effective, it is necessary to reduce the fragmentation of free tokens, otherwise fragmentation will be the main contributing cause of access delay for high bandwidth channels at reasonably high loads. Low capacity channels will almost always have a very short channel establishment delay regardless of the current degree of fragmentation. In the case of hatch reuse, the problem of fragmentation is even greater, as fragmentation can occur in both hatch 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 results from 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 which increases the average size of free token blocks in the nodes has been implemented. This scheme is used both with and without hatch reuse. The schedule works as follows:

1st Fix a home node for each token when the network is started up and distribute tokens so that tokens sharing the same home node always fix an uninterrupted slot

515 407 range. The result is a large average token area in the token map shown in Fig. 4.

2nd When two tokens with consecutive hatches with the same hatch or segment range exist in the vacant pool, they must be merged into a single token (sometimes a repeated splitting and merging operation is required). When merging occurs, segment merging should always be prioritized prior to slot number merging. (The reason for this is that tokens range over only a small number of segments is less useful for other nodes than when tokens range extends across many segments.) Two consecutive tokens in segments, which represent at least partially the same slot range and exist in a node's free pool, is split to obtain consecutive tokens in segments representing the same slot range, which are merged into a single token.

3rd When a node receives a token request from its local user or a remote user, a token from the token pool should be selected using the best-fit algorithm (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, the location of gaps and the location of segments; however, this function should be minimized but can still satisfy the requested capacity. This mechanism can also be used by servers when using a centralized token manager.

4th 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 require larger bits from fewer nodes. The status tables provide this information. Moving tokens is therefore more efficient,

515 407 and results in fewer establishment messages and less fragmentation.

5th Vacant tokens are sent back to the home nodes when they have been inactive for a significant period of time or after a long move.

This schedule returns the tokens to the home nodes as a way to increase the likelihood that two consecutive tokens can be merged into the free list that reduces fragmentation. If the home node's gravity is too strong, the results of the schema become fewer shared resources and unnecessarily signaling. If it is too weak, the fragmentation will remain as a problem. The gravity can be changed during the bus operation.

To evaluate the defragmentation mechanism, we performed some other simulations. Three different simulators (A, B, C) were configured. Simulator A was configured in such a way 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 complete fragmentation of the complete resource pool. All tokens had a single slot and no tokens in the home nodes before activating the defragmentation mechanism. 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 set at 80%.

In Fig. 7, the access delay is shown as a function of simulated time for a 10 km long network. Simulator C started with long access delay and the delay increased as the signaling channels became overloaded and the message queues grew. Simulator B using the defragmentation mechanism worked just as poorly as C at startup, but even after 10 milliseconds, the average access delay was less than 500 microseconds. Later, when a second of simulated time had passed, the B-curve almost catches up with A, ie it coincides in

515 407 simulator performance even though it starts almost without any fragmentation whatsoever. The congestion rate depends on the amount of available 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 the utmost importance: utilization rate and access delay. The utilization rate is the part of nominal network capacity 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 utilization rate 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 gap token is reallocated between nodes, the corresponding slot cannot be used for data transfer.

Access delay mainly depends on the load on the control slots, 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: e.g., a node controller's process delay (5 ms), search latency and allocation of available tokens (100 ms), the wait for the first available control slot to pass (50 ms), and finally the wait for that the first allocated data cover should be filled with user data (62.5 ms). In addition, messages will be delayed in queues at the gateway to node controllers waiting for their process. In the simulations that have

515 407 presented below is the average delay 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 transmissions (4-4000 kbytes) that can be seen in data communication will be presented here. The types of traffic occur with bursting times between arrivals, client server oriented as well as with exponentially distributed arrival times. In the simulation model, each transfer begins with the arrival of a new package 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 channel establishment, data transfer and the channel release are independent operations initiated by the user. As an example, a user who knows that a transfer is to take place can hide the channel establishment delay by requesting a channel in advance, so that it is already established when the transfer is initiated. During the time between establishment and release, capacity within the channel is entirely reserved for the user. The most direct use of a channel is for a single transmission, such as a file transfer or a video transmission.

Depending on the characteristics of the application, it may be possible to optimize the use of a channel. For example, a channel can be used to transmit sequences belonging to 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 multiple destinations (multicast), messages to different destinations can be multiplexed on the channel. This means that each message will reach every recipient 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 the tokens in between

515 407 shares so that these tokens should always be available for the following message in the sequence.

This type of user behavior is not included 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 resources have been allocated, even before the receiver receives the channel setup message. This is called rapid channel setup. The recipient will eventually respond with a check message confirming or rejecting the channel.

The user request has the following parameters:

• Package size, which is the amount of user data that is moved between the channel setup and the channel release. We simulate packet sizes from a few kbytes up to a few Mbytes.

• Requested capacity for a channel, which is the number of slots that a node tries to allocate. For all simulations in this text, the requested capacity is fixed to 40 slots or 20.48 Mbit / s.

• 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 hatches (100% or 50% of the requested capacity).

• Source address.

• 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 investigate how the effect of signaling capacity and overhead due to luck reallocation affects utilization rate, channel establishment delay and blocking. We simulate varying traffic conditions, for a topology with the following characteristics:

515 407 • 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, capacity sharing is significant enough to practice and test the token management protocol.

• Each bus has a capacity of 6.4 Gbit / s. We believe this is realistic for what is feasible within one or a few years; 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 shutter speed, which is the speed at which the slot-processing MAC hardware would operate at this achievable speed with existing CMOS technology.

• The total signal capacity is the same for all nodes, but the gaps are split between two fiber directions proportionally, depending on where the nodes are located on the bus. The closer a node is to the gate 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 bus length 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 scattering delay in simulations with different bus lengths are presented in Figures 11 and 13.

• Two different token management models are simulated: an asymmetric scheme where all tokens on a fiber are managed by a single token server and a symmetrical scheme where each node controller manages a small portion of the global token pool.

515 407

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 slot 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 hatch reuse, the system's throughput also depends on the distribution of source / destination pairs. In order for the double bus to obtain this throughput, we used a Monte Carlo simulation where source and destination addresses were uniformly distributed (see left graph of Fig. 8). When compared to a DTM network (simulator configuration as defined below when using a centralized token manager) where the user requests large transfers (4 MB at 20 Mbit / s capacity) and the signaling capacity is not a bottleneck (see right graph of Fig. 8). , utilization is near 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 which reduce the number of available slots that can be used in data transfers. The random 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 of one of the directions when capacity is available in the other. During channel setup, resources can be temporarily locked unused, wasting some capacity.

In the case of the central token manager mentioned earlier, the two nodes responsible for the management need more signaling capacity than the other nodes (eight times more control slots are assigned to a server node than to the other nodes).

515 407

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 packet sizes. If the entire capacity of a channel cannot be allocated, the request is rejected and the tokens are returned to their token server. Package sizes vary from 4 Mbytes to 4 Kbytes, at which point you begin to see a deterioration in throughput.

Impairment of throughput can occur if the processing capacity of the nodes or the capacity of the control channel is too small. The server nodes can be especially congested. The result is that the queues containing control messages start to become very large. The control tokens represent unused capacity, and therefore throughput deteriorates.

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

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 found 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 a offered load of 2.5, you can actually get a throughput higher than 2.0. However, this level of throughput cannot be achieved without rejecting any channels. 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

515 407 behavior and we are therefore not investigating this further. Throughput deterioration occurs at an offered load of 1 at 4 kb transmissions. Although sufficient resources are available within the token server, it is not possible to establish and release channels quickly enough as 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 system throughput with only minor changes in the centralized token protocol, as long as the control log server processing capability is not a bottleneck. In the curves, you can also unexpectedly see that access delay actually decreases as the load increases from 0.1 to 0.5. This is a result of how the gaps are allocated within a channel and not from a faster token requirement process. The time it takes to request tokens from a server increases strictly.

When comparing the DTM performance of Figure 10 and the theoretical values ​​of Figure 8, it can be seen that even the short bursts (a few milliseconds duration) 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 throughput and increase the access delay.

Figure 11 shows the result of the simulations, in which the bus length is increased from 100 to 1000 km (node ​​to node distance is now 50 ms). Both the access delay and the throughput are now limited by the round-trip propagation time 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 greatly on the size of the transfer 515 407 since the establishment phase can be amortized during a long data transfer phase. Channels that transmit large amounts of information, such as 256 bytes, with a duration of one-tenth of a second can still be effectively supported when the bus length is 1000 km.

When using a centralized token manager, 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 effective, since a token server has all 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, resulting in very few establishment messages per channel, even when it comes to user requirements that demand high capacity.

There are also disadvantages. A user who frequently establishes and releases channels can introduce excess signaling by always resending tokens after use, and then requesting these tokens again within a short period of time. The processing capacity of the server node can become 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 rate to a server can also limit performance. Finally, the server node contains state information that all nodes depend on to create channels. The failure of a server node can therefore have an effect on all nodes.

The next section simulates and examines the properties of a fully distributed token manager.

When evaluating the performance of a distributed token manager with luck reuse and defragmentation

515 407 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 Figure 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 much lower than the receivers in Fig. 10. The dependence between the nodes is also much less, which results in a higher degree of reliability. The system works better than any other system that does not provide hatch reuse, but not as good as the centralized hatch reuse system described earlier.

When comparing the performance of this configuration with the centralized token manager in Fig. 10, you see that the blocking is higher and some requirements can be blocked at a much lower load in the distributed implementation.

An unexpected result was that the performance actually decreased as the package size increased! After further checking the results, it was found that a large average transfer size results in less token movement and that the relationship information actually gives an even worse view of free resources within the network than for short transfers. 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 kind of token in a DTM system without slot reuse. At a load higher than 1.00

515 407 a large number of tokens are segmented and the reuse schedule needs them to use them for new queries. Therefore, the status message mechanism used (and developed for a system without reuse) is limited in its ability to meet new requirements in their capacity search, and may, in the worst case, result in higher blocking.

The throughput and access delay in a distributed token manager with bus lengths from 1km to 1000km is presented in Fig. 13. A small 16 kbyte packet is sent between establishing and releasing a channel, for large packets (100 kbytes) the throughput performance in the system is very less affected by bus length. The buses that are 1 km and 100 km give about the same results 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. With regard to the 1000 km 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 the tokens are very close to the node to which the user request arrives and the delay is approximately the same in all system. Even at very high loads, the access delay is about a millisecond shorter than in the system with a centralized server.

The centralized token manager system has the same performance almost independent of traffic as long as processing and signaling capabilities are sufficient. To evaluate the distributed system, we used two other traffic generators. First we used a generator that simulates user requirements arriving in bursts. When a request arrives, we defined that a new request would arrive with 90% probability after 200 ms. The result was that a burst of claims arrives at a node and forces a high temporal location at the source addresses. Second, to generate traffic that is more similar

515 407 client-server behavior, the amount of traffic that arrived at 5 server nodes was increased: numbers 0, 25, 50, 75 and 99. The probability of finding a server destination is also higher.

In Fig. 14, the performance of throughput and access delay in the distributed token server system is presented.

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 clear that status messages and the status table mechanism must be changed to avoid unnecessary blocking when slot reuse is allowed.

When the load increases over a certain degree, it becomes difficult to find free tokens, the blocking becomes significant and the utilization only increases marginally with the load. The degree of blocking at a given load depends mostly on the minimum capacity requirements of the user's request. The lower the minimum capacity, the higher the probability that the node will be able to satisfy the requirement. In addition, only one set of token requirements is issued for each user request in these simulations. The utilization can be increased if several rounds (ie using retries) are implemented, at the expense of longer access delay.

Assuming that the aforementioned waiting times are independent, the average access delay, if a single control slot exists and if the network has a light load, and the loan is not tight, will result in an average access delay of about 125 ms (a single cycle ).

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 any effective defragmentation scheme, fragmentation becomes the dominant contributing cause of the access delay in the simulations.

One consequence of DTM's slot 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 allocated for the transmission, and such traffic can therefore be accepted without particularly much commitment by the reallocation protocol. For transmissions that require high bandwidth, the access delay will be much longer and will almost always involve the reallocation protocol. Generally, however, high bandwidth transmissions will probably be less sensitive to access delay.

These simulations have shown that DTM's protocol for fast circuitry shows good performance for a dual bus with shared medium. Two models of token management have been analyzed and both perform well and can benefit from luck reuse. The centralized model provides the performance most closely resembling the ideal case and also results in a simple implementation. The distributed system is more sensitive to user behavior and must therefore be in a dependency relationship to frequently transmitted status information and to a defragmentation method, to reduce the number of control messages required for channel establishment and slot reallocation. Using the defragmentation method 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

515 407 and the distributed model using a small set of token server nodes is also possible.

In addition, due to channel establishment, overhead can be kept very low, resulting in higher utilization even within small (a few kbytes) transmissions. Access delay is found to be a few hundred microseconds even at high load. The Luck reuse method and arrangement according to the invention can increase the performance by a factor of two without introducing any additional hardware into the nodes. When using the gap reuse method, it is important to use the defragmentation method, as fragmentation can occur in both the gap and segment dimensions.

515 407