LDP IGP synchronization for broadcast networks

A method and apparatus for LDP-IGP synchronization for broadcast networks. In one embodiment of the invention, responsive to a network element bringing up an adjacency with a Designated Router of the broadcast network on a broadcast interface, that network element advertises in its Link State Advertisement (LSA) a peer-to-peer (P2P) adjacency to each member of the broadcast network that has bidirectional IGP communication with the network element instead of advertising a pseudo-node adjacency to the pseudo-node of the broadcast network. Each P2P adjacency includes a high cost to discourage use of those links for transit traffic. After LDP becomes operational with all neighbors on the broadcast interface, the network element advertises the pseudo-node adjacency instead of the P2P adjacencies. Accordingly, transit traffic is avoided through that network element until LDP is operational with all neighbors on the broadcast interface.

BACKGROUND

Embodiments of the invention relate to the field of networking; and more specifically to LDP (Label Distribution Protocol) IGP (Interior Gateway Protocol) synchronization for broadcast networks.

LDP, described in “LDP Specification”, RFC 5036, October 2007, which is used to establish LSPs (label switched paths) to destinations, typically relies on IGP (e.g., Open Shortest Path First (OSPF), defined in “OSPF Version 2”, STD 54, RFC 2328, April 1998, Intermediate system to Intermediate system (IS-IS), defined in “Intermediate system to intermediate system intra-domain-routing routine information exchange protocol for use in conjunction with the protocol for providing the connectionless-mode Network Service (ISO 8473)” ISO standard 10589, 1992, etc.) to provide the underlying routing information for LDP (e.g., the cost metric between the hops in the network). Even though LDP typically relies on the IGP protocol, they are independent from each other. Typically, IGP converges faster than LDP converges As a result, IGP may be operational on a link prior to LDP becoming operational on that link which can lead to packet loss.

The request for comments (RFC) 5443, “LDP IGP Synchronization”, March 2009 (hereinafter “LDP IGP Synchronization”) describes a mechanism to discourage links from being used for IP forwarding if LDP is not fully operational on that link. RFC 5443 describes that when LDP is not fully operational on a given link (e.g., all the label bindings have not yet been exchanged), IGP will advertise the link with maximum cost to discourage traffic from being sent over the link. When LDP on the link becomes operational (e.g., all label bindings have been exchanged), IGP advertises the link with the correct cost.

On broadcast links (more than one LDP/IGP peer on the same link), IGP advertises a common cost to the broadcast link, rather than a separate cost to each peer. A broadcast pseudo-node may be implemented in a network to reduce the number of links in the shortest path first (SPF) (e.g., open shortest path first (OSPF), constrained shortest path first (CSPF)) database of each network element. Each network element forms adjacencies with the broadcast pseudo-node and advertises a link and cost to the broadcast pseudo-node and the broadcast pseudo-node advertises a link and cost to each network element. One of the network elements in the broadcast network acts as a Designated Router (DR) of that network and is responsible for advertising the link and cost from the broadcast pseudo-node to the members of the broadcast network.

For broadcast links, the RFC 5443 “LDP IGP Synchronization” describes that the mechanism can be applied to the link as a whole but not to an individual peer. Advertising maximum cost to the link as a whole may cause sub-optimal traffic diversion and/or black-holing of traffic (e.g., traffic carried on the LSP such as VPN traffic).

SUMMARY

Methods and apparatuses for LDP-IGP synchronization for broadcast networks are described. According to one embodiment of the invention, a network element for use in a broadcast network that depends on the establishment of Label Switched Paths (LSPs) by a label distribution protocol (LDP) that is tied to Internet Protocol (IP) forwarding decisions of an interior gateway protocol (IGP) is adapted to assist in avoiding black-holing of traffic and sub-optimal traffic diversion caused by IGP converging prior to LDP converging. The network element includes a broadcast network interface adapted to carry transit traffic through an LSP when LDP is operational, an LDP module to exchange label bindings with neighbors of the network element, and an IGP module. The IGP module, responsive to bringing up an IGP adjacency with the Designated Router (DR), is operative to advertise a high cost peer-to-peer (P2P) adjacency for the broadcast network interface to each member of the broadcast network that is in a state of bidirectional IGP communication with the network element in a Link State Advertisement (LSA) of the network element instead of advertising a pseudo-node adjacency for the broadcast network interface to a pseudo-node of the broadcast network in that LSA to discourage use of the broadcast interface for transit traffic, where the pseudo-node represents the topology of the broadcast network, and the pseudo-node adjacency represents the unidirectional link from the network element to the pseudo-node. After LDP becomes operational with all neighbors on the broadcast interface, the IGP module is further operative to advertise the pseudo-node adjacency for the broadcast network interface to the pseudo-node in its LSA instead of advertising the P2P adjacencies, thereby removing the discouragement of the use of the broadcast network interface for transit traffic. Thus, transit traffic is avoided on the broadcast network interface until LDP is operational with all neighbors on that broadcast interface.

