FR2725094A1 - Digital data packet transmission network e.g. for international data transmission - Google Patents

Abstract

The invention relates to a packet digital data transmission network. The network comprises between at least one switch (1) and subscriber terminal equipment (AB1 to AB3) at least one subscriber link formed by a public subscriber concentrator in frame mode, CPAT concentrator, placed at the head of the network, CPAT concentrator of head (2), and at least one remote CPAT concentrator (4) interconnected by a bidirectional multiplexed link (3). The external subscriber frames are divided into fragments transmitted, in anticipation of the end of the external frame, between central and remote CPAT in the form of messages made up from fragments originating from external frames of different subscribers. A flood routing method makes it possible, by reaching all the nodes or CPATs of the network by a routing message, to establish a forward path and a return path for routing data, optimum for the crossing time of the network. Application to telecommunications.

Description

NETWORK FOR TRANSMITTING DIGITAL DATA BY PAOUETS a
FRAME MODE CONCENTRATION AND DATA ROUTING METHOD
CORRESPONDING
The present invention relates to a packet digital data transmission network, in frame mode concentration, and to a corresponding data routing method.

 Digital packet data transmission networks are currently used for the transmission of digital data, carrying information of all kinds, over large national or international territories.

In general, these networks allow the transmission of successive information on a line, information subdivided into digital data packets separated by rests, each packet comprising useful data and service data, which allow the routing of packets to the chosen destination. They include for example either one or more private transmission lines, or usually a connection of a plurality of subscribers to the public network via public subscriber hubs, designated by CPA. The public subscriber hubs currently used for connection to the public network are the public packet subscriber hubs designated by CPAP. For a more detailed description of the aforementioned transmission mode, one can usefully refer to the booklet entitled "SPECIFICATIONS
TECHNIQUES FOR USING THE NETWORK "published by and available at the plaintiff's registered office, leaflet 11th TEC update 05.11 / 90.

 The implementation of such concentrators involves a configuration of connection of each subscriber to the attachment concentrator CM as shown in FIG. 1, each subscriber AB being connected by a line MA, MC to the attachment concentrator which allows, in a conventional manner, the data transmission in the form of successive packets. Thus, each subscriber AB has a terminal data transmission equipment, DTE, connected to a modulator-demodulator, MA, which is connected to the home switch by a line, linked to a switch modulator MC, the subscriber links switch with a star configuration.

Experience shows that a significant number of subscribers
AB uses a low or medium data transmission rate, these rates ranging from 1,200 to 19,200 bits / second.

 In addition, each subscriber uses a small percentage of the speed of their connection line, less than 10% on average of their maximum speed during peak hours. Subscriber connection lines are therefore notoriously underused.

 Another drawback of the connection system used results from the star structure of the latter, each subscriber connection line, apart from its common connection to the attachment switch, being structurally and functionally independent.

 The object of the present invention is to remedy the aforementioned drawbacks by implementing, at the level of the subscribers connection to the home switch, a digital packet data transmission network making it possible, in particular, to use common transmission resources of the aforementioned data, from or to the home exchange, in order to ensure the connection of each subscriber to the home exchange.

 Another object of the present invention is the implementation of a digital packet data transmission network allowing between two points of this network, such as a data transmission terminal, DTE terminal, and the home switch, to ensure a diversity of links, by successive different branches of the network, which makes it possible in the event of an incident on one of the constituent branches of a link to replace this branch, or a succession of branches comprising the latter, by a succession of different branches and thus secure and make the transmission of data more reliable.

 Another object of the present invention is the implementation of a packet data transmission network in which the nodes of the network, junction points of several branches of data transmission, ensure routing of the data transmitted by packet, each network node operating, to ensure this transmission, independently and recognizing itself its operating parameters, by learning its environment.

 Another object of the present invention is finally in a digital packet data transmission network, provided with previously mentioned autonomous nodes, the implementation of a routing process, called flooding, of the digital data transmitted in packets between two any determined nodes, method in which all the nodes of the network are reached by a routing probe message, which makes it possible to define a routing path formed by a return path respectively between said predetermined nodes.

 The packet digital data transmission network, between a switch and a plurality of subscribers, via subscriber access links, object of the present invention, is remarkable in that this network comprises, connected to the switch, at least one subscriber link formed by a public subscriber concentrator in frame mode, designated by CPAT concentrator, placed at the head and designated by head CPAT concentrator, and at least one remote CPAT concentrator, the head and remote CPAT concentrators being interconnected by a bidirectional multiplexed link, the head and remote CPAT concentrators allowing the transmission of external subscriber data frames between the switches and subscriber access links.

 The method for routing digital data transmitted in packets, in the form of data frames, over a data transmission network constituted by a plurality of nodes, each comprising a determined number of input-output ports interconnected with an adjacent node by bidirectional transmission lines constituting branches, to establish a routing channel between a generator node and a destination node, the other nodes constituting transit nodes, each of the nodes being identified by an address, the routing channel being constituted by a return path respectively formed each by a succession of branches, is remarkable in that it consists in transmitting from the generator node a routing probe message dedicated to the destination node on all the input-output ports of the generator node connected to an adjacent downstream node, forming a transit node. Following the receipt of the routing probe message by each downstream adjacent node, the routing probe message is completed by concatenation with the address code of the downstream adjacent node considered to form a completed routing probe message dedicated to the destination node. The completed routing probe message dedicated to the destination node is sent from each of the adjacent downstream nodes, on all of the input-output ports of the latter connected to a new adjacent downstream node. The previous concatenation and transmission steps are repeated for any new downstream adjacent node, so that the completed routing probe message reaches all the nodes of the network. On first reaching of the destination node by the completed routing probe message, the outward path is defined by the set of addresses of the transit nodes crossed, contained in the completed routing probe message.

 From the recipient node, operating as a sub-generator node, the preceding steps are repeated towards the generator node, operating as a sub-recipient node, by means of the completed routing probe message dedicated to the sub-recipient node. On the first reaching of the sub-recipient node by the completed routing probe message, the return path is defined by all the addresses of the transit nodes crossed from the sub-generator node to the sub-recipient node contained in the completed routing probe message. and the routing path is formed by the set of addresses of the transit nodes forming the outward path and the return path.

 The packet-based digital data transmission network in frame mode and the data routing method on such a network, objects of the present invention, find application in the field of telecommunications for the transmission of digital packet data regardless of the nature of the information transmitted, digital or video-digital, alphanumeric signals for example.

A more detailed description of a digital packet data transmission network in frame mode concentration and of the corresponding data routing method will be given in relation to the drawings in which, in addition to FIG. 1 relating to the prior art
FIG. 2a represents a digital data network in packets with frame mode concentration, network of CPAT concentrators, in accordance with the object of the present invention,
FIGS. 2b to 2e represent, by way of nonlimiting example, different configurations of networks of CPAT concentrators capable of being produced in accordance with the object of the present invention,
FIG. 3a represents a block diagram of the structure of a CPAT concentrator allowing the production of a network of CPAT concentrators, as represented in FIGS. 2a to 2e,
- Figure 3b shows by way of illustrative example a process of constitution and transmission of shuttles formed by elementary messages, or fragments, emitted by different subscribers connected to a switch by means of a network of CPAT concentrators, according to a configuration similar to that of the hub network
CPAT shown in Figure 2d,
FIGS. 4a and 4b represent the structure of a shuttle comprising a priority key for transmitting a fragment or elementary message transmitted by a subscriber, respectively the structure of a shuttle to be transmitted by a current CPAT concentrator and the process of transmission according to the transmission priority key of the constituent fragments of this shuttle,
- Figure 5a shows, schematically, the successive operations implemented, within a current CPAT concentrator, to produce an internal frame formed of different fragments to be transmitted from one or more external frames supporting a message generated by one or more subscribers, in the case of subscriber connection links to a multiplexed link connected to a downstream CPAT concentrator,
- Figure 5b shows, schematically, the successive operations implemented, within a current CPAT concentrator to produce an external frame to be transmitted, from an internal frame formed of different fragments, in the case of a multiplexed link to a connection link of a destination subscriber,
FIGS. 6a and 6b represent a sequential flowchart of the operations previously illustrated in FIG. 5a respectively 5b,
FIG. 7a represents, purely by way of illustration, a network of CPAT concentrators, each CPAT concentrator of the network forming a node,
FIG. 7b represents a sequential flowchart of the operations implemented for, starting from any node of the network considered as generator node, establishing an information exchange route with a recipient node,
FIG. 8a represents, in general, a network of topology similar to that of the network of FIG. 7a, the nodes of the network can be any but allowing at least to ensure a function similar to that of a transceiver,
- Figure 8b shows, for the network shown in Figure 8a, an illustration of routing process said by flooding by means of a routing probe message, allowing to establish a forward path and a return path, forming a route, in order allow the exchange of information between a so-called origin node and a so-called destination node, the illustration being given in the form of a table of the state of the different nodes of the network following the successive reaching of these by the routing probe message,
- Figures 9a to 9e illustrate a preferred routing process for a network of CPAT concentrators such as that shown in Figure 8a.

 A more detailed description of a digital packet data transmission network in frame mode concentration and of a corresponding data routing method, in accordance with the object of the present invention, will now be given in connection with FIG. 2a and the following figures.

 As shown in FIG. 2a above, the packet digital data transmission network, object of the present invention, makes it possible to ensure transmission between at least one switch, denoted 1, and a plurality of subscribers, denoted AB1, AB2, AB3, via subscriber access links. Conventionally, the aforementioned subscribers have a terminal DTE data transmission equipment making it possible, via a subscriber modem MA, to transmit the data or messages generated by the latter to the switch CM.

 According to a particularly advantageous aspect of the network which is the subject of the present invention, it comprises, connected to the switch CM, denoted 1, at least one subscriber link formed by a public subscriber concentrator in frame mode, designated by CPAT concentrator and carrying reference 2, this CPAT concentrator being placed at the head and designated by the head CPAT concentrator or central CPAT concentrator.

 The transmission network which is the subject of the present invention also comprises, as shown in the above-mentioned figure, at least one remote CPAT concentrator, noted 4, the head and remote CPAT concentrators being interconnected by a bidirectional multiplex link, noted 3.

 The head and remote CPAT concentrators 2 and 4 thus allow the transmission of external subscriber data frames between the switch or switches and the subscriber access links.

