User:Smscoggi/sandbox
 | This is a user sandbox of Smscoggi. You can use it for testing or practicing edits. This is not the sandbox where you should draft your assigned article for a dashboard.wikiedu.org course. To find the right sandbox for your assignment, visit your Dashboard course page and follow the Sandbox Draft link for your assigned article in the My Articles section. |
Dimension-Ordered(e-cube) Routing
[edit]Introduction
[edit]Dimensional Ordered Routing or e-cube routing is a popular routing algorithm that ensures that a packet will take the shortest path, and is therefore deterministic. There are various algorithms used to determine paths for packets to take between nodes in an interconnection network. Using this algorithm, packets must travel completely in one dimension at a time and not return to already completed dimensions. For example: If a network uses x-y-z ordering, and a packet A needs to go from node (0,0,0) to node (1,2,3), it will first travel 1 node in the x direction, 2 nodes in the y direction, and 3 nodes in the z direction. If it is z-x-y ordering, the packet will travel 3 in the z direction first. Once the packet makes a turn (switches dimension), it cannot turn back into traveling for that dimension. [1]
Key Uses of Dimension-Ordering
[edit]Dimension-ordered routing is used for mesh and hypercube topologies in shared memory multiprocessors.[1]
In a hypercube where each dimension has two nodes (binary d-dimensional mesh), dimension-ordered or e-cube routing in this case is known as deadlock free[2]. It uses bit strings as coordinates for both source and receiver. Each string is compared bit by bit, and the packet travels through the dimensions one at a time until there is no difference in the bit string. So, a packet starting at node (1,1,1) needs to get to (1,0,0). In x-y-z ordering, this packet will move from (1,1,1) to (1,0,1) and then (1,0,0). After each hop, the current node bit string is compared to the receiving node's bit string.[3] The fact that there is a specific ordering to the dimensions traveled too will make this algorithm deterministic, where the same path is used for all packets traveling between a specific pair of nodes.[2]
In meshes, or more generally k-ary n-cubes, dimension-ordered routing needed to add virtual channels in order to become deadlock free. Virtual channels alternate between high and low for each dimension in a path. So a packet traveling in one dimension would be in a low channel, and once it switches to the next dimension it will then be in a high channel, continuing the cycle until the packet reaches its destination.[3] This implementation came from Dally and Sietz[4]
Modifications
[edit]- 01turn Routing- Out of the different orders of dimensions a packet could travel (xyz, zyx,..), intstead of having a fixed ordering of dimensions, the order would be chosen randomly when using 01turn routing. This was to mitigate the latency packets experience when there are overused nodes and paths, in a completely deterministic system. [1]
- Valiant Routing- In order to help path diversity, a random node is selected to be an "intermediary node." The path the packet takes to its source must go through this node. Valiant Routing would sacrifice guaranteeing the packet taking the shortest route.[1]
- Fully adaptive routing assistance- Though, dimension-ordered routing is oblivious, not adaptive, it can be a backup for adaptive algorithms that run into problems acquiring adaptive channels.[5]
Advantages and Disadvantages
[edit]Advantages[1]
- Deadlock free- It is imperative that deadlocks be avoided or prevented. Packets that get caught in cyclic paths that never reach their destination can be costly to repair. Because hypercube topologies prevent cyclic turnaround, and meshes can use virtual channels to guide routing. Dimension-ordered routing has been proven to be deadlock-free. [4]
- Simple- This is an easy to implement routing algorithm that only requires that packets travel shortest distance in one direction at a time.[1]
- Easily modified- As shown in the Modifications section, though it is not an extensive list, there are modifications that can be made to expand, loosen, and change properties of the algorithm to fit what is needed, such as better path-diversity and less contention. The algorithm's simplicity aids this.[1]
- Minimal- Minimal routing ensures that the shortest route is always taken to the receiving node. Because of the nature of the Dimension-Ordered algorithm, traveling in one dimension at a time in some order, this routing algorithm is minimal. Always requiring a packet to take the shortest route has it's advantage in simplicity, and in minimizing hops to the receiver. So, transactions, if not met with congestion, or heavily used paths, will be fast and efficient.[1]
- Oblivious- Oblivious routing algorithms do not choose routes based on the state of the network. As in, if there is contention along a certain path, the algorithm cannot choose a different path to accommodate faster transactions. Since Dimension-Ordered routing is minimal, rerouting to a longer path is not allowed, therefore it is Oblivious. However, this serves as an advantage, as a packet will not fall into the traps that an adaptive routing algorithm might, like lifelock, where a packet floats around the network, not trapped in a cycle like deadlock, but constantly finding alternate routes, but never making it to the receiving node.[5][1]
Disadvantages[1]
- Deterministic-Always requiring the shortest distance in addition to traveling in a strict order of dimensions (for x-y-z, all packets travel in first in x, then y, then z directions), routes will always be the same between two nodes. This is a disadvantage because if ports or pathways are highly used, paths cannot take alternate paths to avoid it. There is also a lack of path utilization and fault tolerance. If some part of a path becomes disabled or unusable, all packets that need to use that link or port will not reach its intended destination.[1]
- High contention in highly used nodes and paths- Because this algorithm is deterministic, it is vulnerable to high contention. This will cause high latency and will create overhead canceling out any efficiency gained by the algorithm being minimal.[1]
- Lack of fault tolerance- When one route is always taken, if that route goes down, the packet cannot get through, and will be eventually dropped. [1]
Similar Pages
[edit]References
[edit]- ^ a b c d e f g h i j k l m Solihin, Yan (2016). Fundamentals of Parallel Multicore Architecture. Boca Raton, FL: CRC Press. p. 383-385. ISBN 978-1-4822-1118-4.
- ^ a b Gaughan, Patrick T.;, Yalamanchili, Sudhakar (May 1993). "Adaptive routing protocols for hypercube interconnection networks". Computer. 26 (5). doi:10.1109/2.211888.
{{cite journal}}: CS1 maint: extra punctuation (link) CS1 maint: multiple names: authors list (link) - ^ a b H. Sarbazi-Azad, A. Khonsari, M. Ould-Khaoua (May 2003). "Analysis of k-ary n-cubes with dimension-ordered routing". Future Generation Computer Systems. 19 (4): 493-502.
{{cite journal}}: CS1 maint: multiple names: authors list (link) - ^ a b W. J. Dally and C. L. Seitz (May 1987). "Deadlock-Free Message Routing in Multiprocessor Interconnection Networks". IEEE Transactions on Computers. vol. C-36 (no. 5): pp. 547-553. doi:10.1109/TC.1987.1676939.
{{cite journal}}:|issue=has extra text (help);|page=has extra text (help);|volume=has extra text (help) - ^ a b José Duato, Sudhakar Yalamanchili, Lionel M. Ni (2003). Interconnection Networks: An Engineering Approach (illustrated, revised ed.). Morgan Kaufmann. p. 339. ISBN 9781558608528.
{{cite book}}: CS1 maint: multiple names: authors list (link)