Reviews: BorderPatrol

[Rodrigo Fonseca]

Hi,

Please post your reviews here. Sorry for the delay!

Rodrigo

[Hammurabi Mendes]

Paper Title

BorderPatrol: Isolating Events for Black-box Tracing

Author(s)

Eric Koskinen, John Jannotti

Date

EuroSys, April 2008

Novel Idea

Modifying/parsing the input stream in order to provide event isolation
and improve trace correlation.

Main Result(s)

The paper presents BorderPatrol, a system that intercepts library
calls and, by identifying message boundaries through custom-designed
protocol processors (one per protocol, not per application), logs
protocol events, identify message "witnesses" (matching of
request/response identifiers) and controls the data flow to the
modules to identify its responses given any particular protocol event
(isolating events and improving the correlation).

Impact

The technique improves the inference on the causality of message
traces using the ideas described in the previous two sections, and it
is applicable when we can intercept the points of the system where
input is delivered. Important: they make some assumptions about the
system components (they call honesty, immediacy, and independence).

Evidence

In my opinion, they support their argument by 4 points:

(1) The authors describe how their techniques were implemented, which
provides evidence about the viability of the approach; (2) they
describe common approaches that real-world programs handle multiple
concurrent requests, and say how BorderPatrol can attribute actions to
the correct generator in the most common cases; (3) they show that
their approach has acceptable overhead for the common cases of
workloads (they have bad results on exec-bound workloads, but they
imply that these cases are uncommon) in "micro-benchmarks"; (4) they
show 8-16% overhead in one real-case (note: they have 2% and 96% in
two tests in the other real case, but they have some comments about
the 96% overhead result).

Prior Work + Competitive work

The related work section is extensive. They mention systems that use
application-provided information (Magpie, TraceBack, WebSphere, and
others), and also ones that require inserting metadata on the
applications to perform the inspection (Causeway, X-Trace).

Reproducibility

I think that their "micro-benchmarks" can be reproduced (they give an
idea of what is necessary - it appears reproducible). The BorderPatrol
system is available online; the "control" systems that they used are
obtainable online. I think that the case studies can also be
reproduced, but with much more work (for example, talking to people
responsible by "dearinter.net" to obtain logs and to validate traces).
Interestingly, setting up a custom system of common components would
facilitate the reproducibility, but it would not be "real"). :)

Questions + Criticism

Playing with isolation is a good idea, and the assumptions that they
make appear reasonable at first sight. I'm worried about (1) the task
of modifying all points of input delivery; (2) the real complexity of
protocol processors.

For (1): Considering increasingly complex systems, up to what point
making changes in the input delivery points of the system is viable?

For (2) Isn't it the case that most black-box components use
"black-box messages" to communicate? Although interoperability implies
in standards, the components could still, say, cypher messages to
provide confidentiality. The protocol processors can still be a
"man-in-the-middle", but it doesn't look like they are 100-line
processors anymore.

With concerns (1) and (2), the matter is viability. Isn't easier to
provide hints on the application?

There is another question in the following section (I think it makes
more sense to put it there).

Ideas for further work

In view of the previous section, they could improve/detail better in
an article their infrastructure to building protocol processors.
Another thing, perhaps, is using fast-prototyping and library-rich
languages (python, ruby) to build the protocol processors. [Another
Question] Is there any supporting infrastructure for this languages
already?

[Abhiram Natarajan]

Paper Title: BorderPatrol: Isolating Events for Black-box tracking

Author(s): Erix Koskinen, John Jannotti

Date: 2008, EuroSys

Novel Idea: Usage of "active observation" and "Protocol Processors" to
modify the event stream observed by modules, and leverage knowledge
about standard protocols, avoiding application-specific
instrumentation, respectively

Main Result(s): BorderPatrol: a system that obtains precise traces for
black-box systems that cannot be traced by any other technique.

Impact: Causal request traces are always worth their weight in gold,
because they show a request is processed, and also help in detecting
performance problems; Border Patrol is a system which aids in
obtainment of these traces.

Evidence: The authors confirm the accuracy of BorderPatrol's traces by
comparing to manual instrumentation, and also study the developer
effort required for each kind of trace.

Prior Work: There is quite a bit of relevant work, in various realms:
(a) Instrumentation - Magpie, TraceBack, Commercially available
products, King
(b) Pervasive Frameworks - Pinpoint, Causeway, X-Trace
(c) Probabilistic Correlation - Work by HP Labs, Whodunit
(d) Analysis From Causal Paths - Pip, Pinpoint

