Patent Description:
In recent years, segment routing (Segment Routing, SR) technologies have been widely applied in a <NUM>th generation (<NUM>th Generation, <NUM>) system, the internet of things, a multi-cloud network, and the like. The SR technologies may be classified into two types: an SR technology based on multi-protocol label switching (Multi-Protocol Label Switching, MPLS), which may be referred to as SR-MPLS, and an SR technology based on the internet protocol version <NUM> (Internet Protocol Version, IPv6), which may be referred to as SRv6.

Currently, if the SRv6 technology needs to be used, all devices in a network need to support SRv6. Only in this way can a controller obtain a network topology and calculate a path that meets a service level agreement (Service Level Agreement, SLA). However, it is too difficult for an operator to upgrade all the devices in the network. On one hand, because there are a large quantity of devices in the network, it takes a relatively long time to upgrade all the devices in the network. On another hand, some devices require hardware upgrade to support SRv6. This increases upgrade costs.

<CIT> discloses a network that includes a data forwarding node including: a logical network topology management unit managing a correspondence relationship among at least two different logical network topologies generated by applying different policies to a physical network topology and data traffic conditions to which the logical network topologies are applied; and a packet processing unit selecting a logical network topology corresponding to data traffic to which an incoming packet belongs, determining a packet forwarding destination, and transmitting the incoming packet. The data forwarding node selects a logical network and forwards a packet, based on data traffic.

<CIT> discloses that a router operates in both a Segment Routing (SR) network portion and a Multiprotocol Label Switching (MPLS) network portion of a network that utilizes Intermediate System to Intermediate System (IS-IS). The router receives an IS-IS advertisement message originated by a mapping server that includes a sub-Type-length-value (sub-TLV) element that identifies a preferred type of path across the MPLS network portion for an identifiable set of traffic to be received by the router from the SR network portion. The router identifies, based at least in part upon the sub-TLV element, one path of a plurality of available paths across the MPLS network portion for the identifiable set of traffic, and configures its forwarding plane to utilize the identified one path for the identifiable set of traffic. The IS-IS advertisement message can be an IS-IS TLV such as a SID/Label Binding TLVor Multi-topology SID/Label Binding TLV.

<CIT> discloses a traffic engineering method of an IPv6 network based on partially deployed segmented routing. The traffic engineering method comprises the following steps: acquiring a network topology of the IPv6 network, an initial network link weight matrix and a plurality of traffic matrixes within a set time length; based on the plurality of flow matrixes in the set time length, calculating a representative flow matrix in the set time length; based on the network topology, the initial network link weight matrix and the representative flow matrix, carrying out M times of training on the deep reinforcement learning network, and according to the Mth time of training of the deep reinforcement learning network, determining an optimized network link weight matrix, a segmented routing node set and a corresponding minimized maximum link utilization rate; wherein M is a positive integer greater than <NUM>.

This application provides a path determining method and a related device, so that a new network topology may be established by using an existing network topology structure, to reduce difficulty in path computation, thereby reducing a burden of a management device.

According to a first aspect, an embodiment of this application provides a path determining method, including: determining N<NUM> first-type nodes from N nodes included in a first network topology, where the N nodes include the N<NUM> first-type nodes and N<NUM> second-type nodes, the first-type node supports segment routing over internet protocol version <NUM> SRv6, N<NUM> is a positive integer greater than or equal to <NUM>, and N<NUM> is a positive integer greater than or equal to <NUM>; determining a second network topology corresponding to the first network topology, where the second network topology includes the N<NUM> first-type nodes but does not include the N<NUM> second-type nodes, the target topology structure includes M first-type target paths, an ith first-type target path in the M first-type target paths corresponds to Ki paths in the first network topology, a source node and a destination node of the Ki paths are the same as a source node and a destination node of the ith first-type target path, each of the Ki paths includes at least one second-type node, M is a positive integer greater than or equal to <NUM>, i = <NUM>,. , or M, and Ki is a positive integer greater than or equal to <NUM>; determining transmission overheads of the M first-type target paths, where a transmission overhead of the ith first-type target path is a smallest value of transmission overheads of the Ki paths; and performing path computation based on the transmission overheads of the M first-type target paths and the second network topology.

In the foregoing technical solution, a new network topology may be established by using an existing network topology structure. The new network topology includes only some nodes in the original network topology, and all these nodes support SRv6. In this way, difficulty in path computation may be reduced, to reduce a burden of a management device.

With reference to the first aspect, in a possible implementation of the first aspect, the first-type node is a node that supports SRv6 in the N nodes, and the second-type node is a node that does not support SRv6 in the N nodes. Alternatively, the first-type node is a key node in the N nodes, and the second-type node is a non-key node in the N nodes.