In another embodiment of the invention, a network element for use in a broadcast network that acts as a DR for the broadcast network which depends on the establishment of LSPs by an LDP that is tied to IP forwarding decisions of an IGP, includes a broadcast network interface that is adapted to carry transit traffic through an LSP, and an IGP module. The IGP module is operative to advertise pseudo-node LSAs on the broadcast network interface on behalf of a pseudo-node of the broadcast network to members of the broadcast network, where the pseudo-node represents the topology of the broadcast network, and where each pseudo-node LSA includes an indication of each member of the broadcast network that is adjacent to the DR. The IGP module is further operative to advertise high cost P2P adjacencies to the members of the broadcast network on the broadcast network interface as they are becoming adjacent to the DR, where each P2P adjacency represents a unidirectional link between the DR and a member of the broadcast network, and where the P2P adjacencies are advertised to discourage transmitting transit traffic to those members on the unidirectional links represented by the P2P adjacencies. The IGP module is further operative to cease the advertisement of the P2P adjacencies to those members of the broadcast network that have themselves advertised an LSA to the DR that does not include a P2P adjacency and have become adjacent to the DR. Thus, transit traffic is avoided on a unidirectional link to a member of the broadcast network until the DR receives an LSA from that member that does not include a P2P adjacency.

In another embodiment of the invention, a network element for use in a broadcast network that is adjacent to the DR of the broadcast network and has a bidirectional link to a pseudo-node of the broadcast network, where the broadcast network depends on the establishment of LSPs by an LDP that is tied to IP forwarding decisions of an IGP to function correctly, includes a broadcast network interface adapted to carry transit traffic through an LSP, and an IGP module. The IGP module is operative to receive LSAs from members of the broadcast network including pseudo-node LSAs from the DR that each include an indication of each member of the broadcast network that is adjacent to the DR. The IGP module further is operative to advertise a high cost P2P adjacency to each of those of the members of the broadcast network that are currently themselves advertising a P2P adjacency, where each P2P adjacency represents a unidirectional link between the network element and a member of the broadcast network, and where the P2P adjacencies are advertised to discourage transmitting transit traffic to those members on the unidirectional links represented by the P2P adjacencies. Upon receipt of an LSA that does not include a P2P adjacency from a member, the IGP module is further operative to cease the advertisement of the P2P adjacency to that member.

In another embodiment of the invention, a network element in a broadcast network assists in avoiding black-holing of traffic and sub-optimal traffic diversion in the broadcast network due to IGP converging prior to LDP converging, where the broadcast network depends on the establishment of LSPs by LDP that is tied to Internet IP forwarding decisions of IGP, where the network element is bringing up an adjacency with the DR of the broadcast network. The network element receives a pseudo-node LSA a broadcast network interface of the network element from the DR responsive to an establishment of bidirectional IGP communication with the DR, where the pseudo-node LSA includes an indication of the network element members of the broadcast network. The network element advertises, to each of the network element members of the broadcast network that has bidirectional IGP communication with the network element, a high cost P2P adjacency in its LSA instead of an adjacency to the pseudo-node of the broadcast network, to discourage use of the broadcast network interface for transmit traffic, where the adjacency to the pseudo-node represents the link between the pseudo-node and the network element. Responsive to LDP becoming operational with each of the neighbors on the broadcast network interface, the network element advertises the adjacency to the pseudo-node in its LSA for the broadcast network interface instead of the P2P adjacencies thereby removing the discouragement of the use of the broadcast network interface for transit traffic. Thus, transit traffic is avoided on the broadcast network interface while LDP is not operational with the network element members of the broadcast network.

In another embodiment of the invention, a broadcast network that depends on the establishment of LSPs by LDP that is tied to IP forwarding decisions of IGP, wherein the broadcast network is adapted to avoid black-holing of traffic and sub-optimal traffic diversion caused by IGP converging prior to LDP converging, the broadcast network includes multiple network elements that each include a broadcast network interface, an LDP module that exchanges label bindings with members of the broadcast network on the broadcast network interface, and an IGP module. The IGP module substitutes, while LDP is not operational with the members of the broadcast network on the broadcast network interface, advertising pseudo-node adjacencies in its LSAs with P2P adjacencies having a high cost to those members that have bidirectional IGP communication with the network element to discourage use of the broadcast network interface for transit traffic. The IGP module replaces, responsive to LDP becoming operational with the network element members of the broadcast network on the broadcast network interface, the P2P adjacencies in its LSA with the pseudo-node adjacency thereby removing the discouragement of the use of the broadcast network interface for transit traffic. The IGP module also advertises a high cost P2P adjacency to those of the network element members that have bidirectional IGP communication with the network element and are themselves advertising a P2P adjacency with a high cost to avoid those links to those network element members in forwarding decisions. Thus, transit traffic is avoided on links in the broadcast network on which LDP is not operational.

Thus transit traffic is avoided on a broadcast interface until LDP is operational on that interface without the transit traffic being black-holed or diverted to a sub-optimal path.

DETAILED DESCRIPTION

The techniques shown in the figures can be implemented using code and data stored and executed on one or more electronic devices (e.g., an end station, a network element, etc.). Such electronic devices store and communicate (internally and/or with other electronic devices over a network) code and data using machine-readable media, such as machine-readable storage media (e.g., magnetic disks; optical disks; random access memory; read only memory; flash memory devices; phase-change memory) and machine-readable communication media (e.g., electrical, optical, acoustical or other form of propagated signals—such as carrier waves, infrared signals, digital signals, etc.). In addition, such electronic devices typically include a set of one or more processors coupled to one or more other components, such as one or more storage devices, user input/output devices (e.g., a keyboard, a touchscreen, and/or a display), and network connections. The coupling of the set of processors and other components is typically through one or more busses and bridges (also termed as bus controllers). The storage device and signals carrying the network traffic respectively represent one or more machine-readable storage media and machine-readable communication media. Thus, the storage device of a given electronic device typically stores code and/or data for execution on the set of one or more processors of that electronic device. Of course, one or more parts of an embodiment of the invention may be implemented using different combinations of software, firmware, and/or hardware.

