Networks with Extended Quality of Service using Service Vectors
Sponsor: National Science Foundation
Research and Education Activities:
	1. Decoupling End-to-End Provisioning A novel distributed end-to-end QoS provisioning architecture based on the concept of decoupling the end-to-end QoS provisioning from the service provisioning at routers in the Diffserv network has been proposed and investigated. The main objective of this architecture is to enhance the QoS granularity and flexibility offered by the Diffserv network model, and to improve both the network resource utilization and user benefits. This architecture consists of a new endpoint admission control referred to as Explicit Endpoint Admission Control at the user side, the service vector concept, which allows a data flow to choose different services at different routers along its data path, and a packet marking architecture and algorithm at the router side. The applicability of such an approach in wireless networks is also part of our current research activities. 2. Refining the Service Vector Paradigm: QoS Routing We have investigated a problem referred to as the least hop multiple-additively-constrained path (LHMACP) routing to find paths for services with different classes. We then proposed the k-shortest paths Extended Bellman-Ford (k-EB) algorithm to compute All Hops k-shortest Paths (AHKP) between a source and a destination. Additionally, we have developed an effective heuristic algorithm, based on k-EB, in finding a least hop path subject to multiple additive constraints with very low computational complexity; it achieves near 100% success ratio in finding a feasible path while minimizing its average hop count. 3. Pricing In order to efficiently and effectively use network resources, we have investigated the issue of integrating pricing into QoS routing and propose a PRicing InCEntive QoS Routing (PRICER) mechanism. PRICER consists of two components: a novel Routing-Oriented State updatE (ROSE) scheme and an efficient Pricing Incentive Routing Algorithm (PIRA). ROSE performs the task of exchanging link state information throughout the network, and PIRA is a routing algorithm used to find paths meeting the QoS requirements of applications. PIRA can guarantee finding the QoS constrained path with fairly low average computational complexity. The most distinguished property of PIRA is its progressive property, which is very useful in practice: it can self-adaptively minimize its computational complexity without sacrificing its performance. Another contribution of this paper is the introduction of a method to numerically evaluate the staleness of link state information. 4. Security We have proposed a network security framework, referred to as Security-enhanced Quality of Service (SQoS) with two major objectives. One objective is to offer the users elastic choices on the treatment of messages with appropriate security mechanisms with respect to their own QoS and budget requirements. Another objective is to facilitate interaction between security and QoS mechanisms in the most efficient manner by providing information to each other and performing tasks requested by each other. 5. Switches for Next Generation Routers 5.1 Load-Balanced Combined Input-Crosspoint Buffered Switch As the number of services supported by the next generation networks increases, we consider that switching strategies need to be superior to current proposed approaches. We consider that Combined Input-Crosspoint Buffered Switches are the solution to this need. In this research topic, we investigated a novel architecture that has promising performance and features. The amount of memory in buffered crossbars is proportional to the number of crosspoints, or O(N^2), where N is the number of ports, and to the crosspoint buffer size, which is defined by the distance between the line cards and the buffered crossbar, to achieve 100% throughput under high-speed data flows. A long distance between these two components can make a buffered crossbar costly to implement. We developed a novel load-balanced combined input-crosspoint buffered packet switch that uses small crosspoint buffers and no speedup. The proposed switch reduces the required size of the crosspoint buffers by a factor of N and keeps the cells in sequence. We have expanded the study of the load-balanced switch into a family of switch architectures that we called buffered crossbar switch with flexible crosspoint-buffer access as we created several mechanisms for an input to forward a packet not only to the corresponding crosspoint buffer but to any crosspoint buffer for the destined output. 5.2 Shared-Memory Buffered Crosspoint Switch We also developed a solution for using crosspoint buffers with shared memory. We proposed a new switch that uses no speedup and supports twice the round-trip time with a given crosspoint buffer size, or given with different words, the novel architecture uses 50% memory of that combined input-crosspoint buffered switches while delivering the same performance. The combination of works described in 5.1 and 5.2 opens a new path for investigation as two new packet switch architectures have been proposed. These works also show that higher switching performance can be achieved with practical and new switch architectures. We expect to use these architectures in the support of service vector networks. Using the shared-memory architecture, we focus on providing differentiated services, where traffic is assigned different switching priorities. High priority cells are from delay sensitive traffic such as voice and video. They need to be served prior to other traffic classes to minimize queueing delay within the switch. With the shared-memory switch, we study the service of differentiated traffic and the impact of the sharing of memory at the crosspoint buffers in terms of throughput and average packet delay. We compare the results of the shared-memory switch to those of a switch with dedicated buffers. 6. Next Generation Routers: Analysis of a Flow Control Mechanism A flow control mechanism is used in combined input-crosspoint buffered (CICB) switches to avoid buffer overflow and underflow. Credit-based flow control is widely used in CICB switches to reduce the required crosspoint-buffer size. For simplification, we analyzed a flow control mechanism with active queue management (AQM) and a proportional controller. We showed that the flow control mechanism is stable for small crosspoint buffer sizes and non-negligible round-trip times. In addition, we observed the effect of an input shaper combined with a proportional controller. We showed that the input shaper reduces the response time of the flow control mechanism. 7. Wireless Networks We have implemented large scale wireless network simulations in our OPNET platform. Our networks include ad hoc and infrastructure networks. The models have realistic channels and mobility patterns built in. The cellular model is a CDMA based 3G network. We have vetted simulations with numerical analysis where possible. Our analytical models are implemented using MATLAB. The work has generated research presented towards a Master of Science degree and part of the research towards a PhD degree, both produced within the last year. 8. Coprocessor Design The Message Passing Interface (MPI) is a widely used standard for inter-processor communication in parallel and cluster computers. Its numerous functions are normally implemented in software, thus resulting in large communication latencies. A hardware implementation could reduce communication latencies significantly, thereby increasing the bandwidth. However, this approach cannot be applied in practice to the very large set of functions in MPI. Reconfigurable computing has reached levels where entire parallel systems can be built inside one or more FPGAs (Field-Programmable Gate Arrays). However, specialized components must be built to support communications in each design and the resulting code may be difficult to port to other reconfigurable platforms. In addition, direct performance comparison with conventional parallel computers or PC clusters is not possible since the latter often employ MPI. Introducing MPI primitives in reconfigurable computing creates a framework for efficient parallel code development involving data exchanges independently of the underlying hardware implementation. This paper presents the design and evaluation of a coprocessor that implements a set of MPI primitives. These primitives form a universal and orthogonal set that can be used to implement any other MPI function. A router that can be used to interconnect many such coprocessors in order to build multi-processor systems is also designed and implemented. The performance results justify the implementation of MPI primitives in hardware to support parallel processing with reconfigurable computing. FPGA-based designs to measure essential network parameters have been our objective. More specifically, we have dealt with three relevant schemes: l D1: Calculation of packet loss and one-way network delay using RTP over UDP. l D2: Using the concept of TOPPs (Train of Packet Pairs), we provide a measurement of the available bandwidth. l D3: Partial implementation of the TCP protocol that can be developed further to measure packet loss and network delay. 9. Including Security Metrics in the QoS Set Security and QoS systems have traditionally been considered separately with different objectives and implementation architectures. No protocol has been designed and implemented so far to parameterize security as QoS parameters. However, it has been noted recently that security and QoS are highly intertwined; security mechanisms may severely affect QoS mechanisms in terms of network performance and data confidentiality. Security mechanisms can actually be strengthened and enhanced with information obtained by the QoS system. On the other hand, malicious activities on the network such as DoS attacks, Denial-of-QoS attacks, and the bandwidth stealth diminish the QoS performance significantly. With a secure system, network QoS may still be guaranteed even under the attack. In addition, the users are not given the choices on which security services and mechanisms as well as which security level should be applied to the user traffics. The security-enhanced quality of service-based network has been presented with two major objectives. First, the SQoS network aims to enable cooperation between security and QoS mechanisms to boost the network performance. Second, the users have more options to configure the preferred security services and service degrees for their traffics. Consequently, the ISPs can assign more accurate resources and improve the resource utilization. The SQoS network aims to achieve two major advantages: first, cooperation between security and QoS mechanisms to boost the network performance; second, the SQoS network aims to allow users to configure the preferred security services and service degrees for their traffics. 10. Crosslayer Design for QoS Support We have been working on cross-layer design for energy-efficient quality-of-service support in multihop wireless networks. In the early part, we have characterized the relationship between hop progress and Euclidean distance covered in greedy forwarding approach. We have been working on a generalized power consumption model where the transitions between different states of a node are modeled as a semi-Markov decision process. Along this line, a new receiver-side relay election scheme is being investigated, where the distance coverage bounds on greedy forwarding are used. Observing the fact that the unit-disk coverage does not hold in practice in wireless networks and that there could be additional constraints in electing a relay node, we have been working on multi-criteria based receiver election approach. As a first step, we have been considering the error performance along with the hop progress in electing an optimum relay node. Power control features and its impact on interference are also being investigated. 11. Network State Measurements To provide good QoS in a computer network, robust means to measure essential network parameters are required. A multitude of options are available to perform this task. We have implemented on FPGAs (Field-Programmable Gate Arrays) three such schemes. The first scheme calculates the packet loss and one-way network delay using RTP over UDP; the second one uses the concept of TOPPs (Train of Packet Pairs) to measure the available bandwidth, and the third one is a partial implementation of TCP, which can be developed further to measure various parameters. Our analysis showed that these implementations can carry out efficient parameter measurements at reasonable hardware cost. In addition, our benchmarks compared three hashing schemes for storing TCP tuple information in an effort to support tradeoffs in the design of such systems. 12. Network-based Grid Computing Scalability has become an attribute of paramount importance for network-based computer systems targeting business, scientific and engineering applications. Previous scalability analyses conveniently focused on improving performance when increasing the number of computing nodes. Since the primary objective of scalability analysis is to determine how well a system can work on larger problems with an increase in its size, we introduced a generic definition of scalability. For illustrative purposes, we applied this definition to PC clusters, a rather difficult subject due to their long communication latencies. 13. Multiple Additively Contraints for QoS Networks We have investigated the problem of providing the theoretical framework for selecting a cost function for multiple additively constrained QoS routing that can improve performance of source routing. Simulation is done in two network topologies. 14. Link-State Update for QoS Routing We proposed a theoretical framework for link state update, from which a high performance link state update mechanism is also proposed. We theoretically demonstrate that from the perspective of QoS routing, our proposed link state policy outperforms contender schemes in terms of the update rate and false blocking probability of incoming connections. Extensive simulation was also performed to show experimental results for numerical comparisons. 15. Improving Accuracy of Service Vectors with Packet Marking We investigated a packet marking mechanism and developed an efficient packet marking solution that is suitable for various types of QoS constraints. We assume that for any given QoS constraint, the probability distribution of users' requirement is known a priori. That is, taking the delay constraint as an example, the percentage of users that request network connections with end-to-end delay smaller than x is assumed to be known, where x is in the unit of time. This assumption can be justified by the fact that the probability distributions of user requirements can be obtained from user profiles and from the past experience of network operations. Furthermore, we assume that the probability distributions of all QoS performance measurements of each service class in each node are known. Analysis and simulation were performed. 16. Service Vectors for QoS in Wireless Networks The Service Vector paradigm is extended to wireless ad hoc networks. A cross-layer architecture based on the combination of the service vector scheme and delay bounded link level scheduling has been designed. We demonstrated through modeling and simulation that within this architecture the service vector scheme can provide significant power savings as well as better QoS granularity in wireless ad hoc networks. 17. Shared Memory Switch for Service Vector Networks We have developed a shared memory crosspoint-buffered switch able to switch differentiated traffic that uses service vectors in the classifications of classes. We have study the performance of such switch under different traffic scenarios using computer simulation. The results have been presented in an international conference. 18. Switching and Replication of Multicast traffic We have investigated the replication of multicast packet using the broadcasting properties of a crossbar in a shared-memory crosspoint-buffered switch. For this, we have developed a set of simple and implementable schemes for arbitration of packet from the crosspoint buffers to the output ports. We have tested the switch and arbitration schemes under multicast traffic patterns using extensive computer simulation. 19. Scaling up Scheduling Schemes for High Capacity Switches We have proposed a matching scheme for Clos-network switches with input queuing to make the implementation of very large size switches (in terms of the number of ports) feasible. As Clos-network switches use switch modules to implement one large switch, the matching scheme follows the same architecture by matching in traffic that is dispersed (and aggregated) by modules. We performed computer simulations of the proposed scheme to observe the switching performance and the scalability trend. We called this scheme, module-to-module matching. 20. Active Probing for Measurement of Link State in QoS Networks To measure the multiclass QoS link state, we have developed a distributed real-time per-link QoS measurement system, where each router or the equipment directly connected to the router can send probing packets to launch active measurement processes or passively monitor the incoming traffic. Either using active method or passive is in fucntion of the traffic load of the network. Probing packets are assigned with various service classes so as to measure the accurate state of each service level. Analysis, simulation, and experimentation in our testbed were performed for this activity. 21. Greedy Routing for Ad-Hoc Wireless Networks Traditional purely greedy forwarding in wireless ad hoc networks is not optimal in most practical settings where perfect-reception-within-range cannot be assumed. Although a few link-aware routing schemes have been reported, the tradeoff between greediness and link quality has not been studied. In this research activity, we took a multi-criteria based receiver-side relay election approach in wireless multi-hop forwarding, where a single optimal node is elected among many candidates to relay packets toward the final destination. We introduced a general cost metric in the form of a multi-parameter mapping function that aggregates all decision criteria into a single virtual criterion to rank potential relay candidates. We showed that a suitable mapping function can be found, which trades off greediness for link quality to obtain optimal end-to-end network performance. Compared with the previously reported link-aware forwarding schemes, our results showed a better energy performance and a substantial improvement in end-to-end delay. 22. Transmission Power in Ad-Hoc Wireless Networks In this work, we studied the issue of transmission power control (TPC) in wireless ad hoc networks. Power control plays an important role in energy saving and network performance enhancement. However, the existing TPC schemes either face the problem of hidden and exposed terminal or have additional hardware requirements. We proposed a novel distributed power control protocol, called Receiver Initiated power control Multi-Access (RIMA) that ideally eliminates the hidden terminal problem and at the same time enjoys the same single channel, single-transceiver design of nodes in IEEE 802.11 and 802.15 MAC standards. An enhanced version of RIMA was also proposed where reduced power RTS transmission is allowed to improve spatial reuse of the wireless channel. Simulations were performed to demonstrate the enhanced frame loss rate and network delay performance of the proposed approach with respect to a competitive approach, called transmitter initiated power control MAC protocol.
Back