In the foregoing technical solution, a node that does not support SRv6 and/or a non-key node in the original network topology may be removed, to obtain the new network topology. All nodes in the network topology support SRv6. In this way, even if a node that does not support SRv6 exists in a network, a packet may be forwarded based on a path determined by the management device. Alternatively, the non-key node is ignored during path computation, so that the difficulty in path computation may be reduced, to reduce the burden of the management device.

With reference to the first aspect, in a possible implementation of the first aspect, the method further includes: obtaining a transmission overhead between two adjacent nodes in the first network topology. The determining transmission overheads of the M first-type target paths includes: determining a transmission overhead of each of the Ki paths based on a transmission overhead between two adjacent nodes on each of the Ki paths, and determining the smallest value of the transmission overheads of the Ki paths as the transmission overhead of the ith first-type target path.

With reference to the first aspect, in a possible implementation of the first aspect, the determining transmission overheads of the M first-type target paths includes: performing transmission overhead measurement on the ith first-type target path to obtain the transmission overhead of the ith first-type target path.

The transmission overhead of the ith first-type target path may be directly obtained through measurement by using the foregoing technical solution. In other words, when a transmission overhead is obtained through measurement, a node on a path forwards a measurement packet based on a shortest path. Therefore, the obtained transmission overhead is a smallest transmission overhead. Therefore, the smallest value of the transmission overheads may be directly obtained by using the foregoing technical solution, to reduce a workload of the management device.

With reference to the first aspect, in a possible implementation of the first aspect, the performing transmission overhead measurement on the ith first-type target path to obtain the transmission overhead of the ith first-type target path includes: sending measurement information to the source node and/or the destination node of the ith first-type target path; and receiving measurement feedback information from the source node and/or the destination node of the ith first-type target path, where the measurement feedback information includes the transmission overhead of the ith first-type target path.

With reference to the first aspect, in a possible implementation of the first aspect, the second network topology further includes P second-type target paths, and each of the P second-type target paths includes two of the N<NUM> first-type nodes, and the first network topology includes the P second-type target paths.

With reference to the first aspect, in a possible implementation of the first aspect, the transmission overhead includes a transmission cost and/or a transmission delay.

According to a second aspect, an embodiment of this application provides a management device. The management device includes units configured to implement any possible implementation of the method design in the first aspect. The management device may be a computer device or a component (for example, a chip or a circuit) configured for a computer device.

According to a third aspect, an embodiment of this application provides a computer-readable medium. The computer-readable medium stores program code. When the computer program code is run on a computer, the computer is enabled to perform the method in any possible implementation of the method design in the first aspect.

All aspects, embodiments, or features are presented in this application by describing a system that may include a plurality of devices, components, modules, and the like. It should be appreciated and understood that each system may include another device, component, module, and the like, and/or may not include all devices, components, modules, and the like discussed with reference to the accompany drawings. In addition, a combination of these solutions may be used.

In addition, in the embodiments of this application, the terms such as "example" and "such as" are used to represent giving an example, an illustration, or a description. Any embodiment or design scheme described as an "example" in this application should not be explained as being more preferred or having more advantages than another embodiment or design scheme. Exactly, the term "example" is used to present a concept in a specific manner.

In the embodiments of this application, if a technical means, operation, or limitation is not emphasized as mandatory, it indicates that the technical means, operation, or limitation is optional.

In the embodiments of this application, information (information), a signal (signal), a message (message), or a channel (channel) may be interchangeably used sometimes. It should be noted that meanings expressed by the terms are consistent when differences between the terms are not emphasized. "Relevant (relevant)" and "corresponding (corresponding)" may be interchangeably used sometimes. It should be noted that meanings expressed by the terms are consistent when differences are not emphasized.

In the embodiments of this application, sometimes a subscript such as W<NUM> may be written in an incorrect form such as W1. Expressed meanings are consistent when differences are not emphasized.

A network architecture and a service scenario described in the embodiments of this application are intended to describe the technical solutions in the embodiments of this application more clearly, and do not constitute a limitation on the technical solutions provided in the embodiments of this application. A person of ordinary skill in the art may know that with evolution of the network architecture and emergence of a new service scenario, the technical solutions provided in the embodiments of this application are also applicable to similar technical problems.

Reference to "an embodiment", "some embodiments", or the like described in this specification indicates that one or more embodiments of this application include a specific feature, structure, or characteristic described with reference to the embodiments. Therefore, statements, such as "in an embodiment", "in some embodiments", "in some other embodiments", and "in other embodiments", that appear at different places in this specification do not necessarily mean referring to a same embodiment, instead, the statements mean referring to "one or more but not all of the embodiments", unless otherwise specifically emphasized in other ways. The terms "include", "comprise", "have", and variants of the terms all mean "include but are not limited to", unless otherwise specifically emphasized in other ways.

In this application, "at least one" means one or more, and "a plurality of" means two or more. The term "and/or" describes an association between associated objects and represents that three relationships may exist. For example, A and/or B may represent the following cases: Only A exists, both A and B exist, and only B exists, where A and B may be singular or plural. The character "/" generally indicates an "or" relationship between the associated objects. "At least one of the following" or a similar expression thereof means any combination of the following, including any combination of one or more of the following. For example, at least one of a, b, or c may represent: a, b, c, a and b, a and c, b and c, or a, b, and c, where a, b, and c may be singular or plural.

<FIG> is a schematic diagram of a network structure. A network <NUM> shown in <FIG> includes eight nodes: a node <NUM>, a node <NUM>, a node <NUM>, a node <NUM>, a node <NUM>, a node <NUM>, a node <NUM>, and a node <NUM>. The network <NUM> may be a complete network or part of a complete network.

The nodes (namely, the node <NUM> to the node <NUM>) in the network <NUM> shown in <FIG> may also be referred to as network nodes. The node may be a device such as a workstation, a server, a terminal device, or a network device. Each device may have a different IPv6 address. Two adjacent nodes (for example, the node <NUM> and the node <NUM>, the node <NUM> and the node <NUM>, or the node <NUM> and the node <NUM>) in the network <NUM> shown in <FIG> may be connected by using a wired or wireless medium. An intermediate device may not be included between the two adjacent nodes, or one or more intermediate devices (for example, some switches or optical devices) that do not perform Layer <NUM> forwarding (namely, forwarding based on an internet protocol (Internet Protocol, IP) address) on a packet may be included between the two adjacent nodes.

The nodes in the network <NUM> may be classified into a first-type node and a second-type node.

Optionally, in some embodiments, both the first-type node and the second-type node support SRv6. The first-type node is a key node in the network <NUM>, and the second-type node is a non-key node in the network <NUM>. In some embodiments, the key node may be a border node between two networks. For example, the network may include an access layer, an aggregation layer, a core layer, and the like. Key nodes may be border nodes at these layers. Optionally, in some other embodiments, the key node may be an egress edge node in a network. Correspondingly, the non-key node may be another node other than the key node.

In some other embodiments, the first-type node is a node that supports SRv6, and the second-type node is a node that does not support SRv6.

Alternatively, the first-type node may be a node that supports SRv6 and the first-type node is a key node in the network <NUM>, and the second-type node may be a node that does not support SRv6, or the second-type node may be a node that supports SRv6 and the second-type node is a non-key node in the network <NUM>.

For ease of description, in the following embodiments, it is assumed that the first-type node is the node that supports SRv6, and the second-type node is the node that does not support SRv6.

With reference to the network structure shown in <FIG>, the technical solutions of this application are described in detail in <FIG>. For ease of description, in an embodiment shown in <FIG>, it is assumed that the node <NUM> and the node <NUM> are nodes that do not support SRv6. The node <NUM>, the node <NUM>, the node <NUM>, the node <NUM>, the node <NUM>, and the node <NUM> are nodes that support SRv6. It may be understood that the specific embodiment shown in <FIG> is merely intended to help a person skilled in the art better understand the technical solutions of this application, but is not intended to limit the technical solutions of this application to a limited embodiment.

<FIG> is a schematic flowchart of a path determining method according to an embodiment of this application. The method shown in <FIG> may be performed by a management device in a network. The management device may be a general-purpose computer device, for example, a notebook computer or a personal computer, or may be a dedicated network management device.

<NUM>: The management device determines a topology structure of the network <NUM>.

A specific implementation in which the management device obtains the topology structure of the network <NUM> is not limited in this embodiment of this application. For example, the management device may establish a border gateway protocol-link state (Border Gateway Protocol-Link State, BGP-LS) or an interior gateway protocol (Interior Gateway Protocol, IGP) neighbor with the node in the network <NUM>. The node in the network <NUM> obtains the topology structure of the network <NUM> through BGP-LS or IGP, and sends the obtained topology structure of the network <NUM> to the management device.

<NUM>: The management device determines the first-type node from the nodes included in the network <NUM>.

The nodes in the network <NUM> may be classified into the first-type node and the second-type node based on whether the node supports SRv6. The first-type node is the node that supports SRv6, and the second-type node is the node that does not support SRv6.

As assumed above, the network <NUM> includes six first-type nodes (namely, the node <NUM>, the node <NUM>, the node <NUM>, the node <NUM>, the node <NUM>, and the node <NUM>) and two second-type nodes (namely, the node <NUM> and the node <NUM>) in total.

Any method available in this network environment for determining a type of the node in the network <NUM> may be applied to this embodiment.

For example, in some embodiments, the management device may determine a type of each node in the network <NUM> by the management device. For example, the management device may obtain SRv6 indication information. The SRv6 indication information is used to indicate whether each node in the network <NUM> supports SRv6. In this case, the management device may determine, based on the SRv6 indication information, the first-type node included in the network <NUM>.

