CN119384820A - Intermediate system to intermediate system for source address verification - Google Patents

Abstract

A method implemented by a network node for providing source address verification (Source Address Validation, SAV) information for intermediate system-to-intermediate system (IS-IS) routing to a destination in an asymmetric network includes generating a first link state protocol data unit (LINK STATE Protocol Data Unit, LSP), wherein the first LSP includes a first destination prefix that identifies a first destination of a first path to a first next-hop node, a destination prefix length that indicates a length of the first destination prefix, and a source node Identifier (ID) that identifies the first node as a source node, and transmitting the first LSP to the next-hop node. Upon receiving the first LSP, the receiving node generates an SAV entry from the first LSP and then generates a second LSP to send to other nodes in the network.

Description

Intermediate system to intermediate system for source address verification

The present patent application claims the benefit of U.S. provisional patent application No. 63/347,292 entitled "IS-IS for source address verification (IS-IS for Source Address Validation)" filed on month 31 of 2022, the contents of which are incorporated by reference.

Technical Field

The intermediate system-to-intermediate system (INTERMEDIATE SYSTEM to INTERMEDIATE SYSTEM, IS-IS) routing protocol IS an interior gateway protocol (Interior Gateway Protocol, IGP). The disclosed embodiments relate generally to IS-IS routing, and more particularly to source address verification (Source Address Validation, SAV) for internet protocol (Internet Protocol, IP) networks.

Background

IS-IS routing protocol IS commonly used for large service provider networks. IS-IS may also be deployed in very large enterprise networks. IS-IS a link state routing protocol that uses the open systems interconnection (Open System Interconnection, OSI) protocol to transmit messages and establish adjacencies. The IS-IS router IS assigned OSI addresses, which are then used as router Identifiers (IDs) in the network structure.

The internet relies on IP messages to enable communication between hosts whose destination and source addresses are specified in a header. However, there is no message-level authentication mechanism to ensure that the source address is not altered. The source IP address may be scrambled during transmission or may be modified deliberately. The act of modifying the source IP address is referred to as "IP spoofing (IP spoofing)". IP spoofing can result in anonymity of the sender and the inability of the message to be tracked to its source. Source address authentication is an architecture or framework for authenticating a source address and discarding messages whose source IP address is not authenticated.

Disclosure of Invention

The invention provides an architecture and a technical scheme for source address verification, which can operate in an IS-IS domain.

A first aspect of the invention provides a source address verification (Source Address Validation, SAV) method implemented by a network node for intermediate system-to-intermediate system (INTERMEDIATE SYSTEM to INTERMEDIATE SYSTEM, IS-IS) routing to a destination in an asymmetric network. The method includes receiving a first link state protocol data unit (Protocol Data Unit, PDU) (LINK STATE PDU, LSP) from a first interface, wherein the first LSP includes a first destination prefix identifying a first destination of a first path, a first destination prefix length indicating a length of the first destination prefix, and a first source node Identifier (ID) identifying a source node, generating an SAV entry from the first LSP, wherein the SAV entry includes a source node prefix as an address of the source node and the first interface as an ingress interface for the source node prefix, generating a second LSP from the first LSP and the destination, and transmitting the second LSP to a next hop node in a path to the destination.

Optionally, in the above aspect, the method includes an implementation in which the first LSP and the second LSP are both circuit-wide LSPs (Circuit Scoped LSPs, CS-LSPs) and include path type length values (TYPE LENGTH Value, TLV) of a fourth-release internet protocol (Internet Protocol version, IPv 4), the path TLV including a source node ID and a plurality of IPv4 destinations, each IPv4 destination including an IPv4 destination prefix and a destination prefix length.

Optionally, in the above aspect, the method includes an implementation in which the first LSP and the second LSP are both CS-LSPs and include a path TLV of internet protocol version six (Internet Protocol version, IPv 6) that includes a source node ID and a plurality of IPv6 destinations, each IPv6 destination including an IPv6 destination prefix and a destination prefix length.

Optionally, in any of the above aspects, in other implementations, the second LSP includes a second destination prefix and a second destination prefix length in the first LSP and the first source node ID.

Optionally, in any of the above aspects, in other implementations, the method includes generating a third LSP when the network node is an ingress node, wherein the third LSP is a CS-LSP and includes a third destination prefix and a third destination prefix length of a third destination and a node ID of the network node as a source node ID, wherein the third destination has a third next hop in a routing information base (Routing Information Base, RIB) or forwarding information base (Forwarding Information Base, FIB) of the network node.

Optionally, in any preceding aspect, the method includes an implementation, wherein the third next hop is a next hop node in the RIB or FIB of the network node towards the third destination, the network node sending the third LSP to the third next hop.

Optionally, in any above aspect, the method includes an implementation wherein the generating the SAV table entry includes generating or updating a SAV table entry in a first SAV table in an IS-IS control plane of the network node, and transmitting the first SAV table to update a second SAV table in a data plane of the network node.

Optionally, in any of the above aspects, the method includes an implementation in which the first SAV table or the second SAV table entry is used to validate a source of an incoming message received from an interface, discard the message if the source and the interface are not in any row of the SAV table, and otherwise forward the message according to the FIB.

A second aspect of the present invention provides a source address verification (Source Address Validation, SAV) method implemented by a first node for intermediate system-to-intermediate system (INTERMEDIATE SYSTEM to INTERMEDIATE SYSTEM, IS-IS) routing in an asymmetric network. The method comprises the steps that a first node calculates the shortest path from the first node to the destination node in the asymmetric network by using reverse overhead of a link in the network, the first node generates a reverse routing table (Reverse Routing Table, RRT), wherein the RRT comprises a source prefix serving as an address of the destination node and a next hop interface corresponding to the destination node, and the first node generates an SAV table item according to the RRT, wherein the SAV table item comprises the source prefix and the next hop interface serving as an entrance interface.

Optionally, in the above aspect, in another implementation, when there is a link between a source node and a destination node in the network in a link state Database (LINK STATE Database, LSDB), the link from the source node to the destination node has a first overhead, the link from the destination node to the source node has a second overhead, and the first overhead is different from the second overhead, the network is determined to be asymmetric.

Optionally, in another implementation of the above aspect, the reverse overhead of a link from a source node to a destination node is the overhead of the link from the destination node to the source node.

Optionally, in any above aspect, the method includes an implementation wherein the generating the SAV table entry includes generating or updating a SAV table entry in a first SAV table in an IS-IS control plane of the first node, and transmitting the first SAV table to update a second SAV table in a data plane of the first node.

Optionally, in any of the above aspects, the method includes an implementation, wherein the SAV table entry is used to verify a source of an incoming message received from an interface, discard the message if the source and the interface are not in any row of the SAV table, and otherwise forward the message according to FIB.

A third aspect of the present invention provides a source address verification (Source Address Validation, SAV) method implemented by a first node for intermediate system-to-intermediate system (INTERMEDIATE SYSTEM to INTERMEDIATE SYSTEM, IS-IS) routing in an asymmetric network. The method comprises the steps of calculating shortest paths between each node in the asymmetric network, and generating an SAV table for each shortest path from a second node and through a first interface by the first node, wherein the SAV table comprises a source node prefix as an address of the second node and the first interface as ingress interface information of the source node prefix.

Optionally, in the above aspect, in another implementation, when there is a link between a source node and a destination node in the network in a link state Database (LINK STATE Database, LSDB), the link from the source node to the destination node has a first overhead, the link from the destination node to the source node has a second overhead, and the first overhead is different from the second overhead, the network is determined to be asymmetric.

Optionally, in any above aspect, the method includes an implementation wherein generating the SAV table entry includes generating or updating the SAV table entry in a first SAV table in an IS-IS control plane of the first node, and transmitting the first SAV table to update a second SAV table in a data plane of the first node.

Optionally, in any of the above aspects, the method includes an implementation, wherein the SAV table entry is used to verify a source of an incoming message received from an interface, discard the message if the source and the interface are not in any row of the SAV table, and otherwise forward the message according to FIB.

Optionally, in another implementation, a network node in a communication network includes a memory to store instructions and one or more processors coupled to the memory and to execute the instructions to cause the network node to perform the method of any of the above aspects.

Optionally, in another implementation, a computer program product comprises computer executable instructions stored in a non-transitory medium, wherein the instructions, when executed by one or more processors, cause a network node in a communication network to perform the method of any of the above aspects.

Optionally, in another implementation, a computer program product comprises computer-executable instructions stored in a non-transitory medium, wherein the instructions, when executed by one or more processors, cause a network node in an IS-IS communication network to perform the method of any of the above aspects.

Any of the above embodiments may be combined with any one or more of the other embodiments described above for clarity to create new embodiments within the scope of the present invention.

These and other features will be more clearly understood from the following detailed description taken in conjunction with the accompanying drawings and claims.

Drawings

For a more complete understanding of the present invention, 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.

Fig. 1 IS a schematic diagram of a network architecture of an SAV in an IS-IS domain implementing the system and method of the present invention.

Fig. 2 IS a schematic diagram of an IS-IS domain.

FIG. 3 is a flow chart of one example of an implementation of an embodiment of the present invention.

Fig. 4 is a flow chart of one example of an implementation of other embodiments of the invention.

Fig. 5 is a flow chart of one example of an implementation of an additional embodiment of the invention.

Fig. 6 is a schematic diagram of a type length Value (TYPE LENGTH Value, TLV) format in a message provided by an embodiment of the present invention.

Fig. 7 is a schematic diagram of TLV format in a message provided by an embodiment of the present invention.

Fig. 8 IS a source address verification (Source Address Validation, SAV) method implemented by a network node for intermediate system-to-intermediate system (INTERMEDIATE SYSTEM to INTERMEDIATE SYSTEM, IS-IS) routing to a destination in an asymmetric network, according to an embodiment of the present invention.

Fig. 9 IS a source address verification (Source Address Validation, SAV) method implemented by a first node for intermediate system-to-intermediate system (INTERMEDIATE SYSTEM to INTERMEDIATE SYSTEM, IS-IS) routing in an asymmetric network.

Fig. 10 IS a source address verification (Source Address Validation, SAV) method implemented by a network node for intermediate system-to-intermediate system (INTERMEDIATE SYSTEM to INTERMEDIATE SYSTEM, IS-IS) routing to a destination in an asymmetric network.

Fig. 11 is a schematic diagram of an example of an apparatus of an embodiment of the present invention.

Detailed Description

