With the advancement of semiconductor technology, the System on Chip (SoC) is becoming more and more complex, so the on-chip communication has become a bottleneck of SoC Design. Since the traditional bus system is inefficient and not scalable, the Network-On-Chip (NoC) has emerged as the promising communication mechanism for complex SoCs. As some systems have specific performance requirements, such as a minimum throughput (for real-time streaming data) or bounded latency (for interrupts, process synchronization, etc), communication with Guaranteed Service (GS) support becomes crucial for predictable SoC architectures. Circuit Switching (CS) is a popular approach to support GS, which firstly has to allocate an exclusively connection (circuit) between the source and destination nodes, and then the data packets are delivered over this connection. However, it is inefficient and inflexible because the resource is occupied by single connection during its whole lifetime, which can block other communications. Hence, two extensions of CS have been proposed to share resources: i) Time-Division Multiplexing (TDM), in which the available link capacity is split into multiple time slots to be shared by different flows in TDM scheme; and ii) Space-Division-Multiplexing (SDM), in which only a subset (sub-channel) of the link wires is exclusively allocated to a specific connection, while the remaining wires of the link can be used by other flows. The connection allocation is critical for CS, since the data delivery can start only after the associated connection is allocated. In this thesis, we propose a dedicated hardware connection allocator to solve the dynamic connection allocation problem for CS NoCs, which has to i) allocate a contention-free path between source-destination pairs and ii) allocate appropriate portions of link bandwidth (appropriate number of time slots and subsets) along the path. The dedicated connection allocator, called NoCManager, solves the connection allocation problem by employing a trellis-search based shortest path algorithm. The trellis search can explore all possible paths between source node and destination. Moreover, it shall find the requested path in a fixed low latency and can guarantee the path optimality in terms of path length if the path is available. In this thesis, two different trellis graphs, Forward-Backtrack trellis and Register-Exchange trellis are proposed. The Forward-Backtrack trellis completes the path search in two steps: forward search and backtracking. Firstly, the forward search begins at source node that traverses the network to find the free path. When destination node is reached, the backtrack starts from destination to select the survivor path and collect the associated path parameters. However, Register-Exchange trellis saves the entire survivor path sequences during forward search. Consequently, the backtracking step can be omitted, and thus the allocation time is halved compared to forward-backtrack approaches. Moreover, each trellis graph consists of three categories, unfolded structure, folded structure and bidirectional structure. The unfolded structure can provide high allocation speed while folded structure is more efficient from a hardware point of view. The bidirectional structure starts the search at two sides, source node and destination node simultaneously, so the allocation speed is 2 times faster than previous unidirectional search. Furthermore, in order to address the scalability issue of previous centralized systems, the partitioned architecture (i.e. spatial partitioning technique) is proposed to divide the large system into multiple smaller differentiated logical partitions served by local NoCManagers. This partitioning technique keeps the request load of the manager and manager-node communication overhead moderate. Inside each partition, the path search problem is solved by a local manager with trellis-search algorithm. To establish a path that crosses partitions, the managers communicate with each other in distributed manner to converge the global path. In order to further enhance the path diversity and resource utilization, we adopt the combined TDM and SDM technique. In combined TDM-SDM approach, each SDM sub-channel is split into multiple time slots so that can be shared by multiple flows. Hence, the number of sub-channels can be kept moderate to reduce router complexity, while still providing higher path diversity than TDM scheme. In order to investigate and optimize TDM-SDM partitioning strategy, we studied the influence of different TDM-SDM link partitioning strategies on success rate and path length that allowed us to find the optimal solution. The dedicated connection allocator using the trellis-search algorithm is employed for TDM, SDM and TDM-SDM CS. In the end, we present the router architecture that combines the circuit-switching network (for GS communication) and packet-switching network (for best-effort communication).

No description available.