As used herein, a network element (e.g., a router, switch, bridge, etc.) is a piece of networking equipment, including hardware and software, that communicatively interconnects other equipment on the network (e.g., other network elements, end stations, etc.). Some network elements are “multiple services network elements” that provide support for multiple networking functions (e.g., routing, bridging, switching, Layer 2 aggregation, session border control, and/or subscriber management), and/or provide support for multiple application services (e.g., data, voice, and video). Subscriber end stations (e.g., servers, workstations, laptops, palm tops, mobile phones, smartphones, multimedia phones, Voice Over Internet Protocol (VoIP) phones, portable media players, GPS units, gaming systems, set-top boxes, etc.) access content/services provided over the Internet and/or content/services provided on virtual private networks (VPNs) overlaid on the Internet. The content and/or services are typically provided by one or more end stations (e.g., server end stations) belonging to a service or content provider or end stations participating in a peer to peer service, and may include public webpages (free content, store fronts, search services, etc.), private webpages (e.g., username/password accessed webpages providing email services, etc.), corporate networks over VPNs, etc. Typically, subscriber end stations are coupled (e.g., through customer premise equipment coupled to an access network (wired or wirelessly)) to edge network elements, which are coupled (e.g., through one or more core network elements) to other edge network elements, which are coupled to other end stations (e.g., server end stations).

Within certain network elements, multiple “interfaces” may be configured. As used herein an interface is a connection between a network element and one of its attached networks. An interface has information associated with it that is typically obtained from underlying lower level protocols and the routing protocol (e.g., an IP address and mask). An interface is sometimes referred to as a link. A broadcast interface is an interface that is connected with a broadcast network (sometimes referred to as a “broadcast network interface”).

As used herein, the term “link state advertisement” (LSA) is protocol agnostic. For example, if the IGP is Open Shortest Path First (OSPF), then the link state advertisements can include Router-LSAs, Network-LSAs, etc. If the IGP is intermediate system to intermediate system (IS-IS), then the LSAs can be Link State PDUs, pseudonode LSPs, etc.

A method and apparatus for LDP-IGP synchronization for broadcast networks is described. In one embodiment of the invention, responsive to a network element bringing up an adjacency with a DR of the broadcast network on a broadcast interface, that network element advertises in its LSA for the broadcast interface a peer-to-peer (P2P) adjacency to each member of the broadcast network that has bidirectional IGP communication with the network element instead of advertising a pseudo-node adjacency to the pseudo-node of the broadcast network. Each P2P adjacency includes a high cost to discourage use of those links for transit traffic. After LDP becomes operational with all neighbors on that broadcast interface, the network element advertises the pseudo-node adjacency instead of the P2P adjacencies. Accordingly, transit traffic is avoided through that network element until LDP is operational with all neighbors of the network element.

In another embodiment of the invention, on a DR of the broadcast network, responsive to an adjacency being established between the DR and a neighbor of the broadcast network, the DR advertises a high cost P2P adjacency to the neighbor in its LSA to discourage transmission of transit traffic through that neighbor. The high cost P2P adjacency to that neighbor remains until the DR receives an LSA from that neighbor that does not include a P2P adjacency, which at that point the DR assumes that LDP is operational on that network element and the DR removes the P2P adjacency. Accordingly, transit traffic is avoided through that network element until LDP is operational on that network element.

In another embodiment of the invention, on a network element that is a member of the broadcast network that is adjacent to the DR of the broadcast network, responsive to receiving a pseudo-node LSA, the network element advertises in its LSA a high cost P2P adjacency to each neighbor listed in the pseudo-node LSA that are themselves advertising a high cost P2P adjacency to discourage transit traffic from being transmitted through those neighbors. Responsive to receiving an LSA from one of those neighbors that does not include a P2P adjacency, the network element assumes that LDP is operational on that neighbor and removes the high cost P2P adjacency to that neighbor.

In one embodiment, if the IGP protocol is Open Shortest Path First (OSPF), the Router-LSA of a network element that is bringing up an IGP adjacency with the DR of the broadcast network is not updated with a Link Type 2 (link to transit network) for the subnet until LDP is operational with all network elements on that subnet.

In one embodiment, if the IGP protocol is intermediate system to intermediate system (IS-IS), the Link State PDU of a network element that is bringing up an IGP adjacency with the DR of the broadcast network is not updated with an IS Reachability TLV (or an Extended IS Reachability TLV) to the broadcast network until LDP is operational with all network elements.

FIG. 1illustrates an exemplary broadcast network where LDP and IDP are not synchronized on a member of the network element that is bringing up an IGP adjacency with a Designated Router (DR) of the broadcast network according to one embodiment of the invention. Initially, the network100includes the network elements105,110,130,150,155,160, and165, and the broadcast pseudo-node120. The network elements110,130, and150are each directly coupled with the broadcast pseudo-node120. Thus, the network elements110,130, and150are part of the broadcast network. After some time, the network element140is brought up on the network100and will be part of the broadcast network. It should be understood that the topology of the network100is exemplary, and other topologies may be used in embodiments of the invention. For example, in some embodiments, a broadcast pseudo-node is not used.