Optionally, in some embodiments, the management device may obtain the SRv6 indication information in a process of determining the topology structure of the network <NUM>. For example, in the process of determining the topology structure of the network <NUM>, the management device may obtain topology information reported by each node in the network <NUM>. The topology information includes the SRv6 indication information.

Optionally, in other embodiments, the management device may send SRv6 query information to each node in the network <NUM>. After receiving the SRv6 query information, the node in the network <NUM> sends SRv6 query feedback information to the management device. The SRv6 query feedback information is used to indicate whether the node supports SRv6.

For another example, in some other embodiments, the management device may determine the type of each node in the network <NUM> based on a manual annotation of an administrator. For example, the administrator of the management device may view a maintenance log of the network <NUM> or manually query attribute information of each node in the network <NUM> to determine whether each node in the network <NUM> supports SRv6, and store a determining result in the management device. In this case, the management device may determine the first-type node in the network <NUM> based on the stored determining result.

<NUM>: The management device determines a target topology structure corresponding to the network <NUM>.

<FIG> is a schematic diagram of the target topology structure that is corresponding to the network <NUM> and that is determined by the management device. A target topology structure <NUM> shown in <FIG> includes the first-type nodes in the network <NUM> but does not include a second-type network node in the network <NUM>. The target topology structure <NUM> shown in <FIG> includes the node <NUM>, the node <NUM>, the node <NUM>, the node <NUM>, the node <NUM>, and the node <NUM>, but does not include the node <NUM> and the node <NUM>.

If two adjacent nodes in the network <NUM> both are first-type nodes, the management device may determine that a connection relationship between the two nodes in the network <NUM> is the same as that in the target topology structure. For example, a connection relationship between the node <NUM> and the node <NUM>, a connection relationship between the node <NUM> and the node <NUM>, a connection relationship between the node <NUM> and the node <NUM>, a connection relationship between the node <NUM> and the node <NUM>, and a connection relationship between the node <NUM> and the node <NUM> in the target topology structure <NUM> are the same as those in the network <NUM>. For ease of description, a path between two nodes between which a connection relationship in the network <NUM> is the same as a connection relationship in the target topology structure may be referred to as a second-type target path. In other words, in the target topology structure shown in <FIG>, a path between the node <NUM> and the node <NUM>, a path between the node <NUM> and the node <NUM>, a path between the node <NUM> and the node <NUM>, a path between the node <NUM> and the node <NUM>, and a path between the node <NUM> and the node <NUM> are all second-type target paths.

If one or more second-type nodes are included between two first-type nodes in the network <NUM>, the management device may determine that there is a directly connected path between the two first-type nodes in the target topology structure. In addition, the management device may further determine, in the network <NUM>, one or more paths corresponding to the path. For ease of description, a path between two nodes between which a connection relationship in the network <NUM> is different from a connection relationship in the target topology structure may be referred to as a first-type target path. In other words, in the target topology structure <NUM> shown in <FIG>, a path between the node <NUM> and the node <NUM>, a path between the node <NUM> and the node <NUM>, a path between the node <NUM> and the node <NUM>, and a path between the node <NUM> and the node <NUM> are first-type target paths.

The following describes the first-type target path by using the node <NUM> and the node <NUM> as an example. For ease of description, in the following, the first-type target path between the node <NUM> and the node <NUM> in the target topology structure <NUM> is referred to as a first-type target path <NUM>. A path between two adjacent nodes in the network <NUM> is referred to as a link. A path between the node <NUM> and the node <NUM> is referred to as a link <NUM>, a path between the node <NUM> and the node <NUM> is referred to as a link <NUM>, and so on.

In the network <NUM>, the node <NUM> may communicate with the node <NUM> through a plurality of paths. For example, a path <NUM> may include the link <NUM> and the link <NUM>. A path <NUM> may include the link <NUM>, a link <NUM>, a link <NUM>, and a link <NUM>. A path <NUM> may include a link <NUM>, a link <NUM>, a link <NUM>, and the link <NUM>. A path <NUM> may include the link <NUM>, the link <NUM>, the link <NUM>, and the link <NUM>. It can be learned that each of the path <NUM> to the path <NUM> includes at least one second-type node.

The path <NUM>, the path <NUM>, the path <NUM>, and the path <NUM> may be referred to as paths corresponding to the first-type target path <NUM>. In other words, in the target topology structure <NUM>, the first-type target path <NUM> has four corresponding paths in the network <NUM>: the path <NUM>, the path <NUM>, the path <NUM>, and the path <NUM>. Similarly, in the target topology structure <NUM>, the first-type target path between the node <NUM> and the node <NUM> also has a plurality of corresponding paths in the network <NUM>. The first-type target path between the node <NUM> and the node <NUM> also has a plurality of corresponding paths in the network <NUM>. The first-type target path between the node <NUM> and the node <NUM> also has a plurality of corresponding paths in the network <NUM>.

In conclusion, the management device may determine that the target topology structure includes four first-type target paths and five second-type target paths in total.

<NUM>: The management device may determine a transmission overhead of each of the four first-type target paths.

In some embodiments, the transmission overhead is a transmission delay. In some other embodiments, the transmission overhead is a transmission cost. The transmission cost may also be referred to as a link cost. In some other embodiments, the transmission overhead may include a transmission cost and a transmission delay. In some other embodiments, the transmission overhead may be a value determined based on a transmission cost and a transmission delay. For example, the transmission overhead may be determined according to a formula <NUM>: <MAT>.

Con represents the transmission overhead, C represents the transmission cost, D represents the transmission delay, α represents a weight coefficient corresponding to the transmission overhead, and β represents a weight coefficient corresponding to the transmission delay. α and β are numbers greater than <NUM>.

The first-type target path <NUM> is still used as an example to describe a specific implementation in which the management device determines the transmission overhead of the first-type target path.

Optionally, in some embodiments, the management device may obtain a transmission overhead between two adjacent nodes on each of the four paths (namely, the path <NUM> to the path <NUM>) corresponding to the first-type target path <NUM>. For example, topology information obtained by the management device may include a transmission overhead between two adjacent nodes in the network <NUM>. The path <NUM> is used as an example. The management device may obtain a transmission overhead between the node <NUM> and the node <NUM> (namely, a transmission overhead of the link <NUM>). The management device may further obtain a transmission overhead between the node <NUM> and the node <NUM> (namely, a transmission overhead of the link <NUM>). In this way, the management device may determine that a transmission overhead of the path <NUM> (hereinafter referred to as a transmission overhead <NUM>) is a sum of the transmission overhead of the link <NUM> and the transmission overhead of the link <NUM>. Similarly, the management device may determine a transmission overhead of the path <NUM> (hereinafter referred to as a transmission overhead <NUM>), a transmission overhead of the path <NUM> (hereinafter referred to as a transmission overhead <NUM>), and a transmission overhead of the path <NUM> (hereinafter referred to as a transmission overhead <NUM>). After determining the transmission overhead <NUM> to the transmission overhead <NUM>, the management device may determine a transmission overhead of the first-type target path <NUM> as a smallest value of the transmission overhead <NUM> to the transmission overhead <NUM>.

In some embodiments, the transmission overhead includes the transmission cost and the transmission delay. In this case, a smallest value of a plurality of transmission overheads may be a value of a transmission overhead with a smallest transmission delay in the plurality of transmission overheads.

In some other embodiments, the transmission overhead includes the transmission cost and the transmission delay. In this case, a smallest value of a plurality of transmission overheads may be a value of a transmission overhead with a smallest transmission cost in the plurality of transmission overheads.

In some embodiments, the transmission overhead includes the transmission cost and the transmission delay. In this case, when transmission delays are different, a smallest value of a plurality of transmission overheads is a smallest value of the transmission delays. Alternatively, when transmission delays are the same, a smallest value of a plurality of transmission overheads is a smallest value of transmission costs.

Optionally, in some other embodiments, the management device may perform transmission overhead measurement on the first-type target path <NUM>, to obtain the transmission overhead of the first-type target path <NUM>.

For example, the management device may send measurement information to a target node. The measurement information is used to indicate the target node to perform delay measurement. The target node may be the node <NUM> and/or the node <NUM>. After receiving the measurement information, the target node may perform delay measurement. For example, the target node may use a technology, such as a network quality analysis (Network Quality Analysis, NQA) technology, a two-way active measurement protocol (Two-Way Active Measurement Protocol, TWAMP), or a packet internet groper (Packet Internet Groper, PING) to perform delay measurement on the path between the node <NUM> and the node <NUM>. The target node may obtain the transmission delay of the first-type target path <NUM>. The target node may send measurement feedback information to the management device. The measurement feedback information includes the transmission overhead of the first-type target path <NUM>.

In some embodiments, the target node may directly send a measured transmission delay to the management device as a transmission overhead.

In some other embodiments, the target node may determine a transmission cost based on a transmission delay, and send the transmission delay and the transmission cost to the management device as a transmission overhead. For example, the target node may determine, based on a preset correspondence between a transmission cost and a transmission delay, a transmission overhead corresponding to the measured transmission delay. For another example, the target node may determine, according to on a preset formula, a transmission overhead corresponding to the measured transmission delay.

In some other embodiments, the target node may determine a transmission cost based on a transmission delay, and send the transmission cost to the management device as a transmission overhead.

In this case, the management device may directly obtain the transmission overhead of the first-type target path <NUM>. The transmission overhead of the first-type target path <NUM> is a smallest value of transmission overheads from the node <NUM> to the node <NUM>.

Similarly, the management device may determine a transmission overhead of the first-type target path between the node <NUM> and the node <NUM> in the target topology structure <NUM>, a transmission overhead of the first-type target path between the node <NUM> and the node <NUM>, and a transmission overhead of the first-type target path between the node <NUM> and the node <NUM>.

A manner of determining a transmission overhead of each of the five second-type target paths is the same as or similar to a manner of determining the transmission overhead of the first-type target path. For example, the topology information obtained by the management device may include the transmission overhead between two adjacent nodes in the network <NUM>. In this way, the management device can directly determine the transmission overhead of each second-type target path. For another example, the management device may alternatively determine the transmission overhead of each of the five second-type target paths through measurement. A specific measurement manner is the same as a measurement manner for measuring the transmission overhead of the first-type target path. For brevity, details are not described herein again.

<NUM>: The management device may perform path computation based on the transmission overheads of the four first-type target paths and the target topology structure.

For example, if the management device wants to determine a path from the node <NUM> to the node <NUM>, the management device may determine, based on the four first-type target paths, whether the path reaches the node <NUM> through the node <NUM> or the node <NUM>. For ease of description, it is assumed that the transmission overhead is the transmission delay. It is assumed that a transmission delay from the node <NUM> to the node <NUM> is <NUM>, a transmission overhead from the node <NUM> to the node <NUM> is <NUM>, a transmission overhead from the node <NUM> to the node <NUM> is <NUM>, and a transmission overhead from the node <NUM> to the node <NUM> is <NUM>, and a transmission overhead from the node <NUM> to the node <NUM> is <NUM>. If the path from the node <NUM> to the node <NUM> passes through the node <NUM> and the node <NUM>, a total transmission overhead is <NUM>. If the path from the node <NUM> to the node <NUM> passes through the node <NUM>, a total transmission overhead is <NUM>. In this case, the management device may determine that the path from the node <NUM> to the node <NUM> passes through the node <NUM> and the node <NUM>.

<FIG> is a schematic flowchart of a path determining method according to an embodiment of this application. The method shown in <FIG> may be implemented by a management device or a component (for example, a chip or a circuit) in a management device.

<NUM>: Determine N<NUM> first-type nodes from N nodes included in a first network topology, where the N nodes include the N<NUM> first-type nodes and N<NUM> second-type nodes, the first-type node supports SRv6, N<NUM> is a positive integer greater than or equal to <NUM>, and N<NUM> is a positive integer greater than or equal to <NUM>.

<NUM>: Determine a second network topology corresponding to the first network topology, where the second network topology includes the N<NUM> first-type nodes but does not include the N<NUM> second-type nodes, the target topology structure includes M first-type target paths, an ith first-type target path in the M first-type target paths corresponds to Ki paths in the first network topology, a source node and a destination node of the Ki paths are the same as a source node and a destination node of the ith first-type target path, each of the Ki paths includes at least one second-type node, M is a positive integer greater than or equal to <NUM>, i = <NUM>,. , or M, and Ki is a positive integer greater than or equal to <NUM>.

For example, the first network topology may be the network topology structure of the network <NUM> shown in <FIG>. The node <NUM>, the node <NUM>, the node <NUM>, the node <NUM>, the node <NUM>, and the node <NUM> in the network <NUM> may be first-type nodes, and the node <NUM> and the node <NUM> may be second-type nodes. The second network topology may be the target topology structure <NUM> shown in <FIG>. The target topology structure <NUM> includes the node <NUM>, the node <NUM>, the node <NUM>, the node <NUM>, the node <NUM>, and the node <NUM>.

<NUM>: Determine transmission overheads of the M first-type target paths, where a transmission overhead of the ith first-type target path is a smallest value of transmission overheads of the Ki paths.

<NUM>: Perform path computation based on the transmission overheads of the M first-type target paths and the second network topology.

Optionally, the first-type node is a node that supports SRv6 in the N nodes, and the second-type node is a node that does not support SRv6 in the N nodes. Alternatively, the first-type node is a key node in the N nodes, and the second-type node is a non-key node in the N nodes.

Optionally, the method further includes: obtaining a transmission overhead between two adjacent nodes in the first network topology. Determining the transmission overheads of the M first-type target paths includes: determining a transmission overhead of each of the Ki paths based on a transmission overhead between two adjacent nodes on each of the Ki paths, and determining the smallest value of the transmission overheads of the Ki paths as the transmission overhead of the ith first-type target path.

Optionally, determining the transmission overheads of the M first-type target paths includes: performing transmission overhead measurement on the ith first-type target path to obtain the transmission overhead of the ith first-type target path.

Optionally, the performing transmission overhead measurement on the ith first-type target path to obtain the transmission overhead of the ith first-type target path includes: sending measurement information to the source node and/or the destination node of the ith first-type target path; and receiving measurement feedback information from the source node and/or the destination node of the ith first-type target path. The measurement feedback information includes the transmission overhead of the ith first-type target path.

Optionally, the second network topology further includes P second-type target paths, each of the P second-type target paths includes two of the N<NUM> first-type nodes, and the first network topology includes the P second-type target paths.

Optionally, the transmission overhead includes a transmission cost and a transmission delay.

For a specific implementation of each step of the method shown in <FIG>, refer to the embodiment shown in <FIG>. For brevity, details are not described herein again.

<FIG> is a schematic structural block diagram of a management device according to an embodiment of this application. A management device <NUM> shown in <FIG> includes a topology management unit <NUM>, a data collection unit <NUM>, and a path computation unit <NUM>.

The topology management unit <NUM> is configured to determine N<NUM> first-type nodes from N nodes included in a first network topology. The N nodes include the N<NUM> first-type nodes and N<NUM> second-type nodes. The first-type node supports segment routing over internet protocol version <NUM> SRv6. N<NUM> is a positive integer greater than or equal to <NUM>, and N<NUM> is a positive integer greater than or equal to <NUM>.

The topology management unit <NUM> is further configured to determine a second network topology corresponding to the first network topology. The second network topology includes the N<NUM> first-type nodes but does not include the N<NUM> second-type nodes. The target topology structure includes M first-type target paths. An ith first-type target path in the M first-type target paths corresponds to Ki paths in the first network topology. A source node and a destination node of the Ki paths are the same as a source node and a destination node of the ith first-type target path. Each of the Ki paths includes at least one second-type node. M is a positive integer greater than or equal to <NUM>, i = <NUM>,. , or M, and Ki is a positive integer greater than or equal to <NUM>.

The data collection unit <NUM> is configured to determine transmission overheads of the M first-type target paths, where a transmission overhead of the ith first-type target path is a smallest value of transmission overheads of the Ki paths.

The path computation unit <NUM> is configured to perform path computation based on the transmission overheads of the M first-type target paths and the second network topology.

Optionally, a transmission overhead between two adjacent nodes in the first network topology is obtained. The data collection unit <NUM> is specifically configured to: determine a transmission overhead of each of the Ki paths based on a transmission overhead between two adjacent nodes on each of the Ki paths, and determine the smallest value of the transmission overheads of the Ki paths as the transmission overhead of the ith first-type target path.

Optionally, the data collection unit <NUM> is specifically configured to perform transmission overhead measurement on the ith first-type target path to obtain the transmission overhead of the ith first-type target path.

Optionally, the data collection unit <NUM> is specifically configured to: send measurement information to the source node and/or the destination node of the ith first-type target path; and receive measurement feedback information from the source node and/or the destination node of the ith first-type target path, where the measurement feedback information includes the transmission overhead of the ith first-type target path.

For specific functions of the topology management unit <NUM>, the data collection unit <NUM>, and the path computation unit <NUM>, refer to the method shown in <FIG>. For brevity, details are not described herein again.

The topology management unit <NUM>, the data collection unit <NUM>, and the path computation unit <NUM> may be implemented by a processor.

<FIG> is a schematic structural block diagram of a management device according to an embodiment of this application. The management device <NUM> includes a bus <NUM>, a processor <NUM>, a communications interface <NUM>, and a memory <NUM>. The processor <NUM>, the memory <NUM>, and the communications interface <NUM> communicate with each other through the bus <NUM>. The processor <NUM> may be a field programmable gate array (field programmable gate array, FPGA), an application-specific integrated circuit (application-specific integrated circuit, ASIC), system on chip (system on chip, SoC), a central processing unit (central processing unit, CPU), a network processor (network processor, NP), a digital signal processor (digital signal processor, DSP), a micro controller unit (micro controller unit, MCU), a programmable logic device (programmable logic device, PLD), another programmable logic device, a discrete gate or transistor logic device, a discrete hardware component, or another integrated chip. The memory <NUM> stores executable code included in a management device. The processor <NUM> reads the executable code in the memory <NUM> to perform the method shown in <FIG> or <FIG>. The memory <NUM> may further include another software module, such as an operating system, required for running a process. The operating system may be LINUX™, UNIX™, WINDOWS™, or the like.

An embodiment of this application further provides a chip system, including a logic circuit. The logic circuit is configured to be coupled to an input/output interface, and perform data transmission through the input/output interface, to perform the method shown in <FIG> or <FIG>.

In an implementation process, steps in the foregoing methods can be implemented by using a hardware integrated logical circuit in the processor, or by using instructions in a form of software. The steps of the methods disclosed with reference to the embodiments of this application may be directly performed by a hardware processor, or may be performed by using a combination of hardware in the processor and a software module. The software module may be located in a mature storage medium in the art, such as a random access memory, a flash memory, a read-only memory, a programmable read-only memory, an electrically erasable programmable memory, or a register. The storage medium is located in the memory, and the processor reads information in the memory and completes the steps in the foregoing methods in combination with hardware of the processor. To avoid repetition, details are not described herein again.

