Scalable algorithms for communication networks

摘要: Network scalability has emerged as the essential problem in designing architectures and protocols for large-scale communication systems. Minor efficiencies, that can be tolerated small networks, accumulate become a dominant factor determining performance of large networks. In this thesis, we consider three problems are related to scalability. First, examine size routing tables number nodes network increases. It is shown widely used shortest-path straightline algorithm implemented only when nodes’ memory increases with size. On other hand, it established there exist information-efficient algorithms, e.g., column-first protocol, route packets correctly even if each node capable storing information on fixed destinations only. second part, present novel computational model utilizing time encoding, enables distributed scheduling mechanism. The propose achieves comparable centralized algorithms under uniform traffic. Exploiting connection between switch interval packing, argue nature limits maximum relative load 1 − e−2 worst-case scenario. stability improved by enabling reversibility decision making. Finally, discuss bandwidth sharing multi-hop A buffer management policy utilizes simple packet attributes delivers constant fraction possible throughput. Moreover, robust heavy traffic loads sense throughput does not degrade due congestion.