|
This paper describes how a network can continue to function in the presence of Byzantine failures.
A Byzantine failure is one in which a node, instead of halting (as it would in a fail-stop failure),
continues to operate, but incorrectly. It might lie about routing information, perform the
routing algorithm itself flawlessly, but then fail to forward some class of packets correctly, or
flood the network with garbage traffic. Our goal is to design a network so that as long as one
nonfaulty path connects nonfaulty nodes A and B, they will be able to communicate, with some
fair share of bandwidth, even if all the other components in the network are maximally malicious.
We review work from 1988 that presented a network design that had that property, but
required the network to be small enough so that every router could keep state proportional to
n2, where n is the total number of nodes in the network. This would work for a network of size
on the order of a thousand nodes, but to build a large network, we need to introduce hierarchy.
This paper presents a new design, building on the original work, that works with hierarchical
networks. This design not only defends against malicious routers, but because it guarantees
fair allocation of resources, can mitigate against many other types of denial of service attacks.
|