It should be understood at the outset that although examples of illustrative implementations of one or more embodiments are provided below, the disclosed systems and methods may be implemented using any number of techniques, whether currently known or in existence. The invention is in no way 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.

Techniques to prevent IP spoofing are disclosed herein. By applying the disclosed techniques, the source of the incoming message can be verified. Thus, network scalability and integrity are enhanced.

The link state protocol uses characteristics of the link (e.g., speed and cost in terms of network resources and current congestion conditions) to determine the best path for any given message. The link state protocol is executed by each switching node (e.g., router) in the network. In link state routing, each node in the network maintains a network connection graph in the form of a link state database indicating which nodes are connected to which other nodes. Each node can then independently calculate the best logical path to each possible destination in the network. Each set of best paths is used to provide an updated routing table for each node. The link state routers in the network exchange messages so that each router can learn the entire network topology. Each router can then maintain its own routing table, depending on the topology that is known. Each IS-IS router constructs an LSP that includes the following information:

LSP router identification (address) of sender of LSP

LSP age or residual Life of LSP

LSP. Seq: sequence number of LSP

Link-links advertised in LSP. Each directional link includes the following information:

LSP. Links [ i ]. Id: identification of neighbors

LSP. Links [ i ]. Cost: cost of link.

LSPs are distributed throughout the network by network nodes. Each router maintains a link state Database (LINK STATE Database, LSDB) that includes the latest LSPs sent by each router in the network. When a router receives an LSP, the router first verifies whether the LSP is already stored in its own LSDB. If so, the router determines that the LSP has been distributed and therefore does not forward the LSP. Otherwise, the router forwards the LSP on all links except the link that received the LSP.

To validate the data messages received by each node in an IS-IS domain or region, each node builds and maintains its own SAV table from the LSDB for that node. For the purposes of the present invention, it should be understood that the SAV table includes at least a source prefix identifying the source of the received message and ingress interface information. An example of the format of the SAV table is shown in table 1.

TABLE 1

Source prefix	Inlet interface (or port)
		Prefix-1	Interface-a
Prefix-2	Interface-b
		......	......
Prefix-n	Interface-x

The SAV table is sent to the data plane and used to verify the source address of the received message. When a message is received from the interface, the receiving node will check or validate the message using the receiving node's SAV table. When the source address and the receive/ingress interface of a message are not in the SAV table (that is, there are no rows in the SAV table that include the source address and the receive/ingress interface), the message is intercepted or discarded. Otherwise (that is, there is a row in the SAV table that includes the source address and the receive interface/ingress interface), the message is forwarded according to a routing information base (Routing Information Base, RIB) or forwarding information base (Forwarding Information Base, FIB), examples of which are shown in table 2.

TABLE 2

Destination prefix	Outlet interface (or port)
		Dest-Prefix-1	Out-Interface-a
Dest-Prefix-2	Out-Interface-b
		......	......
Dest-Prefix-n	Out-Interface-x

In a distributed network architecture, each node in the domain builds and maintains its own SAV table, e.g., the SAV table shown in table 1.

FIG. 1 shows a conceptual overview of an architecture for implementing IS-IS for SAV using interfaces Ia through Ib and Ia 'through Ib'. The architecture includes a node 102 that is an upstream node, a node 100 that is a transit node, and a node 110 that is a downstream node. The nodes 100 in the network using IS-IS routing include an IS-IS control plane 106 with LSDB and a first SAV, a routing table manager (routing table manager, RTM) 104 with RIB/FIB, and a data plane 108 with a second SAV. The second SAV table is a copy of the first SAV table. The IS-IS control plane 106 in node 100 receives a first LSP comprising a first source node ID and a first plurality of destinations from upstream node 102 via ingress interface Ia, updates the LSDB based on the received first LSP, and then accesses and updates the forwarding path in the RIB/FIB via interface Ia'. IS-IS control plane 106 constructs and/or updates a first SAV table from the received first LSP and/or RIB/FIB, provides first SAV table information to data plane 108 over interface Ib' to update the second SAV, then generates a second LSP and a third LSP and sends both to downstream node 110 (the next hop) along the forwarding path indicated by the RIB/FIB. The second LSP includes a first source node ID and a second plurality of destinations in the first LSP. The second plurality of destinations have the same next hop node 110 in the first LSP and in the RIB/FIB of node 100. The third LSP includes a node ID of node 100 that is a third source node ID and a third plurality of destinations. The third plurality of destinations have the same next hop node 110 in the RIB/FIB of node 100. When the network node is on a forwarding path to a destination in a third LSP, the prefix of node 100 is added to the third SAV table of the network node.

In one embodiment, whether each forwarding path in an IS-IS domain or region IS symmetrical depends on whether each link of the network topology in the LSDB has the same overhead or cost in both directions. For a link between a and B, when the overhead or cost of the link from a to B is the same as the overhead or cost of the link from B to a, the link has the same overhead or cost in both directions. If each link of the network topology in the LSDB has the same overhead in both directions, each forwarding path in the IS-IS domain or area IS symmetrical, and the network IS also symmetrical, otherwise the network IS asymmetrical, that IS, if there IS a link between a source node and a destination node in the network in the LSDB, the network IS asymmetrical, wherein the link from the source node to the destination node has a first overhead and the link from the destination node to the source node has a second overhead, the first overhead being different from the second overhead. In one embodiment, when constructing the SAV table using the RIB/FIB, if each forwarding path in the IS-IS domain or region IS symmetrical, the IS-IS control plane includes a row in the SAV table for each prefix and next-hop interface in the RIB/FIB. The SAV table row includes prefixes in the source prefix column and interfaces in the ingress interface column.