Of course, the network as shown in FIG. 2a can have a different, more complex configuration, as shown for example in FIG. 2b, in which a head CPAT concentrator 2 is associated for example with a first remote CPAT concentrator, noted 41, and a second remote CPAT concentrator, denoted 42, interconnected to the head CPAT concentrator 2 by means of a multiplexed link, denoted 31 respectively 32
FIG. 2c shows another network configuration in which two switches, denoted ll, respectively 12, are represented, with these two switches being interconnected two head CPAT concentrators, denoted 21 respectively 22, interconnected by a multiplexed link, denoted 3212, and two remote CPAT concentrators, denoted respectively 4 ,, 42, the remote CPAT concentrators being each interconnected to a head CPAT concentrator 21 respectively 22 by a multiplexed link denoted 31 respectively 32. The two remote CPAT concentrators are themselves interconnected via a multiplexed link, noted 3412.

Similarly in FIG. 2d, a particular network configuration has been represented in which a switch 1 is associated with a head CPAT concentrator 2, and three remote CPAT concentrators, the first, denoted 41, being directly connected by a multiplexed link, denoted au to head 2 CPAT concentrator and two concentrators
Remote CPATs, denoted 4z respectively 43, being connected to the preceding remote CPAT concentrator, denoted 41, by means of multiplexed links, denoted 32 respectively 33.

 In the case of the networks represented in FIG. 2b, 2c and 2d, the subscribers are designated by the designation AB with an index, the index corresponding for example to the succession of successive remote CPAT concentrators and to the serial number of l 'subscriber for a remote CPAT concentrator considered.

 In FIG. 2e, the interconnection modes between a head CPAT concentrator or central CPAT concentrator 22 and a switch 11 have been represented, on the one hand, respectively between the central CPAT concentrator 22 and remote CPAT concentrators, denoted 41 to 43 for example, on the other hand.

 As an advantageous example, it is indicated that the head CPAT concentrator 22 can be connected to the switch via a multiplexed link of synchronous switch, synchronous links and asynchronous links for the transmission of external frames to the switch. .

In the case where the switch is a DPS25 switch meeting the packet switching recommendation of CCITT, X.25, the clock signals are generally provided by the central CPAT. It is indicated that this type of connection can be carried out in accordance with notice V.24,
V.28 or X.24, V.ll of the CCITT (Consultative Committee
International for Telephone and Telegraph) relating to DTE, DCE interfaces. Synchronous and asynchronous links are links according to the same advice.

Regarding the link between CPAT center and
Remote CPAT, it is indicated that the bidirectional multiplexed link can be formed by one or more internal multiplexing lines, LMI, connecting the head or remote CPAT concentrators. Thus, the multiplexed link between the central CPAT concentrator 22 and remote CPAT concentrator 41 can be produced, from a multiplexed line 311 and a multiplexed line 312 forming the multiplexed link 3, the multiplexed line 311 not comprising any modulator-demodulator while the multiplexed line 312 includes a modem M at the head CPAT concentrator respectively of the remote CPAT concentrator 41. The multiplexed links 32 respectively 33 ensuring the interconnection between the central CPAT concentrator 22 and the remote CPAT concentrator 42, a share, respectively this same concentrator
Remote CPAT and the remote CPAT concentrator 43, on the other hand, are represented in the form of a multiplexed link in the presence of modems, while the PSTN link between the CPAT center concentrator 22 and the remote concentrator 42 designates a link of the backup link type or overflow by the switched telephone network. It is indicated that when two central or remote CPAT concentrators are connected directly, that is to say without the use of a couple of modems, the junctions can advantageously be kept at the level
V.28, the use of a junction converter not being necessary. In the implementation of the multiplexed line 312 the modems M forming the pair of modems used have V.28 type interfaces when their bit rate is less than or equal to 19,200 bits / second. When using terminal equipment having higher data rates, it is therefore preferable to use interface converters.

According to a particularly advantageous characteristic of the digital packet data transmission network object of the present invention, each multiplexed link being formed by one or more multiplexing lines, each multiplexing line advantageously comprises a plurality of transmission channels, each transmission channel being defined, in a data transmission sequence, by a time window of determined duration. Thus, a channel represents a potential for the possibility of transporting information, in the form of digital data, at the interface between two adjacent CPAT concentrators, that is to say between two head or remote CPAT concentrators directly interconnected by a multiplexed link. For a subscriber message generated by the latter in the form of a data frame constituting an external frame, for a concentrator
CPAT remote, for example, the aforementioned external frame is transformed into a series of fragments of information, or elementary messages, for the subscriber considered at the level of the corresponding CPAT concentrator, which is designated for example by the current CPAT concentrator, a plurality of fragments generated by different subscribers, directly or indirectly linked to the current CPAT concentrator, being selected in the form of echo fragments, by the concentrator
Current CPAT, to constitute an internal frame. This internal frame is transmitted by the current CPAT concentrator to an adjacent CPAT concentrator, in order to ensure the transmission of a shuttle formed by the aforementioned echo fragments and thus ensure the sequential transmission of the different messages. subscribers, by successive partial transmission, each corresponding to the transmission of a fragment per channel allocated to a determined subscriber.

 It is indicated, in general, that the constitution of the internal frames from external frames, that is to say in fact of echo fragments in order to constitute the corresponding shuttles and the transmission of the latter, is carried out at the level of each current CPAT concentrator by a multiplexing / demultiplexing process, which will be described later in the description, this process making it possible of course to route, for a determined channel, a fragment sent by a determined subscriber to a remote CPAT concentrator or head receiver, by successive transmission along the network. It is of course indicated that in the absence of corresponding fragments to be transmitted for the subscriber considered, the channel previously allocated to the aforementioned subscriber can be released, under conditions which will be explained below.

 In a more precise manner and in order to give a more complete description of the multiplexing / demultiplexing operating mode making it possible to explain the constitution of the shuttles, that is to say internal frames, from external frames, a more detailed description. detailed description of the structure and operating mode of a current CPAT concentrator, that is to say a head CPAT concentrator or a remote CPAT concentrator, will now be given in connection with FIGS. 3a and 3b.

 As shown in FIG. 3a, each CPAT concentrator, designated as the current CPAT concentrator, comprises a circuit 10a for receiving and storing external frames sent by the switch l respectively by the subscribers, via d '' a subscriber connection line LR or multiplexed switch denoted LMC of a multiplexed link, these fragmented external frames being stored at the reception circuit lOa in the form of stored fragmented external frames and a circuit lOb for storing internal frames transmitted in the form of shuttle images, NAV, these internal frames being transmitted by an upstream CPAT concentrator and thus memorized at the level of the storage circuit 10b in the form of internal memorized frames.

 A circuit 11 for fragmenting the stored external frames is provided, this circuit allowing the fragmentation, in the form of elementary messages generated by a determined subscriber, of the fragmented external frames stored at the level of the storage circuit 10a.

 An auxiliary data generator circuit 111 representative of the current CPAT concentrator considered and a transmission circuit 12 on the multiplexed link to which the CPAT concentrator is interconnected to a downstream CPAT concentrator are provided, this transmission circuit 12 enabling the transmission of a shuttle message formed for example from the fragments stored in the storage circuits 10a, .10b, previously mentioned, and from frame exchange protocol data.

 With reference to FIG. 3b, it is indicated that a basic message relating to a subscriber, to which a transmission channel is allocated, is assigned a priority order determined at the level of the current CPAT concentrator, which makes it possible to ensure transmission of the shuttle message to or from a plurality of subscribers on the multiplexed link to a downstream CPAT concentrator. With reference to the same FIG. 3b, it is indicated that the channel allocation makes it possible, for a determined channel, to transmit a fragment, resulting from the fragmentation of an external frame or respectively of a memorized shuttle transmitted by an upstream CPAT concentrator, to the current CPAT concentrator.

