Browsing by Subject "Computer network protocols"
Now showing 1 - 4 of 4
- Results Per Page
- Sort Options
Item Addressing the memory bottleneck in packet processing systems(2005) Mudigonda, Jayaram; Vin, Harrick M.The design of packet processing systems is guided by two requirements: (1) high packet processing throughput, and (2) ease-of-programming. Meeting these two requirements simultaneously has proved to be challenging primarily because, packet processing aggravates the well-known problem of memory bottleneck. To overcome the memory bottleneck, today’s packet processing systems support a wide-range of mechanisms such as exposed memory hierarchy, multithreading, and non-blocking multi-word accesses. However, supporting many such mechanisms without clear guidelines for their usage complicates programmability and wastes system resources. In this dissertation, we ask two fundamental questions: (1) what minimal set of mechanisms should a packet processing system support to simultaneously achieve the goals of high throughput and ease-of-programming? and (2) how should one allocate common system resources such as chip area and off-chip memory bandwidth to these competing mechanisms? We make three contributions. First, we demonstrate that the minimal set must include data caches and multithreading for two reasons: (1) contrary to the widely-held belief, packet proviii cessing exhibits considerable data locality and (2) relying exclusively on either data locality or packet-level parallelism leads to low packet throughput. Second, we demonstrate that no fixed configuration of caches and multithreading works well across a spectrum of deployments (combinations of application, workload, and system characteristics). Achieving high throughput in all cases requires a malleable architecture that allows deployments to trade off resources between data caching and multithreading. Third, we develop such a malleable architecture based on a novel predictive register prefetcher that efficiently overlaps the execution of a thread with the thread-switch. Our predictor is accurate and imposes no significant overheads. We demonstrate that for the same chip area and memory bandwidth, our architecture achieves four times the throughput of current commercial systems. We argue that our architecture simplifies programmability. Data caches, unlike the mechanisms used today, are transparent to programmers and compilers. Further, our architecture eliminates the need for explicit thread scheduling as threads can be switched on cache misses. Thus, our approach simultaneously achieves both, high throughput and ease-of-programming. In addition, our findings lay the foundation for managing data accesses in the broader class of highthroughput, request-processing systems.Item Automatic validation of secure authentication protocols(2003-08) Kim, Kyoil, 1964-; Abraham, Jacob A.Item Correct implementation of network protocols(2004) McGuire, Tommy Marcus; Gouda, Mohamed G., 1947-A number of issues combine to make network protocol development signif- icantly more difficult than other areas of computer programming: problems with time, concurrency, and failures; interactions between the network proto- col and its environment; and obstacles in developing the protocol over time. In order to address these issues, we introduce the Timed Abstract Pro- tocol notation and the Austin Protocol Compiler. The Timed Abstract Pro- tocol, or TAP, notation is a domain-specific formal language for describing asynchronous message-passing network protocols, with two execution models: an abstract execution model and a concrete execution model. The abstract execution model is suited for protocol design, comprehension, and correctness verification. The concrete execution model is suited for protocol implementa- tion. We show that the two models are equivalent: that a protocol interpreted under the concrete model preserves the intended behavior of the protocol in- terpreted under the abstract model. The Austin Protocol Compiler, or APC, is a system that transforms a protocol given in the Timed Abstract Protocol notation into executable C code and provides a runtime environment for the protocol. In order to demonstrate the effectiveness of the TAP notation and APC, we present implementations of a secure encryption key exchange proto- col, a failure discovery protocol, and a Domain Name System server. While discussing the latter, we examine the performance of the APC implementation and show that it is comparable to two other DNS servers. The combination of the Timed Abstract Protocol notation and the Austin Protocol Compiler addresses the issues of network protocol develop- ment by allowing precise and verifiable descriptions of protocols which can be made executable easily, in order both to gain experimental experience and to provide reference implementations.Item Designing medium access control protocols for multiple-input-multiple-output wireless networks(2005) Park, Minyoung; Nettles, Scott M.CarrierSenseMultipleAccesswithCollisionAvoidance(CSMA/CA)andtherequestto-send(RTS)/clear-to-send(CTS)controlpacketexchangemechanismbasedmedium access control (MAC) protocols, such as the IEEE 802.11 MAC protocol, are extremely successful in single-hop environments. Unfortunately, in multi-hop environments, they suffer from unfair access to the channel due to a side effect of carrier sense and do not perfectly address the hidden node problem and thus degrade network performance. Fortunately, Multiple-Input-Multiple-Output (MIMO) technologies, which employ multiple antennas on both the transmitter and the receiver, provide capabilities to mitigate interference from neighboring nodes, to mitigate fading, and to increase the capacity of a link. We claim that designing MAC protocols jointly with flexible MIMO physical layer technologies can address the problems of conventional MACs and higher layer protocols for multi-hop wireless networks. To show this, we first propose a MAC protocol, Mitigating Interference using Multiple Antennas MAC (MIMA-MAC), which mitigates interference from neighboring nodes by using MIMO in its spatial multiplexing mode. We show that the MIMA-MAC can address the problems caused by neighboring interference and can also increase the utilization of network resources. We further enhance the MIMAMAC and propose the Mitigating Interference using Multiple Antennas with Antenna Selection diversity MAC (MIMA/AS-MAC), which fully utilizes multiple antennas by employing antenna selection diversity together with spatial multiplexing to mitigate fading as well as to suppress interference from neighboring nodes. For a multi-hop network, we show that the MIMA-MAC can improve TCP performance by mitigating neighboring interference. We further enhance the MIMA/AS-MAC and propose the TCP enhanced MIMA/AS-MAC, which increases the efficiency of small packet transmission. Finally, we explore ways of designing cross-layer MAC protocols that can address the problems of a system using reactive ad hoc routing protocols by controlling transmission modes based on the type of packets and channel conditions.