Inter-domain traffic engineering

[0001] This non-provisional patent application claims priority based upon the prior U.S. provisional patent applications entitled “Inter-domain traffic engineering in the Internet”, application No. 60/634,276, filed Dec. 9, 2004, in the name of Meral Shirazipour, Yves Lemieux and Samuel Pierre.

[0002] 1. Field of the Invention

[0003] The present invention relates to Quality of Service (QoS) for packet traffic and, more particularly, to QoS guarantee for packet traffic transiting through more than one sub network also referred to as Autonomous System (AS).

[0004] 2. Description of the Related Art

[0005] At the moment there is a trend toward all-Internet Protocol (IP) communication. However, IP has been based on a best effort paradigm by which traffic is served in a first-in first-out (FIFO) manner. The problem comes from the fact that time-affected services require a minimal quality of service (QoS) guarantee. Many solutions were developed to address the problem. In the end, it all aims at getting the best performance from the network while optimizing its resource utilization. That is often referred to as traffic engineering. Most traffic engineering techniques are based on the assumption that the engineered traffic will remain within one or few networks under a common administration. However, research shows that most time-affected services usually span across two to eight autonomous systems (AS). This implies that traffic engineering techniques need to support the traffic across more than one AS.

[0006] Unfortunately, little work has been done in the inter-AS or inter-domain traffic engineering field. Many techniques rely on the use of Border Gateway Protocol (BGP), which is the inter-domain routing protocol used in IP networks. BGP is defined at length by the Internet Engineering Task Force (IETF) under the Request For Comment (RFC) number 1771 and 1772, which is herein included by reference. The current inter-domain traffic engineering techniques make use of common BGP path attributes to prefer some inter-domain routes to others. However, these techniques do not provide sufficient reliability to support time-affected services, which require a QoS guarantee not only from each of the traversed AS, but also on an overall end-to-end perspective. Moreover, some further aspects of an acceptable solution are not present in the current inter-domain traffic engineering techniques. For instance, there is a lack granularity that prevents per flow discrimination of QoS.

[0007] As can be appreciated, the current inter-domain traffic engineering techniques fall short at providing a QoS reservation and packet forwarding solution that would fulfill the needs of time-affected services that are provided over multiple AS.

[0008] A first aspect of the invention is directed to a method for forwarding packets from a first router in a first domain to a second router in a second domain. The first and second domains are connected via a series of further routers. The method comprises the steps of receiving, at the first router, a packet addressed to a node reachable via the second router and detecting, at the first router, that an inter-domain QoS reservation is needed. Thereafter, the method follows with step of sending, at the first router, a request message to setup the inter-domain QoS reservation toward the second router. Following reception, at the first router, of an acknowledgment message to confirm that the inter-domain QoS reservation is setup, the method follows with a step of reserving, at the first router, resources in accordance with the inter-domain QoS reservation. The method then continues with a step of encapsulating toward the second router, at the first router, the packet in accordance with the inter-domain QoS reservation by adding a first label to the packet, the first label indicating that the packet is not for delivery in the first domain.

[0009] Optionally, the method could comprise a step of encapsulating toward the second router, at the first router, the first label and the packet by adding a second label thereto, wherein the second label enables proper routing of the thereby encapsulated packet within the first domain.

[0010] The step of reserving could further be performed before the step of sending.

[0011] Another optional behavior of the invention suggests that the step of encapsulating further comprises setting the value of the first label to a value indicating that the packet is not for delivery in the first domain and that the packet is currently transiting between the first domain and a further domain, the further domain being one of the second domain or another domain.

[0012] Yet another optional behavior of the invention suggests that the step of encapsulating further comprises setting the value of the first label to a value indicating that the packet is not for delivery in the first domain and that the packet is currently transiting within the first domain.

[0013] A second aspect of the invention is directed to a method for forwarding packets from a first router in a first domain to a second router in a second domain. The first and second domains being connected via a plurality of further routers. The method comprises the steps of receiving, at a specific router of the plurality of routers, a request message to setup an inter-domain QoS reservation toward the second router. The specific router is in a further domain and the further domain is a member of a group consisting of the first domain, the second domain and another domain. The method then follows with the step of forwarding, at the specific router, the request message to setup the inter-domain QoS reservation toward the second router. Thereafter, the method continues by receiving, at the specific router, an acknowledgment message to confirm that the inter-domain QoS reservation is setup and reserving, at the specific router, resources in accordance with the inter-domain QoS reservation. Then, the following steps are performed for forwarding the acknowledgment message toward the first router, receiving, at the specific router, a packet related to the inter-domain QoS reservation and encapsulating toward the second router, at the specific router, the packet in accordance with the inter-domain QoS reservation by adding a first label to the packet, the first label indicating that the packet is not for delivery in the further domain.

