Syntax and Semantic

Sharing the Network: From Circuit Switching to Packet Switching (The Hitchhiker's Guide to Computer Networks)

2020-10-08T11:55:00.002+02:00

Prelude ... From Circuit Switching to Packet Switching

The simplest approach for two people to communicate over long distances is to connect them through a dedicate physical wire. However, how would we scale that model to a million people that individually want to be able to communicate with everyone else? One approach is to extend wires between all pairs of users, requiring hundreds of billions of wires.

This is definitely not a good way to design a network. So what's wrong with that design? First, it is unlikely that every single person in that network will want to talk to everyone else at the same time. This means that we can use fewer wires. Second, not all connections are created equal. Longer wires cost a lot more money than short ones. Our design should have short wires whenever possible. Also it will be nice if the cost of extending long wires is shared between multiple users at the same time.

Let's revisit our connection strategy. Rather than extending wires between every pair of people, we can take their geographical distance into account. We can connect all users in a single geographical area (say a town or a neighborhood) to a communication "hub" through short wires. The "hub" can connect these users to each other through tiny wires within the hub. The number of tiny wires at the hub can be small and the hub can reconnect its set of tiny wires to connect people that need to communicate at the moment. A pair of users that are connected to the same "hub" can communicate with each other through a dedicated set of wires (their own wires connecting them to the hub and the tiny wire within the hub). This configured connection is called a circuit. The configuration of these circuits change depending on which pair of users want to communicate.

This is what a hub with tiny wires looked like back in the day. operators connect actual wires between the caller and the callee in the circuit board in front of them.

Hubs in a single geographically area (say a metro or a large city) can be connected through a large hub using the same ideas. We can then create huge hubs to connect different cities in the same state or county and mega hubs to connect states or even continents. If we want to make sure that everyone can communicate with everyone over dedicate wires, then the number of "wires" in a link will be equal to the number of users using one end of the hub multiplied by the number of users on the other end. Say if a million people on the east coast want to communicate with a million people on the west coast we will still need a trillion wires. Now we can leverage the fact that not all of users will communicate at the same time. Thus, we can have the number of wires connecting two hubs be equal to the maximum number of a pairs of users that want to communicate at the two ends of a hub.

The upside of circuit switching is that any pair of users get the full bandwidth of the dedicate circuit connecting them. They don't have to compete for bandwidth with anyone. This dedication of resources simplifies the network technologies significantly. However, there are several drawbacks of circuit switching. First, the cost of having dedicated wires is large, especially for "long wires". Second, configuring circuits on demand adds significant latency. The GIF above shows how operators used to configure the circuits manually. Even today automated circuit switching still adds significant latency.

Seems like this dedicated wire business is not working ...

What if multiple people can share the same wire? This is where packetization comes in.

Packet switching relies on breaking any data that a user sends into many small packets of data. Each packet specifies its source and destination. The network handles each packet individually, delivering it to its destination. If two users want to use the same wire, they can take turn each sending a single packet at a time. If the available bandwidth can allows the network to send both packets at "the same time", then the performance perceived by the user will not be different from circuit switching. However, when there is not enough bandwidth for packets from both users to be sent at the same time, then the network will have to hold the packets, put them in a queue, order them based on the importance of their users, and then send time one at a time. If users send much more packets than the network can handle, packets can face very long delays. This leads to one of the biggest challenges that result from resource sharing in computer networks: congestion.

In follow up posts, I will present how modern networks deal with packet queues.

Video on Demand: Part 1 (The Hitchhiker's Guide to Computer Networks)

2020-08-03T14:00:00.007+02:00

Data from the 2019 Global
Internet Phenomena Report

Video is the dominant type of traffic on the Internet. In 2019, video on demand constituted 60% of the total global Internet traffic. The image to the right shows the huge gap between the bandwidth demand of video streaming and the second highest application which is web traffic (think email, blogs, and news). This means that if you are in the computer networks business, you are pretty much in the business of video delivery. So the biggest question here, what is the best way to deliver video?

The "best" in this context can mean a couple of different things. It can mean delivering the best quality video for the user. Video quality does not only refer to whether a video is in HD or UHD but also whether it freezes and hangs or not. The "best" way to deliver video can also mean the most cost efficient way. If we can save 1% of the cost of delivering all videos on the Internet, we can save tens of millions of dollars in network operations costs. This post will explore some of the technologies used to deliver high quality video at low cost.

Before we go any further, I recommend that you do the following experiment: start watching any youtube video on your phone, then put your phone in airplane mode after the first 5 seconds of the video. The video will not immediately stop after the phone goes in airplane mode, rather, it will keep on playing for a few more seconds before it stops. The first question, with a somewhat obvious answer, is: Where did the extra few seconds of video come from if the phone was not connected to the Internet? Clearly, they were downloaded before you put your phone in airplane mode. This leads us to the following questions: Why does Youtube (or any other video streaming service for that matter) do this? How much video is downloaded and how is that determined? Have you ever been watching a video that switched between high quality and low quality, what's up with that?

Adaptive Bitrate (ABR) Video Streaming Algorithms

Videos are not stored as one lengthy file. Rather, videos are broken into small chunks that are downloaded in sequence as you watch the video. Each chunk has around 2-10 seconds of video. Each chunk is stored in different bitrates. Examples of bitrates include Standard Definition (SD), High Definition (HD), and Ultra High Definition (UHD). Chucks that get downloaded but are not yet watched are stored in a buffer (the gray line ahead of the red line in your Youtube play like the GIF above).

The time to download a chunk should be smaller than the time it takes to watch it. Otherwise, you will watch a chunk, and then wait a little bit until the next is downloaded. This is actually what happens when a video freezes and rebuffers (like the GIF above). Rebuffering literally means downloading a chunk into an empty buffer (refilling the buffer) because you watched all that was downloaded in the buffer. The higher the bitrate (the quality or definition) of a video, the longer it takes to download its chunks. This means that if your Internet speed is low, and you force the play to download high quality chunks, the player will have to do a lot of rebuffering.

ABR algorithms are part of the video player app on your phone or smart TV that decides how many chunks to download and the quality of each chunk. The "Adaptive" in ABR refers to choosing the bitrate of the downloaded chunks based on the Internet speed. If your Internet speed changes, say because someone else is watching another video, the adaptive algorithm reduces the bitrate of the downloaded chunks. It will also increase the bitrate when your Internet speed improves.

Researchers identified three video qualities that almost all modern ABR algorithms try to optimize: 1) The quality of the video (obviously) although if you are watching a video on a small screen you won't really notice the difference between HD and UHD. In other words, what the ABR algorithm will consider the best quality for a video depends on the size of the screen you are watching that video on. 2) The number of times the video rebuffers while you are watching. ABR algorithms will sacrifice quality to avoid rebuffering. 3) The ABR algorithm should start the video as soon as possible.

It is not trivial to balance all four factors: try to start the video as fast as possible by downloading the lowest bitrate and you risk shifting between bitrates too many times as you try to improve quality. Delay the start just a bit to download the best quality video and you risk it taking too long or the Internet changing midway and then you have to switch. Fill the buffer too much and you consume too much of the user's data plan, and fill it too little and you risk the video rebuffering. Most modern ABR algorithms find a good balance but there is still room for improvement.

The ABR algorithm measures your Internet speed, and based on that decides the highest video quality possible that will still avoid rebuffering. The image below shows that depending on the available bandwidth (Internet speed), the best bitrate changes. The ABR algorithm downloads a number of chunks to keep the video running even if your Internet is temporarily interrupted but not too much that will download parts of the video far ahead that you might not get to it. This is why when you put your phone in airplane mode, the video kept on going for a while.

Illustration of the most appropriate bitrate as the available bandwidth changes over time
(source of the images)

Developing new ABR algorithms remains an active area of research. ABR algorithms rely on knowing your Internet speed now and guessing what it is going to be like in the future (to download the right amount of chunks to avoid interruptions). Guessing what your Internet is going to be like is especially challenging when you are on the move and using your wireless data. There are a lot of factors that affect the Internet speed you get on your phone when you are using your data plan. Different ABR algorithms take different factors into account and adapt to them in different ways. My colleagues at MIT developed a machine learning-based ABR algorithm that uses deep learning to identify the best bitrate given a bunch of factors including the video, screen size, and network conditions.

Another interesting problem in ABR algorithms arises when we deal with 360 videos. Try playing the 360 video above, you can look around by moving your phone or just swiping on the video. When you are completely facing the sand, the video doesn't display the ocean facing parts. Should the part you are seeing (the sand) be viewed at the same quality as the part you are not seeing (the rest of the ocean)? Note that if you download them both at the same quality, that means you will be downloading a lot of large chunks and that can mean that the overall quality can be low. However, if you decide to download the parts that you are not viewing at a low quality, you can improve the quality of the parts you can actually see. Such decisions can be made based on the interesting part of the video and by modeling and predicting the motion of users through such videos.

In this post, I only cover the video streaming algorithm. There are other aspects of video on demand that are of interest from a networks point of view like where to store the videos and how multiple videos share the network. Such problems I will cover in follow up posts.

The Hitchhiker's Guide to Computer Networks

2020-07-18T01:15:00.132+02:00

Introduction

One of the few reliable things that didn't crumble under the pressure of quarantining and working from home is our digital infrastructure. It remains largely unaffected as we conduct most of our business activities online. This is no accident. It is the result of 40+ years of continuous research to make that infrastructure faster, cheaper, and more reliable. My goal writing this series is to shed some light on the different hidden aspects of our digital infrastructure. In doing so, I hope that I will help the reader get a behind the scene's view of what we take for granted when we are watching HD videos, buying our groceries online, and chatting online with people on the other side of the planet.

A typical Internet user pays for their Internet and online services (Netflix, Amazon Prime, Spotify, iCloud) with some expectations of the quality of experience they will receive. Users also expect that the way they interact with the digital world will keep improving. That's partly why they upgrade their phones, tablets, and laptops and buy new devices like smart assistants. In this series, I will discuss how different parts of the infrastructure work and how that affects such users. Specifically, I will be viewing the different challenges in making the Internet tick as one of three aspects of our everyday interaction with the digital world:

Quality of Experience: When we do anything online, we expect it to work right every time. This expectation of good quality of experience comes from the reliability and promise the infrastructure has consistently shown. But have you ever watched a video that keeps switching between standard definition to high definition only to end up freezing? Of course you have and that's what I refer to here as bad quality of experience. There are a lot of moving parts from your home network, to your Internet service provider, to your video service provider that have to work well together and separately to ensure that you have a good quality of experience online.

Flow of money: The network of connected people and corporations that form the Internet does not only capture the flow of information between them, it also captures the flow of money. You pay your Internet service providers, video service provider, music service, etc. Those service providers in turn pay other parts of the infrastructure like Internet Transit Providers (Internet service providers for the Internet service providers) and cloud services providers (the place where all your videos, pictures, music, and emails are stored and processed). This flow of money is at the center of a lot of how the infrastructure evolves, which can actually end up impacting your monthly Internet bill.

Gateways to the digital world: At the turn of the century, we interacted with the Internet primarily through text-based content viewed on big screens. Twenty years later, we are primarily interacting with it through video on small screens. This required an evolution in personal devices as well as the digital infrastructure (moving from carrying text to carrying 4K HD videos requires a 10,000 folds increase in capacity). The future promises even more developments where our interaction with the digital world is more seamless (think augmented reality and virtual reality with devices less bulky and awkward than the Oculus and Google glasses). Between us and that future there are some challenges that we need to overcome to make the devices more natural and infrastructure even faster.

In every post in this series, I answer three questions regarding each aspect of the infrastructure: What is it? Why should I care? And why haven't we solved all of its problems already? Hopefully, the answer to the first two questions will get the reader to ask the third question. In my answers to the third question, I will attempt to highlight some of the challenges we face with improving and understanding the infrastructure we have built.

Target audience: This series is developed specifically for non-technical people. It is not meant to provide a deep technical description of any particular area. I will avoid most technical terms and the alphabet soup that I think acts as a barrier to understanding the exciting hidden parts of our digital infrastructure.

Overview of our Digital Infrastructure

Before I start explaining different aspects of the foundation of our modern online lives, I will give a very brief and intentionally cartoonic view of the Internet today.

Map of Internet marine cables

When I refer to a network from now on, I refer to a set of connected devices that can communicate within a single infrastructure that is owned and operated by a single entity. For example, within your home network your phone, laptop, smart TV, digital assistant, and smart lights can all communicate through your home wireless router and they are all owned by you. Even when not connected to the Internet, this network can provide some useful functions carrying your data between devices. My wife and I exchange pictures that each of us took of our toddler every night. This exchange happens within our home network. Networks can be very large, spanning whole countries or even multiple continents. For instance, Google's private network carries data between four continents.

The Internet is a network of networks. This means that by definition the Internet is not owned or operated by any single entity. However, the definition also has a very important implication: all the networks that form the Internet have to agree on some set of primitives that allow them to interact without a glitch. This set of primitives has to be very small (so as to avoid imposing any strict limitations on the operator of any single network) but it also has to be expressive enough so that it can handle the diversity of the networks and their operators. This is no trivial matter. All companies in all countries that want to be part of the Internet have to agree on this (think the US, Russia, and China agreeing on and using the same "language"). This means that this "language" has to be expressive enough to allow all networks to interact but limited enough so that each company and country can still enact its own policies within its own network. The main primitive of the Internet, that everyone has to agree on, is that when a network is given a piece of data with a destination address, the network will "attempt" to deliver the data to its destination or forward it to another network that knows how to deliver it. In fact, network operators can choose to prioritize the delivery of data based on the source, destination, or nature of that data, dropping low priority data.

Not all networks are created equal. In fact, networks are typically created to serve a specific purpose (from the hardware they use to the language that hardware speaks). Your home router creates your home network. Your Internet Service Provider has a different set of devices forming its network. The purpose of the network of an Internet Service Provider is to connect residential and small business networks to the rest of the Internet. Transit providers are large networks that connect other big networks to each other. For instance, it can be that a Transit provider is what connects your Internet Service Provider (and consequently your home network) to Facebook's network. Modern online services (including Facebook) typically reside in datacenters. Datacenter networks carry data within a datacenter for processing (like facebook finding your face in a picture). The figure below shows how your home network is connected to the rest of the world through different types of networks.

A simple view of the modern digital infrastructure

Given this picture, think about the quality of experience you are having when watching a video. Specifically, if you are watching a Netflix video and it starts to freeze or switch between standard definition and high definition, whom should you blame? You should probably be able to tell now that the answer to this question is not so simple. It can be that your roommate is watching another video and that's causing glitches in your home network. It can also be that your Internet service provider is overloaded by customers and their network is glitching. The problem can also be in the Transit service provider connecting the datacenter that has your video and your Internet service provider. It can also be a problem with Amazon's datacenter network where most Netflix data is stored. Although in the specific case of Video, some of these scenarios are much more likely than others, depending on the online service you are using and the conditions of each of the networks, the likelihood of who's to blame changes. Also this should provide a clear reasoning for why each of these service providers would deploy their own optimizations in order to avoid any glitches with your video (each optimization is typically a different research question).

If you examine the picture above carefully, you will see that a single company can play multiple roles. This significantly affects the flow of money. For instance, Google can be your Internet provider through Google Fiber or Google Fi. It can also be your video and music provider through Youtube and Youtube Music. This means that a single company can be in control of your view of the Internet and the main beneficiary of your online activity. This evolution in roles happens at a fast pace and at various scales, leading to a very peculiar property for a completely artificial system: The Internet is so big and evolves so quickly that we don't fully understand some aspects of its behavior and how it impacts our own behavior as its users. There is a whole research area that tries to measure and understand the evolution and properties of the modern Internet.

About the Rest of the Series

In follow up (hopefully weekly and more realistically biweekly) posts, I will focus on a specific type of network or problems that is still facing the builders of our digital infrastructure. I will try to alternate between topics based on what aspect of our lives it touches (quality of experience, money, or gadgets). I hope that I will be able to cover the following list of topics:

Video: Being the dominant type of traffic on the Internet and the center of our lives in the quarantine, it seems like a good place to start. I will answer questions like: why does the quality of video change when the connection is not good? to why do live videos glitch more than recorded ones? I will also explore some of the frontiers in video streaming including streaming 360 HD videos and augmented reality.

Internet Architecture: This topic is concerned with defining the primitives that all networks that form the Internet have to agree on and how money flows (who pays whom). I will answer questions like: why is the Internet resilient and not easy to control? and how can freedom of speech be compromised on the Internet (despite its resilience and inherent support of freedom of speech)? I will also discuss some of the exciting recent attempts to make the evolution of the Internet easier without compromising its resilience and security.

Internet of Things: As processors become cheaper and smaller, we are able to stick them on any device and call it a smart device (smart light bulbs, smart microwaves, smart scales etc). The typical implication of such "smartness" is that it can be controlled from your phone from anywhere. This means that infrastructure has to support billions of connected devices. In covering this (maybe recurring) topic I will answer questions like: what are some of the new applications of the Internet of Things? why can't we just plug in all the new devices and make them work like my phone?

Congestion Control: I will tell you the story of the protocol that "saved the Internet" and how the Internet is "not quite saved" till this day.

Stay tuned for more posts and more topics to be covered in this series.

My PhD coping mechanism (or how speaking my mind out loud helps me maintain my sanity)

2018-05-01T21:47:00.000+02:00

Getting a PhD can easily become a lonely where students get depressed, feel out of place, thrown away alone with a mild to a sever sense of the imposter syndrome. There is no wonder that "graduate students are more than six times as likely to experience depression and anxiety as compared to the general population". Almost all my friends in graduate school face some sort of mental health struggle. This prompted me to write a post on my personal approach to dealing with my own issues and they all have to do with talking. Personally, I find it very hard to talk to strangers, so I focus all my talking to people I know. I talk to different people because defeating imposter syndrome, self doubt, angry thoughts, and most importantly the depression spiral requires multiple perspectives, especially with the highly logical PhD student.

Talking with advisors

One of the challenges of being a graduate student is feeling at loss when it comes to assessing my own progress, strengths, and weaknesses. I find myself feeling somewhat bothersome by asking too much from my advisors but I find that having different types of meetings to be very helpful:

Weekly progress meeting Those are backbone of the progress of a junior graduate student. In those meetings you brainstorm, get feedback on ideas, and present new results and approaches. Those are very useful and not having such regular meetings is a source of distress to many graduate students.

Periodic feedback meetings Personally, I like to get periodic feedback on my progress and methodology. This is not a common practice because some either prefer to get that from peers, or they are just not interested to hear someone saying what essentially is "you suck!". The way I see it is that I am always in need for improvement. I schedule a meeting per semester, usually towards the end of the semester, where I sit with my advisors and discuss what I did right and what I did wrong. These meetings have been very helpful in a period where all my papers were getting rejected but my advisors told me that this was just a part of the process and I needed to push through it.

Personal guidance meetings Many professors, at least at Georgia Tech, have an open door to all students. I use that a lot whenever I am stuck either personally and professionally. Rather than stumbling around trying to dig myself out of hole, I walk in and ask for help. This has been very helpful in identifying problems and solutions to many situations ranging from course choices, teaching style, advising junior students, and many more.

I have worked with multiple advisors and I know that in a lot of cases where it is not easy or even feasible to have all these types of meetings with the main advisor. Hence, finding other professors in the department that are willing to have such conversations is extremely important. Diversifying sources of input is important for personal growth as it provides multiple perspectives which helps a student to have a more complete picture. It also helps smooth harsh criticism and pinpoint sources of problems. This is an important approach to avoid falling into the spiral of depression caused by a single source of negative criticism, which also makes it hard to accept solutions provided by the same critic.

Talking with peers

I believe this to be one of the most helpful coping mechanism I have. My peers, specifically my lab mates and close friends, generously allow me to argue, brainstorm, and discuss my plans and vent about life and work. Having such open discussions in a lab stems from a non-competitive environment that our advisors create. These conversations also help maintain it that way.

In most cases, your peers are going through exactly what you are going through. You don't have to explain much and it is hard to be misunderstood, all without condescension. Views from my peers helped keep me out of some troublesome choices and allowed me to put bad events in perspective, like a bad review or a bad interview, and keep my self-confidence alive, even if barely.

Peers are different from advisors or mentors in one important aspect. Advisors and mentors tend to assume specific background, like events you have been through, topics you have read on, or people you must have met or read. This creates pressure in a conversation that was meant primarily for pressure relief. Peers, on the other hand, are going through what you are going through, more or less. They are also typically at a similar stage in life. This makes conversations easier and to the point.

Talking to myself

One of the most dangerous pitfalls of a graduate student's life is the tendency and the need to work solo for long periods of time, spending weeks at a time without speaking to anyone. These lonely periods, combined with any hints of depression, self doubt, and planning for the worst case, can lead to self-reinforced feeling that one is doomed. I find that talking to myself, sometimes even out loud, to be a very helpful way to counter this problem. These, typically one-sided, conversations help me keep my eyes on the ball during those long stretches of solitude.

There are two things that I find I need remind myself of: 1) things can work out and the average case is actually likely to happen, and 2) what I need to do to finish that stretch. This has worked many times to keep me focused and in kinda good mood about the potential average case. It also keeps ideas and problems that comes with thinking about the worst case in check.