In one embodiment, the network elements105,155, and165provider edge network elements and the network100is a Multiprotocol Label Switching (MPLS) network with Virtual Private Network (VPN) applications. As one example, the network element105may have a LDP LSP path to the network elements155and/or165. It should be understood that other LDP LSP paths may be established in the network100. Thus the network100depends on the establishment of Label Switched Paths (LSPs) by a label distribution protocol (LDP) that is tied to Internet Protocol (IP) forwarding decisions of an interior gateway protocol (IGP).

The network element110acts as a designated router (DR) of the broadcast network. Thus, the network element (DR)110manages the broadcast pseudo-node120. For example, the network element (DR)110generates a unidirectional link from the broadcast pseudo-node120to the members of the broadcast network (e.g., the network elements130,140and150) in the form of a pseudo-node LSA (e.g., a network-LSA in OSPF or a pseudo-node LSP in IS-IS). It should be understood that the election of the network element110to be the DR of the broadcast network is exemplary, and different network element members of the broadcast network may be elected to be the DR in embodiments of the invention described herein.

The network elements130and150are adjacent to the network element (DR)110. In addition, LDP is fully operational on the network elements130and150. The network elements130and150each advertise a pseudo-node adjacency in their LSA (e.g., a router-LSA in the case of OSPF). The network element (DR)110also advertises a pseudo-node adjacency in its LSA. A pseudo-node adjacency represents the link between the broadcast pseudo-node120and the network element. The network elements110,130, and150advertise their LSAs to their neighbors. It should be understood that each pseudo-node adjacency has a cost value (which can be different for different network elements).

The network element (DR)110also advertises the interfaces of the broadcast pseudo-node120to its neighbors (e.g., those network elements that either is adjacent to the network element (DR)110or is bringing up an adjacency with the network element (DR)110) in a pseudo-node LSA (e.g., a network-LSA in OSPF or a pseudo-node LSP in IS-IS). Each of the interfaces122,124,126, and128is advertised with a cost of zero. It should be understood that the interfaces illustrated inFIG. 1are exemplary and other interfaces are not illustrated in order not to confuse understanding of the invention.

For purposes of explanation, the network elements110,130, and150each advertise a pseudo-node adjacency with a cost of 1 on the broadcast interfaces114,132, and152respectively. In addition, for exemplary purposes, the other links in the network100, with the exception of the link between the network element (DR)110and the network element165(which is advertised a cost of 10), are also advertised with a cost of 1.

By way of example, prior to the broadcast network including the network element140, transit traffic between the network element105and the network element155flows along the bidirectional path [network element105network element110network element130network element160network element150], and transit traffic between the network element105and the network element165flows along the bidirectional path [network element105network element110network element150network element165].

As illustrated inFIG. 1, the network element140is bringing up an adjacency to the network element (DR)110(e.g., by performing the bringing up adjacency with DR operation185). Thus, the network element140has exchanged hello packets with the network element (DR)110(thus there is bidirectional IGP communication between the network element140and the network element (DR)110). As illustrated inFIG. 1, the network element (DR)110transmits the pseudo-node LSA196to the network element140over interface126.

In one interpretation of the RFC 5443 “LDP IGP Synchronization” as applied to broadcast networks, when a new network element is discovered on the broadcast network (e.g., is bringing up an adjacency with the DR), all the network elements with direct links to the broadcast network advertise maximum cost to the broadcast network. For example, with reference toFIG. 1, if the broadcast interface142of the network element140becomes operational (e.g., the network element140is bringing up an adjacency with the network element (DR)110over the broadcast interface142while the network elements110,130, and150are each already connected with the broadcast pseudo-node120) and detected by the network elements110,130, and150, those network elements each start advertising maximum cost to the broadcast pseudo-node120. In other words, the network elements110,130, and150react to the network element140coming up on the network by advertising a maximum cost pseudo-node adjacency to the broadcast pseudo-node120. The RFC 5443 defines the value of the maximum cost to be LSInfinity (0xFFFF) for OSPF and (0xFFFFFE) for IS-IS. Since maximum cost is greater than the cost of 10, following this interpretation of the RFC 5443 causes transit traffic between the network element105and the network element165to be diverted to the sub-optimal path of [network element105network element110the network element165] instead of the optimal path [network element105network element110network element150network element165] as described above. Thus, using the interpretation of the RFC 5443 that each network element member of the broadcast network advertising a maximum cost to the broadcast network may result in sub-optimal traffic diversion.

In addition, applying the mechanism described in the RFC 5443 “LDP IGP Synchronization” for broadcast networks can lead to traffic being black-holed (continually dropped) at a network element due to each broadcast network element advertising a maximum cost. For example, using the network topology ofFIG. 1and the same links as the previous example, using this interpretation of the RFC 5443 when the network element140is coming up on the broadcast network, the network element110will have the network element140as the nexthop to the network element155resulting in VPN traffic from the network element105to the network element155being black-holed at the network element110until LDP is operational at the network element140. The amount of traffic loss in this case is at least the order of the time it takes for the LDP LSP to become operational. Although the topology inFIG. 1is rather simple, it should be understood that in some topologies this can be of the order of several minutes (which can violate carrier class reliability metrics).

In another interpretation of the RFC 5443 as applied to broadcast networks, when a new network element is discovered on the broadcast network, only that network element advertises a maximum cost to the broadcast network and the other network elements advertise their normal cost. In this interpretation, for example, the network element140advertises a maximum cost pseudo-node adjacency to the broadcast pseudo-node120while the network elements110,130, and150each advertise their pseudo-node adjacency to the broadcast pseudo-node120at their regular cost. It should be understood that the maximum cost pseudo-node adjacency affects traffic to the broadcast pseudo-node120(i.e., traffic outgoing from the broadcast interface142) and does not affect traffic transmitted to the network element140on the broadcast interface142. For example, from the point of view of the network element (DR)110, the link between the network element110and the network element140will have a cost of 1. Using the same example as above and since IGP will converge faster than LDP, the network element110will try and fail to transmit VPN traffic to the network element155through the network element140until that LDP LSP has been established through the network element140. Thus, similar to the above example, the VPN traffic will be black-holed at the network element110.

In contrast, embodiments of the invention allow for LDP-IGP synchronization in broadcast networks without sub-optimally diverting traffic or black-holing traffic. As illustrated inFIG. 1, responsive to the network element140bringing up an adjacency with the network element (DR)110on the broadcast interface142, the network element140suppresses advertising its pseudo-node adjacency180to the broadcast pseudo-node120(e.g., is not advertised) in its LSA and instead advertises in its LSA a peer-to-peer (P2P) adjacency to each network element listed in the pseudo-node LSA196received from the broadcast pseudo-node120(at least those network elements in the pseudo-node LSA that have bidirectional IGP communication with the network element140). Each P2P adjacency represents a unidirectional link between network elements. For example, the network element140includes in its LSA a P2P adjacency to the network elements110,130, and150, which respectively represent the following unidirectional links: [network element140→network element (DR)110], [network element140→network element130], and [network element140→network element150]. This LSA is advertised to the neighbors of the network element140(e.g., the network elements110,130,150, and155, which then populate the LSA to the rest of the routing domain). Each P2P adjacency is advertised with a high cost (e.g., the maximum cost) to discourage use of the link represented by the P2P adjacency. The value of the high cost is chosen such that those links will be used as last resort links.

It should be understood that the high cost P2P adjacencies advertised by the network element140affect only the traffic outgoing from the network element140(that is, traffic outgoing from the broadcast interface142). Therefore, the other network element members in the broadcast network (the network elements110,130, and150) also each advertise in their LSAs a high cost P2P adjacency on their broadcast interfaces to the network element140. Therefore, the unidirectional links to the network element140in the broadcast network are also advertised with a high cost to discourage use of those links. Therefore as illustrated inFIG. 1, the P2P adjacencies190between the network elements130and140, the P2P adjacencies192between the network elements150and140, and the P2P adjacencies194between the network elements110and140are each advertised throughout the network100. It should be understood that the network elements110,130, and150each continue to advertise a pseudo-node adjacency to the broadcast pseudo-node120in their respective LSAs.

The network element140maintains the suppression of the pseudo-node adjacency and the advertisements of the P2P adjacencies until LDP is operational with its neighbors.FIG. 2illustrates the network ofFIG. 1, where LDP is operational (synchronized with IGP) on the network element140according to one embodiment of the invention.

The network element140stops advertising the P2P adjacencies220to the network elements110,130, and150in its LSA after LDP is operational on the broadcast interface142therefore removing the discouragement of the use of the unidirectional links represented by the P2P adjacencies. In one embodiment, LDP is assumed to be operational upon an LDP-IGP synchronization timer expiring (which is set for a worst case (or best guess) of the time it should take for LDP to become operational). In another embodiment, the network element140may implement the LDP End-of-LIB mechanism as specified in IETF draft “LDP End-of-LIB: draft-ietf-mpls-end-of-lib-03.txt”, January 2009, to determine when LDP is operational. For example, in LDP End-of-LIB IETF draft, each LDP peer (neighbor) may signal completion of its label advertisements following session establishment. After receiving all completion signals from each LDP peer, LDP will be operational with all neighbors. The network element140also unsuppresses the pseudo-node adjacency and advertises the pseudo-node adjacency210to the broadcast pseudo-node120with its regular cost. Thus in the LSA of the network element140, the pseudo-node adjacency is advertised and the P2P adjacencies are no longer advertised.

The network elements110,130, and150, upon receiving an LSA of the network element140that does not include a P2P adjacency, stops advertising their P2P adjacency to the network element140in their respective LSAs thereby removing the discouragement of the use of the unidirectional links represented by those P2P adjacencies to the network element140. Thus, as illustrated inFIG. 2, the P2P adjacencies190,192, and194are no longer advertised.

Thus, unlike the RFC 5443, which would cause at least the network element140to advertise its pseudo-node adjacency for the broadcast interface142with a maximum cost until LDP is operational on the broadcast interface142, in embodiments of the invention, the network element140advertises a high cost P2P adjacency to the members of the broadcast network (at least those members which have bidirectional IGP communication (2-way state) with the network element140) in its LSA instead of the pseudo-node adjacency until LDP is operational on the broadcast interface142. In addition, those other members also advertise a high cost P2P adjacency to the network element140in their LSAs until LDP is operational on the broadcast interface142. As a result, transit traffic is avoided on the broadcast network and is not black-holed or diverted in a sub-optimal path.

