CROSS-REFERENCE TO RELATED APPLICATIONS

[0001] This patent application claims the benefit of U.S. Provisional Patent Application No. 63/347,284 filed May 31, 2022 by Futurewei Technologies, Inc., and titled “OSPF for Source Address Validation,” which is hereby incorporated by reference.

TECHNICAL FIELD

[0002] The present disclosure relates to network communication and, in particular, to source address validation in an open shortest path first (OSPF) domain.

BACKGROUND

[0003] OSPF is a link-state routing protocol using Link State Advertisement (LSA) to exchange routing information between routers/nodes. Every node in the OSPF domain builds and maintains its own source address validation (SAV) table. When receiving a packet from an interface, the node checks or validates the packet using its SAV table. If the source address and the receiving/incoming interface of the packet are not in the SAV table, the packet is blocked or dropped. An architecture for validating source addresses is described in further detail in Internet Engineering Task Force (IETF) document Request for Comments (RFC) 8704 entitled “Enhanced Feasible-Path Unicast Reverse Path Forwarding” by K. Sriram, et al., published February 2020.

SUMMARY

[0004] The disclosed aspects/embodiments provide an enhanced distributed architecture/framework of OSPF for SAV. The enhanced architecture is configured to build SAV tables for both symmetric and asymmetric forwarding paths to mitigate source address spoofing and to improve packet routing and network scalability within the OSPF domain.

[0005] A first aspect relates to a method implemented by a network node in an open shortest path first (OSPF) domain, comprising: accessing a network topology of the OSPF domain in a link state database (LSDB); and when a forwarding path in the OSPF domain is asymmetric, receiving a first link state advertisement (LSA) from a first source network node through a first interface; building a source address validation (SAV) table using the first LSA; and generating a second LSA and a third LSA. [0006] Optionally, in any of the preceding aspects, another implementation of the aspect further comprises accessing the network topology comprises determining whether every forwarding path is symmetric, and wherein the forwarding path is determined to be symmetric when every link in the network topology in the LSDB has equal cost metric from a source to a destination and from the destination to the source.

[0007] Optionally, in any of the preceding aspects, another implementation of the aspect provides that the first LSA comprises an identifier of the first source network node, a number of destination prefixes, and a prefix length of each of the destination prefixes.

[0008] Optionally, in any of the preceding aspects, another implementation of the aspect further comprises generating the second LSA based on the first LSA and the FIB or the RIB, wherein the second LSA comprises a Paths Type-Length-Value (TLV) with the first source network node and a plurality of destinations consisting of destination prefixes and prefix lengths in the first LSA, and wherein the destinations have a first same next hop interface to a first same next hop node in the RIB or the FIB; and forwarding, through the first same next hop interface, the second LSA to the first same next hop node.

[0009] Optionally, in any of the preceding aspects, another implementation of the aspect further comprises generating the third LSA based on the FIB or the RIB, wherein the third LSA comprises a Paths TLV with the first source network node as a second source network node and a second plurality of destinations consisting of destination prefixes and prefix lengths from the FIB or the RIB, and wherein the destinations have a second same next hop interface to a second same next hop node in the RIB or the FIB; and forwarding, through the second same next hop interface, the third LSA to the second same next hop node.

[0010] Optionally, in any of the preceding aspects, another implementation of the aspect provides that each of the first LSA, the second LSA, and the third LSA comprises a Paths Type- Length-Value (TLV) and is an OSPFv2 Extended Prefix Opaque LSA of type 9 or an OSPFv3 Extended Link LSA.

[0011] Optionally, in any of the preceding aspects, another implementation of the aspect provides that using the FIB or the RIB to build the SAV table comprises updating the SAV table by creating a row in the SAV table for each prefix with a next hop interface in the FIB or the RIB, and wherein the row comprises the prefix and the next hop interface.

[0012] Optionally, in any of the preceding aspects, another implementation of the aspect provides that using a forwarding information base (FIB) or a routing information base (RIB) to build the SAV table when every forwarding path in the OSPF domain is symmetric. [0013] Optionally, in any of the preceding aspects, another implementation of the aspect provides that building the SAV table using the first LSA comprises creating a row in the SAV table for each prefix attached to the first source network node in the first LSA, and wherein the row comprises the prefix and the first interface.

[0014] A second aspect relates to a network node in an open shortest path first (OSPF) domain, comprising: a memory storing instructions; and a processor coupled to the memory, the processor configured to execute the instructions to cause the network node to access a network topology of the OSPF domain in a link state database (LSDB); and when a forwarding path in the OSPF domain is asymmetric, receive a first link state advertisement (LSA) from a first source network node through a first interface; build a source address validation (SAV) table using the first LSA; and generate a second LSA and a third LSA.

[0015] Optionally, in any of the preceding aspects, another implementation of the aspect provides that the processor is configured to execute the instructions to further cause the network node to determine whether every forwarding path is symmetric, and wherein the forwarding path is determined to be symmetric when every link in the network topology in the LSDB has equal cost metric from a source to a destination and from the destination to the source.

[0016] Optionally, in any of the preceding aspects, another implementation of the aspect provides that the first LSA comprises an identifier of the first source network node, a number of destination prefixes, and a prefix length of each of the destination prefixes.

