SU1499367A1 - Routing device - Google Patents

Abstract

The invention relates to computing and communication technology, in particular, to a technique for building switching nodes on discrete information transmission networks. The purpose of the invention is to increase the speed in the exchange mode and reduce hardware costs. The goal is achieved by eliminating the need to compare the addresses received as part of the message, thus eliminating the need to use the address recognition scheme as part of the device. This is achieved by using the address block 17, performed on the element OR-NOT 19, the inputs of which are connected to the outputs of the memory block 4 of the optimal routes, the delay element 18 and the AND element 20 connected to the output of the decoder 9 of the mode code. 3 il.

Description

(L

FSh.1

31А9

The invention relates to computing and communication technology and can be used in designing data processing devices and building commutators on discrete information transmission networks.

The purpose of the invention is to increase the speed in the exchange mode and reduce meime hardware costs.

FIG. 1 is a block diagram of a routing device; figure 2 - procedure routing network; in fig. 3 is a diagram of an I / O unit.

The device (Fig. 1) contains an input / output unit 1, a multiplexer 2, a multiplexer 3, a block 4 of optimal route memory, a comparison block 5, a relief memory block 6, an address decoder 7, a scan generator 8, a code decoder 9 mode, data demultiplexer 10, block 11 elements OR, adder 12 units, first element AND 13, element NOT 14, second element AND 1-5, element OR 16, and address block 17, which contains delay element 18, the element OR NOT 19 and the element AND 20.

The device has n information

0

67

five

A set of devices connected by duplex communication lines to the inputs and outputs, forms a communication network. In this case, the routing device is a network node, and inputs 21 and video 22 connect it to neighboring nodes.

Suppose that the network solves the problem of finding the set of shortest paths to node A (Fig. 2). In this case, the A-relief is formed from the node A according to the following algorithm.

Node A is assigned a single 5 A-relief value, which is translated in all good directions to adjacent nodes. Neighboring nodes, having obtained a relief, choose the minimum (which in this case is equal to 1), increase the value of the minimum relief by one, and transmit the modified relief value in those output directions that do not contain minimum reliefs. This ensures the directional distribution of the terrain in the network, which eliminates network overload due to reflections and the formation of cycles. Through the final number of translations, equals 0

inputs 21 "connected to the multi-ZO about the maximum height of the relief, in the typelexer 2 and n information you network is formed A-relief, representations connected to the first demultiplexer 3. Input 23 of the installation of the initial state is connected to the control input of the unit 4 memory

35

in terms of the number of communication directions, a set of numbers stored in each node of the network. The value of the height of the relief fa corresponding to this direction is equal to the number of transit nodes on the exchange route to node A in this direction. The set of directions marked with minimum heights of the A-relief forms the shortest path to node A.

optimal routes and block 6 of memory of reliefs.

The input-output unit 1 (FIG. 3) consists of input register 24 and output register 25. The first inputs 26 of the register 24 are connected to the outputs of the multiplex 2, and the second information output 27 of the register 25 is connected to the information inputs of the first demultiplexer 3. The first information output 28 of the information part of the register 24 is connected to the first information input of the second demultiplexer 10. The input 29 information part of the register 25 is connected to the output of the block 11 elements IL. Code 30 and address 31 outputs of the register 24 are connected respectively to the code and address inputs of register 25. At the same time, code output 30 is connected to the input of the decoder 9 of the mode code, and address output 31 to the input of the decoder 7 of the address.

five

0

five

0

five

in terms of the number of communication directions, a set of numbers stored in each node of the network. The height of the relief corresponding to this direction is equal to the number of transit nodes on the exchange route to node A in this direction. The set of directions marked with minimum heights of the A-relief forms the shortest path to node A.

The operation of the device in the exchange mode.

The message arrives at the j-th (j 1,2, ..., p) input 21 in the device. The service code part of this message is from the register, 24 inputs go to output 30, to the decoder 9 of the mode code, at the second output of which a single potential exchange is generated, allowing it to be accessed in memory block 4 of the best routes. The multiplexer 3 switches the I / O unit 1 to the outgoing direction, which is on the shortest path to the final i-th node, in accordance with the control information stored in memory unit 4 of the best routes.

The output direction is connected and determined by the single state of the i-th row of block 4, where i is the address of the destination node transmitted as part of the message. This address, as in the formation mode of the relief, enters the decoder 7 and allows access to the corresponding lines of blocks 4 and 6 of the memory. In this case, the block b does not work, i.e. The second control output of the mode code decoder 9 is set to zero potential. The message is switched in the selected direction and is transmitted to the adjacent node in the direction of the shortest path.

If a message arrives at a node in which a destination subscriber (message receiver) is connected in the f-th direction, then the direction of switching to the subscriber is determined by the address block 17. The route memory line corresponding to this end node contains zeros written to stage of relief formation. At the output of the element OR NOT 19, a single potential is formed, which is fed to the second input of the element 20. To the first input of this element is supplied the control single potential from the output of the decoder 9 of the code. This potential corresponds to the exchange mode. At the third input of the element And 20 receives the same exchange potential, delayed by the time GGD by the delay element 18. The delay time must meet the following condition:

  - pom;

where t f, (5A is the optimal route access time in memory 4. Thus, if the message reached the receiver node, then the output of the AND element 20 of the address block 17 5) is formed by the potential that directs the incoming message in the nth direction to the subscriber - message receiver.

Claims (1)

Claims 50 A routing device comprising a multiplexer, a demultiplexer, a data demultiplexer, a unit adder, an input / output unit, a relief memory unit 55, a comparison unit, an optimal route memory unit, an address decoder, a scan generator. 0 five 0 five 0 five 0 five 0 five a mode code decoder, an OR block, three AND elements, an OR element, a NOT element, the multiplexer’s information inputs are device inputs of the same name, the output of the lightpluxor module is connected to the message input of the I / O unit, the message output of which is connected to the information input terminal of the device; The litter, the outputs of which are outputs of the device, from the first to (n-1) -th outputs of the scan generator (n is the number of communication directions) is connected to the first to (n-1) -th inputs of the multiplexer address and the addresses of the link direction and the relief memory block, the pth output of the scanning generator is connected to the nth input of the multiplexer address, to the first input of the first element I and through the element NOT to the first input of the second element I, the block outputs, the memory of the reliefs are connected to the information inputs of the comparison block The outputs of which are connected to the inputs of the address of the communication direction of the memory block of optimal routes, the outputs of which are connected to the inputs of the first through (n-1) -th digit of the address of the demultiplexer, the input of the n-th digit of the address of which is connected to the code of the third element and The inputs of the installation of OU blocks of reliefs and optimal routes are connected to the input of the initial installation of the device, the code field of the address of the I / O unit is connected to the input of the address decoder, the first of which has its first output (t is the number of devices in the data network ) are connected from the first to the t-th inputs of the address of the relief of the memory block of the reliefs and optimal routes, the output of the floor of the team I The I / O unit is connected to the input of the decoder of the mode code, the first output of which is connected to the second inputs of the first and second I elements, to the inputs of the resolution of the relief memory blocks, optimal routes and comparisons, the second bypass of the mode code decoder memory block of the optimal routes, with the first inputs of the OR element and the third element AND, the output of the information field of the I / O unit is connected to the information input of the data demultiplexer / whose first output is connected to and The information input of the relief memory block, the output of the first element AND is connected to the second input of the OR element, the output of which is connected to the first control input of the data demultiplexer: the second control input of which is connected to the output of the second element AND, the minimum relief of the comparison block is connected to the information the adder input, the output of which and the first output of the data demultiplexer are connected to the first and second inputs of the block of elements OR, respectively, the output of which is connected to K & I.WOfn & t.n R but ts  fffftSK & 1.7 Fig.z Editor V. Petrash Compiled by V. Sychev Tehred L. Serdyukova Order A696 / 49 Circulation 668 VShPSHI State Committee for Inventions and Discoveries at the State Committee on Science and Technology of the USSR 113035, Moscow, Zh-35, 4/5 Raushsk nab. 0 five the input of the information field of the I / O unit, which differs from the fact that, in order to increase the speed in the exchange mode and reduce hardware costs, a delay element and a W-NOT element are introduced into it, and from the first to the (n-1) th inputs an OR-NOT element is connected to the outputs of the first through (n-1) th block of optimal route memory, the output of the IPI-NOT element is connected to the second input of the third AND element, the third input of which is connected to the second output of the mode code decoder through a delay element. 28 19 g5 f (Sjt.3 g7 30 SG Proofreader T.Malets Subscription