xml based navigation structure within CI

[eluser]codeamatic[/eluser]
I am going to implement an xml based navigation structure into one of my CI websites. The problem isn't that I don't know how to code it, but I'm somewhat lost as to how to structure it within CI. Should this be a Library? Should I load the xml file from within this Library(if you in fact think it should be a library) or should I load it within my constructor? Since this navigation will be called on every page, should it be called from within my extended controllers constructor? It will essentially create all of the html markup necessary for the navigation. As mentioned before, I'm not looking for coding assistance, but more or less someone to point me in the right direction as to how I would/should implement into CI.

Thanks in advance...