Os problemas de colorac Ëao de vÂertices e de arestas, que consistem em determinar o menor nÂumero de cores necessÂarias para colorir os vÂertices e arestas de um grafo, respectivamente, de forma que vÂertices adjacentes e arestas adjacentes, respectivamente, possuem cores distintas, sËao problemas computacionalmente difÂıceis e sËao objeto de pesquisa recorrente em teoria do grafos em virtude de inÂumeros problemas prÂaticos que eles modelam. No presente trabalho, estudamos o pior desempenho dos algoritmos gulosos de colorac Ëao de vÂertices e de arestas. O algoritmo guloso tem o seguinte princÂıpio geral: receber, um a um, os vÂertices (respect. as arestas) do grafo a ser colorido, atribuindo sempre a menor cor possÂıvel ao vÂertice (resp. aresta) a ser colorido. Observamos que colorir de forma gulosa as arestas de um grafo equivale a colorir de forma gulosa o seu grafo linha, tendo sido este o maior interesse na pesquisa em colorac Ëao gulosa de arestas. O pior desempenho dos algoritmos Âe medido pelo maior nÂumero de cores que eles podem utilizar. No caso da colorac Ëao gulosa de vÂertices, esse Âe o nÂumero de Grundy ou nÂumero cromÂatico guloso do grafo. No caso da colorac Ëao de arestas, esse Âe o Âındice cromÂatico guloso ou Âındice de Grundy do grafo. Sabe-se que determinar o nÂumero de Grundy de um grafo qualquer Âe NP-difÂıcil. A complexidade de determinar o Âındice de Grundy de um grafo qualquer era entretanto um problema em aberto. Na presente dissertac Ëao, provamos dois resultados de complexidade. Provamos que o nÂumero de Grundy de um grafo (q,q−4) pode ser determinado em tempo polinomial. Essa classe contÂem estritamente a classe dos cografos e P4-esparsos para os quais o mesmo resultado havia sido estabelecido. Esse resultado generaliza portanto aqueles resultados. O algoritmo apresentado usa a decomposicÂËao primeval desses grafos, determinando o parËametro em tempo linear. No que se refere `a colorac Ëao de arestas, provamos que o problema de determinar o Âındice de Grundy Âe NP-completo para grafos em geral e polinomial para grafos caterpillar, implicando que o nÂumero de Grundy Âe polinomial para os grafos linha desses. Mais especificamente provamos que o Âındice de Grundy dos caterpillar Âe D ou D+1 e apresentamos um algoritmo polinomial para determinÂa-lo exatamente. / The vertices and edges colorings problems, which consists in determine the smallest number of colors needed to color the vertices and edges of a graph, respectively, so that adjacent vertices and adjacent edges, respectively, have distinct colors, are computationally hard problems and recurring subject of research in graph theory due to numerous practical problems they model. In this work, we study the worst performance of greedy algorithms for coloring vertices and edges. The greedy algorithm has the following general principle: to receive, one by one, the vertices (respect. edges) of the graph to be colored by assigning always the smallest possible color to the vertex (resp. edge) to be colored. We note that so greedy coloring the edges of a graph is equivalent to greedily coloring its line graph, this being the greatest interest in research on greedy edges coloring. The worst performance of the Algorithms is measured by the greatest number of colors they can use. In the case of greedy vertex coloring, this is the number of Grundy or greedy chromatic number of the graph. For the edge coloring, this is the greedy chromatic index or Grundy index of the graph. It is known that determining the Grundy number of any graph is NP-hard. The complexity of determining the Grundy index of any graph was however an open problem. In this dissertation, we prove two complexity results. We prove that the Grundy number of a (q,q−4)-graph can be determined in polynomial time. This class contains strictly the class of cografos P4-sparse for which the same result had been established. This result generalizes so those results. The presented algorithm uses the primeval decomposition of graphs, determining the parameter in linear time. About greedy edge coloring, we prove that the problem of determining the Grundy index is NP-complete for general graphs and polynomial for catepillar graphs, implying that the Grundy number is polynomial for graphs of line of caterpillars. More specifically, we prove that the Grundy index of a caterpillar is D or D+1 and present a polynomial algorithm to determine it exactly.

The performance of the virtual switch Open vSwitch (OVS) is insufficient to satisfy the current requirements for link bandwidth of the server connections. There is an effort to accelerate the OVS both in the software and in the hardware by offloading the datapath to the smart network interface cards. In this work the COMBO card for 100G Ethernet developed by CESNET is used to accelerate the OVS. The suggested solution utilizes the firmware for FPGA generated from the definition in the P4 language to classify the packets in the card and DPDK for the data transfers and offloading the classification rules into the card. Forwarding of one flow with the shortest frames from physical to physical interface using one CPU core reaches forwarding rate of 11.2 Mp/s (10 times more than the standard OVS) with classification in the card and 5.9 Mp/s without classification in the card.

The domain specific language P4 is a novel initiative which extends the Software-Defined Networking (SDN) paradigm by allowing for data plane programmability. Network virtualisation is a class of network technologies which can be used to abstract the addressing in a network, allowing multiple tenants to utilise the network resources while being agnostic to the underlying network and the other tenants. In other words, twins of tenants using the same addresses can co-exist on the same underlying network. If a twin is a distributed network, it may even be spread out across multiple sites which are connected to a common backbone. In this study, network virtualisation using P4 is evaluated with emphasis on scalability in terms of number of twins and sites. A set of potential network virtualisation technologies are identified and categorised. Based on this categorisation, two variations of network virtualisation are implemented on the P4 capable software switch BMv2 and the performance of both variations are evaluated against the non-P4 solution Linux bridge. Linux bridge was found to yield 451 times more useful bandwidth than the best performing P4 implementation on BMv2, while also learning MAC addresses faster and generating less traffic on the backbone. It is concluded that the performance of network virtualisation implemented and running on BMv2 is worse compared to the non-P4 solution Linux bridge.

京都大学 / 0048 / 新制・課程博士 / 博士(薬科学) / 甲第20305号 / 薬科博第74号 / 新制||薬科||8(附属図書館) / 京都大学大学院薬学研究科薬科学専攻 / (主査)教授 中山 和久, 教授 竹島 浩, 教授 根岸 学 / 学位規則第4条第1項該当 / Doctor of Pharmaceutical Sciences / Kyoto University / DFAM

The advent of Software Defined Networking (SDN) and programmable data planes has revolutionized the networking domain, enabling the programming of networking functions down to the silicon level responsible for data packet switching. Unfortunately, while this programmability offers greater flexibility and control, it also increases the likelihood of introducing software bugs. To counter this risk, rigorous testing methodologies and strategies are essential to ensure the reliability, security, and stability of SDN deployments. A comprehensive approach should combine various techniques, including formal verification, fuzz, and performance testing. Model-Based Testing (MBT) is a technique that can significantly enhance the effectiveness of SDN testing. By leveraging formal models of the system under test, MBT automatically generates test cases that can help identify potential issues in network configuration, data plane programming, and network protocols. Utilizing MBT allows network administrators to systematically explore SDN components’ possible states and transitions, resulting in a higher level of coverage and confidence in the system’s overall stability and security. However, a lack of information on applying MBT in an SDN environment challenges its full implementation and utilization in this field. This master thesis aims to investigate and demonstrate the application of MBT to programmable data plane functions. This work uses VLAN tagging as the target data plane function, and AltWalker is employed as the MBT tool for generating and executing tests on an SDN switch. The results present an initial testing methodology that, when applied to the VLAN tagging function, can provide insights into the potential benefits and challenges of using MBT for SDN testing. This thesis lays the groundwork for further exploration and refinement of MBT methodologies in the context of SDN and programmable data plane functions.

The rise of social media has created an endless source of possibilities for companies to interact and connect with their target audiences. As it is a new channel, companies may experience uncertainty on how to use it to its fullest potential. The purpose of this study is to describe how the Public Service radio channel, P4 Kalmar, use its Facebook page and how its members perceive the communication on this platform. We have also presented recommendations on how P4 Kalmar can improve the relationship with its members. To reach our conclusions we have combined theoretical references with a quantitative content analyze, a survey and qualitative depth interviews. By analyzing our findings we came to the conclusion that P4 Kalmar have to develop a strategy for communicating on social media. But since no general communication strategy for the organization exists they have to develop one before developing one for social media. P4 Kalmar should also niche themselves into becoming the main source for local news on Facebook. Finally they have to focus on the fact that social media is relationship based and that this is the primary reason for their existence on Facebook.

As computer networks grow more complex as the number of connected devices increases, the monitoring and management of such networks also increases in complexity. Current network monitoring tools such as NetFlow, sFlow, ping, traceroute, and tcpdump prove to be both tedious and offer low accuracy when reporting the network state. With the recent emergence in programmable data plane switches, a new framework was created by the P4 Applications Working Group named In- Band Network Telemetry (INT). INT enables network programmers to obtain fine- grained telemetry information directly from the data plane without involvement from the control plane. This project implements INT in hardware Intel Tofino switches and provides a comparison between the three different INT modes of operations (INTXD, INTMX and INTMD) as defined in the framework specifications. The results show the effects of INT when implemented in the data plane, providing the ability to monitor the path a packet took through the network (switch ingress and egress ports), the hop latency, queue occupancy and queuing latency. However, INT can increase the overhead in both the packet and the bandwidth of the network, reducing application throughput. Measures to counteract this are discussed. An earlier implementation of a standalone telemetry report monitoring system was used and analysed, and it allowed for telemetry reports to be reported and visualised at a rate of up to 50 Kpps without any event detection. The results are applied to a Saab 9LV CMS network, and it is concluded that INT allows network operators to obtain a precise overview of the network state, allowing for easier network troubleshooting. / När datornätverk växer sig i komplexitet när antalet anslutna enheter ökar, metoder för övervakningen och hanteringen av sådana nätverk ökar också i komplexitet. Nuvarande nätverksövervakningsverktyg som NetFlow, sFlow, ping, traceroute och tcpdump visar sig vara både besvärliga och ger låg noggrannhet när man rapporterar nätverkstillståndet. Med den framväxten av programmerbara dataplan och programmerbara switchar skapades ett nytt ramverk av P4 Applications Working Group som heter INT. INT gör det möjligt för nätverksprogrammerare att erhålla finkornig telemetriinformation direkt från dataplanet utan inblandning från kontrollplanet. Detta projekt implementerar INT i Intel Tofino- switchar och ger en jämförelse mellan de tre olika INT- driftsätten (INTXD, INTMX och INTMD) enligt definitionen i specifikationerna. Resultaten visar effekterna av INT när det implementeras i dataplanet, inklusive möjligheten att övervaka vägen som ett paket tog genom nätverket (både ingångs- och utgångsportar på switcharna), hop- latens, köbeläggning och kö- latens. Dock kan INT öka overhead i både paketet och bandbredden i nätverket, vilket minskar applikationsgenomströmningen. Åtgärder för att motverka detta diskuteras. En tidigare implementering av ett fristående övervakningssystem för telemetrirapporter användes och analyserades, och det var möjligt att rapportera och visualisera telemetirapporter med en hastighet på upp till 50 Kpps utan någon händelsedetektering. Resultaten tillämpas på ett Saab 9LV CMS- nätverk och man drar slutsatsen att INT tillåter nätoperatörer att få en noggrann översikt över nätverkstillståndet, vilket möjliggör enklare nätverksfelsökning.

This study has examined how two local media companies use Facebook in their operation. The two companies surveyed are P4 Kalmar Sweden Radio and the Barometer OT in Kalmar. Two sub-studies were conducted, a qualitative interview-study with responsible social media editors as well as a quantitative content analysis of Facebook publications over a month's time. The results show that Facebook is seen as a very important platform for the media companies to reach out with their journalism, while Facebook's algorithms affect the news rating and compels companies to constantly re-evaluate the content. The result also shows that traditional news with local connection constitutes the majority of Facebook publications and that it is this category that mainly renders the most response from the audience.

This thesis is an exploration of how professional status is gained and sustained. Sociologists, in taking for granted which occupations are universally identified as professions have concentrated their studies on elite occupations, primarily law and medicine. Their attention has been focussed on the occupational, organizational and behavioural characteristics of these professions, rather than the personal or social characteristics of the incumbents. Consequently, although acknowledging that class, gender and race can provide or limit the resources for professionalizing, these personal attributes have not been considered central to the understanding of the term profession. The research is concerned with the relationship between professional status and gender in probation during a period in its history when it faced considerable threats. It traces the profession's history and maps its rise and fall in relation to its changing gendered composition, culminating in the government's decision to remove the prior qualification for practice in 1995 in order to attract ex-servicemen into probation. The reconstruction of probation into a credible profession is the substantive focus of this study. The analysis of the reconstruction is through a gendered lens and a discourse analytical approach is used to examine texts prepared by probation to promote its cause. This thesis concludes that the status of an occupation is directly related to its gendered construction and to be considered a 'full' profession requires middle class masculinity. Whilst masculine characteristics continue to be necessary for influence and success, the constant drift towards the masculinization of everyone undermines the contribution women can make to organizations and services. In retrospectively revealing the processes through which masculinization and professionalization are discursively achieved, the study opens up the possibility for future challenges to the devaluation of occupations dominated by women.

OLIVEIRA, Ana Karolinna Maia de. Estudo de casos de complexidade de colorações gulosa de vértices e de arestas. 2011. 58 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2011. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-05-24T19:36:17Z No. of bitstreams: 1 2011_dis_akmoliveira.pdf: 520341 bytes, checksum: b0c0d48f19d7c3e376c2c79c3a815b08 (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-05-24T19:36:55Z (GMT) No. of bitstreams: 1 2011_dis_akmoliveira.pdf: 520341 bytes, checksum: b0c0d48f19d7c3e376c2c79c3a815b08 (MD5) / Made available in DSpace on 2016-05-24T19:36:55Z (GMT). No. of bitstreams: 1 2011_dis_akmoliveira.pdf: 520341 bytes, checksum: b0c0d48f19d7c3e376c2c79c3a815b08 (MD5) Previous issue date: 2011 / The vertices and edges colorings problems, which consists in determine the smallest number of colors needed to color the vertices and edges of a graph, respectively, so that adjacent vertices and adjacent edges, respectively, have distinct colors, are computationally hard problems and recurring subject of research in graph theory due to numerous practical problems they model. In this work, we study the worst performance of greedy algorithms for coloring vertices and edges. The greedy algorithm has the following general principle: to receive, one by one, the vertices (respect. edges) of the graph to be colored by assigning always the smallest possible color to the vertex (resp. edge) to be colored. We note that so greedy coloring the edges of a graph is equivalent to greedily coloring its line graph, this being the greatest interest in research on greedy edges coloring. The worst performance of the Algorithms is measured by the greatest number of colors they can use. In the case of greedy vertex coloring, this is the number of Grundy or greedy chromatic number of the graph. For the edge coloring, this is the greedy chromatic index or Grundy index of the graph. It is known that determining the Grundy number of any graph is NP-hard. The complexity of determining the Grundy index of any graph was however an open problem. In this dissertation, we prove two complexity results. We prove that the Grundy number of a (q,q−4)-graph can be determined in polynomial time. This class contains strictly the class of cografos P4-sparse for which the same result had been established. This result generalizes so those results. The presented algorithm uses the primeval decomposition of graphs, determining the parameter in linear time. About greedy edge coloring, we prove that the problem of determining the Grundy index is NP-complete for general graphs and polynomial for catepillar graphs, implying that the Grundy number is polynomial for graphs of line of caterpillars. More specifically, we prove that the Grundy index of a caterpillar is D or D+1 and present a polynomial algorithm to determine it exactly. / Os problemas de colorac¸ ˜ao de v´ertices e de arestas, que consistem em determinar o menor n´umero de cores necess´arias para colorir os v´ertices e arestas de um grafo, respectivamente, de forma que v´ertices adjacentes e arestas adjacentes, respectivamente, possuem cores distintas, s˜ao problemas computacionalmente dif´ıceis e s˜ao objeto de pesquisa recorrente em teoria do grafos em virtude de in´umeros problemas pr´aticos que eles modelam. No presente trabalho, estudamos o pior desempenho dos algoritmos gulosos de colorac¸ ˜ao de v´ertices e de arestas. O algoritmo guloso tem o seguinte princ´ıpio geral: receber, um a um, os v´ertices (respect. as arestas) do grafo a ser colorido, atribuindo sempre a menor cor poss´ıvel ao v´ertice (resp. aresta) a ser colorido. Observamos que colorir de forma gulosa as arestas de um grafo equivale a colorir de forma gulosa o seu grafo linha, tendo sido este o maior interesse na pesquisa em colorac¸ ˜ao gulosa de arestas. O pior desempenho dos algoritmos ´e medido pelo maior n´umero de cores que eles podem utilizar. No caso da colorac¸ ˜ao gulosa de v´ertices, esse ´e o n´umero de Grundy ou n´umero crom´atico guloso do grafo. No caso da colorac¸ ˜ao de arestas, esse ´e o ´ındice crom´atico guloso ou ´ındice de Grundy do grafo. Sabe-se que determinar o n´umero de Grundy de um grafo qualquer ´e NP-dif´ıcil. A complexidade de determinar o ´ındice de Grundy de um grafo qualquer era entretanto um problema em aberto. Na presente dissertac¸ ˜ao, provamos dois resultados de complexidade. Provamos que o n´umero de Grundy de um grafo (q,q−4) pode ser determinado em tempo polinomial. Essa classe cont´em estritamente a classe dos cografos e P4-esparsos para os quais o mesmo resultado havia sido estabelecido. Esse resultado generaliza portanto aqueles resultados. O algoritmo apresentado usa a decomposic¸˜ao primeval desses grafos, determinando o parˆametro em tempo linear. No que se refere `a colorac¸ ˜ao de arestas, provamos que o problema de determinar o ´ındice de Grundy ´e NP-completo para grafos em geral e polinomial para grafos caterpillar, implicando que o n´umero de Grundy ´e polinomial para os grafos linha desses. Mais especificamente provamos que o ´ındice de Grundy dos caterpillar ´e D ou D+1 e apresentamos um algoritmo polinomial para determin´a-lo exatamente.