[0014] Optionally, the method could comprise a step of encapsulating toward the second router, at the specific router, the first label and the packet by adding a second label thereto, wherein the second label enables proper routing of the thereby encapsulated packet within the further domain.

[0015] The step of reserving could further be performed before the step of forwarding.

[0016] An option also suggests that the step of encapsulating further comprises setting the value of the first label to a value indicating that the packet is not for delivery in the further domain and that the packet is currently transiting between the further domain and an other domain, the other domain being one of the second domain or another domain.

[0017] Yet another optional behavior of the invention suggests that the step of encapsulating further comprises setting the value of the first label to a value indicating that the packet is not for delivery in the further domain and that the packet is currently transiting within the further domain.

[0018] A third aspect of the invention is directed to a router in a current domain. The router comprises an input-output means for receiving and sending packets and messages, a routing module for performing regular routing tasks of the router and a reservation module. The reservation module receives a request message, via the input-output means, addressed from a first router to setup an inter-domain QoS reservation toward a second router, the second router being in a further domain, forwards toward the second router the request message to setup the inter-domain QoS reservation, receives an acknowledgment message to confirm that the inter-domain QoS reservation is setup, reserves resources in accordance with the inter-domain QoS reservation, forwards the acknowledgment message toward the first router, receives a packet related to the inter-domain QoS reservation and encapsulates toward the second router the packet in accordance with the inter-domain QoS reservation by adding a first label to the packet, the first label indicating that the packet is not for delivery in the current domain.

[0019] Optionally, the reservation module of the router could further encapsulate toward the second router the first label and the packet by adding a second label thereto, wherein the second label enables proper routing of the thereby encapsulated packet within the current domain.

[0020] Yet another option is for the reservation module of the router to further receive a packet addressed to a node reachable via a third router, detecting that an inter-domain QoS reservation is needed and sending a further request message to setup the inter-domain QoS reservation toward the third router.

[0027] Multi-Protocol Label Switching (MPLS) is currently used in various network configurations in order to provide a simple and efficient forwarding mechanism in packet switched networks. One main feature of MPLS is to associate all packets related to a single communication on a specific path by using a specific label. Once the path is established using a Resource ReserVation Protocol (RSVP), MPLS enabled-routers then simply have to forward all packets in accordance with their respective label. A complete overview of MPLS and RSVP can be obtained at the IETF under the RFC number 3031 for MPLS and 2205, 2750 and 3209 for RSVP, all of which are herein included by reference. However, MPLS as known today can only be deployed inside a uniquely administrated network or Autonomous System (AS) since the label attribution mechanism would otherwise be inefficient.

[0028] The present invention can extend MPLS to enable inter-AS deployment of Label Switched Paths (LSP). In the MPLS context, the present invention uses the capability of MPLS to support label stacking. Some specific label values are stacked with usual label values. Since the specific label values are known to all routers to serve the inter-domain functionality, they are used, within a current AS, to signal that a related LSP is an inter-AS LSP and to signal that the inter-AS LSP is transiting through the current AS or transiting between two ASs. The present invention can further extend RSVP in order to support deployment of the inter-AS LSP.

[0029] While the invention could be seen from the angle of MPLS, it could also be seen from a more general perspective. The following description is made generic and the reader is invited to refer to MPLS as one example of current technologies that could be adapted to support the present invention. Furthermore, necessary adaptations to MPLS could be mentioned, but are not necessarily mentioned within the following description.

[0030] Similarly, the packet traffic transported on an inter-AS path is likely to be IP packet traffic. However, the present invention is not limited to the transportation of IP packets on the inter-AS path. Therefore, the following description is made generic and the reader is invited to refer to IP packets as one example of packets that could be transported on the inter-AS path of the present invention. Time affected services making use of the inter-AS path of the present invention are, consequently, likely to be IP services such as Voice over IP (VoIP), but could also be any other type of services.

[0031] Reference is now made to the drawings where FIG. 1 shows a block diagram of exemplary packet 200 encapsulations in accordance with the teachings of the present invention. The packet 200 represents any type of packet before any treatment related to the present invention. The packet 200 can represent raw data taken directly from an application, by is likely to represent an already encapsulated form of the application's data. This falls outside the scope of the present invention, which is not limited to any specific layer with reference to the Open Systems Interconnect (OSI) network model.