Thus, in Figure 3a, there is shown a first shuttle formed from a frame Tl sent by a subscriber
A21 for the CPAT 42 concentrator and a T2 frame sent by the subscriber A22 of this same CPAT concentrator, a shuttle being formed and transmitted on the multiplexed link connecting the CPAT 42 concentrator to the CPAT 4 concentrator, this shuttle being formed of fragments of the Tl frame and of the T2 frame. A shuttle is transmitted between the concentrator
Remote CPAT 41 and the center CPAT hub 2 on the multiplexed link interconnecting the remote CPAT hub 41 and the center CPAT hub 2, this new shuttle being formed for example of fragments of a T3 frame sent by an A11 subscriber interconnected by a line of connection to the remote CPAT concentrator 41 and of fragments of the aforementioned Tl and T2 frames. However, it is indicated that the fragments of the Tl frame and of the T2 frame are not necessarily the fragments of the Tl frame and of the T2 frame transmitted by the shuttle previously received, due to the order of priority established at the level of each current CPAT concentrator for the transmission of the fragments on the constituted shuttles, as will be described later in the description.

 According to a particularly advantageous aspect of the digital data transmission network in packet concentration in frame mode, in accordance with the object of the present invention, it is understood that the constitution of the aforementioned shuttles makes it possible to ensure the transmission of messages from the switch respectively & destination and from respectively to a plurality of subscribers on the multiplexed links interconnecting the remote or center CPAT concentrators.

In general, it is indicated that the transmission circuit 12 can advantageously include a sequencing circuit allowing, on reception of an internal frame comprising a shuttle message transmitted by a concentrator
Upstream CPAT, the triggering of the aforementioned transmission circuit 12, which makes it possible to ensure, towards the downstream CPAT concentrator, the transmission over the multiplexed line of an internal frame formed of echo fragments, as mentioned previously in the description, constituting a shuttle message. It is indicated that on reception of an external frame, the transmission of an internal frame formed of echo fragments is carried out before the complete reception of the external frame as will be described later in the description. Conversely, on reception of an internal frame, the transmission of an external frame to a subscriber can be triggered before complete reception of all the fragments constituting the original external frame.

 It is also understood that each CPAT concentrator, in order to produce in particular the fragmentation circuit II and the circuit 12 for transmission of shuttle messages, comprises a central computing unit provided with its random access memories and program memories, this central computing unit being represented. by the block 1112 in FIG. 3a, and the aforementioned auxiliary equipment, which can be constituted in particular by the circuit 111 generating the auxiliary data. This auxiliary data can correspond to an address allowing the location of each CPAT concentrator forming the network. A plurality of line coupler circuits, denoted 14, is provided, each coupler circuit being able to comprise a microcontroller, a random access memory for communication with the aforementioned central computing unit and a program memory, for example. can for example be connected to the central unit by the BUS type link shown in FIG. 3a, via a dual port memory 13 for example.

 A more detailed description of the operation of a current CPAT concentrator in a frame multiplexing-demultiplexing protocol in order, on the one hand to constitute the shuttle messages or internal frames, and, on the other hand, to carry out the transmission of those -ci, will now be given in connection with Figures 4a, 4b, 5a, 5b, and 6a, 6b.

 Firstly, FIG. 4a shows the structure of an internal frame. As shown in FIG. 4a, each internal frame comprises a first information field constituted by the shuttle message proper and a second information field constituted by a field relating to the protocol for exchanging internal frames between the current CPAT concentrator and downstream, this exchange protocol being designated by LAPT protocol.

Generally it is indicated that the protocol
LAPT makes it possible to transport without error or loss and while maintaining the order of priority of transmission assigned to the different fragments, that is to say to each subscriber, on a multiplexing link between two adjacent CPAT concentrators of the network, the elaborate shuttles by the multiplexing-demultiplexing function. The LAPT protocol is based on the LAP-B X.25 protocol of the previously mentioned recommendation with the main specificity of modifying the frame header structure, simplifying the procedures for exchanging frame types and optimizing the transmission of acknowledgments.

The LAPT protocol ensures the following points
- transparency at bit level by insertion of zero,
- synchronization by delimitation of the frames with flags,
- detection of transmission errors by insertion and verification of a frame control sequence,
- control of frame formats for recognition and detection of errors,
- management of the transmission of information frames and the reception of acknowledgments,
- monitoring of acknowledgments received and repetition of unacknowledged frames on time delay,
- management of the reception of information frames, transmission of acknowledgment concerning these frames,
- recovery of transmission errors and incidents by retransmission or reset,
- establishment of a logical connection by connection.

 With reference to FIG. 4a, it can be seen that the first information field is formed by a first subfield comprising a plurality of fragments, denoted Fn, each fragment being relative to a given subscriber. The first information field also includes a second sub-field representative of the order of priority of transmission of the fragments relating to the different subscribers, this second sub-field constituting in fact a key of priority of transmission of each fragment.

 In general, it is indicated that the first subfield comprising a plurality of relative fragments & different subscribers is formed by concatenation of successive fragments of different subscribers. Each successive fragment is chosen from the current available set of different fragments to be transmitted, fragments memorized at the level of the storage circuits 10a in FIG. 3a and assigned to a channel whose order of priority is linked to the age of the request. of the subscriber considered.

The second sub-field is representative of the order of priority of transmission of the fragments relating to the different subscribers. It is formed by concatenation of bits, each bit of the aforementioned sub-field being representative of the existence or non-existence of a relative fragment to a subscriber, and the weight of each bit in this same sub-field is itself even representative of the order of priority of the fragments to be transmitted. In FIG. 4a, the order of priority of the fragments F1 is also represented on a vector,
Fn to F4 constituting the shuttle message, the highest order of priority corresponding to that of the fragment F1, this order of priority being represented by the weight of the highest bit of the second sub-field constituting the priority key.

 In general, it is indicated that the aforementioned multiplexing-demultiplexing protocol allows the transport of external frames by using one or more multiplexed links provided by each CPAT concentrator playing the role of transit node.

 In general, the transit delay of an external frame is minimized by the fragmentation mechanism, which makes it possible to start transmitting shuttle messages, or internal frames, on the aforementioned multiplexed links well before the external frame has been received in its entirety.

 To ensure this operating mode, the fragments must follow each other at sufficiently regular time intervals, which is achieved by a system for allocating the transmission rate resource of the multiplexed link formed, as a function of the speed. for each subscriber.

 The retransmission of a fragment in the form of an internal frame respectively of an external frame can however only be carried out when an internal frame has been received in its entirety at the level of a transit CPAT concentrator respectively of a destination CPAT.

 The constitution of the shuttle messages is however carried out so that a minimum of overload of the processor circuits previously mentioned is introduced, the choice of the fragments constituting each shuttle message further respecting the priority of the different requests and the allocation of speech.

 It is further indicated that the aforementioned multiplexing-demultiplexing protocol allows, in addition to the transmission of information corresponding to the external frames, the transmission of information relating to junctions, this information being assimilated to subscriber frames, operational information , also assimilated & frames circulating between two subscribers, and routing information as will be described later in the description.

