The most important part of parallel computation is communication. Except in the most embarassingly parallel examples, processors cannot work cooperatively to solve a problem unless they can communicate. One way to solve the problem of communication is to use an interconnection network. Processors are located at nodes of the network, which are joined by communication channels. Desirable aspects of an interconnection network include low maximum and average routing distances (as measured in the number of communication channels crossed), a large number of processors, and low number of communication channels per processor. A number of published networks are created from the hypercube by rearranging the hypercube's communication links in a systematic way [23] [28] [30] [33] [50]. These networks maintain the same number of processors, communication links, and links per processor as the hypercube, but have dramatically smaller maximum and average routing distances. This thesis derives one formal mathematical description for this family of networks. This formal description is used to derive graph-theoretic properties of existing networks, and to design new networks. The description is also used to design generalized routing and other communications algorithms for these networks, and to show that these networks can embed and simulate other standard networks, for instance, ring and mesh networks. A network simulator is used to model the dynamic behavior of this family of networks under both store-and-forward and wormhole routing strategies for message-passing. The simulation results are used to study and compare the networks' behavior under various message-passing loads, and to determine what properties are desirable in a network that exists in this model. / Graduation date: 1995

published_or_final_version / Mathematics / Master / Master of Philosophy

No description available.

Movable-slot time-division multiplexing (MSTDM) is a medium access control protocol for the integration of voice and data in local area networks. In this thesis, the performance of this protocol is evaluated through mathematical analysis and simulation. Its application in metropolitan area networks is also studied. For the performance evaluation, a non-pre-emptive priority queuing model is first proposed for analysing the mean data delay characteristic of the slotted non-persistent carrier-sense multiple access with collision detection (CSMA/CD) protocol. Then this analytical approach is extended to the slotted MSTDM protocol with non-persistent data packet transmission, and its mean data delay performance is obtained. Numerical results from the analysis are shown and discussed. Moreover, simulation study of the MSTDM protocol is performed. Through the simulation results, the effects of this protocol on the general delay performances of voice and data are discussed. It is found that if first voice packets, which are generated at the beginning of talkspurts, are given a shorter retransmission delay than data packets, the channel-acquisition delay for voice sources can be reduced without sacrificing the data delay performance significantly. The simulation results are also used to verify the analytical results. As the comparisons show, the accuracy of the analysis is high although it is based on a simple approximate model. For the application of MSTDM in metropolitan area networks, a scheme which alleviates the distance and transmission rate constraints associated with this protocol is described. The approach is to divide the stations in a large area into regional groups, each operating in a different frequency band. Each group forms a sub-network which is part of the metropolitan area network. An access protocol is proposed for interconnecting these sub-networks. Also an analysis which finds the optimum number of sub-networks for interconnection is presented. The criterion is to minimize the mean data delay for communications in a sub-network. / Applied Science, Faculty of / Electrical and Computer Engineering, Department of / Graduate

Call number: LD2668 .T4 1984 T56 / Master of Science

在通信網絡中，當我們要傳輸私密信息時，可能有一些非法用戶希望能獲取這些私密信息。在這裡，我們分別稱這個網絡模型模型和非法用戶為竊聽網絡和竊聽者。在本文中，我們希望在某些限制條件下，設計一種編碼來抵抗竊聽者。 / 為了保護私密信息，我們不會在網絡中直接傳遞它，而是傳遞一些加密過的信息，即密文。現在通行的一個方法是:用一些隨機生成的密碼給這些私密信息加密。即使竊聽者能獲取我傳遞的密文，也無法知道確切的私密信息。在本中文，我們考慮了兩種安全級別:完美安全和非完美安全。在完美安全中，密文和私密信息從統計上講是完全獨立的，也就是說竊聽者得到的是一些安全隨機的信息。在非完美安全中，竊聽者被允許獲得一部私密信息。這部分私密信息，是由竊聽者的信息模糊度來衡量的。如果信息模糊度的大小等於私密信息，那麼非完美安全等價於完美安全。 / 本文的重點在於如何以最小的代價保護私密的信息。我們用Ç =(V ， Σ) 來表示通信網絡。其中， ν是所有節點的集合，Σ 是所有信道的集合。一個竊聽者能夠監聽某些信道上的信息。在我們的模型中，每個竊聽者竊聽的信道的集合是固定的。所有這些被竊聽的信道構成了一個竊聽集。我們把所有竊聽集的集合記作A 。 / 在竊聽網絡中，如果考慮完美安全，現有的工作表明，當A是由所有大小為r 的 Σ的子集構成的時候，存在一個線性網絡編碼，在下面兩個標準下是最優的: / 1)私 密信息的長度最大化; / 2) 隨即密鑰的長度最小化。但是，當A 由任意的5 的子集構成的時候，關於性能界的結果很少。 / 在本文的第一部分中，我們著手研究這個方面的問題並得到了以下結論: / 1) 對於私密信息的長度，我們獲得了一個上界並提供了一個多項式算法去計算它。 / 2)對於隨機密鑰的長度，我們從分教覆蓋和分數包裝的為度進行分析，分別獲得了兩個下界。這兩個下界， 我們證明了他們之間存在一個對偶性。接下來，我們討論暸如何去計算這個下界，我們設計了一個暴力算法和一個關於 / 接下來，我們更關注於點對點系統中的非完美安全問題。我們推廣了一個經典的安全模型: II型竊聽信道。在經典的II型竊聽信道模型中，私密信息是通過若干端到端的信道發送的。在這個模型中，假設每個竊聽者只能竊聽A 中的一個竊聽集，其中A是由所有大小為r的信道集構成。在這裡，保護私密信息的策略也和竊聽網絡中一樣。更確切的，我們可以找到一個關於隨機密碼長度的下界，而且這個下界可以通過一個群編碼獲得。我們在推廣中假設A的構成是任意的，每個竊聽者被允許獲得一定的私密信息。在這個模型下，我們定義了關於私密信息，隨機密碼，每個竊聽者的信息模糊度的一個元組。關於這個元組，我們獲得了一個緊的區域。這個區域可以看成是竊聽網絡上關於割集的一個界。 / In a communication network on which a secure message is transmitted, there may exist illegal users who want to obtain information about the message. Here we refer to the network and those illegal users as the wiretap network and wiretappers, respectively. In secure network coding, we aim to find a network code which can protect the message against the wiretappers under certain constraints. / To protect the message we transmit a ciphertext which is a mixture of the message and a private random key, through the channels in the network. In this work, we consider two kinds of security levels: perfect security and imperfect security. In perfect security, the cipher-text is statistically independent of the message, i.e., the wiretapper can obtain only some randomly generated messages. While in imperfect security, the wiretapper can obtain partial information about the message which is measured by the wiretapper's equivocation. If the wiretapper's equivocation is equal to the message size, then the imperfect security reduces to perfect security. / The focus of our work is to protect the message at the minimum cost, which is measured by the size the key and the bandwidth of the network. Here we denote the network by Ç = (V; Σ), where V is the set of nodes and Σ is the set of point-to-point channels in the network. A wiretapper may access the information transmitted on a certain subset of Σ. In our model, it is assumed that the wiretapper can access any one but not more than one set of channels, called a wiretap set, out of a collection A of all possible wiretap sets. / In a wiretap network, if perfect security is required, existing works show that when A consists of all the r -subsets of Σ (i.e. subsets of size r), there exists a linear network code, which is optimal according to the following two criteria: / i) the size of the message is maximum; / ii) the size of random key is minimum. / But when A consists of arbitrary subsets of Σ, very little is known about the fundamental performance limit. / In the first part of our work, we investigate this problem and obtain some results on the above fundamental performance limits. In this work, we adopt the convention that the size of a random variable X is measured by its entropy H(X). / 1) For the size of the message, we derive an upper bound on H(M) and provide a polynomial algorithm to compute it. / 2) For the size of the key, we analyze it from the aspects of fractional covering and fractional packing, respectively, by which we obtain two bounds on H(K) and we prove the duality between them. n520 Then we discuss the algorithms to compute the lower bound, in- cluding a brute force algorithm and a polynomial algorithm in terms of / In the remaining part, we are largely concerned with imperfect security in a point-to-point communication system, where a classical security model referred to as the wire-tap channel II is generalized by introducing imperfect security. In wire-tap channel II, information is sent to the receiver through a set of point-to-point channels. It is assumed that the wiretapper can access any one but not more than one set in A which consists of all the subsets of the channel set with size r. The strategy to protect the private message is the same as that in the wiretap network. Specifically, a lower bound on the size of the key which can be attained by a group code was proved. In our extension, A is arbitrary and from each wiretap set in A, the wiretapper can obtain some partial information about the message. Under these settings, we define an achievable rate tuple in terms of the message, the key and the wiretapper's equivocation, and prove a tight rate region of the rate tuples. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Cheng, Fan. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2012. / Includes bibliographical references (leaves 103-108). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract also in Chinese. / Abstract --- p.ii / Acknowledgement --- p.ix / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Network Coding --- p.2 / Chapter 1.2 --- Secure Network Coding --- p.3 / Chapter 1.2.1 --- Perfect Secrecy System --- p.3 / Chapter 1.2.2 --- Imperfect Secrecy System --- p.8 / Chapter 1.3 --- Thesis Organization --- p.10 / Chapter 2 --- Basic Concepts and Tools --- p.13 / Chapter 2.1 --- Basic Concepts in Information Theory --- p.14 / Chapter 2.1.1 --- A Universal Approach for Bounds --- p.17 / Chapter 2.2 --- Information Inequalities for Joint Entropy --- p.18 / Chapter 2.2.1 --- Han's Inequalities --- p.18 / Chapter 2.2.2 --- Madiman-Tetali's Inequalities --- p.19 / Chapter 3 --- Performance Bounds on a Wiretap Network --- p.23 / Chapter 3.1 --- Problem Formulation --- p.24 / Chapter 3.1.1 --- Admissible Code --- p.25 / Chapter 3.1.2 --- Performance Measures of an Admissible Code . --- p.27 / Chapter 3.2 --- Related Works and Our Contribution --- p.27 / Chapter 3.3 --- Blocking Sets and Wiretap Sets --- p.29 / Chapter 3.4 --- An Upper Bound on the Message Size --- p.32 / Chapter 3.5 --- The Fractional Packing Bound --- p.34 / Chapter 3.6 --- An Alternative Bound --- p.37 / Chapter 3.7 --- A Duality Result --- p.38 / Chapter 3.8 --- Some Properties about the Lower Bound --- p.42 / Chapter 3.9 --- Algorithms for Computing the Lower Bound --- p.44 / Chapter 3.9.1 --- A Brute Force Algorithm --- p.44 / Chapter 3.9.2 --- A Polynomial Algorithm --- p.45 / Chapter 3.10 --- Tightness of the Lower Bound --- p.50 / Chapter 3.10.1 --- When the Best Lower bound is Zero --- p.52 / Chapter 3.10.2 --- Point-to-Point Communication System --- p.52 / Chapter 4 --- Imperfect Secrecy in Wire-tap Channel II --- p.63 / Chapter 4.1 --- Problem Formulation and Related Result --- p.64 / Chapter 4.1.1 --- Problem Formulation --- p.64 / Chapter 4.1.2 --- Related Result --- p.67 / Chapter 4.2 --- Rate Region of the Rate Tuple --- p.70 / Chapter 4.3 --- A Subregion of the Rate Region --- p.71 / Chapter 4.3.1 --- Converse --- p.72 / Chapter 4.3.2 --- Achievability --- p.76 / Chapter 4.4 --- General Rate Region --- p.85 / Chapter 4.4.1 --- Converse --- p.86 / Chapter 4.4.2 --- Achievability --- p.88 / Chapter 5 --- Conclusion --- p.91 / Chapter A --- Some Related Results --- p.97 / Chapter A.1 --- Definitions and Theorems in Linear Programming --- p.98 / Chapter A.2 --- An Equivalent Lower Bound --- p.101 / Bibliography --- p.103

Leung, Kai Man. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2011. / Includes bibliographical references (leaves 63-68). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Background --- p.5 / Chapter 2.1 --- Graph Connectivity --- p.5 / Chapter 2.1.1 --- Preliminaries --- p.5 / Chapter 2.1.2 --- Edge Connectivity --- p.7 / Chapter 2.1.3 --- Vertex Connectivity --- p.7 / Chapter 2.1.4 --- Algorithms for Graph Connectivities --- p.9 / Chapter 2.1.5 --- All Pairs Edge Connectivities --- p.10 / Chapter 2.1.6 --- Edge Splitting-off --- p.11 / Chapter 2.1.7 --- Graph Separator --- p.13 / Chapter 2.1.8 --- Expander Graphs --- p.15 / Chapter 2.1.9 --- Superconcentrator --- p.17 / Chapter 2.2 --- Network Coding --- p.19 / Chapter 2.2.1 --- Concept --- p.19 / Chapter 2.2.2 --- Linear Network Coding --- p.21 / Chapter 2.2.3 --- Random Linear Network Coding --- p.25 / Chapter 2.3 --- Algebraic Tools --- p.26 / Chapter 2.3.1 --- Linear Algebraic Algorithms --- p.26 / Chapter 2.3.2 --- Nested Dissection --- p.28 / Chapter 3 --- Algorithms for Graph Connectivities --- p.35 / Chapter 3.1 --- Introduction --- p.35 / Chapter 3.1.1 --- Our Results --- p.36 / Chapter 3.1.2 --- Related Work --- p.39 / Chapter 3.1.3 --- Techniques --- p.40 / Chapter 3.1.4 --- Organization --- p.41 / Chapter 3.2 --- New Algebraic Characterization --- p.41 / Chapter 3.3 --- Connectivities in Acyclic Graph --- p.46 / Chapter 3.3.1 --- Faster Encoding Algorithms --- p.47 / Chapter 3.4 --- Directed Planar Graphs --- p.49 / Chapter 3.5 --- All Pairs Edge Connectivities --- p.53 / Chapter 3.5.1 --- Connections with Previous Work --- p.55 / Chapter 3.6 --- Edge Splitting-off --- p.56 / Chapter 3.6.1 --- Edge Splitting-off in Directed Graphs --- p.57 / Chapter 3.6.2 --- Edge Splitting-off in Undirected Graphs --- p.58 / Concluding Remarks --- p.61 / Bibliography --- p.62

