WO2004104876A2 - Procede de calcul du plus court chemin et procede de routage et/ou de commutation - Google Patents

Procede de calcul du plus court chemin et procede de routage et/ou de commutation Download PDF

Info

Publication number
WO2004104876A2
WO2004104876A2 PCT/FR2004/001237 FR2004001237W WO2004104876A2 WO 2004104876 A2 WO2004104876 A2 WO 2004104876A2 FR 2004001237 W FR2004001237 W FR 2004001237W WO 2004104876 A2 WO2004104876 A2 WO 2004104876A2
Authority
WO
WIPO (PCT)
Prior art keywords
graph
path
vertices
paths
vertex
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/FR2004/001237
Other languages
English (en)
Other versions
WO2004104876A8 (fr
Inventor
Michel Koskas
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
KoDe
Original Assignee
KoDe
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by KoDe filed Critical KoDe
Priority to CA2525885A priority Critical patent/CA2525885C/fr
Publication of WO2004104876A2 publication Critical patent/WO2004104876A2/fr
Publication of WO2004104876A8 publication Critical patent/WO2004104876A8/fr
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
    • G06Q10/00—Administration; Management
    • G06Q10/04—Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem"
    • G06Q10/043—Optimisation of two dimensional placement, e.g. cutting of clothes or wood
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/12—Shortest path evaluation
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/48—Routing tree calculation

Definitions

  • the present invention relates to the field of graphs.
  • the present invention relates more particularly to a method for calculating the shortest path in a value graph.
  • This type of calculation has many fields of applications, such as for example telecommunications networks, road traffic ...
  • table D contains the shortest distance between the origin and this vertex. To reconstruct the shortest path which achieves this distance, it is then necessary to keep up to date another table C of vertices such that C (s) contains the vertex immediately preceding the vertex s in the shortest path.
  • IBM American patent application US 6,356,911
  • the relation information consists of the estimation function h (v) concerning a specific node v and a set T of destinations, where h (v) is a lower bound of the set of shortest path lengths s' extending from node v to each of the sets of destinations T.
  • the use of the estimation function can improve the speed of the Dijkstra process.
  • a router has a network topology table and a number of resource tables corresponding to areas of the network.
  • QoS Quality of Service
  • a traversable zone along the destination route and links in the zone which satisfy a value of User specified QoS are selected.
  • a calculation is performed on the selected links, this calculation conforming to the Dijkstra algorithm, to find the shortest path to the destination if the referenced entry indicates that the destination is in the local area of the router.
  • the calculation is continued until a shortest path tree is found for all the routers at the edge of the traversable zone or until the calculation ends if the tree is not found for all routers, and a route with an optimum QoS value is determined from the shortest path tree.
  • the present invention intends to remedy the drawbacks of the prior art by proposing a method for calculating the shortest path in a graph which has on average a complexity at 0 (l * ln (v)) where v is the number of vertices and 1 the average path length.
  • the present invention relates in its most general sense to a method of calculating the shortest paths in terms of cost and number of edges in a value graph comprising vertices and an adjacency matrix using means of calculation comprising memory resources and a processor characterized in that it includes the steps consisting in reducing to non-zero integer valuations; • possibly, reduce to the case of valuations all equal to 1 by creating intermediate vertices between two vertices connected by a valuation arc strictly greater than 1; perform a series of increments, an increment consisting of finding the set of vertices which can be arrived at starting from a given n-tuple of vertices; perform a series of decrementations, a decrementation consisting of finding the set of vertices to from which we can arrive at a n-tuple of given vertices; the increments and the decrementations which can succeed one another in any order; • transform the increment / decrement vectors into paths, these paths constituting the set El
  • the method further comprises the step consisting in carrying out successive refinements of the path called "trivial path" of length Nb, this path being the path which borrows Nb times the single edge of the graph Gl, the graph Gl, obtained from G0 by making successive thickenings, comprising only a single vertex and a single edge.
  • the method also comprises a precalculation step consisting in carrying out successive thickenings of the graph G0 until obtaining a graph Gl comprising only one vertex and one arc, a thick layer the graph G consisting in providing the graph G with an equivalence relation; consider that the equivalence classes are the vertices of the thickened graph G '; given two vertices SI and S2 of the thickened graph G ', there exists an edge between SI and S2 if, and only if, there exists if belonging to SI and s2 belonging to S2 such that if and s2 are connected by an edge in G ; the valuation of the edge S1-S2 of G 'being the minimum of the valuations of the edges sl-s2 of G, with si belonging to SI and s2 belonging to S2.
  • a precalculation step consisting in carrying out successive thickenings of the graph G0 until obtaining a graph Gl comprising only one vertex and one arc, a thick layer the graph G
  • the series of increments is carried out until the arrival vertex is contained in the assembly obtained from the departure vertex, which provides a path of length Nb; we intersect the sets obtained with the decrements of the arrival vertex.
  • the series of increments is carried out in a thickening of the initial graph until the vertex of arrival is contained in the set obtained from the vertex of departure, which provides a path of length Nb;
  • the method is applied to the routing of packets in a telecommunications network.
  • the method is applied to the routing of calls in a telecommunications network.
  • the method is applied to a navigation system.
  • the method is applied to a reservation system.
  • the method is applied to an automated translation aid system.
  • the invention also relates to a system for implementing the method comprising at least one processor and memory resources.
  • the invention relates to a switching and / or routing method.
  • the technical problem that arises is that of routing digital data, a call, a packet or a letter by optimizing one or more technical parameters: the transmission time, the distance traveled, the technical resources for transmission or routing, or else avoiding blockages during transmission.
  • the industrial process in the technical field of information systems implements the following technical means: at least computer computing means and physical routing and transmission equipment.
  • Said communication network comprises technical switching and / or routing equipment linked together by transmission means, for example optical fibers, radio transmission means, a pair of copper ...
  • This path can be associated with an allocation or not of bandwidth (network in connection type telephone mode, or network of datagrams in connected or not connected mode, TCP or UDP).
  • bandwidth network in connection type telephone mode, or network of datagrams in connected or not connected mode, TCP or UDP.
  • This modeling will make it possible to obtain the most short path, not necessarily in terms of distance, but as a function of predetermined parameters such as speed, etc., the parameters being modeled by a cost, which is in fact the cost of an edge.
  • the technical problem encountered is the risk of packet loss, an abnormally high and unacceptable transmission time for users, saturations or bottlenecks, speed limits of physical branches or nodes (technical equipment) of the network ...
  • the object of the invention is to optimize the distribution and the choice of physical resources in order to solve these technical problems encountered in industry, for example in the telecommunications industry.
  • the inventor has developed a technical solution in the form of an industrial and technical process and a technical system.
  • the invention can be defined as a switching and / or routing method in a communication network comprising a plurality of technical equipment linked together by transmission means, implemented on computer equipment. comprising computing means and in particular at least one processor and at least one memory, The method comprising a first step of establishing a value graph representing the communication network in which each vertex is a physical item of equipment and each edge is a physical link element between two items of equipment,
  • the switching and / or routing method in the network being characterized in that it consists in calculating the shortest path between a sending equipment A and a equipment B within the network by means of the following sub-steps:
  • a first preliminary sub-step consisting of reducing to non-zero integer valuations in the graph representative of the network and, possibly reducing to valuations all equal to 1 by inserting vertices between any pair of vertices connected by a valuation edge strictly greater than 1;
  • ⁇ o the shortest paths in terms of cost, that is to say the paths minimizing the overall cost of transit in the network, being constituted by the tuple C.
  • Figure 2 shows a graph Gl which is a thickening of the graph G0;
  • Figure 3 shows a graph G2 which is a thickening of the graph Gl
  • FIG. 5 represents a network in which the routing method according to the invention is implemented and
  • Figure 6 illustrates a Porphyry tree for the implementation of the method of the invention in the technical field of machine translation.
  • a nonvalue graph is a set (V, E) where V is a finite set, the set of vertices, and E is a set of couples of summits.
  • the elements of E are called the edges.
  • the first element of an edge is called the origin of the edge. Its second element is called the end.
  • k is the length of the path.
  • the problem of the path is to find the shortest path between two vertices of the graph, in this case the path, or the paths, using the fewest vertices possible.
  • a value graph is a pair (V, E) where V is a finite set, and E a set of triples (v, v ', x) where
  • the path length is in this case:
  • adjacency matrices that is to say matrices representing the set of costs of outgoing edges and incoming edges.
  • a coefficient of the matrix indicates whether there is an edge between two vertices: it is equal to 1 if there is an edge and 0 if there is none.
  • a coefficient of the matrix indicates the valuation of the corresponding edge.
  • dumb (x) (fl, f2, ..., fk) with for all integer i in [1, k], a vertex s' of g 'belongs to fi if, and only if, there exists a vertex s of ei such that s' is in the class of s.
  • InO ⁇ (0,0,0,0,1), (1,0,0,1,0), (0,1,0,0,0), (1,0,1,0,0) , (0,0,0,1,0) ⁇
  • the first thickening of this graph G0 is the graph Gl represented in FIG. 2.
  • This graph in turn thickens into the graph G2 represented in FIG. 3.
  • vertex 2 is in class d
  • vertex 5 is in class e.
  • vertex 2 is in class a
  • vertex 5 is in class c.
  • vertices 2 and 5 are in the class of f.
  • vertex 2 is in class d, 5 is in class e.
  • Finding paths of length 3 In G3, the trivial path is f->f->f-> f.
  • vertex 2 is in class d, 5 is in class e.
  • vertex 2 is in class a
  • 5 is in class c.
  • dumb (l, l) (1,1,1), which gives (1,1,0).
  • Certain fields require heavy calculations to find shorter paths in graphs such as telecommunications or road traffic.
  • the use of computer machines implementing the method according to the invention makes it possible to optimize the resources necessary to carry out these calculations.
  • Another technical field for which the process of the invention presents particularly effective results is the field of vehicle traffic. These vehicles may be road, air, sea, possibly space in the future.
  • the sections of track, which do not meet any other track, are the arcs of the graph; - the valuations (or costs) of the arcs are representative of parameters related to traffic or topology, for example distance, journey time, type of lane, etc.
  • the navigation or road traffic evaluation method comprises stages close to the stages of the routing process.
  • the methods of implementing the method of the invention are similar for air traffic or maritime traffic.
  • the logistic transport network is, similarly, modeled by a graph, in which the vertices are the equipment for routing packets or letters and in which the edges are the elements of connection between the various physical equipments.
  • each vertex corresponds to a meaning S (i, n), which is the i th meaning of the nth significant word.
  • d i, n, j, n + 1
  • a fictitious start vertex connected with a zero cost to each of the meanings of the first word
  • a fictitious end vertex connected with a zero cost to each of the meanings of the last word.
  • the known automatic translation methods require oversized and very expensive calculation means.
  • the technical problem is to carry out such processing with reasonable computer resources while retaining the quality in terms of translation results, by a solution consisting in at least reducing, and preferably eliminating, irrelevant processing, and therefore in using the best available IT resources.
  • a flow problem is characterized by at least one source and at least one sink. It will be noted that it is always possible to reduce to the case of a single source and a single well in such a problem.
  • an arc is a transport medium with a maximum capacity (or flow) and therefore a vertex is a point of competition for incoming or outgoing arcs.
  • the flow problem relates to a problem of managing a flow of at least one physical resource, for example but not necessarily water, electricity, natural gas.

Landscapes

  • Engineering & Computer Science (AREA)
  • Business, Economics & Management (AREA)
  • Human Resources & Organizations (AREA)
  • Strategic Management (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Economics (AREA)
  • Marketing (AREA)
  • Physics & Mathematics (AREA)
  • Entrepreneurship & Innovation (AREA)
  • Development Economics (AREA)
  • Operations Research (AREA)
  • Quality & Reliability (AREA)
  • Tourism & Hospitality (AREA)
  • Game Theory and Decision Science (AREA)
  • General Business, Economics & Management (AREA)
  • General Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)
  • Complex Calculations (AREA)
  • Devices For Executing Special Programs (AREA)

Abstract

La présente invention se rapporte à un procédé de calcul des plus courts chemins en termes de coût et de nombre d'arêtes dans un graphe valué comportant des sommets et une matrice d'adjacence en utilisant des moyens de calcul comprenant des ressources mémoire et un processeur. Selon un autre aspect, l'invention concerne un procédé de commutation et/ou de routage dans un réseau de communication comportant une pluralité d'équipements techniques reliés entre eux par des moyens de transmission, mis en oeuvre sur un équipement informatique comportant des moyens de calcul et notamment au moins un processeur et au moins une mémoire. L'invention se rapporte également à un système de commutation et/ou de routage ou à un système de calcul pour la mise en oeuvre du procédé.

Description

PROCEDE DE CALCUL DU PLUS COURT CHEMIN ET PROCEDE DE ROUTAGE
ET /OU DE COMMUTATION
La présente invention se rapporte au domaine des graphes .
La présente invention se rapporte plus particulièrement à un procédé de calcul du plus court chemin dans un graphe value. Ce type de calcul possède de très nombreux domaines d'applications, comme par exemple les réseaux de télécommunications, le trafic routier...
L'art antérieur connaît déjà l'algorithme de Dijkstra. Cet algorithme tient à jour un ensemble X de sommets dont les distances les plus courtes à l'origine sont déjà connues. Au départ, X contient uniquement le sommet correspondant à l'origine. A chaque étape, on ajoute à X l'un des sommets restants dont la distance à l'origine est la plus courte possible. Si tous les arcs ont des étiquettes positives ou nulles, il est toujours possible de trouver un chemin minimal depuis l'origine vers un sommet s ne passant que par des sommets déjà présents dans X. Appelons raccourci un tel chemin. A chaque étape de l'algorithme, on utilise un tableau D contenant la longueur du meilleur raccourci pour se rendre à chaque sommet. Dès qu'un sommet est atteint, le tableau D contient la distance la plus courte entre l'origine et ce sommet. Pour reconstruire le plus court chemin qui réalise cette distance, il convient alors de tenir à jour un autre tableau C de sommets tel que C(s) contienne le sommet précédant immédiatement le sommet s dans le plus court chemin . L'art antérieur connaît déjà, par la demande de brevet américain US 6 356 911 (IBM) un système de recherche du plus court chemin. Un procédé et un système efficaces sont présentés. Ils permettent de rechercher les plus courts chemins entre une source et des destinations multiples, et entre des sources multiples et des destinations multiples. La vitesse du procédé classique de Dijkstra, qui est le procédé de calcul basique, est amélioré en utilisant des informations sur les relations entre un nœud et un ensemble de destinations dans un graphe. Les informations de relation sont constituées par la fonction d'estimation h(v) concernant un nœud spécifique v et un ensemble T de destinations, où h(v) est une borne inférieure de l'ensemble des longueurs de chemins les plus courts s 'étendant du nœud v à chacun des ensembles de destinations T. L'utilisation de la fonction d'estimation peut améliorer la vitesse du procédé de Dijkstra.
L'art antérieur connaît également, par la demande de brevet américain US 2002/0107711 (Sun Microsystems) une recherche du court chemin utilisant des tuiles et une propagation de coût linéaire par pièce. Un procédé pour trouver les plus courts chemins est décrit. Ce procédé utilise un modèle de coût linéaire par pièce pour guider la recherche à travers le graphe de tuiles compact et pour être sûr qu'un plus court chemin peut toujours être trouvé par calcul d'une manière efficace. La fonction de propagation de segment de tuile à segment de tuile est utilisée pour chercher un emplacement cible depuis un emplacement source à travers une région, et le plus court chemin est trouvé en effectuant un retour en arrière en utilisant les fonctions de coût calculées pendant la recherche. La convolution linéaire minimale est utilisée pour faciliter la propagation de la fonction de coût. L'art antérieur connaît également, par la demande de brevet américain US 2001/0032272 (NEC) un routage de plus court chemin basé sur la QoS (Qualité de Service) pour un réseau de communication hiérarchique. Un routeur a une table de topologie de réseau et un nombre de tables de ressource correspondant à des zones du réseau. En réponse à une requête d'un utilisateur, une des entrées de la table de topologie et l'une des tables de ressources sont référencées, une zone traversable le long de la route de destination et des liens de la zone qui satisfont une valeur de QoS spécifiée par l'utilisateur sont sélectionnés. Un calcul est effectué sur les liens sélectionnés, ce calcul étant conforme à l'algorithme de Dijkstra, pour trouver un chemin le plus court vers la destination si l'entrée référencée indique que la destination est dans la zone locale du routeur. Si l'entrée ne l'indique pas, le calcul est poursuivi jusqu'à ce qu'un arbre de chemin le plus court soit trouvé pour tous les routeurs en bordure de la zone traversable ou jusqu'à ce que le calcul se termine si l'arbre n'est pas trouvé pour tous les routeurs, et une route ayant une valeur de QoS optimum est déterminée à partir de l'arbre de plus court chemin.
Les procédés connus de l'art antérieur possèdent dans le meilleur des cas une complexité en 0(J5*ln(V)) où V est le nombre de sommets et E est le nombre d'arêtes.
La présente invention entend remédier aux inconvénients de l'art antérieur en proposant un procédé de calcul du plus court chemin dans un graphe qui possède en moyenne une complexité en 0( l *ln ( v) ) où v est le nombre de sommets et 1 la longueur moyenne du chemin.
A cet effet, la présente invention concerne dans son acception la plus générale un procédé de calcul des plus courts chemins en termes de coût et de nombre d'arêtes dans un graphe value comportant des sommets et une matrice d'adjacence en utilisant des moyens de calcul comprenant des ressources mémoires et un processeur caractérisé en ce qu'il comporte les étapes consistant à se ramener à des valuations entières non nulles ; • éventuellement, se ramener au cas de valuations toutes égales à 1 en créant des sommets intermédiaires entre deux sommets reliés par un arc de valuation strictement supérieure à 1 ; effectuer une série d'incrémentations, une incrémentation consistant à trouver l'ensemble des sommets auxquels on peut arriver en partant d'un n-uplet de sommets donné ; effectuer une série de décrémentations, une décrémentation consistant à trouver l'ensemble des sommets à partir desquels on peut arriver à un n-uplet de sommets donné ; les incrémentations et les décrémentations pouvant se succéder dans n'importe quel ordre ; • transformer les vecteurs d'incrément/décrément en chemins, ces chemins constituant l'ensemble El des chemins les plus courts en termes de nombre d'arêtes ou empruntant un nombre donné d'arêtes Na ;
• sélectionner le n-uplet de chemins C de moindre coût parmi l'ensemble de chemins El ;
• effectuer Nb = Na + 1 ;
• effectuer tant que (Nb <= v(C)) les étapes suivantes de manière itérative :
{ • examiner parmi les chemins de nombre d'arêtes
Na + 1 ceux, s'ils existent, qui ont un coût strictement inférieur à v(C) et sélectionner parmi ceux-ci ceux C de coût minimal (s'il n'existe pas de tel chemin, alors C'= C) • C = C et Nb = Nb + 1
}
• les chemins les plus courts en termes de coût étant constitués par le n-uplet C .
De préférence , le procédé comporte en outre l ' étape consistant à effectuer des raffinements successifs du chemin dit « chemin trivial » de longueur Nb , ce chemin étant le chemin qui emprunte Nb fois l ' unique arête du graphe Gl , le graphe Gl , obtenu à partir de G0 en ef fectuant des épaississe ents successifs , ne comportant qu ' un seul sommet et une seule arête .
Avantageusement, le procédé comporte en outre une étape de pré-calcul consistant à réaliser des épaississements successifs du graphe G0 jusqu ' à l 'obtention d'un graphe Gl ne comportant plus qu ' un seul sommet et un seul arc , un épais sis sèment du graphe G consistant à munir le graphe G d ' une relation d' équivalence ; considérer que les classes d'équivalence sont les sommets du graphe épaissi G' ; étant donné deux sommets SI et S2 du graphe épaissi G', il existe une arête entre SI et S2 si, et seulement si, il existe si appartenant à SI et s2 appartenant à S2 tels que si et s2 sont reliés par une arête dans G ; la valuation de l'arête S1-S2 de G'étant le minimum des valuations des arêtes sl-s2 de G, avec si appartenant à SI et s2 appartenant à S2.
Selon une variante particulière, la série d'incrémentations s'effectue jusqu'à ce que le sommet d'arrivée soit contenu dans l'ensemble obtenu à partir du sommet de départ, ce qui fournit un chemin de longueur Nb ; on intersecte les ensembles obtenus avec les décréments du sommet d'arrivée.
Selon une variante particulière, • la série d'incrémentations s'effectue dans un épaississement du graphe initial jusqu'à ce que le sommet d'arrivée soit contenu dans l'ensemble obtenu à partir du sommet de départ, ce qui fournit un chemin de longueur Nb ;
• on intersecte les ensembles obtenus avec les décréments du sommet d'arrivée dans le même épaississement du graphe ;
• on raffine alors le chemin obtenu jusqu'à obtenir les plus courts chemins empruntant Nb arêtes dans le graphe initial, s'il en existe ; • s'il n'en n'existe pas, on pose Nb = Nb +1, et on recherche les plus courts chemins empruntant Nb arcs dans un épaississement du graphe initial, qu'on tente de raffiner dans le graphe initial comme à l'étape précédente. On recommence la présente étape tant qu'un plus court chemin n'a pas été trouvé. Selon un mode de mise en œuvre particulier, le procédé est appliqué au routage de paquets dans un réseau de télécommunications .
Selon une variante, le procédé est appliqué au routage d'appels dans un réseau de télécommunications.
Selon une autre variante, le procédé est appliqué à un système de navigation.
Selon un mode de mise en œuvre particulier, le procédé est appliqué à un système de réservation. Enfin, selon une dernière variante, le procédé est appliqué à un système automatisé d'aide à la traduction.
L'invention se rapporte également à un système pour la mise en œuvre du procédé comprenant au moins un processeur et des ressources mémoire.
Selon une forme de mise en œuvre particulièrement préférée, l'invention concerne un procédé de commutation et/ou de routage. Le problème technique qui se pose est celui qui consiste à router une donnée numérique, un appel, un paquet ou une lettre en optimisant un ou plusieurs paramètres techniques : le temps de transmission, la distance parcourue, les ressources techniques de transmission ou de routage, ou bien encore évitant les blocages lors de la transmission.
Le procédé industriel dans le domaine technique des systèmes d'informations selon l'invention met en œuvre les moyens techniques suivants : au moins des moyens informatiques de calcul et des équipements physiques de routage et de transmission.
Afin d'illustrer l'effet technique induit par l'invention, nous présentons ici le procédé de routage et/ou de commutation dans le cadre d'un réseau de communication, de préférence numérique.
Ledit réseau de communication comprend des équipements techniques de commutation et/ou routage reliés entre eux par des moyens de transmission, par exemple des fibres optiques, des moyens de transmission radio, une paire de cuivre ...
Pour transmettre une information sous forme par exemple de paquet IP d'un poste émetteur A à un poste récepteur B, il est nécessaire de définir un chemin. Ce chemin peut être associé à une allocation ou non de bande-passante (réseau en mode connexion type téléphone, ou réseau de datagrammes en mode connecté ou non connecté, TCP ou UDP). On odélise couramment le réseau au moyen d'un graphe value, chacun des sommets correspondant à un équipement : serveur, routeur, central téléphonique, CAA (Commutateur d'Auto-Acheminement) ou autre ... Cette modélisation permettra d'obtenir le plus court chemin, non nécessairement en termes de distance, mais en fonction de paramètres pré-déterminés comme la rapidité, etc., les paramètres étant modélisées par un coût, qui est en fait le coût d'une arête.
Le problème technique rencontré est le risque de perte de paquets, un temps de transmission anormalement élevé et inacceptable pour les utilisateurs, des saturations ou engorgements, des limitations de débits de branches physiques ou bien de nœuds (équipements techniques) du réseau...
Le but de l'invention est d'optimiser la répartition et le choix des ressources physiques afin de résoudre ces problèmes techniques rencontrés dans l'industrie, par exemple dans l'industrie des télécommunications.
Afin de résoudre les problèmes techniques décrits, l'inventeur a élaboré une solution technique sous la forme d'un procédé industriel et technique et d'un système technique.
Ainsi, selon un aspect, l'invention peut être définie comme un procédé de commutation et/ou de routage dans un réseau de communication comportant une pluralité d'équipements techniques reliés entre eux par des moyens de transmission, mis en œuvre sur un équipement informatique comportant des moyens de calcul et notamment au moins un processeur et au moins une mémoire, • le procédé comportant une première étape d'établissement d'un graphe value représentant le réseau de communication dans lequel chaque sommet est un équipement physique et chaque arête est un élément de liaison physique entre deux équipements,
• le procédé de commutation et/ou de routage dans le réseau étant caractérisé en ce qu'il consiste à calculer le plus court chemin entre un équipement émetteur A et un équipement B au sein du réseau au moyen des sous-étapes suivantes :
- une première sous-étape préalable consistant à se ramener à des valuations entières non nulles dans le graphe représentatif du réseau et, éventuellement se ramener à des valuations toutes égales à 1 en intercalant des sommets entre tout couple de sommets reliés par une arête de valuation strictement supérieure à 1 ;
- des sous-étapes supplémentaires consistant à o effectuer une série d'incrémentations, une incrémentation consistant à trouver l'ensemble des sommets (équipements techniques) auxquels on peut arriver en partant d'un n-uplet de sommets donné ; o effectuer une série de décrémentations, une décrémentation consistant à trouver l'ensemble des sommets à partir desquels on peut arriver à un n-uplet de sommets donné ; o les incrémentations et les décrémentations pouvant se succéder dans n'importe quel ordre ; o transformer les vecteurs d'incrément/décrément en chemins, ces chemins constituant l'ensemble El des chemins les plus courts en termes de nombre d'arêtes ou empruntant un nombre donné d'arêtes Na ; o sélectionner le n-uplet de chemins C de moindre coût parmi l'ensemble de chemins El ; o effectuer Nb = Na + 1 ; o effectuer tant que (Nb <= v(C)) les étapes suivantes de manière itérative : { y
examiner parmi les chemins de nombre d'arêtes Na + 1 ceux s'ils existent qui ont un coût strictement inférieur à v(C) et sélectionner parmi ceux-ci ceux C ' de coût minimal (s'il n'existe pas de tel chemin, alors C'= C) • C = C et Nb = Nb + 1
} o les chemins les plus courts en termes de coût, c'est-à-dire les chemins minimisant le coût global de transit dans le réseau, étant constitués par le n-uplet C.
On comprendra mieux l'invention à l'aide de la description, faite ci-après à titre purement explicatif, d'un mode de réalisation de l'invention, en référence aux figures annexées :
• la figure 1 représente un graphe GO ;
• la figure 2 représente un graphe Gl qui est un épaississement du graphe G0 ;
• la figure 3 représente un graphe G2 qui est un épaississement du graphe Gl ;
• la figure 4 représente un graphe G3 qui est un épaississement du graphe G2 ; • la figure 5 représente un réseau dans lequel le procédé de routage selon l'invention est mis en œuvre et
• la figure 6 illustre un arbre de Porphyre pour la mise en œuvre du procédé de l'invention dans le domaine technique de la traduction automatique.
Nous allons, dans un premier temps, donner une nouvelle description du graphe. Ensuite, dans un second temps, nous expliquerons comment cette description peut être utilisée et nous présenterons le procédé selon l'invention, dans différents modes de réalisation.
Un graphe non value est un ensemble ( V, E) où V est un ensemble fini, l'ensemble des sommets, et E est un ensemble de couples de sommets. Les éléments de E sont appelés les arêtes . Le premier élément d'une arête est appelé 1 ' origine de l'arête. Son second élément est appelé extrémité.
Si (vl,v2)GE≈>(v2,vl)GE
alors on dit que le graphe est non dirigé et E peut être considéré comme un ensemble de paires de sommets.
Un chemin entre deux sommets vl et v2 est une suite u0, ... uk d'éléments de V tels que u0 = vlf uk = v2 et pour tout i entier dans [0, k-1],
(ut,ul+1) EE
Dans ce cas, on dit que k est la longueur du chemin.
Le problème du chemin est de trouver le plus court chemin entre deux sommets du graphe, c'est-à-dire dans ce cas le chemin, ou les chemins, utilisant le moins de sommets possible.
Un graphe value est un couple (V, E) où V est un ensemble fini, et E un ensemble de triplets (v, v' , x) où
(vp ) GVetx ≡R v et v' sont les arêtes et x est le coût ou la longueur de l'arête.
Un chemin entre deux sommets vl et v2 est une séquence u0, ... uk d'éléments de V tels que u0 = vl f uk = v2 et pour tout i entier dans [0, k-1],
3x, E R, (u^^x,) EE.
La longueur du chemin est dans ce cas :
Figure imgf000011_0001
Le problème est également de trouver le chemin le plus court entre deux sommets . Dans le domaine des graphes, il est courant d'utiliser des matrices d'adjacence, c'est-à-dire des matrices représentant l'ensemble des coûts des arêtes sortantes et des arêtes entrantes. Dans un mode particulier, un coefficient de la matrice indique s'il existe une arête entre deux sommets : il est égal à 1 s ' il existe une arête et 0 s'il n'en existe pas. Dans un autre mode, un coefficient de la matrice indique la valuation de l'arête correspondante. Dans la suite, nous utiliserons des matrices d'adjacence ne comportant que des 0 et des 1.
Lorsque x est un ensemble de chemins d'un épaississement g du graphe initial GO, on notera dans la suite « dumb(x) » le raffinement trivial de x dans un raffinement du graphe auquel il appartient. Si x=(el, e2, ..., ek) avec el, e2, ... ek des ensembles de sommets de g, et si g' est un raffinement de g, dumb(x) = (fl, f2, ..., fk) avec pour tout entier i dans [1, k], un sommet s' de g' appartient à fi si, et seulement si, il existe un sommet s de ei tel que s' est dans la classe de s.
La description qui suit concerne un exemple de graphe.
Il est entendu que le procédé conforme à l'invention est décrit ici à titre d'exemple, de façon à ce qu'un homme du métier puisse le reproduire.
Considérons le graphe G0 de la figure 1 : Les arcs sortants et entrants sont :
OutO = {(0,1,0,1,0), (0,0,1,0,0), (0,0,0,1,0), (0,1,0,0,1), (1,0,0,0,0)}
InO = {(0,0,0,0,1), (1,0,0,1,0), (0,1,0,0,0), (1,0,1,0,0), (0,0,0,1,0)}
Le premier épaississement de ce graphe G0 est le graphe Gl représenté sur la figure 2.
Les arcs entrants et sortants de ce graphe Gl sont : Outl = {(1,1,0), (1,1,1), (1,0,0)}
Inl = {(1,1,1), (1,1,0), (0,1,0)}
Ce graphe s'épaissit à son tour en le graphe G2 représenté sur la figure 3.
Les arcs entrants et sortants de ce graphe sont :
Out2 = {(1,1), (1,0)} et In2 = {(1,1), (1, 0)}.
Enfin ce graphe s'épaissit en le graphe G3 représenté sur la figure 4.
Les arcs entrants et sortants de ce graphe sont :
Out3 = {(1)} et In3 = {(1)}.
Recherchons par exemple un chemin entre les sommets 2 et 5 dans le graphe G0.
Recherche des chemins de longueur 1 :
Dans G3 : le chemin trivial de longueur 1 est
f->f .
Dans G2 : le sommet 2 est dans la classe d, le sommet 5 est dans la classe e.
Il existe un arc entre d et e. Donc dans G2, on a le chemin d->e
Dans gl : le sommet 2 est dans la classe a, le sommet 5 est dans la classe c.
Il n'existe pas d'arc entre a et c. Donc il n'existe pas de chemin de longueur 1 entre 2 et J_.
Recherche des chemins de longueur 2 :
Dans g3 : les sommets 2 et 5 sont dans la classe de f.
Le chemin trivial de longueur 2 est
f->f->f.
Dans G2 : le sommet 2 est dans la classe d, 5 est dans la classe e.
2 - Incréments
d+1 = (1,1).
On intersecte d + 1 avec dumb(f) = (1,1).
Donc le premier arc donne (1,0)->(1,1)
Puis on fait (1,1) + 1 intersecte avec dumb(f) et arrivée, ce qui donne
(1,1) + 1 intersecte avec (1,1) intersecté avec (0,1), soit (0,1).
Donc le deuxième arc donne ( 1 , 1 ) ->( 0 , 1 ) .
En résumé, les incréments donnent le chemin
(1,0) -> (1,1) -> (0,1)
2 - Décréments
(0,1) - 1 {= (1,0)} intersecté avec (1,1) = (1,0). Donc le dernier arc donne (1,0) -> (0,1)
(1,0) - 1 = (1,1) intersecté avec (1,0) donne (1,0).
Donc le premier arc donne (1,0) -> (1,0)
On a donc un ensemble de chemins de longueur 2 dans G2 qui est :
(1,0) -> (1,0) -> (0,1).
Dans gl :
2 est dans la classe de a, 5 est dans la classe de c.
1 - Incréments
a + 1 = (1,1,0). Donc a+1 intersecté avec dumb(l,0) = (1,1,0) donne (1,1,0).
Le premier arc donne donc (1,0,0) -> (1,1,0).
(1,1,0) + 1 = (1,1,1). Donc (1,1,0) + 1 intersecté avec dumb(1,0) = (1,1,0) donne (1,1,0).
Ce dernier vecteur intersecté avec (0,0,1) donne (0,0,0).
Le deuxième arc donne donc (1,1,0) -> (0,0,0)
Donc 1 ' incrément donne le chemin
(1,0,0) -> (1,1,0) -> (0,0,0)
On en conclut qu'il n'y a pas de chemin de longueur 2 dans gl, et a fortiori dans G0.
Recherche des chemins de longueur 3 : Dans G3, le chemin trivial est f->f->f->f.
Dans G2 : le sommet 2 est dans la classe d, 5 est dans la classe e.
1 - Incréments
d+1 = (1,1).
On intersecte d + 1 avec dumb(f) = (1,1).
Donc le premier arc donne ( 1, 0 )->( 1 , 1 )
Puis on fait (1,1) + 1 intersecté avec dumb(f), ce qui donne
(1,1) + 1 intersecté avec (1,1), soit (1,1).
Donc le deuxième arc donne ( 1 , 1 )->( 1 , 1 )
Puis on fait (1,1) + 1 intersecté avec dumb(f) et arrivée, ce qui donne
(1,1) + 1 intersecté avec (1,1) intersecté avec (0,1), soit (0,1).
Donc le troisième arc donne (1,1)->(0,1).
En résumé, les incréments donnent le chemin
(1,0) -> (1,1) _>(l,l)-> (0,1)
2 - Décréments
(0,1) - 1 {= (1,0)} intersecté avec (1,1) = (1,0).
Donc le dernier arc donne (1,0) -> (0,1) (1,0) - 1 = (1,1) intersecté avec (1,1) donne (1,1).
Donc le deuxième arc donne (1,1) -> (1,0)
(1,1)-1 intersecté avec (1,0) donne (1,0).
Donc le premier arc donne ( 1, 0 ) ->( 1 , 1)
On a donc un ensemble de chemins de longueur 3 dans g2 qui est :
(1,0) -> (1,1)->(1,0) -> (0,1).
Dans Gl : le sommet 2 est dans la classe a, 5 est dans la classe c.
1 - Incréments
a+1 = (1,1, 0).
On intersecte a + 1 avec dumb(l,l) = (1,1, 1), ce qui donne (1,1,0).
Donc le premier arc donne (1,0, 0)->(l,l, 0)
Puis on fait (1,1, 0) + 1 intersecté avec dumb(l,0) = (1,1,0), ce qui donne
(1,1, 0) + l == (1,1,1) intersecté avec (1,1, 0), soit (1,1, 0).
Donc le deuxième arc donne (1,1, 0)->(l,l, 0)
Puis on fait (1,1, 0) + 1 = (1,1,1) intersecté avec dumb(0,1) = (0,1,1) et arrivée, ce qui donne (1,1, 1) intersecté avec (0, 1,1) intersecté avec (0,0, 1), soit (0,0, 1).
Donc le troisième arc donne (1,1, 0)->(0,0, 1).
En résumé, les incréments donnent le chemin
(1,0, 0) -> (1,1, 0) ->(1,1, 0)-> (0,0, 1)
2 - Décréments
(0, 0,1) - 1 {= (0,1,0)} intersecté avec (1,1, 0) = (0, 1,0).
Donc le dernier arc donne (0, 1,0) -> (0,0,1)
(0, 1,0) - 1 = (1,1, 0) intersecté avec (1,1, 0) donne (1,1, 0).
Donc le deuxième arc donne (1,1, 0) -> (0, 1,0)
(1,1, 0)-l intersecté avec (1,0, 0) donne (1,0, 0).
Donc le premier arc donne (1 , 0, 0) ->(l , l , 0)
On a donc un ensemble de chemins de longueur 3 dans gl qui est :
(1,0, 0) -> (1,1, 0)->(0, 1,0) -> (0, 0, 1).
Dans G0 :
1 - Incréments
(0,1,0,0,0)+1 = (0,0,1, 0,0).
On intersecte (0,1,0,0,0) + 1 avec dumb(1,1, 0) = (1,1, 1 , 1 , 0 ) , ce qui donne (0, 0,1,0, 0). Donc le premier arc donne (0, 1, 0, 0, 0)->(0, 0, 1, 0, 0).
Puis on fait (0, 0, 1, 0, 0) + 1 intersecté avec dumb(1, 1,0) = (1,1,1, 1, 0), ce qui donne
(0, 0, 1, 0, 0) + 1 = (0, 0, 0, 1,0) intersecté avec (1,1, 1, 1, 0), soit (0, 0, 0, 1, 0).
Donc le deuxième arc donne (0, 0,1, 0, 0)->(0, 0, 0, 1, 0)
Puis on fait (0, 0, 0, 1, 0) + 1 = (1, 0, 1, 0, 0) intersecté avec dumb(0, 0, 1) = (0,0, 0, 0, 1) et arrivée, ce qui donne :
(1,0, 1, 0, 0) intersecté avec (0, 0, 0, 0, 1) intersecté avec (0,0, 0, 01), soit (0,0, 0, 0, 1).
Donc le troisième arc donne (0, 0, 0, 1, 0)->(0,0, 0, 0, 1).
En résumé, les incréments donnent le chemin
(0, 1,0, 0, 0) -> (0, 0, 1, 0, 0) ->(0, 0, 0, 1, 0)-> (0,0, 0, 0, 1)
2 - Décréments
(0, 0,0, 0, 1) - 1 {= (0, 0, 0, 1, 0)} intersecté avec (0, 0, 0,1, 0) = (0, 0, 0, 1,0).
Donc le dernier arc donne (0, 0, 0, 1,0) -> (0,0, 0, 0, 1)
(0, 0, 0, 1,0) - 1 = (1, 0, 1, 0, 0) intersecté avec ( 0, 0, 1 , 0, 0 ) donne (0, 0, 1, 0, 0). Donc le deuxième arc donne (0, 0,1, 0, 0) -> (0, 0, 0, 1,0)
(0, 0,1, 0, 0)-l intersecté avec ( 0 , 1,0, 0 , 0 ) donne (0, 1, 0, 0, 0).
Donc le premier arc donne (0, 1,0, 0, 0)->(0, 0,1, 0, 0)
On a donc un ensemble de chemins de longueur 3 dans G0 qui est :
(0, 1,0, 0, 0) -> (0, 0,1, 0, 0)->(0, 0, 0, 1,0) -> (0, 0, 0, 0,1).
Finalement, on trouve le chemin 2->3->4->5 et c'est le chemin le plus court.
Le calcul du chemin le plus court étant réalisé en utilisant des moyens de calcul comprenant des ressources mémoires et un processeur, il devient évident pour l'homme du métier, à la lecture des différentes étapes constituant l'exemple précédent, que le procédé selon l'invention possède un effet technique évident : l'optimisation des ressources mémoires et de l'utilisation du processeur. Cette optimisation se traduit, pour de longs calculs, par des gains de temps et des gains financiers très significatifs. Elle peut également se traduire par des gains de place intéressants pour les calculs sur des systèmes embarqués.
Certains domaines exigent de lourds calculs pour la recherche de plus courts chemins dans des graphes comme par exemple les télécommunications ou le trafic routier. L'utilisation de machines informatiques implementant le procédé selon l'invention permet d'optimiser les ressources nécessaires pour réaliser ces calculs. Un autre domaine technique pour lequel le procédé de l ' invention présente des résultats particulièrement efficaces est le domaine du trafic de véhicules . Ces véhicules peuvent être routiers , aériens , maritimes , éventuellement spatiaux dans 1 ' avenir .
Dans le cas du trafic routier, on considère que le réseau routier est modélisé sous la forme d'un graphe value dans lequel : - les carrefours (ou tout croisements de routes/ autoroutes / rues / voies de trafic routier ...) sont les sommets du graphe ;
- les tronçons de voie, qui ne rencontrent aucune autre voie, sont les arcs du graphe ; - les valuations (ou coûts) des arcs sont représentatifs de paramètres liés au trafic ou à la topologie, par exemple la distance, le temps de parcours, le type de la voie...
Ensuite, le procédé de navigation ou d'évaluation du trafic routier comprend des étapes voisines des étapes du processus de routage.
Les modes de mise en œuvre du procédé de 1 ' invention sont similaires pour le trafic aérien ou le trafic maritime.
Un autre domaine technique dans lequel l'invention trouve une excellente application est celui de la logistique. Dans ce domaine industriel, on ne route plus des appels ou des datagrammes, mais des colis, paquets physiques ou bien encore des lettres. Le réseau de transport logistique est, de la même manière, modélisé par un graphe, dans lequel les sommets sont les équipements de routage de paquets ou de lettres et dans lequel les arêtes sont les éléments de liaison entre les différents équipements physiques.
La traduction automatique est un autre domaine dans lequel le procédé de l'invention rencontrera probablement un grand succès, dans la mesure où il conduit à des optimisations d'importance encore inconnue à ce jour.
Pour l'analyse sémantique, les linguistes utilisent un arbre dit arbre de Porphyre. Pour une phrase (ou bien pour tout un texte), chaque sommet correspond à un sens S(i,n), qui est le ième sens du nième mot significatif. On a une distance sémantique d(i,n, j, n+1) entre S(i,n) et S(j, n+1). On choisit un sommet fictif de départ, relié avec un coût nul à chacun des sens du premier mot et un sommet fictif d'arrivée, relié avec un coût nul à chacun des sens du dernier mot. Ainsi, on cherchera à minimiser l'entropie sémantique de la phrase du texte en minimisant le coût du parcours entre le point de départ et le point d'arrivée.
Les procédés de traduction automatique connus nécessitent des moyens de calculs surdimensionnés et très coûteux . Le problème technique est de réaliser de tels traitements avec des moyens informatiques raisonnables tout en conservant la qualité en termes de résultats de traduction, par une solution consistant à au moins réduire, et de préférence éliminer, les traitements non pertinents , et donc d ' utiliser au mieux les ressources informatiques disponibles .
Les problèmes de flots sont également résolus de façon efficace au moyen de l'invention.
Un problème de flot est caractérisé par au moins une source et au moins un puits. On remarquera qu'il est toujours possible de se ramener au cas d'une source unique et d'un puits unique dans un tel problème.
On rattache un flot à un graphe de la façon suivante : un arc est un médium de transport ayant une capacité (ou débit) maximum et donc un sommet est un point de concours d'arcs entrants ou sortants.
Les lois classiques de la physique s'appliquent dans les problèmes de flots (lois des mailles et lois des nœuds). Afin de résoudre ce type de problème, on utilise en général l'algorithme de Ford-Fulkerson, qui consiste à associer le problème de flot à un problème de routage dans un graphe (value). Il consiste à cherche les chemins les plus courts en employant le minimum d'arêtes. On effectue des itérations jusqu'à ce que le graphe ne soit plus connexe entre la source et le puits, éventuellement en autorisant un parcours « à rebours » d'arcs. Lorsqu'on a trouvé un chemin, on enlève à tous les arcs qui le constituent sa capacité minimale.
En pratique, le problème de flot se rapporte à un problème de gestion d'un flux d'au moins une ressource physique, par exemple mais non nécessairement d'eau, d'électricité, de gaz naturel.
L'invention est décrite dans ce qui précède à titre d'exemple. Il est entendu que l'homme du métier est à même de réaliser différentes variantes de l'invention sans pour autant sortir du cadre du brevet.

Claims

REVENDICATIONS
1. Procédé de commutation et/ou de routage dans un réseau de communication comportant une pluralité d'équipements techniques reliés entre eux par des moyens de transmission, mis en œuvre sur un équipement informatique comportant des moyens de calcul et notamment au moins un processeur et au moins une mémoire,
• le procédé comportant une première étape d'établissement d'un graphe value représentant le réseau de communication dans lequel chaque sommet est un équipement physique et chaque arête est un élément de liaison physique entre deux équipements,
• le procédé de commutation et/ou de routage dans le réseau étant caractérisé en ce qu'il consiste à calculer le plus court chemin entre un équipement émetteur A et un équipement B au sein du réseau au moyen des sous-étapes suivantes :
- une première sous étape préalable consistant à se ramener à des valuations entières non nulles dans le graphe représentatif du réseau et, éventuellement se ramener à des valuations toutes égales à 1, en intercalant des sommets entre tout couple de sommets reliés par une arête de valuation strictement supérieure à 1 ; - des sous-étapes supplémentaires consistant à o effectuer une série d'incrémentations, une incrémentation consistant à trouver l'ensemble des sommets (équipements techniques) auxquels on peut arriver en partant d'un n-uplet de sommets donné ; o effectuer une série de décrémentations, une décrémentation consistant à trouver l'ensemble des sommets à partir desquels on peut arriver à un n-uplet de sommets donné ; o les incrémentations et les décrémentations pouvant se succéder dans n'importe quel ordre ; o transformer les vecteurs d'incrément/décrément en chemins, ces chemins constituant l'ensemble El des chemins les plus courts en termes de nombre d'arêtes ou empruntant un nombre donné d'arêtes Na ; o sélectionner le n-uplet de chemins C de moindre coût parmi l'ensemble de chemins El ; o effectuer Nb = Na + 1 ; o effectuer tant que (Nb <= v(C)) les étapes suivantes de manière itérative :
{ examiner parmi les chemins de nombre d'arêtes Na + 1 ceux s'ils existent qui ont un coût strictement inférieur à v(C) et sélectionner parmi ceux-ci ceux C ' de coût minimal (s'il n'existe pas de tel chemin, alors C'= C) • C = C et Nb = Nb + 1
} o les chemins les plus courts en termes de coût, c'est-à—dire les chemins minimisant le coût global de transit dans le réseau, étant constitués par le n-uplet C.
2 - Procédé de commutation et/ou de routage dans un réseau de communication comportant une pluralité d'équipements techniques reliés entre eux par des moyens de transmission, mis en œuvre sur un équipement informatique comportant des moyens de calcul et notamment au moins un processeur et au moins une mémoire, selon la revendication 1, caractérisé en ce qu'il comporte en outre l'étape consistant à effectuer des raffinements successifs du chemin dit « chemin trivial » de longueur Nb, ce chemin étant le chemin qui emprunte Nb fois l'unique arête du graphe Gl, le graphe Gl, obtenu à partir de GO en effectuant des épaississements successifs, ne comportant qu'un seul sommet et une seule arête.
3 - Procédé de commutation et/ou de routage dans un réseau de communication comportant une pluralité d' équipements techniques reliés entre eux par des moyens de transmission, mis en œuvre sur un équipement informatique comportant des moyens de calcul et notamment au moins un processeur et au moins une mémoire selon la revendication 1 ou 2, caractérisé en ce que la série d'incrémentations s'effectue dans un épaississement du graphe initial jusqu'à ce que le sommet d'arrivée soit contenu dans l'ensemble obtenu à partir du sommet de départ, ce qui fournit un chemin de longueur Nb ; et en ce qu ' il comporte en outre les étapes suivantes : * on intersecte les ensembles obtenus avec les décréments du sommet d'arrivée dans le même épaississement du graphe ; on raffine alors le chemin obtenu jusqu'à obtenir les plus courts chemins empruntant Nb arêtes dans le graphe initial, s'il en existe ; s'il n'en n'existe pas, on pose Nb = Nb +1, et on recherche les plus courts chemins empruntant Nb arcs dans un épaississement du graphe initial, qu'on tente de raffiner dans le graphe initial comme à l'étape précédente. On recommence la présente étape tant qu'un plus court chemin n'a pas été trouvé.
4 - Procédé de commutation et/ou de routage dans un réseau de communication comportant une pluralité d'équipements techniques reliés entre eux par des moyens de transmission, mis en œuvre sur un équipement informatique comportant des moyens de calcul et notamment au moins un processeur et au moins une mémoire selon la revendication 1, 2 ou 3, caractérisé en ce qu'il comporte en outre une étape de pré-calcul consistant à réaliser des épaississements successifs du graphe G0 jusqu'à l'obtention d'un graphe Gl ne comportant plus qu'un seul sommet et un seul arc, un épaississement du graphe G consistant à munir le graphe G d'une relation d'équivalence ; • considérer que les classes d'équivalence sont les sommets du graphe épaissi G' ; étant donné deux sommets SI et S2 du graphe épaissi G', il existe une arête entre SI et S2 si, et seulement si, il existe si appartenant à SI et s2 appartenant à S2 tels que si et s2 sont reliés par une arête dans G ; la valuation de l ' arête S1-S2 de G' étant le minimum des valuations des arêtes sl-s2 de G, avec si appartenant à SI et s 2 appartenant à S2.
5 - Procédé de commutation et/ou de routage dans un réseau de communication comportant une pluralité d' équipements techniques reliés entre eux par des moyens de transmission, mis en œuvre sur un équipement informatique comportant des moyens de calcul et notamment au moins un processeur et au moins une mémoire selon la revendication 1, 2 ou 3, caractérisé en ce que la série d' incrémentations s 'effectue jusqu ' à ce que le sommet d ' arrivée soit contenu dans l ' ensemble obtenu à partir du sommet de départ , ce qui fournit un chemin de longueur Nb ; on intersecte les ensembles obtenus avec les décréments du sommet d' arrivée .
6 - Système de commutation et/ou de routage pour la mise en œuvre du procédé selon l'une quelconque des revendications précédentes comprenant au moins un réseau de communication comportant une pluralité d'équipements techniques reliés entre eux par des moyens de transmission, mis en œuvre sur un équipement informatique comportant des moyens de calcul et notamment au moins un processeur et au moins une mémoire.
PCT/FR2004/001237 2003-05-19 2004-05-19 Procede de calcul du plus court chemin et procede de routage et/ou de commutation Ceased WO2004104876A2 (fr)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CA2525885A CA2525885C (fr) 2003-05-19 2004-05-19 Procede de calcul du plus court chemin et procede de routage et/ou de commutation

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
FR0305973A FR2855287A1 (fr) 2003-05-19 2003-05-19 Procede de calcul du plus court chemin dans un graphe
FR03/05973 2003-05-19

Publications (2)

Publication Number Publication Date
WO2004104876A2 true WO2004104876A2 (fr) 2004-12-02
WO2004104876A8 WO2004104876A8 (fr) 2005-08-25

Family

ID=33396564

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/FR2004/001237 Ceased WO2004104876A2 (fr) 2003-05-19 2004-05-19 Procede de calcul du plus court chemin et procede de routage et/ou de commutation

Country Status (4)

Country Link
US (1) US7406047B2 (fr)
CA (1) CA2525885C (fr)
FR (1) FR2855287A1 (fr)
WO (1) WO2004104876A2 (fr)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN101141384B (zh) * 2006-09-08 2010-06-09 华为技术有限公司 最短路径桥中对称树的生成方法

Families Citing this family (10)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20060047421A1 (en) * 2004-08-25 2006-03-02 Microsoft Corporation Computing point-to-point shortest paths from external memory
US20070156330A1 (en) * 2005-12-29 2007-07-05 Microsoft Corporation Point-to-point shortest path algorithm
CN102158388B (zh) * 2010-02-12 2014-12-24 国际商业机器公司 极值路由确定引擎和方法
US8494771B2 (en) 2011-09-07 2013-07-23 Microsoft Corporation Journey planning in public transportation networks
US8861506B2 (en) 2011-12-27 2014-10-14 Apple Inc. Shortest path determination for large graphs
CN103079250A (zh) * 2012-12-16 2013-05-01 北京泛联至诚科技有限公司 一种基于车流密度的物联网单播数据传输方法
CN103473606B (zh) * 2013-08-27 2016-05-18 浙江工业大学 基于gis的最大最短路径长度的公交网络整体换乘性能优化方法
FR3059459B1 (fr) * 2016-11-25 2019-03-15 Electricite De France Optimisation de maintenance de centrale nucleaire
US20230115664A1 (en) * 2021-10-08 2023-04-13 Seagate Technology Llc Resource management for disaggregated architectures
CN116720638B (zh) * 2023-04-13 2024-03-26 广东工业大学 一种基于改进进化算法的逆最短路权重调整方法及系统

Family Cites Families (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH11184837A (ja) 1997-12-11 1999-07-09 Internatl Business Mach Corp <Ibm> 最短経路探索システム
US6477515B1 (en) * 1999-08-11 2002-11-05 The United States Of America As Represented By The Secretary Of The Navy Efficient computation of least cost paths with hard constraints
US6665852B2 (en) * 2000-12-01 2003-12-16 Sun Microsystems, Inc. Piecewise linear cost propagation for path searching
US7139992B2 (en) 2000-12-01 2006-11-21 Sun Microsystems, Inc. Short path search using tiles and piecewise linear cost propagation

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
Sans recherche *

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN101141384B (zh) * 2006-09-08 2010-06-09 华为技术有限公司 最短路径桥中对称树的生成方法

Also Published As

Publication number Publication date
CA2525885A1 (fr) 2004-12-02
US7406047B2 (en) 2008-07-29
FR2855287A1 (fr) 2004-11-26
CA2525885C (fr) 2016-02-16
US20040236811A1 (en) 2004-11-25
WO2004104876A8 (fr) 2005-08-25

Similar Documents

Publication Publication Date Title
Roughgarden Selfish routing
CA2525885C (fr) Procede de calcul du plus court chemin et procede de routage et/ou de commutation
US7039641B2 (en) Modular packet classification
CN102592179B (zh) 用于查找最佳费用的最优化系统和方法
US20080145050A1 (en) System and method for improving the efficiency of routers on the Internet and/or cellular networks and/or other networks and alleviating bottlenecks and overloads on the network
FR2836314A1 (fr) Methode dynamique et distribuee de protection locale d&#39;un chemin a commutation d&#39;etiquettes
EP1858214B1 (fr) Procédé de routage adaptif par déflexion avec apprentissage par renforcement
Becker A tight 4/3 approximation for capacitated vehicle routing in trees
US20030128987A1 (en) System and method for improving the efficiency of routers on the internet and/or cellular networks an/or other networks and alleviating bottlenecks and overloads on the network
EP1479183B1 (fr) Procede pour determiner une route spectrale pour une connexion donnee dans un reseau de telecommunication optique
EP2572478B1 (fr) Procede d&#39;optimisation de routage dans un cluster comprenant des liens de communication statiques et programme d&#39;ordinateur mettant en oeuvre ce procede
EP2033380A1 (fr) Procede de routage de liens virtuels dans un reseau a commutation de trames a determinisme garanti
US20040081153A1 (en) System and method for improving the efficiency of routers on the internet and/or cellular networks and/or other networks and alleviating bottlenecks and overloads on the network
FR2870961A3 (fr) Procede et systeme de navigation
FR2870963A3 (fr) Procede et systeme de traduction automatique
FR2870959A3 (fr) Procede et systeme de routage pour la logistique
FR2871008A3 (fr) Procede de routage et/ou de commutation
FR2870960A3 (fr) Systeme et procede de calcul du plus court chemin et systeme et procede de resolution numerique d&#39;un probleme technique de flot
EP1588279A1 (fr) Procede permettant de produire des solutions a un probleme concret d optimisation multicritere
Vijay et al. A memory-efficient adaptive optimal binary search tree architecture for IPV6 lookup address
Ashvinkumar et al. Local routing in sparse and lightweight geometric graphs
EP1328084B1 (fr) Détermination de la cause d&#39;une dégradation de la qualité d&#39;un service en fonction de l&#39;évolution d&#39;un ensemble de services
Kesswani Performance Evaluation of Shortest Path Routing Algorithms in Real Road Networks
Olver The price of anarchy and a priority-based model of routing
EP2254288B1 (fr) Procédé de prévention et d&#39;évitement de boucles en inter-domaine

Legal Events

Date Code Title Description
AK Designated states

Kind code of ref document: A2

Designated state(s): AE AG AL AM AT AU AZ BA BB BG BR BW BY BZ CA CH CN CO CR CU CZ DE DK DM DZ EC EE EG ES FI GB GD GE GH GM HR HU ID IL IN IS JP KE KG KP KR KZ LC LK LR LS LT LU LV MA MD MG MK MN MW MX MZ NA NI NO NZ OM PG PH PL PT RO RU SC SD SE SG SK SL SY TJ TM TN TR TT TZ UA UG US UZ VC VN YU ZA ZM ZW

AL Designated countries for regional patents

Kind code of ref document: A2

Designated state(s): BW GH GM KE LS MW MZ NA SD SL SZ TZ UG ZM ZW AM AZ BY KG KZ MD RU TJ TM AT BE BG CH CY CZ DE DK EE ES FI FR GB GR HU IE IT LU MC NL PL PT RO SE SI SK TR BF BJ CF CG CI CM GA GN GQ GW ML MR NE SN TD TG

121 Ep: the epo has been informed by wipo that ep was designated in this application
D17 Declaration under article 17(2)a
WWE Wipo information: entry into national phase

Ref document number: 2525885

Country of ref document: CA

122 Ep: pct application non-entry in european phase