6456130
A dynamic range resource reservation protocol for QoS support in wireless networks
Summary form only given. In order to provide support for multimedia applications in mobile ad hoc networks (MANETs), quality of service (QoS) support becomes an important component in their design. In this paper, we present a dynamic range bandwidth reservation protocol for TDMA-based MANETs. In this protocol, a source node S, that needs to send data, sends a request message (QREQ) to reserve a QoS path to the desired destination node D. In the reservation message, the source node specifies a dynamic range [b/sub min/, b/sub max/] of the number of slots needed to transmit the data. The intermediate nodes along the path try to reserve a number of slots, b/sub cur/, that is equal to the maximum number of slots that are "available" within this range (b/sub min/ /spl ges/ b/sub cur/ /spl ges/ b/sub max/). The protocol also permits intermediate nodes to dynamically "downgrade" existing paths that are functioning above their minimum requirements in order to allow the successful reservation for the maximum number of requested paths. When the network traffic load is later decreased, the existing paths are able to be "upgraded" to function with higher bandwidth requirements. This allows the network to admit new QoS paths instead of denying such requests by allowing for "graceful degradation" of other paths. The paper also presents several optimization techniques which are designed to increase the efficiency and throughput of the network. This protocol allows a higher level of flexibility in providing and maintaining QoS support in MANETs.
7582647
On self-similarity and hamiltonicity of dual-cubes
The dual-cube is a newly proposed topology for interconnection networks, which uses low dimensional hypercubes as building blocks. The primary advantages of the dual-cube over the hypercube are that, with the same node degree n, the dual-cube contains 2/sup n-1/ times more nodes than the hypercube and, with the same amount of nodes, the dual-cube has approximately 50% less links than the hypercube. This paper was focused on the investigations of the structural self-similarity and the Hamiltonian property of the dual-cube. It was shown that a dual-cube can be recursively constructed from lower dimensional dual-cubes and, conversely, a dual-cube can be recursively decomposed into lower dimensional dual-cubes. It was also proved that all dual-cubes are Hamiltonian. There exist multiple Hamiltonian cycles on a dual-cube, among which, [(n-1)/2] cycles are edge-disjoint. It was illustrated that rings and linear arrays can be effectively emulated on dual-cubes. Some strategies for track sharing in efficient VLSI layout design were also discussed.
2254959
Local-Safety-Information-Based Broadcasting in Hypercube Multicomputers with Node and Link Faults
This paper presents a method to cope with fault-tolerant broadcasting in hypercube multicomputers with both node and link faults. The local safety concept is extended to faulty hypercubes with both node and link faults. The local-safety-based algorithm is used in a fully unsafe hypercube, where there is no safe node. A fully unsafe hypercube can be split into a set of maximal safe subcubes. We show that if these maximal safe subcubes meet certain requirements given in the paper, broadcasting can still be carried out successfully and in some case optimal broadcast is still possible. The method is extended to fault-tolerant routing and multicasting when the system contains both node and link faults.
16257632
XYZ: a scalable, partially centralized lookup service for large-scale peer-to-peer systems
Peer-to-peer (P2P) systems are characterized by direct access between peer computers, rather than through a centralized server. File sharing is the dominant P2P application on the Internet, allowing users to easily contribute, search and obtain content. P2P systems can be categorized by the degrees of centralization. For fully centralized systems, the lookup service will not be available when the central directory server is down. For purely decentralized and unstructured systems, since there is no information about which nodes are likely to have the relevant files, searching essentially amounts to random search. This makes the lookup service unscalable and unpredictable. The objective of this paper is to design a partially centralized, scalable and self-organizing lookup service (XYZ) for wide area P2P systems. A clustering method is used to create the system backbone by connecting the cluster heads together and a color clustering method is adopted to create color overlays and minimize the searching space. Simulations and analysis are also provided. Extensions are proposed to achieve better performance
27746153
Broadcasting in Faulty Cube-Connected-Cycles with Minimum Recovery Time
We propose a broadcasting algorithm for a faulty Cube-Connected-Cycles multiprocessor. The broadcasting algorithm delivers a message to all the nodes non-redundantly using a binomial tree. The traffic generated because of the recovery is guaranteed to be minimum.
17371165
QoS Routing in Hypercube Multicomputers
In this paper, we present a coding method to capture QoS information in hypercube multicomputers. The coding method is based on a localized algorithm where each node interacts with its neighbors to gather QoS information. Specifically, each node maintains a QoS vector where the k-th element represents the guaranteed QoS performance to a destination that is k hops away. The localized algorithm exhibits desirable properties of self-stabilizing, self-optimizing, and self-healing. Simulation results show that this coding method provides a good approximation of the minimum QoS value to a k-hop destination and, at the same time, uses a relatively small number of packets to propagate a change in link state (QoS value) compared with the classical distributed Bellman-Ford method.
8704620
Improving the reliability of the label distribution protocol
The LDP (label distribution protocol) is used in the control plane to control an optical network. The data plane and the control plane of an optical network could be physically separate. So a failure in the control plane does not necessarily imply a data plane failure and that user communications have to be interrupted. The standard LDP, however, does not provide any mechanism to recover the knowledge stored in LDP entities about the status of the data plane after the faults are fixed. This is a reliability problem of LDP and results in the unnecessary degradation of user communications. On the other hand, in MPLS-enabled IP networks, being able to recover LDP sessions would be potentially faster and more scalable than to re-establish all affected LSPs. The proposed recovery method of LDP for the control plane failures uses label information mirrors (LIMs) in upstream downstream label switching routers (LSRs). Each LIM is a copy of the label information database (LID) in the LSR of an LDP session. We propose a systematic approach to synchronize the contents of a LIM and the corresponding LID, and show how a LIM is used to handle a control plane failure. Detailed descriptions of the recovery procedure for both control channel failures and control node failures are presented. Some significant features of the proposal are outlined.
412675
Linear Asymmetric Classifier for cascade detectors
The detection of faces in images is fundamentally a rare event detection problem. Cascade classifiers provide an efficient computational solution, by leveraging the asymmetry in the distribution of faces vs. non-faces. Training a cascade classifier in turn requires a solution for the following subproblems: Design a classifier for each node in the cascade with very high detection rate but only moderate false positive rate. While there are a few strategies in the literature for indirectly addressing this asymmetric node learning goal, none of them are based on a satisfactory theoretical framework. We present a mathematical characterization of the node-learning problem and describe an effective closed form approximation to the optimal solution, which we call the Linear Asymmetric Classifier (LAC). We first use AdaBoost or AsymBoost to select features, and use LAC to learn a linear discriminant function to achieve the node learning goal. Experimental results on face detection show that LAC can improve the detection performance in comparison to standard methods. We also show that Fisher Discriminant Analysis on the features selected by AdaBoost yields better performance than AdaBoost itself.
36178651
The vertex linear arboricity of distance graphs
A distance graph is a graph G(R,D) with the set of all points of the real line as vertex set and two vertices u,[email protected]?R are adjacent if and only if |u-v|@?D where the distance set D is a subset of the positive real numbers. Here, the vertex linear arboricity of G(R,D) is determined when D is an interval between 1 and @d. In particular, the vertex linear arboricity of integer distance graphs G(D) is discussed, too.
62540784
Customer-managed end-to-end lightpath provisioning
Customer-owned and managed optical networks bring new cost-saving benefits. Two types of such networks are becoming widely used: metro dark fiber networks and long-haul leased wavelength networks. Customers may invoke a special QoS mechanism where end-to-end (E2E) lightpaths are dynamically established across multiple independently managed customer domains. The cost of bandwidth is substantially reduced since it largely becomes a capital cost rather than an ongoing service charge. Customers can optimize the overall resource consumption by utilizing resources from different suppliers. Remote peering and transit reduce the Internet connectivity cost. Bandwidth and quality of service are guaranteed because customers directly peer with each other using transport networks. An architecture for a customer-managed E2E lightpath provisioning system is presented. Integration with Grid applications is discussed and a prototype demonstration is described.
204989501
On clique partitions of split graphs
Abstract Split graphs are graphs formed by taking a complete graph and an empty graph disjoint from it and some or all of the possible edges joining the two. We prove that the problem of deciding the clique partition number is NP-complete, even when restricted to the class of split graphs.