With regard to fragmentation, that is to say the constitution of information packets relating to a determined subscriber, the maximum size of a fragment Fn is determined for each subscriber as a function of its connection speed. It says that
- Fn = 2 bytes for vs at 1200 b / s
- Fn = 4 bytes for vs at 2400 b / s
- Fn = 8 bytes for v S at 4,800 b / s
- Fn = 16 bytes for v S at 9,600 b / s,
- Fn = 24 bytes for vs at 14,400 b / s, and
- Fn = 32 bytes for vs at 19,200 b / s.

 It is indicated that advantageously without limitation, the external frames may after fragmentation be subjected to compression so as to reduce the size of the messages to be transmitted. Fragmentation is carried out on each external frame separately and all the fragments generated are of maximum length, except possibly the last for which the number of useful bytes is supplied.

 When a current CPAT concentrator is used as a transit node for the network, that is to say when the latter only has to choose the fragments to be transmitted according to the speech allocation and the order of priority of transmission, no fragment length conversion is of course performed.

At each current CPAT concentrator, all the fragments are transmitted along a path determined by three elements
- an input, that is to say an input formed by either a subscriber connection line LR or LMC switch, or a CPAT concentrator in the case of operating information,
- an output formed either by a connection line to a subscriber, or a remote CPAT concentrator playing the role of transit node.

 A route is then defined between input and output previously defined as consisting of a succession of links, a link being a number assigned to a given subscriber on a transmission channel of a multiplexed link.

 Speech allocation for a subscriber request is carried out by means of a token enabling the reservation of a number of bytes in a shuttle and in successive shuttles. This number of bytes corresponding to the appropriate fragment size previously defined in the description. The allocation of a token is carried out only on the external frames giving rise to fragmentation.

The tokens remain allocated over the entire duration of transmission of the external frame on a multiplexed link considered, that is to say of course for the duration of transmission of several internal frames or successive shuttle messages.

Each channel allocated to a determined subscriber can then be
- activated and used, when it actually carries a fragment relating to a specific subscriber, or
- activated and empty when the channel, although activated, carries no fragment for the aforementioned subscriber,
- inactive when no information is transmitted via this channel, this inactive state being the initial state of all the channels.

 An inactive channel can be activated as soon as there is sufficient unused space in a shuttle being created and information must be transmitted on this channel.

 Each subscriber request is therefore processed as a function of the subscriber's right to speak, that is to say the allocation made by the token described above and the age of his request.

 The scheduling of the different channels on the vector represented in FIG. 4a makes it possible to establish the priority key represented in this same figure.

 A channel, as soon as it is activated, tends to lose its priority for taking into account a new request, the position of the latter on the vector represented in FIG. 4a migrating towards the low positions thereof.

 On the contrary, inactive channels tend to have a higher priority for taking into account a new request from the subscriber.

 Thus, the most frequently used channels have the lowest positions on the vector, represented in FIG. 4a, while the channels which have never been activated are found in the highest positions.

 The positional addressing of the channels corresponding to the fragments on the vector makes it possible to locate the channels in a shuttle transmitted in the priority key, as shown in FIG. 4a, this location being identical to that of the vector and therefore does not require specifying the subscriber / channel correspondence in the shuttle.

 A current CPAT concentrator is capable of reconstructing the vector of the channels established by the upstream CPAT concentrator, to which it is connected, as well as the subscriber / rank correspondence of the channel in this vector.

 On reception of a shuttle, the activated channels are recognized by the information carried by the priority key and the characteristics of the activated channels and it is then possible to apply to the position of these channels the same migration law, c 'is to say law of priority of transmission, that that used by the concentrator CPAT upstream and thus to determine the correspondence subscriber / channel in the following shuttle.

 As shown in FIG. 4b, following the reception by the downstream CPAT concentrator of an internal frame, the simultaneous reading of the first and second sub-fields in the opposite direction makes it possible to reconstruct, at the level of the downstream CPAT concentrator, the current set of different successive fragments of basic subscriber messages & transmit.

Thus, for any bit of rank n, if the value of this bit is equal to 1, the content of the channel of rank n is specified by an identification field, the channel is therefore active, used or empty, and, if the value of the bit of rank n is equal to 0, the channel is inactive or active and used, (existence of a token for this channel), and the concentrator
CPAT receiver recognizes these possibilities according to the state of the channel.

 As regards the effective use of the channels by the downstream CPAT concentrator, it is indicated in a non-limiting advantageous manner, that this can be carried out as a function of the length of the frames, a long frame corresponding to information which must necessarily be fragmented to be transmitted over an internal multiplexed link for example, information frame containing a data packet of 128 bytes, and a short frame corresponding to information which has a size less than or equal to the maximum size of a fragment.

 Among the aforementioned channels, it is indicated that at least one of these can be reserved as a service channel, in order to route service messages, which will be described later in the description.

 The general operating mechanism of a central or remote CPAT concentrator during the creation of a shuttle will now be described in connection with FIGS. 5a, 5b and 6a, 6b in the nonlimiting example of transfer of traffic frames between two connecting links.

 In the above example, it is indicated that the central computing unit 1112 can be produced by a computer of the type 68020 sold by the company MOTOROLA, with which are associated a corresponding program making it possible to perform all of the functions previously described in the description, and a working memory lOc.

 In FIG. 5a, the encircled numerical references represent steps for implementing the process of constituting the shuttles, these encircled references corresponding to the references 1001 to 1007 in FIG. 6a.

 FIG. 5a more precisely represents an example of implementation of a shuttle constitution process in the case where an external frame, transmitted by a subscriber, is received in the dual port memory 13 via the coupler 14b of the LR connection line. The aforementioned external frame is stored in the dual port memory 13.

 Following the previous step, a polling function (polling in Anglo-Saxon language) is triggered by the calculation unit 1112, this polling function being performed at regular intervals on the dual port memory 13. When a complete fragment or an end of frame signal has been received, a copy of the stored fragment is made in memory 10a of FIG. 3a.

 In FIG. 5a, the scanning step bears the reference 2 circled and the step of copying, in memory 10a, the reference 3 circled. These steps are designated by 1002 and 1003 in Figure 6a. It is indicated, by way of nonlimiting example, that each fragment may contain, in addition to the information generated by the subscriber, flags at the start and at the end of the frame, which make it possible to carry out an identification of a start or an end respectively weft.

 Following the end of step 3 circled or 1003 in Figure 6a, and following the end of transmission of the previous shuttle, a step 4 circled is triggered, step 1004 in Figure 6a, to build an image of the next shuttle, this image being made up of a series of pointers to the different fragments. The pointers are denoted Ptr in FIG. 5a. Of course, the image of the aforementioned shuttle is formed by respecting the rules for selecting channels previously described in the description.

 At regular intervals, a circled step 5 is triggered, this step consisting in the synchronization of transmission proper and having the effect of preparing the transfer of the fragments received in the part of the dual port memory 13 coupled to the corresponding internal multiplexed line. It is of course understood that under these conditions the preceding circled step 5, or step 1005 in FIG. 6a, thus makes it possible to manufacture a shuttle portion of sufficient size between two activation intervals. An activation interval can be taken equal to 4ms. It is understood of course that the transfer of the echo fragments, in the dual port memory, is carried out taking into account the rule for the election of the channels described above. At the end of transfer of the last fragment constituting the shuttle, the priority key and the second subfield relating to the exchange protocol are also generated and transferred to the dual port memory.

