A number of battery-driven sensor nodes are deployed to operate a wireless sensor network, and many routing protocols have been proposed to reduce energy consumption for data communications in the networks. We have proposed a new routing policy which employs a nearest-neighbor forwarding based on hop progress. Our proposed routing method has a topology parameter named forwarding angle to determine which node to connect with as a next-hop, and is compared with other existing policies to clarify the best topology for energy efficiency. In this paper, we also formulate the energy budget for networks with the routing policy by means of stochastic-geometric analysis on hop-count distributions for random planar networks. The formulation enables us to tell how much energy is required for all nodes in the network to forward sensed data in a pre-deployment phase. Simulation results show that the optimal topology varies according to node density in the network. Direct communication to the sink is superior for a small-sized network, and the multihop routing is more effective as the network becomes sparser. Evaluation results also demonstrate that our energy formulation can well approximate the energy budget, especially for small networks with a small forwarding angle. Discussion on the error with a large forwarding angle is then made with a geographical metric. It is finally clarified that our analytical expressions can obtain the optimal forwarding angle which yields the best energy efficiency for the routing policy when the network is moderately dense.

BGP dictates routing between autonomous systems with rich policy mechanisms in today's Internet. Operators translate high-level policy principles into low-level configurations of multiple routers without a comprehensive understanding of the actual effect on the network behaviors, making the routing management and operation an error-prone and time-consuming procedure. A fundamental question to answer is: how to verify the intended routing principles against the actual routing effects of an ISP? In this paper, we develop a methodology RPIM (Routing Policy Inference Model) towards this end. RPIM extracts from the routing tables various policy patterns, which represent certain high-level policy intentions of network operators, and then maps the patterns into specific design primitives that the ISP employs. To the best of our knowledge, we are the first to infer routing policies in ISP networks comprehensively from the aspects of business relationship, traffic engineering, scalability and security. We apply RPIM to 11 ASes selected from RIPE NCC RIS project, and query IRR database to validate our approach. Vast majority of inferred policies are confirmed by the policy registries, and RPIM achieves 96.23% accuracy excluding validation difficulties caused by incompleteness of the IRR database.

At present, the global Internet consists of many ASes. Each AS pays a pre-determined connection fee to another AS for connecting its network with that AS's network. The connection fee type charging may be rational in case of transferring the best-effort type traffic. However, usage charging is necessary to transferring the resource guaranteed type traffic such as the Intserv traffic and the Diffserv traffic. In this case, each AS pays a per-flow fee to another AS every time it routes a flow into another AS. The per-flow fee paid by each AS becomes a part of the cost for that AS. Thus, each AS needs to select a route with the lowest price to improve its own profit. In this paper, we call such an inter-AS routing scheme a price-based inter-AS routing scheme. When each AS has a request to route an inter-AS flow, it can select an inter-AS route with the lowest price to improve its own profit by this routing scheme. Cost-dependent pricing scheme is suitable for the price-based inter-AS routing scheme because it can reduce frequency of price information exchange between ASes. However, in the cost-dependent pricing scheme, profit in each AS depends on the distribution of path costs in that AS. Generally, ASes with narrow ranges of path costs cannot obtain sufficient profits compared to ASes with wide ranges of path costs. Thus, we propose a routing policy for ASes with narrow ranges of path costs to improve their profits efficiently and evaluate its effect using a simple routing model.