bluuebunny/crossref_metadata_2025_split huggingface dataset:
On compact routing for the internet
Authors: Krioukov Dmitri , claffy k c , Fall Kevin , Brady Arthur 
Published: September 2007

The Internet's routing system is facing stresses due to its poor fundamental scaling properties. Compact routing is a research field that studies fundamental limits of routing scalability and designs algorithms that try to meet these limits. In particular, compact routing research shows that shortest-path routing, forming a core of traditional routing algorithms, cannot guarantee routing table (RT) sizes that on all network topologies grow slower than linearly as functions of the network size. However, there are plenty of compact routing schemes that relax the shortest-path requirement and allow for improved, sublinear RT size scaling that is mathematically provable for all static network topologies. In particular, there exist compact routing schemes designed for grids, trees, and Internet-like topologies that offer RT sizes that scale logarithmically with the network size.
In this paper, we demonstrate that in view of recent results in compact routing research, such logarithmic scaling on Internet-like topologies is fundamentally impossible in the presence of topology dynamics or topology-independent (flat) addressing. We use analytic arguments to show that the number of routing control messages per topology change cannot scale better than linearly on Internet-like topologies. We also employ simulations to confirm that logarithmic RT size scaling gets broken by topology-independent addressing, a cornerstone of popular locator-identifier split proposals aiming at improving routing scaling in the presence of network topology dynamics or host mobility. These pessimistic findings lead us to the conclusion that a fundamental re-examination of assumptions behind routing models and abstractions is needed in order to find a routing architecture that would be able to scale "indefinitely.
You must be joking
Authors: Faloutsos Michalis , Banerjee Anirban , Rejaie Reza 
Published: September 2007

We did it! A few CCR issues back, this column argued in favor of an all open review. At the time, most people thought that it was a joke. Quite frankly, we meant it as a joke. It is a crazy world we live in. No, seriously, it was not so much of a joke, as a wild attempt to think outside the box. Or else, desperate times call for desperate measures. Something like that. Apparently, we were so desperate that we actually tried it. And it worked. Beautifully. But then again, we may be biased.
"To say it was easy would be a lie." R. Rejaie and M. Faloutsos, early 21st century.
Future internet research and experimentation
Authors: Gavras Anastasius , Karila Arto , Fdida Serge , May Martin , Potts Martin 
Published: September 2007

The research community worldwide has increasingly drawn its attention to the weaknesses of the current Internet. Many proposals are addressing the perceived problems, ranging from new enhanced protocols to fix specific problems up to the most radical proposal to redesign and deploy a fully new Internet. Most of the problems in the current Internet are rooted in the tremendous pace of increase of its use. As a consequence there was little time to address the deficiencies of the Internet from an architectural point of view.
Within FP7, the European Commission has facilitated the creation of European expert groups around the theme FIRE "Future Internet Research and Experimentation". FIRE has two related dimensions: on one hand, promoting experimentally-driven long-term, visionary research on new paradigms and networking concepts and architectures for the future Internet; on the other hand, building a large-scale experimentation facility supporting both medium- and long-term research on networks and services by gradually federating existing and new testbeds for emerging or future Internet technologies. By addressing future challenges for the Internet such as mobility, scalability, security and privacy, this new experimentally-driven approach is challenging the mainstream perceptions for future Internet development. This new initiative is intended to complement the more industrially-driven approaches which are addressed under the FP7 Objective "The Network of the Future" within the FP7-ICT Workprogramme 2007-08. FIRE is focused on exploring new and radically better technological solutions for the future Internet, while preserving the "good" aspects of the current Internet, in terms of openness, freedom of expression and ubiquitous access. The FIRE activities are being launched in the 2nd ICT call, which closes in October 2007, under the FP7-ICT Objective 1.6 "New Paradigms and Experimental Facilities" (budget ε40m). Projects are envisaged to start in early 2008.
A new foundation for control dependence and slicing for modern program structures
Authors: Ranganath Venkatesh Prasad , Amtoft Torben , Banerjee Anindya , Hatcliff John , Dwyer Matthew B. 
Published: September 2007

The notion of control dependence underlies many program analysis and transformation techniques. Despite being widely used, existing definitions and approaches to calculating control dependence are difficult to apply directly to modern program structures because these make substantial use of exception processing and increasingly support reactive systems designed to run indefinitely.
This article revisits foundational issues surrounding control dependence, and develops definitions and algorithms for computing several variations of control dependence that can be directly applied to modern program structures. To provide a foundation for slicing reactive systems, the article proposes a notion of slicing correctness based on weak bisimulation, and proves that some of these new definitions of control dependence generate slices that conform to this notion of correctness. This new framework of control dependence definitions, with corresponding correctness results, is even able to support programs with irreducible control flow graphs. Finally, a variety of properties show that the new definitions conservatively extend classic definitions. These new definitions and algorithms form the basis of the Indus Java slicer, a publicly available program slicer that has been implemented for full Java.
Dynamic 2D patterns for shading 3D scenes
Authors: Breslav Simon , Szerszen Karol , Markosian Lee , Barla Pascal , Thollot Joëlle 
Published: September 2007