Sun, Qifu. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2009. / Includes bibliographical references (leaves 95-99). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract also in Chinese.

Network coding is a novel technique to improve the throughput of networks to transfer messages from sources to sinks. Before the birth of network coding, intermediate nodes can only forward the received messages. In a network coding scheme, the intermediate nodes are allowed to mix the received messages from different incoming links. Network coding has found a wide range of applications, such as peer-to-peer networks, distributed storage and content distribution. The theory of network encoding complexity aims to deal with the question what the minimum number of encoding nodes needed in networks is. In order to tackle this question, we convert it into a combinatorial optimization problem. For directed networks, I examine the number of “mergings”, a special type of graph structure. Consider an acyclic directed network G with l source-sink pairs. Let ci denote the minimum size of edge-cut between i-th source-sink pair for 1 ≤ i ≤ l. Then, by Menger’s theorem, there exists a group of ci edge-disjoint paths (Menger’s paths) between i-th source-sink pair. Although within the same group these paths are edge-disjoint, the paths from different groups may have to merge with each other. It is known that by choosing Menger’s paths appropriately, the number of mergings among different groups of Menger’s paths is always bounded by a constant, which is independent of the size of G. The tightest such constant for the all the above-mentioned networks is denoted byM(c1, c2, . . . , cl) when all sources are distinct, and by M∗(c1, c2, . . . , cl) when all sources are identical. It turns out that M and M∗ are closely related to the network encoding complexity for a variety of networks, such as multicast networks, two-way networks and networks with multiple sessions of unicast. Computation of these two important functions, however, appears to be rather difficult; so far there are no explicit formulas for M and M∗ for a generic parameter c1, c2, . . . , cl. In this thesis, I derive exact values of and tighter bounds on M and M∗ for some parameters, and establish the inequality relationships between M and M∗. For undirected networks, I examine the number of “hubs”, the vertices of degree at least three. Compared to directed networks, study on network en-coding complexity in undirected networks has seen little progress. Consider an undirected network G with l source-sink pairs. For i = 1, 2, . . . , l, let ci de-note the minimum size of vertex-cut between i-th source-sink pair. I study H (c1, c2, . . . , cl), the minimum number of hubs needed in an undirected network with min-cut constraints. The function H is closely related to network en-coding complexity for undirected networks. I prove that under some constraints, regardless of the size of the undirected networks, such minimum number is always bounded above and I derive tight upper bounds for some special parameters. In particular, for two pairs of sources and sinks, I present a novel path-searching algorithm, the analysis of which is instrumental for the derivations of the tight upper bounds. / published_or_final_version / Mathematics / Doctoral / Doctor of Philosophy

Not available / text