In addition, a circled step 6 is triggered jointly and makes it possible to copy the successive echo fragments corresponding to subscribers Al, A2, An for example, in the dual port memory 13 corresponding to the multiplexed line
CPAT concentrator LMI. This recopy is noted 1006 in FIG. 6a. The transmission step proper on the LMI multiplexed link is then carried out in step 7, circled, by the corresponding line coupler 14a.

 FIGS. 5b and 6b show the steps carried out at a CPAT concentrator in the reverse process to that of FIG. 5a, in the case in particular where an internal frame is received via the LMI multiplexed line , this internal frame used to constitute an external frame, which is transmitted over the connection line LR to a subscriber.

 In FIGS. 5b and 6b, the different stages of the process of demultiplexing of the transmitted fragments bear the references 1 circled to 7 circled respectively, which correspond to the stages represented in 2001 to 2007 in FIG. 6b.

 The circled step 1 represents a step of reception by the line coupler 14a to which the multiplexed line LMI is interconnected, this reception being also followed by a transfer and a memorization of the above-mentioned internal frame towards the dual port memory 13.

 On reception of the corresponding end of frame, the steps 2 circled and 3 circled, correspond to the generation of a request for copying of the frame block received to the working memory lOc with control of the exchange protocol code. The corresponding steps are noted 2002 and 2003 in Figure 6b.

 The operations 2 and 3 circled above are followed by an operation 4 circled for demultiplexing proper of the shuttle or internal frame received, after reception of the complete frame. During this operation, the different fragments are discriminated as a function of the priority key and of the characteristics of the channel, corresponding and finally of the subscriber to whom they are intended for transmission to the latter.

 Following operation 4 circled for demultiplexing previously mentioned, an operation 5 circled for copying the fragment intended for the corresponding subscriber is carried out, this copying being carried out in the dual port memory 13 associated with the connection line LR via of the coupler on line 14b.

 A synchronized synchronization and delay function 6 is generated, this function making it possible to establish the transmission proper, under acceptable synchronization and delay conditions as a function of the length of the frames and the subscriber bit rate for example. In the case of a short frame, the circled transmission 7 can then be immediate via the coupler 14b to the connection line LR. For a long frame, the function 6 circled with delay can make it possible to generate a corresponding self-adaptive guard delay. This delay protects against the risk of too late arrival of a fragment intended for the subscriber considered. The actual program is identified by the reference 7 circled in Figure 5b and by the reference 2007 in Figure 6b.

 We will also now indicate, by way of nonlimiting example, the operating mode of a central CPAT concentrator in the case of reception on a multiplexed switch line, denoted by LMC, as indicated in FIG. 2a or in the Figure 3b.

 On reception on the aforementioned multiplexed line, the frames are cut in blocks. Each block is then subjected to a process of data fragmentation and possibly compression of the header.

 The fragments are then available for possible insertion in a shuttle, which makes it possible to start the transmission of an internal frame before complete reception of the frame transmitted by the switch CM on the multiplexed line LMC.

 The general principles relating to the multiplexing / demultiplexing operating mode specific to the constitution of the shuttles will be indicated below.

 Regarding the allocation of channels, in particular a channel to a specific subscriber, the management of the different channels allows all subscribers to send information, giving priority to those who have not transmitted for a long time to the detriment of those who just made a transmission.

 In addition, a subscriber having a long frame during transmission, it must imperatively keep a place in the next shuttles until the end of the transmission of his external frame on the multiplexing line considered.

 Such a result is obtained by means of a process making it possible to know the place of the shuttles remaining available to allow other subscribers to start transmitting a new frame. This process is controlled by a simple variable, which is decremented respectively incremented, during the allocation respectively the restitution of the token, of the maximum size of the subscribed fragment. At initialization, this variable is equal to the maximum size of the shuttle.

 The process of constituting a shuttle is governed so that the requesting subscribers are elected when the echo fragments sent by these subscribers will appear in the next shuttle. This process consists in testing, for each subscriber, if the latter has requested a program and in such a case of checking whether the remaining available space makes it possible to contain the corresponding fragment. In addition, if the echo fragment for the subscriber considered is a start of a long frame, a token is granted to the latter, this token allowing him to keep his place in the following shuttles. When the subscriber is elected, the space available in the current shuttle is then decremented by the value of the size of the elected fragment.

 In parallel with the constitution of each shuttle, the priority key is generated, which represents the state of the channels used, as previously described in the description.

From an operational point of view, the multiplexing operation performs, at the level of each concentrator
CPAT, the process of constituting each shuttle and makes it possible to carry out the following operations
- implementation of the channel allocation law enabling the corresponding channels to be determined and allocated
- initial reservation of resources;
- election of applicants.

 At the end of this phase, an image of the shuttle is created, which consists of a series of pointers to the fragments of the elected subscribers. This image is used to make transfers to dual port memory 13 as previously mentioned in the description.

 When constituting the image of the shuttle, certain echo fragments may be absent, this is the case for example of a long frame during transmission. In the case where, at the time of feeding, the fragment considered is still not present for a corresponding subscriber, the place of this latter is used for short frames for example. The image of the shuttle thus formed is provisional.

 Finally, it is understood that the synchronization functions 5 circled and 6 circled in FIGS. 5a and 5b make it possible to activate the shuttle supply task with echo fragments in order to effect in fact the constitution of the shuttle proper and the constitution of the priority key associated with it.

 On receipt of an end-of-frame signal, at a current CPAT concentrator, a software interruption is generated which makes it possible, on the one hand, to copy from the dual port memory to the working memory lOc and on the other hand to activate a reception task according to the LAPT protocol allowing the checks described above to be carried out.

 In the case of an information frame, the LAPT protocol makes it possible to orient the received frame towards a demultiplexing function.

After analysis of the aforementioned frame, the protocol
LAPT makes it possible to perform a referral of the various echo fragments constituting the aforementioned frame
- if it is operational information, the corresponding data is stored in a particular area of the working memory 10C until reception of a corresponding end of frame. When the frame is complete address and frame length are transmitted as a parameter when the corresponding task is activated;
- if the received echo fragment contains junction or routing information, the corresponding task is activated, this type of information never being fragmented;
- if the echo fragment is in transit to another remote CPAT concentrator or center, a subroutine is then called which makes it possible to prepare a data transmission on another corresponding multiplexing line.

 Prior to the transmission of the internal frames, and to the constitution of these as mentioned previously in the description, it is necessary, at the level of a network of a CPAT concentrator, as previously described in accordance with the object of the present invention, to carry out a shuttle routing procedure in order to determine, independently of the network topology, a forward path, respectively return path, between two sister addresses defined by the address of a so-called generator CPAT hub, and that of a CPAT concentrator known as the recipient.

 The aforementioned routing procedure will be described more precisely in relation to FIGS. 7a, 7b and following.

 In general, it is indicated that the aforementioned routing procedure is not limited to implementation on a network of CPAT concentrators but can be used on any type of data transmission network in which at each node a transmitting function -receiver is present, the transceiver function essentially having the repetition of a message constituted for example by an internal frame, after updating the destination address of this frame to an adjacent downstream node, as will be described below in the description.

FIG. 7a shows a network of CPAT concentrators in accordance with the object of the present invention in which a CM switch is associated with a central CPAT concentrator, denoted NO, and seven concentrators
CPAT, denoted N1 to N7, in any topology, some of the CPAT concentrators having subscriber connection links in accordance with the notation previously used in the description.

 Of course, each node formed, for example by a CPAT concentrator, comprises a determined number of input-output ports, each node constituting the network thus being interconnected to one or more adjacent nodes by LMI type transmission lines constituting the branches of the network.

As shown in FIG. 7b, the routing procedure makes it possible successively by sending a probe message to determine the outward path in a step denoted 3001 between the generating CPAT concentrator and the receiving CPAT concentrator. This path is of course formed by a succession of branches. Following the determination of the outward path in 3001, a step 3002 is provided allowing validation of the outward path when the concentrator
CPAT recipient has been reached. Following the above-mentioned step 3002, a new step 3003 is provided in order to determine a return path between the destination CPAT concentrator and the generating CPAT concentrator. It is indicated that the return path can of course be different from the outward path, that is to say borrow different successive branches and nodes. Following step 3003 of determining the aforementioned return path, a validation step 3004 of return path is also provided and the route consisting of the outward path and the return path can be valid in 3005. The aforementioned validation steps of the outward path, the return path and the route constituted by the outward path and the return path, can be carried out via transit point validation messages, these messages can be generated by the generating CPAT concentrator respectively by the concentrator
CPAT recipient. It is indicated that the validation messages allow the allocation of a transmission channel for a subscriber considered at each node constituted by a successive CPAT concentrator constituting the outward path and / or the return path.

A more detailed description of the routing process proper will now be given in connection with FIGS. 8a and 8b, FIG. 8a representing the constitutive diagram of the network represented in FIG. 7a, a network in which each constituent node and each constituent branch of this network have have been identified in order to explain the routing process proper above. In the nonlimiting example illustrated by means of FIGS. 8a and 8b, it is considered that the generating node is the node N7 and that the destination node is the node NO, these nodes in the case of FIG. 7a consisting of a remote CPAT concentrator respectively in the center CPAT concentrator connected to the CM switch. It is further indicated that the nodes N1
N6 then constitute transit nodes, each of the nodes being identified by an address.

 The routing process proper then consists in transmitting from the generator node a routing probe message dedicated to the destination node, on all the input-output ports of the generator node connected to an adjacent downstream node. FIG. 8b indicates the progress of the probe message from the generator node N7, the indexed values associated with each node representing the addresses of the input-output ports of a current node and of the nodes adjacent to it. It is of course indicated that the abovementioned downstream adjacent nodes form transit nodes, each column in FIG. 8b indicating the node reached by the probe message and the indices assigned to each node indicating the branches of the network on which the probe message is transmitted.

 Following the receipt of the routing probe message by each adjacent downstream node, the process then consists of completing, by concatenation, this routing probe message with the address code of the adjacent downstream node considered to form a completed routing probe message dedicated to recipient node.

 The routing process in accordance with the object of the present invention then consists in transmitting from each of the adjacent downstream nodes the completed routing probe message dedicated to the destination node on all the input and output ports of the adjacent downstream nodes connected to a new downstream adjacent node. The notion of new downstream adjacent node corresponds to that of a downstream adjacent node which has not yet been reached by the completed routing probe message or which is not at the origin of it.