Competitive Work: The authors stress their system with realistic
workloads from real-life case studiess.

Reproducibility: Pretty elaborate in most of their descriptions, I am
guessing it could be implemented in some measure. However, obtaining
their exact results would be hard.

Question: Is this used anywhere?

Criticism: Very nicely written.

[Zikai]

Paper Title: Border Patrol: Isolating Events for Black-box Tracing
Author(s): Eric Koskinen, John Jannotti (Brown University)
Date/Conference: EuroSys 08 (Apr, 2008)

Novel Idea: Use protocol processors that have protocol-specific
knowledge to implement event isolation and message witnesses. In all,
they allow tracing that actively isolates black-box inputs so that
request paths can be precisely observed without materially affecting
the overall application’s ability to multiplex requests.

Main Results:
(1) Analyze black-box model and make three fundamental assumptions
( honesty, immediacy and independence). Based on the assumptions,
design and implement BorderPatrol, a tracing tool that performs active
observation.
(2) Evaluate BorderPatrol with one multi-threaded system and one event-
driven system. Prove that it can achieve precise tracing with low
overhead in terms of latency.

Evidence: In part 6, two case studies are performed: one with a multi-
threaded Python application tier between an Apache web server front-
end and a PostgreSQL database backend, the other with an event-driven
web server (Zeus). The two cases could only be handled by manual
instrumentation before, and authors show BorderPatrol is able to cope
with them well.

In part7, authors first show a series of micro-benchmarks reflecting
how BorderPatrol increases latency on a single server when workload is
disk-bound, network-bound, file-bound and exec-bound. Then they
measure latency in the two cases in part 6 under realistic day-to-day
workload.

Prior Work:
Libevent [10], Libasync [11], Isaacs et al.[5], TurboGears[20], Apache
web server[3], Zeus[21]

Competitive Work:
Pinpoint [7], Pip[13], Stardust[19]

Reproducibility: Because both source code and binary of BorderPatrol
are publicly available, it is easy to reproduce the experiments
according to the paper setting.

Question: What’s the scalability of the approach? In a system with
more tiers and more servers, is it able to deliver tracing results
correctly and with low overhead?

On Nov 3, 10:10 pm, Rodrigo Fonseca <rodrigo.fons...@gmail.com> wrote:

[Visawee]

Paper Title :
BorderPatrol: Isolating Events for Black-box Tracing

Author(s) :
Eric Koskinen, John Jannotti

Date :
EuroSys’08, April 1–4, 2008, Glasgow, Scotland, UK


Novel Idea :
A tracing technique that actively isolates black-box inputs so that
request paths can be observed accurately. This technique uses

knowledge about standard protocols, avoiding application-specific

instrumentation.

Main Result(s) :
BorderPatrol is able to reconstructs causal paths for a range of
diverse servers including Apache, thttpd, Zeus, BIND, PostgreSQL, and
TurboGears, without modifying any server source code. The overhead of
these tracings is about 10-15%.


Impact :
Helps developers in analysing distributed systems in order to debug
the systems or find opportunities for optimization.


Evidence :
The authors conduct several case studies to confirm that BorderProl is
able to precisely obtain traces of the systems without manual
instrumenting. These case studies cover Zeus, Bind, Apache 1.3,
TurboGears, and PostgreSQL. Then the authors conduct the performance
evaluation tests to see the performance overhead when using
BorderPatrol.
The micro-benchmarks show that BorderPatrol has an average overhead of
- 5.37% for Disk-bound Workload
- 7.65% for Network-bound Workload
- 37.2% for File-bound Workload
- 307.7% for Exec-bound Workload
The author also do overhead evaluations on two test cases stated
above. The “dearinter.net” test case shows that the overhead of using
BorderPartrol is about 10-15%.


Reproducibility :
Although BorderPatrol is publicly available, the results are
irreproducible unless we can obtain the same workloads used in the
case studies and performance evaluations.


Criticism :
The authors should explain more in detail about the recovering request
path process.

On Nov 3, 10:10 pm, Rodrigo Fonseca <rodrigo.fons...@gmail.com> wrote:

[Dimitar]

BorderPatrol:Isolating Events for Black-box
Tracing

Authors: Eric Koskinen, John Jannotti

Date:04/1-4,/2008