[0017] Optionally, in any of the preceding aspects, another implementation of the aspect provides that the processor is configured to execute the instructions to further cause the network node to generate the second LSA based on the first LSA and the FIB or the RIB, wherein the second LSA comprises a Paths Type-Length-Value (TLV) with the first source network node and a plurality of destinations consisting of destination prefixes and prefix lengths in the first LSA, and wherein the destinations have a first same next hop interface to a first same next hop node in the RIB or the FIB; and forward, through the first same next hop interface, the second LSA to the first same next hop node.

[0018] Optionally, in any of the preceding aspects, another implementation of the aspect provides that the processor is configured to execute the instructions to further cause the network node to generate the third LSA based on the FIB or the RIB, wherein the third LSA comprises a Paths TLV with the first source network node as a second source network node and a second plurality of destinations consisting of destination prefixes and prefix lengths from the FIB or the RIB, and wherein the destinations have a second same next hop interface to a second same next hop node in the RIB or the FIB; and forward, through the second same next hop interface, the third LSA to the second same next hop node.

[0019] Optionally, in any of the preceding aspects, another implementation of the aspect provides that each of the first LSA, the second LSA, and the third LSA comprises a Paths Type- Length-Value (TLV) and is an OSPFv2 Extended Prefix Opaque LSA of type 9 or an OSPFv3 Extended Link LSA.

[0020] Optionally, in any of the preceding aspects, another implementation of the aspect provides that when the forwarding path in the OSPF domain is asymmetric, the processor is configured to execute the instructions to further cause the network node to create a row in the SAV table for each prefix attached to the first source network node in the first LSA, and wherein the row comprises the prefix and the first interface.

[0021] Optionally, in any of the preceding aspects, another implementation of the aspect provides that the processor is configured to execute the instructions to further cause the network node to use a forwarding information base (FIB) or a routing information base (RIB) to build the SAV table when every forwarding path in the OSPF domain is symmetric.

[0022] Optionally, in any of the preceding aspects, another implementation of the aspect provides that when every forwarding path in the OSPF domain is symmetric, the processor is configured to execute the instructions to further cause the network node to update the SAV table by creating a row in the SAV table for each prefix with a next hop interface in the FIB or the RIB, and wherein the row comprises the prefix and the next hop interface.

[0023] A third aspect relates to a method implemented by a network node in an open shortest path first (OSPF) domain comprising: computing a shortest path in the OSPF domain from the network node to each of other nodes in a reverse direction; and constructing a source address validation (SAV) table by adding an entry for each prefix attached to a first node when the shortest path is computed from the network node to the first node in the reverse direction.

[0024] Optionally, in any of the preceding aspects, another implementation of the aspect provides that computing the shortest path from the network node to a destination comprises computing the shortest path based on a link metric or cost of each link along a path from the destination to the network node.

[0025] Optionally, in any of the preceding aspects, another implementation of the aspect provides that the entry comprises the prefix and an interface in a source prefix column and incoming interface columns, respectively of the SAV table, and wherein the interface is of the network node on the shortest path. [0026] A fourth aspect relates to a network node in an open shortest path first (OSPF) domain, comprising: a memory storing instructions; and a processor coupled to the memory, the processor configured to execute the instructions to cause the network node to compute a shortest path in the OSPF domain from the network node to each of other nodes in a reverse direction; and construct a source address validation (S AV) table by adding an entry for each prefix attached to a first node when the shortest path is computed from the network node to the first node in the reverse direction.

[0027] Optionally, in any of the preceding aspects, another implementation of the aspect provides that the processor is configured to execute the instructions to further cause the network node to compute the shortest path from the network node to a destination based on a link metric or cost of each link along a path from the destination to the network node.

[0028] Optionally, in any of the preceding aspects, another implementation of the aspect provides that the entry comprises the prefix and an interface in a source prefix column and incoming interface columns, respectively of the SAV table, and wherein the interface is of the network node on the shortest path.

[0029] A fifth aspect relates to a non-transitory computer readable medium comprising a computer program product for use by a network node in an open shortest path first (OSPF) domain, the computer program product comprising computer executable instructions stored on the non-transitory computer readable medium that, when executed by one or more processors, cause the network node to execute the method in any of the disclosed embodiments.

[0030] A sixth aspect relates to means for accessing a network topology of the OSPF domain in a link state database (LSDB); and when a forwarding path in the OSPF domain is asymmetric, means for receiving a first link state advertisement (LSA) from a first source network node through a first interface; means for building a source address validation (SAV) table using based on the first LSA; and means for generating a second LSA and a third LSA.

[0031] A seventh aspect relates to a network node in an open shortest path first (OSPF) domain, comprising means for computing a shortest path in the OSPF domain from the network node to each of other nodes in a reverse direction; and means for constructing a source address validation (SAV) table by adding an entry for each prefix attached to a first node when the shortest path is computed from the network node to the first node in the reverse direction [0032] For the purpose of clarity, any one of the foregoing embodiments may be combined with any one or more of the other foregoing embodiments to create a new embodiment within the scope of the present disclosure. [0033] These and other features will be more clearly understood from the following detailed description taken in conjunction with the accompanying drawings and claims.

BRIEF DESCRIPTION OF THE DRAWINGS

[0034] For a more complete understanding of this disclosure, reference is now made to the following brief description, taken in connection with the accompanying drawings and detailed description, wherein like reference numerals represent like parts.

