Hindi Kavita Ki Sanrachana: Ek Vivechana

A key advantage of optical logic devices is that they are faster than their electronic counterparts [11]. The no availability of static random access optical memory devices and the restrictions associated with traveling-wave optical buffers means that optical domain buffering should be minimized or, if possible, avoided altogether. The MSN with the Clockwork Routing scheme is well suited for use in optical packet-switched networks for a number of reasons: the routing processing is extremely simple and suitable for optical implementation, no optical domain buffering is required, no resequencing is needed at the destination nodes, and throughput is comparable with conventional store-and-forward packet switching [9], [10]. Clockwork Routing requires that all the nodes in an MSN be synchronized to a global clock. The timeslots are arranged in a modulo- sequence of frames. Each node consists of a simple cross-bar switch. All nodes are in the cross state for the first timeslots in each timeframe and in the bar state for the last timeslot in the timeframe. By correctly inserting a packet into a timeslot on a particular output link, it is automatically routed to the destination. No additional processing or buffering is required at intermediate nodes; these nodes need only determine whether the packet has reached its destination or not. Such a simple “for me or not for me” evaluation may be readily implemented in the optical domain [11]. Packet contention in the optical

A key research issue is how the MSN, or for that matter any other multiprocessor interconnection architecture, may be deployed (or embedded) optimally in arbitrary physical topologies. The fact that WDM and wavelength selective devices allow a logical interconnection of nodes that may differ from the physical topology may be exploited to deploy the architectures as regular virtual topologies in arbitrary physical topologies. The virtual topology connectivity is realized by establishing WDM channels, light paths, between appropriate nodes in the physical topology. Two different approaches may be adopted when designing a virtual topology in a wavelength routed network. First, the connectivity of the virtual topology is predefined, and the design problem is to embed this connectivity pattern in the physical topology optimally. In the alternative, the virtual topology connectivity is discretionary and is, in fact, the design output. In the latter approach, the traffic matrix is an important optimization input, and its impact on the design process has been studied extensively. This paper, however, considers the first case of deploying a regular virtual topology optimally in a physical topology; if the MSN is the regular topology, optical domain contentions are avoided, and optical logic devices may be used to switch packets at light path terminals. In such a scenario, the impact of the traffic matrix on the virtual topology design is somewhat more ambiguous; some design approaches assume the traffic matrix is important [4], whereas others disregard it altogether [5]. This paper addresses this ambivalence by comparing solutions obtained with and without the traffic matrix.

Initially, each heuristic was used to find the mappings of the MSN nodes onto the physical topology that minimize the mean light path length. Each mapping will produce a certain traffic weighted embedded intermodal distance for a given traffic matrix. This value was compared with the corresponding value when the heuristics were applied to both node placement optimization and the optimization of the traffic-weighted embedded intermodal distances directly. The some specific traffic scenarios are now discussed.

Thus far, elements of the traffic matrix have been chosen from a uniform random distribution. The impact, if any, of a no uniformly distributed traffic matrix is now investigated. Five different PDFs, in addition to the uniformly distributed case, were considered can be seen that PDF ‘F’ means that

In this case, the volume of traffic exchanged by nodes is generated from a uniform random distribution between 1 and A.A was varied from 10 to 100 in increments of 10.

Five different heuristics are used to find (near-) optimal mappings of the regular virtual topology nodes onto the physical topology nodes: hill climbing (HC), random search (RS), simulated annealing (SA), and two different implementations of genetic algorithms (GA). HC attempts to improve on a randomly chosen initial embedding by accepting moves in the neighborhood of the current solution that improve the cost. In the RS implementation, numerous randomly generated mappings of the MSN onto the physical topology are generated, and the best is chosen. SA is basically a search algorithm that allows uphill moves with a regulated and decreasing probability, allowing escape from local minima and, hopefully, encouraging convergence on the global minimum. SA was chosen since it has been previously successfully used for deploying regular virtual topologies in arbitrary physical topologies [4]. Note that in order to allow a fairer comparison, the same initial embedding was used for SA, HC, and RS, and the implementation ensured that all explored an identical number of possible embedding. GAs is a family of adaptive computational models inspired by evolution in nature. GAs has been applied to a plethora of complex mathematical problems and to the deployment of the MSN in arbitrary physical topologies in [12]. Four different implementations of GAs were compared in [12] and the best two implementations chosen and used in this paper. The two techniques are known as partially mapped crossover (PMX) and cycle crossover (CX).

