Security Issues in Small World Network Routing

Small world network (SWN) have been shown to be navigable - a short route can be found using efficiently using decentralized algorithms. This routing relies on nodes having a position to guide the routing such as its coordinates. Even in the absence of positional information such as node coordinates, by using local self-reorganization, it is possible to reconstruct a proxy for the node coordinates which still allows for efficient routing. This paper shows that in the presence of malicious nodes, the self-reorganization mechanism breaks down. We investigate self-protection mechanisms for such SWNs. Preliminary results using a simple restart mechanism for self-tuning shows that much of the effect of malicious nodes can be mitigated.