We want to do:
In order to reduce Forwarding Table size on topological address schemes, we want to be able to compare addresses in a way that allows us to get the most approximated match. That would pave the way to easily implement hierarchical routing based on address prefixes, load balancing (for QoS cubes not sensible to PDU reordering), etc.
Problems that we currently find in RinaSim:
In the current RinaSim, it seems that address lookup is based on simply iteration over all the entries in the Forwarding Table until an entry that perfectly matches the searched address is found. Otherwise NULL is returned. With that, for example, we cannot compare just address prefixes, or define a default gate.
Proposed modifications/extensions:
We propose to make PDU Forwarding Table Entry an abstract class having a “compare” function that returns how much an address+QoS matches the current entry (like a similarity score). For example, a function returning a double considering 1.0 a perfect match, 0.0 no matching entry and in-between for partial matches. Then, the entry with the best match value would be returned. With that we can use distinct PDU Forwarding Table Entry subclassess depending on the underlying routing scheme, reducing Forwarding Table size and computing time (search and update).
Discussion
-
gaixas1
2014-11-13- assigned_to: gaixas1
-
Vladimír Veselý
2015-01-14- status: open --> accepted
-
Vladimír Veselý
2015-01-14Point taken! We can define interface for PDUForwardingTableEntry from which children classes could inherit certain attributes and functions. But in order to progress in your proposition, please invent for us some address+QoS hierarchy scheme that you would like to test.
Currently we are using strings as APNs. We do not plan to change that so thing about some examples with string delimiters to force hierarchy. As for QoSCube, we are using simple function QoSCube::countFeasibilityScore() to compare QoSCubes between each other. However, it is very naive approach. Be so kind and propose another comparison strategy.
-
gaixas1
2015-01-14Well, really the best solution would be for specific routing schemas to have their own forwarding table, but this address comparison can simply make a solution usable for most routing schemas.
For example, in the schema based on regions, addresses can be simply "regionId.nodeId". And the forwarding table could be populated in the following way:
- For nodes connected at N-1 level and nodes in the same region, add full entry: "regionId.nodeId" + qosId + port
- For all other regions, add "region" entry: "regionId.0" + qosId + port*Note that no node can have nodeId = 0.
If entries on the forwarding table have some compare(Address, qos) function, that could simply return 0 if either the address or qos does not match, or return 2 or 1 if both match and the entry is for the full address or only for the region.
Then, when iterating through the entries on the forwarding table, we use that compare function, and search for the entry that gives us the maximum value (!= 0, as that means not found).
The use of address as strings does not matter to much for that algorithm, as the forwarding table entries could be stored in any way and then the address only needs to be parsed at the compare function.
PD. But as I've said, custom forwarding tables should be better. For this same schema, I'm using one that store entries as a map with a pair of integers <regionId, nodeId> as a key, then, when look up is called, it parses the address into <region, nodeId>, search that pair in the map and if not found then search for <region,0>, so only two queries into a map structure in order to find the next hop.
Last edit: gaixas1 2015-01-14