Talking with my partner

If you are working over 12 hours a day with weekends counted as optional, this can put stress on any relationship outside the lab. I am married and one way my marriage helps me do better at work is that talking with my wife helps defuse me. Whether it is about work, our friends, house chores, or that restaurant that we *have to* try, setting aside my technical thoughts helps me shake the notion that work is all that there is to life. Remembering my "humanity" and sharing those experiences is an integral part of my day to day life and is a very important tool to keep me sane through a somewhat insane life style.

Keeping a relationship going under high work pressure is a topic for another post.

Talking with my parents

One of the harshest parts of being an international student is being away from one's family, especially if you are coming from a country where all families tend to live in the same city and see each other on weekly, if not daily, basis. Over the years I developed a routine of speaking on the phone with my parents on semi-daily basis to give myself a strong sense of connection to home for around 5 minutes a day. These brief conversations are a very important part of keeping any sense of home sickness at bay.

There are several other coping mechanisms including TV, video games, reading, socializing, and occasional running or playing squash.

The evolution of Internet routing

2018-04-03T22:48:00.000+02:00

If you ask "how do I get a video from Netflix to my TV screen?" you will probably get a variety of answers depending on whom you ask. Here are a TL;DR of the answers you are most likely to get:

the home setting answer "your access point gets the video from the Netflix over the Internet and sends it over wifi to your TV"
the smart apps and video encoding answer "the Netflix app creates an HTTP request specifying your account and some chunks of the video you are about to watch and the Netflix server replies with HTTP responses that contain the chunks"
the Internet Protocol (IP) answer "your smart TV creates packets addressed to the Netflix server by its IP address. Based on the IP address, the packets are first sent to the access point which sends it over fiber or telephone landlines to the Internet Service Provider (ISP), like AT&T, the ISP then sends it to other networks which eventually deliver it to Netflix (the ISP can also directly deliver it to Netflix). All this journey is guided by the IP address in the packets created by your TV"

In this blog post, I will focus on the third journey which is so revolutionary that it earned its creator (Vint Cerf) a Turing Award (Nobel Prize of computing). It is also so important to the core operation of the Internet that it is one of the very few things that survived from the inception of the Internet till now. It is also the only "agreement" all participating networks in the Internet has to agree on. The Border Gateway Protocol (BGP) has been at the heart of this consensus for almost 30 years. Like almost any other field, things that require consensus will stifle innovation.

BGP Basics

The Internet, as broadly known, is a network of networks. Each of those networks is called an Autonomous System (AS). All autonomous systems have to be registered (pretty much like all domain names have to be registered) and they have to speak to each other in BGP. In short, BGP is the main language of the Internet. With the rise of the web as the killer app of the Internet and the need for monetization of the networks, BGP became a language that expresses not only how data should flow over the Internet, but who has to pay whom to deliver it. At the time of the development of BGP, the Internet was pretty hierarchical as shown below

from wikipedia

Consumers, which can be home subscribers or web-based services, pay Tier 3 networks (ISPs) which pay Tier 2 and Tier 1 networks (ISPs of ISPs or transit networks) to move data for them. This hierarchy started to create a problem when latency became a main concern for web consumers over the past 15 years or so. Basically, your Netflix video has to travel through the Tier 3 connected to Netflix then up to a Tier 2 and then even to a Tier 1 before going down again to your Tier 3 and then to you.

This increased latency motivated content providers (e.g., Netflix) to create direct links with all Tier 3 networks who are willing to participate creating what is called "peering links" as shown below.

from drpeering

The current state of the Internet has Content Providers connected directly to ISPs through multiple connection points. BGP allows each party to specify their preference of which link to be used for every group of addresses through various ways which are configured in each router. This changed the Internet from a multi-hop network (in terms of Autonomous systems) into a single hop network [1][2]. This "single hop" architecture is much better in terms of latency from the perspective of consumer and in terms of cost from the perspective of content providers and ISPs.

The Problems with BGP

It is clear that BGP has taken us very far with simple language that everyone can agree on. However, BGP has problems that, due to its age, are very well documented and very well known. I will discuss some of the most prominent ones that motivate a need for the evolution.

BGP was developed for a relatively small Internet where routers can be configured by people with relative ease. The Internet has evolved and increased in scale orders of magnitude over compared to its younger self. This increase in scale makes the basic task of configuring BGP routers a problematic task that can cause misconfigurations and outages.
BGP failures can be expensive which requires robust hardware. Moreover, BGP routers require the moving of terabytes of data per second. These requirements translate into extremely high cost of routers that are relatively rigid and are not flexible enough to support the rapid change in requirements.
BGP is not very dynamic as it was developed primarily to connect autonomous system with little to no representation of dynamic load and preferences. However, current networks, where autonomous systems are connected to each other through multiple peer links, have dynamic requirements and require complex operations (e.g., load balancing).
Other notable problems include lack of control over end-to-end behavior, routing data based only on destination address without consideration of the source, and indirect expression of policies. For interested readers, check one of the following papers [3][4][5].

Because of these problems, BGP research has been long, innovative, but highly unsuccessful. One main source of the failure is the need for consensus requires that EVERY stakeholder to agree on the change which is highly problematic for many reasons including political and monetary reasons. However, there are some recent approaches that bypass the hurdles against BGP.

Innovations "beyond/around" BGP

To avoid the need for consensus content providers have been attempting to create solutions that allow for avoiding BGP problems while avoiding the need for consensus. The following are the most prominent approaches:

Creating a more compact Internet topology: This approach presents the simplest solution: To simplify the hierarchical tier-based topology of the Internet, lets move the content servers (e.g., Netflix servers) to the ISP. This solution requires coordination between ISPs and content providers, where content providers provide ISPs with hardware that they can place inside their networks. This approach bypasses BGP completely by having content move from content providers to consumers without leaving a single autonomous system. One of the prominent examples of such cooperation between ISPs and content providers is used by Netflix.

from presentation by flavio amaral from Netlfix

As shown in the picture above, the ISP includes the Netflix appliance in their network to serve data directly to users. The appliance periodically collects data from Netflix servers in the cloud and caches it locally. This solution is adopted by a wide variety of content providers (a very nice illustration of their infrastructure is provided by Google here). This approach is convenient despite having scalability problems. The main scalability problem is manifested by the impossibility of providing enough appliances to match the actual infrastructure of Netflix at every ISP. However, this solution was shown to provide good enough improvements in performance compared to traditional approaches.

Leveraging Software Defined Networks (SDNs): SDNs have allowed for rapid evolution of networks by moving the implementation of network rules from individual routers which work in a distributed way, to a central controller that configures all routers which in the case of SDN are simpler than the ordinary ones. This allows for easier configuration of networks and reduction of network cost. It also allows for better network telemetry and expression of policy which can be easily translated into network routing rules. This approach has been mapped to be used to control BGP routers by translating complex policies into BGP rules. Such approach has been used by Google and Facebook to control their peering links. A picture from Facebook's approach is below

from Facebook's engineering blog

As the picture shows, the network collects information about traffic load and possible routes to the same address. Then, based on that data, the controller creates route overrides which are then injected in the BGP peering router to modify BGP behavior. This allows the content providers to choose peering links based on their requirements overcoming some of the problems of the drawbacks of relying solely on BGP. However, several problems remain unsolved as the rest of the ASes still rely on BGP. Furthermore, solutions presented so far rely on the knowledge afforded by content providers only.

Conclusion

Internet is one the main drivers of innovation in this age, despite lack of innovation in the Internet's infrastructure. Some aspects of this infrastructure has seen some improvements in the past few yeats, but I believe that we are still a long way from an infrastructure that can support dynamic loads and policies that we currently need and will need more to drive more innovation.

Extending wpa_supplicant for kernel mac80211 control

2018-04-03T00:44:00.000+02:00

wpa_supplicant is a popular cross platform tool for wifi network configuration. On linux kernel, wpa_supplicant can use NetLink (nl80211) to pass commands and arguments to the configuration API of IEEE 802.11 (cfg80211). In this post, I will go through the different edits needed to pass arguments from userspace to mac80211 through wpa_supplicant. I will use my work on WiFi augmentation which allows wpa_supplicant to configure mac80211 to control its medium access control behavior.

wpa_supplicant has two main components: wpa_supplicant daemon and the wpa_cli client program. The edits I will present will be in both the daemon and the client. My edits assumes the existence of some functions in kernel that the user of wpa_supplicant is attempting to invoke.

The edit starts with the wpa_cli (client) code. The wpa_cli code maintains an array of all commands it can process mapped to callback functions that should be executed on the invocation of that command. The array can be found at wpa_supplicant/wpa_cli.c "const struct wpa_cli_cmd wpa_cli_commands":

The array element specifies the function to call which requires adding the function as specified below which is added to the same file:
The above function gets the parameters passed through the client and calls the wpa_cli_cmd or wpa_cli_commad functions (note that wpa_cli_cmd calls wpa_cli_commad) which are implemented to pass the arguments eventually to the wpa_supplicant_ctrl_iface_process function in wpa_supplicant/ctrl_iface.c file. The function is basically a bug switch statement that invoke different functions based on the command string passed through wpa_cli_cmd :
The handler function should be implemented in wpa_supplicant/wpa_supplicant.c and should look something like as follows that first obtains network information to select the network to control in kernel and calls the Station Management Entity (sme) function:
The sme function calls the driver function. The driver interface is implemented in wpa_supplicant/driver_i.h which requires extending the struct wpa_driver_ops structure to include the function corresponding to sample_change. The driver function creates an nl80211 message. I will cover the edits to the nl80211 driver and the nl80211 implementation in kernel in a following post.

On Proposing Research Ideas

2015-11-18T00:59:00.000+02:00

I spent the last month assisting my advisors on writing an NSF research proposal. It was one of my most exhausting and educational experiences ever.

It all happened slowly through some random tasks I got assigned. Some tasks seemed trivial and even useless at the time, but it all made sense when we worked on the complete proposal draft. It started with writing a "brain dump" of all ideas we have been iterating over the past 4-6 months. Then, it got interesting.

The Interesting Platform (Motivation, use cases, existing problems)
The brain dumb is often too technical as I spent time going through related work and defining interesting problems, what people are working on, and where I stand in all of that. This all does not cut it unless there is a clear use case. A scenario where all proposed research ideas are employed to make something "cool" happen.

The idea of how such use cases look like went through several phases:
1) When I started working on the project and I had a cool idea that I wanted to realize.
2) When I started digging deep into that cool idea to define how it is currently built.
3) When I surfaced back from the details to scratch parts of the use case already addressed by related work, ideas that are just way too complex, and ideas that are not really interesting. Then, I realized that the use case I had was no longer appealing
4) Finally, I was able to articulate a use case where novel research is required and where that research is applied to make cool things happen

One mistake I made was to think that by having that use case I had an interesting problem ...

The Challenge (why not "just" build it)
A very naive question when you present a use case is "why can't I just hire a bunch of engineers to develop this?". The answer to that question is basically what makes the use case an introduction to a good research statement. In this phase, I had to define what are the "clear" challenges in building a system that helps with the proposed use case.

In this phase, my advisors asked me to identify key points that I believe helped A LOT make the problem and why it is challenging much clearer in my head. These points included: identifying tradeoffs, identifying a baseline (some approach that is clear, easy, and works poorly), and metrics of success. Going through the exercise of coming up with these points helped me form a holistic set of challenges that need addressing for the use case to work.

So far, no specific research problems have been identified in the proposal ...

The Devil is in the Detail
A proposal should have clear tasks that, when executed, can make the presented use case a reality.

The identified challenges are appealing to motivate research in the direction of realizing the presented use case and the different applications that such use cases imply. However, challenges are not clear nor thorough enough to motivate an agency to fund a proposal. Moreover, the proposal has work that will typically take multiple years to realize. Hence, the exercise for this phase was to break down the identified challenges into different research problems.

I tried to break down a solution for the use case into layers and components. For each layer and component, I identified sub-components and challenges to be addressed to make each component and layer work. I also tried to make the different problems as generic as possible to avoid having dependencies between the appeal of the different problems.

I decided to go with the layered architecture as it better suited my problem. Within each layer I identified a set of challenges and possible approaches to solve it. From that point, more focus was dedicated to the related work of the individual problems and how we can solve them.

But this is just the proposal ...

No Devil will pay you for useless specifics
A lesson learned during the different phases of writing the proposal is that: a proposal should have enough details to show that the problem is interesting, we know what we are talking about, and that we have ideas to how to solve it. Yet, a proposal should avoid going into too much detail that the problem appear solved or that it's just wasting precious space in the proposal. There is also a fine line between being clear about what the problems of interest are and making them seem obvious and easy to solve.

But what will you do if you got the money tomorrow ...

Start Already!
This part is particularly tricky. In the proposal, there should be enough details to motivate every research problem without going too deep into mere conjectures. Yet, there should be a clear to do list for one or too tasks where it should be clear in the text that we are aware of how we are proceeding with them.

To that end, my advisors asked me to identify a set of tasks that I would work on if the fund was granted now. Having that in mind, writing about the tasks, the baselines, and the possible direction much more concrete than just suggestions and ideas.

But most of it are in reality just ideas ...

Papers v.s. Proposals
This is were the difference between writing a paper and writing a proposal is most clear. In a paper, you write to make what you did most clear and try to match your writing to your implementation and approach. In a proposal, the emphasis is more on clarity of the approach. In other words, the writing of the proposed approach can be simplified and tweaked to make it simpler.

Another distinction is that the idea of a paper can be very specific, guided based on related work, and "standalone". A proposal is a story with several interesting, and potentially standalone, problems that needs addressing to make that story a reality. Hence, you can think easily of an idea for a paper based on thorough knowledge of related work and the state-of-the-art, yet, a proposal requires more crafting, deeper understanding, and much grander story.

Final remarks:
In a typical proposal, you want to motivate the funding agency to give you, and you specifically, that money to solve that problem. This can, and should, be highlighted in many ways including:

Previous achievements and experience with related problems including publications and summary of findings.
Preliminary results pertaining to the proposed problem and initial findings on solving one of its subtasks.
Facilities available in your institution and any other enabling factors that make you standout.

DARPA Robotics Challenge

2015-06-08T02:33:00.000+02:00

DARPA Robotics Challenge Finals 2015 took place at Fairplex (Pomona, California). The event included an expo with tons of robotics shows and even some booths where you can play around with the robots. The competition took place on 4 tracks each with a replica of the challenge stage.

The tracks:

The winners:

Team KIAST making it look way too easy with Hubo

Running man, a robot with an attitude and a large cheering squad, walking on rubble for the win.

Chimp leaving at its own terms .. like a true champion.

Random moments:

The expo and the demos:

Attaching a WiFi Dongle to an AR Drone 2.0 (a.k.a. Compiling Drivers for ARM Based Devices)

2013-12-04T16:17:00.001+02:00

Correction (4/24/2014): for your driver to work the AR Drone 2.0 you have to compile the kernel version provided by Parrot which can be found here https://devzone.parrot.com/projects/show/oss-ardrone2

One of the down sides of "out of the box" AR Drone 2.0 is that you can't control multiple drones from the same machine. Another down side is that you can't attach USB devices except flash memories and some other predefined devices due to the limited nature of the busybox deployed on the drone. To over come the first down side without manipulating the WiFi configurations of the built-in WiFi card (i.e. you don't want to mess up your new drone), you will need to overcome the second problem (i.e. install a WiFi dongle and its driver manually). In this tutorial, I try to walk you through the steps to do just that.

I assume that you are working a Linux machine (seriously we are not going to compile drivers on Windows). Ubuntu is preferable !

Because the Drone has an ARM processor, we will need to compile the driver using an ARM compiler against a Linux kernel compiled for ARM. The first step would be to Install arm compiler

:~$ sudo apt-get install  gcc-arm-linux-gnueabi

Then you will need to get and compile a linux kernel with the same version as the one on the ARM machine. You can know that information using the uname command (in the case of AR Drone 2.0 that's 2.6.32).

:# uname -a
Linux uclibc 2.6.32.9-g4190abb #1 PREEMPT Fri Jul 20 14:10:11 CEST 2012 armv7l GNU/Linux

Notice the extraversion .9-g4190abb, we will need to edit the makefile of the kernel to match the extraversion. To actually get the kernel source code:

:~$ wget https://www.kernel.org/pub/linux/kernel/v2.5/linux-2.6.32.9.tar.bz2
:~$ tar xjvf linux-2.6.32.9.tar.bz2

Open the makefile and edit the "EXTRAVERSION" to whatever extraversion your ARM machine has. The next step will be to configure the kernel:

:~$ export ARCH=arm
:~$ export CROSS_COMPILE=arm-linux-gnueabi-

Then, for AR Drone 2.0, get the kernel.config file from here. Open the arch/asm/configs directory in the kernel and put the configuration file there and rename it to "ardroine_defconfig" and compile the kernel:

:~$ make ardrone_defconfig:~$ make

Now it's time to compile the driver. First, you will need to know which driver to get for the specific WiFi dongle you are using. To do that, connect the WiFi dongle to the AR Drone and telnet the drone:

:~$ telnet 192.168.1.1


:# lsusbBus 001 Device 002: ID 050d:1102 Belkin Components 
Bus 001 Device 001: ID 1d6b:0002

Search online for a driver that matches the vendor:id pair (050d:1102 in my case) which requires the RTL8188USC driver. After you download the driver's source code, edit its makefile to use

CROSS_COMPILE := arm-linux-gnueabi-
LINUX_SRC = location of kernel
LINUX_SRC_MODULE = (location of kernel)/drivers/net/wireless/

Then compile the driver which will produce a .ko file (e.g. 8192cu.ko). Copy that file to the ARM machine (in the Drone's case use FTP to copy the file to the drone) then navigate through the terminal to the file's location:

:~$ telnet 192.168.1.1
:~$ cd /data/video
:~$ insmod 8192cu.ko

If the dongle is plugged, unplug it then replug it and test whether it's working or not:

:~$ ifconfig -a

if a new interface is there, then congrats !!

Next Generation TV Ratings Systems

2013-07-15T03:06:00.000+02:00

TV ratings conventionally depend on focus groups and/or set top devices that keep track of the channels and shows viewed. This approach has been the main source of information for rating TV shows, sports, news, etc and it has been an integral part of the economics of the TV industry. But with the growing sources of viewing TV programmes either live (using TV sets or online streaming) or later (using video on demand either through set top devices or online portals) and with the growing number of TV viewers posting their opinions about what they are viewing, TV programmes rating is become a more challenging task that requires innovative solutions.

On the other hand, recently booming terms like "Connected Viewers" and "Two Screen Viewing" describe TV viewers that use their smart phones or tablets while watching TV. These smart devices forms a rich source of information on the TV viewing habits of the device's owners. This information can help both the TV industry and the TV viewers. On one side, the TV industry can definitely use information regarding the TV viewing habits streaming in live from millions of mobile devices. In addition to normal ratings information, this new source of information comes with detailed preferences list and characterization of each programme viewer. This new information can help make better ads and make more informed airtime assignments. Moreover, web-based and mobile based advertisers (e.g. Google) can have more information about the mobile device's owner which means more information for their ads engines. On the other hand, the mobile devices' owners can make use of social applications and recommendations that are based on their TV viewing habits.

At the Wireless Research Center @ E-JUST we realized the potential of building such an application. The application enables tracking a mobile device's owner TV habits need to work passively collecting information about each programme and any online activity made while watching that programme (similar to tracking web-browsing history). While the detection of the programme playing on a TV is a well addressed problem and available for free by applications like IntoNow. The problem at hand here is more complex as we cannot assume that the user will activate the application each time he/she is watching a TV.

In our work (accepted at Ubicomm'13) we aim at analyzing the acoustic fingerprint and visual fingerprints of a TV set in order to determine whether a device's owner is viewing a TV or not. Our preliminary results showed a huge potential in using these two sensors (i.e. microphone and camera) to perform the passive detection functionality, allowing applications like IntoNow to identify the programme playing afterwards.

Our novel stack of applications presents a new generation of audience measurement systems that can provide larger sets of more accurate and higher dimensional data about TV viewing. Also linking the TV viewing habits of a user to her viewing habits of online portals like youtube will give a clearer image of the popularity of TV programmes.

For more details check our technical report on arXiv: Mohamed Ibrahim, Ahmed Saeed, Moustafa Youssef, and Khaled A. Harras, "Unconventional TV Detection using Mobile Devices", arXiv:1306.0478.

Integrating Click Router and GNURadio

2013-03-26T11:45:00.000+02:00

Recently, I have been working on integrating Click Modular Router to work with both WiFi cards and USRPs to facilitate the development of cognitive radio testbeds. I am using GNURadio to control N210 USRPs. I found that developing routing hops to be interesting and worth sharing as it requires the USRP to simultaneously send and receive. This requires the transmission and reception to be on separated frequencies.

For transmission, first a client socket must be created in the click configuration code.

Socket(TCP, localhost, 4002, Client true)

Then, I used a thread to constantly listens on that socket and transmits the data once a new packet is received. This allows for the separation of tasks and good visibility of the transmission code. I noticed that there is a trend to include the transmission code within the main function which degrades the code readability. The thread takes as a parameter the top_block describing the data path on the USRP.

class tx_th (threading.Thread):
    def __init__(self,tb):
        threading.Thread.__init__(self)
        self.tb = tb
        self.tx_soc = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
        self.tx_soc.bind(('',4002))
        self.tx_soc.listen(1)
        self.tx_soc_client,addrr = self.tx_soc.accept()
        self.pktno = 0
        self.pkt_size = 1500

    def run(self):
        print "Thread Started ..."
    
        while True:
            try:
                data = self.tx_soc_client.recv(1024)
                if data:
                    control_flag = struct.unpack('i', data[0:4])
                    if control_flag == 0:
                        target_tx_freq = struct.unpack('i', data[4:8])
                        self.tb.source.u.set_center_freq(target_tx_freq, 0)
                    else:
                        data_to_be_sent = data[1:]
                        payload = struct.pack('!H', self.pktno & 0xffff) + data_to_be_sent
                        self.tb.txpath.send_pkt(payload, False)
                        self.pktno += 1
                        sys.stderr.write('.')
            except:
                print traceback.format_exc()
                t= 1

As for the reception, a server socket is created in the Click configuration file.

Socket(TCP, localhost, 4001, Client false)

And in the USRP control code, the rx_callback method is modified to be:

    def rx_callback(ok, payload):
        global n_rcvd, n_right, s

        (pktno,) = struct.unpack('!H', payload[0:2])    
        data_recv = payload[2:]

        if s is None:
   print "Data Socket Recv None"
   s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
   s.connect(("127.0.0.1",4001))
   s.send(data_recv)
        else:
   s.send(data_recv)

The assumption here is that each packet is annotated with its packet number (for debugging purposes).

Open Science - SFD 2011

2011-08-28T13:56:00.000+02:00

For the third year I was invited to give a talk at Software Freedom Day @ Alexandria University 2011 and I wanted to talk about something that links what I am doing now (I am a research assistant at E-JUST) and open source so I started researching Open Source Science.

Starting from the fact that I use a lot of open source modules and packages in my work developed by others and put on the internet for everyone to use. I began to understand the wider concept of open science which aims at enabling everyone who is willing to participate in any scientific endeavor to have a part in it.

Facilitated by the internet, ideas, tasks, documents, code, scientific data and even videos of experiments are shared by the project's coordinator for anyone to participate in anyway and every way possible. And the results are amazing !!

My main goal from the presentation and this post is to show how openness can boost research either by using the collective intelligence of all participants (as in the PolyMath project or InnoCentive) or reducing the time or the resources need as in science for citizens organization.

Other aspects of open science include making all the products of scientific projects available to the public for everyone to learn from and build on, saving money and time for other projects.

One of the best introduction you can have to open science is the presentation made by Michael Nielsen at TEDxWaterloo.

Also below is the presentation I gave at Software Freedom Day @ Alexandria University 2011.

Contributing to Open Source - SFD 2010

2010-08-25T16:55:00.000+02:00

Today I presented "Contributing to Open Source" as a part of Software Freedom Day @ Alexandria University 2010 held at Bibliotheca Alexandrina. The audience was great and helped in making the presentation better than I anticipated.

This is the presentation I hope it would be useful to those that missed the event.

Contributing to Open Source

View more presentations from Ahmed Saeed.

It was cool to be presenting at the BA for the first time.

Research Opportunities in Egypt

2010-08-02T13:32:00.000+03:00

Lately I have been exploring the research communities and opportunities in Egypt, specially Computer Science oriented research groups. I was amazed by the number of opportunities that are available now specially for a fresh graduate like myself.

I'll try to list some of the opportunities I have came across and that I consider tempting.

1. Cairo Microsoft Innovation Center (CMIC) :
One of the best research centers and it collaborates with a lot of the institutions that follows. There you'll get the chance to work with cutting edge technologies developing projects that will directly help the Arabic community.

2. Government Funded Research Projects:
Development funds like ITIDA, NTRA and STDF are providing support for research projects and IT projects on all level. It's quite interesting to be working on an independent research project that totally matches your interests with absolutely no restrictions and get payed.

3. E-JUST & Nile University:
Working on a research project at either of these universities will offer you the chance of working in an environment like no other. It tries to match the graduate studies experience in the US. Although there are some restrictions that you don't find in independent research project, you get to finish your master's degree at one of these institutions and get payed a better salary.

4. R&D Startups:
Recently R&D startups started to appear in Egypt. They offer a pretty intense experience offering the challenges and excitement that you'll find at any research project while focusing on specific targets, deadlines and specifications. Of course the salary is better than universities and independent research projects, but publications are not guaranteed.

5. Mubarak City for Science and Technology:
This one is pretty new to me. I have just learned about the options there. Some of them seems promising but the environment is awfully similar to those of public universities. Although the salary is a little bit higher than a typical Teaching Assistant position at any public university you'll end up getting you master's degree from a public university. There are specific tracks which doesn't provide a lot of flexibility but some of them are quite interesting.

6. Bibliotheca Alexandrina:
The BA has A LOT going on with different teams working on many interesting projects. They have a super computer (the only I know of in Egypt). Also their books digitization system is recognized as one of the best systems in the world. The salary is quite good but it's not easy either to get in or get out.

7. Masters Degree in Public Universities:
This is the last sanctuary to fresh graduates seeking research opportunities. The problem with this option is that any work requires commitment and this track doesn't include a payroll so you end up working at software house either part or full time. This degrades your efficiency greatly regarding time available to do the needed work or even studying the master's courses.

All the above statements are totally subjective and based on my own opinion and the opinions of anonymous people that had experience at each of those institutions.

A Research Graduation Project Accepted in PACT 2010

2010-07-22T13:10:00.001+03:00

I have been working throughout the past year on my graduation project. The main target of the project was accelerating a Numerical Weather Prediction model (the Weather Research and Forecasting model) using GPUs. We implemented the latest version of one of the modules and our implementation was published as part of the latest release of a system supported by the United States Air Force and the National Oceanic and Atmospheric Agency (NOAA).
After our thesis defense we decided to go on with this work and submit it as a research poster to a high ranking conference and we chose PACT. International Conference on Parallel Architectures and Compilation Techniques (PACT) is a top tier, rank 1 conference. We submitted our work as a research poster for the ACM Student Research Competition in the Undergraduate Category (I have already particpated at an ACM SRC at MobiCom'09 last summer).
I was informed on 22nd of July 2010 that our work "Quantifying the Impact of GPU Specific Optimizations: An Experimental Study on a Weather Forecasting Application" was accepted and the judges' comments were great. This is yet another proof that Egyptian Public Universities, with no fund whatsoever, can produce high quality research on the undergraduate level.

Waiting for your comments :).

CUDA compilation on Linux (Makefiles)

2010-05-09T15:04:00.002+03:00

I have been struggling with compiling complex CUDA code, with complex I mean a lot of .cu .F .cpp and .c files. I have created a makefile that can help you compile that kind of code. I'll try to give a quick view of it here explaining some parts:

First you'll need to specify the CUDA path and the compilers and linkers. Here I am using gcc and g++ for .c and .cpp files and nvcc for .cu files:


CUDA_INSTALL_PATH ?= /usr/local/cuda

CXX        := g++
CC         := gcc
LINK       := g++ -fPIC
NVCC  := nvcc -ccbin /usr/bin

Then you need to specify where to locate the CUDA header files :


# Includes
INCLUDES  = -I. -I$(CUDA_INSTALL_PATH)/include

# Common flags
COMMONFLAGS += $(INCLUDES)
NVCCFLAGS += $(COMMONFLAGS)
CXXFLAGS  += $(COMMONFLAGS)
CFLAGS    += $(COMMONFLAGS)

Then you specify where to locate the CUDA binaries for linking :


LIB_CUDA       := -L$(CUDA_INSTALL_PATH)/lib -lcudart

Then you specify the object files that the executable depends on and the name of the executable flle:


OBJS =  sample_cuda_objectfile.cu.o sample_cpp_objectfile.cpp.o
TARGET = exec
LINKLINE  = $(LINK) -o $(TARGET) $(OBJS) $(LIB_CUDA)

Finally you specify the compilation rules. The following are generic rules so all you need to do is change the OBJS and TARGET variables for compilation:


.SUFFIXES: .c .cpp .cu .o

%.c.o: %.c
 $(CC) $(CFLAGS) -c $<  -o $@

 %.cu.o: %.cu
 $(NVCC) $(NVCCFLAGS) -c $<  -o $@

%.cpp.o: %.cpp
 $(CXX) $(CXXFLAGS) -c $< -o $@

$(TARGET): $(OBJS) Makefile
 $(LINKLINE)

Contributing to Open Source (Why? and How?)

2010-05-04T12:52:00.000+03:00

Open Source products are everywhere now, probably now you're using some of them. And I am sure that a lot of people are appreciating the role of open source. This post is about giving back to the community, helping others and moving forward one of the applications/tools you're using as a part of your everyday life.

Why Contribute to Open Source??

Sun Microsystems had a slogan "Change (Y)our world". And that summarizes what contributing to open source is all about. It's about making You better and making The World better. Let's make it clearer.

When you contribute to open source it helps you in some many ways, it gets you to code and practice and enhance your programming skills. Then gets your code reviewed, reviewed and then reviewed once more before it becomes a part of an official release. And finally it gets you to document your code.
Of course how much a project adds to your skills depends on the scale of the project and the importance of the feature you're implementing.

On the other hand, when you contribute to open source you're giving back to the community, helping improve the project you're contributing to and hence making someone's life easier by introducing a feature or fixing a bug and your code is out there for people to learn for it.

How to Contribute to Open Source??

First, you'll have to choose a project.

Start small, choose small project with a small code base that you can get familiar with easily and you can get the people who wrote the code easily too.
Choose a project you use, so you can be able to know what it needs and have clear vision of what's used for, what type of users you're targeting and what's missing that you once needed.
Choose a project you like, and that way you'll be able to give it the time and get to have a reason to commit some time for developing, testing and documenting.

You can start by scanning active projects on sourceforge or github where you can find active small scale projects.

Second, start communicating with the development community.

Join the project's development mailing lists and start scanning the e-mails to sense the trends and topics of interest to the community currently.
Join the project's IRC channel and start asking the questions you have (search for answers on the mailing lists, wiki and blog posts before going to IRC so you get an answer).
Chekout the code and compile it.
Check the project's bug tracker and try fixing a bug or two before working on a feature.

Finally if you find that you can work on the project CHECK FEATURES LIST START CODING.

KNN Algorithm and KD-Trees

2010-03-31T00:19:00.001+02:00

I am taking a Pattern Recognition course this semester, it's not really one of my favourite topics but I am doing OK. We had an assignment last week to test and compare different classification algorithms. One of the algorithms we were asked to implement was KNN (K Nearest Neighbours). We were asked to find a way that makes searching for the K Nearest Neighbours faster; that's what this post about.

The problem briefly is that: Given two sets of K dimensional points find the N nearest points (using Euclidean distance or any other measurement) to a K dimensional point X.

The Naive Solution:
Go through the list, find the distance between X and all the points in the two sets, get the smallest N elements in the distances list... Simple enough.
As part of our assignment we were given a dataset of 100,000 points which proved this algorithm to be very slow.

My Naive WRONG Solution:
I thought that it was easy to index the points in a way that makes it efficient to find the nearest points to a given point. Multiple Dimensional Sorting... It was totally wrong because two points might have the same values of m dimensions but the values of the other (K-m) dimensions put them far away from each other.

Possible Indexing Solutions:
There are different ways to index K Dimensional Points based on how near they are to each other. I will mention here KD-Trees.

KD-Trees:
K dimensional trees is a binary tree that is based on space partitioning. It's used to index multi-dimensional data.

The idea behind it is using the tree to navigate through space partitions while decreasing the size of each partition as you go through the tree.
The figure represents a simple 3d-tree. The dimensions are X,Y and Z. Constructing such a tree is much similar to a conventional binary search tree but differs in only that splitting mechanism uses a different dimension at each level and keeps iterating on them in the same order.
The root point in the figure splits the space into two partitions X>5 and X<5. On the second level of the tree the X>5 partition is split into two partitions Y>3 and Y<3 and so on.

So as you can see by navigating through the tree you get a good approximation of the nearest points to the point you're searching for. But because the point you're searching for might be on the edge of one of the partitions a normal binary search will not always yield the correct the real nearest neighbour so re-checking is needed.

To do that re-checking the algorithm saves the point obtained by a normal binary search as the current best. Then it iterates on the nodes already visisted in the tree to check for two things:

If any of those nodes' distance is smaller than the current best.
If there exists a partition (branch) that might contain points with smaller distances. That's done by comparing the distance between the point we're searching for and the splitting point on the adjacent partition (the sibling of the node currently being examined) and the current best distance.

I have made a simple implementation of KD-Trees and a nearest neighbour search algorithm in matlab. You can find it here.

Weather Research and Forecasting Model Explained (Part 3) - System Architecture and Parallelism

2010-02-17T13:34:00.001+02:00

WRF ,as mentioned in part 1 and part2, is a system designed for both operational and research purposes, and to run on systems from conventional laptops to super computers. The design of such a versatile system is a real challenge.
In this post we will explore some of the WRF's Software Framework design and explain the functionality of the different layers of the system. Also we'll discuss how the system handles parallelism in different hardware environments.
Software Framework Architecture[1][2]:
(The following functionalities doesn't include parallelism handling)

Figure1: Hierarchical WRF Software Design

As it appears in Figure 1, the system design has 3 layers:

The Driver Layer:
It defines and allocates domains and associates them in a nest hierarchy. It also manages the flow of a system run as it's responsible for stepping the time for the loop mentioned in part1. And it's responsible for I/O operations.

The Mediation Layer:
It interfaces between the two other layers. For example the driver layer uses Fortran 90's derived data-types while the model layer deals with scalar arrays only. The mediation layer is responsible for dereferencing the scalar arrays from the derived data types.

The Model Layer:

It performs the actual weather prediction computations like physics calculations and time integration.

Parallelism (Two Level decomposition):

Due to the versatileness of the system mentioned before, parallel systems including shared memory and distributed memory architectures. Two level decomposition addresses that problem by decomposing domains in patches and decomposing patches into tiles. With patches being "a section of a model domain allocated to a single memory address space" and tiles being "the amount of a patch that is allocated to a one thread of execution and every cell of a patch that requires computation must fall into some tile"[2].
The driver layer is responsible for distributed and shared memory allocation. Also it handles the decomposition of domains into patches and patches into tiles. While the model layer handles only tiles. This part reflects one of the best design features of the WRF Software Framework; Model layer is meant to be programmed by meteorological scientists not computer scientists, so handling parallelism issues (i.e. synchronization, memory allocation, communication, etc) was made part of the driver layer leaving the model layer to have only "meteorological calculators"-tiles callable subroutines.

[1] John G. Michalakes, Michael McAtee and Jerry Wegiel, SOFTWARE INFRASTRUCTURE FOR THE WEATHER RESEARCH AND FORECAST MODEL
[2] Weather Research and Forecast Model 1.2: Software Design and Implementation

Weather Research and Forecasting Model Explained (Part 2) - Nesting and System Components

2010-02-12T20:37:00.007+02:00

In the part 1 we introduced WRF and discussed the meteorological basics of Advanced Research WRF. In this part we discuss the concept of nesting and explain different system parts of WRF. But first we'll define two basic terms.
Grid: Raw atmospheric data layed out as a discrete grid for an area of the map.

Figure 1 [1] Grid examples

Domian: A model created by processing grid information and making it ready for processing by WRF Model.
Nesting:
Nesting is a way of getting high resolution data from low resolution data.That's achieved by introducing more grid or grids to the initial state. Those finer grain grids force the need for more high resolution data. That data is obtained by interpolating data from coarse grain grids or could be user input.

Figure 2 [1] Nested grid

WRF System Components:

Figure3 [1] WRF system components

As it appears in figure 1, the system has 3 main components: Preprocessor (WPS), the WRF Model and Post Processor.

The WPS is responsible for preparing the input (initial conditions and lateral boundary conditions) to ARW for real-data simulations by [2]

Defining simulation domain and nested domains.
Computing latitude, longitude, map scale factors for every grid point
Interpolates time-invariant terrestrial data to simulation grids (e.g., terrain height and soil type)
Interpolates meteorological fields from another model onto simulation domains

The WRF Software Framework is the core engine of the system, it has the Dynamics solver, physics package and WRF-Chem and the interfacing between them. That core has all the equations mentioned in part 1.

The Post Processor, it processes the output of the WRF WRF Software Framework and converts it to GRIB format. For more information check [3] and [4].

[1] A Description of the Advanced Research WRF Version 3, http://www.mmm.ucar.edu/wrf/users/docs/arw_v3.pdf
[2] WPS Basics, http://www.mmm.ucar.edu/people/duda/files/wps_files/WPS-basics.pdf
[3] NCEP WRF Post Processor User Guide, http://www.emc.ncep.noaa.gov/mmb/papers/chuang/2/wrfpost.txt
[4] User's Guide for the NMM Core of the Weather Research and Forecast (WRF) Modeling System Version 3, Chapter 7: Post Processing Utilities.

Weather Research and Forecasting Model Explained (Part 1) - Weather Prediction Basics

2010-02-04T14:05:00.004+02:00

My goal here is to give a simple overview of the WRF for computer science students.
The Weather Resarch and Forecasting (WRF, pronounced "worf") model is an open-source numerical weather prediction (NWP) and atmospheric simulation system designed for both research and operational applications [1]. This system was developed as joint effort between National Center of Atmospheric Research, National Oceanic and Atmospheric Administration (NOAA), Air Force Weather Agency and others. In this post ,and the posts to follow, I'll try to explain the WRF from two different perspectives, the first being Meteorology and the second being Computer Science.
I am here concerned with the Advanced Research WRF (ARW) subset of WRF.
Weather Prediction Basics:
Weather Prediction means to predict the state of the atmosphere in terms of (pressure, temperature, speed of wind, etc). Our atmosphere is controlled by flow and the conditions of the air across the planet and by predicting that flow we can predict the weather conditions in the area of interest. The prediction is done by providing a system with information about the current state of the area of interest. Then the system uses that information as the parameters for its equations (usually difference equations) to produce future conditions for that area.
Euler's Equations:
Advanced Research WRF's dynamics engine integrates Euler's Equations to predict air flow.

Euler's equations are defined as a set of differential equations used in fluid dynamics to govern invscid flow (Wikipedia).

Being continuous equations, Euler's equations are discretized. Both temporal and spacial discretization are needed. So the surface of the earth is mapped as a grid ,based on the projection method used to project the spheric shape of earth, where all variable are defined on that grid.

Figure 1 Spacial discretization

(V,U,W are wind velocities, θ is the potential temperature)

For temporal discretization, the Euler's equations are integrated using a time-split integration scheme called Runge-Kutta method.

The following loop is used to integrate the equations and this loop is the main loop in the system (i.e. all other components are used to provide this loop with the information needed to compute the current time step)

Begin Time Step

Begin RK3 Loop: 

Solve the equations

End RK3 Loop

Compute non-RK3 physics 

End Time Step

Note: This is a very simple version of the loop for the complete version reference [1].

Initial and lateral boundary conditions:
For the system to be able to predict the weather for a certain area it doesn't only need its initial conditions but it also needs a way to know its boundary conditions as of course adjacent areas affect the area of interest. To solve this problem, several methods of generating lateral boundary data are used including periodic generating in which the lateral boundary conditions are repeated along the x-axis or y-axis or both.

[1] A Description of the Advanced Research WRF Version 3

Internet 4.0: Out of the Stone Age (Second Draft)

2009-11-05T18:46:00.000+02:00

(This is an enhanced version of the my earlier post with the results of your comments and my discussions with friends).
With the relatively rise of online social networks and it's uncontrolable availability to vulnerable users (children, teenager and even people with low or no technical background) exposed a huge privacy concerns for everyone. Your data that your putting on the internet are available one way or another to almost everyone. Along with web giants such as Google and Facebook keeping track of every click you make for either targeted services or anonymized purposes. And that made me ask one basic question:
Do they have the right to know all my internet behaviour ?
Lets first state some important definitions that we'll need.

My behaviour is what I the links I click on the internet to browse the web to check, read and edit free online content.
My service request is the link I click to ask some service provider to make something for me.

My main goal is to make my behaviour totally private (owned by me) and my services request authenticatable and both "anonyimizably" trackable (we don't won't google search to fail). So lets see how this can happen.
What I am proposing is an ID that's connected to the internet 24/7 where ever it is. This ID acts as a single point of access to your whole online life from your name, date of birth and picture to your browsing habits and computer and TV preferences to social security number and credit card number.
I guess such a device can have a lot of criticism so let's answer the ones I got so far one by one,
Browsing the Internet:
The major two issues that are of concern here are Behavioural data and Web Pages Personalization that is based on tracking such behavioural data. What's happening now that data about what EXACTLY I am doing on the internet is tracked one way or another by some service and if someone can put all this data together can know exactly my behaviour and use that data the way he wants or event sell it.
This data belongs to me so what I am suggesting here is that each individual behaviour data is processed online and the extracted information should be saved into his ID. That way as an internet baby with no data about you (no character built yet) your ID will start gaining some character using the data that's processed while you are surfing the internet.
As for personalization, a web advantage that we can't afford to lose, web sites can query you ID for the characteristics it's looking for. Standardizing those characteristics should help the spreading of those IDs and make using them easier.
Shopping Online:
This activity is one basic example of a service request. Those services will need some kind of authentication so that we won't have fake IDs and impersonations with identity theft issues. Other services that will need authentication are location and country based services.
Facilitating such service will make online identity theft a more difficult job for hackers as it for thieves that that are trying to break into a secured house without the proper keys.
The need for a centralized state:
The previous point exposed a very essential issue that such a system will need to gain the trust of the users and the services providers. Having a centralized trusted centre for issuing and maintaining those IDs linking them to their true owners where you can renew and update you basic information. Also where you can track people with criminal records, bank records and other official and important records. That way service providers will be able to trust ID owners if they checked with clean records from that central point.
There are two rules that such a central point should follow, the first is having only the data needed to authenticate incoming IDs, it shouldn't contain data about their behaviour or services request. Think about it in the way the government keep track of social security numbers and driving licenses.
The second rule is having really secured links between that central point and service providers. Strict laws should be made for the violation of the terms of use of such links.
Using Multiple Devices (Extending the idea, a little):
I can imagine such a person carring such an ID and setting in front of his TV and immediately loads his TiVo programs without a click on the remote. Then, he moves toward his computer and it welcomes him while opening his front page. Then while surfing all the websites pops data and advertisement that are meant only for that person. Other websites that he never visited before use the character he already created to help him have a more personalized experience, helping him save time and money by poping only stuff that it knows he'll need.
Also that ID can start processing the data it has to extract information that a single behaviour monitor wouldn't have figured out.
Implementation:
Implementations suggested in "Privacy, Cost, and Availability Tradeoffs in Decentralized OSNs" such as having machines on the clouds or personal computers should work fine. But what I can imagine is a device as small as a flash drive that is connected to the internet through WiMax coverage and with all you data on it. That device have WiFi and Bluetooth cards to help it connect with different devices and a small processor to interact with all that environment around it.
Conclusion:
This system tries to map the world we already live in to the online world. We managed to have a very private real world and with the help of new technologies we're making it more secured and more private and yet leaving our online identities totally exposed. This system will need a lot of work to even come near being a reality but the technology needed is already here, all we need is to realize the value of our privacy and being identified as a single person online.

Getting over stone age of the internet: discovering agriculture and building homes

2009-11-01T23:41:00.001+02:00

If you look at the current internet, giving its age and the type of problems it's facing, you can see clearly that we're still in the middle of, what I'd like to call it, the stone age of the internet.
We're talking about a technology that's only 30 years old, it has yet a lot of potentials to be discovered and drawbacks and problems to be solved. The problem I want to expose here is privacy. I'd like to compare the real stone age (5000 years B.C.) to the internet stone age (1985 to 2009).
The stone age:
During the stone age humans lived in the forests and took cover in caves from the rain, they lived in tribes that shared the same interest and cared for each other's interests. Communication between those tribes was almost impossible and they probably fought over everything (territory, food, women, etc). They slept right there in the open thinking that they are well protected that way. Invented some traps and protection systems to protect them and maybe considered those who got eaten by predators just flows in the protection system they had and they probably had their engineers work on that flow. By the end of the stone age humans made some of the most important discoveries in the history and those were agricultural and building homes. Sick of being exposed to all what nature had hidden for them, they built homes to protect themselves from the predators that intentionally meant to hurt them and other occasional incidents such as rain. Building homes close together they formed cities with a great building in the middle of the city forming the city hall. That city hall is were messengers from other cities went to communicate with that city.
The internet stone age:
I think by now the analogy should be a little bit clear. We're now creating profiles leaving them exposed one some public servers with some security and privacy measures that are broken and patched all the time. Leaving the data of our teenagers exposed to all kind of e-predators and think by having that easily breakable privacy measures we're doing our best. Also we're scattering our information amongst different social networks and services that can't really agree on a way to communicate and that most of the time are fighting over the money coming from the ads business.
We're basically making one "Ahmed Saeed" appear to be 5 different persons because he has 5 accounts on different social networks and services. And by that we're wasting the precious data that can be inferred by knowing that those 5 men are basically the same (Google is working on that but it's just another patch). On the other hand, this "Ahmed Saeed" is leaving his data out there for people he don't know to use in all sorts of ways.

I guess we're close to getting out of the internet stone age as the work suggested in "Privacy, Cost, and Availability Tradeoffs in Decentralized OSNs" published in Sigcomm's WOSN 2009 suggests what's near to discovering homes in the stone age. Probably over time we'll start building homes that are sustainable and reliable to provide us with the online cities we all dream of.

Trying to order the new Ubuntu CD and that's what I get

2009-11-01T00:47:00.000+02:00

Demand for Ubuntu CDs is very high, and we're trying to ensure that we have enough CDs for those who really need one. We've noticed that you've already received CDs of several previous Ubuntu releases. You can help us ensure the continued availability of Ubuntu CDs by

* upgrading to the new release without a CD
* downloading your own CD for free
* becoming an Ubuntu member by contributing to Ubuntu, and thereby becoming eligible for more CDs

Thanks for your support of Ubuntu!

I am sure they are trying to do there best but my point of view that people with longest history with Ubuntu are the best candidates to share the CDs with others. Maybe I am wrong but I just want a CD :(

Video Segmentation: Science fiction coming true

2009-10-25T21:16:00.001+02:00

First I'd like to define roughly what video segmentation is then talk about it in more technical details.
The term video segmentation is used with two applications in mind, the first making a long video short by extracting the key shots and images and puting them in a sequence summarizing the long video. So you can think of it as making movies trailers automatically.
The other is extracting the objects that were shot in a video and tracking them through a series of shots; in short making videos of the objects in one big video. So you can think of it as Arnold Schwarzenegger moving as the terminator identifying objects with his "eyes" and getting data about objects he's seeing.
Both problems are challenging and interesting but I'll focus more on the challenges faced when developing algorithms for the second definition.

If you used Photoshop ever then you must have done some image segmentation before. If you still don't know what I am talking about, remember the magic tool. Using that tool you can select objects in a certain image almost automatically. A lot of technquies have been developed for that problem and they are quite useful now. But lets think how complicated it can get with it turns into a moving objects.
A simple answer to the problem would be, video is just a series of images so we can just keep selecting the object in all of those frames.
Simply doing that will raise a question, how can you know that the object you're selecting now is the same object you selected in the previous frame?
Objects tend to move, backgrounds do the same thing and both tend to have at some points parts that make them look as if they were the same objects.
Also objects tend to intersect and hide behind one another making it look as if objects are disappearing.
Another important behaviour is that most objects change the way they look (think of a rubber ball).
With all of those consideration in mind, developing an algorithm that does object identification, object tracking and event detection becomes a very interesting and difficult task.
To wrap it up, I'll give a simple example which I guess must be using video or at least image segmentation. Digital Cameras, cool new digital cameras can detect faces and track them while them camera is moving. Just add some face recognition system and you got yourself a first component of terminator's system :D