Centroid.EU Blog

Two algorithms for rate-limiting

October 17th, 2012

I thought of these myself last night, please provide comments if you have another idea.

2 rate limiting algorithms
--------------------------

Pretend you want to rate limit 3 packets per 6 seconds on the Internet.
I have thought of two ways to do this, one using 1 timestamp and a counter,
and the other using several timestamps and a counter which is more accurate.

First way
---------

When you have a packet arriving you take the timestamp of it.  For the next
six seconds you can take on 2 more packets.  Once the six seconds expired
you save the new timestamp and allow 3 more packets.  This has the drawback
that you can fire off a packet, wait 5 seconds and fire off 2 more, then when
the sixth second is passed you send off 3 more packets so in 7 seconds you can
fire off 6 packets which isn't exactly what the rate of packets per second
says.  However given 12 seconds it averages out because you wait 5 seconds from
those passed 7 seconds and don't allow anymore packets during that time.  Then
on the 13th second you can fire off 3 more packets.

Second way
----------

To alleviate the "burst" problem of above you can add more memory resources
and add more timestamps.  You allocate 3 timestamps for 3 packets per 6 seconds.
Then you make two counters.  One for the position of the last timestamp and
one for the amount of packets that passed.  So then when you start this
you send a packet and it saves the timestamp in timestamp[counter1] it then
increases counter1 and counter2.  Next packet comes in a second later, it
checks timestamp[counter1 - counter2] if it has been under 6 seconds then
add the timestamp to timestap[counter1] and increase both counter1 and
counter2. 5 seconds later another packet comes in, the first timestamp is now
"expired" and gets set to 0, also counter2 gets decreased by one.  This 
ensures that we know how many timestamps exist.  We then check 
timestamp[counter1 - counter2] and if the offset in time is under 6 seconds
then we add another timestamp in timestamp[counter1].  The tricky part is
to deal with wrap-arounds.  Ie. if you have 3 timestamps you can only fill
timestamp[0], timestamp[1], timestamp[2] before going back to timestamp[0],
which likely has been blanked otherwise the packet is dropped.

I invite you to provide clarifications and addendums,

-peter

:-)

0 comments

---

Seti@home has failed

October 13th, 2012

I got this in the mail the other day:

We need your help to continue the Search for Extraterrestrial Intelligence!

I guess the millions of people contributing computer cycles over the last 15 years is not enough anymore. Now the organization wants money. I think this is the wrong approach. Look, they got millions of people happily contributing on a client-server setup. Their servers are failing and they can't get more and they ask for money (which they likely won't get). It's time to make seti@home peer-to-peer. Figure out a way and people shall follow by installing the software. And the 'net will be better for it. That's my 2 cents.

0 comments

---

One computer per year

October 11th, 2012

I've done some planning and I've come to the conclusion that I need one more computer per year until 2016. See my computing history from april. Here is how I think it will go down:

1. in 2013, I'm going to buy Gaia a mac mini most likely, I need this for my new stand up table, I'll see if I can switch Saturn my netbook to OpenBSD then
2. in 2014, I'm going to retire mars (G4 Cube) and make Gaia its replacement, I'm also going to retire Jupiter which will be 4 years old and buy a replacement and call this Venus. Venus should have over 8 GB RAM but a power saving cpu.
3. in 2015, I'm likely going to need a laptop perhaps, I'll call this Mercury

This basically puts me on track since 2010 for 1 new computer per year, I think I'm crazy perhaps (well I knew that). Since electricity in Germany is going to get more expensive, it is good then that I retire Mars and I'm hoping for Gaia to be power saving (at max cpu 85 watts apple says, but no indicator of idle power). Also Jupiters replacement, Venus should be power saving this will save me a bundle of money. I'm considering putting 1500 euros per year aside for these "toys", and since I'm not married yet I don't have to worry about supporting the kids ;).

0 comments

---

My top 8 genres in my iTunes collection

October 5th, 2012

Here is who I threw money at in the last 10 years. Each song is about 99 cents worth. The way I did this was select all songs in itunes and pasted the titles in an editor file. This file I then uploaded to a Unix computer and did the following command.

# awk '{print $(NF - 1)}' music.txt| grep -v [0-9] | sort | uniq -c | sort -r | head -8
 125 Reggae
  33 Hip-Hop/Rap
  22 Filmmusik
  19 Weltmusik
  17 Rock
  11 Pop
   7 Sound
   7 R&B

However I get most other music from youtube, until I decide to give the artist a bit of money.

0 comments

---

The big smoggies...VPS's though?

October 2nd, 2012

Internet datacenters are big smoggies. Often servers sit there idling doing nothing but waiting to take over a redundancy task. I'd just like to say that my VPS network that I have created is on a X users shared basis, where more than one customer resides on a server. They each borrow from the other in terms of resources. And that's why I don't run permanent load on my vps's because it suits the other guy as well. And in the end we have more than just an idle server. We have a community on that server. And it's greener than me going out and putting up a colo or a "root server" (dedicated).

The new york times wrote about that all computers on the internet use up enough electricity for 30 nuclear power plants. Not all of that electricity comes from green electricity but carbon oxided emissions such as coal. The way we use the internet is not sustainable ... virtualization helps though if only a little.

0 comments

---

Bad Cryptography: a one time pad

October 1st, 2012

When I put my backups on the online storage I "encrypt" the file twice. Once with AES 256 in CBC mode and once with a one time pad that unfortunately repeats so it's supposedly insecure. I want to share this one time pad with you as it's derived from the one time pad at hackepedia.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define BLOCKSIZE       512

int
main(int argc, char *argv[])
{
 uint64_t count = 0;
 int keylen;
 char *key;
 u_char c[BLOCKSIZE];
 struct stat sb;
 char *ch;
 int fd, len, i;

 if (argc != 2) {
  fprintf(stderr, "must provide a keyfile\n");
  exit(1);
 }

 if (lstat(argv[1], &sb) < 0) {
        perror("lstat");
        exit(1);
 }

 fd = open(argv[1], O_RDONLY, 0);

 if (fd < 0) {
        perror("open");
        exit(1);
 }

 if ((ch = mmap(NULL, sb.st_size, PROT_READ, MAP_FILE|MAP_SHARED, fd, 0)) == MAP_FAILED) {
        perror("mmap");
        exit(1);
 }

 while ((len = read(STDIN_FILENO, c, sizeof(c))) > 0) {

        for (i = 0; i < len ; i++) {
                c[i] ^= ch[count % sb.st_size];
                count++;
        }

        write(STDOUT_FILENO, c, len);
 }

 munmap(ch, sb.st_size);
 close(fd);

 return 0;
}

When I back up then it looks something like this in a pipeline

tar -cf - /data | ./onetime onetimefile | openssl enc -e -aes-256-cbc -kfile kfile  \
| gzip -c | upload-program

I am gambling somewhat whether this is secure, but I'd feel a little naked with just an AES-CBC encryption.

0 comments

---

Purchased online-backup storage

September 30th, 2012

September seems to be a purchasing month for me. I have purchased 20 GB of online storage (at 1.49 euros per month) from strato.de. They are located in Berlin and I intend to use them as a temporary storage for my VPS.

On mondays I'll back up moon.virgostar.net, on wednesdays I'll back up goldflipper.net and on fridays I'll back up io.solarscale.de or something of this order. On the days inbetween those backups I'll download the images home on my harddrive. I think something of the order of 700 GB max will flow between me and this backup storage (per month). Should be worth it.

0 comments

---

Old --> New

September 23rd, 2012

I exchanged the first picture with the second picture in my private section of my webpage centroid.eu.

Even though I could lose a few lbs I think I'm still a pretty lad.

0 comments

---

This is how I left summer behind

September 23rd, 2012

On a ship, on the river Danube. Goodbye Summer! See you later! Hello Autumn!

0 comments

---

Privacy: they know who you are anyways

September 21st, 2012

Ever since I had a fire in my apartment building I've been couching at my parents house. I noticed that youtube and google know exactly who I am whenever I return to their site. Even the same banners over and over on slashdot revealed to me that they can track me. The big difference between my house and my parents house is that they have a dynamic IP address and I have a static IP. So what's the difference? With a static IP I even get to run a "server" doing my own mail and knowing that my mail isn't kept on some shady server somewhere, it's right at home instead. The privacy with a static IP is protected more I'd argue than with a dynamic IP. This surprises even me.

0 comments

---