Hi everyone,

I’m glad to announce that I don’t belong to 82 % of authors whose paper has been rejected from the IEEE IWQoS 2008 (acceptance rate 18 % for full papers in 2006). So I’m currently preparing the camera ready version of my paper and looking forward to a trip to The Netherlands in order to present it in June. I’ll post more information regarding the paper as soon as I’m done with the camera ready version.

The last IETF meeting was held in Philadelphia last week. Recall my previous posting about turning the protocol stack upside-down. Jonathan Rosenberg, who is with Cisco, presented a new trend in a talk at the meeting: TCP over UDP. The main motivation for this approach is NAT traversal, which can be done using UDP pretty well. Unfortunatly, the UDP protocol has, among other things, a lack of flow control, which is a pretty compfortable thing application level programmers do not want to miss. The combination of both advantages (NAT traversal and e.g. flow control) results in tunneling TCP over UDP. Thus, there is one more best effort datagram protocol layer in between. Does this endeavour highlights the need for a new Internet, as researcher in the Future Internet sector are claiming?

The above image shows the Internet density as logarithmic visualisation of the Information Please (r) database holding data concerning the Internet usage from 2005 mixed with a population grid.

I discovered RFC 3251 today, which describes Electricity over IP as persiflage to numerous RFC’s published by the IETF themed “X over Y”, whereas “X over Y” will be followed by “Y over X” sooner or later. Just for instance, once we had the usual setup where IP packets were encapsulated in Ethernet frames which is a often used link layer protocol (IP over Ethernet). Nowadays, Ethernet over IP is possible as well (RFC 3378: “EtherIP: Tunneling Ethernet Frames in IP Datagrams“), turning the ordinary protocol stack upside down by sending layer 2 protocols over layer 3.

Once upon a time, MPLS was used to go round the “time intensive” routing process in IP backbone networks by using pre-defined switching paths to guide the packet’s way through the network (IP over MPLS). Since June 2007 we got RFC 4817 describing how to encapsulate MPLS in IP packets (MPLS over IP).

In the 90’s, service providers were deploying ATM networks before they were suppressed by the more cost-effective Ethernet technology about a decade later [1]. ATM was once famous partly due to its Quality of Service abilities. Following the general trend, the next step towards a upside down protocol stack is to introduce the notion of pseudo-wires in order to route ATM over IP.

The next step is to tunnel Synchronous Optical Networking (SONET) over MPLS (over IP over … ?), which is interesting as SONET is synchronous whereas IP is not and easily leads to jitter within the transmission.

By the way, not only the IETF is tunnelling the whole protocol stack from every possible direction when needed. Also amateur radio operators encapsulate TCP/IP in AX.25 (the layer 2 protocol used for wireless transmissions in amateur radio) using the 44. class A IP subnet for accessing their own WWW called HamWeb or chatting over IRC instead of more appropriate solutions. So here we have IP over AX.25, which is just like IP over Ethernet, fine. However, when no radio is available, the radio network can be accessed by tunnelling AX.25 over IP (AXIP). So here we’re sending a layer 2 protocol over a layer 3 one again.

As Spam over IP is already old-fashion, we now got IP over Spam. Yes, online banking can now be encapsulated in Viagra! Note that this approach is new as layer 3 packets are now encapsulated in layer 7 data! We do no longer stick to tunnelling the lower layer but consider higher layers also. The potential benefit of this encapsulation is that the great (fire)wall in China can be overcome, as they’re sending and receiving a lot of spam which turns it into a high-bandwidth, low-latency channel, as Dan Kaminsky highlighted in his talk.

So what’s next? Well, RFC 3251 will give the definite answer: Electricity over IP, where IP packets carry electricity in discrete, digitalized form. The document is based on the discovery that the distribution network for electricity is not an IP network. So do service providers have to extend their triple play offerings (classical Internet, (IP)TV, telephone) by electricity over IP to get the IETF into non-technical areas such as the distribution of electricity? Electricity could be routed “over the Internet to reach remote places which presently do not have electricity connections but have only Internet kiosks (e.g., rural India)”. Well, I suggest to read the document and find out about newly emerging technologies, such as:

• MPLampS: Mostly Pointless Lamp Switching
• LER: ‘Low-voltage Electricity Receptor - fancy name for “lamp”‘
• VPN: Voltage Protected Network

So long,

Oliver — waiting for the first electricity trojan or worm and wondering whether houses are no longer in danger due to electricity thieves.

PS: When will we become tunnelling approaches that consider layer 8 (guess who’s controlling the applications …)? I could imagine IP over long or short term memory by memorizing the packet. I’m wondering how Raptor codes (a state-of-the-art Forward Error Correction technique) would perform when coping with an error process called forgetting?

PPS: RFC 2549 introduced Internet Protocol over Avian Carriers (IPoAC) . Will there be Avian Carriers over IP soon?

[1] Disclaimer (just to prevent of someone getting me wrong): Yes, I know how ADSL traffic is still carried (although there is a trend to migrate to Ethernet as this technology is cheaper than ATM due to its wide-spreadness), remember that this post is devoted to RFC 3251 which is a joke so some statements may be a bit “overgeneralised” here Moreover, I also know they benefits of tunnelling layer 2 protocols over IP, they are mostly written in the article “Layer 2 over IP/MPLS” by Chris Metz (Cisco) published in IEEE Internet Computing journal back in 2001. However, this post is not an article discussing pro’s and con’s of several technologies.

For some reason, that is not obvious to me at the moment, a correct understanding of the Gilbert-Elliott model seems to be hard. After giving a talk in October last year, where I also mentioned the model, someone said to me: “It’s great, you were actually the first person that explained the model correctly”. This confirmed my impression I got from reading papers dealing with this model some time ago. The explanations were not wrong, but some things were sometimes a bit mixed up. I’m wondering where this comes from as the model is actually quite simple. After I found another misunderstanding of the model in the web today, I thought it’s time to write a blog post covering Gilbert-Elliott.

However, what exactly is the Gilbert-Elliott model? Well, consider you want to describe the characteristic of a packet loss process where packets are dropped by a router in cases of overload on a given line. So what you want is to describe the behaviour of a channel and thus create a channel model. (The Gilbert-Elliott model was designed for describing bit errors and not packet losses, but is also used for the latter which I also find more demonstrative)

A very simplistic channel model is the memoryless channel, sometimes also called Binary Symmetric Channel (BSC) or Poisson channel, but I don’t want to go into details why there exist different names for it. In this channel model, a packet is dropped with a certain probability p and not dropped with probability 1-p. This decision is made for every packet separately. Therefore, packet drops are independent and identically distributed (iid). Longer bursts (longer than 1 lost packet in sequence) only rarely occur.

However, this simplistic model is not adequate to model channels were bad channel conditions tend to persist, e.g. when considering packet drops caused by finite queueing systems in routers. In 1960, Gilbert published a paper where he proposes a model to describe burst noise channels. His model is based on a 2-state Markov chain and thus adds memory to the Binary Symmetric Channel. Roughly speaking, the memory of the chain allows to define a probability of a packet being lost of the previous packet was also lost and thus to generate error bursts. The model looks as follows:

The Gilbert-Elliott Model

It consists of two states: the good (G) and bad (B) channel state. There are two transition probabilities, p and r. A transition from the good to the bad state happens with probability p and from the bad to the good state with r. Each state generates an error free packet with probability k (h), respectively. So the Gilbert-Elliott model has four model parameters that need to be estimated during training.

However, there are three commonly used versions of the model that should be differentiated. Let’s start with the most simple model version which I tend to call just ‘Simple Gilbert’. It only consists of two model parameters, the transition probabilities p and r. The state dependent error probabilities are set to k=1 and h=0, leading to a good state that generates no errors at all whereas the bad state generates nothing but errors. Model parameters for the ‘Simple Gilbert’ model can be easily obtained from an packet loss trace, as the state sequence is directly observable.

The model Gilbert published in his paper consisted of three model parameters: p,r and h. Thus, the above described ‘Simple Gilbert’ model is just a simplification of what Gilbert has originally published. However, Gilbert suggests in this paper to set h to 0.5, but his model allows h to be in the interval [0,1]. So the original Gilbert model is more general than most of the simplifications which are also entitled ‘the Gilbert model’. Moreover, something interesting happens when allowing h to be different to 0–the concrete state sequence is no longer observable in the output generated by the model or contained in the loss trace, as it is not obvious whether the symbol “packet not dropped” has been generated by the good or bad state. As there exists a doubly embedded stochastic process now, the Gilbert model forms an Hidden Markov Model.

What about the error probability in the good state, 1-k? Well, I did not forget about it in the last paragraph, this model parameter simply does not exist in the Gilbert model and k is always set to 1. Gilbert left the extension to the model by including k and thus allowing errors to be generated in both states to Elliott (1963). Model parameters in the Gilbert-Elliott model are usually set such that the bad state generates loss bursts, whereas the good states generates rare, single packet drops.

However, I read some papers that were only dealing with the simplified version of the Gilbert model, but entitled it as ‘Gilbert-Elliott’. This is one of the misunderstandings I often find in the literature. Another one, which I found quite often, is the misspelled name of ‘Elliott’ where authors forgot about one t at the end of the name (I guess this finding is somewhat related to Did They Read What They Cited? *g*).

Original papers:

• E. N. Gilbert, “Capacity of a Burst-Noise Channel,” Bell System Technical Journal, vol. 39, pp. 1253–265, Sep. 1960.
• E. O. Elliott, “Estimates of Error Rates for Codes on Burst-Noise Channels,” Bell System Technical Journal, vol. 42, pp. 1977–1997, Sep. 1963.