WO2006021631A1 - Procede de controle de routage dans un reseau de paquets supporte par un reseau de transport - Google Patents

Procede de controle de routage dans un reseau de paquets supporte par un reseau de transport Download PDF

Info

Publication number
WO2006021631A1
WO2006021631A1 PCT/FR2005/001513 FR2005001513W WO2006021631A1 WO 2006021631 A1 WO2006021631 A1 WO 2006021631A1 FR 2005001513 W FR2005001513 W FR 2005001513W WO 2006021631 A1 WO2006021631 A1 WO 2006021631A1
Authority
WO
WIPO (PCT)
Prior art keywords
link
routers
metric
network
virtual
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/FR2005/001513
Other languages
English (en)
Inventor
Jean-Louis Le Roux
Géraldine Calvignac
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.)
Orange SA
Original Assignee
France Telecom SA
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 France Telecom SA filed Critical France Telecom SA
Priority to AT05778640T priority Critical patent/ATE520225T1/de
Priority to US11/658,771 priority patent/US7978687B2/en
Priority to EP05778640A priority patent/EP1771981B1/fr
Publication of WO2006021631A1 publication Critical patent/WO2006021631A1/fr
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • 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
    • H04L45/123—Evaluation of link metrics
    • 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
    • H04L45/124—Shortest path evaluation using a combination of metrics

