Independent Measurement of Broadband Provisioning Quality by SamKnows: A Step Towards Providers’ Accountability?

Some time ago on this blog we wrote about the lack of accountability in home broadband provisioning. We noted how difficult it is for a typical broadband customer to give evidence about poor service. One of the solutions to generate legally sound evidence we mentioned was to deploy hardware monitors attached to customer modems. This is exactly what SamKnows Limited have done, although the reasons behind their project are probably different. The project was partly backed up by Ofcom.

A report describing the project has been published by Sam Crawford here.  In this article, we briefly characterise the measurement scheme, pick out some interesting results and finally comment whether this scheme could be used to gather evidence about quality of broadband provisioning for individual users.

One of the objectives of Sam’s report is to enlighten the public about the myth that speed is by far the most important property of a broadband service. The results show that speed is only one of many properties which affect the quality of the service and that other properties can have larger effect on the quality as perceived by the user.

We at PaperPicker look at this project as an example of how Internet providers could be made accountable. A typical user can never find out, leave alone quantify, what is wrong with their connection. An ISP can always blame user’s equipment for the fault and it is extremely difficult for users to show evidence of poor service. A measurement scheme such as this is a real-world example of generating statistically and legally sound evidence.

What was done and how

At the heart of the scheme lie hardware monitoring units, installed at homes of volunteers and equipped with measurement routines. The monitoring units were deployed all over UK with the help of Ofcom. Over the course of 6 weeks in 2008 these units were generating multiple types of traffic, recording measurements and sending the results to SamKnows servers. The test included 223 devices and covered 12 UK-based Internet service providers (ISP).

What makes this project unique is the fact that the collected measurements are both independent of ISPs and statistically sound. The measurements are independent of ISPs because they do not require any cooperation from ISPs. Statistical confidence comes from the number of units deployed and the number of measurements carried out.

However, since SamKnows do not quite disclose the reasons for doing this project nor they specify how it is financed, one can have doubts over the independence. On the other hand, the project is backed up by Ofcom, the UK telecom regulator.

So how does it work?

A monitoring unit (Linksys WRT54GL with embedded Linux) is connected between user’s modem or router and user’s computers as shown in the figure below. The unit generates traffic only when the user’s equipment does not. A pre-programmed set of tests runs according to a given schedule and results are collected at SamKnows servers.

 

 

Metrics and results

Sam’s report presents and analyses a number of different measurements, but we will comment on a few selected ones in the following table.

Metric	Result	Comment
Latency	Provider-average of about 40ms.	Virgin.net did particular badly; at peak hours latency goes up by 180% compared to quiet hours, while the cross-provider average increases in peak hours by only 25%.
Loss	Very small across providers (under 0.6%).	–
Response time of DNS queries	Very good across providers (average of 46ms) with the exception of Be Unlimited which occasionally exceeded 4-times the average response time.	The report shows how DNS query times affect web browsing even when latency is low.
DNS failures	Very low with a failure rate average of 0.81%, apart from Be Unlimited at 2.82%.	–
Perception quality of VoIP	Most providers achieved a score close to the theoretical maximum, with the exception of Virgin Media, despite its very small latency.	Measurements show how jitter (the variance of delay) lowers the perception quality of VoIP. Virgin Media has excellent latency results but suffers low VoIP quality due to high jitter.
Speed as a percentage of implied line speed	Most providers achieve 75%, but from a more detailed graph we see that both ADSL and Cable Virgin drop significantly in speed during peak hours.	Implied line speed is defined as the maximum throughput achieved across all speed tests within a two day period.

 

Another interesting finding is the evidence of ISP performing traffic shaping for traffic at ports other than 80. This is because ISPs are trying to cap peer-to-peer protocols traffic and those use non-80 ports.
 
A small objection against the time averaging of results: Take the 75% line speed result. As such it may not reflect user’s satisfaction very well. For example, if for most of the day the speed is high but most users are not using the connection (they are not at home), and then evening brings a significant drop when many users are at home, the result may be 75% just because the speed ishigh for large part of the day.

So for example Virgin.net exhibits a 50% drop in implied line speed at peak hours. For a user who connects only in the evening (after work), this 50% drop would certainly translate into a larger drop in satisfaction than the three quarters suggested by the 75% time-averaged drop.

Would this scheme suffice to provide evidence of poor quality?

Although this measurement scheme was probably not developed with the aim of gathering evidence against ISPs, one could imagine it could be used in such way. Of course, only large-scale metrics could be reported, such as averages across large number of locations, metrics of commoly accessed DNS servers and such. A more granular evidence would require several monitoring devices per location (e.g., a street) and this might be financially unfeasible. Another issue would be the fact that the monitoring devices measure only when users are idle, while many faults occur when many users are using the service. And so while this is the first independent and statistically solid measurement scheme there is, its use as a monitor of quality for geographically clustered or individual users is limited.

The report certainly fulfills its premise by showing that connection speed has only a limited effect on user’s perception of quality and that the Internet experience is affected by many other factors which providers are in control of. Could this report serve as a hint to regulators that ISPs should enrich their contracts by other properties than mere speed?

Advertisement

Vint Cerf on Current Internet Research Problems

In September this year the British Computer Society organised an international academic conference, chaired by Prof.  Erol Gelenbe, featuring talks and papers under the theme of ”Visions of Computer Science”. Among the key speakers appeared also Vint Cerf, one of the founders of Internet’s underlying mechanics, currently holding the position of “Internet Evangelist” at Google.  Vint Cerf has given a speech on the history of Internet, its current issues and the concept of Interplanetary Internet.  In this article we would like to provide a handy list of what Vint Cerf considers as the most important research problems concerning current Internet.

List of research problems concerning the Internet

• Security at all levels

• Internet Erlang Formula

  Erlang formulas were used in telephony, whereby the call blocking probability could be calculated based on calls arrivals, duration and the number of lines. By “Internet Erlang formula” Vint means some tool which could relate network parameters to the network performance perceived by users or applications. Vint identifies the problem in the lack of up-to-date models. The never ending innovation of applications makes any model assumptions go quickly wrong, unlike in telephone networks.

• “Mobility is something that we have not handled well in the Internet“

  Vint said that he had made a mistake in the design of TCP/IP by binding too tightly TCP end-point identifier to the physical location/IP address. Currently, a TCP user moving elsewhere destroys the TCP connection.

• We are not exploiting the possibilities of
  • Multihoming – how do we take advantage of being connected to the Internet via multiple service providers at the same time (hence given several IP addresses simultaneously)
  • Multipath routing whereby multiple routes would be use simultaneously, rather than using one route after another breaks
  • Broadcasting, especially in wireless networks where broadcast is a natural feature of the medium

• Semantic web

  Vint asserts that there is a vast potential in creating machinable semantic relationships rather than mere hyperlinks. A searched expressions may exist in several different contexts and Internet users can help increase the semantic clarity of Internet content.

• The problem of rotten bits

  If we do not retain the software that had been used to create content in the past, it will become invisible and meaningless in the times to come. Think of a proprietary formats which are no longer supported by the company that developed them, or just older formats not longer supported.

• Energy consumption

  One of Google data centers consumes 128 megawatts of energy. Engineers increasingly take into account energy consumption as one of the design criteria when developing algorithms and computer architectures.

A note on IPTV

Most people associate video with streaming video. However, only 15% of the video we watch constitutes real-time video. Vint asserts that the rest can and should be thought of as a mere file transfer, since the source is not real-time. This consideration lightens the otherwise stringent demands a real-time video transfer impose on networks. Vint predicts that streaming will be only a minor aspect of video on the Internet.

A note on intellectual property

Vint notices that the Internet works by copying content, hence touching on the issue at heart of intellectual property protection. Vint suggests that copyright infringment in the Internet context will need to be defined differently from a mere copying.

A note on running out of capacity

Vint asserts that the backbone links composed of optical fibres are far from running out of capacity, but problems are real in the network edges. He sees this as a regulatory and economical issue.

A closing note

During the talk Vint presented a slide with a picture of a 1977 network demonstration he co-designed. The network managed to carry a real-time telephone call across 3 completely different networks – radio, landline and satellite – networks differing in modulation, bit-rate, loss-rate (kind of VoIP in 1977!). How much has the Internet really changed since then? Apart from its unprecedented growth, little seems to have changed in its underlying foundations. This article presented a list of current research challenges as seen by Vint Cerf, a visionary who co-fathered these foundations, a visionary with the most amazing track record.

The Role of Accountability in Home Broadband Provisioning

As of July 2008, some 20 years after the first Internet Service Providers (ISP) were formed and some 50 years after packet switching was invented, the home broadband customer still has no guarantee of any quality parameter, no way of holding his ISP accountable for interruptions and low speed, no choice of quality and no way to fairly share resources with other customers in times of congestion.

Any home broadband customer will be familiar with the situation when something is wrong with their connection, be it unavailability, high data loss or failed name servers. Yet upon contacting the provider one is taken through a bemusing routine of resetting their PC, router, modem, and whatever else has buttons to press, the ISP rarely saying: “It is our fault, we’ll refund you.”

What exactly determines the quality of a broadband connection? All performance characteristics will depend on

• Network dimensioning and management
• Behaviour of other customers
• Resource sharing mechanism in place
• The rest of the Internet.

While the rest of the Internet is not in the operator’s powers and the behaviour of the users only partly, the network dimensioning and resource sharing facilitation certainly are. Let us now briefly describe what these issues encompass and how today’s operators implement them.

(The lack of) Resource sharing mechanisms

Resource sharing is a mechanism determining the division of network resources between the operator’s customers, especially in times of high demand and congestion. Certain resource sharing is facilitated by medium access protocols. For example, the DOCSIS protocol used in cable networks has extensive means of controlling the total usage of resources of every user at any time. Also the transport layer offers some resource sharing mechanism; TCP controls the rate of every connection but not the total rate of a user. Besides, it cares about resources along the end-to-end path rather than the resources in the operator’s network only.
The medium access protocols and even transport layer protocols are fully controllable by the operator who could use them to facilitate resource sharing.

So how do some of UK’s major broadband providers deal with fair sharing? Virgin Media cable broadband penalizes rough customers after they have committed a high-usage activity. The ISP will reduce the speed of the user’s connection for the duration of 5 hours after the customer exceeds a limit on the amount of data he transmits or receives in a given time interval.
This means that

• The punishment becomes ineffective if the user is not interested in using the connection after the incident.
• The punishment does not protect others at the time of congestion.

British Telecom employs a “Fair Usage Policy” according to which a customer’s bit rate will be “restricted” when the customer becomes a “heavy user”.

Please note that the cable standard DOCSIS offers excellent facilities when it comes to QoS. It has 6 quality classes and 8 priority levels. It has total control over upstream (hence can regulate TCP connections by regulating the protocol acknowledgments) and it can also schedule the downstream. The DOCSIS standard is well documented and a number of QoS-related research papers have been written on the topic, most of them focusing on real-world implementation.

Network dimensioning and management

It is the number of customers that largely determines the operator’s income. The infrastructure acquired to realise the sold service reduces profit. It is only natural that an operator tries to increase the former and reduce the latter, given that the service quality is hardly monitored at all and that it is extremely difficult for a customer to claim refunds for bad service. It is obvious that a network operator has great incentives not to support any initiative aimed to objectively measure the quality of the offered service.

It is not practical to infer an operator’s network management because the ISP is not obliged to disclose this information and even if it did, its effect on quality is non-trivial. What is left then is the pursuit of a mechanism which would hold the operator accountable for the service it provides, hence possibly motivating the provider to change their network management.

The rest of this article complains about the lack of accountability and presents 2 hypothetical strategies to increase the accountability.

Operator’s accountability

The mere availability of a data connection is the core of the sold service but it is the quality of broadband provisioning that determines the utility customers derive from it. Yet, it is extremely difficult to prove that a service has been inadequate at some point in time. It is practically impossible for a common user to show that there was for example a packet loss-rate of 40% for the duration of 50 minutes last Saturday afternoon and that it was not the customer’s fault.

Why is it that we can take a broken watch back to the shop and have our money refunded, we can even raise legally sound complaints about complex services such as consulting or insurance but it is almost impossible for a non-techy broadband user to show that something was wrong with their broadband service? What is it about Internet service which makes it so hard to complain about?

For one thing, Internet provisioning is a multi-dimensional service. It spans across several time-scales, across space, it has complex statistical properties and it is perceived subjectively (unlike the quality of electricity or gas). But take the complexity of water quality standards, for example.  They comprise over 50 quantitative parameters every liter of drinking water must satisfy. Yet, utility companies do satisfy these standards and the state usually takes care of their monitoring.

One can argue that an additional set of requirements on home broadband provisioning would increase the cost and in turn the price, having a negative effect on the service proliferation. But surely one can use the same argument in the case of water quality, car safety, and many other areas in which more stringent legal requirements clearly brought benefits far outweighing the cost.

Proving unsatisfactory quality

Part of the Consumer Law related to the provision of broadband is the Sale of Goods & Services Act. Under the Sale of Goods Act 1979 and The Supply of Goods and Services Act 1982 service providers must sell goods that are, among other things,

• of satisfactory quality and
• delivered as described.

Of course, satisfactory quality remains undefined and the service is described only vaguely. Furthermore, even if some well-defined quality was breached, there would not be an easy way for a customer to prove it.

Let’s now design a simple hypothetical accountability strategy for today’s home broadband service. The aim here is to create a piece of evidence immune to the operator suggesting that perhaps there was a fault on the customer’s side.

A) Massively deployed application-layer metering

There are 2 ways we can think of, both solid for a court room. Since judges operate on the basis of reasonable belief, we’ll employ some statistics: If a large number of customers at the same time experience, measure and document a bad connection, it is unlikely that this is due to all of them having misconfigured their firewalls or having their cables cut at the same time. Naturally, in several cases it could have been the customer’s fault, but it is beyond reasonable belief that a large group of customers of a particular operator erred at the same time. Hence an application running on the customer’s computer can be used to generate evidence about the service when put together with a large number of other data.

A basic version of this concept is already in place. There are Internet forums where users post their measurements, obtained often from the excellent Speedtest.net. Now if these measurements were made automatically and the results processed to extract geographical and spatial commonalities, that would be a big step towards holding the ISP accountable.

B) Certified hardware monitors attached to customer modems

This method would rely on a device connected between the modem and user equipment. This device, let’s call it a monitor, will have a certification from some regulatory body such as the UK Ofcom. Operators will be legally obliged to allow this device be connected to the modem they provide. Another party – a governmental organisation or a regulated private company – will collect data from these monitors and make them available to the public. Since monitors are standardized and cannot be modified by the customer, there need not be a large number of them in order to rule out the customer’s fault.

Similarly to the way TV and radio ratings are collected from several customers, so measurement data will be collected from several monitors in a given locality, as illustrated in the figure below.

Both strategies require a start-up investment and some low long-term funding. Most customer will also need incentives to participate in the strategy.

Conclusion

Broadband speeds continue to grow together with the necessity of Internet access and the demands of new applications. Advances on the physical and medium access layer are being adopted by the industry. Innovative Internet applications are booming. Yet the experience of any more-than-slightly advanced Internet users is marred by poor network management, failures, oversubscription and unfair usage. At the same time, the progress on the intermediate layers – IP, transport, management – seems to stagnate. Thousands of research papers on quality provisioning and resource allocation seem to have been written in vain.

Be it a lobby group, customer iniative or the government themselves who will push the idea of accountability into practice, we think it is the key for a better home Internet provisioning.

Network Congestion Control, M. Welzl, Wiley 2005. (A Book Review)

Network Congestion Control: Managing Internet Traffic — Michael Welzl (Wiley Series on Communications Networking & Distributed Systems 2005).

The control of Internet congestion is a field entangling numerous research, engineering and economic topics, each of which, on itself, offers only a limited perspective on the problem. Some books on this topic treat it as a part of a broader field of network communications, others provide a narrow formal mathematical exposition. Michael Welzl’s book is an exception. It exposes congestion control in several facets, always succinctly explaining the principles and anticipating reader’s questions. Aimed mainly at starting PhD students and interested networking people outside the research community, it avoids formal mathematics and builds up the material through common sense. But it is far from trivial: the author provides a profound overview of the principles, problems and solutions and manages to cover a vast number of diverse topics, focusing on underlying principles, practicality, drawbacks. The author co-chairs the Internet Congestion Control Research Group and works at the University of Innsbruck in Austria.

Essential introduction into the problematics is developed in chapter 2, in which the less informed reader becomes familiar with the basic concepts such as control feedback, stability, queue management, scalability, incentives, fairness. Present technology is the topic of chapter 3, 70% of which takes a fairly detailed description of TCP. The exposition is incremental and problem-motivated. The rest of this chapter briefly describes SCTP, RED and ATM’s Available Bit Service.

The main value of the book I see in its latter part. Chapter 4 is an excellent exposition of very recent experimental enhancements to congestion control. Most of this chapter is dedicated to TCP enhancements and active queue management enhancements. About 10 recent queue management techniques are presented, including such specialities as RED with Preferential Dropping and Stochastic Fair BLUE. A view from the Internet provider’s side is briefly treated in chapter 5. The topics here share one property: they operate on a much larger timescale than those of other chapters. They include Traffic Engineering, MPLS and QoS architectures. Although the level of detail here is much lower than in other chapters, the chapter puts the others into a perspective. The last chapter makes for an exciting read: it presents a mixture of open problems waiting for the hungry PhD mind. It also contains the author’s personal view on the subject. It could be characterised as common-sense reflections of a well-informed pragmatic.

Two appendices conclude the book. Appendix A shows some practical teaching techniques, Appendix B introduces the workings of the IETF.

As great as the book seems, I spotted a few over-simplifications:
Section 2.17.3 describes the concept of proportional fairness. The author states here that the maximization of total utility maximises financial gain. I think this is quite misleading because the term financial gain remains undefined and it is not clear from the text where the revenue comes from. Even if the reader knew it is here meant to come from congestion prices, this would be still problematic. It is true that revenue is maximised if prices charged equal to the congestion prices corresponding to the utility maximisation, but congestion prices are typically not meant to generate revenue as they serve as a control mechanism.
Further the author states that the maximisation of utility functions can be seen as an “optimisation (linear programming)”. But only the constraints are linear and the objective function is non-linear, concave, hence the optimization problem is nonlinear.
In section 5.1 the author explains long-range dependence of Internet traffic. It is here stated that Poisson process’s distribution flattens out as the timescale grows. Surely it is meant that the autocorrelation function flattens out. (As opposed to that of self-similar Internet traffic.) [Update: See comments below by the book’s author. ]

A word of warning for PhD students
This book is a very good one but I think one should be cautious about using some of the open problems as a basis of one’s PhD. The problems border with engineering rather than research and in some colleges solving these problems cannot satisfy PhD requirements by definition. Ideally, solutions to these problems will come about as a byproduct of a more fundamental framework called the thesis. Perhaps these problems can motivate and trigger a PhD topic, but they should not constitute it.

Any alternative books out there?
A book treating congestion control in detail is The Mathematics of Internet Congestion Control by R. Srikant, 2004, Birkhäuser, but be aware: the exposition is quite straightforward and very formal. Another adept is High Performance TCP/IP Networking by M. Hassan and R. Jain, 2003, Prentice Hall, which is limited to TCP and focuses on performance evaluation.

In summary, the material in this unique book is excellently exposed, a good balance between depth and clarity is kept throughout and the book should be keenly received by its audience.

Deloitte’s Puzzling Prediction on Internet Congestion in 2007

Internet backbone is likely to run out of capacity in year 2007 is among the 2007 Telecommunications Predictions [1] brought by Deloitte Touche Tohmatsu, an analyst company, writes Greg Goth in this month’s IEEE Internet Computing magazine article “More Online Video Rekindles Network Capacity Debate” [2]. Greg Goth presents the findings of Deloitte Touche Tohmatsu concerning the growth of Internet traffic and the chances of running out of capacity. This is put in contrast to the opinions of 4 Internet insiders. They all happen to contradict Deloitte’s prediction. In this article we will try to find out who is closer to the truth.

Let’s quote here Deloitte’s key statements in [1]:

The Internet is often regarded as an infinite resource. Unfortunately, this is not the case; and in some parts of the world, its use may approach the total available capacity in 2007.

And in large print:

The unrelenting growth in Internet traffic during 2007 may overwhelm some of the Internet’s backbones: the terabit-capable pipes connecting continents.

Should this prediction be taken seriously?

I don’t think so, for 2 reasons. First, the Internet insiders questioned in Greg’s article all happen to oppose Deloitte in their predictions. Secondly, I find it hard to accept the validity of the main arguments the Deloitte group use to deduce their conclusion.

First let’s see who the 4 Internet insiders are and what they have to say about major backbones running out of capacity [2]:

Name	Role	Statement
Brian Washburn	Principal analyst at Current Analysis	Capacity scarcity is an issue of the core network, where it is easy to add capacity thanks to modern fibre optics. Internet would have to grow by several more orders of magnitude for optics to become outpaced.
Robert Rosenberg	President of telecommunications analysis firm Insight Research	There is huge capacity glut on the long haul.
Andrew Odlyzko	Former AT&T researcher, Director of Digital Technology Center, University of Minnesota	“Long-haul routes are in no danger of becoming swamped” and “There’s a huge deficiency in the final mile.”
Glen Russo	Vice president of wholesale markets for tier-1 carrier Level 3	No glut, but no shortage either.

All seem to contradict Deloitte’s findings.

But let us see how Deloitte arrived at its conclusion. In their report [1] we find they present 2 major arguments: the first is that the number of users will grow over 1 billion. But we do not get to read whether this is an exceptional surge or the usual rate of growth.

“The second, more important factor is video. Over a third of all Internet traffic in 2007 is expected to be in the form of mostly illegal, peer-to-peer video.”

But how does this relate to congestion? Presumably, illegal peer-to-peer video is not a real-time transmission, hence it will run at the same rate as the exchange of music files or text files. Of course, with the number of p2p users growing, the total bandwidth consumed grows, but that has little to do with p2p video.

The only concrete and numerical presented argument seems to be that

“The volume of traffic flowing over the world’s largest Internet hub, the Amsterdam Internet Exchange (AMS-IX), which carries approximately 20 percent of all Europe’s Internet traffic, grew at a compound monthly average of 7.4 percent in 2006.”

This indicates around 120 percent yearly growth of traffic amount in this case. If this information is correct then it conflicts with Odlyzko’s estimate [2] of 50 to 60 percent a year growth. Perhaps the growth of the Amsterdam hub is not representative (given it is the world’s busiest interchange) or it includes the effect of new providers joining the exchange as time passes.

Indeed, in a presentation by AMS-IX’s CTO Henk Steenman we find a slide showing an increase in number of members of about 50 per year. If so, then a traffic growth of 120 percent in the exchange does not translate into a 120 percent growth in link utilization, since it is going to be distributed over more links.

Besides, the growth of total traffic amount does not equal to the total growth of link load! Traffic amount is the number of bits carried in some long time interval (e.g., a day), whereas link load is the instant rate of packets. Deloitte worry about congestion on links using traffic amount growth as the main argument without saying how it translates to link load.

But let’s assume for a moment that the traffic amount growth corresponds also to the peak bit rate growth. This is unlikely, but it will give us the upper bound on how bit rate can grow. The following table then shows how the bit rate changes from year to year, given the claimed 7.4 percent monthly growth, 50 new members a year and the extreme assumption of peak bit rate growing at the rate of traffic amount growth.

Year	Number of members	Peak bit rate [Gbps]	Average rate per member [Gbps]
2006	250	140	140/250=0.56
2007	300	307 (120% growth from 140)	307/300=1.02

Hence we have (1.02-0.56)/0.56=82 percent increase in bit rate on average over all members. Note that this is an overestimation, because the growth of total amount of traffic does not have to mean an equivalent growth of peak bit rate. (It can mean that bandwidth is used more often at the same rate as before.)

In conclusion, I would say the only thing Deloitte got correct about traffic growth is that there will be some. But I cannot see how their arguments lead to the conclusion that it is likely that Internet backbone in year 2007 will become more congested than in other years.

Personally, I think the problem of congestion is much more tangible in smaller networks closer to the end–customer. Lack of accountability, frequent outages and underprovisioning give a real headache to the broadband user, who still cannot, in year 2007, choose between if only 2 classes of end-to-end service.

References

[1] Deloitte Touche Tohmatsu “Telecommunications Predictions, Technology, Media and Telecommunications Trends 2007”, 2007. Available on-line at http://www.deloitte.com/dtt/article/0,1002,cid%253D141454,00.html

[2] Goth, G. “More Online Video Rekindles Network Capacity Debate”, Internet Computing, IEEE, May-June 2007.

Jon Crowcroft on Opportunistic Networks and Human Mobility

Jon Crowcroft is a computer science researcher at the University of Cambridge. You can get a fairly good idea about his virtues and attitudes by reading through his webpage and papers, notably “Qos’s downfall: at the bottom, or not at all!” [1] and “Report from the Clean Slate Network Research post-SIGCOMM 2006 Workshop” [2]. Jon gave a talk last week at Imperial College, London, about a daring vision of a ubiquitous network formed by humans shown feasible by extensive, breath-taking experiments. In this article we will try to convey the key points of the talk.

All Together We Can Be One Big Mobile Ad-Hoc Wireless Network

The project Jon and his colleagues are working on concerns the delivery of data in a network with absolutely no infrastructure by making use of human mobility and local forwarding between wireless devices carried by people.

As Jon says:

[It’s about a] network that doesn’t have an end-to-end connectivity at any given moment, but you can construct a path by storing the data and then waiting a while, until things change and then forwarding them.

This can be also also expressed as a STORE – CARRY – FORWARD paradigm with the following meaning:

• “STORE” – in a portable devices we carry around (e.g a mobile phone)
• “CARRY” – carry the data in your device while you walk and travel around
• “FORWARD” – send data to another device on a short distance when appropriate using some wireless protocol (e.g. Bluetooth) and a forwarding protocol

Note that this idea falls into the area of “delay-tolerant networking” and “opportunistic communications”.

The rest of the talk aims at two fundamental questions:

• How does such network ever work?

and

• How to design a suitable forwarding protocol?

To answer the former question, we have to understand human mobility. Put simply – how many people we meet and what people they meet – parameters which allow us to estimate the chances that a message is delivered to its destination in a given time.

Adding Social Aspects to Human Mobility Modelling

As Jon notices, wireless networks have a dual nature – a physical one and a social one. Every person has multiple affiliations: few members of the family, colleagues at work, your friends who you meet occasionally, and, importantly, strangers who just happen to be in your proximity. It turns out that the social structures are vital to the feasibility of the network.

The iMote

(Picture is taken from “Pocket Switched Networks: Real-world mobility and its consequences for opportunistic forwarding” by Chaintreau, A., et al., available online at http://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-617.html)

To obtain some confidence in how a network described above would perform, an amazing experiment has been carried out. (See [3] for details.) A large group of people were given a small Bluetooth-enabled device called iMote (in the picture above), which they carried around for several days. All the iMote does is it records contacts with other iMotes (time and ID). By processing the data from the iMotes at the end of the experiment, authors could map them to the personal data of the participants (with their informed consent) which included their affiliations, social connections, and other elements pertaining to their life style.

It is a little bit hard to describe the results of the experiments concisely. But one thing is for sure: we are all connected pretty well. It is perfectly realistic to expect that a message from any sender reaches any destination. The property to optimise is the delivery time. Note that these results are conservative (i.e. they are likely to be better in real world) as they stem from experiments with much smaller number of participants compared to the real world where every one carries a wireless device.

The reader may be interested in learning that the social structure of the network can be characterised using the concept of community-cliques and centrality, and that the parameter crucial to the functionality of the opportunistic network is the inter-contact time defined as the time interval between two consecutive contacts between a pair. The experiments show that the inter-contact probability distribution is heavy-tailed and similar to the approximate power law shape. Quoting [3], “This is contrary to the exponential decay of many mobility models put forward in the literature. As a result, opportunistic networking algorithms which have been designed around exponential models must be re-evaluated in the light of our observations.”

Having obtained a solid confidence in the feasibility of such network from iMote experiments, the problem to tackle now is the design of a suitable forwarding protocol.

Designing a Forwarding Protocol

Imagine you are standing in a crowd, your next generation phone storing some data to be sent. A forwarding protocol will decide which device in your proximity will be used to propagate your data further. Note that there isn’t any holy grail in the search for a forwarding protocol and author do not claim the proposed protocol is optimal.

When routing a packet in a wired network, we choose the next hop according to some parameter describing the next hop (e.g. its distance from the destination). What are the key parameters describing a node (a person) in terms of its suitability as the next hop?

• Node’s popularity — how many other nodes it encounters
• Node’s affiliations — what social groups it encounters

The forwarding protocol can be based on these characteristics in a number of ways. Jon takes us through simple protocols such as the RANK protocol which forwards data to highly centric nodes (the guy on the corner selling peanuts would be an absolutely brilliant forwarding node) or the LABEL protocol which uses nodes with the same affiliation as the destination node, showing the probabilities of successful delivery as a function of delivery time. The BUBBLE protocol uses popularity to “bubble up” through different social groups until it finds a node with a good connection to the target group. Then it travels between social groups using nodes’ affiliation labels.

In all this Jon emphasises the need for modeling of heterogeneity at multiple levels. For example, a postman is a highly central node in the sense that he meets a lot of people, but not any particular social group, whereas a conference chair may be an asocial loner with high centrality in geeky circles. The BUBBLE protocol reflects this.

Issues, Bits & Pieces and a Conclusion

User privacy is a major concern here. Even though the forwarding protocol does not need concrete information about your affiliations, the idea that others might know about your social structure is disturbing. Another open issue is the way people would be motivated to participate in the network. A highly popular node will surely drain its battery sooner for example, and needs to be compensated for this. How to include incentives in the network? And, naturally, how to deal with malicious use?

Issues aside, we saw this exciting proposal of an opportunistic network shown feasible by extensive emulations. Reading through the paper Network Architecture Research Considerations Or The Internet Conspiracy at the online edition of the Computer Communication Review , you can notice that this project goes well in line with the philosophy of no-network-architecture-at-all.

But most importantly, this work presents, in my opinion, a great example of a bold, visionary and yet pragmatic research. If you are after fresh research ideas in the post-Internet era, keep your eyes on Crowcroft.

The presentation slides for the talk are now available here.

References

[1] Jon Crowcroft, Steven Hand, Richard Mortier, Timothy Roscoe, and Andrew Warfield “Qos’s downfall: at the bottom, or not at all!” In RIPQoS ’03: Proceedings of the ACM SIGCOMM workshop on Revisiting IP QoS, pages 109–114, New York, NY, USA, 2003. ACM Press.

[2] Crowcroft, J. and Key, P. 2007. “Report from the clean slate network research post-sigcomm 2006 workshop” SIGCOMM Comput. Commun. Rev. 37, 1 (Jan. 2007), 75-78. DOI=http://doi.acm.org/10.1145/1198255.1198268

[3] Chaintreau, A., Hui, P., Crowcroft, J., Diot, Ch., Gass, R., Scott, J. “Pocket Switched Networks: Real-world mobility and its consequences for opportunistic forwarding”. Technical Report, Number 617. ISSN 1476-2986. University of Cambridge Computer Laboratory, February 2005. Available online at http://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-617.html.

“How Fair Is Your Queue?” – Notes on talk by Prof. Levy

The task of inventing a good fairness metric for queues is a tough and important one. Such a metric would aid the design of wide range of systems, policies and applications including web servers, P2P applications, call centers, and others. In 2006, though, there still is not one single, widely accepted criterion.

In December 2006, Prof. Hanoch Levy from Tel Aviv University, Israel, gave a gripping talk on the topic of fairness in queues. The talk took place at Imperial College, London. In this article, based on Prof. Levy’s talk, we would like to draw the attention of networking researchers and system designers to this useful and practical topic.

What is queue fairness?

Before exposing the centrepiece of Prof. Levy’s talk, we should make clear what “queue fairness” actually is. Most researchers will be familiar with “flow fairness”. Flow fairness attempts to make flows (streams of packets) fair to each other. As an example, take “flow rate fairness”, which makes flows fair to each other in terms of their rates, or a “cost fairness” which makes flows fair with regard to the cost they incur. By contrast, “queue fairness” asks: How fair is the service received by a job (or a customer) in one queue?

As an example, consider the following scenario. A large job arrives at a queue first and a very short job arrives at a queue a bit later. Is it more fair to serve the first job or the short job first? That obviously depends on the type of service, context, culture, but in any case it would be useful to have a metric quantifying the fairness of the policy.

Why bother with queue fairness at all?

• The question is in fact redundant because the very purpose of queues is fairness! Queues, as opposed to crowds, appeal to our notion of fairness. Therefore, fairness is inherent part of queues.
• People do care about fairness. A company can get sued if a customer loses money due to being treated unfairly.
• In order to design a policy, we need a metric to evaluate it. However, there is no widely accepted metric for queue fairness as of yet.

The problem is, there is no established fairness criteria for jobs in a queue and it is difficult to devise one.

Resource Fairness: Solving the Seniority vs. Size Dilemma

At the heart of the difficulty lies the dilemma between seniority and size. Seniority refers to the time a customer spent in the queue waiting. Size refers to the service requirement, which is proportional to the size of the job. Previous proposals based themselves on either seniority [2] or size [3], which results in limited applicability and non-intuitive outcomes. For example, a seniority-based criteria ranks FCFS (First-Come-First-Serve) policy as the most fair policy and LCFS (Last-Come-First-Serve) as the most unfair policy, while a size-based criteria gives results exactly opposite.

In Prof. Levy’s talk, it was argued that a fairness measure should account for both. To this end, authors Raz, Levy and Avi-Itzhak in [1] focus on the server resources and how they are allocated to the jobs. Specifically, the fairness measure is based on the belief that “at every epoch all jobs present in the system deserve an equal share of the server’s attention” [1]. The accumulated deviations from the fair share over time define discrimination. And discrimination is then taken as the measure of unfairness.

Thanks to this definition, we can promptly obtain

• an individual measure of discrimination, defined as the expected discrimination experienced by a customer and conditioned on the number of customers the customer finds upon its arrival (This metric can take positive and negative values, corresponding to positive and negative discrimination, respectively), and
• a system measure of discrimination, defined as the variance of individual discrimination (Zero variance will signify a fair system as everyone is discriminated the same.)

Case analysis: Individual Discrimination in M/M/1 queue with FCFS policy

It is interesting to see how this measure quantifies different extreme situations in a M/M/1/K queue running a FCFS discipline.
Consider the following 4 cases:

Case	Customer finds	Fairness Criteria outcome
a)	Long queue in a lightly loaded system	Negative discrimination
b)	Long queue in a heavily loaded system	Zero discrimination
c)	Short queue in a lightly loaded system	Zero discrimination
d)	Short queue in a heavily loaded system	Positive discrimination

We see these results are in agreement with the feeling we would have in given situations. (Imagine queueing in a supermarket at busy/dead hour.)

What about system unfairness? It is shown that the proposed fairness metric consistently ranks unfairness of policies as follows (in a M/M/1/K queue):

Processor Sharing	is always fairer than	FCFS,
FCFS	is always fairer than	Random Order of Service,
Random Order of Service	is always fairer than	LCFS.

This orderliness is actually remarkable compared to single-metric based criteria.

The proposed fairness criterion is named “Resource Allocation Queuing Fairness Measure (RAQFM)”. That is because it is based on the amount of resources the queue grants to customers.

When to use which criteria?

Seniority-based fairness [2] should be used in cases when getting a job done is far more important than the waiting time. An example is queuing for a scarce service such as a limited number of bargain tickets. There being pushed away by 1 place makes all the difference to the customer.

Fairness based on service time [3] is suitable where resources consumed by the customers do not “run out” (e.g. a web server or a supermarket). An example is the Shortest Job First Policy.

Whenever there is a concern about both seniority and job size, resource-based fairness serves as a suitable measure.

Ideas for future work

Although the problem of queue fairness has been with us as long as queueing theory itself, the attention it has received from the research community has been quite modest. This leaves many interesting problems to explore. We list here a few:

• Suppose a system policy is designed that satisfies certain fair criteria including job size. How will this affect customers in their behaviour? Will they modify their job size and arrivals to improve their treatment?
• Would it be possible to say that simple policies such as FCFS have the advantage of offering less opportunities for customers to exploit the policy?
• Customers with larger jobs can generate more revenue and could be entitled to a priority treatment. How could revenue management be incorporated to the framework of queue fairness? (As heard in the after-presentation discussion.)

Bibliography

[1] Raz, D., Levy, H., Avi-Itzhak, B. “A Resource-Allocation Queueing Fairness Measure”. In ACM SIGMETRICS/Performance’04, June 2004.

[2] Avi-Itzhak, B., Levy, H. “On measuring fairness in queues”. Advances of Applied Probability, 36:3 (2004), pp. 919-936, 2004.

[3] Wierman, A.,Harchol-Balter, A. “Classifying scheduling policies with respect to unfairness in an M/GI/1”. In Proceedings of ACM Sigmetrics 2003 Conference on Measurement and Modeling of Computer Systems, San Diego, CA, June 2003.

PowerPoint presentation

If I get permission from Prof. Levy, I’ll post here the PowerPoint presentation used for the talk.

This is the PowerPoint presentation Prof. Levy used for his lecture at Imperial College:

PowerPoint presentation – Prof. Levy – Imperial College lecture

Dismantling a Religion: Is TCP wrong?

Fairness in communication networks is a topic of great interest. It has been treated in hundreds of papers and led to design of some of the most widely used protocols (e.g., TCP). But Bob Briscoe in his Internet Draft from October 2006 [1] argues that the fairness criteria used by the networking world today is fundamentally wrong.

Specifically, Briscoe

• Rejects flow rate fairness (widely accepted and used) as completely inappropriate, wrong & ignorant. This also applies to the TCP algorithm and fair queueing algorithms.
• Suggests that all proposals using flow rate fairness be discarded or someone should write a defence of flow rate fairness.
• Argues that weighted proportional fairness is a correct fairness criteria. It also notices that the paper introducing weighted proportional fairness rejected flow rate fairness, but the community did not notice.
• Proposes that weighted proportional fairness is implemented and deployed.
• Accuses the research community of creating a hegemony in this case and ignoring voices from outside.

To give a short introduction, let us say that fairness is a measure characterising division of resources among users. Once a fairness criteria is defined, a policy can be evaluated with respect to that criteria and policies can be designed which achieve fairness in terms of a given fairness criteria.

The most widely used fairness is based on bit rates of individual flows. It is called flow rate fairness and it attempts at making flows fair to each other in terms of their bit rates. An example of a flow rate fairness is max-min fairness. It is defined as an allocation of rates where no rate can be increased without decreasing some other, already lower, rate.

Flow Rate vs. Weighted Proportional Fairness

Most importantly, Briscoe says that flow rate fairness allocates a wrong measure among wrong entities, namely rate among flows, and that the right way to do it is to allocate cost among economic entities as it is done in Weighted Proportional Fairness proposal by Kelly [2].

Kelly’s paper [2] “struck an intellectual death blow” to the idea of flow rate fairness, but the dominant belief system did not notice, since cost fairness proposal stated its case in terms of the dominant belief system.

Dismantling the Flow Rate Fairness religion involves analysing 2 basic questions: what should be allocated (rates vs. cost) and among what (flows vs. economic entities) should that something be allocated. Following is the compilation of Briscoe’s arguments against Flow Rate Fairness and pro Cost Fairness.

1. What should be allocated? (Fairness of what?)
Regarding this question, Briscoe rejects fairness between flows and justifies cost fairness by arguing that:

• Arguments against fairness between flows:
  • Flow is not a good measure of either benefit or cost.
  • Equalising rates does not equalise benefits or cost.
  • “Fair allocation of rates isn’t based on any respected definition of fairness from philosophy or the social sciences.”
• Arguments for cost fairness:
  • Kelly showed that, using cost, each user will want their congestion algorithm to adjust its rate to maximise their net utility—benefit minus cost. Users will allocate themselves rates in proportion to the share of the cost that they cause – Weighted Proportional Fairness.
  • Cost fairness maximises total utility across the network.
  • “Cost in any part of the world has an exchange value with cost in any other part, because, wherever there’s an Internet attachment, ther’s a connection with the global economy.”

Further it is argued that it is not realistic to define fairness within the system (the Internet) without reference to fairness outside the system (society and market). But cost fairness naturally relates to monetary cost. And monetary cost allows to proceed with the concept “you get what you pay for” — a fairness concept we live in.

2. What entities should it be allocated among? (Fairness among what?)
Briscoe argues that fairness should be enforced among economic entities and not flows, as

• “There is no evidence that fairness between flows relates in any way to fairness between any real-world entities that one would expect to treat fairly, such as people or organisations.”
• Flow rate fairness is trivial to cheat by creating arbitrary number of smaller flows.
• “Fairness can only be meaningful between entities with real-world identities—humans, organisations, institutions, businesses.”
• Allocating resources among economic entities reflects the commercial reality and prevents multiple flows cheating.

Summary

I think Briscoe’s draft brings up a few extremely important points.

The accusation of research community creating a hegemony ignoring voices from outside is a serious one and I would encourage readers to express their views about this.

The lesson for beginning researchers is that one should question everything, even the seemingly fundamental truths in our field. If these are truths indeed, one gains a deeper understanding, if not, one gains a huge potential to publish.

I find a bit vague the statement that cost fairness would achieve outcomes “hopelessly unlike” the outcomes that result from flow rate fairness [1, p.3]. Although the intellectual superiority of Cost Fairness matters a great deal, maybe the practical difference would be negligible due to some large-scale effects, and thus not worth deployment. It would be nice to see a simulation illustrating the difference, but that does not have to be Briscoe’s job, of course. It is the networking research community who should react.

Unfortunately, the page dedicated to FAQ about this draft is empty as of this writing. A suitable place for a timely respond could be the online Computer Communication Review or this very journal (PaperPicker).

It is noteworthy that the draft was written with some help of such networking luminaries like Scott Shenker or Jon Crowcroft.

Bibliography

[1] B. Briscoe. Flow Rate Fairness: Dismantling a Religion. (Internet-Draft. Expires: April 18, 2007), October 2006. http://www.ietf.org/internet-drafts/draft-briscoe-tsvarea-fair-00.pdf.

[2] F. Kelly. Charging and Rate Control for Elastic Traffic. European Transactions on Telecommunications, 8(1):33-37, 1997. http://www.statslab.cam.ac.uk/~frank/elastic.html.

CoNEXT 2006 comes to an end

CoNEXT 2006 has come to an end. It was a great couple of days getting to speak to European and American Networking researchers, and I really enjoyed the experience!

I have recorded the talks of all the speakers (except for Matthias’ talk which was overwritten by the shoddy Thomson MP3 player they gave us). If anyone would like me to post any audio, or if any of the speakers would like a copy for improving their future presentations, just post a comment.

Also, my camera died on the first day of the conference so I don’t have any photos. If you attended the conference and have taken any pictures, please leave a comment or drop me a line at paperpicker@gmail.com.

I’m looking forward to CoNEXT 2007 in New York!

Cheers!

Michael Gellman

Powered by Qumana

Updated (4 March 2007):

Here we post few photos from CoNEXT 2006 kindly sent to us by Ana Rita Leitão.

10 tips to write a paper (from Jim Kurose)

The second event of the CoNEXT 2006 student workshop was a panel discussion entitled “How to write a paper” with Jim Kurose, Christophe Diot and Anja Feldmann. Each speaker offered different advice that is invaluable to anyone interested in writing quality papers.

Jim Kurose started the panel with a great selection of tips and advice on writing a quality paper. He’s posted his slides, and I’ve uploaded an audio recording of his talk, with highlights below. If you would like to post this audio somewhere on the web, you must get Jim’s permission first.

[odeo http://studio.odeo.com/audio/3672693%5D

10 tips to write a paper

Jim Kurose

1. Every paper tells a story. Know your story.

   Look at the story as an “elevator pitch” – it’s a summary that if you got into an elevator with someone, by the time that you got to the top of a 10-story building, you could tell them what your paper is about.A story is not what you did, but it is the new ideas and new insights that you have.

2. Write top-down

   State your broad themes first. Say what you are going to say before you say it.

3. Introduction: crucial, formulaic

   He has a full write-up on his website of the way an introduction should be structured, but it basically boils down to the following 5 paragraphs:

   1. Motivation: what is the problem, and why is it important?
   2. Narrow down the scope. Within this broad area, this is what I’m doing.
   3. This paragraph always starts “In this paper, we …” This is the most important paragraph in the entire paper. You have 10-15 lines of text to summarize your story, and it had better sound exciting.
   4. How different, better is your work compared to others’ work.
   5. The remainder of this paper is structured.

4. Master the basis of organized writing

   Know that a paragraph is an ordered set of topically related sentences, and should always starts with a lead sentence. Sentences and paragraphs should flow logically. Don’t mix tenses.

5. Put yourself in place of reader

   Don’t make the reader suffer — it should be a pleasant experience. It is easy to dump lots of thoughts on the page; what’s hard is crafting them into a story. Take the time to write less. Readers will not dig to get a story.

6. Put yourself in place of reader

   Signpost, give a road-map of where you’re going. Think about what the reader knows and doesn’t know; what they need and don’t need. You are writing for the reader, not for yourself.

   Try to use white-space, bulettedlists, figures, etc. to make your paper easier to read.

7. No one (not even your mother) is as interested in this topic as you

8. State results carefully

   Don’t overload the reader with 40 graphs. If you can’t use less than 40 graphs, something is wrong. Leave big proofs for the appendix and put a sketch in the main text.

   Try to give enough data for others to repeat your simulations, experiments, etc. Pay attention to the statistical properties of your results. Are they representative, or do they just represent some corner case?

9. Don’t overstate/understate your results

   Be careful to know under what conditions your results hold. If you are trying to draw conclusions about the Internet, do you have a large enough sample, from many different locations?

   If you say your results are small, interest will be small. Don’t fail to think about the broader interpretation of your results.

10. Study the art of writing

    Writing well give you an unfair advantage! It matters in getting your work published.Jim recommended 2 texts:

    • Elements of Style
    • Writing for Computer Science: The Art of Effective Communication

    In addition, Jim made an excellent suggestion to pick authors of papers that you like, and study what it is about their writing that makes it so good. He mentioned that he really likes the writing of Scott Shenker.

11. Good writing takes time

    Allow others to review your writing. Find a good editor friend. Don’t start the paper 3 days before the deadline while you are still trying to generate and understand results.

Alert readers will have noticed that 5 & 6 are the same, and there are actually 11 tips; such is the bounty of Jim’s knowledge and experience 🙂

For more resources, check out the writing portion of Jim’s website.

Powered by Qumana