Google Summer of Code wrap-up: Linux XIA

It’s Friday! Time for another Google Summer of Code wrap-up post. Boston University / XIA is one of the 37 new organizations to the program this year. Read below about three student projects and their work to discover the future architecture of the internet.

Linux XIA is the native implementation of eXpressive Internet Architecture (XIA), a meta network architecture that supports evolution of all of its components, which we call “principals,” and promotes interoperability between these principals. We are developing Linux XIA because we believe that the most effective way to find the future Internet architecture that will eventually replace TCP/IP is to crowdsource the search. This crowdsourced search is possible in Linux XIA.

Our organization, Boston University / XIA, received 34 proposals from 12 countries. As a first-year organization in Google Summer of Code (GSoC), we were surprised by the number of proposals, and we did our best to choose great students for each of the following projects:

Extending XLXC to support arbitrary network topologies

XLXC is a set of scripts written in Ruby that creates network topologies using virtual interfaces and Linux containers. While testing a new network stack, a good amount of work goes into creating testing environments. XLXC saves developers and tinkerers a lot of time while experimenting with Linux XIA. Our student Aryaman Gupta from India worked with mentor Rahul Kumar to enable XLXC to emulate any topology using a language to describe the topologies.

Implementing perfect hashing for mapping XID types to loaded principals

Linux XIA needs to call forwarding functions that correspond to each XID type in order to forward a packet. XID types are 32-bit identifiers associated with principals which, in turn, define the forwarding functions. Being able to hash each XID type to a unique entry in an array increases the number of packets Linux XIA can forward per second because it reduces the number of memory accesses per lookup. Our student Pranav Goswami, also from India, worked with mentor Qiaobin Fu to find the best perfect hashing algorithm for Linux XIA to use in this case, and implemented it in Linux XIA.

Implementing the LPM principal

We do not know how the future Internet will route packets between autonomous systems (ASes), but we are certain that Linux XIA can leverage IP's routing tables to have large deployments of Linux XIA. This is the goal of the LPM principal: leveraging routing tables derived from BGP, OSPF, IS-IS and any other IP routing protocol to forward XIA packets natively, that is, without encapsulation in IP. Thanks to the evolution mechanism built into Linux XIA, when a better way to route between ASes becomes available, we will be able to incrementally phase LPM out. Student André Ferreira Eleuterio from Brazil implemented the LPM principal in Linux XIA with the help of mentor Cody Doucette.

We are going to work with our students during the fall to have their contributions merged into our repositories and to add new projects to our ideas list that build upon their contributions. We expect that this will motivate new contributors by showing how much impact they can have on Linux XIA. Finally, new collaborators do not need to wait for the next GSoC to get involved! Join our community today, and "do what you can, with what you have, where you are" to make a difference like our three students successfully did.

By Michel Machado, Organization Administrator for Boston University / XIA

Introducing CCTZ: a simple time zone library for C++

"Time zones are logical and easy to use."

—no one ever

Programming with time zones is notoriously difficult and error prone. Sure, this is partially because time zones have some inherent complexity. But perhaps the bigger problem is that programmers don't have a clear conceptual model of how time and time zones work. Additionally, library support may not be what it should. The end result is that code dealing with time zones is often overly complicated and sometimes even wrong.

A couple years ago we set out to fix these time zone programming woes within Google. We did this first by defining a greatly simplified mental model that enables programmers to understand time concepts and correctly reason about their code. We also created a C++ Time Zone library that closely matches this mental model and allows programmers to handle even the most complicated issues in a general and clear way.

And since we don't believe that time zone programming problems are unique to Google, we think our solutions may be useful to others. We presented these ideas and announced the open sourced cctz library this week at CppCon 2015. Even if you don't use C++, we hope you'll take a moment to read about the simplified mental model and perhaps flip through the slides from our talk, because those ideas are language independent.

by Greg Miller and Bradley White, Google Engineering

Introducing Brotli: a new compression algorithm for the internet

At Google, we think that internet users’ time is valuable, and that they shouldn’t have to wait long for a web page to load. Because fast is better than slow, two years ago we published the Zopfli compression algorithm. This received such positive feedback in the industry that it has been integrated into many compression solutions, ranging from PNG optimizers to preprocessing web content. Based on its use and other modern compression needs, such as web font compression, today we are excited to announce that we have developed and open sourced a new algorithm, the Brotli compression algorithm.

