<p>In the previous post I have had explained everything there is about using you own ONT. After some usages it seemed the combination of ONT module and EdgeRouter wasn't the perfect fit. The EdgeRouter's logs were filling up and every once in a while my whole network froze for several seconds.</p>
<h2>Background</h2>
<p>In my original post I explained allot of terminology about GPON, what it is. What you all need. etc. In this one, I will not. I will focus on what happened and what I tried and lastly, why I changed to make everything happy again. So for the full information, please also read <a href="/blog/2024-02-25-your-own-GPON-ONT-part-2">this blog post</a>.</p>
<p>First of, what happened? Well everything worked well for quite a while. But every so often my whole network froze, or at least my router did and thus al my network traffic. During the freeze it will not react to anything or route any traffic. After about 5 seconds it will unfreeze and continue if nothing ever happened. When inspecting the logs I noticed many messages like the once stated below.</p>
<pre><code>kernel: i2c-octeon 1180000001000.i2c: unhandled state: 0
kernel: Failed to read SFP EEPROM_0 at byte 29 val -5!!
</code></pre>
<p>After some investigation these messages started when I popped in the GPON module. I2C is a protocol which is commonly used over SFP to communicate with the EEPROM of these SFP modules. After allot of e-mailing between both Ubiquiti and fs-store I came to the conclusion that these the devices: The EdgeRouter-4 and GPON SFP module with MAC from FS.com, are incompatible. The module requires a I2C speed below 80KHz while the EdgeRouter's minimum is 100KHz.</p>
<h2>So now what</h2>
<p>I scoured the internet for alternative solutions. There where many. Initially I bought a UFiber instant module from Ubiquiti themselves. But I couldn't get it to work with my ISP even with a custom ROM flash. During this process I did find out that most of these "multi-propose" GPON module have the same PON SoC at their heart: the Realtek RTL960x. And from this family of products there where several options which were quite open and friendly to use to begin with. I poked around and talked to people from my ISP and in the end I landed on the ODI DFP-34X-2C2. You can find many of these sticks on aliexpress, I bought <a href="https://nl.aliexpress.com/item/1005003515456552.html?spm=a2g0o.order_list.order_list_main.11.21ef79d2wId0Gv&#x26;gatewayAdapt=glo2nld">this one</a> (watch out, the module is 48 euro's, you need to select your connection "color" first, I had an APC connection).</p>
<h2>Making it work</h2>
<p>Using the new module is actually quite easily. I did not load any custom software on it what so every. These modules all "expose" themselves via HTTP and SSH on a static IP: <code>192.168.1.1</code>. For me this is quite anoying, because my router's IP is <code>192.168.1.1</code>. To configure it I popped it into a switch, I put it into it's own untagged vlan along with another port which was connected to my laptop. I statically assigned my laptop <code>192.168.1.42</code> and I browsed to <code>http://192.168.1.1</code>. The module has a handy web interface from which I could assign an other IP, namely <code>192.168.20.2</code> and I could change the GPON SN of the module to my original GPON module's SN. This way I didn't have to contact my ISP and let them change the allowed GPON SN. You don't have to change your GPON SN if your provider allows you to run your own setup, you can email them the stated GPON SN and they will authorize you. If they don't... You can copy theirs instead... I also entered the LOID id and password from the old stick. I didn't think my provider uses it, but what does it matter. I  entered <code>1234567890</code> and <code>password01</code>. I popped it into my router and after a few minutes everything worked great!</p>
<h2>Accessing the module</h2>
<p>Unfortunately this module doesn't allow you to enter a gateway. So you cannot access it from another network. You can access it from your router so this gave me the following workaround. I assigned the interface which holds the GPON module the network <code>192.168.20.1/24</code>. Since my router has SSH I can SSH Tunnel a HTTP connection to the module using  <code>ssh -L 8080:192.168.20.2:80 192.168.1.1</code>. Now for as long as this ssh tunnel is open you can access the web panel of the module on <code>http://localhost:8080</code>.</p>


I ran into some issues with the combination of my GPON module and router. In this post I tell you what happened and how I resolved it.

Your own GPON ONT pt. 2

<p>Update: The module and router combi stated in this article don't interact that well. Please read my <a href="/blog/2024-02-25-your-own-GPON-ONT">followup</a> for an alternative module.</p>
<p>Some people just go out of there way to really own their internet service to the fullest. I am one of those people. I really dislike having gear from my internet service provider (ISP) at home. Especially because I know for a fact that my own gear is faster, more reliable, more configurable and cannot be screwed with by them. Now of course, this also means they cannot help me if I have internet issues. But honestly with my own gear, these incidents are few and far between.</p>
<h2>What are we working with</h2>
<p>I am using allot of ubiquiti's unifi gear, like the unifi AP's an switches. But for the routing I preferred the EdgeRouter-4, it is beefy enough, it has a SFP port and it s a bit cheaper (and allot smaller) than the USG 4 pro. And for a full sized managed switch I got a Cisco SG300-52 which I bought as a second hand cheaply. For this blog we would only need a router with an SFP slot, and the SFP module to put in it.</p>
<ul>
<li>EdgeRouter-4</li>
<li><a href="https://www.fs.com/de-en/products/133619.html">GPON SFP module with MAC</a></li>
</ul>
<p>Here in the Netherlands, it is a right to run your own networking gear. So they cannot disallow me for running my own gear, trying to fiddle with theirs, etc. The connection is on my premise, the gear is on my premise, thus I am allowed to use it however I want. Moreover in the Netherlands Fiber is quite common and, most often, more affordable than alternatives because of better competition. I got my own network setup already hooked up to an ISP (Tweak), but unfortunately, they have been bought by a bigger company, so I moved to another ISP named Jonaz. Sadly Jonaz uses GPON which requires other SFP modules than I am used to.</p>
<h2>GPON vs AON</h2>
<p>As I found out during this period, not all fibre networks are made the same. Besides the different fibre connectors and wave-length there  is also a difference between active (AON) and passive networks (PON). Passive networks need special protocols with authentications called GPON of XGS-PON used. In my case, Tweak used AON with LC as a connector. This was as as easy as buying the correct module from fs.com, plugging it in, assigning the provider's VLAN, and done.</p>
<p>My new provider (Jonaz) uses a PON network with SC as a connector and GPON as protocol. Initially these modules are already more expensive on fs.com. Moreover there are less total "options" to choose from but the terminology is really confusing.</p>
<h2>Choosing the "right" GPON SFP stick</h2>
<p>When you browse for GPON SFP sticks you will be hit with some weird terminology, lets go through most of them. First of, GPON has two sides to a connection, your provider, which is known as the OLT (optical line terminal) and the consuming side, known as ONU (optical network unit) or ONT (optical network terminal).</p>
<p>Next to this you have sticks with MAC and without MAC. This isn't referring to a MAC address (which I initially thought). But it refers to the capabilities of the stick itself. Sticks without a MAC need to be paired with gear specially designed to handle PON connections. All the packets send through PON network are special and they need to be handled and decoded as such. Sticks with MAC can do these things on the stick itself, basically it is a whole modem on a stick!</p>
<p>I didn't have special gear handling PON connections. I could buy a "Ubiquiti UFiber" instead. But I didn't wanted to add new gear. I wanted my fibre to go straight into my EdgeRouter 4. So I bought the <a href="https://www.fs.com/products/133619.html">GPON ONU Stick with MAC SFP</a>. Perfect.</p>
<h2>Getting the "right" Serial</h2>
<p>Most GPON ONU devices will have the serial used during GPON authentication on the stick or on the packaging. Unfortunately. fs.com , for unknown reasons, does not. Confusingly they add a serial number to the box, but that is the product serial number. Not the serial used during GPON authentication. If you have a PON capable device and added a stick you should be able to read the PON serial right from it. But as said before I did not have such gear. I bought a stick to handle that itself. So I needed to log into the module itself to retrieve (or set) it.</p>
<p>These SFP sticks come with their own mini server. You cannot do allot with it. By default when you plug it in it will use an IP of <code>192.168.1.10</code> and you can log into it using SSH. The challenge is how to do it from the EdgeRouter. If you already use the <code>192.168.1.0/24</code> network you will be in quite of a pickle. What I did was have a SFP capable switch in the target network (<code>192.168.1.0/24</code>), add the module to it, logged into the stick with the steps below and change the ip address. The commands for this are shown on <a href="https://hack-gpon.org/ont-fs-com-gpon-onu-stick-with-mac/#setting-management-ip">this website</a>. You should set the management IP to a network which you are not currently using.</p>
<p>Now plug it into your EdgeRouter, add a static IP to the SFP interface with the IP of the management IP's gateway the stick expects. By default it will be <code>192.168.1.1/24</code>. Wait a few seconds for it to fully boot. And now you can ssh into it from anywhere in your network. The stick uses some older SSH specs so we would need to enable some insecure algorithms.</p>
<pre><code>ssh -oHostKeyAlgorithms=+ssh-rsa -oKexAlgorithms=+diffie-hellman-group14-sha1 ONTUSER@192.168.1.10

password: 7sp!lwUBz1
</code></pre>
<p>Now we are in the stick and we can ask for it's GPON serial used during authentication with  <code>fw_printenv | grep nSerial</code>. This is the serial your ISP needs to talk with your stick.</p>
<h2>Would you recommend?</h2>
<p>Well, most of the time: NOOOO. Don't get me wrong, it works wonders. And it is doable and the SFP module is not that expensive. But if you are not fully experienced with networking gear and how to debug (common) problems with networks, it is hard to recommend.</p>
<p>There are no big benefits, but there is one big drawback. Your ISP will not be able to help you if you have problems. If you are unlucky they will not help you because you run your own gear. But most of the time, they won't be able to help because they don't have the tools they normally have. Normally ISP's have build in tool in their own gear to debug common problems. But without their gear in your network, they cannot use those, and thus they are blind.</p>
<p>But I am quite happy with it! There is one less (literal and figurative) black box from my ISP in my networking closet. I can inspect more about the PON connection when / if I need to. But other than that, no difference.</p>
<p>Hopefully this writeup was useful to some people.</p>


Running your own network setup can be fun. But this isn't always as straight forward as you might expect. Read more how to hook up the GPON network of your provider to your own gear.

Your own GPON ONT

<p>So I got in on the new hype nowadays: Statically generated websites with a JAMstack. My reason for it is twofold, I wanted to learn about this new hype. But more importantly, I didn't want to maintain my WordPress, I don't want to update it and it's plugins to keep it secure, I don't keep updating a template in order to keep my website viewable throughout updates and most importantly I don't want to receive emails because some Russians tried to log into my WordPress account or fear it got hacked because I didn't update it quickly enough.</p>
<h2>Static... what now?</h2>
<p>So first, a short introduction what this statically generated thing I am talking about?</p>
<p>With WordPress your content, your pages, blogs, menus, are stored in a database. For each page access WordPress will roughly do the following:</p>
<ol>
<li>Consult it's database and check what kind of page the user tries to access.</li>
<li>Fetches all the content from the database</li>
<li>Puts the content from the database in the template</li>
<li>Renders the page which the content</li>
<li>Serve the generated page to the user</li>
</ol>
<p>With statically generated websites step 1 trough 4 are done when you build the website, before you upload your website. Now your websites is just a bunch of HTML pages without the server needing to do anything for you, just like the old days. The benefits: Less dependencies on external parties, no need of a PHP capable web host, a website which is easy to cache and the best thing: it is fast as heck.</p>
<p>To be fair, blog type websites or just plain old websites do lent themselves very well for this thing. Every type of website where you don't need any input from the end user and  where you can have your content ready before-hand and this content isn't changed much. You can also make more complex sites static, for example webshops. It's just not so straight forward.</p>
<h2>This is the way</h2>
<p>So how did I did this, what did I use? And how did I like it.</p>
<h3>Content management</h3>
<p>So first things first, I wanted to have all my content available in my source control. I am an developer and I don't mind tinkering when I get full control. So I looked up a CMS which is git based and I ended up with Netlify CMS. Not the best choice I can make, now I require a netlify account and an Netlify identity. But their are upsides, I can edit my content without it, and switch it out when something better comes along.</p>
<h3>Static framework</h3>
<p>So we have some options, if you google 'static website generator' you got things to choose. I ended up with NuxtJS, which is based on VueJS, I really like VueJS. It is easy to get into, it has good documentation and a good ecosystem. It has a downside though, it is not as fast as others out there, you need to have knowledge about javascript and VueJS, although VueJS is easy enough to get into and lastly my biggest issue, the javascript ecosystem is really unstable and I still need to apply updates every week. Luckily even I know allot of javascript (I ended up using typescript, because why not?) and even if I don't update, my site is static, so no security issues there!</p>
<p>There even is a create template for NuxtJS and I got the basics up and running within half an hour. Whats more, I got some content loaded within have an hour. Amazing!</p>
<h3>TailwindCSS</h3>
<p>But... I got no styling, I could have used some front-end frameworks like Bootstrap or Bulma and purchase a template. But... I wanted full control and I wanted to learn something new, so I used TailwindCSS. I can recommend it is you want the freedom, you know some CSS and you go FULL rage when CSS promises you to do a thing while it obviously doesn't work for this specific instance. In my opinion, TailwincCSS makes CSS simpeler, but you still use CSS, thus it is not as easy as Bootstrap.</p>
<h2>The struggles</h2>
<p>So this is a more technical solution to WordPress, you still need to have some coding skills to do this. In my opinion with basic HTML and JS you will be fine. What's more, if you need more complex things, like tags on your blogs, you need to build it yourself. No easy plugins or database joins, at least I didn't find any.</p>
<h2>Final verdict</h2>
<p>To be totally honest, when I started I thought I wouldn't like the hassle and end up buying something like a squarespace account and be done with it. I just want a website to have a presence and to blog a bit.</p>
<p>But! It was way easier than I thought, and even though I don't like netlify CMS that much, I like the freedom that the whole stack brings me. I will switch CMS one day, or just inline edit in NuxtJS (because yes it can do that in dev mode).</p>
<p>All in all, a fun experience and this website is here to stay! 10/10 would statically generate it again</p>


My journey migrating from WordPress to a fully statistically generated with NuxtJS, TailwindCSS and Netlify CMS, aka a JAMstack.

Going static

<h2>Trees?</h2>
<p>But let’s begin at the beginning. Within computer science, a tree is a data structure containing nodes. Each node in the tree contain information and can refer to other nodes in the tree, these are known as children. Each node without child nodes is called a leaf node. When you draw this out with pen and paper and squeeze your eyes real close, you might see the tree-like structure in it (or you might need another beer).</p>
<h2>Soo B what?</h2>
<p>Some people might confuse a B tree with a binary tree and those people are not far off. Binary trees have one key value per node and have two children. When looking up a value you start traversing the tree, beginning with the first node (which is known as the root node). If the value is smaller than the key of the node you take the left child, if it is larger you take the right child. When the lookup value matches the key of the node, that is the node you were looking for. This way value lookups in a balanced tree are only O(log n). Of course this can be made so that each node has one or multiple data items per key value.</p>
<p>The B tree on the other hand has not one key value per node but a predefined amount of sorted key values, known as the bucket size. This means that it also references more children nodes, in fact each node references maximal its bucket size plus one child. This whole bucket thing will however increase the steps it would take to lookup a value in the most optimal situation. So why not just use a binary tree, since that is theoretically faster? Well, with a binary tree you need to jump around in memory and this comes at a great cost, which is why B trees tend to perform better.</p>
<p>Moreover when implementing a B tree which also writes its nodes to disk, you save a lot of disk IO by clustering the keys and nodes. Each node means potentially another disk operation and those tend to be one of the slowest types of operations. One might ask: “If disk operations are that slow, why not add all keys to a single sorted list and iterative lookup the value?”. First off good question, but this does mean that you potentially need to iterate the whole list to find a key value and on top of that it means that the whole list needs to be in memory and mutating a large list is quite expensive. So it is important that a good balance is chosen between between disk IO and operations. Common bucket sizes are 64 keys, but this may vary based on the memory and cache size of a system. Ideally you want a whole bucket to fit in your cache.</p>
<h2>There was a + right?</h2>
<p>So how does a B+ differ from a B tree? Well a B tree and binary tree have the values which correspond to the key value of the node in the node itself. B+ trees on the other hand store all the values in the leaf nodes. This has as benefit that deleting and inserting is a bit easier and on top of that, when the leaf nodes reference their neighboring leaf nodes, iterating over all values will be faster.</p>
<h2>Why?</h2>
<p>To understand why, let me give a little example. Given we have a document store, where we have n documents. These documents need to be stored and filed such that we can refer to a document by an identifier so that we have easy access to that document. In this example the identifier is our key and the document is our value, when we create a B+ tree of these documents we can delete, insert and find documents with relative ease. The problem using other structures as hashmaps is that these structures are not as dense as B+ trees. More over, dynamically growing hashmaps becomes quite expensive very fast and let’s not start about the trouble one will get into when trying to create a disk based hashmap.</p>
<h2>Advanced topics</h2>
<p>Now we know what a B+ tree is, let’s start looking into how lookups, inserts and deletions are performed.</p>
<h2>Key Selection</h2>
<p>The easiest of the three are the lookups. As mentioned before, in order to find a given key in a given B+ tree we need to traverse the tree starting with the root node. However when comparing the given lookup key with the keys in the bucket, when do we decide to go to the node of that key? Let me first note that there are multiple ways to do this, but I will explain and use the following rule. For every key in the bucket you compare it with the keys in the bucket and you choose the first node where the key in the bucket is bigger than the lookup key. When every key in the bucket is smaller than the lookup key, the last node is taken.</p>
<p>This is done recursively until a leaf node is found, where the data item belonging to the given lookup key is returned.</p>
<h2>Insertion</h2>
<p>The initial insert of a given data item and key is fairly easy. First the leaf node which will hold the key and data item must be found, this is done with the previously mentioned key selection algorithm. Next the key is inserted in the bucket at the appropriate place within the bucket. If the bucket is full after the insertion, the node is split where one node has the lower half and one node the upper half of the keys. Now the newly created node must be inserted in the parental node and if needed that node can be split as well.</p>
<h2>Deletion</h2>
<p>The hardest algorithm is deletion, in fact this is such a pain to implement that most B+ tree implementation use a small trick to do this. Upon deleting an item, mark the key as invalid and after a defined amount of deletions rebuild the complete tree from ground up. This seems insanely slow, but in fact the amortized complexity is the same.</p>
<h2>Bulk insert</h2>
<p>Building a complete B+ tree given a sorted set of key-value pairs is quite simple to do. Start by dividing the sorted key value pairs in parts such that each part fills a bucket, but leave one space empty for a future insert. Create leaf nodes for every part and fill the buckets with the given data.</p>
<p>Now our new dataset consists of the leaf nodes containing our key value pairs, now nodes can be created where each key is the highest value in our leaf node’s bucket. This continues until we end up with just one node.</p>
<h2>To conclude</h2>
<p>This concludes the B+ trees, as example one might look at HybreDb – B+ tree. HybreDb is the project I talked about at the beginning of this post and it does implement the above described B+ tree. Only the deletion I used is a bit more complicated as well as the disk based B+ tree, which allows the whole tree to be written to file and all changes are appended to a file.</p>


Since I have been busy with a new project for school and since it seems promising, let’s talk more about it! As can be guessed by the title it is a database. And as people might know B+ trees are one of the most important parts of a good database. Datastores, key-value stores, relational databases, graph databases all have a B+ tree or at least a B tree. These trees are data structures that are used to store and lookup key values within databases.

On databases: B+ trees

<p>A few weeks ago I needed to create a way of deploying webservices in nodeJS for a client of mine. I looked at some of the existing packages out on the web, but I couldn’t find anything to my liking. I decided to custom build it, not only for learning purposes, but also to be able to use a framework the client was already accustomed to.</p>
<p>One of the problems I faced was the URL routing. Of course there were no problems with static routes, but one of the nice things to have in these kind of situations is parameters within the URL and other fancy things like wildcards. Once again I turned to the web, but the only given solution I found was “just regex all routes and per request iterate over all route regexs”. Although this will work, it isn’t a really elegant approach, I even dare to say that this is almost as brute force of a solution as it gets.</p>
<p>In this post I will use the following routes (and syntax) as an example. The routes are the key within the JSON, where the accepted HTTP verbs are prepended between square brackets. The resource (a file containing the webservice) is the value in this map.</p>
<pre><code class="language-js">var routes = {
    '/': 'index.js',
    '[GET]/test/{id}/': 'test.js:paramExample',
    '[GET]/test/{1}/{2}/': 'test.js:paramExample',
    '/test/hallo/world/': 'test.js:halloworld',
    '[GET,PUT]/test/json/': 'test.js:getJson',
    '[POST]/test/': 'test.js:post',
    '/statics/*': 'statics.js',
}
</code></pre>
<h2>Tree building</h2>
<p>Ok, of course we could regex the whole thing, but let’s first use our brains. We need a way to structure all routes given. I have done this by creating a tree structure which can be seen in te figure to the right. Every purple node is a node which is bound to a resource, so those are possible end nodes. The once with curly brackets are parameters and the astrix is a wildcard. The HTTP verbs are not seen in this picture, but can still be present in the actual node structure, I choose not to show them to allow for a cleaner representation.</p>
<h2>Tree traversing</h2>
<p><img src="/uploads/roadieroutegraph-300x271.png#right" alt="Routes structured in a tree where each purple has a resource bound to it"></p>
<p>Routes structured in a tree where each purple has a resource bound to it</p>
<p>For the people that read my previous post about search algorithms, this will look awfully familiar to a state space representation. In fact it can be used as such, we can use the created tree as possible paths. If we have an input URL we can traverse the tree in that order. Say we have ‘/test/hallo/world/’ the order of traversing will be ‘/’->’test’->’hallo’->’world’, great this works! Except for an URL like ‘/test/hallo/’, with the given routing table we would like to end up as a ‘/test/{id}/’ route, but in our implementation it will end up at ‘/test/hallo/’ which does not have a resource bound to it. So in fact, we need a search algorithm to solve this.</p>
<h2>Searching the answer</h2>
<p>Before anyone tries an uninformed search algorithm let’s revisit our tree. We now know that all purple states are goal states if and only if the HTTP verb matches and the complete user’s route is used — wildcards use up the complete left-over route. When we try an uninformed search algorithm for ‘/test/json/’ it will map to ‘/test/{id}/’ before ‘/test/json/’, this is because we need to apply a kind of ranking in our routes. We could restructure our whole tree to make sure the static routes are looked at first, than the routes with parameters and lastly the wildcards. But instead of restructuring the whole tree with every added route, we could also add weights and use a informed search algorithm.</p>
<p>So our weights are as followed: [1]:static, [2]:parameter, [3 times the size of the leftover URL]:wildcard. I know the wildcard is the ugly duck in this case, but I will explain that later. Now when we use greedy search — which always takes the cheapest route first, ‘/test/json/’ will in fact be routed to ‘/test/json’ instead of ‘/test/{id}/’, this is because ‘/test/json’ as a total cost of 2 and ‘/test/{id}’ has a cost of 3. Now the wildcard, we always want the static routes first and the parameters after that, say we have a ‘/{1}/{2}/{3}/’ route and a ‘/*’ route. The parameter route has a cost of 6 (2 for each parameter), in fact the maximum cost of any route containing only static and parameters is 2 times the length of the URL items. Therefore if we want the wildcards to be last, we need to scale according to the left over URL parts, we could suffice with 2n+1 but anything greater than 2 times the URL items is good, and with 3 times the URL items you have some space to apply ranking between the wildcards themselves.</p>
<h2>Worth it?</h2>
<p>Hell yeah! The main problem with regexing everything is that your worst case scales according to the total of routes you have. This thing scales with the size of the user route, because shorter URLs need to check less states before reaching their goal state. Of course this model can be expanded to include some kind of regex mechanism inside each node, typed parameters, ect. Also a thing to note is that adding or removing routes is really easy. Just add a node per URL part if it doesn’t exist yet and add a resource to the end.</p>
<p>See a live example in the nodeJs roadie package, available on <a href="https://www.npmjs.com/package/roadie">npm</a> and <a href="https://github.com/blackshadev/Roadie">github</a></p>


Ever wondered how packages like flask and express route their URLs to the correct functions, even with properties like wildcards and parameters? In this post I will discuss a solution to this URL routing problem which uses a search algorithm to find the correct route.


URL routing

<h2>Problem description</h2>
<p>Search problems are quite common, for example. A maze solver, a puzzle solver or it’s most common use: a path finder. All search problems can be described as a tree, where each node represents a “state”, to advance from one state to the next we use what is called a “move”. Some of these states are a goal states, these are what we are looking for and preferably as fast as possible with the shortest cost.</p>
<h2>State space of a maze</h2>
<p>Given a random maze with one exit and one entry. Each state consists of the position within this maze. The path from a given state is given by going up in the state tree. The exit is marked as a goal state and a move will return all possible follow-up states from a given state. Immediately it can be seen that if the maze has loops and we expand all states as deep as possible we would end up in an endless loop at some point.</p>
<h2>Traversing the state space uninformed</h2>
<p>Now we have a way of representing the problem in an uniform matter, the only thing left is to find is a method to get to the goal state(s).</p>
<h2>Depth first</h2>
<p>Let’s begin with the most simple one: Depth first search. This search algorithm expands all states as deep as possible, so if the maze has loops this isn’t the best idea, but it is a start. If we wanted we could build a safe guard into the move function to not allow the occurrence of the same state within a branch of the state space twice, this is referred to as branch closing. The reason depth first search is so easy is because we have to only keep track of one branch at a time, moreover it is a recursive algorithm. Below follows a simple python implementation of depth first search.</p>
<pre><code class="language-python">def DFS(state):
    if(isGoal(state)): return [state];
    states = move(state)
    for s in states:
        res = DFS(s)
        if(res != None):
            return [state] + res

    return None
</code></pre>
<h2>Breadth first</h2>
<p>Breadth first search is a more memory heavy search algorithm, what it does instead of diving into the depth of our state space we expand horizontal first, this way we search all possible states and this way we avoid being stuck on those loops. More importantly is this will always return the shortest path, this is because instead of deeping out, we expand every possible path one step at a time. Note, again we could close some tree branches based upon reoccurring states, but for simplicity sake this is left out.</p>
<pre><code class="language-python">def BFS(start):
    queue = [[start]]

    # branch is one branch of the tree, it contains states
    branch = None
    while len(queue) > 0 :
        branch = queue.pop(0)

        if isGoal(branch[-1]): break;

        states = move(s[-1])
        # add all follow-up states to the queue
        queue = queue + [ [branch + s] for s in states ]
    return branch
</code></pre>
<p>As it can be seen, we need to keep track of every branch we create, this can lead to an immense consumption of resources.</p>
<h2>Just think before you act</h2>
<p>Now let’s assume every move has a cost associated with it, this cost is given in the form of a positive number and with this cost we create a weighted graph. Instead of traversing everything let’s try and think which states will likely give us the best result. For these examples the move function will not only return the possible states, but also the cost to get there associated with them.</p>
<h2>Dijkstra</h2>
<p>The first thing anybody would think of is, just expand the path with the lowest cost so far. And indeed this is a valid method. This algorithm is called after Edgar Dijkstra who invented and showcased this algorithm in the early days of the computers. Now an important side note, within Dijkstra’s algorithm it is specified that we can’t have reoccurring states in our path, so we will apply that within our example as well.</p>
<pre><code class="language-python">def dijkstra(start):
    queue = [{"cost": 0, "path": [start]}]

    branch = None
    while len(queue) > 0:
        branch = queue.pop(0)

        if isGoal(branch["path"][-1]): break;

        states, costs = move(branch)
        queue = queue + [ {
                "cost": branch["cost"] + costs[i],
                "path": branch["path"] + states[i]
            } for i in range(len(states))
            if states[i] not in branch["path"] # ignore already present states
        ]
        queue = sorted(queue, key=lambda x: x["cost"])
</code></pre>
<p>The example above is kept simple, instead of resorting the whole queue we could insert the states on the correct position to keep everything sorted, but this is easier to read. As can be seen we also keep track of the whole path again, but we prioritize the expansion of paths with a lower cost. Some observant readers will see that when every cost is the same, we will have the same behavior as breadth first search.</p>
<h2>A* the star of search algorithms</h2>
<p>For the most search problems we have some sort of measure for how far we are away from a end point. Lets call this our estimate and this can be calculated for every state. In our maze example this can be the absolute distance between us and the exit. If we now prioritize the expansion of states to the states with the lowest cost and estimate, we end up with searching the least possible amount of states and finding the optimal solution first.</p>
<pre><code class="language-python">def AStar(start):
    queue = [{"cost": 0, "estimate": estimate(start), "path": [start]}]

    branch = None
    while len(queue) > 0:
        branch = queue.pop(0)

        if isGoal(branch["path"][-1]): break;

        states, costs = move(branch)
        queue = queue + [ {
                "cost": branch["cost"] + costs[i],
                "estimate": estimate(branch["path"][-1]),
                "path": branch["path"] + states[i]
            } for i in range(len(states))
            # ignore already present states
            if states[i] not in branch["path"]
        ]
        queue = sorted(queue, key=lambda x: x["cost"] + x["estimate"])

    return branch
</code></pre>
<p>As can be seen, this is really a small alteration to dijkstra’s algorithm.</p>
<h2>End remarks</h2>
<p>And this concludes our tour through search space, the given examples are not ultimate solutions and are only there as a guide to explain the algorithms. Also there are lots more search algorithms, but these are the most used and most essential algorithms, basicly if you can reduce a problem to the state space you have a good way of reaching your goal. On top of that, if you have a good estimate function for your state space you have a really really great way to reach your goal with A*. Most of todays GPS programs run either dijkstra or A* to do the path finding.</p>


Search problems are one of those problems that every programmer will encounter at least once in his or her life. An important note is that this post will explain search problems, but these are not “how to lookup relative hits in multiple texts” but more “given a map, what is the best route from A to B”. I will discuss search problems in general, Astar and other search algorithms.

Blog posts

Your own GPON ONT pt. 2

Your own GPON ONT

Going static

On databases: B+ trees

URL routing

Searching made easy