Measuring Effectiveness of Address Schemes for AS-level Graphs

摘要: OF DISSERTATION Measuring Effectiveness of Address Schemes for AS-level Graphs This dissertation presents measures efficiency and locality Internet addressing schemes. Historically speaking, many issues, faced by the Internet, have been solved just in time, to make work [Han06]. Consensus, however, has reached that today’s routing system is facing serious scaling problems: multi-homing which causes finer granularity policies control realize various traffic engineering requirements, an increased demand provider-independent prefix allocations injects unaggregatable prefixes into Default Free Zone (DFZ) table, ever-increasing user population mobile edge devices. As a result, DFZ table again growing at exponential rate. Hierarchical, topology-based long considered crucial forwarding scalability. Recently, number research efforts are considering alternatives this traditional approach. With goal informing such research, we investigated address assignment existing (IPv4) Internet. In particular, ask question: “how can measure scheme given input graph?” To do so, first define notion or based on average bit-hops required advertize all order quantify how far from “optimal" current is, assign ASes “from scratch" manner preserves observed semantics, using three increasingly strict definitions equivalence. Next propose another metric some sense quantifies “efficiency" labeling independent forwarding/routing mechanisms. We validate effectiveness applying it series schemes with increasing randomness graph. After apply across years compare results those compact