Slashdot Mirror

Uh. The real problem is latency, not buffer size. Right? That's what people are complaining about - packets are taking longer than they should.

You propose solving the latency problem by reducing buffer size.

I propose solving the latency problem by reducing the maximum time packets are allowed to spend in a router (AKA latency).

Which do you think actually deals with the real issue? If the problem is latency, why not deal with it rather than go off on loosely related tangents?

BTW I finally read the article and seems what they propose is actually related to my suggestion - use time in queue. I think their approach might work - it definitely should work better than stuff like RED (which is stupid IMO).

FWIW I came up with my suggestion more than a year ago ( http://tech.slashdot.org/comments.pl?sid=1939940&cid=34793154 ) it was rather obvious to me - fix latency by dealing with latency. Well duh! I later commented on a related article that was linked to by Slashdot e.g. http://queue.acm.org/detail.cfm?id=2071893
Note: the article author(s) were still on the wrong track back then (still focusing on size of buffers). That's why I posted my post. Maybe they took the idea and ran with it. Or they came up with it by themselves.

That's why I think most patents nowadays are BS. It's easy for anyone reasonably bright to come up with very many different good[1] ideas. The trouble is implementing them and then pushing them to the market takes way longer. I'm not currently in the business of writing router software.

[1] Insanely great is a different matter ;).

Router buffers, and full routing buffers is a bad thing, they're talking about buffering your packets, not buffering the contents of your disk. Here, I found you a good article to read about bufferbloat http://queue.acm.org/detail.cfm?id=2209336

I am not an expert on container shipping, but this was one of the first things I thought to search for on Google:

https://dl.acm.org/citation.cfm?id=1954135

Here you have an algorithm for reducing the amount of work done at ports, which means less energy consumption or in other words less resource consumption. Assuming, of course, that it does not simply encourage more consumption for the same amount of resources.

The real problem that the world faces is not that technology is increasing resource consumption; technology is making things more efficient. The problem is that the demand for things keeps increasing as more and more countries join the high-tech revolution.

The ACM Queue did a bit on it last year.

http://queue.acm.org/detail.cfm?id=2071893

The acm did a great series on bufferbloat
http://queue.acm.org/detail.cfm?id=2071893 and http://www.bufferbloat.net/projects/bloat/

And here's the ACM citation.

Whenever I visit family in the US, I notice the latency seems to be much higher there. I wonder if some or all ISP's intentionally insert delays to pump up latency and make the speed feel really low,

There is a growing feeling that Internet routers are buffering too many packets when they really just should be dropping them (known as Bufferbloat). Packets should not be held at a router for more than a few miliseconds for processing. If they need to be held any longer, they should really just be dropped, and TCP congestion avoidance can then do its job by throttling down your connection.

High latency on single-hops (I'm assuming the company's test servers are a mere hop away), is almost certainly due to bufferbloat.

As someone said, latency comes from many things, but the biggest source of latency is buffering. When router buffers are oversized, the latency they introduce is disproportionately large. This has a negative effect on many things, including TCP thoughput during the slow start phase, which includes most HTTP transactions in the absence of pipelining.

Add the fact that you need three full round trips to establish a TCP connection (SYN, ACK, SYN-ACK) and you can see how 300ms latencies can be disastrous.

TCP was designed with the assumtion of an average 100ms roundtrip. Buffers ought to be sized to match that latency, by allocating enough buffering for 100ms or probably less of data at the link's maximum egress bandwidth. So, a 10Mbit connection ought to have 100kbit worth of buffering. However, routers are usually configured with bigger buffers. If you run ifconfig, you'll see your own computer's buffer is at 11Mbits (1000 packets of up to 1500 bytes each), 112 times that much, for a maximum latency of 1 full second.

To compensate, core routers have an algorithm called RED (Random Early Detection), that introduces packet loss way before the queue is full. Packet loss is what TCP uses to know the link is congested, and throttle back on transmission speed. However, with a overly large buffer, lots of users, poorly set up RED (RED requires complex configuration), it's quite possible your own computer, or your ISP's routers are creating a bigger than necessary latency.

