A distributed, compact routing protocol for the Internet

The Internet has grown in size at rapid rates since BGP records began, and continues to do so. This has raised concerns about the scalability of the current BGP routing system, as the routing state at each router in a shortest-path routing protocol will grow at a supra-linearly rate as the network grows. The concerns are that the memory capacity of routers will not be able to keep up with demands, and that the growth of the Internet will become ever more cramped as more and more of the world seeks the benefits of being connected. Compact routing schemes, where the routing state grows only sub-linearly relative to the growth of the network, could solve this problem and ensure that router memory would not be a bottleneck to Internet growth. These schemes trade away shortest-path routing for scalable memory state, by allowing some paths to have a certain amount of bounded “stretch”. The most promising such scheme is Cowen Routing, which can provide scalable, compact routing state for Internet routing, while still providing shortest-path routing to nearly all other nodes, with only slightly stretched paths to a very small subset of the network. Currently, there is no fully distributed form of Cowen Routing that would be practical for the Internet. This dissertation describes a fully distributed and compact protocol for Cowen routing, using the k-core graph decomposition. Previous compact routing work showed the k-core graph decomposition is useful for Cowen Routing on the Internet, but no distributed form existed. This dissertation gives a distributed k-core algorithm optimised to be efficient on dynamic graphs, along with with proofs of its correctness. The performance and efficiency of this distributed k-core algorithm is evaluated on large, Internet AS graphs, with excellent results. This dissertation then goes on to describe a fully distributed and compact Cowen Routing protocol. This protocol being comprised of a landmark selection process for Cowen Routing using the k-core algorithm, with mechanisms to ensure compact state at all times, including at bootstrap; a local cluster routing process, with mechanisms for policy application and control of cluster sizes, ensuring again that state can remain compact at all times; and a landmark routing process is described with a prioritisation mechanism for announcements that ensures compact state at all times.

Administrative justice and the control of bureaucratic decision-making: A study investigating how decision-makers in local authority education departments respond to the work of redress mechanisms

This socio-legal thesis has explored the factors responsible for explaining whether and how redress mechanisms control bureaucratic decision-making. The research considered the three principal institutions of administrative justice: courts, tribunals, and ombudsman schemes. The field setting was the local authority education area and the thesis examined bureaucratic decision-making about admissions to school, home-to-school transport, and Special Educational Needs (SEN). The thesis adopted a qualitative approach, using interviews and documentary research, within a multiple embedded case study design. The intellectual foundations of the research were inter-disciplinary, cutting across law, socio-legal studies, public administration, organization studies, and social policy. The thesis drew on these scholarly fields to explore the nature of bureaucratic decision-making, the extent to which it can be controlled and the way that learning occurs in bureaucracies and, finally, the extent to which redress mechanisms might exercise control. The concept of control was studied across all its dimensions – in relation both to ex post control in specific cases and the more challenging notion of ex ante or structuring control. The aim of the thesis was not to measure the prevalence of bureaucratic control by redress mechanisms, but to understand the factors that might explain its presence or absence in a particular area. The findings of the research have allowed for a number of analytical refinements and extensions to be made to existing theoretical and empirical understandings. 14 factors, along with 87 supporting propositions, have been set out with the aim of making empirically derived suggestions which can be followed up in future research. In terms of the thesis’ contribution to existing knowledge, its comparative focus and its emphasis on the broad notion of control offered the potential for new insights to be developed. Overall, the thesis claims to have made three contributions to the conceptual framework for understanding the exercise of control by redress mechanisms: it emphasizes the importance of ‘feedback’ in relation to the nature of the cases referred to redress mechanisms; it calls attention to the structure of bureaucratic decision-making as well as its normative character; and it discusses how the operational modes of redress mechanisms relate to their control functions.