Reducing Buffer Requirements in Core Routers using Dynamic Buffering

Earlier studies have exploited statistical multiplexing of flows in the core of the Internet to reduce the buffer requirement in routers. Reducing the memory requirement of routers is important as it enables an improvement in performance and at the same time a decrease in the cost. In this paper, we observe that the links in the core of the Internet are typically over-provisioned and this can be exploited to reduce the buffering requirement in routers. The small on-chip memory of a network processor (NP) can be effectively used to buffer packets during most regimes of traffic. We propose a dynamic buffering strategy which buffers packets in the receive and transmit buffers of a NP when the memory requirement is low. When the buffer requirement increases due to bursts in the traffic, memory is allocated to packets in the off-chip DRAM. This scheme effectively mitigates the DRAM access bottleneck, as only a part of the traffic is stored in the DRAM. We build a Petri net model and evaluate the proposed scheme with core Internet like traffic. At 77% link utilization, the dynamic buffering scheme has a drop rate of just 0.65%, whereas the traditional DRAM buffering has 4.64% packet drop rate. Even with a high link utilization of 90%, which rarely happens in the core, our dynamic buffering results in a packet drop rate of only 2.17%, while supporting a throughput of 7.39 Gbps. We study the proposed scheme under different conditions to understand the provisioning of processing threads and to determine the queue length at which packets must be buffered in the DRAM. We show that the proposed dynamic buffering strategy drastically reduces the buffering requirement while still maintaining low packet drop rates.

On Optimal Performance in Mobile Ad-Hoc Networks

In this paper we are concerned with finding the maximum throughput that a mobile ad hoc network can support. Even when nodes are stationary, the problem of determining the capacity region has long been known to be NP-hard. Mobility introduces an additional dimension of complexity because nodes now also have to decide when they should initiate route discovery. Since route discovery involves communication and computation overhead, it should not be invoked very often. On the other hand, mobility implies that routes are bound to become stale resulting in sub-optimal performance if routes are not updated. We attempt to gain some understanding of these effects by considering a simple one-dimensional network model. The simplicity of our model allows us to use stochastic dynamic programming (SDP) to find the maximum possible network throughput with ideal routing and medium access control (MAC) scheduling. Using the optimal value as a benchmark, we also propose and evaluate the performance of a simple threshold-based heuristic. Unlike the optimal policy which requires considerable state information, the heuristic is very simple to implement and is not overly sensitive to the threshold value used. We find empirical conditions for our heuristic to be near-optimal as well as network scenarios when our simple heuristic does not perform very well. We provide extensive numerical and simulation results for different parameter settings of our model.

Effect of strain path change on the evolution of texture and microstructure during rolling of copper and nickel

The effect of strain path change during rolling has been investigated for copper and nickel using X-ray diffraction and electron back scatter diffraction as well as crystal plasticity simulations. Four different strain paths namely: (i) unidirectional rolling; (ii) reverse rolling; (iii) two-step cross rolling and (iv) multi-step cross rolling were employed to decipher the effect of strain path change on the evolution of deformation texture and microstructure. The cross rolled samples showed weaker texture with a prominent Bs {1 1 0}< 1 1 2 > and P(B(ND)) {1 1 0}< 1 1 1 > component in contrast to the unidirectional and reverse rolled samples where strong S {1 2 3}< 6 3 4 > and Cu {1 1 2}< 1 1 1 > components were formed. This was more pronounced for copper samples compared to nickel. The cross rolled samples were characterized by lower anisotropy and Taylor factor as well as less variation in Lankford parameter. Viscoplastic self-consistent simulations indicated that slip activity on higher number of octahedral slip systems can explain the weaker texture as well as reduced anisotropy in the cross rolled samples. (C) 2011 Elsevier B.V. All rights reserved.

On the Limits of Spatial Reuse and Cooperative Communication for Dense Wireless Networks

We consider a dense ad hoc wireless network comprising n nodes confined to a given two dimensional region of fixed area. For the Gupta-Kumar random traffic model and a realistic interference and path loss model (i.e., the channel power gains are bounded above, and are bounded below by a strictly positive number), we study the scaling of the aggregate end-to-end throughput with respect to the network average power constraint, P macr, and the number of nodes, n. The network power constraint P macr is related to the per node power constraint, P macr, as P macr = np. For large P, we show that the throughput saturates as Theta(log(P macr)), irrespective of the number of nodes in the network. For moderate P, which can accommodate spatial reuse to improve end-to-end throughput, we observe that the amount of spatial reuse feasible in the network is limited by the diameter of the network. In fact, we observe that the end-to-end path loss in the network and the amount of spatial reuse feasible in the network are inversely proportional. This puts a restriction on the gains achievable using the cooperative communication techniques studied in and, as these rely on direct long distance communication over the network.

