Embedded devices such as routers, switches, and firewalls commonly have sensitive information stored on them such as passwords, cryptographic keys, and information about the network around them and services that these device(s) provide. When disposing of or reselling this equipment in the secondary market it is crucial to erase this sensitive information. However, there is an important question that must be asked: Do the erase commands and routines offered by the device manufacturers actually erase the sensitive data? This thesis investigates methods and tools to determine the completeness of this erasure in some common network devices. These methods are used on a sample of networking equipment found to still contain sensitive information after being erased according to vendor recommendations. A computer program was developed to show how this information can be removed. The information in this document is useful for equipment owners, brokers and others looking to remarket their current equipment; all of whom want to minimize the risk of leaking sensitive data to other parties. / Nätverksutrustning såsom routrar, switchar och brandväggar har ofta känslig information lagrad internt, som lösenord, kryptografiska nycklar, information om nätverket runt dem samt tjänster de tillhandahåller. Om denna utrustning ska säljas på andrahandsmarkanden eller på annat sätt byta ägare är det viktigt att all känslig information raderas.  Men kan man lita på att raderings rutiner och metoder som tillhandahålls av tillverkaren verkligen raderar känslig data? Denna avhandling undersöker lämpliga verktyg och metoder för att granska vilken information som minnen i inbyggda system innehåller. Dessa metoder testas praktiskt på några system som visar sig ha kvar känslig information efter att de raderats enligt tillverkarens rekommendationer. Ett datorprogram som demonstrerar hur denna information kan undersökas och raderas finns med som en del av avhandlingen. Informationen i detta dokument är användbar för ägare av datakomutrustning, mäklare av sådana samt andra som vill minimera risken för att läcka känslig information vid återförsäljning av sin begagnade utrustning.

Nous étudions dans cette thèse le problème de l’exploration parallèle d’un graphe à l’aide des multiples, synchronisés et mobiles agents. Chaque agent est une entité individuelle qui peut, indépendamment des autres agents, visiter les sommets du graphe ou parcourir ses arêtes. Le but de ensemble des agents est de visiter tous les sommets de graphe.Nous étudions d’abord l’exploration du graphe dans un modèle où chaque agent est équipé de mémoire interne, mais les noeuds n’ont pas de mémoire. Dans ce modèle les agents sont autorisés à communiquer entre eux en échangeant des messages. Nous présentons des algorithmes qui s’exécutent dans un minimum de temps possible pour polynomiale nombre d’agents (polynomiale en nombre de sommets du graphe). Nous étudions aussi quelle est l’impact de différentes méthodes des communications. Nous étudions des algorithmes où les agents peuvent se communiquer à distance arbitraire,mais aussi où communication est possible seulement entre les agents situés dans le même sommet. Dans les deux cas nous présentons des algorithmes efficaces. Nous avons aussi obtenu des limites inférieures qui correspondent bien à la performance des algorithmes.Nous considérons également l’exploration de graphe en supposant que les mouvements des agents sont déterminés par le soi-disant rotor-router mécanisme. Du point de vue d’un sommet fixé, le rotor- router envoie des agents qui visitent les sommet voisins dans un mode round-robin. Nous étudions l’accélération défini comme la proportion entre le pire des cas de l’exploration d’un agent unique et des plusieurs agents. Pour générales graphes, nous montrerons que le gain de vitesse en cas de multi-agent rotor-router est toujours entre fonction logarithmique et linéaire du nombre d’agents. Nous présentons également des résultats optimaux sur l’accélération de multi-agent rotor-router pour cycles, expanseurs, graphes aléatoires, cliques, tores de dimension fixé et une analyse presque optimale pour hypercubes.Finalement nous considérons l’exploration sans collision, où chaque agent doit explorer le graphe de manière indépendante avec la contrainte supplémentaire que deux agents ne peuvent pas occuper le même sommet. Dans le cas où les agents sont donnés le plan de graphe, on présente un algorithme optimal pour les arbres et un algorithme asymptotiquement optimal pour générales graphes. Nous présentons aussi des algorithmes dans le cas de l’exploration sans collision des arbres et des générales graphes dans la situation où les agents ne connaissent pas le graphe. Nous fermons la thèse par des observations finales et une discussion de problèmes ouverts liés dans le domaine de l’exploration des graphes. / In this thesis we study the problem of parallel graph exploration using multiple synchronized mobile agents. Each mobile agent is an entity that can, independently of other agents, visit vertices of the graph and traverse its edges. The goal of the agents is to visit all vertices of the graph. We first study graph exploration in the model where agents are equipped with internal memory but no memory is available at the nodes. Agents in this model are also allowed to communicate between each other by exchanging messages. We present algorithms working in a minimal possible time for a team of polynomial size (in the number of vertices of the graph). We also study the impact of the available range of communication by analysing algorithms for agents which can communicate at arbitrary distance, or only with other agents located at the same node. We present efficient algorithms and lower bounds that almost match our positive results in both communication models. We also consider graph exploration when movements of agents are determined according to the so-called rotor-router mechanism. From the perspective of a fixed node, the rotor-router sends out agents which visit the node along its outgoing edges, ina round-robin fashion. We study the speedup which is the ratio between the worst-case exploration of a single agent and of multiple agents. We first show that the speed up for general graphs for the multi-agent rotor-router is always between logarithmic and linear in the number of agents. We also present a tight analysis of the speedup for the multi-agent rotor-router for cycles, expanders, random graphs, cliques, constant dimensional tori and an almost-tight analysis for hypercubes. Finally we consider collision-free exploration, where each agent has to explore the graph independently with the additional constraint that no two agents can occupy the same node at the same time. In the case when agents are given the map of the graph, we show an optimal algorithm for trees and an asymptotically optimal algorithm for general graphs. We also present algorithms for collision-free exploration of trees and general graphs in the case when agents have no initial knowledge about the graph. We close the thesis with concluding remarks and a discussion of related open problems in the area of graph exploration.