[0035] FIG. 1 is a schematic diagram of a network topology including an OSPF domain according to an embodiment of the disclosure.

[0036] FIG. 2 is a schematic diagram of a format of SAV table and a format of Forwarding Information Base (FIB) of a network node according to an embodiment of the disclosure.

[0037] FIG. 3 is a schematic diagram of a reference architecture of OSPF for SAV according to an embodiment of the disclosure.

[0038] FIG. 4 is a schematic format of paths type length value (TLV) for an Internet Protocol version 4 (IPv4) according to an embodiment of the disclosure.

[0039] FIG. 5 is a schematic diagram illustrating a format of an OSPF version 2 (OSPFv2) Extended Prefix Opaque LSA with Paths TLV according to an embodiment of the disclosure.

[0040] FIG. 6 is a schematic format of paths type length value (TLV) for an Internet Protocol version 6 (IPv6) according to an embodiment of the disclosure.

[0041] FIG. 7 is a schematic diagram illustrating a format of an OSPF version 3 (OSPFv3) Extended Prefix Opaque LSA with Paths TLV according to an embodiment of the disclosure.

[0042] FIG. 8 is a schematic diagram of link state (LS) Type according to an embodiment of the disclosure.

[0043] FIG. 9 is a method implemented by a network node in the OSPF domain according to an embodiment of the disclosure.

[0044] FIG. 10 is a method implemented by a network node in the OSPF domain according to an embodiment of the disclosure.

[0045] FIG. 11 is a schematic diagram of a network apparatus according to an embodiment of the disclosure.

DETAILED DESCRIPTION

[0046] It should be understood at the outset that although an illustrative implementation of one or more embodiments are provided below, the disclosed systems and/or methods may be implemented using any number of techniques, whether currently known or in existence. The disclosure should in no way be limited to the illustrative implementations, drawings, and techniques illustrated below, including the exemplary designs and implementations illustrated and described herein, but may be modified within the scope of the appended claims along with their full scope of equivalents.

[0047] The OSPF protocol, defined in RFC 2328 entitled “OSPF Version 2” by J. Moy, published April 1998, is an interior gateway protocol used to distribute link state information within a single autonomous system. Every router running OSPF gathers link state information from available routers and constructs a topology map of the network. The topology is used by the router to compute a routing table for routing packets.

[0048] The disclosed aspects/embodiments provide an enhanced distributed architecture/fram ework of OSPF for SAV. The enhanced distributed architecture is configured to build SAV tables for both symmetric and asymmetric forwarding paths to mitigate source address spoofing and to improve packet routing and network scalability within the OSPF domain. In such a manner, the source information will be distributed through all possible forwarding paths originated from the source.

[0049] FIG. 1 is a schematic diagram of a network topology 100 including an OSPF domain 102. The OSPF domain 102 comprises a plurality of network nodes 104, 106, 108, 110, 112, 114, and 116. While seven network nodes 104-116 are shown in the OSPF domain 102, more or fewer nodes may be included in practical applications.

[0050] For ease of discussion, all of the network nodes 104-116 have been given a letter designation. For example, the network node 104 has the designation A, the network node 106 has the designation B, the network node 108 has the designation C, the network node 110 has the designation D, the network node 112 has the designation E, the network node 114 has the designation F, and the network node 116 has the designation G.

[0051] Each of the network nodes 104-116 is a forwarding router. Some of the network nodes, namely the network nodes 104, 110, 114 and 116, are disposed at an edge of the OSPF domain 102. The network nodes 104, 110, 114 and 116 receiving packets from outside the OSPF domain 102 may be referred to as an upstream node/an ingress node. The network nodes 104, 110, 114, and 116 transmitting packets out of the OSPF domain 102 may be referred to as a downstream node/an egress node. Depending on the direction of packet traffic, each of the network nodes 104-116 may function as an ingress node or an egress node.

[0052] Each of the network nodes 104, 110, 114, and 116 may be referred to herein as a destination network node. Each of the network nodes 104-116 has one or more neighbor nodes. As used herein, a neighbor node refers to a network node that is one hop away from the network node. For example, network node 106 has four neighbor nodes in FIG. 1, namely network node 104, network node 108, network node 112, and network node 114. Indeed, each of network node 104, network node 108, network node 112, and network node 114 are one hop away from network node 106.

[0053] The network nodes 104-116 in FIG. 1 are coupled to, and communicate with each other, via links 120. The links 120 may be wired, wireless, or some combination thereof. Each of the links 120 have a cost. In an embodiment, the forwarding paths in the OSPF domain 102 may be computed by a routing protocol such as, for example, an OSPF Protocol. In an embodiment, one or more of the network nodes 104-116 may request that a network controller calculate the forwarding paths through the OSPF domain 102. Once calculated, the forwarding paths may be distributed to one or more of the network nodes 104-116 by the network controller. [0054] FIG. 2 is a schematic diagram 200 of a format of SAV table 202 and a format of FIB 204 of a network node (e.g., network node 104). Each of the network nodes 104-116 in the network topology 100 in FIG. 1 derives a SAV table. The SAV table stores SAV rules on the data plane. Each of the network nodes 104-116 builds and maintains its own SAV table. Each node queries its local SAV table to validate the authenticity of source addresses. The SAV table 202 comprises two columns: a list of source prefixes and incoming interfaces (or incoming interface addresses/incoming ports). For example, the network node 104 has a source prefix of prefix- 1 and has an incoming interface of interface-a, has a source prefix of prefix-2 and has an incoming interface of interface-b, and so on. The SAV table 202 is sent to the data plane and used to check or validate the source address of a packet. Source address validation verifies that a packet has been sent from a valid source address. When a packet arrives on an interface, the router performs a SAV table lookup using the source prefix. The result from the SAV table lookup is an interface from which the packet received. The interface obtained from the SAV table 202 must match the interface on which the packet arrived. If it does not match, the router blocks or drops the packet.