Convincing them of the need to fix this situation will not be easy, though. But you probably should start by reducing your own computer's txqueue.

The PDF has more pixels: http://portal.acm.org/ft_gateway.cfm?id=2146416&type=pdf

A Tour through the Visualization Zoo

It seems to be more complete and more oriented to concepts instead of website examples. But may be a personal preference.

This isn't a new claim. See: Do We Need Inheritance? [PDF], Evolution of Object Behavior using Context Relations, Selective Open Recursion: Modular Reasoning about Components and Inheritance [PDF], Encapsulation and inheritance in object-oriented programming languages and many other academic sources.

It's widely acknowledge that inheritance violates encapsulation. It's a fundamental problem with OOP.

If you prefer a less academic and more practical discussion, try a Google search for OOP criticism.

Well, Tracje's thesis defence is next week; after that, it should appear online somewhere. I looked up the references in my copy, have a look:
Training students to steal: a practical assignment in computer security education (ACM, pdf also here or here).
Effectiveness of Physical, Social and Digital Mechanisms against Laptop Theft in Open Organizations (IEEE, pdf also here).

Fun! This 6502-assembler-in-LISP looks similar to Henry G. Baker's "COMFY" 6502 compiler (described in "The COMFY 6502 compiler", SIGPLAN Notices, 1997). You can check out the COMFY-6502 implementation that uses Common Lisp (sadly this appears to be entrapped in the ACM non-commercial-use-only license, though for 6502 code that isn't very limiting). One cool thing about the approach of using LISP as an "assembler" in general is that unlike many traditional macro assemblers, this approach can easily do stuff like choose the optimal instruction set for branches because it can determine if it's in range for a short branch and use them when available. You can do it other ways, of course, but it's pretty elegant in LISP. Those interested in this sort of thing might like my page on 6502 Language Implementation Approaches or my page on making LISP-based languages more readable (especially sweet-expressions).

A good citation on buffer bloat is Jim Getty's ACM Queue article on Buffer Bloat, in which he says:

Proper solutions for Web browsers can improve access-link behavior. These include HTTP/1.1 pipelining and Google's SPDY, both of which can achieve better performance, reduce the total number of packets and bytes transferred, and enable TCP to function better.

I've also spoken with Jim about this, and he definitely views SPDY as potentially part of the solution, not part of the problem. In fact, he was the person who first pointed out the existence of SPDY to me.

BTW: the reason SPDY does relative well with respect to bufferbloat is that it multiplexes a lot of traffic over a single TCP stream, and most lower level TCP software and hardware, including routers, tends to bound the number of packets they'll queue from a single stream. Trouble comes when the same application opens a ton of parallel streams, each of which gets to queue several packets; the result is that together they clog the buffers, add to latency, and prevent other application streams from progressing.

Sorry that it's behind a paywall, but here is my (peer-reviewed) take on it all http://dl.acm.org/citation.cfm?id=1368052&CFID=76329268&CFTOKEN=39574160

From the abstract:

This research returns to first principals, and considers the underlying Dexter Model of Hypertext, and how that may be placed within a broader model of document content that is amenable to adaptation of content to user needs either through configuration, or through dynamic self-adaptation. The model proposed considers a document in terms of five individual abstractions: content, inventory, semantics, navigation, and adaptation. A simple (fully working) example, taken from a small fragment of Google Maps, is presented to demonstrate how such a model may operate in practice, adapting between two different user profiles on demand.

Join the ACM.

This still comes on paper every month (plus a digital edition):

http://cacm.acm.org/

The articles cover a wide range of topics, including:

- Computing and society
- Legal issues
- New trends in computing
- Programming language geekery

Some of it may be too "niche" or "hardcore" (depending on your interests) but there's usually something for everybody in every issue. No, it won't be quite as task-specific as some of the mags out there (i.e., Not many articles with titles like "Turn up the Volume with LVM: twenty ways to crank up your hard drive!!") but excellent, nonetheless.

YMMV of course.

