40767747
Hardness on IP-subnet Aware Routing in WDM Network
In this paper, we study the hardness of the IP-subnet aware routing problem in WDM network. IP-subnet aware routing attempts to reduce routing overhead by grouping a set of addresses under a single subnet. However, routing in WDM network with subnets imposes neighboring IP interfaces along the path to be on the same subnet. This subnet constraint forces the routing path to be longer unless routing permits reconfiguration of subnets. The hardness of this routing problem is first studied in [1]. We investigate further the problem of finding paths accounting for subnets and its hardness. Regardless of subnets, we argue that a shortest IP hop path can be constructed in a polynomial time. We provide efficient routing algorithms to justify our argument.
9969836
Efficient route establishment and maintenance in wireless sensor networks with mobile base stations
The integration of ground wireless adhoc networks and airborne UAVs is a promising solution for realtime data collection in wireless sensor networks. Such networks play a vital role in many mission critical tasks such as forest fire-fighting and battlefield support. An important problem is to establish/maintain efficient routing structures in the ground sensor network for packet relaying. Our problem is unique in that the base stations are non-static, which necessitates frequent update of the routing structure. The performance of flooding based methods are evaluated. Particularly, in order to deal with non-uniform node density, we propose to introduce an artificial delay factor to control the flooding pattern. We mathematically prove that the delay should be proportional to local node density. Our simulation results show that the proposed method achieves good load balance among multiple base stations.
550326
Efficient alarm management in optical networks
As the capacity of optical transport networks increases, rapid fault identification and localization become increasingly important. These problems are more challenging than in traditional electronic networks because of optical transparency. In a transparent optical network which does not regenerate optical signals, a fault may propagate to various parts of the network from the origin, and multiple alarms can be generated for a single failure. Efficient alarm management and filtering requires a careful selection and placement of network monitoring equipment. In this paper we survey the capabilities of current optical monitoring equipment and formulate a problem of selecting monitors to be placed throughout the network. Simulation results suggest that the number of monitors and generated alarms can be significantly reduced if monitor locations are selected judiciously.
6488428
Preserving survivability during logical topology reconfiguration in WDM ring networks
We consider the design of reconfiguring logical topologies over physical WDM ring networks. The logical topology consists of the same set of nodes as the physical topology, and the links of the logical topology are lightpaths established (or embedded) over the physical topology. The logical topology is said survivable if the failure of any single physical link does not disconnect the logical topology. In this paper, we consider the following problem: Given a logical topology with its survivable embedding over a physical ring network and a new logical topology to be reconfigured, find a sequence of lightpaths additions and deletions satisfying the given wavelengths and ports constraints such that the logical topology remains survivable throughout the reconfiguration.
800618
Packet filtering for congestion control under DoS attacks
Congestion control in IP networks is typically done at each router through queue management, and the network is entirely dependent on the end hosts to react congestion. However, when misbehaving flows exist and continue to send their packets in very high rates, the queue management schemes implemented in current IP routers reveal a significant shortcoming in protecting legitimate flows. Here, we propose a novel scheme for congestion control in IP networks. Our approach is a time-window based filtering mechanism implemented in a router and processed before a queue management policy is applied. Setting the window size properly and dropping packets reaching in the next window can catch the nonresponsive nature of misbehaving flows. The performance of our proposed scheme is demonstrated through extensive simulations using the NS2, simulator using a set of simulated traffic generated based on IP traces reported in http://www.nlnar.org.
24043784
Efficient scheduling of transmissions in optical broadcast networks
All-optical networks (AONs) with a broadcast-star based physical topology offer the possibility of transmission scheduling to resolve channel and receiver conflicts. This paper considers the problem of scheduling packet transmissions in a wavelength-division multiplexed (WDM) optical network with tunable transmitters and fixed-tuned receivers. The scheduling problem is complicated by tuning latency, a limited number of channels, and arbitrary traffic demands. We first analyze scheduling all-to-all packet transmissions and obtain a new lower bound for the schedule length. The lower bound is achieved by an algorithm proposed by Pieris and Sasaki (1994). We then extend the analysis to the case of arbitrary traffic demands and obtain lower bounds for the schedule length. Two constructions for scheduling algorithms are provided through list scheduling and multigraphs. The upper bounds so obtained not only provide performance guarantees with arbitrary demands, but also nearly meet the lower bound in simulations.
38568907
Construction and shape analysis of PH quintic Hermite interpolants
In general, the problem of interpolating given first-order Hermite data (end points and derivatives) by quintic Pythagorean-hodograph (PH) curves has four distinct formal solutions. Ordinarily, only one of these interpolants is of acceptable shape. Previous interpolation algorithms have relied on explicitly constructing all four solutions, and invoking a suitable measure of shape—e.g., the absolute rotation index or elastic bending energy—to select the “good” interpolant. We introduce here a new means to differentiate among the solutions, namely, the winding number of the closed loop formed by a union of the hodographs of the PH quintic and of the unique “ordinary” cubic interpolant. We also show that, for “reasonable” Hermite data, the good PH quintic can be directly constructed with certainty, obviating the need to compute and compare all four solutions. Finally, we present an algorithm based on the subdivision, degree elevation, and convex hull properties of the Bernstein form, that gives rapidly convergent curvature bounds for PH curves, using only rational arithmetic operations on their coefficients.
30297846
Throughput Aware Mapping for Network on Chip Design of H.264 Decoder
Network-on-Chip (NoC) has been proposed as a new methodology for addressing the design challenges of future massly integrated system in nanoscale. In this paper, we present the queuing theory based model for router to evaluate the performance of NoC in terms of drop probability, throughput and energy consumption. Then we apply the linear programming to optimize the allocation of the heterogeneously functional blocks (IPs) onto the given heterogeneous NoC architecture so as to obtain the maximum throughput as well as to optimize the energy dissipation of whole system. Finally, the three differently heterogenous Tree-based network topologies are proposed as the NoC architectures for the study case of H.264 Decoder. This paper also evaluates the proposed topologies by comparing them to other conventional topologies such as 2-D Mesh and Fat-Tree with respects to throughput, power consumption and size. We use the power modelling tool, known as Orion model to calculate the static powers, areas, and dynamic powers of three topologies. The experiment results show that our Tree-based topologies offer similar throughputs as Fat-Tree does and much higher throughputs compared to 2-D Mesh while use less chip areas and energy consumptions.
10020005
Robust kernel Isomap
Isomap is one of widely used low-dimensional embedding methods, where geodesic distances on a weighted graph are incorporated with the classical scaling (metric multidimensional scaling). In this paper we pay our attention to two critical issues that were not considered in Isomap, such as: (1) generalization property (projection property); (2) topological stability. Then we present a robust kernel Isomap method, armed with such two properties. We present a method which relates the Isomap to Mercer kernel machines, so that the generalization property naturally emerges, through kernel principal component analysis. For topological stability, we investigate the network flow in a graph, providing a method for eliminating critical outliers. The useful behavior of the robust kernel Isomap is confirmed through numerical experiments with several data sets.
12754524
Almost rotation-minimizing rational parametrization of canal surfaces
Almost rotation minimizing parametrization of the canal surface is given. The basic building block of our approach is the curve approximation scheme that enables us to construct a curve, called the parameter curve, on the canal surface that produces, when projected and rescaled, an almost parallel normal vector field on the spine curve. Its construction relies on our earlier methods and results on relating the geometry of the canal surface to the Lorentzian geometry of the Minkowski geometry via the Clifford algebra formalism. We then iteratively construct patches out of the parameter curves via suitable interpolation procedure. Furthermore, its rotational deviation, i.e., the angle deviation from the parallel (no rotation) frame along the spine curve, can be controlled with the use of the rotation deviation estimate of the parameter curves. Our numerical experiment shows that the rotation deviation is minuscule. When compared with other earlier results including our earlier one, our result fares extremely favorably. To facilitate the implement, a practitioners' summary is given in the appendix.
5939692
Analyzing the Performance of Mesh and Fat-Tree Topologies for Network on Chip Design
The demand of integration of many heterogeneous semiconductor intellectual property (IP) blocks has been introducing a new chip design paradigm so called on chip network. This paradigm promisingly offers a packet switched network among IPs to reduce the main problems in the very deep sub micron technologies that arise from non-scalable global wire delay, failure to achieve global synchronization, errors due to the signal integrity, non-scalable bus based functional interconnection, etc. This paper introduces interconnected or switched network topologies and also analyze their performances in terms of communication protocol related to the issues such as routing strategy, buffer size, routing algorithm , etc. The above mentioned evaluations are done by utilizing the tool that has been widely used in the research domain of computer network design, so called NS-2.