WO2006008349A1

WO2006008349A1 - Method and device for measuring the quality of at least one internet protocol service

Info

Publication number: WO2006008349A1
Application number: PCT/FR2004/001562
Authority: WO
Inventors: Paul Rolland
Original assignee: Witbe Net
Priority date: 2004-06-23
Filing date: 2004-06-23
Publication date: 2006-01-26

Abstract

The invention relates to a method for measuring the quality of at least one Internet protocol service from an active device embodying a measuring robot connected to a first IP network used as a referential to a target device embodying the host of said service and connected to a second IP network with which the first IP network can communicate. The measuring robot and target device communicate in the form of packets directed by routers pertaining to the IP networks, said routers each comprising a variable route parameter. According to the inventive method, (a) a data stream is emitted by the measuring robot in conformance with a protocol used by the service measured, said data stream comprising packets which each have an initial route parameter (TTL), and the initial route parameter is stored in association with each packet emitted, (b) the route parameter is conditionally modified at each router met by a packet, or on the target equipment, (c) according to the value of the route parameter, a packet containing an identification of the corresponding emitted packet is selectively redirected by the router or by the target equipment towards the measuring robot, and (d) the measuring robot calculates a quality of service index from the route parameter values of emitted packets and the route parameters of redirected packets in conjunction with the emitted packets. The invention also relates to a device for implementing said method.

Description

INTERNET PROTOCOL SERVICE »

The present invention relates generally to the determination of the quality of service of network protocols such as the Internet Protocol (IP for "Internet Protocol" according to the term Anglo-Saxon dedicated).

Technical reminders

Currently, networks operating with the IP Internet protocol are used both for Internet use and Intranet use, the essential difference being the choice of addressing plans associated with these uses.

In Internet use, IP networks have a public IP address and include a routing function of the transmitted information, which is in the form of "IP packets" (hereinafter packets).

In Intranet use, IP networks have a private address that is not published and therefore can not be routed over Internet IP networks to which Intranet IP networks are likely to be connected. Addressing Intranet IP networks is now standardized according to RFC1918.

It should be noted that there is not a single global IP network, but a dynamic interconnection of several thousand IP networks. These IP networks have variable sizes and can be variable geometry. However, they share common characteristics, including:

- a unique numbering system called "Autonomous System" (AS) in English terminology, for "Autonomous System", the attribution of which is worldwide (for example AS15436); this system makes it possible to group all the blocks of IP addresses (aggregation) under an AS so as to allow the announcement of all the world routes; an exchange system, between the Internet operators in charge of the different IP networks, of their set of routes according to a dynamic protocol of the EGP type (for "External Gateway Protocol" in English terminology, or an external gate protocol), in particular the BGP4 protocol ("Border Gateway Protocol" in English terminology, or external access protocol).

There are three ways of exchanging routes between operators: - "Peering" (peer-to-peer exchange): graceful exchange at the level of global trading nodes. This is the original method today more and more abandoned;

- Transit: an operator allows another operator to advertise his set of routes through his IP network, for (financial) compensation;

- the private "Peer": an operator exchanges for private purposes and directly from his IP network traffic (in particular his set of routes) with another operator.

The robustness of the Internet is linked to this ability to interchange dynamic sets of route sets from one operator to another operator. This is related to the so-called "unconnected" operating mode of the IP protocol.

A consequence of this is that it is not easy, apart from reading BGP route tables which contain all the routes of an operator according to this BGP protocol, to predict an IP route that will follow an IP packet. data from a point belonging to a first IP network to a point belonging to a second IP network. Moreover, the track can be asymmetric at any time, that is to say that between two points exchanging data IP packets, the return path goes through different routers (in particular in number) of routers crossed during the way to go. On the other hand, there are two types of IP network infrastructure:

a typology of traditional operators, as illustrated in FIG. 1a of the drawings: an operator uses high-speed telecommunications media (which are specific to him or made available by other operators), for example of the ATM type ( Asynchronous Transfer Mode or asynchronous transfer mode), SDH ("Synchronous Digital Hierarchy"), or WDM (Wavelength Division Multiplexing), bare fiber, satellite, etc. It thus creates its private IP network infrastructure that can be used by potential customers. This IP network is integrated, in the case of an Internet IP network, in a given autonomous system of XYZ number and uses internal routing (IGP) type ("Internai Gateway Protocol") Anglo-Saxon terminology, ie internal door protocol), operating on different routers R of different geographical locations; the BGP4 external access protocol allows interconnection with other Internet operators; - a typology of Internet operators: a given AS XYZ uses high-speed Internet IP networks either on a single multihomed site ("Multihoming") or, as illustrated in Figure 1b, in multi-sites with routers R geographically distributed and connected by the BGP4 protocol to different operators of corresponding geographies.

The two typologies presented make an equivalent Internet service and are not differentiable in terms of BGP4 route announcements.

It should be noted that the complexity of the global global structure of IP networks leads to a major complexity of the location of faults, responsibility of the different actors and inter-operator obligations; as a corollary, there are many elements that influence the quality of the service rendered (QoS for the term "Quality of Service") by IP networks.

State of the prior art

It follows from the foregoing that it is difficult and complex to measure the quality of service if we consider a complex global connection chain, an example of which is illustrated in FIG. 2, and which is associated with multiple services, such as, for example, messaging and a website (Web site).

In this respect, operators nowadays ensure an obligation of means and not an obligation of results on their services, and offer at best:

- indications of use or quality on the last mile (part called "Last Mile" network), ie statistics from the router R closest to the customer), and a commitment on a level of availability of the latter kilometer;

- indicators of the functioning of their backbone ("backbone" according to the Anglo-Saxon term) in the form of a "meteorology" of the backbones and contractual commitments on transit times in their backbone, all this remaining however very plot.

It is paradoxical that, in all services of the IP protocol and in particular services provided by so-called RFC messages ("Request For Comment"), there is a very large number of contributions concerning the different flows of IP data packets, but only a very limited number of contributions regarding the measurement of quality of service as perceived by the end users of IP networks.

The Applicant is thus aware of only two contributions aimed at quality of service. A first of these is materialized by the utility says