The theory isn't new, but a convincing implementation is.

Convincing to who? to you?

ACM was quite convinced back in 2000 when they published the paper.

They obviously implemented it because it contains a lot of measurements.

Convincing to browser developers, obviously, who moved to fix the other problems fairly quickly but have, to date, done nothing about this one.

And obviously, yes, they implemented a method for doing this back in 2000 for that paper. It's what's being referred to when the author notes, "Such attacks were historically regarded as fairly impractical, slow, and noisy - and perhaps more importantly, one-shot." What we have now, though, is a method that is fast, practical, and nondestructive.

The theory isn't new, but a convincing implementation is.

Convincing to who? to you?

ACM was quite convinced back in 2000 when they published the paper.

They obviously implemented it because it contains a lot of measurements.

Here's the ACM link I failed to post before.

http://dl.acm.org/citation.cfm?id=2046756

"..we describe a practical attack on XML Encryption, which allows to decrypt a ciphertext by sending related ciphertexts to a Web Service and evaluating the server response. We show that an adversary can decrypt a ciphertext by performing only 14 requests per plaintext byte on average."

Impressive!

Now if only the Association for Computing Machinery would get on board.

And don't bullshit yourself. Only one company used the word "multi-touch" before Apple did...Fingerworks. And apple bought them in 2005.

Such absolute bullshit. Not to mention all of panasonic's multitouch whiteboard products.

Skipping past all of the opinion pieces, I think that what jobs you choose don't necessarily destroy your future but they will definitely shape it. Regarding the whether or not IT and CS are actually different beasts I think that educationally they try very hard to differentiate between them and in the workforce there is a lot more hybridization that is going on according to the needs of the project/employer. They both fall under computing though. Here's a little something that you might find interesting on the differentiation. http://www.acm.org/education/curric_vols/CC2005-March06Final.pdf

I didn't read it in depth but what I remember from it was that it was a knee-of-the-curve result, not something where the paper authors thought there was 0 benefit to >32

Yes, that's what they argued, but frankly, it's not a valid result when gcc is your compiler. Wall wrote a very interesting paper on how to use 1000 registers. Compilers today don't even have to come close to any of the fancy tricks he talks about to suck up register resources. :)

but more importantly, it has implementation costs too. If you make a physical register file too large it will cease to perform like a register file.

We already have register files with hundreds of registers. They are used for O-O-O processing. They simply aren't ISA visible. Yes, there is a hardware limit, but even that is larger than people think it is. [Note: almost-shameless plug!] Techniques like register caching can be very effective, allowing very large register files with essentially the same performance as a small register file. Now, with every other architecture research study, take it with a very large grain of salt. But it is an interesting idea. It seems to me that ISA encoding is really the bigger problem.

There's also the concern of needing to save & restore too much state to make a context switch.

Yep, that is a big problem that most people ignore. There certainly is a balance to be struck. In many of the codes I see, 90% of the time is spent in inner loops with no calls, so this isn't generally a problem for those programs. OS effects are usually pretty minimal, but again that's HPC which is certainly quite different from a more general-purpose machine. As with any statement, evaluate it in the context provided. :)

Ah-- I see. I misunderstood what you meant when you said that "needing the right way to express them" is not the problem. I agree-- graphical programming languages don't really solve the problem. OTOH, when I was a teenager, my father worked on a project called Function Machines that, in my mind, deeply tied together the mathematical and programmatic concepts of functions. In Function Machines, functions looked like meat grinders, and, in some way, I've thought about functions as variations on meat grinders ever since. In my graduate computational complexity theory course, this once came out inadvertently, when I started talking about input to reduction functions being meat and the output being a trick played by the butcher. My classmates were like... "what the hell are you talking about?" ;)

The key thing to remember is that there are many ways to understand something-- everybody has to learn from what they already know. Some of us are fortunate to have technical people in our lives at an early age, and we are exposed to analytical ways of thinking. When we finally get our hands dirty with programming, it comes naturally. Other people have no basis for understanding, or even appreciating, that knowledge. Instilling the appreciation is the hardest part, but that's ultimately what will help them to succeed. Computer science can be incredibly challenging, and if you aren't internally-motivated, you're never going to learn it.

