WO2016082580A1 - 负载分担的方法和路由设备 - Google Patents

负载分担的方法和路由设备 Download PDF

Info

Publication number
WO2016082580A1
WO2016082580A1 PCT/CN2015/086261 CN2015086261W WO2016082580A1 WO 2016082580 A1 WO2016082580 A1 WO 2016082580A1 CN 2015086261 W CN2015086261 W CN 2015086261W WO 2016082580 A1 WO2016082580 A1 WO 2016082580A1
Authority
WO
WIPO (PCT)
Prior art keywords
load sharing
routing device
information
load
relationship
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/CN2015/086261
Other languages
English (en)
French (fr)
Inventor
张亚博
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Huawei Technologies Co Ltd
Original Assignee
Huawei Technologies Co Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Huawei Technologies Co Ltd filed Critical Huawei Technologies Co Ltd
Priority to PCT/CN2015/086261 priority Critical patent/WO2016082580A1/zh
Priority to EP15863894.0A priority patent/EP3166268B1/en
Publication of WO2016082580A1 publication Critical patent/WO2016082580A1/zh
Priority to US15/607,104 priority patent/US10404584B2/en
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Images

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/58—Association of routers
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/48—Routing tree calculation
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L49/00—Packet switching elements
    • H04L49/50—Overload detection or protection within a single switching element
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/12—Shortest path evaluation
    • H04L45/121—Shortest path evaluation by minimising delays
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/24—Multipath
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/74—Address processing for routing
    • H04L45/745—Address table lookup; Address filtering
    • H04L45/7453—Address table lookup; Address filtering using hashing
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/10—Flow control; Congestion control
    • H04L47/12—Avoiding congestion; Recovering from congestion
    • H04L47/125—Avoiding congestion; Recovering from congestion by balancing the load, e.g. traffic engineering
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L61/00—Network arrangements, protocols or services for addressing or naming
    • H04L61/09—Mapping addresses
    • H04L61/10—Mapping addresses of different types
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L67/00—Network arrangements or protocols for supporting network services or applications
    • H04L67/01—Protocols
    • H04L67/10—Protocols in which an application is distributed across nodes in the network
    • H04L67/1001—Protocols in which an application is distributed across nodes in the network for accessing one among a plurality of replicated servers

