CN101299726B - Method for calculating forwarding shortest path - Google Patents
Method for calculating forwarding shortest path Download PDFInfo
- Publication number
- CN101299726B CN101299726B CN2008101291297A CN200810129129A CN101299726B CN 101299726 B CN101299726 B CN 101299726B CN 2008101291297 A CN2008101291297 A CN 2008101291297A CN 200810129129 A CN200810129129 A CN 200810129129A CN 101299726 B CN101299726 B CN 101299726B
- Authority
- CN
- China
- Prior art keywords
- switch
- weight
- current
- matrix
- destination
- 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.)
- Active
Links
Images
Landscapes
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
The invention discloses a method for computing the transmit shortest path, including the steps of: building the weighting array; initializing the built array according to the presupposed port attribute, to obtain the weighting array of the exchanger to the neighbor exchanger; recurrently traversing and computing the weighting array of the current exchanger to the other exchanger; comparing and acquiring the minimum in the weighting array of current exchanger to the other exchanger, to obtain the shortest path from the current exchanger to the other exchanger in the exchanger stacking system. The invention realizes the shortest path transmit in the exchanger stacking system to lift the transmitting efficiency of the message, reduce the wide band occupancy, cause the wide band use more reasonable on the link.
Description
Technical Field
The present invention relates to a technology for calculating a shortest forwarding path, and more particularly, to a method for calculating a shortest forwarding path in a switch stacking system.
Background
When there are many switches in the switch stack system, the selection of the message forwarding path may affect the load and forwarding capability of the entire switch stack system. For example, in a stacking system composed of six switches, daisy-chained switches are sequentially used from switch 1 to switch 6, i.e., the switches are connected in a ring topology. When a message enters from a port of the switch 1 and needs to be forwarded to a port of the switch 6, if the message is forwarded from the switch 1 through six switches one by one, the bandwidth is occupied, and the bandwidth on a link is unreasonably used. The fastest forwarding method for this situation is to forward the message from the port of the switch 1 directly to the port of the switch 6 connected to the switch 1, that is, to select a shortest path for forwarding, and forward the message from the switch 1 directly to the switch 6.
At present, when the prior art is used to forward a message, the message forwarding is usually performed directly according to the forwarding paths between the switches in the preset switch stacking system, instead of performing the message forwarding according to the calculated and determined forwarding shortest path, so the prior art has the following disadvantages: the forwarding efficiency of the message is low; bandwidth occupancy is high and bandwidth usage on the link is not reasonable.
Disclosure of Invention
In view of the above, the main objective of the present invention is to provide a method for calculating a shortest forwarding path, which can implement shortest forwarding of a message in a switch stacking system, so as to improve the forwarding efficiency of the message; reducing bandwidth occupancy and making bandwidth usage on the link more reasonable.
In order to achieve the purpose, the technical scheme of the invention is realized as follows:
a method of calculating a forwarding shortest path, the method comprising the steps of:
A. creating a weight array; initializing the created weight array according to a preset port attribute so as to obtain the weight array from the switch to a neighbor switch; the weight array is an array used for identifying the distance of a message forwarding path between all the switches in the switch stacking system; the port attribute is an attribute used for recording the port connection relationship among all the switches in the switch stacking system;
B. recursively traversing and calculating a weight array from the current switch to the target switch; comparing and obtaining the minimum value in the weight array from the current switch to the target switch to obtain the shortest path from the current switch to the target switch in the switch stacking system; wherein,
the weight array for calculating the current switch to the target switch is as follows: under the condition that a forwarding path from the current switch to a destination switch is unknown; or the forwarding path from the current switch to the destination switch is known, and the formula for calculating the weight array from the current switch to the destination switch is as follows under the condition that the weight array from the current switch to the destination switch is greater than the weight array from the current switch to the reference switch + the weight array from the reference switch to the destination switch: weight [ src ] [ dst ] ═ weight [ src ] [ mid ] + weight [ mid ] [ dst ]; wherein, src is the number of the current switch, mid is the number of the reference switch, and dst is the number of the target switch; weight [ src ] [ dst ] is the weight array from the current switch to the destination switch, weight [ src ] [ mid ] is the weight array from the current switch to the reference switch, and weight [ mid ] [ dst ] is the weight array from the reference switch to the destination switch.
Wherein, step A also includes: initializing a sending matrix according to a preset port attribute; the sending matrix is used for identifying a sending path of the message;
step B, calculating the sending matrix to finish the message sending from the current switch to the target switch; the calculation formula for calculating the sending matrix is as follows: the transmit matrix [ src ] [ dst ] ═ the transmit matrix [ src ] [ mid ].
Wherein, also include after step B:
C. continuing to execute the step B until all the switches are circularly traversed to obtain the shortest path from each switch to the target switch in the switch stacking system; acquiring a sending matrix from each switch to a target switch;
D. and completing the message forwarding of the shortest path according to the shortest path from each switch to the target switch and the sending matrix from each switch to the target switch.
The invention recursively traverses and calculates the weight array from the current switch to the target switch; and comparing and obtaining the minimum value in the weight array from the current switch to the target switch to obtain the shortest path from the current switch to the target switch in the switch stacking system.
The invention can realize the shortest path forwarding of the message in the switch stacking system and improve the forwarding performance of the message in the switch stacking system, namely, the forwarding efficiency of the message is improved, the bandwidth occupancy rate is reduced, and the bandwidth on a link is more reasonably used.
Drawings
FIG. 1 is a schematic flow chart of the implementation of the method of the present invention;
FIG. 2 is a schematic diagram of a switch stack system.
Detailed Description
The core idea of the invention is as follows: recursively traversing and calculating a weight array from the current switch to the target switch; and comparing and obtaining the minimum value in the weight array from the current switch to the target switch to obtain the shortest path from the current switch to the target switch in the switch stacking system.
The following describes the embodiments in further detail with reference to the accompanying drawings.
As shown in fig. 1, a method for calculating a forwarding shortest path includes the following steps:
It should be noted that the weight array is used to identify the distance of the packet forwarding path between the switches in the switch stack system. For the neighbor switches, two adjacent switches are mutually neighbor switches. And the port attribute is used for recording the port connection relation among the switches in the switch stack system.
Here, for creating the weight array, the number of switches in the switch stack system is set to n, and each switch is numbered 0, 1,.. times., (n-1) in descending order, and then a two-dimensional array weight [ n ] [ n ] is created as the weight array, which is used to record the path weight between any two switches. Generally, the path weight between two switches that are neighbor switches to each other, i.e. the weight array of a switch to its neighbor switch is 1, can be understood as that the path of a switch to its neighbor switch is one hop.
Here, step 101 further includes: initializing a sending matrix, namely a sending path of the message according to the preset port attribute so as to complete the message sending from the current switch to the target switch by calculating the sending matrix in the following process. The current switch is a source switch, and the destination switch is a destination switch to which a message needs to be sent through the source switch. The transmit matrix is represented by the transmit matrix source destination. And the sending matrix [ source ] [ destination ] is used for identifying the stacking port on the source switch, and the message sent to any port of the destination switch by the source switch is sent through the stacking port.
Wherein, step 101 further comprises: initializing a receiving matrix, namely a receiving path of the message according to the preset port attribute so as to complete the message receiving of the target switch from the current switch by the subsequent calculation of the receiving matrix. The current switch is a source switch, and the destination switch is a destination switch to which a message needs to be sent through the source switch. The receive matrix is represented by the receive matrix destination source. The receiving matrix [ source ] [ destination ] is used to identify a stack port on the destination switch, and if the source switch needs to send a message to the destination switch, the message is sent to the stack port, that is, a message received by the destination switch from any port of the source switch is received through the stack port.
Hereinafter, the initialization of the created weight array according to the preset port attribute, and the transmission matrix and the reception matrix will be described by way of example.
When a port i is a stack port of a switch with the serial number src, the port attributes of the port i are tx _ cpu _ key and tx _ stk _ idx, and the switch corresponding to tx _ cpu _ key has the serial number dst. Thus, the switch src is used as the source switch and the switch dst is used as the destination switch. Then the switch src can send a message to the switch dst through the port i, and then initialize and set the weight array as: weight [ src ] [ dst ] ═ 1; initializing and setting the transmit matrix as: sending a matrix [ src ] [ dst ] ═ i; initializing and setting the receive matrix as: [ dst ] [ src ] ═ tx _ stk _ idx. According to the method, all stack ports of all switches in the switch stack system are traversed, and initialization of the weight array, the sending matrix and the receiving matrix is completed according to the port attributes of all stack ports in the switch stack system. In addition, when the stack port is fully dual-man-hour, the stack port can be used not only as a port for sending messages, but also as a port for receiving messages. Then, the weight array may also be initialized and set to: weight [ dst ] [ src ] ═ 1; initializing and setting the transmit matrix as: sending a matrix [ dst ] [ src ] ═ i; initializing and setting the receive matrix as: the receive matrix [ src ] [ dst ] ═ tx _ stk _ idx. According to the method, all stack ports of all switches in the switch stack system are traversed, and initialization of the weight array, the sending matrix and the receiving matrix is completed according to port attributes of all stack ports in the switch stack system.
Wherein, step 102 further comprises: and calculating a sending matrix to finish the message sending from the current switch to the target switch. Step 102 further comprises: and calculating a receiving matrix to complete the message receiving of the destination switch from the current switch.
Here, the calculation of the weight array from the current switch to the destination switch specifically includes: under the condition that a forwarding path from a current switch to a target switch is unknown; or the forwarding path from the current switch to the destination switch is known, and the formula for calculating the weight array from the current switch to the destination switch is the following formula (1) under the condition that the weight array from the current switch to the destination switch is greater than the weight array from the current switch to the reference switch + the weight array from the reference switch to the destination switch:
weight[src][dst]＝weight[src][mid]+weight[mid][dst] (1)
wherein, src is the number of the current switch, mid is the number of the reference switch, and dst is the number of the target switch; weight [ src ] [ dst ] is the weight array from the current switch to the destination switch, weight [ src ] [ mid ] is the weight array from the current switch to the reference switch, and weight [ mid ] [ dst ] is the weight array from the reference switch to the destination switch. And the current switch src and the reference switch mid, and the reference switch mid and the destination switch dst are communicated with each other.
Here, the calculation formula for calculating the transmission matrix is formula (2) shown below:
transmit matrix [ src ] [ dst ] ═ transmit matrix [ src ] [ mid ] (2)
Here, the calculation formula for calculating the reception matrix is formula (3) shown below:
receiving matrix [ dst ] [ src ] ═ receiving matrix [ dst ] [ mid ] (3)
It should be noted here that since all switches in the switch stack system are traversed when the shortest path is obtained by calculating and comparing the weight arrays, the switches cannot be the same. For example, in a switch stack system, there are three switches, which are numbered src, mid, and dst, and the three switches cannot be the same: the switch src, the switch mid and the switch dst cannot refer to the same switch, i.e., the switch src, the switch mid and the switch dst refer to three different switches in the switch stack system.
Wherein, in step 102, the method further comprises the following steps: and acquiring a receiving matrix from each switch to a destination switch.
And step 104, setting the shortest path from each switch to the target switch and the sending matrix from each switch to the target switch into a message path forwarding table and sending the message path forwarding table to the chip, and completing message forwarding of the shortest path according to the set value in the chip.
Wherein, in step 104, the method further comprises the following steps: and (3) setting the receiving matrix from each switch to the target switch into a message path forwarding table and issuing the message path forwarding table to the chip, wherein the message forwarding of the shortest path is completed according to the setting value in the chip, namely: and completing the message forwarding of the shortest path according to the shortest path from each switch to the target switch, the sending matrix from each switch to the target switch and the receiving matrix from each switch to the target switch.
The following describes a specific implementation process for calculating the forwarding shortest path in a traversal manner by using an example.
Taking the stack of four switches in fig. 2 as an example, the numbers are A, B, C and D respectively from top to bottom, that is, as shown in fig. 2, the switch stack system in this example includes: switch a, switch B, switch C, and switch D. The switch A is connected with the switch B and the switch D; the switch B is connected with the switch A, the switch C and the switch B; the switch C is connected with the switch B and the switch D; switch D is connected to switch C and switch a. The stack ports of each switch are x-port and y-port, not shown.
Take the example of performing recursive traversal for switch a and calculating the weight array from the current switch to the destination switch. Specifically, the weight array and the transmission matrix of each switch are initialized first. weight [ a ] [ B ] ═ 1, transmission matrix [ a ] [ B ] ═ x, weight [ a ] [ D ] ═ 1, and transmission path [ a ] [ D ] ═ y. Then, when calculating the shortest path, all switches of the switch stack system are traversed, that is, the calculation parameters involved in the above formula (1) and formula (2): the source switch src, the reference computer mid and the destination switch dst all have to traverse to all switches and the source switch src, the reference switch mid and the destination switch dst cannot be identical. Then the process of performing recursive traversal from a and calculating the weight array from the current switch to the destination switch is as follows:
a. taking switch a as the source switch src, since the source switch src, the reference switch mid and the destination switch dst cannot be the same, the reference switch mid starts from switch B, i.e. at this time, the reference switch mid is taken as switch B, and the destination switch dst starts from switch C.
Here, if weight [ a ] [ C ] is unknown, weight [ a ] [ C ] + weight [ B ] [ C ] ═ 2, and transmission matrix [ a ] [ C ] ═ x. Next, the destination switch dst is selected as switch D, but weight [ B ] [ D ] is unknown and the destination switch dst continues to traverse down. Since switch D is the last, the traversal of the destination switch dst is stopped.
b. Next, referring to the switch mid to go down, at this time, switch mid is taken as switch C, and the traversal from a is restarted, and then the destination switch dst can be taken as switch B and switch D.
Here, weight [ A ] [ B ] is known and weight [ A ] [ B ] < weight [ A ] [ C ] + weight [ C ] [ B ], so weight [ A ] [ B ] remains unchanged, as does the transmit matrix [ A ] [ B ].
Next, the destination switch dst is selected as switch D, weight [ A ] [ D ] is known, and weight [ A ] [ D ] < weight [ A ] [ C ] + weight [ C ] [ D ], so weight [ A ] [ D ] remains unchanged, and similarly, the sending matrix [ A ] [ D ] also remains unchanged, and the destination switch dst is the last switch D. Since switch D is the last, the traversal of the destination switch dst is stopped.
c. Next, the reference switch mid continues to traverse downwards, at this time, the reference switch mid is taken as the switch D, the destination switch dst can be taken as the switch B and the switch C, and the calculation is performed according to the above method, so that the shortest paths from the switch a to other switches are determined.
After the switch A is used as the recursive traversal of the source switch src, the source switch src traverses downwards, and the weight arrays and the transmission matrix are calculated according to the principle of the a-c process of performing the recursive traversal from the switch A and calculating the weight arrays from the current switch to the destination switch until all switches in the switch stacking system are circularly traversed, so that the shortest path from each switch to the destination switch in the switch stacking system is finally obtained, and the transmission matrix from each switch to the destination switch is finally obtained.
The above description is only a preferred embodiment of the present invention, and is not intended to limit the scope of the present invention.
Claims (3)
1. A method for calculating a forwarding shortest path, the method comprising the steps of:
A. creating a weight array; initializing the created weight array according to a preset port attribute so as to obtain the weight array from the switch to a neighbor switch; the weight array is an array used for identifying the distance of a message forwarding path between all the switches in the switch stacking system; the port attribute is an attribute used for recording the port connection relationship among all the switches in the switch stacking system;
B. recursively traversing and calculating a weight array from the current switch to the target switch; comparing and obtaining the minimum value in the weight array from the current switch to the target switch to obtain the shortest path from the current switch to the target switch in the switch stacking system; wherein,
the weight array for calculating the current switch to the target switch is as follows: under the condition that a forwarding path from the current switch to a destination switch is unknown; or the forwarding path from the current switch to the destination switch is known, and the formula for calculating the weight array from the current switch to the destination switch is as follows under the condition that the weight array from the current switch to the destination switch is greater than the weight array from the current switch to the reference switch + the weight array from the reference switch to the destination switch: weight [ src ] [ dst ] ═ weight [ src ] [ mid ] + weight [ mid ] [ dst ]; wherein, src is the number of the current switch, mid is the number of the reference switch, and dst is the number of the target switch; weight [ src ] [ dst ] is the weight array from the current switch to the destination switch, weight [ src ] [ mid ] is the weight array from the current switch to the reference switch, and weight [ mid ] [ dst ] is the weight array from the reference switch to the destination switch.
2. The method according to claim 1, wherein step a further comprises: initializing a sending matrix according to a preset port attribute; the sending matrix is used for identifying a sending path of the message;
step B, calculating the sending matrix to finish the message sending from the current switch to the target switch; the calculation formula for calculating the sending matrix is as follows: the transmit matrix [ src ] [ dst ] ═ the transmit matrix [ src ] [ mid ].
3. The method of claim 2, further comprising, after step B:
C. continuing to execute the step B until all the switches are circularly traversed to obtain the shortest path from each switch to the target switch in the switch stacking system; acquiring a sending matrix from each switch to a target switch;
D. and completing the message forwarding of the shortest path according to the shortest path from each switch to the target switch and the sending matrix from each switch to the target switch.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN2008101291297A CN101299726B (en) | 2008-06-30 | 2008-06-30 | Method for calculating forwarding shortest path |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN2008101291297A CN101299726B (en) | 2008-06-30 | 2008-06-30 | Method for calculating forwarding shortest path |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN101299726A CN101299726A (en) | 2008-11-05 |
| CN101299726B true CN101299726B (en) | 2011-04-20 |
Family
ID=40079418
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN2008101291297A Active CN101299726B (en) | 2008-06-30 | 2008-06-30 | Method for calculating forwarding shortest path |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN101299726B (en) |
Families Citing this family (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101488893B (en) * | 2009-03-04 | 2011-04-27 | 北京星网锐捷网络技术有限公司 | Stack system test method, apparatus and system |
| CN101645850B (en) * | 2009-09-25 | 2013-01-30 | 杭州华三通信技术有限公司 | Forwarding route determining method and equipment |
| CN103546390B (en) * | 2012-07-17 | 2018-05-18 | 中兴通讯股份有限公司 | A kind of fixed length bag Weighted Fair Queuing dispatching method and device |
| WO2017108119A1 (en) * | 2015-12-23 | 2017-06-29 | Huawei Technologies Co., Ltd. | Rack awareness |
Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN1764146A (en) * | 2004-10-21 | 2006-04-26 | 华为技术有限公司 | Optimization route choosing method |
| US7123615B2 (en) * | 2002-02-02 | 2006-10-17 | 3Com Corporation | Stacked network routers |
| CN1852266A (en) * | 2006-06-01 | 2006-10-25 | 杭州华为三康技术有限公司 | Method and apparatus for optimizing load-sharing route of network business flow |
| CN101018180A (en) * | 2007-03-12 | 2007-08-15 | 中兴通讯股份有限公司 | A method for implementing the forward table in the stack system |
-
2008
- 2008-06-30 CN CN2008101291297A patent/CN101299726B/en active Active
Patent Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7123615B2 (en) * | 2002-02-02 | 2006-10-17 | 3Com Corporation | Stacked network routers |
| CN1764146A (en) * | 2004-10-21 | 2006-04-26 | 华为技术有限公司 | Optimization route choosing method |
| CN1852266A (en) * | 2006-06-01 | 2006-10-25 | 杭州华为三康技术有限公司 | Method and apparatus for optimizing load-sharing route of network business flow |
| CN101018180A (en) * | 2007-03-12 | 2007-08-15 | 中兴通讯股份有限公司 | A method for implementing the forward table in the stack system |
Also Published As
| Publication number | Publication date |
|---|---|
| CN101299726A (en) | 2008-11-05 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| KR20150140265A (en) | Heterogeneous channel capacities in an interconnect | |
| JP2013524685A5 (en) | Data center and arrangement method | |
| CN104320341B (en) | Adaptive and asynchronous routing network system on 2D-Torus chip and design method thereof | |
| CN102780628B (en) | On-chip interconnection network routing method oriented to multi-core microprocessor | |
| CN101299726B (en) | Method for calculating forwarding shortest path | |
| CN104853399B (en) | Cooperating relay system of selection based on improved Genetic Particle Swarm hybrid algorithm | |
| US7436829B2 (en) | Methods and apparatus for reconfiguring packets to have varying sizes and latencies | |
| KR20130007063A (en) | Hybrid optical networks-on-chip system and routing method thereof | |
| CN109327409B (en) | Data center network DCN, method and switch for transmitting traffic in DCN | |
| CN110536187B (en) | Method for forwarding data and access stratum switching equipment | |
| CN103597789A (en) | Fabric chip having a port resolution module | |
| US9755907B2 (en) | Managing a switch fabric | |
| CN113726879B (en) | Hybrid data center network system VHCN based on VLC link | |
| US8249101B2 (en) | Mobile ad hoc network configured as a virtual internet protocol network | |
| CN113115282B (en) | Thing communication method and system | |
| CN101854691B (en) | Routing method for multi-channel wireless network | |
| CN117155842B (en) | Method, system, equipment and medium for implementing double-host route | |
| CN113632558B (en) | Wi-Fi communication method and device | |
| US9479391B2 (en) | Implementing a switch fabric responsive to an unavailable path | |
| CN117097661A (en) | Data packet forwarding method and device, storage medium and electronic equipment | |
| CN101917334B (en) | A Transmission Network Generation Method Using Partial Node Network Coding | |
| CN110324876B (en) | Clustering routing method based on nano network node energy perception | |
| CN104717154B (en) | A kind of method and device of transmission data packet | |
| CN104065572A (en) | Wireless network routing algorithm for intelligent meter reading system | |
| CN114760719A (en) | Method, apparatus, device and storage medium for discovering and connecting to soft access device |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| C14 | Grant of patent or utility model | ||
| GR01 | Patent grant |