Sally Floyd, Who Helped Things Run Smoothly Online, Dies At 69 (nytimes.com) 17
An anonymous Slashdot reader shares a report from The New York Times commemorating Sally Floyd, a computer scientist who recently passed away at the age of 69 from metastatic gall bladder cancer. "Dr. Floyd was best known as one of the inventors of Random Early Detection, or RED, an algorithm widely used in the internet," reports The New York Times. "Though not readily visible to internet users, it helps traffic on the network flow smoothly during periods of overload." From the report: The internet consists of a series of linked routers. When computers communicate with one another through the internet, they divide the information they intend to exchange into packets of data, which are sent to the network in a sequence. A router examines each packet it receives, then sends it on to its intended destination. But when routers receive more packets than they can handle immediately, they queue those packets in a holding area called a buffer, which can increase the delay in transmitting data. Moreover, the buffer has a limited capacity, so if the router continually receives traffic at a higher rate than it can forward, at some point it will discard incoming traffic. For all their ingenuity, the creators of the internet did not foresee some of the difficulties that arose as the network grew.
Well into the 1980s, the internet frequently experienced a period of huge degradation in performance known as a congestion collapse. Here the network's capacity was consumed by computers repeatedly transmitting packets, which routers were forced to discard because of overload. Dr. Floyd's Random Early Detection was an enhancement of work done in the 1980s byVan Jacobson, a computer scientist whose scheme for signaling computers to slow down is often credited with saving the internet from collapse in the '80s and '90s. Dr. Floyd and Dr. Jacobson developed RED together. "With RED, a router would generate a signal saying, 'I've got enough backlog that I'm going to tell senders I'm backed up,'" said Vern Paxson, a computer scientist at the University of California, Berkeley, who collaborated on research with Dr. Floyd. This meant that by discarding the occasional data packet earlier, routers could often avoid getting completely clogged.
Well into the 1980s, the internet frequently experienced a period of huge degradation in performance known as a congestion collapse. Here the network's capacity was consumed by computers repeatedly transmitting packets, which routers were forced to discard because of overload. Dr. Floyd's Random Early Detection was an enhancement of work done in the 1980s byVan Jacobson, a computer scientist whose scheme for signaling computers to slow down is often credited with saving the internet from collapse in the '80s and '90s. Dr. Floyd and Dr. Jacobson developed RED together. "With RED, a router would generate a signal saying, 'I've got enough backlog that I'm going to tell senders I'm backed up,'" said Vern Paxson, a computer scientist at the University of California, Berkeley, who collaborated on research with Dr. Floyd. This meant that by discarding the occasional data packet earlier, routers could often avoid getting completely clogged.
Shoulders of giants. (Score:1)
RIP.
Re:WTF (Score:5, Informative)
Re: (Score:2)
Re:WTF (Score:4, Interesting)
Anecdotes are not data. One counterexample does not make a general statement false. And finally, it was in the move from mainframes to microcomputers that the bro-culture of computers arose, during the 80s, and Sally was already well on her way through college at that time (she completed her PhD in '89).
Re: (Score:2)
Re: (Score:3)
And, in a related field, early video game programmers were men and women. Games back then were marketed as for families, not just for boys or girls. Then, there was a video game crash (after some truly horrible games were released by companies seeking money and not caring about quality). After that, Nintendo decided to release their NES in the toy aisle. Unfortunately, the toy aisles were divided between Boy Toys and Girl Toys. They needed to pick one and picked Boys. Their marketing reflected this and vide
Re: (Score:2)
Fascinating. I had no idea that's the history. I would love to read more about this era of video game development. Do you know of any good sources?
Re: (Score:2)
Here's an Internet pioneer who passed away and all you can think about is her gender. Nah, no bias among some nerds.
I'm wondering how the RED packet got through reliably - does this depend on an asymmetrically fully line? Packet prioritization? Did it just keep retrying?
Re: (Score:1)
It looks like instead of dropping the last packet once the buffer is full, it can randomly drop an incoming packet based on the size of the remaining buffer in the router.
Think of the old I love Lucy episode, instead of letting the chocolates fall off the end of the belt, they started pulling ones out randomly as the line became backed up.
Re:WTF (Score:5, Informative)
RED doesn't transmit control packets. It "signals" by dropping packets, and lets normal TCP mechanisms detect the packet drop and do their thing.
The point of RED is it drops the packet before it absolutely has to which gives TCP more time to figure out there is congestion before it sends even more packets down the wire making the situation worse. In other words, in addition to packets a normal queue would have dropped, it drops a randomly chosen batch of packets it could have delivered, but would have delivered with a lot of delay. This also spreads out the drops so multiple TCP sessions do not congest at the same time resulting in sawtoothing where all the sessions end up synchronizing and pulsing traffic at the same time, which counterintuitively leaves the congested path emptier than its full capacity yet still congested.
There are more advanced protocols these days like SFQ and some proprietary ones that get pretty deep into the packets to predict the backoff behaviors of even non-TCP traffic, but RED was the first widely implemented in routers, was very lightweight from a router CPU/memory resource perspective, and is definitely a historical landmark.
Re: (Score:2)
Yeah, RED was designed back when it was still the practice to expect adherence to standards and good behavior on the part of the endpoints. Bad actors is why SFQ or at least per-flow WRED is important these days, though sadly not as widely available as one might like. If you've got a moderate number of users and you aren't just throwing bandwidth at the problem and have cash, at least one proprietary packet shaper with DPI I know of can do even better than that (and also make it easy to see on which side
Ethernet (Score:4, Informative)
If this seems somehow counterintuitive, it's important to understand that Ethernet uses a method called CSMA/CD to figure out if it is okay to transmit a signal.
C = Carrier
S = Sense
M = Multiple
A = Access
---
C = Collision
D = Detection
So Ethernet first checks the "wire" for a signal (someone else is transmitting?) If it doesn't find anything then it tries to signal. If it happens to signal at the same time as another node on the wire, then it detects a collision and backs off a random amount of time before it tries again.
As an Ethernet pipe gets upwards of 70% saturated the whole thing starts to collapse because so many of the nodes are colliding and re-trying that your available bandwidth goes down the toilet.
On top of Ethernet we've layered on a ton of functionality (OSI layers 3-7) which allows us to do awesome things with Ethernet networks, but these don't "help" layers 1-2 (they are what they are).
As the summary states RED is a signalling method to let other nodes on the network know that a routing device is approaching a full buffer. This is required because (by definition) a routing device may have multiple networks and the one that the sending device is on and the destination network are not necessarily the same. So the sender doesn't know that the router's target network is overloaded (so it can't just check itself).
Hope this helps/makes sense. I'm not a network engineer but I play one on TV.
Re: (Score:1)
As an Ethernet pipe gets upwards of 70% saturated the whole thing starts to collapse because so many of the nodes are colliding and re-trying that your available bandwidth goes down the toilet.
Not sure if you were talking about the 80s, but today we have more than just hubs, we also have bridges/switches/(routers), which limit the collision domain to the two Ethernet endpoints, so generally the bandwidth lost due to CSMA/CD has been limited to the worse case CSMA/CD when N=2.
Re: (Score:2)
There is the prospect (and a patent application) of using phantom packets to trigger CSMA/CD for backpressure notification based on destination port queue length. Not sure how widely that ever caught on. Modern ethernet has pause frames etc but support for such standards can be less than universal, and they are all really hacks compared to an actual call-based protocol like ATM.
Respect to (Score:2)
Respect to all people who helped or help make the internet better and faster. Sad she left us so young.