"Ping", which makes it possible to detect if an equipment is available ("alive" according to the English term consecrated) or not; this utility works according to the ICMP protocol (for the English expression "Internet Control Message

Protocol ", or Internet Control Message Protocol) and is very frequently and easily used, since in the mind of the user, the first reflex is to check whether the remote service is active or not.

However, the ping utility associated with the protocol in question has a very limited scope: - it does not characterize the quality of a network in particular in terms of bit rate, but only allows to understand if a remote device is active or not and the time required for a package sent to him to return;

- it is limited mainly to an IP Intranet network use, because many operators perform a filtering eliminatory on the protocol

ICMP to make it inoperative and furthermore, many routing devices treat this protocol only if the load of the equipment allows it, the priority being not to slow down the traffic;

the ICMP protocol being specific, it does not reflect the uses conventionally performed according to the UDP protocols ("User Datagram

Protocol "in English terminology, or user datagram protocol) and TCP (Transmission Control Protocol in English terminology, or transmission control protocol).

A second known contribution lies in the utility "Traceroute", which has the advantage of allowing a user to visualize (trace) the path borrowed by IP packets between a point A (typically the user's personal computer) and a point B (typically a remote server).

Here again, the limitations of this utility and the way Internet IP networks operate give it limited interest. In particular :

- Traceroute can be used according to the UDP protocol (and sometimes according to ICMP) but never according to a set of protocols used jointly (for example TCP and UDP). - Traceroute visualizes the path in the A to B direction but requires identical manipulation from point B to view the path from B to A (return path), even if some operators start to install "mirror" servers on their backbones to assist experienced users in this kind of manipulation.

It should also be noted that, for users having the appropriate technical knowledge, some operators provide read access to the BGP4 routing tables which indicate the paths traversed by the packets. But this data can only be exploited with perfect control of the BGP4 protocol and a thorough knowledge of Internet IP networks. In addition, this only gives a local representation that reflects the choice of routing policies made by the operators.

Thus, there is currently no technique to offer quickly and conveniently, that is to say in particular without a complex reprocessing of data collected by known utilities, realistic measures of quality of service at the level of IP.

Summary of the invention An object of the invention is therefore to provide a quality of service measurement of networks and IP services whose results are reliable regardless of the complexity of the IP networks encountered during the measurements.

To this end, the invention proposes, according to a first aspect, a method for measuring the quality of at least one Internet protocol service from an active equipment constituting a measurement robot, connected to a first IP network serving as a a repository to a target equipment constituting the host of said service and connected to a second IP network with which the first IP network is able to communicate, the measurement robot and the target equipment being able to communicate with each other; another in the form of packets directed by routers belonging to the IP networks and each having a modifiable path parameter, characterized by the following steps: (a) sending by the measurement robot a data stream in accordance with a protocol used by the measured service, this data flow comprising packets each having an initial path parameter (TTL), and storing the initial path parameter in association with each transmitted packet, (b) at each router encountered by a packet or at the target equipment, unconditional modification of the path parameter,

(c) according to the value of the browse parameter, selective return by the router or the target equipment to the measurement robot of a packet containing an identification of the corresponding transmitted packet, and (d) calculation by the robot of measurements, based on the values of the sent packet browsing parameters and the packet traversal parameters returned in correspondence with the transmitted packets, of a quality of service index.

According to a second aspect, the invention proposes measuring robot equipment for measuring the quality of at least one Internet protocol service, characterized in that it is able to be connected to a first network. IP serving as a repository for performing measurements on a service implemented on a target device connected to a second IP network with which the first IP network is able to communicate, the measurement robot and the target equipment being able to communicate with each other in the form of packets directed by routers belonging to the IP networks, each packet having an editable path parameter, the routing parameter of each packet being able to be modified in a conditional manner at each router encountered or at the level of the target equipment, and according to the value of the routing parameter, each router or the target equipment being able to send selectively to the measurement robot a packet containing an identification of the corresponding transmitted packet, and in that that he understands:

(a) means for transmitting a data stream in accordance with a protocol used by the measured service, said data stream comprising packets each having an initial routing parameter (TTL),

(b) means for storing the initial scan parameter in association with each transmitted packet, and

(c) computing means capable, from the values of the sent packet browsing parameters and the packet routing parameters returned in correspondence with the transmitted packets, of a quality of service index.

Preferred, but not limiting, aspects of this method and equipment are:

a plurality of packets each having a different path parameter are transmitted.

the path parameters are successive integers between 1 and an integer greater than one. - the change of parameter of course includes the decrementation of the parameter of course of a unit.

- The return of a packet by a router or the target equipment is performed if the decrementation of the path parameter in it causes the value of said path parameter to zero.

the calculation comprises a step of determining a packet normalized packet return parameter subtracted between the effective value of the packet's travel parameter returned to the measurement robot and a selected returned packet's packet parameter origin value. among a group of possible original values as compatible with said actual value.

the calculation comprises the evaluation of an asymmetry criterion by comparison between the value of a transmitted packet travel parameter and the normalized value of a packet packet return parameter.

the calculation comprises the evaluation of a distance criterion based on the position, relative to a threshold value, of a travel parameter of an issued packet for which the target equipment has returned a packet.

the calculation comprises evaluating an attainability criterion by detecting the non-reception of packets returned by the target equipment in correspondence with transmitted packets.

the calculation comprises the evaluation of a loss criterion by detecting the point non-reception of packets returned by routers or by the target equipment in correspondence with transmitted packets. the calculation comprises the evaluation of a time-of-travel criterion by measuring time between the sending of packets and the reception of packets returned in correspondence with transmitted packets.

this measurement of time comprises at least one time measurement between the sending of at least a first packet and the reception of a packet returned by a router in correspondence with the first transmitted packet, and a measurement of time between the transmitting another packet and receiving a packet returned by the target equipment in correspondence with said other transmitted packet.

the calculation comprises the evaluation of a temporal stability criterion by determining the difference between a plurality of measured travel times and an average of said travel times.

the evaluation of the temporal stability criterion comprises the determination of several differences between measured travel time and mean travel time, for several transmitted packets having different travel parameters.

the quality of service index is calculated by combining at least two criteria values, such as a weighted sum.

the transmission of the data stream and the calculation take place according to one to three different protocols, which preferably comprise at least one transport layer protocol and / or at least one network layer protocol.

an overall quality index is determined by combining, preferably by an average, the quality of service indices obtained according to the two protocols at least. - Several packets having the same path parameter are transmitted, and the calculation takes into account a plurality of returned packets corresponding to these several transmitted packets.

the path parameters are constituted by standard time-of-life parameters ("time to live")

- The identification of a packet sent in a returned packet is contained in an emitted packet signature reproduced in the returned packet.

Brief description of the drawings

Other objects, features and advantages of the invention will appear better on reading the following detailed description of a preferred embodiment thereof, given by way of nonlimiting example and with reference to the appended drawings. in which, in addition to FIGS. 1a, 1b and 2 already described: FIG. 3 is a diagram of a reference IP network for the method according to the invention;

FIGS. 4a and 4b are diagrams of the interface infrastructure between the referencing IP network of FIG. 3 and other IP networks; and

FIGS. 5 to 7 give three examples of traces obtained with the method of the invention, these traces notably including criteria and combined index values and alarm information.

- Figure 8 is a diagram of an access infrastructure to ISPs (Internet Service Providers) on which the invention can be implemented.

Detailed description of a preferred embodiment 1. Methodology

We will now describe in detail an IP network quality of service measurement methodology on which the method according to the invention is based.

A QoS QoS measurement methodology for IP networks has three main steps where we will specify:

what is observed, namely the protocols, and whether these protocols are standardized (RFC type) or proprietary (especially in terms of video retransmission), the invention of course also applying to future protocols;

- the system from which they are observed (referential system); and

the way in which they are observed, in particular determined by granularity parameters of measurement, information of choice of measurement method, etc.).

Regarding the reference systems of observation, we can distinguish three levels of such referential systems, more and more precise, according to the objectives of apprehension of the quality of service:

- "Supplier" reference system: this is the simplest repository, since it is composed by the network of the service provider itself; this kind of repository detects about 70% of breakdowns; but it does not detect edge effects related to the design of the Internet networks themselves (interconnection problems, failures on primary or secondary name servers, Proxy problems, etc.). ).

- "Operators" referential system: this is a reference system composed of at least two different IP networks; observations can be made on the IP network of the provider itself, but they are correlated by observations in the same conditions, made on one or more different IP networks of the provider network; the network numbers AS are therefore necessarily different, with a connection to operators of first rank ("Tier-One" in English terminology) different; such a reference system can detect between 70 and 80% of failures; but the difficulties are on the one hand that it is necessary to be connected to enough of the main backbones (at least all the first ranks), and on the other hand that it is necessary to implement an intelligent, complex correlation and heavy, between the detected events; in general, this kind of repository system allows to determine that the backbone is failing, but more rarely to determine that it is the observed Internet service that is failing; - independent reference system: this is the ultimate evolution of reference systems, developed by specialized companies. This kind of repository system automatically selects the best route ad for joining a service from a provider and, in the event of a failure, selecting other routes, while respecting the provider's listing priorities. This type of reference system, depending on its network architecture, can detect 100% of failures, since it is independent of its own quality. This type of repository is preferred in the measurement of quality of service of Internet IP networks.

The IP network quality of service measurement method according to the invention is capable of performing quality measurements from any of these reference systems, in particular according to the desired accuracy.

Three levels of quality will now be described, making it possible to determine an overall quality of a service. For each of these three levels, a notation approach is used for a comparison of the minimum thresholds, payable, vital or superfluous, to be determined in case not case:

^' * level AVAILABILITY: it is a question here of measuring the availability of a service, with regard to the measurement methodology and the repository used; this overall availability is a function of a sampling frequency (Fq), which determines the periodicity of the measurements and which is chosen protocol by protocol and according to the requirements of the corresponding standard;

* INTEGRITY level: this is the corollary of availability: it is here to ensure that the requested service has correctly responded to the solicitation; for example, a connection that does not affect the correct IP address, a Web server responding to a message such as "too many users, try again later ...", etc. reveal a quality defect at the INTEGRITY level; integrity can be measured either in absolute value or in relative value with respect to availability; * PERFORMANCE level: it is a matter of determining the efficiency of a service, that is to say the quality of the service itself, which depends on the service studied; for example, in the case of an Internet access, typically a useful rate or a ratio between the useful bit rate and the theoretical bit rate is taken into account; the theoretical bit rate is measured outside the supplier's network, on a given minimum size (for example 20 KB, minimum size to avoid performance oscillation phenomena of a large IP network) through the HTTP protocol ("HyperText Transfer Protocol" in English terminology, or hypertext transfer protocol) or FTP ("File Transfer Protocol" in English terminology, or file transfer protocol) and on a site that does not have any limitation or intrinsic disturbance with regard to the test performed.

With regard to the periodicities used for the measurements at the different levels (which play on what may be called the temporal granularity of observation of the measurements), it is advantageous to be able to freely choose this granularity, mainly according to the protocol of the IP service measured and or a certain critical level of its use. At most, very spaced, for example every 4 hours, may be sufficient, but more typically, measurements are made with a periodicity of between about 1 hour for a non-critical service and about a few minutes in case of strong need for service availability, or in the case a critical service.

Finally, regarding the criteria to be used according to the IP service whose quality is to be measured, it should be noted that the different IP services do not have the same sensitivity to the requirements of availability, integrity or performance. For example, it is possible to determine the performance of an Internet access in absolute value (X Kb / s) or in relative value (for example X% of the nominal capacity of the telecommunication medium used, or Y% of the speed announced by the provider). According to another example, it is possible to determine the relay performance of an email server by the ability of said server to relay an email in less than X seconds.

2. General description

Based on this methodology, the method according to the invention aims to measure the quality of QoS service of IP networks used for the transport of the following main protocols or services:

- protocols and services standardized by RFC requests for comments, at present HTTP, HTTPS (secure HTTP), SMTP (for "Simple Mail Transfer Protocol" in English terminology, or simple mail transfer protocol) , POP3 (for "Post Office Protocol" in English terminology, or post office protocol), IMAP4 (for "Internet Mail Access Protocol" or mail access protocol

Internet), DNS (for Domain Name System), LDAP (for Lightweight Directory Access Protocol in English terminology, or Lightweight Directory Access Protocol), RADIUS ( network authentication service), FTP, etc ... - Proprietary protocols and services, mainly in audio / video, such as RealNetwork® or Microsoft® WMS.

- protocols and services to come or under development, such as IVPN protocols (for "Internet Virtual Private Network", or virtual private network

Internet) and voice services / 1P with the H323 protocol and its successors.

It should be noted that all these protocols intervene, within the architecture of IP networks, at the level of the "application" layer of the network. It will be recalled in this respect that the set of layers forming the IP network architecture is a stack of these layers, each layer N is built on the N-1 layer. The purpose of the N layer is to provide some services to the layer

N + 1 and following, sparing them the details of implementation of these services. In addition, the N layer of a machine A handles the conversation with the N layer of another machine B according to a protocol. However, no data is transferred directly from the N layer of A to the N layer of B, but each layer transmits the data and control to the next lower layer via an interface, up to the physical layer (level 1).

Above the "physical" layer is the "network" layer whose conversation protocol is the IP protocol and which manages how data IP packets are routed from A to B. When an abnormal event occurs at the network layer level, this event is reported using the above ICMP protocol. There are currently a dozen types of ICMP messages, each encapsulated in an IP packet. Such reports provide IP network test information. The "Ping" utility described previously uses some of these ICMP messages.

Above the "network" layer is the "transport" layer whose role is to accept data from the upper layer, to cut them possibly in smaller units and to ensure that all the pieces arrive correctly at B. Two protocols currently manage exchanges at the level of the "transport" layer, namely TCP and UDP.

Above, the "application" layer that accepts all the protocols and services listed above.

A characteristic of the method according to the invention is to be able to exploit protocols intervening at the "network" and "transport" layers, and for example ICMP, TCP and UDP, to measure the quality of service.

In general, the method according to the invention is implemented on a given IP device constituting a measurement robot so as to test a target, namely an IP device that one seeks to join in order to measure the state of the device. network between the measuring robot and this target). The measurement robot simulates a data flow according to one of the protocols or services of the "application" layer. Then, from this simulated data stream, the method performs the measurements using the above three ICMP, TCP and UDP protocols to generate, by operations which will be detailed below, two main categories of information.

