5433735
Avoiding Transient Loops Through Interface-Specific Forwarding
Under link-state routing protocols such as OSPF and IS-IS, when there is a change in the topology, propagation of link-state announcements, path recomputation, and updating of forwarding tables (FIBs) will all incur some delay before traffic forwarding can resume on alternate paths. During this convergence period, routers may have inconsistent views of the network, resulting in transient forwarding loops. Previous remedies proposed to address this issue enforce a certain order among the nodes in which they update their FIBs. While such approaches succeed in avoiding transient loops, they incur additional message overhead and increased convergence delay. We propose an alternate approach, loopless interface-specific forwarding (LISF), that averts transient loops by forwarding a packet based on both its incoming interface and destination. LISF requires no modifications to the existing link-state routing mechanisms. It is easily deployable with current routers since they already maintain a FIB at each interface for lookup efficiency. This paper presents the LISF approach, proves its correctness, discusses three alternative implementations of it and evaluates their performance.
14253908
Proactive vs reactive approaches to failure resilient routing
Dealing with network failures effectively is a major operational challenge for Internet service providers. Commonly deployed link state routing protocols such as OSPF react to link failures through global (i.e., network-wide) link state advertisements and routing table recomputations, causing significant forwarding discontinuity after a failure. The drawback with these protocols is that they need to trade off routing stability and forwarding continuity. To improve failure resiliency without jeopardizing routing stability, we propose a proactive local rerouting based approach called failure insensitive routing (FIR). The proposed approach prepares for failures using interface-specific forwarding, and upon a failure, suppresses the link state advertisement and instead triggers local rerouting using a backwarding table. In this paper, we prove that when no more than one link failure notification is suppressed, FIR always finds a loop-free path to a destination if one such path exists. We also formally analyze routing stability and network availability under both proactive and reactive approaches, and show that FIR provides better stability and availability than OSPF.
45980845
Optimal adaptive bandwidth monitoring for QoS based retrieval
Network aware multimedia delivery applications guarantee QoS parameters like media object transmission time limit by actively monitoring the available bandwidth of the network and adapting the object to a target size that can be transmitted within a given time limit. A critical problem is how to obtain an accurate enough estimation of available bandwidth while not wasting too much time in bandwidth testing. We present an algorithm to determine the optimal amount of bandwidth testing, given a probabilistic confidence level for network-aware multimedia retrieval. Our implementation and experiments show that the algorithm finds out the optimal amount of bandwidth testing effectively with minimum computation overhead.
2412157
Optimal adaptive bandwidth monitoring for QoS based retrieval
Network aware multimedia delivery applications are a class of applications that provide certain level of quality of service (QoS) guarantees to end users while not assuming underlying network resource reservations. These applications guarantee QoS parameters like media object transmission time limit by actively monitoring the available bandwidth of the network and adapting the object to a target size that can be transmitted within a given time limit. A critical problem is how to obtain an accurate enough estimation of available bandwidth while not wasting too much time in bandwidth testing. In this paper, we present an algorithm to determine optimal amount of bandwidth testing given a probabilistic confidence level for network-aware multimedia object retrieval applications. The model treats the bandwidth testing as sampling from an actual bandwidth population. It uses statistical estimation method to quantify the benefit of each new bandwidth-testing sample, which is used to determine the optimal amount of bandwidth testing by balancing the benefit with the cost of each sample. Our implementation and experiments shows the algorithm determines the optimal amount of bandwidth testing effectively with minimum computation overhead.
5719748
Leopard: A Locality Aware Peer-to-Peer System with No Hot Spot
Recent research [7,12,2] has shown that Internet hosts can be efficiently (i.e., without excessive measurements) mapped to a virtual (Euclidean) coordinate system, where the geometric distance between any two nodes in this virtual space approximates their real IP network distance (latency). Based on this result, in this paper, we propose an alternative approach that inherently incorporates a virtual coordinate system into a P2P network. In our system, called Leopard, a node is assigned a coordinate in the so-called node geo space as it joins the network, and obtains neighbor relationships that reflects network proximity from the beginning. The object id space and the node geo space are then “weaved” together via a novel technique called geographically-scoped hashing. Through analysis and simulation, we show three major desirable properties of Leopard to exemplify the power of this paradigm shift: i) a constant routing stretch, i.e., IP level network latency of object look-up is proportional to the distance between a requesting node and the target object; ii) always locates a near-by copy when multiple copies exist; and iii) effectively handles “flash crowd” traffic with near optimal load balancing.
3035412
On the Expected Number of Failures Detected by Subdomain Testing and Random Testing
We investigate the efficacy of subdomain testing and random testing using the expected number of failures detected (the E-measure) as a measure of effectiveness. Simple as it is, the E-measure does provide a great deal of useful information about the fault detecting capability of testing strategies. With the E-measure, we obtain new characterizations of subdomain testing, including several new conditions that determine whether subdomain testing is more or less effective than random testing. Previously, the efficacy of subdomain testing strategies has been analyzed using the probability of detecting at least one failure (the P-measure) for the special case of disjoint subdomains only. On the contrary, our analysis makes use of the E-measure and considers also the general case in which subdomains may or may not overlap. Furthermore, we discover important relations between the two different measures. From these relations, we also derive corresponding characterizations of subdomain testing in terms of the P-measure.
2838174
Minimizing the number of programming steps for diagnosis of interconnect faults in FPGAs
This paper presents a procedure to diagnose single faults in SRAM based FPGAs. The procedure is nonadaptive and requires six programming steps to give the exact position and type of any single fault in a FPGA. It is proved that the number of programming steps required for the procedure is minimal for a non-adaptive procedure with the given interconnect model.
5687277
A self-adaptive scheduling algorithm of on-demand broadcasts
In mobile wireless systems data on air can be accessed by a large number of mobile users. Many of these applications such as wireless internets and traffic information systems are pull-based, that is, they respond to on-demand user requests. In this paper, we study the scheduling problems of on-demand broadcast environments. Traditionally, the response time of the requests has been used as a performance measure. In this paper we consider the performance as the average cost of request composed of three kinds of costs—access time cost, tuning time cost, and cost of handling failure request. Our main contribution is a self-adaptive scheduling algorithm named LDFC, which computes the delay cost of data item as the priority for broadcast. It performs well compared with some previous algorithms in this context.
15449420
Procurement of enterprise resource planning systems: experiences with some Hong Kong companies
Many cases of adoption of Enterprise Resource Planning (ERP) systems have been reported in the literature. Some of the adopted ERP systems fail to satisfy the customer's requirements, despite the high spending and substantial efforts that have been put into the adoption exercise. This is undoubtedly unsatisfactory. A way to avoid this problem is to adopt a well planned, managed, and controlled ERP procurement process. This paper describes our studies of three Chinese companies in Hong Kong which have adopted ERP systems. We report the experience of these companies, and discuss how the Chinese culture might have shaped the procurement practices in their ERP adoption exercises.
17008107
A Rendering Equation for Specular Transfers and Its Integration into Global Illumination
In this paper, we present a rigorous theoretical formulation of the fundamental problem—indirect illumination from area sources via curved ideal specular surfaces. Intensity and area factors are introduced to clarify this problem and to rectify the radiance from these specular surfaces. They take surface geometry, such as Gaussian curvature, into account. Based on this formulation, an algorithm for integrating ideal specular transfers into global illumination is also presented. This algorithm can deal with curved specular reflectors and transmitters. An implementation is described based on wavefront tracing and progressive radiosity. Sample images generated by this method are presented.