I think it's the prequel, A Deepness in the Sky. I thought A Fire Upon the Deep had even cooler concepts though.
Both are great reads. Fire Upon the Deep had some cooler concepts, but narrative-wise I prefer Deepness in the sky. The emotional response I had to the memory-control-slavery aspects made my blood boil.