i The first category is the list of devices traversed by IP data packets to reach the target. This list can be simplified by identifying each router traversed by its Internet address (IP address). A list of IP addresses is then obtained on which it is possible, preferably, to apply a known hashing algorithm, such as the MD5 algorithm (for "Message Digest" in English terminology, or message digest), which provides a unique result (in the form of 4 32-bit words in the current implementation) representative of the list of IP addresses of the different routers, and therefore the path followed by the data IP packets. Preferably, the method stores, at each measurement, a maximum set of 30 crossed equipment, for all ICMP, TCP and UDP protocols, the UDP and TCP ports being chosen freely by the customer in perfect adequacy with its uses.

> The second category reflects the state of communication between the measurement robot and the target, based on various criteria that will be detailed. The set of these criteria is computed individually in the form of a quality index, respectively W _TCP , WUD _P and W _ICMP , for each of the three protocols TCP, UDP, and ICMP; the use of three different indices makes it possible to take into account the fact that each protocol can be processed more or less rapidly by the different IP devices encountered. The criteria for measuring the state of the network are preferably: asymmetry (Asym criterion), the number of IP devices encountered (Hops criterion), the fact that the contact is established with the target (Unreach criterion), the rate loss of packets (Loss criterion), the transit time of the packets (Delay criterion), and finally the variance of this transit time (Stability criterion).