This characteristic of failure to reach a downstream adjacent node considered forming a transit node can be easily obtained by memorizing the routing probe message completed as soon as it is received by the adjacent downstream node considered and comparison of a reference number of any Subsequent completed routing probe message received by the adjacent downstream node under consideration. Thus, upon observation of FIG. 8b relative to the outward path, it can be seen that the node N5 is reached following the transmission by the generator node N7 on the branch 13, the second attack on this node N5, following the retransmission by the node N4 on the branch 14, then causing no transmission from the node N5 considered to be the adjacent node downstream from the node N4, this situation being represented by the sign X.

The previous steps of complement by concatenating the routing probe and transmission message from each downstream adjacent node are repeated for any new downstream adjacent node, that is to say necessarily the nodes
N4, N5 in column 2 of the aforementioned FIG. 8b and the nodes N1, N2, N3, N6 in the third column of this same figure. This repetition is carried out so that the completed routing probe message reaches all the nodes of the network and in particular the destination node NO. When the destination node is reached for the first time by the completed routing probe message, the outward path is defined by all the addresses of the transit nodes crossed, addresses contained in the completed routing probe message.

In FIG. 8b relating to the outward path, it is indicated that the outward path retained is ultimately the path
N7, N5, N2, NO symbolized by a circled cross, it being understood that for the purposes of the description it has been assumed, in a simplifying manner, that the transmission time between any two nodes was identical, the case where the transmission times on the links of the network between two adjacent nodes are not identical, which of course is the general case, having the sole effect of shifting the instants of reaching successive transit nodes, without changing the principle of implementation of the routing process, referred to as flood routing.

 Of course, following the reaching by the routing probe message of the recipient node, the preceding steps can then be repeated from the recipient node, operating as node under generator, to the generator node, then operating as node under recipient, at by means of the completed routing probe message dedicated to the node under recipient, that is to say ultimately the starting node N7. In the same way, the return path is defined on first reaching the node under recipient by the routing probe message supplemented by all the addresses of the transit nodes crossed, from the node under generator NO to the node under recipient N7, these addresses being contained in the completed routing probe message.

The routing path is then formed by the set of addresses of the transit nodes forming the outward path and the return path.

 It is of course indicated that in the case where a forward path already exists between the destination node and the generating node, the repetition of the preceding steps to define a return path between the above-mentioned nodes is not essential, the return path can be constituted by this path to go.

 In FIG. 8b relating to the return path, the stop symbols for sending the routing probe message have been shown with the same symbols for any node already reached by this same message and the first reaching of the node under recipient N7 by means of d 'a circled cross. The return path is then, for example, the path NO, N1, N4, N7 with the conventions already used in the context of determining the outward path.

 As shown in FIG. 8a, the addresses of the nodes of the network can be absolute and / or relative addresses. It is understood that if absolute addresses are used in the context of a network of CPAT concentrators for example, the circuit 111 of FIG. 3a then makes it possible to generate these absolute addresses by means of a battery of microswitches for example.

 In an advantageous embodiment of the network of CPAT concentrators which is the subject of the present invention, the addresses of the nodes are formed by the relative addresses of the latter, these relative addresses possibly consisting, for example, of references of the input ports of adjacent nodes. In such a case, and in a particularly advantageous manner as shown in FIG. 8a, the nodes adjacent to the node N5, which are none other than the nodes N2, N3, N4, N6 and N7, are necessarily determined by the pair of addresses corresponding input-output ports, that is to say the pair 02 for the node N2, 12 for the node N3, 20 for the node N6, 31 for the node N7 and 41 for the node N4. We understand of course that it is sufficient to assign the references to the input-output port considered so as to avoid any repetition of torque. We can also, advantageously, associate each pair representative of a line address, or relative address, an absolute address consisting for example of a number assigned to each CPAT concentrator.

 In a conventional manner, it is indicated that the routing probe message comprises at least one identification flag of the recipient node, respectively of the node under recipient, a field of addresses of the transit nodes, a field of addresses of the generating node respectively of the node. under generator.

 In a practical way, it is indicated that on the first reaching of the recipient node and before the repetition step towards the node under recipient making it possible to establish the return path, the process can consist of * inverting the completed routing probe message, the address field of the generating node constituting the recipient node and the identification flag of the recipient node, which makes it possible to generate the completed routing probe message dedicated to the recipient node.

 It is indicated that the routing process previously described can be used in any type of network as previously mentioned, that is to say in networks of CPAT concentrators for example. The aforementioned routing process is said to be distributed due to the fact that each CPAT concentrator executes the routing process using the local information at its disposal, that is to say the relative and / or absolute addresses previously mentioned.

 A routing process, more particularly adapted to the exploitation of the possibilities of each CPAT concentrator constituting a network in accordance with the object of the present invention, will now be described in conjunction with FIGS. 9a to 9e.

 In accordance with a particularly advantageous aspect of the process which is the subject of the present invention, it consists in reserving on all the CPAT concentrators constituting the network at least one transmission channel to constitute a routing channel. It is indicated that the routing channel is, for example, constituted by the service channel previously mentioned in the description.

 The method which is the subject of the present invention then consists, in order to carry out the routing process proper, in transmitting the routing probes on the aforementioned routing channel. Of course, the routing process can then be carried out as described previously in the description.

 However, a preferred routing process will be described in the case where the network is constituted, for example, by a set of CPAT concentrators as shown in FIG. 9a, this network being able to have any topology but corresponding, for the simplicity of the description , to the network previously described in relation to FIG. 8a.

 We consider the network of FIG. 9a, in which the routing process proper must be carried out between an upstream node, noted Am, or upstream point, the node N7 and a downstream node, noted Av, or downstream point, the node NO in Figure 9a.

It is recalled that a channel in fact represents a potential for the possibility of transporting information on an internal multiplexed line LMI, between concentrators
CPAT and finally between network nodes. The information concerning a subscriber is transported via the aforementioned LMI multiplexed lines, via the corresponding channel allocated to this subscriber.

 Establishing a path between an upstream point Am and a downstream point Av, the nodes N7 and NO in FIG. 9a, therefore consists in allocating a channel to the subscriber considered on each of the successive multiplexed lines.

 At the initialization of the network, that is to say during the request for message transmission by the subscriber, no channel is originally assigned. Only the service channels previously mentioned in the description exist.

In accordance with a particularly advantageous aspect of the routing process which is the subject of the present invention, the aforementioned service channel is used to transport the routing information.
- routing probes, outward path and return path,
- messages for validation of the outward or return path called echo probes, and
- failure messages as will be described below in the description.

 It is indicated that a speed is associated with a channel, which makes it possible to increase the size of information that can circulate on a channel in a shuttle message.

 For example, the service channel can correspond to a speed of 9600 bits / s, that is to say a fragment size of 16 bytes.

 As regards the addressing of each subscriber for a node considered, that is to say the upstream point, for example, Am, it is indicated that the address of a subscriber is determined by the concentrator number CPAT, for example, and the connection line number of the subscriber considered.

 As part of the implementation of the aforementioned routing process, as previously mentioned in the description, the number of the CPAT concentrator is used as well as the LMI multiplexed line number to perform relative addressing as mentioned previously in the description.

 The routing process for a network of CPAT concentrators, in accordance with the object of the present invention, is then preferably implemented according to the steps below.

 The aforementioned routing process is activated by emission of a routing probe by the CPAT concentrator located at the upstream point Am in order to establish a path with the downstream point Av.

 In accordance with an advantageous aspect of the routing process which is the subject of the present invention, this consists, on exchange request, in determining, firstly, the existence or non-existence of a current path between the upstream point Am and the downstream point Av.

 If no current path exists, the routing process previously described in the description, so-called flooding routing process, can then be implemented to determine a path between the upstream point Am and the aforementioned downstream point Av.

 Preferably it is indicated that in the absence of a current path between the point Am and the point Av, at regular interval, when a subscriber is in service, a routing probe can be emitted, for the establishment of a path, or, when a current path exists, with a view to finding a better path, that is to say an optimal path between the upstream point Am and the downstream point Av. By way of example, indicates that routing probes can be sent, at the rate of one probe per second and per subscriber.

 It is thus understood that in the event of the existence of a current path the routing method, object of the present invention, in its advantageous embodiment, then consists in transmitting from the upstream point Am a routing probe message to the downstream point to determine any path distinct from the aforementioned current path. It is indicated by way of example that in FIG. 9a the current path corresponds for example to the path N7, N5, N2, NO.

 In accordance with a particularly advantageous aspect of the routing process which is the subject of the present invention, it consists in simultaneously transmitting, on the current path, a specific probe message to the downstream point Av.