Definitions

  • the embodiments of the present invention relate to communication technologies, and in particular, to a load balancing method and a routing device.
  • a routing device forwards a packet
  • the routing device performs load balancing based on the packet characteristics, and the traffic is evenly hashed to all outgoing interfaces to ensure that the routing device bandwidth resources are obtained.
  • the load balancing is divided into two types: packet-by-packet and flow-by-flow.
  • Packet-based load balancing causes packets of one service flow to be hashed to different interfaces. The physical parameters of different interfaces may cause packets of the service flow. Out of order, so the packet-by-package load sharing is less used on the live network.
  • the traffic-based load balancing requires the routing device to perform the hash (HASH) routing based on the packet characteristics to implement load balancing and ensure that the traffic of the same packet features the same outgoing interface.
  • HASH hash
  • FIG. 1 is a schematic diagram of a network structure.
  • traffic is HASH-routed on the A device, the A device sends traffic to the B device.
  • the B device uses the same HASH algorithm as the A device to perform traffic.
  • HASH routing the routing result of the B device is the same as the routing result of the A device, causing the problem of uneven load sharing of the B device.
  • the disturbance factor is used to interfere with the HASH routing result to reduce the coupling of load sharing results between different routing devices. degree.
  • the number of ports of the routing device is limited, even if the perturbation factors of the physical devices are different, the routing device performs according to the disturbance factor.
  • the coupling degree of the load sharing result obtained by the HASH operation may also be high. Especially when the network size is large enough, there will always be a situation in which the routing device has uneven load sharing, which affects the network running quality.
  • the embodiment of the present invention provides a load balancing method and a routing device to solve the problem of uneven multi-level load sharing between routing devices, so that multi-level load sharing is uniform.
  • a first aspect of the present invention provides a load sharing method, including:
  • the routing device obtains the load sharing information of the downstream routing device that has the load sharing relationship, and the load sharing information includes the load sharing algorithm and the disturbance factor of the downstream routing device having the load sharing relationship.
  • the routing device determines the first load sharing information of the routing device according to the load sharing information of the downstream routing device that has the load sharing relationship, where the first load sharing information includes the first load sharing algorithm of the routing device. And a first perturbation factor, wherein the first perturbation factor is different from a perturbation factor of all downstream routing devices having a load sharing relationship;
  • the routing device sends the first load sharing information to the upstream routing device having the load sharing relationship, and the load sharing information of all the downstream routing devices having the load sharing relationship;
  • the routing device uses the first load sharing information to determine a forwarding path of the data packet.
  • each of the load sharing information includes a lock status identifier, where the lock status identifier is used to indicate whether the corresponding load sharing information is Locked;
  • Determining, by the routing device, the first load sharing information of the routing device according to the load balancing information of the downstream routing device that has the load sharing relationship including:
  • the routing device determines whether the lock state identifiers of the load balancing information of the downstream routing devices that have the load sharing relationship are all locked states;
  • the routing device sets the downstream routing according to all the load sharing relationships.
  • the load balancing information determines the first load sharing information
  • the routing device sends the first load sharing information to an upstream routing device that has a load sharing relationship, including:
  • the routing device sets the lock status identifier of the first load sharing information to be locked, and sends the first load sharing information to the upstream routing device that has the load sharing relationship.
  • the routing device acquires all the downstream routes that have a load sharing relationship Before the load sharing information of the device, the method further includes:
  • the routing device obtains load balancing information of all the downstream routing devices that have a load sharing relationship.
  • the routing device shares the second load
  • the information is sent to the upstream routing device with the load sharing relationship, and the second load sharing information includes a second load sharing algorithm and a second interference factor of the routing device.
  • the routing device obtains the load sharing information of all the downstream routing devices that have a load sharing relationship, including:
  • the routing device sends a load sharing request message to an adjacent downstream routing device
  • the routing device receives the load sharing response returned by the neighboring downstream routing device, where the load sharing response includes load balancing information of all the downstream devices having the load sharing relationship.
  • a second aspect of the present invention provides a routing device, including:
  • the obtaining module is configured to obtain load sharing information of all the routing devices of the routing device that have a load sharing relationship, where the load sharing information includes a load sharing algorithm and a disturbance factor of the downstream routing device having the load sharing relationship;
  • a first determining module configured to determine first load sharing information of the routing device according to load balancing information of all the downstream routing devices that have a load sharing relationship, where the first load sharing information includes the first a load sharing algorithm and a first disturbance factor, wherein the first disturbance factor is different from a disturbance factor of the downstream routing device having the load sharing relationship;
  • a sending module configured to send, to the upstream routing device that has a load sharing relationship, the first load sharing information, and load balancing information of all the downstream routing devices that have a load sharing relationship;
  • a second determining module configured to determine, by using the first load sharing information, a forwarding path of the data packet when the routing device receives the data packet.
  • each of the load sharing information includes a lock status identifier, where the lock status identifier is used to indicate whether the corresponding load sharing information is Locked;
  • the first determining module is specifically configured to: determine whether the lock state identifiers of the load balancing information of the downstream routing devices that have the load sharing relationship are all locked states;
  • the sending module is specifically configured to: set the lock state identifier of the first load sharing information to be locked, and send the first load sharing information to the upstream routing device that has a load sharing relationship.
  • the acquiring module is further configured to:
  • the routing device is a non-leaf node, the load sharing information of all the downstream routing devices with the load sharing relationship is obtained.
  • the sending module is further configured to: send the second load sharing information to the upstream routing device that has a load sharing relationship, where the second load sharing information includes a second load sharing algorithm and a second interference factor of the routing device.
  • the acquiring module is specifically configured to:
  • all routing devices with load sharing relationships in the network determine their own load sharing information through negotiation, so as to avoid the same interference factor of other routing devices.
  • each routing device having a load sharing relationship obtains load balancing information of all downstream routing devices with load sharing relationships, and determines all of its own load sharing information according to its own downstream routing device with load sharing relationship.
  • the load sharing information determines its own load sharing information, so that its own perturbation factor and the disturbance factor of the downstream routing device with load sharing relationship, so that the load sharing information between all the routing devices with load sharing relationship in the network is coupled. The degree is reduced, so that the load sharing at all levels is uniform.
  • Figure 1 is a schematic diagram of a network structure
  • FIG. 2 is a flowchart of a load sharing method according to Embodiment 1 of the present invention.
  • FIG. 3 is a schematic diagram of another network structure
  • FIG. 4 is a schematic structural diagram of a routing device according to Embodiment 2 of the present invention.
  • FIG. 2 is a flowchart of a load sharing method according to Embodiment 1 of the present invention. As shown in FIG. 3, the method in this embodiment may include:
  • the routing device obtains load balancing information of all downstream routing devices that have a load sharing relationship, where the load sharing information includes a load sharing algorithm and a disturbance factor of all downstream routing devices with load sharing relationships.
  • FIG. 3 is a schematic diagram of another network structure.
  • routing devices A, B, C, D, E, F has a load-sharing relationship.
  • the load-sharing relationship of the routing device refers to the interface where the routing device has a load-sharing relationship.
  • the load-balanced interface is, for example, an outbound interface of an equal-cost route or an interface bundled into a trunk.
  • routing devices A and F you need to obtain the load balancing information of routing devices B, C, and E.
  • routing device B you need to obtain the load balancing information of routing device E.
  • routing devices C and E there is no Load balancing information of the downstream routing device with load balancing.
  • the routing device obtains the load sharing information of all the downstream routing devices that have the load balancing relationship.
  • the routing device sends a load balancing request message to the neighboring downstream routing device.
  • the adjacent downstream routing device is configured according to the load sharing. Request to return a load sharing response to the routing device.
  • the routing device receives the load sharing response returned by the neighboring downstream device, where the load sharing response includes load balancing information of all the downstream routing devices having the load sharing relationship, where the load sharing information includes: a load sharing algorithm used by the routing device and Disturbance factor.
  • All the routing devices in the network send a load balancing request message to the neighboring downstream routing device.
  • the load balancing request is used to obtain the load balancing information of the downstream routing device with the load sharing relationship.
  • the time-to-live of the load sharing request message The value of the Time-To-Live (TTL) value is 1. Therefore, the adjacent downstream routing device does not forward the load sharing request after receiving the load sharing request message sent by the upstream routing device.
  • the neighboring downstream routing device determines whether the load balancing interface exists. If yes, the adjacent downstream routing device collects the load balancing information of the neighboring routing device and the obtained neighboring downstream device.
  • the load balancing information of the downstream routing device with the load sharing relationship is carried in the load sharing request response and returned to the upstream routing device. If the adjacent downstream routing device does not have a load balancing interface, the adjacent downstream routing device does not return a load sharing response to the upstream routing device. For example, after the routing device B sends the load sharing request message to the routing device D and the routing device E, the routing device E has a load sharing interface. Therefore, the routing device E returns a load sharing response to the routing device B, and the routing device D does not. It has a load sharing interface. Therefore, routing device D does not reply to the load sharing response.
  • Each of the routing devices with load balancing relationships involved in the multi-level load balancing path generates a tree table, which stores load balancing information of all downstream routing devices with load balancing relationships.
  • the load sharing request message further carries the load balancing information of the routing device, where the load sharing information carried by the load sharing information is the load sharing information that is currently being used by itself, and is not the final determined load according to the method of the embodiment of the present invention.
  • the device can carry the load sharing information of the routing device in the OPTION option field in the Internet Protocol (IP) header.
  • IP Internet Protocol
  • the IP option can be carried by the type length value (Type-Length-value, TLV for short).
  • the load sharing type, load sharing algorithm, and disturbance factor of the routing device is carried by the load sharing information that is currently being used by itself, and is not the final determined load according to the method of the embodiment of the present invention.
  • the device can carry the load sharing information of the routing device in the OPTION option field in the Internet Protocol (IP) header.
  • IP option can be carried by the type length value (Type-Length-value, TLV for short).
  • Type-Length-value Type-Length-value
  • the load sharing message may use a special Internet Control Message Protocol (ICMP) message, or a special field of the Interior Gateway Protocol (IGP) protocol, or a multiplexing border gateway protocol (
  • ICMP Internet Control Message Protocol
  • IGP Interior Gateway Protocol
  • BGP Border Gateway Protocol
  • BPDU Bridge Protocol Data Unit
  • the method of the present embodiment introduces a locking principle to avoid frequent changes of the load balancing information of the routing device.
  • the purpose of the locking principle is to ensure that the load sharing information is determined from the leaf node and gradually spread to the root node to avoid non-leaf nodes.
  • the load sharing information is repeatedly changed.
  • the locking principle ensures that the routing device is restarted or the new routing device does not cause large-area load sharing information changes in the network.
  • the leaf node is a routing device without a downstream routing device.
  • the non-leaf node is a routing device with a downstream routing device.
  • a state lock identifier is set for the load sharing information of each routing device, and the lock state identifier is used to indicate whether the corresponding load sharing information is locked, and the load sharing information is locked, meaning that the load sharing information is stable.
  • Status When each routing device sends its own load balancing information to the upstream routing device, it sets the value of the state locking identifier according to the actual situation.
  • the routing device determines the first load sharing information of the routing device according to the load balancing information of the downstream routing device that has the load sharing relationship, where the first load sharing information includes the first load sharing algorithm and the first interference of the routing device. a factor, wherein the first perturbation factor is different from a perturbation factor of all downstream routing devices having a load sharing relationship.
  • the routing device determines whether the lock state identifiers of the load balancing information of all the downstream routing devices having the load sharing relationship are all locked. If yes, the routing device determines the first load sharing information according to the load sharing information of all the downstream routing devices. . The routing device selects the best hash load sharing algorithm and/or selects the best hashing disturbance factor when determining the first load sharing information, so as to ensure that the load sharing at all levels in the network can be uniform. Therefore, the determined first perturbation factor is different from the perturbation factor of all downstream routing devices having a load sharing relationship.
  • the first load sharing algorithm may be the same as the load sharing algorithm of all downstream routing devices having a load sharing relationship. In this embodiment, each routing device determines its own perturbation factor to be different from the interference factor of the downstream routing device with load sharing relationship. Therefore, the coupling of the perturbation factors of the routing devices at all levels is reduced.
  • Each routing device sets the value of the state-locked identifier of the load balancing information when it sends its own load-sharing information to its own upstream device.
  • the upstream routing device only determines the load balancing of all downstream routing devices with load balancing.
  • the first load sharing information is determined according to the load sharing information of all the downstream routing devices that have the load sharing relationship. If some or all of the lock status information of the load balancing information of the downstream device of the routing device is not locked, the routing device does not determine the first load sharing information, but the second load.
  • the load sharing information of the downstream routing device of the routing device and the load balancing device of the routing device is sent to the upstream routing device.
  • the second load sharing information is the load sharing information currently used by the routing device, and may be the load sharing information determined after the last load sharing information adjustment, or may be the default load sharing information.
  • the routing device sends the first load sharing information When the upstream routing device is configured, the value of the lock state identifier of the first load sharing information is set to the locked state, but the routing device sends the second load sharing information to the upstream routing device, and the second load sharing information is used.
  • the value of the lock status ID is set to the unlock status.
  • the routing device sends the first load sharing information to the adjacent upstream routing device, and the load sharing information of the downstream routing device that has the load sharing relationship.
  • the routing device after determining the first load sharing information, sets the locking status identifier of the first load sharing information to a locked state, and then sends the first load sharing information to the adjacent upstream routing device, and the all Load balancing information of the downstream routing device with load balancing.
  • the routing device sends the first load sharing information to the neighboring upstream routing device, and the load balancing information of the downstream routing device having the load sharing relationship is used to load the first load sharing information and all the load sharing relationships.
  • the load balancing information of the downstream routing device is finally sent to all the upstream routing devices with the load balancing relationship, so that the upstream routing device with the load sharing relationship loads the load based on the first load information and the downstream routing devices with the load sharing relationship.
  • the information determines its own load sharing information.
  • all the routing devices in the network determine their own load sharing information through a negotiation method, and the determination of the load sharing information is spread from the leaf node to the root node, and each routing device having the load sharing relationship determines its own
  • the load balancing information is used, the load balancing information of the downstream routing device with the load balancing relationship is determined.
  • each routing device considers the load sharing of the downstream routing device. Information, try to choose the best load-sharing algorithm and the disturbance factor, so that the coupling between the load-sharing algorithm and the disturbance factor between all the routing devices with load-sharing relationships in the network is reduced, so that load sharing at all levels is uniform.
  • the final load sharing information of the routing devices A, B, C, E, and F having the load sharing relationship in FIG. 3 is: the load sharing algorithm of the routing device A is algorithm 1, the disturbance factor is n, and the route is The load balancing algorithm of device B is algorithm 5, the disturbance factor is Y, the load sharing algorithm of routing device C is algorithm 2, the disturbance factor is X, the load sharing algorithm of routing device E is algorithm 2, the disturbance factor is m, and the routing device F The load sharing algorithm is algorithm 2, and the disturbance factor is z. It can be seen that, by using the method in this embodiment, the routing factors of all the routing devices with the load sharing algorithm in the network are different, so that each routing device with the load sharing algorithm performs hash routing according to the respective load sharing information. , can reduce the coupling degree of load sharing results.
  • the routing device uses the first load sharing information to determine a forwarding path of the data packet.
  • the routing device selects the data packet according to the load balancing algorithm and the disturbance factor according to the first load sharing information, to determine the data packet from the data packet. Which interface of the routing device has a load sharing relationship is sent out. Specifically, the routing device performs two hash operations on the data packet. When the hash operation is performed, the routing device performs an exclusive OR operation on the source IP address and the destination IP address of the data packet to obtain the first XOR result. Then, the routing device multiplies the perturbation factor by the physical outbound interface matrix of the routing device, and the physical outbound interface matrix of the routing device is composed of all physical outbound interfaces of the routing device that have a load sharing relationship.
  • the matrix obtained by multiplying is ranked, and the first XOR result is XORed with the rank of the multiplied matrix to obtain a second XOR result, and the result obtained by the second XOR result is determined.
  • the outgoing interface of the data packet when performing the first hashing operation, the source IP address and the destination IP address of the data packet may be respectively inverted, and then the inverted source IP address and the inverted destination IP address are respectively performed.
  • the address is XORed.
  • the perturbation factor in the embodiment of the present invention is a random number, and the random number is generated by the routing device.
  • all the routing devices with the load sharing relationship in the network determine their own load sharing information through negotiation to avoid the same interference factor of the other routing devices.
  • each routing device having a load sharing relationship obtains load balancing information of all downstream routing devices with load sharing relationships, and determines all of its own load sharing information according to its own downstream routing device with load sharing relationship.
  • the load sharing information determines its own load sharing information, so that its own perturbation factor and the disturbance factor of the downstream routing device with load sharing relationship, so that the load sharing information between all the routing devices with load sharing relationship in the network is coupled. The degree is reduced, so that the load sharing at all levels is uniform.
  • the routing device determines whether it is a leaf node; if the routing device is a non-leaf node, the route The device obtains load sharing information of all the downstream routing devices that have the load sharing relationship. If the routing device is a leaf node, the routing device sends the second load balancing algorithm to all upstream routing devices with load sharing relationships.
  • the routing device in this embodiment includes: an obtaining module 11, a first determining module 12, and a sending module 13 And a second determining module 14.
  • the obtaining module 11 is configured to obtain load sharing information of all the routing devices of the routing device that have a load balancing relationship, and the load sharing information includes a load balancing algorithm of the downstream routing device that has the load sharing relationship. Disturbance factor
  • the first determining module 12 is configured to determine first load sharing information of the routing device according to load balancing information of all the downstream routing devices that have a load sharing relationship, where the first load sharing information includes the routing device a load sharing algorithm and a first perturbation factor, wherein the first perturbation factor is different from a perturbation factor of all downstream routing devices having a load sharing relationship;
  • the sending module 13 is configured to send the first load sharing information to the upstream routing device that has the load sharing relationship, and the load sharing information of all the downstream routing devices that have the load sharing relationship;
  • the second determining module 14 is configured to determine, when the routing device receives the data packet, the forwarding path of the data packet by using the first load sharing information.
  • each of the load sharing information includes a lock status identifier, where the lock status identifier is used to indicate whether the corresponding load sharing information is locked.
  • the first determining module 12 is specifically configured to: determine all Whether the lock state identifier of the load balancing information of the downstream routing device having the load sharing relationship is the locked state; if yes, determining the first load sharing information according to the load sharing information of all the downstream routing devices having the load sharing relationship.
  • the sending module 13 is configured to: set the lock state identifier of the first load sharing information to be locked, and send the first load sharing information to the upstream routing device that has a load sharing relationship.
  • the obtaining module 11 is further configured to: determine, before the load balancing information of the downstream routing device that has the load sharing relationship, whether the routing device is a leaf node; if the routing device is a non-leaf The node obtains load sharing information of all the downstream routing devices that have the load sharing relationship. If the routing device is a leaf node, the sending module 13 is further configured to: send the second load sharing information to the upstream routing device that has a load sharing relationship, where the second load sharing information includes the routing device The second load sharing algorithm and the second disturbance factor.
  • the acquiring module 11 is specifically configured to: send a load sharing request message to an adjacent downstream routing device, and receive a load sharing response returned by the adjacent downstream routing device, where the load sharing response includes all Load sharing information of downstream devices with load balancing relationships.
  • the routing device of this embodiment may be used to implement the technical solution of the first embodiment, and the specific implementation manners and technical effects are similar, and details are not described herein again.
  • the aforementioned program can be stored in a computer readable storage medium.
  • the program when executed, performs the steps including the foregoing method embodiments; and the foregoing storage medium includes various media that can store program codes, such as a ROM, a RAM, a magnetic disk, or an optical disk.

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

一种负载分担的方法和路由设备，网络中所有具有负载分担关系的路由设备通过协商的方法确定自己的负载分担信息，以避免自己的负载分担信息中的扰动因子与其他路由设备的扰动因子相同。具体地，每个具有负载分担关系的路由设备，通过获取所有具有负载分担关系的下游路由设备的负载分担信息，在确定自己的负载分担信息时，根据自己的所有具有负载分担关系的下游路由设备的负载分担信息确定自己的负载分担信息，使得自己的扰动因子与所有具有负载分担关系的下游路由设备的扰动因子，从而使得网络中所有具有负载分担关系的路由设备之间的负载分担信息的耦合度降低，使得各级负载分担均匀。

Description

负载分担的方法和路由设备
本申请要求于2014年11月28日提交中国专利局、申请号为201410709183.4、发明名称为“负载分担的方法和路由设备”的中国专利申请的优先权，其全部内容通过引用结合在本申请中。
技术领域
本发明实施例涉及通信技术，尤其涉及一种负载分担的方法和路由设备。
背景技术
路由设备在转发报文时，如果转发表项存在多个等价的出接口，则路由设备会根据报文特征进行负载分担，将流量平均散列到所有出接口上，保证路由设备带宽资源得到充分利用。负载分担分为逐包和逐流两种，逐包负载分担会导致一条业务流的报文被散列到不同的接口上，由于不同的接口的物理参数不同，可能导致该业务流的报文乱序，所以逐包负载分担现网使用的较少。逐流负载分担需要路由设备根据报文特征进行哈希(HASH)选路，实现负载分担的同时，确保相同报文特征的流量走相同的出接口。
如果网络中存在多级路由设备，每一级路由设备都需要对流量进行HASH选路，且每一级路由设备采用的HASH算法相同，则可能存在多级负载分担不均的问题，当多级负载分担不均时，有可能导致报文丢失。如图1所示，图1为一种网络结构的示意图，当流量在A设备上进行HASH选路时，A设备将流量发送给B设备，B设备使用与A设备相同的HASH算法对流量进行HASH选路，B设备的选路结果与A设备的选路结果相同，导致B设备出现负载分担不均的问题。
对于多级负载分担不均的问题，一般引入多种HASH算法，或者在HASH选路的过程中，使用扰动因子对HASH选路结果进行干扰，以降低不同路由设备之间的负载分担结果的耦合度。但是，由于路由设备的端口数量有限，即使各物理设备的扰动因子不同，路由设备根据扰动因子进行 HASH运算得到的负载分担的结果的耦合度也可能很高，尤其是当网络规模足够大时，总会有路由设备存在多级负载分担不均的情况，影响网络运行质量。
发明内容
本发明实施例提供一种负载分担的方法和路由设备，以解决路由设备之间的多级负载分担不均的问题，使得多级负载分担均匀。
本发明第一方面提供一种负载分担的方法，包括：
路由设备获取所有具有负载分担关系的下游路由设备的负载分担信息，所述负载分担信息包括所述所有具有负载分担关系的下游路由设备的负载分担算法和扰动因子；
所述路由设备根据所述所有具有负载分担关系的下游路由设备的负载分担信息确定所述路由设备的第一负载分担信息，所述第一负载分担信息包括所述路由设备的第一负载分担算法和第一扰动因子，其中，所述第一扰动因子与所述所有具有负载分担关系的下游路由设备的扰动因子不同；
所述路由设备向具有负载分担关系的上游路由设备发送所述第一负载分担信息，以及所述所有具有负载分担关系的下游路由设备的负载分担信息；
当所述路由设备接收到数据报文时，所述路由设备使用所述第一负载分担信息确定所述数据报文的转发路径。
结合本发明第一方面，在本发明第一方面的第一种可能的实现方式中，所述每个负载分担信息中包括锁定状态标识，所述锁定状态标识用于表示对应的负载分担信息是否被锁定；
所述路由设备根据所述所有具有负载分担关系的下游路由设备的负载分担信息确定所述路由设备的第一负载分担信息，包括：
所述路由设备判断所述所有具有负载分担关系的下游路由设备的负载分担信息的锁定状态标识是否均为锁定状态；
若是，则所述路由设备根据所述所有具有负载分担关系的下游路由设 备的负载分担信息确定所述第一负载分担信息；
所述路由设备向具有负载分担关系的上游路由设备发送所述第一负载分担信息，包括：
所述路由设备将所述第一负载分担信息的锁定状态标识置为锁定，向所述具有负载分担关系的上游路由设备发送所述第一负载分担信息。
结合本发明第一方面以及本发明第一方面的第一种可能的实现方式，在本发明第一方面的第二种可能的实现方式中，所述路由设备获取所有具有负载分担关系的下游路由设备的负载分担信息之前，所述方法还包括：
所述路由设备确定自己是否为叶子节点；
若所述路由设备为非叶子节点，则所述路由设备获取所述所有具有负载分担关系的下游路由设备的负载分担信息。
结合本发明第一方面的第二种可能的实现方式，在本发明第一方面的第三种可能的实现方式中，若所述路由设备为叶子节点，则所述路由设备将第二负载分担信息发送给所述具有负载分担关系的上游路由设备，所述第二负载分担信息包括所述路由设备的第二负载分担算法和第二扰动因子。
结合本发明第一方面，在本发明第一方面的第四种可能的实现方式中，所述路由设备获取所有具有负载分担关系的下游路由设备的负载分担信息，包括：
所述路由设备向相邻下游路由设备发送负载分担请求消息；
所述路由设备接收所述相邻下游路由设备返回的负载分担响应，所述负载分担响应中包括所述所有具有负载分担关系的下游设备的负载分担信息。
本发明第二方面提供一种路由设备，包括：
获取模块，用于获取所述路由设备的所有具有负载分担关系的下游路由设备的负载分担信息，所述负载分担信息包括所述所有具有负载分担关系的下游路由设备的负载分担算法和扰动因子；
第一确定模块，用于根据所述所有具有负载分担关系的下游路由设备的负载分担信息确定所述路由设备的第一负载分担信息，所述第一负载分担信息包括所述路由设备的第一负载分担算法和第一扰动因子，其中，所述第一扰动因子与所述所有具有负载分担关系的下游路由设备的扰动因子不同；
发送模块，用于向具有负载分担关系的上游路由设备发送所述第一负载分担信息，以及所述所有具有负载分担关系的下游路由设备的负载分担信息；
第二确定模块，用于当所述路由设备接收到数据报文时，使用所述第一负载分担信息确定所述数据报文的转发路径。
结合本发明第二方面，在本发明第二方面的第一种可能的实现方式中，所述每个负载分担信息中包括锁定状态标识，所述锁定状态标识用于表示对应的负载分担信息是否被锁定；
所述第一确定模块具体用于：判断所述所有具有负载分担关系的下游路由设备的负载分担信息的锁定状态标识是否均为锁定状态；
若是，则根据所述所有具有负载分担关系的下游路由设备的负载分担信息确定所述第一负载分担信息；
所述发送模块具体用于：将所述第一负载分担信息的锁定状态标识置为锁定，向所述具有负载分担关系的上游路由设备发送所述第一负载分担信息。
结合本发明第二方面以及本发明第二方面的第一种可能的实现方式中，在本发明第二方面的第二种可能的实现方式中，所述获取模块还用于：
在获取所述所有具有负载分担关系的下游路由设备的负载分担信息之前，确定所述路由设备是否为叶子节点；
若所述路由设备为非叶子节点，则获取所述所有具有负载分担关系的下游路由设备的负载分担信息。
结合本发明第二方面的第二种可能的实现方式中，在本发明第二方面的第三种可能的实现方式中，若所述路由设备为叶子节点，则所述发送模 块还用于：将第二负载分担信息发送给所述具有负载分担关系的上游路由设备，所述第二负载分担信息包括所述路由设备的第二负载分担算法和第二扰动因子。
结合本发明第二方面，在本发明第二方面的第四种可能的实现方式中，所述获取模块具体用于：
向相邻下游路由设备发送负载分担请求消息；
接收所述相邻下游路由设备返回的负载分担响应，所述负载分担响应中包括所述所有具有负载分担关系的下游设备的负载分担信息。
本发明实施例提供的负载分担的方法和路由设备，网络中所有具有负载分担关系的路由设备通过协商的方法确定自己的负载分担信息，以避免自己的扰动因子与其他路由设备的扰动因子相同。具体地，每个具有负载分担关系的路由设备，通过获取所有具有负载分担关系的下游路由设备的负载分担信息，在确定自己的负载分担信息时，根据自己的所有具有负载分担关系的下游路由设备的负载分担信息确定自己的负载分担信息，使得自己的扰动因子与所有具有负载分担关系的下游路由设备的扰动因子，从而使得网络中所有具有负载分担关系的路由设备之间的负载分担信息的耦合度降低，使得各级负载分担均匀。
附图说明
为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作一简单地介绍，显而易见地，下面描述中的附图是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动性的前提下，还可以根据这些附图获得其他的附图。
图1为一种网络结构的示意图；
图2为本发明实施例一提供的负载分担方法的流程图；
图3为另一种网络结构的示意图；
图4为本发明实施例二提供的路由设备的结构示意图。
具体实施方式
为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
图2为本发明实施例一提供的负载分担方法的流程图，如图3所示，本实施例的方法可以包括：
S101、路由设备获取所有具有负载分担关系的下游路由设备的负载分担信息，该负载分担信息包括所有具有负载分担关系的下游路由设备的负载分担算法和扰动因子。
以图3所示例子为例，图3为另一种网络结构的示意图，网络中共有11台路由设备，路由设备被划分了多级，其中，路由设备A、B、C、D、E、F具有负载分担关系，这里，路由设备具有负载分担关系是指路由设备存在负载分担关系的接口，负载关系分担接口例如为等价路由的出接口或者捆绑成trunk的接口等。对于路由设备A和F来说，需要获取路由设备B、C、E的负载分担信息，对于路由设备B来说，需要获取路由设备E的负载分担信息，对于路由设备C和E来说，没有具有负载分担关系的下游路由设备的负载分担信息。
本实施例中，路由设备获取所有具有负载分担关系的下游路由设备的负载分担信息，具体可以为：路由设备向相邻下游路由设备发送负载分担请求消息；该相邻的下游路由设备根据负载分担请求向该路由设备返回负载分担响应。该路由设备接收该相邻下游设备返回的负载分担响应，该负载分担响应中包括所有具有负载分担关系的下游路由设备的负载分担信息，其中，负载分担信息包括：路由设备采用的负载分担算法以及扰动因子。
网络中的所有路由设备在每个探测周期都会向自己相邻的下游路由设备发送一次负载分担请求消息，该负载分担请求用于获取具有负载分担关系的下游路由设备的负载分担信息。该负载分担请求消息的生存时间 (Time-To-Live，简称TTL)值为1，因此，相邻的下游路由设备在接收到上游路由设备发送的负载分担请求消息后不会将该负载分担请求转发出去。相邻的下游路由设备在接收到负载分担请求消息后，判断自己是否存在负载分担接口，若存在，则相邻的下游路由设备将自己的负载分担信息，以及获取到的该相邻下游设备的具有负载分担关系的下游路由设备的负载分担信息携带在负载分担请求响应中返回给上游路由设备。若相邻的下游路由设备不存在负载分担接口，则该相邻的下游路由设备不向上游路由设备返回负载分担响应。例如，图3中路由设备B在向路由设备D和路由设备E发送负载分担请求消息后，路由设备E具有负载分担接口，因此，路由设备E向路由设备B返回负载分担响应，路由设备D不具有负载分担接口，因此，路由设备D不回复负载分担响应。最终多级负载分担路径中涉及的每台具有负载分担关系的路由设备都会生成一个树表，该树表中保存了自己的所有具有负载分担关系的下游路由设备的负载分担信息。
可选地，该负载分担请求消息中还携带该路由设备自己的负载分担信息，这里携带的负载分担信息为自己当前正在使用的负载分担信息，并不是根据本发明实施例的方法最终确定的负载分担信息。具体可以在网络互联协议(简称Internet Protocol，简称IP)头中携带OPTION选项字段中该路由设备的负载分担信息，IP选项中可通过类型长度值(Type-Length-value，简称TLV)的方式携带该路由设备的负载分担类型、负载分担算法以及扰动因子。该负载分担消息可以使用特殊的互联网控制报文协议(Internet Control Message Protocol，简称ICMP)报文，或者复用内部网关协议(Interior Gateway Protocol，简称IGP)协议特殊字段，或者复用边界网关协议(Border Gateway Protocol，简称BGP)协议的特殊字段，或者使用特殊的网桥协议数据单元(Bridge Protocol Data Unit，简称BPDU)报文等，本发明并不对此进行限制。
本实施例的方法，在具体实现时引入了锁定原则避免路由设备的负载分担信息频繁变化，锁定原则的目的是确保负载分担信息的确定从叶子节点开始，逐步扩散到根节点，避免非叶子节点的负载分担信息反复变动。并且锁定原则可以确保路由设备重启或新增路由设备不会导致网络中出现大面积的负载分担信息变化。这里叶子节点为没有下游路由设备的路由设 备，非叶子节点为具有下游路由设备的路由设备。本实施例中，为每个路由设备的负载分担信息设定了一个状态锁定标识，该锁定状态标识用于表示对应的负载分担信息是否被锁定，负载分担信息被锁定意味着负载分担信息处于稳定状态，每个路由设备在向上游路由设备发送自己的负载分担信息时，会根据实际情况设定状态锁定标识的值。
S102、该路由设备根据所有具有负载分担关系的下游路由设备的负载分担信息确定该路由设备的第一负载分担信息，该第一负载分担信息包括该路由设备的第一负载分担算法和第一扰动因子，其中，该第一扰动因子与所有具有负载分担关系的下游路由设备的扰动因子不同。
具体地，该路由设备判断所有具有负载分担关系的下游路由设备的负载分担信息的锁定状态标识是否均为锁定，若是，则该路由设备根据所有下游路由设备的负载分担信息确定第一负载分担信息。该路由设备在确定第一负载分担信息时选择散列性最好的负载分担算法和/或选择散列性最好的扰动因子，以便于保证网络中各级负载分担能够均匀。因此，确定的该第一扰动因子与所有具有负载分担关系的下游路由设备的扰动因子不同，但是，该第一负载分担算法可以与所有具有负载分担关系的下游路由设备的负载分担算法相同。本实施例中，每个路由设备确定的自己的扰动因子都与其具有负载分担关系的下游路由设备的扰动因子不同，因此，降低了各级路由设备的扰动因子的耦合性。
每个路由设备在向自己的上游设备发送自己的负载分担信息时都会设定负载分担信息的状态锁定标识的值，上游路由设备只有在确定自己的所有具有负载分担关系的下游路由设备的负载分担信息的状态锁定标记都为锁定状态时，才会根据该所有具有负载分担关系的下游路由设备的负载分担信息确定第一负载分担信息。若该路由设备的所有具有负载分担关系的下游设备的负载分担信息中有部分或全部的锁定状态标识为非锁定状态，那么该路由设备不会确定第一负载分担信息，而是将第二负载分担信息以及该路由设备的所有具有负载分担关系的下游路由设备的负载分担信息发送给上游路由设备。这里，第二负载分担信息是该路由设备当前使用的负载分担信息，具体可以是上次负载分担信息调整后确定的负载分担信息，也可以是默认的负载分担信息。该路由设备在将该第一负载分担信息发送 给上游路由设备时，将该第一负载分担信息的锁定状态标识的值设置为锁定状态，但是该路由设备在将该第二负载分担信息发送给上游路由设备时，将该第二负载分担信息的锁定状态标识的值设置为非锁定状态。
S103、该路由设备向相邻上游路由设备发送该第一负载分担信息，以及该所有具有负载分担关系的下游路由设备的负载分担信息。
具体地，该路由设备在确定该第一负载分担信息之后，将该第一负载分担信息的锁定状态标识置为锁定状态，然后向相邻上游路由设备发送该第一负载分担信息，以及该所有具有负载分担关系的下游路由设备的负载分担信息。该路由设备向相邻上游路由设备发送该第一负载分担信息，以及该所有具有负载分担关系的下游路由设备的负载分担信息的目的是，将该第一负载分担信息以及该所有具有负载分担关系的下游路由设备的负载分担信息最终发送给所有具有负载分担关系的上游路由设备，使具有负载分担关系的上游路由设备根据该第一负载信息以及该所有具有负载分担关系的下游路由设备的负载分担信息确定自己的负载分担信息。
本实施例的方法，网络中的所有路由设备通过协商的方法确定自己的负载分担信息，负载分担信息的确定从叶子节点开始扩散至根节点，每个具有负载分担关系的路由设备在确定自己的负载分担信息时，都会根据自己的所有的具有负载分担关系的下游路由设备的负载分担信息确定自己的负载分担信息，在具体确定负载分担信息时，每个路由设备都会考虑下游路由设备的负载分担信息，尽量选择散列性最好的负载分担算法和扰动因子，从而使得网络中所有具有负载分担关系的路由设备之间的负载分担算法和扰动因子的耦合度降低，使得各级负载分担均匀。
如图3所示，图3中具有负载分担关系的路由设备A、B、C、E、F最终的负载分担信息分别为：路由设备A的负载分担算法为算法1，扰动因子为n，路由设备B的负载分担算法为算法5，扰动因子为Y，路由设备C的负载分担算法为算法2，扰动因子为X，路由设备E的负载分担算法为算法2，扰动因子为m，路由设备F的负载分担算法为算法2，扰动因子为z。可知，通过本实施例的方法，网络中的所有具有负载分担算法的路由设备的扰动因子都不相同，这样，各具有负载分担算法的路由设备在根据各自的负载分担信息进行哈希选路时，可以降低负载分担结果的耦合度。
S104、当该路由设备接收到数据报文时，该路由设备使用该第一负载分担信息确定该数据报文的转发路径。
具体地，当该路由设备接收到数据报文时，该路由设备根据该第一负载分担信息中包括负载分担算法和扰动因子对该数据报文进行选路，以确定将该数据报文从该路由设备的哪个具有负载分担关系的接口发送出去。具体的，路由设备通常会对数据报文进行两次哈希运算，第一次哈希运算时路由设备将数据报文的源IP地址和目的IP地址进行异或运算得到第一异或结果，然后，路由设备将扰动因子与该路由设备的物理出接口矩阵进行相乘，该路由设备的物理出接口矩阵由该路由设备的所有具有负载分担关系的物理出接口组成。其次，对相乘得到的矩阵求秩，将第一异或结果与相乘得到的矩阵的秩进行异或，得到第二次异或结果，根据第二次异或结果取模得到的结果确定该数据报文的出接口。可选地，在进行第一次哈希元运算时，可以将数据报文的源IP地址和目的IP地址分别进行取反，然后，对取反后的源IP地址和取反后的目的IP地址进行异或运算。本发明实施例中的扰动因子为随机数，该随机数由路由设备产生。
本实施例，网络中所有具有负载分担关系的路由设备通过协商的方法确定自己的负载分担信息，以避免自己的扰动因子与其他路由设备的扰动因子相同。具体地，每个具有负载分担关系的路由设备，通过获取所有具有负载分担关系的下游路由设备的负载分担信息，在确定自己的负载分担信息时，根据自己的所有具有负载分担关系的下游路由设备的负载分担信息确定自己的负载分担信息，使得自己的扰动因子与所有具有负载分担关系的下游路由设备的扰动因子，从而使得网络中所有具有负载分担关系的路由设备之间的负载分担信息的耦合度降低，使得各级负载分担均匀。
在上述实施例一的基础上，该路由设备获取所有具有负载分担关系的下游路由设备的负载分担信息之前，该路由设备确定自己是否为叶子节点；若该路由设备为非叶子节点，则该路由设备获取所述所有具有负载分担关系的下游路由设备的负载分担信息。若该路由设备为叶子节点，则该路由设备将第二负载分担算法发送给所有具有负载分担关系的上游路由设备。
图4为本发明实施例二提供的路由设备的结构示意图，如图4所示，本实施例的路由设备包括：获取模块11、第一确定模块12、发送模块13 和第二确定模块14。
其中，获取模块11，用于获取所述路由设备的所有具有负载分担关系的下游路由设备的负载分担信息，所述负载分担信息包括所述所有具有负载分担关系的下游路由设备的负载分担算法和扰动因子；
第一确定模块12，用于根据所述所有具有负载分担关系的下游路由设备的负载分担信息确定所述路由设备的第一负载分担信息，所述第一负载分担信息包括所述路由设备的第一负载分担算法和第一扰动因子，其中，所述第一扰动因子与所述所有具有负载分担关系的下游路由设备的扰动因子不同；
发送模块13，用于向具有负载分担关系的上游路由设备发送所述第一负载分担信息，以及所述所有具有负载分担关系的下游路由设备的负载分担信息；
第二确定模块14，用于当所述路由设备接收到数据报文时，使用所述第一负载分担信息确定所述数据报文的转发路径。
可选地，所述每个负载分担信息中包括锁定状态标识，所述锁定状态标识用于表示对应的负载分担信息是否被锁定；则所述第一确定模块12具体用于：判断所述所有具有负载分担关系的下游路由设备的负载分担信息的锁定状态标识是否均为锁定状态；若是，则根据所述所有具有负载分担关系的下游路由设备的负载分担信息确定所述第一负载分担信息。相应地，所述发送模块13具体用于：将所述第一负载分担信息的锁定状态标识置为锁定，向所述具有负载分担关系的上游路由设备发送所述第一负载分担信息。
可选地，所述获取模块11还用于：在获取所述所有具有负载分担关系的下游路由设备的负载分担信息之前，确定所述路由设备是否为叶子节点；若所述路由设备为非叶子节点，则获取所述所有具有负载分担关系的下游路由设备的负载分担信息。若所述路由设备为叶子节点，则所述发送模块13还用于：将第二负载分担信息发送给所述具有负载分担关系的上游路由设备，所述第二负载分担信息包括所述路由设备的第二负载分担算法和第二扰动因子。
本实施例中，所述获取模块11具体用于：向相邻下游路由设备发送负载分担请求消息；接收所述相邻下游路由设备返回的负载分担响应，所述负载分担响应中包括所述所有具有负载分担关系的下游设备的负载分担信息。
本实施例的路由设备，可用于执行实施例一的技术方案，具体实现方式和技术效果类似，这里不再赘述。
本领域普通技术人员可以理解：实现上述各方法实施例的全部或部分步骤可以通过程序指令相关的硬件来完成。前述的程序可以存储于一计算机可读取存储介质中。该程序在执行时，执行包括上述各方法实施例的步骤；而前述的存储介质包括：ROM、RAM、磁碟或者光盘等各种可以存储程序代码的介质。
最后应说明的是：以上各实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述各实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分或者全部技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的范围。

Claims (10)

  1. 一种负载分担的方法，其特征在于，包括：
    路由设备获取所有具有负载分担关系的下游路由设备的负载分担信息，所述负载分担信息包括所述所有具有负载分担关系的下游路由设备的负载分担算法和扰动因子；
    所述路由设备根据所述所有具有负载分担关系的下游路由设备的负载分担信息确定所述路由设备的第一负载分担信息，所述第一负载分担信息包括所述路由设备的第一负载分担算法和第一扰动因子，其中，所述第一扰动因子与所述所有具有负载分担关系的下游路由设备的扰动因子不同；
    所述路由设备向具有负载分担关系的上游路由设备发送所述第一负载分担信息，以及所述所有具有负载分担关系的下游路由设备的负载分担信息；
    当所述路由设备接收到数据报文时，所述路由设备使用所述第一负载分担信息确定所述数据报文的转发路径。
  2. 根据权利要求1所述的方法，其特征在于，所述每个负载分担信息中包括锁定状态标识，所述锁定状态标识用于表示对应的负载分担信息是否被锁定；
    所述路由设备根据所述所有具有负载分担关系的下游路由设备的负载分担信息确定所述路由设备的第一负载分担信息，包括：
    所述路由设备判断所述所有具有负载分担关系的下游路由设备的负载分担信息的锁定状态标识是否均为锁定状态；
    若是，则所述路由设备根据所述所有具有负载分担关系的下游路由设备的负载分担信息确定所述第一负载分担信息；
    所述路由设备向具有负载分担关系的上游路由设备发送所述第一负载分担信息，包括：
    所述路由设备将所述第一负载分担信息的锁定状态标识置为锁定，向所述具有负载分担关系的上游路由设备发送所述第一负载分担信息。
  3. 根据权利要求1或2所述的方法，其特征在于，所述路由设备获取所有具有负载分担关系的下游路由设备的负载分担信息之前，所述方法还包括：
    所述路由设备确定自己是否为叶子节点；
    若所述路由设备为非叶子节点，则所述路由设备获取所述所有具有负载分担关系的下游路由设备的负载分担信息。
  4. 根据权利要求3所述的方法，其特征在于，若所述路由设备为叶子节点，则所述路由设备将第二负载分担信息发送给所述具有负载分担关系的上游路由设备，所述第二负载分担信息包括所述路由设备的第二负载分担算法和第二扰动因子。
  5. 根据权利要求1所述的方法，其特征在于，所述路由设备获取所有具有负载分担关系的下游路由设备的负载分担信息，包括：
    所述路由设备向相邻下游路由设备发送负载分担请求消息；
    所述路由设备接收所述相邻下游路由设备返回的负载分担响应，所述负载分担响应中包括所述所有具有负载分担关系的下游设备的负载分担信息。
  6. 一种路由设备，其特征在于，包括：
    获取模块，用于获取所述路由设备的所有具有负载分担关系的下游路由设备的负载分担信息，所述负载分担信息包括所述所有具有负载分担关系的下游路由设备的负载分担算法和扰动因子；
    第一确定模块，用于根据所述所有具有负载分担关系的下游路由设备的负载分担信息确定所述路由设备的第一负载分担信息，所述第一负载分担信息包括所述路由设备的第一负载分担算法和第一扰动因子，其中，所述第一扰动因子与所述所有具有负载分担关系的下游路由设备的扰动因子不同；
    发送模块，用于向具有负载分担关系的上游路由设备发送所述第一负载分担信息，以及所述所有具有负载分担关系的下游路由设备的负载分担信息；
    第二确定模块，用于当所述路由设备接收到数据报文时，使用所述第一负载分担信息确定所述数据报文的转发路径。
  7. 根据权利要求6所述的路由设备，其特征在于，所述每个负载分担信息中包括锁定状态标识，所述锁定状态标识用于表示对应的负载分担信息是否被锁定；
    所述第一确定模块具体用于：判断所述所有具有负载分担关系的下游 路由设备的负载分担信息的锁定状态标识是否均为锁定状态；
    若是，则根据所述所有具有负载分担关系的下游路由设备的负载分担信息确定所述第一负载分担信息；
    所述发送模块具体用于：将所述第一负载分担信息的锁定状态标识置为锁定，向所述具有负载分担关系的上游路由设备发送所述第一负载分担信息。
  8. 根据权利要求6或7所述的路由设备，其特征在于，所述获取模块还用于：
    在获取所述所有具有负载分担关系的下游路由设备的负载分担信息之前，确定所述路由设备是否为叶子节点；
    若所述路由设备为非叶子节点，则获取所述所有具有负载分担关系的下游路由设备的负载分担信息。
  9. 根据权利要求8所述的路由设备，其特征在于，若所述路由设备为叶子节点，则所述发送模块还用于：将第二负载分担信息发送给所述具有负载分担关系的上游路由设备，所述第二负载分担信息包括所述路由设备的第二负载分担算法和第二扰动因子。
  10. 根据权利要求6所述的路由设备，其特征在于，所述获取模块具体用于：
    向相邻下游路由设备发送负载分担请求消息；
    接收所述相邻下游路由设备返回的负载分担响应，所述负载分担响应中包括所述所有具有负载分担关系的下游设备的负载分担信息。
PCT/CN2015/086261 2014-11-28 2015-08-06 负载分担的方法和路由设备 Ceased WO2016082580A1 (zh)

Priority Applications (3)

Application Number Priority Date Filing Date Title
PCT/CN2015/086261 WO2016082580A1 (zh) 2014-11-28 2015-08-06 负载分担的方法和路由设备
EP15863894.0A EP3166268B1 (en) 2014-11-28 2015-08-06 Load sharing method and routing device
US15/607,104 US10404584B2 (en) 2014-11-28 2017-05-26 Load sharing method and router device

Applications Claiming Priority (3)

Application Number Priority Date Filing Date Title
CN201410709183.4A CN104486236B (zh) 2014-11-28 2014-11-28 负载分担的方法和路由设备
CN201410709183.4 2014-11-28
PCT/CN2015/086261 WO2016082580A1 (zh) 2014-11-28 2015-08-06 负载分担的方法和路由设备

Related Child Applications (1)

Application Number Title Priority Date Filing Date
US15/607,104 Continuation US10404584B2 (en) 2014-11-28 2017-05-26 Load sharing method and router device

Publications (1)

Publication Number Publication Date
WO2016082580A1 true WO2016082580A1 (zh) 2016-06-02

Family

ID=52760741

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/CN2015/086261 Ceased WO2016082580A1 (zh) 2014-11-28 2015-08-06 负载分担的方法和路由设备

Country Status (4)

Country Link
US (1) US10404584B2 (zh)
EP (1) EP3166268B1 (zh)
CN (1) CN104486236B (zh)
WO (1) WO2016082580A1 (zh)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN112039783A (zh) * 2020-08-19 2020-12-04 恒安嘉新（北京）科技股份公司 通信数据输出方法、装置、计算机设备及存储介质

Families Citing this family (10)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN104486236B (zh) * 2014-11-28 2018-02-06 华为技术有限公司 负载分担的方法和路由设备
CN107743094B (zh) * 2016-08-30 2020-05-12 腾讯科技（深圳）有限公司 路由接入方法及路由接入装置
CN108540399B (zh) * 2018-04-26 2022-03-01 新华三技术有限公司 一种负载分担实现方法及装置
CN114726660A (zh) 2018-09-30 2022-07-08 华为技术有限公司 发送、处理报文的方法、入口节点及网络系统
CN109787914B (zh) * 2019-03-28 2022-07-01 新华三技术有限公司 负载分担方法、装置及网络设备
WO2022135217A1 (zh) * 2020-12-21 2022-06-30 华为技术有限公司 负载分担的方法、根节点设备、叶子节点设备以及系统
CN115914234B (zh) * 2021-08-03 2025-04-01 华为技术有限公司 负载均衡的哈希算法信息的确定方法、装置及存储介质
CN115474215B (zh) * 2022-09-06 2023-03-21 广东九博科技股份有限公司 一种基于路由器的组网方法及系统
CN116567726A (zh) * 2023-06-21 2023-08-08 南京熊猫汉达科技有限公司 一种卫星通信系统自适应负载分担系统及方法
CN119070972B (zh) * 2024-07-31 2025-11-04 新华三技术有限公司 一种防止多级跨设备链路聚合连接哈希极化的方法及设备

Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN1921415A (zh) * 2006-09-27 2007-02-28 北京航空航天大学 网络资源负载均衡方法
US20090279431A1 (en) * 2008-05-08 2009-11-12 Pritam Baruah Load Balancing Pseudowire Encapsulated IPTV Channels Over Aggregated Links
CN102143041A (zh) * 2010-07-02 2011-08-03 华为技术有限公司 一种网络流量分担的方法、装置及系统
CN104486236A (zh) * 2014-11-28 2015-04-01 华为技术有限公司 负载分担的方法和路由设备

Family Cites Families (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN100407705C (zh) * 2006-04-12 2008-07-30 华为技术有限公司 一种路由器控制方法和系统
CN100499592C (zh) * 2006-06-05 2009-06-10 华为技术有限公司 通讯网络中对数据流的分流方法和装置
US7903654B2 (en) * 2006-08-22 2011-03-08 Foundry Networks, Llc System and method for ECMP load sharing
CN100531098C (zh) * 2007-03-13 2009-08-19 华为技术有限公司 一种对等网络系统及重叠网间节点的互通方法
US8274980B2 (en) * 2009-02-26 2012-09-25 International Business Machines Corporation Ethernet link aggregation
CN101527685B (zh) * 2009-04-17 2011-07-20 华为技术有限公司 一种报文传输链路的分配方法和装置
US8565239B2 (en) * 2009-07-14 2013-10-22 Broadcom Corporation Node based path selection randomization
US20120287946A1 (en) * 2011-05-13 2012-11-15 Broadcom Corporation Hash-Based Load Balancing with Flow Identifier Remapping
US8743768B2 (en) * 2012-02-27 2014-06-03 Cisco Technology, Inc. On-demand diverse path computation for limited visibility computer networks
US10135914B2 (en) * 2013-04-16 2018-11-20 Amazon Technologies, Inc. Connection publishing in a distributed load balancer
US9621642B2 (en) * 2013-06-17 2017-04-11 Telefonaktiebolaget Lm Ericsson (Publ) Methods of forwarding data packets using transient tables and related load balancers

Patent Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN1921415A (zh) * 2006-09-27 2007-02-28 北京航空航天大学 网络资源负载均衡方法
US20090279431A1 (en) * 2008-05-08 2009-11-12 Pritam Baruah Load Balancing Pseudowire Encapsulated IPTV Channels Over Aggregated Links
CN102143041A (zh) * 2010-07-02 2011-08-03 华为技术有限公司 一种网络流量分担的方法、装置及系统
CN104486236A (zh) * 2014-11-28 2015-04-01 华为技术有限公司 负载分担的方法和路由设备

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
See also references of EP3166268A4 *

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN112039783A (zh) * 2020-08-19 2020-12-04 恒安嘉新（北京）科技股份公司 通信数据输出方法、装置、计算机设备及存储介质

Also Published As

Publication number Publication date
US20170264538A1 (en) 2017-09-14
CN104486236A (zh) 2015-04-01
EP3166268A1 (en) 2017-05-10
US10404584B2 (en) 2019-09-03
EP3166268A4 (en) 2017-11-22
CN104486236B (zh) 2018-02-06
EP3166268B1 (en) 2019-11-20

Similar Documents

Publication Publication Date Title
CN104486236B (zh) 负载分担的方法和路由设备
EP3399703B1 (en) Method for implementing load balancing, apparatus, and network system
US11943136B2 (en) Advanced preferred path route graph features in a network
EP3103230B1 (en) Software defined networking (sdn) specific topology information discovery
US11240063B2 (en) Methods, nodes and computer readable media for tunnel establishment per slice
US9019865B2 (en) Advertising traffic engineering information with the border gateway protocol
US11290394B2 (en) Traffic control in hybrid networks containing both software defined networking domains and non-SDN IP domains
US9288686B2 (en) Topology discovery based on SCTP/X2 snooping
CN105634973B (zh) 基于负载均衡的路由方法和设备
US8667174B2 (en) Method and system for survival of data plane through a total control plane failure
EP3058777B1 (en) Topology discovery based on explicit signaling
EP2817926A1 (en) Delegate forwarding and address resolution in fragmented network
US9398553B2 (en) Technique for improving LDP-IGP synchronization
CN102355421A (zh) 一种lsp网络拥塞处理的方法、装置及系统
CN105282041A (zh) 基于isis的洪泛方法及装置
WO2015154427A1 (zh) Trill isis的路由计算方法及装置
CN104994019B (zh) 一种用于sdn控制器的水平方向接口系统
US10367732B2 (en) Route control for internet exchange point
WO2019209480A1 (en) Resource reservation and maintenance for preferred path routes in a network
Jayaprakash et al. RIP, OSPF, eigrp routing protocols
CN104065578B (zh) 一种基于ason光网络的ip路由处理方法和装置
WO2018095438A1 (zh) 等价多路径ecmp处理方法及装置
Le Implementation of GlobalProtect and Data Centre Interconnect
CN105591940A (zh) 一种trill网络分发树选择方法和trill网络节点

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 15863894

Country of ref document: EP

Kind code of ref document: A1

REEP Request for entry into the european phase

Ref document number: 2015863894

Country of ref document: EP

WWE Wipo information: entry into national phase

Ref document number: 2015863894

Country of ref document: EP

NENP Non-entry into the national phase

Ref country code: DE