It is on the basis of these different criteria that the method according to the invention calculates the quality indices W _TC P, WUD _P and WI _CM P. and can, if appropriate, combine them themselves into a combined index W giving the state of communication between the measurement robot and the target.

The calculation of the combined index W (noted for example over 100) is preferably performed by averaging the three individual indices:

The individual indices are furthermore each determined as a weighted sum of the aforementioned criteria for the protocol under consideration, namely:

W | _C MP = AsymiccMP + HopsicMP + UnreachicMP + LossicMP + DelayicMP + StabilityicMP W _T cp = cp ⁺ _T Asym Hopsτcp Unreachτcp ⁺ + Loss ⁺ _T cp Delayτcp ⁺ Stabilityτcp

WuDP = AsyrτiuDP ⁺ HopsuDP + UnreachuDP + LossuDP + DelayuDP + StabilityuDP

it being observed that the weighting in question is obtained not here by weighting coefficients for each criterion, but by adjusting the rating range chosen for each criterion, preferably as follows:

It is observed here that the weighting makes it possible to give more importance to more influential criteria on the overall quality of the service, and in particular to the criteria of delay of transit of the packets (Delay) and variability of this time (Stability). Other weightings are of course possible depending on the needs. Preferably, a quality level is expressed by comparing the combined index W with given thresholds, determined, for example, empirically, an example being given below:

Optionally, it is also possible to express a Major dysfunction in the case of a lack of contact with the target under each of the three protocols, namely:

UnreachicMP = -5

Unreach-rcp = -5

UnreachuDP = -5

In such a case, the method may comprise a step of transmitting a major alarm status code.

We will return later on the precise calculation of the various criteria indicated above and composing the indices W.

3. Obtaining measures to evaluate the criteria

The technical implementation of the measurements made by the method according to the invention will now be described in greater detail.

In the first place, it is known that the header of an IP data packet includes a life time field (TTL parameter for "Time To Live"). In current implementations, this field contains an integer whose value is between 0 and 255 (eight-bit encoding), and that each traversed router decrements by one until the field value eventually reaches zero. Therefore, the IP packet is considered lost, and the router has decremented the last unit of time to zero to return a message to the sender to inform him that the IP packet has not arrived at destination due to lack of time (and more precisely the too many routers crossed). This message, sent according to the ICMP protocol, contains among others information on the router that sends it.

It is mainly on a new exploitation of the values of the TTL parameter in the transmitted packet and in the returned packet that the method according to the invention evaluates a certain number of the criteria involved in the quality of service indices. - ..

In a preferred embodiment, the method sends N IP packets (with N preferably close to 30) of data for each measurement performed, assigning the different packets TTL values ranging from N to 1.

Thus, the IP packet with TTL = I "dies" from the first router encountered, another IP packet with TTL = 2 from the second router encountered, and so until the target is finally reached, or the thirtieth router be reached. In this way, the method according to the invention retrieves the information of the different routers encountered, contained in the different messages returned by these routers.

A first piece of information consists of the IP addresses of the routers, enabling the method according to the invention to reconstruct the path traversed by the packets.

In detail, the ICMP signaling message returned by a given router to the machine that issued an IP packet when the TTL value of that packet is brought to zero by this router includes the IP header and the 64 first bits of the IP packet transmitted (see for more information RFC 792 - Internet Control Message Protocol).