[0032] A first encapsulation example 210 potentially used by the present invention is a conventional label encapsulation of the packet 200 using MPLS. A label 212 is added to the packet 200. The packet 200 encapsulated with the label 212 is understood only within a specific AS, as specified by MPLS.

[0033] A second example 220 potentially used by the present invention is an intra-domain label encapsulation of the packet 200. The packet 200 is encapsulated with a first label 222. The first label 222 has a known value informing involved routers that the packet 200 thereby encapsulated relates to inter-domain traffic and that the packet 200 is currently transiting within an AS (by opposition to transiting between two ASs). In other words, the packet 200 when encapsulated with the first label 222 is not for delivery in the AS, but is transiting within a given domain toward a further domain. The packet 200 and the first label 222 are further encapsulated with a second label 224 to indicate how the packet 200 is to be treated at this given position within the AS. In the context of MPLS, the first label 222 could conveniently be set to 4 since it is a reserved value not yet used in conventional MPLS.

[0034] A third example 230 potentially used by the present invention is an inter-domain label encapsulation of the packet 200. The packet 200 is encapsulated with a first label 232. The first label 232 has a known value informing involved routers that the packet 200 thereby encapsulated relates to inter-domain traffic and that the packet 200 is currently transiting between a first AS and a second AS (by opposition to transiting within an AS). In other words, the packet 200 when encapsulated with the first label 232 is not for delivery in the first AS, but is transiting between the two domains. The packet 200 and the first label 232 are further encapsulated with a second label 234 to indicate how the packet 200 is to be treated at this given position between the two ASs. In the context of MPLS, the first label 232 could conveniently be set to 5 since it is a reserved value not yet used in conventional MPLS. In some implementations, a single value could also be used to indicate that the packet is related to an inter-domain QoS reservation. However, this will prevent the ASs to distinguish between intra-domain traffic and inter-domain traffic, which could be desirable to fine-tune the QoS assignment within a given AS. Furthermore, having different values for inter and intra domain labels provides a wider range of available values.

[0035] FIG. 2 shows an exemplary network 100 topology in accordance with the teachings of the present invention. FIG. 2 shows a three Autonomous Systems AS1 110, AS2 120 and AS3 130. Only routers are shown interconnected in the AS1 110, the AS2 120 and the AS3 130 since the teachings of the present invention are mainly aimed at improving those, but it should be understood that the ASs are likely to contain further nodes, which make use of the routing capabilities provided by the various routers (further nodes such as terminating nodes, service nodes, database nodes, etc.). The AS1 110 comprises four routers R11 111, R12 112, R13 113 and R14 114. The AS2 120 comprises five routers R21 121, R22 122, R23 123, R24 124 and R25 125. The AS3 130 comprises four routers R31 131, R32 132, R33 133 and R34 134. Various links are further shown connecting the routers in their respective AS. The R14 114 in the AS1 110 is further connected to the R21 121 of the AS2 120 and the R25 125 in the AS2 120 is further connected to the R33 133 of the AS3 130. The R14 114, the R21 121, the R25 125 and the R33 133 are usually referred to as border routers since they enable connection of their respective AS toward other systems (e.g. other AS, third party service provider, single node, etc.).

[0036] Reference is now concurrently made to FIG. 2 and FIG. 3, which shows an exemplary nodal operation and flow chart of an inter-domain path setup in accordance with the teachings of the present invention.

