Design method of a network of packet transmission of the deterministic type

IS 2 280 331 T3

DESCRIPTION

Sizing procedure for a deterministic packet-switched transmission network.

The present invention relates to deterministic packet-switched transmission networks.

A packet-switched transmission network enables the exchange of data in packet form between different geographically dispersed entities. Its interest is to reduce the number of physical transmission links necessary for routing the information, thereby allowing one or more physical links to be distributed in time between several information flows in some parts of their paths.

A packet-switched transmission network is made up of a set of interconnection nodes joined by transmission links wired or not and that constitute a meshing of the space where the entities with which it has to communicate are distributed.

A packet is presented in the form of a stream of bits whose constitution respects a strict organization defined by a network protocol with different parts or fields of which some are reserved for the service information necessary for its routing, such as the identities of the entity. issuer and the recipient entity, and others for the data to be transmitted.

A packet is introduced into the transmission network at one of its interconnection nodes in direct relationship with the issuing entity by means of a physical transmission link such as a cable or another. It is routed to the first interconnection node through the physical link that connects this first node with the issuing entity. Once it reaches this first interconnection node, it is redirected to another physical transmission link. This other physical transmission link makes it progress within the transmission network towards the recipient entity and allows it to reach either the recipient identity, or another connection node of the network closer to the recipient identity. it in turn redirects to another physical transmission link, and so on. In the end, the packet follows, up to the recipient entity, a so-called virtual path because only the time of the packet transmission materializes. This virtual path uses a more or less long chain of physical transmission links joined at their ends by interconnection nodes. Each interconnection node ensures, at its level, the dispatch of the packets that arrive, between the different physical transmission links that are directly connected to it, this dispatch being carried out from the service information contained in the packets. A very widespread example of a packet-switched network is provided by switched Ethernet networks.

In a packet-switched transmission network, the activity of the interconnection nodes is highly variable and depends on the routing of the packets. Thus, it can be found, at certain times, with interconnection nodes close to saturation or even saturated and causing packet loss, while others are under-exploited. This has led to real-time monitoring of the activities of the different connection nodes and the adoption of various procedures for the local forwarding of packages with a view to a better distribution of the tasks between the different interconnection nodes. The counterpart of this local forwarding is that the virtual path followed by a package from its issuing entity to its recipient entity is not completely defined in advance, which makes the transmission less reliable and above all, it brings a risk to the transit time of information. via network. In a certain number of situations, where the reliability of the transmission and the transit time of the information are critical data, as in the case of a transmission network that connects aircraft equipment, this local forwarding is avoided, including each node. connection a table that strictly defines the outgoing port that a packet must take based on its incoming port and the sender and recipient addresses. The packet-switched transmission network is then called “deterministic” since the virtual paths that the packets can take are fixed and require a reprogramming of the interconnection nodes in order to be modified and that the time of passage through each interconnection node is limited.

However, it is enough for the packet-switched transmission network to be of the deterministic type to guarantee its reliability; it must also have a dimensioning adapted to the information flows to be transmitted, that is, it does not present any possibility of saturation at the level of its interconnection nodes.

An interconnection node can be symbolized by a device that presents:

- a bank of input ports E, oscillating i from 1 to n, a bank of output ports Sj, oscillating j from 1 am,

- a bank of multiplexers Pj, one per output port Sj, each multiplexer Pj being destined to a given output port Sj and connecting with its destination output port Sj all the input ports E¡ capable of being connected to it,

- a bank of Pj FIFO type Fj memories (from the Anglo-Saxon "First In First Out") interspersed between the outputs of the multiplexers and the output ports Sj to manage queues in the vertical of the output ports and regularize packet flows on the physical transmission links connected to the output ports ^Sj ^,Y

IS 2 280 331 T3

- one or more routing automatons that control the different multiplexer (s) depending on the service information contained in the packets.

This representation of an interconnection node is only intended to facilitate understanding. It does not prejudge the real architecture in which it can only have a single central multiplexer that channels the flows that arrive from the input ports to the correct output ports.

The problem of saturation of an interconnection node is related to that of queue management, that is, the percentage of occupancy and the risks of overflowing the FIFO memories located vertically from its output ports. The transmission network must be dimensioned in such a way that the FIFO memories of its different interconnection nodes cannot overflow and that these have uniform capacities and filling percentages, the routing time of a packet being at the level of an interconnection node essentially made up of your time spent in the queue of the port of departure you take.

