Routing Algorithms Based on Partial Deployment of SAVA Nodes in Trustworthy Internet

Abstract

Although the fundamental principles of best-effort and destination address based packet forwarding in today's Internet have brought tremendous convenience, the trustworthy issue in Internet is a hot problem since the lack of source IP address checking in most cases makes it easy for the attackers to spoof the source address. Therefore, one challenge in trustworthy Internet is to build a feasible mechanism to verify the source address. Recently, a feasible mechanism called Source Address Validation Architecture (SAVA) has been proposed to specify standardization of methods for building effective source-address validation to ensure that packets forwarded hold authentic source addresses. In SAVA mechanism, if a packet has been recognized as a spoofed source address, it will be dropped by the SAVA router and not be transmitted to the next hop. In our work, we study the routing algorithms based on partial deployment of SAVA nodes in Internet and propose three kinds of routing algorithms, i.e., Shortest-Path Algorithm (SPA), SAVA based Shortest-Path Algorithm (SSPA), and SAVA based Shortest-Path Algorithm with Load Balancing (SSPALB). To the best of our best knowledge, this is the first investigation for SAVA mechanism from the point of routing method. In SPA, the packet will be routed on the shortest path that may not traverse the SAVA node, and then the SAVA requirement may not be ensured. In SSPA, the packet will be routed on the shortest path that must traverse one SAVA node such that the SAVA requirement can be ensured. In SSPALB, the packet will be routed on the shortest path that must traverse one SAVA node at the same time this SAVA node must be the least-load such that the SAVA requirement can be ensured and the load can be more balancing. We simulate an incremental traffic model for the three kinds of routing algorithms to compare the performances of SAVA Satisfactory Degree (SSD) and Load Balancing (LB). Simulation results show that:

1. the SSDs of SSPA and SSPALB can reach 100% while the SSD of SPA is only 20%–30%, which means that SSPA and SSPALB are completely satisfactory for SAVA requirements but SPA cannot;

2. the LB of SSPALB can reach 100% while the LBs of SPA and SSPA are only 70%–80%, which means that SSPALB is more favorable for the load balancing.

This work was supported in part by the National Natural Science Foundation of China (Nos. 60802023, 60673159, 70671020), the National High-Tech Research and Development Plan of China (No. 2006AA01Z214), the Specialized Research Fund for the Doctoral Program of Higher Education (Nos. 20070145096, 20070145017, 20060145012), and the Program for New Century Excellent Talents in University.