FIG. 3is a block diagram of an exemplary network element configured for LDP-IGP synchronization for broadcast networks according to one embodiment of the invention. WhileFIG. 3illustrates the network element140, it should be understood that one or more of the network elements in the network100may include similar features. As illustrated inFIG. 3, the network element140includes the control plane310, which is coupled with the data plane360. The control plane310includes the command line interface330, the IGP module320, the interface state manager335, the LDP module340, and the label manager350. The IGP module320includes the neighbor state machine380and the LDP-IGP synchronization LSA module385. The IGP module320manages the neighbor adjacency table322, the link state database324, the local IGP RIB (routing information base)326, and the local IGP interface structure328.

The IGP module320may receive configuration parameters for LDP-IGP synchronization for broadcast networks from the command line interface330. For example, a network administrator may use the command line interface330to configure the LDP-IGP synchronization for broadcast networks on the network element140(e.g., whether the LDP-IGP synchronization for broadcast networks is enabled, one or more interfaces to monitor for LDP-IGP synchronization for broadcast networks, etc.). In another embodiment, the LDP-IGP synchronization for broadcast networks mechanism is installed for each broadcast interface on the network element140.

The interface state manager335manages the interfaces of the network element140, including the broadcast interface142. For example, the interface state manager335detects when an interface is operational. The interface state manager335is coupled with the IGP module320. The IGP module320registers those broadcast interfaces (e.g., the interfaces as specified during configuration) with the interface state manager335. The interface state manager335notifies the IGP module320upon a state change of one of those registered interfaces (e.g., a broadcast interface becoming operational, a broadcast interface going down, etc.). The IGP module320may then update the local IGP interface structure328with those interfaces.

The IGP module320establishes and maintains neighbor adjacencies with other network elements in the network100. For example, the IGP module320transmits and receives hello packets from other network elements in the network100. From these hello packets, the IGP module320creates and maintains the neighbor adjacency table322.

The IGP module320also transmits and receives link-state information (typically in the form of link-state advertisements (LSAs)) to construct a topology of the network100. From the LSAs it receives and transmits, the IGP module320creates and maintains the link state database324(thus the link state database324is a representation of the network topology of the network100).

The IGP module320also includes the neighbor state machine380. According to one embodiment when the IGP is OSPF, the neighbor state machine380operates as defined in the RFC 2328. For example, the neighbor state machine380manages the different neighbor state changes that occur (e.g., the states when establishing bidirectional IGP communication, the states when establishing an adjacency, etc.).

In one embodiment, the IGP module320also includes a shortest path first (SPF) process to determine the optimum paths to destinations of the link state database324(thus the SPF process is applied to the information of the link state database324). The routes selected are added to the local IGP RIB326, which are then programmed to one or more FIBs370(forwarding information bases) on the data plane360. The routes may also be programmed to a main RIB on the control plane.

As previously described, the IGP module320transmits and receives LSAs to construct the topology of the network100. The IGP module320includes the LDP-IGP synchronization LSA module385which excludes the pseudo-node adjacency from its LSAs for a broadcast interface until LDP is operational on that broadcast interface. In one embodiment, if LDP is not fully operational for a broadcast interface, the LDP-IGP synchronization LSA module385sets a suppress pseudo-node adjacency from LSA flag for that interface in the local IGP interface structure328.

The LDP module340negotiates labels with the other network elements in the network100. In one embodiment, the LDP module340determines when LDP is fully operational for a particular broadcast interface and notifies the IGP module320that LDP is fully operational for that interface. The IGP module320may then clear the suppress pseudo-node adjacency from LSA flag if it has been set (and then advertise that pseudo-node adjacency). The LDP module340is also coupled with the label manager350, which creates and maintains the LSP structure(s)355which, among other things, create and manage the labels for the LSPs. The labels are programmed to one or more label forwarding information bases (LFIBs) in the data plane360. For example, the labels stored in the LSP structure(s)355are programmed to one or more packet processing units of one or more line cards in the network element140.

FIG. 4is a flow diagram illustrating exemplary operations performed on a network element member of the broadcast network that is bringing up an IGP adjacency with the DR of the broadcast network to discourage use of a broadcast network interface for transit traffic until LDP is operational with all neighbors of that network element member according to one embodiment of the invention. The operations ofFIG. 4will be described with reference to the exemplary embodiments ofFIGS. 1-3. However, it should be understood that the operations ofFIG. 4can be performed by embodiments of the invention other than those discussed with reference toFIGS. 1-3, and the embodiments discussed with reference toFIGS. 1-3can perform operations different than those discussed with reference toFIG. 4.

As illustrated inFIG. 4, the network element140is performing the operations400. The operations400begin at block410where an adjacency is coming up with the network element (DR)110on the broadcast interface142. Flow moves to block415, where the IGP module320receives the pseudo-node LSA196from the designated router. The pseudo-node LSA196includes an indication of each network element member of the broadcast network (e.g., the network elements110,130, and150). Flow moves from block415to block420.

At block420, the IGP module320determines whether LDP is operational with all neighbors on the broadcast interface142. According to one embodiment of the invention, the LDP-IGP synchronization module385operates an LDP-IGP synchronization timer which is set for an estimate on the time it should take for LDP to become operational. Upon that timer expiring, the LDP-IGP synchronization module385assumes that LDP is operational (and thus LDP and IGP are synchronized). In another embodiment, the LDP-IGP synchronization module385implements the draft IETF LDP End-of-LIB mechanism as described previously herein. If LDP is operational with all neighbors on the broadcast interface142, then flow moves to block450where the adjacency up processing continues as normal, otherwise flow moves to block425.