While Zopfli is Deflate-compatible, Brotli is a whole new data format. This new format allows us to get 20–26% higher compression ratios over Zopfli. In our study ‘Comparison of Brotli, Deflate, Zopfli, LZMA, LZHAM and Bzip2 Compression Algorithms’ we show that Brotli is roughly as fast as zlib’s Deflate implementation. At the same time, it compresses slightly more densely than LZMA and bzip2 on the Canterbury corpus. The higher data density is achieved by a 2nd order context modeling, re-use of entropy codes, larger memory window of past data and joint distribution codes. Just like Zopfli, the new algorithm is named after Swiss bakery products. Brötli means ‘small bread’ in Swiss German.

The smaller compressed size allows for better space utilization and faster page loads. We hope that this format will be supported by major browsers in the near future, as the smaller compressed size would give additional benefits to mobile users, such as lower data transfer fees and reduced battery use.

By Zoltan Szabadka, Software Engineer, Compression Team

Google Summer of Code wrap-up post: Pencil Code

Pencil Code is a collaborative programming site for art, music and creating games. It is also a place to experiment with mathematical functions, geometry, graphing, webpages, simulations and algorithms. Pencil Code had three Google Summer of Code students in 2015. You can read more about their project successes below.

As we return to school and look around Pencil Code in preparation for classes this fall, there are quite a few improvements created by our Google Summer of Code (GSoC) students. The first thing you see when you log in — icons everywhere! But better yet, if you have saved the program recently, the icon will be a screenshot of the program's output. This change will help students and teachers quickly identify saved projects, and will help people find interesting projects they want to share.

The icon implementation was done by Xinan Liu, a student at Singapore National University. He rewrote several bits of the Pencil Code server to support the icons, and then on the client side, he integrated the very cool html2canvas library to create the screenshots.

Xinan also contributed quite a bit beyond this project. He refactored our node.js-based build to switch from require.js to browserify, and he has been contributing to other sharing and scaling features on Pencil Code, helping other non-GSoC contributors get up to speed and reviewing their pull requests. We're looking forward to Xinan's continuing involvement and contributions to our little open source community.

The next contribution was by IIIT Hyderabad student Saksham Aggarwal. Saksham has implemented an HTML block mode for the Droplet block editor, which means that teachers can introduce beginners to HTML syntax using a drag-and-drop interface. And as usual with Droplet, you can toggle between blocks and text at any time. Saksham is also working on a similar Droplet-based editor for CSS syntax. The visual HTML syntax editor is a very accessible way to see and work with HTML syntax without having to type every bracket. And yet, magically, it does not hide the syntax - by toggling into text, you can work directly with traditional code. It is fully authentic, but highly accessible. You can read a paper about Saksham's work here.

The final project was a collaboration between GSoC student Jeremy Ruten from the University of Saskatchewan, and two of our summer students Amanda Boss from Harvard and Cali Stenson from Wellesley. They created an incredibly ambitious project to implement a "rewindable" debugger in Pencil Code. Although it is not quite ready for production yet, we are already using pieces of it in Pencil Code. You will see the debugger in coming months! For examples of how it transforms code, you can check out Jeremy, Amanda and Cali's writeup of their debugging work.

Did I mention that the three of them are students? And that they built this rewindable debugger over just one summer!? They made improvements that will make a real difference as we use Pencil Code to bring computer science to the next generation of students.

We'd like you to participate!

If you are interested in bringing some of this cool work into your classroom, join our discussion group by signing up at teach.pencilcode.net. We have teachers from elementary school to college, from Texas to Singapore. And if you'd like to make an open source contribution, check out ideas.pencilcode.net for project ideas, and join the teaching discussion group — also an area where our open source contributors hang out.

We are grateful to Google for supporting our summer open source program with GSoC. We hope the summer was as interesting for our students as it was productive for our project. We look forward to our students' continued involvement in the Pencil Code community.

By David Bau, Organization Administrator for Pencil Code

Google Summer of Code wrap-up post: Institute for Artificial Intelligence

Now that the 11th year of Google Summer of Code has officially come to a close, we will devote Fridays to wrap-up posts from a handful of the 137 mentoring organizations that participated in 2015. Organizations this year represented a wide range of computing fields including artificial intelligence, featured below.

