CN105471749A - Order-flexible low diameter large scale interconnection network topological structure and routing method thereof - Google Patents
Order-flexible low diameter large scale interconnection network topological structure and routing method thereof Download PDFInfo
- Publication number
- CN105471749A CN105471749A CN201610040721.4A CN201610040721A CN105471749A CN 105471749 A CN105471749 A CN 105471749A CN 201610040721 A CN201610040721 A CN 201610040721A CN 105471749 A CN105471749 A CN 105471749A
- Authority
- CN
- China
- Prior art keywords
- routing node
- super
- node
- place
- bunch
- 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.)
- Granted
Links
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/02—Topology update or discovery
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
The invention discloses an order-flexible low diameter large scale interconnection network topological structure and a routing method thereof, solving the problem that a current network topological structure can not overcome disadvantages and deficiencies of the present router technique. In the technical scheme, a whole topology is connected by nq super routing nodes in a Galaxy graph mode, wherein the nodes are divided into n clusters, and each cluster comprises q super routing nodes. Each super routing node comprises a connected routing nodes; each super routing node leads out ah links to connect with other super routing nodes; (n-1) links are in connection with super routing node of other clusters in the Galaxy graph; (q-delta)/2 links are in connection with other super routing node of a same cluster; each routing node is in connection with p terminals, and leads out (a-1) links to connect with other (a-1) routing nodes in a same super routing node; h links are in connection with other super routing nodes. Compared with a current network topological structure, the network topological structure of the invention has the advantages of low network diameter and flexible configuration, and can effectively support an HPC system.
Description
Technical field
The present invention relates to the interference networks in the communications field, be specifically related to a kind of exponent number for extensive interference networks low diameter topological structure and method for routing thereof flexibly.
Background technology
Instantly, the scale of large-scale computing systems has exceeded several ten thousand nodes, as the Milky Way No. 2 supercomputer systems of China and Blue Gene (BlueGene/Q) system of IBM.These large-scale computing systems have strict requirement and demand to the overall performance of system, constructions cost and power consumption.Interference networks are important component parts of large-scale computing systems, and occupy critical role in the design object completing whole system.Network delay, the network bandwidth and cost and power dissipation overhead are all used to the important indicator assessing interference networks end to end.The interference networks of planned network topological structure to structure large-scale computing systems are extremely important.
For meeting the large-scale computing systems of more different application and scale, design of network topology structure needs to consider following three indexs:
1. cost overhead and energy consumption expense cost performance.For E (Exascale=10
18=trillion (10
2× 10
8× 10
8) Flops) level high-performance calculation (HighPerformanceComputing, HPC) system, system platform cost requirement will at below 20MW with power dissipation overhead below 200M dollar.In whole E level HPC system construction, cost overhead and the power dissipation overhead of structure interference networks can account for 33% and 50% of whole system.So, a cost overhead and the high topological structure of energy consumption expense cost performance essential to E level HPC system.
2. end-to-end delay.The physics postponing to depend mainly on network diameter and real system is end to end disposed.A good topological structure not only requires that low also requirement of network diameter is convenient to dispose, and therefore, lower end-to-end delay is also the important indicator of optimized network performance.
3. the flexibility of topological structure.High performance computing system is because application demand is different, also different to the scale demand of several ten thousand nodes from hundreds of.So the flexibility of topological structure is also the important indicator in topology design, need the flexibility of topological structure can support different network sizes under limited router technique.
But, limited power consumption, area-constrained under, meet ever-increasing interconnect bandwidth and performance requirement, realize extensive, high density, high performance Systems Interconnection Network, complete above-mentioned target and there are some challenges.The physics postponing to depend mainly on network diameter and real system is end to end disposed.So some topological structures have been suggested the topological structure solving low network diameter, as: Dragonfly, HyperX, Skywalk and SlimFly etc., but these topological structures are difficult to realize E level computing system under existing router process conditions.At present, what construct low diameter topological structure is all based on high-order router, but due to the physical resource of chip and the growth of power dissipation overhead constraint route chip exponent number, these low diameter topological structures are difficult to arbitrary extension scale.In the router chip of signal of telecommunication interconnection, the restriction of the area of SerDes, the complexity of Crossbar and chip boundary bandwidth makes chip exponent number while each port bandwidth of guarantee increase difficulty.And the power consumption that the growth of exponent number can cause router chip larger is born.Such as, the data of a unidirectional SerDes link transmission data bit (bit) need to consume 20pJ, and so the up-to-date Omni-path framework put forward of Intel needs to consume 160W on SerDes.Therefore, research and propose use silicon photonics at present and solve the problems such as chip bandwidth, electric energy consumption.Altera and Avago has produced a fpga chip applying embedded parallel optical module MicroPOD.Although relative light signal technology is day by day ripe, because the restriction of optical module polymerization makes each router chip still can not draw more port.Along with E level calculates the arrival in epoch, the problem of router exponent number is more and more important.Another one challenge is then how tradeoff design interference networks.In order to the complexity of control system, data center proposes to use the computing system of rack scale to replace traditional modular system, and the computing system of rack scale can provide high bandwidth, and the application for cabinet-level proposes routing mechanism and congestion control flexibly and effectively.Such system is equally applicable to some stationary applications of high performance computing system.But the bandwidth of how to compromise rack room and interior of equipment cabinet is still an open problem to the optimal performance realizing whole system.
Since the proposition of FlattenedButterfly structure, using high-order router to build interconnected network system is Main Means.A lot of higher order topology also proposes in succession, as Fattree structure, Dragonfly structure, HyperX structure, Skywalk structure, SlimFly structure etc.Higher order topology structure compares low order topological structure can obtain less network diameter, such as Torus and Mesh.But these higher order topology structures adopt the router of current process can not support E level HPC system at present.Fattree structure is one of the most classical higher order topology structure, can scale be increased by adding the number of plies and do not use the router of more high-order, but Fattree topological structure is difficult to expansion, and when physics realization, wiring density and wiring irregularity are its very large shortcomings.Dragonfly structure not only network diameter low and also combine Power Line Communication and fiber optic cable communications advantage reduce cost overhead, but once router exponent number is determined, its maximum-norm that can build is certain.HyperX structure be one can the topological structure of flexible configuration, but every one-dimentional structure is all that the totally interconnected autgmentability that causes is limited.Although Skywalk structure can support random scale and limit the length of link, the factors such as routing policy are all uncontrollable.SlimFly is diameter is 2 structures that can be similar to support maximum-norm, but is limited to fixing path and network size.
Summary of the invention
One object of the present invention is, for overcoming the shortcoming of existing route device technique based on existing interconnection network topological structure with not enough, cannot support E level HPC system, provide a kind of exponent number extensive interconnection network topological structure of low diameter flexibly.
Another object of the present invention provides a kind of method for routing on designed topological structure.
In order to reach first object; the present invention realizes by the following technical solutions: exponent number is the extensive interconnection network topological structure of low diameter flexibly; whole topology is divided into double-layer structure; a large super routing node is formed as ground floor structure by a routing node is totally interconnected; a routing node in super routing node be designated as respectively the 0th routing node, the 1st routing node ..., t routing node ..., a-1 routing node; 0≤t≤a-1, a, t are integer.Second layer structure is then based on ground floor structure, and each super routing node is connected other super routing node by the mode of Galaxy figure, and wherein said connection is that the h bar link of respectively being drawn by a routing node in ground floor structure provides, and h is integer.Galaxy figure be one can the figure of flexible configuration, according to the configuration needs of real system, the parameter configuration of adjustment Galaxy figure, thus build whole network topology.
Galaxy figure of the present invention is determined by parameter n, q, and n, q are integer.
Have in Galaxy figure n bunch (cluster), be designated as the 0th bunch, the 1st bunch ..., kth bunch ..., (n-1)th bunch, 0≤k≤n-1, k is integer.There is q node in each bunch and meet
wherein δ ∈-1,0,1},
for integer, q node be designated as respectively the 0th node, first node ..., the i-th node ..., q-1 node.0≤i≤q-1, i is integer.Each node is drawn (q-δ)/2 link and is connected other (q-δ)/2 nodes with cluster, and draws n-1 bar link and connect node in other n-1 bunch respectively.
Each node two-dimensional coordinate represents, the two-dimensional coordinate of the i-th node in kth bunch is designated as (a
i0a
i1a
isa
i (n-1), k), the n tuple a of the first dimension
i0a
i1a
isa
i (n-1)what represent is that current super routing node has the numbering of the super routing node of annexation with other n-1 bunches respectively, and i represents that this node is the i-th node in kth bunch, wherein a
isrepresent the i-th node (a of kth bunch
i0a
i1a
isa
i (n-1), k) connect the node (a of s bunch
j0a
j1a
jka
j (n-1), s), wherein a
jk=a
is, 0≤a
is≤ q-1,0≤j≤q-1, a
ik=i, 0≤s≤n-1, s, j are integer.The k of the second dimension represents that this node is positioned at kth bunch.
In Galaxy figure, kth bunch follows the condition be connected between s bunch of two nodes as follows:
(1) if k<s, so:
And if only if a
is-a
js∈ X, (a
i0a
i1a
isa
i (n-1), k) with (a
j0a
j1a
jsa
j (n-1), k) be connected.
And if only if a
ik-a
jk∈ X ', (a
i0a
i1a
ika
i (n-1), s) with (a
j0a
j1a
jka
j (n-1), s) be connected.
And if only if a
is=a
jk, (a
i0a
i1a
isa
i (n-1), k) with (a
j0a
j1a
jka
j (n-1), s) be connected.
(2) if k=s, so:
And if only if a
is-a
js∈ X, (a
i0a
i1a
isa
i (n-1), k) with (a
j0a
j1a
jsa
j (n-1), k) be connected.
(3) if k>s, so:
And if only if a
is-a
js∈ X ', (a
i0a
i1a
isa
i (n-1), k) with (a
j0a
j1a
jsa
j (n-1), k) be connected.
And if only if a
ik-a
jk∈ X, (a
i0a
i1a
ika
i (n-1), s) with (a
j0a
j1a
jka
j (n-1), s) be connected.
And if only if a
is=a
jk, (a
i0a
i1a
isa
i (n-1), k) with (a
j0a
j1a
jka
j (n-1), s) be connected.
Wherein, X and X ' is defined as follows, and ξ is finite field F
qgenerator:
(1) if
then X={1, ξ
2..., ξ
q-3, X '={ ξ, ξ
3..., ξ
q-2;
(2) if
then
(3) if
then
It should be noted that, when asking set X and X ', all needing to make to the element in set the content that value that mould q computing draws is only set; In Galaxy figure kth bunch be connected between s bunch of two nodes condition judgment time, expression formula a
is-a
jsdeng whether belonging to set X or X ', be also to a
is-a
jsdo mould q computing to judge whether again to belong to set X or X ', but in order to the terseness expressed, be not particularly illustrated in relevant Mathematical Papers and will make mould q computing [MaciejBesta etc., SlimFly:ACostEffectiveLow-DiameterNetworkTopology " (the effective low diameter network topology SlimFly of a kind of cost); InternationalConferenceforHighPerformanceComputing; Networking; StorageandAnalysis2014 (SC2014), second chapter Part II].Therefore, asking set X and X ' and to judge in Galaxy figure that whether connected kth bunch with time between s bunch of two nodes in the present invention, be not particularly illustrated and will make mould q and operate.
In practical structures, each routing node is by three-dimensional coordinate (a
i0a
i1... a
ik... a
i (n-1), k, t) represent, a
i0a
i1a
ika
i (n-1)represent that the super routing node at this routing node place is in the position of Galaxy figure with k, t then represents that this routing node is super routing node (a
i0a
i1... a
ik... a
i (n-1), t routing node k), and meet the h bar link that each routing node is supplied to second layer structure and meet ah>=n-1+ (q-δ)/2.Each terminal is then by four-dimensional coordinate (a
i0a
i1... a
ik... a
i (n-1), k, t, c) represent, c represents that this terminal is routing node (a
i0a
i1... a
ik... a
i (n-1), k, t) c terminal, the number of terminals that p connects for each routing node, 0≤c≤p-1, p, c are integer.
Therefore, topological structure of the present invention nq super routing node is divided into q super routing node in n bunch, each bunch and is formed by connecting according to the mode of Galaxy figure by nq super routing node, comprise a routing node in each super routing node, each routing node connects p terminal.Each routing node draws other a-1 routing node in the same super routing node of a-1 bar link connection, draws h bar link and connects other super routing node.So, a super routing node is drawn ah bar link and is connected other super routing node, meet ah >=n-1+ (q-δ)/2, wherein n-1 bar link connects the super routing node of other bunch in Galaxy figure, and (q-δ)/2 link connects other super routing node of same bunch.
In order to reach second object, the present invention by the following technical solutions: a kind of method for routing based on the described exponent number extensive interconnection network topological structure of low diameter flexibly, search message from routing node (a
i0a
i1a
ika
i (n-1), k, t
1) to object terminal (a
j0a
j1a
jka
j (n-1), s, t
2, route c) comprises following steps, wherein t
1and t
2be respectively the numbering of routing node in super routing node, 0≤t
1≤ a-1,0≤t
2≤ a-1, t
1, t
2be integer:
(1) routing node (a at current message place is detected
i0a
i1a
ika
i (n-1), k, t
1) and object terminal (a
j0a
j1a
jka
j (n-1), s, t
2, the c) routing node (a at place
j0a
j1a
jka
j (n-1), s, t
2) whether be same routing node, namely detect and whether meet a
ik=a
jk, k=s and t
1=t
2;
If a
ik=a
jk, k=s and t
1=t
2, show that the routing node at message place and the routing node at object terminal place are same routing node, then by object terminal (a
j0a
j1a
jka
j (n-1), s, t
2, c) as next-hop node, path finding terminates;
Otherwise, a
ik≠ a
jkor k ≠ s or t
1≠ t
2, show that the routing node at message place and the routing node at object terminal place are not same routing node, enter step (2);
(2) routing node (a at detection messages place
i0a
i1a
ika
i (n-1), k, t
1) and the routing node (a at object terminal place
j0a
j1a
jka
j (n-1), s, t
2) whether in same super routing node, namely detect and whether meet a
ik=a
jkand k=s;
If a
ik=a
jkand k=s, show that the routing node at the routing node at message place and object terminal place is in same super routing node, then by the routing node (a at object terminal place
j0a
j1a
jka
j (n-1), s, t
2) as next-hop node, go to step (1);
Otherwise, a
ik≠ a
jkor k ≠ s, show that the routing node at the routing node at message place and object terminal place is not in same super routing node, then enter step (3);
(3) the super routing node (a at detection messages place
i0a
i1a
ika
i (n-1), k) and the super routing node (a at object terminal place
j0a
j1a
jka
j (n-1), whether s) be connected, method: if k<s and a if being
is=a
jk, enter step (3.1); If k=s and a
js-a
is∈ X, enters step (3.2); If k>s and a
is=a
jk, enter step (3.3); Otherwise the condition of step (3.1), (3.2), (3.3) does not all meet, show that the super routing node at message place is not connected with the super routing node at object terminal place, go to step (4);
(3.1) k<s and a
is=a
jk, show that the super routing node at message place is connected with the super routing node at object terminal place.If the routing node (a at message place
i0a
i1a
ika
i (n-1), k, t
1) and the super routing node (a of object
j0a
j1a
jka
j (n-1), s) connected routing node
being same routing node is
wherein
for lower floor operation, then routing node
as down hop, enter step (1); If
then by the super routing node (a at message place
i0a
i1... a
ik... a
i (n-1), k) with the super routing node (a of object
j0a
j1... a
jk... a
j (n-1), s) connected routing node
as down hop, enter step (1);
(3.2) k=s and a
js-a
is∈ X, shows that the super routing node at message place is connected with the super routing node at object terminal place.If the routing node (a at message place
i0a
i1a
ika
i (n-1), k, t
1) and the super routing node (a of object
j0a
j1... a
jk... a
j (n-1), s) connected routing node
being same routing node is
wherein Δ is a
js-a
isthe value of mould q is gathering the sequence number sorted from small to large in X, then routing node
as down hop, wherein λ is a
is-a
jsthe value of mould q, gathering the sequence number sorted from small to large in X, enters step (1); If
then by the super routing node (a at message place
i0a
i1... a
ik... a
i (n-1), k) with the super routing node (a of object
j0a
j1... a
jk... a
j (n-1), s) connected routing node
as down hop, enter step (1);
(3.3) k>s and a
is=a
jk, show that the super routing node at message place is connected with the super routing node at object terminal place.If the routing node (a at message place
i0a
i1a
ika
i (n-1), k, t
1) and the super routing node (a of object
j0a
j1... a
jk... a
j (n-1), s) connected routing node
being same routing node is
then routing node
as down hop, enter step (1); If
then by the super routing node (a at message place
i0a
i1... a
ik... a
i (n-1), k) with the super routing node (a of object
j0a
j1... a
jk... a
j (n-1), s) connected routing node
as down hop, enter step (1);
(4) the super routing node (a with message place is found
i0a
i1... a
is... a
i (n-1), k) with the super routing node (a of object
j0a
j1... a
jk... a
j (n-1), public super routing node s), finding method is as follows: if k<s, enters step (4.1); If k=s, enter step (4.2); If k>s, enter step (4.3);
(4.1) if a
is-a
jk∈ X, enters step (4.1.1); If a
is-a
jk∈ X ', enters step (4.1.2);
(4.1.1) a
is-a
jk∈ X, shows that the public super routing node of the super routing node at message place and the super routing node at object terminal place is in kth bunch, then meet a
ls=a
jksuper routing node (a
l0a
l1... a
ls... a
l (n-1), k) be public super routing node, wherein 0≤l≤q-1, l is integer;
If the routing node (a at message place
i0a
i1a
ika
i (n-1), k, t
1) and public super routing node (a
l0a
l1... a
lk... a
l (n-1), k) connected routing node
being same routing node is
wherein Δ is a
lk-a
ikthe value of mould q is gathering the sequence number sorted from small to large in X, then routing node
as down hop, wherein λ is a
ik-a
lkthe value of mould q, gathering the sequence number sorted from small to large in X, enters step (1);
If
then by the super routing node (a at message place
i0a
i1... a
is... a
i (n-1), k) with public super routing node (a
l0a
l1... a
ls... a
l (n-1), k) connected routing node
as down hop, wherein Δ is a
lk-a
ikthe value of mould q, gathering the sequence number sorted from small to large in X, enters step (1);
(4.1.2) a
is-a
jk∈ X ', shows that the public super routing node of the super routing node at message place and the super routing node at object terminal place is in s bunch, then meet a
is=a
lksuper routing node (a
l0a
l1... a
lk... a
l (n-1), s) be public super routing node, wherein 0≤l≤q-1, l is integer;
If the routing node (a at message place
i0a
i1a
isa
i (n-1), k, t
1) and public super routing node (a
l0a
l1... a
lk... a
l (n-1), s) connected routing node
being same routing node is
then routing node
as down hop, enter step (1);
If
then by the super routing node (a at message place
i0a
i1... a
ik... a
i (n-1), k) with public super routing node (a
l0a
l1... a
lk... a
l (n-1), s) connected routing node
as down hop, enter step (1);
(4.2) by order traversal kth bunch all super routing node (a from big to small
l0a
l1... a
lk... a
l (n-1), k) meet a
lk-a
ik∈ X and a
jk-a
lkthe minimum value of ∈ X, then super routing node (a
l0a
l1... a
ls... a
l (n-1), k) be public super routing node, wherein 0≤l≤q-1, l is integer;
If the routing node (a at message place
i0a
i1a
isa
i (n-1), k, t
1) and public super routing node (a
l0a
l1... a
ls... a
l (n-1), k) connected routing node
being same routing node is
wherein Δ is a
lk-a
ikthe value of mould q is gathering the sequence number sorted from small to large in X, then routing node
as down hop, wherein λ is a
ik-a
lkthe value of mould q, gathering the sequence number sorted from small to large in X, enters step (1);
If
then by the super routing node (a at message place
i0a
i1... a
ik... a
i (n-1), k) with public super routing node (a
l0a
l1... a
lk... a
l (n-1), k) connected routing node
as down hop, wherein Δ is a
lk-a
ikthe value of mould q, gathering the sequence number sorted from small to large in X, enters step (1);
(4.3) if a
is-a
jk∈ X, enters step (4.3.1); If a
is-a
jk∈ X ', enters step (4.3.2);
(4.3.1) a
is-a
jk∈ X, shows that the public super routing node of the super routing node at message place and the super routing node at object terminal place is in s bunch, then meet a
lk=a
issuper routing node (a
l0a
l1... a
lk... a
l (n-1), s) be public super routing node, wherein 0≤l≤q-1, l is integer;
If the routing node (a at message place
i0a
i1a
isa
i (n-1), k, t
1) and public super routing node (a
l0a
l1... a
lk... a
l (n-1), s) connected routing node
being same routing node is
then routing node
as down hop, enter step (1);
If
then by the super routing node (a at message place
i0a
i1... a
is... a
i (n-1), k) with public super routing node (a
l0a
l1... a
lk... a
l (n-1), s) connected routing node
as down hop, enter step (1);
(4.3.2) a
is-a
jk∈ X ', shows that the public super routing node of the super routing node at message place and the super routing node at object terminal place is in kth bunch, then meet a
ls=a
jksuper routing node (a
l0a
l1... a
lk... a
l (n-1), k) be public super routing node, wherein 0≤l≤q-1, l is integer;
If the routing node (a at message place
i0a
i1a
ika
i (n-1), k, t
1) and public super routing node (a
l0a
l1... a
lk... a
l (n-1), k) connected routing node
being same routing node is
wherein Δ is a
lk-a
ikthe value of mould q is gathering the sequence number sorted from small to large in X, then routing node
as down hop, wherein λ is a
ik-a
lkthe value of mould q is gathering the sequence number sorted from small to large in X, and λ is integer and sorts from 0, enters step (1);
If
then by the super routing node (a at message place
i0a
i1... a
is... a
i (n-1), k) with public super routing node (a
l0a
l1... a
lk... a
l (n-1), k) connected routing node
as down hop, wherein Δ is a
lk-a
ikthe value of mould q is gathering the sequence number sorted from small to large in X, and Δ is integer and sorts from 0, enters step (1).
The present invention has following advantage and effect relative to prior art:
(1) the extensive interconnection network topological structure of the present invention is not when by the restriction of router exponent number, and growth scale is successional.If when router chip technique is limited, this structure can build same scale network with the router chip that exponent number is different also can build the network of different scales with the router chip of same exponent number, namely network size is nqap, the exponent number of routing node is a+h+p-1, can be realized the network struction of different demand by adjustment parameter n, a, p, q, h.Therefore, topological structure of the present invention can overcome the shortcoming of existing route device technique with not enough, supports E level HPC system;
(2) the extensive interconnection network topological structure of the present invention is the hierarchical structure configured by multi-parameter, therefore can according to the demand of real system, and adjustment parameter n, a, p, q, h meet the demand of system two points of performances such as bandwidth, network diameter;
(3) the Galaxy figure that adopts of the extensive interconnection network topological structure of the present invention can according to requirement in practical systems according to bunch or the large wisp structure of super node be divided into several modules and be convenient to physical layout, and in conjunction with optical cable and cable cost and apart from upper difference, effectively reduce the expense of physics cost; And Galaxy figure be one can the figure of flexible configuration, according to the configuration needs of real system, the parameter configuration of adjustment Galaxy figure, thus build whole network topology flexibly, and support the network struction of different scales HPC system;
(4) in the extensive interconnection network topological structure of the present invention; q bar link and super routing node inside is had to be totally interconnected structures between any two bunches; make to have many redundant links between super routing node and between routing node; therefore method for routing of the present invention can find mulitpath, effectively promotes communication efficiency and the fault-tolerance of topological structure.
Accompanying drawing explanation
Fig. 1 is the exponent number of the present invention ground floor structure of the extensive interconnection network topological structure of low diameter and super routing node structure chart flexibly, and the router quantity wherein in super routing node is a=3;
Fig. 2 is the exponent number of the present invention macrograph of the second layer structure of the extensive interconnection network topological structure of low diameter and Galaxy figure flexibly, and quantity wherein bunch is n=2, and the number of nodes of each bunch is q=5;
Fig. 3 is the exponent number of the present invention extensive interconnection network topological structure of low diameter flexibly, wherein configuration n=2 and q=5 of Galaxy figure, the routing node quantity a=3 of each super routing node, and mark super routing node (00 in detail, 0) and (13,1) connection and between (11,0);
Fig. 4 is the method for routing flow chart of the exponent number of the present invention extensive interconnection network topological structure of low diameter flexibly.
Embodiment
Below in conjunction with embodiment and accompanying drawing, the present invention is described in further detail, but embodiment of the present invention are not limited thereto.
This example discloses each Rotating fields of extensive interconnection network topological structure, and as shown in Figure 1,3 routing nodes in a super routing node are totally interconnected to be formed as ground floor structure; Now each routing node connects 2 terminals with two ports respectively, and another two ports connect other two routing nodes in same super routing node respectively.The second layer structure macrograph of topological structure as shown in Figure 2, each super routing node draws 2 links connections two other super routing node with cluster, and draw 1 super routing node that 1 link connects another bunch, wherein n=2 and q=5, then gather X={1,4}, X '={ 2,3}.By being configured to the single super routing node that Galaxy schemes and every 3 routing nodes form of n=2, q=5 to form topological structure of the present invention as shown in Figure 3, this topological structure comprises double-layer structure.In second layer structure, the link between super routing node is respectively from each routing node in ground floor structure, and 3 routing nodes namely in each super routing node are drawn 1 link respectively and connected other 3 super routing nodes.
This example topological structure is made up of 2 bunches and each bunch of 5 super routing nodes, and wherein each super routing node is containing 3 routing nodes and 6 terminals, in this example n=2, q=5, a=3 and p=2.
Be its numbering according to super routing node and routing node and terminal present position coordinate in the extensive interconnection network topological structure of this example.
Each super routing node uses two-dimensional coordinate (a
i0a
i1a
isa
i (n-1), k) represent, the n tuple a of the first dimension
i0a
i1a
isa
i (n-1)what represent is that current super routing node has the numbering of the super routing node of annexation, wherein a with other n-1 bunches respectively
isrepresent the i-th node (a of kth bunch
i0a
i1a
isa
i (n-1), k) connect the node (a of s bunch
j0a
j1a
jka
j (n-1), s), wherein, a
jk=a
is, a
ik=i.The k of the second dimension then represents that current super routing node is positioned at kth bunch.The macrograph of topological structure second layer structure of the present invention as shown in Figure 2, give each super routing node numbering according to above-mentioned coordinate, n=2, q=5, therefore in structure, the coordinate of each super routing node is (a
i0a
i1, k), wherein for the super routing node being numbered (11,0), k is 0, represents that this super routing node is positioned at No. 0 bunch, a
10be 1, represent that this super routing node is positioned at No. 0 bunch of No. 1 super routing node structure, a
11be 1, represent this super routing node and be positioned at the 1st bunch and its a
i0coordinate be 1 super routing node have annexation.Therefore the super routing node being numbered (13,1) and the super routing node being numbered (11,0) have connection.For the super routing node that coordinate figure is (13,1), due to a
30be 1, represent this super routing node and be positioned at the 0th bunch and its a
i1coordinate be 1 super routing node have annexation, and then further verification number be that the super routing node of (13,1) and the super routing node that is numbered (11,0) have connection.Because q=5, then gather X={1,4}, because a
20-a
10=1, so a
20-a
10∈ X, has annexation between the super routing node being therefore numbered (11,0) and (22,0).In like manner, annexation is had, wherein a between the super routing node being numbered (21,1) and (42,1)
21-a
11∈ X.
For each routing node, use 3 dimension coordinate (a
i0a
i1a
ika
i (n-1), k, t), the first peacekeeping two-dimensional representation be all the coordinate of this super routing node in routing node place, the t of the 3rd dimension then represents routing node (a
i0a
i1a
ika
i (n-1), k, t) and be the super routing node (a in place
i0a
i1a
ika
i (n-1), t routing node k).Whole topological structure as shown in Figure 3, is numbered (00,0,0), (00,0,1) and (00,0,2) routing node is positioned at super routing node (00,0), in structure, each routing node is drawn a link respectively and is connected super routing node (11,0), (44,0) and (00,1).
For each terminal, use 4 dimension coordinate (a
i0a
i1a
ika
i (n-1), k, t, c), the first peacekeeping two-dimensional representation be the super routing node (a in this terminal place
i0a
i1a
ika
i (n-1), numbering k), that the third dimension represents is this terminal place routing node (a
i0a
i1a
ika
i (n-1), k, t) numbering, what fourth dimension represented is that this terminal is at routing node (a
i0a
i1a
ika
i (n-1), k, t) connect the numbering of terminal, wherein 0≤c≤p-1.
Topological structure as shown in Figure 3, utilize the method for routing of the exponent number of the present invention extensive interconnection network topological structure of low diameter flexibly to find terminal (00,0,2,0) to the path of terminal (13,1,2,0), step is as follows:
(1) whether sense terminals (00,0,2,0) and terminal (13,1,2,0) connect on same routing node, and after testing, they are not connected on same routing node;
(2) whether the routing node at sense terminals (00,0,2,0) and terminal (13,1,2,0) place connects on same super routing node, and after testing, they are not connected on same super routing node;
(3) whether the super routing node at sense terminals (00,0,2,0) and terminal (13,1,2,0) place is connected, and after testing, is not connected between the super routing node at two terminal places;
(4) the super routing node be jointly connected with the super routing node of terminal (00,0,2,0) and terminal (13,1,2,0) place is found.The super routing node being numbered (11,0) is as seen from Figure 3 super routing node (00,0) and (13,1) public super routing node, the routing node (00 in super routing node (00,0), 0,0) routing node (11 of super routing node (11,0) is connected, 0,1), therefore, then by routing node (00,0,0) as down hop.
Next by routing node (00,0,0) as current routing node, detect routing node (00,0,0) and object routing node (13,1,2) whether be connected on same routing node, as shown in Figure 3, two routing nodes are not be connected on same routing node, simultaneously, also not in same super routing node, and be not connected between the super routing node at two routing node places.Continue the public super routing node of super routing node at searching two routing node places and the routing node that the super routing node at current routing node place is connected with public super routing node as down hop, namely with routing node (00,0,0) routing node (11 be connected, 0,1) as down hop.
Next by routing node (11,0,1) as current routing node, detect routing node (11,0,1) and object routing node (13,1,2) whether be connected on same routing node, as shown in Figure 3, two routing nodes are not be connected on same routing node, simultaneously, also not in same super routing node, but be connected between the super routing node at two routing node places.The routing node continuing to be connected between the super routing node at searching two routing node places is as down hop, and the routing node (11,0,2) be namely connected with routing node (11,0,1) is as down hop.
Next by routing node (11,0,2) as current routing node, detect routing node (11,0,2) and object routing node (13,1,2) whether be connected on same routing node, as shown in Figure 3, two routing nodes are not be connected on same routing node, simultaneously, also not in same super routing node, but be connected between the super routing node at two routing node places.The routing node continuing to be connected between the super routing node at searching two routing node places is as down hop, and the routing node (13,1,2) be namely connected with routing node (11,0,2) is as down hop.
Routing node (13,1,2) is exactly the routing node that object terminal (13,1,2,0) connects, and path finding terminates.
Above-described embodiment is shortest-path rout ing algorithms execution mode of the present invention; but embodiments of the present invention are not restricted to the described embodiments; change, the modification done under other any does not deviate from Spirit Essence of the present invention and principle, substitute, combine, simplify; all should be the substitute mode of equivalence, be included within protection scope of the present invention.
Claims (8)
1. an exponent number extensive interconnection network topological structure of low diameter flexibly, it is characterized in that, whole topology is divided into double-layer structure, a large super routing node is formed as ground floor structure by a routing node is totally interconnected, a routing node in super routing node be designated as respectively the 0th routing node, the 1st routing node ..., t routing node ..., a-1 routing node, 0≤t≤a-1, a, t are integer; Second layer structure is then based on ground floor structure, and each super routing node is connected other super routing node by the mode of Galaxy figure, and wherein said connection is that the h bar link of respectively being drawn by a routing node in ground floor structure provides, and h is integer;
Have in Galaxy figure n bunch (cluster), be designated as the 0th bunch, the 1st bunch ..., kth bunch ..., (n-1)th bunch, 0≤k≤n-1, n, k are integer; There is q node in each bunch, a super routing node of each node and topological structure ground floor structure, and meet q=4l+ δ, wherein δ ∈ {-1,0,1}, l is integer, q node be designated as respectively the 0th node, first node ..., the i-th node ..., q-1 node; 0≤i≤q-1, i, q are integer; Each node is drawn (q-δ)/2 link and is connected other (q-δ)/2 nodes with cluster, and draws n-1 bar link and connect node in other n-1 bunch respectively;
Each node two-dimensional coordinate represents, the two-dimensional coordinate of the i-th node in kth bunch is designated as (a
i0a
i1a
isa
i (n-1), k), the n tuple a of the first dimension
i0a
i1a
isa
i (n-1)what represent is that current super routing node has the numbering of the super routing node of annexation with other n-1 bunches respectively, and i represents that this node is the i-th node in kth bunch, wherein a
isrepresent the i-th node (a of kth bunch
i0a
i1a
isa
i (n-1), k) connect the node (a of s bunch
j0a
j1a
jka
j (n-1), s), wherein a
jk=a
is, 0≤a
is≤ q-1,0≤j≤q-1, a
ik=i, 0≤s≤n-1, s, j are integer; The k of the second dimension represents that this node is positioned at kth bunch; Each super routing node is drawn ah bar link and is connected other super routing node, meet ah>=n-1+ (q-δ)/2, wherein n-1 bar link connects the super routing node of other bunch in Galaxy figure, and (q-δ)/2 link connects other super routing node of same bunch;
Comprise a routing node in each super routing node, each routing node is by three-dimensional coordinate (a
i0a
i1... a
ik... a
i (n-1), k, t) represent, a
i0a
i1a
ika
i (n-1)represent that the super routing node at this routing node place is in the position of Galaxy figure with k, t then represents that this routing node is super routing node (a
i0a
i1... a
ik... a
i (n-1), t routing node k), each routing node draws other a-1 routing node in the same super routing node of a-1 bar link connection, draws h bar link and connects other super routing node;
Each routing node connects p terminal, and each terminal is then by four-dimensional coordinate (a
i0a
i1... a
ik... a
i (n-1), k, t, c) represent, c represents that this terminal is routing node (a
i0a
i1... a
ik... a
i (n-1), k, t) c terminal, 0≤c≤p-1, p, c are integer.
2. the exponent number extensive interconnection network topological structure of low diameter flexibly as claimed in claim 1, is characterized in that, in described Galaxy figure, kth bunch follows the condition be connected between s bunch of two nodes as follows:
(1) if k<s, so:
And if only if a
is-a
js∈ X, (a
i0a
i1a
isa
i (n-1), k) with (a
j0a
j1a
jsa
j (n-1), k) be connected;
And if only if a
ik-a
jk∈ X ', (a
i0a
i1a
ika
i (n-1), s) with (a
j0a
j1a
jka
j (n-1), s) be connected;
And if only if a
is=a
jk, (a
i0a
i1a
isa
i (n-1), k) with (a
j0a
j1a
jka
j (n-1), s) be connected;
(2) if k=s, so:
And if only if a
is-a
js∈ X, (a
i0a
i1a
isa
i (n-1), k) with (a
j0a
j1a
jsa
j (n-1), k) be connected;
(3) if k>s, so:
And if only if a
is-a
js∈ X ', (a
i0a
i1a
isa
i (n-1), k) with (a
j0a
j1a
jsa
j (n-1), k) be connected;
And if only if a
ik-a
jk∈ X, (a
i0a
i1a
ika
i (n-1), s) with (a
j0a
j1a
jka
j (n-1), s) be connected;
And if only if a
is=a
jk, (a
i0a
i1a
isa
i (n-1), k) with (a
j0a
j1a
jka
j (n-1), s) be connected;
Wherein, X and X ' is defined as follows, and ξ is finite field F
qgenerator:
(1) if q=4l+1, then X={1, ξ
2..., ξ
q-3, X '={ ξ, ξ
3..., ξ
q-2;
(2) if q=4l-1, then X={1, ξ
2..., ξ
2l-2, ξ
2l-1, ξ
2l+1..., ξ
4l-3,
X′＝{ξ,ξ
3,…,ξ
2l-1,ξ
2l,…,ξ
4l-4,ξ
4l-2}；
(3) if q=4l, then X={1, ξ
2..., ξ
4l-2, X '={ ξ, ξ
3..., ξ
4l-1.
3. the exponent number extensive interconnection network topological structure of low diameter flexibly as claimed in claim 2, is characterized in that, when asking set X and X ', all needs to make to the element in set the content that value that mould q computing draws is only set; In Galaxy figure kth bunch be connected between s bunch of two nodes condition judgment time, be also to a
is-a
jsdo mould q computing to judge whether again to belong to set X or X '.
4., based on the method for routing of the extensive interconnection network topological structure of low diameter flexibly of the exponent number described in claim 1-3, it is characterized in that, search message from routing node (a
i0a
i1a
ika
i (n-1), k, t
1) to object terminal (a
j0a
j1a
jka
j (n-1), s, t
2, route c) comprises following steps, wherein t
1and t
2be respectively the numbering of routing node in super routing node, 0≤t
1≤ a-1,0≤t
2≤ a-1, t
1, t
2be integer:
(1) whether the routing node detecting current routing node and object terminal place is same routing node:
If so, then using object terminal as next-hop node, path finding terminates;
If not, then step (2) is entered;
(2) routing node at current routing node and object terminal place is detected whether in same super routing node:
If so, then using object routing node as next-hop node; Enter step (1);
If not, then step (3) is entered;
(3) detect the super routing node at current routing node place whether to be connected with the super routing node at the place of object terminal:
If so, the routing node be then connected by super to current super routing node and object routing node is as down hop; Enter step (1);
If not, then step (4) is entered;
(4) find the public super routing node with current super routing node and the super routing node of object, the routing node be then connected with public super routing node by current super routing node, as down hop, enters step (1).
5. the method for routing of the exponent number as claimed in claim 4 extensive interconnection network topological structure of low diameter flexibly; it is characterized in that; in described step (1), whether the routing node detecting current routing node and object terminal place is same routing node, and method is as follows:
Detect the routing node (a at current message place
i0a
i1a
ika
i (n-1), k, t
1) and object terminal (a
j0a
j1a
jka
j (n-1), s, t
2, the c) routing node (a at place
j0a
j1a
jka
j (n-1), s, t
2) whether be same routing node, namely detect and whether meet a
ik=a
jk, k=s and t
1=t
2;
If a
ik=a
jk, k=s and t
1=t
2, show that the routing node at message place and the routing node at object terminal place are same routing node, then by object terminal (a
j0a
j1a
jka
j (n-1), s, t
2, c) as next-hop node, path finding terminates;
Otherwise, a
ik≠ a
jkor k ≠ s or t
1≠ t
2, show that the routing node at message place and the routing node at object terminal place are not same routing node, enter step (2).
6. the method for routing of the exponent number as claimed in claim 4 extensive interconnection network topological structure of low diameter flexibly; it is characterized in that; in described step (2), detect the routing node at current routing node and object terminal place whether in same super routing node, method is as follows:
Routing node (a at detection messages place
i0a
i1a
ika
i (n-1), k, t
1) and the routing node (a at object terminal place
j0a
j1a
jka
j (n-1), s, t
2) whether in same super routing node, namely detect and whether meet a
ik=a
jkand k=s;
If a
ik=a
jkand k=s, show that the routing node at the routing node at message place and object terminal place is in same super routing node, then by the routing node (a at object terminal place
j0a
j1a
jka
j (n-1), s, t
2) as next-hop node, go to step (1);
Otherwise, a
ik≠ a
jkor k ≠ s, show that the routing node at the routing node at message place and object terminal place is not in same super routing node, then enter step (3).
7. the method for routing of the exponent number as claimed in claim 4 extensive interconnection network topological structure of low diameter flexibly; it is characterized in that; in described step (3); whether detect the super routing node at current routing node place to be connected with the super routing node at the place of object terminal, method is as follows:
If k<s and a
is=a
jk, enter step (3.1); If k=s and a
js-a
is∈ X, enters step (3.2); If k>s and a
is=a
jk, enter step (3.3); Otherwise the condition of step (3.1), (3.2), (3.3) does not all meet, show that the super routing node at message place is not connected with the super routing node at object terminal place, go to step (4);
(3.1) k<s and a
is=a
jk, show that the super routing node at message place is connected with the super routing node at object terminal place; If the routing node (a at message place
i0a
i1a
ika
i (n-1), k, t
1) and the super routing node (a of object
j0a
j1a
jka
j (n-1), s) connected routing node
being same routing node is
wherein
for lower floor operation, then routing node
as down hop, enter step (1); If
then by the super routing node (a at message place
i0a
i1... a
ik... a
i (n-1), k) with the super routing node (a of object
j0a
j1... a
jk... a
j (n-1), s) connected routing node
as down hop, enter step (1);
(3.2) k=s and a
js-a
is∈ X, shows that the super routing node at message place is connected with the super routing node at object terminal place; If the routing node (a at message place
i0a
i1a
ika
i (n-1), k, t
1) and the super routing node (a of object
j0a
j1... a
jk... a
j (n-1), s) connected routing node
being same routing node is
wherein Δ is a
js-a
isthe value of mould q is gathering the sequence number sorted from small to large in X, then routing node
as down hop, wherein λ is a
is-a
jsthe value of mould q, gathering the sequence number sorted from small to large in X, enters step (1); If
then by the super routing node (a at message place
i0a
i1... a
ik... a
i (n-1), k) with the super routing node (a of object
j0a
j1... a
jk... a
j (n-1), s) connected routing node
as down hop, enter step (1);
(3.3) k>s and a
is=a
jk, show that the super routing node at message place is connected with the super routing node at object terminal place; If the routing node (a at message place
i0a
i1a
ika
i (n-1), k, t
1) and the super routing node (a of object
j0a
j1... a
jk... a
j (n-1), s) connected routing node
being same routing node is
then routing node
as down hop, enter step (1); If
then by the super routing node (a at message place
i0a
i1... a
ik... a
i (n-1), k) with the super routing node (a of object
j0a
j1... a
jk... a
j (n-1), s) connected routing node
as down hop, enter step (1).
8. the method for routing of the exponent number as claimed in claim 4 extensive interconnection network topological structure of low diameter flexibly; it is characterized in that; in described step (4); find the public super routing node with current super routing node and the super routing node of object; then the routing node be connected with public super routing node by current super routing node is as down hop, and concrete steps are as follows:
Find the super routing node (a with message place
i0a
i1... a
is... a
i (n-1), k) with the super routing node (a of object
j0a
j1... a
jk... a
j (n-1), public super routing node s), finding method is as follows: if k<s, enters step (4.1); If k=s, enter step (4.2); If k>s, enter step (4.3);
(4.1) if a
is-a
jk∈ X, enters step (4.1.1); If a
is-a
jk∈ X ', enters step (4.1.2);
(4.1.1) a
is-a
jk∈ X, shows that the public super routing node of the super routing node at message place and the super routing node at object terminal place is in kth bunch, then meet a
ls=a
jksuper routing node (a
l0a
l1... a
ls... a
l (n-1), k) be public super routing node, wherein 0≤l≤q-1, l is integer;
If the routing node (a at message place
i0a
i1a
ika
i (n-1), k, t
1) and public super routing node (a
l0a
l1... a
lk... a
l (n-1), k) connected routing node
being same routing node is
wherein Δ is a
lk-a
ikthe value of mould q is gathering the sequence number sorted from small to large in X, then routing node
as down hop, wherein λ is a
ik-a
lkthe value of mould q, gathering the sequence number sorted from small to large in X, enters step (1);
If
then by the super routing node (a at message place
i0a
i1... a
is... a
i (n-1), k) with public super routing node (a
l0a
l1... a
ls... a
l (n-1), k) connected routing node
as down hop, wherein Δ is a
lk-a
ikthe value of mould q, gathering the sequence number sorted from small to large in X, enters step (1);
(4.1.2) a
is-a
jk∈ X ', shows that the public super routing node of the super routing node at message place and the super routing node at object terminal place is in s bunch, then meet a
is=a
lksuper routing node (a
l0a
l1... a
lk... a
l (n-1), s) be public super routing node, wherein 0≤l≤q-1, l is integer;
If the routing node (a at message place
i0a
i1a
isa
i (n-1), k, t
1) and public super routing node (a
l0a
l1... a
lk... a
l (n-1), s) connected routing node
being same routing node is
then routing node
as down hop, enter step (1);
If
then by the super routing node (a at message place
i0a
i1... a
ik... a
i (n-1), k) with public super routing node (a
l0a
l1... a
lk... a
l (n-1), s) connected routing node
as down hop, enter step (1);
(4.2) by order traversal kth bunch all super routing node (a from big to small
l0a
l1... a
lk... a
l (n-1), k) meet a
lk-a
ik∈ X and a
jk-a
lkthe minimum value of ∈ X, then super routing node (a
l0a
l1... a
ls... a
l (n-1), k) be public super routing node, wherein 0≤l≤q-1, l is integer;
If the routing node (a at message place
i0a
i1a
isa
i (n-1), k, t
1) and public super routing node (a
l0a
l1... a
ls... a
l (n-1), k) connected routing node
being same routing node is
wherein Δ is a
lk-a
ikthe value of mould q is gathering the sequence number sorted from small to large in X, then routing node
as down hop, wherein λ is a
ik-a
lkthe value of mould q, gathering the sequence number sorted from small to large in X, enters step (1);
If
then by the super routing node (a at message place
i0a
i1... a
ik... a
i (n-1), k) with public super routing node (a
l0a
l1... a
lk... a
l (n-1), k) connected routing node
as down hop, wherein Δ is a
lk-a
ikthe value of mould q, gathering the sequence number sorted from small to large in X, enters step (1);
(4.3) if a
is-a
jk∈ X, enters step (4.3.1); If a
is-a
jk∈ X ', enters step (4.3.2);
(4.3.1) a
is-a
jk∈ X, shows that the public super routing node of the super routing node at message place and the super routing node at object terminal place is in s bunch, then meet a
lk=a
issuper routing node (a
l0a
l1... a
lk... a
l (n-1), s) be public super routing node, wherein 0≤l≤q-1, l is integer;
If the routing node (a at message place
i0a
i1a
isa
i (n-1), k, t
1) and public super routing node (a
l0a
l1... a
lk... a
l (n-1), s) connected routing node
being same routing node is
then routing node
as down hop, enter step (1);
If
then by the super routing node (a at message place
i0a
i1... a
is... a
i (n-1), k) with public super routing node (a
l0a
l1... a
lk... a
l (n-1), s) connected routing node
as down hop, enter step (1);
(4.3.2) a
is-a
jk∈ X ', shows that the public super routing node of the super routing node at message place and the super routing node at object terminal place is in kth bunch, then meet a
ls=a
jksuper routing node (a
l0a
l1... a
lk... a
l (n-1), k) be public super routing node, wherein 0≤l≤q-1, l is integer;
If the routing node (a at message place
i0a
i1a
ika
i (n-1), k, t
1) and public super routing node (a
l0a
l1... a
lk... a
l (n-1), k) connected routing node
being same routing node is
wherein Δ is a
lk-a
ikthe value of mould q is gathering the sequence number sorted from small to large in X, then routing node
as down hop, wherein λ is a
ik-a
lkthe value of mould q is gathering the sequence number sorted from small to large in X, and λ is integer and sorts from 0, enters step (1);
If
then by the super routing node (a at message place
i0a
i1... a
is... a
i (n-1), k) with public super routing node (a
l0a
l1... a
lk... a
l (n-1), k) connected routing node
as down hop, wherein Δ is a
lk-a
ikthe value of mould q is gathering the sequence number sorted from small to large in X, and Δ is integer and sorts from 0, enters step (1).
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201610040721.4A CN105471749B (en) | 2016-01-21 | 2016-01-21 | The exponent number flexibly extensive interconnection network topological structure of low diameter and method for routing |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201610040721.4A CN105471749B (en) | 2016-01-21 | 2016-01-21 | The exponent number flexibly extensive interconnection network topological structure of low diameter and method for routing |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN105471749A true CN105471749A (en) | 2016-04-06 |
| CN105471749B CN105471749B (en) | 2018-06-26 |
Family
ID=55609042
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201610040721.4A Active CN105471749B (en) | 2016-01-21 | 2016-01-21 | The exponent number flexibly extensive interconnection network topological structure of low diameter and method for routing |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN105471749B (en) |
Cited By (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN108462632A (en) * | 2016-12-09 | 2018-08-28 | 湖南工程学院 | A kind of trunk path extracting method of directed complex networks |
| CN109189720A (en) * | 2018-08-22 | 2019-01-11 | 曙光信息产业(北京)有限公司 | Stratification Survey on network-on-chip topology and its method for routing |
| CN109327255A (en) * | 2018-09-26 | 2019-02-12 | 中国民航管理干部学院 | A kind of method for routing and system for unmanned plane ad hoc network |
| CN110062301A (en) * | 2019-01-23 | 2019-07-26 | 中通服咨询设计研究院有限公司 | Route selection method, device, equipment and storage medium |
| CN111030927A (en) * | 2019-11-20 | 2020-04-17 | 中国人民解放军国防科技大学 | Network-on-chip routing method and network router with sequential perception |
| CN112988651A (en) * | 2021-05-12 | 2021-06-18 | 北京壁仞科技开发有限公司 | Computing system, computing processor, and data processing method |
| CN113271267A (en) * | 2021-05-18 | 2021-08-17 | 清华大学 | Interconnection network, adaptive routing method, apparatus, electronic device, and storage medium |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20140064287A1 (en) * | 2012-08-29 | 2014-03-06 | Oracle International Corporation | System and method for supporting discovery and routing degraded fat-trees in a middleware machine environment |
| CN103907322A (en) * | 2011-11-09 | 2014-07-02 | 甲骨文国际公司 | System and method for providing deadlock free routing between switches in a fat-tree topology |
-
2016
- 2016-01-21 CN CN201610040721.4A patent/CN105471749B/en active Active
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN103907322A (en) * | 2011-11-09 | 2014-07-02 | 甲骨文国际公司 | System and method for providing deadlock free routing between switches in a fat-tree topology |
| US20140064287A1 (en) * | 2012-08-29 | 2014-03-06 | Oracle International Corporation | System and method for supporting discovery and routing degraded fat-trees in a middleware machine environment |
Non-Patent Citations (2)
| Title |
|---|
| MACIEJ BESTA AND TORSTEN HOEFLER: ""Slim fly: A cost effective"", 《INTERNATIONAL CONFERENCE FOR HIGH PERFORMANCE COMPUTING, NETWORKING, STORAGE AND ANALYSIS》 * |
| 雷斐，董德尊，廖湘科: ""SuperStar：一种可扩展高阶互连拓扑结构"", 《计算机工程与科学》 * |
Cited By (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN108462632A (en) * | 2016-12-09 | 2018-08-28 | 湖南工程学院 | A kind of trunk path extracting method of directed complex networks |
| CN108462632B (en) * | 2016-12-09 | 2020-07-14 | 湖南工程学院 | Backbone path extraction method for directed complex network |
| CN109189720A (en) * | 2018-08-22 | 2019-01-11 | 曙光信息产业(北京)有限公司 | Stratification Survey on network-on-chip topology and its method for routing |
| CN109327255A (en) * | 2018-09-26 | 2019-02-12 | 中国民航管理干部学院 | A kind of method for routing and system for unmanned plane ad hoc network |
| CN110062301A (en) * | 2019-01-23 | 2019-07-26 | 中通服咨询设计研究院有限公司 | Route selection method, device, equipment and storage medium |
| CN111030927A (en) * | 2019-11-20 | 2020-04-17 | 中国人民解放军国防科技大学 | Network-on-chip routing method and network router with sequential perception |
| CN112988651A (en) * | 2021-05-12 | 2021-06-18 | 北京壁仞科技开发有限公司 | Computing system, computing processor, and data processing method |
| CN113271267A (en) * | 2021-05-18 | 2021-08-17 | 清华大学 | Interconnection network, adaptive routing method, apparatus, electronic device, and storage medium |
Also Published As
| Publication number | Publication date |
|---|---|
| CN105471749B (en) | 2018-06-26 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN105471749A (en) | Order-flexible low diameter large scale interconnection network topological structure and routing method thereof | |
| Chen et al. | The features, hardware, and architectures of data center networks: A survey | |
| US9674116B2 (en) | Data distribution packet-flow interconnect fabric modular management optimized system | |
| US10303640B2 (en) | Method and apparatus to manage the direct interconnect switch wiring and growth in computer networks | |
| Besta et al. | Slim fly: A cost effective low-diameter network topology | |
| Mo et al. | A hierarchical hybrid optical-electronic network-on-chip | |
| Guo et al. | Low insertion loss and non-blocking microring-based optical router for 3D optical network-on-chip | |
| CN105138493B (en) | Non-exchanger network construction system and method suitable for parallel operation | |
| Wu et al. | An inter/intra-chip optical network for manycore processors | |
| CN104052663A (en) | Large-scale on-chip chip interconnecting method and routing algorithm for realizing interconnecting structure | |
| Lv et al. | Fault diagnosis based on subsystem structures of data center network BCube | |
| KR102171890B1 (en) | Computing system framework with unified storage, processing, and network switching fabrics incorporating network switches and method for making and using the same | |
| Truong et al. | Hybrid electrical/optical switch architectures for training distributed deep learning in large-scale | |
| CN103986670A (en) | Method for obtaining performance of optical switch chip | |
| CN104486212B (en) | Three-dimensional plate glazing network topology and routing path calculation method | |
| Cai et al. | Design and OPNET implementation of routing algorithm in 3D optical network on chip | |
| CN108768864B (en) | Data center network topology system easy to expand and high in fault tolerance | |
| Aggarwal | Design and performance evaluation of a new irregular fault-tolerant multistage interconnection network | |
| KR102691170B1 (en) | Technology of flexiblex interconnect topology and packet controlling method in host network with silicon-photonics interface for high-performance computing | |
| Xingyun et al. | A fault tolerant bufferless optical interconnection network | |
| Jahanshahi et al. | Interconnection Networks | |
| Kochar et al. | nD-RAPID: a multidimensional scalable fault-tolerant optoelectronic interconnection for high-performance computing systems | |
| CN107104909B (en) | Fault-tolerant special network-on-chip topology generation method | |
| Soni et al. | An efficient and improved algorithm for generating an equivalent planar architecture of the data vortex switch | |
| Li et al. | Accelerate Distributed Deep Learning with a Fast Reconfigurable Optical Network |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |