Modular reduction is a fundamental operation in cryptographic systems. Most well known modular reduction methods including Barrett's and Montgomery's algorithms leverage some-pre computations to avoid divisions so that the main complexity of these methods lies in a sequence of two long multiplications. For large wordlengths a multiplication which is tantamount to a linear convolution is performed via the fast Fourier transform (FFT) or other transform-based techniques as in the Schonhage-Strassen multiplication algorithm. We show a fundamental property (the separation principle): in a modular reduction based on long multiplications, the linear convolution required by one of the two long multiplications can be replaced by a cyclic convolution, and the halves can be separated using other information available due to the intrinsic redundancy of the operations. This reduces the number of operations by about 25%. We demonstrate that both Barrett's and Montgomery's methods can be sped up by using the aforementioned fundamental principle. It is shown that a direct application of this algorithm to modular exponentiation (either using Barrett's or Montgomery's methods) can be expected to yield about about 17% speedup.

Data striping across multiple network interfaces and its applications to mobile environments was recently investigated (Phatak and Goff, 2002). Therein, a network-layer Internet protocol (IP)-in-IP encapsulation mechanism was proposed to aggregate the bandwidth of multiple network paths by striping a single transport layer [transmission control protocol (TCP)] connection across them. The analysis and experimental results from that study demonstrated fundamental limitations to TCPs performance in such scenarios. In this paper, we therefore propose a method of overcoming these limitations by striping data at the transport layer. For a proof-of-concept demonstration we use a substantially enhanced version of the stream control transmission protocol (SCTP). Our analytical results and experimental data illustrate that there are significant advantages to using a transport protocol with native support for the simultaneous use of multiple network interfaces, as opposed to stretching TCP to a point where it is no longer effective. This work naturally leads to another fundamental issue of end-to-end support for host mobility at the transport layer. Our analysis and results demonstrate that transport layer support for multiple network (IP) interfaces, together with the capability to dynamically add or delete IP addresses can yield the following advantages: higher bandwidth, load balancing, and increased fairness, enhanced reliability, and end-to-end support for host mobility. This is independent of the underlying network-layer and, hence, is applicable to static/wired, as well as wireless/ad hoc environments. The proposed protocol offers a unified solution to both data striping across multiple networks interfaces, as well as end-to-end mobility support.

We compare implementations of Duprat and Muller's branching CORDIC and Phatak's double step branching (DSB)-CORDIC algorithms for sine and cosine evaluation. For reference we also report on classical CORDIC implementations for the same wordlengths. We have also implemented double stepping in the classical algorithm and report on the performance of this method. CORDIC evaluation of sine and cosine includes two parts, the zeroer and the rotator. We discuss implementation issues related to the minimization of the delay of each iteration of the algorithm (including delays for both the zeroer as well the rotator). We then examine hybrid methods that select the components from different algorithms (such as a DSB zeroer together with a classical rotator or vice versa).

With ubiquitous computing and network access, multiple network conduits are becoming available to mobile as well as static hosts. Selection of the preferred mode of data transfer is a dynamic optimization problem depending on the type of application, its bandwidth/latency/jitter requirements, current network status, cost, power consumption, battery life, and so on. Furthermore, since wireless bandwidth is likely to remain a scarce resource, we foresee scenarios wherein mobile hosts require simultaneous data transfer across multiple IP interfaces to obtain higher overall bandwidth. We present a brief overview of related work identifying schemes that might be applicable to the problem, along with their feasibility, and pros and cons. We then propose a new mechanism to aggregate the bandwidth of multiple IP links by splitting a data flow across multiple network interfaces at the IP level. Our method is transparent to transport (TCP/UDP) and higher layers. We have analyzed the performance characteristics of the aggregation scheme and demonstrated significant gain when the links being aggregated have similar bandwidth and latency. The use of multiple interfaces also enhances reliability. Our analysis identifies the conditions under which the proposed scheme, or any other scheme that stripes a single TCP connection across multiple IP links, can be used to enhance throughput. Several interesting directions for future work have also been identified.

In mobile ad hoc networks, the topology of the network is constantly changing as nodes move in and out of each other's range, breaking and establishing links. TCP performs poorly in such networks because packets that are lost due to path disconnections trigger TCP's congestion avoidance mechanisms. We investigate the effect of preemptive routing protocols, where an alternative path is found before an actual disconnection occurs, on the performance of TCP. Preemptive routing should perform well for TCP traffic because it reduces the delays caused by TCP's unnecessary use of congestion avoidance when paths break. We observe this behavior under some, but not all scenarios. Specifically, it appears that when the network is saturated, the additional traffic introduced by preemptive routing causes small degradation in performance. In the analysis process, we encountered an unfairness problem resulting from interaction between the routing protocol and the MAC layer under multiple continuous transmission cases. Similar unfairness problems were encountered by other studies-however the observations of those studies related those problems to the number of hops, and not the routing effects as we observed. This motivates the study of fairer wireless MAC protocols for multi-hop and ad hoc networks.

Existing on-demand ad-hoc routing algorithms initiate route discovery only after a path breaks, incurring a significant cost in detecting the disconnection and establishing a new route. In this work, we investigate adding proactive route selection and maintenance to on-demand ad-hoc routing algorithms. More specifically, when a path is likely to be broken, a warning is sent to the source indicating the likelihood of a disconnection. The source can then initiate path discovery early, potentially avoiding the disconnection altogether. A path is considered likely to break when the received packet power becomes close to the minimum detectable power (other approaches are possible). Care must be taken to avoid initiating false route warnings due to fluctuations in received power caused by fading, multipath effects and similar random transient phenomena. Experiments demonstrate that adding proactive route selection and maintenance to DSR and AODV (on-demand ad hoc routing protocols) significantly reduces the number of broken paths, with a small increase in protocol overhead. Packet latency and jitter also goes down in most cases. We also show some experimental results obtained by running TCP on top of the proactive routing schemes proposed. Several improvements and extensions are also discussed. Pro-active route selection and maintenance is general and can be used with other routing algorithms and optimizations to them.

It is well-known that constant-time addition, in which the execution delay is independent of operand lengths, is feasible only if the output is expressed in a redundant representation. There are many ways of introducing redundancy and the specifics of the redundant format employed can have a major impact on the performance of constant-time addition and digit set conversion. This paper presents a comprehensive analysis of constant-time addition and simultaneous format conversion. We consider full as well as partially redundant representations, where not all digit positions are redundant. The number of redundant digits and their positions can be arbitrary, yielding many possible redundant representations. Format conversion refers to changing the number and/or position of redundant digits in a representation. It is shown that such a format conversion is feasible during (ie, simultaneous with) constant time addition, even if all three operands (the two inputs and single output) are represented in distinct redundant formats. We exploit "equal-weight grouping" (EWG), wherein bits having the same weight are grouped together to achieve the constant-time addition and possible simultaneous format conversion. The analysis and data show that EWG leads to efficient implementations. We compare VLSI implementations of various constant-time addition cells and demonstrate that the conventional 4:2 compressor is the most efficient way to execute constant time-addition. We show interesting connections to prior results and indicate possible directions for further extensions.

Optimizing TCP (transport layer) for mobility has been researched extensively. We present a brief summary of existing results which indicates that most schemes require intermediaries (such as base stations) to monitor the TCP traffic and actively participate in flow control in order to enhance performance. Although these methods simulate end-to-end semantics, they do not comprise true end-to-end signaling. As a result, these techniques are not applicable when the IP payload is encrypted. For instance IPSEC, which is expected to be standard under IPv6, encrypts the entire IP payload making it impossible for intermediaries to monitor TCP traffic unless those entities are part of the security association. In addition, these schemes require changes (in the TCP/IP code) at intermediate nodes making it difficult for the mobile clients to inter-operate with the existing infrastructure. In this paper we explore the "freeze-TCP" mechanism which is a true end-to-end scheme and does not require the involvement of any intermediaries (such as base stations) for flow control. Furthermore, this scheme does not require any changes on the "sender side" or intermediate routers; changes in TCP code are restricted to the mobile client side, making it possible to fully inter-operate with the existing infrastructure. We then outline a method which integrates the best attributes of freeze-TCP and some existing solutions. Performance results highlight the importance of pro-active action/signaling by the mobile-host. The data indicate that in most cases, simply reacting to disconnections tends to yield lower performance than pro-active mechanisms such as freeze-TCP.