Method and Network Element for Rerouting Traffic, While Maintaining the Quality of Service, in Networks with Slow Route Convergence

CROSS REFERENCE TO RELATED APPLICATIONS

0001This application is the US National Stage of International Application No. PCT/EP2005/053718, filed Jul. 29, 2005 and claims the benefit thereof. The International Application claims the benefits of German application No. 10 2004 037 024.9 DE filed Jul. 30, 2004, both of the applications are incorporated by reference herein in their entirety.

FIELD OF INVENTION

0002The invention relates to a method for defining a route for the routing of traffic and to a network element with means for executing such a method.

BACKGROUND OF INVENTION

0003A currently very topical field of activity in the area of networks and network technologies is the further development of data networks for the transmission of real-time traffic while maintaining quality-of-service features.

0004In future data networks, of which the most important representatives are IP (Internet Protocol) networks, are to support applications which include the transmission of voice, video and data streams in real time. A fast and reliable transport of data packets or IP packets must be guaranteed for such applications. For this purpose future IP networks—alongside the traditional “best effort” services for data transmission—should offer new transmission services which provide the necessary bandwidths from end to end and reliably transfer to the recipient IP packets with small, barely-fluctuating delay and very low packet loss rates (i.e. while maintaining quality-of-service features). These new services will be referred to below as QoS services (QoS: Quality of Service) and the traffic transported by them as QoS traffic.

0005Since the Internet is a combination of a growing number of individual IP networks, referred to as autonomous systems (AS), which are administered and controlled by different organizations, QoS services must be realized and made available in this internetwork to provide cross-network coverage. To achieve this end resource management systems which provide the resources necessary for the assured quality of service to the QoS traffic across the different networks are generally employed. For various reasons, such as traffic engineering and changes to networks and business relationships, cross-network traffic is frequently diverted on to new cross-network routes. The cross-network routing along routes from individual networks or autonomous systems is frequently also referred to as inter-domain routing.

0006The interaction of autonomous systems in the Internet, i.e. the cross-network forwarding of IP packets across the boundaries of individual IP networks, is controlled by the inter-domain routing protocol BGP (BGP: Border Gateway Protocol) (described in RFC1771). To this end adjacent border routers establish what are known as BGP peering sessions and exchange routing information via what are known as UPDATE messages. A network uses BGP to learn which IP addresses are accessible via which routes. Routes in this case are routes between networks at the level of autonomous systems and are encoded as sequences of AS (Autonomous System) numbers. Autonomous systems are assigned unique AS numbers for this purpose. If traffic is to be diverted onto a new route a border router announces a change in route by means of an UPDATE message (announcement of the new route, or withdrawal of an existing route, or both). This type of change in route is generally broadcast from network to network across many networks using further UPDATE messages. Networks further away generally receive a number of UPDATE messages via a number of routes and see different routes from which they select the best route from their standpoint. This means that a convergence process is started with the first UPDATE which has been measured as lasting around three minutes on average. During the convergence time the traffic affected is as a rule diverted numerous times to changing routes which means that significant delays of IP packets and high packet loss rates have to be expected.

0007Resource management systems and signaling protocols, such as BGRP (BGRP: Border Gateway Reservation Protocol) for example, are used for the provision and administration of the resources needed for QoS services. Resource Management reserves the necessary resources along the routes provided by the BGP protocol. A resource reservation must then follow the route changes initiated by the BGP protocol, i.e. when a route is changed a correspondingly changed reservation must be undertaken. This causes major problems, above all during the convergence time in which a network is looking for a new stable route from a number of routes. Routes selected in the interim are not immediately recognizable as intermediate solutions. If the route changes are followed rapidly by resource management then resources are reserved several times for the same traffic. If resource management waits for convergence the assured quality of service of the QoS traffic can be damaged in the long term.

SUMMARY OF INVENTION

0008An object of the invention is to specify an optimized method for defining routes while maintaining quality-of-service features.

0009The object is achieved by a method as claimed in the independent claims.

0010The invention is based on the idea, when defining a route, e.g. within the framework of a route change or a notification of a new route, of only announcing this route before it is put into service or activated after a delay, e.g. by making a corresponding entry in a routing table. In this case the announcement of the route preferably consists of communicating the future route. It is for example also possible to reference within the framework of the announcement a route already reserved as an alternate in order to bring about the activation of the route in this way.

0011The invention is primarily intended to overcome the problems which arise during the definition of inter-domain routes, e.g. by means of the BGP protocol, caused by the comparatively slow convergence during the determination or specification of new or changed routes. These slow convergence times are above all a problem in the transmission of real-time traffic. As part of the inventive method the route is first announced and is later activated after a time delay.

0012In the meantime a convergence in respect of the new or changed route can be undertaken, i.e. the optimum route in the sense of a metric is selected from a number of announced routes to the same destination and a resource reservation along this optimum route can be undertaken. In this way the necessary resources are available when the route is activated. The traffic to be transported, especially QoS traffic, can be diverted without any adverse effects. It is conceivable for the inventive method and the conventional procedures to be used in parallel, with the inventive method being employed if QoS traffic is involved.

0013Planned route changes, i.e. rerouting necessary because of line and node outages, can be executed with the inventive method without disturbing the assured quality of service for the QoS traffic. The method thus increases the availability of QoS services and simplifies resource management. The quality of service of QoS services in the planned rerouting of cross-network traffic streams can be safeguarded in this way. In particular this supports traffic engineering of cross-network traffic which even today is an increasingly significant practice among network operators.

0014Even if the invention is aimed primarily at remedying the problems arising in inter-domain routing in data networks, the inventive idea is not restricted to this case. It is immediately evident to the person skilled in the art that the inventive procedures can be employed in any communication networks in which problematic delays occur in the definition of new or modified routes. In particular the inventive method can also be employed in intra-domain routing if difficulties arise for similar reasons in respect of convergence times in the Intra-domain routing.

0015The event which causes the new route to be put into operation or activates the new route is preferably specified by the sending of a route activation message, also simply referred to as activation below. A network element which puts a new route into operation then receives two different messages delayed in relation to each other; one to announce the change of route, the second to activate this route change. The event which initiates the putting into operation could however also take another form, it being conceivable for example for a network element to start a timer or timers after receiving a route modification message and to initiate the putting into operation after this timer times out. A route activation message can be provided by an UPDATE message of the BGP protocol for example.

0016Resources are preferably reserved between the receipt of the route announcement message and the activation of the route. This resource reservation may possibly precede a selection of an optimum route. The reservation of resources for the new route (which may have been identified as the optimum one) can for example be implemented with the aid of a resource reservation message which is sent to a resource management entity. The address of this resource management entity can have been communicated by means of a route announcing message to the network element responsible for route definition. The resource management entities affected by resource reservations are localized in a preferred embodiment along the route to be defined. In this case a resource reservation message is transmitted from the network element along a route which was set up when the resource announcing message was processed, which corresponds to the new route in its course and allows reservation messages to be sent without affecting existing traffic. To this end the route is preferably created, when the resource announcing message is processed, with a prefix which is notified by the resource announcing message and contains an address of the resource manager in the system which has originally initiated the route announcing. A message can be propagated in this way along at the entire route, alternatively the routing entities lying on the new route for their part send resource reservation messages to assigned resource management entities to guarantee a resource reservation along the entire route. Since resource reservation messages can run in the opposite direction on the path from route announcing messages, the assignment of a resource management entity can easily be derived from the route announcement message.

0017In accordance with a further development of the object of the application a successful resource reservation can be confirmed to the network element responsible for defining the route. The activation of the route can be made dependent on the prior receipt of a confirmation of the reservation, i.e. the activation is not undertaken unless a confirmation for the resource reservation is available. Alternatively, if a route reservation fails, the arrival of the activation can be prevented, e.g. by a route activation message not being sent to the network element. Furthermore the activation can be made dependent on the resource manager specified in the route announcing messages receiving, as a reaction to its announcement, reservations for which the total resource requirements lie within one period of time.