I highly suggest teaching in something like PHP. PHP gets knocked around by the intelligentsia, but the fact is that it is a simple, procedural, C-like language, largely without things like objects and functional idioms to get in the way. It has the ability to do indirection (references), so when people need to graduate to passing complex data structures around (and you should endeavor to get them to that point ASAP), they can do it. You can set them up centrally, but most of all, they can write cool programs that their friends can use, on the web and on their cellphones. And it is relevant. After that they can explore the wonders of Ruby and the mysteries of C on their own.

splitenz writes:

"Hoping to unify the growing but disparate market of NoSQL databases, the creators behind CouchDB and SQLite have introduced a new query language for the format, called UnQL (Unstructured Data Query Language — .PS). It has Microsoft's backing."

Then, FTA (right at the bottom of it):

This version of UnQL has no relation to an identically named unstructured data query language proposed by a University of Pennsylvania researcher over a decade ago, Phillips said.

I know it's slashdot, but c'mon. Just looking at the linked postscript file shows you a major WTF discrepancy. First the paper is from 2000, and then that paper's query language is based on algebras that do not resemble Codd's relational algebra at all. And that runs counter to this, also FTFA:

Like SQL, UnQL was built on the foundation of relational algebra, Phillips said.

The news are great. The coverage blows. It would pay to read the stuff that is being submitted as a story... just sayin...

I'm sorry... what? TFA has no content and UnQL is from 2000.

1983 http://portal.acm.org/citation.cfm?doid=800045.801573

1991 http://portal.acm.org/citation.cfm?doid=120782.120785

Apple invented multi-touch when?

Also this patent is not for the gesture language they use, it appears to be for ALL multi-touch interactions either "on the screen" or "near the screen".

1983 http://portal.acm.org/citation.cfm?doid=800045.801573

1991 http://portal.acm.org/citation.cfm?doid=120782.120785

Apple invented multi-touch when?

Also this patent is not for the gesture language they use, it appears to be for ALL multi-touch interactions either "on the screen" or "near the screen".

But still, there's heaps an application can do to reduce the number of memory pages that need to be read into ram at any point in time. If an application runs some kind of tree search, and each element it considers is on a separate memory page, then that will result in a lot more memory pages being read from disk. If, on the other hand, you optimise algorithms such that related data is located on the same memory pages, the number of hard faults can be drastically reduced.

The Gordon Bell Prize give at the Supercomputing Conference is effectively the yearly Nobel Prize for computing.

Wikipedia
http://en.wikipedia.org/wiki/Gordon_Bell_Prize

ACM website:
http://awards.acm.org/bell/

At the author of the article mentions, the ACM Alan M. Turing Award is the definitive award given out in the computer science community and is considered on par with the Nobel Prize. All the winners of the Turing Award have won the award based on work that has stood the test of time, typically on merit that was introduced 20+ years prior and still stands today as a fundamental and invaluable core contribution to the field. You will find contributions on computational theory, TCP/IP, programming language theory, HCI, cryptography, software engineer, and others.

Note, however, that the Turing Award does not cover IT or telecom.

Yes; this is follow-up work to the paper in that earlier article.

Also important to note, neither paper is specific to Skype; their work is on encrypted VoIP in general. But apparently /. prefers things having to do with Skype for some reason.

This is old news: It's already been monetized by Gordon Ross's company: http://www.biopassword.com/keystroke_dynamics_advantages.asp - I had a chance to use this system back in 2004 and it was pretty cool. When the system is learning your password initially, you type it a handful of times so that it can average times between keystrokes. You can type "normal" or you can type at an abnormal rhythm. Your choice. Here are some other papers published a long time ago... http://portal.acm.org/citation.cfm?id=581272 (2002) http://portal.acm.org/citation.cfm?id=266434 (1997)