On the Production of Anorexic Plan Diagrams

A "plan diagram" is a pictorial enumeration of the execution plan choices of a database query optimizer over the relational selectivity space. We have shown recently that, for industrial-strength database engines, these diagrams are often remarkably complex and dense, with a large number of plans covering the space. However, they can often be reduced to much simpler pictures, featuring significantly fewer plans, without materially affecting the query processing quality. Plan reduction has useful implications for the design and usage of query optimizers, including quantifying redundancy in the plan search space, enhancing useability of parametric query optimization, identifying error-resistant and least-expected-cost plans, and minimizing the overheads of multi-plan approaches. We investigate here the plan reduction issue from theoretical, statistical and empirical perspectives. Our analysis shows that optimal plan reduction, w.r.t. minimizing the number of plans, is an NP-hard problem in general, and remains so even for a storage-constrained variant. We then present a greedy reduction algorithm with tight and optimal performance guarantees, whose complexity scales linearly with the number of plans in the diagram for a given resolution. Next, we devise fast estimators for locating the best tradeoff between the reduction in plan cardinality and the impact on query processing quality. Finally, extensive experimentation with a suite of multi-dimensional TPCH-based query templates on industrial-strength optimizers demonstrates that complex plan diagrams easily reduce to "anorexic" (small absolute number of plans) levels incurring only marginal increases in the estimated query processing costs.

l-pGlu-(2-propyl)-l-His-l-ProNH2 attenuates 4-aminopyridine-induced epileptiform activity and sodium current: a possible action of new thyrotropin-releasing hormone analog for its anticonvulsant potential

L-PGlu-(2-proPyl)-L-His-L-ProNH(2) (NP-647) is a CNS active thyrotropin-releasing hormone (TRH) analog with potential application in various CNS disorders including seizures. In the present study, mechanism of action for protective effect of NP-647 was explored by studying role of NP-647 on epileptiform activity and sodium channels by using patch-clamp methods. Epileptiform activity was induced in subicular pyramidal neurons of hippocampal slice of rat by perfusing 4-aminopyridine (4-AP) containing Mg(+2)-free normal artificial cerebrospinal fluid (nACSF). Increase in mean firing frequency was observed after perfusion of 4-AP and zero Mg(+2) (2.10+/-0.47 Hz) as compared with nACSF (0.12+/-0.08 Hz). A significant decrease in mean firing frequency (0.61+/-0.22 Hz), mean frequency of epileptiform events (0.03+/-0.02 Hz vs. 0.22+/-0.05 Hz of 4-AP+0 Mg), and average number of action potentials in paroxysmal depolarization shift-burst (2.54+/-1.21 Hz vs. 8.16+/-0.88 Hz of 4-AP +0 Mg) was observed. A significant reduction in peak dV/dt (246+/-19 mV ms(-1) vs. 297 18 mV ms-1 of 4-AP+0 Mg) and increase (1.332+/-0.018 ms vs. 1.292+/-0.019 ms of 4-AP+0 Mg) in time required to reach maximum depolarization were observed indicating role of sodium channels. Concentration-dependent depression of sodium current was observed after exposure to dorsal root ganglion neurons to NP-647. NP-647 at different concentrations (1, 3, and 10 mu M) depressed sodium current (15+/-0.5%, 50+/-2.6%, and 75+/-0.7%, respectively). However, NP-647 did not show change in the peak sodium current in CNa18 cells. Results of present study demonstrated potential of NP-647 in the inhibition of epileptiform activity by inhibiting sodium channels indirectly. (C) 2011 IBRO. Published by Elsevier Ltd. All rights reserved.

Evolution of texture and grain boundary microstructure in two-phase (α + β) brass during recrystallization

