Patent Description:
The present disclosure relates generally to mLDP transport, in particular to mLDP transport over a BIER core.

Multi-Protocol Label Switching (MPLS) is a type of data-carrying technique for high-performance telecommunications networks that directs data from one network node to the next based on short path labels rather than long network addresses, avoiding complex lookups in a routing table. The labels identify virtual links (paths) between distant nodes rather than endpoints. MPLS can encapsulate packets of various network protocols, hence its name "multiprotocol". MPLS supports a range of access technologies, including T1/E1, ATM, Frame Relay, and DSL. XP015127390, M-LDP Signaling Through BIER Core; draft-hj-bier-mldp-signaling-<NUM>. txt, discusses mLDP signaling over a BIER core. <CIT> discusses establising T-LDP sessions among edge devices.

Seamless multipoint label distribution protocol (mLDP) transport over a bit index explicit replication (BIER) core may be provided. First, it may be determined that a first plurality of network devices comprise BIER edge routers. Then, in response to determining that the first plurality of network devices comprise BIER edge routers, a Targeted Label Distribution Protocol (T-LDP) session may be created between a first one of the first plurality of network devices and a second one of the first plurality of network devices. Next, an address of a peer device connected to the second one of the first plurality of network devices may be advertised by the second one of the first plurality of network devices over the T-LDP session.

Systems and apparatus for implementing the methods described herein, including network nodes, computer programs, computer program products, computer readable media and logic encoded on tangible media for implementing the methods are also described.

Both the foregoing overview and the following example embodiments are examples and explanatory only, and should not be considered to restrict the disclosure's scope, as described and claimed. Further, features and/or variations may be provided in addition to those set forth herein. For example, embodiments of the disclosure may be directed to various feature combinations and sub-combinations described in the example embodiments.

The following detailed description refers to the accompanying drawings. Wherever possible, the same reference numbers are used in the drawings and the following description to refer to the same or similar elements. While embodiments of the disclosure may be described, modifications, adaptations, and other implementations are possible. For example, substitutions, additions, or modifications may be made to the elements illustrated in the drawings, and the methods described herein may be modified by substituting, reordering, or adding stages to the disclosed methods. Accordingly, the following detailed description does not limit the disclosure. Instead, the invention is defined by the appended claims.

In conventional Internet Protocol (IP) multicast forwarding, packets of a given multicast "flow" may be forwarded along a tree that may have been constructed for a specific purpose of carrying the flow. This may require transit nodes to maintain state on a per-flow basis, and may require the transit nodes to participate in multicast-specific tree building protocols. The flow to which a packet belongs may be determined by its IP source and destination address fields.

Bit Index Explicit Replication (BIER) may comprise an alternative process for multicast forwarding. It may not require any multicast-specific trees, and hence may not require any multicast-specific tree building protocols. Within a given "BIER domain", an ingress node may encapsulate a multicast data packet in a "BIER header". The BIER header may identify a packet's egress nodes in that domain. Each possible egress node may be represented by a single bit within a bitstring. To send a packet to a particular set of egress nodes, an ingress node may set the bits for each of those egress nodes, and may clear other bits in the bitstring. Each packet may then be forwarded along a unicast shortest path tree from the ingress node to the egress nodes. Thus there may be no per-flow forwarding entries with BIER.

Because of the aforementioned advantages of BIER, service providers may desire migration strategies to introduce BIER into networks for multicast distribution. Consistent with embodiments of the disclosure, one migration strategy may comprise introducing BIER in core (P) routers of an existing network, and keeping multipoint Label Distribution Protocol (mLDP) on the edge (PE) routers. This may be beneficial because the P routers may be simpler (e.g., run less features), and may allow for a phased introduction of BIER leaving the PE routers unaltered. Deploying BIER in the core of the network may significantly reduce the amount of multicast state in the core network.

Embodiments of the disclosure may allow mLDP to be deployed over a BIER core with a minimal configuration overhead by using Targeted mLDP (T-mLDP) sessions with new extensions. Accordingly, stitching of mLDP to BIER on the P routers may be provided.

<FIG> shows an operating environment <NUM> consistent with embodiments of the disclosure for providing seamless mLDP transport over a BIER core. As shown in <FIG>, operating environment <NUM> may comprise a network <NUM>. Network <NUM> may comprise a BIER core <NUM> and a plurality of mLDP edge routers. The plurality of mLDP edge routers may comprise a first mLDP edge router <NUM> (i.e., PE-<NUM>), a second mLDP edge router <NUM> (i.e., PE-<NUM>), a third mLDP edge router <NUM> (i.e., PE-<NUM>), a fourth mLDP edge router <NUM> (i.e., PE-<NUM>), a fifth mLDP edge router <NUM> (i.e., PE-<NUM>), and a sixth mLDP edge router <NUM> (i.e., PE-<NUM>).