This is old news: It's already been monetized by Gordon Ross's company: http://www.biopassword.com/keystroke_dynamics_advantages.asp - I had a chance to use this system back in 2004 and it was pretty cool. When the system is learning your password initially, you type it a handful of times so that it can average times between keystrokes. You can type "normal" or you can type at an abnormal rhythm. Your choice. Here are some other papers published a long time ago... http://portal.acm.org/citation.cfm?id=581272 (2002) http://portal.acm.org/citation.cfm?id=266434 (1997)

There should be a System Admin "Code of Ethics". The closest is the IEEE "Code of Ethics", or the ACM "Code of Conduct" if they happen to have joined.

The first is "bite sized", the second is probably more relevant but way more wordy, but how many people even bother joining either?

We are unorganized as a group at large, and the lack of standards to adhere to is part of the problem that we, as a Profession; including Admins, Programmers/Developers, Support Techs; need to address somehow.

(/rant) :)

computer professionals for social responsibility

cpsr.org

http://cpsr.org/issues/ethics/index.html

FTFY

That scratching sound is onda technology getting added to the "don't use" list all around the world.

+1 insightful

Wether he was right or wrong in being the only person with admin access, and wether that was a situation he created, or was thrust upon him, I am APPALLED by the fact that he attempted to hold the system for ransom.

There should be a System Admin "Code of Ethics". The closest is the IEEE "Code of Ethics", or the ACM "Code of Conduct" if they happen to have joined.

The first is "bite sized", the second is probably more relevant but way more wordy, but how many people even bother joining either?

We are unorganized as a group at large, and the lack of standards to adhere to is part of the problem that we, as a Profession; including Admins, Programmers/Developers, Support Techs; need to address somehow.

(/rant) :)

This was already well-researched in the HCI literature, starting with Olsen's groundbreaking paper on the DataNose around 1986, and extended significantly by Brad Meyers, et al., in their 1991 UIST paper on Nose Gesture Interfaces and Rhino-Virtual-Reality in General.

http://portal.acm.org/citation.cfm?id=120789

It would appear that content centric networking (CCN) can solve this problem. http://mags.acm.org/queue/200901/?pg=8#pg8

1. Get more people
2. Have them check each other's work

The second part relies on the independence of the people-- i.e., they are not colluding to distort your "computation". But crowdsourcing sites like MTurk and Slashdot effectively mitigate this by 1) having a large user base from which they 2) sample randomly. MTurk allows you to do crowdsourced checking of crowdsourced content by exposing the worker_id, so that you can exclude a worker who participated in one step from participating in another. Slashdot's moderation system requires that people can't post and moderate at the same time.

This paper coins the term "inter-annotator agreement" for this idea for NLP-type tasks. There are other papers, too, but I have to get back to work.

As someone who just finished writing a paper (minutes ago) for his graduate empirical methods course, I beg to differ. You can argue that too few CS papers which should be empirical actually are. Fair enough. But there are plenty of areas where good empirical research is being done. Any time the relationship between independent and dependent variables is not known, science is a good place to start. If you haven't come across one of these papers yet, I suggest that you are simply not reading the literature.

CS started as a branch of mathematics, and so there is a natural tendency not to be 'scientific' among many sub-disciplines, particularly in the more theoretical areas. E.g., theory often talks about computational complexity classes that aren't just feasible, they're impossible. But it is still useful to talk about them because it firmly establishes asymptotic bounds on the real stuff. The best CS papers are a kind of dialectic between these two worlds: reason about something deductively, and then use simulation or experimentation to validate your results. Repeat. This is the way physics has operated for nearly two centuries, and CS is finally coming along as well. Given the youth of CS as a field, and thus its relative immaturity, I think people have discovered some pretty amazing things using this method.

Here is an example of a good, empirical CS paper. Here is another really excellent one.

As someone who just finished writing a paper (minutes ago) for his graduate empirical methods course, I beg to differ. You can argue that too few CS papers which should be empirical actually are. Fair enough. But there are plenty of areas where good empirical research is being done. Any time the relationship between independent and dependent variables is not known, science is a good place to start. If you haven't come across one of these papers yet, I suggest that you are simply not reading the literature.