With the advancement of semiconductor technology, the System on Chip (SoC) is becoming more and more complex, so the on-chip communication has become a bottleneck of SoC Design. Since the traditional bus system is inefficient and not scalable, the Network-On-Chip (NoC) has emerged as the promising communication mechanism for complex SoCs. As some systems have specific performance requirements, such as a minimum throughput (for real-time streaming data) or bounded latency (for interrupts, process synchronization, etc), communication with Guaranteed Service (GS) support becomes crucial for predictable SoC architectures. Circuit Switching (CS) is a popular approach to support GS, which firstly has to allocate an exclusively connection (circuit) between the source and destination nodes, and then the data packets are delivered over this connection. However, it is inefficient and inflexible because the resource is occupied by single connection during its whole lifetime, which can block other communications. Hence, two extensions of CS have been proposed to share resources: i) Time-Division Multiplexing (TDM), in which the available link capacity is split into multiple time slots to be shared by different flows in TDM scheme; and ii) Space-Division-Multiplexing (SDM), in which only a subset (sub-channel) of the link wires is exclusively allocated to a specific connection, while the remaining wires of the link can be used by other flows. The connection allocation is critical for CS, since the data delivery can start only after the associated connection is allocated. In this thesis, we propose a dedicated hardware connection allocator to solve the dynamic connection allocation problem for CS NoCs, which has to i) allocate a contention-free path between source-destination pairs and ii) allocate appropriate portions of link bandwidth (appropriate number of time slots and subsets) along the path. The dedicated connection allocator, called NoCManager, solves the connection allocation problem by employing a trellis-search based shortest path algorithm. The trellis search can explore all possible paths between source node and destination. Moreover, it shall find the requested path in a fixed low latency and can guarantee the path optimality in terms of path length if the path is available. In this thesis, two different trellis graphs, Forward-Backtrack trellis and Register-Exchange trellis are proposed. The Forward-Backtrack trellis completes the path search in two steps: forward search and backtracking. Firstly, the forward search begins at source node that traverses the network to find the free path. When destination node is reached, the backtrack starts from destination to select the survivor path and collect the associated path parameters. However, Register-Exchange trellis saves the entire survivor path sequences during forward search. Consequently, the backtracking step can be omitted, and thus the allocation time is halved compared to forward-backtrack approaches. Moreover, each trellis graph consists of three categories, unfolded structure, folded structure and bidirectional structure. The unfolded structure can provide high allocation speed while folded structure is more efficient from a hardware point of view. The bidirectional structure starts the search at two sides, source node and destination node simultaneously, so the allocation speed is 2 times faster than previous unidirectional search. Furthermore, in order to address the scalability issue of previous centralized systems, the partitioned architecture (i.e. spatial partitioning technique) is proposed to divide the large system into multiple smaller differentiated logical partitions served by local NoCManagers. This partitioning technique keeps the request load of the manager and manager-node communication overhead moderate. Inside each partition, the path search problem is solved by a local manager with trellis-search algorithm. To establish a path that crosses partitions, the managers communicate with each other in distributed manner to converge the global path. In order to further enhance the path diversity and resource utilization, we adopt the combined TDM and SDM technique. In combined TDM-SDM approach, each SDM sub-channel is split into multiple time slots so that can be shared by multiple flows. Hence, the number of sub-channels can be kept moderate to reduce router complexity, while still providing higher path diversity than TDM scheme. In order to investigate and optimize TDM-SDM partitioning strategy, we studied the influence of different TDM-SDM link partitioning strategies on success rate and path length that allowed us to find the optimal solution. The dedicated connection allocator using the trellis-search algorithm is employed for TDM, SDM and TDM-SDM CS. In the end, we present the router architecture that combines the circuit-switching network (for GS communication) and packet-switching network (for best-effort communication).

No description available.

No description available.