The sizing of a deterministic packet-switched transmission network is done by giving it a first form. The starting point is a supposed network topology adapted to the geographical arrangement of the equipment to be connected and the importance of the information flows to be exchanged, this network topology consisting of the definition of virtual VC paths for the routing of the different information flows , and the meshing of interconnection nodes connected to each other and to the equipment through physical connection links that support these virtual paths. It is then verified that the number, capacities and arrangements of the interconnection nodes and of the physical transmission links that connect the interconnection nodes with each other and with the issuing and receiving entities allow the passage, without problem, of the set of roads. and the network topology is retouched until this check is conclusive.

The packets of a flow of information coming from the same issuing entity and occupying the same virtual VC path initially occupy periodic time windows widely spaced in relation to the transmission capacities of the physical links used by a network. However, since their passage through a first interconnection node, they find themselves in competition with packets belonging to other information flows and according to other virtual paths, and for this reason they may be forced to wait in queues at the output port level. must take. Such a passage through a queue disturbs the regularity of the initial flow of packets. This disturbance or instability increases as it passes through the connection nodes crossed and can even cause packet aggregates or group transmission along virtual paths. These packet aggregates produce, when they cross a connection node, a temporary increase in the activity of the latter, which is absorbed thanks to the queues and which generates new delays and an eventual increase in aggregates. This phenomenon of aggregates must be taken into account in the enumeration of the virtual paths and in the determination of the capacities of the FIFO memories of the interconnection nodes, since it plays with the maximum transmission time of a virtual path and with the filling of the queues at the interconnection nodes.

The document "Intelligent Resource Dimensioning in ATM Networks INTERNATIONAL SWITCHING SYMPOSIUM", Berlin, 15-23 April 1995, mentions the use of Artificial Intelligence for the dimensioning of networks, but is not interested in the problems generated in the queues.

The subject of the present invention is a method for sizing a deterministic packet-switched transmission network taking into account the phenomenon of packet aggregation during their progression in the network along a virtual path.

The object of the invention is a method for sizing a deterministic packet-switched transmission network that puts equipment in communication to be interconnected and that includes interconnection nodes connected to each other and to the equipment through physical connection links, this consisting of procedure in establishing a list of information flows to be routed between the different equipment connected by the network, propose a supposed network topology adapted to the geographical arrangement of the equipment to be connected by the network and to the importance of the information flows to be exchanged between the equipment, the indicated topology consisting of the definition of virtual paths for the conduction of the different flows information, and a meshing of interconnection nodes connected to each other and to the equipment by physical connection links that support these virtual paths, estimate at the level of each connection node, the maximum delays introduced in packet transmissions by the instability phenomena caused by themselves and by the connection nodes already crossed by the packets, check that these maximum delays are compatible with the limits taxes and retouch the network topology while this compatibility is not obtained, characterizing this procedure because, In a network where the packets all have the same routing speed V in the physical connection links, the estimation of the maximum delays introduced by the phenomenon of instability in the packet transmissions in the different virtual paths goes through the determination of the instability component AJ_K, j added by an interconnection node K at the level of one of its output ports Sj in relation, by means of a buffer that houses a queue and by a multiplexing device, with N flows coming from the input ports E, , making this determination of the instability component AJ_K, j, in the case where each packet flow of a VC virtual path_l that enters the buffer through an input port E, present, between a packet aggregate and the packet or packet aggregate that follows it, a

ES 2 280 331 T3 minimum time interval sufficient to allow an emptying of the buffer after the reception of an aggregate of packets and before the reception of the packet following the aggregate, applying the relation:

Λ '

<img file="ES2280331T3_D0001.tif" />

where V is the routing speed of the physical connection link connected to the output port Sj and where Q is the maximum number of bits in the queue estimated from the relation:

<img file="ES2280331T3_D0002.tif" />

where N is the number of packet flows likely to converge towards the considered output port, that is, the number of flows that pass through the interconnection node and converge towards the considered output port Sj, this in the hypothesis that a flow packet is associated with a VC virtual path_b Bi the maximum size in bits of an aggregate of packets capable of reaching a VC_l by an input port E,, the maximum size that can also be expressed by the relation:

<img file="ES2280331T3_D0003.tif" />

where Ml is the maximum number of packets in an aggregate of packets capable of reaching a virtual path VCl through an input port E_l and being q_max the maximum number of bits in a packet.

Advantageously, the maximum size Bl in bits of an aggregate of packets capable of being presented in a virtual path VC_l through an E port of entry_l of a network interconnection node is taken equal to the largest aggregate size of B_VCllk packets likely to be presented in this virtual VC path_l which takes the input port E_l of the connection node K considered:

<img file="ES2280331T3_D0004.tif" />

being the largest size of B_{VCl lk} aggregate of packets capable of being presented in a VCl virtual path that takes the input port El of the connection node k considered obtained from the relationship system:

<img file="ES2280331T3_D0005.tif" />

K here being the number of connection nodes crossed by a virtual path considered and the index k identifying the connection nodes crossed by a virtual path considered in the order in which they are crossed by the packets, determining the different instability components AJ_l ,_k little by little going through the different virtual paths from its beginnings to its extremes.

IS 2 280 331 T3

Advantageously, once the instability components added by the different interconnection nodes at the levels of their different output ports have been determined, it is checked, in each virtual path VC_b than the minimum time intervals AT_IiK between the largest aggregate of packets and the next packet that arrives first at the levels of the various interconnection nodes found, obtained by the relation:

<img file="ES2280331T3_D0006.tif" />

they are enough to avoid any problem of saturation of the queues caused by groups that are too close together, that is, they comply well with the inequality:

<img file="ES2280331T3_D0007.tif" />

where M is a positive integer that represents the number of packets in the second group at most equal to the number of virtual paths that take the exit port of the interconnection node considered, selected according to the degree of security required for transmission, or the inequality for a virtual path

<img file="ES2280331T3_D0008.tif" />

Other characteristics and advantages of the invention will emerge from the description given below, of an embodiment given by way of example.

This description will be made with respect to the drawing in which:

- a figure 1 represents an example of a packet-switched transmission network topology,

- Figure 2 schematizes an interconnection node of the preceding transmission network, seen from one of its output ports,

- Figure 3 illustrates the saturation phenomenon that can occur at the confluence of two regular packet flows and that justifies the presence of a tail upstream from an exit port of an interconnection node,

- Figure 4 illustrates the same space occupation phenomenon as figure 3 but generalized at the confluence of N flows comprising packet aggregates,

- Figure 5 illustrates the need for a minimum time interval between two groups of packets of N flows that converge towards the same output port to avoid a possibility of overflowing the queue that regulates this output port,

- Figure 6 shows the origin of the instability phenomenon attributed to a regular packet flow when it converges with two other regular packet flows,

- Figure 7 shows the phenomenon of packet aggregation that can occur along a virtual path due to the instability introduced in the crossing of interconnection nodes of a transmission network located on this virtual path, and

IS 2 280 331 T3

FIG. 8 is a flow chart illustrating the main stages of a network sizing procedure according to the invention.

Figure 1 shows different sets of equipment 10 to 18 communicating with each other via a packet-switched transmission network 20. The sets of equipment 10 to 18 are of unequal importance and are geographically dispersed in an area covered by the packet-switched transmission network 20 that is schematized by a mesh of interconnection nodes represented by circles and physical interconnection links represented by segments. of straight lines that join the interconnection nodes between them. Each piece of equipment represented by a rectangle is connected to the packet-switched transmission network, at the level of one or more interconnection nodes located nearby, by one or more physical interconnection links.

The transmission of the packets on the network by the sender is carried out periodically. Each packet is entered in a time window and two successive packets occupy two successive windows. Each packet respects a certain formalism or protocol that depends on the transmission network. As a general rule, it is structured in bit fields, some of which are reserved for the service information necessary for its routing, such as the identities of the issuing entity and the recipient entity, and others for the data to be transmitted. At the beginning of a piece of equipment, the packets occupy, in the physical interconnection link that leads them to a first interconnection node of the network, the time windows regularly spaced. Upon reaching this first interconnection node, each packet undergoes a routing that consists of an analysis of its service information fields to determine through which output port the packet should leave the node and then in a channeling of the packet towards the queue. from the port of departure in question. The queue is essential because a packet can be found waiting, that is, competing in the exit port, with other packets coming from other entry ports of the connection node. The memory made in the form of FIFO will allow these packets to be stored while waiting for their turn to issue. After a certain waiting time that depends on the importance of the queue at the time of its passage, the packet is sent to a physical interconnection link that takes it to the destination equipment, either directly, or through other nodes of interconnection and other physical interconnection links.