BIER core <NUM> may comprise a plurality of BIER edge routers <NUM> and a BIER core device <NUM> (i.e., P0) (e.g., a core router). Plurality BIER edge routers <NUM> may comprise a first BIER edge router <NUM> (i.e. P1), a second BIER edge router <NUM> (i.e. P2), a third BIER edge router <NUM> (i.e. P3), and a fourth BIER edge router <NUM> (i.e. P4).

With conventional systems, each node in a network may run an mLDP session. For example, with conventional systems, a leaf node may initiate mLDP signaling towards a root of a tree where the whole core may use mLDP enabled signaling. Embodiments of the disclosure, as illustrated in <FIG>, may provide, for example, a migration strategy for service providers to move to a BIER core while keeping the edge routers (i.e., PE's) unchanged. Accordingly, mLDP may be used from the edge routers to a BIER core.

The elements described above of operating environment <NUM> (e.g., the plurality of mLDP edge routers and plurality BIER edge routers <NUM>) may be practiced in hardware and/or in software (including firmware, resident software, micro-code, etc.) or in any other circuits or systems. The elements of operating environment <NUM> may be practiced in electrical circuits comprising discrete electronic elements, packaged or integrated electronic chips containing logic gates, a circuit utilizing a microprocessor, or on a single chip containing electronic elements or microprocessors. Furthermore, the elements of operating environment <NUM> may also be practiced using other technologies capable of performing logical operations such as, for example, AND, OR, and NOT, including but not limited to, mechanical, optical, fluidic, and quantum technologies. As described in greater detail below with respect to <FIG>, the elements of operating environment <NUM> may be practiced in a computing device <NUM>.

<FIG> is a flow chart setting forth the general stages involved in a method <NUM> consistent with an embodiment of the disclosure for providing seamless mLDP transport over a BIER core. Method <NUM> may be implemented using operating environment <NUM> described in more detail above with respect to <FIG>. Ways to implement the stages of method <NUM> will be described in greater detail below.

Method <NUM> may begin at starting block <NUM> and proceed to stage <NUM> where it may be determined that a first plurality of network devices (e.g., any two or more of plurality BIER edge routers <NUM>) comprise BIER edge routers. For example, one of the challenges of seamlessly transporting mLDP over a BIER core may be how to determine where BIER core starts <NUM>.

As shown in <FIG>, BIER core <NUM> may connect all the P routers (i.e., BIER core device <NUM> and plurality of BIER edge routers <NUM>). Each of the Egress/Ingress P routers (i.e., plurality of BIER edge routers <NUM>) may have been configured with a Bit Forwarding Egress Router Identifier (BFER ID). For example, first BIER edge router <NUM> may have BFER ID "BFER-<NUM>", second BIER edge router <NUM> may have BFER ID "BFER-<NUM>", third BIER edge router <NUM> may have BFER ID "BFER-<NUM>", and fourth BIER edge router <NUM> may have BFER ID "BFER-<NUM>". The PE routers (e.g., the plurality of mLDP edge routers) may be directly connected to the Egress/Ingress P routers and may have established mLDP sessions.

The plurality of mLDP edge routers may only run mLDP and plurality of BIER edge routers <NUM> may run both mLDP and BIER. Embodiments of the disclosure may first determine which routers in network <NUM> are plurality of BIER edge routers <NUM> (i.e., the Egress/Ingress P routers) in order to establish targeted LDP sessions.

As stated above, plurality of BIER edge routers <NUM> may each be configured with a BFER ID. When plurality of BIER edge routers <NUM> are configured with a BFER ID, this ID may be associated with a loopback address and announced in the Interior Gateway Protocol (IGP) and advertised. Each router that is part of this IGP may receive the BIER specific announcements. These BFER ID to Prefix mappings may be installed into a Routing Information Base (RIB) corresponding to network <NUM>. Because LDP may also be connected to the RIB, it may learn the BIER BFER ID's from the RIB. Embodiments of the disclosure may determine which routers in network <NUM> are plurality of BIER edge routers <NUM> by leaning from the RIB which routers have a BFER ID.

From stage <NUM>, where it may be determined that the first plurality of network devices comprise BIER edge routers, method <NUM> may advance to stage <NUM> where a Targeted Label Distribution Protocol (T-LDP) session between a first one of the first plurality of network devices and a second one of the first plurality of network devices may be created in response to determining that the first plurality of network devices comprise BIER edge routers. For example, embodiments of the disclosure may use the aforementioned BFER's prefix addresses that were learned from the RIB to create a full mesh of T-LDP sessions among plurality of BIER edge routers <NUM>. For example, a first T-LDP session <NUM> may be created between first BIER edge router <NUM> and second BIER edge router <NUM>, a second T-LDP session <NUM> may be created between first BIER edge router <NUM> and third BIER edge router <NUM>, and a third T-LDP session <NUM> may be created between first BIER edge router <NUM> and fourth BIER edge router <NUM>. Although not shown in <FIG>, a T-LDP session may be created between all plurality of BIER edge routers <NUM>.

LDP may comprise a protocol in which routers capable of MPLS may exchange label mapping information. Two routers with an established session are called LDP peers and the exchange of information may be bi-directional. LDP may be used to build and maintain LSP databases that may be used to forward traffic through the MPLS networks. Targeted LDP sessions may be different because, during the discovery phase, hellos are unicast to the LDP peer rather than using multicast. Consequently, T-LDP may be set up between non-directly connected peers. Consistent with embodiments of the disclosure, BIER BFER ID announcements may be used to setup a full mesh of Targeted LDP sessions.

BIER core device <NUM> (i.e., P0) in the middle of BIER core <NUM> does not have a BFER ID. Furthermore, BIER core device <NUM> may run BIER only and not mLDP. Accordingly, BIER core device <NUM> will not be considered to setting up a T-LDP session. The number of P nodes in a network may be much smaller compared to the PE routers, so this may not be a scale concern.

Once the T-LDP session (e.g., first T-LDP session <NUM>) between the first one of the first plurality of network devices (e.g., first BIER edge router <NUM>) and the second one of the first plurality of network devices (e.g., second BIER edge router <NUM>) is created in stage <NUM>, method <NUM> may continue to stage <NUM>. At stage <NUM>, second BIER edge router <NUM> may advertise, over first T-LDP session <NUM>, an address of a peer device (e.g., fifth mLDP edge router <NUM>) connected to second BIER edge router <NUM>.

Having the T-LDP sessions created above may not enough. For example, if second mLDP edge router <NUM> (i.e., PE-<NUM>) is sending a mLDP Label Mapping towards an mLDP Root (e.g., fifth mLDP edge router <NUM> (i.e., PE-<NUM>)), second mLDP edge router <NUM> may do a route lookup on the Root address in the RIB, and find that the next-hop is first BIER edge router <NUM> (i.e. P1). Since the next-hop (i.e., first BIER edge router <NUM>) is directly connected to second mLDP edge router <NUM>, second mLDP edge router <NUM> may be able to find the correct LDP session to send the Label Mapping on. First BIER edge router <NUM> may try to do the same thing, lookup the root address of fifth mLDP edge router <NUM> in the RIB. This will return BIER core device <NUM> (i.e., P0) as the next-hop. However, BIER core device <NUM>, is not a LDP peer because BIER core device <NUM> is not running mLDP and no label mapping can be sent. To correct this issue, embodiments of the disclosure may provide a process where first BIER edge router <NUM> may be able to determine that the targeted LDP session to second BIER edge router <NUM> (i.e. P2) may comprise the right LDP neighbor to send the Label Mapping.

When mLDP does a route lookup on the Root address, the directly connected next-hop address is returned. This directly connected address may be used to do a lookup in the database that has all the directly connected addresses of all the LDP peers. These addresses may be advertised using the "Address Message" when establishing the LDP peer. However, first BIER edge router <NUM> (i.e., P1) only knows about the connected addresses of second BIER edge router <NUM> (i.e. P2), third BIER edge router <NUM> (i.e. P3), and fourth BIER edge router <NUM> (i.e. P4). Consequently, first BIER edge router <NUM> (i.e., P1) may be unable to determine that fifth mLDP edge router <NUM> (i.e., PE-<NUM>) is reachable through first T-LDP session <NUM> to second BIER edge router <NUM> (i.e. P2).

Embodiments of the disclosure may provide an LDP Message Type, which is like the "Address Message", but allows to "proxy" advertise connected addresses of its LDP peers. For example, second BIER edge router <NUM> (i.e. P2) may advertise its own connected addresses as normal, but may also advertise the addresses it has learned from fourth mLDP edge router <NUM> (i.e., PE-<NUM>) and fifth mLDP edge router <NUM> (i.e., PE-<NUM>). These may be advertised, one-hop, over the T-LDP sessions towards first BIER edge router <NUM> (i.e. P1), third BIER edge router <NUM> (i.e. P3), and fourth BIER edge router <NUM> (i.e. P4). When first BIER edge router <NUM> (i.e. P1) does the RIB lookup on the Root address, the next-hop points to BIER core device <NUM>. BIER core device <NUM> (i.e., P0) will not find an LDP peer for that next-hop.

To address this, embodiments of the disclosure may add an exception in the mLDP logic to use the Root address and do a lookup in the connected address database. Due to the aforementioned process, first BIER edge router <NUM> will find a connected address (being fifth mLDP edge router <NUM> (i.e., PE-<NUM>)), associated with first T-LDP session <NUM> to second BIER edge router <NUM> (i.e. P2). The mLDP Label Mapping may be forwarded to second BIER edge router <NUM> (i.e. P2) that may do the normal mLDP procedures. Accordingly, LDP peers connected over BIER core <NUM> may "proxy" advertise the connected addresses from its peers, such that the downstream mapping of the Root node to LDP Peer works.

In addition, it may be possible that a PE router is connected to multiple P routers. A downstream P router may then see multiple candidate upstream P routers (via the Targeted LDP session) that are announcing reachability to the Root address. If there are multiple candidate upstream P routers, the P router may be chosen with the best metric from the RIB, if equal, some load balancing logic may be applied to pick one.

Consequently, embodiments of the disclosure may use the BIER BFER ID announcements to setup a full mesh of T-LDP sessions. Then, the connected addresses may be proxy advertise over the T-LDP sessions. Accordingly, routers on edge of BIER network <NUM> may be able to determine which T-LDP peer can be used to reach the mLDP root address without being directly connected to it. After second BIER edge router <NUM> advertises the address in stage <NUM>, method <NUM> may then end at stage <NUM>.

<FIG> shows a computing device <NUM>. As shown in <FIG>, computing device <NUM> may include a processing unit <NUM> and a memory unit <NUM>. Memory unit <NUM> may include a software module <NUM> and a database <NUM>. While executing on processing unit <NUM>, software module <NUM> may perform processes for providing seamless mLDP transport over a BIER core, including for example, any one or more of the stages from method <NUM> described above with respect to <FIG>. Computing device <NUM>, for example, may provide an operating environment the plurality of mLDP edge routers and the plurality BIER edge routers. The plurality of mLDP edge routers and the plurality BIER edge routers may operate in other environments and are not limited to computing device <NUM>.

Computing device <NUM> may be implemented using a Wireless Fidelity (Wi-Fi) access point, a cellular base station, a tablet device, a mobile device, a smart phone, a telephone, a remote control device, a set-top box, a digital video recorder, a cable modem, a personal computer, a network computer, a mainframe, a router, a switch, a server cluster, a smart TV-like device, a network storage device, a network relay device, or other similar microcomputer-based device. Computing device <NUM> may comprise any computer operating environment, such as hand-held devices, multiprocessor systems, microprocessor-based or programmable sender electronic devices, minicomputers, mainframe computers, and the like. Computing device <NUM> may also be practiced in distributed computing environments where tasks are performed by remote processing devices. The aforementioned systems and devices are examples and computing device <NUM> may comprise other systems or devices.

Embodiments of the disclosure, for example, may be implemented as a computer process (method), a computing system, or as an article of manufacture, such as a computer program product or computer readable media. The computer program product may be a computer storage media readable by a computer system and encoding a computer program of instructions for executing a computer process. The computer program product may also be a propagated signal on a carrier readable by a computing system and encoding a computer program of instructions for executing a computer process. Accordingly, the present disclosure may be embodied in hardware and/or in software (including firmware, resident software, micro-code, etc.). In other words, embodiments of the present disclosure may take the form of a computer program product on a computer-usable or computer-readable storage medium having computer-usable or computer-readable program code embodied in the medium for use by or in connection with an instruction execution system. A computer-usable or computer-readable medium may be any medium that can contain, store, communicate, propagate, or transport the program for use by or in connection with the instruction execution system, apparatus, or device.

Embodiments of the disclosure may be practiced via a system-on-a-chip (SOC) where each or many of the elements illustrated in <FIG> may be integrated onto a single integrated circuit. Such a SOC device may include one or more processing units, graphics units, communications units, system virtualization units and various application functionality all of which may be integrated (or "burned") onto the chip substrate as a single integrated circuit. When operating via a SOC, the functionality described herein with respect to embodiments of the disclosure, may be performed via application-specific logic integrated with other components of computing device <NUM> on the single integrated circuit (chip).

Claim 1:
A method comprising:
determining(<NUM>) that a first plurality of network devices comprise Bit Index Explicit Replication ,BIER, edge routers;
creating, in response to determining that the first plurality of network devices comprise BIER edge routers, a Targeted Label Distribution Protocol ,T-LDP, session between a first one of the first plurality of network devices and a second one of the first plurality of network devices;
advertising, by the second one of the first plurality of network devices over the T-LDP session, an address of a peer device connected to the second one of the first plurality of network devices; and
placing, by the first one of the first plurality of network devices, an entry in a proxy database, wherein the entry indicates a connection between the peer device and the second one of the first plurality of network devices.