Method for providing communications network stability
First Claim
1. 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σ
/ε
.right brkt-top., where σ
is a burst size of packet injections, and ε
is a utilization factor of the network;
calculating a routing factor c, the routing factor c calculated as c=2(2Δ
/ε
)d-1, where d is the length of a longest path in the network for any particular one packet of the plurality of packets, ε
is a utilization factor of the network, and Δ
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 Sij (t) of the plurality of packets as a function of the routing factor c; and
determining a maximum number Rij (t) of packets which will be routed through a particular switch in the network such that Rij (t)=|Sij (t)|+Lε
/(2δ
), where δ
is a maximum of number input ports and output ports of the particular switch.
3 Assignments
0 Petitions
Accused Products
Abstract
A packet routing technique which is stable for all networks in the presence of input blocking and output blocking. The packets injected within a network are examined and based on a historical perspective of those packets a determination is made on how to route individual packets throughout the network in a stable manner. In particular, in order to achieve complete network stability, individual switches within the network need to choose matchings, i.e., input to output port connections, that reflect the demand on each port-pair within the switches. Thus, if all packets are guaranteed to be in the network for at most a maximum number of time blocks, then a particular switch will have seen all the packets injected in the network at least that maximum number of blocks ago. Thus, a switch can choose port-pair combinations to facilitate the transmission of packets such that each packet currently in the network will reach its intended destination within the maximum number of blocks after its injection therefore providing network stability.
5 Citations
2 Claims
-
1. 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σ
/ε
.right brkt-top., where σ
is a burst size of packet injections, and ε
is a utilization factor of the network;calculating a routing factor c, the routing factor c calculated as c=2(2Δ
/ε
)d-1, where d is the length of a longest path in the network for any particular one packet of the plurality of packets, ε
is a utilization factor of the network, and Δ
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 Sij (t) of the plurality of packets as a function of the routing factor c; and determining a maximum number Rij (t) of packets which will be routed through a particular switch in the network such that Rij (t)=|Sij (t)|+Lε
/(2δ
), where δ
is a maximum of number input ports and output ports of the particular switch. - View Dependent Claims (2)
-
Specification
-
- Resources
-
Current AssigneeLucent Technologies, Inc. (Nokia Corporation)
-
Original AssigneeLucent Technologies, Inc. (Nokia Corporation)
-
InventorsZhang, Yihao, Andrews, Daniel Matthew
-
Primary Examiner(s)Pham, Chi H.
-
Assistant Examiner(s)Pham, Brenda H.
-
Application NumberUS09/083,011Time in Patent Office908 DaysField of Search370/389, 370/392, 370/400, 370/412, 370/418, 370/409, 370/380, 370/369, 370/370, 370/233US Class Current370/380CPC Class CodesH04L 45/02 Topology update or discoveryH04L 47/28 in relation to timing consi...