CS started as a branch of mathematics, and so there is a natural tendency not to be 'scientific' among many sub-disciplines, particularly in the more theoretical areas. E.g., theory often talks about computational complexity classes that aren't just feasible, they're impossible. But it is still useful to talk about them because it firmly establishes asymptotic bounds on the real stuff. The best CS papers are a kind of dialectic between these two worlds: reason about something deductively, and then use simulation or experimentation to validate your results. Repeat. This is the way physics has operated for nearly two centuries, and CS is finally coming along as well. Given the youth of CS as a field, and thus its relative immaturity, I think people have discovered some pretty amazing things using this method.

Here is an example of a good, empirical CS paper. Here is another really excellent one.

Guess your uncle doesn't know about ACM's Transactions on Mathematical Software. Hundreds of routines for all sorts of math. And it's mostly FORTRAN. Here's one for Delaunay Triangulation. Made in '96. Sadly, it's behind a pay wall.

Hacking up your own routine is all very well, and knowing how to do it is important. But actually doing it is a waste of time, unless you need the practice, or it's something real simple. Yes, some people will go hunting for a library routine to find the maximum of two values, or something else really basic. Or they'll write some serious overkill without realizing it, use a gigantic routine for something short and easy. A common one is to use a string append function complete with automatic dynamic allocation and reallocation of more memory, to build a string one character at a time. Talk about slow. But for the rest... You know, the old expression "reinventing the wheel". There's a huge difference in quality, too. Your hack job will have bugs both subtle and gross, and will be a minimal effort with minimal or no testing that barely does the job. The library code will have fewer bugs, and probably be able to handle more and weirder data, be more stable (numerical stability), and faster. The whole focus of most software engineering paradigms is "reuse"!

Some of the shortest path algorithms I've seen in commercial software is downright shameful. They aren't hard algorithms. Maybe a game designer can be excused for a crap pathing algorithm, but how about a map application? No excuse for that.

The extremest form of emphasis on OOP in teaching CS, objects-first, as seen, for example, in Kölling's Objects First with Java, has been heavily criticised lately in the computer science education community. One recent visible critique was Moti Ben-Ari's Objects Never? Well, Hardly Ever! (PDF, unofficial version to avoid ACM paywall), (paywalled official ACM version).

Similar things are happening at my own university, where objects-first has been seen as an important preparation for future programming work. The CS course for engineering majors who won't be doing any more programming switched from Java to Python and covering OOP briefly at the end of the course; the CS course for CS majors and others who will be studying more programming is due to do the same this autumn.

Here's the link to the citation describing Les Valiant's work: http://www.acm.org/news/featured/turing-award-2010

Turner Whitted An improved illumination model for shaded display Communications of the ACM, v.23 n.6, p.343-349, June 1980

More detail:
http://lists.ucc.gu.uwa.edu.au/pipermail/lore/2006-August/000040.html

http://www.merit.edu/mail.archives/nanog/1997-04/msg00340.html
http://www.merit.edu/mail.archives/nanog/1997-04/msg00444.html
http://portal.acm.org/citation.cfm?id=347428&dl=ACM&coll=

http://web.archive.org/web/20070328170121/http://www.riverstonenet.com/support/bgp/design/index.htm

Then how about this?

http://portal.acm.org/citation.cfm?id=1896663

Hah. I once found a very short piece of Postscript which ray-traced a reflective sphere on a chess board.

Sounds like the one published by the ACM here. A boggling 762 bytes of PS.

All experts in the field that I've spoken to think that P is probably not equal to NP, but that a proof either way is going to be very hard.

Since I'm interested in this particular field, allow me to point to a column that appeared in the ACM SIGACT News a couple of years ago, containing the results of an informal poll among mathematicians about their opinion on P=?NP and their estimates when this problem would be solved.

The majority of them (but not all) believe that indeed P!=NP; several also thought that P=NP, or that the question of whether P=NP was independent (of ZFC). A significant number also did not commit to an opinion either way.

There's a PDF available here, too.

-John