It is indicated that the specific probe message is a routing probe message comprising a mark, this routing probe message being sent on the current path.

 On reception by the downstream point Av of the routing probe message respectively of the specific routing probe message, the routing method in accordance with the object of the present invention then consists in memorizing the time of arrival at the downstream point Av of the probe message routing and the specific routing probe message.

 A time credit is then calculated for the current path and the aforementioned time credit can then be increased or decreased by the time difference between the arrival times of the routing probe message and the specific routing probe message, this operation allowing optimize the transmission time between the upstream point AI and the downstream point Av of the network.

More precisely, it is indicated that if the first probe received at the downstream point Av is the specific probe message conveyed on the current path, the concentrator
CPAT of the downstream point Av triggers a timer with a value equal to
T = TCR where TCR denotes a maximum authorized time credit.

For a delay D elapsed between the instant of reception of the first probe and the arrival of the second probe or the expiry of the timer mentioned above, the concentrator CPAT located at the downstream point Av increases the time credit TCRc of the current path d 'a value
TCRc * = TCRc + D.

If the first probe is not the specific probe carried on the current path, the CPAT concentrator located at the downstream point Av arms a timer of equal value &:
T = TCRc.

On receipt of the specific probe carried by the current path, before the expiry of the aforementioned timer T, the CPAT concentrator then decreases the credit of the time elapsed for the current path to the value
TCRc * = TCRc - D.

 If the duration timer T expires, the concentrator CPAT located at the downstream point Av then considers the new path as better and then sends an echo probe message.

 It is indicated that the allocated time credit mechanism thus makes it possible to avoid continual switching between two equivalent paths.

 FIG. 9b shows the structure of a probe message during the initial transmission at point 1) respectively by a transit CPAT concentrator at point 2).

In the structure of the aforementioned probe messages, it is indicated that the references designate the elements below
- AA: address of the subscriber,
- CO: command code equal for example to short frame,
- CR: routing control code.

 The routing control code comprises, as shown in point 2 of FIG. 9b, a CC probe control field, a N (S) field probe number for the subscriber considered and a current path existence field, this field making it possible to characterize the probe message as a specific routing probe message or a common routing probe message.

 The fields LMI1 to LMIn indicate the list of multiplexing lines or addresses of the CPAT concentrators crossed as previously described in the description.

According to another particularly advantageous aspect of the routing process which is the subject of the present invention, when the network is constituted by a network of hubs
CPAT, and the outward path having been determined under the conditions mentioned above, a particularly advantageous characteristic may consist in determining the return path to use the outward path in reverse, the return path routing then being designated by reverse return path.

 This process appears advantageous insofar as, of course, the optimization of the return path, starting from the reverse path, can be carried out as mentioned previously in the description to optimize a return path different from the reverse path, which can then to be considered as the current path.

 Under the conditions mentioned above, it is indicated that the CPAT concentrator located at the downstream point Av then sends an echo probe message constituted from a routing probe message, this echo probe message being transmitted on the reception link of the routing probe go which made it possible to establish the way to go.

The echo probe message then presents the structure represented in FIG. 9c and includes the fields below
- CO, AA, LMI1 to LMIn previously described in connection with FIG. 9a as well as
- CR itself containing the fields
- CC: routing command code equal to echo, code for example on two bits,
- N (S) probe number also coded on two bits,
- PTR: index on the multiplexing line number on which the adjacent CPAT concentrator, that is to say the concentrator located at node N2 in FIG. 9a, located on the current forward path, traveled in the opposite direction, must transmit the echo probe message.

 The PTR field can be coded on three bits.

Upon receipt of the echo message by the concentrator
Adjacent CPAT, on the forward path traveled in the opposite direction, aiming to constitute the outward path, the adjacent CPAT concentrator performs the following treatments
- retrieving the multiplexed line number for sending the echo,
- access to the multiplexing line on which the echo message is to be retransmitted, the multiplexing line 20 in FIG. 9a, which corresponds to the link N2-N5 on the outward path,
- replacing the reference of the LMI multi-plexed line for receiving the echo probe message with the reference for the multiplexed line for receiving the echo message, therefore for sending the probe message, this reference being that which is pointed to by the PTR index ,
- decrement the index,
- re-transmission of the echo probe message.

 When the PTR index finds the original value corresponding to the link 31 between the nodes N5 and N7, for example, the CPAT concentrator reached is the one that emitted the original routing probe that caused the establishment or optimization from the outward path, that is to say at the upstream point Am at node N7. The aforementioned CPAT concentrator generates a validation message for the forward path transit points, this validation message or path establishment then being transmitted in the channel assigned to the subscriber considered.

The path establishment message allows the assignment of a channel to the subscriber on each LMI multiplexed line and is transmitted on this channel. I1 is represented in figure 9d, and presents the fields below
- CO: multiplexing or path establishment control field,
- D: debit of the subscriber considered,
- AA: address of the subscriber and of course
- LMI1 to LMIn: list of successive & borrow links, known from the echo probe message.

 It is indicated that the assignment of the new path is carried out during the passage of the above-mentioned validation message or path establishment, this assignment consisting in assigning a channel to the subscriber concerned on each of the multiplexing lines used successively.

 Similarly, it is indicated that the establishment or optimization of the return path can be carried out in a similar manner.

 Of course, the routing method which is the subject of the present invention not only makes it possible to optimize the path followed by a message transmitted between an upstream point Am and a downstream point Av and the corresponding return path, but also to restore this path upon breaking of that -this, or to optimize or re-establish any elementary path, comprising the upstream point Am, upon rupture of the latter.

Thus, in FIG. 9a, it is indicated that any elementary path, that is to say succession of multiplexed lines
LMI between node N7 and node N2 for example, can be replaced by a replacement path N7, N5, N3, N2 in the event of line break N5, N2.

 In general, it is indicated that following the rupture of a multiplexing line such as the aforementioned line, a concentrator CPAT in transit, receiving traffic intended to be routed on a broken or reinitialized line, transmits in the service channel a message in the opposite direction of the current path to the original CPAT concentrator.

 Upon receipt of a break message, the original CPAT concentrator immediately retransmits a routing probe, in order to restore the broken path, according to the routing process previously described in the description.

 A spontaneous scanning procedure available at each CPAT Am concentrator ensures that the best path is chosen. It is indicated that by way of example, at regular intervals each concentrator CPAT determines the best path for one of the subscriber addresses that it manages.

 It is indicated that this process makes it possible to take into account the variations in load on a given multiplexed line, the initialization of a new multiplexed line and, of course, to precede the detection of a disappearance or the reinitialization of a line. multiplexed.

The structure of a path departure message is shown in Figure 9e. This message includes the following fields
- CO: multiplexing control code corresponding to a short frame,
- Cr: routing control code, and
- AA: address of the subscriber.

 It is indicated that the routing command field itself comprises a specific path breaking command field.

 It is indicated that each path breaking message borrows the service channel previously described in the description.

 We have thus described a digital packet data transmission network formed by public subscribers in frame mode, CPAT concentrators, particularly efficient insofar as, thanks to a particularly efficient routing process of information packets, a very great flexibility in using the network and very high reliability and security of transmission of this information are obtained.

