The recent burst growth of the Internet use overloads networking systems and degrades the quality of communications, e.g., bandwidth loss, packet drops, delay of responses, etc. To overcome such degradation of communication quality, the notion of Quality of Service (QoS) has received attention in practice. In general, QoS switches have several queues and each queue has several slots to store arriving packets. Since network traffic changes frequently, QoS switches need to control arriving packets to maximize the total priorities of transmitted packets, where the priorities are given by nonnegative values and correspond to the quality of service required to each packet. In this paper, we first derive the upper bounds for the competitive ratio of multi-queue preemptive QoS problem with priority between 1/α and 1, i.e., for any α ≥ 1, the algorithm TLH is (3-1/α)-competitive. This is a generalization of known results--for the case that packets have only priority 1 (α =1), the algorithm GREEDY (or TLH) is 2-competitive; for the case that packets have priorities between 0 and 1 (α = ∞), the algorithm TLH is 3-competitive. Then we consider the lower bounds for the competitive ratio of multi-queue preemptive QoS problem with priority between 0 and 1, and show that the competitive ratio of any multi-queue preemptive QoS algorithm is at least 1.514.

In this paper, we present an efficient downlink power control scheme, for wireless networks, based on two key ideas: (i) global-local fixed-point-approximation technique (GLOFPAT) and (ii) bottleneck removal criterion (BRC). The proposed scheme copes with all scenarios including infeasible case where no power allocation can provide all multiple accessing users with target quality of service (QoS). For feasible case, the GLOFPAT efficiently computes a desired power allocation which corresponds to the allocation achieved by conventional algorithms. For infeasible case, the GLOFPAT offers valuable information to detect bottleneck users, to be removed based on the BRC, which deteriorate overall QoS. The GLOFPAT is a mathematically-sound distributed algorithm approximating desired power allocation as a unique fixed-point of an isotone mapping. The unique fixed-point of the global mapping is iteratively computed by fixed-point-approximations of multiple distributed local mappings, which can be computed in parallel by base stations respectively. For proper detection of bottleneck users, complete analysis of the GLOFPAT is presented with aid of the Tarski's fixed-point theorem. Extensive simulations demonstrate that the proposed scheme converges faster than the conventional algorithm and successfully increases the number of happy users receiving target QoS.

This paper proposes the Dual Zipfian Model addressing how to describe HTTP access trends in large-scale data communication networks, and discusses how to design the capacity of address cache tables in an edge router of the networks. We show that destination addresses of packets can be characterized by two types of Zipf's law. Fundamental concept of the Dual Zipfian Model is in complementary use of these laws, and we can derive the relationship between the number of accesses and the number of destination addresses. Experimental results show that the relation gives a good approximation. Applying this relation, we derive cache hit probabilities of the address cache table that incorporates high-speed address resolution. Using the probabilities, design issues including the capacity of the cache tables and aging algorithms of cache entries are also discussed.

Due to the recent network service market trends, network infrastructure providers must make their network infrastructures tolerant of network service complexity and swift at providing new network services. To achieve this, we first make a design decision for the single domain network infrastructure in which we use network virtualization and separate the network service control and management from the network infrastructure and leave the resource connectivity control and management in the network infrastructure so that the infrastructure can maintain simplicity and the network service can become complex and be quickly provided. Along with the decision, we construct an architecture of the network infrastructure and a network management model. The management model defines a slice as being determined by abstracted resource requirements and restructures the roles and planes from the viewpoint of network infrastructure usability so that network service requesters can manage network resources freely and swiftly in an abstract manner within the authorities the network infrastructure operator provides. We give the details of our design and implementation for a network virtualization management system along with the model. We deployed and evaluated our designed and implemented management system on the Japan national R&E testbed (JGN-X) to confirm the feasibility of our management system design and discuss room for improvement in terms of response time and scalability towards practical use. We also investigated certain cases of sophisticated network functions to confirm that the infrastructure can accept these functions without having to be modified.

The exciting goals of ubiquitous computing and communication services can only be achieved if we can increase the efficiency with which the location of mobile terminals can be managed; current mobile infrastructures are not efficient since they treat all mobile terminals uniformly despite that fact that many mobiles often move together (i.e. passengers on the same train or a group of cars on a road). This paper presents a hierarchical location management scheme that handles such grouped mobiles collectively and so reduces the overhead costs of location management. In our scheme, mobiles that move together for long enough form a mobile network and make a hierarchy in the wireless access network. The scheme also adjusts the number of mobile networks to keep communication overhead low. We apply the scheme to Mobile IPv6 and evaluate the resulting performance improvement. Simulation results confirm that our hierarchical approach can greatly reduce the overhead costs of location management, and that it is very practical since it can flexibly develop suitable mobile networks.

In high-speed data networks, it is important to execute high-speed address resolution for packets at a router. To accomplish high-speed address resolution, address cache is effective. For HTTP accesses, it has been discussed that the Dual Zipfian Model can describe the distribution of the destination IP addresses, and it enabled us to derive the cache miss ratio in the steady state, i. e. , the cache miss ratio when the cache has full entries. However, at the time that systems are initialized or network topology is changed, the address cache has no address information or invalid address information. This paper shows the compulsory miss ratio which is the cache miss ratio when the cache has no address entry. In addition, we discuss the replacement policies of cache entries, for fast recovery of packet reachability, when the cache has information of unreachable address.

Web APIs are offered in many Web sites for Ajax and mashup, but they have been developed independently since no reusable database component has been specifically created for Web applications. In this paper, we propose WAPDB, a distributed database management system for the rapid development of Web applications. WAPDB is designed on Atom, a set of Web API standards, and provides several of the key features required for Web applications, including efficient access control, an easy extension mechanism, and search and statistics capabilities. By introducing WAPDB, developers are freed from the need to implement these features as well as Web API processing. In addition, its design totally follows the REST architectural style, which gives uniformity and scalability to applications. We develop a proof-of-concept application with WAPDB, and find that it offers great cost effectiveness with no significant impact on performance; in our experiments, the development cost is reduced to less than half with the overhead (in use) of response times of just a few msec.

Many P2P lookup services based on distributed hash tables (DHT) have appeared recently. These schemes are built upon overlay networks and ignore distance to the target resources. As a result, P2P lookups often suffer from unnecessarily long routes in the underlay network, which we call overlay dilation. This paper proposes a new scheme for resource routing, called hybrid hierarchical overlay routing, dubbed Hyho. We introduce distance-weighted Bloom filters (dwBFs) as a concise representation of routing information for scattered resources in overlay networks. To further reduce the size of Bloom filters, so that they are linear in the number of distinct resources, Hyho splits overlay networks in accordance with DHT, where each subnetwork has a smaller set of resources and spans the entire network thinly. As a result, Hyho constructs a hierarchical overlay network and routes requests accordingly. Simulation results show that Hyho can reduce overlay dilation to one half that yielded by the Chord lookup service.

Current Web authentication frameworks have well-known weaknesses. HTTP provides an access authentication framework, but it is rarely used because it lacks presentational control. Forms and cookies, which are most commonly used, have the long-standing privacy issue raised by tracking. URI sessions, which are used in some mobile services like i-mode 1.0, disclose session identifiers unintentionally. This paper proposes iAuth, which integrates better parts of the existing frameworks and fixes their problems; iAuth allows servers to provide log-in forms, and introduces a session header to avoid servers' tracking and unintentional disclosure. Since iAuth has backward compatibility with the major legacy browsers, developers can freely introduce iAuth into their Web sites or browsers as needed. Experiments confirm its correct operation; an iAuth server is shown to support not only an iAuth client but major legacy browsers. We believe that iAuth will resolve the long-standing issues in Web authentication.

Source routing multicast has been gathering much more attention rather than traditional IP multicast, since it is thought to be more scalable in terms of the number of groups at the cost of higher traffic loads. This paper introduces a mathematical framework to analyze the scalability of source routing multicast and IP multicast by leveraging previous multicast studies. We first analyze the amount of data traffic based on the small-world nature of networks, and show that source routing multicast can be as efficient as IP multicast if a simple header fragmentation technique (subgrouping) is utilized. We also analyze scalability in terms of group numbers, which are derived under the equal budget assumption. Our analysis shows that source routing multicast is competitive for low bit-rate streams, like those in the publish/subscribe service, but we find some factors that offset the advantage. This is the first work to analytically investigate the scalability of source routing multicast.