Eliminating livelock by assigning the same priority state to each message that is inputted into a flushable routing system during N time intervals

Claim 1

Message routing apparatus for preventing livelock in a network of interconnected nodes, said network having a flushable time T and each one of said nodes having a plurality of input and output paths, said message routing apparatus comprising: an input message processor having an interval timer for generating a sequence of at least N time intervals, n 1 through n N , a register for receiving input messages, and means for assigning a priority state p to each one of said input messages in said register during a nth time interval of said N time intervals, where each nth time interval is of duration T; an output message processor connected to said input message processor through said network; and a node message processor at each one of said nodes having means for reading said priority state on each arriving message, logic means for awarding priority to said arriving messages with priority state (p-1) during said nth time interval and to said arriving messages with priority state p during an (n+1)th time interval, and means for outputting said arriving message awarded priority on a one of said output paths toward said output message processor.

Claim 5

A method for routing a digital message through a network of interconnected nodes, said network having a flushable time T and each one of said nodes having a plurality of input and output paths, said method comprising the steps of: generating a sequence of N time intervals, n 1 through n N , each nth time interval having a duration T; assigning each said digital message generated during an nth time interval of said N time intervals a priority state p; inputting each said digital message with said priority state p to said network during said nth time interval; and determining the message priority at each one of said nodes so that digital messages with priority state (p-1) have priority during said nth time interval and digital messages with priority state p have priority during an (n+1)th time interval, wherein digital messages with said priority state (p-1) are flushed from said network during said nth time interval.

Claim 6

A method for routing a digital message through a network of interconnected nodes, said network having a flushable time T and each one of said nodes having a plurality of input and output paths, said method comprising the steps of: generating a sequence of N time intervals, n 1 through n N , each nth time interval having a duration T; assigning each said digital message generated during an nth time interval of said N time intervals a priority state p; inputting each said digital message with said priority state p to said network during said nth time interval; and determining the message priority at each one of said nodes so that digital messages with priority state (p-1) have priority during said nth time interval and digital messages with priority state p have priority during an (n+1)th time interval, wherein digital messages with said priority state (p-1) are flushed from said network during said nth time interval.