Abstract

Energy consumption has already become a major challenge to the current Internet. Most researches aim at lowering energy consumption under certain fixed performance constraints. Since trade-offs exist between network performance and energy saving, Internet Service Providers (ISPs) may desire to achieve different Traffic Engineering (TE) goals corresponding to changeable requirements. The major contributions of this paper are twofold: 1) we present an OSPF-based routing mechanism, Routing On Demand (ROD), that considers both performance and energy saving, and 2) we theoretically prove that a set of link weights always exists for each trade-off variant of the TE objective, under which solutions (i.e., routes) derived from ROD can be converted into shortest paths and realized through OSPF. Extensive evaluation results show that ROD can achieve various trade-offs between energy saving and performance in terms of Maximum Link Utilization, while maintaining better packet delay than that of the energy-agnostic TE. © 2012 IFIP International Federation for Information Processing. Document type: Part of book or chapter of book

Abstract

TEZ8153 Tez (Yüksek Lisans) -- Çukurova Üniversitesi, Adana, 2010. Kaynakça (s. 55-57) var. xi, 59 s. : res., hrt., tablo ; 29 cm. In this thesis, a web based public transportation route planning tool (ToTRoP) is developed. The routes are generated to transport people to a specific location (a hospital, a stadium, a university campus etc.) while keeping minimum cost and maximum passenger number. ToTRoP uses Google APIs to convert text based address data into geographical location data and then generates the most beneficial routes to a target point. ToTRoP is used to derive possible transportation routes from the city of Adana to Çukurova University's campus based on the anonymous address data of the freshmen students. According to the test results, transportation of approximately 76 % of the students is enabled through seven routes. The tool can work integratedly with other GIS software thanks to WFS support. This feature enables it to be a SOA based GIS application. Bu tezde, halk otobüsü taşımacılığı için coğrafi bilgi sistemi tabanlı rotalar üreten bir web aracı geliştirilmiştir. Farklı adreslerde yaşayan kişileri hedef bir noktaya (hastane, stadyum, üniversite kampüsü v.b.) taşımak amacıyla üretilen rotaların hedefe minimum maliyetle en fazla yolcunun erişmeleri amaçlanmıştır. Sunulan araç verileri coğrafik verilere dönüştürmek için Google Map API'leri kullanır ve hedef noktaya ulaşmak için en faydalı rotaları üretir. Bu araç Çukurova Üniversitesi kampüsüne ulaşım için yeni öğrencilerin adres bilgilerini baz alarak uygulanabilir taşıma rotaları üretti. Bu test verilerine göre yedi tane rota ile öğrencilerin yaklaşık %76 sının taşınması sağlandı. Ek olarak OGC tarafından tanımlanan WFS servisi ile diğer CBS uygulamaları ile entegre olabilir. Bu saye de yapılan uygulama SOA tabanlı olmuştur.

Abstract

Tato práce se zabývá technologií Multiprotocol Label Switching a to zejména moderními metodami, které je možné použít v rámci této technolologie. Jako příklad lze uvést využití podpory kvality služeb při směrování. V práci jsou navrhnuty a simulovány různé topologie a scénáře, které ověřují možnosti využití MPLS v podpoře kvality služeb. This work is considered to evaluate the needs of MPLS implementation in current IP networks with respect to Quality of Service guarantees. It shows many aspects and evaluations of the influence of different traffic classes. The best solutions are evaluated with simulations and can be implemented with respect to Quality of Service guarantees. A

Abstract

SDN approaches to inter-domain routing promise better traffic engineering, enhanced security, and higher automation. Yet, naïve deployment of SDN on the Internet is dangerous as the control plane expressiveness of BGP is significantly more limited than the data plane expressiveness of SDN, which allows fine-grained rules to deflect traffic from BGP’s default routes. Most notably, this mismatch may lead to incorrect forwarding behaviors such as forwarding loops and blackholes, ultimately hindering SDN deployment at the inter-domain level. In this work, we make a first step towards verifying the correctness of inter-domain forwarding state with a focus on loop freedom while keeping private the SDN rules, as they comprise confidential routing information. To this end, we design a simple yet powerful primitive that allows two networks to verify whether their SDN rules overlap, i.e. the set of packets matched by these rules is non-empty, without leaking any information about the SDN rules. We propose an efficient implementation of this primitive by using recent advancements in Secure Multi-Party Computation and we then leverage it as the main building block for designing a system that detects Internet-wide forwarding loops among any set of SDN-enabled Internet eXchange Points. Master [120] : ingénieur civil en informatique, Université catholique de Louvain, 2017

Abstract

Vehicle routing problems (VRP) are one of the most studied problems in combinatorial optimization. In recent years, it has gained the attention of many researchers and business organizations not only in its classical application, but also because of the many environmental considerations that it is possible to consider. Objectives that aims to reduce fuel consumption or directly the emissions of CO2 and other greenhouse gases (GHG) have become widely adopted. Being so, many models that estimate emissions and fuel consumption have been proposed in the literature, accounting for different factors that affect fuel consumption in road transportation, such as payload, slope and travel speed. These comprehensive models, while providing very accurate results in modeling emissions and fuel consumption, are very dependent on numerous parameters and user inputs, many not easily retrievable by practitioners. In this way, a Practical Pollution-Routing Problem (PPRP) is a VRP that aims to reduce fuel consumption using simple and practical computations based on the Fuel Consumption Rate (FCR) of vehicles. Another important variant of the VRP that has also attracted recent attention is the time-dependent vehicle routing problem (TDVRP), in which the effects of congestion and travel speeds fluctuations during the day are taken into account when designing the delivery routes. A time-dependent approach to the PPRP, however, has not been found in the literature. Thus, our research addresses this gap and aims to propose a new variant of this problem called the Practical Pollution-Routing Problem with Time-Dependent speeds (PPRP-TD), as it has important value to practitioners interested in the reduction of fuel consumption and the hazardous effects caused by diesel trucks. We propose several instance problems based on real operations of a major retailer company that distributes in São Paulo, and also analyze the time dependent speeds of the São Paulo network. To solve both the PPRP and the PPRP-TD, we propose the GRASP-FESA solution method, which is an FCR-based Extended Savings Algorithm (FESA) combined with a Greedy Randomized Adaptive Search Procedure (GRASP) metaheuristic. In the case of the PPRP-TD, we also perform an extensive time-dependent scheduling for all given routes. The method is able to provide good results, although being computationally expensive in the case of large instances. Problemas de roteirização de veículos (VRP) são alguns dos mais estudados problemas na otimização combinatória. Recentemente, pesquisadores e organizações também tem prestado atenção não apenas em suas aplicações clássicas, mas também nas muitas considerações ambientais que podem ser consideradas. Objetivos que buscam reduzir o consumo de combustíveis fósseis e a emissão de gases do efeito estufa tem sido amplamente utilizados. Assim sendo, diversos modelos para estimar as emissões de gases poluentes e consumo de combustível vem sendo propostos, considerado diversos fatores que influenciam no consumo de combustível, como a carga transportada, inclinação da via e velocidade de tráfego. Esses modelos compreensivos, embora forneçam resultados bem precisos na modelagem de emissões e consumo de combustível, são muito dependentes de uma grande quantidade de parâmetros e entradas dos usuários, sendo que muitos não são facilmente obtidos. Dessa forma, um Problema de Pollution-Routing Prático é um VRP que busca reduzir o consumo de combustível usando cálculos simplificados para o consumo de combustível, baseados na taxa de consumo de combustível de diferentes classes de veículos. Outra importante variante do VRP é o VRP dependente do horário, em que os efeitos de congestionamento e velocidades de tráfego flutuantes ao longo do dia são considerados ao se construir as rotas de entrega. Entretanto, uma abordagem ao PPRP com velocidades dependentes do horário não foi encontrada na literatura. Portanto, nossa pesquisa endereça esta lacuna e busca propor uma nova variante deste problema, chamado Problema de Pollution-Routing Prático com velocidades Dependentes do Horário (PPRP-TD), devido ao importante valor para empresas e praticantes interessados em reduzir o consumo de combustível de suas frotas, assim como os graves efeitos causados ao ambiente por veículos movidos a combustíveis fósseis. São propostas diversas instâncias baseadas nas operações reais de um grande varejista em São Paulo, além de uma análise das velocidades deptendentes do horário na rede de São Paulo. Para resolver tanto o PPRP quanto o PPRP-TD, é proposto o método de solução GRASP-FESA, que é um FCR-based Extended Savings Algorithm (FESA) combinado com a metaheurística GRASP (Greedy Randomized Adaptive Search procedure). No caso do PPRP-TD, também é realizada uma programação extensiva dependente do horário para todas as rotas. O método é capaz de obter bons resultados, embora seja computacionalmente caro no caso de grandes instâncias.

Abstract

Trabalho apresentado no âmbito do Mestrado em Engenharia Informática, como requisito parcial para obtenção do grau de Mestre em Engenharia Informática The high speeds and decreasing costs of Ethernet solutions has motivated providers’ interest in using Ethernet as the link layer technology in their backbone and aggregation networks. Provider scale Ethernet offers further advantages, providing not only an easy to manage solution for multicast traffic, but also transparent interconnection between clients’ LANs. These Ethernet deployments face altogether different design issues, requiring support for a significantly higher number of hosts. This support relies on hierarquization, separating address and virtual network spaces of customers and providers. In addition, large scale Ethernet solutions need to grant forwarding optimality. This can be achieved using traffic engineering approaches. Traffic engineering defines the set of engineering methods and techniques used to optimize the flow of network traffic. Static traffic engineering approaches enjoy widespread use in provider networks, but their performance is greatly penalized by sudden load variations. On the other hand, dynamic traffic engineering is tailored to adapt to load changes. However, providers are skeptical to adopt dynamic approaches as these induce problems such as routing instability, and as a result, network performance decreases. This dissertation presents a Simple and Stable Dynamic Traffic Engineering framework (SSD-TE), which addresses these concerns in a provider scale Ethernet scenario. The validation results show that SSD-TE achieves better or equal performance to static traffic engineering approaches, whilst remaining both stable and responsive to load variations.

Abstract

In a few years, the Internet has quickly evolved from a research network connecting a handful of users to the largest distributed system ever built. The Internet connects more than 20,000 Autonomous Systems (ASs) which are administratively independent networks. While the initial Internet was designed to provide a best-effort connectivity among these ASs, there is nowadays a growing trend to deploy new services such as Voice/Video over IP or VPNs. To support these emergent services, ASs need to better engineer their Internet traffic. Traffic Engineering encompasses several goals such as better spreading the traffic load inside a network and obtaining better end-to-end performance (lower latency or higher bandwidth)."br""br" Engineering the traffic inside a single AS is feasible and pretty well understood. To the opposite, interdomain traffic engineering is still a difficult problem. The main issue comes from the current Internet routing architecture, articulated around the Border Gateway Protocol (BGP). BGP propagates a subset of the Internet topology for scalability and stability reasons and does not optimize a single global objective. This limits the control each AS has on its routing and has dramatic implications for interdomain traffic engineering."br""br" In this thesis, we evaluate the primitive BGP-based routing control mechanisms. For this purpose, we designed and implemented a new approach for modeling BGP on large Internet-scale network topologies. Finally, to overcome the limitations of BGP in terms of routing control, we propose Virtual Peerings, a new mechanism based on a combination of BGP and IP tunneling. We apply Virtual Peerings to solve various interdomain traffic engineering problems such as balancing the load of Internet traffic received by an AS or decreasing the end-to-end latency of Internet paths. (FSA 3)--UCL, 2006

Abstract

Optimizing the way traffic is routed over networks has been of interest since we first started using computer networks to communicate and exchange information. Network technologies are constantly evolving and so do the underlying problems that need to be solved. This thesis focus on studying the recently proposed segment routing technology. In a traditional IP network, packets are routed using shorted paths according to weights that are configured on the network links. Segment routing offers a new way of routing traffic by allowing packets to do some detours on their way. Between these detours, traditional shortest path routing is used, making this technology have almost no usage overhead. We aim at providing a mathematical formalization of segment routing and showcase several of its use cases. We believe that such a formalization is going to help advance the research of the algorithmic aspects of segment routing by providing a solid mathematical foundation and notations which can serve as a starting point for others to research this topic. We leverage segment routing to solve traffic engineering problems, perform network monitoring and provide traffic duplication services that are robust to link failures. (FSA - Sciences de l'ingénieur) -- UCL, 2020

Abstract

O componente de planejamento faz parte do projeto de desenvolvimento dos veículos autônomos, e é responsável por gerar rotas para o sistema como um todo. Em aplicações em que o veículo deve visitar pontos em intervalos de tempo pré-determinados, o componente de planejamento se enquadra em um problema de roteirização conhecido da literatura, denominado problema de roteirização de veículos com janelas de tempo. Tal problema é uma generalização do problema clássico de roteirização de veículos classificado no grupo de problemas NP-Hard. Esse trabalho apresenta uma proposta de solução para o problema baseada na metaheurística algoritmo genético. Os cromossomos foram representados pela ordem de atendimento dos clientes sem delimitadores de rota. Para quebrar os cromossomos em rotas, foi utilizado um procedimento adaptado baseado em Prins (2004). A população inicial se constitui por uma parte construída com cromossomos criados aleatoriamente e outra parte construída através da heurística de inserção I1 de Solomon (1987), com quatro formas diferentes de inserir o primeiro cliente de cada rota. Na fase de recombinação, foram utilizados quatro tipos de crossover: uniforme, dois pontos, heurístico e PMX, e um operador de mutação baseado em uma busca heurística. A cada geração foram aplicados princípios de elitismo e pós-otimização utilizando a heurística -interchange de Osman (1993). O algoritmo foi testado nos conjuntos C1, C2, R1, R2, RC1 e RC2 de Solomon (1987) e os resultados foram comparados com os melhores resultados encontrados na literatura. The planning component is a part of autonomous vehicle development project and it is responsible to generate routes for the system as a whole. In applications which vehicle must to visit way points at predetermined intervals of time, the planning component fits into a routing problem known in the literature called routing problem with time windows. This problem is a generalization of the classical vehicle routing problem classified in the group of NP- Hard problems. This thesis presents a solution proposal to problem based on genetic algorithm metaheuristic. Chromosomes were represented by the order of serving customers without delimiters route. To split the chromosomes on routes, it is used a procedure adapted based on Prins (2004). The initial population is constituted by two parts: one with randomly created chromosomes and another constructed through the insertion heuristic I1 of Solomon (1987), with four different ways of insertion of the first customer of each route. In the recombination step, four types of crossover were used: uniform, two points, heuristic, and PMX, and a mutation operator based on heuristic search. In each generation it is applied principles of elitism and postoptimization using the -interchange heuristic of Osman (1993). The algorithm was tested on the sets C1, C2, R1, R2, RC1 and RC2 of Solomon (1987) and the results were compared with the best results found in the literature.