An Efficient Monarchic Reconfiguration Protocol with Deadlock Freedom on Interconnection Networks

Monarchic Reconfiguration protocol (MRP) is the selfgoverning, independent and autonomous system to resolve the deadlocking problem during reconfiguration in interconnection networks. Deadlock is the cyclic dependency between the old and new routing functions. Our aim is to protect the routing path with deadlocking freedom and improve the performance drastically. Our proposed method will increase the availability and dependability of the network and reduce 100 % pocket drops ratio with deadlock freedom. 1. INTERCONNECTION NETWORKS High-performance interconnection networks comprise the communication backbone in digital systems at several system levels. At the higher system levels, local-area networks (LANs) are used in clusters of PCs, networks of workstations and other distributed processing systems which serve as cost/performance effective alternatives to tightly-coupled massively parallel processing systems. System-area networks (SANs) are used for interconnecting processors, memories, and I/O devices in systems with the primary goal of increasing reliability in the presence of link/router failures. Storage-area networks (STANs)[1]are used to increase performance and reliability of large disk arrays by offering access to stored data by processors through multiple paths, thus providing continued service in the presence of processor failure. Internet protocol router fabric (IPRF) networks are used within IP routers to handle IP traffic at high (multi gigabit) sustained line rates. Server I/O(SIO) and inter processor communication (IPC) [2,3] networks are used to overcome many of the scalability limitations of multi chip bus-based systems, allowing high-speed interconnections between memory controllers and I/O devices, direct access to disk from LAN adapters, and concurrent communication between processors, memories and I/O devices in multiprocessors. Likewise, at lower levels, networks-on-chip (NOCs) [4,5,6]are used to overcome many of the performance limitations of bus-based systems at the chip level. Parallel computing and communication systems built from the above networks require high-performance communication services [7] with high reliability, availability and dependability collectively, high robustness. The performance [8] of the interconnection network is measured, in part, by packet delivery time[9] from source to destination (i.e., latency) and by the number of packets delivered per unit time (i.e., throughput). In essence, a high-performance network allows the maximum number of packets to make forward progress to their destinations in minimal time, preferably along shortest paths [10] to preserve network bandwidth. Likewise, the reliability, availability and dependability of a network equally impact the overall goodness (quality of a system). These attributes are measured, in part, by the network's ability to remain up and running at near normal levels even when events occur which change its configuration, possibly due to changes in users' needs and/or system state. Such reconfiguration events may include, for example, hot-swapping of components, failure or addition of links/nodes, activation or deactivation of hosts/routers, etc., in a LAN [24] environment. Since network resources are finite and, ultimately, are contended for, structural hazards on those resources are inevitable which delay or prevent packet transmission in the network. This occurs even in networks that feature advanced router architectures. Such hazards cause packets to block which, eventually, can lead to network congestion and, possibly, deadlock. One of the more critical problems to be addressed in order to achieve high network performance and robustness is that of efficiently handling deadlock anomalies. The rest of the paper organized as follows. Section 2 provides the idea description about the proposed system. Section 3 describes the related work about the system. Section 4 deals with limitations of reconfiguration. Section 5 provides network model and assumption related to the proposed system and also this section introduces the concept of Monarchic Reconfiguration Protocol (MRP). 1.1. Network and Router Model Direct networks consist of a set of nodes interconnected by point-to-point links or channels. No restriction is imposed on the topology of the interconnection network. Each node has a router. We assume that the switch is a crossbar, therefore allowing multiple packets [11] to traverse a node simultaneously without interference. The routing and arbitration unit configures the switch [12], determining the output channel for each packet as a function of the destination node, the current node, and the output channel status. The routing and arbitration unit can only process one packet header at a time. If there is contention for this unit, access is round-robin[13]. When a packet gets the routing and arbitration unit but cannot be routed because all the valid output channels are busy, it waits in the corresponding input buffer until its next turn. By doing so, the packet gets the first valid channel that becomes available when it is routed again. This strategy achieves a higher routing flexibility than strategies in which blocked packets wait on a single predetermined channel. Physical channels [14] are bidirectional full duplex. Physical channels may be split into virtual channels. Virtual channels are assigned the physical channel cyclically, only if they are ready to transfer a flit [21](demand-slotted round-robin). Fig 1 shows the basic router model . The interconnection network I is modeled by using a strongly connected directed graph with multiple arcs, I = G(N, C). The International Journal of Computer Applications (0975 – 8887) Volume 43– No.9, April 2012 2 Routing and Arbitration Injection Channel Ejection Channel Fig. 1 A basic router Model vertices of the graph N represent the set of processing nodes. The arcs of the graph C represent the set of communication channels. More than a single channel is allowed to connect a given pair of nodes. Bidirectional channels [15] are considered as two unidirectional channels. We will refer to a channel and its associated edge buffer indistinctly. The source and destination nodes of a channel ci are denoted si and di respectively. A routing algorithm is modeled by means of two functions: routing and selection. The routing function [16] supplies a set of output channels based on the current and destination nodes. A selection from this set is made by the selection function [17] based on the status of output channels at the current node. This selection is performed in such a way that a free channel (if any) is supplied. If all the output channels are busy, the packet will be routed again until it is able to reserve a channel, thus getting the first channel that becomes available. As we will see, the routing function determines whether the routing algorithm is deadlock-free or not. The selection function only affects performance.