7846317
Throughput differentiation using coloring at the network edge and preferential marking at the core
In this paper we introduce an innovation in differentiated services architecture consisting of adaptive two-level coloring at the edge and preferential marking at the core. We identify general properties of these two processes which, when met, guarantee a desirable fixed point for the network; i.e., one where aggregated flow rates meet or exceed given targets in an over-provisioned network. Specific mechanisms realizing the aforementioned properties lead to so-called active rate management controllers for edge coloring, and a preferentially-marking, active queue management controller at the core. We discuss stability of the fixed point for this network, and validate results using ns simulations.
13845864
On the interaction between overlay routing and underlay routing
In this paper, we study the interaction between overlay routing and traffic engineering (TE) in a single autonomous system (AS). We formulate this interaction as a two-player non-cooperative non-zero sum game, where the overlay tries to minimize the delay of its traffic and the TE's objective is to minimize network cost. We study a Nash routing game with best-reply dynamics, in which the overlay and TE have equal status, and take turns to compute their optimal strategies based on the response of the other player in the previous round. We prove the existence, uniqueness and global stability of Nash equilibrium point (NEP) for a simple network. For general networks, we show that the selfish behavior of an overlay can cause huge cost increases and oscillations to the whole network. Even worse, we have identified cases, both analytically and experimentally, where the overlay's cost increases as the Nash routing game proceeds even though the overlay plays optimally based on TE's routing at each round. Experiments are performed to verify our analysis.
11427190
Exploiting the IPID Field to Infer Network Path and End-System Characteristics
In both active and passive network Internet measurements, the IP packet has a number of important header fields that have played key roles in past measurement efforts, e.g., IP source/destination address, protocol, TTL, port, and sequence number/acknowledgment. The 16-bit identification field (IPID) has only recently been studied to determine what information it might yield for network measurement and performance characterization purposes. We explore several new uses of the IPID field, including how it can be used to infer: (a) the amount of internal (local) traffic generated by a server; (b) the number of servers in a large-scale, load-balanced server complex and; (c) the difference between one-way delays of two machines to a target computer. We illustrate and validate the use of these techniques through empirical measurement studies.
2899757
Providing throughput differentiation for TCP flows using adaptive two-color marking and two-level AQM
In this paper we propose a new paradigm for a Differentiated Service (DiffServ) network consisting of two-color marking at the edges of the network using token buckets coupled with differential treatment in the core. Using fluid-flow modelling, we present existence conditions for token-bucket rates and differential marking probabilities at the core that result in all edges receiving at least their minimum guaranteed rates. We then present an integrated DiffServ architecture comprising of an active rate management controller at the marking edge and a two-level active queue management controller at the core. The validity of the fluid flow model and performance of this new scheme are verified using ns simulations.
147783
Availability in BitTorrent Systems
In this paper, we investigate the problem of highly available, massive-scale file distribution in the Internet. To this end, we conduct a large-scale measurement study of BitTorrent, a popular class of systems that use swarms of actively downloading peers to assist each other in file distribution. The first generation of BitTorrent systems used a central tracker to enable coordination among peers, resulting in low availability due to the tracker's single point of failure. Our study analyzes the prevalence and impact of two recent trends to improve BitTorrent availability: (i) use of multiple trackers, and (ii) use of Distributed Hash Tables (DHTs), both of which also help to balance load better. The study considered more than 1,400 trackers and 24,000 DHT nodes (extracted from about 20,000 torrents) over a period of two months. We find that both trends improve availability, but for different and somewhat unexpected reasons. Our findings include: (i) multiple trackers improve availability, but the improvement largely comes from the choice of a single highly available tracker, (ii) such improvement is reduced by the presence of correlated failures, (iii) multiple trackers can significantly reduce the connectivity of the overlay formed by peers, (iv) the DHT improves information availability, but induces a higher response latency to peer queries.
6607794
Can an Overlay Compensate for a Careless Underlay?
We investigate the ability of an overlay network to compensate for “careless” routing in the native network layer, i.e., for network-layer routes not optimized for performance. We consider cost/traffic-dependent, overlay routing on top of an underlay routing based on randomly-generated, cost/traffic-independent link weights, and determine the extent to which overlay-overcareless-underlay can achieve performance close to that attainable when underlay routing is performed in an optimal cost/trafficdependent (“careful”) manner. We identify three graph-theoretic metrics that collectively characterize the richness of the underlay network: the tightness (characteristic path length, or CPL), the thickness (cut average) and the weighted sum of node degrees. We find that only when the underlay graph is rich can the overlay compensate for a careless underlay. If network links have linear costs, we prove that overlay cost is a linear increasing function of CPL under some assumptions. Finally, we investigate heuristics (based on the notion of richness) for choosing a set of overlay nodes of fixed size that is likely to result in good overlay performance.
7586705
The Representational Power of Discrete Bayesian Networks
One of the most important fundamental properties of Bayesian networks is the representational power, reflecting what kind of functions they can or cannot represent. In this paper, we establish an association between the structural complexity of Bayesian networks and their representational power. We use the maximum number of nodes' parents as the measure for the structural complexity of Bayesian networks, and the maximum XOR contained in a target function as the measure for the function complexity. A representational upper bound is established and proved. Roughly speaking, discrete Bayesian networks with each node having at most k parents cannot represent any function containing (k+1)-XORs. Our theoretical results help us to gain a deeper understanding on the capacities and limitations of Bayesian networks.
13998980
Image annotation refinement using random walk with restarts
Image annotation plays an important role in image retrieval and management. However, the results of the state-of-the-art image annotation methods are often unsatisfactory. Therefore, it is necessary to refine the imprecise annotations obtained by existing annotation methods. In this paper, a novel approach to automatically refine the original annotations of images is proposed. On the one hand, for Web images, textual information, e.g. file name and surrounding text, is used to retrieve a set of candidate annotations. On the other hand, for non-Web images that are lack of textual information, a relevance model-based algorithm using visual information is used to decide the candidate annotations. Then, candidate annotations are re-ranked and only the top ones are reserved as the final annotations. To re-rank the annotations, an algorithm using Random Walk with Restarts (RWR) is proposed to leverage both the corpus information and the original confidence information of the annotations. Experimental results on both non-Web images of Corel dataset and Web images of photo forum sites demonstrate the effectiveness of the proposed method.
20777551
A Method of Network Simplification in a 4PL System
In fourth party logistics (4PL), network optimization needs to synthesize the entire possible 3PL vendors to provide integrated logistics schemes, which can meet all the requirements of customers. Since there are knapsack constraints and un-knapsack constraints, the computational burden is considered to be a problem and a modest computation is required. In this paper, a 4PL optimization network-model is established and a two-process method is suggested for simplifying the corresponding 4PL network. An example is provided and some analysis is given after the calculation.
16669804
An effective region-based image retrieval framework
We present a region-based image retrieval framework that integrates efficient region-based representation in terms of storage and retrieval and effective on-line learning capability. The framework consists of methods for image segmentation and grouping, indexing using modified inverted file, relevance feedback, and continuous learning. By exploiting a vector quantization method, a compact region-based image representation is achieved. Based on this representation, an indexing scheme similar to the inverted file technology is proposed. In addition, it supports relevance feedback based on the vector model with a weighting scheme. A continuous learning strategy is also proposed to enable the system to self improve. Experimental results on a database of 10,000 general-purposed images demonstrate the efficiency and effectiveness of the proposed framework.
15728506
Interactive collision detection for complex and deformable models using programmable graphics hardware
In this paper we present an interactive collision detection algorithm for complex and deformable objects. For two target models, our approach rapidly calculates their region of interests (ROI), which is the overlapping of their axis aligned bounding boxes (AABBs), in CPU. The surfaces of both models inside the ROI are then voxelized using a novel GPU-based real-time voxelization method. The resultant volumes are represented by two 2D textures in video memory. The collision query is efficiently accomplished by comparing these 2D textures in GPU. The algorithm is robust to handle arbitrary shapes, no matter geometric models are convex or concave, closed or open, rigid or deformable. Our preliminary implementation achieves interactive frame rate for complex models with up to one million triangles on commodity desktop PCs.