[0055] The format of the FIB table 204 comprises two columns: a list of destination prefixes and outgoing interfaces (or outgoing interface addresses/outgoing ports). The existing SAV mechanisms are based on FIBs that do not validate the authenticity of the source address for the traffic received from all directions (e.g., asymmetric paths). Thus, an enhanced distributed architecture/framework of OSPF for SAV is disclosed.

[0056] FIG. 3 is a schematic diagram of a distributed reference architecture 300 of OSPF for SAV according to an embodiment of the disclosure. For the purpose of discussion, the reference architecture of FIG. 3 may be referred to herein as a distributed architecture. The disclosed distributed reference architecture 300 provides a framework to generate SAV tables on nodes for both symmetric and asymmetric forwarding paths using an OSPF control plane to mitigate source address spoofing and to improve packet routing and network scalability within the OSPF domain. In an embodiment, the network node is one of the network nodes 104, 106, 108, 110, 112, 114, 116, and 116 in the OSPF domain 102 of FIG. 1.

[0057] As shown in FIG. 3, the reference architecture 300 of OSPF for SAV includes an upstream network node 302, a transit network node 304, and a downstream network node 306. The transit network node 304 comprises an OSPF control plane 308, a routing table manager (RTM) 310, and a data plane 312. In an embodiment, the reference architecture 300 of OSPF for SAV may include additional components in practical applications.

[0058] The OSPF control plane 308 handles all routing protocol control traffic and includes a link state database (LSDB) 314 that contains the topology of the OSPF domain 102. The LSDB 314 is built by the transit network node using information contained in link state advertisements (LSAs) received from other network nodes in the OSPF domain 102. The LSDB 314 is synchronized between the network nodes within the same area (e.g., the OSPF domain 102). The OSPF control plane 308 further includes a SAV table 316. The SAV table 316 stores a list of source prefixes and incoming interface generated by the transit node 304. In an embodiment, the network node accesses the network topology in the LSDB 314 to determine whether a forwarding path is symmetric or asymmetric to build the SAV table 316 accordingly. In an embodiment, the forwarding path is determined to be symmetric when every link in the network topology in the LSDB has equal cost metric from a source to a destination and from the destination to the source. As shown in FIG. 3, the OSPF control plane 308 is coupled to the upstream network node 302 by way of the la interface and to the downstream network node 306 by way of the lb interface. In an embodiment, the la interface and the lb are bi-directional.

[0059] The RTM 310 includes a routing information base (RIB)/FIB 318. The RTM 310 configured to store routing tables and/or forwarding tables in a storage unit. After being stored, the RTM 310 may access, update, delete, etc., the routing and/or forwarding tables. As shown, the RTM 310 is coupled to the OSPF control plane 308 by way of the la’ interface. In an embodiment, the la’ interface is bi-directional.

[0060] The data plane 312 handles all the data traffic and receives the SAV table 316 from the control plane 308. The SAV table 316 contains the entries built by the transit network node. As shown, the data plane 312 is coupled to the OSPF control plane 308 by way of the lb’ interface. In an embodiment, the lb’ interface is bi-directional. The control plane 308 comprises software configured to manage or instruct the data plane 312. By contrast, the data plane 312 contains the part of the software that processes data requests. The data plane 312 may also be referred to as the forwarding plane. In an embodiment, the OSPF control plane 308 sends the SAV table 316 to the data plane 312. That is, the data plane 312 receives the SAV table 316 from the OSPF control plane 308.

[0061] In an embodiment, each network node in the OSPF domain 102 of FIG. 1 builds its own SAV table by utilizing the reference architecture 300 as depicted in FIG. 3. In an embodiment, the upstream network node/source network node 302 originates a first LSA carrying the destination prefixes which have a same next hop node. The first LSA comprises a Paths TLV. The Paths TLV comprises an identifier of the source network node, a number of destination prefixes, and a prefix length of each of the destination prefixes. The first LSA is of type 9 link-local scope. The first LSA is an OSPFv2 Extended Prefix Opaque LSA of type 9 or an OSPFv3 Extended Link LSA.

[0062] The upstream network node 302 advertises the first LSA to the next hop node within the OSPF domain 102. The OSPF control plane 308 in a network node receives the first LSA from the upstream/ source network node 302 at interface la. The OSPF control plane 308 accesses the network topology in its LSDB 314 to determine whether distributing forwarding paths are needed (i.e., there is a path that is asymmetric) or not needed (i.e., all the paths are symmetric). [0063] In one embodiment, determining whether distributing forwarding paths is needed is through determining whether every forwarding path is symmetric. A forwarding path from a source to a destination is symmetric means that the path from the source to the destination goes through the same links and nodes as the path from the destination to the source. In one embodiment, whether every forwarding path in the OSPF domain 102 or area is symmetric is determined by whether every link in the network topology in LSDB 314 has the same metric or cost in both directions. For example, for a link 120 between network node 104 (i.e., node A) and network node 106 (i.e., node B), the link has the same metric or cost in both directions means that the link from node A to node B has the same metric or cost as the link from B to A. If every link in the network topology in LSDB 314 has the same metric or cost in both directions, then every forwarding path in an OSPF domain or area is symmetric; otherwise, there may be an asymmetric path in the OSPF domain or area in which a packet traverses from the source to the destination in one path and takes a different path when it returns to the source.

[0064] As depicted in FIG. 3, through interface la’, the OSPF control plane 308 in a network node accesses the forwarding paths in RIB/FIB 318 and distributes the paths if needed. In a first case, when distributing forwarding paths are not needed (i.e., all the paths are symmetric), the OSPF control plane 308 in the network node builds the SAV table 316 using the RIB/FIB 318 in the network node through interface la’. For building the SAV table using the RIB/FIB 318, the OSPF control plane 308 includes a row in the SAV table 316 for each prefix with a next hop interface in the RIB/FIB 318. The row contains the prefix and the interface in the source prefix and incoming interface columns respectively. For example, suppose that each node in FIG. 1 has a prefix, which is named by prefix-node-name (e.g., node A has prefix- A). The RIB/FIB in each node contains the prefix of each of the other nodes. The RIB/FIB in network node 110 (a.k.a., network node D) contains prefix-A with interface to next hop C, prefix-B with interface to next hop C, prefix-C with interface to next hop C, prefix-E with interface to next hop E, prefix-F with interface to next hop E and prefix-G with interface to next hop E. Node D builds its SAV table by adding a row into its SAV table for each prefix in its RIB/FIB. Node D adds six rows into its SAV table. The first row contains prefix-A and the interface to next hop C in the source prefix and incoming interface columns respectively. The second row contains prefix-B and the interface to next hop C in the source prefix and incoming interface columns respectively. The third row contains prefix-C and the interface to next hop C in the source prefix and incoming interface columns respectively. The fourth row contains prefix-E and the interface to next hop E in the source prefix and incoming interface columns respectively. The fifth row contains prefix-F and the interface to next hop E in the source prefix and incoming interface columns respectively. The sixth row contains prefix-G and the interface to next hop E in the source prefix and incoming interface columns respectively.

[0065] In a second case, when the distributing forwarding paths are needed (i.e., there are some paths that are asymmetric), the OSPF control plane 308 accesses the forwarding paths in the RIB/FIB 318 and distributes the paths through LSAs of link-local scope. The OSPF control plane 308 then builds the SAV table using LSAs, generates new LSAs of link local scope from the LSA received, and sends the new LSAs to their corresponding next hop nodes.

[0066] As discussed above, the upstream network node 302 sends the first LSA through the interface la to the transit node 304, which is a next hop node. In one embodiment, when the next hop node 304 receives the LSA from the interface la, node 304 builds its SAV table. In one embodiment, node 304 includes or creates a row in the SAV table for each prefix attached to the source network node in the LSA. The row contains the prefix and the interface la in the Source Prefix and Incoming Interface columns, respectively. The next hop node 304 generates new LSAs of link local scope from the first LSA received and sends the new LSAs to their corresponding next hop nodes. Each of the new LSAs comprises the same source network node as the first LSA received. In an embodiment, the node 304 generates a second LSA for a plurality of destinations prefixes in the first LSA received. These pluralities of destinations prefixes have a same first next hop interface to a same first next hop node in the RIB/FIB of node 304. The next hop node 304 sends, through the same first next hop interface, the second LSA to the same first next hop node. In an embodiment, the node 304 generates a third LSA based on the FIB or the RIB, wherein the third LSA comprises a Paths TLV with the node 304 as a second source network node and a second plurality of destinations consisting of destination prefixes and prefix lengths from the FIB or the RIB of node 304, and wherein the destinations have a same second next hop interface to a same second next hop node in the RIB or the FIB; and then forwards, through the same second next hop interface, the third LSA to the same second next hop node.

[0067] In this way, after building the SAV table 316, the OSPF control plane 308 sends the S AV table 316 to the data plane 312 via interface lb ’ .

[0068] In an embodiment, a number of protocol extensions are discussed. The protocol extensions are implemented using type length values (TLVs).

[0069] FIG. 4 is a schematic diagram illustrating a format of paths type length value (TLV) 400 for an Internet Protocol version 4 (IPv4) according to an embodiment of the disclosure. A node (e.g., upstream node 302) originates an LSA comprising a paths TLV for a number of paths from the node. The format of paths TLV 400 comprises a type field 402, a length field 404, a source node identifier field 406, a destination prefix field 408, and a prefix-length field 410. The type field 402 including a value indicating the type of the TLV. The value is to be determined (TBD). The length field 404 defines the length of the value portion of the TLV in octets. The source node identifier field 406 (4 bytes) identifies a node of the source prefix and comprises a source node ID of the source network node. The destination prefix field 408 comprises a number of destination prefixes, and the prefix-length field 410 comprises a prefix length of each of the destination prefixes. For example, Destination-prefix- 1 indicates a first destination prefix and Prefix-len-1 indicates a length of the first destination prefix for a first IPv4 destination. Destination-prefix-n indicates a nth destination prefix and Prefix-len-n indicates a length of the nth destination prefix for a nth IPv4 destination.

[0070] FIG. 5 is a schematic diagram illustrating a format of an OSPF version 2 (OSPFv2) Extended Prefix Opaque LSA 500 with Paths TLV according to an embodiment of the disclosure. In an embodiment, for OSPF, when needed, a network node originates an OSPFv2 Extended Prefix Opaque LSA. OSPFv2 is a routing protocol that supports IPv4. The OSPFv2 Extended Prefix opaque LSA is of link state type 9 (i.e., link-local scope), including Paths TLV. [0071] The OSPFv2 Extended Prefix Opaque LSA includes a LS age field 502, an Options field 504, a LS Type field 506, an Opaque Type field 508, an Opaque ID field 510, an Advertising Router field 512, a LS sequence number field 514, a LS checksum field 516, a Length field 518, and a TLVs field 520.

[0072] The LS age field 502 contains the age of the OSPFv2 Extended Prefix Opaque LSA advertisement in seconds. The Options field 504 can be used to specify one or more OSPFv2 options. The Options field 504 enables OSPF routers to support (or not support) optional capabilities, and to communicate their capability level to other OSPF routers. In an embodiment, the LS Type field 506 is of type nine (9) (i.e., link-local scope). The Opaque Type field 508 is used to differentiate the various types of OSPFv2 Opaque LSAs. The Opaque Type field 508 may have Opaque Type of x (the exact type is to be assigned by IANA) for OSPFv2 Extended Prefix Opaque LSA. The Opaque ID field 510 can contain an arbitrary value that is used to maintain or differentiate between multiple OSPFv2 Extended Prefix Opaque LSAs. The Advertising Router field 512 contains the router ID of the router that originated the OSPFv2 Extended Prefix Opaque LSA. The LS sequence number field 514 contains successive sequence numbers that is used to detect old or duplicate LSAs. The LS checksum field 516 contains a checksum of the complete contents of the OSPFv2 Extended Prefix Opaque LSA including the LSA header, but excluding the LS age field 502. The Length field 518 represents the total length (in octets) of the OSPFv2 Extended Prefix Opaque LSA, including the LSA header and all TLVs (including paths TLV). The TLVs field 520 includes a paths TLV.

[0073] In an embodiment, when the distributing forwarding paths are needed (i.e., there is a path that is asymmetric), the OSPF control plane 308 in a network node accesses the forwarding paths in the RIB/FIB 314 of the network node and distributes the paths through LSAs of linklocal scope. For example, the network node originates and maintains an Extended Prefix Opaque LSA of LS type 9 (i.e., link-local scope), which includes a Paths TLV. The paths TLV comprises an identifier of the network node as a source node, a number of destination prefixes, and a prefix length of each of the destination prefixes. These destination prefixes have a first same next hop interface to a first same next hop node. The network node then sends the LSA through the first interface to the first next hop node.

[0074] In an embodiment, when the first next hop node receives the LSA with the Paths TLV from the first interface, the first next hop node builds its SAV table. In one embodiment, the first next hop node includes or creates a row in the SAV table for each prefix attached to the source node in the LSA. The row contains the prefix and the first interface in the Source Prefix and Incoming Interface columns respectively. The first next hop node generates new LSAs of link local scope with Paths TLVs from the LSA received and sends the new LSAs to their corresponding next hop nodes. In an embodiment, the first next hop node generates a new LSA of LS type 9 (i.e., link-local scope) comprising a Paths TLV with the same source node as the LSA received and a plurality of destinations prefixes in the LSA received. These pluralities of destinations prefixes have a second same next hop interface to a second same next hop node in the RIB/FIB of the first next hop node. That is, the paths to these destination prefixes use the second same next hop node. The paths TLV contains these destinations prefixes. For each destination, the TLV includes a prefix length of the destination prefix and the destination prefix. The first next hop node sends the new LSA to the second next hop.

[0075] FIG. 6 is a schematic format of paths type length value (TLV) 600 of an Internet Protocol version 6 (IPv6) according to an embodiment of the disclosure. The node originates an LSA of link-local scope comprising a paths TLV for a number of paths from the node. The format of paths TLV 600 comprises a type field 602, a length field 604, a source node identifier field 606, a destination prefix field 608, and a prefix-length field 610. The type field 602 includes a value indicating the type of the TLV. The value is to be determined (TBD). The length field 604 defines the length of the value portion of the TLV in octets. The source node identifier field 606 (4 bytes) identifies the node as a source node. The destination prefix field 608 comprises a number of destination prefixes, and the prefix-length field 610 comprises a prefix length of each of the destination prefixes. For example, Destination-prefix- 1 indicates a first destination prefix and Prefix -len-1 indicates a length of the first destination prefix for a first IPv6 destination. Destination-prefix-n indicates a nth destination prefix and Prefix -len-n indicates a length of the nth destination prefix for a nth IPv6 destination.

[0076] FIG. 7 is a schematic diagram of OSPF version 3 (OSPFv3) Extended Link LSA 700 with Paths TLV according to an embodiment of the disclosure. The OSPFv3 Extended Link LSA 700 has similar format as the OSPFv2 Extended Prefix Opaque LSA 500 in FIG. 5. The OSPFv3 Extended Link LSA 700 includes a LS age field 702, a LS Type field 704, a Link State ID field 706, an Advertising Router field 708, a LS sequence number field 710, a LS checksum field 712, a Length field 714, an Options field 716, and a TLVs field 718.