[0037] In the shown example, the R11 111 of the AS1 110 receives packets addressed to a destination that the R34 134 is best positioned to reach (e.g. using information provided through a routing protocol such as BGP. BGP could also provide the information on the destination AS (i.e. the AS3 130). Once it is determined that the R34 134 is not in the AS1 110, the R11 111 sends a request message 310 addressed to the R34 134. The message is forwarded along the way up to the R34 134. The request message 310 contains the address of the R11 111 (as its source address) and contains sufficient indication for the R34 134 to understand that an inter-domain QoS reservation of resources needs to take place. In the context of MPLS, the request message 310 could be a modified RSVP Path message having the following structure [AS3, Destination_address, Label_Request]. As an optional behavior, it is possible for the R11 111 to establish the inter-domain QoS reservation with the first router available within the AS3 130 instead of the last router, as shown. That leaves the matter of routing the traffic within the final AS to the AS itself.

[0038] Upon reception of the request message 310, the R34 134 replies with an acknowledgment message 320. The acknowledgement message 320 is forwarded back to the source of the request message 310 (i.e. the R11 111 in the present example). The acknowledgment message 320 contains information necessary to reserve the resources along the way between the two routers R11 111 and R34 134. In the present example, the acknowledgement message 320 specifies label values to be used (following rules exemplified in FIG. 1). The first labels should clearly identify the traffic as being related to inter-domain QoS reservations. This means that all routers compatible with the present invention need to understand the chosen values. The determination of the actual values of the second labels is outside the scope of the present example. The determined values of the second labels should enable proper routing of the packets between the R11 111 and the R34 134, on a hop-by-hop basis. It should also be noted that any given router should be able to support multiple QoS reservations for different sources and destinations. In the context of MPLS, the acknowledgment message 320 could be a modified RSVP reservation or RESV message. Examples of each individual RESV messages are shown under the corresponding arrow on FIG. 3. Upon reception of the acknowledgment message 320, the R11 111 knows that proper QoS reservation has occurred toward the R34 134 and that it is now possible to sends packets to the R34 134 using the label values from the acknowledgment message. Alternatively, the request message 310 could contain the label values, which would be confirmed by the acknowledgment message 320.

[0039] The following table contains example of the label values used in the example of FIG. 3:

[0040]

	Before R11	→
	R11	→
	R12	→
	R14	→
	R21	→
	R22	→
	R25	→
	R33	→
	R34	→

[0041] The QoS reservation resulting of the procedure shown on FIG. 3 is shown on FIG. 2 by the dotted line 140 between the R11 111 and the R 34 134.

[0042] FIG. 4 shows a flow chart of the algorithm used by a router of a current AS to setup QoS reservations and forward packets in accordance with the teachings of the present invention. FIG. 4 shows a first alternative in which the router receives packets to be sent in a further AS 410A. The destination address is usually sufficient to indicate that the packets are to be sent to the further AS. Thereafter, the router detects that an inter-domain QoS reservation is needed 420 (e.g. based on policies maintained in the AS). The router can, optionally (as shown by the dashed box), already reserve resources in accordance with the determination of step 420. The router then sends a request message 440 to setup proper QoS reservation to a further router (either inside or outside the current AS). As mentioned before, the request message sent in 440 contains sufficient information for the receiver to understand that an inter-domain QoS reservation of resources needs to take place. The router then either receives and acknowledgment message 450A or an error message 450B. In the case of the acknowledgment message (450A), the router can then reserve resources 460 in accordance with the content of the acknowledgement message itself or with the information known from the request message of step 440. However, the QoS reservation 460 does not occur if it already took place before (e.g. step 430). The packets received thereafter related to the established QoS reservation 460B (determined by the source and destination addresses) are encapsulated and treated in accordance with the QoS reservations 470. If the received message is, however, an error message 450B (e.g. since a router does not support the invention), the router can forward the error message or send a new error message to the source of the message 480 or could also change, e.g., the destination address 490 of the request message to try to avoid the source of error. The router then goes back to step 440 for sending the newly built request message. A second alternative of the invention occurs when the router directly receives a request message 410B instead of packets as in 410A. The router then continues with steps 430 as shown above.

[0043] FIG. 5 shows a modular representation of a router 500 in accordance with the teachings of the present invention. The router 500 has at least one input-output port or means 510 and 510′ for receiving and sending packets. The router comprises a reservation module 520 comprising means for conducting the logic presented above, for instance, in FIG. 4. The router further comprises a routing module 530 for performing regular tasks of a typical router. The routing module 530 could interact with the reservation module 520 and vice-versa. This could be helpful, as mentioned above, in the determination of the location of destination within or outside a current AS in which the router resides. Not shown on FIG. 5 is the underlying hardware architecture (e.g. memory, processor, etc.) of the router 500 since it does not affect the teachings of the present invention,

[0044] Although several examples of the present invention have been illustrated in the accompanying drawings and described in the foregoing description, it will be understood that the invention is not limited to the embodiments disclosed, but is capable of numerous rearrangements, modifications and substitutions without departing from the teachings of the present invention. In general, statements made in the description of the present invention do not necessarily limit any of the various claimed aspects of the present invention. Moreover, some statements may apply to some inventive features but not to others. In the drawings, like or similar elements are designated with identical reference numerals throughout the several views, and the various elements depicted are not necessarily drawn to scale.