Figure 2 models an interconnection node seen from one of its output ports Sj. It is distinguished, upstream from the output port Sj, by a memory 30 of the FIFO type (First In First Out in Anglo-Saxon language) fed with packets by a multiplexer 31 connected to the various input ports E_n AND₂, .. E¡ .., E_N liable to be channeled to the exit Sj. The multiplexer 32 is controlled by a forwarding automaton 31 that captures the packets that arrive at the input ports of the interconnection node, analyzes their fields of service information and determines the output ports through which they must leave the interconnection node.

The presence of a queue upstream from each exit port of a connection node raises the problem of its management, that is, of the tensions to be imposed on the traffics that feed this queue so that it remains limited and the estimation of its maximum size when these tensions are respected. In effect, a queue overflow can lead to packet loss while the maximum size of a queue determines the maximum delay that a packet can experience when transiting the output port associated with the queue.

In order to appreciate the properties of a queue located in an interconnection node upstream from an exit port, one begins by looking at the favorable conditions of an exit port of a first-level interconnection node that receives two regular flows of packets that they arrive at two different ports of entry, regular, which means that these two packet flows have not passed through, before, no other interconnection node where they could have passed through a queue so that they are not yet affected by instability phenomena, their packets succeeding one another in regular cadences.

Well, as represented in figure 3, two regular flows i1 and i2 of packets arriving with a speed V and with a periodicity T_i1 for flow i1 and T_i2 for flow i2 to two input ports E_i1 and E_i2 of a connection node of the first level to be directed to the same output port Sj, the packets of flow i1 being composed of qii bits and those of flow i2 by qi2 bits. Two cases can occur at the output Sj of the interconnection node:

- Either the incoming packet from stream i1 and the incoming packet from stream i2 occupy temporary windows without recovery, the size of the window being equal to this level to the duration of the packet since it has not experienced any instability. They are then called non-concurrent and are routed without experiencing delay to the common port of exit. Packages 40 and 50 are an example of non-participating packages.

- or else the packet entering stream i1 and the packet entering stream i2 occupy time windows that are recovered by at least one bit. They are then called for containment. The second packet in time must wait for the end of processing the first packet in a queue before it can be directed to the outgoing port. Packages 41 and 51 are an example of packages in contention.

IS 2 280 331 T3

Or two non-participating packets, one received first by the interconnection node on the date of receipt t_i1 and the other received second on the date of receipt t_AND, the non-participating property is expressed by the condition:

<img file="ES2280331T3_D0009.tif" />

being q_i1 the size in bits of a packet from stream i1, in fact the packet received first. while the phenomenon of containment is expressed by the condition

<img file="ES2280331T3_D0010.tif" />

&lt;t., + ti

<img file="ES2280331T3_D0011.tif" />

When two packets are in contention, the second is delayed for the time necessary for the treatment of the first and goes to the exit immediately after the first without leaving a free time window between them. The second package then forms, with the first, an aggregate of two packages. The phenomenon of packet aggregation increases from interconnection node to interconnection node in the path of an information flow. Thus, when a flow of packets arrives at the entrance of an interconnection node lower than the first level, it may contain more or less important aggregates of several packets originating from the routings experienced by the packets in interconnection nodes found upstream. These aggregates disturb the flow rates of packet flows, adding to them the phenomenon of instability and causing sudden increases in activity at the level of the interconnection nodes.

To appreciate this phenomenon, one is placed in the hypothesis closest to reality, illustrated by figure 4, of an exit port of a lower-level interconnection node that receives a group of N aggregates of packets in contention, coming from N different packet flows arriving at the interconnection node at the same transmission speed V, through N different input ports. These N packet aggregates must wait in a queue upstream from the outgoing port to be broadcast, each in turn, to the interconnection physical link connected to the outgoing port.