<p>The objective of this thesis is to design and implement a small scaleInternet Service Provider (ISP) for the NetCenter sub department atMälardalen University. The ISP is intended to give NetCenter a networkseparate from the University’s network, providing them with a moreflexible environment for lab purposes. This will give their students anopportunity to experience a larger backbone with Internet accessibility,which has not been previously available. At the same time it will place theteachers in control of the network in the NetCenter lab premises.The network is designed with a layered approach including an Internetaccess layer, a larger core segment and a distribution layer with aseparated lab network. It also incorporates both a public and a privateserver network, housing servers running e.g. Windows Active Directory,external DNS services, monitoring tools and logging applications. TheInternet access is achieved by peering with SUNET providing a full BGPfeed.This thesis report presents methods, implementations and results involvedin successfully creating the NetCenter ISP as both a lab network and anInternet provider with a few inevitable shortcomings; the most prominentbeing an incomplete Windows Domain setup.</p>

Multiprotocol Label Switching (MPLS) fuses the intelligence of routing with the performance of switching and provides significant benefits to networks with a pure IP architecture as well as those with IP and ATM or a mix of ther Layer 2 technologies. MPLS technology is key to scalable virtual private networks (VPNs) and end-to-end quality of service (QoS), enabling efficient utilization of existing networks to meet future growth. The technology also helps to deliver highly scalable, differentiated end-to-end IP services with simpler configuration, management, and provisioning for both Internet providers and end-users. However, MPLS is a connection-oriented architecture. In case of failure MPLS first has to establish a new label switched path (LSP) and then forward the packets to the newly established LSP. For this reason MPLS has a slow restoration response to a link or node failure on the LSP.The thesis provides a description of MPLS-based architecture as a preferred technology for integrating ATM and IP technologies, followed by a discussion of the motivation for the fast and reliable restoration mechanism in an MPLS network. In this thesis first we address the fast rerouting mechanisms for MPLS networks and then we focus on the problem of packet loss, packet reordering and packet delay for protected LSP in MPLS-based network for a single node/link failure. In order to deliver true service assurance for guaranteed traffic on a protected LSP we use the fast rerouting mechanism with a preplanned alternative LSP. We propose enhancements to current proposals described in extant literature. Our fast rerouting mechanism avoids packet disorder and significantly reduces packet delay during the restoration period.An extension of the Fast Rerouting proposal, called Reliable and Fast Rerouting (RFR), provides some preventive actions for the protected LSP against packet loss during a failure. RFR maintains the same advantages of Fast Rerouting while eliminating packet losses, including those packet losses due to link or node failure (circulating on the failed links), which were considered to be "inevitable" up to now.For the purpose of validating and evaluating the behavior of these proposals a simulation tool was developed. It is based on the NS, a well-known network simulator that is being used extensively in research work. An extension featuring the basic functionality of MPLS (MNS) is also available for the NS, and this is the basis of the developed simulation tool.Simulation results allow the comparison of Fast Rerouting and RFR with previous rerouting proposals.In addition to this we propose a mechanism for multiple failure recovery in an LSP. This proposal combines the path protection, segment protection and local repair methods. In addition to the multiple link/node failure protection, the multiple fault tolerance proposal provides a significant reduction of delay that the rerouted traffic can experience after a link failure, because the repair action is taken close to the point of failure.Then we proceed to address an inherent problem of the preplanned alternative LSP. As alternative LSPs are established together with the protected LSP it may happen that the alternative is not the optimal LSP at the time the failure occurs. To overcome this undesired behavior, we propose the Optimal and Guaranteed Alternative Path (OGAP). The proposal uses a hybrid of fast-rerouting and a dynamic approach to establish the optimal alternative LSP while rerouting the affected traffic using the preplanned alternative LSP. This hybrid approach provides the best of the fast rerouting and the dynamic approaches.At the same time we observed that the protection path becomes in fact unprotected from additional failures after the traffic is rerouted onto it.To address this we propose a guarantee mechanism for protection of the new protected LSP carrying the affected traffic, by establishing an alternative LSP for the rerouted traffic after a failure, avoiding the vulnerability problem for the protected traffic.Finally, we present a further optimization mechanism, adaptive LSP, to enhance the existing traffic engineering for Quality of Services (QoS)provision and improve network resource utilization. The adaptive LSP proposal allows more flexibility in network resource allocation and utilization by adapting the LSP to variations in all network loads,resulting in an enhancement of existing MPLS traffic engineering.

