Integrated circuit and method for time slot allocation

• US 20070195748A1
• Filed: 03/23/2005
• Published: 08/23/2007
• Est. Priority Date: 04/05/2004
• Status: Active Grant

• Current Assignee: Network System Technologies LLC
• Original Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Inventors: Radulescu, Andrei
• Granted Patent: US 7,564,865 B2
• Time in Patent Office: Days
• US Class Current: 370/351
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation

Abstract

An integrated circuit comprising a plurality of processing modules (M, S; IP) and a network (N) arranged for coupling said modules (M, S; IP) is provided. Said integrated circuit further comprises a plurality of network interfaces (NI) each being coupled between one of said processing modules (M, S; IP) and said network (N). Said network (N) comprises a plurality of routers (R) coupled via network links (L) to adjacent routers (R). Said processing modules (M, S; IP) communicate between each other over connections using connection paths (C1-C12) through the network (N), wherein each of said connection paths (C1-C12) employ at least one network link (L) for a required number of time slots. At least one time slot allocating unit (SA) is provided for computing a link weight factor for at least one network link (L) in said connection path (C1-C12) as a function of at least one connection requirement for said at least one network link (L), for computing a connection path weight factor for at least one connection path (C1-C12) as a function of the computed link weight factor of at least one network link (L) in said connection path (C1-C12), and for allocating time slots to said network links (L) according to the computed connection path weight factors.

Claims

1. Integrated circuit comprising a plurality of processing modules (M, S;

IP) and a network (N) arranged for coupling said modules (M, S;

IP), comprising

a plurality of network interfaces (NI) each being coupled between one of said processing modules (M, S;

IP) and said network (N);

wherein said network (N) comprises a plurality of routers (R) coupled via network links (L) to adjacent routers (R);

wherein said processing modules (M, S;

IP) communicate between each other over connections using connection paths (C1-C12) through the network (N), wherein each of said connection paths (C1-C12) employ at least one network link (L) for a required number of time slots,

at least one time slot allocating unit (SA) for computing a link weight factor for at least one network link (L) in said connection path (C1-C12) as a function of at least one connection requirement for said at least one network link (L), for computing a connection path weight factor for at least one connection path (C1-C12) as a function of the computed link weight factor of at least one network link (L) in said connection path (C1-C12), and for allocating time slots to said network links (L) according to the computed connection path weight factors.

2. Integrated circuit according to claim 1, wherein said at least one time slot allocating unit (SA) is further adapted to compute a connection path weight factor for at least one connection path (C1-C12) as a function of said at least one connection requirement of the said connection path.

3. Integrated circuit according to claim 1, wherein said connection requirements comprise bandwidth, latency, jitter, priority and/or slot allocation requirements of the connection path (C1-C12).

4. Integrated circuit according to claim 2, wherein said at least one time slot allocating unit (SA) is adapted to compute said function for computing link weights as a weighted sum of bandwidth and/or slot table requirements for said at least one network link (L).

5. Integrated circuit according to claim 3, wherein said at least one time slot allocating unit (SA) is adapted to compute said function for computing connection path weights as a weighted sum of the computed link weight factors of at least one network link (L) in said connection path (C1-C12) and the bandwidth, latency, jitter, priority and/or slot allocation requirements of the said connection path (C1-C12).

6. Integrated circuit according to claim 1, wherein said at least one time slot allocating unit (SA) is adapted to allocate time slots to said at least one network link (L) in decreasing order of connection path weight factor.

7. Integrated circuit according to claim 1, wherein said at least one time slot allocating unit (SA) is adapted to compute said connection path weight factors based on said computed link weight factors, the length of said connection path (C1-C12), and the number of time slots required for said connection path (C1-C12).

8. Integrated circuit according to claim 7, wherein said at least one time slot allocating unit (SA) is adapted to compute said connection path weight factors based on said computed link weight factors, the length of said connection path (C1-C12), and the number of time slots required for said connection path weighted by a first, second and third weight factor (a1, a2, a3), respectively.

9. Integrated circuit according to claim 7, wherein at least one time slot allocating unit (SA) is arranged in at least one of said plurality of network interface (NI) and comprises a first time slot table (ST) with entries specifying connections to which time slots are allocated to, and said routers (R) comprise second time slot tables (ST) with entries representing reservations of time slots without specifying connections.

10. Integrated circuit according to claim 9, wherein said routers (R) move data arranged in packets with packet headers according to said packet headers.

11. Integrated circuit according to claim 1, wherein at least one time slot allocating unit (SA) is arranged in at least one of said plurality of network interface (NI) and comprises a first time slot table (ST) with entries specifying connections to which time slots are allocated to, and said routers (R) comprise second time slot tables (ST) with entries comprising information for routing data in said network (N).

12. Integrated circuit according to claim 9, wherein said time slot allocating unit (SA) is adapted to find the first free time slots in said first and second slot tables (ST1, ST2) along said connection paths (C1-C12) according to the required time slots of said connections (C1-C12).

13. Integrated circuit according to claim 9, said time slot allocating unit (SA) is adapted to find the required free time slots in said first and second time slot tables (ST1, ST2) for said connections (C1-C12) by finding at least a first free time slot in one of said first and second slot tables (ST1, ST2), by computing positions which are equally distanced in the slot table, and by searching locally around the computed positions to find the nearest free time slot.

14. Integrated circuit according to claim 13, wherein the search for free time slots is started from the most loaded network link (L).

15. Integrated circuit according to claim 9, wherein said time slot allocating unit (SA) is adapted to find the required free time slots in said first and second time slot tables (ST1, ST2) for said connections (C1-C12) by traversing said slot tables (ST1, ST2), by filtering the reserved time slots, and by shifting the searched time slots with one position for each network link (L) in said connection (C1-C12).

16. Method for time slot allocation in an integrated circuit comprising a plurality of processing modules (M, S;

IP) and a network (N) arranged for coupling said modules (M, S;

IP), and a plurality of network interfaces (NI) each being coupled between one of said processing modules (M, S;

IP) and said network (N) comprising a plurality of routers (R) coupled via network links (L) to adjacent routers (R);

comprising the steps of;

communicating between processing modules (M, S;

IP) over connections using connection paths (C1-C12) through the network (N), wherein each of said connection paths (C1-C12) employ at least one network link (L) for a required number of time slots,

computing a link weight factor for at least one network link (L) in said connection path (C1-C12) as a function of at least one connection requirement for said network links (L),

computing a connection path weight factor for at least one connection path (C1-C12) as a function of the computed link weight factor of at least one network link (L) in a connection path (C1-C12), and

allocating time slots to said network links (L) according to the computed connection path weight factors.

17. Data processing system comprising:

a plurality of processing modules (M, S;

IP) and a network (N) arranged for coupling said modules (M, S;

IP), comprising;

a plurality of network interfaces (NI) each being coupled between one of said processing modules (M, S;

IP) and said network (N);

wherein said network (N) comprises a plurality of routers (R) coupled via network links (L) to adjacent routers (R);

wherein said processing modules (M, S;

IP) communicate between each other over connections using connection paths (C1-C12) through the network (N), wherein each of said connection paths (C1-C12) employ at least one network link (L) for a required number of time slots,

at least one time slot allocating unit (SA) for computing a link weight factor for at least one network link (L) in said connection path (C1-C12) as a function of at least one connection requirement for said at least one network link (L), for computing a connection path weight factor for at least one connection path (C1-C12) as a function of the computed link weight factor of at least one network link (L) in said connection path (C1-C12), and for allocating time slots to said network links (L) according to the computed connection path weight factors.