Patent ID: 6147990
Filing Date: 2000-11-14
Classification: H04L

Abstract:
A method of routing a plurality of packets in a network, the network having a plurality of switches, the method comprising the steps of:partitioning a plurality of time blocks L such that L=.left brkt-top.2.sigma./.epsilon..right brkt-top., where .sigma. is a burst size of packet injections, and .epsilon. is a utilization factor of the network;calculating a routing factor c, the routing factor c calculated as c=2(2.DELTA./.epsilon.).sup.d-1, where d is the length of a longest path in the network for any particular one packet of the plurality of packets, .epsilon. is a utilization factor of the network, and .DELTA. is a maximum number of input ports or output ports of any one switch in the plurality of switches in the network;identifying a subset S.sub.ij (t) of the plurality of packets as a function of the routing factor c; anddetermining a maximum number R.sub.ij (t) of packets which will be routed through a particular switch in the network such that R.sub.ij (t)=.vertline.S.sub.ij (t).vertline.+L.epsilon./(2.delta.), where .delta. is a maximum of number input ports and output ports of the particular switch.