The Transmission Control Protocol (TCP) is the dominant transport protocol in today?s Internet. The original design of TCP left congestion control open to future designers. Short of implementing changes to the TCP stack on the end-nodes themselves, Internet Service Providers have employed several techniques to be able to operate their network equipment efficiently. These techniques amount to shaping traffic to reduce cost and improve overall customer satisfaction. <br /><br /> The method that gives maximum control when performing traffic shaping is using an inline traffic shaper. An inline traffic shaper sits in the middle of any flow, allowing packets to pass through it and, with policy-limited freedom, inspects and modifies all packets as it pleases. However, a number of practical issues such as hardware reliability or ISP policy, may prevent such a solution from being employed. For example, an ISP that does not fully trust the quality of the traffic shaper would not want such a product to be placed in-line with its equipment, as it places a significant threat to its business. What is required in such cases is third-party rate control. <br /><br /> Formally defined, a third-party rate controller is one that can see all traffic and inject new traffic into the network, but cannot remove or modify existing network packets. Given these restrictions, we present and study a technique to control TCP flows, namely triple-ACK duplication. The triple-ACK algorithm allows significant capabilities to a third-party traffic shaper. We provide an analytical justification for why this technique works under ideal conditions and demonstrate via simulation the bandwidth reduction achieved. When judiciously applied, the triple-ACK duplication technique produces minimal badput, while producing significant reductions in bandwidth consumption under ideal conditions. Based on a brief study, we show that our algorithm is able to selectively throttle one flow while allowing another to gain in bandwidth.