Novel Idea: Recent work has shown that traces can be valuable input
for tools which look for faulty
modules, discover anomalous request path in distributed systems.
However , obtaining precise
request traces in a heterogeneous system can be extremely difficult.
BorderPatrol
is attempting to do that using various techniques with a light-weight
module isolation.

Main Results: Border Patrol is able to obtain precise traces with only
10-15% overhead.
It uses active observation to observe and subtly modify the event
streams sent and received by
modules. Protocol processor implements active observation without
implementation knowledge,
but only with protocol knowledge. The main purpose of the processors
is to identify message boundaries
and to track message witnesses.

Impact: BorderPatrol can be useful tool to gather traces for web
hosting companies.

Evidence: The authors supports their claims by setting several
experiments. The result of the
experiments show that BorderPatrol logs traces with minimum overhead.

Prior Work: They are several works that have similar goals such as
Magpie, Traceback and Pinpoint

Reproducibility: I think experiments are reproducible if we have the
source code , but I
think implementation is not reproducible because the paper leaves a
lot of details.

Criticism: The evaluation was rather lacking , it only demonstrated
that BorderPatrol has low
performance overhead. It did not demonstrate how effective their
approach is compare to similar
methods for collecting traces.

On Nov 3, 10:10 pm, Rodrigo Fonseca <rodrigo.fons...@gmail.com> wrote:

[Siddhartha Jain]

Siddhartha Jain

Title: BorderPatrol

Novel Idea:

Use of active observation by modifying the event stream to obtain a precise

request trace. Has protocol processes which use information about standard

protocols to get a better trace avoiding app-specific knowledge and instrumentation

Main Results:

Border patrol is described in detail and results are given using case studies to

demonstrate the effectiveness of border patrol and evaluation of the overhead of

the system.

Prior Work:

A lot of prior work using instrumentation and statistical approaches.

Reproducibility:

Open source!

Ideas for future work:

A better method of evaluation than just case studies.

On Wed, Nov 3, 2010 at 10:10 PM, Rodrigo Fonseca <rodrigo...@gmail.com> wrote:

[Duy Nguyen]

Title:

BorderPatrol: Isolating Events for Black-box Tracing

Authors:
Eric Koskinen,  John Jannotti

Date:

EuroSys 2008

Novel Idea:
Like Project5, this is a tracing framework that requires no modification
to the systems. But unlike Project5, to infer call path, Border Patrol uses
active observation in which some reasonable assumptions about system are
made (honest, immediate, independent), and library interposition techniques
are used.

Main Result(s):
With applications that comply to BorderPatrol assumptions like: Apache, Zeus,
PostgreSQL, it successfully reconstructs the causal path.

Impact:
Unknown, but to me, this work is more reasonable than Project 5 which relies
too much on heuristics and signal processing techniques which are difficult to
verify.

Evidence:
BorderPatrol is evaluated on live system (dearinter.net), its accuracy in
reconstructing tracing path and its affect on system performance are measured.
A test on closed source software (Zeus) is also performed.

Prior Work
Pip, Magpie, Project5, Traceback

Competitive work
Other pervasive tracing framework can be considered BorderPatrol's competitive
works are: PinPoint, Causeway, XTrace

Reproducibility
Yes

Question/Criticism:
It would be nice to see some tests on systems that don't obey to BorderPatrol's
assumptions.

On Wed, Nov 3, 2010 at 10:10 PM, Rodrigo Fonseca <rodrigo...@gmail.com> wrote:

[Shah]

Title:

BorderPatrol: Isolating Events for Black-Box Tracing

Authors:

[1] Eric Koskinen
[2] John Jannotti

Source and Date:

Eurosys '08 Proceedings of the 3rd ACM SIGOPS/EuroSys European
Conference on Computer Systems, 2008.

Novel Idea:

The authors state that BlackBox is unique in its ability to obtain
precise traces.

Main Result:

The authors present a system called BorderPatrol which has the ability
to provide precise traces. This aids in understanding the behavior of
black-box distributed systems.

Impact:

This paper doesn't seem to have had a significant impact as the number
of citations seems to be less than 15.

Evidence:

The researchers provide the performance of BorderPatrol by conducting
two case studies. The first one deals with multi-threaded tiers and
the second one focuses on an event-driven web server - specifically,
Zeus.

Prior Work:

