And here we can get inspiration for our lab, ideas for our lab sessions. Thanks Fred. Good morning everyone. When we were preparing for the Open IFS I asked Glenn whether he wanted me to give this presentation or the one I gave yesterday and he said both. And luckily this was actually ready, this was a work that we presented with Laura Feranti last year at a meeting on sub-seasonal variability in Washington DC. And I thought that some aspects might be relevant to what you will be doing and the way you may want to verify your experiments here. So you all know that 2015-16 was one of the three biggest in linears we had, probably according to some measures the strongest one in the record. But what I would like to point out is that there was a lot of intracisional variability during this winter and therefore what you will verify, so what when you verify your experiments against the observation the result will depend on exactly what period you are going to look at. So this is the outline of the talk. I will show you something about your sub-seasonal variability both in the U-Atlantic and the Indo-Pacific circulation during this winter. We'll talk a bit about the connection between the rainfall in the Indo-Pacific domain and the non-harmic circulation from analysis and from our current operational seasonal forecast system for winter. And now I will show you how the sub-seasonal variability is represented in the ensemble of our operational seasonal forecast. We do 51 member ensemble so the sub-seasonal variability can be quite different among different members and I will show you how this will affect the prediction. And I will talk a bit about the predictability on a shorter time scale than one season. So here is what happened in reality in 2015, winter 1516. These are maps of 500 leptopascal height taken from the NOAA climate diagnostic bulletin. We hope that it will still be there for the next El Nino. So what you see here is that the maps have some common features but also quite some remarkable differences from one month to the other. In December, it is well known that December is not the month where you see a very strong signal in the Pacific. Everybody is thinking about the connection from the El Nino to the North Pacific but all the seasonal forecasters in the U.S. say that they usually look at January, February, March as the peak season for the response on the Pacific North American part. And in fact, if you look at the map for December here, you don't see a lot of signal in the North Pacific. And instead you see this very strong signal here with a low just south of Iceland and a big ridge over western Europe. So this particular anomaly obviously projects strongly on the positive phase of the North Atlantic oscillation. When you move to January, then the pattern is quite different, sort of wave number two pattern. Now you see this traditional low over the North Pacific which is typical of the El Nino response. And you get again the sort of canonical negative articulation signal in high latitudes. The low over the North Atlantic as weak and has actually moved to the south to the point that actually if you project this anomaly on a standard North Atlantic oscillation pattern, you actually get a negative projection. Then we come to February and in February the low over the Central and Pacific is maintained. But somehow the flow over Europe has come back to this tripolar structure that was very evident in December. And so again we come back to a positive phase of the North Atlantic oscillation. So you will get monthly means to look from your open IFS output. So if you average the three months you will get something quite standard over the North Pacific. But for Europe you will not get the sort of canonical answer response with a negative articulation. Because in this particular winter that actually only happened during January. And instead you will look more like a wave number two pattern with lows over the North Atlantic and the North Pacific that resemble Wallows cold ocean warm land pattern. Now what I will show you now I mentioned that this map project in a different way on to the North Atlantic oscillation. So I will show you this through one of the products that we issue for seasonal forecast. Which is the projection of the geopotential height anomaly on to this first empirical octagonal function for this particular domain. And what you find on our website are these so-called climagrams. And these climagrams are basically plot where we basically compare the distribution of this particular index in the analysis. And that gives this is done on a monthly basis. It's actually the only product of our seasonal forecast where you see monthly information. So the yellow and orange bar give you basically the spread of the distribution of this index in the period of the reforcast for system 4. So in this case it's 1981 to 2010. The red line is the median. The orange bar gives the central tercyl interval. And the yellow gives the distance between the fifth and the 95th percentile. So this is the distribution. And here you actually have the projection over DOF which is there in the corner. And here at the bottom you have the two meter temperature average over northern Europe. Well known then these are well correlated. So positive and AO brings warm anomalies over northern Europe and vice versa. The gray bars actually give again the median tercyl and fifth to 95th percentile distribution from the model climatology during the same period. And the purple bar gives the distribution from the actual seasonal forecast. In this case the seasonal forecast started on the first of November. So if the purple bars are shifted with respect to the gray ones it means that the forecast for this particular season is very different from its own climatology. So you have a significant anomaly. And in this case you see that if you look at the first month November, December, January at least from the forecast from November. If you look for example at the medium or the box indicating the tercyl that is shifted upwards with respect to the gray bar. So it means that the forecast is predicting a substantial shift in the distribution of this index compared to its own climatology. And the same is true for the two meter temperature. So the model was predicting positive and AO basically throughout the winter and warm anomalies over northern Europe throughout the winter. This may be most likely what you will get from your experiments. However if you look to what happened in January as I pointed out January was quite different. So in January the sign of the NaO changed from positive to negative. And we actually had some very cold spells in January. So the temperature anomaly in January 16 was actually cold. The red dots are the verification. So of course when you look at the operational forecast you don't see the red dots. You see everything except the red dots. But then aposteriori as a verification these plots are modified so that you can actually see how they observed a value fitted with the predicted distribution. So again if you average December, January and February and you look over Europe in the Atlantic you will see probably a positive NaO signal. But yeah take into account that if you do a verification, if you are looking on a month basis there was actually this significant variability between different months. Now why is that? Well of course one may speculate but the strongest source of intracisional variability in the tropics and in some parts of the extra tropics as well is the mother and Julian oscillation. And probably many of you are already familiar with it is basically a propagation of large scale organized areas of convection that usually starts in the western Indian Ocean and propagates to the east. And Wheeler and Handon in 2004 proposed a classification of this MJO cycle in eight different phases and proposed one index which is now widely used in the verification of weather prediction and climate models. So these are the canonical eight phases of the MJO according to Wheeler and Handon and these phase two and phase three are the phases where the convection is in the western and central Indian Ocean. And a number of studies for example one from Kassou in 2008 on Nature actually pointed out that about ten days after these phases occur ten to fifteen days you tend to have a positive NaO signal in the North Atlantic and following typically phase six after ten days you tend to have a negative NaO. So did the MJO episode occur in 2015-16? The answer is yes. You can actually see again some data from the NOAA bulletin. So these are of molar diagrams with time going from top to bottom. So starts in June 15 and goes up to April 16. On the left hand side you see anomalies of outgoing long wave radiation. So low anomalies are indicative of increased convection. So you see that overall throughout the season you tend to have negative anomalies typically in the NINU-4 region. However there's quite a strong modulation even more so when you actually look to the compensating sinking motion over the maritime continent. And if you actually look farther west in the area of the western Indian Ocean what you see is that you see negative anomalies in December and negative anomalies in February but actually positive anomalies during January. So although the signal in the main NINU region in terms of OLR is quite consistent throughout the season when you look at the maritime continent and the western Indian Ocean you see the effect of this MJO activity. You can see clearly the easter propagation of the signal in this other of molar diagrams that shows the velocity potential at 200 hectopascal. And again you see here for example that this if you look at December you actually have an anomaly of negative sign again indicative of convection over the Indian Ocean. November and early December then you actually have positive anomalies here at the beginning of January which actually vanish again in February. So quite a lot of intracesional variability in the tropics. And now so it's interesting to try to work out how the convection in different parts of this domain actually connects with the extra tropics. And well it's now three years ago with colleagues at ECMWF we looked at the teleconnections in our seasonal forecast system system 4 and particularly we look at the connection of rainfall in three regions of the Indian Ocean and up to the Central Pacific domain with both rainfall in other parts of the world and geopotential height. We focused on three regions one on the western and central Indian Ocean that you see at the top the maritime continent and then in your four region. And what you see is a comparison on these maps from the GPCP 2.2 data set on the left hand side and system 4 on the right hand side. And you can see a sort of a common structure in the these are maps of covariance of rainfall everywhere with rainfall in the boxes. And you can see that there is this tripolar structure which is basically a consequence of the dominant variability in the water circulation. So usually when you have a scent due to increased convection for example in the Indian 4 region and you have the scent of the maritime continent but then again increased rainfall over the western part of the Indian Ocean. The Indian Ocean so these two regions are regions where there is a positive correlation between SST and rainfall. Very strong here about something like 50 to 60 percent here. So the precipitation in the western Indian Ocean is positively correlated with the SST but to a less strong constraint than you have in the Indian 4 region. So there's more internal variability from the Indian Ocean that you have in the Central Pacific. Actually this is an area where there is hardly any correlation between SST and rainfall because actually the amount of rainfall is controlled not so much from the SST but just from the dynamical response to the other two areas of ascent. So you can see that the system 4 does a pretty good job in simulating these teleconnections as we have diagnosed them from observed data, the GPCP data. You can actually, one difference that's quite interesting is that if you look at this particular map you see that the signal associated with rainfall over the western Indian Ocean so the covariance between the rainfall over the western Indian Ocean and the Central Pacific is actually stronger in the model than it is in the observation. So somehow the model tends to like this tripolar structure more consistently than in reality. Now if you now look at the geopotential height anomalies that cover with the precipitation in these regions let's focus on the two, the one on the left and the one on the right. The one on the left is from the western Indian Ocean. The top are the teleconnection maps from Iran Interim and here are from system 4. So from the Indian Ocean you tend to get the wave number 2 structure with a positive NEO signal actually quite stronger in the observation than in the model but still the model captures that. While if you look at the teleconnection from the NEO 4 region if you look at the observed map you see actually a negative NEO pattern. You don't see this very much in the model and the reason we think is because of the stronger link between the Indian Ocean and the Central Pacific in our model. So since the Indian Ocean tends to give a positive NEO if you actually always associate a linear with a strong convection in the Indian Ocean you will tend to get a positive NEO as well. However one has to say that if you look actually to 2015-16 the observed average for the season looks more like this map than the top map. So because as I said it was the main response in this year was not the sort of canonical response to answer that you see in this particular diagram. Now of course you can do things in reverse and say instead of starting from the tropics and seeing what happens in the extra tropics you can start from the NEO signal and it's interesting to do this now to compute these covariances the other way around and to do them month by month. So if we now take, we compute the NEO index as the projection onto the first Atlantic UF and you compute the covariance of rainfall everywhere and you do it on a monthly basis. Well first of all of course you see the traditional shift of the precipitation to northern Europe which is characteristic of positive NEO and then you see in December again this characteristic tripolar structure of precipitation in the tropics. When you move to January the connection to the central Pacific actually tends to vanish but you still see this tripolar structure between the Indian Ocean and the maritime continent. In February most of the signal is actually gone. So when you actually average the three months together you have a rather weak signal. So this is a problem that has been noted by many authors that when we try to connect the response of ENSO to the extra tropics and especially in Europe often doing the traditional seasonal average then to wipe out the signal because the signal is actually different in the early part of winter and the late part of winter. This is something that Fred mentioned yesterday and again so this is some aspect that you may want to see in your model whether you get a different response in the early part of winter when this tripolar structure seems to be stronger. So in fact we found out also from looking at the observation the best index for this wave number two pattern is actually a combination of ascending motion over the western and central Indian Ocean and sinking motion over the maritime continent. So if you construct an index basically as a dipoly index between these two regions same as you can do for example for the NAO between Iceland and the Azores and then you teleconnect this index just in December and January then you get a very strong extra tropical response with this characteristic wave number two pattern. So February doesn't contribute very much to this particular correlation but it's actually stronger in the early part of the winter. Now I mentioned that different ensemble members can represent this in transition of variability in different ways and so I already showed you that if we put all our ensemble members together the model tended to stay in a positive NAO state throughout the season. However some ensemble members did show the inter-seasonal variability so what Laura did was to pick up the best five members in system four in the sense that those that showed the largest change in the NAO index between December and January. You remember we had a very positive NAO in December it went to negative in January. So if we pick up this member then the geopotential height anomaly would look like this in December and the temperature, two meter temperature over Europe will look like this so very strong energy signal and positive anomaly and then in January you move to the structure with actually positive anomaly over the Arctic so a negative Arctic oscillation and that is actually associated with cold temperatures. So some members actually managed to do the same as the real atmosphere but only a minority of them. So we try to understand why it happened and try to relate it to the convection in these regions that I showed you before and these are maps of 200 hectopascal velocity potential anomaly for the five best members on the left and the ensemble mean of all the 51 members on the right and this is what, this is the anomaly in December and this is the anomaly in January and both these five members and the ensemble mean show that this very strong signal that came from the western Indian Ocean so negative velocity potential anomalies are indicative of enhanced vertical motion and convection so all members were probably quite consistent in getting the decrease in the activity over the western Indian Ocean however if you actually look at the maritime continent region there was quite a difference so the best member actually showed an intensification of the sinking motion over the maritime continent and the ascending motion over the Indian Ocean region so somehow the strength of the working circulation while in December was mainly between the maritime continents and the Indian Ocean actually shifts in January to a more traditional El Nino pattern that has in fact the canonical reconnection as a negative articulation side. If you look at the ensemble mean the change over the Indian Ocean is there but you actually, if you actually look at this feature there's actually a weakening of the two centers over the maritime continent and the Nino four regions so somehow what it seems is that the anomaly in the working circulation shifted from being mainly over the west Pacific and the Indian Ocean in December to the central Pacific in January and this basically changed the response from a positive NEO to a more canonical negative articulation scene. So if you run your 10 member ensemble you may get some of them First of all, we have to say that sub-seasonal variability is hard to predict beyond the first, let's say, month or two months in the best cases. So it's not very easy to predict what happens in generally starting from the first of November so don't be disappointed somehow. Usually sub-seasonal variability operationally is limited to 30 or 45 days. So probably some of your members will show the change as it's depicted in these panels some of them will look more like the ensemble mean. So this is just to warn you about the possible differences that you may find in your ensembles. Now in this prediction of course there's another factor apart from the inherent predictability and that is the fact that all models have systematic errors so in some sense it's usually easier to predict some transitions in a model if the model tends to like the state towards which the atmosphere is actually moving. And actually, so if you look at the same climagrams for the North Atlantic oscillation here and the two-meter temperature anomaly from actually operational seasonal forecast starting not on the first of November but first of December and the first of January, you actually see that even from the first of January the model actually did not do this transition from positive to negative NAO even if you don't, one more month. But actually, if we started from the first of January then it actually got the return back to a positive NAO signal correct. So the transition from positive to negative was not well forecasted on a range of two months but the transition from negative to positive was. And we think that the reason is because somehow this in February there was a return to a situation similar to what we had in December which is a situation with which the model tends to reproduce more easily. I showed you that the model likes this tripolar structure and tends to actually enforce a tripolar structure on the rainfall anomaly. So we think that the difference in the predictability on the two-month time scale was somehow related to the fact that the model went back to a state which is more somehow consistent with its own dynamics. Okay, the conclusion is just a summary of what I said and so we hope that this may guide the way in which you look at your experiments and the different ensembles and I think that Glenn has, so we have included this western Indian Ocean as one of the boxes that can be analyzed with the Metview script so that you can actually look at, for example, time series of evolution of rainfall and the system in this particular region which is quite important for the teleconnexions.