Definitions

  • the present invention relates to a method of controlling the routing in a packet network supported by a transport network allowing the dynamic creation / deletion of packet transport links of said packet network. It also relates to a routing control system, a dynamic routing control unit and an adjacency management unit for implementing said routing control method.
  • a network of packets is called a network that transfers information-bearing packets and the routing functions of these packets.
  • the packets referred to in this description are, for example, IP (Internet Protocol) packets.
  • IP Internet Protocol
  • the present invention is particularly applicable to a packet network which has the structure, according to the so-called overlay model, an example of which is shown in FIG. 1. It comprises routers, for example four in number A, B, C and D, connected to each other by a core transport network 10, for example an optical transport network, comprising optical switches OXCl to OXC4 capable of to pass the packets processed by each router A, B, C, D.
  • a UNI client-network interface provides logical control between a router and the core network.
  • the present invention applies to the case of an architecture network according to the so-called "overlay" model where the domain of the packets (for example the IP domain) is relatively independent of the domain of the core transport network (for example the domain optical).
  • the core network provides connections that are viewed from the packet network as point-to-point.
  • the packet network acts vis-à-vis the core network as a client.
  • the packet network routing protocol and the core network routing protocol are independent.
  • the interface between a router and a switch of the core network 10 is a logical control interface which provides for the transmission of signaling messages between a peripheral router and the optical switch of the optical network to which it is connected for the creation, the destruction, the modification, a request for status of optical circuits of the optical network.
  • Optical-User Network Interface such as those described by the OIF (Optical Internetworking Forum) standardization bodies. and IETF (Internet Engineering Task Force).
  • the signaling messages are based on the resource reservation protocol with RSVP-TE (Resource Reservation Protocol - Traffic Engineering) traffic engineering.
  • a packet-switched network generally implements a routing protocol whose essential function is to determine for packets that must pass from one router to another, the least expensive path ( we also say the shortest path) knowing that each link from one router to another to which it is connected is assigned a cost, also called metric.
  • the routing protocol in question here is a link state routing protocol, for example of the internal type, such as a protocol of the IGP link state type (Interior Gateway Protocol: intra-domain protocol), such as in particular the Open Shortest Path First (OSPF) protocol.
  • OSPF Open Shortest Path First
  • the latter is the subject of the request for comments 2328 (RFC 2328). It could also be the ISIS protocol
  • the operating principle of a protocol of the IGP link state type is as follows. At each IP network adjacency that the protocol itself can determine by a particular protocol called Hello protocol, is associated a metric whose value is representative of a characteristic of the adjacency: an arbitrary value assigned by the network administrator (for example a value of 1 representing a router crossed, the delay transmission on the link considered, the reliability of the link, etc.). The metric can also be called the cost of the link. The protocol then calculates the route to all routers in the network using a "shortest path first" algorithm SPF, the path length (or the cost of a path) being determined by summing metrics links forming this path.
  • SPF shortest path first algorithm
  • the present invention is therefore only interested in the packet network which, in an exemplary embodiment to be described, is an IP network, with a link state routing protocol, for example of the IGP link state type.
  • An "adjacency" is a link that links two routers that have become neighbors to exchange routing information, that is, they are not only neighbors because they each have an interface to the same network but also that they have synchronized their respective topology tables.
  • the control capabilities offered by a link-state routing protocol are not adequate for performing traffic engineering (TE).
  • TE traffic engineering
  • SPF Shortest Path First
  • a virtual topology consists of virtual circuits that appear as physical links for the routing protocol. In this way, the control of traffic and resources can be considered at the level of the virtual topology.
  • VNT Virtual Network Topology
  • IGP protocol link state routing
  • the algorithm for calculating the new topology adds new optical paths in order to limit the congestions that may appear, given the traffic and on the other hand, eliminates an optical path that is underutilized.
  • Two traffic thresholds (high and low) are respectively defined for congested optical paths and underutilized optical paths. If the request for traffic on an optical path is greater than the high threshold, a new optical path is created so that traffic on the congested optical path is re-routed. The end nodes of the new optical path are selected from all the adjacencies of the end nodes of the congested link. On the other hand, if the request for traffic on an optical path is lower than the low threshold, this optical path is suppressed provided that this does not introduce congestion.
  • IP Internet Protocol
  • GMPLS Generalized MPLS
  • This document therefore describes the dynamic updating of the topology of a network according to the traffic matrix.
  • the mechanism described in the document mentioned above nevertheless has the drawback of not proposing mechanisms capable of controlling the impact of a creation / destruction of links on the routing protocol. Indeed, it has been possible to highlight such an impact which creates instabilities of the topology and too frequent changes. It can even result in congestion or underutilization of certain links.
  • the purpose of the present invention is therefore to propose a method for controlling the topology of a packet network supported by a transport network that allows the dynamic creation / deletion of packet transport links of said packet network that does not have the same content.
  • the present invention thus relates to a method of controlling the routing in a packet network supported by a transport network authorizing the dynamic creation / deletion of packet transport links of said packet network, said method including: a routing step which, according to a metric assigned to each link of the packet network, determines the shortest path between said head end router and the tail end router of the same connection,
  • said link can take three states:
  • a virtual connection state in which a virtual metric is assigned to said link between said head end router and said tail end router; the same communication, said state being taken when said link is likely to be the subject of a direct connection and the traffic between said two routers does not fulfill said creation / destruction conditions, said virtual metric then being subject to information to other routers of an undifferentiated metric, - an actual connection state in which a metric, called real metric, is normally assigned to said link between said head end router and said tail end router of the same communication, said state being taken when the traffic between said two routers fulfills said creation / destruction conditions.
  • the value of the virtual metric is chosen relative to that of the actual metric either equal or lower.
  • the value of the virtual metric is chosen relative to that of the sum of the real metrics of the indirect paths connecting said two routers either equal or less.
  • the present invention also relates to a routing control system in a packet network supported by a transport network authorizing the dynamic creation / deletion of packet transport links of said packet network.
  • the system is of the type that includes
  • a management unit that, based on a metric assigned to each packet network link, determines the shortest path "between said end router head and the tail end router in the same LAN, an announcement unit to the other routers of said network of the metric assigned to each link of the packet network,
  • controlling said unit so as to create a real connection between said two routers and said management unit so as to create real adjacency and to announce said real adjacency as a link with an actual metric, when the traffic between said two routers fills said creation / destruction conditions.
  • said routing system in a packet network comprises a connectivity test unit for testing the connectivity of said link.
  • the management unit includes a real adjacency management unit associated with a table of real adjacencies and a management unit.
  • Virtual unit associated with a table of virtual adjacencies said announcement unit being provided to announce to the other routers of said network the metrics contained in one and the other of said tables.
  • the present invention further relates to a dynamic management unit of the topology of a packet network supported by a transport network authorizing the
  • said unit being arranged to control a management unit which, based on a metric assigned to each link of the packet network, determines the shortest path between said head end router and the tail end router of the same connection, an announcement unit to the other routers of said network of
  • the present invention further relates to a routing unit of a packet network supported by a transport network allowing the dynamic creation / deletion of packet transport links of said packet network, said unit, according to a metric assigned to each a packet network link, determining the shortest path between said head end router and the tail end router of the same connection, and including an announcement unit to other routers of said network of the metric assigned to each link of the packet network, said routing unit being intended for implementing the method described above. It is characterized in that it includes a real adjacency management unit associated with a table of real adjacencies and a virtual management unit associated with a table of virtual adjacencies, said announcement unit being provided to announce to the other routers of said network the metrics contained in one and the other of said tables.
  • Fig. 1 is an exemplary structure of a network to which the present invention can be applied
  • Fig. 2 is a block diagram of a system for dynamic reconfiguration of the topology of a packet network that can implement the method that is the subject of the present invention
  • Fig. 3 shows the three states that can take a packet link that is processed according to the method of the present invention
  • Figs. 4a and 4b show the impact of the method of the present invention on the routing of packets in a network, according to two different choices of virtual metrics allocated to a particular link of this network.
  • the packet network to which the present invention applies is moreover in accordance with the packet networks described in the preamble of the present description.
  • the control system shown in FIG. 2 essentially consists of a unit 2 for dynamic management of the topology of the network functionally connected to a network.
  • Link creation / destruction unit 5 in the transport network (such as the core transport network 10 of Fig. 1) providing physical transport of packets of the packet network. It also comprises an IP network link management unit 3 which is connected to the network topology management unit 2. While the management unit 3 is implemented in each of the routers of the network, the dynamic management units 2 and the creation / destruction of links 5 are also implemented in each of the routers of the network, or centralized units.
  • the routing control method object of the present invention comprises steps that are implemented by one or the other of these units in accordance with the description which follows.
  • the link generation / destruction unit 5 provides the interface between the management unit 2 and the transport network. This is a logic control interface that provides for the transmission of signaling messages between packet router A, B, C, or D of the packet network (see Fig. 1) and the optical switch OXC1 to OXC4 of the packet network. core network 10 to which it is connected for creation, destruction, modification, a request for status of optical circuits of the optical network, etc.
  • the UNI interface is a so-called UNI-interface (see the preamble of the present description).
  • the IP network comprises a real adjacencies management unit 31, a virtual adjacencies management unit 32, a real adjacencies table 33 and a virtual adjacencies table 34. It also comprises a unit 35 (flooding unit). announces to the other routers in the packet network the state of the interfaces of the considered router as well as its real and virtual adjacencies The data describing this state is called Link State Advertisement (LSA).
  • LSA Link State Advertisement
  • an adjacency is a link that links two routers that have become neighbors to exchange routing information, that is, they are not only neighbors, but also that they have synchronized their topology tables. respective, here called adjacency tables.
  • Unit 3 is part of an Interior Gateway Protocol link-state (IGP) type routing protocol.
  • IGP Interior Gateway Protocol link-state
  • unit 2 The function of unit 2 is the following. For each router that may be directly connected to the relevant router (eg router A in Fig. 1 which is likely to be connected directly to the router B), the unit 2 for dynamic management of the topology of the transport network has the function, on the one hand, to ask the unit 3 to create / destroy virtual adjacencies or real and, on the other hand, ask the unit 5 to create / destroy links between these two routers.
  • the operation of the unit 2 will be explained by means of FIG. 3. On this
  • Fig. 3 three states of a link are represented: a non-connected state NC, a virtual connection state CV and a real connection state CR.
  • the unit 2 When no active connection between two routers that are likely to be directly connected is performed, the unit 2 requests the unit 3 to create a virtual adjacency and announce it as a conventional link but with a specific metric MV which is called virtual metric.
  • the system goes into CV virtual connection state (arrow a).
  • the virtual adjacencies management unit 32 then controls the recording in the table 34 of the virtual metric Mv for the link in question.
  • the unit 2 When the unit 2 decides to establish a real connection between two routers, it asks the unit 3 to create a real adjacency and announce it as a conventional link with the real metric Mr of said link.
  • the considered link goes into the actual connection state CR (arrow b).
  • the real adjacencies management unit 31 then controls the recording in the table 33 of the virtual metric Mr for the link considered.
  • the unit 2 may request the unit 3 to delete the virtual adjacency by deleting, by means of the virtual adjacencies management unit 32, the metric Mv of the table 34.
  • the unit 2 uses the unit 5 of creation / destruction of links to create said link between said two routers in the transport network.
  • the unit 2 decides to delete the real connection between the two routers considered, it asks the unit 3 to create a virtual adjacency and to announce it as a conventional link with the virtual metric Mv of said link.
  • the system returns to the CV virtual connection state (arrow c).
  • the virtual adjacencies management unit 32 controls the recording in the table 34 of the virtual metric Mv for the link in question. After a time exceeding the time required, on the one hand, at the creation of this virtual adjacency and, on the other hand, the transmission of this virtual adjacency to the other routers of the packet network, the unit 2 requests that the unit 3 to remove the real adjacency by deleting, by means of the real adjacencies management unit 31, the metric Mr of the table 33.
  • the unit 2 uses the link creation / destruction unit 5 to delete said link between said two routers in the transport network.
  • the unit 2 triggers a process of regular verification of the real connectivity between the two end routers of the virtual adjacency.
  • There is real connectivity when there is a path between two routers consisting of real links, that is, when traffic can be routed, directly or indirectly, between these two routers.
  • This process is supported by a connectivity unit 36.
  • the connectivity unit 36 detects a loss of connectivity, it informs the management unit 32 which then removes the virtual adjacency of the table 34. illustration, the connectivity unit could use a so-called TE-LSP link between the two routers concerned.
  • the link between the two routers returns to the non-connected state NC (arrow d).
  • the unit 2 can command the unit connectivity 36 stopping the connectivity checking process when ordering the removal of a virtual adjacency from the table 34 and the creation of a real adjacency.
  • Mc (A-B) the sum of the metrics Mr (Ii), with Ii representing a link among all the links constituting the shortest path between the routers A and B.
  • Mr (A-B) the actual metric of the link directly linking routers A and B and Mv (A-B) the virtual metric of the link directly linking routers A and B.
  • Mr (A-B) Mv (A-B) ⁇ Mc (A-B)
  • the operator of the packet network chooses one policy rather than another depending on whether or not it wishes to modify, before or after the creation of a real link A-B, the routing of the traffic to this link A-B.
  • Figs. 4a and 4b we consider a packet network consisting of four routers A, B, C and D. It has not shown the corresponding core network since this is not necessary. Two links are assumed: one going from A to B, the other going from D to B. At the moment considered, the link between the routers A and B is ensured via the router C and the link between the router D and the Router B is provided via Router A and also Router C.
  • a virtual adjacency AB of metric Mv is created in the table of virtual adjacencies.
  • the link between routers A and B is in the unconnected state of FIG. 3.
  • the created virtual adjacency is notified to other routers in the network, including routers C and D.
  • the metric Mv of the virtual link between the routers A and B is equal to the metric Mc of the ACB path, ie in the given example 2 (the metrics assigned to the links are represented by digits in the vicinity of the lines representing the links) .
  • the three paths DCB, DACB and DAB have the same metric equal to three.
  • the router D then shares its traffic between the destination of the router A and that of the router C.
  • the average total throughput on any path between the routers A and B is measured by any appropriate method, thus including the traffic flowing between the routers. A and B, but also the traffic flowing between the routers D and B by the path DACB, for example.
  • this average total throughput becomes greater than a threshold rate, the direct link AB is created. He then carries the metric Mr. The AB traffic passes through this link. The same is true of a portion of the traffic from the router D to the router B.
  • the metric Mv of the virtual link between the routers A and B is lower than the metric Mc of the path ACB, ie in the example given 1.
  • the shortest path is the path DAB whose metric is equal to 2 (and not the path DCB or DACB as it could have been the case with the method of the state of the art where the metric Mv is not used).
  • the router D will therefore direct its traffic to the router A.
  • the path followed by this traffic is therefore, for now, the DACB path.
  • the average total bit rate is measured on the path between the routers A and B, thus including the traffic flowing between the routers A and B, but also the traffic flowing between the routers D and B by the path DACB.
  • this average total throughput is greater than a threshold rate
  • the direct link AB is created.
  • the AB traffic passes through this link.
  • DB traffic In this case, before creation of the direct link AB, the traffic is attracted to this link which is then only virtual.
  • the metric Mr is equal to the metric Mv, there is no routing modification after creation of the direct link AB, except for the routing performed by the routers A and B. On the other hand, if the metric Mr is less than the metric Mv, the traffic is attracted to the direct link AB. It will be understood that there is a change in traffic through the network.
  • TE-LSP Traffic Engineering - Label Switching Path

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