The Transmission Control Protocol (TCP) is the dominant transport protocol in today?s Internet. The original design of TCP left congestion control open to future designers. Short of implementing changes to the TCP stack on the end-nodes themselves, Internet Service Providers have employed several techniques to be able to operate their network equipment efficiently. These techniques amount to shaping traffic to reduce cost and improve overall customer satisfaction. <br /><br /> The method that gives maximum control when performing traffic shaping is using an inline traffic shaper. An inline traffic shaper sits in the middle of any flow, allowing packets to pass through it and, with policy-limited freedom, inspects and modifies all packets as it pleases. However, a number of practical issues such as hardware reliability or ISP policy, may prevent such a solution from being employed. For example, an ISP that does not fully trust the quality of the traffic shaper would not want such a product to be placed in-line with its equipment, as it places a significant threat to its business. What is required in such cases is third-party rate control. <br /><br /> Formally defined, a third-party rate controller is one that can see all traffic and inject new traffic into the network, but cannot remove or modify existing network packets. Given these restrictions, we present and study a technique to control TCP flows, namely triple-ACK duplication. The triple-ACK algorithm allows significant capabilities to a third-party traffic shaper. We provide an analytical justification for why this technique works under ideal conditions and demonstrate via simulation the bandwidth reduction achieved. When judiciously applied, the triple-ACK duplication technique produces minimal badput, while producing significant reductions in bandwidth consumption under ideal conditions. Based on a brief study, we show that our algorithm is able to selectively throttle one flow while allowing another to gain in bandwidth.

Nous étudions dans cette thèse le problème de l'exploration parallèle d'un graphe à l'aide des multiples, synchronisés et mobiles agents. Chaque agent est une entité individuelle qui peut, indépendamment des autres agents, visitez les sommets du graphe ou parcourir ses arêtes. Le but de ensemble des agents est de visiter tous les sommets de graphe. Nous étudions d'abord l'exploration du graphe dans un modèle où chaque agent est équipé de mémoire interne, mais les nœuds n'ont pas de mémoire. Dans ce modèle les agents sont autorisés à communiquer entre eux en échangeant des messages. Nous présentons des algorithmes qui s'exécutent dans un minimum de temps possible pour polynomiale nombre d'agents (polynomiale en nombre de sommets du graphe). Nous étudions aussi quelle est l'impacte de différent méthodes des communications. Nous étudions des algorithmes où les agents peuvent se communiquer à distance arbitraire, mais aussi où communication est possible seulement entre les agents situés dans le même sommet. Dans les deux cas nous présentons des algorithmes efficaces. Nous avons aussi obtenu des limites inférieures qui correspondent bien à la performance des algorithmes. Nous considérons également l'exploration de graphe en supposant que les mouvements des agents sont déterminés par le soi-disant rotor-router mécanisme. Du point de vue d'un sommet fixé, le rotor- router envoie des agents qui visitent les sommet voisins dans un mode round-robin. Nous étudions l'accélération défini comme la proportion entre le pire des cas de l'exploration d'un agent unique et des plusieurs agents. Pour générales graphes, nous montrerons que le gain de vitesse en cas de multi-agent rotor-router est toujours entre fonction logarithmique et linéaire du nombre d'agents. Nous présentons également des résultats optimaux sur l'accélération de multi-agent rotor-router pour cycles, expanseurs, graphes aléatoires, cliques, tores de dimension fixé et une analyse presque optimale pour hypercubes. Finalement nous considérons l'exploration sans collision, où chaque agent doit explorer le graphe de manière indépendante avec la contrainte supplémentaire que deux agents ne peuvent pas occuper le même sommet. Dans le cas où les agents sont donnés le plan de graphe, on présente un algorithme optimal pour les arbres et un algorithme asymptotiquement optimal pour générales graphes. Nous présentons aussi des algorithmes dans le cas de l'exploration sans collision des arbres et des générales graphes dans la situation où les agents ne connaissent pas le graphe. Nous fermons la thèse par des observations finales et une discussion de problèmes ouverts liés dans le domaine de l'exploration des graphes.

This thesis concerns measuring, understanding and modelling Internet traffic. We first study the origins of the statistical properties of Internet traffic, in particular its scaling behaviour, and propose a constructive model of packet traffic with physically motivated parameters. We base our analysis on a large amount of empirical data measured on different networks, and use a so called semi-experimental approach to isolate certain features of traffic we seek to model. These results lead to the choice of a particular Poisson cluster process, known as Bartlett-Lewis point process, for a new packet traffic model. This model has a small number of parameters with simple networking meaning, and is mathematically tractable. It allows us to gain valuable insight on the underlying mechanisms creating the observed statistics. / In practice, Internet traffic measurements are limited by the very large amount of data generated by high bandwidth links. This leads us to also investigate traffic sampling strategies and their respective inversion methods. We argue that the packet sampling mechanism currently implemented in Internet routers is not practical when one wants to infer the statistics of the full traffic from partial measurements. We advocate the use of flow sampling for many purposes. We show that such sampling strategy is much easier to invert and can give reasonable estimates of higher order traffic statistics such as distribution of number of packets per flow and spectral density of the packet arrival process. This inversion technique can also be used to fit the Bartlett-Lewis point process model from sampled traffic. / We complete our understanding of Internet traffic by focusing on the small scale behaviour of packet traffic. To do so, we use data from a fully instrumented Tier-1 router and measure the delays experienced by all the packets crossing it. We present a simple router model capable of simply reproducing the measured packet delays, and propose a scheme to export router performance information based on busy periods statistics. We conclude this thesis by showing how the Bartlett-Lewis point process can model the splitting and merging of packet streams in a router.