At block425, the IGP module320suppresses advertising a pseudo-node adjacency to the broadcast pseudo-node120. Suppressing that pseudo-node adjacency causes that pseudo-node adjacency not to be included in the link state database324. The IGP module320also sets a suppress pseudo-node adjacency from LSA flag for the broadcast interface142in the local IGP interface structure328. Flow moves from block425to block430.

At block430, the IGP module320inserts a high cost P2P adjacency to those members listed in the pseudo-node LSA that has bidirectional IGP communication with the network element140in its LSA and advertises that LSA to its neighbors. With reference toFIG. 1, P2P adjacencies at a high cost to the network elements110,130, and150are advertised in the LSA for the broadcast interface142(assuming they each have bidirectional IGP communication with the network element140) to the network elements110,130,150, and155. The high cost P2P adjacencies discourages transit traffic from being transmitted through the broadcast interface142towards the network elements110,130, and150. As will be described in greater detail later herein, the high cost P2P adjacencies also serve as an indication to the network elements110,130, and150that LDP is not yet operational on the broadcast interface142of the network element140. Flow moves from block430to block435where the neighbor state machine380of the IGP module320continues the adjacency up processing.

Flow moves to block435to block440, where the IGP module320determines whether LDP is operational with all neighbors on the broadcast interface142. The OSPF module determines whether LDP is operational as described above with reference to block420. If LDP is not operational, then flow moves back to block440where the IGP module320continues to wait until LDP is operational. However, if LDP is operational, then flow moves to block445.

At block445, the IGP module removes the P2P adjacencies from the LSA and inserts the pseudo-node adjacency in the LSA and advertises that LSA. With reference toFIG. 2, the P2P adjacencies from the network element140to the network elements110,130, and150have ceased being advertised and have been replaced with the pseudo-node adjacency to the broadcast pseudo-node120, thereby removing the discouragement of the use of the broadcast interface142for outgoing transit traffic. As will be described in greater detail later herein, replacing the P2P adjacencies with the pseudo-node adjacency also serves as an indication to the network elements110,130, and150that LDP is now operational on the broadcast interface of the network element140.

FIGS. 5A and 5Bare flow diagrams illustrating exemplary operations performed on the network element (DR)110. The operations ofFIGS. 5A-Bwill be described with reference to the exemplary embodiments ofFIGS. 1 and 2. However, it should be understood that the operations ofFIGS. 5A-Bcan be performed by embodiments of the invention other than those discussed with reference toFIGS. 1 and 2, and the embodiments discussed with reference toFIGS. 1 and 2can perform operations different than those discussed with reference toFIGS. 5A-B.

As illustrated inFIG. 5A, the network element (DR)110performs the operations500. The operations500begin at block510where an adjacency is established with a neighbor (e.g., the network element140) that is coming up on the network. At this point in time, the network element (DR)110assumes that LDP will not be operational since the network element140has just established an IGP adjacency (and thus transit traffic should not yet be sent to the network element140). Thus, flow moves to block515where the IGP module advertises a high cost P2P adjacency to the network element140in its LSA to discourage use of the link to the network element140to transmit transit traffic. Flow moves from block515to block520to continue the normal adjacency up processing steps.

As illustrated inFIG. 5B, the network element (DR)110performs the operations525. At block530, the IGP module of the network element (DR)110receives an LSA from a neighbor that was advertised a P2P adjacency (e.g., an LSA for the broadcast interface142of the network element140). Flow moves from block530to block535. As described above with reference toFIG. 4, the high cost P2P adjacency advertised by the network element140for the broadcast interface142serves as an indication that LDP is not operational on the broadcast interface142(and thus transit traffic should be avoided being sent towards the broadcast interface142). Therefore, at block535, the IGP module of the network element (DR)110determines whether the received LSA includes a P2P adjacency. If the LSA includes a P2P adjacency, then flow moves to block545where the IGP module continues with LSA receipt processing. However, if the LSA does not include a P2P adjacency, then flow moves to block540.

As described above, receiving an LSA from the network element140for the broadcast interface142that does not include a P2P adjacency serves as an indication that LDP is operational on that interface and that transit traffic may be sent toward the network element140(or at least considered by a SPF algorithm with its normal cost). Therefore, at block540, the IGP module of the network element (DR)110removes the P2P adjacency to the network element140from its LSA, which removes the discouragement of transmitting transit traffic to that network element. With reference toFIG. 2, the network elements110and140have stopped advertising the P2P adjacencies194thereby removing the discouragement of the use of the bidirectional link between the network elements110and140for transmission of transit traffic. Flow moves from block540to block545where the IGP module continues with LSA receipt processing.

FIG. 6Ais a flow diagram illustrating exemplary operations performed on a network element member of the broadcast network that is adjacent to the DR of the broadcast network responsive to receiving a pseudo-node LSA according to one embodiment of the invention. The operations ofFIG. 6Awill be described with reference to the exemplary embodiments ofFIG. 1. However, it should be understood that the operations ofFIG. 6Acan be performed by embodiments of the invention other than those discussed with reference toFIG. 1, and the embodiments discussed with reference toFIG. 1can perform operations different than those discussed with reference toFIG. 6A.

As illustrated inFIG. 6A, the network element130performs the operations600. However, it should be understood that other network elements in the network100perform similar operations (e.g., the network element150). At block610, the IGP module of the network element130receives a pseudo-node LSA of the broadcast pseudo-node120. Flow moves from block610to block615.