We describe a new way to render 3D scenes in a variety of non-photorealistic styles, based on patterns whose structure and motion are defined in 2D. In doing so, we sacrifice the ability of patterns that wrap onto 3D surfaces to convey shape through their structure and motion. In return, we gain several advantages, chiefly that 2D patterns are more visually abstract - a quality often sought by artists, which explains their widespread use in hand-drawn images.
Extending such styles to 3D graphics presents a challenge: how should a 2D pattern move? Our solution is to transform it each frame by a 2D similarity transform that closely follows the underlying 3D shape. The resulting motion is often surprisingly effective, and has a striking cartoon quality that matches the visual style.
Dynamic planar map illustration
Authors: Asente Paul , Schuster Mike , Pettit Teri 
Published: September 2007

There are many types of illustrations that are easier to create in planar-map-based illustration systems than in the more common stacking-based systems. One weakness shared by all existing planar-map-based systems is that the editability of the drawing is severely hampered once coloring has begun. The paths that define the areas to be filled become divided wherever they intersect, making it difficult or impossible to edit them as a whole.
Live Paint is a new metaphor that allows planar-map-based coloring while maintaining all the original paths unchanged. When a user makes a change, the regions and edges defined by the new paths take on fill and stroke attributes from the previous regions and edges. This results in greater editing flexibility and ease of use. Live Paint uses a set of heuristics to match each region and edge in a changed illustration with a region or edge in the previous version, a task that is more difficult than it at first appears. It then transfers fill and stroke attributes accordingly.
Prakash
Authors: Raskar Ramesh , Nii Hideaki , deDecker Bert , Hashimoto Yuki , Summet Jay , Moore Dylan , Zhao Yong , Westhues Jonathan , Dietz Paul , Barnwell John , Nayar Shree , Inami Masahiko , Bekaert Philippe , Noland Michael , Branzoi Vlad , Bruns Erich 
Published: September 2007

In this paper, we present a high speed optical motion capture method that can measure three dimensional motion, orientation, and incident illumination at tagged points in a scene. We use tracking tags that work in natural lighting conditions and can be imperceptibly embedded in attire or other objects. Our system supports an unlimited number of tags in a scene, with each tag uniquely identified to eliminate marker reacquisition issues. Our tags also provide incident illumination data which can be used to match scene lighting when inserting synthetic elements. The technique is therefore ideal for on-set motion capture or real-time broadcasting of virtual sets.
Unlike previous methods that employ high speed cameras or scanning lasers, we capture the scene appearance using the simplest possible optical devices - a light-emitting diode (LED) with a passive binary mask used as the transmitter and a photosensor used as the receiver. We strategically place a set of optical transmitters to spatio-temporally encode the volume of interest. Photosensors attached to scene points demultiplex the coded optical signals from multiple transmitters, allowing us to compute not only receiver location and orientation but also their incident illumination and the reflectance of the surfaces to which the photosensors are attached. We use our untethered tag system, called Prakash, to demonstrate methods of adding special effects to captured videos that cannot be accomplished using pure vision techniques that rely on camera images.
Ldr2Hdr
Authors: Rempel Allan G. , Trentacoste Matthew , Seetzen Helge , Young H. David , Heidrich Wolfgang , Whitehead Lorne , Ward Greg 
Published: September 2007

New generations of display devices promise to provide significantly improved dynamic range over conventional display technology. In the long run, evolving camera technology and file formats will provide high fidelity content for these display devices. In the near term, however, the vast majority of images and video will only be available in low dynamic range formats.
In this paper we describe a method for boosting the dynamic range of legacy video and photographs for viewing on high dynamic range displays. Our emphasis is on real-time processing of video streams, such as web streams or the signal from a DVD player. We place particular emphasis on robustness of the method, and its ability to deal with a wide range of content without user adjusted parameters or visible artifacts. The method can be implemented on both graphics hardware and on signal processors that are directly integrated in the HDR displays.
Robust on-line computation of Reeb graphs
Authors: Pascucci Valerio , Scorzelli Giorgio , Bremer Peer-Timo , Mascarenhas Ajith 
Published: September 2007

Reeb graphs are a fundamental data structure for understanding and representing the topology of shapes. They are used in computer graphics, solid modeling, and visualization for applications ranging from the computation of similarities and finding defects in complex models to the automatic selection of visualization parameters.

We introduce an
on-line
algorithm that reads a stream of elements (vertices, triangles, tetrahedra, etc.) and continuously maintains the Reeb graph of all elements already reed. The algorithm is
robust
in handling non-manifold meshes and
general
in its applicability to input models of any dimension.