It should be noted that the processor in the embodiments of this application may be an integrated circuit chip, and has a signal processing capability. In an implementation process, steps in the foregoing method embodiments can be implemented by using a hardware integrated logical circuit in the processor, or by using instructions in a form of software. A general-purpose processor may be a microprocessor, or the processor may be any conventional processor or the like. The steps of the methods disclosed with reference to the embodiments of this application may be directly performed and completed by a hardware decoding processor, or may be performed and completed by using a combination of hardware and software modules in the decoding processor. The software module may be located in a mature storage medium in the art, such as a random access memory, a flash memory, a read-only memory, a programmable read-only memory, an electrically erasable programmable memory, or a register. The storage medium is located in the memory, and the processor reads information in the memory and completes the steps in the foregoing methods in combination with hardware of the processor.

It may be understood that the memory in the embodiments of this application may be a volatile memory or a nonvolatile memory, or may include a volatile memory and a nonvolatile memory. The nonvolatile memory may be a read-only memory (read-only memory, ROM), a programmable read-only memory (programmable ROM, PROM), an erasable programmable read-only memory (erasable PROM, EPROM), an electrically erasable programmable read-only memory (electrically EPROM, EEPROM), or a flash memory. The volatile memory may be a random access memory (random access memory, RAM), used as an external cache. Through example but not limitative description, many forms of RAMs may be used, for example, a static random access memory (static RAM, SRAM), a dynamic random access memory (dynamic RAM, DRAM), a synchronous dynamic random access memory (synchronous DRAM, SDRAM), a double data rate synchronous dynamic random access memory (double data rate SDRAM, DDR SDRAM), an enhanced synchronous dynamic random access memory (enhanced SDRAM, ESDRAM), a synchronous link dynamic random access memory (synchlink DRAM, SLDRAM), and a direct rambus dynamic random access memory (direct rambus RAM, DR RAM). It should be noted that the memory of the systems and methods described in this specification includes but is not limited to these and any memory of another proper type.

According to the methods provided in the embodiments of this application, this application further provides a computer program product. The computer program product includes computer program code. When the computer program code is run on a computer, the computer is enabled to perform the method in any embodiment shown in <FIG> or <FIG>.

According to the methods provided in the embodiments of this application, this application further provides a computer-readable medium. The computer-readable medium stores program code. When the program code is run on a computer, the computer is enabled to perform the method in any embodiment shown in <FIG> or <FIG>.

According to the methods provided in the embodiments of this application, this application further provides a system, including the foregoing management device. The system further includes a plurality of nodes. The plurality of nodes include at least two nodes that support SRv6.

It may be clearly understood by a person skilled in the art that, for the purpose of convenient and brief description, for a detailed working process of the foregoing system, apparatus, and units, refer to a corresponding process in the foregoing method embodiments, and details are not described herein again.

For example, the unit division is merely logical function division and may be other division in an actual implementation.

When the functions are implemented in a form of a software functional unit and sold or used as an independent product, the functions may be stored in a computer-readable storage medium. Based on such an understanding, the technical solutions of this application essentially, or the part contributing to the conventional technology, or some of the technical solutions may be implemented in a form of a software product. The software product is stored in a storage medium, and includes several instructions for instructing a computer device (which may be a personal computer, a server, or a network device) to perform all or some of the steps of the methods described in the embodiments of this application. The foregoing storage medium includes: any medium that can store program code, such as a USB flash drive, a removable hard disk, a read-only memory (Read-Only Memory, ROM), a random access memory (Random Access Memory, RAM), a magnetic disk, or an optical disc.

Claim 1:
A path determining method, comprising:
determining (<NUM>) N<NUM> first-type nodes (<NUM>-<NUM>) from N nodes comprised in a first network topology, wherein the N nodes comprise the N<NUM> first-type nodes (<NUM>-<NUM>) and N<NUM> second-type nodes (<NUM>-<NUM>), the first-type node supports segment routing over internet protocol version <NUM>, SRv6, N<NUM> is a positive integer greater than or equal to <NUM>, and N<NUM> is a positive integer greater than or equal to <NUM>;
determining (<NUM>) a second network topology corresponding to the first network topology, wherein the second network topology comprises the N<NUM> first-type nodes (<NUM>-<NUM>) but does not comprise the N<NUM> second-type nodes (<NUM>-<NUM>), a target topology structure (<NUM>) comprises M first-type target paths, an ith first-type target path in the M first-type target paths corresponds to Ki paths in the first network topology, a source node and a destination node of the Ki paths are the same as a source node and a destination node of the ith first-type target path, each of the Ki paths comprises at least one second-type node, M is a positive integer greater than or equal to <NUM>, i = <NUM>, ..., or M, and Ki is a positive integer greater than or equal to <NUM>;
determining (<NUM>) transmission overheads of the M first-type target paths, wherein a transmission overhead of the ith first type target path is a smallest value of transmission overheads of the Ki paths; and
performing (<NUM>) path computation based on the transmission overheads of the M first-type target paths and the second network topology.