The objective of this thesis is to design and implement a small scaleInternet Service Provider (ISP) for the NetCenter sub department atMälardalen University. The ISP is intended to give NetCenter a networkseparate from the University’s network, providing them with a moreflexible environment for lab purposes. This will give their students anopportunity to experience a larger backbone with Internet accessibility,which has not been previously available. At the same time it will place theteachers in control of the network in the NetCenter lab premises.The network is designed with a layered approach including an Internetaccess layer, a larger core segment and a distribution layer with aseparated lab network. It also incorporates both a public and a privateserver network, housing servers running e.g. Windows Active Directory,external DNS services, monitoring tools and logging applications. TheInternet access is achieved by peering with SUNET providing a full BGPfeed.This thesis report presents methods, implementations and results involvedin successfully creating the NetCenter ISP as both a lab network and anInternet provider with a few inevitable shortcomings; the most prominentbeing an incomplete Windows Domain setup.

The multi-net Global Routing Problem (GRP) in VLSI physical design is a problem of routing a set of nets subject to limited resources and delay constraints. Various state-of-the-art routers are available but their main focus is to optimize the wire length and minimize the over ow. However optimizing wire length do not necessarily meet timing constraints at the sink nodes. Also, in modern nano-meter scale VLSI process the consideration of process variations is a necessity for ensuring reasonable yield at the fab. In this work, we try to nd a fundamental strategy to address the timing-driven Steiner tree construction (i.e., the routing) problem subject to congestion constraints and process variation. For congestion mitigation, a gradient based concurrent approach (over all nets) of Erzin et. al., rather than the traditional (sequential) rip-and-reroute is adopted in or- der to propagate the timing/delay-driven property of the Steiner tree candidates. The existing sequential rip-up and reroute methods meet the over ow constraint locally but cannot propagate the timing constraint which is non-local in nature. We build on this approach to accommodate the variation-aware statistical delay/timing requirements. To further reduce the congestion, the cost function of the tree generation method is updated by adding history based congestion penalty to the base cost (delay). Iterative use of the timing-driven Steiner tree construction method and history based tree construction procedure generate a diverse pool of candidate Steiner trees for each net. The gradient algorithm picks one tree for each net from the pool of trees such that congestion is e ciently controlled. As the technology scales down, process variation makes process dependent param- eters like resistance, capacitance etc non-deterministic. As a result, Statistical Static Timing Analysis or SSTA has replaced the traditional static timing in nano-meter scale VLSI processes. However, this poses a challenge regarding the max/min-plus algebra of Dijkstra like approximation algorithm that builds the Steiner trees. A new approach based on distance between distributions for nding maximum/minimum at the nodes is presented in this thesis. Under this metric, the approximation algorithm for variation aware timing driven congestion constrained routing is shown to be provably tight and one order of magnitude faster than existing approaches (which are not tight) such as the MVERT. The results (mean value) of our variation aware router are quite close to the mean of the several thousand Monte Carlo simulations of the deterministic router, i.e the results converge in mean. Therefore, instead of running so many deterministic Monte Carlo simulations, we can generate an average design with a probability distribution reasonably close to that of the actual behaviour of the design by running the proposed statistical router only once and at a small fraction of the computational e ort involved in physical design in the nano regime VLSI. The above approximation algorithm is extended to local routing, especially non- Manhattan lambda routing which is increasingly being allowed by the recent VLSI tech- nology nodes. Here also, we can meet delay driven constraints better and keep related wire lengths reasonable.