The paper has addressed the important theme of designing multi-hop regular virtual topologies for optical packet switching in networks with arbitrary topologies. The MSN with the Clockwork Routing scheme is well suited to optical packet switching and so has been used as an exemplar regular topology. Due to the intractable nature of the virtual topology design problem, five alternative AI-based optimization heuristics are employed to find (near-) optimal solutions expeditiously. The virtual topology design problem is decomposed into two sub problems dilation minimization and node placement optimization which, respectively, use only the physical topology and virtual topology or the virtual topology and traffic matrix as optimization inputs. These sub problems are compared with each other and the results of tackling the overarching problem directly under a variety of

counterintuitive observations may be made from results presented in this paper. First, dilation minimization typically outperformed node placement optimization. Hence, it may be concluded that it is of greater benefit to ensure that all virtual topology links are dilated by the minimum distance in the physical topology than to ensure that nodes that exchange a relatively large volume of traffic are near each other in the virtual topology. In node placement optimization, the number of intermediate light paths is minimized, but the (suboptimal) embedding within the physical topology will result in arbitrarily large light path lengths; hence, the final cost will be far from optimal. Second, the fact that dilation minimization results were comparable to the best overall results suggests that it is possible to design the regular virtual topology without using the traffic matrix, and yet the solution is near optimal for a range of traffic scenarios and would thus be immune to traffic condition.

[1] M. G. Hluchyj and M. J. Karol, “Shufflenet: An application of generalized perfect shuffles to multihop lightwave networks,” J. Lightwave Technol., vol. 9, pp. 1386–1397, Oct. 1991. [2] B. Mukherjee, “WDM-based lightwave networks—Part II: Multihop systems,” IEEE Network, pp. 20–31, July 1992. [3] K. N. Sivarajan and R. Ramaswami, “Lightwave networks based on de Bruijn graphs,” IEEE/ACM Trans. Networking, vol. 2, pp. 70–79, Feb. 1994. [4] B. Mukherjee, S. Ramamurthy, D. Banerjee, and A. Mukherjee, “Some principles for designing a wide-area optical network,” in Proc. IEEE Infocom, 1994, pp. 110–119. [5] I. Chlamtac, A. Ganz, and G. Karmi, “Lightnets: Topologies for highspeed optical networks,” J. Lightwave Technol., vol. 11, pp. 951–961, May/June 1993. [6] N. F. Maxemchuk, “The Manhattan Street Network,” in Proc. IEEE Globecom, 1985. [7] “Routing in the Manhattan Street Network,” IEEE Trans. Commun., vol. Com-35, pp. 503–512, May 1987. [8] C. P. Ravikumar, T. Rai, and V. Verma, “Kautz graphs as attractive logical topologies in multihop lightwave networks,” Comput. Commun., vol. 20, pp. 1259–1269, 1997. [10] “Routing and fairness issues associated with a self-routing control strategy in regular mesh photonic networks,” in Proc. Int. Teletraffic Conf., June 1999, pp. 1301–1310. [11] D. Cotter et al., “Nonlinear optics for high-speed digital information processing,” Science, vol. 286, pp. 1523–1528, Nov. 1999. [12] O. Komolafe, D. Harle, and D. Cotter, “Optical packet switching over arbitrary physical topologies using the Manhattan Street Network: An evolutionary approach,” in Proc. IFIP Conf. Optical Network Design Modeling, Feb. 2001