Assuming:

• that the maximum size, in number of bits, of a packet authorized in the network is q ^, • that the maximum size of an aggregate in number of packets, coming from the nth stream is M, so that the maximum size in bits B From an aggregate from an nth flow is equivalent to:

Bi - Mi X CJmax • that the set of flows reaches the queue at the apparent speed NV, and • that the queue empties at the speed V, the maximum quantity Q of bits that can be expected in the queue is at most:

<img file="ES2280331T3_D0012.tif" />

where Sup {B¡} is the size in bits of the most important aggregate among those of the N input streams,

ES 2 280 331 T3, that is, the sum of the bits of all the aggregates minus the bits of the most important aggregate, which can be any one of them. If all aggregates have the same size B, the maximum number of bits that can wait in the queue is equal to:

Q = (N - 1) B

From the maximum amount of bits that can be waited in the queue, the maximum time that can take in the transmission of packets, the passage through the interconnection node considered, is deduced, the maximum time that corresponds to the increase in instability AJ contributed by this node of interconnection to packet flows:

(2)

So that this maximum number of bits that can be expected in a queue is not exceeded, it is necessary that the queue has, between two groups, the time to empty enough to accommodate the bits of the next group. This time corresponds to a minimum AT time between two groups. If a single flow is considered, the minimum time AT¡ that must separate a first aggregate B¡ from a second aggregate B'¡ must respect the condition:

<img file="ES2280331T3_D0013.tif" />

In the most general case illustrated in figure 5 where a group of N aggregates B'¡ that arrive simultaneously at N flows is followed by a group of N aggregates B, already arrived simultaneously at N flows, the minimum time that AT separates the two groups must respect the condition

<img file="ES2280331T3_D0014.tif" />

Apart from these considerations on the clearing of an interconnection node by packet flows, we move on to virtual paths, that is, to the paths effectively followed in the transmission network by the different information flows exchanged between the equipment connected to the network. of transmission. In the case of a deterministic packet-switched transmission network, these virtual paths are invariable, all packets of the same flow experiencing the same routing through the network interconnection nodes. The maximum time of reception by a recipient equipment of a message transmitted through the transmission network by an issuing equipment can then be appreciated through the maximum transmission time of the packets to the virtual path that connects them through the network.

It is based on the hypothesis that the traffic of a virtual VC path is always regulated at its source so that a minimum time T separates two of its successive packets. As shown in figure 6, the passage through the first interconnection node by the packets that follow a virtual path VC, is manifested by the appearance of an instability due to the phenomenon of contention at the level of this interconnection node with packets that follow other virtual paths that take the same exit port. This contention phenomenon means that a packet that follows a virtual VC path can be found at the exit of an interconnection node within an aggregate of packets following other virtual paths and at any position within this aggregate. The possibility of aggregation when passing through an interconnection node of the first level makes the width of the time window in which a packet can be found pass, from the maximum width of a packet at the beginning of the virtual VC path to the width of the aggregate plus possible and introduces an instability phenomenon since the width of the packet does not vary but its position is displaced in relation to its emission window by an unpredictable delay of which only the upper limit is known. This instability corresponds to the maximum delay that the packet may experience as it passes through the interconnection node since it can cross it without any delay if conditions are favorable or with the maximum delay if conditions are particularly unfavorable. In the example of figure 6, the position of the window of a packet that was secure before the first level interconnection node and corresponded to the emission window, becomes insecure after the interconnection node, the insecurity covering the time of three packages.

IS 2 280 331 T3

The instability experienced by the packets according to a given virtual path increases as the interconnection nodes are cleared. More precisely, the instability J_{l&gt; K} that affects a flow of packets according to a virtual path VCi, at the level of the output of the K-nth interconnection node found, it is equal to the sum of the instability components contributed by all the interconnection nodes crossed:

<img file="ES2280331T3_D0015.tif" />

determining the instability components contributed by the different connection nodes from relation (2).

