Thesis (M.S. in Computer Science)--Naval Postgraduate School, March 2003. / Thesis advisor(s): Geoffrey Xie, John Gibson. Includes bibliographical references (p. 127-128). Also available online.

Thesis (M.S. in Computer Science)--Naval Postgraduate School, March 2003. / Thesis advisor(s): Geoffrey Xie, John Gibson. Includes bibliographical references (p. 89). Also available online.

Thesis (M.S. in Computer Science)--Naval Postgraduate School, March 2003. / Thesis advisor(s): Geoffrey Xie, Bert Lundy. Includes bibliographical references (p. 97-98). Also available online.

Thesis--PlanB (M.S.)--University of Wisconsin--Stout, 2002. / Field problem. Includes bibliographical references.

Thesis (M.S.)--University of Florida, 2002. / Title from title page of source document. Document formatted into pages; contains v, 52 p.; also contains graphics. Includes vita. Includes bibliographical references.

Thesis (M.S. in Computer Science)--Naval Postgraduate School, June 2003. / Thesis advisor(s): Paul C. Clark, Cynthia E. Irvine. Includes bibliographical references (p. 75-76). Also available online.

Interpersonal communication with network infrastructure creates mobile and online social networks, which shorten the distance among people. It naturally leads to an important question asking for a clear and detailed description of information dissemination and diffusion process in social networks. An in-depth understanding of the question may help in various aspects,e.g., designing better communication protocols and predicting the demand of hot contents. In the thesis we focus on two concrete sub-questions. The first one is to describe the performance of mobile social networks under the practical constraint that information is only allowed to be shared among mutual social friends. Existing designs for mobile social networks enable opportunistic message exchange whenever two mobile devices are within the transmission range of each other. However in real life, people may only be willing to interact with their social friends instead of anyone upon contact. Under such a constraint message forwarding may behave differently. We concentrate on modeling the end-end delivery delay in this scenario under two message validity models, unlimited validity and limited validity. In the first case nodes try their best to relay a message to the destination. While in the latter case a relay node will delete its local copy of a message after carrying it for some time T. Mean-field equations for the dynamic of the population of spreader nodes are derived. With solutions of these equations and empirical studies, we get insightful results. First, more skewed distribution of the number of friends leads to larger delay. Second, the unicast delay is almost constant rather than quickly decreasing with the network size. Last, with a moderate choice of T, we can guarantee almost 100% delivery with a delay very close to the case of unlimited validity. It signifies that a good trade-off can be obtained between delivery efficiency and energy/storage overhead. The second sub-question asks for a model of information diffusion in online social networks. Sharing information in OSN platforms like Twitter and Facebook has become an important part of human life. Thus understanding the dynamic is important as it may help, for example, predict the demand of media contents. We make use of the age-dependent branching process framework to describe the diffusion of content with constant popularity. We give explicit expression for the expected diffusion cascade size, analyze its asymptotic behavior and compare it with the prediction of traditional, over-simplified epidemic model. Also we analyze the diffusion of content with time-variant popularity. An integral equation governing the growth of cascade size is given. Some measurement observations are also explained and quantified. Lastly we design a new model incorporating the geographical locality of contents based on the study of multitype age-dependent branching processes, where the expression for expected cascade size is also given, offering a clear picture of the whole process. Extensive simulations verify the analytical expressions and offer straightforward insights into some other properties of the diffusion process which are not captured by the mathematical formulation. / published_or_final_version / Computer Science / Master / Master of Philosophy

High-speed routers and high-performance data centers share a common system-level architecture in which multiple processing nodes are connected by an interconnection network for high-speed communications. Load balancing is an important technique for maximizing throughput and minimizing delay of the interconnection network. In this thesis, efficient load balancing schemes are designed and analyzed for next-generation routers and data centers. In high-speed router design, two preferred switch architectures are input-queued switch and load-balanced switch. In an input-queued switch, time-domain load balancing can be carried out by an iterative algorithm that schedules packets for sending in different time slots. The complexity of an iterative algorithm increases rapidly with the number of scheduling iterations. To address this problem, a single-iteration scheduling algorithm called D-LQF is designed, in which exhaustive service policy is adopted for reusing the matched input-output pairs in the previous time slots to grow the match size. Unlike an input-queued switch, a load-balanced switch consists of two stages of crossbar switch fabrics, where load balancing is carried out in both time and space domains. Among various load-balanced switches, the feedback-based switch gives the best delay-throughput performance. In this thesis, the feedback-based switch is enhanced in three aspects. Firstly, we focus on reducing its switch fabric complexity. Instead of using crossbars, a dual-banyan network is proposed. The complexity of dual-banyan can be further reduced by merging the two banyans to form a Clos network, resulting in a Clos-banyan network. Secondly, we target at improving the delay performance of the feedback-based switch. A Clos-feedback switch architecture is devised where each switch module in the Clos network is a small feedback-based switch. With application-flow based load balancing, packet order is ensured and the average packet delay is reduced from O(N) to O(n), where N and n are the switch and switch module sizes, respectively. Thirdly, we extend the feedback-based switch to support multicast traffic. Based on the notion of pointer-based multicast VOQ, an efficient multicast scheduling algorithm with packet replication at the middle-stage ports only is proposed. In order to provide close-to-100% throughput for any admissible multicast traffic patterns, a three-stage implementation of feedback-based switch is also designed. In designing load balancing schemes for data centers, we focus on the most popular fat-tree based data centers. Notably, packet-based load balancing is widely considered infeasible for data centers. This is because the associated packet out-of-order problem will cause unnecessary TCP fast retransmits, and as a result, severely undermine TCP performance. In this thesis, we show that if packet-based load balancing is performed properly, the packet out-of-order problem can be easily addressed by slightly increasing the number of duplicate ACKs required for triggering fast retransmit. Admittedly, in case of a real packet loss, the loss recovery time will be increased. But our simulation results show that such an increase is far less than the reduction in the network queueing delay (due to a better load-balanced network). As compared to a flow-based load balancing scheme, our packet-based scheme consistently provides significantly higher goodput and noticeably smaller delay. / published_or_final_version / Electrical and Electronic Engineering / Doctoral / Doctor of Philosophy

No description available.

published_or_final_version / Computer Science and Information Systems / Master / Master of Philosophy