1. Power raising circuit (10) for generating, starting from a binary digital signal (X), an output signal (Y) representative of the k-th power of said binary digital signal (X), characterised in that it comprises:
an extracting module for extracting powers of 2 (13, 14), able to subdivide a respective input signal (Zn) into a first part (msb(Zn)) that is the power of 2 immediately lower than or equal to said respective input signal (Zn) and a second part (Znmsb(Zn)) corresponding to the difference between said respective input signal and said first part,
an input module (12) able to apply said binary digital signal (X) as said respective input signal to said extracting module (13, 14), and
a shifter module (15) co-operating with said extracting module (13, 14) for generating at least a portion of said output signal (Y) by means of a shift operation performed on at least one signal derived from said binary digital signal (X).
2. Circuit as claimed in claim 1, characterised in that said shifter module (15) performs said shift operation acting on the second part (XA) of said binary digital signal.
3. Circuit as claimed in claim 1 or claim 2, characterised in that it comprises a circuit module (18) for generating at least a respective portion of said output signal (Y) by inserting zeros between the adjacent bits of said binary digital signal (X).
4. Circuit as claimed in any of the previous claims, characterised in that it comprises a summation node (19) for generating said output signal (Y) as a sum of portions of signal (18, 17) respectively corresponding:
to a power of said first part (A) of said binary input signal (X), and
to the product (A(XA)) of the first part (A) and of the second part (XA) of said binary digital signal (X).
5. Circuit as claimed in any of the previous claims, characterised in that:
said input module (12) has associated, according to a general iterative scheme comprising a set of successive steps, a return path (141) for returning to the input of said extracting module (13, 14) the aforesaid second part generated in a previous step of said iterative scheme, as respective new input signal (Zn) to be used in a further step of said iterative scheme, and
said shifter module (15) has associated an accumulation element (17) for accumulating new portions of said output signal (Y) generated by said shifter module (19) in subsequent steps of said iterative scheme.
6. Circuit as claimed in claim 4 and claim 5, characterised in that, in each of said steps of said iterative scheme, said shifter module (15) generates a portion of said output signal (Y) to be accumulated in said accumulation element (17), said portion to be accumulated being obtained from a signal (Zn) derived from said binary digital signal (X).
7. Circuit as claimed in claim 6 characterised in that said portion of output signal (Y) to be accumulated is obtained starting from the product (msb(Zn)((Znmsb(Zn)) of a first part (msb(Zn)) and of a second part ((Zmsb(Zn)) of signal generated by said at least one extracting module (13, 14) starting from said first binary digital signal (X).
8. Circuit as claimed in any of the claims from 5 to 7, characterised by a control circuit for selectively controlling the number of the steps of said iterative scheme.
9. Circuit as claimed in claim 8, characterised in that said control circuit is sensitive to the signal present on said return path (141) and is able to interrupt the iterative scheme when the aforesaid second part generated in a previous step of said iterative scheme reaches the value of zero.
10. Circuit as claimed in any of the previous claims, characterised in that said extracting module comprises:
an extracting unit (13) that receives said respective input signal (Zn) and determines therefrom as respective output signal (msb(Zn)) said first part of signal that is the power of 2 lower than or equal to said respective input signal, and
a summation unit (14) that receives with opposite signs said respective input signal (Zn) and said respective output signal (msb(Zn)) and determines therefrom said second part of signal (Znmsb(Zn)).
11. Circuit as claimed in any of the previous claims, characterised in that said power is the power of order 2 of said binary digital signal (X).
12. Power raising circuit (10) for generating, starting from a binary digital signal (X), an output signal (Y) representative of the k-th power of said binary digital signal (X), characterised in that it comprises a circuit module (18) for generating at least a respective portion of said output signal (Y) by inserting k zeros between the adjacent bits of said binary digital signal (X).
13. Method for generating, starting from a binary digital signal (X), an output signal (Y) representative of the k-th power of said binary digital signal (X), characterised by the steps of:
extracting from said binary digital signal (X) representative of a respective input signal (Zn) a first part (msb(Zn)) that is the power of 2 immediately lower than or equal to said respective input signal (Zn) and a second part (Znmsb(Zn)) corresponding to the difference between said respective input signal and said first part,
generating at least one portion of said output signal (Y) by means of a shift operation performed on at least one signal extracted from said binary digital signal (X).
14. Method as claimed in claim 13, characterised by the step of
generating said at least one portion of said output signal (Y) by means of a shift operation acting on the second part (XA) of said binary digital signal.
15. Method as claimed in claim 13 or claim 14, characterised by the step of
generating said at least one portion of said output signal (Y) by inserting zeros between the adjacent bits of said binary digital signal (X).
16. Method as claimed in any of the claims from 13 to 15, characterised by the step of:
generating said output signal (Y) as a sum of portions of signal (18, 17) respectively corresponding:
to a power of said first part (A) of said binary input signal (X), and
to the product (A(XA)) of the first part (A) and of the second part (XA) of said binary digital signal (X).
17. Method as claimed in any of the claims from 13 to 15, characterised by an iterative scheme comprising the steps of:
returning back said second part generated in a previous extracting step of said iterative scheme, as respective new input signal (Zn) to be used in a further step of said iterative scheme,
extracting from said respective new input signal (Zn) a new first part (msb(Zn)) that is the power of 2 immediately lower than or equal to said respective new input signal (Zn) and a new second part (Znmsb(Zn)) corresponding to the difference between said respective new input signal and said new first part,
generating portions of said output signal (Y) by means of shift operations performed on at least one of said respective new input signal extracted from said binary digital signal (X), and
accumulating said portions of said output signal (Y) in subsequent steps of said iterative scheme.
18. Method as claimed in claim 17, characterised by the step of:
selectively controlling the number of the steps of said iterative scheme.
19. Method for generating, starting from a binary digital signal (X), an output signal (Y) representative of the k-th power of said binary digital signal (X), characterised by the step of:
generating at least one portion of said output signal (Y) by inserting k zeros between the adjacent bits of said binary digital signal (X).
The claims below are in addition to those above.
All refrences to claim(s) which appear below refer to the numbering after this setence.
1. A method of implementing a layer 3 Virtual Private Network (VPN) over an underlying Ethernet network, the Ethernet network implementing a link state protocol in a network control plane to enable each Ethernet node to have a synchronized view of a topology of the Ethernet network and to individually populate a forwarding information base according to a computed view of the network, the method comprising the steps of:
assigning a VPN I-SID to the VPN, the VPN I-SID being a community of interest identifier with relevance to the network control plane for selective installation of forwarding state in the Ethernet node forwarding information bases, but not used to forward traffic on the Ethernet network;
establishing a first Virtual Routing and Forwarding table (VRF) for the VPN on a first node in the link state protocol controlled Ethernet network,
assigning the VPN I-SID to the first VRF;
advertising the VPN I-SID in a first link state protocol link state advertisement by the first node;
establishing a second VRF for the VPN on a second node in the link state protocol controlled Ethernet network;
assigning the VPN I-SID to the second VRF;
advertising the second attachment of the I-SID in a link state protocol link state advertisement by the second node; and
using the VPN I-SID when transmitting packets of data on the link state protocol controlled Ethernet network to allow a node that receives the packets to identify the correct VRF to be used for further handling of the packets.
2. The method of claim 1, further comprising the steps of:
establishing a plurality of additional VRFs for the VPN on other nodes in the link state protocol controlled Ethernet network;
assigning the VPN I-SID to the other VRFs; and
advertising the attachment of the I-SID to the other VRFs in link state protocol link state advertisements by the other nodes.
3. The method of claim 1, wherein iBGP is used to exchange customer routes tagged with the identifying I-SID between the VRFs.
4. The method of claim 3, wherein the I-SIDs identifying the VRFs are also exchanged via iBGP.
5. The method of claim 1, wherein link state protocol advertisements are used to exchange customer routes tagged with the identifying I-SID between the VRFs.
6. The method of claim 5, wherein the link state protocol advertisements are used to also exchange routing information of the link state protocol controlled Ethernet network.
7. The method of claim 6, wherein the link state protocol is Intermediate-System to Intermediate-System (IS-IS) and the link state protocol advertisements have a Type Length Value (TLV) to specify to the nodes on the link state protocol controlled Ethernet network that the IS-IS link state advertisement carries customer routes associated with a VPN.
8. The method of claim 7, wherein the TLV enables IPv4 as well as IPv6 customer routes to be carried in the IS-IS link state protocol advertisement.
9. A method of implementing an Internet Protocol (IP) Virtual Private Network (VPN) over a link state protocol controlled Ethernet network, the method comprising the steps of:
establishing a first Virtual Routing and Forwarding table (VRF) for the IP VPN on a first node in the link state protocol controlled Ethernet network,
advertising a first global IP address assigned to the first VRF and a MAC address of the first node in a link state advertisement in the link state protocol controlled Ethernet network, the first global IP address identifying the first VRF on the first node;
establishing forwarding state to the MAC address in intermediate nodes of the link state protocol controlled Ethernet network; and
when a second node on the link state protocol controlled Ethernet network has an IP packet including a first IP header and being associated with the VPN that is to be transmitted to the first node on the link state protocol controlled Ethernet network, prepending a second IP header to the packet by the second node, the second IP header including as a destination IP address the global IP address assigned to the first VRF, and then prepending a third header to the packet by the second node, the third header including the MAC address of the first node, and forwarding the packet with the second and third headers onto the link state protocol controlled Ethernet network.
10. The method of claim 9, wherein the intermediate nodes on the link state protocol controlled Ethernet network forward the IP packet using the MAC address of the third header according to the installed forwarding state for that MAC address in the nodes of the link state protocol controlled Ethernet network.
11. The method of claim 10, wherein when the first node receives the packet, it reads the third header to learn that the destination address of the MAC header matches its own MAC address, and then reads the IP address of the second header to identify the first VRF.
12. The method of claim 11, wherein the first IP header is a client IP header containing routing information that may be used in connection with routing information in the first VRF to determine a customer facing interface for the IP packet.
13. The method of claim 9, wherein iBGP is used to exchange customer routes between the first VRF and other VRFs associated with the VPN that have been instantiated on other nodes in the link state protocol controlled Ethernet network.
14. The method of claim 9, wherein link state protocol advertisements are used to exchange customer routes between the first VRF and other VRFs associated with the VPN that have been instantiated on other nodes in the link state protocol controlled Ethernet network.