[0077] The LS age field 702 contains the age of the OSPFv3 Extended Link LSA advertisement in seconds. In an embodiment, the LS Type field 704 indicates the function performed by the LSA. The high-order three bits of LS type encode generic properties of the LSA, while the remaining bits (called LSA function code) indicate the LSA's specific functionality. The Extended Link LSA has a LS Type of 0x8028. The link state ID field 706 indicates router's identifier for the LSA. The Advertising Router field 708 contains the router ID of the router that originated the OSPFv3 Extended Link LSA. The LS sequence number field 710 contains successive sequence numbers that is used to detect old or duplicate LSAs. The LS checksum field 712 contains a checksum of the complete contents of the LSA including the LSA header, but excluding the LS age field 702. The Length field 714 represents the total length (in octets) of the OSPFv3 Extended Link LSA. The Options field 716 specifies the options bits that the originating router would like to set. The TLVs field 718 contains a paths TLV.

[0078] FIG. 8 is a schematic diagram of LS Type 800 of an LSA according to an embodiment of the disclosure. The LS type 800 includes a U-bit field 802, a S2-bit field 804, a Sl-bit field 806, and an LSA function code field 808. The U-bit field 802 indicates how the LSA should be handled by a router that does not recognize the LSA's function code. The S2-bit field 804 and Sl-bit field 806 indicate the flooding scope for the LSA. There are three flooding scopes for the LSA. For example, the S2-bit field 804 and Sl-bit field 806 are set to 0 to indicate linklocal flooding scope. The S2-bit field 804 is set to 0 and Sl-bit field 806 are set to 1 to indicate area flooding scope for the LSA. The S2-bit field 804 is set to 1 and Sl-bit field 806 are set to 0 to indicate autonomous system (AS) flooding scope for the LSA.

[0079] In an alternative embodiment, when there is a routing/forwarding path which is not symmetric, the SAV table is built using reverse paths. In a first implementation, every node (e.g., node G in FIG. 1) in OSPF domain builds its SAV table in two steps. In a first step, the node builds a reserve routing table (RRT). The RRT has the same format as a normal routing table or RIB. Node G computes a shortest path from node G to each of the other nodes using the link metric or cost of each link in the reverse direction. When node G finds a shortest path from node G to node E with a next hop interface, node G adds an entry for each prefix attached to E into its RRT. The entry comprises the prefix as the destination and the next hop interface as the next hop. In a second step, the node (e.g., node G in FIG. 1) includes a row in its SAV table for each prefix with a next hop interface in its RRT. The row contains the prefix and the interface in the Source Prefix and Incoming Interface columns respectively. In a second implementation, the first step and the second step are combined to build a SAV table. For example, node G computes a shortest path from node G to each of the other nodes using the link metric or cost of each link in the reverse direction. When node G finds a shortest path from node G to node E with a next hop interface, node G includes a row in its SAV table for each prefix attached to node E. The row contains the prefix and the interface in the Source Prefix and Incoming Interface columns respectively. [0080] In another alternative embodiment, when there is a routing/forwarding path which is not symmetric, the SAV table of the node G is built through multiple path computations. For example, node G computes a shortest path from each of the other nodes in the domain to every destination. For a computed shortest path from node E as a source to a destination, if the path goes through node G from an incoming interface le, then node G includes or creates a row in its SAV table for each prefix attached to node E. The row contains the prefix and the interface le in the Source Prefix and Incoming Interface columns respectively.

[0081] FIG. 9 is a method 900 implemented by a network node in the OSPF domain according to an embodiment of the disclosure. The network node may be any of the network nodes 104-116 and the OSPF domain may be the OSPF domain 102.

[0082] At block 902, the method 900 comprises accessing a network topology of the OSPF domain in a link state database (LSDB).

[0083] At block 904, the method 900 comprises determining whether every forwarding path in the OSPF domain is symmetric. In an embodiment, the forwarding path is determined to be symmetric when every link in the network topology in the LSDB has equal cost metric from a source to a destination and from the destination to the source.

[0084] At block 906, the method 900 comprises deciding whether or not the forwarding is symmetric.

[0085] At block 908, the method 900 comprises using a forwarding information base (FIB) or a routing information base (RIB) to build a source address validation (SAV) table when every forwarding path in the OSPF domain is symmetric. In an embodiment, using the FIB or the RIB to build the SAV table comprises updating the SAV table by creating a row in the SAV table for each prefix with a next hop interface in the FIB or the RIB, wherein the row comprises the prefix and the next hop interface.

[0086] At block 910, the method 900 comprises receiving a first link state advertisement (LSA) from a first source network node through a first interface when a forwarding path in the OSPF domain is asymmetric. In an embodiment, the first LSA comprises an identifier of the first source network node, a number of destination prefixes, and a prefix length of each of the destination prefixes.

[0087] At block 912, the method 900 comprises building the SAV table using the first LSA. In an embodiment, building the SAV table using the first LSA comprises creating a row in the SAV table for each prefix attached to the first source network node in the first LSA, wherein the row comprises the prefix and the first interface.