The authors state that a lot of prior work has focused on specifics at
the loss of precision. These include either simplifying the
instrumentation burden or the use of statistical methods. They divide
prior work into four bins: Instrumentation, Pervasive Frameworks,
Probabilistic Correlation and Analysis from Causal Paths. For the
first category, they give the example of Magpie and TraceBack. For the
second, they mention PinPoint and Causeway, for the third Whodunit is
mentioned. Finally, Pip is deemed to be part of the last bin.

Competitive Work:

The researchers suggest that recent work such as Pinpoint, Pip and
Stardust are unable to trace complex systems. Hence, these may be
considered to be 'competitive'.

Reproducibility

The scientists provide a fair amount of detail to make the results
reproducible. They furnish adequate snippets of code as well as
describe in length their approach and methodology.

Question:

Why has this paper not gained more popularity (if that's a fair to
ask)? The idea seems novel.

Criticism:

None. However, on what kind of systems could this test be performed on
to gain useful data?

Ideas for Further Work:

None.

[James Chin]

Paper Title: “BorderPatrol: Isolating Events for Black-box Tracing”

Authors(s): Eric Koskinen, John Jannotti

Date: 2008 (EuroSys ‘08)

Novel Idea: This paper presents BorderPatrol, which obtains precise
request traces through systems built from a litany of unmodified
modules. BorderPatrol obtains traces using active observation, which
carefully modifies the event stream observed by modules, simplifying
precise observation. Specifically, BorderPatrol obtains precise

traces for black-box systems that cannot be traced by any other
technique.

Main Result(s): The authors confirmed the accuracy of BorderPatrol’s
traces by comparing it to manual instrumentation. Specifically, they
learned that traces can be obtained for unmodified programs without
sacrificing precision. They also compared the developer effort
required for each kind of trace. BorderPatrol imposes limited
overhead on real systems (approximately 10-15%) and it may be enabled
or disabled in at run-time, making it a viable option for deployment
in production environments.

Impact: Developers would benefit from tracing tools that follow single
requests as they are passed between modules, including third-party
binary modules, even as those requests are passed and returned from
remote, unmodified systems. In addition, recent work has shown that
request traces can be valuable input to automated tools.

Evidence: One evaluation consists of case studies and a performance
evaluation. The authors show that BorderPatrol reconstructs causal
paths through a range of diverse servers including Apache, thttpd,
Zeus, BIND, PostgreSQL, and TurboGears, without modifications to
server source code or the use of statistical methods. Furthermore,
the authors show that the overhead of tracing is about 10-15% and can
be activated at runtime, making it a viable technique for production
environments.

Prior Work: Previous work in request tracing has generally focused on
either simplifying the instrumentation burden, or the use of
statistical methods that eliminate instrumentation but also lose the
ability to trace precisely. Systems such as Pinpoint, Pip, and
Stardust analyze precise request traces to identify faulty modules,
discover anomalous request paths, and make capacity plans. However,
these systems rely on simple trace gathering techniques that are

unable to trace complex systems.

Competitive Work: Same as prior work.

Reproducibility: BorderPatrol is publicly available, so the findings
appear to be reproducible if one follows the testing procedures
outlined in this paper.

Question: Who, if any, is using BorderPatrol now?

Criticism: This paper did not really suggest any ideas for future
work.

Ideas for further work: Perform benchmark testing on a cluster of
servers instead of just a single one.

On Nov 3, 10:10 pm, Rodrigo Fonseca <rodrigo.fons...@gmail.com> wrote:

[Basil Crow]

Title: BorderPatrol: Isolating Events for Black-box Tracing

Authors: Eric Koskinen and John Jannotti

Date: EuroSys 2008

Novel idea: BorderPatrol is a system which obtains causal request traces without the need to modify the original application. BorderPatrol accomplishes this by observing and modifying the event streams sent and received by an application on the protocol level.

Main results: BorderPatrol is a set of tools which can be used to instrument an application which serves requests from clients. BorderPatrol's causal request traces add minimal overhead to the original application.

Impact: Black-box tracing is useful for rapid debugging of production applications, as illustrated by the Turbogears example in the paper.

Evidence: The authors present a compelling case study of debugging performance problems in a multithreaded web application written in Python. Analyzing the traces led to several performance improvements in the application, ranging from application configuration to database inefficiencies. The authors also ran a series of micro-benchmarks to determine the mean overhead of their tracing system (37.2%).

Prior Work: The design of this system reminds me of Sun's DTrace, which is a tool for debugging kernel and application issues in production without modifying the original application.