Two software libraries that originate from our laboratory, the Institute for Artificial Intelligence, that are used and supported by a larger user community are the KnowRob system for robot knowledge processing and the CRAM (Cognitive Robot Abstract Machine) framework for plan-based robot control. In our group, we have a very strong focus on open source software and active maintenance and integration of projects. The systems we develop are available under BSD and MIT licenses, and partly (L)GPL.

Within the context of these frameworks, we offered four projects during the summer term in 2015, which were all accepted to Google Summer of Code (GSoC).

Multi-modal Big Data Analysis for Robotic Everyday Manipulation Activities

The project "Multi-modal Big Data Analysis for Robotic Everyday Manipulation Activities" added to our ongoing work to build the robotic perception system RoboSherlock for service robots performing household chores. Our GSoC student, Alexander, made exciting progress and valuable contributions during the summer. He ported an earlier prototypical proprioceptive module from Java to C++ to integrate it into RoboSherlock, he developed tools for visualizing the module's various detections and annotations, and applied this infrastructure to detect collisions of the robot's arms with unperceived parts of the environment in a shelf reordering task. We are also very happy that Alexander decided to stay and keep on working on RoboSherlock after GSoC ended.

Kitchen Activity Games GUI

Our GSoC student, Mesut, developed a GUI to interact with the robotics simulator Gazebo. The simulator has been used as a library, allowing different scenarios (worlds) to be selected and executed. Playlists can be generated in order to replay logged episodes. During the replay, various plugins can be linked and executed from the GUI to allow post processing the data. The user interface will ease organizing and saving simulation data further used for learning. You can view Mesut’s project on GitHub here.

Symbolic Reasoning Tools with Bullet using CRAM

Autonomous robots performing complex manipulation tasks in household environments, such as preparing a meal or tidying up, are required to know where different objects are located and what properties they have. The knowledge about their environment is called “belief state”, i.e. the information that the robot believes holds true in the surrounding world. Our GSoC student, Kunal, worked on improving the world representation of the CRAM robotic framework, which represents the environment as a 3-dimensional world where simple physics rules of the Bullet Physics engine apply. The goal of the project was to issue events when errors are found in the belief state, such as, if the robot thinks its arm is inside of a table, which is physically impossible. A stand-alone ROS (Robot Operating System) publisher node, that would notify all its listeners about errors, was partially implemented while integration with the CRAM belief state is still in progress.

Report Card Generation from Robot Mobile Manipulation Activities

Throughout the summer, our GSoC student Kacper made great progress in developing a framework for automatically generating report cards from robot experiences. We have a special focus in mobile manipulation activities in robots and are interested in anomaly detection in our rather complex systems — the developed components greatly help us save time on mundane analysis tasks, and make complicated analysis steps (looking up all aspects of a certain action, comparing different trials) easier to do.

By Jan Winkler, Organization Administrator and PhD student at the Institute of Artificial Intelligence

Building a Build System: Bazel reaches Beta

We're excited to announce the Beta release of Bazel, an open source build system designed to support a wide variety of different programming languages and platforms.

There are lots of other build systems out there -- Maven, Gradle, Ant, Make, and CMake just to name a few. So what’s special about Bazel? Bazel is what we use to build the large majority of software within Google. As such, it has been designed to handle build problems specific to Google’s development environment, including a massive, shared code repository in which all software is built from source, a heavy emphasis on automated testing and release processes, and language and platform diversity. Bazel isn’t right for every use case, but we believe that we’re not the only ones facing these kinds of problems and we want to contribute what we’ve learned so far to the larger developer community.

Our Beta release provides:

• Binary releases for Linux and OS X.
• Support for building and testing C++, Java, Python, Rust, and more.
• Support for building Docker images, Android apps, and iOS apps.
• Support for using libraries from Maven, GitHub, and more.
• A robust API for adding your own build rules.

Check out the tutorial app to see a working example using several languages.

We still have a long way to go.  Looking ahead towards our 1.0.0 release, we plan to provide Windows support, distributed caching, and Go support among other features. See our roadmap for more details and follow our blog or Twitter account for regular updates.  Feel free to contact us with questions or feedback on the mailing list or IRC (#bazel on freenode).

By Jeff Cox, Bazel team