0018The route announcing message preferably contains a code or attribute which identifies it as an announcing message. Information about the time of arrival of the event, e.g. the time of the sending of a route activation message, can be transferred with this announcing message. This information can consist both of a time difference between the announcing message and the event triggering the activation, and also of an absolute point in time of the planned arrival of the event of the activation. In the latter case it is desirable to synchronize the clocks of the sender of the message and the recipient, i.e. the network element, which for example can be achieved using the NTP (Network Time Protocol) protocol (described in RFC1305). The route announcing message can essentially take the form of a BGP UPDATE message, in which case it is modified in relation to conventional UPDATE messages at least to the extent that it should include a code identifying it as an announcing message. It can comprise information about the arrival of the time and an address of a resource management entity responsible, which also represents an expansion with respect to conventional UPDATE messages.

0019The inventive method then executes as follows in a preferred embodiment realized by means of UPDATE messages. Advance announcements of route changes are triggered by traffic engineering and other planned traffic diversions. If in future current traffic is to reach an autonomous system A via another border router R<b>2</b> instead of via a border router R<b>1</b>, i.e. is to be routed via new paths, then the border router R<b>2</b> to be used in the future sends a BGP UPDATE message in the conventional manner to the neighbors involved. By contrast with the previous execution sequence however, it sends an UPDATE message U<b>1</b> with an advance announcement of the new route. Later, at an announced time, R<b>2</b> sends a second regular UPDATE message U<b>2</b> with the new route announced in U<b>1</b>. The UPDATE message U<b>1</b> announces U<b>2</b> and gives the networks involved the opportunity, without disturbing current traffic, of running through the convergence process beforehand, reserving the required resources on the new convergent route and diverting the traffic involved with the propagation of U<b>2</b> without any problems in one step onto a prepared route. To this end new attributes are inserted into UPDATE messages in accordance with RFC 1771: for the identification of announcements, for the notification of the transmit time of U<b>2</b> and for the notification of the address of a resource manager in A to which reservations for the announced route are to be sent. Like a regular UPDATE message, an announcement also contains a route consisting of a prefix P, a route R encoded in a list of AS numbers and attributes. The prefix P, route R and attributes are identical to those in U<b>2</b>.

0020Possible variants of this preferred embodiment are: The border router R<b>2</b> could send an announcement U<b>1</b> without specifying the time of the planned sending of the actual UPDATE message U<b>2</b> and simply wait for an appropriate length of time before U<b>2</b> is sent (estimates about distribution of the route lengths) and a reacting AS could likewise wait for an appropriate period of time for the signaling for resource reservation (estimates about distribution of the route lengths). Alternatively U<b>1</b> could contain a time interval instead of a point in time which is adapted from border router to border router (deduction of forwarding and processing time) and which displays the remaining time until U<b>2</b> is sent out. As an optional improvement the UPDATE U<b>2</b> can contain a reference to U<b>1</b> and facilitate the linkage with the announced route change.

0021The object of the invention also includes a network element with means for executing a method in the sense of the inventive procedure.

BRIEF DESCRIPTION OF THE DRAWINGS

0022The invention is explained in greater detail below within the context of an exemplary embodiment with reference to Figures. The figures show:

0023<figref idref="DRAWINGS">FIG. 1</figref>: a section of an internetwork which is formed by autonomous systems (AS).

0024<figref idref="DRAWINGS">FIG. 2</figref> and <figref idref="DRAWINGS">FIG. 3</figref>: a flowchart for executing an inventive method.

DETAILED DESCRIPTION OF INVENTION

0025Within the framework of the exemplary embodiment, route changes during inter-domain routing are announced by means of the BGP protocol with a new form of UPDATE messages. The actual route changes are then undertaken delayed by a few minutes in time from the announcement, this being able to be undertaken in the way provided for in conventional methods in the BGP protocol. The time delay is selected so that an optimum route is determined as a rule before the route change and a resource reservation can be undertaken. Since an average convergence process in inter-domain routing takes about 3 minutes, a time delay of a few minutes makes sense. This enables the convergence phase and the resource reservation for QoS traffic to be given priority in the period of time between the announcement and the actual rerouting. The rerouting is only delayed in relation to the announcement if the convergent route is already known and the resources needed have already been provided. Route announcements are transported by means of UPDATE messages and undergo the same convergence process as regular UPDATE messages, however do not change the traffic flow but initiate the determination of the later convergent route.

0026In accordance with the invention new attributes are used in BGP UPDATE messages, with which a route change can be announced in advance with an UPDATE message U<b>1</b> (this route announcing message is also referred to as an announcement below). I.e. the attributes identify the UPDATE message as an announcement of a route change. Then, at an end time given in the announcement U<b>1</b> (in the order of magnitude of minutes after the sending of U<b>1</b>), as provided for within the framework of the BGP protocol, the rerouting is initiated with a regular second UPDATE message U<b>2</b>. In the usual way the UPDATE message U<b>2</b> contains the prefixes which can be reached and the AS path, i.e. the IP addresses of the accessible systems and the list of the autonomous systems leading to the destination. The UPDATE message U<b>1</b> which is used as the announcement contains the same information as U<b>2</b> and additional specifications: an indicator that an announcement of an incoming new route is involved, the time at which actual route change is to be initiated with the second UPDATE message U<b>2</b> and also the address of a resource manager responsible for the resource reservations. In the example this resource manager is localized in the autonomous system which originally announces the route change with the UPDATE message U<b>1</b>. This resource manager is localized in the example given in <figref idref="DRAWINGS">FIG. 1</figref> at the border router R<b>12</b>. A resource manager can for example be implemented with the aid of software by processes which run on a router or on an independent hardware platform. A central resource management is also possible.

0027The announcement U<b>1</b> and all announcements derived from it in the subsequent course of execution undergo the usual selection processes at each border router, e.g. filter for incoming UPDATEs, selection of the best route (‘best path selection’) and filter for outgoing UPDATEs which decides on the route selection and forwarding, without however changing the existing routing of the traffic affected by the activation of the announced route. In accordance with the BGP protocol a maximum of one route to each destination—the best route—is forwarded to neighboring nodes. This restriction does not influence the forwarding of announced routes. Announced routes, once they have successfully passed through the selection process and are also modified like similar regular routes, are forwarded to all neighbors, as are the routes later initiated or activated by the UPDATE message U<b>2</b>. Announcements however do not influence the current best route of the traffic involved used for routing, especially do not change the corresponding entry in routing tables (FIB (forwarding information base)) and do not replace any routes learned via regular UPDATE messages. Like the UPDATE message U<b>2</b> later, the announcement U<b>1</b> thus triggers convergence processes. A remote autonomous system B, which will later react to U<b>2</b> and will divert QoS traffic, undergoes a convergence process and already learns the routes available later and especially the convergent routes to be selected later, onto which the traffic will then be diverted. After an appropriate period of time and before the time at which U<b>2</b> is sent which is known from the announcements, the autonomous system B reserves the resources needed for the diversion of the traffic involved on the convergent, best future route learned from the announcements. For this a corresponding signaling message is sent to the resource manager of the autonomous system A named in the announcement U<b>1</b>. To make this possible, all autonomous systems involved in the forwarding of the announced routes have created a route with a suitable prefix of the IP address of the resource manager. This means that the signaling message to the resource manager in the autonomous system A is generally already being sent over the new best path. If the UPDATE message U<b>2</b> is then sent at the announced time, all autonomous systems react as previously, i.e. implementing routing for the traffic involved along the new route. Those autonomous systems which already know from the announcement phase that they are diverting traffic onto a new route wait for the arrival of the already known convergent route. Only then do they modify their routing tables (FIBs: forwarding information bases) and forward a corresponding UPDATE message.

0028<figref idref="DRAWINGS">FIG. 1</figref> shows seven autonomous systems AS<b>1</b>, AS<b>2</b>, . . . , AS<b>7</b>. Two networks, network N<b>1</b> and network N<b>2</b>, are connected to AS<b>1</b>. In network N<b>1</b> the end systems can be reached with the IP addresses in the address block 10.10.10.0/24, i.e. 10.10.10.0 through 10.10.10.255, in network N<b>2</b> the end systems can be reached with the addresses in the address block 10.10.11.0/24, i.e. 10.10.11.0 through 10.10.11.255. In this case 10.10.10.0/24 specifies an IP address, 10.10.10.0, and a mask length, <b>24</b>, and stands for all IP addresses which match the specified address 10.10.10.0 in the first 24 bits (mask length), i.e. 10.10.10.0 through 10.10.10.255. Only some of the routers involved are shown in <figref idref="DRAWINGS">FIG. 1</figref>, the border routers via which the autonomous systems are connected to each other: R<b>11</b>, R<b>12</b>, R<b>21</b>, R<b>22</b>, R<b>31</b>, R<b>32</b>, R<b>33</b>, R<b>41</b>, R<b>42</b>, R<b>51</b>, R<b>52</b>, R<b>61</b>, R<b>62</b>, R<b>71</b> and R<b>72</b>. Also only partly shown are the components responsible for resource management. As indicated by the typical resource managers RM<b>11</b>, RM<b>12</b>, RM<b>61</b> and RM<b>62</b> each border router is especially assigned a resource manager here.

0029Routes are shown in this example in the form (P, a<b>1</b>, a<b>2</b>, . . . , aN). In this case the prefix P describes the address block with the reachable destination addresses and the following sequence a<b>1</b>, a<b>2</b>, . . . , aN the sequence of the autonomous systems to be passed through via which the traffic reaches the destination addresses from P. For example (10.10.10.0/23, 4, 2, 1) is a route from the autonomous system AS<b>6</b>. It leads with the address block 10.10.10.0/23 to the networks N<b>1</b> and N<b>2</b>. The character sequence <b>4</b>, <b>2</b>, <b>1</b> stands for the sequence of the autonomous systems: AS<b>4</b>, AS<b>2</b>, AS<b>1</b> which forward the traffic from the autonomous system AS<b>6</b> to the networks N<b>1</b> and N<b>2</b>.

0030Assuming that autonomous system AS<b>6</b> uses the route (10.10.10.0/23, 4, 2, 1) for the traffic to the destination networks N<b>1</b> and N<b>2</b>, the load on the connection between the routers R<b>21</b> and R<b>11</b> is approaching the capacity limit and the autonomous system AS<b>1</b> would like to divert a part of the traffic onto other routes. It is further assumed that the autonomous system AS<b>1</b> decides to divert the traffic to network N<b>2</b> on routes via R<b>12</b>.

0031According to the previous method, that is within the framework of the BGP protocol, without the new inventive method, the router R<b>11</b> would restrict the destination addresses which can be accessed via it with an UPDATE message to 10.10.10.0/24 and notify the router R<b>12</b> with an UPDATE message about the accessibility 10.10.11.0/24. This would initiate a convergence process generally lasting three minutes on average, during which the quality-of-service for traffic streams from the autonomous system AS<b>6</b> to the networks N<b>1</b> and N<b>2</b> suffers considerably and possibly during the convergence process resources are reserved in number of times on different paths between the autonomous systems AS<b>6</b> and AS<b>1</b>.

0032In accordance with the new inventive method the router R<b>12</b> sends an UPDATE message U<b>1</b> to the router R<b>31</b> which contains an announcement of the route (10.10.11.0/24, 1). U<b>1</b> could contain the fact that this route will be notified as a binding route in 10 minutes with a further UPDATE message. AS<b>3</b> propagates the announced route as (10.10.11.0/24, 3, 1) to routers R<b>41</b>, R<b>51</b> and R<b>71</b>. The autonomous system AS<b>4</b> propagates the announced route as (10.10.11.0/24, 4, 3, 1) to the autonomous system AS<b>6</b> although the router R<b>42</b> has already forwarded (10.10.10.0/23, 4, 3, 1) to router R<b>61</b>. The convergence phase is completed in this example when (10.10.11.0/24, 4, 3, 1) via router R<b>42</b>, (10.10.11.0/24, 5, 3, 1) via router R<b>52</b> and (10.10.11.0/24, 7, 3, 1) via router R<b>72</b> have arrived in the autonomous system AS<b>6</b> and the autonomous system AS<b>6</b> has selected what it sees as the best route. It is assumed here that the autonomous system AS<b>6</b> decides on (10.10.11.0/24, 5, 3, 1), e.g. because this is the optimum route in the sense of a metric. With the announced routes the autonomous system AS<b>6</b> also finds out about the switchover time intended by the autonomous system AS<b>1</b>. Taking into account the fact that the clocks of the autonomous systems AS<b>1</b> and AS<b>6</b> are not running synchronously, the autonomous system AS<b>6</b> will inform its resource management in good time about its choice of route and cause the resource manager RM<b>62</b> to signal the required resources on the selected future route to the resource manager RM<b>12</b>. This means that the new route is defined and the required resources are already provided when router R<b>12</b> sends at the announced time a further UPDATE message U<b>2</b> with the route (10.10.11.0/24, 1) to router R<b>31</b>, this time as a regular UPDATE message. In a sequence which cannot be defined beforehand, triggered by the U<b>2</b> UPDATE, messages with the routes (10.10.11.0/24, 4, 3, 1), (10.10.11.0/24, 5, 3, 1) and (10.10.11.0/24, 7, 3, 1) will arrive at the autonomous system AS<b>6</b>. The autonomous system AS<b>6</b> already knows the new convergent route and will now wait until such time as the UPDATE message with the route (10.10.11.0/24, 5, 3, 1) arrives. The autonomous system AS<b>6</b> will then adapt its routing and put the traffic to N<b>2</b> on to a new path which is already available as an end-to-end path at this point, represents the convergence state and provides the necessary resources. Without significant adverse effects on the quality of service this diverts the traffic to the new route (except for possible overlaps of traffic on the new link and traffic still running on the old link which has not yet reached its destination at the time of the rerouting). Subsequently the resource manager RM<b>61</b> will adapt the resources reserved on the old route via the autonomous systems AS<b>4</b>, AS<b>2</b> and AS<b>1</b>, i.e. release the resources no longer needed because of the traffic diversion.

0033The autonomous system AS<b>6</b> proceeds in this case according to the flowchart shown in <figref idref="DRAWINGS">FIG. 2</figref> and <figref idref="DRAWINGS">FIG. 3</figref>. For the sake of simplification it is assumed here that an UPDATE only contains an announced route R with prefix P (step <b>101</b>). An expansion for UPDATE messages which announces a number of routes is of no importance to the person skilled and the art. Steps <b>102</b>, <b>104</b>, <b>105</b>, <b>107</b>, <b>108</b> and <b>109</b> correspond to the processing of announced routes described in RFC1771. In step <b>106</b> route announcements are filtered out in this sequence which in future describe the best routes and are stored in a new database for announced routes, Pen-RIB (Pen stands for Pending), (step <b>123</b>), if R is the first such route announcement for the prefix P (not entered in Pen-RIB) a timer is started (step <b>121</b> and <b>122</b>). A route R* is generated from the route announcement R which is identical to R except for the prefix P* (step <b>124</b>). P* is the prefix of the resource manager responsible for reservations on the announced route with the prefix R, in the example a prefix for an address of RM<b>12</b> in AS<b>1</b>. R* is now entered in Loc-RIB and activated instead of the route announcement (step <b>125</b>).

0034Announced routes which are expected as a result of the route announcements entered in Pen-RIB are filtered out in step <b>103</b> and given special treatment. They are entered in the database Pen-RIB (step <b>131</b>). With the first such entry a timer is started (step <b>132</b> and <b>133</b>). If the route R corresponds to the new best route contained in the Pen-RIB, all routes buffered in the Pen-RIB for the prefix P are processed and all entries for the prefix P in Pen-RIB deleted (step <b>134</b>, <b>135</b> and <b>136</b>). The processing in step <b>135</b> corresponds to that of steps <b>104</b>, <b>105</b>, <b>107</b>, <b>108</b> and <b>109</b>.

0035If a timer set in step <b>122</b> times out (step <b>201</b>) the resource management is informed about an impending change of route in order to initiate a corresponding resource reservation (step <b>202</b>). If a timer set in step <b>133</b> times out (step <b>301</b>) it is assumed that the new best route stored in Pen-RIB is no longer valid. A check is made as to whether there are entries for the prefix P in Pen-RIB (step <b>302</b>). If there are, all the routes buffered for prefix P in Pen-RIB are processed (step <b>303</b>) and deleted in Pen-RIB (step <b>304</b>). Furthermore the resource management is informed about the change (step <b>305</b>).

0036If it is to be assumed that route changes initiated by a number of autonomous systems for the same prefix must be held in Pen-RIB, the entries in Pen-RIB must be made according to prefix and an identification of the sender of the original announcement (AS<b>1</b> or router R<b>12</b> in the example) must be provided. To this end route change messages must where necessary also provide a suitable value for this identification, e.g. an AS number or a IP address of a border router.