La présente invention concerne un procédé de contrôle du routage dans un réseau de paquets supporté par un réseau de transport autorisant la création/suppression dynamique de liens de transport des paquets dudit réseau de paquets, ledit procédé incluant une étape de routage, une étape d'information aux autres routeurs dudit réseau de la métrique affectée à chaque lien du réseau de paquets et une étape de création/destruction d'un lien. Selon la présente invention, ledit lien peut prendre trois états : un état non-connecté lorsque lesdits deux routeurs ne sont pas susceptibles d'être connectés directement, un état de connexion virtuelle dans lequel une métrique virtuelle est affectée audit lien entre ledit routeur d'extrémité de tête et ledit routeur d'extrémité de queue de la même communication, un état de connexion réelle dans lequel une métrique, dite métrique réelle, est normalement affectée audit lien.

Description

Procédé de contrôle de routage dans un réseau de paquets supporté par un réseau de transport
La présente invention concerne un procédé de contrôle du routage dans un réseau de paquets supporté par un réseau de transport autorisant la création/suppression dynamique de liens de transport des paquets dudit réseau de paquets. Elle concerne également un système de contrôle de routage, une unité de contrôle dynamique du routage et une unité de gestion des adjacences pour la mise en œuvre dudit procédé de contrôle du routage.
On appelle un réseau de paquets un réseau qui assure le transfert des paquets porteurs d'information ainsi que les fonctions de routage de ces paquets. Les paquets dont il est question dans la présente description sont par exemple des paquets IP (Internet Protocol). La présente invention s'applique tout particulièrement à un réseau de paquets qui a la structure, selon le modèle dit à superposition de couches (overlay), dont un exemple est représenté à la Fig. 1. Il comprend des routeurs, par exemple au nombre de quatre A, B, C et D, reliés les uns les autres par un réseau de transport cœur 10, par exemple un réseau de transport optique, comportant des commutateurs optiques OXCl à OXC4 capables de faire transiter les paquets traités par chaque routeur A, B, C, D. Une interface client-réseau UNI assure le contrôle logique entre un routeur et le réseau cœur.
Plus précisément, la présente invention s'applique au cas d'un réseau architecture selon le modèle dit "overlay" où le domaine des paquets (par exemple le domaine IP) est relativement indépendant du domaine du réseau de transport cœur (par exemple le domaine optique). Le réseau cœur assure des connexions qui sont vues du réseau de paquets comme étant point à point. Le réseau de paquets agit vis-à-vis du réseau cœur comme un client. De plus, le protocole de routage du réseau de paquets et celui de réseau cœur sont indépendants. L'interface entre un routeur et un commutateur du réseau cœur 10 est une interface de contrôle logique qui prévoit l'émission de messages de signalisation entre un routeur périphérique et le commutateur optique du réseau optique auquel il est relié pour la création, la destruction, la modification, une demande de statuts de circuits optiques du réseau optique. Il peut s'agir d'une interface entre un réseau de paquets IP et un réseau de transport optique dite interface 0-UNI (Optical-User Network Interface) telle que celles qui sont décrites par les organismes de normalisation OIF (Optical Internetworking Forum) et IETF (Internet Engineering Task Force). Dans ce cas, les messages de signalisation sont basés sur le protocole de réservation de ressources avec ingénierie de trafic RSVP-TE (Resource Réservation Protocol - Traffic Engineering).
Comme cela est le cas pour un réseau IP, un réseau à commutation de paquets met généralement en œuvre un protocole de routage dont la fonction essentielle est de déterminer pour des paquets devant transiter d'un routeur à un autre, le chemin le moins coûteux (on dit aussi le chemin le plus court) sachant qu'à chaque lien d'un routeur à un autre auquel il est relié est affecté un coût, également appelé métrique. Le protocole de routage dont il est question ici est un protocole de routage à état de lien (link state), par exemple du type interne, comme un protocole du type IGP link state (Interior Gateway Protocol : Protocole intra-domaine), tel que notamment le protocole dit OSPF (Open Shortest Path First). Ce dernier fait notamment l'objet de la requête pour commentaires 2328 (RFC 2328). Il pourrait également s'agir du protocole ISIS
(Intermediate System to Intermediate System : système intermédiaire à système intermédiaire) décrit notamment dans la requête pour commentaires 3784 (RFC 3784).
Le principe de fonctionnement d'un protocole du type IGP link state est le suivant. A chaque adjacence du réseau IP que le protocole lui-même peut déterminer par un protocole particulier dit protocole Hello, est associée une métrique dont la valeur est représentative d'une caractéristique de l'adjacence : une valeur arbitraire attribuée par l'administrateur du réseau (par exemple une valeur de 1 représentant un routeur traversé, le délai de transmission sur le lien considéré, la fiabilité du lien, etc.). La métrique peut également être appelée coût du lien considéré. Le protocole calcule alors la route vers l'ensemble des routeurs du réseau en utilisant un algorithme "du plus court chemin d'abord" SPF, la longueur d'un chemin (ou le coût d'un chemin) étant déterminée par sommation des métriques des liens formant ce chemin.
La présente invention ne s'intéresse donc qu'au réseau de paquets qui, dans un exemple de réalisation qui sera décrit, est un réseau IP, avec un protocole de routage à état de liens, par exemple du type IGP link state.
On appelle "adjacence" un lien qui lie deux routeurs qui sont devenus voisins pour échanger des informations de routage, c'est-à-dire qu'ils sont non seulement voisins parce qu'ils ont chacun une interface à un même réseau mais aussi qu'ils ont synchronisé leurs tables de topologie respectives.
Les capacités de contrôle offertes par un protocole de routage à état de lien, tel que le protocole IGP, ne sont pas adéquates pour effectuer de l'ingénierie de trafic (TE). Du fait que les algorithmes de routage à trajet le plus court (SPF : Shortest Path First) sont optimisés sur la base de simples métriques, ils ne prennent pas en compte les caractéristiques de trafic et de disponibilité de bande passante pour leurs décisions de routage. Ainsi, des congestions peuvent avoir lieu lorsque les trajets les plus courts de plusieurs flux de trafic convergent sur de mêmes liens ou de mêmes routeurs ou encore lorsqu'un flux de trafic converge sur un lien ou un routeur qui ne possède pas une bande passante suffisante pour le supporter. Le modèle à superposition de couches (modèle overlay) décrit ci-dessus en relation avec la Fig. 1 permet de résoudre en partie ces problèmes en créant des topologies virtuelles au-dessus de la topologie physique du réseau de paquets. Une topologie virtuelle est ainsi constituée de circuits virtuels qui apparaissent comme des liens physiques pour le protocole de routage. De cette manière, le contrôle du trafic et des ressources peut être envisagé au niveau de la topologie virtuelle.
Un exemple de mise en œuvre de cette superposition d'une topologie virtuelle consiste à faire supporter par le réseau de paquets un réseau de transport optique qui lui assure l'ingénierie de trafic. Ainsi, dans l'article intitulé "Distributed Virtual Network Topology Control Mechanism in GMPLS-Based Multiregion Networks" paru dans IEEE Journal on Selected Areas in Communications, vol 21, no.8, ppp : 1254 - 1262 d'octobre 2003, dont les auteurs sont K. Shiomoto and ail, est décrite une méthode de reconfiguration dynamique de la topologie virtuelle du réseau (VNT : Virtual Network Topology) qui est distribuée (c'est-à-dire qu'il n'y a aucune coordination centralisée dans l'exécution de la reconfiguration du réseau) et qui consiste essentiellement dans l'utilisation d'un protocole de routage à état de liens (du type IGP mentionné ci-dessus) pour que chaque nœud partage la même topologie virtuelle et une demande de trafic sur les trajets optiques individuels, lequel trafic est mesuré au nœud d'origine. Le protocole de routage à état de liens est utilisé pour disséminer les informations portant sur la topologie virtuelle et celles portant sur la demande de trafic sur le trajet optique. Chaque nœud calcule la nouvelle topologie et la compare à la présente afin d'identifier les trajets optiques qui devraient être activés/désactivés. Lorsque ce nœud est le nœud d'origine du trajet optique, la procédure d'activation/désactivation est mise en œuvre. Lorsque chaque nœud a ainsi agi, la topologie VNT est reconfigurée et le trafic IP est re-routé sur la nouvelle topologie.
L'algorithme de calcul de la nouvelle topologie ajoute de nouveaux trajets optiques afin de limiter les congestions qui peuvent apparaître, compte tenu du trafic et par contre, supprime un trajet optique qui est sous-utilisé. Deux seuils de trafic (un haut et un bas) sont respectivement définis pour les trajets optiques congestionnés et les trajets optiques sous-utilisés. Si la demande de trafic sur un trajet optique est supérieure au seuil haut, un nouveau trajet optique est créé afin que le trafic sur le trajet optique congestionné soit re-routé. Les nœuds d'extrémité du nouveau trajet optique sont sélectionnés parmi toutes les adjacences des nœuds d'extrémité du lien congestionné. Par contre, si la demande de trafic sur un trajet optique est inférieure au seuil bas, ce trajet optique est supprimé à condition que cela n'introduise alors pas une congestion.
Plus précisément, le document dont il est question ici décrit une méthode de reconfiguration dynamique virtuelle et distribuée de la topologie de réseaux de paquets à protocole Internet (IP) supportant la commutation MPLS-TE ou GMPLS (Generalized MPLS : voir à ce sujet les requêtes pour commentaires RFC 3471 et suivantes) sur des réseaux optiques à multiplexage par division de longueurs d'ondes (WDM : Wavelength-division-multiplexing). Cette méthode consiste en un mécanisme qui, en fonction de la charge de trafic sur des chemins du type TE-LSP, décide d'établir ou de supprimer des circuits optiques du réseau WDM.
Ce document décrit donc la mise à jour dynamique de la topologie d'un réseau en fonction de la matrice de trafic. Le mécanisme qui est décrit dans le document mentionné ci-dessus présente néanmoins l'inconvénient de ne pas proposer de mécanismes capables de contrôler l'impact d'une création/destruction de liens sur le protocole de routage. En effet, on a pu mettre en évidence un tel impact qui crée des instabilités de la topologie et des changements trop fréquents. Il peut même en résulter des congestions ou des sous- utilisations de certains liens.
Le but de la présente invention est donc de proposer un procédé de contrôle de la topologie d'un réseau de paquets supporté par un réseau de transport autorisant la création/suppression dynamique de liens de transport des paquets dudit réseau de paquets qui ne présente pas les inconvénients des procédés de l'art antérieur tel que celui qui est décrit dans le document mentionné ci-dessus.
La présente invention concerne donc un procédé de contrôle du routage dans un réseau de paquets supporté par un réseau de transport autorisant la création/suppression dynamique de liens de transport des paquets dudit réseau de paquets, ledit procédé incluant : - une étape de routage qui, en fonction d'une métrique affectée à chaque lien du réseau de paquets, détermine le chemin le plus court entre ledit routeur d'extrémité de tête et le routeur d'extrémité de queue de la même connexion,
- une étape d'information aux autres routeurs dudit réseau de la métrique affectée à chaque lien du réseau de paquets, - une étape de création/destruction d'un lien ou d'une connexion entre ledit routeur d'extrémité de tête et le routeur d'extrémité de queue de la même communication lorsque le chemin le plus court passe par ledit lien et que le trafic entre lesdits deux routeurs remplit des conditions de création/destruction.
Selon une caractéristique essentielle de la présente invention, ledit lien peut prendre trois états :
- un état non-connecté lorsque lesdits deux routeurs ne sont pas susceptibles d'être connectés directement,
- un état de connexion virtuelle dans lequel une métrique virtuelle est affectée audit lien entre ledit routeur d'extrémité de tête et ledit routeur d'extrémité de queue de la même communication, ledit état étant pris lorsque ledit lien est susceptible de faire l'objet d'une connexion directe et que le trafic entre lesdits deux routeurs ne remplit pas lesdites conditions de création/destruction, ladite métrique virtuelle faisant alors l'objet d'une information aux autres routeurs d'une métrique indifférenciée, - un état de connexion réelle dans lequel une métrique, dite métrique réelle, est normalement affectée audit lien entre ledit routeur d'extrémité de tête et ledit routeur d'extrémité de queue de la même communication, ledit état étant pris lorsque le trafic entre lesdits deux routeurs remplit lesdites conditions de création/destruction.
Selon une autre caractéristique de la présente invention, pour le lien considéré, la valeur de la métrique virtuelle est choisie relativement à celle de la métrique réelle soit égale soit inférieure.
Selon une autre caractéristique de la présente invention, pour le lien considéré entre deux routeurs, la valeur de la métrique virtuelle est choisie relativement à celle de la somme des métriques réelles des chemins indirects reliant lesdits deux routeurs soit égale soit inférieure.
Selon une autre caractéristique de la présente invention, lorsque ledit lien est dans son état de connexion virtuelle, un test de connectivité est réalisé.
La présente invention concerne également un système de contrôle du routage dans un réseau de paquets supporté par un réseau de transport autorisant la création/suppression dynamique de liens de transport des paquets dudit réseau de paquets. Ledit système est du type qui comprend
- une unité de gestion qui, en fonction d'une métrique affectée à chaque lien du réseau de paquets, détermine le chemin le plus court "entre ledit routeur d'extrémité de tête et le routeur d'extrémité de queue de la même connexion, - une unité d'annonce aux autres routeurs dudit réseau de la métrique affectée à chaque lien du réseau de paquets,
- une unité pour la création/destruction d'un lien ou d'une connexion entre ledit routeur d'extrémité de tête et le routeur d'extrémité de queue de la même communication lorsque le chemin le plus court passe par ledit lien et que le trafic entre lesdits deux routeurs remplit des conditions de création/destruction, et
- une unité de gestion dynamique de la topologie du réseau.
Il est caractérisé en ce que ladite unité de gestion dynamique de la topologie du réseau est prévue pour : W
- commander ladite une unité de gestion de manière à créer une adjacence virtuelle et à annoncer ladite adjacence virtuelle comme un lien avec une métrique virtuelle, lorsque ledit lien est susceptible de faire l'objet d'une connexion directe et que le trafic entre lesdits deux routeurs ne remplit pas lesdites conditions de
5 création/destruction, et
- commander ladite unité de manière à créer une connexion réelle entre lesdits deux routeurs et ladite unité de gestion de manière à créer une adjacence réelle et à annoncer ladite adjacence réelle comme un lien avec une métrique réelle, lorsque le trafic entre lesdits deux routeurs remplit lesdites conditions de création/destruction.
10 Avantageusement, ledit système de contrôle du routage dans un réseau de paquets comporte une unité de test de connectivité pour tester la connectivité dudit lien.
De même, il est tel que ladite unité de gestion inclut une unité de gestion des adjacences réelles associée à une table des adjacences réelles et une unité de gestion
15 virtuelles associée à une table des adjacences virtuelles, ladite unité d'annonce étant prévue pour annoncer aux autres routeurs dudit réseau les métriques contenues dans l'une et l'autre desdites tables.
La présente invention concerne encore une unité de gestion dynamique de la topologie d'un réseau de paquets supporté par un réseau de transport autorisant la
20 création/suppression dynamique de liens de transport des paquets dudit réseau de paquets, ladite unité étant prévue pour commander une unité de gestion qui, en fonction d'une métrique affectée à chaque lien du réseau de paquets, détermine le chemin le plus court entre ledit routeur d'extrémité de tête et le routeur d'extrémité de queue de la même connexion, une unité d'annonce aux autres routeurs dudit réseau de
25 la métrique affectée à chaque lien du réseau de paquets et une unité pour la création/destruction d'un lien ou d'une connexion entre ledit routeur d'extrémité de tête et le routeur d'extrémité de queue de la même communication lorsque le chemin le plus court passe par ledit lien et que le trafic entre lesdits deux routeurs remplit des conditions de création/destruction. Elle est caractérisée en ce qu'elle est prévue pour :
30 - commander ladite une unité de gestion de manière à créer une adjacence virtuelle et à annoncer ladite adjacence virtuelle comme un lien avec une métrique virtuelle, lorsque ledit lien est susceptible de faire l'objet d'une connexion directe et que le trafic entre lesdits deux routeurs ne remplit pas lesdites conditions de création/destruction, et - commander ladite unité de manière à créer une connexion réelle entre lesdits deux routeurs et ladite unité de gestion de manière à créer une adjacence réelle et à annoncer ladite adjacence réelle comme un lien avec une métrique réelle, lorsque le trafic entre lesdits deux routeurs remplit lesdites conditions de création/destruction. La présente invention concerne enfin une unité de routage d'un réseau de paquets supporté par un réseau de transport autorisant la création/suppression dynamique de liens de transport des paquets dudit réseau de paquets, ladite unité, en fonction d'une métrique affectée à chaque lien du réseau de paquets, déterminant le chemin le plus court entre ledit routeur d'extrémité de tête et le routeur d'extrémité de queue de la même connexion, et incluant une unité d'annonce aux autres routeurs dudit réseau de la métrique affectée à chaque lien du réseau de paquets, ladite unité de routage étant destinée à la mise en œuvre du procédé décrit ci-dessus. Elle est caractérisé en ce qu'elle inclut une unité de gestion des adjacences réelles associée à une table des adjacences réelles et une unité de gestion virtuelles associée à une table des adjacences virtuelles, ladite unité d'annonce étant prévue pour annoncer aux autres routeurs dudit réseau les métriques contenues dans l'une et l'autre desdites tables.
Les caractéristiques de l'invention mentionnées ci-dessus, ainsi que d'autres, apparaîtront plus clairement à la lecture de la description suivante d'un exemple de réalisation, ladite description étant faite en relation avec les dessins joints, parmi lesquels :
La Fig. 1 est un exemple de structure d'un réseau auquel la présente invention peut s'appliquer,
La Fig. 2 est un schéma synoptique d'un système de reconfiguration dynamique de la topologie d'un réseau de paquets pouvant mettre en œuvre le procédé objet de la présente invention,
La Fig. 3 montre les trois états que peut prendre un lien de paquets qui est traité selon le procédé de la présente invention, et
Les Figs. 4a et 4b montrent l'impact du procédé de la présente invention sur le routage des paquets dans un réseau, selon deux choix différents de métrique virtuelle allouée à un lien particulier de ce réseau.
Le réseau de paquets auquel s'applique la présente invention est par ailleurs conforme aux réseaux de paquets décrits dans le préambule de la présente description.
Le système de contrôle représenté à la Fig. 2 est essentiellement constitué d'une unité 2 de gestion dynamique de la topologie du réseau reliée fonctionnellement à une unité 5 de création/destruction de liens dans le réseau de transport (tel que le réseau de transport cœur 10 de la Fig. 1) assurant le transport physique des paquets du réseau de paquets. Il comporte également une unité 3 de gestion des liens du réseau IP qui est reliée à l'unité 2 de gestion de la topologie du réseau. Alors que l'unité de gestion 3 est implémentée dans chacun des routeurs du réseau, les unités de gestion dynamique 2 et de création/destruction de liens 5 sont, soit également implémentées dans chacun des routeurs du réseau, soit des unités centralisées. Le procédé de contrôle du routage objet de la présente invention comporte des étapes qui sont mises en œuvre par l'une ou l'autre de ces unités conformément à la description qui suit.
L'unité 5 de création/destruction de liens réalise l'interface entre l'unité de gestion 2 et le réseau de transport. Il s'agit d'une interface de contrôle logique qui prévoit l'émission de messages de signalisation entre un routeur de paquets A, B, C ou D du réseau de paquets (voir Fig. 1) et le commutateur optique OXCl à OXC4 du réseau cœur 10 auquel il est relié pour la création, la destruction, la modification, une demande de statuts de circuits optiques du réseau optique, etc. Dans un mode préférentiel de réalisation de la présente invention, le réseau cœur 10 étant un réseau de transport optique, l'interface UNI est une interface dite 0-UNI (voir préambule de la présente description. L'unité 3 de gestion des liens du réseau IP comprend quant à elle une unité de gestion des adjacences réelles 31, une unité de gestion des adjacences virtuelles 32, une table des adjacences réelles 33 et une table des adjacences virtuelles 34. Elle comporte également une unité 35 (unité de flooding) d'annonce aux autres routeurs du réseau de paquets de l'état des interfaces du routeur considéré ainsi que de ses adjacences réelles et virtuelles. Les données qui décrivent cet état sont appelées LSA (Link State Advertisement).
On rappelle qu'une adjacence est un lien qui lie deux routeurs qui sont devenus voisins pour échanger des informations de routage, c'est-à-dire qu'ils sont non seulement voisins, mais aussi qu'ils ont synchronisé leurs tables de topologie respectives, ici appelées tables des adjacences.
L'unité 3 est une partie d'un protocole de routage du type IGP à état de lien (Interior Gateway Protocol link-state).
La fonction de l'unité 2 est la suivante. Pour chaque routeur qui est susceptible d'être raccordé directement au routeur concerné (par exemple le routeur A de la Fig. 1 qui est susceptible d'être raccordé directement au routeur B), l'unité 2 de gestion dynamique de la topologie du réseau de transport a pour fonction, d'une part, de demander à l'unité 3 de créer/détruire des adjacences virtuelles ou réelles et, d'autre part, de demander à l'unité 5 de créer/détruire des liens entre ces deux routeurs. On va expliciter le fonctionnement de l'unité 2 au moyen de la Fig. 3. Sur cette
Fig. 3, on a représenté trois états d'un lien : un état non connecté NC, un état de connexion virtuelle CV et un état de connexion réelle CR.
Lorsque deux routeurs ne sont pas susceptibles d'être directement connectables, le lien qui aurait pu relier directement ces deux routeurs est dans l'état non connecté NC.
Lorsqu'aucune connexion active entre deux routeurs qui sont susceptibles d'être connectés directement n'est effectuée, l'unité 2 demande à l'unité 3 de créer une adjacence virtuelle et de l'annoncer comme un lien classique mais avec une métrique spécifique Mv qui est dite métrique virtuelle. Le système passe dans l'état de connexion virtuelle CV (flèche a). L'unité de gestion des adjacences virtuelles 32 commande alors l'enregistrement dans la table 34 de la métrique virtuelle Mv pour le lien considéré.
Lorsque l'unité 2 décide d'établir une connexion réelle entre deux routeurs, elle demande à l'unité 3 de créer une adjacence réelle et de l'annoncer comme un lien classique avec la métrique réelle Mr dudit lien. Le lien considéré passe dans l'état de connexion réelle CR (flèche b). L'unité de gestion des adjacences réelles 31 commande alors l'enregistrement dans la table 33 de la métrique virtuelle Mr pour le lien considéré. Après un temps excédant au moins le temps nécessaire, d'une part, à la création de cette adjacence réelle et, d'autre part, à la transmission de cette adjacence aux autres routeurs du réseau de paquets (au moyen de l'unité de flooding 35), l'unité 2 peut demander à l'unité 3 de supprimer l'adjacence virtuelle par suppression, au moyen de l'unité de gestion des adjacences virtuelles 32, de la métrique Mv de la table 34.
On notera que pour les autres routeurs du réseau de paquets, la transformation de l'adjacence virtuelle en adjacence réelle consiste uniquement à modifier la métrique du lien considéré, puisqu'ils n'ont pas connaissance, en ce qui concerne le lien considéré, de cette notion de virtuel et de réel.
On notera encore que l'annonce de la métrique réelle aux routeurs autres que ceux d'extrémité du lien considéré n'est pas nécessaire et, n'est donc avantageusement pas réalisée, lorsque la métrique virtuelle est choisie supérieure à la métrique réelle, dans la mesure où, dans ce cas, cette annonce n'aurait aucune incidence sur le routage. Pour que la création soit effective, l'unité 2 fait appel à l'unité 5 de création/destruction de liens pour créer ledit lien entre lesdits deux routeurs dans le réseau de transport.
Inversement, lorsque l'unité 2 décide de supprimer la connexion réelle entre les deux routeurs considérés, elle demande à l'unité 3 de créer une adjacence virtuelle et de l'annoncer comme un lien classique avec la métrique virtuelle Mv dudit lien. Le système repasse dans l'état de connexion virtuelle CV (flèche c). L'unité de gestion des adjacences virtuelles 32 commande alors l'enregistrement dans la table 34 de la métrique virtuelle Mv pour le lien considéré. Après un temps excédant au moins le temps nécessaire, d'une part, à la création de cette adjacence virtuelle et, d'autre part, à la transmission de cette adjacence virtuelle aux autres routeurs du réseau de paquets, l'unité 2 demande à l'unité 3 de supprimer l'adjacence réelle par suppression, au moyen de l'unité de gestion des adjacences réelles 31, de la métrique Mr de la table 33.
Pour que cette création soit effective, l'unité 2 fait appel à l'unité 5 de création/destruction de liens pour supprimer ledit lien entre lesdits deux routeurs dans le réseau de transport. Avantageusement, lorsqu'une liaison entre deux routeurs est dans l'état de connexion virtuelle, l'unité 2 déclenche un processus de vérification régulier de la connectivité réelle entre les deux routeurs d'extrémité de l'adjacence virtuelle. Il y a connectivité réelle lorsqu'il existe un chemin entre deux routeurs constitué de liens réels, c'est-à-dire lorsque le trafic peut être acheminé, directement ou indirectement, entre ces deux routeurs. Ce processus est pris en charge par une unité de connectivité 36. Lorsque l'unité de connectivité 36 détecte une perte de connectivité, elle en informe l'unité de gestion 32 qui supprime alors l'adjacence virtuelle de la table 34. A titre d'illustration, l'unité de connectivité pourrait utiliser une liaison dite TE-LSP entre les deux routeurs concernés. La liaison entre les deux routeurs repasse dans l'état non-connecté NC (flèche d).
Dans la mesure où, lorsqu'une liaison se trouve dans l'état connecté, le test de connectivité est pris en charge par le protocole de routage (par exemple par le protocole dit Hello), l'unité 2 peut commander à l'unité de connectivité 36 l'arrêt du processus de vérification de la connectivité lors de la commande de la suppression d'une adjacence virtuelle de la table 34 et la création d'une adjacence réelle.
On comprendra que l'attribution des métriques Mv et Mr à un lien particulier déterminera le comportement du système, notamment en ce qui concerne l'impact sur le routage des paquets du réseau de paquets (par exemple des paquets IP) de la création/destruction de liens réels. On appelle métrique Mr(I) la métrique du lien 1,
Mc(A-B) la somme des métriques Mr(Ii), avec Ii représentant un lien parmi tous les liens constituant le plus court chemin entre les routeurs A et B. On notera encore
Mr(A-B) la métrique réelle du lien liant directement les routeurs A et B et Mv(A-B) la métrique virtuelle du lien liant directement les routeurs A et B.
Différentes politiques de choix des valeurs Mr et MV annoncées sont possibles selon les valeurs relatives de Mr(A-B) et de Mv(A-B), mais aussi selon les valeurs relatives de Mc(A-B) et Mv(A-B). Au total, les quatre cas suivants peuvent être considérés :
I) Mr(A-B) = Mv(A-B) = Mc(A-B)
2) Mr(A-B) = Mv(A-B) < Mc(A-B)
3) Mr(A-B) < Mv(A-B) = Mc(A-B)
4) Mr(A-B) < Mv(A-B) < Mc(A-B)
Ces quatre cas dépendent de la valeur prise par la métrique Mv(A-B), d'une part, relativement à la somme des métriques Mc(A-B) et, d'autre part, relativement à la métrique réelle Mr(A-B).
L'opérateur du réseau de paquets choisit telle politique plutôt qu'une autre suivant qu'il souhaite modifier ou non, avant ou après la création d'un lien réel A-B, le routage du trafic vers ce lien A-B.
Aux Figs. 4a et 4b, on considère un réseau de paquets constitué de quatre routeurs A, B, C et D. On n'a pas représenté le réseau cœur correspondant puisque cela n'est pas nécessaire. On suppose deux liaisons : l'une allant de A vers B, l'autre allant de D vers B. Au moment considéré, la liaison entre les routeurs A et B est assurée via le routeur C et la liaison entre le routeur D et le routeur B est assurée via le routeur A et également le routeur C.
On se place du point de vue du routeur A. Puisque la connexion entre les routeurs A et B n'est pas effectuée, une adjacence virtuelle AB de métrique Mv est créée dans la table des adjacences virtuelles. La liaison entre les routeurs A et B est dans l'état non-connecté de la Fig. 3. L'adjacence virtuelle créée est notifiée aux autres routeurs du réseau, notamment aux routeurs C et D.
Dans le cas de la Fig. 4a, la métrique Mv du lien virtuel entre les routeurs A et B est égale à la métrique Mc du chemin ACB, soit dans l'exemple donné 2 (les métriques affectées aux liens sont représentées par des chiffres au voisinage des traits représentant les liens). On peut remarquer que pour le routeur D, les trois chemins DCB, DACB et DAB ont la même métrique égale à trois. Le routeur D partage alors son trafic entre la destination du routeur A et celle du routeur C. On mesure, par toute méthode appropriée, le débit total moyen sur tout chemin entre les routeurs A et B, incluant par conséquent le trafic circulant entre les routeurs A et B, mais aussi le trafic circulant entre les routeurs D et B par le chemin DACB, par exemple. Lorsque ce débit total moyen devient supérieur à un débit seuil, le lien direct AB est créé. Il porte alors la métrique Mr. Le trafic AB passe donc par ce lien. II en est de même d'une partie du trafic du routeur D vers le routeur B.
On constate que le routage qui est effectué aussi bien par le routeur C que le routeur D (tous les routeurs à l'exception des routeurs d'extrémité du lien considéré) est mis en place au moment où la liaison est déclarée dans l'état de connexion virtuelle et n'est pas modifié après le passage à l'état de connexion réelle de la liaison. En conséquence, la répartition du trafic à travers le réseau de paquets n'est pas modifiée après la création du lien direct A-B et il en résulte une stabilité du routage obtenue grâce à l'invention.
Dans le cas de la Fig. 4b, la métrique Mv du lien virtuel entre les routeurs A et B est inférieure à la métrique Mc du chemin ACB, soit dans l'exemple donné 1. On peut remarquer que pour le routeur D, le chemin le plus court est le chemin DAB dont la métrique est égale à 2 (et non le chemin DCB ou DACB comme cela aurait pu être le cas avec la méthode de l'état de la technique où n'est pas utilisée la métrique Mv). Le routeur D va donc aiguiller son trafic vers le routeur A. Le chemin suivi par ce trafic est par conséquent, pour l'instant, le chemin DACB. Comme précédemment, on mesure le débit total moyen sur le chemin entre les routeurs A et B, incluant par conséquent le trafic circulant entre les routeurs A et B, mais aussi le trafic circulant entre les routeurs D et B par le chemin DACB. Lorsque ce débit total moyen est supérieur à un débit seuil, le lien direct AB est créé. Le trafic AB passe donc par ce lien. Il en est de même du trafic DB. Dans ce cas, avant la création du lien direct A-B, le trafic est attiré vers ce lien qui n'est alors qu'encore virtuel.
On constate également que le routage qui est effectué aussi bien par le routeur C que le routeur D (tous les routeurs à l'exception des routeurs d'extrémité du lien considéré) est mis en place au moment où la liaison est déclarée dans l'état de connexion virtuelle et n'est pas modifié après le passage à l'état de connexion réelle de la liaison. En conséquence, la répartition du trafic à travers le réseau de paquets n'est pas modifiée après la création du lien direct A-B. Il en résulte une stabilité du routage obtenue grâce à l'invention. Dans l'un ou l'autre cas, une fois le lien A-B créé, la métrique Mr est appliquée au lien direct A-B. On se retrouve dans l'état de connexion réelle CR de la Fig. 3.
Dans la mesure où la métrique Mr est égale à la métrique Mv, il n'y a pas de modification de routage après création du lien direct A-B, hormis le routage effectué par les routeurs A et B. Par contre, si la métrique Mr est inférieure à la métrique Mv, le trafic est attiré vers le lien direct A-B. On comprendra qu'il y a modification du trafic à travers le réseau.
Lorsque le débit total moyen sur un lien, par exemple le lien entre les routeurs A et B, tombe en dessous d'un seuil bas, ce lien est physiquement supprimé et la métrique affectée à ce lien devient, pour ces routeurs, une métrique virtuelle Mv (état de connexion virtuelle de la Fig. 3). Si la valeur de cette métrique est supérieure à la valeur de la métrique réelle sur ce lien, le routage effectué par les routeurs, notamment les routeurs autres que les routeurs d'extrémité (en l'occurrence les routeurs C et D) va être modifié. Cela ne sera par contre pas le cas si la valeur de la métrique réelle est égale à la valeur de la métrique virtuelle.
Pour pouvoir mesurer le débit total du trafic qui transite entre les routeurs A et B, il peut être avantageux d'établir entre ces deux routeurs A et B un chemin dit TE- LSP (Traffic Engineering - Label Switching Path) qui agrège tout le trafic, direct ou indirect, entre ces deux routeurs. Cette méthode particulière permet d'éviter un routage du trafic où suite à des choix de métriques particulières, des boucles pourraient se produire.

Claims

REVENDICATIONS
1) Procédé de contrôle du routage dans un réseau de paquets supporté par un réseau de transport autorisant la création/suppression dynamique de liens de transport des paquets dudit réseau de paquets, ledit procédé incluant : - une étape de routage qui, en fonction d'une métrique affectée à chaque lien du réseau de paquets, détermine le chemin le plus court entre ledit routeur d'extrémité de tête et le routeur d'extrémité de queue de la même connexion,
- une étape d'information aux autres routeurs dudit réseau de la métrique affectée à chaque lien du réseau de paquets, - une étape de création/destruction d'un lien ou d'une connexion entre ledit routeur d'extrémité de tête et le routeur d'extrémité de queue de la même communication lorsque le chemin le plus court passe par ledit lien et que le trafic entre lesdits deux routeurs remplit des conditions de création/destruction, caractérisé en ce que ledit lien peut prendre trois états : - un état non-connecté lorsque lesdits deux routeurs ne sont pas susceptibles d'être connectés directement,
- un état de connexion virtuelle dans lequel une métrique virtuelle est affectée audit lien entre ledit routeur d'extrémité de tête et ledit routeur d'extrémité de queue de la même communication, ledit état étant pris lorsque ledit lien est susceptible de faire l'objet d'une connexion directe et que le trafic entre lesdits deux routeurs ne remplit pas lesdites conditions de création/destruction, ladite métrique virtuelle faisant alors l'objet d'une information aux autres routeurs d'une métrique indifférenciée,
- un état de connexion réelle dans lequel une métrique, dite métrique réelle, est normalement affectée audit lien entre ledit routeur d'extrémité de tête et ledit routeur d'extrémité de queue de la même communication, ledit état étant pris lorsque le trafic entre lesdits deux routeurs remplit lesdites conditions de création/destruction.
2) Procédé de contrôle du routage dans un réseau de paquets selon la revendication 1 , caractérisé en ce que pour le lien considéré, la valeur de la métrique virtuelle est choisie relativement à celle de la métrique réelle soit égale soit inférieure. 3) Procédé de contrôle du routage dans un réseau de paquets selon la revendication 1 ou 2, caractérisé en ce que pour le lien considéré entre deux routeurs, la valeur de la métrique virtuelle est choisie relativement à celle de la somme des métriques réelles des chemins indirects reliant lesdits deux routeurs soit égale soit inférieure.
4) Procédé de contrôle du routage dans un réseau de paquets selon l'une quelconque des revendications précédentes, caractérisé en ce que lorsque ledit lien est dans son état de connexion virtuelle, un test de connectivité est réalisé.
5) Système de contrôle du routage dans un réseau de paquets supporté par un réseau de transport autorisant la création/suppression dynamique de liens de transport des paquets dudit réseau de paquets, ledit système comprenant : - une unité de gestion (3) qui, en fonction d'une métrique affectée à chaque lien du réseau de paquets, détermine le chemin le plus court entre ledit routeur d'extrémité de tête et le routeur d'extrémité de queue de la même connexion,
- une unité d'annonce (35) aux autres routeurs dudit réseau de la métrique affectée à chaque lien du réseau de paquets, - une unité (5) pour la création/destruction d'un lien ou d'une connexion entre ledit routeur d'extrémité de tête et le routeur d'extrémité de queue de la même communication lorsque le chemin le plus court passe par ledit lien et que le trafic entre lesdits deux routeurs remplit des conditions de création/destruction, et
- une unité (2) de gestion dynamique de la topologie du réseau, caractérisé en ce que ladite unité (2) est prévue pour :
- commander ladite une unité de gestion (3) de manière à créer une adjacence virtuelle et à annoncer ladite adjacence virtuelle comme un lien avec une métrique virtuelle, lorsque ledit lien est susceptible de faire l'objet d'une connexion directe et que le trafic entre lesdits deux routeurs ne remplit pas lesdites conditions de création/destruction, et
- commander ladite unité (5) de manière à créer une connexion réelle entre lesdits deux routeurs et ladite unité de gestion (3) de manière à créer une adjacence réelle et à annoncer ladite adjacence réelle comme un lien avec une métrique réelle, lorsque le trafic entre lesdits deux routeurs remplit lesdites conditions de création/destruction.
6) Système de contrôle du routage dans un réseau de paquets selon la revendication 5, caractérisé en ce qu'il comporte une unité de test de connectivité (36) pour tester la connectivité dudit lien.
7) Système de contrôle du routage dans un réseau de paquets selon la revendication 5 ou 6, caractérisé en ce que ladite unité de gestion (3) inclut une unité de gestion des adjacences réelles (31) associée à une table des adjacences réelles (33) et une unité de gestion virtuelles (32) associée à une table des adjacences virtuelles (34), ladite unité d'annonce (35) étant prévue pour annoncer aux autres routeurs dudit réseau les métriques contenues dans l'une et l'autre desdites tables (33 et 34).
8) Unité (2) de gestion dynamique de la topologie d'un réseau de paquets supporté par un réseau de transport autorisant la création/suppression dynamique de liens de transport des paquets dudit réseau de paquets, ladite unité étant prévue pour commander :
- une unité de gestion (3) qui, en fonction d'une métrique affectée à chaque lien du réseau de paquets, détermine le chemin le plus court entre ledit routeur d'extrémité de tête et le routeur d'extrémité de queue de la même connexion,
- une unité d'annonce (35) aux autres routeurs dudit réseau de la métrique affectée à chaque lien du réseau de paquets,
- une unité (5) pour la création/destruction d'un lien ou d'une connexion entre ledit routeur d'extrémité de tête et le routeur d'extrémité de queue de la même communication lorsque le chemin le plus court passe par ledit lien et que le trafic entre lesdits deux routeurs remplit des conditions de création/destruction, caractérisée en ce qu'elle est prévue pour :
- commander ladite une unité de gestion (3) de manière à créer une adjacence virtuelle et à annoncer ladite adjacence virtuelle comme un lien avec une métrique virtuelle, lorsque ledit lien est susceptible de faire l'objet d'une connexion directe et que le trafic entre lesdits deux routeurs ne remplit pas lesdites conditions de création/destruction, et - commander ladite unité (5) de manière à créer une connexion réelle entre lesdits deux routeurs et ladite unité de gestion (3) de manière à créer une adjacence réelle et à annoncer ladite adjacence réelle comme un lien avec une métrique réelle, lorsque le trafic entre lesdits deux routeurs remplit lesdites conditions de création/destruction.
9) Unité de routage (3) d'un réseau de paquets supporté par un réseau de transport autorisant la création/suppression dynamique de liens de transport des paquets dudit réseau de paquets, ladite unité, en fonction d'une métrique affectée à chaque lien du réseau de paquets, déterminant le chemin le plus court entre ledit routeur d'extrémité de tête et le routeur d'extrémité de queue de la même connexion, et incluant une unité d'annonce (35) aux autres routeurs dudit réseau de la métrique affectée à chaque lien du réseau de paquets, ladite unité de routage (3) étant destinée à la mise en œuvre du procédé selon la revendication 1 à 4, caractérisée en ce qu'elle inclut une unité de gestion des adjacences réelles (31) associée à une table des adjacences réelles (33) et une unité de gestion virtuelles (32) associée à une table des adjacences virtuelles (34), ladite unité d'annonce (35) étant prévue pour annoncer aux autres routeurs dudit réseau les métriques contenues dans l'une et l'autre desdites tables (33 et 34).
PCT/FR2005/001513 2004-07-27 2005-06-17 Procede de controle de routage dans un reseau de paquets supporte par un reseau de transport Ceased WO2006021631A1 (fr)