The operations in blocks615-630are performed for each neighbor listed in the pseudo-node LSA. For explanatory purposes, the operations of blocks615-630will be described with reference to the network element140. At block615, the IGP module of the network element130determines whether there is bidirectional IGP communication with network element140. If there is not bidirectional IGP communication, then flow moves to block635where LSA receipt processing continues. It should be understood that if there is not bidirectional IGP communication, the bidirectional check during execution of the SPF will fail resulting in that link not being used to transmit transit traffic (thus there is no need to advertise a high cost P2P adjacency for that link). If there is bidirectional IGP communication, then flow moves to block620.

At block620, the IGP module determines whether the network element140is currently advertising a P2P adjacency to the network element130(e.g., whether the latest LSA received from the network element140includes a high cost P2P adjacency). In one embodiment the IGP module accesses its LSDB to determine whether the network element140is advertising a P2P adjacency. If the network element140is not advertising a P2P adjacency, then flow moves to block635where LSA receipt processing continues. However, if the network element140is advertising a P2P adjacency, then flow moves to block625. By way of example, the network element140is currently advertising a P2P adjacency to the network element130.

At block625, the IGP module adds a high cost P2P adjacency to the network element140in its own LSA to discourage use of the link to the network element140for transit traffic. Flow then moves to block630where the LSA is advertised (e.g., flooded). With reference toFIG. 1, the P2P adjacencies190between the network elements130and140are advertised. Thus in each unidirectional direction, a high cost P2P adjacency has been advertised which discourages use of the bidirectional link between the network elements130and140for transit traffic. Flow then moves to block635.

FIG. 6Bis a flow diagram illustrating exemplary operations performed on a network element member of the broadcast network that is adjacent to the DR of the broadcast network responsive to establishing bidirectional IGP communication with a neighbor network element member of the broadcast network according to one embodiment of the invention. The operations ofFIG. 6Bwill be described with reference to the exemplary embodiments ofFIGS. 1 and 2. However, it should be understood that the operations ofFIG. 6Bcan be performed by embodiments of the invention other than those discussed with reference toFIGS. 1 and 2, and the embodiments discussed with reference toFIGS. 1 and 2can perform operations different than those discussed with reference toFIG. 6B.

As illustrated inFIG. 6B, the network element130performs the operations640. However, it should be understood that other network elements in the network100perform similar operations (e.g., the network element150). At block645, bidirectional IGP communication has been established with a neighbor (e.g., a neighbor listed in the pseudo-node LSA being advertised by the DR). Flow moves to block650, where the IGP module of the network element130determines whether the neighbor is currently advertising a P2P adjacency to the network element130(e.g., similar to operation of block620). If the neighbor is not advertising a P2P adjacency, then flow moves to block665where LSA receipt processing continues. However, if the neighbor is advertising a P2P adjacency, then flow moves to block655.

At block655, the IGP module of the network element130adds a high cost P2P adjacency to that neighbor in its LSA to discourage use of that link for transit traffic. Flow then moves to block660where the LSA is advertised (e.g., flooded). Flow then moves to block655.

FIG. 6Cis a flow diagram illustrating exemplary operations performed on a network element member of the broadcast network that is adjacent to the DR of the broadcast network responsive to receiving an LSA of a neighbor network element of the broadcast network according to one embodiment of the invention. The operations ofFIG. 6Cwill be described with reference to the exemplary embodiments ofFIGS. 1 and 2. However, it should be understood that the operations ofFIG. 6Ccan be performed by embodiments of the invention other than those discussed with reference toFIGS. 1 and 2, and the embodiments discussed with reference toFIGS. 1 and 2can perform operations different than those discussed with reference toFIG. 6C.

As illustrated inFIG. 6C, the network element130performs the operations695. However, it should be understood that other network elements in the network100perform similar operations (e.g., the network element150). At block675, the IGP module of the network element130receives an LSA from a neighbor (e.g., the network element140). As described above with reference toFIG. 4, the high cost P2P adjacency advertised by the network element140serves as an indication LDP is not operational on the broadcast interface142(and thus transit traffic should be avoided being transmitted towards the broadcast interface142). Therefore, at block680, the IGP module determines whether the LSA includes a high cost P2P adjacency. If the LSA includes a P2P adjacency, then flow moves to block690where LSA receipt processing continues. However, if the LSA does not include a P2P adjacency, then flow moves to block685.

As described above, receiving an LSA from the network element140that does not include a P2P adjacency serves as an indication that LDP is operational on the broadcast interface142and that transit traffic may be sent toward the network element140(or at least considered by a SPF algorithm with its normal cost). Therefore, at block685, the IGP module of the network element130removes the P2P adjacency to the network element140from its LSA if one exists, which removes the discouragement of transmitting transit traffic to that network element. With reference toFIG. 2, the network elements130and140have stopped advertising the P2P adjacencies194thereby removing the discouragement of the use of the bidirectional link between the network elements130and140for transmission of transit traffic. Flow moves from block685to block690where the IGP module continues with LSA receipt processing.

Thus unlike the RFC 5443 as applied to broadcast networks, the LDP-IGP synchronization mechanism described herein does not lead to transit traffic being black-holed or transit traffic from being diverted to sub-optimal paths as it is a zero-traffic-loss procedure. Therefore carrier class reliability metrics, which can easily be violated in a network that applies the RFC 5443 to broadcast networks when a link comes up, are sustained using the LDP-IGP synchronization mechanism described herein.