Claims (18)

 1) Digital packet data transmission network, between at least one switch and a plurality of subscribers, via subscriber access links, characterized in that said network comprises, connected to said switches, at least one link subscribers formed by: - a public concentrator of frame mode subscribers, designated  by CPAT concentrator placed at the head and designated by  leading CPAT concentrator, and - at least one remote CPAT concentrator, said concentrates  Head and remote CPAT tracers being interconnected  by a bidirectional multiplexed link, said  Head and remote CPAT concentrators allowing the  transmission of external subscriber data frames  between said switches and said access links  subscribers.  2) Transmission network according to claim 1, characterized in that said multiplexed link is formed by one or more multiplexing lines connecting said concentrators, head CPAT and remote CPAT.  3) Transmission network according to claim 2, characterized in that each multiplexing line forming the multiplexed link comprises a plurality of transmission channels, each channel being defined in a data transmission sequence by a time window of determined duration.  4) Transmission network according to one of claims 1 to 3, characterized in that each concentrator CPAT, designated as the current CPAT concentrator, comprises - means for receiving and memorizing said  external frames emitted by said switches, respec  said subscribers, in the form of external frames  stored, respectively of internal frames transmitted  by an upstream CPAT concentrator, in the form of lines  internal memories, - means of fragmentation in the form of messages  elementary relating to a specific subscriber, said  stored external frames, - auxiliary data generating means represented  tives of said current CPAT concentrator, - transmission means, on said multi link  plexed, to a downstream CPAT concentrator, a message  shuttle formed from said elementary messages and  frame exchange protocol data, a  basic message relating to a subscriber being allocated a  transmission channel according to a determined order of priority  born, which ensures the transmission of the message  shuttle to or from a plurality  subscribers on said multiplexed link.  5) Transmission network according to claim 4, characterized in that said transmission means comprise sequencing means allowing, upon reception of an internal frame comprising a shuttle message transmitted by an upstream CPAT concentrator, the immediate triggering of the transmission means, which ensures, to said downstream CPAT concentrator, the transmission over the multiplexed link of an internal frame formed of echo fragments and comprising said shuttle message, and, on reception of an external frame, the transmission of a frame internal formed of echo fragments, before the complete reception of said external frame  6) Transmission network according to claims 4 and 5, characterized in that each CPAT concentrator comprises - a central computing unit provided with its RAMs,  program memories, and auxiliary equipment, - a plurality of line coupler circuits, each  coupler circuit comprising a microcontroller, a  RAM for communication with the central processing unit  calculation, a program memory.  7) Transmission network according to claims 4 and 5, characterized in that each internal frame comprises: - a first information field consisting of the message  shuttle, - a second information field consisting of a field  relating to the protocol for exchanging internal frames between  current and downstream CPAT concentrator, said first information field being formed by a first sub-field comprising a plurality of fragments or elementary messages (Fn) relating to different subscribers and by a second sub-field representative of the order of priority of transmission of said elementary messages relating to the various subscribers.  8) Transmission network according to claim 7, characterized in that said first subfield comprising a plurality of fragments or elementary messages relating to different subscribers is formed by concatenation of successive fragments or elementary messages of different subscribers, each successive fragment being chosen from the current set of different fragments to be transmitted and assigned to a channel according to the speech allocation and the age of the demand of each subscriber, said second sub-field representative of the order of priority of transmission of said elementary messages relating to the different subscribers being formed by concatenation of bits, each bit of said subfield being representative of the existence or non-existence of an elementary message, or fragment, relating to a subscriber and the weight of each bit in this same subfield being representative of the order of priority of the fragments to be transmitted.  9) Transmission network according to claims 7 and 8, characterized in that, following the reception by said CPAT concentrator downstream of an internal frame, the simultaneous reading of the first respectively second sub-fields makes it possible to reconstruct, at said concentrator CPAT downstream, the current set of different successive fragments of elementary messages from different subscribers to be transmitted.  10) Transmission network according to one of the preceding claims 3 to 9, characterized in that, prior to the transmission of said frames, a routing procedure is carried out making it possible to determine, independently of the topology of said network, a respective forward path. return between two sister addresses defined by the address of a generating CPAT concentrator and a destination CPAT concentrator, said routing procedure successively making it possible, by sending a probe message, - to determine the outward path, between CPAT concentrator  recipient CPAT generator and concentrator, this path  being formed by a succession of branches made up  by a multiplexed line between two CPAT concentrators  adjacent, - to validate the outward path, - to determine the return path between said concentrator  Receiving CPAT and said generating CPAT concentrator, - validating the return path, and - validating the route constituted by the outward path and by  the return path, said validation steps being  performed via a validation message  transit points generated by said concentrator  CPAT generator, respectively CPAT concentrator  recipient, said validation messages allowing  allocation of a transmission channel for said subscriber  at each successive CPAT concentrator built  direction of the outward and / or return path.  11) Method for routing digital data transmitted in packets in the form of data frames over a data transmission network consisting of a plurality of nodes each comprising a determined number of input-output ports interconnected to an adjacent node by lines of bidirectional transmission constituting branches, to establish a routing path between a generator node and a destination node, the other nodes constituting transit nodes, each of the nodes being identified by an address, the routing path being constituted by a forward path and a return path each formed by a succession of branches, characterized in that said method consists in a) transmitting from the generating node a probe message  routing dedicated to said recipient node on all  input / output ports of said connected generator node &  an adjacent downstream node, forming a transit node, and,  following receipt of said routing probe message by  each adjacent downstream node, b) to complete by concatenation said message probe of  routing with the address code of the adjacent downstream node  considered to form a routing probe message  completed dedicated to said destination node, c) to send from each of the adjacent downstream nodes  said completed routing probe message dedicated to said node  recipient on all input / output ports of said  adjacent downstream nodes connected to a new node  adjacent downstream, d) repeating steps b) and c) for any new node  adjacent downstream, so that said probe message  routing completed reaches all the nodes of the network, and,  on the first reaching of said recipient node by said  routing probe message completed, the outward path being  defined by the set of addresses of the transit nodes  traversed, contained in the routing probe message  completed, e) to repeat, from said recipient node, operating  as a sub-generator node, steps a), b), c) and d)  to said generator node, operating as a node under  recipient, by means of said routing probe message  completed dedicated to said sub-recipient node, said  return path being defined, on first hit  said node under recipient by said message probe of  routing supplemented by all the addresses of the nodes  of transit crossed from the sub-generator node to the node  sub-recipient, contained in the probe message  routing completed, said routing path being formed by  the set of addresses of the transit nodes forming the  way to go and way back.  12) Method according to claim 11, characterized in that the addresses of said nodes are absolute and / or relative addresses.  13) Method according to claim 12, characterized in that said relative addresses for a current transit node and its adjacent downstream nodes are formed by the pair of addresses of the input-output ports of said current transit node and the ports of input-output of each adjacent transit node respectively interconnected.  14) Method according to one of claims 11 to 13, characterized in that said routing probe message comprises at least - an identification flag of the destination node,  respectively sub-recipient, - an address field of the transit nodes, - an address field of the generating node, respectively  sub-generator.  15) Method according to claim 14, characterized in that, following the first attack of said recipient node, and prior to step e) consisting in repeating steps a), b), c) and d) towards said node under - recipient, this consists of inverting, in said completed routing probe message, the address field of the generator node, constituting the sub-recipient node, and the identification flag of the recipient node, which makes it possible to generate said completed routing probe message dedicated to said sub-recipient node.  16) Method according to one of claims 11 & 15, characterized in that, for a transmission network formed by a set of CPAT concentrators, according to claims 1 and 4, it consists  - reserving at least one transmission channel to constitute a routing channel,  - emitting said routing probes on said routing channel.  17) Method according to claim 16, characterized in that it consists, to determine an optimal path between an upstream point and a downstream point of said network:  to send from said upstream point a routing probe message to said downstream point to determine any path distinct from said current path,  to send, simultaneously, on said current path, a specific probe message to said downstream point, and on receipt by said downstream point of said routing probe messages respectively of specific routing probe,  memorizing the time of arrival at said downstream point of said routing probe message respectively specific routing probe message,  - calculate a time credit for the current path,  - to increase or decrease said time credit by the time difference separating the instants of arrival of said routing probe message respectively specific routing probe, which makes it possible to optimize the transmission time between upstream point and downstream point of the network .  18) Method according to claim 17, characterized in that the upstream and downstream nodes are constituted by any one of the CPAT concentrators comprising a subscriber link respectively by any CPAT concentrator distinct from the CPAT concentrator of the upstream node, which makes it possible to on the one hand, to optimize any elementary path comprising the upstream CPAT concentrator, constituting a current path, and, on the other hand, to restore a replacement elementary path comprising this same upstream CPAT concentrator, upon rupture of said elementary path.