Priority Applications (3)

Application Number Priority Date Filing Date Title
AT05778640T ATE520225T1 (de) 2004-07-27 2005-06-17 Verfahren zur routing-steuerung in einem durch ein transportnetzwerk gestütztem paketnetzwerk
US11/658,771 US7978687B2 (en) 2004-07-27 2005-06-17 Method for controlling routing in a packet network supported by a transport network
EP05778640A EP1771981B1 (fr) 2004-07-27 2005-06-17 Procede de controle de routage dans un reseau de paquets supporte par un reseau de transport

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
FR0408268 2004-07-27
FR0408268 2004-07-27

Publications (1)

Publication Number Publication Date
WO2006021631A1 true WO2006021631A1 (fr) 2006-03-02

Family

ID=34946753

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/FR2005/001513 Ceased WO2006021631A1 (fr) 2004-07-27 2005-06-17 Procede de controle de routage dans un reseau de paquets supporte par un reseau de transport

Country Status (4)

Country Link
US (1) US7978687B2 (fr)
EP (1) EP1771981B1 (fr)
AT (1) ATE520225T1 (fr)
WO (1) WO2006021631A1 (fr)

Families Citing this family (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US9525636B2 (en) * 2014-10-20 2016-12-20 Telefonaktiebolaget L M Ericsson (Publ) QoS on a virtual interface over multi-path transport
US10187292B2 (en) * 2016-04-15 2019-01-22 Microsoft Technology Licensing, Llc Data center topology having multiple classes of reliability

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6275470B1 (en) * 1999-06-18 2001-08-14 Digital Island, Inc. On-demand overlay routing for computer-based communication networks
WO2003019870A2 (fr) * 2001-08-24 2003-03-06 Peribit Networks, Inc. Procede et systeme efficaces permettant la decouverte et la verification automatiques d'itineraires optimaux a travers un reseau superpose maille multipoint dynamique
WO2004034653A1 (fr) * 2002-10-11 2004-04-22 Nokia Corporation Echange de trafic par tunnelisation dynamique avec optimisation des performances

Family Cites Families (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5854899A (en) * 1996-05-09 1998-12-29 Bay Networks, Inc. Method and apparatus for managing virtual circuits and routing packets in a network/subnetwork environment

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6275470B1 (en) * 1999-06-18 2001-08-14 Digital Island, Inc. On-demand overlay routing for computer-based communication networks
WO2003019870A2 (fr) * 2001-08-24 2003-03-06 Peribit Networks, Inc. Procede et systeme efficaces permettant la decouverte et la verification automatiques d'itineraires optimaux a travers un reseau superpose maille multipoint dynamique
WO2004034653A1 (fr) * 2002-10-11 2004-04-22 Nokia Corporation Echange de trafic par tunnelisation dynamique avec optimisation des performances

Non-Patent Citations (2)

* Cited by examiner, † Cited by third party
Title
GUERIN R A ET AL: "QoS routing mechanisms and OSPF extensions", GLOBAL TELECOMMUNICATIONS CONFERENCE, 1997. GLOBECOM '97., IEEE PHOENIX, AZ, USA 3-8 NOV. 1997, NEW YORK, NY, USA,IEEE, US, vol. 3, 3 November 1997 (1997-11-03), pages 1903 - 1908, XP010254897, ISBN: 0-7803-4198-8 *
LEE W C: "TOPOLOGY AGGREGATION FOR HIERARCHICAL ROUTING IN ATM NETWORKS", COMPUTER COMMUNICATION REVIEW, ASSOCIATION FOR COMPUTING MACHINERY. NEW YORK, US, vol. 25, no. 2, 1 April 1995 (1995-04-01), pages 82 - 92, XP000570739, ISSN: 0146-4833 *

Also Published As

Publication number Publication date
EP1771981B1 (fr) 2011-08-10
ATE520225T1 (de) 2011-08-15
EP1771981A1 (fr) 2007-04-11
US7978687B2 (en) 2011-07-12
US20090040943A1 (en) 2009-02-12

Similar Documents

Publication Publication Date Title
US8780697B2 (en) Bandwidth management for MPLS fast rerouting
Li et al. Efficient distributed restoration path selection for shared mesh restoration
WO2003071745A1 (fr) Methode dynamique et distribuee de protection locale d&#39;un chemin a commutation d&#39;etiquettes
Wang et al. Efficient distributed bandwidth management for MPLS fast reroute
WO2003071746A1 (fr) Methode de protection locale de chemins a commutation d&#39;etiquettes avec partage de ressources
FR2931604A1 (fr) Technique de protection dans un reseau de communication en mode connecte d&#39;un arbre primaire point a multipoint.
EP2345210B1 (fr) Gestion de topologie de routage dans un reseau
EP1432184B1 (fr) Dispositif de détermination de chemins de communication dans un réseau de communications à commutation d&#39;étiquettes, en présence d&#39;attributs de sélection
EP1252744B1 (fr) Procede d&#39;optimisation dynamique de la qualite de service dans un reseau de transmission de donnees
EP1650910B1 (fr) Contrôle des paramètres d&#39;une connexion Ethernet-GMPLS
EP1771981B1 (fr) Procede de controle de routage dans un reseau de paquets supporte par un reseau de transport
JP4373929B2 (ja) パス経路算出方法、パス経路算出装置、および、通信システム
EP1766899A1 (fr) Dispositif de gestion de ressources pour un reseau de communications a connexions inter-noeuds associees a des droits de preemption de ressources partagees et de priorite d&#39;acces aux ressources
EP1878172B1 (fr) Controle de la reservation de ressources partagees de chemins de connexion dans un reseau de communication a commutation d&#39;etiquettes de type &#34;non paquet&#34;
EP1821468B1 (fr) Dispositif d&#39;allocation de capacités de liens par prise en compte de répartition de charge pour un réseau de communication
EP3231137B1 (fr) Réseau superposé pour reseau de communication connectant des centres de données d&#39;un fournisseur de services en nuage
EP2235893B1 (fr) Technique pour protéger un chemin à commutation d&#39;étiquettes multipoint à multipoint en mode connecté lors d&#39;une panne affectant un noeud donné du chemin
FR2924556A1 (fr) Protection d&#39;un chemin a commutations d&#39;etiquettes primaire en mode connecte lors d&#39;une panne affectant un noeud donne dudit chemin dans un reseau de communication par commutation d&#39;etiquettes.
Shirazipour et al. End-to-end path computation schemes for traffic engineering in next generation multi-domain networks
Duarte Jr et al. GigaManP2P: an overlay network for distributed QoS management and resilient routing
Shirazipour End-to-End Path Computer Schemes for Traffic Engineering in Next Generation Multi-Domain Networks
FR2921534A1 (fr) Procede pour faire communiquer entre eux une pluralite de noeuds d&#39;extremite a travers un reseau de communication.

Legal Events

Date Code Title Description
AK Designated states

Kind code of ref document: A1

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 KM KP KR KZ LC LK LR LS LT LU LV MA MD MG MK MN MW MX MZ NA NG NI NO NZ OM PG PH PL PT RO RU SC SD SE SG SK SL SM 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: A1

Designated state(s): 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 IS IT LT 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
WWE Wipo information: entry into national phase

Ref document number: 2005778640

Country of ref document: EP

NENP Non-entry into the national phase

Ref country code: DE

WWP Wipo information: published in national office

Ref document number: 2005778640

Country of ref document: EP

WWE Wipo information: entry into national phase

Ref document number: 11658771

Country of ref document: US