CAREER: Logical Reasoning of Networks with Partial Knowledge

Temple University, Philadelphia PA

Investigators

Abstract

Logical reasoning has made tremendous progress in computer networks in the past decade, assuring desirable behaviors of various types on many different networks. Such achievement relies on an important assumption: the reasoning process on an entirely known network always reaches a decisive conclusion. But the sheer size and complexity of modern networks make it hard, if not impossible, to obtain complete knowledge of the target network, and even when some knowledge is missing, it is still desirable to perform some (perhaps weaker) reasoning. This project challenges the assumption that logical reasoning must be complete and develops techniques for networks only partly known. To achieve logical reasoning of networks with uncertain events and limited visibility, this project plans to develop (1) loss-less modeling in which network uncertainty is explicitly handled without corrupting the querying capability; and (2) complete verification relative to the level of information available, which reaches an inconclusive result only when more information is needed. A realization of this vision is built around knowledge representation and partial reasoning, resulting in a simple yet powerful logical language for uncertain and missing information, enabling a rich set of semantics-based manipulation of partial networks by partial evaluation, program containment, predicate instantiation, etc. As a step towards logical reasoning of real-world networks in which an omniscient view is unlikely and partial reasoning is most sought-after, this project plays a unique role in the continued growth and evolution of computer networks. Simultaneously, the hyper-scale of networks as a driving challenge engages the knowledge reasoning community to revise and advance earlier complexity results, producing a more compelling use in networking. By leveraging the connection between the incomplete knowledge representation in this project and the numerical methods of inductive reasoning, this project may also facilitate future development of probabilistic reasoning for quantitative network behaviors. The project website https://ravel-net.org/ will be maintained to disseminate the progress of the project. Supporting tools will be made open-source; source code will also be available on the github server https://github.com/ravel-net with online documentation to facilitate independent validation and reuse; networking traces, benchmarks, and real-world dataset will be collected and made public. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.