When the giga that affects the packets of the same information flow, that is, the packets that follow the same virtual path VC_l the minimum period T is approaching or exceeding_l that separates the emission of two successive packets, an aggregation phenomenon can occur at the level of the virtual path itself. Indeed, if the order of the packets according to a virtual path cannot be modified since the packets follow one after another the same and only path within the transmission network, which is of a deterministic type, the packets pass the same interconnection node at different times, with variable transit times that depend on the occupation, at the time of their passage, of the queue of the exit port they take. Thus, after a packet that has taken a long time to cross an interconnection node, the next packet on the same virtual path may take less time and so on resulting in an aggregation of packets on the virtual path if instability affects the exit, the virtual path becomes of the same order or greater than the minimum period that separates, in the emission, two successive packets. Figure 7 illustrates a case of packet aggregation that can occur in a virtual path that presents instability at the output slightly greater than twice the time interval T_l that separates two successive packages at the time of their introduction in the virtual path. A first packet 60 experiences a particularly long treatment time practically equal to instability, since it crosses the interconnection nodes taken by the virtual path at times when the queues are particularly loaded, and encounters a delay practically equal to twice the interval of time T, that separates it in the emission of other packets. The packet that follows it recovers it as it encounters more favorable routing conditions but cannot pass it, so it also experiences a delay of the order of a time interval T_l whereas the following packet 62 also encounters favorable routing conditions and is practically no longer blocked by the packets that precede it on the virtual path. The result is that upon arrival of the virtual path, there are time intervals T_l empty while they should contain a package and others that contain package aggregates while they should only contain a single package at a time.

More precisely, the maximum size of an aggregate B_VCllt liable to be presented in a virtual path VC_lwhich takes the input port E_l of a K nth connection node K crossed by the virtual path VC_l is linked with the sum of the instability components AJ_l ,_K accumulated in this virtual path VC_l when passing through the interconnection nodes found before this K nth interconnection node and in the minimum time interval Ti of separation of the packets as they enter the virtual path through the relationship system:

<img file="ES2280331T3_D0016.tif" />

and the minimum time interval that separates such an aggregate from the next packet on the VC virtual path_lalways at the level of the entry port The value of the K nth interconnection node crossed has the following value:

<img file="ES2280331T3_D0017.tif" />

this at the input of node k, knowing that an aggregate can only occur when the next packet has not been delayed in the queues through which it has passed. This packet is said to conform if the distance that separates it from the aggregate is&gt; AT_l.

IS 2 280 331 T3

The maximum size Q of a queue upstream of an exit port Sj of an interconnection node k, in the presence of a single group of packets or aggregates of packets obtained previously (relation (1)) can also be expressed as a function of the flows that take the N virtual paths VC_l that pass through the output port Sj considered:

N

Q - ^ Aggregate size max _VCi - Sup ^ Aggregate size max _vc J ^w is / sw

The equilibrium condition (relation (3)) that guarantees not to exceed this maximum size in the presence of the only traffic of a virtual VC path_l imposes a minimum time interval AT_l between two groups:

ET,&gt;

Now this checks by reason of the relation (6), the condition:

<img file="ES2280331T3_D0018.tif" />

So that the equilibrium condition in the presence of a single virtual path is:

<img file="ES2280331T3_D0019.tif" />

V

Since, on the other hand, it has been seen that a minimum time interval AT_l between two packages or aggregates of a virtual path VCl could only occur between an aggregate followed by a separate package, we have:

<img file="ES2280331T3_D0020.tif" />

In the end, the equilibrium condition in the presence of a single virtual path is expressed:

<img file="ES2280331T3_D0021.tif" />

In the presence of several virtual paths, the minimum time interval to be respected to avoid everything exceeds the maximum size Q_max of a queue must take into account traffic interactions of all virtual paths that pass through the queue. In the worst case, where the contention is maximum, all the virtual paths presenting at the same time aggregates of maximum size packets, the second group will be made up of separate packets that are not all presented at the same time. The hypothesis is therefore formed that in the end

ES 2 280 331 T3 of the first group, the queue reaches its maximum capacity and that it receives in the course of the second group N separate or conforming packets of which only M are forced, that is, they are covered with at least one bit. Under these conditions, it can be guaranteed that the queue will not exceed its maximum capacity if the first packet of the second group arrives after an AT time after the first group, long enough for the queue to have been emptied of M-1 packets. This comes to admit the condition:

<img file="ES2280331T3_D0022.tif" />

