Abstract:
Disclosed is a method and apparatus for provisioning a label switched path (LSP) between two endpoints executing a first set of MPLS functions. The method and apparatus associates a first node with the first endpoint and a second node with the second endpoint. The first node is designated as the source. Both the first and second nodes execute a second set of MPLS functions, wherein the second set of MPLS functions include the first set of MPLS functions and additional MPLS functions. As the source, the first node provisions a first MPLS path (i.e., LSP) between itself and the first endpoint. The first node then provisions a second MPLS path (i.e., LSP) between the first node and the second node. The first node then transmits a message to the second node instructing the second node to provision a third MPLS path between the second node and the second endpoint. The three MPLS paths are bridged at the first and second nodes to complete the LSP between the two endpoints.

Description:
BACKGROUND OF THE INVENTION 
     The present invention relates generally to networks, and more particularly to provisioning a label switched path (LSP) across two or more networks. 
     In order to provide customers with the ability to communicate between two independent locations, a Communications Network Provider or an Internet Service Provider (ISP) typically has to combine multiple circuit segments of one or more networks into a single communication path. In more detail, each circuit segment may only span a portion of the single communication path. Sometimes, the devices (switches, routers) in the different networks can communicate with each other in order to set up the entire communication path. In other instances, however, devices in different segments of different networks cannot communicate with each other because either they communicate using different protocols or one node cannot handle the complexity of the communication protocol used by another node. 
     One communication protocol often used to facilitate communication within a network and across networks is the Multiprotocol Label Switching (MPLS) protocol. MPLS enables the provisioning of virtual circuits, or label switched paths (LSPs), across IP networks. Variants of MPLS or similar protocols have also been used in Optical and ATM networks as well. In particular, MPLS involves setting up a specific path for a given sequence of packets. The path is identified by a label in each packet. Routers use the label to direct a packet to its next hop until it reaches its destination. This label saves a router the time conventionally needed to look up the destination IP address in each packet and forward the packet based on this IP address. The label is swapped with a different label at each hop. Often, multiple labels are used. Multiple paths can be defined between two endpoints to provide load balancing and backup service in the event of a line failure. LSPs are set up for two purposes. The first is to allow network routers to forward packets to each other. The second is to directly connect two customer locations across the network. 
     An MPLS network includes several network elements. These network elements include Label Edge Routers (LERs) and Label Switching Routers (LSRs). Nodes belonging to other networks communicating with an MPLS network communicate with Label Edge Routers (LERs). LERs are devices that connect to other networks communicating with an MPLS network, determine routes, and add or remove labels from packets. LSRs are devices that switch packets and add or remove labels from packets. 
     In more detail, when packets enter an MPLS-based network, Label Edge Routers (LERs) provide the packets with a label (i.e., an identifier) and sometimes even with a stack of labels. Each successive router that encounters this packet will “pop” (remove) one or more labels from one end of the stack of labels. The labels contain an index into a routing table stored by routers. The index specifies the next hop for the packet and any labels that need to be “pushed” (added) on the stack of labels. The label carries the information that determines which path a packet should take. 
     Once the LERs determine how to route packets with the same (group of) destination IP addresses, they set up LSPs for each of the routes and associate labels with each hop of the LSP. Paths can be engineered using manual or automatic techniques. MPLS supports explicit routing, in which network engineers define specific paths across a network for specific types of traffic. MPLS also supports constraint-based routing, in Which the path is selected dynamically. Constraint-based routing involves programming traffic-engineering parameters into the network. 
     The traditional way to set up an LSP is to select one endpoint node (i.e., endpoint) of the LSP as the source and the other endpoint of the LSP as the destination. The source node (also referred to below as source router) typically determines the route of the LSP and then communicates with each router in the route to set up the LSP. These communications involve complex routing and signaling protocols, such as the MPLS suite of protocols. 
     MPLS processing (e.g., the labeling of the packets, the determination of an LSP for different packets, etc.) requires processing capabilities beyond a limited set of capabilities. In order for an endpoint node to perform the functions (e.g., the provisioning of an LSP) of a source, the endpoint node has to be capable of executing the full suite of MPLS and/or network inter-working protocols. This, however, is often not the case. The devices on customer premises typically have limited capabilities. These devices often do not have the power to execute a full complement of routing, signaling, and inter-working protocols. Typically, the ability to run a full routing protocol in order to exchange network topology information and to calculate a path for an LSP is not provided in these devices. The set of signaling functions may be reduced to accepting and completing LSP set up requests that are originated by another device. 
     For example, it may be desirable to share data between two office locations. Routers at the customer premises (i.e., each office location), however, are typically not capable of communicating using the full suite of MPLS. These routers (at the customer premises) can frequently communicate with the more complex network devices, but these communications can only utilize a limited set of functions due to the customer premises equipment&#39;s limited capabilities. 
     Thus, a new way of setting up an LSP is needed using customer premises equipment capable of executing only a limited set of MPLS functions. 
     BRIEF SUMMARY OF THE INVENTION 
     The present invention provides for an improved method and apparatus for provisioning a label switched path between a first endpoint and second endpoint of a network. The two endpoints execute a first set of MPLS functions. Thus, to set up a label switched path between the two endpoints, a node associated with one of the two endpoints is designated as a source node to provision the LSP between the two endpoints. The source node can execute a second set of MPLS functions. The second set of MPLS functions include the first set of MPLS functions and additional MPLS functions. 
     In accordance with the present invention, the system associates a first node with the first endpoint and a second node with the second endpoint. The first node is designated as the source. Both the first and second nodes execute a second set of MPLS functions, wherein the second set of MPLS functions comprise the first set of MPLS functions and additional MPLS functions. As the source, the first node provisions a first MPLS path (i.e., LSP) between itself and the first endpoint. The first node then provisions a second MPLS path (i.e., LSP) between the first node and the second node. The first node then transmits a message to the second node instructing the second node to provision a third MPLS path between the second node and the second endpoint. 
     The first node also bridges the first MPLS path and the second MPLS path so that data can flow between the two MPLS paths. The message sent to the second node can also request the second node to bridge the third MPLS path and the second MPLS path so that data can flow between these two MPLS paths. 
     Similar to the first node being designated as a source, the second node may be designated as a destination node after the second node is associated with the second endpoint. In one embodiment, a Network Management System (NMS) transmits the message(s) to the source and/or destination nodes. 
     The message sent to the source for provisioning the LSP between the two endpoints may have several identifiers. For example, the message may include a first identifier for the first endpoint and a second identifier for the second endpoint. The message may also include a third identifier for the source node. The message may include an identifier for the LSP being provisioned. The message transmitted from the source to the destination node may include a request to set up an LSP as well as a request to bridge two LSPs together. 
     These and other advantages of the invention will be apparent to those of ordinary skill in the art by reference to the following detailed description and the accompanying drawings. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  shows a high level block diagram of a network having two endpoints in accordance with an embodiment of the invention; 
         FIG. 2  shows a high level block diagram of the network with Element Management Systems and a Network Management System in accordance with an embodiment of the invention; 
         FIG. 3  is a flowchart showing the steps performed by the Network Management System and first and second nodes to provision a label switched path between the two endpoints of the network in accordance with an embodiment of the invention; and 
         FIG. 4  is a high level block diagram of a message transmitted between nodes in the network to provision the label switched path in accordance with an embodiment of the invention. 
     
    
    
     DETAILED DESCRIPTION 
     The present invention enables the provisioning of a label switched path (LSP) across two or more MPLS networks. Despite endpoints of an LSP being routers (or switches) that are incapable of communicating using the full suite of MPLS and executing network inter-working protocols, the present invention enables the provisioning of an LSP to connect the two endpoints at remote customer locations. 
       FIG. 1  shows a block diagram of an LSP across networks  50 . A core network, or main network,  90  includes nodes (e.g., router or switch)  97 ,  99 . The nodes  97 ,  99  can execute the full suite of MPLS for routing. The nodes  97 ,  99  also have inter-working protocol capabilities in order to communicate with routers outside of the core network  90 . 
     Endpoint node  95  (i.e., first endpoint  95 ) is positioned in a first customer premises location and endpoint node  96  (i.e., second endpoint  96 ) is positioned in a second customer premises location. These endpoint nodes cannot execute the full suite of functions associated with MPLS (i.e., or a first protocol). The first endpoint  95  communicates with the router  99  via an access network  91 . Similarly, the second endpoint  96  communicates with the router  97  via access network  92 . Each access network  91 ,  92  is the part of the network  50  that connects the customer equipment (e.g., router  95 ) to the customer&#39;s network provider or ISP (e.g., router  99 ). 
     Referring to  FIG. 2 , one or more Element Management Systems (EMSes)  200   a ,  200   b ,  200   c  (generally  200 ) manage the routers in one or more networks. Each EMS  200  is a device that is generally connected to the routers (or switches) of one (or more) IP network(s). The EMS  200  provides a graphical user interface (GUI) of the network to one or more network administrators and displays the network and its associated routers, shelves, bays, circuits, etc. to the network administrators. The EMS  200  can also perform fault management and performance management. The EMS  200  is used for downloading software to the routers and for backup of critical data. Each EMS  200  communicates with a Network Management System (NMS)  204  (also referred to as an Operations Support System (OSS)). The NMS  204  provisions the various circuit segments and the interfaces between the various segments. In one embodiment, the NMS  204  has independent systems for provisioning, inventory, maintenance, and billing. The provisioning and inventory systems may contain a database of all network facilities, such as the network&#39;s routers, ports, links between routers, etc. In some embodiments, the NMS  204  is another EMS  200 . The NMS  204  may also partially replace the EMSes  200 , performing some of its functionality as well as some of the functionality performed by each EMS  200 . 
     The NMS  204  is the system typically used by the network provider to set up the connection between the customer endpoints. To this end, the NMS  204  sends out provisioning commands to the network devices. Often these commands flow to the routers via the respective EMSes  200 . The EMSes  200  may also act on the provisioning commands and send a modified set of commands to the routers. Prior to the availability of network inter-working protocols, each segment of the connection was set up independently by NMS  204 , and the various inter-connection points were manually cabled together at the various locations under the direction of the NMS  204 . This last manual aspect significantly increased the time it took to set up a complete connection. 
     With the advent of inter-working protocols, the devices at the interconnection points can communicate with each other making it possible for provisioning commands to flow from one network to another. This makes it possible to set up the entire connection, spanning more than one network, in one provisioning step without any intermediate manual cabling tasks. The traditional way to set up an LSP requires at least one endpoint of the LSP to be able to execute a full set of MPLS functions. This is often not the case, particularly so when the endpoints are in customer locations. 
     A set of associations, or links, are created in NMS  204 . Every network device or customer premise device that is incapable of executing the full MPLS functionality is linked to one or more network devices with full MPLS functionality. Each associated device is capable of setting up an LSP to any other point in this network and across other networks. 
       FIG. 3  shows a flowchart illustrating the steps performed to provision an LSP across endpoints  95 ,  96 . The NMS  204  first associates the first node  99  with the first endpoint  95  in step  302 . The NMS  204  then designates the first node  99  as the source of the LSP in step  304 . 
     The association may be based on one or more rules, such as rules relating to the physical location of the nodes. For example, the first node  99  is associated with the first endpoint  95  because the first node  99  is the closest router to the first endpoint  95  that can communicate via the full suite of MPLS. The rule could also be based geographically on where the LSP is to be routed. For example, there could be one associated node for an LSP from the domestic US network to Europe and another for an LSP to Canada. The rule could also be to match the endpoint device with a node having a device from the same vendor of communication equipment. 
     The NMS  204  also associates a second node  98  with the second endpoint  96  in step  306 . This association with the second endpoint  96  may be based on the same criteria as the first association (e.g., router closest to the second endpoint  96  that can communicate using the full suite of MPLS) or may be based on different criteria. The second node  98  is described above as being associated with the second endpoint  96  because of its physical location in relation to the second endpoint  96 . Further, the associations do not have to be one to one. For example, the second node  98  may be associated with multiple endpoints of different paths. The second node may be in the same network as the second endpoint or in a different network. It is not necessary to always associate a first node and a second node. For example, if the second endpoint is capable of full MPSL functionality then the second association is not needed. 
     In one embodiment, the second node  98  is also designated as a destination node. The NMS  204  then transmits a provisioning message to the source node via the EMS  200  corresponding to the source (e.g., EMS  200   b ). As described in more detail below, the message includes identifiers for the two endpoints  95 ,  96  as well as an identifier for the destination node (i.e., second node  98 ) associated with the destination endpoint (i.e., the second endpoint  96 ). 
     The source node  99  provisions the LSP between the endpoints  95 ,  96  in three steps. First, the source node  99  sets up a first LSP  101  between the first endpoint  95  and the source node  99  in step  308 . Next, the source  99  provisions a second LSP  102  between the source  99  and the second node  98  in step  310 . The source node  99  also bridges, or enables communication between, the two LSPs  101  and  102 . The source  99  then transmits a message to the second node  98  requesting the provisioning of a third LSP  103  between the second node  98  and the second endpoint  96  in step  312 . The message also requests the second node  98  to bridge the second LSP  102  and the third LSP  103 . The bridging of the LSPs  102 ,  103  enables data to flow between the two LSPs  102 ,  103 . The source node  99  has therefore set up an LSP across multiple networks by provisioning and bridging, in step  314 , multiple LSPs together (i.e., LSP  101 ,  102 , and  103 ). The source  99  provisions an LSP using information collected by its routing protocol (e.g., Border Gateway Protocol, Open Shortest Path First Protocol), such as the topology of the entire network and all reachable destination addresses. 
     Moreover, although described above and below with respect to the source node  99 , the description equally applies to the destination node  98 . In other words, the second node  98  could instead be designated as the source node and the first node  99  could be designated as the destination node. 
       FIG. 4  is a block diagram of an embodiment of a provisioning command or message  400  transmitted from the NMS  204  to the source  99  and then from the source  99  to the second node  98  to request the provisioning of the third LSP  103 . The message sent from the NMS  204  to the source  99  includes fields  402  through  416  (i.e., above the dashed line  417 ). The message sent from the source  99  to the second node  98  includes the fields above dashed line  417  as well as the fields  418  through  422  below the dashed line  417 . 
     In more detail, the message  400  includes an LSP identifier  402  (e.g., LSP  100 ) to identify the LSP that is being provisioned. The message  400  can also include LSP parameters  404 , such as the bandwidth needed for the LSP, the maximum latency allowed, etc. The message  400  also includes an identifier  406  for the first endpoint  95  and the type  408  of the first endpoint  95 . The type  408  of the first endpoint  95  identifies whether the first endpoint  95  is capable of executing the full suite of MPLS and network inter-working protocols. The type  408  may be a flag to indicate whether the endpoint  95  can handle the MPLS protocol. Alternatively, the type  408  may be a symbol or drawing depicting whether the endpoint  95  can handle the MPLS protocol. The message  400  can also include an identifier  410  of the node  99  associated with the first endpoint  95 . 
     The message  400  also includes the same fields  412 - 416  for the second endpoint  96 , such as an identifier  412  for the second endpoint  96 , a type  414  of the second endpoint  96 , and an identifier for the node  98  associated with the second endpoint  96 . 
     To provision LSP  103 , the source  99  transmits a separate message to the destination node  98  having the fields above and below the dashed line  417 . The message  400  may include a request  420  to set up the third LSP  103  and to bridge the second LSP  102  and the third LSP  103 . This request  420  may be, for example, a flag. The message  400  additionally includes an identifier  422  for the second LSP  102 . Although shown in a single message, any number of the fields  402 - 422  may be transmitted in any number of messages. 
     The functions of the nodes, endpoints, EMSes, and NMSes and elements of the network described above may be implemented by one or more computers executing appropriate computer program code. The computer program code may be stored in a storage device and loaded into memory when execution of the computer program code is desired. Thus, the computer operation will be defined by computer program code stored in memory and/or storage and the computer will be controlled by one or more processors executing the computer program code. The computer also includes one or more network interfaces for communicating with other devices via a network. 
     For example, each node (e.g., the source node  99 ) may include one or more interfaces for transmitting and receiving messages such as message  400  described above. Each node may further include one or more processors to execute the functionality described above. One skilled in the art will recognize that an implementation of an actual computer will contain other components as well. 
     Although described above with respect to IP networks running the MPLS protocol, the present invention also applies to Optical networks (e.g., Synchronous Optical Network switches, or SONET), Asynchronous Transfer Mode (ATM) networks, etc. that run either variants of the MPLS protocol or some other protocol with equivalent functionality. These networks have virtual circuits or Time Division Multiplexing (TDM) circuits that are akin to LSPs. Further, the present invention may be used with multiple networks running different protocols so long as the network inter-working functionality can translate instructions from one protocol to another. 
     The foregoing Detailed Description is to be understood as being in every respect illustrative and exemplary, but not restrictive, and the scope of the invention disclosed herein is not to be determined from the Detailed Description, but rather from the claims as interpreted according to the full breadth permitted by the patent laws. It is to be understood that the embodiments shown and described herein are only illustrative of the principles of the present invention and that various modifications may be implemented by those skilled in the art without departing from the scope and spirit of the invention. Those skilled in the art could implement various other feature combinations without departing from the scope and spirit of the invention.