Optical networking, employing wavelength division multiplexing (WDM), is seen as the technology of the future for the Internet. This dissertation investigates several important problems affecting optical circuit switching (OCS) and optical burst switching (OBS) networks. Novel algorithms and new approaches to improve the performance of these networks through effective routing and channel scheduling are presented. Extensive simulations and analytical modeling have both been used to evaluate the effectiveness of the proposed algorithms in achieving lower blocking probability, better fairness as well as faster switching. The simulation tests were performed over a variety of optical network topologies including the ring and mesh topologies, the U.S. Long-Haul topology, the Abilene high-speed optical network used in Internet 2, the Toronto Metropolitan topology and the European Optical topology. Optical routing protocols previously published in the literature have largely ignored the noise and timing jitter accumulation caused by cascading several wavelength conversions along the lightpath of the data burst. This dissertation has identified and evaluated a new constraint, called the wavelength conversion cascading constraint. According to this constraint, the deployment of wavelength converters in future optical networks will be constrained by a bound on the number of wavelength conversions that a signal can go through when it is switched all-optically from the source to the destination. Extensive simulation results have conclusively demonstrated that the presence of this constraint causes significant performance deterioration in existing routing and wavelength assignment (RWA) algorithms. Higher blocking probability and/or worse fairness have been observed for existing RWA algorithms when the cascading constraint is not ignored. To counteract the negative side effect of the cascading constraint, two constraint-aware routing algorithms are proposed for OCS networks: the desirable greedy algorithm and the weighted adaptive algorithm. The two algorithms perform source routing using link connectivity and the global state information of each wavelength. Extensive comparative simulation results have illustrated that by limiting the negative cascading impact to the minimum extent practicable, the proposed approaches can dramatically decrease the blocking probability for a variety of optical network topologies. The dissertation has developed a suite of three fairness-improving adaptive routing algorithms in OBS networks. The adaptive routing schemes consider the transient link congestion at the moment when bursts arrive and use this information to reduce the overall burst loss probability. The proposed schemes also resolve the intrinsic unfairness defect of existing popular signaling protocols. The extensive simulation results have shown that the proposed schemes generally outperform the popular shortest path routing algorithm and the improvement could be substantial. A two-dimensional Markov chain analytical model has also been developed and used to analyze the burst loss probabilities for symmetrical ring networks. The accuracy of the model has been validated by simulation. Effective proactive routing and preemptive channel scheduling have also been proposed to address the conversion cascading constraint in OBS environments. The proactive routing adapts the fairness-improving adaptive routing mentioned earlier to the environment of cascaded wavelength conversions. On the other hand, the preemptive channel scheduling approach uses a dynamic priority for each burst based on the constraint threshold and the current number of performed wavelength conversions. Empirical results have proved that when the cascading constraint is present, both approaches would not only decrease the burst loss rates greatly, but also improve the transmission fairness among bursts with different hop counts to a large extent.

No

abstract: The upstream transmission of bulk data files in Ethernet passive optical networks (EPONs) arises from a number of applications, such as data back-up and multimedia file upload. Existing upstream transmission approaches lead to severe delays for conventional packet traffic when best-effort file and packet traffic are mixed. I propose and evaluate an exclusive interval for bulk transfer (EIBT) transmission strategy that reserves an EIBT for file traffic in an EPON polling cycle. I optimize the duration of the EIBT to minimize a weighted sum of packet and file delays. Through mathematical delay analysis and verifying simulation, it is demonstrated that the EIBT approach preserves small delays for packet traffic while efficiently serving bulk data file transfers. Dynamic circuits are well suited for applications that require predictable service with a constant bit rate for a prescribed period of time, such as demanding e-science applications. Past research on upstream transmission in passive optical networks (PONs) has mainly considered packet-switched traffic and has focused on optimizing packet-level performance metrics, such as reducing mean delay. This study proposes and evaluates a dynamic circuit and packet PON (DyCaPPON) that provides dynamic circuits along with packet-switched service. DyCaPPON provides (i) flexible packet-switched service through dynamic bandwidth allocation in periodic polling cycles, and (ii) consistent circuit service by allocating each active circuit a fixed-duration upstream transmission window during each fixed-duration polling cycle. I analyze circuit-level performance metrics, including the blocking probability of dynamic circuit requests in DyCaPPON through a stochastic knapsack-based analysis. Through this analysis I also determine the bandwidth occupied by admitted circuits. The remaining bandwidth is available for packet traffic and I analyze the resulting mean delay of packet traffic. Through extensive numerical evaluations and verifying simulations, the circuit blocking and packet delay trade-offs in DyCaPPON is demonstrated. An extended version of the DyCaPPON designed for light traffic situation is introduced in this article as well. / Dissertation/Thesis / Ph.D. Electrical Engineering 2014