Optionally, we construct a skeleton-like embedding of the Reeb graph, and/or remove topological noise to reduce the output size.
For interactive multi-resolution navigation we also build a hierarchical data structure which allows real-time extraction of approximated Reeb graphs containing all topological features above a given error threshold.
Our extensive experiments show both high performance and practical linear scalability for meshes ranging from thousands to hundreds of millions of triangles. We apply our algorithm to the largest, most general, triangulated surfaces available to us, including 3D, 4D and 5D simplicial meshes. To demonstrate one important application we use Reeb graphs to find and highlight topological defects in meshes, including some widely believed to be "clean."
Dappled photography
Authors: Veeraraghavan Ashok , Raskar Ramesh , Agrawal Amit , Mohan Ankit , Tumblin Jack 
Published: September 2007

We describe a theoretical framework for reversibly modulating 4D light fields using an attenuating mask in the optical path of a lens based camera. Based on this framework, we present a novel design to reconstruct the 4D light field from a 2D camera image without any additional refractive elements as required by previous light field cameras. The patterned mask attenuates light rays inside the camera instead of bending them, and the attenuation recoverably encodes the rays on the 2D sensor. Our mask-equipped camera focuses just as a traditional camera to capture conventional 2D photos at full sensor resolution, but the raw pixel values also hold a modulated 4D light field. The light field can be recovered by rearranging the tiles of the 2D Fourier transform of sensor values into 4D planes, and computing the inverse Fourier transform. In addition, one can also recover the full resolution image information for the in-focus parts of the scene.
We also show how a broadband mask placed at the lens enables us to compute refocused images at full sensor resolution for layered Lambertian scenes. This partial encoding of 4D ray-space data enables editing of image contents by depth, yet does not require computational recovery of the complete 4D light field.
Image and depth from a conventional camera with a coded aperture
Authors: Levin Anat , Fergus Rob , Durand Frédo , Freeman William T. 
Published: September 2007

A conventional camera captures blurred versions of scene information away from the plane of focus. Camera systems have been proposed that allow for recording all-focus images, or for extracting depth, but to record both simultaneously has required more extensive hardware and reduced spatial resolution. We propose a simple modification to a conventional camera that allows for the simultaneous recovery of both (a) high resolution image information and (b) depth information adequate for semi-automatic extraction of a layered depth representation of the image.Our modification is to insert a patterned occluder within the aperture of the camera lens, creating a coded aperture. We introduce a criterion for depth discriminability which we use to design the preferred aperture pattern. Using a statistical model of images, we can recover both depth information and an all-focus image from single photographs taken with the modified camera. A layered depth map is then extracted, requiring user-drawn strokes to clarify layer assignments in some cases. The resulting sharp image and layered depth map can be combined for various photographic applications, including automatic scene segmentation, post-exposure refocusing, or re-rendering of the scene from an alternate viewpoint.
Joint bilateral upsampling
Authors: Kopf Johannes , Cohen Michael F. , Lischinski Dani , Uyttendaele Matt 
Published: September 2007

Image analysis and enhancement tasks such as tone mapping, colorization, stereo depth, and photomontage, often require computing a solution (e.g., for exposure, chromaticity, disparity, labels) over the pixel grid. Computational and memory costs often require that a smaller solution be run over a downsampled image. Although general purpose upsampling methods can be used to interpolate the low resolution solution to the full resolution, these methods generally assume a smoothness prior for the interpolation.
We demonstrate that in cases, such as those above, the available high resolution input image may be leveraged as a prior in the context of a joint bilateral upsampling procedure to produce a better high resolution solution. We show results for each of the applications above and compare them to traditional upsampling methods.
Probabilistic abstraction for model checking
Authors: Laplante Sophie , Lassaigne Richard , Magniez Frédéric , Peyronnet Sylvain , de Rougemont Michel 
Published: September 2007

The goal of model checking is to verify the correctness of a given program, on all its inputs. The main obstacle, in many cases, is the intractably large size of the program's transition system. Property testing is a randomized method to verify whether some fixed property holds on individual inputs, by looking at a small random part of that input. We join the strengths of both approaches by introducing a new notion of probabilistic abstraction, and by extending the framework of model checking to include the use of these abstractions.
Our abstractions map transition systems associated with large graphs to small transition systems associated with small random subgraphs. This reduces the original transition system to a family of small, even constant-size, transition systems. We prove that with high probability, “sufficiently” incorrect programs will be rejected (ε-robustness). We also prove that under a certain condition (exactness), correct programs will never be rejected (soundness).

Our work applies to programs for graph properties such as bipartiteness,
k
-colorability, or any ∃∀ first order graph properties. Our main contribution is to show how to apply the ideas of property testing to syntactic programs for such properties. We give a concrete example of an abstraction for a program for bipartiteness. Finally, we show that the relaxation of the test alone does not yield transition systems small enough to use the standard model checking method. More specifically, we prove, using methods from communication complexity, that the OBDD size remains exponential for approximate bipartiteness.
Introduction
Authors: Hohmuth Michael 
Published: September 2007

Since the early microkernel hype of the 1980s and some spectacular failures in the 1990s, the field of small-kernelbased systems has enjoyed renewed interest mostly because of contemporary challenges for computer security: Modern hypervisors and microkernels allow removing buggy and untrusted standard operating systems from a system's trusted computing base. At the same time, these kernels are small enough to make them (and indeed all of a system's trusted software) attainable for security auditing, formal methods, and even formal verification.
In this Special Topic Issue of Operating Systems Review, we explore this field in many dimensions: In addition to current research, we present both retrospective and forward-looking work; we look at both overall system structure as well as the mechanics of building small-kernel-based systems; and we present work from both the hypervisor and the microkernel factions of the small-kernel community.
A critique of the GNU hurd multi-server operating system
Authors: Walfield Neal H. , Brinkmann Marcus 
Published: September 2007

The GNU Hurd's design was motivated by a desire to rectify a number of observed shortcomings in Unix. Foremost among these is that many policies that limit users exist simply as remnants of the design of the system's mechanisms and their implementation. To increase extensibility and integration, the Hurd adopts an object-based architecture and defines interfaces, in particular those for the composition of and access to name spaces, that are virtualizable.
This paper is first a presentation of the Hurd's design goals and a characterization of its architecture primarily as it represents a departure from Unix's. We then critique the architecture and assess it in terms of the user environment of today focusing on security. Then follows an evaluation of Mach, the microkernel on which the Hurd is built, emphasizing the design constraints which Mach imposes as well as a number of deficiencies its design presents for multi-server like systems. Finally, we reflect on the properties such a system appears to require.
Towards effective user-controlled scheduling for microkernel-based systems
Authors: Stoess Jan 
Published: September 2007

With μ-kernel based systems becoming more and more prevalent, the demand for extensible resource management raises - and with it the demand for flexible thread scheduling. In this paper, we investigate the benefits and costs of a μ-kernel that exports scheduling from the kernel to user level. A key idea of our approach is to involve the user level whenever the μ-kernel encounters a situation that is ambiguous with respect to scheduling, and to permit the kernel to resolve the ambiguity based on user decisions. A further key aspect is that we rely on a generic, protection domain neutral interface between kernel and applications.
For evaluation, we have developed a hierarchical user level scheduling architecture for the L4 μ-kernel, and a virtualization environment running on its top. Our environment supports Linux 2.6.9 guest operating systems on IA-32 processors. Experiments indicate an application overhead between 0 and 10 percent compared to a pure in-kernel scheduler solution, but also demonstrate that our architecture enables effective and accurate user-directed scheduling.
Design and automation
Authors: Radke C. E. 
Published: September 2007

At the recent ACM 70 Conference, Bob Hitchcock chaired the SIGDA meeting. There were four of us in attendance: Bob (IBM), John Hanne (Texas Instruments), Murray Freeman (Philco), and myself (IBM). Later we caught a passer-by, Bob Brover (UCLA student). Although Bob was not acquainted with SIGDA or its purposes, at our insistence he did come up with a definition of Design Automation (DA). His on-the-spot definition was:
DESIGN -- An iterative, decision-making process that seeks to optimize the value of society's resources.
AUTOMATION -- Selecting of procedures for doing work with less effort.
Computer-aided preliminary layout of customized MOS arrays
Authors: Larsen R. P. 
Published: September 2007

One of the most perplexing problems confronting device designers utilizing MOS technology is the development of an effective layout design methodology. This paper describes a versatile layout design scheme for customized digital-type MOS arrays utilizing four-phase clocking schemes (ratioless logic). The analytical characterization of this layout design scheme is defined through the introduction of p-order and m-order indices. The p-order indices are assigned to members of the Boolean equation set that define the relative placement of their mechanization areas (p-diffusion structures) on the MOS array. The m-order indices are assigned to members of the term set that define their relative placements within parallel metalization channels on the MOS array. The underlying variables influencing the algorithmic derivation of quasi-optimal p-order and m-order assignments are also discussed.
This preliminary layout design methodology is then related to the computer-aided design environment. Two computer programs, named P-ORDER and M-ORDER, that comprise the computer-aided design environment are briefly described. A simple example is also presented to illustrate the complementary relationships that exist between the device designer and computer within the computer-aided design environment. Computer inputs and outputs for this simple problem are presented to stress the minimal input requirements and the pictorial characterizations of computer-synthesized solutions, which are essential ingredients to cost effective computer-aided design applications.