What is a WAI-ARIA compliant implementation for navigation bar/menu

We are in the process of implementing (i.e. adding) WAI-ARIA support to the main navigation menu of a web portal. Menu is the one shown here:

Navigation menu screenshot

Menu is implemented by means of classic <ul> / <li> / <a> DOM tree, styled with CSS to look like horizontal tabs.

What is a WAI-ARIA compliant implementation for such a widget?

I've read many parts of most recent WAI-ARIA specs from w3org for a general understanding, taxonomy, and so on. Then I've read about several examples of UI widget implementations. I could not find any example specifically targetd at such a CSS navigation menu. The closest widgets I've always found around are the Menu, the MenuBar, and the TabPanel. Of course I also looked in Free ARIA Community group (where this question was originally posted).

I'd say that none of those widgets exactly match a (CSS) navigation menu. As an example, TabPanel may control some content in the page (--> aria-controls), maybe MenuBar too; but I'm not at all sure that a navigation menu controls content in the page (it controls the next page to show). Without going further, there are some other differences as well. References are at the end of the post. If anyone as better (or more fit) examples of navigation menu, we'd be glad to know about them.

References

Solution

A possible implementation would be:

HTML structure:

<div> <!-- Outer wrapper -->
  <ul> <!-- Main navigation bar container -->
    <li> <!-- First-level item without submenu -->
      <a> <!-- Destination URL -->
      </a>
    </li>
    <li> <!-- First-level item with submenu -->
      <a> <!-- Destination URL -->
      </a>
      <ul> <!-- Second-level menu container -->
        <li> <!-- Second-level item -->
          <a>
          </a> <!-- Destination URL -->
        </li>
      </ul>
    </li>
  </ul>
</div>

Roles:

role=”navigation” for outer wrapper <div>
role="menubar" for <ul> navigation bar container
role="menu" for second-level <ul> containers
role="presentation" for first- and second-level <li> menu items (they are not needed in the exposed accessible menubar structure)
role="menuitem" for first- and second-level <a> menu items

Properties:

aria-haspopup="true" for first-level <a> menu items having a submenu
aria-labelledby="ID of previous <a> menu item" for second-level <ul> containers

States:

aria-selected="true" on currently visited first- or second-level <a> item; aria-selected="false" on the other <a> items. That is to enforce the concept “selected <==> current page”
aria-expanded="true/false" for second-level <ul> containers
aria-hidden="true/false" for second-level <ul> containers
aria-activedescendant="" for main <ul> navigation bar container. This is an alternative to working with tabindex
tabindex=0 on currently visited <a> item; tabindex=-1 on the other <a> items. That is in order to first focus on the current page when tabbing to the navigation bar. It is an alternative to working with aria-activedescendant

Keyboard:

Tab: Move focus in/out of the menu from other points in the web application.
Shift+Tab: Move focus in/out of the menu from other points in the web application, in the reversed order.
Right arrow: Next navigation bar item
Left arrow: Previous navigation bar item
Enter: Activate currently focused item (i.e. navigate to corresponding URL)
Space: Activate currently focused item (i.e. navigate to corresponding URL)

Aug/2014: aria-selected Vs menuitem

In reply to @Joshua Muheim comment: now I can see from here, as well as from his reference, that aria-selected attribute is not allowed for menuitem role.
As I read from this recent SO answer there are some solutions given the current state of things, and there is a new proposed attribute too.