Reproducibility: Source code is available. One would simply need access to a busy web server to try it out.

[Matt Mallozzi]

Matt Mallozzi

11/4/10

Title:

BorderPatrol: Isolating Events for Black-box Tracing

Authors:

Koskinen, Jannotti

Date:

2008

Novel Idea:

Although black-box distributed systems modules may act in arbitrary ways,

especially when multiple requests are being handled simultaneously, real

applications behave with enough of a pattern that useful information about

causal paths between modules can be derived.

Main Results:

A black-box distributed system tracing tool based on library interposition

(like how Valgrind inserts its own tracing code for malloc/free).

Impact:

Like Project5 and NetMedic, BorderPatrol offers the possibility of making

debugging distributed systems much easier and much more familiar to

programmers of single-system, serial programs.

Evidence:

Case studies to show the effectiveness of BorderPatrol, as well as

performance evaluation to argue that the overhead involved isn't too

crippling.

Prior Work:

This tool builds upon the aims of previous systems such as Pinpoint, Pip,

and Stardust, but extends the aims further to better support black-boxes

and complex systems.

Competitive Work:

BorderPatrol differentiates itself from similar tools by being

application-agnostic, non-intrusive to application code (that is either

difficult or impossible to modify), and non-probabilistic in determining

input/output correlation.

Reproducibility:

Open source! The website even has detailed instructions on how to install

and use their software.

Question:

BorderPatrol claims to be application independent, but what about when a

company decides that common, possibly open standards are actually more like

guidelines (*cough*, Microsoft), and writes their own RPC protocol?

Criticism:

How many protocol processors need be implemented to cover the vast majority

of communications between various black-box modules? It seems like the

closer a system is to being a black box, the more likely it is to use a

communication protocol that is not common and not publicly specified.

Ideas for Further Work:

Detect which protocol is being used based on the data being seen. Or for a

completely separate project (but which would help patch up some of the

weaknesses of this system), automatically learn the message syntax for new

and unknown protocols.

On Wed, Nov 3, 2010 at 10:10 PM, Rodrigo Fonseca <rodrigo...@gmail.com> wrote:

[Sandy Ryza]

Aaah I just realized I never submitted my review for this. When I
went to submit it the first time it hadn't been posted and I forgot to
check back.

Title:
BorderPatrol: Isolating Events for Black-box Tracing

Authors:

Eric Koskinen, John Jannotti

Date:

EuroSys '08

Novel Idea:
The authors present BorderPatrol, a system for extracting causal paths
from distributed systems composed of communicating black boxes that
interposes itself between components to isolate requests and associate
them with other requests caused by them. While their system is
application-agnostic, it is not protocol-agnostic: it requires the use
of small protocol handlers to find the boundaries between messages in
the protocols that are used to pass messages between components.

Main Result(s):
The authors find that their system is able to correctly understand
message traces in the case studies they test it with. They find that
its impact on performance averages at about 10-15% latency overhead,
but is highly variable depending on the system they use it to monitor,
reaching 307% latency overhead on one of their benchmarks and 96%
latency overhead on a component in one of their case studies.

Evidence:
The authors undertook two case studies to evaluate their system's
correctness. They ran it on dearinter.net, a several-tiered web app
that communicates with HTTP, FastCGI, and PostgreSQL, and confirmed
their results with the developers and with manual instrumentations.
They also used it to monitor an enterprise-scale commercial event
driven web server, Zeus. They evaluated their system's impact on
latency with a series of micro-benchmarks and with the same case
studies.

Prior Work & Competitive Work:
Statistical approaches, such as in NetMedic and Project5, that attempt
to find the most used paths in a system. Pinpoint, Pip, and Stardust,
systems that also obtain precise traces, but these systems use simple
techniques that are not applicable to complex distributed systems.
Manual instrumentation approaches modify applications to log data to
associate outputs with inputs.

Reproducibility:
The system (and I think the code) is freely available. The
dearinter.net case study would not be reproducible would collaboration
with dearinter.net like the authors undertook, and the Zeus case study
was only described in moderate detail.

Criticism:
While they discuss one situation in a test-case in which their system
helped to discover an inefficiency, the authors devote little space to
what types of problems BorderPatrol is meant to/is good at solving.

Question:
I didn't exactly understand what they mean when they say their method
can detect forks, but not joins. Can we go over this?

On Nov 3, 10:10 pm, Rodrigo Fonseca <rodrigo.fons...@gmail.com> wrote: