Title :
Source Misrouting in King Topologies
Author :
Stafford, E. ; Martinez, C. ; Bosque, Jose Luis ; Vallejo, Fernando ; Camarero, Cristobal ; Perez, Borja ; Beivide, Ramon
Author_Institution :
Univ. of Cantabria, Santander, Spain
Abstract :
King networks were proposed as higher degree alternatives to 2D tori and meshes. These networks offer improved throughput and latency with minimum distance routing in benign traffic patterns. As a solution to performance problems in adverse traffic pattern of the minimal routing, this article presents a misrouting solution. It uses two parameters to control the generation of routing tables. Using the paths on these tables, packets reach their destination nodes through non-minimal paths, without deadlock, live lock or starvation. Optimal values for the parameters are empirically determined. This routing strategy slightly improves the throughput while hardly increasing the base latency and extending the linear behaviour of the network. Experimental results confirm the good properties of this algorithm compared to minimal routing and Valiant algorithms.
Keywords :
multiprocessor interconnection networks; network routing; network topology; 2D mesh; 2D tori; Valiant algorithm; distance routing; king network; king topology; minimal routing; misrouting solution; nonminimal path; routing strategy; routing table; source misrouting; traffic pattern; Algorithm design and analysis; Bandwidth; Network topology; Routing; System recovery; Throughput; Topology;
Conference_Titel :
High Performance Computing and Communications, 2014 IEEE 6th Intl Symp on Cyberspace Safety and Security, 2014 IEEE 11th Intl Conf on Embedded Software and Syst (HPCC,CSS,ICESS), 2014 IEEE Intl Conf on
Print_ISBN :
978-1-4799-6122-1
DOI :
10.1109/HPCC.2014.78