The evolution of texture and microstructure during recrystallization is studied for two-phase copper alloy (Cu–40Zn) with a variation of the initial texture and microstructure (hot rolled and solution treated) as well as the mode of rolling (deformation path: uni-directional rolling and cross rolling). The results of bulk texture have been supported by micro-texture and microstructure studies carried out using electron back scatter diffraction (EBSD). The initial microstructural condition as well as the mode of rolling has been found to alter the recrystallization texture and microstructure. The uni-directionally rolled samples showed a strong Goss and BR {236}385 component while a weaker texture similar to that of rolling evolved for the cross-rolled samples in the α phase on recrystallization. The recrystallization texture of the β phase was similar to that of the rolling texture with discontinuous 101 α and {111} γ fiber with high intensity at {111}101. For a given microstructure, the cross-rolled samples showed a higher fraction of coincident site lattice Σ3 twin boundaries in the α phase. The higher fraction of Σ3 boundaries is explained on the basis of the higher propensity of growth accidents during annealing of the cross-rolled samples. The present investigation demonstrates that change in strain path, as introduced during cross-rolling, could be a viable tool for grain boundary engineering of low SFE fcc materials.

Trade determination in multi-attribute exchanges

Electronic exchanges are double-sided marketplaces that allow multiple buyers to trade with multiple sellers, with aggregation of demand and supply across the bids to maximize the revenue in the market. Two important issues in the design of exchanges are (1) trade determination (determining the number of goods traded between any buyer-seller pair) and (2) pricing. In this paper we address the trade determination issue for one-shot, multi-attribute exchanges that trade multiple units of the same good. The bids are configurable with separable additive price functions over the attributes and each function is continuous and piecewise linear. We model trade determination as mixed integer programming problems for different possible bid structures and show that even in two-attribute exchanges, trade determination is NP-hard for certain bid structures. We also make some observations on the pricing issues that are closely related to the mixed integer formulations.

Boxicity and Poset Dimension

Let G be a simple, undirected, finite graph with vertex set V (G) and edge set E(G). A k-dimensional box is a Cartesian product of closed intervals [a(1), b(1)] x [a(2), b(2)] x ... x [a(k), b(k)]. The boxicity of G, box(G), is the minimum integer k such that G can be represented as the intersection graph of k-dimensional boxes; i.e., each vertex is mapped to a k-dimensional box and two vertices are adjacent in G if and only if their corresponding boxes intersect. Let P = (S, P) be a poset, where S is the ground set and P is a reflexive, antisymmetric and transitive binary relation on S. The dimension of P, dim(P), is the minimum integer t such that P can be expressed as the intersection of t total orders. Let G(P) be the underlying comparability graph of P; i.e., S is the vertex set and two vertices are adjacent if and only if they are comparable in P. It is a well-known fact that posets with the same underlying comparability graph have the same dimension. The first result of this paper links the dimension of a poset to the boxicity of its underlying comparability graph. In particular, we show that for any poset P, box(G(P))/(chi(G(P)) - 1) <= dim(P) <= 2box(G(P)), where chi(G(P)) is the chromatic number of G(P) and chi(G(P)) not equal 1. It immediately follows that if P is a height-2 poset, then box(G(P)) <= dim(P) <= 2box(G(P)) since the underlying comparability graph of a height-2 poset is a bipartite graph. The second result of the paper relates the boxicity of a graph G with a natural partial order associated with the extended double cover of G, denoted as G(c): Note that G(c) is a bipartite graph with partite sets A and B which are copies of V (G) such that, corresponding to every u is an element of V (G), there are two vertices u(A) is an element of A and u(B) is an element of B and {u(A), v(B)} is an edge in G(c) if and only if either u = v or u is adjacent to v in G. Let P(c) be the natural height-2 poset associated with G(c) by making A the set of minimal elements and B the set of maximal elements. We show that box(G)/2 <= dim(P(c)) <= 2box(G) + 4. These results have some immediate and significant consequences. The upper bound dim(P) <= 2box(G(P)) allows us to derive hitherto unknown upper bounds for poset dimension such as dim(P) = 2 tree width (G(P)) + 4, since boxicity of any graph is known to be at most its tree width + 2. In the other direction, using the already known bounds for partial order dimension we get the following: (1) The boxicity of any graph with maximum degree Delta is O(Delta log(2) Delta), which is an improvement over the best-known upper bound of Delta(2) + 2. (2) There exist graphs with boxicity Omega(Delta log Delta). This disproves a conjecture that the boxicity of a graph is O(Delta). (3) There exists no polynomial-time algorithm to approximate the boxicity of a bipartite graph on n vertices with a factor of O(n(0.5-is an element of)) for any is an element of > 0 unless NP = ZPP.

Scheduling identical parallel machines with machine eligibility restrictions to minimize total weighted flowtime in automobile gear manufacturing

In this paper, we address a scheduling problem for minimizing total weighted flowtime, observed in automobile gear manufacturing. Specifically, the bottleneck operation of the pre-heat treatment stage of gear manufacturing process has been dealt with in scheduling. Many real-life scenarios like unequal release times, sequence dependent setup times, and machine eligibility restrictions have been considered. A mathematical model taking into account dynamic starting conditions has been proposed. The problem is derived to be NP-hard. To approach the problem, a few heuristic algorithms have been proposed. Based on planned computational experiments, the performance of the proposed heuristic algorithms is evaluated: (a) in comparison with optimal solution for small-size problem instances and (b) in comparison with the estimated optimal solution for large-size problem instances. Extensive computational analyses reveal that the proposed heuristic algorithms are capable of consistently yielding near-statistically estimated optimal solutions in a reasonable computational time.

Selective colorimetric detection of nanomolar Cr (VI) in aqueous solutions using unmodified silver nanoparticles

In this study we present a colorimetric detection method for Cr (VI) in aqueous solution based on as synthesized silver nanoparticles (Ag NPs) without surface functionalization. The method principle involves reduction of Cr (VI) to Cr (III) by excess reductant present in as synthesized Ag NP dispersion, and subsequent aggregation of Ag NPs by Cr (III) leading to red-shift of the surface plasmon resonance (SPR) peak. The UV-vis absorption spectra. Zeta potentials, dynamic light scattering measurements, and scanning electron microscopy (SEM) confirmed the aggregation of the Ag NPs. Under the optimized conditions, a good linear relationship (correlation coefficient r=0.981) was obtained between the ratio of the absorbance at 550 nm to that at 390 nm (A(550/390)) and the concentration of Cr (VI) over the range of 10(-3)-10(-9) M 50 mg/L to 50 ng/L]. The reported probe has a limit of detection down to 1 nM, which, to the best of our knowledge, is the lowest ever reported for the colorimetric detection of Cr (VI). Furthermore, a remarkable feature of this method is that it involves a simple technique exhibiting high selectivity to Cr (VI) over other tested heavy metal ions. (C) 2012 Elsevier BM. All rights reserved.

Deformation behaviour of Titanium in torsion

The evolution of microstructure and texture in Hexagonal Close Pack commercially pure titanium has been studied in torsion in a strain rate regime of 0.001 to 1 s(-1). Free end torsion tests carried out on titanium rods indicated higher stress levels at higher strain rate but negligible change in the strain-hardening behaviour. There was a decrease in the intra-granular misorientation while a negligible change in the amount of contraction and extension twins was observed with increase in strain rate. The deformed samples showed a C-1 fibre (c-axis is first rotated 90 degrees in shear direction and then +30 degrees in shear plane direction) at all the strain rates. With the increase in strain rate, there was an increase in the intensity of the C-1 fibre and it became more heterogeneous with a strong {11(2)over-bar6}< 2(8)over-bar)63 > component. In the absence of extensive twinning, pyramidal < c+a > slip system is attributed for the observed deformation texture. The present investigation, therefore, substantiates the theoretical prediction of increase in strength of texture with strain rate in torsion.

Algorithmic aspects of k-tuple total domination in graphs

For a fixed positive integer k, a k-tuple total dominating set of a graph G = (V. E) is a subset T D-k of V such that every vertex in V is adjacent to at least k vertices of T Dk. In minimum k-tuple total dominating set problem (MIN k-TUPLE TOTAL DOM SET), it is required to find a k-tuple total dominating set of minimum cardinality and DECIDE MIN k-TUPLE TOTAL DOM SET is the decision version of MIN k-TUPLE TOTAL DOM SET problem. In this paper, we show that DECIDE MIN k-TUPLE TOTAL DOM SET is NP-complete for split graphs, doubly chordal graphs and bipartite graphs. For chordal bipartite graphs, we show that MIN k-TUPLE TOTAL DOM SET can be solved in polynomial time. We also propose some hardness results and approximation algorithms for MIN k-TUPLE TOTAL DOM SET problem. (c) 2012 Elsevier B.V. All rights reserved.