With extremely wide bandwidth and good channel properties, optical fibers have brought fast and reliable data transmission to todays data communications. However, to handle heavy traffic flowing through optical physical links, much faster processing speed is required or else congestion can take place at network nodes. Also, to provide people with voice, data and all categories of multimedia services, distinguishing between different data flows is a requirement. To address these router performance, Quality of Service /Class of Service and traffic engineering issues, Multi-Protocol Label Switching (MPLS) was proposed for IP-based Internetworks. In addition, routers flexible in hardware architecture in order to support ever-evolving protocols and services without causing big infrastructure modification or replacement are also desirable. Therefore, reconfigurable hardware implementation of MPLS was proposed in this project to obtain the overall fast processing speed at network nodes. The long-term goal of this project is to develop a reconfigurable MPLS router, which uniquely integrates the best features of operations being conducted in software and in run-time-reconfigurable hardware. The scope of this thesis includes system architecture and service algorithm considerations, Verilog coding and testing for an actual device. The hardware and software co-design technique was used to partition and schedule the protocol code for execution on both a general-purpose processor and stream-based hardware. A novel RPS scheme that is practically easy to build and can realize pipelined packet-by-packet data transfer at each output was proposed to take the place of the traditional crossbar switching. In RPS, packets with variable lengths can be switched intelligently without performing packet segmentation and reassembly. Primary theoretical analysis of queuing issues was discussed and an improved multiple queue service scheduling policy UD-WRR was proposed, which can reduce packet-waiting time without sacrificing the performance. In order to have the tests carried out appropriately, dedicated circuitry for the MPLS functional block to interface a specific MAC chip was implemented as well. The hardware designs for all functions were realized with a single Field Programmable Gate Array (FPGA) device in this project. The main result presented in this thesis was the MPLS function implementation realizing a major part of layer three routing at the reconfigurable hardware level, which advanced a great step towards the goal of building a router that is both fast and flexible.

With extremely wide bandwidth and good channel properties, optical fibers have brought fast and reliable data transmission to todays data communications. However, to handle heavy traffic flowing through optical physical links, much faster processing speed is required or else congestion can take place at network nodes. Also, to provide people with voice, data and all categories of multimedia services, distinguishing between different data flows is a requirement. To address these router performance, Quality of Service /Class of Service and traffic engineering issues, Multi-Protocol Label Switching (MPLS) was proposed for IP-based Internetworks. In addition, routers flexible in hardware architecture in order to support ever-evolving protocols and services without causing big infrastructure modification or replacement are also desirable. Therefore, reconfigurable hardware implementation of MPLS was proposed in this project to obtain the overall fast processing speed at network nodes. The long-term goal of this project is to develop a reconfigurable MPLS router, which uniquely integrates the best features of operations being conducted in software and in run-time-reconfigurable hardware. The scope of this thesis includes system architecture and service algorithm considerations, Verilog coding and testing for an actual device. The hardware and software co-design technique was used to partition and schedule the protocol code for execution on both a general-purpose processor and stream-based hardware. A novel RPS scheme that is practically easy to build and can realize pipelined packet-by-packet data transfer at each output was proposed to take the place of the traditional crossbar switching. In RPS, packets with variable lengths can be switched intelligently without performing packet segmentation and reassembly. Primary theoretical analysis of queuing issues was discussed and an improved multiple queue service scheduling policy UD-WRR was proposed, which can reduce packet-waiting time without sacrificing the performance. In order to have the tests carried out appropriately, dedicated circuitry for the MPLS functional block to interface a specific MAC chip was implemented as well. The hardware designs for all functions were realized with a single Field Programmable Gate Array (FPGA) device in this project. The main result presented in this thesis was the MPLS function implementation realizing a major part of layer three routing at the reconfigurable hardware level, which advanced a great step towards the goal of building a router that is both fast and flexible.

This dissertation focuses on service scheduling and transshipment problems. The study of service scheduling is motivated by decisions facing service planners, who must inspect and maintain geographically dispersed infrastructure facilities. We study the problem of deciding which operations a service unit must perform at each customer location, given the sequence in which the unit periodically visits these locations. Each customer requires multiple service operations, and each operation has a time-varying completion or penalty cost that depends on the previous service time. The goal is to schedule the service start time for each customer and select the operations to perform so as to minimize the total completion cost. We first discuss how to solve a special case of this problem in which each site is visited only once per service cycle. We formulate this problem as a discrete time indexed network flow problem and prove that it is NP-hard in the ordinary sense. Then, we represent the problem as a multidimensional shortest path problem with path-dependent arc lengths. In this structure, arc costs depend on the total time spent for all customers. The resulting formulation is solvable via algorithms that have pseudo-polynomial run times. Computational results show that the shortest path approach outperformed the general network flow model. We then analyze the general case of this problem, in which each site can be visited more than once and prove that the problem is NP-Hard in the strong sense. We discuss the valid cuts and describe the preprocessor that reduces the problem size. Next, we examine an application to the general case of the problem and develop a fast and effective heuristic procedure that repeatedly applies the shortest path approach to subsequences that do not visit any customer more than once. Computational results for several problem instances show that the proposed heuristic identifies near optimal results very quickly, whereas a general purpose integer-programming solver (CPLEX) is not able to find an optimal solution even after many hours of computational time. Then we focus on techniques such as problem reduction, branching variables, and subdividing problem to smaller problems to get better solution times for the actual problem. Computational results show that these techniques can improve solution times substantially. Finally, we study a transshipment problem, in which the shipments need to be transported from their origin to destination and are subject to the logical and physical transportation network on which they rely. We consider a space-time network that allows one to formulate the problem as a multi-commodity network flow problem with additional side constraints and show the complexity results. We propose alternative models and propose algorithms for lower and upper bound calculations. / text

The third generation of mobile communication systems introduce interactive Multicast and Unicast multimedia services at a fast data rate of up to 2 Mbps and is expected to complete the globalization of the mobile telecommunication systems. The implementation of these services on satellite systems, particularly for broadcast and multicast applications to complement terrestrial services is ideal since satellite systems are capable of providing global coverage in areas not served by terrestrial telecommunication services. However, the main bottleneck of such systems is the scarcity of radio resources for supporting multimedia applications which has resulted in the rapid growth in research efforts for deriving efficient radio resource management techniques. This issue is addressed in this thesis, where the main emphasis is to design a dynamic scheduling framework and algorithm that can improve the overall performance of the radio resource management strategy of a UMTS compatible satellite network, taking into account the unique characteristics of wireless channel conditions. This thesis will initially be focused on the design of the network and functional architecture of a UMTS -compatible satellite network. Based on this architecture, an effective scheduling framework is designed, which can provide different types of resource assigning strategies. A functional model of scheduler is defined to describe the behaviours and interactions between different functional entities. An OPNET simulation model with a complete network protocol stack is developed to validate the performance of the scheduling algorithms implemented in the satellite network. Different types of traffic are considered for the OPNET simulation, such as the Poisson Process, ONOFF Source and Self Similar Process, so that the performance of scheduling algorithm can be analyzed for different types of services. A novel scheduling algorithm is proposed to optimise the channel utilisation by considering the characteristics of the wireless channel, which are bursty and location dependent. In order to overcome the channel errors, different code rates are applied for the user under different channel conditions. The proposed scheduling algorithm is designed to give higher priority to users with higher code rate, so that the throughput of network is optimized and at the same time, maintaining the end users' service level agreements. The fairness of the proposed scheduling algorithm is validated using OPNET simulation. The simulation results show that the algorithm can fairly allocate resource to different connections not only among different service classes but also within the same service class depending on their QoS attributes.