Thursday, February 16, 2017

Better Never Than Late

These days it's difficult to impossible to work on a mobile device of any kind that doesn't have a Global Positioning System (GPS) function integrated into it. But although I've worked as a product developer on many such devices over the years, I've never actually had the excuse to dig into the details of GPS, what information it provides, its format, and how you interpret it.

Since I'm a hands-on learner, there was only one thing to do. Along the way I was delighted to come up with a simple, real-life example of why sometimes losing data is a good thing. But it will take some time to get to that lesson.

The Road Test

From just parts I had on hand, I threw together a little portable battery-powered remote unit that reads data from a GPS receiver and transmits it to a base station in my office. The base station feeds the data to the Google Earth application. The Google Earth app produces a moving map display showing the path of the portable unit. All this occurs in real-time, the map updating on the display in my office as I drive around the neighborhood with the remote unit.

This is a nine minute screen recording of the moving map display, plus the terminal window of the base station as my software parses the GPS data and displays the results. The report includes position, altitude, heading, speed, and information about all of the satellites in the GPS constellation that the receiver can see. The Google Earth app and the terminal window are all running on the desktop Mac sitting in my office. The bad news is this may be the most boring video ever. The good news is you can use the YouTube player controls to fast forward through the portions of the drive where I was stopped at traffic lights.

The Hardware

All of this was surprisingly easy to do.

Hazer Testbed

Here is a high altitude view of my test setup. The GPS device feeds data over a serial connection to the remote unit "Tin", which passes it via User Datagram Protocol (UDP) over the Long Term Evolution (LTE) modem to the IPv6 internet. The GPS data ends up on my IPv6 test network (the same one I wrote about in Buried Treasure) where it feeds into the base station "Lead". Because Google Earth expects to receive data over a serial port from an actual GPS device, that's exactly how the base station feeds it, using a USB-to-serial convertor, to my Mac desktop running the Google Earth application. Google Earth thinks it's talking directly to a GPS device; it is unaware that Tin and Lead (and a pile of other network gateways) are acting as proxies between the GPS device and Google Earth.

Hazer sender "tin"

This is the remote unit, Tin. It consists of
USGlobalSat BU-353S4

The USGlobalSat BU-353S4 GPS receiver is a remarkably small, inexpensive, and easy to use device. It enumerates as a serial interface, e.g. /dev/ttyUSB0, from which you read ASCII data. Although my application was written in C, you could probably use almost any language, like Python. If you want to experiment with GPS, the BU-353S4, which is based on the SiRF Star IV chipset, makes it easy. However, there are several equally capable USB-based GPS devices on the market (some of which use the ublox 7 chipset) and I tested my software with several of them.

2016 Subaru WRX Limited

Perhaps the most important component of this project was the automobile I used to drive the remote unit around the neighborhood: a 2016 Subaru WRX Limited with a two liter turbocharged engine and all wheel drive. A little overkill for this project, but it's important to have good tools. (Mrs. Overclock refers to the WRX as The Batmobile.)

Road Testing

This is my test fixture inside the WRX. You can see my Mac laptop and the remote unit on the passenger seat, and the GPS receiver up on the dashboard by the windshield.

Hazer receiver "lead"

This is the base station, Lead, another Raspberry Pi 3, in my office that receives the GPS data from the remote unit over the IPv6 internet and feeds it via a serial cable to Google Earth running on my Mac desktop.
There are commercial devices that do this kind of thing. They are typically much simpler, cheaper, and lower power: a micro controller, a GPS chipset and a patch antenna, a 3G or even 2G cellular radio, and data is transmitted using Short Message Service (SMS) text messaging. But I threw this together with parts I already had on hand.
The Technology

The Global Positioning System is a Global Navigation Satellite System (GNSS) owned by the U. S. Government and operated by the U. S. Air Force. It is not the only GNSS; Russia (GLONASS), China (BeiDou-2), Europe (Galileo) have equivalent systems. GPS is a constellation of a couple of dozen satellites plus spares distributed in six different orbital planes. The first GPS satellite was launched in 1973.

Surprisingly, GPS satellites actually know nothing about position. What they know about is time. Each satellite broadcasts its unique identification number plus a time stamp. Every GPS receiver has embedded in it a detailed and precise map of the orbit of every GPS satellite. When the receiver sees the ID and time stamp from the satellite, it knows the expected position of the satellite, and can compute the propagation delay of the message by the time difference, based on the speed of light and taking relativity into account. The receiver can then calculate the distance it is from the satellite. Now the receiver knows it lies somewhere on a sphere whose radius is that distance. The receiver makes this same calculation based on several satellites, and it can then compute its position based on the intersection of all those spheres.
This isn't as complex as it may seem. It's solving four simultaneous equations with four unknowns: x, y, z, and t, where t is the difference between the receiver's clock and GPS time. Since there are four variables to solve, the receiver must be able to see at least four satellites to compute a solution.
The more precise the time stamp from the satellite, the more precise the position calculation. This is why each GPS satellite carries multiple redundant atomic clocks. And why by commanding the satellites to introduce variation in the time stamps - jitter - the U. S. military can reduce the usefulness of the GPS broadcasts to civilian receivers while their own units continue to receive encrypted messages with the more precise time.
This makes GPS a remarkably useful technology for getting the current date and time. Even if you're not interested in where you are, you might be interested in when you are. Telecommunications and other systems now routinely synchronize their own sense of time to the highly accurate satellite time using GPS receivers.
All of this - the map of the orbits of the satellites, the precise internal clock synchronized to GPS time, the code to do the complex position calculations - is embedded inside the tiny commercially available GPS chip sets. All the heavy lifting is done for you.

That it works at all may seem like a little miracle. But this basic idea has been around for a long long time. Ships in coastal waters used to measure when they heard a fog horn sounded at regular known intervals, emitted from a station at a well known map location, against their own ship's clock to compute their distance from the shore.

The Software

Most GPS devices support the National Marine Electronics Association (NMEA) 0183 specification. (Version 4.10 is the one I used). They may also support their own proprietary data formats, and there are sometimes good reasons to use those. But the NMEA 0183 spec provides a data format that is simple to use and meets many needs.

NMEA 0183 defines sentences, records consisting of ASCII data formatted into comma-separated fields. Each sentence begins with a dollar sign ($) and is terminated by an asterisk (*), a checksum encoded as two hexadecimal digits (e.g. 77), a carriage return (\r), and a line feed (\n). These sequences defines the framing of every GPS sentence. (This will be important later).
The first field in every sentence contains a string identifying the specific talker (e.g. GP means a GPS device) and what kind of record it is. In the example sentences above, the records RMC, GGA, GSA, and GSV contain, respectively, the recommended minimum (basic position, heading, and speed), the position fix (latitude, longitude, altitude, and time), the active satellites (those that where used for the position fix), and the satellites in view (those that the receiver can see, whether it uses them or not). There are lots of other possible sentences, but these four seem to be the ones that most GPS chipsets emit by default.
Screen Shot 2017-02-15 at 8.55.15 AM
When my software parses and interprets the NMEA sentence stream, it displays a report on the terminal in a form that is a little more comprehensible than the raw NMEA sentences. This is a screen snapshot from my laptop inside the car as I was running the test. (The terminal display on the base station in my office is identical, as you can see in the video.)

The software displays the NMEA sentence it received from the GPS device, and the sentence it forwarded to the base station. Next is a summary of the data in a form I can understand: the date and time in Universal Coordinated Time (UTC); the latitude and longitude in degrees, minutes and seconds; the altitude in feet; the compass heading; and the speed in miles per hour. Following that is the same data in a more technical form: the latitude and longitude in decimal degrees, the altitude in meters, the heading in degrees, the speed in knots (nautical miles per hour), and some internal information about the how the data in the NMEA sentence was encoded. Next is a list of the specific satellites used in the position fix, and some information about how accurate the fix is based on the positions of the satellites. Finally is a list of all the satellites in view, their identification number, elevation, azimuth, and signal strength.

Oh, No, Not Another Learning Experience