This characteristic is exploited according to the invention to "sign" the IP packets transmitted by the measurement robot, that is to say by including a specific information (signature) in their first 64 bits. This signature makes it possible, when receiving an ICMP message to exceed the life time ("TTL

Exceeded "), to find to which IP packet emitted it corresponds. According to one aspect of the invention, this signature comprises among others the value of the TTL parameter originally assigned to this packet, for purposes explained below.

The method according to the invention also makes it possible to determine whether the forward and return paths of an IP packet are symmetrical or not in terms of the number of routers crossed. This feature is based primarily on three elements:

the information of the original TTL parameter of each IP packet transmitted by the method, contained in the signature of this packet; a first observation, according to which it is estimated that on the network, an IP packet never goes through more than 30 routers before reaching its goal, and finally

- and a second observation, according to which with the vast majority of existing routers, a packet sent by the router and containing an ICMP message type "TLL Exceeded" itself contains a TLL origin parameter whose value is, according to implementation, 255, 127, 63, 31.

Thus, when receiving a returned packet containing an ICMP message of the "TTL Exceeded" type, the method according to the invention performs the following operations: - search for the current value of the TTL parameter of the returned packet (for example equal to 113); - search for the value of the original TTL parameter of the returned packet among the various possible TTL values (here 255 or 127 or 63 or 31); more precisely, since, as we have seen above, a packet hardly ever passes through more than 30 routers before reaching its goal, it is deduced that this original value is necessarily that among the four possible values which is immediately greater than the current TTL value; in this example it will be 127;

calculating the difference between the original value and the current value of the TTL parameter, ie here 127 - 113 = 14, thus to determine the number of routers crossed by the returned packet;

recovering the value of the TTL parameter contained in the IP packet originally sent by the method, from the signature information returned in the data portion of the ICMP message of "TTL Exceeded"; this value is either - as described above - contained in a particular position of the first 64 bits of the transmitted packet, which are returned in the returned packet, or retrieved by the method using the signature, for example by consultation of a table ; suppose here that this value is 12; - comparison between the difference calculated as above (here 14) for the returned packet and the original value (here 12) for the transmitted packet.

If these values are equal, then the method could determine that the forward and backward paths, borrowing the same number of routers, were symmetrical in terms of the number of routers crossed; if, on the contrary, these values are different, as in the present example, then the paths have been determined to be asymmetrical. The evaluation of the Asym criterion will be detailed below using these values.

The method provides on this occasion the actual numbers of routers crossed on the outward and return, numbers that will be used as we will detail more far behind for other criteria involved in QoS quality of service determination.

Advantageously, in order to increase the representativity of the results obtained, the determination of the number of routers traveled in the round trip as described above is implemented, for each value of TTL and for each of the protocols (UDP, ICMP and TCP ) measured three times by sending three IP data packets. This allows :

- to guard against a possible loss of packets, and to obtain an indication of the loss rates, and

- Increase the wealth of information to determine the actual times out and back (always in terms of the number of routers crossed) put by the packets, and thus to obtain estimates of the variability of the speed of the network.

The paths followed by the packets, as we have seen, are processed by the hashing algorithm (typically the aforementioned MD5 algorithm) to give a unique MD5 key to each path. It should be noted that this compression is not reversible, so that it is not possible from the contents of the key MD5 to find the list of IP addresses submitted to the hash and forming the path.

As we will see, the result of this comparison influences the values of certain criteria involved in determining QoS quality of service. More precisely, the method is thus able to estimate the variability or the stability of the IP network on the path between the measurement robot and the target.

As we saw above, the "Unreach" criterion makes it possible to know if the target has answered or not. To evaluate this criterion, the method determines, by examining the information of the returned IP packets, whether among these packets, one or several originate (ie the source IP address of the IP header) the target device.

The presence of packets -comportant this source address makes it possible to determine that the target is in a "reachable" state ("reachable" in English terminology), while the absence of such packets makes it possible to determine an "unreachable" state ("Unreachable" in Anglo-Saxon terminology).

4. Evaluation of the criteria from the measurements

We will now describe a preferred calculation, based on the information recorded as described above, of the various criteria for defining the indices W.

asym

The calculation of the Asym asymmetry index is based on the determination of the number of routers traveled in the round trip, as determined from the TTL parameters as described above for different transmitted packets having different TTL parameters. These values are designated "TTLEΓΠIS" and "TTLeceived normalizes", being specified ÎCÎ qU ^β the TTLrecorded standard value is that obtained by difference with the value deduced from the original TTL parameter (255, 127, 63 or 31) in the packet returned.

For each of the values i of TTL (typically from 1 to 30) of the transmitted packets, the method calculates a difference value:

I I Ie Eeeee normalizes i "I-E: mιs ι

The Asym criterion is then calculated as follows J

It is understood that the value of the criterion Asym passes quickly to zero as soon as multiple asymmetries are encountered for the different values of the TTL parameter.

, Hops

Being reminded here that, during the measurement, IP packets are sent with TTL values ranging from 1 to 30, the Hops criterion of the index W aims to represent the fact that beyond 20 routers crossed, the The measurement robot is faced with an imprecise network environment in which everything is confounded, and events reported beyond this "distance" must no longer have any influence on the quality of service index W.

Preferentially, the Hops criterion is a linearly decreasing function obtained by the formula:

Hops = 20 - number of routers crossed

it being specified that the number of routers crossed is determined by examining the IP addresses of the packets received by the measurement robot and by determining the value of the TTL parameter of the transmitted packet for which the received packet includes an IP header designating the target.

In this way, any path involving the crossing of more than 20 routers brings the value of the Hops criterion to zero.

unreach Concerning the calculation of the accessibility criterion Unreach, it is done by determining if the machine sheltering the target is indeed in service, starting from the following principles:

- for the TCP protocol as for the UDP protocol, the assumption is that the measurement is made on ports that correspond to active services of the machine, and it must answer if it is running and if the service is active;

- for the ICMP protocol, the type of IP packet sent (ICMP "Echo request" message) is one of those mentioned to be supported by all IP devices installed on the Internet (see RFC 1122 , § 3.2.2.6), and it is therefore mandatory to reply with an ICMP message "Echo Reply", or echo reply.

Thus, the fact that the target machine responded reveals normal behavior, and it is the absence of an answer that indicates an abnormal situation.

To mark the importance of this unreachable character, the value of the Unreach criterion is preferentially negative in this case: f 0 if the target is reached Unreach = \

- 5 otherwise

loss

It will be recalled first of all that for each of the possible values of the TTL parameter, several packets (typically 3) are sent and all the responses received are counted. For the loss loss criterion calculation, the method examines whether, for each IP packet transmitted, a response is well received. If not, the method can only identify a loss in the broad sense because it is not possible to distinguish between the loss of the transmitted IP packet and the loss of the returned response. This nevertheless reveals a lack of reliability of the transport network. The value of the criterion Loss is preferentially calculated incrementally, as follows:

- An intermediate variable Lost is initialized to zero; - For each TTL parameter value between 1 and the TTL parameter value in the target response packet (denoted TTL _max ), Lost is incremented according to the number of IP packets transmitted, the number of received IP packets, and number of cases where the target has not been reached, as follows: Lost = Lost + (Nb IP Emis Packets - (Nb IP Packets Received + Nb

Unreach)) the Loss criterion is then calculated as follows: Loss = (10 ^* Nb Packets IP Emis ^* TTL _max -10 ^* Lost)

Delay

The value of the Delay criterion is calculated by timing the response times of the last N equipment to the most that responded (with typically N = 3), it being specified that, in the case where the measured equipment is very close in terms of the number of routers to cross, the method may be required to perform a number of measurements less than N. The method determines the average response time (tmr) of these devices, in milliseconds. Then, preferentially, this time tmr is converted into a 25 millisecond slice, rounded to the lower integer, and then converted into a Delay criterion value according to the following method:

- If tmr <0, Delay = 0.

- If tmr> 30, Delay = 30.

- Otherwise, Delay = tmr

Practically, this amounts to limiting times to a range of 0 to 750 milliseconds. Stability

Finally, concerning the calculation of the value of the criterion Stability, in the same way as for the calculation of the Delay criterion, an average time is determined, but this time on all the packets with different values i of the TTL parameter. The stability is then preferably calculated by the difference between 30 and the mean squared value of the DeltaPMj measurements (after conversion into 25 ms slices) collected for the different packets, according to the formula:

Stability = ^{30 ~}

int (Average Time - TimeTTL,) or DeltaPM. = *

25

The criteria evaluated as described above are then applied, for each of the protocols concerned (TCP, UDP and ICMP in the present example) to the computation of the indices W _TCP , WUDP and WI _C MP, then the combined index W is calculated, these various calculations having been described above.

-4?

5. Other features

The method according to the invention may also optionally, during each measurement it performs, detect whether a major or minor type event occurs.

It should be noted in this regard that with the development of digital telecommunications, the measurement of the quality of transmissions has long been carried out on technical parameters, mainly error rates, specific to these transmissions, and known in particular under the designations TE10 ^'3 (1 erroneous bit for 1000 bits transferred) and TE10 ^{' 6} (1 bit erroneous for 1 million bits transferred). Until the mid-1980s, these parameters were evaluated using bit counting over an undetermined period of time and out of normal operation (intrusive measurement). Two evolutions then appeared:

a non-intrusive measurement of errors for CRC (Cyclic Redundancy Check), particularly on the frames

CRC4 of 2 Mb / s; and

- the creation of a standard to judge the perceived quality of transmissions by a user and named G821.

This standard allowed, from factual elements called minor elements (TE10 ^"6 ) and major elements (TE10 ^'3 ), to associate the concept of time with these parameters and to create new standard indicators and in particular:

- SAE (second with error),

- SGE (second seriously erroneous), and - Unavailability (state decreed after 10 consecutive SGEs, and which ends after a return to normal measured several times consecutively).

These indicators made it possible to create the notions of qualification G821 which are currently very often the contractual referents of good functioning. It is also on the basis of these indicators, and always in connection with the time dimension, that we have seen the recent notions of SLA (Service Level Agreement or Service Level Agreement) of Internet operators.

The method according to the invention also preferably includes a classification of each dysfunction of Internet services by use and by gravity, classifying these malfunctions into events:

- minor (equivalent to what is the TE10 type error ^"6 )

- major (equivalent to what is the error of type TE10 ^"3 ).

The following steps are then implemented: during each measurement campaign related to obtaining a service quality index W, the method verifies, while storing all the incoming data, the presence of an event of the minor or major type, if the method detects an event of minor or major type, it proceeds to a second measurement by forcing if necessary the measuring time to its shortest period for a given protocol; for example, if the measurements in progress concern an HTTP protocol whose quality is evaluated every hour, the detection of a minor event during an evaluation results in a second evaluation not an hour later (predetermined period) but after the flow of a much shorter time (eg 5 minutes later, which is the shortest period used in practice for evaluation of an HTTP quality of service), if the second measurement does not confirm a state of the minor or major event type, the normal measurement cycle resumes, and only the "minor or major event" state is memorized in addition to the data used to indicate the quality, if the second measurement confirms a "minor or major event" state , the process triggers an alarm at an alarm level as shown in the following table:

The method according to the invention therefore determines a state of minor or major alarm that may result in the sending of an alert message (via e-mail, fax, SMS (for "Short Message Service" in English terminology). , either short message service), SNMP (for Simple Network Management Protocol), and the beginning of a period of minor or major unavailability of the measured service.

in the event of such a period of unavailability being triggered, the method according to the invention continues, for a nominal duration of unavailability (preferably chosen to be less than or equal to 24 hours), to measure the service according to the periodicity. shorter until the end of the unavailable period, then resumes a normal measurement cycle either at the end of the nominal unavailability time or when returning to the correct availability status

the end of the state of unavailability is determined by the method after two consecutive measurements free from minor or major events; this avoids all unstable repetitive states; this return to the normal state is accompanied by the sending of an end of alert message by the same channel as for the alert message.

It will be observed here that, thanks to the progress of steps as explained above, a minimum unavailability period is equal to the maximum of twice the minimum period between two successive measurements. If this duration and chosen short (typically 5 min and the problem at the source of the major or minor event disappears, the duration of the unavailability remains reasonable.

6. Technical implementation of the repository system

The measurements carried out over Internet IP networks by the method according to the invention are based on an independent reference system, as indicated previously. The network (backbone) constituting this reference system is based on broadband access to two or more Internet operators, thereby to realize an IP network infrastructure refer to similar to that illustrated in Figure 1 has previously described and in Figure 3. In this regard is observed in this figure 3 that the network designated by AS15436 comprises a series of equipment distributed throughout the world and interconnected by broadband links with multiple Internet operators, being able to communicate according to the different current application protocols.

As indicated, this architecture can be qualified as a reference system if it responds to two major constraints such as total availability and high-speed operation.

The first constraint is satisfied by a so-called "multihome" structure on each of the equipment, associated with a multi-router technical architecture as illustrated in FIG. 4a. In this figure, the different remote accesses to the machines RMA1, RMA2, RMA3, etc. (RMA for "Remote Measurement Agent" in English terminology or "remote measurement robot") are connected by Ethernet or Gigabit Ethernet 100-bit broadband links to at least two routers R1 and R2, themselves interconnected by a high speed link of the same type. The routers IP1 and IP2 designate the IP addresses of these two routers. FIG. 4a also mentions an IP3 address which is a virtual router address in accordance with the HSRP protocol ("Hot Standby Routing Protocol"). Each of the routers is itself connected to several ISP Internet operators (for "Internet Service Provider" in English terminology, ie ISP) by broadband access.

The constraint of broadband is related to the requirement that measurements made by the method of the invention via the reference system do not cause slowdown points IP networks involved in trade.

In concrete terms, the network forming the reference system has POPs ("Point Of Presence" in English terminology, or point of presence) in optimal physical sites for this type of realization, and in particular so-called IPOP rooms for "Internet Point of Presence" is point of presence Internet. A standard IPOP structure is illustrated in Figure 4b. Each of the routers R1 and R2 above is connected to at least one redundant router "Router Switch" via high speed access type Ethernet 100, Fast Ethernet 100 (FO Eth 100) or Gigabit Ethernet (GO Gigabit Eth). The redundant routers are connected to at least two sites (A ₁ B) of operators (Operator 1, Operator 2, ..., Operator N) via high-speed accesses (F01, F02).

Referring here to FIG. 8, it should be noted that such a redundant and secure high-speed structure defining the IP referent network makes it possible to perform measurements according to the method of the invention from different Internet access providers, noted FAI in Figure 8, for example national, with RMA measurement robots whose access is carried out according to various technologies such as dialup telephone network (PSTN) access, digital network access integrated with services (ISDN), digital subscriber line (DSL or ADSL) access, etc. This reflects the perceived quality of service through the end-user ISPs, while ensuring that the observed measures only relate to the service providers targeted by the quality measure.

7. Examples

FIGS. 5 to 7 of the drawings give three examples of traces obtained (in a debug mode) in response to a start instruction of the method according to the invention, these traces including the various criteria values obtained and the overall index, and as various other information including travel (including the message MD5 and the list of IP addresses of equipment traveled). Thus, FIG. 5 illustrates an example of a trace obtained on a target machine hosting a site www.rain.fr using the three TCP, UDP and ICMP protocols. The combined index W is here designated by "WITBEJNDICE" and equal to 87.

Figure 6 illustrates an example of a trace obtained on a target machine hosting a site www.special.com using the only UDP protocol in an "operator" mode. As a result, the target machine is not accessible according to the UDP protocol, and a major alarm is triggered (UDPJJNREACH = -5).

Finally, FIG. 7 illustrates an example of a trace obtained on a target machine hosting the same site www.special.com with the UDP and ICMP protocols in "operator" mode; the machine is accessible under ICMP but not under UDP; the overall index is 66 and a minor alarm is triggered.

Of course, we can bring to the invention many variations and modifications.

Claims

A method for measuring the quality of at least one Internet protocol service from an active device constituting a measurement robot connected to a first IP network serving as a reference to a target device constituting the host of said service and connected to a second IP network with which the first IP network is able to communicate, the measurement robot and the target equipment being able to communicate with each other in the form of packets directed by routers belonging to the IP networks and each having a modifiable path parameter, characterized in that it comprises the following steps:

(a) transmitting by the robot measurements of a data stream in accordance with a protocol used by the measured service, this data stream comprising packets each having an initial path parameter (TTL), and storing the initial path parameter in association with each issued packet,

(b) at each router encountered by a packet or at the target device, conditional modification of the path parameter,

(c) according to the value of the browse parameter, selective return by the router or the target equipment to the measurement robot of a packet containing an identification of the corresponding transmitted packet, and

(d) computation by the robot of measurements, from the values of the sent packet browsing parameters and the packet routing parameters returned in correspondence with the transmitted packets, of a quality of service index.

2. Method according to claim 1, characterized in that step (a) comprises transmitting a plurality of packets each having a different path parameter.

3. Method according to claim 2, characterized in that the path parameters are successive integers between 1 and an integer greater than one.

4. Method according to one of claims 1 to 3, characterized in that the path parameter change in step (b) comprises decrementing the path parameter of a unit.

5. Method according to claim 4, characterized in that the return of a packet in step (c) is performed if the decrementation of the path parameter in step (b) causes the value of said path parameter to zero. .

6. Method according to claim 5, characterized in that the calculation in step (d) comprises a step of determining a packet normalized packet return parameter subtracted between the effective value of the packet's return parameter returned to the measurement robot and a returned packet routing parameter origin value selected from a group of possible original values as compatible with said actual value.

7. Method according to claim 6, characterized in that the calculation in step (d) comprises the evaluation of an asymmetry criterion (Asym) by comparison between the value of an transmitted packet travel parameter and the normalized value of a packet traversal parameter returned.

8. Method according to one of claims 1 to 7, characterized in that the calculation in step (d) comprises the evaluation of a distance criterion (Hops) from the position, with respect to a Threshold value, of a path parameter of an emitted packet for which the target device has returned a packet.

9. Method according to one of claims 1 to 8, characterized in that the calculation in step (d) comprises the evaluation of a reachability criterion (Unreach) by detecting the non-reception of packets returned by the target equipment in correspondence with transmitted packets.

10. Method according to one of claims 1 to 9, characterized in that the calculation in step (d) comprises the evaluation of a loss criterion (Loss) by detecting the point non-reception of returned packets. by routers or by the target equipment in correspondence with transmitted packets.

11. Method according to one of claims 1 to 10, characterized in that the calculation in step (d) comprises the evaluation of a criterion of travel time

(Delay) by time measurement between the sending of packets and the reception of packets returned in correspondence with transmitted packets.

12. Method according to claim 11, characterized in that the time measurement comprises at least one time measurement between the transmission of at least a first packet and the reception of a packet returned by a router in correspondence with the first packet. transmitted packet, and a time measurement between the transmission of another packet and the reception of a packet returned by the target equipment in correspondence with said other transmitted packet.

13. Method according to one of claims 1 to 12, characterized in that the calculation in step (d) comprises the evaluation of a criterion of stability time (Stability) by determining the difference between a plurality of measured travel times and an average of said travel times.

14. Method according to claim 13, characterized in that the evaluation of the temporal stability criterion comprises the determination of several differences between measured travel time and mean travel time, for several transmitted packets having different path parameters.

15. Method according to one of claims 7 to 14, characterized in that step (d) comprises calculating the quality of service index by combining at least two criteria values.

16. The method of claim 15, characterized in that said combination is a weighted sum.

17. Method according to one of claims 1 to 16, characterized in that the steps (a) to (d) are implemented according to at least two different protocols.

18. The method of claim 17, characterized in that the two or more different protocols comprise at least one transport layer protocol and at least one network layer protocol.

19. Method according to one of claims 17 and 18, characterized in that it comprises a step of determining an overall quality index by combining the quality of service indices obtained according to the two protocols at least.

20. The method of claim 19, characterized in that said combination of indices is an average.

21. Method according to one of claims 1 to 20, characterized in that step (a) comprises the transmission of several packets having the same path parameter, and only the calculation in step (d) takes there is a plurality of returned packets corresponding to these several transmitted packets.

22. Method according to one of claims 1 to 21, characterized in that the path parameters are constituted by standard life time parameters.

23. Method according to one of claims 1 to 22, characterized in that the identification of a packet sent in a packet returned in step (c) is contained in a transmitted packet signature reproduced in the returned packet.

24. Equipment forming a measurement robot for measuring the quality of at least one Internet protocol service, characterized in that it is capable of being connected to a first IP network serving as a reference for performing measurements on a service. implemented on a target device connected to a second IP network with which the first IP network is able to communicate, in that the measurement robot and the target equipment are able to communicate with each other under form packets directed by routers belonging to IP networks, each packet having an editable path parameter, the path parameter of each packet being able to be modified conditionally at each router encountered or at the target device level , and depending on the value of the browse parameter, each router or the target equipment being able to send selectively to the measurement robot a packet containing a identification of the corresponding transmitted packet, and in that it comprises: (a) means for transmitting a data stream in accordance with a protocol used by the measured service, this data stream comprising packets each having a parameter initial course (TTL),

(b) means for storing the initial scan parameter in association with each transmitted packet, and (c) suitable computing means, based on the values of the transmitted packet travel parameters and the corresponding packet search parameters. with the transmitted packets, a quality of service index.

25. Equipment according to claim 24, characterized in that the transmitting means are able to emit a plurality of packets each having a different path parameter.

26. Equipment according to claim 25, characterized in that the path parameters are successive integers between 1 and an integer greater than one.

27. Equipment according to one of claims 24 to 26, wherein the path parameter of a packet is adapted to be modified at each router encountered or at the target equipment by decrementing and where the return of a packet by the router or target equipment is performed if the decrementation of the path parameter causes the value of said path parameter to zero, characterized in that the calculation means are able to determine a normalized packet parameter parameter returned by subtraction between the actual value of the packet travel parameter returned to the measurement robot and a returned packet route parameter origin value selected from a group of possible source values as compatible with said actual value.

28. Equipment according to claim 27, characterized in that the calculating means comprise a means for evaluating an asymmetry criterion (Asym) by comparing the value of an transmitted packet travel parameter with the normalized value. a returned packet path parameter.

29. Equipment according to one of claims 24 to 28, characterized in that the calculation means comprise a means for evaluating a distance criterion (Hops) from the position, with respect to a threshold value. , a path parameter of an emitted packet for which the target device has returned a packet.

30. Equipment according to one of claims 24 to 29, characterized in that the calculation means comprise a means of evaluation of a reachability criterion (Unreach) by detecting the non-reception of packets returned by the target equipment in correspondence with transmitted packets.

31. Equipment according to one of claims 24 to 30, characterized in that the calculation means comprise a means of evaluation of a loss criterion by detecting the non-specific reception of packets returned by routers. or by the target equipment in correspondence with transmitted packets.

32. Equipment according to one of claims 24 to 31, characterized in that the calculating means comprise a means for evaluating a criterion of travel time (Delay) by time measurement between the transmission of packets and the receiving packets returned in correspondence with transmitted packets. - ~

33. The method of claim 32, characterized in that the time measurement comprises at least one time measurement between the transmission of at least a first packet and the reception of a packet returned by a router in correspondence with the first transmitted packet, and a time measurement between the transmission of another packet and the reception of a packet returned by the target equipment in correspondence with said other transmitted packet.

34. Equipment according to one of claims 24 to 33, characterized in that the calculating means comprise a means for evaluating a criterion of temporal stability (Stability) by determining the difference between a plurality of travel times. measured and between an average of said travel times.

Equipment according to claim 34, characterized in that the evaluation of the temporal stability criterion comprises the determination of several differences between the measured travel time and the average travel time, for several transmitted packets having different travel parameters.

36. Equipment according to one of claims 28 to 35, characterized in that the calculation means comprise means for combining at least two criteria values to establish the quality of service index.

Equipment according to claim 15, characterized in that the combining means is a weighted summation means.

38. Equipment according to one of claims 24 to 37, characterized in that the transmitting means, the storage means and the calculation means are adapted to be implemented according to at least two different protocols.

39. Equipment according to claim 38, characterized in that the two or more different protocols comprise at least one transport layer protocol and at least one network layer protocol.

40. Equipment according to one of claims 38 and 39, characterized in that it further comprises means for determining an overall quality index by combining the quality of service indices obtained according to the two protocols at least.

41. Equipment according to claim 40, characterized in that said combination of indices is an average.

42. Equipment according to one of claims 24 to 41, characterized in that the transmitting means are capable of transmitting a succession of several packets having the same parameter of course, and that the calculation means are able to take into account. count a plurality of returned packets corresponding to these several transmitted packets.

43. Equipment according to one of claims 24 to 42, characterized in that the path parameters are constituted by standard life time parameters.

44. Equipment according to one of claims 24 to 43, characterized in that each packet transmitted by the transmitting means comprises an emitted packet signature containing the identification of the transmitted packet, said signature being able to be reproduced in a packet. returned corresponding to the level of a router or the target device.