Fig. 2 shows one example of an overview of an IS-IS network domain 200. IS-IS domain 200 includes a plurality of network nodes A, B, C, D, E, F and G. Network nodes a through G are coupled to and communicate with each other via links 110. The link 110 may be a wired link, a wireless link, or some combination thereof. Each link 110 has a cost or overhead (not shown in fig. 2). Each of the network nodes a to G may be a destination network node and have a plurality of neighbor nodes. The neighbor node of the first network node is referred to as a second network node directly connected to the first network node. For example, network node a has three neighbor nodes, namely neighbor node C, neighbor node B, and neighbor node F. Network nodes disposed at the edge of IS-IS domain 200 are referred to as edge network nodes or edge nodes. For example, network nodes A, C, D, G and F are edge network nodes. Edge network nodes that receive messages from outside IS-IS domain 200 may be referred to as ingress nodes. Edge network nodes that send messages out of IS-IS domain 200 may be referred to as egress nodes. Each of the edge network nodes A, C, D, G and F may act as an ingress node or an egress node depending on the direction of the message traffic.

As described above, the IS-IS control plane in a network node can access the network topology stored in the LSDB of that node and update the RIB/FIB of that node by calculating the shortest path to the destination using that node's LSDB. Each of nodes a through G builds and maintains its own separate SAV table. For example, when each forwarding path is symmetrical (that is, the network is symmetrical), node D builds the node's SAV table using the node's RIB/FIB. For node A as the source node, when the entry in the RIB/FIB of node D (referred to as node 100 in FIG. 1) includes node A as the destination and an egress Interface-D-C to the next hop C (referred to as node 102 in FIG. 1), node D includes each prefix of node A and an ingress Interface-D-C (referred to as Ia in FIG. 1) in the SAV table of node D. For a message from a source to a node D through a node A, the message passes through an Interface-D-C.

When an asymmetric forwarding path exists (i.e., the network is asymmetric), in one embodiment, each node in the network may construct and maintain an SAV table for that node from the first LSP including the first source node ID and the received first set of destinations and the RIB/FIB for that node. The node generates a second LSP based on the first LSP and the RIB/FIB of the node. The second LSP includes a first source node ID and a second set of destinations that have the same second next hop in the first LSP and in the RIB/FIB of the node. The node sends a second LSP to the second next hop. When the node is an ingress node, the node generates a third LSP based on the RIB/FIB of the node. The third LSP includes a node ID of the node as a source node ID and a third set of destinations in the RIB/FIB of the node and having a same third next hop. The node sends a third LSP to a third next-hop. Each LSP is a circuit-wide LSP (Circuit Scoped LSP, CS-LSP).

With further reference to the network domain architecture shown in fig. 1 and 2, it should be appreciated that each node in an IS-IS domain/region may construct and maintain its own SAV table in a symmetric or asymmetric communication network, as described in more detail below.

Figure 3 illustrates one embodiment of a method of constructing an SAV table in the presence of asymmetric forwarding paths. The first node shown in flowchart 300 has multiple destination prefixes (also referred to as destinations) and the same next hops to those destinations in the RIB/FIB of the first node 300. The first node 300 initiates and maintains a first CS-LSP that includes the destination as an Identifier (ID) of the first node 300 of the source node. The first CS-LSP also includes, for each destination, the prefix length of each destination prefix and the destination prefix itself. The first node 300 then sends the CS-LSP over interface Ib to the next-hop node 302 in the path to the destination.

In an IS-IS protocol data unit (Protocol Data Unit, PDU), a type length Value (TYPE LENGTH Value, TLV) IS used. In the disclosed embodiment, a TLV called a path or route TLV is defined. When a node issues a CS-LSP that includes a path TLV for multiple paths from the node, the path TLV includes the destination prefixes for the paths.

After the next-hop node 302 receives the first CS-LSP including the first path TLV from the first node 300 over interface Ib, the next-hop node 302 builds the SAV table for that node. In one embodiment, the next hop node 302 includes or creates a row in the SAV table for each source prefix connected to the first node 300. The row includes a source prefix and an interface Ib in a source prefix column and an ingress interface column, respectively.

Next-hop nodes 302 then generate CS-LSPs including path TLVs from the received first CS-LSPs and send these CS-LSPs to their corresponding next-hop nodes. In one embodiment, next-hop node 302 generates a second CS-LSP that includes a second path TLV for multiple destinations in the received first CS-LSP (but not including the destination (i.e., prefix) of node 302). The second path TLV includes an Identifier (ID) of the first node 300 as the source node. Multiple destinations have the same second next hop in the RIB/FIB of next hop node 302. That is, the paths to these destinations use the same second next hop. The second path TLV includes, for each destination, a prefix length of the destination prefix and the destination prefix. The next-hop node 302 sends the second CS-LSP to the second next-hop node.