This project, which I code-named Hazer (a rodeo term), is divided into two parts: a library of C functions that handle the parsing of NMEA sentences, and a command line utility, gpstool, whose original purpose was to provide a functional test of the library. Like most complex UNIX command line tools, using gpstool looks like a case of ASCII throw-up.
gpstool -D /dev/ttyUSB0 -b 4800 -8 -n -1 -6 -A lead -P 5555 -E
This is the command on the remote unit that reads from the GPS device on serial port /dev/ttyUSB0 at 4800 bits per second, forwards the NMEA sentences to the base station lead (whose IPv6 address is in the remote unit's /etc/host file) on port 5555, and displays a report.
gpstool -6 -P 5555 -D /dev/ttyS0 -b 4800 -8 -n -1 -O -E
This is the command on the base station that receives NMEA sentences from the remote unit on port 5555, emits the sentences on serial port /dev/ttyS0 at 4800 bits per second for Google Earth to read, and displays a report.

I wrote gpstool to use the User Datagram Protocol (UDP) to forward the NMEA sentences to the base station. UDP is a protocol implemented on top of the Internet Protocol (IP), both versions 4 and 6. It differs from its peer Transmission Control Protocol (TCP) in some important ways.

TCP guarantees delivery, and order. If the protocol stack on the receiver detects that that a TCP packet was lost, it notifies the sender to resend the packet. The entire packet stream from the sender is delayed: the pending packets behind the lost packet are held in buffers on the sender, until the lost packet makes it through to the receiver.

This sounds like maybe a good thing, and sometimes it is. But for time-sensitive real-time data, this is a real problem, particularly on mobile radio links where the communication channel is routinely disrupted. GPS location data effectively has an expiration date; it goes stale quickly. The GPS device is constantly emitting location information in the form of NMEA sentences, a new position fix about once per second (or as often as five times a second on some of the GPS devices I tested). If an NMEA sentence is delayed due to a transmission error, there is another sentence just a second behind it containing a more current fix. And another even more current fix a second behind that one. It is better to toss a delayed sentence and wait for the next one, instead of processing old news.

My IPv6 testing with the LTE modem (see Buried Treasure) demonstrated that there is occasional packet loss in the mobile network. Using TCP would lead to filling up kernel buffers on the sender dealing with the retransmissions, to congestion and perhaps even more packet loss on the network as bandwidth is used to transmit the same packet over again, sometimes more than once, sending data that is ultimately no longer useful.

UDP, on the other hand, is best effort. UDP does not guarantee delivery. UDP doesn't even guarantee that the order of arriving packets is maintained, since successive UDP packets can take different routes through the network with different bandwidths, latencies, and propagation delays. gpstool doesn't get upset with lost NMEA sentences; it just picks up with the next position fix it receives. And because each position fix comes with a UTC timestamp, it can detect time running backwards and reject sentences that arrive out of order.

  • Sometime it is better to lose data than to receive it with absolute reliability.

This was not a new lesson for me. I first encountered this twenty years ago when I worked at Bell Labs on a telecommunications system that used Asynchronous Transfer Mode (ATM) to carry voice calls between distributed portions of the system on optical communication channels, sometimes even across international boundaries. We leveraged features of ATM like traffic management, class of service, and quality of service, so that frames of voice samples that arrived late were tossed in favor of the next frame that was sure to arrive shortly. And I encountered it again a few years later, when ATM was replaced with Voice over IP (VoIP), where frames of voice samples were carried on the Internet using Real Time Protocol (RTP).

For people that have never worked in telecommunications, the complexities of reconstructing, in real-time, analog sound from digitized voice samples always involved a lot of explanation. Or a lot of hand waving. For sure a lot of white board diagrams. But the real-time nature of a position fix of a car driving around the neighborhood is something I think is pretty easy to grasp.

But Wait, There's More

TCP implements a byte stream with no implicit framing. That is, what the receiver reads from its TCP socket in a single operation isn't necessarily the same bytes that the sender wrote to its TCP socket in a single operation, although the complete byte stream is guaranteed to be the same from beginning to end across all reads and writes.

UDP implements datagrams, where every read of the UDP socket by the receiver delivers a block of bytes with the same beginning and end that was written by the sender in a single operation, if that datagram successfully made it from sender to receiver at all.

When I first wrote gpstool, I intended it to just be a handy way to functionally test the Hazer library. When I got the idea of forwarding NMEA sentences to Google Earth, I initially tried using socat, the handy utility available for Linux/GNU and MacOS. My socat command on the remote unit looked something like
socat OPEN:/dev/ttyUSB0,b115200 UDP6-SENDTO:lead:5555
with a similar socat running on the base station.

But socat doesn't know anything about the framing of NMEA sentences from the GPS device. It just reads as many bytes as are available on the serial port, packages them up into a datagram, and sends them off.

When UDP packets were occasionally lost, it was a disaster on the base station, since what was lost wasn't typically a complete NMEA sentence, but the middle of one, or the end of one and the beginning of the next one. The state machine in Hazer responsible for reconstructing NMEA sentences could recover from this. But the stream of NMEA sentences was badly corrupted, and a lot of time was spent dealing with it, with a lot of lost sentences.

So instead, I added the UDP forwarding feature to gpstool, which sent UDP datagrams containing only single whole NMEA sentences. This made the reconstruction of the NMEA sentence stream, and dealing with the occasional lost sentence, almost trivial.

  • Sometimes losing data isn't so bad, if you have some control over what data you lose.

As a result, I have run gpstool on the remote unit and on the base station, the former sending NMEA sentences from the GPS device to the latter, for hours with no problems.

You Can Do This Too

The Hazer library, along with gpstool, is available as an open source project on GitHub.
Although the Hazer library only relies on the standard C and Posix libraries, gpstool makes use of Diminuto, my library of C systems programming functions, which is also available as an open source project on GitHub.
Roundhouse, my IPv6 test bed, is yet another open source project on GitHub.
The availability of inexpensive and reliable GPS receivers with easy to use USB-to-serial interfaces, and the simple ASCII format of NMEA 0183 sentences, makes using the Global Positioning System straightforward and rewarding. It's your tax dollars at work. Isn't it time you added some geolocation capability to your project?


SiRF, NMEA Reference Manual, 1050-0042, Revision 2.2, SiRF Technology, Inc., 2008-11

NMEA, Standard for Interfacing Marine Electronic Devices, NMEA 0183, version 4.10, National Marine Electronics Association, 2000

E. Kaplan, ed., Understanding GPS Principles and Applications, Artech House, 1996

Wikipedia, "Global Positioning System",, 2017-02-12

Tuesday, January 31, 2017

Buried Treasure

I confess to a rather inconvenient character flaw: I can only learn by what I refer to as "the laying on of hands". Reading books and articles is entertaining. I enjoy talks and lectures and conferences and other excuses to get out of the lab. But when it comes to developing expertise and internalizing knowledge, for me there's no substitute to actually doing.

So when I decided it was time to learn about version 6 of the Internet Protocol (IPv6), I knew I was going to have to spend some time writing some code. Since I make my living as a product developer, with a profitable emphasis on the low level, I was interested in how applications and systems would be affected by the API changes brought on by IPv6 when compared to that of the venerable version 4 Internet Protocol that I - and everyone else - had been using for decades.

Internet Protocol version 4 (IPv4) is the historical foundation for most of the Internet and World Wide Web that we all know today. But for reasons that will become clear if you make it through this lengthy article, IPv6 is becoming increasingly necessary in today's world of global deployments, mobile devices, and the Internet of Things (IoT).
(You can click on any of the images in this article to be taken to a larger version.)
The Big Picture
Power Curves

Long time readers will recognize this logarithmic graph: it compares the relative exponential growth rates of several technological domains: microprocessor speed, number of CPU cores, memory size, etc. It's easy to see that the rate of growth of Internet connectivity outstrips all of the other domains, even though those other domains are enablers of that growth. But technologists architect, design, implement, and pay for systems that meet anticipated needs over a relatively short time window. Designing for the far future is hard to justify economically, especially when such designs may not work for the circumstances you find yourself in today.

Internet Hosts Count log

This second logarithmic graph shows the growth in Internet connectivity by year. The years are important here: IPv4 was architected, designed, and deployed roughly from 1974 to 1983 when it was established as the standard protocol for ARPANET, the U.S. defense department network that was what passed for the Internet in those days. ARPANET was a child of the Cold War: both its funding and its design revolved around this fact.

When IPv4 became the standard, there were hundreds of hosts on the Internet. One of the problems with living on an exponential growth curve, particularly at the beginning, is that it may be difficult to see that you're living on an exponential growth curve. And even if you do, it may be difficult to convince other people that you have to plan for billions of hosts on the Internet.

A History Lesson

When people say "IP", at least in the United States, typically IPv4 is the protocol they mean. It is the protocol most folks in the U.S. use today, whether they know it or not, when they cruise the web. It is the protocol implemented by the WiFi router they bought at their local electronic store. When folks say "TCP/IP", it is somewhat of a misnomer: Transmission Control Protocol (TCP) is one of several protocol layers that runs on top of IPv4. User Datagram Protocol (UDP) is another that is also widely used by Internet-enabled applications.

IPv4 was planned around what its designers could foresee. It used 32-bit addresses, really just integer numbers, allowing for an almost inconceivable at the time 4.2 x 109 or more than four billion hosts. The addresses are by convention written as four octets (8-bit numbers), in decimal, separated by periods.
An internet is network of networks. An IPv4 address identifies not just a particular host, but the network to which that host is connected. So hosts on the same network would share some of the same values as part of their IPv4 address. This was done so that the routing of data packets on the Internet could be for the most part table driven and efficient.

When the Domain Name System (DNS), a distributed database system that maps domain names like to one or more IPv4 addresses, came along, those addresses were stored in records referred to as type A. A for Address. (This will become important later.)

Since each network on the Internet needed a unique block of address, and each host a unique address within that block, there eventually was a U.S.-based authority that as responsible for assigning and keeping track of blocks of addresses, the Internet Assigned Number Authority (IANA). Organizations that connected their network to the Internet were assigned small or large blocks of addresses by the IANA, depending on their anticipated need.

These blocks were organized using a scheme that made it easy to tell what part of the address was the network part and what was the host part; different ranges of address blocks were in different classes. There were just three classes, A, B, or C, depending on how the network and host values in the address were divvied up: for addresses in the class A range, only the first octet or byte identified the network; class B, the first two octets; class C, the first three octets. So each class had a different ratio of the number of networks to the number of hosts on a particular network that could be represented.

As the Internet grew from hundreds to millions (and later, billions) of computers, and its geographic span grew as well, the Internet evolved from a U.S. defense internetwork designed to survive a nuclear strike into a global internetwork that included networks and computers that were part of commercial, educational, cultural, government, and other kinds of organizations. The class scheme that mapped addresses into networks and hosts turned out to be too inflexible for the growth it was being asked to address. And organizations outside of the United States rightfully objected to a U.S.-centric organization controlling the allocation of what had become a valuable and limited global resource. (The IANA probably didn't really want the job of managing IPv4 addresses for everyone in the world, either.)

In 1993, the class scheme was replaced with a new scheme called Classless Inter-Domain Routing (CIDR). With CIDR, the division between the network and host portions of the address could occur on any bit boundary, and could be different for every network. You could no longer tell just by looking at an IPv4 address what part identified the network and what part identified the host. (Subnet masks made even more complex schemes possible, but you had to be a masochist to use them.) This made routing much more complicated and computationally expensive. But it gave Internet architects a lot more flexibility in assigning and managing blocks of addresses.

CIDR was made possible by those very same exponential curves that caused the problem in the first place. While the WiFi router that sits in my family room is a relatively modest piece of kit, so-called core routers that handle traffic on the Internet backbone are effectively special purpose supercomputers, and are priced accordingly. The growth of the Internet and the growing computational cost of routing strains our ability to build, or pay for, routers to handle IPv4 traffic.

Regional Internet Registries world map

The globalization issues was addressed by establishing five broad regional organizations to control the allocation of IPv4 addresses: Africa (AfriNIC), Asia-Pacific (APNIC), North America (ARIN), Latin America and Caribbean (LACNIC), and Europe (RIPE NCC). The IANA still existed, but it now handed out large blocks of addresses to these regional organizations, who were then responsible for divvying up those blocks to organizations in their region of responsibility.

The Limits to Growth

So that's pretty much were we are now.  How are we doing with the whole IPv4 address thing? It is probably no surprise that folks in the know watch this closely. And it's not hard to find web sites that give you up to the minute real-time statistics on how many IPv4 addresses are left. Here's a snapshot I took a month or so ago from a web site managed by Hurricane Electric, an Internet service provider.

Screen Shot 2017-01-13 at 2.01.52 PM

Huh. That's not good.

According to this, the IANA has no more IPv4 address blocks to give out. And the well at the American Registry of Internet Numbers (ARIN) is dry too.

Yep, this isn't a joke. North America is clean outta IPv4 addresses. There are no more to be had. And at the rate the Internet is growing, the other regions won't last much longer either.

So how is it that every new mobile phone and tablet has an Internet connection? And as soon as someone moves out of their parents' house, their first purchase is a WiFi router so they have Internet connectivity in their dorm room, apartment, condo, or house?

There are basically two ways this is being handled.
  1. If an organization in North America requests a block of IPv4 addresses, they go on a waiting list. As organizations give up IPv4 address blocks (a rare occurrence but it does happen), the addresses are aggressively recycled and assigned to folks on the waiting list.
  2. Rampant cheating.
Remember when I mentioned those higher level protocols TCP and UDP? IP is responsible for getting data to the right network, and host on that network. But once there, it is up to TCP and UDP to determine which application or service that data goes to. It is easy to see how this is necessary if you just consider your mobile phone: at any moment it is burning up your mobile data plan because your Facebook app is updating your news feed, your Google Mail app is checking for new electronic mail, your Messenger app is checking for new messages, your weather app is checking for alerts, and what not. All of these data streams have to be kept separate and directed to the appropriate app.

If those apps are using TCP or UDP, this is done using a port number. Port numbers are 16-bit numbers known only to TCP or UDP; IP really has no idea they even exist. Sixteen bits gives us about 6.5 x 104 or sixty-five thousand possible values. Port numbers are conventionally written as a single decimal number. For example, the standard port number for a web server is port 80. When you cruise the web and clink on a link, you are sending data to port 80 to the web server on whatever web site you are visiting.

If you and your buddy were to peer into the web pages that manages each of your WiFi routers in your respective homes, or the apps that manage your internet connectivity of your mobile phones, tablets, or laptops, you might be surprised to find out that your router is assigning the same IPv4 addresses to the Internet connected devices on your WiFi network as your buddy's. My iPhone has the address on my home network. Yours might too. And my WiFi router has the address It is extremely likely yours does as well.

In order to spread the use of IP addresses further, when it became clear that we were heading for Peak IPv4, Internet architects came up with some clever strategies of exploiting that largely unused port number range. Largely unused because at the time no one could conceive of a single computer really being able to use sixty-five thousand connections. Through mechanisms called Network Address Translation (NAT) and Port Forwarding (I've never seen an acronym for that but let's call it PF), your home router (probably) has an actual unique IPv4 address assigned to it by your Internet Service Provider (ISP), but every IPv4 address that is used behind it has a private address, which is to say, it is not unique, and no one outside of your home network ever sees it.

Instead, as far as the outside world is concerned, all of your Internet connections appear to terminate at your router, to its unique IPv4 address, each connection with its own unique port number. Your router maps every single packet over each of those connections to some private address (via NAT) and port number (via PF) on your home network. The devices on your home network, with  their private IPv4 addresses, are not globally routable. Which is to say, they are effectively not on the Internet. Only your router is on the Internet. Maybe. Probably. There are a few implications of this.
  1. NAT and PF are expensive. Your router has to break apart every IPv4 packet and deal with the TCP and UDP layers, rewriting data in every single packet to preserve the illusion of Internet connectivity. As the private network behind a router grows, this becomes less and less feasible.
  2. Those exponential growth curves make it more and more likely that a single computer, or network of computers, or internetworks of computers, behind a single router, can actually support sixty-five thousand or more simultaneous data streams. So it becomes increasingly possible for Internet connections to fail because all the port numbers are in use.
  3. The IPv4 address shortage is so severe, that the address assigned your router may itself be a private address. If so, then there is another entire layer of NAT and PF going on of which you are not even aware. The sixty-five thousand port number limit occurs at which ever router up the line that actually has a globally routable IPv4 address. And the computational load on that router is proportionally greater.
  4. It has been clear for a long time that the solutions used to extend the usefulness of IPv4, like NAT and PF, were limited not just in scalability, but in functionality. The need for a centrally implemented and managed point of connectivity on which to perform NAT and PF had major implications for the mobile devices that had to switch not just from cell tower to cell tower, but from provider to provider,  as the devices change location. And the lack of global routability didn't fit with many of the expected network architectures of the Internet of Things in which small devices might be independent of central management.
This One Goes To Eleven

And we're out of IPv4 addresses.

So from about 1995 to 2005, Internet engineers designed and implemented Internet Protocol version 6 to solve as many of these problems as they could foresee. They could have doubled the address space of IPv4 just by adding a single bit. Or increased it by a factor of four billion by doubling its size to sixty-four bits. But instead, they cranked IPv6 addresses up to 128-bits in length. This yields about 3.4 x 1038 possible values, a number so big we don't have a word for it, although hundred billion billion billion billion might serve. This vast address range means really large blocks of addresses can be reserved for special purposes, and addressing can be designed to reduce the computational load on routers by eliminating complexities like CIDR.

IPv6 addresses are conventionally written as eight hextets (16-bit numbers) in hexadecimal, separated by colons.
There are no classes. IPv6 separates the fields in an address in a CIDR-like fashion, on bit boundaries. There is some advantage to separating the fields on a hextet, octet, or hex digit boundary when possible, just for readability. As we will see in some examples below, the first hextet of the address carries special meaning, indicating whether the address is private or global or what not.

Typically, IPv6 addresses are divided up into a 48-bit prefix that identifies the organization (2600:100e:b003), 16-bits that identifies the network within the organization (f288), and a full 64-bits to identify the interface (c265:6cae:85c8:4f68). The separation between the network and host portions of the address is specified CIDR-like, for example /64 above. Some ISPs provide a 64-bit prefix (/64) instead of a 48-bit prefix (/48), but that merely means they aren't allowing you to further divvy up your address space into subnetworks. Other prefix lengths between /48 and /64 are possible, with /60 being a common one. A /128 prefix really means your ISP is assigning you a single IPv6 address.

Why interface, and not host? Because when IPv4 was invented, no one could conceive of a computer, except for routers, having or needing more than one network interface. But today, your mobile phone has a network interface to the cellular network, and another to the WiFi network. Your laptop may have three network interfaces it uses simultaneously: a cellular modem, a WiFi radio, and a wired Ethernet connection. The interface portion of the IPv6 network is sixty-four bits to make it trivial to map commonly used lower level hardware addresses (like a 48-bit Ethernet address) easily into the interface portion of an IPv6 address.

If you access a domain name that can map to an IPv6 address, like can, that address is stored in a type AAAA record in DNS. Type AAAA because an IPv6 address record is four times bigger than an IPv4 address record. No, really.

TCP and UDP still exist, and for the most part run as they did before but now on top of IPv6. (There are a few differences in how checksums are calculated by these protocols, but that's immaterial to this discussion.)

IPv6 is the new world order.

Except IPv6 is not new. As early as 2004, the Linux 2.2 kernel saw an IPv6 protocol stack implemented alongside its existing IPv4 stack. By 2005, IPv6 saw broad deployment among many internet service providers. IPv6 is being widely used in parts of the world - particularly Asia and Europe - that see high growth in Internet connectivity, high population density, and nearly ubiquitous use of mobile devices. Mobile network providers in particular are driven to use IPv6 both for its scalability and the global routability it provides to the devices that use it.

But in the United States, IPv4 is a victim of its own success, so broadly deployed and used that a sudden wholesale conversion to IPv6 is just not practical. Never the less, numbers don't lie: the move to IPv6 is necessary and inevitable, driven by the continued exponential growth of Internet connectivity.

Fortunately, you can easily experiment with IPv6, even in your existing IPv4 infrastructure.

The IPv6 Man Cave


This is what passes for my lab bench in my home office. Somewhat remarkably, there are at least eleven Linux-based systems pictured here, including an Android phone, an Asterisk PBX, and my Linux/GNU server named "Mercury" that I use for software development. To the lower right you can see an anti-static mat with a pile of stuff on it. This is my IPv6 testbed.


"Roundhouse" is my tiny IPv6 router. It is a Raspberry Pi 2 in a black case on the right that runs OpenWrt, an open source router package. Roundhouse has two Ethernet connections, one to my IPv4-based home network (an Ethernet switch to the far right), and one to my IPv6 testbed network (the Ethernet switch near the center).

Screen Shot 2016-12-07 at 9.40.06 AM

OpenWrt supports a 6in4 tunneling mechanism that allows you to reach the IPv6-based Internet by passing IPv6 packets over an IPv4 connection to an internet service provider that acts as a tunnel broker. Hurricane Electric provides just such a capability. My IPv4 ISP is Comcast, but my IPv6 ISP is Hurricane Electric; I tunnel through the former to reach the latter.
Important Safety Tip: when you implement such a tunnel, you are driving a big hole right through the firewall in your IPv4-based router. Furthermore, since IPv6 eliminates the need for NAT and PF, it also eliminates the additional security that those mechanisms provide to hide your home network from the Internet. IPv6 potentially makes all devices connected to it globally routable, that is, reachable from anywhere else on the IPv6-based Internet. Getting your firewall right will be even more crucial when you use IPv6. I'm paranoid enough that the IPv6 network I've documented here no longer exists. Before I deleted that Hurricane Electric tunnel, I did a lot of IPv6 firewall testing using network penetration tools like nmap. So should you.

"Tin" is a Raspberry PI 3 whose sole network connection is via a cellular modem to Verizon Wireless' LTE network that supports both IPv4 and IPv6.

"Lead" and "Copper" are Raspberry Pi 3s, and "Bronze" a Raspberry Pi 2, that are all connected to the IPv6-based test network.

"Zinc" is a Raspberry Pi 3 that is connected only to the IPv4-based home network.

Mercury, my development server, has two Ethernet interfaces, and is connected to both the IPv4 home network and the IPv6 test network.

All of the systems in the testbed run some version of Linux, and all have dual protocol stacks: they can speak both IPv6 and IPv4 on the same network. Any organizational transition from IPv4 to IPv6 is likely to be gradual, and running dual stacks is in my opinion the only reasonable approach. (I've also routinely connected Mac and Windows systems to this network, just plugging them into the testbed Ethernet switch, and they worked just fine using IPv6 too.)

The Naming of Cats

Let's suppose you wanted to run a server application on Lead, one of the Raspberry Pi 3s on the IPv6 test network. What IP address, v4 or v6, might you use to reach it? It turns out there are a lot of choices, and they all work.
Screen Shot 2017-01-16 at 1.51.32 PM is Lead's private IPv4 address assigned by good old DHCP on the router. This works because Lead runs both the IPv4 and IPv6 protocol stacks and can use them interchangeably on the test network.

0:0:0:0:ffff: is a v4-mapped IPv6 address: an IPv6 address with an IPv4 address encapsulated in it. This is the standard approach of presenting an IPv4 address to the IPv6 protocol stack. It can be abbreviated ::ffff:, the IPv6 convention being :: means "insert as many zeros here as you need". is the static IPv4 address of the Roundhouse router on the home network, plus the port number 5555 that I defined. This works because I added an old-school NAT and PF rule to the Roundhouse firewall to map all IPv4 packets arriving on port 5555 on the router to the same port number on Lead. The router has to handle the mapping and rewriting of every single packet that arrives on this port. This is likely how your own IPv4 network works today.

fd71:9abb:2f8a::1ffa:1d19:2d51:88cf is a unique-local or private IPv6 address created by Lead using the fd71:9abb:2f8a prefix provided by the router, a 0 subnet, and a 1ffa:1d19:2d51:88cf interface address created using a cryptographic hash. Yes, IPv6 has the equivalent of IPv4 private addresses, and like IPv4, they are not globally routable.

fd71:9abb:2f8a::bb6 is another unique-local IPv6 address assigned by the router using DHCPv6. It has the same prefix and subnet number as the prior unique-local address, and an interface address generated by DHCPv6.

fe80::a2b7:5f4b:a1a3:7cf9 is a link-local IPv6 address, another form of private address. It is created by Lead just to talk to its router, and is only visible on the link that they share (in this case, the Ethernet).

fe80:d6a9::38bf:e273:1704 is another link-local IPv6 address, this one assigned to the Raspberry Pis wireless interface which I didn't use in this project.

::1 is the IPv6 equivalent of the IPv4 loopback address could use either of these addresses to talk to itself.

2001:470:4b:4e2:92d3:a519:6d57:b1e4 is finally what you were waiting for. It is the global-unicast IPv6 address, with the globally routable prefix 2001:470:4b assigned by Hurricane Electric, the subnet 4e2 also assigned by Hurricane Electric (because I elected not to subnet my tunnel), and the 92d3:a519:6d57:b1e4 interface address generated using a cryptographic hash (some IPv6 stacks use a form of the Ethernet MAC address here, but by default this stack uses what is essentially a random number).

Those Who Can Do

So let's run a server on Lead, and a client that talks to it on each of the other systems in the testbed. We'll use a program called internettool that is part of my Diminuto C-based package of Linux/GNU systems programming tools.
Diminuto is open source (LGPL), and portions of it have found their way in to a number of products shipped by several of my clients. So don't be too surprised if it turns up in your travels. Besides tools to test network connectivity, Diminuto also has tools to test other stuff, like General Purpose Input/Output (GPIO) hardware and serial ports, interfaces that are commonly used in my line of work.
In each of the screen shots below, all of which are from the same test session, I let the test run for an hour or two, then suspended each of the programs so that the command that I used for the test is displayed by the shell.

Screen Shot 2017-01-23 at 1.46.27 PM
Lead is running internettool in server mode: it receives packets and sends them right back to the sender. It is using IPv6 (-6) and UDP (-u). It is listening on port 5555 (-p 5555). Each time it receives a packet, it displays it proceeded by a timestamp and the IPv6 address from which it was received.

Perusing the source IPv6 addresses reported by Lead yields some interesting stuff.

Zinc packets are arriving from the v4-mapped IPv6 address
on the IPv4 home network (the network part of the IPv4 home network is 192.168.1).

Tin packets are arriving from the global-unicast IPv6 address
which is the IPv6 address Verizon Wireless assigned to the LTE modem for this test.

Mercury packets are arriving from the unique-local IPv6 address
private to the IPv6 test network.

Bronze packets are arriving from the v4-mapped IPv6 address
on the IPv6 test network (when using IPv4, the network part of the IPv6 test network is 192.168.2).

Copper packets are arriving from a v4-mapped IPv6 address
on the IPv6 test network.

So what do the clients look like?
Screen Shot 2017-01-23 at 1.46.31 PM
Zinc is running internettool in client mode: it sends packets and expects to receive the same packet back. It is using IPv4 (-4) and UDP (-u) - recall that Zinc is on the IPv4 home network. It is sending to the static IPv4 address of the router (-A using port 5555 (-P 5555) - it is relying on the old school NAT and PF mechanism provided by the OpenWrt router, which must crack open and rewrite all of Zinc's data packets.
Screen Shot 2017-01-23 at 1.46.20 PM
Tin is running internettool in client mode. It is using IPv6 and UDP. It is sending to the global-unicast IPv6 address of Lead (-A 2001:470:4b:4e2:92d3:a519:6d57:b1e4) - recall that Tin is on the Verizon LTE network - using port 5555. Note the -7 reported by Tin: this indicates that it has lost seven packets, which is more than ten percent (the sequence number of the last received packet is seven behind that of the last sent packet). This is possible when using UDP, and seems to be typical of the LTE cellular network. None of the other clients in the text fixture lost any packets.
Screen Shot 2017-01-23 at 1.46.39 PM
Mercury is running internettool in client mode. It is using IPv6 and UDP. It is sending to the unique-local IPv6 address of Lead (-A fd71:9abb:2f8a:0:1ffa:1d19:2d51:88cf) - it can do this because they are on the same local area network - using port 5555.
Screen Shot 2017-01-23 at 1.46.34 PM
Bronze is running internettool in client mode. It is using IPv4 and UDP. It is sending to the IPv4 address of Lead on the IPv6 network (-A - it can send directly, not using NAT and PF - using port 5555.
Screen Shot 2017-01-23 at 1.46.23 PM
Copper is running internettool in client mode. It is using IPv6 and UDP. It is sending to the IPv4 address of Lead on the IPv6 network but in a v4-mapped IPv6 address (-A ::ffff: using port 5555.

All of these clients, using a broad mixture of addressing modes, and using either IPv4 or IPv6, were able to concurrently communicate bidirectionally with the same server on Lead, with the server using a single listening socket attached to port 5555 and IPv6.

Practical Considerations

Most of the commands you use for IPv4 either work with IPv6 or have IPv6 counterparts or equivalents. You use the IPv6 version of the command if you are specifying an IPv6 address, or if you want make sure the command uses the IPv6 address corresponding to the domain name you use (because most hosts that have an IPv6 address also have an IPv4 address, and DNS can map the domain name to either of them). Here are examples of how some commands change for IPv6.
ping6 (instead of ping
traceroute6 (instead of traceroute
ssh -6 
ip -6 
ip -6 neigh show (instead of arp
wget -6 
route -A inet6 
nslookup -query=AAAA 
host -t AAAA
Screen Shot 2017-01-17 at 10.15.28 AM
This is an example of using ip -6 neigh show on the router. Notice how both link-local (fe80:) and global-unicast (2001:) addresses are shown. You have to correlate them using the Ethernet link-level addresses (e.g. lladdr f0:d1:a9:d9:1f:4d) to know which IPv6 addresses point to the same physical Ethernet interfaces.

Screen Shot 2017-01-13 at 2.33.07 PM

If you want to specify an IPv6 address in a web browser, the standard is to put the IPv6 address in square brackets. This is a web page of the management interface (called LuCI) of the OpenWrt router. You can see the URL with its IPv6 address in square brackets
in the address bar at the top.

You can see that the router reports its IPv4 address on the home network (which is its WAN connection to the IPv4 Internet) and its IPv6 address of its end of the Hurricane Electric tunnel (which is its WAN connection to the IPv6 Internet).

Also note that the IPv4 WAN has as its default gateway my home WiFi router with its typical private address, but for the IPv6 WAN there is no default gateway. While OpenWrt allows you to specify a default gateway, it may not be necessary; IPv6 has mechanisms for a router to advertise itself on a LAN as the default gateway so that hosts can self-configure their route to the outside world.

Screen Shot 2017-01-18 at 8.22.37 AM
Wireshark works just fine with IPv6. In this example you can see that it displays both IPv6 and IPv4 packets on the same LAN. I've selected to decode a router advertisement packet in which the OpenWrt router provides its Ethernet link-layer address, both the Hurricane Electric globally routable IPv6 prefix and its IPv6 unique-local prefix, an IPv6 routing prefix, and the link-local IPv6 address of a DNS server.

Screen Shot 2016-12-24 at 3.19.18 PM

There are web sites that evaluate your implementation of IPv6 by forcing your web browser to perform a series of actions. is such a website. This is a browser window running on one of the Raspberry Pis on the IPv6 test network. The web site gets everything correct.

You Can Do This Too

Screen Shot 2017-01-17 at 9.16.01 AM
Roundhouse, my project to generate an OpenWrt router image that supports a Hurricane Electric 6in4 tunnel, can be found in a repository on GitHub. You'll have to set up a tunnel with Hurricane Electric using their web interface, create a configuration file with the parameters they provide you, and point the Roundhouse Makefile at it.
Screen Shot 2017-01-17 at 9.16.21 AM
My Diminuto C-based systems programming package, including the sources for internettool, can also be found in a repository on GitHub.
What Does It All Mean

I was concerned about the stability and usability of the IPv6 stack and associated socket API in Linux. I needn't have been; it all worked with no WTF moments. That shouldn't have been a surprise, given its maturity.

My testbed has convinced me that, with just a little work, it is possible to deploy IPv6 into a server-side product (for example, in a data center), and communicate with that server using either new IPv6 clients or legacy IPv4 clients in the field.


R. Graziani, IPv6 Fundamentals, Cisco Press, 2013

P. Bieringer, Linux IPv6 HOWTO, 2015-10-16

R. Gilligan, S. Thomson, J. Bound, J. McCann, W. Stevens, "Basic Socket Interface Extensions for IPv6", RFC 3493, February 2003

W. Stevens, M. Thomas, E. Nordmark, T. Jinmei, "Advanced Sockets Applications Program Interface (API) for IPv6", RFC 3542, May 2003

E. Davies, S. Krishnan, P. Sovola, "IPv6 Transition/Coexistence Security Considerations", RFC 4942, September 2007

T. Berners-Lee, R. Fielding, L. Masinter, "Uniform Resource Identifier (URI) Syntax", RFC 3986, January 2005

O. Li, T. Jimmel, K. Shima, IPv6 Core Protocols Implementation, Morgan Kaufmann, 2007

K. Auer, IPv6 Prefix Primer, IPv6 Now Pty Ltd, 2011

Update (2017-02-04)

A recent issue of the High Scalability blog was kind enough to cite this article. Even better, author Todd Hoff also cited a really interesting article on trends in Addressing 2016 for IPv4 and IPv6. Written by Geoff House of APNIC, it makes for interesting reading and is a great companion piece to this article (or perhaps vice versa), giving a much bigger picture view of Internet addressing, NAT, and PF.

I've also made a few corrections and clarifications here and there since this article was first published.

Update (2017-02-07)

I added my list of references that I found useful. I expanded a bit on the IPv6 address fields.

Friday, December 23, 2016

Christmas Pi

I have come to the conclusion that you could replace "climate change" with "IPv6" and get rhetoric on both sides of the debate that would sound plausible. And maybe vice versa. As some of my friends and colleagues have remarked
Bah! I've been hearing the IP address doomsdayers complain for years but people are still hooking up their thermostats to the Internet. IPv6 is a lie. I'll only believe it exists when I see polar bear that can support a 128bit address.
Please supply the names of all staff involved in engineering IPv6 readiness.
and even
I for one do not believe that IPv6 is caused by humans. 
See what I mean? In any case, I decided it was time for me to see what IPv6 had to offer.

(The following was updated on 2017-01-19.)


Roundhouse is my IPv6 router than runs the open source OpenWrt on a Raspberry Pi 2, and manages an IPv6-through-IPv4 WAN tunnel via Hurricane Electric, an (among other things) IPv6 tunnel provider. The router exposes the IPv6 WAN over an Ethernet switch on the upper right.

You can find the Roundhouse project, which is mostly just a makefile and some configuration, here:

The other Raspberry Pi 2 and 3 systems shown here, scrounged from other projects, form the bulk of my IPv6 testbed.

Tin has as its only network connection an LTE cellular modem through which it uses IPv6. I use it for penetration testing of my IPv6 firewall and to demonstrate the global routing of IPv6 global unicast addresses.

Zinc is normally used for testing software that handles GPIO and serial ports, but here it accesses systems on the IPv6 testbed from my production IPv4 network.

Bronze is normally my 32-bit ARM reference platform, but here it demonstrates a dual stack capability by using IPv4 on the IPv6 LAN.

Copper accesses IPv6 devices using a variety of mechanisms including IPv6 global unicast addresses, v4-mapped IPv6 addresses, and IPv6 local unique addresses.

Lead acts as a server, accepting datagrams over UDP or connections over TCP, and echoing any data it receives back to the sender.

I've been expanding Diminuto, my open source C/Linux/GNU-based systems programming library, to support its socket API on IPv6. It wasn't difficult. This library includes the software I've been running on on the Raspberry Pis. Portions of Diminuto have found their way into several commercial products. You can find it here:

Finally I'm still collecting and testing hardware entropy generators, a project called Scattergun that my alter ego recently gave a talk about. I hope to one day write more about that.

Quantum Entropy Generator

You can find Scattergun here:

I hope this convinces you that I have not been slacking off during the holidays.

Best wishes to you and yours. Season's greetings!

(And an especially jolly Ho Ho Ho and Thank You to Alan, Doug, and Dale for their IPv6 comments.)