[0088] At block 914, the method 900 comprises generating a second LSA and a third LSA. [0089] In an embodiment, the method 900 further comprises generating the second LSA based on the first LSA and the FIB or the RIB, wherein the second LSA comprises a Paths Type-Length-Value (TLV) with the first source network node and a plurality of destinations consisting of destination prefixes and prefix lengths in the first LSA, and wherein the destinations have a first same next hop interface to a first same next hop node in the RIB or the FIB; and forwarding, through the first same next hop interface, the second LSA to the first same next hop node.

[0090] In an embodiment, the method 900 further comprises generating the third LSA based on the FIB or the RIB, wherein the third LSA comprises a Paths TLV with the network node as a second source network node and a second plurality of destinations consisting of destination prefixes and prefix lengths from the FIB or the RIB, and wherein the destinations have a second same next hop interface to a second same next hop node in the RIB or the FIB; and forwarding, through the second same next hop interface, the third LSA to the second same next hop node. In an embodiment, each of the first LSA, the second LSA, and the third LSA comprises a Paths Type-Length-Value (TLV) and is an OSPFv2 Extended Prefix Opaque LSA of type 9 or an OSPFv3 Extended Link LSA.

[0091] FIG. 10 is a method 1000 implemented by a network node in the OSPF domain according to an embodiment of the disclosure. The network node may be any of the network nodes 104-116 and the OSPF domain may be the OSPF domain 102.

[0092] At block 1002, the method 1000 comprises computing a shortest path in the OSPF domain from the network node to each of other nodes in a reverse direction. In an embodiment, the shortest path from the network node to a destination is computed based on a link metric or cost of each link along a path from the destination to the network node.

[0093] In block 1004, the method 1000 comprises constructing a source address validation (SAV) table by adding an entry for each prefix attached to a first node when the shortest path is computed from the network node to the first node in the reverse direction. In an embodiment, the entry comprises the prefix and an interface in a source prefix column and incoming interface columns, respectively of the SAV table, and wherein the interface is of the network node on the shortest path.

[0094] FIG. 11 is a schematic diagram of a network apparatus 1100 (e.g., a network node, a neighbor node, etc.). The network apparatus 1100 is suitable for implementing the disclosed embodiments as described herein. The network apparatus 1100 comprises ingress ports/ingress means 1110 and receiver units (Rx)/receiving means 1120 for receiving data; a processor, logic unit, or central processing unit (CPU)/processing means 1130 to process the data; transmitter units (Tx)/transmitting means 1140 and egress ports/egress means 1150 for transmitting the data; and a memory/memory means 1160 for storing the data. The network apparatus 1100 may also comprise optical-to-electrical (OE) components and electrical-to-optical (EO) components coupled to the ingress ports/ingress means 1110, the receiver units/receiving means 1120, the transmitter units/transmitting means 1140, and the egress ports/egress means 1150 for egress or ingress of optical or electrical signals.

[0095] The processor/processing means 1130 is implemented by hardware and software. The processor/processing means 1130 may be implemented as one or more CPU chips, cores (e.g., as a multi-core processor), field-programmable gate arrays (FPGAs), application specific integrated circuits (ASICs), and digital signal processors (DSPs). The processor/processing means 1130 is in communication with the ingress ports/ingress means 1110, receiver units/receiving means 1120, transmitter units/transmitting means 1140, egress ports/egress means 1150, and memory/memory means 1160. The processor/processing means 1130 comprises an OSPF module 1170. The OSPF module 1170 is able to implement the methods disclosed herein. The inclusion of the OSPF module 1170 therefore provides a substantial improvement to the functionality of the network apparatus 1100 and effects a transformation of the network apparatus 1100 to a different state. Alternatively, the OSPF module 1170 is implemented as instructions stored in the memory/memory means 1160 and executed by the processor/processing means 1130.

[0096] The network apparatus 1100 may also include input and/or output (VO) or devices/I/O means 1180 for communicating data to and from a user. The VO devices or VO means 1180 may include output devices such as a display for displaying video data, speakers for outputting audio data, etc. The VO devices or VO means 1180 may also include input devices, such as a keyboard, mouse, trackball, etc., and/or corresponding interfaces for interacting with such output devices.

[0097] The memory/memory means 1160 comprises one or more disks, tape drives, and solid-state drives and may be used as an over-flow data storage device, to store programs when such programs are selected for execution, and to store instructions and data that are read during program execution. The memory/memory means 1160 may be volatile and/or non-volatile and may be read-only memory (ROM), random access memory (RAM), ternary content-addressable memory (TCAM), and/or static random-access memory (SRAM).

[0098] While several embodiments have been provided in the present disclosure, it may be understood that the disclosed systems and methods might be embodied in many other specific forms without departing from the spirit or scope of the present disclosure. The present examples are to be considered as illustrative and not restrictive, and the intention is not to be limited to the details given herein. For example, the various elements or components may be combined or integrated in another system or certain features may be omitted, or not implemented.

[0099] In addition, techniques, systems, subsystems, and methods described and illustrated in the various embodiments as discrete or separate may be combined or integrated with other systems, components, techniques, or methods without departing from the scope of the present disclosure. Other examples of changes, substitutions, and alterations are ascertainable by one skilled in the art and may be made without departing from the spirit and scope disclosed herein.