1,720,989 research outputs found
The world according to MARP
No full textIn multi-agent route planning (MARP), there is a set of agents each with a start location and a destination location on a shared infrastructure, and the goal of each agent is to reach its destination in the shortest possible time, without coming into conflict (e.g. because of a collision) with any of the other agents. The MARP problem is relevant in automated guided vehicle systems, with application domains in flexible manufacturing systems or at container terminals like Rotterdam or Singapore. Another application domain for MARP is airport taxi routing, where aircraft must taxi between runway and gate, while avoiding close proximity with other aircraft. In the literature, a number of approaches to MARP exist. The first is to have one planner make a plan for all agents. Because of its complete overview, the centralized planner can in principle find an optimal set of agent route plans. Unfortunately, finding an optimal set of plans is intractable (as we show in this thesis), and in practice optimal plans can only be found if there are not more than a handful of agents. A second approach, and the one we take in this thesis, is to let the agents plan one by one, each agent planning around the plans of the previous agents (in the sense that no conflict is introduced with any existing plans). In this prioritized approach (the agents plan in the order of their priority), it is possible to find an individually optimal route plan in reasonable time, although there is no guarantee that the combination of agent plans is also optimal. A third approach to MARP is to do very little planning (for example by choosing a fixed path between start and destination), and instead to check at every next step in the plan-execution phase whether it is safe to move forward, or whether a conflict will ensue. In this approach there are no guarantees for either local or global optimality, but it can be a convenient approach in dynamic environments, where unexpected changes can invalidate carefully crafted plans. If however there are no plans, then nothing can be disrupted, and any situation can be treated the same way. By contrast, the first two (planning) approaches to MARP require additional plan repair techniques to deal with unexpected incidents. We present a model for MARP in which the infrastructure is modeled as a graph of resources (like roads and intersections); each resource has a capacity, which is the maximum number of agents that may occupy the resource at the same time. A route plan is a sequence of resources each with an occupation time interval, and the objective in MARP is to find a set of agent route plans such that the capacities of the resources are never exceeded. In our model, we also identify a number of additional constraints that have to be satisfied depending on the application domain. For example, we formulate constraints to forbid overtaking, constraints that forbid cyclic plans, and constraints that require a minimum separation between agents of at least one empty resource. Even if no additional constraints need to be satisfied, finding an optimal solution to the MARP problem is intractable. Our route planning algorithms make use of free time windows on resources. A free time window is an interval during which an agent can make use of a resource without causing a conflict with any of the existing route plans. We search for a route plan by constructing a graph of the free time windows, and performing an adapted shortest-path search through this graph, which results in an optimal (shortest-time), conflict-free route plan for a single agent. Our contribution lies in the speed of our algorithm, which is much faster than previous optimal single-agent route planning algorithms. In addition, we also present a route planning algorithm that can find a conflict-free route plan along a sequence of locations (rather than from a start location to a single destination location), which is the first algorithm in its kind, as far as we know. Planning approaches to MARP require additional mechanisms to deal with unexpected incidents during plan execution. In this thesis, we consider vehicle incidents that temporarily immobilize an agent (which can be caused by e.g. a human that steps into the path of an agent). If, after the slowdown, all agents including the delayed agent ignore the disruption, then a deadlock situation can arise. In the literature there exists a mechanism that can prevent deadlocks, and thus ensure that each agent can reach its destination safely, albeit with a possible delay. This mechanism is based on the resource priority that agents inherit after the planning process: from the set of agent plans, we can infer the order in which agents visit a resource (and the first agent to visit a resource has the highest resource priority). The deadlock prevention mechanism is simply to respect these resource priorities during plan execution, which means that agents sometimes have to wait for a delayed agent with a higher priority. In some cases, there is no need to wait for a delayed agent, and the resource priority can be changed during plan execution without creating a deadlock situation. In the literature, one such priority-changing algorithm exists, but the conditions under which it allows a priority change are very strict, which limits the applicability of the algorithm. We developed a new priority-changing algorithm that allows changes in more situations, which therefore has the potential to achieve a bigger reduction in agent delay. Our algorithm makes use of a graph structure that can predict exactly which priority changes are safe, and which will lead to a deadlock. In our experiments we evaluated the robustness of agent route plans, i.e., the property of plans to remain efficient, in terms of minimizing delay, even if unexpected incidents necessitate minor plan revisions. Above, we described three schedule repair algorithms: either fully respect the resource priorities during plan execution, or allow some priority changes using the existing priority-changing algorithm, or using our new algorithm. Respecting resource priorities can be seen as a baseline approach to incident handling: if it results in short delays, then no priority changes are necessary; if it would result in long delays, then we can seek to reduce this delay by changing some priorities at run-time. In taxi route planning experiments on a model of Schiphol airport, the baseline method produced satisfactory results: in case there are only a few short incidents, then there is hardly any delay; in case there are many incidents of a long duration, then the average delay was still rarely more than 20% of the length of the agent plans. Experiments on other types of infrastructures (such as grid-like networks and small-world networks) also showed that delay is low for a small number of short incidents, but for a large number of long incidents, delays of around 100% were frequently reached. One reason why the results are so favourable for the airport experiments is that the locations of the start and destination points of the agents were not fully randomized, as aircraft agents travel between runways and gates. Hence, if aircraft agents use the same resource, then they are most likely heading in the same direction. Our experiments suggest that the most delay from incidents arises when agents that have to wait for each other travel in opposite directions. We also managed to reduce delay by changing priorities, and our algorithm, which produces the greatest number of priority changes, also managed the greatest reduction in delay. A different set of experiments evaluated the cost of the multi-agent plan (which can be measured by e.g. recording the finish time of the latest agent) that results from sequential single-agent planning, for arbitrary agent priorities. Under the assumption that the optimal set of agent priorities will result in a close-to-optimal global plan, then measuring the difference between the best and the worst observed set of priorities gives an indication of the worst-case global plan cost that can be obtained using prioritized planning. In our experiments, we tried 100 different sets of agent priorities for a single problem instance, and for each type of infrastructure, we tried numerous instances. The best results were again obtained for the airport infrastructure, and again the locations of the start and destination points seem to be the main reason: because all agents travel in more or less the same direction, they manage to organize themselves into flows, regardless of which agent is allowed to plan first. For other types of infrastructures, it proved to be important to have multiple routes between any two locations. Otherwise, if e.g. one road connects two parts of the infrastructure, then this road can become a bottleneck if agents on either side of the road need to cross; arbitrarily assigned priorities can then lead to a situation where the travel direction of the resource alternates with every other agent, which is much less efficient than many agents using the resource at the same time in the same direction. To conclude, we presented a prioritized approach to the multi-agent route planning problem. MARP has many important application domains like airport taxi routing and route planning for automated guided vehicles, and our new algorithm is fast enough to be applied to problem instances of realistic size. To deal with unexpected incidents, we have focussed on schedule repair methods, but in future work we can investigate how plan repair techniques (i.e., also allowing agents to choose a different route) can further reduce delay. Another direction of future research is how we can reduce the cost of the global plan. Our route planning algorithms are optimal for a single agent, and the combination of individually optimal route plans sometimes leads to high-quality global plans --- for example in the taxi route planning experiments, where the location of the start and destination points of the agents ensured that they travel in the same directions and therefore interfere little with each other. On other infrastructures, an arbitrary priority assignment can sometimes lead to a poor global plan. To improve global plan cost, one possibility is to find a better set of agent priorities. Another option is to investigate whether agents can coordinate before or during planning, such that an agent also takes into account the benefit of other agents during planning.Software TechnologyElectrical Engineering, Mathematics and Computer Scienc
Towards a global implementation of Named Data Networking
No full textThe host-to-host IP model currently supporting the Internet does not suffice in supporting current-day content distribution in the form of content-sharing via peer-to-peer applications, real-time media streaming and social networks. Since the design of IP, the usage of the Internet has changed from a messaging and few-to-few information sharing system to a fewto-many content distribution system where many users request large amounts of overlapping information. Running a content distribution network over a host-to-host network appears to be very inefficient since every piece of content needs to travel the complete distribution-chain from generator to consumer every time it is requested. The result is that identical pieces of information will often redundantly travel the same links and routers. Information Centric Networking tries to solve this problem by proposing route-by-name instead of route-by-address mechanisms. This enables networks to be optimized for contentdistribution instead of connections and allows routers to cache often requested pieces of content in memory. In this thesis we will attempt to solve problems that arise at the introduction of a new globally routeable network, enabling clients and networks to be a full member (both consumer and generator) on a global Information Centric Network. The topics discussed vary from dynamic end-user configuration and generating globally unique names in order to share information on the Information Centric Network, via mapping techniques to decrease routing complexity, to proposing a transition mechanism that dynamically creates IP encapsulating tunnels between disconnected Information Centric Networks. In short, we discuss a multitude of problems which need to be addressed in order to assist the global implementation of an Information Centric Network.Network Architectures and Services (NAS)TelecommunicationsElectrical Engineering, Mathematics and Computer Scienc
Performance Analysis of WebRTC-based Video Conferencing
No full textVideo Conferencing has been rapidly gaining attention and is becoming a more popular way to communicate due to better internet connectivity and increasing computation power. Because of this increase in demand, the dying out of proprietary plugins like Adobe Flash, and the need for easy and accessible video conferencing, a new browser technology emerged: WebRTC. WebRTC allows internet browsers to perform a peer-to-peer video conference without the need to install additional plugins or applications. WebRTC is widely adopted for video conferencing solutions and getting more support across all browsers. WebRTC is easy to use by application developers, but unfortunately does not allow a developer to easily have insight into the video call characteristics made on the platform. This is because the way WebRTC handles network congestion is completely hidden away in the code of the browser. This work describes the media pipeline of WebRTC including all different network protocols used by WebRTC. To have a better understanding of how WebRTC handles network congestion, the Google Congestion Control (GCC) algorithm used by WebRTC is analyzed. Since WebRTC works over UDP which does not support congestion control like e.g. TCP does, a custom made congestion control is used. GCC changes the data rate based on packet loss and latency measured at respectively the sender and the receiver side during a WebRTC video conference. Based on the thorough WebRTC analysis including related work which some of WebRTC’s pitfalls, a test bed is set up to conduct a comprehensive performance analysis of WebRTC using the latest browsers, for different scenarios, while being subject to different network effects. The effects of additional latency, packet loss and limited bandwidth are tested. The effects of cross traffic, multi-party, WebRTC on mobile devices, different browsers and different video codecs are furthermore analyzed. This performance evaluation verifies that results shown in earlier research no longer hold due to the improved GCC algorithm. Results however do show that there is room for improvement since inter-protocol fairness is not ideal and WebRTC streams have a higher priority than competing TCP flows. It also shows the difference in WebRTC’s performance for different internet browsers and mobile devices. Also the newly added support for the video codecs VP9 and H.264 are analyzed which do not perform as expected and need to improve.Electrical Engineering, Mathematics and Computer ScienceNetwork Architectures and Service
Routing in Optical and Stochastic Networks
No full textIn most types of networks (e.g., optical or transportation networks), finding one or more best paths from a source to a destination, is one of the biggest concerns of network users and providers. This process is known as routing. The routing problems differ accordingly depending on different application scenarios with their respective routing goals. For example, in the field of data communication networks, with many communication applications emerging (such as Cloud Computing, Internet Protocol Television (IPTV), Video-On-Demand), finding optimum routing paths has been considered in the bandwidth-limited network or when it is expensive to increase the capacity of the existing hardware. Moreover, for network providers, the Service Level Agreements (SLA) determine the level of service that is promised to the network user. The routing problems should also incorporate these SLAs (e.g., connection availability). The energy consumption of the data communication networks is another example, due to its impact on the environment (e.g., green house effect). Energy-aware routings have been considered as one approach to efficiently deal with this issue. Apart from that, the network itself is likely to behave in a stochastic manner. For instance, especially in large networks, it is difficult to obtain an accurate view on the link characteristics like bandwidth utilization or latency, because their dynamics are usually of the same order as the time it would take to distribute information on the link state throughout the network. The routing problems become more difficult to solve if the network dynamics have to be considered. This thesis deals with routing problems in two kinds of networks, namely, (1) (deterministic) optical networks and (2) stochastic networks. Optical networks have been widely deployed because of their high capacity, low bit rate, etc. Wavelength Division Multiplexing (WDM) technology enabled optical networks divides the capacity of a fiber into several non-overlapping wavelength channels that can transport data independently. These wavelength channels make up lightpaths, which are used to establish optical connections that may span several fiber links. Chapters 2 and 3 study the energyaware path selection problem in IP-over-WDM optical networks and the energy-efficient network design problem, respectively. In Chapter 4, a more flexible optical network enabled by OFDM technology is introduced, which is here called spectrum-sliced elastic optical path (SLICE) network. In this kind of network, the capacity of a fiber link is divided into a fixed number of (overlapping) low data rate transporting units, which are called subcarriers. Subsequently, Chapter 4 studies the routing problem in SLICE networks. Connection availability, which is defined as the probability that the corresponding connection is available, is a key element of many SLAs. Establishing a path over a connection should obey the availability agreements to avoid the loss of revenue. Chapter 5 studies the availability-based path selection problem. The energy-aware path selection problem in Chapter 2 is polynomial-time solvable, but all the other problems in Chapters 3, 4 and 5 are proved NP-hard. To solve them, exact algorithms or efficient heuristics are proposed. In deterministic optical networks, the link weights (e.g., energy) are usually assumed to be known, while in the so-called stochastic networks they are uncertain. Although in some cases optical networks may behave in a stochastic manner, most of the routing problems in deterministic optical networks are already NP-hard as mentioned above, which suggests that similar routing problems in stochastic optical networks are even harder to solve. We therefore consider more general stochastic networks, which are not confined to any specified type of network. Chapter 6 studies the maximum-flow problem without and with a delay constraint under the assumption that the bandwidth and delay follow a general log-concave probability distribution. A convex optimization formulation is proposed to solve the maximum-flow problem in stochastic networks. When a delay constraint is imposed on each path, the problem becomes NP-hard. To solve it, an approximation algorithm and a heuristic are devised. So far, all the studies do not thoroughly account for the correlations between link weights, but the link weights (such as failure probability) are correlated in some real-life networks. For example, in interdependent networks, where for instance the electricity network and Internet network are coupled and inter-connected, and one node or link failure in one network may cause failures of nodes or links in the other network. Chapter 7 addresses the shortest path problem and the min-cut problem (the dual problem of the maximum-flow problem in conventional networks) in more general correlated networks.Correlated network can also be regarded as a special kind of stochastic network, since its link weight is uncertain instead of fixed. Two correlated link weight models are studied, namely (1) deterministic correlated model and (2) (log-concave) stochastic correlated model. These two problems are proved NP-hard under the deterministic correlated model, and cannot be approximated to arbitrary degree, unless P=NP. But they are shown polynomial time solvable under a (constrained) nodal deterministic correlated model. Under the (log-concave) stochastic correlated model, two convex optimization formulations are proposed to solve the shortest path problem and the min-cut problem, respectively. Finally, Chapter 8 concludes with the main findings and contributions of this thesis, and also points out possible future work.Intelligent SystemsElectrical Engineering, Mathematics and Computer Scienc
An Overview of Algorithms for Network Survivability
Full text linkNetwork survivability—the ability to maintain operation when one or a few network components fail—is indispensable for present-day networks. In this paper, we characterize three main components in establishing network survivability for an existing network, namely, (1) determining network connectivity, (2) augmenting the network, and (3) finding disjoint paths.We present a concise overview of network survivability algorithms, where we focus on presenting a few polynomial-time algorithms that could be implemented by practitioners and give references to more involved algorithms.Network Architectures and ServicesElectrical Engineering, Mathematics and Computer Scienc
Quality of Service Routing in the Internet. Theory, Complexity and Algorithms
No full textThe Internet consists of many network elements that direct packets on the correct path leading towards the destination. This process of finding and following a path to the destination is called routing. Routing is not infallible and packets may get lost: the current Internet cannot give any quality guarantees regarding the packets it transports. However, many new multi-media applications (e.g., VoIP) cannot properly operate without such guarantees. Finding paths that can meet such demands is called Quality of Service (QoS) routing. This thesis identifies several algorithmic concepts of QoS routing, which are all incorporated into our exact SAMCRA algorithm. The first large-scale performance evaluation of QoS algorithms indicates that the SAMCRA algorithm performs best. Besides SAMCRA, also algorithms for multicast QoS routing and link-disjoint QoS routing are proposed in this thesis. QoS routing is NP-complete, which means that to find the exact solution, algorithms require, in the worst case, a running time that cannot be bounded by a polynomial function. This thesis also analyzes the complexity of QoS routing and argues that it is feasible in practice. Hence, exact algorithms like SAMCRA should be used instead of heuristics. Finally, the dynamics of QoS routing are discussed and some preliminary work in this area is provided. Here, too, SAMCRA outperformed the other implemented algorithms.Electrical Engineering, Mathematics and Computer Scienc
Robustness Analysis and Capacity Management of the KPN (PS) Mobile Core Network
No full textThis thesis has two main topics. On the one hand it discusses how the robustness of a network can be increased as efficient as possible, where connectivity is treated as a robustness measure. On the other hand It treats capacity management of a network when it is still in its design phase. In particular, it shows how bandwidth management can be done on the network edges, while it also gives an implication to prioritize the vertices based on their relative importance. One of KPN's mobile core networks is treated as a case study.Network Architectures and ServicesTelecommunicationsElectrical Engineering, Mathematics and Computer Scienc
Telecommunication requirements in low-voltage smart grids
No full textThe electricity power system is shifting from a high reliance on centralized large power plants towards a system in which distributed generation units, like solar panels, are penetrating into the lower parts of the power grid. As a result, the consumers are becoming active prosumers who in addition to consuming can also autonomously generate, store, import or export power. Secondly, the introduction of new electronic devices, such as: electrical vehicles and heat pumps resulting in increased energy demand. The capacity of the current energy grid is insufficient to facilitate the future needs. To solve this problem without constructing a complete new power grid the smart grid is devised. A smart grid is able to use the assets of the legacy power grid in a more efficient way; in order to facilitate the future power needs without installing a complete new grid. The “smart” in “smart grid” heavily relies on the use of telecommunication and ICT. A smart energy grid holds the promise of increased reliability, since there is no longer one single point of failure, increased energy sustainability, through the use of different types of environmentally friendly energy sources, and an increased efficiency, due to less loss in transporting energy over large distances. However, the smart grid, with its intermittent distributed energy sources also presents various challenges. Firstly, the traditional grid topology is designed for uni-directional top-down power flow, which might not be able to optimally include local bi-directional power exchange. Specifically, the low-voltage and the medium-voltage network segments, where most of the local power exchanges is going to take place, needs to be updated. Secondly, the intermittent production behaviour of the distributed sources as well as the autonomy of the prosumers to manage their own energy demand likely lead to different (and possibly more volatile) load profiles. Control of the resources in a smart grid is therefore important. To build and control a smart grid, a large network of smart devices must be created, these smart devices must be able to communicate with each other. Since smart grids are not commonly in use, and still much under development, acquiring data on the actual telecommunications requirements is an utopia. Nonetheless, since ICT forms a crucial element of a smart grid, the aim of this research is to estimate which parts of a smart grid would have the biggest telecommunications demands. Subsequently, based on our knowledge of the Dutch energy grid of Alliander and various simulations, we take a cautious step at guestimating the actual telecommunications need in the foreseeable future of the smart grid. We take a bottom-up approach starting at the end nodes in the low-voltage energy grid.Network Architectures and ServicesElectrical Engineering, Mathematics and Computer Scienc
Comparison of optical inter-domain routing protocols in the presence of wavelength converters
No full textThe success of optical technology has introduced a new future for the Internet. With the many advantages of optical technology, multimedia applications which require strict quality of service(QoS) are able to be guaranteed in an optical network. Unfortunately, the optical technology still have some limits in setting up a connection. One of these limits is that a lightpath must use the same wavelength on all the links along its path from source to destination in an optical network without wavelength converters. This limit influents the resource utilization. In an optical network, wavelength converters are used to overcome this limit so they will help to improve the efficiency of the resource utilization. However, because of their expensiveness, a limited number of wavelength converters are usually used at some routers in optical networks. Many researchers have been working on multi-domain routing protocol for optical networks. In this thesis, we will implement and evaluate the performance of three optical inter-domain protocols in an optical network with wavelength converters. In particular three protocols which are discussed in dept are: Optical Border Gateway Protocol (OBGP), Optical Border Gateway Protocol Plus (OBGP+) and IDRA-based Routing Protocol (IDRA protocol). By building the simulations for each protocol in OPNET, we compare the performance of the three protocols based on two metrics: the blocking ratio of inter-domain lightpath requests and the overall number of routing messages to archive this blocking ratio. Moreover, we also evaluate the efficiency of wavelength converters in an optical network.Computer EngineeringElectrical Engineering, Mathematics and Computer Scienc
Analytics at the speed of light: Feasibility and challenges for real time analytics of large datasets in hybrid clouds.
No full text''Real-time services'' is a very challenging topic. Running analytics in real-time when there is an abstract network layer makes things even more complicated. The demand to analyze huge data-sets in real time or in the long term has been increasing over the past decade in many sectors including health-care, general science and various online services with a prime example being the trending MMOG community. Combining the network and computation infrastructure efficiently is a challenge that requires careful planning and deployment. This work extends the work that has been done in the field of cloud computing by incorporating the network infrastructure in the analytics procedure. We follow a threefold approach to the problem using mathematical analysis, simulations and real world experiments. The results have shown that real-time analytics over the network is feasible, despite the lack of QoS provisioning in many cases. The bottleneck of the total procedure is oscillating between the network and the computation part of the system, depending on the available computation and networking infrastructure as well as the time complexity of the algorithms used for the analytics.Electrical Engineering, Track TelecommunicationsIntelligent SystemsElectrical Engineering, Mathematics and Computer Scienc
- …
