A network interconnect device and message exchange protocol for forwarding data among packet forwarding devices are provided. According to one aspect of the present invention, data is forwarded between a first and second packet forwarding device coupled to an interconnect device. The interconnect device receives a menu message from the first packet forwarding device that indicates one or more types of data that are awaiting transmission on the first packet forwarding device. Based upon the menu message, the interconnect device transmits an order message selecting a type of data of the one or more types of data awaiting transmission to the first packet forwarding device. The interconnect device receives a message from the first packet forwarding device containing data of the type selected by the order message. The interconnect device then forwards the data to the second packet forwarding device. According to another aspect of the present invention, data is forwarded among multiple packet forwarding devices through an interconnect device by selecting a configuration of the interconnect device based upon ports to which the packet forwarding devices have data to transfer. For each of the ports of the interconnect device, an indication of ports to which an attached packet forwarding device has data to transfer is received. Based upon these port indications, a configuration of the interconnect device is selected that contains non-conflicting paths through the interconnect device. Data is then forwarded in accordance with the selected configuration by forwarding data from those of the of packet forwarding devices coupled to ports that have been selected as source ports to corresponding destination ports.