Monitoring and stimulating of complex systems, in particular of flow and congestion mechanisms and control in communication networks

• US 20030161266A1
• Filed: 03/11/2003
• Published: 08/28/2003
• Est. Priority Date: 03/01/2000
• Status: Abandoned Application

• Current Assignee: Inria Institut National de Recherche EN Informatique et EN Automatique
• Original Assignee: Inria Institut National de Recherche EN Informatique et EN Automatique
• Inventors: Hong, Dohy, Baccelli, Francois
• Application Number:
  US10/220,014
• Publication Number:
  US 20030161266A1
• Time in Patent Office: Days
• US Class Current: 370/229
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/145 involving simulating, designing, planning or modelling of a network
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/0829 Packet loss
• CPC Class Codes: H04L 43/0852 Delays
• CPC Class Codes: H04L 43/0864 Round trip delays
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/193 at the transport layer, e.g. TCP related
• CPC Class Codes: H04L 47/26 using explicit feedback to the source, e.g. choke packets
• CPC Class Codes: H04L 47/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]
• CPC Class Codes: H04Q 3/0083 Network planning or design; Modelling of planned or existing networks

Abstract

The invention concerns a device and a method assisting in monitoring and/or simulating a complex system, in particular a telecommunication network. It consists in storing data in matrix form, of dynamically variable structure, with iterative multiplication in max-plus algebra of a current matrix of network data and an instantaneous matrix of the network parameters.

Claims

1. Device for assisting the monitoring and/or simulation of a complex system, in particular of a communication network, characterised in that it comprises:

a memory (ROM, RAM) for storing a first set of data representing parameters of the network as well as for receiving at least a second set of data representing events in the network, a portion of the memory being reserved for storing data in matrix form,

a computing unit (CAL) capable of effecting on at least two matrices of dynamically variable structure an operation forming a product according to the algebra known as MAX-PLUS,

a modelling unit (MOD) for constructing at least a first matrix (Z(n)) and a current matrix (A(n)) respectively according to the first set of data and second set of data according to a selected model, and

a pilot unit (PIL) for applying iteratively the first matrix and the current matrix to the computing unit, the product matrix obtained (Z(n+1)) becoming a new first matrix.

2. Device according to claim 1, characterised in that the first set of data comprises data relating to the topology of the network.

3. Device according to claim 2, characterised in that the first set of data comprises the number (K) of routers of the network crossed by a connection to be monitored or simulated and properties of the routers.

4. Device according to claim 3, characterised in that the first set of data comprises memory sizes of the routers (b_K).

5. Device according to one of claims 2 to 4, characterised in that the first set of data comprises statistical properties of the traffics offered in the network.

6. Device according to one of the preceding claims, characterised in that the modelling unit comprises:

a static modelling sub-unit (ST) for constructing the first matrix according to the first set of data, and

a dynamic modelling sub-unit (DYN) for constructing at least one current matrix according to the second set of data.

7. Device according to one of the preceding claims, characterised in that the second set of data comprises information relating to losses (p_, p+) in the network.

8. Device according to one of the preceding claims, characterised in that the second set of data comprises information relating to transverse fluxes in the network relative to a controlled connection to be monitored or simulated.

9. Device according to one of claims 7 or 8, characterised in that the second set of data comprises information relating to congestion in the network.

10. Device according to one claims 7 to 9, characterised in that the second set of data comprises information relating to overtaking of delays (T0) in the network.

11. Device according to one of the preceding claims, characterised in that the product matrix represents an output in the network associated with the connection to be monitored or simulated.

12. Device according to claim 11, characterised in that the product matrix represents an average output in the network.

13. Device according to claim 11, characterised in that the product matrix represents fluctuations of an instantaneous output.

14. Device according to one of the preceding claims, characterised in that the modelling unit is contrived to construct a plurality of matrices in a number corresponding substantially to the number of packages in the network.

15. Device according to one of the preceding claims, characterised in that the modelling unit selected comprises the consideration of variable size of a window (w_n) used to control the number of packages in the network.

16. Device according to claim 15, characterised in that model selected comprises the consideration of a network comprising routers with a ‘

first-come, first-served’

-type discipline.

17. Device according to one of claims 15 or 16, characterised in that the model selected comprises the consideration of a network comprising routers with a WFQ-type discipline.

18. Device according to one of the preceding claims, characterised in that the model selected comprises the consideration of a network controlled by a TCP-type protocol.

19. Device according to one of claims 15 to 18, characterised in that the model selected comprises the consideration of a determinist service (s).

20. Device according to one of claims 15 to 18, characterised in that the model selected comprises the consideration of a random service (s).

21. Device according to one of the preceding claims, characterised in that the current matrix at least comprises dynamically variable coefficients (A_ik).

22. Device according to one of the preceding claims, characterised in that the product matrix obtained is a vector shown by a single-column matrix (Z(n)).

23. Method of assisting the monitoring of a complex system, in particular of a communication network, characterised in that it comprises the following stages:

a) obtain first data representing network parameters,

b) construct a first matrix (Z(n)) according to a selected model according to the first data,

c) receive at a selected instant at least a second set of data representing events in the network,

d) construct at least a second matrix (A(n)) of variable dynamic structure according to a selected model according to the second set of data, and

e) carry out on the matrices an operation forming a product according to the algebra known as MAX-PLUS, the product matrix obtained (Z(n+1)) representing the state of the network at the aforesaid selected instant.

24. Method according to claim 23, characterised in that it further comprises the following stage:

f) repeat at selected instants the stages c), d) and e), whereas the product matrix obtained becomes the first matrix after stage e)

which makes it possible to follow a temporal evolution of the state of the network at the selected instants.

25. Method of simulating a complex system, in particular mechanisms for flux and congestion control in a communication network, characterised in that it comprises the following stages:

a) obtain first data representing parameters particular to the network,

b) construct a first matrix (Z(n)) according to a selected model according to the first data,

c) simulate events in the network and provide at least a second set of data representing the events,

d) construct at least a second matrix (A(n)) according to a selected model according to the second set of data, and

e) carry out on the matrices an operation forming a product according to the algebra known as MAX-PLUS, the product matrix obtained (Z(n+1)) representing the state of the network being subjected to the above-mentioned events.

26. Method according to claim 25, characterised in that it further comprises the following stage:

f) repeat, for successive events, stages c), d), and e), whereas the product matrix obtained becomes the first matrix after stage e),

which makes it possible to predict an evolution of the state of the network according to the above-mentioned events.