Due to the tremendous growth of traffic volume caused by both exponential increase of number of Internet users and continual emergence of new bandwidth demanding applications, high capacity networks are required in order to satisfactorily handle the extremely large amount of traffic. Hence, optical fiber communication is the key technology for the network infrastructure. This thesis addresses design, analysis and simulation of access and core networks targeting important research problems, which need to be tackled for the effective realization of next generation optical networks. Among different fiber access architectures, passive optical network (PON) is considered as the most promising alternative for the last mile connection due to its relatively low cost and resource efficiency. The inherent bursty nature of the user generated traffic results in dynamically changing bandwidth demand on per subscriber basis. In addition, access networks are required to support differentiated quality of service and accommodate multiple service providers. To address these problems we proposed three novel scheduling algorithms to efficiently realize dynamic bandwidth allocation in PON, along with guaranteeing both the priority and fairness of the differentiated services among multiple users and/or service providers. Meanwhile, because of the increasing significance of reliable access to network services, an efficient fault management mechanism needs to be provided in PON. In addition, access networks are very cost sensitive and the cost of protection should be kept as low as possible. Therefore, we proposed three novel cost-effective protection architectures keeping in mind that reliability requirement in access networks should be satisfied at the minimal cost. Regarding the optical core networks, replacing electronic routers with all-optical switching nodes can offer significant advantages in realizing high capacity networks. Because of the technological limitations for realizing all-optical nodes, the focus is put on the ingenious architecture design. Therefore, we contributed on novel switching node architectures for optical circuit and packet switching networks. Furthermore, we addressed different aspects of routing and wavelength assignment (RWA) problem, which is an important and hard task to be solved in wavelength routed networks. First, we proposed an approach based on the information summary protocol to reduce the large amount of control overhead needed for dissemination of the link state information in the case of adaptive routing. In addition, transparency in optical networks may cause vulnerability to physical layer attacks. To target this critical security related issue, we proposed an RWA solution to minimize the possible reachability of a jamming attack. Finally, in order to evaluate our ideas we developed two tailor-made simulators based on discrete event driven system for the detailed studies of PON and switched optical networks. Moreover, the proposed tabu search heuristic for our RWA solution was implemented in C++. / QC 20100707

Este trabalho consiste na especificação e desenvolvimento da arquitetura de um Comutador Digital para TDM Determinístico E1, visando sua posterior implementação em microeletrônica. Inicialmente são apresentados os conceitos gerais sobre os Sistemas de Comutação, bem como das principais modalidades de comutação, seguidos de um estudo aprofundado da Comutação de Circuitos e suas técnicas mais utilizadas, devido a sua Intima relação com a multiplexação TDM e a hierarquia E1. Do mesmo modo, são descritas as características das Redes Corporativas E1 e dos multiplexadores E1, junto com as funções principais do Comutador dentro do ambiente de uma rede ponto-a-ponto. Com base no estudo prévio, e proposta a arquitetura de um Comutador Digital baseado em técnicas TSI capaz de fornecer funções de comutação local e remota entre os dispositivos conectados aos multiplexadores El, que formam os nos de uma Rede Corporativa com controle centralizado. 0 projeto logico e a simulação do Comutador Digital foram realizados dentro do framework SOLO/Cadence, usando a biblioteca de Standard Cells da tecnologia CMOS de 1.2µ. O simulador lógica SILOS, disponível no SOLO/Cadence, foi utilizado para validar a arquitetura proposta. Detalhes de implementação e resultados de simulação são apresentados. O módulo de controle do Comutador Digital e apenas especificado. / This work consists in the specification and development of a Digital Circuit Switch architecture for E1l Deterministic TDM, looking toward a future microelectronics implementation. First, general concepts about Switching Systems and its basic elements, as well as the main kinds of switching are presented. Also, a meticulous study about Circuit Switching and its more used techniques is realized, because of the intrinsec relation with TDM and E1 hierarchy. In the same way, the characteristics of E1 Corporate Networks and E1 multiplexers are described, along with the main functions of the Digital Switch into an end-to-end network. Taking into account the previous study, the architecture of a Digital Switch based on TSI techniques, is proposed. This architecture is able to perform local and remote switching between the devices connected to E1 multiplexers, which form the network nodes of an end-to-end Corporate Network. The logic design and the circuit simulation of the Digital Switch were performed within SOLO/Cadence Standard Cells desing framework, using CMOS 1.2µ technology. The logic simulator SILOS was used to validate the proposed architecture. Implementation details and simulation results are presented. The Control module of the Digital Switch is only specified.