| In the past decades, the Internet has been a vital infrastructure in a wide range of areas such as e-commerce, education, and entertainment. To route the packets through the Internet, it is extremely important for each node to maintain the status of the paths as accurate as possible. Traditionally, such status information is obtained from the update messages of the routing protocols such as OSPF (Open Shortest Path First) and BGP (Border Gateway Protocol). Recently, many researchers have proposed active probing schemes to obtain the performance oriented information such as loss rate, delay, and available bandwidth in addition to the mere connectivity information. In either case, to get more accurate information, frequent update or probing may be required.; However, frequent control and probing packets may cause adverse effects on the network. Because of the propagation delay and other delays, routing update messages may cause state inconsistency among the nodes, which creates loops or packet losses. The probing packets cause extra burden to the Internet, furthermore, network operators may consider them as attacks to the network.; To alleviate such problems, in this dissertation, we first select three types of networks as the representatives of the Internet's diverse components: wired intra-domain networks, static wireless networks, and multihomed stub networks. Then, we identify the problems of the non-data packets in each specific network and propose several schemes that can reduce the problems and even improve the performance. The schemes include local inference, local update, and exploitation of the AS hierarchy of the Internet.; The local inference provides a way to infer the status of a remote link without an explicit link state update message. This reduces the amount of link state updates and the state inconsistency. The local update is based on the blacklist, which is created in each packet upon a link failure and removed when it is not informative. The creation and removal limit the propagation of the link state updates. Finally, we investigate the efficacy of the Euclidean based distance estimation scheme, which is known to be helpful for routing peer selection in the peer to peer networks. |