which is also expressed from the date t_and of reception of the end of the first group and of the date of reception ζ of the beginning of reception of the second group in the queue:

<img file="ES2280331T3_D0023.tif" />

Now, if we take as a time reference the moment of the beginning of reception of the first group in the queue:

<img file="ES2280331T3_D0024.tif" />

<img file="ES2280331T3_D0025.tif" />

(where t¡ is the time of arrival to the waiting queue of the jth packet in contention of the second group by reference with the time of arrival of the first group to the queue) so that the equilibrium condition is also expressed:

Aggregate size max ^ J min ^} --—-&gt; (M -1) íSjiM *

4th

V

This equilibrium condition is translated, for any one k of the virtual paths that take the queue, by the following condition on its minimum time interval AT_K:

<img file="ES2280331T3_D0026.tif" />

The relationships that have just been established make it possible to size a deterministic packet-switched transmission network to meet particular latency or routing time stresses, and

ES 2 280 331 T3 routing regularity or instability imposed on the information flows that use their virtual paths.

The dimensioning of a deterministic packet-switched transmission network is carried out by successive fine-tuning. It begins by proposing an initial network topology, that is, a set of fixed virtual paths that interconnect the connected equipment, and a meshing of interconnection nodes and physical connection links between interconnection nodes and between interconnection nodes and equipment that support virtual paths, which seem to be able to accommodate the geographical disposition of the equipment to be connected, and have sufficient returns for the amounts of information to be exchanged between the teams. It is then verified that the proposed topology supports the different traffic foreseen both at the level of the physical connection links, whose flows must be sufficient to ensure the circulation of the local traffic that takes them, as well as at the level of the interconnection nodes whose occupation of the queues must make it possible to respect the tensions imposed by the equipment, on the times and routing regularities of the information flows. While this check is not conclusive, the proposed topology is adjusted both at the level of the virtual paths (number and configuration), as well as at the level of the interconnection nodes (number and capacity in input and output ports) and physical connection links. (number and flow rates), seeking a certain homogeneity between the different interconnection nodes and the different physical connection links.

The main difficulty resides in the stage of checking the correct adaptation of the proposed topology to the various stresses imposed. In order to carry out this check, it is proposed to determine, incrementally, by lowering the routes of the virtual paths, the instability components added by the different interconnection nodes at the level of their different exit ports, first avoiding the problem of possibility of queue saturation caused by successive groups of packets that are too close together, then checking on each virtual path that such a problem does not arise. The knowledge of the instability components added by the different interconnection nodes in their output ports makes it possible to easily determine the total instability that affects each virtual path of the transmission network to see if it is low enough to allow respecting the voltages on the times and the regularity of the transmission imposed by the equipment put in communication.

Indeed, the instability component at the level of one Sj of the output ports of an interconnection node K can be determined by means of the relation (2), from the maximum quantity Q of bits that can be found in the queue of this output port and the transmission speed V of the physical connection link that leaves this output port:

<img file="ES2280331T3_D0027.tif" />

The transmission speed V of the physical connection link that starts from the output port is a piece of information that emerges from the characteristics of this physical link. The maximum quantity Q of bits of the queue can be determined, by means of the relation (1), as a function of the maximum sizes of bits Bl, of the aggregates of packets that converge towards the considered output port Sj:

where N is the number of packet flows capable of converging towards the considered output port, that is, the number of virtual paths that arrive at the interconnection node and which converge towards the considered output port Sj.

The maximum size in bits Bi of an aggregate of packets can also be expressed by the relation:

<img file="ES2280331T3_D0028.tif" />

where M_l the maximum number of packages in a package aggregate and q_lllav the maximum number of bits in a packet. It is a datum at this level of increase since it refers to the entry ports of the interconnection node and consequently, either to the exit ports of interconnection nodes located upstream in the virtual roads that have been the subject of previous stages in the incrementation, or the output ports of the equipment.

More precisely, the maximum size B_l in bits an aggregate of packets capable of being presented in a virtual path VCl in a network interconnection node K is taken equal to the size of the largest aggregate of packets

IS 2 280 331 T3

B_{VCl lt} liable to occur at the level of the interconnection node K to converge towards the output port Sj on the virtual path VCi that takes an input port of the connection node K considered:

<img file="ES2280331T3_D0029.tif" />

obtaining the largest aggregate size of packets B_{VCl lt} liable to occur in a virtual path VCl that takes an input port of the connection node K considered from the relationship system (5):

<img file="ES2280331T3_D0030.tif" />

where K is the number of interconnection nodes crossed by a virtual path considered before reaching the level of the port of departure considered of the interconnection node studied and the index k that identifies the connection nodes crossed upstream, by a virtual path considered in the order in which they are traversed by the packets.

It is observed that the preceding relationship system only resorts to instability components AJ_lt with respect to exit ports of interconnection nodes located upstream in the virtual roads in question and consequently determined in the course of previous stages of the incrementation.

Once the instability components added by the different interconnection nodes at the levels of their different output ports have been determined, it is verified, in each virtual path VCl, that the minimum time intervals AT_l,_K between the largest aggregate and the next packet that reaches the levels of the various interconnection nodes found first, obtained by the relation (6):

<img file="ES2280331T3_D0031.tif" />

This at the exit of node K is enough to avoid any problem of saturation of the tails caused by groups that are too close, that is, they comply well with inequality (8):

<img file="ES2280331T3_D0032.tif" />

where M is a positive integer at most equal to the number of virtual paths that take the exit port of the interconnection node considered, selected according to the degree of security required for transmission, or the inequality (9):

<img file="ES2280331T3_D0033.tif" />

Once these conditions are met, the estimates of the different instability components are admitted and used to determine the instability that affects each virtual path and checks that it is compatible with

ES 2 280 331 T3 the latency and regularity stresses imposed on the different information flows exchanged between the devices. The conditions and voltages not respected refer the proposed topology into question, which is modified until times that are satisfactory.

Figure 8 is a flow chart illustrating the main steps of the sizing procedure of a packet switched transmission network using the above conformance checking method. This flowchart begins with two separate tasks, one for proposing a deterministic packet-switched transmission network topology that takes into account the geographical locations of the equipment to be connected and the importance of the information flows to be exchanged between them. , the other 71 of inventory that lists the latency and traffic regularity tensions that must be respected by the information flows exchanged by the equipment through the network. The task 70 for proposing a network topology makes a proposal, in the form of a data table 72, of a deterministic network plane with fixed virtual paths, at least one per information flow and a meshing of interconnection nodes connected to each other. and with the equipment through physical connection links in which the different virtual paths are traced in a fixed way. The inventory task 71 lists, in the form of a data table 73, the latency and traffic voltages to be respected by the different information flows, consequently by the different virtual paths that lead these flows. The two data tables 72 and 73 relating to the proposed topology for the network and the transmission voltages associated with the different information flows to be transmitted are then used by a task 74 to check the adequacy of the proposed topology to the different voltages which determines, incrementally, according to the method just described, the instability components contributed by the interconnection nodes at the level of their different output ports, deduces from its instability components, the instabilities that affect the different proposed virtual paths, verifies that the minimum time intervals AT_kk that separate two packets or aggregates of packets in each virtual path and at the levels of the various interconnection nodes found are sufficient so that the determinations of instability amplitudes cannot be questioned and produce, in the form of a data table 75, a list of the virtual paths that pose problems, either because they do not respect the minimum time intervals between packets or aggregates of successive packets, or because they are affected by an instability that is too important to respect the latency times or the regularity stresses imposed on the information flows that they route, with a list of exit ports of interconnection nodes where these problems have been detected for the first time at along the course of each virtual path. This table 75 with its list of virtual paths that pose problems and exit ports of the interconnection nodes where the problems detected in the virtual paths appear is then used by a task 76 for modifying the network topology that proposes a new routing of virtual roads with problems, without modifying the meshing of the interconnection nodes and of the physical links of connections when it is possible to regulate these problems by means of a redistribution of the network resources between the different virtual paths, or by modifying the meshing of the network by means of the contribution of new physical links of connection between the interconnection nodes, increase in the number of entry or exit ports of some interconnection nodes and even through the contribution of new interconnection nodes. This task 66 provides a new topology proposal for the network that takes the place of the preceding one in the data table 72 which is in turn subjected to the verification task 74, this until the data table 75 that repeats the paths virtual problems is left empty.