When the next-hop node 302 is an ingress node, the next-hop node 302 generates a CS-LSP that includes a path TLV from the RIB/FIB of the next-hop node 302. In one embodiment, next-hop node 302 generates a third CS-LSP that includes a third path TLV for multiple destinations in the RIB/FIB of next-hop node 302. The third path TLV includes an Identifier (ID) of the next-hop node 302 as the source node. Multiple destinations have the same third next hop in the RIB/FIB of next hop node 302. The third path TLV includes, for each destination, a prefix length of the destination prefix and the destination prefix. The next-hop node 302 sends the third CS-LSP to the third next-hop node.

As shown in fig. 4, in one embodiment, the first node shown in flowchart 400 may construct an SAV table when an asymmetric forwarding path exists. The node 400 in this example builds a reverse routing table (reserve routing table, RRT). RRT has the same format as a normal routing table or RIB. In step 402, node 400 calculates a shortest path from itself (i.e., node 400) to each other node in the domain using the link cost or cost of each link in the reverse direction. In step 404, when the node 400 finds the shortest path from the node 400 to the second node having the next hop interface, the node 400 adds an entry for each prefix connected to the second node to the RRT of the node 400. The entry includes a prefix and a next hop interface as a destination. In step 406, the node 400 then uses the RRT to build or update the SAV table of the node 400. Node 400 includes a row in the SAV table for each prefix and next hop interface in RRT. The row includes a prefix and a next hop interface in a source prefix column and an ingress interface column, respectively. In step 408, the node 400 sends the updated SAV to the data plane of the node 400.

In this example, referring to fig. 4, in the context of fig. 2, node a calculates a shortest path from node a to each of network nodes B through G using the link overhead or cost of each link in the reverse direction in step 402. The link overhead or cost of a link in the reverse direction is referred to as the reverse overhead or cost of the link. For example, for a link from node a to node C, node a uses the link cost or cost of the link from node C to node a (i.e., the cost or cost of the link from node a to node C in the reverse direction) to calculate a shortest path to each of network nodes B to G. For the link from node C to node D, node a uses the link cost or cost of the link from node D to node C to calculate a shortest path to each of network nodes B to G. In step 404, when node A finds the shortest path from node A to node D with the next hop Interface-A-C, node A adds an entry for each prefix connected to node D to node A's RRT. The entry includes a prefix as the destination and a next hop Interface-a-C as the next hop. In step 406, node A generates an SAV table that includes a row for the prefix and the next hop Interface-A-C in the RRT added to node A. The row includes a prefix and an Interface-A-C in a source prefix column and an ingress Interface column, respectively. In step 408, node A sends the updated SAV to node A's data plane.

In another embodiment, when the path is asymmetric, each node may construct its SAV table by calculating a path from each node in the domain to each destination in the domain. The first node calculates a shortest path from each of the other nodes in the domain to each destination. For a calculated shortest path from a second node as a source to a destination, if the path passes through the first node from the ingress Interface-p, the first node includes or creates a row in the SAV table of the first node for each prefix connected to the second node. The row includes a prefix and an Interface-p in a source prefix column and an ingress Interface column, respectively. After the SAV table IS built, the IS-IS control plane in each node sends the SAV table to the data plane through interface Ib'. Referring to fig. 5, in one embodiment, a node 500 may build an SAV table when asymmetric forwarding paths exist. In this example, each node in the network computes a shortest path from each other node in the domain to each destination.

For example, referring to fig. 5, in the context of fig. 2, from the perspective of node B, node B calculates all shortest paths between all nodes a through G in step 502. In step 504, the shortest path from node A to node E in this example is determined to pass through node B by interface-A-B. Then, in step 506, the node B includes or creates a row in the SAV table of the node B for each prefix connected to the node a. The row includes a prefix and an Interface-A-B in a source prefix column and an ingress Interface column, respectively. The same or similar SAV entries are created for all shortest paths through the node B. Paths that do not pass through the node B are ignored in step 508 and omitted from the SAV table of the node B.

In the disclosed embodiment, extension of the TLV (denoted as path TLV) may be used in implementations applicable to version four internet protocol (Internet Protocol Version, ipv 4) and version six internet protocol (Internet Protocol Version, ipv 6).

The format of the path TLV for IPv4 is shown in fig. 6. When a node issues a CS-LSP that includes a path TLV for multiple paths from the node, the path TLV includes the destination prefixes for the paths. The path TLV of IPv4 includes:

A source node Identifier (ID) (6 bytes) identifies the node of the source prefix.

Prefix-len-1 and Destination-Prefix-1 indicate the first IPv4 Destination, including the length of the first Destination Prefix and the first Destination Prefix itself.

The Prefix-len-n and the Destination-Prefix-n indicate the nth IPv4 Destination, i.e., the length of the nth Destination Prefix and the nth Destination Prefix.

The path TLV for IPv6 is shown in fig. 7. When a node issues a CS-LSP that includes a path TLV for multiple paths from the node, the TLV includes the destination prefixes for the paths. The path TLV of IPv6 includes:

The source node ID (6 bytes) identifies the node of the source prefix.

Prefix-len-1 and Destination-Prefix-1 indicate the first IPv6 Destination, i.e. the length of the first Destination Prefix and the first Destination Prefix.

The Prefix-len-n and Destination-Prefix-n indicate the nth IPv6 Destination, i.e., the length of the nth Destination Prefix and the nth Destination Prefix.

Fig. 8 IS a source address verification (Source Address Validation, SAV) method 800 implemented by a network node for intermediate system-to-intermediate system (INTERMEDIATE SYSTEM to INTERMEDIATE SYSTEM, IS-IS) routing to a destination in an asymmetric network, according to an embodiment of the present invention. In one embodiment, the network node comprises node 100 in fig. 1 or one of network nodes A, B, C, D, E, F and G in fig. 2.

In block 802, the network node receives a first link state protocol data unit (Protocol Data Unit, PDU) (LINK STATE PDU, LSP) from a first interface. In one embodiment, the first LSP includes a first destination prefix that identifies a first destination of the first path, a first destination prefix length that indicates a length of the first destination prefix, and a first source node Identifier (ID) that identifies the source node.

In block 804, the network node generates an SAV table entry according to the first LSP. In one embodiment, the SAV entry includes a source node prefix that is an address of the source node and a first interface that is an ingress interface of the source node prefix.

In block 806, the network node generates a second LSP from the first LSP and the destination. In block 808, the network node sends the second LSP to a next hop node in the path to the destination.

In one embodiment, the first LSP and the second LSP are both circuit-wide LSPs (Circuit Scoped LSPs, CS-LSPs) and include a path TLV of a fourth-edition Internet protocol (Internet Protocol version, IPv 4). In one embodiment, the path TLV includes a source node ID and a plurality of IPv4 destinations, each IPv4 destination including an IPv4 destination prefix and a destination prefix length. In one embodiment, the second LSP includes a second destination prefix and a second destination prefix length in the first LSP and the first source node ID.

In one embodiment, the first LSP and the second LSP are both circuit-wide LSPs (Circuit Scoped LSPs, CS-LSPs) and include a path TLV of Internet protocol version six (Internet Protocol version, IPv 6). In one embodiment, the path TLV includes a source node ID and a plurality of IPv6 destinations, each IPv6 destination including an IPv6 destination prefix and a destination prefix length. In one embodiment, the second LSP includes a second destination prefix and a second destination prefix length in the first LSP and the first source node ID.

In one embodiment, method 800 further comprises generating a third LSP when the network node is an ingress node. In one embodiment, the third LSP is a circuit-wide LSP (Circuit Scoped LSP, CS-LSP) and includes a third destination prefix and a third destination prefix length of a third destination and a node ID of the network node as a source node ID, wherein the third destination has a third next hop in a routing information base (Routing Information Base, RIB) or forwarding information base (Forwarding Information Base, FIB) of the network node. In one embodiment, the third next hop is the next hop node in the RIB or FIB of the network node towards the third destination, to which the network node sends the third LSP.

Fig. 9 IS a source address verification (Source Address Validation, SAV) method 900 implemented by a first node for intermediate system-to-intermediate system (INTERMEDIATE SYSTEM to INTERMEDIATE SYSTEM, IS-IS) routing in an asymmetric network. In one embodiment, the first node comprises node 100 in fig. 1 or one of network nodes A, B, C, D, E, F and G in fig. 2.

In block 902, a first node calculates a shortest path from the first node to a destination node in an asymmetric network by using reverse overheads of links in the asymmetric network. In block 904, the first node generates a reverse routing table (Reverse Routing Table, RRT). In one embodiment, the RRT includes a source prefix as an address of the destination node and a next hop interface corresponding to the destination node.

In block 906, the first node generates an SAV entry from the RRT. In one embodiment, the SAV table entry includes a source prefix and a next hop interface as an ingress interface.

In one embodiment, when there is a link between a source node and a destination node in a network in a link state Database (LINK STATE Database, LSDB), the link from the source node to the destination node has a first cost, the link from the destination node to the source node has a second cost, and the first cost is different from the second cost, it is determined that the network is asymmetric. In one embodiment, the reverse overhead of the link from the source node to the destination node is the overhead of the link from the destination node to the source node.

Fig. 10 IS a source address verification (Source Address Validation, SAV) method 1000 implemented by a network node for intermediate system-to-intermediate system (INTERMEDIATE SYSTEM to INTERMEDIATE SYSTEM, IS-IS) routing to a destination in an asymmetric network. In one embodiment, the first node comprises node 100 in fig. 1 or one of network nodes A, B, C, D, E, F and G in fig. 2.

In block 1002, a network node receives a first LSP from an upstream node over a first interface. In an embodiment, the first LSP includes a first node source Identifier (ID) and a first plurality of destinations. In block 1004, the network node updates a link state Database (LINK STATE Database, LSDB) according to the first LSP. In block 1006, the network node updates the forwarding paths in the information base according to the first LSP through the second interface.

In block 1008, the network node builds or updates a first SAV table based on one or both of the first LSP and the information base. In block 1010, the network node provides a first SAV table to the data plane over a third interface.

In block 1012, the network node updates the second SAV table according to the first SAV table. In block 1014, the network node generates a second LSP from the first LSP. In block 1016, the network node sends the second LSP to the downstream node along a forwarding path indicated by the information base.

In one embodiment, the second LSP includes a first source node ID and a second plurality of destinations in the first LSP. In one embodiment, the second plurality of destinations all have the same next hop node in the information base. In one embodiment, the third LSP includes a node ID of the network node and a third plurality of destinations. In one embodiment, the third plurality of destinations all have the same next hop node in the information base. When the network node is an ingress node, the network node generates a third LSP and sends the third LSP to the next-hop node.

In one embodiment, the method 1000 further includes adding a prefix of the network node to the third SAV table when the network node is on a forwarding path to a destination in the third LSP. In one embodiment, the information repository includes a routing information repository (Routing Information Base, RIB) or a forwarding information repository (Forwarding Information Base, FIB). In one embodiment, the method 1000 further includes using the first SAV table or the second SAV table to verify the source of one or more incoming messages.

In one embodiment, method 1000 further comprises determining that the forwarding paths in the IS-IS domain are symmetric when each link in the LSDB of the network node has the same overhead or cost in both directions. In one embodiment, when the cost of a link from a first network node to a second network node is the same as the cost of a link from the second network node to the first network node, the links in the LSDB of the network nodes have the same overhead or cost in both directions.

In one embodiment, in constructing the first SAV table or the second SAV table, if each forwarding path in the IS-IS domain or region IS symmetrical, the IS-IS control plane of the network node includes a row in the first SAV table or the second SAV table for each prefix and next-hop interface in the information base.

In one embodiment, method 1000 further comprises determining that the forwarding path in the IS-IS domain IS asymmetric when links in the LSDB of the network node have different overheads or costs in both directions. In one embodiment, when the cost of a link from a first network node to a second network node is different from the cost of a link from the second network node to the first network node, the links in the LSDB of the network nodes have different overheads or costs in both directions.

A method, apparatus, system and computer program product may implement the above embodiments. The disclosed embodiments improve network scalability. The disclosed embodiments may be deployed in any router and switch used by service providers around the world.

Fig. 11 is a schematic diagram of a routing device 1100 (e.g., node 100 or network node A, B, C, D, E, F, G) provided by an embodiment of the present invention. The routing device 1100 is suitable for implementing the disclosed embodiments described herein. In one embodiment, the routing device 1100 may be a router, switch, node, or other communication device for handling internet traffic.

The routing device 1100 includes an ingress port 1110 (or input port 1110) and a receive unit (Rx) 1120 for receiving data, one or more processors, logic units, or central processing units (central processing unit, CPU) 1130 for processing the data, a transmit unit (Tx) 1140 and an egress port 1150 (or output port 1150) for transmitting the data, and a memory 1160 for storing the data. Routing device 1100 may also include an optical-to-electrical (OE) component and an electro-optical (EO) component coupled with ingress port 1110, receive unit 1120, transmit unit 1140, and egress port 1150, serving as an outlet or inlet for optical or electrical signals.

The one or more processors 1130 are implemented in hardware and software. The one or more processors 1130 may be implemented as one or more CPU chips, one or more cores (e.g., implemented as a multi-core processor), one or more field programmable gate arrays (field programmable GATE ARRAY, FPGAs), one or more Application SPECIFIC INTEGRATED Circuits (ASICs), and one or more digital signal processors (DIGITAL SIGNAL processors, DSPs). One or more processors 1130 are in communication with the ingress port 1110, the receive unit 1120, the transmit unit 1140, the egress port 1150, and the memory 1160. Processor 1130 includes IS-IS routing module 1170.IS-IS routing module 1170 implements the disclosed embodiments described above. For example, IS-IS routing module 1170 performs, processes, prepares, or provides various decoding operations. Thus, inclusion of IS-IS routing module 1170 provides substantial improvements to the functionality of routing device 1100 and affects the transition of routing device 1100 to a different state. The IS-IS routing module 1170 IS optionally implemented with instructions stored in memory 1160 and executed by one or more processors 1130.

Memory 1160 may include one or more magnetic disks, one or more magnetic tape drives, and one or more solid state disks, and may be used as an overflow data storage device to store programs when such programs are selected for execution, as well as to store instructions and data that are read during execution of the programs. For example, memory 1160 may be volatile and/or nonvolatile, and may be read-only memory (ROM), random access memory (random access memory, RAM), ternary content addressable memory (ternary content-addressable memory, TCAM), and/or static random-access memory (SRAM).

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

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, modules, techniques, or methods without departing from the scope of the present invention. Other items shown or described as coupled, directly coupled, or communicating with each other may be indirectly coupled or communicating through some interface, device, or intermediate component, whether electrically, mechanically, or otherwise. Other examples of changes, substitutions, and alterations are ascertainable by one skilled in the art and could be made without departing from the spirit and scope disclosed herein.

Claims (20)

1. A source address verification (Source Address Validation, SAV) method implemented by a network node for intermediate system-to-intermediate system (INTERMEDIATE SYSTEM to INTERMEDIATE SYSTEM, IS-IS) routing to a destination in an asymmetric network, the method comprising:

a first link state protocol data unit (LINK STATE Protocol Data Unit, LSP) is received from a first interface, wherein the first LSP comprises:

A first destination prefix identifying a first destination of the first path;

A first destination prefix length indicating a length of the first destination prefix;

Generating an SAV table entry according to the first LSP, wherein the SAV table entry comprises:

A source node prefix as an address of the source node;

The method comprises the steps of receiving a source node prefix, generating a first LSP according to the source node prefix, generating a second LSP according to the first LSP and a destination, and sending the second LSP to a next hop node in a path to the destination.

2. The method of claim 1, wherein the first LSP and the second LSP are both circuit-wide LSPs (Circuit Scoped LSPs, CS-LSPs) and include path type length values (TYPE LENGTH Value, TLV) of internet protocol version four (Internet Protocol version, ipv 4), wherein the path TLV comprises:

A source node ID;

A plurality of IPv4 destinations, wherein each IPv4 destination includes an IPv4 destination prefix and a destination prefix length.

3. The method of claim 1 or2, wherein the first LSP and the second LSP are both circuit-wide LSPs (Circuit Scoped LSPs, CS-LSPs) and include path type length values (TYPE LENGTH Value, TLV) of internet protocol version six (Internet Protocol version, ipv 6), wherein the path TLV includes:

A source node ID;

a plurality of IPv6 destinations, wherein each IPv6 destination includes an IPv6 destination prefix and a destination prefix length.

4. A method according to any one of claims 1 to 3, wherein the second LSP comprises:

a second destination prefix and a second destination prefix length in the first LSP;

The first source node ID.

5. The method of any one of claims 1 to 4, further comprising generating a third LSP when the network node is an ingress node, wherein the third LSP is a circuit-wide LSP (Circuit Scoped LSP, CS-LSP) and comprises:

a third destination prefix and a third destination prefix length of a third destination, wherein the third destination has a third next hop in a routing information base (Routing Information Base, RIB) or forwarding information base (Forwarding Information Base, FIB) of the network node;

the node ID of the network node as the source node ID.

6. A method according to any one of claims 1 to 5, wherein the third next hop is the next hop node in the RIB or FIB of the network node towards the third destination, the network node sending the third LSP to the third next hop.

7. The method of any one of claims 1 to 5, wherein generating the SAV table entry comprises generating or updating a SAV table entry in a first SAV table in an IS-IS control plane of the network node, and transmitting the first SAV table to update a second SAV table in a data plane of the network node.

8. The method of any of claims 1 to 7, wherein the first SAV table or the second SAV table is used to validate a source of an incoming message received from an interface, discard the message if the source and the interface are not in any row of the SAV table, and otherwise forward the message according to the FIB.

9. A source address verification (Source Address Validation, SAV) method implemented by a first node for intermediate system-to-intermediate system (INTERMEDIATE SYSTEM to INTERMEDIATE SYSTEM, IS-IS) routing in an asymmetric network, the method comprising:

calculating a shortest path from the first node to a destination node in the asymmetric network by using reverse overhead of links in the asymmetric network;

Generating a reverse routing table (Reverse Routing Table, RRT), wherein the RRT comprises a source prefix as an address of the destination node and a next hop interface corresponding to the destination node;

and generating an SAV table item according to the RRT, wherein the SAV table item comprises the source prefix and the next hop interface serving as an input interface.

10. The method of claim 9, wherein when there is a link between a source node and a destination node in the network in a link state Database (LINK STATE Database, LSDB), the link from the source node to the destination node has a first cost, the link from the destination node to the source node has a second cost, and the first cost is different from the second cost, the network is determined to be asymmetric.

11. The method according to claim 9 or 10, characterized in that the reverse overhead of a link from a source node to a destination node is the overhead of the link from the destination node to the source node.

12. The method of any one of claims 9 to 11, wherein generating the SAV table entry comprises generating or updating a SAV table entry in a first SAV table in an IS-IS control plane of the first node, and transmitting the first SAV table to update a second SAV table in a data plane of the first node.

13. The method according to any of the claims 9 to 12, characterized in that the SAV table entry is used for verifying the source of an incoming message received from an interface, discarding the message if the source and the interface are not in any row of the SAV table, otherwise forwarding the message according to a forwarding information base (Forwarding Information Base, FIB).

14. A source address verification (Source Address Validation, SAV) method implemented by a first node for intermediate system-to-intermediate system (INTERMEDIATE SYSTEM to INTERMEDIATE SYSTEM, IS-IS) routing in an asymmetric network, the method comprising:

calculating a shortest path between each node in the asymmetric network;

generating an SAV table for each shortest path from a second node and through a first interface via the first node, wherein the SAV table comprises:

a source node prefix as an address of the second node;

The first interface being an ingress interface of the source node prefix.

15. The method of claim 14, wherein when there is a link between a source node and a destination node in the network in a link state Database (LINK STATE Database, LSDB), the link from the source node to the destination node has a first cost, the link from the destination node to the source node has a second cost, and the first cost is different from the second cost, the network is determined to be asymmetric.

16. The method of claim 14 or 15, wherein generating the SAV entry comprises generating or updating an SAV entry in a first SAV table in an IS-IS control plane of the first node and transmitting the first SAV table to update a second SAV table in a data plane of the first node.

17. The method according to any of the claims 14 to 16, characterized in that the SAV table entry is used for verifying the source of an incoming message received from an interface, discarding the message if the source and the interface are not in any row of the SAV table, otherwise forwarding the message according to a forwarding information base (Forwarding Information Base, FIB).

18. A network node in a communication network, the network node comprising:

A memory for storing instructions;

One or more processors coupled to the memory and configured to execute the instructions to cause the network node to perform the method of any one of claims 1 to 17.

19. A computer program product comprising computer-executable instructions stored on a non-transitory medium, wherein the instructions, when executed by one or more processors, cause a network node in a network to perform the method of any one of claims 1 to 17.

20. A computer program product comprising computer-executable instructions stored on a non-transitory medium, wherein the instructions, when executed by one or more processors, cause a network node in an IS-IS network to perform the method of any one of claims 1 to 17.