It appears that the Lagos State Emergency Management Agency has concluded the search and rescue operations at the scene of the Ibutimeta building collapse as sympathizers hang around sub-in. As scavengers climb the heap of rubbles to pick beats and pieces of their properties, some residents and eyewitnesses say some of those that died in a tragic incident have been buried. My mother-in-law and my sister lived in the collapsed building. The boys around tried but they brought out my mother-in-law and the son dead. Some other victims were calling that they were still trapped in the rubble but the caterpillars brought them out dead too. In fact, those dead were more than 20. There are some houses inherited by the third generation and are still gerrible but this house was not well built whether it has existed for 30 or 50 years. Government should help monitor the developers or else young and old would continue to die. This particular building was built with adinari sand. I will blame the government because the residents of those places, I can't blame them much in the sense that if you look at the cost of rent in this country is too high. The cost of houses in this area is so much. A woman parlor, getting a woman parlor one million naira with agreement and commission. How many people has that money? And I believe most of them died in that house because of the high cost of apartment. That is why they didn't leave.


What we got to last week was some issues with routing algorithms and routing techniques. What are some of the problems or decisions we need to make when we design an algorithm for routing? That is some way to find a path from source to destination. Then we need to choose the criteria for selecting the best path. So what do we mean by best? And there are different criteria, sometimes called metrics. So four of them are listed here. There are others. There are performance criteria or routing metrics, ways to measure the best path. When to decide which route to take, who decides, who collects the information, whether it's all nodes participate in a distributed manner or there's some special centralized node that collects information. And then the last two parts which we're going to spend a bit more time on is where do we get information from and how often do we collect that information. But first let's just look at routing metrics and look at another simple example. You don't have this one. Here's a network with five nodes, five switches. And if we want to choose a path from node one to node four, we've got two possible paths in this case, path one, two, three, four and path one, five, four. So source, node one, destination four. And the links, I've given some characteristics of each of the links. For example, the link from node one to two has a delay, for example, propagation delay, maybe queuing delay at the nodes of five milliseconds and a data rate of 100 megabits per second. And similar, we've got values for other links. So in this simple network, if we want to get from node one to node four, what's the least cost path if we use the metric of hops? Can anyone tell me? What is the least cost path if we use the metric of hops? And a reminder, what is a hop? A hop is the traversal of one link. We make one hop from one node to another. In routing, we normally find the least cost path where the cost is determined by our metric. So what's the path? One, five, four, two hops. A hop from one to five and a hop from five to four. So two hops across that path. If we took the other path, it's three hops. So when we use hops as a metric, then the costs we can think of each link is one. The cost for this link is one. The cost for the link from five to four is one. The cost for all links is one. And in least cost routing, once we have the costs for the links, we simply find the path with the least cost where the cost of the path is the sum of the cost of the links on that path. So the cost of this path is two. The cost of this path is three. Therefore, the least cost path or the least cost route is one, five, four. That's using the metric of hops. Path one, five, four costs two units, two hops. What if we use delay instead of hops as the metric? We change the metric to delay. What is the path and what is the cost of that path? And you've got two choices of path. So not so hard, but what's the total cost? What's the best path now? Which path are you going to take? One, two, three, four, why? Least number of the total delay, if you add up these three delays, five milliseconds plus six milliseconds plus 10 milliseconds, then we have 21 milliseconds from one, two, three, four. The alternate path takes us 28 milliseconds. So in that case, if we use a different metric, we would say the least cost path would be one, two, three, four. So the costs in this case come directly from the delay. In fact, so if we know the delay of the link, we can say the cost of this link is five. So we get a different least cost path. One, two, three, four, total cost of 21. So with those two cases, hops or delay, we can relate the metric to the cost and then just use an algorithm like, we can calculate it manually, but for a larger network, we could use an algorithm like Dijkstra's algorithm that would calculate that for us, because that's how those shortest path algorithms, how they work, they use the cost to determine the shortest path from source to destination. Any questions? Those two are easy. This one's not so easy. This cost path from node one to node four if the metric is data rate. And the way to think of that, I want to get a lot of data from node one to node four. I've got a network and I'm going to run it for months and I'm always sending data across that network. If we care about the data rate or eventually the throughput, which is proportional to the data rate, which path should we use to get the highest data rate? Which one? One, two, three, four, why? High data rate, this one. So in the path one, two, three, four, the first link has a data rate of 100 megabits per second, which means we've got a lot of data, let's say across a period of 24 hours one day, we've always got data to send. So we can send it at 100 million bits per second to node two. When that receives data, it's continuously receiving data we're always sending, it receives data and sends to node three that data at 10 megabits per second. And as three receives data, it sends at a rate of 50 megabits per second to four. And let's look at that in a bit more depth. If node one is sending at 100 megabits per second, at what speed does node two receive? What's the maximum speed it can receive? Assuming no errors, nothing goes wrong. At what rate does it receive data? No overheads, everything's simple. If one sends at 100 megabits per second, two receives at 100 megabits per second, okay, easy. You receive at the same rate that the sender is sending on the link. So two is receiving data at 100 megabits per second. Two is sending data at 10 megabits per second. It cannot send faster. At what speed does node three receive the data? 10 megabits per second. Node three is receiving data at 10 megabits per second. Now, across those two links, even though we're sending or we could potentially send at 100 megabits per second here, node three is never going to receive at a rate larger than 10 megabits per second. It cannot receive at 100 megabits per second because this link here limits our speed. Now, although node three can send at 50 megabits per second to node four, node three is only receiving at 10 megabits per second. It's like I'm receiving data 10 megabits per second. How fast can I send out data on average? On average, I cannot send any more than 10 megabits per second because I've only got 10 megabits per second to receive. All right, I can send out at 50 megabits per second, but then I would spend some time not sending at all. The data that we send out cannot not be larger than the data that we send in over a long period of time. So what would actually happen at node three is it receives data at 10 megabits per second. It transmits that quickly, and then it waits to receive some more data, not sending anything. And then it receives some more and transmits. So we care about the speed at which we can deliver data from node one to node four. And across this path, we are limited by this link. If we look over a long period of time and measured, then even though we can send at 100 here and 50 here, in fact, across the entire path, the best we could do from one to four is limited by 10 megabits per second.  What's the best path? One, five, four. Across that path, the best we could do is at 20 megabits per second, because what we say the bottleneck link is the link with the lowest data rate. So in path one, two, three, four, the bottleneck link has a capacity or data rate of 10 megabits per second. In one, five, four, 20 megabits per second, which is better. So the better path in that case would be one, five, four. If you don't understand why that limits this, have a think about it and maybe you can do some calculations of transmission times or think about other things you may know like water flow through pipes. The amount that you can send through a pipe of a certain diameter is limited, the rate at which the water flows. This is like pipes. We have a very thick pipe here. We can send a lot of data. But once it gets here, we've got a thin pipe. We're restricted as to how much water can go between two and three. And even though we have a thicker pipe here, the amount coming into that pipe is limited by what comes into node three. So in fact, we're limited by the lowest capacity link in this case or the lowest capacity pipe in a water system. Often called the bottleneck link. It's the slowest part of the network. So best path we just determined is one, five, four. How would we calculate that? That is what we need to do with least cost routing is assign costs to the links such that an algorithm like Dijkstra's algorithm can automatically find the path by simply finding the path with the least cost when we add up the costs. One way to do that is to consider, okay, our network has a maximum data rate of all the links of 100 megabits per second. We know that actual data rates of the links let's assign a cost to each link which is the maximum divided by the actual. So we get these cost values. This link from one to two has a cost of one unit, 100 megabits per second divided by, so the maximum divided by the actual of 100 megabits per second. The second link has a cost of 10, 100 divided by 10 and so on. These are the costs we assign. And now we just use an algorithm to find the path with the least cost. One, two, three, four has a cost of 13. One, five, four has a cost of 10. Least cost path, 10, one, five, four. So sometimes with our metrics we cannot equate the metric value to the cost. We could with delay. Cost of this path, this link was five units because delay is additive across the path delay is just the sum of the link delays. But data rate is not additive. So we need some function to convert the data rate into some cost, so it's a bit more complex there. In fact, that function doesn't work in all cases. It works in many practical cases, but not in all cases. So just an example of least cost routing. We take some metric, use that metric to assign a cost to each link. Once we have costs on links, then we use some algorithm to find the least cost path from source to destination. Sometimes the mapping of metric to cost is more complex than what we have seen in simple cases. So let's return to the case in our network. We calculate the least cost paths at some point in time. But over time, the network conditions may change. Therefore, we need to collect information about the network conditions. Where do we collect that from? How do we collect it? And we often need to update that information on a regular basis. How often do we update it? So we're gonna look at some examples of where do we get information from and how often do we update that information? Here's our example network. A reminder, the least cost path from node one to node six was 1456. We calculated last lecture, one plus one plus two, a cost of four. So let's say node one has calculated least cost path from one to six is 1546. Cost is four units. It's sending its data across that path. Node one has a lot of data to send to six. It's sending it across this path 1456 and keep sending. Because maybe when we built the network, we told node one, these are the links, these are the costs. And we ran some algorithm here that calculated the least cost path to six. So we're using that path. But over time, the conditions of the network may change. So let's say the link from node five to six, the conditions change. And the cost was two units before. And let's say the cost rises to 20. Why? Well, it depends on what the cost is measuring. Maybe the cost is related to the amount of congestion or data going across that link. And at some point it's going up, meaning this link is becoming worse and worse for our data transfer. As the cost goes up, that's bad. So the cost goes up. Now, node one is still sending data to node six via this path 1456. Is it using the optimal path? Is node one using the optimal path to get data from one to six? Hands up for yes. Hands up for no. Okay, a few people. All right, you can check. The path from one to six has now has a cost of one plus one plus 20, 22. I'm sure you can find other paths from one to six with a lower cost. For example, 136 has a cost of five plus 510 units. So it's no longer using the least cost path. It's using a suboptimal path if it keeps using 1456, which is bad. Bad for performance because what we want with routing is to use the best path, the least cost path. We're not using it anymore because the network conditions changed. So, what we'd like is that somehow node one learns of this change. So it will update and recalculate the least cost path and find an alternate path to node six. So avoid this 20 cost link here. Well, how does it know that this link cost has changed from two to 20? Remember these, this may be a network across a country or a city. There's no direct link from node one to node five or six. So what information does node one know? Well, first each node we assume knows about the costs and the end points of each of its links. That is its connections to its neighbors. Node one knows that it is linked to node four and the cost of the link to node four is one and reverse is seven. When we see these arrows here, think that there's three cables plugged into node one. When we turned on node one, we knew who was at the other end point of those cables and we know the costs of using those links. So we say that each node knows information which is local to itself. Information source, local meaning, information that that node has immediately or always has access to. So we assume node one knows about these links and the cost of those links. So if anything changes on those links, for example, the link from node one to node four changes from one to 10, node one knows about that immediately. That's easy. So if it did change here, node one could recalculate. Unfortunately, this hasn't changed. The link over here has changed. Node one does not have direct access to that information. It's a link to some other node. So each node knows information about its local links or its links to neighbors. We have three neighbors of node one. Another way to learn about the changes in the network is to ask your neighbors to tell you about their links. So what we could do is say, every node tells its neighbor about the current conditions. For example, node four sends a message to node one saying, I currently have links to one, two, three and five and the costs of those links are these values. And similar, node two sends a message to node one saying, I currently have links to these nodes, these are my neighbors and these are the cost of the links. In that way, node one would learn about the current conditions of those other links and try and draw what node one knows, considering different information. So node one knows about its local links. So when I highlight it red, it means node one knows that information. That is who is on the other end point of the link and what's the cost of that link. And similar, the link up to node three. Those links we'd say are local information or a local to node one. If we extend and we get our neighbors to tell us about their links, so node three, node two and node four all send some special message to node one, then node one would eventually know about its neighbor's links, which includes all these other links, node two to three, the reverse direction. So node one would learn about the links and the costs of its neighbor's links. Who is at the other end point and what are the, sorry. And what are the costs? So that is using information from what we say adjacent nodes or neighbor nodes, the neighbor nodes, inform us. From node one, node one's perspective, that is better because now node one has a better picture of the current conditions of the network. It knows about the costs of all of these red links. So it knows more than just its local information. It knows most of the network in this case, in this example, in a larger network, maybe not. Now the problem with this approach of asking your neighbors to tell you about their links is it creates some overhead in communications. That is, we need to send a special message from node one, oh, sorry, node four to node one, and node two to node one, and node three to node one. We say that's an overhead of using the network. We want to minimize that. We'd like to avoid that overhead because sending that special message is time that we cannot spend sending data. So the advantage of asking our neighbors to tell us about their links is that we'd learn more about the network, but the disadvantage is that we have some overhead. And of course, not just to these three nodes have to tell their neighbors, all nodes have to tell their neighbors. Unfortunately, just by asking our neighbors, we still don't know about this link from five to six because we were unlucky and that none of our neighbors have a link between have the link from five to six. So what can we do? Well, we could extend and ask our neighbors, neighbors to tell us about their links. We'd learn more about the network, but there'd be more messages sent through the network, more overhead. And the best case, ask all nodes to tell us about their links. So every node in the network sends a message to node one about their current status of the links. And if six sent a message to one, and as would five, then node one would learn about that link and would learn that the link from five to six now has a cost of 20. Okay, let's update my least cost routes and let's find a new route from one to six. So where do we get information from? The case of none is a special case, we'll return to that later. Local, meaning information that's local to that current node. Ask our neighbor or adjacent nodes. And maybe the best case is all nodes. Ask all nodes or get all nodes to tell us about their current links. Nodes along some route. Again, a special case we may see later. Once node one knows that this link has changed to 20, we recalculate the route and start using that optimal route. So we recalculate the route, find the best one, whatever it is. And then one minute later, the cost changes back to one. What happens? What do we do? Do we know that the cost has changed? We don't know, how could we know? We need some regular updates of the cost. That is, we need to repeat this procedure of getting all nodes to tell us about their costs. So in general, we need to keep learning about the costs and the topology changes. That is, we need to get updates. When do we get updates? Continuous means we always have access to the information. For example, we would say that the local links for node one, if this cost changes from one to two, then node one immediately knows that because it's directly connected to that link. So we'd get continuous updates about that cost. That's easy. Another approach is periodic updates. Every five minutes, each node sends a message to every other node saying these are the current costs. So we get an update every five minutes on a periodic basis. Or maybe there's a major change in the amount of data traveling through the network or a portion of the network, a major load change. That is, the amount of data traveling between five and six suddenly jumps to be very high. That triggers node five to tell everyone, this link is being used a lot. Maybe you want to update your routes. So a major change in how the network's being used or a topology change. The link from five to six goes down, is disconnected. It's no longer there in our network. Then maybe that triggers node five to tell everyone, I no longer have a link to six. Please update your routes if necessary. So there's different ways to trigger when to perform updates based upon some events or on a periodic basis. Because as the network operates, we'd like to use the least cost routes and because the network conditions change, we need to get more information about the network to calculate the least cost routes. So there are some trade-offs there. In general, what we can say about where do we get the information from, the source and how often, the more information we collect, the better the chance we will choose the optimal routes. So the more we know about the network, the more chance we'll choose the best path from source to destination. If I know nothing about the change in the network, if node one didn't know that this cost change from two to 20, then of course, there's a high chance that node one will use the least or a suboptimal route from one to six. The more information we learn, the better chance we'll choose the best path. And the more frequently we learn about the changes, again, the more chance we'll choose the best path or use the best path for the longest period of time. So learning more information on a regular basis or on a frequent basis is better for choosing best paths. But it's bad for overhead because usually to learn that information, nodes need to send special packets through the network. If I need to send a special packet to every other node every one second, node four to every other node, and every other node to every other node, then there are many packets being sent per second just to learn this information. If we extend that to a network of 100 nodes, then we're sending 10,000 packets per second just to inform everyone about the network conditions, not to send data, but to learn about the network conditions. So the more information, the better for choosing the best route, but the worse it is for overhead. So that's the main trade-off with routing or this part of routing. Any questions on those issues for routing techniques? Let's look at some other parts of routing. Assuming that we can learn the information about the network topology, and assuming we've got some algorithm for calculating the least cost paths, then what do we do? How do we get the data from source to destination? Well, there are different strategies. Fixed routing is quite simple, but we'll use it to introduce some important concepts we use in most computer networks. The approach in fixed routing is that we build the network and the person who builds the network knows the network topology. We know who's linked to who, and we know the costs of those links because we chose the metric, the performance criteria. So when we build the network, we get a picture of the network like this. We plug the network parameters into some algorithm, into a computer program that calculates all the least cost paths. Calculates the least cost paths from every source to every destination. So the routes are determined, for example, using Dijkstra algorithm or others. And then we fix that route for the duration of the network, or at least for a long time. So we build the network, calculate the routes and those routes are fixed. We get fixed routing. At least until there's some major change in the network. Let's say I build the network, it has six nodes, in a month's time I add one more node to it. So maybe at that time I recalculate the least cost routes. But during that one month, the same routes are used all the time. That's easy because we don't need to learn about the network conditions in the network as it operates. But the problem is that as the network conditions change inside the network, for example, the amount of data being sent across links change, the delays change. With fixed routing, we don't choose new routes, even as those conditions change. So for example, if we have some overload, too much data being sent in one portion of the network, we maybe had an overload in the link from node five to node six, a lot of data being sent, the cost went up. With fixed routing, we wouldn't consider that. We'd still keep using this link from node one, or the path, node one through to node six. Until there was some major update in the network, like we add a new node, then we may recalculate and find, okay, there's a better path from one to six. So normally with fixed routing, we calculate the least cost paths at the start and then keep them fixed. It's simple. You just calculate the routes at the start and maybe program it either into the nodes themselves or have some special computer that stores those routes. When we want to send data, we just look up the route and send the data. The problem is that it's not very flexible as the network changes. So when the network's running, people are sending data, the delay may change, the throughput may change across links. Therefore, there may be better routes between a source destination pair. With fixed routing, we don't consider that. It's very inflexible in that sense. Suboptimal paths will be used on a regular basis. So with fixed routing, determine the paths, determine the routes using some algorithm and then somehow program it into the nodes so that when we send data, we will use those paths. Let's focus on how we do that, how we store the information about the paths. First, here's our network again. Same network, just smaller. How many paths are there? How many least-cost paths do we have in that network, in this network? Any answer? Sorry, so here's our network. What we need to do, because we may want to be able to send data from anywhere, any node to any other node. Six wants to send data to three, then we need a path. Four wants to send to two, we need a path. So what we do when we build our network, we find all least-cost paths from any source to any destination from any source to every destination. So how many paths would there be in that case? Well, we have six potential sources. Node one through to node six are sources. Node one, how many potential destinations? Five, five other nodes. So there's five paths needed. Node two, how many potential destinations? Five, there are five destinations. Remember, from one to two, and from two to one, they may be different paths because there's different costs. There may be different least-cost paths. So from two to all other destinations, there's five paths needed from three to five others. So there are 30 paths needed in total. With six nodes, there are 30 possible paths from any source to any destination. Each six to five possible destinations. So we calculate the 30 paths and we'd use an algorithm to calculate them for us. And you've got this towards the end of this lecture note, yeah, this topic. I've calculated the paths for each of those source nodes. So this table on the left, ignore the one on the right. That's later, this one. I've calculated the paths from each node to each possible destination. So the first source node one. If one is the source, then, in fact, my program that did this calculates from node one to the six other nodes, node one to one, one to two, one to three, and so on. We don't consider the case from node one to node one. We don't care about that, sending to ourselves. Ignore this first row. The second row here is destination node two, third row destination node three, node three, four, five, six. And this is if node two is the source, destination node one, three, four, five, six, and so on for the other nodes. That's what this table shows. So I've calculated the paths and we can read it as from node one to node two. The path is one, direct to two. From node one to node six, a least cost path is one, four, five, six, and the cost of that path is four. From node three to node four, a least cost path is three, five, four, and the cost is two. And there are 30 paths listed there for each in total for the network. The costs with zero are not paths at all. They're direct to from source to destination. That's for our six node network. What if you have 100 nodes? How many paths? Okay, just a larger network, 100 nodes. How many paths do we need? With six nodes, how many do we need? We needed 30. So with 100, we need how many? How many sources are there with 100 nodes? 9,900 paths. With six nodes, remember, we need path from any node to any other node. So there are six possible sources. Each source has five possible destinations. So six times five paths, 30 paths. With 100 nodes, there are 100 possible sources. Each source has 99 possible destinations. So 99 times 100, 9,900 paths needed. That's when you need a computer to calculate those paths for you, because you're not gonna calculate that 10,000 paths by hand. But you do the same thing. Calculate the least cost paths. Let's look at some of the paths. Look at some concepts of how do we store the paths? Let's just make note of some paths. If we look at the table on the other slide, a path, a least cost path from one to six, we had was one, four, five, six. And the cost was four units in that case. So that's, we've calculated that. What's the least cost path from four to six? Don't look at the picture. Don't cheat. Don't look at the pictured. Look at the screen. What's the least cost path from four to six? The hint is it's up here. It must be, or a least cost path from four to six must be four, five, six. There may be others, but there should be no other paths with a lower cost from four to six. That's an important point. And you can check now if you wanna check, it turns out it is in our network. There's a path four, five, six, and it has a cost of three. And if you check, the segment from one to four has a cost of one, and from four to six has a cost of three. So the path from one to six had a cost of four. If we look at the individual segments, one to four had a cost of one, four to six a cost of three. Because the least cost path from one to six includes the segment four, five, six, it implies that a least cost path from four to six must include four, five, six. Why? Well, what if it didn't? What if there was a path from four to six with a cost of two? Let's say we had another node. Node seven, there was a path four, seven, six. And it had a cost of two. Then look at the first path. What can we say about that? If there's a path four, seven, six, so there's a new node in the network connected in between four and six has a cost of two units, what does that tell us about the first path? Or tell me a least cost path from one to six. Then there must be a path from one to six which is one, four, seven, six, which would have a cost of one. To get from one to four, the cost is one. But now we say to get from four to six, the cost is two. Therefore, there must be a path from one to six, one, four, seven, six, with a cost of three, which is lower than our current cost of four. So if there existed a path from four to six with a lower cost than four or five, six, then it must mean that there's a path from one to six with a lower cost than one, four, five, six. Of course, there is no node seven in our network, so it's not the case, but it tried to give an example of the fact that if we know this is a least cost path, one, four, five, six, then it directly leads to a least cost path, four, five, six, being present from four to six. Because if there was a lower cost path from four to six, such as four, seven, six, with a cost of two, then there would be a lower cost path from one to six. But we just said this is the least cost path, so there cannot be a lower cost path. So what we can learn from that is that, given a least cost path, all the segments along there also make up least cost paths. There may be other least cost paths with the same cost, but there will not be any lower ones. So if we know one, four, five, six is a least cost path, we know one, four is a least cost path, four, five from four to five, from five to six, and we know four to six, the least cost path is four, five, six. One to five, we know a least cost path is one, four, five. The segments are also least cost paths. That's useful because it means that we don't need to store the entire path when we store the information about where to send data. And that helps in our structuring of routing tables. Any questions on that concept? That's important to know before we move on. People see why that's the case or see why it can't be the case that we have a lower cost path from four to six. The logic of that makes sense, okay? You're sure? There'll be questions in the quiz for you tomorrow afternoon to make sure you're sure. Now, we use this information to work out what information to store for our routes. If node one has data to send to six, then it wants that data to traverse the path, one, four, five, six. So node one sends the data, think of a single packet. The destination is six. Node one sends it to node four because that's the next node in the path. Node four sees it has some data. The destination is still six. It came from one, destination is six. Node four doesn't need to know the path before there. In fact, it doesn't even need to know the source. It just needs to know, okay, I've got data, destination is six, the least cost path from me, node four to six is four, five, six, so I send to five. And let's just remove, if you ignore that one, another path, we know which is least cost is five, six, which had a cost of, you'll check, I think it was two. Because four, five, six is a least cost path, so it's five, six. So what happens, node one has data to send to six. It knows that the next node in the path to reach six is node four, so we send the data to four. Node four has the data, looks at the destination. Destination six, node four knows from its least cost path to reach six. The next node is node five, so it sends to node five. And node five receives this data, sees the destination is six, and node five has a least cost path to six, which is to send direct to six. So five would send to six, and six would receive the data and finished. The process that we use there, when node one sends to node four, it in fact doesn't care that five is going to come after four. All node one needs to know is what is the next node in the path to reach destination six? Similar, all node four needs to know. To reach destination six, what is the next node in the path? Because of this nature that the segments are all least cost paths of the entire path, then we know if we send to node four, we don't need to tell node four to send to five and six, because if node four has data and is going to send to six, then it's guaranteed to travel a least cost path. So what we actually need to know from the sender's perspective is, what is the next node in the least cost path? For example, node one needs to know that the next node to reach node six is four. Node four needs to know, the next node to reach node six is five, and five needs to know that six is the next node. We don't need to know the rest, we don't need to store the rest of the path, and that becomes important in practice and arrives at how routing tables are normally structured. So again, what we do now is calculate all least cost paths in the network. So we know the least cost paths from every source to every destination. Similar to this table, we calculate this entire table. We have all the paths, one, two, one, four, five, three, one, four, and so on. Then we store in some table, the routing table, instead of the entire path, we store only the next node in the path to reach some destination. And optionally, we store the cost in practice, we may use the cost as well. So we store information which is to reach this destination, the next node in the least cost path is this node. And optionally, the cost of that is some cost. This is the general structure of a routing table or a routing directory. We normally call it a routing table. So we calculate all the least cost routes, but then we just store the next node, which is in fact the second column in this picture. From node one, its routing table would be this set of data, but just destination two, three, four, five, and six. That's two, three, four, five, and six. Next node, two, four, four, four. The other part of information is not needed. We may store the cost as well. Node two. From node two to nodes one, three, four, five, and six, the next nodes are one, three, four, four, and four. Because node two, if we're sending to six, we just need to know to send to four, and then four will use its least cost path to send to six. And the least cost path from four to six is included in the least cost path from two to six. What we get, and we'll come back to the one we missed, are routing tables that look like this. They're called directories here, but that's just from the textbook, a routing table. These are the routing tables for individual nodes. How to read them is if we have data at node one, and the destination is node two, send to node two. If we have data at node four, so we have a packet at node four, and the destination of that packet is node three, send to node five. So these are routing tables for each of the nodes. And in this is the case where each node stores its own routing table. Where does that data come from? You can check. Look at node one. To reach destinations two, three, four, five, and six, the next nodes are two, four, four, four, and four. From node one to reach the destinations two, three, four, five, and six, the next nodes are two, four, four, four, and four. So that routing table information, destination next node, is directly from the least cost path calculations. But we don't need to store the entire path. We just store the next node in the path. Why is that an advantage? A, storing an entire path uses up memory, especially when we have long paths. And importantly, when we exchange information with other nodes, then we only need to exchange the next node. We don't have to tell them about the entire path. We don't need to determine the entire path in some cases. So it simplifies routing in large networks by just keeping track of the next node. This is a case where we distribute the routing tables amongst each node. Node four has data to send to six. Normally in the packet that contains the data, there's a header. Inside the header will be the destination address. Destination equals six. So what node four? Sorry, let's go back to our simple case. Node one has data to send to six. Destination six, node one, destination six. It looks in its routing table, destination six. Okay, let's send this packet to node four. The packet's delivered across the link to node four. Node four receives the packet. The destination is still node six. Node four looks in its routing table. Destination six, let's send to five. Five receives the packet. Destination is still node six. Five looks in the routing table. Destination six, let's send to six. Six receives the packet. 6 is the destination, we've successfully delivered the data from 1 to 6. That process of using the routing tables to determine where to send the data is called forwarding. We forward the data from node to node by looking up the routing tables, the process of forwarding. So we often separate the two processes. The strategies, protocols and algorithms for finding the least cost paths and creating the routing table. So putting the data inside those routing tables is the role usually of a routing protocol. So calculate or collect the information about the network, calculate the least cost paths and then store it at a routing table. That's routing. Or the process, the procedure for a routing protocol. Forwarding is the process of, okay, once we have those routing tables and I have data to send from source to destination, simply look in the routing tables to determine who to send it to. Who to forward the data to until it reaches the destination. So we usually separate out those systems. And for example in the internet the protocol used for forwarding is called the internet protocol, IP. There are different protocols used for routing. So there are separate processes, separate protocols. But both of them are centered around the routing table. Routing creates the routing table, puts data into the routing table, forwarding users or reads the routing table. We saw an example, this example is when we store the routing information in the nodes themselves. Another approach is if we have some central node that stores all the routes. A centralized routing table like this. So we store in some special node from source node three to reach node two, send to node five. From node five to reach node two, send to node four. From four to reach node two, send to node two. And you note that look at the columns two, four, four, four, four. It's just a combination of each of these columns. So it's just a combined information, exactly the same information presented in a different way. Centralized routing table used in a small networks usually when we have one special node that can keep track of the routes and store this. In larger networks distributed routing tables where the same information is stored but split amongst the different nodes is used in this case. And that's what's used in the internet, distributed routing tables. Let's have a look at one example. A very quick example, we'll see another one later. So in the internet our routing tables are distributed amongst the nodes in the internet. And in practice amongst all computers or all devices that use the internet protocol. So on my laptop let's try and look at the routing table. So my laptop when it's connected to the internet it has a routing table. Now it's very simple. And we won't go through the details because we haven't studied addresses and parts of the internet protocol. But we'll see the basic structure. It's a table, there's the header row and there's three rows of data. So three routes in this case. And focus on the first two columns. The first column is the destination. The next second column titled gateway is the next node in the route. So if we want to equate this, so destination is our destination, gateway is our next node. Destination instead of next node is called gateway. It's just another name. The next node in the path. Of course in the internet we don't use numbers to identify computers. We don't use small numbers like this. We use larger numbers. And they're presented in different ways. We'll see some examples here. In fact we've used some names to map the IP addresses to names. Let's simplify that. Just look at the second case. Same information presented in a different way. Three routes from my computer. Skip over the first one for now. The second two are saying in fact in the internet we don't necessarily have to store routes to individual nodes. We can store routes to an entire network of nodes. And that's what the second two rows are. They're saying to reach anyone on this network, anyone starting with address 169254 then send to this destination. All zeros. Well this is a special case. This says in fact don't send to an X1. You can send direct to them. There's no router that you need to send to. No next node to send to. You can send it across your link to that node. This is not the best example because we haven't covered these concepts of networks yet. But these two are saying anyone is on these networks in the third one <IP_ADDRESS> don't send to another switch send direct to that destination. That's what the gateway of all zeros means. The first one says for anyone else anyone else in the world that's what this all zeros case means here. It means if the destination is not one of these two then send to the next node called <IP_ADDRESS>. Again in the internet we can simplify routing tables by instead of storing routes to every possible destination we can use these concepts like a default route. If I want to reach someone starting with 169254 or 192.168.1, send direct to them. Otherwise the first one says send everything else to <IP_ADDRESS>. So this is actually my local router in the network. We will come back and see examples and the exact meanings of those addresses in the topic on internet working on IP. Any questions on routing tables? What you should be able to do and you'll see in the quiz for example given some simple network topology find some least cost routes so go through the steps I think you'll see a quiz question. Here's a network topology tell me the routing table for node three. So how do you do that? What you do is from the network topology you calculate the least cost paths. You don't necessarily need all of them. In the questions at least you won't need to calculate all least cost paths, it won't be too complex. Calculate the least cost paths and then to create the routing table look at those paths and for each destination find the next node in the least cost path to reach that destination and that creates your routing table. The routing table in the simplest form is two columns destination next node in the path optionally a third column of the cost but that's not needed so you get a practice and make sure that you can a understand least cost paths and be how a routing table is constructed. Let's summarize on fixed routing. There's another routing strategy of flooding we'll skip and do that tomorrow and then look at the dynamic or adaptive routing. Fixed routing we calculate or determine the routes when we build the network at network start up we can use either a centralized or distributed approach for storing the routing table and choosing the path, choosing the route so which nodes choose the route because we know the entire network topology when we build the network where does the information come from to calculate the least cost paths? Well we say from all nodes it's an approach where it's as if we have the entire picture of the network to calculate the least cost paths but we never update that information so I have an entire picture of the network at the start, calculate least cost paths and that's it don't update the least cost paths well in practice we may do it on an irregular basis like every few months or when a major change happens because it's never updated it means that often we may be using suboptimal paths paths which are not actually the least cost means it's only really useful when we have small networks or very stable networks so when things don't change much that's okay but if things change often the amount of data being sent changes, the delay changes then we need to be more flexible than fixed routing so what do we do to overcome that for large networks then we use the same approach but simply get regular updates maybe every few minutes get an update by sending special packets through the network telling every other node about their current network conditions, the current link conditions like we saw in our example all nodes send a special packet to every other node saying this is my current, these are my current links these are the current costs as the nodes receive these special packets they can recalculate the least cost paths that's not fixed routing that's the general approach of adaptive routing, we adapt so we still use routing tables we still calculate least cost routes it's just that we do it on a regular basis we continue doing it as the network operates and it's what's used in most medium to large sized networks, packet switching networks and it's what's used in the internet today we need to go through, well for that to work we need to get these regular updates about the current status of the links so there are different ways to collect that information we'll come back to that but let's just summarise well how do we compare it the advantage that we get from adaptive routing compared to fixed routing is that we get better performance because we more often choose the best path so if we're always using the best path we get the best performance with fixed routing if we use a suboptimal path for two weeks then that could be poor performance and we do things like balance the amount of traffic traffic means the amount of data sent across the network that is I'm sending data across this path we detect that there's a lot of congestion there a lot of people are sending across this path so we start using an alternate path so the data travelling through the network starts to be balanced so instead of all the data going in one direction or across one portion of the network we can spread it out with fixed routing that's not so easy so it's much better for performance but it comes at the expense of complexity we need to continuously recalculate the least cost paths and we need to have algorithms to do that and to collect the information there's a lot of overhead if we collect a lot of information on a regular basis the more information we collect the better quality of that information and the better paths we'll choose but the more overhead so we'll see that there are trade-offs there what we'll do tomorrow is go through this other strategy that we skipped over flooding which is completely different from the other from fixed and adaptive routing flooding is just send to everyone if you send to everyone then eventually the destination will receive a copy and you don't need to calculate least cost paths so let's go through flooding tomorrow and finish on routing hopefully tomorrow